mlsanityData to 7 Oct 2026

Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses

arXiv 2107.08346 ↗First posted 18 Jul 2021cs.LG stat.MLcited by 51

Not on the map. Why?

Abstract (arXiv)

Policy optimization is a widely-used method in reinforcement learning. Due to its local-search nature, however, theoretical guarantees on global optimality often rely on extra assumptions on the Markov Decision Processes (MDPs) that bypass the challenge of global exploration. To eliminate the need of such assumptions, in this work, we develop a general solution that adds dilated bonuses to the policy update to facilitate global exploration. To showcase the power and generality of this technique, we apply it to several episodic MDP settings with adversarial losses and bandit feedback, improving and generalizing the state-of-the-art. Specifically, in the tabular case, we obtain widetildeO(√T) regret where T is the number of episodes, improving the widetildeO(T2/3) regret bound by Shani et al. (2020). When the number of states is infinite, under the assumption that the state-action values are linear in some low-dimensional features, we obtain widetildeO(T2/3) regret with the help of a simulator, matching the result of Neu and Olkhovskaya (2020) while importantly removing the need of an exploratory policy that their algorithm requires. When a simulator is unavailable, we further consider a linear MDP setting and obtain widetildeO(T14/15) regret, which is the first result for linear MDPs with adversarial losses and bandit feedback.

Key facts. Cited by 51 papers in the map (data through 7 Oct 2026). Builds on 26 of its 39 references that are in the map. First posted on arXiv 18 Jul 2021.

Builds on

26 of 39 references.

References · 26

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  6. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  7. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  8. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
  9. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  10. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  11. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  12. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
14 more
  1. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  2. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  3. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  4. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  5. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  6. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  7. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  8. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  9. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
  10. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  11. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 29
  12. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  13. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  14. 2021Improved Regret Bound and Experience Replay in Regularized Policy Iterationcited by 18

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 6; 2023: 15; 2024: 13; 2025: 7; 2026: 8.

51 papers.

Sort:

By area:

  1. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  2. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  3. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  4. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  5. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  6. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  7. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 18
  8. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  9. 2023Best of Both Worlds Policy Optimizationcited by 17
  10. 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 16
  11. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  12. 2023A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPscited by 15
38 more
  1. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptionscited by 15
  2. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
  3. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  4. 2021Nearly Optimal Policy Optimization with Stable at Any Time Guaranteecited by 13
  5. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
  6. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  7. 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimizationcited by 11
  8. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
  9. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  10. 2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncited by 6
  11. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  12. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraintscited by 5
  13. 2022Cooperative Online Learning in Stochastic and Adversarial MDPscited by 4
  14. 2023Near-Optimal Adversarial Reinforcement Learning with Switching Costscited by 4
  15. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4
  16. 2023Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraintscited by 4
  17. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  18. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  19. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
  20. 2025Decision Making in Hybrid Environments: A Model Aggregation Approachcited by 3
  21. 2025An Improved Algorithm for Adversarial Linear Contextual Bandits via Reductioncited by 3
  22. 2024Scale-free Adversarial Reinforcement Learningcited by 2
  23. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
  24. 2025Reinforcement Learning from Adversarial Preferences in Tabular MDPscited by 2
  25. 2025An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPscited by 2
  26. 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcited by 2
  27. 2024Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedbackcited by 1
  28. 2024Optimistic Regret Bounds for Online Learning in Adversarial Markov Decision Processescited by 1
  29. 2026Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processescited by 1
  30. 2026Optimal Regret for Policy Optimization in Contextual Banditscited by 1
  31. 2026Multi-agent imitation learning with function approximation: Linear Markov games and beyondcited by 1
  32. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  33. 2024Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimizationcited by 0
  34. 2024State-free Reinforcement Learningcited by 0
  35. 2025Online Episodic Convex Reinforcement Learningcited by 0
  36. 2026Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximationcited by 0
  37. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
  38. 2026Near-Optimal Regret in Adversarial Kernel Banditscited by 0

50 most cited of 51 All 51 (JSON)