Practical Marginalized Importance Sampling with the Successor Representation
Authors: Scott Fujimoto
David Meger
Doina Precup
Venue:  (2021)
Keywords: marginalized importance sampling
off-policy evaluation
deep reinforcement learning
successor representation

Abstract: Marginalized importance sampling (MIS), which measures the density ratio between the state-action occupancy of a target policy and that of a sampling distribution, is a promising approach for off-policy evaluation. However, current state-of-the-art MIS methods rely on complex optimization tricks and succeed mostly on simple toy problems. We bridge the gap between MIS and deep reinforcement learning by observing that the density ratio can be computed from the successor representation of the target policy. The successor representation can be trained through deep reinforcement learning methodology and decouples the reward optimization from the dynamics of the environment, making the resulting algorithm stable and applicable to high-dimensional domains. We evaluate the empirical performance of our approach on a variety of challenging Atari and MuJoCo environments.

Under review as a conference paper at ICLR 2021
PRACTICAL MARGINALIZED IMPORTANCE SAMPLING WITH THE SUCCESSOR REPRESENTATION
Anonymous authors Paper under double-blind review
ABSTRACT
Marginalized importance sampling (MIS), which measures the density ratio be- tween the state-action occupancy of a target policy and that of a sampling distri- bution, is promising approach for off-policy evaluation. However, current state- of-the-ar art MIS methods rely on complex optimization tricks and succeed mostly on simple toy problems. We bridge the gap between MIS and deep reinforcement learning by observing that the density ratio can be computed from the successor representation of the target policy. The successor representation can be trained through deep reinforcement learning methodology and decouples the reward op- timization from the dynamics of the environment, making the resulting algorithm stable and applicable to high- sigh-dimenssonal domains. We evaluate the empirical performance our approach on a variety of challenging Atari and MuloCo envi- ronments.
INTRODUCTION
Off-policy evaluation (OPE) is a reinforcement learning (RL) task where the aim is to measure the performance of a target policy from data collected by separate behavior policy (Sutton & Barto 1998). As it can often be difficult or costly to obtain new data, OPE offers an avenue for re-using previously stored data, making it an important challenge for applying RL real-world
domains (Zhao et al. 2009 Mandel et al. 2014 Swaminathan et al. 2017
Gauci et al.) 2018).
Marginalized importance sampling (MIS) (Liu et al.) [0188] Xie al. 2019 Nachum al.. 2019a) is a family of OPE methods which re-weight sampled rewards by directly learning the density ratio between the state-action occupancy of the target policy and the sampling distribution. This approach can have significantly lower variance than traditional importance sampling methods (Precup et al.) 2001], which consider a product of ratios over trajectories, and is amenable to deterministic policies and behavior agnostic settings where the sampling distribution is unknown. However, the body of MIS work is largely theoretical, and as a result, empirical evaluations of MIS have mostly been carried out simple diw-dimensional tasks, such mountain car (state dim. of 2) cartpole (state dim. of 4). In comparison, deep RL algorithms have shown successful behaviors in high-dimensional domains such as Humanoid locomotion (state dim. of 376) and Atari (image-based),
In this paper, we present a straightforward approach for MIS that can be computed from the suc- cessor representation (SR) of the target policy. Our algorithm, the Successor Representation DIs- tribution Correction Estimation (SR-DICE), is the first method that allows MIS to scale to high- dimensional systems, far outperforming previous approaches. In comparison to previous algorithms which rely on minimax optimization or kernel methods (Liu et al.) 2018 Nachum et al. 2019a Uehara & Jiagg 2019 Mousavi et al. 2020), SR-DICE requires only a simple convex loss ap- plied to the linear function determining the reward, after computing the SR. Similar to the deep RI. methods which can learn in high-dimensional domains, the SR can computed easily using behavior-agnostic lemporal-differeme (TD) methods. This makes our algorithm highly amenable to deep learning architectures and applicable to complex tasks.
Our derivation of SR-DICE also reveals an interesting connection between MIS methods and value function learning. The key motivation for MIS methods is, unlike traditional importance sampling methods, they can avoid variance with an exponential dependence on horizon, by re- s-wiiihting in- dividual transitions rather than accumulating ratios along entire trajectories. We remark that while the MIS ratios only consider individual transitions, the optimization procedure is still subject the

---

