$\displaystyle\mathbb{E}_{S_{k}\sim\kappa_{b}}\left[[F(Q,S_{k},A_{k},S_{k+1})](s,a)\right]$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{k}\sim\kappa_{b}}\left[\mathbbm{1}_{\\{(S_{k},A_{k})=(s,a)\\}}\left(\mathcal{R}(S_{k},A_{k})+\gamma\max_{a^{\prime}\in\mathcal{A}}Q(S_{k+1},a^{\prime})-Q(S_{k},A_{k})\right)+Q(s,a)\right]$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{k}\sim\kappa_{b}}\left[\mathbbm{1}_{\\{(S_{k},A_{k})=(s,a)\\}}\left(\mathcal{R}(S_{k},A_{k})+\gamma\max_{a^{\prime}\in\mathcal{A}}Q(S_{k+1},a^{\prime})\right)+(1-\mathbbm{1}_{\\{(S_{k},A_{k})=(s,a)\\}})Q(S_{k},A_{k})\right]$
$\displaystyle=\;$
$\displaystyle\kappa_{b}(s)\pi_{b}(a|s)[\mathcal{H}(Q)](s,a)+(1-\kappa_{b}(s)\pi_{b}(a|s))Q(s,a),$

where
$\mathcal{H}:\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}\mapsto\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$
is the Bellman’s optimality operator defined by

$\displaystyle[\mathcal{H}(Q)](s,a)=\mathbb{E}[\mathcal{R}(S_{k},A_{k})+\gamma\max_{a^{\prime}\in\mathcal{A}}Q(S_{k+1},a^{\prime})\mid
S_{k}=s,A_{k}=a]$

for any $(s,a)$. Now use the definition of the matrix $N$ and we have
$\bar{F}(Q)=N\mathcal{H}(Q)+(I-N)Q$.

    2. (b)

Since it is well-known that the Bellman’s optimality operator
$\mathcal{H}(\cdot)$ is a $\gamma$-contraction with respect to
$\|\cdot\|_{\infty}$, we have for any
$Q_{1},Q_{2}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$:

$\displaystyle\|\bar{F}(Q_{1})-\bar{F}(Q_{2})\|_{\infty}$ $\displaystyle=\;$
$\displaystyle\|N(\mathcal{H}(Q_{1})-\mathcal{H}(Q_{2}))+(I-N)(Q_{1}-Q_{2})\|_{\infty}$
$\displaystyle=\;$
$\displaystyle\max_{(s,a)}|\kappa_{b}(s)\pi_{b}(a|s)([\mathcal{H}(Q_{1})](s,a)-[\mathcal{H}(Q_{2})](s,a))+(1-\kappa_{b}(s)\pi_{b}(a|s))(Q_{1}(s,a)-Q_{2}(s,a))|$
$\displaystyle\leq\;$
$\displaystyle\max_{(s,a)}\left[\kappa_{b}(s)\pi_{b}(a|s)|[\mathcal{H}(Q_{1})](s,a)-[\mathcal{H}(Q_{2})](s,a)|+(1-\kappa_{b}(s)\pi_{b}(a|s))|Q_{1}(s,a)-Q_{2}(s,a)|\right]$
$\displaystyle\leq\;$
$\displaystyle\max_{(s,a)}\left[\kappa_{b}(s)\pi_{b}(a|s)\|\mathcal{H}(Q_{1})-\mathcal{H}(Q_{2})\|_{\infty}+(1-\kappa_{b}(s)\pi_{b}(a|s))\|Q_{1}-Q_{2}\|_{\infty}\right]$
$\displaystyle\leq\;$
$\displaystyle\max_{(s,a)}\left[\kappa_{b}(s)\pi_{b}(a|s)\gamma\|Q_{1}-Q_{2}\|_{\infty}+(1-\kappa_{b}(s)\pi_{b}(a|s))\|Q_{1}-Q_{2}\|_{\infty}\right]$
$\displaystyle=\;$
$\displaystyle\|Q_{1}-Q_{2}\|_{\infty}\max_{(s,a)}(1-(1-\gamma)\kappa_{b}(s)\pi_{b}(a|s))$
$\displaystyle=\;$
$\displaystyle(1-N_{\min}(1-\gamma))\|Q_{1}-Q_{2}\|_{\infty}.$

Therefore, the operator $\bar{F}(\cdot)$ is a contraction mapping with respect
to $\|\cdot\|_{\infty}$, with contraction factor
$\beta_{1}=1-N_{\min}(1-\gamma)$.

    3. (c)

It is enough to show that $Q^{*}$ is a fixed-point of $\bar{F}(\cdot)$, the
uniqueness part follows from $\bar{F}(\cdot)$ being a contraction [1]. Using
the fact that $\mathcal{H}(Q^{*})=Q^{*}$, we have

$\displaystyle\bar{F}(Q^{*})=N\mathcal{H}(Q^{*})+(I-N)Q^{*}=NQ^{*}+(I-N)Q^{*}=Q^{*}.$

###  Proof of Theorem 3.1

Since the contraction norm is $\|\cdot\|_{\infty}$, Lemma 2.1 (2) is
applicable. To apply Theorem 2.1, we first identify the corresponding
constants using Proposition 3.1 in the following:

$\displaystyle A$
$\displaystyle=A_{1}+A_{2}+1=3,\;B=B_{1}+B_{2}=1,\;\varphi_{1}\leq
3,\;\varphi_{2}\geq\frac{1-\beta_{1}}{2},\;\varphi_{3}\leq\frac{456e\log(|\mathcal{S}||\mathcal{A}|)}{1-\beta_{1}},$
$\displaystyle c_{1}$
$\displaystyle\leq(\|Q_{0}-Q^{*}\|_{\infty}+\|Q_{0}\|_{\infty}+1)^{2},\;c_{2}=(3\|Q^{*}\|_{\infty}+1)^{2}.$

Now we apply Theorem 2.1 (2) (a). When $\alpha_{k}\equiv\alpha$ with $\alpha$
chosen such that

$\displaystyle\alpha
t_{\alpha}(\mathcal{M}_{Y})\leq\frac{\varphi_{2}}{\varphi_{3}A^{2}}\frac{(1-\beta_{1})^{2}}{8208e\log(|\mathcal{S}||\mathcal{A}|)}.$

we have for all $k\geq t_{\alpha}(\mathcal{M}_{Y})$:

$\displaystyle\mathbb{E}[\|Q_{k}-Q^{*}\|_{\infty}^{2}]\leq\;$
$\displaystyle\varphi_{1}c_{1}\left(1-\frac{1-\beta_{1}}{2}\alpha\right)^{k-t_{\alpha}(\mathcal{M}_{Y})}+\frac{\varphi_{3}c_{2}}{\varphi_{2}}\alpha
t_{\alpha}(\mathcal{M}_{Y})$ $\displaystyle\leq\;$ $\displaystyle
3(\|Q_{0}-Q^{*}\|_{\infty}+\|Q_{0}\|_{\infty}+1)^{2}\left(1-\frac{1-\beta_{1}}{2}\alpha\right)^{k-t_{\alpha}(\mathcal{M}_{Y})}$
$\displaystyle+\frac{912e\log(|\mathcal{S}||\mathcal{A}|)}{(1-\beta_{1})^{2}}(3\|Q^{*}\|_{\infty}+1)^{2}\alpha
t_{\alpha}(\mathcal{M}_{Y})$ $\displaystyle=\;$ $\displaystyle
c_{Q,1}\left(1-\frac{1-\beta_{1}}{2}\alpha\right)^{k-t_{\alpha}(\mathcal{M}_{Y})}+c_{Q,2}\frac{\log(|\mathcal{S}||\mathcal{A}|)}{(1-\beta_{1})^{2}}\alpha
t_{\alpha}(\mathcal{M}_{Y}),$

where $c_{Q,1}=3(\|Q_{0}-Q^{*}\|_{\infty}+\|Q_{0}\|_{\infty}+1)^{2}$ and
$c_{Q,2}=912e(3\|Q^{*}\|_{\infty}+1)^{2}$.

###  Q-Learning with Diminishing Stepsizes

We next present the finite-sample bounds for $Q$-learning with diminishing
stepsizes, whose proof follows by directly applying Theorem 2.1 (2) (b) and
(2) (c) and hence is omitted.

######  Theorem B.1.

Consider $\\{Q_{k}\\}$ of Algorithm (9). Suppose that Assumption 3.1 is
satisfied, then we have the following results.

  1. (1)

    1. (a)

When $\alpha_{k}=\frac{\alpha}{k+h}$ with $\alpha=\frac{1}{1-\beta_{1}}$ and
properly chosen $h$, there exists $K_{1}^{\prime}>0$ such that the following
inequality holds for all $k\geq K_{1}^{\prime}$:

$\displaystyle\mathbb{E}[\|Q_{k}-Q^{*}\|_{\infty}^{2}]\leq
c_{Q,1}^{\prime}\left(\frac{K_{1}^{\prime}+h}{k+h}\right)^{1/2}+2c_{Q,2}^{\prime}\frac{\log(|\mathcal{S}||\mathcal{A})}{(1-\beta_{1})^{3}}\frac{t_{k}(\mathcal{M}_{Y})}{k+h},$

where $c_{Q,1}^{\prime}=3(\|Q_{0}-Q^{*}\|_{\infty}+\|Q_{0}\|_{\infty}+1)^{2}$
and $c_{Q,2}^{\prime}=3648e(3\|Q^{*}\|_{\infty}+1)^{2}$

    2. (b)

When $\alpha_{k}=\frac{\alpha}{k+h}$ with $\alpha=\frac{2}{1-\beta_{1}}$ and
properly chosen $h$, there exists $K_{1}^{\prime}>0$ such that the following
inequality holds for all $k\geq K_{1}^{\prime}$:

$\displaystyle\mathbb{E}[\|Q_{k}-Q^{*}\|_{\infty}^{2}]\leq
c_{Q,1}^{\prime}\frac{K_{1}^{\prime}+h}{k+h}+4c_{Q,2}^{\prime}\frac{\log(|\mathcal{S}||\mathcal{A})}{(1-\beta_{1})^{3}}\frac{t_{k}(\mathcal{M}_{Y})\log(k+h)}{k+h}.$

    3. (c)

When $\alpha_{k}=\frac{\alpha}{k+h}$ with $\alpha=\frac{4}{1-\beta_{1}}$ and
properly chosen $h$, there exists $K_{1}^{\prime}>0$ such that the following
inequality holds for all $k\geq K_{1}^{\prime}$:

$\displaystyle\mathbb{E}[\|Q_{k}-Q^{*}\|_{\infty}^{2}]\leq
c_{Q,1}^{\prime}\left(\frac{K_{1}^{\prime}+h}{k+h}\right)^{2}+16c_{Q,2}^{\prime}\frac{\log(|\mathcal{S}||\mathcal{A})}{(1-\beta_{1})^{3}}\frac{t_{k}(\mathcal{M}_{Y})}{k+h}.$

  2. (2)

When $\alpha_{k}=\frac{\alpha}{(k+h)^{\xi}}$ with $\xi\in(0,1)$, $\alpha>0$,
and properly chosen $h$, there exists $K_{1}^{\prime}>0$ such that the
following inequality holds for all $k\geq K_{1}^{\prime}$:

$\displaystyle\mathbb{E}[\|Q_{k}-Q^{*}\|_{\infty}^{2}]\leq
c_{Q,1}^{\prime}\exp\left(-\frac{(1-\beta_{1})\alpha}{2(1-\xi)}((k+h)^{1-\xi}-(K_{1}^{\prime}+h)^{1-\xi})\right)+c_{Q,2}^{\prime}\frac{\log(|\mathcal{S}||\mathcal{A})}{(1-\beta_{1})^{2}}\frac{t_{k}(\mathcal{M}_{Y})}{k+h}.$

###  Proof of Corollary 3.1.1

We will derive a more general result, which implies Corollary 3.1.1. Suppose
we have a non-negative sequence $\\{z_{k}\\}$ and the following bound:

$\displaystyle z_{k}\leq(1-\tau_{1}\alpha)^{k}z_{0}+\tau_{2}\alpha
t_{\alpha},$

where $\tau_{1}\in(0,1)$, $\tau_{2}>0$, and $t_{\alpha}\leq
L(\log(1/\alpha)+1)$ for some $L>0$. Then, in order for
$z_{k}\leq\epsilon^{2}$, in view of the term $\tau_{2}\alpha t_{\alpha}$, we
need

$\displaystyle\alpha=\mathcal{O}\left(\frac{\epsilon^{2}}{\log(\frac{1}{\epsilon})}\right)\tilde{\mathcal{O}}\left(\frac{1}{\tau_{2}}\right).$

Using the bound of $\alpha$ in the term $(1-\tau_{1}\alpha)^{k}z_{0}$, we have

$\displaystyle
k=\mathcal{O}\left(\frac{\log^{2}(\frac{1}{\epsilon})}{\epsilon^{2}}\right)\tilde{\mathcal{O}}\left(\frac{\tau_{1}}{\tau_{2}}\right).$

Using this result along with Jensen’s inequality in the finite-sample bound of
$Q$-learning proves Corollary 3.1.1.

###  Comparison to [31]

In this section, we discuss the connection of our finite-sample bounds of
$Q$-learning with that of [31], which provides by far the state-of-the-art
high probability bounds of $Q$-learning. In particular, we show that

  1. (1)

The high probability bounds in [31] do not imply our mean square bounds.

  2. (2)

When compared with our results, [31] does not lead to improved dependency on
the size of the state-action space.

We begin by restating Theorem 5 in [31]. To maintain consistency, we use our
notation. Let $t_{\text{mix}}=t_{1/4}$ (cf. Definition 2.1). For any
$\delta\in(0,1)$ and $\epsilon\in(0,\frac{1}{1-\gamma}]$, let integer $T$ and
the constant stepsize $\alpha$ satisfy

$\displaystyle T$
$\displaystyle\geq\frac{c_{0}}{N_{\min}}\left(\frac{1}{(1-\gamma)^{5}\epsilon^{2}}+\frac{t_{\text{mix}}}{1-\gamma}\right)\log\left(\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\right)\log\left(\frac{1}{(1-\gamma)^{2}\epsilon}\right)$
(25) $\displaystyle\alpha$
$\displaystyle=\frac{c_{1}}{\log\left(\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\right)}\min\left(\frac{(1-\gamma)^{4}\epsilon^{2}}{\gamma^{2}},\frac{1}{t_{\text{mix}}}\right),$

where $c_{0}$ and $c_{1}$ are universal constants. Further define

$\displaystyle t_{\text{frame}}$
$\displaystyle=\frac{443t_{\text{mix}}}{N_{\min}}\log\left(\frac{4|\mathcal{S}||\mathcal{A}|T}{\delta}\right),$
$\displaystyle\quad t_{\text{th}}$
$\displaystyle=\max\left(\frac{2\log(\frac{1}{(1-\gamma)^{2}\epsilon})}{\alpha
N_{\min}},t_{\text{frame}}\right),$ $\displaystyle\mu_{\text{frame}}$
$\displaystyle=\frac{1}{2}N_{\min}t_{\text{frame}},\quad$ $\displaystyle\rho$
$\displaystyle=(1-\gamma)(1-(1-\alpha)^{\mu_{\text{frame}}}).$

Then we have the following Theorem from [31].

######  Theorem B.2 (Theorem 5 of [31]).

Consider the asynchronous $Q$-learning algorithm in Algorithm with
$\alpha_{t}\equiv\alpha$. For any $\delta\in(0,1)$ and any
$\epsilon\in(0,\frac{1}{1-\gamma}]$. there exists a universal constant $c>0$
such that with probability at least $1-6\delta$, the following relation holds
uniformly for all $t\leq T$:

$\displaystyle\|Q_{t}-Q^{*}\|_{\infty}\leq(1-\rho)^{k}\frac{\|Q_{0}-Q^{*}\|_{\infty}}{1-\gamma}+\frac{c\gamma}{1-\gamma}\|V^{*}\|_{\infty}\sqrt{\alpha\log(\frac{|\mathcal{S}||\mathcal{A}|T}{\delta})}+\epsilon,$
(26)

