acceptodds
Under review as a conference paper at ICLR 2027

Decision-Sufficient Representations for Partially Observed Control

10 views

Abstract

A latent state for control must decide what to forget. Reconstruction spends capacity on every background detail; passive prediction discards any cue it cannot forecast, even one that changes the best action. A latent state should instead retain the distinctions that alter controlled reward consequences, and only those. We make this precise with the decision Hankel matrix, whose rows are histories and whose columns are reward-rooted, observation-contingent policy trees. Its rank is the minimal dimension of any exact linear representation of these consequences; a basis of its columns yields a decision code from which every trusted tree value, the optimal action values, and the complete optimal-action set are exact functions; and equality of its rows is the coarsest quotient that preserves every trusted return. At finite capacity, a taskwise decision rate–distortion objective admits a finite-sample oracle inequality and a deployment-regret guarantee, and its zero-regret rate equals the log-size of a minimum reachable action-profile cover, attained by an encoder that ignores nuisance entirely. In exact computations on finite POMDPs, the decision rank stays at while a decision-null nuisance inflates the belief span -fold, rises by exactly one for an action-changing cue that observation prediction aliases, and, among million encoders, regret first vanishes at four codes, reached by a single nuisance-free encoder. Compress what is decision-null, not what is hard to predict.

Primary area:
learning theory
Keywords:
representation learning, partially observed control, decision sufficiency, state abstraction, reinforcement learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_s6ppOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies compressed history representations in finite POMDPs. Drawing on established linear compression methods, it formulates policy-tree values for a designated set of "trusted actions" as a Hankel matrix and provides a corresponding rank characterization. Under various additional assumptions, the paper also presents bounds for choosing an encoder from a finite class and characterizes the minimum codebook size needed for optimal decisions across tasks. Experiments on small synthetic models are provided.

Critical strengths

None

Critical weaknesses
  1. The writing and organization of the paper require substantial improvement. There is no clear statement of the central problem; instead, the text relies on informal examples and terminology. A lot of notation/terminology is also used without explicit definitions in the main body (e.g., "nuisance", "core", LτL_{\tau} in Theorem 4, etc.). The transitions between sections are difficult to follow, as the paper shifts from preserving the values of all considered policy trees to preserving optimal-action selection. These are distinct requirements, yet they are somehow presented as parts of a single characterization. The main contribution and the relationship between the results are therefore unclear.
  2. The paper should discuss how it differs from prior work. For example, linear compression construction is closely related to Poupart and Boutilier (2002), and it is unclear what is this paper's contribution here. The assumptions also need discussion, and, currently, most of them are relegated to the appendix.
Questions for authors
  1. Could you provide a precise, self-contained statement of the central problem, specifying what the representation must preserve, the admissible encoder and decoder classes, the information available to the learner, and the objective being optimized?
  2. What additional conclusions does your Theorem 1 provide beyond the invariant-subspace characterization of lossless linear compression in Poupart and Boutilier (2002)?
5 comments

We thank Reviewer s6pp for the direct, insightful feedback on organization, problem specification, assumption scope, and positioning relative to Poupart & Boutilier (2002). Our revision addresses each point directly.

Q1. Self-contained central problem & definitions

Section 2 (pp. 2–3) establishes all primitives ahead of main results:

  • Section 2.1 defines the POMDP tuple, Ga,oG_{a,o}, beliefs bhb_h, trusted actions Atr⊆A\mathcal{A}_{\mathrm{tr}}\subseteq\mathcal{A}, closed-loop policy trees Σfin\Sigma_{\mathrm{fin}} (Eq. (1)), infinite plans Π∞\Pi_\infty, background details, passive prediction, core X=x(H)X=x(H), and nuisance N=n0(H)N=n_0(H).
  • Section 2.2 specifies targets, classes, known vs. unknown quantities, and objectives across both stages:
    • Exact linear sufficiency (Sec. 3): Preserve all trusted returns DΠ(h,σ)=bh⊤ασD_\Pi(h,\sigma)=b_h^\top\alpha_\sigma over linear-decoder maps ϕ:Hcov→Rm\phi:\mathcal{H}_{\mathrm{cov}}\to\mathbb{R}^m, minimizing dimension mm (Thm. 1) and coarseness (Cor. 1). Primitives ra,Ga,o,bh\\{r_a,G_{a,o},b_h\\} compute zDz_D via Algorithm 1 (optional behavior identification is in App. B.1).
    • Finite-capacity optimal-action sufficiency (Sec. 4): Preserve optimal actions across task family T\mathcal{T} via shared discrete codebooks ϕ∈ΦM\phi\in\Phi_M (∣range⁡(ϕ)∣≤M|\operatorname{range}(\phi)|\le M) and heads gτ∈Gϕg_\tau\in\mathcal{G}_\phi, minimizing worst-task regret D(ϕ)D(\phi) vs. rate R(ϕ)=log⁡∣range⁡(ϕ)∣R(\phi)=\log|\operatorname{range}(\phi)| (Eq. (4)). With kernels, Qτ⋆Q_\tau^\star, μτ\mu_\tau, and (X,N)(X,N) unknown, empirical selection uses only nτn_\tau offline histories and certified targets Q^τ\widehat{Q}_\tau, giving oracle/deployment bounds (Thm. 2) and zero-regret rate (Thm. 3).
  • Assumps. 1–12 appear inline in Secs. 3–4 (pp. 4, 6, 7), and Appendices B–C (pp. 17–26) give full proofs in 10 pages, including finite Krylov depth for Prop. 1 (Prop. B.3).

