Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis
Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis
复制标题
DOI：
10.1137/20m1331524
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
K. Khamaru;A. Pananjady;Feng Ruan;M. Wainwright;Michael I. Jordan
中科院分区：
文献类型：
--
作者：
K. Khamaru;A. Pananjady;Feng Ruan;M. Wainwright;Michael I. Jordan
我们解决贴现马尔可夫决策过程中的政策评估问题，并提供实例相关的保证下生成模型的$\ell_\infty$-错误。我们建立了渐近和非渐近版本的局部极大极小的政策评估下限，从而提供了一个依赖于实例的基线比较算法。理论启发的模拟表明，广泛使用的时间差（TD）算法是严格的次优时，在非渐近设置进行评估，即使与Polyak-Ruppert平均。我们通过引入和分析方差减少形式的随机逼近来解决这个问题，表明它们实现了非渐近的，依赖于实例的对数因子的最优性。
We address the problem of policy evaluation in discounted Markov decision processes, and provide instance-dependent guarantees on the $\ell_\infty$-error under a generative model. We establish both asymptotic and non-asymptotic versions of local minimax lower bounds for policy evaluation, thereby providing an instance-dependent baseline by which to compare algorithms. Theory-inspired simulations show that the widely-used temporal difference (TD) algorithm is strictly suboptimal when evaluated in a non-asymptotic setting, even when combined with Polyak-Ruppert iterate averaging. We remedy this issue by introducing and analyzing variance-reduced forms of stochastic approximation, showing that they achieve non-asymptotic, instance-dependent optimality up to logarithmic factors.