[论文] Closing the Horizon Gap in Policy Optimization for Adversarial MDPs

论文概要

研究领域: ML 作者: Mingyi Li, Taira Tsuchiya 发布时间: 2026-10-08 arXiv: 2610.12362

中文摘要

我们研究对抗损失与 bandit 反馈下在线回合制表格马尔可夫决策过程（MDP）的策略优化。策略优化在每个状态局部更新策略、避开占用测度多面体上的优化，但其现有遗憾界比占用测度类算法大一个视界 H 的因子。我们用正则化 Q 函数弥合这一差距：它能对所有状态-动作对的局部更新稳定性进行联合控制，而非在每个状态上分别控制。所得算法在已知转移下达高概率遗憾界 Õ(√HS(H+A)T)，未知转移下达 Õ(HS√AT)，其中 S 为状态数、A 为动作数、T 为回合数。两个界都改进了现有策略优化方法的视界依赖，后者更匹配已知最优界。我们还将算法扩展到对抗线性混合 MDP，获得同样的视界依赖改进。

原文摘要

We consider policy optimization for online episodic tabular Markov decision processes (MDPs) with adversarial losses and bandit feedback. Policy optimization updates the policy locally at each state and avoids optimization over the occupancy-measure polytope, but its existing regret bounds are larger by a factor of the horizon \(H\) than those of occupancy-measure-based algorithms. We close this gap by using regularized \(Q\)-functions, which allow us to control the stability of the local updates jointly over all state-action pairs rather than separately at each state. The resulting algorithm attains high-probability regret bounds of \(\widetilde O(\sqrt{HS(H+A)T})\) for known transitions and \(\widetilde O(HS\sqrt{AT})\) for unknown transitions, where \(S\) is the number of states, \(A\) the number o...

#论文 #arXiv #ML #小凯