Q2. Unifying tree values (Sec. 3) and optimal-action selection (Sec. 4)

Sections 1, 2.2, and 4 connect Secs. 3–4 as one relaxation along the decision-sufficiency spectrum:

  1. Theorem 1 and Corollary 1 characterize exact linear decoding of every trusted tree return DΠ(h,σ)D_\Pi(h,\sigma). While this drops unpredictable distractors (wtw_t), linearly decoding suboptimal observation-branching trees forces DΠD_\Pi to track predictable cycles (Table 1, p. 8: d=32d=32).
  2. In finite-capacity offline control, encoders output discrete bounded codebooks rather than exact linear subspaces. Relaxing the target from all tree returns (Sec. 3) to worst-task optimal-action regret (Sec. 4) yields the control-level quotient theorem (Theorem 3, zero-regret rate log⁡mdecreach\log m_{\mathrm{dec}}^{\mathrm{reach}}, dropping the cyclic distractor from 3232 to 33) plus finite-sample oracle and deployment bounds (Theorem 2).

Q3. Exact mathematical advances of Theorem 1 beyond Poupart & Boutilier (2002) [VDC]

Remark 1 (p. 5) and Table 2 (p. 10) isolate our advances over VDC:

  1. Covered-history kernel projection (d≤dim⁡WΠd\le\dim\mathcal{W}_\Pi): VDC builds the reward-rooted Krylov space WΠ⊆R∣S∣\mathcal{W}_\Pi\subseteq\mathbb{R}^{|\mathcal{S}|} (Atr=A\mathcal{A}_{\mathrm{tr}}=\mathcal{A}) on the full simplex and projects beliefs onto WΠ\mathcal{W}_\Pi. With covered-history evaluation T:WΠ→RHcovT:\mathcal{W}_\Pi\to\mathbb{R}^{\mathcal{H}_{\mathrm{cov}}}, (Tα)(h)=bh⊤α(T\alpha)(h)=b_h^\top\alpha, Thm. 1(i)–(ii) handles belief-span degeneracies (ker⁡T≠0\ker T\neq\\{0\\}), lowering rank from dim⁡WΠ\dim\mathcal{W}_\Pi to d=dim⁡T(WΠ)d=\dim T(\mathcal{W}_\Pi) whenever covered beliefs span a proper subspace (Eq. (2)).
  2. Observable tree coordinates without test-time beliefs: Instead of belief projections FbhF b_h, pivoted QR selects dd deterministic trees (σ1,…,σd)(\sigma_1,\ldots,\sigma_d) giving observable codes zD(h)=(DΠ(h,σ1),…,DΠ(h,σd))∈Rdz_D(h)=(D_\Pi(h,\sigma_1),\ldots,D_\Pi(h,\sigma_d))\in\mathbb{R}^d.
  3. Matching lower bound over all exact-linear history maps: While VDC gives an upper bound (dim⁡WΠ\dim\mathcal{W}_\Pi), Thm. 1(iv) proves the matching converse m≥dm\ge d (and zD=Bϕz_D=B\phi) across all exact-linear history maps (Assump. 4).
  4. Full tie sets & gap-free envelopes (Thm. 1(iii)): Qa⋆Q_a^\star, V⋆V^\star, and the full tie set A⋆(h)\mathcal{A}^\star(h) factor through zDz_D over arbitrary common-tape randomized plans without attainment or gap assumptions.
  5. Coarsest safe quotient & Borel boundary (Cor. 1): Row equality h≡Dh′h\equiv_D h' is the coarsest return-safe partition, yields finite cue-separating witnesses, and establishes Borel nonrecovery outside σ(Ht)\sigma(H_t) (post-action shocks ξt\xi_t).
  6. Section 4 (Thms. 2–3) moves beyond linear tree-value subspaces to finite-capacity multi-task optimal-action compression, eliminating predictable distractors that inflate VDC and DΠD_\Pi.

We hope these clarifications address your concerns and look forward to further discussion.

The revised manuscript is significantly different from the original submission. I maintain my original score.

Thank you for following up. The central research question remains the same, and the revisions address your requests for clearer definitions, a better explanation of the relationship between the results, and a comparison with prior work. Could you please identify which specific changes you consider significantly different from the original submission, and which of your original concerns remain unresolved after our response? This would help us understand the basis for your assessment.

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

This work studies partially observable Markov decision processes (POMDPs). From what I understood, the authors seek to investigate what information needs to be retained to preserve meaningful reward consequences of actions. To this end, the authors introduce a decision Hankel matrix, whose rows are histories, whose columns are actions, and whose entries are the expected returns of executing those actions given the corresponding histories. This work further shows that the rank of the decision Hankel matrix determines the minimum dimension of a representation needed to recover the optimal action values and the complete optimal-action set.

Critical strengths
  1. Presentation: This work presents several concrete numerical toy examples to illustrate some of its concepts.
