Nearly Quadratic Query Complexity for Smooth Bellman Fixed Points

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.