# Concentration bounds for SSP Q-learning for average cost MDPs

Shaan ul Haque1 and Vivek S. Borkar2,∗ *Work of VSB was supported by an S. S.
Bhatnagar Fellowship from Council for Scientific and Industrial Research,
Govt. of India1Department of Electrical Engineering, IIT Bombay, Powai, Mumbai
400076, India<EMAIL_ADDRESS>of Electrical Engineering,
IIT Bombay, Powai, Mumbai 400076, India<EMAIL_ADDRESS>
###### Abstract

We derive a concentration bound for a Q-learning algorithm for average cost
Markov decision processes based on an equivalent shortest path problem, and
compare it numerically with the alternative scheme based on relative value
iteration.

##  I Introduction

Q-learning, introduced originally for the discounted cost Markov decision
processes in [1], is a data-driven reinforcement learning algorithm for
learning the ‘Q-factor’ function arising from the dynamic programming equation
for the infinite horizon discounted reward problem. It can be viewed as a
stochastic approximation counterpart of the classical value iteration for
computing the value function arising as the solution of the corresponding
dynamic programming equation. Going over from value function to the so called
Q-factors facilitates an interchange of the conditional expectation and the
nonlinearity (the minimization, to be precise) in the recursion, making it
amenable for stochastic approximation. These ideas, however, do not extend
automatically to the average cost problem, which is harder to analyze even
when the model (i.e., the controlled transition probabilities) is readily
available. The reason for this is the non-contractive nature of the associated
Bellman operator. This extension was achieved in [2] in two different ways.
The first, called RVI Q-learning, is a stochastic approximation counterpart of
the ‘relative value iteration’ (or RVI) algorithm for average cost [3] and is
close in spirit to the original. However, there is another algorithm dubbed
SSP Q-learning based on an alternative scheme due to Bertsekas [4], which does
involve a contraction under a weighted max-norm. Motivated by a recent paper
on concentration for stochastic approximation in [5], we present here a
similar concentration for the SSP Q-learning exploiting its explicitly
contractive nature, something that is missing in RVI, leading to non-trivial
technical issues in providing finite time guarantees for it (see, e.g., [6]).
We also provide an empirical comparison between the two with suggestive
outcomes.

Section II builds up the background and section III states the key assumptions
and the main result. Its proof follows in section IV. Section V describes the
numerical experiments.

##  II Background

###  II-A Preliminaries

We consider a controlled Markov chain $\\{X_{n}\\}$ on a finite state space
$S=\\{1,2,...,d\\}$ with a finite action space $U=\\{u_{1},...,u_{r}\\}$ and
transition probabilities $p(j|i,u)=$ the probability of transition from $i$ to
$j$ under action $u$ for $i,j\in S,u\in U$. Associated with this transition is
a “running cost” $k:S\times U\mapsto\mathcal{R}$ and the aim is to choose
actions $\\{Z_{n}\\}$ non-anticipatively (i.e., conditionally independent of
the future state trajectory given past states and actions) so as to minimize
the “average cost”

$\limsup_{n\to\infty}\frac{1}{n}\sum_{m=0}^{n-1}E[k(X_{m},Z_{m})].$ (1)

We shall be interested in “stationary policies” wherein $Z_{n}=v(X_{n})$ for a
map $v:S\to U$. It is known that an optimal stationary policy exists under the
following “unichain” condition which we assume throughout: under any
stationary policy the chain has a single communicating class containing a
common state (say, $i_{0}$). The dynamic programming equation for the above
problem is [3]

$V(i)=\min_{u}\Big{[}k(i,u)+\sum_{j\in\mathcal{S}}p(j|i,u)V(j)-\beta\Big{]}.$
(2)

The unknowns are $V(\cdot),\beta$ where $\beta$ is uniquely characterized as
the optimal average cost. $V(\cdot)$ is only unique upto an additive constant.
The associated “Q-factor” is

$Q(i,a)=\Big{[}k(i,u)+\sum_{j\in\mathcal{S}}p(j|i,u)\min_{v}Q(j,v)-\beta\Big{]}.$
(3)

The aim is to get these Q-factors even when we do not know the transition
probabilities, but have access to a black box which can generate random
variables according to the above transition probabilities.

###  II-B SSP Q-learning

Recall the stochastic shortest path problem. Let $S=S_{0}\cup T$ with
$S_{0}\cap T=\phi$ and $i_{0}\in T$. The objective is to minimize

$E\Big{[}\sum_{n=1}^{\tau-1}k(X_{n},Z_{n})+h(X_{\tau})\Big{]}$

where $h:S\times U\mapsto\mathcal{R}$ is the terminal cost and
$\tau:=\min\\{n\geq 0:X_{n}\in T\\}$. Under our assumtions, $\tau<\infty$
a.s., in fact $E[\tau]<\infty$. The dynamic programming equation to solve this
problem is given by

$\displaystyle V(i)=\min_{u}\big{[}k(i,u)+\sum_{j\in S}p(j|i,u)V(j)\big{]}]\
\forall\ i\in S_{0},$ $\displaystyle V(i)=h(i)\ \forall\ i\in T.$

Coming back to average cost problem, SSP Q-learning is based on the
observation that the average cost under any stationary policy is simply the
ratio of the expected total cost and the expected time, between two successive
visits to the reference state $i_{0}$. This connection was exploited by [4] to
convert the average cost problem into a stochastic shortest path (SSP)
problem. Consider a family of SSP problem parameterized by $\lambda$, with the
cost given by $k(i,u)-\lambda$ for $k$ as above and some scalar $\lambda$.
Then the dynamic programming equation for the above SSP problem is