Critical weaknesses
  1. Presentation: I have to say that some parts of this work are a bit difficult to follow.

    1. Is the problem studied here a learning problem or just an offline optimization problem? I would recommend that the authors explicitly define and discuss which quantities are known and which are unknown. For example, is Ga,oG_{a,o} known or unknown?
    2. The connections between some parts of this work are not very clear. For instance, in the abstract, the authors first state, “We make this precise with the decision Hankel matrix ... that preserves every trusted return.” Subsequently, they state, “At finite capacity, a taskwise decision rate–distortion objective...” What is the connection between the “decision Hankel matrix” and the “taskwise decision rate–distortion objective”? This is a bit confusing for the reader.
    3. I think the discussion of the key results and the conditions required for those results may be insufficient. For instance, in Sec. 3.2, the authors simply state Theorem 1 without providing any discussion afterward. Moreover, Theorem 1 requires 6 assumptions (Assumptions 6–11). These assumptions are neither discussed nor explained, and they are not even stated in the main text. In particular, I personally found Assumption 10 very hard to understand, and it seems to be a strong assumption that may require an oracle. I regard the submission as a theoretical paper, for which I do not think it is appropriate to introduce critical assumptions without discussing them and to defer even their statements to the appendix.
    4. Some terms are introduced without being formally defined or sufficiently discussed, making it a bit difficult for me to understand their meaning:
      • “equality of its rows is the coarsest quotient”: What does it mean by 'equality of its rows' and what's the meaning of 'coarsest quotient'?
      • “taskwise decision rate–distortion objective”: What does “decision rate–distortion” mean?
      • “Reconstruction spends capacity on every background detail”: What is meant by “background detail”?
      • “passive prediction discards any cue it cannot forecast, even one that changes the best action”: What is meant by “passive prediction”?
      • “policy tree”: The authors define a policy tree as σ=(a,(σo)o∈O)\sigma=\left(a,\left(\sigma_o\right)_{o\in\mathcal O}\right). To me, this looks very similar to a trajectory, a more natural and common term in the reinforcement learning literature.
      • “At finite capacity”: What does “At finite capacity” mean, and what is assumed to have finite capacity?
      • “deployment-regret guarantee”: What does “deployment regret” mean?
      • “zero-regret rate”: What does this mean? Do the authors mean the constant regret?
      • “action-profile cover”: What does “action-profile cover” mean?
      • “A nonempty set of trusted actions generates the trusted policy trees”: “Trusted actions” are not formally defined, and it is unclear to me what the term means.
      • “ignores nuisance entirely”: What does “nuisance” mean here?
  2. Technical innovations: It is unclear to me what the main technical innovations are, as I do not find sufficient discussion of this in the paper. Some existing works appear to have already developed very similar techniques or frameworks. For example, POMDP compression using a subspace that contains the reward vectors and is invariant under action–observation operators, together with a Krylov procedure, has already been proposed in [1]. A characterization of the minimum dimension in terms of the rank of a history–action matrix has also been established, for example, in [2]. The relationship between observation-only prediction and reward modeling, as well as the inclusion of rewards in predictive representations, has also been investigated in [3]. Overall, the technical innovations seem somewhat limited to me, and I would recommend that the authors provide a more detailed discussion and explanation of whether this work develops any new techniques.

[1] Poupart et al. Value-directed Compression of POMDPs. NeurIPS, 22.

[2] Singh et al. Predictive State Representations: A New Theory for Modeling Dynamical Systems. UAI, 04.

[3] Baisero et al. Reconciling Rewards with Predictive State Representations. IJCAI, 21.

Questions for authors

Please see the weakness part above.

4 comments

We thank Reviewer MgxP for the audit of our terminology, assumptions, and positioning against prior work. Every question is addressed directly in the revision.

Q1. Problem formulation vs. offline learning; known vs. unknown

Section 2.2 (p. 3) specifies known vs. unknown quantities across one spectrum:

  • Sec. 3 (Decision-Hankel sufficiency): Given ra,Ga,o,bh\\{r_a,G_{a,o},b_h\\}, Alg. 1 computes d,zDd,z_D via Krylov closure and QR; when kernels are unknown and behavior data under μ\mu are observed, App. B.1 identifies DΠD_\Pi via gg-functionals or stopped IS.
  • Sec. 4 (Decision rate–distortion): An offline learning problem over (ΦM,Gϕ)(\Phi_M,\mathcal{G}_\phi). Kernels, Qτ⋆Q_\tau^\star, μτ\mu_\tau, and (X,N)(X,N) are unknown; using nτn_\tau offline histories ∼μτ\sim\mu_\tau and certified targets Q^τ\widehat{Q}_\tau, Thm. 2 bounds oracle (Eq. (6)) and deployment regret (Eq. (7)).

Q2. Bridge between DΠD_\Pi (Sec. 3) and D(ϕ)D(\phi) (Sec. 4)

Sections 1, 2.2, and 4 (p. 5) connect both stages: Sec. 3 linearly decodes all policy-tree returns, yielding ≡D\equiv_D and rank dd. This drops unpredictable nuisance (wtw_t), yet predictable cyclic distractors inflate dd via suboptimal trees (Table 1, p. 8: d=32d=32 vs. mdecreach=3m_{\mathrm{dec}}^{\mathrm{reach}}=3). Sec. 4 relaxes the criterion to worst-task optimal-action regret D(ϕ)D(\phi) under discrete rate R(ϕ)=log⁡∣range⁡(ϕ)∣R(\phi)=\log|\operatorname{range}(\phi)| and finite data, yielding Thm. 3 (log⁡mdecreach\log m_{\mathrm{dec}}^{\mathrm{reach}}).

Q3. Exact assumption scope of Theorems 1–3

