Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise
This work provides theoretical guarantees for two-time-scale stochastic approximation methods used in reinforcement learning, addressing a known bottleneck in analyzing algorithms with Markovian noise.
The authors derived a tight finite-time upper bound on the error for linear two-time-scale stochastic approximation with Markovian noise, showing that the mean squared error decreases as trace(Σ^y)/k + o(1/k), where Σ^y matches the covariance in the Central Limit Theorem. They applied this result to establish sample complexity for off-policy reinforcement learning algorithms like TDC, GTD, and GTD2.
Stochastic approximation (SA) is an iterative algorithm for finding the fixed point of an operator using noisy samples and widely used in optimization and Reinforcement Learning (RL). The noise in RL exhibits a Markovian structure, and in some cases, such as gradient temporal difference (GTD) methods, SA is employed in a two-time-scale framework. This combination introduces significant theoretical challenges for analysis. We derive an upper bound on the error for the iterations of linear two-time-scale SA with Markovian noise. We demonstrate that the mean squared error decreases as $trace (Σ^y)/k + o(1/k)$ where $k$ is the number of iterates, and $Σ^y$ is an appropriately defined covariance matrix. A key feature of our bounds is that the leading term, $Σ^y$, exactly matches with the covariance in the Central Limit Theorem (CLT) for the two-time-scale SA, and we call them tight finite-time bounds. We illustrate their use in RL by establishing sample complexity for off-policy algorithms, TDC, GTD, and GTD2. A special case of linear two-time-scale SA that is extensively studied is linear SA with Polyak-Ruppert averaging. We present tight finite time bounds corresponding to the covariance matrix of the CLT. Such bounds can be used to study TD-learning with Polyak-Ruppert averaging.