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

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

## Key facts

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

## Placed in

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

## Builds on (most cited first, 30 of 31)

- [Reinforcement Learning in Healthcare: A Survey](https://mlsanity.com/paper/1908.08796/) (2019)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [Deployment-Efficient Reinforcement Learning via Model-Based Offline Optimization](https://mlsanity.com/paper/2006.03647/) (2020)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Provably Efficient Q-Learning with Low Switching Cost](https://mlsanity.com/paper/1905.12849/) (2019)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)
- [Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL](https://mlsanity.com/paper/2012.08005/) (2020)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost](https://mlsanity.com/paper/2101.00494/) (2021)
- [Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost](https://mlsanity.com/paper/2202.06385/) (2022)
- [A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting](https://mlsanity.com/paper/2011.01075/) (2020)
- [Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimality](https://mlsanity.com/paper/2202.06450/) (2022)
- [On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function](https://mlsanity.com/paper/2102.02049/) (2021)
- [When is Realizability Sufficient for Off-Policy Reinforcement Learning?](https://mlsanity.com/paper/2211.05311/) (2022)
- [Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2210.00701/) (2022)
- [Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning](https://mlsanity.com/paper/2210.08238/) (2022)
- [Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data](https://mlsanity.com/paper/2307.04354/) (2023)
- [Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm](https://mlsanity.com/paper/2103.09847/) (2021)
- [Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPs](https://mlsanity.com/paper/2302.12456/) (2023)
- [A General Framework for Sequential Decision-Making under Adaptivity Constraints](https://mlsanity.com/paper/2306.14468/) (2023)
- [Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice](https://mlsanity.com/paper/2305.13185/) (2023)

## Built on by (most cited first, 2 of 2)

- [Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints](https://mlsanity.com/paper/2402.01111/) (2024)
- [Near-Optimal Reinforcement Learning with Shuffle Differential Privacy](https://mlsanity.com/paper/2411.11647/) (2024)

## 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.