Replicable Reinforcement Learning
Authors: ERIC EATON
Marcel Hussing
Michael Kearns
Jessica Sorrell
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning
Learning Theory
Replicability
Reproducibility
TL;DR: We initiate the study of replicable reinforcement learning and provide two novel, provably replicable algorithms.

Abstract: The replicability crisis in the social, behavioral, and data sciences has led to the formulation of algorithm frameworks for replicability --- i.e., a requirement that an algorithm produce identical outputs (with high probability) when run on two different samples from the same underlying distribution. While still in its infancy, provably replicable algorithms have been developed for many fundamental tasks in machine learning and statistics, including statistical query learning, the heavy hitters problem, and distribution testing. In this work we initiate the study of replicable reinforcement learning, providing a provably replicable algorithm for parallel value iteration, and a provably replicable version of R-Max in the episodic setting. These are the first formal replicability results for control problems, which present different challenges for replication than batch learning settings.

Replicable Reinforcement Learning
Eric Eaton University of Pennsylvania Philadelphia, PA 19104 eeatonEseas upenn edu
Marcel Hussing University of Pennsylvania Philadelphia, PA 19104 mhussing@seas. upenn edu
Michael Kearns University of Pennsylvania Philadelphia, PA 19104 mkearnstcis upenn edu
Jessica Sorrell
University of Pennsylvania Philadelphia, PA 19104 jsorrelléseas upenn edu
Abstract
The replicability crisis in the social, behavioral, and data sciences has led the formulation of algorithm frameworks for replicability - i.e., requirement that an algorithm produce identical outputs (with high probability) when run on two different samples from the same underlying distribution. While still in its infancy, provably replicable algorithms have been developed for many fundamental tasks machine learning and statisties, including statistical query learning, the heavy hitters problem, and distribution testing. In this work we initiate the study replicable reinforcement learning, providing a provably replicable algorithm for parallel value iteration, and a provably replicable version of R-max the episodic setting. These the first formal replicability results for control problems, which present different challenges for replication than batch learning settings.
Introduction
The growing prominence of machine learning (ML) and its widespread adoption across industries underscore the need for replicable research [Wagstaff 2012 Pineau et al. 2021 Many scientific fields have suffered from this same inability reproduce the results of published studies (Begley) and Ellis
2012). Replicability in ML requires not only the ability to reproduce published results Wagstaff 2012), as may be partially addressed by sharing code and data (Stodden al., 2014], but also consistency in the results obtained from successive deployments of an ML algorithm in the same environment. However, the inherent variability and randomness present in ML pose challenges to achieving replicability, as these factors may cause significant variations in results.
Building upon foundations of algorithmic stability (Bousquet and Elisseeff 2002 recent work in learning theory has established rigorous definitions for the study of supervised learning Impagliazzo et al. 2022] and bandit algorithms (Esfandiari et al. 2023a that are provably replicable, meaning that algorithms produce identical outputs (with high probability) when executed on distinct data samples from the same underlying distribution. However, these results have not been extended to the study of control problems such as reinforcement learning (RL), that have long been known suffer from stability issues [White and Eldeib 1994 Mannor al.) 2004 Islam et al. 2017 Henderson et al.) 2018). These stability issues have already sparked research into robustness for control problems including RL [Khalil et al.) 1996 Nilim and Ghaoui] 2005 Iyengar 2005 Non- deterministic environments and evaluation benchmarks, the randomness of the exploration process, and the sequential interaction of RL agent with the environment all complicate the ability make RL replicable. Our work is orthogonal to that of the robustness literature and our goal is not to reduce
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the effect of these inherent characteristics. such as by decreasing the amount of exploration that an agent performs, but develop replicable RL algorithms that support these characteristics.
Toward this goal, we initiate the study of replicable RI. and develop the first set of RI algorithms that are provably replicable. We contend that the fundamental theoretical study of replicability in RL might advance our understanding of the aspects of RL algorithms that make replicability hard. In this work, we put on similar lens as Impagliazzo et al. [2022] and consider replicability as an algorithmic property that can be achieved simul limuluouyussyy with exploration and exploitation. First, we show that possible to obtain a near-optimal, replicable policy given sufficiently many samples from every state in the environment. This notion is then naturally extended to replicable exploration.
Our contributions can be summarized as follows. We provide two novel and efficient algorithms to
show that stochastic, sample-based value iteration can be done replicably and replicably explore the space of an MDP while also finding an optimal policy.
We experimentally validate that our algorithms require much fewer samples than theory suggests.
2 Preliminaries
2.1 Reinforcement learning
We consider the problem of solving a discounted Markov decision process (MDP) M (S,A, P. μu with state space S, action space A, reward function R, transition kernel P. discount factor 7, and initial state distribution jt. We assume that the size of the state space [S] and number of possible actions |A|] are finite and not too large. Further, we assume that the rewards for every state-action pair are deterministic, bounded, and known. Relaxing assumptions function might not necessarily seem straightforward in our goal of replicable RL, as the stochastic reward would need to be made replicable. However, the case can be handled by our algorithms with minor modifications and only constant factor overhead. The goal is to find a policy æ : S + A that maximizes the cumulative discounted reward Jn, Σk=n > k-- R&(s, a). We use the typical definitions of the value and Q-value functions for the expected cumulative discounted return from a state or state-action pair, respectively:
P.y.
the reward
V (s) = E J s/2 =
Qx(s,) = E [M s,an = al
R.P
To show the various difficulties that come from trying to achieve replicability in RL, we consider two different settings to examine various components of the problem.
Parallel sampling setting First, we ask whether it is even possible to obtain a replicable policy from empirical samples without considering the challenges of exploration. For this, we can adopt the setting of generative models G.,, or more precisely, the parallel sampling setting. In the parallel sampling model, first introduced by Kearns and Singh [1998a]. one has access to a parallel generative sampling subroutine M)) A single call to PS PS(GM) will return. for every state-action pair (s, a) E S A, a randomly sampled next state E S drawn from P(s'|s, (s/ a). The key advantage that this model separates learning from the quality of the exploration procedure.
Definition 2.1 (Generative model). Let M denote an arbitrary MDP. Then generative model Gys(ss a)) is a randomized algorithu that, given a state-action pair (s, E S x A. outputs a deterministic reward R(s, a) and next state s' sampled from P(-|s,a) a)..
Definition 2.2 (Parallel sampling). Let M denote arbitrary MDP. Then call to the parallel sampling subroutine (S(G returns exactly one sample s ~ Gm(((B az)) for every state-action pair (st a;) in S x A of M using a generative model.
Episodic setting The second setting we consider one in which an algorithm does have to explore the MDP before it can obtain an optimal policy. More precisely, we consider an episodic setting where, in every episode e E 21, .... E), the agent starts environment for fixed amount of time H. At any step h E [1, H). the agent is in some state sh. selects an action db, receives a reward ra and transitions to a new state 81+1- Gathering a trajectory (No, do, To, 8H, an, rT) of states, actions and rewards under policy ι can be thought of as draw from a distribution 7 ~ (T). We will omit the sub-and superscripts when clear from context. For consistency with the remaining analysis, work with disccounte version of the problem.
position so ~ 1 and interacts with the

---

2.2 Replicability
We build on the recent framework by Impaglazzo et al. [202], which considers replicability as property of randomized algorithms that take as input a dataset sampled i.i.d. from arbitrary distribution. They consider an algorithm to be replicable if, on two runs in which its internal randomness is fixed and its input data is resampled, it outputs the same result with high probability:
Definition 2.3 (Replicability). Fix a domain X and target replicability parameter P E (0. 1). randomized algorithm A X - 3 is p-replicable if for all distributions D over X, randomizing over the internal randomness r of and choice of samples S1, S2, each of size n drawn i.i.d. from D. we have: ,t. (S( o A(22r)) P
Several key tools that were introduced by Impagliazzo et al. [2022] will prove useful or yield inspiration for the algorithms developed in this work. One of the key observations is that many of the computations in RL can be phrased as statistical queries, defined as follows:
Definition 2.4 (Statistical query, [Kearns 1998). Fix distribution D over X and accuracy parameter a E (0, 1). A statistical query is a function @ X + [0, and a mechanism M answers with tolerance on distribution D if a M satisfies E [EI~ [o]]]] + a
We will make direct use of the replicable algorithm for answering statistical queries by Impagliazzo ctt al. [2022] which will be useful to obtain replicable estimates of various measurements such as transition probabilities. We will refer to the replicable statistical query procedure rSTAT. We note that Impagliazzo et al. [2022] also proves a lower-bound on the sample complexity required for replicable statistical queries, showing that the results below essentially tight.
Theorem 2.1 (Replicable statistical queries, Impaghazzo et al. (2022)). There p-replicable algorithu rSTAT such that for any distribution D over X, replicability parameter E (0, 1), accuracy parameter a (0, failure parameter 8 E Op),, and query Φ X + [0, 1], letting be
sample of O
log(1/5)
elements drawn i...d. from D, we have that a ISTAT (8,
(p- a
satisfies E [E->D [[])) + aj except with probability at most d over the samples S.
At very high level, rSTAT uses its sample empirically estimate the expected value of the statistical query on the target distribution. then uses its internal randomness to pick an evenly-spaced set of canonical representatives from the [0, I] interval, and returns whichever canonical representative is closest to the empirical estimate. We note that the algorithm [mpagliazzo et al. [2022] for replicably answering statistical queries is not only sample efficient, but also computationally efficient, as it has runtime polynomial in 1/a, 1/p, and (16(1
3 Replicable reinforcement learning
To define replicability for the RL setting, we can adapt Definition 2.3 more or less exactly. The question that arises is which of the many RL objects should be made replicable? We separate the difficulty of replicability into three levels: replicability of the MDP, the value function, and the policy. Since these objects carry different amounts of information [Farahmand 2011], the following relationships can be established.
If we are able to replicably (and accurately) estimate an MDP, we can always replicably compute an (optimal) value function using standard techniques on our estimates, and from replicable value functions we can obtain the corresponding policies. Note that the inverse is not true as we lose information when going from MDP to value function and then policy. As a result, we expect that replicable estimation of MDPs is the hardest setting in stochastic RL, followed by replicable value function, and then policy estimation.
For replicability of control problems, a sensible measure to ask for is the production of identical policies, which are the ultimate object of primary interest. We would least like to ensure that with high probability, we can obtain identical optimal policies across two runs of our RL procedures:
Definition 3.1 (Replicable policy estimation). Let A be policy estimation algorithm that outputs policy म* : A given a set of trajectories sampled from an MDP. Algorithm A is p-replicable if. given independently sampled trajectory sets S₁ and Sz, and yielding policies मं and R2 it holds
3

---

Start
Goal
Obstacle
Policy
10
0.8
0.0
Figure 1: The GridWorld for our experiments (left) and different policies that generated by the Phased Q-learning Algorithm on this gridworld (center and right). Following the first policy (center) more likely reaches the left goal while following the right policy more likely reaches the right goal. All states except the goals have 0 reward. The actions are up, down, left and right; there is 30% chance that after choosing an action the agent moves left right of the target direction.
for all states 8 E S and actions a E A that
"f # (alo)l s
+ A((rr) A (als) + A(22;r)
s.t.
where r represents the internal randomness of A. Trajectory sets S1 and S2 may potentially be gathered from the environment during the execution of an RL algorithm.
While this definition is the weakest would like achieve, the results we present in this paper pro- vide stronger guarantees. Our Replicable Phased Value Iteration builds on [Kears and Singh [998a and ensures replicability of value functions. while our Replicable Episodic R-max follows [Kearns and Singh 1998b Braiman and Tennenholtz [003) and provides replicability of full MDPs. Equivalent
formal definitions for replicable value and MDP estimation are given in Appendix A
Current algorithms for sample-base based RL problems will struggle to satisfy Definition 3.1 of replicabil- ity and output different policies even in simple environments (see Figure [ In some cases, this may not be problematic since the resulting policies will still be s-optimal, but in practice it is often hard to tell when that is the case. Fixing replicability will support the identification of problematic solutions and encourage procedures that yield more stable solutions in the long run. Varying policies can, for example, arise from sample uncertainty, insufficient state-space coverage, or differing exploration. In order to achieve replicability, all of the aforementioned challenges need to be addressed. which makes for an intricate but interesting problem. With this in mind, the next section will introduce first set of formally replicable algorithms that separate out some of these challenges.
4 Algorithms
4.1
Replicable phased value iteration
The first question we answer positively is whether it is even possible to achieve replicability when the samples are drawn i.i.d. from the same distribution. For this, we use the parallel sampling model described in section 2 This model is well-suited for the task as it allows us to analyze sample-based value iteration independent of the exploration policy that collects the samples.
We provide a replicable version of indirect Phased Q-learning [Kearns and Singh 1998a), which was later also referred times and at every iteration makes m calls to (S(GM), computes an approximate value estimate for every state and does one round of value updates. Kearns and Singh [1988a] provide the following Lemma 4.1 to show the optimality of the original procedure.
Phased Value Iteration [Kakade] 2003]. In brief, the algorithm iterates T
Lemma 4.1 (Phased Q-learning convergence, [Kearns and Singh 1998a ). Suppose the number of calls to PS(G mn) is chosen such that the value function estimates produced in every round by Phased Q-learning are sufficiently accurate. For any MDP M, Phased Q-learning converges to a policy n whose return is within of the optimal policy n².
Our algorithm operates similarly, but we would like to achieve replicability on top optimality. We use randomized rounding procedure for statistical query estimation (rSTAT) provided by Im pagliazzo et al. [2022) to compute the value estimates every iteration. For this, we assume that the value function normalized to the interval [0, 1]. A detailed description of our algorithm is

---

provided in Algorithm!! [ The Replicable Phased Value Iteration (rPVI) algorithm we provide satisfies Definition 3.1 and produces e-optimal policies. goes even one step further and produces not only replicable policies but replicable value functions. This is formalized in the following Theorem 4.1 Theorem 4.1. Let (0, 1) be the accuracy and p E (0,1) be the replicability parameter. Let 5 E (0, 1) be the sample faiture probabiliry. Set the number of calls to M) at every iteration to
m m= log 2 (1/1) log
|SI|A 8
+ log log (og(l)))
(p
where supresses the dependence on 71. In two runs (1) and (2) with shared internal randommess, Algorithm produces identical policies, s.t. Pr( * (2) E O(p). In every run, the produced policies ă achieve return at most less than the optimal policy x' with all but probability O(6).
Proof Sketch, We give sketch for the proof of the theorem here and refer the reader to full proof in Appendix B.2 Assume that we can get replicable and accurate estimates of the value function expectations from our rSTAT procedure. One can show by induction that the algorithm consistently produces the same value functions in every iteration. Lemma 4.2 guarantees the convergence to an optimal policy. Finally, we can use union and Chernoff bounds to pick sufficiently large sample for our rTAT queries be replicable and accurate and satisfy our assumption.
An interesting observation that rPVI discretizes the space of values as function of the E-parameter and (see Appendix B.2). As result, replicability becomes harder for larger values of as discretization intervals become smaller and we require more samples to obtain an equally sized p. This is intuitive as we need to account for more potential future states that might impact our estimates.
The number of samples to compute a replicable value function is at most Ollog (1/c))S times larger than computing non-replicable one [Kearns and Singh| 1998a], Still, key observation of the original Phased Q-learning result was that is sufficient for every state-action pair to have a sample size logarithmic in [S][A], making the procedure cheaper than estimating the full transition dynamics of an MDP. The cost of replicability is the loss of this property. However, we note that rPVI does not yield replicable transition probability estimation. Using the idea of rSTAT queries obtain transition estimates turns out to be significantly more expensive than the replicable value estimation done by Algorithm [ (see Appendix [.2.1]. Our results retain the notion that direct value estimation is much cheaper than estimating the full transition kernel even in the presence of replicability.
4.2 Replicable RL with exploration
Next, we consider the setting of episodic exploration. We show that, despite the stochastic nature of exploration, is possible to guarantee replicability while still outputting an E-optimal policy.
We take the R-max algorithm of Bralimn and Tennenholiz (2003) as the starting point for our replicable algorithm RepRMAX (Algorithm 2) It proceeds in rounds where the agent interacts with
Algorithm Replicable Phased Value Iteration (rPVI)
Parameters: accuracy s, failure probability 6, replicability failure probability p Input: Generative Model G.
Output: e-optimal policy #*
Initialize Qo(s, a) to 0 for all (s, a) S A For all s E S, let (0(8)= = max, ((x,a) for 1. = 0..... T do S S (PS (PS(G
> do m calls to PS(GM) and store next-states in map from state-action pairs (s, a) to next states ST(s, a)).
for (8, E x A do
((5)) (STTT a)], (s))
(s, + R(s, a) + V(()) end for end for return ** - arg max, (s,
5

---

Algorithm 2 Replicable Episodic R-max (RepRMAX)
Parameters: Accuracy E, aceuracy failure probability replicability failure probability p. horizon H Input: MDP M, maximum reward Rmax Output: e-optimal policy x ~M
Initialize т M to random policy, counters for state-visitation n(s, a) to 0 Initialize K, the set collecting known state-action pairs, to the empty set 0 Initialize S. the set collecting trajectories to be used for estimating transition probabilities, to 0 Initialize MM Px (s'|s (s a) == 1 = s] for all (s, a') and Rx (x, ==1
Rmax for all (8, a)
while TI "Mx is not E-opimmal do
Collect sample of trajectories S; + p( and add S, S
K; < RepUpdateK K, {n(s, a) ().))))))))) identify new known states
For all (s.a) a) E K2, let S[(s, a)] be the multiset of visited from (s, a) for all E
For all s' E S, let Φx (s) = 1[s ss)
Update MR for all (s, a) K; Px(s'|s,a) = (T) Rx(s, = R(s,a)
K= K;
Compute TMx from Mr end while return 7 `Mх
the environment for multiple episodes. The collection of trajectories encountered during exploration is used to incrementally build model M of the underlying MDP M. The algorithm implicitly partitions the set of state-action pairs S x A into two groups: known and unknown. All (s, a) E S A are initialized to be unknown. While state is unknown, the model M maintains that (s.a) a) is self-loop with probability 1, and that (s, a) has maximum reward, thereby promoting exploration of unknown states. After state-action pair (s, a) has been visited sufficiently many times, it is added to the collection of known states K and its transition probabilities P and reward R are updated with an empirical approximation of Pk a. for all s' E S and the observed reward R, respectively. After every update, the policy т MM is computed as the optimal policy of the current model estimate.
While convergence of Algorithmm2 to an e-optimal policy follows from familiar arguments [Brafman] and Tennenholtz 2003), J proving replicability will require great deal of additional care. To ensure that two runs of RepRMAX (with shared internal randomness) converge to the same policy with high probability, we will show something even stronger: we prove that two such runs will with high probability perform the same sequence of updates to their respective models MM and policies π TMx"
To enforce this property, introduce sub-routine in Algorithm 3 which replicably identifies state-action pairs that should be added to the collection of known states. Guaranteeing that at each iteration the set of known states K will be the same for two independent runs of the algorithm helps ensure that the models of the MDP MR, , and consequently the policies ग "Mx learned at each iteration, will also be identical. To provide replicability, we will want avoid using fixed threshold for the number of times a state-action pair (s, a) must be visited before it is considered "known". Under small deviations in realized transitions, a fixed threshold might lead to some (s, a) becoming known in one run of the algorithm and not another. Instead, we use a randomized threshold.
In a call Algorithm 3 the sample drawn at that round is used to estimate the expected number of visits to (8, a) in a single trajectory, for every (s, a). This estimate is added to the count ni a). which maintains the sum, over all iterations thus far, of the estimated expected visits to (s, a) from single trajectory of the policy π MM at that iteration. A new threshold k' is then sampled uniformly from ik. + w]. If n(s, a) 2 k., it is added to the set of known states K. From standard concentration arguments, we know that for two runs of Algorithm 2 with independent samples, the estimates of the total number of expected visits n(,s, a) will both be close to the true total number of expected visits, and therefore close to each other. Algorithm 3 will only make different decisions about adding an (s, a) pair to the set of known states if the threshold k' is chosen to fall between the two estimated values ni(s a) from the two runs. Here, the concentration
n(ss, a) and the fact that randomized allows us to bound the probability that the threshold k' is chosen to fall between the different n n a)

---

values. We show in Theorem 4.2 that so long as the sample size m that is used to estimate expected visits, and the window w from which the randomized threshold sampled, are taken be large enough, the update to the set of known states at each round will be replicable.
Algorithm 3 RepUpdateK
Parameters: Accuracy failure probability 6, replicability failure probability p
Input: Sample of trajectories S,, set of known states K, set of state counts {n(s, ()).)))EXA Output: List of new known state-action pairs K;
K. {(8, a) (s,a)= E A and (s,a) E K}
k' <- [kk k + w)
for (x, E K; do
[55 Eres, 2h-1 1 [((sh; an) (s)
n(s, a) = = a) + Gs,
if (n(ssa) a) < k' then
Remove (s,a) a) from K;
end if end for return K;
Now that we have understood the intricacies on an intuitive level, we will prove convergence (Lemma 4.2) and replicability (Theorem (.2) of Algorithm 2
Lemma 4.2 (Convergence). Consider A to be Algorithm 4 Let (0, be the accuracy parameter,
P E (0, 1) the replicability parameter, and 8 E (0, 1), be the sample failure probability, with 5 < p/4.
Let E O H|S|IAI
be a bound on the number of iterations of Algorithm 2 Suppose + H² log(1/51)
6²
SE and let m Ō (1S p²
log(1/p) be the number of trajectories per iteration. Let
1 - > H[А
H be the lowest expected visit count of a state-action pair before it is known. Let w E O(k) define the window Ik, k + for sampling the randomized threshold k'. Then with all but probability after T iterations, A yields an e-optimal policy.
The proof of convergence is similar to those found in Kearns and Singh 1998b) and [Brafman and
Tennenholtz/ 2003), so we defer the proof to Appendix B.3] We continue here with the final theorem statement that summarizes the properties of our RepRMAX algorithm.
Theorem 4.2. Let parameters be set as in Lemma 4.2 Then with all but probability 8. A converges to an e-optimal policy in T iterations and samples m&T trajectories, each of length H. for total sample complexity of O (1S"]AA) H9 log(1/e)
n (1 log(1ip) Further, let S₁ and S₂ e1o
p3cb
be two trajectory sets, independently sampled over two runs of A with shared internal randomness.
and let TI (1) (als) + A(5;r) and (2)) (als) + A(2irr). Then "Mx"
"Mxx"
Prs j (als) # x MM (als)) O(p).
Proof. Lemma 4.2 gives us that, for our settings of k and T, Setoritthmmonveerre to an c-optimal policy T iterations, except with probability ò. The sample complexity follows immediately from the bound on T and the setting of m, so it remains to analyze replicability. Our analysis will make use of some additional shorthand. We use PK E (T)))) to denote the replicability
parameter for the decision to add a single (s, a) to K, in a single call to Algorithm 3 We similarly -
use PsQ E (pp ((S)) asq E (0<((1>)2/|$$)) replicability, accuracy, and failure parameters for the rSTAT queries made during the updates to P(s'|s, a). We use t O ("PK) O(is (Afrz) to denote high probability bound the difference between the empirical estimates for the expected visits to a given (s, a) in a trajectory across two runs of Algorithm 3 i.e. (2 [2)
and ĐsQ E ((5/(SS)2
to denote the
E O()). We are now ready to prove the following stronger claim:
Claim 4.1. If two runs of Algorithm begin iteration with M!) MM =(1) x (2)
MMx "Mx" and
(n(s,a)() n(s, E O(i)) V(s a), then at the end of i, M = M "MK "Mx"
(1) = =x and
()) a(s,a) (2) E O(it + t) V(s, o), with all but probability O(pr|S]|4 PSQ K1l[S)).
7

---

We take the initialization of Algorithm2 the base case for our inductive proof. Before the first (2)
We iteration, T "xxx is initialized randomly and shared internal randomness yields म "Mx " "Mxx"
(1)
deterministically initialize MMx and all n(s, and so M = -M Next, we prove the inductive step. We begin by showing that, at the end of the ith iteration, In(s,a)(0 m(s,a)) a(s,a)()))))))))))))))))) E O(it + 1) V(s,a), with all but probability ((px(S||A|).
K and n(s, a) = n(s,, a) (2))
Our inductive hypothesis gives us that [n(ss, a))) - n(ss, e) E Oii)), so it suffices to show that, for single (s, a), dhu dlee (tt) except with probability O(px)- To obtain high prob- ability bounds on [Ca,a - 222) we will rely on our assumption that at the start of the iteration, (1) (2)
Mr "I "M It follows that, for every state-action pair (s, the expected number of visits
to (s,a) in a single episode is the same for both iterations. That is, for every (s, (s,a), defining Cxaa == Pr) E 1[(sh, an) = (s, we have Ca.a Ca.a-
(2)
(1)) For particular (s,a), Chernoff bounds applied to the average observed counts Ca.a and that they must both be close to their (shared) expectation with high probability. We draw a sample of
(2) show
m E O [SSPIATT (og(1/e)
E O
112 ing(1/a)
E Ō
11² log(
1
trajectories, and each Ca.a E [0, HJ, so except with probability 4 exp
-2
E ((pk),
H
S
1 m
Σ Σ TES
1n (s, (s) c0
+
Σ
Σ
1/
(s. -c(L) O(1,,
TES(2)
h=1
where Th == (sh, an). Union bounding over all 8 E S and a E A shows that the stated bound holds for all (s, a) except with probability pk|S]|AA].
We now show that M K = =M at the end of the iteration, except with probability O(pxSS|A
PsQ |sq| [||[)]) Observe that .M M at the end of the iteration unless at least one of the following two events occurs: 1) (2(2) * K({) the set of new known (s, a) pairs differs across the two runs. 2) The updates to Px (s')s,a) and R(s, a) differ for at least one (s, a). The first event
occurs exactly when K' falls in between n(s, a) + 2ll and a))2) + 23) We have already shown that
(nss, a)()) + + n(s, a) - (2) E O + t) E O(T))
for single (s, a), except with probability ((p)). We have sampled K' uniformly at random from an interval of width w, it follows that Pr s, [(s. a) E KC >x!3) e O + ET' /w). We took t wox so by union bound over S x A. the probability of the first event is at most ((()))A|pK) T
To bound the probability of the second event conditioned the first event not occurring, it suffices to bound the probability that the updates (x [s, a) for (s,a) E K, differ across both runs, By the conditioning, we have K(D) = (2 so it suffices to show that each call to rSTAT returns the same value for both runs. Taking PSQ. ass. and dsQ as the replicability, tolerance, and failure parameters respectively gives that sample of size O(S) log(1/ōsq) ) ((E(ps 28sq 2) Volog ((18)) 7)+) is sufficient, by Theorem 2.1 Furthermore, we have assumed that 7 H|A log (1/p))
ōsQ < psq/4, and PsQ suffice. Each (s, a) is added to K; only if it was visited at least km times. We have taken & = H. [S|*) 11" log(1/p) 24p""
so sample of size E [S etp"
log(1/o)
will also
m E O "s"AA log(1/p) and T E Ω [SIILAIH) It follows that mk E E
p
and therefore ST(s,, a)] comprises at least s i.i.d. samples from P(- 8, a,) as desired. Union bounding over the |K,||S] queries in the ith iteration gives a bound of KillS)psq on the probability of the second event, conditioned on the first event not happening.
We now assemble our inductive argument into proof of the theorem. At the start of itera- tion i, the inductive hypothesis holds except with probability P + psq|
8

---

Noting that Σド= K Σ |S||A], and recalling that we have taken replicability parameters PK O(p/(T(S) and psq E Op/ ([)( ensures we achieve a replicability parameter p after the T iterations of Algorithm
4.3 Limitations
As mentioned previously, our bounds lose some of the properties that standard RL results provide, such as the ability to estimate value functions with only logarithmic dependence on relevant parameters. We expect that some of the sample complexity overhead from achieving replicability is inevitable, as seen in the statistical query power-bound of Imppaliazz et al. (2022). Nonetheless, we hope that future work can improve on the sample-complexttess of our algorithms.
Our work is in part motivated by the recent replicability concerns in deep RL [Islam et al. 2017 Henderson et al. 2018). However, establishing formal guarantees in these highly complicated settings is often not easy. As such, our algorithms suffer the weakness that many theoretical results in RL have to deal with, namely their lack of immediate applicability to real-world problems. Yet, our empirical evaluation in section will show that there is hope for practical application.
5 Experiments
While our asymptotic bounds have sample complexity overhead from the introduction of replicability, we would like analyze the actual requirements in practice. We introduce simple MDP in Figure T that contains several ways of reaching the two goals. We analyze the impact of the number of calls to PS( on replicability for rPVI. In theory, our dependence on the number of calls is not logarithmic with respect to |S|[_|] but we would like to see if can draw sample that is much smaller, maybe even on the order of the logarithmic requirement. We choose accuracy & = 0.02, failure rate 5 = 0.001 and replicability p = 0.2. The number of calls that would be required by standard Phased Q-learning at most m 13000 (ignoring 7 factors). We take several multiples of m and measure the fraction of identical and unique value functions, treating the rSTAT PsQ as hyperparameter.
The results are presented Figure 2 revealing that the number of samples needed to replicably produce the same value function can be several orders of magnitude lower than suggested by our bounds and that it is feasible use a larger PSQ than theoretically required. This should allow to scale to more complex problems in the future. The algorithm quickly produces a small set of value functions that may not be identical but, with little more data, minor differences are removed. Note that using a replicable procedure naturally incurs overhead, which is expected. However, the overhead is significantly better than the theoretically required sample-size with squared |S||AA] dependence. In the rSTAT procedure, taking smaller values for PsQ for fixed sample should improve replicability at the cost of accuracy of query responses, by increasing the width of each subinterval of the partition so that there are fewer partition elements overall. The experiments highlight that, as long as sample sizes are sufficiently large and Psq is chosen small enough, we achieve high replicability.
Related work
Our work builds upon the foundational ideas by Impagliazzo et al. [2022). who introduce formal notions of replicability that are strongly related to robustness, privacy, and generalization [Bun et al., 2023 Kalavasis et al., 2022). Building on these formal definitions of replicability, researchers have provided algorithms for replicable bandits [Estandiari et al.) 2023a] and replicable clustering [hsfann diari et al. 2023b). Ahn et al. [2022) introduce algorithms for convex optimization using a slightly different notion of replicability. Our paper presents the first results for formally replicable algorithms
in a control setting.
A concurrent and independent work by Karbasi et al. 2023 also studies formal replicability of reinforcement learning. They also study the setting of discounted tabular MDPs, with access to a generative model, and show the same sample complexity upper- upper-bounds for achieving replicable policy estimation in this setting that we prove in our work. Additionally, they provide a matching lower bound. They go to consider two relaxed notions of replicability that allow them to provide improved sample complexity upper-bounds in the generative model setting. Our work instead considers a second setting. providing a first algorithm for replicable policy estimation in the episodic exploration

---

Value for pso:
P
|s/
[S]
1.00
1.00
Fraction of identical Value Functions
replicability threshold
Fraction of Unique Value Functions
better +
0.75
0.75
0.50
better
0.50
0.25
0.25
0.00
0.00
8m
16m
32m
8m
8m
16m
Number Calls to
Number of Calls PS
The largest percentage of identical value functions across 150 runs. With more data, the quantity in- creases and the choice of psq becomes less important.
The percentage of unique value functions across 150 runs. Varying PSQ has negligible impact, while more samples quickly reduce it.
Figure 2: The rPVI algorithm evaluated on varying numbers of calls to PS) with several values for the internal rSTAT parameter PSq- Results are provided across 150 runs with different random sampling seeds. The number calls set to constant factor multiples of m = 13000. The dotted green line denotes the replicability threshold of p. The results show that, in practice, the number of samples needed for replicability can be orders of magnitude lower than our bounds suggest.
setting. We also provide experimental validation of the practical feasibility of our Replicable Phased Value Iteration algorithm.
From an RL perspective, our work is strongly related to understanding exploration MDPs Kearns
and Singh 1998b [Brafman and Tennenholtz/ 2003 Kakade 2003). In the finite-horizon episodic
setting, researchers made progress on upper bounds for exploration Auer and Ortner [2006], Auer et al.)
[200 Jaasshaaaahhaa et al. [2010] that ultimately led to the development of near-complete understanding
of the problem [Azar et al. 2017 Zanette and Brunskill] 2019] [Simchowitz and Jamieson 2019
Lower bounds Further, Jiin et al. 2020). Kaufmann et al. [2021] provide results on a reward-free framework that allows for the optimization of any reward function. While good amount of progress has been made on understanding the base problem, the notion of replicability is not considered in any of them.
provided in other works [Dann and Brunskill] [015 Osband and Roy 2016
Given the connections of replicability and robustness, our work is related but orthogonal to that of the study worst-case optimal policies and value functions. These worst-case results are often obtained via the study of robust Markov decision processes, first introduced by Nilim and Ghaoui (2005).
Iyengar (2005). One line of work here has focused on relaxation assumptions and combatting conservativeness in robust MDPs Wiesemann et al. 2013 Mannor al.. 2016 Petrik and Russel 2019 Panaganti and Kalathil 2022). Others have focused on various new formulations such as distributional robustness [u and Mannor 2010 Yu and Xu 2016). However, all of the above work
focuses on understanding worst-cases and finding policies that do not have to be replicable.
Finally, our work is related to efforts in practical RL ensure replicability, such benchmark
design [Guss et al., 202T Mendez et al. 2022) and robust implementation [Nagarajan al. 2018
Seno and Imai 2022 and evaluation [ynnerup al. 2020 Jordan et al., 2020 Agarwal et al. 2021
7 Conclusion & future work
We introduced the notion of formal replicability to the field of RL and established various novel algorithms for replicable RL. While these first results might have sub-optimal sample complexities, they highlight the crucial fact that replicability in RL is hard and requires study of the various aspects that impact it. We hope that future work can alleviate some of these efficiency challenges. general open question is if replicable RL might simply be harder by nature than standard RL? This question needs to be posed on various levels because, as we argue Section finding a replicable policy might be easier than requiring the value function to be replicable. Finally, we believe the development of replicable algorithms for other settings such as the non-episodic setting as well as practical application are of great importance.
10

---

Acknowledgments and Disclosure of Funding
The first and second authors are partially supported by the DARPA SAIL-ON program under contract HR001 120C0040, the DARPA ShELL program under agreement HR001 12190133, and the Army Research Office under MURI grant W91 INF20-1-0080, The last author is supported part by the Simons Collaboration on the Theory of Algorithmic Fairness, and NSF grant CCF-2217062.
References
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron C Courville, and Marc Bellemare. Deep reinforcement learning at the edge of the statistical precipice. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages -9304-29320. Curran Associates, Inc., 2021.
Kwangjun Ahn, Prateek Jain, Ziwei Ji, Satyen Kale, Praneeth Netrapalli, and Gil I. Shamir. Repro- ducibility in optimization: Theoretical framework and limits. In Alice H. Oh. Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. In B. Schölkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems, volume 19. MIT Press, 2006.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. In D. Koller, D. Schuurmans, Y. Bengio, and Bottou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning. volume 70 of Proceedings of Machine Learning Research, pages 263 272. PMLR, 06-11 1 Aug 2017.
C. Glenn Begley and Lee Ellis. Drug development: Raise standards for preclinical cancer research. Nature, 483(7391):531--55 March 2012.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2(Mar):499-577 2002.
Ronen I. Brafman and Moshe Tennenholtz. R-max general polynomial time algorithm for near-optimal reinforcement learning. J. Mach. Learn. Res., 3:213-200 231,, mar 2003.
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 Barna Saha and Rocco Servedio, editors, Proceedings of the 55th Annual ACM Symposium Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 520-527. ACM, 2023.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 2, NIPS' 15, page 2818-282228 8-2826, Cambridge, MA, USA, 2015. MIT Press.
Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas. Replicable bandits. In The Eleventh International Conference Learning Representa- fions, 2023a.
Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni, Grigoris Velegkas, and Felix Zhou. Replicable clustering, 2023b.
Amir-massoud Farahmand. Action-gap phenomenon in reinforcement learning. In J. Shawe-Taylon R. Zemel, Bartlett, F. Pereira, and K.Q. Weinberger, editors, Advances Newral Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
11

---

William Hebgen Guss, Stephanie Milani, Nicholay Topin, Brandon Houghton, Sharada Mohanty, Andrew Melnik, Augustin Harter, Benoit Buschmaas, Bjame Jaster, Christoph Berganski, Dennis Heitkamp, Marko Henning, Helge Ritter, Chengjie Wu, Xiaotian Hao, Yiming Lu, Hangyu Mao, Yihuan Mao, Chao Wang. Michal Opanowiez, Anssi Kanervisto, Yanick Schraner, Christian Scheller, Xiren Zhou, Lu Liu, Daichi Nishio, Toi Tsuneda, Karolis Ramanauskas, and Gabija Juceviciute. Towards robust and domain agnostic reinforcement learning competitions: Minerl 2020. In Hugo Jair Escalante and Katja Hofmann, editors, Proceedings of the NeurlPS 2020 Competition and Demonstration Track, volume 133 of Proceedings of Machine Learning Research, pages 233 252. PMLR, 06 12 Dec 2021.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters, 18/IAA ASAAAAAAAAAAAAAA" AAAI Press, 2018. ISBN 978-1-57735--00-8.
Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. In Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing, STOC 2022, page 118-831, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450392648. doi: 10.1 00.1144555199353519977
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.
Garud N. Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11651):1563-1600, 2010.
Chi Jin, Akshay Krishnamurthy, Max Simehowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4870-4879. PMLR, 13-18 Jul 2020.
Scott Jordan, Yash Chandak, Daniel Cohen, Mengxue Zhang, and Philip Thomas. Evaluating the performance of reinforcement learning algorithms. In Hal Daumé III and Aarti Singh, editors, Pro- ceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4962-4973, PMLR, 13-18 Jul 2020.
Sham M. Kakade. On the Sample Complexity of Reinforcement Learning. Phd thesis, 2003.
Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistinguishability of learning algorithms, 2023.
Amin Karbasi, Grigoris Velegkas, Lin F. Yang, and Felix Zhou. Replicability in reinforcement learning, 2023.
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato, editors, Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 865-891. PMLR, 16-19 Mar 2021.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. J. ACM, 45(6):983-1066
Nov 1998.
Michael Kearns and Satinder Singh. Finite-sample convergence rates for q-learning and indirect algorithms. Advances in Neural Information Processing Systems, 11, 1998a.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine Learning, 49:209-232, 1998b.
IS Khalil, JC Doyle, and K Glover. Robust and optimal control. Prentice hall, 1996.
12

---

Nicolai A. Lynnerup, Laura Nolling, Rasmus Hasle, and John Hallam. A survey reproducibility by evaluating deep reinforeement learning algorithms on real-world robots. In Leslie Pack Kaelbling, Danica Kragic, and Komei Sugiura, editors, Proceedings of the Conference on Robot Learning. volume 100 of Proceedings of Machine Learning Research, pages 466 489. PMIR, 30 Oct-01 Nov 2020.
Shie Mannor, Duncan Simester, Peng Sun, and John N. Tsitsiklis. Bias and variance in value function estimation. In Proceedings of the Twenty- Eientt-FFrstt International Conference on Machine Learning, page 72, New York, NY, USA, 2004, Association for Computing Machinery.
Shie Mannor, Ofir Mebel, and Huan Xu. Robust mdps with k-rectangular uncertainty. Mathematics of Operations Research,
1509, 2016.
Jorge Mendez, Marcel Hussing, Meghna Gummadi, and Eric Eaton. Composuite: A compositional reinforcement learning benchmark. In 1st Conference on Lifelong Learning Agents, 2022.
Prabhat Nagarajan, Garrett Wamell, and Peter Stone. Deterministic implementations for reproducibil- ity in deep reinforcement learning. In 2nd Reproducibilit in Machine Learning Workshop at ICML 2018, Stockholm, Sweden, July 2018
Arnab Nilim and Laurent El Ghaoui. Robust control markov decision processes with uncertain transition matrices. Operations Research, 53(5):700-798, 2005.
Ian Osband and Benjamin Van Roy. On lower bounds for regret in reinforcement learning, 2016.
Kishan Panaganti and Dileep Kalathil. Sample complexity of robust reinforcement learning with generative model. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume PMLR, 28-30 Mar 2022.
151 of Proceedings of Machine Learning Research, pages
Marek Petrik and Reazul Hasan Russel. Beyond confidence regions: sets for robust mdps. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Tight bayesian ambiguity
Joelle Pineau, Philippe Vincent-Lamarre 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-2,, 2021.
Takuma Seno and Michita Imai. D3rlpy: An offline deep reinforcement learning library. 23(1), 2022.
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buu Buch E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
V. Stodden, F. Leisch, and R.D. Peng. Implementing Reproducible Research. Chapman Hall/CRC The R Series. Taylor & Francis, 2014. ISBN 978 1466561595.
Kiri L. Wagstaff. Machine learning that matters. In Proceedings of the 29th International Coference on International Conference on Machine Learning, page 1851-1856, Madison, WI, USA, 2012. Omnipress.
Chelsea C. White and Hany K. Eldeib. Markov decision processes with imprecise transition probabil- ities. Operations Research, 42(4):739-744 1994.
Wolfram Wiesemann, Daniel Kuhn, and Breç Rustem. Robust markov decision processes. Mathe- matics of Operations Research, 38(1):153-18) 2013.
Huan Xu and Shie Mannor. Distributionally robust markov decision processes. In J. Lafferty, C. Williams, Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010.
13

---

Pengqian Yu and Huan Xu. Distributionally robust counterpart in markov decision processes. lEEE Transactions on Automatic Control, 61(9))2538 -22222233,,,, 2016.
Andrea Zanette and Emma Brunskill. Tighter
regret bounds in reinforcement learning without domain knowledge using value function bounds. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 7304-7312. PMLR, 09-15 Jun 2019.
14


Reviews:
[{"review_id": "pxCdsYJDtd", "reviewer": "Reviewer_BN9y", "summary": "This paper proposes a new reinforcement learning algorithm based on the replicability crisis and gives proof for the proposed method, providing a new perspective in this field.", "questions": "Please refer to the Weaknesses.", "limitations": "The authors have discussed the limitations in details. Nevertheless, the proposed method should be wildly evaluated in different benchmarks and provide some insights to readers, especially for a new idea.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The idea of replicable reinforcement learning is brand new and may provide a new perspective for reinforcement learning.\n2. The proof of the related lemma is sufficient and strict.\n", "weaknesses": "1.\tThe experiments are insufficient. Though the proposed replicable reinforcement learning requires much fewer samples, the performance of the replicable RL lacks. \n2.\tMore comparable experiments (i.e. DDPG, TD3, A3C, SAC, etc.) should be carried out to show the effectiveness of the proposed method.\n3.\tIt is better to provide some insightful analysis or conclusion from the replicable RL.\n4.\tThe organization may lack cohesion and coherence. Though several definitions and lemma are introduced, the relationship and function of each lemma lack a detailed claim.\n5.\tThe proposed replicable RL should be evaluated in the public benchmark such as gym， MuJoCo, etc.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer BN9y,\n\nThank you for your feedback, we appreciate that you see the direction of replicable reinforcement learning as a novel perspective.\n\nIn response to the comments in the Weaknesses and Questions sections:  \n\n“The experiments are insufficient. Though the proposed replicable reinforcement learning requires much fewer samples, the performance of the replicable RL lacks.”\n* Would you be willing to clarify this point? Our proposed algorithms require more samples than the standard versions of these algorithms and it is not clear to us what is intended by “requiring fewer samples”. The algorithms we provide are formally replicable **and** $\\varepsilon$-optimal. In all experiments, the learned policies are $\\varepsilon$-optimal, so the performance can technically not be better than that. (see Theorem 4.1 and 4.2) \n\n“More comparable experiments (i.e. DDPG, TD3, A3C, SAC, etc.) should be carried out to show the effectiveness of the proposed method.”\n*  We think that comparison to common benchmark deep learning methods is inappropriate for this stage of replicable reinforcement learning research. As we show in our work, designing reinforcement learning algorithms that can learn approximately optimal policies while simultaneously satisfying replicability is a challenging task that requires new technical tools and algorithm design. Our work initiates the study of replicable reinforcement learning, building a technical toolkit for replicable RL toolkit that we hope can be used to obtain more performant algorithms in the future, but our techniques in their current form are not applicable to non-linear function approximation or deep learning. Even linear function approximation would require the development of completely new tools for replicability. We agree that this is an interesting direction for future work, and it is a line of research we plan to pursue, but there are substantial technical leaps to make before we can guarantee replicability of deep learning approaches. \n\n“It is better to provide some insightful analysis or conclusion from the replicable RL.”\n* As we state in the introduction, we provide novel algorithms that are formally replicable. (Line 35 and following) These algorithms are provably correct and replicable with high probability (see Theorem 4.1 and 4.2). The analysis of the algorithms is provided either in the Appendix B.1 and B.2 for Algorithm 1 and in large parts in the main text (L215 - 276) or Appendix B.3 for Algorithm 2. The analysis of the empirical results is done in L298-305. The conclusion is provided in the Conclusion & Future work section. Would you mind clarifying what additional analysis we could add to improve the paper?\n\n“The organization may lack cohesion and coherence. Though several definitions and lemma are introduced, the relationship and function of each lemma lack a detailed claim.”\n* As stated in the text, Definitions 2.1 and 2.2 are used to describe the theoretical settings we consider. Definition 2.3, 2.4 and Theorem 2.1 frame the context of the work and provide the required formal background. Definition 3.1 is one of the contributions and is used to derive the algorithms we propose. Both Theorem 4.1 and 4.2 satisfy this Definition 3.1 (see their respective text). Lemma 4.1 is used to provide the accuracy argument for Theorem 4.1 (see L166-167) (see full proof in Appendix B.1 and B.2). Lemma 4.2 (L215, typo here) is used to prove convergence of Theorem 4.2 (see L230). This should cover all the definitions and lemmas in the main text and all of them are explicitly used in some main claim or are used to frame context and setting. Can you elaborate which specific definition or lemma is unclear?\n\n“The proposed replicable RL should be evaluated in the public benchmark such as gym， MuJoCo, etc.”\n* Our Algorithms are tabular reinforcement learning algorithms and we evaluate our algorithm on a tabular MDP in section 5. The experiments we conduct are explicitly designed to demonstrate that our algorithms replicably converge to good policies, not just that they learn good policies, and moreover that the sample complexity overhead of achieving replicability in practice may be less significant than what is suggested by the asymptotic upper-bounds of our theoretical guarantees.  \n* Tabular reinforcement learning algorithms do not generally scale well with respect to the size of the state-space, and so are not typically tested in gym environments. Given that our algorithms are tabular, and that our primary contributions are of a theoretical nature, we believe that gym environment (or similar) experiments would detract from, rather than complement, the presentation of our main results. That being said, if there are suggestions for experiments that might improve our understanding of replicability in practice, we would be happy to run them!\n"}, {"review_id": "PEEdCvy2L7", "reviewer": "Reviewer_fsAq", "summary": "This paper studies replicable reinforcement learning. And they show that stochastic sample-based value iteration can be done replicably and explore the space of an MDP to find an optimal policy. Furthermore, they give some theoretical results. The effectiveness of the replicable algorithm is validated by simple experiments, requiring fewer sample than the theory suggests.", "questions": "- Definition 2.3 is not clear. What does $r$ mean? This is the same definition as Impagliazzo et al. (2022). There is no citation!\n- ''As a result, we expect that replicable estimation of MDPs is the hardest setting in stochastic RL, followed by replicable value function and then policy estimation'', if we don't know the MDP, how do we estimate the fine value function and policy function. I think that MDP is a foundation.\n- ''a new threshold k′ is sampled uniformly from [k, k + w].  '', why is k' chosen at random instead of assigning one? What's your motivation for doing this?\n- From the left figure of Fig.2, except for the number of steps, it can be seen the choice of $\\rho_{SQ}$ is crucial. We should know how to choose it. Can you clarify why $\\rho_{SQ}=\\frac{\\rho}{|S|}$ has a good result? And if we increase the number of steps, when $\\rho_{SQ}=\\frac{\\rho}{|S|}$, do we still get good results?", "limitations": "The authors explained the limitations of their work well. I do not see an obvious negative societal impact.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- They first introduce the notion of replicability to RL because RL algorithms are difficult to reproduce. \n- They provide two novel algorithms (replicable phased value iteration and Exploration) for replicable RL and also give corresponding theoretical results. This formulation provides a good foundation for the problem.", "weaknesses": "- From this paper,  at each iteration $t$, many episodes interacting with the environment are required. This is equivalent to modeling the environment. If so, it is trivial to obtain similar policies, even though there are some theories. The studies in this area concern a few episodes interacting with env at each iteration; after $T$ iterations, the two policies are close to each other. This is just like the Policy Iteration and the Value Iteration.\n- The experimental evaluation is weak, though the paper pays more to the theoretical part.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer fsAq,\n\nThank you for your feedback. We appreciate that you think that our notion of replicability provides a good foundation for studying reproducibility in RL.\n\nIn response to the comments in the Weaknesses and Questions sections:\n\n“at each iteration, many episodes interacting with the environment are required. This is equivalent to modeling the environment. If so, it is trivial to obtain similar policies, even though there are some theories.”\n* Simply interacting with the environment would not give us that we can model it. It is significantly harder to model the full environments than to find a policy (see e.g., Kearns et al 1998). Could you elaborate which theories you are talking about? We are unaware of any theory that would ensure replicability and accuracy of any previous RL procedure.\n\n\"The studies in this area concern a few episodes interacting with env at each iteration; after iterations, the two policies are close to each other. This is just like the Policy Iteration and the Value Iteration.\"\n* This seems to be a key misunderstanding. We are not asking that the two policies are close to each other but we are asking they be *identical* across different stochastic interactions with the environment. In our settings, transitions need to be sampled while algorithms like value iteration assume direct access to the transition function. The stochastic version would be Phased Value Iteration which we use in the paper. There is no guarantee for replicability (or policy similarity) in PVI. See Figure 1 for a counter-example.\n\n“The experimental evaluation is weak, though the paper pays more to the theoretical part.”\n* Our algorithms are tabular RL algorithms and we evaluate them on a tabular MDP in section 5. The experiments we conduct are explicitly designed with two goals in mind: a proof of concept for replicable algorithms in a non-trivial environment (i.e., an environment where there is more than one optimal policy, so that replicability is not already implied by optimality) and to show that the sample complexity overhead of replicability is not as onerous as might be suggested from the asymptotic upper-bounds. Our experiments cover both points. That being said, if there are suggestions for experiments that might improve our understanding of replicability in practice, we would be happy to run them!\n\n“Definition 2.3 is not clear.” \n* r is the shared internal randomness mentioned in the definition and should be stated in the text of the definition. Good catch; we added this in L87. We also added the citation to the definition directly to be more precise.\n\n“if we don't know the MDP, how do we estimate the fine value function and policy function”\n* Most RL algorithms do not assume to *know* the MDP, they merely have access to a sampling machine (e.g., an environment). We do not need to estimate the reward function and transition probabilities to run PVI but we can compute a value function without knowing the exact form of the MDP. This is cheaper in terms of sample complexity since the value function is significantly smaller than the transition function.\n\n''why is k' chosen at random instead of assigning one?\"\n* This is done to achieve replicability. Suppose there are two runs of the algorithm (1) and (2). Our goal is to make updates to the set of known states K identical across runs, to establish downstream replicability. In (2), we would like to add to K exactly all elements that were added to K in (1). Assume there was a fixed threshold k. It could be that in expectation we will see some state-action $(s, a)$ pair enough times that it meets the fixed threshold k. Due to the stochastic nature of exploration, the realized transitions in (1) may cause us to visit $(s, a)$ only (k-1) times, while the realized transitions in (2) cause us to see it (k+1) times. A fixed threshold would mean that we don’t add $(s, a)$ to K in (1), but do add it to K in (2), making replicability difficult to reason about. Yet, we can guarantee that the realized number of visits to a state-action pair concentrates around its mean. By randomizing the threshold k over a large interval, we can ensure with high probability that k does not fall between the two realized values for visitation counts. Hence, the algorithm makes the same decisions about whether $(s, a)$ is added to K in both (1) and (2) (see proof of Theorem 4.2). We have updated the paper to provide this motivation in the algorithmic exposition.\n\n“Can you clarify why has $\\rho_{SQ} = \\frac{\\rho}{|S|}$ a good result? And if we increase the number of steps, when $\\rho_{SQ} = \\frac{\\rho}{|S|}$, do we still get good results?”\n* Informally, the replicable statistical query algorithm uses its random string to partition the [0,1] interval into subintervals, and assigns canonical representatives to each subinterval. It empirically estimates the value of the query using its sample, and then returns the nearest canonical representative to the empirical estimate. For a fixed sample, taking smaller values for $\\rho_{SQ}$ improves replicability at the cost of accuracy of query responses, by increasing the width of each subinterval of the partition so that there are fewer partition elements overall. This way, two estimates that are close are likely to be rounded to the same representative, but the possible error induced by this rounding will increase.\n* As long as the sample sizes are sufficiently large and $\\rho_{SQ}$ is chosen small enough, we expect that we achieve high replicability. The current sample size of 30 runs was not representative to reflect this so we increased the number of runs we compute identical value functions over to 150. The new plots (appended in PDF) show that with a large sample size, any $\\rho_{SQ}$ smaller than $\\rho_{SQ} = \\rho/|S|$ works well. In all cases, $\\rho_{SQ} = 0.2$ results in poor performance arguably because the subintervals are too small such that the likelihood of falling into different bins is too high."}, {"review_id": "bbkOoSp29p", "reviewer": "Reviewer_u4VH", "summary": "This paper studies an important topic of RL replicability. Under some assumptions, this work gives definitions of rho-replicable and proposes two algorithms: Rep-PVI and Rep-RMAX, and shows their reproducibility properties through proof.\n", "questions": "Finite state space and known deterministic reward function seem to be too strong assumptions. The stochasticity comes from 1. exploration and 2. environment stochasticity (including dynamics and reward). If the reward is known and deterministic, a planning algorithm can always be applied and RL is not necessary.\n\nWith the parallel sampling definition, the parallel sampling subroutine PS(G) actually turns the transition distribution into a deterministic kernel, this is also a strong assumption. To this end, all stochasticity sources are canceled out in your study.\n\nI may understand it wrongly, but with those assumptions, I wonder if the basic Q-learning algorithm also enjoys the property of convergence to the optimal policy with probability 1. This lead to another question of why the PVI and RMAX algorithms are selected to build the method upon.\n\nFor the experiment section, have the authors tried to experiment on some standard RL environment? Inclusively the classical navigation tasks (but are more standard ones) so that the trade-offs between replicability and the performance can have a clearer exposition?\n\n", "limitations": "The generality of the proposed method, which also affects the importance of their contribution to the field.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Overall, the development of the paper is smooth, the topic is important, the perspective is novel in the RL literature, and the analytical and empirical evidence seems supportive of the claims.\n", "weaknesses": "Please see the questions section below\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer u4VH,\n\nThank you for your feedback! We are glad that you find the topic of replicable RL important and novel.\n\nIn response to the comments in the Questions section:\n\n “I may understand it wrongly, but with those assumptions, I wonder if the basic Q-learning algorithm also enjoys the property of convergence to the optimal policy with probability 1. This lead to another question of why the PVI and RMAX algorithms are selected to build the method upon.”  \n* Neither Phased Value Iteration nor Q-learning converge to an optimal policy with probability 1 in the stochastic (PAC) setting we consider since we always have to account for the sampling failure probability. Classical Phased Value Iteration as well as versions of Q-learning are $\\varepsilon$-optimal with probability $1-\\delta$ under certain coverage assumptions. However, a key point that is missing in this consideration is that there may be more than one $\\varepsilon$-optimal policy. As such, neither of these algorithms are replicable, which is the property we study in this work.\n* We start at the very beginning of sample complexity analysis and use two of the early algorithms that already prove to be quite challenging in the setting we select. Phased Value Iteration (sometimes Phased Q-Learning) - as the name suggests - is an algorithm that effectively does Value Iteration (repeatedly) when having access to sampled transitions rather than the full transition model. This is the first step of introducing stochasticity to dynamic programming-based algorithms such as classical Value Iteration and it already bears a significant overhead for replicability, and necessitates new techniques not previously appearing in the RL literature. \nThe second setting we consider is that of episodic exploration and, here, an initial class of algorithms to start with is the $E^3$ or RMax style algorithms. These algorithms contain a natural notion of previously explored states via their sets of known states. We use the sets of known states as a proxy for what parts of the space have been explored and try to replicably have the same sequence of states be added to K. This choice is made to create a way of measuring and comparing exploration across two runs.\n\n“Finite state space and known deterministic reward function seem to be too strong assumptions. The stochasticity comes from 1. exploration and 2. environment stochasticity (including dynamics and reward). If the reward is known and deterministic, a planning algorithm can always be applied and RL is not necessary.”\n* Finite state spaces and deterministic reward functions are very common assumptions in the RL literature and the base problem considering these two has only very recently been considered close to solved (Azar et al., 2017; Zanette and Brunskill, 2019; Simchowitz and Jamieson, 2019). Control problems per se are hard and making these assumptions allows us to study them in parts. As mentioned in the text, our algorithms can easily be adjusted to handle stochastic rewards (see L54f) since estimating them on top of transitions or values is just additive overhead. We agree that planning and RL are connected but both warrant their individual study to make scientific progress.\n\n“With the parallel sampling definition, the parallel sampling subroutine PS(G) actually turns the transition distribution into a deterministic kernel, this is also a strong assumption. To this end, all stochasticity sources are canceled out in your study.”\n* This is incorrect and the parallel sampling subroutine does **not** automatically give us a kernel. This would only be true in the limit of $n$ where $n$ is the number of samples for every individual state. However, sample complexity bounds study the lowest number of samples we can use to achieve our goal which does not require full estimation of the kernel itself (see Kearns et al. 1998). The challenge for the first algorithm is in fact to obtain a replicable policy under the uncertainty of sampling which is not canceled out. If this were true, standard algorithms like Phased Value Iteration would provide replicable policies but they do not (see Figure 1 for counter-example).\n\n“For the experiment section, have the authors tried to experiment on some standard RL environment? Inclusively the classical navigation tasks (but are more standard ones) so that the trade-offs between replicability and the performance can have a clearer exposition?”\n* Our algorithms are tabular RL algorithms and we evaluate them on a tabular MDP in section 5. The experiments we conduct are explicitly designed with two goals in mind: a proof of concept for replicable algorithms in a non-trivial environment (i.e., an environment where there is more than one optimal policy, so that replicability is not already implied by optimality) and to show that the sample complexity overhead of replicability is not as onerous as might be suggested from the asymptotic upper-bounds. Our experiments cover both points.\nTabular RL algorithms do not generally scale well with respect to the size of the state-space, and so are not typically tested in these environments. Given this, and that our primary contributions are of a theoretical nature, we believe that gym environment experiments would detract from, rather than complement, the presentation of our main results. That said, if there are suggestions for experiments that might improve our understanding of replicability in practice, we would be happy to run them!\n* Could you specify which classical navigation tasks you are referring to? We considered several tasks from the standard RL book by Sutton et al. (2018) but found them too simple for the purposes of studying replicability. A key property for a good benchmark MDP is that there should be several $\\varepsilon$-optimal policies that could be selected, so that we can demonstrate our algorithm chooses the same one with high probability over samples (for a fixed random string), and is therefore replicable."}, {"review_id": "jRmZdtkunH", "reviewer": "Reviewer_vrU3", "summary": "\nThis paper discusses the development of algorithm frameworks for replicability, which is a response to the replicability crisis in social, behavioral, and data sciences. The paper introduces provably replicable algorithms for machine learning and statistics, including replication results for control problems, which pose different challenges than batch learning settings. The paper provides a provably replicable algorithm for parallel value iteration and a provably replicable version of R-Max in the episodic setting, which are the first formal replicability results for control problems.", "questions": "1. Can the corresponding analysis continue to be maintained in the setting of deep networks?\n2. How much additional cost is required for the proposed method?", "limitations": "Although the method has a strong mathematical and theoretical analysis, it would be better to have more sufficient experiments in the experimental section.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method has a strong mathematical and theoretical analysis, which is convincing.\n2. The researched field appears to be valuable and interesting.\n3. The writing is clear and easy to understand.", "weaknesses": "Although the method has a strong mathematical and theoretical analysis, it would be better to have more sufficient experiments in the experimental section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer vrU3,\n\nThank you for your feedback. We are glad that you find our work convincing and valuable.\n\nIn response to the comments in the Weaknesses and Questions sections:\n\n“Although the method has a strong mathematical and theoretical analysis, it would be better to have more sufficient experiments in the experimental section.”\n* Our algorithms are tabular reinforcement learning algorithms and we evaluate our algorithms on a tabular MDP in section 5. The experiments we conduct are explicitly designed with two goals in mind: a proof of concept for replicable algorithms in a non-trivial environment (i.e., an environment where there is more than one optimal policy, so that replicability is not already implied by optimality) and to show that the sample complexity overhead of replicability is not as onerous as might be suggested from the asymptotic upper-bounds. Our experiments cover both points. That being said, if there are suggestions for experiments that might improve our understanding of replicability in practice, we would be happy to run them!\n\n“Can the corresponding analysis continue to be maintained in the setting of deep networks?”\n* The proposed techniques are in their current form not applicable to non-linear function approximation.  Even linear function approximation would require the development of completely new tools for replicability. We agree that this is an interesting direction for future work but there are several leaps to make before we can guarantee replicability of deep learning approaches.\n\n\"How much additional cost is required for the proposed method?”\n* The overhead on the methods is on the order $|S|^2|A|^2 / \\rho^2$ for rPVI (see L173) and $|S|^5|A|^6H^6 /(\\epsilon^2 \\rho^2)$ for RepRMax (we will add this to the appendix)"}]

Author rebuttal:
Dear Reviewers, 

Thank you for your valuable feedback! We are grateful for the questions, suggestions, and opportunity to clarify the intent of our work. 

We would first like to provide a set of common answers to the points raised by reviewers here. We will provide the responses to individual reviewer’s questions in the appropriate, reviewer-specific response form. 

First and foremost, we would like to highlight that this is a theoretical manuscript with a focus on providing the first-ever results for formally replicable reinforcement learning. Experimentation is secondary and is done to validate the potential usefulness of general replicable algorithms for real-world problems in the future. We are excited that several reviewers see the novelty and need for such algorithms and that the reviewers believe that our claims are well supported. For other commonly highlighted comments or questions:

Deep Learning Baselines: Several reviews ask about comparisons to deep learning methods. We can only stress again that this is the first fundamental work on formally replicable reinforcement learning, and we think that comparison to common benchmark deep learning methods is inappropriate for this stage of replicable reinforcement learning research. As we show in our work, designing reinforcement learning algorithms that can learn approximately optimal policies while simultaneously satisfying replicability is a challenging task that requires new technical tools and algorithm design. Our work initiates the study of replicable reinforcement learning, building a technical toolkit for replicable RL that we hope to further develop in the future, but our techniques in their current form are not applicable to non-linear function approximation or deep learning. Even linear function approximation would require the development of completely new tools for replicability. We agree that this is an interesting direction for future work, and it is a line of research we plan to pursue, but there are several substantial technical leaps to make before we can guarantee replicability of deep learning approaches. 

Choice of algorithms. We start at the very beginning of sample complexity analysis and use two of the early algorithms that already prove to be quite challenging in the setting we select. Phased Value Iteration (sometimes Phased Q-Learning) - as the name suggests - is an algorithm that effectively does Value Iteration (repeatedly) when having access to sampled transitions rather than the full transition model. This is the first step of introducing stochasticity to dynamic programming-based algorithms such as classical Value Iteration and it already bears a significant overhead for replicability, and necessitates new techniques not previously appearing in the RL literature. 
The second setting we consider is that of episodic exploration and, here, an initial class of algorithms to start with is the E^3 or RMax style algorithms. These algorithms contain a natural notion of previously explored states via their sets of known states. We use these sets of known states as a proxy for what parts of the space have been explored and try to replicably have the same sequence of states be added to K. This choice is made to create a way of measuring and comparing exploration across two runs.

Experiments: Our algorithms are tabular reinforcement learning algorithms and we evaluate our algorithms on a tabular MDP in section 5. The experiments we conduct are explicitly designed with two goals in mind: a proof of concept for replicable algorithms in a non-trivial environment (i.e., an environment where there is more than one optimal policy, so that replicability is not already implied by optimality) and to show that the sample complexity overhead of replicability is not as onerous as might be suggested from the asymptotic upper-bounds. Our experiments cover both points.
	
It was suggested that we include experiments in a classical gym environment as well. Tabular reinforcement learning algorithms do not generally scale well with respect to the size of the state-space, and so are not typically tested in these environments. Given that our algorithms are tabular, and that our primary contributions are of a theoretical nature, we believe that gym environment (or similar) experiments would detract from, rather than complement, the presentation of our main results. That being said, if there are suggestions for experiments that might improve our understanding of replicability in practice, we would be happy to run them!

We have integrated your feedback into the draft of the manuscript. Here is a brief summary of the changes we are going to add:

1.) We found a minor bug in the analysis of the Replicable R-Max algorithm which we have fixed, and adjusted the rates accordingly.  
2.) We made clarifying changes on the notation in Definition 2.3 and fixed a typo in the enumeration of Theorem from (previously) 4.1 to (now) 4.2.  
3.) We updated the experimental plots using a more representative sample (new plots in PDF) and included a more intuitive explanation of the analyzed parameter $\rho_{SQ}$.  
4.) We extended the informal description of the RepRMAX algorithm to provide better intuition for the randomized threshold.

Meta-review: This paper breaks new ground by defining a framework for provably replicable RL algorithms for tabular RL settings and as such is highly valuable for the NeurIPS community. At the cost of reduced sample efficiency, we are guaranteed, with high probability, to always obtain the same policy from the algorithm regardless of the random seed used. Some reviewers have raised concerns about applicability to deep RL settings, but I think these concerns are only founded to a limited extent.  I think the authors have addressed the concerns of the deep RL community adequately in their answer to my comment. In a nutshell, I do not think it is fair to expect a paper based on a premise this novel to match performance of more standard algorithms which have been tuned over many years.

However, the paper still does have some presentation issues. For example:
- $\mathcal{A}$ is used for both action set (sec 2.1) and algorithm (sec 2.2)
-  $r$ is used for both reward (sec 2.1) and algorith randomness (sec 2.2) which is not defined until def 3.1

I wanted to ask the authors to carefully-proof read the paper again to make sure issues like the above are addressed.
Decision: Accept (poster)