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

2020/03/09 by Tengyang Xie, Nan Jiang, Xie, Tengyang +1 · 1 voice · 7 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Advanced Multi-Objective Optimization Algorithms #Reinforcement Learning in Robotics #cs.AI #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2003.03924

openalex publication_date 2020/03/09 · openalex created_date 2020/03/13 · openalex updated_date 2026/07/28

Abstract

We prove performance guarantees of two algorithms for approximating Q^⋆ 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.

Citations

• Generalized Optimal Matching Methods for Causal Inference

Cited by

• Fast Rates for the Regret of Offline Reinforcement Learning
• Near-Optimal Offline Reinforcement Learning via Double Variance\n Reduction
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
• Conservative Q-Learning for Offline Reinforcement Learning
• Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can\n be Exponentially Harder than Online RL

Discussions

• Q* Approximation for Batch Reinforcement Learning: A Theoretical Comparison [hn, 21 points, 3 comments]

Related

• Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learning
• Batch Value-function Approximation with Only Realizability
• Sharp Analysis of Smoothed Bellman Error Embedding
• Provably Good Batch Reinforcement Learning Without Great Exploration
• Approximated Multi-Agent Fitted Q Iteration