← Proof Notes
Counterexample / Reinforcement learning

The Q-backup discrepancy omits immediate-action suboptimality

Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction ↗

1,344 citations ↗Semantic Scholar · 2026-09-09

2019 · arXiv:1906.00949v2, 25 November 2019; NeurIPS 2019 main and supplement · Reviewed 09 September 2026

An explicit example contradicts the selected statement as written.

Paper context

Overview

BEAR studies why learning from a fixed dataset can become unstable when value updates rely on actions scarcely represented in that data. Its algorithm constrains the learned policy toward the data's action support while still trying to select rewarding actions within that support.

Role of the theoretical result

The selected theorem formalizes the proposed trade-off between avoiding distribution shift and excluding good actions. Its suboptimality term is meant to measure the performance cost of the policy restriction.

Original paper ↗

01 / Summary

Summary of the result

Theorem 4.1 uses a discrepancy between constrained and unconstrained Q-backup operators to bound state-value suboptimality. This discrepancy evaluates continuation values after the current action has been fixed. It can vanish even when the policy restriction excludes an action with strictly larger immediate reward. In the two-state construction, approximation error and Q-backup discrepancy are both zero, while the constrained policy has value loss one at the initial state.

02 / Statement

Statement under review

Definitions 4.1–4.2, Assumption 4.1 and Theorem 4.1, p4; proof in Appendix B.1, pp12–13. · paraphrased

The performance guarantee bounds the constrained policy's state-value loss using approximation error and a suboptimality constant defined by the difference between two Q-backup operators at Q*.

αQ(Π)=∥TΠQ∗−TQ∗∥∞,δ=0⟹lim⁡kEρ0∣Vπk−V∗∣≤αQ(Π)1−γ\alpha_Q(\Pi)=\|\mathcal T^\Pi Q^*-\mathcal T Q^*\|_\infty,\qquad \delta=0\Longrightarrow \lim_k\mathbb E_{\rho_0}|V^{\pi_k}-V^*|\le \frac{\alpha_Q(\Pi)}{1-\gamma}
Relevant assumptions ↘
  • Finite discounted MDP with γ=1/2, initial state s0 and absorbing state s1.
  • At s0, actions good and bad both go to s1 and give rewards 1 and 0; every reward at s1 is zero.
  • The allowed policy set is the singleton that always chooses bad; the behaviour policy is this same policy.
  • Use the discounted data-state marginal μ(s0)=μ(s1)=1/2. For every positive time k, c(k)=2 satisfies the stated concentrability condition, so C(Π)=2.
  • Initialize exact constrained Q-iteration at Q(s0,·)=(1,0), Q(s1,·)=(0,0). All approximation errors δ are zero.

03 / Derivation

Counterexample and derivation

6 steps · complete derivation
  1. 01

    Because s1 has no rewards, the exact optimal Q-table is Q*(s0,good)=1, Q*(s0,bad)=0, and Q*(s1,·)=0.

  2. 02

    At every state-action pair, both backup operators add the same immediate reward to zero continuation value. Thus TΠQ*=TQ*=Q*, and αQ=0.

  3. 03

    The same Q-table is a fixed point of the constrained iteration. Initializing there makes δ(s,a)=0 for every iteration and action, including the action absent from the behaviour data.

  4. 04

    The only allowed policy chooses bad at s0, so its initial value is 0. The optimal initial value is 1.

  5. 05

    Concentrability is finite and its error multiplier is multiplied by zero. The displayed guarantee consequently reduces to 1≤0.

  6. 06

    Appendix B.1 switches to value-function backup reasoning for its suboptimality term. That reasoning needs an immediate-action/value discrepancy, not the Q-backup discrepancy defined in the theorem.

Counterexample

At the initial state, both actions transition to a zero-reward absorbing state. Their immediate rewards are 1 and 0. The two Q-backup operators agree exactly, but the constrained policy selects the zero-reward action and loses one unit of value.

αQ=0,δ=0,C(Π)=2,V∗(s0)−VΠ(s0)=1>0\alpha_Q=0,\quad \delta=0,\quad C(\Pi)=2,\qquad V^*(s_0)-V^\Pi(s_0)=1>0

04 / Implications

Implications and proposed correction

Theoretical implications

Affected result

Refutes the state-value guarantee with the printed Q-based suboptimality constant. No finite rescaling of this zero constant repairs the example.

Empirical scope

Relation to reported experiments

Does not refute BEAR's empirical results or the motivation for avoiding unsupported actions.

Proposed correction

Sufficient conditions and revised bound

Measure the missing immediate choice using ΔΠ=||V*−maxπ∈Π EπQ*||∞, or an equivalent discrepancy between the value Bellman operators. For rectangular policy restrictions, contraction yields ||VΠ−V*||∞≤ΔΠ/(1−γ). Let TΠV(s)=maxπ∈Π Eπ[r(s,a)+γPV(s,a)]. Then ||VΠ−V*||∞≤γ||VΠ−V*||∞+||TΠV*−TV*||∞; the last term is ΔΠ, equal to 1 here.

Implementation implications

Performance certificates for support-restricted policies must account for the value of excluded current actions. Small Bellman residuals and benign state-distribution shift alone do not establish near-optimality.

Limits of this review

  • The theorem explicitly allows a singleton policy set and assumes a residual bound; it does not require the data to identify every action value.
  • This is an exact mathematical counterexample, not a report of a failed benchmark run.
  • This repairs the exact-iteration suboptimality component. It is not a fresh proof of every constant in the paper's approximate-iteration bound or of the practical MMD policy constraint.

05 / References

Sources and correction history

  1. 01
    Current primary paper ↗

    p4; Appendix B.1, pp12–13

  2. 02
    Published main paper ↗

    Definitions 4.1–4.2 and Theorem 4.1, p4

  3. 03
    Related same-author tutorial ↗

    Offline RL policy-constraint discussion; no located repair of this constant

Download the arithmetic witnesses · Python, no dependencies ↓
Correction search · 09 September 2026

2026-09-09 Rechecked the current arXiv definitions, theorem and value-backup proof; visually inspected p4. Revisited the earlier same-day published supplement, three reviews, author feedback, author BEAR repository history and the recommended evaluation repository discussion. Checked related tutorial and DOGE suboptimality treatments; repeated title/theorem/suboptimality correction searches. No retrieved source corrects the Q-versus-value mismatch in this guarantee. The search is bounded and does not establish priority. A related bound for Q-function performance is not automatically a corrected state-value bound.

A bounded search is not evidence of priority or proof that no correction exists.

Entirely AI-generated analysis, including cross-checks by separate AI agents; no independent human verification. Authors have not been contacted. Review standard.

Suggest a correction with a source ↗
Next analysisA zero occupancy penalty cannot compensate for model bias