mlsanityData to 7 Oct 2026

Online Convex Optimization in Adversarial Markov Decision Processes

arXiv 1905.07773 ↗First posted 19 May 2019cs.LG cs.AI stat.MLcited by 79

Not on the map. Why?

Abstract (arXiv)

We consider online learning in episodic loop-free Markov decision processes (MDPs), where the loss function can change arbitrarily between episodes, and the transition function is not known to the learner. We show tildeO(L|X|√|A|T) regret bound, where T is the number of episodes, X is the state space, A is the action space, and L is the length of each episode. Our online algorithm is implemented using entropic regularization methodology, which allows to extend the original adversarial MDP model to handle convex performance criteria (different ways to aggregate the losses of a single episode) , as well as improve previous regret bounds.

Key facts. Cited by 79 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 19; 2022: 10; 2023: 20; 2024: 19; 2025: 8; 2026: 3.

79 papers.

Sort:

By area:

  1. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  2. 2021Reward is enough for convex MDPscited by 82
  3. 2024Multi-turn Reinforcement Learning from Preference Human Feedbackcited by 65
  4. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  5. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  6. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  7. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  8. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  9. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  10. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  11. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  12. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
38 more
  1. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  2. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  3. 2021Provable RL with Exogenous Distractors via Multistep Inverse Dynamicscited by 28
  4. 2022Performative Reinforcement Learningcited by 25
  5. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  6. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  7. 2021Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallcited by 21
  8. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
  9. 2022Online Policy Optimization for Robust MDPcited by 19
  10. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  11. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 18
  12. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  13. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  14. 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 16
  15. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  16. 2023A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPscited by 15
  17. 2024Learning Adversarial MDPs with Stochastic Hard Constraintscited by 15
  18. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
  19. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  20. 2022Socially Fair Reinforcement Learningcited by 13
  21. 2024Performative Reinforcement Learning in Gradually Shifting Environmentscited by 13
  22. 2021Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximationcited by 11
  23. 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimizationcited by 11
  24. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
  25. 2023Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximationcited by 9
  26. 2023A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraintscited by 9
  27. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  28. 2024Markov Persuasion Processes: Learning to Persuade from Scratchcited by 8
  29. 2024Uncertainty-based Offline Variational Bayesian Reinforcement Learning for Robustness under Diverse Data Corruptionscited by 8
  30. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  31. 2023Efficient Model-Based Concave Utility Reinforcement Learning through Greedy Mirror Descentcited by 6
  32. 2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncited by 6
  33. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 5
  34. 2023Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescited by 5
  35. 2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraintscited by 5
  36. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  37. 2024Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPscited by 5
  38. 2022Cooperative Online Learning in Stochastic and Adversarial MDPscited by 4

50 most cited of 79 All 79 (JSON)