AIIC AI Intelligence Centre

SOURCE-LINKED INTELLIGENCE

Closing the Horizon Gap in Policy Optimization for Adversarial MDPs

arXiv · AI, language, vision and robotics · article · Oct 8, 2026 · UTC

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 atta

Read original source ↗ Open in workspace

recordType
paper
region
Global

Evidence & attribution

First collected: 2026-10-09T08:21:58.456Z. This is not the publication date.