betaFeedback

WorksComputer Science

Improved Regret via Variance-Aware Policy Optimization in Adversarial MDPs

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.

Paper details

vlnc:W_tzbrpg2f
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…