Off-Policy Evaluation for Action-Dependent Non-stationary Environments
Authors: Yash Chandak
Shiv Shankar
Nathaniel D. Bastian
Bruno Castro da Silva
Emma Brunskill
Philip S. Thomas
Venue: NeurIPS 2022 Accept (2022)
Keywords: non-stationarity
off-policy
reinforcement learning
counterfactual

Abstract: Methods for sequential decision-making are often built upon a foundational assumption that the underlying decision process is stationary. This limits the application of such methods because real-world problems are often subject to changes due to external factors (\textit{passive} non-stationarity), changes induced by interactions with the system itself (\textit{active} non-stationarity), or both (\textit{hybrid} non-stationarity). In this work, we take the first steps towards the fundamental challenge of on-policy and off-policy evaluation amidst structured changes due to active, passive, or hybrid non-stationarity. Towards this goal, we make a \textit{higher-order stationarity} assumption such that non-stationarity results in changes over time, but the way changes happen is fixed. We propose, OPEN, an algorithm that uses a double application of counterfactual reasoning and a novel importance-weighted instrument-variable regression to obtain both a lower bias and a lower variance estimate of the structure in the changes of a policy's past performances. Finally, we show promising results on how OPEN can be used to predict future performances for several domains inspired by real-world applications that exhibit non-stationarity.

