Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning

arXiv:2605.15692v1 Announce Type: new 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, sum_{k=1}^K [V^{*,M^k} - V^{pi^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 widetilde{O}(sqrt{SAH^3Klog L}) for adversarial contexts, where L denotes the number of possible contexts. This result implies a regret bound of widetilde{O}(sqrt{SAH^3K}) for stochastic contexts. We further translate the stochastic regret guarantee into a sample complexity bound of widetilde{O}(SAH^3/epsilon^2) for a fixed context distribution. In addition, we derive a gap-dependent regret bound of [ widetilde Oleft( inf_{pin [0,1)} left( frac{1}{Delta_{min}^{p}} + pKDelta_{min}^{p} right)log K dot poly(S,A,H) right), ] where Delta_{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.

Source: arXiv cs.LG | 2026-05-18