Finding good policies in average-reward Markov Decision Processes without prior knowledge

Authors: adrienne  tuynman
rémy  degenne
emilie  kaufmann
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 11:23:55

Abstract: We revisit the identification of an $\varepsilon$-optimal policy in average-reward Markov Decision Processes (MDP). In such MDPs, two measures of complexity have appeared in the literature: the diameter, $D$, and the optimal bias span, $H$, which satisfy $H\leq D$.
  Prior work have studied the complexity of $\varepsilon$-optimal policy identification only when a generative model is available. In this case, it is known that there exists an MDP with $D \simeq H$ for which the sample complexity to output an $\varepsilon$-optimal policy is $\Omega(SAD/\varepsilon^2)$ where $S$ and $A$ are the sizes of the state and action spaces. Recently, an algorithm with a sample complexity of order $SAH/\varepsilon^2$ has been proposed, but it requires the knowledge of $H$. We first show that the sample complexity required to estimate $H$ is not bounded by any function of $S,A$ and $H$, ruling out the possibility to easily make the previous algorithm agnostic to $H$. By relying instead on a diameter estimation procedure, we propose the first algorithm for $(\varepsilon,\delta)$-PAC policy identification that does not need any form of prior knowledge on the MDP. Its sample complexity scales in $SAD/\varepsilon^2$ in the regime of small $\varepsilon$, which is near-optimal. In the online setting, our first contribution is a lower bound which implies that a sample complexity polynomial in $H$ cannot be achieved in this setting. Then, we propose an online algorithm with a sample complexity in $SAD^2/\varepsilon^2$, as well as a novel approach based on a data-dependent stopping rule that we believe is promising to further reduce this bound.

Main paper: 
 introduction: 
 Reinforcement learning (RL) is a paradigm in which an agent interacts with its environment, modeled as a Markov Decision Process (MDP), by taking actions and observing rewards. Its goal is to learn, or to act according to, a good policy, that is a mapping from state to actions which maximizes cumulative rewards. However, there are different ways to define this notion of (expected) cumulative reward: in the finite horizon setting, one should maximize the expected sum of rewards up to a certain fixed horizon; in the discounted setting, each consecutive reward is γ times as important as the previous one, with 0 < γ < 1. In this paper, we focus on the average reward setting, in which the value of a policy is measured by its asymptotic mean reward per time step. This setting is ideal for long-term learning, as there is no need to tune the horizon or discount parameters. However, the asymptotic nature of its optimality criterion makes the problem more complicated and highly sensitive to small changes in the MDP, which is less observable in the finite horizon or discounted settings.Formally, a Markov Decision Processes is defined as a tuple (S,A,P ,r) where S is the state space of finite size S, A is the action space of finite size A. Letting Σ X denote the set of distribution over a set X , P : S × A → Σ S is the (assumed unknown) transition kernel, and r : S × A → Σ [0,1] is the reward kernel. For each state-action pair (s, a), we denote by r s,a = E[r(s, a)] the (assumed known) mean reward 1 . At each time step t, the agent observes a state s t ∈ S, takes an action a t , and observes a reward r t ∼ r(s t , a t ) and a next state s t+1 ∼ P (s t , a t ). In an average-reward MDP (AR-MDP) the value of a policy π : S → ∆(A) is measured with its gain g π (s) = lim T →+∞ 1 T E π T -1 t=0 r t |s 0 = s where the expectation is taken when the agent follows policy π (i.e., s t ∼ π(a t )) from the initial state s. In this paper, we consider weakly communicating MDPs (defined in Section 2) in which a policy π ⋆ maximizing the gain in all states exists and has a constant value, denoted by g π⋆ .We are interested in the best policy identification problem: we want to build an algorithm that learns the MDP by taking actions and collecting observations, until it can, after some (possibly random) number of interactions τ output a policy π that is near-optimal. More precisely, given two parameters ε ∈ (0, 1) and δ ∈ (0, 1) we seek an (ε, δ)-Probably Approximately Correct (PAC) algorithm, that is an algorithm that satisfies P (τ < ∞, ∃s ∈ S, g π⋆ -g π (s) > ε) ≤ δ .Our objective is to find such an algorithm that has minimal sample complexity, i.e., that requires the least amount of steps τ , with high probability or in expectation. Two different models can be considered for the collection of observations. In the online model, the algorithm can only choose the action a t to sample at each time step, as the state s t is determined by the MDP's dynamics and the previous actions. With a generative model however the agent can sample the reward and next state of any state action pair (s t , a t ), regardless of which state it arrived in at the previous time step.To the best of our knowledge, prior work on (ε, δ)-PAC best policy identification in AR-MDPs has exclusively considered the generative model setting. In the online setting, the regret minimization objective has however been studied a lot (e.g., [9, 2, 3] ). Existing sample complexity or regret bounds feature different notions of complexity of the MDP, besides its size S, A. The diameter D and the optimal bias span H, formally defined in the next section, are two such complexity notions that both feature in lower or upper bounds on the sample complexity of existing algorithms. More specifically for (ε, δ)-PAC policy identification, the work of [22] provides a worse-case lower bound showing that there exists an MDP on which any (ε, δ)-PAC algorithm using a generative model should have a sample complexity larger than Ω((SAD/ε2 ) log(1/δ)). The recent work of [27] provides an (ε, δ)-PAC algorithm that takes H as input and whose sample complexity is O (SAH/ε 2 ) log(1/δ) 2 . Using that H ≤ D, this algorithm is thus optimal, and the lower bound is also in Ω((SAH/ε 2 ) log(1/δ)). This raises the following question: can an algorithm attain the same optimal sample complexity without prior knowledge of H? More broadly, as detailed in the next section, all existing (ε, δ)-PAC algorithms require some form of prior knowledge on the MDP, and we propose the first algorithms that are agnostic to the MDP.In the generative model setting, a first hope to get an algorithm agnostic to H is to plug-in a tight upper bound on this quantity in the algorithm of [27] . Our first contribution is a negative result: the number of samples necessary to estimate H within a prescribed accuracy is not polynomial in H, S and A. This result is proved in Section 3. On the positive side, by combining a procedure for estimating the diameter D inspired by [21] with the algorithm of [27] we propose in Section 4 Diameter Free Exploration (DFE), an algorithm for communicating MDPs that does not require any prior knowledge on the MDP and has a near-optimal O (SAD/ε 2 ) log(1/δ) sample complexity in the asymptotic regime of small ε. Then in Section 5 we discuss the hardness of (ε, δ)-PAC policy identification in the online setting. We notably prove a lower bound showing that the sample complexity of (ε, δ)-PAC policy identification cannot always be polynomial in S, A and H, even with the knowledge of H. On the algorithmic side, we propose in Section 6 an online variant of DFE whose sample complexity scales in SAD 2 /ε 2 . As prior work, DFE hinges on a conversion between the discounted and average-reward settings [22] and uses uniform sampling. Departing from this approach, we further propose a novel data-dependent stopping rule tailored for AR-MDPs that can be used both in the generative model and the online setting. We prove that it is (ε, δ)-PAC for any (possibly adaptive) sampling rule and give preliminary sample complexity guarantees.T -1 t=0 r t |s 0 = s . By writing P π = (P (s, π(s))) s , and introducing P π = lim T →+∞ 1 T T t=1 P t-1 π the asymptotic distribution matrix, as well as defining r π (s) = E[r(s, π(s))], we have g π (s) = P π (s)r π . Finally, we can define the bias vector b π = +∞ t=1 P t-1 π -P π • r π . Those vectors satisfy the so-called Poisson equations (see [18] ):EQUATIONWe notice that the solution, b π , is defined up to an additive element in Ker(I -P π ). We can then define g ⋆ the optimal gain and (up to an additive constant) b ⋆ the optimal bias satisfyingEQUATIONwhere p s,a is the (row) vector of transition probabilities from (s, a). We further defineH = max s b ⋆ (s) -min s b ⋆ (s)as the span of the optimal bias. The optimal bias span is always smaller than the diameter [2] , which motivates a line of work replacing D with H in existing regret bounds [2, 7] . These improved bounds are however obtained only when H is known. Similarly existing sample complexity bounds featuring H all require this knowledge, as discussed in more detail below.In addition to the diameter D and the optimal bias span H, we define the mixing time t ⋆ mix = max π inf t ≥ 1 : max s P t π (s) -P π (s) 1 ≤ 1 2O SA(τ t ⋆ mix ) 2 ε 2 log(1/δ) 1 √ τ S ≤ P π (s) ≤ √ τS , τ known t ⋆ mix over all policies, known [11] OSA(t ⋆ mix ) 2 ε 2 log(1/δ) t ⋆ mix , known [12] O SAt ⋆ mix,D ε 3 log(1/δ) t ⋆ mix,D , known [16] O SA(t ⋆ mix ) 3 ε 2 log(1/δ) t ⋆ mix , known (policy gradient) [24] O SAt ⋆ mix,D ε 2 log(1/δ) t ⋆ mix,D , known [22] O SAH ε 3 log(1/δ) H known [26] O SAH 2 ε 2 + S 2 AH ε log(1/δ) H known [27] O SAH ε 2 H known This paper O SAD ε 2 + S 2 AD 2 log(1/δ) no prior knowledge [12] Ω SAt ⋆ mix ε 2Lower bound (worse case)[22] Ω SAD ε 2 log(1/δ) Lower bound (worse case)which has also appeared in previous sample complexity bounds. By default the maximum is taken over all stochastic policies π : S → Σ A , and we denote by t ⋆ mix,D the same quantity where the maximum is restricted to deterministic policies.Multiple papers have considered the problem of finding an ε-optimal policy in average-reward with access to a generative model. We summarize existing results in Table 1 . [12] and [22] derived worse case lower bounds for the problem by exhibiting MDPs on which a certain number of samples must be collected to guarantee correctness of any (ε, δ)-PAC algorithm. The literature has first focused on the mixing time as a measure of the complexity of MDPs [23, 11, 12, 16] , until the mixing time-scaling lower-bound for the sample complexity was matched by [24] , for an algorithm taking t ⋆ mix,D as input. Algorithms using the optimal bias span H were introduced more recently, by [22] and [26] , and the lower bound scaling in H was matched up to logarithmic factors by [27] . This side of the literature has mostly used the links between discounted and average-reward MDPs and has used that for known H it is possible to choose a discount γ (with 1 -γ of order ε/H) such that H-optimal policies in the discounted MDP are ε-optimal in the average-reward MDP [22] . This idea leads to upper bounds of the sample complexity that scale with the (assumed known) upper bound on H. To make these algorithms agnostic to the MDP, a natural question is therefore: can we find a tight upper bound on H from the data?3 On the hardness of estimating HIn this section, we investigate the complexity of estimating the optimal bias span H and more specifically of finding upper bounds on this quantity. Definition 1. We say an algorithm computes a ∆-tight upper bound for the optimal bias span with probability 1 -δ when, on any MDP of optimal bias H, it outputs Ĥ such that with probability higher than 1 -δ, H ≤ Ĥ ≤ H + ∆.Theorem 1 shows that there exists an MDP on which the sample complexity of an algorithm finding a ∆-tight upper bound with probability larger than 1 -δ can be arbitrarily large. As a consequence, there cannot exist a bound on this sample complexity depending solely on S, A, H, δ and ∆.Theorem 1. For any δ < 1 2e 4 , T > 0, ∆, there exists an ergodic MDP M with optimal bias span H = 1/2, S = 3 and A = 2 such that any algorithm that computes a ∆-tight upper bound for the optimal bias span with probability 1 -δ under a generative model assumption needs (in expectation) more than T samples in M.To give an idea of the proof, we first focus on the weakly-communicating setting, with the full proof and the necessary ergodicity transformation detailed in Appendix A. We use the family of MDPs (M R ) 0<R<1 displayed in Figure 1 . Indeed, having R < 1/2 makes the full-line policy optimal; since moving from one state to the optimal final state (1) is very easy in this case, no state is drastically worse than another, hence a small optimal bias span, H = 1/2. However, R > 1/2 makes the dashed-line policy optimal; moving from state 3 to state 2 is more difficult as p is small, taking on average 1/p time steps, and state 3 has a worse reward than state 2; thus state 3 is considered way worse than state 2, hence a high optimal bias span, H = 1+p p R. Thus, to bound H tightly, one needs to know whether R > 1/2 or R < 1/2, which can require many samples if R is very close to 1/2. We remark that since the hard MDP instance in our proof has a fixed optimal bias span 1/2, we would have the same problem if we looked for algorithms trying to find Ĥ such that, with high probability, H ≤ Ĥ ≤ (1 + ∆)H. Moreover, instead of looking for upper bound we could also consider the task of estimating H within a given margin of error and the same issue would arise.1 2 3 1 2 , 1 R, 1 0, 1 -p 0, p 0 , 1 0 , 1 0 , 1While Theorem 1 does not preclude the existence of an algorithm that is agnostic to H and reaches a O((SAH/ε 2 ) log(1/δ)) sample complexity, it still suggests that assuming a known upper bound on H is a lot to ask. In the next section we will see that for communicating MDPs such an assumption is not needed to attain a near-optimal sample complexity.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: Our claims are that it is not possible to feasibly estimate H (shown in Theorem 1), that our new algorithm (Algorithm 1) requires no prior knowledge, is (ε, δ)-PAC, and near optimal (Theorem 2); that, in the online setting, the sample complexity of best policy identification does not scale polynomially with H (Theorem 3); that our new proposed stopping rule is (ε, δ)-PAC (Theorem 6).Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 In order to position our work in the literature on best policy identification in average-reward MDP, we start by recalling some properties of average-reward MDPs and give a formal definition of the different complexity measures that have appeared in the literature.First of all, it can be more or less easy to travel through the MDP and visit some states. We call an MDP weakly communicating if there exists a closed set of states that are all reachable from every other state (meaning S ′ ⊂ S such that for any s, s ′ in S ′ , min π:S→A E[min{t, s t = s ′ }|s 0 = s, ∀t ′ , a t ′ = π(s t ′ )] < +∞) and a possibly empty set of states which are transient (meaning the return time min{t, s t = s} when the chain starts with s 0 = s is not almost surely finite) under any policy. Furthermore, when there is no such transient state, the MDP is then communicating, and it is possible to define the diameter of the MDP to quantify how fast circulating in the MDP can be:D = max s̸ =s ′ min π:S→A E[min{t > 0, s t = s ′ }|s 0 = s, ∀t ′ , a t ′ = π(s t ′ )] .Finally, if the MDP satisfies for any policy π and states s, s ′ that E[min{t, s t = s ′ }|s 0 = s, ∀t ′ , a t ′ = π(s t ′ )] < +∞, then the MDP is ergodic. If the MDP satisfies this except for a possibly empty set of transient states, the MDP is then called unichain. In the following, the MDPs are all considered at least weakly communicating, though some results shall require some stronger assumptions, which we will specify. Notably, every mention of the diameter will assume communicating MDPs.The diameter has appeared in previous upper and lower bound on the regret [9] and in the lower bound of [22] for best policy identification. The diameter is also used in the literature on the Stochastic Shortest Path (SSP) problem, in which one seek to minimize the sum of cost obtained before some goal state is reached (some details on this alternative framework are given in Appendix B). The SSP-diameter is defined as the maximum over states of the minimum expected steps to the goal state, and it appears in the sample complexity bounds given by [21] . We will see in the following that there are multiple similarities between the SSP setting and our average-reward setting, the use of the diameter being only one of them.For a policy π : S → A, we define the gain g π (s) = lim T →+∞Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: The limitations of the paper are addressed in the conclusion Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
