acceptodds
Under review as a conference paper at ICLR 2027

A Contractive Bellman Update Can Solve the Wrong Bellman Equation

Abstract

A contractive Bellman update can have a unique fixed point that recommends the wrong action. We study product eligibility traces where one outcome determines both a temporal-difference error and the coefficient scaling the inherited trace. In finite discounted models with deterministic state-action rewards, the fixed point combines an environmental first transition with an induced continuation kernel. A model can preserve every action gap on its own, yet produce a strict policy cycle through this mixed use. For fixed, reward- and policy-independent continuation kernels, a finite linear test characterizes preservation of every action comparison across rewards and stationary policies. The test permits state-dependent value errors and yields a closest compatible coefficient with unchanged conditional means. Without knowing the transition matrix, we also construct policy-dependent coefficients that can retain outcome dependence while preserving one selected comparison. The induced gap is a strictly positive multiple of the true gap, allowing exact pairwise policy improvement after re-evaluation. A learned-likelihood study connects the failure mechanism to an implemented update: more independent fitting data can make the wrong population ordering more likely. Values need not be exact to support correct policy comparisons.

Primary area:
reinforcement learning
Keywords:
Bellman operator, temporal-difference learning, fixed-point bias, likelihood weighting, reinforcement learning.

Reviews

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

This paper appears to study the use of eligibility traces in TD learning for policy evaluation. The authors consider a more general form of eligibility traces than those used in traditional TD(λ\lambda) and show that the limiting solution may differ from the original Bellman target.

Critical strengths

Understanding TD learning with eligibility traces that go beyond traditional TD$(\lambda)$ is potentially interesting and may advance the policy evaluation component of an overall actor-critic framework for RL, making this a timely and relevant research direction.

Critical weaknesses

This paper seems to have been largely generated by an LLM, with clear indicators such as unreadable combinations of words in sentences, numbering all equations in the appendix even though most are not referenced, and boxed environments highlighting important results. This makes it very hard to read and understand the paper and assess the novelty of the work.

Questions for authors

None.

Reviewer_nsKwOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary
  • This paper investigates how outcome-dependent eligibility traces can induce a biased Bellman operator that remains contractive but converges to a fixed point producing incorrect action rankings.

  • The authors derive the induced Bellman operator and an exact error-transport identity (Theorems 2–3), establish a necessary and sufficient condition for preserving action gaps across all rewards and stationary policies (Theorem 5), and construct transition-model-free coefficients that preserve selected pairwise action comparisons (Theorem 8).

  • The theoretical findings are supported by explicit counterexamples, including policy cycles, and experiments using learned likelihoods from Chunked-TD. The results demonstrate that incorrect action rankings can persist even as model estimation improves.

Critical strengths
  • Rigorous characterization of a subtle failure mechanism. The paper derives the population Bellman operator induced by outcome-dependent eligibility traces and shows that a contractive evaluator can converge to a fixed point that produces incorrect action rankings. The exact error-transport identity and explicit policy-cycle counterexample provide strong theoretical support for this finding.

  • Novel characterization of policy-comparison preservation. Theorem 5 establishes a necessary and sufficient condition for preserving action gaps across all rewards and stationary policies under mixed evaluation. This distinguishes the contribution from existing work on ordinary model equivalence. Experiments using learned likelihoods further demonstrate that the identified bias can persist even as model estimation improves.

Critical weaknesses
  • Limited scope and uncertain practical significance. The theoretical analysis is primarily restricted to finite tabular settings and specific outcome-dependent trace constructions. Although the experiments demonstrate incorrect action rankings, including with learned neural likelihood models, the evaluation settings remain relatively controlled. It is unclear how frequently this failure mechanism arises in practical deep RL applications and whether it leads to substantial downstream policy regret.

  • Limited evidence of practical advantages for the proposed correction. Theorem 5 relies on knowledge of the environmental transition kernel, while Theorem 8 preserves only a selected pairwise action comparison and requires reevaluation as the policy or selected pair changes. In Appendix F.4, the proposed rollout-based implementation achieves essentially the same policy improvement as direct Monte Carlo evaluation under matched interaction budgets, despite substantial sampling costs. Although this does not diminish the theoretical result, the paper does not establish when the proposed correction would offer computational or statistical advantages over simpler evaluation alternatives.

