# Accelerating Value Iteration with Anchoring

Jongmin Lee1 Ernest K. Ryu1,2
1Department of Mathematical Science, Seoul National University
2Interdisciplinary Program in Artificial Intelligence, Seoul National
University

###### 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, where $\gamma$ is the discount factor.
Surprisingly, however, the optimal rate in terms of Bellman error 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 _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\geq 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.

##  1 Introduction

Value Iteration (VI) 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 $\gamma<1$ is used, (exact) VI is a contractive
iteration in the $\left\|{\cdot}\right\|_{\infty}$-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 of Bellman error for the VI
setup was not known, and finding a general acceleration mechanism has been an
open problem. The classical $\mathcal{O}(\gamma^{k})$-rate of VI is inadequate
as many practical setups use $\gamma\approx 1$ or $\gamma=1$ for the discount
factor. (Not to mention that VI may not converge when $\gamma=1$.) Moreover,
most prior works on accelerating VI focused on the Bellman consistency
operator (policy evaluation) as its linearity allows eigenvalue analyses, but
the Bellman optimality operator (control) is the more relevant object in
modern RL.

#### Contribution.

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 “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\geq 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.

###  1.1 Notations and preliminaries

We quickly review basic definitions and concepts of Markov decision processes
(MDP) and reinforcement learning (RL). For further details, refer to standard
references such as [69, 84, 81].

#### Markov Decision Process.

Let $\mathcal{M}(\mathcal{X})$ be the space of probability distributions over
$\mathcal{X}$. Write $(\mathcal{S},\mathcal{A},P,r,\gamma)$ to denote the MDP
with state space $\mathcal{S}$, action space $\mathcal{A}$, transition
probability
$P\colon\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{M}(\mathcal{S})$,
reward $r\colon\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, and
discount factor $\gamma\in(0,1]$. Denote
$\pi\colon\mathcal{S}\rightarrow\mathcal{M}(\mathcal{A})$ for a policy,
$V^{\pi}(s)=\mathbb{E}_{\pi}[\sum^{\infty}_{t=0}\gamma^{t}r(s_{t},a_{t})\,|\,s_{0}=s]$
and
$Q^{\pi}(s,a)=\mathbb{E}_{\pi}[\sum^{\infty}_{t=0}\gamma^{t}r(s_{t},a_{t})\,|\,s_{0}=s,a_{0}=a]$
for $V$\- and $Q$-value functions, where $\mathbb{E}_{\pi}$ denotes the
expected value over all trajectories $(s_{0},a_{0},s_{1},a_{1},\dots)$ induced
by $P$ and $\pi$. We say $V^{\star}$ and $Q^{\star}$ are optimal $V$\- and
$Q$\- value functions if $V^{\star}=\sup_{\pi}V^{\pi}$and
$Q^{\star}=\sup_{\pi}Q^{\pi}$. We say $\pi_{V}^{\star}$ and $\pi_{Q}^{\star}$
are optimal policies if
$\pi_{V}^{\star}=\operatorname*{argmax}_{\pi}{V^{\pi}}$ and
$\pi_{Q}^{\star}=\operatorname*{argmax}_{\pi}{Q^{\pi}}$. (If argmax is not
unique, break ties arbitrarily.)

#### Value Iteration.

Let $\mathcal{F}(\mathcal{X})$ denote the space of bounded measurable real-
valued functions over $\mathcal{X}$. With the given MDP
$(\mathcal{S},\mathcal{A},P,r,\gamma)$, for $V\in\mathcal{F}(\mathcal{S})$ and
$Q\in\mathcal{F}(\mathcal{S}\times\mathcal{A})$, define the Bellman
consistency operators $T^{\pi}$ as

$\displaystyle T^{\pi}V(s)$
$\displaystyle=\mathbb{E}_{a\sim\pi(\cdot\,|\,s),s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[r(s,a)+\gamma V(s^{\prime})\right],$ $\displaystyle
T^{\pi}Q(s,a)$ $\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a),a^{\prime}\sim\pi(\cdot\,|\,s^{\prime})}\left[Q(s^{\prime},a^{\prime})\right]$

for all $s\in\mathcal{S},a\in\mathcal{A}$, and the Bellman optimality
operators $T^{\star}$ as

$\displaystyle T^{\star}V(s)$
$\displaystyle=\sup_{a\in\mathcal{A}}\left\\{r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[V(s^{\prime})\right]\right\\},$ $\displaystyle
T^{\star}Q(s,a)$ $\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\sup_{a^{\prime}\in\mathcal{A}}Q(s^{\prime},a^{\prime})\right]$

for all $s\in\mathcal{S},a\in\mathcal{A}$. For notational conciseness, we
write $T^{\pi}V=r^{\pi}+\gamma\mathcal{P}^{\pi}V$ and
$T^{\pi}Q=r+\gamma\mathcal{P}^{\pi}Q$, where
$r^{\pi}(s)=\mathbb{E}_{a\sim\pi(\cdot\,|\,s)}\left[r(s,a)\right]$ is the
reward induced by policy $\pi$ and $\mathcal{P}^{\pi}(s)$ and
$\mathcal{P}^{\pi}(s,a)$ defined as

$\displaystyle\mathcal{P}^{\pi}(s\rightarrow s^{\prime})$
$\displaystyle=\mathrm{Prob}(s\rightarrow
s^{\prime}\,|\,a\sim\pi(\cdot\,|\,s),s^{\prime}\sim P(\cdot\,|\,s,a))$
$\displaystyle\mathcal{P}^{\pi}((s,a)\rightarrow(s^{\prime},a^{\prime}))$
$\displaystyle=\mathrm{Prob}((s,a)\rightarrow(s^{\prime},a^{\prime})\,|\,s^{\prime}\sim
P(\cdot\,|\,s,a),a^{\prime}\sim\pi(\cdot\,|\,s^{\prime})),$

are the transition probabilities induced by policy $\pi$. We define VI for
Bellman consistency and optimality operators as

$V^{k+1}=T^{\pi}V^{k},\quad Q^{k+1}=T^{\pi}Q^{k},\quad
V^{k+1}=T^{\star}V^{k},\quad Q^{k+1}=T^{\star}Q^{k}\qquad\text{ for
}k=0,1,\dots,$

where $V^{0},Q^{0}$ are initial points. VI for control, after executing $K$
iterations, returns the near-optimal policy $\pi_{K}$ as a greedy policy
satisfying

$T^{\pi_{K}}V^{K}=T^{\star}V^{K},\quad T^{\pi_{K}}Q^{K}=T^{\star}Q^{K}.$

For $\gamma<1$, 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^{\pi}$, $Q^{\pi},V^{\star}$, and $Q^{\star}$ with
$\mathcal{O}(\gamma^{k})$-rate. For notational unity, we use the symbol $U$
when both $V$ and $Q$ can be used. Since
$\left\|{TU^{k}-U^{k}}\right\|_{\infty}\leq\left\|{TU^{k}-U^{\star}}\right\|_{\infty}+\left\|{U^{k}-U^{\star}}\right\|_{\infty}\leq(1+\gamma)\left\|{U^{k}-U^{\star}}\right\|_{\infty}$,
VI exhibits the rate on the Bellman error:

$\displaystyle\left\|{TU^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq(1+\gamma)\gamma^{k}\left\|{U^{0}-U^{\star}}\right\|_{\infty}\qquad\text{
for }k=0,1,\dots,$ ($1$)

where $T$ is Bellman consistency or optimality operator, $U^{0}$ is a starting
point, and $U^{\star}$ is fixed point of $T$. We say $V\leq V^{\prime}$ or
$Q\leq Q^{\prime}$ if $V(s)\leq V^{\prime}(s)$ or $Q(s,a)\leq Q^{\prime}(s,a)$
for all $s\in\mathcal{S}$ and $a\in\mathcal{A}$, respectively.

#### Fixed-point iterations.

Given an operator $T$, we say $x^{\star}$ is fixed point if
$Tx^{\star}=x^{\star}$. Since Banach [5], the standard fixed-point iteration

$x^{k+1}=Tx^{k}\qquad\text{ for }k=0,1,\dots$

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}=\beta_{k+1}x^{0}+(1-\beta_{k+1})Tx^{k}\qquad\text{ for }k=0,1,\dots,$

where $x^{0}$ is an initial point and
$\\{\beta_{k}\\}_{k\in\mathbf{N}}\in(0,1)$.

###  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 is a line of research that emulates VI by
learning a model of the MDP dynamics [85, 83, 62] and applying a modified
Bellman operator [7, 33]. Asynchronous VI, another variation of VI 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
fixed-point iteration with a contractive operator. The Halpern iteration [39]
converges for nonexpansive operators on Hilbert spaces [96] and uniformly
smooth Banach spaces [70, 97]. (To clarify, the $\|\cdot\|_{\infty}$-norm in
$\mathbb{R}^{n}$ is not uniformly smooth.)