provided that $0<\alpha\log(\frac{|\mathcal{S}||\mathcal{A}|T}{\delta})<1$.
Here, we define
$k:=\max\\{0,\left\lfloor\frac{t-t_{\text{th}}}{t_{\text{frame}}}\right\rfloor\\}$.

######  Remark.

Given an accuracy $\epsilon>0$ and a probability threshold $\delta>0$, suppose
we want to find the number of iterations $t_{0}$ required so that
$\|Q_{t_{0}}-Q^{*}\|_{\infty}\leq\epsilon$ with probability at least
$1-\delta$. To use the high probability bound (26), we need to first find a
$T\geq t_{0}$ satisfying Eq. (25), then Eq. (26) provides a concentration
bound that holds uniformly for all $t\leq T$, and hence for $t_{0}$. Note that
the parameter $T$ appears on the RHS of Eq. (26).

To compare Theorem B.2 with our Theorem 3.1, we begin by translating the
concentration bound (26) into mean square bound through the following well-
known formula:

$\displaystyle\mathbb{E}[X]=\int_{0}^{\infty}\mathbb{P}(X>x)dx-\int_{-\infty}^{0}\mathbb{P}(X<x)dx\leq\int_{0}^{\infty}\mathbb{P}(X>x)dx,$

where $X$ is any integrable random variable. It follows that

$\displaystyle\mathbb{E}\left[\|Q_{t}-Q^{*}\|_{\infty}-(1-\rho)^{k}\frac{\|Q_{0}-Q^{*}\|_{\infty}}{1-\gamma}-\epsilon\right]$
$\displaystyle\leq\;$
$\displaystyle\int_{0}^{\infty}\mathbb{P}\left[\|Q_{t}-Q^{*}\|_{\infty}-(1-\rho)^{k}\frac{\|Q_{0}-Q^{*}\|_{\infty}}{1-\gamma}-\epsilon>x\right]dx$
$\displaystyle\leq\;$
$\displaystyle\int_{0}^{\infty}6|\mathcal{S}||\mathcal{A}|T\exp\left(-\frac{1}{\alpha}\left(\frac{(1-\gamma)x}{c\gamma\|V^{*}\|_{\infty}}\right)^{2}\right)dx$
$\displaystyle=\;$ $\displaystyle
3\sqrt{\pi}|\mathcal{S}||\mathcal{A}|T\frac{c\gamma\sqrt{\alpha}\|V^{*}\|_{\infty}}{(1-\gamma)}$
$\displaystyle\leq\;$ $\displaystyle
3\sqrt{\pi}|\mathcal{S}||\mathcal{A}|T\frac{c\sqrt{\alpha}}{(1-\gamma)^{2}}.$

Hence we have for any $0\leq t\leq T$:

$\displaystyle\mathbb{E}\left[\|Q_{t}-Q^{*}\|_{\infty}\right]\leq(1-\rho)^{k}\frac{\|Q_{0}-Q^{*}\|_{\infty}}{1-\gamma}+3\sqrt{\pi}|\mathcal{S}||\mathcal{A}|T\frac{c\sqrt{\alpha}}{(1-\gamma)^{2}}+\epsilon.$
(27)

We next try to derive sample complexity based on Eq. (27). In order to make
the second term on the RHS of Eq. (27) less than $\epsilon$, where $\epsilon$
is the given accuracy, the constant stepsize $\alpha$ must satisfy:

$\displaystyle\alpha\leq\mathcal{O}\left(\frac{(1-\gamma)^{4}\epsilon}{|\mathcal{S}|^{2}|\mathcal{A}|^{2}T^{2}}\right).$

However, under the previous upper bound on $\alpha$, the first term on the RHS
of Eq. (27) cannot be made less than $\epsilon$ when $\epsilon$ is small. To
see this, using the upper bound on $\alpha$ and we have

$\displaystyle(1-\rho)^{k}\sim\left(1-\Theta\left(\frac{1}{T^{2}}\right)\right)^{T},$

which does not go to zero as $T$ tends to infinity. Therefore, because of the
presence of $T$ on the RHS of Eq. (26), the concentration bound provided in
Theorem B.2 does not imply a mean square bound with a valid sample complexity
for any $\epsilon>0$, and hence does not imply our results.

Note that Theorem B.2 provides a concentration bound which holds uniformly for
all $t\leq T$. For a fixed $t>0$, in light of Eq. (26), we conjecture the
following stronger high probability bound. With probability at least
$1-6\delta$,

$\displaystyle\|Q_{t}-Q^{*}\|_{\infty}\leq(1-\rho)^{k}\frac{\|Q_{0}-Q^{*}\|_{\infty}}{1-\gamma}+\frac{c\gamma}{1-\gamma}\|V^{*}\|_{\infty}\sqrt{\alpha\log(\frac{|\mathcal{S}||\mathcal{A}|}{\delta})}+\epsilon,$
(28)

which is obtained by simply removing $T$ on the RHS of Eq. (26). We emphasize
that the high probability bound (28) is not obtainable from [31] due to the
artifact of their proof technique. Nevertheless, suppose one establishes a
high probability bound of the form (28). Then this would imply the following
mean square bound:

$\displaystyle\mathbb{E}\left[\|Q_{t}-Q^{*}\|_{\infty}\right]\leq(1-\rho)^{k}\frac{\|Q_{0}-Q^{*}\|_{\infty}}{1-\gamma}+3\sqrt{\pi}|\mathcal{S}||\mathcal{A}|\frac{c\sqrt{\alpha}}{(1-\gamma)^{2}}+\epsilon,$

which further gives the following sample complexity:

$\displaystyle
t=\tilde{\mathcal{O}}\left(\frac{|\mathcal{S}|^{2}|\mathcal{A}|^{2}}{\epsilon^{2}(1-\gamma)^{5}N_{\min}}\right).$

In the best case scenario, where
$N_{\min}=\frac{1}{|\mathcal{S}||\mathcal{A}|}$, the sample complexity is

$\displaystyle\tilde{\mathcal{O}}\left(\frac{|\mathcal{S}|^{3}|\mathcal{A}|^{3}}{\epsilon^{2}((1-\gamma)^{5})}\right).$

In view of the previous inequality and our sample complexity bound (cf.
Corollary 3.1.1), it is clear that the dependency on the effective horizon,
the accuracy $\epsilon$, and the size of the state-action space would be no
better than ours, even if the conjectured stronger high probability bound were
proven.

##  Appendix C V-Trace

###  Proof of Proposition 3.2

  1. (1)

Using the definition of $F(V,y)$, we have for any
$V_{1},V_{2}\in\mathbb{R}^{|\mathcal{S}|}$, $y\in\mathcal{Y}$, and
$s\in\mathcal{S}$:

$\displaystyle|[F(V_{1},y)](s)-[F(V_{2},y)](s)|$ $\displaystyle=\;$
$\displaystyle\left|\mathbbm{1}_{\\{s_{0}=s\\}}\sum_{i=0}^{n-1}\gamma^{i}\left(\prod_{j=0}^{i-1}c(s_{j},a_{j})\right)\rho(s_{i},a_{i})\left(\gamma(V_{1}(s_{i+1})-V_{2}(s_{i+1}))-(V_{1}(s_{i})-V_{2}(s_{i}))\right)+V_{1}(s)-V_{2}(s)\right|$
$\displaystyle\leq\;$ $\displaystyle
2\|V_{1}-V_{2}\|_{\infty}\sum_{i=0}^{n-1}\gamma^{i}\bar{c}^{i}\bar{\rho}+\|V_{1}-V_{2}\|_{\infty}$
$\displaystyle\leq\;$
$\displaystyle\begin{dcases}\frac{(2\bar{\rho}+1)(1-(\gamma\bar{c})^{n})}{1-\gamma\bar{c}}\|V_{1}-V_{2}\|_{\infty},&\gamma\bar{c}\neq
1,\\\ (2\bar{\rho}+1)n\|V_{1}-V_{2}\|_{\infty},&\gamma\bar{c}=1.\end{dcases}$

It follows that
$\|F(V_{1},y)-F(V_{2},y)\|_{\infty}\leq(2\bar{\rho}+1)\eta(\gamma,\bar{c})\|V_{1}-V_{2}\|_{\infty}$.

For any $y\in\mathcal{Y}$ and $s\in\mathcal{S}$, we have

$\displaystyle|[F(\bm{0},y)](s)|$
$\displaystyle=\left|\mathbbm{1}_{\\{s_{0}=s\\}}\sum_{i=0}^{n-1}\gamma^{i}\left(\prod_{j=0}^{i-1}c(s_{j},a_{j})\right)\rho(s_{i},a_{i})\mathcal{R}(s_{i},a_{i})\right|$
$\displaystyle\leq\sum_{i=0}^{n-1}\gamma^{i}\bar{c}^{i}\bar{\rho}$
$\displaystyle=\begin{dcases}\frac{\bar{\rho}(1-(\gamma\bar{c})^{n})}{1-\gamma\bar{c}},&\gamma\bar{c}\neq
1,\\\ n\bar{\rho},&\gamma\bar{c}=1.\end{dcases}$

It follows that $\|F(\bm{0},y)\|_{\infty}\leq\eta(\gamma,\bar{c})$.

  2. (2)

The proof is identical to that of Proposition 3.1 (2).

  3. (3)

    1. (a)

Using the definition of $\bar{F}(\cdot)$, we have for any
$V\in\mathbb{R}^{|\mathcal{S}|}$ and $s\in\mathcal{S}$:

$\displaystyle\mathbb{E}_{Y\sim\mu}[[F(V,Y)](s)]$ $\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\kappa}\left[\mathbbm{1}_{\\{S_{0}=s\\}}\sum_{i=0}^{n-1}\gamma^{i}\left(\prod_{j=0}^{i-1}c(S_{j},A_{j})\right)\rho(S_{i},A_{i})\left(\mathcal{R}(S_{i},A_{i})+\gamma
V(S_{i+1})-V(S_{i})\right)\right]+V(s).$

For any $0\leq i\leq n-1$, we have by the Markov property and the tower
property of conditional expectation that

$\displaystyle\mathbb{E}_{S_{0}\sim\kappa}\left[\mathbbm{1}_{\\{S_{0}=s\\}}\gamma^{i}\left(\prod_{j=0}^{i-1}c(S_{j},A_{j})\right)\rho(S_{i},A_{i})\left(\mathcal{R}(S_{i},A_{i})+\gamma
V(S_{i+1})-V(S_{i})\right)\right]$ $\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\kappa}\left[\mathbbm{1}_{\\{S_{0}=s\\}}\gamma^{i}\left(\prod_{j=0}^{i-1}c(S_{j},A_{j})\right)\mathbb{E}[\rho(S_{i},A_{i})\left(\mathcal{R}(S_{i},A_{i})+\gamma
V(S_{i+1})-V(S_{i})\right)\mid S_{i}]\right]$ $\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\kappa}\left[\mathbbm{1}_{\\{S_{0}=s\\}}\gamma^{i}\left(\prod_{j=0}^{i-1}c(S_{j},A_{j})\right)[D(R_{\pi_{\bar{\rho}}}+\gamma
P_{\pi_{\bar{\rho}}}V-V)](S_{i})\right]$ $\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\kappa}\left[\mathbbm{1}_{\\{S_{0}=s\\}}\gamma^{i}\left(\prod_{j=0}^{i-2}c(S_{j},A_{j})\right)\mathbb{E}[c(S_{i-1},A_{i-1})[D(R_{\pi_{\bar{\rho}}}+\gamma
P_{\pi_{\bar{\rho}}}V-V)](S_{i})\mid S_{i-1}]\right]$ $\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\kappa}\left[\mathbbm{1}_{\\{S_{0}=s\\}}\gamma^{i}\left(\prod_{j=0}^{i-2}c(S_{j},A_{j})\right)[(CP_{\pi_{\bar{c}}})D(R_{\pi_{\bar{\rho}}}+\gamma
P_{\pi_{\bar{\rho}}}V-V)](S_{i-1})\right]$ $\displaystyle=\;$
$\displaystyle\cdots$ $\displaystyle=\;$
$\displaystyle\mathbb{E}_{S_{0}\sim\kappa}\left[\mathbbm{1}_{\\{S_{0}=s\\}}\gamma^{i}[(CP_{\pi_{\bar{c}}})^{i}D(R_{\pi_{\bar{\rho}}}+\gamma
P_{\pi_{\bar{\rho}}}V-V)](S_{0})\right]$ $\displaystyle=\;$
$\displaystyle[\mathcal{K}(\gamma
CP_{\pi_{\bar{c}}})^{i}D(R_{\pi_{\bar{\rho}}}+\gamma
P_{\pi_{\bar{\rho}}}V-V)](s).$

Therefore, we have

$\displaystyle\bar{F}(V)$ $\displaystyle=\sum_{i=0}^{n-1}\mathcal{K}(\gamma
CP_{\pi_{\bar{c}}})^{i}D(R_{\pi_{\bar{\rho}}}+\gamma
P_{\pi_{\bar{\rho}}}V-V)+V$ (29)
$\displaystyle=\left[I-\mathcal{K}\sum_{i=0}^{n-1}(\gamma
CP_{\pi_{\bar{c}}})^{i}D(I-\gamma
P_{\pi_{\bar{\rho}}})\right]V+\sum_{i=0}^{n-1}\mathcal{K}(\gamma
CP_{\pi_{\bar{c}}})^{i}DR_{\pi_{\bar{\rho}}}.$

    2. (b)

For any $V_{1},V_{2}\in\mathbb{R}^{|\mathcal{S}|}$, we have

$\displaystyle\left\|\bar{F}(V_{1})-\bar{F}(V_{2})\right\|_{\infty}$
$\displaystyle=\left\|\left[I-\mathcal{K}\sum_{i=0}^{n-1}(\gamma
CP_{\pi_{\bar{c}}})^{i}D(I-\gamma
P_{\pi_{\bar{\rho}}})\right](V_{1}-V_{2})\right\|_{\infty}$
$\displaystyle\leq\left\|I-\mathcal{K}\sum_{i=0}^{n-1}(\gamma
CP_{\pi_{\bar{c}}})^{i}D(I-\gamma
P_{\pi_{\bar{\rho}}})\right\|_{\infty}\|V_{1}-V_{2}\|_{\infty}$

For simplicity of notation, denote $G=I-\mathcal{K}\sum_{i=0}^{n-1}(\gamma
CP_{\pi_{\bar{c}}})^{i}D(I-\gamma P_{\pi_{\bar{\rho}}})$. To evaluate the
$\ell_{\infty}$-norm of $G$, we first show that $G$ has non-negative entries.
Note that $G$ can be equivalently written by

$\displaystyle G$ $\displaystyle=I-\mathcal{K}\sum_{i=0}^{n-1}(\gamma
CP_{\pi_{\bar{c}}})^{i}D(I-\gamma P_{\pi_{\bar{\rho}}})$
$\displaystyle=I-\mathcal{K}D-\mathcal{K}\sum_{i=0}^{n-2}(\gamma
CP_{\pi_{\bar{c}}})^{i+1}D+\mathcal{K}\sum_{i=0}^{n-2}(\gamma
CP_{\pi_{\bar{c}}})^{i}\gamma DP_{\pi_{\bar{\rho}}}+\mathcal{K}(\gamma
CP_{\pi_{\bar{c}}})^{n-1}\gamma DP_{\pi_{\bar{\rho}}}$
$\displaystyle=I-\mathcal{K}D+\mathcal{K}\sum_{i=0}^{n-2}(\gamma
CP_{\pi_{\bar{c}}})^{i}\gamma(DP_{\pi_{\bar{\rho}}}-CP_{\pi_{\bar{c}}}D)+\mathcal{K}(\gamma
CP_{\pi_{\bar{c}}})^{n-1}\gamma DP_{\pi_{\bar{\rho}}}.$ (30)

