Timezone: »

 
Poster
Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
Tengyu Xu · Shaofeng Zou · Yingbin Liang

Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #206
in Reinforcement Learning and Planning -- Markov Decision Processes »

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.

Keywords: Markov Decision Processes · Optimization · Reinforcement Learning and Planning · Stochastic Optimization
[ Paper]  [ Poster] 

Author Information

Tengyu Xu (The Ohio State University)
Shaofeng Zou (University at Buffalo, the State University of New York)
Yingbin Liang (The Ohio State University)

More from the Same Authors