cs.LGNov 12, 2026

Improved Regret via Variance-Aware Policy Optimization in Adversarial MDPs

Authors: Ofir Schlisselberg, Alon Cohen, Yishay Mansour

Organizations: Tel Aviv University · Tel Aviv University and Google Research

Abstract

We study episodic adversarial MDPs with unknown dynamics and full-information rewards and achieve regret with leading term O~(H3SAK)\widetilde O(\sqrt{H^3SAK}). Here HH is the horizon, SS the total number of states across decision layers, AA the number of actions, and KK the number of episodes. This improves the two incomparable prior leading terms by factors S/H\sqrt{S/H} and H3\sqrt{H^3}, leaving a factor H\sqrt H to the lower-bound scale. We give a reduction from unknown to known dynamics for downstream-dependent algorithms, whose policy at step hh is computed only from information at steps h+1h+1 and onward. This reduces the remaining leading-order gap to finding a downstream-dependent known-dynamics algorithm with O~(HK)\widetilde O(H\sqrt K) regret, which would yield the tight O~(HSAK)\widetilde O(H\sqrt{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 O~(H3K)\widetilde O(\sqrt{H^3K}) regret under known dynamics with full information; its H\sqrt H gap to the target HKH\sqrt K rate is inherited by our unknown-dynamics guarantee. We also show that with known dynamics and trajectory bandit feedback, VOPO achieves O~(H2SAK)\widetilde O(\sqrt{H^2SAK}) regret. Both known-dynamics guarantees improve the corresponding state-of-the-art PO bounds by a factor H\sqrt H. A matching lower bound establishes that the full-information rate is tight in one parameter regime.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Closing the Horizon Gap in Policy Optimization for Adversarial MDPs

    Oct 8, 2026Mingyi Li, Taira TsuchiyaRegret Minimization in RLMarkov Decision Processes

  2. Data- and Variance-dependent Regret Bounds for Online Tabular MDPs

    Feb 2, 2026Mingyi Li, Taira Tsuchiya, Kenji YamanishiRegret Minimization in RLMarkov Decision Processes

  3. Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal S\sqrt S and K\sqrt K Dependencies in Tabular and Linear AMDPs

    Nov 12, 2026Aarush Kulkarni, Khang Nguyen, William Chang +1Regret Minimization in RLMarkov Decision Processes