mlsanityData to 14 Oct 2026

Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning

arXiv 2605.15692 ↗First posted 15 May 2026cs.LG stat.MLcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We study episodic reinforcement learning with fixed reward and transition functions, but with episode-dependent admissible action sets that are observed at the start of each episode. Performance is measured by cumulative regret against the episode-wise optimal value, sumk=1K [V*,Mk - Vπk,Mk], where Mk represents the action context in the k-th episode. We show that the MVP algorithm naturally extends to this framework and enjoys strong theoretical guarantees. In particular, we establish a minimax regret bound of widetildeO(√SAH3Klog L) for adversarial contexts, where L denotes the number of possible contexts. This result implies a regret bound of widetildeO(√SAH3K) for stochastic contexts. We further translate the stochastic regret guarantee into a sample complexity bound of widetildeO(SAH3/ε2) for a fixed context distribution. In addition, we derive a gap-dependent regret bound of [ widetilde Oleft( infp∈ [0,1) left( frac1Deltaminp + pKDeltaminp right)log K · poly(S,A,H) right), ] where Deltaminp is the global p-trimmed positive-gap floor over suboptimal (h,s,a) triples. This bound can substantially improve upon the minimax rate when the relevant suboptimality gaps are large.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 26 of its 47 references that are in the map. First posted on arXiv 15 May 2026.

Builds on

26 of 47 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Sample Complexity Characterization for Linear Contextual MDPs5 Feb

Other references · 25

  1. 2018Is Q-learning Provably Efficient?cited by 487
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  3. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 201
  4. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  5. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  6. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  7. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 66
  8. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 55
  9. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  10. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 52
  11. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 49
  12. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 46
13 more
  1. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 39
  2. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 35
  3. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 29
  4. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 19
  5. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 18
  6. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 16
  7. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 15
  8. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 11
  9. 2024Linear Contextual Bandits with Interferencecited by 8
  10. 2025Contextual Linear Bandits with Delay as Payoffcited by 7
  11. 2024Strategic Linear Contextual Banditscited by 5
  12. 2024Federated Linear Contextual Bandits with Heterogeneous Clientscited by 4
  13. 2026Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximationcited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism
  2. 2026Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints
  3. 2026Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence
  4. 2026Unified Framework of Distributional Regret in Multi-Armed Bandits and Reinforcement Learning
  5. 2025Reinforcement Learning from Adversarial Preferences in Tabular MDPs
  6. 2026Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferences
  7. 2026Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximation
  8. 2024Optimistic Q-learning for average reward and episodic reinforcement learning