Finding good policies in average-reward Markov Decision Processes without prior knowledge
Authors: Adrienne Tuynman
Rémy Degenne
Emilie Kaufmann
Venue: NeurIPS 2024 poster (2024)
Keywords: sample complexity
Markov decision process
best policy identification
average reward
Primary area: reinforcement_learning

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.

Finding good policies in average-reward Markov Decision Processes without prior knowledge
Adrienne Tuynman
Rémy Degenne remy, reny.degenne@inria.
adrienne. in
Emilie Kaufmann emilie. kaufmann@unii viliee.
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRISIAL, F-59000 Lille, France
Abstract
We revisit the identification of e-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 < D. Prior work have studied the complexity of e-optimal policy identification only when a generative model is available. this case, is known that there exists an MDP with D = H for which the sample complexity to output an e-optimal policy (2(SAD/² where S and are the sizes of the state and action spaces. Recently, an algorithm with sample complexity of order S SAH/e² has been proposed, but requires the knowledge of H. We first show that the sample complexity required to estimate / 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 diameter estimation procedure, algorithm for (s, -PA policy identification that does not need any form prior knowledge on the MDP. Its sample complexity scales in SAD/E /=² in the regime small E, which is near-optimal. In the online setting, our first contribution is lower bound which implies that sample complexity polynomial in H cannot be achieved this setting. Then, we propose an online algorithm with a sample complexity in S SAD* stopping rule that we believe is promising to further reduce this bound.
propose the first
/e?, 2, as well as a novel approach based on data-dependent
Introduction
Reinforcement learning (RL) is paradigm in which an agent interacts with its environment, modeled Markov Decision Process (MDP), by taking actions and observing rewards. Its goal is to learn, to act according to, a good policy, that is mapping from state to actions which maximizes cumulative rewards. However, there 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 7 times as important as the previous one, with 0 < 7 < 1. In this paper, we focus on the average reward setting, in which the value of a policy 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 small changes in the MDP, which is less observable in the finite horizon or discounted settings.
Formally, Markov Decision Processes is defined tuple (S.A,P.r) where S is the state space of finite size S, is the action space of finite size A. Letting Σx denote the set of distribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

over a set X, P. S A - Es is the (assumed unknown) transition kernel, and r S x A + 1). is the reward kernel. For each state-action pair (s, (s,a), we denote by Vssa = E[r(s, a)] the (assumed known) mean reward'. At each time step t, the agent observes a state St E S, takes an action de. and observes reward Tr r(st,a)) 0z) and next state 8t+1 ~ P(st, at). In an average-reward MDP (AR-MDP) the value of a policy т : S + ((A) is measured with its gain (s)s) = +om FE, - ry|50 = where the expectation is taken when the agent follows policy π (i.e., 8t ~ T (az)) from the initial state s. In this paper, we consider weakly communicating MDPs (defined in Section 2) in which a policy r, maximizing the gain in all states exists and has a constant value, denoted by 9x.-
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 T output a policy मे that is near-optimal. More precisely, given two parameters 8 E (0, 1) and 5 E (0, 1) we seek an (e, 6.-Poobbyy Approximately Correct (PAC) algorithm, that is an algorithm that satisfies
P ((T < 00, 3s E gn. ga (s) E) 8
Our objective is to find such an algorithm that has minimal sample complexity, i.e., that requires the least amount of steps r. 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, to sample at each time step, as the state & is determined by the MDP's dynamics and the previous actions. With generative model however the agent can sample the reward and next state of any state action pair (st; dt). regardless of which state it arrived in at the previous time step.
To the best of our knowledge, prior work on (e, PPC 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.. 19, 2, 3D. Existing sample complexity or regret bounds feature different notions of complexity of the MDP, besides its size S, 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 (s, 8)- policy identification, the work of [22] provides a worse-case lower bound showing that there exists an MDP on which any (c. 8)C algorithm using a generative model should have a sample complexity larger than Q(SSAD/" log(1/5)). The recent work of [27] provides an (e, P)AC algorithm that takes H as input and whose sample complexity is δ ((SAH/e² (egg))))))))/)0))) (1))). Using that H < D, this algorithm is thus optimal, and the lower bound is also in (((S log(1 (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 (E. 8)AC algorithms require some form of prior knowledge on the MDP, and we propose the first algorithms that are agnostic to the MDP.
Contributions In the generative model setting, first hope 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 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 near-optimal Ô ((SAD/=*) log(1/5)) sample complexity in the asymptotic regime of small e. Then in Section we discuss the hardness of (c, 8PA P-CCoolicy identification in the online setting. We notably prove lower bound showing that the sample complexity of (a. 8) -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 SAD2 /e2. As prior work, DFE hinges on a conversion between the discounted and rewaad settings [22] and uses uniform sampling. Departing from this approach, we further propose novel data-dependent stopping rule tailored for AR-MDPs that
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 casier than estimating the transition probabilities, and doing can be done little cost, therefore not changing our results much. In the paper, the Ö hides constant factors and logarithmic terms in S.A.D H. 1/s and log (l)))
2

---

can be used both in the generative model and the online setting. We prove that it is (c. 6)- for any (possibly adaptive) sampling rule and give preliminary sample complexity guarantees.
Related work
In order to position work in the literature best policy identification in average-rewar 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' C S such that for any 8, s' in S', min E[min 8t = 8') 5') = Vit dy = [5 < +00) and possibly empty set of states which are transient (meaning the return time min((, 8 = }) when the chain starts with sy = 8 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 min Ef > 0, St = s'H|so s, Vt' or [(ss)]] apee SSA
Finally, if the MDP satisfies for any policy ı and states s, s' that E[min s, s' s'Hss s, Vt', dr [sy)]] < toc, 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 also used in the literature 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 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.
given in Appendix B). The
For a policy : S + A, we define the gain (s) = limy +o + EE' Et=0 ri s0 s] By writing P= (P(s, (s))), and introducing Pr limy +-m 1 Σズ= p the asymptotic distribution matrix, as well as defining (s) = E[r(s, x (s))), we have 9r (8) = (s)r), Finally, we can define the bias vector d = Eta (Pa-1 Px) Fu. Those vectors satisfy the so-called Poisson equations (see [18]):
{ (T - Pz)9= = 0 9T + (T P )b, =
We notice that the solution, by, is defined up to an additive element in Ker(L- Ps). We can then define g" the optimal gain and (up to an additive constant) b* the optimal bias satisfying
g" b* (s) = max (F(s, a) + b=
(5)
where Ps.a is the (row) vector of transition probabilities from (s, We further define
H = max b* (8) min 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 Il all require this knowledge, discussed in more detail below.
In addition to the diameter D and the optimal bias span H, we define the mixing time
mix = maxiinn inf { 2 1 max (t (
1
(a())),, s S
3

---

find tight upper bound on Table 1: Existing sample complexity bounds in the generative model setting
Algorithm
Bound
Setting
[23]
(A( 1
log(1/6))
(+(
V $
known
VFS
mix over all policies, known
[11]
Ö
SA(t )a
log(1/8)
mix known
[12]
1og(1/5)
1 D known
5²
SA(tjul" log(1/8))
[16]
mix known (policy gradient)
[24]
SAt
log( (
m m known
g²
[22]
SAH Ed
log(1/0)
H known
[26]
SAH² 2a
+ s AH
log(1/8)
H known
[27]
Ô (SAH)
H known
This paper
δ ([SAD
ea + S AD"] log(1/6))
no prior knowledge
[12]
Ω 9
Lower bound (worse case)
[22]
( SAD log (og(1/)))
Lower bound (worse case)
which has also appeared in previous sample complexity bounds. By default the maximum taken over all stochastic policies æ S + E, and we denote by / the same quantity where the maximum restricted to deterministic policies.
Multiple papers have considered the problem of finding an e-optimal policy in average-reward with access 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 certain number of samples must be collected to guarantee correctness of any (e. 8)- 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 sower-bound for the sample complexity was matched by [24], for an algorithm taking f* mix.D p 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 I it is possible to choose a discount y (with 1 - y of order E/ Hf) such that Hoptimall policies the discounted MDP are e-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, natural question is therefore: H from the data?
3 On the hardness of estimating H
In 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 Il such that with probability higher than 1 5, H < H < A.
Theorem shows that there exists MDP on which the sample complexity of an algorithm finding A-tight upper bound with probability larger than can be arbitrarily large. As a consequence, there cannot exist bound on this sample complexity depending solely on S, A, H, d and A.

---

Theorem 1. For any d << 1 >> 0, A, there exists ergodic MDP M with optimal bias span H = 1/2, S and A = such that any algorithm that computes a -ight upper bound for the optimal bias span with probability - E under generative model assumption needs (in expectation) more than T samples in M.
Sketch of proof To give idea of the proof, first focus the weakly- weakly-communicet communicating setting, with the full proof and the necessary ergodicity transformation detailed in Appendix A. We use the family of MDPs (MR)o<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, state is drastically worse than another, hence small optimal bias span, H 1/2. However, R > 1/2 makes the dashed-line policy optimal; moving from state 3 to state is more difficult as small, taking on average 1 1/p time steps, and state 3 has worse reward than state 2; thus state 3 is considered way worse than state hence high optimal bias span, H 1 R. Thus, bound H very close to 1/2.
P
tightly, one needs to know whether > 1/2 or < 1/2, which can require many samples if R is
1
3
0.P
R,
0,
Figure 1: MDP MR. the hard instance for Theorem 1. Each arrow corresponds to action and next state combination, and is annotated with the mean reward of the action and the probability of the transition. Arrows with a different line style correspond to different actions.
We remark that since the hard MDP instance in our proof has fixed optimal bias span 1/2, we would have the same problem if we looked for algorithms trying to find A such that, with high probability, H < f < (1 + A)H. Moreover, instead of looking for upper bound we could also consider the task of estimating H within given margin of error and the same issue would arise.
While Theorem does not preclude the existence of an algorithm that is agnostic to H and reaches a ((SSHH/))) log(1/5)) sample complexity, it still suggests that assuming a known upper bound on H is lot ask. In the section will see that for communicating MDPs such an assumption is not needed to attain a near-optimal sample complexity.
4 A near-optimal algorithm without prior knowledge
As we have seen, finding tight upper bounds on 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', [2] propose to use a doubling trick to counter not knowing H. at the expense of an additional factor of V/S in the regret. 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 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.
The doubling trick method
We propose Diameter Free Exploration (DFE), stated Algorithm 1, which combines diameter estimation sub-routine that follows from the work [21, 20] with the state-of-the-s algorithm of
Some issues about this algorithm detailed in [6]. but the doubling trick still deserves consideration.
5

---

Data: Accuracy (0, 1), confidence level 8 (0
Let D be the output of Algorithm 2 with accuracy 1 and confidence level 8/2. Let be the output of Algorithm with accuracy E, upper bound H = D and confidence level 6/2
return A
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 quantity D which satisfies D S D <
4D with probability larger than 1 6/2, using random number of samples N from each state action pair (s.a) that satisfies N = Ó (log(1/6) + S)). Then Algorithm 3 (which also uses uniform sampling) takes as input D and is guaranteed to output policy that e-optimal with probability larger than 1-65 6/2, using a total number of samples of order This gives the following theorem.
O SAD log ()
Theorem 2. Algorithm is (E, 6)PAC and its sample complexity satisfies, with probability 8,
T T= δ SAD 82
(1
D2SA
log { D222
From Theorem 4 of [22], there exists communicating MDP with sample complexity in Ω SAA In (1/8)) Therefore, the DFE algorithm is worse than the lower bound by a multiplicative factor (1 + D=² + DS* 178 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 the best of our knowledge there exists no online algorithm that is guaranteed to output policy î satisfying g 2 g" E with probability larger than 1-8 8 this section, we give some elements of explanation.
On the hardness of a regret to PAC conversion In the finite-horizon setting, [10] gave 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 algorithm should yield 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 policy converges towards the gain of this policy, but the speed of this convergence is determined by the mixing time. Moreover, as shown [22], this mixing time can be arbitrarily large. However, the regret is not defined asymptotically. In [9], the regret time T
defined as Tg* E re]. In [17], the regret Ex- 1ET re] E re]- As the mixing time can be big, it is possible that these regret measures are small for large number of steps, but that the underlying policy is not anywhere near asymptotically optimal.
is therefore not possible to preemptively define the number of steps necessary for the regret- minimizing algorithm find an asymptotically good policy, and not just one that good on the short term. For example, for any N E IN, N > 2, consider the MDP Mp displayed in Figure with n and any p' < -_ While the dashed-line policy is asymptotically best, the full-lined policy is better for at least N time steps, and not even E-optimal, as we show in Appendix C. An algorithm guaranteeing low regret (over slightly modified version of the MDP guarantee ergodicity) could therefore take the full-line action for a number steps independent of the known parameters S and A, and the knowledge of N would be required to know how many samples
"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 prior knowledge the MDP through some parameter 3 related to the mixing time

---

1,1-p
1. 1.p'
1,p
4,1-p'<I3
0.
-p
0.P
0,p'
0, 0-1-p
Figure 2: MDP Ma.y with high mixing time.
js
35 2
(1,1 1,1-p) C 81
$2
8g
1,
Figure 3: MDP Mj, the hard instance for Theorem 3
necessary for best policy identification. This means that 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 straightforward wrapper as the episodic setting. Similar arguments in the SSP setting have been brought for example in [21].
hardness result As the following lower bound shows, it is in fact not possible at all have an online best policy identification algorithm that has a sample complexity bound polynomial in S, A and Н. This result is counterpart of the hardness result proved by [5] in SSP-MDPs.
Theorem 3. For any 52 4,4,224, there exists weakly communicating MDP with S states, A actions, mean rewards in [0, 11. H S
(0, 1), 8 E (0, 1 and any (e, 8)CPAC online algorithm,
and 2 15-1 A such that if the algorithm starts in a given state 81, [[]]] = 9
Sketch of proof For jerje E (S 1) we define the hard instance M, as in Figure An agent in 82 must execute the precise sequence of actions j to get back 81, which the only state that generates non zero rewards. Since not learning this precise sequence would mean the agent will perform badly one of the My. and therefore perform very suboptimal policy, the agent will need have big enough sample size to at least see with high probability when starting in 81. With a small value of p. possible 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-efficiee learning impossible in the online setting of SSP. Indeed, their hard MDP is one where the cost always the same in each state, in which case we can easily transform the SSP problem into average reward one, shown in Figure 5. Indeed, if the costs of the SSP-MDP all equal and non-zero, then finding an optimal policy in 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. Li
We remark that while the hard MDP instances M, used in our proof have an optimal bias span H that is upper bounded by S. its diameter exponential is Hence while Theorem implies that no online algorithm can get O 2² sample complexity (with or without the knowledge of H) on every instance and for every e, does not rule out the possibility have an online algorithm with sample complexity scaling with D. We propose such an algorithm in the next section.
7

---

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 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 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 8 using a slightly worse sample complexity in (DD The second ingredient, Algorithm 3, starts by collecting fixed number of samples ń proportional to (D/E²) log (1E))A(6E)) 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 (SADm + D3/255 A)
samples, with high probability. We call the resulting algorithm Online-DFE.
Theorem 4. Online-DFE is (s, 6)-PAC and its sample complexity satisfies, with probability larger than 1 - 5 = O5
SADD 2² + ADD)
Compared to Theorem 2 for the generative model setting, we note a multiplicative D factor in the sample complexity, as well as less explicit dependency in 6. Still, it provides online PAC algorithm whose sample complexity scales in /AD2/E2 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, promising direction is to investigate more adaptive algorithms, directly tailored for the average-reward setting. This is what we do next.
6.2 Towards more adaptive algorithms
We recall that an identification algorithm uses three components: a sampling rule, selecting at time t state-action pair (st, az). after which the next state S1+1 ~ P(s,, at) and the reward r; r(st, dz) is observed; a stopping rule 7 which decides whether the data collection can be stopped, and a recommendation स which is guess for near-optimal policy that depends on the first observations. In the online setting, the sampling rule is actually reduced to the choice a given st, as we have the constraint that 8 P(s,, a.). In this section we introduce 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 No - 1 ((st, az) (s, a)) the number of visits to the state action pair (8, a) in the first n steps and f". the empirical estimate of the transition probability vector Ps.a built at step n, where p"., can be arbitrarily chosen to be the constant vector equal to 3 if N =.
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, E R$ and on the ability to build confidence intervals the quantity (n) = F..a + b,. by, (s). This leads to build an upper bound of the span of I. (n). which can be seen as the average-reward equivalent of the Bellman error as defined in [8]. We know that, if bn. = bb, then (max, Is.a (n)), is equal to the constant vector g Conversely, by Theorem 8.5.5 of [18], if the span of (max, T (n)), is small, then the associated policy x (s) = arg max, Ta (n) is approaching the optimal one; this can be used to derive criterion for correctness of value iteration in average-reward MDPs. Therefore, by examining an upper-bound on the span of 1, we get the following theorem.
Theorem S. In a weakly communicating MDP, for a given vector bn E RR, for all pairs (s, a) we have bn (Lg (bni 8), U. (b, 8)). then defining tn arg max, 1n.2 (bn; 8), we have
min max Imb (b, 8) S gh. S g" S max max 1n- (b, 8)
where Ind (bni 8) ;- Ta.a + LE (bn: 8) bn (s) and I (bns 8) Fa,a + U (bn, 8) bn (s).
$ "the Os notation hides constants and logarithumic terms in S.A.D, H and 1/8 (instead of log in ②) as the work of [20] did not try to optimize the dependency in 6, we did in Section 4.
8

---

Now to propose a concrete stopping rule, we provide expressions of U and L chosen such that the premise of Theorem is satisfied every round n, with high probability. KL(p, q) denotes the Kullback-I Libler divergence between the probability vectors p and q on S.
Definition 2. Given a sequence of (ba)n. we define
No. KL 8,0 (ba:))))) = max p'b
5,a p') S x(6, N
L (bn: 8) = min p'bn
No KL p¹) S z(6, s.a
for the threshold function x(6, v) = log(S (S - 1) log (e(1 + 0 1))) and
Te.8 min max max (bn. 8) min max 1. (b,: 6) S [e
(6)
The following result is consequence of Theorem 5 and KL-based time uniform concentration result for the transition probabilities from [1] (Lemma 5 in Appendix). Using Pinsker's 's inequality (see Remark in Appendix where we discuss some computational aspects), also justify that this theorem hold for U L replaced by
2r(6, N
2x 22,6,,0 No.
Ü. (ba: Pr bn +16blllo0
(baa(bnid)) Ph 111b vo
(7)
N
No
Theorem 6. For any sampling rule ((sn; an))n, and any sequence (n of bias vectors, the algorithm using the stopping rule Te.6 defined in (6) and recommending (ss) arg maxa 1g,2(bri (br;8)
satisfies P (r < ox,9" 03 6) 8.
Theorem shows that for any sampling rule, be in the generative model or in the online setting, the stopping rule (6) and associated recommendation rule yields an (c, 8 algorithm, for any choice of bias vector sequence 6n Of course, bad choices sampling rules and bias vectors could still yield almost surely (e.g. picking always (st, az) = (51, a1) when 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 generative model, with the VI stopping rule (6) where the sequence of biais vector is b, b, where b,, is the optimal bias vector in the AR-MDP with rewards Ts.a and transition probabilities given by (f%.a)s,a (see Algorithm 4). We prove in Theorem that in unichain MDPs, for sufficiently small the sample complexity of this by (A((HTT))* (log } + 5) where 5²
algorithm is bounded with probability larger than
I'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 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?/E² 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 GOSPRI. approach. Our stopping rule actually suggests some clever online choices that could used to make the algorithm stop earlier. For example could be interesting to make greedy choice of the bias vector b, that minimizes over b E RS the quantity max, max, I (b; 5) min, max, M (b; 8). Assuming we could compute this vector, a possible online sampling rule could be optimistic choice on = argmax, FFe.a + U S (bn, 8)]. We leave the analysis of such algorithms for future work.
7 Conclusion and perspective
We provided several elements indicating that the optimal bias span H may not be an adequate complexity measure for e-optimal policy identification an average-reward MDP. the generative model setting, 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 S SAH/e" sample complexity on every H. On the algorithmic side, we proposed the first best policy
MDP, with or without the knowledge identification algorithms for the generative model setting that does not require any form of prior knowledge on the MDP. By estimating the diameter instead of H, DFE attains a near-optimal sample complexity in SAD/é / for communicating MDPs. We further proposed an online variant of DFE with a slightly larger SAD* sample complexity, which is a factor D away from the worse case lower bound established in the generative model setting. We leave as open question whether there exists online algorithms with a SAD/E" sample complexity. In future work, we will investigate whether the novel adaptive stopping rule proposed in our work can lead this reduced sample complexity, when combined with a suitable online sampling rule.
Acknowledgments and Disclosure of Funding
The authors acknowledge the funding of the French National Research Agency under the project FATE (ANR22-CE23-00164)) and the PEPR IA FOUNDRY project ANRR23-PPIAA-000 The authors are members of the Inria team Scool.
References
[1] Aymen Al Marjani and Alexandre Proutiere. Adaptative sampling for best policy identification in Markov Decision Processes. In 38th international conference on Machine Learning, volume 139. PMLR, 2021.
[2] Peter L. Bartlett and Ambuj Tewari. REGAL: A regularization based algorithm for reinforcement learning in weakly communicating MDPs. In 25th conference uncertainty in artificial intelligence (UAI2009). 2009.
[3] Hippolyte Bourel, Odalric Maillard, and Mohammad Sadegh Talebi. Tightening exploration in upper confidence reinforcement learning. In Internation Conference on Machine Learning (ICML), 2020.
[4] Apostolos N. Burnetas and Michael N. Katehakis. Optimal adaptative policies for Markov Decision Processes. Mathematics of operations research, 22(1):222-255, 1997.
[5] Liyu Chen, Andrea Tirinzoni, Matteo Pirotta, and Alessandro Lazaric. Reaching goals is hard: setting the sample complexity of the stochastic shortest path. In 34th International conference on Algorithmic learning theory, volume 201, pages 310-357. PMLR, 2023.
[6] Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Near Optimal Exploration Exploration-Exxloittiiio Exploitation in Communicating Markov Decision Processes. 32nd Conference on Neural Information Processing Systems, 2018
[7] Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span- constrained ppploratiio-exploitaaaee in reinforcement learning. In Internation Conference on Machine Learning (ICML), 2018.
[8] Scott Fujimoto, Meger David, Doina Precup, Ofir Nachum, and Shixiang Shane Gu. Why should trust you, Bellman? the Bellman error is a poor replacement for value error. In 39th international conference on Machine Learning, volume 162. PMLR, 2022.
[9] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning, Journal of Machine Learning Research, 11:1563-1600, 2010.
[10] Chi Jin, Zeyuan AZu, Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? In 32nd international conference on on Neural Information Processing Systems (NeurIPS 2018), 2018
[11] Yujia Jin and Aaron Sidford. Efficiently solving MDPs with stochastic mirror descent, 37th international conference Machine Learning, volume 119, PMLR, 2020.
10

---

[12] Yujia Jin and Aaron Sidford. Towards tight bounds on the sample complexity of average-reward MDPs. In 38th international conference on Machine Learning, volume 139. PMLR, 2021.
[13] Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory (ALT), 2021.
[14] Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine Learning, 49:209-2333 2002.
[15] Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[16] Tianjiao Li, Feiyang Wu, and Guanghui Lan, Stochastic first-order methods for average-reward markov decision processes. https://arxiv.. wtw.oo/////../............ 2022.
[17] Fabien Pesquerel and Odalrie-Ambry Maillard. IMED-RO MIED-RL: Regret optimal learning of ergodic Markov Decision Processes. In 36th conference on Neural Information Processing Systems (NeurIPS 2022), 2022.
[18] Martin L. Puterman. Markov Decision Processes. John Wiley & sons, 1994.
[19] Jean Tarbouriech, Evrard Garcelon, Michal Valko, Matteo Pirotta, and Alessandro Lazaric. No-regret exploration in goal-oriented reinforcement learning. In Internation Conference on Machine Learning (ICML), 2020.
[20] Jean Tarbouriech, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. A provably efficient sample collection strategy for reinforcement learning. In 35th conference on neural information processing systems, 2021.
[21] Jean Tarbouriech, Mattco Pirotta, Michal Valko, and Alessandro Lazaric. Sample complexity bounds for stochastic shortest path with generative model. In 32nd International conference on Algorithmic learning theory, volume 132. PMLR, 2021.
[22] Jinghan Wang, Mengdi Wang, and Lin F. Yang. Near sample-optimal reduction-based policy learning for average reward MDP. htt.tpp//aaxii.orrrpppeo /bb http:/abaa2222...2 2212200022 2022.
[23] Mengdi Wang. Primal-dual learning: Sample complexity and sublinear run time for ergodic Markov Decision Problems. http:://arriiv.orggbb//// http://aaab/11..11100000 2017.
[24] Shengbo Wang. Jose Blanchet, and Peter Glymn. Optimal sample complexity for average reward markov decision processes. https://arxiv. http://axxiiv.o/aa////////////// 08833, 2023.
[25] Zihan Zhang and Xiangyang Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. In 33rd conference on neural information processing systems, 2019.
[26] Zihan Zhang and Qiaomin Xie. Sharper model-free reinforcement learning for average-reward Markov Decision Processes. ittps://arxivv wwtp://////aaaaaaeeeeeaa 16394, 2023.
[27] Matthew Zurek and Yudong Chen. Span-based optimal sample complexity for average reward MDPs, attps://arzie wwwpsiiivvrg//bbbee wtgg/bs////1......//areegg//g 13469, 2023.

---

A Proof of Theorem
We only prove here the result for weakly communicating MDPs, and provide the ergodic MDP necessary to prove the general theorem.
Fix 8, T and A. Define d = c and d' -288. Let E min
. to To
10
2/
af +1
case the notation, we denote by Ma and M respectively the MDPs M 2 -- and M in Figure 1. The rewards distribution in these MDPs assumed to be Bernoulli variables with the means indicated in the figure.
The optimal policy in MM. always chooses the actions represented by full line. Its gain is 1. its bias vector (up to additive constant) is (0, - -2). In MY., the optimal policy always chooses the dashed actions and its optimal gain is associated bias vector (up to an additive constant) is (- (2 + 8) He 0, ( + ++) : With He the
Using the Poisson equations, we can show that its
span of the optimal bias for Mr and H2 that of M', have:
p
H - He
+
(1+p)
+ +
2
p
2
E
+
+E
E
2
A
Consider now algorithm that outputs H A-tight upper bound for the optimal bias span with probability greater than 1 - å on any MDP. We denote by 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 7 the number of samples of the dashed action taken in state 2 before stopping and by K, the number times the agent gets a reward of 1 among the first & visits of state 2. We introduce the three events
ε, (Ā < HD}
{
- 1 KilK k=
E2
max isiie
{ (
Eg
where we define
/ 12 e) (5 + E) 1r In 2. with 0 = exp
-4d'22 (t-+)(++e)
and let /*
(t-o)(++e) 4d'c2
In 205 We let & n 8
Let W be the interaction history of the learner and the generative model, L(w) P(W = ww) and L'(w) P' w). For K f-
L'(W)
1g (1/2+c) L(W)
(1/2-) 1e 2 0 g
by the arguments within the proof for Lemma 13 [5]. Using a change of measure, we can write
P'()) 2 ((()) = F. (W)] = F.
L'(W) L(W)
I ((W)) P(E) = 25P(E)-
(8)
8){ [ is the sum of t Bernoulli variables of expectation (1/2 - s), and thus of variance (1/2 e)(1/2 s). Kolmogorov's inequality states that
Moreover, in Me. K₁ - (1/2- -5)
K2 (2 - - >
1" (1
P P
max IStS
E2
which entails P(E) 7/8. The detailed computation is given in the proof for Lemma 12 of [5].
12

---

Now, we assume towards contradiction that P(Es) 2 7/8. Using the above, this yields
P(E) v P(E))
+ P(82) + P(&3)
< +
1
2'
where the first incquality uses that P(E,) 2 - 5 by the correctness of the algorithm and the second inequality uses that 8 S 1. Hence, we have P(E) > 2 which leads P'(E1) using (8). This contradicts the correctness of the algorithm. Therefore, we have P(Es) < g.
It follows that with probability larger than 5/4 f 2 t on Mg. hence
E
E
which concludes the proof.
More generally, adding the transitions described in Figure 4 with 7' = -P can be used to show that computing a -ight upper bound for the optimal bias span with high probability would need in expectation more than 7 samples.
I+p
2 1 T
0,1
0,1
T/2
2/2/2
2
0.P
R,
0, 1 p
Figure 4: MR the ergodic case
B Complements for Section
In this Appendix, we provide some details on the two components of our near-optimal algorithm: procedure to provide a high-probubility upper bound on the diameter (Algorithm 2) and a near-optimal algorithm for best policy identification in an average reward MDP that requires upper bound on H as an input (Algorithm 3). Finally, we give the proof of Theorem 2.
B.1 Diameter Estimation Procedure
The procedure proposed by [20] for estimating the diameter hinges the observation that the diameter can expressed terms of optimal values in goal-oriented Markov Decision Decision (or SSP-MDP for Stochastic Shortest Path). We recall that in SSP-MDP the transition kernel is coupled with goal state 8y E S and cost function e (8,a) + c(s, a). The value of a (deterministic) policy that is to be minimized, is denoted by
1 (6)
(s) = 0,99
Σ
c(si, n (st))
81 =
13

---

where (s) inf{t: Sc+1 sg|s1 is the number of steps before reaching the goal when starting from state and following policy л. The diameter can thus be written
max maxmaamma min E ((T max max min VT, V (s')
8
max max VI.a 8'
where Vo denotes the optimal (i.e. minimal) value function the SSP-MDP with cost e and goal state By and 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 Vo.,," that now recall for completeness. Given cost function and goal state 8g. EVI-SSPe,s, c.s, takes input a set of plausible transitions P (P(s, a)),.. such that P(s, a) are included in the set of probability distribution over S (and the unknown vectors Ps.a is believed to belong to P(s, a)), and precision μvv. It introduces the extended optimal Bellman operator, defined for v E IR as
Lu(s) min c(s,a) min pe aEA
(eP().
for 8 + 8y and Lo(g) EVI-SSP c.s, sets vp - 0 E R and defines U/+1 Luy for j 2 0. stops at iteration j min {j ||0z+1 fy < μvs] and outputs ey. It also outputs an optimistic transition kernel p = (Pa.a),.a. defined for all s,
Pa.a argmin pr peP(s,a)
and the optimistic greedy policy
म ((s)
argmin [c(s, a) + pu]
aEA
We denote by c, (s) the value function of policy in the SSP with cost function c. goal state Sy and transition kernel p. Previous work (see e.g. Lemma of [21]) have established the following properties.
Lemma 1. Assume that, for all (s, a), Ps.a P(ss a). Letting (ū, EVI-SSP c.s, (P, Pv)), the following inequalities hold (component-wise):
(i) T S V and T < V
V
c,8g c,2g
(ii) if pvi S Smiu then V 0,8g
24t Cyiin
Notably, this result gives upper bound 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 in [21]. Let p and p be two transition kernels such that for all (s, a), liPs. Ps.all & Assume that Cmin > O and that under both p and there exists at least one policy that reaches 8g almost surely from any state (such policy called proper). Let a be proper policy in P such that
2ml VT al,0 S Cminn
(9)
Then is proper in p and
2nl V
1lo0
V8 E S, S (8) <
1
Vo ciog
(8)
Criin
'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 and its analysis.
14

---

Finally, the last step to be able to apply Lemma is to construct the sets ((s, a) that contains the true transition probabilities with high probability. This can be done as in the rest the paper by relying on Lemma 5, which gives confidence regions of the form
{o E Es - -s,a 1l S ((n,))
where Pa.a.n is the empirical estimate of the transition probability after the n-th transition has been observed from (s, a) and ((n, 6) 2log(S4/0)+2(5 (og(ee1111(((111))
n
The resulting algorithm for estimating the diameter is described Algorithm It 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 8 (0, 1)
Set W = 2 and Uso =
while x0 > W do
W + 2W
Set accuracy 7 = गे and compute N [6, n) = inf B(n, 8) s n)}
Call the generative model until each (s, a) gets N visits.
Let each (s, a) let P(s, a) = {p E Es |p - Pe.a,vl11 S n) and P= = (P(s, a))
for
$1,.., 55 do
Let (ōl*), p(.) T())) EVI-SSP,, 1.a (P, LAE)
end
Let USo max, max (5) end
return D= (1 xe 6
Algorithm 2: A diameter estimation procedure
Theorem Lete S With probability 1 8, Algorithm run with parameters and outputs an estimate D which satisfies
D D$ 1+ E(1+E)
(1 (1+
2
using SA x (6, ) samples where
N 1) == inf (n 0: ((n, 5) S sn}
leading to an overall sample complexity of
D2SA E2
52 A
δ
log
8
E²
where the Õ ignores logarithmic factors in S, D, 1/2 and log(1/5).
Proof. The proof closely follows that of [20]. We let W,, be the value of W in the n-th iteration of the while loop (starting at 1), such that W,, 2n-1 We define The 4W, and U, the value of T at the end of the 7-th iteration. The number of iteration used by the algorithm is ñ min Un < W.). Assume the event
E = (Vs, a, Vn 2 1, -a.
Ps,all S (nn, 6))
( holds. Using property of the EVI scheme (first statement Lemma 1), for all n, Un S Vi. D (component-wi) wiise), which yields S S D. Hence ñ is bounded by min(n: D Wn) S log, +D) We now bound the final accuracy îj == Mi. First, as Uoe == Uy < Wa. we have îj S 3_ Moreover, using that
Ti..
D Z P > W Wa
further yields
< Ι < 8
8D
40
15

---

We let 0(4) ,p(1), ((6))=(()) (+() be the output of Extended Value Iteration with goal state in the final iteration, and let V1, denote the value function in the SSP MDP with costs 1, goal state and transition kernel plo). For every s',, using the simulation lemma, have
(8)
S + 27 V 1, V (8')
1,8
provided that the condition
27 10 1
satisfied. This is the case by using the second statement of Lemma on îj established above:
together with the upper bound
5(1 +8)
27 T
1s 1100 S 277(1 + e)] & 27/(1 + 8)0 S
3
2
where the last step uses that & & 1. Hence, one can write
(8)
W W1
2 V.. - 2l V
1/ (5')
(1 2 + + b1 (8)
WV I
(1 277 + =)) =) = D
(1+ (1 (1+
(1 E)+
where (a) uses the second statement of Lemma (b) uses the definition of 8.o and (c) 2 I D and 1fU S s/4. Recalling that D = oa (s') yields that, on event 3
uses that
D D s (1 + E)E ([ +E)
Moreover, the number of samples collected per transition is N(6 S (6. s.).
The conclusion follows from the fact that & holds with probability larger than 5 (Lemma 5) and by upper bounding N (5, & using Lemma 6 in Appendix F. Specifically, choosing the parameters
8D
2 = n/a = 2og SA b 2(S - 1), and d we get
(AA 8
2(S log c (S - 1)m
SA 8
8e
(66 m) S 1
log
+
log
+
n
17a
which leads to the approximation stated Theorem 7.
B.2 Near-optimal algorithm using the knowledge of
We recall here for completeness the algorithm of [27] to find an e-optimal policy in 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 refined analysis was proposed by [27]) with the reduction from the average reward the discounted case from [22].
Data: Accuracy & E (0, 1]. upper bound H on H, confidence level å E (0, 1)
Set discount factor 7
1277
Set I44Ca log 125A with C2 the constant in Theorem of [27]
6=
Collect samples from the transition in each (s, a) Let be the estimated transition kernel based on all transitions collected
Compute the randomized reward function F(s, a) = r(s, a) + + where Xe,a i.dd 1 ([0, # Compute & the optimal policy in the discounted MDP (7. p. 7)
return a
Algorithm 3: Algorithm 2 from [27]
16

---

p' Theorem 8. With probability 1 5. Algorithm with parameters E (0, 11. H satisfying H S H
and å (0. 1) outputs policy it satisfying
(Vs S, p (s) S
1-
and collects (deterministic) total number of transitions given by
144C25
125
log
E²
where C2 is the constant in Theorem 1 of [27].
B.3 Proof of Theorem 2
We let D be the output of Algorithm run with parameters and 8/2 and the total number of samples uses. From Theorem 7, it holds that
(D'SA P ( P D 4D, (
D252 2 1-/22.
We let be the output of Algorithm 3 run with parameter E, Đ and 8/2 and T2 the total number of samples uses. Using Theorem 8, we have
14AC2SAD
24SA
P g" - 92 E,
log
D
2 21-
g2
òe
The total sample complexity being + r2, using union bound yields that with probability 1 6, it holds that g* g# and
576C2SAD
24SA
D252
log
E2
8E
( SAD
+ +D'SA log
111
D2
+
E²
T ([
SAD
+ 52 log
(
2²
Complements for Section
C.1 Study of the MDP Mp
We recall the MDP introduced in Figure We prove the following: for any N, for any p < 1/N and any p' < 1. the policy in full line æ is optimal for more than N steps, but is not s-optimal in average reward.
1,1-p P
1, p'
1,p
1,1-9'<
3
0, -
0.P
0,p'
0, 0,1-p P
Figure 2: MDP Mp (repeated from page 7)
For that, define un the probability of being in state 1 at timestep n. We note that u, does depend on the policy chosen. Since we know
uo = 1
u.)) we have
Un+1 = (1
+ pp((1 -ppp)un
p'
Un = (1 - p²)
1
+ v¹
17

---

Therefore, the (asymptotic) gain for the full-line policy x is yr
L p+p while that of the dashed-line
policy x' is 9n' 1 ptp ptv Since p' < 1
p0(1 + 8) p(1 e) p' (p + D/)e
Jx < 9x' -
and we have indeed that π is not e-optimal.
Moreover, the empirical reward up step n for policy я is = Er= uha and =n+1-E Ei=o for policy H'. As (rn/n),, is decreasing and (n/ increasing, policy n' becomes better than when Ei=o Un S n+1 that is, when
2
(n +
d' p+
+
(1
P'
Σ
11-P-p'' n+1
(1
p+v
1=
p
1
1
(1-p-10
ppp-p'mm p')n+t
1 p
-
p+p pl
n n+1
p+p
2 p p+p
which implies
(n+ 1)(p +/) - n(n + +1)2
p¹ - p p'
p+ p n n+1
p + p'
by using that (1 n < 1 (n + 1)x + n(n + 1)x² /2 for any < r 1. Finally, x' being
better than ı at timestep implies
= s 1/2 / 1 ptp i.., n N.
2
C.2 Proof of Theorem
Proof. For S, A, e, å satisfying the assumptions of Theorem 3, we let - and define the family of MDPs M, for any j AS-1, displayed in Figure There are A actions available in each of the S states, but the figure only displays actions with distinct transitions.
16c
js
J2
js
1,1-
$1
$2
$3
$5
{1,p}
Figure 3: MDP Mj (repeated from page 7)
In state 81, for any action a, a reward of is incurred, and there is probability p of getting into state and probability 1 of staying in 81.
In state sn for ( 5), taking action jn-1 transitions state Sn+1 (where $5+1 $1) and every other action transitions to state $2, with no reward.
To summarize, it is very unlikely to get into state $2; but, once it has been entered, only one specific deterministic policy can allow agent to get back to the favorable state 81.
Let be (possibly stochastic) policy. Let us write pf (si-1(s;) for i {2, (2.... and x T With Pa.j the transition matrix under æ in MDP My, and Pr.; limr + Et nj we know that Pr.j = Pr.j- Since the MDP M, is unichain, by theorem A.2 of [18], all the of .. are identical to vector (7))...))) E Es.
p!-1
18

---

We therefore deduce the following linear system:
= (1 p)m + p's
pm + >> (1 p/ Mm
n=2
Vn E {3....)) Tm p 1a-1- 1m
7n
=1
==1
Injecting the third equation into the second yields pm + S-11 (m finally 22 = p'p- Therefore,
-7a41) + 9s
x and
m 1+ p(1 + p2
+ pyps
xx
=1
It
using that 1 + pl pspp + o 2 1. Finally,
g
$ 1+ E 25
The optimal policy in M, is to play action Jn-1 in state sn for (2,..., so the above equation becomes 77, + p(S 1)) and the optimal gain in Mj is g I+r(S-1)
If a policy is e-optimal in .M.. we have
5 2 g"
-E 1
F 1
+ p(S -1) -
2
(S - 1)p 2
p - 1+ (S - 1)p +
P
+
(S - 1)p²
I
I
x
1 1-E(1 + +(S 1)p)
x 2 p SS 1)p + (1+ -S-1pp
(S- 1) 2
((S 1)++1}2 + (- 1)p(1 5-1(5-11p)
Since (S- - 1)p p < Therefore, (S - 1)x+ 2 1+73-17 Finally, 15-1 2 1. and xt 2 P. Since Σ, o =
1' (1 +1+ (S 1)p) < 2. Since we also have < 1 (1 - E(S - 11))
1'
1e
we deduce that each policy can be e-optimal for most Be MDPs in (M,b.. By denoting 2/4 = 1l (st is s-optimll in M,)- we have E, v S :
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 learner that is (e, -ccoreet whose sample complexity is smaller than 1 1/p with probability larger than 7/8 on all the instances (M₃),- By writing E, the event that the first 1/p steps from S₁ all transit to s1; Eg the event that the learner uses at most 1/p samples; and È = E1 n Eg; we can prove that for every j, writing P, the probability distribution w.r.t. Mj, we have (,( 2 8.
We let E' the bad event which the policy returned by the learner is not e-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 &, the algorithm has never visited another state than 81 before stopping and outputting क. We denote by P(REE) the common value of Py (+r ()) for all j. which satisfies J P() 1.
19

---

It follows that E, Jg P( I Be and that there exists j such that Sa Py(f(E) [ P(f di I pA For this value of j.
P)(E(E)= =1- { P)CRE) 21 PAS-1 2
88 1
The overall failure probability in M2 is thus PY(E") 2 ((()))((ET))) 2 + > 6, which contradiction. Therefore, for all (s,6)-PAC algorithm there exists instance M, for which Py > 1/p) 2 1/88 hence the expected sample complexity under this instance larger than 1/8p.
Let us finally compute the diameter and bias span of MDP Mj. For states and 8s, the only (deterministic) policy with finite traveling time from 81 to 8j is the policy which plays action ja-1 in state 8n for any n E (..SS.). As the bottleneck of exploration is the small probability to transition from 81 82, the travel time biggest from 81 $2. Therefore,
AS-1
D min (t > 0, st = 813|800 = ss, At' ar = ((+)]] - T:S+AA
16s
As for the bias span, by fixing ((82) 0, the Poisson equations (5) yield for i E (3....S) that b(x;) = (i 2)g, and finally b(s1) = (S 1)g S S.
Figure 5: An SSP-MDP and its average reward transformation
20

---

D Complements for Section
D.1 Correctness of the stopping rule
Proof. (Theorem 5) We first note that ga,, Pa Fan = Pan Fan + Pa.bn bn] where we use that
Ps,Pa. = PA..
Since for all 8, a, Ps.ann 2 L (bni 6), we have
g+. An Tan (1)ss.(o)((ni0)) bn) Psn
maxx 12.0 (bni 0))
by the definition of a... and finally I*., min, max, 1n (bxi 6).
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 9n = P = Px Fr + Pabn bnl S Pa Fx + -U (o), bn.
< Pr max 13 (bni 6))
and finally g S max, max, m_. (bn 6) Finally, since g is the gain of an optimal policy, 9 2 ga.
Proof. (Theorem 6) By Theorem 5, we have
P [T < +00, FF <g E]
P nn g" Iz. E, max I 8) min max (bni 6) s
S PP mm Es, a, ps & (bn 8), (b
(b,;;
Using further union bound and the definitions of U and L.,
P < +00, O# < =
< P An, 7s, a. Ps, 2 U (ba(bnn)) 5)) U 7,, 7s, a, as S 1 (bni 0))]
(6, N 8.0)
P
3n. 3s. 3a, KL Ps.a)
N
88,
where the last inequality follows from the concentration result given in Lemma 5,
D.2 sample complexity analysis
In this section, we present and analyze algorithm for the generative model setting using the simplest possible sampling rule, uniform sampling. together with the adaptive stopping rule (6) for bn b, such that b, is the optimal bias function in the AR-MDP with transition probabilities given by (P%,a).,a (normalized so that the bias in the first state is always O). The pseudo-code of the algorithm is given in Algorithm 4.
Remark 1. The quantities Um and L in Definition 2 are solutions complex optimization problems and can be expensive to compute. Several modifications are possible to prevent long run times. First, it is possible not 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 (b,; 6) < Una(bur
(bn; 8) and L (b,; 8) 2 L (br; 6) using Pinsker's 's inequality:
2x(5, No.
2x(8, No a.
Ün (bni 8) = Dr.aba 11bnlloo
(bnn 6) bn - -11b
Nga
No.
Theorem 6 (as well as our sample complexity analysis follow) still applies for these alternative choices which are easier to compute but yield looser confidence intervals and thus theory a larger sample complexity.
21

---

Data: Accuracy (0, 1), confidence level 8 (0, 1) O, bn = 0. M (b,, 6) 1, 1 (bn, |n, 8) = 0; while max, max, m (b.. 5) min, max, Ii,a (bn, 8) do for (s. S A do
Sample reward and next state of a end
= SA;
Compute Paz,a for each (s,a)
Compute bn bn the bias of the empirical MDP, with rewards Fs,a and transitions f2..:
Compute (bn, 6) and In (b,,, 5) using U, L from Definition 2 (or the relaxations (7))
end
(arg max, 1n (bn::)) return A.
Algorithm 4: Uniform sampling combined with adaptive stopping
We analyze Algorithm 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.
A simulation lemma for AR-MDPs To introduce this result, we need the following definitions.
Definition 3. Let DM be the set of policies generating unichain Markov chain on a weakly communicating MDP M. For M an MDP and π E DM.
1
0
0
0 (x(31.82)
8s($1,85)
Is-1
0 82)
85(8
the matrix such that the Poisson equatioos (3) and (4) rewrite as Il = T with the average reward vector and h (g. bx (32) by (81); (s9) b (s1)). We further define
61= min 19x g²1, A max DMDM
|| and A2 max ||/x||00
3.9=$9
TEDM
where the norm used is the operator norm associated to the infinity norm, sup||=||>==1 Ax
||||||
We can show with results from [18] that II, is invertible for any unichain policy म, hence A₃ 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 - PP,,, which is of dimension for unichain MDPs as proved in Theorem A.5. Therefore, since in the unichain setting solutions to IT Hr = T 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 + Es be the transition probability matrix of weakly communicating MDP M' with the same reward function F as M. For a given policy that is unichain on M, if for all (s.a) we have llp'.. Pe.alli S A1(A2+2) then 1 h 11 S x.
Lemma 4. Suppose M unichain. Let p' : S A + Es be the transition probability matrix of unichain MDP M' with the same reward function M. for all s, we have l/p'.a Ps.aali S
where x S 8n /2, then b M' 1| < x. A((++2)
It is necessary to suppose M unichain, because without this assumption, there is no guarantee that there exists 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 I'M := (A + 81/2).
22

---

Theorem 9. For E S d1. with probability larger than - 6, the sample complexity of Algorithm on unichain MDP satisfies
== SA((H +1))TM)²
+ +
log
Just like DFE, Algorithm is (s, 5) PA- algorithm using 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 e and small å both scale in (SAc(MM)s=² log(1/8 1/8) but for different complexity quantities: e1 (M) = for Algorithm while C2 (2 = ((H + 1) V TM2² for Algorithm 4. We know from the lower bound that the latter has be larger for some MDPs, but far did not manage to quantify their difference (even we suspect that 22 can be much larger than c1). Besides this, hope that the sample complexity of Algorithm 4 can be significantly reduced by the of smarter (online) sampling rules.
D.3 Simulation lemmas
such that max I|Pa,a - P'a,ali $ Proof. (Lemma 3) First, let us fix any policy and ||
We thus have Hz h h
I
II Pd Pr. and therefore ||T, IT' y.
h (II, - II,,)= = =II (h h₂)
||T || > 11/ 1
Moreover,
||--1|| < |11
- ||4=31
1
< [[TT]]
|| 7|| ||TT"|||
|111--11-
||159||
||0
since ||-==||| 1.
And therefore,
11 1/
|100
y
<
A2 1 A
z Therefore, for any x. taking A, -d, gives the result.
Proof. (Lemma 4) Fix < 8,/ and let π be an optimal policy in M', For any policy n², using Lemma 3 successively with policy and policy x' yields 9.r g' x 2 g', x > 9 2x and finally fx > !r' 8n which implies by definition of &n that fr 2 Jx', and therefore is optimal in M. Hence applying Lemma to π yields the result.
D.4 Proof of Theorem
Fix a unichain MDP. We prove in Theorem 10 below an explicit upper bound on the sample complexity of Algorithm 4. For 81, we deduce from that
r T= δ SA((H + +1)
[log (1) + $s) s))
c²
as claimed in Theorem 9.
Theorem 10. With probability larger than 1 the sample complexity of Algorithm 4 is smaller than
SA(S 1) y 1
2C
log y 2
C
where y 11 In SA/8 8-1 and C = 258 max (T)
min(6i.c)
23

---

Proof of Theorem 10 We write N; = L to denote the number of visits in each state action pair time step We denote by the optimal bias function (normalized be equal zero in the first state). We set E (0, 8) to be determined later and define the three events
S4
(z( No)
E
Vt, Vs, a. 11pa,a Pa.all1 S
116: - 6l1o0 < <GE}
3 min (( - 2 e, e.11bellz)) }
(6) N₂
(E,
Ss, 19,,,,101 110al110/l120/
Using Lemma 5, know that P(E) - 5.
We first prove that, if E
E2(E, t) is satisfied for a certain time step t, then the stopping condition (6) is satísfied at this time step. To this end, let us assume that & n (E, (,, () holds for fixed & and &. We recall the definition the confidence bounds U and L from Definition 2 and their relaxations U and L. defined in (7). For all (s, a), we have
Ts.a U.. U (b;;)) be(s) S Fa.a + Ü (b1;5) - b.(s)
No ||8: 1100 de(s)
= Tsaa + B2 be +
Ni.
S To.a + Paab + (P'a
Ps,a + pb, - -b)
2x(0, Ni.a)
|1bells0 ((()) b(s) b(s)
No.
2x N
S Tss + Ps.ab b(s) + -lb hn + Bellocy
No
2x(0, No.
+ +110, 11/1-0/100+ +
|80 100 + -10b- 6l100
N3.0
1
3
(1
3
S Tsa Da,a b(s) + + +
+ Ee +
+ g6
To. + Po.ab - b(s) + 2
Similarly, we can prove that
be(s) S rs.a Ps.a b(s) 1
Ts.a + T,c
2
Finally, since b is solution to the optimal Poisson equation (5), we know that
max max (Fa + Ps.ab b(s)) min max (Fs,a + Po.a - b(s)) = 0
follows that
max (T..a + US (b:: b((s)) min max (Feo + L' (Br 8) - be(s)) S
and the stopping condition is met.
Then, we establish a sufficient condition on & and t to have & C (E,
Assume that the event & holds. Let 5" min(fe, 61/2). From Lemma 4, if for all s, have (l, a) - p(s, a)lla Σ fe then ||b - belloo S E'. which implics E1 t). Hence, on E, a sufficient condition for (E, f) to hold is
2x(8, No)
g'
N₂
I'
24

---

Introducing c(E) = [F
this is equivalent to
log (SA/6) + (S 1) (1 + log(1 + N -1)) S dE)
and finally to
N₂ c(E) S-1 log I+ (1+ S- 21+ log(SA/4
N₂
(10)
S-1
Next, we establish a sufficient condition on and have E (E,t) C EE2(E,), that when (5, () holds
We first remark
2x(6,No)
20r(6, No)
|1 10
s (16e bl1oo + 1166l=s))
No
N₂
20 No)
2 (Ee
H) HH)+HH
N₂
Therefore, a sufficient condition for E2(E,t) t) to hold is
2x No)
1 - 65
min
E,
Ne
4(H + {E)
2
Introducing (g)) = min
1-
e² ?
this is equivalent to
32
H++E)
log(5AA/))(5 - 1) log(1 N./(5 1)) (C()NN/(S-))
and finally to
N₂ d({) S-1 log (1+
N₂
log(SA/0)
>
(1I)
S S-1
S-1
Finally, put things together. The conditions (10) and (11) are of similar form. Defining C(E) = min((((E),E(())) for any & E (0, 1/6) the condition
N₂
>1 1 log(SA/o)
C(E) S-1 log 1 1 1-1-1
(12)
S-1
a sufficient condition on have & C & EE (((EE) If follows that for t satisfying (12), the algorithm has stopped before time t, with probability larger than - 8.
We observe that the larger C(g), the less stringent the condition is t, but finding the value of & E (0, 1/6) that maximizes C'E) leads to tedious calculations. Instead we go for finding lower bound on C(1/12), denoted by C, which also provides valid sufficient condition on t:
N₂
No S
1+ log (SA5))
log 1+
S -
-
S-1
log(SA/6) this condition is satisfied for Using Lemma 6, letting = 1 + 8-1
N₂ y
2C
y 4+2
C 2)
1+
log
$ 1-1
C
To conclude the proof, we explicit the value of C. We have
1
(1/2)²
min [(/ (6)))(2)))
C(1/12) = min
32
(H
1/112
r
1
E²
E²
87
min
2
128
(H + +e/12)2
288T
8T
M
1
6²
2²
87
> min
128
(H + 1)2
288T 2
8
M
M
1
g2
8
min
128
H
+ 1)2
2
M
8T2
M
25

---

where we used twice that S 1. Hence valid lower bound on C(1/12) is
mi)( C 288 max(H 11, M))
Auxillary results
In this section, restate useful result from the literature. The first is time uniform concentra- tion result on the transition probabilities that can be obtained as a consequence of Lemma 9 from [T].
Lemma 5, For all å E (0, 1), with æ(6, v) loo (S 1) log (e(1 + v/(5 - 1))),
8
P [ E N: N N
KL (a Ps,a) > N(6,N S
SA
Furthermore, letting B(n, 8) == /20lbm)) the event
= (Vs, a, vn 1, 1l2h, Pe.alli S B(N 8))
holds with probability 6.
Proof. With (m) the empirical estimate of Ps.a once m samples have been collected in arbitrarily setting (0) as the constant vector 1/S,
P In E IN N KLLP', Ps,a) > 216, N 8.01 S)]
P [n, E IN: No. m, N (L Pa.a) x(6, No S)]
PP [mm E IN m Ps,a) > x(6, m, m) S)]
6
SA
by Lemma 9 from [1]. The second claim stems from union bound over S, A and Pinsker's inequality applied to the first claim.
The second result is an inversion lemma, which allows get explicit sample complexity bounds. Lemma 6 (Lemma 15 from [13]). Let 2 and b, c, d 0.
n < a + bog((c + dn) then
1 A
d a + blog c+ (a+ blVe+ va)22)
n S
26

---

NeurIPS Paper Checklist
1. Claims
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 is not possible to feasibly estimate (shown in Theo- rem 1), that our algorithm (Algorithm 1) requires prior knowledge, is (e, 6)-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 proposed stopping rule is (e, 6)-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 long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations 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 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
27

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Some of the more general assumptions (prior knowledge of the mean knowl- edge, generative model) are listed in the introduction. We have stated some proofs of past results for completeness when relevant.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
We have made experiments
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
28

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
We have made no experiments
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips..
public/ /uui CeeeeSeeeo as
wttpsaimmssssssnnieeiooeooeioene conPolccy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nips. wttppcccccc/ccccccccccccccccctct guides/ catnsuubmssiioPPoo
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, 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 the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
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, confi-
dence intervals, statistical significance tests, 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 with given experimental conditions).
29

---

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).
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 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 figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: We have made no experiments
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttp///eerrr/eeeeee/eee/eeeeeeet cc htppppl//aaaaaeepleeeeeeeeppppea ctuuidee ines?
Answer: [Yes]
Justification: Our work is theoretical enough not cause any ethical concerns
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration 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 socictal 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.
30

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not have any experiments, and release no models
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses 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 existing assets
Guidelines:
The answer NA means that the paper does 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
31

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We release assets
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: We have not used crowdsourcing or research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We have not used crowdsourcing or research with human subjects
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "OuoisHjyu5", "reviewer": "Reviewer_XRXp", "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.\nSome 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.\nFor 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.\nThe paper also explains the difficulty of reducing the PAC problem to cumulative regret minimization.", "questions": "n.a.", "limitations": "n.a.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Novel results, new ideas, especially with the lower bounds.", "weaknesses": "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.)\n\nSince 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback on our paper.\n\nIt is true that we do not relate the PAC setting to most other settings, but we do point out that the results in the cumulative regret setting are unapplicable here, which is quite different from the finite horizon or discounted models. An interesting new preprint, Achieving Tractable Minimax Optimal Regret in Average Reward MDPs by Boone et al., 2024, even provides a regret-minimizing algorithm that scales in $H$ without requiring prior knowledge of it - something we argue does not seem attainable in best policy identification. Looking at what happens when attempting to minimize for example simple regret in average-reward would be interesting future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bWX39IVkSa", "reviewer": "Reviewer_NtfV", "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.", "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?\n\nCould the authors clarify which algorithms and theorems they consider to be the main technical contributions of this paper?", "limitations": "The authors adequately addressed the limitations in the conclusion.", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "This paper presents a complete procedure, DFE, that achieves near-optimal sample complexity for small $\\epsilon$ without any prior knowledge of $H$ for average-reward MDP. This approach fills a gap in the existing literature.\n\nThe finding that accurately estimating $H$ can have arbitrarily large complexity is new and interesting.\n\nThis paper also presents a new finding that achieving a sample complexity polynomial in $H$ in the online setting is infeasible, setting theoretical boundaries for future research.\n\nThe paper is technically sound, demonstrating rigor in the development and justification of its claims. The presentation quality of this paper is good.\n\nThe authors did a great literature review on average-reward MDPs.", "weaknesses": "The main concern with this paper is the limited novelty and contribution of the proposed solutions. \n\nThe 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$.\n\nThe 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.\n\nThe 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.\n\nIn 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.\n\nTheorem 3 in this paper is also very similar to Theorem 9 in [5].\n\nWhile 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed feedback on our paper.\n\nOur main point in this paper is that H is not the right complexity measure for best policy identification in average reward MDPs. Once that point is made, we then turn to other measures and provide an algorithm that shows that a bound depending on D instead can be attained without prior knowledge.\n\nIn [27] and other previous papers, the lower bound considered uses H as the main complexity measure, and the algorithm of [27] is said to have a sample complexity bound that also depends on H, provided H is given to the algorithm.\nAs the reviewer points out, the algorithm also can take an upper bound of H and have a sample complexity that depends on the upper bound (and we use this in our paper).\nNonetheless, the focus in that previous paper and others is on H: H is presented as the right complexity measure, and the need to know an upper bound on it in the algorithm is minimized (H is assumed known \"for simplicity\").\n\nWe argue that having an upper bound on H that actually reflects H (and not something else like D) is not feasible, and that the focus on H in the bounds in the literature is perhaps misplaced. In the generative setting, we prove that we can't first estimate H and then use it in an algorithm that takes it as a parameter (Theorem 1). In the online setting, we prove a lower bound that shows that no algorithm can have an upper bound polynomial in H and not D (Theorem 3).\n\nThen we demonstrate that a weaker complexity measure, D, is attainable. We agree that our algorithms are a combination of previous ones. The novelty in our work is the idea that since H seems to not be attainable, obtaining algorithms that depend on D is meaningful. Given that it's achievable by a combination of previous algorithmic elements, we did not reinvent a new way of doing it (the combination of those methods to obtain an algorithm scaling with D had however never been described).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "f5DHCE9awj", "reviewer": "Reviewer_en8V", "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.", "questions": "Please find my questions in the comments above.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "I appreciate the efforts to study the sample complexity bounds without prior knowledge.  However, the current result seems incremental and insufficient for an acceptance in my opinion.", "weaknesses": "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.\n\nMinimax-optimal reward-agnostic exploration in reinforcement learning, Li et.al., 2024;\n\nHorizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies, Zhang et. al., 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's insightful feedback on our paper.\n\nOur main contribution in this paper is that H is not the right complexity measure for best policy identification in average reward MDPs. Once that point is made, we then turn to other measures and provide an algorithm that shows that a bound depending on D instead can be attained without prior knowledge.\n\nIt is true that we have not shown that there cannot be any algorithms scaling in $H$ in the generative model. However, we have seen that there are none in the current literature. Since the original lower bound of [22] scales in $D$, $H$ is impossible to estimate, and the in the online setting an algorithm can reach $D$ but not $H$, we postulate that bounds scaling in $H$ are unattainable. However, what is certain is that the current state of the art algorithms cannot actually scale in $H$, making our algorithm scaling in $D$ meaningful.\n\nWe thank the reviewer for the references to reward-free exploration and will investigate how they could be used for best policy identification.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9ngJtPWmQq", "reviewer": "Reviewer_FXz4", "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.", "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.\n\nThis 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?\n\nTheorem 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)\n\nThe formatting for the display for Algorithm 1 should be fixed", "limitations": "There are no significant limitations which require addressing", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The problem of learning near-optimal policies in average reward MDPs without knowledge of complexity parameters is a fundamental and important problem, and this paper makes a number of small but important steps towards either achieving this goal or demonstrating its difficulty. I therefore am confident that this work will prove to be significant, in the sense that it will lead to future work which build off of its attempts. I think the presentation is mostly very clear and does a good job motivating the different settings and ideas.", "weaknesses": "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.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are thankful to the reviewer for their very constructive feedback on our paper.\n\nWhile the algorithms we present are combinations of previously known methods, the main point of interest of this paper is that $H$ is not the right measure of complexity due to the impossibility of estimating it and the fact the sample complexity does not scale well with it in the online setting. %The solutions given are indeed proofs of concept.\nWe show that combining prior work is near optimal with regards to the more meaningful complexity measure $D$. While the complexity analysis in 6.2 is only valid in the generative model, the correctness is proved also in the online setting, and thus provides a new way of constructing online best policy identification algorithms.\n\nThe assumption of unique optimal policy is indeed merely useful for convenience of definitions. We can remove this assumption by redefining $H$ to be the maximum bias span over all gain-optimal policies, as we do not try to reach bias-optimality.\n\nThe notation in Table 1 is meant to hide log factors in $\\log(1/\\delta)$, not those in $\\delta$ (as $\\log(1/\\delta)$ is the ``right'' dependence in $\\delta$). We will clarify this in the paper. The bound in [27] depends on $\\log(1/\\delta)$ and that dependence is missing in the table: this will be fixed. The other entry that currently does not have a $\\log(1/\\delta)$ factor is the lower bound of [12], which indeed does not depend on $\\delta$.\n\nFor Theorem 1, we can change the example to obtain a MDP with known rewards, and shift the difficulty to estimating transitions. We can replace state 2 by three states, (2, 2', 2''), where 2 is connected to 1 and 3 as in Figure 1, but we remove the action with reward R.\nInstead we add an action with reward 1/2 that transitions to 2' with probability $R$ and to 2'' with probability $1-R$. In 2' there is only one action which goes to 2 with probability 1 and reward 1. In 2'' there is also one action which goes to 2 with probability 1 and reward 0. Choosing $p$ to be $(1+\\varepsilon)/2\\Delta$ and $R=1/2 \\pm\\varepsilon$ yields the result through the same reasoning as in Theorem 1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)