# Frozen Policy Iteration: Computationally Efficient RL under Linear Qπ Realizability for Deterministic Dynamics

arXiv: https://arxiv.org/abs/2603.00716 · HTML: https://mlsanity.com/paper/2603.00716/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 20 of its 37 references that are in the map.
- First posted on arXiv 28 Feb 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 20 of 20)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration](https://mlsanity.com/paper/2008.07737/) (2020)
- [Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)
- [Efficient Local Planning with Linear Function Approximation](https://mlsanity.com/paper/2108.05533/) (2021)
- [Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity](https://mlsanity.com/paper/2002.07125/) (2020)
- [Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.11612/) (2021)
- [Confident Approximate Policy Iteration for Efficient Local Planning in qπ-realizable MDPs](https://mlsanity.com/paper/2210.15755/) (2022)
- [Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics](https://mlsanity.com/paper/2406.11810/) (2024)
- [Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions](https://mlsanity.com/paper/2406.11640/) (2024)
- [Uniform-PAC Guarantees for Model-Based RL with Bounded Eluder Dimension](https://mlsanity.com/paper/2305.08350/) (2023)
- [Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions](https://mlsanity.com/paper/2409.04840/) (2024)

## Abstract (arXiv)

We study computationally and statistically efficient reinforcement learning under the linear Qπ realizability assumption, where any policy's Q-function is linear in a given state-action feature representation. Prior methods in this setting are either computationally intractable, or require (local) access to a simulator. In this paper, we propose a computationally efficient online RL algorithm, named Frozen Policy Iteration, under the linear Qπ realizability setting that works for Markov Decision Processes (MDPs) with stochastic initial states, stochastic rewards and deterministic transitions. Our algorithm achieves a regret bound of widetildeO(√d2H6T), where d is the dimensionality of the feature space, H is the horizon length, and T is the total number of episodes. Our regret bound is optimal for linear (contextual) bandits which is a special case of our setting with H = 1. Existing policy iteration algorithms under the same setting heavily rely on repeatedly sampling the same state by access to the simulator, which is not implementable in the online setting with stochastic initial states studied in this paper. In contrast, our new algorithm circumvents this limitation by strategically using only high-confidence part of the trajectory data and freezing the policy for well-explored states, which ensures that all data used by our algorithm remains effectively on-policy during the whole course of learning. We further demonstrate the versatility of our approach by extending it to the Uniform-PAC setting and to function classes with bounded eluder dimension.