Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning

Abstract

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, ∑_k=1^K [V^{*,M^k} − V^{π^k,M^k}], where M^k 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 Õ(√(SAH³Klog L)) for adversarial contexts, where L denotes the number of possible contexts. This result implies a regret bound of Õ(√(SAH³K)) for stochastic contexts. We further translate the stochastic regret guarantee into a sample complexity bound of Õ(SAH³/ε²) for a fixed context distribution. In addition, we derive a gap-dependent regret bound of Õ( inf_{p∈ [0,1)} ( 1/Δ_min^p + pKΔ_min^p )log K · poly(S,A,H) ), where Δ_min^p 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.

Frequency-Uniform Log-Regret Reinforcement Learning for Diffusions
Jose Blanchet, Lutong Hao, Renyuan Xu
arXiv27 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Minimax Regret for Sobolev Kernel-Based Reinforcement Learning
Haichen Hu, David Simchi-Levi
arXiv25 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
Online Autotuning of Algebraic Multigrid via Contextual Bandits and Reinforcement Learning
Xudong He, Ruiyu Wang, Yilang Ding +2
arXiv1 Nov 2026PreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
Sharp Regret Bounds and a Task-Covariance Correction for Spectral Representation Learning
Dier Tang, Jing Yee Tan, Guangyue Han
arXiv26 Sep 2026PreprintarXiv licenceFull textStatisticsarXiv
Minimax PAC Bounds for Learning in Exogenous Contextual MDPs
Corentin Pla, Hugo Richard, Marc Abeille +1
arXiv25 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{chen2026tighter,
  title = {{Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning}},
  author = {Zijun Chen and Zihan Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2605.15692},
  eprint = {2605.15692},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.15692},
}

RIS

TY  - UNPB
TI  - Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning
AU  - Zijun Chen
AU  - Zihan Zhang
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2605.15692
UR  - https://arxiv.org/abs/2605.15692
AB  - 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, ∑_k=1^K [V^*,M^k − V^π^k,M^k], where M^k 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 Õ(√(SAH^3Klog L)) for adversarial contexts, where L denotes the number of possible contexts. This result implies a regret bound of Õ(√(SAH^3K)) for stochastic contexts. We further translate the stochastic regret guarantee into a sample complexity bound of Õ(SAH^3/ε^2) for a fixed context distribution. In addition, we derive a gap-dependent regret bound of Õ( inf_p∈ [0,1) ( 1/Δ_min^p + pKΔ_min^p )log K · poly(S,A,H) ), where Δ_min^p 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.
ER  -

Abstract

Related

Cite