📊 statistics

Fitted Occupancy-Ratio Evaluation without Bellman Completeness

This paper introduces Fitted Occupancy-Ratio Evaluation (FORE), a method for offline policy evaluation that achieves convergence without Bellman completeness by relying solely on the realizability of the discounted occupancy ratio through a KL-contraction-based adjoint Bellman recursion.

Original authors: Lars van der Laan, Nathan Kallus

Published 2026-07-29

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Lars van der Laan, Nathan Kallus

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to play a video game, but you aren't allowed to let the robot play the game itself. Instead, you only have a giant, dusty notebook filled with moves and outcomes from a different player who played the game a long time ago. This is the world of "offline reinforcement learning." The challenge is that the robot's new strategy might look very different from the old player's notebook. If the robot tries to visit a part of the game world the old player never touched, the notebook has no data for that spot. It's like trying to navigate a new city using a map of a different city; you might get lost or make dangerous guesses. To fix this, scientists use a mathematical trick called an "occupancy ratio." Think of this ratio as a special magnifying glass or a set of weights that tells the robot: "Hey, the old player rarely went here, but our new plan goes there all the time. So, when we look at the old data, we need to give extra importance to the few times they did go there, and ignore the places they never went."

For a long time, figuring out these weights was like trying to solve a puzzle where every piece you placed made the next piece harder to find. The standard methods required a very strict condition: the "map" of the new strategy had to be perfectly compatible with the "map" of the old data in a complex, mathematical way. If the new strategy was too different, the math would break, and the robot would learn the wrong lessons. This paper introduces a new method called Fitted Occupancy-Ratio Evaluation (FORE). Instead of forcing the puzzle pieces to fit perfectly, FORE uses a clever, step-by-step approach that naturally corrects itself. It treats the problem like a game of "hot and cold," where the robot slowly adjusts its weights to get closer and closer to the truth, without needing the strict compatibility that used to be required. The authors show that as long as the robot's new plan can be described by the tools it has, it can learn the correct weights and make safe, accurate predictions about how well it will do, even if the old data was messy or incomplete.

The Story of the Self-Correcting Magnifying Glass

In the world of artificial intelligence, there's a classic problem: How do you judge a new plan using only old data? Imagine you are a coach trying to evaluate a new soccer team's strategy, but the only footage you have is of a completely different team playing in a different league. If the new team tries to score from a spot the old team never touched, your footage is useless. You need a way to "re-weight" the old footage so it looks like the new team played it. This is where the occupancy ratio comes in. It's a number that tells you how much more (or less) often the new team visits a specific spot compared to the old team.

The paper's authors, Lars van der Laan and Nathan Kallus, noticed that the old ways of calculating this ratio were like trying to balance a seesaw with a heavy, rigid bar. You had to assume that the "seesaw" (the math behind the scenes) was perfectly stable and that the new team's moves were perfectly predictable based on the old team's moves. If the new team did something unexpected, the whole calculation would wobble and fail. They called this the need for "Bellman completeness," which is a fancy way of saying, "The math must be able to describe every possible future move perfectly."

Enter FORE (Fitted Occupancy-Ratio Evaluation).

The authors propose a new way to find these weights that is much more flexible. Instead of trying to solve a giant, impossible equation all at once, FORE works like a sculptor chipping away at a block of stone. It starts with a rough guess and then repeatedly refines it.

Here is the magic trick:

The Adjoint Bellman Recursion: Imagine the occupancy ratio as a shadow cast by the new team's strategy. The paper shows that this shadow follows a specific rule (an "adjoint Bellman equation").
The KL Projection: Instead of forcing the shadow to fit a rigid mold, FORE uses a special kind of "magnifying glass" called KL divergence (a way of measuring how different two probability distributions are). At each step, FORE takes the current guess of the shadow and projects it onto the best possible shape it can make with the tools it has.
The Self-Correction: The most exciting part is that this process naturally shrinks the error. The authors prove that with every step, the guess gets closer to the true ratio, like a ball rolling down a hill into a valley. Crucially, this happens without needing the strict "Bellman completeness" assumption. The method works as long as the true ratio can be approximated by the tools the robot has, even if the tools can't describe every single future move perfectly.

What the Paper Actually Found

The authors didn't just dream this up; they proved it mathematically and tested it.

The Main Finding: They showed that FORE converges to the correct occupancy ratio. If the true ratio exists within the class of functions the algorithm is using (a condition called "realizability"), the error shrinks geometrically. This means the method is stable and reliable, even when the new strategy is very different from the old data.
What It Rules Out: The paper explicitly argues against the idea that you need "Bellman completeness" or "adjoint Bellman completeness" to get good results. In the past, researchers thought you needed a perfect map of all possible futures to make this work. FORE shows you don't. You just need a good enough approximation of the ratio itself.
The "What If" Scenarios (Coverage): The paper also tackles the problem of "insufficient coverage." What if the new team goes to a part of the field the old team never visited? In this case, the full ratio cannot be known. The authors introduce Coverage-Stopped FORE. This version acts like a safety valve. It estimates the value of the new strategy only up to the point where the data runs out. It provides a "conservative lower bound," essentially saying, "We know for sure the team will get at least this much value, even if we don't know what happens in the unexplored areas."

The Proof and the Play

To back up their claims, the authors did two things:

Mathematical Proofs: They provided rigorous proofs showing that the error in their method is bounded. They broke the error down into three parts: how far off the starting guess was, how well the tools could approximate the true ratio, and the statistical noise from having a limited amount of data. They showed that the method handles all three gracefully.
Simulations: They ran computer experiments to see how FORE performed in the real world of numbers.
- Experiment 1 (Baird-style MRP): They used a classic "star-shaped" problem where old methods (like standard Fitted Q-Evaluation) are known to explode and fail. FORE, however, stayed stable and converged to the correct answer.
- Experiment 2 (Linear-Gaussian): They tested a continuous problem where the math gets messy. Again, standard methods struggled, but FORE and a version of FORE that "re-weights" the data (FORE-reweighted FQE) performed much better, keeping the errors low even as the game got harder.
- Experiment 3 (Missing Data): They simulated a situation where the new strategy tried to go to places the old data didn't cover. The Coverage-Stopped FORE successfully identified the "safe" part of the strategy and gave a conservative estimate, while standard methods that tried to guess the missing parts failed miserably.

Why This Matters

This paper is a big deal because it removes a major roadblock in teaching AI from old data. For years, scientists thought you needed a perfect, complete understanding of the future to learn from the past. FORE shows that you can be "good enough" and still get a reliable answer. It's like saying you don't need to know every single street in a city to give someone good directions; you just need a map that covers the main routes well enough.

The authors are careful to note that this isn't a magic wand that solves every problem. If the new strategy goes to places the old data never touched, you still can't know the full truth. But for the parts you can see, FORE gives you a much more stable and reliable way to measure success. It turns a fragile, high-stakes calculation into a robust, step-by-step process that gets better the more you try.

In short, FORE is a new, more resilient way to teach robots to learn from history, proving that you don't need a perfect crystal ball to make a good guess about the future.

Technical Summary: Fitted Occupancy-Ratio Evaluation without Bellman Completeness

Problem Statement

Offline policy evaluation (OPE) aims to estimate the performance of a target policy $\pi$ using data collected from a behavior policy. A central challenge is correcting the distributional shift between the offline data distribution $\nu$ and the target policy's discounted state-action occupancy measure $d_{\pi,\gamma}$ .

Existing methods typically fall into two categories:

Value-based methods (e.g., Fitted Q-Evaluation, FQE): These estimate the value function by iteratively regressing Bellman targets onto a function class. However, theoretical guarantees for FQE generally require Bellman completeness (the Bellman image of any function in the class must lie within the class) or stability of the projected Bellman operator. Without these, the composition of the Bellman operator and the projection (under the offline distribution) may not be contractive, leading to instability.
Ratio-based methods (e.g., Primal-Dual, Minimax): These estimate the occupancy ratio $\omega_{\pi,\gamma} = d d_{\pi,\gamma} / d\nu$ by enforcing balance moments over a critic class. These approaches typically require dual realizability or adjoint Bellman completeness (the critic class must be rich enough to detect residuals generated by the ratio class), shifting the approximation burden to a coupled pair of classes.

The paper addresses the gap where neither value-function completeness nor dual completeness holds, yet the target occupancy ratio itself is well-approximated by a hypothesis class.

Methodology: Fitted Occupancy-Ratio Evaluation (FORE)

The authors propose Fitted Occupancy-Ratio Evaluation (FORE), a fitted fixed-point method that estimates the discounted occupancy ratio through an adjoint Bellman recursion.

Core Mechanism

Adjoint Bellman Identification: The discounted occupancy ratio satisfies the fixed-point equation $\omega_{\pi,\gamma} = B^\pi_\gamma \omega_{\pi,\gamma}$ , where $B^\pi_\gamma$ is the adjoint Bellman operator. Unlike standard Bellman operators, $B^\pi_\gamma$ acts on densities.
KL-Projected Iteration: Instead of solving a minimax saddle-point problem, FORE iterates the adjoint Bellman map. At each step $k$ , given an estimate $\omega^{(k)}$ , the method computes the next estimate $\omega^{(k+1)}$ by projecting the exact Bellman image $B^\pi_\gamma \omega^{(k)}$ onto a hypothesis class $\mathcal{W}$ (of normalized log-ratios) using Kullback–Leibler (KL) divergence:
$\omega^{(k+1)} = \Pi^{\text{KL}}_{\mathcal{W}} (B^\pi_\gamma \omega^{(k)})$
Single-Level Objective: Crucially, the KL projection of the adjoint Bellman image can be computed via a single-level density-ratio objective (Lemma 3.2). This avoids the need for a separate critic class. The objective involves:
- The initial state moment $E_{d_0}[h(X)]$ .
- The one-step transition moment $E_\nu[\omega(X)h(X^+)]$ .
- A log-partition normalization term.
  This allows implementation using standard supervised learners (e.g., gradient-boosted trees, neural networks).

Theoretical Foundation

The stability of FORE relies on the geometry of KL divergence:

KL Contraction: The unprojected adjoint Bellman operator is a contraction in relative entropy (KL divergence) with factor $\gamma$ (Lemma 3.1).
Compatible Projection: Because the projection is performed in the same KL geometry, the projected operator inherits this contraction property.
Approximation Condition: The central requirement is merely the realizability (or approximation) of the target discounted occupancy ratio by the hypothesis class. The method does not require the class to be closed under the adjoint Bellman operator (i.e., no adjoint Bellman completeness is needed).

Handling Limited Coverage

When the target policy visits state-action pairs not supported by the offline data (violating absolute continuity), the full ratio is not identifiable. The authors introduce Coverage-Stopped FORE:

It targets the discounted occupancy accumulated before the first uncovered state-action pair.
It employs a learned coverage classifier to identify and discard the singular component of the Bellman update.
It uses clipping to regularize estimation in weakly covered regions.
The resulting value estimate serves as a conservative lower bound on the true target policy value for non-negative rewards.

Key Contributions

Algorithmic Formulation: Characterization of the discounted occupancy ratio as the unique fixed point of an adjoint Bellman recursion and the introduction of FORE, which estimates this via repeated single-level KL density-ratio objectives.
Population Theory: Development of an approximation theory based directly on occupancy-ratio realizability. The KL-projected adjoint Bellman operator contracts in relative entropy toward the true ratio, up to an approximation error determined by the log-ratio class, without requiring adjoint Bellman completeness.
Finite-Sample Guarantees: Proof of finite-sample regret bounds for the empirical fitted recursion. The generalized KL error decomposes into a geometrically decaying initialization term, a population KL approximation term, and a statistical term governed by the local Rademacher complexity of the log-ratio and induced multiplier classes.
Policy Evaluation Applications:
- Reward Reweighting: Direct value estimation using the fitted ratio.
- Doubly Robust Estimation: A product-form error bound combining the fitted ratio with a fitted Q-function.
- FORE-Weighted FQE: Using the fitted ratio as a projection weight in FQE to stabilize the Bellman recursion without Bellman completeness assumptions on the value class.
Coverage-Stopped Extension: An extension to limited-coverage settings that yields conservative lower bounds and diagnoses effective coverage.

Results

Theoretical Results

Convergence: Under realizability of the occupancy ratio, the population recursion converges geometrically in KL divergence.
Error Bounds: The finite-sample error bound scales with the approximation error of the ratio class and the statistical complexity (critical radius) of the hypothesis class. Notably, the approximation error term scales as $\sqrt{\epsilon_{KL}/(1-\gamma)}$ , which is more favorable than the $(1-\gamma)^{-1}$ scaling often seen in value-function bounds under approximate Bellman completeness.
Stability: The method stabilizes FQE when used as a weighting mechanism, even if the value function class is not Bellman complete.

Numerical Experiments

The paper validates the theory through three experiments:

Baird-style Finite MRP: Demonstrates that linear FQE can be unstable (expansive) under the offline data distribution, while FORE remains stable and converges to the true ratio. FORE-reweighted FQE also stabilizes the value estimation.
Linear-Gaussian Policy Evaluation: In a continuous setting where the value class is not Bellman complete, linear FQE fails (multiplier > 1). FORE converges rapidly (multiplier $\approx 0.086$ ), and FORE-reweighted FQE restores contraction. FORE achieves lower density-ratio error and competitive value RMSE compared to minimax methods (MWL, DualDICE).
Coverage-Stopped FORE: Under insufficient data coverage, standard FORE and post-hoc clipping fail to target the correct sub-probability measure. Coverage-stopped FORE successfully recovers the coverage-stopped occupancy ratio and provides accurate lower bounds on the value, outperforming baselines in both ratio and value error.

Significance and Claims

The paper claims to identify discounted occupancy-ratio realizability as a sufficient condition for offline policy evaluation, removing the need for:

Bellman completeness of a value class.
Adjoint Bellman completeness of a ratio class.
Dual completeness of a critic class.

The significance lies in shifting the approximation burden from complex closure conditions (which are often restrictive and hard to verify) to the direct representability of the distribution shift itself. By leveraging the KL geometry, FORE achieves stability and convergence guarantees that are structurally distinct from and often weaker than the assumptions required by FQE or minimax methods. The authors position this as a fundamental alternative to value-based and minimax ratio-based approaches, particularly in settings where the occupancy ratio is well-approximated but the value function or critic classes lack the necessary completeness properties.

The paper remains modest regarding limitations: full-ratio recovery still requires coverage (absolute continuity), and in high-dimensional or near-deterministic settings, estimating the ratio may be as difficult as estimating the value function. The coverage-stopped extension addresses this by changing the estimand to a conservative lower bound rather than extrapolating into unsupported regions.