Convergence of Two-Timescale Markovian Stochastic Approximations with Applications in Reinforcement Learning

This work studies the convergence of two-timescale stochastic approximations (SA), a class of iterative algorithms that update two sets of parameters in fast and slow timescales respectively. Notable examples of two-timescale SA in reinforcement learning (RL) include temporal difference learning with gradient correction (TDC) and actor-critic methods. Previously, the stability (i.e., boundedness) and convergence of two-timescale SA were only established under i.i.d. noise. This work instead establishes the stability and convergence of two-timescale SA under Markovian noise, a setup that is more realistic in RL. Notably, we do not need to use any projection operator and the noise does not need to live in a compact space. Our key technical novelty is to control the fast timescale parameter with the running max of the slow timescale parameter, instead of with the current slow timescale parameter, as most prior works do. As a key application, we establish the first almost sure convergence of TDC with eligibility traces under off-policy learning with linear function approximation.

Some AI systems learn by updating certain components quickly while adjusting others more gradually. This "two-timescale" learning strategy is widely used in algorithms for decision-making tasks such as robotics and game playing, and evaluating how well an AI system makes decisions. However, previous mathematical guarantees for these methods relied on unrealistic assumptions about the randomness in the data they observe. In this work, we prove that two-timescale learning algorithms converge (i.e., they eventually stabilize to the desired solution) even when the data is correlated over time, as is typically the case in real-world AI systems. Our analysis also removes several restrictive assumptions used in earlier work, making the results applicable to a broader range of algorithms. The key technical idea is a new way of analyzing how the fast- and slow-changing parts of the algorithm interact. As an important application, we establish the first rigorous convergence guarantee for a widely used algorithm called temporal difference learning with gradient correction with eligibility traces. Overall, these results strengthen the theoretical foundations of AI and help explain why practical algorithms can perform reliably in complex environments.