Thank you for highlighting this—it sharpened our dependency layout. Behavioral positivity and conditional-moment assumptions apply only to optional off-policy identification (App. B.1: Assumps. B.1–B.2, Prop. B.1), whereas Thm. 1 and Cor. 1 hold intrinsically under Assumps. 1–4 inline in Sec. 3.1 (p. 4) (finite POMDP, bounded rewards, complete continuations, exact-linear class; no oracle/data assumption). Assumps. 5–9 (Thm. 2) and Assumps. 10–12 (Thm. 3) appear inline in Secs. 4.1–4.2 (pp. 6–7).

Q4. Definitions of all 11 terms (Secs. 2–4, pp. 2–7)

  1. Policy tree vs. trajectory (Sec. 2.1): Trajectory: realized sequence (o1,a1,…,ok,ak)(o_1,a_1,\ldots,o_k,a_k); policy tree σ∈Σfin\sigma\in\Sigma_{\mathrm{fin}}: closed-loop plan ⊥\bot or (a,(σo)o∈O)(a,(\sigma_o)_{o\in\mathcal{O}}) (a∈Atra\in\mathcal{A}_{\mathrm{tr}}).
  2. Trusted actions Atr\mathcal{A}_{\mathrm{tr}} (Sec. 2.1): Subset Atr⊆A\mathcal{A}_{\mathrm{tr}}\subseteq\mathcal{A} whose returns are preserved (Atr=A\mathcal{A}_{\mathrm{tr}}=\mathcal{A} gives full control).
  3. Background detail (Sec. 2.1): Observable (wtw_t, Fig. 1) adding entropy without changing rewards or core dynamics.
  4. Passive prediction (Sec. 2.1): Observation forecasting without reward rooting (Obs-PSRs).
  5. Coarsest quotient (Cor. 1): h≡Dh′h\equiv_D h' iff DΠ(h,σ)=DΠ(h′,σ)D_\Pi(h,\sigma)=D_\Pi(h',\sigma) ∀σ\forall\sigma; any return-safe partition η\eta refines ≡D\equiv_D.
  6. Decision rate–distortion (Eq. (4)): Tradeoff between R(ϕ):=log⁡∣Zϕ∣R(\phi):=\log|\mathcal{Z}_\phi| and D(ϕ):=max⁡τmin⁡gEμτ[Vτ⋆(H)−Qτ⋆(H,g(ϕ(H)))]D(\phi):=\max_\tau\min_g\mathbb{E}_{\mu_\tau}[V_\tau^\star(H)-Q_\tau^\star(H,g(\phi(H)))].
  7. At finite capacity (Sec. 4.1): Discrete codebooks ϕ∈ΦM\phi\in\Phi_M with ∣range⁡(ϕ)∣≤M|\operatorname{range}(\phi)|\le M.
  8. Deployment regret (Eq. (7)): Closed-loop suboptimality Vτ⋆−Vτπ^τV_\tau^\star - V_\tau^{\widehat{\pi}_\tau} of π^τ=g^τ∘ϕ^\widehat{\pi}_\tau=\widehat{g}_\tau\circ\widehat{\phi}.
  9. Action-profile cover (Def. 2): Finite C⊆AT\mathcal{C}\subseteq\mathcal{A}^{\mathcal{T}} covering uτ∈arg⁡max⁡aqτ⋆(x,a)u_\tau\in\arg\max_a q_\tau^\star(x,a) across active tasks for μˉX\bar{\mu}_X-a.e. xx; min size mdecreachm_{\mathrm{dec}}^{\mathrm{reach}}.
  10. Zero-regret rate (Thm. 3): Minimal rate min⁡ϕ∈ΦM: D(ϕ)=0R(ϕ)=log⁡mdecreach\min_{\phi\in\Phi_M:\,D(\phi)=0}R(\phi)=\log m_{\mathrm{dec}}^{\mathrm{reach}} where D(ϕ)=0D(\phi)=0.
  11. Nuisance (Sec. 2.1, Assump. 10): Return-annihilator distinctions (Sec. 3), or observable N=n0(H)N=n_0(H) complementary to core X=x(H)X=x(H) (Sec. 4).

Q5. Advances beyond [1] Poupart & Boutilier (2002), [2] Singh et al. (2004), and [3] Baisero & Amato (2021)

Isolated in Remark 1 (p. 5), Table 2 (p. 10), and Sec. 6:

  • Beyond [1] VDC: (1) covered-history projection cuts rank from dim⁡WΠ\dim\mathcal{W}_\Pi to d=dim⁡T(WΠ)d=\dim T(\mathcal{W}_\Pi) when ker⁡T≠0\ker T\neq\\{0\\}; (2) QR gives dd observable tree values zD(h)z_D(h) without beliefs at test time; (3) Thm. 1(iv) proves m≥dm\ge d over exact-linear maps; (4) Thm. 1(iii) gives full tie sets A⋆\mathcal{A}^\star gap-free while Cor. 1 gives ≡D\equiv_D and shock nonrecovery.
  • Beyond [2] Obs-PSR & [3] R-PSR: Open-loop obs tests make [2] alias cues (Table 1: 44 vs. d=5d=5) and force [2]–[3] to grow with cyclic distractors (3232 vs. 44 core-br. / 33 for mdecreachm_{\mathrm{dec}}^{\mathrm{reach}}). Dropping obs-only tests (Sec. 3) and using action covers (Sec. 4) resolves all three pathologies.

I thank the authors for the response, though I believe most of the content of the response may have been generated by AI.