Under review as a conference paper at ICLR 2021
dynamics of the underlying MDP. Subsequently, we use this insight show a connection between a well-known MIS method, DIaIDICE (Nachum et al. 2019a), and Bellman residual minimiza- tion (Bellman 1957: Baird 1995). which can help explain some of the optimization properties and performance of
as well as other related MIS methods.
We benchmark the performance of SR-DICE on several high-dimensional domains in MuJoCo Todorov et al. 2012) and Atari (Bellemare et al.) 2013), against several recent MIS methods. Our results demonstrate two key findings regarding high-dimensional tasks.
SR-DICE significantly outperforms the benchmark algorithms. We attribute this performance gap SR-DICE's deep RL. components, outperforming the MIS baselines in the same way that deep RL outperforms traditional methods on high-ding sigh--imensional domains. Unfortunately, part of this performance gap is due to the fact that the baseline MIS methods scale poorly to challenging tasks, In Atari we find that the baseline MIS method exhibit unstable estimates, often reaching errors with many orders of magnitude.
MIS underperforms deep RL. Although SR-DICE achieves a high performance, we find its errors are bounded by the quality of the SR. Consequently, we find that SR-DICE and the standard SR achieve a similar performance across all tasks. Worse so, we find that using deep TD method, comparable to DQN (Mnih et al. 2015) for policy evaluation outperforms both methods. Although the performance gap is minimal, for OPE there lacks convincing argument for SR-DICE, any current MIS method, which introduce unnecessary complexity. However, this does not mean MIS is useless. We remark that the density ratios themselves are independent objective which have been used for applications such as policy regularization (Nachum et al.] [2019b] Touati et al.) 2020), imitation learning (Kostrikov et al. 2019)), off-policy policy gradients (Imani et al. 2018 Liu al.) 2019b Zhang et al.) 2019), and non-uniform sampling (Sinha et al.] (2020). SR-DICE serves as a stable, scalable approach for computing these ratios. We provide extensive experimental details in the supplementary material and our code is made available.
2 BACKGROUND
Reinforcement Learning. RL is a framework for maximizing accumulated reward of an agent interacting with its environment (Sutton & Barto 1998). This problem is typically framed as a Markov Decision Process (MDP) A,, A. do 7), with state space S, action space A, reward function R. dynamics model p. initial state distribution do and discount factor y. An agent selects actions according to a policy क : S x A + [0, 1]. In this paper we address the problem of off-policy evaluation (OPE) problem where the aim is to measure the normalized expected per-step reward of the policy R(T) = (1 - E, 1E= (rr(St, at)]. An important notion in OPE is the value function Q"((s,a) a) = E,, - 7 (r(s, at) 8ig = 8, ag = a). which measures the expected sum of discounted rewards when following n, starting from (s)
We define d' a) as the discounted state-action occupancy, the probability of seeing (s, a) under policy with discount y: d'
(1 11-7) 7) Ei=o 7' Sap du du(s))p - s, (a)sds))((s)) where pe (80 + s, I) is the probability of arriving the state after time steps when starting from an initial state so. This distribution is important as R(T) equals the expected reward r(s, a) under d":
R(x) = (e. (r(((8))))) a)].
Successor Representation. The successor representation (SR) (Dayan 1993) of a policy is measure of occupancy of future states. It can be viewed as a general value function that learns vector of the expected discounted visitation for each state. The successor representation Tp" of a given policy æ is defined as T (s'ls) = Ex 7'1 = s')1s0 = s]. Importantly, the value function can be recovered from the SR by summing over the expected reward of each state (s(s) = Σ. (s'' (s' [r(s', a')]. For infinite state and action spaces, the SR can instead be generalized the expected occupancy over features, known the deep SR (Kulkarni et al. 2016) or successor features (Barreto et al. 2017). For a given encoding function ø S x + R", the deep SR s= : S A + R is defined as the expected discounted sum over features from the encoding function á when starting from a given state-action pair and following
oc
1 (s, a) = Ex
> ((5,, ar)
80 s, 40 a
(2)
2

---

Under review as a conference paper at ICLR 2021
If the encoding ((s, a) is learned such that the original reward function is a linear function of the encoding r(s, = w o(s, a), then similar to the original formulation of SR, the value function can be recovered from linear function of the SR: (= is trained to minimize the MSE between v/ (8 and ((x, a) + roi'ss", on transitions (s. 0, s') sampled from the data set. A frozen target network vi is used to provide stability (Mnih al. 2015 Kulkarni et al., (2016), and is updated to the current network a/ + 6tah after fixed number of time steps. The encoding function Φ is typically trained by an encoder-decoder network (Kulkarni al.
v (s. a). The deep SR network a
2016 Machado et al. 2017 2018a).
Marginalized Importance Sampling. Marginalized importance sampling (MIS) is family of im- portance sampling approaches for off-policy evaluation in which the performance R(T)) is evaluated by re-weighting rewards sampled from a data set DD = [(s, a, r')') ~ p(s' (is'(s,a) a.)dd (s, a), where dD is an arbitrary distribution, typically but not necessarily, induced by some behavior policy. It
follows that R(T) can computed with importance sampling weights on the rewards d' (s.a).
(o,a)
d a) (s ((s))))(ssa)) r(s,
R (T) (s.a))dd
The goal of marginalized importance sampling methods is learn the weights w(s,a) (e
"P(s,a)' using data contained in D. The main benefit of MIS that unlike traditional importance methods, the ratios are applied to individual transitions rather than complete trajectories, which can reduce the variance of long or infinite horizon problems. In other cases, the ratios themselves can be used for variety of applications which require estimating the occupancy of state-action pairs.
DualDICE. Dual stationary DIstribution Correction Estimation (DualDICE) (Nachum et al. 2019a) is well-known MIS method which uses a minimax optimization to learn the density ratios. The underlying objective which DuaIDICE aims to minimize is the following:
1 2 ( ( (f((ss a')))] Em, (f an)]. (4)
min J(f)
It can be shown that Equation (4) is uniquely optimized by the MIS density ratio. However, since dependent on transitions (s, a, s'), there are two practical issues with
[s, a) 10)-210 ( a')l this underlying objective. First, the objective contains square within an expectation, giving rise to the double sampling problem (Baird 1995), where the gradient will be biased when using only a single sample of (s, a,,' 8'). Second, computing [(x,a] a) - [= ('s',a') aa)) for arbitrary state-action pairs, particularly those not contained in the data set, non-trivial, as relies on an expectation over succeeding states, which is generally inaccessible without model of the environment. To address both concerns, DualDICE uses Fenchel duality (Rockafellar 1970) to create the following minimax optimization problem:
min max J(f, w) = (ee.aand a' ()(s.
as)
w
(5)
(1 - 7) so (f du)]-
Similar to the original formulation, Equation (4) it can be shown that Equation (5) is minimized when w(s, a) is the desired density ratio.
A REWARD FUNCTION PERSPECTIVE ON DISTRIBUTION CORRECTIONS
In this section, we present our behavior-agnostic approach to estimating MIS ratios, called the Suc- cessor Representation DIstribution Correction Estimation (SR-DICE). Our main insight is that MIS can be viewed as optimization over the reward function, where the loss is uniquely optimized when the reward the desired density ratio. We then apply our reward function perspective on a well-known MIS method, DuaIDICE (Nachum et al. 2019a), which enables to observe difficul- ties in the optimization process and better understand related methods. All proofs for this section are left to Appendix A
3.1 THE SUCCESSOR REPRESENTATION DICE
We will now derive our MIS approach. Our derivation shows that by treating MIS as reward function optimization, obtain the desired density ratios can be obtained in straightforward manner
3

---

Under review as a conference paper at ICLR 2021
from the SR of the target policy. This pushes the challenging aspect of learning onto the computation of the SR, rather than optimizing the density ratio estimate. Furthermore, when tackling high- dimensional tasks, can leverage deep RL approaches (Mnih et al.) 2015 Kulkarni et al. 2016) to make learning the SR stable, giving rise to practical MIS method.
(s,a))) using only data sampled from the data set D and the policy т. This presents a challenge as we have direct access to neither d' nor dD. As a starting
Our aim is to determine the MIS ratios
("(s.a)
point, begin by following the derivation of DualDICE (Nachum et al. 2019a). We first consider the convex function _mx² næ, which is uniquely minimized by x² with f(s, a), m with ds a), and n with d' (s,a) a), we have reformulated the convex function as the following objective:
Now by replacing x
J(P) (nayaad [f(s, a) - -1- (s [f), F(s,a)V(s.a)
min
(6)
2
While this objective is still impractical it relies on expectations over both dp and d", from Nachum et al. (2019)) we can state the following about Equation (6)
Observation 1 The objective J(A) is minimized when f(s,a) = (s.a) (" V(s,a).
Now will diverge from the derivation of DuaIDICE. Note choice of notation, f(s, a), in Equation (6) Describing the objective in terms of a fictitious reward f will allow us to draw on familiar relationships between rewards and value functions and build stronger intuition. Consider the equivalence between the value function over initial state-action pairs and the expectation of rewards over the state-action visitation of the policy (1 - 7) !Q" (so, ao)l = [r(s a)].
follows that the expectation over d= in Equation ca)
can be replaced with a value function Q over f:
min J(P) = Beeaa)aa [F(s, a)²] -01 B) (Q ao) ((s,a)V(s.a)
Using (1 (1-7)lEso,a) (~ ao) = Ex- [F(s, a)] provides method for accessing the otherwise
intractable d! This form of the objective convenient because d by sampling from the data set and Q² can be computed using any policy evaluation method.
estimate the expectation
While we can estimate both terms in Equation with relative ease, the optimization problem not directly differentiable and would require re-learning the value function Q with every adjustment to the learned reward f. Fortunately, there exists a straightforward paradigm which enables direct reward function optimization known successor representation (SR).
Consider the relationship between the SR T of the target policy and its value function Exg.an IQT (su, ag)] E., (s))s E., EE, T (s}ss)EE, (rs,a)) the tabular setting. It fol- lows that we can create an optimization problem over the reward function from Equation (7)
1 Blaasaa [f(s, = a)?] - (1 Eso Σ Th (s|50) Bawn [f(s, a)]
min Jo Ju(F) = ((s.a)((s,a)
(8)
This objective can be generalized to continuous states by considering the deep SR that over features 0(s, a) and optimizing the weights of linear function In this instance, the estimated density
ratio f(s, a) is determined by w d(s, a) and we can optimize w by minimizing the following:
min J (w) = _ E,p (wTo[s, as) - (1 Bog [w 10 (so. [o)]
Since this optimization problem is convex, has closed form solution. Define Do as the set of start states contained in D. The unique optimizer Equation (9) is as follows:
D
min J(w) = (1 - 7)
Σ (agglso) "Fo 4o),
(10)
Σ (e.))ED (bs a) E, (1
D
SoEDo
where Φ; is the ith entry of the vector 6. However, may generally prefer iterative, gradient- based solutions for scalability. We call the combination of learning the deep SR followed by op-
timizing Equation (9) the Successor Representation stationary DIstribution Correction Estimation
4

---

Under review as a conference paper at ICLR 2021
Algorithm SR-DICE
1: At each time step sample mini-batch of N transitions (s, a, r')) and start states So from D.
2: for = 1 to Tı do
3: min 2 ( a)) (s)
Encoding & loss
4: for [ = 1 to T2 do
5: minga { a) + +700 (s'((s'' (s,
Deep successor representation v/tt loss
6: for t = to T3 do
7: minw 2 (w 0(s a))² -) v= (so. ap). Density ratio w loss (Eqution (9)
8: Output: R(T) estimate [DI 1 Esaar)e wi (s,a)r((,a).
(SR-DICE). SR-DICE is split into three learning phases: (1) learning the encoding 6, (2) learn- ing the deep SR प., and (3) optimizing Equation (9) For the first two phases follow standard practices from prior work (Kulkarni et al. 2016, Machado et al.J (2188)), training the encoding ø via decoodrr network to reconstruct the transition and training the deep SR t\ using TD learning-style methods. We summarize SR-DICE in Alggorihhmm I Additional implementation--evel
details can be found in Appendix DD
Although is difficult to make any guarantees on the accuracy of an approximate vh" trained with deep RI techniques, if assume 16t is exact, then we can show that SR-DICE learns the least squares estimator to the desired density ratio.
Theorem Assuming (1 - so [vb* (sn, ao)] Recers)met (o(s, a)). then the optimizer w of
(e the objective J(w) is the least squares estimator of SSxA (wT (oss (=(5,))
d(s,a).
Hence, the main sources of error in SR-DICE are learning the encoding 6 and the deep SR r/5" Notably, both of these steps independent of the main optimization problem of learning w, as we have shifted the challenging aspects of density ratio estimation onto learning the deep SR. This leaves deep RL to do the heavy lifting. The remaining optimization problem, Equation (9) only involves directly updating the weights of a linear function, and unlike many other MIS methods, requires no tricky minimax optimization.
SR-DICE can also be applied to any pre-existing SR, or included into standard deep RL algo- rithms (Mnih et al.) 2015 Lillicrap et al. 2015 Hessel et al. 20177] Fujimoto et al.) (2018) by treating the encoding @ as auxiliary reward. This provides an alternate form of policy evaluation through MIS, or method to access density ratios between the target policy and the sampling distribution, with possible applications exploration, policy regularization, or unbiased off off-policy gradients (Liu
ct al. 2019b; Nachum et al. 2019b Touati al. 2020).
3.2
REWARD FUNCTIONS MIS: A CASE STUDY ON DUALDICE
One of the main attractions for MIS methods is they use importance sampling ratios which re-wer t--weight individual transitions rather than entire trajectories. While independent of the length of trajectories collected by the behavior policy, we remark the optimization problem is not independent of the im- plicit horizon defined by the discount factor 7 and MIS methods are still subject to the dynamics of the underlying MDP. In SR-DICE we explicitly handle the dynamics of the MDP by learning the SR with TD learning methods. In this case study. we examine well-known MIS method, DuaIDICE (Nachum et al., 2019a), and discuss how propagates updates through the MDP by considering its relationship to residual algorithms which minimize the mean squared Bellman er- ror (Baird) 1995). By viewing other MIS methods through the lens of reward function optimization, we can understand their connection to value-based methods, shedding light on their optimization properties and challenges.
Recall the underlying objective of DualDICE:
1
min = / 2 E( (s(s.a) - 7E,, (/ (((,,(')) -
ao)].
(11)
By viewing the problem as reward function optimization, we can transform DuaIDICE into a more familiar format that considers rewards and value functions. To begin, state the following theorem.
5

---

Under review as a conference paper at ICLR 2021
Theorem 2 Given an MDP (S,A, . do: 7). policy n, and and function f 8 A - R. define the reward function r S x A + R where f(s, a) = f(s,, a) ~r (f(' d')] Then it follows that the value function Q" defined by the policy n. MDP, and reward function function ř, is the function f.
The proof follows naturally from the Bellman equation (Bellman) 1957.. Informally, Theorem states that any function can be treated as an exact value function Q", for carefully chosen reward function f(s, a) = f(s, a) - y [f a')].
Theorem 2 provides two perspectives on DuaIDICE. By replacing terms in Equation (1I) with re- wards and value functions, it can be viewed as the same objective as Equation (7) from SR-DICE:
1 min J(F) = 2 [)s,a)]] (1->))))91-1)-omp (ss,a)V(s.a)
Eso ( (80, ao)
(12)
The first insight from this relationship is that like SR-DICE, DualDICE can be viewed as reward function optimization and still requires some element of value learning. However, for DuaIDICE the form of the reward and value functions are unique. From Theorem 2 we remark that f ag) always exactly Q (so. ag) without additional computation. This occurs because f(so, ag) is not function of the reward, rather, the rewards are defined as function of f. When the reward function adjusted, [su 0o) may remain unchanged and other rewards are adjusted to compensate.
To emphasize how DuaIDICE is subject to the properties of value learning. consider a second per- spective on DuaIDICE taken from Theorem 2 where we replace f with Q":
min J(Q²)) = 2 B (Q0((s.)) -By [Q=(ss,a))) -(1 - Q"
(11--)EBoo 2) [ an)
Bellman residual minimization
(13)
The first term is equivalent to Bellman residual minimization (Bellman 1957 Baird 1995), where the reward is 0 for all state-action pairs. The second term attempts to maximize only the initial value function Q" (so, og). From a practical perspective this relationship is concerning as the first term
relies on successfully propagating updates throughout the MDP to balance out with changes to the initial values. which may occur quickly. Consequently, in cases where DualDICE performs poorly, we may see the initial values approach infinity.
To understand how this objective performs em- pirically, we measured the output of DuaIDICE on a basic OPE task with an identical be- havior and target policy, In this case the true MIS ratio is 1.0 for all state-action pairs. Consequently, both the fictiuous reward [f -)->aa>>aa... -= [f(',, d']]] and normalized initial value function (1 Esp.a (f an)] should approach 1.0. In Figure 1 we graph both E- (w, a)). where wiss a) f(s. a)
Pendulum
HallCheelsh
MIS Rato
04
Time
f(00, mo)
se(ss,)) a))
>IE...= f(s', a') is the ratio used by DualDICE [qquatio (5). and (1 2) (f(s an)!
plot the average values EgD [w[(s, a)l and (1 - 7) (su, ad)] output by DualDICE on a task with an identical behavior and target policy, such that the true value of both terms is 1. The 10 individual trials are plotted lightly, with the mean bold. The estimates of DualDICE matches our hypothesis that DuaIDICE overestimates fs0, og) as propagating up- dates through the MDP occurs much slower rate.
Figure 1:
output by DuaIDICE.
While on the easier task, Pendulum, the per- formance looks reasonable, on HalfCheetah we can see that (1 - En, If ag)] greatly overestimates and E [w((sa)) a)) is highly unsta- ble. This result is intuitive given the form of Equation (13) where the first term, which w(s, a) approximates, is pushed slowly towards 0 and the second term is pushed towards oc. On the lower dimensional problem, Pendulum, the objective is optimized more easily and both terms approach 1.0. On the harder problem, HalfCheetah. we can see how balancing residual learning, which is notoriously slow (Baird 1995), with a maximization term initial states creates difficult optimzation procedure.

---

Under review as a conference paper at ICLR 2021
These results highlight the importance, and challenge, of propagating updates through the MDP. MIS methods are not fundamentally different than value-based methods, and viewing them as such may allow us to develop richer foundations for MIS.
4 RELATED WORK
Off-Policy Evaluation. Off- Off-policy evaluation is well-studied problem with several familics of ap- proaches. One family of approaches is based on importance sampling, which re-weights trajectories by the ratio of likelihoods under the target and behavior policy (Precup al., (001). Importance sampling methods are unbiased but suffer from variance which can grow exponentially with the length of trajectories (Li al., 2015 Jiang & Li 2016). Consequently, research has focused on vari- ance reduction (Thomas & Brunskill |216]] Munos et al. al.] 2016 Farajtabar et al. (0118) or contextual bandits (Dudik et al. [011]] Wang et al. (017). Marginalized importance sampling methods (Liu et al. 2018) aim to avoid this exponential variance by considering the ratio in stationary distribu- tions, giving an estimator with variance which is polynomial with respect horizon (Xie et al.)
2019 Liu et al. 2019a). Follow-up work has introduced a variety of approaches and improvements. allowing them to be Schavior-agnostir (Nachum et al. 2019a] Uehara & Jiang [209 Mousavi al., 2020) and operate in the undiscounted setting (Zhang et al. 2020a c). In a similar vein, some OPE methods rely on emphasizing, or re- re-weighting, updates based on their stationary distribution (Sutton)
al. 2016 Mahmood et al. 2017 Hallak & Mannor 2017 2017/eelada Gelada & Bellemare 2019), or learning
the stationary distribution directly Wang et al. 2007 2008).
Successor Representation. Introduced originally by Dayan 1993) as an approach for improving
generalization in temporal-different methods, successor representations (SR) were revived by re- cent work deep successor RL (Kulkarni et al. 2016) and successor features (Barreto al. 2017) which demonstrated that the SR could be generalized to a function approximation setting. The SR has found applications for task transfer (Barreto al. 2018 Grimm al. 2019), navigation (Zhang et al. 2017: Zhu et al. 2017). and exploration (Machado et al., [201 8a Janz et al. 2019). 1t has also been used in a neuroscience context to model generalization and human reinforcement learn- ing (Gershman et al. 2012 Momennejad et al. [2017] (0177/Ge Gershman 2018). The SR and our work also relate to state representation learning (Lesort et al. 2018) and general value functions (Sutton & Tanner 2005 Suttonn et al.) 2011).
5 EXPERIMENTS
To evaluate method, we perform several off-policy evaluation (OPE) experiments variety of domains. The aim is to evaluate the normalized average discounted reward ((s.a)==r [r(s, a) of target policy π. We benchmark our algorithm against two MIS methods, DualDICE (Nachum et al. 2019a) and GradientDICE (Zhang et al.] 2020c). two deep RL approaches and the true return of the behavior policy. The first deep RL method a DQN-style approach (Mnih et al. 2015) where actions are selected by (denoted Deep TD) and the second is the deep SR where the weight w is trained minimize the MSE between w' T o(s, a) and r(s, a) (denoted Direct-SR) (Kulkarni al. 2016). Environment-specifi experimental details are presented below and complete algorithmic and hyper-parameter details are included the supplementary material.
Continuous-Acttonn Experiments. We evaluate the methods on variety of MuJoCo environments (Brockman et al., 2016, Todorov al. 2012]. We examine two experimental settings. In both settings the target policy т and behavior policy Tu are stochastic versions of a deterministic policy Ta obtained from training the TD3 algorithm (Fujimoto et al. 2018). We evaluate a target policy 0.1.
+ (0, o²), where
For the "easy" setting, we gather data set of 500k transitions using a behavior policy ma na (O of)). where σr = 0.133. This setting roughly matches the experimental setting defined by Zhang et al. (2020a).
For the "hard" setting, gather significantly smaller data set of 50k transitions using behavior policy which acts randomly with p = 0.2 and uses म. + +V of), where σb = 0.2, with = 0.8.
discount factor of 7 0.99 and all hyper-parameters are kept constant across environments. All experiments are performed over 10 seeds. We display the results of the "easy" setting in Figure 2 and the "hard" setting in iniiuree
Unless specified otherwise,
7

