Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
arXiv:2003.03924
Abstract
We prove performance guarantees of two algorithms for approximating in batch reinforcement learning. Compared to classical iterative methods such as Fitted Q-Iteration---whose performance loss incurs quadratic dependence on horizon---these methods estimate (some forms of) the Bellman error and enjoy linear-in-horizon error propagation, a property established for the first time for algorithms that rely solely on batch data and output stationary policies. One of the algorithms uses a novel and explicit importance-weighting correction to overcome the infamous "double sampling" difficulty in Bellman error estimation, and does not use any squared losses. Our analyses reveal its distinct characteristics and potential advantages compared to classical algorithms.
Published in UAI 2020
References in corpus (4)
Cited by in corpus (13)
- Conservative Q-Learning for Offline Reinforcement Learning
- What are the Statistical Limits of Offline RL with Linear Function Approximation?
- Provably Good Batch Reinforcement Learning Without Great Exploration
- Batch Value-function Approximation with Only Realizability
- Is Pessimism Provably Efficient for Offline RL?
- Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
- Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
- Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
- Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning
- Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
- Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
- Fast Rates for the Regret of Offline Reinforcement Learning
- A maximum-entropy approach to off-policy evaluation in average-reward MDPs