$\displaystyle V(i)=\min_{u}\big{[}k(i,u)+\sum_{j\in S,j\neq
i_{0}}p(j|i,u)V(j)-\lambda\big{]},$ (4a) $\displaystyle V(i_{0})=0.$ (4b)

For each fixed policy, the cost is linear in $\lambda$ with negative slope.
Thus $V(\cdot)$, being the lower envelope thereof, is piecewise linear with
finitely many linear pieces and concave decreasing in $\lambda$ for each
component. When we replace $\lambda$ by $\beta$ and force $V(i_{0})=0$, we
recover (2). This suggests the coupled iterations

$\displaystyle V_{k+1}(i)=\min_{u}\big{[}k(i,u)+\sum_{j\in S,j\neq
i_{0}}p(j|i,u)V_{k}(j)-\lambda_{k}\big{]},$ (5a)
$\displaystyle\lambda_{k+1}=\lambda_{k}+a(n)V_{k}(i_{0}).$ (5b)

The SSP Q-learning scheme for the above problem is [2]

$\displaystyle
Q_{n+1}(i,u)=Q_{n}(i,u)+a(n)I\\{X_{n}=i,Z_{n}=u\\}\big{(}k(i,u)$
$\displaystyle+\ \min_{v}Q_{n}(X_{n+1},v)I\\{X_{n+1}\neq
i_{0}\\}-\lambda_{n}-Q_{n}(i,u)\big{)},$ (6a)
$\displaystyle\lambda_{n+1}=\Gamma(\lambda_{n}+a^{\prime}(n)\min_{v}Q_{n}(i_{0},v)).$
(6b)

Here $\Gamma(\cdot)$ is a projection operator onto the interval $[-g,g]$ with
$g$ chosen so as to satisfy $\beta\in(-g,g)$. Although this assumes some prior
knowledge of $\beta$, that can be obtained by a bound on $k(\cdot,\cdot)$.
This also ensures that (14) below holds. We rewrite the above equations as
follows

$\displaystyle
Q_{n+1}(i,u)=Q_{n}(i,u)+a(n)[F^{i,u}(Q_{n},(X_{n},Z_{n}),\lambda_{n})$
$\displaystyle-Q_{n}(i,u)+M^{i,u}_{n+1}(Q_{n})],$ (7a)
$\displaystyle\lambda_{n+1}=\Gamma(\lambda_{n}+a^{\prime}(n)f(Q_{n})),$ (7b)

and

$\displaystyle
F^{i,u}(Q_{n},(X_{n},Z_{n}),\lambda_{n})=I\\{X_{n}=i,Z_{n}=u\\}\big{(}k(i,u)$
$\displaystyle+\sum_{j\neq
i_{0}}p(j|i,u)\min_{v}Q_{n}(j,v)-\lambda_{n}\big{)},$ $\displaystyle
M^{i,u}_{n+1}(Q_{n})=I\\{X_{n}=i,Z_{n}=u\\}\big{(}\min_{v}Q_{n}(X_{n+1},v)\times$
$\displaystyle I\\{X_{n+1}\neq i_{0}\\}-\sum_{j\neq
i_{0}}p(j|i,u)\min_{v}Q_{n}(j,v)\big{)},$ $\displaystyle
f(Q)=\min_{u}Q(i_{0},u).$

As observed in [7], the map $F(\cdot,\cdot,\lambda)$ is a contraction for a
fixed $\lambda$ under a certain weighted max-norm

$\|x\|:=\max|w_{i}x_{i}|,\ x\in\mathcal{R}^{d},$

for an appropriate weight vector $w=[w_{1},...,w_{d}]$, $w_{i}>0$.

##  III Main Result

We state our main theorem in this section, after setting up the notation and
assumptions. The assumptions are specifically geared for the SSP Q-learning
applications in Section II-B, as will become apparent.

Consider the coupled iteration

$\displaystyle
x_{n+1}=x_{n}+a(n)\big{(}F(x_{n},Y_{n},\lambda_{n})-x_{n}+M_{n+1}(x_{n})\big{)},$
(8)
$\displaystyle\lambda_{n+1}=\Gamma(\lambda_{n}+a^{\prime}(n)f(x_{n})),n\geq 0$
(9)

for
$x_{n}=[x_{n}(1),...,x_{n}(d)]^{T}\in\mathcal{R}^{d},\lambda_{n}\in\mathcal{R}$.
Here:

  * •

$\\{Y_{n}\\}$ is the ‘Markov noise’ taking values in a finite state space $S$,
i.e.,

$\displaystyle P(Y_{n+1}|Y_{m},x_{m},m\leq n)$ $\displaystyle=$ $\displaystyle
P(Y_{n+1}|Y_{n},x_{n})$ $\displaystyle=$ $\displaystyle
p_{x_{n}}(Y_{n+1}|Y_{n}),\ n\geq 0,$

where for each $w$, $p_{w}(\cdot|\cdot)$ is the transition probability of an
irreducible Markov chain on $S$ with unique stationary distribution $\pi_{w}$.
We assume that the map $w\mapsto p_{w}(j|i)$ is Lipschitz, i.e., for some
$L_{1}>0$,

$\sum_{j\in S}|p_{w}(j|i)-p_{v}(j|i)|\leq L_{1}\|w-v\|,\ \forall i\in
S,w,v\in\mathcal{R}^{d}.$

By Cramer’s theorem, $\pi_{w}(i)$ is a rational function of $\\{p_{w}(j|k)\\}$
with a non-vaishing denominator, so the map $w\mapsto\pi_{w}(i)$ is similarly
Lipschitz, i.e., for some $L_{2}>0$,

