Near-Optimal Sample Complexity for MDPs via Anchoring
Authors: Jongmin Lee
Mario Bravo
Roberto Cominetti
Venue: ICML 2025 poster (2025)
Keywords: Average-reward MDP
Generative model
Sample complexity analysis
Value iteration
Halpern iteration
Variance reduction sampling
Reinforcement learning theory
Primary area: theory->reinforcement_learning_and_planning
TL;DR: We propose a near sample optimal model-free algorithm for weakly communicating average reward MDPs which is implementable without prior knowledge

Abstract: We study a new model-free algorithm to compute  $\varepsilon$-optimal policies for average reward Markov decision processes, in the weakly communicating setting. Given a generative model, our procedure combines a recursive sampling technique with Halpern's anchored iteration, and computes an $\varepsilon$-optimal policy with sample and time complexity $\widetilde{O}(|\mathcal{S}||\mathcal{A}|\||h\||^{2}/\varepsilon^{2})$  both in high probability and in expectation.  To our knowledge, this is the best complexity among model-free algorithms, matching the known lower bound up to a factor $ \||h\|| $.  Although the complexity bound involves the span seminorm $ \||h\|| $ of the unknown  bias vector, the algorithm requires no  prior knowledge  and  implements a stopping rule which guarantees  with probability 1 that the procedure terminates in finite time. We also analyze how these techniques can be adapted for discounted MDPs.

Near-Optimal Sample Complexity for MDPs via Anchoring
Jongmin Lee Mario Bravo?
Roberto Cominetti
Abstract
memory requirements, specially when combined with func- tion approximation techniques for large scale problems.
We study a new model-free algorithm to compute E-optimal policies for average reward Markov de- cision processes, in the weakly communicating setting. Given generative model, our procedure combines recursive sampling technique with Halpern's 's anchored iteration, and computes an e-optimal policy with sample and time complex- ity ([[S)|-A]]]> Ilpp/" both in high probability and in expectation. To our knowledge, this is the best complexity among model-free algorithms, matching the known lower bound up factor || Although the complexity bound involves the span seminorm |lh*|l |lap of the unknown bias vector, the algorithm requires no prior knowledge and implements a stopping rule which guarantees with probability that the procedure terminates in finite time. We also analyze how these techniques can be adapted for discounted MDPs.
The sample complexity of model-free algorithms has been studied both in the discounted and the average reward se- tups. While for discounted MDPs these procedures have been shown to achieve optimal sample complexity, previous results for average rewards are less satisfactory and exhibit substantial gap with respect the known lower bound, Furthermore, most prior model-free and model-based algo- rithms for average reward MDPs require for their implemen- tation some a priori bound on the mixing times or on the span seminorm of the bias vector.
1.1. Our contribution
We propose a new model-free algorithm to compute an g- optimal policy for weakly communicating average reward MDPs. We show that, with probability at least - 8, the algorithm achieves the task with sample and time complex- ity of order ( A
||| h" llpp/ /22). Here S and A are the state and action spaces of the MDP and ||A" [l is the span seminorm of the bias vector described later in Section 1.2, while L = In(| |||||/>" (=6)) In (l]h* lsp//) is a log- arithmic multiplicative factor. This yields a near-optimal algorithm since this complexity matches the known lower bound up to a factor || More explicit estimates of the algorithm's 's complexity are discussed in Section 3.2.
1. Introduction
A main task in reinforcement learning is to compute e-optimal policy for Markov Decision Processes (MDPs) when the transition probabilities are unknown. If one has access to a generative model that provides independent sam- ples of the next state for any given initial state and action, a standard approach in model-based algorithms is to approxi- mate the transition probabilities by sampling to a sufficiently high accuracy, and build surrogate model which is then solved by dynamic programming techniques. In contrast, model-free methods recursively approximate solution of the Bellman equation for the value function, with lower
Our algorithm can be implemented without any prior knowl- edge about [|*[|sp nor other characteristics of the optimal policy. Also, it implements a stopping rule which guarantees with probability that the method finds an e-optimal policy in finite time, with the above complexity bound holding both in high probability as well as expectation. This compares favorably to previous model-free and model-based methods which usually require some prior estimates of the span semi- norm l1pp or an upper bound for the maximal mixing time fmix (see Table I and Section 1.3). To our knowledge, the only algorithm with explicit complexity guarantees and which does not require prior knowledge is the model-based method in the recent paper by Tuynman et al. (2024), which however applies for communicating MDPs, achieving complexity bound of Ō ((S))A) + |S|2|A| where D stands for the diameter of the MDP.
'Department of Mathematical Sciences, Scoul National Uni- versity, Scoul, Korea FFaulltdd de Ingeniería y Ciencias, Uni- versidad Adolfo Ibáñez, Santiago, Chile 'Institute for Mathe- matical & Computational Engineering and Department of Indus- trial and Systems Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile. Correspondence to: Jongmin Lee <dlwhd2000@ auw.cc..r>.. Mario Bravo < www.bbrrvvaiii.oooooo Roberto Cominetti <roberto.comine www.ietimmu.cll........
+
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
The core of our analysis builds on the following key ideas.

---

Near-Optimal Sample Complexity for MDPs via Anchoring
Previous works
Sample complexity
Method type
MDP class
Prior knowledge
Wang (2017)
Ô [
mmix/ /E²)
model-free
M
Jin & Sidford (2020)
0 (|S) |A| 12 mix /22)
model-free
M
Jin & Sidford (2021)
0 ([S] |A| Fmixx )
model-based
M
Li et al. (2024)
Ô (|S] | 1 mixx / /=2)
model-free
M
Wang et al. (2024)
Ô ([S] mmxi
model- based
M
O
Wang al. (2022)
Ö [|8]|||]]] || /spp
model-based
W
Zhang Xie (2023)
Ô [[S]]A 11p////)
model-free
W
Zurek & Chen (2024)
δ ([S)] (1s)s/
model-bate based
W
Zurek & Chen (2024)
Ö [I + | (lpp)))))
model-based
G
O
Jin et al. (2024a)
δ [[S]]A4) mix/ 1
model-free
M
A
Bravo & Contreras (2024)
δ ([S]| |/" 11 (1p//²)
model-free
W
Zurek & Chen (2025)
0 [18)|A]]]
model-based
W
A
This work (Theorem 3.2)
Ô ([5)
11g./
model-free
W
A
Tuynman et al. (2024)
Ö ([SILA|DD/E)
model-based
C
X
This work (Corollary 3.5)
model-free
W
Table Algorithms for average reward MDPs. The table shows the leading term in the sample complexity for computing e-optimal policy with probability at least 5. The notation O(-) hides logarithmic factors including log(1 The column 'MDP class' distinguishes the type of MDP which the algorithm applies: (M) uniformly mixing ergodic MDPs with finite mixing times faixi (C) communicating MDPs with finite diameter D: (W) weakly communicating MDPs with bias vector h" and (G) general MDPs with transient parameter Owa- The symbol 'O' denotes algorithm that requires prior knowledge fmax, ||h" ll.. duan for implementation. Similarly, '2' stands for algorithms that run without prior knowledge but require it to fix the number of iterations or the number of samples. Finally applies algorithms that do not require any prior knowledge, For more thorough discussion see Section
First, we show that any approximate solution of the Bell- man equation with an residual error yields an e-optimal policy. To achieve an accurate empirical estimation of the Bellman residual error, use recursive sampling tech- nique analyzed using Azuma- Azuma-Hoeffdhnn Hoeffdooe- inequality. Leveraging these estimates, we draw concepts from the domain of fixed-points for nonexpansive maps, where the classical Halpern (or Anchored) iteration is known to be efficient (see Section 1.3 for a detailed discussion). This combined approach represents our main contribution and, to the best of our knowledge, is being applied for the first time average reward MDPs in the generative setup. In the last section we adapt these ideas to study similar algorithm for discounted MDPs and compare with other existing methods.
erences (Bertsekas, 2012; Puterman, 2014; Sutton & Barto, 2018). We consider Markov decision process A, A, with finite state space S, finite action space A, transition kernel P: S A - A(S), and reward S A - R. Given an initial state so and stationary and determin- istic control policy S + A, the average reward or gain In E R$ is defined by
(x(s) = lim Ex n
E r(s,, | sp
where E,, denotes the expected value over all trajectories (so, dg, $1, ....... St, ......) of the Markov chain induced by the control = (sx)) with transitions 8t+1 ~ P( oz). The optimal reward is then g" (s) )) = max, Ir (s). A policy и is called e-optimal if < g" (s) - g (8) () S e for all E S.
Notations. For finite set J we denote (JJ) the set of probability distributions over J. Also, for E RJ we denote by ||0||00 = maxjed [x]]] its infinity norm and by ||r||ap = maxje. =xj)) - minje. æ(j) its span seminorm. For r IR and a real number E IR, we denote x - the vector with components z(j) for all E
Although one could consider more elaborated history- dependent randomized policies ग,, when S and A are finite the optimum is already attained with the simpler determin- istic stationary policies (Puterman, 2014), such policies and we denote P, the transition matrix of the induced Markov chain, namely, Pr (s'(s) P(s'l T())..
restrict to
1.2. The model
Let us recall some basic facts about average reward Markov decision processes. These can found the classical ref-
Classification of MDPs. An MDP is called unichain the Markov chain P- induced by every policy π has single
2

---

and then taking actions TT8) = =a E A that attain the max. This Bellman equation always has solutions (Puter- man, 2014, Corollary 9.1.5). Under the assumption (H) the gain g(s) = g" is constant across all states with g the opti- mal average reward (Puterman, 2014, Theorems 8.3.2, 8.4.1, 9.1.2, 9.1.6) so that hereafter we treat the gain 9" (s) as scalar 9* E R. Moreover, (Puterman, 2014, Theorems 9.1.7, 9.1.8) show that choosing actions that maximize the right hand side in the Bellman equation yields an optimal policy. Near-Optimal Sample Complexity for MDPs via Anchoring
recurrent class plus possibly empty set of transient states!. The MDP is said to be weakly communicating if there is set of states where each state in the set is accessible from every other state in that set under some policy, plus pos- sibly empty set of states that are transient for all policies. Otherwise, the MDP is called multichain in which case each Pr may have multiple recurrent classes. Unichain MDPs are weakly communicating, while multichain is the weakest notion. In this paper we set our study in the middle ground by adopting the following standing assumption:
1.3. Previous work
Average reward MDPs. The setup of average reward MDPs was introduced in the dynamic programming litera- ture by Howard (1960), while Blackwell (1962) established theoretical framework for their analysis. Reinforcement learning provides a variety of methods to approximately solve average reward MDPs in the case where the transi- tion matrix and reward are unknown (Mahadevan, 1996; Dewanto et al., 2020). These methods include model-based algorithms (Jin & Sidford, 2021; Zurek & Chen, 2024), model-free algorithms (Wei et al., 2020; Wan et al., 2021), policy gradient methods (Bai et al., 2024; Kumar et al., 2025), and mirror descent (Murthy & Srikant, 2023).
(H) The MDP AS,A,P,)) is weakly communicating.
Bellman's equation. An optimal policy x can be obtained by first solving the following Bellman equation for the gain g E TRS and bias h E TRS namely: for all 8 E S
Model-based methods with a generative model. Model- based algorithms use sampling to estimate the transition probabilities of the MDP, and then solve the surrogate model by using standard dynamic programming techniques. These methods can achieve optimal sample complexity in both the discounted and average reward setups. For discounted MDPs, Agarwal et al. (2020); Li et al. (2020) achieve opti- mal sample complexity by matching the lower bound in Azar et al. (2013). For average reward MDPs satisfying a uniform mixing condition, Jin & Sidford (2021) proposed model- based algorithm based on a reduction to discounted MDP. Also using reductions to discounted MDPs, (Wang et al., 2022) relaxed the uniform mixing assumption to deal with weakly communicating MDPs; Wang et al. (2024) achieved optimal sample complexity assuming finite mixing times; and, Zurek & Chen (2024) achieved optimal complexity for weakly communicating and multichain MDPs.
(s)) + g(s) = max (r(s, + Σ P((5),,)))))) aEd
e'ES
Bellman's 's equation can be rewritten in terms of the so-called Q-factors Namely, denoting Q(8, a) the expression inside the maximum, the system becomes: for all (s, a) E S x A
Q(s. a) 9" as) + Σ P(s''ss, (s,a) a) max Q(s', aa), ''ES
a'EA
and then an optimal policy can be obtained by selecting (()) E argmax a(s,a).
Model-free methods with a generative model. Most model-free algorithms directly estimate the Q- Q-factors and policy without learning a model of the transition probabil- ities. They are more efficient in terms of computation and memory requirements, and can tackle large scale problems when combined with function approximation.
This Q-version of the Bellman equation can be expressed more compactly as the fixed-point equation?
Q Q P (Q) -g"
where max : SSSAA + R assigns to each Q S the vector h E R with h(s)= = max Q(s,a),, whereas P R - SSA transforms each h R into the matrix Phe E S with Ph(s, a) = -ves ((sl(ssa)((ss)) a))(s").
In the generative model setup (Kearns & Singh, 1998) the sample complexity of model-free algorithms has been widely studied. For discounted MDPs they achieve op- timal sample complexity matching the complexity lower bound (Sidford et al., 2018; Wainwright, 2019; Jin et al., 2024b). For average rewards, Table I presents a summary of the sample complexity of previous model-free and model- based algorithms. Specifically, for MDPs with finite mixing times fmix. Wang (2017) developed model-free method that applies primal-dual algorithm to a bilinear saddle point reformulation of the Bellman equation. Also under the mixing condition, Jin & Sidford (2020) use stochas- tic mirror descent framework to solve bilinear saddle point problems, whereas Li et al. (2024) studied an actor-critic method also based on stochastic mirror descent. Zhang
In what follows we denote T RSAA + S the map T(Q) = r + P max so that Bellman's 's equation re- duces to Q- = (Q(()) with T₂- (Q) = T(Q) - g" We denote Q* an arbitrary fixed-point, and h- maxa((") the corresponding solution for the original form of Bell- man's 's equation.
For basic concepts Markov chains such as recurrent classes, transient states, accessibility, irreducibility, etc., we refer to Puter- man (2014, Appendix A.2). RReall that for matrix B E RRSAA. and real number g E IR, the operation B- g subtracts g from each component B(,, a).
3

---

Near-Optimal Sample Complexity for MDPs via Anchoring
& Xie (2023) first obtained sample complexity results for weakly communicating MDPs, by applying Q-learning with variance reduction to approximation by a discounted MDP. Lower bounds on the sample complexity for mixing and weakly communicating MDPs, with orders of fmxx/e" and [| llsp/ respectively, were established by Jin & Sid- ford (2021) and Wang et al. (2022).
the first methods considered in the dynamic programming literature (Bellman, 1957) and serve as a fundamental algo- rithm to compute the value function for discounted MDPs as well as unichain average reward MDPs. The sample-based variants, such as TDD-Lerrning (Sutton, 1988), Fitted Value Iteration (Ernst et al., 2005; Munos & Szepesvári, 2008), and Deep Q-Network (Mnih et al., 2015), are the workhorses of modern reinforcement learning algorithms (Bertsekas & Tsitsiklis, 1996; Sutton & Barto, 2018; Szepesvári, 2010). VIs are also routinely applied in diverse settings, includ- ing factored MDPs (Rosenberg & Mansour, 2021), robust MDPs (Kumar et al., 2024), MDPs with reward machines (Bourel et al., 2023), and MDPs with options (Fruit et al., 2017). In the generative model setup, variance reduction sampling was applied approximate VIs for discounted re- wards: Sidford et al. (2023; 2018) use precomputed offsets to reduce variance of sampling, Wainwright (2019) applies S SVRG-type variance reduction sampling (Johnson & Zhang, 2013) to Q-learning, and Jin et al. (2024b) use SARAH-type variance reduction sampling (Nguyen et al., 2017) which we also exploit in this work.
Prior knowledge. A drawback of these previous model- based and model-free algorithms is that their implementa- tion requires prior estimates for the mixing times fmix of the Markov chains induced by all policies, or the span seminorm [|p* of some solution of Bellman's equations. Several methods that partially overcome this limitation have been proposed recently. In the case of finite but unknown mixing times, Jin et al. (2024a) combine Q-learning and approxima- tion by discounted MDPs with progressively larger discount factors, presenting a model-free algorithm with sample com- plexity of order 1 /s". For weakly communicating MDPs, Bravo& & Contreras (2024) develop a model- free value itera- tion that combines Halpern's 's anchoring with mini-batching. achieving sample complexity of order ||4* ||4" /e7. Also in the weakly communicating setting, Zurek & Chen (2025) recently proposed a model-based algorithm that uses a dis- counted MDP approximation with a sufficiently large dis- count factor, which is then solved by plugging in a generic subroutine, achieving a complexity of ||1" Addi- tionally, Neu & Okolo (2024) use a primal-dual stochastic gradient descent combined with a regularization technique, although the sample complexity is not stated in terms of the intrinsic characteristics of the MDP but in terms of the output of the algorithm, namely, using the expected value of the gain of the policy generated by the method.
Halpern iterations. For 7-contractions on Banach spaces,
the classical Banach-Picard iterates *++ = T(x*) con- verge to the unique fixed point x = T(x*), ). with explicit * S 7 (xx)) - x0Il
bounds for the residuals [|T(**)
and the distance ||.* - - I (T(=)))) 201 to the fixed point. This fits well for discounted MDPs, and is also useful in the average reward setting for unichain MDPs.
For nonexpansive maps with y = 1, as it is the case for average reward MDPs, these estimates degenerate and pro- vide no useful information. An alternative is provided by Halpern's 's iteration *++11 = (1 f )a² + BR+1 T(x*"), where the next iterate is computed
Although the implementation of these methods does not involve explicitly the mixing time mmix. the diameter D, or the span seminorm ||4*||ap of a bias vector, they do need an estimate of these quantities in order to fix the number of iterations that need to be run or the number of samples to collect in order to guarantee E-optimality. In this sense, they fail to fully dispense for the need of prior knowledge. To the best of our knowledge, the only algorithms that can run without prior knowledge and guarantee at termination an e-optimal policy are the model-based algorithm by Tuyn- man et al. (2024), which applies to communicating MDPs by estimating the diameter D, and the model-free algorithm SAVIA+ + presented in this paper which applies to the larger class of weakly communicating MDPs by implementing an effective stopping rule based on the empirical Bellman resid- ual. These latter algorithms achieve sample complexities of order D/e e² and h" / /22 respectively.
convex combination between T(**) and the initial point z. which acts as an anchor point along the iterations (Halpern, 1967). The se- quence 3g E (0, 1) is chosen exogenously and increasing to 1, so that the strength of the anchor mechanism diminishes as the iteration progresses.
Halpern's anchored iteration has been widely studied in minimax optimization and fixed-point problems (Halpem, 1967; Sabach & Shtern, 2017; Lieder, 2021; Park & Ryu, 2022; Contreras & Cominetti, 2022; Yoon & Ryu, 2021; Cai et al., 2022). In the context of reinforcement learning. Lee & Ryu (2023; 2025) applied the anchoring technique to VIs achieving an accelerated convergence rate for cumulative- reward MDPs and the first non-asymptotic rate for average reward multichain MDPs. As mentioned, Bravo & Contreras (2024) applied the anchoring mechanism to Q-learning for average reward MDPs with generative model.
Value Iterations. Value iterations (VIs) an instantiation of the Manach-Picare fixed point iterations- were were among
Assuming that the set of fixed points Fix(T) is nonempty, and under suitable conditions on 3e. Halpern's 's iterates have
4

---

Near-Optimal Sample Complexity for MDPs via Anchoring
been proved to converge towards fixed point in the case of Hilbert spaces (Wittmann, 1992) as well as in uniformly smooth Banach spaces (Reich, 1980; Xu, 2002). For more general normed spaces, the analysis in Sabach & Shtern (2017, Lemma 5) implies that for 3x = k/(k + 2) one has the explicit error bound [|T(x*) - 1 - A+1 ||x0 - x=1l- The proportionality constant in this bound was recently im- proved in the Hilbert setting by Lieder (2021); Kim (2021). For comprehensive analysis, including the determination of the optimal Halpern iteration, see Contreras & Cominetti (2022).
Combining Proposition 2.1 with the general estimate of the Bellman residual error, it follows that
9 9T. (5) s 11 T( S 241 11@ Q"11sp
4
where (8) E argmax (*, Thus (Anc-VI) not only reduces the Bellman residual error but it allows to derive e-optimal policies.
2.3. Estimating T(Q*) by recursive sampling
We are interested in the generative setting where the tran- sition kernel P not known but one can generate sam- ples from P(-|s, a). In this case (Anc-VI) cannot be imple- mented since one cannot compute T(Q*). With a generative model, natural approach is to approximate 7 ~ T(Q*) by computing h = max (Q*) and then collecting samples { ~ P(-ss a) in order to set
2. F Framework overview
2.1. Anchored Value Iteration
As discussed in Section 1.2, Bellman's 's equation is equiv- alent to the fixed point equation Q
(Q) where (Q) = T(Q)- g" with T(Q) r + (Q)) Since A and P are nonexpansive for the norm ||. ol.o in the corresponding spaces, the same holds for Tg- and one might consider Halpern's 's iteration
Th r(, a) + THE ES ( (s²).
We note that the number of samples required to attain a small error scales with the norm of h². In order to reduce the sample complexity, we use instead a recursive sampling technique borrowed from Jin et al. (2024b). The basic idea is to exploit the previous approximation 7 ~ T(Q*-1) and the linearity of the map P. and to approximate ((Q)) by estimating the difference T(Q*) - -T(Q-11) = Pa with d = h h and adding I Specifically, for each (s, a) take my samples 8j PP--|, a) and set
Qu+1= (1- Bx+1) Qo + Bk+1 Tg. (Q*).
(1)
This recursion involves the unknown optimal value g". How- ever, since T(Q +c) T(Q)= + c homogeneous by addi- tion of constants R. one can interpret (1) in the quotient quotient space M S E with E the subspace of constant matrices, and consider instead the implementable iteration where 9" is removed
T' a) T (s, + me Σド d (8)), h 2.
1
Qu+l= = (1 (1- Bo+1) Qº + Bkt1 T(Q*). (Anc-VI)
As explained in Appendix C, both (1) and (Anc-VI) are equivalent up to constants and can be interpreted as a stan- dard Halpern iteration in the quotient space M.
Starting with T = E SXA and h = 0 E R and denoting D* R Pitk the matrix sampled at the k-th stage, we have
Th Th=r+ -1= D'
2.2. Reducing both Bellman residual and policy error
that all the previous estimates {Di) used to ap- proximate T(Q*). The subsequent analysis will show that |d 1kpp can be significantly smaller than ||A* achieving a significant reduction in the overall sample complexity.
From the previous observations, it follows that the error bounds for Halpern's iteration directly translate into er- ror bounds for (An in span seminorm. In particu- lar, Sabach & Shtern (2017, Lemma 5) implies that for 3x = k/(k + 2) (Anc-VI) the Bellman residual error con- verge to zero with the explicit bound in span seminorm
Our algorithms, to be presented in next section, will use as a subroutine the following generic sampling procedure.
A Algorithm 1 SAMPLE m)
IQ"- < 11- Q
Input: d R m N
where Q* is any solution of Bellman's 's equation. Moreover, for weakly communicating MDPs we can prove that any Q with small residual |[Q T(Q) yields an approxi- mately optimal policy. More precisely, adapting (Puterman, 2014, Theorem 9.1.7), we have following result.
for (s,a) E x A do
D(s, a) 1 E d(s,) with sj id P(- s,))
end for Output: D
Proposition 2.1. Let Q E S and π : S + A a greedy policy such that (s) E argmax,EA Q(s, a). Then for all states 8 E S we have 0 S g" (8) < I|Q - [(Q)
For later reference we observe that this subroutine draws | m samples and its output satisfies DD|sp S ||d]|sp In
5

---

Near-Optimal Sample Complexity for MDPs via Anchoring
what follows we focus on the sample complexity, that is to say, the total number of samples required by the algorithms. If we assume that each sample requires constant -time,, then the time complexity of the algorithms will be of the same order as the sampling complexity.
ing the specific choice of number of samples my in the recur- sive sampling, combined with some ad-hoc union bounds.
REMARK. A direct consequence of Proposition 3.1 is that, with probability at least 1 1- the true Bellman residual error I@* 1Q*-777 (QQ*) lsp and the empirical residual | - T [| differ at most by 2s, as results from a triangular inequality for |1-Ilsp and the general estimate ||
3. Stochastic Anchored Value Iteration
Ilsp - 2 1lse-
We may now present our method which combines two basic ingredients: an anchored value iteration and recursive sam- pling. The following SAVIA iteration is our basic algorithm which considers a fixed sampling sequence Cj >> 0 and an averaging sequence Bx E (0, 1) increasing to 1.
In what follows we consider the specific sequences
{
Ck = (n By (k+
(S)
which satisfy 2 Ek== O 1 1 and 3x increasing to 1. These 3e's are the same as in Sabach & Shtern (2017), and provide explicit guarantees for the reduction of the Bell- man residual error. The choice for cs has been carefully tailored to achieve a small sample complexity.
Algorithm 2 SAVIA 6),
Input: Q" E g E N; > 0;8 E (0.1)
a = |n(2 ()
T-1 = =r; h- = 0:30= =0
for k = =0...., n2 do
The following result presents our complexity bound for SAVIA for weakly communicating MDPs satisfying (H).
Q' (1-5x) @ + BB T
h* m )
Theorem 3.2. Assume (H) and (S) and let be the outpul computed by SAVIA(Q", , n, 5). Then, with probability at least (1 - 6') we have, for all s SE S
mm""
d h² h-
mg max I en ||d /
D SAMPLE(d" t m&)
8|1Q0 Q*11ap
T = 7 D*
g" - Ir- (8) S QQ" T(Q")
+ 4s,
+ 2
end for
T" (s) E argmax AEA (s) (Vs S)
with a sample and time complexity of order
Output: (Q", ,""
((L1S)A4((11)) - -Q" 1110"1222/ + n²))
The iteration can start from an arbitrary Qº, including the all-
where L = In((S]]AI(n In 2).
zero matrix. However, if one has prior estimate Q" z Q" (e.g. from a similar MDP solved previously), it may be convenient to start from Qo since our complexity bounds scale with the distance |Q" - @''I=p. In any case we stress that SAVIA does not require any prior knowledge and all the parameters in the algorithm are independent of Q" or h", including the sequences Se, Ck for which we provide specific choice in the next subsection.
The proof exploits Proposition 3.1 and the remark above in order to establish an upper bound of the Bellman residual error. The bound for the optimality gap in the policy error then follows from Proposition 2. The recursive sampling technique is crucial here to attain a complexity that scales quadratically in e, whereas a naive sampling would give a much worse order complexity. Note that L contains only logarithmic factors and is bounded away from 0 so that in our complexity estimates it can absorb any constant factors.
3.1. Sample complexity for the basic SAVIA iteration.
In order to study the sample complexity of SAVIA we first establish conditions which ensure that with high probability the recursive sampling provides good approximations T x T(Q*) for all k's. We only present the main results and ideas, and defer all proofs to the Appendix.
3.2. A model-free algorithm without prior knowledge
Theorem 3.2 shows that SAVIA effective in reducing the Bellman residual error as well as the policy error. Namely, with probability at least 1 - 8, after > ||Q" Q" llsp/ iterations it produces a ooottmal policy n" and with Ô (IS)) Q" 1l2. /c2 + 1)) complexity.
Proposition 3.1. Let Ck > O with 2 k= C T Q³ the iterates generated by SAVIA(Q" .n, E, 8). Then, with probability at least 1-8 we have T -T(Q )1x S simultaneously for all 1: O...., n.
-1 < and E
Unfortunately, since Q' is unknown we cannot directly de- termine the number of iterations n required to achieve this goal. To bypass this issue, we modify the basic iteration by running SAVIA for an increasing sequence of n's us- ing a standard doubling trick (Auer et al., 1995; Besson
The proof is an adaptation of the arguments leading to the Azuma- Azuma-Hoeffding inequality (Azuma, 1967), by consider-
6

---

Near-Optimal Sample Complexity for MDPs via Anchoring
& Kaufmann, 2018), and incorporating an explicit stop- ping rule based on the empirical Bellman residual error IIQ 1 sp. Specifically, we consider the SAVIA+ iter- ation described in Algorithm 3.
SAVIA+ computes an e-optimal policy without requiring any prior estimates for the number of iteration run, thanks to the doubling trick and the stopping rule.
In order to compare our complexity result with the lower bound and the previous results in Table 1, which concern the case || sp 2 1, we state the following Corollary under this assumption. Note however that Theorem 3.4 holds without any additional restriction.
Algorithm 3 SAVIA+(Q",
Input: 2 E RSAA; > 0;5 E (0,1)
for i = 0, 0... do
Set n4 = 2;,0, = 8/c,.
Corollary 3.5. Assume (H), (S), r(s,a) E [0, for all (s,a) S x A. and ||h* llsp 2 1. Ler (QN .N,, nN be the output of (AVIA+(Q",=/)))) 5) with Qo = 0 and S 1. Then, with probability at least (1 5) we have, for all S
(Q"h, 7h; T².) SAVIA(Q", en,,,, 6,),,
until ||Q 1 sp < 14
Output: T , n
g" - -- (s) IQ@ T(Q Se with sample and time complexity |||AA||Ih*| where L = In (|S)| (=pp In (I1h"lspp/ /E).
Our next results establish the effectiveness of the stopping rule and determine the sample complexity of the modified algorithm SAVIA+. In order to simplify the notation, and to avoid equation display issues, we express our estimates in terms of the following quantities
The proof is straightforward application of Theorem 3.4 considering that I|Q" S |r[|sp + ||A' To the best of our knowledge, the sample complexity in Corollary 3.5 is state-of-the-are among model-free algorithms, and matches the complexity lower bound up to a factor ||/' Fur- thermore, SAVIA+ does not require any prior knowledge of |/A ll and automatically provides an E-optimal policy, unlike most prior works.
[ 1|Q0 - Q'Il.pp
QQº0 1aap + 110%
K = max[11/|ls 11p))
Define the stopping time of SAVIA+ as the random variable
N inf(n; E N.: |IQ" - -1 S 1
Our previous results provide PAC bounds (probably approx- imately correct) which guarantee small error with high probability. On the other hand, it is also relevant to estimate the expected sample complexity considering the full proba- bility space, including the low probability events in which the algorithm may take a significantly longer time to con- verge. Such expected complexity results have been studied mainly in the multi-armed bandit literature (Katz-Samuels & Jamieson, 2020; Mason et al., 2020; Jourdan et al., 2023), but much less in the reinforcement learning literature. The following result establishes the expected sample complexity of SAVIA+ in terms of expected policy error.
where "mms" 's are the iterates generated in each loop. We first show that N has finite expectation and, as a conse- quence, that the algorithm stops in finite time.
Proposition 3.3. Assume (H) and (S). Then, B[N] S 2(1 + p/E)/(1 5). In particular N is finite almost surely and SAVIA+(Q' E, 5) stops with probability 1 after finitely many loops.
The proof exploits the fact that restarting SAVIA from Q" in every cycle guarantees the independence of the stopping events in each loop. This independence is also relevant to establish the following sample complexity of SAVIA+, which is one of the main results of this paper.
Theorem 3.6. Assume (H) and (S). Let (QN,T ,NN, be the output of SAVIA+(Q ,E,0). 6). Then, for all s E S
Theorem 3.4. Assume (H) and (S). Let (QN, ,TN, " the output of SAVIA+(Q (0000ee000 5). Then, with probability at least (1 5) we have, for all E
TNN be
Elgg - 9x xx)] < 16 + 611r11pp
with expected sample and time complexity
M. (s) < I1QN T(Q2) S 16E, g" - N
+ 1/=)(+++))))+()((/)))))))11) 0US1AA
with sample and time complexity OLL [S]|A ( where _ = (
In (1+t/E).
In contrast with the proof of Theorem 3.4 which only fo- cuses on the occurrence of good events, the analysis in expectation requires to estimate the sample complexity for the 'unlucky' events where Theorem 3.2 does not provide a guarantee of low sample complexity. To this end we es- tablish a uniform bound for ||d'||sp S max{||r [|r [|Q and compute the expected sample complexity considering
In the proof, we consider some 'good' events G; (see Ap- pendix) which guarantee low sample complexity for the i-th loop and then, through simple union bounds, we show that the probability of these good events occurring at every iteration at least 1 - 5. Thus Theorem 3.4 shows that
7

---

Near-Optimal Sample Complexity for MDPs via Anchoring
both the lucky and unlucky events by the law of total expec- tation.
Similarly the case of average rewards, by introducing the 7-contracting map Ty : RRSAA R defined as (Q) + 7 P maxa(Q), this is equivalent to the fixed point equation Q = (Q)
Observe that, compared to Theorem 3.4, the expected policy error and expected sample complexity include the additional terms d|pppp and (((S)|AA| (1 + (1 + (x) re- spectively. These additional terms arise from the the un- lucky events, showing a fourth order in while our PAC complexity is quadratic in E.
4.2. Sample complexity of SAVID
We present now our algorithms SAVID and SAVID+ adapted to the setting of discounted MDPs. The main dif- ference is the introduction of the discount factor in the sam- pling process updates
From Theorem 3.6 we derive following analog of Corol- lary 3.5 for the expected policy error and complexity.
Corollary 3.7. Assume (H), (S), r(s,a) [0, 1] for all
T T== +
+D D - E D
(s, () E S x A and ||h" 1|sp 2 1. Ler (QN, ,NN, nN) be the
output of SAVIA+(QU (Q", ,e/17, 5) with Q = 0, e S 1. and
and the fact that we measure errors using the infinity norm instead of the span seminorm. Also, the previous variable h is now called V, to reflect the nature of the value function in this setting, With these premises, all the elements of our approach, including the anchored value iteration, recursive sampling, and proof techniques, are directly adapted to the discounted setup.
== = Then, for all E
E Egg² - I N (s)] S.
with expected sample complexity δ (
Interestingly, by setting 8 = e² 117, the expected sample complexity of Corollary 3.7 has same order as Corollary 3.5. We are not aware of such estimates on the expected com- plexity for MDPs with a generative model.
Algorithm 4 SAVID 8,),8
Input: Q" 125 ;n e N; 0;6 e (0.1)
a [n(2[$][AA(++1))))) T-1 rr: V-1 0;80- 0
4. Discounted MDPs
for k = =0.... do
In this section, we extend SAVIA to the discounted setup. We will show that with minor changes the approach applies to the discounted case, using essentially the same key ideas.
Qh = (1-3x) [0 + :3 T
1 ((*) dk V Vk-i
my = max m | /671,1}
4.1. The model
D = SAMPLE my)
T T + Dy
Let us recall the setup. We consider a discounted Markov decision process (S, A, P,r,7), where 7 E (0, is the discount factor. The assumptions the state and action spaces, transition prohabilities, and rewards remain the same as in the average reward case, except for condition (H) which is no longer required. Given an initial state 50 = 8 and action ag= = a and a stationary and deterministic policy :: S A. the Q-vauue function is now defined by
end for T"' (8) E arggaa (s) ( Output: Q", ,,, TT
Algorithm 5 SAVII+((" 6,,6,)
Input: Q" E SSAA; ;E > 0:8 (0,1) for i = 0, 1,... do
(s( = E, E Ei (rrs,, a:) so s, ag = a)
Set n, = 2-, 8, = 5/c,.
(Q"i T ;") = SAVID(Q", n,, 7,
where E,, denotes the expected value over all trajectories (so, ag. $1, a1...., St, ......) induced by P and I.
until [|Qm: - Tmm 1l < lls
Output: Qm+, Tmi Th
The optimal Q-value is Q* a) = max, Qx a) and an optimal policy chooses (s) E argmax (*(x,a) A policy π is called e-optimal if ||Q- - Qx S.
The following result connects the Bellman residual error to the policy error. Compared to Proposition 2.1, there is - y loss when we translate the Bellman residual error QQ - (Q)ll,,, into a policy error.
is well-known that Q' is the unique solution of the fol- lowing the Bellman equation, for all (s, a) E ESX
x
Proposition 4.1. Let Q E RSAA and π :: S - policy such that ((s) E argmax Q(s,a). Then we have I|Q* Q S 12, QQ T,(Q))lax
S-A Aa greedy
a(s,a) = r(s,a) + Σ P(s"|s,a) max a(s'aa)) S'ES
d'
8

---

Near-Optimal Sample Complexity for MDPs via Anchoring
Recall that a major difficulty in the average reward setting was the fact that in general we do not have priori bound on the optimal bias vector ht. For discounted MDPs, we have the simple bound ||@* ao I ||r|] /11 (1) that can be used to run SAVID and which allows us to obtain the following sample complexity.
have || 0(1/VT7)), the complexity bound in
Theorem 4.3 improves to ((8))A1/((1))))))) Note
however that the worst case example in (Azar et al., 2013) is such that || (11((1
5. Conclusion
Theorem 4.2. Assume (S), r(s, a) E [o. 1] for all (s, a) E S x A, and n = [1-)()) Lei (Q", Tm, ,h) be the output of SAVID(Q", n, en,1100,6. 6. with Qo 0 and
This work proposed a novel framework Stochastic Anchored Value Iteration that computes an e-optimal policy with an- chored value iteration and recursive sampling. Our model- free algorithm SAVIA+ does not require prior knowledge of the bias vector and achieves near-optimal sample complexity for weakly communicating average reward MDPs, matching the lower bound up factor ||h" Issp Similarly, SAVID+ attains near-optimal complexity for discounted MDPs.
S (1((1-7) Then, with probability least (1 5) we
have
IlQ - ((()) ae Se
with sample and time complexity O ((11 ((1-15) where Ly = In(2//s14A/((11)))llll In (2/((1)7)))
is known that for discounted MDPs the lower bound on the complexity to compute an e-optimal Q-value func- tion and an e-optimal policy is ([ )??) (Azar et al., 2013). In fact, model-free algorithms can achieve this complexity; see (Wainwright, 2019) for Q- values and (Sidford et al., 2018) for optimal policies. Since IIQ - [Q) I (1 () ||@" - o1 it follows that these algorithms require O(15)) (((5)))A((11-))))))) to obtain an Bellman residual error. Up to our knowledge, the sample complexity in Theorem 4.2 is the best known sample complexity to obtain an residual error for discounted MDPs.
A possible research direction is to improve the sample com- plexity of SAVIA+ to match the lower bound for weakly communicating MDPs. Other interesting open questions are the analysis of the anchoring framework for general multi- chain MDPs, and the study of alternative sampling setups such as episodic sampling and online learning.
A Acknowledgments
(((S)|A)))((
The work of Mario Bravo and Roberto Cominetti was par- tially supported by FONDECYT 1241800 Jongmin Lee was supported by the Samsung Science and Technology Foundation (Project Number ESTF-BA2101-02
On the other hand, Proposition 4.1 implies that, to compute an s-optimal policy with arbitrary high probability, SAVID requires [[SS]|A|/((L (1(((11))( sample calls, matching the lower bound up to a factor 1/(1-1 (1--). In what follows, we show that SAVID+ can improve this upper bound, making the dependence explicit on || and saving a factor of 1/(1-7)2 by using a doubling trick and a stopping rule.
Impact Statement
This paper focuses on the theoretical aspects of reinforce- ment learning. There are no societal impacts that we antici- pate from our theoretical result.
4.3. Sample complexity of SAVID+
References
Theorem 4.3. Assume (S), r(s, a) E 10, 11 for all (s, a) E S x A. and 1 2 1. Let (QN TN x N, be the outpur
Agarwal, A., Kakade, S., and Yang. L. F. Model-based rein- forcement learning with a generative model is minimax optimal. Conference on Learning Theory, 2020.
of SAVID+(Q" (2)/4, 6, with Q 0 and S
1/(1-7). Then, with probability at least (1 5) we have
l|Q" - -2 S 22 - (Tx(0M) )1 (11 71 S e,
Auer, P., Cesa-Bianche N., Freund, Y., and Schapire, R. E. Gambling a rigged casino: The adversarial multi-armed bandit problem. Proceedings of IEEE 36th Annual Foun- dations of Computer Science pp. 322-331, 1995.
with sample and time complexity
(L,15114 011,1114111 11 1(-7)/(1))))))
Azar, M. G., Munos, R., and Kappen, H. J. Minimax PAC bounds on the sample complexity of reinforcement learn- ing with a generative model. Machine Learning, 91(3): 229. 2013.
where I., = In (218)141/(11 In (2)((17)))) (12(()1))(((((111)))))
Notice that if we use the bound || S 1/(1-7) we get (((S][41((11))) =)) complexity, which matches the one of SAVID. However, the sample complexity of
Azuma, K. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19(3):357-367, 1967.
SAVID+ shows an explicit dependence on ||Q' that might be useful for particular MDPs For instance, if we

---

Near-Optimal Sample Complexity for MDPs via Anchoring
Bai, Q. Mondal, W. U., and Aggarwal, V. Regret analysis of policy gradient algorithm for infinite horizon average reward Markov decision processes. International Confer-
Jin, Y. and Sidford, A. Efficiently solving MDPs with stochastic mirror descent. International Conference on Machine Learning, 2020.
ence on Artificial Intelligence, 2024.
Jin, Y. and Sidford, A. Towards tight bounds on the sam- ple complexity of average-reward MDPs. International Conference on Machine Learning, 2021.
Bellman, R. A Markovian decision process. Journal of Mathematics and Mechanics, ((5):679-684, 1957.
Jin, Y., Gummadi, R., Zhou, Z., and Blanchet, J. Feasible Q-lcarning for average reward reinforcement learning. International Conference on Artificial Intelligence and Statistics, 2024a.
Bertsekas, D. P. Dynamic Programming and Optimal Con- trol, volume II. Athena Scientific, 4th edition, 2012.
Bertsekas, D. P. and Tsitsiklis, J. N. Neuro-Dynamic Pro- gramming. Athena Scientific, 1996.
Jin, Y., Karmarkar, I., Sidford, A., and Wang, J. Truncated variance reduced value iteration. Neural Information Processing Systems, 2024b.
Besson, L. and Kaufmann, E. What doubling tricks can and can't do for multi-armed bandits. arXiv preprint 1803,68000 2018.
Johnson, R. and Zhang, T. Accelerating stochastic gradi- ent descent using predictive variance reduction. Neural information processing systems, 2013.
Blackwell, D. Discrete dynamic programming, The Annals of Mathematical Statistics, 33:719-726, 1962.
Jourdan, M., Degenne, R., and Kaufmann, E. An -best-arm and beyond.
Bourel, H., Jonsson, A., Maillard, O.-A., and Talebi, M. S. Exploration in reward machines with low regret. Interna- tional Conference Artificial Intelligence and Statistics, 2023.
identification algorithm for Neural Information Processing Systems, 2023.
Katz-Samuels, J. and Jamieson, K. The true sample com- plexity of identifying good arms. International Confer- ence on Artificial Intelligence and Statistics, 2020.
Bravo, M. and Contreras, J. P. Stochastic Halpern iteration in normed spaces and applications to reinforcement learning. arXiv preprint arXiv:2403. 1233884 2024.
Kearns, M. and Singh, S. smite-sample convergence rates for Q-learning and indirect algorithms. Neural Informa- tion Processing Systems, 1998.
Cai, X., Song, C., Guzmán, C., and Diakonikolas, J. Stochas- tic Halpern iteration with variance reduction for stochas- tic monotone inclusions. Neural Information Processing Systems, 2022.
Kim, D. Accelerated proximal point method for maximally monotone operators. Mathematical Programming, 190 (1-2):57-87) 2021.
Contreras, J. and Cominetti, R. Optimal error bounds for non-expansive fixed-point iterations in normed spaces. Mathematical Programming, 199(1-2):343-374 2022.
Kumar, N., Wang, K., Levy, K. Y., and Mannor, S. Efficient value iteration for s-rectangular robust Markov decision processes. International Conference on Machine Learn- ing. 2024.
Dewanto, V., Dunn, G., Eshragh, A., Gallagher, M., and Roosta, F. Average-reward model-free reinforcement learning: a systematic review and literature mapping. arXiv preprint arXiv:2010.08920 2020.
Kumar, N., Murthy, Y., Shufaro, I., Levy, K. Y., Srikant, R., and Mannor, S. On the global convergence of policy gradient in average reward Markov decision processes. International Conference on Learning Representations, 2025.
Ernst, D., Geurts, P., and Wehenkel, L. Tree-based batch mode reinforcement learning. Journal of Machine Learn- ing Research, 2005.
Lee, and Ryu, E. K. Accelerating value iteration with anchoring. Neural Information Processing Systems, 2023,
Fruit, R., Pirotta, M., Lazaric, A., and Brunskill, E. Regret minimization MDPs with options without prior knowl- edge. Neural Information Processing Systems, 2017.
Lee, J. and Ryu, E. K. Optimal non-asymptotic rates of value iteration for average-teward markov decision processes. International Conference on Representation Learning, 2025.
Halpern, B. Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 7366)957-961, 1967.
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. Breaking the sample size barrier model-based reinforcement learning with generative model. Neural Information Processing Systems, 2020.
Howard, R. A. Dynamic Programming and Markov Pro- cesses. John Wiley and Sons, 1960.
10

---

Near-Optimal Sample Complexity for MDPs via Anchoring
Li, T., Wu, F., and Lan, G. Stochastic first-order methods for wwwrage-reward Markov decision processes. Mathematics of Operations Research, 2024.
Sidford, A., Wang, M., Wu, X., Yang, L., and Ye, Y. Near- optimal time and sample complexities for solving Markov decision processes with generative model. Neural In- formation Processing Systems, 2018.
Lieder, F. On the convergence of the Halpem-iteration. Optimization Letters, 15(2):055-41, 2021.
Sidford, A., Wang, M., Wu, X., and Ye, Y. Variance reduced value iteration and faster algorithms for solving Markov decision processes. Naval Research Logisties, 70(5):423- 442, 2023.
Mahadevan, S. Average reward reinforcement learning: Foundations, algorithms, and empirical results. Machine Learning,
1996.
Sutton, R. S. Learning to predict by the methods of temporal differences. Machine Learning, 3:9-44, 1988.
Mason, B., Jain, L., Tripathy, A., and Nowak, R. Finding all E-good arms in stochastic bandits. Neural Information Processing Systems, 2020.
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An introduction. MIT press, 2nd edition, 2018.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., and et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-533 2015.
Szepesvári, C. Algorithms for Reinforcement Learning. Morgan Claypool Publishers, 2010.
Munos, and Szepesvári, C. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 2008.
Tuynman, A., Degenne, R., and Kaufmann, E. Finding good
policies in average-reward Markov decision processes without prior knowledge. Neural Information Processing Systems, 2024.
Murthy, Y. and Srikant, R. On the convergence of natural policy gradient and mirror descent-like policy methods for average-reward MDPs. IEEE Conference Decision and Control, pp. 1979-1984, 2023.
Wainwright, M. J. Variance-reduced Q-learning is minimax optimal. arXiv preprint
2019.
Wan, Y., Naik, A., and Sutton, R. S. Learning and planning in average-reward Markov decision processes. Interna- tional Conference on Machine Learning, 2021.
Neu, G. and Okolo, N. Dealing with unbounded gradients in stochastic saddle-point optimization. International Conference on Machine Learning, 2024.
Wang. J., Wang, M., and Yang. L. F. Near sample-optimal reduction-based policy learning for average reward MDP, 1.Xiv:2212.006033 2022.
Nguyen, L. M., Liu, J., Scheinberg, K., and Takáč, M. Sarah: A novel method for machine learning problems using stochastic recursive gradient. International Conference on Machine Learning, 2017.
Wang, M. Primal-dual learning: Sample complexity and sublinear run time for ergodic Markov decision problems. arXiv:1710.06100, 2017.
Park, J. and Ryu, E. K. Exact optimal accelerated complex- ity for fixed-point iterations. International Conference on Machine Learning, 2022.
Wang. S., Blanchet, J., and Glynn, P. Optimal sample com- plexity for average reward Markov decision processes. International Conference on Learning Representations, 2024.
Puterman, M. L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 2nd edition, 2014.
Wei, C.-Y,, Jahromi, M. J., Luo, H., Sharma, H., and Jain, R. Model-free reinforcement learning in infinite-horizon average-reward Markov decision processes. International Conference on Machine Learning. 2020.
Reich, S. Strong convergence theorems for resolvents of accretive operators in Banach spaces. Journal of Mathe- matical Analysis and Applications, 75(1):287-292, 1980.
Rosenberg, A. and Mansour, Y. Oracle-efficient regret mini- mization in factored MDPs with unknown structure. Neu- ral Information Processing Systems, 2021.
Wittmann, R. Approximation of fixed points of nonexpan- sive mappings. Archiv der Mathematik, 58(5):866444 491, 1992.
Sabach, S. and Shtern, S. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640-66 660, 2017.
Xu, H.-K. Iterative algorithms for nonlinear operators. Jour- nal of the London Mathematical Society, 66(1):240-255 2002.

---

Near-Optimal Sample Complexity for MDPs via Anchoring
Yoon, T. and Ryu, E. K. Accelerated algorithms for smooth
convex-concave minimax problems with (1/h22) rate squared gradient norm. International Conference Machine Learning, 2021.
Zhang, Z. and Xie, Q Sharper model-free reinforcement learning for average-reward Markov decision processes. Conference Learning Theory, 2023.
Zurek, M. and Chen, Y. Span-based optimal sample com- plexity for weakly communicating and general average reward MDPs. Neural Information Processing Systems, 2024.
Zurek, M. and Chen, The plug-in approach for average- reward and discounted MDPs: Optimal sample complex- ity analysis. Conference on Algorithmic Learning Theory, 2025.
12

---

Near-Optimal Sample Complexity for MDPs via Anchoring
A. Omitted proofs for the average reward setting
In this section, we present the proofs omitted the main body of the paper, along with additional comments to complement our results, We start by analyzing the average reward setup, while the analog results in the discounted setting is presented in Appendix B. For better readability, we restate the main results.
A.1. Proof of Proposition 2.1
Proposition 2.1. Let Q IxS and π.: : S - A a policy such that x(s) argmax ((s, a). Then for all states s we have S 9" 9x (s) < IQ - (QQ)lspp
Then 9x Prrr Tr Proof. Let PT the transition matrix of the Markov chain induced by x. that ==(ssss)=p((sssss...../>>>) (sss'ss,
where P = limy--se 1 Ei= (P+)* and (s) = r(s, π (s)). Since P = P Pr. it follows that for all h E IRS we T
have On = P (r= + P h). In particular if we take h = max A (Q) so that h(s) = (s, (s))). then for every E S the term rx (s') + (s) - h(s') is exactly the component (s', (T')) of the matrix (Q)) Q, and therefore by averaging according to (-1s) we derive the inequality (s(ss) 2 min,',a' (T(Q) (s','a
Similarly, for optimal policy x" we have 9" P Px- h h) for h m Denoting (1(s) Q(s, (8)) we have hs) < h(s) and therefore
T-- (8') + (Pr-h)(8') h(8) S rT (5' (P+) - h1 hs(ss).
Noting that Tx- (s') (Pa-))(ss)) (s') is the component (s', (s') of (()) Q. and averaging with P (-Is) we get
g" = (s) S max af (T) a'). Sustracting both estimates we conclude 0 $ g" (s) S [[T(Q) Qllap. O
A.2. Proofs of Section 3.1
Let o :i probability distribution over the trajectories ( (D*) )ENN Notice that, because of the order of the updates, T is Fx -eeasuuure whereas Q* ,,*, d and ma, being functions of 7k are Fx-i-measurable.
o.....k) k)) denote the natural filtration generated by the sampling process in SAVIA, and IP(() the
Proposition 3.1. Let > O with 2
< 1 and Th Q² the iterates generated by SAVIA(Q", ,n,,,,,,,,,. ,n,,,6). Then, with k= Gt >
probability at least - 8 we have | T(Q*) )lo0 I & simultaneously for all k == =0,..... -0....,72 n.
Proof. Let Y D' - Pd' and X = Σ Y Since h-1 = 0, by telescoping T(Q*) + Ph =r Σ Pd and ビ==
then using (2) we get T T(Q')= = (Di - Pd') = x
We proceed estimate I| 2 E) by adapting the arguments of Azuma-Hoeffülee inequality. Let s.a ~ P(-|s.0) s. skjj
for j L...., m be the samples at the k-th iteration for (s. a) E S x A. that
yd a) 1 Ej (d
Pd ( a))
V(s,a) EXA
Since dt and my are Fa-1- measuraall, it follows that [ 0 and therefore X is F&- Fg-martingale. From Markov's inequality and the tower property of conditional expectations we get that for each (s, a) E S x A and X >> 0
((X*((s 2) S e A= B exxee(AX
- Ae E exp x (s, a)) Eiexp(A (a (s) Fx-1I].
(3)
Now, conditionally on Fx-1, the terms yk - ($2 - Pit (s, a)) in the sum of ( a) are independent random variables with zero mean and Y
<
- me
||d 1pp that Hoeffding's 's Lemma gives us
E exp (A))
= II E
I exp 1
(4)
Using (3) and (4), together with m& 2 a cac 112//22 simple induction yields
17 1o). E(exp(A (xxxp(>*((s,a))) < exp (2X222 Et
13

---

Near-Optimal Sample Complexity for MDPs via Anchoring
Then, since Σi=o 9i'
2 (-x we get (e /X22 and taking A 20/e we deduce
(s,a) 2 S =x=((=))=0/222((((11=)
A symmetric argument yields the same bound for P(X* (s. a) < -E) so that ((IX"(ss a)l =)
Applying a union bound over all (8,a) a) E x A we get I[| n0 2 e) S (n+ and then a second union bound over
k gives o 2 =}) S 8. The conclusion follows by taking the complementary event.
From now on we consider the specific sequences o = 5(k + 22 + 2) and 3₂ = k/(k+2 2). We also fix some solution Q' of Bellman's 's equation Q = T(Q") - g", and we set h- = m We keep the notation for all the sequences generated by SAVIA and we assume throughout that
||T - 11 S for all k: = .,...,n,
n,
(5)
which, in view of Proposition 3.1, holds with probability at least (1 - 5). Also, as noted earlier, for D = SAMPLE(d, m) we have sp S |[d]lsp- which combined with the nonexpansivity of the map Q - (Q) implies
T T sp
D sl S
||d 1bpp | - up S ||@ '1sp.
(6)
As preamble to the proof of Theorem 3.2 we establish two preliminary technical Lemmas. Lemma A.I. Assuming (S) and (5), have that
11e 11 s 11 Q01ppsp + 3 k, for all O...., n.
Proof. From the iteration Q² = (1 - 10) + 3y Th-1 with 33. = k+2
k we get
1 - Q' 1 2 110 Q" llsp + 442 # - Q*
Using the invariance of I1-p by addition of constants and the nonexpansivity of T for this seminorm, triangle inequality 2 oloo and the bound (5) imply
together with I1- $ 2|
|| Q'1
-T("")l S 25 11 1--1--0 -Q
(8)
which plugged back into (7) yields
110 - Q'11 S 222 -''1la + トトッ (2s + 1| QQ"1lpp
Denoting 02 (A: 1)(k + 2) (51 this becomes 02 0. (k: + 2s k:A + 1) + 0k- 1, and inductively
0x 0 + (i
+ 0 2k 1)(k + 2)
2) + 2 kkkk 1)( + 2).
The conclusion then follows dividing by (k: + () + 2).
Lemma A.2. Assume (S) and (5) and let pk 21|Q" - Q' 1pap + 3 e
Then
11 Q4-111pp 1lap S x(k+1)
2 Σ -i=1 Pi+2 for all k 1....,n.
Proof. From Qh
2 20000
00 + 1s = and Q+1
2 Q0 + *-1T+ 2 we derive
k+2
k+2
k+1
Q Q - [k+1)(++2]
2 ( Qo) + k+1
k-1 (T - -T
(9)
Now, (8) together with Lemma A. readily imply || 101 7 Q 1lap +110- - -Q² 11pp S Pk42, and therefore
using (6) we get
I|Q²t - 111pp I ((++)((+2] Pk+2 1 1| - -2--211pp
2
Denoting 0 = (kk + 1)]lQ*
1 lsp we have 0 - 2422h+2 + 0p-1 S 2pk+2 + 02-1. Hence 0, 2 Pi+2 from
which the result follows directly.
14

---

Near-Optimal Sample Complexity for MDPs via Anchoring
Theorem 3.2. Assume (H) and (S) and let (Q", Th, ,","") be the oulput computed by SAVIA(Q", n, n,,,,), Then, with probability least (1 5) we have, for all S
g" - -x- (x) -T(")= - 81QQ0 Qss
+ 4E,
++2
with a sample and time complexity of order
([LIS] 111 110))2)) + +n²))
where L = In((S]AA((n + In (n + 2).
Proof. From Proposition 3.1, with probability at least (1 - 8) we have 1 - -T(Q") I for all A = 0,.... n. Now, the recursion Q" n+2 -0 +
n 7 implies
n+2
Q" - -((()))
2 (Q0 T(Q")) + n+z (T T(Q"-1)) + n+z -) n+2
(10)
Using the fact that Q' =T(") - g" and the invariance of 11-11sp by additive constants, triangle inequality and the Il-llsp- nonexpansiityy of (.) together with Lemma A.1, imply
11Q" - 1l - 11Q" 10 11Q"
Q" lsp S Pn.
while Lemma A.2 gives I T(Q")) using these estimates together with Proposition 2.1 and
m(++1) 1) Σ Li=1 Pi+2- Thus, applying triangle inequality (10) and
|| S 2/
oo we obtain
g" - (s) S 11Q" -000~=T(Q"))) ll S
n+2 Pn 2s (n+ +2 Ex Pi+2
2
2
411+2m)
|1Q0 Q011sp + 1(388+33')
[a+1X=+2]
30+1)(++2] + 4E.
8] Q - 1l
n+2
To estimate the complexity, for &: 2 1, we use the inequality ||a sp $ 11
1 in (6) and Lemma A.2 to find
| 1p 5 T[(+T] Σ Limi Pi+2
- 10200 1011pp + 2(k++5) 3(++1]
< - 1100 - Q-11 + 25.
Now, estimate the total number of samples (8||A] Σ k= my we recall that my max [ack /s which can be bounded as m& < + achlldd /
Then
En m 5 (n + 10++1)=0 - Σ c 1|
(n+11)+ 10c In (2) | 13 + 5n
(k (k+))
Q" + 22)²
s (n+1)
10 hn (2) Qu 13 Σ
240
In (k 2) - 40 Σi (k 2) 2n +2)
[k+1]
(al a In
2)
Q* a (n
(11)
where the third inequality results by using the trivial bounds (a + 6)2 < 20 + 20 and A < 3. and the last equality from integral estimations of the sums. The announced complexity bound then follows by multiplying this estimate by |AA||S] and using the definition of and T..
REMARK. The complexity analysis above can be refined obtain an explicit multiplicative constant in O(-).
15

---

Near-Optimal Sample Complexity for MDPs via Anchoring
A.3. Proofs of Section 3.2
We now proceed establish the finite convergence and complexity of the algorithm SAVIA+, for which introduce some additional notation. Let us recall the definition of the parameters
μ || Q" 1pp
V | 10 + 110%
A = max 10 [lsp)-
The stopping time of SAVTA+ is the random variable
= (n; EN: 1Q@h 1 T sl S 14
with n and Qt the iterates generated in each loop of SAVIA+(Q" 0, For notational convenience we also define
T= e IIQ "Q" T kp S 14c}
so that in fact N = 2'. We let in E N be the smallest integer satisfying n40 2 -|Q0 - 1211sp/ = p/e, so that either in = and nig or 1%:-1 = mig / < p/s, which combined imply nio S 2(1 + p/e).
In order to estimate the sample complexity, we consider the random events
S. = f1l - 1lsp - 14=} and G, = [|| T(Qh)) E, Vk- = 0, o....,n.
with T and " the inner iterates generated during the execution of SAVIA ni, E, 8;) in the i-th loop of SAVIA+, and denote by M, the number of samples used during this call, so that the total sample complexity is M & E Mp. Observe that the My's 's and M are random variables.
With these preliminary definitions we proceed to establish the following simple but useful preliminary estimate.
Lemma A.3. Assume (H) and (S). Then, for all 2 in we have ((S.)) 2 (PG 2 1 - 64.
Proof. Proposition 3.1 guarantees F(G;) 2 1 - 6, so it suffices to show that G C S.. This follows from Theorem 3.2 since for 2 io and all w E G; we have
(w) - (T)(())) - -(Q")) IIT("")))) - T (m (w)
-Q'll + + n;t2
<
14
Proposition 3.3. Assume (H) and (S). Then, E[N] S 2(1 p/t)p(1))/))) 8). In particular N finite almost surely and
SAVIA+(Q 6) stops with probability after finitely many loops.
Proof. Since in each loop SAVIA+(Q). n4, 6.) restarts afresh from Qo, the events (S:: N) mutually independent and therefore
IP(T = = P P( sy n S.) = j=0 ((S)) PPSS.).
From Lemma A.3 we get P(S)) < P(G.) < 6; for all 2 in + 1 and then [P[ = i) S j= 85. On the other hand, from
2 2i G7 < it follows that 6; 8/0j < 6/2 and therefore TP(T i) (5/2)(-lu. Using this estimate and the identity
n, nig2 2 io, we obtain
[ Di n P(N n2)
nio + Eingtt nig 25- P(I =
S mig (1 Eisio1 81-
This last expression is exactly nig/ 8) and the conclusion follows using the bound Mig 2 + w/e).
16

---

Near-Optimal Sample Complexity for MDPs via Anchoring
Theorem 3.4. Assume (H) and (S). Let (QN, TW m²)) be the oulpua of Sf ee, se, Then, with probability least 6) we have, for all E S
g - 9NN (8) 11@ - -T( )1sp _ 16
with sample and time complexity (S) /5a +1)) where L = (L+t//))0) (11(1=//e).
Proof. The inequality between the policy error and the Bellman error follows from Proposition 2.1 so it suffices to prove the second one. Consider the events A = { S fo} and B Ni=o G.. We claim that P(An B) 2 1 - ô. Indeed, by Proposition 3.1 we have P(G;)) I 6, so that
P(B*) = PIU G S E i= 8/c S 6/2,
while Lemma A.3 implies P(A) > IP (S..)) 2 F(G 2 1-160 d:o- 1 - 6/2, which combined yield PIAAUBB S d. Now, from the definition of N, I and G,, it follows that on the event A n B we have
1|@ - T(Q") 1p S 11@ T 1p + I|T T(Q*) )|spp 14 + 28 16
Moreover, using (11) in the proof of Theorem 3.2, we can to bound the total sample complexity M 2 E/ M, as
M s E f2 M. O (15114)) a: 1| /e2 a In; + 2) Q ///p// + nz In + 2))
the parameter used in the i-th internal cycle of SAVIA+. Note that (n,+1)c; I 14n3 and therefore a; V [1))))) Now, since the terms in the sum above increase with using the estimate nig S 2(1 + w/E) conclude
where a; = [n(2
M $ |S||A|| on (oo 1)
1 O (112112 + In (m:, + 2) 10, n² In In: 2))
< ||||A||| oig In (n., + 2) ( (1Q"
+ +2//22 + +4(1 + +/E)²)
0 0010)/11))
Corollary 3.5. Assume (H), (S), r(s, a) E [0, for all (s,a) E x A, and ||t 10p 2 1. Let (QN, ,T,, ,N,NNN be the output of SAVIAA+( e/16, with Qo and $ 1. Then, with probability at least (1 6) we have, for all E S
g" gN~ (s) S QQQ" - -T(Q Se
with sample and time complexity O |||| 11 /=²) where L = In (| (=8) In (n2((111llsp)) llsp/s).
Proof. Since Qº = 0 we have |1Q0 - 0-1 = ||Q" 1sp = ||r + P max h² 11 S ||rllsp + ||A" The result then follows
from Theorem 3.4 by noting that (1 ///))= |11//1//// which transforms T. into the multiplicative factor T..
Next we proceed to establish the approximation and complexity results in expectation. We begin by the following technical Lemma which provides crude bound for the sample complexity of each cycle of SAVIA+
Lemma A.4. Let M4 S my be the number of samples used in SAVIA(Q", ,,),, during a given cycle e N. Then M; < (SILA] (n, + (K/E)²a a: n² In2 (n, + 2)) where
+1/6.).
Proof. We first show by induction that for all k = 0,.... ..... we have ||d S and || S (k + 1)k. For k: = 0. this is true by initialization since dd x Q² and T r. Using (6), (9), and the induction hypothesis, we have
2 ||d bp s 11 Qt I (++1)(k+2) || T - @011pp
k-1
ld 1|sp
k+1
< क
(k:: + 1)x + k) +
K4I
k-1 K.
and consequently
| ap I 1|
|| 1lap - (k 1)x + 1|0/ S (k + 2)K,
17

---

Near-Optimal Sample Complexity for MDPs via Anchoring
Then, using these bounds, the sample complexity M, for the i-th cycle can be readily bounded as
M < ([]A][(m; + 1) + (au/ 3ー= 1
S ((m + +) + (0k/e)(/e/aaaa/ شأ=رز + 2) In
(j+ +++2 2))
= SIII (m + (e/E) n In (n; + 2))
Theorem 3.6. Assume (H) and (S). Let (Q", (Q",N,, n n
be the output of SAVIA+ 6). Then, for all E S
Bigg -x" (8)] S 16 + 81111ppp
with expected sample and time complexity
+ 6 (1
X 1=1 G, as in the proof of Theorem 3.4 which established that on the event A n B we have 5² - -r (8) < 16 e for all E S with P(A n B) 2 1 6. On the complementary event (A n B) we
Proof. Consider the events A = (I S 10} and B =
can use the crude bound 9* Ix (s) $ || sop and then, since ((An B) S 8, we derive the first claim
Eig" 9x- (s)] - 16 + 8 |r||ap-
To estimate the expected value of the sample complexity M Ei= M4 we note that A Wi { i). and therefore
E| M = M[M n BJ P(An B) + E|M B P Bd) 21 E[M = i] IP = i).
Let us bound separately the three terms in this sum. For the first term we observe that on the event An B we can apply the bound in Theorem 3.4 and since P(An B) < 1 get with L. (n( (1+//))/6) In (1+/ that
B[M]An B] P(An B) ( 2/2 1)).
For the second term, we combine P(An (²) S (B3) - 5 with the bound in Lemma A.4 and nio S 2(1 + n/e) to get
B| B S ||||AA E O(n + (k/=)Pamn? In In? 2))
< 6 |A| O (nio + (m/s) ni, In (nio + 2))
S S O nio + i. (1/EE)
where the last inequality follows from the bound 0:o In (14 2) < O())
For the third term R A E E[M P(I i), using again the bound in Lemma A.4 we get
= = ビド B[M, - - O(n, + (k/E) n² In In, 2))
= =|S|[AA| ((p + (k/E)aa In + 2))
and therefore
R < |A||A] E O(n, + (M/E) (n. + 2)) P(I = i).
To estimate the dominant terms in this last sum we recall that a; |n(2|8]| (n; + 1)/6)) with n; = 24 and 5, 8/63. Since In((n + 1)e;) = Oii) we get o; = O +i < OV)), and similarly In (m: + 2) = O so that
R < S|| - 0(. (k/=)² 19 P(1 =
Using the fact that n4 n1:0 26-26 and noting that for i > in +1 have P(T = < 11 8g 50
I JF2
i-1
(see the derive
proof of Proposition 3.3), by setting S1 = Eisiot 20-50 I
i-1
1 and S2 Eisiot1 22(1-10) ;3 11= J+2
R R B | + +S D (k/E)3n1
18

---

Near-Optimal Sample Complexity for MDPs via Anchoring
The sums S₁ and S2 can be computed explicitly in terms of incomplete Gamma functions as
S 2- [io + [(oo + 2,] - (e² ( 3)/2, S = 84 400 + 5) +
(T + 2) - l(0 + = (((o+)))))
so the third term satisfies
R S 8|S|AA O (noo ( (66+)))
Putting together these three bounds, by regrouping terms of the same order and ignoring logarithmic terms we get the announced bound for the expected value of the sample complexity
B[M] < O (T(u2/E² +1) (1)) 8 + (60+)) O
+ (1
(H//))²)
Corollary 3.7. Assume (H), (S), r(s, a) E [0 for all (8. a) E A and 1p 2 1. Let (Q", TNN xx ,N,,,
be the outpud
yySAVIA+(*,,e/I) with Qo 0, 1, and 5 e² 2/77.. Then, for all S
Eig" IN~ (s) S
with expected sample complexity Ō (181)
Proof. From Theorem 3.6 have Fl[g* 9-- (8)) < 19 17 11lppp s. Also the expected complexity follows directly from Theorem 3.6 and the choice of ö.
B. Omitted proofs for the discounted reward setting
nice feature our approach, presented mainly in the average reward case, is that it can applied almost verbatim to the discounted setup. Consequently, the proofs for discounted MDPs and average reward MDPs are fairly similar. However, for the sake of completeness, the arguments are repeated or referred to those in Appendix A when they are basically the same.
B.1. Proofs of Section 4.2
Proposition 4.1. Let Q E RSAA and π : S a greedy policy such that rTs) argmax Q a). Then we have IIQ 1o < 2 |Q (T(Q)
Proof. A simple triangle inequality gives | - 10 < 11Q Ql + ~ so it suffices to show that both terms
in this latter sum are bounded by - QQ - (Q) loo. The first incquality I|Q* - Q11 S ب I (Q)ll results directly from the following triangle inequality combined with Q" = (T("") and the fact that T, is conttrcctonn
|'' - 21 < l1Q" - Tx(() + (TT(()
Qll >lQ"" Ql + 1Q T, (Q)
To establish the second inequality ||xx - 21 < - ||Q - Tx(Q) we first note that Qx satisties the recursive formula
Qx(s,a) r(),a) + Exesspssllss Q,(,,))
while the definition of gives Q(s',=(s')) (Q)x so that
(2) a) = r(s, a) + Eves p(s')s, Q(s', (((6sT((s)))))))) (Ts)))
Then, sustracting both formulas we readily get ||Q= - (T) 5 ~>1Q - -Ql and therefore
I|Q- Ql1oo - =1Q= [, (QTx(Q) Q11 S 1/ Q11 IQT,(()) Q11
which readily implies ||Q= - Qll1s S 1 ||Q T,(Q)ll as claimed.
19

---

Near-Optimal Sample Complexity for MDPs via Anchoring
Analogously the average reward setting, let Fs = = 0,....; k}) be the natural filtration generated by the sampling process in SAVID, and IP(.) the probability distribution over the trajectories (D*) Again, T is F& meeauuraae whereas Q*, Vk d², and my are -eeasuaauuablle.
Proposition B.1. Let Cg with 2 2k-n Ck 1 < 1 and T* Q* the iterates generated by SAVID(Q", n,,,,,7)) Then, with probability at least - 8 we have 1T TT( I 'yE simultaneously for all k = .R.
Proof. Let Y = D - Pd and X = - Y'. Since V-1 = 0, by telescoping (₂( = =r + = = Σ i Pd
and then using (2) we get 7 (2*))) = 7 o Pd') 7 7 The estimation of [P[ 2 8) proceeds the exact same manner as in the proof of Proposition 3.1.
From now on we consider the specific sequences c₁ = 5 + 2) In (k: + 2) and By = k/( 2), meaning that we assume (S). Let Q" be the unique solution of the Bellman equation (Q) = Q. We assume throughout that
| T,( S for all ls == . n
(12)
which, in view of Proposition B.I, holds with probability at least (1 -1-0 6) when SAVID n, m, is implemented. Also, noted earlier, for D = SAMPLEE(,, m) we have || S ||d]| which combined with the nonexpansivity of the map Q + max (QQ implies
1 - Th 11.0 - 111101 s>11d"1| = =7|| - vl-
S 5T -4
(13)
The following two technical lemmas serve as counterparts Lemmas A. and A.2 in this setting. Unlike the previous results, they establish estimates from the iterate Q² to Q* in the infinity norm and therefore the conclusions change slightly. As before, these lemmas act as prelude to the general bound given by Theorem B.4.
Lemma B.2, Assuming (S) and (12), we have that
11 - 10 =1100 - -Q'll + #ze ek for all h = o....,n.
Proof. From the iteration Q! (1 - -², + 3x Th- with 3x = kt2
k
we get
||0h Q'11 S k42 |000 2- 1l + k+2
| - Q'
Bound (12) and y S imply
|| - Q- =
- (Q''")
S
(14)
From here the proof follows the exact same lines as in the proof of Lemma A.I.
Lemma B.3, Assume (S) and (12) and let Pk 2 21Q00 ao + Jek. Then
|| 1 - S
2
Σ
Pit2-
for all h 1,...,
kik + 1)
i=1
Proof. From Q+= = 2 Q0 + k. T and Qh-1=
00
2 Q0 + k- 2 we derive
k+2
k+1
k+1
Q+ Q Q [K+1)(442] k1- -Q²)= + K -
-1k-2).
Now, (14) together with Lemma B.2 readily imply ||T - -Q1 S | -Q- 10:1000 + +110- - Q2 S Pk+2, and
therefore using (13) we get
|| 1 Qh-1 11 <
2 (1+1) +
k-1 k+1
||Q -Q
Using that > & 1, the proof finishes exactly as in Lemma A.2
20

---

Near-Optimal Sample Complexity for MDPs via Anchoring
The folowing theorem is the analogue of Theorem 3.2 for discounted MDPs. For the sake of completeness and given that the constants involved are different, provide the full proof.
Theorem B.4. Assume (S) and let (Q", T x²)) ) be the output computed by SAVID(Q",,, n,,,0,,). 7). Then, with probability at least (1 5) we have
811@0 -Q-1l
II"" - -T(1")) I
n + 22,
with a sample and time complexity of order
O [S)A - 11ll++10000 110911 n²))
where L, = In(2|S))|4(( + 1n 2).
Proof. From Proposition B.I, with probability at least (1 - 8) we have 1| - -T,(09) for all k = O,.... Now,
the recursion Q" n Qo + n+2 T implies
Q" TT(")))))
2 n+2 (Qo (Q")))
n+2 (T (Tm-1- Tz(Qm=1)) + n (Tş(Q-=1) - (T((")).
(15)
Using the triangle inequality and Lemma B.2, we have that
| T,(9") < |1@² Q- bo + +1 - -2
+ +
Pn.
while Lemma B.3 gives [T<(Q=-1) (Q using these estimates together with Proposition 4.1, we obtain
20 S n(n+1)
Di=1 Pi+2- Thus, applying a triangle inequality (15) and
|0"" -0"==T(0"") T,(0")1l>> S n Pr. + [+++] Σi=1 Pi+2
1(142n)
|Q00 101000 + 2(34843322) 3(++1 + 2s.
(m+1](++2)
8 Q01
n+2
To estimate the complexity, for l 2 1, we use the inequality ||at to find
11 s 1 Q=-
11 in (13) together with Lemma B.3
||a|| 11.0 S k[k+1] Ei= Pi+2
- Q000000000 Q- || |1 + k+5
3(+1
- Q0 Q" 11 +
Now, to estimate the total number of samples |S||A|] E my we recall that my max{/2aca ||ab1132 7577,13 which
can be bounded as m. < 1 + 20ck ||d fea. Then
E my S (n + 1) + 20 Σ n
k= Ck |
(n+ 1)+ 2 In (2) ||Qull 113 + Σ (k+ ( ||Q0 1000-Q110 Q'1 +E)"
S (n (n+ 1)+ a0 In 2 (2) 10113- E
480 (k+22
In (k+ Q - 1-122 20 (ke 2n
= =a /e2 + In + 2) Q1 11 /s² + an an In (n²
(16)
where we use the same estimations as in the proof of Theorem 3.2.
Theorem 4.2. Assume (S), r(s, a) for all (s, a) E S A, and (n==10(((1)ee) Let (Q",T", T²) ",,,T"""" be the output of SAVIDDQ" n,, nn,e100,,,, with Q" 0 and < 1/(1-7)) Then, with probubility least (1 -8) we have
||Q" (q( S
with sample and time complexity ((L_15)144((11-))2)) where L, In
Proof. The proof follows directly from Theorem B.4 and the bound ||Q" S 11((1-1)
21

---

Near-Optimal Sample Complexity for MDPs via Anchoring
B.2. Proofs of Section 4.3
We now proceed establish the complexity of the algorithm SAVID+, Again, the proof almost the same as in the average reward case, where some of the constants must be estimated differently. Precisely, the time in which the inner loop in SAVID+ stops will now depend on ||QO -Q
Under a slight abuse of notation, we define the stopping time of SAVID+ as
N = in; E EN- I|Q - T 1 I 11
where Th and Q s are the iterates generated in each loop of SAVID+ (Q" 0.2) As before, we let in E N be the smallest integer satisfying nig 2 |000 Q'
11 /e, so that either io and R.i = 1 or m /2 < || Q* /c,
which combined imply nio 1 + 2 |Q" Q ol e.. Also, in the average reward setting, consider the events
S = -11"" S 11 and G; =
= TO00=-T((01 T,(00 S, vk= 0,..., ni)),
with Q and ' the inner iterates generated during the execution of SAVID(Q", ,4,,, 04, in the i-th loop of SAVID+ Lemma B.S. Assume (S). Then, for all i 2 in we have that IP(S:) 2 P(G,) 2 1 6;-
Proof. The proof is the same as its average reward counterpart Lemma A.3 by just observing that, if 2 in then, for all w E G
(w) - T (w)ll - 110h(()) (,(Q")) + (TT(("))(w)) T (w)(ll
81108-0 1lx
m,t +2
S 11E.
Theorem B.6. Assume (S) and let (Q", T N ) be the outpua of SAVID+(Q*,e, 8) Then, with probability at least
(1 () we have
|1@ - 11 12c
with sample and time complexity
o (ī, S1LA S|LA| (1I@ + 1100 - 1x2 / + +)).
where L., = =1(()))44 Q- |0 /0) In (1+2||000 - Q²1 /s).
Proof. Consider the events A= 1o} and B n Gs Using the exact same argument in the proof of Theorem 3.4, now through Proposition B.1 and Lemma B.5, we know that P(An B) 2 - 8. Also, on the event A in B and from the definition of N, we have
||Qat - (Q s - IT + +||T
- T,(QN) < 1l = 12s.
Now, using (16) in the proof of Theorem B.4 the total sample complexity M of the algorithm can be estimated, as in the average reward case, by
Σ 0 ||0 /e² + a, In3 2) 11Q0 11 /6² + a ain In2 (n: + +2))
M |
1=0
where a; |n is the parameter defined in the i-th cycle of SAVID+. Again, for SAVIA+, use
that n2, < 21+2 Q- |l /=)² = O(I@0 - 1= /22 + 1), to get
M ~ |S||A|| 0 a 11 /02 in(nno 2) az In (mi, + 2) |1Q0 Q² /62 + as n2 In In' + +2)
< | ai. In (n + 2) 0(112911 + +1|Q0 Q" 00 )2 //222 + 1).
22

---

Near-Optimal Sample Complexity for MDPs via Anchoring
Finally, state claimed complexity result for SAVID+, whose proof follows directly from Proposition B.1, Theorem B.6, and the fact that 1| S 1/(11- (1-
Theorem 4.3. Assume (S), r(s, a) E [0, for all (s,a) 8 A, and 1|Q* (AVID+((",e(11>)))
1l.c 2 1. Let (Q", T x be the output of with Q = 0 and 5 1/(11111))) Then, with probability least (1 6) have
l1Q - 1xxll s - /(1-7))) SE
with sample and time complexity
014,151141111111 / ((11~))67)
where T., In (22)5)441((11-))))) In (2/((1-7))).
C. The Anchored Value Iteration as Halpern's 's iteration on quotient space
The recursion (1) involves the unknown optimal value g" However, since T(Q T(Q) c homogeneous under addition of constants e E IR, this prompts to consider the map T M + M defined by T(Q))) = [T(Q)) on the quotient
space M = RxxAABB E with E the subspace of constant matrices, endowed with the induced quotient norm
1 2 1 1sp
|
min cER
|Q + clloo
E
One can readily check that 7 is nonexpansive for the norm
|| || and moreover
CLAIM: Q" E Fix(Tg:) ) if and only [Q*] E Fix(T).
Proof. If Q² = Ty- (Q*) then [Q") [T(Q" -g"} -(()'=9"1) =(QQ))) Conversely, if [Q") = T(Q')) T((])) = (T()))
then Q = T(Q*) + e for some E R, and Puterman (2014, Theorem 9.1.2) gives -g" so that Q' E Fix((Tg)) O
Projecting (1) on the quotient space M it follows that the equivalence classes [Q*] = Q² + E of the iterates (Qr JKen generated by (I) satisfy the following Halpern's 's iteration for (-))
[Q*+1==0 (1- BK+1 7(QQ1))
In this projected iteration the unknown 9" plays no role. Moreover, the equivalence classes [Q"] coincide with those generated by the implementable modification (Anc-VI) in which g" ignored. This shows that, modulo constants, both (I)
and (Anc-V VI) equivalent and their corresponding residuals in span seminorm coincide.
Finally, using the identity |Q I( 2||[@] T(Q))
|. any error bound for Halpern's iteration applied to T
directly transfers into bound for l|Q - -T(Q*) I|sp- In particular, for 3x k/(k + 2) we get
1|Q* 1 -T(*)) 10 1sp-
23


Reviews:
[{"review_id": "8lVTDuBS1N", "reviewer": "Reviewer_mUiL", "summary": "The established sample complexity of $O(\\frac{1}{\\epsilon^2})$ for average reward MDPs using a interesting approach of Halpern's iteration. The result is independent of mixing time which is very important.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the opportunity to clarify some points that were not transparent \nin our manuscript, and to better put in perspective our contribution with respect to \nprevious work. For the list of references please refer to the reply to Reviewer BWFD.\n\n1. Comparison with [19]\n \nThere are two major differences between our results and those in [19, Zurek & Chen].\nFirst, in contrast with SAVIA+ which is model-free, the algorithm proposed in [19] is \nmodel-based with its higher memory requirements for storing the empirical transition kernel.\nSecond, and more importantly, Zurek & Chen's method requires prior knowledge of an upper \nbound for the span seminorm of the bias vector $H\\geq \\\\|h^*\\\\|_{sp}$, whereas SAVIA+ does not \nrequire any prior-knowledge. \n\n2. Comparison with [7]\n\nGanesh et al. [7] study a model-free algorithm for average reward MDPs, although in a  different context of Markovian sampling and function approximation which allows to deal with large state spaces by considering a parameterized family of policies. The proposed actor-critic algorithm is designed to optimize  the parameters of the policy. The results are restricted to ergodic MDPs, although their method does not require prior-knowledge of the mixing time. The main result, Theorem 1, establishes an optimal asymptotic convergence rate in expectation, although no finite error bounds in high probability are provided. As a consequence the model and its underlying assumptions, as well as the algorithm and the complexity results, are of a different nature compared to our paper and neither one implies the other.\n       \n\n\n3. Strict contraction vs nonexpansivity of Bellman's operator\n\nFor average reward MDPs with finite mixing times  Bellman's operator is indeed a strict contraction in span seminorm. However, this property fails in the weakly communicating case where $t_{mix}$ can be infinite, and Bellman's operator may be just nonexpansive with multiple fixed points. Consider a simple example with two states $S=\\\\{s_1,s_2\\\\}$ and two actions $A=\\\\{a_1,a_2\\\\}$ with deterministic transitions: action $a_1$ keeps the process at the current state, whereas $a_2$ moves to the other state; all rewards are $1$ except when moving from $s_2$ to $s_1$ under action $a_2$ whose reward is $0$. The optimal reward is $g^*=1$ and Bellman's operator for the bias $h=(h_1,h_2)$ is (see line 93 second column of our paper): $T(h_1,h_2)=(\\max\\\\{h_1,h_2\\\\},\\max\\\\{h_1-1,h_2\\\\})$ which is nonexpansive in span seminorm but not a contraction. In fact $T$ has a continuum of fixed points even up to identification modulo constants, namely, all vectors $h=(h_1,h_2)\\in\\mathbb{R}^2$ such that $h_1-h_2 \\in[0,1]$.", "claims_and_evidence": "Looks good.", "methods_and_evaluation_criteria": "Seems so.", "theoretical_claims": "I didn't verify the proofs.", "experimental_designs_or_analyses": "No", "relation_to_broader_scientific_literature": "Average reward MDPs are crucial field of studies, with many real world setting, hence the sample complexity for the same, is of great importance.", "essential_references_not_discussed": "> The paper [1], also has similar results $O(\\frac{1}{\\epsilon^2})$ convergence using span norm. Requesting authors to compare their work with this.\n\n\n> [2] also proves sample complexity of $O(\\frac{1}{\\epsilon^2})$, without knowledge of mixing time.\n\n\n\n\n[1] @misc{zurek2024spanbasedoptimalsamplecomplexity,\n      title={Span-Based Optimal Sample Complexity for Average Reward MDPs}, \n      author={Matthew Zurek and Yudong Chen},\n      year={2024},\n      eprint={2311.13469},\n      archivePrefix={arXiv},\n      primaryClass={cs.LG},\n      url={https://arxiv.org/abs/2311.13469}, \n}\n\n[2] @misc{ganesh2024orderoptimalglobalconvergenceaverage,\n      title={Order-Optimal Global Convergence for Average Reward Reinforcement Learning via Actor-Critic Approach}, \n      author={Swetha Ganesh and Washim Uddin Mondal and Vaneet Aggarwal},\n      year={2024},\n      eprint={2407.18878},\n      archivePrefix={arXiv},\n      primaryClass={cs.LG},\n      url={https://arxiv.org/abs/2407.18878}, \n}", "other_strengths_and_weaknesses": "Strengths: Paper is well written as easy to read.   The theoretical results are convincing. The approach (Halpern's iteration) used is very interesting.\n\nWeakness: It is not sure, how the result improves the SOTA, as the $O(\\frac{1}{\\epsilon^2})$ sample complexity without knowledge of mixing time already exits in [1].  \n\n\n\n [1] @misc{ganesh2024orderoptimalglobalconvergenceaverage,\n      title={Order-Optimal Global Convergence for Average Reward Reinforcement Learning via Actor-Critic Approach}, \n      author={Swetha Ganesh and Washim Uddin Mondal and Vaneet Aggarwal},\n      year={2024},\n      eprint={2407.18878},\n      archivePrefix={arXiv},\n      primaryClass={cs.LG},\n      url={https://arxiv.org/abs/2407.18878}, \n}", "other_comments_or_suggestions": "Suggestions:  Better literature surevey would better position the paper and its contribution.", "questions_for_authors": "Q1: The paper states the average reward MDP has no contraction mapping, hence uses Halpern iteration (anchored VI) that has convergece rate of $O(\\frac{1}{k})$. However, as shown in section 6.6 of [1], it proves  average reward MDP Bellman operator is a $\\gamma$-contraction where $\\gamma$ is a function of mixing time of the MDP. It would be appreciated, if the authors could clarify these two.\n\n\n\n\n\n\n[1] [Wiley Series in Probability and Statistics] Martin L. Puterman - Markov decision processes_ discrete stochastic dynamic programming (1994, Wiley-Interscience)", "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": "XLVqxGkAz1", "reviewer": "Reviewer_jzY5", "summary": "This paper studies the sample complexity of weakly communicating average-reward MDPs assuming access to a generative model. The authors focus on developing model-free algorithms by using a stochastic version of Halpern iteration. They show that this approach achieves a sample complexity bound in terms of the span of a bias vector solving the Bellman optimality equations, and unlike some prior work, their algorithm does not require any prior knowledge of this complexity parameter. They achieve this by using a doubling trick combined with a stopping condition. They also adapt their algorithm to discounted MDPs.\n\n## update after rebuttal\n\nI think the authors for their response. I'll maintain my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer's constructive feedback. For the list of references please refer to the reply to review BWFD.\n\n1. Advantage of SAVIA+ compared to [8] and [20]\n\nThe papers [8] and [20] propose model-free and model-based methods under the mixing time and weakly communicating assumptions, respectively. Although they can run without prior-knowledge of mixing times and bias span, they do not allow to determine the number of iterations required to achieve an $\\epsilon$-optimal policy, unless one has a priori bounds on $t_{mix}$ or $h^*$. While our SAVIA algorithm has the same drawback (see Section 3.2), by using a doubling trick and the empirical Bellman error we get SAVIA+ which finds an $\\epsilon$-optimal policy with high probability. This is a key advantage over previous methods, and we believe it is the first method that is \"fully\" prior-knowledge-free. We will clarify this in the revised version.  \n\n2. Novelty of results for discounted MDPs (DMDPs)\n\nOur main contribution is clearly the sample complexity for average MDPs. However, given the novelty of anchoring and recursive sampling in RL, exploring their use for  DMDPs is natural and instructive. Let us discuss the relevance of our Bellman error by comparing to [18, 19]. For ergodic DMDPs with $t_{mix} \\le 1/(1-\\gamma)$, [18] obtains sample complexity $O(SA t_{mix}(1-\\gamma)^{-2} \\epsilon^{-2})$. For weakly communicating and general MDPs, if $H ,B+H \\le 1/(1-\\gamma)$, [19] obtains $O(SA H(1-\\gamma)^{-2} \\epsilon^{-2})$ and \n$O(SA (B+H)(1-\\gamma)^{-2} \\epsilon^{-2})$, respectively. These bounds include the factors $t_{mix}, H, B$ and hold only for $\\gamma$ large enough. In contrast our Theorem 4.2 provides a sample complexity $O(SA (1-\\gamma)^{-2} \\epsilon^{-2})$ to achieve $\\epsilon$-Bellman error, with no additional parameters and assumptions. We believe this is still a meaningful contribution.\n \nThe fixed-point residual, corresponding to the Bellman error in MDPs, has been widely used as a performance measure [10, 14] and, unlike the distance to the Q*, it is computable. This also holds in the generative setting where one can compute the empirical Bellman error, whereas estimating the policy error is more challenging as it involves the g*. Moreover, the information-theoretic lower bound of the Bellman error has been recently studied in the tabular setup [11, 12]. In the generative setting the lower bound for $\\epsilon$-optimal policy is $O(SA (1-\\gamma)^{-3} \\epsilon^{-2})$ [2]. Our Theorem 4.2 shows that the Bellman error is at most $O(SA(1-\\gamma)^{-2}\\epsilon^{-2})$, which we believe is the best upper bound currently available and does not follow from previous results. We will clarify this in the revision.\n\nRegarding Theorem 4.3, as noted by the reviewer, [20] presents a model-based approach with complexity depending on V*.  Although [20, Theorems 9 and 10] guarantee the convergence, they require knowledge of V* to determine the number of iterations to obtain an $\\epsilon$-optimal policy. In contrast, SAVID+ does not require knowledge of Q* to get $\\epsilon$ optimality. In this sense, our Theorem 4.3 improves over prior results. As suggested, we will expand our review of prior works for DMDPs, with a more detailed discussion on model-based and model-free methods.\n\n3. Propositions 2.1 and 4.1\n\nFor completeness and readability we think it is useful to include Propositions 2.1 and 4.1 which connect the Bellman error to the policy error, justifying our focus on the former. Proposition 2.1 is a Q-factor variant of a result for bias vectors in [13], whereas Proposition 4.1 is a simple consequence of estimates for contractions. However, we could not find these statements explicitly in [3] nor other prior works. We will clarify this in the revision and would be happy to include a reference for these facts.\n\n4. Stopping rule\n\nThanks for mentioning the connection with [15]. We note however that [15] considers a model-based algorithm with a stopping rule based on an estimate of the diameter of the MDP, restricting the framework to communicating MDPs. In the revision we will discuss this connection.\n \n5. Prior work on stochastic Halpern in MDPs\n\nWe are sorry for the misunderstanding (line 49 col. 2). We intended to stress that our work is the first to combine recursive sampling with Halpern iteration. As the reviewer noted, we acknowledged that [4] used Halpern iteration in this context (line 207). Specifically, [4] considers stochastic Halpern iteration for nonexpansive maps using minibatches, establishing error bounds in expectation. For average MDPs this yields a residual of at most $\\epsilon$ in expectation with a larger sample complexity $O(SA\\epsilon^{-7})$. We suspect it should be possible to get $\\epsilon$-optimality in high probability with that rate, but the bound is not explicit in its dependence on the $H$. So it is unclear whether it can be implemented without prior knowledge (as the case of [8, 20]). We will clarify this in the revised version.", "claims_and_evidence": "The main claims of this paper are all of a theoretical nature and supported by proofs.", "methods_and_evaluation_criteria": "The methods, namely stochastic Halpern iteration, make much sense for this problem. The evaluation criterion of sample complexity to learn near-optimal policies is standard for this well-studied problem. Measuring the sample complexity required to find a point with small Bellman error in the discounted setting (Theorem 4.2) is new. While this is an interesting finding which I do think is worthy of inclusion in the paper, it is unclear to me what use this has (beyond the fact that low Bellman error implies a bound on the suboptimality, which is probably what we actually care about).\n\nRelated to this task of finding a point with small Bellman error, regarding the comments made about prior work on approximately line 426, first column, it does not follow that these works require the stated complexity $SA/((1-\\gamma)^3 \\varepsilon^2)$ to obtain an $\\varepsilon$ Bellman residual error, it just means that their sample complexity for doing so is upper-bounded by this amount. In fact, several prior works achieve a sampling complexity of $SA/((1-\\gamma)^2 \\varepsilon^2)$ [Wang et al 2023, Zurek & Chen 2024] for computing an $\\epsilon$-optimal policy. In light of this and my comment above on Bellman error vs. suboptimality, I have reservation with the claim on line 429 on Theorem 4.2 being the best known complexity.", "theoretical_claims": "I looked over most results for the average-reward setting, which seem correct.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The achieved sample complexity is inferior to the best prior model-based approaches. The achieved sample complexity is slightly better than that of the best prior model-free approach of Zhang and Xie (2023), removing a lower order ($O(1/\\varepsilon)$) term present in their bound. There also exists an earlier model-based approach https://arxiv.org/abs/2410.07616v1, which is not cited in this paper, which achieves a similar sample complexity bound also without prior knowledge of the span parameter. Therefore the main contribution of this paper is that it is simultaneously model-free, prior-knowledge-free, and obtains a sample complexity bound which is suboptimal by only one factor of the span parameter. This is still a nice contribution, in particular because the problem of removing the need for prior knowledge is important and challenging. \n\nThe results for discounted MDPs do not seem to offer significant improvements upon prior work so I am uncertain about their value. (For instance, the dependence on $Q^\\star$, obtained in Theorem 4.3, is also obtained in Jin et al. 2024b, which is not mentioned. I think more discussion about the relationship of the discounted MDP results to the literature would improve the paper.", "essential_references_not_discussed": "Discussion on Jin et al. 2024b and https://arxiv.org/abs/2410.07616v1 should be added. See \"Relation to Broader Scientific Literature\" above.\n\nhere are several missing references all related to termination conditions. Propositions 2.1 and 4.1 are very standard and well-known (e.g. I think they appear in the Bertsekas Dynamic Programming and Optimal Control books). A stopping rule guaranteeing near-optimality is provided in Tuynmann et al. (2024) (the authors cite this paper but do not mention this stopping rule, which seems at least closely related to the one used in this paper, and so discussion of their relationship seems needed).", "other_strengths_and_weaknesses": "The paper is generally written clearly.\n\nSince the results for discounted MDPs are basically half of the paper, the authors should discuss more related work for solving discounted MDPs (such works are only given a few lines in the introduction).\n\nThe authors should also discuss more related work on model-based methods and include the comparison in Table 1. Particularly in the tabular setting, the distinction between model-based and model-free methods are blurry and not particularly useful.  \n\nIn the introduction (around line 49 column 2) the authors seem to claim that their main contribution is that they are the first to apply a Halpern technique to average-reward MDPs in the generative model setting. However in line 207 column 1 the authors cite the earlier work Bravo and Cominetti (2024) and explicitly mention it was used in this same problem setting. Therefore it seems like it would be beneficial for the authors to clarify their main contributions.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "What is the use of a Bellman error bound (Theorem 4.2) beyond the fact that low Bellman error implies a bound on the suboptimality?", "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": "BHyRhwANUJ", "reviewer": "Reviewer_BWFD", "summary": "This paper introduces a novel value iteration algorithm that achieves near-optimal sample complexity in the setting of *weakly communicating* MDP. A weakly communicating MDP is an MDP whose state space is comprised by a set of states that are accessible from one another and an additional set of transient states. The authors consider average reward and discounted cumulative reward value functions.\n\nThe algorithm proposed is a value iteration scheme with anchoring. Effectively, it can be seen as a form of Halpern's iteration. The sample complexity is $\\tilde{O}(|S||A|\\|h^*\\|^2/\\epsilon^2)$.\n\nThe propose 2 algorithms for the average reward case and 2 for the cumulative discounted rewards. In both cases they start with a base algorithm that is incorporating Halpern's iteration on top of value iteration. Yet, as that algorithm relies on knowledge of the Q values from their optimal values, they propose a scheme that uses a doubling trick to be able to call the primary algorithm and while each time getting a better estimate of the optimal Q value.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments. \n\n1. What stands in the way of achieving linear dependence on $\\\\|h^*\\\\|_{sp}$?\n\nThis is a very interesting and relevant question which we tried to address without success so far. From a technical viewpoint, the quadratic dependence of our sample complexity derives from the batch size $m_k$ in SAVIA which involves the quadratic term $\\\\|d^k\\\\|^2$. In order to reduce the sample complexity and reach the theoretical lower bound with linear dependence on $\\\\|h^*\\\\|_{sp}$, we considered introducing an additional variance reduction to SAVIA+. A possible approach is to implement a restart similar to the one used in [16] for discounted MDPs, which removed a factor $1/(1-\\gamma)$ in the complexity by a carefully designed rerun of the main algorithm. Unfortunately we have not succeeded to adapt this technique to the average reward and at this point it is unclear to us whether this is possible or not. Exploring this is indeed an interesting future direction.\n\n2. Do you think that Halpern iteration could improve with q-learning? \n\nWe are not sure how to interpret this question. It is known that synchronous RVI Q-learning can be viewed as a stochastic version of the Krasnoselskii-Mann (KM) iteration [5, 16]. A discussion on this is also included in the rebuttal to Reviewer hCuT. In the absence of noise, Halpern is known to be optimal achieving a $1/n$ convergence rate [14], whereas KM generally attains at best a $1/\\sqrt{n}$ rate [6]. Interestingly, [12] demonstrated that these non-asymptotic rates for KM and Halpern also hold for average MDPs in the tabular setting. In the stochastic framework, KM has already some type of built-in variance reduction so one might conjecture that in combination with Halpern could attain a smaller complexity. Unfortunately, our attempts in this direction did not succeed and produced worse complexity compared to the pure Halpern with recursive sampling presented here.\n\nReferences\n\n[1] Abounadi J., Bertsekas D., Borkar V.S. (2002), Stochastic approximation for nonexpansive maps: application to Q-learning algorithms, SIAM Journal on Control and Optimization 41(1):1-22.\n\n[2] Azar M.G., Munos R.,  Kappen H.J. (2013), Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine Learning, 91(3): 325-349.\n\n[3] Bertsekas D.P. (2012), Dynamic Programming and Optimal Control, volume II. Athena Scientific, 4th edition.\n\n[4]  Bravo M., Contreras J.P. (2024), Stochastic Halpern iteration in normed spaces and applications to reinforcement learning. arXiv:2403.12338.\n\n[5] Bravo M., Cominetti R., (2024) Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds, SIAM Journal on Control and Optimization, 69:191-219.\n\n[6] Contreras J.P., Cominetti R., (2022), Optimal error bounds for nonexpansive fixed-point iterations in normed spaces, Mathematical Programming, 199(1-2):343-374.\n\n[7]  Ganesh S., Mondal W.U., Aggarwal V. (2024), Order-Optimal Global Convergence for Average Reward Reinforcement Learning via Actor-Critic Approach, arXiv:2407.18878v2.\n\n[8] Jin Y., Gummadi R., Zhou Z., Blanchet J. (2024a) Feasible Q-learning for average reward reinforcement learning. International Conference on Artificial Intelligence and Statistics.\n\n[9] Jin Y., Sidford A. (2020), Efficiently solving MDPs with stochastic mirror descent. International Conference on Machine Learning.\n\n[10] Lieder F. (2021), On the convergence rate of the Halpern-iteration. Optimization Letters, 15(2):405-418.\n\n[11] Lee J., Ryu E. (2023), Accelerating value iteration with anchoring. Neural Information Processing Systems.\n\n[12] Lee J., Ryu E. (2025), Optimal non-asymptotic rates of value iteration for average-reward MDPs. International Conference on Learning Representations.\n\n[13] Puterman M.L. (2014) Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 2nd edition.\n \n[14] Sabach S., Shtern S. (2017), A first order method for solving convex bileveloptimization problems. SIAM Journal on Optimization, 27(2):640-660.\n\n[15] Tuynman A., Degenne R., Kaufmann E. (2024), Finding good policies in average-reward Markov decision processes without prior knowledge. Neural Information Processing Systems.\n\n[16] Wainwright M.J. (2019). Variance-reduced-learning is minimax optimal. arXiv:1906.04697 \n\n[17] Wainwright M.J. (2019). Stochastic approximation with cone-contractive operators: Sharp $\\ell_\\infty$ bounds for Q-learning. arXiv:1905.06265 \n\n[18] Wang S., Blanchet J., Glynn P. (2024), Optimal sample complexity for average reward Markov decision processes. International Conference on Learning Representations.\n\n[19] Zurek M., Chen Y. (2024), Span-based optimal sample complexity for weakly communicating and general average MDPs. Neural Information Processing Systems.\n\n[20] Zurek M., Chen Y. (2025), The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis. arXiv:2410.07616.", "claims_and_evidence": "The claims made are supported by rigorous mathematical proofs.", "methods_and_evaluation_criteria": "The paper is of theoretical focus and there are no experiments.", "theoretical_claims": "I checked the correctness of Proposition 2.1, Proposition 3.1, and Theorem 3.2.", "experimental_designs_or_analyses": "No experiments. The analyses rely on mathematical arguments", "relation_to_broader_scientific_literature": "The authors achieve to design an almost optimal algorithm for MDPs that does not depend on the mixing time and the state spain is weakly communicating. It is a very natural RL problem and the algorithm they propose combines value iteration with Halpern's iteration.", "essential_references_not_discussed": "I do not think they have omitted some essential reference.", "other_strengths_and_weaknesses": "Strengths:\n* the authors manage to get an almost optimal sample complexity\n* the sample complexity is independent of the mixing time of the MDP\n* the algorithmic solution requires minor modification over prior method\n\nWeakness:\n* no experimental evaluation", "other_comments_or_suggestions": "None", "questions_for_authors": "* What stands in the way of achieving linear dependence on $\\| h_* \\|_{sp}$?\n* Do you think that Halpen iteration could improve with q-learning as well, achieving similar results?", "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": "7g2HQ6sbAl", "reviewer": "Reviewer_hCuT", "summary": "The authors propose a new model-free algorithm for solving average-reward weakly communicating MDPs with a generative model. The authors achieved the sample complexity of order $\\widetilde{O}(SAH^2 / \\varepsilon^2)$, where $S$ is a number of states, $A$ is a number of actions, $H$ is a span of an optimal bias function. The main property of the algorithm is that it does not require any prior knowledge on $H$. Additionally, the authors adapted their approach to a discounted setting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful comments. Both of the Reviewer's questions are central to our motivation for writing this work. For the list of references please refer to the reply to Reviewer BWFD.\n\n1. Use of a related variance reduction technique\n\nThe paper [16] is related to ours in the sense that classical (synchronous) Q-learning is fundamentally a stochastic version of the Krasnoselskii-Mann (KM) iteration for a contracting operator. It builds on earlier work by the same author [17], where a sample complexity of $O(SA(1-\\gamma)^{-5}\\epsilon^{-2})$ was established. However, it is important to note that the method cited by the Reviewer applies only in the discounted setting, with complexity measured in terms of the distance to the optimal Q-factor. The argument in that paper is clever: by employing variance reduction techniques inspired by stochastic optimization, it improves the original (suboptimal) complexity by a factor of $1/(1-\\gamma)$. To achieve minimax optimality, a rerun of the main algorithm is carefully designed. From a technical standpoint, the variance reduction argument relies on a precise interplay between the step size (which depends on the contraction parameter), the number of iteration $n$, and the specific structure of the iteration itself. In fact, the number of samples per epoch explicitly depends on $\\gamma$, and the step size decreases as $\\alpha_n=1/(1+(1-\\gamma)n)$.\n\nRegarding the reviewer's specific question, in the average reward setting, the Bellman operator is generally only nonexpansive. This makes it difficult to apply a similar argument due to the crucial role of the discount factor in previous approaches. Nevertheless, we employ a related idea by carefully designing (random) controlled batches to reduce variance. Unfortunately, our approach appears to be constrained to using the square of the span seminorm of $d^k$, as any alternative choice would affect the overall sample complexity.\n\nThat being said, it is worth mentioning that in the discounted case, our SAVID+ method can achieve a sample  complexity of $O(SA(1-\\gamma)^{-4}\\epsilon^{-2})$ for computing an $\\epsilon$-optimal policy (see Theorem 4.3). It remains an open question whether a restarting strategy could be devised in this setting to remove the final $1/(1-\\gamma)$ factor.\n\n2. On the connection of our method to Q-learning\n\nThe well-known (synchronous version of) Q-learning algorithm takes on a different meaning in the average reward case. In this setting, the goal is to compute bias vectors and (bias) Q-factors to derive optimal policies. The closest analogue to Q-learning in this context is the RVI-Q-learning algorithm [1]. The technical challenge here is that, since the optimal value g* is unknown, an auxiliary function is introduced as an online estimator. However, this approach has a drawback: the resulting operator, while related to the Bellman function, may lose its nonexpansiveness. Nevertheless, it is possible to analyze the RVI-Q procedure using a related iteration, which also turns out to be a stochastic version of the KM iteration (see, for instance, [5] for a nonasymptotic analysis in the unichain case), \nwhere the set of fixed points is unbounded.\n\nWe can now answer the question, which, as mentioned, is central to our motivation. From a purely fixed-point perspective, RVI-Q-learning and similar algorithms can be seen as instances of stochastic KM iterations. It is known that in the absence of noise Halpern iteration is faster with a $1/n$ convergence rate for the fixed-point residual (see references in our paper for further details) whereas KM achieves at best a rate of $1/\\sqrt{n}$.\n\nIn conclusion, the Reviewer's intuition is fully correct: our goal was precisely to \"improve Q-learning\" by leveraging the fact that the Bellman error controls the induced policy value (see Proposition 2.1). To reach near-optimal complexity, this idea from fixed-point theory is combined with recursive sampling techniques that have been developed for computing almost-optimal policies \nin average reward MDPs.", "claims_and_evidence": "**Claim 1.** Algorithm SAVIA achieves the $\\varepsilon$-policy error using $\\mathcal{O}(SAH^2/\\varepsilon^2)$ samples but requires the knowledge of $H$;\n\nThe proof looks good to me. \n\n**Claim 2.** Algorithm SAVIA+ achieves the $\\varepsilon$-policy error using $\\mathcal{O}(SAH^2/\\varepsilon^2)$ samples without knowledge of $H$, using a combination of SAVIA and the doubling trick. \n\nThe statement is expected and looks good to me too, however, I did not verify the proof in detail. \n\n**Claim 3.** This algorithm also achieves $\\varepsilon$-error in terms of solution to Bellman equations with the same sample complexity;\n\nThis automatically follows from the structure of the proof.\n\n**Claim 4.** The adaptation of the algorithm to discounting case achieves $\\varepsilon$-solution to Bellman equations using $\\mathcal{O}(SA/(\\varepsilon^2 (1-\\gamma)^2))$ samples and $\\varepsilon$-optimal policy using $\\mathcal{O}(SA/(\\varepsilon^2 (1-\\gamma)^4))$ samples. \n\nThis statement looks good to me, although I did not verify it in detail in the Appendix.", "methods_and_evaluation_criteria": "The paper of theoretical nature and does not contain any empirical studies.", "theoretical_claims": "See **Claims and Evidence** section.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The key contributions of this paper follow the current scientific literature. In particular, the question on the optimal sample complexity without prior knowledge in average-reward MDPs is very interesting and not yet well-studied (although the number of studies of this question increases).", "essential_references_not_discussed": "All related literature was discussed in detail.", "other_strengths_and_weaknesses": "As one of the strengths of the paper, I have to underline the clarity and the quality of writing, as well as a detailed literature review.", "other_comments_or_suggestions": "No additional comments.", "questions_for_authors": "- What do you think, could a variance-reduction technique (Wainwright, 2019) reduce the sample complexity of your method in the average-reward setting? For example, it is observable that in the current approach, the dependence on H^2 comes from evaluation of expectations with respect to $d^k$, but if one replaces $d^k$ with some variance-reduced version with a norm of only a constant order, it can improve the final sample complexity. \n- How is the proposed method connected to a usual Q-learning? Can we treat this method as some modification of Q-learning?\n\n\nWainwright, M. J. (2019). Variance-reduced $ Q $-learning is minimax optimal. arXiv preprint arXiv:1906.04697.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces a model-free algorithm to identify, in the generative model setting, $\epsilon$ optimal policies in weakly communicating MDPs. The algorithm is a value iteration procedure with anchoring that can be seen as a form of Halpern’s iteration. The authors establish an upper bound on its sample complexity, scaling as $SA\| h^\star\|^2/\epsilon^2$, where $\| h^\star\|$ is the span semi-norm of the bias vector (in the average reward scenario). The algorithm does not require any a-priori knowledge. In summary, the main contribution of this paper is to devise an algorithm simultaneously model-free, prior-knowledge-free, and to obtain a sample complexity bound which is suboptimal by only one factor of the span parameter. 

All reviewers acknowledge the quality of the analysis. The only concerns pertain to the novelty of the approach and the comparison with existing work. Halpern’s iteration has been used previously for learning in average reward MDPs. There are also related work presenting algorithms with similar sample complexity but with the knowlegde of an upper bound on the span. The authors here remove this knowledge (by using a doubling trick). 
No experiments are presented and the results are purely theoretical.
Decision: Accept (poster)