- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The authors study how to identify a POMDP from a single trajectory without resets. They explain how counterfactual samples can help identify the underlying model and provide a concrete approach for deterministic POMDPs with sufficiently small transition and observation corruptions. Their algorithm uses action-observation sequences that identify the hidden state to recover the number of states and the uncorrupted model. They provide theoretical recovery guarantees and synthetic experiments.
Critical strengths
-
I think the paper has a beautiful presentation. It flows well and develops an intriguing argument.
-
Many applications of counterfactual reasoning assume access to counterfactuals, while obtaining them is itself a substantial obstacle. I particularly appreciate that this paper addresses that obstacle and provides a concrete way to obtain the relevant information along a single trajectory, under its assumptions.
Critical weaknesses
-
It is unclear to me how broadly the assumption of a “slightly corrupted” deterministic POMDP applies in practice. This seems potentially restrictive for environments with intrinsic stochasticity. Furthermore, the allowable corruption level in the worst-case guarantee becomes very small as the number of states grows. Concrete examples of practical settings where these assumptions are plausible would help.
-
The sample-complexity bounds are quite large, while the experiments suggest substantially better performance on the examples considered. Although the authors acknowledge this gap, it would be helpful to identify the main sources of looseness in the analysis and discuss whether they could be tightened to better explain the empirical results.
-
It is not clear to me how to choose the filtering threshold and history/test lengths without knowing the underlying model. The experiments show that the filtering threshold can materially affect recovery, including in the noiseless setting, so practical guidance on parameter selection would be useful.
-
The connection to policy evaluation and control remains underdeveloped. Although model identification is the stated focus, it would help to explain how the recovered model could be used for these tasks and how estimation error and residual corruption would affect value estimates or policy quality. The reliance on uniformly random actions also raises questions about extending the method to adaptive control. A discussion of these obstacles and the relationship to existing model-based POMDP reinforcement-learning methods would clarify the significance for decision-making.
Questions for authors
-
Can the authors give concrete practical examples where the near-determinism and corruption assumptions are reasonable?
-
In Appendix D.3.4, the Euclidean row-error bound uses , where is the vector of centered observation counts and . Could applying a Hilbert-space Freedman inequality directly to this vector avoid the explicit factor? If so, how much would this tighten the resulting sample-complexity bound?
-
Could the authors quantify how much of the sample-complexity gap on their experimental domains comes from the lower bound in Appendix D.6.1? Would a sharper uniform lower bound on block-occurrence probabilities, accounting for all action paths that produce an uncorrupted anchor history, substantially improve these guarantees?
-
How should the filtering threshold and history/test lengths be selected when the underlying model is unknown? Could these choices be guided by the observed data?
-
What would be needed to combine this identification procedure with policy evaluation or control in the corrupted environment? In particular, could an optimistic control approach accommodate its exploration requirements, and what additional analysis would be needed for value-error or regret guarantees?
2 comments
I thank the authors for their effort in answering my questions and their revisions. I maintain my positive score.
Response to LhQx
Thank you for the helpful suggestions and feedback.
The purpose of stating Theorem 3 (and its tighter version, Theorem 8, in the appendix) is to justify that CfactSP is robust against some form of corruption noise, and does not promise tightness in the paper. As a result, there are two forms of looseness in the stated bound: (1) looseness introduced by the worst-case assumptions about the deterministic POMDP being learned under corruptions and (2) looseness that is inherent to the proof technique even under the worst-case constant assumptions.
One example of the first includes the fact mentioned about the worst-case bound in appendix F.6.1. (previously D.6.1) The simulated domain Espresso, which has a lower bound to the “closed, pod in machine” state has one unique path through the state-transition graph to this state and one unique anchor sequence, and the suggested approach yields the same lower bound probability as the one calculated in appendix F.6.1. While this could be a source of looseness for the other environments, we do not believe this causes orders of magnitude sample-inefficiency in analysis.
Examples of the second include:
Our focus in this paper is primarily on learning a model, which can then be used by a planning system, and we assume a largely two-phase process of learning and then planning. We believe the utility of this approach allows the model to be reused as the task changes. Reliance on uniform random actions as part of the learning phase is a common assumption for learning systems. For the problem of learning linear dynamical systems, analysis is done by drawing i.i.d. random samples from normal Gaussians (the analog to uniform random for unbounded real domains) for real vector-valued control inputs [2].
As you suggest, one simple control strategy is to form a policy against the learned deterministic model and to maintain a belief over the latent state. The agent may notice if the model is corrupted, because discrepancies introduced by noise would force the belief state to collapse (lose support on all states). In a situation like this, the agent could re-initialize the belief to uniform and start again. One could then do an analysis on the performance of this policy and generalize standard statistical RL arguments/algorithms (see [3] for an example) for regret bounds. However, this work is beyond the scope of this paper.
Furthermore, perhaps a Bayes adaptive approach could be used to eliminate the assumed division between learning the model and then planning. We believe that our approach to learning the model could be a part of the inner inference process, but that next step is beyond the scope of this paper.
[1] Y. Peng, L. Zhang, and Z. Zhang, “Statistical Efficiency of Distributional Temporal Difference Learning,” in Advances in Neural Information Processing Systems, Curran Associates, Inc., 2024, pp. 24724–24761.
[2] M. Simchowitz, H. Mania, S. Tu, M. I. Jordan, and B. Recht, “Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification,” May 24, 2018, arXiv: arXiv:1802.08334.
[3] D. J. Foster, N. Golowich, and Y. Han, “Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient,” in Proceedings of Thirty Sixth Conference on Learning Theory, PMLR, Jul. 2023, pp. 3969–4043. Accessed: Nov. 12, 202.