Offline RL Without Bellman Completeness: FORE Drops the Hardest Assumption

Paper: 2607.05375 Authors: Lars van der Laan, Nathan Kallus Categories: stat.ML, cs.LG

The Gap

Offline policy evaluation (OPE) answers a deceptively simple question: if we had run a different policy, what would the total reward be? The dominant toolkit relies on occupancy ratios—the density ratio between the target policy’s state-action distribution and the behavior policy’s distribution. Primal-dual and minimax methods (e.g., dual doubly robust estimators, minimax weight learning) estimate these ratios by enforcing occupancy-balance moments over a critic class. The catch: their convergence guarantees require Bellman completeness—the assumption that applying the Bellman operator to any function in your value-function class stays inside that class. This is a strong structural condition on the hypothesis space that rarely holds in practice and is essentially impossible to verify.

The authors observe that existing fitted Q-evaluation analyses also lean on Bellman completeness or its cousin, projected-operator stability. The gap is clean: can we do offline policy evaluation with just realizability—the assumption that our hypothesis class contains the thing we’re looking for—without demanding closure under Bellman operators?

Problem: Offline policy evaluation needs occupancy ratios
    |
    v
Prior methods: primal-dual / minimax -> enforce balance moments
    |
    v
Requirement: Bellman completeness on value-function class
    |              \
    |               \ (rarely holds, hard to verify)
    v                v
Gap: Can we drop Bellman completeness?
    |
    v
FORE approach: adjoint Bellman recursion on ratios
    |
    v
Only need: realizability of the occupancy ratio itself
    |
    v
Evidence: KL-contraction + finite-sample regret bounds
    |
    v
Conclusion: Ratio realizability suffices for OPE

The Increment

One sentence: Before this paper, offline policy evaluation methods needed Bellman completeness (a structural closure condition on function classes); after this paper, we know that merely assuming the ratio is in your hypothesis class is sufficient.

Core Mechanism

FORE works with the discounted occupancy ratio (w(s,a)), which measures how much more (or less) likely the target policy visits a state-action pair compared to the behavior policy, accounting for temporal discounting. Instead of estimating this ratio indirectly through value functions and balance constraints, FORE directly characterizes (w) through an adjoint Bellman recursion: the ratio at the current timestep equals the immediate importance weight plus the discounted expected ratio at the next timestep, averaged over the behavior policy’s transitions.

At each iteration, FORE solves a single-level KL-projection problem: given the current ratio estimate, apply the adjoint Bellman operator to get a target, then project that target back onto the log-ratio hypothesis class by minimizing KL divergence. This is a simple supervised regression on one-step transition data—no inner optimization loop, no adversarial training. The key mathematical insight is that the adjoint Bellman operator is a contraction in KL divergence (relative entropy), so repeated projection converges to the fixed point, which is the true ratio.

The fitted ratio then supports three downstream estimation strategies: direct reward reweighting (weight observed rewards by the ratio), occupancy-weighted fitted Q-evaluation (use the ratio to reweight a fitted Q-function), and doubly robust estimation (combine the ratio with a Q-function for variance reduction).

Iteration t:
                                     
  w_t(s,a)  -----> Adjoint Bellman Operator ----->  T[w_t](s,a)
  (current ratio)    (one-step transition)          (target)
                           |
                           v
                    KL Projection onto
                    log-ratio class H
                           |
                           v
                    w_{t+1}(s,a) = argmin_{h in H} KL(T[w_t] || h)
                    (next ratio estimate)
                           |
                           v
                    Repeat until convergence
                    (KL contraction guarantees fixed point)

Structural metaphor: Calibrating a bathroom scale with known weights.

Imagine you have a bathroom scale that might be miscalibrated. You want to find the correction factor (how much to multiply every reading by to get the true weight) for every possible weight on the scale. The adjoint Bellman recursion is like this: if you know the correction factor at 150 lbs and you know the physical relationship between adjacent readings, you can infer what the correction factor should be at 149 lbs and 151 lbs. Each iteration is like placing a known weight on the scale, computing what the corrected reading *should be, then turning the calibration knob to minimize the gap between your current correction curve and the target. The KL projection is your “turning the knob” step—it adjusts your correction function to be as close as possible to the target in a relative-entropy sense. The contraction property means each calibration step gets you strictly closer to the true correction curve. You don’t need to know anything about the scale’s internal mechanism (no Bellman completeness); you just need your correction curve to be flexible enough to represent the true one (realizability). After enough rounds, the scale is calibrated.

Key Concepts

• Occupancy ratio: Suppose you’re a doctor who treated patients under guideline A, but you want to know what would have happened under guideline B. The occupancy ratio is, for each patient profile, how much more likely guideline B would have produced that profile compared to guideline A. If the ratio is 3 for young diabetic patients, it means guideline B “targets” that population three times more. Multiplying observed rewards by this ratio reweights your observed data to look like it came from guideline B—without actually running guideline B.

• Bellman completeness: This is the assumption that if you take any value function from your hypothesis class and apply one step of the Bellman equation (compute the one-step backup), the result is still representable in the same class. It’s like saying: if your spreadsheet can represent any polynomial of degree (\leq 3), and the operation “multiply by (x) and add 1” always produces another polynomial of degree (\leq 3), you’re complete. In practice, this almost never holds—the backup pushes functions outside the class, creating approximation errors that compound. This paper avoids needing this entirely.

• Adjoint Bellman operator: The standard Bellman operator propagates *values forward in time (what’s the value of this state given future values?). The adjoint propagates importance weights backward—how much does the current state-action pair matter for the overall distribution mismatch? Think of it as the difference between tracking “where does the river flow?” (forward/standard) versus “where did the water in this bucket come from?” (backward/adjoint).

Framework Shift

Before (mainstream approach):        After (this paper):

 Value class V                        Ratio class W
      |                                    |
      v                                    v
 Bellman operator T_V                 Adjoint Bellman T_W
      |                                    |
      v                                    v
 Balance constraints                  KL projection
 (enforce T_V[V] in V)               (project T_W[w] onto W)
      |                                    |
      v                                    v
 Requires: V closed under T_V         Requires: W contains true w
 (Bellman completeness)              (realizability only)
      |                                    |
      v                                    v
 Optimization: minimax /              Optimization: single-level
 primal-dual (hard)                    regression (easy)

From value-function completeness to ratio-function realizability, the core shift is moving the locus of approximation from the space where closure is demanded to a space where mere containment suffices.

Expert Assessment

Problem choice: This is a genuine and well-posed gap. Bellman completeness has been the Achilles’ heel of offline RL theory for years—it’s the assumption everyone makes and nobody likes. The occupancy-ratio angle is not entirely new (dual importance-weight estimators exist), but framing the problem as a fixed-point iteration on ratios rather than values is a clean conceptual move. This sits at a productive intersection of density ratio estimation, operator theory, and offline RL.

Method maturity: The approach is clever rather than brute force. The adjoint Bellman recursion as a KL-contraction is elegant and the single-level projection avoids the nested optimization headaches of primal-dual methods. However, the gap between the population-level contraction argument and the finite-sample bound involves approximation error terms that could be large in practice. The method inherits the usual curse of horizon through the discount structure—long horizons mean the ratio can become extreme, and KL projection on extreme ratios is numerically fragile.

Experimental integrity: This is a theory paper—the contribution is the theoretical framework and the finite-sample bounds, not empirical benchmarks. The absence of experiments is appropriate for the contribution, though it does mean we lack evidence on whether the KL projection step is practical at scale or whether the ratio class realizability assumption is more or less restrictive than Bellman completeness in practice.

Writing quality: The paper is technically dense but well-structured. The connection between the adjoint Bellman operator and KL-contraction is the conceptual core, and the authors explain it clearly. Where they cut corners: the discussion of *why ratio realizability is easier to satisfy than Bellman completeness is thin—more concrete examples (even toy MDPs) showing the difference would strengthen the narrative considerably. Section 4 on downstream estimators could also benefit from a running example.

Verdict: weak accept — The theoretical contribution is clean and fills a real gap, but the absence of any empirical grounding or concrete guidance on choosing ratio classes leaves practitioners without a clear path to adoption.

Takeaways

1. Reframe value estimation as ratio estimation. If you’re working on off-policy evaluation and hitting completeness walls, consider whether the object you’re estimating can be switched from a value function to a density ratio. Ratios often have simpler structure and weaker approximation requirements.

2. KL-contraction as a design principle. When designing iterative procedures for distribution-related quantities, check whether your operator contracts in KL (or another f-divergence). If it does, you can use single-level projection instead of adversarial training—the analysis becomes cleaner and the optimization easier.

3. The adjoint perspective on Bellman equations. The idea of studying the *adjoint of a forward operator—propagating weights backward rather than values forward—is a general technique that applies beyond RL. Anytime you have a Markov chain and want to understand distribution shift, the adjoint recursion gives you a direct handle on the density ratio without going through the value function.