- Rating
- 2
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper characterizes universal Bellman completeness for linear spaces of state values containing constants in finite MDPs with at least two actions. It requires closure for every choice of represented action rewards and continuation values. It proves that this holds exactly when the space consists of all functions constant within partition blocks and transitions are lumpable for every action. It also provides finite certification procedures, approximate recovery results, and planning guarantees.
Critical strengths
The characterization gives universal completeness a concrete interpretation through state aggregation. The finite certificates and approximate recovery results extend the analysis beyond the exact characterization, connecting representation error to transition mismatch and planning loss.
Critical weaknesses
My main concern is the motivation for the universal condition. The introduction appeals to the importance of Bellman completeness in offline RL, but the paper studies the stronger requirement that one linear space of state values accommodate every independent choice of represented action rewards. Its relevance to an established learning or planning problem remains unclear. In particular, reward variation already forces maximum closure with zero continuation, so the partition conclusion depends crucially on this strengthening.
The advance over existing results also needs a sharper comparison. Chen and Jiang already connect completeness of classes of Q functions defined by a given partition to bisimulation. This paper derives the partition structure from a general linear space of state values under reward universality. An explicit comparison of the different reward quantifiers and function spaces would help establish the additional insight, including which approximate results go beyond existing abstraction guarantees.
Questions for authors
What concrete learning or planning problem benefits from this exact universal condition beyond ordinary completeness for a fixed reward?
Which parts of the characterization and defect identity provide new insights beyond existing equivalences between completeness and bisimulation and the classical result for linear spaces closed under pointwise maxima?
In what concrete regime do the separation or conditioning assumptions for approximate recovery hold, and when do the resulting planning bounds improve on a trivial bound?
5 comments
Reminder
Thank you again for your valuable feedback. As the end of the discussion period is approaching, we are hoping to hear your thoughts on our response. We hope that we have addressed your comments, and we would greatly appreciate it if you were willing to consider increasing your score if you are satisfied with our response.
Reminder
Dear Reviewer TkCD,
We hope our replies and the rebuttal revision PDF have addressed your concerns. Please let us know if there is anything further we can clarify during the rebuttal period. We would be happy to discuss any remaining issues.
Author Response
We thank the reviewer for their attention and reading of our paper. Below we try to address the concerns you raised.
We agree that, for a fixed task, studying completeness under a fixed reward is entirely reasonable. But we are interested in reusing the same representation across tasks with shared dynamics and different represented rewards. Universal completeness ensures that Bellman targets for these tasks remain in the same value space. We explain this motivation in more detail in our General Comment. We also evaluated learned representations with fitted value iteration. Training on a reward family reduced mean value error on held-out rewards by approximately 29% to 33% compared with training on one task.
Chen and Jiang (2019) study completeness for a fixed reward on a full Q-function class defined by a given partition. Theorem 3 starts from a general linear state-value space and allows each action's reward to vary independently within that space. This stronger condition lets us derive the partition itself and show that each action's transitions are lumpable with respect to it. For Theorem 6, Chen and Jiang already give a quantitative relation between Bellman closure defect and transition mismatch. Their bounds coincide when rewards agree within each block. We adapt this relation to our Bellman operator and value normalization. We agree that the original wording could make the identity appear to be an independent new contribution, and we will revise the contribution statement to clarify this point. Further details are provided in our General Comment.
Our approximate analysis also addresses how aggregation structure can be recovered from a small closure defect in a general value space. Theorem 7 shows that a sufficiently small, nonzero defect already forces an exact block-constant structure. Revised Theorem 18 (in our reply to Reviewer Db2T) recovers a nearby aggregation space under anchor conditioning and bounds both the distance to that space and its transition mismatch. These results provide the structure needed to apply abstraction guarantees. Theorem 8 then bounds planning error on the aggregation space for rewards that are constant on its blocks.
One concrete regime is when the dynamics admit a lumpable partition and the available features approximate its block indicators. For the exact indicators, choosing one anchor per block gives κI=1. Small perturbations that preserve the constant function keep κI close to one, and Proposition 19 bounds the resulting closure defect. Thus, sufficiently small perturbations satisfy the recovery condition εκI(1+κI)<1/d in revised Theorem 18. In one example with d=3 and nonzero feature perturbations, the selected anchors have κI≈1.001. The certified upper bound on εκI(1+κI) is 0.007515<1/3.
For planning with the true quotient transitions and rewards constant within each block, Theorem 8 gives a clear range where the bounds improve on the trivial bound 2Rmax/(1−γ). The value bound is smaller when λ<(1−γ)/γ, and the policy bound is smaller when λ<(1−γ)/(2γ). For example, with γ=0.92, λ=0.02, and Rmax=1, the value and policy bounds are 5.75 and 11.5, respectively, compared with the trivial bound of 25. For a partition recovered by Theorem 18, both bounds improve on the trivial bound whenever the theorem's upper bound on λ♯ is below (1−γ)/(2γ).