$\sum_{i\in S}|\pi_{w}(i)-\pi_{v}(i)|\leq L_{2}\|w-v\|,\ \forall i\in
S,w,v\in\mathcal{R}^{d}.$

See Appendix B, [5] for some bounds on $L_{2}$.

  * •

$\\{M_{n}(x)\\}$ is, for each $x\in\mathcal{R}^{d}$, an
$\mathcal{R}^{d}$-valued martingale difference sequence parametrized by $x$,
with respect to the increasing family of $\sigma$-fields
$\mathcal{F}_{n}\coloneqq\sigma(x_{0},Y_{m},M_{m}(x),x\in\mathcal{R}^{d},m\leq
n)$, $n\geq 0$. That is,

$E[M_{n+1}(x)|\mathcal{F}_{n}]=\theta\>\ \mathrm{a.s.}\>\ \forall\;x,n,$ (10)

where $\theta$ is the zero vector. We also assume the componentwise bound: for
some $K_{0}>0$,

$|M_{n}^{\ell}(x)|\leq K_{0}(1+\|x\|)\>\textrm{a.s.}\>\forall\;x,n,l.$ (11)

  * •

$F(\cdot)=[F^{1}(\cdot),\cdots,F^{d}(\cdot)]^{T}:\mathcal{R}^{d}\times
S\rightarrow\mathcal{R}^{d}$ satisfies

$\displaystyle\|\sum_{i\in
S}\pi_{w}(i)(F(x,i,\lambda)-F(z,i,\lambda))\|\leq\alpha\|x-z\|,$
$\displaystyle\ \forall\ x,z,w\in\mathcal{R}^{d},\lambda\in\mathcal{R},$ (12)

for some $\alpha\in(0,1)$. By the contraction mapping theorem, this implies
that $\sum_{i}\pi_{w}(i)F(\cdot,i,\lambda)$ has a unique fixed point
$x^{*}_{w}(\lambda)\in\mathcal{R}^{d}$ (i.e.,
$\sum_{i}\pi_{w}(i)F(x^{*}_{w}(\lambda),i,\lambda)$ $=x^{*}_{w}(\lambda)$). We
assume that $x^{*}_{w}(\lambda)$ is independent of $w$, i.e., there exists a
$x^{*}(\cdot)$ such that

$\sum_{i\in S}\pi_{w}(i)F(x^{*}(\lambda),i,\lambda)=x^{*}(\lambda),\\\ \
\forall\;w\in\mathcal{R}^{d}.$ (13)

We also assume that the map $x\mapsto F^{\ell}(x,i,\lambda)$ is Lipschitz
(w.l.o.g., uniformly in $i$ and $\ell$). Let the common Lipschitz constant be
$L_{3}>0$, i.e.,

$|F^{\ell}(x,i,\lambda)-F^{\ell}(z,i,\lambda)|\leq L_{3}\|x-z\|,$ $\ \forall
i\in S,\ell\in\\{1,\cdots,d\\},x,z\in\mathcal{R}^{d}.$

We assume that $F$ is concave piecewise linear and decreasing in $\lambda$.
Furthermore, $\widetilde{F}_{n}(x,Y_{n},\lambda)\coloneqq
F(x,Y_{n},\lambda)+M_{n+1}(x)$ is assumed to satisfy

$\displaystyle\|\widetilde{F}_{n}(x,Y_{n},\lambda)\|\leq K+\alpha\|x\|\>\
\textrm{a.s.}.$ (14)

  * •

Moreover, we assume that $f(x^{*}(\lambda))$ is Lipschitz with Lipchitz
constant $L_{4}>0$: for all $\lambda_{1},\lambda_{2}\in\mathcal{R}$

$|f(x^{*}(\lambda_{1}))-f(x^{*}(\lambda_{2}))|\leq
L_{4}||x^{*}(\lambda_{1})-x^{*}(\lambda_{2})||.$ (15)

  * •

$a(n)\geq 0$ is a sequence of stepsizes satisfying

$a(n)\to 0,\ \sum_{n}a(n)=\infty,$ (16)

and is assumed to be eventually non-increasing, i.e., there exists $n^{*}\geq
1$ such that $a(n+1)\leq a(n)\ \forall\;n\geq n^{*}$. Since $a(n)\to 0$, there
exists $n^{\dagger}$ such that $a(n)<1$ for all $n>n^{\dagger}$.111Observe
that we do not require the classical square-summability condition in
stochastic approximation, viz., $\sum_{n}a(n)^{2}<\infty$. This is because the
contractive nature of our iterates gives us an additional handle on errors by
putting less weight on past errors. A similar effect was observed in [5]. We
further assume that $a(n)=\Omega(1/n)$. So, $a(n)\geq\frac{d_{1}}{n}$ for all
$n\geq n_{1}$ for some $n_{1}$ and $d_{1}>0$. We also assume that there exists
$0<d_{2}\leq 1$ such that
$a(n)=\mathcal{O}\left(\left(\frac{1}{n}\right)^{d_{2}}\right)$, i.e.,
$a(n)\leq d_{3}\left(\frac{1}{n}\right)^{d_{2}}$ for all $n\geq n_{2}$ for
some $n_{2}$ and $d_{3}>0$. Larger values of $d_{1}$ and $d_{2}$ and smaller
values of $d_{3}$ improve the main result presented below. The role this
assumption plays in our bounds will become clear later. Define
$N\coloneqq\max\\{n^{*},n^{\dagger},n_{1},n_{2}\\}$, i.e., $a(N)<1$, $a(n)$ is
non-increasing after $N$ and $\frac{d_{1}}{n}\leq a(n)\leq
d_{3}\left(\frac{1}{n}\right)^{d_{2}},\forall\ n\geq N$. Also, it is assumed
that the sequence $\epsilon(n)=\frac{a^{\prime}(n)}{a(n)}\to 0,$ i.e.,
$a^{\prime}(n)=o(a(n))$.

