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

Understand

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.