# Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2013.

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

- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Robust Policy Gradient against Strong Data Corruption](https://mlsanity.com/paper/2102.05800/) (2021)
- [Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits](https://mlsanity.com/paper/2203.06803/) (2022)
- [Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learning](https://mlsanity.com/paper/2006.16785/) (2020)
- [Imitation Learning in Discounted Linear MDPs without exploration assumptions](https://mlsanity.com/paper/2405.02181/) (2024)
- [Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure](https://mlsanity.com/paper/2111.00781/) (2021)
- [Performative Reinforcement Learning in Gradually Shifting Environments](https://mlsanity.com/paper/2402.09838/) (2024)
- [Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations](https://mlsanity.com/paper/2106.11519/) (2021)
- [Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruption](https://mlsanity.com/paper/2402.08991/) (2024)
- [Online Markov Decision Processes with Aggregate Bandit Feedback](https://mlsanity.com/paper/2102.00490/) (2021)
- [Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games](https://mlsanity.com/paper/2303.12287/) (2023)
- [Learning Correlated Equilibria in Mean-Field Games](https://mlsanity.com/paper/2208.10138/) (2022)
- [Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning](https://mlsanity.com/paper/2505.17610/) (2025)
- [Online Nonstochastic Model-Free Reinforcement Learning](https://mlsanity.com/paper/2305.17552/) (2023)
- [Time-Constrained Robust MDPs](https://mlsanity.com/paper/2406.08395/) (2024)
- [Online Resource Allocation in Episodic Markov Decision Processes](https://mlsanity.com/paper/2305.10744/) (2023)
- [Learning in Multi-Player Stochastic Games](https://mlsanity.com/paper/2210.14280/) (2022)
- [Local and Global Stability in Performative Reinforcement Learning](https://mlsanity.com/paper/2609.06467/) (2026)

## Abstract (arXiv)

We study the problem of learning Markov decision processes with finite state and action spaces when the transition probability distributions and loss functions are chosen adversarially and are allowed to change with time. We introduce an algorithm whose regret with respect to any policy in a comparison class grows as the square root of the number of rounds of the game, provided the transition probabilities satisfy a uniform mixing condition. Our approach is efficient as long as the comparison class is polynomial and we can compute expectations over sample paths for each policy. Designing an efficient algorithm with small regret for the general case remains an open problem.