For $n\geq 0$, we further define:

$\displaystyle b_{k}(n)$ $\displaystyle=$ $\displaystyle\sum_{m=k}^{n}a(m),\
0\leq k\leq n<\infty,$ $\displaystyle b^{\prime}_{k}(n)$ $\displaystyle=$
$\displaystyle\sum_{m=k}^{n}a^{\prime}(m),\ 0\leq k\leq n<\infty,$
$\displaystyle\color[rgb]{0,0,0}\beta_{k}(n)$
$\displaystyle\color[rgb]{0,0,0}=$
$\displaystyle\color[rgb]{0,0,0}\begin{cases}\frac{1}{k^{d_{2}-d_{1}}n^{d_{1}}},&\text{if}\
d_{1}\leq d_{2}\\\ \frac{1}{n^{d_{2}}},&\text{otherwise},\end{cases}$
$\displaystyle\kappa(d)$ $\displaystyle=$ $\displaystyle\|\textbf{1}\|,\
\textbf{1}:=[1,1,\cdots,1]^{T}\in\mathcal{R}^{d},\ d\geq 1,$
$\displaystyle\bar{\epsilon}(n)$ $\displaystyle=$ $\displaystyle\sup_{m\geq
n}\epsilon(m).$

Our main result is a follows:

###### Theorem 1

(a) Let $n_{0}\geq N$. Then there exist finite positive constants $c_{1}$,
$c_{2}$, $c_{3}$ and $D$, depending on $\|x_{N}\|$, such that for $\delta>0$,
$n\geq n_{0}$ and
$C=e^{\kappa(d)(K_{0}(1+\|x_{N}\|+\frac{K}{1-\alpha})+c_{2})}$, the inequality

$\displaystyle\|x_{n}-x^{*}(\lambda_{n})\|\leq
e^{-(1-\alpha)b_{n_{0}}(n)}\|x_{n_{0}}-x^{*}(\lambda_{n_{0}})\|$
$\displaystyle+\frac{\delta+a(n_{0})c_{1}+\bar{\epsilon}(n_{0})c_{3}}{1-\alpha}$
(17)

holds with probability exceeding

$\displaystyle
1-2d\sum_{m=n_{0}+1}^{n}e^{-D\delta^{2}/\beta_{n_{0}}(m)},0<\delta\leq C,$
(18) $\displaystyle
1-2d\sum_{m=n_{0}+1}^{n}e^{-D\delta/\beta_{n_{0}}(m)},\delta>C$ (19)

(b) There exist finite constants $c_{4}$, $c_{5}$ and an $N^{\prime}\geq N$
large enough such that for $n\geq\hat{n}\geq N^{\prime}$, the inequality

$\displaystyle|\lambda_{n}-\beta|\leq|\lambda_{\hat{n}}-\beta|e^{-(1-\alpha)c_{4}b^{\prime}_{\hat{n}}(n)}$
$\displaystyle+c_{5}\Big{(}e^{-(1-\alpha)b_{\hat{n}}(n)}\|x_{\hat{n}}-x^{*}(\lambda_{\hat{n}})\|+\frac{\delta+a(\hat{n})c_{1}+\bar{\epsilon}(\hat{n})c_{3}}{1-\alpha}\Big{)}$
(20)

holds with probability exceeding

$\displaystyle
1-2d\sum_{m\geq\hat{n}+1}^{n}e^{-D\delta^{2}/\beta_{\hat{n}}(m)},0<\delta\leq
C,$ (21) $\displaystyle
1-2d\sum_{m\geq\hat{n}+1}^{n}e^{-D\delta/\beta_{\hat{n}}(m)},\delta>C$ (22)

##  IV Proof

We begin with a lemma adapted from [5].

###### Lemma 1

$\sup_{n\geq N}\|x_{n}\|\leq\|x_{N}\|+\frac{K}{1-\alpha},$ a.s.

###### Proof:

Using (14), we have

$\displaystyle\|x_{n+1}\|$ $\displaystyle=$
$\displaystyle\|(1-a(n))x_{n}+a(n)\widetilde{F}_{n}(x_{n},Y_{n},\lambda_{n})\|$
$\displaystyle\leq$ $\displaystyle(1-a(n))\|x_{n}\|+a(n)(K+\alpha\|x_{n}\|)$
$\displaystyle=$ $\displaystyle(1-(1-\alpha)a(n))\|x_{n}\|+a(n)K.$

For $n,m\geq N$, define
$\psi(n,m)\coloneqq\prod_{k=m}^{n-1}(1-(1-\alpha)a(k))$ if $n>m$ and $1$
otherwise. Note that, since $a(N)<1$, $0\leq\psi(n,m)\leq 1$ for all $n,m\geq
N$. Then

$\|x_{n+1}\|-\frac{K}{1-\alpha}\leq(1-(1-\alpha)a(n))\left(\|x_{n}\|-\frac{K}{1-\alpha}\right).$

Now
$\|x_{N}\|\leq\|x_{N}\|+\frac{K}{1-\alpha}=\psi(N,N)\|x_{K}\|+\frac{K}{1-\alpha}$.
Suppose

$\|x_{n}\|\leq\psi(n,N)\|x_{N}\|+\frac{K}{1-\alpha}$ (23)

