acceptodds
Under review as a conference paper at ICLR 2027

Universal Bellman Completeness Forces Lumpable State Partitions

Abstract

Bellman completeness is a key assumption in fitted value methods and offline reinforcement learning because repeated Bellman updates must remain representable in a fixed value space. However, its universal form leaves the structure of a complete value space and a way to check it unclear. We study this converse for a finite Markov decision process (MDP) with at least two actions and a value space containing the constant functions. We prove that closure under every optimal Bellman update using rewards and continuation values from the space holds exactly when the value space consists of functions constant on the blocks of a unique state partition, and the transition kernel for every action is lumpable with respect to that partition. Independent action rewards expose closure under pointwise maxima and isolate each action's transition kernel. Together, these constructions yield an exact finite certificate based on adaptive Bellman membership queries. On a block-constant value space, they also give an exact relation between the closure defect and transition mismatch. Under separation or conditioning assumptions, this relation supports block recovery and yields value and policy loss bounds.

Primary area:
learning theory
Keywords:
Bellman completeness, reinforcement learning theory, state abstraction, lumpability, quotient MDPs

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_TkCDOpenReview ↗
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
AuthorsOpenReview ↗

Author Response

We thank the reviewer for their attention and reading of our paper. Below we try to address the concerns you raised.

W1/Q1: Motivation for the universal condition.

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.

W2/Q2: Comparison with existing results.

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.

Q3: When do the recovery conditions hold, and when are the planning bounds informative?

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\kappa_I=1. Small perturbations that preserve the constant function keep κI\kappa_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\varepsilon\kappa_I(1+\kappa_I)<1/d in revised Theorem 18. In one example with d=3d=3 and nonzero feature perturbations, the selected anchors have κI≈1.001\kappa_I\approx1.001. The certified upper bound on εκI(1+κI)\varepsilon\kappa_I(1+\kappa_I) is 0.007515<1/30.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−γ)2R_{\max}/(1-\gamma). The value bound is smaller when λ<(1−γ)/γ\lambda<(1-\gamma)/\gamma, and the policy bound is smaller when λ<(1−γ)/(2γ)\lambda<(1-\gamma)/(2\gamma). For example, with γ=0.92\gamma=0.92, λ=0.02\lambda=0.02, and Rmax⁡=1R_{\max}=1, the value and policy bounds are 5.755.75 and 11.511.5, respectively, compared with the trivial bound of 2525. For a partition recovered by Theorem 18, both bounds improve on the trivial bound whenever the theorem's upper bound on λ♯\lambda_\sharp is below (1−γ)/(2γ)(1-\gamma)/(2\gamma).

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.

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.

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

The paper studies a strong form of Bellman completeness in finite MDPs, where each action's reward can be chosen independently from a linear value space. It proves that closure under all optimal Bellman updates holds exactly when the space is block-constant on a unique state partition and the transitions are lumpable for every action. The paper also gives a finite test for completeness and studies approximate closure and its effect on planning. Synthetic experiments examine the theoretical results and compare quotient planning with several baselines.

Critical strengths
  1. The converse result is the strongest part of the paper. It shows that universal Bellman completeness requires a particular state partition and lumpable transitions, without assuming either structure in advance. The proof is relatively simple: independently chosen rewards allow the Bellman operator to recover pointwise maxima and isolate each action's transition. This makes it clear why the characterization holds and which assumptions are needed.

  2. I also find the exact defect identity ER(FP)=γλ\mathcal{E}_{R}(F_{\mathcal{P}}) = \gamma\lambda useful. It shows that, for block-constant value spaces, Bellman closure error is determined by differences in block-transition probabilities among states in the same block. The paper uses this connection to bound the error from planning on a reduced MDP. The finite completeness test is another useful result, since it replaces a condition over infinitely many rewards and values with a finite set of checks.

Critical weaknesses
  1. I am not sure how much the main characterization tells us about the Bellman completeness assumptions used in RL. Definition 1 allows the reward for each action to vary independently within the value space. This freedom is essential to the proof, but most RL settings have a fixed reward function. The connection to standard completeness assumptions in offline RL is therefore unclear. The experiments focus on synthetic MDPs with block structure and controlled perturbations, so they offer little evidence on this point.

  2. I could not justify the use of κ\kappa in Theorem 18. It is defined as κ=min⁡IκI\kappa = \min_{I} \kappa_{I}, but the proof uses Lagrange functions for a chosen anchor set II, which need not minimize κI\kappa_{I}. In particular, the bound ∥ℓi∥∞≤κ\lVert \ell_{i} \rVert_{\infty} \leq \kappa does not follow for an arbitrary II. The recovery guarantee seems to require either a minimizing anchor set or a condition stated in terms of κI\kappa_{I}.

Questions for authors
  1. Does Theorem 18 assume that the anchor set II minimizes κI\kappa_{I}? This seems necessary for the bound used in the proof. I would like to know whether the result holds for arbitrary anchor sets and how the intended condition relates to Figure 2(d).

  2. Is there a fixed-reward or Q-function version of Theorem 3? If not, a counterexample would be useful. I am also unsure which part of the converse is new relative to the classical results on finite vector lattices and lumpability.

  3. I could not find how acceptance was decided in Figure 2(c). Was the cutoff (λ0+λ1)/2(\lambda_{0}+\lambda_{1})/2 from Theorem 14, or was a different test used? The numerical settings for λ0\lambda_{0}, λ1\lambda_{1}, ξ\xi, and δ\delta, along with the construction of the near-boundary instances, are not clear from the experimental description.

6 comments
AuthorsOpenReview ↗

Author Response

We thank the reviewer for their careful and largely positive review of our work that helped us significantly improve it. Below we hope to address some of your concerns.

W1: Not sure how much the main characterization tells us about the Bellman completeness assumptions used in RL.

We understand your concern that most RL settings have a fixed reward, while our condition allows each action’s reward to vary independently. We agree that, for a fixed task, studying completeness under a fixed reward is entirely reasonable. However, completeness for one reward does not tell us whether the same representation remains complete for other tasks with the same dynamics. We are interested in identifying the representation structure that allows this guarantee to be reused across these tasks. We therefore keep the dynamics and features fixed and require completeness for every choice of represented action rewards, so that the guarantee does not depend on which reward in this family defines the task. Further details are provided in our General Comment.

We also expanded our experiments to include fitted value iteration and representation learning.

(i) We evaluated FVI by repeatedly computing Bellman targets from sampled transitions and fitting them by least squares. With 1,000 states and five features (λ=0\lambda=0), increasing samples per state-action pair from 32 to 256 reduced mean value error from 0.01706 to 0.00476 for the block space. The reward-matched general space remained near 0.171 at both sample sizes. Using the true transition kernel, the errors were approximately 1.2×10−81.2\times10^{-8} for the block space and 0.17035 for the general space. This shows how representation error can limit FVI accuracy even after transition estimation error is removed.

(ii) For representation learning, we trained two features alongside three fixed reward features, comparing one reward task with eight tasks using matched data and training budgets. We then froze the representations and ran FVI on 16 held-out rewards from the same reward space. The table reports mean value error in the supremum norm, averaged over rewards and initializations within each MDP, then over 20 MDPs per setting. Across these four settings, training on a reward family reduced mean FVI value error on held-out rewards by approximately 29% to 33% compared with training on a single task.

States  λ\ \ \lambdaSingle taskReward familyReduction
10000.050250.0355229.3%
1000.020.052850.0375229.0%
50000.045510.0304733.1%
5000.020.045170.0318229.5%

W2/Q1: Anchor choice in Theorem 18 and Figure 2(d).

Thank you for pointing this out. You are right that the original statement used the minimum condition number over all anchor sets, while the proof used the Lagrange functions of a chosen set II. We had only required the anchor matrix to be nonsingular, so the bound used in the proof was not justified for an arbitrary choice.

We have therefore revised Theorem 18 to use the condition number of the selected anchors throughout. The revised Theorem 18 applies to any anchor set II with nonsingular ΦI\Phi_I, provided its condition number κI\kappa_I satisfies εκI(1+κI)<1/d\varepsilon\kappa_I(1+\kappa_I)<1/d.

For any II with nonsingular ΦI\Phi_I, we define

\qquad \beta_I=\varepsilon\kappa_I(1+\kappa_I), \qquad \zeta_I=(d-1)\beta_I,$$ and require $\beta_I<1/d$. This choice gives the bounds used in the proof, $$\lVert \ell_i \rVert_{\infty} \le \kappa_I, \qquad \lVert f \rVert_{\infty} \le \kappa_I \max_{x \in I} \lvert f(x) \rvert \quad (f \in F).$$ The recovery conclusions and error bounds retain their original form with these corrected quantities. In particular, the anchors need not minimize the condition number and the guarantee applies whenever their own $\kappa_I$ satisfies the stated condition. Choosing minimizing anchors gives the special case $\kappa_I=\kappa_*$, where $\kappa_*=\min_J\kappa_J$ over nonsingular anchor sets. Figure 2(d) shows how the recovery threshold depends on dimension and anchor conditioning: $$\varepsilon_{\mathrm{crit}}(d,\kappa) =\frac{1}{d\kappa(1+\kappa)}.$$ The condition $\beta_I<1/d$ is equivalent to $\varepsilon<\varepsilon_{\mathrm{crit}}(d,\kappa_I)$, so a defect strictly below the corresponding curve satisfies the recovery condition. Following the revision to **Theorem 18**, we will replace $\kappa$ with $\kappa_I$ in Figure 2(d).
AuthorsOpenReview ↗

