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, ${\sum }_{k=1}^K[V^{\ast ,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 $\tilde{O}(\sqrt{SA{H}^{3}K\log L})$ for adversarial contexts, where $L$ denotes the number of possible contexts. This result implies a regret bound of $\tilde{O}(\sqrt{SA{H}^{3}K})$ for stochastic contexts. We further translate the stochastic regret guarantee into a sample complexity bound of $\tilde{O}(SA{H}^3/{ϵ}^2)$ for a fixed context distribution. In addition, we derive a gap-dependent regret bound of $$\tilde{O}\left(\underset{p\in [0,1)}{\inf }\left(\frac{1}{{\Delta }_{\min }^p}+pK{\Delta }_{\min }^p\right)\log K\cdot \mathrm{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.