a near-optimal algorithm without prior knowledge: 
 As we have seen, finding tight upper bounds on H is not feasible in finite time. In the literature on regret minimization, in which improved regret bounds featuring H have also been derived when H is known, two types of workarounds have been used. In the REGAL algorithm 3 , [2] propose to use a doubling trick to counter not knowing H, at the expense of an additional factor of √ S in the regret. The doubling trick method is not applicable to BPI problems, though. For communicating MDPs, the idea of plugging-in an upper bound on D which is also a (not necessarily tight) upper bound on H was first proposed by [25] and permits to match the minimax lower bound on the regret of [9] featuring D. In this section, we translate this idea to the best policy identification setting.We propose Diameter Free Exploration (DFE), stated as Algorithm 1, which combines a diameter estimation sub-routine that follows from the work of [21, 20] with the state-of-the-art algorithm of Data: Accuracy ε ∈ (0, 1), confidence level δ ∈ (0, 1)Let D be the output of Algorithm 2 with accuracy 1 and confidence level δ/2. Let π be the output of Algorithm 3 with accuracy ε, upper bound H = D and confidence level δ/2 return π Algorithm 1: Diameter Free Exploration (DFE) [27] when (an upper bound on) H is known. Both components are described in details in Appendix B with their theoretical properties. More precisely, DFE first calls Algorithm 2 to output a quantity D which satisfies D ≤ D ≤ 4D with probability larger than 1 -δ/2, using a random number of samples N from each state action pair (s, a) that satisfies N = O(D 2 (log(1/δ) + S)). Then Algorithm 3 (which also uses uniform sampling) takes as input D and is guaranteed to output a policy that is ε-optimal with probability larger than 1 -δ/2, using a total number of samples of orderO SA D ε 2 log 1 δ. This gives the following theorem.Theorem 2. Algorithm 1 is (ε, δ)-PAC and its sample complexity satisfies, with probability 1 -δ,τ = O SAD ε 2 + D 2 SA log 1 δ + D 2 S 2 A .From Theorem 4 of [22] , there exists a communicating MDP with a sample complexity in Ω SAD ε 2 ln (1/δ) . Therefore, the DFE algorithm is worse than the lower bound by a multiplicative factor 1 + Dε 2 + DSε 2 log 1/δ . In particular, in the regime of small ε, this algorithm is optimal up to logarithmic factors. 
