The optimal unbiased value estimator and its relation to LSTD, TD and MC

By Steffen Grünewälder, Klaus Obermayer. 2009

7 citations recorded by the source corpus.

In this analytical study we derive the optimal unbiased value estimator (MVU) and compare its statistical risk to three well known value estimators: Temporal Difference learning (TD), Monte Carlo estimation (MC) and Least-Squares Temporal Difference Learning (LSTD). We demonstrate that LSTD is equivalent to the MVU if the Markov Reward Process (MRP) is acyclic and show that both differ for most cyclic MRPs as LSTD is then typically biased. More generally, we show that estimators that fulfill the Bellman equation can only be unbiased for special cyclic MRPs. The reason for this is that at each state the bias is calculated with a different probability measure and due to the strong coupling by the Bellman equation it is typically not possible for a set of value estimators to be unbiased with respect to each of these measures. Furthermore, we derive relations of the MVU to MC and TD. The most important of these relations is the equivalence of MC to the MVU and to LSTD for undiscounted MRPs in which MC has the same amount of information. In the discounted case this equivalence does not hold anymore. For TD we show that it is essentially unbiased for acyclic MRPs and biased for cyclic MRPs. We also order estimators according to their risk and present counter-examples to show that no general ordering exists between the MVU and LSTD, between MC and LSTD and between TD and MC. Theoretical results are supported by examples and an empirical evaluation.

Subfields: Artificial Intelligence, Control and Systems Engineering

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 Control and Systems Engineering

Citations in the corpus

RUDDER: Return Decomposition for Delayed Rewards (2018, methodology): “at all action-state pairs are visited and updated inﬁnitely often. A2.2 Bias-Variance of the Q-Value Estimators Bias-variance investigations have been done for Q-learning. Grünewälder & Obermayer [34] investigated the bias of temporal difference learning (TD), Monte Carlo estimators (MC), and le”
Construction of approximation spaces for reinforcement learning (2013, background): “3) is the most sample effective unbiased value estimator (Grünewälder and Obermayer, 2011).”