Implicit Temporal Differences
Anonymous Author 1、Anonymous Author 2、Anonymous Author 3 Aviv Tamar The Technion - Israel Institute of Technology Haifa 32000, Israel、Panos Toulis Department of Statistics, Harvard University Cambridge, MA 02138, USA、Shie Mannor The Technion - Israel Institute of Technology Haifa 32000, Israel、Edoardo M. Airoldi Department of Statistics, Harvard University Cambridge, MA 02138, USA
Abstract
In reinforcement learning, the TD( $\lambda$ ) algorithm is a fundamental policy evaluation method with an efficient online implementation that is suitable for large-scale problems. One practical drawback of TD( $\lambda$ ) is its sensitivity to the choice of the step-size. It is an empirically well-known fact that a large step-size leads to fast convergence, at the cost of higher variance and risk of instability. In this work, we introduce the implicit TD( $\lambda$ ) algorithm which has the same function and computational cost as TD( $\lambda$ ), but is significantly more stable. We provide a theoretical explanation of this stability and an empirical evaluation of implicit TD( $\lambda$ ) on typical benchmark tasks. Our results show that implicit TD( $\lambda$ ) outperforms standard TD( $\lambda$ ) and a state-of-the-art method that automatically tunes the step-size, and thus shows promise for wide applicability.
中文速览
TD(λ)是强化学习中估计价值函数的核心算法，但它对步长（step-size）极度敏感——步长大则收敛快却容易发散，步长小则稳定但收敛慢，这一痼疾长期困扰着实际应用。受隐式随机梯度下降（implicit SGD）的启发，本文提出"隐式TD(λ)"：在每步权重更新时，让新权重同时出现在等式两端，再利用Sherman-Morrison公式将其化为与标准TD(λ)计算量完全相同（特征数线性复杂度）的显式公式。理论上，作者通过分析每次迭代中权重变化的上界证明，隐式版本引入了一个自动收缩因子βₜ，当特征向量的范数很大时能把更新幅度压回安全范围，从而从根本上抑制发散；实验上，在puddle world和cart-pole等基准任务中，隐式TD(λ)在所有测试步长下均保持稳定，而标准TD(λ)和当前最优的自适应步长方法Alpha-Bound在步长稍大时便频繁崩溃。这项工作意义在于：它在不增加任何计算开销、不改变收敛目标的前提下，大幅提升了TD(λ)的鲁棒性，有望直接替代标准TD(λ)成为新的默认实现。
原文 arXiv:1412.6734;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1412.6734v1