Faster Fixed-Point Methods for Multichain MDPs
Authors: Matthew Zurek
Yudong Chen
Venue: NeurIPS 2025 poster ()
Keywords: Markov decision processes
value iteration
fixed-point methods
Halpern iteration
average-reward RL
Primary area: reinforcement_learning

Abstract: We study value-iteration (VI) algorithms for solving general (a.k.a. multichain) Markov decision processes (MDPs) under the average-reward criterion, a fundamental but theoretically challenging setting. Beyond the difficulties inherent to all average-reward problems posed by the lack of contractivity and non-uniqueness of solutions to the Bellman operator, in the multichain setting an optimal policy must solve the navigation subproblem of steering towards the best connected component, in addition to optimizing long-run performance within each component. We develop algorithms which better solve this navigational subproblem in order to achieve faster convergence for multichain MDPs, obtaining improved rates of convergence and sharper measures of complexity relative to prior work. Many key components of our results are of potential independent interest, including novel connections between average-reward and discounted problems, optimal fixed-point methods for discounted VI which extend to general Banach spaces, new sublinear convergence rates for the discounted value error, and refined suboptimality decompositions for multichain MDPs. Overall our results yield faster convergence rates for discounted and average-reward problems and expand the theoretical foundations of VI approaches.

Faster Fixed-Point Methods for Multichain MDPs
Matthew Zurek Department of Computer Sciences University of Wisconsin-Madison matthew.c wwrekwwisc..e..me
Yudong Chen Department of Computer Sciences University of Wisconsin yudongchen@cs. wisc edu
Abstract
We study value-iteration (VI) algorithms for solving general (a.k.a. multichain) Markov decision processes (MDPs) under the average-reward criterion, funda- mental but theoretically challenging setting. Beyond the difficulties inherent to all average-reward problems posed by the lack of contractivity and non-uniqueness of solutions to the Bellman operator, in the multichain setting an optimal policy must solve the navigation subproblem of steering towards the best connected com- ponent, in addition to optimizing long-run performance within each component. We develop algorithms which better solve this navigational subproblem in order to achieve faster convergence for multichain MDPs, obtaining improved rates of convergence and sharper measures of complexity relative to prior work. Many key components of our results are of potential independent interest, including novel connections between average-reward and discounted problems, optimal fixed-point methods for discounted VI which extend to general Banach spaces, new sublinear convergence rates for the discounted value error, and refined suboptimality decom- positions for multichain MDPs. Overall our results yield faster convergence rates for discounted and average-reward problems and expand the theoretical foundations of VI approaches.
Introduction
Markov decision processes (MDPs) the canonical framework for modeling sequential decision- making problems, and sit at the core of reinforcement learning (RL), operations research, and control theory. Planning algorithms for solving MDPs therefore play fundamental role in several fields. Among planning techniques for MDPs, value-iteration (VI) style methods, which are based upon solving the Bellman equation, are among the simplest and most fundamental, and also serve as key primitives within or templates for countless modern RL algorithms.
In this paper study MDPs with the everage-reward criterion, where the objective is to optimize unn-run/steady-stat performance. Despite its foundational importance for infinite-horizon problems, the average-reward setting is less well understood from theoretical perspective due its complexity. Compared to the discounted setting, where the Bellman operator strongly contractive, the average- reward Bellman operator merely nonexpansive and has non-unique solutions. In particular we focus on the unrestricted setting of general (a.k.a. multichain) MDPs, which poses particular analytical challenges, due in part to the facts that all optimal policies may induce multiple recurrent classes and so the optimal werage-reward may depend on the initial state, and that multiple Bellman/optimality equations with different behaviors are needed. relative to communicating MDPs (where all states are accessible from one another via some sequence of actions), multichain MDPs may feature multiple inescapable regions of states that differ in the maximum performance achievable within said regions, and algorithms for solving multichain MDPs must solve the "naviagtion/rransien"" subproblem of reaching the best possible such region, in addition to the "recurrent" subproblem of optimizing long-run performance within a region.
more intuitive terms, one key challenge that
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Some recent work has obtained nonasymptotic convergence guarantees for VI methods in multichain average-rewand MDPs, addressing some of these complexities by making connections to the dis- counted setting employing Halpern iteration, a fixed-point method with nonasymptotic convergence properties even for nonexpansive operators. However, past work fails to adequately capture and adapt to the difficulty of the navigation subproblem: previous algorithms have performance bounds which degrade with excessively large complexity parameters, which are large even for casier communicating MDPs or only measure the time needed to solve the navigation problem exactly and yield vacuous guarantees before this point. Overall, algorithms from prior work fail to achieve optimal performance for general reward MDPs.
In this paper we address these issues, developing faster algorithms terms of sharper measures of the complexity of multichain MDPs. To achieve this main goal. we develop many intermediate results of independent interest. These include new relationships between average-reward and discounted RI. objectives, optimal algorithms for discounted value iteration (and general fixed-point problems in Banach spaces), algorithms with new sublinear ((1/n) rates for reducing the discounted value error, and new suboptimality formulas for multichain MDPs which highlight the roles of both Bellman optimality equations. Beyond our algorithmic improvements, this collection of results advances the theoretical foundations of VI methods and multichain MDPs.
1.1 Problem setup
A Markov decision process is tuple (S, A. where S, A denote the state and action spaces, respectively, which are assumed to finite, P: S x A- + (SS) is the transition kernel where (SS) denotes the probability simplex over S, and Markovian) policy is a mapping क S + A(A), and we let II denote the set of all such policies. A deterministic policy has T(s) with all probability mass one action for all S, in which case we also treat æ as a mapping S + AA and we denote the set of all deterministic policies by ITMD. For any initial state so S and any policy n, we let E% denote the expectation with respect to the induced distribution over trajectories (so, Ao, S1, .I....) where At (S,)) and Se+1 ~ P(- St, At). Let R2 = r(S,, At). Fixing some 7 E [o, 1). the discounted value function V,J E RSS of a policy is V (s) E, - ' R.). Define the optimal value function V -SP V (where the supremum taken elementwise). The gain pT [0, 1]s of policy π is p5 = 4 E 2
[0. [0.1] is the reward function. A (randomized
T- Rt]. The optimal gain p" E: |0, 1|sh is defined as p" SUPTTINMM p* The bias function hTd E R of policy क is (s) = C-limy-+ E, ET (R. pm (S.))l, where C-lim denotes the Cesaro limit. A policy x is Blackwell-opting for all 7 2 7 we have V = Vi: at least one such policy always exists and we denote it .² Any policy induces Markov chain over S, and we let Pz denote its transition matrix. We let Hr. denote the Drazin inverse of - Pa- We collect some of its properties in Appendix [add also refer to Puterman 1994 Appendix AJ. The suboptimality of π is ||p" p" Ile An MDP communicating il for any pair s, E S, 8 is accessible from s, meaning there exists some π and some k 2 1 such that E = 8') 0. An MDP is weakly communicating if it consists of set of states S, such that s' is accessible from 8 for all s. s' E Se,, and set of states S, = S \ Se which are transient under all policies. An MDP is general (which we use interchangeably with multichain) if there are no restrictions. We refer to [Puterman, 1994] Chapter 8.3] for more on MDP classifications. In weakly communicating MDPs p² is equal across all states (a constant vector).
if there exists some
such that
X - X where X is a Banach space with norm ||-I|, we say that L is a-Lipschitz if for all x, E X, [[(x))]((([))])(( L(x')l < a ||æ 2'|l. L is (a-)contractive if a < 1, and is nonexpansive if = 1, For an initial point xo E X, Picard iteration generates the sequence (z+) by I++1 = L(xz), and Halpern iteration generates the sequence T++1 (1 8441)20 + ((x) for some sequence (f.) where each 3, [0. 1).
Fixed-point methods For a general operator
Bellman operators For any policy π the policy projection matrix M is an S-by-(S A) matrix such that for any Q E RSxA and E S, (M*Q)(s) = Σ9EA T(a s)Q(s, a). The maximization operator M. S + R has (MQ = maxag a). We often treat P as (S x A)- by-S matrix with Peo.s' = P(s' s,a), and with this definition we have P. = M=P. For any V E R and any 7 E J0, 1). the r-discounted Bellman operator T, : RS + R is defined as (V()= M(r + vPV). The average-reward Bellman operator is T == Ti that is, T(V)

---

M(r + PV). For a vector V E R the discounted and average-reward fixed- -xintpoint errors (a.k.a. Bellman errors) are [VT & and [V] V -''l respectively, and the discounted value Fora policy n, the discounted and average-reward Bellman evaluation operators + + and T (V) = M + PV), respectively. Ty, T7 are --contractive, and T, T are nonexpansive, all with respect to |1-1| V is the unique fixed-point of T-.
error is V Vill
are T,5 (V) =
Bellman equations
Let p, E SR.. The (standarr/uummodifeee)) multichain optimality conditions
are
max Psap = p(s) Vs E,, acA
(1a)
max r(8, a) + Paah = p(.) + V*)
(1b)
oEA::P..P=Pp
The necessity for two optimality equations is unique to the multichain setting, in particular the fact that optimality requires solving both the transienthnviigational subproblem, of steering towards the optimal recurrent class (expressed in equation (a ) as well as the recurrent subproblem of attaining
long-run optimality within each such class. The complications introduced by the restricted maximum of (bb motivate the introduction of the modified multichain optimality conditions
max Psaf p(s) Vs E, aEA
(2a)
max maxr(s. a) + Psn h = p(s) + h(s)
(2b)
aEA
These can be written in vectorized form as M (Pp) p and Thh) = M(++Ph) p h. Solutions
always exist both equations: for any Blackwell-optimal policy ,², (p*, satisfies the unmodified
Bellman equations, and there exists some M > sufficiently large so that (p'.1" + Mp") satisfies
both the modified and unmodified Bellman equations [Puterman 1994
Proposition 9.1.1]. All
solutions (p. h) the unmodified equations [Ta and (Tb) have p p'. However, solution (p. h)
to the modified equations (2a) and (2b) do not necessarily have = p² (see [Bertsekas] 2018
Example 5.1.1). A sufficient condition for p = p² is that there exists single policy ι satisfying both maximums simultaneously, meaning (Pp)
M(Pp) and M + Ph) M(r + Ph)
[Puterman 1994] Theorem 9. 1.2a].. Potentially of independent interest, in Lemma D.I we show
that solution (p, h) of the modified optimality equations admits such simultancously maximizing policy if and only if (p, ft) also satisfies the unmodified optimality equations.
Complexity parameters For any policy π E IIMR we define R" to be the set of states which are recurrent in the Markov chain P. and we Ut = S RR the set of transient states. We define the transient time parameter Bd of policy to be the maximum (over all starting states) expected amount
of time spent by æ in transient states, that is max.0 T,, TRa, where TR- = in (1 2 0 0: S, E R is the hitting time of the set RS We define the bounded transient time parameter of the MDP p to be B max BT [Zurek and Chen 2025b]. We define the minimum gain-optimality gap A min {p- (s) Psap" :p'(s) - Paap" > ~0, E S, a E A) [Lee and Ryu 2024 For t E g we define the span seminorm ||v||sp = max,es v(s) - minges v()).
1.2 Prior work and their limitations
In this subsection we provide detailed description of results from recent work which are directly comparable with our main theorems. However, since the full set of our results intersects with several different areas, we provide more extensive related work in Appendix B including references to VI analyses for multichain MDPs which give only asymptotic guarantees, and more information on Halpern iteration. Here we focus on the two most relevant prior works, which are the first to obtain nonasymptotic guarantees for general average- reward MDPs with VI approaches.
Zurek and Chen 2025b focus on statistical complexity of average-reward RL but develop a reduction from average-reward (gain) suboptimality to discounted suboptimality, which implies the following:
Proposition 1.1. Suppose that n 2 4. Set 7 so that T
Then for the policy से such that 2 2lg
n
T, (V,) (V,) where Vn T (0). we have
3B
1 1p log(n).
100 p- p=1loo $2
n
3

---

See Appendix|E]ie for its proof, which follows easily from Zurek and Chen 2025b]. A key shortcoming that nonzero and potentially very large even in MDPs where p constant, thus failing to adapt to situations when the navigation problem is trivial. Also the rate scales worse than O(1/n).
Lee and Ryu 2024 Theorem 2), based on Halpem iteration, obtains the following guarantees:
Proposition 1.2. Let (p", ,h) be solution to both the modified and unmodified Bellman equa-
tions] There exists an algorithm that, for any input Vo E RRS,, if n > K where K 3|rll 1211V6 (illv--lll. +3110"llx after n iterations produces oulput Vn E B such that
3
8
K n
1100 10 S (1(.)) Vnn -p"llo
1I6o 1l
11o" 1l.0.
where ā satisfies (V,) = T(V.)
Note the ||r|| I|p" 1oc terms are generally (1) for the scaling used in this paper. The leading term involves the quantity K which introduces a dependence on the potentially very large quantity Voo-lll which is essentially the number of iterations required estimate p² accurately enough to perfectly solve the navigation problem. Overall, (for a no-prior-knowledge initialization Vo = 0)
these two results yield incomparable rates O((B + ||/=* sps) loga and O(| ([[] (1+ ) and both seem unable to adequately address the complexity of solving the navigation problem, especially when
the iteration budget is not large enough to solve it perfectly. (Also as we show in Theorem D.4 |//]/o
may be much larger than | slsp and introduce an additional 1/ dependence.)
1.3 Our contributions
Here summarize some of our main contributions. Lemma and Corollary 2.2] relate policy suboptimality to both Bellman equations, and motivate the introduction of a refined complexity measure (3) whose properties we analyze. We identify new conditions that enable us to develop convergent VI methods, for both 7 (Corollary 3.2 and T (Algorithm [ and Theorems 3.4 and 3.5), leading to optimal nonasymptotic rates and dependencies
the refined complexity measure. We develop new average-to-discounned reductions (Lemma (4.)). Theorem 4.2 demonstrates the optimality of Algorithm 2 for general contractive fixed-point problems Banach spaces, leading to improvements for the discounted operator Tr,. Lemma 4.3sshows that the discounted value error VV; Vo can be reduced at a sublinear (1/tt) rate, even when y is close 1, rather than O()"). These are combined to develop an algorithm based on discounted VI for multichain MDPs (Theorem with different and improved convergence properties.
Sensitivity analysis for multichain MDPs
In order to achieve our goal of developing algorithms for multichain MDPs that have the sharpest dependence on the navigation subproblem's 's difficulty and give nonvacuous performance without solving it perfectly, we first analyze how the degree of eиror in approximate solution to the Bellman optimality equations relates to the suboptimality of a policy constructed from this solution.
Lemma 2.1. For any policy π and any IR.5 we have
p" p- Hr,, (Pxp" p²) + P (r. P.h p" h)-
The first and second terms on the right-hand side above are related to the first and second modified Bellman equations (2ap and (2b), respectively. If ||*p** prl 0, which is always the case when p² is constant (such as when is weakly communicating). then the first term vanishes and essentially recover standard result [Puterman] 1994 Theorem 8.5.5). However, in general this demonstrates the importance of satisfying the first Bellman equation (6). The main theorem of Lee and Ryu (2024) for general MDPs only provides a guarantee once the number of iterations is sufficiently large that the output policy π would satisfy PPPpp p² lloc = O, which incurs a dependence on the potentially large parameter 1/A and hides the role of the first Bellman equation.
'The statement of [Lee and Ryu 2024 Theorem 2] only requires h to be a modified Bellman equation solution, but their definition requires the existence of a simultaneously argmaxing policy, which we show in Lemma D.I is equivalent l also satisfying the unmodified equations.

---

Generally the vector (Pap" - has many zero entries for reasons explained shortly, implying some entries of the matrix Hr, (the Drazin inverse of I P+) are irrelevant. (See Lemma FF3 for more on Hp, 's entries.) This directly motivates the definition of our sharp complexity parameter 'dopp
T max E drop
Σ IIPSLAAP < <S)())) t=
SES
This is equivalently the expected--otaa-reeaan value function of policy π for the indicator reward function F(s. = PsPsap" < <p" (s)}. This connection is used in an essential way for certain proofs. In words, T drep measures the maximum (over starting states) amount of time spent by т taking "gain-dropping" actions. We also define Tdrop max+en1m drup (note that T drop could equivalently be defined as the optimal snpected-total-red the maximum amount of time spent taking "gain-dropping" actions by any policy, from any starting state. (By standard results [Puterman 1994] Chapter 7], even allowing history-dependent randomized policies, the maximum is attained by some E II .) We call T drop the gain-dropping time. These parameters are essentially defined in the sharpest way so that following bound holds:
value function for the reward r), which similarly is
Corollary 2.2. For any policy and any vector h E R.S,
llp" -pm-p11la-
p011oo Tmmp 1 + (h) - p01100
While the condition Psap" < <s) in (3) appears very quantitative, it is actually closely related to the MDP's topological structure: such monn-ainn-ressevvee on the "boundary" of some strongly-comnected MDP component in the sense that they have nonzero probability of transitioning to some such that there is no policy which can eventually reach s from s' with probability 1 (since if there were, we would have p² (5') p (s)). Since many state-action pairs cannot be on such a boundary (including all state-action pairs which recurrent under any policy), we must have Peap* = p" (s) for some state-action pairs. (Note we always have p*(ss 2 PsaP".)
state-action pairs (s, a) are necessarily
As shown in Lemma F.I T drop is always finite in finite MDPs. We always have T Tropp S B and Tdrop I A as shown in Lemmas [R5 and F.6] respectively, the latter of these facts due to an interesting Markov-inequa Markov-inequality-lik argument. drop = if p" is constant, whereas B may still be arbitrarily large in this case. We also show examples where Trrop is arbitrarily smaller than 1/A in Theorem D.4
3 Value iteration for multichain average-reward MDPs
3.1 Coupling-based analysis
key requirement for the convergence of Halpern iteration is that the operator must possess some fixed point. This is not the case for average-reward MDPs, where T instead satisfies T(h) h + pa for h satisfying (b)). which implies T has no fixed point (unless p* = 0), but the shifted operator T(x) := Txx)- ) - p" does have a fixed point. The gain p² is generally unknown so we cannot explicitly apply the shifted operator T. However, as has been observed in prior work (e.g. Bravo and Contreras) (2024)), when '²' is multiple of the all-one vector 1 then it commutes with T in the sense that T( +app)) Txx) + app for all a E R (since is a standard fact that T commutes with 1 in this sense). This commutativity property is sufficient for obtaining the same guarantees as if the shift p* were known, since then the unshifted iterates generated with T can be related to the hypothetical sequence of iterates which would have been generated with the appropriately shifted operator T.
We observe this style of coupling argument can be abstracted to general fixed-point problems involving "unshifted" operators without fixed points. In particular we can address the policy evaluation setting, where for some policy π we seek / such that (h) Re h + p², where T is the Bellman consistencylevaluation operator. Suboptimal policies generally have non-constant gain pT, even for MDPs where p" is state-independent (a multiple of 1). such as weakly communicating MDPs. Thus prior arguments (such as those within Bravo and Contreras (2024)) are insufficient analyze Halpern iteration applied to T but since this operator satisties the key commutativity property T (h + app) = T (h) + ap", a coupling-bant based analysis still works.
Lemma 3.1. Fix p, E X and suppose L X X satisfies f(x + ap) L(x)) + ap for all E X and R. Define the shifted operator L: C: X X by D(x) [(x) p. Fix some sequence
5

---

(B:) E ER. Then defining the sequences (mr) and (ye)e=o by yo 20 and
T++1 = (1- -1 Bo+1 20 + Be+1
and Me+1 = (1 -1--a Bs+1)30 + (()r)(
and letting A, - IT Bz. have for all 2 0 that
Tt - yt App.
Combining with an analysis of Halpern iteration specialized to affine operators [Contreras and Cominetti 2022, Theorem 4.6] for improved constant, we obtain the following result for finding fixed points of 7 - pp, the (shifted) Bellman policy evaluation operator.
Corollary 3.2. Fix ho KSS, fix some policy E 11MR and let T be the Bellman con- sistencylevaluation operator for policy Then generating the sequence (ht) by h4+1 = (1 B441)ho -Be+17"(hy where 3r
I. we have for all t that
2
(h+. - h4 p=1
|1 A7 11
This exactly matches the lower bound [Lee and Ryu 2024] Theorem 4], meaning that this rate for the fixed-point error of T - p² unimprovable for any palue-teration-styye method satisfying a
certain natural subspace condition (see Lee and Ryu 2024 for details) ?
3.2 Leveraging restricted commutativity
However, the commutativity property C(x + ap) C(x) + ap used in Lemma 3.1 does not
generally hold for the Bellman optimality operator T in general MDPs. However, 7 satisfies certain restricted commutativity property: for h satisfying both the modified (2b) and unmodified (Tb)
Bellman equations, we have Thh+ap'' Thh)+ + + = h++ (a++1 1)pp for all E R. (See Lemma
D.2) Our next results show that this condition is actually sufficient develop dille-iteration-basss algorithms for solving general MDPs, by using Algorithm
Algorithm 1 Approximately Shifted Halpern Iteration
input: Number of iterations n for each phase, initial point ho
1: Let 22p hg
b gain estimation and warm-start phase
2: for = 0, .....,11 do
3: Tz+1 = (xx,)
4: end for
5: Let = Tn. form gain estimate ò 1 (In - Io), form as :- T
6: for = .,....,.7 do
Halpern iteration phase; begins with Tn
7: Zt+1 = (1 ==+1==0 + B.41 ( where 3r
2+2
8: end for
9: return policy से such that (s) argmax, E E (s) + Pea
Algorithm I has two phases, for total of 2n iterations. First, Picard steps are performed obtain Fn T(a) (ho). and this Fn is used both form gain estimate / (Jn ho) and to initialize the next phase of the algorithm. The second phase of the algorithm is a standard Halpern iteration, but with an approximately shifted operator 7 T formed using the gain estimate. The quality of the gain estimate p is ensured by the following fact
Lemma 3.3. Suppose h satisfies both the modified
2b and unmodified (b)) Bellman equations.
Then for any ba E S and any integer n. 2 0, we have (n) (ho) np* h T S
hllac-
Therefore H,, is close to np" and thus P approaches 0² as n increases. This fact alone sufficient for the success of the second phase of the algorithm in finding point on, with small fixed-point residual
'While the lower bound Lee and Ryu 2024 Theorem stated for the optimality operator -- -pp". the hard instance |A| 1 so this operator is equal T p= for æ being unique possible policy. 'While a similar statement appears [Puterman 1994 Theorem 9.4.1], due to some ambiguity in the à for which it holds, we provide proof and discuss the details Appendix

---

pp" pp 2n aollog. However as shown in Corollary 2.2 finding such 2x, and taking the greedy policy 7 such that T* (zn) T(=a), is insufficient for achieving small suboptimality ||00 p² I| we must also control ||P=p*= p² 1=1 which is related to the navigation subproblem. This is why it is essential to initialize the second phase with zn since dn is closely aligned with rip", it is possible to show that all subsequent iterates remain aligned with np",, and hence म will be chosen in way which approximately maximizes Pxp* (and the elementwise maximum of this quantity over all policies is p²). In summary, the first phase of the above algorithm, and in particular the initialization which is close in direction to np". , is essential to how our algorithm solves the navigation subproblem. These ideas lead to the following theorem.
(2x(2))
Theorem 3.4. Let h be any vector satisfying both the modified (2b) and unmodified (l) equations (with p p²). ). For all n. 2 1, Algorithm with inputs n, ho returns on and a policy To such that
10
3
drop
+
13 +
35
x2
20
1h1 A1100
00
and
13
35
20
(zn)) - p- Zn 1o
|/ho
helloo
(5)
The bound (5) outperforms the fixed-point error convergence rate from [Lee and Ryu 2024 Theorem
2] by factor of O(1 + /, and matches (up to constants) the lower bound of S2[ Tho 11 /n) shown by [Lee and Ryu 2024 Theorem 3] for the fixed-point residual in the weakly communicating setting. Therefore, Theorem 3.4 demonstrates surprising finding that general MDPs no harder than weakly communicating MDPs in terms of fixed-point error, disproving a conjecture in Lee
and Ryu (2024). This result holds for all 2 1, whereas [Lee and Ryu 2024 Theorem 2] only
holds for 2 C C- for some constant C. The bound also obtains an improved rate
A
Theorem 2] achieves a rate of O - ||/e - hilloo) (which is worse since Tdmp < 1/A as shown in Lemma F.6) Furthermore, under a large-n setting similar to that of (Lee and Ryu 2024 Theorem 2], we obtain a refined guarantee for the policy suboptimality without any algorithmic changes:
of O [1op-t1 ||Ag hll for the policy suboptimality, whereas [Lee and Ryu 2024
Theorem 3.5. Let h be any vector satisfying both the modified (2b) and unmodified (Ib) equations (with p )²). For all > AllMg-Mh
Algorithm
1
with inputs n, ho returns a policy ā such that
13
+
/ falloc
Since Theorem 3.5 matches the best-known convergence rate for policy suboptimality in weakly communicating MDPs (e.g. [Lee and Ryu/ 2024 Corollary 2D), this result suggests that general MDPs are also no more difficult than weakly communicating MDPs in terms of policy suboptimality. for a regime of sufficiently large n. We note however that to the best of our knowledge the only existing lower bound [Lee and Ryu 2024 Theorem 3] applies specifically to fixed-point error, and showing a similar lower bound for the policy suboptimality is an interesting open question. Understanding whether there is gap between the optimal convergence rates for policy suboptimality and for fixed- fixed-point error outside of this large-n regime is another open question.
Finally we further discuss the restricted commutativity property. Lemma D.2 shows the property T(h + aap") = /t + (a + 1)p" (for all a E R) holds if and only if h solves both the modified and unmodified Bellman equations. Actually most of the proof can be performed in the abstract setting of a general nonexpansive "unshifted" operator L. where L(x + ap) = x= + (a + 1)p for some p. E X and all a e E (which implies x= is a fixed point of the "shifted" operator C p). See Theorem H.5) which shows that we can find nn with small shifted fixed-point error [[((z)) P z, however, there does not seem be a generic analogue of bounding P|Ppp p* p01ooo.
4 Discounted value iteration
4.1 Discounted reduction
Now we develop algorithms for solving general average-reward MDPs via discounted VI approach. We first develop new reduction lemma, bounding the average-reward suboptimality ||p" - p² al in terms of the discounted fixed-point error [VT) Vlloo and our complexity parameters.
7

---

Lemma 4.1. Suppose for some V E ES that policy is greedy with respect to + pVV that is, (V) (V),), and that 7 2 3. Then, letting satisfy the modified and unmodified Bellman
equations and letting M = min { [1hilaap I|h" 1lap + + Trrop + 11 11sp drop J. we have
11e" 11'1~~"'1
drop 1) ((1-)) (++ 7M) 16
16) - Vllx)
See the slightly more general Lemma J.6] from which Lemma 4.1 follows immediately. Fixing some iteration budget n, Lemma 4.1 suggests that get (11/n) rate, we must set the effective horizon 1/(1 - 7) to be at least order (n)). Next it remains to control the discounted fixed-point error term [VT Vl,,, which is challenging with this large choice of effective horizon.
4.2 Faster fixed-point error convergence
As part of our first step in minimizing the discounted fixed-point error, we develop a result of independent interest: simple algorithm which achieves optimal fixed-point error convergence rate (up to constants) for y < 1 contractive operators in general normed spaces. The algorithm simply deploys standard Halpern iteration for approximately T-y steps, then switches to Picard iteration. While the analysis trivial, the best of our knowledge algorithm obtaining such guarantees was not previously known despite prior work on related problems, and we find it surprising that such a simple algorithm and analysis achieves optimality.
Algorithm 2 Ceappern-Then-Piie
input: Initial point zo, contraction factor y < 1, y-contractive operator L
1: Let E
T- -1
2: for = 0, 0,..., F....,,E.. do
D Halpern iteration for first RJ T-y steps
3:
Tt+1 (1 - BB++ )uo + B(te where
4: end for
5: for F.... do
& switch to Picard iteration after Rd
1-7 steps
6:
T++1 = L(xxt)
7:
end for
Theorem 4.2. Let L: X be cy-oottractivve operator with respect to some norm x² be its fixed point. Letting (Iz)teN be the sequence of iterates generated by Algorithm
and let we have
1 |000
2+1|
t S t> E
E
7
[((x)) -x,1
8e
1000
x=
8(1
1-1-710 e- 11200
Ei
Park and Ryu 2022 show lower bound of (1 (1+
100 - x Il for the fixed-point error (in
Eizo ?
the Hilbert space setting, meaning the lower bound may be improvable for our Banach space setting),
which is matched by Algorithm 2 jup to constant of 8e/(1 +7).
We can immediately apply Algorithm 2 with the discounted Bellman operator T, to minimize the discounted fixed-point error (V) 1oo. With this particular operator, Lee and Ryu (2023) show
a lower bound on the discounted fixed-point enror of class of algorithms), implying the optimality of Algorithm 2 up to a factor of 8c. [ee and Ryu [2033 also presents an algorithm for minimizing the discounted fixed-point error, and while their algorithm achieves a slightly improved constant relative to Theorem 4.2 (with L TT,) for certain
Voo Vi (for certain natural
initializations, their guarantee does not match the Ei 7 V| Vill lower bound up constants for all initializations Vi (including the initializations required in the next subsection), and hence our Algorithm is the first do so. See Appendix B.T for more comparing with Lee and Ryu 2023
4.3 Faster value error convergence
Algorithm 2 alone (applied to T₂) insufficient to obtain the desired bound on the discounted fixed-point error (V)) Vllco: the error bound depends the initial value error ||V; Vo Volloc.

---

and with a generic initialization like Vo- O. this value error can generally be 9(1 7) = (n)
with our large choice of effective horizon. Hence after (nn) iterations Algorithm 2 would only lead to bound like (V) ol I O(n/n) O(1), whereas we desire this term to be ((1/n).
To fix this problem, we show that by using undiscounted value iterations and re-normalization step. we can reduce the value error at a sublinear O(1/t) rate:
Lemma 4.3. Fix E (0, 1). Let h be a solution to both the modified and unmodified Bellman equations. Then for any integer such that 0 < T-m. we have
min |1hllap 1//111111
sp +
Tarop + ||10' 11 Tdrop
1 1 ((117) 1111)))00000
(0)
V
2
t
1 7
Goyal and Grand- Grand-Clément 2023 Theorem 3] show a lower bound that ||V V* 2 بسm for any Vi produced by an algorithm satisfying certain iterate span condition This geometric yf rate is vacuous in situations where y is very close to (including our setting where 7 = 1 1 and hence n R e- = (2(1)). However, the hard instance in their lower bound depends on the iteration count t and has |/ Isp = || Ilsp 2 t (and also Tanop 0). If we instead restrict the complexity of the instancee (as measured by the complexity parameters) as the iteration count increased, their hard instance becomes inadmissible, and we find that a sublinear (l1/t) rate is possible.
In particular, with our choice of effective horizon 1/(1 - 7) n, an initialization which has value error independent of n (but depends on the complexity parameters Lemma (.3). Generally when the iteration budget larger than the effective horizon, we can use this warm-start procedure to reduce the value error rapidly before switching to Algorithm to get an improved guarantee for solving discounted MDPs. This "warm-start" phase bears an interesting similarity to the first phase of Algorithm
n steps to produce
Algorithm 3 Warm-Start Halpern-Theen -hehadd
input: Discount factor 7 number of iterations such that 1 [
1: Let 0, E" = --
2: for t = =O...,, E' 1 do
initialization phase
3: Te+1 =
4: end for
5: Obtain V as the (n F') F')tth th iterate from Algorithm 2 with inputs FE, 7, Ty
6: return V and policy से such that (ss) argmax,e.ooo A (s, a) + + 7P.a
Theorem 4.4. For all n 2 E'
1 Algorithm returns V such that
8e
7 E
M (+) Se &
(1
[T,(V) - VIloo I
M
7
- 7p
where M = min [1V/llsps |1/T"" Ilsp + T Tarop + || hTT h="1 Ilsp T Tropp }. h satisfies the modified and unmodified Bellman equations, and (x) holds if n 2 2F
Algorithm 3 thus uses three phases: E" steps of undiscounted Picard iteration, E steps of discounted Halpern iteration, and then finally discounted Picard iteration. Combining this with our reduction MDPs.
result, Lemma 4.1 leads immediately to our final result on solving multichain average-
Theorem 4.5. Fix an integer n 2 2. Set 7 satisfy the modified and unmodified Bellman equations. Then the output policy से satisfies
and run Algorithm 3 with inputs y, 2n. Let
71 min |1:l1 sp 11
1l + T drop
1T
T
Torop
+
p²
(T (Tdrop + +)
sp
n 1
Goyal and Grand- CClémet 2023 Theorem 3] actually states a weaker result, but as we show in Theorem B. 2 their analysis can be strengthened to obtain the claimed lower bound.

---

Theorem 4.5 only makes use of the first two phases of Algorithm 3 but as we show in Theorem 1.9 the constant in Theorem 4. could be improved by utilizing the third phase to rapidly decrease fixed-point error. One interesting advantage of Theorem 4.5 over Theorem 3.4 that it obtains one guarantee independent |pA|lspp which as we discuss in Appendix D.1 can hide a dependence on A even when Trrop and ||4" l/ the span of a Blackwell optimal policy, are small.
Conclusion and limitations
In this paper we designed faster VI algorithms for solving multichain average-reward MDPs, and along the way developed a collection of results advancing the theoretical foundations of VI methods and multichain MDPs. One limitation of our results is that the Bellman operators may not be exactly computable, and even if they are, it may be preferable to leverage stochastic evaluations to speed up computations; we believe these are promising directions for future work.
Acknowledgments and Disclosure of Funding
Y. Chen and M. Zurek acknowledge support by National Science Foundation grants CCF-2233152 and RM3-2023239.
References
Dimitri P. Bertsekas. Approximate dynamic programming. Number volume in Dynamic pro- gramming and optimal control / Dimitri P. Bertsekas, Massachusetts Institute of Technology. Athena Scientific, Belmont, Massachusetts, fourth edition, updated printing edition, 2018. ISBN 978-1-886529-08.1 978-1-886529-44-1.
Mario Bravo and Juan Pablo Contreras. Stochastic Halpern iteration in normed spaces and applica- tions to reinforcement learning, November 2024. URI.http://arziit hwtg//bb/24000 12338 arXiv:2403.1 12338 [math].
Mario Bravo, Thierry Champion, and Roberto Cominetti. Universal bounds for fixed point itera- tions via optimal transport metrics, April 2022. URL http:://arriivoorrr/a///00... 00300
arXiv:2108.0000 003000 [math].
X. R. Cao. Single Sample Path-Based Optimization of Markov Chains. Journal of Optimization Theory and Applications, 100(3):527-54) 548, March 1999. ISSN 0022-3239. 1573-2878. doi: 10. 1023//A:1022334224488 URL http: /ttt:://ink. http:://iinnn.ssiiiierr..e springer com/10 1:11:///21112222422288
Xi-Ren Cao. A unified approach Markov decision problems and performance sensitivity analysis.
Automatica, 36(5):771-774, May 2000. ISSN 00051098. doi: 10.1011650000--1999999999 URL
elsevier....... ottpa////......///a/a.///o//////
Xi-Ren Cao and Xianping Guo. A unified approach Markov decision problems and performance sensitivity analysis with discounted and average criteria: multichain cases. Automatica, 40(10):
1749-1759, October 2004. ISSN 00051098. doi: 10.10166jautomaaica.004.4 https://linkinghun o 1090000010000440446113333
URL
Grace E. Cho and Carl D. Meyer. Markov chain sensitivity measured by mean first passage times.
Linear Algebra and its Applications, 316(1-3):21-88, September 2000. ISSN 00243795. doi: 10. 1016//500224379559990022222
URL httpt:://iikkngghuut elsevier wwt./etrreee//ppii.....
$00243795590022833
Grace E. Cho and Carl D. Meyer. Comparison perturbation bounds for the stationary distribution of Markov chain. Linear Algebra and its Applications, 335(1-3): September 2001. ISSN 00243795. doi: 10. (1..001//0002447550111100 (00320---
URL httttsss///iikingguuut www.aewwwiiii......iiii.ee..ee.. elsevier
Juan Pablo Contreras and Roberto Cominetti.
Optimal enorr bounds for nonexpansive fixed-
point iterations normed spaces, May 2022. URL www.aawwwwwwggaa///a.ooa/// 10969
arXiv:2108. [math].
10

---

E. V. Denardo and B. L. Fox. Multichain Markov Renewal Programs. SIAM Math.. 16(3): 468 487, May 1968. ISSN 0036- 1399. doi: 10.1137/0116038 URL httpp:://oo...org 1137/0116038
Richard Durrett. Probability: theory and examples. Cambridge series in statistical and probabilistic mathematics. Cambridge University Press, Cambridge, fifth edition edition, 2019. ISBN 978-1- 108-47368-2.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient Bias-Span-Constrainnd Exploration- Exploration-Exlloiittion in Reinforcement Learning, July 2018. URL URK.atttp//arxxiv.rr//aass arXiv: 180.:18000 [cs, stat].
1802. 1802.04020 04020
Vineet Goyal and Julien Grand-Clément. A First-Order Approach to Accelerated Value Iteration. Operations Research, 71(2)517-535, March 2023, ISSN 0030-364X, 1526-5463. doi: 10.
1287/opre.2022.2266 URL
informs
2269
Benjamin Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathematiial
Society, 7366)9957-961 November 1967. ISSN 0002-9904, 1936-881X. URL https://
ottp:////ooooo//oooioooooooo---e http:///ooooooooooooo/oaaaoaaaa/ Publisher: American Mathematical Society.
Ilse C. F. Ipsen and Carl D. Meyer. Uniform Stability of Markov Chains. SIAM Journal on Matrix
Analysis and Applications, 15(4):1061-1074, October 1994. ISSN 0895-4798. doi: 10. 1137/
$089547989223756.. htttps://eppbb siam. /ttp://///0..111///000666//6//30 Publisher: Society for Industrial and Applied Mathematics.
Yujia Jin and Aaron Sidford. Towards Tight Bounds on the Sample Complexity of Average-reward MDPs, June 2021. URL http://arxii http//iiw..rr//////////////
arXiv:2106.07046 [cs, math].
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, Cambridge; New York, NY, 2020. ISBN 978-1-108-57140-1.
Jongmin Lee and Emestt K. Ryu. Accelerating Value Iteration with Anchoring, October 2023. URL http://arxiv. org/ abs. 2305 2305. 16569 1XXi:22305.16599
[cs] version: 2.
Jongmin Lee and Emest K. Ryu. Optimal Non- Aon-Asyyptotic Rates of Value Iteration for Average- Reward Markoy Decision Processes. October 2024. URL httt:tttts/:pereeeti/ www.rrewwwwwwwwweeeeeeeeee net/forum?
id=WuuczPVVWWC
Felix Lieder. On the convergence rate of the Halpern-iteration. Optimization Letters. 15(2):005- 418, March 2021. ISSN 1862-4480. doi: 10. springer com http/articccleeee 10. /000//11190-011 000000020--16500 1111190020000-11----01 Company: Springer Distributor: Springer Institution: Springer Label: Springer Number: 2 Publisher: Springer Berlin Heidelberg.
URL/https- //link
Carl D. Meyer. Sensitivity of Stationary Distribution a Markov Chain. SIAM Jour- nal on Matrix Analysis and Applications, 15(3):715-728, July 1994. ISSN 0895-4798. doi: 10.1137780955479992229000
URL atttps://epoe siam. otg//oi//abaaeoooooooo hati//ab/110 /00 1137/ Publisher: Society for Industrial and Applied Mathematics.
508954798922288000
Carl D. Meyer, Jr. The Condition of Finite Markov Chain and Perturbation Bounds for the Limiting Probabilities. SIAM Journal on Algebraic Discrete Methods, 1(3):233-283, September 1980. ISSN 0196-5212. doi: 10.1137/0601033 URL hnttps://eppe 1137/0601031 Publisher: Society for Industrial and Applied Mathematics.
siam. org/doi/abs/10
Jisun Park and Ernest Ryu. Exact Optimal Accelerated Complexity for Fixed-Poin Iterations. In Proceedings of the 39th International Conference on Machine Learning, pages 17420-17457. PMLR, June 2022. URL 2640-3498.
mlr. watarprressvv1//ppra/// html ISSN:

---

Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programmingg Wiley Series in Probability and Statistics. Wiley, 1 edition, April 1994. ISBN 978-0-771-669977-229977 0-470-31688-7. doi: 10. 1002/998947733 URL httpp:///oallmlllbbrrr.....g... com/
Shoham Sabach and Shimrit Shtemn. A First Order Method for Solving Convex Bi-Level Optimization Problems, February 2017. URL http://arne org/ abs 1102 03999 arXiv:1702.03999 [math].
P. J. Schweitzer and A. Federgruen. The Asymptotic Behavior of Undiscounted Value Iteration in Markov Decision Problems. Mathematics of Operations Research, 2(4):360-381, November 1977. ISSN 0364-765X, 1526-5471. doi: 10. 12.27/moor...4366) URL UtL_https://pubbonnll inf informs.comm www.m.oor//oi///0 w000:.1117mmmmmm /moor 2.6360
Schweitzer and A. Federgruen. The Functional Equations of Undiscounted Markov Renewal Programming. Mathematics of Operations Research, 3(4):308- 321, November 1978. ISSN 0364- 765X. doi: 10. 10.1227/moor.3. 3.3.00. URL htttps:/ppabsonniint Publisher: INFORMS.
informs.... www.orooo.g/ooo////////oo oog//oo///.oooo. 1
moor 3. 308
P. Schweitzer and A. Federgruen. Geometric Convergence of Iteratin in Multichain Markov Decision Problems. Advances in Applied Probability, 11(1):188 217, 1979. ISSN 0001-8678. doi: 10.2307/142677.. Probability Trust.
//t::///wwww www.wjstoo.....oo jstor htgpsttabe////1/277/// Publisher: Applied
Paul J. Schweitzer. Perturbation Theory and Finite Markov Chains, Journal of Applied Probability,
(2):401-413, 1968. ISSN 0021-9002. doi: 10. (0.2307/3212266 Uttttttp:://// h/tp:::///wwww... http://ww..jtrrrooo...o.oo.or..t jstor org/ stable/3212261
Publisher: Applied Probability Trust.
Satinder P. Singh and Richard C. Yee. An Upper Bound on the Loss from Approximate Optimal-
Value Functions. Machine Learming, 16(3):227-23 September 1994. ISSN 1573-0565. doi:
10.1023/A:10222693555999 URL
Jinghan Wang, Mengdi Wang, and Lin F. Yang. Near Samplc-Optimal Reduction-based RanpllobptiinllRdccccttobbebe Policy Learning for Average Reward MDP, December 2022. URL http::/arxivv.rrgabbes 00603, arXiv:2212.0080 [cs].
Matthew Zurek and Yudong Chen. The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis, October 2024a. URLLhttp://arx// abs/ 2410. 2410.07616 arXiv:2410.07616 [es].
Matthew Zurek and Yudong Chen. Span-Based Based Optimal Sample Complexity for Weakly Communi- cating and General Average Reward MDPs, June 2024b.
11477 arXiv:2403. 11477 [es].
Matthew Zurek and Yudong Chen. Span-Agnostic Optimal Sample Complexity and Oracle Inequal- ities for everage-Reward RI., February 2025a. URL http:://axxi...o/// wwwp:/.rgg/////// 220//2502200 1 11238 arXiv:2502.1 1238 [es].
Matthew Zurek and Yudong Chen. Span- Span-Based Optimal Sample Complexity for Weakly Communi- cating and General Average Reward MDPs. Advances in Neural Information Processing Systems, 37:33455-33504, January 2025b. URL lttps::/ ieciiiinnnsneuuriiie neurips cc/paper...pp.pppeee cew..pps..ccppppprfflle....... files/
12

---

A Guide to appendices
In Appendix B we discuss related work in more detail. In Appendix C we introduce more notation used within the proofs. In Appendix D we discuss topics related to the solutions of the modified and unmodified Bellman equations. Appendix contains a proof of Proposition [.] discussed in the introduction. The remaining appendices are mainly devoted to proofs of the results presented in the paper, and largely proceed in the same order. Appendix F contains proofs of the results from Section
2 Appendices G and H prove the results from Subsections 3.1] I. 3.2 Theorem 4.2 is proven in Appendix Other results related to discounted VI are proven in Appendix
B
Related work
Here discuss more related work.
Analysis of value iteration in average-reward MDPs Value iteration methods have been exten- sively studied for average-reward MDPs. We refer to Schweitzer and Federgruen [1977 1979] and the references within, which develop asymptotic convergence guarantees for value iteration in multichain MDPs.
Perturbation analysis for Markov chains Results of a similar nature to our Theorem 2. and Corollary 2.2 have long history and are referred as perturbation theory or sensitivity analysis for Markov chains. Some references Geelude/Schwiizenn [1688, Meyer [9800 1994), Ipsen and Meyer [994], Cho and Meyer (2000. Cho and Meyer [000]] provides a comprehensive comparison of such bounds, all focusing on the case of ergodic Markov chains. Such bounds commonly involve parameters related to the deviation matrix Hp (the Drazin inverse of for Markov chain with
transition matrix P). Also see Cao [999 2000).
Cao and Guo [0044] for similar results focused on
MDPs
Halpern iteration While Halpem iteration has a long history Herm 1967], J. its nonasympootic convergence properties have been the subject of intense recent study [Sabach and Shtern, [017].
Lieder [021] and Park and Ryu [0022 obtain exactly optimal convergence rates in Hilbert spaces, for nonexpansive and contractive operators. [Bravo et al. [022], Contreras and Cominetti [2022) consider the general normed space setting, of greater relevance to MDPs. In the context of Markov decision processes and RL., Bravo and Contreras [2024) develop Q-lcarning algorithm based on Halpern iteration, and Lee and Ryu| [2023] and Lee and Ryu [0044] utilize Halpern iteration for solving discounted and average-reward MDPs, respectively.
Complexity of discounted value iteration Many different approaches have been taken in the literature to try to accelerate convergence of value iteration methods, especially when the discount factor is close 1. /ooya and Grand-Clément 2023) develop faster VI algorithms for solving discounted MDPs using momentum-like techniques, obtaining faster convergence in terms of the value error for reversible MDPs and also proving lower bounds. Lee and Ryu (222) develop an algorithm for solving discounted MDPs with improved convergence properties for the fixed-point error, using variant of Halpern iteration, and also develop lower bounds. There exist many alternative approaches, less closely related to the present work, based on changing the operator from the Bellman operator. See [Puterman 1994 value iteration.
Chapter 6] or [Bertsekas) 2018 Chapter 2] for some of the variants of
reductions Solving average-reward MDPs by approximating them via discounted problems is a very common approach in the RL literature, especially among works studying statistical (sample) complexity. Jin and Sidford (02TT) Wang et al. (2022). Zurek and Chen [2025a] develop such reductions applicable to weakly communicating MDPs or even more restrictive classes of MDPs. Fruit al. [2018). Zurek and Chen [2024a] consider the related approach of perturbing the transition matrix to ensure contractive properties. Zurek and Chen [202bb develop the first such reduction for general MDPs, involving the parameter B. Zurek and Chen (025b) also provides lower bounds on the sample complexity of solving general average-reward MDPs in terms of B. An interesting question whether it could be replaced by the sharper Tarop within their results.
Halpern iteration can be understood regularizing nonexpansive operator make it strongly
13

---

contractive, and decaying the regularization strength. From this perspective, there are conceptual similarities to discounted RL. particularly for problems where y is not intrinsic but rather functions as tuning parameter which trades off long-term performance for computational tractability.
Other related work Schweitzer and Federgruen 1978 study the solutions of the unmodified Bellman equations.
B.1
Comparison of Algorithm to prior work
Here we give more detail on the comparison of Algorithm when applied the discounted Bellman operator Ty, With|Lee Lee and Ryu [2033], who also consider minimizing the discounted fixed-point error and obtain similar guarantees. The algorithm Lee and Ryu 2023] can also be seen as interpolating between Halpern and Picard iterations, but in a more continuous manner (by continuously adjusting stepsizes) rather than the discrete transition employed in Algorithm 2 For certain specialized initializations, [Lee and Ryu 2023, Theorem 2] demonstrates
improved constant relative to that achieved by our Algorithm 2 but the key limitation of (Lee and Ryu 2023] Theorem 2] is that has order-wise worse performance for some general initializations. Specifically, ignoring constant factors, their result for general initializations can be written as
IT, -vllo E. max [1Vo - V2 Vo -==1 }
where they define Vi to be the fixed-point of Bellman anti-optimality operator Ty defined
an an) a) = r(s, a) + min y
Σ P(s') s,a)Q(6(,o) s'ES
aE
(see Lee and Ryu 2023 Section 4] for how their [Lee and Ryu 2023 Theorem 2] can be written in terms of = up to constant factors). Tyaanii replaces the max in the usual discounted operator with min, and as we now show, this can lead its fixed point V being very far from VV the fixed point of Ty. Consider the following one state, two action MDP:
1,,(1,1) +1
2, r1, +0
Figure 1: A one-state, two-action MDP where V and V are far apart. The two actions are denoted by straight and dashed lines respectively, and are annotated with their associated reward.
trivial check that Vi max {1lv V I. Vo V the setting considered in our Section bounded independently of
- and D.
0, so for any Vo e we have This issue is prohibitive to good performance in where are able construct Vo with |Vo V;
B.2 Lower bounds for discounted value error
Goyal and Grand-Clément 2023 Theorem 3] shows the following:
Proposition B.1. Fix 7 E (0, 1) and an integer n 2 1. Then there exists a discounted MDP
such that for any sequence of iterates (Vi) satisfying Vo 0 and
Vo+1 E Span(Vo..... ... V.. (V)). (v(V.)) Vs 2 0,
14

---

we have for any E {I...., 1} that
7 1 1+7
V.. - V
2
In fact, by reusing the work done within their proof, it is possible to prove the following stronger result:
Theorem B.2. Fix y E (0,1) and an integer n 2 Then there exists discounted MDP (,T,)) such that for any sequence of iterates (Vi) satisfying Vo = 0 and
Vs+1 E spannVin Vo....,
...,, V. (Vo).. Tv(V.)) vs 2 0,
we have for any E (1....,.7 - 1] that
VV.
V 00
Proof. We use the same instance as the one constructed the proof [Goyal and GrrandCCéémnnt
2023 Theorem 3), which has S = .I,...,7h n.. As argued in this proof, the optimal value function
satisfies (1) = プー for all = ....., n. They also show that for any 8 E {o,..... n 1}. assuming V. satisfies the condition in the theorem statement, we have that V.(1) = 0 for any i 12 2. Therefore for any & E (0....,n-11 1},
| - Villa 2 V..(s + 1) - V7 [|6++]]== 0 10---
7
1-
1 1-7
C More notation
|[ loo denotes the I1-1l 11 operator norm of a matrix W. We note that this also equal max; |ee W|] 1| that is, the maximum e norm of all rows of W.
For any policy we re Mr equivalently Ta (s) Eoea <(a s)r(s, a) (for any E S). pPx)
We have V/-T (such that V,"" V. There always exists such a discounted optimal policy which deterministic. Fixing a policy ग, the limiting matrix pos is
rr We let xı denote r-discounted optimal policy
p = C-lim PT lim
pk k=0
T-x
T
where C-lim is the Cesaro limit. We have p Pa = Ps P Pa as Hp,, It is sometimes referred to as the deviation matrix. We have
poo
We denote the Drazin inverse of
T-1 Hp. C-lim T-000
(p P20)
km0
Additionally Hp, satisfies
(I - P.)HH = Hp,
Pa) = P
pe0
Hr, px p 12HHr =0
We also have that p" = pro and h" HH.T.. We refer to Puterman 1994 Appendix A] for more properties of Hr.
The modified Bellman equations can be written a vectorized form as
M(P)) = P:
(6)
T(h) + p h.
(7)
15

---

D Properties of solutions to Bellman equations
First we show that for some (p. h) which satisfy the modified Bellman equations, there exists simultaneously argmaxing policy if and only if they also satisfy the unmodified Bellman equations.
Lemma D.I. Suppose (p, h) satisfies the modified Bellman equations (6) and 77. Then there exists a policy x attaining the maximums in both equations simultaneously, that is there exists π E IIMD such that
(Pp) = (r Ph) = p h.
(8)
(9)
if and only if hi) also satisfies the unmodified Bellman equations
1ab and 1b
Proof. For the entire proof fix (p, h) satisfying the modified Bellman equations and 7 First
we suppose that there exists some π E IIMD attaining the maximums in both equations simultaneously (satisfying (8) and (9)) and try to show that (p. h) satisfy the unmodified Bellman equations (Ta
and (Ib). is immediate that (Ta) is satisfied since is the same as equation (2a). To check (Ib).
note that by (8) have that Ps)( p. and by (9) and (2b) (for the first and second equalities. respectively) we have
r(8, + Pa = p(s) h(s) maxr(s, a) + Paah.
aeA
Therefore we have that
max aEA:P..P=p(s)
r(s + Psah 2 r(8, + Pax(o) p(s) + Ms)
(since P Pen(s)p= p) and also trivially
max aEA:PaaP=p
r(s,a) Paah maxr(s; a) Psah p(s) h(s),
aed
must have A r(s, Paoh p(s) + h(s) (that is, the second unmodified
Bellman equation (Ib) is satisfied).
Now we assume that (p, h) satisfy the unmodified Bellman equations (aa and (lb) and try to show
that there exists a policy æ E MM satisfying (8) and ( We define (for each s S) (T)) E AA to be an action attaining the maximum in (bb. that (s) p(s) and
r(s, P (s p(s) h(s).
But then since p(s) + h(s) .max, A rrss, + Paah by the modified Bellman equation (bb). we clearly have that satisfies (8) and
Next show another equivalent property to (p,h) h) satisfying both the unmodified and modified Bellman equations, the restricted commutativity property, which is essential for Algorithm [
Lemma D.2. (p", f)) satisfies both the modified and unmodified Bellman equations if and only for any E R we have
T(h + axp)) h (a 1)p".
(10)
Proof. First suppose that (p", h) satisfies both the modified and unmodified Bellman equations. By Lemma D.I there exists simultancously argmaxing policy æ satisfying (8) and ( Now letting E R be arbitrary, we have that
T(h + ap") 2 T (h + ap') rx + Pah + Prap" rx + P.h + ap" = =T(h) + tap
using the properties of π. However we can also bound
T(h + ++*) = M(r Ph + Pap') < M(r + Ph) + ((Pap')= = T(h)) aap.
Therefore we must have that ((h ap*) = T(h) + app = + (a + 1)p* as desired (using that satisfies the modified Bellman equation in this final equality).
16

---

Now we assume (TO) holds for all a E R. Note that we immediately have that (p", h) satisfies the modified Bellman equation by taking a 0 (and we always have that MPpp p²). Now we choose sufficiently large so that the corresponding deterministic argmaxing policy ι such that
T(h + -ap) = TT + (h aap")
must satisfy Pap" - p² Specifically a 1+ ++ suffices, because then if π did not satisfy A
P=p" - 0² (but is deterministic) then we would have Pxp" S p* - = Px-p' - A by the definition of A, and thus (fixing some arbitrary E S) we would have
a> 1+11 |1Al1p
(s) rx. (s) te, Pa-
A
( - P ae, T (P - P=p*) = ne. Pa 2 as > - rx- (8)+ (x)
= T (h app) (s) = (s)) + +e_ Ph ap') < (s) + e P.. (h + app) = T (h + app) (s)
and the final inequality contradicts the fact that T(h + -pp) = =T 77(h + kp'). Now using 10) and
then this fact that Pxp" p², and then canceling terms, we have
h + (a + 1)p" = T(h + app) TT + - Tx + Px P. Pp r. + aap
= h p- = To + Pa = T (h).
Using a 0 in I0] we have that Thh)= - p- + h. so - Thus we have shown that is a simultaneously argmaxing policy for the modified Bellman equation solution (p", h) in the sense of (8) and (9). so by Lemma D.I satisfies both the modified and unmodified Bellman equations.
Next we prove Lemma 3.3 and discuss the ambiguity within [Puterman] 1994 Theorem 9.4.1]. To the best of our understanding. the proof of [Puterman 1994 Theorem 9.4.1 makes use of particular
solution h* to the modified Bellman equations which is constructed in (Puterman, 1994 Proposition
9.1.1] by adding a large multiple of p² some h which satisfies the unmodified Bellman equations. This ensures the existence of a simultaneously argmaxing policy (in the sense of equations (8) and ()) and such a policy is used in an essential way for the proof. As noted in Subsection I.1
not all solutions (p. h²) of the modified Bellman equations have p = p², with an example provided in [Bertsekas] 2018) Example 5.1.1]. Also mentioned there, a sufficient condition for p p² is
the existence of a simultaneously argmaxing policy. Therefore, not all solutions of the modified Bellman equations admit a simultaneously argmaxing policy (with [Bertsekas] 2018 Example 1.1.1] necessarily being an example, and another example provided below), so the proof of (Puterman 1994. Theorem 9.4. 1] does not hold for all solutions to the modified Bellman equations. We note that the statement of [Puterman| 1994 Theorem 9, 9,4.1] Lee and Ryu [2024) apparently allows general solution to the modified Bellman equations, although in Lee and Ryu 2024] the definition of solution to the modified Bellman equation adds the condition that simultaneously argmaxing policy must exist.
Proof of Lemma 3.3 We have that
T (ha) npp - All < -
0c + (T)) np" -
by the triangle inequality. Since h satisfies both the modified and unmodified Bellman equations, by Lemma D.2 (used n times) we have
((n) (h) np" h 0
((n (T(h)) -pp h m
r(n-1) (h + p²) - -np" h ((n (h) - (n - 1)p² - h
[(0) (h) (0)p' hh 00
|1/ blll00 O.
By nonexpansiveness T, is easy to see that all these calculations yields the desired result.
[ (ho) - (()) (1) S 11100- -bll Combining
17

---

D.1
Constructing solutions to the modified Bellman equations
In this subsection demonstrate how solutions to the modified Bellman equations h may have a on the order of 1 and arbitrarily large, even when constructed from a vector h" solving the A
unmodified Bellman equations which has | 1l S O(1).
The following lemma demonstrates this construction. This is a non -on-asympooiic version of Puterman 1994 Proposition 1.1.1] which was originally shown by Denardo and Fox [1988]..
Lemma D.3. Letting h = -" + | 11, p p².
+1 p", h satisfies the modified Bellman equation 7 with
Proof. Since we have
M(r + Ph) 2 = (r + Ph)
+
= M=
r P
hT² +
sp
0²
A
11hT
11
+ 1
Tx* +p
Pa-p"
A
||
= pp + 1e"
+
sp
+
p
= p² + h
since Pr.p" = p² and rzr + Px ha p³ + h,," it suffices show that for all deterministic policies
that Md (r + Ph) S p² + h. If P Pot(s)p'' (s), then since h= satisfies the unmodified Bellman
equation (1b) (with p = p²), we have
e, C. (r Ph) = r(s, (())) + h
hhT"
+1
= (r(8,((8)) + P=
sp
P
Pen(s)p*
A
1h
+1
=r(s,((s)) (s
(s(s)
A
+1
S maxr(s,a) + Paah" aEA
sp
p²
(s)
|A="
11
+
max
r(s,a) + Poah"
+
(s(s)
A
1/=""
+
= p'()s + hta (s) +
sp
(*(s)
A
= p*((s) h(s)
desired. Now consider the case where (ax(s)p" (o hm first we calculate that
(=().
Letting a"
(s)) + Panttahi"*
max AEA:P (r(s,a) + Psah
= =rss, T(s)) -r(s,a") + (Pat(s) Poor )
< 1 1rd
(II)
sp
18

---

Also since Pa Ps)()))p < (s), by definition of A we have p²(s) - Ps Pst(s)pp 2 A, and thus
(r Ph) r(s, (8)) + Pen (s)
| 11
+1
=s)) P (
P
Pox(s)p)
A
| 11
+1
{r(s, + Pat(s)
(p*(s)
-A)
A
hmm
1lap
+1
max aEAt
r(s,a) + Peat"
+1+
hr
+
(s)
A)
sp
|| 1p
p' (s)
A (((
pp h(s)
making use in the second inequality.
Now we show a simple example where Tarop.
| 11 01() and [1lll ~ I is arbitrarily large.
+1
+0
+1
+1
+0
+0
Figure 2: A four-state MDP parameterized by e > O. Each arrow represents a (deterministic) action and is annotated with its reward. Only state 4 has multiple actions.
Theorem D.4. Fix E > 0. Then for the MDP in the above Figure
1. Tarop 1.
2. [ 1.
3. =
4. Letting H denote the set of all solutions to the modified Bellman equations,
inf
| ep"
: TR, (0", h= +ep²) E H H =.
Proof. is immediate that
8
This implies that 1 (by considering the actions in state 4). It is also trivial to see that Tarop = 1, since only state has any grainndropping" actions available, and they all lead to states other than state 4 after 1 step. Since necessarily p0 0, this implics that the absorbing states 2,
19

---

must have hn (s) 0. Combining with the unmodified Bellman equation (which h" must satisfy) implies that
0
had
h² + cpp" so we have | 1ppp 1. Finally, for hp",
to satisfy the modified Bellman equation we
must have
0+ + (1) 1 c(1 + (2)
+++01)+0 +0 1+ d +0
cz 3
which implies h= (1) c 2 1 for all solutions of this form the modified Bellman equations, and
furthermore ht (3) + cp" pppppp(') (3) = + c0 = O, which implies the span of h= + op" is at least 1 e-
E
Proof of Proposition
Proof of Proposition
1.1
We have
||
V
2
11,
2 1-7
116o 1' < (1 7)2
2
?"
where the inequality ||
V
S I-y 11V Vl is due to Singh and Yee 1994
ensure
above quantity is S we need
2
(1 - 7)2 1- -
7" S 7)
(1 - 7)2
n log(+)) I log
2
log
(1-g)²
log
2
(1-7)²
log
log(1/7)
log
(1-
1-7
where for the final implication, we use that log(1/7) 2 1- for any 7. Finally, with the stated choice of the RHS above is
n2 2log(n) log (2 (lgg((n) S log(n)
n log (n)
log
2 llg(n)) 2 2log(n) n
as desired, Finally, we can apply [urrek and Chen 2025b
Proof of Theorem 6] to give that
P" 22p - (1 7) 3B + 3
h" sp
+ 1.
F Proofs for sensitivity analysis for multichain MDPs
Proof of Lemma 2.1 h E S we have
We prove the more general statement that for any policy and any vectors
p= p Hp, (Pr - D)p + Po P + P.h h).
20

---

(Then we can substitute p² to obtain the statement of Lemma 2.1
Since Hp, (P= p I, we have
(Pr p (P= - T)p.
Also since Pre (Px - -) and p" = Parra rn, we have
Pr + Pgh
Pao (rx - =p= -P
Combining these two calculations, we have
p² - p= (p" + pP P-
P (rz Pah p- h Hp, (Px D)p.
Lemma F.1.
1. For any policy x, all states s such that e, Pxp" - (s) are transient.
2. For any policy n, Tag is finite.
3. Trrop is finite.
Proof. For the first statement, suppose some state s recurrent under the Markov chain Pr. Then all states in the support of e, P- must also be recurrent and in the same maximal closed recurrent class. By Zurek and Chen 2022bb Lemma 17], any states s" in the same recurrent class have p p'(s') p" p"(s",,
must have eg Pap" = (s)) Therefore by contraposition, if e, Pxp" p (8)
then must be transient.
For the second statement, if for some 8 policy has nonzero probability of taking some action a such that Psap" < p², then we must have Pap" < p*. Therefore almost surely 1(Ps.,A..* <
p" (S))) & I(e Pap < <Si)),)), which implies
Σ T (e Pap < <p'(s))
T drop
max E eES
Σ (PS.,AP < <s)()))
max E. S
#ES
Hence drop is bounded by the expected amount of time spent by the Markov chain Px in states which are transient under Pr (maximized over all starting states), and since the expected amount of time spent in transient states in finite Markov chain is finite [Durrett 2019], must have that T drop is
Tarop
finite.
For the final statement, since there are only a finite number of policies in 1D and Trop each т E MD we have that Tarop ma T < 20.
0o for
Lemma F.2. Suppose that MD deterministic policy. Then
T
max E EES
I Pap < p²)
drop
1=
Proof. Note that for deterministic policy we have A, = T(S)), and thus PS.AA." = Ps. es, Pap". Therefore
XG I (PS.A.P" <p)(S.))
T
max ET SES
Σ
max ET SES
Σ
(c Pap <p)()))
drop
Lemma F.3. Fix a deterministic policy π E 1D let s, E S be two states, and suppose s' is transient under P.. Then
(Hp.) = E.
Σ
I(S, = =
(12)
1=0
21

---

or in words, P. )sa is the expected number visits of state s' when following policy and starting state Therefore
max BES
Σ
(Hp,) B"
(13)
s'ss' is transient under Ps
and
Σ
(Hp.).s' T
drop
(14)
8/ Pa0 <x)()'
Proof. Since s' is transient, we have that e, Pree Eg/ 0. Thus
(Hre)ss' C-lim T-+00
(P* )eo)
k=
lim
e (Pt
P2o yesr
N N
T=1
T-1
lim
e P
transient
N N
T=1 k=0
lim
c.
T T.P es
k=0
E
Σ I(S: = 5t)
where the second-last equality follows from elementary analysis arguments, be using the fact that the Cesaro limit of convergent sequence is simply its usual limit, and the sequence convergent since all terms are nonnegative and the infinite sum finite
ETT c_ e.P. Cs'
TEN
since s' is transient [Durrett 2019
The next two statements follow immediately (noting that by Lemma F.1 all states such that T PrP < p² p=(s') are transient in Pr, and using the formula for T Top given Lemma F.2 for MD).
Proof of Corollary 2.2 Combining Lemma 2.1 with the triangle inequality we have
l| p" lloo $ (H - p² ll | (rx + P.h. p² - -hilloo
Since | 000000 < 1, we can bound
122 + P.h. p² -- -h)ll
< |oo
1000000 || + P.h p² h1ll
< I'm + P.h p² l
(h) h - p"
22

---

To bound [Hpp(PxP* - p0) using Lemma F.3 we have
|Hp, (Prp" p')
=max #ES
C, Hp, (Prp" - pp)]
Σ
(Hrr) not (PTD"
max
#ES
FES
Σ
(Hrr) Cj - -p))
max #E8
s'ES: (P=pp"
E
(Hp,) e - P=pp)
max SES
K'ES: (Pep"
max #ES
Σ
(HP-)ew 110-~ -rrpollo
s'ES: eJ -P=00--0)
(261)
l1e" - -aP 110
drop
In (i) we used that e. (Pxp* p²) + is Ds to
< 0, since (Pap' -p-) > 0
impossible. In (ii) we used the fact that (HP,)..' 2 0 for any state s' which is transient under Pa
(implied by Lemma F.3 and the fact that the states s' such that Pxp" < ps) are transient by Lemma R.1 as well as the fact that e P=p") 2 again. In (iii) we again use Lemma F3
Lemma F.4. For any x. E R and policy π such that P = 0, we have that
sSu Hr S Hr,y.
Proof. To show the desired elementwise inequality, it suffices to fix 8 and show e Hp 1 6g Hr,y. y. By an almost identical calculation to that of Lemma F3 we have that
T-1
e H. x = lim Σ
e p
and e. = lim
e p
T
T+000
k=
k=0
Since ph is a stochastic matrix, x < y implies that
T
T-1
T p
k=0
for any T, and thus
Hp,
lim
Σ
c
p
<
lim
P c, Hr.y.
T-400
km
0
Lemma F.5. For any fixed policy
MD we have T drop S B Consequently Terop S B.
Proof. First we prove the statement for a fixed policy æ. For any set X C S eet E R be a vector such that
ex(s = f (0 otherwise
s SEX X
Let X be the set of states which are transient under P= and let Y be the set states s such that
e. Pap" < (s). By Lemma F.1 we have Y C X, so elementwise I ex. By Lemma E.3 we
have that B = max.es e H Hp, ex and that T max.es e Hp, ey (also using Lemma F. 2 Then using Lemma F.4 we have that
T drop maxe sES
T T Hp S max e Hp, ex sES
23

---

Now taking the maximum over all stationary deterministic policies, we have that
T drop
sup TM
drop
sup Mm
B
Lemma F.6. For any fixed policy IDD
we have T drop S A
Consequently Tarop S A.
Proof.
First we fix policy и E TT and show that Tx drop
S A
From the proof of Lemma 2.1 we
have
1P - Pap') = pp- P p"
and also p² Pop p S 1 since p" 2 0 so Poop" 2 O. We define ey in the same way as in the proof of Lemma F.5 that we let be the set of states s such that e, Pag" < (s) and ey be indicator vector for this set. Then (since Pap I p² so e, Pap" p² (s) for some is impossible) we have that Ey (p* -PPp))
Pap". Then by the definition of A we have that
p Pap" = ey (p" PxPp) 2 Dey.
Since both sides of this elementwise inequality only supported states which transient under P= (so Poo (p" Pap") ) = O and p ey = 0), by Lemma F4 we have that
Hr. (p' P=P*) 2 AHr.ey.
Combining all these inequalities have that
AHp, ey & Hr, (0* - P=P") = p-- PP 1
which implies
AT A Amax drop sES
e Hrp ey $
drop max,es e,_ Hp, as shown in the proof of Lemma F.5 Rearranging have that Trop I 1 as desired, and then taking the supremum over all π E MD we have that T drop = EIDD Trop 5. 3.
(using that T
Lemma F.7. Fix starting state 8y- For any infinite sequence of policies No, Ti...., letting So = 80, A, ~ ( P(- Sr, Ar) its induced distribution over trajectories, and letting E (m)) denote the corresponding expectation, have that
B
Σ F(Sk As) k=
<
Tdrop
T
where r(8,a) T[(Psapp <d)).
Proof. Note that [Puterman, 1994 Assumption 7.1.1] is satisfied, since the reward function is non-negative. Therefore by [Puterman] 1994 Theorem 7.1.9] there exists stationary deterministic optimal policy से for the expected total reward problem. Therefore we have
(n Mimo
Σ r(Sk, As)
E
Σ k=0
r(Sk, Ax)
S Trop S
T drop
desired.

---

G Proofs of coupling-based results
Proof of Lemma 3.7 We prove this result by induction. Note that by convention Ag = (since it an
empty summation). Therefore the = 0 case holds because we have yo = you + Op = - Aop.
Now we suppose that for some have xa yt + Acp. Then (also using the definition that zo yo) we can calculate that
F++1 = (1 B(+1) + ((x1
(1 81+1880 + B1+1 Clys + Asp)
(1 B441)00 + B441 (()) + B1t
(1 Bc+1)00 + 3r+ (yn) + 1 + 1)p
V1+1 3 (Ar 1)p.
Now it remains to show that A4+1 B (A, + 1), which is true because we have
++1
Beti(Ae +1 Be+1
ΣI By +1
EI f=
B3 +
II Bj A1+1-
Proof of Corollary 3.2 Fixing some policy IIMR, we have that T (h) (T
Pxh Ta 1.+P p is an afnne operator, and furthermore it has fixed point ha since by the Poisson/Bellman
equation we have
T (h*) = TT + PPh" p²=
+
The nonexpansiveness of T with respect to 1|-1|,0 also follows immediately from that of T since
-
S ||h h'll
Therefore we can directly apply [Contreras and Cominetti 2022 Theorem 4.6) to conclude that, for any initial point you ho. the Halper--ieraation-eenee
iterate sequence (ye ) where
yo+1 = (1 - f141)80 + B.++1 (2x)
and B = Z4I satisfies
2 11:0- 1- 101000
2
(g:) y1
11
h- 10
(15)
+
+++
To apply Lemma 3.1 notice that for any a E R we have that
T (xr ap") = rr + Pa axp)==p== rr Tn + Pax a aP = + Pax tap (T((x) + ap"
due to the key fact that Pap" p Now applying Lemma 3.1 have that h4 Yt + Aep" (where he is defined in the statement of Corollary 3.2 Therefore
1 (he) - hr - 1=1
T (ye + A App))
(y) App") - p= 11
T (We) + App"
(yr Aep=) p² 11
T (y:) - Yt p #1
7" (yr) 3/1
hoo h" 1lo
t t+1
using the commutativity property in the second equality, and applying 15 in the final inequality.
We note that htd could be replaced with any other fixed point of T (h) with an unchanged analysis.
25

---

H Proofs of results for fixed-point methods under restricted commutativity
Here we prove the main results of Subsection 3.2
H.1
Abstract setting
Recall that seminorm ||-I| is function X - [0, oo) which satisfies the triangle inequality and positive homogeneity, that is, for all v, E X (where X is a vector space) and a E I,
| + yll - ||=||| + |yyl
and
|oo] = |o|| ||=]|]
Our results in this section hold for the abstract setting that L X - X is nonexpansive with respect seminorm
||-I|, meaning
[|<(x) - C(y)ll s 1| yl
for all z, y E X. We assume that L satisfies
C(a + aap x² (a 1)p
(16)
for some p, E X and for all E R. We also define the shifted operator L(x) [(x) p. Note the above implies that x² is fixed-point of L. Also C is clearly nonexpansive since [(x)) L(x') [(x)) [(x') for any x. E X. First we restate Algorithm for this general setting.
Algorithm 4 Approximately Shifted Halpern Iteration (General)
input: Number of iterations n for each phase, initial point zo do 2: Tz+1 C(x))
1: for = .,...,
3: end for
4: Let 20 Fy form gain estimate T = (Inn zo)
Halpern iteration phase; begins with Fy
5: Form approximate shifted operator E as L(z) = [(z) -
6: for -n...,, do B4+1)=0 + ((z)) where 1 1+2
7: 2++1
8: end for
9: return 2n
For the rest of the proofs treat and Ve, the inputs Algorithm 4 as fixed. Before beginning the proofs, we define =* xx + np, and we note that = is also fixed-point of Z (by taking in (16)). For all integers 2 define
A = Σ
II 8 B.Br-1 1.. B.B.-1.... ... ....4 +,,,8-1 +
(17)
We also assume that 90 and let Ao 0.
Lemma H.l. If 9 1 1+3 then L
Proof. We show this by induction. By definition Ao 0, so the desired formula holds for t = 0. Note that by definition Ar, for all 2 we have A, = Be + At-1). Therefore supposing the desired formula holds for some A, where & 2 0, we have
A411 B1+1 + A,) = 1
2 t t+3
1
t
t t+1t+3 ++1
=
3
t 3 3
desired.
26

---

Lemma H.2.
1 pl - 200 x=
and
1120 2011 S a000 x=11.
Proof. First show that
|| (aro) - nop 2| - =x'1l-
(18)
We calculate that
(10) (20) - 20 mop - c (1)) (2r0 - x² - -mp
+ ||x= xoll
C (ox) - -[(r) (x**)
+ ||==* xol
- 110 voll 1l + -1,0* - zool
Next, we have
(xro) -
p
n
so using (88).
||0 pl| ((n))xn) - -p 30
2 [0o - x"1
Next, since 2" = x² + np ((n) we have by nonexpansiveness that
||=0- =01 = (x)) c(") s ||
x=1
Now show the Halpem iterates remain bounded using the shifted Bellman operator L. Lemma H.3. For all S n,
1 - 2= I 3
-1000 - x= 11
Proof. We show the stronger bound
A 11000 - x"1
|| - 2=1| S 1:00- - x=1 +
by induction. This obviously holds for 0 since Ao 0 and by using Lemma H.2 Letting / be arbitrary and assuming the above statement holds for / 1, we have
|| - 2" =
(1 - 8:)20 + 3r - 2-
< (1 3:)=0 + 3([(==1) - ==1 + 3e ||p - 71
S (1 3,) ||20 - 21 + 8, [[((=]1) - 11 8e ||p ~
I (1 (.) | - ='1l + & || - 211l + 8 | P1
$ (1 (.) - =11l + & || - =1 23,
220 x"1 ||
n
At-
2,
$ (1- 8,) 20 111 + 8
|1:00 xx1
11000
x²11 [|
+
-000
x=1
n
n
3,A, 1 + B
(1 3, + 8b) ||z0 2" ||
+ 2
Iz0 x² ||
n
Ar ||:00 a=") ||
= =0 =11 + 2
2 A
< 120 21 +
| x²1
27

---

where the first two inequalities are by triangle inequality, then we use nonexpansiveness, of Z and the fact that 2(=*) = 2", then we use Lemma H.2 to bound ||p - Đll. then we use the inductive hypothesis, in the penultimate equality we use that A, Be Ar-1), and in the final inequality we
use Lemma H.2 to bound 1| =='|.
We conclude by using Lemma
H. and the fact that & n.
Lemma H.4. For all t S n,
[[(z)) =oll S 11:0 x²1l
Proof.
[[(2)) 2011 [[((2) E(=*) + 2- 20
- [Z(z) Z(=*)] + 1|2 - 20l
$ || - 2011 + |1 - 201l
| x=1
using Lemmas H.3 and H.2 in the final step.
Now can prove the main theorem. Theorem H.5.
13 +
35
+
20
[(zn) =n|1
n²
11:00 x"
Proof. For any 2 1, we have
2+41 - 24 = (1 B(+1) 20 + Be41 (1 3:)20 (3(
(Be Be+1) 20 (Be41 - (1) + 3e (Elzs) - ((21-1)
= (Be+1 - BB)) (a(zx) (0)))
20) + Be (A(z.) - [(2-1))
= (Be+1 - (b) (I(z)) - 20) + (E(z) -(zz-1)) + (0c+1-
B: 11:1-13:66
- 7)
Therefore
|| - zell S (Be+1 - 3:) [[(x)) - =zol + 3. [(x) - I(2--1) + (B141 - BB:) 11e - P1
S (Br+1 - 3c) 3 11:00 - x=1| + 3e || -1-1|1 + (Be+1 - BB) 2 1200 - x=11
2
Be || 21 + (8e41 3e)
+ n
||z0 - x"1
(19)
using the triangle inequality, and then Lemmas
H.4 and
H.2
We also note that
||||| - =0ol
(11 B1) B) =0
3,
20
[(z0)
< 81 1|=0 - [((z)]l + 31 [(20) E(zo)
31 11====ZZe - I(zz)]l + 31 lle Pl
< 8,2 =0 - 211 ||
+ 31 11p--10 P1
4 |00 0111
using Lemma H.2 the fact that B1 1 and also the inequality
3.
|| 20
[(z0)]| s -1=0 - 211 + ||((²) - E(z0)] < 2| - 211l
28

---

since 2" is a fixed-point of Z. Now supposing inductively that || - 2 (which we have just confirmed for the case that 0), we use the bound
c+1 ||e x²1
(99
to obtain that
8
2
|=+ 21ll - Be 11:
2-111 + (Be+1 BB)
|1000
x''l
n
16
+ 12
18
2
S B,-
|100 - x011 + (B(+1 - BB))
+
||a0 - xx1
t+1
3
B.
3441
- 3c
(
16
4
+
+
||:00 - x²1 ||
1 +++ 1
2
3
1
16
4
11:0 - x"1l
t
2
3
n1
where the final inequality is because
Bt
+
3o+1
-
3r
=
1
1+2
+
1
1+3
2
-
1 +
1+2
2
+
1
2
++ 1
2
=
(t + 1)(t +2)
+
(++ 2) 3)
1+1
1
$ (t 1)(t +2)
+
Therefore by induction we have that
16 1
|| 1 1|1 5
3 n
100 - x11
+
1
for all t 121 1.
Now relating || - -1l to the fixed-point error, we have
2+11 - 2 = (1 Bc+1)=0 + B4+ [(z)) - 2t
= (1 B(+1) - 21) + Be+1 (Z(zx) 2x)
(1 Be+1) 21) + BB+1 (C(z)) 24) + BB++1 P)
which implies
Bet1 (zx) 21) = (z++1 -z)) - - p) - (1 - Be+1)(E0 z1)
so by triangle inequality
Be+1 [[((z)) 21 < || - zell + Be+1 |lp - p + (1 - (e+1) |:000 - zell
< | - = + Bc+1 ||p - p + (1 - -/+1) (1|=0 - 11 + ||= - 1)
16 + 1
2
x²1 (1 - ) 8 11:00 x=1
11000
x=1| + Be+1
|1:0
++2 2
n
3
16
3 +
++
2 8)
+
+
|1:00 x=1
t+2
2
1+
1+33
Rearranging and simplifying, we obtain
[[(,)) - 2=|1 <
1
18
3
+
4
+
++12
+
2 8)
||:0 x1'l
Be+1
1+2
1n3n
1+33
++3 3
116 + a
4
t+12
2 8
+
|100 - I*1
f ++1 1
1++
f+3n
1 33
2
++3
16 1
16)
110 - x11| +
3
+
120 - =I"l
n
++1
t+2
+
3
2
(+3
1
1
16
4
<
|10
x11 +
+
|1:00 - =x"l
n
1+1
1+2
t+3
n
2
1+3
21+
16
4
110
x11
+
11:0
- -x*1|-
++ 1 (t
1
2)
+ 3)
n
29

---

Now substituting n, and using that
n+25 n+2
1+
+1+
we have
1+
2
2
16
4
[Z(z)) -z|1 -
300
x=1
+
120
x=1
n +
3
n
+
32
+
3
3n
20 - x
||
11
13 +
35
20
n2
200
x
H.2 Undiscounted value iteration setting
Here we specialize to the case of - - T and prove Theorems 3.4 and 3.5
First we develop result to control the first of Corollary 2.2
Lemma H.6. Let h satisfy both the modified and unmodified Bellman equations. Suppose that E RRS satisfies || - Tpp - holloo S B for some r, B >> O. Then if n is greedy with respect to
r+ Pz PT (2)),. we have
2B T 1.
P&p" 2 p"
Proof. Since h satisfies both the modified and unmodified Bellman equations, by Lemma D.1 there
exists policy which attains the maximum in both simultaneouslyy, meaning (h) pp" + h and Pxp" = p Then we can calculate
1
P&P
Px (Tp*)
r
1
Pr (Tp" + h-)
r
2 1
Pr (z --- rpp- - -hll 1 h))
1
1
2
Pr (2 B1 - h)
1
P (P+ (2 B1) + rx p² -h)) h)
1
T (1x Paz B1 p² - h))
2 P
(rr + - - B1 - -p" - h)
1
2 T
(T** Pa. (Tp* +h) Py. ||= - ---ppp-llll-
B1 p²
1
(Fa. Pa (Tp" hh) -2B1 p² h)
p
2B
p
r
where we used the fact that (by the modified Bellman equation 7 Fa + (Th==T(h)) T(h)=
0² h which implies - P,h Tx p" h, and then the fact that since is greedy with respect to
T(=) 7*)x)= = + Pæz, and then in the final equality we used that Pap" 0² and that r= Pah p²
r + Pz we have Tx + Paz T
Lemma H.7 Let satisfy both the modified and unmodified Bellman equations. The policy output by Algorithm 7 satisfies
10 ho h1l
PPap" - -p'1l-- <
n
30

---

Proof. Specializing 1-|l = I1- L = T, and x² = h, by Lemma H.3 we have
5 l1 - h1llo
an np" /1 = || z" 2000 S 200 - x x'1l c0 =
3
By Lemma H.6 this implies that
10 h0 ke
Pap 2 p"
n
Also we trivially have P&p" pp
Lemma H.8. Let lo satisfy both the modified and unmodified Bellman equations. The vector on and policy it ouiput by Algorithm 7 satisfy
13
35
20
T (Zn) p
2m
ho
h hlloo
n
Proof. This follows immediately from Theorem H.5 by specializing ||-I| = 11.11oc = TT and
x h. We note that defined so that T(zn) 7 (zn).
Proof of Theorem 3.4
This follows immediately by using Lemmas H.7 and H.8 to bound the two
terms in Corollary
Proof of Theorem
3.5
Under the assumption that n 2
we have by Lemma H.7 that
A
|Pap" p*1lo0 ho
A<A
12
By the definition of A and since स is deterministic policy, this implies that || -0 = 0.
Using this fact, as well as Lemma H.8 bound the other term in Corollary 2.2 we immediately obtain the desired conclusion.
I Proof of Theorem 4.2
The following theorem on the performance of Halpern iteration for general normed spaces due to (Sabach and Shtern| 2017 Lemma 5]. Their result is presented for Fuclidean spaces but the proof holds for general norms. See [Contreras and Cominetti 2022 Remark 2] for more discussion of this bound.
Theorem 1.1. Suppose C is nonexpansive with respect to some norm ||-||- Let x* be a fixed point of L. and fix some initial point zo- For all t- 1,2,... let F4+1 = =(1 - -8++1)a0 + Bet1 where
8.
2 Then for all 2 we have
242
[[())) F+ll S t ++1 |100 - x²1l
Proof of Theorem 4.2 Let xt be the unique fixed point of L. Let E
1, which is
since 1- 1 2 Since Algorithm generates iterates ......, TE in identical manner to the Halpern iteration described Theorem L.T. and also is conotraccivve for 7 then it is clearly nonexpansive, by Theorem I.I we have that
[[(())) 2x11===1 S t ++1
||l0
x=1
for all f. = O,..., E. In particular
[[(rg) - zell < E+1 1+1 |/20 x'l s
a - x
31

---

...., Now fort = E ...., since we have = ((x--1), it is immediate from y-contractivity of C that
[[((z)) 21 [|((z) (ax S 7 1|, - 24-111 = 7 ([((2)11 xz-
Therefore for all t = 1, E + 2.... we have
[[((z)) rell - x/' 12 [[((z)) ZBll S xm- R 4
100 x"'1
Now we relate these bounds to the quantity
7¹ Σ
First we note the useful fact that
sup 7E(0.1)
- = c.
(20)
which we will verify later. Now for the case that & O,..., E, we can bound
2
Li
2i
t+ 7 -
S 4e
++1
Ei
using (20) in the final inequality, since y Litr +1 I q we can bound
+ +1
Next for the case that t 2 E 1.
4e
Diso 7
where in the final inequality we used 20 again and that Ei 7² S 000
7"
I-
Therefore we have shown that
[zx.) - xzll= s Io x²
E
gl
100
x11l
1>
E
S
4e
1-7
Σ gi
|1:0 x=1. (21)
In the case that 1 1
is an integer, we thus have that
| x*1|
15 F
[[(x)) - xz11 <
S
4e
||:0 - x²1l.
(22)
[(1 - (1(1->)p-- 2- E 11:00 - x11|
1> E
Σ Li=0
In the case that --y is not an integer, using the fact that
since
I- 2 1, we obtain
I
2 1-
1+1 100
x*1| - E 11:0 -80-x" x111
15 E
[C(a)) - -x,1 S
88
|1:0 - x
8(1 - -)
t> E
E
- +1 is smooth function on (0, 1), and it suffices to show that the function 7 ト log(> +1) non-decegsiing and approaches as 7 - 1 (since log is monotone increasing). To show + log(7 +1 is non-decreasing it suffices to show that its derivative is 2 O. We have
Now it remains to verify 20 Note y
y +
log(> --) dy
d
1og(7) 1 y
1 7-1
log(7) 7 1 log(7) (7 1)²
dr 7
77
( - 1)2
and by Taylor's 's theorem applied to log about 7 1, for any ? E (0, 1) there exists some & E (0, 1) such that log(>) = 1+1
( 1)2 < 1, and so 7 1 - log(?) > 0 for any E (0. 1)
and thus the function log(> - +1 nondecreasing. Next, to show that the limit of this function as + 1 is 1, by I. H'Hopital's 'ss rule we have
lim log(> log - lim 7 log(7) = lim 7-1 7
log(7) +
7+1
as desired. Thus suP)e(0.1) log(? _ -1, + 1, and so since log is monotone increasing we have that (o.) 7 + exp(1) desired.
32

---

J Proofs of DMDP Results
J.1 Gain approximation lemmas
In this section we develop several different bounds on the quantity
V
--100
Lemma J.1. For any 7 (0, 1), have that
V7
ht"
+
-drop
+
1
T
sp
sp
Proof. By Zurek and Chen (2024b
Lemma 20),
V --p0" p²
|
lop
which implies
V
Thus it remains to upper-bound V Let n. be deterministic discounted optimal policy (such that Vi "V,"), which is guaranteed to exist Puterman [1994]. From the unmodified Bellman
equation ( (with p pf), E S satisfies e, Pazp" p² (s)) then
max (*(s) + h" (s) aEA:Prap=p(s)
r(s,a) + Psah 2 r(ss, n (s)) (s =raz (s) + c, P Px:h.
instead we have that e,_ Pxip" < (s).. then instead we can bound
T Tmz (s) Cx Pr:: h= PT- (s) - e, Pa- I ||llap + e (
Pa. )h² $1 + 150
and since r=
rx (8) + e P = (s) + h²t (s). we have that
p' + h² (s) + ++ /rm
2 Tx; Pm,
Thus, similarly to what have done in above proofs, letting Y be the set of states such that e_ Pxgp" < pp'(s), and letting ey be the indicator vector for this set, combining the two cases we obtain the elementwise inequality
Im Pash h" -p h= + (1+ | (11)))))) ey
(23)
Thus using the fact that all entries of (1 - PPxx) are nonnegative, we have that
Vi (I pP=;)
Px:)ht + (1 | (1+1 - -eer (24)
S (I - (I=->==:~- +I
Now bound all the terms in 24 First, since Pryp" pp, we can derive that
pk pr pk- x;
P Payp" < pk-1 p' .... Sp
m;
for any integer & 2 0, and thus
(1-7Pag) 11
Σ
7
pk
p*
<
x p = -
k=0
k=D
Next, by Lemma K.1 we have that (I 7 -
Px: yh*
Pr
<
|| |1 1. Finally, shown in
Lemma Ey is only nonzero on states which are transient under the Markov chain Pry. which implies ey = 0. Therefore for any 7 we have that
1
(I (I- (T=/P=:)- -ey (I (T-''Px:)
p ey
1 o
33

---

and so by Lattimore and Szepesvár 2020
Exercise 38.9] we have that
lim (I - Pa;)) lly ey 7/1
lim (1 - er 7'11
1
P ev Hp. ey
-
drop
where the final equality is due Lemma F33 But also have that (1 (1=7/Pa;) (=t:)=tty non-decreasing as 7/ t 1, so this implies that
-tey c is (elementwise)
(1=7Pa;)
lim P/:; 71
=T
dropp'
Finally using these three bounds in we obtain that
V
p
+
h
+
T drop
S
1 --
7-70
1¹ + 1T
+|100
sp
+
(1+
| lmm))
Tdmp-
Lemma J.2. For any 7 E (0, 1), letting h be any solution to both the modified and unmodified Bellman equations 2b and (Ib). we have that
1
1 |1bllp-
Proof. By Lemma D.I. there exists a policy π attain both maximums in the modified Bellman equations simultaneously the sense of (8) and ( that is, Pap" p² and r, Pah (h) T(h) p² + h. Rearranging, this implies that T= pr + + P=)h. Then we have
V 2 Vi
= (1 -Ppp) rx
-P=))==) -P=) (0" + + - Px)h)
(1 -1-7)=)-1pp p² + (1-1Pr) -1- h.)h.
Since Pap" p", this implies that Pspp" p* for all t 2 0, have that
(T-7P=) 0- = , pt
x'
t=
t=0
Also - 7 - - Pa)h 2 -Vill by using Lemma
K.1
Therefore we have shown that
V 2 1-, p² ||bl1.p2
By the second modified Bellman equation 2b have that
p² + .( Ph) 2 M (r Ph) = r=; + Pryh.
Rearranging we have that raz S + (I Pa:)M Then by monotonicity of (I - (PPp.))))- have that
V = (1 7 -1rx rxa
$ (I - 7p=; )- (p- +(I -Ps:)h)
-I 1 + (I - Pm; hh.
Since P= S p², this implies that Pt p" pr for all t 2 0. and have that
(I VP-PPm:) = Σ
pt n.
p*
1 p*.
1=0
1=0
Again using Lemma K. we have that (I P a
(I
Paę )a < |||| sp 1. Thus we have checked
the other direction that V S - |1/||.p rearranging, we have that
combining with the above lower-bound and
|
1
p²
< |1illag
1 ?
34

---

J.2 Discounted reduction results
In this subsection we relate the terms appearing in Corollary 2.2 to those which are directly controlled by solving discounted MDPs, that is, the discounted fixed-point error (V) - V and the value error ||V - -Vill
Lemma J.3. Suppose for some V R that some policy π is e-greedy with respect + yPV, that is, T (V) 2 (v()) e1. Then
IT(V) - - P1IP> - ~0 + [VT Vll + (1 (1-
V
1 1- 0²
1
te.
In particular if is greedy with respect to (E = 0) then
IT(V)) V pp'lo S PPap" 0011 + (VV Vll + - 7) V --
1 1- 00
Proof. We just need to prove the first statement, from which the second follows immediately. We can lower-bound (VV) as
T(V) = M(r + PV) = M (r+ + (1-
1 V
2M r + (1-7)) 1- p- - (1 P)
1
1
V 1
= ( + +Pp - -(1 7)
MM+++PP
+ (V+') ((1 7)
M PVV + Pp') -1 7)
80
V
=M* + Pap* - -(1 7)
= =T,(V) + P -(1 - -(1 -7) V
pz
= =T,(V) a1 + Pap" - (1-
V
1.
1
We upper-bound T(V) as
T(V) M(r + = M M + (1-
1
SM M
+ ( (1-
1 1-
0¹ + (1 P)P
V
1
1
-M r + +Pp + +(1++111- +117) 7) V
=M ((++>PV+PPp) + 7) V 0
1
SM + +1 7)
V
1
= +
1.
1
35

---

Subtracting V + p² from both inequalities and combining, we obtain
T((V) - V - -el+ +1+ PxP - (1 V
1 pz 1
S ST(V) - V p²
1
s STy(V - (1 -v (
1- p²
1.
Therefore
IT(V)- -V V
~0'llo Pxpp - ~0 + +V]T((V) - VIl + (1 (1-)) 7)
V
1
te.
1
Lemma J.4. Suppose for some V RS that some policy π is e-greedy with respect + pPV,
that is, T (V) 2 (v(V) - e1. Then
1 + (TV)) - VIl
1 1+2(1- 1) V
Pap" $ (1 -
1 1 p² 1.
00
Proof. First we calculate that
1 - + P&V
7 -v) -V (1PPV -V)
1
1
PaV
7
7
7
V
n + Tx + TP-V -V V-Tx (T(1) -V
7
7
V ra + Tv(V) -V 8
7
7 ?
which implies
V.
| 10o
+
[T>(V) Vl
1+ + [[T((V) - V 1.
V V-
1
7 7
7
7
Using this key bound, we have that
0² 0- P S (1 (0--)V + (1-
p- V
1 Pap"
7
1
1 (1 - P.V + P1 -7) | 1
((1 + (1 -))
pr V
1- p¹ -
- 1
20
x
(1 (V - PvV) 2 7)
V
1
80
S (1 - 7) 1 + [T(V) VII
1+2(1 - 7)
1--0
1
p
1.
1-7
8
Lemma J.5. Suppose for some V S that some policy n is e-greedy with respect + PVV, that is, TV (V)= 2 (V) - e1. Then
[TT V - - s (IT(V) - p-ppp'lla p P p011 +2(1 -1) V
1
1 - ? p"
te.
Proof. Note that since (*(V)= S T(V), we immediately have that
(²(V) -V V - pp" s T(V) - V - p" < [T(()) - V p011 1.
36

---

Thus it remains to lower-bound (V( - V - p² Let ग be some policy such that M(r + PV)
M (r + PV). Now we calculate that
(V)) M5 PV) M7 (r + +( (1
2 -1
-
2 -
-M²(++ (((r+PV)-- -V)-(--))V-a P
- -M(++ -
= =((V) -1 - (Pa - pT) -(1 (P+ - P*)
1
1
2 T(() e1 - (P= - Pa) - 2(1 7)
V
p²
1
2 T(V) =1 - (p" Pap") 2(1 - -7) V 1
1
where in the final inequality we used that Pap" pp Subtracting V + p² from both inequalities we obtain that
(p' -((1)) 1 1.
1
(V()) TWW)VV-''
2(1
Combining this with the upper bound, taking || and using the triangle inequality, we obtain the desired statement.
L
Lemma J.6. Suppose for some V R$ that some policy π is E-greedy with respect + yPV, that is, T (V) 2 Tv(V- =1. Then
110- p'll I (Tămp + 1) (((1 (( (70-->)1-11
2 2-7 [T, - Vll +2 1 -
2 ?
+
7
9
Furthermore, letting h satisfy the modified Bellman equations
we have
l1e" p'lloo I (Tarop 11 7(1 [711- min
||bllsp:
h
T druup + 155
Taup
+
2 67
(TTx(V) Vll
4p
?
+ 1 -
2 +
7 γ
Additionally assuming 7 2 1/2 we have
1100 0² al 5 (TT + 1) (1 (1->) ( (4+ 4 7 |1blllp 1000111)))
|1-0
Tanp ))
+ T
drop +
sp
+ 16]1TT(V - -Vlloo +48
Proof. By Corollary 2.2 we have
S T
dmp
P p011,s + (V) - V p'lloo
(25)
so it remains to control the terms || p*110o and [V) V - -ppllac By Lemma J.4 we have
1 1 ++++|ITT(V)+ Vll + + -7) | v- 1
||p" - Pap S (1 (1-7)
p"
(26)
7
37

---

Starting with Lemma J.3 we have
1
(V) - V - x 1 s - -V +1 - - 00 + +2(11 - 7) V
- ? p²
1
2
[IPaO' - 001l + (VT Vl + +11-1 -1) 7)
1
V
+ +||P=p* 0'110 + +2(11 -7) || 1
0*
+
8
=2||Pap' -''1 + +3(1 V 1-1 1
pz
+ +[T - VIl +2E
x
(10
1 ++ E + [VT - Vll
+ + 7) ||| 1- 1- p²
22 2 (1 7)
7
+ +3(1 - -7) || V--
1
+ +VV - VIloo +
7 77) |
1- 0-
1
2 1 7 +1) [1T,(V) -ill
+
+2 1 ?
1 1 + 1
+2
7(1 7) V 0r
1
+
2 2-Y
[[T,(V)
V1l +2
+21-7 2
+ -
7
?
00
(27)
where we used Lemma
J.3 in (i) to bound [[T(V) - V - p01l and then used (6) in (ti) to
bound [|Ppp' - pl
Now using this bound we have that
27 on (V) - V - p*1loc and the bound 26 on Pxp" - p'1l in 25
1 1+e+ + [Ta(V) - Vll
+ +2(1 - 7) V 7
110" p01loo S
TTop
(1 - 7)
p²
7
+ 7(1 - 7) || 1
1
2 2-7
[IT((V) - V1l +2 1 7 +
0*
+
e
?
7
< (T drop +1) ((1 - 7)
/1| v
+ 2-7 [T,(()) - VIl
-2-
1
2
p"
+2
_
7
7
(28)
This is the first statement of the lemma. For the second statement of the lemma, we have by the triangle inequality and Lemmas J.1 and J.2 that
pr
$ || - 1l + 1|1
1
p²
7
V Vill + min {
|1bllpp: 1,-0
T
drop
+ ||155
T
Tdmp
xp
up
(V)
VIl
+min
|1lllpp
1000
- -Tarop
|10-
T drop
sp
sp
(29)
where for the final incquality we used the standard fact that VVVl S 1 [1T Vll (which follows from
||V - vi [|V-T,(VIIL.) + [[T,(V) - T,(;5)1 S S (T+(Vll +7|lV - -V;
38

---

and then rearranging). Combining 29
with 28 we have that
l1pT p'1l00 1 (Tärop + +1)
7(1- 7)
7(1
V
1 p²
+
2-7
[[T,(V) - Voloo +2 -
2
7
Tarop }}
x (T drop
+1)
7(1->)
7- [[Tx(V)
-V + min |1bll
1r
+ drop
+
sp
+ 2-7 ([T(() - Vll +2 7 + E
7
2 64
= -Tämup drop
7(1 +1)
(7(1->) -
min
l1bllsp
hr*
+ Tdrop + h=*
Tdrop +
[[T(()) - Vll
+ 2 1 - + -8
2
as desired.
The final statement follows immediately from the facts that y S and s 2.
J.3 Faster value error convergence
In this subsection present results which relate the output of undiscounted Picard iterations to the discounted value function Vi+" with the objective of proving Lemma 4.3
The following lemma basically follows from [Puterman, 1994 Theorem 9,4.1], although as discussed in Appendix D there are some ambiguities in its requirements on h. For this reason we provide complete proof.
Lemma J.7. Suppose that (p", ,h) satisfies both the modified and unmodified Bellman equations. Then for any 2 0, we have
(T)) np* n $ |1bll.p
Proof. First note that elementwise
(max (ns)((())))))))))))) S 0 (min h(s) sE$
sES
By monotonicity of T (applied n times for each inequality), we have that
7 hh (max (m)))(()))1 < (m) (0) S (n) S
h
(minh(s)) h())1
(30)
sES
Using the constant shift property of T (that T(x + cl) T(x) + cl for any x E R and any e E R), as well as Lemma D.2 which guarantees that T(h cp") h + (c+ 1)p², we have that
T (m) (h cl) (n- (T (h + cl)) = ((-1) (h +c1
+ +cl) = (n (2p* + c1) = (m 2) (T
( (np" + c1) np + cl.
Therefore using this calculation to evaluate the left- and right- sides of (30). we have that
np* + h (maxh(s))) h(s)s1 7 (0) I np* + (min h hss))
sES
sES
Rearranging we have
h (max h(s))1 < (T)))()) -p- < - (min h(s)) SES
#ES
which implies
(n)) (0) npp 11 S max
max h(8))
(min h(s)),
min h(s') (max M(s))
=11bll,p
E'ES
$ES
s'ES
SES
39

---

Lemma J.8. For any n 2 O, we have
( np*)
h"
Trop +Tdrpp
h"
T
sp
Proof. Let mi be some poliey attaining the maximum during the kth application of that is
(0) = 7 (T(H=1(0)).
Then it is straightforward to compute that
(() = Txp +
PRa
Tan-1
Pro P Pn--ITnnd + +... (Pon Pan-1 ... Paa) rm
Σ t=1
II A=n
Pa
Trc
(31)
where we take the product I[ which happens only for t = n))
Pa. an be equal to the identity matrix if is empty (if n < t 1,
Using steps identical to those used to obtain
23 but replacing कदद by Te, we obtain for any that Ts. S p" +
1 c.s + (1
+I (I Ph,
where es, is the indicator function for the set of states S; {s e P..p" (s)). Recalling the reward function r(s, a) = PMPp < ps)} defined in Section 2 this is equivalent to M Tz. Combining with (3T) (and using monotonicity of P= for any m we have that
(0+ ( (T--PP,)h)) P=,) + [1+110510 TTl)
(32)
and now we upper bound each term in (32). For any policy we have P=p" P= S SPPP- p", and so applying this fact many times we have that
Σ
II
PRE
P
np
Next, we have that
H II
141
Σ
Pro
(T- Pa, h
PAT
hT
II Pri
h=²
1=1 k=
t=1
k=
1=1
k=n
hT
Pap
h=
Since (IIhnn Pa. ... Px, is a stochastic matrix, we have that h² (IThmn Pre) h
| 1l 1. Finally, have
[+1 II
Σ
PmL
Px. < T
using Lemma since each coordinate of the left-hand side is bounded by the expected total reward value function the nonstationary policy (mı, T2, .... (with terms after time n dropped). Combining these three bounds with 32 we obtain that
T ( np" 1
1 1
hn"
Tarp 1.
sp
up
Finally it remains to lower-bound (m))))). Since we have 0 2 h=¹ max.es hT (s)1 =: x. by monotonicity of T we have that
( > (x)
40

---

Furthermore since 7(h) 2 T (h) for any h we have that
(x) 2 (Tm) (m)
(x))
Furthermore we have
T" (x) Txx + Pa- (h
max ht" (s)1) ra- + Px
max h"d (s)
$E8
=p + ht max h" (s)1 = p² + I.
#ES
Repeating this fact n times we have
(n)
(T
(x) np* np" - 1"*
1.
Therefore
( 2 np"
1,
sp
and so combining with the upper bound on T(n) (0) we conclude that
( - np"
hr ||
hr
T
drop
sp
5p
Now we can combine both of these lemmas along with Lemmas J.2 and
J.1
prove Lemma 4.3
Proof of Lemma 4.3 By triangle inequality we have
(0)
(0)
<<
(0)
1 p"
+
p²
V
t(1 (11~7)
f(1 7)
1
(() (0) tp"
(33)
{(1 (1->)
Using Lemma J.7 bound the first term and Lemma J.2 on the second term, we obtain that
(0)
V
t(1 - 7) |/bllap + ||Ael
t(1 (1--))
2
|1bllap
t(1 - 7)
using the fact that 5
I (so
(1-7)
1) in the second inequality.
Using identical steps but instead bounding the first and second terms of (33 with Lemmas J.S and respectively, we obtain that
1
T (9 ()) - V.
S
2
|
+ Tarop +
,²² Tarop
t(1
1(1 7)
We conclude by taking the minimum of these two bounds on |パ- ((0(() Vi²
J.4 Discounted VI results
Proof of Theorem 4.4 Let M = min || [ssp |//" 1lsp + Tarop + 11 11 Tarop. Since E'
I- we can apply Lemma 4.3 to obtain that
gg - V T(8) (0) V
x E(1 - 7)
M
2
M
1- - 1) (1 11))
2
M.
7
41

---

We can immediately combine this with Theorem 4.2 to obtain that
16e 7u E
[T,(0) ol I
M.
7 2i=o 7
The second statement of the theorem would follow if we could show the bound
E² 7:
1
E
1=0
under the condition that n 2 2E' 1. By rearranging, this is equivalent to showing that
n-E E
Σ 1=0
r S (1 (1+
1 +
Σ
(34)
1=
==
Writing Ei= 7 = >/= ? + Σ n
E'
would follow from showing that
B=
E
(35)
1=0
Under the assumption that n 2 2E 1, we have that
E
E
Σ
1=0
(since
-E>> E" - 1). By rearranging and using the bound 7 1 S e from 20). we have that
F.¹ < 29 1 S, and
7.
E 1
n
$
1=
i F2!
showing (35) as desired.
Proof of Theorem 4.5 have
Let M min {1lhllsp: || 1lap + Tdrop + ||/ T ). By Lemma 4.3
(t)) vz
2M
2M
2M.
n(1 7)
n
By applying 22 from the proof of Theorem 4.2 with = Ty xo (()) x² = -V;, and / = n,
since
1 we obtain that it outputs V such that
[V,(V) - VIl < 4(1 7 11 (() V.
((m) (0) Vi
< +
< 2M
where for the second inequality we used that (1 -- = 1-1 < n+1
1-1 (n+1)(1-1)
since
n+1
42

---

Now combining this bound with Lemma J.6 we have that the policy म which is greedy with respect PPV satisfies
10a
p²
1
S (Tárop +1
7(1 7)
2 2+67
[1Tx(V)
Vll +2 1
7
7
2 6 8M
1
I (T drop +
M +
+
n
n
+
1
7
64M
2
drop + 1)
M +
1
n
T1
71M + 2
S (T drop + 1)
1
Now we demonstrate the effects of using more iterations from the "third phase" of Algorithm Note that the below theorem involves (2 + k) y iterations, so to compare its convergence rate to that of Theorem 4.5 it should be multiplied by (2 + k), and the guarantee of Theorem 4.5 should be multiplied by 2 (since it uses 2n iterations).
Theorem J.9. Fix an integer n 2 2 and a number 2 0 such that kn is an integer. Ser = 1 and run Algorithm 4.4 with inpuls 7: (2 + k)yn Then
|00 p²
10 S (Terop + 1) (7+ 664) +
n
Proof. Let M = min (11
|1,² 1lsp + T drop ||"" T drop
By identical steps to the previous
proof, we have that the vector V output by Algorithm 4.4 satisfies
[[T,(V) - 1l I 4(1 7)7 (1+1))))
(0) Vit 1
I 4(1 (k
8 km M.
Furthermore we have nmm (1
1 < e Combining with Lemma J.6 we have that the policy
which is greedy with respect to r + PV satisfies
10
p²1
(Tē
drop +1)
7(1- - ([1->)M
2 2+66
[VT,(V)
Vll + 2 2--7
7
7
2+6 6
8M
(T drop + 1)
M +
71
1- I
n
1
64M
2
(T drop
+ 1)
+
+
n
72
n
*64) +2
$ drop
+ +1)
n1
We remark that the function (2 1)) + 64c-k) is minimized l: 3.78 with value 48.9, which a factor of approximately 142/48.9 Rs 2.9 smaller than the value at k =
K
Auxiliary lemmas
The following calculation, which we use several times and hence include for completeness, essentially identical to one within the proof of Zurck and Chen [2024b] Lemma 20].
43

---

Lemma K.1. For any policy and any h E R we have that
11a- P S &11bllspp
Proof. Using the Neumann series to expand
(I=) we have
06
(1->P=)) Pt)
= Σ
pt
1ptt1
t=0
[=0
I =
YP,
Pl
P
Pt
t=
0
= =1+ + ( 1)P4 Σ 7
1=0
= I - - -a)
Pr. and (1 11-7) -> are all stochastic matrices (all entries are non-negative and all rows sum to 1), and hence Px (1 - 71 - -Pa)) is also stochastic matrix. Then it is immediate for any stochastic matrix Q that elementwise have millees h(s) s Qh S max.ss h(s)1, which implies
||(I- - TP= Pa)hll
-1a)al = =1 11 (1 - - S ||bll.p
as desired.
L Experiments
While this paper focuses on theoretical complexity analysis, we provide few preliminary experi- mental examples.
First we describe, for parameters k. T 2 1 and æ > 0, the parameterized MDP M 7) on which we run our experiments. M(, 7') has + 1 states, where state 0 is absorbing (has only one action, which leads back state 0). The remaining states each have two actions, titled "good" and "bad". The "good" actions all lead deterministically to another of the states {1...., }} such that if the "good" action taken in all such states then forms a cycle of length k. For convenience we let Tee denote this policy which takes the "good" action in all states in (1....,k) kj. The reward for the "good" action is chosen randomly to be or 0.5 with equal probability. The "bad" action in state s for any E {1,..., k) has reward 1, and leads to state () with probability 1/7 and back to the given state s with probability 1- 1/T. Finally, we define the reward of the only action the absorbing state 0 to be Tm (1)
(that is, compute the reward of the cycle, and then subtract e). Hence the optimal policy is Te (considered to take the only available action in state 0), which will have pT (s) = nT (1) for all E [L....,k) k} and - (0) = (1)
Note all other policies have gains equal to (1) 1. It is straightforward to compute that A = f and Tanp = T.
Below we plot the fixed point error [T(h)) h4 p*1 for the tth iterate generated by Algorithm I standard value iteration (VI), and [Lee and Ryu 2024, Theorem 2] (LR). We intentionally focus on the case where the number of iterations n is smaller than k (the total number of states). We plot both
E = 1/2 and ε = 1/20, keeping 10, = 300. All experiments were run on single consumer laptop in less than minute.
44

---

0.5
= 0.05
Alg.
Alg.
LR
LR
W
15.0
15.0
12.5
12.5
1/FE
10.0
3/
10.0
7.5
7.5
5.0
5.0
2.5
2.5
0.0
0.0
100
40
100
Iterations
Iterations
note that due to periodicity, VI does not converge. In this experiment, decreasing & seems not to affect the convergence of Algorithm[] whereas LR seems converge more slowly. We emphasize that these experiments only consider the fixed-point error, whereas our sensitivity analysis reveals that it is essential to additionally control p' l*1 in order to obtain suboptimality bounds. Overall, much more thorough experimental study on more domains and metrics is needed to better understand the practical performance of our algorithms.
45

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims made in the abstract and introduction are substantiated throughout Sections 3 and
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limitations the paper are discussed in the conclusion in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
46

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
All code used to produce the experimental results is provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "cipps.c/puulli//guu /tte:///uuddde/oooSuuubbmiibia ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All experimental details are provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: There are no meaningful sampling errors in the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
48

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Computational resource information is provided.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:p/s///aarpssccooooooo///haa
Answer: [Yes]
Justification: This paper does not have any direct negative societal impacts nor any potential harms caused by the research process.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper studies theoretical aspects of solving Markov decision processes and thus there are no immediate positive or negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
49

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
50

---

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

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
52


Reviews:
[{"review_id": "PIVVa37gFx", "reviewer": "Reviewer_RpJU", "summary": "This paper presents a finite-time convergence analysis for value iteration in general (multichain) MDPs under the average-reward setting. Unlike traditional value iteration, which relies on the contraction property of the Bellman operator (typically present in discounted settings), the average-reward case lacks contraction, rendering standard analysis techniques inapplicable. While prior works have attempted to address this challenge using complexity parameters, their guarantees often degrade to worse than $\\mathcal{O}(1/n)$ in the general MDP setting. This paper introduces a novel complexity measure, gain-dropping time, which is both theoretically analyzed and shown to yield sharper convergence bounds. In addition, the authors develop new average-to-discounted reductions and establish optimality results for fixed-point methods in general Banach spaces.", "questions": "* A proof sketch for key results (e.g., Theorems 3.4 and 4.5) would improve readability and help clarify the paper's novel analytical techniques.\n* Lemma F.5 & F.6 shows that $T_{drop}$, which is asymptotically better than either bound in general. However, could $T_{drop}$ still be on the order of $in$ the worst case? Clarifying the tightness of this bound would be helpful.\n* The concept of gain-dropping time is quite interesting. Is it possible to extend this notion to analyze sample complexity or regret bounds in the offline or online reinforcement learning settings?", "limitations": "The authors acknowledge that exact computation of Bellman operators may be infeasible in large-scale MDPs, and stochastic approximation may be necessary. Another limitation is that although the authors show that $T_{drop}$, no absolute constant upper bound is provided. As such, practical estimation or bounding of $T_{drop}$​ remains an open issue.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths** \n* This paper introduces a novel complexity measure, gain-dropping time, to analyze the convergence rate of value iteration in multichain average-reward MDPs. Based on this measure, the authors derive convergence bounds that improve upon prior work.\n\n* The motivation is clearly stated, and the limitations of existing approaches are thoroughly discussed.\n\n* A new reduction technique is proposed that connects average-reward problems to discounted ones. This enables better bounds on the optimality gap under general MDP settings.\n\n\n**Weaknesses**\n* The paper is entirely theoretical. While the results are strong, empirical experiments demonstrating faster convergence compared to existing baselines would significantly strengthen the paper.\n\n* The convergence guarantees rely on the assumption that the bias vector $h$ satisfies both the modified and unmodified Bellman equations. Although Theorem D.4 discusses special cases (e.g., when $h$ is constant), a more general constant bound on $h$ would enhance the practical interpretability of the results.", "was_revised": true, "final_justification": "I accept the authors’ explanation and will maintain my positive score for this paper.", "rebuttal": "We thank you for your positive review. We would like to respond to some of your listed weaknesses and questions.\n\n1. Weakness 2: While we agree that requiring $h$ to satisfy both Bellman equations reduces its interpretability (relative to $h$ which satisfies only the unmodified Bellman equation, since in this case the bias function of a bias-optimal/Blackwell-optimal policy can simply be used), we note that prior works studying the convergence of value iteration for general average-reward MDPs [Lee and Ryu 2024, Puterman 1994] have also utilized $h$ satisfying these requirements. (In fact, [Lee and Ryu 2024, Puterman 1994] analyze under arguably an even less interpretable assumption, that $h$ satisfies the modified Bellman equation and also admits a policy in the simultaneous argmax of equations (2a) and (2b), in the sense of equations (7) and (8); one of our minor contributions is showing that such $h$ are exactly the $h$ which satisfy both the modified and unmodified Bellman equations (Lemma D.1).)\n2. Question 1: Here we provide more details of the proofs of Theorems 3.4 and 4.5. Overall, we agree that including these details would benefit the paper, and we would use an additional camera-ready page to do so.\n\n    - Theorem 3.4: The high-level approach is to control both terms appearing in Corollary 2.2, which itself is a direct consequence of Lemma 2.1. As discussed in the paragraph beginning on line 241, Lemma 3.3 can be used to obtain an estimate $\\hat{\\rho}$ of the optimal gain $\\rho^\\star$. This enables the formation of the approximately shifted operator $\\widehat{\\mathcal{T}} := \\mathcal{T} - \\hat{\\rho}$ which is used in Algorithm 1. At a high level, since standard convergence analyses of Halpern iteration would guarantee small fixed-point error if it were ran using the “perfectly” shifted operator $\\mathcal{T} - \\rho^\\star$, our analysis then shows that instead using $\\widehat{\\mathcal{T}}$ does not cause too much error. As discussed in the paragraph beginning on line 248, this is only immediately sufficient to control the fixed-point error term from Corollary 2.2, but since the second phase of the algorithm is initialized with $x_n$ which is well-aligned with the direction $\\rho^\\star$ (and because our analysis demonstrates that this property is still true after the second phase terminates), the other term $\\| P_\\pi \\rho^\\star - \\rho^\\star \\| $ appearing in Corollary 2.2 is also guaranteed to be small after termination.\n\n    - Theorem 4.5: The starting point here is to use our novel discounted reduction Lemma 4.1. Internally the proof of this lemma also makes use of Corollary 2.2 and connects its bound to quantities related to the discounted Bellman operator. As discussed in the paragraph beginning on line 287, Lemma 4.1 suggests that we must try to achieve small discounted fixed-point error while using a large value of the effective horizon $\\frac{1}{1-\\gamma}$. This objective leads us to the development of Algorithms 2 and 3, for reasons which are explained in those sections but in particular in the paragraphs beginning on lines 314 and 330. This culminates in Algorithm 3 and Theorem 4.4 describing its performance, which we can essentially directly combine with the reduction Lemma 4.1. One interesting key lemma is Lemma J.1, which relates the optimal discounted value function $V_\\gamma^\\star$ to $\\rho^\\star$ using the $T_{drop}$ parameter and is key for both the proof of Lemma 4.1 and the proof of Algorithm 3/Theorem 4.4. Lemma J.8 performs a similar function but instead relates $\\mathcal{T}^{(n)}(\\mathbf{0})$ to $\\rho^\\star$, and is also key to the idea of Algorithm 3 and Theorem 4.4.\n3. Question 2: The bounds of Lemmas F.5 and F.6 are tight, as can be seen by the following example: Fix a parameter $T > 1$. Consider an MDP with three states (1,2,3). State 1 has only one action which is absorbing with reward +1. State 2 also has only one action which is absorbing and with reward +0. State 3 has two actions: the action 1 leads deterministically to state 1 and gives reward +1. Action 2 gives reward +1, and has probability $1-1/T$ of leading back to state 3, and probability $1/T$ of leading to state 2. Then it is straightforward to compute that $\\rho^\\star = [1 ~ 0 ~ 1]$ and the parameters $\\mathsf{B}, \\mathsf{T}_{drop}$, and $1/\\Delta$ are all equal to $T$ for this instance.\n4. Question 3: We believe that there is a high possibility that the gain-dropping time could be useful in simulator/offline RL settings, and it might be interesting to understand whether new algorithms could achieve sample complexity results in terms of this sharper parameter, rather than the bounded transient time parameter used in [Zurek and Chen 2025b]. It may also be useful in the online setting, but a main obstacle in the online setting is formulating a useful notion of regret for general average-reward MDPs, since generally an algorithm may become “trapped” in low gain regions of the MDP without any ability to escape."}, {"review_id": "vsBo1zlVwf", "reviewer": "Reviewer_9Hca", "summary": "They explicitly decompose the multichain average reward MDP problem into the “navigation/transient” subproblem (reaching the best recurrent class) and the “recurrent” subproblem (optimizing long-run reward within a class). Accelereated VI schemes are proposed and lower bounds are matched to show optimality of the theoretical convergence rate.", "questions": "- It would greatly enhance the paper's impact by constructing a motivating example in the introduction why multichain average reward is really a pressing subject to study instead of discounting and weakly communicating MDPs in an RL setting.\n- Numerical examples for the proposed algorithm would also greatly help.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- Halpern‑then‑Picard achieves the lower bounds in Banach spaces; immediately drives faster VI for multichain MDPs.\n- Lemma 4.1 ties average‑reward error to discounted residual without exploding terms, enabling a practical $\\gamma$‑tuning recipe.\n\nWeaknesses\n\n- Convergence relies on a Blackwell‑optimal policy that simultaneously maximizes both Bellman equations and on knowing n≫1/Δ; these caveats are scattered in footnotes/appendix. \n\n- Notation is heavy - for example, nine new symbols appear in Section 2; key ideas (why Halpern warm‑start solves navigation) are buried on the other hand.\n\n- The link to practical RL speed‑ups is weak. Bounds carry huge factors and require preset phase lengths based on unknown parameters, and no adaptive rule is proposed.\n\n- Claims of “faster” remain theoretical; paper omits timing comparisons on even toy multichain MDPs.", "was_revised": true, "final_justification": "The authors clarified the points raised so I increased my score from 3 to 4.", "rebuttal": "We would like to address several inaccuracies of this review. \n\n1. Response to weaknesses bullet 1: Our algorithms for solving general average-reward MDPs do not depend on knowledge of Blackwell-optimal policies in any way. While some _guarantees_ in our theorems depend on a vector $h$ which satisfies both the modified and unmodified Bellman equations, such a vector $h$ is only used in the _analysis_ and is not needed to run the algorithms. Additionally, knowledge of $n > 1/\\Delta$ is not required to run the algorithms. This condition is used in one location, Theorem 3.5, which strengthens the convergence rate for Algorithm 1 relative to Theorem 3.4 when this condition happens to hold. Overall, all our theorems explicitly state all assumptions required for them to apply to the algorithms, and there are no “scattered” caveats in the appendices/footnotes.\n2. Response to weaknesses bullet 2: The paragraph beginning on line 248 is dedicated to discussing why the warm-start phase is helpful for solving the navigation problem. Section 2 features only two new definitions, our novel parameters $T^\\pi_{drop}$ and $T_{drop}$.\n3. Response to weaknesses bullet 3: As mentioned in our first bullet point, the only condition on phase lengths is $n > 1/\\Delta$ appearing in Theorem 3.5, and this only strengthens the convergence rate of Algorithm 1 when this condition holds (relative to Theorem 3.4, which applies without this condition). Algorithm 1 does not require any unknown parameters to be run. While our results are stated for the setting where the desired number of iterations $n$ is decided upon beforehand, our convergence rates can trivially be extended to the “anytime” setting where $n$ is chosen later by running the algorithms with $n=2^1, 2^2, 2^3, …$. We feel as if the leading ($\\Theta(1/n)$) terms in our results do not feature prohibitively large constants. Overall we focused on qualitative improvements relative to prior work."}, {"review_id": "0ohofnhQ23", "reviewer": "Reviewer_pddB", "summary": "This paper presents new iterative algorithms to compute the gain in general finite MDPs and the optimal value in discounted MDPs.\nThe algorithms combine Picard iterates and Halpern iterates to alleviate the non-contraction of the Bellman operator.\nIn both cases, the error bounds are within small factors to lower bounds.", "questions": "Maybe a numerical section proving experiments on \"generic\" MDPs would show that the gap with previous approaches is not marginal?\n\n\nThe remark made in conclusion about the computability of Bellman operators is quite intriguing and deserves some explanations.\nThe reader does not understand what the authors have in mind.\nFor example, the case of compact action spaces is quite different because solutions of Bellman equations are not always optimal in that case.\nThis also rises the question of time and space complexity of the proposed algorithms.", "limitations": "The main limitation is the incremental character of the paper. The discussion on previous work is precise and explains  the difference between both bounds. However, this difference can be marginal and can even disappear in some cases. \n\n\nAnother point of interest, that  is not discussed at all, is the use of alternative methods that do not use VI to compute the gain and value of the MDP.\n\n\nAn average or even smooth complexity analysis of fixed point methods in MDPs is also missing. That would have a more significant impact in practical uses.\n\nThe topic of this paper is borderline with respect to the main subject of NeurIPS (all aspects of Machine Learning).", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper uses a well thought combination of classical (Picard) and Cezar-type (Halpern) iterates that seem to be innovative.\nMaybe a discussion on this coud be added.\n\n\nBoth algorithms  (discounted  and undiscounted) have  marginally better errors bounds than existing results as they introduce a new complexity parameter T_{drop} \nthat is smaller than existing ones, although it is of the same order in the worst cases.\n\nThe definition of T_{drop} is qualitative and not quantitative: why not take the average gain of the actual difference (max with 0) instead of the indicator that looks less sharp?", "was_revised": true, "final_justification": "I keep my positive score. I like the way the author use Cezaro type iterations but I still have concerns about using this result for ML purposes.", "rebuttal": "We thank you for your positive review. We would like to respond to some of your listed weaknesses and questions.\n\n1. Third paragraph in Strengths and Weaknesses section regarding definition of $T_{drop}$: We agree that whether the indicator can be removed is an interesting question, and it would appear that the answer is negative for the following reason: We believe it is possible to show that $\\mathbb{E}^\\pi [\\sum_{t=0}^\\infty \\rho^\\star(S_t) - P_{S_t, A_t}\\rho^\\star ] = \\mathbb{E}^\\pi [\\rho^\\star(s_0) - \\rho^\\star(S_\\infty)]$, where $S_\\infty$ is some state in the (potentially random) closed recurrent class reached by the policy. This implies that we would always have $\\mathbb{E}^\\pi [\\sum_{t=0}^\\infty \\rho^\\star(S_t) - P_{S_t, A_t}\\rho^\\star] \\leq \\max_s \\rho^\\star(s) - \\min_s \\rho^\\star(s)$, which is $\\leq 1$ for our scaling (where $\\|r\\|_\\infty \\leq 1$), which is probably too small to serve as a complexity measure since it is bounded $O(1)$ independently of the properties of the MDP. (We believe that adding a max with $0$ would still not fix the overall issue.)\n2. Second question: We are happy to expand upon our comments. One potential setup is that, instead of assuming access to the transition matrix $P$, and hence the ability to exactly compute matrix-vector products of the form $Ph$, we could instead investigate the development of algorithms which are only able to access $P$ stochastically via sampling: given $s,a$, we can only draw a sample $S’$ from the distribution given by the row vector $P_{sa}$; in this case then $h(S’)$ will be an unbiased estimate of $(Ph)(sa)$ (the $s,a$th coordinate of the vector $Ph$). Since computing $ (Ph)(sa) $ will generally take $O(S)$ time, if $S$ is large then this sampling approach might be able to form a sufficiently good estimate of $ (Ph)(sa) $ in a smaller amount of time (if samples can be obtained sufficiently quickly).\n3. First paragraph of limitations: Beyond making quantitative improvements in algorithmic performance relative to prior work, we believe that overall we also develop a range of useful theoretical observations which expand the foundations of this topic. We also note that since value-iteration-style methods form the backbone of many approaches to reinforcement learning and have extensive prior work, even apparently small differences in approaches are still of significant interest and may lead to downstream impacts.\n4. Second paragraph of limitations (re non-VI methods): We agree that this is an interesting topic, however, we are not aware of major studies of the complexity of alternative methods for solving general average-reward MDPs. Despite the very long history of VI methods for average-reward MDPs, non-asymptotic complexity guarantees have only been developed very recently.\n5. Fourth paragraph of limitations: We feel that this paper is squarely within the stated call for papers for NeurIPS, fitting within the topic of \"Reinforcement learning (e.g., decision and control, planning, hierarchical RL, robotics)\", as our paper mainly focuses on solving MDPs (thus addressing the \"planning\" problem). Our paper is also related to the NeurIPS topic of Optimization. In particular, we present some results in a general language of fixed-point methods common to optimization researchers (ex. Theorem 4.2, Appendices H and I)."}, {"review_id": "7ww2satnMF", "reviewer": "Reviewer_9RCM", "summary": "This paper presents new value-iteration (VI) algorithms for solving multichain Markov Decision Processes (MDPs) under the average-reward criterion---a setting known for its analytical and computational difficulties. Unlike discounted MDPs, average-reward problems lack contractivity and may yield non-unique Bellman solutions. A central challenge in the multichain setting is the navigation subproblem, where an optimal policy must guide the agent toward the most rewarding recurrent class. The authors address this with novel algorithms that exhibit faster convergence by incorporating sharper complexity measures such as the gain-dropping time \\\\(T_{\\text{drop}}\\\\). Additional contributions include improved reductions between average-reward and discounted problems, optimal fixed-point methods applicable to Banach spaces, and refined suboptimality bounds. Collectively, these results strengthen the theoretical underpinnings of VI for general MDPs.", "questions": "1. How sensitive are the algorithms to inaccuracies in the estimated gain vector \\\\( \\rho^\\star \\\\)? Could a poor estimate significantly affect convergence or policy quality?\n2. Many guarantees require that the initial vector \\\\( h_0 \\\\) and the target \\\\( h \\\\) satisfy both the modified and unmodified Bellman equations. How practical is it to construct such an \\\\( h \\\\) in real-world settings?\n3. To what extent do the results depend on the specific commutativity conditions of the Bellman operator? Could similar results be generalized to operators lacking this structure?\n4. The warm-start procedures (e.g., using \\\\( T^{(t)}(0) \\\\)) are critical to performance. Are there other initialization schemes that could yield better empirical performance or simplify implementation?\n5. The value of \\\\( \\gamma = 1 - \\frac{1}{n} \\\\) plays a crucial role in performance. Could the algorithm adapt \\\\( \\gamma \\\\) dynamically during training based on observed convergence behavior?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. Introduction of the gain-dropping time \\\\(T_{\\text{drop}}\\\\) allows more accurate characterization of the navigation difficulty in multichain MDPs.\n 2. Proposed methods achieve optimal or near-optimal non-asymptotic convergence rates, surpassing prior works by Lee \\& Ryu and Zurek \\& Chen.\n 3. Results extend to general Banach spaces and unify various aspects of fixed-point theory and MDP planning.\n  4. Intermediate results such as discounted-to-average-reward reductions and fixed-point error analyses can benefit a broad range of applications.\n   5. The paper presents well-structured algorithms (e.g., Shifted Halpern Iteration, Warm-start Halpern-then-Picard) with precise theoretical guarantees.\n\n\nWeaknesses\n\n1. The work is entirely theoretical; practical performance on real-world or benchmark problems is not demonstrated.\n 2. While asymptotically efficient, the proposed multi-phase algorithms may incur substantial runtime in large-scale problems.\n 3. Several results assume access to solutions of both modified and unmodified Bellman equations, which may not be readily obtainable.\n 4. The technical presentation is dense, potentially limiting readability for practitioners unfamiliar with fixed-point theory or advanced MDP concepts.", "was_revised": true, "final_justification": "Having reviewed the authors' responses, I remain satisfied and will uphold my positive recommendation.", "rebuttal": "We thank you for your positive review. We would like to respond to some of your listed weaknesses and questions.\n\n1. Weakness 3/Question 2: For the theorems in Section 3 which involve an initialization $h_0$, no assumptions are made on $h_0$. In particular it does not need to satisfy both the modified and unmodified Bellman equations. A vector $h$ satisfying both equations is needed only within the analysis and the statement of the convergence guarantee within the theorems, but is not needed to run the algorithm.\n2. Question 3: You are correct that our results can be generalized to operators beyond the Bellman operator, as we show in Appendix H.1 (culminating in Theorem H.5). However, this theorem shows that we can find points with small fixed-point error for operators satisfying a certain generalized commutativity property (equation (14)), but there is no obvious general analogue of extracting a “policy” from such a fixed point and arguing about the gain-preserving properties (in the sense of Corollary 2.2) of such a policy, so overall not all of our results have any analogue in this more general setting.\n3. Question 4: The warm-start procedure is designed so that $T^{(t)}(0)$ is well-aligned with the direction $\\rho^\\star$ (in the sense that $T^{(t)}(0) \\approx t \\rho^\\star$), so a different procedure could generally try to accomplish this in another fashion, but it is not immediately clear how to do so without knowing $\\rho^\\star$ a priori.\n4. Question 5: It is unclear how to modify the proposed algorithms to utilize adaptive stepsizes, but this is an interesting topic of future research."}]

Author rebuttal:

Meta-review: This submission studies faster fixed-point methods for solving multichain Markov Decision Processes (MDPs) under the average-reward criterion, where the Bellman operator is non-contractive and standard value-iteration analyses struggle. The authors propose iterative schemes that combine Halpern (Cesàro-type) and Picard updates, introduce a sharper complexity measure and develop average-to-discounted reductions and optimal fixed-point results in general Banach spaces. They provide non-asymptotic convergence guarantees that improve on prior bounds (e.g., Lee & Ryu; Zurek & Chen), with lower-bound matching up to small factors in the relevant settings.

Reviewers generally found the theoretical contributions solid and well-motivated. The new complexity parameter offers a cleaner characterization of the navigation/transient difficulty in multichain MDPs and is smaller than previous parameters (though worst-case orders can coincide). The algorithms (e.g., warm-start Halpern-then-Picard, shifted Halpern) are clearly specified with precise guarantees, and the discounted-to-average reduction avoids blow-ups that hampered earlier analyses.

At the same time, concerns remain. The work is entirely (or nearly entirely) theoretical; empirical validation is limited (the authors later provided a simple synthetic example illustrating fixed-point error decay, but broader experiments are still missing). Some assumptions raised questions about applicability, although the authors clarified that vectors satisfying both the modified and unmodified Bellman equations are used for analysis and statements of guarantees—not required to run the algorithms. 

During rebuttal, the authors added proof sketches and clarifications (including tightness examples for parameter relationships) and addressed several misunderstandings. Taken together with the reviewers’ largely positive assessments (three borderline-accepts and one accept), I view this as a strong theoretical contribution that advances the state of the art on convergence guarantees for multichain average-reward MDPs. While richer experiments would strengthen the paper, the novelty and rigor here meet the bar.

Recommendation: Accept.
Decision: Accept (poster)