Offline policy optimization under all-policy linear realizability
Original title: Computationally Efficient Offline Policy Optimization with All-Policy Linear Realizability
The method uses one convex regression per layer and has sample dependence of order epsilon to the minus two.
The paper studies offline policy optimization in finite-horizon Markov decision processes when every deterministic Markov policy has a linear action-value function. From trajectories of one unknown behavior policy, the algorithm has tilde-O of epsilon to the minus two sample dependence and complexity polynomial in log of 2 plus B. A two-action lower bound shows the accuracy exponent 2 is necessary.
- The algorithm performs exactly one convex regression per layer.
- Guarantees allow any fixed initial-state distribution.
- A covariance-coverage variant has polynomial dependence on B.
- Rounding confidence radii upward preserves the exact witness.
From the original article
1 min read at arxiv.orgWe 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$.
By Zhijie Zheng · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.