# Online Markov Decision Processes with Non-oblivious Strategic Adversary

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 46 references that are in the map.
- First posted on arXiv 7 Oct 2021.

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

- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)
- [Real World Games Look Like Spinning Tops](https://mlsanity.com/paper/2004.09468/) (2020)
- [Modelling Behavioural Diversity for Learning in Open-Ended Games](https://mlsanity.com/paper/2103.07927/) (2021)
- [Online learning in MDPs with linear function approximation and bandit feedback](https://mlsanity.com/paper/2007.01612/) (2020)
- [Diverse Auto-Curriculum is Critical for Successful Real-World Multiagent Learning Systems](https://mlsanity.com/paper/2102.07659/) (2021)
- [On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games](https://mlsanity.com/paper/2109.01795/) (2021)
- [Online Double Oracle](https://mlsanity.com/paper/2103.07780/) (2021)
- [Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games](https://mlsanity.com/paper/2106.04958/) (2021)

## Built on by (most cited first, 3 of 3)

- [Robust Multi-Agent Reinforcement Learning by Mutual Information Regularization](https://mlsanity.com/paper/2310.09833/) (2023)
- [Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms](https://mlsanity.com/paper/2411.00707/) (2024)
- [Vulnerable Agent Identification in Large-Scale Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2509.15103/) (2025)

## Abstract (arXiv)

We study a novel setting in Online Markov Decision Processes (OMDPs) where the loss function is chosen by a non-oblivious strategic adversary who follows a no-external regret algorithm. In this setting, we first demonstrate that MDP-Expert, an existing algorithm that works well with oblivious adversaries can still apply and achieve a policy regret bound of O(√T log(L)+τ2√ T log(|A|)) where L is the size of adversary's pure strategy set and |A| denotes the size of agent's action space. Considering real-world games where the support size of a NE is small, we further propose a new algorithm: MDP-Online Oracle Expert (MDP-OOE), that achieves a policy regret bound of O(√Tlog(L)+τ2√ T k log(k)) where k depends only on the support size of the NE. MDP-OOE leverages the key benefit of Double Oracle in game theory and thus can solve games with prohibitively large action space. Finally, to better understand the learning dynamics of no-regret methods, under the same setting of no-external regret adversary in OMDPs, we introduce an algorithm that achieves last-round convergence result to a NE. To our best knowledge, this is first work leading to the last iteration result in OMDPs.