Closing the Horizon Gap in Policy Optimization for Adversarial MDPs
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 Õ(√(HS(H+A)T)) for known transitions and Õ(HS√(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.
Related
- Benign Nonconvex Landscape for Policy Optimization: Infinite-Horizon Discounted MDPs with General State and Action Spaces
- One Act, Many Masks: Effect-Marginal Policy Optimization for Long-Horizon Agents
- Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs
- Embedding Information in Policy Randomness: Distribution-Preserving Implicit Communication in MDPs
- Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness
BibTeX
@misc{li2026closing,
title = {{Closing the Horizon Gap in Policy Optimization for Adversarial MDPs}},
author = {Mingyi Li and Taira Tsuchiya},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12362},
eprint = {2610.12362},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12362},
}
RIS
TY - UNPB
TI - Closing the Horizon Gap in Policy Optimization for Adversarial MDPs
AU - Mingyi Li
AU - Taira Tsuchiya
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.12362
UR - https://arxiv.org/abs/2610.12362
AB - 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 Õ(√(HS(H+A)T)) for known transitions and Õ(HS√(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.
ER -