Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
This work provides theoretical guarantees for off-policy reinforcement learning algorithms in more realistic, non-i.i.d. settings, which is incremental but important for practical applications.
The authors tackled the problem of analyzing the convergence rate of the two time-scale TDC algorithm under non-i.i.d. Markovian samples, showing it can achieve O(log t/(t^(2/3))) convergence with diminishing stepsize and exponential convergence with constant stepsize, albeit with a non-vanishing error, and proposed a blockwisely diminishing stepsize variant for improved accuracy.
Gradient-based temporal difference (GTD) algorithms are widely used in off-policy learning scenarios. Among them, the two time-scale TD with gradient correction (TDC) algorithm has been shown to have superior performance. In contrast to previous studies that characterized the non-asymptotic convergence rate of TDC only under identical and independently distributed (i.i.d.) data samples, we provide the first non-asymptotic convergence analysis for two time-scale TDC under a non-i.i.d.\ Markovian sample path and linear function approximation. We show that the two time-scale TDC can converge as fast as O(log t/(t^(2/3))) under diminishing stepsize, and can converge exponentially fast under constant stepsize, but at the cost of a non-vanishing error. We further propose a TDC algorithm with blockwisely diminishing stepsize, and show that it asymptotically converges with an arbitrarily small error at a blockwisely linear convergence rate. Our experiments demonstrate that such an algorithm converges as fast as TDC under constant stepsize, and still enjoys comparable accuracy as TDC under diminishing stepsize.