Should one compute the Temporal Difference fix point or minimize the Bellman Residual ? The unified oblique projection view
Bruno Scherrer LORIA - INRIA Lorraine - Campus Scientifique - BP 239 54506 Vandœuvre-lès-Nancy CEDEX FRANCE
Abstract
We investigate projection methods, for evaluating a linear approximation of the value function of a policy in a Markov Decision Process context. We consider two popular approaches, the one-step Temporal Difference fix-point computation (TD(0)) and the Bellman Residual (BR) minimization. We describe examples, where each method outperforms the other. We highlight a simple relation between the objective function they minimize, and show that while BR enjoys a performance guarantee, TD(0) does not in general. We then propose a unified view in terms of oblique projections of the Bellman equation, which substantially simplifies and extends the characterization of Schoknecht (2002) and the recent analysis of Yu & Bertsekas (2008). Eventually, we describe some simulations that suggest that if the TD(0) solution is usually slightly better than the BR solution, its inherent numerical instability makes it very bad in some cases, and thus worse on average.
中文速览
马尔可夫决策过程（MDP）中的策略评估通常需要用线性函数去近似价值函数，而TD(0)不动点法和贝尔曼残差（Bellman Residual，BR）最小化法是两种最流行的做法，但学界对它们孰优孰劣一直缺乏清晰认识。本文通过构造具体的小型MDP反例，证明两种方法各有胜负——BR在某些情况下误差有界而TD误差可趋于无穷，TD在另一些情况下则能精确还原部分状态的价值而BR做不到。理论上，作者揭示了一个简洁关系：BR误差是TD误差的上界，因此BR最小化天然附带对近似误差的性能保证，而TD则没有类似保证，存在数值不稳定的隐患；进一步地，作者用斜投影（oblique projection）的统一框架重新诠释并推广了前人对这两种方法的分析。模拟实验则表明，TD解通常略优于BR解，但其数值不稳定性会在部分情形下导致极差的结果，平均而言反而不如BR——这一发现对实际算法选择具有重要的参考价值。
原文 arXiv:1011.4362;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1011.4362v1