Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes
Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes
复制标题
DOI：
10.1145/3578338.3593526
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
D. Huo;Yudong Chen;Qiaomin Xie
中科院分区：
文献类型：
--
作者：
D. Huo;Yudong Chen;Qiaomin Xie
我们考虑使用恒定步骤的线性近似（LSA），并将LSA的联合过程视为一个时间合并的马尔可夫链，证明了其在Wasserstein距离中的独特限制和固定分布纳偏差与高阶术语成比例。与I.I.D相比，LSA在可逆的链中消失了。 IAS。证明可以使用M≥2个步骤来减少偏见，从而消除了偏置扩展中的M-1领先术语。
We consider Linear Stochastic Approximation (LSA) with constant stepsize and Markovian data. Viewing the joint process of the data and LSA iterate as a time-homogeneous Markov chain, we prove its convergence to a unique limiting and stationary distribution in Wasserstein distance and establish non-asymptotic, geometric convergence rates. Furthermore, we show that the bias vector of this limit admits an infinite series expansion with respect to the stepsize. Consequently, the bias is proportional to the stepsize up to higher order terms. This result stands in contrast with LSA under i.i.d. data, for which the bias vanishes. In the reversible chain setting, we provide a general characterization of the relationship between the bias and the mixing time of the Markovian data, establishing that they are roughly proportional to each other. Polyak-Ruppert averaging reduces the variance of the LSA iterates but does not affect the bias. The above characterization allows us to show that the bias can be reduced using Richardson-Romberg extrapolation with m≥ 2 stepsizes, which eliminates the m-1 leading terms in the bias expansion. This extrapolation scheme leads to an exponentially smaller bias and an improved mean squared error, both in theory and empirically. Our results immediately apply to the Temporal Difference learning algorithm with linear function approximation, Markovian data, and constant stepsizes.