Future-Dependent Value-Based Off-Policy Evaluation in POMDPs

Summary

- This paper proposes a novel future-dependent value function to study the problem of OPE in POMDPs with function approximations. - A new Bellman-style conditional moment equation is derived for the future-dependent value function, based on which the value function can be learned via finite sample using minimax learning methods. - Under certain completeness, realizability, and overlapping assumptions, a finite sample theoretical bound is derived for the proposed minimax learning algorithm. The paper also provides experimental evidence to empirically evaluate the performance of the algorithm.

Strengths

- The paper first proposes using "future-dependent value function" to solve the problem of OPE in POMDPs, which is a critical problem in offline RL literature. The resulting method potentially overcomes the curse of horizon in learning POMDPs. - The presentation of the paper is clear, e.g., using memory-less policy to illustrate the idea in the main text. The connections with highly related works, e.g., OPE in MDPs, OPE in confounded POMDPs, system dynamics learning, spectral learning, are well-discussed. - The statistical theory regarding minimax learning and OPE is sound, and empirical evaluations are also provided.

Weaknesses

- The idea of incorporating future information as parts of value functions for POMDPs is not new, e.g., [1], even though I still appreciate that this paper first attempts using such methods for OPE in POMDPs. - The main part of the statistical theory regarding minimax estimation and OPE is standard given that various customized assumptions (completeness, realizability, and certain overlapping conditions) hold. **References:** [1] Uehara M, Sekhari A, Lee J D, et al. Provably efficient reinforcement learning in partially observable dynamical systems[J]. Advances in Neural Information Processing Systems, 2022, 35: 578-592.

Questions

- Regarding the completeness assumption (2b), how can it be justified in the examples provided in the paper, e.g., HSE-POMDPs? I would appreciate it if the authors could provide more detailed clarifications on that. - A novelty of the paper is using both history and future proxies in POMDP OPE. Is it possible to give a more quantitative trade-off between the usage of the history part and the future part (probably problem-dependent) towards optimal identifying and evaluating the policy value? - Another seemingly key assumption in the presentation of the paper is that the offline data from an infinite horizon POMDP has a stationary distribution. Even mentioned in the main texts, I still wondering if the algorithm and theory can be directly extended to the more general non-stationary settings.

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The above points in Questions are potential limitations.

Summary

The paper introduces a novel model-free approach for off-policy evaluation (OPE) in partially observable Markov decision processes (POMDPs). The authors propose the use of future-dependent value functions (FDVFs) to capture the latent states by leveraging future observations. They provide a Bellman-like equation and a minimax algorithm for FDVFs, along with a PAC analysis.

Strengths

+ The paper addresses a crucial challenge of handling real-world data that are partially observable and difficult to collect. + The proofs seem to be correct.

Weaknesses

- The readability of the paper can be enhanced, particularly by providing a more intuitive motivation and explanation of FDVFs. The paper is densely written with numerous references to other sections and papers, which disrupts the flow. It is important to clearly state the main assumptions, problem, and overall approach in an intuitive manner. - The main weakness of the paper is the experiments section, which only considers a simple environment (CartPole) with partial observability achieved by adding Gaussian noise. - Additionally, the proposed method utilizes a limited history (3-step) and one-step future, which may not sufficiently demonstrate its effectiveness in mitigating the curse of horizon. - Furthermore, it is important to compare the proposed method with other OPE methods designed for POMDPs, as well as those using stacked observations.

Questions

In Remark 3, "heir proposal" seems to be a typo; could you please clarify? Instead of SIS, could SIS with resampling (a.k.a. SIR, SIS/R, SMC, particle filtering) be utilized instead?

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

No

Summary

The paper considers off-policy evaluation for POMDPs, where the data is collected using a behavior policy that is only dependent on the observations available to the evaluation policy as well. The work defines a new "future-dependent" value function and its associated Bellman equations that are used to define a new set of conditional moment equations. While the existing estimators for this setting suffer from the curse of the horizon, the proposed method does not. Overall, I think it is an interesting idea, though there are some points that can be clarified better.

Strengths

- Interesting idea of using future-dependent value functions. Though some prior works have touch upon similar ideas, the proposal is different enough. - OPE in POMDP is a common topic of interest and might be relevant to a lot of people.

Weaknesses

- More discussions about Assumptions could be helpful - Experiments can be improved

Questions

