arXiv：cs.LG· Mingyi Li, Taira Tsuchiya·· 3 小时前
对抗性 MDP 策略优化中的 horizon 差距被补齐
Closing the Horizon Gap in Policy Optimization for Adversarial MDPs
AI 导读
研究者针对带对抗性损失和 bandit 反馈的在线回合制表格 MDP，用正则化 Q 函数实现策略优化，将已知转移下的遗憾界改进为 Õ(√HS(H+A)T)、未知转移下为 Õ(HS√AT)，消除了既有策略优化界相对占用度量算法多出的 H 因子，后者已匹配已知最优界。该方法还扩展到对抗性线性混合 MDP 并取得相同的 horizon 依赖改进。
正文
Abstract: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 of actions, and $T$ the number of episodes. Both bounds improve the horizon dependence of existing policy optimization bounds, and the latter matches the best-known bound. We further extend the algorithm to adversarial linear-mixture MDPs and obtain the same improvement in the horizon dependence.
| Comments: | 17 pages, 2 tables |
| Subjects: | Machine Learning (cs.LG); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.12362 [cs.LG] |
| (or arXiv:2610.12362v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.12362 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Mingyi Li [view email]
[v1]
Thu, 8 Oct 2026 17:26:55 UTC (18 KB)
来源：arXiv：cs.LG · arxiv.org