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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyxie2020q

Related papers

• Risk Bounds And Rademacher Complexity In Batch Reinforcement Learning (2021)0.00
• Approximated Multi-agent Fitted Q Iteration (2021)0.00
• Stabilizing Q-learning With Linear Architectures For Provably Efficient Learning (2022)0.00
• Minimax-optimal Off-policy Evaluation With Linear Function Approximation (2020)0.00
• Fitted Q Evaluation Without Bellman Completeness Via Stationary Weighting (2025)0.00
• On The Estimation Bias In Double Q-learning (2021)0.00
• Switching The Loss Reduces The Cost In Batch (offline) Reinforcement Learning (2024)0.00
• Iterated \(q\)-network: Beyond One-step Bellman Updates In Deep Reinforcement Learning (2024)0.00