Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs
Authors: Matthew Zurek
Yudong Chen
Venue: NeurIPS 2024 oral (2024)
Keywords: reinforcement learning theory
average reward
sample complexity
Primary area: reinforcement_learning
TL;DR: We resolve the span-based sample complexity of weakly communicating average reward MDPs and initiate the study of general multichain MDPs, obtaining minimax optimal bounds and uncovering improved horizon dependence for fixed discounted MDP instances.

Abstract: We study the sample complexity of learning an $\varepsilon$-optimal policy in an average-reward Markov decision process (MDP) under a generative model. For weakly communicating MDPs, we establish the complexity bound $\widetilde{O}\left(SA\frac{\mathsf{H}}{\varepsilon^2} \right)$, where $\mathsf{H}$ is the span of the bias function of the optimal policy and $SA$ is the cardinality of the state-action space. Our result is the first that is minimax optimal (up to log factors) in all parameters $S,A,\mathsf{H}$, and $\varepsilon$, improving on existing work that either assumes uniformly bounded mixing times for all policies or has suboptimal dependence on the parameters. We also initiate the study of sample complexity in general (multichain) average-reward MDPs. We argue a new transient time parameter $\mathsf{B}$ is necessary, establish an $\widetilde{O}\left(SA\frac{\mathsf{B} + \mathsf{H}}{\varepsilon^2} \right)$ complexity bound, and prove a matching (up to log factors) minimax lower bound. Both results are based on reducing the average-reward MDP to a discounted MDP, which requires new ideas in the general setting. To optimally analyze this reduction, we develop improved bounds for $\gamma$-discounted MDPs, showing that $\widetilde{O}\left(SA\frac{\mathsf{H}}{(1-\gamma)^2\varepsilon^2} \right)$ and $\widetilde{O}\left(SA\frac{\mathsf{B} + \mathsf{H}}{(1-\gamma)^2\varepsilon^2} \right)$ samples suffice to learn $\varepsilon$-optimal policies in weakly communicating and in general MDPs, respectively. Both these results circumvent the well-known minimax lower bound of $\widetilde{\Omega}\left(SA\frac{1}{(1-\gamma)^3\varepsilon^2} \right)$ for $\gamma$-discounted MDPs, and establish a quadratic rather than cubic horizon dependence for a fixed MDP instance.

Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs
Matthew Zurek
Yudong Chen Department of Computer Sciences University of Wisconsin-Madison yudong. Chen@wisc.edt
Department of Computer Sciences University of Wisconsin-Madison matthew. zurek@wisc.ed
Abstract
We study the sample complexity of learning an s-optimal policy in an average- reward Markov decision process (MDP) under generative model. For weakly communicating MDPs, we establish the complexity bound Ô AS where H is the span of the bias function of the optimal policy and SA is the cardinality of the state-action space. Our result is the first that is minimax optimal (up log factors) in all parameters S, A, H. and E, improving on existing work that either assumes uniformly bounded mixing times for all policies or has suboptimal dependence on the parameters. We also initiate the study of sample complexity in general (multichain) average-reward MDPs. We argue a new transient time parameter B is necessary, establish an Ô (SA B+H) complexity bound, and prove a matching (up to log factors) minimax lower bound. Both results are based on reducing the average-reward MDP to a discounted MDP, which requires new ideas in the general setting. To optimally analyze this reduction, develop improved bounds for y-discounted MDPs, showing that (SA
and Ö(SA (1->}=s²) samples suffice to learn s-optimal policies in weakly communicating and in general MDPs, respectively. Both these results circumvent the of 2 (SA (1 for disccuutee MDPs, and establish quadratic rather than cubic horizon dependence for a fixed MDP instance.
B+H
minimax lower bound
Introduction
The paradigm of Reinforcement learning (RL) has demonstrated remarkable successes in various sequential learning and secision-making problems. Empirical successes have motivated extensive theoretical study of RL algorithms and their fundamental limits. The RL environment is commonly modeled as a Markov decision process (MDP), where the objective is to find policy that maximizes the expected cumulative rewards. Different reward criteria are considered, such as the finite horizon total reward E" Σ R.] and the infinite horizon total discounted reward ET [Σ yRRc] with a discount factor 7 < 1. The finite horizon criterion only measures performance for T steps, and the discounted criterion dominated by rewards from the first 1
T time steps. In many situations where the long-term performance of the policy æ is of interest, we may prefer to evaluate policies by their long-run average reward limy ET [TT=] R.].
A foundational theoretical problem in RL is the sample complexity for learning near-optimal policy using a generative model the MDP [10] meaning the ability to obtain independent samples of the next state given any initial state and action. For the finite horizon and discounted reward criteria, the
sample complexity of this task has been thoroughly studied (e.g., 3 15 19 [[2). However, despite significant effort (reviewed in Section 1.1 the sample complexity of the average reward setting is unresolved in existing literature.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Our contributions In this paper, we resolve the sample complexity of weakly communicating Average-Reward Reward MDPs (AMDP) in terms of H := ||h* spunn the span of the bias (a.k.a. relative value function) of the optimal policy. We show that (SAHH/E² samples suffice to find an e-optimal policy of a weakly communicating MDP with S states and A actions. This bound, presented in Theorem is the first that matches the minimax lower bound (SSAH/E*) up to log factors.
Furthermore, we initiate the study of sample complexity for average-reward general MDPs, which refers to the class of all finite-space MDPs without any restrictions [1]. General MDPs are not necessarily weakly communicating and all their optimal policies may be multichain. In this general setting, we demonstrate the span H alone cannot characterize the sample complexity, as the lower bound in Theorem 4 exhibits instances which require > HS A/e² samples. This observation motivates our introduction of new transient time bound parameter B, which in conjunction with H captures the sample complexity of general average-reward MDPs. Specifically, our Theorem
g shows that
δ (SAA B+H) samples suffice to learn an E-optimal policy, and Theorem provides a matching minimax lower bound of ? (SA
= B= We remark that it is trivially impossible to achieve low regret in standard online settings of general MDPs, since the agent may become trapped in closed class of low reward states [4]. The simulator setting is natural for studying general MDPs since it avoids this fatal issue, although the existence of multiple closed classes with different long-run rewards still plays a fundamental role in the minimax sample complexity, as reflected in the dependence on B.
To establish the above upper bounds, we adopt the and improve on prior work by developing enhanced sample complexity bounds for y-discounted MDPs (DMDPs). We improve the analysis of variance parameters related to DMDPs using a new multistep variance Bellman equation, which is applied in a recursive manner to bound the variance of near-optimal policies. For general (multichain) MDPs, we further utilize law-of-total- variance ideas to bound the total variance contribution from transient states, which present new challenges significantly different to their behavior in the weakly communicating setting. Our average- to-discounted reduction also requires new techniques, because many structural properties used in earlier reduction arguments no longer hold for general MDPs. Our analysis leads to DMDP B+H
approach ( 20),
sample complexities of ((SA (1-7)422) H and Ö(SA,
(1-7)222 to learn c-optimal policies in weakly communicating and general MDPs, respectively. Notably, the latter bound, valid for all MDPs, circumvents the existing lower bound Q SA
3 15 Whereas this minimax lower bound
(1-7)8a22
allows the adversary to choose the transition matrix P based on with B x T 3 Theorem 3], our result reflects the complexity of a fixed MDP P through its parameters H, B and quadratic dependence on the effective horizon r This fixed-P complexity essential for our particular algorithmic approach, where the reduction discount 7 is chosen depending on P. is also a more relevant framework in general for many RL problems where the discount faccor is tuned for best performance on a particular instance.
1.1 Comparison with related work on average-reward MDPs
We summarize in Table existing sample complexity results for average reward MDPs.
Various parameters have been used to characterize the sample complexity of average reward MDPs. including the diameter D of the MDP, the uniform mixing time bound Tunif for all policies, and the span H of the optimal bias; formal definitions are provided in Section 2 All sample complexity upper bounds involving Funif require the strong assumption that all stationary deterministic policies have finite mixing times. Otherwise, Tumif co by definition, which for example occurs if some policy induces a periodic Markov chain. It is also possible to have = oc, while H and our newly introduced B are always finite for finite state-action spaces. As shown in (20). there is generally no relationship between 1) and Tunif; they can each be arbitrarily larger than the other. On the other hand, it has been shown that H < 1) [4] and that H < 8Tuni (20). Therefore, either of the first two minimax lower bounds in Table T (which both use hard instances that are weakly communicating)
imply lower bound of Ω ( H and thus the minimax optimality of our Theorem
To the best of our knowledge, no prior work has considered the average-reward sample complexity of general (potentially multichain) MDPs Existing results make assumptions at least as strong as weakly communicating uniformly bounded mixing times.
2

---

Method
Sample Complexity
Reference
Comments
Ö(SA 2
Primal-Dual SMD
8
requires uniform mixing
Reduction to DMDP
Ô (SA Tunit
requires uniform mixing
S Ö SA Tuuit
Policy Mirror Descent
requires uniform mixing
Reduction to DMDP
Ô (SA Tugit
2
requires uniform mixing
Reduction to DMDP
A
20
weakly communicating
Refined Q-Learning
((SA
H²
26
weakly communicating
g
Reduction to DMDP
Ö (SAA H
Our Theorem
weakly communicating
Reduction to DMDP
Ö(SA
Our Theorem
8
general MDPs
Lower Bound
i (SA Smgit)
implies 52 (SA g2
Lower Bound
Ω (SA
20
implies 52 (
Lower Bound
ńt (SA B+H PM
Our Theorem
general MDPs
Table 1: Algorithms and sample complexity bounds for average reward MDPs with S states and A actions. The goal is finding an e-optimal policy under generative model. Here H == || Ilspan is the span of the optimal bias, Tunif is uniform upper bound mixing times of all policies, and D is the MDP diameter, with the relationships H S STunif and H < D. B is the transient time parameter.
The work 9 was the first to develop an algorithm based on reduction to a discounted MDP with discount factor of 7
Tunis" Their argument was improved in (20), which improved the uniform mixing assumption to only assuming a weakly communicating MDP, and used a smaller discount factor y = 1 A. These arguments both make essential use of the fact that the optimal gain is independent of the starting state, which does not hold for general MDPs. After analyzing the reductions, both (9] and (20) then solved the discounted MDPs by appealing to the algorithm from [2]. To the best of our knowledge, the algorithm of 12 the only known algorithm for discounted MDPs which could work with either reduction, as the reductions each require _ 1- m-y policy from the discounted MDP, and other known algorithms for discounted MDPs do not permit such large suboptimality levels. (We discuss algorithms for discounted MDPs in more detail below.) Other algorithms for average-reward MDPs are considered in 9 13 26 matching the minimax lower bounds.
The above results fall short of
While preparing this manuscript, we became aware of (22), which considers the uniform mixing setting and obtains minimax optimal sample complexity O Tugit) in terms of Tunif- Although developed independently, their work and ours have several similarities. We both utilize discounted reductions and observe that is possible improve the sample complexity of the resulting DMDP task by improving the analysis of variance parameters. They accomplish the improvement by leveraging the uniform mixing assumption, whereas make use of the low span of the optimal policy. Note that H < 8Tunit holds in general and there exist MDPs with H < Tunif = co, so our Theorem 2 strictly stronger than the result of 22
c.
1.2 Comparison with related work on discounted MDPs
We discuss a subset of results for discounted MDPs in the generative setting. Several works 15
19
12 obtain the minimax optimal sample complexity of Ö Ö(5A (SSA for finding e-optimal policy w.r.t. the discounted reward. However, only [2] able to show this bound for the full range of E (0, r-11- As mentioned, the reduction from average reward MDPs requires a large in the resulting discounted MDP, making it unsurprising that all of 99 20 22 as well as our Algorithm ] essentially use their algorithm. The matching lower bound established in 15.3.
As mentioned earlier, both we and the authors of 222 21 independently observed that the á (SA (A-T))))))) sample complexity lower bound can be circumvented in the settings that arise
3

---

under the average-to to-ddscuuutedd reductions. The authors of [22] 21 assume uniform mixing and
obtain discounted MDP sample complexity of (1 (1-7)-0²
Funif
first in [2 by modifying the
algorithm of [9] and then in (22] under wider range of E by instead modifying the analysis of [12]. The work [2]] also proves matching lower bound. Our Theorem for discounted MDPs attains
assuming only that the MDP is weakly communicating. Again, in light of the relationship that H < 8Tuuif our results are strictly better (ignoring constants), and their lower bound also establishes the optimality of our Theorem
sample complexity of Ö (TSAT-
H
2 Problem setup and preliminaries
Markov decision process (MDP) is given by a tuple (S, where S is the finite set of states, A is the fimite set of actions. P : S x A + (SS) is the transition kernel with A(S) denoting the probability simplex over S, and : S X + [0, 1] the reward function. Let S := [S] and A |A] denote the cardinality of the state and action spaces, respectively. Unless otherwise noted, all policies considered are stationary Markovian policies of the form π S + A(A). For any initial state so E S and policy и, we let E denote the expectation with respect to the probability distribution over trajectories (So: Ao, Si, .I,...) .) where So 8n. A, ~ π (St). and Se+1 ~ P(- | Se, Ar).
Equivalently, this is the expectation with respect to the Markov chain induced by x starting in state so, with the transition probability matrix Pa given by (Pa)...' == LOEA π (a)s) s, a). We also define (ra),= == EOSA T(als)r(s, a). We occasionally treat P as an (S X A)-by-S matrix where Paa.s' = P(s, a, s'). We also let P.u denote the row vector such that (sa P(s, a, s'). For any S and any bounded function X of the trajectory, we define the variance V [X] := BT (X - E. [x])², with its vector version y [X] E R$ given by (V [X]), = V, [X]. For s E S, let e, E I be the vector that is all 0 except for a 1 in entry 8. Let R be the all-one vector. For each v E R,, define the span semi-none ||tillspon : max.es v(s) minges v(s).
Discounted reward criterion A discounted MDP is tuple (8, A. P,r, 7), where 7 E (0. 1) is the discount factor. For a stationary policy オ, the (discounted) value function V. : :S - [0, x)) is defined, for each 8 E S, as V (s) == E 20 - yRRs, where R. = =r(S,. A,) is the reward received time f. It is well-known that there exists optimal policy n., that is deterministic and
satisfies Vi (s) = (s) == sup, (s) for all s E S [4]. In discounted MDPs the goal is to compute an E-optimal policy, which we define as policy π satisfying || - -V+ll S E. We define one more variance parameter Vp, [V RRS specific to a given policy æ, by (Vp. [V7)),
Eves (Pr) (V') E.. (P+) a. (s])
Average-reward criterion In an MDP (S, P,r). the average reward per stage or the gain of policy æ starting from state s is defined as ,² (s) == lim A [Eioo R.]. The bias function of any stationary policy is (s) == C-limy E [>T (R, - pT (S{)) ]. where C-lim denotes the Cesaro limit. When the Markov chain induced by P- is aperiodic, C-lim can be replaced with the usual limit. For any policy æ, its p and ha satisfy pT P=p" and pT h r. P,h
policy x is Blackwell-optimal if there exists some discount factor 7 E (0, 1) such that for all y 2 5 we have V 2 V. for all policies m. Henceforth we let x denote some fixed Blackwell-optimal policy, which is guaranteed to exist when S and A are finite 14]. We define the optimal gain pa E R by (s) sup- (s) and note that we have p² = pT For all s E S, p= (s) 2 max Peap", or equivalently p² 2 Pxp" for all policies (and this maximum is achieved by T²). We also define h²* h= (and note that this definition does not depend on which Blackwelll are multiple). For all s E S. p" and h* satisfy p*()) + (s) = max p"p (8) Tsa + Pech" known as the (unmodified) Bellman equation.
n is used, if there
weakly communicating MDP is such that the states can be partitioned into two disjoint subsets S S S₁ U S2 such that all states in SJ are transient under any stationary policy and within S2, any state is reachable from any other state under some stationary policy. In weakly communicating MDPs p² is constant vector (all entries are equal), and thus (p*, .I')) are also solution to the modified Bellman equation /² (s) + h (s)))) = maxae A Tsa + Psah" When discussing weakly communicating MDPs we occasionally abuse notation and treat p² scalar. A stationary policy is multichain if it
4

---

induces multiple closed irreducible recurrent classes, and an MDP is called multichain if it contains such a policy.
MDPs always contain some gain-optimal policy which is unichain (not multichain), but in general MDPs, all gain-optimal policies may be multichain and p* may not be a constant vector. All uniformly mixing MDPs are weakly communicating. In the average reward setting, our goal is find an s-optimal policy, defined as policy л such that || p ll c.
Complexity parameters Our most important complexity parameter is the span of the optimal bias function H := ||h* Il II In addition, for general MDPs we introduce a new transient time parameter B, defined as follows. Let IT be the set of deterministic stationary policies. For each л E IT, let R be the set of states which are recurrett in the Markov chain Pr. and let T = S' \ R be the set of transient states. Let TR= = it S; E R²} be the first hitting time of a state which is recurrent under т. We say MDP satisfies the bounded transient time property with parameter B if for all policies т and states a E & we have E [TR=] S B, or in words, the expected time spent in transient states (with respect to the Markov chain induced by T) is bounded by B.
We recall several other parameters used in the literature to characterize sample complexity. The diameter is defined as D == max,, inn E,, Ma2l where denotes the hitting time of a state s E S. For each policy æ, if the Markov chain induced by P= has a unique stationary distribution Ux. we define the mixing time of π as T == inf { 2 1 : max _ (P=)* - v/ S 2t) If all policies π E II satisfy this assumption, we define the uniform mixing time Tunif == sup= T= Note that D) and Tunif are generally incomparable [20,, while we always have H < D) 4 and H S &Tunif [20]. It is possible for Tunif = co, for instance if there are any policies which induce periodic Markov chains, Also, D= = oo if there are any states which are transient under all policies. However, H and B are finite in any MDP with S, A < 00. Also if Tunif is finite, Lemma 27 shows B < 4Tunif-
We assume access to a generative model [0] also known as a simulator. This means we can obtain independent samples from P(- S. s. for any given s E S. E A, but P itself is unknown. We assume the reward function r is deterministic and known, which is standard in generative settings (e.g.. 21 since otherwise estimating the mean rewards is relatively easy. Specifically, to learn an e-optimal policy for the discounted MDP, we would need to estimate each entry of r to accuracy O(11 - 7)e), which requires a lower order number of samples Ō (1-7))==²) ). For this reason we assume (as in (20 that H 2 1. Using samples from the generative model, our Algorithm D constructs an empirical transition kernel P. For a policy we use (T((s) to denote the value function computed
with respect to the Markov chain with transition matrix Px (as opposed to Pa). Our Algorithm I also utilizes perturbed reward function 7, and we use the notation V... (s) denote a value function
computed using this reward (and Pa); more concretely, we replace R, with R = F(S,. Ad) in the definition above of V.. We use the notation Vi when using P and F simultaneously.
3 Main results for weakly communicating MDPs
Our approach is based on reducing the average-reward problem to a discounted problem. We first present our algorithm and guarantees for the discounted MDP setting. As discussed in Subsection 1.I our algorithm of choice, Algorithm[]] [ is essentially the same as the one presented in [12. with a slightly different perturbation level ę. Algorithm ] constructs an empirical transition kernel P using samples per state-action pair from the generative model, and then solves the resulting empirical (perturbed) MDP (P, F, 7). As noted in [12), the perturbation ensures 7. can be computed exactly in poly( - S, A, log(1/)))) time by multiple standard MDP solvers. We remark in passing that the SA- transition matrix P has at most nSAA nonzero entries.
Our Theorem D provides an improved sample complexity bound for Algorithm | Junder the setting that the MDP is weakly communicating.
Theorem 1 (Sample Complexity of Weakly Communicating DMDP). Suppose the discounted MDP (P,r, r, 7) is weakly communicating. H
1 1 and & < H. There exists constant C2 > 0 such that, I-
for any d E (0, 1). in C2
H log (11-2) SA {A_), then with probability at least 1 8, the policy
Th output by Algorithm satisfies V7 V1 7. <e.
5

---

Algorithm Perturbed Empirical Model-Based Planning
input: Sample size per state-action pair nt target accuracy e, discount factor ?
I: for each state-action pair (s, a) E S x A do
2: Collect n. samples S 5,a' 5,,..... s,a from P(- ssa))
3: Form the empirical transition kernel P(s/ 8, = = - 115 - ='), for all 8' e
4: end for
5: Set perturbation level 5 = (1 - 7)
6: Form perturbed reward F r + Z where (s, a) iid. Unif(0, {)
7: Compute a policy SG.p which is optimal for the perturbed empirical discounted MDP (P, 7,
8: return 7.
Since we observe n samples for each state-action pair, Theorem I shows that a total number of samples suffices to learn an s-optimal policy. This bound improves on the O --
( HSA ->
complexity bound from [[2] when the span H is no larger than the effective horizon
This
assumption holds many situations, as can be seen by using the relationships S D or H S 8Tunif- On the other hand, in the regime with H > -ーx the existing bound Ō ( ), also achieved by Algorithm
1 is superior. In this regime, the discounting effectively truncates the MDP at a short horizon before the long-run behavior of the optimal policy (as captured by H) kicks in.
Proof highlights for Theorem 7 The key to obtaining this improved complexity is careful anal- ysis of certain instance-specifte variance parameters. It suffices to bound 1 V and
7.p -V
S4 v by O(e). The prior DMDP complexity of [I- is obtained using the well-
known law-of-totall-arrinnc argument 11122 which ultimately yields sample complexity like
SA دー
1 xd R.]]ls.
to bound V. -1," I O(e). From here, the variance of
the cumulative discounted reward
E> 7 R. is bounded by (1-7)2 since the total reward
in a trajectory is within [0, r We instead seek to bound | [ 7 Rel S O
Assume H is an integer. The first step is to decompose VT [E *R,) recursively like
H-1
V
Σ R'e = V
ΣT 7 (V; + 2H (Prz)
RR,
R
(see our Lemma This is multi-step version of the standard variance Bellman equation (e.g., [16 Theorem I)). Ordinarily an H-step expansion would not be useful, since the term V.,"" (SH) by itself appears to have fluctuations on the order of + in the worst case depending on SH (note SH is the
random state encountered at time H). However, in our setting, we should have V,"* = -
h (SH), reducing the magnitude of the random fluctuations to order H = || (See Lemma
for a formalization of this approximation which first appeared in (23]. Therefore expansion to H
steps achieves the optimal tradeoff between maintaining 1/";" |
H-1
7 RR + (SH)) S O (H2)
and minimizing 2H, As desired this yields
- 7 R.
0
H2 (- 0 ( where
T- 00( ())-T)) requires + H. See Lemma
15 for the complete argument.
We would like to use a similar argument as above to bound the second term [. V #
which is the "evaluation error" of the empirically optimal policy . However, applying the same argument would give bound in terms of Vi m.r
span which, unlike for the analogous term involving the true optimal policy n². a priori bounded in terms of H. (If we instead assumed uniform mixing, we could immediately bound this by ((Tunit). ).) Thus, to control the variance associated with (1 V V, #
evaluating p we are able recursively bound V,, P
which
span
can be shown to yield the desired sample complexity.

---

Now we present our main result for the rverage-reward problem in the weakly communicating setting. Applied this setting with DMDP target accuracy e = H. our Algorithm reeduess the problem to y-discounted MDP with
12H and then calls Algorithm T with target accuracy H.
Algorithm 2 Average-to- to- Discouut Reduction
input: Sample size per state-action pair n, target accuracy (0, 11, DMDP target accuracy
1: Set = 1 12c
2: Obtain #* from Algorithm | with sample size per state-action pair n, accuracy E, discount 7
3:
return f**
We have the following sample complexity bound for Algorithm 2
Theorem 2 (Sample Complexity of Weakly Communicating AMDP). Suppose the MDP (P,r) is weakly communicating. There exists a constant C₁ > such that for any 8, (0, 1), if Ci z log (SAH) ) we call Algorithm 2 with e H, then with probability least 6, the output policy ît" satisfies the elementwise inequality p* p² S El.
Again, since we observe n samples for each state-action pair, this result shows that Ō (SSA 2 total
samples suffice to learn s-optimal policy for the average reward MDP. This bound matches the minimax lower bound in [20 and is superior to existing results for weakly communicating MDPs
(see Table] D. We note that the proof of Theorem I works long as H is any upper bound of [ span
hence Algorithm 2 also only needs an upper bound for ||h*], span'
We show in the following theorem that it is in general impossible to obtain a useful upper bound on ||A* Ilapan with a sample complexity that is a function of only ||**|lapann This suggests that not easy
to remove the need for knowledge of |[h"]] span
Theorem 3. For any given n, T 2 1, there exist two MDPs Mo and M, with S = 4, A such that Mo has optimal bias span 1, .M, has optimal bias span T, and it is impossible to distinguish between Mo and Mi with probability 2 with samples from each state-action pair.
Thus even for an MDP with small span, there exists another MDP that has arbitrarily large span and is arbitrarily statistically close (that is, cannot be distinguished even with a large sample size n). We emphasize that all previous algorithms in Table also require knowledge of their respective complexity parameters, and such assumptions are pervasive throughout the literature on average- reward RL. The only exception of which we are aware is the contemporaneous work 7 which
achieves a suboptimal Ö(SA A Tagit) sample complexity without knowledge of Tumit in the uniformly mixing setting. is unclear if H-based sample complexities are possible without knowing H. Besides the evidence offered by Theorem 3 in the online setting, it has been conjectured that knowledge of H necessary to obtain an H-dependent regret bound 6 5 25). Moreover, even with knowledge of H, the only known online algorithm with optimal regret is computationally inefficient 25 making it somewhat surprising that our Theorem usee simple and efficient algorithm.
Nevertheless, when H is unknown, one can replace H with the diameter D (since H < D). The diameter is known to be estimable [25] i and is often a more refined complexity parameter than Tunif- Our Theorem 2 is the first to imply the optimal diameter-based complexity Ō O(542). ), given knowledge of D or using constant-factor upper bound obtained from some estimation procedure.
4 Main results for general MDPs
Our starting point for general MDPs that unlike the weakly communicating setting, their complexity cannot be captured solely by |h*] Imppmn We first argue this point informally using the simple example in Figure [] which is parameterized by value T 1. Only state contains multiple actions, and action 2 is optimal since it leads to state 2 which collects reward 0.5 forever, while taking action will always eventually lead to state 3 where the reward is 0 forever. We thus have p* [0.55 0.5, 0] T and [|A*| II span = O. However, clearly ((T)) samples are required to even observe a transition - 3. so the sample complexity must depend on T > (without observing a transition - 3, we cannot determine that action 1 is not optimal). Taking action 1 leads to large reward of in the short
7

---

term (for T steps in expectation), so even if we had perfect knowledge of the environment, the optimal y-discounted policy would not choose the optimal action a 2 until the effective horizon I- 2 ((T)). Thus T-y ~ H is insufficient for the reduction to discounted MDP. Note that this instance has its bounded transient time parameter B = T. This example reflects that transient states play a categorically different role in general MDPs: the weakly communicating setting, states which are transient under all policies be completely ignored, whereas in this example our action at state 1 fully determines our reward even though state is transient under all policies.
== 2
2 b R = 0.5
1, 11
P(3 1, 1,
P(1 1, =11)=1-
3 3
R=
Figure 1: A general MDP where 7-discounted approximation fails unless T ((T) >> ||**|lap
The statistical hardness is formally captured by the following theorem, which uses improved instances to obtain the correct dependence on E.
Theorem 4 (Lower Bound for General AMDPs). For any E (0,1/4), B 2 1, A and E 8N, for any algorithm A Alg which is guaranteed to return an E e/3-optimal policy for any input mverage-reward MDP with probability at least 1. there exists MDP M (P,r) such that:
1. M has S states and A actions.
2. Letting h² be the bias of the Blackwellooptimal policy for M, we have | = O.
3. M satisfies the bounded transient time assumption with parameter B.
4. A lg requires O2 (8) samples per state-action pair on M.
A similar minimax lower bound holds for the discounted setting.
Theorem 5 (Lower Bound for General DMDP). For any & (0,1/4), B 4 and S E 8N for any algorithm A Alg which is guaranteed return an e/3-optimal policy for any input discounted MDP with probability at least 3.
4. there exists a discounted MDP M (P, (Pr,7) 7) such that:
1. .M has S states and A actions.
2. M satisfies the bounded transient time assumption with parameter B.
3. A Alg requires Q B Blog(SA) samples per state-action pair on M.
(1-7)
The lower bounds of Ō from the weakly communicating setting still apply in the general setting. Together with Theorem they imply a Ô H+B
lower bound for general average-reward MDPs.
Figure demonstrates that, unlike the weakly communicating setting, discounted reduction with T- set in terms of only H cannot succeed for general MDPs. (Contrast with Lemma for the analogous theorem from [20) for weakly communicating MDPs.) We remedy this issue and lay the foundation for our matching upper bound by proving new reduction theorem in terms of H and B; in particular, measures how much farther ahead we must look in order to determine which closed communicating class will be reached. By Lemma 27 B < 4Tunif, although B is always finite unlike Tunif-
Theorem (Average-to-Discoun) Reduction for General MDP). Suppose (P,r) a general MDP, has an optimal bias function ht satisfying ||/2") span < H, and satisfies the bounded transient time assumption with parameter B. Fix E (0, 1) and set 7 any e-poottimll policy for the discounted MDP (Prr,7) then pa p" S 3 + 2 2BTH) el.
5 For any Ey [0, 1 if is
Proof highlights. Letting n, be the optimal policy for the 7diicountedd MDP, our first key observation that p² is constant within any irreducible closed recurrent block of the Markov chain Paz. essentially

---

because all states in this block must be reachable from each other with probability one (see Lemma
17 Leveraging the optimality of xny, this enables us to bound both |V," (s) - p* (s) and
(-)) by (ala")))))))) for any s which is recurrent under Th. which when combined demonstrate that the gain pTi(s) (s) of n. is near-optimal for its recurrent states. See Lemma 21 We
then leverage the bounded transient time assumption to guarantee that for transient 8, V2 (s) is dominated by the expected returns from recurrent states, since at most (BB) time is spent in transient states. We complete the proof of Theorem by combining these facts, as well as extending them to accommodate approximately optimal policies.
Next establish improved sample complexity for the discounted problem in the setting relevant to this reduction. This bound matches the lower bound in Theorem 5 up to log factors.
Theorem 7 (Sample Complexity of General DMDP). Suppose B + H S + and &
B H. There
B+H log exists constant C3 > O such that, for any 5 (0, 1), if C3 (1-7)8e2
SA (1-2)8e) ). then with
probability 1 8, the policy K output by Algorithm
satisfies
| - Vy v.p
S E.
Finally, we present our result for the sample complexity of general average-reward MDPs, matching the lower bound Theorem uup to log factors. We again use the reduction Algorithm 2 this time with the larger DMDP target accuracy E = B + H, leading discount factor of 7
H2
Theorem 8 (Sample Complexity of General AMDP). There exists constant C2 0 such that for any 6,8 E 1), if n 2 C₂ B+H
log
(AA(+HH) and we call Algorithm 2 with = B - H, then with
ea
dc
probability at least 8. the output policy 7* satisfies the elementwise inequality p px S =1.
Proof highlights. Similarly to Theorem 2 we seek to bound certain variance parameters, and this time it would suffice to bound the variance of the cumulative discounted reward starting from any state s like V Ei 7a R.] s <0( (. Such bound indeed holds for states that are recurrent under n., because p" (S.) will remain constant to /² (s) for all i, since, as mentioned above, /" is constant on closed irreducible recurrent blocks, and all (St)e2 will stay in the same block as s. Therefore, we can almost reuse our argument from the weakly communicating case. However, if is transient, it is easy see that V.= D bounded transient time assumption), to either an absorbing reward state or an absorbing reward state. Thus, when s is transient,
((+=)) )²) in general (even under the consider example where from we transition
instead of bounding | -= ). we directly work with the sharper variance parameter
e, (1 (1-r VV [V]]] which is also common to the analysis of DMDPs [2 (and
in these previous works is bounded in terms of | IE 7f RR Rall see Lemma 12 for this relationship). We instead develop a novel www-of-total-variance.. contribution of transient states this sharper variance parameter. See Lemma 26 details.
argument which limits the total
Conclusion
In this paper we obtained optimal sample complexities for weakly communicating and general average reward MDPs by improving the analysis of discounted MDPs, revealing quadratic rather than cubic dependence on the effective horizon for fixed instance. A limitation of our results (as well as of all previous results) is that the average-to-diset disccouteed reduction requires prior knowledge of parameters for optimal complexity, and an interesting open question is whether it is possible to remove this assumption. In conclusion, we believe our results shed greater light on the relationship between the discounted and average reward settings as well as the fundamental complexity of the discounted setting, and we hope that our technical developments can be useful in future work, such as leading efficient optimal algorithms in the online setting.

---

Acknowledgments and Disclosure of Funding
Chen and M. Zurek were supported in part by National Science Foundation CCF-2233152 and DMS-2023239.
References
[1] Alekh Agarwal, Sham Kakade, and Lin F. Yang. Model-Based Reinforcement Learning with Generative Model is Minimax Optimal, April 2020. arXiv:1906.0380 [cs, math, stat] version:
3.
[2] Mohammad Gheshlaghi Azar, Remi Munos, and Bert Kappen. the Sample Complexity of Reinforcement Learning with a Generative Model, June 2012. arXiv:1206.646 [cs, stat].
[3] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J. Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with generative model. Machine Learning. 91(3):325 349, June 2013.
[4] Peter L. Bartlett and Ambuj Tewari. REGAL: A Regularization based Algorithm for Reinforce- ment Learning in Weakly Communicating MDPs, May 2012. arXiv: 1rXiv:1205.2660 1205.2661.
[5] Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Near Optimal EiploratiionEEpllottaaaee in Non-Commun ConCunumunic Markov Decision Processes, March 2019. arXiv:1807.0233: [cs, stat].
[6] Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient Bias-Span- Constrained Exploration--Exlloittioni in Reinforcement Learning, July 2018. arXiv:1802.04020 [cs, stat].
[7] Ying Jin, Ramki Gummadi, Zhengyuan Zhou, and Jose Blanchet. Feasible SQS-Learning for Average Reward Reinforcement Learning. In Proceedings The 27th International Conference on Artificial Intelligence and Statistics, pages 1630-1638. PMLR, April 2024. ISSN: 2640-3498.
[8] Yujia Jin and Aaron Sidford. Efficiently Solving MDPs with Stochastic Mirror Descent, August 2020. arXiv:2008.122 12776.
[9] Yujia Jin and Aaron Sidford. Towards Tight Bounds on the Sample Complexity of Average- reward MDPs, June 2021. arXiv:2106.00446 [cs, math].
[10] Michael Kearns and Satinder Singh. Finite-Sampi Convergence Rates for Q-Learning and Indirect Algorithms. In Advances in Neural Information Processing Systems, volume 11. MIT Press, 1998.
[11] David Levin and Yuval Peres. Markov Chains and Mixing Times. American Mathematical Soc., October 2017.
[12] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with Generative Model. In Advances in Neural Information Processing Systems, volume 33, pages -18712 Curran Associates, Inc., 2020.
[13] Tianjiao Li. Feiyang Wu, and Guanghui Lan. Stochastic first-order methods for average-reward Markov decision processes, September 2024. arXiv:2205.05800
[14] Martin I.. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, August 2014.
[15] Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[16] Matthew Sobel. The variance of discounted Markov decision processes. Journal of Applied Probability, (9(4):794-802 December 1982. Publisher: Cambridge University Press.
10

---

[17] Jean Tarbouriech, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. A Provably Efficient Sample Collection Strategy for Reinforcement Learning, November 2021. arXiv:2007.06437 [cs, star].
[18] Martin J. Wainwright. High--Dimessoonal Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, edition, February 2019.
[19] Martin Wainwright. Variance-reduced SQS-learning minimax optimal, August 2019. arXiv:1906.0469 [cs, math, stat].
[20] Jinghan Wang. Mengdi Wang, and Lin Yang. Near Sample-Optimal Reduction- Policy Learning for Average Reward MDP, December 2022. arXiv:2212.00603 [cs].
[21] Shengbo Wang, Jose Blanchet, and Peter Glynn. Optimal Sample Complexity of Rein- forcement Learning for Mixing Discounted Markov Decision Processes, September 2023. arXiv:2302.07477.
[22] Shengbo Wang. Jose Blanchet, and Peter Glynn. Optimal Sample Complexity for Average Reward Markov Decision Processes, February 2024. arXiv:2310.08833.
[23] Chen-Ye Yu Wei, Mehdi Jafarnia-Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes, February 2020. arXiv:1910.07072 [cs, stat].
[24] Bin Yu. Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam, pages 423-435. Springer, 1997.
[25] Zihan Zhang and Xiangyang Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function, December 2019. arXiv:1906.05110 [cs, stat] version: 3.
[26] Zihan Zhang and Qiaomin Xic. Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes, June 2023. arXiv:2306.16394 [cs].

---

A Proofs for weakly communicating MDPs
In this section, provide the proofs for our main results in Section B weakly communicating MDPs. Before beginning. we note that given that H 2 1, we may assume that H is an integer by setting H [H], which only affects the sample complexity by constant multiple < relative the original parameter H. Let bo == su S [M denote the &oo operator norm of a matrix M. We record the standard and useful fact that (| y P 10 1 for any transition
I-7
probability matrix P', which follows from the Neumann series (1 - -P1)-1 120 (rP') and the elementary fact that [P"" (1 1o0 1.
A.1 Technical lemmas
First we formally state the main theorem from 20 which gives reduction from weakly communi- cating average-reward problems to discounted problems.
Lemma 9. Suppose (P,r) is an MDP which is weakly communicating and has optimal bias
function ht satisfying [ 1h""lspam H. Fix E (0, 1] and set =1 H. For any Ey E [0, I- if x is any E, opttimal policy for the discounted MDP (P,r, (P,r,7). 7). then
p" < (8+3 el. 0 -"
From here, we will first establish lemmas which are useful for proving Theorem 1 on discounted MDPs, and then we will apply the reduction approach of Lemma too prove Theorem 2 on average- reward MDPs. As mentioned in the introduction, a key technical component of our approach is to establish superior bounds on a certain instance-dependent variance quantity which replace a factor of
1 with a factor of H. Before reaching this step however, to make use of such bound, we require 1-y
an algorithm for discounted MDPs which enjoys variance-dependent guarantee.
The work [12 obtains bounds with variance dependence that suffice for our purposes. However, they do not directly present said variance-dependent bounds, so we must slightly repackage their arguments in the form we require.
Lemma 10. There exist absolute constants eı, 02 such that for any E (0, 1), if n z 1 log
SA SA_) ). (T-
then with probability least 8, after running Algorithm 1
we have
Ci log (1~7]0E
SA
[
Sm
VP
n
log
SA
[1
6 6
+ c17
+
(1 - 7)
and
0 log
SA
2 - Vi 7.P
sr\
(1-7)aE)
P )-1
P
V
n
(2)
SA log (T-2)65)
V
CiTY
+
(1-7)n
20
6
Proof. First we establish equation II.
The proof of 12 Lemma 1] shows that when n >
1662 2 log
48 =
with probability at least d have
1-7
4.5 log +fr
2 log
V,
S 471
7pp) VP.5
V2
20
n
(3)
45 log -=
2 log
|
+ y
(1 - 72
12

---

Now since
= - 7 mx
-> - - - -pppa -1--xPat
< (1 7 pPaz) -=
000000 1 11
5 8
$ 1-7 6'
we can obtain equation ① by triangle inequality (although we will choose the constant below).
Next establish equation
Using 12 Lemma 6], with probability least 1 we have that
36(1-1) Eō(1 - 7)
O (s, ~ (s)) - p a)
(4)
3S
185
uniformly over all s and all a # (s)) From this separation condition 4 the assumptions of [12
= in their notation) for the MDP with the perturbed reward 7. The Lemma 5] hold (with w = 1854 proof of (122 Lemma 5] shows that under the event holds, the conditions for [12] Lemma 2] are
satisfied (with, in their notation, 31 = 2 log
(T-7)/ S. T-q 2 log
32
(1-7)48PE log T
[.775 A
with additional failure probability S 6. The proof of [12 Lemma 2] then shows that, assuming
16a 2 log
5765 xa (1-7)107E
log I-7
we have
I-7
1 7.P
Vo.p
31 I 4
(I
y pR
Ri )-1
V
V
+
7/ (1-7)n
(5)
where we abbreviated B1 2oo
576.8 13t (1-7)'82E log I-7
for notational convenience.
We can again calculate that
Vy
a
V
(1
-P
-T 1 - -(I
:Pr;. -1 -I=-P=;;
00
< (1
Pp )-1
17 rrloo
000+00
2 8
E
7
6'
so 1
Vi
<
1
V Ri.
by triangle inequality, essentially giving
Finally, choose the constants e₁ and C2 we first note that 2 log log
ei log ((1-7)8)) for some absolute constant c,, and therefore also all our requirements on n are
fulfilled when n 2 1 log [I-7]0= - log [1-5)08) for another absolute constant d. Lastly we note that by the union bound the total failure probability is at most 36, so obtain failure probability of 5' we may set = 8//3 and absorb the additional constant when defining C1, C2 in terms of ci c2. and we also then increase a by factor of to absorb the factor of appearing in the first terms within (3) and (5).
Now can analyze the variance parameters
(1 (u:) VP. VVe.s
and
(1 (1- p .
VP
Vi
S.
which appear in the error bounds in Lemma 10 from (23 Lemma 2].
We begin by reproducing the following inequality
Lemma 11. In weakly communicating MDP, for all y [0. 1), it holds that
sup
1 p* < H.
13

---

The following relates the variance parameter of interest to another parameter, the variance of the total discounted rewards. This result essentially appears [ Lemma 4] (which was in turn inspired by
3 Lemma 8)), but since their result pertains to objects slightly different than Pr and Vr, [V7]] we provide the full argument for completeness.
Lemma 12. For any deterministic stationary policy nt, we have
~ 1 (p=))Pa)''v Vp. [
2
SV
4/4
Y
R
(=0
Proof. First we note the well-known variance Bellman equation (see for instance 16
Theorem ID::
R4
Vv
[ + P M Σ Y R
(6)
Now we can basically identically follow the argument of [1 Lemma 4]. The matrix (1 (1=)) has rows which are each probability distributions (are non-negative and sum to 1). Therefore, by Jensen's 's inequality and the concavity of the function + Vx, for each row E S we have
(1- Vp, V
$ V (1 - [
Using this fact we can calculate that, abbreviating = Vp, [V
- =7 171 7-7
- (1-
- - Vo
" 7 V /[(1 () -pxx)
7
VI - |1(1 -
In order to relate || - {P=) - w/110 to ||[1 -22 11011 in order to apply the variance Bellman equation (6). we calculate
[[ >P>) e x
|| (( (1-
-1- 72 11
= ||(T 7Px)
7(1 - 22Ps) -1ul|
[]((1 -))( (T
P.) Pb)
< [[(1 - () (1- - +7 91-2p)) -1ollo0
< (1 (1-~) 7) (0]=))(([--P)) - 100 (| - P 1 +7 |1(1 - -
< <1 (1+7)) ([]++)[([T-2))) ||T7-
2 [1 - -2²P)-
Combining these calculations with the variance Bellman equation (
we conclude that
1 I >(a Volloo ST -/ - P2,,) Lo
2
7F'
Σ Re
VI-7
1==
as desired.
The following is multi-step version of the variance Bellman equation, which we will later apply with T H but holds for arbitrary T.
Lemma 13. For any integer T Z for any deterministic stationary policy n, we have
T-
4E
R
= V
Σ 0=1
R R₂ + n2 (7((
+
Σ 7 R
1=0
14

---

and consequently
V
21=0 * Re + x" V
(ST) (S()
V
7"
R
72
Proof.
Fix a state so E S. Letting FT be the o-algebra generated by (Si,..., ST), we calculate that
2
x
0
V 80
?
Rs
ET 90
2' R4 (50(
t=0
20 X Re + ,, V1 (50) + Σ R Re (.r) )
2
E 90
2 R'R 7 V (Tx))))
E
E
Σ
7 R4 + 7 (Sr) (50)
Fr
t=0
t=T
B
Using the above shorthands and opening the square, we obtain
xC
R
ET
E
[12 B² + 2AB Fr]]
1=0
ET 9g
[A2 + E [B2[FT]
+ 2A [B]++]]
E 5g
A + ES, [B2]]
T-1 Σ
20
E 5D
Y'R + 7
V." (50)
+ +ES
7't R. 7 V (St)
1==
DC
Eg
7 + 2
Vi7 (80)
+ 7 B3
Σ 1=0
7" *Re V77(S))
T- >" R4 + VV
+ +22 To pTax
7 Re
where we used the tower property, the Markov property, and the fact that EY immediate from the definition of V.5). Since e. PT is probability distribution, it follows from
[B[Fr] 0 (which
Holder's inequality that |c] pT
Σ - xa Re]]
I V Ei RRllll Therefore, holds that
DC
VT
Σ
S T
Σ 7' + + VV
+22
V=
R2
00
and we can obtain the desired conclusion after rearranging terms.
We also need the following elemetary inequality.
Lemma 14. 7 2 1 - + for some integer T 2 1, then
1- 2T
11
2
T
T.
1 1-7
2
5
Proof. Fixing T 1, we have
2T
+
+
2T 21
15

---

which is increasing in 7 inf,
1- 721 - I-7
is attained y 7. Now allowing 7 > 1 to be
arbitrary, note 1-(1- 1-(1-#) = - (1 7)² ) so it suffices to show that (1
+) 27
2 1-
for all T 2 1. By computing the derivative, one finds that 1 1 (1 so
+) 27
is monotonically decreasing.
(1 (1-
7)
1
27
lim
(1
1 21
=
1
T T-0
T
6
We can now provide a bound on the variance of the total discounted rewards under Ty.
Lemma 15. Letting n. be the optimal policy for the weakly communicating discounted MDP (P, r. ?).
y 2 1 1
H' we have
Σ 7 1=
5 5
1
it suffices to bound the Proof. By using the multi-step variance Bellman equation in Lemma 13 quantity V Et R' + Hv²" (SH)
Fixing state 80 E S,
H
H
Σ
7 Rs + 7 MV, [V,
= -.
Σ
7 Rr + +7
1 p*
H
S 1
Σ
7 + 7
13- (5+(
1 p"
H-1
Vi" (SH) p*) |
< 2E
Σ
7 Re
+ 2E
7
1 - )
< 2H sup
V
< 4H
where in the final inequality we used Lemma obtain
Taking the maximum over all states s and combining
with Lemma 13
8c
4H2
R
<
11-221 2H
Combining this bound with the elementary inequality in Lemma
14 which can be rearranged to show
that 5 (1-YHH we complete the proof.
We also need to control the variance under 7, which requires additional steps. This is done the following lemma.
Lemma 16. We have
H2
V #
1. A
D.
y
7.P
R
< 15
00
H(1
-7)
1=0
16

---

Proof. In light of the multi-step variance Bellman equation in Lemma 13 it suffices to give a bound on
V T.P
- 3dt Rs
+ "V 2 (SH) We have for any state 8o that
T 80
RR, + 1 "
H
- >" R4 + VV (SH) - -7
V.
1 p*
Eeg
Rs + Vip
(( (SH) g4h 1 - ? p
1
R4 + ||
(Vi و
(SH)
(SH) (S)((s)) + + (vT
1 -
< 31E P
Σ 7 RR:
37 +3,2t
2 . (VTT*(SH) (Sn) V vi²) 2
)²
V (SH) -1- 10) )²
1
+ 2322tB
B
H-1 < 31b
Er'Ii T Re
+ + 1,
(v (S+)) 2 + +6.2H
V, 7, 12
+ 37 + B
(S+(
0r) -
(7)
where we have used triangle inequality and the incqualities (a + S 2a² + 26 and (a+b+c)3+ 3a² + 36² + 3c Now we bound each term of (7). First, we have
H-1
2
1+ (11 (4--)e)
2) )
s 6H² (1) 2
31E
Σ
(1 + +2) s 6H² S [f
where we had (1-7)e < 6H S 2/ because 1_ 2 H and S H. Clearly it holds that
By 24 ti. (V (Sn) - V (Sn)) S 6 v||155
B
By argument identical to those used in the proof of the error bounds in Lemma T0
we get
k.
VyJ
1 - 5
6'
so 2H
<
22
H²
since S H. Finally, using Lemma
we obtain
2 < ssp V (SH)
3 -
2,,
(SH) 1- x00))
1 p* S SHH
17

---

Using all these bounds in
we have
TH1
Σ
RR
+
7 H V (SH)
H-1
2
(Vi (SH)) 2
$ 3.Eap d
Σ 7 Re:
+ 67
2
+ 6,
1,
By
B
Viy 1i"((SH)
- p'
1
49
1
H² + 6 Vo ui Vi, 2
+3
6
6
12H
+6
Vy
7.
Vi 2
Finally, we use the elementwise inequality
V. 7.
9 p
V.
xp
1
Viy x
2
1
7PP
2 V.
18800
Vgl T.p
1
-
7.P
Vi+
1,
x
from which it follows that
Vy =
Vi
V3
x.
+
V V,7 ;
Combining
this with
g we conclude
H
Σ
RR + H
VT (SH)
< 12H2 + 12
Di
2
+ 12
D2
(9)
80
Now combining with Lemma 13 and then using Lemma 14 we have
Σ 0
72
Ri + HV
v 7. (SH)
R
1-224 2H
1=
00
H2
+
V
1 7.
-
1.
2
S 12
1
2
5
H2
V
Vi
2
+
Vi7
1
S 12
20
4
H(1 7)
H2
+
V9
V.
+
1.7
2
15
H(1
7)
as desired.
A.2 Proofs of [ 2
With the above lemmas we can complete the proof of Theorem I on discounted MDPs.
Proof of Theorem
Our approach will be utilize our variance bounds within the error bounds
from Lemma
10
We will find value for which guarantees that 7 V
and
R
8 V
are both s e/2, which guarantees that [ Rio
V,"" Se.
18

---

First we note that the conclusions of Lemma 10 require n 2 large enough that this holds.
c2_ log (1-7)68] l-
SA so we assume is
P 7 Starting with inequality t from Lemma and then applying our
Now we bound
variance bounds through Lemma and then Lemma 15
we have
7.
C1 log
SA
log
SA
[I-
[1-7]0E
$ sm
7
Px;))
Pr
+ C17
n
(1 - -7mm
6
Cj log (1-7)68)
SA
Σ
80
7 Rd
+ 617
SA log
(1-7)66
+
n
(1 - (m-
100
C1 log (1-7)6c
SA
2
5
H
C17
8AA log
(1-7]0E
Vi7
+
n
1
?
(1 - 7)m
80
6 log
(1-7)6E)
SA
H
log
(1-9)0E
E
10
+
C1
+
(1 7)2
(1
7)
6
where in the last inequality we used the facts that |55
1
and y S 1. Now if we assume
1-7
360c, (1-7)282 log (
H
844 ). we have
(1-7)ā5)
V 10
< 1
C1 log
(1-9)65
SA
10
H
SA log
(1-7)68
(1
7)2
(1 - 2
1
Ve²
+
1
+
E
6
H
6
< 2/2
due to the fact that E I H.
Next, to bound
1 F
starting from inequality 2 in Lemma 10 and then analogously
7.P
applying Lemma
12 and then Lemma
16
we obtain
Vi
Ci log
log
m\
[1->]0E
(I
Pr. )-1
V VP:.
V V
c17
(I-9)06)
+
E
(1 (1-1) 7)
6
C1 log
SA
log
SA
{T-7)6E)
2
(1-7)66)
|
8
Y.P
y R:
+ C17y
+
(1 - 7)
6
t=0
C log
(1-7)oe
SA
2
H2 +
Vy,p
+
x ==
15
1 1-7
H(1 (11
log
SA
[I-1)08
E
+ C17
1
(1 (1-7))
7)n
80
6'
19

---

Combining with the fact from above that
V
S
H.
2 as well as the facts that
V7.8" 10
S
T-y 7 S 1, and Va + S vā + vb, we have
1/2 V 1.533/0 2
c1 log
SA
H22 +
(1-7)6E
2
Vg
$
15
n
1
H(1 ((1-7) 7)
log
8.1
(1-9)0E
+ C1
(1
7)2
6
SA c1 log
(1-2)55
30
5 VV
v|
- H2 +
H(1 7)2
4
log
SA
(1-7)6E)
+ C1
(1
222
<) log
(1-1]05
SAA
30
5 H+ +
|,7300 -V
V 4
H(1 7)2
log
SA
(1- (1-7)0E)
+ C1
(1 - 7)
Rearranging terms gives
Ci log
SAA.
[1-7]56
30 V H(1 7)2
| ViJ
1-
n
SA ci log
SA log
(1-7)6e)
75H/2
(1-7)68)
+
+
(1 (1-7)3
2 1
Assuming n 2 120c1 (1 (1-7)202
log
SA (1-7)dc)
we have
SA C1 log (I-7)8e)
30
E2 7)2
1
18
n
H(1 - 7) 2
2
H
H(1 - 7)2
=1
2H
2 2
since
H. Also assuming n (75/2) 24 C1 \--
H
log
8A (I-7]ō8)
have similarly to before
that
SA Ci log (I-7]0E)
75H/2 (1-
log
[1-7]0E
SA
E
+ C1
+
12
(1-7)21
(1
6
1
(1
)22
H
(1 - 7)22
+
+
24
H
(1
7)2
24
H
(1 -
7)2
E
E
+
24
24
6
4'
V 2 x.
2
Combining these two calculations, we have
Vy.5
< = 50
1'
as desired.
D 2 7pp-
Since we have established that we can conclude that
7.p
Vi
5/. since also
ViT
ViJ
# 7.
<
1+
1 1 E1,
1oc
20

---

that is that Th is e-optimal for the discounted MDP (P) We finally note that all requirements the size of can be satisfied by requiring
SA
n C2
(1 ))22 log
()-E))
O2H
360cg H
(75/2)24²
SA
max
log
(1 222 2¹ (1 --)
(1 ?)?
(1 7)6E
C2
360c, H
(75/2)24P
SA
max
log
1- (1 - 2
(1 - 7)
(1 - 7/6E (1-7)6
where used that {I->)
H2
1-7 (since I-y 2 and H e).
(1-7)E"
We next use Theorem to prove Theorem on average-reward MDPs.
Proof of Theorem 2
Using Theorem T with target accuracy H and discount factor 7 1 12H obtain a H-optimal policy for the discounted MDP (P, r, 7) with probability at least as long as
SA
n n C2
log
(1 PH2
(1 - 7)65
H2
12H SA
= C2
log
H2 g2
de
which is satisfied when n 2 C
log
SAH 6=
for sufficiently large C1-
Applying Lemma (with error parameter
since we have chosen 7 =
5/12
). we have that
12
H H
x²* <
(8
3
el
12
as desired.
A.3 Proof of Theorem 3
Proof of Theorem 3 F, 2 1. First we define the instances My and MI, which have parameters
B and 6 which we will choose later, using Figure 2 Note that both MDPs, all states have only one action. The only difference is in the state transition distribution at state 1: For Mo this is ] Cat( 3. 1)) distribution and for Mi this is Cat( 1 + &, 2 e) distribution, where Cat(pi, P2) denotes the categorical distribution with event probabilities pı and p2 = 1 P1.
21

---

R
R
B
R = 0
Instance Mo
R =
R
B
0
R
Instance Mi
Figure 2: MDPs used in Theorem
Now we calculate the bias of instance M1. It is easy to check the stationary distribution is [I a + E 2: 5.0]. Therefore has optimal gain pa the optimal bias
11
+
+
2 + Now we claim that
2
a
- E/2 1
2 - E/2
2/2
+ 1)
We can check this by showing that ph" = O and that p' h² r Pht, where P is the transition matrix of the above MDP (again, note that each state has only one action, so there only one policy, and we use this policy to induce the markov chain with transition matrix P). First,
8 8
ph
=.
8
4
It is also easy to check the first three of the equality p01 hi Ph For the fourth row, we have
1
+ (1- B ht (4)
h²(4) + 2 B (())
B (i)(4)== -E E
2B 2
+ h²(4)= 7 (B+
Thus || - -
(Be+1). If we set 2T 1. we have ||4*| span T. e Also note that the calculation for h holds for any so the optimal bias span of Mo is [0, 5: 3: 0] T. and thus Mo has optimal bias span 1.
Finally, to distinguish between the two MDPs Mo and Mi, we must be able to determine the next-state distribution of state 1, that is, distinguish between the two hypotheses Q: = Cat(3 1 2) and Q2 = Cat(} + E, 2 - e). Given n i.i.d. observations from the transition distribution state this is a binary hypothesis testing problem between the product distributions Q and Q By Le
22

---

Cam's 's bound (24] the testing failure probability is lower bounded by
1
(1 - 10p 22 2
2
1
DKL
(9
2 2
1 1 2
(Kl(1))02)
where 1Q - Q2 lT and DKL(QT Q2) denote the total variation distance and Kullback- (KL)
divergence between Q and Q2. respectively, and the last two (in)equalities follow from Pinsker's incquality and tensorization of KL divergence. By direct caleulation, we have
DEL (Q1(Q1)2)) = log
+ log
2
1
23
2
1 2
28
+
log + +x) xx vx
2 1+ 2E
2
1 - 2
4
4E2
I &
E
4
Combining the last two equations, we see that the testing failure probability is at least 1 2 (1 //ne2 Thus, if we set e = Tyn the failure probability is at least 1
B Proofs for general MDPs
In this section, we provide the proofs for our main results in Section for general MDPs. Again, we can assume that H + is an integer, which only affects the sample complexity by a constant multiple 2.
First we develop more notation which will be useful in the setting of general MDPs. Recall we defined, for any policy n, that RD is the of states which are recurrent in the Markov chain Px. and T = S \ RD is the set of transient states. We now present standard decomposition of Markov chains [14, Appendix A]. For any policy æ, possibly after reordering states so that the recurrent states appear first (and are grouped into disjoint irreducible closed sets), we can decompose
X 0 Y=
P5 =
(10)
Z+
such that X, are probabilities of transitions between states which are recurrent under w, Yn are probabilities of transitions from 7 into RT, and Zz are probabilities of transitions between states within T Furthermore, supposing there are irreducible closed blocks within RT, X,, block- diagonal of the form
X
2
X,
X
The limiting matrix of the Markov chain induced by policy सr is defined as the matrix
T-1
p C-lim P
lim T-
Σ P 1=
T-300
T
poc stochastic matrix (all rows positive and sum 1) since S is finite. We also have P,P pbo = PrxP,. Additionally, p² pxera In terms of our decomposition, we have
X
p3o
(11)
oc
23

---

where
0
0
n,1
0
X
0
x22
X
T.kk
each X = Lx for some stochastic row vector xx and x = (1- (x- Also we
have (1 -,)=1 Ez= Z and Et= Y = (T Zx) ) Y has stochastic rows (each row is
probability distribution, that all entries are positive and sum 1).
With the same arrangement of states as within the above decomposition of P. 10 let
decompose V. into recurrent and transient states, and generally we use this same notation for any vector x E R we let x list the values of xs for recurrent x E RR, I contain Eg for E T and we assume the entire x: has been rearranged that [ z| T Note that the rearrangement of states depends on the policy π so this notation has potential for confusion applied to objects relating to multiple policies once, but the policy determining the rearrangement will always be clear from context in our arguments.
The main reason decompose Ps. into recurrent and transient states is the following key observation. Lemma 17. For any policy n, if 8,8 s' are in the same recurrent block of the Markov chain with transition matrix Px, then p² (8) = p" (5').
Proof. Define the history-dependent policy स which follows π until its history first contains s', after which point it follows π² Since (s() the optimal gain achievable starting by following any history-dependent policy [14). we have (*(s) 2 (*(s) = limy- 1 E IT- Rg (where E is defined in the natural way from the distribution over trajectories (Sp, .o....) where A ~ (So, Ao...., S.) and S2+1 P(- Se,, Ac)). Let T. inf 1: St s') be the hitting time of state s' and let Fr., be the stopped o-algebra (with respect to the filtration where for all nonnegative integers F, is the o-algebra generated by So, Ao. Se, At). Then
lim
R
lim
E
R
FTy
1=0
(=0
T-1
lim
R₁ + E
Σ Re FT, (=T,
t=0
T
lim
R₁ + ((T,TT))
T T
lim
7 E
Σ
Rs + g(T,To))
T-220
t=
lim 1
E (TT,
T 7-00
where (T,kk) = Ey
T- ΣrD
Rs and we used the tower property, -raasuaaauyy of
ITu-1 R2 the strong Markov property, and the definition of न. Now note that T/ < al- most surely since and s' are in the same recurrent block, and on the event {T's = k} for any natural number k. have that
k-1
lim T
(T
k) = lim T
T
By
Σ t=
R
= ps')s)
24

---

because we can bound
Ri
Ry
E T
R
T
T
and both sides converge to pa (s'). Therefore and also this random variable is bounded by 1, by the dominated convergence theorem we have
g(T,),)) converges almost surely to the constant p (s'),
T
lim - = p'((s) T-
lim T E (T. = E
Thus we have shown that (s()s 2 (s')). Since s and s' were arbitrary states in the same recurrent block we also have p (s') 2 p² (s), and thus p² (0()) p=s's as desired.
Lemma 18. For any state which is transient under policy if the MDP satisfies the bounded transient time assumption with parameter B, we have
Σ t=
Z
B.
Proof. Let inf(t: St E R²}. Notice that
|le_ Σ3
||
= (T > t). Therefore, we have
<
c Z
t=0
1=0
(T > t)
1=0
E [T)
< B,
where we used a well-known formula for the expectation of nonnegative-intege intghii--intger-vlulee valued random variables, and the bounded transient time assumption.
Lemma 19. Let s be transient state under Pa. Then
c, (I-
le_
Σ - (1-
e E 7 2
Proof. Using the decomposition of Pss can calculate for any integer > 1 that
Xt
0
pt =
El
Xt-k
Z
T.
Therefore, have
c. = e
pt
eg Σ Σl= - 1
6 -
Cs
-e - -
& 7
le
Ee 22 1, Σ,
xx
x E -
& T
Note that we are able to rearrange the order of the summation in the third equality because all summands are (elementwise) positive.
25

---

B.1 Proof of Theorem 6
Theorem 6 our result which helps reduce general average reward MDPs discounted MDPs, is proven straightforward consequence of the following sequence of lemmas, some of which will also be needed for the proof of our discounted MDP sample complexity bound Theorem
Lemma 20. We have
V
| 11
Proof. We begin by observing that π² satisties
p + 11 -x- + ha-
Therefore, it holds that
V = - -xxx) - -
= - -I- ) (p' ht- - -x=-h*)
7 1 p² + (I 77pp. (1 - (T- I..
Since P=+p" = p², we can calculate that
(1 ( = Σ
* pt pr.p"
p'p"
120
120
It also holds that
(1 (T- (T Pa.)= Σ
(I - Pa.)
120
120
120
Pr
[+1
p
(12)
120
and 7 (1 E1>0 72 -1. Therefore
(12 is the difference of two stochastic
matrices, and so it follows that
[| (Pa- - P1- h"
11 ||4*
span
Lemma 21. If m is optimal for the discounted MDP (P,r,)) and s is recurrent under Tiy then
1
Vg (s)
p (s)
$ ||h*|
span
and
(s)
x (s) < l llapan
These facts can be written as respectively.
Vi
$ | ||Allspam and
Vil
< ||/+
span
Proof. First note that is recurrent for the Markov chain Paş. then all states the support of e] Pa; are in the same recurrent block as state s, and p² is constant (and equal to p² within this recurrent block by Lemma 17 The (unmodified) Bellman equation states that
(s) + hs)ss)
max a:P a:P.np"=pp'M
Tsa + Psch
26

---

Since we established that e, Pr: = (s),,, all actions a in the support of 5z
|
s) satisfy
Paap" p² (s), and therefore
max + Psalt
a: PuP ppPost==pp(s)
2 Σ
ma(a 8) (rea + Poah")
atA
= e (Tn; + Pach')
Since this holds for all s E R"4, we can rearrange to obtain that
Ps
+ Xx: h²
Now we can follow an argument which is similar to that of Lemma 2]. We have
= 7 -rrra
= (1 - (xn;)) -Tag
$ (1 X==)==
1p+
X h*
using monotonicity of xx:) in the final inequality. Due to the observation above that for all E R all actions in the support of na s) satisfy Psap" p" (s), we have XxyP² p Therefore have
0
1 D-
(I (-
Σ
t=
For the second term, by using argument which is completely analogous to that used in Lemma 20 Combining these steps we obtain that
we have || Xxx) )1
h- - X h
S ||h*
I|
span
|| span 1.
To obtain lower bound, we can combine the optimality of o for the y-discuunted problem with Lemma to obtain the bound
spun 1.
Therefore we can conclude that
pz
|
span
For the second bound in the lemma statement, we first note that, as observed in 20).
poo
p
p m
p
1=0
Also, as discussed previously, if e R then c, Pr=p=* p" (s), so then we also have e._ prop' p² (s) (which can be seen directly from the definition of the limiting matrix Poo). Equivalently, eg (T - Pig ppp)p* = O. Using both of these two observations, we have
(s) V.
1
(s) = CT 1--Po Rx
p3o V
1
=e, (1 (V,
p*)
1
=c,
X
p²).
27

---

Therefore, we obtain
W4
[
x
V1 1
span
$ 2
S 2
|
I|sppn
using the first bound from the lemma statement in the final inequality.
Lemma 22. We have
B + || span
and
|
1
1 7 p";
S B + 2
1pan
Proof. Note that by combining with Lemma that
21
it suffices to prove for any transient state s E T
1
Vg (s)
s + ||14 span p (s)
1
and
(s)
pm (s)
B + 2 21hh" Maapn
Let be transient under o... Then starting by using Lemma 19 we can calculate
V3" (s) = E (1 PPp;)
20
Σ r'ee T2;Ta; +7 Σ
eee 1z Yn (1 - 7xxx)) -
T'es
T 1t T +7
Σ
e'e T 1z Y VI7
1=0
1=0
<
T 57
+
Σ
Ce T 2t Yn
Vi
(13)
1=0
1=0
By Lemma 18 we have that
C Σ t=
T
Pr:
Σ
T zt
Fr
< B.
Now we can obtain the two bounds in the lemma statement by bounding the second term of 13 in two different ways. For the first bound in the lemma statement, can use the first bound in Lemma
28

---

21 to calculate that
Σ
c
-z =i;
Vig
v
p + Σ
c 4z xx;
Vi7
0
1=0
1=0
1=1
Y
p* + Vi
1 pr
7 Y m
+
|1^0 I1span
span
X x pr + ||/* span
8
X
+ 1 span
1
0² || span
Cg Popp" + ||A*| IIspaan
span
< (s) + ||b" span
where we used the fact that X 7: p* = pr and then that e, P S (s). This gives an upper bound
of
V <
p² p*(ss + B + ||
1
Combining with the lower bound
V
(s)
V
(s)
p" p²(s) -1(A-1
1
span
we obtain that
|
< B + ||4"]] span
which is the first bound in the lemma statement.
29

---

To obtain the second bound in the lemma statement, using the second bound from Lemma 21 calculate for the second term in [3) that
we can
Σ 1=0
cx
Va
Cx
7
Ya
1
p
+
Σ
Cx
7
Y
V.7
7
1
1=0
1
Σ
8x
4 Y
p"
+
V7
p
1 pJ + +2 2212*1 span
Cg 4 " m3
T T Y
P + 2 |122 span
1
Ca 2az m
X m. + 2 11 span
Y xx Twz + =1" IIspan
1 C, r + 12 span
(s) + 2 ||
span
where in the second equality we used the fact that (
G.- T.. is probability distribution,
and in the final steps used the decomposition of p and the fact that p" mt
P
Therefore by combining these steps we obtain that
1
ViJ (s) S B + 2
||h]]| span
(s))))
Combining with the lower bound
1
(s)
V= (s)
2 1 pr (s) - -1hh span
pmi(s)
(s)
||hh
1 7
span
we obtain the desired bound
V, (s) 1 1- ?
pr (s)
S CB+ ++211111l,ppan
Lemma 23. If a. satisfies V 2 Vn 51, then
VT
3B +
||4*||
span + 6.
Proof. Similar to the proof of Lemmas 21 and 22 we will first establish bound for the states which are recurrent under т. Specifically, we will first show that if s is recurrent under æ we have
1
V (s)
(8)
2B + 2 2||h"| span + 5.
(14)
Letting s E RT, following steps which are similar to the proof of the second part of Lemma 21 wc have (x)
pT -I-
1
1
-e_ e - poo)
1- p*)
c. [I - p. (V,"
1
0²)+
teg (I P. (V - -
7
30

---

using the fact discussed in Lemma 21 that e. (I - pr))) )pt = 0 since is recurrent under т. Then by triangle inequality, we obtain
(s)() 1
p" (s)
$
e, (I pr))
7 p²)
+ (I-
)(7
17"
1
p'
V
Viji
1
span
span
2
12
1
0
s 2B + 2 |1^* 1/s0l + 6,
where we used the facts that ||-1lspan 2 and that V,," 2 V. 2 81.
Having established (1). we now extend to transient states using arguments similar to those for the
second bound of Lemma 22 Let be transient under π. Then starting by using Lemma 19 we can calculate
(s)(s e, (I - -ppp)
2
Σ Nee 7 +1
T Y - 7xxx) T
C
1=0
Σ t-0
N'e T ZZrr +1
%/g T V
1=1
C2
T Z T +
Σ
Cx
T T
V
1=0
1=0
6x
T z
| 00 +
Σ ex Y
V
t=0
1=0
<B+
T
Y
V
(15)
using the bounded transient time assumption via Lemma 18 in the final step. Then we can calculate
Σ 0
T
Y
V
VI
T Y
p +
Y
V
0
1
1=0
1=0
1
Z
pF +
VF
p
Y
p- +BB +2
|/1
11
span +
Y
pootx + + ||** Ispon + 8
T T 1
X T + 2B + 2 11 span + 5
1=0
1
ex Ty T. + +BB + +| span +
1
1
p0000 + 2B + 2 | 0g
span
+
7
1
(T(s) 2B + 2 11 sppan + 5,
7
31

---

where in the first equality we used the fact that (E c, 2;yx is probability distribution, in the second inequality we used the bound (14) and in the final steps used the decomposition of P and the fact that pz p
Therefore by combining this last bound with the bound (5) we have
V (+) S 3B + 2 |11111 span + p (8).
Combining with the lower bound
1 0- (s)
span - 1 p"(() -1141 spsnnn 6,
(s) - 82 V (s) -8
||
we conclude that
(T(())
p" (s) S SB 2 1span + 8
as desired.
Proof of Theorem 6 that
Suppose is opttmmll for the discounted MDP (P,r,7). We calculate
p" 2 V (3B + 2 2| Ilapan + +ey)
2 V (3B + 2 2| spun + +228g)
/"" (3B + || span + +22,
7
(3B | sppn
25y);
where in the first inequality we used Lemma 23 in the second inequality we used the fact that is e, -y-otiiall, in the third inequality we used the optimality of π for the discounted MDP, and in the final inequality we used Lemma 20 Therefore by mulitplying both sides by 1-% % we have that
D p B+H H
(3B + 13B+3|1" span + +2,) 2 2 36 +
Ey B
E.
H
B.2
Proof of Theorem 7 (Discounted MDP Bounds)
In this section, we provide main result on the sample complexity of general discounted MDPs. Our proof relies on three lemmas that provide bounds on relevant variance parameters. The first lemma controls the variance for πミ on recurrent states.
Lemma 24. Letting मं be the optimal policy for the discounted MDP (Prr,)) 2 B+H we have
32 B + H
max 7 e 4 (1 (P=;))
Vp
5 (1 - 7)
Proof.
First, using the decomposition
10
we can calculate for any R that
c (I-
-1
Vp
V
E. T(T
-7x=;)
Vp Vi
Es TTT(L 7xx3))
Vx=3
Vg
32

---

Also due to the decomposition, notice that set R is closed set for the Markov chain with transition matrix P.:. and furthermore when restricting to the entries corresponding this closed set we obtain the transition matrix x Therefore we can apply Lemma 12 to this subchain to obtain that
2
7 (I -T- xxxx)=
Vj
V
Σ 1=1
7
Ra
V
7
Abbreviating L B + H, can also then apply Lemma 13 to bound
EL-1
Re + +7 " (SL)
7
RR,
72
1=0
We can repeat a similar argument as within Lemma 13 to bound this term. Fixing an initial state so RT the key observation is that p² is constant on the recurrent block of Xx; containing 50, and therefore any state trajectory So = 80: S1, S2.... under the transition matrix Pxę will have (SL) = pa (so). Therefore for this fixed so we have
Σ 7 Rr + 7 V (St)
V
Σ 7 Rr + 7"
(5 - 1 p (so)
2
Egg
7' R4 + +
(5+(
1 pr (80)
< 2E
? R
+ 2E m
76 (1))
1
p² ($0) ) 2
1- 7
2F
Σ 7 R
+ 2E
Th
74h
(V
p² (Sz)
< 21 +2 sup
(s)
1- - p (s))
1
< 2 + 2H
< 4L
where we used Lemma 21 in the penultimate inequality, Applying this argument to all 8g E R we obtain
L-1
RR R₁ +
1=0
33

---

Therefore by combining with our initial bounds we have that
2
00
max 7 *ERT y c -1-=7pp:) )-1 Vp,
72t
R
Elso Pt + 7 (8
2
1
1-726 22
2
4L2
7,27.
2
16L2
5L(1 7)
32
L
5
(1 7)2
where in the penultimate inequality we used Lemma 14 bound I-qar S 1 (I-7)L
The next lemma controls the variance for 77 recurrent states.
Lemma 25. Letting Rt be the optimal policy for the discounted MDP (P,7,7). if7 21 we have
6+H
?
c
PR
V
Ppp.p
VTP
SER S.
V
V
B + H
15
29
1 7)2
B
H
1-7
Proof. Let L B + H. By the same arguments in the beginning of the proof of Lemma 24 have
max 7 [] P
# VT
2
80
7 RRR
SER ".
1
T
E rR, + y
VVV (SL)
2
1
1 1-
so again suffices to bound V
Fix 8o Ri.. Again, as observed in Lemma 24 p* is constant on the recurrent block of Xa; containing So, will have
ΣLz ft + V
(SL)
34

---

P'(S))= = pso) with probability one. Therefore (mostly following the steps of Lemma 16
/Rc + V R2n *( (St)
V P
Σ 7¹ Re + / 3 (SL) - -/ 1- p (50)
2
1
< 80 a
7 RR + V/ (St) - -/ 1 - y
pr (80)
1 1 7 p² (SL) (11))) 2
Eg m
7 R4 +g
S (vrD - V/ (S1)) + + (vr
+ +37 -322EE00 u.. (Vi (St) -V; (Sa)) 2
S 3E.0
? Ru
1 1 (
2
+ +
< 33E
Σ 3' Rs
+ 6- 2L Ri
E.0
(v, Vi -V²" (S.)) + +6,2
V8g Vi v 2
- 2
+ 3-,2 2
Vi (5)
(16)
using the inequalities (a + b c)² < 3a² + 312 + 3c. and (a + b)3 < 2a² + 2b..
Now we bound
each term of (16) analogously to the steps of Lemma 16 For the first term of (T6).
(1 (4-
( 2
Σ E
S {3(L (|rll + +2)² 6l2
<612 (1+
s 6L2
6)
6
where we had (1-r)e S El S 1/ because 1-1 2 I. and e S L. For the second term of (6))
(v 6,2LB.00 Z.p
(5((())
2 5 |, -
-V, v
V,5
I1,)
2
I 6
+
7.P
where we used (a (a+bb 6)2 < 2a² + 26 and the fact that | -v
<
V.7
7iP
1 v=-l1, which was shown in Lemma 16 For the third term of (66).
||
V
- Vi
7.0
2 <6
A. Vo
- Vi
2 56 6
(1-m)
E 2
= 6
EE
2
1 6
L
where the fact that Lemma 10 and the final inequality is due to the assumption that < L. For the fourth term of (1)).
Rip Visp
V
-
is identical to the arguments used in the proof of
2
3y 27 E
(SL)
p* (SL)
< 3
< 3LL2
1
using Lemma 22 for the second inequality. Using all these bounds in (16). we obtain
V 50
T--1 Σ t=0
+ Re + 7 V=55"(())
<
49
+3
1
+3
L²
+ 6 61
Vn $io
+
+11 7:p
V3 l²² 2
6
6
x
35

---

and so (since this holds for arbitrary So E R² we have
L-1 I
Vos P.P
Σ
St + 7 " (St)
- 6
1 + 6
(11//000
7.P
1,
5.0
+
v.5.1
1=
Therefore, combining with our initial arguments,
max 7 76 e1 ?Pat. Pri.p
V
7.p
"ER S.
yoipp
Ei=0 1-11
2e + 7 33. (SL)
2
1
7
1 1-726
2
68 6
L + 6 (1 [1 - 1/7 3
+
7.
V3
1
v 720
2
68
6
T.2 +
6 (||
Vi 3
+
7.p
V
vI 72t
2
68 I +
v
6 ()|
7.p
- 1y7bi0
+
V -
V3
1 Y
V 5 -7)1
Vy #
TM
+ 7. Vil
L
15
7.P
29
V
(1 7)2
L
1-7
where we used Lemma 14 to bound 1-720 1 (1-7)L-
The next lemma controls the variance on all states. Lemma 26. Under the settings of Lemmas 24 and 25
we have
7 (1 {Px:)
Vp V
4
B B+ H
(1 71
8
and
Vy T.P
1 7.P
V
B + H
15
7.P
7 (I :Ps.
V.'VVran V
Vr
8 V (1 7)
B H H
Proof. First we establish the first bound in the lemma statement, As we have already bounded the entries corresponding to the recurrent states of n. by Lemma 24 it remains to bound the transient states. Let s E T be an arbitrary transient state. Using Lemma we have
cT Pr; ) 11
Ve,g
[i
7ex
k 7 Yy: (T 7Xx;) -1
''v Vr
ViJi
R=1
+ ye
T Σ
7²
Zt
W
Pag
Vi
(17)
0=0
36

---

Now we bound each of the terms in (7) For the first term, we can calculate
k 7k (x
S ycg
T
Z
m (I -xxx;)
km
80
? (1 (1-))x)) ) 1 VPrg Vi
E2
k=1
32 B + H
5 (1 7)²
where we used the fact that T
Σ
00
x3 is probability distribution and Lemma 24
R=
For the second term of (7 we have
00
00
e/e²
T Z
yCs
P 3
Vi
65
$ Z
Σ
Vra; Vi"
T oc
7t $zz 1=
t=0
t=0
t=
0
Meea T7/2
59
8
1 3
Σ 0=
Vpr: Vi3
0=
C2
2t=0 7" ZZZz
DC
6
T
Z #2
2
eee T TZ, xx
P
7
(18)
t=0
f=0
Er xe z
where we used Jensen's inequality since x ++ x is concave and
is a probability
Στ- 2
distribution (all entries of this row vector are positive and they sum to 1 due to our normalization).
Now we bound each factor in (88. Using Lemma [8] we have
e
Z
S
ZL
SBB
1
For the second factor in 18 we have
Σ t=
re
ce
Z V
Pet
T 2
Pmg
t=0
00
+ 6g
b--1 'Yn: (I
-VVP.t Pay
k=1
= =c! (I p Pr:
where the equality step is due to Lemma 19 Now we can apply two steps which are used within
Lemma 12 to obtain the desired bound on this term. Abbreviating v Vp
it is shown
within Lemma 12 that
7² 7Pa;
w/1 s 22
22
:=
Σ
2 (1-7)2
t==
(where the final inequality is because the total discounted return is within [0, can bound the second factor in (88 as
Therefore we
2
22 1 7
ees es
7z Vr,g
S V
(1
7)2
t=
37

---

Combining all of these bounds back into 17
we have
-Pp=))
/ Ve..
[57 S
32 B H
+ +VB v2
7)
7-7
B B+H
(1 71-
Thus we have established the first inequality from the lemma statement. For the second inequality, the argument is entirely analogous, except that we use Lemma 25 of Lemma 24 and also in the MDP with the perturbed reward we have the bound
instead
|
2 1-1)
||||| + +5²
2
Σ
Rs
S 20
y
1
( 11(11-))
2
1
7 2
(1 7)2
7)2
where we used the fact that [1~b]e obtain the bound
I 6 because
B and S B + H. Thus
6(B+H)
7
P2;
)
V P=t.0
B + H
15 B+H
1
7.P
+
7.P
V,
5 29
(1 7)
1 - 7
VB 7V2
6(1 - 7)
B H
15
T p 7.P
Vj 7.P
+
1
V, 7
(1 7)
B
H
1-7 7
This completes the proof of the lemma.
We now ready prove Theorem on the sample complexity of general discounted MDPs.
Proof of Theorem 7 To prove Theorem 7 we will combine our bounds of the variance parameters
Lemma 26 with Lemma TO First, starting with (T) from Lemma 10 and combining with the first bound from Lemma 26 we have that there exist absolute constants C1 C2 such that for any 8 E (0, 1),
38

---

SA (1->)85) ) then with probability least 1 8
n oz log I-y
ci log
SA
| - 1,-1110 s
(T-1)
(T -1-77 (T:pp=;) VP
SA log
(1-7)6E)
+ c17
+
(1 - 7)
log
(1-7)6E
9A
B+H
log
(T13)85
SA
Vi7
T
n
(1 7)3
(1-7)m
6
log
9A
8A log
(1-7)6c
B+ H (1-
(1-7)66
C1
n
(1
2
g²
16-62 62 B+H
2'
where the penultimate inequality is under the assumption that 2 16 22---- 61 and the final inequality makes use of the fact that E < B + H. Next, still using Lemma TO under the same event, we also have
-(-7)
B+H
log
(1-
84
V.
V
T.P
SA C1 log
S 57\
(1-7)AE)
(I
PR:
)
Pa
7.P
#
SA log
(1-9)55
C177
V
(1
7)
6
SA C1 log
(1-7)or)
B+H (1-
15
VS2 vM
+
ViJ
<
81
n
B H
7
log
SA
(I-7)88
+ 617
V 7 3.
(1 - 7)n
6
C1 log
(I-9)00e
SA
B
15
T V S.
+ + H)/2
S
81
n
(1 7)2
B
7
SA log
(1 (1-7)55)
1
E
+ Ci
+
(1 - 7)
1
6
using the second inequality from Lemma 26 for the second inequality, and then we use the fact
that
Vi P
< G 1- which was argued in Lemma 26. as well as the fact from above that
39

---

P3 - |o
Se/2 (B+ + H)/2. After rearranging, we obtain that
01 log
[I-y)0E
15 1
V9
7:P
C1 log
(I-7)0E
SA
B H (1 7)
15 (B+H)/2
log
(1-77)02
SA
e
C1
71
B + H 1-7
(1 - 71
6 6
Cj log
SA
log
SA
(I-7)00
B + H
(I-9]08
101
+ C1
(19)
n
(1 7)3
(1 - 7)n
6
nn 2 62.
10
ci
B+H (2(1->) 7)
log
(1-1)68)
SA
then the RHS of 19
is bounded by
E
7 c²
1
1
:/
1
+
S
S 0.4s
6
6
B + H 62 102
62
10a
using the assumption that s < B + Under the same condition on n, we also have that
C1 log
SA
(1-
15
1
|
Vy #7.0
11
B + H - ?
62
15
Vi 7.0
(B + H)²
6 102
7.p
15 62
Vy 7.
10a
# Vi
2
0.9
TMP
where again we used the assumption that & S B + H. Combining these two bounds with the inequality 19.. we obtain that
0.9
Vi x
< 0.4s
which implies that
0.4
8
7.
<
0.9
2
Since we have established that
|
Va
and that
V
Vy T.
S S. since also
D 2 7.P
p 7.Pa we can conclude that
D 7.P
1 1
V
1 15
that is that Ri is opttimll.
Finally, we check that all of our conditions on can be satisfied if
n 2 max 60 10 c1
B+H
62 16c1
B + H
C2
log
SA
c² 7)2
7)2
(1 7)0s
and since
> B + H and B + H 2 E, we have
B+H
(B++H) (1(17)
1
so the above is
T-
guaranteed we set C3- = max max(62 (62. 10 c0 62) and require n Ca
log
SA
[I-
40

---

B.3 Proof of Theorem 8 (General Average-Reward MDP Bounds)
In this section, we prove our main result on the sample complexity general average-reward MDPs.
Proof of Theorem g
We can combine our bound for discounted MDPs, Theorem 7 with our reduction
from rewaaee-rwward MDPs to discounted MDPs, Theorem 6
Using Theorem with target accuracy + H and discount factor 7 1 T2(B+H) we obtain
(B Ho-ttti policy for the discounted MDP (P,r,7) 7) with probability least 1 long
B + H
SA
n 2 C3 (1 - ( - H)²
log
(1 - 7)6E
B +
(B + H)²
12(B + H) SA
= C2
log
(B H)²
82
de
which is satisfied when n 2 C4
B-H g²
log
SA(B+H) DE
for sufficiently large C4.
Applying Theorem 6 (with error parameter 12
we obtain
B H
p
3
g1
B
B+H
12
as desired.
B.4 Proof of Theorems
4 and
(Lower Bounds)
In this section, we prove our minimax lower bounds on the sample complexity of general average- reward MDPs (Theorem 4 and discounted MDPs (Theorem 5
Proof of Theorem First consider the MDP instances Ma indexed by a" E {I...., A} shown in Figure 3 In all instances, states 2, 3 and are absorbing states, and state is transient state. State has actions and is the only state with multiple actions. At state 1, taking action a = will take the agent to state 4 deterministically: taking action will take the agent back to state 1 with probability P(1 = 1 1 to state with probability P(2 1, 2), and to state 3 with probability T.
1,3 = 2)] P(2) 1, 2). The instances differ only in the values of P(2[1, and P(3 a). which are shown in Figure 3 along with the reward R for each state-action pair.
For the MDP instance M1, the optimal policy is taking action = 1 at state 1, leading to an average reward 1/2; taking any other action leads to sub-optimal average reward of 1-2e. Similarly, for 2
the instance Ma with a* E (2....,4) A}. the optimal action is a = a* with average reward 1+2- the action a = 1 has average reward 1, and all other actions have average reward 2 By direct calculation, we find that the span of the optimal policy || taking any action a of the agent will stay in state for B steps expectation before transitioning to state 2 or 3, so the bounded transient time is satisfied with parameter B.
2
in all instances. Moreover, by
We next define (A-1)S/4 master MDPs Ma indexed by E (1,..., .,. S/4) and a* E (2..... A} as follows. Each master MDP M. . has S/4 copies sub-MDPs such that the s*th sub-MDP is equal to Ma and all other sub-MDPs
equal M1. We rename the states that the states of the sth sub-MDP has states 4s + 1, 4s + 2, 4s + 3, 4s + 4 corresponding to states 1, 2, 4 of the instances shown in Figure Note each of these master MDPs has S states and A actions, satisfies the bounded transient time property with parameter B, and has the span of the bias of its Blackwell optimal policy equal to Note that for given policy и be e/3-average optimal in master MDP M, it must take action a* in state 4s* 1 with probability at least 2 /3, and it must take action 1 in states 4s + for E (1, (1,...,5/44 5/43 \
{s*} with probability at least 2/3.
Thus, for an algorithm Alg to output an e/3-average optimal policy it must identify the master MDP instance Ma+.ar (equivalently, the values of s* and a²) in the sense that there must be exactly one state 48 + where an action a * 1 taken with probability 2 2/3. Therefore it suffices to lower bound the failure probability of any algorithm Alg for this (A 1)8/ 4-way testing problem. By
41

---

R 1/2
1, 1/2
P(2 1,0) 1-2x
# (2.
A). R= =
2 e R
3 R=0
P(1 1,4) -1
P(3 1,0)
1i2 22
Instance M1
D R=1/2
L, 1/2
P(2 1,a) = 1-26
(2....,A//11 A))(a'), R= 26)/2
R
P3 1,a)
b R=0
P(1 1.0) = 1
a= R 2:)/
(2 11,²)
142 2B
P(1 (111)) =1 -
P(3 1,a') 1-26
Instance Mar for at E (2,...,
Figure 3: MDP Instances Used in the Proof Lower Bound in Theorem
construction, for any two distinct index pairs (si, at) and az),az), the master MDPs Majjaj and Mas.ag differ only in the state-action pairs (4sj, at) and (4s3, az), and we have
2s 1 1 28
Pm.ging ( [|4ss,a0 ai) = Cat
1
=: Q1
B'
2B
2B
1 25
28
Pmi.g (: |s4 ) = Cat 1
=: Q2,
B' 2B
2B
where Cat(pI, Cat(pI.P2.21) Pa) denotes the categorical distribution with event probabilities p: 's (and vice versa for the distributions of the state action pair (4sğ, az)).
Now we use Fano's method [88 lower bound this failure probability. Choose an index J uniformly at random from the set J == {1...., S/4} .2. A} and suppose that we draw iid samples X = x (X,,..., X.,) from the master MDP My; note that under the generative model, each random variable X, represents an (S by- transition matrix with exactly one nonzero entry in each row. Letting I(J; denote the mutual information between J and X, Fano's inequality yields that the
failure probability lower bounded by
I(J; + log 2 1og((AA1)5/4)
42

---

We can calculate using the fact that the P.'s are i.i.d., the chain rule of mutual information, and the form of the construction that
X(::)) (I)
DKL. (PM.g.1 PM.g.ng)
S n
max (s1 (+5.aa)))
(s] (51-4[)7(52,9)
mD<r Q2) DRi. (Q2 Q1)).
By direct calculation, we have
25
25
1
DxI (Q)
log
log 2e
2B
+
2e
2B
2g
4
25
4
log(1 + Sx,
2B
1 28
2B
- 28
16
B(1 + 21 2s)
32s²
e 1
B
Also note that DRr. (Q2(11) =
in this case. Therefore the failure probability least
I(J; Pm) log 2
64c llogg 2
log((A - 1)5/4) log (A 1)5/4)
64c²
1
2 log( - 1)5/4)
where in the second inequality we assumed A and S are at least sufficiently large constant, For the above RHS to be smaller than 1/4, we therefore require n 2 ? B ())
Proof of Theorem The desired DMDP lower bound follows from combining our AMDP lower bound Theorem with the average-to-discomm reduction in Theorem 0
B.5 Relationship between transient time and mixing time
Lemma 27. In any uniformly mixing MDP, we have B < 4Taulf.
Proof. Fix a deterministic stationary policy т. Notice that since all states in the support of the stationary distribution Vn are recurrent, for any E S we have
Ts (Se is transient)
= Σ
pa (S, = 8')
Σ
p (S, = =s)+ Σ
P. (St =s) (s()l)
R'RR
.x (S, = 8') v² (s')l
E'S
1
< 2 max ||o_ pt - v=1 ||
$E 2
< 2 2 [[/Tumrr]
where the final inequality uses standard properties of mixing 11 Chapter 4]. Now define T T= inf(l: S, RD J. Then, using standard formula for the expectation of maanegative-intege--abbie random
43

---

variables, we have for any E S that
1
(T 1()
P. (Se is transient)
1=0
2 Σ
2
Lt/Fumit]
(=0
00
Tunif 2 t
t=
4rmnff-
Since this bound holds for all E 8 and all deterministic stationary policies n. we conclude that S 4Tunif
44

---

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: All claims made the abstract and introduction match the theoretical results provided in the main results Sections 3 and
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 the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The conclusion (Section mentions the main limitation, of the necessity of knowledge of H/B for the optimal average-reward complexity results to hold, and this point
is elaborated upon in Section 3
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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in 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
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
45

---

Answer: [Yes]
Justification: All assumptions are provided with their respective theorems and within the problem setup Section 2 and formal proofs of all results provided in Appendices A and
B
Guidelines:
The answer NA means that the paper does 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 in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include 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 be 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 is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
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 a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to 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 reprodueibility may be tricky in some cases, in which authors are welcome to 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 (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
46

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /otee//guudddeeeedSuuubbmiibii ssionPolicy) for more details.
The authors should provide instructions on 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 omitted from the script and why.
At submission time, 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
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: The paper does not include 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, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
47

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but 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 or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in 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 to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include 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 rums 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 make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics
Answer: [Yes]
Justification: Our research does involve any human subjects or datasets, and as foundational theoretical paper it does not have any direct potentially harmful societal consequences.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification; Our work is foundational research on the sample complexity of average-reward and discounted MDPs, and thus is not directly tied to any negative applications.
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 why the paper does not address societal impact.
48

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not provide any data nor models.
Guidelines:
The answer NA means that the paper poses no 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 to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification:
The paper does not use any code, model, nor data assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
49

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
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:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part 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 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. Crowdsoureing 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:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 the main paper.
According the NeurIPS Code of Ethics, 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 NeurIPS 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.
50


Reviews:
[{"review_id": "vJEO68yWK2", "reviewer": "Reviewer_6ECs", "summary": "The paper resolves the open problem of designing an algorithm for the generative tabular average reward setting for weakly communicating MDPs that achieves optimal span-dependent sample complexity with known span. This is done by an original observation that is concerned with discounted MDPs: Existing sample complexity bounds for the discounted setting are refined and the result is obtained from this refinement by reducing the average reward setting to the discounted setting, just like it was done in previous works. A second result is to give the first sample complexity results for general MDPs; with matching lower and upper bounds.", "questions": "n.a.", "limitations": "n.a.", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Solving a major open problem based on an interesting insight: This is a breakthrough paper.", "weaknesses": "None", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review.", "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": "askCfOWK42", "reviewer": "Reviewer_i8Mw", "summary": "This paper presents an algorithm with optimal sample complexity in general average reward MDPs.", "questions": "1. The authors discuss the fact that H cannot estimated while D can be. However they do not mention anything about B ?\nMy first guess would be that B cannot be estimated either because it looks discontinuous in the paramaters on the MDP.\n\n2. Maybe I am mistaken but I did not see a proper definition of the transient time B, used in the statement of Theorems 4 and 5.", "limitations": "Again, the generative model looks like a strong assumptions.\n\nThe lack of numerical experiments is classical in this domain. It seems that MDPs of size 10 are already impossible to learn, which limits strongly the practical aspect of this type of algorithms. Can the authors comment on this?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The algorithm proposed is sample optimal for the general class of MDPs (possibly  multichain) that are much harder to learn than uni-chain or ergodic MDPs. \nIt also introduces a new parameter, the transient time that helps one assess  the sample complexity for multi-chain MDPs.", "weaknesses": "Although the following papers only appear recently on Arxiv ( i am not an author of either of them)\nI think they should be mentioned because they answer some questions raised in the paper.\n\nFirst XXBoone shows that regret bounds  using H are possible without prior knowledge of H, disproving the supposed conejcture\n in papers [5,4,25] cited in this submission. Actually, the same paper answers the point about the computational eficiency of the optimal algorithm.\n\nSecond, the results of the current submission should be compared to XXKauffman which seems to solve the same problem.\n\nIn the ergodic case, i agree that navigating and generative models are almost similar but in the general case, the generative model looks very strong.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- We would like to call attention to our results for weakly-communicating MDPs, which we believe represent a major strength of our work as they resolve the longstanding problem of the sample complexity of average-reward MDPs (Theorem 2) with an interesting insight on the complexity of discounted MDPs (Theorem 1). \n- We note that both of the referenced preprints appeared on arXiv after the NeurIPS submission deadline, so they should not contribute negatively to the evaluation of our submission. Still, we are happy to discuss their relation to our work while attempting to maintain our own anonymity.\n  - The preprint by Kaufmann et al. is directly inspired by a preprint version of the present submission. They also provide evidence that the optimal bias span $\\mathsf{H}$ is hard to estimate, although their lower bound instances require randomized rewards unlike our Theorem 3. As suggested by our paper starting at line 276, the diameter $D$ is estimable and upper bounds $\\mathsf{H}$, so a diameter estimation procedure can be used to remove the need for knowledge of $\\mathsf{H}$. Kaufmann et al. formalize this observation and combine an existing algorithm for the generative model which requires knowledge of $\\mathsf{H}$ with a diameter estimation procedure from prior work to get a diameter-based sample complexity in the generative model setting, and they also combine a sample collection procedure for the navigating setting (also from prior work) to be able to apply the existing generative model algorithm to the navigating setting.\n  - The preprint by Boone et al. claims to obtain an optimal span-based regret bound in the online setting without prior knowledge of $\\mathsf{H}$. We are unable to verify their result but we agree it would be highly surprising in light of past conjectures. We note that their result does not imply any sample complexity bounds for our setting, as unlike the episodic finite horizon setting, there is no known regret-to-PAC conversion. In fact, the mentioned paper by Kaufmann et al. provides discussion suggesting such a conversion is impossible, and it also claims to show that no online algorithm with or without knowledge of $\\mathsf{H}$ can identify an $\\varepsilon$-gain-optimal policy with the $\\widetilde{O}(SA\\mathsf{H}/\\varepsilon^2)$ complexity achieved by our algorithm. Regarding simplicity and efficiency, while their algorithm is efficient, it is still very complicated and apparently does not achieve the optimal regret $\\widetilde{O}(\\sqrt{SAHT})$ until at least $T \\geq \\Omega(S^{40}A^{20}H^{10})$. Hence, we still find it surprising that (in our different setting), there exists an optimal algorithm, our Theorem 2, which achieves the optimal complexity $\\widetilde{O}(SA \\mathsf{H}/\\varepsilon^2)$ for all $\\varepsilon < 1$ and is highly simple.\n- We agree that generative model access can be a strong assumption, but we believe that it plays a fundamental theoretical role and its study can lead to algorithms for more general settings. In particular, even when the MDP is not ergodic, algorithms for the navigating setting can reduce to the generative model, which is the approach taken in the mentioned paper by Kaufmann et al., who reduce to the model-based algorithm that we use. Additionally, as discussed starting at line 49, we believe the generative model is particularly natural for studying general/multichain MDPs.\n- The definition of the bounded transient time parameter $\\mathsf{B}$ appears in Section 2 (Problem setup and preliminaries), line 176.\nRegarding the estimation of the bounded transient time parameter $\\mathsf{B}$, we believe that, as you suggest, this parameter may be difficult to estimate. While we believe your point about the discontinuity of $\\mathsf{B}$ is correct, we believe that the discontinuity may not actually be the main obstacle. While generally $\\widehat{P} \\to P$ does not imply $\\mathsf{B}(\\widehat{P}) \\to \\mathsf{B}(P)$, the natural sampling model also ensures that the support of $\\widehat{P}$ is contained within that of $P$ (and eventually their supports must be equal), and with this additional constraint (on the sequence of empirical transition matrices) we should have $\\mathsf{B}(\\widehat{P}) \\to \\mathsf{B}(P)$. However, we are unsure how to compute the function $\\mathsf{B}(\\widehat{P})$ without enumerating exponentially many policies. Consequently we believe $\\mathsf{B}$ can only be tractably bounded for small MDPs or when there is some prior knowledge/structure in the MDP.\n- Regarding your comment that MDPs of size 10 are impossible to learn, we are not sure which measure of size you refer to. For MDPs with $S \\cdot A = 10$, our algorithms would be highly practical. For MDPs with a number of states on the order of $2^{10}$, we agree that tabular algorithms such as ours would not be practical, and instead function approximation would be needed. We hope that analogous to episodic MDPs, our study of the average-reward tabular setting can lead towards algorithms using function approximation methods.", "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": "QSFm3p93XJ", "reviewer": "Reviewer_AFus", "summary": "This work obtains the first minimax optimal sample complexity bound of weakly communicating and general average reward MDPs, without uniform mixing assumption, by introducing new transient time parameter and obtaining tighter minimax optimal sample complexity bound for discounted MDP.", "questions": "(1) You may change the following citation which has been accepted by ICLR 2024. \n\n[21] Shengbo Wang, Jose Blanchet, and Peter Glynn. Optimal Sample Complexity for Average Reward Markov Decision Processes, October 2023.\n\nSome other citations like [13] lack location (ArXiv, conference, journal, etc.). \n\n(2) In lines 152-153 about the definition of Blackwell-optimal 154 policy, do you mean for all $\\gamma\\in[\\overline{\\gamma},1)$ or $\\gamma\\in[\\overline{\\gamma},1]$? Does $V_{\\gamma}^{\\pi^*}\\ge V_{\\gamma}^{\\pi}$ mean $V_{\\gamma}^{\\pi^*}(s)\\ge V_{\\gamma}^{\\pi}(s), \\forall s$?\n\n(3) In lines 155-156, what does $P_{sa}\\rho^*$ mean? Does $\\rho^*(s)\\ge P_{\\pi}\\rho^*$ mean $\\rho^*(s)\\ge (P_{\\pi}\\rho^*)(s):=\\sum_{s\\in\\mathcal{S}}P_{\\pi}(s,s')\\rho^*(s')$? The meaning of $\\rho^*(s)\\ge {\\rm a~vector}$ is not clear to me.\n\n(4) In Theorem 2, the accuracy $\\overline{\\epsilon}=H$ for DMDP is not arbitrarily small. Why can the accuracy for AMDP be arbitrarily small $\\epsilon$?", "limitations": "I agree with the following two statements made in the checklist: \n\n(1) Limitations: \"The conclusion (Section 5) mentions the main limitation, of the necessity of knowledge of H/B for the optimal average-reward complexity results to hold, and this point is elaborated upon in Section 3.\" \n\n(2) Negative societal impact: \"Our work is foundational research on the sample complexity of average-reward and discounted MDPs, and thus is not directly tied to any negative applications.\"", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This theoretical work provides comprehensive lit review. I did not check the proof, but the theoretical results look reasonable and strong based on my knowledge about discounted MDP theory. The presentation is clear.", "weaknesses": "A few points are to be clarified as shown in the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. Thank you for making us aware of the updated citation. We will fix this and the other citations which lack locations.\n2. Our definition of Blackwell-optimal policies is standard and matches that of Puterman [14, Chapter 10]. We must use $\\gamma \\in [\\overline{\\gamma}, 1)$ since the discount factor $\\gamma$ must be strictly less than $1$ (the discounted value function is not defined for $\\gamma = 1$). You are correct that the statement $V_\\gamma^{\\pi^\\star} \\geq V_\\gamma^{\\pi}$ means that $V_\\gamma^{\\pi^\\star}(s) \\geq V_\\gamma^{\\pi}(s)$ for all states $s$.\n3. Thank you for catching this issue. $P_{sa} \\rho^\\star = \\sum_{s’} P(s’\\mid s,a) \\rho^\\star(s’)$, as we treat $P_{sa}$ as a row vector. You are correct that there should not be an index in the second definition, which should be written $\\rho^\\star \\geq P_\\pi \\rho^\\star$ (and understood to hold in an elementwise sense), in order for it to be equivalent to the first definition that $\\rho^\\star(s) \\geq \\max_{a \\in \\mathcal{A}} P_{sa} \\rho^\\star$. We will fix this typo.\n4. We agree this is an interesting point. Mathematically, from the reduction from (weakly-communicating) average-reward MDPs to discounted MDPs [20, Proof of Theorem 1], we are guaranteed that if policy $\\pi$ is $\\overline{\\varepsilon}$-optimal for DMDP (meaning $V^\\pi_\\gamma \\geq V_\\gamma^\\star - \\overline{\\varepsilon} \\mathbf{1}\\$), then $\\pi$ has gain at least $\\rho^\\star - C(1-\\gamma)(\\mathsf{H} + \\overline{\\varepsilon})$ for an absolute constant $C$. Note that $(1-\\gamma)$ is the inverse of the effective horizon so this bound goes to $0$ as the effective horizon increases, which is exactly what is done within Theorem 2 as we set the effective horizon to be like $C’ \\frac{\\mathsf{H}}{\\varepsilon}$ (where $\\varepsilon$ is the target accuracy).", "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": "fxb8Jt3bbM", "reviewer": "Reviewer_hsZR", "summary": "This paper presents a model-based reinforcement learning algorithm for tabular MDPs with the average reward criteria. The authors assume a generative model (each state-action pairs can be simulated) and studies learning algorithm that sample each state-action pairs n times.  In the weakly communicating setting, the authors provides the first algorithm that achieves the minimax lower-bound to find an \\varepsilon-policy. The authors study also the more general case of multi-chain MDPs for which the authors introduce a parameter B (time to visite a recurrent-state) and propose both an analysis of a minimax lower bound and an algorithm that achieves this bound.", "questions": "Are there any novelty in the algorithmic part or is it just the analysis that is new?\n\nThe use of a generative model drastically simplifies the analysis. Would any of these results translate to a navigating model?\n\nThe lower bound seem to imply that *all* state-action pairs have to be visited n times. I am surprized that the sampling of state-action pairs is not adaptive. Would it change anything?", "limitations": "NA.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is really well written. The related work section show that the paper is well documented, and the authors make a good use of the related work via the various references throughout the text. The choice of the examples and their use is nicely done. All in all, the paper is nice to ready.\n\nThe paper improves on related work and obtain an algorithm that matches the lower bound.\n\nThe paper is very precise in its definitions (contrary to many papers on the same subjects).\n\nThe paper studies learning algorithm for multi-chain MDPs, which is rarely done.", "weaknesses": "The algorithmic novelty of the paper seems limited. Only the analysis seems new.\n\nThe authors focus on a generative model (although this is probably unavoidable in the multichain case).\n\nTo me, the discussion on the lower bound is not complete.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Regarding algorithmic novelty, you are correct that several of our results are established with novel analyses of existing algorithms. We believe that this is a strength of our results, for several reasons. Simple algorithms are preferable in practice, and our analyses demonstrate that several of the simplest and most well-studied approaches, namely average-to-discounted reduction and the plug-in approach for solving DMDPs, can be used to achieve optimal sample complexity. We believe this is a more impactful result as opposed to a problem-tailored algorithm which is unlikely to be used in practice. Additionally, our results on the plug-in approach for solving DMDPs hold when any algorithm is used to solve the empirical MDP $\\widehat{P}$, which is a stronger result than proving that only a particular algorithm works.\n- Additionally, we believe that our results for general/multichain MDPs represent algorithmic novelties, since conditions for the average-to-discounted reduction to work were not previously known for this setting (and the conditions are different compared to the weakly communicating setting; namely, a different effective horizon is required within the reduction). For example, even when the true transition matrix $P$ is known, our multichain average-to-discounted reduction Theorem 6 suggests new iterative algorithms for solving multichain MDPs: if we (approximately) solve $P$ as a DMDP with effective horizon $(\\mathsf{B}+\\mathsf{H})/\\varepsilon$ by standard discounted value iteration methods, then we get an $\\varepsilon$-gain-optimal policy. This is interesting to compare to usual (undiscounted/average-reward) value iteration, which to our knowledge does not have finite-time guarantees for general MDPs.\n- We agree that generative model access can be a strong assumption, but we note that it can be a building block for algorithms which work in more general settings. Sometimes this may be from an indirect theory-building perspective, and other times algorithms for the generative model can be directly used and combined with another procedure for exploring and obtaining samples in a navigating model. Also, as pointed out by reviewer i8Mw, in commonly studied uniformly mixing settings, the navigating model basically reduces to the generative model (with an additional mixing time complexity factor).\n- Regarding the lower bound, the sampling model is chosen to match that of the generative model, which assumes an equal number of samples from each state-action pair. We believe that an adaptive sampling model would not substantially change the lower bound. (We actually believe that our current lower bound construction could be adapted to this setting, for the following reasons: The construction for Theorem 4 is based on the difficulty of distinguishing amongst a set of $\\Theta(SA)$ different MDPs. Each of these MDPs has a different “special” state-action pair $(s^\\star,a^\\star)$ which yields slightly larger expected average reward but are otherwise identical. Discerning the identity of $(s^\\star,a^\\star)$ by sampling adaptively from different state-action pairs is thus similar to a best-arm identification problem for stochastic multi-armed bandits, so we believe adaptive lower bound arguments from that setting could be used here.)", "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:
We thank all reviewers for their time and positive feedback. We will respond to each reviewer directly via individual rebuttals.

Meta-review: Reviewers unanimously agree that this is a good paper resolving an important question. The presentation is also clear. Some reviewers believe this is an award-quality paper.
Decision: Accept (oral)