mlsanityData to 14 Oct 2026

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

arXiv 1303.3055 ↗First posted 12 Mar 2013cs.LG stat.MLcited by 18

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 1; 2021: 5; 2022: 3; 2023: 3; 2024: 4; 2025: 1; 2026: 1.

18 papers.

Sort:

By area:

  1. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  2. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  3. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  4. 2020Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learningcited by 15
  5. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptionscited by 15
  6. 2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
  7. 2024Performative Reinforcement Learning in Gradually Shifting Environmentscited by 14
  8. 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
  9. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  10. 2021Online Markov Decision Processes with Aggregate Bandit Feedbackcited by 10
  11. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 10
  12. 2022Learning Correlated Equilibria in Mean-Field Gamescited by 6
6 more
  1. 2025Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learningcited by 4
  2. 2023Online Nonstochastic Model-Free Reinforcement Learningcited by 2
  3. 2024Time-Constrained Robust MDPscited by 2
  4. 2023Online Resource Allocation in Episodic Markov Decision Processescited by 1
  5. 2022Learning in Multi-Player Stochastic Gamescited by 0
  6. 2026Local and Global Stability in Performative Reinforcement Learningcited by 0