Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.

(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?

(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?

(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. 

[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.

[2] Precup, D. (2000). Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, 80.

[3] Munos, R., Stepleton, T., Harutyunyan, A., & Bellemare, M. (2016). Safe and efficient off-policy reinforcement learning. Advances in neural information processing systems, 29.

[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.

questions: Please see the previous box.
limitations: This paper does not have any negative potential negative societal impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: === Strengths

The 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.

=== Weaknesses

I 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.
questions: === Assumption 1

The 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?

The 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?

=== Theorem 1

The 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.

What 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?

=== Theorem 2 and Assumption 3

Thm 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}.

It 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.

=== IV regression for bias reduction

On a high level, Eqn 3-4 suggests that instead of directly carrying out regression X->Y, we should do something like

X->g
g->Y

The 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)

=== Empirical analysis in Fig 4

Fig 4 is quite difficult to parse even after reading the texts below the plots. 

On 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.

On 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. 

On 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.

=== Fig 5

It 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).

Better use log scale as some bars are barely visible.

=== POMDP method comparison

The 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.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths:
1.	The structure of this paper is clear. This paper addresses an interesting question of off-policy evaluation under the presence of non-stationarity.
2.	The presented algorithm is well grounded from Econ theories by utilizing instrument variables. 

Weakness:
1.	Literature 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. 
2.	The claim and the discussion of “active non-stationarity” is somewhat confusing (more on this later in Questions).
3.	The authors seem to overstate their contribution.  
4.	Baseline methods are weak and not presenting state-of-the-art.


questions: 1.	I’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? 

2.	Similarly, 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.


Reference
[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.
[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.
[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.
[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.

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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: ## Strengths

* **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.
* **Fair Assumptions.** As far as I can tell, Assumption 1 may be reasonable for many of the applications mentioned, but is still very general.
* **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.
* **Experiments are promising.** The authors present experiments on four artificial domains, that show significant improvement when deploying their method.

## Weaknesses
* **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.
* **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.
* **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.
* **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.

## Minor
* 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.
* 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.

## Disclaimer
The 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.

questions: I still have some questions, in particular:
* 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?
* 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.

limitations: I think some of the limitations of this work are not sufficiently discussed. In particular, I wonder
* how sample efficient the method is
* how sensitive it is to violations of Assumption 1 and Assumption 2
* whether it can be used to learn optimal policies in non-stationary settings 
I 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.
review_title: null

Meta-review: metareview: The paper addresses off-policy evaluation for non-stationary environments. A key distinction from the prior work, highlighted by multiple reviewers is the aspect that non-stationarity can come from the agent’s own actions (as opposed to just the exogenous factors). The paper uses a combination of importance sampling and bias and variance reduction to show strong consistency of the derived estimator. 

There are certain assumptions that were considered too restrictive by a reviewer (re: Meta-transition matrix of the agent and the MDP transition matrix). The authors in their rebuttal provided some insight into why the assumption is necessary and why it makes sense from a pragmatic point of view. I request author’s to further expand upon the discussion on this assumption in the final copy.

Another concern raised by a critical reviewer focused on novelty, especially in comparison to work in MDPs (mostly due lack of clarity in the definition of active non-stationarity). The critical reviewer, however, was satisfied about other questions and concerns he had raised.

Overall, this is an interesting work with good theoretical and empirical insights and the reviewer pool leans towards acceptance.

confidence: Certain
Decision: Accept