cs.LGNov 8, 2026

Computationally Efficient Offline Policy Optimization with All-Policy Linear Realizability

Authors: Zhijie Zheng

Organizations: Peking University

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 BB. From independent complete trajectories of one unknown Markov behavior policy, and under all-policy occupancy coverage, we give an algorithm with O~(ε−2)\widetilde O(\varepsilon^{-2}) sample dependence and computational complexity polynomial in log⁡(2+B)\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−2B^{-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 BB. A two-action lower bound shows that the accuracy exponent 22 is necessary.

Explore similar work

CardsList
  1. Frozen Policy Iteration: Computationally Efficient RL under Linear QπQ^π Realizability for Deterministic Dynamics

    Feb 28, 2026Yijing Ke, Zihan Zhang, Ruosong WangRegret Minimization in RLPolicy Iteration

  2. Optimistic Actor-Critic with Parametric Policies for Linear Markov Decision Processes

    Mar 30, 2026Max Qiushi Lin, Reza Asad, Kevin Tan +3Actor-Critic MethodsPolicy Learning