---

Under review as a conference paper at ICLR 2021
Hopper
Time sloza (165)
Tire (te5)
Time (745)
Time steza (Ted)
Time stppo
SR-DICE
DuaiDICE
GradienDDIC
Direct-SR
Deep
Behavior Rima
Figure 2: Off-policy evaluation results on the contimuous-action MuJoCo domain using the "easy" experimental setting (500k time steps and σ, 0.133). The shaded area captures one standard deviation across 10 trials. We remark that this setting be considered easy the behavior policy achieves lower error, often ouiper- forming all agents. BR-DICE significantly outperforms the other MIS methods on environments, except for Humanoid, where GradientDICE achieves a comparable performance.
Hopper
Humanold
Time (Teb)
Time (Tad)
Time
Time
(1ads
SR-DICE
DuaIDICE
GradientDICE
Diract-SR
Behavior R(ms)
Figure 3: Off- pfl-colicy evaluation results on the continuous-actionn MuloCo domain using the "hard" experimental setting (50k time steps, ab 0.2, random actions with p 0.2). The shaded area captures standard deviation across 10 trials. This setting uses significantly fewer time steps than the "easy" setting and the behavior policy is poor estimate the target policy. Again, we see SR-DICE outperforms
MIS methods, demonstrating the benefits of our proposed decomposition and simpler optimization. This setting also shows the benefits of deep RL methods over MIS methods for OPE in high dimensional domains, deep TD performs the strongest in every environment.
Atari Experiments. We also test each method on several Atari games (Bellemare al. 2013), which are challenging due to their high-dimensional image-based state space. Standard pre- processing steps are applied (Castro et al. 2018) and sticky-actions are used (Machado et al. 201 to increase difficulty and remove determinism. Each method is trained on data set of one million time steps. The target policy the deterministic greedy policy trained by Double DQN (Van Hassell ct al. 2016 The behavior policy is the e-greedy policy with
0.1. We use discount factor of 0.99. Experiments are performed over seeds. Results are displayed in FFigure 4 Additional experiments with different behavior policies can be found in the supplementary material.
Discussion. Across the board we find SR-DICE significantly outperforms the MIS methods. From the MSE graphs, we can SR-DICE achieves much lower error in every task. Looking at the estimated values of R(T)) in the continuous-action environments, Figure 3, we can see that SR- DICE converges rapidly and maintains stable estimate, while the MIS methods are particularly unstable, especially in the case of DuaIDICE. These observations are consistent in the Atari domain FFigure 4). Overall, we find the general trend in performance is Deep TD SR-DICE Direct- SR MIS. Notably Direct-SR and SR-DICE perform similarly in every task, suggesting that the limiting factor in SR-DICE the quality of the deep successor representation.
Ablation. To study the robustness of SR-DICE relative to the competing methods, we perform an ablation study and investigate the effects of data set size, discount factor, and two different behavior policies. Unless specified otherwise, we use experimental settings matching the "hard" setting. We report the results in Figure 5) In the data set size experiment (a), SR-DICE perform well with as few 5k transitions (5 trajectories). In some instances, the performance is unexpectedly improved with less data, although incrementally. For small data sets, the SR methods outperform Deep TD. One hypothesis is that the encoding acts low data regime. In (b) we report the performance over changes in discount factor. The relative ordering across methods is unchanged. In (c) use behavior policy of (00 of), with o 0.5,
auxiliary reward and helps stabilize learning in the
8

---

Under review as a conference paper at ICLR 2021
Pong
Time stoza (165)
Time (te5)
Time (745)
Tima (Ted))
Time slapo (1c5)
SR-DICE
DuaiDICE
GradienDDIC
Direct-SR
Deep
Behavior RiTa)
We plot the log MSE for off-policy evaluation in the image-based Atari domain. The shaded area captures one standard deviation across 3 trials. We can see the MIS baselines diverge on this challenging vironment, while the remaining methods perform similarly. Perhaps surprisingly. baseline of using (())) from the behavior policy outperforms methods by a fairly significant margin. Al- though the estimates from deep RL methods are stable, they are biased, resulting in a higher MSE.
Figure 4:
most games, the naive
HallCheetah
HbllCheetah
HalfChestah
HaiCChettah
110 M00
TTanskionn
Diseourt
Time (Taf)
Timo
SR-DICE
DuaIDICE
+ GradientDICE
-
Direct-RR
-
Deep TD
Bohavior R(ms)
(a) Data set size
(b) Discount factor
y
(c) Increased noise
(d) Deterministic policies
Figure 5: Ablation study results for the HalfCheetah task. We default the "hard" setting wherever possible. Error bars and the shaded area captures one standard deviation over 10 trials. (a) We vary the size of the data set D. (b) We vary the discount factor y. (c) We use new behavior policy with (00 af) noise with og = 0.5. (d) We use the same deterministic behavior and target policy.
a much larger standard deviation than either setting for continuous control. The results are similar the original setting, with an increased bias on the deep RL methods. In (d) we use the underlying deterministic policy as both the behavior and target policy. The baseline MIS methods perform surprisingly poorly, once again demonstrating their weakness on harder domains.
6 CONCLUSION
In this paper, introduce a method which can perform marginalized importance sampling (MIS) using the successor representation (SR) the target policy. This is achieved by deriving an MIS formulation that can be viewed reward function optimization. By using the SR, we effectively disentangle the dynamics of the environment from learning the reward function. This allows us to (a) use well-known deep RL methods to effectively learn the SR in challenging domains (Mnih al., 2015 Kulkarni et al. 2016) and (b) provide a straightforward loss function to learn the density ratios without any optimization tricks necessary for previous methods (Liu et al.) 2018 Uehara Jiang 2019 Nachum et al. 2019a; Zhang et al. 2020c). This reward function interpretation also provides insight into prior MIS methods by showing how they are connected value-basee methods. Our resulting algorithm, SR-DICE, outperforms prior MIS methods in terms of both performance and stability and is the first MIS method which demonstrably scales to high-dimensional problems.
As a secondary finding, our benchmarking shows that current MIS methods underperform more traditional value-based methods at OPE on high-dimensional tasks, suggesting that for practical applications, deep RL approaches should still be preferred. Regardless, outside of OPE there exists a wealth of possible applications for MIS ratios, from imitation (Kostrikov et al. 2019) to policy optimization (Imani al. 2018 Liu al. 2019b] Zhang et al. 2019) to mitigating distributional shift in offline RL (Fujimoto et al, 2019b Kumar et al.] 2019). For ease of use, our code is provided, and hope algorithm and insight will provide valuable contributions to the field.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
André Barreto, Will Dabney, Rémi Munos, Jonathan J Hunt, Tom Schaul, Hado van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. In Advances in neural information processing systems, pp. 4055-4065 2017.
Andre Barreto, Diana Borsa, John Quan, Tom Schaul, David Silver, Matteo Hessel, Daniel Mankowitz, Augustin Zidek, and Remi Munos. Transfer in deep reinforcement learning using successor features and generalised policy improvement. In International Conference on Machine Learning, pp. 501-510, 2018.
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Richard Bellman. Dynamic Programming. Princeton University Press, 1957.
Dimitri P Bertsekas and John N. Tsitsiklis. Neuro-Dynanic Programming. Athena scientific Bel- mont, MA, 1996.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym, 2016.
Pablo Samuel Castro, Subhodeep Moitra, Carles Gelada, Saurabh Kumar, and Mare G Belle- mare. Dopamine: A research framework for deep reinforcement learning. arXiv preprint arXiv: 1812.06/1/ 2018.
Peter Dayan. Improving generalization for temporal difference learning: The successor representa- tion. Neural Computation, 5(4.))) 624, 1993.
Miroslav Dudik, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In Proceedings of the 28th International Conference on International Conference on Machine Learning, pp. 1097-1104, 2011.
Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off- evaluation. In International Conference Machine Learning, pp. 1447-1456, 2018.
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In International Conference on Machine Learning, volume 80, pp. 1587- 1596. PMLR. 2018.
Scott Fujimoto, Edoardo Conti, Mohammad Ghavamzadeh, and Joelle Pineau. Benchmarking batch deep reinforcement learning algorithms. arXiv preprint 1r100:1910.01708, 2019a.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pp. 2052-2062, 2019b.
Jason Gauci, Edoardo Conti, Yitao Liang, Kittipat Virochsiri, Yuchen He, Zachary Kaden, Vivek Narayanan, Xiaohui Ye, Zhengxing Chen, and Scott Fujimoto. Horizon: Facebook's open source applied reinforcement learning platform. arXiv preprint 1xXv:1811.00026) 2018.
Carles Gelada and Mare G Bellemare. Off-policy deep reinforcement learning by bootstrapping the covariate shift. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp- 3647-3655, 2019.
Samuel Gershman. The successor representation: its computational logic and neural substrates. Journal of Neuroscience, 38(33):7193-7200 2018.
Samuel Gershman, Christopher D Moore, Michael T Todd, Kenneth A Norman, and Per B Seder- berg. The successor representation and temporal context. Neural Computation, 1553)115331,568, 2012.
10

