Optimal Sample Complexity for Average Reward Markov Decision Processes
Authors: Shengbo Wang
Jose Blanchet
Peter Glynn
Venue: ICLR 2024 poster (2024)
Keywords: reinforcement learning
Markov decision processes
long run average reward
sample complexity
Primary area: reinforcement learning
TL;DR: We resolve the open question regarding the sample complexity of policy learning for maximizing the long-run average reward associated with a uniformly ergodic Markov decision process (MDP), assuming a generative model.

Abstract: We resolve the open question regarding the sample complexity of policy learning for maximizing the long-run average reward associated with a uniformly ergodic Markov decision process (MDP), assuming a generative model. In this context, the existing literature provides a sample complexity upper bound of $\widetilde O(|S||A|t_{\text{mix}}^2 \epsilon^{-2})$ and a lower bound of $\Omega(|S||A|t_{\text{mix}} \epsilon^{-2})$.  In these expressions, $|S|$ and $|A|$ denote the cardinalities of the state and action spaces respectively, $t_{\text{mix}}$ serves as a uniform upper limit for the total variation mixing times, and $\epsilon$ signifies the error tolerance. Therefore, a notable gap of $t_{\text{mix}}$ still remains to be bridged. Our primary contribution is the development of an estimator for the optimal policy of average reward MDPs with a sample complexity of $\widetilde O(|S||A|t_{\text{mix}}\epsilon^{-2})$. This marks the first algorithm and analysis to reach the literature's lower bound. Our new algorithm draws inspiration from ideas in Li et al. (2020), Jin \& Sidford (2021), and Wang et al. (2023). Additionally, we conduct numerical experiments to validate our theoretical findings.

Published as a conference paper at ICLR 2024
OPTIMAL SAMPLE COMPLEXITY FOR AVERAGE REWARD MARKOV DECISION PROCESSES
Shengbo Wang, Jose Blanchet & Peter Glynn
Department of Management Science and Engineering
Stanford University
Stanford, CA 94305, USA
(shengbo.. wang, jose bllachett giynn y estannerdaafdddd
ABSTRACT
We resolve the open question regarding the sample complexity of policy learn- ing for maximizing the long-run average reward associated with uniformly er- godic Markov decision process (MDP), assuming a generative model. this context, the existing literature provides sample complexity upper bound of O(SS) A A F lower bound of S [[[ [[[S][][[mm) ||
these expressions, IS] and |A| denote the cardinalities of the state and action spaces respectively, mmix serves as a uniform upper limit for the total variation mixing times, and signifies the eπrоr tolerance. Therefore, notable gap of mix still remains to be bridged. Our primary contribution is the development of an estimator for the optimal pol- icy of average reward MDPs with a sample complexity of O[[S) A4emx 3) This marks the first algorithm and analysis reach the literature's lower bound. Our new algorithm draws inspiration from ideas in Li et al. (2020), Jin & Sidford (202I), and Wang al. (2023). Additionally, we conduct numerical experiments to validate our theoretical findings.
INTRODUCTION
This paper offers a theoretical contribution to the area of reinforcement learning (RL) by providing the first provably optimal sample complexity guarantee for a tabular RL environment which controller wishes to maximize the long run average reward governed by a Markov decision process (MDP).
The landscape of RI. has been illuminated by remarkable empirical achievements across diverse spectrum of applications (Kober et al., 2013] Sadeghi Levine 2016 Deng al., 2017). As consequence, great deal of research effort has been channeled into RL theory and its applications within operations research and the management sciences. In many real-world scenarios, influenced by engineering and managerial considerations, the MDP model naturally unfolds within envi- ronment where viable policies must stable (Bramson) 2008). In these settings, the controlled Markov chain induced by reasonable policy will typically converge in distribution steady state, regardless of the initial condition. This phenomenon is known as mixing. Within such modeling environments, the long average reward emerges well-defined and pertinent per- formance measure to maximize. Its relevance is particularly pronounced in scenarios where there an absence of an inherent time horizon discount factor. situations where system exhibits fast mixing, finite-time observation of the state process can offer a good statistical representation of its long-term behavior. As a result, becomes reasonable to anticipate that, for such systems, lower-complexity algorithm for policy learning is attainable.
unique
Recognized as a significant and challenging open problem in RL theory, the optimal sample com- plexity for average reward MDPs (AMDPs) under generative model, i.e., sampler capable of generating new states for the controlled Markov chain conditioned on any state and action, has been
"The Ō. Ō. θ hide log factors.

---

Published as a conference paper at ICLR 2024
Table 1: Sample complexities of AMDP algorithms. When mix appear in the sample complexity, an assumption of uniform ergodicity is being made, while the presence of H is associated with an assumption that the MDP is weakly communicating.
Sample complexity
Algorithm
Origin
upper bound (Ö)
Primal-dual learning
Wang (017))
|S| 2 mix
Primal-dual SMD"
Jin & Sidford 2020
|||| Alc mix -2
Reduction DMDP"
Jin & Sidford (0021)
|S A mixx
Reduction to DMDP
Wang et al. (0022)
|S| A H
Refined Q-learning
Zhang & Xie (2023
|S] A H
Reduction to DMDP
This paper
[S] A mix
Jin & Sidford (022
SX[|S]| A 1
Lower bound
Wang et al. (2022)
extensively investigated in the literature (refer to Table TT. In this paper, our focus is learning an optimal policy for a uniformly ergodic AMDP (Meyn & Tweedie 2009 Wang et al. (023), and we attain the first optimal sample complexity bound within this context. Specifically, assuming finite state and action spaces, uniform ergodicity implies that the transition matrix P5 induced by any sta- tionary Markov deterministic policy has the property that pm converges rows in & distance as m - 0o at geometric rate. The time constant of this geometric convergence known as the mixing time. The largest mixing time over all æ is an important parameter denoted by miix (see equation (..2). In this setting, we establish the following main result:
matrix with identical
Theorem 0 (Informal). Assuming that the AMDP uniformly ergodic, the sample complexity of learning a policy that achieves long run average reward within E (0, 1] of the optimal value with high probability is
ē (
(IS||A|tmis
where (S), |A| are the cardinality of the state and action spaces, respectively.
A rigorous version of Theorem 0 is presented in Theorem We highlight that this is the first optimal result in the domain of sample complexity of AMDPs, as it achieves the lower bound Jin & Sidford 202T) for uniformly ergodic AMDPs.
1.1 LITERATURE REVIEW
In this section, we review pertinent literature to motivate our methodology and draw comparisons with our contributions.
The relevant literature is summarized in Table I It's important to note that the works mentioned in this table revolve around the concept of mixing, albeit from distinct perspectives. On one side, Waag (2017); Jin & Sidford (2020) 2021). and the current paper assumes uniformly ergodic AMDP. Conversely, Wang al. (2022) and Zhang & Xie (2023) operate under a milder assumption, considering weakly communicating AMDPs as defined Puterrman (194). Under this assumption, only the optimal average reward is guaranteed remain independent of the initial state and is attained by a stationary Markov deterministic policy. In particu- lar, certain policies in this setting might not lead to mixing Markov chain, potentially rendering the policy's 's average reward state dependent. Consequently, the uniform mixing time upper bound fmix infinite within such instances. In this context, a pertinent complexity metric parameter denoted as H is the span semi-norm (see (A.I)) upper bound of transient value functions H max; |u. Ispann"
Sample Complexity of Average Reward RL:
where the max is taken over all optimal policies and 2 is defined in 2.5 As demonstrated in
$ H is the maximum span of optimal transient value functions. See the literature review for discussion.
'Let 17" be the stationary distribution of P.. then r == max. max.es 1f" (s)/ min. 17" (s).
SMD stands for stochastic mirror descent while DMDP stands for discounted MDP.
For periodic chains, the limit in (25) is understood the Cesaro limit, see Puterman 1994
2

---

Published as a conference paper at ICLR 2024
Table Sample complexity of uniformly ergodic DMDP algorithms when mmix S (1- where Y is the discount factor.
Sample complexity
Origin
Minimum sample size (52)
upper bound (Ö)
Azar et al. 2013)
[S]|A[(1 - 7) -3 6
[ - 7)
Agarwal al. (2020)
|5]|4|(1 - 7) 6
|S]|-A[[1 - 7)
Li ct al. 2020
|S]|A[(1 - -7)
|S]]_A[(1 7)-
Wang et al. (2023)
[S||A|t - (2)11--)-22 -2-
[S||AA((1 - 7)
This paper
| - 22-
|S]|A|[[1 -)
Lower bound
fuix (1 22--
N/A
Wang et al. (2023)
Wang et al. (2022), it holds that H S 8tmix when the reward is bounded in [0, 1]. It's important to note that H7 depends on the specific reward function, whereas mmix does not. Therefore, the reverse inequality cannot hold, even within the realm of uniformly ergodic MDPs. This is evident when consider a reward function that is identically O. However, it's worth mentioning that the family of worst-case uniformly ergodic MDP instances presented in Wang et al. (203)) exhibits H = (tmixx) See Section 5 for some more discussion.
Additionally, we highlight that two existing papers in the literature, namely Jin & Sidford (2021) and |Wang et al. (2022). employ the reduction to a discounted MDP (DMDP) method to facilitate policy learning for AMDPs. This paper follows the same approach. In Section 1.2 we will offer an in-depth discussion of this methodology and a comparison with these two papers.
Sample Complexity of Discounted Tabular RL: In recent years, there has been substantial interest in understanding the worst-case sample complexity theory of tabular DMDPs. This research has given rise to two primary approaches: model- and model-free. Model-based strategies involve constructing an empirical MDP model from data and employing dynamic programming (see |Azar al. (213); Sidford et al. (2018); Agarwal et al. (2020) [i et al. (2022)). yielding optimal upper and lower bounds of @(S)) (1-7) 3 (e=3)) 2), where is the discount factor. Mcanwhile, the model-free route maintains lower-dimensional statisties of the transition data, exemplified by the iconic Q- learning (Watkins & Dayan 1992) and its extensions. Li et al. (202T) demonstrates that the classic
Q-learning algorithm has worst-case sample complexity of @[SS]]A[(1 -7)-2 However, Wainwright (2019) introduced a variance-reduced Q-learning variant that reaches the same lower
bound as model-based methods.
Worst-case analysis provides uniform guarantees for convergence rates across all 7-discounted MDP instances. However, the worst-case examples that achieve the lower bound must have transition kernel or reward function that depends on y (Wang et al. 2023). In contrast, Khamaru et al. (202I) settings, where the transition kernel and reward function
focuses eestance-deeendee and proves matching sample complexity upper and lower hounds. Wang et al. (203)) concentrates on scenarios in which the class of MDPs can encompass arbitrary reward functions, while the transition kernels are assumed to obey various mixing time upper bounds. A particular setting is when this mixing time upper bound is uniform across all policies. This specific setting aligns with the central objective of this paper: Derive optimal sample complexity theory for uniformly ergodic AMDPs.
fixed,
1.2 ALGORITHM METHODOLOGY
Our approach to algorithmic design draws inspiration from Jinn & Sidford (202I), wherein the opti- mal policy of uniformly ergodic AMDP is approximated by that learned from a discounted MDP (DMDP) with a discount factor - y ( (mix)) This idea approximating the AMDP by a
DMDP been considered and implemented since 1970s, see Hordijk & Tijms (1975). It is known as the reduction method in the AMDP sample complexity literature. As shown in Table however,
The lower bound in Wang al. 2023 assumes |S]| 0(1).
3

---

Published as a conference paper at ICLR 2024
both Jin & Sidford (2021) and Wang et al. (2022) employed this strategy and yet obtained an e dependency, deviating from the canonical rate obtained in this paper.
To understand this deviation and motivate our methodology, we provide brief discussion of the sample complexity theory for uniformly ergodic DMDPs. Prior to Wang et al. (2023), the DMDP algorithm, known as perturbed model-based planning. and the analysis in [i al. (2020) achieved a sample complexity dependence on 1 - 7 of Ō((1 -?) - Though optimal for the worst-case DMDP, this dependence on - is sub-optimal for policy learning of uniformly ergodic DMDPs. On the other hand, the state-of-the- an optimal (1mix(1-12) -) dependence, as displayed in 2 The sub-optimal
algorithm and associated analysis in Wang et al. (2023) yield dependency observed in bot & Sidford (2021) and Wang et al., (2022) can be attributed to their utilization of
the @(( - -)) result from Li et al. 2020), without taking into account the complexity reduction from the associated mixing assumptions.
Building upon the aforementioned DMDP results, our strategy is rooted in recognizing that the optimal sample complexity of uniformly ergodic DMDPs is ([S)] (1-))22))))---3 As shown in Table 2 the algorithm presented in Wang et al. (2023) is capable of achieving this complexity. However, as indicated in the third column of Table 2 it necessitates a minimum sample size of (((S)) (1) 3) This quantity can be interpreted as the initial setup cost of the algorithm which is indifferent to the specification of c. Unfortunately, (1 - -)- proves to be excessively large for our objective. For a more comprehensive discussion on this issue, see Section [.1
To overcome this challenge, in this paper, we successfully establish an optimal sample complex- ity upper bound for the algorithm proposed in Li et al. (2020) in the setting of uniformly ergodic DMDPs. We achieve this while simultaneously maintaining a minimum sample size requirement of [ - -)) This optimal sample complexity bound for uniformly ergodic DMDPs, which builds upon and enhances the findings in Wang et al. (2023). is of independent theoretical signifi- cance. The formal statement is presented in Theorem | Section 3.1 This accomplishment made possible by applying analytical techniques presented in Wang et al. (2023). In conjunction with the
reduction methodology outlined in Jin & Sidford (202 ) these developments collectively result in the AMDP Algorithm
2
which attains the optimal sample complexity as outlined in Theorem 0
2 MARKOV DECISION PROCESSES: DEFINITIONS
We consider the setting of MDPs with finite state and action space S and A. Let P(S) denote the set of probability measures on S. An element p E P(S) can be seen as a row vector in |i Let M(r, P,)) denote discounted MDP (DMDP), where P: x A - P(S) is the transition kernel, and y E (0, 1) is the discount factor. Note that P can be identified with s, a indexed collection of measures {Pa.e P(S): (s, a) S A). We denote an average reward MDP (AMDP) with the same reward function and transition kernel by M(r, P).
S x A - [o, 1] is the reward function,
Let H = (IS) x _ and H the product -ieldd form the underlying measureable space. Define the stochastic process {(X,, At), t 2 0} by the point evaluation (h) st, Achh) a, for all t 2 O for any h = (So. ao, $1, a1 .)....) E H. At each time and current state X₁, if action A, is chosen, the decision maker will receive reward r(Xi, Ar). Then, the law of the subsequent state satisfies L(X, Xo, Ao,... N,, A.) = Ax.,A, (.) w.p.1.
It is well known that achieve optimal decision making in the context of infinite horizon AMDPs or DMDPs (to be introduced). it suffices to consider the policy class IT consisting of stationary. Markov, and deterministic policies; i.e. any क E II can be seen as a function π : S + A. For π E il and initial distribution E P(S), there is a unique probability measure QJ on the product space s.t. the chain ((X,, A.). t 2 0} has finite dimensional distributions
(X, 80, Ao = da..... ... A, = 04) ((s)) (so. (#1 Per 1. 1)()))1 (m(s)) = as, Vi). where the indicator function. Note that this also implies that (X,, t 2 0} Markov chain under Q with transition matrix P. defined by
(x)), = (8))
Also, we define r. by (s) (())-
4

---

Published as a conference paper at ICLR 2024
2.1 DISCOUNTED MDPs
For E II, let Ey denote the expectation under under Q7. For with full support S, the discounted value function v² (s) of a DMDP is defined via
(8)
F
t Ab) Ab) Xo
be seen as a vector ax RISI and be computed using the formula vn = -P--7Pa- trx The optimal discounted value function is defined as
max o" (8), S. =el
For probability measure p on S. let p[v] denote the sum E.es p(s)u(s). It well known that ot is
the unique solution of the following Bellman equation:
en (s) max (r(s,a) + TPs,,al")))
(2.1)
Moreover, (s) E arg m (r(s. u) + (Ps.a(v")) optimal and hence V² = -1-774 -(-') -
2.2 AVERAGE REWARD MDP
As explained in the introduction, in this paper, assume that the MDP of interest is uniformly ergodic. That is, for all π E II, Pn is uniformly ergodic. By Wang et al. (2023), this is equivalent to the setting in (Wang) 2017 Jin & Sidford (02T) where the authors assume
mix == max inf well
m 2 1 max #ES
P (s, 7 - 2 < 0o.
(2.2)
Here 1/+r (.) is the stationary distribution of Pa and ||-11 is l distance between probability
tors. Further, this is also shown in Wang et al. (2023) to be equivalent to the following assumption:
Assumption (Uniformly Ergodic MDP). For any π II, there exists m 2 1,g S 1 and probubil- ity measure tp E PSS) such that for all E S, pm (s, ) 2 (V()).
Here, the notation pr denotes the mith power of the matrix Px. Assumption Tis commonly referred to, in the general state-space Markov chain literature, as P., satisfying the Doeblin condition (Meyn we define the minorization time as follows.
& Tweedie 2009). In the context of Assumption[1 [
Definition (Minorization Time). Define the minorization time for a uniformly ergodic kernel P.. as
Eminorize (Pa) = inf m/g inf Pm 2 qi(()) for some & E P(S)
SES
Define the minorization time for the uniformly ergodic MDP as
tminorize == max Eminorize (Pa).
xell
Since is finite, the above max is always achieved, and hence miiuorize < cc. Moreover, Theorem 1 of Wang et al. (2023) shows that tuinorize and fmix equivalent up-to constant factors:
mminorize < 22 S 22 log ( minorize-
(2.3)
Therefore, the subsequent complexity dependence written in terms of tminorize can be equivalently expressed using tmix.
Under Assumption [ for any initial distribution Xo p, the long run average reward of any policy defined as
0." = T
r (X,, Ar)
T
==
where the limit always exists and doesn't depend on μ.. The long run average reward at can be characterized via any solution pair (u, a), u: S + R and a E R to the Poisson's 's equation,
Fr (T Pr Pz)u.
(2.4)

---

Published as a conference paper at ICLR 2024
Under Assumption solution pair (u, a) always exists and is unique up to shift in i.. {(u + ce, a) : R. where e(s) = 1, Vs E S, are all the solution pairs to (2.4). particular, for
any II, define the transient value function a.k.a. the bias
(8) = lim
E
(ra(()) a²)
(2.5)
T-000
where the limit always exists. Then, (u", a) ) is the unique up shift solition to 2.4).
Similar to DMDPs, define the optimal long run average reward ā as
á == max
#ell
Then, for any म that achieve the above maximum, (u", .a) solves rx - - -1 Pa)u
3 OPTIMAL SAMPLE COMPLEXITIES UNDER A GENERATIVE MODEL
In this section, we aim to develop an algorithm for AMDPs that achieves the sample complexity as presented in Theorem 0 The randomness used by the algorithm arises from underlying probabil- ity space (S2 F, P). We proceed under the assumption that we have access to a generative model, or sampler, which allows to independently draw samples of the subsequent state from the transition probability (s', & E 5) given any state action pair (s, a).
As explained in Section 1.2 our methodology closely aligns with the approach introduced in Jin & Sidford (202T). We leverage the policy acquired from a suitably defined DMDP as an approximation the optimal policy for the AMDP. However, prior this work, the state-of-the-art DMDP algo- rithms, along with the accompanying worst-case sample complexity analysis. fall short in achieving the optimal sample complexity articulated in Theorem 0 (Jin & Sidford 2021 Wang et 2022).
This limitation emanates from the fact that the sample complexity of uniformly ergodic DMDPs has a dependence (1 - -)- as demonstrated in the preceding research Wang et al. (2023). This is notable improvement over the (1 (1-7)-3 dependence associated with the worst-case-optingg DMDP theory (Li et al. 2020), a foundation upon which Jín & Sidford (202T) and Waan et al. (2022)
were constructed. Consequently, to attain the desired complexity result, our initial step involves establishing enhanced sample complexity assurances for uniformly ergodic DMDPs.
3.1 SAMPLE EFFICIENT ALGORITHM FOR UNIFORMLY ERGODIC DMDPS
We recognize that the optimal sample complexity of uniformly ergodic DMDPs should be - 2 2); c.f. (Wang et 2023). Regrettably. as mentioned earlier, the algorithm introduced in Wang et al. (2023), while indeed capable of achieving this sample complex- ity, falls short in terms of the minimum sample size as it requires (([SS]A[( -7) -3) for its execution, a complexity that is too large for our purposes.
To elaborate on this issue, note that the algorithm introduced in Wang et al. (2023) constitutes a variant the variance-reduced Q-learning ( (Wainwright] 2019). This family of algorithms ne- cessitates minimum sample size of n = [([S[]A[[1 - -)- as per existing knowledge. Re- markably, model-based algorithms can achieve significantly smaller minimal sample sizes: e.g.
n [|(( - -) Agarwal al. (2020). and the full-coverage n = [[[S]]A[(( (1-l(11>)--1 - in Li et al. (020)_ See T This comparison motivates our adoption of the algorithm introduced in Li et al. (2020) and to draw upon the techniques utilized for analyzing mixing MDPs from Wang al. (2023). The synergistic combination of these ideas, as elucidated in Theorem [ results in an algorithm with the optimal sample complexity of @([S]] [[[S]][[[mmann [|mmnorriza (1 26-2 and minimum sample size n [[] - -1) at the same time. In this section, our analysis suppose Assumption minoriie S (1 (1-7)-1 and 2 1
3.1.1 THE DMDP ALGORITHM AND ITS SAMPLE COMPLEXITY
We introduce the perturbed model-based planning algorithm for DMDPs in Li et al. (2020). Let > be design parameter that we will specify later. Consider random perturbation of the

---

Published as a conference paper at ICLR 2024
reward function
R(s, == r(s,a) - [(, (s,0)
where the random element Z S x A + [0,4]
((s, a) Unif(0,5)
(3.1)
i.dd. V(s. a) S A. The reason consider a perturbed reward with amplitude parameter Ç is to ensure that the optimality gap of the optimal policy, compared with any other suboptimal policy, is sufficiently large. To accomplish this, is not necessary to assume uniform distributions of (ss, a). However, we opt for this choice for the sake of convenience. This reward perturbation technique is
well motivated in [L et al. 2020). So, we refer the readers to this paper for detailed exposition. Then, the perturbed model-basee planning algorithm therein is formulated in Algorithm |
Algorithm Perturbed Model-base based Planning (Li et al. 2020 PMBP( n)
Input:
Discount factor 7 E (0, 1). Perturbation amplitude Ç >> 0. Sample size 2 1.
Sample in 33.1 and compute R = r + Z.
Sample i.i.d. ( cl2) S......... s(n) for each (s,a) E S x A. Then, compute the empirical kernel
P == (s', (8,a) ESESXXL A,
A 5) where
(s')
1
S = E
Compute the solution 8n the empirical version of the Bellman equation 2. i.. Vs E S, (s))) = maxag (R(s,, a) -VP,,((o)) Then, extract the greedy policy
fs(s) E arg max (R(s, a) + ( SE S.
a
return To-
By 22.1 To returned by Algorithm | optimal for the DMDP instance M(R, 7)) Also, computing do therein involves solving a fixed point equation in RISI, This can be done (with machine precision) by performing value or policy iteration using additional samples.
In summary, al. 2020)) proposed to use tn, the optimal policy of the reward-perturhed empirical DMDP M(R, P) as the estimator to the optimal policy x" of the DMDP M(r, P.7). They proved that this procedure achieves sample complexity upper bound of + [[S]] A[(1 - -3 over all DMDPs (not necessarily uniformly ergodic ones) with a minimum sample size requirement S [A[(1 - -)) We are able to improve the analysis and achieve an accelerated result of independent interest the context of uniformly ergodic DMDPs. Before introducing our results, let us define two parameters. Recall ( from (3.1). For prescribed error probability 5 E (0. 1), define
(1) = 2 log S4| |A] logz (1--)= and v/
{8(1 (6(1-))
(1 - 2
All
The reason for defining (-) and n/ will become clear when we introduce the intermediate results in Proposition A. and A.2 in the Appendix. Now, we are ready to state improved error and sample complexity bounds for Algorithm that achieve minmax optimality for uniformly ergodic DMDPs:
in force. Then, for any 7 E [1/2, 1), < > and n 2 643s(1g)(1 -1, the policy too returned by Algorithm PMBP(>; S. satisfies
Theorem Suppose Assumption
2ç
3s(11) Miiinorine
0 n² - 50
<
+ 486
(3.2)
1 1-
(1 (1- Pn
w.p. at least 8-8. Consequently, choose (1-7)e 7)e/4, the sample complexity achieve error O < S Vtuinorriee/ (1 7) w.p. at least is
||]|A|tmnnoti
222
7

---

Published as a conference paper at ICLR 2024
The proof of Theorem 1 is deferred to Appendix
Remark. Compare to the worst case result in, c.g., Azar et al. (013 and Li al. (020). Theorem
1 replaces a power of (1 - -) by Eminorize in (32 The implied sample complexity upper bound
matches the lower bound in Wang et al. 2023) up log factors. So, O can be replaced by O Also, this is achieved with a minimum sample size n 6448(1%))
-7)-+ -1 This and the mixing time
equivalence
2.3) confirms the sample complexity claim in Table
3.2 AN OPTIMAL SAMPLE COMPLEXITY UPPER BOUND FOR AMDPS
Using the sample complexity upper bound in Theorem 1 we then adapt the reduction procedure considered in Jim & Sidford (2021). This leads to an algorithm that learns an e-optimal policy for any AMDP satisfying Assumption with the optimal sample complexity. Concretely, we run the reduction and perturbed model-based planning Algorithm
Algorithm Reduction and Perturbed Model-based Planning
Input: Error tolerance E (0, 1]. Assign
- 1 =
cB3(1z)
7
<
7) minorize, and
191 minorize
(1 minoriie
where c -4822. Run Algorithm with parameter specification PMBP(7; (,))) and obtain output tn. return No.
This algorithm has the following optimal sample complexity guarantee:
Theorem 2. Suppose Assumption 7 is force. The policy än output by Algorithm satisfies 0 S
ā a Fo < w.p. at least 1 - 5. Moreover, the total number of samples used is
[|||A\/minrrie
The proof Theorem 2 deferred to Appendix
Remark. This achieves the minmax lower bound in Jin & Sidford (2221) up to log factors. So, δ be replaced by é. This and the equivalence relationship 2.3 between tminorize and tmix is formal statement of Theorem
4 NUMERICAL EXPERIMENTS
In this section, we conduct two numerical experiments to verify our algorithm's optimal sample complexity dependence on and mminorize The family of reward functions and transition kernels used for both experiments belongs to the family of hard instances constructed in Wang et al. (2023). By the same reduction argument, this family of AMDPs has sample complexity [[mminorize ²)
First, we verify the dependence of our algorithm. To achieve this, we study the error of estimating the true average reward 0.5 as the sample size increases. The experiment runs 300 replications of Algorithm 2 under different sample sizes and constructs the red data points and regression line in Figure la We also implement the algorithm proposed in Jin & Sidford (2021), conduct the same experiment, and produce the data in blue. Our algorithm outperforms the prior work. Moreover, in log-log scale, the red regression line has a slope that is close to -1/2, indicating a n -1/2 conver- gence rate. This verifies the optimal Ō))=2) dependence of our Algorithm the blue line has a slope near - 11/3, indicating suboptimal Ōc-33) for the algorithm in Jin & Sid- ford (2021). This significant improvement is due to our optimal implementation and analysis of the DMDP algorithm in Li et al. 2020 reducing sample complexity dependence on (1 --)-!
2 On the other hand,
Next, we verify our algorithm's 's sample complexity dependence on tminorixe- Fix e > and recall that 1 7 ((e/Iminozzi
(Imiinriize -1). So, the optimal sample size for Algorithm
8

---

Published as a conference paper at ICLR 2024
10"3
[16221] slope 0..3
slape 0.02
work, slope
10"2
average error
average error
10-3.
10
108
10
10
10a Eminorice
10a
number of samples
(a) Convergence rate comparison with Jin Sidford
(b) Verification minorize dependence. slope in-
2021 A 0.5 slope verifies the Ö(E dependence. dicates the (fminorize dependence.
Figure 1: Numerical experiments using the hard MDP instance in Wang et al. 2023
2 is = ( ( 2) minnrriee ) = θ (fminooczze) which is linear in minorize. Thus, applying Algorithm to the hard instance with minorization time minorize using sample size Ciiinorizee for some large constant C, our sample complexity upper bound suggests that the estimation error of ā should be Õ(1). Consequently, plotting the average error against the number of samples used cquivalently, fminorize on a log-log scale while varying fminorize should yield a line with a near 0 (or possibly negative) slope, according to theory. The experiments in Figure use C 4500 for the purple line and C = 18000 for the blue line. With imimorize varying within the range [10, 1000). both regression lines exhibit near 0 slope, indicating O(tminorize) dependence.
Therefore, through the numerical experiments presented Figure we separately verify the opti- mality of our algorithm's 's sample complexity dependence on both and minoriiee
CONCLUDING REMARKS
We now discuss certain limitations intrinsic to our proposed methodology well as potential av- enues for future research. Firstly, the use of the DMDP approximation approach necessitates a priori knowledge of an upper bound on the uniform mixing time for the transition kernel P in order to ini- tiate the algorithm. In practical applications, such upper bound can be challenging to obtain, or in certain instances, result in excessively pessimistic estimates. One could circumvent this by using an additional logarithmic factor of samples, thus allowing for the algorithm to operate with geomet- rically larger values of fmix. and terminate after suitable number of iterations. Nevertheless, this approach still hinges upon the knowledge of the mixing time to achieve optimal termination.
Secondly, assume strong form of MDP mixing known uniform ergodicity. While theo- retically optimal, this notion of mixing yields conservative upper bounds on sample complexity in situations wherein suboptimal policies induce Markov chains with especially large mixing times.
our contention, supported by the findings presented in references such as Wang et al. (2022) and Wang al. (2023), that the sample complexity should be contingent solely upon the properties the optimal policies. Moreover, the complexity measure parameter // that is used in Wang et al. (2022); Zhang & Xie (2023) has several advantages over mmix that lie beyond the ability generalize to weakly communicating MDPs. In particular, for periodic chains and special situations where the optimal average reward remains indepeddddnn despite the presence of multiple recurrent classes of the transition kernel induced by optimal policy, the parameter H is well-defined but 4mix is (Puterman| 1994). Consequently, we are now dedicating research effort to the development of an algorithm and analysis capable of achieving a sample complexity of [(
Lastly, the assumption of uniform ergodicity extends beyond finite state space MDPs, aspire to venture into the realm of general state-space MDPs. Our objective is to extrapolate the principles underpinning methodology obtain sample complexity results for general state space MDPs.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The material in this paper is based upon work supported by the Air Force Office of Scientific Re- search under award number TTA555--0-1-00397 Additional support is gratefully acknowledged from NSF 1915967. 21 28199 2229012, 2312204.
REFERENCES
Alekh Agarwal, Sham Kakade, and Lin F. Yang. Model-based reinforcement learning with gener- ative model is minimax optimal. In Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory. volume 125 of Proceedings of Machine Learning Research, pp. 67-83. PMLR, 09-12 Jul 2020.
14
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J. Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with generative model. Mach. Learn., 91(3): 325-349, jun 2013. ISSN 0885-6125. doi: 10.10077/119994--13-35330
3
Maury Bramson. Stability of Queueing Networks: École d' Été de Probabilités de Saint- Flour XXXVI 2006. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. [
Y. Deng, F. Bao, Y. Kong, Z. Ren, and Q. Dai. Deep direct reinforcement learning for financial signal representation and trading. IEEE Transactions Neural Networks and Learning Systems, 28(3):653-666 664, 2017.
Arie Hordijk and Henk Tijms. A modified form of the iterative method of dynamic programming The Annals of Statisties, 3(1):003-208 1975. ISSN 00905364. URL www.:tttp:/./ httt:::/www... jstor.
3
Yujia Jin and Aaron Sidford. Efficiently solving MDPs with stochastic mirror descent, 2020.
Yujia Jin and Aaron Sidford. Towards tight bounds on the sample complexity of average-reward MDPs, 2021.
g
9
13
Koulik Khamaru, Eric Xia, Martin J. Wainwright. and Michael I. Jordan. Instance-optimallty in optimal value estimation: Adaptivity via variance-reduced q-learning, 2021.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal Robotics Research, 32(1 22(1)):22881127) 2013.
Gen Li, Yuting Wei, Yuejic Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with generative model. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, Curran Associates, Inc., 2020.
volume 33, pp. 22861-12872
I7
Gen Li, Changxiao Cai, Yuxin Chen, Yuantao Gu, Yuting Wei, and Yuejie Chi. Is q-learning mini- max optimal? A tight sample complexity analysis. arXiv preprint 1rXiv:2102.065:: 2021. B
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-based offline reinforcement learning, 2022. 3
Sean Meyn and Richard L. Tweedie. Markov Chains and Stochastic Stability. Cambridge Mathe- matical Library. Cambridge University Press, 2 edition, 2009. doi: 10.1017/CB8997801116666
5
M.L. Puterman. Average Reward and Related Criteria, chapter 8, pp. 331-440. John Wiley & Sons, Ltd, 1994. ISBN 9780470316887. doi: http://ooioog///..00229198711111
9 12
Fereshtch Sadeghi and Sergey Levine. Cad2rl: Real single-image flight without single real image.
arXiv preprint preprimi arXiv:1611.04200 2016. !
Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sam- ple complexities for solving Markov decision processes with generative model. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- BiancB,, and R. Gamett (eds.), Advances in Newral Information Processing Systems, volume 31. Curran Associates, Inc., 2018.1 3
10

---

Published as a conference paper at ICLR 2024
Martin J. Wainwright. Variance-reduced q-learning is minimax optimal, 2019. 3
Jinghan Wang, Mengdi Wang, and Lin F. Yang. Near sample-optimal reduction baased policy learn-
ing for average reward MDP, 2022. 23 9
Mengdi Wang. Primal-dual π learning: Sample complexity and sublinear run time for ergodic
Markov decision problems, 2017. 2
Shengbo Wang, Jose Blanchet, and Peter Glynn. Optimal sample complexity of reinforcement
learning for uniformly ergodic discounted Markov decision processes, 2023.
13 15 18
Christopher J. C. H. Watkins and Peter Dayan, Q-learning. Machine Learning, 833):279-222, May 1992. ISSN 1573-0565. doi: 10. 10.1007/BF00992668, 3
Zihan Zhang and Qiaomin Xie. Sharper model-free reinforcement learning for average-reward Markov decision processes, 2023.

---

Published as a conference paper at ICLR 2024
Appendices
A
STATISTICAL PROPERTIES OF THE ESTIMATORS OF UNIFORMLY ERGODIC DMDPS
In this section, objective is establish concentration properties pertaining the estimators of the value function and optimal policies. Before discussing these statistical properties, we introduce some notations and auxiliary quantities that facilitate our analysis.
Under Assumption 1 it is useful to consider the span semi-norm (Puterman 1994.. For vector E V RA let be the vector with all entries equal to one and define
|o span
== inf || co
<EP
(A.1)
max 2
min U/. Isidd
Isid
Note that the span semi-norm satisfies the triangle inequality |v + w S Wlssan | spann
The analysis in this section will make use of the following standard deviation parameters: define
()) V [v [s,a and (x)))(s) (s,
(A.2)
Let To be optimal policy associated with MDPs M(7, P, R). Recall that to is optimal for M(7 P, R). Define for any x E II, on (I )P)) 1 R, and bg = (I - Px) R. Also, let
40 (T - -
Consider the following event
P2 2,,== inf SE8
(s) 00
max (o(s.b) b) b*fo(()
2 2nj
(A.3)
This is set of good events on which the optimality gap MDP M(T, P. R) is larger than 1).
Recall the definition of the reward perturbation Z in (3. and perturbed reward R. For any т E II, let R5 (s) R(s, (8)) and (s) = 7(8, (s)) for all 8 E S. To achieve the desired sample
efficiency in terms of the minimum sample size, Li et al. (2020) recursively defines the auxiliary
values:
h Rxi
0 (1 - (1=)P=>*
0 (1 (Pa) hg
(A.4)
hT = o
of (I - > -P=
07 (1 - PPa) -1 -2p
for all 1 2 1. Using these sequences and the techniques in Wang et al. (2023). we are able to show the following concentration bound:
Proposition A.1. Assume Assumption and for some 17 1, P(Ln)
8/3. For 2
(4)8(()) - -7)-1 then w.p. at least under P
B muinorize
BB(n) It minorize
10
00 ão
S 243
and
vo 1o < 486
To
(1 72
(1 7
where
|4|[S||A| ((1 7)
35(1) log
(1 1 2n0
The proof of Proposition A.1 is provided in section C.2 We see that the conclusion of A. will
resemble the statement of Theorem if P(),)) > 1 8/3 3 as well as to
To z v" and up to ~ n are
sufficiently close. The following proposition Li al. (2020) proves the former requirement.
Proposition A.2 (Lemma 6, Li et al. (2020)) Let
cō(1 -7)
then P(I);;) 2 -8/3.
12

---

Published as a conference paper at ICLR 2024
A.1 PROOF OF THEOREM 1
Now, we ready present of proof of Theorem given Propositions A. and A.2
Proof. Observe that for any æ E II, by the construction in (A.4)
" = (T - p RT = + -1 -1-7p=) 17
Therefore,
|100 v01ooc s -[1(1-7P3)) 110,000 I 5
1-7
Consider
Uº 00 = (u* - 10 (v))
- -0 ) + (1) -10 + (v) x²))
2ç
1 + no vo
where the optimality of no implies that oi 1 8-6 8
00
2 O. By Proposition A.1 and A.2 w.p. least
Ba(ng ) Uminorize
I 486
(1 1
provided that
To arrive at the sample complexity bound, we first note that (1(5)) has log dependence on Ç. Choose < (1 7)e/4 and for 4 4862.
n = Aminorize:3$(13 =ō - ((1 2)
(minoriae
(1 7)
Then for e S V tminorize (1 ----1 643s(13) (11)()))(117)) and w.p. at least 1 -
-
486c
w² n0 +
Ve
B REDUCTION BOUND AND OPTIMAL SAMPLE COMPLEXITY FOR AMDP
This this section, we prove Theorem given the DMDP optimal sample complexity result Theo- rem[] To achieve this, we need the following lemma that allows us to compare the long run average value and the discounted value of the MDP. From Lemma Din Sidford (202I) and Theorem 1 of
Wang et al. (2023) (c.f. equation 2.3 ). we have that
Lemma 1. Under Assumption for all II.
[I >)== at 1loo S 59(1 tminorize
B. PROOF OF THEOREM 2
Given Lemma and Theorem we present the proof of Theorem 2
Proof of Theorem First, note that (1 7) 1 > minooriee 1. By Theorem ] and the choice of and n, the policy To satisfies
2 80
tminorize
w.p. at least 8.
13

---

Published as a conference paper at ICLR 2024
Let denote optimal policy of the average reward problem. Then, w.p. at least 1 1-6, 6,
a (1 - 7) (1 7)(=** v²] (1 7)(0"- v + [(1 7)0 R0 {
á
(1)
S [ (1 - >>)= + (1 - 7) v + [[1 - -7)000 - a
9(1 Minuorize + (1 7) minorriz + 9(1 - 7) 7
(18)
where (i) uses the optimality of n², (ii) follows from Lemma and the /minorize-Opimmali of ao.
(iit) is due to the choice = 196mstorize
The total number of samples used is
| Ō (1 7)
[S||A] mimnniiz
=ō
(|S||AA|(
22
This implies the statement of Theorem
C PROOFS OF KEY PROPOSITIONS
C.I DECOUPLING THE DEPENDENCE OF AND no
In this section, introduce the method proposed by Agarwal al. (2020) decouple the statistical dependence of Paraa' and f at a particular state action pair (s', E S A. To simplify notation,
(s'.a") E S x A to denote pair of state and action. Define the kernel (())
(2) Ra,a E P(S) (8, E x A s.t. n 8g and (2) Ús.a for all (s,a) * z. Therefore, Now, for fixed p R. define modified reward
under (*)) and at state action pair (s',a'), the MDP will transition to s' w.p.1, while other transitions are done according to P.
h (2.P)) (s, = pll {= = (s, a)) Rn + (0, a),
Let g(2,p) be the unique solution of the Bellman equation
g(s) ) = max
(n (1(20)) (8, + >n(()(o1)
aEA
Let ((2.P) be any optimal policy associated with g(2.P), Now notice that since A 8g non- random. Thus, g(z-p) and ((*-)) are independent of P2. By the definition of the auxiliary value functions in expression (A.4) above, 1/ (2.00 := up (((x))) is also independent of p.. Therefore, if we define G. == ofp,a (s,a) A z, R), then of (2.PP) is measureable w.r.t. G..
Therefore, we can decouple the dependence of P... and do by replacing #n with {(2, p) for some P that io x( with high probability. To achieve this, first preseribe finite set (a g-net of the interval [-(1 1-(1-))-1 ,1 -] that will be denoted by Ni) of possible values for and prove that for sufficiently small E, such a p can be picked from this set. Note that the motivation for constructing Ns and seeking P within it stems from the finite nature of this set, which enables us apply the union bound technique.
Concretely, define an E-net on (1
NV = (-ke -(ke - .,, O,...,(k,, - 1)E, kgE]
where lig (1 (1- Note that, We < 2(1 -16-1 Then the following lemma in Li et al. 2020 indicates that it is sufficient to set g = (1 7)m/4 where we recall that is the optimality gap parameter of the event P. A.3).
Lemma 2 Li et al. (2020), Lemma 4). For each E x A, there exists Ps E N(112)n44 S.t.
(w)) #o( for all Sty
14

---

Published as a conference paper at ICLR 2024
With this decoupling technique and policies x(2,
approximate vi by ot (2.0) with P=
N (n/44/ In particular, the following concentration inequality for uf (2-0)) can be translated to that of of Ro leading our proof of Proposition A.1
Lemma (Bernstei''s ' Inequality). For each & E S x A, consider any finite set U C R, then w.p.
at least å under P, we have that for all S 1", E A
[6:
p=)
(1) (.)p)
11
B o (2xp) (2)
B 1/
(2.p)
span
where
2|
= 21og
and [U] == supaesxA [U(+))
This lemma proved Appendix D.I We note that, of course, N(1-22/44 Nourse.Na-s>wwi (1=))
will used in place of
C.2 PROOF OF PROPOSITION A.
Before we prove Proposition A.1 we introduce the following lemma that converts Bernstein-type inequalities for {rr} in Lemma to concentration bound of ûo-
Lemma 4. Fix any > 0 and possibly data dependent policy i(w) E IL Let B c s.t.. Yo E B, the sequence (vf) defined in (A.4) satisfies
b $ V
(Px P*)
span
for all 1ogg((1 - (11-))-1) where the absolute value is taken entry-wise. Then
minooiize
1100 - v 11.0
I 243
2
on B, provided that n 2 64b(1 - -1
The proof of this lemma is provided in Appendix D.2 Note the appearance of minnrriee in the bound. This is consequence of the analysis technique in Wang et al. (2023). With the above auxiliary definitions and results, we prove Proposition A.I
Proof of Proposition A.l replaced by 8/3 and ((=) by N(117)9/44 there exists B C s.t. P(B) 2 1 8/3 and B S2
We proceed with proving the first bound. By Lemma 2 and with
(0= p=) 10
(0= -p=) [of pp
Br(1)
3s(n)
(2.Pe)
n
Ispan
BB(1) (1)
Bo(1))
-
50 (2)
+
n
Jpan
for 0 15
log, (1-7)-11) ==
E A. p (=).
In particular, on 2,
Bs(n)
Bs(n)
(Pro - - oof I
Fao (u
span
all 0 S 1 S l", Therefore, we conclude that by Lemma
Ba (1)) minurrie
0
50
to
243
(1 Pn
15

---

Published as a conference paper at ICLR 2024
on B n S.y. Sinece P(L,)) 2 1 6/3, apply union bound, one obtains the first claimed.
To prove the second claim, we note that
I to 1
(%) 0 + (%0
100
:50)
+
R0 #o
100
< 11 o no
~0
+
50 00
V0
5o
where the last inequality follows from 00 0
S O. Hence, it remains to bound ||00 60 1l
It is easy to see that the same proof of Lemma 3
implies that
(o(T))
(5(1) 7
(P=o
Pao 2o0 -
(2
Ro
n
span
for all 0 0-15'" 1" w.p. at least 8/3. Therefore, by Lemma
Mminrrinn
11 - 11 I 243
w.p. at least 1- 8/3. Again, application of the union bound completes the proof.
D PROOFS OF AUXILIARY LEMMAS
D.1 PROOF OF LEMMA 3
Proof. Recall that G2 = afs, (s) + 2, R). For each S A, define the probability
measure P.(-) == P(1G22) and expectation E-[.] = El-19.]. Fix any 0 s l* and p E (*)).
Since (f= [1][1] = 0.
(02 -ps) 1 (2.0))
S 2 (2.p)
span
As p. is independent of Gz, and of2xP) is measureable w.r.t. Gz,
p=) Therefore, by Bernstein's inequality, for any 1 2
E. (Ø= -p))
[of [/(=P))
0.
Ps (((==-Pi) P&) [ffww)]] >t) S exx
222
2no² (2.0)) (z) + (2,0)
nt
span
Choose s.t. the r.h.s. is less than 8/(($)]A[[()0)) we find that it is sufficient for
[1S||A111 e
(2.0)
t2
2 log
8
(2.p)
(2) +
log
2 (
span
3
5
Clearly
B (o (2.p)
(z.p)
t0 =
+
n
span
satisfies the above inequality. Therefore,
(Ā= p=) (1(=10) 10
P
max
max
SESxAA pEt(())
Σ
Σ
EP. ((b= - p=) -p))
[000 > to)
,288 PEU(()
Σ
A
(EU(()
<
This directly implies the statement of the lemma.
16

---

Published as a conference paper at ICLR 2024
D.2 PROOF OF LEMMA 4
Proof. First, observe that by the definition in (A.4.
of of (T (I- ([=- (I-
= (I 7 (1
7I (1-->++jut - - - (1 7
P=)
Let us define A = B in the lemma,
00 of al By the assumption of Lemma for all 0 S 1 1", on the event
(
M( - -ppx) (P= - P=)uū² 11
A
(1)
b
|| - --a-
oz (15)) 111
7b
+ (1 7/n
|of
span
(D.1)
yb
VV | 00
(1 117m
Ispan
b S TV - ALt + m
7b
n
|
1
+
(1
7)n
|u8
ssan
where (i) and (it) follow from (1 - P being non-negative so that (1 (1- S (1
7 -P S (7 77- g for all function S - IR and 2 [h]-
We think of (D.1 as recursive bound for 4g To analyze this recursive bound, we first consider the following. By Lemma 11 of et al. 2020), we have that for / 2 0
1o 1oo = ||( - [[-I>Pa)
S
110 1lo
7v1
(D.2)
s...
4
VvI
Therefore, expanding the recursion
D.I
Au V b D +
b v
7b
100 span
n n
(1
r"
1 1
&
76
A.- +
7
-
|| 1l.0
+
VV
(1
7)
n
span
k=
Since of 2 0 for all 1: 0. llp
|o llo We have that
Ispan
b r'
A. + (1+
76
76
4o <
TV
|
+
100
[1 7)m
(1
7)
lpan
(D.3)
1=1
=: Ej + Eg + Es
17

---

Published as a conference paper at ICLR 2024
We first consider Eg. By the identities
(D.1) and D.2
b
yb
A s v n2
(I (Pa) oz (of)
+ (1 7)m2
10
lspan
10
7
V
1 (uf 11.00 +
76
|o{-
1
(1 - 7)
Ispa
7
76
|| 20
+
(1 7)
(1 - (1
+ 7b
(n/11 -7)
1--1
1
V
(1 -1-2 7)
(1-7)n
73
b
(7/1 -~=1-))
4
) l1ofllo
+
4
7)
(1 7)
2 72
b
4
||02ll00
2
(1 - 7)m 17
where (i) follows from n 2 11(11 - 7). Therefore,
72
166
(1111/22
E1 5 2 7 (1 (1--70 7)m
|o
n
b
2-11" (1*+2)
vI
(1g
b
(1082(1-7)/2
where (i) follows from the assumption that n 2 64b(1->) and (ii) is due to 8" 12 > 1ogg(())
))
Next, we bound Eg. By D.2
Eg < M
b
K |
MV
(
2
n
A
16b
< 27
1
(1-
k=
< 2/
Also, note that v0 Corollary 6.2.1 of Wang et al. 2023)
(I P3
x and of = -1- 7Pp) 1o=
(o*). By Proposition 6.1 and
< 80 / tminorize
and ||
10 span minoorize
Thus we conclude that
b
7 (1
An
3
U0 span
n
7)m
1
bt btminarize
3bt minorine
240
1
bt biminoriiz
< /
(1 72
18

---

Published as a conference paper at ICLR 2024
where the last inequality follows from Einoorize $ (1 -1)- and so minoorize /n S 1 by assumption
on 71.
19


Reviews:
[{"review_id": "AJ65kIqvdi", "reviewer": "Reviewer_fwUc", "summary": "This paper resolves the issue of sample complexity associated with maximizing the long-term average reward dictated by a uniformly ergodic Markov Decision Process (MDP), predicated on the assumption of a generative model. The findings of this study enhance the pre-existing results by a factor of $t_{mix} and align with the established lower bound. The algorithm introduced herein is a synthesis of the methodologies proposed by Jin & Sidford (2021) and Li et al. (2020).", "questions": "1. The paper could benefit from a greater emphasis on the challenges addressed by the study. Could you provide more information on the specific challenges inherent to the problem you are solving and how your approach effectively addresses these issues? \n2. Could you please elaborate on the unique aspects of your algorithm and how it distinctly contributes to the field beyond the synthesis of methodologies from Jin & Sidford (2021) and Li et al. (2020)? Highlighting the novel components of your approach could significantly strengthen the impact of your paper.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper addresses a significant issue in the domain of Markov Decision Processes, providing a solution to the sample complexity associated with maximizing the long-term average reward. This is a valuable contribution that could potentially advance understanding and application in this area.\n2. By enhancing pre-existing results by a factor of the mixing time and aligning with the established lower bound, the paper provides a comparative analysis that underscores the improvements made and the relevance of the studies.\n3. This paper is well-written and easy to understand.", "weaknesses": "1. The algorithm is primarily a synthesis of methodologies from Jin & Sidford (2021) and Li et al. (2020). While this approach has its merits, the novelty of this paper is somewhat limited given its dependence on previous works.\n2. The paper could be enhanced by placing greater emphasis on the challenges addressed by the study and the innovative aspects of the proposed algorithm. Highlighting these elements would help to showcase the unique contributions of the paper and further establish its significance in the field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "gMRWrWW12o", "reviewer": "Reviewer_qCaw", "summary": "The authors presents the sample complexity result for the average-reward Markov Decision Processes (AMDPs) under the assumption of ergodicity and with an access to a simulator. This sample complexity is nearly minimax optimal in the class of ergodic MDP, thus closing the gap in mixing time or desired accuracy that appears in previous works. The presented algorithm is basically applies the reduction technique from AMDP to DMDP and efficiently exploits ergodicity assumption in the DMDP setup.", "questions": "- What are main barriers to provide an algorithm with dependence not on a mixing time-type quantity but on span of optimal value? This questions has its importance because it is know that this guarantee will be strictly tighter than mixing dependent.\n- Is it possible to provide an algorithm without a reduction to discounted setting?\n- Is it possible to extend this approach to exploration setup and provide a feasible algorithm with guarantees like (Orther, 2020)?\n\nOrtner, Ronald. \"Regret bounds for reinforcement learning via markov chain concentration.\" *Journal of Artificial Intelligence Research* 67 (2020): 115-128.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- First minimax optimal guarantees for AMDPs under a generative model assumptions;\n- As a byproduct, authors provide minimax optimal  for ergodic DMDPs\n- Computationally feasible algorithm;\n- Simplicity of the presented approach.", "weaknesses": "- All the main instruments has already introduced in other papers, and thus this paper may lack of novelty.\n    - Reduction of AMDP to DMDP is presented in (Jin & Sidford, 2021)\n    - Optimal rates with optimal warm-up are presented in (Li et al. 2020);\n    - Rates for mixing DMDP are already presented in (Wang et al. 2023) (specifically, Proposition 6.1 and Corollary 6.2.1);\n\nYujia Jin and Aaron Sidford. Towards tight bounds on the sample complexity of average-reward\nMDPs, 2021.\n\nGen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier\nin model-based reinforcement learning with a generative model. In H. Larochelle, M. Ranzato,\nR. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems,\nvolume 33, pp. 12861–12872. Curran Associates, Inc., 2020.\n\nShengbo Wang, Jose Blanchet, and Peter Glynn. Optimal sample complexity of reinforcement\nlearning for uniformly ergodic discounted Markov decision processes, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "tnRzZIdsuT", "reviewer": "Reviewer_tPAf", "summary": "The authors considered the sample complexity of average reward MDPs under the uniformly ergodic condition, and provided a novel analysis for the algorithm given in Li et al. 2020, which results in an upper bound that matches the known lower bound.", "questions": "1. I'm a little confused about some notation. Is alpha in (2.6) in R^|S|? It should be, but later in the definition of \\bar{alpha}, we need to choose the maximum alpha, which seems incorrect since it is a vector. \n2. Equation (2.4), where is \\eta defined? It seems to appear without any context. \n3. Can you comment on the choice of distribution of Z(s,a)? Does it make a difference if another distribution (non-uniform) is used?\n4. Though I can understand the result is theoretical, have the authors used any numerical results to verify the optimal algorithm behavior that suggests the sample complexity scaling?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Theoretical paper that gives a matching bound, therefore fully establishing the optimal sample complexity for AMDP under the uniform ergodicity condition.\n2. The background was explained clearly, and the context of the result to other related settings is also well explained.\n3. In most places, the notations and proofs are done rigorously, more so than the average papers.", "weaknesses": "1. The result is somewhat thin in the sense that it feels like filling a small gap that was somehow overlooked by several previous groups of researchers, though I personally like the cleanness of the result. \n2. The main contribution is technical, yet the main paper does not really spend the effort to clearly explain the technical critical point that enables the authors to establish the bound. Particularly, it appears Proposition A.1 is the critical step to establish the concentration inequality. More discussion on the technical level on the difference with previous bounds should be given.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "nfAbfLRSWE", "reviewer": "Reviewer_iFE8", "summary": "This paper studies the sample complexity of learning the optimal policy in average-reward Markov decision processes, under the assumption of a uniformly ergodic MDP and a generative model. The proposed algorithm improves the best sample complexity upper bound in existing works and matches the lower bound of the problem. This is achieved by combining the algorithmic ideas of two lines of existing research, by first reducing the AMDP to a discounted-reward MDP and then establishing an optimal sample complexity upper bound in the setting of uniformly ergodic discounted MDPs.", "questions": "Does your work imply any new results for the case where the uniform ergodicity assumption does not hold, such as the weakly communicating AMDP setting?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper studies an important problem in reinforcement learning theory. It closes the gap between the upper and lower bounds of the sample complexity for learning an optimal policy. The technical proofs look solid as far as I can tell. The presentation of the algorithm and analysis is also clear.", "weaknesses": "As the authors have mentioned in the paper, the algorithm is developed by combining the algorithmic ideas from two lines of existing research (Jin & Sidford, 2021) and (Li et al., 2020). While in general we would hope to see technical novelty in terms of algorithm design, it is probably okay with this work because reducing to a discounted MDP (Jin & Sidford, 2021) seems to be a standard approach, and the authors do make improvements over the analysis of (Li et al., 2020) to establish a sharper sample complexity upper bound. \n\nEven though I understand that the main contributions of this work are theoretical, I would still hope to see some numerical results to demonstrate some of the ideas in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)