The fixed-point residual $\left\|{Tx_{k}-x_{k}}\right\|$ is a commonly used
error measure for fixed-point problems. In general normed spaces, the Halpern
iteration was shown to exhibit $\mathcal{O}(1/\log(k))$-rate for (nonlinear)
nonexpansive operators [48] and $\mathcal{O}(1/k)$-rate for linear
nonexpansive operators [17] on the fixed-point residual. In Hilbert spaces,
[72] first established a $\mathcal{O}(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 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 a 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 a 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 accelerate algorithms for minimax optimization and
fixed-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 a 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
$\Omega(1/k^{1-\sqrt{2/q}})$ lower bound on distance to solution for Halpern
iteration with a nonexpansive operator in $q$-uniformly smooth Banach spaces.
In [17], a $\Omega(1/k)$ lower bound on the fixed-point residual for the
general Mann iteration with a nonexpansive linear operator, which includes
standard fixed-point iteration and Halpern iterations, in the
$\ell^{\infty}$-space was provided. In Hilbert spaces, [65] showed exact
complexity lower bound on fixed-point residual for deterministic fixed-point
iterations with $\gamma$-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.

##  2 Anchored Value Iteration

Let $T$ be a $\gamma$-contractive (in the $\|\cdot\|_{\infty}$-norm) Bellman
consistency or optimality operator. The _Anchored Value Iteration_ (Anc-VI) is

$\displaystyle U^{k}=\beta_{k}U^{0}+(1-\beta_{k})TU^{k-1}\qquad$ (Anc-VI)

for $k=1,2,\dots,$ where $\beta_{k}=1/(\sum_{i=0}^{k}\gamma^{-2i})$ and
$U^{0}$ is an initial point. In this section, we present accelerated
convergence rates of Anc-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 $\pi_{K}$ as a greedy policy satisfying
$T^{\pi_{K}}U^{K}=T^{\star}U^{K}$ after executing $K$ iterations.

Notably, Anc-VI obtains the next iterate as a convex combination between the
output of $T$ and the starting point $U^{0}$. We call the $\beta_{k}U_{0}$
term the _anchor term_ since, loosely speaking, it serves to pull the iterates
toward the starting point $U_{0}$. The strength of the anchor mechanism
diminishes as the iteration progresses since $\beta_{k}$ is a decreasing
sequence.

The anchor mechanism was introduced [39, 72, 49, 65, 17, 48] for general
nonexpansive operators and $\|\cdot\|_{2}$-nonexpansive and contractive
operators. The optimal method for $\|\cdot\|_{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 to Anc-
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
$\|\cdot\|_{2}$-nonexpansive 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 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 it 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 $0<\gamma<1$ be the discount factor and $\pi$ be a policy. Let $T^{\pi}$
be the Bellman consistency operator for $V$ or $Q$. Then, Anc-VI exhibits the
rate

$\displaystyle\left\|{T^{\pi}U^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-U^{\pi}}\right\|_{\infty}$
$\displaystyle=\left({\frac{2}{k+1}+\frac{k-1}{k+1}\epsilon+O(\epsilon^{2})}\right)\left\|{U^{0}-U^{\pi}}\right\|_{\infty}\qquad\text{
for }k=0,1,\dots,$

where $\epsilon=1-\gamma$ and the big-$\mathcal{O}$ notation considers the
limit $\epsilon\rightarrow 0$. If, furthermore, $U^{0}\leq T^{\pi}U^{0}$ or
$U^{0}\geq T^{\pi}U^{0}$, then Anc-VI exhibits the rate

$\displaystyle\left\|{T^{\pi}U^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-U^{\pi}}\right\|_{\infty}$
$\displaystyle=\left({\frac{1}{k+1}+\frac{k}{k+1}\epsilon+O(\epsilon^{2})}\right)\left\|{U^{0}-U^{\pi}}\right\|_{\infty}\qquad\text{
for }k=0,1,\dots.$

If $\gamma\geq\frac{1}{2}$, both rates of Theorem 1 are strictly faster than
the standard rate ($1$) of VI, since

$\displaystyle\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}=\gamma^{k}\frac{\left({1-\gamma^{2}}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({1-\gamma^{2k+2}}\right)}<\gamma^{k}(1+\gamma).$

The second rate of Theorem 1, which has the additional requirement, is faster
than the standard rate ($1$) of VI for all $0<\gamma<1$. Interestingly, in the
$\gamma\approx 1$ regime, Anc-VI achieves $\mathcal{O}(1/k)$-rate while VI has
a $\mathcal{O}(1)$-rate. We briefly note that the condition $U^{0}\leq TU^{0}$
and $U^{0}\geq TU^{0}$ 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 1 while deferring
the full description to Appendix B. In the outline, we highlight a particular
step, labeled $\blacktriangle$, that crucially relies on the linearity of the
Bellman consistency operator. In the analysis for the Bellman optimality
operator of Theorem 2, resolving the $\blacktriangle$ step despite the
nonlinearity is the key technical challenge.

###### Proof outline of Theorem 1.

Recall that we can write Bellman consistency operator as
$T^{\pi}V=r^{\pi}+\gamma\mathcal{P}^{\pi}V$ and
$T^{\pi}Q=r+\gamma\mathcal{P}^{\pi}Q$. Since $T^{\pi}$ is a linear
operator111Arguably, $T^{\pi}$ is affine, not linear, but we follow the
convention of [69] say $T^{\pi}$ is linear., we get

$\displaystyle T^{\pi}U^{k}-U^{k}$
$\displaystyle=T^{\pi}U^{k}-(1-\beta_{k})T^{\pi}U^{k-1}-\beta_{k}T^{\pi}U^{\pi}-\beta_{k}(U^{0}-U^{\pi})$
$\displaystyle\stackrel{{\scriptstyle\blacktriangle}}{{=}}\gamma\mathcal{P}^{\pi}(U^{k}-(1-\beta_{k})U^{k-1}-\beta_{k}U^{\pi})-\beta_{k}(U^{0}-U^{\pi})$
$\displaystyle=\gamma\mathcal{P}^{\pi}(\beta_{k}(U^{0}-U^{\pi})+(1-\beta_{k})(T^{\pi}U^{k-1}-U^{k-1}))-\beta_{k}(U^{0}-U^{\pi})$
$\displaystyle=\sum_{i=1}^{k}\left[\left({\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right)\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{k-i+1}(U^{0}-U^{\pi})\right]$
$\displaystyle\quad-\beta_{k}(U^{0}-U^{\pi})+\left({\Pi^{k}_{j=1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{k+1}(U^{0}-U^{\pi}),$

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 $\left\|{\cdot}\right\|_{\infty}$-norm of both sides, we conclude

$\displaystyle\left\|{T^{\pi}U^{k}-U^{k}}\right\|_{\infty}\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-U^{\pi}}\right\|_{\infty}.$

∎

###  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

$\displaystyle\hat{T}^{\star}V(s)$
$\displaystyle=\inf_{a\in\mathcal{A}}\left\\{r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[V(s^{\prime})\right]\right\\}$
$\displaystyle\hat{T}^{\star}Q(s,a)$
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\inf_{a^{\prime}\in\mathcal{A}}Q(s^{\prime},a^{\prime})\right],$

for all $s\in\mathcal{S}$ and $a\in\mathcal{A}$. (The sup is replaced with a
inf.) When $0<\gamma<1$, the Bellman anti-optimality operator is
$\gamma$-contractive and has a unique fixed point $\hat{U}^{\star}$ by the
exact same arguments that establish $\gamma$-contractiveness of the standard
Bellman optimality operator.

######  Theorem 2.

Let $0<\gamma<1$ be the discount factor. Let $T^{\star}$ and $\hat{T}^{\star}$
respectively be the Bellman optimality and anti-optimality operators for $V$
or $Q$. Let $U^{\star}$ and $\hat{U}^{\star}$ respectively be the fixed points
of $T^{\star}$ and $\hat{T}^{\star}$. Then, Anc-VI exhibits the rate

$\displaystyle\left\|{T^{\star}U^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\max{\left\\{\left\|{U^{0}-U^{\star}}\right\|_{\infty},\left\|{U^{0}-\hat{U}^{\star}}\right\|_{\infty}\right\\}}$

for $k=0,1,\dots$. If, furthermore, $U^{0}\leq T^{\star}U^{0}$ or $U^{0}\geq
T^{\star}U^{0}$, then Anc-VI exhibits the rate

$\displaystyle\left\|{T^{\star}U^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-U^{\star}}\right\|_{\infty}\quad\,\,\text{if}\,\,U^{0}\leq
T^{\star}U^{0}$ $\displaystyle\left\|{T^{\star}U^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-\hat{U}^{\star}}\right\|_{\infty}\quad\,\,\text{if}\,\,U^{0}\geq
T^{\star}U^{0}$

for $k=0,1,\dots$.

Anc-VI with the Bellman optimality operator exhibits the same accelerated
convergence rate as Anc-VI with the Bellman consistency operator. As in
Theorem 1, the rate of Theorem 2 also becomes $\mathcal{O}(1/k)$ when
$\gamma\approx 1$, while VI has a $\mathcal{O}(1)$-rate.

###### Proof outline of Theorem 2.

The key technical challenge of the proof comes from the fact that the Bellman
optimality operator is non-linear. Similar to the Bellman consistency operator
case, we have

$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle=T^{\star}U^{k}-(1-\beta_{k})T^{\star}U^{k-1}-\beta_{k}T^{\star}U^{\star}-\beta_{k}(U^{0}-U^{\star})$
$\displaystyle\stackrel{{\scriptstyle\blacktriangle}}{{\leq}}\gamma\mathcal{P}^{\pi_{k}}\left({U^{k}-(1-\beta_{k})U^{k-1}-\beta_{k}U^{\star}}\right)-\beta_{k}(U^{0}-U^{\star})$
$\displaystyle=\gamma\mathcal{P}^{\pi_{k}}(\beta_{k}\left({U^{0}-U^{\star}}\right)+(1-\beta_{k})(T^{\star}U^{k-1}-U^{k-1}))-\beta_{k}(U^{0}-U^{\star})$
$\displaystyle\leq\sum_{i=1}^{k}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\mathcal{P}^{\pi_{l}}}\right)(U^{0}-U^{\star})\right]$
$\displaystyle\quad-\beta_{k}(U^{0}-U^{\star})+\left({\Pi^{k}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k}\gamma\mathcal{P}^{\pi_{l}}}\right)(U^{0}-U^{\star}),$

where $\pi_{k}$ is the greedy policy satisfying
$T^{\pi_{k}}U^{k}=T^{\star}U^{k}$, we define
$\Pi^{i}_{l=k}\gamma\mathcal{P}^{\pi_{l}}=\gamma\mathcal{P}^{\pi_{k}}\gamma\mathcal{P}^{\pi_{k-1}}\cdots\gamma\mathcal{P}^{\pi_{i}}$,
and last inequality follows by induction and monotonicity of Bellman
optimality operator. The key step $\blacktriangle$ uses greedy policies
$\\{\pi_{l}\\}_{l=0,1,\dots,k}$, 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 Hahn–Banach extension theorem to overcome this technicality. The
full argument is provided in Appendix B.

To lower bound $T^{\star}U^{k}-U^{k}$, we use a similar line of reasoning with
the Bellman anti-optimality operator. Combining the upper and lower bounds of
$T^{\star}U^{k}-U^{k}$, we conclude the accelerated rate of Theorem 2. ∎

For $\gamma<1$, the rates of Theorems 1 and 2 can be translated to a bound on
the distance to solution:

$\displaystyle\left\|{U^{k}-U^{\star}}\right\|_{\infty}\leq\gamma^{k}\frac{\left({1+\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({1-\gamma^{2k+2}}\right)}\left\|{U^{0}-U^{\star}}\right\|_{\infty}$

for $k=1,2,\dots$. This $O(\gamma^{k})$ rate is worse than the rate of
(classical) VI by a constant factor. Therefore, Anc-VI is better than VI in
terms of the Bellman error, but it is not better than VI in terms of distance
to solution.

##  3 Convergence when $\gamma=1$

Undiscounted MDPs are 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 is a nonexpansive (not contractive)
fixed-point iteration and may not convergence to a 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,222 As a specific example, the
classical policy gradient theorem [82] calls for the use of $\nabla
J(\theta)=\mathbb{E}\left[\sum^{\infty}_{t=0}\gamma^{t}\nabla_{\theta}\log\pi_{\theta}(a_{t}\,|\,s_{t})Q^{\phi}_{\gamma}(s_{t},a_{t})\right]$,
but many modern deep policy gradient methods use $\gamma=1$ in the first
instance of $\gamma$ (so $\gamma^{t}=1$) while using $\gamma<1$ in
$Q^{\phi}_{\gamma}(s_{t},a_{t})$ [63]. and this empirical practice makes the
theoretical analysis with $\gamma=1$ relevant.

In this section, we show that Anc-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, we show that
fixed points, if one exists, can be found, and we therefore argue that the
inability to find fixed points should not be considered an obstacle in
studying the $\gamma=1$ setup.

We first state our convergence result for finite state-action spaces.

######  Theorem 3.

Let $\gamma=1$. Let $T\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be the
nonexpansive Bellman consistency or optimality operator for $V$ or $Q$. Assume
a fixed point exists (not necessarily unique). If, $U^{0}\leq TU^{0}$, then
Anc-VI exhibits the rate

$\displaystyle\left\|{TU^{k}-U^{k}}\right\|_{\infty}\leq\frac{1}{k+1}\left\|{U^{0}-U^{\star}}\right\|_{\infty}\qquad\text{
for }k=0,1,\dots.$

for any fixed point $U^{\star}$ satisfying $U^{0}\leq U^{\star}$. Furthermore,
$U^{k}\rightarrow U^{\infty}$ for some fixed point $U^{\infty}$.

If rewards are nonnegative, then the condition $U^{0}\leq TU^{0}$ is satisfied
with $U^{0}=0$. So, under this mild condition, Anc-VI with $\gamma=1$
converges with $\mathcal{O}(1/k)$-rate on the Bellman error. To clarify, the
convergence $U^{k}\rightarrow U^{\infty}$ has no rate, i.e.,
$\|U^{k}-U^{\infty}\|_{\infty}=o(1)$, while
$\left\|{TU^{k}-U^{k}}\right\|_{\infty}=\mathcal{O}(1/k)$. In contrast,
standard VI does not guarantee convergence in this setup.

We also point out that the convergence of Bellman error does not immediately
imply point convergence, i.e., $TU^{k}-U^{k}\rightarrow 0$ does not
immediately imply $U^{k}\rightarrow U^{\star}$, when $\gamma=1$. Rather, we
show (i) $U^{k}$ is a bounded sequence, (ii) any convergent subsequence
$U^{k_{j}}$ converges to a fixed point $U^{\infty}$, and (iii) $U^{k}$ is
elementwise monotonically nondecreasing and therefore has a single limit.

Next, we state our convergence result for general state-action spaces.

######  Theorem 4.

Let $\gamma=1$. Let the state and action spaces be general (possibly infinite)
sets. Let $T$ be the nonexpansive Bellman consistency or optimality operator
for $V$ or $Q$, and assume $T$ is well defined.333Well-definedness of $T$
requires a $\sigma$-algebra 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, etc. Assume a fixed
point exists (not necessarily unique). If $U^{0}\leq TU^{0}$, then Anc-VI
exhibits the rate

$\displaystyle\left\|{TU^{k}-U^{k}}\right\|_{\infty}\leq\frac{1}{k+1}\left\|{U^{0}-U^{\star}}\right\|_{\infty}\qquad\text{
for }k=0,1,\dots$

for any fixed point $U^{\star}$ satisfying $U^{0}\leq U^{\star}$. Furthermore,
$U^{k}\rightarrow U^{\infty}$ pointwise monotonically for some fixed point
$U^{\infty}$.

The convergence $U^{k}\rightarrow U^{\infty}$ pointwise in infinite state-
action spaces is, in our view, a non-trivial contribution. When the state-
action space is finite, pointwise convergence directly implies convergence in
$\|\cdot\|_{\infty}$, 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^{k}\rightarrow U^{\infty}$ pointwise does not necessarily imply
$U^{k}\rightarrow U^{\infty}$ in $\|\cdot\|_{\infty}$.

##  4 Complexity lower bound

We now present a complexity lower bound establishing optimality of Anc-VI.

######  Theorem 5.

Let $k\geq 0$, $n\geq k+2$, $0<\gamma\leq 1$, and $U^{0}\in\mathbb{R}^{n}$.
Then there exists an MDP with $|\mathcal{S}|=n$ and $|\mathcal{A}|=1$ (which
implies the Bellman consistency and optimality operator for V and Q all
coincide as $T\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$) such that $T$
has a fixed point $U^{\star}$ satisfying $U^{0}\leq U^{\star}$ and

$\left\|{TU^{k}-U^{k}}\right\|_{\infty}\geq\frac{\gamma^{k}}{\sum_{i=0}^{k}\gamma^{i}}\left\|{U^{0}-U^{\star}}\right\|_{\infty}$

for any iterates $\\{U^{i}\\}^{k}_{i=0}$ satisfying

$U^{i}\in
U^{0}+\mathrm{span}\\{TU^{0}-U^{0},TU^{1}-U^{1},\dots,TU^{i-1}-U^{i-1}\\}\qquad\text{
for }i=1,\dots,k.$

###### Proof outline of Theorem 5.

Without loss of generality, assume $n=k+2$ and $U^{0}=0$. Consider the MDP
$(\mathcal{S},\mathcal{A},P,r,\gamma)$ such that

$\displaystyle\mathcal{S}=\\{s_{1},\dots,s_{k+2}\\},\quad\mathcal{A}=\\{a_{1}\\},\quad
P(s_{i}\,|\,s_{j},a_{1})=\mathds{1}_{\\{i=j=1,\,j=i+1\\}},\quad
r(s_{i},a_{1})=\mathds{1}_{\\{i=2\\}}.$

Then,
$T=\gamma\mathcal{P}^{\pi}U+[0,1,0,\dots,0]^{\intercal},U^{\star}=[0,1,\gamma,\dots,\gamma^{k}]^{\intercal}$,
and $\left\|{U^{0}-U^{\star}}\right\|_{\infty}=1$. Under the span condition,
we can show that $\left({U^{k}}\right)_{1}=\left({U^{k}}\right)_{k+2}=0$.
Then, we get

$\displaystyle
TU^{k}-U^{k}=\left(0,1-\left({U^{k}}\right)_{2},\gamma\left({U^{k}}\right)_{2}-\left({U^{k}}\right)_{3},\dots,\gamma\left({U^{k}}\right)_{k}-\left({U^{k}}\right)_{k+1},\gamma\left({U^{k}}\right)_{k+1}\right)$

and this implies

$\left({TU^{k}-U^{k}}\right)_{1}+\left({TU^{k}-U^{k}}\right)_{2}+\gamma^{-1}\left({TU^{k}-U^{k}}\right)_{3}+\cdots+\gamma^{-k}\left({TU^{k}-U^{k}}\right)_{k+2}=1.$

Taking the absolute value on both sides,

$\displaystyle(1+\cdots+\gamma^{-k})\max_{1\leq i\leq
k+2}{\\{|TU^{k}-U^{k}|_{i}\\}}\geq 1.$

Therefore, we conclude

$\displaystyle\|TU^{k}-U^{k}\|_{\infty}\geq\frac{\gamma^{k}}{\sum_{i=0}^{k}\gamma^{i}}\left\|{U^{0}-U^{\star}}\right\|_{\infty}.$

∎

Note that the case $\gamma=1$ is included in Theorem 5. When $\gamma=1$, the
lower bound of Theorem 5 _exactly_ matches the upper bound of Theorem 3.

Since

$\frac{\gamma^{k}}{\sum_{i=0}^{k}\gamma^{i}}\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\leq\frac{4\gamma^{k}}{\sum_{i=0}^{k}\gamma^{i}}\qquad\text{
for all }0<\gamma<1,$

the lower bound establishes optimality of the second rates Theorems 1 and 2 up
to a constant of factor $4$. Theorem 5 improves upon the prior state-of-the-
art complexity lower bound established in the proof of [37, Theorem 3] by a
factor $1-\gamma^{k+1}$. (In [37, Theorem 3], a 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 $\|U^{0}-U^{\star}\|_{\infty}$,
so we make the dependence explicit, and we 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 a factor of
$1-\gamma^{k+1}$. 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 5 is arguably very natural and is
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 3]. However, designing an
algorithm that breaks the lower bound of Theorem 5 by violating the span
condition remains a possibility. In optimization theory, there is precedence
of lower bounds being broken by violating seemingly natural and minute
conditions [40, 35, 98].

##  5 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 $0<\gamma<1$ and let $T^{\star}$ be the Bellman optimality operator. The
_Approximate Anchored Value Iteration_ (Apx-Anc-VI) is

$\displaystyle\begin{aligned}
U_{\epsilon}^{k}&=T^{\star}U^{k-1}+\epsilon^{k-1}\\\
U^{k}&=\beta_{k}U^{0}+(1-\beta_{k})U_{\epsilon}^{k}\end{aligned}$ (Apx-Anc-VI)

for $k=1,2,\dots,$ where $\beta_{k}=1/(\sum_{i=0}^{k}\gamma^{-2i})$, $U^{0}$
is an initial point, and the $\\{\epsilon^{k}\\}_{k=0}^{\infty}$ is the error
sequence modeling approximate evaluations of $T^{\star}$.

Of course, the classical Approximate Value Iteration (Apx-VI) is

$\displaystyle U^{k}$ $\displaystyle=T^{\star}U^{k-1}+\epsilon^{k-1}$ (Apx-VI)

for $k=1,2,\dots,$ where $U^{0}$ is an initial point.

######  Fact 1 (Classical result, [11, p.333]).

Let $0<\gamma<1$ be the discount factor. Let $T^{\star}$ be the Bellman
optimality for $V$ or $Q$. Let $U^{\star}$ be the fixed point of $T^{\star}$.
Then Apx-VI exhibits the rate

$\displaystyle\left\|{T^{\star}U^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq(1+\gamma)\gamma^{k}\left\|{U^{0}-U^{\star}}\right\|_{\infty}+\left({1+\gamma}\right)\frac{1-\gamma^{k}}{1-\gamma}\max_{0\leq
i\leq k-1}\left\|{\epsilon^{i}}\right\|_{\infty}\,\,\,\text{ for
}k=1,2,\dots.$

######  Theorem 6.

Let $0<\gamma<1$ be the discount factor. Let $T^{\star}$ and $\hat{T}^{\star}$
respectively be the Bellman optimality and anti-optimality operators for $V$
or $Q$. Let $U^{\star}$ and $\hat{U}^{\star}$ respectively be the fixed points
of $T^{\star}$ and $\hat{T}^{\star}$. Then Apx-Anc-VI exhibits the rate

$\displaystyle\left\|{T^{\star}U^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\max{\left\\{\left\|{U^{0}-U^{\star}}\right\|_{\infty},\left\|{U^{0}-\hat{U}^{\star}}\right\|_{\infty}\right\\}}$
$\displaystyle\quad+\frac{1+\gamma}{1+\gamma^{k+1}}\frac{1-\gamma^{k}}{1-\gamma}\max_{0\leq
i\leq k-1}\left\|{\epsilon^{i}}\right\|_{\infty}\qquad\text{ for
}k=1,2,\dots.$

If, furthermore, $U^{0}\geq T^{\star}U^{0}$, then (Apx-Anc-VI) exhibits the
rate

$\displaystyle\left\|{T^{\star}U^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-\hat{U}^{\star}}\right\|_{\infty}+\frac{1+\gamma}{1+\gamma^{k+1}}\frac{1-\gamma^{k}}{1-\gamma}\max_{0\leq
i\leq k-1}\left\|{\epsilon^{i}}\right\|_{\infty}$

for $k=1,2,\dots$.

The dependence on $\max\left\|{\epsilon_{i}}\right\|_{\infty}$ of Apx-Anc-VI
is no worse than that of Apx-VI. In this sense, Apx-Anc-VI is robust against
evaluation errors of the Bellman operator, just as much as the standard Apx-
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
Gauss–Seidel-type updates in finite state-action spaces. Let $0<\gamma<1$ and
let $T^{\star}\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be the Bellman
optimality operator. Define
$T_{GS}^{\star}\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ as

$T_{GS}^{\star}=T^{\star}_{n}\cdots T^{\star}_{2}T^{\star}_{1},$

where $T_{j}^{\star}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is defined as

$\displaystyle
T^{\star}_{j}(U)=(U_{1},\dots,U_{j-1},\left({T^{\star}(U)}\right)_{j},U_{j+1},\dots,U_{n})$

for $j=1,\dots,n$.

######  Fact 2.

[Classical result, [69, Theorem 6.3.4]] $T_{GS}^{\star}$ is a
$\gamma$-contractive operator and has the same fixed point as $T^{\star}$.

The _Gauss–Seidel Anchored Value Iteration_ (GS-Anc-VI) is

$\displaystyle U^{k}$
$\displaystyle=\beta_{k}U^{0}+(1-\beta_{k})T_{GS}^{\star}U^{k-1}$ (GS-Anc-VI)

for $k=1,2,\dots,$ where $\beta_{k}=1/(\sum_{i=0}^{k}\gamma^{-2i})$ and
$U^{0}$ is an initial point.

######  Theorem 7.

Let the state and action spaces be finite sets. Let $0<\gamma<1$ be the
discount factor. Let $T^{\star}$ and $\hat{T}^{\star}$ respectively be the
Bellman optimality and anti-optimality operators for $V$ or $Q$. Let
$U^{\star}$ and $\hat{U}^{\star}$ respectively be the fixed points of
$T^{\star}$ and $\hat{T}^{\star}$. Then GS-Anc-VI exhibits the rate

$\displaystyle\left\|{T_{GS}^{\star}U^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\max{\left\\{\left\|{U^{0}-U^{\star}}\right\|_{\infty},\left\|{U^{0}-\hat{U}^{\star}}\right\|_{\infty}\right\\}}$

for $k=0,1,\dots$. If, furthermore, $U^{0}\leq T_{GS}^{\star}U^{0}$ or
$U^{0}\geq T_{GS}^{\star}U^{0}$, then GS-Anc-VI exhibits the rate

$\displaystyle\left\|{T_{GS}^{\star}U^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-U^{\star}}\right\|_{\infty}\quad\,\,\text{if}\,\,U^{0}\leq
T_{GS}^{\star}U^{0}$
$\displaystyle\left\|{T_{GS}^{\star}U^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-\hat{U}^{\star}}\right\|_{\infty}\quad\,\,\text{if}\,\,U^{0}\geq
T_{GS}^{\star}U^{0}$

for $k=0,1,\dots$.

We point out that GS-Anc-VI cannot be directly extended to infinite action
spaces since Hahn–Banach extension theorem is not applicable in the
Gauss–Seidel setup. Furthermore, we note that a similar analysis can be
carried out for GS-Anc-VI with the Bellman consistency operator.

##  7 Conclusion

We show that the classical value iteration (VI) is, in fact, suboptimal and
that the anchoring mechanism accelerates VI to be optimal in the sense that
the accelerated rate matches a complexity lower bound up to a constant factor
of $4$. We also show that the accelerated iteration provably converges to a
fixed point even when $\gamma=1$, if a fixed point exists. Being able to
provide a substantive improvement upon the classical VI is, in our view, a
surprising contribution.

One direction of future work is to study the empirical effectiveness of Anc-
VI. Another direction is to analyze Anc-VI in a model-free setting and, more
broadly, to investigate the effectiveness of the anchor mechanism in more
practical RL methods.

Our results lead us to believe that many of the classical foundations of
dynamic programming and reinforcement learning may be improved with a 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 a
similar line of investigation on iteration complexity.

## Acknowledgments and Disclosure of Funding

This work was supported by the the Information & communications Technology
Planning & Evaluation (IITP) grant funded by the Korea government(MSIT)
[NO.2021-0-01343, Artificial Intelligence Graduate School Program (Seoul
National University)] and the Samsung Science and Technology Foundation
(Project Number SSTF-BA2101-02). We thank Jisun Park for providing valuable
feedback.

## 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–232, 2022.
  * [2] D. G. Anderson.  Iterative procedures for nonlinear integral equations.  Journal of the Association for Computing Machinery, 12(4):547–560, 1965.
  * [3] D. 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–181, 1922.
  * [6] M. Barré, A. Taylor, and A. d’Aspremont.  Convergence of a 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 J. Tsitsiklis.  Parallel and Distributed Computation: Numerical Methods.  Athena Scientific, 2015.
  * [10] D. P. Bertsekas.  Dynamic Programming and Optimal Control, volume II.  4th edition, 2012.
  * [11] D. P. Bertsekas and J. N. Tsitsiklis.  Neuro-Dynamic Programming.  Athena Scientific, 1995.
  * [12] W. Bowen, X. Huaqing, Z. Lin, L. Yingbin, and Z. Wei.  Finite-time theory for momentum Q-learning.  Conference on Uncertainty in Artificial Intelligence, 2021.
  * [13] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford.  Lower bounds for finding stationary points I.  Mathematical Programming, 184(1–2):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’équations simultanées.  Comptes rendus de 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):2639–2646, 2021\.
  * [17] J. P. Contreras and R. Cominetti.  Optimal error bounds for non-expansive fixed-point iterations in normed spaces.  Mathematical Programming, 199(1–2):343–374, 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. P. De Farias and B. Van Roy.  On the existence of fixed points for approximate value iteration and temporal-difference learning.  Journal of Optimization theory and Applications, 105:589–608, 2000\.
  * [20] J. Diakonikolas.  Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities.  Conference on Learning Theory, 2020.
  * [21] J. Diakonikolas and P. Wang.  Potential function-based framework for minimizing gradients in convex and min-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-based 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] Y. 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(1–2):321–351, 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, 6:503–556, 2005.
  * [30] D. Ernst, M. Glavic, P. Geurts, and L. Wehenkel.  Approximate value iteration in the reinforcement 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.  International Conference on 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.
  * [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] G. J. Gordon.  Stable function approximation in dynamic programming.  International Conference on Machine Learning, 1995.
  * [37] V. Goyal and J. Grand-Clément.  A first-order approach to accelerated value iteration.  Operations Research, 71(2):517–535, 2022.
  * [38] J. Grand-Clément.  From convex optimization to MDPs: A review of first-order, second-order and quasi-newton methods for MDPs.  arXiv:2104.10677, 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 finite-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. Iutzeler 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, 190(1–2):57–87, 2021.
  * [44] D. Kim and J. A. Fessler.  Optimized first-order methods for smooth convex minimization.  Mathematical Programming, 159(1–2):81–107, 2016.
  * [45] 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.
  * [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-nonconcave 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):1680–1691, 2007.
  * [49] F. Lieder.  On the convergence rate of the Halpern-iteration.  Optimization Letters, 15(2):405–418, 2021.
  * [50] M. Lutter, S. Mannor, J. Peters, D. Fox, and A. Garg.  Value iteration in continuous actions, states and time.  International Conference on Machine Learning, 2021.
  * [51] P.-E. Maingé.  Convergence theorems for inertial KM-type algorithms.  Journal of Computational and Applied Mathematics, 219(1):223–236, 2008.
  * [52] A. massoud Farahmand, M. Ghavamzadeh, C. Szepesvári, and S. Mannor.  Regularized fitted Q-iteration for planning in continuous-space Markovian decision problems.  American Control Conference, 2009.
  * [53] H. B. McMahan and G. J. Gordon.  Fast exact planning in Markov decision processes.  International 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, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis.  Human-level control through deep reinforcement learning.  Nature, 518(7540):529–533, 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–857, 2008.
  * [58] A. S. Nemirovski.  Information-based complexity of linear operator equations.  Journal of Complexity, 8(2):153–175, 1992.
  * [59] Y. Nesterov.  Lectures on Convex Optimization.  Springer, 2nd edition, 2018.
  * [60] Y. Nesterov, A. Gasnikov, S. 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. E. Nesterov.  A method for solving the convex programming problem with convergence rate $\mathcal{O}(1/k^{2})$.  Doklady Akademii Nauk SSSR, 269(3):543–547, 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 P. Thomas.  Is the policy gradient a gradient?  International Conference on Autonomous Agents and Multiagent Systems, 2020.
  * [64] C. Park, J. Park, and E. K. Ryu.  Factor-$\sqrt{2}$ 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-point 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.  arXiv:1905.10899, 2019.
  * [72] S. Sabach and S. Shtern.  A first order method for solving convex bilevel optimization problems.  SIAM Journal on 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.
  * [74] D. Scieur, A. d’Aspremont, and F. Bach.  Regularized nonlinear acceleration.  Mathematical Programming, 179(1–2):47–83, 2020.
  * [75] Y. Shehu.  Convergence rate analysis of inertial Krasnoselskii–Mann type iteration with applications.  Numerical Functional Analysis and Optimization, 39(10):1077–1091, 2018.
  * [76] W. Shi, S. 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–202, 2010.
  * [78] J. J. Suh, J. Park, and E. K. Ryu.  Continuous-time analysis of anchor acceleration.  Neural Information Processing Systems, 2023.
  * [79] K. Sun, Y. Wang, Y. Liu, B. Pan, S. Jui, B. Jiang, L. Kong, et 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] R. S. Sutton and A. 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 reinforcement 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. Szepesvá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] A. Taylor and Y. Drori.  An optimal gradient method for smooth strongly convex minimization.  Mathematical Programming, 199(1-2):557–594, 2023.
  * [87] S. Tosatto, M. Pirotta, C. d’Eramo, 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–202, 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] B. Van Roy.  Performance loss bounds for approximate value iteration with state aggregation.  Mathematics of Operations Research, 31(2):234–244, 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, B. 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 on Numerical Analysis, 49(4):1715–1735, 2011.
  * [94] C. J. Watkins and P. Dayan.  Q-learning.  Machine Learning, 8:279–292, 1992.
  * [95] D. Wingate, K. D. Seppi, and S. Mahadevan.  Prioritization methods for accelerating MDP solvers.  Journal of Machine Learning Research, 6(25):851–881, 2005.
  * [96] R. Wittmann.  Approximation of fixed points of nonexpansive mappings.  Archiv der Mathematik, 58(5):486–491, 1992.
  * [97] H.-K. Xu.  Iterative algorithms for nonlinear operators.  Journal of the London Mathematical Society, 66(1):240–256, 2002\.
  * [98] T. Yoon and E. K. Ryu.  Accelerated algorithms for smooth convex-concave minimax problems with $\mathcal{O}(1/k^{2})$ 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.11093, 2022.
  * [100] Y. Zeng, F. Feng, and W. Yin.  AsyncQVI: Asynchronous-parallel 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 on 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.

##  Appendix 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 $0<\gamma\leq 1$. If $U\leq\tilde{U}$, then
$T^{\pi}U\leq T^{\pi}\tilde{U},T^{\star}U\leq T^{\star}\tilde{U}$.

######  Lemma 2.

Let $0<\gamma\leq 1$. For any policy $\pi$, $\mathcal{P}^{\pi}$ is a
nonexpansive linear operator such that if $U\leq\tilde{U}$,
$\mathcal{P}^{\pi}U\leq\mathcal{P}^{\pi}\tilde{U}$.

###### Proof.

If $r(s,a)=0$ for all $s\in\mathcal{S}$ and $a\in\mathcal{A}$,
$T^{\pi}=\gamma\mathcal{P}^{\pi}$. Then by Lemma 1 and $\gamma$-contraction of
$T^{\pi}$, we have the desired result. ∎

######  Lemma 3.

Let $0<\gamma<1$. Let $T^{\star}$ and $\hat{T}^{\star}$ respectively be the
Bellman optimality and anti-optimality operators. Let $U^{\star}$ and
$\hat{U}^{\star}$ respectively be the fixed points of $T^{\star}$ and
$\hat{T}^{\star}$. Then $\hat{U}^{\star}\leq U^{\star}$.

###### Proof.

By definition, $\hat{U}^{\star}=\hat{T}^{\star}\hat{U}^{\star}\leq
T^{\star}\hat{U}^{\star}$. Thus,
$\hat{U}^{\star}\leq\lim_{m\rightarrow\infty}\left({T^{\star}}\right)^{m}\hat{U}^{\star}=U^{\star}$.
∎

##  Appendix B Omitted proofs in Section 2

First, we prove the following lemma by induction.

######  Lemma 4.

Let $0<\gamma\leq 1$, and if $\gamma=1$, assume a fixed point $U^{\pi}$
exists. For the iterates $\\{U^{k}\\}_{k=0,1,\dots}$ of Anc-VI,

$\displaystyle T^{\pi}U^{k}-U^{k}$
$\displaystyle=\sum_{i=1}^{k}\left[\left({\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right)\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{k-i+1}(U^{0}-U^{\pi})\right]$
$\displaystyle\quad-\beta_{k}(U^{0}-U^{\pi})+\left({\Pi^{k}_{j=1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{k+1}(U^{0}-U^{\pi})$

where $\left({\Pi^{k}_{j=k+1}(1-\beta_{j})}\right)=1$ and $\beta_{0}=1$.

###### Proof.

If $k=0$, we have

$\displaystyle T^{\pi}U^{0}-U^{0}$
$\displaystyle=T^{\pi}U^{0}-U^{\pi}-(U^{0}-U^{\pi})$
$\displaystyle=T^{\pi}U^{0}-T^{\pi}U^{\pi}-(U^{0}-U^{\pi})$
$\displaystyle=\gamma\mathcal{P}^{\pi}\left({U^{0}-U^{\pi}}\right)-(U^{0}-U^{\pi})$

If $k=m$, since $T^{\pi}$ is a linear operator,

$\displaystyle T^{\pi}U^{m}-U^{m}$
$\displaystyle=T^{\pi}U^{m}-(1-\beta_{m})T^{\pi}U^{m-1}-\beta_{m}U^{0}$
$\displaystyle=T^{\pi}U^{m}-(1-\beta_{m})T^{\pi}U^{m-1}-\beta_{m}U^{\pi}-\beta_{m}(U^{0}-U^{\pi})$
$\displaystyle=T^{\pi}U^{m}-(1-\beta_{m})T^{\pi}U^{m-1}-\beta_{m}T^{\pi}U^{\pi}-\beta_{m}(U^{0}-U^{\pi})$
$\displaystyle=\gamma\mathcal{P}^{\pi}(U^{m}-(1-\beta_{m})U^{m-1}-\beta_{m}U^{\pi})-\beta_{m}(U^{0}-U^{\pi})$
$\displaystyle=\gamma\mathcal{P}^{\pi}(\beta_{m}(U^{0}-U^{\pi})+(1-\beta_{m})(T^{\pi}U^{m-1}-U^{m-1}))-\beta_{m}(U^{0}-U^{\pi})$
$\displaystyle=(1-\beta_{m})\gamma\mathcal{P}^{\pi}\sum_{i=1}^{m-1}\left[\left({\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right)\left({\Pi^{m-1}_{j=i+1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{m-1-i+1}(U^{0}-U^{\pi})\right]$
$\displaystyle\quad-(1-\beta_{m})\gamma\mathcal{P}^{\pi}\beta_{m-1}(U^{0}-U^{\pi})+(1-\beta_{m})\gamma\mathcal{P}^{\pi}\left({\Pi^{m-1}_{j=1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{m}(U^{0}-U^{\pi})$
$\displaystyle\quad+\beta_{m}\gamma\mathcal{P}^{\pi}(U^{0}-U^{\pi})-\beta_{m}(U^{0}-U^{\pi})$
$\displaystyle=\sum_{i=1}^{m-1}\left[\left({\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right)\left({\Pi^{m}_{j=i+1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{m-i+1}(U^{0}-U^{\pi})\right]$
$\displaystyle\quad-\beta_{m-1}(1-\beta_{m})\gamma\mathcal{P}^{\pi}(U^{0}-U^{\pi})+\beta_{m}\gamma\mathcal{P}^{\pi}(U^{0}-U^{\pi})$
$\displaystyle\quad-\beta_{m}(U^{0}-U^{\pi})+\left({\Pi^{m}_{j=1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{m+1}(U^{0}-U^{\pi})$
$\displaystyle=\sum_{i=1}^{m}\left[\left({\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right)\left({\Pi^{m}_{j=i+1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{m-i+1}(U^{0}-U^{\pi})\right]$
$\displaystyle\quad-\beta_{m}(U^{0}-U^{\pi})+\left({\Pi^{m}_{j=1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{m+1}(U^{0}-U^{\pi})$

∎

Now, we prove the first rate of Theorem 1.

###### Proof of first rate in Theorem 1.

Taking $\left\|{\cdot}\right\|_{\infty}$-norm both sides of equality in Lemma
4, we get

$\displaystyle\left\|{T^{\pi}U^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq\sum_{i=1}^{k}\left|\beta_{i}-\beta_{i-1}(1-\beta_{i})\right|\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left\|{\left({\gamma\mathcal{P}^{\pi}}\right)^{k-i+1}(U^{0}-U^{\pi})}\right\|_{\infty}$
$\displaystyle\quad+\beta_{k}\left\|{U^{0}-U^{\pi}}\right\|_{\infty}+\left({\Pi^{k}_{i=1}(1-\beta_{i})}\right)\left\|{\left({\gamma\mathcal{P}^{\pi}}\right)^{k+1}(U^{0}-U^{\pi})}\right\|_{\infty}$
$\displaystyle\leq\bigg{(}\sum_{i=1}^{k}\gamma^{k-i+1}\left|\beta_{i}-\beta_{i-1}(1-\beta_{i})\right|\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)+\beta_{k}+\gamma^{k+1}\Pi^{k}_{j=1}(1-\beta_{j})\bigg{)}$
$\displaystyle\quad\left\|{U^{0}-U^{\star}}\right\|_{\infty}$
$\displaystyle=\left({\sum_{i=1}^{k}\gamma^{k+i-1}\frac{\left({1-\gamma^{2}}\right)^{2}}{1-\gamma^{(2k+2)}}+\gamma^{2k}\frac{1-\gamma^{2}}{1-\gamma^{2k+2}}+\gamma^{k+1}\frac{1-\gamma^{2}}{1-\gamma^{2k+2}}}\right)\left\|{U^{0}-U^{\pi}}\right\|_{\infty}$
$\displaystyle=\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-U^{\pi}}\right\|_{\infty},$

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<\gamma<1$. Let $T$ be Bellman consistency or optimality operator. For
the iterates $\\{U^{k}\\}_{k=0,1,\dots}$ of Anc-VI, if $U^{0}\leq TU^{0}$,
then $U_{k-1}\leq U_{k}\leq TU_{k-1}\leq TU_{k}\leq U^{\star}$ for $1\leq k$.
Also, if $U^{0}\geq TU^{0}$, then $U_{k-1}\geq U_{k}\geq TU_{k-1}\geq
TU_{k}\geq U^{\star}$ for $1\leq k$.

###### Proof.

First, let $U^{0}\leq TU^{0}$. If $k=1$,
$U^{0}\leq\beta_{1}U^{0}+(1-\beta_{1})TU^{0}=U_{1}\ \leq TU^{0}$ by
assumption. Since $U^{0}\leq U^{1}$, $TU^{0}\leq TU^{1}$ by monotonicity of
Bellman consistency and optimality operators.

By induction,

$U^{k}=\beta_{k}U^{0}+(1-\beta_{k})TU^{k-1}\leq TU^{k-1},$

and since $\beta_{k}\leq\beta_{k-1}$,

$\displaystyle\beta_{k}U^{0}+(1-\beta_{k})TU^{k-1}$
$\displaystyle\geq\beta_{k-1}U^{0}+(1-\beta_{k-1})TU^{k-1}$
$\displaystyle\geq\beta_{k-1}U^{0}+(1-\beta_{k-1})TU^{k-2}$
$\displaystyle=U^{k-1}.$

Also, $U^{k-1}\leq U^{k}$ implies $TU^{k-1}\leq TU^{k}$ by monotonicity of
Bellman consistency and optimality operators, and $U^{k}\leq TU^{k}$ implies
that $U^{k}\leq\lim_{m\rightarrow\infty}\left({T}\right)^{m}U^{k}=U^{\star}$
for all $k=0,1,\dots$.

Now, suppose $U^{0}\geq TU^{0}$. If $k=1$,
$U^{0}\geq\beta_{1}U^{0}+(1-\beta_{1})TU^{0}=U_{1}\ \geq TU^{0}$ by
assumption. Since $U^{0}\geq U^{1}$, $TU^{0}\geq TU^{1}$ by monotonicity of
Bellman consistency and optimality operators.

By induction,

$U^{k}=\beta_{k}U^{0}+(1-\beta_{k})TU^{k-1}\geq TU^{k-1},$

and since $\beta_{k}\leq\beta_{k-1}$,

$\displaystyle\beta_{k}U^{0}+(1-\beta_{k})TU^{k-1}$
$\displaystyle\leq\beta_{k-1}U^{0}+(1-\beta_{k-1})TU^{k-1}$
$\displaystyle\leq\beta_{k-1}U^{0}+(1-\beta_{k-1})TU^{k-2}$
$\displaystyle=U^{k-1}.$

Also, $U^{k-1}\geq U^{k}$ implies $TU^{k-1}\geq TU^{k}$ by monotonicity of
Bellman consistency and optimality operators, and $U_{k}\geq TU_{k}$ implies
that $U^{k}\geq\lim_{m\rightarrow\infty}\left({T}\right)^{m}U^{k}=U^{\star}$
for all $k=0,1,\dots$. ∎

Now, we prove following key lemmas.

######  Lemma 6.

Let $0<\gamma\leq 1$, and assume a fixed point $U^{\pi}$ exists if $\gamma=1$.
For the iterates $\\{U^{k}\\}_{k=0,1,\dots}$ of Anc-VI, if $U^{0}\leq
U^{\pi}$,

$\displaystyle T^{\pi}U^{k}-U^{k}$
$\displaystyle\leq\sum_{i=1}^{k}\left[\left({\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right)\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{k-i+1}(U^{0}-U^{\pi})\right]$
$\displaystyle\quad-\beta_{k}(U^{0}-U^{\pi}),$

where $\left({\Pi^{k}_{j=k+1}(1-\beta_{j})}\right)=1$ and $\beta_{0}=1$.

######  Lemma 7.

Let $0<\gamma<1$. For the iterates $\\{U^{k}\\}_{k=0,1,\dots}$ of Anc-VI, if
$U^{0}\geq T^{\pi}U^{0}$,

$\displaystyle T^{\pi}U^{k}-U^{k}$
$\displaystyle\geq\sum_{i=1}^{k}\left[\left({\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right)\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{k-i+1}(U^{0}-U^{\pi})\right]$
$\displaystyle\quad-\beta_{k}(U^{0}-U^{\pi}),$

where $\left({\Pi^{k}_{j=k+1}(1-\beta_{j})}\right)=1$ and $\beta_{0}=1$.

###### Proof of Lemma 6.

If $U^{0}\leq U^{\pi},$ we get

$\displaystyle T^{\pi}U^{k}-U^{k}$
$\displaystyle=\sum_{i=1}^{k}\left[\left({\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right)\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{k-i+1}(U^{0}-U^{\pi})\right]$
$\displaystyle\quad-\beta_{k}(U^{0}-U^{\pi})+\left({\Pi^{k}_{j=1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{k+1}(U^{0}-U^{\pi})$
$\displaystyle\leq\sum_{i=1}^{k}\left[\left({\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right)\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{k-i+1}(U^{0}-U^{\pi})\right]-\beta_{k}(U^{0}-U^{\pi}),$

by Lemma 4 and the fact that
$\left({\Pi^{k}_{j=1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{k+1}(U^{0}-U^{\pi})\leq
0$. ∎

###### Proof of Lemma 7.

If $U^{0}\geq TU^{0}$, $U^{0}-U^{\pi}\geq 0$ by Lemma 5. Hence, by Lemma 4, we
have

$\displaystyle
T^{\pi}U^{k}-U^{k}\geq\sum_{i=1}^{k}\left[\left({\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right)\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{k-i+1}(U^{0}-U^{\pi})\right]-\beta_{k}(U^{0}-U^{\pi}),$

since
$0\leq\left({\Pi^{k}_{j=1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{k+1}(U^{0}-U^{\pi})$.
∎

Now, we prove the second rates of Theorem 1.

###### Proof of second rates in Theorem 1.

Let $0<\gamma<1$. By Lemma 5, if $U^{0}\leq T^{\pi}U^{0}$, then $U^{0}\leq
U^{\pi}$. Hence,

$\displaystyle 0$ $\displaystyle\leq T^{\pi}U^{k}-U^{k}$
$\displaystyle\leq\sum_{i=1}^{k}\left[\left({\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right)\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{k-i+1}(U^{0}-U^{\pi})\right]-\beta_{k}(U^{0}-U^{\pi}),$

by Lemma 6. Taking $\left\|{\cdot}\right\|_{\infty}$-norm both sides, we have

$\left\|{T^{\pi}U^{k}-U^{k}}\right\|_{\infty}\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-U^{\pi}}\right\|_{\infty}.$

Otherwise, if $U^{0}\geq TU^{0}$, $U^{k}\geq TU^{k}$ by Lemma 5. Since

$\displaystyle 0$ $\displaystyle\geq T^{\pi}U^{k}-U^{k}$
$\displaystyle\geq\sum_{i=1}^{k}\left[\left({\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right)\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\gamma\mathcal{P}^{\pi}}\right)^{k-i+1}(U^{0}-U^{\pi})\right]-\beta_{k}(U^{0}-U^{\pi}),$

by Lemma 7, taking $\left\|{\cdot}\right\|_{\infty}$-norm both sides, we
obtain same rate as before.

Lastly, Taylor series expansion for both rates at $\gamma=1$ is

$\displaystyle\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}$
$\displaystyle=\frac{2}{k+1}-\frac{k-1}{k+1}(\gamma-1)+O((\gamma-1)^{2}),$
$\displaystyle\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}$
$\displaystyle=\frac{1}{k+1}-\frac{k}{k+1}(\gamma-1)+O((\gamma-1)^{2}).$

∎

For the analyses of Anc-VI for Bellman optimality operator, we first prove
following two lemmas.

######  Lemma 8.

Let $0<\gamma\leq 1$. If $\gamma=1$, assume a fixed point $U^{\star}$ exists.
Then, if $0\leq\alpha\leq 1$ and $U-(1-\alpha)\tilde{U}-\alpha
U^{\star}\leq\bar{U}$, there exist nonexpansive linear operator
$\mathcal{P}_{H}$ such that

$\displaystyle T^{\star}U-(1-\alpha)T^{\star}\tilde{U}-\alpha
T^{\star}U^{\star}$ $\displaystyle\leq\gamma\mathcal{P}_{H}\bar{U}.$

######  Lemma 9.

Let $0<\gamma<1$. If $0\leq\alpha\leq 1$ and $\bar{U}\leq
U-(1-\alpha)\tilde{U}-\alpha\hat{U}^{\star}$, then there exist nonexpansive
linear operator $\hat{\mathcal{P}}_{H}$ such that

$\displaystyle\gamma\hat{\mathcal{P}}_{H}(\bar{U})$ $\displaystyle\leq
T^{\star}U-\alpha
T^{\star}\tilde{U}-(1-\alpha)\hat{T}^{\star}\hat{U}^{\star}.$

###### Proof of Lemma 8.

First, let $U=V,\tilde{U}=\tilde{V},U^{\star}=V^{\star},\bar{U}=\bar{V}$, and
$V-(1-\alpha)\tilde{V}-\alpha V^{\star}\leq\bar{V}$.

If action space is finite,

$\displaystyle T^{\star}V-(1-\alpha)T^{\star}\tilde{V}-\alpha
T^{\star}V^{\star}$ $\displaystyle\leq
T^{\pi}V-(1-\alpha)T^{\pi}\tilde{V}-\alpha T^{\pi}V^{\star}$
$\displaystyle=\gamma\mathcal{P}^{\pi}\left({V-(1-\alpha)\tilde{V}-\alpha
V^{\star}}\right)$ $\displaystyle\leq\gamma\mathcal{P}^{\pi}\bar{V}$

where $\pi$ is the greedy policy satisfying $T^{\pi}V=T^{\star}V$, first
inequality is from $T^{\pi}\tilde{V}\leq T^{\star}\tilde{V}$ and
$T^{\pi}V^{\star}\leq T^{\star}V^{\star}$, and second inequality comes from
Lemma 1. Thus, we can conclude $\mathcal{P}_{H}=\mathcal{P}^{\pi}$.

Otherwise, if action space is infinite, define
$\mathcal{P}(c\bar{V})=c\sup_{s\in\mathcal{S}}\bar{V}(s)$ for $c\in\mathbb{R}$
and previously given $\bar{V}$. Let $M$ be linear space spanned by $\bar{V}$
with $\left\|{\cdot}\right\|_{\infty}$-norm. Then, $\mathcal{P}$ is linear
functional on $M$ and $\|\mathcal{P}\|_{\text{op}}\leq 1$ since
$\frac{|c\sup_{s\in\mathcal{S}}\bar{V}(s)|}{\left\|{c\bar{V}}\right\|_{\infty}}\leq
1$. Due to Hahn–Banach extension Theorem, there exist linear functional
$\mathcal{P}_{h}\colon\mathcal{F}(\mathcal{S})\rightarrow\mathbb{R}$ with
$\mathcal{P}_{h}(\bar{V})=\sup_{s\in\mathcal{S}}\bar{V}(s)$ and
$\|\mathcal{P}_{h}\|_{\text{op}}\leq 1$. Furthermore, we can define
$\mathcal{P}_{H}\colon\mathcal{F}(\mathcal{S})\rightarrow\mathcal{F}(\mathcal{S})$
such that $\mathcal{P}_{H}V(s)=\mathcal{P}_{h}(V)$ for all $s\in\mathcal{S}$.
Then, since
$\|\mathcal{P}_{H}(V)\|_{\infty}=|\mathcal{P}_{h}(V)|\leq\|\mathcal{P}_{h}\|_{\text{op}}\leq
1$ for $\left\|{V}\right\|_{\infty}\leq 1$, we have
$\|\mathcal{P}_{H}\|_{\infty}\leq 1$. Therefore, $\mathcal{P}_{H}$ is
nonexpansive linear operator in $\left\|{\cdot}\right\|_{\infty}$-norm. Then,

$\displaystyle T^{\star}V(s)-(1-\alpha)T^{\star}\tilde{V}(s)-\alpha
T^{\star}V^{\star}(s)$
$\displaystyle=\sup_{a\in\mathcal{A}}\bigg{\\{}r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[V(s^{\prime})\right]\bigg{\\}}-\sup_{a\in\mathcal{A}}\bigg{\\{}(1-\alpha)r(s,a)+(1-\alpha)\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\tilde{V}(s^{\prime})\right]\bigg{\\}}$
$\displaystyle\quad-\sup_{a\in\mathcal{A}}\bigg{\\{}\alpha
r(s,a)+\alpha\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[V^{\star}(s^{\prime})\right]\bigg{\\}}$
$\displaystyle\leq\sup_{a\in\mathcal{A}}\bigg{\\{}r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[V(s^{\prime})\right]-(1-\alpha)r(s,a)-(1-\alpha)\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\tilde{V}(s^{\prime})\right]\bigg{\\}}$
$\displaystyle\quad-\sup_{a\in\mathcal{A}}\bigg{\\{}\alpha
r(s,a)+\alpha\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[V^{\star}(s^{\prime})\right]\bigg{\\}}$
$\displaystyle\leq\gamma\sup_{a\in\mathcal{A}}\bigg{\\{}\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[V(s^{\prime})-(1-\alpha)\tilde{V}(s^{\prime})-\alpha
V^{\star}(s^{\prime})\right]\bigg{\\}}$
$\displaystyle\leq\gamma\sup_{s^{\prime}\in\mathcal{S}}\\{V(s^{\prime})-(1-\alpha)\tilde{V}(s^{\prime})-\alpha
V^{\star}(s^{\prime})\\}$
$\displaystyle\leq\gamma\sup_{s^{\prime}\in\mathcal{S}}\bar{V}(s^{\prime}).$

for all $s\in\mathcal{S}$. Therefore, we have

$\displaystyle T^{\star}V-(1-\alpha)T^{\star}\tilde{V}-\alpha
T^{\star}V^{\star}\leq\gamma\mathcal{P}_{H}(\bar{V}).$

Similarly, let $U=Q,\tilde{U}=\tilde{Q},U^{\star}=Q^{\star},\bar{U}=\bar{Q}$,
and $Q-(1-\alpha)\tilde{Q}-\alpha Q^{\star}\leq\bar{Q}$.

If action space is finite,

$\displaystyle T^{\star}Q-(1-\alpha)T^{\star}\tilde{Q}-\alpha
T^{\star}Q^{\star}$
$\displaystyle\leq\gamma\mathcal{P}^{\pi}\left({Q-(1-\alpha)\tilde{Q}-\alpha
Q^{\star}}\right)$ $\displaystyle\leq\gamma\mathcal{P}^{\pi}\bar{Q}$

where $\pi$ is the greedy policy satisfying $T^{\pi}Q=T^{\star}Q$, first
inequality is from $T^{\pi}\tilde{Q}\leq T^{\star}\tilde{Q}$ and
$T^{\pi}Q^{\star}\leq T^{\star}Q^{\star}$, and second inequality comes from
Lemma 1. Then, we can conclude $\mathcal{P}_{H}=\mathcal{P}^{\pi}$.

Otherwise, if action space is infinite, define
$\mathcal{P}(c\bar{Q})=c\sup_{(s^{\prime},a^{\prime})\in\mathcal{S}\times\mathcal{A}}\bar{Q}(s^{\prime},a^{\prime})$
for $c\in\mathbb{R}$ and previously given $\bar{Q}$. Let $M$ be linear space
spanned by $\bar{Q}$ with $\left\|{\cdot}\right\|_{\infty}$-norm. Then,
$\mathcal{P}$ is linear functional on $M$ and $\|\mathcal{P}\|_{\text{op}}\leq
1$. Due to Hahn–Banach extension Theorem, there exist linear functional
$\mathcal{P}_{h}\colon\mathcal{F}(\mathcal{S}\times\mathcal{A})\rightarrow\mathbb{R}$
with
$\mathcal{P}_{h}(\bar{Q})=\sup_{(s^{\prime},a^{\prime})\in\mathcal{S}\times\mathcal{A}}\bar{Q}(s^{\prime},a^{\prime})$
and $\|\mathcal{P}_{h}\|_{\text{op}}\leq 1$. Furthermore, we can define
$\mathcal{P}_{H}\colon\mathcal{F}(\mathcal{S}\times\mathcal{A})\rightarrow\mathcal{F}(\mathcal{S}\times\mathcal{A})$
such that $\mathcal{P}_{H}Q(s,a)=\mathcal{P}_{h}(Q)$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$ and $\|P_{H}\|_{\infty}\leq 1$.
Therefore, $\mathcal{P}_{H}$ is nonexpansive linear operator in
$\left\|{\cdot}\right\|_{\infty}$-norm. Then,

$\displaystyle T^{\star}Q(s,a)-(1-\alpha)T^{\star}\tilde{Q}(s,a)-\alpha
T^{\star}Q^{\star}(s,a)$
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\sup_{a^{\prime}\in\mathcal{A}}Q(s^{\prime},a^{\prime})\right]-(1-\alpha)r(s,a)-(1-\alpha)\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\sup_{a^{\prime}\in\mathcal{A}}\tilde{Q}(s^{\prime},a^{\prime})\right]$
$\displaystyle\quad-\alpha r(s,a)-\alpha\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\sup_{a^{\prime}\in\mathcal{A}}Q^{\star}(s^{\prime},a^{\prime})\right]$
$\displaystyle\leq\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\sup_{a^{\prime}\in\mathcal{A}}\left\\{Q(s^{\prime},a^{\prime})-(1-\alpha)\tilde{Q}(s^{\prime},a^{\prime})\right\\}\right]-\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\sup_{a^{\prime}\in\mathcal{A}}\alpha
Q(s^{\prime},a^{\prime})\right]$
$\displaystyle\leq\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\sup_{a^{\prime}\in\mathcal{A}}\left\\{Q(s^{\prime},a^{\prime})-(1-\alpha)\tilde{Q}(s^{\prime},a^{\prime})-\alpha
Q^{\star}(s^{\prime},a^{\prime})\right\\}\right]$
$\displaystyle\leq\gamma\sup_{(s^{\prime},a^{\prime})\in\mathcal{S}\times\mathcal{A}}\left\\{Q(s^{\prime},a^{\prime})-(1-\alpha)\tilde{Q}(s^{\prime},a^{\prime})-\alpha
Q^{\star}(s^{\prime},a^{\prime})\right\\},$
$\displaystyle\leq\gamma\sup_{(s^{\prime},a^{\prime})\in\mathcal{S}\times\mathcal{A}}\bar{Q}(s^{\prime},a^{\prime})$

for all $(s,a)\in\mathcal{S}\times\mathcal{A}$. Therefore, we have

$\displaystyle T^{\star}Q-(1-\alpha)T^{\star}\tilde{Q}-\alpha
T^{\star}Q^{\star}\leq\gamma\mathcal{P}_{H}(\bar{Q}).$

∎

###### Proof of Lemma 9.

Note that $\hat{T}^{\star}$ is Bellman anti-optimality operators for $V$ or
$Q$, and $\hat{U}^{\star}$ is the fixed point of $\hat{T}^{\star}$. First, let
$U=V,\tilde{U}=\tilde{V},\hat{U}^{\star}=\hat{V}^{\star},\bar{U}=\bar{V}$, and
$\bar{V}\leq V-(1-\alpha)\tilde{V}-\alpha\hat{V}^{\star}$. Then,

$\displaystyle
T^{\star}V(s)-(1-\alpha)T^{\star}\tilde{V}(s)-\alpha\hat{T}^{\star}\hat{V}^{\star}(s)$
$\displaystyle=\sup_{a\in\mathcal{A}}\bigg{\\{}r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[V(s^{\prime})\right]\bigg{\\}}-\sup_{a\in\mathcal{A}}\bigg{\\{}(1-\alpha)r(s,a)+(1-\alpha)\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\tilde{V}(s^{\prime})\right]\bigg{\\}}$
$\displaystyle\quad-\inf_{a\in\mathcal{A}}\bigg{\\{}\alpha
r(s,a)+\alpha\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\hat{V}^{\star}(s^{\prime})\right]\bigg{\\}}$
$\displaystyle\geq\inf_{a\in\mathcal{A}}\bigg{\\{}r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[V(s^{\prime})\right]-(1-\alpha)r(s,a)-(1-\alpha)\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\tilde{V}(s^{\prime})\right]\bigg{\\}}$
$\displaystyle\quad-\inf_{a\in\mathcal{A}}\bigg{\\{}\alpha
r(s,a)+\alpha\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\hat{V}^{\star}(s^{\prime})\right]\bigg{\\}}$
$\displaystyle\geq\gamma\inf_{a\in\mathcal{A}}\bigg{\\{}\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[V(s^{\prime})-(1-\alpha)\tilde{V}(s^{\prime})-\alpha\hat{V}^{\star}(s^{\prime})\right]\bigg{\\}}.$

Then, if action space is finite,

$\displaystyle T^{\star}V-(1-\alpha)T^{\star}\tilde{V}-\alpha
T^{\star}V^{\star}$
$\displaystyle\geq\gamma\mathcal{P}^{\hat{\pi}}\left({V-(1-\alpha)\tilde{V}-\alpha\hat{V}^{\star}}\right)$
$\displaystyle\geq\gamma\mathcal{P}^{\hat{\pi}}\bar{V}$

where $\hat{\pi}$ is the policy satisfying
$\hat{\pi}(\cdot\,|\,s)=\operatorname*{argmin}_{a\in\mathcal{A}}\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[V(s^{\prime})-(1-\alpha)\tilde{V}(s^{\prime})-\alpha\hat{V}^{\star}(s^{\prime})\right]$
and second inequality comes from Lemma 1. Thus, we can conclude
$\mathcal{P}_{H}=\mathcal{P}^{\pi}$.

Otherwise, if action space is infinite, define
$\hat{\mathcal{P}}(c\bar{V})=c\inf_{s\in\mathcal{S}}\bar{V}(s)$ for
$c\in\mathbb{R}$ and previously given $\bar{V}$. Let $M$ be linear space
spanned by $\bar{V}$ with $\left\|{\cdot}\right\|_{\infty}$-norm. Then,
$\hat{\mathcal{P}}$ is linear functional on $M$ and
$\|\hat{\mathcal{P}}\|_{\text{op}}\leq 1$ since
$\frac{|c\inf_{s\in\mathcal{S}}\bar{V}(s)|}{\left\|{c\bar{V}}\right\|_{\infty}}\leq
1$. Due to Hahn–Banach extension Theorem, there exist linear functional
$\hat{\mathcal{P}}_{h}\colon\mathcal{F}(\mathcal{S})\rightarrow\mathbb{R}$
with $\hat{\mathcal{P}}_{h}(\bar{V})=\inf_{s\in\mathcal{S}}\bar{V}(s)$ and
$\|\hat{\mathcal{P}}_{h}\|_{\text{op}}\leq 1$. Furthermore, we can define
$\hat{\mathcal{P}}_{H}\colon\mathcal{F}(\mathcal{S})\rightarrow\mathcal{F}(\mathcal{S})$
such that $\hat{\mathcal{P}}_{H}V(s)=\hat{\mathcal{P}}_{h}(V)$ for all
$s\in\mathcal{S}$. Then $\|\hat{\mathcal{P}}_{H}\|_{\infty}\leq 1$ since
$\|\hat{\mathcal{P}}_{H}(V)\|_{\infty}=|\hat{\mathcal{P}}_{h}(V)|\leq\|\hat{\mathcal{P}}_{h}\|_{\text{op}}\leq
1$ for $\left\|{V}\right\|_{\infty}\leq 1$. . Thus, $\hat{\mathcal{P}}_{H}$ is
nonexpansive linear operator in $\left\|{\cdot}\right\|_{\infty}$-norm. Then,
we have

$\displaystyle
T^{\star}V(s)-(1-\alpha)T^{\star}\tilde{V}(s)-\alpha\hat{T}^{\star}\hat{V}^{\star}(s)$
$\displaystyle\geq\gamma\inf_{a\in\mathcal{A}}\bigg{\\{}\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[V(s^{\prime})-(1-\alpha)\tilde{V}(s^{\prime})-\alpha\hat{V}^{\star}(s^{\prime})\right]\bigg{\\}}$
$\displaystyle\geq\gamma\inf_{s^{\prime}\in\mathcal{S}}\\{V(s^{\prime})-(1-\alpha)\tilde{V}(s^{\prime})-\alpha\hat{V}^{\star}(s^{\prime})\\}$
$\displaystyle\geq\gamma\inf_{s^{\prime}\in\mathcal{S}}\\{\bar{V}(s^{\prime})\\}$

for all $s\in\mathcal{S}$. Therefore, we have

$\displaystyle\gamma\hat{\mathcal{P}}_{H}(\bar{V})\leq
T^{\star}V(s)-(1-\alpha)T^{\star}\tilde{V}(s)-\alpha\hat{T}^{\star}\hat{V}^{\star}(s).$

Similarly, let
$U=Q,\tilde{U}=\tilde{Q},\hat{U}^{\star}=\hat{Q}^{\star},\bar{U}=\bar{Q}$, and
$\bar{Q}\leq Q-(1-\alpha)\tilde{Q}-\alpha\hat{Q}^{\star}$. Then,

$\displaystyle T^{\star}Q(s,a)-\alpha
T^{\star}\tilde{Q}(s,a)-(1-\alpha)\hat{T}^{\star}\hat{Q}^{\star}(s,a)$
$\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\sup_{a^{\prime}\in\mathcal{A}}Q(s^{\prime},a^{\prime})\right]-(1-\alpha)r(s,a)-(1-\alpha)\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\sup_{a^{\prime}\in\mathcal{A}}\tilde{Q}(s^{\prime},a^{\prime})\right]$
$\displaystyle\quad-\alpha r(s,a)-\alpha\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\inf_{a^{\prime}\in\mathcal{A}}\hat{Q}^{\star}(s^{\prime},a^{\prime})\right]$
$\displaystyle\geq\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\inf_{a^{\prime}\in\mathcal{A}}\left\\{Q(s^{\prime},a^{\prime})-(1-\alpha)\tilde{Q}(s^{\prime},a^{\prime})\right\\}\right]-\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\inf_{a^{\prime}\in\mathcal{A}}\alpha\hat{Q}(s^{\prime},a^{\prime})\right]$
$\displaystyle\geq\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\inf_{a^{\prime}\in\mathcal{A}}\left\\{Q(s^{\prime},a^{\prime})-(1-\alpha)\tilde{Q}(s^{\prime},a^{\prime})-\alpha\hat{Q}^{\star}(s^{\prime},a^{\prime})\right\\}\right].$

Hence, if action space is finite,

$\displaystyle T^{\star}Q-(1-\alpha)T^{\star}\tilde{Q}-\alpha
T^{\star}Q^{\star}$
$\displaystyle\geq\gamma\mathcal{P}^{\hat{\pi}}\left({Q-(1-\alpha)\tilde{Q}-\alpha
Q^{\star}}\right),$ $\displaystyle\geq\gamma\mathcal{P}^{\hat{\pi}}\bar{Q},$

where $\hat{\pi}$ is the policy satisfying
$\hat{\pi}(\cdot\,|\,s)=\operatorname*{argmin}_{a\in\mathcal{A}}\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[Q(s^{\prime})-(1-\alpha)\tilde{Q}(s^{\prime})-\alpha
Q^{\star}(s^{\prime})\right]$ and second inequality comes from Lemma 1. Then,
we can conclude $\mathcal{P}_{H}=\mathcal{P}^{\hat{\pi}}$.

Otherwise, if action space is infinite, define
$\hat{\mathcal{P}}(c\bar{Q})=c\inf_{(s^{\prime},a^{\prime})\in\mathcal{S}\times\mathcal{A}}\bar{Q}(s^{\prime},a^{\prime})$
for $c\in\mathbb{R}^{n}$ and previously given $\bar{Q}$. Let $M$ be linear
space spanned by $\bar{Q}$ with $\left\|{\cdot}\right\|_{\infty}$-norm. Then,
$\mathcal{P}$ is linear functional on $M$ with
$\|\hat{\mathcal{P}}\|_{\text{op}}\leq 1$. Due to Hahn–Banach extension
Theorem, there exist linear functional
$\hat{\mathcal{P}}_{h}\colon\mathcal{F}(\mathcal{S}\times\mathcal{A})\rightarrow\mathbb{R}$
with
$\hat{\mathcal{P}}_{h}(\bar{Q})=\inf_{(s^{\prime},a^{\prime})\in\mathcal{S}\times\mathcal{A}}\bar{Q}(s^{\prime},a^{\prime})$
and $\|\hat{\mathcal{P}}_{h}\|_{\text{op}}\leq 1$. Furthermore, we can define
$\hat{\mathcal{P}}_{H}\colon\mathcal{F}(\mathcal{S}\times\mathcal{A})\rightarrow\mathcal{F}(\mathcal{S}\times\mathcal{A})$
such that $\mathcal{P}_{H}Q(s,a)=\hat{\mathcal{P}}_{h}(Q)$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$ and $\|\hat{P}_{H}\|_{\infty}\leq 1$.
Thus $\hat{\mathcal{P}}_{H}$ is nonexpansive linear operator in
$\left\|{\cdot}\right\|_{\infty}$-norm. Then, we have

$\displaystyle T^{\star}Q(s,a)-\alpha
T^{\star}\tilde{Q}(s,a)-(1-\alpha)\hat{T}^{\star}\hat{Q}^{\star}(s,a)$
$\displaystyle\geq\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[\inf_{a^{\prime}\in\mathcal{A}}\left\\{Q(s^{\prime},a^{\prime})-(1-\alpha)\tilde{Q}(s^{\prime},a^{\prime})-\alpha\hat{Q}^{\star}(s^{\prime},a^{\prime})\right\\}\right]$
$\displaystyle\geq\gamma\inf_{(s^{\prime},a^{\prime})\in\mathcal{S}\times\mathcal{A}}\left\\{Q(s^{\prime},a^{\prime})-(1-\alpha)\tilde{Q}(s^{\prime},a^{\prime})-\alpha\hat{Q}^{\star}(s^{\prime},a^{\prime})\right\\}$
$\displaystyle\geq\gamma\inf_{(s^{\prime},a^{\prime})\in\mathcal{S}\times\mathcal{A}}\bar{Q}(s^{\prime},a^{\prime}),$

for all $(s,a)\in\mathcal{S}\times\mathcal{A}$. Therefore, we have

$\displaystyle\gamma\hat{\mathcal{P}}_{H}(\bar{Q})\leq
T^{\star}Q-(1-\alpha)T^{\star}\tilde{Q}-\alpha\hat{T}^{\star}\hat{Q}^{\star}.$

∎

Now, we present our key lemmas for the first rate of Theorem 2.

######  Lemma 10.

Let $0<\gamma\leq 1$. If $\gamma=1$, assume a fixed point $U^{\star}$ exists.
For the iterates $\\{U^{k}\\}_{k=0,1,\dots}$ of Anc-VI, there exist
nonexpansive linear operators $\\{\mathcal{P}^{l}\\}_{l=0,1,\dots,k}$ such
that

$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle\leq\sum_{i=1}^{k}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})\right]$
$\displaystyle\quad-\beta_{k}(U^{0}-U^{\star})+\left({\Pi^{k}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})$

where $\Pi^{k}_{j=k+1}(1-\beta_{j})=1$ and $\beta_{0}=1$.

######  Lemma 11.

Let $0<\gamma<1$. For the iterates $\\{U^{k}\\}_{k=0,1,\dots}$ of Anc-VI,
there exist nonexpansive linear operators
$\\{\hat{\mathcal{P}}^{l}\\}_{l=0,1,\dots,k}$ such that

$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle\geq\sum_{i=1}^{k}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})\right]$
$\displaystyle\quad-\beta_{k}(U^{0}-\hat{U}^{\star})+\left({\Pi^{k}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star}),$

where $\Pi^{k}_{j=k+1}(1-\beta_{j})=1$ and $\beta_{0}=1$.

We prove previous lemmas by induction.

###### Proof of Lemma 10.

If $k=0$,

$\displaystyle T^{\star}U^{0}-U^{0}$
$\displaystyle=T^{\star}U^{0}-U^{\star}-(U^{0}-U^{\star})$
$\displaystyle=T^{\star}U^{0}-T^{\star}U^{\star}-(U^{0}-U^{\star})$
$\displaystyle\leq\gamma\mathcal{P}^{0}(U^{0}-U^{\star})-(U^{0}-U^{\star}).$

where inequality comes from first inequality in Lemma 8 with
$\alpha=1,U=U^{0},\bar{U}=U^{0}-U^{\star}$.

By induction,

$\displaystyle U^{k}-(1-\beta_{k})U^{k-1}-\beta_{k}U^{\star}$
$\displaystyle=\beta_{k}\left({U^{0}-U^{\star}}\right)+(1-\beta_{k})(T^{\star}U^{k-1}-U^{k-1})$
$\displaystyle\leq(1-\beta_{k})\sum_{i=1}^{k-1}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k-1}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k-1}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})\right]$
$\displaystyle\quad-(1-\beta_{k})\beta_{k-1}(U^{0}-U^{\star})+(1-\beta_{k})\left({\Pi^{k-1}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k-1}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})$
$\displaystyle\quad+\beta_{k}(U^{0}-U^{\star}),$

and let $\bar{U}$ be the entire right hand side of inequality. Then, we have

$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle=T^{\star}U^{k}-(1-\beta_{k})T^{\star}U^{k-1}-\beta_{k}U^{0}$
$\displaystyle=T^{\star}U^{k}-(1-\beta_{k})T^{\star}U^{k-1}-\beta_{k}U^{\star}-\beta_{k}(U^{0}-U^{\star})$
$\displaystyle=T^{\star}U^{k}-(1-\beta_{k})T^{\star}U^{k-1}-\beta_{k}T^{\star}U^{\star}-\beta_{k}(U^{0}-U^{\star})$
$\displaystyle\leq\gamma\mathcal{P}^{k}\bigg{(}(1-\beta_{k})\sum_{i=1}^{k-1}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k-1}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k-1}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})\right]$
$\displaystyle\quad-(1-\beta_{k})\beta_{k-1}(U^{0}-U^{\star})+(1-\beta_{k})\left({\Pi^{k-1}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k-1}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})$
$\displaystyle\quad+\beta_{k}(U^{0}-U^{\star})\bigg{)}-\beta_{k}(U^{0}-U^{\star})$
$\displaystyle=\sum_{i=1}^{k-1}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})\right]$
$\displaystyle\quad-\beta_{k-1}(1-\beta_{k})\gamma\mathcal{P}^{k}(U^{0}-U^{\star})+\beta_{k}\gamma\mathcal{P}^{k}\left({U^{0}-U^{\star}}\right)$
$\displaystyle\quad-\beta_{k}(U^{0}-U^{\star})+\left({\Pi^{k}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})$
$\displaystyle=\sum_{i=1}^{k}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})\right]$
$\displaystyle\quad-\beta_{k}(U^{0}-U^{\star})+\left({\Pi^{k}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star}).$

where inequality comes from first inequality in Lemma 8 with
$\alpha=\beta_{k},U=U^{k},\tilde{U}=U^{k-1}$, and previously defined
$\bar{U}$. ∎

###### Proof of Lemma 11.

Note that $\hat{T}^{\star}$ is Bellman anti-optimality operators for $V$ or
$Q$, and $\hat{U}^{\star}$ is the fixed point of $\hat{T}^{\star}$. If $k=0$,

$\displaystyle T^{\star}U^{0}-U^{0}$
$\displaystyle=T^{\star}U^{0}-\hat{U}^{\star}-(U^{0}-\hat{U}^{\star})$
$\displaystyle=T^{\star}U^{0}-\hat{T}^{\star}\hat{U}^{\star}-(U^{0}-\hat{U}^{\star})$
$\displaystyle\geq\gamma\hat{\mathcal{P}}^{0}(U^{0}-\hat{U}^{\star})-(U^{0}-\hat{U}^{\star}).$

where inequality comes from second inequality in Lemma 9 with
$\alpha=1,U=U^{0},\bar{U}=U^{0}-\hat{U}^{\star}$.

By induction,

$\displaystyle U^{k}-(1-\beta_{k})U^{k-1}-\beta_{k}\hat{U}^{\star}$
$\displaystyle=\beta_{k}(U^{0}-\hat{U}^{\star})+(1-\beta_{k})(T^{\star}U^{k-1}-U^{k-1})$
$\displaystyle\geq(1-\beta_{k})\sum_{i=1}^{k-1}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k-1}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k-1}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})\right]$
$\displaystyle\quad-(1-\beta_{k})\beta_{k-1}(U^{0}-\hat{U}^{\star})+(1-\beta_{k})\left({\Pi^{k-1}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k-1}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})$
$\displaystyle\quad+\beta_{k}(U^{0}-\hat{U}^{\star}),$