on the hardness of best policy identification in the online setting: 
 In the online setting, many algorithms with regret guarantees have been designed, however to the best of our knowledge there exists no online algorithm that is guaranteed to output a policy π satisfying g π ≥ g * -ε with probability larger than 1 -δ4 . In this section, we give some elements of explanation.On the hardness of a regret to PAC conversion In the finite-horizon setting, [10] gave a way to convert any algorithm guaranteeing sublinear regret into a BPI algorithm with finite sample complexity. However, in average-reward MDP, this conversion is not straightforward. Indeed, it hinges on the fact that selecting at random one of the policies played during the regret-minimizing algorithm should yield a good enough policy: the more time steps there are, the smaller the regret induced by the most recent policy is, thus the better the policy is. However, in our setting, we know that the empirical mean reward of a policy converges towards the gain of this policy, but the speed of this convergence is determined by the mixing time. Moreover, as shown in [22] , this mixing time can be arbitrarily large. However, the regret is not defined asymptotically. In [9] , the regret at time T is defined asT g * -E[ T t=1 r t ]. In [17], the regret is E π * [ T t=1 r t ] -E[ T t=1 r t ].As the mixing time can be big, it is possible that these regret measures are small for a large number of steps, but that the underlying policy is not anywhere near asymptotically optimal.It is therefore not possible to preemptively define the number of steps necessary for the regretminimizing algorithm to find an asymptotically good policy, and not just one that is good on the short term. For example, for any N ∈ N, N ≥ 2, consider the MDP M p displayed in Figure 2 with p = 1 N and any p ′ < 1-ε 1+ε p. While the dashed-line policy is asymptotically best, the full-lined policy is better for at least N time steps, and is not even ε-optimal, as we show in Appendix C.1. An algorithm guaranteeing low regret (over a slightly modified version of the MDP to guarantee ergodicity) could therefore take the full-line action for a number of steps independent of the known parameters S and A, and the knowledge of N would be required to know how many samples are 1 2 3 1, 1 -p 0, 1 -p 1, 1 -p ′ 0, 1 -p ′ 0, p 1, p ′ 1, p 0, p ′s 1 s 2 s 3 ... s S {1, p} j 1 j 2 j S-2 j S-1{1, 1 -p} Figure 3 : MDP M j , the hard instance for Theorem 3 necessary for best policy identification. This means that a wrapper turning any regret minimization algorithm into a best policy identification algorithm would require estimating and incorporating this measure N somewhere, which argues against the existence of a straightforward wrapper as in the episodic setting. Similar arguments in the SSP setting have been brought up for example in [21] .A hardness result As the following lower bound shows, it is in fact not possible at all to have an online best policy identification algorithm that has a sample complexity bound polynomial in S, A and H. This result is as a counterpart of the hardness result proved by [5] in SSP-MDPs.Theorem 3. For any S ≥ 4, A ≥ 4, ε ∈ 0, 1 4 , δ ∈ 0, 1 16 , and any (ε, δ)-PAC online algorithm, there exists a weakly communicating MDP with S states, A actions, mean rewards in [0, 1], H ≤ S and D ≥ A S-1 /16ε such that if the algorithm starts in a given states 1 , E[τ ] = Ω A S-1 ε .Sketch of proof For j ∈ (S -1) A , we define the hard instance M j as in Figure 3 . An agent in s 2 must execute the precise sequence of actions j to get back to s 1 , which is the only state that generates non zero rewards. Since not learning this precise sequence would mean the agent will perform badly on one of the M j , and therefore perform a very suboptimal policy, the agent will need to have a big enough sample size to at least see s 2 with high probability when starting in s 1 . With a small value of p, it is possible to make the sample complexity exponentially big, as we detail in Appendix C.2. This hard MDP is actually inspired from the hard SSP-MDP instance considered by [5] to prove that sample-efficient learning is impossible in the online setting of SSP. Indeed, their hard MDP is one where the cost is always the same in each state, in which case we can easily transform the SSP problem into an average reward one, as shown in Figure 5 . Indeed, if the costs of the SSP-MDP are all equal and non-zero, then finding an optimal policy in it can be show to be equivalent to finding an optimal policy in the corresponding AR-MDP in which the only reward is in the initial state.We remark that while the hard MDP instances M j used in our proof have an optimal bias span H that is upper bounded by S, its diameter is exponential is S. Hence while Theorem 3 implies that no online algorithm can get a O SAH ε 2 sample complexity (with or without the knowledge of H) on every instance and for every ε, it does not rule out the possibility to have an online algorithm with a sample complexity scaling with D. We propose such an algorithm in the next section.6 Algorithms for the online setting 6.1 Diameter Free Exploration for the online setting Our first idea to tackle the online setting is to propose an online variant of the Diameter Free Exploration algorithm from Section 4. While the first ingredient of DFE is Algorithm 2, a diameter estimation procedure based on a generative model, we could use instead the online diameter estimation procedure proposed by [20] to get an upper bound D ≤ D ≤ 4D with probability larger than 1 -δ using a slightly worse sample complexity in Ōδ (D 3 SA) 5 . The second ingredient, Algorithm 3, starts by collecting a fixed number of samples n proportional to ( D/ε 2 ) log (12SA/(δε)) from each (s, a), using the generative model. We can replace this step by using the GOSPRL algorithm of [20] to collect this amount of samples with an online algorithm, which requires Ōδ (SADn + D 3/2 S 2 A) samples, with high probability. We call the resulting algorithm Online-DFE. Theorem 4. Online-DFE is (ε, δ)-PAC and its sample complexity satisfies, with probability largerthan 1 -δ, τ = Ōδ SAD 2 ε 2 + S 2 AD 3 .Compared to Theorem 2 for the generative model setting, we note a multiplicative D factor in the sample complexity, as well as a less explicit dependency in δ. Still, it provides an online PAC algorithm whose sample complexity scales in SAD 2 /ε 2 in the small ε regime. We remark that the extra factor D compared to the lower bound for the generative setting comes from the use of GOSPRL and the (mostly theoretical) conversion from the generative to the online setting. To get more efficient algorithms, a promising direction is to investigate more adaptive algorithms, directly tailored for the average-reward setting. This is what we do next. 
towards more adaptive algorithms: 
 We recall that an identification algorithm uses three components: a sampling rule, selecting at time t a state-action pair (s t , a t ), after which the next state s t+1 ∼ P (s t , a t ) and the reward r t ∼ r(s t , a t ) is observed; a stopping rule τ which decides whether the data collection can be stopped, and a recommendation π which is a guess for a near-optimal policy that depends on the first τ observations. In the online setting, the sampling rule is actually reduced to the choice of a t given s t , as we have the constraint that s t+1 ∼ P (s t , a t ). In this section we introduce a novel stopping rule, that can be used in conjunction with different sampling rule, possibly in the online setting.The Value Iteration stopping rule We first introduce some notation to define the stopping rule. We denote by N n s,a = n t=1 1((s t , a t ) = (s, a)) the number of visits to the state action pair (s, a) in the first n steps and pn s,a the empirical estimate of the transition probability vector p s,a built at step n, where p n s,a can be arbitrarily chosen to be the constant vector equal to 1 S if N n s,a = 0. Our stopping rule takes inspiration from the stopping condition of value iteration for average-reward MDPs. It relies on a sequence of bias vectors b n ∈ R S and on the ability to build confidence intervals on the quantity I s,a (n) = r s,a + p s,a b n -b n (s). This leads us to build an upper bound of the span of I s,a (n), which can be seen as the average-reward equivalent of the Bellman error as defined in [8] . We know that, if b n = b ⋆ , then (max a I s,a (n)) s is equal to the constant vector g ⋆ . Conversely, by Theorem 8.5.5 of [18] , if the span of (max a I s,a (n)) s is small, then the associated policy π(s) = arg max a I s,a (n) is approaching the optimal one; this can be used to derive a criterion for correctness of value iteration in average-reward MDPs. Therefore, by examining an upper-bound on the span of I, we get the following theorem. Theorem 5. In a weakly communicating MDP, for a given vector b n ∈ R S , if for all pairs (s, a) we have p s,a b n ∈ L n s,a (b n ; δ), U n s,a (b n ; δ) , then defining πn (s) = arg max a I n,♭ s,a (b n ; δ), we havemin s max a I n,♭ s,a (b n ; δ) ≤ g πn ≤ g ⋆ ≤ max s max a I n,♯ s,a (b n ; δ)whereI n,♭ s,a (b n ; δ) := r s,a + L n s,a (b n ; δ) -b n (s) and I n,♯ s,a (b n ; δ) := r s,a + U n s,a (b n ; δ) -b n (s).Now to propose a concrete stopping rule, we provide expressions of U and L chosen such that the premise of Theorem 5 is satisfied in every round n, with high probability. KL(p, q) denotes the Kullback-Leibler divergence between the probability vectors p and q on S. Definition 2. Given a sequence of (b n ) n , we defineU n s,a (b n ; δ) = max p ′ b n N n s,a KL(p n s,a , p ′ ) ≤ x(δ, N n s,a ) L n s,a (b n , δ) = min p ′ b n N n s,a KL(p n s,a , p ′ ) ≤ x(δ, N n s,a )for the threshold function x(δ, y) = log(SA/δ) + (S -1) log (e(1 + y/(S -1))) and letEQUATIONThe following result is a consequence of Theorem 5 and a KL-based time uniform concentration result for the transition probabilities from [1] (Lemma 5 in Appendix). Using Pinsker's inequality (see Remark 1 in Appendix where we discuss some computational aspects), we can also justify that this theorem hold for U n s,a , L n s,a replaced byEQUATIONTheorem 6. For any sampling rule ((s n , a n )) n , and any sequence (b n ) n of bias vectors, the algorithm using the stopping rule τ = τ ε,δ defined in (6) and recommending π(s) = arg max a I τ,♭ s,a (b τ ; δ) satisfies P (τ < ∞, g ⋆ -g π > ε) ≤ δ.Theorem 6 shows that for any sampling rule, be it in the generative model or in the online setting, the stopping rule ( 6) and associated recommendation rule yields an (ε, δ)-PAC algorithm, for any choice of bias vector sequence b n . Of course, bad choices of sampling rules and bias vectors could still yield τ = ∞ almost surely (e.g. picking always (s t , a t ) = (s 1 , a 1 ) when a generative model is available).Choosing a sampling rule As a sanity-check we analyze in Appendix D.2 an algorithm which combines the simplest possible sampling rule, uniform sampling from a generative model, with the VI stopping rule (6) where the sequence of biais vector is b n = bn where bn is the optimal bias vector in the AR-MDP with rewards r s,a and transition probabilities given by (p n s,a ) s,a (see Algorithm 4). We prove in Theorem 9 that in unichain MDPs, for sufficiently small ε the sample complexity of this algorithm is bounded with probability larger than 1 -δ by O SA(H∨Γ M ) 2 ε 2 log 1 δ + S , where Γ M is some constant depending on the MDP. We refer the reader to Appendix D.2 for the definition of this constant, that has a complex expression and should be in most case larger than H.We remark that we could also use GOSPRL to turn Algorithm 4 into an online algorithm (using phases of increasing length in which we collect a uniform number of samples using GOSPRL and check our stopping rule), with a sample complexity essentially multiplied by D. However the resulting sample complexity is likely to be much larger than SAD 2 /ε 2 in the small ε regime, making this algorithm not very interesting. We believe that to get efficient algorithms for the online setting it is important to depart from this uniform sampling + GOSPRL approach. Our stopping rule actually suggests some clever online choices that could be used to make the algorithm stop earlier. For example it could be interesting to make a greedy choice of the bias vector b n that minimizes over b ∈ R S the quantity max s max a I n,♯ s,a (b; δ) -min s max a I n,♭ s,a (b; δ). Assuming we could compute this vector, a possible online sampling rule could be optimistic choice a n = argmax a [r s,a + U n sn,a (b n , δ)]. We leave the analysis of such algorithms for future work.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA]Justification: We have made no experiments Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusion and perspective: 
 We provided several elements indicating that the optimal bias span H may not be an adequate complexity measure for ε-optimal policy identification in an average-reward MDP. In the generative model setting, as all existing algorithms with sample complexity featuring H require prior knowledge of this quantity, we investigated the question of estimating H and proved that the sample complexity of this estimation task can be arbitrarily large. Then, in the online setting, we gave a lower bound on the sample complexity indicating that no algorithm can get a SAH/ε 2 sample complexity on every MDP, with or without the knowledge of H. On the algorithmic side, we proposed the first best policy identification algorithms for the generative model setting that does not require any form of prior knowledge on the MDP. By estimating the diameter D instead of H, DFE attains a near-optimal sample complexity in SAD/ε 2 for communicating MDPs. We further proposed an online variant of DFE with a slightly larger SAD 2 /ε 2 sample complexity, which is a factor D away from the worse case lower bound established in the generative model setting. We leave as an open question whether there exists online algorithms with a SAD/ε 2 sample complexity. In future work, we will investigate whether the novel adaptive stopping rule proposed in our work can lead to this reduced sample complexity, when combined with a suitable online sampling rule.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA] Justification: We have made no experiments Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: Our work is theoretical enough that its societal impact is negligible Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We do not have any experiments, and release no models Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: We use no existing assets Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: We only prove here the result for weakly communicating MDPs, and provide the ergodic MDP necessary to prove the general theorem. ease the notation, we denote by M ε and M ′ ε respectively the MDPs M 1 2 -ε and M 1 2 +ε in Figure 1 . The rewards distribution in these MDPs are assumed to be Bernoulli variables with the means indicated in the figure . The optimal policy in M ε always chooses the actions represented by a full line. Its gain is 1 2 , its bias vector (up to an additive constant) is (0, -1 2 , -1 2 ). In M ′ ε , the optimal policy always chooses the dashed actions and its optimal gain is 1 2 + ε. Using the Poisson equations, we can show that its associated bias vector (up to an additive constant) is-1 2 + ε 1+p p , 0, -1 2 + ε 1 p .With H ε the span of the optimal bias for M ε and H ′ ε that of M ′ ε , we have:H ′ ε -H ε = 1 p 1 2 + ε (1 + p) - p 2 = 1 p 1 2 + ε + ε = ∆ -ε 1 2 + ε 1 2 + ε + ε = ∆Consider now an algorithm that outputs Ĥ a ∆-tight upper bound for the optimal bias span with probability greater than 1 -δ on any MDP. We denote by P and P ′ the probability with regards to M ε and M ′ ε respectively, and E and E ′ the associated expectation. We denote by τ the total number of samples used before stopping, by T the number of samples of the dashed action taken in state 2 before stopping and by K t the number of times the agent gets a reward of 1 among the first t visits of state 2. We introduce the three eventsE 1 = { Ĥ < H ′ ε } E 2 = max 1≤t≤t ⋆ | 1 2 -ε t -K t | ≤ z E 3 = T ≤ t ⋆ ,where we definez = 2 1 2 -ε 1 2 + ε t ⋆ ln d θ , with θ = exp -4d ′ ε 2 t ⋆ ( 1 2 -ε)( 1 2 +ε) and let t ⋆ = ( 1 2 -ε)( 1 2 +ε) 4d ′ ε 2 ln 1 2dδ . We let E = E 1 ∩ E 2 ∩ E 3 .Let W be the interaction history of the learner and the generative model, L(w) = P (W = w) andL ′ (w) = P ′ (W = w). For K = K T , L ′ (W ) L(W ) 1 E = (1/2 + ε) K (1/2 -ε) T -K (1/2 -ε) K (1/2 + ε) T -K 1 E ≥ θ d 1 Eby the arguments within the proof for Lemma 13 of [5] . Using a change of measure, we can writeEQUATIONMoreover, in M ε , K t -(1/2 -ε) t is the sum of t Bernoulli variables of expectation (1/2 -ε), and thus of variance (1/2 -ε)(1/2 + ε). Kolmogorov's inequality states thatP (E 2 ) = P max 1≤t≤t ⋆ K t - 1 2 -ε t > ε ≤ t ⋆ 1 2 -ε 1 2 + ε ε 2which entails P (E 2 ) ≥ 7/8. The detailed computation is given in the proof for Lemma 12 of [5] . Now, we assume towards contradiction that P (E 3 ) ≥ 7/8. Using the above, this yieldsP E ≤ P (E 1 ) + P (E 2 ) + P (E 3 ) ≤ δ + 2 8 < 1 2 ,where the first inequality uses that P (E 1 ) ≥ 1 -δ by the correctness of the algorithm and the second inequality uses that δ ≤ 1 2e 4 . Hence, we have P (E) > 1 2 which leads to P ′ (E 1 ) > δ using (8) . This contradicts the correctness of the algorithm. Therefore, we have P (E 3 ) < 7 8 . It follows that with probability larger than 1 8 , T ≥ t ⋆ on M ε , henceE[τ ] ≥ E[ T ] ≥ t ⋆ 8 ≥ T,which concludes the proof.More generally, adding the transitions described in Figure 4 with τ ′ = τ p 1+p can be used to show that computing a ∆ 1+τ -tight upper bound for the optimal bias span with high probability would need in expectation more than T samples. In this Appendix, we provide some details on the two components of our near-optimal algorithm: a procedure to provide a high-probability upper bound on the diameter (Algorithm 2) and a near-optimal algorithm for best policy identification in an average reward MDP that requires an upper bound on H as an input (Algorithm 3). Finally, we give the proof of Theorem 2.EQUATIONThe procedure proposed by [20] for estimating the diameter hinges on the observation that the diameter can expressed in terms of optimal values in a goal-oriented Markov Decision Decision (or SSP-MDP for Stochastic Shortest Path). We recall that in a SSP-MDP the transition kernel is coupled with a goal state s g ∈ S and a cost function c : (s, a) → c(s, a). The value of a (deterministic) policy π, that is to be minimized, is denoted byV π c,sg (s) = E π    τ (sg ) π (s) t=1 c(s t , π(s t )) s 1 = s   where τ(sg) π(s) = inf{t : s t+1 = s g |s 1 = s, π} is the number of steps before reaching the goal when starting from state s and following policy π. The diameter can thus be writtenD = max s max s ′ ̸ =s min π E[τ (s) π (s ′ )] = max s max s ′ ̸ =s min π V π 1,s (s ′ ) = max s max s ′ ̸ =s V ⋆ 1,s (s ′ )where V ⋆ c,sg denotes the optimal (i.e. minimal) value function in the SSP-MDP with cost c and goal state s g and 1 is the cost function that is constant and equal to 1.Prior works on SSP-MDPs [19, 21] have proposed and analyzed an Extended Value Iteration scheme for SSP, whose goal is to obtain confidence bounds on V ⋆ c,sg , that we now recall for completeness. Given a cost function c and a goal state s g , EVI-SSP c,sg takes as input a set of plausible transitions P = (P(s, a)) s,a such that P(s, a) are included in the set of probability distribution over S (and the unknown vectors p s,a is believed to belong to P(s, a)), and a precision µ VI . It introduces the extended optimal Bellman operator, defined for v ∈ R S as We denote by V π c,sg (s) the value function of policy π in the SSP with cost function c, goal state s g and transition kernel p. Previous work (see e.g. Lemma 4 of [21] ) have established the following properties.Lv(s) = minLemma 1. Assume that, for all (s, a), p s,a ∈ P(s, a). Letting ( v, p, π) = EVI-SSP c,sg (P, µ VI ), the following inequalities hold (component-wise):(i) v ≤ V ⋆ c,sg and v ≤ V ⋆ c,sg ≤ V π c,sg (ii) if µ VI ≤ cmin 2 then V π c,sg ≤ 1 + 2µVI cmin v.Notably, this result gives an upper bound on the optimal value in the optimistic SSP-MDP. With the additional help of a simulation lemma, proved by [20] , we can further relate it to the value in the true SSP-MDP.Lemma 2 (Lemma 2 in [21] ). 6 Let p and p be two transition kernels such that for all (s, a), ∥p s,a -p s,a ∥ 1 ≤ η. Assume that c min > 0 and that under both p and p there exists at least one policy that reaches s g almost surely from any state (such a policy is called proper). Let π be a proper policy in p such thatEQUATION)Then π is proper in p andEQUATIONFinally, the last step to be able to apply Lemma 1 is to construct the sets P(s, a) that contains the true transition probabilities with high probability. This can be done as in the rest of the paper by relying on Lemma 5, which gives confidence regions of the form{p ∈ Σ S : ∥p -ps,a,n ∥ 1 ≤ B(n, δ)}where ps,a,n is the empirical estimate of the transition probability after the n-th transition has been observed from (s, a) and B(n, δ) = 2 log(SA/δ)+2(S-1) log(e(1+n/(S-1)))n .The resulting algorithm for estimating the diameter is described in Algorithm 2. It is a slight variation of the procedures proposed by [20] to estimate the SSP diameter and by [21] to estimate the diameter in the online setting. In particular, our instantiation relies on simpler confidence regions.Data: Accuracy ε > 0, confidence level δ ∈ (0, 1)Set W = 1 2 and v ∞ = 1 while v ∞ > W do W ← 2WSet accuracy η = ε 4W and compute N = N (δ, η) = inf{n : B(n, δ) ≤ η} Call the generative model until each (s, a) gets N visits. Let each (s, a) let P(s, a) = {p ∈ Σ S : ∥p -ps,a,N ∥ 1 ≤ η} and P = (P(s, a)) s,a . for s = s 1 , ..., s S doLet ( v (s) , p (s) , π (s) ) = EVI-SSP 1,s P, 1∧ε 2 end Let v ∞ = max s max s ′ ̸ =s v (s) (s ′ ). end return D = (1 + η v ∞ /2) v ∞ Algorithm 2: A diameter estimation procedure Theorem 7. Let ε ≤ 1.With probability 1 -δ, Algorithm 2 run with parameters ε and δ outputs an estimate D which satisfiesD ≤ D ≤ 1 + ε(1 + ε) 2 (1 + ε)D using SA × N (δ, ε 8D ) samples where N (δ, η) := inf {n > 0 : B(n, δ) ≤ η} ,leading to an overall sample complexity ofO D 2 SA ε 2 log 1 δ + D 2 S 2 A ε 2where the O ignores logarithmic factors in S, A, D, 1/ε and log(1/δ).Proof. The proof closely follows that of [20] . We let W n be the value of W in the n-th iteration of the while loop (starting at n = 1), such that W n = 2 n-1 . We define η n = ε 4Wn and v n the value of v ∞ at the end of the n-th iteration. The number of iteration used by the algorithm is n = min{n :v n ≤ W n }. Assume the event E = (∀s, a, ∀n ≥ 1, ∥p s,a,n -p s,a ∥ 1 ≤ B(n, δ))holds. Using a property of the EVI scheme (first statement in Lemma 1), for all n, v (s)n ≤ V ⋆ 1,s ≤ D (component-wise), which yields v n ≤ D. Hence n is bounded by min{n : D ≤ W n } ≤ log 2 (D) + 1.We now bound the final accuracy η := η n . First, as v ∞ := v n ≤ W n , we have η ≤ ε 4 v∞ . Moreover, using thatD ≥ v n-1 > W n-1 = W n 2 further yields ε 8D ≤ η ≤ ε 4 v ∞ .We let v (s) , p (s) , π (s) be the output of Extended Value Iteration with goal state s in the final iteration, and let V 1,s denote the value function in the SSP MDP with costs 1, goal state s and transition kernel p (s) . For every s, s ′ , using the simulation lemma, we haveV ⋆ 1,s (s ′ ) ≤ V π (s) 1,s (s ′ ) ≤ (1 + 2 η∥ V π (s) 1,s ∥ ∞ ) V π (s) 1,s (s ′ ) provided that the condition 2 η∥ V π (s)1,s ∥ ∞ ≤ 1 is satisfied. This is the case by using the second statement of Lemma 1 together with the upper bound on η established above:2 η∥ V π (s) 1,s ∥ ∞ ≤ 2 η(1 + ε)∥ v (s) ∥ ∞ ≤ 2 η(1 + ε) v ∞ ≤ ε(1 + ε) 2 ≤ 1 ,where the last step uses that ε ≤ 1. Hence, one can writeV ⋆ 1,s (s ′ ) ≤ (1 + 2 η∥ V π (s) 1,s ∥ ∞ ) V π (s) 1,s (s ′ ) (a) ≤ (1 + 2 η(1 + ε)∥ v (s) ∞ )(1 + ε) v (s) (s ′ ) (b) ≤ (1 + 2 η(1 + ε) v ∞ )(1 + ε) v ∞ = D (c) ≤ 1 + (1 + ε)ε 2 (1 + ε)D,where (a) uses the second statement of Lemma 1, (b) uses the definition of v ∞ and (c)uses that v ∞ ≤ D and ηv ∞ ≤ ε/4. Recalling that D = max s,s ′ ̸ =s V ⋆ 1,s (s ′ ) yields that, on event E, D ≤ D ≤ (1 + (1 + ε)ε 2 )(1 + ε)D.Moreover, the number of samples collected per transition is N (δ, η) ≤ N δ, ε 8D . The conclusion follows from the fact that E holds with probability larger than 1 -δ (Lemma 5) and by upper bounding N δ, ε 8D using Lemma 6 in Appendix E. Specifically, choosing the parameters ∆ 2 = η 2 , a = 2 log SA δ , b = 2(S -1), c = e and d = e S-1 we getN (δ, η) ≤ 1 η 2 log SA δ + 2(S -1) η 2 log e + e (S -1)η 4 log SA δ + 8e η 4 .which leads to the approximation stated in Theorem 7.We recall here for completeness the algorithm of [27] to find an ε-optimal policy in an average reward MDP when an upper bound H of the optimal bias span H is known, and its theoretical guarantees. The algorithm consists in a slight variation of the Perturbed Empirical Model-Based Planning algorithm originally given by [15] (for which a refined analysis was proposed by [27] ) with the reduction from the average reward to the discounted case from [22] . Theorem 8. With probability 1 -δ, Algorithm 3 with parameters ε ∈ (0, 1], H satisfying H ≤ H and δ ∈ (0, 1) outputs a policy π satisfying P ∀s ∈ S, ρ ⋆ -ρ π (s) ≤ ε ≥ 1 -δ and collects a (deterministic) total number of transitions given byData: Accuracy ε ∈ (0, 1], upper bound H on H, confidence level δ ∈ (0, 1) Set discount factor γ = 1 -ε 12H Set n = 144C2H144C 2 SAH ε 2 log 12SA δε ,where C 2 is the constant in Theorem 1 of [27] .We let D be the output of Algorithm 2 run with parameters 1 and δ/2 and τ 1 the total number of samples it uses. From Theorem 7, it holds thatP D ≤ D ≤ 4D, τ 1 = O D 2 SA log(1/δ) + D 2 S 2 A ≥ 1 -δ/2.We let π be the output of Algorithm 3 run with parameter ε, D and δ/2 and τ 2 the total number of samples it uses. Using Theorem 8, we haveP g ⋆ -g π ≤ ε, τ 2 ≤ 144C 2 SA D ε 2 log 24SA δε D ≤ D ≥ 1 -δ/2.The total sample complexity being τ = τ 1 + τ 2 , using a union bound yields that with probability 1 -δ, it holds that g ⋆ -g π ≤ ε andτ ≤ O D 2 SA log(1/δ) + D 2 S 2 A + 576C 2 SAD ε 2 log 24SA δε = O SAD ε 2 + D 2 SA log 1 δ + D 2 S 2 A = O SAD ε 2 + D 2 S 2 A log 1 δ .We recall the MDP introduced in Figure 2 . We prove the following: for any N , for any p < 1/N and any p ′ < 1-ε 1+ε p, the policy in full line π is optimal for more than N steps, but is not ε-optimal in average reward. For that, we define u n the probability of being in state 1 at timestep n. We note that u n does not depend on the policy chosen. Since we know u 0 = 11 2 3 1, 1 -p 0, 1 -p 1, 1 -p ′ 0, 1 -p ′ 0, p 1, p ′ 1, p 0, p ′u n+1 = (1 -p)u n + p ′ (1 -u n ), we haveu n = (1 -p -p ′ ) n 1 - p ′ p + p ′ + p ′ p + p ′Therefore, the (asymptotic) gain for the full-line policy π is g π = p ′ p+p ′ , while that of the dashed-line policy π ′ is gπ ′ = 1 -p ′ p+p ′ = p p+p ′ . Since p ′ < 1-ε 1+ε p, p ′ (1 + ε) < p(1 -ε) p ′ < p -(p + p ′ )ε g π < g π ′ -εand we have indeed that π is not ε-optimal.Moreover, the empirical reward up to step n for policy π is r n = n t=0 u n , and r ′ n = n+1-n t=0 u n for policy π ′ . As (r n /n) n is decreasing and (r ′ n /n) n is increasing, policy π ′ becomes better than π whenn t=0 u n ≤ n+12 , that is, when(n + 1) p ′ p + p ′ + 1 - p ′ p + p ′ n t=0 (1 -p -p ′ ) t ≤ n + 1 2 p p + p ′ • 1 n + 1 • 1 -(1 -p -p ′ ) n+1 p + p ′ ≤ 1 2 - p ′ p + p ′ which implies p p + p ′ • 1 n + 1 • (n + 1)(p + p ′ ) -n(n + 1)(p + p ′ ) 2 p + p ′ ≤ 1 2 - p ′ p + p ′ by using that (1 -x) n+1 < 1 -(n + 1)x + n(n + 1)x 2 /2 for any 0 < x < 1. Finally, π ′ being better than π at timestep n implies -n 2 ≤ 1 2 -p ′ p+p ′ 1 p -1 p+p ′ , i.e., n ≥ 1 p ≥ N .Proof. For S, A, ε, δ satisfying the assumptions of Theorem 3, we let p = 16ε A S-1 and define the family of MDPs M j for any j ∈ A S-1 , displayed in Figure 3 . There are A actions available in each of the S states, but the figure only displays actions with distinct transitions.s 1 s 2 s 3 ... s S {1, p} j 1 j 2 j S-2 j S-1{1, 1 -p} Figure 3 : MDP M j (repeated from page 7)• In state s 1 , for any action a, a reward of 1 is incurred, and there is probability p of getting into state s 2 , and probability 1 -p of staying in s 1 .• In state s n for n ∈ {2, . . . , S}, taking action j n-1 transitions to state s n+1 (where s S+1 = s 1 ) and every other action transitions to state s 2 , with no reward.To summarize, it is very unlikely to get into state s 2 ; but, once it has been entered, only one specific deterministic policy can allow an agent to get back to the favorable state s 1 .Let π be a (possibly stochastic) policy. Let us write p j i = π(j i-1 |s i ) for i ∈ {2, ...S}, and x j π = S i=2 p j i . With P π,j the transition matrix under π in MDP M j , and P π,j = lim T →∞ 1 T T t=1 P t-1 π,j , we know that P π,j P π,j = P π,j . Since the MDP M j is unichain, by theorem A.2 of [18] , all the rows of P π,j are identical to a vector (η 1 , ...η S ) ∈ Σ S .We therefore deduce the following linear system:                       η 1 = (1 -p)η 1 + p j S η S η 2 = pη 1 + S n=2 (1 -p j n )η n ∀n ∈ {3, ...S}, η n = p j n-1 η n-1 S n=1 η n = 1Injecting the third equation into the second yieldsη 2 = pη 1 + S-1 n=2 (η n -η n+1 ) + η S -x j π η 2 and finally x j π η 2 = pη 1 . Therefore, η 1 1 + p(1 + p j 2 + p j 2 p j 3 + ... + x j π ) x j π = 1 =⇒ η 1 ≤ 1 1 + p x j π , using that 1 + p j 1 + p j 2 p j 3 + ... + x j π ≥ 1. Finally, g j π ≤ 1 1 + p x j π .The optimal policy in M j is to play action j n-1 in state s n for n ∈ {2, . . . , S}, so the above equation becomes η 1 (1 + p(S -1)) = 1 and the optimal gain in M j is g j = 1 1+p(S-1) . If a policy π is ε-optimal in M j , we haveg j π ≥ g j -ε 1 1 + p x j π ≥ 1 1 + p(S -1) -ε (S -1)p ≥ p x j π -ε 1 + (S -1)p + p x j π + (S -1)p 2 x j π x j π ≥ p 1 -ε (1 + (S -1)p) (S -1)p + ε (1 + (S -1)p) (S -1)x j π ≥ 1 1 + ε ((S-1)p+1) 2 (S-1)p(1-ε-ε(S-1)p) Since (S -1)p ≤ 1 4 , (1 + (S -1)p) 2 ≤ 2. Since we also have ε < 1 4 , (1 -ε -ε(S -1)p) ≥ 1 2 . Therefore, (S -1)x j π ≥ 1 1+ 4ε (S-1)p. Finally, 4ε (S-1)p ≥ 1, and x j π ≥ p 8ε . Since j x j π = 1, we deduce that each policy π can be ε-optimal for at most 8ε p MDPs in {M j } j . By denoting y j π = 1 {π is ε-optimal in Mj } , we have j y j π ≤ 8ε p . For the remainder of the proof, we can use the proof of Theorem 9 of [5] , which we retranscribe here. Assume towards contradiction that there exists a learner that is (ε, δ)-correct whose sample complexity is smaller than 1/p with probability larger than 7/8 on all the instances (M j ) j . By writing E 1 the event that the first 1/p steps from s 1 all transit to s 1 ; E 2 the event that the learner uses at most 1/p samples; and E = E 1 ∩ E 2 ; we can prove that for every j, writing P j the probability distribution w.r.t. M j , we have P j (E) ≥ 1 8 . We let E ′ be the bad event in which the policy π returned by the learner is not ε-optimal. We observe that on the event E, the distribution of the output policy π conditionally to E is independent on j as on the event E, the algorithm has never visited another state than s 1 before stopping and outputting π. We denote by P (π|E) the common value of P j (π|E) for all j, which satisfies π P (π|E)dπ = 1.It follows that j π P (π|E)y j π dπ ≤ 8ε p and that there exists j such that π P j (π|E)y j π dπ = π P (π|E)y j π dπ ≤ 8ε pA S-1 . For this value of j,P j (E ′ |E) = 1 - π P j (π|E)y j π dπ ≥ 1 - 8ε pA S-1 = 1 2The overall failure probability in M j is thus P j (E ′ ) ≥ P j (E)P j (E ′ |E) ≥ 1 16 > δ, which is a contradiction. Therefore, for all (ε, δ)-PAC algorithm there exists an instance M j for which P j (τ > 1/p) ≥ 1/8, hence the expected sample complexity under this instance is larger than 1/8p.Let us finally compute the diameter and bias span of MDP M j . For states s 1 and s S , the only (deterministic) policy with finite traveling time from s 1 to s j is the policy which plays action j n-1 in state s n for any n ∈ {2, ...S}. As the bottleneck of exploration is the small probability to transition from s 1 to s 2 , the travel time is biggest from s 1 to s 2 . Therefore,D = min π:S→A E[min{t > 0, s t = s 1 }|s 0 = s S , ∀t ′ , a t ′ = π(s t ′ )] = 1 p + S -1 = S -1 + A S-1 16εAs for the bias span, by fixing b(s 2 ) = 0, the Poisson equations ( 5) yield for i ∈ {3, ...S} that b(s i ) = (i -2)g, and finally b(s 1 ) = (S -1)g ≤ S. s by the definition of πn , and finally g πn ≥ min s max a I n,♭ s,a (b n ; δ). For π a stationary deterministic optimal policy satisfying the optimal Poisson equation ( 5) (that exists according to Theorem 8.4.3 and 8.4.4 of [18] ),g = g π = P π r π = P π [r π + P π b n -b n ] ≤ P π r π + U n s,πn(s) (b n ; δ) s -b n ≤ P π max a I n,♯ s,a (b n ; δ)s and finally g ≤ max s max a I n,♯ s,a (b n ; δ) Finally, since g is the gain of an optimal policy, g ≥ g πn .Proof. (Theorem 6) By Theorem 5, we have ≤ δ , where the last inequality follows from the concentration result given in Lemma 5.P [τ < +∞, g π < g ⋆ -ε] ≤ P ∃n, g ⋆ -g πn > ε, max s max a I n,♯ s,a (b n ; δ) -min s max a I n,♭ s,a (b n ; δ) ≤ ε ≤ P ∃n, ∃s, a, p s,a b n / ∈ [L s,a (b n ; δ), U n s,In this section, we present and analyze an algorithm for the generative model setting using the simplest possible sampling rule, uniform sampling, together with the adaptive stopping rule (6) for b n = bn such that bn is the optimal bias function in the AR-MDP with transition probabilities given by (p n s,a ) s,a (normalized so that the bias in the first state is always 0). The pseudo-code of the algorithm is given in Algorithm 4. Remark 1. The quantities U n s,a and L n s,a in Definition 2 are solutions to complex optimization problems and can be expensive to compute. Several modifications are possible to prevent long run times. First, it is possible not to check for stopping at each time step while preserving correctness. Second, the stopping rule can be relaxed with the following looser confidence intervals which satisfy U n s,a (b n ; δ) ≤ U n s,a (b n ; δ) and L n s,a (b n ; δ) ≥ L n s,a (b n ; δ) using Pinsker's inequality:U n s,a (b n ; δ) = pn s,a b n + ||b n || ∞ 2x(δ, N n s,a ) N n s,a , L n s,a (b n ; δ) = pn s,a b n -||b n || ∞ 2x(δ, N n s,a ) N n s,a .Theorem 6 (as well as our sample complexity analysis to follow) still applies for these alternative choices which are easier to compute but yield looser confidence intervals and thus in theory a larger sample complexity. We analyze Algorithm 4 for unichain MDPs, for which we are able to derive a simulation lemma, akin to those existing in the discounted [14] or SSP [21] settings. It relates the gains and the bias in two AR-MDPs that are close enough.Data: Accuracy ε ∈ (0, 1), confidence level δ ∈ (0, 1) n = 0, b n = 0, I n,♯ s,a (b n , δ) = 1, I n,♯ s,a (b n , δ) = 0; while max s max a I n,♯ s,a (b n , δ) -min s max a I n,♭ s,A simulation lemma for AR-MDPs To introduce this result, we need the following definitions. Definition 3. Let D M be the set of policies generating a unichain Markov chain on a weakly communicating MDP M . For M an MDP and π ∈ D M ,Π π =    1 0 ... 0 1 ... I S-1 1    - 0 P π (s 1 , s 2 ) ... P π (s 1 , s S ) ... ... 0 P π (s S , s 2 ) ... P π (s S , s S )is the matrix such that the Poisson equations (3) and (4) rewrite as Π π h π = r π with r the average reward vector and h π = (g π , b π (s 2 ) -b π (s 1 ), ...b π (s S ) -b π (s 1 )). We further defineδ 1 = min π,gπ̸ =g ⋆ |g π -g ⋆ |, ∆ 1 = max π∈D M ||Π -1 π || and ∆ 2 = max π∈D M ||h π || ∞where the norm used is the operator norm associated to the infinity norm, ||A|| = sup ||x||∞=1 ||Ax|| ∞ .We can show with results from [18] that Π π is invertible for any unichain policy π, hence ∆ 1 is well-defined. Indeed, by Theorem A.7 and (A.4), there exist solutions to the Poisson equations. By Theorem 8.2.6, the solution is unique up to an additive vector in the kernel of (I -P ), which is of dimension 1 for unichain MDPs as proved in Theorem A.5. Therefore, since in the unichain setting solutions to Π π H π = r π are exactly solutions for (4), we can conclude.The following two lemmas can be extracted from the proofs of Lemmas 7 and 8 of [4] . For completeness, we provide a full proof in Appendix D.3. Lemma 3 (Simulation lemma). Let p ′ : S × A → Σ S be the transition probability matrix of a weakly communicating MDP M ′ with the same reward function r as M . For a given policy π that is unichain on M , if for all (s, a)we have ||p ′ s,a -p s,a || 1 ≤ x ∆1(∆2+x) then ||h π -h M ′ π || ∞ ≤x. Lemma 4. Suppose M unichain. Let p ′ : S × A → Σ S be the transition probability matrix of a unichain MDP M ′ with the same reward function r as M . If for all s, a we have||p ′ s,a -p s,a || 1 ≤ x ∆1(∆2+x) where x ≤ δ 1 /2, then ||b ⋆ -b ⋆,M ′ || ∞ ≤ x.It is necessary to suppose M unichain, because without this assumption, there is no guarantee that there exists a policy π that is optimal in M ′ and unichain in M .Sample complexity bound Using these results together with our previous concentration result for the transitions (Lemma 5) permits to prove the following high-probability bound on the sample complexity of Algorithm 4, which features the quantityΓ M := ∆ 1 (∆ 2 + δ 1 /2).Theorem 9. For ε ≤ δ 1 , with probability larger than 1 -δ, the sample complexity of Algorithm 4 on a unichain MDP satisfiesτ = O SA((H + 1) ∨ Γ M ) 2 ε 2 log 1 δ + S .Just like DFE, Algorithm 4 is an (ε, δ)-PAC algorithm using a generative model that does not require any prior knowledge on the MDP, as its stopping rule is fully data-dependent. Their sample complexity in the regime of small ε and small δ both scale in (SAc(M)/ε 2 ) log(1/δ) but for different complexity quantities: c 1 (M) = D for Algorithm 1 while c 2 (M) = ((H + 1) ∨ Γ M ) 2 for Algorithm 4. We know from the lower bound that the latter has to be larger for some MDPs, but so far we did not manage to quantify their difference (even if we suspect that c 2 can be much larger than c 1 ). Besides this, we hope that the sample complexity of Algorithm 4 can be significantly reduced by the use of smarter (online) sampling rules.Proof. (Lemma 3) First, let us fix any policy π and y < 1||Π -1 π || such that max s,a ||p s,a -p ′ s,a || 1 ≤ y. We thus have Π π h π = Π ′ π h M ′ π . Π π -Π ′ π = P ′ π -P π , and therefore ||Π π -Π ′ π || < y. h π (Π π -Π ′ π ) = Π ′ π (h M ′ π -h π ) ||Π ′-1 π || • ||h π || • y > ||h M ′ π -h π || ∞ Moreover, ||Π ′-1 π || ≤ ||Π -1 π || • ||Π π Π ′-1 π || -||Π -1 π || + ||Π -1 π || ||Π ′-1 π || ≤ ||Π -1 π || • ||Π π Π ′-1 π -I|| + ||Π -1 π || ||Π ′-1 π || ≤ ||Π -1 π || • ||Π ′-1 π || • y + ||Π -1 π || ||Π ′-1 π || ≤ ||Π -1 π || 1 -||Π -1 π || • y since ||Π -1 π || • y < 1. And therefore, ||h π -h M ′ π || < ||Π -1 π || • ||h π || • y 1 -||Π -1 π || • y ≤ ∆ 1 ∆ 2 y1 -∆ 1 y Therefore, for any x, taking y = x ∆1∆2+x∆1 gives the result.Proof. (Lemma 4) Fix x < δ 1 /2, and let π be an optimal policy in M ′ . For any policy π ′ , using Lemma 3 successively with policy π and policy π ′ yields g π > g ′ π -x ≥ g ′ π ′ -x > g π ′ -2x and finally g π > g π ′ -δ 1 , which implies by definition of δ 1 that g π ≥ g π ′ , and therefore π is optimal in M . Hence applying Lemma 3 to π yields the result.Fix a unichain MDP. We prove in Theorem 10 below an explicit upper bound on the sample complexity of Algorithm 4. For ε ≤ δ 1 , we deduce from it that Proof of Theorem 10 We write N t = t SA to denote the number of visits in each state action pair at time step t. We denote by b the optimal bias function (normalized to be equal to zero in the first state). We set ξ ∈ (0, 1 6 ) to be determined later and define the three eventsτ = O SA((H + 1) ∨ Γ M ) 2 ε 2 log 1 δ + S ,E =    ∀t, ∀s, a, ||p t s,a -p s,a || 1 ≤ 2x(δ, N t ) N t    E 1 (ξ, t) = || bt -b|| ∞ < ξε E 2 (ξ, t) =    ∀s, a, || bt || ∞ 2 x(δ, N t ) N t < min 1 4 - 3 2 ξ ε, || bt || ∞    Using Lemma 5, we know that P(E) ≥ 1 -δ.We first prove that, if E ∩ E 1 (ξ, t) ∩ E 2 (ξ, t) is satisfied for a certain time step t, then the stopping condition (6) is satisfied at this time step. To this end, let us assume that E ∩ E 1 (ξ, t) ∩ E 2 (ξ, t) holds for a fixed t and ξ. We recall the definition of the confidence bounds U and L from Definition 2 and their relaxations U and L in (7) . For all (s, a), we haver s,a + U t s,a ( bt ; δ) -bt (s) ≤ r s,a + U t s,a ( bt ; δ) -bt (s) = r s,a + pt s,a bt + 2x(δ, N t s,a ) N t s,a || bt || ∞ -bt (s) ≤ r s,a + p s,a b + (p t s,a -p s,a )b + pt s,a ( bt -b) + 2x(δ, N t s,a ) N t s,a || bt || ∞ -bt (s) + b(s) -b(s) ≤ r s,a + p s,a b -b(s) + ||b -bt + bt || ∞ 2x(δ, N t s,a ) N t s,a + || bt -b|| ∞ + 2x(δ, N t s,a ) N t s,a || bt || ∞ + || bt -b|| ∞ ≤ r s,a + p s,a b -b(s) + ξε + 1 4 - 3 2 ξ ε + ξε + 1 4 - 3 2 ξ ε + ξε ≤ r s,a + p s,a b -b(s) + 1 2 εSimilarly, we can prove thatr s,a + L t s,a -bt (s) ≤ r s,a + p s,a b -b(s) - 1 2 ε.Finally, since b is a solution to the optimal Poisson equation ( 5), we know that max Then, we establish a sufficient condition on ξ and t to have E ⊆ E 1 (ξ, t).Assume that the event E holds. Let ξ ′ = min(ξε, δ 1 /2). From Lemma 4, if for all s, a we have||p t (s, a) -p(s, a)|| 1 ≤ ξ ′ Γ M , then ||b -bt || ∞ ≤ ξ ′ , which implies E 1 (ξ, t). Hence, on E, a sufficient condition for E 1 (ξ, t) to hold is 2x(δ, N t ) N t < ξ ′ Γ M . Introducing c(ξ) = 1 2 ξ ′ Γ M 2, this is equivalent to log(SA/δ) + (S -1) (1 + log(1 + N t /(S -1))) ≤ c(ξ)N t and finally toEQUATIONNext, we establish a sufficient condition on ξ and t to have E 1 (ξ, t) ⊆ E 2 (ξ, t). We first remark that when E 1 (ξ, t) holds∥ bt ∥ ∞ 2x(δ, N t ) N t ≤ ∥ bt -b∥ ∞ + ∥b∥ ∞ 2x(δ, N t ) N t ≤ (ξε + H) 2x(δ, N t ) N tTherefore, a sufficient condition for E 2 (ξ, t) to hold isEQUATIONIntroducing c ′ (ξ) = min 1 32 1-6ξ H+ξε 2 ε 2 , 1 2 , this is equivalent to log(SA/δ)/(S -1) + 1 + log(1 + N t /(S -1)) < c ′ (ξ)N t /(S -1)and finally toEQUATIONFinally, we put things together. The conditions (10) and ( 11) are of similar form. Defining C(ξ) = min(c(ξ), c ′ (ξ)), for any ξ ∈ (0, 1/6) the conditionEQUATIONis a sufficient condition on t to have E ⊆ E ∩ E 1 (ξ, t) ∩ E 2 (ξ, t). If follows that for t satisfying (12) , the algorithm has stopped before time t, with probability larger than 1 -δ.We observe that the larger C(ξ), the less stringent the condition is on t, but finding the value of ξ ∈ (0, 1/6) that maximizes C(ξ) leads to tedious calculations. Instead we go for finding a lower bound on C(1/12), denoted by C, which also provides a valid sufficient condition on t:C N t S -1 -log 1 + N t S -1 > 1 + log(SA/δ) S -1 .Using Lemma 6, letting y = 1 + log(SA/δ), this condition is satisfied forN t S -1 ≥ y C 1 + 2C y log y + 2 C .To conclude the proof, we explicit the value of C. We haveEQUATIONEQUATIONEQUATIONEQUATION= min 1 128ε 2 (H + 1) 2 , ε 2 288Γ 2 M , δ 2 1 8Γ 2 M ,where we used twice that ε ≤ 1. Hence a valid lower bound on C(1/12) isC = 1 288 min(δ 1 , ε) 2 max(H + 1, Γ M ) 2 .In this section, we restate some useful result from the literature. The first is a time uniform concentration result on the transition probabilities that can be obtained as a consequence of Lemma 9 from [1] . Lemma 5. For all δ ∈ (0, 1), with x(δ, y) = log(SA/δ) + (S -1) log (e(1 + y/(S -1))), The second result is an inversion lemma, which allows to get explicit sample complexity bounds. Lemma 6 (Lemma 15 from [13] ). Let n ≥ 1 and a, b, c, d > 0.PIf n∆ 2 ≤ a + b log(c + dn) then n ≤ 1 ∆ 2 a + b log c + d ∆ 4 (a + b( √ c + √ d)) 2NeurIPS Paper Checklist38th Conference on Neural Information Processing Systems (NeurIPS 2024).In most practical cases, the reward of the system are decided preemptively, and the uncertainty solely resides in the dynamics; moreover, estimating rewards is often easier than estimating the transition probabilities, and doing it can be done at little cost, therefore not changing our results much.In the paper, the O hides constant factors and logarithmic terms in S,A,D or H, 1/ε and log(1/δ).Some issues about this algorithm are detailed in[6], but the doubling trick still deserves consideration.The work of[16] provides an online policy gradient algorithm for ergodic MDPs but its guarantees are not expressed in the PAC setting considered in the paper (rather with simple regret). Moreover, this algorithm requires some prior knowledge on the MDP through some parameter β related to the mixing timethe Ōδ notation hides constants and logarithmic terms in S,A,D, H and 1/δ (instead of log(1/δ) in O) as the work of[20] did not try to optimize the dependency in δ, as we did in Section 4.Compared to the original statement, we fixed a small typo in the condition(9), and also propagated the changes accordingly in the definition of Algorithm 2 and its analysis. 


Decision: Based on the reviews and extensive discussions, this paper addresses an important problem in average-reward Markov Decision Processes (MDPs), particularly in identifying near-optimal policies without prior knowledge of complexity parameters. While some reviewers raised concerns about the novelty and the reliance on existing methods, others highlighted the meaningful contributions and the thoughtful investigation into the complexities of the PAC setting in average-reward MDPs. Despite the debates around the necessity of assuming a unique optimal policy and the potential for refining the exposition, the consensus leans toward the paper being a solid contribution that will likely influence future work in the area. Therefore, I recommend accepting this paper, acknowledging its technical soundness and the significance of its contributions, even if they build on established techniques.

Reviews: review: paper_summary: paper_summary: The problem of identifying near optimal policies with high probability, either in the generative, or in the online setting, is considered when the state-action space is finite, and the criteria to compare policies is how much reward they collect on the average in the long term ("PAC setting"). Algorithms are compared based on their sample complexity: the number of interactions they need before they return with a near-optimal policy. The main question is whether knowledge of the span of the optimal value function allows for a reduced sample complexity.
Some partial answers are obtained: For the generative setting, it is shown that estimating the span itself is not tractable. Next, the more moderate goal of designing an algorithm that adapts to the diameter is achieved.
For the online setting it is shown that with or without the knowledge of H, the problem is intractable. Finally, sound algorithms are designed that control sample complexity in terms of the (possibly unknown) diameter.
The paper also explains the difficulty of reducing the PAC problem to cumulative regret minimization.
strength_weakness: strength_weakness: It was known that one can estimate the diameter; hence algorithms that adapt to the diameter are not that surprising. The PAC setting is a bit artificial. Results for the PAC setting are more interesting if they mimic the results of the other settings (fixed, known or unknown budget, simple regret, or cumulative regret); and the results in this paper just underline how unnatural the PAC setting is (the algorithm needs to know how well it does; this is nice to have, but less essential than doing well.)