However, most of my concerns remain unresolved. For example, in the third weakness point under Presentation in my original review, I said “I think the discussion of the key results and the conditions required for those results may be insufficient. For instance, in Sec. 3.2, the authors simply state Theorem 1 without providing any discussion afterward.” and “Moreover, Theorem 1 requires 6 assumptions (Assumptions 6–11). These assumptions are neither discussed nor explained, and they are not even stated in the main text. In particular, I personally found Assumption 10 very hard to understand, and it seems to be a strong assumption that may require an oracle. I regard the submission as a theoretical paper, for which I do not think it is appropriate to introduce critical assumptions without discussing them and to defer even their statements to the appendix.”

The response from the authors still does not seem to present the corresponding discussions and explanations of the key results. Further, the response from the authors only explained which theorems use which assumptions. However, my concern is that some of these assumptions, as well as why they are needed, are not well explained, rather than where they are needed. More importantly, some assumptions seem to be rather stringent and difficult to satisfy in practice. Thus, the authors’ response is actually unrelated to my previous concern. In light of this, I still do not think the current paper meets the bar for acceptance at ICLR.

Also, even if the technical innovations and the significance of this work meet the bar for acceptance at ICLR, given that many parts of this work may need substantive revisions, I personally feel that this paper may need another round of peer review. Therefore, I will maintain my current score for this work and may not respond to further responses from the authors.

AuthorsOpenReview ↗

Response to Reviewer MgxP (1/2)

Thank you for your candid feedback. We apologize that our previous reply read like a compact index pointing to sections of the paper rather than directly discussing the meaning, necessity, and practical realism of the assumptions and results in plain text. Below we provide that discussion directly.

1. Regarding the former "Assumption 10" (oracle assumption) in Theorem 1 Your original review rightly flagged that Assumption 10 in the initial submission (which assumed access to exact conditional expectations of off-policy trajectory estimators) looked like an oracle assumption and was not discussed. That assumption was only ever meant for an optional appendix remark on how one could estimate the Hankel matrix from off-policy behavior logs if the POMDP model were unknown. Theorem 1 itself is a structural theorem about the POMDP model (just like PSR rank in Singh et al., 2004 or Value-Directed Compression in Poupart & Boutilier, 2002). It does not use any oracle or behavior-policy assumption. It requires only a finite discounted POMDP (γ∈(0,1)\gamma \in (0,1)) so that policy-tree value vectors lie in R∣S∣\mathbb{R}^{|\mathcal{S}|} and infinite-horizon returns converge geometrically.

2. Why the assumptions in Theorems 2 and 3 are needed, what breaks without them, and how realistic they are

  • Why Theorem 2 needs target accuracy ητ\eta_\tau (Assumption 8) and concentrability CτC_\tau (Assumption 9): In offline representation selection (Section 4), the learner does not know the true optimal value function Qτ⋆(h,a)Q_\tau^\star(h,a) and only has offline trajectories logged under a behavior distribution μτ\mu_\tau plus an approximate critic Q^τ\widehat{Q}_\tau with sup-norm error ητ\eta_\tau.
    • Why ητ\eta_\tau is needed: If the critic Q^τ\widehat{Q}_\tau has arbitrary unconstrained error on some actions, empirical regret minimization will pick an encoder that overfits to the critic's mistakes; ητ\eta_\tau quantifies how critic error propagates additively (2ητ2\eta_\tau in Eq. (6)) into representation selection.
    • Why CτC_\tau is needed: When we deploy the learned policy π^τ\widehat{\pi}_\tau in closed loop, its state-history visitation distribution shifts away from the offline distribution μτ\mu_\tau. Without a coverage bound CτC_\tau between deployment visitation and μτ\mu_\tau, an encoder can have zero error on the offline dataset while choosing bad actions on histories only visited during closed-loop rollout. Bounded concentrability CτC_\tau and critic error ητ\eta_\tau are standard in offline RL theory (e.g., Munos & Szepesvari, 2008; Chen & Jiang, 2019); our bound makes their exact cost explicit rather than assuming a perfect critic or zero distribution shift.
  • Why Theorem 3 needs recursive core sufficiency (Assumption 10) and shared nuisance support (Assumption 11): Theorem 3 asks when a finite-capacity codebook can drop predictable distractors and achieve zero action regret across a family of tasks using log⁡mdecreach\log m_{\mathrm{dec}}^{\mathrm{reach}} bits.
    • Why Assumption 10 is needed: It states that histories split into a task-relevant core XX (e.g., physical state of a robot and objects) and a nuisance process NN (e.g., moving background video or lighting), where NN can have arbitrary predictable dynamics of its own, but rewards and next-core transitions depend only on (X,A)(X,A). If NN causally changed future rewards or core states, NN would not be a distractor and no zero-regret encoder could ignore it.
    • Why Assumption 11 (shared nuisance support) is needed: Suppose Task 1 only ever occurred under daytime lighting (N=0N=0) and Task 2 only under nighttime lighting (N=1N=1). Then an encoder could "cheat" by reading the lighting NN to infer which task is being evaluated, packing multiple core states into a single code and beating the core cover number mdecreachm_{\mathrm{dec}}^{\mathrm{reach}}. Assumption 11 requires only that at a given core state xx, the set of possible nuisance values nn is the same across tasks (their probabilities can differ arbitrarily). This holds naturally whenever tasks are defined in the same physical environment or simulator.
AuthorsOpenReview ↗

Response to Reviewer MgxP (2/2)

3. Meaning of the main results and scope of the revision Together, Theorem 1 and Theorem 3 explain a fundamental phenomenon in control representations: if you require a representation to linearly predict all policy-tree returns (Theorem 1), it eliminates unpredictable noise (wtw_t) and post-action shocks (ξt\xi_t), but it still has to track predictable irrelevant background processes because suboptimal policies can branch on them. Once you relax the requirement to preserving only optimal actions across tasks at finite codebook capacity (Theorem 3), predictable background processes are eliminated as well. Finally, we emphasize that the revised PDF did not change any theorems, proofs, or experiments from the original submission—it simply moved these assumption statements and discussions from the appendix into the main body and removed duplicated setup text in the appendix.

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

This paper talks about representation of histories in POMDPs. The main idea is to have a representation that at the same time maintains important decision relevant observations and removes unimportant irrelevant ones and ignores yet other ``nuisance'' observations that are anyway not available at decision time.

The authors show with a simple example why earlier approaches fail in at least one of the three aspects. Then the authors propose a new representation that they call the decision Hankel matrix, whose rows are histories and whose columns are reward-rooted, observation-contingent policy trees. They then show several results about this Hankel matrix representation. First its rank is the minimal dimension of any exact linear representation of these consequences. Then a basis of its columns yields a decision code from which every trusted tree value as well as its optimal action values and action set can be recovered as exact functions. Finally, they show that equality of its rows is the coarsest quotient that preserves every trusted return. As a second main theroetical result for finite POMDPs they give a finite-sample bound for selecting an encoder from a finite class, followed by a deployment-regret guarantee under some coverage assumptions. Finally, they show how the minimum representation to get zero decision regret can be obtained as a function of the minimum reachable action-profile cover, and show it can be achieved under assumptions that ignores nuisance information. They show some basic experiments to validate their results.

Critical strengths

On the positive side, the paper addresses an interesting problem. The simple problem is well motivated and I believe natural. The theorem statements appear to be potentially interesting and impressive, as best as I could understand them, and the proof techniques are non-trivial.

Critical weaknesses

On the negative side, the paper is impossible to check within the review period given it has a 50+page appendix. Second, the technical parts of the abstract, introduction and preliminaries are not accessible to the non-expert. For instance some sentences of the abstract are full of undefined technical terms that are repeated in introduction as well, and in neither place are they understandable. While I believe the motivation made sense, I was unable to move from that to the technical details as it was very dense and lacking definitions/intuition. In other words it seems difficult to assess the significance of the main results without having to read the long appendix. Finally, the experiments (with very few synthetic benchmarks) felt a bit perfunctory and threadbare.

Questions for authors
  1. Can you give the main intuition and a simple proof sketch for the main three theorems? I would like to know which are the non-trivial parts and why.
  2. Can you make the preliminaries self-contained?
  3. What is the purpose of the experiments? Are they just to validate the theory or do they establish something beyond what comes out from the theory?
  4. how strong or realistic/practical are the various assumptions using in the three main theorems? As many of them are in the appendix it is difficult to understand the limitations of the work without having to read the full appendix.
3 comments

We thank Reviewer kLU8 for recognizing the motivation, theoretical depth, and proof techniques of our work, and for the constructive suggestions on inspectability.

Q1. Main intuition, proof sketch, and non-trivial ingredients (Theorems 1–3)

Concise proof summaries follow Theorems 1–3 inline (Sections 3–4), backed by a 10-page self-contained proof appendix (Appendices B–C, pp. 17–26):

  • Theorem 1 (pp. 4–5, App. B): Four mechanisms drive the theorem:
    1. One-child graft invariance (Lem. B.2): Subtracting the 1-step tree τa0=(a,(⊥)o)\tau_a^0=(a,(\bot)_o) (ατa0=ra\alpha_{\tau_a^0}=r_a) from τa,o,σ\tau_{a,o,\sigma} (grafting σ\sigma onto branch oo) gives ατa,o,σ−ατa0=γGa,oασ∈WΠ\alpha_{\tau_{a,o,\sigma}}-\alpha_{\tau_a^0}=\gamma G_{a,o}\alpha_\sigma \in \mathcal{W}_\Pi; γ>0\gamma>0 closes WΠ\mathcal{W}_\Pi under every Ga,oG_{a,o}, even on zero-probability observations.
    2. Nontrivial belief kernel (Prop. B.4): Covered beliefs bhb_h may span a proper subspace of R∣S∣\mathbb{R}^{|\mathcal{S}|}, so (Tα)(h):=bh⊤α(T\alpha)(h):=b_h^\top\alpha can have ker⁡T≠0\ker T \neq \\{0\\} and d=dim⁡T(WΠ)<dim⁡WΠd=\dim T(\mathcal{W}_\Pi)<\dim\mathcal{W}_\Pi. Unique weights cσc_\sigma live in T(WΠ)T(\mathcal{W}_\Pi) and are realized constructively by dd observable tree columns.
    3. Infinite plans via a common tape (Lem. B.5, Prop. B.6): Freezing Ξπ\Xi_\pi turns any depth-LL randomized continuation π(L)\pi^{(L)} into one root-independent convex combination in Σfin\Sigma_{\mathrm{fin}} (απ(L)∈WΠ\alpha_{\pi^{(L)}}\in\mathcal{W}_\Pi); uniform convergence (Rmax⁡γL/(1−γ)R_{\max}\gamma^L/(1-\gamma)) places απ∈WΠ\alpha_\pi\in\mathcal{W}_\Pi.
    4. Gap-free tie sets (Prop. B.7): History-independence of Π∞(a)\Pi_\infty(a) transfers Qa⋆Q_a^\star, V⋆V^\star, and the full tie set A⋆\mathcal{A}^\star onto Z=zD(Hcov)\mathcal{Z}=z_D(\mathcal{H}_{\mathrm{cov}}) via sup⁡π∈Π∞(a)⟨zD(h),cπ⟩\sup_{\pi\in\Pi_\infty(a)}\langle z_D(h),c_\pi\rangle without attainment or gap assumptions.
  • Theorem 2 (p. 6, App. C.1): Beyond Hoeffding/union bounds over NclsN_{\mathrm{cls}} triples: (i) conditioning on EQ\mathcal{E}_Q keeps error 2ητ2\eta_\tau additive rather than multiplying ϵτ\epsilon_\tau (even if P(EQ)=0\mathbb{P}(\mathcal{E}_Q)=0); (ii) sup-norm stability transfers bounds to (ϕ^,g^τ)(\widehat{\phi},\widehat{g}_\tau) without unique optimizers; and (iii) a Bellman telescope plus Radon–Nikodym lift isolates Cτ/(1−γ)C_\tau/(1-\gamma) solely in Eq. (7), leaving Eq. (6) shift-free.
  • Theorem 3 (p. 7, App. C.2): Core contraction (Prop. C.4) gives Qτ⋆(h,a)=qτ⋆(x(h),a)Q_\tau^\star(h,a)=q_\tau^\star(x(h),a) (achievability). The non-trivial converse rules out ϕ(x,n)\phi(x,n) splitting xx along nn or using nuisance correlations to beat mdecreachm_{\mathrm{dec}}^{\mathrm{reach}}. Disintegrating Lτ(ϕ,gτ)=0L_\tau(\phi,g_\tau)=0 yields rτ(x)ντ,xn:ϕ(x,n)=zΔτ,z(x)=0r_\tau(x)\nu_{\tau,x}\\{n:\phi(x,n)=z\\}\Delta_{\tau,z}(x)=0; shared support (Assump. 11: ντ,x∼νσ,x\nu_{\tau,x}\sim\nu_{\sigma,x}) forces active codes zz at xx to be active across T(x)\mathcal{T}(x) (uz∈Ureach(x)u_z\in\mathcal{U}_{\mathrm{reach}}(x)), giving a global cover of size ≥mdecreach\ge m_{\mathrm{dec}}^{\mathrm{reach}} (Lem. C.6, Prop. C.7).

Q2. Self-contained preliminaries & checkable proofs

Section 2 (pp. 2–3) defines all primitives before Sec. 3, and Appendices B–C (pp. 17–26) prove Theorems 1–3, Corollary 1, and finite Krylov depth in Proposition 1 (Prop. B.3).

Q3. Purpose of experiments & findings beyond theorems

Section 5 runs exact machine-precision computations on finite POMDPs (plus exhaustive search over all 4,213,660 discrete encoders in Sec. 5.2) to measure exact population quantities—belief spans, PSR ranks, bisimulation, dd, mdecreachm_{\mathrm{dec}}^{\mathrm{reach}}, and family regret—uncovering three phenomena:

  1. Predictable nuisance separation (Table 1, p. 8): On cyclic nuisance (k=8k=8), Obs/Rew-PSRs and branch-complete dd reach 3232, while core-branching keeps d=4d=4 and action-regret compression (Thm. 3) drops to mdecreach=3m_{\mathrm{dec}}^{\mathrm{reach}}=3.
  2. Below-knee coin balancing (Sec. 5.2, p. 9): At M=2M=2 (<mdecreach=4<m_{\mathrm{dec}}^{\mathrm{reach}}=4), optimal compression retains a decision-null coin to balance worst-case task regret (0.1700.170 vs. 0.1840.184 best core-only).
  3. Sharpness vs. envelopes (Fig. 3c, Fig. 4): Rank stabilizes at depth 22 (<L⋆=dim⁡WΠ<L^\star=\dim\mathcal{W}_\Pi), error scales as n−0.49n^{-0.49}, and deployment regret tracks cleanly for Cτ∈[1.5,136]C_\tau\in[1.5,136].

Q4. Scope and realism of Assumptions 1–12

All 12 assumptions appear inline (pp. 4, 6, 7): Assumps. 1–4 (Thm. 1) are finite-POMDP primitives with no positivity/oracle requirement (off-policy estimation is in App. B.1, Assumps. B.1–B.2); Assumps. 5–9 (Thm. 2) pair finite-class bounds (Sec. 6 notes covering/Rademacher extensions) with ητ,Cτ\eta_\tau,C_\tau isolating error and shift; Assumps. 10–12 (Thm. 3) permit arbitrary predictable nuisance under shared support ντ,x∼νσ,x\nu_{\tau,x}\sim\nu_{\sigma,x} (no density-ratio bound).

Thank you for the response and the revision. The paper has shrunk significantly due to a shorter proof appendix. The assumptions now stated next to each theorem, and the proof sketches make the paper much easier to inspect. But I wonder if the sheer amount of change here results in a new paper and hence requires a new review. I myself can say that I went through it briefly but wasn't able to redo the review. That would be impossible in the given time.

