Emphatic TD Bellman Operator is a Contraction

By Assaf Hallak, Aviv Tamar, Shie Mannor. 2015

3 citations recorded by the source corpus.

Recently, \citet{SuttonMW15} introduced the emphatic temporal differences (ETD) algorithm for off-policy evaluation in Markov decision processes. In this short note, we show that the projected fixed-point equation that underlies ETD involves a contraction operator, with a $\sqrt{\gamma}$-contraction modulus (where $\gamma$ is the discount factor). This allows us to provide error bounds on the approximation error of ETD. To our knowledge, these are the first error bounds for an off-policy evaluation algorithm under general target and behavior policies.

Subfields: Artificial Intelligence, Control and Systems Engineering, Reinforcement Learning, Statistical Learning Theory

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

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (2020, methodology): “Only recently have practical methods for estimating the marginalized importance ratio been introduced (Sutton et al., 2016; Yu, 2015; Hallak et al., 2015, 2016; Hallak and Mannor, 2017; Nachum et al., 2019a; Zhang et al., 2020; Nachum et al., 2019b).”
Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize (2015, background): “ subspaces that determines the approximation bias Φθ∗ − Πvπ in the worst case, for a worst-case choice of rλ π,γ. (For details, see also [55, Sec. 2.2].) Recently, for the case of constant λ,i and γ, [31, 15] derived bounds on the approximation bias that are based on contraction (or contraction-like”