mlsanityData to 14 Oct 2026

Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning

arXiv 2210.08238 ↗First posted 15 Oct 2022cs.LGcited by 13

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

Abstract (arXiv)

In this paper, we study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. The multi-batch reinforcement learning framework, where the agent is required to provide a time schedule to update policy before everything, which is particularly suitable for the scenarios where the agent suffers extensively from changing the policy adaptively. Given a finite-horizon MDP with S states, A actions and planning horizon H, we design a computational efficient algorithm to achieve near-optimal regret of tildeO(√SAH3Kln(1/δ))footnotetildeO(·) hides logarithmic terms of (S,A,H,K) in K episodes using Oleft(H+log2log2(K) right) batches with confidence parameter δ. To our best of knowledge, it is the first tildeO(√SAH3K) regret bound with O(H+log2log2(K)) batch complexity. Meanwhile, we show that to achieve tildeO(poly(S,A,H)√K) regret, the number of batches is at least Omegaleft(H/logA(K)+ log2log2(K) right), which matches our upper bound up to logarithmic terms. Our technical contribution are two-fold: 1) a near-optimal design scheme to explore over the unlearned states; 2) an computational efficient algorithm to explore certain directions with an approximated transition model.

Key facts. Cited by 13 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 19 of its 35 references that are in the map. First posted on arXiv 15 Oct 2022.

Builds on

19 of 35 references.

References · 19

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  4. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  5. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  6. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  7. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  8. 2019Batched Multi-armed Bandits Problemcited by 98
  9. 2017Device Placement Optimization with Reinforcement Learningcited by 86
  10. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  11. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  12. 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 61
7 more
  1. 2019Convergent Policy Optimization for Safe Reinforcement Learningcited by 57
  2. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  3. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  4. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  5. 2018Learning to Optimize Join Queries With Deep Reinforcement Learningcited by 32
  6. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  7. 2020Multinomial Logit Bandit with Low Switching Costcited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 5; 2024: 3; 2025: 3; 2026: 2.

13 papers.

Sort:

By area:

  1. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  2. 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPscited by 9
  3. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  4. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 8
  5. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  6. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 4
  7. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  8. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2
  9. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  10. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  11. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  12. 2026The Horizon Threshold in Cooperative Multi-Agent Reward-Free Explorationcited by 0
1 more
  1. 2026Optimal Multi-Reward Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  2. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
  3. 2026Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs
  4. 2026Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximation
  5. 2026Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence
  6. 2024Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism
  7. 2026Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batching
  8. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization