Frozen Policy Iteration: Computationally Efficient RL under Linear $Q^{\pi}$ Realizability for Deterministic Dynamics
Authors: Yijing Ke
Zihan Zhang
Ruosong Wang
Venue: ICLR 2026 Poster (2026)
Keywords: Theory of Reinforcement Learning
Policy Iteration
Linear Function Approximation
Primary area: learning theory

Abstract: We study computationally and statistically efficient reinforcement learning under the linear $Q^{\pi}$ 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^{\pi}$ 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.

Published as a conference paper at ICLR 2026
FROZEN POLICY ITERATION: COMPUTATIONALLY EF- FICIENT RL UNDER LINEAR Q" REALIZABILITY FOR DETERMINISTIC DYNAMICS
Yijing Ke', Zihan Zhang", Ruosong Wang
"chooo of EECS, Peking University
*Department of Computer Science and Engineering, HKUST CFCC and School of Computer Science, Peking University keyi jinge pku. edu.
zihanzêcse, ust. .k
ruosongwanggsku. edu.
ABSTRACT
We study computationally and statistically efficient reinforcement learning under the linear Q" realizability assumption, where any policy's Q-function is linear in given state-action feature representation. Prior methods in this setting are either computationally intractable, or require (local) access to a simulator, In this paper, propose 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 regret bound of 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 optimal for linear (contextual) bandits which is special case of our setting with H =
Existing policy iteration algorithms under the same setting heavily rely on re- peatedly sampling the same state by access to the simulator, which is not imple- mentable 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 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 ef- fectively on-policy during the whole course of learning. We further demonstrate the versatility of our approach by extending it to the Uniform-PAr setting and to function classes with bounded eluder dimension.
INTRODUCTION
In modern reinforcement learning (RL), function approximation schemes are often employed to handle large state spaces. During the past decade, significant progress has been made towards un- derstanding the theoretical foundation of RL with function approximation. By now, a rich set of tools and techniques have been developed (Jiang al. 2017 Sun et al. 2019; Jin al. 2020 Wang et al. 2020 Du et al. 2021; Jin et al. 3021;Fostte et al. 2021), which have led to statistically efficient RL with function approximation under various structural assumptions. However, despite these advancements, a remaining challenge is that many of these statistically efficient RI. algorithms are computationally inefficient, which severely limits the practical applicability of these approaches. Recently, these peapputttiioallstatttiini
gaps have drawn significant interest from the RL theory community, leading to computationally efficient algorithms (Zanette et al.) 2020b Wu et al. 2024 Golowich & Moitra 2024) and computational hardness results (Kane al. 2022).
For the special case of RL with linear function approximation, a structural assumption common in the literature is the linear bellman completeness assumption (Zanette et al.) 2020a b Wu et al.
2024 Golowich & Moitra 2024). which, roughly speaking, assumes that the Bellman backups of linear state-action value functions are still linear w.r.t. fixed feature representation given to the

---

Published as a conference paper at ICLR 2026
learner. This assumption naturally arises when analyzing value- salue-iteration type RL algorithms (e.g., FQI (Munos] 2005)) with linear function approximation. It is by now well-understood that RL with linear bellman completeness is statistically tractable (Zanette et al. 2020a Du al. 202T Jin al.) 2021), in the sense that a near-optimal policy can be learned with polynomial sample complex- ity. However, the algorithm employed to achieve such polynomial sample complexity require solv- ing computationally intractable optimization problems, and recently a number of algorithms have been proposed to fill this computationallstatisiici
gap, leading to statistically and computation- ally efficient RL under linear bellman completeness for MDPs satisfying the explorability assump- tion (Zanette et al.] 2020b), MDPs with deterministic dynamics, stochastic rewards and stochastic initial states (Wu et al. 2024), and MDPs with constant number of actions (Golowich & Moitral 2024].
A major drawback of the linear bellman completeness assumption, as observed by Chen & Jiang (2019), is that it not monotone the function class under consideration. For the linear function case, adding more features into the feature representation may break the assumption. This makes the bellman completeness much less desirable for practical scenarios, as in modern RL applications, neural networks with billions of parameters employed as the function approximators, and feature selection could be intractable in such cases.
For RL with linear function approximation, another common assumption is the linear Q realiz- ability (Du et al., 2019a Lattimore et al. 2020; Yin et al. 2022 Weisz et al.] 2022 2023). which assumes that any policy's Q-function is linear in fixed state-action feature representation given to the learner. This assumption naturally arises when analyzing policy-iteration type RL algorithms (e.g.. LSPI (Lagoudakis & Parr 2 with linear function approximation, and it has the desired monotonicity property, in the sense that adding more features never hurts realizability. However, unlike linear bellman completeness, the computational statissiil gap under linear Q" realizability is largely unexplored. Under this assumption, the first method with polynomial sample complexity due to Weisz et al. (2023), and similar to linear bellman completeness, existing algorithms (Weisz et al., 2023] Mhammedi] 2025) with such sample complexity requires either computationally in- tractable optimization problems or oracles. Other algorithms (Du et al. 2019a Lattimore et al.) 2020 Yin et al.) 2022, Weisz et al. 2022) with polynomial running time further require (local) ac- cess to a simulator, which enables the algorithm to restart from any visited states. In contrast, in the standard online RL setting, there is no known RL algorithm that is both statistically and computa- tionally efficient. In fact, under the linear Q' realizabilityy, even when the transition dynamics are deterministic, it unclear if computationally efficient RL possible.
In terms of methodology, the algorithm by Weisz et al. (2023) employs the global optimism ap- proach and relies on maintaining large and complex version spaces. It is unclear how implement such approach in a computationally efficient manner, and obtaining an algorithm with polynomial running time under linear Q" realizability was left as an open problem by WWisz et al. (2023). Mhammedi] (2025 achieves sample and oracle efficient under linear Q" realizability by relying on a cost-sensitive classification oracle. However, such oracle could be NP-hard to implement in the worst case. Meanwhile, the algorithms by Yin et al. (2022); Weisz et al. (2022) employ the standard approximate policy-iteration framework and assume local access to a simulator. these algorithms, before adding state-action pair (s, a) into the dataset, the algorithms use multiple rollouts start- ing from (s, a) to ensure all successor states are well-explored, so that the policy value associated with (s, a) is accurate. Once a new under-cxplored state appears, the whole algorithm restarts from that state and perform additional rollouts to make it well-explored. Consequently, these algorithms critically rely the simulator to revisit the same state for multiple times. However, such resam- pling mechanism is not implementable in the standard online RL setting when the state-space is large. Even with deterministic dynamics, long as the initial state is stochastic, we might not even encounter the same state twice during the whole learning process.
In this paper, we provide the first computationally efficient algorithm under the linear QT realizabil- ity assumption with stochastic initial states, stochastic rewards and deterministic dynamics in the online RL setting. Our algorithm, named Frozen Policy Iteration (FPI), achieves a regret bound of O(VTHHTTY where d is the dimensionality of the feature space, is the horizon length, and T is the total number of episodes. which is optimal for linear (contextual) bandits (Dani et al.] 2008),
a special case with H = 1. Unlike existing policy iteration algorithms (Du et al. 2019a Lattimore
Throughout the paper, we use Õ()tto suppress logarithm factors.
2

---

Published as a conference paper at ICLR 2026
et al. 2020: Yin et al. 2022 Weisz et al. 2022), our new algorithm circumvents the resampling issue 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 the Uniform-PAC setting (Dann et al.] 2017) and to function classes with bounded eluder dimension (Russo & Van Roy| (201)). Due to the simplicity of our algorithm, we are able give a proof-of-concept implementation on standard control tasks illustrate practicality and to ablate the role of freezing.
2 RELATED WORK
Linear Q Realizabillty. The connection and difference between our work and prior work under Linear Q" Realizability (Du et al., 2019a Lattimore et al. 2020 Yin et 2022 Weisz et al. 2022 2023) have already been discussed in the introduction. In Table we compare our new result with prior works to make the difference clear. We also note that the algorithms by Lattimore et al. (2020);
Yin et al. (2022); Weisz et al. (2022) work in the discounted setting, while our new algorithm and the algorithm by Du et al. (20 20); Weisz et al. (2023) work under the finite-horizon setting.
Linear Q" Realizability. The Linear Q" Realizability assumes that the optimal Q-function is linear in given state-action feature representation. Since Linear Q Realizability implies Lin- car Q* Realizability, algorithms under Linear Q² Realizability could also be relevant to our setting. However, existing algorithms that work under this assumption either require lower bounded subopti- mality gap and deterministic dynamics with deterministic initial states (Du et al. 2019b 2020), fully deterministic system (i.e., deterministic rewards and initial states) (Wen & Van Roy, 2013), or lower bounded suboptimality gap with local access to a simulator (Li et al. 2021). All these assumptions much stronger than those assumed by prior algorithms under Linear Q" Realizability.
Uniform-PAC. Dann et al. (0117) propose the Uniform-PAS PAC setting as a bridge between the PAC setting and the regret minimization setting, and develop the first tabular RL algorithm with Uniform-PAC guarantees. Uniform-PAr PAC guarantees are also achieved for RL with function approx- imation (He et al., [022] Wu al., 2023). To achieve the Uniform-Pae racy level framework similar to that of He et al. (2021). though the details are substantially different since our algorithm based on policy-iteration, while their algorithm is based on value-iteration.
guarantee, we use an accu-
Stochastic transitions
PAC guarantee
Regret guarantee
Access model
Du et al. (2019a)
generative model
X
Lattimore et al. (2020)
generative model
Yin al. (2022)
local access
Weisz et al. (2022)
local access
X
online RL
Weisz et al. (023)
(computationally
intractable) online RL
This work
Table 1: Comparison with prior works.
3 PRELIMINARIES
A finite-horizon Markov Decision Process (MDP) is defined by the tuple (S, P.R.R. H E N+ is the horizon. = S U... U SH is the state space, partitioned by the horizon H, with Sā denoting the set of states at stage h E [ = {1.... ... H. J. We assume that Si, SH are disjoint sets. AA is the action space. :: S₁, x A + A(Sa+1) is the transition function, where A(S denotes the set of probability distributions over Sh+1- R S A + A( 1)) is the reward distribution, where R(s, a) is a distribution on [0, 1] with mean r(s, a), indicating the stochastic reward received by taking action a on state s. fa A(Si) is the probability distribution of the initial
3

---

Published as a conference paper at ICLR 2026
state. Given policy π S + A. for each E Sp and E A, define the state-action value function of policy π as (= a) E E
ab - a, and the state value function as (s)) = Q" (ss Let n the optimal policy. For an RL algorithm, define its regret in the first T episodes as the sum of the suboptimal- ity gap of the first T trajectories, Reg(T)) - E (V" ) E r(s) ) where
(t) ,.... 1 (1)) ................................ ,8
ag is the trajectory in the t-th episode.
Let V Rdddd symmetric positive definite. For any æ Rd define the elliptical norm induced
by V as | = vx Vx. Vv. zero-mean random variable X is called o-subGaassian if E [eax] s x200//2 for all X E IR.
In this work, we assume the Linear Q" Realizability assumption, formally stated below.
Assumption (Linear Q" Realizability), MDP (S,A, H, P. R. μ) is k-approximate Q realizable with a feature map & : SS x A + R for some K > 0. That is, for any policy т, there exists 87. 0 Rd such that for any h [H).s E S₁, and A, 1Q" (s, (,(s,)),05) a),0%1 S K.
We assume that the feature map ø is given learner. Since (=(ssa) E [0, H], we also make the following assumption, which ensures that Φ(s, a) and 0% have bounded norm for all (s,a) E E x A and h E [H]
Assumption 2 (Boundedness), For any h E [M] |0((, s for all s E Sn, E A and |10%11, & vdH for any policy x.
We further require deterministic state transition.
Assumption 3 (Deterministic Transitions). For any E and a A, P(s,a) a) is a one-point distribution, i.e., the system transitions to unique state after taking action on state
0.1
82
0.9
03
a1
84
a2
03
0.2
0.8
Figure 1: An example of MDP satisfying linear Q" realizability, where (1),a))= = 0(81, a2) e1. ((82, ag) 62, (5(3, 03) e3-
We note that linear Q" realizability does not imply linear bellman completeness even in MDPs with deterministic transitions. Figure [ssuur shows an example satisfying linear Q" realizability which is not linear bellman complete. Moreover, although we assume the transition be deterministic, the initial state distribution is stochastic (in fact, our algorithm allows for adversarially chosen initial states), and the reward signal could be stochastic. Therefore, learning is still challenging this case. Also, stochastic initial state could in fact cover number of standard RL benchmarks including classical control tasks (e.g., CartPole, Acrobot) (Towers et al. 2024) and MuloCo Environments (Todorov et al.) (012), where randomness primarily arises from the reset distribution rather than process noise. For Atari Games, when sticky actions are disabled, the simulator yields deterministic dynamics; stochasticity is typically injected only at reset.
4 WARMUP: FROZEN POLICY ITERATION IN THE PAC SETTING
In this section, we present the probably approximately correct (PAC) version of our main algorithm, which serves warmup of the more complicated regret minimization algorithm in Section 5
4.1 THE ALGORITHM
In our algorithm, for each step E [H], we maintain dataset Dj, which is an ordered sequence consisting of (8h,2, in (n,i), where (n..) S₁ A is state-action pair, and
Datasets.
4

---

Published as a conference paper at ICLR 2026
Algorithm Frozen Policy lteration-PAC (FPI-PAC)
1: Initialize 1I, = {} for all h E [M]
2: for t t,..... .T' do
3: For each E [H] and & E Sh. define
TT. (s) arg aa Qe(s,a)
(s,a) a) E Cover (Dt,,, for all E A
anny a A such that (s, Cover (Dr, otherwise
where Cover (Dr., 5) as defined in ① and Qr(8, a) is as defined in 3
4: Receiving 51 di .1 52 02 ...., a H by executing T.
(t) (E) (1)
(2) (2) (e) (t)
5: he f max h E [H] (sh an (ov
(8) (2)
6: if hy exists then
7: q. + --h=hhe (t)
8: Update D1+1,A. Denro U (shh 1 (.)) and D411,6 Di, for any he
9: end if end for
4h.i is total reward obtained by following policy ne starting from (sh, an,s). We further define $1.1 = o ($h,s, ap.s) to be the feature (sh,i: an,a). In the description Algorithm for clarity, we use Dr, denote the snapshot of DD, before the t-th round, and initialize Di, l.e., the dataset before the first round, to be the empty set for all h E [H].
Exploration Mechanism. For each round step [H]. we first test if for all actions a E A. (s, a) could be covered by existing data in Dr Concretely, for dataset D [(s,, a,, -- define
first define policy Ths where for each state
Cover(D,e) = {(s, a) E x A: [lø(s, a)ll= S se}
(1)
where E = AI E ((s, a, (0(s, a;)T T is the regularized empirical feature covariance matrix. Equivalently, Cover(D, 8) contains state-action pairs (s, a) for which the least squares estimate has error upper bounded by (roughly) s. If for all actions E A. (s, a) lies in Cover(D, eD,)), we define (s) to be the greedy policy with respect to a Q-function Qe (defined later). Otherwise, there must be an action E A satisfying (s, & Cover(D, and define TT(s) to be any such a to encourage exploration. We break tic in a consistent manner when there are multiple such a.
Avoiding Off-Policy Data and Resampling. After defining policy Tr, we execute म, to receive a trajectory sample, forms a new dataset D.+ based on Dr, h. and the collected data, and proceeds to the next round 1. So far, the design of algorithm does not differ significantly from the standard policy iteration framework. Indeed, the main novelty of Algorithm [ lies in how we form the new dataset D++1,k and define Q-function Qc+1 based on D.+1,h- h. If not handled properly, our datasets could contain off-policy data once is updated. In particular, for each data (sh, O,..,, It,i), gt,i might deviate significantly from the Q-value of (sh. (i.;;) once the policy is updated. We note that assuming access to a simulator (Du et al.) (2019a] Lattimore et al.) (0200) Yin et al. [202]] Weisz et al. 2022 2023), one could simply recollect samples by executing the updated policy starting from (8h,, (4,4) estimate its Q-value with respect to the updated policy. Unfortunately. in the online setting with stochastic initial states, such resampling is not implementable as we might not even encounter the same state twice during the whole learning process.
Updating Datasets. In the design of Algorithm I we only include the high-confidence part of the trajectory data into the new datasets. In particular, St Algorithm step h, so that (s) aa))) could be not covered by existing data. We then add (1(t) The ae) into Dr.h, form Di+1,h, where qi is the total reward starting from step ht For all other step h + h4, we keep Dr,, unchanged. This design choice is due to the following reason: for all steps h > h4,
define ht to be last (t)
we must have (s) a) E Cover (Dr,,, e) for all a A, since otherwise an exploratory action would have been chosen (cf. the definition of TT), which further implies that is a near-optimal policy (t)
(t) (1) & Cover (Di, e), ahe could be for hh het22 8/ On the other hand, since (5 ah.)
(t)
5

---

Published as a conference paper at ICLR 2026
suboptimal action for 8h;" Because of this, we only include (oh, ohh) into the new dataset, and discard all other state-action pairs on the trajectory.
(0)
Freezing High-Confidence States. It remains define the Q-function Q. based on the dataset DLA-- Here, naive choice is to use all data in Dr, to obtain least- squtres estimate and define Qr accordingly, but by doing so, eventually our datasets could still contain off-policy data once the (+) policy गi is updated. In particular, although S lies in the high-confidence region coverd by Dr,
for all > h4s the policy on state (t) could still be changed in later rounds once we update mis which means our dataset contains reward sums from different policies. Here, new idea is to freeze the updates on TT(s). once our datasets could cover (s, a) for all a E A. Concretely, for each round for each Sh define
(s) = min { |: E N: (s,0) E Cover ((SSh, Cn,is m.))) for all a E A} A (Paul- (2)
Recall that Dr,A- = {( an,s 3h. |Paal is the snapshot our dataset at step before the t-th round. Essentially, (s)s) is the first time we add a data into Dr, after which (s, a) could be covered by Dr,, for all E A. Therefore, by defining Qs(s,)) using only the first (x))) data Dr, we effectively freeze the updates (s(s) once our datasets could cover (s, a) for all A. Therefore, for each h E [H] and E Sn, we define
Qi(s,a) QK(())(s.a),
(3)
where (s(s) is as defined in and
@x(5, = ((s,a), a), hh,k
the least squares estimate by using only the first data in Dí with
Σn, = Al
o o
(4)
i
4.2 THE ANALYSIS
In this section, we outline the analysis of Algorithm ! In our analysis, define
2d
4- 4=-4
D In
(5)
X2
Our first lemma shows that for any round t and h [H]. [Dr,u] is always upper bounded by D.
Lemma 1. For any t 2 1, E [H). it holds that [Dr,al S D.
The proof Lemma I is based on observation that we add a data (sn,ss Uh, gh.s) into Dz+ in the 1-th round, we must have (8h. ap.;) & Cover(Di,,,e) Therefore, by the standard elliptical potential lemma (Lattimore & Szepesvári 2020 Lemma Tholds.
Our second lemma shows that for state-action pair (Sh,i an added into Dí in the t-th round, the Q-function of (sh,s: an.s) with respect to any later policy ne (i.e., 2 f) will be unchanged.
Lemma 2. For any h [H] and i let be the round when (sh, Ih.s) appended
to Drn iee. (Sh, ah,i, qh.a) E Dit1,6 while (Sh,i, Ch,i, qh.i) & De. Then (**(sh an.s) =
QFu(Sh,s ah,s) for all zt.
The proof of Lemma 2 is based on the following observation: suppose add state-action pair (s) (nh) into the dataset in the 1-th round, for all > h4, we must have (a aa E Cover (Di,a, e) for all a E A, since otherwise an exploratory action with (s .a) & Cover (Dr,n, e) would have been chosen. Therefore, by the way we define Qe (cf. (3). the action of s) will be frozen for policies Te defined in later rounds > t. In short, Lemma 2 formalizes the intuition that all data used by algorithm remain effectively on-policy even if the policy n updated.

---

Published as a conference paper at ICLR 2026
For each round 2 1, let & qt QTh oh,) Because both n, and the MDP transitions
deterministic, ///² and dh are determined given me- Consequently, & is the sum of independent 1-subGaussians, and is therefore H -u-assaaasnian. Our third lemma deñnes a high probability event, which we will condition on in later parts of the proof. Its proof is based on standard concentration inequalities for self-normalized processes (Abbasi- et al. 2011).
(t)
H
Lemma 3. Define event Ehigh as
R Σ
H o
vh [H
Stu.s
S
2HH
In
1
+
In
2
Ad
Then F[Cnigh] 2 1
Define
d
D Xd
H x
V 2H
In
1
+ In
VD vAdH,
where D is defined in 55) Lemma show that under the event Erigh detined in Lemma 3
(Q)(s,))= (** a)) is upper bounded by aill((s, a)lxx,,.-1
Lemma 4. Under Enigh for any & 2 1,h E [H].0 S S [Daul, E Sh, E A, it holds that (Q) (s. S allo(s, a)lls + R, where En. is as defined in
The proof of Lemma 4 uses the high probability event in Lemma 3 and also critically relies on Lemma 2 which shows that all data in our dataset remain on-policy during the whole algorithm.
The following lemma, which is direct implication of Lemma and the definition of Cover e) (cf. (T) and Qi (cf. (3)). shows that for those state-action pairs (s, E Cover(Dr,,, E), we have 1Q,(s, a) Q (s, [ss,a]]
Lemma 5. Under Enight for any t 2 1, E [H] E Sh,a A. if (s,a) E)) then [Q:(s, a) - Q=* (s, S aE K.
Our final lemma characterizes the suboptimality of ,, for those well-explored states E S satisfying (s,a) E Cover(Dr,,, E) for all E A. Lemma 6. Under Enigh given t 2 1, E S1, (s, E f)r all A, then we have VT (s) VT (s) 2H + k).
To prove Lemma 6 by the performance difference lemma (Kakade & Langford 2002). we only need to show that for the state-action pair (s). af))) at each step h of the trajectory induced by the optimal policy π²,, switching from aj = x²' (s)) to Tx(5%) reduces the policy value of by at most 2(ar + k). for all actions a A. (5%, a) could be covered by Dr,, then the above claim is clearly true by Lemma 5 and the definition of and Q2 in (3). Otherwise, we could find a well-explored state s for some h' < h. Using the Q" realizability assumption (Assumption I for such si we further shows the policy value of any A at state s7, differs by at most aE
By taking H-1 and scaling by a factor of ((Ha) (denoted by ε), we arrive at the final guarantee of Algorithm
Theorem 1. There a constant so that for any > CVdHK, by picking certain e, with probabil-
ity at least 1 - 6, the number of episodes with suboptimality gap greater than is at most δ (dH
To prove Theorem 1 note that if (s] a) Cover(Dr.,,e) for all a E A, Lemma 6 guarantees that the suboptimality gap of such episode is at most E. In the other episodes, we must have increased the size of one dataset by whose total occurrence count upper bounded by HDD because every dataset will be updated at most D times by Lemmal
Time and Space Complexity. Assume that o(s, a) can be computed in poly(d) time and space given any S and a A. In Algorithm the size of every dataset is bounded by D, so its
7

---

Published as a conference paper at ICLR 2026
poly We assume that the action space finite, under which case (T(s) can be computed in time OI poly(d)). Therefore, the time complexity of Algorithm is O HT AIl poly(d)
space complexity is δ
5 REGRET MINIMIZATION VIA FROZEN POLICY ITERATION
In this section, we present the regret minimization version of Frozen Policy Iteration. See Algo- rithm for the formal description.
Algorithm Frozen Policy Iteration-Regre Minimization (FPI-Regret)
1: Initialize ( empty list for all 1 2 0,
[H]
2: for t= 1t=1=.... .... . do
3: { L
L is defined in Section
B.
4:
get
H do 5: for 1,
6:
if all of J, (5) (2) 1 1
). ,,, (x! are true then
D. 3 is as defined (6)
7:
take action a/ 10 (6)
(1) m is as defined in (
8:
9:
else
10:
he x- h
1 t min {i 1: 3: (5) is not true
11:
1/ 1
pick any (s such that (s &f Cover (D) 2-1)
13:
14:
take action ox t a
A! is as defined 7
end if (t)
16:
get 'h hh+1
end for
18:
if < L then
à Σ
(t)
h= Tb
D( appapdd (8 0be Gc)
(1) (t)
21: endi if
end for
Datasets and Accuracy Levels. Algorithm follows similar high-level framework as Algo- r However, Aggorithm[usse a fixed accuracy parameter which is inadequate for achieving
vT-type regret bound. Instead, Algorithm 2 Juses multiple accuracy levels < < T., where level I corresponds to an instance of Algorithm 1 with accuracy 2 and L is fixed constant defined
later (Section B.1 For each 1 > 1 and [H] maintain dataset ( which is an ordered sequence consisting of (8),3) 1
(0) (1)) As in Section 4 for every / 2 1, let ((0) be the snapshot of
( before the f-th round. We also write / = (( ( and x = A E
Adjusting Accuracy Level. At the beginning of each episode, the accuracy level / initialized to be L. i.e. the level with highest accuracy. For each step h, if there is action such that (s cannot be covered by D("" with accuracy 2-1' for some l' < I, then we would replace I with /' (Step aiming at lower accuracy of 2- Concretely, for each E Sr, define the indicator
()) = 1 (s, E Cover(D()) 2-1) for all a A (5)
where A (s) is subset of actions that will be defined later in this section. Here, Cover 2-1) follows the same definition as in (1. all of 7(4) (1 ... 300 (0) true, keep unchanged
8

---

Published as a conference paper at ICLR 2026
(1) for the purpose of exploitation. Otherwise, we replace with the add a data (1) (8) (s) is false, and take an exploratory action Once an episode finished, we br (t) into D where he is the last level where we take an exploratory action, and qe is the sum of rewards starting from step by the trajectory, and proceed to the next round.
and follows greedy policy Tt
smallest l' so that Dr (11)) (t))
Exploration under Accuracy Level Constraints. A subtlety in Algorithm 2 is that how the exploratory action is chosen. Unlike Algorithm where any action satisfying (s,a) & (Dv could be chosen, here we also need to make sure that the suboptimality incurred by the chosen exploratory action is upper bounded by (roughly) 2 2-1 To this end, for the t-th round, for each state s and accuracy level 1, we define a subset of actions, (s). which include all actions with suboptimality upper bounded by 2 2 To estimate the suboptimality of actions, we use the estimated Q-value accuracy level | 1. Finally, when deciding whether to the freeze the policy of a state s at the t-th round and accuracy level I, we only test whether (s, a) could be covered by the dataset for those actions in A
( (s), instead of the whole action space A.
Formally, we define A!"). 2.9 and o inductively on I as follows:
A {
1=1
(s) = (aEAAu-11 0f (s, 2 Q, (s, ((( - 2HAL11
(7)
1>1
(s) min N:N: (s) E Cover (f10h) (1)) ) for all E (()
|
Qf (s, a) = 200 f as:
(8) arg max Q: (8, ( (s)
(8)
where A is defined in Section B.1 and (s, = (b5 a), (1))
2h, Σx i= Phelhin
1 (9)
is the least
squares estimate by using only the first k data in 1// as in Section
The formal guarantee of Algorithm is summarized as the following theorem.
Theorem 2. With probability 6, for any 2 1, the regret incurred by Algorithm 2 satisfies RTg(T) = (V vdH²TRK.
Theorem 2 is proved using series of lemmas similar to those in Section 4 though the proofs here are more complicated due to the use of multiple accuracy levels. See Section B for the details.
Time and Space Complexity. In Algorithm 2 at most one dataset will be updated at each round, so its space complexity is OTT poly(d)). Note that 1/.0 is upper bounded by 1,, we can replace Step with min (t, L), which ensures that L does not affect the actual computational time. The time complexity of Algorithm is (HTT) HATTIAA/poo poly(d)).
Algorithm 2 also enjoys Uniform-PAC guarantee of Ō (HH See Section B.6 fo the details. Morcover, we Turther extend results from linear function approximation function classes with bounded cluder dimension. We provide bounds on Reg(T) of
Extensions.
o (V dimg (F,T-1) log 5
HT +log Nog,((FTT22)) (l.o) )
See Section foo the details.
6 EXPERIMENTS
We implement Algorithm and conduct experiments on simple RL environments from the OpenAI gym. Our experiments performed on CartPole-vl and InvertedPendulum-va.. We use the tile

---

Published as a conference paper at ICLR 2026
coding method (Sutton & Barto 2018) to produce a feature map in continuous space. The number of tiles per dimension is set to For InvertedPendulum-We we discretize the action space into actions and set the number of steps per episode to 60. In the implementation, is set to 10 and set to 1. We maintain the covariance matrix E.. to compute policy тı- Since storing En. for all h H and & I [Da,u] would lead to huge memory cost, we only keep the last 20 En, 's for each E [
CartPole
InvertedPendulumm
300
30
25
Reward
200
Reward
20
100
FPI
15
FPI w/o freezing
freezing
10
2
3 Episode
0
3 Episode
4
-10
-10
Figure 2: Learning curves on CartPole-vl and InvertedPendulum-vv. Results are averaged over seeds. The shaded area captures a 95% confidence interval around the average performance.
To ablate the role of freezing, we also implement version of Algorithm I without the freezing operation, i.e. using the whole dataset to estimate Q-values for each step h E [H]. Figure 2 shows that the freezing operation has indeed improved the performance of our algorithm.
DISCUSSIONS AND OPEN PROBLEMS
H Factors in the Regret and Uniform-PPa Bounds. The relatively high polynomial dependence on H in the regret and Uniform-PAC bounds primarily arises from the need for exploration under multiple accuracy level constraints. Ensuring that the optimal action each state preserved across all accuracy levels introduces additional H factors compared to the PAC analysis. Further improvements on the dependence of H will be an interesting future work.
Reliance on Deterministic Transitions. Applying our algorithm to MDPs with stochastic transi- tions is non-trivial, as the current analysis critically relies on the property that the state-action pairs collected in the datasets are well-explored. This property ensures that once pair (s, a) added to the dataset, the subsequent trajectory remains within the high-confidence region, preserving the effectively on-policy nature the data. Under stochastic dynamics, observing only one trajectory from given pair (s,a) a) does not guarantee that sufficiently large or high-probability subset of trajectories starting from (s, a) lies within the high-confidence region. Extending our algorithm to stochastic transition models hence remains an open problem.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Jinglin Chen and Nan Jiang. information-theorede considerations in batch reinforcement learning. In International conference on machine learning, pp. 1042-1051. PMLR, 2019.
Varsha Dani, Thomas Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In 21st Annual Conference on Learning Theory, pp. 355-366, 2008.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Informaionn Processing Systems, 30, 2017.
10

---

Published as a conference paper at ICLR 2026
Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in In International Conference Machine Learning, pp.
PMLR, 2021.
Simon Du, Sham Kakade, Ruosong Wang, and Lin Yang. Is good representation sufficient for sample efficient reinforcement learning? arXiv preprini arXiv: arXiv:/910.00 1ettt999000.. 2019a.
Simon S Du, Yuping Luo, Ruosong Wang, and Hanrui Zhang. Provably efficient q-learning with function approximation via distribution shift error checking oracle. Advances in Neural Informa- tion Processing Systems, 32, 2019b.
Simon S Du, Jason D Lee, Gaurav Mahajan, and Ruosong Wang. Agnostic q-learning with func- tion approximation in deterministic systems: Tight bounds approximation error and sample complexity. arXiv preprini arXiv:2002.077225 2020.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487 2021.
Noah Golowich and Ankur Moitra. Linear bellman completeness suffices for efficient online re- inforcement learning with few actions. In The Thirty Seventh Annual Conference on Learning Theory, pp. 1939-1981. PMLR, 2024.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Uniform-pac bounds for reinforcement learning with linear function approximation. Advances in Neural Information Processing Systems, 34:14188- 14199, 2021.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low bellman rank are pac-leamable. In International Conference on Machine Learning, pp. 1704-1713, PMLR, 2017.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pp. 2137-2143. PMLR, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in neural information processing systems, 34:13406-13418. 2021.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the nineteenth international conference on machine learning, pp. 267-274, 2002.
Daniel Kane, Sihan Liu, Shachar Lovett, and Gaurav Mahajan. Computationnalstatisttiaal gap in reinforcement learning. In Conference Learning Theory, pp- 1282 1302. PMLR, 2022.
Michail Lagoudakis and Ronald Parr. Least-squares policy iteration. Journal of machine learning research, (00Deec):107-11444 2003.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms.. Cambridge University Press, 2020.
Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in rl with generative model. In International conference machine learning, pp- 5662-5670. PMLR, 2020.
Gen Li, Yuxin Chen, Yuejie Chi, Yuantao Gu, and Yuting Wei, Sample-efficient reinforcement learn- ing feasible for linearly realizable mdps with limited revisiting. Advances Neural Information Processing Systems, 34:16671 166671116685,, 2021.
Zakaria Mhammedi. Sample and oracle efficient reinforcement learning for mdps with linearly- realizable value functions. In Proceedings of Thirty Eighth Conference on Learning Theory, volume 291, pp. 4078-4166 PMLR, 2025.
Rémi Munos. Error bounds for approximate value iteration. Proceedings of the 20th National Conference Artificial Intelligence, pp. 1006-1011, 2005.

---

Published as a conference paper at ICLR 2026
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pp. 2998-9933. PMLR, 2019.
Richard Sutton and Andrew Barto. Reinforcement learning: An introduction. MIT press, 2nd edition, 2018.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference intelligent robots and systems, pp. 5026-5033. IEEE, 2012.
Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, et al. Gymnasium: standard interface for reinforcement learning environments. arXiv preprint arXiv:2407. 0704407777032.. 2024.
Ruosong Wang, Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-614 6135, 2020.
Gellért Weisz, András György, Tadashi Kozuno, and Csaba Szepesvári. Confident approximate policy iteration for efficient local planning in q realizabe mdps. Advances Neural Information 2022.
Processing Systems,
Gellért Weisz, András György, and Csaba Szepesvári. Online linearly q" -realizzabl mdps is as easy in linear mdps if you learn what to ignore. Advances in Neural Information Processing Systems, 97919922229555 2023.
Zheng Wen and Benjamin Van Roy. Efficient exploration and value function generalization in de- terministic systems. Advances in Neural Information Processing Systems, 26, 2013.
Runzhe Wu, Ayush Sckhari, Akshay Krishnamurthy, and Wen Sun. Computationally efficient rl under linear bellman completeness for deterministic dynamics. arXiv preprint arXiv:2406. 1810, 2024.
Yue Wu, Jiafan He, and Quanquan Gu. Uniform-pac guarantees for model-based with bounded eluder dimension. In Uncertainty in Artificial Intelligence, pp. 2304-2313, PMLR, 2023.
Dong Yin, Botao Hao, Yasin Abbasi- Yadkori, Nevena Lazié, and Csaba Szepesvári. Efficient local planning with linear function approximation. In International Conference on Algorithmic Learn- ing Theory, pp. 1165-1192. PMLR, 2022.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near op- timal policies with low inherent bellman error. In International Conference on Machine Learning, pp. 10978-10989, PMLR, 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Provably ef- ficient reward-agnostic navigation with linear value iteration. Advances in Neural Information Processing Systems, 33:11756-11766 2020b.
THE USE OF LARGE LANGUAGE MODELS
In the preparation of this paper, employed large language models (LLMs) as a general-purpose assistive tool for non-substantive tasks. Specifically, LLMs were used for:
Assisting in editing, proofreading, and formatting of textual content.
Generating code snippets for creating figures and visualizations, which were then verified and customized by the authors.
12

---

Published as a conference paper at ICLR 2026
The LLMs did not contribute to the core ideation, analysis, substantive writing of the research. The authors take full responsibility for the entire content this paper, including any portions influ- enced by LLMs, and affirm that the of LLMs complies with academic integrity standards. LLMs are not considered authors or contributors to this work.
A MISSING PROOFS IN SECTION
The proofs of the lemmas in Section is almost the same with the ones in Section See lemmas
16 for the proofs of lemmas to respectively.
B MISSING PROOFS IN SECTION 5
B.1 NOTATIONS
Given any 8 E (0, 1), define constants
H-1
VH In
L
+ 1 (or +00 if 0)
k
241+2
Di = 2d 22 In
1
= = (dl 22r)
X2
d
Di
2H12
(V dHHlog
H + 2' Vdlk
2H
In
1
+ In
VDix VXdH 0
Ad
6
8
H + vdlk
A ai 2- +K
0 2-1
dHl log
8
For every / > 1, E [M],i 2 1, let (. be the round when (5 h 9h is appended to D For (t)
every round 2 1, let ( be the size of D(1, and & be - Q"1 (5) ah.).
B.2 UPPER BOUND FOR THE SIZE OF DATASETS
Lemma 7. For any 1 2 1, [H] 4 2 holds that 1 x011)
2-!
Proof. Denote (1) by t. From algorithm
(1)
(t) ag
Cover (D!)) 2-1
h/
so we have
(/0))
2 2-
Lemma 8. For any t 2 1, h E [H], it holds that (
ihh < Dr.
Proof. Denote ( by D. By lemma
2
Ohai
x00
-1
2 1 for all 1 < i S D, so we have
D
<
min
2
hh
1
13

---

Published as a conference paper at ICLR 2026
D
S 2
Σ min
1,
hir
i=1
det 2i(1) -i,t>>
22 .2n
(elliptical potential lemma (Lattimore & Szepesvári
2020
det
24,00
D
S 22dh In
1+
(9)
Ad
D
< 2d 2
(In(1 +x) S v for 0)
Xd
Therefore, D <
2 2d Plugging it into 9 gives the desired result.
B.3 AVOIDING RESAMPLING
Lemma 9, Given & 2 1,12 1, E [H] E Sr, ifll of ( ,
are true, then for any
2 t
Q (s,a) Q."h (s, Va E (s)
Te
(1) (s) = म. (1) (s)
(10)
A (s) = A (s)
Proof. Assume by induction TTp holds for t0 Since 2. (s) is true, k!9(s) (s) k." S D
for all 1' 2 l,a E A (s). Note that Q (s, a) depends only on ki (s); ('l (s) depends only on
(()(s)
A (s) and Q² (s, and (4+t) depends only on A (s) and Q (s, a): 10 holds also for
lo-
Lemma 10. For any 1 2 1, E [H) 2 Q 1 (5 (n
(. Q" (1) n
(5) a for all 2t, where
Proof. From algorithm we have 8/2
(t) = h, a
(2) = n and J. (x))) is true for all 1 S S
h < h' < H. By lemma (s
(t) (1) (s for all h < h' S H, so the trajectory starting
= ग.
from (5 an using policy is the same with the one using policy n.
B.4 CONCENTRATION BOUND FOR Q- QAVAUS
Let (Fr) be filtration such that F, is the olalebrra generated by (r )isisneem Then n. (()(s) --mmmcuuurablle for all 1, 2 1, S. Denote F[] by E-H.
Lemma 11. (6 is martingale difference sequence w.r.t (F.) Moreover, Fe/Fo-1 is
/ HHssuGaausiaan for all t 1.
Proof. Fix any & 2 1. Denote (t) by l. From algorithm H,
n (2) (0(()))) for all h < h S
we have dx
H
E
Th
(t)
ht
Q=e
(9) a
By tower rule, we have E,-1 = E Σith, (1) QT (t) (t)
Moreover, since 8% and ah are Fi-1 measurable for all [H] by the determinism of the MDP transitions, F-F is the sum at most H independent 1-subGaussians, and is therefore VH-ssbGaussian.
h4
14

---

Published as a conference paper at ICLR 2026
Lemma 12 (Concentration of Self-Normalized Processes (Abbasi- Yadkori al. 2011)). Let (Etfe= be a martingale difference sequence w.E.. {Fi) Let E Fi-1 be o-suuGaussian Ler he be valuud stochastic process such that is Fi-1 meessaaaaeb Let As be a d x d positive definite matrix, and A₁ be Ao Dimi did, Then for any ô > O, with probability at least - 6, we have for all 2 1,
forker
det(A det(Au) 1/2
Σ QEEt
I 20 In
A7
Lemma 13. Define event Enigh as
d
1+ k:
2H12
11 1, 12
Σ
1 h,d
2H
In
In
2
Xd
6
Then P(Cnigh] 2 1 - 8.
Proof. For any 1 1, h E [H], (5gg 1 is subsequence of (Er By lemmas 11 and 12 with
probability least 1
2 have for all 11
8
det
(11) 1/2
det
(t)
-1/2
! i
2h,0)
0
R.
S 2H
6/(211(3)
-1
d
trace
2H12
S 2H
2 In
+ In
Ad
d
k
2H12
< 2H
In
1
+ In
Ad
5
union bound over and h concludes the proof.
Lemma 14 (aanette al. (2200a). Lemma 8). Let {6:) be real-valued sequence such that
|6 I and [o be an vvaluee sequence. For A Xl >x
Φ107 have
n Σ
d
S n
1=1
A-1
Lemma 15. Under Enight for any 2 1,1 2 1, h E [H],0 S S (10) p Sh, a A, it holds that
(s. - -== th (s) & asllo(s, a) A)ll
1 + n
Proof. Let 6, be q
(100
(sh (1)
on.e 07. Then by assumption |6 S R.
@ (s) Q= Q=
K (ss ()(s, (= (s,
2 (s, a)
((s.a),
+
0 (s,
((s,a), O5
+
(s,
()ss.a).07) 1
k
6(s a), 1()
Σ
h
Ih
0%
i=1
15

---

Published as a conference paper at ICLR 2026
R
20
(s, a), 1:(1)
Σ
hi
Q
+ +c//3
1=1
(s, 0), (1) -1
2h
hi
Q
!1)
(
(1)
shii anis)
(1)
+ +6((0)
0% 1
(emma 10
i=1
(s, 0), E(0 -1
(1)
0%
+ 8$ + 5/10
h2
h₂
k
6(3, .), 1(10
di + E,00)
Ph
1=1
k
k
12) 10
$ {11o(s,)) 1) whik
+
h
6
+
-1
-1
Seachy-Schwartz
s < a) 1220 -1 (v
k
2H12
211
In
1
In
Vkn
vA
2
Xd
5
(lemmas 12 and 14)
s (ailló(s.
(assumption) 2 and lemma
hi
Lemma 16. Under Enigh given 2 1,1 2 1,h E [H]s E Sh. if (s) is true, then for any E (s).
(s, - (s,((s)))))))))))))))))))))))( s A
Proof. Denote (s) by By definition & S D Since (s) true, | a)ll -1 S 2-1
for all a E A! (1) (s), so we have
1000 Q (s.a)
(s, Q (s.a)
(by definition)
s arll@((, x(0 +
(lemma 15
s A
B.5 REGRET ANALYSIS
Lemma 17. Given E O, Uo. U1,... , Rd, let A be AI + Ei If ffllolla S then
there exist coefficients "I, Cn E R such that Σn= of s e² and ll10 En cuiily S VXe.
Proof.
Let u be A 11 Up. Then Up Au= = Au + E iult u. Pick G; u. We can verify that
( u)
Au T + 1=1
(o. u) u Au |1ol1 S E²
i=1
1=1
0g
42
||uul|2
Villulla S Vde
1=1
2
16

---

Published as a conference paper at ICLR 2026
Lemma 18. For 0,1 S h1 < h2 H, given policy and trajectories
{ 0 h/2 0/2 1=0
(1) (0)
such that TO To(s)) 0n for all 0 <is S n, hi + 1 h2 if
(10)
(4)
(0) (0)
Cover (H(S
( .0 i=1
(0) and 8hg #
1 hig for all Sis n, then for any policy π and any a1, 02 E A, it holds that
l0T 5hh .11
Q"
(h22
(0) 02)
$ (R + VAdHe + VIRR))
Proof. Fix policy Define policy ग and Na for E A follows, where stage(s) h if E Sn.
[(s) = To(s)
stage(s) l2
(())
stage(s)
> h2
(s())=
(1))
(8))
8 + 8/2
Since 8/2 Sh2
for all sis n, we have Q*
(8h1 1h1
(8) === ($hh Oh
(8)
Let R be
E Th
+ rh2-1 Sh1
(0)
Oh1 dhg To
(0)
Then (Th( th R Q" (5 a) for all A.
(0)
(0)
Denote
(( 22 by de By lemma 17 there exist coefficients "1 ,C E IR such that E ot
(4)
g² and
n2
du
GØ
S Vee
2
Let go be Σi=
( . (1)
R. Then we have for any a E A.
(0)
h22
4u
Q"
00)
R
QQ
(0)
(0)
Ta
(1) s
1=1
)
TTa
(0)
(0)
(0o,
0
+
Φ0
capie T
+
ci
-Q²
(5h " 0
(
(9)
1=1
< + vxe ||
10 112
+
Σ
iml
S 5 v AdlEe + Viice
which gives the desired result.
Lemma 19. For any 1 2 1, < h < W & 1, all of (
(((() are true, where
Proof. From the algorithm we have h = hr so policy oi is used at stage h + 1,.., H, which means all of (0 (1)),.. (0(0) (o(()) are true.
17

---

Published as a conference paper at ICLR 2026
Lemma 20. Under Enigh given 2 1, 1, [M] E Sh. ifall ()), (6), 130(0) are true, thenfor any Al (s),
(s, 2 (s. - h)
Furthermore, x (s) E A (1)))
(s).
Proof. Assume by induction the result holds for 10 - 1. Let the trajectory starting from (s,a)
using policy IT" be (5), dg 4411 " ,5H 0zt). where sh s, 0 a. For each h2 +
H,
if 2 (shg) is true, then
Q sha Ft
(1)
(shaa)
Q (shai (1) (sh22) A
(lemma T6p
(1] (sha) (shaa) A
(by the definition of ,.
(1)
2 Q (shg: x²" (sh2)) 2
(lemma 16
otherwise, let hn be max N ha all of J. (s%c) ... 38 (8%) true). which al- ways exists since h satisfies the condition. Define policy
(8) all of (s), mo(s) (s) otherwise
(8), ... ((((s)) (8) are true
iih the trajectory starting from (1 and using policy a!!) is the same with the using policy To. Starting from (5 o using policy wo. the trajectory will reach shy which not on any of the tra- (1) jectories starting from (6 (i because 7." (sh,) not true.
By lemmas 9 and 19
have that for any 1 S i
Using the induction hypothesis we have az E Al (st,), ) so 1 )l,))
S
2
By lemma
18 have
Q= hha
11) (sha)
at
Q (shns T (shaa) -2 kt (Vidtt + (Dh -2-1)
19
Qt ( (shg. T (sha)) -21
Therefore, we conclude that Q3!" (5% 19) (5 )) 2 Q"?" (5% T" (s%p)) - 24, for all h < N' s H. By performance difference lemma, we have
Σ
(Q=1² (Shr, a( (str) (sh,
4t² (sh x= (s%:))
W=h+1 2 2(H - A)
Furthermore,
0.1h (s) QT (s)) A
(lemma 16
18

---

Published as a conference paper at ICLR 2026
Q" (s) - (2 h) + 1)
Q (t (5)) (2(H - h) + 1)A
(by the optimality of x²)
(1)
5, 5
(1) (9) 2(H -
(lemma [6
so (s) E A (( which concludes the induction.
Lemma 21. Under Eigg for any t 1, E [M]] it holds that
H
E
Σ
(t)
V" (5%)
4H
Σ
A 1
k h
Proof.
We use induction on h from H to 1.
H
E
Li=h
H
Ex-1
hh
E2
(t)
1=++1
H
[0)
V"
4H Σ
100-1
(by induction)
1++1
(=++1
(1 (8)
4H
(00-
1=1+
h
(1)
(0)
A 11
10-1
(lemma 16
(
)
(19))
(1)
8h T
8/h
(2H + 1)A 40 -1
(by the definition of A.
(15 -1)
(1)
8/
(1)
(2H + 1)
(by the definition of m
88h
(1)
(2H 2)
(lemma [6
2 Q"
8h , n
(1)
8/
(1)
4H A -1
(lemma 20
V=
4HA 10- 11-1
Lemma 22. For any 1 S le < L, it holds that
1 3h H s.t.
(0)
k
S Dr
1=1
Proof. For any / 2 1 such that (1) < k for some ho E [H). the size of exactly one D( will increase by after the t-the episode for some < k and h E [H]. Then by lemma we have for any T 2 1,
T
k H
3h E [H] s.t. 1
< k
D
H Σ Dr
I.h
1=1
19

---

Published as a conference paper at ICLR 2026
Lemma 23. For any h E [1], it holds that Ei=12 2-th -0 =Ō(Vali
Tx vH
Proof. Let I. be
12
log2
T 2nd
so that HD2 2 T. By lemma 22 we have for any
S < T
T
k Di T,
min(k,L
k
min
< min
DL. Σ Dt S
D
h
Therefore,
T
T
I-1
10
2 1. +
2 2-h 2 2-(6)1)
1 (000 kk]
E=1
1=1
1=1
Tk
$
H
D1 2-1
VH
1=1
Tk
ddHT
VH
Proof of Theorem
By lemma
13
Enigh holds with probability at least 8, so we have
H
T
Reg( (T) S 4H
(lemma 21
%
1=1
VdH 2 2-th
K VH
H
hm
t=1
Tk VH
H
VdH
VdHT++
+
(lemma 23
h=1
3 (VVVHHT + VdHTTK)
B.6 UNIFORM-PAN PAC
Theorem 3. Let (ge) be the number of episodes whose suboptimality gap is greater than E. There exists a constant C such that with probability at least holds for all >> that
N ( +-CVHH2klog {
H ) ō (0 HHH
k
E2
Proof. Let h be min [T. 1, l, 4H² VaH) + θ (log #1
})} so that there exists a constant C
such that A ina + C v dx log H for all k < < L. With probability at least 1 8, Enigh is true,
so we have
8 CVTH2 m log
H
4H
c CVaHH k log
(lemma 21
20
t=1
h=1
Σ t=1
3h E [H] s.l. A 1
E
Vdk dr log
4H2
4
20

---

Published as a conference paper at ICLR 2026
3h [M] 1/ kk}
(by the definition of k)
Dt
(lemma 22
12
(T)))
C FUNCTOIN CLASS WITH BOUNDED ELUDER DIMENSION
We extend the Q-function into more general function class. Let Usp : H0 O) be a real-valued function class.
Assumption 4. For any policy n there exist ". ,0 O such that for (5, a) 8 E Sn, a E A.
Q= a), for all
Definition 1. A state-action pair a) E S is e-dependent on {(8, as di) C 8 A w.r.t
F if any pair of functions f1, E F satisfying Σi (fi (si a;) [2 a.)) S g² also satisfies (s,(s, f a)] S Further, (s, a) is e-independent of {(s;, a)) W.L F if (s, a) is not e-dependent on (s,,,;));;)
Definition 2. The s-eluder dimension dimg ) is the length d of the longest sequence of elements in S x A such that, for some e' 2 every element is e' e'-independent of its predecessors.
Define the width of a subset F. F at (s, a) E x A as
w)(8, = sup
(T(s, a) [().a)).
JJeF
For dataset D {(si, a;) 4)) and FC F, define
CDv = ((s,a) E CSSA A: (s,a) is e-dependent on {(s,, a;)) w.r.t F, and wy(s,a) S {e}.
Let B7 (F, (,) be
N NJ, a. 11x)) + 2at 8H + 8 8
4f2
8
8
where N(F, a, l denotes the a-covering number of F the sup-norm ||. -1....
Define least squares estimates and confidence sets as
arg min
Σ
( ② In.1
11)
fEF
Fll h.k
(EF
Σ
(1 (9 32 F, THT T
We use the same procedure as Algorithm 2 while for every h E [1]], Sn, a E A, re-define
gf0 (s) = 1 31 < DiA s.t. (8, E Cover (f ((102)
(1) { F 2-1) for all a E (1)
(1) 1*
(s,a) (s, =
(o (.
and re-define constants
D; - 2 H dimg (F,T-1)
HT log 5
log Nog (1111-l))))
A 2-1
T. [log2 TJ +
21

---

Published as a conference paper at ICLR 2026
Lemma 24. For any 1 1, [H), holds that D S Dr.
Proof. Denote (1 by D.
(h.s //.) > ) + dim (F,2
(1)
W r(t)
1=1
(1
4,7
(F, 4/112 77)
dimg (F,2-1) + dimæ (F,
+
2 2-21 21
(Proposition 3 from Russo & Van Roy (2013)
HI N (F,T l00e) +
H
HT log
00 22r
Hlog
dime (F.T-1) (1 < L)
S
Dr
Lemma 25. Define event Enigh
1I 122,h
[H]
1, o EF(
Then P(Cnigh] 2 1 8.
Proof. For every / 2 1, h E [M]] by lemma 11 and Proposition from Russo & Van Roy (0013)
with probability at least 2HT we have
E F0 (1) h.k
for all & 2 1. A union bound over and h concludes the proof.
Lemma 26. Under Enigh given 2 1,1 2 1, E [H],8 8 Sn. if ()) is true, then for any a E A
Q (s, º=²² " (s,a) 2-
Proof. Denote a) by k. Since 11th (s) is true, w (8, S 2 for all a E Al so we
have
(s) (s,a)
-
(12(5,,)) a) - uv uf (s,
S w w (8, a) 21
Lemma 27. For > 0,3 0,1 1 h1 < h2 < H, given a policy no, and n + 11 trajectories
{
(6)
(8) (2) 0/e
[ 1=0
such that To(s) (1) (1)
(0) a for all 0 < n, h + 1 s h h2 if (s o is e-dependent on
{(shi) onn )'mm and 9 & Sb for all 1 < sis S n, then for any policy x and any a, 02 E A, it
(1) )"
(0)
holds that
Q"
(0) hhg aa - -Q=
(0)
8/2
< 2
22

---

Published as a conference paper at ICLR 2026
Proof. Fix policy Define policy π and na for a E A as follows, where stage(s) = h if E Sh.
(o(ss) (T())
stage(s) - h2
(s)
stage(s) > h2
(0)
8/g
(s)
(0)
(())
8 # 1/22
( Since 1h h/2
(0)
for all
sis n, have (7((
(5/1 1/1
(i)
Q
(5h2
(1) (8)
Let R be
E rh +
+ rh
8h1
= hn
Then QTa( "/1
(0) (0)) = R + Q"
h/
for all E.A.
Since E/=l (foz, (sh) (sh):0h1) ohe
(8))
for (5 1h
= =05 E², we have
Soz,
h1
(0)
Thi
Sog
8/1 h1
(0)
(0)
Se
by the definition of e-dependence. Let 20 be
(0((mnn
h
(0)
R. Then we have for any a E A.
h2
8/g
+
R
1/y
by
TT
9h1
(0)
1h1
Q"
8/1 B4
(0)
s/1 fog:
0/1
(0)
for,
(0)
(0)
which gives the desired result.
By lemmas 26 and 27 lemmas 20 and 21 still hold. Lemma 28. For any h E [H]. it holds that
Σ 2- 10 =0 (v HPT dimg (F,T-1)
T
(log HT
8 + log NoggN(F,T-2.11 (1x0)
Proof. Let T, be
T
log2
+ log (F,, 2-2 2111 (10)) +01
2
H2 dimg (F,T-1) (log HT
5
so that HDL 2 T. By lemma
22
we have for any 1 S k < I.
T Σ
min
0 << k
< min
T, H
Dt
< H min
DL. Σ Dr s H
Σ D
1=1
1=1
1=1
Therefore,
T
T
I-1
(0)
2-L L +
2 2- k - 2-(121) 1 f1100 S sx))
1=1
1=1
L
5 VT + H
2-
1=1
-0
( 1PT dimg (F,T-1)
log HT + log N(F, 21 (1oo)
23

---

Published as a conference paper at ICLR 2026
Theorem 4.
With probability at least 8, it holds that for any T 2 1.
(v H (F,T-1)
HT
Reg(T) = O
log
log
ol
Proof. By lemma
25
Enigh holds with probability least 1 5, have
T
(T) 2 4/1
(lemma 20
1=
(1) 1=1
8H
h=1
(1
=0
HOT dime (F,T-1)
log
HT
5 + log N(,, 11,,,-2,11-113
(lemma 28
24


Reviews:
[{"review_id": "7KmubrIHrI", "reviewer": "Reviewer_Jqpd", "summary": "The submission employs algorithmic peeling for the exploration uncertainty to achieve the first sublinear regret with tractable computational complexity for learning in MDPs with linear $Q^\\pi$ realizability under deterministic transition and step-wise disjoint state spaces. Their analysis bypass the need of simulations of \"rollout reset\" in the online setting and naturally compatible with the Uniform-PAC analysis given the multi-level regression structure is similar to that in He et al. 2021 (Uniform-pac bounds for reinforcement learning with linear function approximation)", "questions": "- Although it is acceptable for a theory paper to not implement Algorithm 2, the fact that Algorithm 2 requires $\\kappa$ as an **input**, e.g., in the computations of $\\bar{L}$ and $\\Delta_l$'s, is indeed a concern since it is unclear how to estimate $\\kappa$ a priori. Do the authors plan to justify or make some educated guess on the mitigation of this fact?\n- Line 269: the term \"near-optimal\" might be misleading, I guess the authors mean low-$\\mathcal{D}_{t, h}$-uncertainty for $s_h^{(t)}$?\n- On the $\\sqrt{d}H$ in Assumption 2: let us say $\\kappa$ is very close to $0$, then what would be the upper bound of $Q^\\pi$ in Assumption 1, i.e., the upper bound of $Q^\\pi$ in Assumption 1 then becomes $\\sqrt{d}H$?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The delicate exploitation of the loopless deterministic \"tree\" structure via peeling and the design of $k_t(s)$ is novel\n- The multi-level uncertainty slicing in Algorithm 2 aligns well with the intuition and is easy to follow", "weaknesses": "- On the disjointness assumption of $\\mathcal{S}$: It seems that the regret analysis heavily rely on the disjointness assumption of the state space, i.e., $\\mathcal{S}\\_{h_1} \\cap \\mathcal{S}\\_{h_2} = \\emptyset$ when $h_1 \\neq h_2$, effectively enforcing the process to be a \"tree\", e.g., in **the proof of Lemma 18**, etc. This is an unusually strong assumption because such an assumption is often considered acceptable only in adversarial MDPs.\n\n### Minor weaknesses\n\n- According to the definition of $\\bar{L}$, the time complexity of Algorithm 2 appears to be finite only if $\\kappa > 0$, which is counter-intuitive. This might be only a matter of presentation but the reviewer encourages the authors to elaborate it in the final version.\n- Line 052: To the best of the reviewer's knowledge, MDPs with linear bellman completeness are only known to be tractable under deterministic transitions [1] or constant many actions [2]\n- On Lemma 12: The authors did not mention (in the main text) their assumption on reward noise in Preliminaries or Theorem 2.\n- Reindexing $\\mathcal{D}_{t,h}$ is acceptable but its notation should be detailed before Section 4.1\n\nReferences\n\n[1] Wu, Runzhe, et al. \"Computationally efficient rl under linear bellman completeness for deterministic dynamics.\" arXiv preprint arXiv:2406.11810 (2024).\n\n[2] Golowich, Noah, and Ankur Moitra. \"Linear bellman completeness suffices for efficient online reinforcement learning with few actions.\" The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B1Mgm8GCLD", "reviewer": "Reviewer_TPzh", "summary": "In online reinforcement learning with deterministic transitions, the authors propose frozen policy iteration under linear $Q^\\pi$ realizability. The method admits only high-confidence part of each trajectory into the dataset and freezes the policy at sufficiently explored states and learn without restarting simulator or resampling. They prove high-probability regret bounds, uniform-PAC guarantees, and extensions based on the eluder dimension, and demonstrate the effectiveness of freezing on small-scale control tasks.", "questions": "1. I am curious how the strong dependency on $H$ arises in the regret or Uniform-PAC bounds, and whether there is scope for mitigation.\n2. In the Algorithm 1 experiments, is it possible to compare with additional baseline algorithms beyond the freezing ablation? Could you also provide experimental validation for Algorithm 2?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. They present a computationally efficient algorithm that operates without simulator restart or resampling, and provide theoretical guarantees via high probability regret bounds, Uniform-PAC results, and extension to function classes based on the eluder dimension.\n2. They conduct ablation studies on the effect of freezing across two RL environments and report detailed implementation choices to aid reproducibility.", "weaknesses": "1. The theory relies heavily on linear $Q^\\pi$ realizability (Assumption 1) and deterministic transitions (Assumption 3).\n2. The regret bound and Uniform-PAC bound exhibit significant dependence on the horizon $H$.\n3. PAC guarantees may become loose over practically interesting $\\varepsilon$ ranges when $\\kappa$ is not small.\n4. The experiments are limited to verifying Algorithm 1 and ablation studies on freezing, while Algorithm 2—one of the core components of the proposed theory—was neither implemented nor evaluated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YI6jVWRM5c", "reviewer": "Reviewer_Mz6n", "summary": "This paper proposes a computationally and statistically efficient reinforcement learning algorithm, called Frozen Policy Iteration (FPI), under the linear $Q^\\pi$ realizability assumption.\nUnlike prior works, FPI requires no simulator access and operates with stochastic initial states and rewards, assuming only deterministic transitions.\nThe key idea of FPI is to freeze the policy for well-explored states—once all actions at a state are sufficiently covered, the algorithm stops updating that state’s policy. This mechanism ensures that all collected data remain effectively on-policy throughout learning, enabling efficient regret minimization without the need for resampling or simulator resets.\nFPI achieves a regret bound of $\\tilde{O}(\\sqrt{d^2 H^7 T})$, which is remarkable since most prior works under this assumption attain only PAC-type guarantees.", "questions": "1. At which point in the analysis is the deterministic transition assumption essential?\n\n2. During exploration—when a state–action pair $(s,a)$ is insufficiently covered by the dataset—do you think it would be possible to achieve better performance by selecting actions based on *optimal design* methods rather than choosing them randomly?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, the paper is well-written and easy to follow.\nAchieving what appears to be the first regret bound under the linear $Q^\\pi$ realizability setting is an interesting result.\nHowever, the paper seems to require clearer articulation and positioning of its key contributions.", "weaknesses": "1. Weisz et al. (2023) study a similar setting, except that they allow for stochastic transitions. Their algorithm attains only a PAC guarantee, not a regret bound. If their analysis were restricted to deterministic transitions, would their algorithm also achieve a regret bound comparable to FPI? A discussion of this comparison, maybe following Theorem 1, should be included in the paper (including explicit contrasts between the PAC guarantees).\n\n2. The computational cost of the proposed algorithm is not discussed. A comparison of the computational efficiency with prior works would strengthen the paper.\n\n3. The proposed algorithm is limited to finite state and action spaces, which diminishes the benefits of using function approximation.\n\n4. No experimental results. Even simple empirical validations or illustrative examples would help demonstrate the practicality of the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gN67k98AjN", "reviewer": "Reviewer_Cp6M", "summary": "This paper makes convincing progress in developing computationally and statistically efficient algorithms to learn an optimal policy in linear $Q^\\pi$ realizable MDPs, here with the additional assumptions that the dynamics are deterministic.\nI checked the proofs and they look correct and in retrospect simple which is a further positive point in favour of the paper.\nMoreover, the \"frozen\" technique seems to be useful in the experiments.", "questions": "If the memory issue I pointed out is correct, do you see any way to run the algorithm with memory that is independent of $\\mathrm{poly}(\\epsilon^{-1})$?\n\nThe author never says that after $D$ updates of the dataset than any state action pair is covered. I think this remark would help a lot with the proof sketch of Theorem 1. Could you present the proof stating that the statement of Lemma 6 implies Theorem 1 if every state action pair is covered, and then state that this happens necessarily after D updates of the dataset, invoking Lemma 1?\n\nDo you have any idea about how this algorithm could be extended to the adversarial reward setting ?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The analysis is simple and elegant.\n\nMoreover, you need only the realizability of the policies that are played by the algorithm. This is a much milder assumption compared to the Linear $Q^\\pi$ realizability assumption imposed in [1,2] which crucially relies on the realizability also of policies that are never selected by the algorithm (in order to prove that the expectation of any low range function is linear).\n\n[1] Weisz et al. Online RL in Linearly -Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore\n\n[2] Zakaria Mhammedi, Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions", "weaknesses": "1) If I understand correctly, the freezing technique requires keeping in memory the past linear weights of the Q function. Since the number of states to be frozen will eventually be of order $\\epsilon^{-2}$, it seems to me that the suggested algorithm requires memory scaling as $\\epsilon^{-2} d$. Is this correct? If yes, please mention it clearly in the paper.\nSimilarly, also deploying the learned policy does not seem very easy because it requires keeping in memory all the history of the $Q$-values weights, and a snapshot of the dataset at the different times $t$. At deployment time, when a new state action pair is visited, it does not seem very easy to check at which time step it started to be covered. Do you have any ideas how you could learn a policy parametrized by only $d$ parameters in this setting?\n\n2) The regret analysis holds only for stochastic rewards and not adversarially chosen. It might be better to clarify this.\n\n3) The work \"Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions\" by Zakaria Mhammedi is very relevant and should be discussed in the related works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)