mlsanityData to 14 Oct 2026

Finite-time Convergence Analysis of Actor-Critic with Evolving Reward

arXiv 2510.12334 ↗First posted 14 Oct 2025cs.LG cs.AIcited by 2

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Many popular practical reinforcement learning (RL) algorithms employ evolving reward functions-through techniques such as reward shaping, entropy regularization, or curriculum learning-yet their theoretical foundations remain underdeveloped. This paper provides the first finite-time convergence analysis of a single-timescale actor-critic algorithm in the presence of an evolving reward function under Markovian sampling. We consider a setting where the reward parameters may change at each time step, affecting both policy optimization and value estimation. Under standard assumptions, we derive non-asymptotic bounds for both actor and critic errors. Our result shows that an O(1/√T) convergence rate is achievable, matching the best-known rate for static rewards, provided the reward parameters evolve slowly enough. This rate is preserved when the reward is updated via a gradient-based rule with bounded gradient and on the same timescale as the actor and critic, offering a theoretical foundation for many popular RL techniques. As a secondary contribution, we introduce a novel analysis of distribution mismatch under Markovian sampling, improving the best-known rate by a factor of log2T in the static-reward case.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 43 of its 64 references that are in the map. First posted on arXiv 14 Oct 2025.

Builds on

43 of 64 references.

References · 43

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,379
  3. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,330
  4. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  5. 2015Continuous control with deep reinforcement learningcited by 3,407
  6. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  7. 2020Learning to summarize from human feedbackcited by 2,588
  8. 2018Soft Actor-Critic Algorithms and Applicationscited by 1,240
  9. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,194
  10. 2018Exploration by Random Network Distillationcited by 993
  11. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 669
  12. 2020Curriculum Learning for Reinforcement Learning Domains: A Framework and Surveycited by 373
31 more
  1. 2019Way Off-Policy Batch Deep Reinforcement Learning of Implicit Human Preferences in Dialogcited by 284
  2. 2019Self-Supervised Exploration via Disagreementcited by 265
  3. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  4. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  5. 2018Understanding the impact of entropy on policy optimizationcited by 176
  6. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 144
  7. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  8. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  9. 2020Learning to Utilize Shaping Rewards: A New Approach of Reward Shapingcited by 114
  10. 2018Count-Based Exploration with the Successor Representationcited by 112
  11. 2018On Learning Intrinsic Rewards for Policy Gradient Methodscited by 102
  12. 2019Keeping Your Distance: Solving Sparse Reward Tasks Using Self-Balancing Shaped Rewardscited by 78
  13. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 68
  14. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  15. 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
  16. 2017Count-Based Exploration in Feature Space for Reinforcement Learningcited by 49
  17. 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
  18. 2021Self-Supervised Online Reward Shaping in Sparse-Reward Environmentscited by 37
  19. 2024Exploration and Anti-Exploration with Distributional Random Network Distillationcited by 33
  20. 2022Finite-time analysis of single-timescale actor-criticcited by 32
  21. 2023Flipping Coins to Estimate Pseudocounts for Exploration in Reinforcement Learningcited by 28
  22. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 26
  23. 2020Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedupcited by 25
  24. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  25. 2023Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processescited by 25
  26. 2022A Small Gain Analysis of Single Timescale Actor Criticcited by 24
  27. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 20
  28. 2023Behavior Alignment via Reward Function Optimizationcited by 16
  29. 2022Exploring through Random Curiosity with General Value Functionscited by 10
  30. 2021Learning to Shape Rewards using a Game of Two Partnerscited by 9
  31. 2024Random Latent Exploration for Deep Reinforcement Learningcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Collaborative Yet Personalized Policy Training: Single-Timescale Federated Actor-Criticcited by 0
  2. 2026Towards Understanding the Training of GFlowNets: A Theoretical Perspectivecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
  2. 2024On the Convergence of Single-Timescale Actor-Critic
  3. 2024A Finite-Sample Analysis of an Actor-Critic Algorithm for Mean-Variance Optimization in a Discounted MDP
  4. 2026Second-Order Actor-Critic Methods for Discounted MDPs via Policy Hessian Decomposition
  5. 2026A Concentration Bound for Two-Timescale Actor-Critic Algorithm
  6. 2026Provably Convergent Actor-Critic for MARL through Risk-aversion
  7. 2026Policy Gradient Methods for Non-Markovian Reinforcement Learning
  8. 2026Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning