Computationally Efficient Offline Policy Optimization with All-Policy Linear Realizability

Zhijie ZhengarXiv 2026 · arXiv

This paper, recently published on arXiv, tackles a fundamental challenge in Reinforcement Learning (RL): how to learn an optimal policy from a fixed "offline" dataset without needing to interact with the environment, and doing so in a way that is both statistically and computationally efficient.

TL;DR

The authors present a new algorithm for offline policy optimization that achieves the optimal $\widetilde{O}(\varepsilon^{-2})$ sample complexity while remaining computationally efficient, even when the parameter space is massive. By using a "witness policy" approach and a shared reference design, they bypass the need for the restrictive "Bellman completeness" assumption, requiring only that every policy's value function is linear in known features.

What Problem Does This Paper Address?

Offline RL is the "Holy Grail" for applications like healthcare or autonomous driving, where collecting new data is expensive or dangerous. We want to take a log of past actions and outcomes and find a better strategy.

Most efficient algorithms rely on Bellman Completeness—the idea that if you take a linear function and apply a Bellman backup (a standard RL update), the result is still a linear function. However, in the real world, this rarely holds. A much more realistic (but harder to work with) assumption is All-Policy Linear Realizability: simply assuming that for every policy, there exists a linear representation of its value function.

The problem? Under this weaker assumption, standard "Fitted Value Iteration" fails because the regression targets might not be representable by your model. Previous attempts to solve this were either statistically inefficient or computationally "explosive," especially when the norm of the linear coefficients ($B$) was large.

Methods

The authors introduce an algorithm that performs exactly one convex regression per layer of the MDP (working backward from the horizon). Key technical innovations include:

  1. Stopped-Return Targets: Instead of trying to approximate the optimal value function directly, the algorithm uses "stopped returns." If the uncertainty at a state is too high, it "stops" and uses a pessimistic value. If uncertainty is low, it "continues" along the behavior policy's path. This creates a consistent "witness policy" that justifies the value estimates.
  2. Shared Reference Design: The algorithm uses a portion of the data to build a fixed "confidence geometry" (ellipsoidal bounds). This geometry is reused across all layers, which prevents errors from compounding exponentially.
  3. Logarithmic Complexity in $B$: Most algorithms scale poorly as the parameter bound $B$ grows. This paper uses bounded prediction constraints and "truncated leverage" to ensure the computational cost only grows with $\log(B)$.
  4. Finite-Bit Implementation: Unlike many theoretical papers that assume infinite-precision "real-arithmetic," the authors provide a version of the algorithm that works with rational numbers and finite bits, proving it can actually run on a standard computer in polynomial time.

Datasets

This is a theoretical paper focused on algorithmic guarantees and complexity bounds. It does not evaluate on standard benchmarks like D4RL. However, the authors include a synthetic two-action MDP to prove a lower bound, demonstrating that any learner in this setting must use at least $\Omega(\varepsilon^{-2})$ samples to reach an $\varepsilon$-optimal policy.

Key Insights and Ideas

  • The Witness Policy "Aha" Moment: You don't need to find the optimal policy in one giant leap. You just need to find a policy that is "consistent" with your data. By constructing a "witness" policy that follows the behavior policy unless it finds a clearly better, certain action, the authors ensure the regression targets always stay within the linear class.
  • Pessimism via Uncertainty: The algorithm uses a "pessimistic query." When the range of possible values for actions is much larger than the uncertainty, it picks a value that is guaranteed to be achievable by a mixture of real actions.
  • Efficiency is Possible: The paper proves that "All-Policy Realizability" is not just a theoretical curiosity but a practical foundation for offline RL, provided you use the right geometric constraints.

Key Results

  • Sample Complexity: The algorithm requires $\widetilde{O}(\varepsilon^{-2})$ trajectories, which matches the theoretical lower bound for accuracy.
  • Computational Complexity: The runtime is polynomial in the horizon ($H$), feature dimension ($d$), coverage constant ($C$), and—crucially—the logarithm of the coefficient bound ($\log B$).
  • Coverage Flexibility: The guarantees hold under "all-policy occupancy coverage," and the authors provide a variant that works under the even weaker "covariance coverage" (though with polynomial rather than logarithmic dependence on $B$).

Limitations and Future Work

  • Parameter Dependence: While the dependence on $B$ is logarithmic, the dependence on the horizon ($H$), dimension ($d$), and coverage ($C$) is polynomial and likely not yet optimal.
  • Pointwise Realizability: The paper assumes realizability holds for every state-action pair. Relaxing this to "average-case" realizability (where the model only needs to be good on average) remains an open challenge.
  • Covariance Coverage Gap: The authors note that it is currently unknown if logarithmic dependence on $B$ can be achieved under the weaker "covariance coverage" and "approximate realizability" settings.

Summary updated

Abstract

We study offline policy optimization in finite-horizon Markov decision processes where every deterministic Markov policy has an action-value function linear in known features, with coefficient norm at most $B$. From independent complete trajectories of one unknown Markov behavior policy, and under all-policy occupancy coverage, we give an algorithm with $\widetilde O(\varepsilon^{-2})$ sample dependence and computational complexity polynomial in $\log(2+B)$. The algorithm performs exactly one convex regression per layer. Its stopped-return targets are the values of a single consistent Markov witness policy. A shared reference design and bounded prediction constraints convert fast clipped-regression error into pointwise confidence for the raw linear predictions. Truncated leverage controls the performance loss without requiring empirical covariance approximation at scale $B^{-2}$. Rounding confidence radii upward preserves the exact witness and yields a polynomial-time bit implementation for rational numerical inputs. The guarantees allow any fixed initial-state distribution; realizability and coverage need only be checked for deterministic policies. We also establish a covariance-coverage variant with uniform approximate realizability and polynomial dependence on $B$. A two-action lower bound shows that the accuracy exponent $2$ is necessary.
BibTeX
@misc{zheng2026computationally,
  author = {Zhijie Zheng},
  title = {{Computationally Efficient Offline Policy Optimization with All-Policy Linear Realizability}},
  year = {2026},
  eprint = {2611.11423},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.11423},
}
Figure