# Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization

arXiv: https://arxiv.org/abs/2407.05704 · HTML: https://mlsanity.com/paper/2407.05704/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 51 references that are in the map.
- First posted on arXiv 8 Jul 2024.

## Builds on (most cited first, 28 of 28)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon](https://mlsanity.com/paper/2009.13503/) (2020)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Online Convex Optimization in Adversarial Markov Decision Processes](https://mlsanity.com/paper/1905.07773/) (2019)
- [Optimistic Policy Optimization with Bandit Feedback](https://mlsanity.com/paper/2002.08243/) (2020)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Worst-Case Regret Bounds for Exploration via Randomized Value Functions](https://mlsanity.com/paper/1906.02870/) (2019)
- [Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation](https://mlsanity.com/paper/2103.12923/) (2021)
- [Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses](https://mlsanity.com/paper/2107.08346/) (2021)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition](https://mlsanity.com/paper/2106.04117/) (2021)
- [Learning Adversarial Markov Decision Processes with Delayed Feedback](https://mlsanity.com/paper/2012.14843/) (2020)
- [Scale-Free Algorithms for Online Linear Optimization](https://mlsanity.com/paper/1502.05744/) (2015)
- [A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes](https://mlsanity.com/paper/2305.08841/) (2023)
- [Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2102.08940/) (2021)
- [KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints](https://mlsanity.com/paper/1805.05071/) (2018)
- [Rate-Optimal Policy Optimization for Linear Markov Decision Processes](https://mlsanity.com/paper/2308.14642/) (2023)
- [Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback](https://mlsanity.com/paper/2310.11550/) (2023)
- [Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processes](https://mlsanity.com/paper/2407.03065/) (2024)
- [Policy Optimization via Adv2: Adversarial Learning on Advantage Functions](https://mlsanity.com/paper/2310.16473/) (2023)

## Abstract (arXiv)

We consider the problem of learning in adversarial Markov decision processes [MDPs] with an oblivious adversary in a full-information setting. The agent interacts with an environment during T episodes, each of which consists of H stages, and each episode is evaluated with respect to a reward function that will be revealed only at the end of the episode. We propose an algorithm, called APO-MVP, that achieves a regret bound of order tildeO(poly(H)√SAT), where S and A are sizes of the state and action spaces, respectively. This result improves upon the best-known regret bound by a factor of √S, bridging the gap between adversarial and stochastic MDPs, and matching the minimax lower bound Omega(√H3SAT) as far as the dependencies in S,A,T are concerned. The proposed algorithm and analysis completely avoid the typical tool given by occupancy measures; instead, it performs policy optimization based only on dynamic programming and on a black-box online linear optimization strategy run over estimated advantage functions, making it easy to implement. The analysis leverages two recent techniques: policy optimization based on online linear optimization strategies (Jonckheere et al., 2023) and a refined martingale analysis of the impact on values of estimating transitions kernels (Zhang et al., 2023).