Abstract Reward Processes: Leveraging State Abstraction for Consistent Off-Policy Evaluation

Summary

The authors introduce a new framework that groups the states with a similar reward, hence reduces variance of any applied OPE estimator.

Strengths

The framework is technically sound, well discussed, the analysis is on point and addresses important questions, for example that regardless of the choice of state abstraction function \phi, the overall framework remains asymptotically consistent. The discussion on how the framework translates to existing OPE methods when varying its parameters (\phi, c) help show where the improvements of this framework lie. The experiments are complete and show a strong empirical performance of this method.

Weaknesses

Minor: [L548, L560, L586, L600, L609] "See Appendix B" is obsolete, we are already in Appendix B.

Questions

In [L212] you claim this is the first model-based OPE method that converges to a true policy value without any model class assumptions. How does your method compare to action clustering method of Peng et al. (2023)? This method factors action space instead of the state space, and regardless of the model class, it seems to converge to a true policy value. In [L304], you suggest that performance can be improved even further by applying estimator selection methods. Moreover, in [L250], you mention there is no approach to discovering good abstraction functions \phi. The recent work of Cief et al. (2024) might solve both these issues. References: Peng, Jie, Hao Zou, Jiashuo Liu, Shaoming Li, Yibao Jiang, Jian Pei, and Peng Cui. “Offline Policy Evaluation in Large Action Spaces via Outcome-Oriented Action Grouping.” In Proceedings of the ACM Web Conference 2023, 1220–30. WWW ’23. New York, NY, USA: Association for Computing Machinery, 2023. https://doi.org/10.1145/3543507.3583448. Cief, Matej, Michal Kompan, and Branislav Kveton. “Cross-Validated Off-Policy Evaluation.” arXiv, May 24, 2024. http://arxiv.org/abs/2405.15332.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors extensively discuss the limitations throughout the work, for example, in Conclusions.

Summary

The paper introduces a new framework, STAR, for off-policy evaluation (OPE). OPE uses a chain with rewards (MRP) to conduct the evaluation. The challenge of this methodology is that the MRP estimation can introduce bias, given the shift between the behavior policy and the policy for evaluation. STAR is designed to address this challenge. STAR projects continuous state space to a tabular space and introduces the abstract reward process (ARP), which refers to the MRP over an abstract state space. The tabular abstract state space reduces the difficulty of reward prediction, thus eliminating the model class mismatch in prediction. It is proved in the paper that projecting states to a discrete space preserves the return.

Strengths

* The paper makes good contributions by proposing a new framework for off-policy evaluation. The proposed method is analyzed in detail with both mathematical proofs and empirical evaluations. * The introduction clearly lists the challenges and contributions, as well as provides a subsection for an overview of the new method. The way the introduction is organized tunes to be helpful for better understanding. * For the introduced step, abstracting continuous states with a tabular space, the paper explains the advantages clearly. The paper also provides mathematical proof to explain why this step is not considered as a source of error.

Weaknesses

* Theorem 3.1 proves why state abstraction preserves the return with a known reward function on the abstraction state space, but it remains unclear how the state abstraction increases the difficulty of learning the transition model for predicting the reward and the next state, and possibly also introduces stochasticity. Assuming the true MDP has $P(r_0, s_1| s_0, a_0) = 1$ and $P(r_1, s_3|s_1, a_0)=1$, if the state abstraction projects $s_0$ and $s_1$ to the same representation $\phi_0$, which is possible because the latent space is tabular. Then, the model will have to simulate a stochastic transition with probability $P(r_0, s_1 | \phi_0, a_0)=0.5$ and $P(r_1, s_3 | \phi_0, a_0)=0.5$. Therefore, it seems how accurate the evaluation is heavily depends on how good the state abstraction is. If so, it would be good to point out in the paper.

Questions

Please see the concern above

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes

Summary

This paper studies the problem of Off-Policy Evaluation (OPE), which consists of estimating the value of a policy $\pi_e$ from an input dataset generated from another behaviour policy $\pi_b$. One naive way of constructing the estimated return of $\pi_e$ would be to compute its associated empirical Markov Reward Process (MRP) in the MDP, then apply importance sampling to it. Instead, the technique proposed in the paper is to apply importance sampling to an abstract MRP obtained via some discrete abstraction function. This technique has been validated with theoretical results, and with an experimental comparison against other baselines.

Strengths

(Idea and contribution) The core idea, that is marginalizing states into abstract MRP, is simple. However, it requires special care in selecting appropriate abstract representations that allow lossless evaluation of arbitrary policies. As confirmed by Theorem 3.1, this is indeed the case for the ARP defined in the paper (though it should be noted that this strongly relies on $\gamma = 1$). From Theorem 3.1 all the other results follow, which verify that the proposed technique is sound for *any mapping function*. The fact that "actions propagate through the abstract state transitions" (line 227) is also a very interesting addition, that contributes to the application of importance sampling. Summarizing, the theory developed in the paper is an elegant display of the abstraction process for OPE, and a sound use of HRL principles. (Evaluation) The technique has been compared with a good number of relevant baselines from the literature. The results show that the proposed estimators have competitive or better performance than their competitors. The authors also reported the median estimator. Even though it is not always the best estimator, this addition allows to have a clearer picture, and it was evaluated positively. (Presentation) The quality of presentation is high. Each new technical definition is well motivated, and the paper is reasonably self contained. (Reproducibility) The authors provided the full source code at the time of submission. The hyperparameters are also provided.

Weaknesses

1. The theoretical results show that the method is sound and any estimator constructed as explained in the paper is an unbiased estimate of the true value. However, the paper does not provide any theoretical result regarding the reduction in variance, which is the second motivation of this work. This is only confirmed experimentally in some domains. 1. No finite samples analysis has been conducted. Thus, when considering datasets of finite size, no theoretical result regarding the approximation error is available. 1. The method assumes to explicitly know the behaviour policy that generated the data. This is a strong limitation that has been also listed by the authors in the limitation section. This did not contribute heavily to the final score. Minor: - There are some typos in the use of z and z' in equation (2) and in the proof of Theorem 3.1. - If accepted, I suggest to use the additional page for explaining the missing details of the experimental evaluation, such as: - How is the MSE for OPE exactly defined - How is the variance-bias measure is constructed for Figure 3. - List Algorithm 1 in the main body

Questions

4. How did you obtain the probabilities of the behaviour policy for the ICU sepsis dataset? 5. Which of the baselines assume complete knowledge about the behaviour policy? The authors may also address any of the points raised above.

Rating

8

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

The authors listed all the most important limitations of this work. The contribution has no direct societal impact and it does not require further discussion regarding negative impact.

Reply

I would like to thank the authors for their reply. The reply addressed my concern. After reading the reply and other reviews, I increased the score.

Comment by Authors | Errata

We would like to highlight that in its current form Theorem 4.3 as stated in in our paper [Chaudhari et al., 2024] is false. Specifically, one step in its proof does not hold, invalidating the proof. We note this error along with a suggested corrected in the follow [errata document](https://shreyasc-13.github.io/docs/ARP_errata.pdf). The rest of the paper and its theoretical and empirical results remain unchanged.