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

Yijing Ke; Zihan Zhang; Ruosong Wang

cs.LGFeb 28, 2026

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

Authors: Yijing Ke, Zihan Zhang, Ruosong Wang

Organizations: School of EECS, Peking University · Department of Computer Science and Engineering, HKUST · CFCS and School of Computer Science, Peking University

Abstract

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 $\widetilde{O}(\sqrt{d^2H^6T})$ , 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.

Figures & tables

	Access model	Stochastic transitions	PAC guarantee	Regret guarantee
Du et al. (2019a)	generative model	$\checkmark$	$\checkmark$	$\times$
Lattimore et al. (2020)	generative model	$\checkmark$	$\checkmark$	$\times$
Yin et al. (2022)	local access	$\checkmark$	$\checkmark$	$\times$
Weisz et al. (2022)	local access	$\checkmark$	$\checkmark$	$\times$
Weisz et al. (2023)	online RL (computationally intractable)	$\checkmark$	$\checkmark$	$\times$
This work	online RL	$\times$	$\checkmark$	$\checkmark$

Table 1: Comparison with prior works.

Panel of Figure 1 — Figure 1: An example of MDP satisfying linear $Q^{\pi}$ realizability, where $\phi(s_{1},a_{1})=\phi(s_{1},a_{2})=e_{1}$ , $\phi(s_{2},a_{3})=e_{2}$ , $\phi(s_{3},a_{3})=e_{3}$ .

\pi_{t}(s)=\begin{cases}\mathop{\arg\max}_{a\in\mathcal{A}}Q_{t}(s,a)&\left(s,a\right)\in\operatorname{Cover}\left(\mathcal{D}_{t,h},\varepsilon\right)\text{ for all }a\in\mathcal{A}\\ \text{any

a\in\mathcal{A}

such that

(s,a)\notin\operatorname{Cover}\left(\mathcal{D}_{t,h},\varepsilon\right)

}&\text{otherwise}\end{cases},

Algorithm 1 Frozen Policy Iteration-PAC (FPI-PAC)

Panel of Figure 2 — Figure 2: Learning curves on CartPole-v1 and InvertedPendulum-v4. Results are averaged over 5 seeds. The shaded area captures a 95% confidence interval around the average performance.

Regret Minimization in RL

Regret minimization in reinforcement learning develops agents that learn effective policies while limiting cumulative loss against an optimal benchmark.

See all 59 papers

Mar 24, 2026

End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions

We study reinforcement learning (RL) with linear function approximation in Markov Decision Processes (MDPs) satisfying linear Bellman completeness -- a fundamental setting where the Bellman backup of any linear value function remains linear. While statistically tractable, prior computationally efficient algorithms are either limited to small action spaces or require strong oracle assumptions over the feature space. We provide a computationally efficient algorithm for linear Bellman complete MDPs with deterministic transitions, stochastic initial states, and stochastic rewards. For finite action spaces, our algorithm is end-to-end efficient; for large or infinite action spaces, we require only a standard argmax oracle over actions. Our algorithm learns an

\varepsilon

-optimal policy with sample and computational complexity polynomial in the horizon, feature dimension, and

1/\varepsilon

Zakaria Mhammedi, Alexander Rakhlin, Nneka Okolo

Google Research, NYC · MIT

Reinforcement Learning Linear Markov Decision Processes Policy Learning Sample-Efficient RL Function Approximation in RL

Ask PDF

May 27, 2026

Commit to the Bit: Reactive Reinforcement Learning Done Right

Reinforcement learning algorithms are commonly analyzed (and designed) under the Markov assumption. This is unrealistic, as most environments encountered in practice are either partially observable, or require function approximation that restricts the agent to access non-Markovian state features. We consider the problem of learning an optimal reactive policy in a finite environment with deterministic observations (or equivalently, hard state aggregation). We introduce a new algorithm, Committed Q-learning, and prove almost-sure convergence to the optimal reactive policy under an intuitive assumption we call rewire-robustness. This assumption is strictly weaker than the

q_\star

-realizability condition used in prior work. Our algorithm is a variant of classical Q-learning in which the behavior policy commits to a single action upon entering a feature, and only resamples actions when the observed feature changes. A crucial part of our analysis is the introduction of quasi-Markov environments.

Onno Eberhard, Claire Vernade, Michael Muehlebach

Max Planck Institute for Intelligent Systems, Tübingen, Germany · University of Tübingen · University of Technology Nuremberg.

Reinforcement Learning Partially Observable RL Q-Learning Policy Learning Non-Markovian RL

Ask PDF

Aug 23, 2026

Q-Learning with Stable Infinite-Dimensional Linear Function Approximation

Q-learning with linear function approximation can be unstable because an arbitrary approximation architecture need not preserve the Bellman contraction. We develop a stable infinite-dimensional linear function approximation framework for Q-learning from a single Markovian behavior-policy trajectory. The learning variable is a coefficient field

θ\in C(\mathbb L)

on a compact latent metric space

(\mathbb L,ρ)

. The framework uses a reconstruction operator that maps

θ

to a continuous Q-function and a compression operator that maps Bellman updates back to latent coordinates. Nonexpansiveness of both operators induces a contractive latent Bellman map on

C(\mathbb L)

, with a unique fixed point

θ^*

whose reconstruction approximates the optimal Q-function up to representation error. We propose two stochastic approximation (SA) algorithms and establish their sup-norm convergence bounds with a leading term of order

\widetilde O(n^{-1/2})

. The infinite-dimensional formulation provides a powerful abstraction for identifying the structures that govern statistical difficulty. Smoothness of the compression map in

ρ

is inherited by

θ^*

and the SA iterates, allowing uniform estimation errors to be controlled through covering numbers of

(\mathbb L,ρ)

rather than the dimension of

C(\mathbb L)

. Remarkably, the SA algorithms we propose are agnostic to the choice of

ρ

, and thus can automatically adapt to both the smoothness and the geometry. We further illustrate the framework through Q-measure-learning with linear density approximation and output-layer neural weight training under a frozen pretrained network.

Shengbo Wang

Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California

Q-Learning Function Approximation in RL Linear Function Approximation Stochastic Approximation

Ask PDF

Abstract

Regret Minimization in RL

Explore similar work

End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions

Commit to the Bit: Reactive Reinforcement Learning Done Right

Q-Learning with Stable Infinite-Dimensional Linear Function Approximation