Improved Regret via Variance-Aware Policy Optimization in Adversarial MDPs
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 . Here is the horizon, the total number of states across decision layers, the number of actions, and the number of episodes. This improves the two incomparable prior leading terms by factors and , leaving a factor to the lower-bound scale. We give a reduction from unknown to known dynamics for downstream-dependent algorithms, whose policy at step is computed only from information at steps and onward. This reduces the remaining leading-order gap to finding a downstream-dependent known-dynamics algorithm with regret, which would yield the tight 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 regret under known dynamics with full information; its gap to the target rate is inherited by our unknown-dynamics guarantee. We also show that with known dynamics and trajectory bandit feedback, VOPO achieves regret. Both known-dynamics guarantees improve the corresponding state-of-the-art PO bounds by a factor . A matching lower bound establishes that the full-information rate is tight in one parameter regime.
Figures & tables
| Result | Leading -dependent term |
|---|---|
| Rosenberg and Mansour (2019a) | |
| Tiapkin et al. (2024) | |
| This work | |
| Standard lower-bound scale Domingues et al. (2021) |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Regret Minimization in RL
Regret minimization in reinforcement learning develops agents that learn effective policies while limiting cumulative loss against an optimal benchmark.
See all 70 papers