mlsanityData to 7 Oct 2026

Online Policy Optimization for Robust MDP

arXiv 2209.13841 ↗First posted 28 Sep 2022cs.LG stat.MLcited by 19

Not on the map. Why?

Abstract (arXiv)

Reinforcement learning (RL) has exceeded human performance in many synthetic settings such as video games and Go. However, real-world deployment of end-to-end RL models is less common, as RL models can be very sensitive to slight perturbation of the environment. The robust Markov decision process (MDP) framework -- in which the transition probabilities belong to an uncertainty set around a nominal model -- provides one way to develop robust models. While previous analysis shows RL algorithms are effective assuming access to a generative model, it remains unclear whether RL can be efficient under a more realistic online setting, which requires a careful balance between exploration and exploitation. In this work, we consider online robust MDP by interacting with an unknown nominal system. We propose a robust optimistic policy optimization algorithm that is provably efficient. To address the additional uncertainty caused by an adversarial environment, our model features a new optimistic update rule derived via Fenchel conjugates. Our analysis establishes the first regret bound for online robust MDPs.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). Builds on 25 of its 42 references that are in the map. First posted on arXiv 28 Sep 2022.

Builds on

25 of 42 references.

References · 25

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2018Quantifying Generalization in Reinforcement Learningcited by 345
  4. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  5. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  6. 2018Assessing Generalization in Deep Reinforcement Learningcited by 132
  7. 2018Generalization and Regularization in DQNcited by 117
  8. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  9. 2019Observational Overfitting in Reinforcement Learningcited by 90
  10. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  11. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
  12. 2021Decoupling Value and Policy for Generalization in Reinforcement Learningcited by 81
13 more
  1. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  2. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  3. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  4. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 67
  5. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  6. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  7. 2022Doubly Robust Distributionally Robust Off-Policy Evaluation and Learningcited by 34
  8. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
  9. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  10. 2021Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptoticscited by 27
  11. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
  12. 2021Nearly Optimal Policy Optimization with Stable at Any Time Guaranteecited by 13
  13. 2020Robust Batch Policy Learning in Markov Decision Processescited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 8; 2025: 4; 2026: 3.

19 papers.

Sort:

By area:

  1. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  2. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  3. 2023Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlationcited by 25
  4. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
  5. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  6. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  7. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 17
  8. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 15
  9. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 12
  10. 2025Hybrid Cross-domain Robust Reinforcement Learningcited by 3
  11. 2025Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learningcited by 2
  12. 2024The Fallacy of Minimizing Cumulative Regret in the Sequential Task Settingcited by 1
7 more
  1. 2025Online Bayesian Risk-Averse Reinforcement Learningcited by 1
  2. 2025Online Robust Reinforcement Learning with General Function Approximationcited by 1
  3. 2026Online Robust Reinforcement Learning Through Monte-Carlo Planningcited by 1
  4. 2023Solving Robust MDPs through No-Regret Dynamicscited by 0
  5. 2024Robust Offline Reinforcement Learning for Non-Markovian Decision Processescited by 0
  6. 2026Distributionally Robust Cooperative Multi-Agent Reinforcement Learning via Robust Value Factorizationcited by 0
  7. 2026Evolving Robustness--Exploration Trade-off in Online Reinforcement Learning via Quantile Bayesian Risk MDPscited by 0