and let $\bar{U}$ be the entire right hand side of inequality. Then, we have

$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle=T^{\star}U^{k}-(1-\beta_{k})T^{\star}U^{k-1}-\beta_{k}U^{0}$
$\displaystyle=T^{\star}U^{k}-(1-\beta_{k})T^{\star}U^{k-1}-\beta_{k}\hat{U}^{\star}-\beta_{k}(U^{0}-\hat{U}^{\star})$
$\displaystyle=T^{\star}U^{k}-(1-\beta_{k})T^{\star}U^{k-1}-\beta_{k}\hat{T}^{\star}\hat{U}^{\star}-\beta_{k}(U^{0}-\hat{U}^{\star})$
$\displaystyle\geq\gamma\hat{\mathcal{P}}^{k}\bigg{(}(1-\beta_{k})\sum_{i=1}^{k-1}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k-1}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k-1}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})\right]$
$\displaystyle\quad-(1-\beta_{k})\beta_{k-1}(U^{0}-\hat{U}^{\star})+(1-\beta_{k})\left({\Pi^{k-1}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k-1}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})$
$\displaystyle\quad+\beta_{k}(U^{0}-\hat{U}^{\star})\bigg{)}-\beta_{k}(U^{0}-\hat{U}^{\star})$
$\displaystyle=\sum_{i=1}^{k-1}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})\right]$
$\displaystyle\quad-\beta_{k-1}(1-\beta_{k})\gamma\hat{\mathcal{P}}^{k}(U^{0}-\hat{U}^{\star})+\beta_{k}\gamma\hat{\mathcal{P}}^{k}\left({U^{0}-\hat{U}^{\star}}\right)$
$\displaystyle\quad-\beta_{k}(U^{0}-\hat{U}^{\star})+\left({\Pi^{k}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})$
$\displaystyle=\sum_{i=1}^{k}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})\right]$
$\displaystyle\quad-\beta_{k}(U^{0}-\hat{U}^{\star})+\left({\Pi^{k}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star}).$

where inequality comes from second inequality in Lemma 9 with
$\alpha=\beta_{k},U=U^{k},\tilde{U}=U^{k-1}$, and previously defined
$\bar{U}$. ∎

Now, we prove the first rate of Theorem 2.

###### Proof of first rate in Theorem 2.

Since $B_{1}\leq A\leq B_{2}$ implies
$\left\|{A}\right\|_{\infty}\leq\sup\\{\left\|{B_{1}}\right\|_{\infty},\left\|{B_{2}}\right\|_{\infty}\\}$
for $A,B\in\mathcal{F}(\mathcal{X})$, if we take
$\left\|{\cdot}\right\|_{\infty}$ right side first inequality of Lemma 10, we
have

$\displaystyle\sum_{i=1}^{k}\left|{\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right|\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left\|{\left({\Pi^{i}_{l=k}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})}\right\|_{\infty}$
$\displaystyle\quad+\beta_{k}\left\|{U^{0}-U^{\pi}}\right\|_{\infty}+\left({\Pi^{k}_{j=1}(1-\beta_{j})}\right)\left\|{\left({\Pi^{0}_{l=k}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})}\right\|_{\infty}$
$\displaystyle\leq\left({\sum_{i=1}^{k}\gamma^{k-i+1}\left|{\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right|\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)+\beta_{k}+\gamma^{k+1}\Pi^{k}_{j=1}(1-\beta_{j})}\right)$
$\displaystyle\quad\left\|{U^{0}-U^{\star}}\right\|_{\infty}$
$\displaystyle=\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-U^{\star}}\right\|_{\infty},$

where the first inequality comes from triangular inequality, second inequality
is from nonexpansiveness of $\mathcal{P}^{l}$, and last equality comes from
calculations.

If we take $\left\|{\cdot}\right\|_{\infty}$ right side of second inequality
of Lemma 10, similarly, we have

$\displaystyle\sum_{i=1}^{k}\left|{\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right|\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left\|{\left({\Pi^{i}_{l=k}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})}\right\|_{\infty}$
$\displaystyle\quad+\beta_{k}\left\|{U^{0}-U^{\pi}}\right\|_{\infty}+\left({\Pi^{k}_{j=1}(1-\beta_{j})}\right)\left\|{\left({\Pi^{0}_{l=k}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})}\right\|_{\infty}$
$\displaystyle\leq\left({\sum_{i=1}^{k}\gamma^{k-i+1}\left|{\beta_{i}-\beta_{i-1}(1-\beta_{i})}\right|\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)+\beta_{k}+\gamma^{k+1}\Pi^{k}_{j=1}(1-\beta_{j})}\right)$
$\displaystyle=\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-\hat{U}^{\star}}\right\|_{\infty},$

where the first inequality comes from triangular inequality, second inequality
is from from nonexpansiveness of $\hat{\mathcal{P}}^{l}$, and last equality
comes from calculations. Therefore, we conclude

$\displaystyle\left\|{T^{\star}U^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\max{\left\\{\left\|{U^{0}-U^{\star}}\right\|_{\infty},\left\|{U^{0}-\hat{U}^{\star}}\right\|_{\infty}\right\\}}.$

∎

Next, for the second rate in Theorem 2, we prove following lemmas by
induction.

######  Lemma 12.

Let $0<\gamma\leq 1$. If $\gamma=1$, assume a fixed point $U^{\star}$ exists.
For the iterates $\\{U^{k}\\}_{k=0,1,\dots}$ of Anc-VI, if $T^{\star}U^{0}\leq
U^{\star}$, there exist nonexpansive linear operators
$\\{\mathcal{P}^{l}\\}_{l=0,1,\dots,k}$ such that

$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle\leq\sum_{i=1}^{k}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})\right]-\beta_{k}(U^{0}-U^{\star})$

where $\Pi^{k}_{j=k+1}(1-\beta_{j})=1$ and $\beta_{0}=1$.

######  Lemma 13.

Let $0<\gamma<1$. For the iterates $\\{U^{k}\\}_{k=0,1,\dots}$ of Anc-VI, if
$U^{0}\geq T^{\star}U^{0}$, there exist nonexpansive linear operators
$\\{\hat{\mathcal{P}}^{l}\\}_{l=0,1,\dots,k}$ such that

$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle\geq\sum_{i=1}^{k}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})\right]-\beta_{k}(U^{0}-\hat{U}^{\star}),$

where $\Pi^{k}_{j=k+1}(1-\beta_{j})=1$ and $\beta_{0}=1$.

###### Proof of Lemma 12.

If $k=0$,

$\displaystyle T^{\star}U^{0}-U^{0}$
$\displaystyle=T^{\star}U^{0}-U^{\star}-(U^{0}-U^{\star})$
$\displaystyle\leq-(U^{0}-U^{\star})$

where the second inequality is from the condition.

By induction,

$\displaystyle U^{k}-(1-\beta_{k})U^{k-1}-\beta_{k}U^{\star}$
$\displaystyle\leq(1-\beta_{k})\sum_{i=1}^{k-1}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k-1}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k-1}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})\right]$
$\displaystyle\quad-(1-\beta_{k})\beta_{k-1}(U^{0}-U^{\star})+\beta_{k}(U^{0}-U^{\star}),$

and let $\bar{U}$ be the entire right hand side of inequality. Then, we have

$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle=T^{\star}U^{k}-(1-\beta_{k})T^{\star}U^{k-1}-\beta_{k}T^{\star}U^{\star}-\beta_{k}(U^{0}-U^{\star})$
$\displaystyle\leq\gamma\mathcal{P}^{k}\bigg{(}(1-\beta_{k})\sum_{i=1}^{k-1}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k-1}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k-1}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})\right]$
$\displaystyle\quad-(1-\beta_{k})\beta_{k-1}(U^{0}-U^{\star})+\beta_{k}(U^{0}-U^{\star})\bigg{)}-\beta_{k}(U^{0}-U^{\star})$
$\displaystyle=\sum_{i=1}^{k}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})\right]-\beta_{k}(U^{0}-U^{\star}),$

where inequality comes from first inequality in Lemma 8 with
$\alpha=\beta_{k},U=U^{k},\tilde{U}=U^{k-1}$, and previously defined
$\bar{U}$. ∎

###### Proof of Lemma 13.

If $k=0$,

$\displaystyle T^{\star}U^{0}-U^{0}$
$\displaystyle=T^{\star}U^{0}-\hat{U}^{\star}-(U^{0}-\hat{U}^{\star})$
$\displaystyle\geq-(U^{0}-\hat{U}^{\star}).$

where the second inequality is from the fact that $U^{0}\geq T^{\star}U^{0}$
implies $T^{\star}U^{0}\geq U^{\star}$ by Lemma 5 and
$U^{\star}\geq\hat{U}^{\star}$ by Lemma 3.

By induction,

$\displaystyle U^{k}-(1-\beta_{k})U^{k-1}-\beta_{k}\hat{U}^{\star}$
$\displaystyle\geq(1-\beta_{k})\sum_{i=1}^{k-1}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k-1}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k-1}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})\right]$
$\displaystyle\quad-(1-\beta_{k})\beta_{k-1}(U^{0}-\hat{U}^{\star})+\beta_{k}(U^{0}-\hat{U}^{\star}),$

and let $\bar{U}$ be the entire right hand side of inequality. Then, we have

$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle=T^{\star}U^{k}-(1-\beta_{k})T^{\star}U^{k-1}-\beta_{k}\hat{T}^{\star}\hat{U}^{\star}-\beta_{k}(U^{0}-\hat{U}^{\star})$
$\displaystyle\geq\gamma\hat{\mathcal{P}}^{k}\bigg{(}(1-\beta_{k})\sum_{i=1}^{k-1}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k-1}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k-1}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})\right]$
$\displaystyle\quad-(1-\beta_{k})\beta_{k-1}(U^{0}-\hat{U}^{\star})+\beta_{k}(U^{0}-\hat{U}^{\star})\bigg{)}-\beta_{k}(U^{0}-\hat{U}^{\star})$
$\displaystyle=\sum_{i=1}^{k}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})\right]-\beta_{k}(U^{0}-\hat{U}^{\star}),$

where inequality comes from second inequality in Lemma 9 with
$\alpha=\beta_{k},U=U^{k},\tilde{U}=U^{k-1}$, and previously defined
$\bar{U}$. ∎

Now, we prove the second rates of Theorem 2.

###### Proof of second rates in Theorem 2.

Let $0<\gamma<1$. Then, if $U^{0}\leq T^{\star}U^{0}$, then
$T^{\star}U^{0}\leq U^{\star}$ and $U^{k}\leq T^{\star}U^{k}$ by Lemma 5.
Hence, taking $\left\|{\cdot}\right\|_{\infty}$-norm both sides of first
inequality in Lemma 12, we have

$\left\|{T^{\star}U^{k}-U^{k}}\right\|_{\infty}\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-U^{\star}}\right\|_{\infty}.$

Otherwise, if $U^{0}\geq TU^{0}$, $U^{k}\geq TU^{k}$ by Lemma 5. taking
$\left\|{\cdot}\right\|_{\infty}$-norm both sides of second inequality in
Lemma 13, we have

$\left\|{T^{\star}U^{k}-U^{k}}\right\|_{\infty}\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-\hat{U}^{\star}}\right\|_{\infty}.$

∎

##  Appendix C Omitted proofs in Section 3

First, we present the following lemma.

######  Lemma 14.

Let $\gamma=1$. Assume a fixed point $U^{\star}$ exists. For the iterates
$\\{U^{k}\\}_{k=0,1,\dots}$ of Anc-VI,
$\left\|{U^{k}-U^{\star}}\right\|_{\infty}\leq\left\|{U^{0}-U^{\star}}\right\|_{\infty}$.

###### Proof.

If $k=0$, it is obvious. By induction,

$\displaystyle\left\|{U^{k}-U^{\star}}\right\|_{\infty}$
$\displaystyle=\left\|{\beta_{k}U^{0}+(1-\beta_{k})TU^{k-1}-U^{\star}}\right\|_{\infty}$
$\displaystyle=\left\|{(1-\beta_{k})(TU^{k-1}-U^{\star})+\beta_{k}\left({U^{0}-U^{\star}}\right)}\right\|_{\infty}$
$\displaystyle\leq(1-\beta_{k})\left\|{TU^{k-1}-U^{\star}}\right\|_{\infty}+\beta_{k}\left\|{U^{0}-U^{\star}}\right\|_{\infty}$
$\displaystyle\leq(1-\beta_{k})\left\|{U^{k-1}-U^{\star}}\right\|_{\infty}+\beta_{k}\left\|{U^{0}-U^{\star}}\right\|_{\infty}$
$\displaystyle=\left\|{U^{0}-U^{\star}}\right\|_{\infty}$

where the second inequality comes form nonexpansiveness of $T$. ∎

Now, we present the proof of Theorem 3.

###### Proof of Theorem 3.

First, if $U^{0}\leq TU^{0}$, with same argument in proof of Lemma 5, we can
show that $U^{k-1}\leq U^{k}\leq TU^{k-1}\leq TU^{k}$ for $k=1,2,\dots.$

Since fixed point $U^{\star}$ exists by assumption, Lemma 4 and 10 hold. Note
that $\gamma=1$ implies $\beta_{k}=\frac{1}{k+1}$ and if we take
$\left\|{\cdot}\right\|_{\infty}$-norm both sides for those inequalities in
lemmas, by simple calculation, we have

$\displaystyle\left\|{TU^{k}-U^{k}}\right\|_{\infty}\leq\frac{2}{k+1}\left\|{U^{0}-U^{\star}}\right\|_{\infty}$

for any fixed point $U^{\star}$ (since $0\leq T^{\star}U^{k}-U^{k}$, we can
get upper bound of $\left\|{T^{\star}U^{k}-U^{k}}\right\|_{\infty}$ from Lemma
10).

Suppose that there exist $\\{k_{j}\\}_{j=0,1,\dots}$ such that $U^{k_{j}}$
converges to some $\tilde{U}^{\star}$. Then,
$\lim_{j\rightarrow\infty}(T-I)U^{k_{j}}=(T-I)\tilde{U}^{\star}=0$ since $T-I$
is continuous. This implies that $\tilde{U}^{\star}$ is a fixed point. By
Lemma 14 and previous argument, $U^{k}$ is increasing and bounded sequence in
$\mathbb{R}^{n}$. Thus, $U^{k}$ has single limit point, some fixed point
$\tilde{U}^{\star}$. Furthermore, the fact that $U^{0}\leq
TU^{0}\leq\tilde{U}^{\star}$ implies that Lemma 6 and 12 hold. Therefore, we
have

$\displaystyle\left\|{TU^{k}-U^{k}}\right\|_{\infty}\leq\frac{1}{k+1}\left\|{U^{0}-\tilde{U}^{\star}}\right\|_{\infty}.$

∎

Next, we prove the Theorem 4.

###### Proof of Theorem 4.

By same argument in the proof of Theorem 3, if $U^{0}\leq TU^{0}$, we can show
that $U^{k-1}\leq U^{k}\leq TU^{k-1}\leq TU^{k}$ for $k=1,2,\dots.$, and

$\displaystyle\left\|{TU^{k}-U^{k}}\right\|_{\infty}\leq\frac{2}{k+1}\left\|{U^{0}-U^{\star}}\right\|_{\infty}$

for any fixed point $U^{\star}$. Since $U^{k}$ is increasing and bounded by
Lemma 14 and previous argument, $U^{k}$ converges pointwise to some
$\tilde{U}^{\star}$ in general action-state space. We now show that $TU^{k}$
also converges pointwise to $T\tilde{U}^{\star}$. First, let $T$ be Bellman
consistency operator and $U=V,\tilde{U}^{\star}=\tilde{V}^{\pi}$. By monontone
convergence theorem,

$\displaystyle\lim_{k\rightarrow\infty}T^{\pi}V^{k}(s)$
$\displaystyle=\lim_{k\rightarrow\infty}\mathbb{E}_{a\sim\pi(\cdot\,|\,s)}\left[\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[r(s,a)+\gamma V^{k}(s^{\prime})\right]\right]$
$\displaystyle=\mathbb{E}_{a\sim\pi(\cdot\,|\,s)}\left[\lim_{k\rightarrow\infty}\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[r(s,a)+\gamma V^{k}(s^{\prime})\right]\right]$
$\displaystyle=\mathbb{E}_{a\sim\pi(\cdot\,|\,s)}\left[\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[r(s,a)+\gamma\lim_{k\rightarrow\infty}V^{k}(s^{\prime})\right]\right]$
$\displaystyle=T^{\pi}\tilde{V}^{\pi}(s)$

for any fixed $s\in\mathcal{S}$. With same argument, case $U=Q$ also holds. If
$T$ is Bellman optimality operator, we use following lemma.

######  Lemma 15.

Let $W,W^{k}\in\mathcal{F}(\mathcal{X})$ for $k=0,1,\dots$. If $W^{k}(x)\leq
W^{k+1}(x)$ for all $x\in\mathcal{X}$, and $\\{W^{k}\\}_{k=0,1,\dots,}$
converge pointwise to $W$, then
$\lim_{k\rightarrow\infty}\\{\sup_{x}W^{k}(x)\\}=\sup_{x}W(x)$.

###### Proof.

$W^{k}(x)\leq W(x)$ implies that $\sup_{x}W^{k}(x)\leq\sup_{x}W(x)$. If
$\sup_{x}W(x)=a$, there exist $x$ which satisfying
$a-W(x)<\frac{\epsilon}{2}$, and by definition of $W$, there exist $W^{k}$
such that $a-W^{k}(x)<\epsilon$ for any $\epsilon>0$. ∎

If $U=V$ and $\tilde{U}^{\star}=\tilde{V}^{\star}$, by previous lemma and
monotone convergence theorem, we have

$\displaystyle\lim_{k\rightarrow\infty}T^{\star}V^{k}(s)$
$\displaystyle=\lim_{k\rightarrow\infty}\sup_{a}\left\\{\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[r(s,a)+\gamma V^{k}(s^{\prime})\right]\right\\}$
$\displaystyle=\sup_{a}\left\\{\lim_{k\rightarrow\infty}\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[r(s,a)+\gamma V^{k}(s^{\prime})\right]\right\\}$
$\displaystyle=\sup_{a}\left\\{\mathbb{E}_{s^{\prime}\sim
P(\cdot\,|\,s,a)}\left[r(s,a)+\gamma\lim_{k\rightarrow\infty}V^{k}(s^{\prime})\right]\right\\}$
$\displaystyle=T^{\star}\tilde{U}^{\star}(s)$

for any fixed $s\in\mathcal{S}$. With similar argument, case $U=Q$ also holds.

Since $TU^{k}\rightarrow T\tilde{U}^{\star}$ and
$U^{k}\rightarrow\tilde{U}^{\star}$ pointwisely, $TU^{k}-U^{k}$ converges
pointwise to $T\tilde{U}^{\star}-\tilde{U}^{\star}=0$. Thus,
$\tilde{U}^{\star}$ is indeed fixed point of $T$. Furthermore, the fact that
$U^{0}\leq TU^{0}\leq\tilde{U}^{\star}$ implies that Lemma 6 and 12 hold.
Therefore, we have

$\displaystyle\left\|{TU^{k}-U^{k}}\right\|_{\infty}\leq\frac{1}{k+1}\left\|{U^{0}-\tilde{U}^{\star}}\right\|_{\infty}.$

∎

##  Appendix D Omitted proofs in Section 4

We present the proof of Theorem 5.

###### Proof of Theorem 5.

First, we prove the case $U^{0}=0$ for $n\geq k+2$. Consider the MDP
$(\mathcal{S},\mathcal{A},P,r,\gamma)$ such that

$\displaystyle\mathcal{S}=\\{s_{1},\dots,s_{n}\\},\quad\mathcal{A}=\\{a_{1}\\},\quad
P(s_{i}\,|\,s_{j},a_{1})=\mathds{1}_{\\{i=j=1,\,j=i+1\\}},\quad
r(s_{i},a_{1})=\mathds{1}_{\\{i=2\\}}.$

Then,
$T=\gamma\mathcal{P}^{\pi}U+[0,1,0,\dots,0]^{\intercal},U^{\star}=[0,1,\gamma,\dots,\gamma^{n-2}]^{\intercal}$,
and $\left\|{U^{0}-U^{\star}}\right\|_{\infty}=1$. Under the span condition,
we can show that $\left({U^{k}}\right)_{1}=\left({U^{k}}\right)_{l}=0$ for
$k+2\leq l\leq n$ by following lemma.

######  Lemma 16.

Let $T\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be defined as before.
Then, under span condition, $\left({U^{i}}\right)_{1}=0$ for $0\leq i\leq k$,
and $\left({U^{i}}\right)_{j}=0$ for $0\leq i\leq k$ and $i+2\leq j\leq n$.

###### Proof.

Case $k=0$ is obvious. By induction, $\left({U^{l}}\right)_{1}=0$ for $0\leq
l\leq i-1$. Then $\left({TU^{l}}\right)_{1}=0$ for $0\leq l\leq i-1$. This
implies that $\left({TU^{l}-U^{l}}\right)_{1}=0$ for $0\leq l\leq i-1$. Hence
$\left({U^{i}}\right)_{1}=\left({U^{0}}\right)_{1}=0$. Again, by induction,
$\left({U^{l}}\right)_{j}=0$ for $0\leq l\leq i-1$, $l+2\leq j\leq n$. Then
$\left({TU^{l}}\right)_{j}=0$ for $0\leq l\leq i-1$, $l+3\leq j\leq n$ and
this implies that $\left({TU^{l}-U^{l}}\right)_{j}=0$ for $0\leq l\leq i-1$,
$l+3\leq j\leq n$. Therefore, $\left({U^{i}}\right)_{j}=0$ for $i+2\leq j\leq
n$. ∎

Then, we get

$\displaystyle
TU^{k}-U^{k}=\Big{(}0,1-\left({U^{k}}\right)_{2},\gamma\left({U^{k}}\right)_{2}-\left({U^{k}}\right)_{3},\dots,\gamma\left({U^{k}}\right)_{k}-\left({U^{k}}\right)_{k+1},\gamma\left({U^{k}}\right)_{k+1},\underbrace{0,\dots,0}_{n-k-2}\Big{)},$

and this implies

$\left({TU^{k}-U^{k}}\right)_{2}+\gamma^{-1}\left({TU^{k}-U^{k}}\right)_{3}+\cdots+\gamma^{-k}\left({TU^{k}-U^{k}}\right)_{k+2}=1.$

Taking the absolute value on both sides,

$\displaystyle(1+\cdots+\gamma^{-k})\max_{1\leq i\leq
n}{\\{|TU^{k}-U^{k}|_{i}\\}}\geq 1.$

Therefore, we conclude

$\displaystyle\|TU^{k}-U^{k}\|_{\infty}\geq\frac{\gamma^{k}}{\sum_{i=0}^{k}\gamma^{i}}\left\|{U^{0}-U^{\star}}\right\|_{\infty}.$

Now, we show that for any initial point $U^{0}\in\mathbb{R}^{n}$, there exists
an MDP which exhibits same lower bound with the case $U^{0}=0$. Denote by
MDP($0$) and $T_{0}$ the worst-case MDP and Bellman consistency or opitmality
operator constructed for $U^{0}=0$. Define an MDP($U^{0}$)
$(\mathcal{S},\mathcal{A},P,r,\gamma)$ for $U^{0}\neq 0$ as

$\displaystyle\mathcal{S}=\\{s_{1},\dots,s_{n}\\},\,\,\mathcal{A}=\\{a_{1}\\},\,\,P(s_{i}\,|\,s_{j},a_{1})=\mathds{1}_{\\{i=j=1,\,j=i+1\\}},\,\,r(s_{i},a_{1})=\left({U^{0}-\mathcal{P}^{\pi}U^{0}}\right)_{i}+\mathds{1}_{\\{i=2\\}}.$

Then, Bellman consistency or optimality operator $T$ satisfies

$TU=T_{0}(U-U^{0})+U^{0}.$

Let $\tilde{U}^{\star}$ be fixed point of $T_{0}$. Then, if
$U^{\star}=\tilde{U}^{\star}+U^{0}$, $U^{\star}$ is fixed point of $T$.
Furthermore, if $\\{U^{i}\\}^{k}_{i=0}$ satisfies span condition

$U^{i}\in
U^{0}+span\\{TU^{0}-U^{0},TU^{1}-U^{1},\dots,TU^{i-1}-U^{i-1}\\},\qquad
i=1,\dots,k,$

$\tilde{U^{i}}=U^{i}-U^{0}$ is a sequence satisfying

$\tilde{U}^{i}\in\underbrace{\,\tilde{U}^{0}}_{=0}+span\\{T_{0}\tilde{U}^{0}-\tilde{U}^{0},T_{0}\tilde{U}^{1}-\tilde{U}^{1},\dots,T_{0}\tilde{U}^{i-1}-\tilde{U}^{i-1}\\},\qquad
i=1,\dots,k,$

which is the same span condition in Theorem 5 with respect to $T_{0}$. This is
because

$TU^{i}-U^{i}=T_{0}(U^{i}-U^{0})-(U^{i}-U^{0})=T\tilde{U}^{i}-\tilde{U}^{i}$

for $i=0,\dots,k$. Thus, $\\{\tilde{U}^{i}\\}^{k}_{i=0}$ is a sequence
starting from $0$ and satisfy the span condition for $T_{0}$. This implies
that

$\displaystyle\left\|{TU^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle=\left\|{T\tilde{U}^{k}-\tilde{U}^{k}}\right\|_{\infty}$
$\displaystyle\geq\frac{\gamma^{k}}{\sum^{k}_{i=0}\gamma^{i}}\left\|{\tilde{U}^{0}-\tilde{U}^{\star}}\right\|_{\infty}$
$\displaystyle=\frac{\gamma^{k}}{\sum^{k}_{i=0}\gamma^{i}}\left\|{U^{0}-U^{\star}}\right\|_{\infty}.$

Hence, MDP($U^{0}$) is indeed our desired worst-case instance. Lastly, the
fact that
$U^{0}-U^{\star}=\tilde{U}^{0}-\tilde{U}^{\star}=-(0,1,\gamma,\dots,\gamma^{n-2})$
implies $U^{0}\leq U^{\star}$.

∎

##  Appendix E Omitted proofs in Section 5

First, we prove following key lemma.

######  Lemma 17.

Let $0<\gamma<1$. For the iterates $\\{U^{k}\\}_{k=0,1,\dots}$ of Anc-VI,
there exist nonexpansive linear operators
$\\{\mathcal{P}^{l}\\}_{l=0,1,\dots,k}$ and
$\\{\hat{\mathcal{P}}^{l}\\}_{l=0,1,\dots,k}$ such that

$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle\leq\sum_{i=1}^{k}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})\right]-\beta_{k}(U^{0}-U^{\star})$
$\displaystyle\quad+\Pi^{k}_{j=1}(1-\beta_{j})\Pi^{0}_{l=k}\gamma\mathcal{P}^{l}(U^{0}-U^{\star})-\sum_{i=1}^{k}\Pi^{k}_{j=i}(1-\beta_{j})\Pi^{i+1}_{l=k}\gamma\mathcal{P}^{l}\left({I-\gamma\mathcal{P}^{{i}}}\right)\epsilon^{i-1},$
$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle\geq\sum_{i=1}^{k}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})\right]-\beta_{k}(U^{0}-\hat{U}^{\star})$
$\displaystyle\quad+\Pi^{k}_{j=1}(1-\beta_{j})\Pi^{0}_{l=k}\gamma\hat{\mathcal{P}}^{l}(U^{0}-\hat{U}^{\star})-\sum_{i=1}^{k}\Pi^{k}_{j=i}(1-\beta_{j})\Pi^{i+1}_{l=k}\gamma\hat{\mathcal{P}}^{l}\left({I-\gamma\hat{\mathcal{P}}^{{i}}}\right)\epsilon^{i-1},$

for $1\leq k$, where $\Pi^{k}_{j=k+1}(1-\beta_{j})=1$,
$\Pi^{k+1}_{l=k}\gamma\mathcal{P}^{l}=\Pi^{k+1}_{l=k}\gamma\hat{\mathcal{P}}^{l}=I$,
and $\beta_{0}=1$.

###### Proof of Lemma 17.

First, we prove the first inequality in Lemma 17 by induction.

If $k=1$,

$\displaystyle U^{1}-(1-\beta_{1})U^{0}-\beta_{1}U^{\star}$
$\displaystyle=(1-\beta_{1})\epsilon^{0}+\beta_{1}(U^{0}-U^{\star})+(1-\beta_{1})(T^{\star}U^{0}-U^{0})$
$\displaystyle\leq(1-\beta_{1})\epsilon^{0}+(1-\beta_{1})\gamma\mathcal{P}^{0}(U^{0}-U^{\star})+(2\beta_{1}-1)(U^{0}-U^{\star}),$

where inequality comes from Lemma 8 with
$\alpha=1,U=U^{0},\bar{U}=U^{0}-U^{\star}$, and let $\bar{U}$ be the entire
right hand side of inequality. Then, we have

$\displaystyle T^{\star}U^{1}-U^{1}$
$\displaystyle=T^{\star}U^{1}-(1-\beta_{1})T^{\star}U^{0}-\beta_{1}U^{\star}-\beta_{1}(U^{0}-U^{\star})-(1-\beta_{1})\epsilon^{0}$
$\displaystyle\leq\gamma\mathcal{P}^{1}((1-\beta_{1})\epsilon^{0}+(1-\beta_{1})\gamma\mathcal{P}^{0}(U^{0}-U^{\star})+(2\beta_{1}-1)(U^{0}-U^{\star}))-\beta_{1}(U^{0}-U^{\star})$
$\displaystyle\quad-(1-\beta_{1})\epsilon^{0}$
$\displaystyle=(1-\beta_{1})\gamma\mathcal{P}^{1}\gamma\mathcal{P}^{0}(U^{0}-U^{\star})+\gamma\mathcal{P}^{1}(2\beta_{1}-1)(U^{0}-U^{\star})-\beta_{1}(U^{0}-U^{\star})$
$\displaystyle\quad-(I-\gamma\mathcal{P}^{1})(1-\beta_{1})\epsilon^{0}.$

where inequality comes from Lemma 8 with
$\alpha=\beta_{1},U=U^{1},\tilde{U}=U^{0}$, and previously defined $\bar{U}$.

By induction,

$\displaystyle U^{k}-(1-\beta_{k})U^{k-1}-\beta_{k}U^{\star}$
$\displaystyle=\beta_{k}\left({U^{0}-U^{\star}}\right)+(1-\beta_{k})(T^{\star}U^{k-1}-U^{k-1})+(1-\beta_{k})\epsilon^{k-1}$
$\displaystyle\leq(1-\beta_{k})\sum_{i=1}^{k-1}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k-1}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k-1}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})\right]$
$\displaystyle\quad-(1-\beta_{k})\beta_{k-1}(U^{0}-U^{\star})+(1-\beta_{k})\left({\Pi^{k-1}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k-1}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})$
$\displaystyle\quad+\beta_{k}(U^{0}-U^{\star})-(1-\beta_{k})\sum_{i=1}^{k-1}\Pi^{k-1}_{j=i}(1-\beta_{j})\Pi^{i+1}_{l=k-1}\gamma\mathcal{P}^{l}\left({I-\gamma\mathcal{P}^{{i}}}\right)\epsilon^{i-1}+(1-\beta_{k})\epsilon^{k-1},$

and let $\bar{U}$ be the entire right hand side of inequality. Then, we have

