Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes
Authors: Jongmin Lee
Ernest K. Ryu
Venue: ICLR 2025 Poster (2025)
Keywords: Average-reward Markov decision process
Average-reward MDP
Value iteration
Reinforcement learning theory
RL theroy
Dynamic programming
Convergence analysis
Anchoring mechanism
Primary area: reinforcement learning
TL;DR: We characterize optimal non-asymptotic convergence rates of VI and its variants in average-reward MDPs.

Abstract: While there is an extensive body of research on the analysis of Value Iteration (VI) for discounted cumulative-reward MDPs, prior work on analyzing VI for (undiscounted) average-reward MDPs has been limited, and most prior results focus on asymptotic rates in terms of Bellman error. In this work, we conduct refined non-asymptotic analyses of average-reward MDPs, obtaining a collection of convergence results advancing our understanding of the setup. Among our new results, most notable are the $\mathcal{O}(1/k)$-rates of Anchored Value Iteration on the Bellman error under the multichain setup and the span-based complexity lower bound that matches the $\mathcal{O}(1/k)$ upper bound up to a constant factor of $8$ in the weakly communicating and unichain setups.

Published as a conference paper at ICLR 2025
OPTIMAL NON-ASYMPTOTIC RATES OF VALUE ITERATION FOR AVERAGE-REWARD MDPs
Jongmin Lee
Ernest K. Ryu
Scoul National University Department of Mathematical Sciences d1 whdd00000 snu. ac.kr
UCLA
Department of Mathematics e eryu@math.uc. ucla www..eduuuuuu
ABSTRACT
While there is an extensive body of research on the analysis of Value Iteration (VT) for discounted cumulative-reward MDPs, prior work on analyzing VI for (undiscounted) average-reward MDPs has been limited, and most prior results focus on asymptotic rates in terms of Bellman error. In this work, we conduct refined non-asymptotic analyses of average-reward MDPs, obtaining collection of convergence results that advance our understanding of the setup. Among our new results, most notable are the (1 (1/kk)-rates of Anchored Value Iteration on the Bellman error under the multichain setup and the span-based complexity lower bound that matches the (1/kk) upper bound up to a constant factor of 8 in the weakly communicating and unichain setups.
INTRODUCTION
Average-reward Markov decision processes (MDPs) are fundamental framework for modeling decision-making. where the goal is maximize long-term, steady-state performance. However, compared to the discounted cumulative-reward counterpart, the average-reward setup is more complex to analyze, and there has been less prior work on it. It is known that while iterates of VI diverge to infinity, the normalized iterates and the Bellman error converge to the optimal average reward under certain aperiodicity condition. However, despite this understanding of convergence, quantifying the convergence of such methods for various classes of average-reward MDPs has been open.
In this work, we conduct refined non-asymptotic analyses of average-reward MDPs, obtaining a collection of convergence results advancing our understanding of the setup. Notably, establish (11/k) convergence rates of Anchored Value Iteration on the Bellman error under the multichain setup, and we present a span-based complexity lower bound that matches the ((1kk)-upper bound up to constant factor of 8 in the weakly communicating and unichain setups.
Non-asym multi MDP
Asym multi MDP
Non-asym
Asym
Non- uni MDP
Asym
Prior works
w.C. MDP
W.C. MDP
uni MDP
1, 2
X
X
X
3, 4
X
X
[5]
X
X
X
Our work
/=
Table 1: Summary of our contributions. (1: Federgruen et al. (1978), 2: Van Der Wal (1981), 1, 3: Schweitzer Federgruen (1977), 4: Schweitzer & Federgruen (1979), Bertsekas (1998), 'Non-asym' stands for non-asympiotic convergence, 'Asym' for asymptotic convergence, 'multi' for multichain, 'w.c.' for weakly communicating, and 'uni" for unichain.) One check mark indicates convergence result (upper bound) and two check marks with strict inequality sign indicate convergence result accompanied by a complexity lower bound but they do not match. Two check marks with equal sign indicate a matching complexity lower bound. For multichain MDPs, present the first non-asymptotic convergence result in Theorem 2. For weakly communicating MDPs, we present the first optimal complexity by matching the non-asymptotic convergence result in Corollary with the complexity lower bound in Theorem 3.

---

Published as a conference paper at ICLR 2025
1.1 NOTATION AND PRELIMINARIES
We quickly review basic definitions and concepts of average-reward Markov decision processes (MDPs) and reinforcement learning (RL). For further details, refer standard references such as Puterman (2014); Bertsekas (2012); Sutton & Barto (2018b).
Average-reward Markov decision processes. Let,M((t be the space of probability distributions over X. Write (S, P.r) to denote the infinite-horizon undiscounted MDP with finite state space
S, finite action space A, transition matrix P: S A M(S), and bounded reward r: 8 A
R. Denote S .M(A) for policy, g 9²) lim on E,, ELD r(se, ax)
for average-reward of a given policy, where Ez denotes the expected value over all trajectories (50, ao, $1, 01 -1, aT-1) induced by P and We say 9 optimal average reward if g (s) max, 9" (s) for all E S. We say π is an e-optimal policy if I|9* g 1l S.
Value Iteration. Let F(X) denote the space of bounded measurable real-valued functions X. With the given undiscounted MDP (S,A) r), for V E F(S), define the Bellman consistency operators 7
(s) = 1 (s).0' s..a) [r(s, a) + V(s')
for all S, and the Bellman optimality operators T (s) max (r(s,a) + Es (,,a)))) [V(s')]}
aeAA
for all E S. For notational conciseness, we write TVV = rr + pVV, where r=(ss Ba ()) (r(s, a)] is the reward induced by policy x and
(* s') Prob(s + s' la x(- s). P(-1s.a))
is transition matrix induced by policy æ We define the standard Value Iteration (VI) for the Bellman optimality operator as
v* TV for 1.2,....
where / is an initial point. After executing K iterations, VI returns the near-optimal policy πK as greedy policy satisfying T v
TVK.
Fixed-point iterations. Given operator T, classical Banach fixed-point theorem (Banach, 1922) states that if T' is contractive, fixed point of T exists and following Picard iteration
* = k-1
for h = 1,2.....
converges to the unique fixed point of T. If is nonexpansive but not contractive such the rotation operator, Picard iteration may not converge to a fixed point. (For undiscounted MDPs, the Bellman optimality operator is nonexpansive but not necessarily contractive.) In such cases, one may use Kransnosel skii-Maann iteration (Mann, 1953; Krasnosel'skke 1955)
x b- (1 du Tx for k: 1,2,
where (ARLEE E [0, 1], or Halpern iteration (Halpern, 1967)
x² = >xax + (1 Ag)TTaa11 for t = 1,2,....
where n is initial point and (Me E [0, 1]. guarantee convergence.
Classification of MDPs. MDPs are classified as follows by the structure transition matrices. (For definitions of basic concepts of MDPs such as irreducible class, recurrent class, transient states, accessibility, etc., please refer to Puterman (2014, Appendix A.2).)
MDP is unichain if the transition matrix corresponding to every deterministic policy consists of a single irreducible recurrent class plus possibly empty set of transient states. MDP is weakly communicating, if there exists closed set of states where cach state in that set is accessible from every other state in that set under some determinisite policy, plus a possibly empty set of states which is transient under every policy. MDP is multichain, if the transition matrix corresponding any deterministic policy contains one or more irreducible recurrent classes.
MDP is weakly communicating if MDP is unichain, and MDP is multichain if MDP is weakly communicating. Since every MDP is multichain, we use the expressions multichain and general interchangeably.
2

---

Published as a conference paper at ICLR 2025
Multichain General
Weakly Communicating
Unichain
Figure 1: Classification of MDPs: Unichain WWeakly Communicating Multichain (General)
Modified Bellman equations. Bellman equations defined as
Following Puterman (2014, Section 9.1.1), we consider the modified
Σ P(s' ([d(),)))(()) g(s),
max r(s,a)+ +
Σ e'ES
P(s' 18,a))(()) h(s) g(())
max
SESS
for all S, and we express these more concisely as max (P* g) = g:
max(r" + h"h = h
We say (g", hh*) is a solution of the modified Bellman equations if (g", hh*) satisfies the two equations and there exists policy n¹ attaining maximum simultancously. It is known that solutions of modified Bellman equations always exist (Puterman, 2014, Proposition 9.1.1). Furthermore, g is unique and it is equal to the optimal average reward (Puterman, 2014. Theorem 9.1.2, 9.1.6). Finally, policy T simultaneously attaining the maximum in the modified Bellman equations an optimal policy (Puterman, 2014, Theorem 9.1.8).
the MDP weakly communicating or unichain, g R is a uniform constant vector, i.e., 9 cl for some e E R, where Rh is the vector with entries all 1 (Puterman, 2014, Theorem 8.3.2, 8.4.1). Then, first modified Bellman equations holds automatically, and modified Bellman equations reduce to
max(r" x + pP*) = - g.
#
1.2 PRIOR WORKS
Average-reward MDP. The setup of average-reward MDP was first introduced by Howard (1960) in the dynamic programming literature. Blackwell (1962) provided theoretical framework for analyzing average-reward MDP. Yushkevich (1974); Denardo Fox (1968) studied modified Bellman equations of multichain MDPs and solutions were characterized by Schweitzer & Federgruen (1978); Schweitzer (1984). In reinforcement learning (RL), average-rewan MDP was mainly considered in the sample- sample-based setup to find optimal policy when the transition matrix and reward unknown (Dewanto et al., 2020). For this setup, Burnetas & Katehakis (1997); Jaksch et al. (2010) analyze regret minimization problem for unichain and communicating MDPs. Also, model-based algorithms (Zhang & Ji, 2019), model-free algorithms (Wei et al., 2020; Wan et al., 2021), policy gradient method (Kakade, 2001), and finite time analysis (Zhang al., 2021) have been studied.
Convergence of Value Iteration. Value iteration (VI) was first introduced in the DP literature (Bellman, 1957) and serves fundamental dynamic programming algorithm for computing the value functions. Its approximate and sample-based variants, such as Temporal Different Learn- ing (Sutton, 1988), Fitted Value Iteration (Ernst et al., 2005; Munos Szepesvári, 2008), Deep Q-Network (Mnih al., 2015), are the workhorses of modern RL algorithms (Bertsekas & Tsitsiklis, 1996; Sutton Barto, 2018 Sa; Szepesvári, 2010). is also routinely applied in diverse settings, including factored MDPs (Rosenberg & Mansour, 2021), robust MDPs (Kumar al., 2024), MDPs with reward machines (Bourel et al., 2023), and MDPs with options (Fruit et al., 2017).
The convergence of VI in average- reward MDPs has been extensively studied. For unichain MDPs, delta coefficient and ergodicity coefficient have been considered as the linear rate VI (Seneta, 2006; Hübner, 1977), (Puterman, 2014, Theorem 6.6. l), and the J-stage span contraction demonstrates
3

---

Published as a conference paper at ICLR 2025
linear rate of VI for every J-th iterations in terms of span seminorm (Federgruen et al., 1978; Van Der Wal, 1981), (Puterman, 2014, Theorem 8.5.2). Bertsekas (1998) proposes A-SSP, which exhibits non-asymptotic linear convergence under the recurrent assumption. When MDP is multichain, it is known that normalized iterates converge to the optimal average reward (Puterman, 2014, Theo- rem 9.4.1) while policy error might not converge to zero. Schweitzer & Federgruen (1977; 1979) established necessary and sufficient conditions of convergence of VI and established asymptotic linear convergence on Bellman error.
For convergence of iterates to the ht solution of modified Bellman equations, White (1963) introduced Relative Value Iteration (RVI) which subtracts a uniform constant for every iteration. Morton & Weeker (1977) studied sufficient conditions of convergence of RVI. Bravo & Cominetti (2024) studied asymptotic convergence rates of Rx-RVI on Bellman error in Q-learning setup, and Bravo & Contreras (2024) also considered Q-learning version of Halpern iteration in average-reward MDP and study sample complexity.
In Section A of the appendix, we present several tables that thoroughly compare the our new results with the prior results of the literature, and refer to Della Vecchia al. (2012) for further detailed conditions of convergence of VI.
Fixed point iterations. The Banach fixed-poine theorem (Banach, 1922) establishes the convergence of the standard fixed-poing iteration with contractive operator. As generalization of Picard iteration, Kransnosel skil-Mann iteration (KM) (Mann, 1953; Krasnosel's skii, 1955) was introduced, and its convergence with general nonexpansive operators was shown by Martinet (1970). The Halpern iteration (Halpern, 1967) converges for nonexpansive operators on Hilbert spaces (Wittmann, 1992) and uniformly smooth Banach spaces (Reich, 1980; Xu, 2002).
When a nonexpansive operator T' is assumed to have a fixed point, the fixed-point residual [7'22 - = is commonly used error measure for fixed-point problems. In Hilbert spaces, the KM iteration with nonexpansive operators was shown to exhibit O(1/VK)-rate by Matsushita (2017). Sabach & Shtern (2017) first established an (11kk))-r was later improved by Lieder (2021); Kim (2021). In general normed spaces, KM iteration with nonexpansive opeator was proven to exhibit (L/VV))rrat (Baillon & Bruck, 1992; Cominetti et al., 2014; Bravo & Cominetti, 2018). The Halpern iteration was shown to exhibit ((1/k) for (nonlinear) nonexpansive operators (Leustean, 2007; Sabach & Shtern, 2017; Contreras & Cominetti, 2022).
for the Halpern iteration, and the constant
Inconsistent fixed-point iteration. A fixed-poim iteration for a nonexpansive operator T without a fixed point is referred to the inconsistent setup, and it is the analog relevant to the average-reward MDP setup. There exist a line of researches about convergence of inconsistent fixed-point iteration in both Hilbert space (Pazy, 1971; Applegate et al., 2024; Bauschke et al., 2014; Liu et al., 2019) and Banach space (Browder & Petryshyn, 1966; Reich, 1973; Baillon, 1978; Reich & Shafrir, 1987). Notably, Park Ryu (2023) studied sublinear convergence rates of KM iteration and Halpern iteration of the inconsistent setup in Hilbert spaces and established optimality by providing complexity lower bound.
Complexity lower bounds. With the information- based complexity analysis (Nemirovski, 1992), complexity lower bound on first-order methods for convex minimization problem has been thoroughly studied (Nesterov, 2018; Drori, 2017: Drori & Taylor, 2022: Carmon et al., 2020; 2021; Drori & Shamir, 2020). If a complexity lower bound matches an algorithm's 's convergence rate, it establishes optimality of the algorithm (Nemirovski, 1992; Kim & Fessler, 2016; Salim et al., 2022; Taylor & Drori, 2023; Drori & Teboulle, 2016; Park & Ryu, 2022). In Hilbert spaces, Park & Ryu (2022) showed exact complexity lower bound on fixed-point residual for deterministic fixed-point iterations with contractive and nonexpansive operators. In fixed- fixed-point problems, Colao & Marino (2021) estab-
lished 2 Q(1/A11V22/ lower bound on distance to solution for Halpern iteration with a nonexpansive operator in q-uniformly smooth Banach spaces. In general normed space, Contreras & Cominetti (2022) provided (11/k) lower bound on the fixed-point residual for the general Mann iteration with nonexpansive linear operator, which includes Picard iteration, KM iteration, and Halper iteration.
In discounted MDPs, Goyal & Grand-Clément (2022) provided lower bound on the Bellman error and distance to optimal value function for fixed-point iterations satisfying span condition with 7-
4

---

Published as a conference paper at ICLR 2025
contractive Bellman operators. Lee & Ryu (2023) improved upon the prior lower bound on Bellman error by a factor 1 - 7 > and further established ([11k) bound in undiscounted MDP. However, none of these works consider the average-reward MDP setup. Zurek & Chen (2023) studied sample complexity of learning a near-optimal policy in an average-reward MDP under generative model.
1.3 CONTRIBUTION
We summarize the contributions of this work as follows.
Non-asymptotic rates. For multichain MDPs, establish the first non-asymplotic convergence rates on Bellman error. Theorems and 2 and Corollary and present the -symptttto sublinear rates both Bellman and policy errors in multichain MDPs (see Tables A.1 and A.2 of the Appendix). For the Relative Value Iteration (RVI) and its variants as described in Section 6, Theorems and establish the non-asymptotic sublinear rates both Bellman and policy emrors and point convergence in weakly communicating MDPs (see Tables A.5 and A.6 of the Appendix).
Complexity lower bound. Theorems 3 and present the first complexity lower bounds for the wwerage-reward MDP setup, one with multichain MDP and another with unichain MDP. These complexity lower bounds apply both to the Bellman error and normalized iterates for value-iteration- type methods satisfying the span condition.
Characterization of optimal complexity. Through our matching the convergence rates (upper bound) and the complexity lower bounds, we first establish the optimal complexity of standard VI in terms the normalized iterates and of Anc-V VI in terms of the Bellman error.
2 PERFORMANCE MEASURES
We quickly review the standard performance measures used to quantify convergence rates of value- iteration-type methods for average-reward MDPs. Let 7 be the Bellman optimality operator of the given MDP, and suppose a method generates sequences { k and 1k= We call V*-v2 with an appropriate scaling factor ag > for k = 0, 1. ... the normalized iterates. We call ag
TV - Vk the Bellman error at V for k 0, 1..... We call g" - Th the policy error at Ty for 0, I....... Again, we call the V TV for k 1,2, 2.... standard Value Iteration (VI) with greedy policy satisfying T V = TV*
Fact 1 (Classical result, (Puterman, 2014, Theorem 9.4.1)). Consider general (multichain) MDP. Then, for k 2 1, the normalized iterates of standard VI with ag l exhibit the rate
V
0
2
| 0 h² 11 k
9
Fact shows that the normalized iterates converge to optimal average reward in multichain MDPs with asymptoii rate. As we will later show with Theorem 4, the ((1/k) -ate on the normalized iterates of Fact exactly optimal. However, it is known that the convergence of normalized iterates does not guarantee convergence of policy error (Della Vecchia et al., 2012, Example 4).
Fact 2 (Classical result. (Puterman, 2014, Theorem 9.1.7, 8.5.5)). Consider general (multichain) MDP. If [[TV V -g" 1l O, I19* y ll O, where TV greedy policy satisfying T TV. Furthermore, if MDP is weakly communicating, I|g* -g" I |[ - - g"
V
Fact 3 (Classical result, (Puterman, 2014, Theorem 9.4.5)). Consider general (multichain) MDP Assume that the transition matrices corresponding every average-optimal deterministic policy are aperiodic. Then, for standard VI, the Bellman error TVV Vk g" Ilos converges to zero. Furthermore, [|g g0 also converges to zero.
Fact shows that, unlike normalized iterate, convergence of Bellman error guarantees convergence of policy error. But the classical asymptotic convergence results the Bellman error of Fact has no quantitative rate (and also additionally requires aperiodicity), so we establish several stronger non-asymptotic rates throughout this paper.
5

---

Published as a conference paper at ICLR 2025
We also briefly mention another performance measure considered in average-reward MDPs. The span seminorm is defined as |ællee = max; T2 min, 2; for I E R". The span seminorm of the Bellman error |[V v lep has been considered for weakly communicating and unichain MDPs because in such setups, the optimal average reward g" is a uniform constant and I|TV* V - -g'llpp = |[VV* - lepp. Therefore, unlike the || || -nom of the Bellman error, the span seminorm is computable without knowledge of 9". In this work, primarily focus convergence rates of the normalized iterates and || =e -norm of the Bellman errors. Nevertheless, we point out that results the latter measure imply rates the span seminorm of the Bellman enror in weakly communicating and unichain MDP, since | Vllap I [TV - g" g01l,o (Puterman, 2014, Section 6.6.1) in such setups.
RELAXED VALUE ITERATION
The Relaxed Value Iteration (Rx-VI)
V = A A +11 --)
(Rx-VI)
for k 1....... where is the Bellman optimality operator, V E R starting point, and 0 S Aạ < 1 for k = 0, 1.... is a greedy policy satisfying T TV for k = 0. Notably, Rx-VI obtains the next iterate as a convex combination between the output Tf and the current point yk=1
We now present our non-asymptotic sublinear converge rates of Rx-VI terms of the Bellman and policy errors while deferring the proofs to Section F of the appendix.
Theorem 1. Consider a general (multichain) MDP. Let (g" ,h") be solution of the modified Bellman equations. For k > K, the Bellman and policy errors of Rx-V VI with A 1/2 exhibits the rate
4 4 1=11,0
l1g" -00 | -V -9'llo
v /3.1411992 )(k K)-
where K =(21|rlls +4|| +6 h- 11 21 /c,
inf 0<6= sES ( 1P" - gl
and S is the set of all deterministic policies. Since denotes the policy in this work, we write (3.141592...) to denote the mathematical constart usually written m.
We clarify that for general (multichain) MDPs, the Bellman error does not bound the policy error. However, our analysis shows that the Bellman error does bound the policy error for k > K.
The characterization of K in Theorem is somewhat intricate when considering general MDPs. This is simplified if we focus on specific class of MDPs which includes weakly communicating and unichain MDPs.
Corollary 1. Consider a a general (multichain) MDP satsifying p= for any policy æ. Let (g* Jt)) be solution of the modified Bellman equations. For k 2 the Bellman and policy errors of Rx-VI with As- = 1/2 exhibit the rute
4 4 10
I1g* - -0 S || - -V 10
(3.141592....
Proof of Corollary 1. We apply Theorem 1. By assumption MDP, S/(m PT g" = 9²) 0.. So c= infree ||P" g" - g" al = oo and K = 0. Finally, we plug K = 0 into Theorem 1.
Note that the weakly communicating MDPs satisfy the assumption Corollary I since g* = cl for some E IR (Puterman, 2014, Theorem 8.3.2) and so p=cl cl for any policy л. In the next section, Anc- VI. Section B of Appendix presents more general results establishing convergence rates for arbitrary 0 in terms of both the Bellman error and the normalized iterates.
will show that the ((1/vk))-n with Rx- Rx-VI can be improved to O(1/k)-rate with

---

Published as a conference paper at ICLR 2025
Broadly speaking, Rx-VI is well-studied algorithm. This averaging mechanism has been widely studied in fixed-point theory literature under the name Krasnosel skir-Mann iteration (Mann, 1953;
Krasnosel'skin 1955; Bauschke & Combettes, 2017; Baillon & Bruck, 1992: Cominetti et al., 2014).
In the dynamic programming literature, the aperiodic transformation (Puterman, 2014, Section 8.5.4),
which averages the transition matrix and identity to make the transition matrix aperiodie, is closely related to this averaging mechanism. In the reinforcement learning literature, TD learning and Q learning use the averaging mechanism stabilize randomness and ensure convergence (Sutton, 1988; Watkins, 1989; Bertsekas & Tsitsiklis, 1995; Bravo & Cominetti, 2024), and in tabular setup, Kushner & Kleinman (1971); Porteus Totten (1978); Goyal & Grand-Clément (2022); Akian et (2022) studied convergence of Rx-VI in discounted MDP setup. However, to the best of our knowledge, no prior work has established non-asymptotic rates of Rx-VI or any other itllt--ttration-typeee method for multichain MDPs. Only Schweitzer & Federgruen (1977; 1979) established asymptotic convergence results for multichain MDPs.
4 ANCHORED VALUE ITERATION
The Anchored Value Iteration
V = Ao + ---6)---11
(Anc-VI)
for k = 1,2..... where T is the Bellman optimality operator, 0 E IR" is starting point, and S Xạ < for 0, 1..... Ty a greedy policy satisfying T p TV for k 0, o.... Notably, Anc-VI obtains the next iterate as convex combination between the output I' and the starting point v (note, RX-VI uses V instead of Vo), We call the A Vo term the anchor term since, loosely speaking, it serves to retract the iterates back toward the starting point Vo. Generally, AS is set to be a decreasing sequence, and then the strength of the anchor mechanism diminishes as the iteration progresses.
We now present our non-asymptotic sublinear converge rates of Anc-VI VI in terms of the Bellman and policy errors while deferring the proofs to Section G of the Appendix.
Theorem 2. Consider a general (multichain) MDP. Let (g" ,hh" be solution of the modified Bellman
equations. For l > K, the Bellman and policy errors of Anc-Ve with A
k42- exhibits the rate
8
K
l1g - g** 1l00 S l|TV -v*
-9'1 - - k+1
=
|1v
1l + k+1 l1g 1lo
where K = =3311rllo 12 0o - -h1llc + +3 +3119-11 11o0) /e,
O<E= TES *ES\(s] P
inf
| ooo
and S is the set of all deterministic policies.
As before, Theorem 2 claims that the Bellman error bounds the policy error for k > K, and the characterization of K in Theorem 2 is simplified we focus on a specific class of MDPs which includes weakly communicating and unichain MDPs.
Corollary 2. Consider a general (multichain) MDP satsifying pr = for any policy æ. Let (9*,h") be a solution of the modified Bellman equations. For l 2 1, the Bellman and policy errors of Anc-Vi VI with A
2 exhibits the rate
k+2
8
llo -r
1|TVV--
1
9
101l
k +
Proof of Corollary 2. Follows from the same line of argument as for Corollary 1.
Note, the anchoring mechanism allows us to improve the rate to ((1kk). In the next section, will show that the (11k) rate is optimal in the weakly communicating setup by providing matching complexity lower bound. Section C of Appendix presents more general results establishing convergence rates for arbitrary 2g in terms of both the Bellman error and the normalized iterates.
The anchor mechanism has been widely studied in minimax optimization and fixed-poin problems (Halpern, 1967; Sabach & Shtemn, 2017; Lieder, 2021; Park & Ryu, 2022; Contreras & Cominetti,
7

---

Published as a conference paper at ICLR 2025
2022; Yoon & Ryu, 2021). In the context of reinforcement learning, Lee & Ryu (2023) applied the anchoring mechanism to VI to achieve an accelerated convergence rate for cumulative-rewart MDPs, and Bravo & Contreras (2024) applied the anchoring mechanism to Q-learning for average-reward MDPs. However, to the best of our knowledge, no prior work established a non-asymptotic rate for value-iteration-type methods for multichain MDP.
We further clarify that our non-asymptotic convergence results in Section 3 and 4 are neither a direct application nor direct adaptation of the prior convergence. VI for the average-reward MDP setup can be thought of as fixed point iteration withoul fixed point, and so most prior analyses assuming the existence of fixed point do not apply. Bravo Contreras (2024); Bravo & Cominetti (2024) study the convergence of Rx-RVI and Anc-RVI in unichain MDPs by applying results derived from the fixed-point iteration setup, but their analyses do not extend mulichain MDPs. the inconsistent fixed point iteration setup, analog relevant to the average-reward MDPs setup, prior analyses for Hilbert space (Pazy, 1971; Applegate et al., 2024; Bauschke et al., 2014; Liu et al., 2019; Park Ryu, 2023) are not applicable to Bellman operators since 8 with || |l -norm is not Hilbert space. The prior analyses for Banach space assuming uniformly Gateaux differentiable norm (Browder Petryshyn, 1966; Reich, 1973; Reich & Shafrir, 1987) uniform convexity (Browder & Petryshyn, 1966) are not applicable either since || || -nor is not uniformly Gateaux differentiable norm and Rd with || -norm is not uniformly convex space. We note that our analyses specifically utilize the structure of Bellman operators and modified Bellman equation to obtain a non-asymptotic convergence rate on both Bellman and policy errors, adapting proof techiniques from Cominetti et al. (2014); Contreras & Cominetti (2022) to the multichain setup.
COMPLEXITY LOWER BOUND
We now present complexity lower bounds establishing optimality of Anc-VI in terms of the Bellman error and standard VI in terms of the normalized iterates. To the best of our knowledge, Theorems and 4 are the first complexity lower bounds for value-iteration-type methods in the wewaade-reward MDP setup.
Following the information-based complexity framework (Nemirovski, 1992), we consider the span condition
V++1 E v + span VO, ,V, V1 ..... TV V*J,
where T is the Bellman optimality operator and span(.A) is set of all finite linear combinations the elements of A. Standard VI, Rx- RI, and Anc-VI all satisfy equation 1.
Optimality of Ane-V VI for Bellman error. We now establish the optimality of Anc-VI VI for weakly communicating and unichain MDPs in terms of the Bellman error.
Theorem 3. Let k 2 0, n 2 k + 2, and o E R". Then there exists a unichain MDP with |S| and |A| such that its modified Bellman equations has a solution (g*,h") satisfying
Σ (TV Ca''VV'-V -V)) V-- -
2
1
V
h"'
k
for any iterates { - satisfying the span condition equation and any choice of real numbers (oiYimo such that Σ 1= 1.
Æ+1 1 - Note that the construction of Theorem 3 a unichain MDP, which is also weakly communicating MDP. The lower bound matches the 8 | - ht upper bound of Corollary 5, which applies to both weakly communicating and unichain MDPs. The upper and lower bounds match up to constant of factor 8, and we therefore conclude optimality for both weakly communicating and unichain MDPs.
we set 04 in Theorem 3, we get TV V* -
k+11
Exact optimality of standard VI for normalized iterates. We now establish the optimality of standard VI for general (multichain) MDPs in terms of the normalized iterates.
8

---

Published as a conference paper at ICLR 2025
Theorem 4. Let k 2 0, + 3, and Vo E R Then there exists multichain MDP with |S] and |A| = such that its modified Bellman equations has a solution (g" ,g*,h" hh)) satisfying
Σ
aa((TV V4)
2
V0 h 1011
k k+1
for any iterates { 1i-0 satisfying the span condition equation and any choice of real numbers {az (o such that Ei=o =1.
pkt1 - 9
If we set
k+I for all = = ,, in Theorem 4, we get
ll This lower bound exactly matches the x+I | h- Il upper bound of Fact and we therefore conclude exact optimality of standard VI in terms of the normalized iterates.
K+I |
DC
Discussion. To clarify, the unichain MDP construction of Theorem 3 is a multichain MDP, so Theorem and Fact together already establish optimality up to a constant factor of However, the multichain construction of Theorem 3 improves the lower bound by a constant factor of 2, and this factor of 2 leads the exact match.
The span condition used in Theorems 3 and 4 are arguably very natural and is satisfied by Standard VI, Ex.VI, and Ane-VI. The span condition is commonly used the construction of complexity lower bounds for first-order optimization methods (Nesterov, 2018; Drori, 2017: Drori & Taylor, 2022: Carmon al., 2020; 2021; Park & Ryu, 2022) and has been used the lower bound for standard VI and Anc-VI (Goyal& & GirandCClémnt 2022; Lee & Ryu, 2023). However, designing that breaks the lower bound Theorem and 4 by violating the span condition remains a possibility, In optimization theory, there is precedence of lower bounds being broken by violating seemingly natural and minute conditions (Hannah et al., 2018; Golowich et al., 2020; Yoon & Ryu, 2021).
algorithm
RELAXED AND ANCHORED RELATIVE VALUE ITERATION
The iterates of standard VI, Rx- RX-VI, and Ane- diverge. For example, the iterates of standard VI asymptotically behave as V ky* as k + co by Fact 1. Of course, the normalized iterates do converge, but we want the iterates themselves to converge, the algorithm must be modified.
The Relative Value Ieeraiion (RVI) subtracts some uniform constant vector at each iteration:
h Th* f(h*-1)
for k = 1,,2,... where T' is the bellman optimality operator, ht E R2" is starting point, E RR" is the uniform constant vector with all entries 1, and f: En R is a continuous function satisfying f(x + cl) = f(x) + e for any E R. Following is one of known convergence results of RVI.
Fact 4 (Classical result, (Bertsekas, 2012, Theorem 4.3.2)). Consider a unichain MDP. Assume that the transition matrices corresponding to every average-optimal deterministic policy are aperiodic, and ((h) (Th); for some fixed
S n. Then, for some solution of modified Bellman equations (g* ht). the iterates of standard RVI converge to h* and (Th*), h converges g".
Like standard VI, iterates of Rx- VI and Ane- VI also diverge as we show in the Theorems 7 and 9 of the Appendix. To ensure convergence of the iterates, can also subtract uniform constant vectors from the iterate. The Relaxed Relative Value Itraation
h 1 + (1 Ao (R -
(Rx-RVI)
for k = 1,2...., where 0 S de < 1 and ho is starting point. Te is greedy policy satisfying
T 1 k for 0, 1.... The Anchored Relative Value Iteration
h² 1 + +(1 > - ff(h -f(h--1 (1)
(Anc-RVI)
for l: = 1,....., where < d < and 1o starting point. He greedy policy satisfying T ht T for k 0,
Now we present our non-asy aomassymptoiic convergence rates of Rx-RVI and Anc-RVI in terms Bellman and policy errors while deferring the proofs Section in Appendix.

---

Published as a conference paper at ICLR 2025
Theorem 5. Consider weakly communicating MDP. Let (g" hh)) be solution of modified Bellman equations. For k 2 1 and, , the Bellman and policy errors of Rx-RVI with 2k = 1/2 exhibits the rate
119* - -1 1 <1|TH* 1²* -g S (33.141592.. 11 l=x
Furthermore, h - 1 and f(h²)I g" for solution of modified Bellman equations ,1)))
Theorem Consider weakly communicating MDP. Let (g",")) be solution of modified Bellman
equations. For k 2 L, the Bellman and policy errors of Anc-Anc--V with Aς-
k42 exhibits the rate
2
11g - 100 S |1hh"
9 1-
k ++1
Furthermore, MDP is unichain, h + h and f(h²)1 + g for some solution of modified Bellman equations (g ht)).
Since Rx-RVI and Anc-RVI generate same policy as Rx-VI and Anc- respectively, the rates of Bellman errors of Rx-RVI and Anc-RVI Theorem 5 and are immediately implied by the rates of Rx-VI and Anc-VI VI in Corollary 1 and 2, respectively. Therefore, the main substance of Corollary I and are the convergence results , f(h))1 + (h g"). Section general results establishing convergence rates for arbitrary A in terms of the Bellman error and convergence of iterates. Lastly. we briefly note that for weakly communicating MDP, non-asymptotic rate on Bellman eπrоr can be obtained from results in Bravo & Contreras (2024); Bravo & Cominetti (2024) by leveraging their convergence analysis with uniform constant g in unichain MDP.
Appendix presents more
CONCLUSION
In this work, we present the first non-asymptotic convergence rates multichain MDPs in terms of the Bellman error. We also provide complexity lower bounds matching the upper bound of Anc-VI VI in terms the Bellman error up to a constant factor of 8 for weakly communicating and unichain MDPs. Finally, also showed that standard VI is exactly optimal in terms of the normalized iterates for multichain MDPs. Our results and proof techniques open the door to future work on non-asymptotic, sublinear, and optimal rates for average-reward MDPs.
One future direction is to fully characterize the optimal non-asymptotic complexity on Bellman error for multichain MDPs, exactly match the lower bound of Theerrm 4. We aim to achieve this goal by enhancing our lower bound through the consideration of more delicate worst-case multichain MDPs.
current upper bound of Theorem 2, with its dependence K, does
Finally, we highlight an observation implied by our results: the "correct" rates for (undiscounted) average-reward MDPs sublinear, i.e., something like (1/k).. This contrasts with the classical y-discounted sumulative-rewart MDP setup, where we are accustomed to O()*) We expect future work analyzing other average-rewan MDP setups and algorithms similarly discover optimal sublinear rates.
8 ACKNOWLEDGMENTS
This work is supported by the National Research Foundation Korea (NRF) grant funded by the Korea government (No.RS-2024 20..002002400022233... We thank Tacho Yoon for providing valuable feedback.
REFERENCES
Marianne Akian, Stéphane Gaubert, Zheng Qu, and Omar Saadi. Multiply accelerated value iteration for non-symmetric affine fixed point problems and application to Markov decision processes. SIAM Journal Matrix Analysis and Applications, 1991):199-20 232, 2022.
David Applegate, Mateo Díaz, Haihao Lu, and Miles Lubin. Infeasibility detection with primal-dual hybrid gradient for large-scale linear programming. SIAM Journal on Optimization, 34(1):459-44 -84, 2024.
10

---

Published as a conference paper at ICLR 2025
Jean-Bernard Baillon. On the asymptotic behavior of nonexpansive mappings and semigroups in banach spaces. Houston J. Math., 4(1):1-9, 1978.
Jean-Bernard Baillon and Ronald E Bruck. Optimal rates of asymptotic regularity for averaged nonexpansive mappings. Fixed Point Theory and Applications, 128:27-66, 1992.
Stefan Banach. Sur les opérations dans les ensembles abstraits leur application aux équations intégrales. Fundamenta Mathematicae, 3(1):133-181, 1922.
Heinz H Bauschke and Patrick I. Combettes. Conver Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2th edition, 2017.
Heinz H Bauschke, Warren L Hare, and Walaa Moursi. Generalized solutions for the sum two maximally monotone operators. SIAM Journal Control and Optimization, 52(2):1034-1047, 2014.
Richard Bellman. A Markovian decision process. Journal of Mathematics and Mechanics, 6(5): 679-684, 1957.
D. Bertsekas and J. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996.
Dimitri P Bertsekas. A new value iteration method for the average cost dynamic programming problem. SIAM journal control and optimization, 36(2):742-759 1998.
Dimitri P Bertsekas. Dynamic Programming and Optimal Control, volume II. 4th edition, 2012.
Dimitri Bertsekas and John N Tsitsiklis. Neuro-Dyye Maaro--ynamic Programming. Athena Scientific, 1995.
David Blackwell. Discrete dynamic programming. The Annals of Mathematical Statistics, 33: 719-726, 1962.
Hippolyte Bourel, Anders Jonsson, Odalric-Ambryn Maillard, and Mohammad Sadegh Talebi. Exploration reward machines with low regret. International Conference on Artificial Intelligence and Statistics, 2023.
Mario Bravo and Roberto Cominetti. Sharp convergence rates for averaged nonexpansive maps. Israel Journal of Mathematics, 227:163-188, 2018.
Mario Bravo and Roberto Cominetti. Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds. SIAM Journal on Control and Optimization, 62(1):191-219, 2024.
Mario Bravo and Juan Pablo Contreras. Stochastic halpern iteration in normed spaces and applications to reinforcement learning. arXiv preprint arXiv:2403. 2338,, 2024.
Felix Earl Browder and Walter Petryshyn. The solution by iteration of nonlinear functional equations in banach spaces. Bulletin of the American Mathematical Society, 72:571-575, 1966.
Apostolos N Burnetas and Michael N Katehakis. Optimal adaptive policies for markov decision processes. Mathematics of Operations Research, 22(1):222-255 1997.
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds finding stationary points I. Mathematical Programming, 184(1-2))1 (1111))71--12,, 2020.
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points II: first-order methods. Mathematical Programming, 185(1-2):11-355, 2021.
Vittorio Colao and Giuseppe Marino. On the rate of convergence of Halpern iterations. Journal of Nonlinear and Convex Analysis, 22(12):2639 2646, 2021.
Roberto Cominetti, José Soto, and José Vaisman. On the rate of convergence of Krasnosel sskii- Mann iterations and their connection with sums of Bernoulis. Israel Journal of Mathematics, 199 (2):757-772, 2014.
Juan Pablo Contreras and Roberto Cominetti. Optimal error bounds for non-expansive fixed- fixed-point iterations in normed spaces. Mathematical Programming, 19941-2)343-374, 2022.

---

Published as a conference paper at ICLR 2025
Eugenio Della Vecchia, Silvia Di Marco, and Alain Jean-Marie. Illustrated review of convergence conditions of the value iteration algorithm and the rolling horizon procedure for average-cost MDPs. Annals of Operations Research, 199:193-218 2012.
Eric V Denardo and Benneu L Fox. Multichain Markov renewal programs. SIAM Journal on Applied Mathematics, 16(3):468-487, 1968.
Vektor Dewanto, George Dunn, Ali Eshragh, Marcus Gallagher, and Fred Roosta. Average-rewand model-free reinforcement learning: systematic review and literature mapping. arXiv preprint arXiv:2010.0889 089200 2020.
Yoel Drori. The exact cetemmattionbbseee complexity of smooth convex minimization. Journal of Complexity, 39:1-16, 2017.
Yoel Drori and Ohad Shamir. The complexity of finding stationary points with stochastic gradient descent. International Conference Machine Learning, 2020.
Yoel Drori and Adrien Taylor. On the oracle complexity of smooth strongly convex minimization. Journal of Complexity, 68, 2022.
Yoel Drori and Mare Teboulle. An optimal variant of Kelley's cutting-plane method. Mathematical Programming, 160(1-2):211351. 2016.
D. Ernst, P. Geurts, and L. Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 2005.
Awi Federgruen, Paul J Schweitzer, and Hendrik Cornelis Tijms. Contraction mappings underlying undiscounted Markov decision problems. Journal of Mathematical Analysis and Applications, 65 (3):711-730, 1978.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Emma Brunskill. Regret minimization in mdps with options without prior knowledge. Neural Information Processing Systems, 2017.
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. Conference on Learning Theory, 2020.
Vineet Goyal and Julien Grand-Clément. A first-order approach to accelerated value iteration. Operations Research, 71(2):517-533 2022.
Benjamin Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathernatiaal Society, 736))557-961, 1967.
Robert Hannah, Yanli Liu, Daniel O' O'Connor, and Wotao Yin. Breaking the span assumption yields fast finite-sum minimization. Neural Information Processing Systems, 2018
Ronald A Howard. Dynamic Programming and Markov Processes. John Wiley and Sons, 1960.
Gerhard Hübner. Improved procedures for eliminating suboptimal actions in markov programming by the of contraction properties. Transactions of the Seventh Prague Conference Information Theory, Statistical Decision Functions, Random Processes, 1977.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning, Journal of Machine Learning Research, 11(51):1563-1600, 2010.
Sham M Kakade. A natural policy gradient. Neural Information Processing Systems, 2001.
Donghwan Kim. Accelerated proximal point method for maximally monotone operators. Mathemati- cal Programming, 190(1-2):77-77, 2021.
Donghwan Kim and Jeffrey A Fessler. Optimized first-order methods for smooth convex minimization. Mathematical Programming, 159(1-2):81-10) 2016.
Mark A Krasnosel's skii. Two remarks on the method of successive approximations. Uspekhi Matematicheskikk Nauk, 123 1955.
12

---

Published as a conference paper at ICLR 2025
Navdeep Kumar, Kaixin Wang, Kfir Yehuda Levy, and Shie Mannor. Efficient value iteration for s-rectangular robust markov decision processes. International Conference on Machine Learning. 2024.
Harold Kushner and A Kleinman. Accelerated procedures for the solution of discrete Markov control problems. IEEE Transactions Automatic Control, 16(2):147-152, 1971.
Jongmin Lee and Ernest Ryu. Accelerating value iteration with anchoring. Neural Information
Processing Systems, 2023.
Laurentiu Leustean. Rates of asymptotie regularity for Halpern iterations of nonexpansive mappings. Journal of Universal Computer Science, 13(11):1680-16) 2007
Felix Lieder. On the convergence rate of the Halpem- itteration. Optimization Letters, 15(2):405-415 2021.
Yanli Liu, Ernest Ryu, and Wotao Yin. A new use of Douglas Rachford splitting for identifying infeasible, unbounded, and pathological conic programs. Mathematical Programming, 177(1): 225-253, 2019.
W Robert Mann. Mean value methods in iteration. Proceedings of the American Mathematical Society, 4(3):506 510, 1953.
B. Martinet. Régularisation d' d'inéquations variationnelles par approximations successives. Revue Française de Informatique et Recherche Opérationnelle, 4(R3):154-153 1970.
Shin-Y Ya Matsushita. On the convergence rate of the Krasnosel skii-Mann iteration. Bulletin of the Australian Mathematical Society, 96(1):162-170, 2017.
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, and et al. Human-level control through deep reinforcement learning. Nature, 518(7540):599-33,,
2015. 2015.
Thomas E Morton and William E Wecker. Discounting, ergodicity and convergence for Markoy decision processes. Management Science, 2388)880-9900, 1977.
R. Munos and C. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 2008.
Arkadi Semenovič Nemirovski. Information-based complexity of linear operator equations. Journal of Complexity, 8(2):153-173 1992.
Yurii Nesterov. Lectures on Convex Optimization. Springer, 2nd edition, 2018.
Jisun Park and Ernest K Ryu. Exact optimal accelerated complexity for fixed-point iterations. International Conference on Machine Learning, 2022.
Jisun Park and Ernest K. Ryu. Accelerated infeasibility detection of constrained optimization and fixed-point iterations. International Conference on Machine Learning, 2023.
A Pazy. Asymptotic behavior of contractions in hilbert space. Israel Journal of Mathematics, 9: 235-240, 1971.
Evan L Porteus and John C Totten. Accelerated computation of the expected discounted return in Markov chain. Operations Research, 26(2):350-358, 1978.
Martin I.. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 2nd edition, 2014.
Simeon Reich. Asymptotic behavior of contractions in banach spaces. Journal of Mathematical Analysis and Applications, 44(1):57-70, 1973.
Simeon Reich. Strong convergence theorems for resolvents of accretive operators in Banach spaces.
Journal of Mathematical Analysis and Applications, 75(1):287-292. 1980.
13

---

Published as a conference paper at ICLR 2025
Simeon Reich and Itai Shafrir. The asymptotic behavior of firmly nonexpansive mappings. Proceed- ings of the American Mathematical Society, 101(2)226-255,, 1987.
Aviv Rosenberg and Yishay Mansour. Oracle-efficient regret minimization in factored mdps with unknown structure. Neural Information Processing Systems, 2021.
Shoham Sabach and Shimrit Shtern. first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27(2):640-66 (6006666666,0,, 2017.
Adil Salim, Laurent Condat, Dmitry Kovalev, and Peter Richtárik. An optimal algorithm for strongly convex minimization under affine constraints. International Conference on Artificial Intelligence and Statistics, 2022.
Paul Schweitzer. On the existence of relative values for undiscounted Markovian decision processes with a scalar gain rate. Journal of mathematical analysis and applications, 104(1):67-78, 1984.
Paul Schweitzer and Awi Federgruen. The asymptotic behavior of undiscounted value iteration in Markov decision problems. Mathematics of Operations Research, 2(4):360-381) 1977.
Paul Schweitzer and Awi Federgruen. The functional equations of undiscounted Markov renewal programming. Mathematics of Operations Research, 3(4):308-321, 1978.
Paul J Schweitzer and Awi Federgruen. Geometric convergence of value-iteration in multichain Markov decision problems. Advances in Applied Probability, (111:188-211) 1979.
E Seneta. Non-Negative Matrices and Markov Chains. Springer Science & Business Media, 3th edition, 2006.
R. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 1988.
R. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018a.
Richard Sutton and Andrew G Barto. Reinforcement Learning: An introduction. MIT press, 2nd edition, 2018b.
C. Szepesvári. Algorithms for Reinforcement Learning. Morgan Claypool Publishers, 2010.
Adrien Taylor and Yoel Drori. An optimal gradient method for smooth strongly convex minimization. Mathematical Programming, 199(1-2):557-59) 2023.
Johannes Van Der Wal. Stochastic dynamic programming: successive approximations and nearly optimal strategies for Markov decision processes and Markov games. 1981.
Yi Wan, Abhishek Naik, and Richard $ Sutton. Learning and planning in average-reward Markov decision processes. International Conference on Machine Learning, 2021.
C. C. H. Watkins. Learning from Delayed Rewards. PhD thesis, 1989.
Chen- Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model-free reinforcement learning in infinite-horizon average-reward Markov decision processes. International conference on machine learning, 2020.
D. J. White. Dynamic programming, Markov chains, and the method of successive approximations. J. Math. Anal. Appl, 6(3):373-376, 1963.
Rainer Wittmann. Approximation of fixed points of nonexpansive mappings. Archiv der Mathematik, 58(5):486 491, 1992.
Hong-Kun Xu. Iterative algorithms for nonlinear operators. Journal of the London Matheratical Society, 66(1):240-256 2002.
TaeHo Yoon and Ernest K Ryu. Accelerated algorithms for smooth convex-concave minimax problems with (11k?²) rate on squared gradient norm. International Conference on Machine Learning, 2021.
14

---

Published as a conference paper at ICLR 2025
AA Yushkevich. On class of strategies in general Markov decision models. Theory of Probability & Its Applications, 18(4):777-779, 1974.
Sheng Zhang, Zhe Zhang, and Siva Theja Maguluri. Finite sample analysis of average-reward td learning and q-learning. Neural Information Processing Systems, 2021.
Zihan Zhang and Xiangyang Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. Neural Information Processing Systems, 2019.
Matthew Zurek and Yudong Chen. Span-based optimal sample complexity for average reward MDPs. arXiv preprint arXiv:2311. 2023.
15

---

Published as a conference paper at ICLR 2025
A COMPARISON WITH PRIOR CONVERGENCE RESULTS IN TERMS OF PERFORMANCE MEASURES
In this section, we present asymptotic and non-asymptotic convergence results prior works and our work in terms of Bellman error, policy error, span seminorm, and normalized iterates. We denote the correspondence between numbers and prior works as follows. [1: Federgruen et al. (1978), Van Der Wal (1981), 3: Schweitzer & Federgruen (1977), 4: Schweitzer & Federgruen (1979), Bertsekas (1998), 6: Puterman (2014), 7: Bravo & Cominetti (2024), 8: Bravo & Contreras (2024), 9: Bertsekas (2012))
A.1
BELLMAN ERROR
Non-asym multi MDP
Asym multi MDP
Non-asym W.c. MDP
Asym
Non-asym uni MDP
Asym uni MDP
Prior works
W.C. MDP
1.2
3.4
X
X
[5]
Rx- Rx-VI VI
Anc-VI
A.2
POLICY ERROR
Non-asym multi MDP
Asym multi MDP
Non-asym
Asym
Non-asym uni MDP
Asym uni MDP
Prior works
w.C. MDP
w.C. MDP
1,
X
X
X
3.4
X
[5]
X
X
X
/
RX-VI
V
V
V
Ane-VI
/
V
/
A.3
SPAN SEMINORM
Non-asym multi MDP
Asym multi MDP
Non-asym w.c. MDP
Asym
Non-asym uni MDP
Asym uni MDP
Prior works
W.C. MDP
1,
N/A
N/A
3, 4
N/A
N/A
X
5
N/A
N/A
X
/
Rx-
N/A
N/A
/
Anc-VT VI
N/A
N/A
V
/
/
/
A.4
NORMALIZED ITERATES
Non-asym multi MDP
Asym multi MDP
Non-asym w.c. MDP
Asym W.C. MDP
Non-asym uni MDP
Asym uni MDP
Prior works
6
Rx-VI
Anc-VI
A.5
BELLMAN ERROR (RVI)
Non-asym multi MDP
Asym multi MDP
Non-asym w.c. MDP
Asym
Non-asym uni MDP
Asym
Prior works
w.c. MDP
uni MDP
N/A
N/A
N/A
N/A
X
X
N/A
N/A
Rx-RVI
N/A
N/A
V
Anc-RVI
N/A
N/A
16

---

Published as a conference paper at ICLR 2025
A.6
POLICY ERROR (RVI)
Non-asym multi MDP
Asym multi MDP
Non-asym MDP
Asym
Non-asym uni MDP
Asym uni MDP
Prior works
MDP
N/A
N/A
X
N/A
N/A
9
N/A
N/A
X
X
/
Rx-RVI
N/A
N/A
/
Anc-RVI
N/A
N/A
V
/
/
/
A.7
SPAN SEMINORM (RVI)
Non-asym multi MDP
Asym multi MDP
Non-asym
Asym
Non-asym uni MDP
Asym MDP
Prior works
w.c. MDP
W.C. MDP
N/A
N/A
X
N/A
N/A
X
9
N/A
N/A
X
/
Rx-RVI
N/A
N/A
V
Anc-RVI
N/A
N/A
V
B CONVERGENCE RATES OF RX- VI WITH ARBITRARY X
In this section, we present the convergence rates of Rx-VI for arbitrary A in terms of both the Bellman error and the normalized iterates.
Theorem Consider a general (multichain) MDP. Let (g","") hh*) be a solution the modified Bellman equations. For k > K, the normalized iterates of Rx- VI with ag = Et= (1) exhibits the rate
V VO
2(1 11 11)
|
10
(1-()
Theorem 8. Consider general (multichain) MDP. Let (g", "h" be solution of the modified Bellman equations. Let < X3 for 1 LSS j and lim Xj < Then, there exist 0 < such that for < the Bellman and policy errors of RI exhibit the rates
2 2|1v0
11111
16 - g S TV Vk 9"
I1
3..141992...
EE Ar X;)
Specifically, K is the minimum iteration number satisfying if K S k, generated by Rx- VI satisfies paxy" 5* g", first modified Bellman equation.
We defer the proofs to Appendix F. Note that Theorems 7 and 8 imply the convergence of normalized
iterate and Bellman error to g" respectively when Σe, (1 A₂) = oc and Σ A, - A,) = oc.
Interestingly. for normalized iterate, Theorem I recovers rate of standard VI in Fact 1. Corollary 3. Consider general (multichain)) MDP. Let (g" ,h") be solution of the modified Bellman equations. The normalized iterate of Rx- in Theorem 7 is optimized when Ag. 0 with
Vk
V
2 ||vo h- b0.0 k
9
b
Proof. By AM-GM inequality, have 11 (I < Eigg A since X < 1. This 1-1
implies 1 S Σ (1-x. and
for i, equality holds. Therefore, by plugging X; 0 in
Theorem 7, we get the desired result.
L
Lastly, we present the non-asymptotic rate of Rx- VI with arbitrary A in specific class of MDPs which includes weakly communicating.
17

---

Published as a conference paper at ICLR 2025
Corollary 4. Consider a general (multichain) MDP satsifying P = for any policy Let ,g*,h") be a solution of the modified Bellman equations. Let Xj < for $ Then, for S the Bellman error Rx- VI exhibit the rates
21vo 1111
11g - 110 S | vk -g'l S
(3.141592... ... ازكز )z X,)
Proof. We apply Theorem 8. By assumption on MDP, S/1T P= = ge) =0. So inf ||P g" g01loo oo and K = 0. Finally, we plug K 0 into Theorem 8
C CONVERGENCE RATES OF ANC-VI VI WITH ARBITRARY AE:
In this section, we present the convergence rates of Anc-VI for arbitrary As in terms of both the Bellman error and the normalized iterates.
Theorem Consider a general (multichain) MDP. Let (g"h"") be a solution of the modified Bellman Az)) exhibits the rates equations. The normalized iterates of Ane-V VI with >i= 11
Vk
2(1 - Xx)
1| h-" 10
9
k 11
(1
2i=1 11: (1
Theorem 10. Consider a general (multichain) MDP. Let (g", be solution of the modified
Bellman equations. Let Act1 S. dς- < for 1 S k and lim Xς. = 0. Then, there exist 0 < K such that for K < k the Bellman and policy errors of Anc-nc VI exhibit the rates
52(1-
g0* S II
52 -
yh- 10
1-
Σ X.1 x1 -2,)
110 1
+ 21T k(1 23) 11
Specifically, K. is the minimum iteration number satisfying S Ti generated by Ane-Ve VI satisfies prx g" = g", first modified Bellman equation.
We defer the proofs to Appendix G. Note that Theorems 3 and 4 imply the convergence of nor- malized iterate and Bellman error g respectively when lim Σ (1 X,) and lime-soe E AT (1 X1) 1. We briefly mention that like Rx-VI, convergence rate of normalized iterate of Ane- Inc-IT is optimized when A and recover rate of standard VI in Fact 1.
Lastly, we present the non-asymptotic rate of Anc-Vi VI with arbitrary A in specific class of MDPs which includes weakly communicating.
Corollary 5. Consider a general (multichain) MDP satsifying P=g* = =g" for any policy n. Let (9* hit) be a solution of the modified Bellman equations. Let d S As 1.r < k. Then, there exist O < K such that for K < k, the Bellman and policy errors of Anc- VI exhibit the rates
- S T vk 1011 22
Σ 1 (1 (1)))))3
1100 -1--11111-- 11
Proof. We apply Theorem By assumption on MDP, 5/(z (/" = -²) 0. So
infaea ||""g" -golloo oo and K = O. Finally, we plug K = () into Theorem 10
18

---

Published as a conference paper at ICLR 2025
D CONVERGENCE RATES OF RX-RVI AND ANC-RVI WITH ARBITRARY XE
In this section, we present the convergence rates of Rx-RVI and Anc-RVI for arbitrary A in terms of both the Bellman error.
j
Theorem 11. Consider weakty communicating MDP. Let (g* hh) be solution of the modified Bellman equations. Let 0 < Aj- fforr 1 J. Then, for 1 S k, Rx-RVI exhibit the rates
2 1 h- 101
l1g g- 10 $ Th h g" S
(3.141592...
EE 1
and if lim sup A, < h² converges to htt and f(hh)1 converges to g" for some solution of modified Bellman equations (g", ,
Theorem 12. Consider weakly communicating MDP. Let (g",h") be solution of the modified Bellman equations. Let AR+1 S Au= < 1 S k. Then, Anc-RVI exhibit the rates
l1g" gg" 11 S |h h 9" 10 22
Σ Em -2)) 111. 101l.0
and if lim 0 and MDP is unichain. h converges to h* and f(h")1 converges to g" for some solution of modified Bellmun equations (g" h))).
We defer the proofs to Appendix We note that rates of Bellman errors of Rx-RVI and Anc-RVI in Theorem 11 and 12 are exactly match the rates of Rx-VI and Ane-VI VI in Corollary 4 and respectively.
E PRELIMINARIES
In this section, we define some notations and introduce elementary propositions used in proofs.
E. NOTATIONS
We denote V V ii (s) for all E S and V, V RR.
We denote -1 AjA,-1 ... As (ascending order) and 11 A; A4Au-1 ... .. (descending order) where 5 < k and A, px for j < i k. We define 11 _ = 1 and Σi= A, = 0 if 0 < k j.
We denote P* lim Ei=o p for Cesaro limit of stochastic matrix P (Cesaro limit of stochastic matrix always exist (Puterman, 2014, Theorem A.6)).
E.2 PROPOSITIONS
Proposition 1. Bi S A B2 implies ||All S max{]| 1lao |2
Proof. By definition of llo, we get the desired result.
Proposition 2. If P1, Pi,PP P2 are stochastic matrices and 0 < a, b, there exist stochastic matrix such that aP1 bP: (a b)P.
Proof. Define P(i.j) (a b)++)) + (i) Then, by simple calculation, we get the desired result.
then Proposition 3. (Bertsekas, 2012, Lemma 1.1.1) Vf V, then T ST TV ST
Proposition 4. For any policy n. D is nonexpansive linear operator such that if V V. PVV V.
19

---

Published as a conference paper at ICLR 2025
Proof. (f) for all E & a A, T = pr. Then by Proposition 3, have the desired result.
Proposition 5. For a stochastic matrix P, P-P = PP P.
Proof. By definition of p*, we get the desired result.
Proposition 6. Pf g" g", 11g* gl 11x0 | - V - -g" where TV T.
Proof. Since pay g¹ gg, (p=v)* , g" = =g¹. Then v = (p*v)* (r (pav)* (r+v+
--vV-VV VV--"g") 0²)= = (Pav) (TV V -V-g") -g"), where second equality from Proposition Therefore, we have 119* - ax ITV V - g llx.
F OMITTED PROOFS OF THEOREMS FOR SECTION 3 AND B
In this section, we present omitted proofs convergence theorems of Rx-VI. We prove Theorems 7, 8, and turn.
F.1 PROOF OF THEOREM 7
First, we prove the following lemma by induction.
Lemma 1. For the iterates {V* of Rx-VI,
1==1,,,..
V (4p===(0t//(
11 H+ 1 10411 (1-x-)))m))))))) (1 (1-A)+1)r33
1=0
Proof. - + (1- - (1-++(1-))P0o]) + (1 (1- A1T
By induction,
pk+1
-1+11
1TP0 TT (1 \
k-1
+
[1++1 1 (1- ) (1 ds+1)m
1=0
+ (1 - (x41)
Pr II MP= + (1 ) pai
IP 1 (1tt1 (1 {p-))pa)) (1 )ot2)r + trm
1=0
O1 + (1 A
I (1 + (1 )1+z)pT.)) (1- )3+1)m
(2441
==0
Now, we prove following key lemma.
20

---

Published as a conference paper at ICLR 2025
Lemma 2. For the iterates (V*) )==0,12... Rx- VI.
Vk
Σ (1 < (1 - -11) + ht*
j=1
11 + 1
-1+1)) 11*) S V Σ (1 >,)99
j=1
Proof.
For the first inequality, we have Vk
=II 1 + )++1)
1 i=k- (1m (1-N)p())))) )541)r
)m1))=)))
11
(1441/ + (1 - A
+++t1 1=k-1 (1++1 + - { (1 A5+1)(1 + -I--aaifh
- (1it1 + +(1 )
|++1 (1141 / +1 >i+1) - A1+11 - (1 - {j+1)P=s)
+ Σ (1 Xj)9
==1
11 (14+1l + -1- 1 + (I 11
+ (1 )
k
(1 - \z)g
j=1
k Σ (1 Az)g"
11
(1411l + (1- - h +
h²)
j=1
where first equality comes form Lemma 1, first inequality follows from second Bellman equation, second inequality follows from first Bellman equation, and second equality from telescoping-sum argument.
We now prove the second inequality.
IP==x-10W442 + (1- \4
I1 1 + (1- (11+4()))))))))) (1 *s+1)r
1=
-I +
n i+ - (1411 (1 \141)== ((1 *s+1)r
- (A - (p-
1 (A4 1 + (1- >s+1)(0* (1- )1*)
&
(1- + 1² n70 T + (1 PF. -11)
3=1
where first inequality follows from Lemma and the fact that ( are greedy policies, first equality comes from second Bellman equation, and second equality is from first Bellman cquation.
We ready prove Theorem 7.
21

---

Published as a conference paper at ICLR 2025
Proof of Theorem 7. By Lemma 2, we have
k (1 >z)g" 2 1 + (1 -1 + +1- vo
/b Vo
j=1
1 + (1 - d141)D=.)) (I.) ((+))=)
(vo (vo -17)
- (1 -4)))1 h²),
and
Vk - po '(1 >y)g* 2 I1 (1++1 + (1 (1+1) (VV - hh') + h² -Vo
j=1
- (Ai+1 + (1 )et1)P=.)- - (TT ( (Vo - -11t)
(1 11 1 [((= - 11)).
By Proposition 1, this implies
1 vo Σ
(1 -y
2 TT - 1|v0 - h-1 111
1=1
Hence, conclude
V 04
2(1 nT 11)
- g"
-1 10
Σド=1
k
(1 22))
Σj -2)
F.2 PROOF OF THEOREM
First, define of = (II (1 (1 for ş and ag = 1, where {ARhse e [0, 1]. Let An 0 for computational conciseness. Following lemma will simplify calculation in later proof.
Lemma 3. For 0 < K2 < kn,
a
1+111
a,
a
a
j
to
k
H-1
h1
a a,
ko ki
Σ |=j
(1- Ar)
= Σ
(1 A1).
d= 11 1=0
22

---

Published as a conference paper at ICLR 2025
Proof. First and second equality can be proved by simple calculation. With first and second equality, we prove third equality as follows.
h2
Σ 1=j
[a->2)) 21)
m1)
=
h1 l2 1= 1
(1
21)
Σ
aj
=k-11j00
1=0
1=0
a (1-xi) X1)
Σ
12kg+//=kg+
h
Σ
a (1 Ar)
km
i' ka + 1mm k2+1
h
kg Σ
Σ
(1- 20a
k
1
11
1=
Σ (1 (1- 11) - 1
l
=
(1 A1)
+ - k
k2+1
21-
1 ki
1 1221
h
Σ (1-1))
1=
By simple calculation, for the iterates (V* J0=0,1,2,.. of Rx-VI,
VE
(u (
1=
where TV-1 = Vo, and we have following lemma.
Lemma 4. For the iterates {V*) 1, of Rx- VI.
hg
k
pha - p22
J=0 1=
for 0 S 22 S kl.
Proof. By definition, we have
l2
ksa=
ks
NiTVi11
lo TVi-1
a
0=0
k=0
Av
a k
+
(a
a (
#
k2
a T
ap af
i=bg+1
i=0 j=bzt1
0= 11
where third equality is from Lemma 3.
23

---

Published as a conference paper at ICLR 2025
Following lemma will be used in proof in later proof. Lemma 5. For the iterates {V* 1,=,,1,2... of Rx- VI,
TVK vo Σ
>yyg"* - v pm ( (1 (111)P=)((1 hr)),
/=0
TVK vo 2 Σ (1 - 2z)9* + +h* - - + Pt. (T ++ ) - 1²)).
1=
Proof. We have
TV ST
Σ (1- \1)g" +h* + 1 + (1 )=+ 11)) + +
Σ >z)g + pT - X141)P=i)(VO) -h²))
/=1
+ +P* h²* + +g* + +(1 - -F*
Σ (1 - >z)g + p (N + +(1 X1+1)P=) h²)) + h² 1=0
where first inequality is from Lemma 3 and 2, second inequality comes from second Bellman equation, and last equality follows from first Bellman equation.
Also, we have
k E1 (1-21991 + h² + - (1411 +
TVk 2 pr.
)1T1) h²)) + +
k
Σ (1 - >y)g PP. 1 (411)==))(10 - -h²))
1=1
hh* g" + (1 - Ph"
& Σ >,)g p (I (1 (eT1) -h)) h², j-0
where first inequality is from Lemma 3 and 2 and the fact that { are greedy policies, first equality comes from second Bellman equation, and last equality follows from first Bellman equation.
We now prove one of key lemmas for Theorem 8. For that, define
h2 kb, =
Ri for 0 < K2 < ki and Cn,-1 = 1, CR. = 0 for all 0 < k. Note that at = (1 12)) (1- Aÿ) and
a a
c-115-1
j=0
k=
ag = for 0 S j < k. Then, we have following lemma.
Lemma 6. For the iterates [ of Rx-V VI and S hiz E hr.
k kk
Σ (1 x=>= Cki A2 (Stt
S k21 h²),
where Shi,kz :S .2 are stochastic matrices.
24

---

Published as a conference paper at ICLR 2025
Proof. We use induction 22- Let k2 O. Then, Ck,u Ei= of II A, (ag 1) by
Lemma 3. Also, by Lemma 2, we have
& pd -a- Xz)Ø5
V
1=1
h" 0o + 11 (1++1l (1 (11)) h²)
(1 1 - hi)) ) (I 1 ) - (T===-)))))))
(S. 52.0) (VV - -hr)
where Sk: and 0h.0 = (1-II =+11 ( (
+ -
By induction.
Vk2
h
hp
Σ
-
(=k2
j=0
kj
Σ
(TVi-1
-TVi-1)
ks ki (TV Vo)
d ai
k
ki
Σ
Σ
k/ ki
di
(p
i , p 173-1 n: 1)+ Σ
ap
to a (TVi-I Vo)
1
1= k2+1
ki
hy
h
Σ
kg $y
pai (Vi-1 - -V--1 +
Σ
a ki (TVi-1 - v
a
d
b
1=
Σ \1)g ( (S--11-1 - 1 - 1(0)
ai
1-1
Un a
k
Σ (1
\t)g + (p=--1 (Aenl )et1) - 1) (Vo - -1²))
1=
ki
ki
ko ki ai 1.j 1 S10 h²) +
ka ki aj di
E(- >1)g
E (1 (1-1)))
1=
t= + 1=
kb C - shi )2 - h²) + Σ (1 (1-1
where first equality is from Lemma 4, first inequality comes from the fact that {mI)1=0....... are greedy policies, second inequality follows from induction and Lemma 5, last equality is from Lemma 3, and
Si.
(Nt+1 I +11 \4+1)P=1)
j=0, else,
s
{
{
1
j= 0, else,
P S
p S 54-1.8-1
and
sti
k2ikk 2imbx
Ein a
--1
and Sh
kk Ei
Σh
Enz o a -1-1--1
a
To obtain lower bound of Vk - Vks, we need more sophisticated consideration, and following lemma is necessary for later argument.
Lemma 7. Let (V*) )== be the iterates of Rx-VI Let lim sup d < 1. Let F {T P" g" g²}. Then there exist K such that if K < k.
TV
max 7 T V.
REB
25

---

Published as a conference paper at ICLR 2025
Proof. Suppose is infinitely often repeated deterministic policy among { Then there exist increasing sequence kn such that Tkk. = л and Ak. converge to some X < 1. Then, since v = Ara M1 V + Aka+1 +1)T we have
Vk++1
Vha
V
Akn+1 Shat1
+(1
Akn 1
1l+ E (1 (1-Ai)
Di=1
2x)
Ad)
p
+ (1 - Akut1)
i= (1 (1-
If kn 0o, lim sup Aạ implies Ej=1 (1 XU) cc.
Then, by Theorem 7, we have
g =g" + (1 g)P""
Thus 9* = =p g* and this implies π E. By finiteness of action and state space, number of infinitely repeated policy is also finite. Therefore there exist K such that TV* maxxge 7 V for S
We are now ready to prove left key lemma. To obtain proper lower bound of 4 Vkk, roughly speaking, we need consider Vk as initial point where N is iteration number in Lemma 13. For
that, define {X& Jg such that X/2 = > for K + < and NR= = 0. bjj = (11 x() (1 - X3) for
K k. and by 1. Also, define
l
K kg
b
K 1-11--11
j=N i=
for 0 S 122 < k1 and ok K,K- = for all K I k. Note that if 0, X drs 69 = aj. and
k2,82 do for all 0 S ki, j,j,k, k.
Lemma 8. Let (V*) [=*))=0,1122 1.1....... be the iterates of Rx-VI. Suppose there exist K such that if S k TVk maxxer T V where E = =t : p"gg g" g. Then, for K S kg S K,
K X)g* + Cs (St
Sx k h²) - V vkk
1=
where sky.ka, khi are stochastic matrices.
Proof. For K S k, by simple calculation, we have
1-1 V = II = - I (1 P +
K
and
v*
= II
== (N + (1 - M P +
1 k (2 PT 1)+2)r=*
2 _I (X + (1 - ) +
1 (X -xx N1+1)r
k
=II
(2 + (1 - )P=.
k-1
(X I + (1 X )11 + +I -p*))ht)
k
Σ j=
(1 X2)g* + + K - (X/41 + (1 ( -h))
=
26

---

Published as a conference paper at ICLR 2025
where first equality comes from previous equality, first inequality follows the fact that fmt are greedy policies, second equality comes from second Bellman equation, and last equality is from first Bellman equation.
Now, we use induction on 22. If K2 = K, by previous incquality,
kn Σ j=K+1
Vh Vk_
(1 (1-X (1=)))**
h²- vk + 11 k= (N/+11 (1 X=1))==)(( -1))
(11 -1 (N/42 (1 X ) -1 -1)) -- - -1i)
2 (M k=k -1 (N/+1 1 + (1 - 1p=)) - -1 )1 ( ) ) - 1²))
(1 - N - + +(1
k
\=+1)P" (Vo -h²)
( (Stt.
k
Ski K ((V - -h')
where second inequality comes from Lemma 2 and first Bellman equation (note that g" terms cancel out), and
. (1 (1- -IK N++1)* -I I +11 (1- ((1)P=))) (1I k -1++11)
x ( + (1 (1- )
chi, K 11 - (A++1 1 + (1 - \T+))
S2'
K =k.x=1 11 -1 M4r
K.K
By induction,
Vh Vkk
h Σ
b (TVi-l -TV--1
ki
hi +
Σ
Σ
Σ
(TV+i1 VK)
k
Σ
Σ
ya (p + 5
- -- )
-
+ Σ
ba (TVL-I- - vK)
t=bz+1
Σ
bab ks p (vi- ()-l)+ +
b (IVi-l- - (k)
i=
Σ
yes te p
Σ
Xiig* + - 1 (Si-115- - S 5 -11)
k=
Σ
Σ
X)9=* + -p== ( + (11/++111XX1001 Xz1) (1)) - 1) (V - -h²))
k=k
27

---

Published as a conference paper at ICLR 2025
R2
p
Σ 11
Xigg + (5-1--155)111- Sz 1 )(V - 11*)
i= +1 +1==
i-1 (1-x1)9' + (mr 2 7+ (1 - \241)
K
1
1=k
(II K (d++1/ + (1 ) -II - (A + (1 )eta)par)) ) (vo ntt)
D t K 1-1---1 - -/0 11²) +
Σ (1 Xiig*
flj=K
K
K -h k2 (St
-h) - (V= h²)+ Σ (1 Xa)9" /=
where first equality is from similar argument in the proof of Lemma 4, first inequality comes from the are greedy policies, second inequality follows from induction and simlilar
fact that { Kt argument in the proof of Lemma 5, last inequality is from Lemma 2 and first Bellman equation (note that g terms cancel out), second from the last equality is from same argument in the proof of Lemma 3, and
pd II
(4+1 I (1 14T) ( 1 (1 +(11-1111111111111 )(H1) j = K,
E
clse,
II= - (1+11 pm Sz ----1
( + (1 (411)P=)) j= K, else,
5ty
s/ kh = (ok
hoa ks k
-يا S
(k2
Am Rg +
j== K
shi,8a
(ch1,ka)
k2
15- St
1=0
For the explicit convergence rate of Theorem 8, will use the following Fact.
Fact 5. (Cominetti et al., 2014, Section 2.3) For 0 < k and K < SK
2
(1 A1t1) -1 -00+11 5
V m Et Aa1 21) Di
2
(1 (--2441) +1 S
V 1 TK X(1 - X2)
Now, we are ready prove Theorem 8.
Proof of Theorem 8. First, by Lemma 6, we have
T v* -g"
(1 >x+11) -1 - ph. - g"
S (1 - A6t1)) - - -1'++++ Ax+1)g") - g"
(1- - (SK+1
sk ) h²).
28

---

Published as a conference paper at ICLR 2025
Similarly, by Lemma 8, we have
TV - V - g"
(1 Xe+1) -1t1) VV g
2 (1 (1-1 - 1 (S
(S
110 h*). v h"
Thus, this two inequality implies that
|TV vk 1011 -
- X: X;)
by Fact 5 and A X/ for K K+15 k. Finally, by applying the Proposition 6, we conclude proof.
F.3 PROOF OF THEOREM
Let S be set of all deterministic policies and inf (= P*g*=9") ||PT g" g"lloo (note that if S/(T "P"g" = 9²} 9 E 0o). By definition of Bellman optimality operator, there exist deter- ministic policy Th such that. By definition of Bellman optimality operator, there exist deterministic π such that
pi+1 y* + =2
1 pppuv r
for all k. By simple calculation, this is equivalent to
n
k +
2V
2p= V
p
Vk 0
k
vk+1 V0
)
+
Vk
Vo
k
k 2
R+1
2
Let -²
k/2
9r
+
6e. By Theorem 7 with du =
2.
1
we have
vh
Vo
11"
gx
k/2
k/4
and this implies
||vo- h1- 111100
|1Ex|100 5
k/4
Then, we have
Vk
V0
k: +1
|k+11 Vo
Vk 04
a
2
b
k
k+1 2
2
2(k + 1)
pm (g* + +EN)
(g*
+ Ex+1) + (g" Ex)
k
2
2(k + 1)
Pd g" g" + Px
g
Ek+1 + EK.
k
This implies
P" n 2Vo
2P= V
2 T
2(k + 1)
p" Ex +
k Ex+11 Ej.
k
Then, if we take
11 in both sides of previous equality,
1 (2 |||r + | ~0 16
||elloc - ko
1 h" 11 +11l9"1112)
Thus, if l 2 (2 11 +4 | | 16 | 1--0-1 ha 11 +2 11x)) - p = g".
Thus, if we set K = (2 [rll + 4 ||||| + 16 h" 1 2lll cl, K satisfied condi-
tions of Theorem Therefore, by Theorem 8 with A = =1/2 for all we obtain desired rate of Bellman and policy errors.
29

---

Published as a conference paper at ICLR 2025
G OMITTED PROOFS OF SECTION 4 AND C
In this section, we present omitted proofs convergence theorems Anc- VI. We prove Theorem 9, 10, and 2 in turn.
G.1
PROOF OF THROREM 9
Define Å = 1 as coefficient of Anc-VI for computational conciseness.
First, we prove the following lemma by induction.
Lemma 9. For the iterates )==,,,.... of Anc-VI,
k-1
Σ [1I j= (1 (1-a)) (I pmt) po + Σ (1
j= (1- 1,)) (
p pri) rm
2=0
1=0
Proof. If 0, 1 = VO.
By induction.
pk+1 (1- )b41)TVK + AatiVo VO
(1-A641) prx Σ( (II 1 (1 -5)))d, (Ptl vo
pTi)
k-1
+ (1 - X1)) ( pTi) prz
+ +r + Av+1V vo
1=0
k+1
Σ (1 1= (1- (" vo + Σ
11 11 /=it1 (1 - Az) (1 pr1
i=0
Now, we prove following key lemma.
Lemma 10. For the iterates {V 1k of Anc-VI, VI,
k-1
-1 Az)g* s Σ k=
[II -1 (1-))) (Mi---)Par) (v0- -h²),
k-1
h"
[II
pm.) (vo --) s Vt
Σ (1 - -xylg".
2=
1=0
Proof. For the first inequality, we have
Vk
u -1 (1 A1))A,, PP*) vo
I1I -1+1+1111 -2)) (witl pri) n
1 (1 - -1)) (IT) (m pat) vo
(TT 1 (1 21)) ( (0" + -
1=0
k-1
A
n
11=1111111 24)ga h"
TT -1 >1)) (Ti= (Vo h²)
where first equality follows from Lemma 9, first inequality comes from second Bellman equation, and second inequality is from first Bellman equation and telescoping-sumg argument.
30

---

Published as a conference paper at ICLR 2025
We now prove second inequality.
k-1
J 1= (1 - -y]) 1 vo +
1
(1 - 22) 1 nm
i=
1= - -1y))a (Ti=-- vo
T -1 -2y) (Ti=k_1 ptt)) (g* (1 pT*)
n - 2z)g* + ht* + Σ
Σ i=0
m -1 (1 2y)1A (II (TT.)- (vo - -h))
=
where first inequality follows from the Lemma 3 and fact that o are greedy policies, first equality comes from second Bellman equation, and second equality is from first Bellman equation.
We now prove Theorem 9.
Proof of Theorem 9. By Lemma 10, we have
k-1
yk 0 Σ
11
-1
(1
1=0
k-1
< (1 - Aa)(1* - VO) + Σ
(II i1 (1 - A1)1A, P (Vo - h²),
1=0
Vk V Σ
11 11:111111 Az)g
i=0
2 A1) - v9) + k-1
> (1 >1))a, (Mi (vo - 11)).
If we take
I| right side of first and second inequality, we have
--1
(1 - Aw)((" VO)
(Mi-e (vo 11*) 1
1=0
2 Ax) \x)|/10 11" 1l,0
(1 Aw -V0) + Σ
k 1-1
- (1 >;))a, (T (M=. (vo _ -1²)
< 2(1 Ax) 11v0 - 11 b0,
and this implies
Vk 0
2(1 \1)
g*
|| h-
k 17 111--p X1)
Σi= IT: [1 -2,)
G.2 PROOF OF THBOREM 10
Following lemma will be used in proof in later proof.
31

---

Published as a conference paper at ICLR 2025
Lemma 11. For the iterates {V 1K=0,1... of Anc- VI,
k+1
141 (1 - -5)1d; (Mi -1) (V) hr)
TV
(1 >z)9** +
1=1
1=0
1++1
TV
m [1 >z)g* +
Σ
[TT
j=++| (1 -1))1 (T.. -1] (1) 11))
Proof. For the first inequality, We have
TVK
spa
Σ m 1=t11
Az)i0 +h- +
Σ ( -1 ^;))Ai (Mi= pmi) (vo - -1²) + t
k < Σ 11 (1- >z)g* +
k:
Σ 1 Az))A PmT) (vo - 1141) -1()
i=1
i=0
+ P + 5" + (T -P"m)hh
k+1
Σ
-1 >5)gg* + Σ Em (1)))A) (Ti) (Vo 11²) + h0," =1
where first inequality is from Lemma 10 and second inequality comes from Bellman equations.
Now, we prove the second inequality.
TV
pd,
Σ II
2g)9* +h + > (1 (1- (TH PF.) (vo- (10-)1)) + -.
k
h
Σ IIk
(1 -Ag)g* + Σ
III m1 - (1-A)))A, (I.) (Vo - -h))
1=0
h"* +g" + (1 - 1P"
4+1
Σ 11
-1 >z)g* +
(1- AY))A, (P.) (vo - h1) h
where first inequality is from Lemma 10 and the fact that Ty is greedy policy and first equality comes from Bellman equations.
We now prove one of key lemmas. Lemma 12. For the iterates {V 122.. An
(1 1 1
k Ao 11= (1 g" + (1- Σ 11 - 13) (St - 55 - -h*)
g6+ (1-
k
V ph- S
i=1
where Sk, Si are stochastic matrices.
Proof. We use induction. If l: = 1,
0 = (1 - x + (1 - \1) - (1 (1- ~1)
$ (1 X1)g" + (1= -1) -ht)
where inequality follows from second Bellman equation.
32

---

Published as a conference paper at ICLR 2025
By induction,
vh+1_ yk
-b++1 V0 +11 Au ITV* - Av - (1- An)TV/-1
(AR *R+I) - V4) + (1 -c) - -V
SAAx- *R+I)(TVE Vo) (1- Ae))PE (V* - Vh-1)
k+1
S (Ax AR+I)
Σ
n [ ->z)g" + Σ (T) -11 - Az))A, PTi) - 1 (vo (v0-h²) 1r)
i=1
t |
+ - -Ax)PTH
Σ
Ae 1ell (1- Az) (1-)s) g
i=1
1
x j=i (1 - -2y)
(S - (((1=~1") -h²))
k
k+1
d
I -1 (1 -11)
9¹
Σ N >z)9
i=1
i=1
h
+
1 A
A (111 -1p) + + (Ax - Ac+1) Σ
(Ax-Ax+1
(T - Ag)]d; (Ti)
i=1
1=0
1 A
X,11 1= (1 -2y)
5t (10--1)) -11²
i=1
(Ax dl+1)I+
1- Σ π1 (1 gh (VO -10--1))
i=1
k+1 Σ 1=1
k+1
A (1-
g* +
1T (1 -2)) (1-()))))
- -h*)
where first inequality comes from the fact that Th. Th-1 are greedy policies, second inequality follows from induction and Lemma 11, last inequality from the second Bellman equation, and
Sh+1
1
1
k+1
E
A -1 -2)) (1-1)))
(die AK+1) Σ
(T - (1 -A1))a, PTi)
+11-
15=000 - -1112/ paa sit
+ - A
i=1
k+1 11
-1
k Σ 1 - >5)2x/ p sst
Ar 1 (2))
1 A
i=1
i=1
Note that condition of leading coefficients positive.
To obtain lower bound of V v we need more sophisticated consideration, and following lemma is necessary for later argument.
Lemma 13. Let 1 be the iterates of Anc-VI. Let d S AA=11for S l and lim d 0.
Let E = { P"g" = =."). Then there exist K such that if K < k.
TVK
max
T V REE
Proof. Suppose infinitely often repeated deterministic policy among ( 0.12....... Then there
exist increasing sequence kn such that Tk., π. Then, since Vh++1 >t. +1 10 + (1->e. +1, TVV
33

---

Published as a conference paper at ICLR 2025
have
Vk++1
V
V Km
Anx+1
+
A 1
2i=1 IT kn - 22))
Li=1
xix
II in
|=
(1
Xj)
Nn 2i=1
k. j=i (1 )z)
p
+ (1 -mx+t)
g=1 Aÿ)
-i=1
If ki, + xo, lim Ag 0 implies limg- -o E Σi=p -1-))= xo by Lemma 14. Then, by Theorem
7, we have 9" = =p g², and this implies т E E. By finiteness of action and state space, number of infinitely repeated policy is also finite. Therefore there exist K such that TV max 7 Vk for K S k.
Lemma 14. Ifli d = 0, then lo Ex 11 (1 - 2z).
Proof. By condition, for any 6 > O, there exist Ke such that As > e if K S k. Hence, lim inf Ei=o II 2y) 2 1/c 1. This concludes lemma.
The following lemma will be used the proof of key lemma. Lemma 15. Let {V*) 1==12.... be the iterates of Anc- VI. For S K + 1,
Vk pb-1 2
1-
dR- 11 - 21) ST.9"* + (Ak-1 )x) Σ 1 >2)99*
1=1
b
+
X k j=
[1 (1- 21))
(8% - 5g. - -h²),
where Sh. S Sly are stochastic matrices.
Proof. We use induction. = V1 V1 - - TV - h*).
-1 -1 (1- + +(1 +11-11)11111 -1
By induction.
vk+1 4b
(Ax XEV - Vo)
(1- AE)PEF 1(V vk-1)
k+1
2 (Ax AR+1)
Σ (1 - ~2199" +
Σ (u) (1 (;))Ai (T.) -1 (Vo (vo- 11²))
(11-2
+(1 - pm
Σ
Au 11 -11) 55.9" + (Dx-1 Ax) Σ 11 >z)1g*
i=1
1=1
+1-- 1
MT 23)
(St: S )VV - -h²)
34

---

Published as a conference paper at ICLR 2025
Σ - (1 - 1)) g- - 1- 1-1x du - Σ
k+1
= -Ax AR+1)
AR - )a)) pmu- pmm Styg"*
i=1
+ (Ax-1 2b)
11 2y)Dmk-ig' + (A+ -
)x+1)
(1I -= (1 -A1)]A (1
i=1
==0
1 Ak Σ
A.Ily=1 (11) pp (vo- h())
k
(Au d2+1)l+
1- - Σ 11 -21) p= S/z (Vo -h")
1=1
k+1
21)) {
k+1
(Ax
AR+1)
E1 g-
Σ (1
sggtig gr
i=1
k+1
|
xللل 11) (S "VV h²)
where first inequality comes from the fact that Th: Th-1 are greedy policies, second inequality follows from induction and Lemma 11, and
k+1
stit1
(1-
1
= (1 - -2)) (NNa- - AN+1) -64-))01)
Σ
c1 (1 A1))Ar (LI_
i=1
1=0
+1 -==
-1 - -2)22/ pai--s St
Sh+1
1
k+1
X (1 - -2,) (IN-- (A+E-Aet1)+ A +
1 11- \
Σ u 1111/ px.
&
i=1
k+1
sk+1
1
11 - 23) (1-1a)
(Ai-1- As) Σ -1 (1 >p)
i=1
+ 1
Σ
A 1 (1 (1
(1-1))) 22))
Pmik-s sik
i=1
(Note that 0
Ab+11 2 implies 1 d -/t 11 (1_)))
Now, we prove left key lemma.
Lemma 16. Let {V*) k= be the iterates of Anc- VI. Suppose there exist K such that if K S k. TVk = maX V where E = { p"g = g²}. Then, for K + 1 S k. For the iterates
(V*) |= of Anc-VI,
V* -
k Af 23) g" + 1 Σ (11= 21)) d (5% - st)(vo h*)
1=1
+ - (1)))
(1-2
K+1
dx II f= -Xi) (st - SSt>
1=1
where Sh. Sk. Sky are stochastic matrices.
35

---

Published as a conference paper at ICLR 2025
Proof. We use induction. If = K + 1, by Lemma 15, we have
V yk+1_
Vk
K+1
K+1
1
Σ
xx j= (1 -11)) 5 n² + (Ax AK-1)
Σ n (= - ->))a*
i=1
K-1
(1 (1- 1 (1-11) (5 - -5 - h1)
K+1
k+1
AK+1ll (1 - )1) (1))) g" + 1 Σ مل - 211) - - h²)
K+1
23) (sK - g".
where SK= I.
By induction, for k 2 K +
vk+l= ys
= (Ax - -R+1)( - Vo) + (1 - Xx)(TV* - TV
2 (Ae - -A+I)(TV== - vo) + (1- - Ae)PPF-II(K - 11-1)
Σ (1 (U)= - A5))A: (Mi=aPr.) -1) ) (vo
2 (Ax AR+1)
Σ
(1 1 (1= -As)g" +
(vo- h')
i=1
(1-2
k
+(1 Pxt)
Σ
Ad (1 X1)) g¹
i=1
k
(m (1 - -2y) X;
(S), - -5t) h1))
1=1
K+1
+ m k-1
j= (1- - -11) {
Σ
dx f=s (1 - -a)) (1-)) (SB. - -St)a*
i=1
k+1
2 2Ax \e+1)
Σ
g" (1=
11 11 - >31
(1-de- Σ Xu 1e 11 >z) gr
1- Σ Xx11 (1 21))
K+1
+ +11=-44(1 (1 - A1)
(pri- - - S4:
k
+
(Ax - \et11)
Σ
(TT
(1 - >;))ab Pm.)
==
1- An- Σ n [1 (1 >1)11 pre- ) (vo (VU-h²) 1²))
(Ax - dc+1)(+
1 1->x= -
Σ 11 (1 -2,)da/ 1 (vo -1a)
i=1
k+1
k+1
1641 (1
g" + 1
Σ
111 - -21) (s7 - (/0 -h²)
i=1
(1-
K+1
+ +1 (1 -21)
1 1
Σ
Xx
rT k j=
(1 ->1)
(S/ - >9
1=1
36

---

Published as a conference paper at ICLR 2025
where first inequality comes from the fact that Tk: TT-11 are greedy policies, second inequality follows from Lemma 11 and induction, last equality is from first Bellman equation, and
= -(1 k+1
Adl (1 - m)) (
strt
(Au= Ak+1)
( j- (1 -, (T.)
+ 1 Ak
Σ n n1- -2)bb) pre-ish)
iml
k+1
&
sk+1
A1II 1= (1-1) 23)
(Au - + + [1->x Σ
11 j=
(1 2/)20)
i=1
i=1
sk+1
Sg
p St.
Now, we prove Theorem 10.
Proof of Theorem 10. First, we have
TV
V g"
$ >x(TV* Vo) + (1- -x) -
A+1
k
A -1 -2ygg* + A
Σ
Eu - -x))d Pm!) -1) (vo (vo- -/0-)²) 12) 1=0
i=1
(11-2)
k 1a (1 -11) 9"
+ (1 Ax) pm*
i=1
1=1lf=1 (1 - 21)) -25)
(S) -V -1t) g"
k
b ( م= (1 - (1)))) P + (I->x Σ x - - 2/1) pir st (vo (vo- -
A
k A= Σ
Aal+ +
Pm (vo h²)
1=1
where first inequality comes from the fact that Te: Tk-1 are greedy policies, second inequality follows from induction and Lemma 11 and 12, and last equality is from the second Bellman equation.
Similarly,
TV bb g¹
2 A (TV -V0) + (1- -c))pse- -vR-1) g"
E - (1 (1))a, p -1) (vo - h²)
A
t (1 - >>g)0" Ak
+ (1 >pp (1--
Σ
A x (1 - -23) g"
1=1
1- Σ A11
11 k- (1 (1))
(St. - ( -11²)
(1 2/) 1-
K+1
Σ
A 1l (1 23)) (S$ - -ty )g' 96
1=1
37

---

Published as a conference paper at ICLR 2025
& Σ
A
(11 j= (1 1m + (1- do - Σ
Aلlي 23) pr (vo
(vo- - 11))
1=0
i=1
k
Σ 21l1y -2)) put-igh (vo - -h²)
dpl +
11- d
II - X1)
(1- 1 Σ
(1-I
K+1
(1
p (p S.. ( - )g)) )g¹
where first inequality comes from the fact that mh: Tk-1 are greedy policies, second inequality follows from Lemma 11 and 16, and last equality is from the second Bellman equation.
If we take Il right side of first and second inequality, we have
k Σ
2 1
X .1 (1- ~1) 11v0 -
k
K+1
K j= =1 (1- 13)) |10"
2
1 1- Σ X1 (1 11) |100 101
-111-)))) 11) 1-
Σ
x
i=1
i=
respectively. Therefore, we get
TVV - vh -5-g g- 1000 22 1 - Σ
X.lly - -11) |110 1101000 + +111 - - X,) 11g 1lo
1=1
since -+ (1 12) (1 EK- Ax II (1 (1-)) s I1
K+1
-2)) Finally, by applying the
Proposition 6, we conclude proof.
G.3 PROOF OF THROREM 2
Let S be set of all deterministic policies and | if S/(T P"""" 3²} 0 oc). By definition of Bellman optimality operator, there exist deterministic policy कy such that
PP I01l (note that
vo k+ 1
k+1
p++1
p
b + k 3
1: + 3
k *
for k. By simple calculation, this is equivalent to
k ++1 1 Te
k+1 TM
("=
Vk VO
k ++1
Wk+1
V4
++ k/3 k+3
k
k
k+1
3
3
Let vk_v0
1/3 = =g" ck. By Theorem 9 with d
k+2 we have
V*
0
/2"
g"
<
k/3
k/6
and this implies
||v0- h"
11
11eallo0
k/6
Then, we have
+ 1 PT
Vb - --00
b 1
h: *+3 3
k
1: pa (g* + kk)
+ 1
(g*
+ Ex+11
1 3
k
2
k Ek
k: +
=p g" g"
n g"
+
h: Ek41.
+
3
1:
+
3
38

---

Published as a conference paper at ICLR 2025
This implies
k ++ r
++1
k+1
prkgg - 9" =
k + 3 k/3
+
k +
px g" + kD
k: +
Ek +
k Ek+1
Then, if we take |l in both sides of previous equality.
0 0<es 1
(3 |||l + 12 po - h1¹ 00 + +3110")lb0)
Thus, if 2 (3 |l 12 1o h +3119 E =_1, gp =
Thus, we set K = (3 |11l00 + 12 0o - -1
- K satisfied conditions of Theo-
rem 8. Therefore, by Theorem 8 with d; = 142 for all i, we have desired rate of Bellman and policy errors.
2
H OMITTED PROOFS IN SECTION 5
H.1 PROOF OF THEOREM 3
First, we prove the case 0 for n 2 k + 2. Consider the MDP P,, such that
s= (81, (,,, )n) A {ai}: P(s: 8j. a1) ((,)))(e-11))) r(s,, 01) (i=1}} where {s...... Sn } is closed irreducible set and {sn} is transient set. Thus, given MDP is unichain. Moreover, = P + [1, 0, ..... OJT, and since (PT) (P*)m for 1 S m S 1, Σ
(P (PTy
g" lim
pd = [1/(n .)........................ ................................ 1/(n 1)]T and h" = [(n 1)/(2n 2). (n
32/ 2) 2)..... (n - (2n - 2), (n - 1)/(2n - 2) satisfy modified Bellman equation.
Therefore, | hr 1=1l000 1/2, and under the span condition, we can show following lemma.
Lemma 17. Let T: R + R be defined as before. Then, under span condition, (V'), for osisk k. + S n.
Proof. We use induction. Case 0 is obvious. By induction, (v'), 0 for 0 S 4-1 0 for 0 s 1 i - 1, + 2 S S and this implics that
I S s Then (TV'), j 1 1, S n. Therefore, (V'), = 0 for + 1 < j S n. n (TV' - v²), 0 for 0 < l < -
Thus, under the span condition, for k. we get
TV--v's V = (1 (V*),, (Vi) (V' (,.,, (00))..,,((()))_ (V") -V*),, (V') 0 0,...,0
カ-ं-1
and this implies that
(TV'- v*) +... (TV'- V'n, 1.
Then
(TV'- - -V'):
1=1
for 0 sis k.
E
0 = 1. we have
n >
Σ 04
TV V-), (1)
and taking the absolute value on both sides.
Σ
Σ a:
(TV V 21
1=1 ==0
39

---

Published as a conference paper at ICLR 2025
Since (TV* - -V for k 2 S I, we have
&
(I: + 1) max ISTSR
Σ
aTVi (TV' Vi)1 21.
Therefore, this implies
Σ a (TVi Vi) 1=0
++1
Since g" [1/(n - 1), 1/(n 1),.....
..... 1/(n 1)]. conclude
Σ a -vi) g"
max
k+1 n 1 n
|10 1h
k
Now, we show that for any initial point 0 E RR. there exists an MDP which exhibits same lower bound with the case 0 Denote by MDP(0) and To the worst-case MDP and Bellman optimality operator constructed for V O. Define MDP(V") A, for V of 0 as
S = (81,.... }n), A= (a1): P(s: (1, = (0,0=(0---)),,)))
r(s,, a1) (Vo p= + (i=1))
Then, Bellman optimality operator 7 satisfies
TV = To(V Vo) + Vo.
Let g* be average reward of To and h solution of optimlaity equation. Then, since limp-soo Ei P*) 0, 9" ğ" is average reward of T and h- v h is also solution of Bellman equation. Furthermore, (V') satisfies span condition
V E 10 + span (TV - v "V v1 TVi-1 1i----v-1- vi-1),
i= 1= k
Vi Vi - yo is sequence satisfying
V E 0o +span 8o - i",To - vi,.., Tapi-1 vi-1),
i 1.....,,
which is the same span condition in Theorem 4 with respect To. This is because
TV V To(v - r²) - (V' vo) = TV V
for i = O,..., This implies that
k. Thus, ( Ti=o is sequence starting from 0 and satisfy the span condition for To-
k
Σ 1=0
as (TV' - V 11
Σ
(TVi
a:
1²* -Vo)
1=0
100 ht
1: +
1 h" 11
Hence, MDP(V") is indeed our desired worst-case instance.
H.2 PROOF OF THEOREM 4
We now present the proof of Theorem 4.
40

---

Published as a conference paper at ICLR 2025
Proof of Theorem 4. First, we prove the case 0 0 for 2 k +.3. Consider the MDP (S,),P,r) such that
(81...., Sn A {ar}. P(s: 53, = [ r(s;,a1) 1 (i=2,in))
where {s1}, {8n] are closed irreducible sets and { $n-1] is transient set. Thus, given MDP is multichain. Morevoer, T' P + [0, O, ... 1 and since (p*) TT = (p*) for m Z k+ O" 1om Dimg(P p [0..... 0, 1 and h 1/2, 0)
which satisfy Bellman equation. Thus, ||v hill 1/2. Under the span condition, we can show following lemma.
Lemma 18. Let T: R2 + IR be defined as before. Then, under span condition, (V'); 0.for osisk. and (V*), for 0 s < k and < j n-
Proof. We use induction. Case i is obvious. By induction, (V"), - for <lsi-1 Then (TV'), = for 0 S / S i - 1. This implies that (IV' V²), = 0 for 0 s sisi 1 1. Hence
11
(V*), 0. Again, by induction, (V*), 0 for l 1 -,,1-, 2 n- Then (TV'), 1 and this implies that (TV) - v2), 0 for 0 < 1,
for 0 < < ; 1, 3 S S
1+3 < n 1. Therefore, (V*), 0 for -
Thus, under the span condition, for 0 v i < k we get
TV - v (0.1- (v - (vi) ..... (V'), - -(V') s41 (V:) 0......1).
n- 3
and this implies that
(TV' - Vi - g¹)1 +... (TV* - Vi - -g')n
where 9" en. Then,
04 (TV' - V²- )²)); = a,
for 0 Sis k. If E = 1, we have
V =1
a:
and taking the absolute value on both sides.
k
Σ
a (TVi -v -ii- 9*)| 21.
Since (TV) - -V- 18- ---);); for = 1 and & we have
- - -0)) 21.
(k+1) 1) max Is
(TV' V*) -t)
Therefore, we conclude
k: Σ
(TV' Vo -T)
g"
2
04 h"
k +1
2=0
With same argument proof of Theorem we can extend this result arbitrary Vo,
41

---

Published as a conference paper at ICLR 2025
1 OMITTED PROOFS IN SECTION 6 AND D
I.1 PROOF OF THEOREM 11
Consider Rx-VI and v = ht_ Let ) be the iterates of Rx-VI. Then, since T(u + cl) cl + T(e) for arbitrary E R" and R, Vk h c for some ck E R. This implies
TV₁ - Vv= = The- - hig and by Corollary 4, we have
2 21118 - h- 11e
l - g 110 - |TT 11th - l0 S
V Σイ de X.)
Now, consider following iteration
V
>
+ V A (TV 9¹)
g
9
9
for 1 < k where g" is average reward of T and Vi0 h Then, 11 - h- 11.0 1 |||v-11 - -h111
00
for 1 S ls where ht is solution of Bellman equation. This is because
1| - 1111 = [V lt*) + (1 Au (TV
(T g" - -k*)
9
Ax || [ h 00 + (1 -1-a0 Ax)
TVk -9" hh" 11
S A || g - - 1l
+ (1 As) V h²
1 - h"1 11
where second inequality is from the fact that h* is fixed point of nonexpansive operator T(-) + g". This implies that V is bounded. Then, there exist convergent subsequence Vi"" which converges to some Vi E Rd. Since is uniform constant vector, using previous argument and Theorem 8, we have 1 - 1= by condition of A This implies that Vg is solution of Bellman equation, and since ||V Vollac S $IVV*= -Val-
g
[TV 5 v - -9" S \(=
2
Voll we have Vk 9 + Vg.
By previous argument, there exist C₁ E R such that V2 = h + cc for 0 S hs where cu = 0. Also, we have
V 11* = >\a(V -Nu(V=---1 + (1 Av) g - Th - + 1(h+-1)1)
= =AACK-11 + -11xx)(c--11- - - f(h
= -AACH-11= + (1 (1=)))((V,>-111111- g).
where last equality comes from the property of f. This implies O₁ = AKCK-I + (1
(I-)x)((VV+))
9) Dا A1)(1 (V - 9) where 9" ğ1. We now prove e + f(V,) g. Since f is a continuous function and Vk + Vg [[(V) 9l S M for some 0 < M, and there exist K such that (Vg) g (f(V)) 9)ق for any 0 and all K < k. For K + k. we have
(S(V)) - 9 -ccl = A.) (f(V)) - Øl +
AN - x1) (F(K)) 9- ( 9))
< (mL (f(Vg) - Ø1 + Σ
( (F(Vg) - 9 - (((1g--))
j= K+1
K
+ 1 - 21) [SVV)) 9 -
< (T) M +ct
Σ m m 11)1 21) 2M.
Thus, as k- + x., c + f(Vy) - 9 if lim sup X < 1. This implies h² converges to h" solution of
Bellman equations, and have h²' =Th" f(h)1. By uniqueness of g", -(h)) = g
42

---

Published as a conference paper at ICLR 2025
1.2 PROOF OF THEOREM 5
If A; 1/2 for all i, it satisfies condition of Theorem 11. Then, by Theorem 11 with X; = 1/2, we get the desired result.
1.3 PROOF THEBOREM 12
Consider Ane- VI and 0 = n² Let {
1,,,,, be the iterates of Anc-VI. Then, since T(v cl) = cl + T(v) for arbitrary E IR" and E R, V* = hett + for some E IR. This implies
TV Vx= = The hgg and by Corollary 5, we have
k
9 - 9m loc 1 Th n² - -90lloc 2
Σ 1=0
(1-A)
11100 h- 10
Consider following iteration
V = \ + +(1 - -TV
for 1 S l where g" is average reward of T and V = h Then, V/ 101l - 1/0 -1*1lx- By induction, we have
V
h2 111
(V9 - h²) (1 {x) - -g" - -h²)
S AR VI l1"
+ (1 (1- |VV "9*
S A V -h" 10 + (1)) 11--1 1-11
V 1lo
where second inequality is from the fact that h" is fixed point of nonexpansive operator of T()) -g" and last inequality comes from induction. This implies that V is bounded.
By previous argument, there exist Cj E R such that Vk 3 = h² + cx1 for S since 9 is uniform constant vector. Also, we have
Vk ht = (1 - (1+)))(TV++> -g" - Th 1(1k
= -11-4)(ck-1 g' f(1h-1111
= =(1- -1- (1=)))(((V+-1))
where last equality comes from the property of f. This implics c₁ (1 (f g*). Since f is continuous function, the boundedness of Va implies the boundedness of e and this also
implies boundedness h
Now for convergence of & use folloiwng fact.
Fact 6 (Classical result, (Schweitzer & Federgruen, 1978, Remark 3)). If MDP is unichain and h is solution of modified Bellman equations, h" + cl for arbitary c IR and some fixed solution of modified Bellman equations h"
Suppose there exist convergent subsequence ht of h. Then, there also exist subsequence K., of A which converges to some h. By the previous convergence result, h must be solution of modified Bellman equation, and by Fact 6, h² + for some constant e E IR and h fixed solution of modified Bellman equation. This implies > (h*
I (l)--1) (1 Aw, -1) -1 - -(hhk-11
Th + f(h")1. Since Th" + 1 is fixed, h converge to where = Th - fh) By uniqueness of g*, f(h")] = g"
1.4 PROOF OF THEOREM 6
If X; 2/(i + 2) for all i, it satisfies condition of Theorem 12. Then, by Theorem 12 with
A 2/(i+ + 2), we get the desired result.
43


Reviews:
[{"review_id": "MFZOVHgUOp", "reviewer": "Reviewer_DZ2n", "summary": "This paper investigates the convergence guarantees of the value iteration algorithm (VI) and some of its variants for average-reward MDPs. The following variants are considered: standard value iteration (Standard VI), Relaxed VI (Rx-VI), Anchored VI (Anc-VI). Further, the corresponding variants of the Relative VI algorithm are considered. The paper presents several results for these methods as well related lower bounds, all of which hold non-asymptotically. The lower bounds include a broad class of VI-type algorithms that satisfy a standard span-condition. Further, one lower bound is derived for the general class of multi-chain MDPs. In terms of upper bounds, it is established that a convergence rate of $O(1/k)$ is optimal as it matches the rate asserted by the lower bounds. They also apply to multi-chain MDPs.", "questions": "See above.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper focuses on value iteration (and some of its variants) in the average-reward setting and presents several new results on their iteration complexities, substantially improving state-of-the-art, to my best knowledge. The presented upper bounds exhibit, in my view, some key strengths: they hold non-asymptotically; they cover multi-chain MDPs, which are quite general; and some of them are provably optimal. Further, the presented lower bounds that hold for a broad class of MDPs (multi-chain ones) are quite interesting. \n\nVI plays a key role in model-based reinforcement learning algorithms, and often appears there as a routine that must be run several times at each policy update. Hence, understanding iteration complexity of VI-style algorithms is important for the RL community.  \n\nThe paper does a great job in discussing and presenting VI (and the variants) in a systematic and precise way as fixed-point iterations. Although such connections are already known, most literature fail to provide precise pointers to relevant results on convergence of fixed-point iterations from communities beyond RL. \n\nThe paper is well-written and well-organized, and the results and algorithmic ideas are presented very clearly. (I report below some typos and other relevant minor comments below.)", "weaknesses": "Comments about Literature\n- \n1- It was a good idea to provide pointer to works on average-reward RL. However, at least two key papers [1,2] appears missing. Further, (Zanette & Brunskill, 2019) must not have been cited as it deals with RL in episodic MDPs, and more importantly, it does not use any type of value iteration. \n\n2- VI plays a key role in many algorithms designed for average-reward RL, beyond the tabular setting. For instance, it is used as a routine in algorithms developed for a wide range of settings including factored MDPs (e.g., [3]), robust MDPs [4], MDPs with reward machines [5], MDPs with options [6], etc. To further highlight the importance of VI, it might be necessary to enrich discussion in this part. I suggest the authors briefly expand the related work to address this. This makes the paper a better fit to the audience of ICLR. \n\n\n\nSome Minor Comments\n- \n1. In Fact 2, you write $\\pi_V$ to seemingly denote the greedy policy w.r.t. a value function $V$. However, it is not formally defined. \n2. In several places (e.g., Theorem 1), you use ‘/’ to denote set exclusion. Shouldn’t it be ‘\\’ or ‘\\setminus’ command in LaTeX? \n3. In line 317: In the second half of this rather long sentence (i.e., starting from “and in tabular setup”), you cite 4 papers, covering both discounted and undiscounted. But it is not fully clear that ‘respectively’ in the end maps which paper to which category.  \n4. That you wrote 3.14 in lieu of the number $\\pi$ to avoid overloading notation sounds rather strange. A fix could be to use text mode to write the number $\\pi$.  \n5. In line 456, did you mean Theorem 4 in the sentence “… improves the lower bound by constant factor of 2.”?\n6. Line 394: Definition of “span” is missing. \n\n\nSome Typos\n-\n- l. 188: There exist line ==> … exists a line  \n- l. 211: an near-optimal ==> a near-optimal\n- l. 218: … of the Appendix ==> of Appendix OR of the appendix  ---- In some places (e.g., l. 280) you correctly used the latter form)\n- l. 221: Table A.5 and A.6 ==> Tables A.5 and A.6  ---- It appeared elsewhere, e.g., l. 218, 370,…  \n- Corollary 2: a a general ==> remove extra ‘a’\n- l. 306: … MDPs satisfies ==> … satisfy\n- Theorem 4: such that such that ==> such that\n\n\nReferences\n- \n[1] Jaksch, Thomas, Ronald Ortner, and Peter Auer. \"Near-optimal Regret Bounds for Reinforcement Learning.\" Journal of Machine Learning Research 11 (2010): 1563-1600.\n\n[2] Burnetas, Apostolos N., and Michael N. Katehakis. \"Optimal adaptive policies for Markov decision processes.\" Mathematics of Operations Research 22.1 (1997): 222-255.\n\n[3] Rosenberg, Aviv, and Yishay Mansour. \"Oracle-efficient regret minimization in factored mdps with unknown structure.\" Advances in Neural Information Processing Systems 34 (2021): 11148-11159.\n\n[4] Kumar, Navdeep, et al. \"Efficient Value Iteration for s-rectangular Robust Markov Decision Processes.\" Forty-first International Conference on Machine Learning.\n\n[5] Bourel, Hippolyte, et al. \"Exploration in reward machines with low regret.\" International Conference on Artificial Intelligence and Statistics, 2023.\n\n[6] Fruit, Ronan, et al. \"Regret minimization in mdps with options without prior knowledge.\" Advances in Neural Information Processing Systems 30 (2017).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ketRddYFeB", "reviewer": "Reviewer_M4JL", "summary": "This paper analyzes value iteration methods for average-reward MDPs, focusing on the case of general/multichain MDPs. The algorithms studied are based off of Halpern and Kransnosel’skii-Mann iterations, as well as relative versions (which prevent divergence of iterates). New nonasymptotic upper bounds are established for the multichain setting, and lower bounds are also provided.", "questions": "Are there any interesting technical novelties within the analysis of algorithms for multichain MDPs? Because value iteration is such a widely used algorithmic template in RL, I think it is easier to overlook the seemingly lower level of technical novelty of the paper if there are any simple but novel insights which might be applicable more broadly.\n\n(Related) How does the analysis differ from standard analyses for KM/Halpern iterations?\n\nDo you think it is possible to improve the Bellman error rate for general MDPs to match the lower bound? What are some challenges in doing so?\n\nWhat is the normalized iterate performance measure useful for?\n\nIs there a reason why it seems to be easier to get good performance for the normalized iterate performance measure rather than the Bellman error? (In the sense that standard VI works well.)\n\nTypos:\nThe tables in Appendix A say \"muAlti MDP\"", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Since multichain MDPs are the most general setting and yet they have received relatively little attention compared to weakly-communicating settings, I think the nonasymptotic results on multichain MDPs are of good significance. \n\nIt is nice to have lower bounds, and I think it is interesting that the standard VI is optimal in terms of the normalized iterates.\n\nThe paper is thorough in its presentation of related work, which I think will benefit the community.", "weaknesses": "It doesn't seem like there is a large amount of technical novelty/insight used to establish the upper bounds for multichain MDPs. I think the paper would be stronger if the authors could discuss any interesting technical novelties. It would also be nice if the main body of the paper could include some proof ideas.\n\nRelated to the above point, the proofs are not very easy to follow and could benefit from some discussion about the steps beyond just the statements of the lemmas. In particular, it would be nice for there to be discussion particularly about how the analysis differs from standard analyses for KM/Halpern iterations.\n\nThe upper bounds for general MDPs do not match the lower bounds. This is another area which would benefit from some more technical discussion in the main body of the paper.\n\nIt seems unclear what the normalized iterate performance measure is actually useful for/why should we care about it (contrasting the Bellman error, which at least under some conditions is related to actual policy performance)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tPGKyWXOlD", "reviewer": "Reviewer_Wd6w", "summary": "The paper investigates non-asymptotic convergence rates for value iteration algorithms in average-reward Markov decision processes (MDPs). The analysis convergence rates of O(1/k) for Anchored Value Iteration and O(1/sqrt(k)) for Relaxed Value Iteration under specific conditions, leading to a better understanding of these algorithms in multichain settings. Additionally, they establish matching lower bounds that indicate the optimality of their results for weakly communicating and unichain MDPs. While the theoretical contributions are notable, the paper could benefit from clearer explanations and empirical validation to support the theoretical findings.", "questions": "In addition to the mentioned weaknesses, I request authors to provide further clarifications on the following points :\n\n1. How sensitive are the convergence rates of Relaxed Value Iteration (Rx-VI) and Anchored Value Iteration (Anc-VI) to the choice of the relaxation parameter ? Are there optimal choices that might specifically apply for different MDP classes?\n\n2. The presented results show improved convergence rates for Anc-VI compared to Rx-VI. Are there scenarios where Rx-VI might be preferable, or is Anc-VI generally superior?\n\n3. The paper establishes optimal complexity for standard VI and Anc-VI in certain MDP classes. Are there other value iteration variants or MDP classes not covered in this work? If so, it might be worth having a discussion on whether similar optimality is anticipated for those settings.\n\n4. Are results presented applicable only for stationary MDPs ? It will be worth investigating how resilient these bounds are when the MDP is non-stationary i.e., unknown drifts/distribution shifts occur across time.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper provides a detailed analysis of non-asymptotic convergence rates for value iteration in average-reward MDPs, addressing a gap in existing literature.\n\n2. It establishes both upper and lower bounds for convergence rates, contributing to a clearer understanding of the performance of value iteration algorithms.\n\n3. The theoretical results are presented with comprehensive proofs, demonstrating rigorous mathematical foundations.\n\n4. The work includes novel findings on the complexity lower bounds for average-reward MDPs, which may inform future research directions in this area.", "weaknesses": "1. The paper lacks empirical validation of its theoretical results, making it difficult to assess the practical applicability of the proposed methods in real-world scenarios. Additionally, there is a limited discussion on how these theoretical findings might translate into practical implementations or inform algorithm design.\n\n2. The presentation is highly technical and may pose challenges for ML community researchers who are not deeply familiar with the underlying mathematical concepts, potentially limiting the accessibility of the research and further algorithm design. The authors should consider enhancing the understanding by providing more intuitive explanations, intermediate remarks and some visual/diagrammatic aids to complement their analysis.\n\n3. There is no discussion of the computational complexity or scalability, nor any exploration of sensitivity analyses for key parameters. This omission raises questions about how well the characterized bounds hold for larger or more complex MDP settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dDDc06Pqv2", "reviewer": "Reviewer_uKP2", "summary": "This paper consider the problem of learning average reward MDPs given the underlying dynamics. The major contribution is to  propose a simple but efficient iteration method (Anchored Value Iteration)  to learn a near-optimal policy. In comparison, the naive Bellman iteration method could only approximate the optimal value function, instead of a near optimal policy.", "questions": "Please see the comments above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Overall I appreciate the technical effort to improve the order of $k$ by designing a proper learning rate sequence $\\\\{\\lambda_k\\\\}_{k\\geq 1}$.", "weaknesses": "The major concern is about the significance of the result. The condition number $\\epsilon$ might be a problem in the worst case. In particular, I do not understand how  a $\\delta-$sub-optimal state-action pair ($\\delta\\to 0$) forces a larger iteration number. Is there any lower bounds related to the condition number $\\epsilon$?  I also wonder whether  the same problem exists in the case of discounted MDP.\n\nAnother concern is about the motivation. This work assumes access to the Bellman operator oracle, which is relatively strong in related fields. \n\nMinor point: Line 1556 and possible other places: the index in $\\Pi$ should be $\\Pi_{\\ell=i}^{k-1}$, not $\\Pi_{\\ell=k-1}^{i}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)