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

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/\sqrt{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 $\log^2T$ in the static-reward case.

Popular artificial intelligence (AI) programs often learn through trial and error using a system of rewards. To speed up this training, researchers frequently shift these rewards over time—essentially moving the goalposts to guide the AI from simple tasks to harder ones. However, we lacked the mathematical proof to guarantee that this "shifting goalpost" method actually works reliably. Our study provides the very first mathematical guarantee for this approach. We analyzed a standard AI learning setup and proved that even when rewards change at every single step, the AI is still guaranteed to find the absolute best strategy. In fact, as long as the rewards don't change too abruptly, the AI learns just as fast as it would with fixed, unchanging goals. By proving exactly how and why these moving rewards work, we have built a solid foundation for techniques already used to train cutting-edge AIs. This reassurance allows developers to design smarter, faster, and more adaptable AI systems with total confidence that their math is sound.