Efficient Offline Policy Optimization under All-Policy Linear Q-Realizability

Abstract

We study offline policy optimization in finite-horizon Markov decision processes with a finite action set and a known bounded feature map. We assume that the action-value function of every randomized memoryless policy is exactly linear, with coefficient norm at most B, and that the state-action occupancy measure of every such policy is dominated by C times the occupancy measure of a single unknown memoryless behavior policy. Given independent complete trajectories from this behavior policy, we construct an explicit algorithm that returns an epsilon-optimal deterministic memoryless policy with high probability. Its trajectory complexity and exact-real arithmetic complexity are polynomial in the horizon, feature dimension, number of actions, C, B, inverse accuracy, and logarithmic inverse failure probability. The algorithm alternates convex regression with validation and the growth of a list of certified policy directions. Certified action gaps yield exact linear representations of stopped targets; a single continuation-policy error expansion avoids repeated concentrability factors; and a log-determinant potential bounds the number of unsuccessful rounds. No behavior probabilities or policy-optimization oracle are required. The complexity depends polynomially on B, not merely on its bit length, and the result requires exact realizability and all-policy state-action coverage.