# Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning

arXiv: https://arxiv.org/abs/2103.13883 · HTML: https://mlsanity.com/paper/2103.13883/

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 14 of its 61 references that are in the map.
- First posted on arXiv 25 Mar 2021.

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

## Builds on (most cited first, 14 of 14)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Batch Policy Learning under Constraints](https://mlsanity.com/paper/1903.08738/) (2019)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [A vector-contraction inequality for Rademacher complexities](https://mlsanity.com/paper/1605.00251/) (2016)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling](https://mlsanity.com/paper/1906.03393/) (2019)
- [Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes](https://mlsanity.com/paper/1908.08526/) (2019)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency](https://mlsanity.com/paper/2102.02981/) (2021)
- [Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/2007.03760/) (2020)
- [On Value Functions and the Agent-Environment Boundary](https://mlsanity.com/paper/1905.13341/) (2019)

## Built on by (most cited first, 30 of 42)

- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [A Review of Off-Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2212.06355/) (2022)
- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcare](https://mlsanity.com/paper/2305.01738/) (2023)
- [Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics](https://mlsanity.com/paper/2105.03863/) (2021)
- [Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage](https://mlsanity.com/paper/2106.03207/) (2021)
- [Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2205.13589/) (2022)
- [Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization](https://mlsanity.com/paper/2111.13807/) (2021)
- [On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2211.13208/) (2022)
- [Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Sets](https://mlsanity.com/paper/2205.10671/) (2022)
- [When is Realizability Sufficient for Off-Policy Reinforcement Learning?](https://mlsanity.com/paper/2211.05311/) (2022)
- [Oracle Inequalities for Model Selection in Offline Reinforcement Learning](https://mlsanity.com/paper/2211.02016/) (2022)
- [Robust Fitted-Q-Evaluation and Iteration under Sequentially Exogenous Unobserved Confounders](https://mlsanity.com/paper/2302.00662/) (2023)
- [Relational Reasoning via Set Transformers: Provable Efficiency and Applications to MARL](https://mlsanity.com/paper/2209.09845/) (2022)
- [Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Exploration](https://mlsanity.com/paper/2209.07376/) (2022)
- [Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data](https://mlsanity.com/paper/2307.04354/) (2023)
- [Bellman Residual Orthogonalization for Offline Reinforcement Learning](https://mlsanity.com/paper/2203.12786/) (2022)
- [Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments](https://mlsanity.com/paper/2208.11040/) (2022)
- [On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardness](https://mlsanity.com/paper/2210.10464/) (2022)
- [On Learning Verifiers and Implications to Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.22650/) (2025)
- [VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximation](https://mlsanity.com/paper/2302.12780/) (2023)
- [When is Offline Policy Selection Sample Efficient for Reinforcement Learning?](https://mlsanity.com/paper/2312.02355/) (2023)
- [Taming "data-hungry" reinforcement learning? Stability in continuous state-action spaces](https://mlsanity.com/paper/2401.05233/) (2024)
- [Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes](https://mlsanity.com/paper/2404.00099/) (2024)
- [Towards Efficient Constraint Handling in Neural Solvers for Routing Problems](https://mlsanity.com/paper/2602.16012/) (2026)
- [Exploiting Action Impact Regularity and Exogenous State Variables for Offline Reinforcement Learning](https://mlsanity.com/paper/2111.08066/) (2021)
- [An Experimental Comparison Between Temporal Difference and Residual Gradient with Neural Network Approximation](https://mlsanity.com/paper/2205.12770/) (2022)
- [A Unified Framework of Policy Learning for Contextual Bandit with Confounding Bias and Missing Observations](https://mlsanity.com/paper/2303.11187/) (2023)
- [Fitted value iteration methods for bicausal optimal transport](https://mlsanity.com/paper/2306.12658/) (2023)

## Abstract (arXiv)

This paper considers batch Reinforcement Learning (RL) with general value function approximation. Our study investigates the minimal assumptions to reliably estimate/minimize Bellman error, and characterizes the generalization performance by (local) Rademacher complexities of general function classes, which makes initial steps in bridging the gap between statistical learning theory and batch RL. Concretely, we view the Bellman error as a surrogate loss for the optimality gap, and prove the followings: (1) In double sampling regime, the excess risk of Empirical Risk Minimizer (ERM) is bounded by the Rademacher complexity of the function class. (2) In the single sampling regime, sample-efficient risk minimization is not possible without further assumptions, regardless of algorithms. However, with completeness assumptions, the excess risk of FQI and a minimax style algorithm can be again bounded by the Rademacher complexity of the corresponding function classes. (3) Fast statistical rates can be achieved by using tools of local Rademacher complexity. Our analysis covers a wide range of function classes, including finite classes, linear spaces, kernel spaces, sparse linear features, etc.