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

Oct 8, 2026

Closing the Horizon Gap in Policy Optimization for Adversarial MDPs

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 HH than those of occupancy-measure-based algorithms. We close this gap by using regularized QQ-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 O~(HS(H+A)T)\widetilde O(\sqrt{HS(H+A)T}) for known transitions and O~(HSAT)\widetilde O(HS\sqrt{AT}) for unknown transitions, where SS is the number of states, AA the number of actions, and TT 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.
Feb 2, 2026

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

This work studies online episodic tabular Markov decision processes (MDPs) with known transitions and develops best-of-both-worlds algorithms that achieve refined data-dependent regret bounds in the adversarial regime and variance-dependent regret bounds in the stochastic regime. We quantify MDP complexity using a first-order quantity and several new data-dependent measures for the adversarial regime, including a second-order quantity and a path-length measure, as well as variance-based measures for the stochastic regime. To adapt to these measures, we develop algorithms based on global optimization and policy optimization, both built on optimistic follow-the-regularized-leader with log-barrier regularization. For global optimization, our algorithms achieve first-order, second-order, and path-length regret bounds in the adversarial regime, and in the stochastic regime, they achieve a variance-aware gap-independent bound and a variance-aware gap-dependent bound that is polylogarithmic in the number of episodes. For policy optimization, our algorithms achieve the same data- and variance-dependent adaptivity, up to a factor of the episode horizon, by exploiting a new optimistic QQ-function estimator. Finally, we establish regret lower bounds in terms of data-dependent complexity measures for the adversarial regime and a variance measure for the stochastic regime, implying that the regret upper bounds achieved by the global-optimization approach are nearly optimal.
Nov 12, 2026

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

We study regret minimization in episodic Adversarial Markov Decision Processes (AMDPs) with unknown transitions and bandit feedback. In tabular AMDPs with SS states, AA actions, and horizon HH, the best known KK-episode regret is O~(HSAK)\tilde O(HS\sqrt{AK}), whose S\sqrt S gap to the Ω(HSAK)Ω(H\sqrt{SAK}) lower bound has long remained open. In linear AMDPs with dd-dimensional features, after a five-year line of improvements starting from K14/15K^{14/15}, computationally efficient algorithms without a simulator or exploratory assumptions still only attain O~(K3/4)\tilde O(K^{3/4}) regret. A common challenge in both settings is to estimate the Q-function of a changing policy: past data comes from earlier policies that differ from (and are correlated with) the current one, while freezing the policy for future episodes worsens the dependency on KK. We instead propose a general technique called introduced feedback delays: we estimate the Q-function of the policy using future episodes while still updating the policy, as if the feedback were delayed. While feedback delays are usually an obstacle imposed by the environment, here they are introduced voluntarily and, perhaps surprisingly, come at no extra cost. We develop Geometric Resampling with Rejection (GRR) to account for policy changes during the delay, and threshold the visitation probabilities to avoid long delays on rarely visited state-action pairs. With this unified technique, our policy optimization algorithms achieve, with high probability, O~(poly(H)SAK)\tilde O(\text{poly}(H)\sqrt{SAK}) regret in tabular AMDPs, resolving the open problem; and O~(poly(d,H)K)\tilde O(\text{poly}(d,H)\sqrt K) regret in linear AMDPs, giving the first efficient algorithm optimal in KK. They also naturally extend to delayed AMDPs with a total feedback delay D\mathfrak D, yielding the first bounds optimal in SS and D\mathfrak D (tabular) and in KK and D\mathfrak D (linear).