In view of Eq. (30), it remains to show that the matrix
$DP_{\pi_{\bar{\rho}}}-CP_{\pi_{\bar{c}}}D$ has non-negative entries. For any
$s,s^{\prime}\in\mathcal{S}$, we have

$\displaystyle[DP_{\pi_{\bar{\rho}}}-CP_{\pi_{\bar{c}}}D](s,s^{\prime})$
$\displaystyle=D(s)P_{\pi_{\bar{\rho}}}(s,s^{\prime})-C(s)P_{\pi_{\bar{c}}}(s,s^{\prime})D(s^{\prime})$
$\displaystyle\geq
D(s)P_{\pi_{\bar{\rho}}}(s,s^{\prime})-C(s)P_{\pi_{\bar{c}}}(s,s^{\prime})$
$\displaystyle=D(s)\sum_{a\in\mathcal{A}}\pi_{\bar{\rho}}(a|s)P_{a}(s,s^{\prime})-C(s)\sum_{a\in\mathcal{A}}\pi_{\bar{c}}(a|s)P_{a}(s,s^{\prime})$
$\displaystyle=\sum_{a\in\mathcal{A}}\left[\min\left(\bar{\rho}\pi_{b}(a|s),\pi(a|s)\right)-\min\left(\bar{c}\pi_{b}(a|s),\pi(a|s)\right)\right]P_{a}(s,s^{\prime})$
$\displaystyle\geq 0,$ (31)

where the last line follows from $\bar{c}\leq\bar{\rho}$.

Now since the matrix $G$ has non-negative entries, we have

$\displaystyle\|G\|_{\infty}$ $\displaystyle=\|G\bm{1}\|_{\infty}$
($\bm{1}=(1,1,\cdots,1)^{\top}$)
$\displaystyle=\left\|\left[I-\mathcal{K}\sum_{i=0}^{n-1}(\gamma
CP_{\pi_{\bar{c}}})^{i}D(I-\gamma
P_{\pi_{\bar{\rho}}})\right]\bm{1}\right\|_{\infty}$
$\displaystyle=\left\|\bm{1}-(1-\gamma)\mathcal{K}\sum_{i=0}^{n-1}(\gamma
CP_{\pi_{\bar{c}}})^{i}D\bm{1}\right\|_{\infty}$ $\displaystyle\leq
1-\mathcal{K}_{\min}(1-\gamma)\sum_{i=0}^{n-1}(\gamma C_{\min})^{i}D_{\min}$
($0<C(s)\leq D(s)\leq 1$ for all $s$)
$\displaystyle=1-\mathcal{K}_{\min}\frac{(1-\gamma)(1-(\gamma
C_{\min})^{n})D_{\min}}{1-\gamma C_{\min}}$ $\displaystyle=\beta_{2}.$

It follows that
$\left\|\bar{F}(V_{1})-\bar{F}(V_{2})\right\|_{\infty}\leq\|G\|_{\infty}\|V_{1}-V_{2}\|_{\infty}\leq\beta_{2}\|V_{1}-V_{2}\|_{\infty}$.

    3. (c)

It is enough to show that $V_{\pi_{\bar{\rho}}}$ is a fixed-point of
$\bar{F}$, the uniqueness follows from $\bar{F}$ being a contraction operator.
Using the Bellman equation $V_{\pi_{\bar{\rho}}}=R_{\pi_{\bar{\rho}}}+\gamma
P_{\pi_{\bar{\rho}}}V_{\pi_{\bar{\rho}}}$, we have by Eq. (29) that

$\displaystyle\bar{F}(V_{\pi_{\bar{\rho}}})=V_{\pi_{\bar{\rho}}}+\mathcal{K}\sum_{i=0}^{n-1}(\gamma
CP_{\pi_{\bar{c}}})^{i}D(R_{\pi_{\bar{\rho}}}+\gamma
P_{\pi_{\bar{\rho}}}V_{\pi_{\bar{\rho}}}-V_{\pi_{\bar{\rho}}})=V_{\pi_{\bar{\rho}}}.$

###  Proof of Theorem 3.2

We will apply Theorem 2.1 and Lemma 2.1 (2) to the V-trace algorithm. We begin
by identifying the constants:

$\displaystyle A$ $\displaystyle=A_{1}+A_{2}+1\leq
2(\bar{\rho}+1)\eta(\gamma,\bar{c}),\;B=B_{1}+B_{2}=\bar{\rho}\eta(\gamma,\bar{c}),\;\varphi_{1}\leq
3,\;\varphi_{2}\geq\frac{1-\beta_{2}}{2},\;\varphi_{3}\leq\frac{456e\log(|\mathcal{S}|)}{1-\beta_{2}}$
$\displaystyle c_{1}$
$\displaystyle\leq(\|V_{0}-V_{\pi_{\bar{\rho}}}\|_{\infty}+\|V_{0}\|_{\infty}+1)^{2},\;c_{2}=4(\bar{\rho}+1)^{2}\eta(\gamma,\bar{c})^{2}(\|V_{\pi_{\bar{\rho}}}\|_{\infty}+1)^{2}.$

Now we apply Theorem 2.1 (2) (a). When $\alpha_{k}=\alpha$ for all $k\geq 0$,
where $\alpha$ is chosen such that

$\displaystyle\alpha(t_{\alpha}(\mathcal{M}_{S})+n)\leq\frac{\varphi_{2}}{\varphi_{3}A^{2}}=\frac{(1-\beta_{2})^{2}}{7296e(\bar{\rho}+1)^{2}\eta^{2}(\gamma,\bar{c})\log(|\mathcal{S}|)},$

we have for all $k\geq t_{\alpha}+n$:

$\displaystyle\mathbb{E}[\|V_{k}-V_{\pi_{\bar{\rho}}}\|_{\infty}^{2}]\leq\;$
$\displaystyle\varphi_{1}c_{1}(1-\varphi_{2}\alpha)^{k-K_{2}}+\frac{\varphi_{3}c_{2}}{\varphi_{2}}\alpha
t_{\alpha}(\mathcal{M}_{Y})$ $\displaystyle\leq\;$ $\displaystyle
3(\|V_{0}-V_{\pi_{\bar{\rho}}}\|_{\infty}+\|V_{0}\|_{\infty}+1)^{2}\left(1-\frac{1-\beta_{2}}{2}\alpha\right)^{k-K_{2}}$
$\displaystyle+\frac{3648e\log(|\mathcal{S}|)}{(1-\beta_{2})^{2}}(\bar{\rho}+1)^{2}\eta(\gamma,\bar{c})^{2}(\|V_{\pi_{\bar{\rho}}}\|_{\infty}+1)^{2}\alpha(t_{\alpha}(\mathcal{M}_{S})+n)$
$\displaystyle=\;$ $\displaystyle
c_{V,1}\left(1-\frac{1-\beta_{2}}{2}\alpha\right)^{k-K_{2}}+c_{V,2}\frac{\log(|\mathcal{S}|)}{(1-\beta_{2})^{2}}(\bar{\rho}+1)^{2}\eta(\gamma,\bar{c})^{2}\alpha(t_{\alpha}(\mathcal{M}_{S})+n),$

where
$c_{V,1}=3(\|V_{0}-V_{\pi_{\bar{\rho}}}\|_{\infty}+\|V_{0}\|_{\infty}+1)^{2}$
and $c_{V,2}=3648e(\|V_{\pi_{\bar{\rho}}}\|_{\infty}+1)^{2}$.

###  V-trace with Diminishing Stepsizes

We here only present using linear stepsize that achieves the optimal
convergence rate (Theorem 2.1 (2) (b) (iii)).

######  Theorem C.1.

Consider $\\{V_{k}\\}$ of Algorithm (10). Suppose Assumption 3.2 is satisfied
and $\alpha_{k}=\frac{\alpha}{k+h}$ with $\alpha=\frac{4}{1-\beta_{2}}$ and
properly chosen $h$. Then there exists $K_{2}^{\prime}>0$ such that the
following inequality holds for all $k\geq K_{2}^{\prime}$:

$\displaystyle\mathbb{E}[\|V_{k}-V_{\pi_{\bar{\rho}}}\|_{\infty}^{2}]\leq
c_{V,1}^{\prime}\frac{K_{2}^{\prime}+h}{k+h}+c_{V,2}^{\prime}\frac{\log(|\mathcal{S}|)}{(1-\beta_{2})^{3}}(\bar{\rho}+1)^{2}\eta(\gamma,\bar{c})^{2}\frac{t_{k}(\mathcal{M}_{S})+n}{k+h},$

where
$c_{V,1}^{\prime}=3\|V_{0}-V_{\pi_{\bar{\rho}}}\|_{\infty}+\|V_{0}\|_{\infty}+1)^{2}$
and $c_{V,2}^{\prime}=233472e^{2}(\|V_{\pi_{\bar{\rho}}}\|_{\infty}+1)^{2}$.

###### Proof of Theorem C.1.

The corresponding constants have been identified in the proof of Theorem 3.2.
Now apply Theorem 2.1 (2) (c). When $\alpha_{k}=\frac{\alpha}{k+h}$ with
$\alpha=\frac{4}{1-\beta_{2}}$ and properly chosen $h$, there exists
$K_{2}^{\prime}>0$ such that we have for all $k\geq K_{2}^{\prime}$:

$\displaystyle\mathbb{E}[\|V_{k}-V_{\pi_{\bar{\rho}}}\|_{\infty}^{2}]\leq\;$
$\displaystyle\varphi_{1}c_{1}\left(\frac{K_{2}^{\prime}+h}{k+h}\right)^{\varphi_{2}\alpha}+\frac{8e\alpha^{2}\varphi_{3}c_{2}}{\varphi_{2}\alpha-1}\frac{t_{k}(\mathcal{M}_{Y})}{k+h}$
$\displaystyle\leq\;$ $\displaystyle
3\|V_{0}-V_{\pi_{\bar{\rho}}}\|_{\infty}+\|V_{0}\|_{\infty}+1)^{2}\frac{K_{2}^{\prime}+h}{k+h}$
$\displaystyle+233472e^{2}\frac{\log(|\mathcal{S}|)}{(1-\beta_{2})^{3}}(\bar{\rho}+1)^{2}\eta(\gamma,\bar{c})^{2}(\|V_{\pi_{\bar{\rho}}}\|_{\infty}+1)^{2}\frac{t_{k}(\mathcal{M}_{S})+n}{k+h}$
$\displaystyle=\;$ $\displaystyle
c_{V,1}^{\prime}\frac{K_{2}^{\prime}+h}{k+h}+c_{V,2}^{\prime}\frac{\log(|\mathcal{S}|)}{(1-\beta_{2})^{3}}(\bar{\rho}+1)^{2}\eta(\gamma,\bar{c})^{2}\frac{t_{k}(\mathcal{M}_{S})+n}{k+h},$

where
$c_{V,1}^{\prime}=3\|V_{0}-V_{\pi_{\bar{\rho}}}\|_{\infty}+\|V_{0}\|_{\infty}+1)^{2}$
and $c_{V,2}^{\prime}=233472e^{2}(\|V_{\pi_{\bar{\rho}}}\|_{\infty}+1)^{2}$. ∎

##  Appendix D $n$-step TD

###  Proof of Proposition 3.3

  1. (1)

    1. (a)

For any $V_{1},V_{2}\in\mathbb{R}^{|\mathcal{S}|}$ and $y\in\mathcal{Y}$, we
have

$\displaystyle\|F(V_{1},y)-F(V_{2},y)\|_{2}$ $\displaystyle=\;$
$\displaystyle\left(\sum_{s\in\mathcal{S}}\left[\mathbbm{1}_{\\{s_{0}=s\\}}\left(\gamma^{n}(V_{1}(s_{n})-V_{2}(s_{n}))-(V_{1}(s_{0})-V_{2}(s_{0}))\right)+V_{1}(s)-V_{2}(s)\right]^{2}\right)^{1/2}$
$\displaystyle\leq\;$
$\displaystyle\left(\sum_{s\in\mathcal{S}}[\mathbbm{1}_{\\{s_{0}=s\\}}(\gamma^{n}+1)\|V_{1}-V_{2}\|_{2}]^{2}\right)^{1/2}+\|V_{1}-V_{2}\|_{2}$
(Triangle inequality) $\displaystyle\leq\;$ $\displaystyle
3\|V_{1}-V_{2}\|_{2}.$

    2. (b)

For any $y\in\mathcal{Y}$, we have

$\displaystyle\|F(\bm{0},y)\|_{2}^{2}=\sum_{s\in\mathcal{S}}\left(\mathbbm{1}_{\\{s_{0}=s\\}}\sum_{i=0}^{n-1}\gamma^{i}\mathcal{R}(s_{i},a_{i})\right)^{2}\leq\sum_{s\in\mathcal{S}}\mathbbm{1}_{\\{s_{0}=s\\}}\left(\sum_{i=0}^{n-1}\gamma^{i}\right)^{2}\leq\frac{1}{(1-\gamma)^{2}}.$

It follows that $\|F(\bm{0},y)\|_{2}\leq\frac{1}{1-\gamma}$.

  2. (2)

The proof is identical to that of Proposition 3.1 (2).

  3. (3)

    1. (a)

Since $n$-step TD is a special case of V-trace, we can directly apply
Proposition 3.2 (3) (a) here. Observe that when $\pi=\pi_{b}$ and
$\bar{c}=\bar{\rho}=1$, we have $C=D=I$ and
$P_{\pi_{\bar{c}}}=P_{\pi_{\bar{\rho}}}=P_{\pi}$. Hence we have

$\displaystyle\bar{F}(V)=\left[I-\mathcal{K}\sum_{i=0}^{n-1}(\gamma
P_{\pi})^{i}(I-\gamma P_{\pi})\right]V+\mathcal{K}\sum_{i=0}^{n-1}(\gamma
P_{\pi})^{i}R_{\pi}.$

    2. (b)

For any $V_{1},V_{2}\in\mathbb{R}^{|\mathcal{S}|}$ and $p\geq 1$, we have

$\displaystyle\|\bar{F}(V_{1})-\bar{F}(V_{2})\|_{p}$
$\displaystyle=\left\|\left[I-\mathcal{K}\sum_{i=0}^{n-1}(\gamma
P_{\pi})^{i}(I-\gamma P_{\pi})\right](V_{1}-V_{2})\right\|_{p}$
$\displaystyle\leq\left\|I-\mathcal{K}\sum_{i=0}^{n-1}(\gamma
P_{\pi})^{i}(I-\gamma P_{\pi})\right\|_{p}\|V_{1}-V_{2}\|_{p}.$

For simplicity of notation, we denote $G=I-\mathcal{K}\sum_{i=0}^{n-1}(\gamma
P_{\pi})^{i}(I-\gamma P_{\pi})$. Since $G$ has non-negative entries
(established in the proof of Proposition 3.2 (3) (b)), we have

$\displaystyle\|G\|_{\infty}=\|G\bm{1}\|_{\infty}=\left\|\bm{1}-\kappa\sum_{i=0}^{n-1}\gamma^{i}(1-\gamma)\right\|_{\infty}=1-\mathcal{K}_{\min}(1-\gamma^{n}).$

Moreover, using the fact that $\kappa$ is the stationary distribution of
$P_{\pi}$ (i.e., $\kappa^{\top}P_{\pi}=\kappa^{\top}$), we have

$\displaystyle\|G\|_{1}=\|\bm{1}^{\top}G\|_{\infty}=\left\|\bm{1}^{\top}-\kappa^{\top}\sum_{i=0}^{n-1}\gamma^{i}(1-\gamma)\right\|_{\infty}=1-\mathcal{K}_{\min}(1-\gamma^{n}).$

To proceed, we need the following lemma.

######  Lemma D.1.

Let $G\in\mathbb{R}^{d\times d}$ be a matrix with non-negative entries. Then
we have for all $p\in[1,\infty]$:

