Emphatic temporal difference (ETD) learning (Sutton et al., 2016) is a successful method to conduct the off-policy value function evaluation with function approximation. Although ETD has been shown to converge asymptotically to a desirable value function, it is well-known that ETD often encounters a large variance so that its sample complexity can increase exponentially fast with the number of iterations. In this work, we propose a new ETD method, called PER-ETD (i.e., PEriodically Restarted-ETD), which restarts and updates the follow-on trace only for a finite period for each iteration of the evaluation parameter. Further, PER-ETD features a design of the logarithmical increase of the restart period with the number of iterations, which guarantees the best trade-off between the variance and bias and keeps both vanishing sublinearly. We show that PER-ETD converges to the same desirable fixed point as ETD, but improves the exponential sample complexity of ETD to be polynomials. Our experiments validate the superior performance of PER-ETD and its advantage over ETD.

本文提出了一种新的ETD方法PER-ETD，通过每次评估参数的迭代周期内重启和更新后续跟踪，采用对数增长的设计来保证方差和偏差之间的最佳权衡，并保持两者亚线性消失，实现了与ETD相同的理想固定点收敛，但改善了ETD的指数样本复杂度为多项式级别，实验证明PER-ETD具有优越性能和优势。

PER-ETD: 多项式高效的强调时序差分学习方法