$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle=T^{\star}U^{k}-(1-\beta_{k})T^{\star}U^{k-1}-\beta_{k}U^{0}-(1-\beta_{k})\epsilon^{k-1}$
$\displaystyle=T^{\star}U^{k}-(1-\beta_{k})T^{\star}U^{k-1}-\beta_{k}T^{\star}U^{\star}-\beta_{k}(U^{0}-U^{\star})-(1-\beta_{k})\epsilon^{k-1}$
$\displaystyle\leq\gamma\mathcal{P}^{k}\bigg{(}(1-\beta_{k})\sum_{i=1}^{k-1}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k-1}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k-1}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})\right]$
$\displaystyle\quad-(1-\beta_{k})\beta_{k-1}(U^{0}-U^{\star})+(1-\beta_{k})\left({\Pi^{k-1}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k-1}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})$
$\displaystyle\quad+\beta_{k}(U^{0}-U^{\star})-(1-\beta_{k})\sum_{i=1}^{k-1}\Pi^{k-1}_{j=i}(1-\beta_{j})\Pi^{i+1}_{l=k-1}\gamma\mathcal{P}^{l}\left({I-\gamma\mathcal{P}^{{i}}}\right)\epsilon^{i-1}+(1-\beta_{k})\epsilon^{k-1}\bigg{)}$
$\displaystyle\quad-\beta_{k}(U^{0}-U^{\star})-(1-\beta_{k})\epsilon^{k-1}$
$\displaystyle=\sum_{i=1}^{k}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})\right]-\beta_{k}(U^{0}-U^{\star})$
$\displaystyle\quad+\Pi^{k}_{j=1}(1-\beta_{j})\Pi^{0}_{l=k}\gamma\mathcal{P}^{l}(U^{0}-U^{\star})-\sum_{i=1}^{k}\Pi^{k}_{j=i}(1-\beta_{j})\Pi^{i+1}_{l=k}\gamma\mathcal{P}^{l}\left({I-\gamma\mathcal{P}^{{i}}}\right)\epsilon^{i-1},$

where inequality comes from Lemma 8 with
$\alpha=\beta_{k},U=U^{k},\tilde{U}=U^{k-1}$, and previously defined
$\bar{U}$.

Now, we prove second inequality in Lemma 17 by induction.

If $k=1$,

$\displaystyle U^{1}-(1-\beta_{1})U^{0}-\beta_{1}\hat{U}^{\star}$
$\displaystyle=(1-\beta_{1})\epsilon^{0}+\beta_{1}(U^{0}-\hat{U}^{\star})+(1-\beta_{1})(T^{\star}U^{0}-U^{0})$
$\displaystyle\geq(1-\beta_{1})\epsilon^{0}+(1-\beta_{1})\gamma\hat{\mathcal{P}}^{0}(U^{0}-\hat{U}^{\star})+(2\beta_{1}-1)(U^{0}-\hat{U}^{\star}),$

where inequality comes from Lemma 9 with
$\alpha=1,U=U^{0},\bar{U}=U^{0}-\hat{U}^{\star}$, and let $\bar{U}$ be the
entire right hand side of inequality. Then, we have

$\displaystyle T^{\star}U^{1}-U^{1}$
$\displaystyle=T^{\star}U^{1}-(1-\beta_{1})T^{\star}U^{0}-\beta_{1}\hat{U}^{\star}-\beta_{1}(U^{0}-\hat{U}^{\star})-(1-\beta_{1})\epsilon^{0}$
$\displaystyle\geq\gamma\hat{\mathcal{P}}^{1}((1-\beta_{1})\epsilon^{0}+(1-\beta_{1})\gamma\hat{\mathcal{P}}^{0}(U^{0}-\hat{U}^{\star})+(2\beta_{1}-1)(U^{0}-\hat{U}^{\star}))-\beta_{1}(U^{0}-\hat{U}^{\star})$
$\displaystyle\quad-(1-\beta_{1})\epsilon^{0}$
$\displaystyle=(1-\beta_{1})\gamma\hat{\mathcal{P}}^{1}\gamma\hat{\mathcal{P}}^{0}(U^{0}-\hat{U}^{\star})+\gamma\hat{\mathcal{P}}^{1}(2\beta_{1}-1)(U^{0}-\hat{U}^{\star})-\beta_{1}(U^{0}-\hat{U}^{\star})$
$\displaystyle\quad-(I-\gamma\hat{\mathcal{P}}^{1})(1-\beta_{1})\epsilon^{0}.$

where inequality comes from Lemma 9 with
$\alpha=\beta_{1},U=U^{1},\tilde{U}=U^{0}$, and previously defined $\bar{U}$.

By induction,

$\displaystyle U^{k}-(1-\beta_{k})U^{k-1}-\beta_{k}\hat{U}^{\star}$
$\displaystyle=\beta_{k}\left({U^{0}-\hat{U}^{\star}}\right)+(1-\beta_{k})(T^{\star}U^{k-1}-U^{k-1})+(1-\beta_{k})\epsilon^{k-1}$
$\displaystyle\geq(1-\beta_{k})\sum_{i=1}^{k-1}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k-1}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k-1}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})\right]$
$\displaystyle\quad-(1-\beta_{k})\beta_{k-1}(U^{0}-\hat{U}^{\star})+(1-\beta_{k})\left({\Pi^{k-1}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k-1}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})$
$\displaystyle\quad+\beta_{k}(U^{0}-\hat{U}^{\star})-(1-\beta_{k})\sum_{i=1}^{k-1}\Pi^{k-1}_{j=i}(1-\beta_{j})\Pi^{i+1}_{l=k-1}\gamma\hat{\mathcal{P}}^{l}\left({I-\gamma\hat{\mathcal{P}}^{{i}}}\right)\epsilon^{i-1}+(1-\beta_{k})\epsilon^{k-1},$

and let $\bar{U}$ be the entire right hand side of inequality. Then, we have

$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle=T^{\star}U^{k}-(1-\beta_{k})T^{\star}U^{k-1}-\beta_{k}U^{0}-(1-\beta_{k})\epsilon^{k-1}$
$\displaystyle=T^{\star}U^{k}-(1-\beta_{k})T^{\star}U^{k-1}-\beta_{k}T^{\star}\hat{U}^{\star}-\beta_{k}(U^{0}-\hat{U}^{\star})-(1-\beta_{k})\epsilon^{k-1}$
$\displaystyle\geq\gamma\hat{\mathcal{P}}^{k}\bigg{(}(1-\beta_{k})\sum_{i=1}^{k-1}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k-1}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k-1}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})\right]$
$\displaystyle\quad-(1-\beta_{k})\beta_{k-1}(U^{0}-\hat{U}^{\star})+(1-\beta_{k})\left({\Pi^{k-1}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k-1}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})$
$\displaystyle\quad+\beta_{k}(U^{0}-\hat{U}^{\star})-(1-\beta_{k})\sum_{i=1}^{k-1}\Pi^{k-1}_{j=i}(1-\beta_{j})\Pi^{i+1}_{l=k-1}\gamma\hat{\mathcal{P}}^{l}\left({I-\gamma\hat{\mathcal{P}}^{{i}}}\right)\epsilon^{i-1}+(1-\beta_{k})\epsilon^{k-1}\bigg{)}$
$\displaystyle\quad-\beta_{k}(U^{0}-\hat{U}^{\star})-(1-\beta_{k})\epsilon^{k-1}$
$\displaystyle=\sum_{i=1}^{k}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})\right]-\beta_{k}(U^{0}-\hat{U}^{\star})$
$\displaystyle\quad+\Pi^{k}_{j=1}(1-\beta_{j})\Pi^{0}_{l=k}\gamma\hat{\mathcal{P}}^{l}(U^{0}-\hat{U}^{\star})-\sum_{i=1}^{k}\Pi^{k}_{j=i}(1-\beta_{j})\Pi^{i+1}_{l=k}\gamma\hat{\mathcal{P}}^{l}\left({I-\gamma\hat{\mathcal{P}}^{{i}}}\right)\epsilon^{i-1},$

where inequality comes from Lemma 9 with
$\alpha=\beta_{k},U=U^{k},\tilde{U}=U^{k-1}$, and previously defined $\bar{U}$
∎

Now, we prove the first rate in Theorem 6.

###### Proof of first rate in Theorem 6.

Since $B_{1}\leq A\leq B_{2}$ implies
$\left\|{A}\right\|_{\infty}\leq\sup\\{\left\|{B_{1}}\right\|_{\infty},\left\|{B_{2}}\right\|_{\infty}\\}$
for $A,B\in\mathcal{F}(\mathcal{X})$, if we take
$\left\|{\cdot}\right\|_{\infty}$ right side of first inequality in Lemma 17,
we have

$\displaystyle\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-U^{\star}}\right\|_{\infty}+(1+\gamma)\sum_{i=1}^{k}\left({\Pi^{k}_{j=i}(1-\beta_{j})}\right)\gamma^{k-i}\left\|{\epsilon^{i-1}}\right\|_{\infty}$
$\displaystyle\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-U^{\star}}\right\|_{\infty}+\frac{1+\gamma}{1+\gamma^{k+1}}\frac{1-\gamma^{k}}{1-\gamma}\max_{0\leq
i\leq k-1}\left\|{\epsilon^{i}}\right\|_{\infty}.$

If we apply second inequality of Lemma 17 and take
$\left\|{\cdot}\right\|_{\infty}$-norm right side, we have

$\displaystyle\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\left\|{U^{0}-\hat{U}^{\star}}\right\|_{\infty}+\frac{1+\gamma}{1+\gamma^{k+1}}\frac{1-\gamma^{k}}{1-\gamma}\max_{0\leq
i\leq k-1}\left\|{\epsilon^{i}}\right\|_{\infty}.$

Therefore, we get

$\displaystyle\left\|{T^{\star}U^{k}-U^{k}}\right\|_{\infty}$
$\displaystyle\leq\frac{\left({\gamma^{-1}-\gamma}\right)\left({1+2\gamma-\gamma^{k+1}}\right)}{\left({\gamma^{k+1}}\right)^{-1}-\gamma^{k+1}}\max{\left\\{\left\|{U^{0}-U^{\star}}\right\|_{\infty},\left\|{U^{0}-\hat{U}^{\star}}\right\|_{\infty}\right\\}}$
$\displaystyle\quad+\frac{1+\gamma}{1+\gamma^{k+1}}\frac{1-\gamma^{k}}{1-\gamma}\max_{0\leq
i\leq k-1}\left\|{\epsilon^{i}}\right\|_{\infty}.$

∎

Now, for the second rate in Theorem 6, we present following key lemma.

######  Lemma 18.

Let $0<\gamma<1$. For the iterates $\\{U^{k}\\}_{k=0,1,\dots}$ of Anc-VI, if
$U^{0}\geq T^{\star}U^{0}$, there exist nonexpansive linear operators
$\\{\mathcal{P}^{l}\\}_{l=0,1,\dots,k}$ and
$\\{\hat{\mathcal{P}}^{l}\\}_{l=0,1,\dots,k}$ such that

$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle\leq\Pi^{k}_{j=1}(1-\beta_{j})\Pi^{0}_{l=k}\gamma\mathcal{P}^{l}(U^{0}-U^{\star})-\sum_{i=1}^{k}\Pi^{k}_{j=i}(1-\beta_{j})\Pi^{i+1}_{l=k}\gamma\mathcal{P}^{l}\left({I-\gamma\mathcal{P}^{{i}}}\right)\epsilon^{i-1}$
$\displaystyle\quad-\beta^{k}(U^{0}-U^{\star}),$ $\displaystyle
T^{\star}U^{k}-U^{k}$
$\displaystyle\geq\sum_{i=1}^{k}\left[(\beta_{i}-\beta_{i-1}(1-\beta_{i}))\left({\Pi^{k}_{j=i+1}(1-\beta_{j})}\right)\left({\Pi^{i}_{l=k}\gamma\hat{\mathcal{P}}^{l}}\right)(U^{0}-\hat{U}^{\star})\right]-\beta_{k}(U^{0}-\hat{U}^{\star})$
$\displaystyle\quad-\sum_{i=1}^{k}\Pi^{k}_{j=i}(1-\beta_{j})\Pi^{i+1}_{l=k}\gamma\hat{\mathcal{P}}^{l}\left({I-\gamma\hat{\mathcal{P}}^{{i}}}\right)\epsilon^{i-1},$

for $1\leq k$, where $\Pi^{k}_{j=k+1}(1-\beta_{j})=1$,
$\Pi^{k+1}_{l=k}\gamma\mathcal{P}^{l}=\Pi^{k+1}_{l=k}\gamma\hat{\mathcal{P}}^{l}=I$,
and $\beta_{0}=1$.

###### Proof of Lemma 18.

If $U^{0}\geq T^{\star}U^{0}$,
$U^{0}\geq\lim_{m\rightarrow\infty}(T^{\star})^{m}U^{0}=U^{\star}$ by Lemma 1.
By Lemma 3, this also implies $U^{0}\geq\hat{U}^{\star}$.

First, we prove first inequality in Lemma 18 by induction. If $k=1$,

$\displaystyle U^{1}-(1-\beta_{1})U^{0}-\beta_{1}U^{\star}$
$\displaystyle=(1-\beta_{1})\epsilon^{0}+\beta_{1}(U^{0}-U^{\star})+(1-\beta_{1})(T^{\star}U^{0}-U^{0})$
$\displaystyle\leq(1-\beta_{1})\epsilon^{0}+(1-\beta_{1})\gamma\mathcal{P}^{0}(U^{0}-U^{\star})+(2\beta_{1}-1)(U^{0}-U^{\star})$
$\displaystyle\leq(1-\beta_{1})\epsilon^{0}+(1-\beta_{1})\gamma\mathcal{P}^{0}(U^{0}-U^{\star}),$

where the second inequality is from the $(2\beta_{1}-1)(U^{0}-U^{\star})\leq
0$, and first inequality comes from Lemma 8 with
$\alpha=1,U=U^{0},\bar{U}=U^{0}-U^{\star}$, and let $\bar{U}$ be the entire
right hand side of inequality. Then, we have

$\displaystyle T^{\star}U^{1}-U^{1}$
$\displaystyle=T^{\star}U^{1}-(1-\beta_{1})T^{\star}U^{0}-\beta_{1}U^{\star}-\beta_{1}(U^{0}-U^{\star})-(1-\beta_{1})\epsilon^{0}$
$\displaystyle\leq\gamma\mathcal{P}^{1}((1-\beta_{1})\epsilon^{0}+(1-\beta_{1})\gamma\mathcal{P}^{0}(U^{0}-U^{\star}))-\beta_{1}(U^{0}-U^{\star})-(1-\beta_{1})\epsilon^{0}$
$\displaystyle=(1-\beta_{1})\gamma\mathcal{P}^{1}\gamma\mathcal{P}^{0}(U^{0}-U^{\star})-\beta_{1}(U^{0}-U^{\star})-(I-\gamma\mathcal{P}^{1})(1-\beta_{1})\epsilon^{0}.$

where inequality comes from Lemma 8 with
$\alpha=\beta_{1},U=U^{1},\tilde{U}=U^{0}$, and previously defined $\bar{U}$.

By induction,

$\displaystyle U^{k}-(1-\beta_{k})U^{k-1}-\beta_{k}U^{\star}$
$\displaystyle=\beta_{k}\left({U^{0}-U^{\star}}\right)+(1-\beta_{k})(T^{\star}U^{k-1}-U^{k-1})+(1-\beta_{k})\epsilon^{k-1}$
$\displaystyle\leq\beta_{k}(U^{0}-U^{\star})-(1-\beta_{k})\beta_{k-1}(U^{0}-U^{\star})+(1-\beta_{k})\left({\Pi^{k-1}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k-1}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})$
$\displaystyle\quad+(1-\beta_{k})\epsilon^{k-1}-(1-\beta_{k})\sum_{i=1}^{k-1}\Pi^{k-1}_{j=i}(1-\beta_{j})\Pi^{i+1}_{l=k-1}\gamma\mathcal{P}^{l}\left({I-\gamma\mathcal{P}^{{i}}}\right)\epsilon^{i-1}$
$\displaystyle\leq(1-\beta_{k})\left({\Pi^{k-1}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k-1}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})+(1-\beta_{k})\epsilon^{k-1}$
$\displaystyle-(1-\beta_{k})\sum_{i=1}^{k-1}\Pi^{k-1}_{j=i}(1-\beta_{j})\Pi^{i+1}_{l=k-1}\gamma\mathcal{P}^{l}\left({I-\gamma\mathcal{P}^{{i}}}\right)\epsilon^{i-1},$

where the second inequality is from $\beta_{k}-(1-\beta_{k})\beta_{k-1}\leq 0$
and let $\bar{U}$ be the entire right hand side of inequality. Then, we have

$\displaystyle T^{\star}U^{k}-U^{k}$
$\displaystyle=T^{\star}U^{k}-(1-\beta_{k})T^{\star}U^{k-1}-\beta_{k}T^{\star}U^{\star}-\beta_{k}(U^{0}-U^{\star})-(1-\beta_{k})\epsilon^{k-1}$
$\displaystyle\leq\gamma\mathcal{P}^{k}\bigg{(}(1-\beta_{k})\left({\Pi^{k-1}_{j=1}(1-\beta_{j})}\right)\left({\Pi^{0}_{l=k-1}\gamma\mathcal{P}^{l}}\right)(U^{0}-U^{\star})+(1-\beta_{k})\epsilon^{k-1}$