Replicability in Reinforcement Learning
Authors: Amin Karbasi
Grigoris Velegkas
Lin Yang
Felix Zhou
Venue: NeurIPS 2023 poster (2023)
Keywords: Theory
Reinforcement Learning Theory
Statistical Learning Theory
Reproducibility
Replicability
TL;DR: We design replicable algorithms for policy estimation in offline, infinite horizon, tabular, discounted Markov decision processes.

Abstract: We initiate the mathematical study of replicability as an 
  algorithmic property in the context of reinforcement learning (RL).
  We focus on the fundamental setting of discounted tabular MDPs with access to a generative model.
  Inspired by Impagliazzo et al. [2022], we say that an RL algorithm is replicable if,
  with high probability,
  it outputs the exact same policy
  after two executions on i.i.d. samples drawn from the generator
  when its internal randomness
  is the same.
  We first provide 
  an efficient $\rho$-replicable algorithm for $(\varepsilon, \delta)$-optimal policy estimation
  with sample and time complexity $\widetilde O\left(\frac{N^3\cdot\log(1/\delta)}{(1-\gamma)^5\cdot\varepsilon^2\cdot\rho^2}\right)$,
  where $N$ is the number of state-action pairs.
  Next,
  for the subclass of deterministic algorithms,
  we provide a lower bound of order $\Omega\left(\frac{N^3}{(1-\gamma)^3\cdot\varepsilon^2\cdot\rho^2}\right)$.
  Then, we study a relaxed version of replicability proposed
  by Kalavasis et al. [2023] called TV indistinguishability.
  We design a computationally efficient TV indistinguishable algorithm for policy estimation
  whose sample complexity is $\widetilde O\left(\frac{N^2\cdot\log(1/\delta)}{(1-\gamma)^5\cdot\varepsilon^2\cdot\rho^2}\right)$.
  At the cost of $\exp(N)$ running time,
  we transform these TV indistinguishable algorithms to $\rho$-replicable ones without increasing their sample complexity.
  Finally,
  we introduce the notion of approximate-replicability
  where we only require that two outputted policies are close
  under an appropriate statistical divergence (e.g., Renyi)
  and show an improved sample complexity of $\widetilde O\left(\frac{N\cdot\log(1/\delta)}{(1-\gamma)^5\cdot\varepsilon^2\cdot\rho^2}\right)$.