Off-Policy Evaluation for Action-Dependent Non-Stationary Environments
Yash Chandak University of Massachusetts
Shiv Shankar University of Massachusetts
Nathaniel D. Bastian
United States Military Academy
Bruno Castro da Silva University Massachusetts
Emma Brunskill Stanford University
Philip S. Thomas
University of Massachusetts
Abstract
Methods for sequential decision-making are often built upon a foundational assump- tion that the underlying decision process is stationary. This limits the application of such methods because real-world problems are often subject changes due external factors (passive non- non-stationarity), changes induced by interactions with the system itself (active non-stationarity), or both (hybrid non-stationarity.. In this work, we take the first steps towards the fundamental challenge of on- on-policy and off off-policy evaluation amidst structured changes due to active, passive, or hybrid non-stationarity. Towards this goal, we make higher-order stationarity assump- tion such that non-stationarity results in changes over time, but the way changes happen is fixed. We propose, OPEN, algorithm that uses a double application counterfactual reasoning and a novel regression to obtain both lower bias and a lower variance estimate of the structure in the changes a policy's 's past performances. Finally, we show promising results how OPEN can be used predict future performances for several domains inspired by real-world applications that exhibit non-stationaris -on-staiionaiit.
seportance-weightee instrument-variable
1 Introduction
Methods for sequential decision making are often built upon a foundational assumption that the underlying decision process is stationary [Sutton and Barto, 2018]. While this assumption was cornerstone when laying the theoretical foundations the field, and while is often reasonable, is seldom true in practice and can be unreasonable [Dulac-Amold et al., 2019]. Instead, real- world problems are subject to uon-stationarity that can be broadly classified as (a) Passive: where the changes the system are induced only by external (exogenous) factors, (b) Active; where the changes result due to the agent's 's past interactions with the system, and (c) Hybrid: where both passive and active changes occur together [Khetarpal al., 2020].
There are many applications that are subject to active, passive, or hybrid non-stationarity. and where the stationarity assumption may be unreasonable. Consider methods for automated healthcare where we would like to use the data collected over past decades to find better treatment policies. In such cases, not only might there have been passive changes due to healthcare infrastructure changing over time, but active changes might also occur because of public health continuously evolving based on the treatments made available in the past, thereby resulting in hybrid non-stationarity. Similar to automated healthcare, other applications like online education, product recommendations, and in fact almost all human-computer interaction systems need not only account for the continually drifting behavior of the user demographic, but also how the preferences of users may change due to interactions with the system [Theocharous al., 2020]. Even social media platforms need to account for the partisan bias their users that change due to both external political developments
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

and increased self-validation resulting from previous posts/ads suggested by the recommender system itself [Cinelli et al., 2021, Gillani et al., 2018]. Similarly, motors in a robot suffer wear and tear over time not only based on natural corrosion but also on how vigorous past actions were.
However, conventional off-policy evaluation methods [Precup, 2000, Jiang and Li, 2015, Xie et al., 2019] predominantly focus on the stationary setting. These methods assume availability of either (a) resetting assumption to sample multiple sequences of interactions from stationary environment with a fixed starting state distribution (i.e., episodic setting), or (b) ergodicity assumption such that interactions can be sampled from a seaady-state/statioaay distribution (i.e., continuing setting). For the problems of our interest, methods based on these assumptions may not be viable. For e.g., in automated healthcare, we have single long history for the evolution of public health, which is neither in a steady state distribution nor can we reset and go back in time to sample another history of interactions.
As discussed earlier, because of non-stationarity the transition dynamics and reward function in the future can be different from the ones in the past, and these changes might also be dependent on past interactions. In such cases, how do we even address the fundamental challenge of off-policy evaluation, i.e., using data from past interactions estimate the performance of new policy in the future? Unfortunately, if the underlying changes are arbitrary, even amidst only passive non- stationarity it may not be possible to provide non- con-vacuous predictions of a policy's 's future performance [Chandak et al., 2020a].
Thankfully, for many real-world applications there might be (unknown) structure in the underlying changes. In such cases, can the effect of the underlying changes on policy's performance be inferred, without requiring estimation of the underlying model/process? Prior work has only shown that this is possible in the passive setting. This raises the question that we aim to answer:
How can one provide a unified procedure for (off) policy evaluation amidst active, passive, or hybrid non-stationarity, when the underlying chunges are structured?
Contributions: To the best of our knowledge, our work presents the first steps towards addressing the fundamental challenge of off- off-policy evaluation amidst structured changes due active or hybrid non-stationarity. Towards this goal, we make a higher-order stationarity assumption, under which the non-stationarity can result in changes over time, but the way changes happen fixed. Under this assumption, we propose a model-free method that can infer the effect of the underlying non- stationarity on the past performances and use that to predict the future performances for given policy. We call the proposed method OPEN: off oof-policy evaluation for non- non-stationary domains. On domains inspired by real-world applications, we show that OPEN often provides significantly better results not only in the presence of active and hybrid non-stationn -on-staiionarity, but also for the passive setting where it even outperforms previous methods designed to handle only passive -on-stationarity.
OPEN primarily relies upon two key insights: (a) For active/hybrid non-stationarity, as the underlying changes may dependend on past interactions, the structure in the changes observed when executing the data collection policy can be different than if one were to execute the evaluation policy. To address this challenge, OPEN makes uses counterfactual reasoning twice and permits reduction of this off-policy evaluation problem to an auto-regression based forecasting problem. (b) Despite reduction to more familiar auto-regression problem, in this setting naive least-squares based estimates of parameters for regr-segrossion suffers from high variance and can even be asymptotically biased. Finally, to address this challenge, OPEN uses a novel pepoortnce-weighhee instrument-variabee (auto-) "regression technique to obtain asymptotically consistent and lower variance parameter estimates.
2 Related Work
Off-policy evaluation (OPE) is an important aspect of reinforcement learning [Precup, 2000, Thomas et al., 2015, Sutton and Barto, 2018] and various techniques have been developed to construct efficient estimators for OPE [Jiag and Li, 2015, Thomas and Brunskill, 2016, Munos et al., 2016, Harutyunyan et al., 2016, Espeholt et al., 2018, Xie et al., 2019]. However, these work focus on the stationary setting. Similarly, there are various methods for tackling non-stationarity in the bandit setting [Moulines, 2008, Beshes et al., 2014, Seznec et al., 2018, Wang et al., 2019a]. In contrast, the proposed work focuses methods for sequential decision making.

---

Literature on off off-poliiy evaluation amidst non-stationarity for sequential decision making is sparse. Perhaps the most closely related works are by Thomas et [2017], Chandak et al. [2020b], Xie et al. [2020a], Poiani et al. [2021], Liotet et al. [2021]. While these methods present an important stepping stone, such methods are for passive non-stationarity and, as we discuss using the toy example in Figure 1, may result in undesired outcomes if used as-is in real-world settings that are subject to active or hybrid non non-stationarity.
Consider a robot that can perform a task each day either by 'walking' or 'running', A reward of 8 obtained upon completion using 'walking', but 'running' finishes the task ...
Run -10
Run
Run
+a10
+a
quickly and results in a reward of 10. However, 'running' wears out the motors, thereby increasing the time to finish the task the next day and reduces the returns for both 'walking' and 'running' by a small factor, a E (0. 1).
Walk
Walk +.8
Walk +a*8
Figure 1: RoboToy domain.
Here, methods for tackling passive non-stationarity will track the best policy under the assumption that the changes due to damages are because of external factors and would fail to attribute the cause of damage to the agent's decisions. Therefore, as on any given day 'running' will always be better, every day these methods will prefer 'running' over 'walking' and thus aggravate the damage. Since the outcome on each day is dependent on decisions made during previous days this leads active non-stationarity, where 'walking' is better in the long run. Finding better policy first requires a method to evaluate a policy's 's (future) performance, which is the focus of this work.
Notice that the above problem can also be viewed as a task with effectively a single lifelong episode. However, we discuss later in Section 4, approaches such modeling the problem as large stationary POMDP or as a continuing average-reward MDP with a single episode may not be viable. Further, non-stationarity can also be observed in multi-agent systems and games due to different agents/players interacting with the system. However, often the goal in these other areas is to search for (Nash) equilibria, which may not even exist under hybrid non-stationarity. Non-stationarity may also result due to artifacts of the learning algorithm even when the problem is stationary. While relevant, these other research areas are distinct from our setting of interest and we discuss them and others in more detail in Appendix B.
3 Non-Stationary Decision Processes
We build upon the formulation used by past work (Xie et al., 2020a, Chandak et al., 2020b] and consider that the agent interacts with lifelong sequence of partially observable Markov decision processes (POMDPs), (M,) However, unlike prior problem formulations, we account for active and hybrid non-stationarity by considering POMDP M++1 to be dependent both on the POMDP M, and the decisions made by the agent while interacting with M,. We provide a control graph for this setup in Figure 2. For simplicity of presentation, will often ignore the dependency of M,+1 on M,* for > 0, although our results can be extended for settings with ls > 0.
Notation: Let M be a finite set of POMDPs. Each POMDP M. E .M is a tuple (O, S, A, P2 Pt, RG (i;), where O is the set of observations, S the set of states, and A is the set of actions, which are the same for all the POMDPs in M. For simplicity of notation, we assume M, O, are finite sets, although our results can be extended to settings where these sets are infinite or continuous. Let Ω2 S O + [0, 1] be the observation function, P. Sx + 00, 1] be the tran- sition function, μ4 : S - [0, 1] be the starting state distribution, and R4 : S x A + Rmaxx Rmax] be the reward function with 0 Rinx < 3C.
Let : x A + [0, be any policy and II be the set of all policies. Let H, (0% A/ R.. be a sequence of at most T interactions in M,, where O,, AA, R are the random variables corresponding to the observation. action, and reward the step t. Let G. == Σn Rt be an observed return and (T) == [x be the performance of π on M,. Let H be the set of possible interaction sequences, and finally let T M x H X M + [0, 1] be the transition function that governs the non-stationarity in the POMDPs. That is, T(m, h, m')= = Pr(M MM;,- M,-m, H,h
3

---

Figure 2 (Left) depicts the control graph for stationary POMDP, where each column cor- responds to one time step. Here, multiple, in- dependent episodes from the same POMDP can be resampled. (Right) Control graph that we consider for a non-stationary decision pro- cess, where each column corresponds to one episode. Here, the agent interacts with a single sequence of related POMDPs (M)); Ab- sence or presence of the red arrows indicates whether the change from M, to M4+1 is inde- pendent of the decisions M; (passive non- stationarityy or not (active non-stationarity).
Stationary decision process
Non-stationary decision process
sequee
Figure 2: Control Graph for the non-stationary pro- cess. See text for symbol definitions.
Problem Statement: We look at the fundamental problem of evaluating the performance of a policy in the presence of non-stationarity, Let (H,) be the data collected in the past by interacting using policies (f.) Let D,, be the dataset consisting of (H+);_ and the probabilities of the actions taken by (3:) Given D,., aim to evaluate the expected future performance of π if deployed
for the next L episodes (each a different POMDP), that is f(t) = E, >k=n+1 J=( (H:)
We call the on-policy setting if Vi, 3 = т, and the off-policy setting otherwise. Notice that even in the on on-policy setting, naively aggregating observed performances from (14)) may not be indicative of I (T) as Mj for > n may be different than M E (M,) due to non-stationarity.
4 Understanding Structural Assumptions
careful reader would have observed that instead of considering interactions with a sequence of POMDPs (M: that are each dependent on the past POMDPs and decisions, an equivalent setup might have been to consider a 'chained' sequence of interactions (H1 , H2.... Hn) as a single episode in 'mega' POMDP comprised of all M E M.. Consequently, & (T) would correspond to the expected future return given (- Tackling this single long sequence of interactions using the settiniing//veaae-reew.w. reward setting is not generally viable because methods for these settings rely an ergodicity assumption (which implics that all states can always be revisited) that may not hold in the presence of non-stationarity. For instance, in the earlier example of automated healthcare, it is not possible to revisit past years.
To address the above challenge, we propose introducing different structural assumption. Particularly, framing the problem as a sequence of POMDPs allows us to split the single sequence of interac- tions into multiple (dependent) fragments, with additional structure linking together the fragments. Specifically,, we make the following intuitive assumption.
Assumption 1. Vm E M such that the performance (TT) associated with m is j.
YT, n' E II, Pr(Je+1(T) = I4 = m; n') = (T( -c 1 = j² (1)
Assumption characterizes the probability that T performance will be j:-1 in the i + 1h episode when the policy T' is executed in the 7th episode. To understand Assumption 1 intuitively, consider 'meta-transition' function that characterizes Pr(J+++ ( T²) similar to how the standard transition function in an MDP characterizes Pr(S.+ |S,, Ar). While the underlying changes actually happen via T, Assumption imposes the following two conditions: (a) A higher-order stationarity condition on the meta- trataattaasiiions under which non-stationarity can result in changes over time, but the way the changes happen is fixed, and (b) Knowing the past performance(s) of policy provides sufficient information for the meta-transition function to model how the performance will change upon executing any (possibly different) policy n'. For example, in the earlier toy robot domain, given the current performance there exists an (unknown) oracle that can predict the performance for the next day if the robot decides to 'run'/"walk walk''
Assumption 1 is beneficial as implicitly captures the effect of both the underlying passive and active non-stationarity by modeling the conditional distribution of the performance ( given Jx),,, when executing any (different) policy x'. the same time, notice that it generalizes (a) the stationary setting, where VT E 11, vi 0, ( (TT),, and (b) only passive non-stationarity,

---

which is special case of (1) wherein n' does not influence the outcome, i.e..
Vmay Th E IT? Vi 0, Pr(J++1(m) J++1|J ma) Pr(J++1(T) J(41)((F)) -s
Remark 1. In some cases, it may be beneficial relax Assumption such that instead of using (T) X') in (1), one considers similar the p-Markov MDP where the transitions are characterized using Pr(Se=1((Sea) While we consider this general setting for our empirical results, for simplicity, to present the key ideas we will consider (1). We provide detailed discussion on cases where we expect such an assumption to be (in)valid, and also other potential assumptions in Appendix C.
(T))(((=()())))))))) x²) This can be considered
At).
5 Model-Free Policy Evaluation
In this section we discuss how under Assumption we can perform model-free off- off-py evaluation amidst passive, active, or hybrid non-stationarity. The high level idea can be decomposed into the following: (a) Obtain estimates of (m))) using [H,),-. (red arrows in Figure 3), and (b) Use the estimates of (J:(T) to infer the effect of the underlying non-stationarity on the performance, and use that to predict (Ja (J)) (blue arrows in Figure 3).
J1
J2
JJ
Jnt1
H1
H2
H
Figure 3: High-level idea.
5.1 Counterfactual Reasoning (J((T)) could have been directly estimated if we had access to (M.))=1- However, how do we estimate (J,(T)) when we only have (H;) collected using interactions via possibly different data collecting policies (B:)
To estimate (J+())) we use the collected data D,, and aim to answer the following counterfactual question: what would the performance of would have been, if was used to interact with M, instead of 3,? To answer this, we make the following standard support assumption [Thomas et al., 2015, Thomas and Brunskill, 2016, Xie et al., 2019] that says that any action that is likely under is also sufficiently likely under the policy 3, for all i.
Assumption 2. Vo E O, Va A. and Vi S P.(o.a) is bounded above by (unknown) constant
T(o.a)
Under Assumption 2. an unbiased estimate of (T(T) can be obtained using common off-policy evaluation methods like importance sampling (IS) or per-decision importance sampling (PDIS)
[Precup, 2000], Vi, J((=) == Σ R', where, pf = - - (0 AP) This J((z) provides an estimate of (x) associated with each Mt and policy ग, as needed for the red arrows in Figure 3.
((O)
5.2 Double Counterfactual Reasoning Having obtained the estimates for (J((T) we now aim to estimate how the performance of π changes due to the underlying non-stationarity. Recall that under active or hybrid non-stationarity, changes in a policy's performance due to the underlying non-stationarity is dependent on the past actions. From Assumption 1, let
Vi > O, Fa (2, T', 8) = (r(J++1(T) g)J{(T) x; z;
denote how the performance of changes between episodes, if x was executed. Here J++1 1 (m) is random variable because of stochasticity in H, (i.e., how n² interacts in M,), as well as in the meta-transition from POMDP M, to M,+1. Similarly, let
Vi > 0, f(J((T) = E, (++ YER (J(,
be some (unknown) function parameterized by 0g E O, which denotes the expected performance of in episode i + 1, if in episode R's performance was JT(TT) and x' was executed. Parameters 0,, depend on æ and thus f can model different types of changes to the performance of different policies.
Recall from Figure 3 (blue arrows), if we can estimate f(, n; 0z) to infer how J:(TT) changes due to the underlying non-stationarity when interacting with then we can use it to predict (J&(z)) + when is deployed in the future. the following, we will predominantly focus on estimating f(, 0z) using past data D... Therefore, for brevity we let f(; fz) f(,,70.).
5

---

If pairs of (J,(T), (T)) are available when the transition between M, and M,+1 occurs due to execution of n, then one could auto-regress (T) on J.(T) to estimate f(=0z) and model the changes in the performance of æt However, the sequence (J)( obtained from counterfactual reasoning cannot be used as-is for auto-regression. This is because the changes that occurred between M, and M are associated with the execution of Br, not т. For example, recall the toy robot example in Figure 1. If data was collected by mostly 'running', then the performance of 'walking' would decay as well. Directly auto-regressing on the past performances of 'walking" would result in how the performance of 'walking' would change when actually executing 'running" However, if we want to predict performances of 'walking' in the future, what we actually want to estimate is how the performance of "walking' changes if "wakking' is actually performed.
To resolve the above issue, we ask another counter-factual question: What would the performance of in M,+1 have been had executed π,, instead of 3r, in M,2 In the following theorem we show how this question can be answered with a second application of the importance ratio p: == p.
Theorem 1. Under Assumptions 1 and 2, Vm E .M such that the performance J(x) associated with m is j. Ex (T)
= EB ( = m).
See Appendix D.I for the proof. Intuitively, as 3r and Bi+1 were used to collect the data in i and i + 1th episodes, respectively, Theorem 1 uses Pi to first correct for the mismatch between and 3, that influences how M; changes Mi+1 due to interactions Hi. Secondly, J1+1 corrects for the mismatch between π and 3++1 for the sequence of interactions H5-1 in M
5.3 Importance- Weighteed Iegerssssoo An important advantage of Theorem 1 is that given ((()), p:Ji+1 (TT) provides an unbiased estimate of Ex, [J++[ even though и may not have been used for data collection. This permits using Y; = p::J+11 (T) as a target for predicting the next performance given X; == (T), i.e. to estimate {() 8z) through regression on (X,, Y.) pairs.
However, notice that performing regression on the pairs (X; = J((x), Y. = p may not be directly possible as we do not have J((T); only unbiased estimates [.(T)) of J((T). This problematic because in least-squares regression, while noisy estimates of the target variable Y; are fine, noisy estimates of the input variable X, may result in estimates of 0g that are not even asymptotically consistent even when the underlying f is linear function of its inputs. To see this clearly, consider the following naive estimator,
Ónativa E Gargmin ΣN (1 -
DEG
Because JT()))) ) is an unbiased estimate of Jz, without loss of generality, let Ji(TT) = (T( + T/- Ja- In-1(()) (T)
where is mean zero noise, Let N == [m, 72, "]]]].. and J = Osaive can now be expressed as (see Appendix D.2),
O a.S, (JJ+NNTN) JTIO 10, 0z.
Observe that N N in (2) relates to the variances of the mean zero noise variables 17. The greater the variances, the more Onaive would be biased towards zero (if Vi, πy: = O, then the true 0z is trivially recovered). Intuitively, when the variance of 7) is high, noise dominates and the structure in the data gets suppressed even in the large-sample regime. Unfortunately, the importance sampling based estimator (T) in the sequential decision making setting is infamous for extremely high variance [Thomas et al., 2015]. Therefore, dnaive can be extremely biased and will not be able to capture the trend in how performances changing, even in the limit of infinite data and linear f. The problem may be exacerbated when f is non-linear.
5.3.1 Bias Reduction To mitigate the bias stemming from noise in input variables, we introduce a novel instrument variable (IV) [Pearl et al., 2000] regression method for tackling non-stationarity. Instrument variables Z represent some side-information and were originally used the causal literature to mitigate any bias resulting due to spurious correlation, caused by unobserved confounders, between the input and the target variables. For mitigating bias in our setting, IVs can intuitively be considered as some indeiifformatinn to 'denoise" the input variable before performing regression.

---

For this VVregression, an ideal IV is correlated with the imput variables (e.g. (T)) but uncorrelated with the noises in the input variable (e.g.. TT.)
We propose leveraging statistics based on past performances as an IV for (T)).. For instance, using 2, == (T) as an IV for (T).. Notice that while correlation between (T) and (T(T) can directly imply correlation between ( and (x),, values of (+) and (T) are dependent on non-stationarity in the past. Therefore, we make the following assumption, which may easily be satisfied when the consecutive performances do not change arbitrarily.
Assumption 3. Vi, Cov (T) * O.
However, notice that the noise in (T) can be dependent on (T)) This is because non statiooarttt can make H;-1 and H, dependent, which are in turn used to estimate 1 and (T()), respec- tively. Nevertheless, perhaps interestingly, we show that despite not being independent, J;-1(T) (T) is uncorrelated with the noise in (TT).
- Theorem 2. Under Assumptions and 2, Vi, Cov (()
= 0.
See Appendix D.3 for the proof. Finally, as IV regression requires learning an additional function g = R + R parameterized by to Ω (intuitivelly, think of this as denoising function), we let
J 4-11 (T)) be an IV for (T) and propose the following IV-regression based estimator,
Σn (o (J))(()))) - J((T))
Gn E argmin PE
(3)
0, E argmin lee
Σ (J-1(T))) :)) p))+2(a))
(4)
Under Assumptions 1, 2, and 3, f and g are linear functions of their inputs, then 0n a strongly consistent estimator of 0,, i.e., O2 ni,, Oz (See Appendix D.3 D.3for the proof.)
Theorem 3.
Remark 2.
Other choices of instrument variables Z, (apart from Z, = J.1 (TT) are also viable. We discuss some alternate choices in Appendix E. These other IVs can be used in (3) and (4) by replacing Ja (1)) with the alternative Zi.
Remark 3. As discussed earlier, it may be beneficial to model J (T)) using (J=(=))i=i-pt+ with p > The proposed estimator can be easily extended by making f dependent on multiple past terms (Xu)i=i-ptt where Vk, X₁ == {((J((()))- Φ). We discuss this in more detail in Appendix E. The proposed procedure is also related to methods that use lags of the time series as instrument variables [Bellemare al., 2017, Wilkins, 2018, Wang and Bellemare, 2019].
Remark 4. An advantage of the model-free setting is that only need consider changes in ((T), which is a scalar statistic. For scalar quantities, linear auto-regressive models have been known to be useful in modeling wide variety of time-series trends. Nonetheless, non-linear functions like RNNs and LSTMs HHochretter and Schmidhuber, 1997] may also be leveraged using deep instrument variable methods [Hartford et al., 2017, Bennett et al., 2019, Liu et al., 2020, Xu al., 2020].
As required for the blue arrows in Figure 3, f(:; can now be used to estimate the expected value EE, [J++1(T) (+T) under hybrid non-stationarity. Therefore, using {(; 0x) we can now auto- regressively forecast the future values of (J+(T)) + and obtain an estimate for I (TT). A complete algorithm for the proposed procedure is provided in Appendix E.I.
5.3.2 Variance Reduction As discussed earlier, importance sampling results in noisy estimates of
(x..). During regression, while high noise in the input variable leads to high bias, high noise in the target variables leads to high variance parameter estimates. Unfortunately, (3) and (4) have target variables containing p; (and 11++) which depend on the product of importance ratios and can thus result in extremely large values leading to higher variance parameter estimates.
The instrument variable technique helped in mitigating bias. To mitigate variance, we draw inspiration
from the reformulation of weighted-importaaee importance sampling presented for the stationary setting by
7

---

10.0
100
80
Eatimate
9.0
Estimate
60
Estimate
9.0
8.5
8.3
8.0
8.0
1000 Episode
1000
Episode
Episode
True Past
True Future
15 weighted return
Denoised
Predicted
Figure 4: An illustration of the stages in the proposed method for the RoboToy domain of Figure 1. Here, evaluation policy π chooses to 'run' more often, whereas the data collecting policy chooses to 'walk' more often. (Left) This results in slow decline of performance for initially, followed by a faster decline once и is deployed after episode 2000. The blue and gray curves are unknown to the algorithm. (Middle) OPEN first uses historical data to obtain counterfactual estimates of (T)) for the past episodes. One can see the high-variance in these estimates (notice the change in the y-scale) due to the of importance sampling. (Right) Intuitively, before naively auto-regressing, OPEN first denoises past performance estimates using the first stage of IV regression (i.e., converts black dots to green dots). can be observed that OPEN successfully denoises the importance sampling estimates. Using these denoised estimates and second use of counterfactual reasoning, OPEN performs the second stage of IV regression. It is able estimate that once is deployed, performances in the future will decrease more rapidly compared to what was observed in the past.
Mahmood et al. [2014], and propose the following estimator,
Σn Pi (o ( -G((T))
where P: = Ps (5)
Gn E argmin PEN
Σj=2 Pj
1=2
Σ (T(((T-)(t)s)))) :0) Ci+1(T))* where P. = PiPit1
On E argmin
(6)
Σド PsP5+1
where G, the return observed for Mj. Intuitively, instead of importance weighting the target, we importance weight the squared error, proportional to how likely that error would be if was used to collect the data. Since dividing by any constant does affect G.. and 0,. the choice of p. and p! ensures that both P. and p! E [0, 1]. thereby mitigating variance but still providing consistency.
Theorem 4. Under Assumptions 1, 2, and 3. if and linear functions of their inputs. then 0n is strongly consistent estimator of 0z i.e., O, a.s. 0n. (See Appendix D.3 for the proof.)
Empirical Analysis
This section presents both qualitative and quantitative empirical evaluations using several environ- ments inspired by real-world applications that exhibit non-stationarity. the following paragraphs, we first briefly discuss different algorithms being compared and answer three primary questions.'
1. OPEN:
off- aff-policy evaluation for non-stationary domains with structured passive, active, or hybrid changes. It is based on our bias and variance reduced estimator developed in (5) and (6). Appendix F. contains the complete algorithm.
We call our proposed method OPEN:
Pro-WIS: For the baseline, we use Prognosticator with weighted least-squares (Pro-WI.S) [Chandak et al., 2020b). This method is designed to tackle only passive non-stationarity.
WIS: A weighted importance sampling based estimator that ignores presence of non-stationarity completely [Precup, 2000].
4. SWIS:
Sliding window extension of WIS which instead of considering all the data, only considers data from the recent past.
'Code available http:://ghhhu...ommyysshhhaaaaaa

---

RoboTay.Acth Active
16
MountainCar
1651
MEDDWW
Dabetes
2.0
[Bias]
Spwwed
Speed
Speed MEDEVAC
Speeed
Reboltyy-hthh betive
Non MountaihCar
Diabetes
3.25
1.25
2.00
0.33
0.30
0.76
0:29
Spieet
Speend
Spoodt
OPEN (Proposed)
Pro-WLS
WIS
SWIS
Figure 5: Comparison of different algorithms for predicting the future performance of evaluation
policy on domains that exhibit active/hybrid non-stationarity. On the x-axis is the speed which corresponds to the rate of non-stationarity; higher speed indicates faster rate change and a speed of zero indicates stationary domain. On the y-axes are the absolute bias (Top row) and the mean-squared error (Bottom row) the predicted performance estimate (lower better everywhere). For each domain, for each speed, for each algorithm, 30 trials were executed.
QL. (Qualitative Results) What is the impact of the two stages of the OPEN algorithm??
In Figure 4 present a step by step breakdown of the intermediate stages of single run of OPEN on the RoboToy domain from Figure 1. It can observed that OPEN is able to extract the effect of the underlying active non-stationarity on the performances and also detect that the evaluation policy ı that 'runs' more often will cause an active harm, deployed in the future.
Q2. (Quantitative Results) What is the effect of different types and rates of non-stationarity?
Besides the toy robot from Figure 1, provide empirical results three other domains inspired by real-world applications that exhibit non-stationarity. Appendix E.3 contains details for each, including how the evaluation policy and the data collecting policy were designed for them.
Non-stationary Mountain Car: In real-world mechanical systems, motors undergo wear and tear over time based on how vigorously they have been used in the past. To simulate similar performance degradation, we adapt the classic (stationary) mountain car domain [Sutton and Barto, 2018]. We modify the domain such that after every episode the effective acceleration foree is decayed proportional to the average velocity of the car in the current episode. This results in active non-stationarity, where the change in the system is based the actions taken by the agent in the past.
Type-1 Diabetes Management: Personalised automated healthcare systems for individual patients should account for the physiological and lifestyle changes of the patient over time. To simulate such scenario we use an source implementation [Xie, 2019] of the U.S. Food and Drug Administration (FDA) approved Type-1 Diabetes Mellitus simulator (TIDMS) [Man et al., 2014] for the treatment of Type-1 diabetes, where we induced non-stationarity by oscillating the body parameters (e.g., rate of glucose absorption, insulin sensitivity, etc.) between two known configurations available in the simulator. This induces passive non statiiition,r,t, that is, changes are not dependent on past actions.
This domain stands for medical evacuation using air ambulances. This domain was developed by Robbins in regions of conflict. Based on real-data, this domain simulates the arrival of different events, from different zones, where each event can have different priority levels. Serving higher priority events yields higher rewards. A good controller decides whether to deploy, and which MEDEVAC to deploy, to serve any event (at the risk of not being able to serve new high-priority event all ambulances become occupied). Here, the arrival rates of different events can change based on external incidents during conflict. Similarly, the service completion rate can also change based on how frequently an ambulance is deployed in the past. To simulate such non-stationarity, we oscillate the arrival rate of
MEDEVAC:
[2020] for optimally routing air ambulances to provide medical assistance

---

the incoming high-priority events, which induces passive non-stationarity. Further, to induce wear and tear, we decay the service rate of an ambulance proportional to how frequently the ambulance was used in the past. This induces active non-stationarity. The presence of both active and passive changes makes this domain subject to hybrid stationaton
Figure 5 presents the (absolute) bias and MSE incurred by different algorithms for predicting the future performance of the evaluation policy л. As expected, the baseline method WIS that ignores the non-stationarity completely fails to capture the change in performances over time. Therefore, while WIS works well for the stationary setting, as the rate of -tatiintton increases, the bias incurred by WIS grows. In comparison, the baseline method Pro- FL- that can only account for passive non stationarity captures the trend better than WIS, but still performs poorly in comparison to the proposed method OPEN that is explicitly designed to handle active/hybrid non non-stationarity. Perhaps interestingly, for the Diabetes domain which only has passive non- stasstationarity we observe that OPEN performs better than Pro-WLS. As we discuss later, this can be attributed to the sensitivity of Pro-WI.S to its hyper-parameters
While OPEN incorporated one variance reduction technique, it can be noticed when the rate of non-stationarity is high, variance can sometimes still be high thereby leading to higher MSE. We discuss potential negative impacts of this in Appendix A. Incorporating (partial) knowledge of the underlying model and developing doubly-robuse version of OPEN could potentially mitigate variance further. We leave this extension for future work.
Q3. (Ablations Results) How robust the methods hyper-parameters?
Due to space constraints, we defer the empirical results and discussion for this to Appendix E.5. Overall, we observe that the proposed method OPEN being an auto-regressive method can extrapo- late/forecast better and is thus more robust to hyper-parameters (number of past terms to condition, as discussed in Remark 3) than Pro-WLS that uses Fourier bases for regression (where the hyper- parameter is the order of Fourier basis) and is not as good for extrapolation.
7 Conclusion
We took the first steps for addressing the fundamental question of off-policy evaluation under the presence of non-stationarity. Towards this goal we discussed the need for structural assumptions and developed a model-free procedure OPEN and presented ways to mitigate its bias and variance. Empir- ical results suggests that OPEN can now not only enable practitioners to predict future performances amidst non-stationarity but also identify policies that may be actively causing harm or damage. In the future, OPEN can also be extended enable control of non-stationary processes.
8 Acknowledgements
Research reported in this paper was sponsored in part by gift from Adobe, NSF award #2018372. This work was also funded in part by the U.S. Army Combat Capabilities Development Command (DEVCOM) Army Research Laboratory under Cooperative Agreement I911NF-17-2-0196 and Support Agreement No. USMA21050. The views expressed in this paper are those of the authors and do not reflect the official policy or position of the United States Military Academy, the United States Army, the Department of Defense, or the United States Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
References
M. Abbott. Instrumental variables (iv) estimation: An introduction, 2007. http:///tteee econ. queensu.
f07. pdf.
C. H. Achen. Why lagged dependent variables can suppress the explanatory power of other indepen- dent variables. In annual meeting of the political methodology section of the American political science association, UCLA, volume 20, pages 7-2000, 2000.
10

---

A. Agarwal, M. Henaff, S. Kakade, and W. Sun. Pe-pg: Policy cover directed exploration for provable policy gradient learning. Advances in Neural Information Processing Systems, 53:13399-13411 2020.
N. Alegre, A. L. Bazzan, and B. C. da Silva. Minimum-delay adaptation in non-stationary reinforce- ment learning via online high-confidence change-point detection. arXiv preprint arXiv:2105.09955, 2021.
H. B. Ammar, R. Tutunov, and E. Eaton. Safe policy search for lifelong reinforcement learning with sublinear regret. In International Conference on Machine Learning, pages 2361-2369. PMLR, 2015.
E. W. Basso and M. Engel. Reinforcement learning in non-stationary continuous time and space scenarios. In Artificial Intelligence National Meeting, volume 7, pages 1-8. Citeseer, 2009,
M. F. Bellemare, T. Masaki, and T. B. Pepinsky. Lagged explanatory variables and the estimation of causal effect. The Journal of Politics, 79(3):949-966 2017.
A. Bennett, N. Kallus, and Schnabel. Deep generalized method of moments for instrumental variable analysis. arXiv preprint arXiv: 12495, 2019.
A. Bennett, N. Kallus, L. Li, and A. Mousavi. Off-policy evaluation in infinite-horizon reinforcement learning with latent confounders. In International Conference on Artificial Intelligence and Statistics, pages 1999-20077. PMLR, 2021.
O. Besbes, Y. Gur, and A. Zeevi. Stochastic multi-armed-banme problem with non-stationary rewards.
In Advances in Neural Information Processing Systems, pages 199-207, 2014.
M. Bowling. Convergence and no-regret in multiagent learning. In Advances in Neural Information Processing Systems, pages 209-216, 2005.
A. Boyan. Least-squares temporal difference learning. In JCML, pages 49-56, 1999.
Buckman, C. Gelada, and M. G. Bellemare. The importance pessimism in fixed-dataset policy optimization. arXiv preprint (0Xi::2000006799, 2020.
A. C. Cameron. Instrument variables, 2019, http://cameron.eet www.:/on....ooo....o............ e240a/ hataaa/chiiv.../. påf.
E. Cetin and O. Celiktutan. Learning pessimism for robust and efficient off-policy reinforcement learning. arXiv preprint / 2021.
Y. Chandak, S. M. Jordan, G. Theocharous, M. White, and P. S. Thomas. Towards safe policy improvement for non-stationary mdps. Neural Information Processing Systems, 2020a.
Y. Chandak, G. Theocharous, S. Shankar, S. Mahadevan, M. White, and P. S. Thomas. Optimizing for the future non-stationary mdps. International Conference on Machine Learning. 2020b.
Y. Chandak, Niekum, B. da Silva, E. Leamnd-MMllerr, E. Brunskill, and P. S. Thomas. Universal off-policy evaluation. Advances in Neural Information Processing Systems, 34, 2021.
T. K. Chandra. Extensions of rajchman's ''s strong law of large numbers. Sankhyā: The Indian Journal of Statistics, Series A, pages 181, 1991.
S. P. Choi, D.-Y. Yeung, and N. L. Zhang. An environment model for nonstationary reinforcement learning. In Advances in Neural Information Processing Systems, pages 987-993, 2000.
M. Cinelli, G. D. F. Morales, A. Galeazzi, W. Quattrociocchi, and M. Starnini. The echo chamber effect on social media. Proceedings of the National Academy of Sciences, 118(9), 2021.
V. Conitzer and T. Sandholm. Awesome: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents. Machine Learning, 67(1-2):
23 43, 2007.
D. R. Cox and H. D. Miller. The theory of stochastic processes. Routledge, 2017.

---

B. C. Da Silva, E. W. Basso, A. L. Bazzan, and P. M. Engel. Dealing with non-stationary environments using context detection. In Proceedings of the 23rd international conference on Machine learning. pages 217-224, 2006.
B. Dai, O. Nachum, Y. Chow, L. Li, C. Szepesvári, and D. Schuurmans. Coindice: Off-policy confidence interval estimation. arXiv preprini arXiv:2010.1 1652, 2020.
F. Doshi- Doshi-Velez and G. Konidaris. Hidden parameter markov decision processes: A semiparametric regression approach for discovering latent task parametrizations. In IJCAI: proceedings of the conference, volume 2016, page 1432. NIH Public Access, 2016.
G. Dulac-Amold, D. Mankowitz, and T. Hester. Challenges real-world reinforcement learning. arXiv preprint arXiv: /90.:::9944/990000 /2901, 2019.
L. Espeholt, H. Soyer, R. Munos, K. Simonyan, Mnih, T. Ward, Y. Doron, V. Firoiu, T. Harley, I. Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-leamer architectures. In International conference on machine learning, pages 1407-1416. PMLR, 2018.
Y. Feng, Z. Tang, na zhang, and qiang liu. Non-asymptotic confidence intervals of off-policy evaluation: Primal and dual bounds. In International Conference Learning Representations, 2021. URL https:t///// opw.reveeeeeeeeeeeeeeee net forum? d=dKg5D1 ZmL..
J. Foerster, R. Y. Chen, M. Al-Shedivat, S. Whiteson, P. Abbeel, and I. Mordatch. Learning with opponent-learning awareness. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 122-130. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
D. J. Foster, Z. Li, T. Lykouris, K. Sridharan, and E. Tardos. Learning in games: Robustness of fast convergence. In Advances Neural Information Processing Systems, pages 4734 2016.
I. Gemp and S. Mahadevan. Online monotone games. arXiv preprint arXiv: 1710::0777000288 2017.
N. Gillani, A. Yuan, M. Saveski, S. Vosoughi, and D. Roy. Me, my echo chamber, and i: introspection on social media polarization. In Proceedings of the 2018 World Wide Web Conference, pages 823 831, 2018.
D. Hamilton.
State-space models. Handbook of econometrics, 4:3039-3080, 1994.
J. Hartford, G. Lewis, K. Leyton- and M. Taddy, Deep iv: A flexible approach for counter- factual prediction. In International Conference on Machine Learning, pages 1414-1423. PMLR, 2017.
A. Harutyunyan, M. G. Bellemare, T. Stepleton, and R. Munos. Q (A) with off-policy corrections. In International Conference on Algorithmic Learning Theory, pages 305-320. Springer, 2016.
D. Hennes, D. Morrill, S. Omidshafiei, R. Munos, J. Perolat, M. Lanetot, A. Gruslys, J.-B. Lespiau, P. Parmas, E. Duenez-Guzmant et al. Neural replicator dynamics. arXiv preprint arXiv:990600000000000 2019.
Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation, 98):1733-1 1997.
R. Jagerman, I. Markov, and M. de Rijke. When people change their mind: Off-policy evaluation in non-stationary recommendation environments. Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, Melbourne, VIC, Australia, February 11-15, 2019. 2019.
N. Jaques, A. Lazaridou, E. Hughes, C. Gulcehre, P. Ortega, D. Strouse, J. Z. Leibo, and N. De Fre- itas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In International Conference Machine Learning, pages 3040-3049. PMLR, 2019.
N. Jiang and J. Huang. Minimax confidence interval for off-policy evaluation and policy optimization. arXiv preprint arXhv:2002.02088, 2020.
12

---

N. Jiang and L. Li. Doubly robust off-policy value evaluation for reinforcement learning. arXiv preprint arXiv:1511.03722, 2015.
K. Khetarpal, M. Riemer, I. Rish, and D. Precup. Towards continual reinforcement learning: A review 0en::2012.134990 2020.
and perspectives. arXiv preprint
N. Levine, K. Crammer, and S. Mannor. Rotting bandits. In Advances in Neural Information Processing Systems, pages 3074-3083, 2017.
C. and M. de Rijke. Cascading non non-stational stationary bandits: Online learning to rank in the non- con-stationary cascade model. arXiv preprint arXiv:1905.1233: 2019.
P. Liotet, F. Vidaich, A. M. Metelli, and M. Restelli. Lifelong hyper-policy optimization with multiple importance sampling regularization. arXiv preprint arXiv:2112.0662) 2021.
Q. Liu, L. Li, Z. Tang, and D. Zhou. Breaking the curse of horizon: Infinite-horizon off-policy estimation. In Advances in Neural Information Processing Systems, pages 5356-5366, 2018.
R. Liu, Z. Shang, and G. Cheng. On deep instrumental variables estimate. arXiv:2004. 14954, 2020.
arXiv preprint
A. R. Mahmood, H. Van Hasselt, and R. S. Sutton. Weighted importance sampling for off-policy learning with linear function approximation. In NIPS, pages 3014-3022, 2014.
A. R. Mahmood, H. Yu, M. White, and R. S. Sutton. Emphatic temporal-differenc learning. arXiv preprint 1507 150,00690,,, 2015.
C. D. Man, F. Micheletto, D. Lv, M. Breton, B. Kovatchev, and C. Cobelli. The UVA/PADOVA type diabetes simulator: New features. Journal of Diabetes Science and Technology, 8(1):26-34, 2014.
R. Mealing and L. Shapiro. Opponent modelling by sequence prediction and lookahead in two- player games. In International Conference on Artificial Intelligence and Soft Computing, pages 385-396. Springer, 2013.
A. W. Moore. Efficient memory-basee learning for robot control. 1990.
E. Moulines. On upper- coper-confieence bound policies for non-stationary bandit problems. arXiv preprint 355 2008
R. Munos, T. Stepleton, A. Harutyunyan, and M. Bellemare. Safe and efficient off off-policy reinforce- ment learning. Advances in neural information processing systems, 29, 2016.
O. Nachum and B. Dai. Reinforcement learning via fenchel-roocafelllar duality. arXiv preprint arXiv:2001.01866, 2020.
O. Nachum, Y. Chow, B. Dai, and L. Li. Dualdice: Behavior- estimation of discounted stationary distribution corrections. Advances in Neural Information Processing Systems, 32, 2019.
H. Namkoong, R. Keramati, S. Yadlowsky, and Brunskill. Off-policy policy evaluation for sequential decisions under unobserved confounding. Advances in Neural Information Processing Systems, 33:18819 1188819-1800 18831, 2020.
Padakandla. A survey of reinforcement learning algorithms for dynamically varying environments. arXiv preprint arXiv:2005. 2020.
S. Padakandla, P. K. J.. and S. Bhatnagar. Reinforcement learning in non-stationary environments. CoRR, abs/ abs/1905.00990, 2019.
A. Parker. Endogenous regressors and instrumental variables, 2020. https:://ww. edt:/economiccs/peee /ttccommmmcs//prrree////////eeee htt.//////nnnt/////slllll Ntt.//oottttlooee...... pdf..
J. Pearl et al. Models, reasoning and inference. Cambridge, UK: CambridggUUniversisypresss 19, 2000.
R. Poiani, A. Tirinzoni, and M. Restelli. Meta-reinforreement learning by tracking task non-stationarity. arXiv preprint arXiv:2105.08834, 2021.
13

---

D. Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
M. L. Puterman. Markov decision processes. Handbooks in operations research and management science, 2:331-434, 1990.
E. Rachelson, P. Fabiani, and F. Garcia. Timdppoly: An improved method for solving time-dependent mdps. In 2009 st IEEE International Conference on Tools with Artificial Intelligence, pages 796-799, IEEE, 2009.
A. Rajchman. Zaostrzone prawo wielkich liczb. Mathesis Polska, 6:145-161, 1932.
W. R. Reed. On the practice of lagging variables to avoid simultaneity. Oxford Bulletin of Economics and Statistics, 77(6):897-900 2015.
M. Robbins, R. Jenkins, N. D. Bastian, and B. J. Lunday. Approximate dynamic programming for the aeromedical evacuation dispatching problem: Value function approximation utilizing multiple level aggregation. Omega, 91:102020, 2020.
Y. Russac, C. Vernade, and O. Cappé. Weighted linear bandits for non-stationary environments. Advances in Neural Information Processing Systems, 32, 2019.
Seznec, A. Locatelli, A. Carpentier, A. Lazaric, and M. Valko. Rotting bandits are harder than stochastic ones. arXiv preprint arXiv:1811.1104. 2018.
C. Shi, M. Uchara, and N. Jiang. A minimax learning approach to off-po evaluation in partially observable markov decision processes. arXiv preprint arXiv:2111.066 2021.
Singh, M. Kearns, and Y. Mansour. Nash convergence gradient dynamics in general- sum games. In Proceedings of the Sixteenth conference on Uncertainty in artificial intelligence, pages 541-548. Morgan Kaufmann Publishers Inc., 2000.
R. Sutton and G. Barto. Reinforcement learning: An introduction. MIT Press, Cambridge, MA, 2 edition, 2018.
R. S. Sutton, H. Maei, and C. Szepesvári. A convergent o(n) temporal-difference algorithm for off-policy learning with linear function approximation. Advances in neural information processing systems, 21, 2008
R. Sutton, H. R. Maei, D. Precup. S. Bhatnagar, D. Silver, C. Szepesvári, and E. Wiewiora. Fast graseent methods for demporal- learning with linear function approximation. In Proceedings of the 26th annual international conference machine learning, pages 993-1000, 2009.
A. A. Taiga, W. Fedus, M. C. Machado, A. Courville, and M. G. Bellemare. On conus-based exploration methods in the arcade learning environment. arXiv preprini arXiv:2109. 11052, 2021.
G. Tennenholtz, U. Shalit, and S. Mannor. Off-policy evaluation in partially observable environments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 10276-10283, 2020.
G. Theocharous, Y. Chandak, S. Thomas, and de Nijs. Reinforcement learning for strategic recommendations. arXiv preprint arXiv:2009.07346, 2020.
P. Thomas and E. Brunskill. Data-efficient off off-policy policy evaluation for reinforcement learning. In International Conference on Machine Learning, pages 2139-2148. 2016.
Thomas, G. Theocharous, and M. Ghavamzadeh. High-confidence off off-policy evaluation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
P. S. Thomas. Safe reinforcement learning. PhD thesis, University of Massachusetts Libraries, 2015.
P. S. Thomas, G. T'heocharous, M. Ghavamzadeh, I. Durugkar, and E. Brunskill. Predictive off-policy policy evaluation for nonstationary decision problems, with applications digital marketing. In AAAL pages 4740-4745, 2017.
14

---

P. S. Thomas, B. C. da Silva, A. G. Barto, S. Giguere, Y. Brun, and E. Brunskill. Preventing undesirable behavior of intelligent machines. Science, 366(6468) 2019.
M. Uehara, J. Huang, and N. Jiang. Minimax weight and q-function learning for off-policy evaluation.
In International Conference on Machine Learning, pages 9659-9668 PMLR, 2020.
C. Vernade, A. Gyorgy, and Mann. Non-stationary delayed bandits with intermediate observations.
In International Conference on Machine Learning, pages 9722-9732. PMLR, 2020.
L. Wang, H. Zhou, B. Li, L. R. Varshney, and Z. Zhao. Be aware of non-stationarity Nearly optimal algorithms for piecewise-statioaal cascading bandits. arXiv preprint arXiv: /909005886. 2019a.
T. Wang, M. Bowling, and D. Schuurmans. Dual representations for dynamic programming and reinforcement learning. In 2007 IEEE International Symposium Approximate Dynamic Pro- gramming and Reinforcement Learning, pages 44-51. IEEE, 2007.
T. Wang, J. Wang, Y. Wu, and C. Zhang. Influence-based multi-agent exploration. arXiv preprint 1r11v:1910.05512. 2019b.
W. Z. Wang, A. Shih, A. Xie, and Sadigh. Influencing towards stable multi-agent interactions. arXiv preprint urXiv:21 2021.
Y. Wang and M. F. Bellemare. Lagged variables instruments, 2019.
A. Wilkins. To lag or not to lag?:
Re-evaluating the use lagged dependent variables in regression analysis. Political Science Research and Methods, 6(2):393-411, 2018.
A. Xie, J. Harrison, and C. Finn. Deep reinforcement learning amidst lifelong non-stationarity. arXiv preprint arXiv:2006. 10701, 2020a.
A. Xie, D. P. Losey, R. Tolsma, C. Finn, and D. Sadigh. Learning latent representations to influence multi-agent interaction. arXiv preprint arXiv:2011.0661/ 2020b.
Xie. Simglucose v0.2.1 (2018), 2019. URL httttt//////tth com/ jxx12x / /ttm///xx1////mm/oooo//o/ simglucose.
Xie, Ma, and Y.-X. Wang. Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling, arXiv preprint arXiv:1906.03: 033393, 2019.
L. Xu, Y. Chen, S. Srinivasan, N. de Freitas, A. Doucet, and A. Gretton. Learning deep features in instrumental variable regression. arXiv preprint arXiv:2010.07154, 2020.
M. Yang, O. Nachum, B. Dai, L. Li, and D. Schuurmans. Off- evaluation via the regularized lagrangian, Advances in Neural Information Processing Systems, 33:6551-6561, 2020.
C. Yuan, Chandak, S. Giguere, P. S. Thomas, and Niekum. Sope: Spectrum of off-policy estimators. Advances in Neural Information Processing Systems, 8458-19881,,,, 2021.
C. Zhang and V. Lesser. Multi-agent learning with policy prediction. In Twenty-fourth AAAI conference on artificial intelligence, 2010.
H. Zhou, J. Chen, L. R. Varshney, and A. Jagmohan. Nonstationary reinforcement learning with linear function approximation. arXiv preprint arXiv:2010.04244, 2020.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
15

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL.)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "j8B9Foyan5y", "reviewer": "Reviewer_h3hM", "summary": "This work proposes a method for evaluating (predicting) the future performance of a policy in non-stationary sequential decision processes. This allows to evaluated policies even if decision processes are changing over time. The work introduces an assumption on the structure of the changes in the decision process, which allows to bring forward statistical estimators for the off-policy performance even under changing decision processes. The benefit is demonstrated in four non-stationary environments.", "questions": "I still have some questions, in particular:\n* In which timestep will the policy $\\pi'$ that is introduced in Assumption 1 be followed? Is it the policy that was obeyed in POMDP $M_i$ or $M_{i+1}$? From the later exposition, I now think that is is the policy followed in $M_i$. Can the authors confirm this?\n* It is not entirely clear how the bias calculated in Figure 5. I would appreciate if the authors could clarify this. If it is a stochastic variable, error bars could be added to the plot.\n", "limitations": "I think some of the limitations of this work are not sufficiently discussed. In particular, I wonder\n* how sample efficient the method is\n* how sensitive it is to violations of Assumption 1 and Assumption 2\n* whether it can be used to learn optimal policies in non-stationary settings \nI would have appreciated a discussion on some of these points. Societal impact is not discussed in the main paper; however, I also don’t see any negative implications of this work. \n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n* **Good Motivation.** I appreciate the motivation of this work with many examples such as motor war and past medical treatments that set the scene well. I agree that off-policy evaluation is an important problem in non-stationary decision processes.\n* **Fair Assumptions.** As far as I can tell, Assumption 1 may be reasonable for many of the applications mentioned, but is still very general.\n* **Theoretically grounded estimators.** The paper presents an estimator for the on off-policy performance in the future episode i+1, then removes its bias using instrumental variables regression and further introduces a technique to reduce the variance of this estimator. I think the overall techniques are valid in this context and result in a strong and consistent estimator.\n* **Experiments are promising.** The authors present experiments on four artificial domains, that show significant improvement when deploying their method.\n\n## Weaknesses\n* **Related work section could be extended.** I think the related work section could be a little more extensive than the 5 works currently referenced. Even if this are the works most closely related to this particular paper, a reader not so familiar with sequential decision making /RL could benefit from some pointers to important works on reinforcement learning / MDPs / policy evaluation in general, for instance.\n* **Notation was not always clear.** While the authors mostly did a good job with the formalization (admittedly, there are many notational objects), some notation is not entirely clear to me. For example, I don’t quite understand what $M_i(\\pi)$ should be in Theorem 1 or what the expectation over $\\beta_i, \\beta_{i+1}$ should be interpreted in the same Theorem. I am not entirely familiar with the conventions in this subdomain, so this might not be a concern for a more proficient reader.\n* **Comparison to single-sequence methods.** I agree that for some use-cases it is not possible to reset the entire environment and start a new sequence. However, for the RoboToy domain it would be possible to consider a life-long reward and reset it to the initial state several times. I would have found that comparison interesting in the experiment section. Even if there was some performance gap to the author's method, their approach still has the benefit that it can be applied to non-resettable environments.\n* **The confounder for the IV regression may also affect** $J_{i-1}$. IV requires that the confounder is independent of the instrument. When using time-series data, this means that it affects $J_i$ and $J_{i+1}$, but not $J_{i-1}$. I wonder if this is a realistic assumption in this case. However, I admit that I have previously seen this assumption being used in time series modelling, but maybe the authors can elaborate on why they think it’s plausible in this particular case.\n\n## Minor\n* In the definition below l. 203 (it would be great if all equations could be numbered), I am uncertain if really an expectation via the policies $\\pi'$ is taken. I don’t see how this definition should be understood, however I agree with the right-hand side.\n* The authors state assumption 2 is “standard” but do not provide any references. I think adding some references that make the same assumption could strengthen the argumentation.\n\n## Disclaimer\nThe reviewer admits that despite their best efforts, their knowledge in the domain of sequential decision making / RL is limited. Therefore they were not able to assess in particular: The novelty of the method, the significance of the problem for the domain, the empirical strength of the experiments.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "j6tevwUk2-8", "reviewer": "Reviewer_3Ye2", "summary": "This paper proposes an off-policy evaluation method for non-stationary environments. The authors distinguish between active and passive non-stationarity, and use double counterfactual reasoning and importance-weighted instrument-variable regression to obtain bias and variance estimation. Empirical comparisons show the superiority of the proposed OPEN method to other baselines in terms of predict future performances.", "questions": "1.\tI’m confused on the definition of “active non-stationarity”. For example, in the discussion of automated healthcare in Introduction, public health continuously evolving based on the treatments made available in the past. Wouldn’t be just state transitions as discussed in MDP? In an MDP, state changes and yet the transition function can stay stationary. In a similar manner, even the title “Action-Dependent Non-Stationary” can be confusing, as my interpretation of this is just state transition based on actions. Can the author please clarify what changes over time and what is non-stationary in a more rigorous mathematical definition? \n\n2.\tSimilarly, the authors claim that this is the first work towards off-evaluation for non-stationary environments and thus also in the empirical analysis, only baselines for passive non-stationarity or no-stationarity are used. However, to me, the active non-stationarity considered in this work is similar to that in reinforcement learning. Can the authors comment on the difference/contribution of your work and, for example, [1,2,3,4] for off-policy evaluation for reinforcement learning? I would also suggest to use these works as more stronger baselines for empirical comparison.\n\n\nReference\n[1] Xie, T., Ma, Y. and Wang, Y.X., 2019. Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. Advances in Neural Information Processing Systems, 32.\n[2] Thomas, P. and Brunskill, E., 2016, June. Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference on Machine Learning (pp. 2139-2148). PMLR.\n[3] Munos, R., Stepleton, T., Harutyunyan, A. and Bellemare, M., 2016. Safe and efficient off-policy reinforcement learning. Advances in neural information processing systems, 29.\n[4] Jiang, N. and Li, L., 2016, June. Doubly robust off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning (pp. 652-661). PMLR.\n", "limitations": "There is no discussion of limitation. Along with my questions regarding the difference between this work and reinforcement learning, one possible direction in the conclusion is to talk about the similarity and difference, and to what extent the results are generalizable to RL settings. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.\tThe structure of this paper is clear. This paper addresses an interesting question of off-policy evaluation under the presence of non-stationarity.\n2.\tThe presented algorithm is well grounded from Econ theories by utilizing instrument variables. \n\nWeakness:\n1.\tLiterature review is not adequate. Even with the content in the appendix, this is no discussion of off-policy evaluation for reinforcement learning or non-stationary multi-armed bandits. \n2.\tThe claim and the discussion of “active non-stationarity” is somewhat confusing (more on this later in Questions).\n3.\tThe authors seem to overstate their contribution.  \n4.\tBaseline methods are weak and not presenting state-of-the-art.\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_Osj7Q4FcWU", "reviewer": "Reviewer_crSm", "summary": "This paper studies the problem of policy evaluation when the environment is changing over episodes. The three ideas that are used to construct an accurate estimator is (1) importance sampling, (2) bias reduction, and (3) variance reduction. Under some reasonable assumptions, the authors show strongly consistency of the constructed estimator. Numerical experiments demonstrate that the proposed algorithm (called OPEN) performs well in several artificial environments.", "questions": "Please see the previous box.", "limitations": "This paper does not have any negative potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall I think this paper is novel. The setting where the environment may change over episodes is a reasonable extension of standard policy evaluation. There can be many other interesting motivating examples. In autonomous driving, the performance of the same policy on the same car may be different depending on how long the car is used.\n\n(1) Suppose we construct a new state-space as $S\\times M$, i.e., we view $M_i$ as an additional state. By doing this do we recover the standard policy evaluation setup where the environment is stationary?\n\n(2) Assumption 1 is somewhat restrictive. It says that the change of the environment depends only on the performance of the previous policy. What is the main challenge in the analysis without this assumption?\n\n(3) There are many related work studying importance sampling based off-policy TD-learning type of algorithms, such as [1,2,3,4], where various techniques are used to overcome the high variance issue in off-policy sampling. \n\n[1] Harutyunyan, A., Bellemare, M. G., Stepleton, T., & Munos, R. (2016, October). Q ($\\lambda $) with Off-Policy Corrections. In International Conference on Algorithmic Learning Theory (pp. 305-320). Springer, Cham.\n\n[2] Precup, D. (2000). Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, 80.\n\n[3] Munos, R., Stepleton, T., Harutyunyan, A., & Bellemare, M. (2016). Safe and efficient off-policy reinforcement learning. Advances in neural information processing systems, 29.\n\n[4] Espeholt, L., Soyer, H., Munos, R., Simonyan, K., Mnih, V., Ward, T., ... & Kavukcuoglu, K. (2018, July). Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In International conference on machine learning (pp. 1407-1416). PMLR.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6Sw2kC41lZf", "reviewer": "Reviewer_Gp7U", "summary": "The paper proposes an off-policy evaluation algorithm for non-stationary environments. Compared to prior work, where non-stationarity is assumed to be external to the agent's actions, this work proposes a setup where the non-stationarity can also come from the agent's own actions. Under a few assumptions, the paper derives a new algorithm which combines importance weighting and IV regression. The paper details a number of theoretical results regarding the consistency of the resulting estimate and shows the new estimate outperforms baseline methods which do not account for the non-stationarity resulting from actions.", "questions": "=== Assumption 1\n\nThe presentation of Assumption 1 is a little bit confusing. Does Eqn 1 hold for all pi' or a particular pi'? Given a fixed pi_1, pi_2, if Eqn 1 holds for both pi_1 and pi_2 we define the corresponding equality to be L_1, L_2, should we expect L_1=L_2 as well? From the fact that Assumption 1 implies the passive non-stationarity in line 169, it seems that we should also have equality between different pi's?\n\nThe notation P(J=J_{i+1}|M=m;pi') is also a bit confusing at first glance and might need some more explanations. Concretely, what does pi' mean in the notation? I presume that the notation's dependency on pi' means that we execute pi' at the i-th episode, and end in (i+1)-th episode -- in other words, the change from episode i to episode i+1 is due to the execution of policy pi' instead of pi. Is this correct?\n\n=== Theorem 1\n\nThe notation E_{beta_i,beta_i+1} is a bit confusing at first glance. Does it mean that we execute beta_i when in M_i, transition to a POMDP M_{i+1} and then execute beta_{i+1} on top of M_{i+1}? It is worth making the notation more clear and maybe spelling out the explicit interactions here.\n\nWhat does M_i(pi) mean exactly? Does it refer to the performance one obtains by executing pi in POMDP M_i? It is not immediately clear to me what's the difference between M_i(pi) and J_i(pi), are they both random variables? The two quantities on both sides of Theorem 1, are they random variables or fixed scalars?\n\n=== Theorem 2 and Assumption 3\n\nThm 2 is indeed quite a surprising result. It is better to offer some more explanations behind the intuition and result of Thm 2. The proof in Appendix D line, it is not immediately clear to me why E_beta[hat{J}_{i+1}|hat{J}_i] = J_{i+1}.\n\nIt also seems that the proof for Thm 2 does not require Assumption 2? It is more clear if during the proof when Assumption 1/2 are applied they are explicitly cited.\n\n=== IV regression for bias reduction\n\nOn a high level, Eqn 3-4 suggests that instead of directly carrying out regression X->Y, we should do something like\n\nX->g\ng->Y\n\nThe two stage process accumulates X into an IV g, and then use g to regress against Y to avoid bias. Is there more familiar example in RL which uses this kind of two time-scale like approximation? It might be helpful to spell out explicitly that here g is the IV. Is the intuition here essentially that by regressing X->g, we allow g to capture the structured information in X while decorrelates itself with random noise in X (in the paper's notation, decorrelate with input noise eta)\n\n=== Empirical analysis in Fig 4\n\nFig 4 is quite difficult to parse even after reading the texts below the plots. \n\nOn the right plot, is it the case that here green dots are essentially values produced by the function g? Is there a reason why the green dots still have quite some variations for any given episode, since I'd expect a smoother prediction function g.\n\nOn the right plot, I do not see black dots in the right plot and can only see green dots, which correspond to the prediction by the IV regression. \n\nOn the middle plot, is the black curve meant to show that IS weighted return generally has very high variance? The bottom curve I cannot see clearly, maybe better to use log scale.\n\n=== Fig 5\n\nIt is good that accounting for active stationarity reduces bias in general. However, in MEDEVAC plot on the bottom, when speed=2, Pro-WLS performs significantly better than OPEN in terms of MSE. Is this because OPEN is hurt by variance? All three methods should all arguably apply certain levels of importance sampling or normalized IS, why should OPEN be more sensitive to variance in this case? It might be useful to spell out an explicit algorithmic difference between Pro-WLS and OPEN to better see the distinction (juxtapose two algo boxes).\n\nBetter use log scale as some bars are barely visible.\n\n=== POMDP method comparison\n\nThe paper has discussed in a few places that a naive POMDP approach to modeling stationarity is not feasible, because the visitation assumption is violated. I think it'd be useful to run a naive POMDP algorithm and see how it behaves on these tasks, to see if violation of the theoretical assumption really hurts the performance in practice.", "limitations": "The paper has discussed a number of its limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "=== Strengths\n\nThe paper takes a first step towards addressing non-stationarity due to the agent's own interactions, and hence takes a relatively significant conceptual step forward compared to prior work. The paper is largely clear in its presentation, has fairly strong theoretical and empirical results that showcase the new algorithm's advantage over baselines.\n\n=== Weaknesses\n\nI think maybe the major weakness is that Assumption 1 feels quite strong, which on a high level, requires that the meta-transition matrix of the agent's performance looks like a MDP transition matrix. Though the assumption does capture the fact that \"the way the changes happen is fixed\", it seems to be quite restrictive in an intuitive sense. I would appreciate more discussion on the limitation of this assumption and how maybe some applications do not fit into such an assumption.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept