arXiv:2607.19854cs.LGstat.ML2026-07

提出首个无需依赖时域长度的最优强化学习算法,突破了以往对时间步数的依赖瓶颈。

Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence

  • 利用值函数单调性与网格投影,避免传统方法中随时间步数增长的误差累积。
  • 实现渐近最优的置信区间上界 $ ilde O( oot\sim\of{SAK}+S^8A^3)$,不依赖 $H$。
  • 适用于需高效探索的有限时域马尔可夫决策过程,尤其适合长时序任务场景。

研究有限时域、时齐的表格型马尔可夫决策过程中的无时域依赖后悔率最小化问题,状态数为 $S$,动作数为 $A$,时域长度为 $H$,每条轨迹总奖励上限为 1。本文提出一种新算法,并证明其后悔上界为 $ ilde O( oot\sim\of{SAK}+S^8A^3)$,失败概率为 $δ$,其中 $K$ 为剧集数,$ ilde O(ullet)$ 隐含 $ ext{poly} ext{log}(S,A,K,1/δ)$ 因子。该结果实现 $H$-自由且渐近最优,与上下文无关老虎机的下界 $Ω( oot\sim\of{SAK})$ 仅差对数因子。相比此前 $O( oot\sim\of{SAK ext{log}H}+S^2A ext{log}H)$ 的结果,完全消除 $ ext{log} H$ 依赖;并大幅改进先前最好水平的 $ ilde O( oot\sim\of{S^9A^3K})$。主要技术难点在于:尽管转移核时齐,但最优值函数 $\\{V_h^*\ brace_{h=1}^H$ 仍为时异。直接对所有值函数做并集界通常引入额外 $ ext{min}\{ ext{log} H,S\}$ 因子。本文通过(i)利用 $V_h^*$ 相对于 $h$ 的单调性,(ii)非平凡地将值函数投影至 $S$ 维网格,避免该因子。分析还依赖三项关键设计:第一,引入时域截断论证,支持基于奖励的探索,无需独立奖励无关探索阶段;第二,设计剪切奖励项,同时保持乐观性与规划所需的单调性;第三,建立新的时齐 MDP 总偏差界,以可控多项式依赖 $S,A$ 控制剪切奖励中的裁剪方差项,且不依赖 $H$。这些工具协同实现渐近最优的 $H$-自由后悔保证。

原文摘要 · Abstract (English)

We study horizon-free regret minimization for finite-horizon time-homogeneous tabular Markov decision processes with $S$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$. We propose a new algorithm and prove a regret upper bound \[\tilde O(\sqrt{SAK}+S^8A^3)\] with failure probability $δ$, where $K$ is the number of episodes and $\tilde O(\cdot)$ hides $\mathsf{poly}\log(S,A,K,1/δ)$. Thus, the regret is $H$-free and asymptotically optimal, matching the contextual-bandit lower bound $Ω(\sqrt{SAK})$ up to logarithmic factors. This completely removes the $\log H$ dependence from the previous $\tilde O(\sqrt{SAK\log H}+S^2A\log H)$ guarantee of Zhang et al. (2021), and drastically improves the prior best horizon-free regret $\tilde O(\sqrt{S^9A^3K})$ of Zhang et al. (2022) asymptotically. The main technical difficulty is that the optimal value functions $\{V_h^*\}_{h=1}^H$ are time-inhomogeneous even though the transition kernel is time-homogeneous. A direct union bound over all value functions typically incurs an additional $\min\{\log H,S\}$ factor. We avoid this factor by (i) exploiting the monotonicity of $V_h^*$ in $h$ and (ii) non-trivially projecting the value functions onto an $S$-dimensional grid. Our analysis relies on three additional ingredients. First, we introduce a horizon-truncation argument that enables reward-based exploration and removes the cost of a separate reward-free exploration phase. Second, we design a cutting bonus that preserves both optimism and the monotonicity needed for planning. Third, we prove a new bound on total deviation for time-homogeneous MDPs, which controls the clipped variance terms in the cutting bonus with adjustable polynomial dependence on $S$ and without any dependence on $H$. Together, these tools yield an asymptotically optimal horizon-free regret guarantee.

强化学习后悔率最优性时齐MDP

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。