mlsanityData to 7 Oct 2026

Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning

arXiv 2103.13883 ↗First posted 25 Mar 2021cs.LG cs.AI stat.MLcited by 42

On the map: Offline RL and imitation learning from data → Offline RL algorithms

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.

Key facts. Cited by 42 papers in the map (data through 7 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.

Builds on

14 of 61 references.

Closest ancestors · 5

Same direction, newest first

  1. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency5 Feb
  2. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  3. 2020Batch Value-function Approximation with Only Realizability11 Aug
  4. 2020Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning7 Jul
  5. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 9

  1. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  2. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  3. 2019Batch Policy Learning under Constraintscited by 242
  4. 2019A Theoretical Analysis of Deep Q-Learningcited by 212
  5. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  6. 2016A vector-contraction inequality for Rademacher complexitiescited by 141
  7. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
  8. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 118
  9. 2019On Value Functions and the Agent-Environment Boundarycited by 19

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 16; 2023: 7; 2024: 5; 2025: 3; 2026: 5.

42 papers.

Sort:

By area:

  1. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  2. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  3. 2022A Review of Off-Policy Evaluation in Reinforcement Learningcited by 92
  4. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  5. 2023Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcarecited by 41
  6. 2021Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptoticscited by 27
  7. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coveragecited by 26
  8. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  9. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalizationcited by 25
  10. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  11. 2022Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Setscited by 18
  12. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
30 more
  1. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learningcited by 13
  2. 2022Relational Reasoning via Set Transformers: Provable Efficiency and Applications to MARLcited by 12
  3. 2023Robust Fitted-Q-Evaluation and Iteration under Sequentially Exogenous Unobserved Confounderscited by 12
  4. 2022Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Explorationcited by 11
  5. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  6. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learningcited by 10
  7. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  8. 2022On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardnesscited by 7
  9. 2025On Learning Verifiers and Implications to Chain-of-Thought Reasoningcited by 6
  10. 2023VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximationcited by 3
  11. 2023When is Offline Policy Selection Sample Efficient for Reinforcement Learning?cited by 3
  12. 2024Taming "data-hungry" reinforcement learning? Stability in continuous state-action spacescited by 3
  13. 2024Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processescited by 3
  14. 2021Exploiting Action Impact Regularity and Exogenous State Variables for Offline Reinforcement Learningcited by 2
  15. 2022An Experimental Comparison Between Temporal Difference and Residual Gradient with Neural Network Approximationcited by 2
  16. 2023A Unified Framework of Policy Learning for Contextual Bandit with Confounding Bias and Missing Observationscited by 2
  17. 2023Fitted value iteration methods for bicausal optimal transportcited by 2
  18. 2026Towards Efficient Constraint Handling in Neural Solvers for Routing Problemscited by 2
  19. 2024Reward-Relevance-Filtered Linear Offline Reinforcement Learningcited by 1
  20. 2024Analyzing and Bridging the Gap between Maximizing Total Reward and Discounted Reward in Deep Reinforcement Learningcited by 1
  21. 2022On Practical Reinforcement Learning: Provable Robustness, Scalability, and Statistical Efficiencycited by 0
  22. 2022Statistical Estimation of Confounded Linear MDPs: An Instrumental Variable Approachcited by 0
  23. 2022InFi: End-to-End Learning to Filter Input for Resource-Efficiency in Mobile-Centric Inferencecited by 0
  24. 2024A priori Estimates for Deep Residual Network in Continuous-time Reinforcement Learningcited by 0
  25. 2025An Information-Theoretic Analysis of OOD Generalization in Meta-Reinforcement Learningcited by 0
  26. 2025Algorithmic Guarantees for Distilling Supervised and Offline RL Datasetscited by 0
  27. 2026A Measure-Theoretic Finite-Sample Theory for Adaptive-Data Fitted Q-Iterationcited by 0
  28. 2026A Rigorous, Tractable Measure of Model Complexitycited by 0
  29. 2026Off-Policy Evaluation for Missingness-Aware Policies in MDPs with Rewards Missing Not at Randomcited by 0
  30. 2026From Weak Data to Strong Policy: Q-Targets Enable Provable In-Context Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
  2. 2020Provably Good Batch Reinforcement Learning Without Great Exploration
  3. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
  4. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  5. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
  6. 2021Continuous Doubly Constrained Batch Reinforcement Learning
  7. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach
  8. 2025Thompson Sampling in Online RLHF with General Function Approximation