---

Under review as a conference paper at ICLR 2021
Christopher Grimm, Irina Higgins, Andre Barreto, Denis Teplyashin, Markus Wulfmeier, Tim Her- tweck, Raia Hadsell, and Satinder Singh. Disentangled cumulants help successor representations transfer to new tasks. arXiv preprint arXiv:
2019.
Assaf Hallak and Shie Mannor. Consistent on-line off-policy evaluation. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1372-1383. JMLR. org. 2017.
Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. arXiv preprint arXiv: 1rXiv:7110.02966 2017.
Ehsan Imani, Eric Graves, and Martha White. An off- off-policy policy gradient theorem using emphatic weightings. In Advances in Neural Information Processing Systems, pp. 96-106, 2018.
David Janz, Jiri Hron, Przemystaw Mazur, Katja Hofmann, José Miguel Hernández-Lobato, and Se- bastian Tschiatschek. Successor uncertainties: exploration and uncertainty in temporal difference learning. In Advances in Neural Information Processing Systems, pp. 4509-4518, 2019.
Nan Jiang and Lihong Li. Doubly robust off- off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning, pp. 652-661, 2016
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 11Xiv:1412.6980, 2014.
Ilya Kostrikov, Ofir Nachum, and Jonathan Tompson. Imitation learning via off-policy distribution matching, arXiv preprini arXiv: 191200521, 2019.
Tejas D Kulkarni, Ardavan Saeedi, Simanta Gautam, and Samuel J Gershman. Deep successor reinforcement learning. arXiv preprint 160. 2016.
Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. Advances in Neural Information Processing Sys- tems, pp. 11784-1111 11794, 2019.
Timothée Lesort, Natalia Díaz- Diaz-Rodríguez Jean-Franois Goudou, and David Filliat. State represen- tation learning for control: An overview. Neural Networks, 108:379-392, 2018.
Lihong Li, Remi Munos, and Csaba Szepesvari. Toward minimax off-policy value estimation. In Artificial Intelligence and Statistics, pp. 608-616, 2015.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: (tt::::5000000000 2015.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off- off-policy estimation. In Advances in Neural Information Processing Systems, pp. 5356- 5366, 2018
Yao Liu, Pierre-Lue Bacon, and Emma Brunskill. Understanding the curse of horizon in off-cy evaluation via conditional importance sampling. arXiv preprint arXiv:1910.0653 2019a.
Yao Liu, Adith Swaminathan, Alckh Agarwal, and Emma Brunskill. Off-policy policy gradient with 2019b.
state distribution correction. arXiv preprint
Marlos C Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray
Campbell. Eigenoption discovery through the deep successor representation. arXiv preprint arXiv:1710.11089, 2017.
Marlos C Machado, Mare Bellemare, and Michael Bowling. Count-based exploration with the successor representation. arXiv preprint arXiv:/807.1 1622, 2018a.
Marlos C Machado, Mare G Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and Michael Bowling. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61:523-562, 201 8b.

---

Under review as a conference paper at ICLR 2021
Ashique Rupam Mahmood, Huizhen Yu, and Richard S Sutton. Multi-step off- polippolyy learning with- out importance sampling ratios. arXiv preprint arXiv: 2017.
Travis Mandel, Yun-En Liu, Sergey Levine, Emma Brunskill, and Zoran Popovic. Offline policy evaluation across representations with applications educational games. In International Con- ference on Autonomous Agents and Multiagent Systems, 2014.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, Nature, 518(7540):529 533-333, 2015.
Ida Momennejad, Evan M Russek, Jin H Cheong, Matthew M Botvinick. Nathaniel Douglass Daw, and Samuel J Gershman. The successor representation in human reinforcement learning. Nature Human Behaviour, 1(9):600699) 2017.
Ali Mousavi, Lihong Li, Qiang Liu, and Denny Zhou. Black-box off-policy estimation for infinite- horizon reinforcement learning. arXiv preprint arXiv:2003. 20l::2003.//2000 2020.
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and efficient off-policy reinforcement learning. Advances in Neural Information Processing Systems, pp. 1054-1062, 2016.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, pp. 2315-2325, 2019a.
Ofir Nachum, Bo Dai, Ily Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Algaedice: 2019b.
Policy gradient from arbitrary experience. arXiv preprini
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems, pp- 8024-8033 2019.
Doina Precup, Richard S Sutton, and Sanjoy Dasgupta. Off-policy temporal-difference learning with function approximation. In International Conference Machine Learning, pp. 417-424, 2001.
R Tyrrell Rockafellar. Convex analysis. Princeton university press, 1970.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In International Conference on Learning Representations, Puerto Rico, 2016.
Samarth Sinha, Jiaming Song, Animesh Garg, and Stefano Ermon. Experience replay with likelihood-free importance weights. arXiv preprint arXiv:2006.131 13169, 2020.
Richard Sutton and Andrew Barto. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998.
Richard S Sutton and Brian Tanner. Temporal -ifffrrreld networks. In Advances in neural informa- tion processing systems, pp. 1377-1384, 2005.
Richard S Sutton, Hamid Reza Maei, Doina Precup. Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for temporal-difference learn- ing with linear function approximation. In International Conference on Machine Learning, pp. 993-1000. ACM, 2009.
Richard S Sutton, Joseph Modayil, Michael Delp. Thomas Degris, Patrick Pilarski, Adam White, and Doina Precup. Horde: scalable real-time architecture for learning knowledge from unsu- pervised sensorimotor interaction. The 10th International Conference on Autonomous Agents and Multiagent Voolum 2, pp. 761-768, 2011.
Richard Sutton, A Rupam Mahmood, and Martha White. An emphatic approach the problem of off-policy temporal-diiie -iffereneee learning. The Journal of Machine Learning Research, 17(1): 2603-2631, 2016.
12

---

Under review as a conference paper at ICLR 2021
Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miro Dudik, John Langford, Damien Jose, and Imed Zitouni. Off-policy evaluation for slate recommendation. In Advances in Neural Information Processing Systems, pp. 3632-3642, 2017.
Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference on Machine Learning, pp. 2139-2148, 2016.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In JEEE/RS/ International Conference on Intelligent Robots and Systems (IROS), pp. 5033.. IEEE, 2012.
Ahmed Touati, Amy Zhang, Joelle Pineau, and Pascal Vincent. Stable policy optimization via off- policy divergence regularization. arXiv preprint arXiv:2003.04103 2020.
Masatoshi Uchara and Nan Jiang. Minimax weight and q-function learning for off- off-policy evaluation. 2019.
arXiv preprint
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In AAAI, pp. 2094-2100, 2016.
Tao Wang, Michael Bowling, and Dale Schuurmans. Dual representations for dynamic programming and reinforcement learning. In 2007 IEEE International Symposium on Approximate Dynamic Programming and Reinforcement Learning, pp. 44-51. IEEE, 2007.
Tao Wang, Michael Bowling, Dale Schuurmans, and Daniel Lizotte. Stable dual dynamic pro- gramming. In Advances in neural information processing systems, pp. 1569-1576, 2008.
Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudík. Optimal and adaptive off-policy evaluation in contextual bandits. In International Conference on Machine Learning, pp. 3589-3597, 2017.
Eric Wiewiora, Garrison W Cottrell, and Charles Elkan. Principled methods for advising reinforce- ment learning agents. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 792-799, 2003.
Tengyang Xie. Yifei Ma, and Yu-Xiang Wang. Towards optimal off off-policy evaluation for rein- forcement learning with marginalized importance sampling. In Advances in Neural Information Processing Systems, pp. 9665-9675, 2019.
Jingwei Zhang, Jost Tobias Springenberg, Joschka Boedecker, and Wolfram Burgard. Deep rein- forcement learning with successor features for navigation across similar environments. 20/7 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2371-2378 IEEE, 2017.
Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. Gendice: Generalized offline estimation of stationary values. arXiv preprint arXiv:2002.09072, 2020a.
Shangtong Zhang, Wendelin Boehmer, and Shimon Whiteson. Generalized off- off-policy actor-critic. 2019.
In Advances in Neural Information Processing Systems, pp.
Shangtong Zhang, Wendelin Bochmer, and Shimon Whiteson. Deep residual reinforcement learn- ing. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1611-1619, 2020b.
Shangtong Zhang, Bo Liu, and Shimon Whiteson. Gradientdice: Rethinking generalized offline estimation of stationary values. arXiv preprint arXiv:2001.1111: 2020c.
Yufan Zhao, Michael R Kosorok, and Donglin Zeng, Reinforcement learning design for cancer clinical trials. Statistics in medicine, 28(26):3294, 2009.
Yuke Zhu, Daniel Gordon, Erie Kolve, Dieter Fox, Fei-Fei, Abhinav Gupta, Roozbeh Mottaghi, and Ali Farhadi. Visual semantic planning using deep successor representations. In Proceedings of the IEEE International Conference on Computer Vision, pp. 483-492, 2017.
13

---

