Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
This addresses the challenge of efficient batch RL for practitioners by reducing error scaling, though it appears incremental as it builds on existing Bellman error estimation concepts.
The paper tackles the problem of approximating optimal Q-values in batch reinforcement learning by proving performance guarantees for two algorithms that achieve linear-in-horizon error propagation, compared to quadratic dependence in classical methods like Fitted Q-Iteration.
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.