mlsanityData to 7 Oct 2026

Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs

arXiv 1909.02769 ↗First posted 6 Sep 2019cs.LG math.OC stat.MLcited by 113

Not on the map. Why?

Abstract (arXiv)

Trust region policy optimization (TRPO) is a popular and empirically successful policy search algorithm in Reinforcement Learning (RL) in which a surrogate problem, that restricts consecutive policies to be 'close' to one another, is iteratively solved. Nevertheless, TRPO has been considered a heuristic algorithm inspired by Conservative Policy Iteration (CPI). We show that the adaptive scaling mechanism used in TRPO is in fact the natural "RL version" of traditional trust-region methods from convex analysis. We first analyze TRPO in the planning setting, in which we have access to the model and the entire state space. Then, we consider sample-based TRPO and establish tilde O(1/√N) convergence rate to the global optimum. Importantly, the adaptive scaling mechanism allows us to analyze TRPO in regularized MDPs for which we prove fast rates of tilde O(1/N), much like results in convex optimization. This is the first result in RL of better rates when regularizing the instantaneous cost or reward.

Key facts. Cited by 113 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Sep 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 2; 2021: 34; 2022: 20; 2023: 21; 2024: 11; 2025: 16; 2026: 9.

113 papers.

Sort:

By area:

  1. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  2. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  3. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  4. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  5. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  6. 2021Reward is enough for convex MDPscited by 82
  7. 2021A general sample complexity analysis of vanilla policy gradientcited by 74
  8. 2023Factually Consistent Summarization via Reinforcement Learning with Textual Entailment Feedbackcited by 71
  9. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  10. 2024REBEL: Reinforcement Learning via Regressing Relative Rewardscited by 66
  11. 2024Multi-turn Reinforcement Learning from Preference Human Feedbackcited by 65
  12. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 64
38 more
  1. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 63
  2. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  3. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 46
  4. 2021Twice regularized MDPs and the equivalence between robustness and regularizationcited by 46
  5. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  6. 2021Greedification Operators for Policy Optimization: Investigating Forward and Reverse KL Divergencescited by 40
  7. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  8. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 32
  9. 2022Mirror Learning: A Unifying Framework of Policy Optimisationcited by 31
  10. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 31
  11. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  12. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  13. 2021Online Apprenticeship Learningcited by 28
  14. 2021Provable RL with Exogenous Distractors via Multistep Inverse Dynamicscited by 28
  15. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  16. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  17. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  18. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 24
  19. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  20. 2022Policy Optimization over General State and Action Spacescited by 21
  21. 2023ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPscited by 19
  22. 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
  23. 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 18
  24. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 17
  25. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 17
  26. 2023PPO-Clip Attains Global Optimality: Towards Deeper Understandings of Clippingcited by 17
  27. 2021A general class of surrogate functions for stable and efficient reinforcement learningcited by 16
  28. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  29. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  30. 2021Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximationcited by 15
  31. 2021Bregman Gradient Policy Optimizationcited by 15
  32. 2022Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexitycited by 14
  33. 2021Actor-critic is implicitly biased towards high entropy optimal policiescited by 13
  34. 2022Latency Optimization for Blockchain-Empowered Federated Learning in Multi-Server Edge Computingcited by 13
  35. 2020When Will Generative Adversarial Imitation Learning Algorithms Attain Global Convergencecited by 12
  36. 2022Finite-Time Analysis of Natural Actor-Critic for POMDPscited by 12
  37. 2025RiskPO: Risk-based Policy Optimization via Verifiable Reward for LLM Post-Trainingcited by 12
  38. 2021Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximationcited by 11

50 most cited of 113 All 113 (JSON)