A few comments:

  1. The abstract is now longer but still dense with undefined terms. The plain-language paragraphs of the original intro seem to have been removed rather than improved. This does not really strengthen the case for accessibility.

  2. For Theorem 3, 2 the non-trivial parts seem clear. However, for Theorem 1, I share the concern of the other reviewers. Is the novelty mainly the choice of columns ? Which step is technically new?

  3. Regarding experiments, thank you for highlighting the three phenomena. However, I still feel the experiments are a bit weak: Section 5 uses the same two small families of synthetic POMDPs, and the cyclic-nuisance and M = 2 coin-balancing results were already in the original appendix, I think.

  4. Finally, for the assumptions, moving them inline helps, but there is no discussion of when Assumptions hold beyond the toy examples.

Despite these remaining concerns, I retain my weak accept score: the theory is interesting and now much easier to check, though checking it carefully would quite some time.

Thank you for taking the time to look through the revision and for maintaining your positive assessment. We would like to briefly clarify the scope of the changes and directly answer your four follow-up questions.

1. Why the page count dropped (no change to the underlying theorems or proofs) The mathematical results, proof steps, and experiments in the revised PDF are the same as in the original submission. In the original 70-page file, our appendix repeated the full setup and lemma headers across multiple sub-appendices, and all assumption statements were stored in the appendix. The reduction from 70 to 26 pages comes simply from moving the existing assumption statements next to the theorems in the main text (as all three reviewers requested) and removing those repeated setup blocks in the appendix, while consolidating Theorems 1–6 into Theorems 1–3, Corollary 1, and Proposition 1. Regarding the abstract and introduction, your point is well taken—we will restore the plain-language opening intuition in the introduction and simplify the abstract wording so the high-level message is immediately accessible before any technical terms appear.

2. In Theorem 1, what is technically new beyond Poupart & Boutilier (2002) [VDC]? It is more than choosing columns σ1,…,σd\sigma_1,\ldots,\sigma_d via QR. In VDC, one assumes known POMDP matrices (ra,Ga,o)(r_a, G_{a,o}) and compresses belief vectors bhb_h over the full simplex by closing span⁡ra\operatorname{span}\\{r_a\\} under Ga,oG_{a,o} to obtain WΠ\mathcal{W}_\Pi (an upper bound of dim⁡WΠ\dim \mathcal{W}_\Pi). Three steps in Theorem 1 and Corollary 1 are technically new:

  • Closing the subspace purely from closed-loop tree evaluations (Lemma B.2): When we only evaluate histories on closed-loop policy trees (which branch on all observations at once), it is not immediate that the tree-value span matches the Ga,oG_{a,o}-invariant subspace. Our one-child graft argument subtracts a 1-step baseline tree from a tree grafted on a single branch (a,o)(a,o), isolating γGa,oασ\gamma G_{a,o}\alpha_\sigma purely from tree values.
  • Quotienting out unreachable belief directions and proving the matching m≥dm \ge d lower bound (Proposition B.4, Proposition B.8): Covered histories Hcov\mathcal{H}_{\mathrm{cov}} often span a proper subspace of the belief simplex. Directions in WΠ\mathcal{W}_\Pi orthogonal to covered beliefs lie in the kernel of the evaluation operator (Tα)(h)=bh⊤α(T\alpha)(h) = b_h^\top\alpha, strictly reducing the dimension from VDC's dim⁡WΠ\dim \mathcal{W}_\Pi to d=dim⁡T(WΠ)d = \dim T(\mathcal{W}_\Pi). We then prove a matching lower bound m≥dm \ge d across all exact-linear history encoders ϕ(h)\phi(h), whereas VDC only establishes sufficiency (an upper bound) for linear belief projections.
  • Lifting finite deterministic trees to infinite randomized plans and tie sets (Propositions B.6–B.7, B.9): Using a shared exogenous random tape, we show that dd finite deterministic tree values already determine all infinite-horizon randomized continuations and the entire optimal-action tie set A⋆(h)\mathcal{A}^\star(h) without action-gap assumptions, and establish the exact Borel nonrecovery boundary for unrevealed post-action shocks.

3. Role of the experiments You are right that the cyclic-nuisance and M=2M=2 coin-balancing instances were previously buried in the appendix; we moved them into Section 5 precisely because they directly answer your question from Round 1 on what the experiments show beyond validating the theorem inequalities (namely, why predictable distractors separate tree-value rank d=32d=32 from action-regret rate mdecreach=3m_{\mathrm{dec}}^{\mathrm{reach}}=3, and why nuisance elimination only holds at the zero-regret knee M=4M=4 rather than below the knee at M=2M=2).

4. When do the assumptions hold beyond toy examples? Consider visual robotic control or autonomous driving across multiple reward tasks (e.g., reaching different targets or driving styles) in an environment with changing background clutter, lighting, or weather:

  • Assumptions 1–4 (Theorem 1) hold for any finite-state, finite-observation discounted POMDP.
  • Assumptions 5–9 (Theorem 2) correspond to standard offline RL pipelines where candidate discrete encoders (e.g., VQ-VAE/tokenized world-model latents) are scored on logged trajectories using a pre-trained offline critic Q^τ\widehat{Q}_\tau (with approximation error ητ\eta_\tau) under a behavior policy that covers the states visited at deployment (concentrability CτC_\tau).
  • Assumptions 10–11 (Theorem 3) hold whenever observations factor into physical task state XX (robot/object pose) and background NN (lighting, camera texture, background pedestrians) where background does not causally alter physical dynamics or rewards (Assumption 10), and where any background condition that can occur in one task can also occur in another task at the same physical state (Assumption 11, shared support).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.