# Closing the Horizon Gap in Policy Optimization for Adversarial MDPs

arXiv: https://arxiv.org/abs/2610.12362 · HTML: https://mlsanity.com/paper/2610.12362/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 31 references that are in the map.
- First posted on arXiv 8 Oct 2026.

## Builds on (most cited first, 4 of 4)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Reinforcement Learning from Adversarial Preferences in Tabular MDPs](https://mlsanity.com/paper/2507.11706/) (2025)
- [Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions](https://mlsanity.com/paper/2606.31769/) (2026)

## Abstract (arXiv)

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(√HS(H+A)T) for known transitions and widetilde O(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.