Policy evaluation with temporal differences: a survey and comparison

By Christoph Dann, Gerhard Neumann, Jan Peters. 2015

252 citations recorded by the source corpus.

Value functions are an essential tool for solving sequential decision making problems such as Markov decision processes (MDPs). Computing the value function for a given policy (policy evaluation) is not only important for determining the quality of the policy but also a key step in prominent policy-iteration-type algorithms. In common settings where a model of the Markov decision process is not available or too complex to handle directly, an approximation of the value function is usually estimated from samples of the process. Linearly parameterized estimates are often preferred due to their simplicity and strong stability guarantees. Since the late 1980s, research on policy evaluation in these scenarios has been dominated by temporal-difference (TD) methods because of their data-efficiency. However, several core issues have only been tackled recently, including stability guarantees for off-policy estimation where the samples are not generated by the policy to evaluate. Together with improving sample efficiency and probabilistic treatment of uncertainty in the value estimates, these efforts have lead to numerous new temporal-difference algorithms. These methods are scattered over the literature and usually only compared to most similar approaches. The article therefore aims at presenting the state of the art of policy evaluation with temporal differences and linearly parameterized value functions in discounted MDPs as well as a more comprehensive comparison of these approaches.We put the algorithms in a unified framework of function optimization, with focus on surrogate cost functions and optimization strategies, to identify similarities and differences between the methods. In addition, important extensions of the base methods such as off-policy estimation and eligibility traces for better bias-variance trade-off, as well as regularization in high dimensional feature spaces, are discussed.

Subfields: Artificial Intelligence, Computer Science Applications, Economics and Econometrics, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

In Economics and Econometrics

In Reinforcement Learning

Citations in the corpus

Benchmarking Deep Reinforcement Learning for Continuous Control (2016, methodology): “Tdlearn (Dann et al., 2014) includes a 20-link pole balancing task, DotRL (Papis & Wawrzyński, 2013) includes a variable-DOF octopus arm and a 6-DOF planar cheetah model, PyBrain (Schaul et al.”
Compatible Value Gradients for Reinforcement Learning of Continuous Deep Policies (2015, background): “The convergence properties of TD-learning and related algorithms have been studied extensively, see (Tsitsiklis and Roy, 1997; Dann et al., 2014).”
Doubly Robust Off-policy Value Evaluation for Reinforcement Learning (2015, methodology): “, 2012), or to fitting the value function directly (Bertsekas & Tsitsiklis, 1996; Sutton & Barto, 1998; Dann et al., 2014).”
On Convergence of Emphatic Temporal-Difference Learning (2015, background): “See e.g., (Maei, 2011; Bertsekas and Yu, 2009; Geist and Scherrer, 2014; Dann et al., 2014).”
An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning (2015, methodology): “Watkins (1989) extended TD learning to control in the form of Q-learning and proved its convergence in the tabular case (without function approximation, Watkins & Dayan 1992), while Rummery (1995) extended TD learning to control in an on-policy form as the Sarsa(λ) algorithm.”
Finite-Sample Analysis of Proximal Gradient TD Algorithms (2015, methodology): “004 for GTD2-MP, which are chosen via comparison studies as in [Dann et al. , 2014].”
Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning (2019, background): “A concrete example is the famous double sampling problem [11], which is not applicable in many contemporary RL benchmarks.”
A Kernel Loss for Solving the Bellman Equation (2019, methodology): “Under the conditions of the corollary, the kernel loss becomes the Norm of the Expected TD Update (NEU), whose minimizer coincides with the TD solution (Dann et al., 2014).”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, background): “See [65] for a more detailed review on policy evaluation.”
Bellman-consistent Pessimism for Offline Reinforcement Learning (2021, background): “1) has a closed-form solution which generalizes LSTDQ [Lagoudakis and Parr, 2003; Sutton et al., 2009; Dann et al., 2014].”
Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize (2015, methodology): “The experimental results in [10] suggest to us that each version can have less variance than the other in some occasions, however.”
Off-policy learning based on weighted importance sampling with linear computational complexity (2015, methodology): “A Monte Carlo technique known as importance sampling (Kahn & Marshall 1953, Rubinstein 1981) is often used to resolve this mismatch in policies (Sutton & Barto 1998, Dann, Neumann & Peters 2014, Geist & Scherrer 2014).”
f-Divergence constrained policy improvement (2017, background): “Performing stochastic gradient descent (SGD) on these objectives leads to various flavors of the residual gradient (RG) algorithm (Baird, 1995), recently surveyed by Dann et al. (2014).”
Stochastic Variance Reduction Methods for Policy Evaluation (2017, methodology): “7 Extensions It is possible to extend our approach to accelerate optimization of other objectives such as MSBE and NEU (Dann et al., 2014).”
Multi-step Off-policy Learning Without Importance Sampling Ratios (2017, background): “A number of computationally scalable algorithms have been proposed that can learn oﬀ-policy without requiring to access or estimate the model of the environment and in that sense are model-free (Precup et al. 2000, 2001, Maei & Sutton 2010, Maei 2011, Yu 2012, Geist & Scherrer 2014, Dann et al. 2014”
Multiagent Fully Decentralized Value Function Learning With Linear Convergence Rates (2018, methodology): “Similarly to [40], we consider randomly generated MDP’s.”
Regularized Policy Iteration with Nonparametric Function Spaces (2016, background): “Several TD-based algorithms and their regularized variants are discussed in a survey by Dann et al. (2014).”
DEVELOPING A PREDICTIVE APPROACH TO KNOWLEDGE (2015, methodology): “Prior experimental studies of gradient-TD methods (e.g., Sutton et al., 2009; Degris et al., 2012; Hackman, 2013; Dann et al., 2014) demonstrated that αh values near zero can achieve good performance in terms of MSPBE optimization and reward maximization (see Degris et al.”