Improved Regret via Variance-Aware Policy Optimization in Adversarial MDPs

improved-regret-via-variance-aware-policy-optimization-in-adversarial-mdps

Improved Regret via Variance-Aware Policy Optimization in Adversarial MDPs

[Submitted on 12 Nov 2026]

View PDF HTML (experimental)

Abstract:We study episodic adversarial MDPs with unknown dynamics and full-information rewards and achieve regret with leading term $widetilde O(sqrt{H^3SAK})$. Here $H$ is the horizon, $S$ the total number of states across decision layers, $A$ the number of actions, and $K$ the number of episodes. This improves the two incomparable prior leading terms by factors $sqrt{S/H}$ and $sqrt{H^3}$, leaving a factor $sqrt H$ to the lower-bound scale. We give a reduction from unknown to known dynamics for emph{downstream-dependent} algorithms, whose policy at step $h$ is computed only from information at steps $h+1$ and onward. This reduces the remaining leading-order gap to finding a downstream-dependent known-dynamics algorithm with $widetilde O(Hsqrt K)$ regret, which would yield the tight $widetilde O(Hsqrt{SAK})$ leading term for unknown dynamics. We instantiate the reduction with VOPO, a policy optimization (PO) algorithm. Its improved guarantees follow from a variance-aware analysis enabled by a novel bonus, which we call the Stability-Matching Bonus (SMB). VOPO achieves $widetilde O(sqrt{H^3K})$ regret under known dynamics with full information; its $sqrt H$ gap to the target $Hsqrt K$ rate is inherited by our unknown-dynamics guarantee. We also show that with known dynamics and trajectory bandit feedback, VOPO achieves $widetilde O(sqrt{H^2SAK})$ regret. Both known-dynamics guarantees improve the corresponding state-of-the-art PO bounds by a factor $sqrt H$. A matching lower bound establishes that the full-information rate is tight in one parameter regime.

Submission history

From: Ofir Schlisselberg [view email]
[v1] Thu, 12 Nov 2026 19:52:56 UTC (29 KB)