Computationally Efficient Offline Policy Optimization with All-Policy Linear Realizability
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 . From independent complete trajectories of one unknown Markov behavior policy, and under all-policy occupancy coverage, we give an algorithm with sample dependence and computational complexity polynomial in . 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 . 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 . A two-action lower bound shows that the accuracy exponent is necessary.
Offline RL
Offline reinforcement learning learns decision-making policies from fixed datasets without interacting with the environment during training.
See all 327 papers