Author Response Part 2

Q2: Is there a fixed-reward or Q-function version of Theorem 3?

The fixed-reward version does not hold in general. We can see this with three states, two actions, and

\quad h=(0,1,2).$$ Let both actions leave the state unchanged and set both rewards to zero. Then $B_0v=\gamma v\in F$ for every $v\in F$. Here the Bellman update simply rescales the value function, so completeness holds even though $$h\vee\mathbf{1}=(1,1,2)\notin F.$$ Since $F$ is not closed under pointwise maxima, it cannot be a full block-constant space. For Q-functions, the analogous statement for the product space $G=F^{\mathcal A}$ also fails, even when we retain independently chosen action rewards. Here each action slice belongs to $F$. Keep the same $F$, but now let every action send every state to state $1$. For any $r,Q\in G$, $$(T_rQ)(s,a) =r_a(s)+\gamma\max_{b\in\mathcal A}Q(1,b).$$ The transition makes the continuation term constant across states, so every action slice stays in $F$. Thus $G$ remains closed under all these Bellman updates, although $F$ is not a full block-constant space. Our original contribution regarding Theorem 3 is explained in the **General Comment**. >Q3: Could not find how acceptance was decided in Figure 2(c). Apologies for the confusion. The original panel used a heuristic test. For the correct partition, it compared the sampled estimate with $\min\{0.35,2.2\sqrt{d/N}\}$, while the other cases used true transitions and a cutoff of $0.17$. The cases labelled as near the boundary were constructed by changing one state's partition label. The original figure plotted results based on samples alongside results based on the true model, which could make readers think that all curves showed the performance of a finite-sample test. We therefore reran all cases using sampled transitions and the midpoint test in Theorem 14. This lets us measure how reliably the test distinguishes small from large transition mismatch as the sample budget changes. The new test accepts when $\widehat{\lambda}\le(\lambda_0+\lambda_1)/2=0.07$, with $$\lambda_0=0.02,\qquad \lambda_1=0.12,\qquad \xi=0.04,\qquad \delta=0.05.$$ We now control $\lambda$ directly by shifting probability mass between two target blocks in one transition row. We tested $\lambda=0.019,0.02,0.12,0.121$ near the two guarantee boundaries and $0.06,0.07,0.08$ around the cutoff. Within $(\lambda_0,\lambda_1)$, we report acceptance rates. At $N=14{,}062$ samples per state-action pair, we observed no false rejections in 18,000 trials with $\lambda\le\lambda_0$ and no false acceptances in 18,000 trials with $\lambda\ge\lambda_1$.

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.

Reviewer_mbrjOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the conditions when a linear value space that contains the constant function is closed under every Bellman update in a finite MDP. The main result in the paper show that this holds if and only if the linear value space is the space of functions constant on the the blocks of a unique state partition, and every action’s transition kernel is lumpable with respect to that partition. Using two constructions, by setting two action rewards with zero continuations and giving all other actions a high negative reward, the paper proves a finite certificate with at most 3k−4+∣A∣k3k-4+|A|k Bellman membership queries, and further prove recovery and planning bounds. Their claims are also validated on synthetic block MDPs.

Critical strengths

The problem statement in the paper is well motivated, and the theoretical contributions are well presented. The proofs with the two constructions makes it clear to understand the partition and lumpabiliy. The theory in the main text seems correct, although I did not go through the appendix thoroughly. The paper is well written, and I found the boundary example in Appendix F to be very helpful.

Critical weaknesses

w1: The contribution does not seem very novel. The main theorem kind of follows already from Aliprantis & Border, 2006) [1] and the original introduction to lumpability from Kemeny & Snell (1960) (missing citation in the paper), and the reverse direction is well explored in the bisimulation literature. So the only novel contribution seems to be the two reward constructions, which does not seem significant.

w2: The experiments seem very limited, with only 20 states in the planning benchmark, and there are no experiments connecting the results to representation learning or fitted value methods.

[1] Aliprantis, Charalambos & Border, Kim. (2006). Infinite Dimensional Analysis: A Hitchhiker's Guide. 10.1007/3-540-29587-9. [2] Kemeny, J. G., & Snell, J. L. (1960). Finite Markov Chains. Springer.

Questions for authors

q1: See w1, could you clarify more on the novelty of the contributions? q2: in the finite certificate, the assumption is that an exact Bellman membership oracle is available. What would be a scenario when this is available but the transition kernel is not?

5 comments
AuthorsOpenReview ↗

Author Repsonse

We would like to thank the reviewer for their careful and detailed review of our work. Below we hope to address some of your concerns.

W1/Q1: The contribution does not seem very novel. Could you clarify more on the novelty of the contributions?

(i) We understand your concern, but we believe the two reward constructions provide the key new insight in Theorem 3(Contribution 1). Our core contribution is to use two carefully chosen reward constructions to turn the characterization of universally Bellman-complete value spaces into a problem that classical structural theory can resolve. Although short, these constructions separate the question of closure under the nonlinear Bellman operator into maximum closure and transition invariance, establishing the conditions needed by the classical results. We see the simplicity of this connection as a good thing. Further details are provided in our General Comment.

(ii) Here are some important and original insights you may find of interest. We give a finite certificate for universal Bellman completeness under an exact Bellman membership oracle (Contribution 2), and study how approximate completeness supports recovery of aggregation structure and planning guarantees (Contribution 3). In Theorem 7 (Contribution 3), a sufficiently small, nonzero closure defect already forces the value space to have an exact aggregation structure, under the stated separation condition. The novel insight is to construct approximate block indicators within the original space. If these approximations are sufficiently accurate, they remain linearly independent, forcing the number of blocks to equal the dimension of the space. This turns an approximation bound into an exact structural conclusion. We further extend the analysis in the Appendix to spaces containing a strictly positive function (Theorem 9), certification and planning with noisy features and sampled transitions under separation assumptions (Theorem 14), and recovery of nearby aggregation spaces under anchor conditioning (Revised Theorem 18 in our reply to Reviewer Db2T). The construction in Theorem 18 maybe particularly interesting. We use approximate closure and the anchor interpolation identities to show that the coordinates are nearly nonnegative and nearly disjoint. Since they sum to one, a sufficiently small defect forces a unique dominant coordinate at each state. We can therefore recover the partition directly by assigning each state to its dominant coordinate, and quantify both the distance to the resulting aggregation space and its transition mismatch.

W2: The experiments seem very limited.

We agree that the original experiments were limited in scale.

(i) We expanded the experiments from 20 to 1,000 states and from 5 to 250 features. At 1,000 states and 250 features, mean fitted value iteration (FVI) value error was 0.02974 using the true partition and 0.46749 using a reward-matched general space (λ=0\lambda=0, 256 samples per state-action pair). These results show that the block structure continues to give lower value error as both the number of states and the representation dimension increase.

(ii) We evaluated FVI by repeatedly computing Bellman targets from sampled transitions and fitting them by least squares. With 1,000 states and five features (λ=0\lambda=0), increasing samples per state-action pair from 32 to 256 reduced mean value error from 0.01706 to 0.00476 for the block space. The reward-matched general space remained near 0.171 at both sample sizes. Using the true transition kernel, the errors were approximately 1.2×10−81.2\times10^{-8} for the block space and 0.17035 for the general space. This shows how representation error can limit FVI accuracy even after transition estimation error is removed.

(iii) For representation learning, we trained two features alongside three fixed reward features, comparing one reward task with eight tasks using matched data and training budgets. We then froze the representations and ran FVI on 16 held-out rewards from the same reward space. The table reports mean value error in the supremum norm, averaged over rewards and initializations within each MDP, then over 20 MDPs per setting. Across these four settings, training on a reward family reduced mean FVI value error on held-out rewards by approximately 29% to 33% compared with training on a single task.

States  λ\ \ \lambdaSingle taskReward familyReduction
10000.050250.0355229.3%
1000.020.052850.0375229.0%
50000.045510.0304733.1%
5000.020.045170.0318229.5%
AuthorsOpenReview ↗

Author Repsonse Part 2

Q2: What would be a scenario when this is available but the transition kernel is not?

We understand that you may be concerned about whether the information access assumed in Contribution 2 is realistic. This is a reasonable concern. Actually, we introduce the exact membership oracle to study how finitely many checks of individual Bellman updates can certify closure across all represented rewards and continuation values. Contribution 2 thus complements the recovery and planning analysis in Contribution 3 with a finite certificate for exact completeness. We also extend certification to finite transition samples and noisy features in Theorem 14. Under the stated feature separation and noise conditions, we recover the partition and estimate its transition mismatch from samples. With sufficient samples, the theorem distinguishes small from large mismatch with high probability, provided the two regimes have a positive separation gap, and gives corresponding planning error bounds.

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.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Comment

We’d like to thank all the reviewers for their time and attention to our work, and for their enthusiasm. Their comments have helped us to improve and sharpen the paper. In general, the reviewers praised the structural characterization (Db2T, TkCD), finite certification (Db2T, TkCD), approximate recovery results (TkCD), and the clarity of the proofs (Db2T, mbrj). In addition, the reviewers shared concerns that we have tried to address. To highlight the largest changes, we have:

  1. Clarified the motivation and significance of universal Bellman completeness.
  2. Clarified our contributions relative to prior work.
  3. Added new experiments (fitted value iteration and representation learning) and expanded the scale of our evaluation.

We now run through the shared concerns in more detail.

Motivation. First, there was concern about (i) why we require completeness across represented rewards and (ii) how this helps with learning or planning (Db2T, TkCD). (i) In fitted value iteration, we want to compute accurate values using a restricted set of features. To avoid introducing representation error at each update, these features need to express the Bellman targets as well as the rewards. Otherwise, repeated fitting can have an error floor that more data alone cannot remove. We are interested in understanding what makes a representation reliable for these updates. Furthermore, completeness for one fixed reward does not tell us whether the same representation remains complete for other tasks with the same dynamics. We aim to identify representation structure that allows this guarantee to be reused across these tasks. We therefore study a uniform guarantee, keeping the dynamics and features fixed while allowing the action rewards to vary independently within the represented space. This lets us examine which representations support Bellman updates across the reward family, independently of the particular reward used to assess them. (ii) The same issue matters in state abstraction, where we want to reduce the state space while retaining the information needed for accurate planning. Discarding relevant state information can produce incorrect values even when the reduced model is estimated perfectly. Our work helps clarify when the universal completeness assumption on general value features justifies such a reduction. The same reduced transition model can then be reused across the represented reward family while preserving optimal values. Our approximate analysis further relates departures from exact completeness to planning error.

Contribution. Many reviewers pointed to the overlap with existing results and asked what our work adds (Db2T, TkCD, mbrj).

Theorem 3 (Contribution 1) characterizes universal Bellman completeness. The necessity proof has four steps:

  1. Use represented action rewards and zero continuation to derive closure under pointwise maxima.
  2. Apply the classical characterization of finite vector lattices (Lemma 2) to obtain a unique partition and equality with its full block-constant space.
  3. Use constant reward offsets to isolate each action and establish that its transition operator preserves the value space.
  4. Apply the classical equivalence between preservation of a block-constant space and lumpability.

Steps 2 and 4 use classical results on finite vector lattices [1] and lumpability [2]. Our core contribution is to use two carefully chosen reward constructions to turn the characterization of universally Bellman-complete value spaces into a problem that classical structural theory can resolve. The first uses zero continuation to express the pointwise maximum of any two represented functions as a Bellman update. The second uses constant reward offsets to make any selected action win at every state, showing that its transition must preserve the value space. We agree that these constructions are short. However, we see their simplicity as a strength! They let us separate maximization from transition and link universal Bellman completeness to the assumptions of these classical results. A useful parallel is [4], where a simple weight construction makes the connection between attention and gradient descent explicit.

Theorem 6 is not identical to the result in [3]. We adapt their relation between Bellman closure defect and transition mismatch to our Bellman operator and value normalization. The focus of Contribution 3 is the recovery and planning results in Theorems 7 and 8. We agree that the original wording could make the identity in Theorem 6 appear to be an independent new contribution. We will revise the contribution statement.

[1] Aliprantis and Border (2006). Infinite Dimensional Analysis: A Hitchhiker’s Guide.

[2] Kemeny and Snell (1960). Finite Markov Chains.

[3] Chen and Jiang (2019). Information-Theoretic Considerations in Batch Reinforcement Learning.

[4] von Oswald et al. (2023). Transformers Learn In-Context by Gradient Descent.

AuthorsOpenReview ↗

PDF Change

We thank all three reviewers again for their comments. We have uploaded the revised PDF. To briefly explain our submission edit, we clarified the motivation (Section 1 and Appendix G.2), corrected the anchor-conditioning statement (Appendix D.4), and expanded the experiments on fitted value iteration, reward transfer, and larger MDPs (Section 5 and Appendix F).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.