acceptodds
Under review as a conference paper at ICLR 2027

Counterfactuals Without Resets: Identifying POMDPs

Abstract

Many problems require estimating a world-dynamics model from interaction data where the observations do not uniquely reveal the underlying state. Our goal is to estimate time-homogenous discrete Partially Observable Markov Decision Processes (POMDPs) from a single trajectory of action and observations without any resets.We find that access to counterfactual samples provides sufficient conditions to learn a larger class of POMDPs.Counterfactual samples are samples from the joint distribution of all possible observations sequences obtained from executing multiple action sequences from the same state.In general, when gathering data from a single trajectory, it is not possible to gather counterfactual samples for a partially observable system.We therefore restrict our attention to the class of POMDPs that can be described as deterministic finite-state machines corrupted with bounded transition and observation noise. We show that deterministic machines contain anchor sequences, which can fully determine the underlying state when observed. We provide an algorithm, Counterfactual Successive Projection (CfactSP), that uses ideas from tensor decomposition and nonnegative matrix factorization to leverage these anchor sequences to identify the POMDP from a single reset-free data sequence. CfactSP is provably robust to a bounded number of corruptions in transition and observations. Empirical results suggest sample-complexity is substantially lower in practice than the guaranteed bound.

Primary area:
learning on time series and dynamical systems
Keywords:
Counterfactuals, POMDPs, Learning without Reset

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_LhQXOpenReview ↗
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
  1. I think the paper has a beautiful presentation. It flows well and develops an intriguing argument.

  2. 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
  1. 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.

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

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

  4. 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
  1. Can the authors give concrete practical examples where the near-determinism and corruption assumptions are reasonable?

  2. In Appendix D.3.4, the Euclidean row-error bound uses ∥M∥2≤d∥M∥∞\lVert M\rVert_2 \leq \sqrt{d}\lVert M\rVert_\infty, where MM is the vector of centered observation counts and d=∣O∣Ld=|\mathcal O|^L. Could applying a Hilbert-space Freedman inequality directly to this vector avoid the explicit d\sqrt{d} factor? If so, how much would this tighten the resulting sample-complexity bound?

  3. Could the authors quantify how much of the sample-complexity gap on their experimental domains comes from the lower bound αβ=((1−β)/n)W\alpha_\beta=((1-\beta)/n)^W 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?

  4. 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?

  5. 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
AuthorsOpenReview ↗

Response to LhQx

Thank you for the helpful suggestions and feedback.

The sample-complexity bounds are quite large... ...it would be helpful to identify the main sources of looseness...

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

In Appendix D.3.4, the Euclidean row-error bound uses… 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?

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:

  1. The usage of scalar Freedman in Section F.3.4 (D.3.4 as mentioned by review): Applying Hilbert-space Freedman (Peng et al. [1], thank you for alerting us to the existence of a Hilbert-space Freedman!) instead improves exponential dependence on the number of observations to logarithmic in Theorem 3 and saves an order of magnitude in the stated comparison for the numerical simulations in Section 5.
  2. All corruptions are conservatively considered for the perturbation of each anchor. Unlike the former source of looseness, this one is difficult to fix without restructuring the whole proof. Improving loose proof steps like these is the subject for future work.

The connection to policy evaluation and control remains underdeveloped.....

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?

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.

I thank the authors for their effort in answering my questions and their revisions. I maintain my positive score.

Reviewer_vH3fOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies how to identify a finite POMDP from a single trajectory without resets or a known state count. It first gives a recovery result with access to counterfactual test distributions, then proposes CfactSP for deterministic models with small amounts of corruption. The algorithm combines anchor histories, tensor features, successive projection, and deterministic rounding to recover the underlying model.

Critical strengths

I like the connection between anchor histories and the geometry of the system dynamics matrix. The analysis goes beyond an independent sample setting by handling overlapping windows and errors in the selected histories.

Critical weaknesses

The definition of minimality in Section 2 does not ensure that states can be distinguished through observations. Appendix C adds the necessary separation and rank conditions, but these should appear in the main result. Section 3.1 also states an incorrect ordinary rank inequality, whereas the appendix uses the appropriate Kruskal rank bound. Finally, the claim that counterfactual samples are “necessary and sufficient” seems stronger than what the results establish.

I’m not yet convinced about the added benefit of the tensor lift. With anchors, the state rows already appear as vertices of the original SDM hull. The lift helps address a limitation of successive projection, but a comparison with direct vertex extraction or a C=1C=1 ablation would clarify what it adds in practice.

Parameter selection remains unclear when the model is unknown. The algorithm does not take the state count as input, but valid choices of K,L,CK,L,C and the frequency threshold depend on unknown structural quantities. The appendix establishes that suitable choices exist, but does not give a clear procedure for choosing them from data. I could not find the actual K,L,CK,L,C settings used in the experiments.

The four domains contain only three to five states. Larger examples and comparisons with alternative learning methods would make the empirical case stronger. Runtime and memory measurements would also help show whether the method remains practical as the history and test spaces grow.

Questions for authors

How are K,L,CK,L,C and the frequency threshold chosen without knowing the state count or anchor lengths?

How do recovery rates and computational costs change as anchors become longer or rarer?

1 comment
AuthorsOpenReview ↗

Response to vH3f

Thank you for the helpful suggestions and feedback.

The definition of minimality in Section 2 does not ensure that states can be distinguished through observations.

We have updated Section 2 to be reflective of the appendix assumptions, e.g. that for every pair of states there exists a sequence of actions of at most length L that produce distinct observation distributions when starting from those two states.

Section 3.1 also states an incorrect ordinary rank inequality, whereas the appendix uses the appropriate Kruskal rank bound.

We have updated the discussion of the main paper to reflect the true Kruskal rank bound.

I’m not yet convinced about the added benefit of the tensor lift. With anchors, the state rows already appear as vertices of the original SDM hull. The lift helps address a limitation of successive projection, but a comparison with direct vertex extraction or a (C=1) ablation would clarify what it adds in practice.

This ablation would require an algorithm to compute a convex hull of a very degenerate set of points (not in general position) in very high dimension (|A||O|^L). A full understanding of this question has not been established theoretically or with practical algorithms. We updated the paper to reflect the current state of progress on this problem.

The appendix establishes that suitable choices exist, but does not give a clear procedure for choosing them from data. I could not find the actual (K,L,C) settings used in the experiments.

We have included the (K, L, C) parameters used in the experiments in Table 1 of appendix B (previously appendix A).

How do recovery rates and computational costs change as anchors become longer or rarer?

We added a runtime/space discussion in Appendix F.1.4 (previously appendix D.1.4). As you might expect, there is exponential dependence for runtime and space on parameters K and L. The dependence on anchor length K can be via Corollary 2 on F.8.2 (now D.8.2). When working through the constants, the sample complexity varies exponentially with K, and the tolerable noise is divided on the order of exponential in K.

The four domains contain only three to five states. Larger examples and comparisons with alternative learning methods would make the empirical case stronger. Runtime and memory measurements would also help show whether the method remains practical as the history and test spaces grow.

We include wallclock runtime and memory estimates in Table 1 of appendix B (previously appendix A).

In general, HMM/POMDP learning is known to have high computational and sample complexity due to their connection to cryptographic problems conjectured to be NP-hard [1]. This is because all algorithms need to consider exponentially increasing numbers of sequences of symbols to learn a predictive model of the system. This means that only relatively simple problems are within practical reach. In future work, we will consider factoring and other structural assumptions to make larger problems tractable.

Finally, the claim that counterfactual samples are “necessary and sufficient” seems stronger than what the results establish.

We have adjusted all language to reflect that counterfactuals are sufficient to identify time-homogeneous POMDPs with well-connected state spaces, but not necessary.

[1] E. Mossel and S. Roch, “Learning nonsingular phylogenies and hidden Markov models,” The Annals of Applied Probability, vol. 16, no. 2, pp. 583–614, May 2006, doi: 10.1214/105051606000000024.

Reviewer_NDquOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The submission proposes an approach to identify (up to state permutations) the dynamics and observations emission functions of a finite POMDPs that satisfies certain conditions including determinism and forms of connectivity that guarantee "anchor sequences".

The approach is generally based on identifying situations at different timesteps that are guaranteed to be associated to the same underlying state, and treating them as independent samples from the same starting conditions, from which transition and observation emission parameters can be estimated directly. The authors claim that this approach allows the estimation of counterfactual probabilities.

The approach is evaluated on a synthetic environment with different degrees of stochasticity, and demonstrates empirical performance that is much better than the derived theoretical bounds.

Critical strengths

The setting without resets is complex and realistic:

Many model and policy learning algorithms assume resettable environments, which limits applicability especially in partially observable settings.

The submission contributes to a very complex identifiability problem:

The submission contributes strict guarantees to the problem of POMDP identifiability. Such a theoretical analysis and guarantees can represent meaningful contributions to a field that is often limited to empirical approaches and evaluations.

Critical weaknesses

Potential issues with the treatment and definition of counterfactuals:

The authors define counterfactuals in a way that does not fully align with the literature of causal inference. Counterfactuals are described and equated in the submission to the process of sampling a different trajectory when conditioned on the same starting state. However, proper counterfactuals must also maintain the same exogenous process in all trajectories. This is not guaranteed by simply conditioning on the same starting state. E.g., consider an environment where a coin H,T{H,T} is flipped at every timestep, and the agent can choose two actions X,Y{X,Y} that do nothing to affect the coin toss. Given an observed transition (H,X)−>H(H,X) -> H, the counterfactual had the agent chosen action YY will still result the same transition (H,Y)−>H(H,Y) -> H deterministically. Whereas according to the author's definition, simply conditioning on the same starting state results in a uniform distribution.

This issue can be fundamentally resolved by the deterministic assumption, but the authors should clarify the correct definitions, the relationship with the deterministic assumption, and consider how the corrupted setting still reintroduces stochasticity that breaks the definition of counterfactuals.

The corrupted setting is not fully clear, and possibly ill-defined in a few ways:

The corrupted-POMDP setting is framed as if the underlying POMDP is deterministic while the agent actually interacts with a corrupted version. But the POMDP is whatever the agent interacts with. If the interactions are stochastic, then the POMDP is stochastic, and the notion of an underlying deterministic POMDP is ill-defined.

Related to the above, the action-corruption described in lines 415-418 is framed in terms of actions being corrupted, which hides the fact that this should be formalized as stochasticity in the the dynamics function.

Lack of discussion on strictness of anchor sequence assumptions:

The assumptions required for the existence of anchor sequences seems quite strict. It would benefit the submission to provide a few POMDP subclasses of interest that satisfy the assumptions, and perhaps some discussion about which POMDPs this would not apply to. For example, the presence of any latent state component that is not directly controlled by the agent (e.g., continuous-tiger, or continuous-heaven-hell) seems to be sufficient to break the assumption.

Questions for authors

Clarification requests:

  • Does the learning process maintain its validity even in the stochastic/corrupted setting, given that the probabilities being estimated are not true counterfactuals?

  • Can you explain and justify the corrupted POMDP setting more?

  • Could you provide some classes of POMDPs where the anchor sequence assumption applies?

  • The authors claim that the number of states is not a prerequisite, but is also learned; it's not fully clear how this is determined, without requiring tests with a possibly unbounded length LL for a generic POMDP.

Suggestions for future work:

  • Clarify the treatment of counterfactuals, and if necessary align with the correct definition of counterfactuals.
  • The statement "Under the assumption there exists a sequence of actions that direct any state to any other state in the POMDP, there exists anchor sequences" reads ambiguously and can be naively interpreted in multiple ways. I believe only one makes sense, ultimately, but it should be rewritten to be clear from the start, e.g., "for every state, there is a sequence of actions that leads to that state from any other state."
1 comment
AuthorsOpenReview ↗

Reponse to NDqu

Thank you for the helpful suggestions and feedback.

The authors define counterfactuals in a way that does not fully align with the literature of causal inference...

Clarify the treatment of counterfactuals, and if necessary align with the correct definition of counterfactuals.

However, proper counterfactuals must also maintain the same exogenous process in all trajectories. This is not guaranteed by simply conditioning on the same starting state. E.g., consider an environment where a coin…”

After careful examination, we agree that the definition of counterfactual used in this paper is different from the notion introduced by Pearl [1]. We specifically differ from Pearl’s definition of counterfactuals in how exogenous noise is coupled across alternate realizations of observed random variables -- in our use of counterfactuals, we do not couple the exogenous processes across alternate realizations. Please see the new appendix A for a comparison of our version of counterfactual and Pearl’s. In deterministic systems, our definition aligns with Pearl’s.

We believe that this version of counterfactual is appropriate for this problem context and for learning real systems like the toolbox, since we must reset a system to some configuration and evaluate some alternate sequence of actions and observations. In that alternate evaluation, the noise from a prior trajectory will not be the same after resetting the system.

Related to the above, the action-corruption described in lines 415-418 is framed in terms of actions being corrupted, which hides the fact that this should be formalized as stochasticity in the dynamics function…

The corrupted POMDP is defined with stochastic transitions/emissions, as stated in Definition 2, and we apologize if that is not clear. We hope to only recover the 'most likely' components of this POMDP, as stated right after the definition.

The statement "Under the assumption there exists a sequence of actions that direct any state to any other state in the POMDP, there exists anchor sequences" reads ambiguously and can be naively interpreted in multiple ways. I believe only one makes sense, ultimately, but it should be rewritten to be clear from the start, e.g., "for every state, there is a sequence of actions that leads to that state from any other state."

We update the text with your suggested phrasing.

The assumptions required for the existence of anchor sequences seems quite strict. It would benefit the submission to provide a few POMDP subclasses of interest that satisfy the assumptions, and perhaps some discussion about which POMDPs this would not apply to. For example, the presence of any latent state component that is not directly controlled by the agent (e.g., continuous-tiger, or continuous-heaven-hell) seems to be sufficient to break the assumption.

Our problem context only considers POMDPs with discrete action, discrete observation, and well-connected discrete state spaces. If the latent state of the POMDP is deterministic, and there is a sequence of actions to reach any state from any other (even if the POMDP had periodic structure, for example), then our algorithm can learn the POMDP.

Does the learning process maintain its validity even in the stochastic/corrupted setting, given that the probabilities being estimated are not true counterfactuals?

Thank you for the astute question. When we take Khatri-Rao products of an SDM, the subset of rows according to anchor sequences are corruptions of the counterfactual rows of the uncorrupted deterministic POMDP, which is not the same as counterfactual rows of the corrupted POMDP with the noise subsumed by stochastic transition/observations. The rows that are sufficiently close to the deterministic POMDP counterfactual can still be selected by successive projection, should the corruption be sufficiently small. We have clarified this point in Section 4.2.

[1] J. Pearl, Causality: models, reasoning, and inference. Cambridge, U.K. ; New York: Cambridge University Press, 2000.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to all reviewers

Thank you to all of our reviewers for the helpful feedback and questions. All reviewers have asked about the applicability of the “corrupted deterministic POMDP problem” introduced in Section 4, which we will answer in this shared note. More than one reviewer has asked for parameter selection. We have also included other improvements made to the paper as well.

On the practicality of learning a deterministic POMDP from an epsilon-corrupted POMDP. Dean et al. [1] has studied this problem in the context of topological map-learning of unknown building floors. Furthermore, we have included a real-world instance of the learning problem in Section 5.1. Here, we collected data from a real-world toolbox, which was the inspiration for the synthetic toolbox domain. The data is collected by humans who carried out the random actions on the toolbox as dictated by a program, and images of the toolboxes are discretized by a vision model. The sources of noise include the human performing a different action than the action sampled by the exploration policy, or misclassification of a vision-model. CfactSP can still learn the toolbox locking mechanism from this data. In general, this problem instance is representative of the problem scenario we have in mind: we want algorithms to learn partially-observable systems from real-world mechanisms like toolboxes, locking doors, appliances, maps, etc. Their structure is largely deterministic, and noise is often due to an action being incorrectly executed or noise inherent to how the observation is recorded in the data.

Runtime dependencies on parameters K, L, C and selection of K, L, C, and frequency threshold. Due to quick runtimes (new Appendix B, Table 1), the frequency filter parameter can be easily adjusted to yield a model. Furthermore, our numerical simulations suggest that the threshold must include the rarest homing anchor for learnability, so a binary-like search could be done to find the right threshold in practice.

In practice, if K and L are too small, then the rows of the SDM will appear to be non-deterministic and the algorithm output is “inconclusive” with increasing amounts of data. This is a situation where both K and L must be lengthened. Furthermore, our experience is that the number of counterfactuals to learn most deterministic POMDPs (such as toolbox, washroom, and espresso), is quite small. In general, to find the parameters (K, L, C) we would first raise the number of counterfactuals to some constant maximum (say, 4 or 5), and then lengthen K, L, raise counterfactuals, lengthen K, L, etc. Since algorithm runtimes are relatively quick, this can be done in an automated procedure until some condition like the bounds in Theorem 8 (tighter version of Theorem 3 sensitive to K, L, and C) hold, or the iterative procedure will continue to run due to insufficient data, too large noise, etc., and the runtime requirements will become too large for execution of CfactSP.

Other improvements:

Relaxing full-rank Forw matrix condition. We have refined Section 3 (and its corresponding appendix, now appendix D and E ) to relax the need for a full-rank Forward matrix. We have included a clearer directed graphical model in Fig 1 as well.

Stronger sample complexity performance in numerical simulations (and new real-world data demonstration). In the process of obtaining running/memory experiments, we found that the stopping threshold for sequential projection was made too stringent relative to the parameter suggested by the theory. We have rerun all experiments relative to the relaxed parameter, yielding stronger performance in our numerical simulations.

[1] T. Dean et al., “Inferring finite automata with stochastic output functions and an application to map learning,” Mach Learn, vol. 18, no. 1, pp. 81–108, Jan. 1995, doi: 10.1007/BF00993822.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.