1. Staring at Definition 1, I am wondering if the importance-weighted return $\rho G$ extracted from F, is a valid instance of $g_V(F)$? (I understand that propensity scores are not a part of $F$, but let's say data is augmented to make them part of $F$). Complimentarily, some discussion + examples around Definition 1 about the existence of $g_V(F)$ would also be fruitful. Line 211 kind of gets at it, but wraps it up in technical jargon. 2. If yes, it is not intuitive to me why would the proposed method break the curse of the horizon. Even if the answer to the above is no, I am wondering if there is a price being paid in terms of the "curse of the future", i.e., the length of $F$? As mentioned in remark 4, if address the problem at hand can be addressed by substituting states with the history observed so far (although $\mu$ would only depend on the current observation under the assumptions made earlier around Eqn 3 and 4.) and that is cursed by the length of the horizon, why wouldn't the proposed method be cursed by the length of the future? 3. When multiple $g_V$ functions exist that satisfy the required condition, is there any reason to prefer one over the other? Can additional regularization be added to bias the solution towards one of them? 4. Optional: In my opinion, section 4 does not contribute much as once the conditional moment equations are obtained, the rest is a standard adaption of existing techniques. I think it would be far more beneficial to a reader to have more discussion + positive/negative examples about the conditions for invertibility and existence, and what they imply in practice.

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.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

4. It would be beneficial to add another baseline, similar to naive minimax OPE, albeit with history as the state (with hyper-parameter tuning done similarly to the proposed method to choose the ideal history length). Minor: - Sentence phrasing in Line 129 suggests a model-based approach, whereas the main method is model-free - Eqn after Line 135 has a typo in subscripts. - Line 199: typo

Summary

The paper addresses the problem of off-policy evaluation in POMDPs. The main idea is to modify the Bellman equation by incorporating future and historical observations instead of relying on unobserved states. This new future-dependent value function allows for policy evaluation without the need for unobserved states. The paper explores the sufficient conditions and conducts finite sample analysis based on the modified Bellman equation. The proposed algorithm is demonstrated through a numerical experiment on CartPole, showing improved prediction error.

Strengths

Motivation and clarity: - The paper acknowledges the common occurrence of partial observability in real-world scenarios and the challenges it poses for off-policy evaluation, making it a relevant and long-standing research problem. - The paper is well-written and easy to follow. Novelty: - The proposed methods are clever and remarkably simple. - The discussion on the conditions for observability and invertibility provides theoretical insights into the occurrence of "magic" (evaluation without observing unobserved states). The entire reasoning process almost feels like a result from a standard RL textbook.

Weaknesses

My only concern is the practicality of the proposed algorithm. The experimental results are not sufficiently convincing, and conducting more extensive studies, including (1) more baselines and (2) more complex environments, particularly real-world POMDP applications, would greatly enhance the paper.

Questions

Questions: 1. The definition of $\mathcal{F}$ for future observations is not consistent. In the equation after line 135 (also Figure 1), $F$ consists of $M_F$ observations and $M_F-1$ actions. However, in lines 142-147, $F$ consists of $M_F$ observations and $M_F$ actions. Which one is actually used in the experiment? 2. (Question regarding the experiment, after reviewing Appendix H.3) Suggestions and Typos 1. Typo: In the equation after line 135, $(O_{-M_H:t-1}, A_{-M_H:t-1})$ should be $(O_{t-M_H:t-1}, A_{t-M_H:t-1})$. 2. Typo: In line 199, remove "heir proposal." 3. It would be interesting for practitioners to observe the prediction error as $M_F$ and $M_H$ vary. Exploring the trade-off between more accurate prediction through increased history/future observations and the complexity of the function space would be an intriguing avenue for future research. 4. An extension to attention-based neural networks as the function space would be extremely interesting.

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.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

n/a

Summary

The paper proposes a new OPE method for in POMDPs. The paper first introduces a new future-dependent value function and derive a new Bellman equation for the future-dependent value functions. Then, the paper proposes an estimator to learn such future-dependent value function. The paper provides theoretical results on the finite sample guarantee and a simple empirical demonstration that the estimator performs well in a partial observable Cartpole environment.

Strengths

The paper introduces a new estimator for POMDPs, which is claimed to be the first model-free method that enable general function approximation and does not suffer from the curse of horizon. I think the paper would have a significant contribution to the OPE community. (Note that I am not familiar with the literature on OPE for POMDPs, so my evaluation is sorely based on the related work section in the paper). The future dependent idea is new, as far as I know. The paper also sufficiently discuss related works on OPE for POMDPs and the corresponding minimax estimator for fully observable MDPs. It is also good that the paper provides many examples on when the conditions hold in different settings such as tabular setting, and the connection between these conditions to conditions in existing works. I didn’t check the proof in the appendix carefully, but the theoretical results are reasonable.

Weaknesses

I think one weakness of the paper is the presentation clarity. It introduce many notation so it requires careful reading at first. I understand that these notations are necessary but I think some improvement can be made to make the paper easier to read. Some steps/derivations are not very clear to me: - Are all expectation in the paper, when not explicitly specified, taken with respect to the offline data sampled from the data collection policy $\pi_b$? - The expectation in definition 1 is taken w.r.t. the data from the data collection policy? What is the intuition behind the definition? If we can sample history from the data collection policy, there exists some function that can map the history to the true return? - In Line 218, “note that right hand side of Eq. 3 is a function of Z,S instead of H”. What is Z here? - The paper is about OPE for short-memory policies, but the main text only describes methods for memory-less policies (for simplicity). I think the paper can still briefly summarizing what is different for short-memory policies. Does the length of the memory affect the finite sample bounds? - The paper mentions that it addresses the curse of horizon, however, isn't this because (1) we only consider short-memory policies and (2) assume future F contains sufficient information about S? In the experiment, the base policy (I guess it is the data collection policy?) is defined on (S,A) but I think the method requires $\pi_b(A|O)$. Did I misunderstand something here?

Questions

I would appreciate it if the authors can answer my questions listed in the weakness section, especially on the curse of horizon.

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

The authors adequately addressed the limitations. They provide many extension of the proposed method in different settings in the appendix (e.g. for finite horizon).

Response to Authors

Thank you for the detailed answers. I’ve read the author response and other reviews and I will keep my evaluation and rating.

Response to Authors

I have read the rebuttal and the comments from other reviewers. Thank you for the efforts dealing with my concerns and questions. I will keep my score as 7.