mlsanityData to 7 Oct 2026

Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity

arXiv 2310.01616 ↗First posted 2 Oct 2023cs.LG cs.AIcited by 2

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

Abstract (arXiv)

We theoretically explore the relationship between sample-efficiency and adaptivity in reinforcement learning. An algorithm is sample-efficient if it uses a number of queries n to the environment that is polynomial in the dimension d of the problem. Adaptivity refers to the frequency at which queries are sent and feedback is processed to update the querying strategy. To investigate this interplay, we employ a learning framework that allows sending queries in K batches, with feedback being processed and queries updated after each batch. This model encompasses the whole adaptivity spectrum, ranging from non-adaptive 'offline' (K=1) to fully adaptive (K=n) scenarios, and regimes in between. For the problems of policy evaluation and best-policy identification under d-dimensional linear function approximation, we establish Omega(log log d) lower bounds on the number of batches K required for sample-efficient algorithms with n = O(poly(d)) queries. Our results show that just having adaptivity (K>1) does not necessarily guarantee sample-efficiency. Notably, the adaptivity-boundary for sample-efficiency is not between offline reinforcement learning (K=1), where sample-efficiency was known to not be possible, and adaptive settings. Instead, the boundary lies between different regimes of adaptivity and depends on the problem dimension.

Key facts. Cited by 2 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 31 of its 46 references that are in the map. First posted on arXiv 2 Oct 2023.

Builds on

31 of 46 references.

Closest ancestors · 3

Same direction, newest first

  1. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning15 Oct
  2. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  3. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm17 Mar

Other references · 28

  1. 2019Reinforcement Learning in Healthcare: A Surveycited by 308
  2. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  3. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  4. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  5. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  6. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  7. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  8. 2020Deployment-Efficient Reinforcement Learning via Model-Based Offline Optimizationcited by 120
  9. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  10. 2019Batched Multi-armed Bandits Problemcited by 97
  11. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  12. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
16 more
  1. 2020Sequential Batch Learning in Finite-Action Linear Contextual Banditscited by 63
  2. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  3. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  4. 2019Regret Bounds for Batched Banditscited by 49
  5. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  6. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  7. 2020A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Settingcited by 24
  8. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  9. 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
  10. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  11. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  12. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  13. 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPscited by 8
  14. 2023A General Framework for Sequential Decision-Making under Adaptivity Constraintscited by 6
  15. 2023Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practicecited by 4
  16. 2022Linear Reinforcement Learning with Ball Structure Action Spacecited by 1

Built on by

Cited by year

Citing papers per year: 2024: 2.

2 papers.

  1. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  2. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  2. 2022A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximation
  3. 2020Provably Good Batch Reinforcement Learning Without Great Exploration
  4. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  5. 2020Batch Value-function Approximation with Only Realizability
  6. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability
  7. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
  8. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison