Accelerating Value Iteration with Anchoring
Authors: Jongmin Lee
Ernest K. Ryu
Venue: NeurIPS 2023 poster (2023)
Keywords: Value Iteration
Reinforcement Learning
Reinforcement Learning Theory
Dynamic Programming
Acceleration
Anchoring mechanism
TL;DR: We proposed anchored value iteration and achieve an accelerated rate for the Bellman consistency and optimality operators.

Abstract: Value Iteration (VI) is foundational to the theory and practice of modern reinforcement learning, and it is known to converge at a $\mathcal{O}(\gamma^k)$-rate. Surprisingly, however, the optimal rate for the VI setup was not known, and finding a general acceleration mechanism has been an open problem. In this paper, we present the first accelerated VI for both the Bellman consistency and optimality operators. Our method, called Anc-VI, is based on an \emph{anchoring} mechanism (distinct from Nesterov's acceleration), and it reduces the Bellman error faster than standard VI. In particular, Anc-VI exhibits a $\mathcal{O}(1/k)$-rate for $\gamma\approx 1$ or even $\gamma=1$, while standard VI has rate $\mathcal{O}(1)$ for $\gamma\ge 1-1/k$, where $k$ is the iteration count. We also provide a complexity lower bound matching the upper bound up to a constant factor of $4$, thereby establishing optimality of the accelerated rate of Anc-VI. Finally, we show that the anchoring mechanism provides the same benefit in the approximate VI and Gauss--Seidel VI setups as well.

Accelerating Value Iteration with Anchoring
Jongmin Lee'
Ernest K. Ryu
Department of Mathematical Science, Scoul National University Interdisscpllinry Program in Artificial Intelligence, Seoul National University
Abstract
Value Iteration (VI) is foundational to the theory and practice of modern reinforce- ment learning, and it is known converge O*)*) )-rate, where y is the discount factor. Surprisingly, however, the optimal rate in terms of Bellman error for the VI setup was not known, and finding general acceleration mechanism has been an open problem. In this paper, we present the first accelerated VI for both the Bellman consistency and optimality operators. Our method, called Ane-VI, is based on an anchoring mechanism (distinct from Nesterov's acceleration), and it reduces the Bellman error faster than standard VI. particular, Ane- VI exhibits a ((1k))-rate for R 1 or even = 1, while standard VI has rate ((1) for 7 2 1/k, where k the iteration count. We also provide complexity lower bound matching the upper bound up to constant factor of 4, therehy establishing optimality of the accelerated rate of Ane- VI. Finally, we show that the anchoring mechanism provides the same benefit in the approximate VI and Gauss-Seidel VI setups as well.
Introduction
Value Iteration (VT) is foundational to the theory and practice of modern dynamic programming (DP) and reinforcement learning (RL). It is well known that when a discount factor 7 < is used, (exact) VI is contractive iteration in the -norm and therefore converges. The progress of VI is measured by the Bellman error in practice (as the distance to the fixed point is not computable), and much prior work has been dedicated to analyzing the rates of convergence of VI and its variants.
Surprisingly, however, the optimal rate in terms Bellman error for the VI setup was not known, and finding a general acceleration mechanism has been an open problem. The classical (7**)) of VI inadequate as many practical setups use y R or 7 for the discount factor. (Not to mention that VI may not converge when 7 = 1.) Moreover, most prior works on accelerating VI focused on the Bellman consistency operator (policy evaluation) its linearity allows eigenvalue analyses, the Bellman optimality operator (control) is the more relevant object in modern RL.
Contribution. In this paper, present the first accelerated VI for both the Bellman consistency and optimality operators. Our method, called Anc-VI, is based on an "anchoring" mechanism (distinct from Nesterov's 's acceleration), and it reduces the Bellman error faster than standard VI. In particular, Anc-VI exhibits a (1akk))r for Rs 1 or even
1, while standard VI has rate O(1) for y 2 1 1/k. where i the iteration count. We also provide a complexity lower bound matching the upper bound to a constant factor of 4, thereby establishing optimality of the accelerated rate of Ane-VI VI. Finally. we show that the anchoring mechanism provides the same benefit in the approximate
VI and Gauss Seidel VI setups as well.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1.1 Notations and preliminaries
We quickly review basic definitions and concepts of Markov decision processes (MDP) and reinforee- ment learning (RL). For further details, refer to standard references such as [69, 84, 81].
Markov Decision Process. Let M(X) be the space of probability distributions over X. Wriie (S,A, P.r.) to denote the MDP with state space S, action space A, transition probability P: x
A + M(S), reward r: S x A - IR, and discount factor 7 (0, 1]. Denote w: S M((A for a policy, (*(() = Ex =
Ex r'r(st, at) 8o = s] and Q (s, a) E [r )'r(s,, 80 8, 4g a] for V- and Q- Q-value functions, where Eg denotes the expected value over all trajectories (80, 40, 81, (I....) induced by P and x. We say V and Q" are optimal V- and Q- value functions if V sup, and Q* sup, Q-. We say Ty and Te are optimal policies if m. argmax V and = a Q (If argmax is not unique, break ties arbitrarily.)
Value Iteration. Let F(X)) denote the space of bounded measurable real-valued functions over X. With the given MDP (S,A, P.r, 7). for E F(S) and Q E F(S A), define the Bellman consistency operators 7 as
(s) Ea-a( 12). [r(s, + +ss(s') (Q(s',a'))
T a) r(s, a)
for all s sES,a E A. and the Bellman optimality operators T as
(V) = sup {r(s. a) + y PC (s.a) [V($']}} acA
T ('Q(s, = r(s,a) + 7BB sup ((s',a')
L'EAA
for all s S S,a E A. For notational conciseness, write T rr + 7p=V V and T r + 7P=Q, where r*t (s) Be-a(-11 (s) (r(s,a) a)] is the reward induced by policy and (s) and
(s) defined as
(n + 5 = Prob(s + lallam((-ls) ~ p()ls.a)
Pd ('s + (s' a') = Prob((s,a) + (s',a')s'' ~ P(-1s,a),d ~ T(- s')),
are the transition probabilitics induced by policy w. We define VI for Bellman consistency and optimality operators
for k = 0, l...., where 10 Q" are initial points. VI for control, after executing K iterations, returns the near-optimal
yk+1 = V =++1=
= Q= Vt+ = T*V
policy गх as greedy policy satisfying
V =T T= = I=xQ"=T"Q"* TTQK
For y < both Bellman consistency and optimality operators are contractions, and, by Banach's fixed-point theorem [5], the VIs converge to the unique fixed points V Q=, VV, and Q" with 0(7*) -rate. For notational unity, we use the symbol U when both V and Q can be used. Since U + | Ul
|TU U T
VI exhibits the rate $ (1 + 7) U U Il
on the Bellman error:
(1) where 7 is Bellman consistency or optimality operator, U a starting point, and U fixed point of T. We say V < V' or Q < Vf < V*(s) or Q(s,a) & as) for all s E S and E A, respectively.
||TU*
1
< (1+
+ 7) 1100 U+1
for 0, 1,...
Fixed-point iterations. Given an operator T, we say x" is fixed point Tf = x². Since Banach [5], the standard fixed-point iteration
-++ = * for k 0, 1......
has been commonly used to find fixed points. Note that VI for policy evaluation and control are fixed-point iterations with Bellman consistency and optimality operators. In this work, we also consider the Halpern iteration
x k+1 = 3x412 + (1- Bx41)Tx*
for k = 0, I,..,
where z is initial point and BBaNNE E 10.

---

1.2 Prior works
Value Iteration. Value iteration (VI) was first introduced in the DP literature [8] for finding optimal
value function, and its variant approximate VI [11, 30, 56, 32, 19, 90, 81] considers approximate evaluations of the Bellman optimality operator. In RL, VI and approximate VI have served as the basis of RL algorithms such as fitted value iteration [29, 57, 52, 87, 50, 36] and temporal difference learning [80, 89, 41, 94, 54]. There a line of research that emulates VI by learning a model of the MDP dynamics [85, 83, 62] and applying modified Bellman operator [7, 33]. Asynchronous VI, another variation of updating the coordinate of value function in asynchronous manner, has also been studied in both RL and DP literature [11, 9, 88, 100].
Fixed-point iterations. The Banach fixed-point theorem [5] establishes the convergence of the standard exed-point iteration with a contractive operator. The Halper iteration [39] converges for nonexpansive operators on Hilbert spaces [96] and uniformly smooth Banach spaces [70, 97]. (To clarify, the || -nrm in R is not uniformly smooth.)
The fixed-pont thintt residual [Tr 2% is commonly used error measure for fixed-point problems. In general normed spaces, the Halpern iteration was shown to exhibit O11/ (ol//oo()))--attt for (nonlinear) nonexpansive operators [48] and (11
for linear nonexpansive operators [17] on the fixed- point residual. In Hilbert spaces, [72] first established a ((1/k)-rate for the Halpern iteration and the constant was later improved by [49, 43]. For contractive operators, [65] proved exact optimality of Halpern iteration through an exact matching complexity lower bound.
Acceleration. Since Nesterov's 's seminal work [61], there has been a large body of research on acceleration in convex minimization. Gradient descent [15] can be accelerated to efficiently reduce function value and squared gradient magnitude for smooth convex minimization problems [61, 44, 45, 46, 102, 21, 60] and smooth strongly convex minimization problems [59, 91, 64, 86, 73]. Motivated by Nesterov acceleration, inertial fixed-point iterations [51, 22, 75, 70, 42] have also been suggested to accelerate fixed-point iterations. Anderson acceleration [2], another acceleration scheme for fixed-point iterations, has recently been studied with interest [6, 74, 93, 101].
In DP and RL, prioritized sweeping [55] is well-known method that changes the order of updates to accelerate convergence, and several variants [68, 53, 95, 3, 18] have been proposed. Speedy Q- learning [4] modifies the update rule of Q-learning and uses aggressive learning rates for acceleration. Recently, there has been line of research that applies acceleration techniques of other areas to VI: [34, 79, 28, 67, 27, 76] uses Anderson acceleration of fixed-point iterations, [92, 37, 38, 12, 1] uses Nesterov acceleration of convex optimization, and [31] uses ideas inspired by PID controllers in control theory. Among those works, [37, 38, 1] applied Nesterov acceleration to obtain theoretically accelerated convergence rates, but those analyses require certain reversibility conditions or restrictions on eigenvalues of the transition probability induced by the policy.
The anchor acceleration, a new acceleration mechanism distinct from Nesterov's, lately gained attention in convex optimization and fixed-point theory. The anchoring mechanism, which retracts iterates towards the initial point, has been used to accelcrate algorithms for minimax optimization and lxxed-point problems [71, 47, 98, 65, 43, 20, 99, 78], and we focus on it in this paper.
Complexity lower bound. With the information based complexity analysis [58], complexity lower bound on first-order methods for convex minimization problem has been thoroughly studied [59, 23, 25, 13, 14, 24]. If complexity lower bound matches an algorithm's convergence rate, it establishes optimality of the algorithm [58, 44, 73, 86, 26, 65]. In fixed-point problems, [16] established
0(1/kI-V2/4) lower bound on distance solution for Halpern iteration with nonexpansive operator in g-uniformly smooth Banach spaces. In [17], ((1/k)) lower bound on the fixed- -xintpoinnt residual for the general Mann iteration with a nonexpansive linear operator, which includes standard fixed-point iteration and Halper iterations, in the -*x was provided. In Hilbert spaces, [65] showed exact complexity lower bound on fixed-point residual for deterministic fixed-point iterations with 7-contractive and nonexpansive operators. Finally, [37] provided lower bound on distance to optimal value function for fixed-point iterations satisfying span condition with Bellman consistency and optimality operators and we discussed this lower bound in section 4.
3

---

2 Anchored Value Iteration
Let T' be a 7-contractive (in the || -norm)omm) Bellman consistency or optimality operator. The Anchored Value Iteration (Anc-VI) is
U B2U (1 TT)
(Anc-VI)
for k = 1, where 3x 1/(2inn 22) and U is an initial point. In this section, we present accelerated convergence rates of Ane- VI for both Bellman consistency and optimality operators for both V- and Q-value iterations. For the control setup, where the Bellman optimality operator is used, Anc- VI returns the near-optimal policy л greedy policy satisfying T U. TUU* after executing K iterations.
Notably, Ane- VI obtains the next iterate as a convex combination between the output of T and the starting point U We call the 9g Un term the anchor term since, loosely speaking, it serves to pull the iterates toward the starting point Uo- The strength of the anchor mechanism diminishes as the iteration progresses since 3g is a decreasing sequence.
The anchor mechanism was introduced [39, 72, 49, 65, 17, 48] for general nonexpansive operators and || ||l=nonexppanive and contractive operators. The optimal method for || - ||2-nonexpansive and contractive operators in [65] shares the same coefficients with Anc-VI, and convergence results for general nonexapnsive operators in [17, 48] are applicable Ane- VI for nonexpansive Bellman optimality and consistency operators. While our anchor mechanism does bear a formal resemblance to those of prior works, our convergence rates and point convergence are neither a direct application nor a direct adaptation of the prior convergence analyses. The prior analyses for ||| pnnnnnexpannsvv and contractive operators do not apply to Bellman operators, and prior analyses for general nonexpansive operators have slower rates and do not provide point convergence while our Theorem 3 does. Our analyses specifically utilize the structure of Bellman operators to obtain the faster rates and point convergence.
The accelerated rate of Anc-VI I for the Bellman optimality operator is more technically challenging and is, in our view, the stronger contribution. However, we start by presenting the result for the Bellman consistency operator because is commonly studied in the prior RL theory literature on accelerating value iteration [37, 38, 1, 31] and because the analysis in the Bellman consistency setup will serve as a good conceptual stepping stone towards the analysis in the Bellman optimality setup.
2.1 Accelerated rate for Bellman consistency operator
First, for general state-action spaces, we present the accelerated convergence rate of Anc- VI for the Bellman consistency operator.
Theorem 1. Let < < be the discount factor and a be a policy. Let T be the Bellman consistency operator for V or Q. Then, Ane- VI exhibits the rate
| S (7-1 -7) (1 2 +
11000 U
-1
( - g
2 k k- +
1100 0(6)))100-UT)1
for k = 0, 1,...
k+ 11+1
k+1
where e = 1 and the big-O notation considers the limit e + O. If. furtheroree, Uo S U or t TT" then Anc-VI VI exhibits the rate
1k - -U 5 (7-1 - 7) 7 - xht1)
1100 1100- -U"
(gk+1) -
-(11 x k+Iet ((e))
for k 1....
k+1
If 7 1, both rates of Theorem are strictly faster than the standard rate (1) of VI, since
(7-1 - 7) (1 + 27 - *21
* (1 7²) (1 + 27 k+1)
< <1 +7).
(111) kh+1
(1 - 71-22k-44 2x-+2)

---

The second rate of Theorem 1, which has the additional requirement, is faster than the standard rate (1) of VI for all 0 < y < Interestingly, in the y regime, Ane- VI achieves ((1/k))-au while VI has (11) We briefly note that the condition U < TU and U 2 TU have been used in analyses of variants of VI [69, Theorem 6.3.11], [77, p.3].
In the following, we briefly outline the proof of Theorem while deferring the full description to Appendix B. In the outline, we highlight particular step. labeled A. that crucially relies on the linearity of the Bellman consistency operator. In the analysis for the Bellman optimality operator of Theorem 2, resolving the step despite the nonlinearity is the key technical challenge.
Proof outline of Theorem 1. Recall that we can write Bellman consistency operator as TV r" + +-PPVV V and T r + -p= Q. Since 2 is a linear operator', we get
U U² = U* (1 - -aa)T= U 11 - U* - 3x U*)
- yp= (U* - -(1 -11 Bxx Bx)) 11 B2U*)= - Bx - -U")
>P"" (Ba(U - -U*) (1 BBT - -U--1)) -Bx(U0 - U*)
Σ (10) - -3,- -B))) (11 (1 8,)) (1P")) -+1 (U) Un)
8:( - - + (T) - 3,)) (y/D) h+1 (U -
where the first equality follows from the definition of Anc-VI and the property of fixed point, while the last equality follows from induction. Taking the |1-11 -norm of both sides, we conclude
T - - S (7---) 7) (1 (1+2 2y - A+1)
1 - 10-lll 10
(Λ gk+1
2.2 Accelerated rate for Bellman optimality operator
We now present the accelerated convergence rate of Anc-VI for the Bellman optimality operator. Our analysis uses what we call the Bellman anti-optimality operator, defined as
(*) inf {r(s,a) -PE (s,a) [v()) atA
Q')(ssa)== = r(s,a) a) + 7E (s.0)
inf Q(5 a() a'EA
for all S and A. (The sup is replaced with inf.) When 0 < 7 < 1, the Bellman anti-
optimality operator is 7-contractive and has unique fixed point Ú* by the exact same arguments that establish 7-contractiveness of the standard Bellman optimality operator.
Theorem 2. Let O < < 1 be the discount factor. Let T* and T respectively be the Bellman optimality and anti-optimality operators for V or Q. Let U and i respectively be the fixed points Tf and f Then, Anc-VI VI exhibits the rate
| - U* (7---7) 27 2 xt1)
max -U' -00 -
(gxt1) - xk+1
for k 0,1, ... If. furthemoree, 10 5 T or Uo TTU then Anc-VI exhibits the rate
U 1211 5 (7-1-7) (1+7-
1 -0-1-l
if < U
(x++1) - -6+11
(1 + o
| 1*11 < (x _ g0+1
100 370-0111
ft > Uo
for k = 0,
'Arguably, 1 is affine, not linear, but follow the convention of [69] say Td is linear.
5

---

Anc- VI with the Bellman optimality operator exhibits the same accelerated convergence rate as Ane- VI with the Bellman consistency operator. As in Theorem the rate of Theorem 2 also becomes ( /k) when y x while VI has (-rate....
Proof outline of Theorem 2.
The key technical challenge of the proof comes from the fact that the Bellman optimality operator is non-linean Similar to the Bellman consistency operator case, we have
T U² T* (1 - Bc)T T - B²(U0) U*)
- -2 - -U*) 3 7PTH (U+ - -(1 -1- (1-31x) -2-))U
= >p= (Br (U - -U²) + (1 - UKt 1 (T*
(b- - -B=eU00 - UU)
x Σ [(3: - -Bi-1(1 - -.)) (1) - -8)) (PT) (v - U*)]
1=1
3x(U0 - U*) + (1)= 8,)) (IP= (U U²),
where Tt is the greedy policy satisfying U yyptkypPe- ...... and last inequality follows by induction and monotonicity of Bellman op- timality operator. The key step A uses greedy policies ( which are well defined when the action space is finite. When the action space is infinite, greedy policies may not exist, so we use the BaanchBanach extension theorem to overcome this technicality. The full argument is provided in Appendix B.
T*U we define ?
To lower bound U* - U*, we use similar line of reasoning with the Bellman anti-optimality operator: Combining the upper and lower bounds of T*T U we conclude the accelerated rate of Theorem 2.
For y 1, the rates of Theorems and can be translated to bound on the distance solution:
1 - S Six (1 + 7) (1 + 27 - *+1
1000
U
2k+2)
for A: = Therefore, Ane-VI VI is better than VI terms of the Bellman error, but it is not better than VI in terms of distance to solution.
This O(7*) rate worse than the rate of (classical) VI by a constant factor.
3 Convergence when 7 =
Undiscounted MDPs not commonly studied in the DP and RL theory literature due to the following difficulties: Bellman consistency and optimality operators may not have fixed points, VI nonexpansive (not contractive) fixed-point iteration and may not convergence to fixed point even if one exist, and the interpretation of a fixed point as the (optimal) value function becomes unclear when the fixed point is not unique. However, many modern deep RL setups actually do not use discounting, 2 and this empirical practice makes the theoretical analysis with y = 1 relevant.
In this section, show that Ane- VI converges to fixed points of the Bellman consistency and optimality operators of undiscounted MDPs. While a full treatment of undiscounted MDPs is beyond the scope of this paper, show that fixed points, if one exists, be found, and therefore argue that the inability to find fixed points should not be considered an obstacle in studying the y = setup.
We first state our convergence result for finite state-action spaces.
Theorem 3. Let r = 1. Let IR + R" be the nonexpansive Bellman consistency or optimality operator for V or Q. Assume a fixed point exists (not necessarily unique). If. U < TU', then Anc-VI exhibits the rate
ITU - - k k 1100-U11.
for k = 1......
? As a specific example, the classical policy gradient theorem [82] calls for the use of VJ(0) E [Ee 7 V log To (a. (s.) a.)]. but many modern deep policy gradient methods use 7 in the first instance of 7 (so y 1) while using 7 < in (8 at) [63].

---

for any fixed point U satisfying U S U Furthermore, U - U for some fixed point U
rewards are nonnegative, then the condition U < TU is satisfied with U 0. So, under this mild condition, Ane- VI with y converges with (11/k)-rate convergence t + U has no rate, i.e., || - U = o(1), while ||TU* - U* O11 (1))).
the Bellman error. To clarify, the
In contrast, standard VI does not guarantee convergence in this setup.
We also point out that the convergence of Bellman eгror does not immediately imply point conver- gence, i.e., TU* U does not immediately imply U +U+, when 7 1. Rather, we show (i) U is a bounded sequence, (ii) any convergent subsequence U converges to fixed point U and (iii U elementwise monotonically nondecreasing and therefore has a single limit.
Next, we state our convergence result for general state-action spaces.
Theorem 4. Let 7 1. Let the state and action spaces be general (possibly infinite) sets. Let T be the nonexpansive Bellman consistency optimality operator for V or Q, and assume T is well defined. Assume a fixed point exists (not necessarily unique). If - TTU, then Anc-Vi exhibits the rate
ITUK- - 1lo S
-
k ++1 1100 -U'
for k 0,1,...
for any fixed point U** satisfying U S U Furthermore, U - U pointwise monotonically for some fixed point U
The convergence U U pointwise in infinite state-action spaces is, in view, a non-trivial contribution. When the state state-action space is finite, pointwise convergence directly implies conver- gence in || lloc, and in this sense, Theorem 4 is generalization of Theorem 3. However, when the state-action space is infinite, pointwise convergence does not necessarily imply uniform convergence, i.e. U 0 pointwise does necessarily imply U + U in loc.
Complexity lower bound
We now present complexity lower bound establishing optimality of Ane-VL.
Theorem 5. Let k 2 0, 2 k + 2, 0 < S 1, and U E RR, Then there exists an MDP with [S] = n and |A| = (which implies the Bellman consistency and optimality operator for V and Q all coincide T: R > J such that T has fixed point U* satisfying U < U* and
gk
TTU -
1bo
b 100-U"1
for any iterates {U MED satisfying
U E U + span (TU" - UO,TU"
TU - for = 1,...,k k.
Proof outline of Theorem 5. Without loss of generality, assume = k + 2 and U = 0. Consider the MDP (S, A, P, P.r,1 7) such that
S $1...... 2k+2), A farl.
P(s: $3, 01) = [(i=j=1,j--1)} r(s;, a1) 1l (i=2))
Then, T = >PU + 0, 1, o.., U 10, 1, "/1 and | - U l = 1. Under the span condition, we can show that (U*), (Ut) k+2 =0. Then, we get
T UK (0. 2 2 (U*)2 (U*))..... : (U*)2 (U*) . (Uh) k+11)
and this implies
(TU* - UU), + (TU* k U + + (TU* U*) + ... + (TU* - U² k+2 =
deell-deiinenness of I' requires alageba on state and action spaces, expectation with respect to transition probability and policy to be well defined, boundedness and measurability of the output of Bellman operators,
7

---

Taking the absolute value on both sides,
(1+ + +y
max 15isk=2
1 1b 2 21.
Therefore, we conclude
gk
ITU 1l0
100 -001
Σ 2i=0
Note that the case 7 is included in Theorem 5. When 7 1, the lower bound of Theorem exactly matches the upper bound of Theorem 3.
Since
(y -7 (1+ (1+7- ()&t1)= -ght g
4
for all <
Σ
Di=0?" 72
R
the lower bound establishes optimality of the second rates Theorems 1 and up a constant of factor Theorem improves upon the prior state-of-the-art complexity lower bound established in the proof of [37, Theorem 3] by factor 1 -*+1_ (In [37, Theorem 3], lower bound on the distance to optimal value function is provided. Their result has an implicit dependence on the initial distance to optimal value function || lco,
make the dependence explicit, and translate their result to a lower bound on the Bellman error. Once this is done, the difference between our lower bound of Theorem 5 and of [37, Theorem 3] is factor of 1 k The worst-case MDP of [37, Theorem 3] and our worst-case MDP primarily differ in the rewards, while the states and the transition probabilities are almost the same.)
The so-called "span condition" of Theorem is arguably very natural and satisfied by standard VI and Anc-VI. The span condition is commonly used in the construction of complexity lower bounds on first-order optimization methods [59, 23, 25, 13, 14, 65] and has been used in the prior state-of-the-art lower bound for standard VI [37, Theorem 3J. However, designing lower bound of Theorem 5 by violating the span condition remains a possibility. optimization theory, there is precedence of lower bounds being broken by violating seemingly natural and minute conditions [40. 35, 98].
algorithm that breaks the
Approximate Anchored Value Iteration
In this section, we show that the anchoring mechanism is robust against evaluation errors of the Bellman operator, just as much as the standard approximate VI.
Let 7 1 and let T be the Bellman optimality operator. The Approximate Anchored Value lteration (Apx-Anc-VV VI) is
Uh = T k-1
(Apx-Anc-V]
t = 0R + +(1 U
for 3: = 1,2, where 3g 1/ 21),, t is an initial point, and the (E*) is the enror sequence modeling approximate evaluations T
Of course, the classical Approximate Value Iteration (Apx- VI) is
U = T + k-1
(Apx-VI)
for k 1,2, where 7 an initial point.
Fact 1 (Classical result, [11, p.333l). Ler < y < 1 be the discount factor. Let T be the Bellman optimality for V or Q. Let U* be the fixed point of T Then Apx- VI exhibits the rate
u - 10 s (1+ - - -U* + +1 +1+ (1+))
1
max os 0Sisk-
||='|
for k = 1, 1.2.....
I-2

---

Theorem 6. Let O < < 1 be the discount factor. Let T* and T respectively be the Bellman optimality and anti-optimality operators for V or Q. Let U and U respectively be the fixed points Tf and T Then Apx-Anc- VI exhibits the rate
1T - U² 1m ( (1 +1++0 27 k+1)
max - -10000
(gh+1) - ghtt
1 7 1 1-
1 g1+1 1- yy os osisk-1
max
||=
for 1,2,...
furtherroee U 2 UU then (Apx-Anc-VI) exhibits the rate
1| -1% I (--1 (1 + 1 -- 1 for k -1,2.....
|00 0-
1+7 1-gh max 1+ k+l 1 - yy 0sisk-1 ||=||l
+
(abt1) 7bt1
The dependence on max ||ell> of Apx-Ane-Vi VI no worse than that Apx-VI. this sense, Apx-Ane-VI is robust against evaluation errors of the Bellman operator, just much as the standard VI.-VI. Finally, we note that a similar analysis can be done for Apx-Anc- VI with the Bellman consistency operator.
6 Gauss-Seidel Anchored Value Iteration
In this section, we show that the anchoring mechanism can be combined with Seide-Seid updates in finite state-action spaces. Let < and let T* R" - IR" be the Bellman optimality operator. Define Tas
R"
+ R" as
TØs = T ... TTTT
where Tÿ RR + R is defined as
(T(U) = -00)=(nn) (U1, (
for j = I.....
Fact [Classical result, [69, Theorem 6.3.4]] Tés is y-contractive operator and has the same fixed point as T*
The Gauss Gauss-Seidel Anchored Value Iteration (GS-Anc-VI)
t = 38800 + (1 3x) Ut)
(GS-Anc-VI)
for k = 1,,,..., where 3r = 1/ 21)) and U is an initial point.
Theorem 7. Let the state and action spaces be finite sets. Let 0 < be the discount factor. Let T* and T respectively be the Bellman optimality and anti-optimality operators for V or Q. Let U and U* respectively be the fixed points of T* and T Then GS-Anc-VV VI exhibits the rate
|TāsU* 1 (--1-7) (1+ 27 - x
max {1100 10 0% 1'1
(7++1) ( -
for =0,1.... If. furthermore, U S &Tā or Uº 2 Uo then GS-Anc- VI exhibits the rate
TTās 12 I (7- (1 +1 y -
it < Uo
(x++1) -1 - -ght1
|TāS 1/ I (y - (1 + - -
1000 1
ft > Uo
(x++1)-1 - xh1
for k = 0,,,
We point out that GS-Anc-V VI cannot be directly extended to infinite action spaces since Hahn-Banach extension theorem not applicable the Bauss-Seide setup. Furthermore, we note that a similar analysis can be carried out for GS-Anc-VI VI with the Bellman consistency operator.

---

7 Conclusion
We show that the classical value iteration (VT) is, in fact, suboptimal and that the anchoring mechanism accelerates VI to be optimal in the sense that the accelerated rate matches complexity lower bound up to constant factor of 4. We also show that the accelerated iteration provably converges to fixed point even when 7 1, if fixed point exists. Being able to provide substantive improvement upon the classical VI is, in our view, surprising contribution.
One direction of future work is to study the empirical effectiveness of Anc-VI. Another direction is to analyze Ane- VI model-free setting and, more broadly, to investigate the effectiveness of the anchor mechanism in more practical RL methods.
Our results lead and reinforcement learning may be improved with careful examination based on an optimization complexity theory perspective. The theory of optimal optimization algorithms has recently enjoyed significant developments [44, 43, 45, 98, 66], the anchoring mechanism being one such example [49, 65], and the classical DP and RL theory may benefit from similar line of investigation on iteration complexity.
believe that many of the classical foundations of dynamic programming
Acknowledgments and Disclosure of Funding
This work was supported by the the Information & communications Technology Planning & Evalua- tion (IITP) grant funded by the Korea governmen((MSIT) Graduate School Program (Seoul National University)] and the Samsung Science and Technol- ogy Foundation (Project Number DSTF-BA2101-02), We thank Jisun Park for providing valuable feedback.
Artificial Intelligence
References
[1] M. Akian, S. Gaubert, Z. Qu, and O. Saadi. Multiply accelerated value iteration for non- symmetric affine fixed point problems and application to markov decision processes. SIAM Journal on Matrix Analysis and Applications, 43(1):199-233 2022.
[2] G. Anderson. Iterative procedures for nonlinear integral equations. Journal of the Associa- tion for Computing Machinery, 12(4):547-560, 1965.
[3] Andre, N. Friedman, and R. Parr. Generalized prioritized sweeping. Neural Information Processing Systems, 1997.
[4] M. G. Azar, R. Munos, M. Ghavamzadeh, and H. Kappen. Speedy Q-learning. Neural Information Processing Systems, 2011.
[5] S. Banach. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fundamenta Mathematicae, 3(1):133-18) 1922.
[6] M. Barré, A. Taylor, and A. d' Aspremont. Convergence of constrained vector extrapolation scheme, SIAM Journal on Mathematics of Data Science, 4(3):979-1002, 2022.
[7] M. G. Bellemare, G. Ostrovski, A. Guez, P. Thomas, and R. Munos. Increasing the action gap: New operators for reinforcement learning, Association for the Advancement of Artificial Intelligence, 2016.
[8] R. Bellman. A Markovian decision process. Journal of Mathematics and Mechanics, 6(5):679- 684, 1957.
[9] D. Bertsekas and Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Athena Scientific, 2015.
[10] D. P. Bertsekas. Dynamic Programming and Optimal Control, volume 4th edition, 2012.
[11] D. P. Bertsekas and J. N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1995.
10

---

[12] W. Bowen, X. Huaqing, Z. Lin, L. Yingbin, and Z. Wei. Finite-timy theory for momentum Q-learning. Conference on Uncertainty in Artificial Intelligence, 2021.
[13] Y. Carmon, C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points
1. Mathematical Programming, 184(122):71-120, 2020.
[14] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points II: first-order methods. Mathematical Programming, 185(1-2)315-355, 2021.
[15] A.-L. Cauchy. Méthode générale pour la résolution des systemes d' d'équations simultanées. Comptes rendus de I' l'Académie des Sciences, 25:536-538, 1847.
[16] V. Colao and G. Marino. On the rate of convergence of Halpern iterations. Journal of Nonlinear and Convex Analysis, 22(12):669--266, 2021.
[17] J. P. Contreras and R. Cominetti. Optimal error bounds for non-expansive fixed- fixed-point iterations in normed spaces. Mathematical Programming, 199(1-2):443374, 2022.
[18] P. Dai, D. S. Weld, J. Goldsmith, et al. Topological value iteration algorithms. Journal of Artificial Intelligence Research, 42:181-209, 2011.
[19] D. De Farias and B. Van Roy. On the existence of fixed points for approximate value iteration and comorrl-ddfffereee learning. Journal of Optimization theory and Applications, 105:589-608, 2000.
[20] J. Diakonikolas. Halpern iteration for near-optimal and parameter-fres freee monotone inclusion and strong solutions to variational inequalities. Conference Learning Theory, 2020.
[21] J. Diakonikolas and P. Wang. Potential function-based framework for minimizing gradients in convex and min-max max optimization. SIAM Journal on Optimization, 32(3):1668-1697 2022.
[22] Q. Dong, H. Yuan, Y. Cho, and T. M. Rassias. Modified inertial Mann algorithm and inertial CQ-algorithm for nonexpansive mappings. Optimization Letters, 12(1):87-102, 2018.
[23] Y. Drori. The exact information -base complexity of smooth convex minimization. Journal of Complexity, 39:1-16, 2017.
[24] Y. Drori and O. Shamir. The complexity of finding stationary points with stochastic gradient descent. International Conference on Machine Learning. 2020.
[25] Drori and A. Taylor. On the oracle complexity of smooth strongly convex minimization. Journal of Complexity, 68, 2022.
[26] Y. Drori and M. Teboulle. An optimal variant of Kelley's cutting-plane method. Mathematical Programming. 160( (0011-2):32133111 2016.
[27] M. Ermis, M. Park, and I. Yang. On Anderson acceleration for partially observable Markov decision processes. IEEE Conference on Decision and Control, 2021.
[28] M. Ermis and I. Yang. A3DQN: Adaptive Anderson acceleration for deep Q-networks. IEEE Symposium Series on Computational Intelligence, 2020.
[29] D. Ernst, P. Geurts, and L. Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 5:503-556, 2005.
[30] Ernst, M. Glavic, Geurts, and Wehenkel. Approximate value iteration in the reinforce- ment learning context. Application to electrical power system control. International Journal of Emerging Electric Power Systems, 3(1), 2005.
[31] A.m. Farahmand and M. Ghavamzadeh. PID accelerated value iteration algorithm. Interna- tional Conference Machine Learning, 2021.
[32] A.-m. Farahmand, C. Szepesvári, and R. Munos. Error propagation for approximate policy and value iteration. Neural Information Processing Systems, 2010.
11

---

[33] M. Fellows, K. Hartikainen, and S. Whiteson. Bayesian Bellman operators. Neural Information Processing Systems, 2021.
[34] M. Geist and B. Scherrer. Anderson acceleration for reinforcement learning. European Workshop on Reinforcement Learning, 2018.
[35] N. Golowich, S. Pattathil, C. Daskalakis, and A. Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. Conference on Learning Theory, 2020.
[36] J. Gordon. Stable function approximation in dynamic programming. International Confer- ence Machine Learning, 1995.
[37] V. Goyal and Grand-Clément. A first-order approach to accelerated value iteration. Opera- tions Research, 71(2)5117-335, 2022.
[38] J. Grand-Clément From convex optimization MDPs: A review of first-order, second-order and quasi-newton methods for MDPs. arXiv:2104.1061 2021.
[39] B. Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 73(6):957-961, 1967.
[40] R. Hannah, Y. Liu, D. O'Connor, and W. Yin. Breaking the span assumption yields fast iiite-sum minimization. Neural Information Processing Systems, 2018.
[41] M. Hessel, J. Modayil, H. Van Hasselt, T. Schaul, G. Ostrovski, W. Dabney, D. Horgan, B. Piot, M. Azar, and D. Silver. Rainbow: Combining improvements in deep reinforcement learning. Association for the Advancement of Artificial Intelligence, 2018.
[42] F. lutzeler and J. M. Hendrickx. A generic online acceleration scheme for optimization algorithms via relaxation and inertia. Optimization Methods and Software, 34(2):383-405, 2019.
[43] D. Kim. Accelerated proximal point method for maximally monotone operators. Mathematical Programming, 19):57777778 2021.
[44] D. Kim and A. Fessler. Optimized first-order methods for smooth convex minimization. Mathematical Programming, 159(1-2):11-107, 2016.
[45] D. Kim and J. Fessler. Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions. Journal of Optimization Theory and Applications, 189(1)1122-219 2021.
[46] J. Lee, C. Park, and E. K. Ryu. A geometric structure of acceleration and its role in making gradients small fast. Neural Information Processing Systems, 2021.
[47] S. Lee and D. Kim. Fast extra gradient methods for smooth structured nonconvex-noncoocave minimax problems. Neural Information Processing Systems, 2021.
[48] L. Leustean. Rates of asymptotic regularity for Halpern iterations of nonexpansive mappings. Journal of Universal Computer Science, 13(11):1600-161, 2007.
[49] F. Lieder. On the convergence rate of the Halpern-ieration. Optimization Letters, 15(2):405- 418, 2021.
[50] M. Lutter, S. Mannor, Peters, D. Fox, and A. Garg. Value iteration in continuous actions, states and time. International Conference on Machine Learning, 2021.
[51] P.-.. Maingé. Convergence theorems for inertial KM-type algorithms. Journal of Computa- tional and Applied Mathematics, 219(1):223-336, 2008
[52] A. massoud Farahmand, M. Ghavamzadeh, C. Szepesvári, and S. Mannor. Regularized fitted Q-iteration for planning in continuous-spac Markovian decision problems. American Control Conference, 2009.
12

---

[53] H. B. McMahan and G. J. Gordon. Fast exact planning in Markov decision processes. Interna- tional Conference on Automated Planning and Scheduling, 2005.
[54] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, King, D. Kumaran, Wierstra, S. Legg. and Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529-535 2015.
[55] A. W. Moore and C. G. Atkeson. Prioritized sweeping: Reinforcement learning with less data and less time. Machine Learning, 13:103-130, 1993.
[56] R. Munos. Error bounds for approximate value iteration. Association for the Advancement of Artificial Intelligence, 2005.
[57] R. Munos and C. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(27):815-88) 857, 2008
[58] A. S. Nemirovski. Information-basee complexity of linear operator equations. Journal of Complexity, 8(2)1153-175, 1992.
[59] Y. Nesterov. Lectures on Conver Optimization. Springer, 2nd edition, 2018.
[60] Y. Nesterov, Gasnikov, Guminov, and P. Dvurechensky. Primal-dual accelerated gradient methods with small-dimensional relaxation oracle. Optimization Methods and Software, 36(4):773-810 2021.
[61] Y. F. Nesterov. A method for solving the convex programming problem with convergence rate O(1 Doklady Akademii Nauk SSSR, 269(3)5433-577, 1983.
[62] S. Niu, S. Chen, H. Guo, C. Targonski, M. Smith, and J. Kovačević. Generalized value iteration networks: Life beyond lattices. Association for the Advancement of Artificial Intelligence, 2018.
[63] C. Nota and Thomas. the policy gradient a gradient? International Conference on Autonomous Agents and Multiagent Systems, 2020.
[64] C. Park, J. Park, and E. K. Ryu. Factor- acceleration of accelerated gradient methods. Applied Mathematics & Optimization, 2023.
[65] J. Park and E. K. Ryu. Exact optimal accelerated complexity for fixed-point iterations. International Conference on Machine Learning, 2022.
[66] J. Park and E. K. Ryu. Accelerated infeasibility detection of constrained optimization and fixed- -oint iterations. International Conference on Machine Learning. 2023.
[67] M. Park, J. Shin, and I. Yang. Anderson acceleration for partially observable Markov decision processes: A maximum entropy approach. arXiv:2211.14998 2022.
[68] J. Peng and R. J. Williams. Efficient learning and planning within the Dyna framework. Adaptive Behavior, 1(4):437-454, 1993.
[69] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 1994.
[70] S. Reich. Strong convergence theorems for resolvents of accretive operators in Banach spaces. Journal of Mathematical Analysis and Applications, 75(1):287-292. 1980.
[71] E. K. Ryu, K. Yuan, and W. Yin. Ode analysis of stochastic gradient methods with optimism and anchoring for minimax problems. 1rXiv: 10899, 2019.
[72] S. Sabach and Shtern. A first order method for solving convex bilevel optimization problems. SIAM Journal Optimization, 27(2):640-660, 2017.
[73] A. Salim, L. Condat, D. Kovalev, and P. Richtárik. An optimal algorithm for strongly convex minimization under affine constraints. International Conference on Artificial Intelligence and Statistics, 2022.
13

---

[74] D. Scieur, A. d' Aspremont, and F. Bach. Regularized nonlinear acceleration. Mathematical Programming, 179(1-2):47-83, 2020.
[75] Shehu. Convergence rate analysis of inertial Krasnoselskii Mann type iteration with applications. Numerical Functional Analysis and Optimization, 39(10):0077-1091 2018.
[76] W. Shi, Song, H. Wu, Y.-C. Hsu, C. Wu, and G. Huang. Regularized Anderson acceleration for off-policy deep reinforcement learning. Neural Information Processing Systems, 2019.
[77] O. Shlakhter, C.-G. Lee, D. Khmelev, and N. Jaber. Acceleration operators in the value iteration algorithms for Markov decision processes. Operations Research, 58(1):193-002, 2010.
[78] J. J. Suh, J. Park, and E. K. Ryu. Continuous-tine analysis of anchor acceleration. Neural Information Processing Systems, 2023.
[79] Sun, Y. Wang. Y. Liu, B. Pan, S. Jui, B. Jiang, L. Kong, al. Damped Anderson mixing for deep reinforcement learning: Acceleration, convergence, and stabilization. Neural Information Processing Systems, 2021.
[80] R. S. Sutton, Learning to predict by the methods of temporal differences. Machine Learning. 3:9 44, 1988.
[81] S. Sutton and G. Barto. Reinforcement Learning: An introduction. MIT press, 2nd edition, 2018.
[82] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for rein- forcement learning with function approximation. Neural Information Processing Systems, 1999.
[83] Q. Sykora, M. Ren, and R. Urtasun. Multi-agent routing value iteration network. International Conference on Machine Learning, 2020.
[84] C. Szeeessári. Algorithms for Reinforcement Learning. Springer, 1st edition, 2010.
[85] A. Tamar, Y. Wu, G. Thomas, S. Levine, and P. Abbeel. Value iteration networks. Neural Information Processing Systems, 2016.
[86] Taylor and Drori. An optimal gradient method for smooth strongly convex minimization. Mathematical Programming, 199(1-2):577-94, 2023.
[87] S. Tosatto, M. Pirotta, C. d' d'Eamo, and M. Restelli. Boosted fitted Q-iteration. International Conference on Machine Learning, 2017.
[88] J. N. Tsitsiklis. Asynchronous stochastic approximation and Q-learning. Machine Learning. 16: 185-222 1994.
[89] H. Van Hasselt, A. Guez, and D. Silver. Deep reinforcement learning with double Q-learning. Association for the Advancement of Artificial Intelligence, 2016.
[90] Van Roy. Performance loss bounds for approximate value iteration with state aggregation. Mathematics of Operations Research, (1(2):234 -222244444444 2006.
[91] B. Van Scoy, R. A. Freeman, and K. M. Lynch. The fastest known globally convergent first-order method for minimizing strongly convex functions. IEEE Control Systems Letters, 2(1):49-54, 2018
[92] N. Vieillard, Scherrer, O. Pietquin, and M. Geist. Momentum in reinforcement learning. International Conference on Artificial Intelligence and Statistics, 2020.
[93] H. F. Walker and P. Ni. Anderson acceleration for fixed-point iterations. SIAM Journal Numerical Analysis, 49(4):1755-1735, 201
[94] C. J. Watkins and P. Dayan. Q-learning, Machine Learning, 8:279-292, 1992.
14

---

[95] D. Wingate, K. D. Seppi, and S. Mahadevan. Prioritization methods for accelerating MDP solvers. Journal of Machine Learning Research, 6(25):851-81) 2005.
[96] Wittmann. Approximation of fixed points nonexpansive mappings. Archiv der Mathe- matik, 58(5):88-491, 1992.
[97] H.-K. Xu. Iterative algorithms for nonlinear operators. Journal of the London Mathematical Society, (6(1))240-22)) 256,,02-6,6660 2002.
[98] T. Yoon and F. K. Ryu. Accelerated algorithms for smooth convex-coneave minimax problems with (11/k²) rate on squared gradient norm. International Conference on Machine Learning. 2021.
[99] T. Yoon and E. K. Ryu. Accelerated minimax algorithms flock together. arXiv:2205.1109: 2022.
[100] Y. Zeng, F. Feng, and W. Yin. AsyncQVI: Asynchronous-parallee Q-value iteration for discounted Markov decision processes with near-optimal sample complexity. International Conference on Artificial Intelligence and Statistics, 2020.
[101] J. Zhang, B. O'Donoghue, and S. Boyd. Globally convergent type-I Anderson acceleration for nonsmooth fixed-point iterations. SIAM Journal Optimization, 30(4):3170-3197 2020.
[102] K. Zhou, L. Tian, A. M.-C. So, and J. Cheng. Practical schemes for finding near-stationary points of convex finite-sums, International Conference on Artificial Intelligence and Statistics, 2022.
15

---

A Preliminaries
For notational unity, we use the symbol U when both V and Q can be used.
Lemma 1. [10, Lemma 1.1.1] Let < 7 S 1. Uf S U, then U < STÜ, TU & T Lemma 2. Let < S 1. For any policy x, p is a nonexpansive linear operator such that if U U.Ü P-U & PrU.
Proof. If r(s, a) = 0 for all s E S and a E A. = yPx Then by Lemma 1 and y-contraction of TE, we have the desired result.
Lemma 3. Let 0 < < Let and T' respectively be the Bellman optimality and anti-optimality operators. Let U* and Ü respectively be the fixed points of T and T Then Ü - U
Proof. By definition, Ü+ = - s ÚT" Thus, Ú+ I limm-+s (T*)
0+ U*
B Omitted proofs in Section 2
First, we prove the following lemma by induction.
Lemma 4. Ler < S L, and if 1. assume a fixed point U exists. For iterates U h=-0..... of Anc-VI,
(3: - -3-1 - ())) (U) 8,)) (1/T)) (U" - U²) U U* Σ
i=1
- 3 U²) + (m) (1 3,)) (yp=) (v -U")
where (1)= 8,) and 30 =
Proof. If k O, we have
TO - U = T U - -U00 - U*)
UT U -U' U?)
7p" (U U*) (U" U*)
If k m. since T is a linear operator,
T LT = Tm - (1 Bm) Um1 Bm
T (1 Bm) Um Bm UH 3m (U - U²
T (1 TTT U Tm T U 8m -
7P" (UTh (1 Bm Um " (U )T²
(P (U U²) + (I "m - (m- )) Bm -U0- 17)
m-1
(1 Bmh Σ
[B) 11---111111 - -))
(117-11 (1 B,)) (yp=ym-11-)) (Uo Um)
- (1 Bm) 1px 3m (U - )T7 + (1 - Bm (11=7 - -zj)) (>p") (00 - -
+ Bm (00ppx((' (1 - (U - -U")
Σ (Bi Bi-1(1 Bi)) (117 (1 - -Bj)) (1p=)m-itt) (U -Um]
8m-1(1 yp (U" - - + Bmypp= -U*)
3m - U²) + (117= - By)) (xpr)mt m+1 (U - (²)
16

---

Σ (B: 1i-1(1 - B:)) (TT=+41 33)) (1pr)) (U (00-U7)
Bm - -U*) + (T j=1 (1 - -33)) (xpp)) (U= - -
Now, we prove the first rate of Theorem 1.
Proof first rate in Theorem 1. Taking I1-11so-
-norm -norm both sides of equality in Lemma 4, we get
U -U* 1 S
18 - 3 - Be)l (1f)=-=10) - -3,)) || it1 (U0 Un) Σ
1=1
+ 3x 10000 - -0²1 101100 + (mi - B:))) (Tppt (vo - (xm)
x-
1 - -3) ( (1 - B,)) + Br + II -- (1 (8))
1100 -U'
h
-ti-l (1 g1-
1 1- g-
+ + k+1 1 1²
+ 77th
1100 - -001 1 1- 2x+2
1- 7(122))2
1 1- 2k+22
7) (1 + 27 - 1)
|0000 U+ 11
())+1) gh+
where the first inequality comes from triangular inequality, second inequality is from Lemma 2, and equality come from calculations.
For the second rate of Theorem 1, we introduce following lemma.
Lemma 5. Let 0 < 7 < 1. Let T be Bellman consistency or optimality operator. For the iterates
(U*) k=0.1.... of VI, U < TU then Uk-1 S U2 TUp-1 S TU $ U for 1 & k. Also, if
T TU", then -k-1 2 Uk 2 TU 2 TU 2 U for 1 S k.
Proof. First, let U < TU k 1, U < R + (1 8 T = U1 < TU by assumption. Since U S TU < TU by monotonicity of Bellman consistency and optimality operators.
By induction,
U* 0RU (1 ---BJTTU-- < T
and since Bx S Bk-
BRU + +11 -1)--TTU 2 0k + (1 - Bx -TU
2 00 + (1
11-1) T
U
Also, Uk-1 < U* implies T < TU by monotonicity of Bellman consistency and optimality operators, and U < TUk implies that & < limm- (T) U U for all I,
Now, suppose U > TU If k = 1, U 2 9,00 + +(1 - 31 YTU = U2 2 TU by assumption. Since U 2 U., TU > TU' by monotonicity of Bellman consistency and optimality operators.
By induction.
U* B2U (1 (-BB)TUU-- > (1=B)IT++TTT
TUK-1
and since 3% S Bk-1,
A&U0 + (1 -1-Ban -Be)TUU S S + (1 - 11-Bk-1)TU-+1
S U0 + (1 - -T-
= Uk-
17

---

Also, Uk-1 2 U implies TUk-1 2 TU by monotonicity of Bellman consistency and optimality operators, and Us T implies that U limm- (T) t U** for all k 0, I....
Now, we prove following key lemmas.
Lemma Let 0 < < S 1, and assume a fixed point U exists i = 1. For the iterates {U j,
of Anc-VI, VI, U < U
k
U U² 1
Σ (B: 18:4-33-106
3:-1(11 (1)1-)))) 8:)) (15- - -3)) (yp=nbbitt k-itt (U - -U*)
i=1
- -x((U00 -
where (TH= 11--8)) 83)) and 90 1.
Lemma 7. Let < < 1. For the iterates (U* Jk= Af ifU 2 TOU
T U² 2
Σ
[19: - -----111111111 - -3)) (1) - -3,)) (xpar) (00 -U7)
i=1
- 3v -
where (11=*+1(1- (1-x41(1-811) -,)) and 30
Proof of Lemma 6. U < U we get
U -K Σ (9, Bi-1(1 (3)) (1)= (1)) (ypor)--tt) (w0 Un)
- -A U*) + (n) - (1 - B,)) (yppoytt1 k++ (00-U)) - -
Σ [8. - B,-1(1 3.)) (1) (1 Bz)) (ypor (w -00 [r) - -Ba(U0 -
by Lemma 4 and the fact that (I), B,)) (ypr)htl k+l -U--U-) -00 S..
Proof of Lemma 7. U 2 TUO, U U² by Lemma 5. Hence, by Lemma 4, we have
k
U U 2 Σ
(B, - Bi-1(1 (1)) (1 - B,)) (1ppr) (v um] -Ba(U" - -U*),
i=1
since 0 < (1 - B,)) (1t
Now, we prove the second rates of Theorem 1.
Proof of second rates in Theorem I. Let 0 < y 1. By Lemma if 5, < T then U Ua. Hence,
0 < T U U
[B. - (1-1(1-B1) (11 (1 (1- (00,,,))) B,)) (1ppr)--at) kit1 (vo (w--U")
--(U0-
by Lemma 6. Taking ||.11.0 -norm both sides, we have
U 10 5 (x-1-m) (1 + xk+l)
1 - U 10
(1++1) x+1
18

---

Otherwise, u 2 TU, "UO,U" U 2 TUk by Lemma 5. Since
0 2 T- -1²
(B: -i-- -1-) (1 -3)) (x (0o (00-Um) un] -B: - U²).
by Lemma 7, taking I1-11 -nom both sides, we obtain same rate as before. Lastly, Taylor series expansion for both rates at y = is
(7 - 7) (1+ 2% 7112
2
k
- 1) O((7 1))3,
(n,+t)) -/t11
k + 1
k + 1
(y-1 - -)) (1+ 7 - 7
1
k
(7 + O((7 (1))-
(xk+2) ( -kt
k +
k +
For the analyses of Anc-VI for Bellman optimality operator, we first prove following two lemmas.
Lemma 8. Let 0 < < 1. If 1, assume fixed point U exists. Then, if S S and
U - (1- a) aU* < U, there exist nonexpansive lineur operator Pn such that
TU (1-4) - SPPHU.
Lemma 9. Let 0 7 1 a S and Ú < - -a)ū at*, then there exist
nonexpansive linear operator PH such that
PP STU - -1- a)
and V Proof of Lemma 8. First, let U V,Ū V, and action space is finite,
a)j aV* <V.
-V -1- aT' <TV (1 a) V
=pp (v- (1 - -Vv") av))
S Sypev
where π is the greedy policy satisfying T"V = T first inequality is from T < T and TVV* TVV* and second inequality comes from Lemma 1. Thus, conclude PH pr.
Otherwise, if action space infinite, define P(cV) csupses V(s) for e E and previously given V. Let M be linear space spanned by V with ll Then, P is linear functional M and Plopp
since lesup.es V(s]
< Due Hahn-Banace extension Theorem, there exist
|
1|-
linear functional Pa: F(S) R with PV(V) sup V(s) and ||Pallop < 1. Furthermore, we can define Pr:: F(S) - F(S) such that Vs) = (V) for s E S. Then, since ((PH(V) [Ph(V)] < ||Palop for Vl I 1, we have PHlloc < 1. Therefore, PH is
19

---

nonexpansive linear operator in |1-1 norm. Then,
(V)(s) - (1 - Vs) as)
((s, + P (s,0) [V(')] }
(1--))(6:0)(11-))))) p( [+(0)]
= =sup aed
sup aEd
ar((s 1pp (6') (V
sup aEd
I sup aEA
r(() a) + +
[[(s]]] (1 - -)) - (1)))))) [[(0]]
ar(s.a) + an
sup acA
Eg 11 (V('') - -1- -1-)
sup aEA
S y sup (V(s') - -11 (1-)) E'E
Y sup (ss).. dEES
for all s E S. Therefore, we have
TVV - (1 - a - aT' spPP))
Similarly, let U U- - Q, =0- =0 and Q (1 - a) =aQ² S SQ.
If action space is finite,
TQQ - (1 a1- aT Q² S 7pp" (Q- (1 (1- - -aQ2 aQr)
S <Sp' Q
where it is the greedy policy satisfying T*Q = T,Q, first inequality is from T S T Q and T=" S TTQ", and second inequality comes from Lemma 1. Then, we can conclude PH = PT.
Otherwise, if action space is infinite, define P(cQ) = csup a') Q(5', a²) for E IR and previously given Q. Let M be linear space spanned by Q with |1-11 -norm. Then, P is linear func- tional on M and ||Pl|op S 1. Due to Banach extension Theorem, there exist linear functional X A) + R with (Q) = sup(r","))ss) x') ( Q(s', a') and IP lop S 1. Furthermore, we can define Pr: F(S x A) + FFSS x A) such that PsrQ(s a) = (Q) for all (s, E S x A and -norm. Then,
|| I 1. Therefore, Py nonexpansive linear operator in -l-ro.--nomm
(*((s, - (1 a)' aT"
=r(s,a) + 77E.NP( 1.,0)
sup Q(d',a') a²) -Q1 -(1-a)r(s,a)- - ((p((s)))-(laaaaa))a a) sup (()' L'EA
a'EAA
-ar(s,a) B7..s-((1ee))
sup
0'(6'a0)
L'EA
{Q(s' a') (1 -1- a)((s)a()3 -BBonPt s,a) sup dEA
sup aQ((ssa')
Lo'EA
sup {0(6', a') (1 (1-a) - aQ (6',)) (Q(s' - (1 -1=)))(510))-00((550000)
S2 sup (d(x')
Sy (W)')
sup
Q(s'aa')
for all (s,a) E S x A. Therefore, we have
T - (1--(1-a)0) Q
QT=QQ {P)
20

---

Proof of Lemma 9. Note that 1* is Bellman anti-optimality operators for V or Q. and Ü+ is the fixed point of T*. First, let U- = V = = = V. and V S V - (1 a)V aV Then,
(*)()) - (1-
+ [V(')) / aEA
sup (1 (1-,))( + (1 Ba--aa)Esppiie [V(5)]] }
= =sup
+on5s.0)+ [m())]}
- inf aEA
((().)++ + 7 [Vs']] (1 - a))(s,a) (1 - a)yBB.m (s)a) [((')]
2 inf aeA
ar(s. + 11))) [
inf aEA
Eg [s,a) - (1 a)) (1=0
Yy inf aEAA
Then, if action space is finite,
TV - (1 -1- a 2 7Pa (V (1- - -av+)
2 yD²
where े is the policy satisfying #- |s) argmin P (s,a] V(s') -1- -1))))))- and second inequality comes from Lemma 1. Thus, we can conclude P11 p
Otherwise, if action space is infinite, define P(cV) = cinf (s) for c E R and previously given V. Let M be linear space spanned by V with
Then, P is linear functional on M and ||p1lop I 1 since jeinf.es (s)] < 1. Due to Hahn -anach extension Theorem, there exist linear ||el|
functional PA: F(S) + R with (V) = infaes (s) and |Pallop I 1. Furthermore, we can define PH: F(S) + F(S) such that PHV = PV) for all E S. Then |/ < 1 since [V) [V)(V) < [P llop S for VV S 1. Thus, PH is nonexpansive linear operator
in |1 -norm. Then, we have
(s) - (1- (1-)) of 2
inf aEd
Ey (g-r((ls)) [V(()) - (1 ())) - (1
2 7 inl (V(s') (1--)
d'ES
2 inf (V('))
SEES
for all S. Therefore, we have
-( af**
Similarly, let -:tp:aaheUUu------.-::::0000,010 and Q=Q (1-a)@ aQ", Then,
Q(s' ot) (1- - ((1-a)))s))-11-))))))))-1---- a) ~p( (((a))) sup @(s' LA'EA
+ (1s,a))+BB.nP(11111
sup L'EA
-ar(s,a)- ar a7BaNP(-1e.)
inf (7)))a)) a'EA
{Q(s',0)) - (1 inf d'Ed e)((s.)))) ( --BawP(- sa))
iuf aQ(s',a) ,a)) a'ed
inf ((((' (1 - a)((s',)) ( deAl
21

---

Hence, if action space is finite,
TQQ - (10-(1a))---od - aT 2 ypa
(1- aQQ)).
2 >ppa Q
where स is the policy satisfying #(- [s) argmin P P(. | [Q(')) - (1 -1a)) and second inequality comes from Lemma 1. Then, we can conclude P/ = =
Otherwise, if action space is infinite, define P(c(2) = cinf Qs' a') for c E R" and previously given Q. Let M be linear space spanned by Q with |1-11 norm. Then, P is linear func- tional on M with || 1. Due Hahn- extension Theorem, there exist linear functional Pr: PRS x A) + with Pa (Q) = (r Q(s', a') and ||P S 1. Furthermore, we can define PH: F(S A) F(S A) such that ( a) (Q( for all (s, S x A and
|| llo S Thus PH nonexpansive linear operator 11 noom. Then, we have
T*)(s, aT a) - (1 Q))
inf a'EA { {Q a') (1 a)(((')()))))))))))) d)) - .0)
2 yB BBB-Ptt-
27 inf
{Q(s' d') (1 (1- (11 al)
(
27 (x)x Q(',a'))
inf
for all (8, ESX A. Therefore, we have
( Q'*Q"
Now, we present our key lemmas for the first rate of Theorem 2.
Lemma 10. Let 0 < If7 1, assume a fixed point U exists. For the iterates {Uk} o, of Anc-Vi, there exist nonexpansive linear operators 1P0,1_0,,.... such that
(U) T*U - Uh Σ [(3, Bp-1(1 -31) (II (1 (1)) (V= U
i=1
- -Bu(U0) - -U*) + +11 - (1-1,)) (IPWYP') (U" - -U*
where 11/: k+1 (1 BB) = and Bo 1.
Lemma 11. Let < < 1. For the iterates (U* Ik=.. of Ane- VI, there exist nonexpansive linear
operators (p")t=,,1,.... such that
[Bt - (36-B:-1(1 - 3:)) (11 (1- B,)) (Mi (UO (10- -Un] T - 2
Σ
i=1
- OU0 - -i-) + (1) - 8,)) (u (vo - -U-,,
where IT. = (1 B,) = and Bo 1.
We prove previous lemmas by induction.
Proof of Lemma 10. If k 0,
T U T U (v - U²)
= - U² - (U U³)
S (PO - -U*) - (U" - -U))
22

---

where inequality comes from first inequality in Lemma 8 with a 1,U = U0, = = - - By induction,
U (1- 3,) PLU*
= 3k (U" - U*) + +1 -
k-1
< (1 - Bx) Σ
[[B: - -B:-111 - B.)) (11= (1 - -3;)) (Li=k-17P)) (0" Un]]
i=1
(1 (1- Bk) U*) (1 B&) (m)=l 8,)) (MP= (U0 U
+ -U*
and let U be the entire right hand side of inequality. Then, we have
T* - 1h
= U - (1 - Ba)TT 32U0
= U - (1 B,)TT 3rU - Bu(UU - U*)
U - (1 B U² -3((U0 - U*)
U
5yph (1- 3x) Σ [[0. 31-1(1 B)) (u (1- (1)) (Hi=)-17P)) (00 UU)]
-(1 -1- -11-Be)3 11 - U²) + (1-
- Ba) (m) - 8,)) (TH (T== (T0 -U*)
+ 1000 (0(000-1)) 011 - 3U0 -00-0" -
Σ [B: Bi-1 B:)) -1 (1)) (T=x)P') -U)
Bk-1 Ba) (UO U²) + Bky (U"- - -U*)
Pe - U*) + (1)= (1 - -Ba)) (IP_ (U - U**)
Σ [B: B (1 (.)) (1)) - BB)) (TT) (UO - -U*)
- PU U*) + (M (1 - 3,)) (ML (Uo -U*).
where inequality comes from first inequality in Lemma 8 with a Bk, U U² U U and previously defined Ú.
Proof of Lemma 11. Note that 7 is Bellman anti-optimality operators for V or Q, and Ú- is the fixed point of T* If k = 0,
TUU - =T*000 - -+- (U - Ūn) =T - - -U0 0')
2 2U -oa) - (U" (10--i- (n).
where inequality comes from second inequality in Lemma 9 with 1,U = Uº, U 00-07 -
23

---

By induction,
U² - (1 U =220"*
-U0 Ún) (1 (a)(TTU---UU -
R-1
2 (1 - )x)
Σ
(B: - -B--1(1 - -B)) (1 - -;)) ( (Mix--171)) (10 -Uy)
i=1
- (L - 3x) - 0+)+ + (1- (1 - -1))) (ub-a- (1) - 04)
+ BB((U0 - (*), -
and let U be the entire right hand side of inequality. Then, we have
T - -Uk
= - (1 - BB) - BLU
U (1 BATTT* Uk- BB8 Bu - -0)
-T (1 - BT) - -Be - Ba (U0 - +.
1-1
2 2TR (a- Bkk)
Σ
[A: Bi- - -a)) (18= (1 - -B²)) (T (v" - -mm]
i=1
-(1 - -kx) - - + 3a) (1)) (B)) (T (100))))))(0-00) ty)
+ +B - -t:)) -e - it)
k-1
Σ (8. BI-1 3e)) (TT) (1 (1)) (MixsTDi) (00 -t)]
-k-1 - (a) (U Ú+) + BaTPe
1u - Ū+)== + (II B,)) (IP (UO- ('))
Σ [(8: - B1- - 8.)) (1)
- (1 - BB)) (II (DD) (00 -to]
3x - i+) + (1) (1- B,)) (ME (UO -
where inequality comes from second inequality in Lemma 9 with a Br, U U² Ú UK-1 and previously defined U.
Now, we prove the first rate of Theorem 2.
24

---

Proof first rate in Theorem 2. Since B1 S A Bg implies ||A|| I |
o2 for
A, B E F(X). if we take Il right side first inequality of Lemma 10, we have
|8c 3--1(1 3:)1 (T (1 (1 - 8,)) ||( (PT) (U" -
+ Bk 1100 10 + (TH (1 - -B,)) || (Ti=+>>' (Ur0 - -U*)
x 13x - 11 - Bi) (T (1)= -B3) + 3h + + + = (1 - B3))
1
U²
(7-1 7) (1 - gttl)
1100 U² 1o
(7++1) ( gk+
where the first inequality comes from triangular inequality, second inequality is from nonexpansive- ness of pl, and last equality comes from calculations.
If we take I1 right side of second inequality of Lemma 10, similarly, we have
Σ |84 31-1 3e) (1)-++ (1 - 3,)) (T" (0 -00- |1
+ BB 1000 -U² (T (1 B3)) (TTE (00 - -try 8
k
Σ 1 k-it1 13, - 3/-- - -3:1 (II 8j)) + 3x + + - 13))
13,-3:-1(
7) (1 + 27 - 2b
|000 t
()*+1) g
where the first inequality comes from triangular inequality, second inequality is from from nonexpan- siveness of Pl, and last equality comes from calculations. Therefore, we conclude
T - 1 S (x- 7) (1 + 27 7 x+1)
max |100 - U 20 1
-
600
())++))- xk41
Next, for the second rate in Theorem 2, we prove following lemmas by induction.
Lemma 12. Let 0 < S 1. If- 1, assume a fixed point U* exists. For the iterates {U*) } 0,
of Anc-VV, TfT U < U*, there exist nonexpansive linear operators {PD) (P",,=0,,..... such
such that
k
T*T Th <
Σ
[(3, 11-1 BB)) (T) (1 - -8)) (TE))P')) (U0 - Um-] - - U+)
1=1
where l - 33) = and Bo 1.
Lemma 13. Let 0 < 7 < 1. For the iterates { of Anc- VI, Uf 2 TUU there exist nonexpansive linear operators (D.).=0,1..... such that
T Th Σ i=1
(Bs 3,-1 -3)) (II 11 -B)) (TiasTDt) (10 (00-tr)) -t"),
where II = (1 BB) = and Bo 1
Proof of Lemma 12. If kf = O,
U - 10 = T - U¹ - (U) - -U")
S < - -U*)
25

---

where the second inequality is from the condition. By induction,
U -0--1- (1 - Bx) 8x) BBU*
h-1
< (1 3x) Σ [(3: (1- Bi)) (1 (1 B3)) (ui= (00
(1 3x) U*) + 3x000 -U*) U*),
and let U be the entire right hand side of inequality. Then, we have
T* t
- -11 1
k-1
I sxpt (1 (1 3x)
[B: - Bi-1 - -Bi) (T (1= - (1-3)) 17)) U*) Σ
d=1
- (1 - -Bx) (U - U²) + (t0 (00) - -3a -U*)
Σ [[B, -1- (:)) (1 B3)) (IE (10 - -U*)] - -Ba(U--U")
- _U),
where inequality comes from first inequality in Lemma 8 with a Ba, U Uk U UK-1, and previously defined U.
Proof of Lemma 13. If k O,
T - T -
--- (U" U+)
2 - -
where the second inequality is from the fact that 1 2 T implics T 2 U by Lemma 5 and U* 2 t by Lemma 3.
By induction,
U (1 -
- -Ba0
2 (1 - 3x) Σ (3. -B,-111 B.)) (1 8,)) (Ul) (00-0*) [n)]
- (1 100 - -Ò²) + (u - Ú*),
and let 0 be the entire right hand side of inequality. Then, we have
T U
- -B -0-) = - -118)-
k-1
2 2ppl (1- 3x) Σ
(B: 11-1 (1a) (11- (1 (BB))) (ME -
1=1
-(1 - -B 1700 - + - (T,)) - -Ba(T0- - -b+)
Σ (B, Bi- - 3.)) I1) - (1 (1---)) BB)) (DD) (00 -tr] - -B - -Ūx).
where inequality comes from second inequality in Lemma with a Br, U = U/ Ú - and previously defined U.
26

---

Now, we prove the second rates of Theorem 2.
Proof of second rates in Theorem 2. Let < 7 < Then, if U I T then T I U* and U UK by Lemma 5, Hence, taking |1 -norm both sides of first inequality in Lemma 12, we have
T - U (x (r'1-)) y
1 U* 11
(gb+1) - 7
Otherwise, if U 2 TU Uhe 2 TU* by Lemma 5. taking Inorm both sides of second inequality Lemma 13, we have
T - 1 S (--1- -)) (1 + - 1
100 100-0-
(gtt2) -kt1
C Omitted proofs in Section 3
First, present the following lemma. Lemma 14. Let y 1. Assume a fixed point U* exists. For the iterates {U" Ik=u.1... of Anc- VI,
| -+ $ | - -
Proof. If = 0, is obvious. By induction,
1 - U0 = || T + (1 - -c)
[|(1 (TU
- U*) + 3s (U U*) x
I (1 3x) T
+ + 100 1
(1 3x) | U
- 11 fx 1 - U*|
| U+|
where the second inequality comes form nonexpansiveness of T.
Now, we present the proof of Theorem 3.
Proof of Theorem 3. First, if U < TU with same argument in proof of Lemma we can show that U < U < TU < T for k = 1,2,....
Since fixed point U* exists by assumption, Lemma 4 and 10 hold. Note that y implies 3* 1 and if we take |I.Ila.-nom -norm both sides for those inequalities in lemmas, by simple calculation, we have
||TU* 10
k k 1100 - -U*l
for any fixed point U* (since 0 < T Uk can get upper bound of ||TUk U²* from Lemma 10).
Suppose that there exist j= such that UAs converges to some Ü+ Then, lim (T TyU*, = T)Ü = 0 since T 7 continuous. This implies that Ü is fixed point. By Lemma 14 and previous argument, U is increasing and bounded sequence in R.. Thus, & has single limit point, some fixed point Ü Furthermore, the fact that U < TU Ü implies that Lemma 6 and 12 hold. Therefore, we have
I Ub
1
17
k+1
Next, prove the Theorem 4.
27

---

Proof of Theorem 4. By same argument in the proof of Theorem 3, U S TU we can show that U I U TT TU for 1, ..... and
|rU* - 1 S k k+1 1100-07
for any fixed point U*, Since U is increasing and bounded by Lemma 14 and previous argument, U converges pointwise to some Ü* in general action-state space. We now show that TU* also
converges pointwise to TÜ* First, let be Bellman consistency operator and U V. Ü V* By monontone convergence theorem,
lim T (*) = lim (awn(-1a) [Eg [ +V
k k+200
koo00
lim Bsr (r(s,a) + 7V (
= 1ssa(
k-000
(e/nP(-13.a) r(s,a) + lim v* k000
= =S*V=(s)
for any fixed S. With same argument, case U = Q also holds. If T is Bellman optimality operator, use following lemma.
Lemma 15. Let W, W F(X) for I,... If (x)) S Wk+l(x) for all x X, and (W*) k converge pointwise to W, then lim (sup, W (*(x)] sup, (xx).
Proof. (*)) W(x) implies that sup, (*(x) sup, W(x). If sup, W(x) a, there exist which satisfying (z) < and by definition of W, there exist W such that (*()) < for any c > 0.
If = and Ü+ V* by previous lemma and monotone convergence theorem, we have
lim (s) lim sup (By~P()1s.)) [r(s, +V+))))+++)))
k0000
1000
lim EgsP(- [r(s,a) + [ k+0
sup
sup BeNP(-la,a) ((0,a) + lim V*('')
k
(s)((ss)
for any fixed E With similar argument, case U = Q also holds.
Since T T and t - Ú* pointwisely, TU* U converges pointwise to TÜ Ū 0. Thus, Ü* is indeed fixed point of Furthermore, the f'at that U TU < Ü implies that Lemma 6 and 12 hold. Therefore, we have
| - 11 S $ U0 | 0+1
D Omitted proofs in Section 4
We present the proof of Theorem 5.
Proof of Theorem 5. First, we prove the case U 0 for k+2. Consider the MDP (S, P,r,y) such that
S = {51 } A taih. P(s: 83, 01) ) = ((==)_1j= r(s,,
= 1 (i=2).
Then, = TP= + J0, 1, 0, 0,,, U = 10, ",..,..,"-33) and ||00 - U' = Under the
span condition, show that (U*), (U*), = 0 for k + < 15 by following lemma.
28

---

Lemma 16. Let T: I=" + I= be defined as before. Then, under span condition, (U*); = for 0 Osis k, and (U*),= 0 for 0 < i S k and S j S
Proof. Case k = 0 is obvious. By induction, (U") = 0 for 0 < Then (TU*) = 0 for 0 S I 1. This implies that (TU' U²), = for 0 - Hence (U"), (U") Again, by induction, (U"), = for 0 < 1 --,,,,2,,222
Then (TU"), = for 0 < S i-1,
I 3 j S n and this implies that -U*) for 11si-1,1+ 35335 j j S n. Therefore, (U'), for S
Then, we get
TUK U = -00 27 - (U*))...... (7*) (U*) k+1 77 (U+)&o)
k+l 0
k-
and this implies
- + (TU -U*) +... 1..... (TU* Ub) k+2
Taking the absolute value on both sides,
(1 +1+
max { k - 1b 21. I8i5n
Therefore, we conclude
* Σ 7 |100 - -o
I - 1l
Now, we show that for any initial point U RR. there exists an MDP which exhibits same lower bound with the case U = O. Denote by MDP(0) and To the worst-case MDP and Bellman consistency or opitmality operator constructed for U = 0. Define an MDP(U") (8, A, P,r,)) for U o 0 as
S = ( }n), A = { P(x: 85, a1) = 1 (====,,==++); r(8;, a1) - (U0-P"U") + 1l (1=2)-
Then, Bellman consistency or optimality operator T satisfies
TU To(U ( + U
Let Ü* be fixed point of To. Then, i = UU, U is fixed point of T. Furthermore, if {U*) == satisfies span condition
U' U spon U TU' 1 U²_ U'....,,TT ...., -U--)
i 1, I....,k.
U = Ui - U is sequence satisfying
Ü+ To tspon ū TūÜ U1 - i
which is the same span condition in Theorem 5 with respect to Tp. This is because
TU U TU - UU) (U² - U T T+
for = O...., k. Thus, ( is a sequence starting from 0 and satisfy the span condition for To- This implies that
ITU Uk 110 = || 0A/
gk
100
8
Eimo 7á
1
U*
E
Hence, MDP(U") is indeed our desired worst-case instance. Lastly, the fact that U - U to -U = -00 1, 1,7 2-2) implies 1 < U.
29

---

E Omitted proofs in Section 5
First, we prove following key lemma.
Lemma 17. Let 0 < < 1. For the iterates (Uh Ik=0, Ane- VI, there exist nonexpansive linear operators (P"):=0,.... I...k and (P) ):00,..... such that
k
T* U/
[(3 - 3 3.)) (1I (11= - B,)) (II)) - - -U0 1x(00-U1
+ 11==11 (1 - -8) (U (10 -U*) - *
Σ m1 - B3 m (1- - -ppt)
im1
k
T - 0²
(8) 3:-1 (3)) (11=itt(1-BB)) (Hi=s (0" - - - -Ba(U0 -0n)
(00-
i=1
+ +1 By) - 0.) - Σ (1 B,) (1-ypi) e
for 1 S k. where IT: -1 (1 (1- = (1))))
B3)
hp' - y I, and Bo 1.
Proof of Lemma 17. First, we prove the first inequality in Lemma 17 by induction.
If k 1,
U²_ - (1- -BIU== = (1 (1-B))++ + +8 - -1)+ -0))
S (1- (1 + + 11 (1) (23: - 1)
where inequality comes from Lemma 8 with a = L,U = U0,0 "0- U U and let U be the entire right hand side of inequality. Then, we have
TT - U = T - - -3)T7 - 310 - 31 - U - - 31-
S ((P- -
+ (1-3))pp' U')) + (23) - 1)(U0= - -U*)) - -1 - -U)
- (1 -3:)c
- U + +P8 - 1) - - - - -0,(0-- -U*) (1 (T (T-1P')(1 31)6
where inequality comes from Lemma 8 with = -U,UU = U ú = Uo and previously defined U.
By induction.
U (1 -
= B (UO- - -U+) + +1
U + (1- - *
< (1 - -3x) k-1
[B: - -3: - (3)) (1/= (1 -1-1000 3,)) (1i= (v UU)]
- -11-3) Ba) U*) + (1 - 3x) (m² 3,) (I= (U=0 -U-)
A-1
+ --
(1- - Σ I | (1 B, D (I- (-> c + (1 k1)c
30

---

and let U be the entire right hand side of inequality. Then, we have
T - Uk
-T'U** (1 - 11-3))TTTk-11 -BU00 (1 - (k))
B6U
= =T'U* -(1 -11- (1-x))T"Uh-1 - - (U=
-11-11-1
1-1
S Sypk (1 (1- B&) Σ [BB 1i- - B)) (1) (1- (1)))) (T/= -U')
(1 - Bxx 3 (U - U + (1 - (a) (T) 8,)) (T=*-17PP)) (U0 - -U*)
k-1
+ 3u - U*) - (1 3x) Σ (1 (1- e² i-1 + (1 - BBs)
- Bu - -U*- - - (1-Bx)e*t =-1
Σ [80 - 81- - (1) (Ui=i+1(11 (1 (1-B,) (UiL) (U) - U*]] - -Ba(U0 -U*
k
+ 1 - 33) B - -U*) - -U*)-
-u - -1))1 (1- -pt)) e
i=1
where inequality comes from Lemma 8 with a 3k, U = Ü Uk-1, and previously defined Ü
U.
Now, we prove second inequality in Lemma 17 by induction.
If ===1, 1,
U - (1) B,0' = (1) +
U9) 2 (1- + (1- (1-81)p00 -(*) (23) - -1)(U- - in),
where inequality comes from Lemma 9 with a =0 = U - U. and let Ū be the entire right hand side of inequality. Then, we have
T U T (1 - B,)T -,,00
- 8, (+) (1 -3))
2 yp (11-)1)
(1) (231 - 1)(10 -Ū*)) - -(*)) -1 - -t")
(3))
(1 b1) (0 1000 - (n)+ + 10)08)111((----11 -0¹) - 0 Un)
- (1 -11-7P') -1)
where inequality comes from Lemma 9 with a = B1,U = U2. Ú U and previously defined U.
By induction,
Uh (1 - -- 1001--8p0 B&ú
Be (TO-- -t+) + (1- ( + (1 =
k-1
2 (1 3k) Σ
[Bi - 3/- - B)) (15=) (1 - -31) (M (vo - -U)]
1=1
- (1 - 8x) (v=0 - - + (1- 3x) (1 (,)) (11- (w - (.y)
1-1
-B - -t-) - (1 (1)))) Σ n | (1 B,
|T
1p'' (D c-2 - -11- - -11-B))c* x-1
31

---

and let U be the entire right hand side of inequality. Then, we have
T - Uk
= =T* - -(1-Be)t'ut - BuL - (1 - 11-))==
U - -(1 ( - Ú-
Ba (U (11)))11))))))
2 ypx (1- Bx) Σ (B: Bi-1(1 B:)) (1 (1 -1-33)) (1iZA-1711) [60 (00-
(1 1x3 10 1000 - (-)) (1- - 3x) (1)=) (1-
8,)) (IESL-17P11) (00--i) -i.))
k-1
+ -k (-) - (1 - 3x)) Σ (1 8,) mppl (I- c--2+ + (1 - -
- 32 (r- - (1 3x ==
Σ (8, 81-1(1 -))) (T)= (1 (1)) (TIL)T)t) (19 -00] -Bc(U0 -On)
k
+ h j=1 (1 - 33) BT) (v0 (y) >
The j=il (1 - B3 / (I- -1t ch c
where inequality comes from Lemma 9 with a = 3x, U = Uh, Ū Uk-1, and previously defined
Ú
Now, we prove the first rate in Theorem 6.
Proof of first rate in Theorem 6. Since Bi S A < B2 implies || < sup[[1]ll |21l for
A, B E F(X), if we take 1l right side of first inequality in Lemma 17, we have
(y 7) (1+ 2x - )
1100 100-U"I -U +1++7)
Σ (n (1 -1 3,)) x x 11
(1--1)- -g/t1
(7-1- 7) (1 27 -
1 + y 1 2k
11000 U
1 k+I 1 - osisk-1 110/
+
max
(x -kt1
If we apply second inequality of Lemma 17 and take Il-llxe-norm -norm right side, we have
(7-1-2) (1 + 2n - 1
+ 1+ 1-g* z² max |e"|
100 10-00~ 00010
( x-11
1+ 1 1-9 osisk-1
Therefore, we get
| - 1 - 5 ( - max U |
1 10- 8+ }
(g++1)= - gk+1
1 1+7 1 1- k
||=||
max
1 1+gh+1 - y osisk-1
Now, for the second rate in Theorem 6, present following key lemma.
32

---

Lemma 18. Let < < 1. For the iterates I== Anc- VI, if U 2 TUU,, there exist
nonexpansive linear operators 10,,.... and ) such that
k Σm 1 By) (T-P((TT-) (T-) 6:1
TVU - Uh - 1T 1 (3333 (,) M - -U*)
==1
340000 -U*);
T 1hh
(3: - 3/-1(1 - 3:)) (T)= - -Bj)) (M (00
(000)))00000000 (00-0)) - -3x 07)
i=1
Σ 11 - B (1- ci-
==1
for 1 S k. where III
j=k41 (1 (1-3,) = 1, T = M = I, and 8o = 1.
Proof of Lemma 18. If U 2 T Uo 2 li U by Lemma 1. By Lemma this also implies U 2 Ü+
First, we prove first inequality in Lemma 18 by induction. If = 1,
U - - 8:)00 - -110 = (1 - 3:)e + +1 - (1-
60) $ (1 31)c0 +(1 - - U + (281 - -1)(00 -
< (1- 3i)e +(1 (U -U),,
where the second inequality is from the (2,3) - 10)00000000000 1)(00- - S 0, and first inequality comes from
Lemma 8 with U, U0 - U --- U* and let Ú be the entire right hand side of inequality. Then, we have
TU - U2 -1 -300 - (1 -1- 81)
S (1 - - - -U*) - Biee
-()) - UU*) - -I- (I- -B,)ca.
where inequality comes from Lemma 8 with =1,, U = U Ú Uo and previously defined U. By induction,
Th (1 Uk) BBU* Br (U U*) (1 (1-B3)
$ BA (U" -U*) - (1 - -B -U") + [1--)
(1 8,)) (IP= (U U*)
+ (1 *x) (1 - 3x) Σ 11 (1 -,,,,,11----111 yp! (1appt) el11
S (1 (6) (1 (1 3,)) ( (U - U + (1 +-)
(1 - 3k) Σ
yp (T- ypt) )-
33

---

where the second inequality is from 5g - -1 Bx) S 0 and let U be the entire right hand side of inequality. Then, have
T t² U - (1-3))TTuh11 B 3c000- U7) (1 Ba)e (1 (1- Bxx (1I) -3)) (IP= (0 - UU*) (1 -Ba)e
syph
k-1
(1 Bx) Σ 11 8 - 1 (1 (I- ct-1) Bk (1 (
k = -I-=1(1 - 3 7 -U*) -
(1 (1-) et
3,
1=1
- 00 - -U),
where the first inequality comes from Lemma 8 with a = Br, U = Uk = Uk-1, and previously defined U.
For the second inequality in Lemma 18, if k 1.
Ut_ -11-B: 3,0
(1 (1 (1)c² Bi(10) - (1- -00
09) = (1 - 31)e - BIUU0 +1)+ -0- - -(U0 -100-01 (-))
2 (1 Bi)e" - Bi (1)-((1)))(U" -0y)
where the second inequality is from U 2 T 2 Ú+, and let Ú be the entire right hand side of inequality.
Then, we have
TU - 1 TTU (1 - -0
- 31U - -i - -00 - -1-
2 (('0--0) - (1--))(000-0 - 81 (1) 31)
= (231 - 11>p1 (1 - -0) - -0n) (1-7P')(L -
3I)e -1)))
where inequality comes from Lemma 9 with a = = = U2, Ú UD, and previously defined 0. By induction,
U (1- kk) 3BÙ
R-1
2 (1 3x) Σ
(3: - -3- - 3.)) (TT (T (1 - -8))) (TL) (00 (w0-t+) [+]
t=1
+ (Be (1 Bx) (T - :.+) (1 -Ba)c+-11
1-1
Σ m (1 (1-1) - (I (1-) c-1
(1 3k)
and let Ú be the entire right hand side of inequality. Then, we have
34

---

T U*
= - -(1 -11 - - Bu - -t) - (1 - (1-
k-1
2 27th (1 (1- B&)
Σ
(Bt Bi-1(1 - -B)) (1 (1 -B3)) (Ti (T0 -t--
i=l
k-1
+ (Bx - (1 - -Ba)) 1) (1 -0x) - (1 - 3pa)
Σ
B 17 (T-rD-) ct-
i=1
+ +11 - (1)e ) -11 (1- -L-Bkk1 (1--a))e--1- 3x (-0000))) U²))
4
(3, 33-1(1 B.)) (11+ -z)) (Wi=A)Pi)(U0 (v0 8:(00-00
Σ M==i(1 3) (1-) ct1
where inequality comes from Lemma 9 with a = 3x, U = UK, UR-1, and previously defined
U.
Now, we prove the second rate in Theorem 6.
Proof of second rate in Theorem 6. If we take I1-1lxc right side of first inequality in Lemma 18, have
(7-1-7) 7
1+7 1-1 g max 1 x 1 - y osisk-1
(g(+t)- -k+11 11000UP
||=||
If we apply second inequality of Lemma 18 and take
II. -norm right side, we have
(x-1-7) (1 - 1)
1 7 - g*
I00- 6-
||'||
max
(g 1-41
1 gh+l - osisk
Therefore, we get
- - S ( h+1
(1-1-1) 7) ght1)
1000011
1 1 1 1-2k max
||=||,o
+ + g 1 - y osisk-1
since U+ - U S U implies that
(x- 77)
11 -U (--1-1) -)) (1+
1 t -0-1
(yx+1)-1 xh41
(1 ( -
F
Omitted proofs in Section 6
For the analyses, we first define fos: IR" + R.ah as
where 17. : R.. + R defined as
1; = (U Ug-1: (f*(1)) UUti,.... Un)
for j = =1,.... 1....,, n. where f is Bellman anti-optimality operator.
35

---

Fact 3. [Classical result, [10, Proposition 1.3.2)) Tês is a ry-onnracctive operator and has the same fixed point T
Now, we introduce the following lemmas.
Lemma 19. Let <,< 1f0 - a S 1, then there exist "y-contraacttev nonnegative matrix PGs such that
TãsU - - (1-a) UT P al*).
Lemma 20. Ler < < 1f0 - v 1, then there exist aycontraccteeee nonnegative matrix Pas such that
Pas(U (1 at*) TTgU (1- aT-s - a'""
Proof of Lemma 19. First let U = V, V, U = V*, For 1 Sis we have
(s;(s;:) - -1- (L=)) o (s:) S V(s)) -1- aT,
=pp" (V - (1- - av.) (8i);
where n, is the greedy policy satisfying T = TV and first inequality is from T T and
TRiV* < TV. Then, define matrix P; as
Pi(V) = (Vi...., Vi-1 (TP" (V)), V.. V.)
for 1...., n. Note that P; nonnegative matrix since pd: is nonnegative matrix. Then, we have
TV (1 - a)TTV aT,V" S P:(V - (1 -1-a)V aV
By induction, there exist sequence of matrices (P:)i=I,...,, satisfying
TēsV a)TTsV aT V* P .....PP(( (1- P1 aaV*)
since V V for all Denote Pas as P....PA Then, Pas is 7-cottractive nonnegative
matrix since
"
"
Σ (Pos) = (P.... P1). S
(P)).
-7
j=1
j=1
where first equality is from definition of P/ for 1 1I inequality comes from definition of PP for 1 < < 1, and last equality induced by definition of P;. Therefore, this implies that Pasll 7.
for 1 iiS
If = Q. with similar argument of case = V, let n. be the greedy policy, define matrix P, as P((Q) (Q1...., B.b.....,Q--1.. ( (Q)) Q.+1...., Qn),
and denote Pas Pa.... .....P.. Then, Pas is --cottractive nonnegative matrix satisfying TōsQ - - TT < Pas(Q - (1 - a) - aQ*).
Proof Lemma 20. First let V, V. 0. V.. For Si S n, we have
(s)(s) - - (x)
(1 (1- ())ra))(s))) + (1 a)7EBrrG P(.1m [(60)]
sup aEd
r(si, + m))) [V(s')]
sup
aEA
ar(s), ayyB (.)) [v-(6)]]
inf aed
inf aed
((s') - (s) uV7
36

---

Let R:(-1s) argmin ueA E [V(s)) (1 (L-)) (s*( -s)())))((>)))) and define matrix P.
Pi(V) (V,,. Vi-1, ( Vith...., Vn))
for i ,,...,7A. n. Note that P. nonnegative matrix since p is nonnegative matrix. Then, we have
Pi(V (1 a-V av*) <TVV (1 a) -
By induction, there exist sequence of matrices (P: satisfying
Pr Pi(V - - (1- aV*) - Tas V (1 - a)T aT
and denote Pas as P,, P.. With same argument in proof of Lemma 19, Pas is --contractive nonnegative matrix.
P1.
If U = Q. with similar argument, let ft (s) = (0(s asQ
and define matrix P; as
P((Q) (UI,.... -U. (I
Denote Pas P,, ... P1. Then, with same argument in proof of Lemma 19, Pas is y-contractive nonnegative matrix satisfying
Pas(Q (es(Q-(1--t)) (1-a)Q-ad) TōsQ T) Q
Next, we prove following key lemma.
Lemma 21. Let < y < 1. For the iterates (U*) k= of (GS-Anc-Vi VI), there exist c-contractive nonnegative matrices (P and (P) (PGs)t=,,1,... such that
k
Uks -Uk $
Σ [(8 Bi-1(1 B:)) (II (T) (1 -3)) P (U- U*)
i=1
Re U*) + (II - B3)) Pmss (U - -
Ta -th
Σ
(B, B1 (,)) (T 11 (1 B;)) (TI (os) (U--t-))
i=1
Be - (1)) B;)) (I P/os (U' -r²)
where I ==+1 B3) and Bo 1.
Proof of Lemma 21. First, we prove first inequality in Lemma 21 by induction.
If 1: 0.
"GsU0UU0 - TōsU0 U* (U--U9 Uo UO - (U" U*)
S (U" - U*) - (U -U*).
where inequality comes from Lemma 19 with
U,U = UO.
37

---

By induction,
TösUk - Uk
-TasUk -11- Be) - - 8x - U*)
3xT
PPss -(1 - -1:)UUk -B,U7) 3x(U0 - U*)
-Po -U*) + (1 - -Ta - 3x0 - -
k-1
s (1 P
[(3: - 1i-1(1 - -B)) ( (1 - -B))) (Tİ= PPss) (T - U*) Σ
- - U*) + (1 B,)) (UP- Pos) (00 (00 -U7)
+BePEs U*) 3x - -U)
= Σ [(: - -B--(11 - B:)) (1)= (1 ==1
(1- - -B)) P(s) (U) U*)
(U -U*) + (1) (1 8,)) (m_aP's) (U= - U*)
where the first inequality comes from Lemma 19 with a = Brr U Uh Ú Uk-1, and second inequality comes from nonnegativeness of Pas-
First, we prove second inequality in Lemma 21 by induction.
k = 0,
Tās - Tōs Ü (v= - in)
= =T GGs - (U" - 0r)
2 PU - (') - -00- -0--0n U²),
where inequality comes from Lemma 20 with a 1,U = Uo.
By induction,
TāsUk Uk
=TōgUk - (1 - (is Bx
- i+)
PaslUU* (1 B&) Uk- -Btr') - (U - 0/0)
PB - Ú'¹) + (1 U
k- - - 1)) - -Bx(U0 -ty
2 (I 11)
Σ
[Bi- - 31-1 8c)) (11=11 (1 BB]) (ui= (10 (w0-
1=1
-U- - +t'++ + (1)= 8,)) Plas) (v - tt)) -t-)
+ +Br - -Ū*) - :u -(m)
Σ (B: - Bi-1(1 -B)) (15=1+1111 - -Bi) (Mi (oas)(UU=)) (10- 07)
==1
1U t.)) + (T (1 - (1)) (TL_. (U0 - -tr)
where the first inequality comes from Lemma 20 with a = Be, U U* Ú = 17 nonnega- tiveness of Pk
Now, we prove the first rate in Theorem 7.
38

---

Proof of first rate in Theorem 7. Since B1 S A S B2 implies &| I sup B B1 : B2
for
A, B E F(X). if we take Il right side of first inequality Lemma 21, we have
18: B.-1 3:)l (1f=+1(1 (1 - 9,)) [I(Ti= -00 -U0 1-
+ 3x 1100
101 + (ut=) (1 - -B)) (MP_+P&ss (U U*
- 13, B Bi) (1)) 8,)) + 3xx + +
11 j= (1 83)
i=1
|00
U01 00
( 7) + - 27 k+1
1 - U* 10o
(-++1) - ク
(
where the first inequality comes from triangular inequality, second inequality is from 7-contraction of Pas. and last equality comes from calculations. If we take I1-Iloo right side of second inequality in
Lemma 21, we have
B B - 3:0l (I) (1 (1 ((ll-,,))) 3,)) [T] (0 -000
+ Bx 1000 -U"I (TT (1 -B)) (TT (ss))s)))s ) (0 - -t-+) 11.0
k
Σ 2 b-i+1 133. - 3i - BB)l
33)) + 3x + + =1 - B3))
7) (1 + 27 - )
()*+1) - x
where the first inequality comes from triangular inequality, second inequality is from from ?- contraction of Plas and last equality comes from calculations. Therefore, we conclude
|TāSU* - - < (r-1- (1 + 2n - k+11) -
(1*+1)= -1 x max {1|00 U*| 1..1110- 1 10
For the second rates of Theorem 7, we introduce following lemma.
Lemma 22, Let < y 1. For the iterates {U* k= of (GS-Anc- VI), U S Uo
then k--1 < U < T S TasU* S U for S k. Also, if U 2 TōsU", then
Uk-1 Uk Uk-1 2 TāsUk 2 U* forlsk
....B By definition, if < Ü,TTU STÜ for any 1 i and this implies that if U < Ü, then Tūs S U. Hence, with same argument in proof of Lemma 5, we can obtain desired results.
Proof. By Fact 3, limm- TōsU = U
Now, we prove the second rates in Theorem 7.
Proof of second rates in Theorem 7. If U < T0 then U - U s 0 and U < Tä by Lemma 22. Hence, by Lemma 21, we get
0 < U U
Σ [(A 13-1 - Ba)) (13 (1--)111111))1 B,)) P(s) (10)) -U*]
- 3u(00 Un) + (1 - B,) Pls) (U - U*)
Σ [(8 - 3, - -a)) (n - (1 - BB)) III (I P(s) (Uo - -U*)] - ((00-U)
39

---

where the second inequality follows from (I By)) P (0) - -U*) s 0. Taking -norr -norm both sides, we have
| 1lc S -- (1 + 7 - |1:0 - 10
(xhtl) ghill
Otherwise, if U 2 U U 2 Tas and U 2 U 2 U by Lemma 22 and 3. Thus, by
Lemma 21, we get
0 2 U* U
2 Σ (3: - 3:-1 (1)):)) (1
- 33)) (mi= (U" - 3x(000 -0000)))) -0,,
where the second inequality follows from I 11 3,)) (IL /os) (00-Ur) Taking Il-lls- -oorm both sides, we have
|TāSUK 14 S (1-1-2) 7) (1+ (1+7-
170 0+ 0+1
(yx+t)) gh+t1
G
Broader Impacts
Our work focuses on the theoretical aspects of reinforcement learning. There are no negative social impacts that we anticipate from our theoretical results.
H
Limitations
Our analysis concerns value iteration. While value iteration is of theoretical interest, the analysis of value iteration not sufficient understand modern deep reinforcement learning practices.
40


Reviews:
[{"review_id": "N9wtLtyPxE", "reviewer": "Reviewer_8tEg", "summary": "The paper introduces an accelerated version of the Value Iteration (VI) algorithm, called Anc-VI, based on the anchoring mechanism.  The proposed method achieves faster reduction in the Bellman error compared to standard VI even when the discounting factor is close to 1. Meanwhile, a complexity lower bound is also provided which match with the upper bound up to a constant 4. Meanwhile, this work also shows the benefits of anchoring mechanism in approximate VI and Gauss-Seidel VI.", "questions": "1.  If it is possible to derive any practical algorithm based on the theoretical findings in this work?\n2. What is the computing complexity of the proposed method comparing with VI?\n3. What is the guidance on choosing $\\gamma$ in practice in order to achieve faster convergence, e.g., let $\\gamma \\approx 1$? ", "limitations": "The authors addressed the limitations in the Appendix. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This work proposed the acceleration of VI by leveraging the anchoring mechanism\n2. The proposed Anc-VI has provable faster convergence rate comparing with classic VI\n3. This work provide the acceleration rate for both the bellman optimality operator and consistency operator", "weaknesses": "1. The performance of anchoring mechanism has reliance on the starting point $U_0$ and discounting factor. In order to have the fast acceleration, we need to set $\\gamma\\approx1$. However, one of the reason that we set discounting factor $\\gamma < 1$ is for faster computing in practice.  The author need to clarify whether the anchoring mechanism still can benefit the learning acceleration in the practical case, e.g., in Theorem 1, when $\\gamma \\to 0$, how does the upper bound show the acceleration. Same question apply to Theorem 2\n2. In the Apx-Anc-VI, when $U_0$ is far from optimal, according to Theorem 6, the first few iteration does not necessary results in policy improvement (e.g., by setting $k=1$, $\\gamma=1$). Thus, what does Theorem 6 can tell on the benefits of using Anchoring mechanism?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments.\n\nWeakness \n\n(i) (+Question (iii)) Although in some practical setups, discount factor $\\gamma$ could be chosen freely, we assumed that environment and MDP and $\\gamma$ are given constants.\n\nIf $1/2 \\le \\gamma<1$, Anc-VI exhibits a provably faster convergence rate (First rates of Theorems 1 and 2) than the standard rate of VI, since  \n\\begin{align*}\n    \\frac{(\\gamma^{-1}-\\gamma)(1+2\\gamma-\\gamma^{k+1})}{(\\gamma^{k+1})^{-1}-\\gamma^{k+1}}\n    =\\gamma^{k}\\frac{(1-\\gamma^2)(1+2\\gamma-\\gamma^{k+1})}{1-\\gamma^{2k+2}}\n    \\le \\gamma^{k}(1+\\gamma).\n\\end{align*}\nIf $0<\\gamma<1/2$, these rates don't guarantee acceleration, but if $TU_0 \\le U_0$ or $ U_0 \\le TU_0$, the second rates of Theorems 1 and 2 are faster than the standard rate of VI for all $0 < \\gamma <1$. (Both rates are decreasing functions of $\\gamma$.)\n\n(ii) For Apx-Anc-VI and Apx-VI, we didn't include the case $\\gamma=1$ since the error diverges as the iteration number increases. If $0<\\gamma<1/2$, Apx-Anc-VI exhibits a provably faster convergence rate than the rate of Apx-VI by same argument in (i). \n\nQuestions. \n\n(i) As VI serves as the foundational basis of practical RL algorithms such as fitted value iteration and temporal difference learning, we expect that Anc-VI will give insight for designing new practical algorithms or improving existing ones by incorporating the anchoring mechanism. This is certainly an interesting direction that we plan to pursue in our future work.  \n\n(ii) Computing complexity of Anc-VI and VI *per iteration* are basically the same; the operation of adding an anchor term is a vector-vector operator, and is therefore negligible compared the evaluation of the Bellman operator, which often involves a matrix-vector operation. "}, {"review_id": "HiWxaQH14m", "reviewer": "Reviewer_GSn8", "summary": "This paper considers an anchored version of Value Iteration and derives accelerated rates in terms of the Bellman error for both the Bellman consistency and optimality operators. Then, the work addresses the particular case of $\\gamma =1$ with a $O(1/k)$ rate that VI fails to guarantee via the standard contraction argument. A complexity lower bound matching the upper-bound (up to a constant numerical factor) is then established. The paper further proposes an error propagation analysis of approximate anchored VI, extending the results of the exact case and a Gauss-Seidel version of the algorithm is also analyzed.    \n", "questions": "Besides the comments above, please find some questions below for clarifications: \n\n1. l. 149 - 151: is the comparison of the rates with VI straightforward from the rates or does it require some algebraic manipulation? It does not seem to be immediate from the expression, please provide more details to clarify in the appendix if needed.  \n \n2. It is mentioned in the paper that the anchoring mechanism is ‘distinct from Nesterov’s acceleration’. The latter mechanism has inspired the work [37] which requires for instance some reversibility conditions as discussed in related works. A recent work (Tran-Dinh 2022) draws connections between Nesterov’s accelerated methods and Halpern fixed point iterations. Could you comment on this? \n\nQuoc Tran-Dinh, 2022. The Connection Between Nesterov’s Accelerated Methods and Halpern Fixed-Point Iterations. \nhttps://arxiv.org/pdf/2203.04869.pdf\n\n3. In the abstract, it is mentioned that ‘the optimal rate for the VI setup was not known’. Do you mean for the Bellman error (as the rest of the abstract and the paper state results for the Bellman error)?  Please precise in that case, I found this a bit confusing at first read. \n\n4. How do you come up with the specific way you set the parameter $\\beta_t$ in l. 122? It seems to match the usual $\\beta_t = 1/(t+1)$ used for anchoring/Halpern iterations in the case where $\\gamma = 1$. Could you provide more intuition about this? \n \n5. Results on the Bellman error can also be translated to the optimality measure $\\|\\|U^k - U^{\\star}\\|\\|$\n using the triangle inequality at least for $0<\\gamma<1$ \nto obtain $\\|\\|U^k - U^{\\star}\\|\\| \\leq \\frac{1}{1-\\gamma} \\|\\|U^k - T U^k\\|\\|$. How would this result compare to VI? Is it meaningful to include a comment along these lines for comprehensiveness given that you discuss translating the result for VI to control the Bellman error? I understand though that the anchoring mechanism is better suited to control the Bellman error. \n\n6. l. 290 - 292: How would the GS update rule would even be defined in infinite dimensions even before talking about the Hahn-Banach theorem for the analysis? Why Hahn-Banach theorem would not be applicable?\n\n7. Minor comment, l. 240: for the upper bound, it seems that one can obtain a constant equal to 2 using the following derivations:  \n$$\\frac{(\\gamma^{-1} - \\gamma)(1+\\gamma - \\gamma^{k+1})}{(\\gamma^{k+1})^{-1} - \\gamma^{k+1}} \n= \\frac{\\gamma^k (1-\\gamma) (1+\\gamma - \\gamma^{k+1}) }{1-\\gamma^{2(k+1)}}\n= \\gamma^k \\frac{1}{\\sum_{i=0}^{2k+1} \\gamma^i} (1+\\gamma - \\gamma^{k+1}) \n\\leq \\frac{2 \\gamma^k}{\\sum_{i=0}^k \\gamma^i}.$$\n\n**Proof related questions for clarifications:** \n\n 8. About the Hahn-Banach argument (for infinite state action space): Could you please provide clarifications regarding the following questions? \n- Lemma 8, 9 in the appendix: What are $U$, $\\tilde{U}$, $\\bar{U}$ in the statements? If these are arbitrary (as they are instantiated later in the proofs of Lemma 10,11 for example), please precise the statement of the lemmas for clarity. \n\n- The definition of the operator $\\mathcal{P}$ (l. 600 for e.g., and others) is not very clear to me. Do you define it only for multiples of $\\bar{Q}$ where $\\bar{Q}$ is defined in the lemma statement or do you define it for every $Q$? Why do you introduce $c$ in the definition? I guess this is because you need homogeneity to invoke the Hahn-Banach theorem but I would expect that this would be verified once you define the sublinear function for the application of the theorem. Also, it is not clear to me why is the $\\mathcal{P}$ as defined a linear functional on M (because of the inf) with $\\|\\|\\mathcal{P}\\|\\|$ = 1, which norm is this? Is it the operator norm (please define it in this case)? The notation $\\bar{Q}$ is a little confusing. If $\\mathcal{P}$ is defined by the inf (without c) for any $Q$, then you can show sublinearity (or rather ‘superlinearity’ with the inf) and homogeneity. The restriction to the span of $\\bar{Q}$ would be a linear functional (as you mention it) and then you can conclude I guess. If this is the reasoning you conduct, please clarify. I suggest to state the Hahn-Banach theorem and its application or at least to clarify what is the sublinear function $p$ used and what is the linear functional dominated by $p$, especially the use of the notation $\\bar{Q}$ for defining $\\mathcal{P}$. \n\n- Minor, l. 568, l. 590: ‘if action space is infinite’? Is it rather state space here? Same comment for other occurrences.   \n\n9. Case $\\gamma =1$: l. 672, 673 in the proofs in appendix, it is stated that the $O(1/(k+1))$ rate is obtained after taking the infinity norm in Lemmas 4 and 10. Does the $O(1/(k+1))$ rate just follow from using $\\beta_k = 1/(k+1)$ or is there any particular upper bounding manipulation? I think more clarifications would be useful for the reader. ", "limitations": "The paper does list the fact that the analysis of VI is not sufficient to understand modern deep RL (in appendix H in the end of the paper) and comments on the potential of future work in the conclusion. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I find the fact that the Anc-VI algorithm is able to address the case $\\gamma  =1$ interesting and the anchoring mechanism seems to be well suited for this case unlike VI.  \nIt is interesting to see that the anchoring idea which was recently investigated in depth in optimization is also interesting in the DP setting. While the idea may seem natural as DP involves fixed point iterations, the execution requires to address several technical challenges that are more specific to the DP setting. \n\n- The contributions of the paper are solid and somehow comprehensive with accelerated convergence rates, a lower bound and extensions to inexact and Gauss-Seidel variants. \n\n- The anchoring mechanism can also be used for further extensions in DP/RL for the design of learning algorithms beyond the deterministic setting.   \n\n- The paper is well-written and the contributions are overall clearly stated. \n\n", "weaknesses": "1. Even if the Bellman error is a natural quantity as a performance measure for fixed point iteration schemes, it would be nice if the paper can comment more if possible on the motivation to consider convergence guarantees in terms of this performance measure compared to the distance to the optimal value function. It is mentioned in l. 18 that the distance to the optimum is not computable and that the Bellman error can be monitored which I find a valid and fair interesting point. However, as a matter of fact, the lower bound provided in [37, Theorem 3] (which is mentioned in the paper) in terms of distance to the optimal value function is actually achieved for Value Iteration. If we would like to approximate the optimal value function as fast as possible to find an optimal policy in a control task for instance, why would we use anchored VI instead of VI? See also the related question 5 in the ‘Questions’ section below. \n\n2.  It is not discussed how to find a near-optimal policy using Anchored VI.  I guess you can just output a policy that is greedy with respect to the output of the Anchored VI algorithm after a certain number of iterations as it is usually done with VI for which there are policy error bounds. Given that Section 1.1 mentions optimal policies, it would be nice to mention that the Anchored VI could be further enhanced to find near-optimal policies as an approximate planning algorithm. \n \n3. The paper only discusses guarantees in terms of the Bellman error comparing with the translated result for VI from distance to optimal value function $\\|\\|U^k - U^{\\star}\\|\\|_{\\infty}$ to Bellman error. It is also similarly possible to translate the Bellman error guarantee to a distance to optimality result. See question 5 below. \n\n4. Case $\\gamma = 1$: How can the (action) state value functions be defined in that case? Definitions of Section 1.1 may not be relevant anymore. While the paper states that that ‘a full treatment of undiscounted MDPs is beyond the scope of this paper’, I think at least adding references would be useful to give a meaning to the problem and hint to the fact that fixed points can be guaranteed to exist (as currently assumed in the paper) under some technical assumptions. This would justify that the assumption is reasonable and allows to avoid some technicalities.\n\n5. I think the paper can comment on the advantages of the Gauss-Seidel Anc-VI and why this extension is considered. Section 6 does not discuss the motivation for considering such an algorithm. Is it for the possibility to perform asynchronous updates via its coordinate-wise update rule? \n\n**Minor:**\n \n- I find the terminology ‘linear operator’ for the Bellman (consistency) operator a little confusing even if Puterman 2005 (p. 144, Eq. (6.1.7)) uses for e.g. the terminology ‘linear transformation’. A linear operator T would satisfy T(0) = 0 according to the standard mathematical definition of a linear operator, which is not the case for the Bellman consistency operator. Maybe affine would be more appropriate.  \n\n- l. 137-141: I would say the result for the Bellman ‘consistency’ operator can also be relevant for policy evaluation which is useful as a subroutine for several algorithms in RL beyond value iteration. \n\n- As a suggestion, the paper could add a figure for the hard MDP instance to ease the reading (see for e.g., Figure 1 in [37]). It also seems that the hard MDP instance is the same as the one in [37], it may be worth it to mention this in that case. \n\n- There is sometimes some redundancy in the proofs. For instance the Hahnn-Banach argument is used identically 2 times in l. 568, l. 590. It is again used for Q functions in l. 578 and l.  600. This also happens for some inductions throughout the proofs which are very similar.  \n\n- Lemma 15 in appendix: in the proof, ‘by definition W, there exist W’, I guess you mean there exists $k$.  \n\n- l. 513 and later: $\\lim …  \\to $,  I guess $\\to$ can be replaced by $=$ here. \n\n- Several grammatical articles are missing in writing, especially in the appendix: l. 225 (a complexity …), l. 507 (a nonexpansive), 510, 515, 520, 664, 700, 759, 760, 764 and several other places.  \n\n**Typos:**\nl. 111, 113: ‘nonexpensive’; \nl. 116: ‘operator’.  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the highly detailed and constructive feedback.\n\nWeakness \n\n(i) As an analogy in the optimization literature, the recent discovery of OGM [1] and OGM-G [2] demonstrate that considering a different performance measure leads to a different optimal algorithm. In this setting, we show that Anc-VI is an optimal algorithm when we consider optimally reducing the Bellman error, but we are not claiming that the Bellman error is \"better\" measure compared to the usual distance to the optimal value function. Our point is that if we consider the Bellman error (which is also natural) Anc-VI is an optimal algorithm. However, one argument for the Bellman error is that we can get a meaningful rate and a point convergence result when $\\gamma\\approx1$ or $\\gamma=1$ only when we consider the Bellman error. We will incorporate this discussion in the revision. We will comment on this point in our revision.\n\n(ii) Thank you for your comment. We will define a near-optimal policy and explain how it can be derived from Anc-VI in revision.\n\n(iii) (+ Question $5$)\nYes, we can. If we translate Bellman error of Anc-VI to the distance to optimal value function using $\\|U^k-U^{\\star}\\| \\le \\frac{1}{1-\\gamma}\\|TU^k-U^k\\|$, Anc-VI shows same convergence rate $O(\\gamma^k)$ with VI but constant factor slower by\n\\begin{align*}\n    \\gamma^{k}(1+\\gamma)\\frac{1+2\\gamma-\\gamma^{k+1}}{1-\\gamma^{2k+2}}   \\ge \\gamma^{k}(1+\\gamma).\n\\end{align*}\nWe will add this argument in the revision.\n\n(iv) We could not find prior works about technical condition of well definiteness of value function when $\\gamma=1$, But we could think of the following MDP instance: If an undiscounted MDP has bounded reward and the probability of transitioning to a terminal state is larger than some fixed positive constant (for all current state and action) this undiscounted MDP has finite value function since $\\sum^{\\infty}_{i=0}nx^n$ converges for $|x|<1$. This is one condition for well definiteness of value function, and pursuing a systematic study of such a condition may be an interesting direction.\n\n(v) We were careful in commenting on what we did not yet prove, but, yes, we think Gauss-seidel Anc-VI is a stepping stone to analyzing asynchronous coordinate update version of Anc-VI, and we plan to study this direction in our future work. We will comment on this in revision. \n\nMinor and typos\n\n(i) We agree with your point on the definition of a linear operator. Although we followed the convention of [3], we will update the terminology in our revision.\n\n(ii) Thank you for this point on the usefulness of the results for the policy evaluation setup. Our intented point of line 137-141 was that the Bellman optimality setting is more difficult due to the nonlinearity and that we are able to provide an acceleration in both the consistency and optimality setups while prior works don't. We will adjust our wording.\n\n(iii) The worst-case MDP in [4] and worst-case MDP in our paper are different primarily in their rewards: $r(s_i, a_1)=\\mathbf{1}_{\\{i=1\\}}$ \n\nand $r(s_i, a_1)=\\mathbf{1}_{\\{i=2\\}}$, respectively. Less significantly, our worst-case MDP has one additional state, but the transition probabilities are essentially the same. Both MDPs have only one action. We will clarify this point, and we will add a figure to illustrate the hard MDP instance.\n\n(iv) As the Hahn-Banach argument is abstract and delicate, we tried to make the argument precise and explicit for every case. However, we will revise the proofs to reduce the redundancy.\n\n(v, vi, vii, Typos)  Thank you for the detailed corrections. We will correct the errors in our revision.\n\nQuestions\n\n(i) Comparison in line 149-151 comes from direct calculations, but we agree with that algebraic manipulation is not immediate. We clarify this in revision.\n\n(ii) Thank you for pointing out this reference. This work does reveal a connection between anchor acceleration and Nesterov's acceleration, but we claim that the two mechanisms are different in the following sense. First, following reformulation scheme of Theorem $3.2$ in this reference, A-VI in [4], a Nesterov-type VI, can not be reformulated to Anchoring type VI since reformulation only covers restricted Nesterov type algorithm. Second, there is line of research for continuous-time models of acceleration, and [5] and [6] showed that anchor acceleration and Nesterov's acceleration have distinct ODE models. It is our view that Nesterov's acceleration and anchor acceleration have a connection but are substantively distinct, but studying the connections and differences between these two acceleration types is certainly an interesting direction. \n\n(iii) Sorry for the confusion. Yes, we mean the optimal rate in terms of Bellman error.  We will clarify this in revision.\n\n(iv) [7] studied anchor acceleration for $\\gamma$-contractive non linear operator respect to $l_2$ norm in Hilbert space. Inspired by this paper, we tested several candidates of $\\beta_n$, $\\frac{1}{\\sum^n_{i=0} \\gamma^{ki}}$ for $k=1,2,3$, \nand we found that the choice $k=2$ gives analytically simple and accelerated rate as in Theorem $1$ and $2$. \n\n(vi) Sorry for the confusion. We can consider block GS update by dividing action space into finite disjoint sets, and `is not applicable' might not be proper expression. We briefly mention that even if we apply Hahn-Banach theorem on block GS update setting, it does not lead us to valid convergence result since argument of Lemma $8$ is not valid for product of multiple operators $\\mathcal{P}_n \\dots \\mathcal{P}_1$ which appears in proof of Lemma $19$. We will clarify this in revision.\n\n(vii) We believe there is little mistake on your calculation since \n\\begin{align*}\n    \\frac{(\\gamma^{-1}-\\gamma)(1+2\\gamma-\\gamma^{k+1})}{(\\gamma^{k+1})^{-1}-\\gamma^{k+1}}\n    =\\gamma^{k}\\frac{(1-\\gamma^2)(1+2\\gamma-\\gamma^{k+1})}{1-\\gamma^{2k+2}}.\n\\end{align*}\n\n**Rebuttal continues in common response**"}, {"review_id": "jrv7z2YylF", "reviewer": "Reviewer_tQc7", "summary": "The authors focus their study on the theoretical analysis of a (simple) variation of the Value Iteration (VI) algorithm, a classical and grounding tool behind many modern (deep)-RL algorithms.\nThe variation considered by the authors incorporates anchor acceleration mechanisms leading to what the authors call Anchored Value Iteration (Anc-VI). More specifically, rather than repeatedly applying the bellman consistency/optimality operators $T$ to reach the fixed point (i.e., $x_{k+1} = T x_k$), Anc-VI obtains the next point as a convex combination between the initial point and the result of applying the operator on the previous point, namely $x_{k+1} = \\beta_k x_0 + (1-\\beta_k) T x_{k}$. Naturally, the sequence $ \\beta_k$ is a vanishing sequence. \n\nAfter introducing the algorithm, the authors proceed with an in-depth analysis of the convergence rates of Anc-VI.\n\nMore specifically:\n1) They study the convergence rate of the Bellman error (i.e, $||Tx_k - x_k||_{\\infty}$) both for the consistency and the optimal operators. The authos show that Anc-VI converges at rate $\\mathcal{O}\\left( 1/k \\right)$ for $\\gamma \\approx 1$ (while standard VI has rate $\\mathcal{O}(1)$). \n2) Under mild assumptions, the authors derive a lower bound that shows that the convergence rates of Anc-VI are tight up to a constant factor of 4. \n3) The author extends their study to the case in which $\\gamma=1$, where VI may not converge to a fixed point even if one exists. Anc-VI, on the other hand, converges to some fixed point asymptotically, and the bellman error shrinks to 0 at a linear rate.\n4) Finally, results are extended to the approximated value iteration setting and to the Gauss-Seidel variation of VI. \n\n\n", "questions": "1) Do you have any intuitive explanation of why such stronger results can be obtained with anchoring? Why should be want to anchor our search close to the initial point? I think this point might add value for possible future development of RL algorithms that might take inspiration from this work. \n2) Why should we anchor only on the initial value rather than doing a, e.g., linear combination of the past value functions? (except for memory requirements). \n3) Is there any existing variation of VI whose upper-bound matches the lower-bound? \n", "limitations": "The authors discuss Limitations in Appendix H. Furthermore, the value of each theoretical result is properly discussed after presenting each result.\n\nPotential negative societal impact. The paper deals with foundational research on the convergence rates of Value Iteration. I don't see a direct path to negative applications. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "VI is a grounding tool of many modern RL algorithms, and its analysis has gathered the community's attention for a long time. The authors thoroughly review existing works and properly contextualize their results within the field. \nApplying the idea of anchoring to Value Iteration is, to the best of my knowledge, novel and leads to some surprising results, which have all been stated in summary above. \n\nMore specifically, the most relevant ones are:\n1) Optimality of the accelerated rate of Anc-VI (i.e., upper bound matches lower bound up to constant factor). \n2) Convergence in the undiscounted setting. \n\nGiven the fact that VI is the grounding core of many modern methods, I think these results are of interest to the RL community at NeurIPS. For this reason, I recommend acceptance. \n\nOn the clarity. Overall, the paper is a nice read, and not particularly hard to follow. ", "weaknesses": "Not much.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are happy to hear that the reviewer found our work interesting.\n\nQuestions \n\n(i) Referring to prior works [1,2,3], we conjectured  that the anchoring mechanism, which pulls the present iterates toward the anchoring point, provides stability and prevents a certain type of cycling behavior. However, we acknowledge that our intuitive understanding of the anchor mechanism is not very strong, and the question of 'why' (beyond the convergence proof) is an interesting direction of future work.\n\n(ii) In fixed-point theory literature, there is a line of research that analyzes the convergence of the anchoring mechanism with arbitrary anchoring points for nonexpansive operators [Section 30.1, 4]. It seems reasonable to consider an anchor that moves, perhaps as a linear combination of past points, and exploring the effectiveness of such variants is an interesting direction. \n\n(iii) As far as we know, there is no prior variant of VI that matched a lower bound. It is worth mentioning that [5] proposed A-VI, a variant of VI that uses Nesterov-type momentum, and showed that it exhibits an accelerated rate in terms of distance to the value function for the Bellman consistency operator. However, this result requires a \"reversibility\" assumption on the MDP.  \n\n[1] T. Yoon and E. K. Ryu. Accelerated algorithms for smooth convex-concave minimax problems with\n$O(1/k^2)$ rate on squared gradient norm. International Conference on Machine Learning, 2021.\n\n[2] J. Park and E. K. Ryu. Exact optimal accelerated complexity for fixed-\npoint iterations. International Conference on Machine Learning, 2022.\n\n[3] J. J. Suh, J. Park, and E. K. Ryu. Continuous-time Analysis of Anchor Acceleration arXiv:2304.00771, 2023.\n\n[4] Bauschke, H. H. and Combettes, P. L. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, second edition, 2017.\n\n[5] V. Goyal and J. Grand-Clément. A first-order approach to accelerated value iteration. Operations Research, 71(2):517–535, 2022."}, {"review_id": "BRaJcz7OvI", "reviewer": "Reviewer_e9mJ", "summary": "New variants of value iterations based on anchoring\nComplexity lower-bound that shows that their algorithms is optimal in a worst-case sense\nNice extensions for various important cases ($\\gamma =1$, approximate VI, gauss-seidel, infinite state-action spaces).", "questions": "p1, l20: “the optimal rate for the VI setup was not known” : isn’t it Theorem 3 in [37] ? This provides a lower-bound on the rate for both value iteration and value evaluation, and shows that VI achieves this rate.\n\np1, l26 - contributions: I am a bit puzzled by the formulations of “$O(1/k)$ rate for $\\gamma \\approx 1$” etc. While this becomes clear when the exact theorems are stated, it may be worth expanding here on the precise formulations of your results.\n\np2, l45, definition of Bellman operator and Bellman consistency: please mention that you overload the notation. Right now $T^\\pi$ is both an operator of $R^{|S|}$ and $R^{|S|\\times|A|}$.\n\nSection 1.1: please define what is the rate of an algorithm. There may be inconsistencies since usually rate suggests that the convergence is linear and the rate $\\rho$ means that error decreases as $\\rho^k$ after k iterations; whereas I believe that the rate of p3, l83 $O(1/k)$ is for the error to decrease as $1/k$ after iterations. Please clarify.\n\nDistinctions between anchoring and Nesterov’s acceleration: some recent works show that in some setup, anchoring and Nesterov’s acceleration are exactly equivalent - they are the same algorithm up to some reformulation [0]. Does this connection hold in your setup?\n\n[0] Tran-Dinh, Q. (2022). The Connection Between Nesterov's Accelerated Methods and Halpern Fixed-Point Iterations. arXiv preprint arXiv:2203.04869.\n\np4, l122: why not simplify the expression of $\\beta_k$ ? The denominator is just a partial geometric sum.\n\np4, lines 151-152: this is quite sketchy, since “rate” has not been defined (see my previous comment). The comments about “$O(1)$ rate for VI when $\\gamma \\approx 1$” do not make sense to me. I understand $\\gamma \\approx 1$ means that VI will converge slowly, but it is more convincing to compare the number of iterations before returning an $\\epsilon$ optimal solution. \n\nChoice of U0: to satisfy the inequalities of line 152, one can choose either $U_0 = 0$ or $U_0 = R / (1-\\gamma)$, with $R$ an upper bound on the rewards. Would that be a good choice in practice though?\n\nTheorem 1: is your choice of \\beta_j the optimal choice?\n\nTheorem 5: is your MDP instance different from the MDP instance from Theorem 3 in [37]? Please clarify.\n", "limitations": "\n* No significant limitations apart from the absence of numerical simulations. It is not clear if the algorithms proposed in this paper perform well; beating vanilla value iteration is not really hard in practice.\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* Strong theorems, able to overcome the shortcomings of the analysis of some prior work that only prove acceleration for linear operators [1, 37]\n\n* Well-written and easy to follow", "weaknesses": "* A bit sketchy on the terminology: “rate” is not defined, some inaccurate statements (“O(1) rate for VI when $\\gamma \\approx 1$”), see my questions below\n* No numerical comparisons with existing methods\n* No analysis in the model-free setup (using sampling)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful feedback.\n\nWeakness\n\n(i) (+Questions (iv) (vii))\nThank you for this point. By \"rate\", we meant the $\\mathcal{O}$-dependency of the error. We will define our use of the term \"rate\" and we will revise the statement \"$O(1)$ rate for VI when $\\gamma\\approx 1$\" to make it more precise. (By $\\gamma\\approx 1$, we meant $\\gamma> 1-1/k$.)\n\n(ii) (+limitation)  We performed several numerical experiments for Anc-VI and found that Anc-VI provided a practical acceleration only in some cases. (Our rate is a worst-case rate, so when the MDP is not a worst-case instance, there is no guarantee that the actual rate of Anc-VI is better than regular VI.) However, we were not yet able to find an adequate theoretical or heuristic explanation that tells us when we can expect the anchor to provide a practical acceleration, so we chose not to present them and left this issue to future work.   \n\n(iii) In fixed-point theory and minimax optimization literature, to the best of our knowledge, whether anchoring provides an acceleration in stochastic settings is still an open problem. The analysis Anc-VI in a model-free setting is indeed an important direction that we plan to study in future work.\n\nQuestions\n\n(i)  Sorry for the confusion. We try to indicate the optimal rate in terms of Bellman error, not the distance to the optimal value function. We will clarify this in revision.\n\n(ii), (iii) We will clarify overload of notation and reflect your comment in revision.\n\n(v) Thank you for pointing out this reference. \nThis work does reveal a connection between anchor acceleration and Nesterov's acceleration, but we claim that the two mechanisms are different in the following sense. First, following reformulation scheme of Theorem $3.2$ in this reference, A-VI in [1], a Nesterov-type VI, can not be reformulated to Anchoring type VI since reformulation only covers restricted Nesterov type algorithm. Second, there is line of research for continuous-time models of acceleration, and [2] and [3] showed that anchor acceleration and Nesterov's acceleration have distinct ODE models. It is our view that Nesterov's acceleration and anchor acceleration have a connection but are substantively distinct, but studying the connections and differences between these two acceleration types is certainly an interesting direction. \n\n(vi) Now that we think about it, the reviewer is probably correct that the expression is simpler when we carry out the partial geometric sum. Thank you for pointing this out. We will make that change in the revision. \n\n(viii) Although we believe that $U_0=0$ is a natural choice, it is probably not a \"good\" choice for all MDPs. In our view, the requirement $U^0\\le TU^0$ is not an onerous one, but it can be a cumbersome one. We feel that this requirement is probably an artifact of the analysis, and we will try to relax it in our future work.\n\n(ix) We believe it is likely that there is a better choice of $\\beta_j$ that slightly improves the constant. However, our choice $\\beta_j$ is a relatively simple one that attains a rate that is optimal up to a constant factor of $4$, so it is the optimal choice in that sense. In terms of our analysis, our choice of $\\beta_j$ is the coefficients that optimize our given analysis.\n\n(x) The worst-case MDP in [4] and worst-case MDP in our paper are different primarily in their rewards: $r(s_i, a_1)=\\mathbf{1}_{\\{i=1\\}}$ \n\nand $r(s_i, a_1)=\\mathbf{1}_{\\{i=2\\}}$, respectively. Less significantly, our worst-case MDP has one additional state, but the transition probabilities are essentially the same. Both MDPs have only one action. We will clarify this point in our revision.\n\n[1] V. Goyal and J. Grand-Clément. A first-order approach to accelerated value iteration. Operations Research, 71(2):517–535, 2022.\n\n[2] Su, W., Boyd, S., and Cand\\`es, E. J.  A \ndifferential equation for modeling Nesterov’s accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17(153):1–43, 2016.\n\n[3] J. J. Suh, J. Park, and E. K. Ryu. Continuous-time Analysis of Anchor Acceleration arXiv:2304.00771, 2023."}]

Author rebuttal:
# Common Response

First of all, we thank the reviewers for their constructive and detailed feedback. We were excited to see that all the reviewers found our work valuable. Indeed, as reviewer e9mJ and tQc7 mentioned, acceleration of Anc-VI is guaranteed by ''strong theorem'' and ''leads to some surprising results'', and we expect the anchoring mechanism of Anc-VI to be applicable to more practical setups. Specifically, Reviewer GSn8 and e9mJ mentioned using Anc-VI in model-free setups and with asynchronous coordinates. We believe these are all interesting future directions. 

$ $

$ $

$ $

$ $


# Rebuttal of reviewer GSn8 continued

Hahn-Banach argument

(i) $U, \\tilde{U}, \\bar{U}$ are arbitrary function satisfying condition of Lemmas. We will clarify this in revision. 

(ii) $\\bar{Q}$ is defined in the Lemma and we introduce $c$ for homogeneity of $\\mathcal{P}$ to invoke the Hahn-Banach theorem as you pointed out. Then, $\\mathcal{P}$ is linear functional in $M$ where $M$ is linear space spanned by $\\bar{Q}$ with $\\|\\cdot\\|_{\\infty}$

-norm.  About norm of $\\mathcal{P}$, we apologize for unclear notation and typo. Norm should be operator norm, and in line 601, '$\\|\\mathcal{P}\\| = 1$' should be modified to '$\\|\\mathcal{P}\\| \\le 1$'. This is true since $\\frac{ |c \\inf_{(s',a') \\in \\mathcal{S} \\times \\mathcal{A}}  \\bar{Q}(s',a')|}{\\|c\\bar{Q}\\|_{\\infty}} \\le 1 $. We will clarify this and reflect your suggestion in our revision.

(iii) If action space is finite, greedy policy satisfying $T^{\\pi}V=T^{\\star}V$ is well defined and it directly leads to Lemma $8$ and $9$ as we showed in proofs. But if action space is infinite, we can not guarantee existence of greedy policy since maximizer may not exist in action space. In this case, we solved this issue by Hahn-Banach argument.  

(iv) If we plug $\\beta_k=\\frac{1}{k+1}$ in Lemma $4$ and $10$, we get $O(1/k+1)$ rate by simple calculation. We will clarify this in our revision. 

[1] D. Kim and J. A. Fessler. Optimized first-order methods for smooth convex minimization. Mathematical Programming, 159(1–2):81–107, 2016.

[2] D. Kim and J. A. Fessler. Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions. Journal of Optimization Theory and Applications, 188(1):192–219, 2021

[3] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 1994

[4] V. Goyal and J. Grand-Clément. A first-order approach to accelerated value iteration. Operations Research, 71(2):517–535, 2022.

[5] Su, W., Boyd, S., and Candès, E. J.  A differential equation for modeling Nesterov’s accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17(153):1–43, 2016.

[6] J. J. Suh, J. Park, and E. K. Ryu. Continuous-time Analysis of Anchor Acceleration arXiv:2304.00771, 2023.

[7] J. Park and E. K. Ryu. Exact optimal accelerated complexity for fixed-point iterations. International Conference on Machine Learning, 2022.

Meta-review: This paper applied the anchoring mechanism rooted in fixed point theory to Value Iteration and showed improved rates in terms of the Bellman errors. While the results are perhaps not too surprising from optimization perspectives, all reviewers find the contributions solid and valuable given the importance of value iteration in RL.  

Therefore, acceptance is recommended, though I strongly suggest the authors to explicitly discuss the key limitations of this work as identified by reviewers in the revision : (1) lack of empirical justification of the advantages of anchored VI , (2) worse bounds in terms of distance to optimal values, (3) challenges for stochastic extensions, etc. Please also be rigorous in terms of the notion of rate, optimality of algorithms.
Decision: Accept (poster)