Questions for authors

The paper is technically sound and theoretically interesting, although its practical significance could be established more convincingly.

Could the authors clarify the intended practical role of the pairwise-preserving construction in Theorem 8, particularly in long-horizon settings where direct Monte Carlo evaluation can be costly?

In Appendix F.4, the proposed rollout-based implementation achieves essentially the same policy improvement as direct evaluation under matched interaction budgets, while requiring substantial sampling. This raises questions about the practical advantages of the proposed construction.

If the intended benefit is to retain the advantages of eligibility traces, could the authors explain how the construction could be incorporated into a learned TD critic without relying on repeated long rollouts? In particular, what advantages might it offer over simpler bias-avoiding trace schemes in terms of sample efficiency, variance reduction, or experience reuse?

Clarifying whether Theorem 8 is primarily an existence result or a step toward a practical learning algorithm would help assess its significance.

1 comment

I appreciate the theoretical contributions of this paper and find its main mathematical results meaningful. The authors' response has also clarified several of my concerns.

However, I share the other reviewers' concerns about the clarity and readability of the presentation. Given the importance of clear communication at a conference, I do not think the current presentation warrants a stronger recommendation.

I therefore maintain my rating.

Reviewer_Kkx9OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2(+1)
Soundness
3
Read review
Paper summary

The title is very clear: it studies the circumstances on the which Bellman update, despite being contractive will give the wrong answer.

However, I find the difficult to summarize the rest of the paper given how it is presented. I failed to see the big picture even if I can follow the individual steps more or less. I also don’t see the connection between the main claim of the Bellman update and convergence, and how the paper is developed.

Critical strengths

The paper appears technically solid, and well studied. Multiple theorems are proven.

Critical weaknesses

I do not really get what the paper is trying to do. I should be able to follow the material, but I cannot see the big picture in the thicket of developments. Maybe the paper needs the space of a journal to make its point. I will detail my issues below.

Abstract: “can preserve every action gap on its own, yet produce a strict policy cycle through this mixed use” – what does this mean? What do you mean by preserving the action gap? What is the policy cycle? What mixed use are you talking about?

The statement “without knowing their transition, matrix…“ is not clear either

The rest of the section starting from “a learned likelihood study” to the end of the abstract is equally obscure, although there’s an idea what might be said here.

Line 036: is that figure 1b?

Line 041: how is the bridge evaluated at 0.6632? Even if there’s no discount I compute a probability of 0.64 of crossing it. There’s something substantially missing from the explanation how this is computed.

Explain the success probability \rho. How does one get the formula p^2(3-2p)? Maybe it’s trivial, but it’s not obvious to the reader.

Line 051: “some errors therefore leave every comparison unchanged even when they vary across states“ – what is projected out here? Something is clearly ignored. What is it?

Line 080: “phase lag delays that scaling by one step” - more explanation required.

Lines 083 and 084: the reviewer does not understand the caption for (d)

Line 087: what is a continuation kernel? Define.

Line 094-099, end of section: the reviewer did not understand what the paper talks about here

Line 135, equation (6): what is the link of this statement to subsequent theorems?

Line 146, proposition 4: what does causal solution mean?

Line 173: the word “with“ is missing before the word “actions“

The statement “in the row order“ followed by the tuples is not clear.

Lines 177 and 178: unclear

Line 191 and following: here is something interesting when you talk about evaluation do you mean Bellmann evaluation or something else? It is not clear what you mean by the cycle. Clearly, if there’s a cycle, it means it does not converge. How is it a contraction? Could it be that there are multiple contractions composed with each other. As this seems to be the closest to the title of the paper, it would be very important to resolve this to the reader.

Line 211: and following – I do not really understand equation 13 and what it’s trying to do

Line 314, theorem 8: how do I see from it that the pair’s ordering, including ties preserved?

Line 351, equation 20: what is \eta_g? I don’t think this has been defined.

Line 395, figure 2 caption: it appears that if the purpose of these diagrams had been described earlier, it might be easier for the reader to understand what’s going on.

Questions for authors

Can you make more transparent what your claim is and how your plan is to make this statement? There are too many assumptions about what the reader knows, even an experienced reader, who is not working the specific specialization in which the paper operates.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.