Under review as a conference paper at ICLR 2021
A DETAILED PROOFS.
A.1 OBSERVATION 1
Observation 1 The objective (f) is minimized when f(s,a) = (s.aa
(x,aj V(s, a).
min J(P) = E (o,a) [f(s, - (1-7)BBoooa (8) ((s,a)((e,o)
(14)
2
R (saaadd [[(s,a)]] (aaaaaer [f(s
(15)
Proof.
Take the partial derivative of J(f) with respect f(s,
0 @f(s, a)
E [F(s, a) (( (((,,))) -) -
-d" (s)
(16)
Then setting 0J(F) pairs (8, a).
0, we have that J(f) is minimized when f(s, a) = d=(s.a) (=
for all acttnnaction
8F(a,a)
A.2 THEOREM
Theorem Assuming (1 - Een [bb (su, ad)l = E(erayaa [6(s, a)}, then the optimizer w of
the objective J(W) is the least squares estimator of ISXA (w ((8,8)) d (x.0) 2
(0,00) d(s,a).
min J(w) = 1 Eyo [(wTo(s,a)) a)s - (1 B Bo [w (so, (s0,
(17)
Proof.
From our assumption we have:
1 min J(w) = 2 EaD (o(,a))))
(a [w ((s, a(s,
(18)
Let S] |A| and N be the feature dimension. Let Φ(s, a) be x 1 feature vector and the M x N matrix where each row corresponds to ods, a) vector. Let be N x 1 vector of parameters. Let d, and dp be M x 1 vectors of the values of d' a) and dd PPss a) for all (s,
First note the least squares estimator of SSXA ( ((s
(s.o) ()(,,))
d(s, a) @w
du is
dp
w -T TT where the division element-wise.
Now consider our optimization problem:
J(w) 0.5d (Tw) d. tw
= 0.5d (dd) vow - d ow
(19)
= 0.5d "O= ow d dw.
14

---

Under review as a conference paper at ICLR 2021
Now take gradient of J(w) with respect to and set equal to 0:
w x" ow d tw
dow x" $
d dd."
dp
w "
dp
(20)
dx
T vw = ①
dp
w (T 14 dx
dp
follows that the optimizer to J(w) ) is the least squares estimator.
A.3 THEOREM
Theorem Given an MDP reward function r 8 A + R as f(s, a) f(s,a))=BBB, aa (f(ss d')}. Then it follows that the value function Q"T defined by the policy n. MDP, and reward function is the function f.
7), policy æ, function f S - R, define the
Proof.
Define f(s, a) = (f a')]. Then note for all state-action pairs (s, a) we have f(s. = f(s, a) + ,')] f(s, a)
+E a')] = f(s a), satisfying the Bellman equation. It follows that f = Q by the uniqueness of the value function (Bertsekas & Tsitsiklis 1996).
This result can also be obtained by considering state-action reward shaping (Wiewiora et al. 2003). and treating the potential function.
B TABULAR SR-DICE
The experimental performance of SR-DICE, in particular its reliance the SR can be partially explained by examining its tabular counterpart. In fact, we can show that the value estimate derived from SR-DICE is exactly equal to value estimate derived directly from the SR.
Recall the form of SR-DICE's objective in a tabular setting, as a function of the SR Th:
min (f)
1
B a)ss (1 EE
Σ T ("((ss (Fss
(21)
((s,o)V(s.a)
2
Which has the following gradient:
Vi(r.o) == -1. 1 (sla)))(())))))
(22)
We compute this gradient from samples. Define Do as the set of start states so E D. It follows:
(((s.a)Jv(F= = [D]
Σ
1 = =,a==' f(s,a)
(8' (''ED
(23)
1
(1 ?) Doo
("(s(so)=(aas))
Sp
15

---

Under review as a conference paper at ICLR 2021
Setting the above gradient to 0 and solving for f(s, a) we have the optimizer of Ju (f).
[
F(s, a) = (1 (1- 7) [Pol
Σ
("(s)so)<(aas)
(24)
Σ
(dd'a 1 8, a = a)
e0
Now consider the MIS equation for estimating the objective R(x) = 20 [V*(so)) where an estimate of d (s.a).
[s,aa]
d' (s, d (s (s,
(25)
D
(S,0)ED
For convenience, assume every state-action pair (s, a) is contained at least once D. Although the result holds regardless. this assumption allows to avoid some cumbersome details. Replace d' (a.a) with é in Equation (25) and expand and simplify:
(a.a)
D
?)
Σ Do
('(sss))r(aas))
as)
(26)
[Pol
E(d 1 s,a' a)
(K,0)ED
= =11 7) PDol
Σ
('(s(so)7(aa1))
E(sranED 1(s' = a' = a) T(,
(27)
#pED (M.)ED
= (1 7)
Σ
(28)
Do
#pEDo (s.))SxA
Noting that E(EO) V (s(lss))(((s))r(( a) V=(su) we can see that SR-DICE returns the same solution as the SR solution for estimating R(T).
C ADDITIONAL EXPERIMENTS
In this section, we include additional experiments and visualizations, covering extra domains, addi- tional ablation studies, run time experiments and additional behavior policies in the Atari domain.
C.I EXTRA CONTINUOUS DOMAINS
Although our focus is on high-dimensional domains, the environments, Pendulum and Reacher, have appeared in several related MIS papers (Nachum et al. 2019a Zhang al. [202aa). Therefore, we have included results for these domains in Figure All experimental settings match the experiments in the main body, and are described fully in Appendix
Pendulum
Reacher
Pendukum
Reacher
Time stoss (1o5)
Time stops (165)
Time stopo (1:5)
Time stope (105)
(a) "Easy" setting
"Hard" setting
DI-DICE
DuaIDICE
- GradienDDICE
- Direct-SR
Deep TD
Behavior R(ms)
Figure 6: Off-policy evaluation results for Pendulum and Reacher. The shaded area captures standard deviation across trials. Even on these easier environment, we find that SR-DICE outperforms baseline MIS methods.
16

---

Under review as a conference paper at ICLR 2021
C.2 REPRESENTATION LEARNING & MIS
SR-DICE relies disentangled representation learning phase where an encoding e is learned, fol- lowed by the deep successor representation प. which are used with linear vector estimate the density ratios. In this section we perform some experiments which attempt to evaluate the im- portance of representation learning by comparing their influence on the baseline MIS methods.
Alternate representations. We examine both DualDICE (Nachum et al., 2019a) and GradientDICE (Zhang et al. (020c) under four settings where we pass the representations and R to their networks, where both @ and x/ are learned in identical fashion to SR-DICE.
(1) Input encoding
f(o(s.a)) (s,),,,)),,
w(o(s,)))
(2) Input SR 2b",
w(t" (s)a).
(3) Input encoding &. linear networks,
a))
w (s,
(4) Input SR vb" linear networks,
f (s,
w (s,a).
See Appendix for specific details on the baselines. We report the results in Figure For GradientDICE, no benefit is provided by varying the representations, although using the encoding matches the performance of vanilla GradientDiCE regardless of the choice of network, providing some validation that 6 is reasonable encoding. Interestingly, for DuaIDICE. gains from using the SR &² as a representation: slightly as input, but significantly when used with linear networks. On the other hand, as GradientDICE performs much worse with the SR, it is clear that the SR cannot be used as a representation without some degree of forethought.
performance
Lop rese
Time (1)))
Time stops (fef)
Time (1u5)
Time (145)
DIIDICE
DuaIDICE
-4- GradientDICE
Encoding+X
Behavior
(a) DuaIDICE
(b) Linear DuaIDICE
(c) GradienDDICE
(d) Linear GradienDDICE
Figure 7: Off-policy evaluation results on HalfCheetah examining value differing representations added to the baseline MIS methods. The experimental setting corresponds to the "hard" setting from the main body. The shaded area captures one standard deviation across 10 trials. We see that using the SR ai as a represen- tation improves the performance of DuaIDICF. On the other hand, GradienDDCC performs much worse when using the SR, suggesting it cannot be used naively improve MIS methods.
Increased capacity. As SR-DICE uses a linear function on top of representation trained with the same capacity as the networks in DualDICE and GradientDICE, our next experiment examines if this additional capacity provides benefit to the baseline methods. To do, we expand each network in both baselines by adding an additional hidden layer. The results are reported in Figure We find there is a very slight decrease in performance when using the larger capacity networks. This suggests the performance gap from SR-DICE over the baseline methods has little do with model size.
HaffCheasthh
1952
DiaIDICE
GradienDDICE
Big DusIDICE
GradienIDICE
Beltvior Rim)
Figure 8: Off- Off-policy evaluation results on HalfCheetah evaluating the performance benefits from larger network capacity on the baseline MIS methods. "Big" refers to the models with an additional hidden layer. The exper- imental setting corresponds the "hard" setting from the main body. The shaded area captures standard deviation across trials. We find that there is no clear performance benefit from increasing network capacity.
17

---

Under review as a conference paper at ICLR 2021
C.3 TOY DOMAINS
We additional test the MIS algorithms on toy random-walk experiment with varying feature repre- sentations, based domain from (Sutton al. 2009).
Domain. The domain a simple 5-state MDP (41, R2; 43, T4, 25) with two actions (dg, a1), where action do induces the transition Hς + æ and action aj induces the transition x; + I4+11 with the state 21 looping to itself with action do and æ5 looping to itself with action 05. Episodes begin in the state 21.
Target. We evaluate policy æ which selects actions uniformly, i.e, (aul)z)) 22;) = <aa = 0.5 for all states zς- Our data set D contains all 10 possible state-action pairs and is sampled uniformly. We use discount factor of = 0.99. Methods are evaluated on the average MSE between their estimate of d' ze on all state-action pairs and the ground-trui truth value, which is calculated analytically.
Hypper-arameters. Since we are mainly interested in function approximation setting, each method uses a small neural network with two hidden layers of 32, followed by tanh activation functions. All networks used stochastic gradient descent with a learning rate a tuned for each method out of (1, 0.5, 0.1, 0.05, 0.01, 0.001]. This resulted in for GradientDICF, and a = 0.05 for SR-DICE. Although there are a small number of possible data points, we use batch size of 128 to resemble the regular training procedure. As recommended by the authors we use = for GradientDICE (Zhang et al. 2020c), which was not tuned. For SR-DICE, we update the target network at every time step T which was not tuned.
0.05 for DualDICE,
= 0.1
Since there are only 10 possible state-action pairs, we use the closed form solution for the vector (Equation (10)). Additionally, skip the state representation phase of SR-DICE, instead learn- ing the SR 6 over the given representation of each state, such that the encoding ø = x. This allows variety of representations rather than using learned encoding. Conse-
us to test SR-DICE quently, with these choices, SR-DICE has no pre-training phase, and therefore, unlike every other graph in this paper, we report the results as the SR is trained, rather than the vector is trained.
Features. To test the robustness of each method we examine three versions of the toy domain, each using a different feature representation over the same 5-state MDP. These feature sets are again taken from (Sutton et al., 2009).
Tabular features: states are represented by one-hot encoding, for example z [0, 1, 0, 0, 0). Inverted features: states are represented by the inverse of one-hot encoding, for example 22 1. 0, 1 1].
2:
Dependent features: states are represented by 3 features which is not sufficient to cover all states
exactly. In this case x = [1, 0, 0). x2 = 1// -/2 0]. x3 1/2 73 / X4 = [0, - + = [0, 0, 1]. Since our experiments use neural networks rather than linear functions, this representation is mainly meant to test SR-DICE, where we skip the state representation phase for SR-DICE and use the encoding x, limiting the representation of the SR.
Tabular Features
Inverted Features
Dependent Features
Time stepx (1a4)
Time stape (1e4)
Time (7o4)
SR.DICE
DuaiDICE
- Gradien
(a) Tabular Features
(b) Inverted Features
(c) Dependent Features
Figure 9: Results measuring the log MSE between the estimated density ratio and the ground-truth simple 5-state MDP domain with three feature sets. The shaded area captures one standard deviation across 10 trials. Results are evaluated every 100 time steps over 50k time steps total.
Results. We report the results in Figure 9 We remark several observations. SR-DICE learns significantly faster than the baseline methods, likely due to its use of temporal difference methods in the SR update, rather than using update similar residual learning, which is notoriously
18

---

Under review as a conference paper at ICLR 2021
Zhang et al. 2020b). GradientDICE appears still be improving, although limit training at 50k time steps, which we feel is sufficient given the domain is deterministic and only has 5 states. Notably, GradientDICE also uses higher learning rate than SR-DICE and DualDICE. We also find the final performance of SR-DICE is much better than DualDICE and GradientDICE in the domains where the feature representation is not partieularly destructive, highlighting the easier optimization of SR-DICE. In the case of the dependent features, we find DualDICE outperforms SR-DICE after sufficient updates. However, remark that this concern could likely be resolved by learning the features and that SR-DICE still outperforms GradientDICE. Overall, we believe these results demonstrate that SR-DICE's strong empirical performance consistent across simpler domains well as the high dimensional domains we examine in the main body.
slow (Baird 1995
C.4 RUN TIME EXPERIMENTS
In this section, we evaluate the run time of each algorithm used in our experiments. Although SR- DICE relies on pre-training the deep successor representation before learning the density ratios, find each marginalized importance sampling (MIS) method uses a similar amount of compute, due to the reduced cost of training after the pre-training phase.
We evaluate the run time on the HalfCheetah environment in MuJoCo (Todorov et al. 2012) and OpenAl gym (Brockman al. 2016). As in the main set of experiments, each method is trained for 250k time steps. Additionally, y, SR-DICE and Direct-SR train the encoder-decoder for 30k time steps and the deep successor representation for 100k time steps before training w. Run time is averaged over 3 seeds. All time-basee based experiments are run on a single GeForce GTX 1080 GPU and a Intel Core 17-6700K CPU. Results are reported Figure
40
40
Time (minutes)
10
SR-DICE
DuaiDICE
GradienIDICE
Direc-SR
Deep TD
The average run time of each off-policy evaluation approach in minutes. Fach experiment is run for 250k time steps and averaged over seeds. SR-DICE and Direct-SR pre-train encoder-decoder for 30k time steps and the deep successor representation 100k time steps.
Figure 10:
We find the MIS algorithms run in comparable time, regardless of the pre-training step involved in SR-DICE. This can be explained as training w in SR-DICE involves significantly less compute than DualDICE and GradientDICE which update multiple networks. On the other hand, the deep reinforcement learning approaches run in about half the time of SR-DICE.
C.5 ATARI EXPERIMENTS
To better evaluate the algorithms in the Atari domain, we run two additional experiments where we swap the behavior policy. We observe similar trends as the experiments in the main body of the paper. In both experiments we keep all other settings fixed. Notably, we continue use the same target policy, corresponding the greedy policy trained by Double DQN (Van Hasselt al. 2016 the same discount factor = 0.99, and the same data set size million.
Increased noise. In our first experiment, we attempt to increase the randomness of the behavior policy. As this can cause destructive behavior in the performance of the agent, we adopt an episode- dependent policy which selects between the noisy policy the deterministic greedy policy the beginning of each episode. This is motivated by the offline deep reinforcement learning experiments from (Fujimoto al. 2019a). As result, use e-greedy policy with p 0.8 and the deter-
19

---

Under review as a conference paper at ICLR 2021
ministic greedy policy (the target policy) with p 0.2. is set to 0.2, rather than 0.1 in the experiments in the main body of the paper. Results are reported in Figure II
Adflettt
BisinRider
Brankout
Knull
Pong
sbace (196)
Time prr..cepe.ooo (WdS)
Time drape (145)
Tirs (Twc)
Time campe (1ad)
SR-DICE
DuaIDICE
-+- GradientDICE
-X- DirectSRR
Deep TD
mme Behavior R(as)
Figure 11: plot the log MSE off- policy evaluation the image-basee Atari domain, using an episode- dependent noisy policy, where = 0.2 with p = 0.8 and = 0 with p 0.2. This episode-dependent selection ensures sufficient state-coverage while using stochastic policy. The shaded area captures one standard devia- tion across trials. Markers are not placed every point for visual clarity.
We observe very similar trends to the original set of experiments. Again, note DuaIDICE and GradientDICE perform very poorly, while SR-DICE, Direct-SR, and Deep TD achieve reasonable, but biased, performance. In this setting, still find the behavior policy is the closest estimate of the true value of R(T).
Separate behavior policy. In this experiment, policy, rather than simply adding noise. This behavior policy derived from an agent trained with prioritized experience replay and Double DQN (Schaul al. 2016). Again, we use e-greedy policy, with = 0.1. We report the results in Figure 12
behavior which is distinct from the target
Beamiildr
Breakcut
Knull
Time stoce (Te))
Time stape Dadd
Time stapa (145)
Time stesa (Ted)
Time staps (1ets
SR.DICE
DuaIDICE
- GradienDDICE
- Direct-SR
- Deep TD
Behavior R(mn)
We plot the log MSE for off- off-policy evaluation in the image- based Atari domain, using a distinct behavior policy, trained by a separate algorithm, from the target policy. This experiment tests the ability to generalize to more off-polla fff-policy setting. The shaded area captures one standard deviation across 3 trials. Markers placed every point for visual clarity.
Figure 12:
Again, we observe similar trends in performance. Notably, in the Asterix game, the performance of Direct-SR surpasses the behavior policy. suggesting off off-policy evaluation can outperform the naïve estimator settings where the policy sufficiently "off-policy" and distinct.
D SR-DICE PRACTICAL DETAILS
In this section, we cover some basic implementation--lvell details of SR-DICE. Note that code is provided for additional clarity.
SR-DICE uses two parametric networks, an encoder-decoder network learn the encoding o and a deep successor representation network पे Additionally, SR-DICE uses the weights of linear function SR-DICE begins by pre-training the encoder-decoder network and the deep successor representation before applying updates to w.
Encoder-Decoder. This mecoerr-decodee network encodes (s, a. the feature vector ő(s, a), which then decoded by several decoder heads. For the Atari domain, we choose to condition the feature vector only states ((s), the reward is generally independent of the action selection. This
20

---

Under review as a conference paper at ICLR 2021
Algorithm 2 SR-DICE
1: Input: Data set D, target policy number of iterations 71, T2, T3, mini-batch size N, tar- get pet.update_rad rate.
2: for 1= 1 to Ti do
3:
Sample mini-bated of N transitions (s. a, r, s')) from D.
4:
mingDD,,,D. D. (Dx (o(s,)) a)) =
Train encoder- decoder
+>a (Da((aa a)) a)² + (D,(((((s - r)
5: end for
6: for ( 1 to T2 do
7: Sample mini-batch of transitions (8, a, 8,)) from D.
8: Sample a' a(s)..
Train deep
9: ming (Ø(s, a) + ri''ss' a') 10 (s,
successor representation
I mod
rate 0: of t v.
11: end for
12:
for 4= to T3 do
13: Sample mini-bate of transitions (s, a, r, s') from D.
14: Sample mini-batch of N start states so from D.
15: Sample Og ~ (5)).
Learn w
16: minw (wTd(s, a))
>)w' 1h (80, ap).
17: end for
change applies both SR-DICE and Direct-SR. Most design decisions are inspired by prior work Machadd et al.) 2017: 2018a).
For continuous control, given a mini-batch transition (s, a, s'), the encoder-decoder network is trained to map the state-action pair (s, a) to the next state s', the action and reward r. The resulting loss function is as follows:
min D) (D. s') (,(o((((s.))) a)² (,(D(o(ss,a) rr -r)
D..
(29)
We use A.r 1, and X, 0.1.
For the Atari games, given mini-batch transition (s, a, T, s'), the decoder network is trained map the state s to the next state s' and reward r, while penalizing the size of ((s). The resulting loss function is as follows:
min D,
C D) = Av (Dx((((s) - 8') *r((D.(((s)) - r)2 Aao(1))
(30)
We use A.' = 1, X, = 0.1 and A = 0.1.
Deep Successor Representation. The deep successor representation e¹ is trained estimate the accumulation of ø. The training procedure resembles standard deep reinforcement learning algo- rithms. Given mini-batch of transitions (8, a, r,)') 8') the network is trained minimize the following loss:
min C(bb*) == (ø(s, a) + mp (s', a') 3 (s, 1ia
(31)
where v is the target network. A target network a frozen network used provide stability (Mnih) et al. 2015 Kulkarni et al., 2016) in the learning target. The target network is updated to the current
network f- 15 after fixed number of time steps, or updated with slowly at each time step v// +- T +(1 = (Lillicrap et al. 2015).
Marginalized Importance Sampling Weights. described in the main body, we learn by optimizing the following objective:
1
min ((w) = B(s.aaaaD (wT, - -(1 Eno [ TT (su, ao)) w
(32)
21

---

Under review as a conference paper at ICLR 2021
This is achieved by sampling state-action pairs uniformly from the data set D, alongside mini-batch of start states so, which are recorded at the beginning of each episode during data collection.
We summarize the learning procedure of SR-DICE in Algorithm 2
E BASELINES
In this section, we cover some the practical details of each of the baseline methods.
E. DUALDICE
Dual stationary DIstribution Correction Estimation (DuaIDICE) NNachum al. 2019a) uses two networks f and w. The general optimization problem is defined as follows:
min max J w) E (s,a) (s..))- ,a [w af 7f(s', a')) 0.5w a)
(33)
(1 7) Bo [f(*0 ao]]-
In practice this corresponds to alternating single gradient updates to f and to. The authors suggest possible alternative functions to the convex function 0.5w(s, a)² such as gl a)l however in practice we found O. (s, a)² performed the best.
E.2 GRADIENTDICE
Gradient stationary DIstribution Correction Estimation (GradientDICE) (Zhang et al. 2020c) uses two networks f and and a scalar u. The general optimization problem is defined as follows:
min max (ww f) = (1 ao (Su. ao)l + 7 at ox (w(s, f)
B(s.a)- /w fs, a)] + A (B(r,))=ap (s a) u| - 0.5u
(34)
Similarly DualDICE, in practice this involves alternating single gradient updates to w. and f. As suggested by the authors we use À =
E.3 DIRECT-SR
Direct-SR is policy evaluation version of deep successor representation (Kulkarni et al. 2016). The encoder-decoder network and deep successor representation are trained in the exact same manner as SR-DICE (see Section D). Then, rather than train w learn the marginalized importance sam- pling ratios, w is trained to recover the original reward function. Given a mini-batch of transitions (s, a, s'), the following loss is applied:
min L(w) = (r w (TT(ssa))2
(35)
E.4
DEEP TD
Deep TD, short for deep temporal-differte ing methodology, akin to DQN (Mnih et al. 2015), and applies it to off-policy evaluation. Given mini-batch transitions (s, a, r, 8') the Q-network is updated by the following loss:
learning, takes the standard deep reinforcement learn-
min L(Q") = (r (''ss', (s'(''')) Q as) Q"
(36)
where a' is sampled from the target policy T-Iss). Similarly, to training the deep successor repre- sentation, Q' is frozen target network which is updated to the current network after a fixed number of time steps, or incrementally at every time step.
F EXPERIMENTAL DETAILS
All networks are trained with Py Torch (version 1.4.0) (Paszke et al. 2019). Any unspecified hyper- parameter uses the PyTorch default setting.
22

---

Under review as a conference paper at ICLR 2021
Evaluation. The marginalized importance sampling methods measured by the average weighted reward from transitions sampled from a replay buffer I E(sa.r) w(s, a)r(s, a), with N = 10k,
while the deep RL methods use (1-م Σ Q(so, ग (an)), where M the number of episodes. Each OPE method is trained data collected by some behavioral policy mb- We estimate the "true" normalized average discounted reward of the target and behavior policies from 100 roll-outs in the environment.
F.1 CONTINUOUS- ACTION ENVIRONMENTS
Our agents are evaluated via tasks interfaced through OpenAl gym (version 0. 0.1..2) (Brockman et al. 2016 which mainly rely on the MuloCo simulator (mujoco-py version 1.50.1.68) (Todorov et al,
2012
We provide description of cach environment in Table 1
Table
Continuous-actio -cciioonouu-iooonnoooo environment descriptions.
Environment
State dim.
Action dim.
Episode Horizon
Task description
Pendulum-vO
3
1
200
Balance a pendulum.
Reacher-v2
11
2
50
Move end effector to goal.
HalfCheetah-v3
17
1000
Locomotion.
Hopper-v3
11
3
1000
Locomotion.
Walker2d-v3
17
1000
Locomotion.
Ant-v3
111
8
1000
Locomotion.
Humanoid-v3
376
17
1000
Locomotion.
Experiments. Our experiments are framed as off-policy evaluation tasks in which agents aim to evaluate R(T) ((..a)=d".r (r((s) a)] for some target policy и. In each of our experiments, cor- responds to a noisy version of policy trained by TD3 agent (Fujimoto al., 2018). a commonly used deep reinforcement learning algorithm. Denote wa, the deterministic policy trained by TD3 using the author's GitHub https: //g /gi thub www..coooooocc....ooommom..oo.oo sfujim/// m/T33 The target policy is defined data set
(0, o²). where 0.1. The off-policy evaluation algorithms generated by a single behavior policy тy- The experiments are done with two settings "casy" and "hard" which vary the behavior policy and the size of the data set. All other settings are kept fixed. For the "easy" setting the behavior policy is defined as:
trained
+ NO, (0,, o,),a, = 0.133.
(37)
and 500k time steps collected (approximately 500 trajectories for most tasks). The "easy" setting roughly based on the experimental setting from Zhang et al. (2020a). For "hard" setting the behavior policy adds increased noise and selects random actions with p 0.2:
ा. + ((0, = 0.2 p p==0a 0.8,
(38)
Uniform random action p 0.2,
and only 50k time steps are collected (upproximately 50 trajectories for most tasks). For Pendulum-
v0 and Humanoid-v3, the range of actions is [-2, 2] and [-0.4, 0.4) respectively, rather than [-1,1]. so we scale the size of the noise added to actions accordingly. We set the discount factor y 0.99. All continuous-action experiments are over 10 seeds.
Pre-training. Both SR-DICE and Direct-SR rely on pre-training the encoder-decoder and deep successor representation vb. These networks were trained for 30k and 100k time steps respectively. As noted Section C.4. even when including this pre-training step, both algorithm have a lower running time than DuaIDICE and GradienDDICE.
Architecture. For fair comparison, we use the same architecture for all algorithms except for DuaIDICE. This fully connected neural network with 2 hidden layers of 256 and ReLU activa- tion functions. This architecture was based on the network defined in the TD3 GitHub and was not tuned. For DuaIDICE, we found tanh activation functions improved stability over ReLU.
For SR-DICE and SR-Direct we use separate architecture for the encoder-decoder network. The encoder network with single hidden layer of 256, making each d(s, a) feature vector of 256.
23

---

Under review as a conference paper at ICLR 2021
There are three decoders for reward, action, and next state, respectively. For the action decoder and next state decoder we use a network with one hidden layer of 256. The reward decoder is a linear function of the encoding, without biases. All hidden layers are followed by ReLU activation functions.
Network hyper-parameters. All networks trained with the Adam optimizer (Kingma & Ba 2014). We use a learning rate of 3e-4, again based on TD3 for all networks except for GradientDICE, which we found required careful tuning to achieve reasonable performance. For GradientDICE we found a learning rate of le-5 for f and w, and le-2 for u achieved the highest performance. For DuaIDICE we chose the best performing learning rate out of {le - 2, - 3, 3e 4, 5e 5, le - 5). SR-DICE, Direct-SR and Deep TD were not tuned and use default paper-parameters from deep RI. algorithms. For training 1 and Q" for the deep reinforce- ment learning aspects of SR-DICE, Direct-SR and Deep TD we use mini-batch size of 256 and update the target networks using = 0.005, again based on TD3. For all MIS methods, we use a mini-batch size of 2048 as described by (Nachum et al. 2019a). We found SR-DICE and DualDICE succeeded with lower mini-batch sizes but did not test this in detail. All hyper-parameters are de- scribed in Table 2
Table 2: Continuous-action environment training hyper-parameters.
Hyper ppper-prreeeter
SR-DICE
DuaIDICE
Gradien(DICE
Direct-SR
Deep TD
Optimizer
Adam
Adam
Adam
Adam
Adam
Q Learning rate
3c 4
3c 4
3e 4
w Learning rate
3e
3e 4
Learning rate
5e 5
le 5
w Learning rate
5e 5
le 5
Learning rate
le 2
t Q" Mini-batch size
256
256
256
w, f, w, u, Mini-batch size
2048
2048
2048
2048
" Q Target update rate
0.005
0.005
0.005
Visualizations. We graph the log MSE between the estimate of R(T) and the true R(x), where the log MSE is computed as log 0.5(X R(T))². We smooth the learning curves over a uniform window of 10. Agents were evaluated every 1k time steps and performance is measured over 250k time steps total. Markers are displayed every 25k time steps with offset for visual clarity.
F.2 ATART
We interface with Atari by OpenAl gym (version 0. (Brockman et al. 2016), all agents use the NoFrameskip-v0 environments that include sticky actions with p = 0.25 Machado et al. 2018b)
Pre-processing, We use standard pre-processing steps based on Machado al. (2018) and Castro ctt al. (0018). We base our description on (Fujimoto al. 2019a), which our code is closely based We define the following:
Frame: output from the Arcade Learning Environment.
State: conventional notion of state in MDP.
Input: input to the network.
The standard pre- processing steps as follows:
Frame: gray-scaled and reduced to 84 x 84 pixels, tensor with shape (1, 84, 84).
State: the maximum pixel value over the most recent frames, tensor with shape (1, 84, 84).
Input: concatenation over the previous 4 states, tensor with shape (4, 84, 84).
The notion of time steps is applied to states, rather than frames, and functionally, the concept of frames can be abstracted away once pre- pro-procsssing has been applied to the environment.
The agent receives state every 4th frame and selects action, which is repeated for the following frames. If the environment terminates within these 4 frames, the state received will be the last frames before termination. For the first 3 time steps of an episode, the input, which considers the
24

---

Under review as a conference paper at ICLR 2021
previous 4 states, sets the non-existent states to all Os. An episode terminates after the game itself terminates, corresponding to multiple lives lost (which itself is deme-deenddent, or after 27k time steps (108k frames or 30 minutes in real time). Rewards clipped to be within range of [-1, 1].
Sticky actions are applied to the environment (Machado et al.) 2018b), where the action at taken at time step i, is set to the previously taken action 0ç-1 with = 0.25, regardless of the action selected by the agent. Note this replacement is abstracted away from the agent and data set. In other words, if the agent selects action a at state s, the transition stored will contain (s, a), regardless if is replaced by the previously taken action.
Experiments. For the main experiments we use behavior and target policy derived from Double DQN agent (Van Hasselt et al. (0116), a commonly used deep reinforcement learning algorithm. The behavior policy is an e-greedy policy with 0.1 and the target policy the greedy policy (i.e. c= 0). In Section C.5 we perform two additional experiments with a different behavior policy. Oth- erwise, all
are fixed across experiments. For each, the data set contains million transitions and uses a discount factor of y 0.99. Each experiment is evaluated over 3 seeds.
Pre-training. Both SR-DICE and Direct-SR rely on pre-training the encoder-decoder and deep successor representation vb. Similar to the continuous-action tasks, these networks were trained for 30k and 100k time steps respectively.
Architecture. We use the same architecture as most salue-based deep reinforcement learning al- gorithms for Atari, e.g. (Mnih et al. 2015; Van Hasselt et al., 2016; Schaul et al. 2016). This architecture is used for all networks, other than the encoder-decoder network, for fair comparison and was not tuned in any way.
The network has 3-layer convolutional neural network (CNN) followed by a fully connected net- work with a single hidden layer. As mentioned in pre- proccessssing the input to the network is a tensor with shape (4, 84, 84). The first layer of the CNN has kernel depth of 32 of size 8 x 8 and stride of 4. The second layer has a kernel depth of 32 of size 4 x 4 and a stride of 2. The third layer has a kernel depth of 64 of size 3 x and stride of 1. The output of the CNN is flattened to a vector of 3136 before being passed to the fully connected network. The fully connected network has a single hidden layer of 512. Each layer, other than the output layer, is followed by a ReLU activation function. The final layer of the network outputs |A| values where [A] is the number of actions.
The encoder-decoder used by SR-DICE and SR-Direct has slightly different architecture. The encoder is identical to the aforementioned architecture, except the final layer outputs the feature vector (bs) with 256 dimensions and is followed by a ReLU activation function. The next state decoder uses a single fully connected layer which transforms the vector of 256 to 3136 and then is passed through three transposed convolutional layers each mirroring the CNN. Hence, the first layer has kernel depth of 64, kernel size of 3 x 3 and stride of 1. The second layer has a kernll depth of 32, kernel size of 4 x 4 and a stride of 2. The final layer has a kernel depth of 32, kernel size of 8 x 8 and stride of 4. This maps to (1, 84, 84) tensor. All layers other than the final layer followed by ReI.U activation functions. Although the input uses a history of the four previous states, as mentioned in the pre-processing section, we only reconstruct the succeeding state without history. We do this because there is overlap in the history of the current input and the input corresponding to the next time step. The reward decoder a linear function without biases.
Network pypae-pprammttes. Our payeer-parameter choices are based on standard tyrer-parameters based largely on (Castro et al. 2018). All networks are trained with the Adam optimizer (Kingma & Ba 2014). We use learning rate of 6. 6.25e-5. Although not traditionally though of has hyper- parameter, in accordance to prior work, we modify e used by Adam be 1.5c-4. For w we use a learning rate of 3e-4 with the default setting of 1e-8. For we use 1e-3. We use a mini-batch size of 32 for all networks. SR-DICE, Direct-SR and Deep TD update the target network every 8k are described in Table 3
time steps. All
Visualizations. We use identical visualizations to the continuous-action environments. Graphs display the log MSE between the estimate of R(T)) and the true R(T) of the target policy, where the log MSE is computed as log 0.5(X - R²z))². We smooth the learning curves over a uniform window of 10. Agents were evaluated every 1k time steps and performance is measured over 250k time steps total. Markers are displayed every 25k time steps with offset for visual clarity.
25

---

Under review as a conference paper at ICLR 2021
Table 3: Training hyper-parameters for the Atari domain.
Hyper-parameter
SR-DICE
DualDICE
GradientDICE
Direct-SR
Deep TD
Optimizer
Adam
Adam
Adam
Adam
Adam
Q Learning rate
6.25e 5
6.25e 5
6.25e
bb Q", ʃ. w Adam
1.5e-4
1.5e-4
1.5e-4 4
1.5e-1
1.5e-4
w, Adam
1e-8
1e
1e-8
w Learning rate
3e 4
3e 4
Learning rate
6.25e 5
6.25e
Learning rate
6.25e 5
6.25e 5
Learning rate
b Q" Mini-batch size
32
32
32
w. f, w. u, Mini-batch size
32
32
TT Q Target update rate
8k
8k
8k
26


Reviews:
[{"review_id": "igZRZZ2uKzx", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nStrengths:\n\n1) The experiments are extensive, and clearly demonstrate the merits as compared to prior benchmarks for off policy RL.\n\n2) The contextual discussion is clear, well-motivates the proposed approach, and gives a nice overview of how importance sampling and off policy RL intersect.\n\n\n\nWeaknesses:\n\n\n1) Theorem 1 seems vacuous. The proof is a simple exercise in elementary calculus -- one may easily show the minimizer of a quadratic is the least squares estimator. The authors need to better explain what is the technical novelty of this statement, and why it is meaningful. Upon inspection it does not seem to qualify as a theorem. This is also true of Theorems 2 and 3. Therefore, I feel the conceptual contribution is not enough to warrant acceptance.\n\n2) The notion of successor representation seems identical to the occupancy measure, which in order to estimate, requires density estimation, which is extremely sample inefficient. Can the authors comment about how to estimate the successor representation efficiently? There is very little discussion of sample complexity throughout, which is somewhat alarming because a key selling point of off-policy schemes for RL is that they alleviate the need for sampling from the MDP transition dynamics.\n\n3) The actual algorithm pseudo-code is missing from the body of the paper, which is permissible because it is in the appendix. However, the structural details of how the algorithm works iteratively and how it departs from previous works are also not explained. That is, while derivation details are presented, iterative details are not. In my opinion this should be strictly required in the body of the paper, as well as contextual discussion of what is similar/different from previous works, but all I could find was high level presentation of objectives minimized at various sections, but not how they are interlinked.\n\n4) The background discussion is disjointed. There is a preliminaries section on page 5, as well as a background section 3.\n\n\nMinor Comments:\n\n\n1) References missing related to the sample/parameterization complexity issues associated with importance sampling: \n\nKoppel, A., Bedi, A. S., Elvira, V., & Sadler, B. M. (2019). Approximate shannon sampling in importance sampling: Nearly consistent finite particle estimates. arXiv preprint arXiv:1909.10279.", "extra_scores": {}, "extra_text": {}}, {"review_id": "ccW3OKyMSg8", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes SR-DICE, which uses a successor representation to compute DICE (discounted stationary distribution correction term).\n* I am worried about both the technical and experimental qualities of this work. The theorems presented are either obvious or previously presented in other works. While the authors argue that the marginalized importance ratio is independent of the horizon (I assume that they are talking about the variance), MIS only alleviates the estimator variance's exponential dependence on the horizon to become the polynomial dependence on the horizon (as proved in Xie et al., Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling, 2019). In the experiments, it is hard to believe that the GradientDICE and DualDICE perform that poorly having Log MSE larger than 0 while the GenDICE paper reports Log MSE less than -4 (HalfCheetah).\n* The paper uses $\\phi$ and $\\psi$ learned by the previous deep successor representation learning algorithm, which is not meant to be used to learn marginal importance ratio. In particular, $\\phi$ is learned by minimizing state, action, and reward reconstruction error and $\\psi$ is the discounted sum of $\\phi$. If we consider a case where $\\pi$ only exploits a very small subset of state-action space, it is easy to see that the reconstruction error minimization in the dataset is not an optimal representation for the marginal importance ratio learning. In this sense, only the linear vector $w$ is used for the learning of marginal importance ratio.\n* The experiment setting is not fair. Direct-SR and SR-DICE in their implementation have effectively 2 hidden layers, where DualDICE and GradientDICE in their implementation have a single hidden layer.\n* The paper is hard to follow. Especially, notation abuse between the real reward and the virtual reward which is optimized to give a marginal importance ratio is very confusing (abuse between real Q and minimizer Q as well). Section 4.2 is also confusing because the authors imposes the problem of DualDICE that is not actually handled by SR-DICE.\n* The idea of adopting successor representation for learning marginal importance ratio seems quite novel.\n* Some people will be interested in this work, but I think the paper would not have much impact on the field.\n\nOverall,\n\nPROS:\n* The idea of using successor representation for learning marginal importance ratio is novel.\n* Avoids minimax formulation of other DICE algorithms, which makes the optimization very hard.\n\nCONS:\n* Not very meaningful theoretical results are presented, which mostly just confuse readers.\n* Uses the representation that is not learned for marginal importance ratio learning\n* Questionable experiment results\n\n\nMinor details:\n* y axis label is \"Log MSE\" for figures although the y axis is log scaled MSE.\n\n\n--------------------------------------\nMost of the concerns are addressed by the authors, and I raised my score accordingly.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ICAD7TFu9AW", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose SR-DICE based on deep SR for density ratio learning. Empirical advantages are observed in tested domains. Overall I think the idea is interesting and theoretically sound, but the experiments are not fully convincing.\n\nIt looks the main claim is that SR-DICE is better than other MIS methods because SR-DICE delegates the update propagation over the MDP to SR, while other MIS methods consider update propagation and density ratio learning together. To me this claim is not coupled with function approximation at all, so I would like to first see some experiments in the tabular setting. SR-DICE is a two-stage learning algorithm, i.e., SR learning + density ratio learning, both have hyperparameters to be tuned. GradientDICE and DualDICE are one-state learning algorithm. If in the tabular setting, we can empirically verify that under the best hyperparameter configuration of each algorithm (guaranteed by a thorough grid search), SR-DICE is more data efficient (counting the samples used in both stages) than GradientDICE and DualDICE, in terms of the density ratio prediction error, then the argument can be well backed. Well-controlled experiments like this, however, do not appear in the current submission.\n\nOnce deep networks are used for function approximation, we run into the problem of representation learning. The authors should at least include one more experiment, where MIS methods run directly on the pretrained deep SR features \\psi_\\pi(s) and/or \\phi(s). In this way, we can distinguish whether the empirical advantage of SR-DICE comes from SR-DICE itself or the improved representation learning.\n\nI'm also interested in seeing experiments for larger gammas, e.g., 0.999, 0.9999. I'm wondering if SR-DICE can consistently outperform GradientDICE with increasing discount factors.\n\nOverall, I'm happy to increase the score if I have any misunderstanding or more convincing results are presented. I appreciate that the authors include deep TD and behavior R(\\pi) as baselines. The empirical study has independent interest beyond SR-DICE. Moreover, deep TD is also referred to as Fitted-Q-Evaluation (FQE) in [x].\n\nx: Voloshin, Cameron, et al. \"Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning.\" arXiv preprint arXiv:1911.06854 (2019).\n\n=======================\n\n(Nov 24) The author response addressed my concerns and I therefore raised my score from 5 to 6. I particularly like the idea of using successor representation for density ratio learning.", "extra_scores": {}, "extra_text": {}}, {"review_id": "77vO1ILdDV", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "***Summary***\nThe paper proposes an approach to employ successor representation combined with marginalized importance sampling. The basic idea exploited in the paper consists of expressing the occupancies in terms of the successor representation and to model it via a linear combination of some features. This allows handling, although approximately, continuous state-action spaces. After having derived the objective function, an experimental evaluation on both Mujoco and Atari domains is presented, including an ablation study.\n\n***Major***\n- (About the linearity of the weight) Linear representations expressed in terms of a feature function are common in RL as the reward function can be often seen as a trade-off of different objectives encoded in the features. However, the choice of the linear representation in Equation (7) is based on the assumption that the marginalized weight is linear in the feature function. This assumption seems to me less justified compared to the one for the reward function. Clearly, a suitable feature design could overcome this limitation. Can the authors explain how the features \\phi are selected or learned? \n- (Experimental evaluation) The results presented in the experimental evaluation are partially unsatisfactory, as also the authors acknowledge. It seems that there is no clear benefit in employing the marginalized importances sampling (both the baselines and the proposed approach) compared to standard deep temporal difference approaches. The authors suggest that this phenomenon can be ascribed to the fact that the quality of the marginalized weights is affected by the successor representation learned. I don't think this is the main weakness of the paper, but a reflection of the usefulness of the method in complex scenarios is necessary. Alternatively, it would be interesting to compare the proposed approach with DualDICE and GradientDICE on simpler tasks (maybe toy ones) in which DualDICE and GradientDICE work well.\n\n\n***Minor***\n- The related work section should be moved later in the paper, maybe after Section 4\n- Pag 2, two lines above Equation (2): the transition model is here employed as a distribution over the next state s' and the reward r, but the reward function is considered separately in the definition of MDP presented before\n- Figures 2, 3, and 4: the plots are not readable when printing the paper in grayscale. I suggest using different linestyles and/or markers\n\n***Typos***\n- Pag 2: isn't -> is not\n- Pag 2: doesn't -> does not\n- Pag 8: the the -> the\n\n***Overall***\nThe paper can be considered incremental compared to DualDICE. I did not find any fault, but I feel that the significance of contribution is currently insufficient for publication at ICLR. In particular, for a paper that proposes a practical variation of a theoretically sound algorithm, the experimental evaluation is essential. I think that the results are currently unable to clearly show the advantages of the proposed method.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is about an approach that combines successor representation with marginalized importance sampling.
Although the reviewers acknowledge that the paper has some merits (interesting idea, good discussion, extensive experimental analysis) and the authors' responses have solved most of the reviewers' issues, the paper is borderline and the reviewers did not reach a consensus about its acceptance. In particular, the reviewers feel that the contributions of this paper are not significant enough.
I encourage the authors to modify their paper by taking into consideration the suggestions provided by the reviewers and try to submit it to one of the forthcoming machine learning conferences.
Decision: Reject