for some $n\geq N$. Then,

$\displaystyle\|x_{n+1}\|-\frac{K}{1-\alpha}$ $\displaystyle\leq$
$\displaystyle(1-(1-\alpha)a(n))\Big{(}\psi(n,N)\|x_{N}\|$ $\displaystyle+$
$\displaystyle\frac{K}{1-\alpha}-\frac{K}{1-\alpha}\Big{)}$
$\displaystyle\leq$ $\displaystyle\psi(n+1,N)\|x_{N}\|$

By induction, (23) holds for all $n\geq N$, which completes the proof of Lemma
1. ∎

###  IV-A Concentration bound for the first iteration

Define $z_{n_{0}}=x_{n_{0}}$ and for $n>n_{0}$:

$\displaystyle z_{n+1}=z_{n}+a(n)\big{(}\sum_{i\in
S}\pi_{x_{n}}(i)F(z_{n},i,\lambda_{n})-z_{n}\big{)},$ (24)
$\displaystyle\lambda_{n+1}=\Gamma(\lambda_{n}+a^{\prime}(n)f(x_{n})),n\geq
0.$ (25)

We use the following theorem adapted from [5], which gives a concentration
inequality for the stochastic approximation algorithm with Markov noise.

###### Theorem 2

Let $n_{0}\geq N$. Then there exist finite constants $c_{1},c_{2},D>0$,
depending on $\|x_{N}\|$, such that for $\delta>0$, $n\geq n_{0}$ and
$C=e^{\kappa(d)(K_{0}(1+\|x_{N}\|+\frac{K}{1-\alpha})+c_{2})}$, the inequality

$\displaystyle\|x_{n}-z_{n}\|\leq\frac{\delta+a(n_{0})c_{1}}{1-\alpha},\ n\geq
n_{0},$ (26)

holds with probability exceeding

$\displaystyle
1-2d\sum_{m=n_{0}+1}^{n}e^{-D\delta^{2}/\beta_{n_{0}}(m)},0<\delta\leq C,$
(27) $\displaystyle
1-2d\sum_{m=n_{0}+1}^{n}e^{-D\delta/\beta_{n_{0}}(m)},\delta>C$ (28)

Since $F(x^{*}(\lambda_{n}),i,\lambda_{n}))=x^{*}(\lambda_{n})$, we have

$\displaystyle
z_{n+1}-x^{*}(\lambda_{n+1})=(1-a(n))(z_{n}-x^{*}(\lambda_{n}))$
$\displaystyle+a(n)\big{(}\sum_{i\in
S}\pi_{x_{n}}(i)(F(z_{n},i,\lambda_{n})-F(x^{*}(\lambda_{n}),i,\lambda_{n}))$
$\displaystyle+\frac{1}{a(n)}(x^{*}(\lambda_{n})-x^{*}(\lambda_{n+1}))\big{)}.$
(29)

Since the map $\lambda\to F$ is piecewise linear and concave decreasing, and
therefore so is the map $\lambda\to x^{*}(\lambda)$. By (• ‣ III) and (13), we
have the following lemma,

###### Lemma 2

$||x^{*}(\lambda_{n+1})-x^{*}(\lambda_{n})||\leq
L_{x}|\lambda_{n+1}-\lambda_{n}|$

###### Proof:

From the definition of $x^{*}(\cdot)$, we have

$\displaystyle\|x^{*}(\lambda_{n+1})-x^{*}(\lambda_{n})\|=\|\sum_{i\in
S}\pi(i)\big{(}F(x^{*}(\lambda_{n}),i,\lambda_{n})$
$\displaystyle-F(x^{*}(\lambda_{n+1}),i,\lambda_{n+1})\big{)}\|$

We have suppressed the subscript of $\pi$, which irrelevant by virtue of (13).
Let $e_{i}\in\mathcal{R}^{d}$ denote the standard basis vectors. Then the
r.h.s. in the above can be written as

$\displaystyle\|\sum_{i\in
S}\pi(i)\big{(}F(x^{*}(\lambda_{n}),i,\lambda_{n})-F(x^{*}(\lambda_{n+1}),i,\lambda_{n+1})\big{)}\|$
$\displaystyle=\|\sum_{i\in
S}\pi(i)\big{(}F(x^{*}(\lambda_{n}),i,\lambda_{n+1})-F(x^{*}(\lambda_{n+1}),i,\lambda_{n+1})$
$\displaystyle+e_{i}(\lambda_{n+1}-\lambda_{n})\big{)}\|$
$\displaystyle\leq\|\sum_{i\in
S}\pi(i)\big{(}F(x^{*}(\lambda_{n}),i,\lambda_{n+1})-F(x^{*}(\lambda_{n+1}),i,\lambda_{n+1})\big{)}\|$
$\displaystyle+\|\sum_{i\in
S}\pi(i)\big{(}e_{i}(\lambda_{n+1}-\lambda_{n})\big{)}\|$
$\displaystyle\leq\alpha\|x^{*}(\lambda_{n+1})-x^{*}(\lambda_{n})\|+|\lambda_{n+1}-\lambda_{n}|\|\sum_{i\in
S}\pi(i)e_{i}\|.$

Thus we finally have

$\displaystyle\|x^{*}(\lambda_{n+1})-x^{*}(\lambda_{n})\|\leq\alpha\|x^{*}(\lambda_{n+1})-x^{*}(\lambda_{n})\|$
$\displaystyle+|\lambda_{n+1}-\lambda_{n}|\|\sum_{i\in S}\pi(i)e_{i}\|$

which leads us to the claim that

$\displaystyle\|x^{*}(\lambda_{n+1})-x^{*}(\lambda_{n})\|\leq
L_{x}|\lambda_{n+1}-\lambda_{n}|$

where $L_{x}=\|\pi\|/(1-\alpha)$. ∎

To get a bound on $|\lambda_{n+1}-\lambda_{n}|$ we use the nonexpansive
property of the projection operator as follows

$\displaystyle|\lambda_{n+1}-\lambda_{n}|=|\Gamma(\lambda_{n}+a^{\prime}(n)f(x_{n}))-\Gamma(\lambda_{n})|$
$\displaystyle\leq|\lambda_{n}+a^{\prime}(n)f(x_{n})-\lambda_{n}|=a^{\prime}(n)|f(x_{n})|$

where we use the fact that $\Gamma(\lambda_{n})=\lambda_{n}$. Combining the
above inequalities, we get

$\|x^{*}(\lambda_{n+1})-x^{*}(\lambda_{n})\|\leq
L_{x}a^{\prime}(n)|f(x_{n})|.$ (30)

Thus,

$\displaystyle\|z_{n+1}-x^{*}(\lambda_{n+1})\|\leq\|(1-a(n))(z_{n}-x^{*}(\lambda_{n}))\|$
$\displaystyle+a(n)\big{(}\|\sum_{i\in
S}\pi_{x_{n}}(i)(F(z_{n},i,\lambda_{n})-F(x^{*}(\lambda_{n}),i,\lambda_{n}))\|$
$\displaystyle+\frac{1}{a(n)}\|(x^{*}(\lambda_{n})-x^{*}(\lambda_{n+1}))\|\big{)}$
$\displaystyle\leq(1-(1-\alpha)a(n))\|z_{n}-x^{*}(\lambda_{n})\|+a(n)\epsilon(n)L_{x}|f(x_{n})|.$
(31)

where $\epsilon(n)=\frac{a^{\prime}(n)}{a(n)}$. Since $x_{n}$ is bounded by
Lemma 1, $f(x_{n})\leq K^{*}<\infty$. Iterating (31) for $n_{0}\leq m\leq n$,
we get,

$\displaystyle\|z_{n+1}-x^{*}(\lambda_{n+1})\|\leq$
$\displaystyle\|x_{n_{0}}-x^{*}(\lambda_{n_{0}})\|\prod_{m=n_{0}}^{n}(1-(1-\alpha)a(m))$
$\displaystyle+K^{\prime}\sum_{m=n_{0}}^{n}\psi(n+1,m+1)a(m)\epsilon(m)$ (32)
$\displaystyle\leq
e^{-(1-\alpha)b_{n_{0}}(n)}\|x_{n_{0}}-x^{*}(\lambda_{n_{0}})\|$
$\displaystyle+K^{\prime}\sum_{m=n_{0}}^{n}\psi(n+1,m+1)a(m)\epsilon(m)$ (33)

where, $K^{\prime}=L_{x}K^{*}$ and $z_{n_{0}}=x_{n_{0}}$. The summation in
last term can be bounded as

$\displaystyle\sum_{m=n_{0}}^{n}\psi(n+1,m+1)a(m)\epsilon(m)$
$\displaystyle\leq\bar{\epsilon}(n_{0})\sum_{m=n_{0}}^{n}\psi(n+1,m+1)a(m),$
(34)

where $\bar{\epsilon}(n):=\sup_{m\geq n}\epsilon(m)$. Note that for any
$0<k<m$,

$\psi(m,k)+\psi(m,k+1)(1-\alpha)a(k)=\psi(m,k+1),$

and hence

$\frac{\psi(m+1,n_{0})}{1-\alpha}+\frac{1}{1-\alpha}\sum_{k={n_{0}}}^{m}\psi(m+1,k+1)(1-\alpha)a(k)=$
$\frac{\psi(m+1,m+1)}{1-\alpha}=\frac{1}{1-\alpha}.$

This implies that

$\sum_{k=n_{0}}^{m}\psi(m+1,k+1)a(k)\ \leq\ \frac{1}{1-\alpha}.$ (35)

Hence

$\sum_{m=n_{0}}^{n}\psi(n+1,m+1)a(m)\bar{\epsilon}(m)\ \leq\
\frac{\bar{\epsilon}(n_{0})}{1-\alpha}.$ (36)

Combining the above,

$\displaystyle\|z_{n+1}-x^{*}(\lambda_{n+1})\|$ $\displaystyle\leq$
$\displaystyle
e^{-(1-\alpha)b_{n_{0}}(n)}\|x_{n_{0}}-x^{*}(\lambda_{n_{0}})\|$ (37)
$\displaystyle+\ \frac{K^{\prime}\bar{\epsilon}(n_{0})}{1-\alpha}.$

Combining (37) with Theorem 2 yields Theorem 1(a).

###  IV-B Concentration bound for the second iteration

The second iteration is given by

$\lambda_{n+1}=\Gamma(\lambda_{n}+a^{\prime}(n)f(x)).$ (38)

Let $\xi_{n}=f(x_{n})-f(x^{*}(\lambda_{n}))$. Subtracting $\beta$ from both
sides, we get:

$\displaystyle\lambda_{n+1}-\beta=\Gamma(\lambda_{n}+a^{\prime}(n)f(x^{*}(\lambda_{n}))+$
$\displaystyle a^{\prime}(n)(f(x_{n})-f(x^{*}(\lambda_{n})))\big{)}-\beta$
$\displaystyle=\Gamma\big{(}\lambda_{n}+a^{\prime}(n)f(x^{*}(\lambda_{n}))+a^{\prime}(n)\xi_{n}\big{)}-\beta.$
(39)

Since the map $\lambda\to x^{*}(\lambda)$ is concave decreasing and piecewise
linear, we have for some finite constant $0<L_{5}\leq L_{6}$ such that

$\displaystyle-L_{6}(\lambda_{1}-\lambda_{2})\leq
f(x^{*}(\lambda_{1}))-f(x^{*}(\lambda_{2}))\leq-
L_{5}(\lambda_{1}-\lambda_{2})$

Replace $\lambda_{1}$ by $\lambda_{n}$ and $\lambda_{2}$ by $\beta$. Since
$f(x^{*}(\beta))=0$:

$\displaystyle-L_{6}(\lambda_{n}-\beta)\leq f(x^{*}(\lambda_{n}))\leq-
L_{5}(\lambda_{n}-\beta)$

Thus,

$\displaystyle\Gamma\big{(}\lambda_{n}-a^{\prime}(n)L_{6}(\lambda_{n}-\beta)+a^{\prime}(n)\xi_{n}\big{)}-\beta\leq\lambda_{n+1}-\beta\leq$
$\displaystyle\Gamma\big{(}\lambda_{n}-a^{\prime}(n)L_{5}(\lambda_{n}-\beta)+a^{\prime}(n)\xi_{n}\big{)}-\beta$
$\displaystyle|\lambda_{n+1}-\beta|\leq\max(|\Gamma\big{(}\lambda_{n}-a^{\prime}(n)L_{6}(\lambda_{n}-\beta)+a^{\prime}(n)\xi_{n}\big{)}$
$\displaystyle-\beta|,|\Gamma\big{(}\lambda_{n}-a^{\prime}(n)L_{5}(\lambda_{n}-\beta)+a^{\prime}(n)\xi_{n}\big{)}-\beta|)$
(40)

Using the fact that $\Gamma(\beta)=\beta$ along with the non-expansive
property of $\Gamma(\cdot)$, we have:

$\displaystyle|\lambda_{n+1}-\beta|\leq\max(|(1-a^{\prime}(n)L_{6})(\lambda_{n}-\beta)+a^{\prime}(n)\xi_{n}|,$
$\displaystyle|(1-a^{\prime}(n))L_{5}(\lambda_{n}-\beta)+a^{\prime}(n)\xi_{n}|$

For some $\hat{n}\geq N$ such that $a^{\prime}(n)L_{6}<1\ \forall\
n\geq\hat{n}$,

$\displaystyle|\lambda_{n+1}-\beta|\leq\max(|(1-a^{\prime}(n)L_{6})|\lambda_{n}-\beta|+a^{\prime}(n)|\xi_{n}|,$
$\displaystyle|(1-a^{\prime}(n)L_{5})|\lambda_{n}-\beta|+a^{\prime}(n)|\xi_{n}|)$
$\displaystyle\leq(1-a^{\prime}(n)L_{5})|\lambda_{n}-\beta|+a^{\prime}(n)|\xi_{n}|,\
n\geq\hat{n}.$

Iterating the above inequality for $\hat{n}\leq m\leq n$, we get:

$\displaystyle|\lambda_{n+1}-\beta|\leq|\lambda_{\hat{n}}-\beta|\prod_{m=\hat{n}}^{n}(1-a^{\prime}(m)L_{5}))$
$\displaystyle+\sum_{m=\hat{n}}^{n}\big{(}\prod_{k=m+1}^{n}(1-L_{5}a^{\prime}(k))\big{)}a^{\prime}(m)|\xi_{m}|.$
(41)

Notice that

$|\xi_{m}|=|f(x_{m})-f(x^{*}(\lambda_{m}))|\leq
L_{4}\|x_{m}-x^{*}(\lambda_{m})\|.$

Using this and the first part of the proof we can bound each $|\xi_{m}|$ with
a term similar to r.h.s. of Theorem 1(a). Using the same analysis as used for
deriving (35), one can verify that

$\sum_{m=\hat{n}}^{n}\big{(}\prod_{k=m+1}^{n}(1-L_{5}a^{\prime}(k))\big{)}a^{\prime}(m)\leq\frac{1}{L_{5}}.$

This leads us to

$\displaystyle|\lambda_{n+1}-\beta|\leq|\lambda_{\hat{n}}-\beta|e^{-(1-\alpha)L_{5}b^{\prime}_{\hat{n}}(n)}$
$\displaystyle+\frac{L_{4}}{L_{5}}\Big{(}e^{-(1-\alpha)b_{\hat{n}}(n)}\|x_{\hat{n}}-x^{*}(\lambda_{\hat{n}})\|+\frac{\delta+a(\hat{n})c_{1}+\bar{\epsilon}(\hat{n})c_{3}}{1-\alpha}\Big{)}$
(42)

holds with probability exceeding

$\displaystyle
1-2d\sum_{m\geq\hat{n}+1}^{n}e^{-D\delta^{2}/\beta_{\hat{n}}(m)},0<\delta\leq
c,$ (43) $\displaystyle
1-2d\sum_{m\geq\hat{n}+1}^{n}e^{-D\delta/\beta_{\hat{n}}(m)},\delta>c$ (44)

where we applied union bound to get the probability. This completes the proof
of Theorem 1(b).

##  V Comparison with RVI Q-learning and Simulation Results

(a) 20 states, 5 actions.

(b) 20 states, 5 actions.

Figure 1: Squared Error vs number of iterations

###  V-A RVI Q-learning

The algorithm for RVI Q-learning is given by [2]