Since there is no box to present my summary opinion, I note it here that the above does not mean that there is no reason to study the PAC setting (ie I consider the above a really minor point). In fact, I find the question of whether there is a real difference between the PAC and the other settings an interesting and important question. Overall, I think the paper makes important and interesting contributions.
questions: questions: n.a.
limitations: limitations: n.a.
paper_summary: paper_summary: This paper addresses average-reward Markov Decision Processes (MDPs). In the context of the generative model, existing literature presents an $\epsilon$-optimal policy with a sample complexity of $O(SAD/\epsilon^2)$. However, this approach requires prior knowledge of an upper bound on the optimal bias span $H$. This paper initially demonstrates that accurately estimating $H$ can have arbitrarily large complexity. Subsequently, it introduces the Diameter Free Exploration (DFE) algorithm for communicating MDPs, which operates without any prior knowledge about the MDP and achieves near-optimal sample complexity for small $\epsilon$. In the online setting, the authors establish a lower bound suggesting that achieving a sample complexity polynomial in $H$ is infeasible. Furthermore, they propose an online algorithm that attains a sample complexity of $O(SAD^2/\epsilon^2)$. They also propose a data-dependent stopping rule that they believe could reduce sample complexity in the online setting.
strength_weakness: strength_weakness: The main concern with this paper is the limited novelty and contribution of the proposed solutions. 

