Replicable Reinforcement Learning with Linear Function Approximation
Authors: Eric Eaton
Marcel Hussing
Michael Kearns
Aaron Roth
Sikata Bela Sengupta
Jessica Sorrell
Venue: ICLR 2026 Poster (2026)
Keywords: reinforcement learning
learning theory
replicability
stability
linear MDP
Primary area: reinforcement learning
TL;DR: We provide results for replicable ridge regression, uncentered covariance estimation as well as RL in both the generative model and episodic linear MDP setting.

Abstract: Replication of experimental results has been a challenge faced by many scientific disciplines, including the field of machine learning. Recent work on the theory of machine learning has formalized replicability as the demand that an algorithm produce identical outcomes when executed twice on different samples from the same distribution. Provably replicable algorithms are especially interesting for reinforcement learning (RL), where algorithms are known to be unstable in practice. While replicable algorithms exist for tabular RL settings, extending these guarantees to more practical function approximation settings has remained an open problem. In this work, we make progress by developing replicable methods for linear function approximation in RL. We first introduce two efficient algorithms for replicable random design regression and uncentered covariance estimation, each of independent interest. We then leverage these tools to provide the first provably efficient replicable RL algorithms for linear Markov decision processes in both the generative model and episodic settings. Finally, we evaluate our algorithms experimentally and show how they can inspire more consistent neural policies.

Published as a conference paper at ICLR 2026
REPLICABLE REINFORCEMENT LEARNING WITH LINEAR FUNCTION APPROXIMATION
Eric Eaton
Marcel Hussing
Michael Kearns
University of Pennsylvania eeaton @ www..eeee...a........eeee
University of Pennsylvania
University of Pennsylvania
mhussing @ seas. wwwas.uuenneedi.
mkearns Decis.upenn.edu
Aaron Roth
Sikata Sengupta
Jessica Sorrell
University of Pennsylvania aaroth @ cis. cis.upenn.edu
University of Pennsylvania sikata @ seas.upenn.edu
Johns Hopkins University jess @ @hu.edu
ABSTRACT
Replication of experimental results has been a challenge faced by many scientific disciplines, including the field of machine learning. Recent work on the theory machine learning has formalized replicability as the demand that an algorithm produce identical outcomes when executed twice different samples from the same distribution. Provably replicable algorithms are especially interesting for reinforcement learning (RI.), where algorithms known be unstable in practice. While replicable algorithms exist for tabular RL settings, extending these guarantees more practical function approximation settings has remained an open problem. In this work, we make progress by developing replicable methods for linear function approximation in RL. We first introduce two efficient algorithms for replicable random design regression and uncentered covariance estimation, each of independent interest. We then leverage these tools to provide the first provably efficient replicable RL algorithms for linear Markov decision processes in both the generative model and episodic settings. Finally, we evaluate our algorithms experimentally and show how they can inspire more consistent neural policies.
INTRODUCTION
Replication is a cornerstone of scientific rigor, yet it remains a persistent challenge for the machine learning community (Wagstafi) [2122] Pineau et al.) (02T). Especially in reinforcement learning (RL), two runs of the same algorithm independently sampled traces through a Markov decision process (MDP) may produce dramatically different policies (Henderson et al., 2018). While issues with instability in RL can be traced far back (White & Eldeib 1994| Mannor et al. 2004). many modern challenges stem from the integration of function approximation techniques such as neural networks into the RL workflow (Islam et al., 2017: Henderson et al. 2018). This instability may be caused by statistical noise (Thrun & Schwartz 1993), environment perturbations (Pinto et al. (017). local minima in non-convex optimization landscapes (Bjorck et al. 2002).. agents exploring different parts of the state space (Pathak et al. 2011)] 1)) or the non-stationarity of the data distribution (Baird) 1995 van Hasselt al. 2018;
al. 2025). Even when policies achieve similar average reward, their behavior may be different (Clary et al. 2219 Chan et al. 2020). complicating efforts to verify and build upon existing results. Such inconsistency is particularly problematic in settings where reliability is essential, such as safety-critical or high-stakes applications (García et al., 2015).
To study the limits of stability in learning, a recent line of work (Impagliazzo et al.) 2022) introduced model of replicability in which two executions of the same algorithm must give the exact same output (with high probability). Such guarantees provide a strong benchmark stability and allow us to audit randomized algorithms, controlling only the algorithm's 's internal randomness enables exact replication of results. The original paper of Impagliazzo et al. (2022) focused on basic statistical primitives like estimating the value of expectations over distribution. While this formal notion of replicability is compelling in stationary settings, it requires additional care in settings involving exploration, such the bandits setting (Esfandiari et al. 2023a). Motivated by the challenge of

---

Published as a conference paper at ICLR 2026
producing reliable outcomes in RL (Islam et al. 2017 Henderson et al. 2018: Voelcker et al. 2024
the notion of replicability has recently gained attention in RL research (Eaton et al. 2023 K Karbasi
et al. 2023). Although exploration poses algorithmic challenges that complicate replicability. many
reliability issues in RL may be related to the difficulties of function approximation (Thrun & Schwartz/
1993] van Hasselt al. 2018). Yet the initial studies replicability in RI. (Eaton et al. 2023
Karbasi et al. 2023) are limited to settings in which one can easily enumerate the state-action space.
In this work, we provide provably replicable methods for linear function approximation in RL. We give the first replicability results for RL beyond the tabular setting: in particular for the linear MDP setting (Yang & Wang 2019; Jin al.] 2020) in which is assumed that the reward function and transition probabilities are representable as an (unknown) linear function of some common embedding of state-action pairs. This is a setting in which provable learning guarantees are known via function approximation; we give algorithms recovering these provable learning guarantees together with new guarantees of replicability. Our main contributions are as follows:
1. We describe new procedures with first guarantees for (a) replicable regression with random designs and (b) replicable uncentered covariance estimation, both of which may be of independent interest.
2. We apply these tools to develop the first replicable RL algorithms for linear MDPs, encompassing both the generative model and episodic exploration setting.
3. We validate our methods in empirical RL scenarios, demonstrating that they yield replicable or more consistent policies with far fewer samples in practice than required by the theory.
PRELIMINARIES
We frame the RL problem (Sutton& & Barto 2018) finding approximately optimal policy in an episodic MDP (Puterman 1994) M = A, R. P, H.q} with state space S, action space A. reward functions R = { The ( transition kernels
{Ph H)) horizon H, and initial state distribution q. In every episode, an agent starts from a state so ~ q and interacts with the MDP for H steps. At any point the agent in some state sh, chooses an action a₁ receives reward (sh,, an). and transitions to a new state according to (s an). The objective is to find a policy,
{Tx) hE(H] that maximizes the expected cumulative reward (q) E D H-1 (n(s,, an)] where the expectation is over the randomness in the initial state, the policy, and the transitions.
h=o
Notation:
Throughout the text, we will use || Ilp to denote the fn-norm and if p is omitted ||
simply denotes the l norm; for matrices || denotes the Frobenius norm.
2.1 LINEAR MARKOV DECISION PROCESSES
When state-action spaces become large, practitioners often resort function approximation solve the RL problem. A common approach to obtaining theoretical guarantees is to make consistency assumptions about the underlying structure of the MDP. We will assume that the rewards and transitions can be represented by a low diweennnniioal feature representation Φ S x A + Rd, This gives rise to the commonly studied framework of linear MDPs (Yang & Wang 2019 Jin et all 2020).
Definition 2.1 (Linear MDP), M is a linear MDP with a feature map ó S x A + Rd for any [H], there exists unknown (signed) measures 14g. (ph, ...)) over S and an unknown vector
O2 IRd such that for any state-action pair (8, a) S x A. we have
Rn a) = (ō(s, a), 0%) and P)(()s, = (ő(s, a)ss,a..u.)
We make the following structural assumptions on the MDP, that are common in the literature. Assumption 2.1 (MDP properties). All rewards are bounded between 0 and 1, the features are normalized such that for all (s, a). [lo(s, a)ll < and for all h, we have max(Ilu(S)) [I), s vd.
A fundamental property that makes this framework interesting is that the Q-functions themselves are always contained within the span of the representation, i.e.
Proposition 2.1 (Jin et al. ).20)). For any linear MDP and policy n, there exists a set of weights (wā]eetr hE(HH) such that for all (8, a, h) E S x A [H), we have Q7, (s, a) (Ø(s, a), wX)
Note that simply assuming Proposition 2.1 as our starting point, rather than making the linearity assumptions on the MDP, would not be enough for our algorithms, since we will have propagate
2

---

Published as a conference paper at ICLR 2026
functions outside the linear class for exploration (Jin et al. 2020). A last fact that will come in useful later is that the weights within each linear MDP can be bounded from above.
Proposition 2.2 (Jin al. (0200). In a linear MDP. for any fixed policy n, let {WT. keeHe be the corresponding weights such that (s, (o(s, a), wh. .. For all h, we have that [| S 2H 2Hv
2.2 REPLICABILITY
To study RL stability in linear MDPs, we adopt the framework of Impagliazzo et al. (2022). which defines replicability as the demand that randomized algorithm produce the same output with high probability when run twice with the same internal randomness but independently resampled data.
Fix domain X and target replicability parameter E (0, 1). A randomized algorithm Å X" + V is p-replicable if for all distributions D over X and choice of samples S1, S2, each of size n drawn from D, coupled only through the internal randomness of A, we have: P2. (((1):) # A())r) S
Definition 2.2 (Replicability (Impagliazzo al. 2022
Recent work has extended this idea RL (Eaton et al.) 2023 Karbasi al.] 2023), adapting the definition of replicability from the supervised setting; rather than drawing two samples from the same distribution, one asks that two runs of the RL algorithm (with fixed internal randomness) in the same MDP yield identical final policies. For instance, Q-learning agent with epsilon -rrendy exploration interacts with a stochastic environment (external randomness) starting with a randomly initialized policy (internal randomness). Running the agent twice the environment with the same internal random seed should produce the same policy with high probability. Obtaining identical policies, rather than merely achieving similar rewards, crucial for predictable and analyzable behavior. This stricter requirement eliminates subtle but potentially impactful behavioral differences that arise from variations in the training data and cause drastic failure in safety-critical domains (Gareía et al. 2015).
Our results rely on key technique by impagliazzo et al. (0022) that uses randomized rounding to obtain replicability in vector spaces, which we extend to matrix spaces. We state slightly adapted version of their results in Algorithm T and Theorem 2.1
Algorithm 1 R Soyperygri-Rourdee
(adapted from Algorithm 6 in (Impagliazzo et al. 2022
Input: Matrix A E Rd xd2 with entries bounded between b, and be, shared randomness r, rounding accuracy
1: Uniformly random draw off from [0, a:4 xd2 using r
2: Vi E [d1].j j. [dy]. define the set of grid intervals
{[b,, b,+a (b, [a 6, +a.
+a), [ +a f +a, b.+ -2a), ........ +
.,, ta +xa, be }}
3: Form Á by mapping each entry As.j to the midpoint the (unique) grid interval from the above
set that contains A.j.
4: Return A.
Algorithm T will return a version of the input matrix A that has been rounded to a randomly shifted grid of intervals in each dimension. This rounded version a replicable estimate that does not differ too much from the original estimate, as formalized in the following:
Let A A e Rdixd with entries bounded between by and be where the bounds are solely required for compu-
Lemma 2.1 (adapted from (Impagliazzo et al. 2022)). Let A be Algoritium !
tational purposes. For both matrices A(a), [1,2], we have ||A/(a) a(A(a))]le S vdn a
A
Further, denote ([A(2) - A(2)|| A. Then, Pr(A(AA)) = 2 did2
Proof. If the Frobenius norm between the two matrices A to l, conversion the (i, coordinate of the two matrices is not rounded to the same point with
(2) is at most A, then by a Frobenius
probability !4! A union bound over the matrix size proves the claim about replicability. For accuracy, the algorithm will change each element by at most a /2, resulting in an E bound on the matrix difference. Converting from the elementwise difference Frobenius completes the proof. I1
3

---

Published as a conference paper at ICLR 2026
3 REPLICABLE TOOLS FOR LINEAR SPACES
Before discussing replicable RL, we first establish two algorithms that are useful for working with data under linearity assumptions and that will be crucial components of our RL procedures. These include replicable linear regression estimator procedure. Given the widespread use of linear estimators across scientific disciplines, we believe that these methods hold broader methodological relevance beyond their use for replicable RL.
well as a replicable second order moment estimation
This section will first consider supervised setting where we are given a dataset of input variables E X C Rd and corresponding labels y IR. The dataset is drawn independently from some distribution D, and the data is modeled using a linear function f(x) = w x, where w E IRd the vector of model weights. We will make the following assumption about boundedness that 1) ensure the resulting optimization problems remain well-defined and stable and 2) prevent extreme values from disproportionately influencing the learned models
Assumption 3.1 (Boundedness of Inputs, Labels, and Weights). The input vectors E R satisfy |x|| < L, the labels E IR satisfy ly| I Y, and all model weights w E R satisfy ||w] - B
3.1
REPLICABLE RIDGE REGRESSION
To effectively operate within the linear MDP space, first step is develop a procedure for replicable linear regression. Prior work on bandits provided a replicable least-squares estimator in the fixed design setting (Esfandiari al. 2023a) where one has access distribution of fixed set input vectors x. This approach is limited to scenarios in which a fixed design distribution can be obtained replicably. In addition, it assumes that the design distribution sufficiently spans the input space. Both of these conditions are not common in RL, where the distribution of visited states evolves as the agent explores its environment. Our first contribution is novel algorithm that builds on the well-known ridge regression algorithm (Hoerl & Kennard 1970) to circumvent these issues. This algorithm works both in scenarios where the full space is not spanned as well as problems with random design.
Our R-Ri ---iidg-RRggrese in algorithm is given in Algorithm Saorithh@aand applies replicable rounding as described in Algorithm to the weights output by classical ridge regression. The key insight that allows us to ensure replicability is that the ridge regressor converges to a global optimum due to the strong convexity of the minimizer. While many results in replicability rely on closeness to a ground truth parameter, simply require that the algorithm relate approximations in objective to approximation in parameter space. Note that we are not making any assumption about the data are given at this point and the results hold even in the agnostic case. The following theorem quantifies the amount of data needed to obtain a replicable estimate.
minimize the given objective. This lets us
Theorem 3.1. Suppose Assumption 3.1 holds. Let E, 10, Let Di = (D,,... Dr} be sequence of independent distributions. Let S ~ DM denote sample generated by taking M i.i.d. draws from each of the t distributions in D(g-- Denote N tM.. For any D(g) have that Algorithm is p-replicable. Let 0 = arg ming ED [00 y)² + \1 Then with probability at least over choice of the sample S ~ DM, holds that w 0|| S E as long as the number of (B+Y)&d samples drawn is N E E (x)) log (1)
As mentioned before, the proof for this result uses the fact that ridge regression provides strongly convex objective. Using this observation, one could first derive a standard excess-risk bound for ridge regression using classical real-valued uniform convergence tools such as Rademacher complexity,
Algorithm 2 R E--Ridge-Regresssiin
Input: Data D {x,, y: W regularization parameter X, accuracy E, failure probability replicability parameter p, shared random string r
1: Compute w (E x A1) Σ5= XJy
N
2: w E--Hypergrid-Roundii (W,, 602 601-
3: return w
4

---

Published as a conference paper at ICLR 2026
and then invoke strong convexity to translate an excess objective tolerance E' > 0 into parameter- distance bound of the form || - E O (()) where w is the ridge solution from Algorithm and À is the regularization parameter. Yet, in our replicability setting, the rounding step requires the weights produced in two independent executions be extremely close in Euclidean norm; achieving this level of parameter closeness via such a risk-based argument would require an extremely small excess-risk tolerance, and feeding this tolerance back into the uniform convergence bound leads to a substantially worse polynomial dependence on d than the rate established in our theorem.
Instead, we rely on a stronger guarantee. Specifically, we show if the population gradient of the risk is uniformly close to the empirical gradient, that is if sup, V (()) VoR(()) S E', then strong convexity implies that the distance between the empirical and true minimizer can be bounded as || 0|| E O /A) (without square root). We formalize this in Lemma A.2 It remains to prove that this gradient difference is in fact small. A traditional uniform convergence analysis is insufficient rectorvaalued, Thus, to get the bound in our theorem, we leverage a recent result by Foster et al. (2018) 8) that provides efficient gradient uniform convergence based on Rademacher results in (Bartlett et al. 2005) and a vector-valued symmetrization lemma (Maurer] 2016). These results are largely for independent and identically distributed data. To obtain our multi-distribution result, we generalize the Rademacher results by |artlett et al. (2005) to multiple distributions in Appendix A.I and propagate this change through all relevant results. Then, we prove in Theorem A.2 that the ridge empirical gradient is close to the population gradient. The key feature of this analysis is that it comes with no dependence on d just like the traditional risk analysis even though are analyzing a d-dimensional object. This gives us all tools to conclude a replicability result in Theorem 3.1 Now, we argue that replicability can be achieved via rounding the weights by relying on the parameter closeness established by strong convexity. We provide the full proof in Appendix A
as the gradient
Theorem 3.1 only establishes replicability; the accuracy of the algorithm is determined by the shape of the underlying data distribution. To get accuracy guarantees, we will make the standard assumptions that the underlying functional structure of the labels is in fact linear and the labels have 0 mean. Furthermore, we will assume access to a distribution over core set of vectors that allows us to represent every point on the domain. More precisely, we define the following core set.
Definition 3.1 (Core set). Let v(x.) be design distribution over vectors X; E C& C 124, We call C {x,} a core set if it satisfies that every vector in the domain X can be written as a linear combination of points on the support of v, i.e. x Ex. Esupp(v) (),(x;)), with |1 < k
Note that we are not making any second order moment assumptions in our core set definition, which means standard least squares estimation would not be possible. Yet, given such core set, we can give a direct bound on the prediction error of the R-Ridge-RRgee
on procedure.
Theorem 3.2 (Fixed Design R- R-Ridge Regression Error). Suppose Assumption holds. Consider dataaet D {x,, 34 J.W where x; comes from coreset Cs. Let x be drawn i.i.d. from Cj 'ss distribution v (x). For each yo, let y: (0*)² x; +&; where {e: are independent random variables [B+Y)2 1 log (t)) samples, c0(p-281²
with E(e.] = 0. Let Ō, E (0, 1). As long as we draw N E Ω
Algorithm 2 is p-replicable, and with probability 1 1- 8 it holds that max, |x (w 0-) s
To prove the accuracy bound (see Appendix A.4 we use our earlier analysis to control the dis- tance between the output w of Algorithm 2 and the ridge minimizer 0. By the triangle inequality, maxx [x (w- f*) is then bounded by the sum of maxx [x (w f)] and max, xx (Ø 0*),, so it remains to control the second term. The coreset assumption implies that every x in the support of v can be written linear combination of at most & coreset points with a coefficient vector of norm at
most Vk, which yields the bound xx T (0 0-) < Vie( Ex ((0 ())=)))) 1/2 Using the optimal-
ity of the ridge solution 0 for the model y = 0 x + e, we show that [xx (Ø 0 0*)) < 120
which implies the uniform bound x T (0) 8*)l < v VEX for all x. Choosing À = =²/ (4
makes this term at most e/ 2/2 combining it with the e/2 bound on |x" (w 0) yields the guarantee.
We acknowledge that the generality leads to slightly worse bounds than those achieved in the fixed design setting. This is because require technique that works even when the data support is small. If one is instead able to make assumptions about the eigenvalues of the second order moment one can recover tighter rates, close the fixed design rates of (Esfandiari et al. 2023a) by setting À = 0.
5

---

Published as a conference paper at ICLR 2026
Algorithm 3 R UR-UC--OO UL-UU--CoV-Estimattee
Input: Data = [x,m (4.m) accuracy e, failure probability 6, replicability parameter
P. shared random string r
1: Compute Eg1 EE= M mm= x. x isisisd
2: Σg f- R- R--yyergridd
(Li,, v, Tp-
de
3: Σij f- Ei for all I j
b symmetrize
4: Return (2)
> IIPSD(A) = U diag(max(({) 0)) UT for A = U diag({) U
3.2 REPLICABLE UNCENTERED COVARIANCE ESTIMATION
The second tool we need is procedure for obtaining a replicable estimate of the second order moment matrix, which we will use to identify parts of the state space that have been visited. In Algorithm we provide this replicable estimation procedure. Two features of a covariance matrix are that is symmetric and positive semidefinite (PSD). Simply applying element-wis randomized rounding to the regular covariance matrix might lead to an output matrix that is neither symmetric nor PSD. Thus, algorithm first computes the upper-triangular part of the regular uncentered covariance, randomly rounds it, and then symmetrizes explicitly. Finally, we project the matrix back onto the original cone by clipping its eigenvalues to ensure the algorithm' 's output is PSD. We guarantee replicability and closeness in Frobenius norm to the expected uncentered covariance via the following Theorem.
Theorem 3.3. Suppose Assumption 3.1 holds. Let e, 6, E 1). Let D = [Di.... DrY be sequence of independent distributions. Let S ~ DM denote a sample generated by taking M i.i.d. draws from each of the distributions in Djg. Denote N = tM. Algorithm iis p-replicable. With probability at least - 8 over the independent draw of the dataset D == (x,, m (T).m))(TT)((M) it
holds that [[IPS Σ
E[xx 11l S as long we draw N E ( log
& samples.
To prove the theorem, we apply an element- wise concentration inequality to the upper-triangular part the empirical covariance matrix and then symmetrize it by copying these entries to the lower- triangular half. The rounding procedure may cause some of the smaller eigenvalues of this matrix to become negative, so we project back onto the cone by clipping these eigenvalues. Since the true uncentered covariance matrix lies in this cone, this projection cannot increase the estimation error. Moreover, as |z|| < 1 for all x E X. the covariance matrix is uniformlly bounded. Combining these observations with Lemma 2. yields the stated result. The full proof is provided in Appendix B.1
REPLICABLE RL WITH LINEAR FUNCTION APPROXIMATION
Equipped with the tools to handle linear spaces replicably, we now present our main results: replicable algorithms for linear MDPs in the generative model and the more challenging episodic setting.
4.1 REPLICABLE LINEAR RL WITH GENERATIVE MODELS
As a warmup, we will consider the setting of RL with a generative model (Kearns & Singh 1998). In
this setting, one is given access to generative model G. that given a state 8 and an action Og returns a deterministic reward R₁, and next state $1+1 sampled from the transition probability Pa (- ax).
In the tabular setting, it common to simply sample every state-action pair from the environment sufficiently often until enough data for statistical concentration is available (e.g. (Kearns & Singh 1998 Kakade )003). the linear setting this is unfortunately not possible since there are possibly infinitely many state-action pairs. Instead, need to obtain set of representative state-action pairs that will cover the lower dimensional space of o. Such set of vectors is often assumed given and can be represented via set of states that gives Mahalanobis distance guarantees YYang & Wang 2019) or via an optimal design (Lattimore & Szepesvári, (020). Given that R-Ridge- --Ridge-Regreese -eee-eegressssss on works without second order moment assumptions, we will reuse core given in Definition 3.1
We state our algorithm for replicable RL with generative model and access to a core set in Al Algorithm Intuitively, the algorithm produces i.i.d. dataset of size M for every h by drawing

---

Published as a conference paper at ICLR 2026
Algorithm 4 R LSVI with core set
Input: MDP M, state action pairs (for core set) C, accuracy and failure probability replicability parameter p. random string r
dh22122 291--26y= log (4) ( + Q KHPd
1: M +
2: V.++(.) =0
3: for to do
4:
D (o(s,a), (8, a) + [n+1(s')] (0 (oya) X, 2H2; (2r 8
5:
W
6:
(n(.) (())
7:
(-)+) min max. Qn u), H}
8: end for
9: return { s.t. for all h. (8) arg max, (8,
next states from the generative model according to the distribution of the core set. then computes the value of the current from the next time-step iteratively. As we use a replicable estimation procedure to obtain the weights w,, at each round, we are guaranteed that estimates in every will be replicable as long as we draw sufficiently many samples. This formalized in the following statement.
Theorem 4.1 (Sample Complexity R-LSVI with core set). Let M be a linear MDP and suppose Assumption 2.7 holds. Suppose we have access to set of state action pairs C, s.t. the corresponding vectors (s, a) form a core set C& of lower dimensional space of Let 6, E. [0, 1]. Algorithm
is p-replicable and with probability 1 - 8 outputs a list of policies {
LH that guarantees us
vss E S, (V* - V*() S E as long as we draw E 20 2e log ( (#) samples.
The accuracy proof combines the standard core set ideas (Lattimore & Szepesvári 2020) with Theorem 3.2] which ensures that each stage's ridge regression produces Q-estimates with Bellman error at most e'. A standard dynamic--rogrammiig argument then shows that for all we have (V*(s) / (s)l S 2F Choosing e' appropriately yields the claimed accuracy. For replicability, we know the only randomness comes from sampling. We start with fixed initialization; then proof by induction that the value estimates remain replicable. The full proof provided in Appendix
4.2 REPLICABLE LINEAR RL WITH EXPLORATION
The previous section illustrated that it is possible to obtain replicable algorithms in the linear MDP setting. However, so far we assumed that we have access to specific core set of state-action pairs of which we can draw next-state samples we please. A key challenge for replicability the noisy exploration process in RL. In the exploration setting, it is possible to obtain optimal policies that are non-replicable using LSVI-UCB (Jin et al.) (020). This section builds on this well-established finding and Algorithm 5 provides a replicable version of LSVI-UCB called R-LSVI-UCB.
deal with
R-LSVI-UCB proceeds in rounds. Rather than updating the policy at every episode, it collects a batch of sampled data with the current policy to obtain replicable estimates of the required datendepnndent quantities. The algorithm then uses R- ---Ridge-Regress ion to obtain a mapping from & to a prediction of Q. For exploration, we add upper confidence bound (UCB) bonus term computed via R-UC- Cov Est imat This leads to the following guarantee for R-LSVI-UCB.
Theorem 4.2 (Sample Complexity R-LSVI-UCB). Let M be an episodic linear MDP and suppose Assumption 2./ holds. Let e, 6, E (0, Algorithm is p-replicable and after collecting total of 62 log" (1/8) trajectories, and outputs a list of policies 11T = { Je=o such that with -41pa
MT E Ω probability for all π E 11, Ex "
V= (so) s
The full proof is provided in Appendix D While our analysis resembles the high-level ideas of LSVI-UCB by Jin et al. (2020), additional ingredients are needed to prove both the replicability and accuracy guarantees in Theorem 4.2 We cannot simply plug primitives for linear spaces into the fully online RL loop, as they only work for fixed-size batches drawn from a fixed distribution. Instead, analyze batched variant of LSVI-UCB in which the policy is held fixed within each round and
7

---

Published as a conference paper at ICLR 2026
Algorithm 5 R-LSVI-UCB
Input: MDP M, accuracy E, failure probability ò, replicability parameter p. random string
1: T - 3 H (l1g((()))))
M < 50 T' log 1/6
) + S(dH);
de
2: A - Q H ); Aw t ( A + 0 )): Pest = (H:T)) = 22(7)
DH
3: () = (3 (.))] for all h E [M]
4: (-) max.Ed (x a) for all h E [M]
5: # hhe [M) where (s(s) arg maX.EA (s.aa
6: for round t E [7] do
7: for m [M] do
D Sample M trajectories under new policy
8:
Observe starting state " q
9: for h E [ do
10:
Take action dn, t (s and receive reward R m.
end for end for
12:
13:
for E [H] do
14:
for m E [M do
15:
nn, = ( In,
16:
for i i [t) do
17:
Vm. R A + h+1 (x1)))
18:
end for
end for
20:
wf+ + R- R-Ridge-Reeee Regbee--Rgressiion(((S..... (amea
[meta)).E(() X, Awo Sear Pesss r)
G++1 t 2-UT--ov-Betiinatiioo//aaaaaa
AA, dests Pest. r)
22:
A + G +AI
23:
Q++((,)) -min H, (W/+1 oo(;-)) + (lo(s)) ((
V ()) = max Q (.,a)
25: end for
26: #1+1 [ ]kElnn where # at+ (.) = arg maxac.1 2 (.,a)
27:
end for
28:
Return {+*) h
a fresh batch of trajectories collected. This batching breaks a key algorithmic symmetry in the original LSVI-UCB analysis, where both regression and the bonus use the same Gram matrix over all past data. As a result, Theorem 4.2 requires a new regret argument for this perturbed-Gre -ramm setting together with a new inter-policy value difference bound (Lemma D.I].
(Lemma D.5] Corollary D.I
The optimism and regret guarantees in LSVI-UCB rely on computing the bonus from the empirical regularized Gram matrix and applying an elliptical potential argument. Under rounding, this argument no longer applies directly. We develop a novel perturbation analysis that bounds Mahalanobis norms under positive semidefinite perturbations of the Gram matrix (Lemmas [D.2 D.3). This shows that the (Lemma D.4) and that its cumulative contribution to regret matches the unrounded rate.
bonus still yields an optimistic Q-function that drives exploration
The guarantees for the replicable ridge and uncentered covariance routines only apply when each call receives i.i.d. samples from fixed distribution. the adaptive, episodic setting the data distributions in later rounds depend earlier policies. To reconcile this, prove replicability by strong induction over rounds: conditioning on the event that both executions have produced identical policies up to round the data in round + 1 is draw from fixed distribution determined by the shared internal randomness and hence identical across runs. We refer to Appendix DD2 for more details.
4.3 LIMITATIONS
The two algorithms we present both give strong stability guarantees in linear function approximation MDP setting. However, their sample complexity cost is larger than that of their non-replicable
8

---

Published as a conference paper at ICLR 2026
counterparts; additionally, linear MDPs alone are often insufficient in practice. While recent work has shown promising results employing linear MDPs on common benchmarks Zhang et al. (2022), they require meticulous feature learning procedure that has replicability guarantees. Towards fully practical replicabilityy. the feature learning problem for low-rank MDPs (Jiang et al. 2017 Du
et al. 2020 Agarwal al. 2020 Modi et al. 2024) remains interesting open question.
EXPERIMENTAL EVALUATION
While some of our worst-case guarantees might seem impractical, this section shows that in practice, algorithms need far fewer samples to work effectively. We also show that even though our results are largely derived for linear MDPs with fixed feature representations, the ideas behind replicability might be valuable to study and its components on the well-studied CartPole environment (Barto et al. 1990). Then, we study the effects of quantized neural network Q-values in Atari environments (Bellemare et al., 2013).
in the non-linear deep RL setting. First, evaluate our algorithm
5.1 EVALUATING REPLICABILITY ON REAL DATASETS
Episode
NOT
REPLICABLE
To show that our algorithms do not require impractically large amounts of data, we implement a version of fitted Q- iteration (Ernst al. (005) with replicable rounding akin generative model algorithm. We use the offline CartPole dataset available via d3ripy (Seno & Imai] 2022) and random Fourier feature encoding for Φ. Over rounds, we use ridge regression fit the value function. The rounding bin size is a 0.2.
RERUCABIE
300
10
Most Common Identical Policy in % NOT
REPLICABLE
200
We vary two components: To ensure that all policies are trained on distinct samples and assess the amount of data needed for replicability, we sub-sample a fraction of the data for training. Then, we vary to examine its impact. We evaluate the cumula- tive return measure of policy quality, and the largest fraction of identical learned weights across all runs. Figure presents the results, averaged over 100 algorithm runs.
REPLICABLE
10-
Fraction of Dataset
Figure 1: Mean return and per- centage of most common identi- cal weight vector. "Not replicable" indicates a baseline without regu- larization and rounding. Using fraction of the data is sufficient to achieve replicability.
Our results show that replicability is achieved with a fraction of the available data and is correlated with high returns. This suggests that when the algorithm fails to fit the values, replication of policies becomes unlikely. While we expect regularization play a role, its effect appears negligible here, likely because a few weights are disproportionately large. Available data seems be the driver for replicability.
Mean episodic return
5.2 QUANTIZING NEURAL Q- V-VALUSS
2010
While we previously noted that achiev- ing replicability in neural network set- ting might be difficult without further work on feature learning, we set out study the effects of our algorithmic elements on deep learning algorithms, We use the recent PQN algorithm (Gal- lici et al., 2025) to train Q-functions on MsPacman and Atari Breakout. Our theory suggests that rounding weights and using regularization can give rise to stability. The implication of rounded weights is rounded Q-values. Rather than rounding weights directly, which may lead to unforeseen challenges in deep learning, we round the outputs of our neural networks onto a fixed grid. We compare version of quantized Q-values with regular PQN as well as regularized versions of both. We measure the final return by averaging each training run's 's 20 final returns. Then, we take holdout expert datasets from Minari (Younis et al.) 2024) for the chosen tasks. On these, we compute the pairwise action agreement across seeds. We report mean and 1.96x standard error over 15 runs in Figure and hyperparameters in Appendix E
8830
Saeal Seedie
2000
2230
5.4
63 5.
63
5.2
35
67
59
Mean pairwise agreement
Mean pairwise agreement
Figure 2: Mean return and agreement MsPacman (left) Breakout (right). Quantization and regularization increase agreement while maintaining high performance.

---

Published as a conference paper at ICLR 2026
Regularization alone is insufficient to ensure high agreement either task while quantization leads to increased agreement. This is in part attributable to low action gaps (Farahmand (201T) in the Atari games. While the quantized policies agree, they can do so on the wrong actions indicated by the low return on Breakout. When combining regularization and quantization, the algorithm's 's return is within variance of the baseline, indicating no loss of performance. In addition, the benefits of agreement from quantization are kept providing empirical evidence for our theoretical findings.
RELATED WORK
Linear Function Approximation RL Early asymptotic convergence guarantees for RI. with function approximation were laid by TTitsiklis & Van Roy (1996) while the study of finite-sample guarantees for RL with linear functions was initiated by Munos & Szepesvári (2008), who study the fitted value iteration algorithm with generative model. Since then, various works have studied
linearity in RL via a multitude of MDP assumptions (Jiang et al. 2017] Zanette et al. 2000b] Dann
let al. 2018 Modi et al.; 2020 Cai et al., 20200] He al. [202]] Wang et al. (021). Closely related to our work, others have studied version of linear MDPs that can represent mixture distributions (Jia
al. 2020 Ayoub et al.] 2020 /Zhou et al. 2021aa] Zhou & Gu 2022) are represented via linear
kernels (Zhou et al. 202 The linear MDP as studied in our paper was introduced by Yang &
Wang (019); Jin et al. (2020) and has since been studied quite extensively (Zanette al., (2020a) where ultimately He et al. (2023) provide nearly minimax guarantees on the online problem. Reward free versions of both linear mixture MDPs (Chen et al.) [202]] Zhang et al., (023) as well as linear
MDPs (Wagenmaker et al.] (022) have also been explored.
Replicability The seminal idea of algorithmic stability has a long history in learning theory and given rise to various settings such as error stability (Kearns & Ron 1999). uniform stability (Bousquet & Elisseeffi 2002), or differential privacy (Dwork et al.] 2006). each quantifying how sensitive an algorithm''s s output
changes in its input data. Recently notions of formal reproducibility have been
proposed (Ahn ct al. 2022 Impagliazzo et al. (022). The notion we call replicability (Impaghazzo al. 2022) was introduced study the limits of stability. It asks that two executions of an algorithm on two different samples from the same distribution will yield the exact same outcome. Replicability
strongly related aforementioned areas like privacy, even generalization (Bun et al. [023
Kalavasis et al., 2003). Since its inception, replicability has been studied for clustering (Esfandiari
al. [002bb) large-margin half spaces (Kalavasis et al. 2024a), hypothesis testing (Liu & Ye 2024
Hopkins et al. 2024| Aamand et al./ (2025), geometric partitions (Vander Woude et al. 2024). and
online settings (Esfandiari et al., 2023a] Ahmadi et al. 2024; Komiyama et al.| 2222). )) Hopkins &
Moran (2025) study the role of randomness for replicability and Kalavasis et al. (2024b) provide
an overview of the computational landscape of replicability. Closely related to ours is the work on
replicable tabular RL (Eaton et al. 2023 Karbasi et al.) 2023 Hopkins et al. 2025).
7 CONCLUSION AND FUTURE WORK
In this work, we provide algorithms for replicable ridge regression and uncentered covariance estimation as well as a set of algorithms for replicable RL with linear function approximation, both in the generative model and the episodic setting. Our experiments validate that the ideas introduced through replicability are feasible real-world dataset sizes and that they extend naturally the deep RL setting. Thus, our algorithms take step towards building more reliable procedures that will facilitate safe deployment of RL in the wild. While we believe that this work can build the foundation for stable RI., there is no immediate societal impact as our manuscript is largely of theoretical nature.
We leave open several interesting questions for future work. Our algorithms were inspired by instability in deep learning but do not directly address the feature learning problem. Additionally, our experiments demonstrate how rounding via quantization can reduce policy differences in neural network training. Scaling these ideas to larger environments, including continuous spaces, is an important step toward ensuring replicability in real-world, safety-critical systems. Finally, concurrent work by Hopkins et al. (2025) shows that it is possible to achieve replicability in the tabular setting at little to no overhead cost. Given the sample complexity of the algorithms presented in this work, a core question is whether an approach like theirs can be extended to the linear setting as well.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
We gratefully acknowledge support from the Simons Foundation Collaboration on Algorithmic Fairness and the NSF ENCoRE TRIPODS Institute. EE and MH's 's research was partially supported by the DARPA Triage Challenge under award PRR00124420300 or recommendations expressed in this material are those of the authors and do not necessarily reflect the view DARPA or the US government.
Any opinions, findings, and conclusion
REFERENCES
Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, Shyam Narayanan, and Sandeep Silwal. On the structure of replicable hypothesis testers. arXiv preprint arXiv:2507.028-2. 2025.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. In Advances in Neural Information Processing Systems, 2020.
Saba Ahmadi, Siddharth Bhandari, and Avrim Blum. Replicable online learning. arXiv preprint arXiv:2411.137300 2024.
Kwangjun Ahn, Prateek Jain, Ziwei Ji, Satyen Kale, Praneeth Netrapalli, and Gil I. Shamir. Repro- ducibility optimization: Theoretical framework and limits. Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Syy- tems, 2022.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, 2020.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine learning proceedings 1995, pp. 30-37. Elsevier, 1995.
Peter Bartlett, Olivier Bousquet, and Shahar Mendelson. Local Rademacher complexities. The Annals of Statistics, 33(4):1497 1537, 2005.
Andrew G. Barto, Richard S. Sutton, and Charles W. Anderson. Neuronlike adaptive elements that can solve difficult learning control problems, pp. 81-93. IEEE Press, 1990. ISBN 08 18620155.
Heinz H. Bauschke and Patrick I., Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer Publishing Company, Incorporated, 2nd edition, 2017. ISBN 3319483102.
M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling, The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279, jun 2013.
Johan Bjorck, Carla Gomes, and Kilian Q Weinberger. Is high variance unavoidable in RL? a case study in continuous control. In International Conference on Learning Representationss 2022.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, ((Ma)):4995522 2002.
Mark Bun, Marco Gaboardi. Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 520-527, 2023.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza-
tion. In Proceedings of the 37th International Conference on Machine Learning, 2020.
Stephanie Chan, Sam Fishman, John Canny, Anoop Korattikara, and Sergio Guadarrama. Measuring the reliability of reinforcement learning algorithms. In International Conference on Learning Representations, 2020.
11

---

Published as a conference paper at ICLR 2026
Xiaoyu Chen, Jiachen Hu, Lin Yang. and Liwei Wang. Near-optimal reward-free exploration for linear mixture MDPs with plug-in in solver. In International Conference on Learning Representations 2022.
Kaleigh Clary, Emma Tosch, John Foley, and David D. Jensen. Let's play again: Variability of deep reinforcement learning agents in atari environments. ArXiv, abs/1904.0631 2019.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alckh Agarwal, John Langford, and Robert Schapire. On oracle-effiiient pac rl with rich observations. In Advances in Neural Information Processing Systems, volume 31, 2018.
Simon S. Du, Sham M. Kakade, Ruosong Wang, and Lin F. Yang. Is a good representation suf- ficient for sample efficient reinforcement learning? In International Conference Learning Representations, 2020.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Conference on Theory of Cryptography, 2006.
Eric Eaton, Marcel Hussing, Michael Kearns, and Jessica Sorrell. Replicable reinforcement learning. In Advances in Neural Information Processing Systems, volume 36, 2023.
Damien Ernst, Pierre Geurts, and Louis Wchenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6, 2005.
Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas. Replicable bandits. In The Eleventh International Conference on Learning Representa- fions, 2023a.
Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni, Grigoris Velegkas, and Felix Zhou. Replicable clustering. In Proceedings of the 37th International Conference on Neural Information Processing Systems, 2023b.
Amir-massoud Farahmand. Action-gap phenomenon in reinforcement learning. In Advances in Neural Information Processing Systems, 2011.
Dylan J Foster, Ayush Sekhari, and Karthik Sridharan. Uniform convergence of gradients for non-convex learning and optimization. In Advances in Neural Information Processing Systems, volume 31, 2018.
Matteo Gallici, Mattie Fellows, Benjamin Ellis, Bartomeu Pou, Ivan Masmitja, Jakob Nicolaus Foerster, and Mario Martin. Simplifying deep temporal difference learning. In The Thirteenth International Conference on Learning Representations, 2025.
Javier García, Fern, and o Feránndez. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(42): 2015.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for linear Markov decision processes. In Proceedings of the 40th International Conference on Machine Learning, 2023.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. MAAI'8//AAI' AAAAAA11//AAATT 18. AAAI Press, 2018.
Arthur E Hoerl and Robert W Kennard. Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1):55-67, 1970.
Max Hopkins and Shay Moran. The role of randomness in stability. In Forty-second International Conference on Machine Learning, 2025.
Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, and Christopher Ye. Replicability in high dimensional statistics. arXiv preprint wrXiv:2466.06628 2024.
12

---

Published as a conference paper at ICLR 2026
Max Hopkins, Sihan Liu, Christopher Ye, and Yuichi Yoshida. From generative to episodic: Sample- efficient replicable reinforcement learning. arXiv preprint arXiv:2507.11906 2025.
Shengyi Huang, Rousslan Fernand Julien Dossa, Chang Ye, Jeff Braga, Dipam Chakraborty, Ki- nal Mehta, and João G.M. Araújo. Cleanrl: High-quality single-file implementations of deep reinforcement learning algorithms. Journal of Machine Learning Research, 2022.
Russell Impagliazzo. Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning, In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022.
Riashat Islam, Peter Henderson, Maziar Gomrokchi, and Doina Precup. Reproducibility of bench- marked deep reinforcement learning tasks for continuous control. In Reproducibility in Machine Learning Workshop (ICML), 2017.
Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang. Model-basee reinforcement learning with value-targeted regression. In Proceedings of the 2nd Conference on Learning for Dynamics and Control, pp. 666-686, 2020.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert Schapire. Con- textual decision processes with low Bellman rank are PAC-learnable. In Proceedings of the 34th International Conference on Machine Learning, 2017.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, 2020.
Sham M. Kakade. On the Sample Complexity of Reinforcement Learning. Phd thesis, 2003.
Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistinguishabiiiy of learning algorithms. In Proceedings of the 40th International Conference Machine Learning, ICML'23, 2023.
Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, and Felix Zhou Replicable learning of margennaggin halfspaces. In Proceedings of the 41st International Conference on Machine Learning, 2024a.
Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas, and Felix Zhou. On the computational landscape of replicable learning. In Advances in Neural Information Processing Systems, volume 37, 2024b.
Amin Karbasi, Grigoris Velegkas, Lin F. Yang, and Felix Zhou Replicability in reinforcement learning. Advances in Neural Information Processing Systems, volume 36, 2023.
Michael Kearns and Dana Ron. Algorithmic stability and sanity-check bounds for leave-one-out cross-validation. Neural Computation, 11siiiin,nn,1,,))).. 1166):127--1453, 1999.
Michael Kearns and Satinder Singh. Finite-sample convergence rates for q-learning and indirect algorithms, Advances in Neural Information Processing Systems, 11, 1998.
Junpei Komiyama, Shinji Ito, Yuichi Yoshida, and Souta Koshino. Replicability is asymptotically free in numti-armed bandits. arXiv preprint arXiv:2402.0739) 2024.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Sihan Liu and Christopher Ye. Replicable uniformity testing. In Advances in Neural Information Processing Systems, volume 37, 2024.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Confer- on Learning Representations, 2019.
Shie Mannor, Duncan Simester, Peng Sun, and John N. Tsitsiklis. Bias and variance in value function estimation. In Proceedings of the Twenty-Fire International Conference on Machine Learning, pp. 72, New York, NY, USA, 2004. Association for Computing Machinery.
Andreas Maurer. A vector-contracee inequality for rademacher complexities. In Algorithmic Learning Theory, pp. 3-17, 2016.
13

---

Published as a conference paper at ICLR 2026
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforce- ment learning using linearly combined model ensembles. In Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, pp. 2010-2020, 2020.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. Journal of Machine Learning Research, 25(6):1-7,, 2024.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity- exploration by self-supervised prediction. In Proceedings of the 34th International Conference Machine Learning, 2017.
Joelle Pineau, Philippe Amcentt-aaarre Koustuv Sinha, Vincent Lariviere, Alina Beygelzimer, Florence d' Alche Buc, Emily Fox, and Hugo Larochelle. Improving reproducibility in machine learning research(a report from the neurips 2019 reproducibility program). Journal of Machine Learning Research, 22(164):1-20, 2021.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial rein- forcement learning. In Proceedings of the 34th International Conference on Machine Learning, 2017.
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley& & Sons, Inc., USA, 1st edition, 1994. ISBN 0471619779.
Tom Schaul, Andre Barreto, John Quan, and Georg Ostrovski. The phenomenon of policy churn. In Advances in Neural Information Processing Systems, 2022.
Takuma Seno and Michita Imai. D3rlpy: An offline deep reinforcement learning library. 23(1), 2022.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018
Sebastian Thrun and Anton Schwartz. Issues in using function approximation for reinforcement learning. In Proceedings of the 1993 Connectionist Models Summer School, 1993.
John Tsitsiklis and Benjamin Van Roy. Analysis of approximation. In Advances in Neural Information Processing Systems, volume 1996.
learning with function
Hado van Hasselt, Yotam Doron, Florian Strub, Mattco Hessel, Nicolas Sonnerat, and Joseph Modayil. Deep reinforcement learning and the deadly triad. arXiv preprint arXiv:1812.02644 2018
Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, and N. V. Vinodchandran. Replicability in learning: Geometric partitions and kkm-spemer lemma. In Advances in Neural Information Processing Systems, volume 37, 2024.
Claas A Voelcker, Marcel Hussing, and Eric Eaton. Can we hop in general? a discussion benchmark selection and design using the hopper environment, In Finding the Frame: An RLC Workshop for Examining Conceptual Frameworks, 2024.
Claas A Voelcker, Marcel Hussing, Eric Eaton, Amir massoud Farahmand, and Igor Gilitschenski. MAD-TD: Model-augmented data stabilizes high update ratio RL. In The Thirteenth International Conference on Learning Representations, 2025.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. Reward-free RL is no harder than reward-aware RL in linear Markov decision processes. In Proceedings of the 39th International Conference on Machine Learning, 2022.
Kiri L. Wagstaff. Machine learning that matters. In Proceedings of the 29th International Coference International Conference Machine Learning, 2012.
14

---

Published as a conference paper at ICLR 2026
Yining Wang, Ruosong Wang, Simon Shaolei Du, and Akshay Krishnamurthy. Optimism in rein- forcement learning with generalized linear function approximation. International Conference Learning Representations, 2021.
Chelsea C. White and Hany K. Eldeib. Markov decision processes with imprecise transition probabil- ities. Operations Research, 42(4):739-749, 1994.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Omar G. Younis, Rodrigo Perez-Vicente, John U. Balis, Will Dudley, Alex Davey, and Jordan K Terry. Minari, September 2024. URL stttps://do1 org./orrgoooo wwt.ooo.......eeeeeoeeeee
13767625
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill, Learning near optimal policies with low inherent bellman error. ICMI''0.. JMLR.org, 2020b.
Junkai Zhang, Weitong Zhang, and Quanquan Gu. Optimal horizon-free reward-free freerd-free exploration for linear mixture MDPs. In Proceedings of the 40th International Conference on Machine Learning, 2023.
Tianjun Zhang, Tongzheng Ren, Mengjiao Yang. Joseph Gonzalez, Dale Schuurmans, and Bo Dai. Making linear MDPs practical via contrastive representation learning. In Proceedings of the 39th International Conference on Machine Learning, pp. 26447-26466 2022.
Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-free reinforcement learning for linear mixture MDPs. In Advances in Neural Information Processing Systems, 2022.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Proceedings of Thirty Fourth Conference on Learning Theorr, 2021a.
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In Proceedings of the 38th International Conference on Machine Learning, 2021b.
15

---

Published as a conference paper at ICLR 2026
A PROOFS OF SECTION 3.1
A.1 UNIFORM CONVERGENCE WITH INDEPENDENT, BUT NOT IDENTICALLY DISTRIBUTED DATA
Let 111 = (D,,..., Dr} be sequence of distributions and denote by S ~ Dij a sample generated by taking M i..dd draws from each of the t distributions of Dij) Recall that t denotes the round that algorithm is in and M is the number of samples we draw per round. Note that DMj is a distribution over full sample of data of size but the data is only sampled from an identical distribution in blocks of size M. We prove below that independence is sufficient for proving Rademacher uniform convergence bounds with respect D
Mt. Every data point drawn is independent from the other,
by adapting the proof from Shalev-Shwartz Shwartz & Ben- Sen-David (2014).
Lemma A.1 (Expected Representativeness Bounded by Twice Rademacher Complexity; Independent
Samples from Sequence of Distributions Version of Bartlett al. (2005) Lemma A.5). For a given sample S ~ Di of size n Mt, let (s)) = 22 (z; and let Lpz (0) EEs (0))
12
E S
(uppppp (0) Ls()))] 2
E S
sup
Σ
(z))l
(=13
i=1.2
Proof. Let S² = (21 ~ D2f be another sample from the same distribution. For all 0 E O Lon (0) Es [()) Therefore for every 8, we have that
Ly (0) (0) = 5 (0)
we take the supremum over both sides and then applying Jensen's 's inequality we get,
sup(Lpn (0) Ls))) = sup E L))) - Ls(0)]
s Elsup(Ls (0) Ls(
g'
Now, if we also take an expectation over the sample S, we get
Islsup(bDy (0) Ls(())] <
E
[sup (L (0) - Ls()))
8
8,5
E Sup T. S.S
Σ
- -(z))())))))
Now, notice that for each j. 2j and z are i.i.d. variables, with respect to each other. Notice that this does not rely on i.i.d. over all data points drawn over the sample, only over the data point drawn in each of 8 and S' coming from the same Dj as i.i.d. samples. Therefore, within the expectation we can swap them out with each other (using the ghost sample trick) to get
E Isup S.5'
((((())) f(z)))
-
F S.S
Sup
(U((e;)-(($))) > (f(+)) f(x))))
{
Now letting oj be the random variable denoting Pr(a, = 1) = Pr(a, = =-1) = 1.4 we obtain that (lo,(f())- f(z,)) + [f(()) - -(x)))]
(sup
S,
(4)
Sup ((((z)))({})) + ((x)))
S,5
If we repeat this for all indices j. then we get that
E
[sup
Σ (f(2)) f(x))) =
E
(sup
o,(((z)) - f(x)))
8.5"
1=1
16

---

Published as a conference paper at ICLR 2026
and using the fact that
ox(((=))))-)) ((x)) z sup Σ
o. + sup Σ
-o.(())
sup
i=1
Finally, we can upper bound
sup
(f(())))(() S sup
ff + sup
f.f(2
S
2 SwDM (~(
E sup
Σ o,f(z,]] 1=1,5,8
A.2 GRADIENT CONCENTRATION AND STRONG CONVEXITY
We want to prove the replicability of Algorithm 2
To do so, we will show that the empirical minimizer induced by the algorithm is close to the expected minimizer in L2 norm via convexity, This we will use to obtain bound on the difference between estimator produced by two independent runs of the algorithm. Define
R(0)=
E SmD (x,y)ES
Σ
(10, v) + 2|101
and let
Rs) = Σ (00,x) - y)² + 11111
(x.8)ES
First, we will prove uniform convergence of the gradient difference of these two functions. To get to this result will build result by Foster et al. (2018) who provide bounds for the uniform convergence of gradients in non-convex learning. While this tools are more general than what we need, it still gives us dimension-fe free bounds on the ridge regression gradient. The key statement that we will need is Proposition for i.i.d. data. The i.i.d. A. The original statement by Foster et al.) (2018) provides guarantees of the data goes back to Lemma A.5 by (Bartlett et al. (005). We reprove this Lemma with our data requirements in Lemma A. A. The remaining elements that are used in the proof of proposition A. I are Theorem A.2 in (Bartlett al., 2005) and Lemma 4 in (Foster et al.
2018) which still hold. We thus state the slightly generalized form of Proposition 2 by Foster
al.
2018 here:
Proposition A.1 (Symmetrization ((Foster al. 2018)). Let L.D = E(nww))D (600; v)] denote
some expected risk function parametrized by some weight vector 8. Let L. be the corresponding empirical risk function. For any 8 >> O, with probability at least 1 5 over the independent draw of data {2i, Ye Vo
N-1
o Ve(0;20 2i vn)
log 1/8 N
Esup (V) ViOO
N
E. sup
Σ
sup 2V,(0;,,,)1 (l,..y
To bound the first term on the RHS, the following Theorem is then introduced
Theorem A.I (Rademacher Chain Rule (Foster et al. 2018)). Let sequences of functions G; : R
R and F; R + R be given. Suppose there are constants La and Lpp S.1. for all S i / N,
|VG < Ta and VK=I [1FFs < L.p Then
sup 2 2: 0
Σ (.V((..F((O)))
S Lp Esup ai 0
Σ (a, (G.(F((O)) + LG Esup a.
Σ F.(O)a
where F.;; is the Jacobian of F; which lives in Raxk and o E [=1]KXN is a matrix of Rademacher random variables.
17

---

Published as a conference paper at ICLR 2026
An immediate consequence of this lemma is the uniform convergence guarantee of the ridge regression gradient which we prove here.
Theorem A.2 (Uniform Convergence of the Ridge Gradient). Let f(2,, y:) S R R be i..dd. samples drawn from distribution D, with |1:i|2 S and Iydl S Y. For fixed radius B 2 0, define the function class
F=
(z. v) (0 y)²
|101| I B
Then there exists an absolute constant e: > such that if
(B (B+ + Y)² log 8)
1
NE
8²
then with probability least 1 6,
Vol(()) - V PaRss se.
sup
Proof. The outline of the proof is as follows. First, we obtain a and upper bound on the expected supremum norm the gradient via the vector valued Rademacher statements in Proposition A. and Theorem I. then we conclude a total bound on the number of samples required via McDiarmid. However, before we do so, we note the following. the gradient formulation of the ridge regressor, the weight regularization term is independent from the data and simply cancels out in the difference of the gradients of V VR( v (0). As consequence, it suffices to bound only the data dependent term. Thus, we start the proof by instantiating the loss as [ xt ---y) n)² + \||01| which means by Proposition A.I
4
N
log 1/01
Esup (()) (Rs(0)]
Sup
Σ o, VE Fz, 36)
sup [[ 2. v)ll 0,
N
The gradient of the loss can be written as Ve(0; x y) (0 x - y)æ. Since the norms of all elements in the supremum are bounded the term on the right also easily bounded
sup |[ x, v)ll sup ||(0 x y|دl| (B+Y) 0.a.y
0.a.y
It remains to bound the first term on the RHS. We invoke Theorem A.1 with G(a) = [a y) F(0) (0 z) and 1. Suppose |all s A then Gi(a) is A-Lishhitz More precisely, we will have that suPa.y [G'(a) & (B + Y). Furthermore F (0) x and we know that ||>||| S which means that I. 1. As a result, we have
N-1
sup 9
Σ o, Vi(00 Fy. 34
sup
G
+AE
N
N-1 Σ
(B 83 vi)
1/
1
sup
+ AE E
0
i=
N-1
sup
020
EE
Σ
0:Ui
+ A
N-1
F
Σ
0330
N-1
N-1 Σ
BE
Σ o3.
+ +B+Y)
< 2B + +YVN
where the last step is a standard Rademacher argument (see, e.g. Shalev-Shwartz & Ben-David 2014)) It remains move from the expected value bound high probability bound. So far, we have
222(++YVV)
(og(1/8))
E Sup VR((0) VRs(0)) <
(B
N
N
18

---

Published as a conference paper at ICLR 2026
4 x 2(2+ + +(B+Y)
(1/((
N (B + () log(1/51)
N
VN
where the second inequality holds as long as we pick N > log(1/)), s.t. 1o8(1/6) S 1. Observe that the bounded difference sup, (VR(0) (î)( changes by most (B Y)/N if we swapped out one sample in the empirical average since [|((0;,,)) S B + YII. As a result, we have by McDiarmid's s inequality that
Pr
sup 0
VR(0) vRs(0)] >
sup VR(0)
vRs(o>]| +t exp
2N
S 82
(B + Y)²
By setting 61 = 82 = 5/2 and applying a union bound, we have with probability
8 that
(B + Y)(8 + Vlog(2/0) + vlog(1/6))
(B + () + 2 (og((/0))
sup
VR(O)
vR)( -
VN
Setting equal and solving yields
(B + (8+ + 2 (2g(2))))
100( B + Y)²
2
log
N
2²
82
Lemma A.2 (Parameter Bound for Ridge via Strong Convexity). Suppose and |10||2 S B. define
Ø = arg min R(0), â arg Rs(0).
0
Because R(0) is 2X-strongly convex, it has unique minimizer Ô. Conditioned on the fact that Vo Ro se.
sup -
we can bound the parameters of the estimator as
00
0
1
E
2X
Proof. Note that both R and Rg are 2A strongly convex. Consequently, the unique minimizers satisfy RR(0) = 0 = (0). and we have that [[V)(0)) - vRs(O)) = [VR(() < e. Now, by strong
convexity have
2 م|1 < (VR VR(O)) < (
( 8)1
When i the inequality holds. Thus, we can safely divide both sides by the norm of the parameter vectors and we get.
2Λ1 0|| ( - R(OO)I
Recall that VR(Ø) O. so have
2A1 - 0| < [R(O Se
110 - 0| < 21
19

---

Published as a conference paper at ICLR 2026
A.3 PROOF OF THEOREM 3.1
With these tools equipped we are ready to prove Theorem 3.1
Proof. Conditioned the success of Theorem A.2 and Lemma A.2
know that
A 2
10 01 S é' (2/(22)
Consider now two iterations of the same procedure producing two estimates ((1) and ((2) By triangle inequality and the above, have that these estimates can differ by at most 211 0ll which means that
|| 11 < A.
Now, by Lemmale 2.1 our rounding procedures maps these two vectors onto the same vector on the d For the error of each rounded estimate, we have
grid with probability
||0 0|| - 100 || + 110 0|| vd
A
+ 2
2
de we account for the 28 probability of failure across two independent
By choosing a d3/2 + +p- 28
algorithm executions and by choosing E' such that A <
2p-2 we have that
c(p-26) 26)
3/2 p 28
{(p 26)
1312 + 25 p - 26.
de
Furthermore, we satisfy
A
vdds
c(p 25)
E(d3/2 + 28)
Vd
2 2+2
22d3/2 + - 26)
22d3/2 + p- 28)
(dd3/2 + p 26)
S
Finally, we need find e to obtain our sample complexity. We have that
s' s(p 20)
2\
d3/2 + 25
2^E(p 28)
6
132 + p 25
Plugging s' into
100(B y)2
N
log
8/2
yields
100(B + (d3// + p- 20)²
2
25(B + +Y
2 8
log
log
SN
4p 26)
12=2(p- - 26)2
A.4 PROOF OF THEBOEM 3.2
Proof. Note that our assumptions do not change anything about the replicability of the estimator. As such it remains to prove the accuracy guarantee. We want to prove that under the stated assumptions it holds that
max x (w 8*)
Note that we can easily decompose the inner term via triangle inequality
x 0
x θ) + xx (0 0*)
20

---

Published as a conference paper at ICLR 2026
By data assumption and our Theorem 3.2, we can have that |x (w 8) - | - كلله 2
remains prove that |x" (0- 8*)l is small. We can use the core-set assumption to rewrite this term as follows
x" (0 04)
Σ T (0-0") 0*)
$ ||
Σ [xxx))x (0 -8-
$ vk
Σ (xx))((x) (0 0²))2
S vk V
E away
(x] (0 - 0²))²
At this point, it remains to show that Eeny (xx] (0 )²) is small. By definition, we know that
θ arg min Ex,pl [00x x y) 11]0 Since y = 0 x + c, we have that
E
(0- + 2ll11k S E (x 00- - - + 1110*112
= E [(x T 0" 0 x e) + =110-12=
Plugging this back we get
20 - 03) 03) S v1X|10011
2
Finally, choosing A
101100112 yields that x2 (0- (0-00) s 5\/2
21

---

Published as a conference paper at ICLR 2026
B PROOFS OF SECTION 3.2
B.1 PROOF OF THEOREM 3.3
Proof. To prove the Theorem, we begin by obtaining elementwise bound against the expected covariance matrix. Let
M-1
Σイ Σ
Σ
Xi.
Ezt Σ b. x
M
i=U
m==
By Hoeffding, union bound, and
||x||
S 1,
(-
M
Pr
U
Es²
21
S 2dl exp
S 8.
2t
Psisis
Thus, setting T = s//d, when we draw at least
2td
2d
8 log
S M
8
samples per distribution, we obtain with high probability that
- - E| S
Conditioned on success of estimation, two such estimates can differ by most by ||āa] - ||
S
2x' = A.
We are interested in the replicability and accuracy after rounding. By Lemma 2.1 we want that d d S p - 25. Furthermore we want for both estimates that
[E)sn(E)) Σ| S
Note that the eigenvalue clipping is simply the metric projection onto the PSD cone $ in the Hilbert space ($4, r)) that the original covariance lies in. Metric projections onto closed convex sets in Hilbert spaces are nonexpansive (i.e., 1-Lipschitz; see, e.g., (Bauschke Combettes (017]). In addition, since D E s our clipping operator would not change the true covariance matrix at all if applied and we have (E) E. As result, we have that
[PSD Σ
Σ||
|[Ipp Σ
IISD (E)] S I Σ||
Thus, it is sufficient to show that the rounded matrix before projection does not incur large error. We do this by decomposing as follows.
E - ElLF S -
E11 15 E11 S e.
d'
By setting a (d3 + 25) we account for the 28 probability of failure across two independent
E(p-28)
algorithm executions and by setting s' such that
where we account for the failure
(d3 + 25)
probability of two executions, we satisfy
d E(p 28)
(d p 262)
d
S p 28
a (d3 + 20-20 26)
d2
as well
A
de + E(p 28)
2 (d3 p - 26)
++2
d
E.
2
2dd + p 28) 2(d3 + - 28) 2 2d + p - 26)
The total sample complexity after plugging in s' comes
4td
20)
2
8td
2d
2p2 - 28)² log 8
- log
< M
=2
Accounting for / distributions finishes the proof.
22

---

Published as a conference paper at ICLR 2026
C PROOFS FOR SECTION 4.1
We provide additional proofs required to complete the proof in the main section here. The following is standard result from the literature that restate for completeness (see e.g. (Kakade 2003) for similar argument).
Lemma C.1. Let Th.0+1 == Ra(s, + Ph maxo Qh+1 (s, a) denote the standard Bellman operator. Assume that for all h, we have
112 - Thh-T@hh+ilee Se.
Then we have
Accuracy of Qu: Vh, 1|Qn- Qiil -H
Policy performance: for (s) == arg maxa Qn (s, a), then we have |V V-1 s 2/12s.
Proof. First Claim: By backward induction h. Base case: Starting from QH a) = O, we have (H,)Qu(s,a) = By our assumption, this implies that QH-1 S As result, we know that 1HH-l- Se
Inductive step: Our inductive hypothesis now states [1Q - Qi+ l| 5 (Il - h 1)s. We have
(n)s, (s) 1Q, -T. |T, Q (s, as)
S [ThQq (s)
< + (H- - h 1)2 (II - h)
Second Claim: Again by backward induction starting at 1.
Base case: For any
(s) - (s) (, (()
= (6)
-
+ (10
2 (1. - ( (0n
+ ()) (
2 25
The third equality here uses the fact that (s. (s)
R(s, a) and the first inequality uses the fact that within our estimated Q-function, we always pick the action with the largest Q-value when following our policy. The last step then uses the first claim.
Inductive step: Our induction hypothesis states that (s) - Vs++1()) 2 2( h H). We have that
V (s)
= Qn(s, (t (s)) (7(ss
= Qn(s, (8)) (7(s, (s)) (1) (x),,
E (viz Vi+ + (8, (s)) - (())
=
an (8)
2 -2(H 1)Hr (i (x)) Qn(s, 7M (8))
+ Qn, (((ss
2 2(H 1)HE 2(H h)e 2 -2(H He
C.I PROOF OF THEOREM 4.1
Proof. The proof builds on the result in Theorem 3.2 We make the following observations. In every
iteration, we call ridge regression procedure from Φ(st; an) to the target variable Ra(sh, an)
23

---

Published as a conference paper at ICLR 2026
max, Qu+1 (sh+1, a). At every step, we know that the Bayes optimal predictor is defined through
the Bellman operator as
E Sha1 Pa
(sn, an) + max Qh-1 a')] = (0n+1) (0) ((<
ax)-
Also, note that for all (s, a) the expected value of the per state-action pair noise ((sa) on the predictor
EEs Ess Ex [Rss a)) max," Qu+i(s',a)) (T((Q ())))) 0. We immediately have from Theorem 3.2 that for all h
max (o(sh, a (0)+ 5 Sh
with failure probability 8' and replicability parameter p'. We now need to union bound over the number of rounds and make sure our does not exceed in total. Since rounds, it suffices to choose 8' = = and p' p/ H. For accuracy, we choose e' = =2(2H²). As result, we have for all h H that [sQ, as) Th. (sp, an) an)llo I < with probability (=)) S е. Let us denote e the
running exactly H
1 1. By Lemma C.1 we immediately have that (** constant term in the cost of the ridge regression procedure. At this point, truth parameters of the optimal policy are bounded ||w S 2/H / via Proposition 2.1 It remains to show that norm the weights output by our algorithm are within a bounded ball B. Recall that we solving ridge regression problem of the form
note that the ground
Σ
(WT (8mm, Am (Ry (8m,h, 4m,h) + Va+1 (n+z((mm)+1))++ 1
M
MEM
Using optimality of WA we can compare to the zero vector. Since Wn. minimizes our objective we have
1
Σ
(wh (Smm, am,))) - (R am,)) + V(+4((mm,4z)) A| 1
M
ME
T (88m,, am.n) - (Rp (0. am, nn + Vn+1 (n+i( + +0 4H²
M MEM
which implies
2H
A A/ 12 < 4H² [/ 1
VT
From the proof of Theorem 3.2 we know that A
That means, it will suffice to choose
4h 1+|2
WA B= 4VEH110 8VivaH
(1)
Our total sample complexity is
H
iv(s, a s Σ
(1+v(s,a)MM
(8,a)
(s.a)ECa
8VTv/dH2
16
+ 211
d 11
H
H
k
log
c6(p - 28
8
10VkvaH' 2
c 16
d 118
H
H
k +
log
c0( 28)2
24

---

Published as a conference paper at ICLR 2026
Ci 13 2
122
S H
k+
log 8
(
26)2
This finishes the accuracy part of the proof.
remains to prove replicability. We prove replicability of the procedure by backward induction. Note which always replicable, so the base case holds. Suppose now that
that all values are initialized the estimate in round h + of Vi++ was replicable. Since the rewards are deterministic, and + was replicable, the label distribution of our ridge regressor the same round Vn, The estimate of w H/ is thus replicable with probability p/ H. Since there are only H rounds, the total procedure is replicable with probability p.
25

---

Published as a conference paper at ICLR 2026
D PROOF OF SECTION 4.2
D.1 PROOFS FOR THEOREM
In the following, let A Eielt) Eme(n] m am ( mo am,)) Al be the regularized Gram matrix used for ridge regression. Denote the ridge solution by
w (AA))
Σ
of ( h + Vh+ (8 m,h+))).
iE({]
mE[M]
Let Gh be the output of R- R-UC-CoV-Rst mati on in Line 21 of Algorithm and let
Σ
Mom o (8 "m,")"
M
EE [M]
noting that GH is simply an "unrounded" version of G That is, G would be the output of C-UC-CoV-BB Est imation in Li the rounding step of the algorithm was omitted. Similarly, and let A 0 A/ be Line of of Algorithm and let AA, 6% + be the "unrounded" version
of A/
To compress notation for partial trajectories and transitions, we write s' m.h to indicate ~ Pl a ). and write PA (-Is) to denote sampling a partial trajectory by executing #t for the remainder of the episode, starting from state at time h.
Lemma D.1 (Bounding inter-policy value differences). Let 5 > 0 and B E Odd)) (hiding logarith- mic dependence on 1/8). Let E = ( -willl be the Euclidian distance between the rounded ridge solution output by R-LSVI-UCB and w Then except with probability 8, for all S, E A, [H].
t t (T)
(k)(s wh) (%
E s
(s') (x = 3lo(s, a))a))))) 0())
Proof. We first observe that (ø(s, a), wh,) = (o(s,a), w/. - wh) + (o(s,)), w/) S (b(s, wh,)
so we will only need to show that ((b(s, a), w (s)
E (s') (s))l > () O(e).
P(...))
By assumption, for any policy æ, we can write Q?(-.)) (d(+))), w It follows that for any π we have
(w
wx) Σ
Σ
( n (P V (8 (8m,)+1)) A.w,
SE(T) mE(M]
Σ
Σ
(s S' ( + (ittl(mm41))
HE(0] mE[M]
Σ
(i (
(Vi+((('))) Aw
VE[4]
mE(M]]
Σ
Σ
p(sin aim ) (V/+1 (S (5m,)44))
E [W+z(s'))) Aw
- 8 s milh
sETd mE[M]
= Σ
Σ
( (n (1 (mm,
SE((] mE[M]
(V't - Di (s')) (s'))) Aw
I
To bound (Ø(s,a), a). w/, wf)., will separately bound
26

---

Published as a conference paper at ICLR 2026
1. (ø(s, a), ((A)) (o(s, a), (AA) Eiem EmELM (s (V ( (s m,1) Eg' [V h (s()))
(ő(s, a), (AA)- [m
n (E [ (6 V (s')
The first term can be bounded as in Jin et al. 2020), applying Sauchy-Schwarz with the inner product y) x y obtain
Ko(s, - wTY Allo(s,))lka))> | (A))
using Lemma B.2 Jin et al. (2020) to bound the norm || - 2/1 Vd. To bound the second term, we again observe
KØ(s, a), (AA)
Σ Σ
pl onnn ( (sm,411)
E (++1(1))1))
str m.
sE|t ME(M)
< (1(8s,))kAA))
Σ
Σ
VE(M] mE(M)
E 8 Pt m.A.
I (5 (s))l)aa))
so it suffices bound [|EE()] Emetar Φ( on (Vh+2
h+1 (5 h,41 - B (V ( ((l))))))
We again refer the reader to Jin et al. (2020), specifically in Section D.2 on Concentration of Self-Normalized Processes and Uniform Concentration over Value Functions.
Ignoring logarithmic dependence (on the covering number, 1/6, core set size, and regularizer penal- ties) and choosing <net xx Нyаx this gives us that 2k
Kéls, (0,
(( n h+1 (V/
(5m,h41)
IE
(8)+1
sP m
kE((] mE(M)
2kenet
s V2(HVV++
(10(s,
Finally, we bound the third term by rewriting
(AR))1 Σ
Wi E serPe
(Vita(s') - (s))(
mE(M]
=(A))-
Σ
(is' a' ( a'm f V5+)(5')- Vir
-ii)--vit (s')du
m MEMM
= -/106))
- - / Vhti(5")- - (i'
follows that (o(s, ()
Σ d(stn ann E. (V') - V
sloupl
me(ar]
min
= ((((, u), / Vh+z(66) - Vit (s)d
()) A(A))-1 / Vie Vi+z((')= - -Vii1 (s')dun(s'))
(V'= (s') (ò(s, a). >(A1) / (Viti(s)) (5)))))))
s'~P((1ssa)
27

---

Published as a conference paper at ICLR 2026
Finally, we can bound the rightmost inner product by
((0(, ()) / Vh+r(1") Vh+ (s') "duu (s'M)
A) ())kas))) f Vitt((5) [HVd(((ss.)))lo)>>
V (s+))')duuas (s))l()))>>
Putting everything together, we have that except with probability 6, for any x E IT, 8 E S, A [M]]
Kō(s, a), w/)) (T) - EE
[ (1+)((') [x)+((')]]
s'~P(-1(sa)
-ob(s, a), w/. - - d'mP(-1a,0)
E
(8'+ - (++)l
S Bllo(s ((l((s,))lk;;)) a)](a)))- + +())
For the purposes of proving the UCB property (Lemma D.4 and our regret bound (Lemma D.5). we will need the following lemma which bounds the Mahalanobis norm of a vector with respect to matrix in terms of the Mahalanobis norm the same vector with respect to small perturbation of A.
Lemma D.2. Let è be positive definite matrix with smallest eigenvalue at least X. Let E. be positive semidefinite matrix for which and |Ell| < E and let A such that A + E. Then for all E S. a...E. E A.
(1lo(s, a)llx (10(8, a))a-a S
E
A-c
Proof. It follows from the Neumann series for (1 + E) that
A-1 = (A + E)-1
-- ((AA)
A-1
(- EA -)
1=0
- EA 11
=
i=1
and so
( = ((s,a) (A- + Σ
)()(( (-EA-1)"j(ssa))
(EEA
1=1
= (((,,))
((s + as,
EA (s)
follows that
16(s, (- o(s, A A ((s < Σ [EA-))
28

---

Published as a conference paper at ICLR 2026
|||
A| -1
E
1=1
||
$ X ||
$ E
Using the fact that for non-negative a, bf la b) then Iva vbl I Vc. This also implies that
(|(((s;))l(()) 1(((s,))las)=111 1 X-
Lemma D.3. So long the rounding error incurred by --UC-CCv--sttmeee satisfies
All
xsa 28- for all 8, a A. h [H], [K], it holds that
1 2 ( e
3H
and
1 alaaa & 11((s,))l(as))-- + 33
Proof. Recalling that
1 Σ Σ
(s "n Al
M
E mE(M]
and
AA
(8 (6 "'m, ST AT
aE((] mE[M]
immediately follows that
((s (),,(,)))) s ((
and therefore
( ()( 2 |1, a)kkas)
By Lemma D.2 we have that
||
||l((s, (0(ssa))laag-1 [|o((, (1())-1) V A |
where = AA AA.- Then so long as ||E||
Aea 23 we have that
E X-
DH
We now prove that the UCB property holds for Algorithm That is, the predicted value of any state-action pair for the current policy is always greater than the true value of that state-action pair under any alternative policy, up to some small, controllable estimation error.
Lemma D.4 (Upper-confidence bound). Let on 1/8). Let [ww - will < &/ be the Euclidian distance between the rounded ridge solution output by R-LSVI-UCB and w Assume that for all E S, a E A, h E [H], E [K], it also holds that a)(s,a)lle,r)- 2 [ (()aa))((aa))-1 3H
and Ô(dH) (hiding logarithmic dependence
Then except with probability 5, for all S, [H] k [K], and all E II:
(1(8))) ()) 0())
29

---

Published as a conference paper at ICLR 2026
Proof. We will prove the lemma by induction on h. Assume that
(s,) 2 (7+1(s,0) - (H - ())
Then we can use Lemma D.1 to argue
(s, ()
a), w()) + Bl a))(()))))()))))11
(in w/) + Bl ())la))))) -
min(H,Q7
E
-vi+(())) by Lemma D.I
>'~((1))
(s, - (H h (+)
by induction
To see that the base case holds for h = - 1, we observe that from Lemma D.1
((((s,)), W - ( 8
+
and therefore (s, & (0(s. a), w + B) a) (((a))))> + O We defined
QH=1(s,a)= = (0(s. a), WH wH + 3110( a) (()l)))))(()))).-.))))))) and so it follows that
(8, a) (% - -
In order to bound the contribution of the UCB bonus term to the regret of our learner, we first bound the sum of the Mahalanobis norms
ΣE Σ
| atth ((a))
AETT] HE]H ME[M]
under the "unrounded" matrices G We then use Lemma D.2 show that the rounding to ensure replicability does not increase the overall regret too much, obtaining a bound on
Σ ΣΣN
Σ
| a k
EE[T] [E( mE[M]
the actual contribution the regret from the bonus term. Lemma D.5 (UCB regret).
T+T [ o mil S MH T(1 1/A)dlo
ΣΣ Σ (E[T] KE[H] ME[M]
Proof. We observe that for any / [T], h E [H], E S, E A, that because Amin (G)) 2 X,
| a) () X || a)ll S +
follows from In(1 + x) < x (1+ In(1 + x) for x 2 then, that
In(1 + lo(s, (|(( s lo(s, (((s)))l(())-
+ (1 + ||o(s, a) a)
From the definition of G the matrix determinant lemma, and the fact that det + X) 2 (x() for positive semidefinite X, we have that
dct(G dot((A++
Σ
Σ
M
se[t+1] mE[ad]
= =det( + M
Σ o( a ( (mm om, )
mE[M]]
30

---

Published as a conference paper at ICLR 2026
(Ch)
Σ
mE(M]
2 det(G))(1
Σ
M
MEIM
It follows that
det(C (G+)
In + 1
Σ
S In
M
det
MEIM
Then
E E E
( a (iah)
M
AE[T] WE HJ MElM!
(1+11/A)
E
E
I1 M
Σ
(1 m. omthh)l)
(E[T] HE
MEIM]
In det (et
(1+1 Σ
Σ
AE[T] NET
det(
= (1+1
Σ In
det
hE[H]
(A + T)
(1+1
Σ he(H]
det(CGg)
X + T
(1 + 1/A))/m
A
where the third inequality follows from the fact that
det(GT)) s (A+ Md
Σ Σ
|0(5 (2))))) s (A+
(E[T] ME[M]
Then applying Cauchy-Schwarz to bound the actual sums of the norms, rather than the quadratic forms, we have
A+1
Σ Σ tE(T] mE[M] KE(H)
Σ
l
+ othl S MH 1(1+1//)+ m.
A
Using Lemma D.5 and Lemma D.3 we bound the real contribution of the bonus term to the overall regret, accounting for the error induced by rounding for replicability. Corollary D.I.
(++
Σ
Σ
[
++1 + (tt 2MH T(1 1/A)dlo
A
(E[TT] (E(N) MM[
Proof. Lemma D.2 gives us
ΣΣD Σ tE|Ti KE[H mE(M]
[ ttllkay is
Σ Σ
Σ
| attil (G))) + V
tE|T mE[M]] he[H]
so long as we ensure
Xd log( A+T
E <
2T
31

---

Published as a conference paper at ICLR 2026
it holds that
A+1 T
Σ ΣEM DE[T) NE[H] mE[M]
Σ
m a - & 2MH T(1 1/2)d/
A
We now use Lemma D.I and Lemma D.4 to prove Theorem 4.2
Proof. Let ITf denote the set of policies output at the end of the algorithm. We want to show that, except with probability 6, for all π E II
E [~[
2 V -(E).
Assume in the following that for all / E T h E [H] we have l| w s A.. and for all E S,
a E A, we have [ a) (1 - |lo(s, a) (A.) v As-
From Lemma D.4 we have that for every E [7]. V be enough to bound
V = VT V +(HA.). and so will
Σ EE(T]
=
Σ
E
18 (80))
(0: (5)))
samag
EE
Σ Σ
m0 - Qi(o a' + err
TM
1E[2] ME[M]
where
crr = Σ Σ
E sprug
(s0 #b()))
(su, (50)) @i(smmo:amn,))) (s mm am.o)
TE mE [M]
s H 2T (1/()
except with probability 6.
We begin by bounding
Σ Σ Ci (m. (s o)
E [7j mE(M)
Applying Lemma D.I to #1, have that except with probability 5
a), wh) (s) s'MP(ssa))
( (s') Vh (s') Slllss + 0(Aw)
and therefore
(s'm amr.h) Qh (s amo,h) (s'+ (s')+ Bl (i
s'ape
B1l10 (m +O(Am)
V Vh (sm,
(Vtr(s') - Vh+1
s'aPp
- -VVit1 (i + 311 Mlan
+ 811 am)))) + O(Aw)
which gives
Σ> Σ @blmmm. @b(mm,ooammo)
KE[T] me(
32

---

Published as a conference paper at ICLR 2026
Σ
Σ
Σ
(V+) V/+i(660] (Vita (i+z((mm)42))
(T m he(m) s'r m.hh
Σ
Σ
Bllo(s (MAA)))
TE(T] mE(M ME(m]
+ 3 ( hn
i ((a + 0(Aw)
Σ
E (V'+('') - ( (Vi+ (5 (
po Pr
1E|2 [M] he[H]
mi.h
Σ :E|T ME[M] he[m]
Σ
28110(s a am 1 0 ( O(Aw),
where the last inequality follows from Lemma
D.3 From Lemma
D.5 it follows that
ΣΣ
do mm.
KE[7] [M
Σ Σ
Σ
E
(+))( (
Vi
tE[2] mE[M]] bE(H)
(A+1) + 43MH 1(14//))
+ +0 AvAA X +
remains bound EiErTy EmE[M ΣnE a' We observe that the sum of a is the sum of deviations of Vi (mm Vi from their expectation Eg'-p' [V (5') (s))( and represents Martingale sequence with every lam - 2/1 bounded r.v.'. Therefore
Pr E
Σ
a'm > 7| S exp( 2TMH
(E[T] mE[M] AE(H)
and then
Pr Σ
dim, H
5
(E[T] ME(M] ME(H]
Putting everything together, we have that
1 7'
Σ
TM Σ Σ
d'm.)) Q dm err
1E[T]
ET
ME(M]
(H / log ( 4BMH
T(1 + +1A)ddlog' ATT)
TM
-TMHO BVAA Aw) H 2T log (og(1/)))
2 1ng(1/8)
13H VT
(1 1/A)d log( A+ HO BvA. A + H TM
20g((1/8)
TM
except with probability 25.
Then taking T Ô H log(1/8)
32H1d A=2
[ [PHHddog(111) ( Art
and ensuring Aa E O(( (()
Ma²
and A. O we have that
1
Σ
V
q
9
(E[T]
except with probability 8.
33

---

Published as a conference paper at ICLR 2026
D.2 REPLICABILITY PROOF FOR THEOREM 4.2
Proof. We prove that Alg. 5 is p-replicable by strong induction over rounds. Let (1(()) and #*((2) be the policies returned at the end of round by two independent executions that share the same internal randomness.
Base case (t 0): Initialization is deterministic, hence #0.(1) #0.(2) with probability
Inductive step: For f 1}, assume E (*((1)) #* Vi k} holds. Conditioned on Ek. both runs collect data in round k+1 using the same mixture over the policies (#" [f'...... #*) (the mixture indices are fixed by the shared internal randomness). For each step h [H], this
induces the same distribution D,,, over design/label pairs (Ø(s). a,), yhh in both runs, where yn is the reward-plus-valuer target with the rounded bonus. Within each round, the M trajectories (and their step-h samples) are i.i.d.; across rounds, fresh trajectories are drawn, so data blocks are independent once the policy sequence is fixed by (i.e., under Eg)-
By Theorem 3.1 with per-call parameter Prág and target Aw and with M large enough as specified there. the rounded ridge outputs coineide: Wi (+),(11) W 1,), except with probability at most Prdg. By Theorem 3.3 with per-call parameter PA and target AA and with the corresponding M, the rounded covariances also coincide: (k++1((1) G (k+1.(22 (hence A coincide) except with probability at most PA- The algorithm sets Pidg PA K) and chooses M to satisfy the sample-size requirements of Thcorems 3.1 and 3.3 for the targets A. and ÅĄ used in the accuracy analysis.
When both estimators succeed for all h E [H] the Q-estimates and bonuses are identical at every state-action pair, and the greedy action selection with deterministic tie- breaking yields the same **+1 in both runs. Taking Pedg = PA = p/(4HK) and union- mnion-bounding over the 2H estimator calls in round k++ shows
Pr pr(a)+ # **+1.(2) Ex] S f.
Unconditioning and using the inductive hypothesis yields
Pr(ak+l(( o ** *++1,(21 < Er| + & <
kg R +
+
(k-1)e
K
By induction, after T' rounds we have Pr(s7.(1) * *T.(2)] < i..., Alg. 5 is p-replicable. Finally. each round uses fresh trajectories; conditioned on &g, the batch at round k++1 1 is i.i.d. from D/h the prerequisites of Theorems 3.1 and hold at every call.
E HYPERPARAMETERS
For our neural network experiments, we use the implementation of PQN available via CleanRL. (Huang al., 2022). We report the hyperparameters that we used in Table [ We found that from the original implementation we need to make minor modifications that do not lead to decrease in performance of the baseline get competitive performance with quantization. Precisely, we change the default exploration rate from 0.1 to 0.25 for MsPacman and to 0.3 for Breakout because quantization leads to lower policy churn which has been shown to increase exploration (Schaul et al., (002)). This an intended side effect. While one might be tempted to argue that exploration from churn good, it is uncontrolled as we do not know how our networks change. Instead, quantization leads to lower churn and the modeler can control the rate of exploration directly. Furthermore, to use decoupled weight decay (Loshchilov & Hutter 2019). We use a weight decay of 0.1 for MsPacman and 0.2 for Breakout. All outputs are rounded multiple of 0.4 during quantization.
change the optimizer
34

---

Published as a conference paper at ICLR 2026
Table 1: Hyperparameters for PQN
optimizer
Adam
total timesteps
10e6
learning_rai
2.5e
num envs
num steps
128
anneal_hh Ir
True
0.99
num mom_mini___e batches bathhe
update_epochi
max grad norm
10.0
start c
1.0
end_e
0.01
exploration ooaatttioo_fraction
0.3
lambda
0.65
F COMPUTATIONAL RESOURCES
Our code is written in Python and uses PyTTrcc for deep learning. Our algorithms for CartPole can be run on household-grade computers using using central processing units (CPUs). For deep learning experiments, we had access to a cluster with various types of graphical processing units (GPUs), including Nvidia RTX3090 and Nvidia A6000 GPUs. Running one seed of the fitted Q-iteration algorithm less than minute while running one PQN experiment takes around 2.5 hours per seed.
G LARGE LANGUAGE MODEL USAGE
During the development of the paper, we made use of Large Language Models (LLMs) in two ways. First, we used it to obtain sentence word suggestions polish text. Second, we used LLMs search engine to find related literature and work to specific theorem statements.
35


Reviews:
[{"review_id": "dzcYYYgzT2", "reviewer": "Reviewer_jZdx", "summary": "This paper develops new replicable algorithms for reinforcement learning in the linear function approximation regime. There have been two prior works on replicable reinforcement learning and one concurrent work. Prior works operate in the setting where the number of actions and state spaces are bounded (and small). In contrast, the present work handles the case where the number of state and action spaces are infinite. However, it makes a linear feature representation of state-action pairs, which is also widely studied in reinforcement learning. In this model, they develop a replicable algorithm for reinforcement learning. This algorithm relies on two fundamental replicable primitives: (1) ridge regression algorithm and (2) uncentered covariance estimation algorithm. The covariance estimation algorithm appears to be novel, while the ridge regression algorithm is not completely novel: it existed for fixed design settings, and this paper extends it to the i.i.d. design setting when the distribution of covariates is bounded. Finally, the authors evaluate their algorithms experimentally and show that they lead to more consistent policies.", "questions": "Minor issues with Theorem 3.1: The phrase \"from which we draw $M$ independent samples totalling $N$\" is unclear. Perhaps it meant \"We draw $M$ independent samples from each distribution, totaling $N = M * t$.\" In the definition of $\\theta^*$, which distribution is the expectation taken over?\n\n---\n\nMinor Typos/Grammatical errors\n1. Algorithm 2: “paramter”\n1. Malahanobis → Mahalanobis\n1. Related works: intrduced\n1. Section 5.2: unforseen\n1. Below theorem 3.1: staightforward\n1. Above Section 5: \n    1. inpractice → in practice\n    1. meticuluous → meticulous \n1. Section 5.1 end of first para has a repeated “the”\n1. Above Section 6: Tegularization → Regularization\n1. Punctuation/hyphenation missing at various places, e.g., in paragraph 2 of the paper “algorithms internal randomness” should be “algorithm’s internal randomness”\n1. Section F: house-hold grade → household-grade\n1. Section G: “sentence of word” → “sentence or word” also, in this section, I do not understand what “and work to specific theorem statements.” means.\n1. Many of the proofs throughout the appendix use $E$ instead of $\\mathbb{E}$ for denoting expectation.\n\nFurther minor suggestions \n1. The “i.e.” before Proposition 2.1 is unusual.\n1. Spurious space at the period at the end of proposition 2.1.\n1. $\\theta^*$ is mentioned in the statement of Theorem 3.2 but only defined in the statement of Theorem 3.1", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Replicability is an interesting and valuable property of algorithms worth having. The paper presents a new replicable algorithm that operates the regime with a large number of state and action pairs where existing methods do not work. As such, I believe it's well in scope for ICLR, and studies an interesting topic.", "weaknesses": "I found this paper very difficult to read.\n\nAt the highest level, there are two main issues. First, the novelty of the proof ideas compared to prior work in replicability and replicable RL is unclear. Second, the paper lacks comparison with existing RL algorithms in the linear regime—it's unclear whether this algorithm modifies existing approaches by using replicable subroutines or requires more fundamental changes.\n\nAt a lower level, the very large polynomial factors in the RL results are puzzling. Can these be improved, or are they necessary? While the simulations are a nice addition. However, then I am confused why the computation of the specific polynomial factors is necessary/important: if the subroutines are replicable, shouldn't the RL algorithm automatically be replicable? Why compute the overall sample complexity? I would have felt better about the large polynomial factors if there were concrete reasons why the polynomial dependences could not be improved (easily). A proof overview here would have been nice, but as far as I see, there were no proof overviews in the main body at least.\n\nRegarding readability issues:\nThe discussion before Theorem 3.1 is a bit confusing. I understand that the objective is strongly convex and hence the closeness in function values is proportional to the closeness in parameters space. But then the discussion of what is needed in the proof is not clear.", "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": "12WAA3m5Ft", "reviewer": "Reviewer_aY1c", "summary": "The paper studies establishing replicability of RL algorithm. By replicability, it means that the algorithm has the same output on arbitrary input with high probability. The authors first derive a replicability result on ridge regression and covariance estimation, which extends the result of randomized rounding result from Impagliazzo et al., 2022. Then, these tools are utilized for the analysis of replicability result of offline RL and online with exploration in the linear MDP case, which requires ridge regression and covariance estimation steps.", "questions": "1.  The author could provide more comments on why the dependency on $\\epsilon$ is high in Theorem 4.1 or 4.2.\n\n\n2. As mentioned in the weakness, where does the large gap compared to the tabular case(Hopkins et al., 2025) come from?\n\n\n3. Can the authors provide more detailed comparison on how worse the bound is compaed to those of tabular cases?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The authors tackle an important issue of reproducibility of RL algorithms in theoretical sense. This is important as many deep RL algorithms are not easy to reproduce in practice.\n\n2. This seems to be the first result for replicability in linear MDP setting. The authors manage to connect the replicability result in supervised learning with theoretical RL in linear MDP literature.\n\n3. The theoretical results are complemented by experimental results to show that there are room for  improvement in the sample complexity result.", "weaknesses": "1. While the theoretical results are new, the novelty of the algorithm or the proof is not clearly explained : 1) Section 3.1 does not clearly explain where the novelty of the algorithm lies compared with Esfandiari et al., 2023a; 2)The use of a core-set appears closely aligned with ideas already established in the literature (Lattimore and Szepesvári).\n\n2. The overall bound is not tight compared to that of Esfandiari et al., 2023a or Hopkins et al., 2025. The authors argue that this comes at the expense of generality. However, the rationale behind this tradeoff is not entirely convincing.  \n\n3. Algorithm 2 requires additional projection  of the estimated covariance matrix on to the cone after rounding is executed.", "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": "YDTekWQwfd", "reviewer": "Reviewer_Byb9", "summary": "This paper studies replicability in RL in the setting of linear function approximation, building upon the seminal work of Impagliazzo et al (2022) and other works that explored replicability in bandits and tabular RL. In a nutshell, replicability asks for RL algorithms that output the same policy when executed twice in the same MDP environment, under shared internal randomness. This work provides the first replicable algorithms for RL in the linear function approximation setting. En route to that task the authors first develop two new, efficient, and replicable algorithms for replicable random design regression and replicable uncentered covariance estimation. They also provide empirical evaluation of their results.", "questions": "- I'm a bit confused about the discussion around Theorem 3.1, and some notation in it. What does $E_{D_{[t]}^M}[(\\theta^\\top x - y)^2 + \\lambda ||\\theta||^2]$ mean? In particular, since $D_{[t]}$ is a sequence of distributions, which one of them are $(x,y)$ drawn from? I might be missing something obvious. Also, I didn't understand why the discussion around the algorithm is needed. Since one can show that the estimate $\\hat w$ from the vanilla ridge-regression is close to the optimal value (as stated in the theorem), why doesn't replicability follow from the (relatively) standard techniques of saying that across two executions $\\hat w_1, \\hat w_2$ will be close to each other (since they are close to $\\theta^*$), and then apply the rounding?\n\n- Why does Algorithm 4 need to have access to a coreset? Is that part of the standard description of RL with linear function approximation in the non-replicable setting?\n\n- As a general comment, I would appreciate it if you could help me understand the results and the necessity of the ideas and techniques in section 3 better. I'm happy to adjust my score.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This paper builds upon a line of work that has received interest and studies a natural problem.\n\n- Some first theoretical bounds are established in this setting, potentially inspiring future work.", "weaknesses": "- I found the writing (especially in section 3) to be a bit confusing.\n\n- The results in section 3 seem to rely on fairly standard algorithmic templates of estimating quantities from samples at some sufficiently high accuracy and then rounding; the bounds also seem to be (fairly) suboptimal.\n\n- The situation is similar for the results in section 4; the replicability arguments are fairly standard (given the results of the previous section) and the sample complexity bounds are unsatisfactory.", "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": "omXE4nSlmK", "reviewer": "Reviewer_2UsG", "summary": "This paper addresses the critical challenge of replicability in reinforcement learning, where algorithms are notoriously unstable, especially when combined with function approximation[lines: 1243, 1253, 1254].The authors extend the formal, \"exact\" notion of replicability—where an algorithm must produce identical outputs from different data samples given the same internal randomness [lines: 1403, 1404]from the tabular setting [lines: 1246, 1270] to the more practical domain of linear function approximation[lines: 1247, 1323].\n\nTo achieve this, the paper makes several key contributions:\n1. It first develops two novel, provably replicable statistical tools: **R-Ridge-Regression** for the random design setting [lines: 1248, 1516] and **R-UC-Cov-Estimation** for uncentered covariance matrices[lines: 1248, 1616]. Both are of independent interest and are built upon randomized rounding techniques [lines: 1414, 1516, 1618].\n2.  Using these tools, the paper presents the **first provably efficient and replicable RL algorithms for linear MDPs**. This includes **R-LSVI** for the generative model setting [lines: 1249, 1647] and **R-LSVI-UCB** for the more challenging episodic exploration setting [lines: 1249, 1728].\n3.  The theoretical results are supported by experiments. First, on CartPole with random Fourier features, the authors show their method achieves replicability with far fewer samples than the loose theoretical bounds suggest [lines: 1799, 1805, 1843]. Second, they apply the *idea* of their work (quantization) to deep RL (PQN on Atari) and demonstrate that it leads to significantly higher policy agreement across random seeds without compromising performance [lines: 1800, 1869, 1915, 1916].\n\nThe paper's theoretical claims are well-supported and appear sound. The authors properly adopt the formal replicability framework from Impagliazzo et al. (2022) [lines: 1401, 1403] and build upon the standard analysis of linear MDPs from Jin et al. (2020). The core of the contribution lies in the novel replicable estimators for ridge regression and covariance. The proofs for these tools correctly use properties of strong convexity and concentration bounds to show that the estimators from two different datasets will be close enough to be mapped to the same rounded value [lines: 1517, 1525, 2759-2763]. The subsequent RL algorithm proofs correctly follow by induction, carefully accounting for the error propagation from batching and rounding [lines: 3747, 3757, 3887]. The experimental methodology is clear, and the results convincingly support the paper's claims.\n\nThe paper is exceptionally well-written, clear, and logically structured. It begins with a strong motivation for the problem, clearly defines the technical preliminaries (linear MDPs and the specific replicability definition) [lines: 1331-1436], and then intelligently builds its contributions. The decision to first introduce the replicable statistical \"tools\" (regression and covariance) in a standalone section [line: 1444] before applying them to the more complex RL setting is highly effective for clarity. The experiments are well-described, and the figures clearly visualize the trade-offs between performance and policy agreement [lines: 1809, 1866].\n\nThe contribution is original and significant. The lack of replicability is a major, well-documented practical problem in RL [lines: 1243, 1252], and this paper is the first to provide a *formal, theoretical* solution in the non-tabular setting of linear function approximation [lines: 1247, 1324]. The new algorithms, R-Ridge-Regression (for random designs) [line: 1515] and R-UC-Cov-Estimation [line: 1616], are novel contributions in their own right and may have applications beyond RL [line: 1447]. This work successfully bridges a major gap and opens up a new and important line of research into provably stable and reliable RL.", "questions": "1.  The sample complexity bounds are the main limitation. The authors mention concurrent work (Hopkins et al., 2025) achieving low overhead for replicability in the *tabular* setting [lines: 1959, 1960]. What are the primary theoretical bottlenecks that prevent a similar low-overhead result in the linear setting? Is the high cost mainly from the R-Ridge-Regression, the R-UC-Cov-Estimation, or the complex interaction between the UCB bonus and the rounding error?\n2.  In the deep RL experiments, the authors chose to quantize the final Q-values [lines: 1869, 1870], whereas the theory for the linear setting involves rounding the *weights* (via R-Hypergrid-Rounding on the output of the regressor) [lines: 1516, 1443]. Could you elaborate on this design choice? Was rounding the neural network weights directly attempted, and if so, what challenges (e.g., training instability) did it present?\n3.  Figure 2 shows that for PQN, regularization alone did not significantly improve policy agreement, but quantization did [lines: 1912, 1916]. This is a very interesting result. Does this imply that the instability in deep RL is less about agents converging to different *local minima* (which regularization might help smooth) and more about the high sensitivity of continuous Q-value representations to small variations in data?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* **Novelty and Significance:** This is the first work to provide provably replicable algorithms for RL with linear function approximation [lines: 1247, 1324]. It tackles the well-known \"replication crisis\" in RL [line: 1243] with theoretical rigor, moving beyond the tabular setting.\n* **New Replicable Estimators:** The paper develops R-Ridge-Regression and R-UC-Cov-Estimation, two new statistical estimators with replicability guarantees [lines: 1248, 1445, 1446]. The extension of replicable regression to the *random design* setting [line: 1515] (as opposed to fixed design) is a key tool that enables the subsequent RL results.\n* **Comprehensive Theoretical Results:** The paper provides a complete theoretical treatment, developing replicable algorithms for both the generative model setting (R-LSVI with core set) [line: 1647] and the more difficult episodic exploration setting (R-LSVI-UCB) [line: 1728].\n* **Strong Experimental Validation:** The authors provide two sets of experiments:\n    1.  A direct validation of the theory on CartPole, which encouragingly shows that replicability is achieved with far fewer samples than the theoretical bounds require [lines: 1804, 1843].\n    2.  A practical extension to deep RL (Atari), showing the core idea of quantization inspired by the theory leads to measurably more consistent policies (higher action agreement) without a loss in performance [lines: 1800, 1915, 1916].", "weaknesses": "While this is a strong paper, its weaknesses are primarily the necessary trade-offs for achieving such a strong replicability guarantee.\n\n1.  **High Sample Complexity:** The most notable weakness, which the authors acknowledge, is the very high sample complexity of the provable algorithms [line: 1733]. For example, the bound for R-LSVI-UCB has high-polynomial dependencies on $d$ and $H$ (e.g., $d^{56}H^{62}$), making the *theoretical* bounds impractical, even if the empirical results are much better.\n2.  **Gap Between Linear Theory and Deep RL:** The theory is confined to linear MDPs, which assumes a good feature representation is already available [lines: 1734, 1794]. The paper does not address the (very hard) problem of how to *learn* these features in a replicable way [lines: 1797, 1956]. The deep RL experiment, while promising, is a heuristic (quantizing Q-values, not weights [lines: 1869, 1870]) and does not have the same theoretical guarantees.\n3.  **Core Set Assumption:** The generative model algorithm (R-LSVI) relies on access to a core set of state-action pairs [lines: 1701, 1704]. This is a standard assumption in related literature but is a strong one that sidesteps the exploration problem, which is (fairly) handled separately in the R-LSVI-UCB algorithm.", "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)