acceptodds
Withdrawn from ICLR 2027

Nearly Quadratic Query Complexity for Smooth Bellman Fixed Points

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Smooth Bellman equations arise in entropy-regularized planning, but estimating their fixed points requires resolving recursively nested continuation values. We show that pointwise estimation with a generative model admits nearly quadratic query complexity on arbitrary measurable state spaces. For bounded rewards, finitely many actions, and smooth backups with gradient norm bounded by \(G\) and contraction condition \(\beta G<1\), our algorithm achieves root mean squared error \(\varepsilon\) using \(\varepsilon^-2\exp\!\bigl(O([\log(1+\log(1/\varepsilon))]^2+1)\bigr)\) queries under a deterministic budget, with all structural parameters fixed. The construction builds on SmoothCruiser’s derivative correction and couples adjacent accuracies through a shared action proposal, accommodating signed derivatives while ensuring increment second moments of order \(u\). This coupling yields a quantitative transformation of any certified cost exponent \(p>2\) into \(1+p/2\). Controlling the constants across an accuracy-dependent number of stages gives the stated bound, improving fourth-power accuracy dependence to quadratic dependence up to a subpolynomial overhead. Independent median amplification adds a factor \(1+\log(1/\delta)\), and a matching confidence-dependent lower bound establishes the necessity of this factor over the full class. We also derive a regularized root-decision guarantee and present finite-state diagnostics of the coupling mechanism. Exact quadratic complexity for general nonlinear backups remains open.

Primary area:
reinforcement learning
Keywords:
Bellman equations, query complexity, multilevel Monte Carlo, entropy-regularized reinforcement learning, planning with a generative model, fixed-point estimation, sample complexity

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 5 reviews, above 27% of the others.
Reviewer_2XPeOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper presents techniques for solving reguarlized Bellman optimality equations, with the main result being an optimal bound with O(1/\epsilon^2) sample complexity, in the desired approximation error \epsilon, improving on previously known rates that scale with O(1/\epsilon^4). The authors also propose a multilevel wrapper around any prior algorithm to boost its error guarantee from an exponent of p to 1+p/2 in \epsilon.

I am unable to give a more intelligible summary, however, since the paper is an AI generated proof summary of an AI generated proof. There is no exposition, and no attempt to make this work human readable.

Also, this is a highly niche topic in a generative model that is only of theoretical interest since it is not applicable to practical problems in an obvious manner. It is not clear to me if ICLR is even a sensible venue here.

Critical strengths

The main 1/\epsilon^2 guarantee as well as the wrapper around black-box algorithms looks interesting and novel. The coupling techniques used to achieve this is also very nice.

Critical weaknesses

The paper has a bibliography of 7 related works on a well-studied topic.

The work reads like a proof and a summary of that proof. The main text does little to actually develop an exposition that explains the problem, its significance, its connection with the broader field, a buildup of the key techniques and a deconstruction of the key results in helping the reader understand the work. As submitted, this is not what a technical paper is supposed to read like.

There is also the issue that the importance and significance of the question being asked is not so clear, since this is a highly niche topic that does not easily connect to practice due to the use of generative model. Note that the generative MDP model has existed for 20+ years since the foundational work of Kearns, Kakade and others, but rarely translated into practically usable insights.

Questions for authors

See the weaknesses above.

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

This paper investigates the estimation of smooth Bellman fixed points over an infinite horizon using a generative model. The proposed approach incorporates derivative-based corrections, a shared action-sampling proposal mechanism, and recursively coupled multilevel estimators. Given fixed smoothness parameters and contraction coefficients, this framework progressively improves the query-complexity exponent, ultimately achieving a complexity that is nearly quadratic in the reciprocal of the target precision, while maintaining a deterministic query budget and high-probability guarantees. For the problem of entropy-regularized planning, the study further establishes a nearly inverse-linear complexity bound for the local decision loss. Experiments conducted on small, finite state spaces demonstrate the advantages of coupling and multilevel allocation.

A notable limitation concerns the literature review and comparative evaluation. The paper overlooks the work Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing (Dam, ICML 2026), which improved the query complexity of the SmoothCruiser algorithm from O~(ε−4)\widetilde O(\varepsilon^{-4}) to O~(ε−3)\widetilde O(\varepsilon^{-3}) via second-order corrections, a result that also encompasses the entropy-regularized setting. Consequently, by benchmarking against the original version of SmoothCruiser (which carries a quartic exponent), the authors have omitted a significant advancement that is directly relevant to their work. The authors should clarify the distinctions between their proposed multi-level refinement method and the aforementioned higher-order correction approach, while also comparing their respective assumptions regarding smoothness, estimation guarantees, and computational conventions. The empirical evaluation is limited to comparing single-level and multi-level variants within the scope of this study; it fails to establish relative performance against Second-Order Smooth Planning for the same entropy-regularized problem. While achieving near-second-order complexity may represent a unique theoretical contribution, the absence of such a comparison diminishes the completeness of the discussion on novelty and leaves open the question of practical performance relative to the prior method.

Critical strengths

The paper establishes nearly quadratic query complexity with deterministic budgets and high-probability guarantees. Its key technical strengths are stable recursive coupling and explicit control of constants across successive complexity improvements.

Critical weaknesses

The paper omits the directly relevant SecondOrderSmoothCruiser (ICML 2026), leaving its literature comparison incomplete. Experiments use tiny synthetic models and lack comparison with this prior method, limiting evidence of practical

Questions for authors
  1. How does your method compare with SecondOrderSmoothCruiser (ICML 2026) in smoothness assumptions, correction mechanism, and query complexity, particularly on the shared entropy-regularized setting?

  2. Since the experiments use empirical-model proxies on three-state problems, how representative are they of the full recursive construction, and how does practical efficiency compare with SecondOrderSmoothCruiser on a common task?

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

The paper studies estimating a prescribed action value Q⋆(s,a)Q^\star(s,a) of a smooth, contractive Bellman fixed point with a generative model on an arbitrary state space. Building on the Taylor correction of SmoothCruiser, it constructs a recursive estimator whose fine and coarse levels share the action proposal, the sampled action and the transition, so that adjacent levels differ by O(u)O(u) in second moment. Combined with multilevel allocation, this maps any algorithm with cost exponent p∈(2,4]p\in(2,4] to one with exponent 1+p/21+p/2; iterating the map for an accuracy-dependent number of stages yields a deterministic budget of ε−2exp⁡(O((log⁡log⁡(1/ε))2))\varepsilon^{-2}\exp(O((\log\log(1/\varepsilon))^2)) queries, improving on SmoothCruiser's ε−4\varepsilon^{-4}. Two-point lower bounds show that the exponent 2 and the log⁡(1/δ)\log(1/\delta) dependence cannot be improved, and small finite-state experiments examine the coupling.

Critical strengths
  1. A substantive complexity improvement. Approaching the mean-estimation exponent of two in an infinite-horizon nonlinear recursion is a meaningful theoretical result. The guarantee accommodates signed gradients and does not depend on a finite-state representation.

  2. Nontrivial coupling and quantitative iteration. The shared proposal allows adjacent resolutions to reuse the same action and transition while their signed importance weights vary smoothly. Importantly, the paper controls second moments and cutoffs uniformly across stages and proves log⁡Cm=O(m2)\log C_m=O(m^2). This is essential for turning a fixed-stage exponent improvement into the stated accuracy-dependent guarantee.

  3. Careful accounting and transparent scope. The central coupling and complexity arguments appear coherent on inspection; I did not identify a specific error in these steps. The construction includes auxiliary queries, sample ceilings, initialization, and confidence amplification in a deterministic budget. The paper also clearly acknowledges the unresolved quadratic endpoint, fixed-parameter scope, and distinction between its experimental implementation and certified algorithm.

Critical weaknesses
  1. The trade-off between the improved exponent and the structural constants is unclear. The near-quadratic guarantee holds for fixed discount, action count and smoothness, and the explicit construction carries extremely conservative constants. In the standard entropy example (R=0.2R=0.2, G=1G=1, L=5L=5, K=2K=2, β=0.7\beta=0.7), the fixed initializer Wu0W_{u_0} alone has a query budget of about 1048410^{484}. The appendices specify these constants algorithmically but give no interpretable comparison with SmoothCruiser in terms of 1/(1−βG)1/(1-\beta G), KK and LL. It is therefore unclear in which accuracy regimes the improved exponent yields a useful guarantee, particularly as the effective horizon grows or the temperature decreases.

  2. The experiments neither test the full recursive construction nor compare against existing alternatives. The experiments use three-state, two-action models. Their tabular empirical-model proxies replace the preceding-stage recursive estimator, so the experiments evaluate neither repeated exponent bootstrapping nor operation without an enumerable state space. Figure 2 compares coupling variants, and Figure 3 compares multilevel allocation with plain averaging of the same finest-resolution estimator. These are useful mechanism checks, but no external method is evaluated, including SmoothCruiser and direct empirical-model planning. The latter is a natural baseline here, since the experimental proxies already enumerate all states and solve empirical Bellman equations. The experiments therefore provide limited evidence of the computational benefits of the complete framework.

  3. A closely related entropy-specific MLMC method is not discussed. Section 2 and Appendix A omit Meunier, Reisinger, and Zhang (2025), who also combine fixed-point iteration with recursive MLMC for infinite-horizon entropy-regularized MDPs and obtain polynomial complexity in expectation. Their assumptions, action spaces and budget convention differ from those here. A theorem-level comparison on the common finite-action subclass would clarify which gains come from the shared-proposal coupling and the quantitative bootstrap.

References

  • Meunier, M., Reisinger, C., and Zhang, Y. Efficient learning for entropy-regularized Markov decision processes via multilevel Monte Carlo. arXiv:2503.21224, 2025.
Questions for authors
  1. Could you provide an analytical comparison or a modest experiment that separates the benefit of recursive bootstrapping from the benefit of standard multilevel allocation? On the finite-state examples, a direct empirical-model estimator would also be an informative baseline.

  2. How does the result compare with Meunier et al. (2025) on their common finite-action entropy-planning subclass, accounting explicitly for contraction assumptions, accuracy exponents, and expected versus deterministic query budgets?

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

This paper reports a new result in the setting of planning with a simulator, where one can query any state-action pair and receive a sampled reward and next state. The objective is to estimate the value of a given root state using as few oracle calls as possible, with a cost independent of the size of the state space. The Bellman max is replaced by a known smooth backup (e.g., the entropy-regularized soft-max). The main result is an algorithm with a deterministic query budget of ε−2exp⁡(O((log⁡log⁡(1/ε))2))\varepsilon^{-2}\exp\big(O\big((\log\log(1/\varepsilon))^{2}\big)\big) for RMS error ε\varepsilon, plus a log⁡(1/δ)\log(1/\delta) factor for high probability, improving on the ≈ε−4\approx\varepsilon^{-4} of SmoothCruiser. The method combines SmoothCruiser's Taylor correction with a coupled multilevel Monte Carlo estimator, and iterates this improvement a growing number of times. Lower bounds of Ω(ε−2log⁡(1/δ))\Omega(\varepsilon^{-2}\log(1/\delta)) are shown on linear models, and experiments on small 3-state MDPs study the coupling mechanism.

Critical strengths

The main strenghts are related to the results and the methodology:

  • A clear theoretical improvement for state-independent smooth planning. Improving on SmoothCruiser's ε−4\varepsilon^{-4} to an exponent of 2+o(1)2+o(1), with a deterministic budget and no dependence on the number of states, is a meaningful step for entropy-regularized planning with a simulator.

  • The step-by-step improvement of the exponent (p↦1+p/2p \mapsto 1 + p/2) is a nice idea. Each stage takes the previous algorithm and makes it faster, and the constants stay under control across stages. The key trick is to make the two coupled estimates share the same random action and transition, which keeps the variance small even when the weights can be negative. This idea could be useful in other recursive estimation problems.

Critical weaknesses

The main weaknesses of the paper are related to how difficult it is to read, due to the complex and unclear presentation of the setting, the related work, and the algorithms. In detail:

  • The setting is never stated as a formal problem. The problem definition and the related work section are very limited, which makes it difficult to position the paper within the existing literature. Table 1, which should serve as the comparison, mixes incomparable cost conventions.
  • The novelty with respect to Beck et al. (2023) is unclear. The comparison with this paper, the main reference used by the authors, is described only as "an inference from these formulas" (Appendix A), so it is difficult to understand how novel the contribution is.
  • The mathematical construction is hard to follow. Many symbols are reused with different meanings, and several parameters are used before they are defined.
  • The experimental validation is limited. The experiments use 3-state models, do not implement the analysed algorithm, and compare against no baseline. There is no plot of cost vs. ε\varepsilon showing the change in the exponent.
Questions for authors
  1. Please confirm the setting: is independence from ∣S∣|S| the main point of the result?

  2. Could you add an experiment showing cost vs. ε\varepsilon for SmoothCruiser against stages 1 and 2 of your construction, on a problem that is not trivially solvable in closed form? Does the measured exponent actually improve from stage to stage?

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

This paper develops a recursively coupled multilevel construction for smooth contractive Bellman operators, achieving nearly quadratic dependence on accuracy in pointwise query complexity. It also uses finite-state experiments to examine the underlying estimation mechanisms.

Critical strengths

The stage-uniform coupling and control of constants represent a substantive theoretical advance. The paper achieves nearly quadratic query complexity for a relatively general class of smooth contractions with fixed structural parameters. This result does not follow directly from existing fixed-depth analyses. The related result by Dam (2026) still has approximately cubic dependence on accuracy and assumes a Lipschitz-continuous Hessian. Reference

Critical weaknesses

There remains an enormous gap between the explicit construction and an executable algorithm. Recalculating the query budget using the base tree specified in the appendix and the structural parameters from the paper's entropy experiment gives approximately 10484.510^{484.5} queries for a single base estimation. The experiments instead use a substitute base estimator and therefore do not validate the complete construction. This substantially limits the practical relevance of the result. Moreover, the repeated qualifications concerning the distinction between the theoretical construction and the experiments make the main text unnecessarily difficult to read.

Questions for authors

For what ranges of structural parameters and target accuracy does the complete construction have a computationally feasible query budget?

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

Related papers

Discussion (0)

Sign in to comment.