$\displaystyle Q_{n+1}(i,u)$ $\displaystyle=$ $\displaystyle
k(i,u)+\sum_{j\in\mathcal{S}}p(j|i,u)\min_{v}Q_{n}(j,v)$ (45) $\displaystyle-
Q_{n}(i_{0},u_{0})$

with $i_{0}\in S$, $u_{0}\in A$ prescribed. The purpose of subtracting the
scalar “offset” $Q_{n}(i_{0},u_{0})$ from each component on the r.h.s. of (45)
is to keep the iterations stable—recall that $Q(\cdot,\cdot)$ is specified
anyway only up to an additive constant. It turns out that
$Q(i_{0},u_{0})\to\beta$. The asynchronous RVI Q-learning algorithm is

$\displaystyle
Q_{n+1}(i,u)=Q_{n}(i,u)+a(n)I\\{X_{n}=i,Z_{n}=u\\}\big{(}k(i,u)$
$\displaystyle+\min_{v}Q_{n}(X_{n+1},v)-Q_{n}(i_{0},u_{0})-Q_{n}(i,u)\big{)}.$
(46)

Under some additional conditions such as aperiodicity and comparably frequent
updates of all components, the above converges to a unique $Q(\cdot,\cdot)$
with $Q(i_{0},u_{0})=\beta$ [2].

###  V-B Simulation experiments

We took two controlled Markov chains with 20 states and 5 actions in each
state as examples. Fig. 1(a) corresponds to the first, while Fig. 1(b)
corresponds to the second. We wanted Markov chains which are irreducible under
any policy and the easiest way to generate such a chain is to generate a
random transition matrix with each element drawn randomly from the interval
$[0,1]$ with a high probability, and then normalize the rows. For the second
example, after getting the random matrix, we changed 50% of the entries to $0$
except the entries corresponding to $p(i|0,u)$ and $p(0|i,u)$ for all
$i\in\mathcal{S}$, $u\in\mathcal{U}$, and then normalized the rows. This
yielded an irreducible matrix for the two examples. For running both
algorithms, we used the same step size of
$a(n)=\frac{1}{\lceil{\frac{n}{2}\rceil}^{0.65}}$ and
$a^{\prime}(1.5|\mathcal{S}||\mathcal{U}|n)=\frac{1}{\lceil{\frac{5000+n}{1.5|\mathcal{S}||\mathcal{U}|}\rceil}^{0.65}\log(\lceil{\frac{5000+n}{1.5|\mathcal{S}||\mathcal{U}|}\rceil})}$,
with $\lambda_{n}$ not being updated for $n$ that are not multiples of
$1.5|\mathcal{S}||\mathcal{U}|$. The reason for choosing these step sizes was
relatively fast rate of convergence for both algorithms and less noisy and
clear plots.

Since we had the access to the transition matrices, we first obtained the
actual value of the desired $Q^{*}$ for each algorithm using value iteration.
Then we ran the asynchronous version of both algorithms and stored the
$l_{2}$-norm error relative to this $Q^{*}$. While explicit contractiveness of
the SSP scheme with respect to a certain norm (as opposed to non-expansiveness
of RVI) might lead us to expect better convergence for SSP, the preliminary
experiments reported here indicate otherwise. RVI was quick to converge,
whereas SSP had initially oscillatory behaviour which died down after some
time and it caught up with RVI. This appears to be due to the high sensitivity
of $f(Q_{n})$ to $\lambda$ which is updated on a slower time scale. However,
this effect is significantly subdued in the second example. These and another
set of similar examples (not reported here) suggest that if the graph of the
MDP is well-connected, suggesting rapid mixing under a stationary policy, it
favours RVI over SSP and this advantage diminishes as the connectivity becomes
sparser. This, however, needs more extensive experiments and theoretical
study.

A further future research direction is to combine either scheme with suitable
function approximation.

## References

  * [1] C. J. C. H. Watkins, “Learning from delayed rewards,” Ph.D. dissertation, King’s College, Cambridge, UK, May 1989. [Online]. Available: http://www.cs.rhul.ac.uk/~chrisw/new˙thesis.pdf
  * [2] J. Abounadi, D. Bertsekas, and V. S. Borkar, “Learning algorithms for markov decision processes with average cost,” _SIAM Journal on Control and Optimization_ , pp. 681–698, 2001.
  * [3] M. L. Puterman, _Markov decision processes: discrete stochastic dynamic programming_. John Wiley & Sons, 2014\.
  * [4] D. P. Bertsekas, “A new value iteration method for the average cost dynamic programming problem,” _SIAM J. Control Optim._ , vol. 36, no. 2, p. 742–759, mar 1998. [Online]. Available: https://doi.org/10.1137/S0363012995291609
  * [5] V. S. B. Siddharth Chandak and P. Dodhia, “Concentration of contractive stochastic approximation and reinforcement learning,” _CoRR_ , vol. abs/2106.14308, 2021. [Online]. Available: https://arxiv.org/abs/2106.14308
  * [6] S. Zhang, Z. Zhang, and S. T. Maguluri, “Finite sample analysis of average-reward td learning and q-learning,” in _Advances in Neural Information Processing Systems_ , M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., vol. 34. Curran Associates, Inc., 2021, pp. 1230–1242. [Online]. Available: https://proceedings.neurips.cc/paper/2021/file/096ffc299200f51751b08da6d865ae95-Paper.pdf
  * [7] J. Tsitsiklis, “Asynchronous stochastic approximation and Q-learning,” LIDS Res. Cent., MIT, Tech. Rep., 1993. [Online]. Available: http://www.springerlink.com/index/QX335286076X3566.pdf