Consistent On-Line Off-Policy Evaluation

By Assaf Hallak, Shie Mannor. 2017

99 citations recorded by the source corpus.

The problem of on-line off-policy evaluation (OPE) has been actively studied in the last decade due to its importance both as a stand-alone problem and as a module in a policy improvement scheme. However, most Temporal Difference (TD) based solutions ignore the discrepancy between the stationary distribution of the behavior and target policies and its effect on the convergence limit when function approximation is applied. In this paper we propose the Consistent Off-Policy Temporal Difference (COP-TD($\lambda$, $\beta$)) algorithm that addresses this issue and reduces this bias at some computational expense. We show that COP-TD($\lambda$, $\beta$) can be designed to converge to the same value that would have been obtained by using on-policy TD($\lambda$) with the target policy. Subsequently, the proposed scheme leads to a related and promising heuristic we call log-COP-TD($\lambda$, $\beta$). Both algorithms have favorable empirical results to the current state of the art on-line OPE algorithms. Finally, our formulation sheds some new light on the recently proposed Emphatic TD learning.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering, Water Science and Technology, Reinforcement Learning, Evaluation & Benchmarks

How researchers see this paper

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

In Computer Networks and Communications

In Electrical and Electronic Engineering

In Water Science and Technology

In Reinforcement Learning

In Evaluation & Benchmarks

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).”
Conservative Q-Learning for Offline Reinforcement Learning (2020, methodology): “Because these methods use dynamic programming, they can suffer from OOD actions [34, 17, 20, 40].”
Accelerating Online Reinforcement Learning with Offline Datasets (2020, methodology): “due to error accumulation with distribution shift [8, 21]. Ofﬂine RL methods aim to address this issue, often by constraining the actor updates to avoid excessive deviation from the data distribution [23, 41, 13, 14, 12, 21, 8, 22, 38, 26, 47]. One class of these methods utilize importance sampling ”
MOReL : Model-Based Offline Reinforcement Learning (2020, background): “[44] perform planning with learned importance weights [45, 46, 47] while using a notion of pessimism for regularization.”
Batch Stationary Distribution Estimation (2020, background): “It is sufﬁcient to adjust observed rewards according to the ratio between the target and behavior stationary distributions (Hallak and Mannor, 2017; Liu et al., 2018; Gelada and Bellemare, 2019).”
GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values (2020, methodology): “Inspired by Hallak & Mannor (2017); Liu et al. (2018), Gelada & Bellemare (2019); Uehara & Jiang (2019) pro-pose different estimators for learning density ratios, either with semi-gradient updates (Sutton, 1988) or by restricting the function class to Reproducing Kernel Hilbert Space.”
Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation (2019, background): “Several other works (Guo et al., 2017; Hallak & Mannor, 2017; Liu et al., 2018a; Gelada & Bellemare, 2019; Nachum et al., 2019) have been proposed to address the high variance issue in the long-horizon problems.”
DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections (2019, methodology): “Proper estimation of these ratios can improve the accuracy of policy evaluation [21] and the stability of policy learning [12, 14, 22, 40].”
Generalized Off-Policy Actor-Critic (2019, methodology): “To approach this issue, Emphatic TD (ETD, Sutton et al. 2016) Inspired by ETD, Hallak and Mannor (2017) propose to weight ∆ t via ρ t ¯ c ( S t ) in the Consistent Off-Policy TD (COP-TD) algorithm, where ¯ c ( s ) .”
Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation (2018, background): “To the best of our knowledge, the recently developed COP-TD algorithm [11] is the only work that attempts to estimate w ⇡ / ⇡ 0 as an intermediate step of estimating the value function of a target policy They take a stochastic-approximation approach and show asymptotic consistence.”
Off-Policy Policy Gradient with Stationary Distribution Correction (2019, background): “…approaches for policy evaluation that avoid the exponential blow up in importance sampling weights by instead computing a direct ratio over the stationary distribution of state visitations under the target and behavior policy (Hallak and Mannor, 2017; Liu et al., 2018a; Gelada and Bellemare, 2019).”
Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling (2019, background): “Hallak and Mannor [2017] and Gelada and Bellemare [2019] also leverage the same fact in time-invariant MDPs, where they use the stationary ratio of state-action pairs to replace the trajectory weights.”
Harnessing Inﬁnite-Horizon Off-Policy Evaluation: Double Robustness via Duality (2019, background): “Several other works (Guo et al., 2017; Hallak & Mannor, 2017; Liu et al., 2018a; Gelada & Bellemare, 2019; Nachum et al., 2019) have been proposed to address the high variance issue in the long-horizon problems.”
Flexible Option Learning (2021, methodology): “A possible solution would be to estimate this quantity by making use of recent approaches [Hallak and Mannor, 2017, Xie et al., 2019, Zhang et al., 2020].”
Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation (2019, methodology): “Applying GEM-style update to COP-TD (Hallak & Mannor, 2017) is still an open problem as COP-TD involves a nonlinear projection, whose gradient is hard to compute.”
A Survey on Offline Reinforcement Learning: Taxonomy, Review, and Open Problems (2022, methodology): “To avoid these exponential weights, marginalized IS [52] uses an estimate of the state-marginal importance ratio ρ (s) = (d (s))/(dβ (s)) to weigh the rewards at each time step.”
Provably Convergent Off-Policy Actor-Critic with Function Approximation (2019, methodology): “Applying GEM-style update to COP-TD (Hallak & Mannor, 2017) is still an open problem as COP-TD involves a nonlinear projection, whose gradient is hard to compute.”
Representation Balancing Offline Model-based Reinforcement Learning (2021, background): “OPE itself is one of the long-standing hard problems in RL (Sutton et al., 1998; 2009; Thomas & Brunskill, 2016; Hallak & Mannor, 2017).”