Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison

Abstract

We prove performance guarantees of two algorithms for approximating $Q^{\star }$ 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.

arXiv commentPublished in UAI 2020

References in corpus (7)

• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Approximate Policy Iteration Schemes: A Comparison
• Generalized Optimal Matching Methods for Causal Inference
• A Kernel Loss for Solving the Bellman Equation
• On the Use of Non-Stationary Policies for Stationary Infinite-Horizon Markov Decision Processes

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