The paper's claim regarding the necessity of knowing $H$ in the algorithm from [27] is somewhat misleading. The referenced paper explicitly mentions that only an upper bound for $H$ is required, not precise knowledge of $H$.

The technique of using an upper bound of $D$ to estimate $H$, as presented in this work, is not original. Reference [25] previously introduced this idea, diminishing the perceived innovation of the current paper’s methodology. Additionally, Algorithm 2, designed to estimate $D$, closely resembles Algorithm 4 in [21], suggesting a lack of substantial differentiation in their algorithm design.

The main algorithm, Diameter Free Exploration (DFE), seems to be a straightforward combination of algorithms in [21] and [27]. The primary theoretical contribution, Theorem 2, appears to be direct. The theorem’s proof does not seem to require substantial intellectual effort, suggesting that similar results could be easily derived by others familiar with the cited works.

In the online setting, the situation is similar. The online-DFE primarily integrates existing algorithms with minimal modification, and the theoretical insights it offers do not extend far beyond established results. This recombination of known techniques without substantial new insights significantly diminishes the paper's novelty and impact.

Theorem 3 in this paper is also very similar to Theorem 9 in [5].

While the authors propose a data-dependent stopping rule that they believe could reduce sample complexity in the online setting, they defer its exploration to future work. While postponing this analysis is understandable, it cannot be recognized as a substantial contribution within the current paper.
questions: questions: Regarding the development of DFE and online-DFE, and Theorems 2 and 4: Is it accurate to say that anyone familiar with [20], [21], and [27] could readily replicate these results? Specifically, were there unique challenges or complexities that are not immediately apparent but critical to the contributions of this paper?

Could the authors clarify which algorithms and theorems they consider to be the main technical contributions of this paper?
limitations: limitations: The authors adequately addressed the limitations in the conclusion.
paper_summary: paper_summary: This paper studies the problem of learning a good policy in averaged-reward MDP with finite diameter. Given previous work on the problem assuming knowledge on the optimal bias span $H$, the authors try to remove the prior knowledge and propose diameter-dependent sample complexity without any prior knowledge. In the meantime, the authors present several observations about the hardness to reach better sample complexity bounds.
strength_weakness: strength_weakness: The major concern is due to limited contribution. Two possible directions to improve this work: (1) Is $H$-dependent sample complexity reachable without prior-knowledge (even allowing worse dependence on $1/\epsilon$)? It might be hard to estimate $H$ precisely according to your observations, but that does not means a lower bound. (2) It seems the exact $D$ factor in the online case could be removed by some efficient reward-free exploration algorithms. One could assume an approximate transition model to help conduct reward-free exploration, where the target is to solve the following problem $\min_{\pi_b}\max_{\pi}\sum_{s,a}\frac{d_{\pi,T}(s,a)}{d_{\pi_b,T}(s,a)}$  ($d_{\pi,T}(s,a)$ is the occupancy distribution following $\pi$ in $T$ steps). I think the following papers might help solve the problem efficiently.

Minimax-optimal reward-agnostic exploration in reinforcement learning, Li et.al., 2024;

Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies, Zhang et. al., 2022
questions: questions: Please find my questions in the comments above.
limitations: limitations: Yes.
paper_summary: paper_summary: The goal of the paper is to learn near-optimal policies in average reward MDPs without prior knowledge of complexity parameters, contrasting extensive prior work which requires knowledge of the values complexity parameters. They rule out the possibility of easily removing this knowledge requirement through estimation of the optimal bias span, but they show that the diameter can be estimated, and use it to give an algorithm in the generative model setting. In the online setting, they again show a negative result for achieving a span-based complexity, but build on the ideas from the generative setting to give a diameter-based complexity bound. They also propose a stopping rule and give some preliminary analysis of its performance.
strength_weakness: strength_weakness: Algorithm 1 is not very novel, since it combines two ingredients from prior work: an optimal algorithm when knowledge of the optimal bias span is known, and a diameter estimation algorithm.

The value of including section 6.2 (the value iteration-inspired stopping rule) is not clear to me, since the algorithm is only given a proof-of-concept analysis for the generative model setting (not the motivating online setting), and furthermore it involves seemingly foreign complexity parameters and does not improve upon the other introduced methods.
questions: questions: Line 110: In weakly communicating MDPs there is guaranteed to be a policy with optimal average reward which is unichain, however this policy might not be any of the higher-order notions of optimality (ex. bias optimal or Blackwell optimal). Also/therefore note that multiple policies with optimal gain may not have the same bias. Thus I think a more careful definition of the optimal bias span is needed here. Also I don't understand why the optimal policy is assumed to be unique; this is clearly not true in many situations (especially in average reward settings, there may be multiple ways to reach the same optimal recurrent class) and would greatly limit the applicability of the results. It doesn't seem like this assumption is needed for anything except potentially convenience in definitions, so I think it should be removed.

This is very nitpicky, but I find it a bit weird that some bounds in Table 1 do not have a listed dependence on $\log(1/\delta)$ (ex.  [27], which apparently does actually depend on $\log(1/\delta)$). Anyways, why include the dependence on $\log(1/\delta)$ for the other results if the $\tilde{O}$ notation is meant to hide log factors?

Theorem 1 (impossibility of estimating $H$) uses unknown rewards, but the previously described setting assumes known mean rewards. Is it possible to get this result to work with known rewards? (One can try replacing the unknown reward state with a sub-MDP with unknown dynamics, but the part which is unclear to me is how adding this sub-MDP would affect the bias span)

The formatting for the display for Algorithm 1 should be fixed
limitations: limitations: There are no significant limitations which require addressing

Comments: title: Rebuttal read
comment: Sorry for the confusion. We use the standard definition for the bias span H, that was shown in the Tewari and Bartlett paper of 2009, REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs,  to be smaller than the diameter. We indeed do not require the unique optimal policy assumption, and can remove this assumption. In our paper, we focus solely on gain-optimal policies, not bias-optimal policies. Thank you for your constructive comments.
One result in the paper concerns estimating $H$. If the definition of $H$ is changed to a nonstandard one, then I think this result has less meaning or more unclear meaning. Also note that it is possible to construct example MDPs where some gain optimal policy has bias span which is larger than $D$ (say there is an absorbing state with reward 1, then a gain optimal policy only needs to get there eventually but can be very suboptimal and take a very long time to get there). Thus if the new definition of $H$ is used, we do not have the relationship $H \leq D$. This is further evidence that the proposed definition is not satisfactory.
It is not clear to me why redefining H is unsatisfactory. From the lower bounds perspective, defining H as the maximum of bias spans of all gain optimal policies just makes the lower bound stronger. The paper makes no claims of using H in upper bounds, so I am truly puzzled why this redefinition is unsatisfactory.
The review of reviewer NtfV has the following structure: Acknowledging that the paper makes interesting, meaningful and original contributions in a well written paper. Next, the reviewer complains about that the paper builds heavily on existing work, and the results are achieved with, what they think, is essentially too little effort, resulting in a verdict to reject the paper (rating of 4). As a fellow reviewer, I find this unreasonable. I think we should cherish meaningful, interesting, original findings, even if the results are using tools and techniques that are well established. There is much to like about a paper besides whether it introduces entirely new ideas. And I think the lower bounds in this paper do have some interesting new twists to them, which is overlooked by the reviewer. I hope that reviewer NtfV will change their harsh rating in light of this: Our field does not need to be adversarial. We all build on previous results in smaller or bigger ways.
Thanks for the response. I am not sure if the proposed solution for redefining $H$ is satisfactory, because the paper concerns the estimation of $H$ and this redefinition seems like it may affect the difficulty of this task. Again, I think assuming a unique optimal policy is a very bad assumption, as this is basically assuming that gain optimal $\implies$ bias optimal. Overall, I will maintain my score.
Thanks for the response. Current I  would like to keep the score. I will adjust the score after discussion with AC and other reviewers.
I confirm I read the rebuttal and the other reviews. I still maintain this is a fine paper investigating a delicate issue in a thoughtful manner.