Replicability in Reinforcement Learning"
Amin Karbasi Yale University, Google Research amin. karbasi @yale. caaale.ddu edu
Grigoris Velegkas Yale University
grigoris.ve wetorrss.ellgkaa@yalle.e.ee edu
Lin F. Yang UCLA
Felix Zhou
Yale University felix. zhou@yale edu
1 linyang@ee.c www.:eeeeeellcecee.c... ucla.edu
Abstract
We initiate the mathematical study of replicability context of reinforcement learning (RL). We focus on the fundamental setting dis- counted tabular MDPs with access to generative model. Inspired by Impagliazzo et al. [2022], we say that an RL algorithm replicable if, with high probability, it outputs the exact same policy after two executions i.i.d. samples drawn from the generator when its internal randomness the same. We first provide an efficient p-replicable algorithm for (s, 5) opttimal policy estimation with sample and time complexity Ö (ool0))1 where N is the number of state-action pairs. Next, (1-7)"--7pp)
algorithmic property in the
for the subclass of deterministic algorithms, we provide a lower bound of order N3 (1-3)".02.p* Then, study a relaxed version of replicability proposed by Kalavasis et al. [2023] called TV indistinguishubiliy. We design computation- ally efficient TV indistinguishable algorithm for policy estimation whose sample
2
complexity is Ö (1-10 At cost of exp(NN) running time, we transform
(I-7)
these TV indistinguishable algorithms to p-replicable ones without increasing their sample complexity. Finally, introduce the notion of auproximatee-eplicabllll where we only require that two outputted policies are close under an appropriate statistical divergence (e.g., Renyi) and show improved sample complexity of Ō N N-log(1/8) -2.
Introduction
When designing reinforcement learning (RL) algorithm, how can one ensure that when it is executed twice in the same environment its outcome will be the same? this work, our goal is to design RL algorithms with provable replicability guarantees. The lack of replicability in scientific research, which the community also refers to as the reproducibility crisis, has been major recent concern. This can be witnessed by an article that appeared in Nature [Baker, 2016]: Among the 1,500 scientists who participated in a survey, 70% of them could not replicate other researchers' findings and more shockingly, 50% of them could not even reproduce their own results. Unfortunately, due to the exponential increase the volume Machine Learning (ML) papers that are being published each year, the ML community has also observed an alarming increase in the lack of reproducibility. As result, major ML conferences such as NeurIPS and ICLR have established "reproducibility challenges" in which researchers encouraged to replicate the findings of their colleagues [Pineau et al., 2019, 2021].
Authorrs listed alphabetically.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Recently, RL algorithms have been a crucial component of many ML systems that are being deployed in various application domains. These include but are not limited to, competing with humans in games [Mnih et al., 2013, Silver et al., 2017, Vinyals et al., 2019. , FAIR], creating self-driving cars (Kiran et al., 2021], designing recommendation systems [Afsar et al., 2022], providing e-healthcare services (Yu et al., 2021], J. and training Large Language Models (LLMs) [Ouyang et al., 2022]. In order to ensure replicability across these systems, an important first step is to develop replicable RL algorithms. To the best of our knowledge, replicability in the context of RL has not received formal mathematical treatment. We initiate this effort by focusing on infinite horizon, tabular RL with a generative model. The generative model was first studied by Kearns and Singh [1998] in order to understand the statistical complexity of long-term planning without the complication of exploration. The crucial difference between this setting and Dynamic Programming (DP) [Bertsekas, 1976] is that the agent needs to first obtain information about the world before computing a policy through some optimization process. Thus, the main question is understand the number of samples required to estimate a near-optimal policy. This problem is similar to understanding the number of labeled examples required in PAC learning [Valiant, 1984].
In this work, we study three different formal notions of replicability and design algorithms that satisfy them. First, we study the definition of Impagliazzo et al. [2022], which adapted to the context of RL says that a learning algorithm is replicable if it outputs the exact same policy when executed twice on the same MDP, using shared internal randomness across the two executions (ef. Definition 2.)0).
We show that there exists a replicable algorithm that outputs a near-optimal policy using Ö(N*) samples", where N is the cardinality of the state-action space. This algorithm satisfies an additional property we call locally random, which roughly asks that every random decision the algorithm makes based on internal randomness must draw its internal randomness independently from other decisions. Next, we provide a lower bound for deterministic algorithms that matches this upper bound.
Subsequently, we study a less stringent notion of replicability called TV indistinguishabiiity. which was introduced by Kalavasis et al. [2023]. This definition states that, in expectation over the random draws of the input, the TV distance of the two distributions over the outputs of the algorithm should be small (ef. Definition 4.1). We design a computationally efficient TV indistinguishable algorithm for answering statistical queries whose sample complexity scales as (dd²). We remark that this improves the sample complexity of its replicable counterpart based on the rounding trick from Impagliazzo et al. [2022] by a factor of d and it has applications outside the scope of our work [Impagliazzo et al., 2022, Esfandiari et al., 2023b,a, Bun et al., 2023, Kalavasis et al., 2023]. This algorithm inspired by the Gaussian mechanism from the Differential Privacy (DP) literature [Dwork et al., 2014]. Building upon this statistical query estimation oracle, we design computationally efficient TV-indissinguuisaable algorithms for Q-function estimation and policy estimation whose sample complexity scales as Ö(N²). Interestingly, we show that by violating the locally random property and allowing for internal randomness that creates correlations across decisions, we can transform these TVV indistinguishable algorithms to replicable ones without hurting their sample complexity, albeit at a cost of ((cxp running time. Our transformation is inspired by the main result of Kalavasis et al. [2023]. We also conjecture that the true sample complexity of p-replicable policy estimation is indeed @(
Finally, we propose a novel relaxation of the previous notions of replicability. Roughly speaking, we say that an algorithm approximately replicable if, with high probability, when executed twice on the same MDP, it outputs policies that are close under a dissimilarity measure that is based on the Renyi divergence. We remark that this definition does not require sharing the internal randomness across the executions. Finally, we design an RL algorithm that is approximately replicable and outputs near-optimal policy with Ö(N) sample and time complexity.
Table 1.1 and Table 1.2 summarizes the sample and time complexity of Q-estimation and policy estimation, respectively. under different notions of replicability. We assume the algorithms in question have a constant probability of success. In Appendix G, we further discuss the benefits and downsides for each of these notions.
For simplicity, we hide the dependence on the remaining parameters of the problem in this section.
2

---

Table 1.1: Complexity Overview for Q-Estimation with Constant Probability of Success.
PROPERTY
SAMPLE COMPLEXITY
TIME COMPLEXITY
Na
N3 (1
LOCALLY RANDOM, REPLICABLE
Peap
TV INDISTINGUISHABLE
N
Ô
Polv(N) =-
[1
REPLICABLE (THROUGH INDISTINCUISHABILITY)
Ô
Table 1.2: Complexity Overview for Policy Estimation with Constant Probability of Success.
PROPERTY
SAMPLE COMPLEXITY
TIME COMPLEXITY
Na
Na
LOCALLY RANDOM, REPLICABLE
TV INDISTINGUISHABLE
Ô
N²
poly(N) 11 (1-7"-pp'
1
REPLICABLE (THROUGH TV INDISTINGUISHABILITYY)
(1-7)622p
N2
0
11 1-7j"cpp
expiN
APPROXIMATELY REPLICABLE
11-73"22p
(1-7)
1.1 Related Works
Replicability. Pioneered by Impagliazzo et al. [2022]. there has been a growing interest from the learning theory community in studying replicability as an algorithmic property. Esfandiari et al. [2023a,b] studied replicable algorithms in the context of multi-armed bandits and clustering. Recently, Bun et al. [2023] established equivalences between replicability and other notions of algorithmic stability such as differential privacy when the domain of the learning problem is finite and provided some computational and statistical hardness results to obtain these equivalences, under cryptographic assumptions. Subsequently. Kalavasis et al. [2023] proposed relaxation of the replicability definition of Impagliazzo al. [2022], showed its statistical equivalence to the notion of replicability for countable domains and extended some of the equivalences from Bun et al. [2023] to countable domains. Chase et [2023], Dixon al. [2023] proposed notion of list-repiicability where the output of the learner is not necessarily identical across two executions but is limited to small list choices.
The closest related work to ours is the concurrent and independent work of Eaton et al. [2023]. They also study a formal notion replicability in RL which is inspired by the work of Impagliazzo et al. [2022] and coincides with one of the replicability definitions we are studying (cf. Definition 2.8). Their work focuses both on the generative model and the episodic exploration settings. They derive upper bounds on the sample complexity in both settings and validate their results experimentally. On the other hand, our work focuses solely on the setting with the generative model. We obtain similar sample complexity upper bounds for replicable RL algorithms under Definition 2.8 and then we show a lower bound for the class of locally random algorithms. Subsequently, we consider two relaxed notions of replicability which yield improved sample complexities.
Reproducibility in RL. Reproducing, interpreting, and evaluating empirical results in RL can be challenging since there are many sources of randomness in standard benchmark environments. Khetarpal et [2018] proposed framework for evaluating RL to improve reproducibility. Another barrier to reproducibility is the unavailability of code and training details within technical reports. Indeed, Henderson et [2018] observed that both intrinsic (e.g. random seeds, environments) and extrinsic (e.g. hyperparameters, codebases) factors can contribute to difficulties in reproducibility. Tian al. [2019] provided an open-source implementation of AlphaZero [Silver et al., 2017], popular RL-based Go engine.
We remark that this equivalence for finite domains can also be obtained, implicitly, from the results of Bun al. [2023].

---

RL with a Generative Model. The study of RL with generative model was initiated by Kearns and Singh [1998] who provided algorithms with suboptimal sample complexity in the discount factor y. A long line of work (see, e.g. Gheshlaghi Azar et al. [2013], Wang [2017], Sidford et al. [201 (a,),, Feng et al. [2019], Agarwal et al. [2020], Li et al. [2020] and references therein) has led to (non-replicable) algorithms with minimax optimal sample complexity. Another relevant line of work that culminated with the results of Even-Dar et al. [2002], Mannor and Tsitsiklis [2004] studied the sample complexity of finding an e-optimal arm in the multi-armed bandit setting with access to generative model.
2 Setting
2.1 Reinforcement Learning Setting
(Discounted) Markov Decision Process. We start by providing the definitions related to the Markov Decision Process (MDP) that we study in this work.
Definition 2.1 (Discounted Markov Decision Process). A (discounted) Markov decision pro- cess (MDP) is a 6-tuple M = (S, 80, A = UsEs A r Here S is a finite set of states, So S is the initial state, AA' is the finite set of available actions for state E 8, and (M 8, s,a) is the transition kernel, i.e, v(s,s') E S², Va E PMr'' | 8,0) 2 and
Vs E S, Ya E A', E'sEs Par(s' | 8, a) and the discount factor by y (0, 1). The interaction between the agent and the environment works as follows. At every step, the agent observes a state s and selects an action a E AA" yielding an instant reward TM a). The environment then transitions to a random new state s' E S drawn according to the distribution Pas (.1 8,a).
We denote the reward function by rM:: : :SxA + [0, 1]
Definition 2.2 (Policy). We say that a map क : + A is a (deterministic) stationary policy.
When we consider randomized policies we overload the notation and denote T($, a) the probability mass that policy и puts on action A in state 8 E S.
Definition 2.3 (Value (V) Function). The value function VM- S + [0, 1/(1>1] of a policy π with respect to the MDP M is given by (s) == E 1 at) 80 = 8] Here at ~ π (8t) and 8141
PM St, (z).
This is the expected discounted cumulative reward of policy. Definition 2.4 (Action- (Q) Function). The action-value (Q) function Qū : S x A + 10. 1/1-)] of a policy π with respect to the MDP M is given by (T,(s, == TM (M a) + 7 Eves (s ss a. VM (s').
We write N == LA4 to denote the number of state-action pairs. We denote by x the optimal policy that maximizes the value function, i.e., Vx, S: V*(() == V (s) V (s). We also define Q²(s,al a)= Q" (s, a). This quantity is well defined since the fundamental theorem of RL states that there exists a (deterministic) policy x' that simultaneously maximizes (s) among all policies x, for all E S (see e.g. Puterman [2014]).
Since estimating the optimal policy from samples when M is unknown could be an impossible task, we aim to compute an E-approximately optimal policy for M.
Definition 2.5 (Approximately Optimal Policy). Let e E (0, 1). We say that the policy a is e- approximately optimal if ||V* V* S.
In the above definition, || absolute value.
Ilso denotes the infinity norm of the vector, i.e., its maximum element in
Generative Model. Throughout this work, we assume we have access to a generative model (first studied in Kearn and Singh [1998]) or sampler Gm. which takes as input state-action pair (s, a) and provides a sample ~ PM 8, a). This widely studied fundamental RL setting allows us to focus on the sample complexity of planning over long horizon without considering the additional complications of exploration. Since our focus throughout this paper is on the statistical complexity of
*We assume that the reward is deterministic and known to the learner. Our results hold for stochastic and unknown rewards with an extra (replicable) estimation step, which does not increase the overall sample complexity.

---

the problem, our goal is to achieve the desired algorithmic performance while minimizing the number of samples from the generator that the algorithm requires.
Approximately Optimal Policy Estimator. We now define what it means for an algorithm aff to be an approximately optimal policy estimator.
Definition 2.6 ((E, 8) 8)-Optimal Policy Estimator). L,t (0, 1)2. A (randomized) algorithm of is called an (z, 80-optimal policy estimator if there exists a number n == ru(E,) 6) E N such that, for any MDP M, when it is given at least n25,, 6) samples from the generator Gm, it outputs policy î such S E with probability at least 1 - ó. Here, the probability is over random draws from Ga and the internal randomness of of
that | V*
Approximately optimal V-function estimators and Q-function estimators are defined similarly. Remark 2.7. In order to allow flexibility to the algorithm, we do not restrict to request the same amount of samples for every state-action pair. Thus n(e, 6) is bound on the total number of samples that af receives from G M- The algorithms we design request the same number of samples for every state-action pair, however, our lower bounds are stronger and hold without this restriction.
When the MDP M is clear from context, omit the subscript in all the previous quantities.
2.2 Replicability
Definition 2.8 (Replicable Algorithm; [Impagliazzo et al., 2022]). Let d' : I" + O be an n- sample randomized algorithm that takes as input elements from some domain I and maps them to some co-domain O. Let R denote the internal distribution over binary strings that af uses. For p E 1), P P3,S'=D",F SoR o (S; of :)) 2
say that of is p-replicable if for any distribution D over I it holds that
P. where (S: denotes the (deterministic) out- put of ef when its input is S and the realization of the internal random string i.
In the context of our work, we should think of s/ as a randomized mapping that receives samples from the generator G and outputs policies. Thus, even when S is fixed, s/( (S) should be thought of as a random variable, whereas el (5; is the realization of this variable given the (fixed) S, We should think of the shared randomness between the executions, which can be implemented as a shared random seed.
One of the most elementary statistical operations we may wish to make replicable is mean estimation. This operation can be phrased using the language of statistical queries.
Definition 2.9 (Statistical Query Oracle; [Kearns, 1998]). Let D be a distribution over the domain
X' and Φ : n + IR be statistical query with true value v* := lim o(X .x,) E R. Here X; s.i.d, D and the convergence is understood probability or distribution. Let e, 8 E (0, 1) 1)2 A statistical query (SQ) oracle outputs a value e such that |p v²1 s & with probability at least 1 - 8.
The simplest example of a statistical query is the sample mean (XI..... X.) = _ Σー X,. Impagliazzo et al. [2022] designed a replicable SQ-query oracle for sample mean queries with bounded co-domain (cf. Theorem C.I).
The following definition is the formal instantiation of Definition 2.8 in the setting we are studying.
Definition 2.10 (Replicable Policy Estimator). Let p E (0, 1). A policy estimator af that receives samples from generator G and returns policy using internal randomness R is p-replicable if for any MDP M, when two sequences of samples 5,5' are generated independently from G, it holds that TP s. S. ( / (S:F) of (S) 1-p.
To give the reader some intuition about the type of problems for which replicable algorithms under Definition 2.8 exist, we consider the fundamental task of estimating the mean of random variable. Impagliazzo et al. [2022] provided a replicable mean estimation algorithm when the variable is bounded (cf. Theorem C.I). Esfandiari et al. [2023b] generalized the result to simultaneously estimate the means of multiple random variables with unbounded co-domain under some regularity conditions on their distributions (cf. Theorem C.2). The idea behind both results to use rounding trick introduced in Impagliazzo et al. [2022] which allows one to sacrifice some accuracy of the estimator in favor of the replicability property. The formal statement of both results, which are useful for our work, are deferred to Appendix C.I.
5

---

3 Replicable Q-Function & Policy Estimation
Our aim in this section is to understand the sample complexity overhead that the replicability property imposes on the task of computing an (s, 5)- approximately optimal policy, Without this requirement, Sidford et al. [2018a], Agarwal et al. [2020], Li et al. [2020] showed that O(N log(1/s)/[(1 =))=² samples suffice to estimate such a policy. value function, and Q-function. Moreover, since Ghesh- laghi Azar et al. [2013] provided matching lower bounds the sample complexity for this problem has been settled. Our main results in this section are tight sample complexity bounds for locally random p-replicable (e, p-pppppprionnee optimal Q-function estimation well upper and lower bounds for p-replicable (c, -p-pprooximately policy estimation that differ by a factor of 1/(1-)). The missing proof' for this section can be found in Appendix D. We remark that both the presented algorithms and lower bounds, we assume local randomness. For example, we assume that the internal randomness is drawn independently for each state-action pair for replicable Q-estimation. In the case where we allow for the internal randomness to be correlated across estimated quantities, we present an algorithm that overcomes present lower bound in Section 4.3. However, the running time of this algorithm is exponential in N.
3.1 Computationally Efficient Upper Bound on the Sample Complexity
We begin by providing upper bounds on the sample complexity for replicable estimation of an approximately optimal policy and Q-function. On high level, we follow a two-step approach: 1) Start with black-box access to some Q-estimation algorithm that is not necessarily replicable (cf.
Theorem D.2) to estimate some Q such that IIQ* Qll 00 I Ep. 2) Apply the replicable rounding algorithm from Theorem C.2 as a post-processing step. The rounding step incurs some loss of accuracy in the estimated Q-function. Therefore, in order to balance between p-replicability and (e, -cccurcyy we need to call the black box oracle with an accuracy smaller than E, i.e. choose 6o < (sp)). This yields increase in the sample complexity which we quantify below. For the proof details, see Appendix D.
Recall that N is the number of state-action pairs of the MDP.
Theorem 3.1. Let p E (0,1)² 1)2 and E (0, 0/3). There is a locally random p-replicable algorithm that outputs an e-optimal Q-function with probability at least 1 - 8. Moreover, it has time and sample complexity O(N3 log()/s) //5)/((1 =) p21).
So far, we have provided replicable algorithm that outputs an approximately optimal Q function. The main result of Singh and Yee [1994] shows that if |1 Q 11 x S E, then the greedy policy with respect to Q i.e., Vs 8, 7 (s) := argmax Q(s, a), is s/proia-aproximmaaely optimal (cf. Theorem D.3). Thus, if we want to obtain an e-approximately optimal policy, it suffices to obtain a (1 ---7)))xppooxmmatt optimal Q-function. This is formalized in Corollary 3.2.
Corollary 3.2. Let E 1)² and ê E e/)). There is locally random p-replicable algorithm that outputs an s-optimal policy with probability at least 8. Moreover, it has time and sample complexity Ö (N3 log(1/s)(((1 - ?
Again, defer the proof to Appendix D.1.
Due to space limitation, the lower bound derivation is postponed Appendix D.
4 TV Indistinguishable Algorithms for Q-Function and Policy Estimation
In this section, we present an algorithm with an improved sample complexity for replicable Q- function estimation and policy estimation. Our approach consists of several steps. First, we design computationally efficient SQ algorithm for answering d statistical queries that satisfies the total variation (TV) indistinguishabiiiyy property [Kalavasis al., 2023] (cf. Definition 4.1), which can be viewed as relaxation of replicability. The new SQ algorithm has improved sample complexity compared to its replicable counterpart we discussed previously. Using this oracle, we show how we can design computationally efficient Qufunction estimation and policy estimation algorithms that
uup logarithmic factors

---

satisfy the TV indistinguishability definition and have an improved sample complexity by a factor of N compared to the ones in Section 3.1. Then, by describing specific implementation of its internal randommess, we make the algorithm replicable. Unfortunately, this step incurs an exponential cost in the computational complexity of the algorithm with respect to the cardinality of the state-action space. We emphasize that the reason we are able to circumvent the lower bound of Appendix D.2 is that we use a specific source of internal randomness that creates correlations across the random choices of the learner. Our result reaffirms the observation made by Kalavasis et al. [2023] that the same learning algorithm, i.e., input + output mapping, can be replicable under one implementation of its internal randomness but not replicable under different one.
First, we state the definition of TV indistinguishabiity from Kalavasis et al. [2023].
Definition 4.1 (TV Indistinguishability; [Kalavasis et al., 2023]). A learning rule of is n-sample p- TV indistinguishable for any distribution over inputs D and two independent samples S, ~ D" it holds that Bs [drv (A(S), A(S)) p.
In their work, Kalavasis et al. [2023] showed how to transform any p-TV indistinguishable algorithm to 2p/ (1 p) rreplicabee one when the input domain is countable. Importantly, this transformation does not change the input - output mapping that is induced by the algorithm. A similar transfor- mation for finite domains can also be obtained by the results in Bun al. [2023]. We emphasize that neither of these two transformations are computationally efficient. Moreover, Bun et al. [2023] give cryptographic evidence that there might be inherent computational hardness to obtain the transformation.
4.1 TV Indistinguishable Estimation of Multiple Statistical Queries
We are now ready to present TV -i-iiiistinguuihabll algorithm for estimating dl independent statistical queries. The high-level approach is as follows. First, we estimate each statistical query up to accuracy <P/Va using black-box access to the SQ oracle and we get estimate îū E [0, 1j Then, the Since the estimated mean of each query is
output of the algorithm is drawn from "( accurate up to sn/va and the variance is e2, we can see that, with high probability, the estimate of each query will be accurate up to Oee). To argue about the TV indistinguishabiiity property, we first notice that, with high probability across the two executions, the estimate ñ02 E [0, 1] satisfies 1171 - 7oallso & 2p- aopee/il e/Vd. Then, we can bound the TV distance of the output of the algorithm La)) S O(p) [Gupta, 2020J. We underline that this behavior is
as drv e" reminiscent of the advanced composition theorem in the Differential Privacy (DP) literature (see e.g.. Dwork et al. [2014]) and our algorithm can be viewed as an extension of the Gaussian mechanism from the DP line of work to the replicability setting. This algorithm has applications outside the scope of our work since multiple statistical query estimation is a subroutine widely used in the replicability line of work [Impagliazzo al., 2022, Esfandiari et al., 2023b,a, Bun et al., 2023, Kalavasis et al., 2023]. This discussion is formalized in the following theorem.
Theorem 4.2 (TV Indistinguishable SQ Oracle for Multiple Queries). Let E, E (0, 1)2 and 6 E (0, p/s). Let $1...., Da be d statistical queries with co-domain [0, 1]. Assume that we can simultaneously estimate the true values of all ø. 's with accuracy E and confidence 8 using n(e, 5) total samples. Then, there exists a p-TV indistinguishable algorithm (Algorithm A. that requires at most //de//2//dd 8/2) many samples to output estimates Uj,..., L2 of the true values U1...., Ua to guarantee that max,e[4] 60 vil S with probability at least 1 6.
4.2 TV Indistigguishable Q-Function and Policy Estimation
Equipped with Algorithm A. we are now ready to present a -n--iiiiiinguisaall algorithm for Q-function estimation and policy estimation with superior sample complexity compared to the one in Section 3.1. The idea is similar the one in Section 3.1. We start with black-box access to an algorithm for Q-function estimation, and then we apply the Gaussian mechanism (Algorithm A. We remark that the running time of this algorithm is polynomial in all the parameters of the problem.
Recall that N is the number of state-action pairs of the MDP.
Theorem 4.3. Let p (0, 1)2 and 5 E (0, (/3). There is a p-TV indistinguishable algorithu that outputs an e-optimal Q Q-function with probability at least 1 - 8. Moreover, it has time and sample complexity ő ( log(1/s)/[(1 >))==pp'))
7

---

Proof. The proof follows by combining the guarantees of Sidford et al. [2018a] (Theorem D.2) and Theorem 4.2. To be more precise, Theorem D.2 shows that in order to compute some Q such that ll -Il 0c S ,, one needs O(N (1/0/)/|((111(())))) Thus, in order apply Theorem 4.2 the sample complexity becomes Ö(N log( /0)/[(/
Next, describe TV indistinguishable algorithm that enjoys similar sample complexity guar- antees. Similarly as before, we use the main result of Singh and Yee [1994] which shows that if 12 - Q-1 I e, then the greedy policy with respect to @ i... Vs E S, fss) :- argmax A. ((s, a), is =/pp--)--pproximaaely optimal (ef. Theorem D.3). Thus, if we want to obtain an e-approximately optimal policy, it suffices to obtain a (1 - app-approx optimal Q-function. The indistinguishable guarantee follows from the data-processing inequality This is formalized in Corollary 4.4.
Corollary 4.4. Let e, E (0, 1)2 and 8 E (0, There p-TV indistinguishable algorithm that outputs s-optimal policy with probability least - 8. Moreover, it has time and sample complexity O(N log( (o)(//))[(11 =²))).
4.3 From TV Indistinguishabiiity to Replicability
We now describe how we can transform the TV indistinguishable algorithms we provided to replicable ones. As we alluded to before, this transformation does not hurt the sample complexity, but requires exponential time the state-action space. Our transformation is based on the approach proposed by Kalavasis et al. [2023] which holds when the input domain is countable. Its main idea is that when two random variables follow distributions that are p-close in TV -iiititteee,, then there is a way to couple them using only shared randomness. The implementation of this coupling is based on the Poisson point process and can be thought of generalization of von Neumann's 's rejection-base sampling to handle more general domains. We underline that in general spaces without structure it is not known yet how to obtain such a coupling. However, even though the input domain of the Gaussian mechanism is uncountable and the result of Kalavasis et al. [2023] does not apply directly in our setting, we are able to obtain a similar transformation as they did. The main step required to perform this transformation is find reference measure with respect which the algorithm is absolutely continuous. We provide these crucial measure- -theorettcc definitions below.
Definition 4.5 (Absolute Continuity). Consider two measures P, P on a o-algebra B of subsets of W. We say that P is absolutely continuous with respect to P if for any E E B such that P(E) 0. it holds that P ((E)
Recall that sf (S) denotes the distribution over outputs, when the input to the algorithm is S. Definition 4.6. Given learning rule af and reference probability measure P, we say that of is absolutely continuous with respect to P if for any input S, (S) is absolutely continuous with respect to P.
We emphasize that this property should hold for every fixed sample S, i.e., the randomness of the samples are not taken into account.
We now define what it means for two learning rules to be equivalent.
Definition 4.7 (Equivalent Learning Rules). Two learning rules s, a are equivalent if for every fixed sample S, it holds that (S) d df"( i.c., for the same input they induce the same distribution over outputs.
Using coupling technique based on the Poisson point process, we can convert the TV indis- tinguishable learning algorithms we have proposed so far to equivalent ones that are replicable. See Algorithm A.2 for description of how to output sample from this coupling. Let us view (S:r), s/ (S);r) as random vectors with small TV distance. The idea is to implement the shared internal randomness using rejection sampling so that the "accepted" sample will be the same across two executions with high probability. For some background regarding the Poisson point process and the technical tools we use, we refer the reader Appendix C.2.
Importantly, for every S. the output a (S) of the algorithms we have proposed in Section 4.1 and Sec- tion 4.2 follow a Gaussian distribution, which is absolutely continuous with respect to the Lebesgue
8

---

measure. Furthermore, the Lebesgue measure is o-finite so we can use the coupling algorithm (cf. Algorithm A.2) of Angel and Spinka [2019], whose guarantees are stated in Theorem C.4. We are now ready to state the result regarding the improved p-replicable SQ oracle for multiple queries. Its proof is an adaptation of the main result of Kalavasis al. [2023].
Theorem 4.8 (Replicable SQ Oracle for Multiple Queries). Let E, p (0, 1)2 and ò e/s). Let .1...., dd be d statistical queries with co-domain [0, 1]. Assume that we can simultaneously estimate the true values of all 0; 's with accuracy and confidence 6 using n(e, 8) total samples. Then, there exists a p-replicable algorithm that requires at most n n(ep/(4 [Av (ogl4//)))))) 8/2) many samples to output estimates vi..... .d of the true values U1, .i......0 Vd with the guarantee that max,e [0; v.l S E, with probability at least 1 1-66 5.
By using an identical argument, we can obtain p-replicable algorithms for Q Q-function estimation and policy estimation. Recall that N is the number of state-action pairs of the MDP.
Theorem 4.9. Let e, E (0, and d E P/4). There is a p-replicable algorithm that out- puts an e-optimal Q-function with probability at least 1 - 6. Moreover, it has sample complexity Ö(N²
- =-)=2p²))
Corollary 4.10. Let p, E 10, and ó E (0, 9/4). There is p-replicable algorithm that out- puts an e-optimal policy with probability at least 5. Moreover, has sample complexity Ö(N² log(o///ooo ())))//((111)888
In Remark E.2 we explain why we cannot a coordinate- coupling.
5 Approximately Replicable Policy Estimation
The definitions of replicability (cf. Definition 2.10, Definition 4.1) we have discussed so far suffer from a sigmificant sample complexity blow-up in terms of the cardinality of the state-action space which can be prohibitive in many settings of interest. In this section, propose approximate replicability, a relaxation of these definitions, and show that this property can be achieved with a significantly milder sample complexity compared to (exact) replicability. Moreover, this definition does not require shared internal randomness across the executions of the algorithm.
First, we define a general notion of approximate replicability as follows.
Definition 5.1 (Approximate Replicability). Let X, y be the input and output domains, respectively. Let K : y y -> Rzg be some distance function on Y and let Pl. P2 (0, 1)2. We say that an algorithm a is (a replicable with respect to k. if for any distribution DD over X (S:;
holds that "s..""""..rr'
of (S::r") r')) 2 p1) S P2.
In words, this relaxed version of Definition 2.8 requires that the outputs of the algorithm, when executed on two sets of i.i.d. data, using independent internal randomness across the two executions, close under some appropriate distance measure. In the context of our work, the output of the learning algorithm is some policy т : + A(A), where ((A) denotes the probability simplex over A. Thus, it is natural to instantiate 6 as some dissimilarity measure of distributions like the total variation (TV) distance or the Renyi divergence. For the exact definition of these dissimilarity measures, we refer the reader to Appendix B. We state the definition of an approximately replicable policy estimator.
Definition 5.2 (Approximately Replicable Policy Estimator). Let a be an algorithm that takes as input samples of state-action pair transitions and returns a policy w. Let be some dissimilarity measure on A (LA) and let P1, P2 E 1)2. We say that / is (pi, P2) apprrxxiiity replicable for any MDP M holds that P...S'GG,.. {max,es <(T(s), n' (s)) 2 p1 S P2, where G is the generator of state-action pair transitions, R is the source of internal randomness of s, π is the output of of on input S, r, and n is its output on input S', r'
To the best of our knowledge, the RL algorithms that have been developed for the model we are studying do not satisfy this property. Nevertheless, many of them compute an estimate Q with the promise that ||Q Q*Il,- < & [Sidford et al., 201 8a, Agarwal et al., 2020, Li et al., 2020]. Thus, it not hard to see that if we run the algorithm twice on independent data with independent internal randomness have that ||Q Q'ilao 2s. This is exactly the main property that we need in order

---

to obtain approximately replicable policy estimators. The key idea is that instead of outputting the greedy policy with respect to this Q-function, we output a policy given by some soft-max rule. Such a rule is a mapping IR50 + ((A) that achieves two desiderata: (i) The distribution over the actions is "stable" with respect to perturbations of the Q-function. (ii) For every & E S, the value of the policy V* that is induced by this mapping is "close" to (s).
Formally, the stability of the soft-max rule is captured through its Lipschitz constant (cf. Defini- tion B.3). In this setting, this means that whenever the two functions Q, Q'' are close under some distance measure (e-g. the la norm), then the policies that are induced by the soft-max rule are close under some (potentially different) dissimilarity measure. The approximation guarantees of the soft-max rules are captured by the following definition.
Definition 5.3 (Soft-Max Approximation; [Epasto et al., 2020D). Let & > 0. A soft-max function f: + (AA s-approximate if for all x E RA,, (f(x), x) 2 maXae Ta -.
In this work, we focus on the soft-max rule that is induced by the exponential function (ExpSoftMaxx), which has been studied in several application domains [Gibbs, 1902 McSherry and Talwar, 2007, Huang and Kannan, 2012, Dwork et al., 2014, Gao and Pavel, 2017]. Recall <(8, a) denotes the probability mass that policy ग puts on action a A in state E S. Given some À >> 0 and exp(AQ(e..)) ((s, a) E SxA, the induced randomized policy π is given by T(s, a) = En'ea" exp (AQtx.aaaa)]] For discussion about the advantages of using more complicated soft-max rules like the one developed in Epasto et al. [2020]. we refer the reader to Appendix F.I.
We now describe our results when we consider approximate replicability with respect to the Renyi divergence and the Total Variation (TV) distance. At high level, our approach is divided into two steps: 1) Run some Q-learning algorithm (e.g. [Sidford et al., 2018a, Agarwal et al., 2020, Li et al., 2020]) to estimate some Q such that ||Q - Q1l I 2) Estimate the policy using some soft-mat rule. One advantage of this approach is that it allows for flexibility and different implementations of these steps that better suit the application domain. An important lemma we use is the following.
Lemma 5.4 (Exponential Soft-Max Approximation Guarantee; [McSherry and Talwar, 2007]). Let E E (0, 1), a 2 1, and set X = log(d)/s, where is the ambient dimension of the impul domain. Then, ExpSoftMax with parameter X is s-approximate and 2X- --pisscchitz continuous (cf. Definition B.3) with respect to (lp, Da),, where Da is the Renyi divergence of order a.
This is important building block of our proof. However, it is not sufficient on its own in order to bound the gap of the ExpSoftMax policy and the optimal one. This is handled in the next lemma whose proof is postponed to Appendix F. Essentially, can be viewed as an extension of the result in Singh and Yee [1994] to handle the soft-max policy instead of the greedy one.
Lemma 5.5 Max Policy vs Optimal Policy). Let e1, 82 E (0, 1)2. Les Q E R be such that @ @-1 || < 11. Let t be the ExpSoft policy with respect to Q using parameter X = loglAl/ez.
Then, V v*1l_ < (221+ta)/(1-7).
Combining Lemma 5.4 and Lemma 5.5 yields the desired approximate replicability guarantees we seek. The formal proof of the following result postponed to Appendix F. Recall we write N : Eses to denote the total number of state-action pairs.
Theorem 5.6. Let a 2 1,7,8,PI, PI, P2 E 1)², and E (0- There is a (pr, P2)- approximately replicable algorithm a with respect to the Renyi divergence Dr such that given access generator G for any MDP M, it outputs a policy ât for which I|V* - VVIl S e with probability at least - 8. Moreover, of has time and sample complexity (og(
Conclusion
In this work, we establish sample complexity bounds for a several notions of replicability in the context of RL. We give an extensive comparison of the guarantees under these different notions in Appendix G. We believe that our work can open several directions for future research. One immediate next step would be to verify our lower bound conjecture for replicable estimation of multiple independent coins (cf. Conjecture D.8). Moreover, it would be very interesting to extend our results to different RI. settings, e.g. offline RL. with linear MDPs, offline RL. with finite horizon, and online RL.
10

---

Acknowledgments
Amin Karbasi acknowledges funding direct support of this work from NSF (IS-1845032), ONR (N00014-19-1-2400) and the AI Institute for Yearning-Enabler Optimization at Scale (TILOS). Lin Yang is supported in part by NSF Award 2221871 and an Amazon Faculty Award. Grigoris Velegkas is supported by TILOS, the Onassis Foundation, and the Bodossaki Foundation. Felix Zhou supported by TILOS. The authors would also like to thank Yuval Dagan for an insightful discussion regarding the Gaussian mechanism.
References
M Mehdi Afsar, Trafford Crump, and Behrouz Far. Reinforcement learning based recommender systems: A survey. ACM Computing Surveys, 55(7):1-38, 2022.
Alekh Agarwal, Sham Kakade, and Lin F Yang. Model- reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory, pages 67-83. PMLR, R, 2020.
Omer Angel and Yinon Spinka. Pairwise optimal coupling of multiple random variables. arXiv preprint arXiv:1903.003:: 2019.
Monya Baker. 1,500 scientists lift the lid reproducibility. Nature, 533(7604), 2016.
Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L Rivest, and Madhu Sudan. Optimality of correlated sampling strategies. arXiv preprint 101iv:1612.01041 2016.
Dimitri P Bertsekas. Dynamic programming and stochastic control. Academic Press, 1976.
Andrei Z Broder. On the resemblance and containment of documents. In Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No. 971B/00171), pages 21-29. IEEE, 1997.
Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell, and Satchit Sivakumar. Stability is stable: Connections between replicability, privacy, and adaptive generalization. arXiv preprint ArXiv:2303. 12921, 2023.
Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 380-388, 2002.
Zachary Chase, Shay Moran, and Amir Yehudayoff. Replicability and stability in learning. arXiv preprint arXiv:2304.03375, 2023.
Peter Dixon, A Pavan, Jason Vander Woude, and NV Vinodchandran. List and certificate complexities in replicable learning. arXiv preprint arXiv:2304.02244 02240, 2023.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends Theoretical Computer Science, 9(3-4):211-40) 2014.
Eric Faton, Marcel Hussing, Michael Kearns, and Jessica Sorrell. Replicable reinforcement learning. arXiv preprint arXiv:2005.15284 2023.
Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni, and Emmanouil Zampetakis. Optimal poproximatioonsmoottnees tradeoff's for soft-max functions. Advances in Neural Information Processing Systems, 33:2651-26660 2020.
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. arXiv preprint 2mXiv:2302.10359 2023b.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for nulti-armed bandit and markov decision processes. In COLT, volume 2, pages 255-270. Springer, 2002.

---

Meta Fundamental AI Research Diplomacy Team (FAIR),, Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, et al. Human-level play in the game of diplomacy by combining language models with strategic 2022.
reasoning. Science, (78(6624):1067-1111
Fei Feng, Wotao Yin, and Lin F Yang. How does an approximate model help in reinforcement learning? arXiv preprint 0aXiv:9912.029860 2019.
Bolin Gao and Lacra Pavel. On the properties of the softmax function with application in game theory and reinforcement learning. arXiv preprint arXiv:/704. 00805, 2017.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91: 325-349, 2013.
Josiah Willard Gibbs. Elementary principles in statistical mechanics: developed with especial reference to the rational foundations of thermodynamics. C. Scribner's sons, 1902.
Rishabh Gupta. KI divergence between 2 gaussian distributions, 2020. URL htLpstts::/n github. iochub..o/20200044 1al---00----11----eeee-------- weweergeneebbeeeeeeen-----
between
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
Thomas Holenstein. Parallel repetition: simplifications and the no-signaling case. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 41 411-419,,000
Zhiyi Huang and Sampath Kannan. The exponential mechanism for social welfare: Private, truthful, and nearly optimal. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 140-149. IEEE, 2012.
Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. arXiv preprint arXiv:2201.08433 2022.
Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistinguishabiliy of learning algorithms. arXiv preprint arXiv:2305. /4311, 2023.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6):983-1006, 1998.
Michael Kearns and Satinder Singh. sample convergence rates for q-learning and indirect algorithms. Advances in neural information processing systems, 11, 1998.
Khimya Khetarpal, Zafarali Ahmed, Andre Cianflone, Riashat Islam, and Joelle Pineau. Re-evaluate: Reproducibility in evaluating reinforcement learning algorithms.(2018) International confer- ence on machine learning. ICML, 2018
B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions Intelligent Transportation Systems, (3(6):490944926 2021.
Jon Kleinberg and Eva Tardos.
Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields. Journal of the ACM (JACM), 49(5): 616-639, 2002.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathemat- ical Soc., 2017.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances in neural information processing systems, 33: 1-61-2 2020.
Shie Mannor and John N Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5(Jun):623 2004.
12

---

Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 94-103. IEEE, 2007.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.500,, 2013.
Long Ouyang, Jeffrey Wu, Xu Jiang. Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744, 2022.
Joelle Pineau, Koustuv Sinha, Genevieve Fried, Rosemary Nan Ke, and Hugo Larochelle. Iclr reproducibility challenge 2019. ReScience C, 5(2):5, 2019.
Joelle Pineau, Philippe Vincent-Lamare Koustuv Sinha, Vincent Larivière, Alina Beygelzimer, Florence d' Alché Buc, Emily Fox, and Hugo Larochelle. Improving reproducibility in machine learning research: report from the neurips 2019 reproducibility program. Journal of Machine Learning Research, 22, 2021.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. Advances in Neural Information Processing Systems, 31, 2018a.
Aaron Sidford, Mengdi Wang. Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 770-787. SIAM, 2018b.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-22 359, 2017.
Satinder P Singh and Richard C Yee. An upper bound on the loss from approximate optimal-value functions. Machine Learning, 16:227-233, 1994.
Yuandong Tian, Jerry Ma, Qucheng Gong, Shubho Sengupta, Zhuoyuan Chen, James Pinkerton, and Larry Zitnick. Elf opengo: An analysis and open reimplementation of alphazero. In International conference on machine learning, pages
PMLR, 2019.
Leslie G Valiant. theory of the learnable. Communications of the ACM, 27(11::1134-1122 1984.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung. David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)3350-354 2019.
Mengdi Wang. Randomized linear programming solves the discounted markov decision problem in nearly-linear (sometimes sublinear) running time. arXiv preprint arXiv: (ete::704000066 2017.
Andrew Chi-Chin Yao. Probabilistic computations: Toward unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 222-227 IEEE Computer Society, 1977.
Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healtheare: survey, ACM Computing Surveys (CSUR), 55(1):1-36, 2021.
13

---

A Omitted Algorithms
Algorithm A.1 TV Indistinguishable Oracle for Multiple Query Estimation
1: j ( (........ pd)
StatistiealQuuryOracles
8
2: Sample 8 N c² /(8 log(Ad/6)) Ta)
3: Output
Algorithm A.2 Sampling from Pairwise Optimal Coupling; [Angel and Spinka, 2019]
1: Input: collection of random vectors S {X} absolutely continuous with respect o-finite
measure μs, with densities fx I& + R, some X E S
2: Let denote the Poisson point process over IRd IR,, x R2 with intensity μ Leb Leb.
3: Sample r == [(1g, Vs, 4.) : NJ ~ R.
4: Let i" + argmin [t; fs( > y.}.
5: Output z;- as a sample for X.
B Omitted Definitions
In this section, we discuss some dissimilarity measures for probability distributions that we use in this work.
Definition B.1 (Total Variation (TV) Distance). Let f2 be a countable domain and P.Q probability distributions over Q. The total variation distance between P. Q, denoted by (P,()))) is defined as
dIv(P,Q) = sup P(A) - Q(4)
Ae20
=IP Q11
inf (X(Y)-((P..))
P(X 4Y),
where II(P, Q) is coupling between P.Q.
In the above definition, coupling is defined to be joint probability distribution (X,Y) II(P.Q) over the product space whose marginals distributions are P, Q. i.e., if we only view the individual components, then X P,Y Q.
Definition B.2 (Renyi Divergence). Let Ω be a countable domain and P. Q be probability distributions over Ω. For any a the Renyi divergence of order a between P, Q. denoted by (PIIQ) is defined as
P(w)a
Da(PI(Q)
log Σ
Q(w)-I
WER
We note that the quantity above is undefined when However, take its limit and define P(w)
(P(lQ) = Ewen P(w) log Quo which recovers definition of KL-divergence. Similarly, we
can define (PII)) = maxwen Q())
P(w)
Another important definition is that of Lipschitz continuity.
Definition B.3 (Lipschitz Continuity). Let X, be two domains, f: X' Y be func- tion, and d, X' x X >> Rzo, d2 : y x y - Ryo be distance measures over X, respec- tively. We say that f is L-Lipschitz continuous with respect d,, d2 if Væ1, E A it holds that d2 ((1)), & L- L-di(zi (1(,))
B.1 Local Randomness
Our algorithms in Section 3 satisfy a property which we call locally random. This roughly means that for every decision an algorithm makes based on external and internal randomness, the internal randomness is used once and discarded immediately after.
14

---

Definition B.4 (Locally Random), Let o .....,((NN)) I - R be an n-sample randomized algorithm that takes as imput elements from some domain I and maps them RV We say that of is locally random if:
(i) The i-th output component of (5; is function of all samples $ but only its own internal random string p())
iii) The sources p(() of internal randomness are independent of each other and the external samples S.
We will see that by restricting ourselves to locally random algorithms, it is necessary and sufficent to incur sample cost of ((N²) for replicable Q-estimation. However, by relaxing this restriction and allowing for internal randomness that is correlated, achieve ((N2) sample complexity.
C
Omitted Preliminaries
C.1 Replicability
Impagliazzo al. [2022] introduced the definition of replicability and demonstrated the following basic replicable operation.
Theorem C.1 (Replicable SQ-Oracle; [Impagliazzo et al., 2022]). Let p. E (0, 1) and 8 E (0. p/s).
Suppose d is sample mean statistical query with co-domain [0, 1]. There is locally random p-replicable SQ oracle to estimate true value with tolerance & and failure rate 5. Moreover, the oracle has sample complexity
ò 0 log
Esfandiari et al. [2023b] generalized the result above to multiple general queries with unbounded co-domain, assuming some regularity conditions on the queries.
Theorem C.2 (Replicable Rounding; [Impagliazzo al., 2022, Esfandiari al., 2023b]). Ler E,P E (0. 1) and & E (0, f/3). Suppose we have finite class of statistical queries ......, 9N with true values G....., G and sampling independent points from ensures that
(E -Gyl G E(p 25)
p 26
with probability at least 1
There a locally random p-replicable algorithm that outputs estimates G, such that
G GGyl
with probability at least for every j [N). Moreover, it requires at most n samples.
C.2 Coupling and Correlated Sampling
Our exposition in this section follows Kalavasis et al. [2023]. Coupling is a fundamental notion in probability theory with many applications [Levin and Peres, 2017]. The correlated sampling problem, which has applications in various domains, e.g., in sketching and approximation algorithms [Broder, 1997. Charikar, 2002], described in Bavarian al. [2016] as follows: Alice and Bob are assigned probability distributions PA and PB. respectively, over finite set W. Without any communication, using only shared randomness as the means coordinate, Alice is required output an element x distributed according to PA and Bob is required to output an element distributed according to PB- Their goal to minimize the disagreement probability Pfr * y}. which is comparable with drv (PA, PB). Formally. correlated sampling strategy for a finite set W with error 8 [0, 1] + [0, 1] specified by a probability space and a pair of functions f,g g Aw x R - W. which are measurable in their second argument, such that for any pair PA, Pp Aw with Vrrv(Pn, PB)) S 5, holds that (i) the push-forward measure f(PA.)) (resp. g( (P.: :) is PA (resp. PB) and (ii) P. TP..T) + r(PB,r)) I =(6). We underline that correlated
15

---

sampling strategy is not the same as a coupling, in the sense that the latter requires single function Aw x Aw - Awxw such that for any PA. PB. the marginals of h(PA, PB) are PA and PB respectively.
It is known that for any coupling function h, it holds that P (a..)) (+ # y) 2 drv (PA, Pb) and that this bound is attainable. Since (f(Pa:)) (.g((..)) induces coupling, it holds that E(0) 2 8 25
and, perhaps surprisingly, there exists strategy with =(6) S I+5 [Broder, 1997, Kleinberg and Tardos, 2002, Holenstein, 2007] and this result is tight [Bavarian et al., 2016]. A second difference between coupling and correlated sampling has do with the size of W: while correlated sampling strategies can be extended to infinite spaces W, it remains open whether there exists correlated sampling strategy for general measure spaces FW μ1) with any non-trivial error bound [Bavarian et al., 2016]. On the other hand, coupling applies to spaces W of any size. For further comparisons between coupling and the correlated sampling problem of Bavarian et al. [2016], we refer to the discussion in Angel and Spinka [2019] after Corollary 4.
Definition C.3 (Coupling). A coupling of two probability distributions PA and P8 is pair of random variables (X, )) defined on the same probability space, such that the marginal distribution of X is PA and the marginal distribution of Y is PB-
A very useful tool for our derivations is a coupling protocol that can be found in Angel and Spinka [2019].
Theorem C.4 (Pairwise Optimal Coupling [Angel and Spinka, 2019]). Let S be any collection of random variables that are absolutely continuous with respect to a a-finite measure μ.. Then, there exists a coupling of the variables in S such that for any X.Y E,
2dTv(X (X,Y)
P(X+ 1+
Moreover, this coupling requires sample access to a Poisson point process with intensity μx Leb x Leb, where Leb is the Lebesgue measure over Rt,, and full access to the densities of all the random variables in S with respect to Finally, we can sample from this coupling using Algorithm A.2.
D Omitted Details from Section 3
Here fill in the details from Section 3, which describes upper and lower bounds for replicable Q- function and policy estimation. In Appendix D.I, we provide the rigorous analysis of an algorithm for locally random replicable Q-function estimation as well replicable policy estimation. Appendix D.3 describes the locall random replicable version of the multiple coin estimation problem, an elementary statistical problem that serves the basis of our hardness proofs. Next, Appendix D.4 reduces locally random replicable Q-function estimation to the multiple coin estimation problem. Finally, Appendix D.5 reduces deterministic replicable policy estimation to locally random replicable Q- function estimation.
D.1 Omitted Details from Upper Bounds
First, we show that we can use any non-replicable Q- Q-function estimation algorithm as a black-box to obtain a locally random replicable Q-function estimation algorithm.
Lemma D.1. Let E't'',8' E (0, 1). Suppose there is an oracle 6 that takes (((((NE',8)) samples
from the generative model and outputs Q satisfying I! Q* 00 S e' with probability at least 1 - 8'.
Let E.p E (0, 1) and 8 E (0.s/s). There is a locally random p-replicable algorithm which makes a single call to O and outputs some Q satisfying I|Q 1 Q" x0 < E with probability at least 1 8. Moreover, it has sample complexity Ō (f (N, So/N, 6)) where so == =lp-26)/(0+1-26;
Proof (Lemma D. Consider calling & with Ö([(N, Eo/N, 5)) samples. This ensures that
Σ ((s,a) Q* a) S cu
16

---

with probability at least 1 - 5. By Theorem C.2, there is locally random p-replicable algorithm that
makes single call to O with the number of samples above and outputs Q(s, a) such that
| - Q'1 Se
with probability of success of at least 1 6.
Sidford et al. [2018a] 8a] showed (non-replicable) Q function estimation algorithm which has optimal (non-replicable) sample complexity up to logarithmic factors.
Recall we write N = Esesh AA*l to denote the total number of state-action pairs.
Theorem D.2 ([Sidford al., 2018a]). Let e, E (0,1), there an algorithm that outputs an E-optimal policy, e-optimal value function, and e-optimal Q-function with probability at least 1 - for any MDP. Moreover, has time and sample complexity
o (
1 log 8)
The proof of Theorem 3.1, which we repeat below for convenience, follows by combining Lemma D.1 and Theorem D.2.
Theorem 3.1. Let E 10, and E (0,)/3). There a locally random p-replicable algorithm that oulputs an 8-optimal Q-function with probability at least 1 - 8. Moreover, it has time and sample complexity O(N3 log(//))
") p²))
The following result of Singh and Yee [1994] relates the Q-function estimation error to the quality of the greedy policy with respect to the estimated Q-function.
Theorem D.3 ([Singh and Yee, 1994]). Let @ be Q-function such that || - Q2 S E. Let (s) = arg maXaes @(s,a), S. Then,
| -V S 7
E
Theorem D.3 enables us to prove Corollary 3.2, upper bound on the sample complexity of replicably estimating an e-optimal policy. We restate the corollary below for convenience.
Corollary 3.2. E, E 10 and â E o/s). There is a locally random p-replicable algorithm that outputs an e-optimal policy with probability least 8. Moreover, has time and sample complexity ((N3 log()/)) - =2
Proof (Corollary 3.2). Apply the p-replicable algorithm from Theorem 3.1 to yield an co-optimal
Q-function and output the greedy policy based on this function. Theorem D.3 guarantees that the greedy policy derived from an co-optiaal Q-function is en/(->>-optimal. Choosing en == (1 - 7) yields the desired result.
The replicability follows from the fact that conditioned on the event that the two Q-functions across the two runs are the same, which happens with probability at least 1 - the greedy policies with respect the underlying Q-functions will also be the s
D.2 Lower Bounds for Replicable Q-Function & Policy Estimation
We now move on to the lower bounds and our approaches obtain them. First, we describe a sample complexity lower bound for locally random p-replicable algorithms that seek to estimate Q" Then, we reduce policy estimation Q-estimation. Since the dependence of the sample complexity on the confidence parameter of the upper bound is at most polylogarithmic, the main focus of the lower bound on the dependence on the size of the state-action space N, the error parameter e, replicability parameter and the discount factor 7.
"assuming consistent tie- breakia rule
17

---

D.2.1 Intuition of the Q-Function Lower Bound
Our MDP construction that witnesses the lower bound relies on the sample complexity lower bound for locally random algorithms that replicably estimate the biases of multiple independent coins. Impagliazzo et al. [2022] showed that any p-replicable algorithm that estimates the bias of a single coin with accuracy ε requires at least (2(/0=²²) samples (cf. Theorem D.13), We generalize this result and derive a lower bound for any locally random p-replicable algorithm that estimates the biases of N coins with accuracy & and constant probability of success. We discuss our approach in Appendix D.2.2.
Next, given some E, P, we design an MDP for which estimating an approximately optimal Q-function is at least as hard as estimating N coins. The main technical challenge for this part of the proof is establish the correct dependence on the parameter y since it is not directly related to the coin estimation problem. We elaborate on it in Remark D.7.
Remark D.4. Our construction, combined with the non-replicable version of the coin estimation problem, can be used simplify the construction of the non-replicable Qestiimation lower bound from Gheshlaghi Azar et al. [2013].
D.2.2 The Replicable Coin Estimation Problem
Formally, the estimation problem, without the replicability requirement, is defined follows.
Problem D.5 (Multiple Coin Problem). Fix q, q,E.& 8 E 1) such that q E (1/,, 1). Given sample access to N independent coins each with bias of either 9 or q determine the bias of every coin with confidence at least 1 - 5.
We now informally state our main result for the multiple coin estimation problem, which could be useful in deriving replicability lower bounds beyond the scope of our work. See Theorem 1.16 for the formal statement. Intuitively, this result generalizes Theorem D.13 to multiple instances.
Theorem D.6 (Informal). Suppose of is a locally random p-replicable algorithm for the multiple coin problem with a constant probability of success. Then, the sample complexity of sl is at least
N NN9((19)
Ω
22p2
Recall Yao's min-max principle [Yao, 1977], which roughly states that the expected cost of randomized algorithm on its worst-case input is at least as expensive as the expected cost of any deterministic algorithm on random inputs chosen from some distribution. is not clear how apply Yao's principle directly, but we take inspiration from its essence and reduce the task of reasoning about randomized algorithm with shared internal randomness to reasoning about a deterministic one with an additional layer of external randomness on top of the random flips of the coins.
Consider now deterministic algorithm g for distinguishing the bias of single coin where the input bias is chosen uniformly in iq - E, q). That is, we first choose p ~ Ulg E, 9]. then provide i.i.d. samples from Be(p) to g. We impose some boundary conditions: if p = q - e. g should output "_" with high probability and if p g, the algorithm should output "+" with high probability. We show that the probability of g outputting "+" varies smoothly with respect to the bias of the input coin. Thus, there is an interval I C (q s, g) such that g outputs "-" or "+" with almost equal probability and so the output of g inconsistent across two executions with constant probability when p lands in this interval. By the choice of U[q E, q]. if E(L) denotes the length of 1, then the output of g inconsistent across two executions with probability least ((fL)fc). Quantifying {(T) and rearranging yields the lower bound for single coin.
For the case of N independent coins, we use the pigeonhole principle to reduce the argument to the case of a single coin. The formal statement and proof of Theorem D.6 is deferred to Appendix D.3. Remark D.7. The lower bound from Impagliazzo et al. [2022] for the single-coin estimation problem holds for the regime g, 9 e E (1/4, 3/4). We remove this constraint by analyzing the dependence of the lower bound on q. When reducing Q-function estimation to the multiple coin problem, the restricted regime yields a lower bound proportional to - 7)-2, In order derive the stronger lower bound of (1 ( (1-7)-3 we must be able to choose R ? which can be arbitrarily close to 1.
In Section 4, we show that allowing for non-locally random algorithms enables us to shave off factor of N in the sample complexity. We also conjecture that this upper bound is tight.
18

---

Conjecture D.8. Suppose (d")) ...... x(M); F) is randomized p-replicable algorithm for the multiple coin problem and has a constant probability of success. Then, the sample complexity of af is at least
N2 1N2((19) ?
D.2.3 A Lower Bound for Replicable Q-Function Estimation
We now present the MDP construction that achieves the desired sample complexity lower bound. We define family of MDPs MI depicted in Figure D.I. This particular construction first presented by Mannor and Tsitsiklis [2004] and generalized by Gheshlaghi Azar et al. [2013]. Feng et al. [2019].
Any MDP M E M is parameterized by positive integers KM, LM- and some PM E [0, 1] for E ( & E [ The state space of M is the disjoint union' of three sets S = X' L where
(k.E)
The X' consists of K states (21,...,,2) and each of them has L available actions (01,-- (01.-..: Oz) =: A.
All states in V. Z have a single action that the agent can take. Remark that each M E M has
N E.Es
| LMML.
For E X. by taking action a E A. the agent transitions to state y(2, a) E y with probability (k.E) For state y(x, a) V, we transition back to y(a, a) with probability Pas (z, a) and to 2(x a) E Z with probability 1 - PM a). Finally, the agent always returns to 2(x, a) for z(x, a) E Z. The reward function (* a) if X y and otherwise. We remark that for every E X, a E A. its Q" function can be computed in closed form by solving the
Let Pas (IR. at) = PM
Bellman optimality equation
1
(M((,,) 1 (p, (Mr(z,)) (1 Par -0] - 7PM (z, a)
a1)
p(a1, or)
plag, an)
p(ax, ag
p(z1,an) a1)
p(a1, at)
p(zg,a) a1)
plak, aL)
ai
ap
ai
ap
I1
J.K
Figure D.I: The class of MDPs considered prove the lower bound in Theorem D.9.
Recall we write N E.EEsslAe to denote the total number of state-action pairs. Our main result in this section is the following.
Theorem D.9. Let p. E (0, y E (1/2,1) 1), and 1/4. Suppose of is a locally random p-replicable algorithm that returns an estimate Q for any MDP with discount factor ? such that (((..a) a) - Q* (s, a)] S e with probability at least 1 6/6 for each s E S, E A Then ad has sample complexity of at least
N3
Ω
(1-
Remark D.10. If Conjecture D.8 holds, we obtain a sample complexity lower bound of
2 ( (1-7)3322p
N2
for general randomized p-replicable algorithms for Q estimation.
Denoted L.
19

---

On high level, we argue that a locally random p-replicable algorithm of for estimating the Q function of arbitrary MDPs up accuracy E Ea/(1>)²² yields locally random p-replicable algorithm for the multiple coin problem (cf. Problem D.5) with tolerance approximately R (1 - 7) when we choose q R y in Theorem D.6. We can then directly apply Theorem D.6 to conclude the proof. See Appendix D.4 for details.
D.2.4 A Lower Bound for Replicable Policy Estimation
Having established the lower bound for locally random replicable Q-function estimation, we now present our lower bound for deterministic replicable policy estimation. We argue that a deter- ministic p-replicable algorithm for optimal policy estimation yields locally random p-replicable algorithm for optimal Q-function estimation after some post-processing that has sample complexity )) follows that the sample complexity lower bound we derived for Q-function estimation holds for policy estimation as well.
ō (N3
In order to describe the post-processing step, employ locally random replicable rounding algorithm (cf. Theorem C.2) that is provided in Esfandiari et al. [2023b]. Intuitively, we show that estimating the value function V of reduces estimating the optimal Q-function of some single-action MDP. Given such estimate V can then estimate Q using the simple sample mean query given sufficient samples from the generative model. Lastly, the locally random replicable rounding subroutine from Theorem C.1 is used as a post proceesion step.
We now state the formal lower bound regarding the sample complexity of deterministic replicable policy estimation. Its proof follows by combining the Q-function estimation lower bound and the reduction we described above. For the full proof, see Appendix D.5.
Theorem D.11. E. P 1). and 5 = 1/4. Suppose s is deterministic p-replicable algorithm that ouppus a randomized policy x such that (V*(s) [*)) S e with probability at least 1 6/12
for each S. Then a has sample complexity of least
N3
(1
222
Remark D.12. If Conjecture D.8 holds, we obtain a sample complexity lower bound of
N2
Ω
(1-7)382p3
for general randomized p-replicable algorithms for policy estimation.
D.3 The Coin Problem
As mentioned before, estimating the bias of coin is an elementary statistical problem. In order to establish our lower bounds, we first aim to understand the sample complexity of locally random algorithms that replicably estimate the bias of multiple coins simultaneously.
Impagliazzo et al. [2022] explored the single coin version of the problem and established version of the following result when the biases 9 of the coins in question lie in the interval (1/4, 3/4). We state and prove the more general result when we allow q to arbitrarily close to
Theorem D.13 (S0-eeplicability Lower Bound; [Impagliazzo et al., 20221). Fix q, E (0, 1)s such that q E E (1/2, 1) and ò 1/4. Let s (c, F) be an algorithm for the (single) coin problem. Suppose s satisfies the following:
(i) of outputs {0, 1} where 1 indicates its guess that the bias of the coin which generated is
(ii) of is p-replicable even when its samples are drawn from coins with bias p E [q E, for all i [N].
(iii) If E {q q}. then al correctly guesses the bias of the i-th coin with probability at least 1 1 6/6.
Then the sample complexity of of is at least
(((1-)) 9)
Ω
s2p²
20

---

We follow similar proof process as Impagliazzo et al. [2022] towards a lower bound for multiple coins. In particular, we begin with the two following lemmas adapted from Impagliazzo et al. [2022].
Lemma D.14 (Immaaliazzoo et al., 2022]). Let 9 10.1) {0. 1 be boolean function. Suppose the input bits are independently sampled from Be(p) for some parameter E [0, 1] and let
Acc: [0, - [0, 1] be given by
Acc(p) = P P a. Bo(r) (g(T) = 13.
Then Acc is differentiable on (0, 1) and for all p E (0,1),
(p) V p(1 - p)
m
Proof (Lemma D.14). Fix p E (0,1) and suppose 2t wiidd. Bo(p). Define
ag = P g(z) = 1
Σ 1
Then
m
m
Acc(p)
ak
p² (1 m-
k
In particular, Acc is differentiable. By computation,
Acd'(p)
111
kkp k-
(11 - -p) - (m- k)p* (1 - mm)m-
k=1
m
Th: - k.
p² m-
ak
D p
m
p pt11 (1 p) mm k(1 p)
(m k)p
ak
p(1 p)
m
p p p) n k - mp
Σ
ak
p(1 p)
m
pd (1 p) mn- |k: - mp
Ok E [0,1]
k
p(1 - p)
1
[|X [[X]]]
X BBn(mn p)
p(1 p)
1
Var[X]
p(1 p)
1
Vmp(1 p)
p(1 - p)
p(1 p)
In the following arguments, we need to reason about probabilistic events with multiple sources of randomness, For the sake of clarity, we use the formal definitions of a probability space and random variable. Specifically, let (WFFPP) P) be an underlying probability space where W is some sample space, F C W is alagebrra, and is probability measure. random variable is simply real-valued function W - R from the sample space.
Define Cp Be(p). Moreover, define C_ Belg - E) and C+ Be(g) to be the distributions of the possible biased coins.
Lemma D.15 (IImpagliazzo et al., 2022)). Fix q, E (0, such that q - E (1/2, 1) and 1/4. Suppose g
: {0, 1)th + {0, 1} is a boolean function satisfying the following:
21

---

(i) For a midd C-, P(w: ((((w)) 0, 2 1 1- 6.
(ii) For a midd C+, P(w: ((((w)) 1 2 1 1- d.
Then for p ~ Uiq - E, g) and z()) .122 ri..d. Cp.
[v((119 9) Ev
P(w: g( (w)) g (x (w))) 20
In other words, we require
m 2 Ω q(1-q)
E² p²
if we wish to reduce the probability above to most p.
We should interpret the input of the function g from Lemma D.15 m realizations of coin flips from the same coin and the output of as its guess whether the bias the coin that generated the realizations is q. Lemma D.15 states that if the function g is "nice", i.c. is able to distinguish the two coins C-,C,, with some fixed confidence - 6, then the same function is not replicable with probability at least S () when the bias is chosen uniformly randomly in the interval lg - E. q). Let us view an arbitrary p-replicable algorithm (e; F) as a distribution over functions gz) Impagliazzo et al. [2022] argued that at least constant fraction of gF is nice, leading to Theorem D.13. Unfortunately, this argument does not extend trivially to the case of multiple coins. However, we present an extension for the special case when af is locally random.
Proof (Lemma D. 15). Let g: {0, 11mh + {0, 1] boolean function that satisfies the condition of Lemma D.15. By Lemma D.14,
Acc(p) = Pe Pe C2 tw g(c(w)) 1}
is differentiable (continuous) and for every p E (g - EE
Aed' (p) V q(1 9)
m
m This is because p(1-p) is non-increasing on (1/2, 1). In particular, Acc(p) V <()o) Lipschitz over the interval [g - E.g].
Now, Acc(g =) < 8 < 1/4 and Acc(q) 2 1 - 8 3/4, thus by the intermediate value theorem from elementary calculus, there is some go (q - E. such that Acc(qu) 1/2. It follows by the Lipschitz condition and the mean value theorem that there is an interval of length M (0/52(3 () around go that for all L,
Acc(p) E
3 3
For two independent sequences of i.i.d. samples, say ((1) 22)), we know that ((x(1)) and g are independent. Thus for p E 1, there is 2 Ace - Acc(p)) > 4/9 probability that g( + (2)()))
Then for p U(q E, q] and x01, xx() riddd Cp.
Pf w g( 11 (w)) + g( (w))
2 P w: g( (w)) + (w)) p(w) E 11 Pfw: p(w) E 13
Vu(L-ol/m
2 9
Ω
p~ U E
25
Vg(1 - 9)
=Ω
e/m
22

---

Lemma D.15 enables us to prove Theorem D.13.
(Theorem D.13). Let G_ be the event that of correctly guess the bias of the coin given p and similarly for G+. Thus
G_ = { w a (dw): = 0}
E p p= q-
G ww (dw);F()))
Here the randomness lies only in the samples č mis.dd Cp and the uniformly random F. By (iii),
3.2 2 P(GS P(F)(()
2 E P(G_ [])
Thus Markov's inequality tells us that choosing F uniformly random satisfies
P(G F) S
with probability at least - 1/(3-2) and similarly for G+.
By union bound, choosing F uniformly at random means G+ both occur with probability at least 2/3. == G+ G._ as a shorthand for indicating the random draw satisfies both G+.
Let us write
Fix F E G to be any particular realization and observe that g := sl (::FF) satisfies the condition of Lemma D.15. By Lemma D.15, p ~ Ulq e, g). and e(1) (()), wisd Cp.
P Plw: (w) + (w):
Σ IPfw: (w) (w) [7) P(F)
2 Σ Ipww: o
7) PFF))
FEG
Vq((1 -
Ω
&//
Vg(l= ②
Ω
8vm
We remark that in the derivation above, a crucial component is the fact that outputs of of across two runs are conditionally independent given the internal randomness.
Since (ii) also holds when p is chosen uniformly at random in the interval [q E, g]. it follows that (2(v((1=9/e//mg S is a lower bound for the replicability parameter. The total sample complexity thus least
q 9) =222
Ω
We now use Theorem D.13 to prove the formal statement of Theorem D.6, samples complexity lower bound for locally random algorithms that replicably distinguish the biases of N independent coins ((1) ..... C(N), assuming each of which either C_ or C+. The lower bound for locally random replicable Q-estimation follows. We formally state Theorem D.6 below.
Theorem D.16 (Theorem D.6; Formal). Fix q, e, E 1)3 such that q s E (1/2, 1) and = 1/4. Let a = (1)(1) ((C)),..,,..... (N)) be a locally random algorithm for the multiple coin problem where (f(() ..... ,, f()) is the output for the i-th coin that draws internal randomness independently from other coins.
Suppose o satisfies the following:
(i) (f(0) oulputs {0, where I indicates its guess that the bius of the coin which generated ( is
23

---

for (ii) of is p-replicable even when its samples are drawn from coins where pl)) E [ all [N].
(mi) pf E 1q- E,-,,) 9, then a correctly guesses the bias of the i-th coin with probability at least 6/c.
Then the sample complexity of of is least
2 ( ( (NN00110))
c2p2
We remark that the scaling with respect is important in order to establish strong lower bound with respect to the parameter (1 7)-
Proof (Theorem D.1 First, we remark that the i-th output of across two runs independent of other outputs since both the coin flips and internal randomness are drawn independently coin.
Thus we may as well assume that (+) only reads the coin flips from the i-th coin.
Let Pe, i E [N] be the probability that the output (f) is inconsistent across two executions when the bias p(t) is chosen uniformly in [g - E, q)- We claim that there are at least N/2 indices [N]
such that Pi I P/N. Indeed, by the independence due to the local randomness property, we have
p 021-
II iE[N]
p:)
exp
E
1 + x S E.
x <
I
2 x E [0,
2
Suppose towards contradiction that more than N/2 indices i [N] satisfy P: P/N. But then
Σ P: N
P.
which is contradiction.
Let I C [N] be the indices of the coins such that P: & p/N. For each E I, (f satisfies the conditions for Theorem D.13. Thus (i) has sample complexity at least
Ω a(1 a(1-))
(2//N)22
follows that the total sample complexity is at least
Ω N 2(1 9) 2 (0/NNN33
NN3 1)
12
p222
D.4 Replicable Q-Function Estimation Lower Bound
In this section, we restate and prove Theorem D.9, lower bound on locally random replicable Q-function estimation.
Theorem D.9. Let P.E E (0, 1)3 y e 1), and 1/4. Suppose of is a locally random
p-replicable algorithm that returns an estimate Q for any MDP with discount factor such that
[Q(s, a) - (* a)] < s with probability at least 1 - 8/6 for each s E S, E A Then of has sample complexity of least
Na
Ω
(1 (1- - 33322

---

Proof (Theorem D.9). Choose := 4t-1/3y and E (0,(1-))/) such that E0 E (1/2, 1). Let C( Be(p!)) be Bernoulli random variables (biased coins) for i E [N] where p( E 4 Eo. g].
To the reduction, first choose any K, L Z, such that KL N and let M M be such that the state action space has cardinality 4N as in the construction in Figure D.I. We identity each i [N] with a pair ax X x A and write in be the index corresponding the pair (x, a). i.e. p(z, a) pf For each state y(z, a) V, we flip the coin C( Be(p(x,, a))) and transition back to yzz a) if the coin lands on I and to z(x, a) E Z if it lands on O. By construction,
QM a)
TPM a)
Let us compare the absolute difference of QT a) when p(z, a) = q versus when p(a, a) =q --50. By computation,
7e0
79 1 1 14 -50 [1 709 - so) 74
Then the following inequalities hold.
q 2
1 ?
37 q
1
2
(1 7)
>
3
2
1 74 7)
1- 7 cu)
(1 7) 7EE
1 1-7
S (1 7) + (1 7))
80 <
7
[1 (1--1) 7).
It follows that
1
1
> 9y60
1- 74
1
7 so)
28(1 7)
350
2 14(1 - 7)
Y
=:6.
Suppose we run a locally random algorithm that replicably estimates Q (x, a) to an accuracy of 5/3. Then we are able to distinguish whether the biases of the coins (fta.a) is either addition, the internal randomness consumed in the estimation of (K...) comes only from the internal randomness used to estimate (² a). Hence the scheme we deseribed a locally random algorithm for the multiple coin problem. Finally, the scheme is replicable even when the biases are chosen in the interval [g Eo, 4)
or In
By Theorem 16 the following sample complexity lower bound holds for dt:
Nº ( 2) = ( (11-))=3]30)
N _1 )
Na
= 12
(1--)3382p 352
D.5
Replicable Policy Estimation Lower Bound
In order to prove a lower bound on locally random replicable policy estimation, we first describe locally random replicable algorithm that estimates the state-action function Q" for given (possibly randomized) policy Recall N : Eles|A" denotes the number of state-action pairs
25

---

Lemma D.17. E, & 1) and ó E (f)) Suppose π is an explicitly given randomized policy. There is locally random o-replicable algorithm that outputs estimate Q of Q" such that with probability least
8, 11@ TM Q"1
Moreover, the algorithm has sample complexity
S|N2 (1 71-7)
N log 1 = 8 = (
N3 222 8
1
Ô
log
(1 72-
Proof (Lemma D.17). Let + ((A) be explicitly given. First, we construct a single-action MDP M = (S, So. {0). Pl, r', 7) whose optimal (and only) state-action function Q' is precisely the value function V of
Let the state space and initial state so remain the same but replace the action space with a singleton "O". We identify each new state-action pair with the state since only one action exists. Next, define the transition probability
('1 80) = Σ AE
T(SO,a) P(s1
so, S0. a).
We can simulate sample from P'( su) by sampling (for free) from the policy, say ((s)). and then sampling from the generative model $1 ~ P(. so, a). Note this costs a single sample from the generative model. In addition, define the reward function as the expected reward at state 80
r' (50)
Σ aE.A"
T a) r(so, a).
This value can be directly computed given πT, r. Finally, the discount factor remains the same.
We remark that Qh (s) = (s) for all s E S by construction. Thus the deterministic (non- replicable) Q-function estimation algorithm from Theorem D.2 is in fact deterministic (non- replicable) algorithm that yields an estimate a of V such that with probability least 1 1 6,
V
V
2N
E' = Epp 26)
+ 1 - 28
Moreover, the sample complexity
δ |S|N2 log 8 (1 722
since the state-action space of M' has size (S). Without loss of accuracy, assume we clip the estimates to lie in the feasible range [0, 1/(1-)))
In order to replicably estimate Q",, we use the following relation
Q* a) = r(s, a) + + [V*
Note that we only have access to an estimate v= (s") and not V (s'), thus we instead estimate
Q" ("( a) == r(s, a) + (BB
i (<()')
But by Hölder's inequality, we are still guaranteed that with probability at least
(s. Q= S >1| s, a.
pr
V
= 7m 4d
E
<
2N
for all S, A
26

---

simply bounded statistical query. By an Hoeffding bound, drawing m samples from the generative model s'j P(- 8, a) implies
Each expectation of the form ((sra)
V
(s')
1 Σ ( - Es [ P
E'
2m(1 - =2
S 2exp
2N
4N2
==1
Thus with
(1-)) 1n (/)
N2
m =
trials, the empirical average estimates a single query P(leo)))) [T with probability at least 6. 6. The total number of samples is thus Nm.
to an accuracy of c//2N
Combining the V estimation and Hoeffding bound yields an estimate Q such that
-
with probability at least 25. Thus we can use the locally random p-replicable rounding scheme from Theorem C.2 to compute an estimate Q" such that with probability at least - 26,
0 - Q- Se.
All all, we described an algorithm that replicably estimates Q" given policy. The algorithm is locally random since the only internal randomness used estimate Q" (s, a) occurs at the last locally replicable rounding step. Finally, the total sample complexity of this algorithm
δ (
|S|N2
N3
73-) (1-7)282pp
log 8
as desired.
With Lemma 1.17 hand, we are now ready to prove Theorem D. 1, which reduces replicable policy estimation to replicable Q-function estimation. We restate the result below for convenience.
Theorem D.11. Let 1)² and ó = 1/4. Suppose of is deterministic p-replicable algorithm that outputs a randomized policy x such that [V*(s) V*( S e with probability at least 8/12
for each E S. Then a has sample complexity of at least
N3
Ω
(1 3)222
Proof (Theorem D.11). Run of to output p-replicable policy such that
- [s)
with probability at least - 6/12 for each 8 E S.
Applying the algorithm from Lemma D.17 with replicability parameter p. failure rate 6/12, and as input yields some estimate Q such that
(s. Q" Q0
with probability at least - 6/12 for each s As.
Using the relationship
(=(()a) = r(s,a) + P( [**(,)],
triangle inequality, as well as a union bound, we realize that
(0,())) - Q= a) S 28
27

---

with probability at least 8/6 for each E S, E A'. Moreover, т is identical across two executions with probability least 1 p by assumption and thus Q will be identical across two executions with probability at least 1 - 2p.
Remark that the scheme we derived above is a locally random 2p-replicable algorithm for Q- estimation. locally random since the only source internal randomness comes from the locally random subroutine in Lemma D.17. Thus the algorithm satisfies the conditions of Theorem D.9 and the lower bound from that theorem applies. In particular, m denotes the sample complexity st then
N
N
m + 8)
2 S
(1-
The LHS is the sample complexity of the scheme derived courtesy of Lemma D.17 and the RHS the lower bound from Theorem D.9. It follows that
N3
(1 "E2p
as desired.
E Omitted Details from Section 4
We now restate and prove Theorem 4.2, a p-TV indistinguishable SQ oracle for multiple queries.
Theorem 4.2 (TV Indistinguishable SQ Oracle for Multiple Queries). Let E, (0, 1)2 and 8 (0. p/s). Let $1....,da be d statistical queries with co-domain [0, 1]. Assume that we can simultaneously estimate the true values of all o; 's with accuracy e and confidence 5 using n(c, total samples. Then, there exists a p-TV indistinguishable algorithm (Algorithm A. that requires at most n((e/[12// /dd (og44/8)) 6/2) many samples to output estimates Ui...., Dd of the true values U1....; Va to guarantee that max,e[4] 6 - U/l S E with probability at least 6.
Proof (Theorem 4.2). We first argue about the correctness of our algorithm. By assumption, with probability at least 1 - 5/2, the oracles provide estimates çr," 's such that
EP
max 77 v/l 'E|d
2
8d log (d//))
2
We call this event E,. Fix some i E [d] and consider the second step where add Gaussian noise (0 E²) to the estimate iu to obtain noisy estimates 0 s. From standard concentration bounds, we know that for X ~ N
P[ - p1 > ro) S 20 22
Plugging in the values
4d 2
o²
8 Slog( 8log(4d/8)) 4d/8)))
r
8
we have that
P( p.l e/2)
<
2d
Thus, taking a union bound over E [d] we have that
8
P max
Tos اu
8/2 2/2
KE(d
We call this event Ez. By taking a union bound over E₁, E2 and applying the triangle inequality, we see that
p
max D - v.l { 28.
iE|d
28

---

We now move on to prove the p-TV indistinguishability guarantees. Consider two executions of the algorithm and let p(2) E E be the estimates after the first step of the algorithm. We know that, with probability at least å over the calls the SQ oracle across the two executions holds that
ep
v 8d log (4d/6)
We call this event & and we condition on it for the rest of the proof. Standard computations [Gupta, 2020] reveal that the KL--divegeecce between two d-dimensional Gaussians p = N N(pp, Ep); q = N (1g: Eg) can be written
DEL (pllg) 1
Egg Epl
log
d (14p 1ng 2 (up (b)) + trace (pp)
In our setting we have
P (
1a)
q 9= (ni1))
E²
8 8log( (d/0) l8
14)
8 8log(44/// (4d/5)
Plugging these we have that
8 $log(4d/0)
( - 1::23// S spa
(pl())
E²
Thus, using Pinsker's 's inequality we see that
drv(p. $ P
V2
Hence, we can bound the expected TV-
p
Eldtv(p. s + <pp
v2
Next, we prove Theorem 4.8, an implementation of the TVVV indistinguishable SQ oracle for multiple queries whose internal randomness is designed in way that also ensures p-replicability. The result is restated below for convenience.
Theorem 4.8 (Replicable SQ Oracle for Multiple Queries). Lete, E (0, 1)2 and 5 E e/s). Ler $1...., Da be d statistical queries with co-domain [0, 1]. Assume that can simultaneously estimate the true values of all o; 's with accuracy e and confidence 8 using n(e, 8) total samples. Then, there / Sd log(Ad/)),, 8/2) many samples to output estimates Ui....; ,..,..,,, Dg of the true values U1,..., Uu with the guarantee that max (0 - v,l S 8, with probability at least 1 1-6. 5.
exists p-replicable algorithm that requires at most n (EeejAA
Proof (Theorem 4.8). Consider a call to Algorithm A.I with TV indistinguishability parameter 1/2. Let us call this algorithm L. Notice that given particular sample, s is Gaussian and therefore absolutely continuous with respect to the Lebesgue measure. Let P be the Lebesgue measure over Rd. Let R be Poisson point process with intensity P Leb x Leb, where Leb is the Lebesgue measure over R, (cf. Theorem C.4).
The learning rule df is defined as in Algorithm A.2. For every input S of .z/ let I's be the conditional density of of given the input S, let r := {(x,, Ve, JeN be an infinite sequence the Poisson point process R, and let i* ;= arg min fs(x,)) >> 3: In words, we consider the pdf of the output conditioned on the input, an infinite sequence drawn from the described Poisson point process, and we focus on the points of this sequence whose y-coordinate falls below the curve. The output of of is Zz- and we denote it by of (S::)))
We will shortly explain why this is well- except for a measure zero event. The fact that af'' is equivalent to follows from the coupling guarantees of this process (cf. Theorem C.4), applied to the single random vector e (S). We can now observe that, except for measure zero event, (i) since af is absolutely continuous with respect to P, there exists such density fs, (ii) the set over which we are taking the minimum is not empty, (iii) the minimum is attained at unique point. This means
29

---

that of is well-defined, except an event of measure zero", and by the correctness of the rejection sampling process [Angel and Spinka, 2019], sf( has the desired probability distribution. We now prove that s'' is replicable. Since of is P/2-TV indistinguishable, it follows that
Rs,s (d oi (S') S p/2.
We have shown that of is equivalent to at, we can see that Is (dTv (ed ((())))))()))))))))))))))))))))) S 5/22 Thus, using the guarantees of Theorem C.4, we have that for any datasets S,5
2drV 20Tv(d" 1 (1)
P (dr + (S':
By taking the expectation over S, we get that
2dTV (s),
Es.s' [P + of (S', r1)1 s Es,s'
1 drv
25 (s),
<
+ Es,s' (dTV( (S),
P
$ + p/2
SP
where the first inequality follows from Theorem C.4 and taking the expectation over S, 8", the second inequality follows from Jensen's 's inequality, and the third inequality follows from the fact that f(x 2x/(1 (1 + æ) is increasing. Now notice that since the source of randomness R. is independent of S, S", we have that
Es,s [P (dd + (f'
,m ( (S'
Thus, we have shown that
Ps.s Ps.s:..Rto + of (S': sp.
and so the algorithm sf is p-replicable, concluding the proof.
Remark E.I. The coupling we described in the previous proof is not computable, since it requires an infinite sequence of samples. However, we can execute it approximately in the following way. We can first truncate the tails of the distribution and consider a large enough d-dimensional box that encloses the pdf of the truncated distribution. Then, by sampling (exp(d)) many points we can guarantee that, with high probability, there will be least one that falls below the pdf. Even though this approximate coupling is computable, it still requires exponential time.
Remark E.2 (Coordinate-Wirt Coupling). Since our algorithms add independent Gaussian noise each of the estimates, a first approach to achieve the coupling using only shared randomness would be construct pairwise coupling between each estimate. In the context of multiple statistical query estimation, this would mean that we couple the estimate of the i-th query in the first execution with the estimate of the i-th query in the second execution. Unfortunately, even though this coupling is computationally efficient to implement it does not give us the desired sample complexity guarantees. To see that, notice that when the -istittacce of estimates across each coordinate O(p), under this pairwise coupling the probability that at least one of the estimates will be different across the two executions is Odd- - p). However, the TV distance of the d-dimensional Gaussians is O(vd. p). and this the reason why the more complicated coupling we propose achieves better sample complexity guarantees. Our results reaffirms the observation that was made by Kalavasis et al. [2023] that the replicability property and the sample complexity of an algorithm are heavily tied to the implementation of its internal randomness, which can lead to substantial computational overhead.
*Under the measure zero event that at least one of these three conditions does not hold, we let ol (S:r) be some arbitrary d-dimensional vector in [0, 17d.
30

---

Omitted Details from Section 5
We now fill in the missing technical details from Section which proposes an approximately replicable algorithm for optimal policy estimation.
Algorithm F.1 Approximately Replicable Policy Estimation
1: 8 <- min p2/2).
2: Run Sublinear Randomized QVI [Sidford et al., 2018a] with confidence 6, discount factor and eτror p1- (1 - 7)/(8 log(I-A)).
3: Let Q be the output of the previous step. log(lA)) 6/2-(1->)*
4: X +
exp exp()((+.a)) Eo'ed exp (Q((,a0))
5: For every S, let (et
6: Output n.
F.1 Different Soft-Max Rules
Instead of using the exponential soft-max rule we described in Section 5, one could use a more sophisticated soft-max rule like the piecewise- linear soft-max rule that was developed in Epasto et al. [2020]. The main advantage of this approach is that it achieves a worst-case E-approximation, i.e., it never picks an action that will lead a cumulative reward that worse that the optimal one (cf. Definition 5.3). We also remark that this leads to sparse policies when there is only small number of near-optimal actions.
F.2 Deferred Proofs
F.2.1 Proof of Lemma 5.5
We now restate and prove Lemma 5.5, useful result which quantifies the performance of the soft-max policy in comparison the optimal policy.
Lemma 5.5 (Soft-Max Policy vs Optimal Policy). Ler E2 E (0, 1)2. Les Q E RSA such that
Q'Il S E1. Let àt be the ExpSoftMax policy with respect to Q using parameter À = loglAl/o2
Then,
V v*ll < (22n+ea)/(1>))
Proof (Lemma 5.5). Using the guarantees Lemma 5.4 we have that
max ((,, a) S Σ #(B,a) ((, + a
aEAA
We can assume without loss of generality that x² is deterministic policy due to the fundamental theorem of RL. Fix an arbitrary E S. By the fact that max [Q(s, a) Q*, S éi, we see that
(s())((s)) s max ((s, a) +
aEA
Σ
π ((5 a) @(s, +
acA
7( (' a) 25, +
a
An equivalent way to write the previous inequality is
r(s, (s)) + 7 Σ
V*(s') P(r(s(s,
3'ES
< Σ (ss
(1(8,)) +y V* Pa)(5((s,0) + 281 + 82
AEA
*eSS
31

---

which implies that
r(8, (x)) - Σ ((8,a).r(88
aEA
5 Σ a(),a)- -V(d))-u(bbbba
- (M(0))PP(611:77))
aEd
L'ES
s'ES
+ 251 +82.
(1)
Let E arg max (*()) (8). Then, we have that
(*()) (3)
S -T(, - r((,
aEA
+y Σ (*')s 5,
T
Ea(s,a)
(d)
(
s3ES
aEA
LESS
Bounding the first two terms the RHS using Equation (1) for we see that
(*) (8)
Σ a(),a).
( VV((')) PMr('(8,='(8))
SS
aEE
EEES
e'ES
V*(s) (M((s((,
Σ (3,
-
7
N'ES
s'ES
28, + 52.
After we cancel some terms on the RHS we conclude that
($)
V (8)
S 7
Σ a(5
Σ V (V (()
28i 1 +
Σ (3,
Σ (8' - PM((115.a) + 221 +
5>
REA
WES
=7 (V*(3)
V
+ 251 + E2
The second inequality follows from the fact that & E arg max,es V*(s) V²(s) and the equality follows from the fact that Eaea (5, 1, 1, Eves PM (8 3) = 1, Va A. Rearranging, that
v (8) V*(3) < 28 +
1
But the choice of s E S was arbitrary, concluding the proof.
F.2.2 Proof of Theorem 5.6
Last but not least, prove Theorem 5.6, upper bound approximaeely-repiccabbe policy estimation. We restate the result below for convenience.
Theorem 5.6. Let a 2 1,7,8, p1, P2 E 1)4, and e E (1-))) There is a (p1. P2)- approximately replicable algorithm a with respect to the Renyi divergence D such that given access to a generator for any MDP M, outputs a policy for which ||V V* S E with probability
at least 1 - ô. Moreover, o has time and sample complexity Ö(N log(\/mi((..::))/(C
5 pp1)
32

---

Proof (Theorem 5.6). First, we argue about the correctness of the approach. Using Theorem D.2 with parameters 7 6 s1 P1 E (L 7)/ log( (l))), can estimate some Q such that ||Ộ1 - I E1, with probability least 1 1- 6/2. We call this event and we condition on Since we use the exponential mechanism with parameter À = (og((AA))(E/2 (1 ->) to compute a policy (s). for every state S, Lemma 5.5 guarantees that
2p1 E (1 - ()/((888))))) (og((-A)) + E/2 (1 (1-7) S
||V - V I
This completes the proof of correctness.
We now proceed with showing the replicability guarantees of this process. Consider two executions of the algorithm and let Q1, Q2 denote the output of the algorithm described in Theorem D.2 in the first and second run, respectively. Notice that, with probability at least 1 - min (ō, } it holds that l|@1 Q-1 lo I E 1|Q² Q* I ε1. We call this event &g and condition on it for the rest of the proof. Thus, by the triangle inequality, we have that
11: @ullc 251
Let #1 n2 denote the policy the algorithm outputs in the first and second execution, respectively. Let E S be some arbitrary state. Since the exponential soft-max is 2X-Lipschitz continuous with respect to (Loo, we have that
(s(Ti())(( - 2X1101 - 121loo
= 2 (e/2 2. (1 7)) 22 PS. 1.5554. (1 -7)
log(1-4)
(8log(1AA)
PI.
Since the event &2 happens with probability - p2 we see that the algorithm (pi: P2) aapproxxxiiy replicable with respect to Da, i.e., the Renyi divergence of order a. This concludes the approximate replicability part of the proof.
As last step, we bound the sample complexity of our algorithm. The stated bound follows directly from Theorem D.2 since we call this algorithm with error parameter P1 E (1-7)/(8 log(l-A))). O
Remark F.1 (Replicability Under TV Distance). It is known that the TV distance of two probability distributions is upper bounded by Dx- Thus, we can see that Theorem 5.6 provides the same guarantees when want to establish replicability with respect to the TV distance.
Remark F.2 (Sample Complexity Dependence pendence of the number of samples in Theorem 5.6 on the two different replicability parameters of Definition 5.2 is different. In particular, the dependence P2 is polylog(//p), whereas the dependence on P1 is poor))/o).
Replicability Parameters). Notice that the de-
G Guarantees under Different Replicability Notions
Since we have studied three different replicability notions in this work, believe it is informative to discuss the advantages and the drawbacks of each one them. Our discussion is centered across four different axes: the replicability guarantees that each notion provides, the sample complexity required to satisfy each definition, the running time required to run the underlying algorithms, and the ability test/verify whether the algorithms have the desired replicability properties.
The definition of Impagliazzo et al. [2022] (Definition 2.8) provides the strongest replicability guarantees since it requires that the two outputs are exactly the same across the two executions. It is also computationally efficient to verify it. Even though it is statistically equivalent to the definition of TV indistinguishabilty. our results along with the results of Bun et al. [2023], Kalavasis et al. [2023] indicate that there might be a computational separation between these two notions. Moreover, the fact that this notion is so tightly related to the way the internal randomness of the algorithm is implemented is a property that is not exhibited by any other notion of stability we are aware of and can be problematic in some applications.
The definition of TV indistinguishabiiity Kalavasis et al. [2023] (Definition 4.1) provides strong replicability guarantees, in the sense that someone who observes the outputs of the algorithm
33

---

under two executions when the inputs are S, cannot distinguish which one between S, S' was responsible for generating this output. Moreover, this definition does nor depend on the way the internal randomness of the algorithm is implemented. On the other hand, testing whether an algorithm has this property more subtle compared to Definition 2.8. In the case of the Gaussian mechanism- based algorithms we discuss in this work the following holds: if the output of the algorithm is promised to be drawn from Gaussian distribution, it computationally and statistically efficient to test whether the outputs under two different datasets S, S' are close in TV distance. However, it is not clear how one can test if the outputs are indeed drawn from a Gaussian distribution.
Finally, the notion of approximate replicability (Definition 5.1) we introduce is further relaxation of the TV indistinguishabiiit property in the following sense: both the replicability definition and TV indistinguishabiiiy definition treat the outputs in a "binary" manner, in the sense that they only care whether the outputs are exactly the same across the two executions. This definition takes more nuanced approach and considers some notion of distance across the outputs that is not binary. As result, it provides the weakest replicability guarantees, which, however, could sufficient in most RL applications. Moreover, as results indicate, there might be some inherent advantage in terms of the sample complexity required to achieve this notion compared to (strict) replicability or TV indistinguishabiiity, which can be crucial in RL applications with large state-action space. Moreover, similarly as with the replicability definition, it is also efficient to test whether an algorithm has this property not.
To sum up, even though we have not completely characterized the sample complexity and compu- tational complexity of each definition we believe that the following is the complete picture: the replicability property is statistically equivalent to the TV indistinguishabiityy property and the approx- imate replicability property has sample complexity that is smaller by a factor of N. Moreover, we believe that there a computational gap between the notions of replicability and TV indistinguishabil ity. We underline that under Conjecture D.8, the results of our work give complete characterization" of the sample complexity of these problems with respect to N.
Up to poly- logarithhi factors.
34


Reviews:
[{"review_id": "VD24bdD6Ek", "reviewer": "Reviewer_i28M", "summary": "Reproducibility is a big problem in RL. This paper builds on Impagliazzo (2022) on replicability in learning, and develops a replicability framework for RL. It focuses on a discounted tabular MDP setting with a generative model. The replicability problem is given shared internal randomness, how many samples are needed for a learning algorithm to output the exact same policy with probability (1-$\\rho$) across two executions. It shows that $\\rho$-replicability requires $O(N^2/\\rho^2)$ more samples than would otherwise be needed for an \\epsilon-optimal Q function, where N is the number of state-action pairs. This matches the lower bound which they also provide. There is also extensions to approximately replicable policy estimation.", "questions": "Q1. Can the authors through some experimental work justify why their notion of replicability (particularly approximate replicability) is more suitable than reporting say 95% confidence intervals? If not experimental work, could you argue this through a simple example?\n\nQ2. Could you elucidate how the replicability framework you introduce can practically help resolve the reproducibility issues in AI/RL?", "limitations": "Please explain how the limitations of your framework can be overcome with further work to make it useful for practically addressing the reproducibility issues in AI/RL?", "rating": 2, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper presents a nice framework for replicability in RL which is related to the reproducibility problem.\n2. The paper is well-written, and it is easy to understand.\n3. The results are interesting though not surprising.", "weaknesses": "My main issue with the paper is the underlying premise that the reproducibility crisis in ML and RL is due to the replication difficulty owing to randomness. It is not! As the authors themselves remark, a lot of the reproducibility issues arise due to the need for hyper-parameters, code not being aligned with the algorithms presented in the papers, training details,  environments not being set up in the same way and results reproducible only on trajectories with specific random seeds, etc. As we all well know, if we want to estimate the mean of a distribution from n samples, we will not get the same estimate from two different experiments. That is why confidence intervals should always be reported: That is the standard way, in some sense of ensuring replicability in statistics. And to get say 95\\% confidence intervals, it is fairly easy to calculate the number of samples (or sample trajectories) needed. That calculation I would expect would scale as O(N^2) as well. So the question is what more have we learnt from the results in this paper? I think the results in this paper are essentially confidence interval type calculations just dressed up nicely as $\\rho$-replicability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their constructive comments.\n\n> As we all well know... So the question is what more have we learnt from the results in this paper? I think the results in this paper are essentially confidence interval type calculations just dressed up nicely as $\\rho$-replicability.\n\nThe reviewer raises an interesting and important point. In many applications, like mean estimation, correctness of the answer ensures some form of replicability. In particular, if we consider the mean estimation problem we know that, with high probability, if we estimate the mean on two sets of $O(1/\\epsilon^2)$ i.i.d. data then the two answers $x_1, x_2$ will be $\\epsilon/2$-close to the true one so, by triangle inequality, they will be $\\epsilon$-close to each other. Coming back to the RL setting, a similar calculation shows that the two policies that are derived from two sets of i.i.d. data will yield rewards that are $\\varepsilon$-close to one another. However, this does not mean that the two policies will be close under any reasonable notion of ``closeness”. In other words, confidence intervals imply replicability in the value space but not in the policy space. In a lot of RL applications we set up the rewards as a proxy that will lead to a good policy, i.e. the object of interest is the policy itself and not necessarily its reward. In order to achieve replicability in the space of policies, we need to do more work than to just report confidence intervals.\n\nAs a concrete example, Yu et al. [2019] state that RL applied towards “a medical or clinical treatment regime is composed of a sequence of decision[s] to determine the course of [action] such as treatment type, drug dosage, or re-examination timing … with a goal of promoting the patient’s long-term benefits.” In such cases, where the output we mostly care about is the policy and not the numerical value of the reward, replicability in the policy estimation is crucial. Indeed, practitioners would not trust the results of algorithms that vary significantly when executed on (potentially different) datasets that are obtained using the same sampling process from the same underlying population.\n\nAlso, note that replicability within the applied RL community is not a novel concept. Numerous studies such as that of Henderson et al. [2019] and Lynnerup et al. [2019] have attempted to tackle this issue from a methodological perspective. These works provide a series of recommended steps in order to perform replicable RL research. From an algorithmic point of view, the previous works have attempted to minimize the differences in the input of the algorithm since RL algorithms are notoriously sensitive to hyperparameters, the environment, etc. We take a different approach and strive to design algorithms that are inherently more stable, therefore attacking the problem at its root.\n\n> Can the authors through some experimental work justify why their notion of replicability (particularly approximate replicability) is more suitable than reporting say 95% confidence intervals? If not experimental work, could you argue this through a simple example?\n\nWe are working on adding experimental evaluation in the next version of our draft. Let us describe a simple example where our notion of approximate replicability is more suitable than just reporting confidence intervals. Consider the problem of computing a stochastic s-t path in a graph. In this problem, the learner has access to a graph but does not know the cost/weight of each edge. We assume that this cost is associated with some distribution in [0,1]. The agent can get information about the cost by querying the edge. Let us consider a naive solution, where the agent estimates the true mean of every edge with accuracy $\\epsilon$ and then returns the shortest path based on the estimated means. We can show that with probability 95% the returned path has a total cost at most $\\epsilon$ more than the optimal one. However, it is not hard to see that due to the estimation error, with probability 99.99% each run of the experiment returns a different path. It is reasonable to say that such an experiment is not replicable. Our notion of approximate replicability allows, essentially, the agent to return a distribution over paths, so that i) the two distributions are ``close’’ and ii) if we sample a path from this distribution, then with high probability, its cost will be at most $\\epsilon$ more than the optimal one.\n\n>  Could you elucidate how the replicability framework you introduce can practically help resolve the reproducibility issues in AI/RL?\n\nOne important practical message our work sends regarding the reproducibility issues in AI/RL is that the max operator leads to results that are brittle and are very sensitive to estimation errors and numerical errors, which make the results non-reproducible. On the other hand, soft-max operators like the one we consider to obtain our approximate replicability results, are much more robust to these types of errors. \n\n> Please explain how the limitations of your framework can be overcome with further work to make it useful for practically addressing the reproducibility issues in AI/RL?\n\nInteresting next steps in this line of work are to consider settings beyond the tabular RL, like the linear function approximation setting. Another direction is to consider the episodic setting and see how we can balance the tradeoff between achieving low regret and computing policies that are ``close’’ across executions.\n\nYu et al. [2019]: Chao Yu, Jiming Liu, and Shamim Nemati: Reinforcement learning in healthcare: a survey.\n\nHenderson et al. [2019]: Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, David Meger: Deep reinforcement learning that matters.\n\nLynnerup et al. [2019]: Nicolai A. Lynnerup, Laura Nolling, Rasmus Hasle, John Hallam: A survey on reproducibility by evaluating deep reinforcement learning algorithms on real-world robots.\n"}, {"review_id": "nT7y5zKoW9", "reviewer": "Reviewer_o1wo", "summary": "The paper makes a significant contribution by introducing a theoretical study of replicability in reinforcement learning. It focuses on discounted tabular Markov Decision Processes (MDPs) with generative models and explores two definitions of replicability: exact and approximate versions. For the exact version of replicability, the authors provide a lower bound and propose an algorithm that achieves near-optimal performance, with the exception of dependence on the discount factor $\\gamma$. In the case of the approximate version of replicability, the authors show an improved sample complexity. ", "questions": "How do classic RL algorithms in the tabular case behave concerning the two notions of replicability discussed in the paper?\n\n", "limitations": "The authors have addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper provides a comprehensive study on the theory of replicability, offering insights into both the exact and approximate versions of replicability. Notably, for the exact version, the authors present both upper and lower bounds, which align closely.\n\n- The concept of replicability in reinforcement learning is highly intriguing, and this paper serves as a pioneering work in advancing the study of theory of replicability in RL. By introducing and delving into this concept, the authors open up new avenues for exploring replicability and its implications in RL research.\n\n- Technically, the paper exhibits strong foundations and analysis, showcasing a solid understanding of the subject matter. The presentation of the research is clear and well-motivated, ensuring that readers can grasp the significance and implications of the findings effectively.", "weaknesses": "- While the topic of studying replicability in RL (Reinforcement Learning) is intriguing, I have reservations about its significance. For instance, if there exists a single optimal policy, it logically follows that all RL algorithms should eventually converge to the same policy. Hence, replicability is inherently implied.\n\n- I understand that this is primarily a theoretical paper; however, it would be advantageous to include some experimental analysis. Specifically, exploring the behavior of classical RL algorithms in the tabular case with regards to replicability would provide valuable insights. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their constructive comments.\n\n> While the topic of studying replicability in RL (Reinforcement Learning) is intriguing, I have reservations about its significance. For instance, if there exists a single optimal policy, it logically follows that all RL algorithms should eventually converge to the same policy. Hence, replicability is inherently implied.\n\nWhile we agree with the reviewer that if there is a single optimal policy, replicability is inherently implied, we believe that only a very small set of RL problems fall into this category. On top of that, if we denote by $\\delta$ the gap in the reward of the optimal policy and the second best policy, the number of samples we need to find an exact optimal policy scales as $O(1/\\delta^2)$. Moreover, if there are two or more optimal policies, then replicability is not trivially implied. In most applications it is the case that either the set of optimal policies is not a singleton, or that the difference in the utility of the optimal policy and the second best policy is so small that we are not willing to pay $O(1/\\delta^2)$ in the sample complexity.\n\nNotice that if there are multiple optimal policies, a naive approach is to add random noise to the rewards. This will ensure that, with probability 1, the optimal policy will be unique. Nevertheless, the gap between the best policy and the second best policy will be very small, which will make it prohibitive to pay the required sample complexity in order to be able to detect it.\n\n> I understand that this is primarily a theoretical paper; however, it would be advantageous to include some experimental analysis. Specifically, exploring the behavior of classical RL algorithms in the tabular case with regards to replicability would provide valuable insights.\n\nAs the reviewer correctly pointed out, our main focus in this paper is a mathematical treatment of replicability in RL. Nevertheless, we are working on experiments which we will add to the next version of our paper. Let us comment on how classical RL algorithms in the tabular setting behave with regards to the replicability notions we consider. Most of these algorithms like the ones in [Kearns and Singh, 1999], [Azar et al., 2013], are based on the Bellman operator which is inherently non-replicable. This is because the Bellman operator is, essentially, a max operator over some computed quantities, which makes it very sensitive to estimation errors. Thus, these algorithms do not satisfy the replicability definitions we consider in this work. On the other hand, in Section 4 we show that if instead of the max operator we consider a soft-max version of it, we can get results that are ``replicable’’ under our definition of approximate replicability.\n\n> How do classic RL algorithms in the tabular case behave concerning the two notions of replicability discussed in the paper?\n\nPlease see our response to the previous comment.\n"}, {"review_id": "vBSnc3SpOi", "reviewer": "Reviewer_GbLw", "summary": "The paper studies replicable reinforcement learning algorithms in the tabular MDP setting with an oracle generative model. The paper gives the first lower-bound for the sample complexity of a $\\rho$-replicable $(\\varepsilon, \\delta)$-optimal algorithm. To obtain this lower-bound, the paper first builds an information-theoretical lower-bound for the sample complexity of estimating $N$ independent possibly biased coins, and then reduces the multiple coin estimation problem to some leveled tabular MDP learning with an oracle generative model. By proposing an algorithm (which is basically running an existing RL algorithm for tabular MDPs with a generative model with some carefully designed precision parameters, and then properly rounding the value function) with $\\tilde O(N^3)$ dependency of $N$ in the sample complexity upper-bound, the paper shows that the proposed sample complexity lower-bound is indeed sharp in $N$.\n\nThe paper also studies a weaker replicability formulation called approximate-replicability and gives an algorithm with $\\tilde O(N)$ sample complexity.", "questions": "Can you provide some insights and comments on the replicability of RL in the pure exploration setting or episodic regret minimization setting (hence both without discounting factors)?", "limitations": "The paper considers RL on tabular MDPs with a generative model, it would be more exciting to see results on weaker settings.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clearly written and easy to follow for readers with background on recent theoretical RL works. The given sample complexity lower-bound in $N$ is tight. The proposed algorithms in both formulations are built upon existing oracle algorithms and simple post-processing and hence easy to understand.", "weaknesses": "In my opinion, the structure of the paper can be slightly improved. The reductions between the optimal Q-function estimation and the optimal policy, the multiple coin estimation problem and RL on tabular MDPs are at a high level easy to understand. The author may consider compress these contents and move some details of the important technical steps (e.g., the replicable rounding step and how to develop the sample complexity lower-bound for the replicable multiple coin estimation problem) to the main text, in order to bring more insight to the readers after reading the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their constructive comments.\n\n> In my opinion, the structure of the paper can be slightly improved. The reductions between the optimal Q-function estimation and the optimal policy, the multiple coin estimation problem and RL on tabular MDPs are at a high level easy to understand. The author may consider compress these contents and move some details of the important technical steps (e.g., the replicable rounding step and how to develop the sample complexity lower-bound for the replicable multiple coin estimation problem) to the main text, in order to bring more insight to the readers after reading the main text.\n\nWe thank the reviewer for the comment. We plan to make these changes in the next version of our draft. Moreover, if the paper gets accepted, we will utilize the extra space to elaborate more on these points. \n\n> Can you provide some insights and comments on the replicability of RL in the pure exploration setting or episodic regret minimization setting (hence both without discounting factors)?\n\nThis is indeed an important area for future research. In these settings, the agent will need to keep track of a potential “model” of the world by performing some Upper Confidence Bound (UCB) type of update. The crucial step to ensure replicability is that, by sharing randomness, the learner will be able to update the “model” of the world in the same way across the two executions (e.g., by doing some variant of randomized rounding in the UCB-type of updates). The main difficulty here is to figure out how to come up with a rounding scheme that on the one hand ensures replicability and on the other hand yields low regret/small number of episodes of exploration.\n\n> The paper considers RL on tabular MDPs with a generative model, it would be more exciting to see results on weaker settings.\n\nWhile we agree with the point that the reviewer raised, our main goal in this work was to provide a comprehensive treatment of the tabular setting, which is the most fundamental setting in RL. We hope and believe that our work will inspire further research in more realistic settings like the linear function approximation setting and the episodic setting. We think that the ideas we have developed in our work, like the replicable $Q$-function estimation (under the different notions of replicability we consider), will be useful in this line of work.\n"}, {"review_id": "v1stK0h0AJ", "reviewer": "Reviewer_1f6r", "summary": "This work studies the question of reproducibility in reinforcement learning (RL). They define reproducibility as an algorithm returning the same policy on two different random draws from the environment, with probability at least $\\rho$. In the generative model setting, they show that there exists an algorithm which is $\\rho$-reproducible, returns an $\\epsilon$-optimal policy with probability at least $1-\\delta$, and collects at most $O(\\frac{N^3 \\log 1/\\delta}{(1-\\gamma)^5 \\epsilon^2 \\rho^2})$ samples, for $N$ the number of state-actions. They also show a lower bound that this is tight (up to a factor of $1/(1-\\gamma)^2$). As the $N^3$ complexity could be prohibitively large in many cases, they show that by relaxing the definition of reproducibility somewhat, they are able to obtain a complexity that scales with $N$ instead.", "questions": "The primary question I have is on motivating the problem setting, as I stated in the weaknesses section.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. To my knowledge, the setting is novel: I do not think the question of reproducibility has been previously considered in the RL literature. Furthermore, the question of algorithmic reproducibility has in general seen attention recently in the broader machine learning literature, so there is general interest in the setting.\n2. The results paint a fairly complete picture of the problem, with nearly matching upper and lower bounds. In addition, they show that the $N^3$ dependence can be reduced by considering a slightly relaxed formulation of the problem.", "weaknesses": "1. The paper does not clearly motivated why we should care about reproducibility in RL. While reproducibility in science in general is an issue, in RL typically the goal is simply to find a policy that (approximately) maximizes the reward, and we don’t necessarily care whether two runs of the same algorithm produce identical policies or not, as long as they have similar performance. The paper does not give clear justification for why this problem is important, but I think this is necessary given the novelty of it. \n2. Definition 2.6 should make clear that the algorithm is able to request which state-actions the $n(\\epsilon,\\delta)$ are from (if it is indeed able to). As it currently reads, it is ambiguous if the algorithm can request which state-actions they are from, or if it is simply given $n(\\epsilon,\\delta)$ samples from the generator—the latter option is clearly not possible since if all samples are from the same state-action it is not possible to learn a good policy.\n3. Definition 2.9 is also somewhat unclear for a similar reason. My reading is that $\\bar{S},\\bar{S}’ \\sim G$ means that samples from a particular set of state-actions are generated from $G$. Would this exclude the case when all the samples are coming from the state-action? Also, does it exclude an adaptive algorithm which chooses which state-actions to sample from based on the data it has already seen?\n4. Using the notation $\\bar{r}$ for the randomness of the algorithm is somewhat confusing as $r$ is already used for the reward. \n5. I understand that space is limited, but if possible it would be helpful to give some more explanation for the algorithm, in particular the replicable rounding procedure, since this is non-standard in the RL literature. Some intuition on why the $N^3$ dependence arises would also be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their constructive comments. \n\n> The paper does not clearly motivated why we should care about reproducibility in RL.. but I think this is necessary given the novelty of it. \n\nThe reviewer raises an important point. In many applications, like mean estimation, correctness of the answer ensures some form of replicability. In the RL setting, we can show that  policies that are derived from two sets of i.i.d. data will yield rewards that are $\\varepsilon$-close to one another. However, in many RL applications we set up the rewards as a proxy that will lead to a good policy, i.e. the object of interest is the policy itself and not necessarily its reward. Unfortunately, \"standard\" RL algorithms do not achieve replicability in the space of policies. This is because most of them are based on the Bellman operator, which is essentially a max operator, and it is very brittle.\n\nAs a concrete example, Yu et al. [2019] state that RL applied towards “a medical or clinical treatment regime is composed of a sequence of decision[s] to determine the course of [action] such as treatment type, drug dosage, or re-examination timing … with a goal of promoting the patient’s long-term benefits.” In such cases, where the output we mostly care about is the policy and not the numerical value of the reward, replicability in the policy estimation is crucial. Indeed, practitioners would not trust the results of algorithms that vary significantly when executed on (potentially different) datasets that are obtained using the same sampling process from the same underlying population.\n\nAlso, note that replicability within the applied RL community is not a novel concept. Numerous studies such as that of Henderson et al. [2019] and Lynnerup et al. [2019] have attempted to tackle this issue from a methodological perspective. These works provide a series of recommended steps in order to perform replicable RL research. From an algorithmic point of view, the previous works have attempted to minimize the differences in the input of the algorithm since RL algorithms are notoriously sensitive to hyperparameters, the environment, etc. We take a different approach and strive to design algorithms that are inherently more stable, therefore attacking the problem at its root.\n\n> Definition 2.6 should make clear that the algorithm is able to request which state-actions the $n(\\epsilon,\\delta)$  are from (if it is indeed able to). As it currently reads, it is ambiguous if the algorithm can request which state-actions they are from, or if it is simply given  $n(\\epsilon,\\delta)$ samples from the generator—the latter option is clearly not possible since if all samples are from the same state-action it is not possible to learn a good policy.\n\nWe would like to thank the reviewer for bringing this up. The algorithm is indeed able to specify the state-action pairs. We will clarify that in the next version of our draft. \n\n> Definition 2.9 is also somewhat unclear for a similar reason. My reading is that $S, \\bar{S} \\sim G$\n means that samples from a particular set of state-actions are generated from $G$. Would this exclude the case when all the samples are coming from the state-action? Also, does it exclude an adaptive algorithm which chooses which state-actions to sample from based on the data it has already seen?\n\nWe would like to thank the reviewer for bringing this up, similarly as before the algorithm is able to select which states-actions it will get samples from. Our algorithms are not adaptive and, intuitively, we do not see how adaptivity could help with replicability. We will clarify that in the next version of our draft.\n\n> Using the notation $\\bar{r}$  for the randomness of the algorithm is somewhat confusing as  is already used for the reward.\n\nWe thank the reviewer for the constructive comment and will change the notation to use $\\xi$ instead.\n\n> I understand that space is limited, but if possible it would be helpful to give some more explanation for the algorithm, in particular the replicable rounding procedure, since this is non-standard in the RL literature. Some intuition on why the $N^3$ dependence arises would also be helpful.\n\nWe agree with the reviewer's comment and will include the following explanation in the next version of our manuscript.\nLet $Q^\\star$ be the optimal $Q$-function. The replicable rounding procedure is based on a rounding scheme that appeared in [Impagliazzo et al., 2022]. It takes as input two $Q$-vectors $Q_1, Q_2$ with the promise that $||Q_1 - Q_2||_\\infty \\leq \\rho \\cdot \\epsilon,$ where $\\rho, \\epsilon$ are the replicability, accuracy parameters respectively. For that, we need $O(N/(\\epsilon^2 \\rho^2))$ many samples. Then, we consider each coordinate $(s,a)$ separately. We discretize the interval $[0,1/(1-\\gamma)]$ that $Q_1(s,a), Q_2(s,a)$ belong to by first consider a random offset $r \\sim U[0,\\epsilon]$ and then increments of length $\\epsilon$. Importantly, this random offset is shared across the two executions. The size of the intervals that we choose for the rounding guarantee that the $|Q_1(s,a) - Q^\\star(s,a)| \\leq \\epsilon, |Q_2(s,a) - Q^\\star(s,a)| \\leq \\epsilon$ and because of the shared random offset we can show that, with probability $1-\\rho$, $Q_1(s,a) = Q_2(s,a)$. Because we need to take a union-bound over the $N$ state-action pairs, we need to set the replicability parameter to be $\\rho/N$. Since the dependence on $\\rho$ is quadratic, we get the extra $N^2$ factor in the sample complexity.\n\nYu et al. [2019]: Chao Yu, Jiming Liu, and Shamim Nemati: Reinforcement learning in healthcare: a survey.\n\nHenderson et al. [2019]: Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, David Meger: Deep reinforcement learning that matters.\n\nLynnerup et al. [2019]: Nicolai A. Lynnerup, Laura Nolling, Rasmus Hasle, John Hallam: A survey on reproducibility by evaluating deep reinforcement learning algorithms on real-world robots.\n"}]

Author rebuttal:

Meta-review: The paper studies replicability in reinforcement learning. The paper considers discounted tabular Markov Decision Processes (MDPs) with generative models and explores two definitions of replicability: exact and approximate versions. For the exact version of replicability, the authors provide a lower bound and propose an algorithm that achieves near-optimal performance, with the exception of dependence on the discount factor. In the case of the approximate version of replicability, the authors show an improved sample complexity.

While one of the reviewer remains concerned on the definition of the replicability, which can be different from what readers would intuitively imagine, this paper has rigorous definition of the terminology and develops solid theory for author's version replicability, and is thus favored by remaining reviewers. Therefore, we recommend acceptance. It would be appreciated if authors could potentially modify proper contents to avoid the confusion in the discussion.
Decision: Accept (poster)