新算法在动态动作集下实现更优的强化学习理论保证。
Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning
- 提出MVP算法扩展框架，处理每轮不同可用动作集。
- 最坏情况后悔上界为√(SAH³K log L)，随机上下文时为√(SAH³K)。
- 首次给出基于子最优间隙的改进后悔界，适合间隙大的场景。
研究具有固定奖励与转移函数的周期性强化学习，每轮开始前观察到依赖于该轮的可行动作集。性能以累积后悔衡量：∑_{k=1}^K [V^{*,M^k} - V^{π^k,M^k}]，其中M^k表示第k轮的动作上下文。我们证明MVP算法可自然扩展至该框架，并具备强理论保障。具体地，在对抗性上下文中，最小最大后悔界为˜O(√(SAH³K log L))，L为可能上下文数；在随机上下文中，该界退化为˜O(√(SAH³K))。进一步将随机后悔界转化为固定上下文分布下的样本复杂度˜O(SAH³/ε²)。此外，我们推导出一个依赖间隙的后悔界：˜O( inf_{p∈[0,1)} (1/Δ_min^p + pKΔ_min^p) log K · poly(S,A,H) )，其中Δ_min^p为全局p-截断正间隙下界。当相关子最优间隙较大时，该界显著优于最小最大率。
原文摘要 · Abstract (English)
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^{π^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^3K\log 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/ε^2)$ for a fixed context distribution. In addition, we derive a gap-dependent regret bound of \[ \widetilde O\left( \inf_{p\in [0,1)} \left( \frac{1}{Δ_{\min}^{p}} + pKΔ_{\min}^{p} \right)\log K \cdot \mathrm{poly}(S,A,H) \right), \] 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。