$\displaystyle\|G\|_{p}\leq\|G\|_{1}^{1/p}\|G\|_{\infty}^{1-1/p}.$

###### Proof of Lemma D.1.

The result clearly holds when $p=1$ or $p=\infty$. Now consider
$p\in(1,\infty)$. Using the definition of induced matrix norm, we have for any
$x\neq 0$:

$\displaystyle\|Gx\|_{p}^{p}$
$\displaystyle=\sum_{i=1}^{d}\left(\sum_{j=1}^{d}G_{ij}x_{j}\right)^{p}$
$\displaystyle=\sum_{i=1}^{d}[G\bm{1}]_{i}^{p}\left(\sum_{j=1}^{d}\frac{G_{ij}}{[G\bm{1}]_{i}}x_{j}\right)^{p}$
$\displaystyle\leq\sum_{i=1}^{d}[G\bm{1}]_{i}^{p-1}\sum_{j=1}^{d}G_{ij}x_{j}^{p}$
(Jensen’s inequality)
$\displaystyle\leq\|G\|_{\infty}^{p-1}\sum_{j=1}^{d}x_{j}^{p}\sum_{i=1}^{d}G_{ij}$
$\displaystyle=\|G\|_{\infty}^{p-1}\sum_{j=1}^{d}x_{j}^{p}[\bm{1}^{\top}G]_{j}$
$\displaystyle\leq\|G\|_{\infty}^{p-1}\|G\|_{1}\|x\|^{p}_{p}.$

It follows that $\|G\|_{p}\leq\|G\|_{1}^{1/p}\|G\|_{\infty}^{1-1/p}$. ∎

Using Lemma D.1 and we have

$\displaystyle\|G\|_{p}\leq\|G\|_{1}^{1/p}\|G\|_{\infty}^{1-1/p}\leq
1-\mathcal{K}_{\min}(1-\gamma^{n})=\beta_{3}.$

Therefore, we have
$\|\bar{F}(V_{1})-\bar{F}(V_{2})\|_{2}\leq\beta_{3}\|V_{1}-V_{2}\|_{2}$. Hence
the operator $\bar{F}(\cdot)$ is a contraction mapping with respect to
$\|\cdot\|_{2}$, with contraction factor $\beta_{3}$.

    3. (c)

The proof is identical to that of Proposition 3.2 (3) (c).

###  Proof of Theorem 3.3

We will apply Theorem and Lemma 2.1 (1) to the $n$-step TD algorithm. We begin
by identifying the constants:

$\displaystyle A$
$\displaystyle=A_{1}+A_{2}+1=4,\;B=B_{1}+B_{2}=\frac{1}{1-\gamma},\;\varphi_{1}\leq
1,\;\varphi_{2}\geq 1-\beta_{3},\;\varphi_{3}\leq 228$ $\displaystyle c_{1}$
$\displaystyle\leq(\|V_{0}-V_{\pi}\|_{2}+\|V_{0}\|_{2}+4)^{2},\;c_{2}=\frac{1}{(1-\gamma)^{2}}(4(1-\gamma)\|V_{\pi}\|_{2}+1)^{2}.$

Now apply Theorem 2.1 (2) (a). When $\alpha_{k}=\alpha$ for all $k\geq 0$,
where $\alpha$ is chosen such that

$\displaystyle\alpha(t_{\alpha}(\mathcal{M}_{S})+n)\leq\frac{\varphi_{2}}{\varphi_{3}A^{2}}=\frac{1-\beta_{3}}{3648},$

we have for all $k\geq t_{\alpha}(\mathcal{M}_{S})+n$:

$\displaystyle\mathbb{E}[\|V_{k}-V_{\pi}\|_{2}^{2}]\leq\;$
$\displaystyle\varphi_{1}c_{1}(1-\varphi_{2}\alpha)^{k-(\alpha(t_{\alpha}(\mathcal{M}_{S})+n))}+\frac{\varphi_{3}c_{2}}{\varphi_{2}}\alpha
t_{\alpha}(\mathcal{M}_{Y})$ $\displaystyle\leq\;$
$\displaystyle(\|V_{0}-V_{\pi}\|_{2}+\|V_{0}\|_{2}+4)^{2}(1-(1-\beta_{3})\alpha)^{k-(\alpha(t_{\alpha}(\mathcal{M}_{S})+n))}$
$\displaystyle+\frac{228}{1-\beta_{3}}\frac{1}{(1-\gamma)^{2}}(4(1-\gamma)\|V_{\pi}\|_{2}+1)^{2}\alpha(t_{\alpha}(\mathcal{M}_{S})+n)$
$\displaystyle=\;$
$\displaystyle\hat{c}_{1}(1-(1-\beta_{3})\alpha)^{k-(\alpha(t_{\alpha}(\mathcal{M}_{S})+n))}+\hat{c}_{2}\frac{\alpha(t_{\alpha}(\mathcal{M}_{S})+n)}{(1-\beta_{3})(1-\gamma)^{2}},$

where $\hat{c}_{1}=(\|V_{0}-V_{\pi}\|_{2}+\|V_{0}\|_{2}+4)^{2}$ and
$\hat{c}_{2}=228(4(1-\gamma)\|V_{\pi}\|_{2}+1)^{2}$.

###  $n$-Step TD with Diminishing Stepsizes

For $n$-step TD with diminishing stepsize, we here only present the result for
using linear diminishing stepsize that achieves the optimal convergence rate
(Theorem 2.1 (2) (b) (iii)).

######  Theorem D.1.

Consider $\\{V_{k}\\}$ of Algorithm (12). Suppose that Assumption 3.3 is
satisfied and $\alpha_{k}=\frac{\alpha}{k+h}$ with
$\alpha=\frac{2}{1-\beta_{3}}$ and properly chosen $h$. Then there exists
$K_{3}^{\prime}>0$ such that the following inequality holds for all $k\geq
K_{3}^{\prime}$:

$\displaystyle\mathbb{E}[\|V_{k}-V_{\pi}\|_{c}^{2}]\leq\hat{c}_{1}^{\prime}\frac{K_{3}^{\prime}+h}{k+h}+\hat{c}_{2}^{\prime}\frac{t_{k}(\mathcal{M}_{S})+n}{(1-\beta_{3})^{2}(1-\gamma)^{2}(k+h)},$

where $\hat{c}_{1}^{\prime}=(\|V_{0}-V_{\pi}\|_{2}+\|V_{0}\|_{2}+4)^{2}$ and
$\hat{c}_{2}^{\prime}=7296e(4(1-\gamma)\|V_{\pi}\|_{2}+1)^{2}$.

###### Proof of Theorem D.1.

The constants are already identified in the proof of Theorem 3.3. Apply
Theorem 2.1) (2) (b) (iii), when $\alpha_{k}=\frac{\alpha}{k+h}$ with
$\alpha=\frac{2}{1-\beta_{3}}$ and properly chosen $h$, there exists
$K_{3}^{\prime}>0$ such that we have for all $k\geq K_{3}^{\prime}$:

$\displaystyle\mathbb{E}[\|V_{k}-V_{\pi}\|_{c}^{2}]$ $\displaystyle\leq\;$
$\displaystyle\varphi_{1}c_{1}\left(\frac{K_{3}^{\prime}+h}{k+h}\right)^{\varphi_{2}\alpha}+\frac{8e\alpha^{2}\varphi_{3}c_{2}}{\varphi_{2}\alpha-1}\frac{t_{k}(\mathcal{M}_{Y})}{k+h}$
$\displaystyle\leq\;$
$\displaystyle(\|V_{0}-V_{\pi}\|_{2}+\|V_{0}\|_{2}+4)^{2}\frac{K_{3}^{\prime}+h}{k+h}+\frac{7296e}{(1-\beta_{3})^{2}}\frac{1}{(1-\gamma)^{2}}(4(1-\gamma)\|V_{\pi}\|_{2}+1)^{2}\frac{t_{k}(\mathcal{M}_{Y})}{k+h}$
$\displaystyle=\;$
$\displaystyle\hat{c}_{1}^{\prime}\frac{K_{3}^{\prime}+h}{k+h}+\hat{c}_{2}^{\prime}\frac{t_{k}(\mathcal{M}_{S})+n}{(1-\beta_{3})^{2}(1-\gamma)^{2}(k+h)},$

where $\hat{c}_{1}^{\prime}=(\|V_{0}-V_{\pi}\|_{2}+\|V_{0}\|_{2}+4)^{2}$ and
$\hat{c}_{2}^{\prime}=7296e(4(1-\gamma)\|V_{\pi}\|_{2}+1)^{2}$. ∎

##  Appendix E TD$(\lambda)$

The following lemma is useful when proving Lemma 3.1 and Proposition 3.4.

######  Lemma E.1.

Let $\mathcal{I}$ be a finite set. For any $k\geq 0$, define two sequences
$\\{i_{t}\\}_{0\leq t\leq k}$ and $\\{a_{t}\\}_{0\leq t\leq k}$ be such that
$i_{t}\in\mathcal{I}$ and $a_{t}\geq 0$ for all $t=0,1,...,k$. Let
$x\in\mathbb{R}^{|\mathcal{I}|}$ be defined by
$x_{i}=\sum_{t=0}^{k}a_{t}\mathbbm{1}_{\\{i_{t}=i\\}}$ for all
$i\in\mathcal{I}$. Then we have

$\displaystyle\|x\|_{2}\leq\sum_{t=0}^{k}a_{t}.$

###### Proof of Lemma E.1.

Using the definition of $\|\cdot\|_{2}$, we have

$\displaystyle\|x\|_{2}^{2}$
$\displaystyle=\sum_{i\in\mathcal{I}}\left(\sum_{t=0}^{k}a_{t}\mathbbm{1}_{\\{i_{t}=i\\}}\right)^{2}$
$\displaystyle=\sum_{i\in\mathcal{I}}\sum_{t=0}^{k}\sum_{\ell=0}^{k}a_{t}a_{\ell}\mathbbm{1}_{\\{i_{t}=i,i_{\ell}=i\\}}$
$\displaystyle=\sum_{t=0}^{k}\sum_{\ell=0}^{k}a_{t}a_{\ell}\sum_{i\in\mathcal{I}}\mathbbm{1}_{\\{i_{t}=i,i_{\ell}=i\\}}$
$\displaystyle\leq\sum_{t=0}^{k}\sum_{\ell=0}^{k}a_{t}a_{\ell}$
$\displaystyle=\left(\sum_{t=0}^{k}a_{t}\right)^{2}.$

The result follows by taking square root on both sides of the previous
inequality. ∎

###  Proof of Lemma 3.1

For any $V\in\mathbb{R}^{|\mathcal{S}|}$ and
$(s_{0},...,s_{k},a_{k},s_{k+1})$, we have by definition of the operators
$F_{k}^{\tau}(\cdot,\cdot)$ and $F_{k}(\cdot,\cdot)$ that

$\displaystyle\|F_{k}^{\tau}(V,s_{k-\tau},...,s_{k},a_{k},s_{k+1})-F_{k}(V,s_{0},...,s_{k},a_{k},s_{k+1})\|_{2}^{2}$
$\displaystyle=\;$
$\displaystyle\sum_{s\in\mathcal{S}}\left[\left(\mathcal{R}(s_{k},a_{k})+\gamma
V(s_{k+1})-V(s_{k})\right)\sum_{i=0}^{k-\tau-1}(\gamma\lambda)^{k-i}\mathbbm{1}_{\\{s_{i}=s\\}}\right]^{2}$
$\displaystyle\leq\;$
$\displaystyle(1+2\|V\|_{2})^{2}\sum_{s\in\mathcal{S}}\left[\sum_{i=0}^{k-\tau-1}(\gamma\lambda)^{k-i}\mathbbm{1}_{\\{s_{i}=s\\}}\right]^{2}$
$\displaystyle=\;$
$\displaystyle\frac{(\gamma\lambda)^{2(\tau+1)}}{(1-\gamma\lambda)^{2}}(1+2\|V\|_{2})^{2}.$
(Lemma E.1)

The result follows by taking the square root on both sides of the previous
inequality.

###  Proof of Proposition 3.4

  1. (1)

For any $V_{1},V_{2}\in\mathbb{R}^{|\mathcal{S}|}$ and
$y\in\mathcal{Y}_{\tau}$, we have by Triangle inequality that

$\displaystyle\|F_{k}^{\tau}(V_{1},y)-F_{k}^{\tau}(V_{2},y)\|_{2}$
$\displaystyle\leq\;$
$\displaystyle\|V_{1}-V_{2}\|_{2}+\left(\sum_{s\in\mathcal{S}}\left[\left(\gamma(V_{1}(s_{k+1})-V_{2}(s_{k+1}))-(V_{1}(s_{k})-V_{2}(s_{k}))\right)\sum_{i=k-\tau}^{k}(\gamma\lambda)^{k-i}\mathbbm{1}_{\\{s_{i}=s\\}}\right]^{2}\right)^{1/2}$
$\displaystyle\leq\;$
$\displaystyle\|V_{1}-V_{2}\|_{2}+2\|V_{1}-V_{2}\|_{2}\left(\sum_{s\in\mathcal{S}}\left[\sum_{i=k-\tau}^{k}(\gamma\lambda)^{k-i}\mathbbm{1}_{\\{s_{i}=s\\}}\right]^{2}\right)^{1/2}$
$\displaystyle\leq\;$
$\displaystyle\|V_{1}-V_{2}\|_{2}+\frac{2}{1-\gamma\lambda}\|V_{1}-V_{2}\|_{2}$
(Lemma E.1) $\displaystyle\leq\;$
$\displaystyle\frac{3}{1-\gamma\lambda}\|V_{1}-V_{2}\|_{2}.$

Similarly, for any $y\in\mathcal{Y}_{\tau}$, we have

$\displaystyle\|F_{k}^{\tau}(\bm{0},y)\|_{2}^{2}$
$\displaystyle=\sum_{s\in\mathcal{S}}\left[\mathcal{R}(s_{k},a_{k})\sum_{i=k-\tau}^{k}(\gamma\lambda)^{k-i}\mathbbm{1}_{\\{s_{i}=s\\}}\right]^{2}$
$\displaystyle\leq\sum_{s\in\mathcal{S}}\left[\sum_{i=k-\tau}^{k}(\gamma\lambda)^{k-i}\mathbbm{1}_{\\{s_{i}=s\\}}\right]^{2}$
($\mathcal{R}(s,a)\in[0,1]$ for all $(s,a)$)
$\displaystyle\leq\frac{1}{(1-\gamma\lambda)^{2}}.$ (Lemma E.1)

It follows that $\|F_{k}^{\tau}(\bm{0},y)\|_{2}\leq\frac{1}{1-\gamma\lambda}$.

  2. (2)

The proof is identical to that of Propositon 3.1 (2).

  3. (3)

    1. (a)

For any $V\in\mathbb{R}^{|\mathcal{S}|}$ and $s\in\mathcal{S}$, we have

$\displaystyle\mathbb{E}_{Y\sim\mu}\left[[F_{k}^{\tau}(V,Y)](s)\right]$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{Y\sim\mu}\left[\left(\mathcal{R}(S_{k},A_{k})+\gamma
V(S_{k+1})-V(S_{k})\right)\sum_{i=k-\tau}^{k}(\gamma\lambda)^{k-i}\mathbbm{1}_{\\{S_{i}=s\\}}\right]+V(s)$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{Y\sim\mu}\left[\sum_{i=k-\tau}^{k}(\gamma\lambda)^{k-i}\mathbbm{1}_{\\{S_{i}=s\\}}\mathbb{E}\left[\left(\mathcal{R}(S_{k},A_{k})+\gamma
V(S_{k+1})-V(S_{k})\right)\;\middle|\;S_{k},S_{k-1},...,S_{0}\right]\right]+V(s)$
$\displaystyle=\;$
$\displaystyle\mathbb{E}_{Y\sim\mu}\left[\sum_{i=k-\tau}^{k}(\gamma\lambda)^{k-i}\mathbbm{1}_{\\{S_{i}=s\\}}(R_{\pi}(S_{k})+\gamma[P_{\pi}V](S_{k})-V(S_{k}))\right]+V(s)$
$\displaystyle=\;$
$\displaystyle\sum_{i=k-\tau}^{k}(\gamma\lambda)^{k-i}\sum_{s_{0}\in\mathcal{S}}\kappa(s_{0})P_{\pi}^{i}(s_{0},s)\sum_{s^{\prime}\in\mathcal{S}}P_{\pi}^{k-i}(s,s^{\prime})(R_{\pi}(s^{\prime})+\gamma[P_{\pi}V](s^{\prime})-V(s^{\prime}))+V(s)$
$\displaystyle=\;$
$\displaystyle\kappa(s)\sum_{i=k-\tau}^{k}(\gamma\lambda)^{k-i}\sum_{s^{\prime}\in\mathcal{S}}P_{\pi}^{k-i}(s,s^{\prime})(R_{\pi}(s^{\prime})+\gamma[P_{\pi}V](s^{\prime})-V(s^{\prime}))+V(s)$
$\displaystyle=\;$
$\displaystyle\kappa(s)\sum_{i=k-\tau}^{k}(\gamma\lambda)^{k-i}[P_{\pi}^{k-i}(R_{\pi}+\gamma
P_{\pi}V-V)](s)+V(s).$

It follows that

$\displaystyle\bar{F}_{k}^{\tau}(V)$
$\displaystyle=\mathcal{K}\sum_{i=k-\tau}^{k}(\gamma\lambda
P_{\pi})^{k-i}(R_{\pi}+\gamma P_{\pi}V-V)+V$
$\displaystyle=\mathcal{K}\sum_{i=0}^{\tau}(\gamma\lambda
P_{\pi})^{i}(R_{\pi}+\gamma P_{\pi}V-V)+V$
$\displaystyle=\left[I-\mathcal{K}\sum_{i=0}^{\tau}(\gamma\lambda
P_{\pi})^{i}(I-\gamma
P_{\pi})\right]V+\mathcal{K}\sum_{i=0}^{\tau}(\gamma\lambda
P_{\pi})^{i}R_{\pi}.$

    2. (b)

For any $V_{1},V_{2}\in\mathbb{R}^{|\mathcal{S}|}$ and $p\in[1,\infty]$, we
have

$\displaystyle\|\bar{F}_{k}^{\tau}(V_{1})-\bar{F}_{k}^{\tau}(V_{2})\|_{p}$
$\displaystyle=\left\|\left[I-\mathcal{K}\sum_{i=0}^{\tau}(\gamma\lambda
P_{\pi})^{i}(I-\gamma P_{\pi})\right](V_{1}-V_{2})\right\|_{p}$
$\displaystyle\leq\left\|I-\mathcal{K}\sum_{i=0}^{\tau}(\gamma\lambda
P_{\pi})^{i}(I-\gamma P_{\pi})\right\|_{p}\|V_{1}-V_{2}\|_{p}.$

Denote $G=I-\mathcal{K}\sum_{i=0}^{\tau}(\gamma\lambda P_{\pi})^{i}(I-\gamma
P_{\pi})$. It remains to provide an upper bound on $\|G\|_{p}$. Since

$\displaystyle G$ $\displaystyle=I-\mathcal{K}\sum_{i=0}^{\tau}(\gamma\lambda
P_{\pi})^{i}+\mathcal{K}\sum_{i=0}^{\tau}(\gamma\lambda P_{\pi})^{i}\gamma
P_{\pi}$
$\displaystyle=I-\mathcal{K}-\mathcal{K}\sum_{i=1}^{\tau}(\gamma\lambda
P_{\pi})^{i}+\mathcal{K}\sum_{i=0}^{\tau}(\gamma\lambda P_{\pi})^{i}\gamma
P_{\pi}$
$\displaystyle=I-\mathcal{K}-\mathcal{K}\sum_{i=0}^{\tau-1}(\gamma\lambda
P_{\pi})^{i+1}+\mathcal{K}\sum_{i=0}^{\tau}(\gamma\lambda P_{\pi})^{i}\gamma
P_{\pi}$
$\displaystyle=I-\mathcal{K}+\mathcal{K}\sum_{i=0}^{\tau-1}(\gamma\lambda
P_{\pi})^{i}\gamma P_{\pi}(1-\lambda)+\mathcal{K}(\gamma\lambda
P_{\pi})^{\tau}\gamma P_{\pi},$

the matrix $G_{\lambda,\tau}$ has non-negative entries. Therefore, we have

$\displaystyle\|G_{\lambda,\tau}\|_{\infty}=\|G_{\lambda,\tau}\bm{1}\|_{\infty}=\left\|\bm{1}-\kappa\frac{(1-\gamma)(1-(\gamma\lambda)^{\tau+1})}{1-\gamma\lambda}\right\|_{\infty}=1-\mathcal{K}_{\min}\frac{(1-\gamma)(1-(\gamma\lambda)^{\tau+1})}{1-\gamma\lambda}$

and

$\displaystyle\|G_{\lambda,\tau}\|_{1}=\|\bm{1}^{\top}G_{\lambda,\tau}\|_{\infty}=\left\|\bm{1}^{\top}-\kappa^{\top}\frac{(1-\gamma)(1-(\gamma\lambda)^{\tau+1})}{1-\gamma\lambda}\right\|_{\infty}=1-\mathcal{K}_{\min}\frac{(1-\gamma)(1-(\gamma\lambda)^{\tau+1})}{1-\gamma\lambda}.$

It then follows from Lemma D.1 that

$\displaystyle\|G_{\lambda,\tau}\|_{p}\leq\|G_{\lambda,\tau}\|_{1}^{1/p}\|G_{\lambda,\tau}\|_{\infty}^{1-1/p}\leq
1-\mathcal{K}_{\min}\frac{(1-\gamma)(1-(\gamma\lambda)^{\tau+1})}{1-\gamma\lambda}.$

Hence the operator $F_{k}^{\tau}(\cdot,\cdot)$ is a contraction with respect
to $\|\cdot\|_{p}$, with a common contraction factor
$\beta_{4}=1-\mathcal{K}_{\min}\frac{(1-\gamma)(1-(\gamma\lambda)^{\tau+1})}{1-\gamma\lambda}$.

    3. (c)

It is enough to show that $V_{\pi}$ is a fixed-point of
$\bar{F}_{k}^{\tau}(\cdot)$, the uniqueness follows from
$\bar{F}_{k}^{\tau}(\cdot)$ being a contraction. Using the Bellman equation
$R_{\pi}+\gamma P_{\pi}V_{\pi}-V_{\pi}=0$, we have

$\displaystyle\bar{F}_{k}^{\tau}(V_{\pi})=\mathcal{K}\sum_{i=0}^{\tau}(\gamma\lambda
P_{\pi})^{i}(R_{\pi}+\gamma P_{\pi}V_{\pi}-V_{\pi})+V_{\pi}=V_{\pi}.$

###  Proof of Theorem 3.4

We will exploit the $\|\cdot\|_{2}$-contraction property of the operator
$\bar{F}_{k}^{\tau}(\cdot)$ provided in Proposition 3.4. Let
$M(x)=\|x\|_{2}^{2}$ be our Lyapunov function. Using the update equation (15),
and we have for all $k\geq 0$:

$\displaystyle\|V_{k+1}-V_{\pi}\|_{2}^{2}$ $\displaystyle=\;$
$\displaystyle\|V_{k}-V_{\pi}\|_{2}^{2}+\underbrace{2\alpha(V_{k}-V_{\pi})^{\top}\left(\bar{F}_{k}^{\tau}(V_{k})-V_{k}\right)}_{\leavevmode\hbox
to7.23pt{\vbox to7.23pt{\pgfpicture\makeatletter\hbox{\hskip
3.61601pt\lower-3.61601pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.41602pt}{0.0pt}\pgfsys@curveto{3.41602pt}{1.88663pt}{1.88663pt}{3.41602pt}{0.0pt}{3.41602pt}\pgfsys@curveto{-1.88663pt}{3.41602pt}{-3.41602pt}{1.88663pt}{-3.41602pt}{0.0pt}\pgfsys@curveto{-3.41602pt}{-1.88663pt}{-1.88663pt}{-3.41602pt}{0.0pt}{-3.41602pt}\pgfsys@curveto{1.88663pt}{-3.41602pt}{3.41602pt}{-1.88663pt}{3.41602pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}+\underbrace{2\alpha(V_{k}-V_{\pi})^{\top}\left(F_{k}^{\tau}(V_{k},Y_{k}^{\tau})-\bar{F}_{k}^{\tau}(V_{k})\right)}_{\leavevmode\hbox
to7.23pt{\vbox to7.23pt{\pgfpicture\makeatletter\hbox{\hskip
3.61601pt\lower-3.61601pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.41602pt}{0.0pt}\pgfsys@curveto{3.41602pt}{1.88663pt}{1.88663pt}{3.41602pt}{0.0pt}{3.41602pt}\pgfsys@curveto{-1.88663pt}{3.41602pt}{-3.41602pt}{1.88663pt}{-3.41602pt}{0.0pt}\pgfsys@curveto{-3.41602pt}{-1.88663pt}{-1.88663pt}{-3.41602pt}{0.0pt}{-3.41602pt}\pgfsys@curveto{1.88663pt}{-3.41602pt}{3.41602pt}{-1.88663pt}{3.41602pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$
$\displaystyle+\underbrace{\alpha^{2}\|F_{k}^{\tau}(V_{k},Y_{k}^{\tau})-V_{k}\|_{2}^{2}}_{\leavevmode\hbox
to7.23pt{\vbox to7.23pt{\pgfpicture\makeatletter\hbox{\hskip
3.61601pt\lower-3.61601pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.41602pt}{0.0pt}\pgfsys@curveto{3.41602pt}{1.88663pt}{1.88663pt}{3.41602pt}{0.0pt}{3.41602pt}\pgfsys@curveto{-1.88663pt}{3.41602pt}{-3.41602pt}{1.88663pt}{-3.41602pt}{0.0pt}\pgfsys@curveto{-3.41602pt}{-1.88663pt}{-1.88663pt}{-3.41602pt}{0.0pt}{-3.41602pt}\pgfsys@curveto{1.88663pt}{-3.41602pt}{3.41602pt}{-1.88663pt}{3.41602pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}+\underbrace{\alpha^{2}\|F_{k}(V_{k},Y_{k})-F_{k}^{\tau}(V_{k},Y_{k}^{\tau})\|_{2}^{2}}_{\leavevmode\hbox
to7.23pt{\vbox to7.23pt{\pgfpicture\makeatletter\hbox{\hskip
3.61601pt\lower-3.61601pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.41602pt}{0.0pt}\pgfsys@curveto{3.41602pt}{1.88663pt}{1.88663pt}{3.41602pt}{0.0pt}{3.41602pt}\pgfsys@curveto{-1.88663pt}{3.41602pt}{-3.41602pt}{1.88663pt}{-3.41602pt}{0.0pt}\pgfsys@curveto{-3.41602pt}{-1.88663pt}{-1.88663pt}{-3.41602pt}{0.0pt}{-3.41602pt}\pgfsys@curveto{1.88663pt}{-3.41602pt}{3.41602pt}{-1.88663pt}{3.41602pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}$
$\displaystyle+\underbrace{2\alpha(V_{k}-V_{\pi})^{\top}\left(F_{k}(V_{k},Y_{k})-F_{k}^{\tau}(V_{k},Y_{k}^{\tau})\right)}_{\leavevmode\hbox
to7.23pt{\vbox to7.23pt{\pgfpicture\makeatletter\hbox{\hskip
3.61601pt\lower-3.61601pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.41602pt}{0.0pt}\pgfsys@curveto{3.41602pt}{1.88663pt}{1.88663pt}{3.41602pt}{0.0pt}{3.41602pt}\pgfsys@curveto{-1.88663pt}{3.41602pt}{-3.41602pt}{1.88663pt}{-3.41602pt}{0.0pt}\pgfsys@curveto{-3.41602pt}{-1.88663pt}{-1.88663pt}{-3.41602pt}{0.0pt}{-3.41602pt}\pgfsys@curveto{1.88663pt}{-3.41602pt}{3.41602pt}{-1.88663pt}{3.41602pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{5}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}+\underbrace{2\alpha\left(F_{k}^{\tau}(V_{k},Y_{k}^{\tau})-V_{k}\right)^{\top}\left(F_{k}(V_{k},Y_{k})-F_{k}^{\tau}(V_{k},Y_{k}^{\tau})\right)}_{\leavevmode\hbox
to7.23pt{\vbox to7.23pt{\pgfpicture\makeatletter\hbox{\hskip
3.61601pt\lower-3.61601pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{3.41602pt}{0.0pt}\pgfsys@curveto{3.41602pt}{1.88663pt}{1.88663pt}{3.41602pt}{0.0pt}{3.41602pt}\pgfsys@curveto{-1.88663pt}{3.41602pt}{-3.41602pt}{1.88663pt}{-3.41602pt}{0.0pt}\pgfsys@curveto{-3.41602pt}{-1.88663pt}{-1.88663pt}{-3.41602pt}{0.0pt}{-3.41602pt}\pgfsys@curveto{1.88663pt}{-3.41602pt}{3.41602pt}{-1.88663pt}{3.41602pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.75pt}{-2.25555pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{6}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>(32)

The terms 1, 2, and 3 correspond to the terms $T_{1}$, $T_{3}$, and $T_{4}$ in
Eq. (A.1.1), and hence can be controlled in the exact same way as provided in
Lemmas A.1, A.4, and A.5. The upper bounds of 1, 2, and 3 are summarized in
the following lemma, whose proof is omitted.

######  Lemma E.2.

The following inequalities hold:

  1. (1)

$\leavevmode\hbox to9.67pt{\vbox to9.67pt{\pgfpicture\makeatletter\hbox{\hskip
4.83623pt\lower-4.83623pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.63623pt}{0.0pt}\pgfsys@curveto{4.63623pt}{2.56055pt}{2.56055pt}{4.63623pt}{0.0pt}{4.63623pt}\pgfsys@curveto{-2.56055pt}{4.63623pt}{-4.63623pt}{2.56055pt}{-4.63623pt}{0.0pt}\pgfsys@curveto{-4.63623pt}{-2.56055pt}{-2.56055pt}{-4.63623pt}{0.0pt}{-4.63623pt}\pgfsys@curveto{2.56055pt}{-4.63623pt}{4.63623pt}{-2.56055pt}{4.63623pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leq-2\alpha(1-\beta_{4})\|V_{k}-V_{\pi}\|_{2}^{2}$
for any $k\geq\tau$.

  2. (2)

$\mathbb{E}[\leavevmode\hbox to9.67pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 4.83623pt\lower-4.83623pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.63623pt}{0.0pt}\pgfsys@curveto{4.63623pt}{2.56055pt}{2.56055pt}{4.63623pt}{0.0pt}{4.63623pt}\pgfsys@curveto{-2.56055pt}{4.63623pt}{-4.63623pt}{2.56055pt}{-4.63623pt}{0.0pt}\pgfsys@curveto{-4.63623pt}{-2.56055pt}{-2.56055pt}{-4.63623pt}{0.0pt}{-4.63623pt}\pgfsys@curveto{2.56055pt}{-4.63623pt}{4.63623pt}{-2.56055pt}{4.63623pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}]\leq\frac{662\alpha^{2}(t_{\alpha}(\mathcal{M}_{S})+\tau)}{(1-\gamma\lambda)^{2}}\|V_{k}-V_{\pi}\|_{2}^{2}+\frac{102\alpha^{2}(t_{\alpha}(\mathcal{M}_{S})+\tau)}{(1-\gamma\lambda)^{2}}(4\|V_{\pi}\|_{2}+1)^{2}$
for all $k\geq 2\tau+t_{\alpha}(\mathcal{M}_{S})$.

  3. (3)

$\leavevmode\hbox to9.67pt{\vbox to9.67pt{\pgfpicture\makeatletter\hbox{\hskip
4.83623pt\lower-4.83623pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.63623pt}{0.0pt}\pgfsys@curveto{4.63623pt}{2.56055pt}{2.56055pt}{4.63623pt}{0.0pt}{4.63623pt}\pgfsys@curveto{-2.56055pt}{4.63623pt}{-4.63623pt}{2.56055pt}{-4.63623pt}{0.0pt}\pgfsys@curveto{-4.63623pt}{-2.56055pt}{-2.56055pt}{-4.63623pt}{0.0pt}{-4.63623pt}\pgfsys@curveto{2.56055pt}{-4.63623pt}{4.63623pt}{-2.56055pt}{4.63623pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leq\frac{32\alpha^{2}}{(1-\gamma\lambda)^{2}}\|V_{k}-V_{\pi}\|_{2}^{2}+\frac{2\alpha^{2}}{(1-\gamma\lambda)^{2}}(4\|V_{\pi}\|_{2}+1)^{2}$
for all $k\geq\tau$.

As for the terms 3, 4, and 5, we can easily use Lemma E.3 along with the
Cauchy-Schwarz inequality to bound them, which gives the following result.

######  Lemma E.3.

The following inequalities hold:

  1. (1)

$\leavevmode\hbox to9.67pt{\vbox to9.67pt{\pgfpicture\makeatletter\hbox{\hskip
4.83623pt\lower-4.83623pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.63623pt}{0.0pt}\pgfsys@curveto{4.63623pt}{2.56055pt}{2.56055pt}{4.63623pt}{0.0pt}{4.63623pt}\pgfsys@curveto{-2.56055pt}{4.63623pt}{-4.63623pt}{2.56055pt}{-4.63623pt}{0.0pt}\pgfsys@curveto{-4.63623pt}{-2.56055pt}{-2.56055pt}{-4.63623pt}{0.0pt}{-4.63623pt}\pgfsys@curveto{2.56055pt}{-4.63623pt}{4.63623pt}{-2.56055pt}{4.63623pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leq\frac{8\alpha^{2}}{(1-\gamma\lambda)^{2}}\|V_{k}-V_{\pi}\|_{2}^{2}+\frac{2\alpha^{2}}{(1-\gamma\lambda)^{2}}(4\|V_{\pi}\|_{2}+1)^{2}$
for all $k\geq\tau$.

  2. (2)

$\leavevmode\hbox to9.67pt{\vbox to9.67pt{\pgfpicture\makeatletter\hbox{\hskip
4.83623pt\lower-4.83623pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.63623pt}{0.0pt}\pgfsys@curveto{4.63623pt}{2.56055pt}{2.56055pt}{4.63623pt}{0.0pt}{4.63623pt}\pgfsys@curveto{-2.56055pt}{4.63623pt}{-4.63623pt}{2.56055pt}{-4.63623pt}{0.0pt}\pgfsys@curveto{-4.63623pt}{-2.56055pt}{-2.56055pt}{-4.63623pt}{0.0pt}{-4.63623pt}\pgfsys@curveto{2.56055pt}{-4.63623pt}{4.63623pt}{-2.56055pt}{4.63623pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{5}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leq\frac{16\alpha^{2}}{(1-\gamma\lambda)}\|V_{k}-V_{\pi}\|_{2}^{2}+\frac{4\alpha^{2}}{(1-\gamma\lambda)}(4\|V_{\pi}\|_{2}+1)^{2}$
for all $k\geq\tau$.

  3. (3)

$\leavevmode\hbox to9.67pt{\vbox to9.67pt{\pgfpicture\makeatletter\hbox{\hskip
4.83623pt\lower-4.83623pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.63623pt}{0.0pt}\pgfsys@curveto{4.63623pt}{2.56055pt}{2.56055pt}{4.63623pt}{0.0pt}{4.63623pt}\pgfsys@curveto{-2.56055pt}{4.63623pt}{-4.63623pt}{2.56055pt}{-4.63623pt}{0.0pt}\pgfsys@curveto{-4.63623pt}{-2.56055pt}{-2.56055pt}{-4.63623pt}{0.0pt}{-4.63623pt}\pgfsys@curveto{2.56055pt}{-4.63623pt}{4.63623pt}{-2.56055pt}{4.63623pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{6}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\leq\frac{64\alpha^{2}}{(1-\gamma\lambda)^{2}}\|V_{k}-V_{\pi}\|_{2}^{2}+\frac{4\alpha^{2}}{(1-\gamma\lambda)^{2}}(4\|V_{\pi}\|_{2}+1)^{2}$
for all $k\geq\tau$.

###### Proof of Lemma E.3.

  1. (1)

For all $k\geq\tau$, we have

4
$\displaystyle=\alpha^{2}\|F_{k}(V_{k},Y_{k})-F_{k}^{\tau}(V_{k},Y_{k}^{\tau})\|_{2}^{2}$
$\displaystyle\leq\frac{\alpha^{2}(\gamma\lambda)^{2(\tau+1)}}{(1-\gamma\lambda)^{2}}(2\|V_{k}\|_{2}+1)^{2}$
(Lemma 3.1)
$\displaystyle\leq\frac{\alpha^{4}}{(1-\gamma\lambda)^{2}}(2\|V_{k}-V_{\pi}\|_{2}+2\|V_{\pi}\|_{2}+1)^{2}$
$\displaystyle\leq\frac{8\alpha^{2}}{(1-\gamma\lambda)^{2}}\|V_{k}-V_{\pi}\|_{2}^{2}+\frac{2\alpha^{2}}{(1-\gamma\lambda)^{2}}(4\|V_{\pi}\|_{2}+1)^{2}.$

  2. (2)

For all $k\geq\tau$, we have

5
$\displaystyle=2\alpha(V_{k}-V_{\pi})^{\top}\left(F_{k}(V_{k},Y_{k})-F_{k}^{\tau}(V_{k},Y_{k}^{\tau})\right)$
$\displaystyle\leq
2\alpha\|V_{k}-V_{\pi}\|_{2}\|F_{k}(V_{k},Y_{k})-F_{k}^{\tau}(V_{k},Y_{k}^{\tau})\|_{2}$
$\displaystyle\leq\frac{2\alpha(\gamma\lambda)^{\tau+1}}{(1-\gamma\lambda)}\|V_{k}-V_{\pi}\|_{2}(2\|V_{k}\|_{2}+1)$
(Proposition 3.4 (1))
$\displaystyle\leq\frac{2\alpha(\gamma\lambda)^{\tau+1}}{(1-\gamma\lambda)}(2\|V_{k}-V_{\pi}\|_{2}+2\|V_{\pi}\|_{2}+1)^{2}$
$\displaystyle\leq\frac{16\alpha(\gamma\lambda)^{\tau+1}}{(1-\gamma\lambda)}\|V_{k}-V_{\pi}\|_{2}^{2}+\frac{4\alpha(\gamma\lambda)^{\tau+1}}{(1-\gamma\lambda)}(4\|V_{\pi}\|_{2}+1)^{2}$
$\displaystyle\leq\frac{16\alpha^{2}}{(1-\gamma\lambda)}\|V_{k}-V_{\pi}\|_{2}^{2}+\frac{4\alpha^{2}}{(1-\gamma\lambda)}(4\|V_{\pi}\|_{2}+1)^{2},.$
(The choice of $\tau$)

  3. (3)

For all $k\geq\tau$, we have

6
$\displaystyle=2\alpha\left(F_{k}^{\tau}(V_{k},Y_{k}^{\tau})-V_{k}\right)^{\top}\left(F_{k}(V_{k},Y_{k})-F_{k}^{\tau}(V_{k},Y_{k}^{\tau})\right)$
$\displaystyle\leq
2\alpha\|F_{k}^{\tau}(V_{k},Y_{k}^{\tau})-V_{k}\|_{2}\|F_{k}(V_{k},Y_{k})-F_{k}^{\tau}(V_{k},Y_{k}^{\tau})\|_{2}$
$\displaystyle\leq\frac{2\alpha(\gamma\lambda)^{\tau+1}}{1-\gamma\lambda}\left(\frac{3}{1-\gamma\lambda}\|V_{k}\|_{2}+\frac{1}{1-\gamma\lambda}+\|V_{k}\|_{2}\right)\left(2\|V_{k}\|_{2}+1\right)$
$\displaystyle\leq\frac{2\alpha(\gamma\lambda)^{\tau+1}}{(1-\gamma\lambda)^{2}}(4\|V_{k}\|_{2}+1)(2\|V_{k}\|_{2}+1)$
$\displaystyle\leq\frac{2\alpha(\gamma\lambda)^{\tau+1}}{(1-\gamma\lambda)^{2}}(4\|V_{k}-V_{\pi}\|_{2}+4\|V_{\pi}\|_{2}+1)^{2}$
$\displaystyle\leq\frac{64\alpha(\gamma\lambda)^{\tau+1}}{(1-\gamma\lambda)^{2}}\|V_{k}-V_{\pi}\|_{2}^{2}+\frac{4\alpha(\gamma\lambda)^{\tau+1}}{(1-\gamma\lambda)^{2}}(4\|V_{\pi}\|_{2}+1)^{2}$
$\displaystyle\leq\frac{64\alpha^{2}}{(1-\gamma\lambda)^{2}}\|V_{k}-V_{\pi}\|_{2}^{2}+\frac{4\alpha^{2}}{(1-\gamma\lambda)^{2}}(4\|V_{\pi}\|_{2}+1)^{2}.$
(The choice of $\tau$)

∎

The rest of the proof is to use the upper bounds we derived for the terms 1 to
6 in Eq. (32) to obtain the one-step contractive inequality. Repeatedly using
such one-step inequality and we get the finite-sample bounds stated in Theorem
3.4.

## References

  * Banach, [1922] Banach, S. (1922).  Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales.  Fund. math, 3(1):133–181.
  * Beck, [2017] Beck, A. (2017).  First-order methods in optimization, volume 25.  SIAM.
  * Beck and Srikant, [2012] Beck, C. L. and Srikant, R. (2012).  Error bounds for constant step-size $Q$-learning.  Systems & control letters, 61(12):1203–1208.
  * Beck and Srikant, [2013] Beck, C. L. and Srikant, R. (2013).  Improved upper bounds on the expected error in constant step-size $Q$-learning.  In 2013 American Control Conference, pages 1926–1931. IEEE.
  * Benveniste et al., [2012] Benveniste, A., Métivier, M., and Priouret, P. (2012).  Adaptive algorithms and stochastic approximations, volume 22.  Springer Science & Business Media.
  * Bertsekas and Tsitsiklis, [1996] Bertsekas, D. P. and Tsitsiklis, J. N. (1996).  Neuro-dynamic programming.  Athena Scientific.
  * Bhandari et al., [2018] Bhandari, J., Russo, D., and Singal, R. (2018).  A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation.  In Conference On Learning Theory, pages 1691–1692.
  * Borkar, [2009] Borkar, V. S. (2009).  Stochastic approximation: a dynamical systems viewpoint, volume 48.  Springer.
  * Borkar and Meyn, [2000] Borkar, V. S. and Meyn, S. P. (2000).  The ODE method for convergence of stochastic approximation and reinforcement learning.  SIAM Journal on Control and Optimization, 38(2):447–469.
  * Bottou et al., [2018] Bottou, L., Curtis, F. E., and Nocedal, J. (2018).  Optimization methods for large-scale machine learning.  Siam Review, 60(2):223–311.
  * [11] Chen, S., Devraj, A., Bernstein, A., and Meyn, S. (2020a).  Accelerating Optimization and Reinforcement Learning with Quasi-Stochastic Approximation.  Preprint arXiv:2009.14431.
  * [12] Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. (2020b).  Finite-Sample Analysis of Contractive Stochastic Approximation Using Smooth Convex Envelopes.  Advances in Neural Information Processing Systems, 33.
  * Chen et al., [2019] Chen, Z., Zhang, S., Doan, T. T., Clarke, J.-P., and Maguluri, S. T. (2019).  Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning.  Preprint arXiv:1905.11425.
  * Dann et al., [2019] Dann, C., Li, L., Wei, W., and Brunskill, E. (2019).  Policy certificates: Towards accountable reinforcement learning.  In International Conference on Machine Learning, pages 1507–1516. PMLR.
  * Dayan and Sejnowski, [1994] Dayan, P. and Sejnowski, T. J. (1994).  TD($\lambda$) converges with probability $1$.  Machine Learning, 14(3):295–301.
  * Devraj et al., [2018] Devraj, A. M., Bušic, A., and Meyn, S. (2018).  Zap meets momentum: Stochastic approximation algorithms with optimal convergence rate.  Preprint arXiv:1809.06277.
  * Devraj and Meyn, [2017] Devraj, A. M. and Meyn, S. (2017).  Zap $Q$-learning.  In Advances in Neural Information Processing Systems, pages 2235–2244.
  * Espeholt et al., [2018] Espeholt, L., Soyer, H., Munos, R., Simonyan, K., Mnih, V., Ward, T., Doron, Y., Firoiu, V., Harley, T., Dunning, I., et al. (2018).  IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures.  In International Conference on Machine Learning, pages 1407–1416.
  * Even-Dar and Mansour, [2003] Even-Dar, E. and Mansour, Y. (2003).  Learning rates for $Q$-learning.  Journal of Machine Learning Research, 5(Dec):1–25.
  * Harutyunyan et al., [2016] Harutyunyan, A., Bellemare, M. G., Stepleton, T., and Munos, R. (2016).  Q($\lambda$) with Off-Policy Corrections.  In International Conference on Algorithmic Learning Theory, pages 305–320. Springer.
  * Jaakkola et al., [1994] Jaakkola, T., Jordan, M. I., and Singh, S. P. (1994).  Convergence of stochastic iterative dynamic programming algorithms.  In Advances in neural information processing systems, pages 703–710.
  * Jin et al., [2018] Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018).  Is $Q$-learning provably efficient?  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 4868–4878.
  * Kearns and Singh, [2000] Kearns, M. J. and Singh, S. P. (2000).  Bias-Variance Error Bounds for Temporal Difference Updates.  In COLT, pages 142–147. Citeseer.
  * Khodadadian et al., [2021] Khodadadian, S., Chen, Z., and Maguluri, S. T. (2021).  Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm.  arXiv preprint arXiv:2102.09318.
  * Kober et al., [2013] Kober, J., Bagnell, J. A., and Peters, J. (2013).  Reinforcement learning in robotics: A survey.  The International Journal of Robotics Research, 32(11):1238–1274.
  * Kushner, [2010] Kushner, H. (2010).  Stochastic approximation: a survey.  Wiley Interdisciplinary Reviews: Computational Statistics, 2(1):87–96.
  * Kushner and Clark, [2012] Kushner, H. J. and Clark, D. S. (2012).  Stochastic approximation methods for constrained and unconstrained systems, volume 26.  Springer Science & Business Media.
  * Lan, [2020] Lan, G. (2020).  First-order and Stochastic Optimization Methods for Machine Learning.  Springer.
  * Levin and Peres, [2017] Levin, D. A. and Peres, Y. (2017).  Markov chains and mixing times, volume 107.  American Mathematical Soc.
  * Li et al., [2021] Li, G., Cai, C., Chen, Y., Gu, Y., Wei, Y., and Chi, Y. (2021).  Tightening the Dependence on Horizon in the Sample Complexity of $Q$-Learning.  Preprint arXiv:2102.06548.
  * Li et al., [2020] Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020).  Sample complexity of asynchronous $Q$-learning: Sharper analysis and variance reduction.  Preprint arXiv:2006.03041.
  * Munos et al., [2016] Munos, R., Stepleton, T., Harutyunyan, A., and Bellemare, M. G. (2016).  Safe and efficient off-policy reinforcement learning.  In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 1054–1062.
  * Precup et al., [2000] Precup, D., Sutton, R. S., and Singh, S. P. (2000).  Eligibility Traces for Off-Policy Policy Evaluation.  In Proceedings of the Seventeenth International Conference on Machine Learning, pages 759–766.
  * Puterman, [1995] Puterman, M. L. (1995).  Markov decision processes: Discrete stochastic dynamic programming.  Journal of the Operational Research Society, 46(6):792–792.
  * Qu and Wierman, [2020] Qu, G. and Wierman, A. (2020).  Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning.  In Conference on Learning Theory, pages 3185–3205. PMLR.
  * Robbins and Monro, [1951] Robbins, H. and Monro, S. (1951).  A stochastic approximation method.  The Annals of Mathematical Statistics, pages 400–407.
  * Ryu and Boyd, [2016] Ryu, E. K. and Boyd, S. (2016).  Primer on monotone operator methods.  Appl. Comput. Math, 15(1):3–43.
  * Silver et al., [2016] Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016).  Mastering the game of go with deep neural networks and tree search.  nature, 529(7587):484.
  * Silver et al., [2017] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. (2017).  Mastering the game of go without human knowledge.  Nature, 550(7676):354.
  * Singh and Sutton, [1996] Singh, S. P. and Sutton, R. S. (1996).  Reinforcement learning with replacing eligibility traces.  Machine learning, 22(1):123–158.
  * Srikant and Ying, [2019] Srikant, R. and Ying, L. (2019).  Finite-time error bounds for linear stochastic approximation and TD learning.  In Conference on Learning Theory, pages 2803–2830.
  * Sutton, [1999] Sutton, R. S. (1999).  Open theoretical questions in reinforcement learning.  In European Conference on Computational Learning Theory, pages 11–17. Springer.
  * Sutton and Barto, [2018] Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * Szepesvári et al., [1997] Szepesvári, C. et al. (1997).  The asymptotic convergence-rate of $Q$-learning.  In NIPS, volume 10, pages 1064–1070. Citeseer.
  * Tsitsiklis, [1994] Tsitsiklis, J. N. (1994).  Asynchronous stochastic approximation and $Q$-learning.  Machine learning, 16(3):185–202.
  * Tsitsiklis and Van Roy, [1997] Tsitsiklis, J. N. and Van Roy, B. (1997).  Analysis of temporal-difference learning with function approximation.  In Advances in neural information processing systems, pages 1075–1081.
  * Tsitsiklis and Van Roy, [1999] Tsitsiklis, J. N. and Van Roy, B. (1999).  Average cost temporal-difference learning.  Automatica, 35(11):1799–1808.
  * Wainwright, [2019] Wainwright, M. J. (2019).  Stochastic approximation with cone-contractive operators: Sharp $\ell_{\infty}$-bounds for ${Q}$-learning.  Preprint arXiv:1905.06265.
  * Watkins and Dayan, [1992] Watkins, C. J. and Dayan, P. (1992).  $Q$-learning.  Machine learning, 8(3-4):279–292.
  * Watkins, [1989] Watkins, C. J. C. H. (1989).  Learning from delayed rewards.


# Uniform rate inflation on the brane

Chia-Min Lin1 Rei Tamura2 Keiko I. Nagao2 1Fundamental General Education
Center, National Chin-Yi University of Technology, Taichung 411030, Taiwan,
R.O.C.  2Department of Physics, Faculty of Science, Okayama University of
Science, 1-1 Ridaicho, Okayama, 700-0005, Japan

###### Abstract

We propose a model of uniform rate inflation on the brane. The potential is
given by a hyperbolic cosine function plus a negative cosmological constant.
The equation of motion is solved analytically without using slow-roll
approximation. The result is that the inflaton field is rolling at a constant
speed. The prediction for cosmological perturbations depends on the field
value at the end of inflation. The experimental constraints could be satisfied
in the parameter space.

##  I Introduction

Cosmic inflation Starobinsky:1980te ; Guth:1980zm ; Linde:1981mu is arguably
the standard scenario of the very early universe. The single idea solves
almost all the problems of the traditional hot big bang model, such as the
flatness problem, the horizon problem, and the unwanted relics problem. The
quantum fluctuations during inflation are amplified to cosmological scales and
could generate primordial tensor and scalar perturbations constrained by
experimental observations such as cosmic microwave background (CMB) observed
by Planck Planck:2018jri .

However, many inflation models exist, and there is no consensus about the best
model. Occam’s razor recommends simplicity. The simplest inflation models are
described by a scalar field $\phi$ called the inflaton field with a potential
$V(\phi)$. Presumably, the energy density of the universe $\rho$ during
inflation is dominated by the energy density of $\phi$ given by

$\rho=\frac{1}{2}\dot{\phi}^{2}+V(\phi).$ (1)

Conventionally, the Friedmann equation of general relativity in a flat,
homogeneous, and isotropic universe is

$3H^{2}=\rho,$ (2)

where $H\equiv\dot{a}/a$ is the Hubble parameter with $a$ the scale factor.
Here and throughout this work, we set the reduced Planck mass to unity, that
is, $M_{P}\equiv 1/\sqrt{8\pi G}=1$. The equation of motion of the inflaton
field is

$\ddot{\phi}+3H\dot{\phi}+V^{\prime}(\phi)=0.$ (3)

In Lin:2023xgs , one of the authors proposed a model called uniform rate
inflation where the inflaton field has the potential

$V(\phi)=\frac{3\lambda^{2}\phi^{2}}{4}-\frac{\lambda^{2}}{2}.$ (4)

The potential consists of a quadratic term and a related negative cosmological
constant. In this model, the equation of motion is solved analytically as

$\dot{\phi}=-\lambda.$ (5)

The inflaton field is rolling at a uniform rate; thus, it is called uniform
rate inflation. Note that there is no need to use slow-roll approximation to
analyze the equation of motion. The solution was found through a study of
quantum cosmology in the framework of de Broglie-Bohm theory Lin:2023sza . The
time evolution can be easily integrated to

$\phi=-\lambda t+d,$ (6)

where $d$ is the integration constant. This model is simple and neat. This
work aims to extend uniform rate inflation to the braneworld and discover the
predictions.

##  II braneworld cosmology

The idea of the braneworld proposes that our four-dimensional world is a four-
dimensional hypersurface (3-brane) embedded in a higher dimensional bulk
Arkani-Hamed:1998sfv . In this scenario, ordinary matter is confined to our
world, while gravity is in the whole $(4+n)$-dimensional spacetime. Such
models are motivated by strongly coupled string theories Horava:1996ma ;
Antoniadis:1998ig . To have sufficiently small extra dimensions not excluded
by short-distance gravitational measurements, we should have $n\geq 2$ from
the argument of dimensional reduction. However, Randall and Sundrum discovered
that the $n=1$ case is still allowed because of the gravitational effects of a
brane on the extra dimension Randall:1999ee ; Randall:1999vf . If one concerns
cosmological evolution of the universe, the Friedmann equation is modified to
Cline:1999ts ; Csaki:1999jh ; Binetruy:1999ut ; Binetruy:1999hy ;
Freese:2002sq ; Freese:2002gv ; Maartens:1999hf

$3H^{2}=\rho\left(1+\frac{\rho}{2\Lambda}\right),$ (7)

where the brane tension $\Lambda$ is related to the 5-dimensional Planck mass
$M_{5}$ as

$\Lambda=\frac{3M_{5}^{6}}{4\pi}.$ (8)

We recover the conventional Friedmann equation if $\rho\ll 2\Lambda$ (like our
current universe). The nucleosynthesis limit implies that
$\Lambda\gtrsim(1\mbox{ MeV})^{4}\sim(4.1\times 10^{-22})^{4}$. A more
stringent constraint can be obtained by requiring the theory to reduce to
Newtonian gravity on scales larger than $1$ mm; this gives $M_{5}\gtrsim
10^{5}\mbox{ TeV}$. which corresponds to $\Lambda\gtrsim 5.0\times 10^{-53}$
Maartens:1999hf . We consider a braneworld described by Eq. (7) in the
following discussion.

##  III uniform rate inflation on the brane

We seek a potential $V(\phi)$ in the braneworld scenario, which has the
solution of the equation of motion given by Eq. (5). Note that
$\ddot{\phi}$=0, therefore the equation of motion from Eq. (3) is

$-3\lambda H+V^{\prime}(\phi)=0,$ (9)

where we have used Eq. (5). By using Eqs. (1), (5), (7), and (9), we can write

$(V(\phi)^{\prime})^{2}=3\lambda^{2}\left[\frac{\lambda^{2}}{2}+V(\phi)+\frac{\left(\frac{\lambda^{2}}{2}+V(\phi)\right)^{2}}{2\Lambda}\right].$
(10)

Interestingly, this equation can be integrated to obtain

$V(\phi)=\frac{\Lambda
c}{2}e^{\sqrt{\frac{3\lambda^{2}}{2\Lambda}}}+\frac{\Lambda}{2c}e^{-\sqrt{\frac{3\lambda^{2}}{2\Lambda}}}-\Lambda-\frac{\lambda^{2}}{2},$
(11)

where $c$ is an arbitrary (suitably rescaled) integration constant. For
simplicity, we choose $c=1$ to obtain

$V(\phi)=\Lambda\cosh\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi-\Lambda-\frac{\lambda^{2}}{2}.$
(12)

This would be the model considered in the following discussion. In retrospect,
it is pretty remarkable that such simple potential admitted an analytical
solution given by Eq. (5) for the complicated equation of motion provided by
Eqs. (1), (3), and (7). Note that we do not need slow-roll approximation here.
The stability of the solution is discussed in the Appendix.

It is interesting to note that when
$\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi\ll 1$, we can expand the potential
of Eq. (12) by using

$\cosh\theta=1+\frac{\theta^{2}}{2}+\cdots.$ (13)

We can regard this as the low-energy limit where the brane high-energy
corrections become unimportant. The result is that we recover Eq. (4) with the
predictions of primordial perturbations given in Lin:2023xgs . Therefore, Eq.
(12) may be regarded as the generalization of the uniform rate inflation given
by Eq. (4) to the braneworld.

Since the potential is an even function of $\phi$, we can assume $\phi>0$ in
the following discussions without loss of generality. The Hubble parameter can
be obtained from Eq. (9) as

$H=\frac{\dot{a}}{a}=\sqrt{\frac{\Lambda}{6}}\sinh\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi.$
(14)

This can be integrated to obtain the scale factor either as a function of time
$t$ or as a function of $\phi$, which is related through $t$ via Eq. (6) as

$a=e^{-\frac{\Lambda}{3\lambda^{2}}\cosh\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi}\equiv
e^{\alpha},$ (15)

(up to an irrelevant integration constant) where we have defined a parameter
$\alpha$. In slow-roll inflation, the scale factor during inflation is
described as quasi-exponential or quasi-de Sitter expansion. Our model has a
closed form for the scale factor, which shows precisely how the scale factor
evolves.

The field value $\phi=\phi_{e}$ at the end of inflation is obtained by solving
$\ddot{a}=0$, which gives

$\cosh\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi_{e}=\frac{3\lambda^{2}}{2\Lambda}+\sqrt{\frac{9\lambda^{4}}{4\Lambda^{2}}+1}.$
(16)

When $\phi>\phi_{e}$, inflation is happening with $\ddot{a}>0$. We assume that
somehow reheating happens after $\phi=\phi_{e}$ and recovers hot big bang. The
inflaton field value $\phi_{60}$ at the number of e-folds $N=60$ (which
corresponds to horizon exit or CMB scale) can be obtained by solving
$\Delta\alpha=60$ that is

$-\frac{\Lambda}{3\lambda^{2}}\left(\frac{3\lambda^{2}}{2\Lambda}+\sqrt{\frac{9\lambda^{4}}{4\Lambda^{2}}+1}\right)+\frac{\Lambda}{3\lambda^{2}}\cosh\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi_{60}=60.$
(17)

This gives

$\cosh\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi_{60}=\frac{363\lambda^{2}}{2\Lambda}+\sqrt{\frac{9\lambda^{4}}{4\Lambda^{2}}+1}.$
(18)

A useful identity is

$\cosh^{2}\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi_{60}-1=\frac{65889\lambda^{4}}{2\Lambda^{2}}+\frac{363\lambda^{2}}{\Lambda}\sqrt{\frac{9\lambda^{4}}{4\Lambda^{2}}+1}.$
(19)

Primordial curvature perturbation can be calculated by using the $\delta N$
formalism Sasaki:1995aw ; Sasaki:1998ug ; Lyth:2004gb ; Lyth:2005fi ;
Wands:2000dp . Our $\alpha$ corresponds to $-N$, therefore by using Eqs. (14)
and (15) with $\delta\phi=H/2\pi$, we have

$\zeta=\frac{\partial
N}{\partial\phi}\delta\phi=-\frac{\partial\alpha}{\partial\phi}\delta\phi=\frac{\Lambda}{12\pi\lambda}\left[\cosh^{2}\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi-1\right],$
(20)

By Eq. (19) and cosmic microwave background (CMB) normalization $\zeta=5\times
10^{-5}$, we obtain

$\frac{\lambda}{12\pi}\left[\frac{65889\lambda^{2}}{2\Lambda}+363\sqrt{\frac{9\lambda^{4}}{4\Lambda^{2}}+1}\right]=5\times
10^{-5}.$ (21)

By using $\lambda^{2}/\Lambda$ as the x-axis, we plot $\lambda$ and $\Lambda$
in Fig. 2 and Fig. 2.

Figure 1: $\lambda$ as a function of $\lambda^{2}/\Lambda$.

Figure 2: $\Lambda$ as a function of $\lambda^{2}/\Lambda$.

Another useful identity can be obtained by Eqs. (19) and (21) (or imposing CMB
normalization on Eq. (20)),

$\cosh^{2}\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi_{60}-1=\frac{\lambda}{\Lambda}\times
6\pi\times 10^{-4}.$ (22)

##  IV the spectral index and the running spectral index

We can write the spectrum by using Eqs. (15) and (20) as111More precisely, we
should write $P=\langle\zeta^{2}\rangle$. However, if we write
$\delta\phi=H/2\pi$ instead of $\langle\delta\phi^{2}\rangle=(H/2\pi)^{2}$ for
$\zeta=\frac{\partial N}{\partial\phi}\delta\phi$, then $P=\zeta^{2}$ gives
the correct result.

$P=\zeta^{2}=\frac{\Lambda^{2}}{144\pi^{2}\lambda^{2}}\left(\frac{9\lambda^{4}}{\Lambda^{2}}\alpha^{2}-1\right)^{2}.$
(23)

The spectral index is given by

$n_{S}\equiv 1+\frac{d\ln P}{d\ln k}=1+\frac{d\ln
P}{d\alpha}=1+\frac{\frac{36\lambda^{4}}{\Lambda^{2}}\alpha}{\frac{9\lambda^{4}}{\Lambda^{2}}\alpha^{2}-1},$
(24)

where $k$ is the comoving wave number of the perturbation. By using Eqs. (15),
(18) and (22), we obtain

$n_{S}=1-6366\lambda\left(\frac{363\lambda^{2}}{2\Lambda}+\sqrt{\frac{9\lambda^{4}}{4\Lambda^{2}}+1}\right).$
(25)

This is plotted as the blue dashed lines in Fig. 3. In the figure, light blue
and cyan regions correspond to the allowed parameter spaces of by 68.3 %
(1$\sigma$) and 99.7 % (3$\sigma$) Confidence Level (C.L.), respectively
Planck:2018jri .

Figure 3: $n_{S}$ as a function of $\lambda^{2}/\Lambda$ (left) and $\Lambda$
(right). The blue dashed line corresponds to the case where inflation ends at
$\phi_{e}$, and the red solid line corresponds to the case where inflation
ends at $\phi_{0}$. The latter is discussed in Sec. V. Light blue and cyan
regions correspond to the allowed parameter spaces of by 68.3 % (1$\sigma$)
and 99.7 % (3$\sigma$) C.L., respectively Planck:2018jri .

The running spectral index can be obtained by taking one more derivative of
$n_{S}$ given in Eq. (24) with respect to $\alpha$ as

$n^{\prime}\equiv\frac{dn_{S}}{d\ln
k}=\frac{dn_{S}}{d\alpha}=-\frac{\frac{36\lambda^{4}}{\Lambda^{2}}\left(\frac{9\lambda^{4}\alpha^{2}}{\Lambda^{2}}+1\right)}{\left(\frac{9\lambda^{4}\alpha^{2}}{\Lambda^{2}}-1\right)^{2}}=-1.91\times
10^{4}\frac{\lambda^{3}}{\Lambda}-2.03\times 10^{7}\lambda^{2},$ (26)

where we have used Eqs. (15) and (22) to obtain the last equality. This is
plotted in Fig. 4 as the blue dashed lines. Observations require
$|n^{\prime}|\lesssim 0.01$ Planck:2018jri . Our results of the running
spectral index $n^{\prime}$ are well within the experimental bounds.

Figure 4: $n^{\prime}$ as a function of $\lambda^{2}/\Lambda$ (left) and
$\Lambda$ (right). The blue dashed lines correspond to the case where
inflation ends at $\phi_{e}$, and the red solid lines correspond to the case
where inflation ends at $\phi_{0}$. The latter is discussed in Sec. V.

##  V the tensor-to-scalar ratio

The tensor-to-scalar ratio $r$ is an experimental parameter that represents
primordial gravitational waves generated during inflation. A detection of it
may be regarded as a smoking gun of cosmic inflation or a holy grail of
experimental search. It is proportional to the ratio of the tensor
perturbation and the scalar perturbation.

The scalar perturbation is represented by

$A_{S}^{2}=\frac{4}{25}\zeta^{2}=\frac{H^{2}\Lambda}{150\pi^{2}\lambda^{2}}\left[\cosh^{2}\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi-1\right].$
(27)

The scalar perturbation generates primordial density perturbations that
provide the initial condition for the structure formation of the universe and
the CMB temperature anisotropy. On the other hand, the tensor perturbation in
a braneworld is Langlois:2000ns ; Bento:2008yx

$A_{T}^{2}=\frac{H^{2}}{50\pi^{2}}F^{2},$ (28)

where

$F^{2}=\left[\sqrt{1+x^{2}}-x^{2}\sinh^{-1}\left(\frac{1}{x}\right)\right]^{-1},$
(29)

and

$x\equiv\left(\frac{3H^{2}}{4\pi\Lambda}\right)^{1/2}.$ (30)

From Eqs. (14) and (22), we obtain

$x^{2}=7.5\times 10^{-5}\frac{\lambda}{\Lambda}.$ (31)

We plot $x$ and $F^{2}$ in our model as a function of $\lambda^{2}/\Lambda$ in
Fig. 6 and Fig. 6.

Figure 5: $x$ as a function of $\lambda^{2}/\Lambda$.

Figure 6: $F^{2}$ as a function of $\lambda^{2}/\Lambda$.

By using Eq. (22), we obtain

$\frac{A_{T}^{2}}{A_{S}^{2}}=\frac{\lambda F^{2}}{2\pi\times 10^{-4}}.$ (32)

The tensor-to-scalar ratio $r$ is defined by

$r\equiv 16\frac{A_{T}^{2}}{A_{S}^{2}}=\frac{8}{\pi}\times 10^{4}\lambda
F^{2}.$ (33)

We plot $r$ as functions of $\lambda^{2}/\Lambda$ and $\Lambda$ in Fig. 7 as
the blue dashed lines.

Figure 7: $r$ as a function of $\lambda^{2}/\Lambda$ (left) and $\Lambda$
(right). The blue dashed lines correspond to the case where inflation ends at
$\phi_{e}$, and the red solid lines correspond to the case where inflation
ends at $\phi_{0}$. The latter is discussed in Sec. V. The constraints are
from Planck:2018jri .

We plot the results of $n_{S}$ and $r$ by the blue dashed line to compare with
experimental data in Fig. 8. Unfortunately, the model does not fit the
constraints.

Figure 8: The spectral index and tensor-to-scalar ratio. The constraints are
from Planck:2018jri . The blue dashed (red) line corresponds to inflation ends
at $\phi_{e}$ ($\phi_{0}$).

One solution is to assume that inflation ends not at $\phi=\phi_{e}$, but at
$\phi=\phi_{0}$ with $\phi_{0}>\phi_{e}$. For example, let us assume
$\Delta\alpha=25$ from $\phi_{0}$ to $\phi_{e}$ in the original model, that is

$-\frac{\Lambda}{3\lambda^{2}}\left(\frac{3\lambda^{2}}{2\Lambda}+\sqrt{\frac{9\lambda^{4}}{4\Lambda^{2}}+1}\right)+\frac{\Lambda}{3\lambda^{2}}\cosh\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi_{0}=25.$
(34)

If inflation ends at $\phi_{0}$, $\Delta\alpha=25$ is missing. Therefore to
have $\Delta\alpha=60$ from $\phi_{60}$ to $\phi_{0}$, we have to modify the
right-hand side of Eq. (17) to $85$. Using this new value of $\phi_{60}$, we
plot the spectral index in Fig. 3, the tensor-to-scalar ratio in Fig. 7, and
their combination in Fig. 8 as the red solid lines. We also plot the running
spectral index in Fig. 4 as the red solid lines. We can see that experimental
constraints can be satisfied by introducing a new parameter $\phi_{0}$.

##  VI conclusion

In this work, we propose a model of uniform rate inflation on the brane. Due
to the complexity of the Hubble parameter given by Eq. (7) and the
corresponding equation of motion, it is pretty remarkable that the equation of
motion can be solved analytically without using slow-roll approximation.
Furthermore, we carefully calculated the predictions of primordial
perturbations, such as the spectral index, the running spectral index, and the
tensor-to-scalar ratio. If inflation ends at $\phi_{e}$, the model could not
fit the observational constraints. However, if inflation ends at $\phi_{0}$,
it is possible to fit the observational data.

##  Appendix A stability of the solution

In this section, we consider a perturbation of $\dot{\phi}$ of the value given
by Eq. (5). Intuitively, we can see from Eqs. (3) and (7) that if somehow
$\dot{\phi}$ is increased (decreased) with the same $V\phi$ and
$V\phi^{\prime}$, $H$ would also increase (decrease). Therefore, the term
$3H\dot{\phi}$ in Eq. (3) is increased (decreased). To compensate for this
increasing (decreasing), a negative (positive) $\ddot{\phi}$ appears, and this
reduces (enhances) $\dot{\phi}$ towards the value given by Eq. (5). There is a
feedback mechanism.

Let us discuss it quantitatively. Consider a perturbation $u$ of the solution

$\displaystyle\dot{\phi}$ $\displaystyle\rightarrow$
$\displaystyle\dot{\phi}+u,$ (35) $\displaystyle\ddot{\phi}$
$\displaystyle\rightarrow$ $\displaystyle\ddot{\phi}+\dot{u}$ (36)
$\displaystyle H$ $\displaystyle\rightarrow$ $\displaystyle H+\delta H.$ (37)

Substituting into Eq. (7), we have

$3\left(H+\delta
H\right)^{2}=\frac{(\dot{\phi}+u)^{2}}{2}+V(\phi)+\frac{\left[\frac{(\dot{\phi}+u)^{2}}{2}+V(\phi)\right]^{2}}{2\Lambda}.$
(38)

This implies

$6H\delta
H=\dot{\phi}u+\frac{\dot{\phi}u}{\lambda}\left(\frac{\dot{\phi}^{2}}{2}+V(\phi)\right).$
(39)

By using Eqs. (5), (12), and (14), we obtain

$\delta H=-\frac{\lambda
u}{\sqrt{6\Lambda}}\coth\sqrt{\frac{3\lambda^{2}}{2\Lambda}}(d-\lambda t).$
(40)

Next, take the first-order perturbation of Eq. (3), we have

$\dot{u}+\left[\sqrt{\frac{3\Lambda}{2}}\sinh\sqrt{\frac{3\lambda^{2}}{2\Lambda}}(d-\lambda
t)+\lambda^{2}\sqrt{\frac{3}{2\Lambda}}\coth\sqrt{\frac{3\lambda^{2}}{2\Lambda}}(d-\lambda
t)\right]u=0.$ (41)

The above differential equation can be solved to obtain

$|u|=b\left|\sinh\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi\right|e^{\frac{\Lambda}{\lambda^{2}}\cosh\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi},$
(42)

where $b$ is an integration constant. Note that $u$ is a small perturbation,
and $\phi$ decreases during inflation. Therefore, $u$ drops out very fast. For
example, if $\cosh\sqrt{\frac{3\lambda^{2}}{2\Lambda}}\phi$ drops by a factor
of $1/10$. Then $|u|$ drops at least by $0.1e^{-10}$.

###### Acknowledgements.

This work is supported by the National Science and Technology Council (NSTC)
of Taiwan under grant number 112-2112-M-167-001-MY2 (CML). The work is also
supported by JSPS Grant-in-Aid for Scientific Research (C) 21K03562 and (C)
21K03583 (KIN). Discussions during the Workshop on Particle and Astroparticle
Physics “Key Interactions Bound for the Invisibles 2023” were helpful as we
started this work.

## References

  * (1) A. A. Starobinsky, “A New Type of Isotropic Cosmological Models Without Singularity,” Phys. Lett. B 91, 99-102 (1980) doi:10.1016/0370-2693(80)90670-X
  * (2) A. H. Guth, “The Inflationary Universe: A Possible Solution to the Horizon and Flatness Problems,” Phys. Rev. D 23, 347-356 (1981) doi:10.1103/PhysRevD.23.347
  * (3) A. D. Linde, “A New Inflationary Universe Scenario: A Possible Solution of the Horizon, Flatness, Homogeneity, Isotropy and Primordial Monopole Problems,” Phys. Lett. B 108, 389-393 (1982) doi:10.1016/0370-2693(82)91219-9
  * (4) Y. Akrami et al. [Planck], “Planck 2018 results. X. Constraints on inflation,” Astron. Astrophys. 641, A10 (2020) doi:10.1051/0004-6361/201833887 [arXiv:1807.06211 [astro-ph.CO]].
  * (5) C. M. Lin, “Uniform rate inflation,” JCAP 04, 037 (2023) doi:10.1088/1475-7516/2023/04/037 [arXiv:2303.04999 [hep-ph]].
  * (6) C. M. Lin, “Just some simple (but nontrivial) analytical solutions for de Broglie-Bohm quantum cosmology,” [arXiv:2301.06088 [gr-qc]].
  * (7) N. Arkani-Hamed, S. Dimopoulos and G. R. Dvali, “Phenomenology, astrophysics and cosmology of theories with submillimeter dimensions and TeV scale quantum gravity,” Phys. Rev. D 59, 086004 (1999) doi:10.1103/PhysRevD.59.086004 [arXiv:hep-ph/9807344 [hep-ph]].
  * (8) P. Horava and E. Witten, “Eleven-dimensional supergravity on a manifold with boundary,” Nucl. Phys. B 475, 94-114 (1996) doi:10.1016/0550-3213(96)00308-2 [arXiv:hep-th/9603142 [hep-th]].
  * (9) I. Antoniadis, N. Arkani-Hamed, S. Dimopoulos and G. R. Dvali, “New dimensions at a millimeter to a Fermi and superstrings at a TeV,” Phys. Lett. B 436, 257-263 (1998) doi:10.1016/S0370-2693(98)00860-0 [arXiv:hep-ph/9804398 [hep-ph]].
  * (10) L. Randall and R. Sundrum, “A Large mass hierarchy from a small extra dimension,” Phys. Rev. Lett. 83, 3370-3373 (1999) doi:10.1103/PhysRevLett.83.3370 [arXiv:hep-ph/9905221 [hep-ph]].
  * (11) L. Randall and R. Sundrum, “An Alternative to compactification,” Phys. Rev. Lett. 83, 4690-4693 (1999) doi:10.1103/PhysRevLett.83.4690 [arXiv:hep-th/9906064 [hep-th]].
  * (12) J. M. Cline, C. Grojean and G. Servant, “Cosmological expansion in the presence of extra dimensions,” Phys. Rev. Lett. 83, 4245 (1999) doi:10.1103/PhysRevLett.83.4245 [arXiv:hep-ph/9906523 [hep-ph]].
  * (13) C. Csaki, M. Graesser, C. F. Kolda and J. Terning, “Cosmology of one extra dimension with localized gravity,” Phys. Lett. B 462, 34-40 (1999) doi:10.1016/S0370-2693(99)00896-5 [arXiv:hep-ph/9906513 [hep-ph]].
  * (14) P. Binetruy, C. Deffayet and D. Langlois, “Nonconventional cosmology from a brane universe,” Nucl. Phys. B 565, 269-287 (2000) doi:10.1016/S0550-3213(99)00696-3 [arXiv:hep-th/9905012 [hep-th]].
  * (15) P. Binetruy, C. Deffayet, U. Ellwanger and D. Langlois, “Brane cosmological evolution in a bulk with cosmological constant,” Phys. Lett. B 477, 285-291 (2000) doi:10.1016/S0370-2693(00)00204-5 [arXiv:hep-th/9910219 [hep-th]].
  * (16) K. Freese and M. Lewis, “Cardassian expansion: A Model in which the universe is flat, matter dominated, and accelerating,” Phys. Lett. B 540, 1-8 (2002) doi:10.1016/S0370-2693(02)02122-6 [arXiv:astro-ph/0201229 [astro-ph]].
  * (17) K. Freese, “Generalized Cardassian expansion: Models in which the universe is flat, matter dominated, and accelerating,” Nucl. Phys. B Proc. Suppl. 124, 50-54 (2003) doi:10.1016/S0920-5632(03)02076-0 [arXiv:hep-ph/0208264 [hep-ph]].
  * (18) R. Maartens, D. Wands, B. A. Bassett and I. Heard, “Chaotic inflation on the brane,” Phys. Rev. D 62, 041301 (2000) doi:10.1103/PhysRevD.62.041301 [arXiv:hep-ph/9912464 [hep-ph]].
  * (19) M. Sasaki and E. D. Stewart, “A General analytic formula for the spectral index of the density perturbations produced during inflation,” Prog. Theor. Phys. 95, 71-78 (1996) doi:10.1143/PTP.95.71 [arXiv:astro-ph/9507001 [astro-ph]].
  * (20) M. Sasaki and T. Tanaka, “Superhorizon scale dynamics of multiscalar inflation,” Prog. Theor. Phys. 99, 763-782 (1998) doi:10.1143/PTP.99.763 [arXiv:gr-qc/9801017 [gr-qc]].
  * (21) D. H. Lyth, K. A. Malik and M. Sasaki, “A General proof of the conservation of the curvature perturbation,” JCAP 05, 004 (2005) doi:10.1088/1475-7516/2005/05/004 [arXiv:astro-ph/0411220 [astro-ph]].
  * (22) D. H. Lyth and Y. Rodriguez, “The Inflationary prediction for primordial non-Gaussianity,” Phys. Rev. Lett. 95, 121302 (2005) doi:10.1103/PhysRevLett.95.121302 [arXiv:astro-ph/0504045 [astro-ph]].
  * (23) D. Wands, K. A. Malik, D. H. Lyth and A. R. Liddle, “A New approach to the evolution of cosmological perturbations on large scales,” Phys. Rev. D 62, 043527 (2000) doi:10.1103/PhysRevD.62.043527 [arXiv:astro-ph/0003278 [astro-ph]].
  * (24) D. Langlois, R. Maartens and D. Wands, “Gravitational waves from inflation on the brane,” Phys. Lett. B 489, 259-267 (2000) doi:10.1016/S0370-2693(00)00957-6 [arXiv:hep-th/0006007 [hep-th]].
  * (25) M. C. Bento, R. G. Felipe and N. M. C. Santos, “Brane assisted quintessential inflation with transient acceleration,” Phys. Rev. D 77, 123512 (2008) doi:10.1103/PhysRevD.77.123512 [arXiv:0801.3450 [astro-ph]].