# Regularized Q-learning

Han-Dong Lim1
<EMAIL_ADDRESS>Do Wan Kim2
<EMAIL_ADDRESS>Donghwan Lee1
<EMAIL_ADDRESS>
(1Department of Electrical Engineering, KAIST, Daejeon, 34141, South Korea
2Department of Electrical Engineering, Hanbat National University
)

###### Abstract

Q-learning is widely used algorithm in reinforcement learning community. Under
the lookup table setting, its convergence is well established. However, its
behavior is known to be unstable with the linear function approximation case.
This paper develops a new Q-learning algorithm that converges when linear
function approximation is used. We prove that simply adding an appropriate
regularization term ensures convergence of the algorithm. We prove its
stability using a recent analysis tool based on switching system models.
Moreover, we experimentally show that it converges in environments where
Q-learning with linear function approximation has known to diverge. We also
provide an error bound on the solution where the algorithm converges.

##  1 Introduction

Recently, reinforcement learning has shown great success in various fields.
For instance, Mnih et al., 2015 achieved human level performance in several
video games in the Atari benchmark (Bellemare et al., 2013). Since then,
researches on deep reinforcement learning algorithms have shown significant
progresses (Lan et al., 2020; Chen et al., 2021). For example, Badia et al.,
2020 performs better than standard human performance in all 57 Atari games.
Schrittwieser et al., 2020 solves Go, chess, Shogi, and Atari without prior
knowledge about the rules. Although great success has been achieved in
practice, there is still gap between theory and the practical success.
Especially when off-policy, function approximation, and bootstrapping are used
together, the algorithm may diverge or show unstable behaviors. This
phenomenon is called the deadly triad (Sutton & Barto, 2018). Famous counter-
examples are given in Baird, 1995; Tsitsiklis & Van Roy, 1997.

For policy evaluation, especially for temporal-difference (TD) learning
algorithm, there has been several algorithms to resolve the deadly triad
issue. Bradtke & Barto, 1996 uses least-squares method to compute fixed point
of TD-learning algorithm, but suffers from $O(h^{2})$ time complexity, where
$h$ is number of features. Maei, 2011; Sutton et al., 2009 developed gradient
descent based methods which minimize the mean square projected Bellman error.
Ghiassian et al., 2020 added regularization term to TD Correction (TDC)
algorithm, which uses single time scale step-size. Lee et al., 2021 introduced
several variants of the gradient TD (GTD) algorithm under control theoretic
frameworks. Sutton et al., 2016 re-weights some states to match on-policy
distribution to stabilize the off-policy TD-learning. Diddigi et al., 2019
uses $l_{2}$ regularization to propose a new convergent off-policy TD-learning
algorithm.

First presented by Watkins & Dayan, 1992, Q-learning also suffers from
divergence issues under the deadly triad. While there are convergence results
under the look-up table setting (Watkins & Dayan, 1992; Jaakkola et al., 1994;
Borkar & Meyn, 2000; Lee & He, 2019), even with simple linear function
approximation, the convergence is only guaranteed under strong assumptions
(Melo et al., 2008; Lee & He, 2019; Yang & Wang, 2019). Melo et al., 2008
adopts an assumption that the behavior policy and target policy are similar
enough to guarantee convergence, which is not practical in general. Lee & He,
2019 assumes a strong assumption to ensure the convergence with the so-called
switching system approach. Yang & Wang, 2019 has a stringent assumption on
anchor state-action pairs. There are few works, Agarwal et al., 2021; Carvalho
et al., 2020; Zhang et al., 2021; Maei et al., 2010, that guarantee
convergence under more general assumptions.

The main goal of this paper is to propose a practical Q-learning algorithm
that guarantees convergence under linear function approximation. We prove its
convergence using the ordinary differential equation (O.D.E) analysis
framework (Borkar & Meyn, 2000) together with the switching system approach
developed in Lee & He, 2019. As in Lee & He, 2019, we construct upper and
lower comparison systems, and prove its global asymptotic stability based on
switching system theories. Compared to the standard Q-learning (Watkins &
Dayan, 1992), the only difference is the additional $l_{2}$ regularization
term, which makes the algorithm relavently simple. Compared to the previous
works (Carvalho et al., 2020; Maei et al., 2010), our algorithm is single
time-scale, and hence, shows faster convergence rates experimentally. Our
algorithm directly uses bootstrapping rather than circumventing the issue in
the deadly triad. Therefore, it could give a new insight into training
reinforcement learning algorithms without using the so-called target network
technique introduced in Mnih et al., 2015. The main contributions of this
paper are summarized as follows:

  1. 1.

A new single time-scale Q-learning algorithm with linear function
approximation is proposed.

  2. 2.

We prove the convergence of the proposed algorithm based on the O.D.E.
approach together with the switching system model in Lee & He, 2019.

  3. 3.

We experimentally show that our algorithm performs faster than other two time-
scale Q-learning algorithms (Carvalho et al., 2020; Maei et al., 2010).

Related works are summarized as follows: Motivated by the empirical success of
the deep Q-learning in Mnih et al., 2015, recent works in Zhang et al., 2021;
Carvalho et al., 2020; Agarwal et al., 2021 use the target network to
circumvent the bootstrapping issue and guarantees convergence. Carvalho et
al., 2020 uses a two time-scale learning method, and has a strong assumption
on the boundedness of the feature matrix. Zhang et al., 2021 used $l_{2}$
regularization with the target network, while a projection step is involved,
which makes it difficult to implement practically. Moreover, it also uses a
two time-scale learning method. Agarwal et al., 2021 additionally uses the so-
called experience replay technique with the target network, and also has a
strong assumption on the boundedness of the feature matrix. Furthermore, the
optimality is only guaranteed under a specific type of Markov Decision
Process. Maei et al., 2010 suggested the so-called Greedy-GQ (gradient
Q-learning) algorithm, but due to non-convexity of the objective function, it
could converge to a local optima.

##  2 Preliminaries and Notations

###  2.1 Markov Decision Process

We consider an infinite horizon Markov Decision Process (MDP), which consists
of a tuple $\mathcal{M}=(\mathcal{S},\mathcal{A},P,r,\gamma)$, where the state
space $\mathcal{S}$ and action space $\mathcal{A}$ are finite sets,
$P(s^{\prime}|s,a)$ denotes the transition model,
$r:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}$ is the
reward, and $\gamma\in(0,1)$ is the discount factor. Given a stochastic policy
$\pi:\mathcal{S}\rightarrow\mathcal{P}(\mathcal{A})$, where
$\mathcal{P}(\mathcal{A})$ is the set of probability distributions over
$\mathcal{A}$, agent at the current state $s_{k}$ selects an action
$a_{k}\sim\pi(\cdot|s_{k})$, then the agent’s state changes to the next state
$s_{k+1}\sim P(\cdot|s_{k},a_{k})$, and receives reward
$r_{k+1}:=r(s_{k},a_{k},s_{k+1})$. A deterministic policy is a special
stochastic policy, which can be defined simply as a mapping $\pi:{\cal
S}\to{\cal A}$, which maps a state to an action.

The objective of the Markov decision problem (MDP) is to find a deterministic
optimal policy, denoted by $\pi^{*}$, such that the cumulative discounted
rewards over infinite time horizons is maximized, i.e.,

$\displaystyle\pi^{*}:=\operatorname*{arg\,max}_{\pi}{\mathbb{E}}\left[\left.\sum_{k=0}^{\infty}{\gamma^{k}r_{k}}\right|\pi\right],$

where $(s_{0},a_{0},s_{1},a_{1},\ldots)$ is a state-action trajectory
generated by the Markov chain under policy $\pi$, and
${\mathbb{E}}[\cdot|\pi]$ is an expectation conditioned on the policy $\pi$.

The Q-function under policy $\pi$ is defined as

$\displaystyle
Q^{\pi}(s,a)={\mathbb{E}}\left[\left.\sum_{k=0}^{\infty}{\gamma^{k}r_{k}}\right|s_{0}=s,a_{0}=a,\pi\right],$
$\displaystyle s\in{\cal S},a\in{\cal A},$

and the optimal Q-function is defined as $Q^{*}(s,a)=Q^{\pi^{*}}(s,a)$ for all
$s\in{\cal S},a\in{\cal A}$. Once $Q^{*}$ is known, then an optimal policy can
be retrieved by the greedy action, i.e.,
$\pi^{*}(s)=\operatorname*{arg\,max}_{a\in{\cal A}}Q^{*}(s,a)$. Throughout, we
assume that the MDP is ergodic so that the stationary state distribution
exists and the Markov decision problem is well posed.

It is known that the optimal Q-function satisfies the so-called Bellman
equation expressed as follows:

$\displaystyle Q^{*}(s,a)$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[r_{k+1}+\max_{a_{k+1}\in\mathcal{A}}\gamma
Q^{*}(s_{k+1},s_{k+1})|s_{k}=s,a_{k}=a\right]$ $\displaystyle:=$
$\displaystyle{\mathcal{T}}Q^{*}$ (1)

where ${\mathcal{T}}$ is called the Bellman operator.

###  2.2 Notations

In this paper, we will use an O.D.E. model of Q-learning to analyze its
convergence. To this end, it is useful to introduce some notations in order to
simplify the overall expressions. Throughout the paper, $e_{a}$ and $e_{s}$
denote $a$-th and $s$-th canonical basis vectors in
$\mathbb{R}^{|\mathcal{A}|}$ and $\mathbb{R}^{|\mathcal{S}|}$, respectively.
Moreover, $\otimes$ stands for the Kronecker product. Let us introduce the
following notations:

$\displaystyle P:=$ $\displaystyle\begin{bmatrix}P_{1}\\\ \vdots\\\ P_{|{\cal
A}|}\\\ \end{bmatrix}\in{\mathbb{R}}^{|{\cal S}||{\cal A}|\times|{\cal
S}|},\quad R:=\begin{bmatrix}R_{1}\\\ \vdots\\\ R_{|{\cal A}|}\\\
\end{bmatrix}\in{\mathbb{R}}^{|{\cal S}||{\cal A}|},$ $\displaystyle Q:=$
$\displaystyle\begin{bmatrix}Q_{1}\\\ \vdots\\\ Q_{|{\cal A}|}\\\
\end{bmatrix}\in{\mathbb{R}}^{|{\cal S}||{\cal A}|},$ $\displaystyle D_{a}:=$
$\displaystyle\begin{bmatrix}d(1,a)&&\\\ &\ddots&\\\ &&d(|{\cal S}|,a)\\\
\end{bmatrix}\in{\mathbb{R}}^{|{\cal S}|\times|{\cal S}|},$ $\displaystyle
D:=$ $\displaystyle\begin{bmatrix}D_{1}&&\\\ &\ddots&\\\ &&D_{|{\cal
A}|}\end{bmatrix}\in{\mathbb{R}}^{|{\cal S}||{\cal A}|\times|{\cal S}||{\cal
A}|},$

where $P_{a}\in\mathbb{R}^{|{\cal S}|\times|{\cal S}|},a\in{\cal A}$ is the
state transition matrix whose $i$-th row and $j$-th column component denotes
the probability of transition to state $j$ when action $a$ is taken at state
$i$, $P^{\pi}\in\mathbb{R}^{|{\cal S}||{\cal A}|\times|{\cal S}||{\cal A}|}$
represents the state-action transition matrix under policy $\pi$, i.e.,

$\displaystyle(e_{s}\otimes e_{a})^{T}P^{\pi}(e_{s^{\prime}}\otimes
e_{a^{\prime}})$ $\displaystyle=$
$\displaystyle{\mathbb{P}}[s_{k+1}=s^{\prime},a_{k+1}=a^{\prime}|s_{k}=s,a_{k}=a,\pi],$

$Q_{a}=Q(\cdot,a)\in{\mathbb{R}}^{|{\cal S}|},a\in{\cal A}$ and
$R_{a}(s):={\mathbb{E}}[r(s,a,s^{\prime})|s,a],s\in{\cal S}$. Moreover,
$d(\cdot,\cdot)$ is the state-action visit distribution, where i.i.d random
variables $\\{(s_{k},a_{k})\\}_{k=0}^{\infty}$ are sampled, i.e.,

$d(s,a)={\mathbb{P}}[s_{k}=s,a_{k}=a],\quad\forall a\in{\cal A},s\in{\cal S}.$

With a slight abuse of notation, $d$ will be also used to denote the vector
$d\in{\mathbb{R}}^{|{\cal S}||{\cal A}|}$ such that

$d^{T}(e_{s}\otimes e_{a})=d(s,a),\quad\forall s\in{\cal S},a\in{\cal A}.$

In this paper, we represent a policy in a matrix form in order to formulate a
switching system model. In particular, for a given policy $\pi$, define the
matrix

$\displaystyle\Pi^{\pi}:=\begin{bmatrix}e_{\pi(1)}\otimes e_{1}\\\ \vdots\\\
e_{\pi(|\mathcal{S}|)}\otimes e_{|\mathcal{S}|}\\\
\end{bmatrix}\in\mathbb{R}^{|{\mathcal{S}}|\times|{\mathcal{S}}||{\mathcal{A}}|}.$
(2)

Then, we can prove that for any deterministic policy, $\pi$, we have

$\displaystyle\Pi^{\pi}Q=\begin{bmatrix}{Q(1,\pi(1))}\\\ {Q(2,\pi(2))}\\\
\vdots\\\ {Q(|{\cal S}|,\pi(|{\cal S}|))}\\\ \end{bmatrix}.$

For simplicity, let $\Pi_{Q}:=\Pi^{\pi}$ for $Q\in\mathbb{R}^{|\cal S||\cal
A|}$.

Moreover, we can prove that for any deterministic policy $\pi$,
$P^{\pi}=P\Pi^{\pi}\in\operatorname{\mathbb{R}}^{|\operatorname{\mathcal{S}}||\operatorname{\mathcal{A}}|\times|\operatorname{\mathcal{S}}||\operatorname{\mathcal{A}}|}$.
Using the notations introduced, the Bellman equation in (1) can be compactly
written as

$\displaystyle Q^{*}=\gamma P\Pi_{Q^{*}}Q^{*}+R=:{\cal T}Q^{*},$

where $\pi_{Q^{*}}$ is the greedy policy defined as
$\pi_{Q^{*}}(s)=\operatorname*{arg\,max}_{a\in\mathcal{A}}Q^{*}(s,a)$.

###  2.3 Q-learning with linear function approximation

Q-learning is widely used model-free learning to find $Q^{*}$, whose updates
are given as

$\displaystyle Q_{k+1}(s_{k},a_{k})\leftarrow
Q_{k}(s_{k},a_{k})+\alpha_{k}\delta_{k},$ (3)

where

$\delta_{k}=r_{k+1}+\gamma\max_{a\in\mathcal{A}}Q_{k}(s_{k+1},a)-Q_{k}(s_{k},a_{k})$

is called the TD error. Each update uses an i.i.d. sample
$(s_{k},a_{k},r_{k},s_{k+1})$, where $(s_{k},a_{k})$ is sampled from a state-
action distribution $d(\cdot,\cdot)$.

Here, we assume that the step-size is chosen to satisfy the so-called the
Robbins-Monro condition

$\displaystyle\alpha_{k}>0,\quad\sum\limits^{\infty}_{k=0}\alpha_{k}=\infty,\quad\sum\limits^{\infty}_{k=0}\alpha_{k}^{2}<\infty.$
(4)

When the state-space and action-space are too large, then the memory and
computational complexities usually become intractable. In such cases, function
approximation is commonly used to approximate Q-function, (Mnih et al., 2015;
Schrittwieser et al., 2020; Hessel et al., 2018; Lan et al., 2020). Linear
function approximation is the simplest function approximation approach. In
particular, we use the feature matrix
$X\in\operatorname{\mathbb{R}}^{|\operatorname{\mathcal{S}}||\operatorname{\mathcal{A}}|\times
h}$ and parameter vector $\theta\in\mathbb{R}^{h}$ to approximate the
Q-function, i.e., $Q\simeq X\theta$, where the feature matrix is expressed as

$\displaystyle X:=\begin{bmatrix}x^{T}(1,1)\\\ \vdots\\\
x^{T}(1,|\mathcal{A}|)\\\ \vdots\\\
x^{T}(|\mathcal{S}|,|\mathcal{A}|)\end{bmatrix}\in\operatorname{\mathbb{R}}^{|\operatorname{\mathcal{S}}||\operatorname{\mathcal{A}}|\times
h}.$

Here, $x(\cdot.\cdot)\in\mathbb{R}^{h}$ is called the feature vector, and $h$
is a positive integer with $h<\\!\\!<|{\cal S}|$. The corresponding greedy
policy becomes

$\displaystyle\pi_{X\theta}(s)=\operatorname*{arg\,max}_{a\in\mathcal{A}}x^{T}(s,a)\theta.$
(5)

Next, we summarize some assumptions adapted throughout this paper.

######  Assumption 2.1.

The state-action visit distribution is positive, i.e., $d(s,a)>0$ for all
$s\in\mathcal{S},a\in\mathcal{A}$.

######  Assumption 2.2.

The feature matrix, $X$, has full column rank, and is a non-negative matrix.
Moreover, columns of $X$ are orthogonal.

######  Assumption 2.3 (Boundedness on feature matrix and reward matrix).

There exists constants, $X_{\max}>0$ and $R_{\max}>0$, such that

$\displaystyle\max(||X||_{\infty},||X^{T}||_{\infty})$
$\displaystyle<X_{\max},$ $\displaystyle||R||_{\infty}$
$\displaystyle<R_{\max}.$

Note that 2.2 and 2.3 are commonly adopted in the literature, e.g. Carvalho et
al. (2020); Melo et al. (2008); Lee & He (2019). Moreover, under 2.1, $D$ is a
nonsingular diagonal matrix with strictly positive diagonal elements.

######  Lemma 2.4.

(Gosavi, 2006) Under 2.3, the optimal Q-function, $Q^{*}$, is bounded as
follows:

$\displaystyle||Q^{*}||_{\infty}\leq\frac{R_{\max}}{1-\gamma}$ (6)

The proof of Lemma 2.4 comes from the fact that under the discounted infinite
horizon setting, $Q^{*}$ can be expressed as an infinite sum of geometric
sequence.

######  Remark 2.5.

Carvalho et al., 2020; Agarwal et al., 2021 assume $||x(s,a)||_{\infty}\leq 1$
for all $(s,a)\in\mathcal{S}\times\mathcal{A}$. Moreover, Zhang et al. 2021
requires specific bounds on the feature matrix which is dependent on various
factors e.g. projection radius and transition matrix . On the other hand, our
feature matrix can be chosen arbitrarily large regardless of those factors.

###  2.4 O.D.E. Analysis

The dynamic system framework has been widely used to show convergence of
reinforcement learning algorithms, e.g., Sutton et al. 2009; Maei et al. 2010;
Borkar & Meyn 2000; Lee & He 2019; Carvalho et al. 2020; Lee et al. 2021.
Especially, Borkar & Meyn, 2000 is one of the most widely used techniques to
show stability of stochastic approximation using O.D.E analysis. Consider the
following stochastic approximation with a non-linear mapping
$f:\operatorname{\mathbb{R}}^{n}\rightarrow\operatorname{\mathbb{R}}^{n}$,

$\displaystyle\theta_{k+1}=f(\theta_{k})+m_{k},\quad$ (7)

where $m_{k}\in\operatorname{\mathbb{R}}^{n}$ is an i.i.d. noise vector. For
completeness, results in Borkar & Meyn, 2000 are briefly summarized in the
sequel. First of all, some assumptions to guarantee the convergence are listed
below.

######  Assumption 2.6.

1\. The mapping
$f:\operatorname{\mathbb{R}}^{n}\rightarrow\operatorname{\mathbb{R}}^{n}$ is
globally Lipschitz continuous, and there exists a function
$f_{\infty}:\operatorname{\mathbb{R}}^{n}\rightarrow\operatorname{\mathbb{R}}^{n}$
such that

$\lim_{c\rightarrow\infty}\frac{f(cx)}{c}=f_{\infty}(x),\quad\forall{x}\in\operatorname{\mathbb{R}}^{n}.$
(8)

2\. The origin in $\operatorname{\mathbb{R}}^{n}$ is an asymptotically stable
equilibrium for the ODE $\dot{x}_{t}=f_{\infty}(x_{t})$.

3\. There exists a unique globally asymptotically stable equilibrium
$\theta^{e}\in\mathbb{R}^{n}$ for the ODE $\dot{x}_{t}=f(x_{t})$ , i.e.,
$x_{t}\rightarrow\theta^{e}$ as $t\rightarrow\infty$.

4\. The sequence $\\{m,k\geq 1\\}$ where $\operatorname{\mathcal{G}}_{k}$ is
sigma-alebra generated by $\\{(\theta_{i},m_{i},i\geq k)\\}$, is a Martingale
difference sequence. In addition , there exists a constant $C_{0}<\infty$ such
that for any initial $\theta_{0}\in\operatorname{\mathbb{R}}^{n}$ , we have
$\operatorname{\mathbb{E}}[||m_{k+1}||^{2}|\operatorname{\mathcal{G}}_{k}]\leq
C_{0}(1+||\theta_{k}||^{2},\forall{k}\geq 0)$.

5\. The step-sizes satisfies the Robbins-Monro condition in (4).

Under the above assumptions, we now introduce Borkar and Meyn theorem below.

######  Lemma 2.7 (Borkar and Meyn theorem).

Suppose that 2.6 holds, and consider the stochastic algorithm in (7). Then,
for any initial $\theta_{0}\in\operatorname{\mathbb{R}}^{n}$, $\sup_{k\geq
0}||\theta_{k}||<\infty$ with probability one. In addition ,
$\theta_{k}\rightarrow\theta^{e}$ as $k\rightarrow\infty$ with probability
one.

The main idea of Borkar and Meyn theorem is as follows: iterations of a
stochastic recursive algorithm follow the solution of its corresponding O.D.E.
in the limit when the step-size satisfies the Robbins-Monro condition.
Therefore, by proving the asymptotic stability of the O.D.E., we can induce
the convergence of the original algorithm. In this paper, we will use an
O.D.E. model of Q-learning, which is expressed as a special nonlinear system
called a switching system. In the next section, basic concepts in switching
system theory are briefly introduced.

###  2.5 Switching System

In this paper, we will consider a particular nonlinear system, called the
_switched linear system_ (Liberzon, 2003),

$\displaystyle\frac{d}{dt}x_{t}=A_{\sigma_{t}}x_{t},\quad
x_{0}=z\in{\mathbb{R}}^{n},\quad t\in{\mathbb{R}}_{+},$ (9)

where $x_{t}\in{\mathbb{R}}^{n}$ is the state,
$\sigma\in{\mathcal{M}}:=\\{1,2,\ldots,M\\}$ is called the mode,
$\sigma_{t}\in{\mathcal{M}}$ is called the switching signal, and
$\\{A_{\sigma},\sigma\in{\mathcal{M}}\\}$ are called the subsystem matrices.
The switching signal can be either arbitrary or controlled by the user under a
certain switching policy. Especially, a state-feedback switching policy is
denoted by $\sigma(x_{t})$.

Stability and stabilization of (9) have been widely studied for decades.
Still, finding a practical and effective condition for them is known to be a
challenging open problem. For example, contrary to linear time-invariant
systems, even if each subsystem matrix $A_{\sigma}$ is Hurwitz, the overall
switching system may not be stable in general. This tells us that tools in
linear system theories cannot be directly applied to conclude the stability of
the switching system.

Another approach is to use the Lyapunov theory (Khalil, 2002). From standard
results in control system theories, finding a Lyapunov function ensures
stability of the switching system. In this paper, we prove that if the
switching system consists of negative definite matrices, then we can always
find a common quadratic Lyapunov function and ensure its stability.

######  Proposition 2.8.

Consider the switching system (9), and assume that each subsystem matrix,
$A_{\sigma}$, is negative definite for all $\sigma\in\\{1,\dots,M\\}$. Then,
(9) is globally asymptotically stable.

We will use this fact to prove the convergence of the proposed algorithm. In
particular, the proposed Q-learning algorithm can be modelled as a switching
system, whose subsystem matrices are all negative definite.

##  3 Projected Bellman equation

In this section, we introduce the notion of projected Bellman equation with a
regularization term, and establish connections between it and the proposed
algorithm. Moreover, we briefly discuss the existence and uniqueness of the
projected Bellman equation. We will also provide an example to illustrate the
existence and uniqueness.

When using the linear function approximation, since the true action value may
not lie in the subspace spanned by the feature vectors, a solution of the
Bellman equation may not exist in general. To resolve this issue, a standard
approach is to consider the projected Bellman equation defined as

$\displaystyle X\theta^{*}=\Gamma{\mathcal{T}}X\theta^{*},$ (10)

where $\Gamma:=X(X^{T}DX)^{-1}X^{T}D$ is the weighted Euclidean Projection
with respect to state-action visit distribution onto the subspace spanned by
the feature vectors, and ${\cal T}X\theta^{*}=\gamma
P\Pi_{X\theta^{*}}X\theta^{*}+R$. In this case, there is more chances for a
solution satisfying the above projected Bellman equation to exist. Still,
there may exist cases where the projected Bellman equation does not admit a
solution. We will give an example of such case in Section 3.

To proceed, let us rewrite (10) equivalently as

$\displaystyle X\theta^{*}=$ $\displaystyle X(X^{T}DX)^{-1}X^{T}D(\gamma
P\Pi_{X\theta^{*}}X\theta^{*}+R)$ $\displaystyle\Leftrightarrow$
$\displaystyle X^{T}DX\theta^{*}$ $\displaystyle=$ $\displaystyle
X^{T}DX(X^{T}DX)^{-1}X^{T}D(\gamma P\Pi_{X\theta^{*}}X\theta^{*}+R)$
$\displaystyle\Leftrightarrow$ $\displaystyle\underbrace{(X^{T}DX-\gamma
X^{T}DP\Pi_{X\theta^{*}}X)}_{A_{\pi_{X\theta^{*}}}}\theta^{*}=\underbrace{X^{T}DR}_{b},$

where we use the simplified notations

$\displaystyle A_{\pi_{X\theta^{*}}}:=X^{T}DX-\gamma
X^{T}DP\Pi_{X\theta^{*}}X,\quad b=X^{T}DR.$

Therefore, the projected Bellman equation in (10) can be equivalently written
as the nonlinear equation

$\displaystyle b-A_{\pi_{X\theta^{*}}}\theta^{*}=0.$ (11)

A potential deterministic algorithm to solve the above equation is

$\displaystyle\theta_{k+1}=\theta_{k}+\alpha_{k}(b-A_{\pi_{X\theta_{k}}}\theta_{k}).$
(12)

If it converges, i.e., $\theta_{k}\to\theta^{*}$ as $k\to\infty$, then it is
clear that $\theta^{*}$ solves (11). In this paper, the proposed algorithm is
a stochastic algorithm that solves the modified equation

$\displaystyle b-(A_{\pi_{X\theta_{e}}}+\eta C)\theta_{e}=0,$ (13)

where $C:=X^{T}DX$, and $\eta\geq 0$ is a weight on the regularization term.
Similar to (12), the corresponding deterministic algorithm is

$\displaystyle\theta_{k+1}=\theta_{k}+\alpha_{k}(b-(A_{\pi_{X\theta_{k}}}+\eta
C)\theta_{k}).$ (14)

If it converges, i.e., $\theta_{k}\to\theta_{e}$ as $k\to\infty$, then it is
clear that $\theta_{e}$ solves (13). Some natural questions that arise here
are as follows: Which conditions can determine the existence and uniqueness of
the equations in (11) and (13). Partial answers are given in the sequel.

Considering the non-existence of fixed point of (10) (De Farias & Van Roy,
2000), both (11) and (13) may not also have a solution. However, for the
modified Bellman equation in (13), we can prove that under appropriate
conditions, its solution exists and is unique.

######  Lemma 3.1.

When $\eta>||(X^{T}DX)^{-1}||_{\infty}X_{\max}^{2}-1$, a solution of (13)
exists and is unique.

The proof is given in Section A.3 of the supplemental material, and uses
Banach fixed-point theorem (Agarwal et al., 2018). It follows similar proof
(Melo, 2001) to establish the existence and uniqueness of solution of (1).
From Lemma 3.1, we can see that when the weight $\eta$ is sufficiently large,
the existence and uniqueness of the solution is guaranteed.

Note that even if a solution satisfying (13) exists, $X\theta_{e}$ may be
different from the optimal Q-function, $Q^{*}$. However, we can derive a bound
on the error, $X\theta_{e}-Q^{*}$, using some algebraic inequalities and
contraction property of Bellman operator, which is presented below.

######  Lemma 3.2.

Assume that a solution of (13) exists. When
$\eta>\gamma||\Gamma||_{\infty}-1$, we have the following bound:

$\displaystyle||X\theta_{e}-Q^{*}||_{\infty}\leq$
$\displaystyle\frac{1}{1+\eta-\gamma||\Gamma||_{\infty}}||Q^{*}-\Gamma
Q^{*}||_{\infty}$
$\displaystyle+\frac{\eta}{1+\eta-\gamma||\Gamma||_{\infty}}\frac{R_{\max}}{1-\gamma}$

where $\Gamma=X(X^{T}DX)^{-1}DX$ is the projection operator.

Some remarks are in order for Lemma 3.2. First of all,
$\eta>\gamma||\Gamma||_{\infty}-1$ ensures that the error is always bounded.
The first term represents the error incurred by the difference between the
optimal $Q^{*}$ and $Q^{*}$ projected onto the feature space. Therefore, this
error is induced by the linear function approximation. The second term
represents the error potentially induced by the regularization. For instance,
if $1>\gamma||\Gamma||_{\infty}$, then the second error term vanishes as
$\eta\to 0$. Finally, note that as $\eta\to\infty$, the first error term
vanishes. This means that the error by the regularization dominates the error
induced by the linear function approximation.

We now provide an example where the solution does not exist for (11) but does
exist for (13).

######  Example 3.3.

Let us define a MDP whose state transition diagram is given as in Figure 1.
The cardinality of state space and action space are $|{\cal S}|=3$, $|{\cal
A}|=2$ respectively.

Figure 1: State transition diagram

The corresponding state transition matrix, and other parameters are given as
follows:

$\displaystyle X$ $\displaystyle=\begin{bmatrix}0.01&0\\\ 0.1&0\\\ 0&0.01\\\
0&0.01\\\ 0.1&0\\\ 0&0.01\end{bmatrix},\;R_{1}=\begin{bmatrix}-2\\\ 0\\\
0\end{bmatrix},\;R_{2}=\begin{bmatrix}1\\\ 0\\\ 0\end{bmatrix},$
$\displaystyle P_{1}$ $\displaystyle=\begin{bmatrix}0&1&0\\\
\frac{1}{4}&\frac{1}{4}&\frac{1}{2}\\\ \frac{1}{4}&\frac{1}{2}&\frac{1}{4}\\\
\end{bmatrix},\;P_{2}=\begin{bmatrix}0&0&1\\\
\frac{1}{4}&\frac{1}{4}&\frac{1}{2}\\\
\frac{1}{4}&\frac{1}{2}&\frac{1}{4}\end{bmatrix},\;$ $\displaystyle\gamma$
$\displaystyle=0.99,\quad d(s,a)=\frac{1}{6},\;\forall s\in{\cal S},\forall
a\in{\cal A}$

where the order of elements of each column follows the orders of the
corresponding definitions. Note that for this Markov decision process, taking
action $a=1$ and action $a=2$ at state $s=2$ have the same transition
probabilities and reward. It is similar for the state $s=3$. In this MDP,
there are only two deterministic policies available, denoted by $\pi_{1}$ and
$\pi_{2}$, that selects action $a=1$ and action $a=2$ at state $s=1$,
respectively, i.e., $\pi_{1}(1)=1$ and $\pi_{2}(1)=2$. The actions at state
$s=2$ and $s=3$ do not affect the overall results.

The motivation of this MDP is as follows. Substitute $\pi_{X\theta^{*}}$ in
(11) with $\pi_{1}$ and $\pi_{2}$. Then each of its solution becomes

$\displaystyle\theta^{e1}$ $\displaystyle:=\begin{bmatrix}\theta^{e1}_{1}\\\
\theta^{e1}_{2}\end{bmatrix}\approx\begin{bmatrix}-6\\\
111\end{bmatrix}\in\mathbb{R}^{2},$ $\displaystyle\theta^{e2}$
$\displaystyle:=\begin{bmatrix}\theta^{e2}_{1}\\\
\theta^{e2}_{2}\end{bmatrix}\approx\begin{bmatrix}-496\\\
-4715\end{bmatrix}\in\mathbb{R}^{2}$

respectively. If $\pi_{1}$ is the corresponding policy to the solution of
(11), it means that action $a=1$ is greedily selected at state $s=1$.
Therefore, $Q^{\pi_{1}}(1,1)>Q^{\pi_{1}}(1,2)$ should be satisfied. However,
since $Q^{\pi_{1}}(1,1)=x(1,1)^{T}\theta^{e1}=-0.06$ and
$Q^{\pi_{1}}(1,2)=x(1,2)^{T}\theta^{e1}\approx 1.11$, this is contradiction.
The same logic applies to the case for $\pi_{2}$. Therefore, neither of them
becomes a solution of (11). On the other hand, considering (13) with
$\eta=1.98$ which satisfies (18), the solution for each policy becomes
$\theta^{e1}_{1}\approx 0.13,\theta^{e1}_{2}\approx 13$ and
$\theta^{e2}_{1}\approx 0.02,\theta^{e2}_{2}\approx 14$ respectively. For
$\pi_{1}$ and $\pi_{2}$, we have $Q^{\pi_{1}}(1,1)<Q^{\pi_{2}}(1,2)$ and
$Q^{\pi_{1}}(1,1)<Q^{\pi_{1}}(1,2)$ respectively. Hence, $\theta^{e2}$
satisfies (13) and becomes the unique solution.

##  4 Algorithm

In this section, we will introduce our main algorithm, and elaborate the
condition on the regularization term to make the algorithm convergent. The
proposed algorithm is motivated by TD-learning. In particular, for on-policy
TD-learning, one can establish its convergence using the property of the
stationary distribution. On the other hand, for an off-policy case, the
mismatch between the sampling distribution and the stationary distribution
could cause its divergence (Sutton et al., 2016). To address this problem,
Diddigi et al., 2019 adds a regularization term to TD-learning in order to
make it convergent. Since Q-learning can be interpreted as an off-policy TD-
learning, we add a regularization term to Q-learning update motivated by
Diddigi et al., 2019. This modification leads to the proposed algorithm as
follows:

$\displaystyle\theta_{k+1}=\theta_{k}+\alpha_{k}(x(s_{k},a_{k})\delta_{k}+\eta
x(s_{k},a_{k})x(s_{k},a_{k})^{T}\theta_{k})$ (15)

Note that letting $\eta=0$, the above update is reduced to the standard
Q-learning with linear function approximation in (3). The proposed algorithm
is different from Diddigi et al., 2019 in the sense that a regularization term
is applied to Q-learning instead of TD-learning.

Rewriting the stochastic update in a deterministic manner, it can be written
as follows:

$\displaystyle\theta_{k+1}=\theta_{k}+\alpha_{k}(b-(A_{\pi_{X\theta_{k}}}+\eta
C)\theta_{k}+m_{k+1}),$ (16)

where

$\displaystyle m_{k+1}$ $\displaystyle=\delta_{k}x(s_{k},a_{k})+\eta
x(s_{k},a_{k})^{T}x(s_{k},a_{k})\theta_{k}$ (17)
$\displaystyle-(b-(A_{\pi_{X\theta_{k}}}+\eta C)\theta_{k})$

is an i.i.d. noise. Note that without the noise, (16) is reduced to the
deterministic version in (14).

In our convergence analysis, we will apply the O.D.E. approach, and in this
case, $A_{\pi_{X\theta_{k}}}+\eta C$ will determine the stability of the
corresponding O.D.E. model, and hence, convergence of (15). Note that (16) can
be interpreted as a switching system defined in (9) with stochastic noises. As
mentioned earlier, proving the stability of a general switching system is
challenging in general. However, we will use Proposition 2.8 to prove its
asymptotic stability. In particular, we can make $A_{\pi_{X\theta_{k}}}+\eta
C$ to be negative definite under the following condition:

$\eta>\max_{\pi\in\Theta,s\in{\cal S},a\in{\cal A}}\frac{\gamma
d^{T}P^{\pi}(e_{a}\otimes e_{s})}{2d(s,a)}-\frac{2-\gamma}{2}$ (18)

where $\Theta$ is the set of all deterministic policies, and $\otimes$ is the
Kronecker product. Lemma A.2, given in Section A.2 of the supplemental
material, is similar to Theorem 2 in Diddigi et al., 2019, and ensures such a
property. Now, we can use Proposition 2.8 to establish stability of the
overall system.

Building on the negative definiteness of the $A_{\pi_{X\theta_{k}}}+\eta C$,
in the next section, we prove that under the stochastic update (15), we have
$\theta_{k}\rightarrow\theta_{e}$ as $k\to\infty$ with probability one, where
$\theta_{e}$ satisfies the projected Bellman equation in (13). If $\eta=0$
satisfies (18), we can guarantee convergence to an optimal policy without
errors.

##  5 Convergence Analysis

Recently, Lee & He, 2019 suggested a switching system framework to prove the
stability of Q-learning in the linear function approximation cases. However,
its assumption seems too stringent to check in practice. Here, we develop more
practical Q-learning algorithm by adding appropriately a preconditioned
regularization term. We prove the stability of the proposed Q-learning with
regularization term (15) following lines similar to Lee & He, 2019.

Our proof mainly relies on Borkar Meyn theorem. Therefore, we first discuss
about the corresponding O.D.E. for the proposed update in (15), which is

$\displaystyle\dot{\theta}_{t}$
$\displaystyle=-(1+\eta)X^{T}DX\theta_{t}+\gamma
X^{T}DP\Pi_{X\theta_{t}}X\theta_{t}+X^{T}DR$ (19)
$\displaystyle:=f(\theta_{t}).$

Then, using changes of coordinates, the above O.D.E. can be rewritten as

$\displaystyle\frac{d}{dt}(\theta_{t}-\theta_{e})$ (20)
$\displaystyle=(-(1+\eta)X^{T}DX+\gamma
X^{T}DP\Pi_{X\theta_{t}}X)(\theta_{t}-\theta_{e})$ $\displaystyle+\gamma
X^{T}DP\Pi_{X\theta_{t}}X\theta_{e}-\gamma
X^{T}DP\Pi_{X\theta_{e}}X\theta_{e},$

where $\theta_{e}$ satisfies (13). Here, we assume that the equilibrium point
exists and is unique. We later prove that if the equilibrium exists, then it
is unique.

To apply Borkar Meyn theorem, we discuss about the asymptotic stability of the
O.D.E. in (20), and check conditions of 2.6 in Section A.5 of the supplemental
material.

Note that (20) includes an affine term, i.e., it cannot be expressed as a
matrix times $\theta_{t}-\theta_{e}$. Establishing asymptotic stability of
switched linear system with affine term is difficult compared to switched
linear system (20). To circumvent this difficulty, Lee & He, 2019 proposed
upper and lower systems, which upper bounds and lower bounds the original
system, respectively using the so-called vector comparison principle. Then,
the stability of the original system can be established by proving the
stability of the upper and lower systems, which are easier to analyze.
Following similar lines, to check global asymptotic stability of the original
system, we also introduce upper and lower systems, which upper bounds and
lower bounds the original system, respectively. Then, we prove global
asymptotic stability of the two bounding systems. Since upper and lower
systems can be viewed as switched linear system and linear system,
respectively, the global asymptotic stability is easier to prove. We stress
that although the switching system approach in Lee & He, 2019 is applied in
this paper, the detailed proof is entirely different, and is nontrivial. In
particular, the upper and lower systems are given as follows:

$\displaystyle\frac{d}{dt}\theta^{u}_{t}$
$\displaystyle=(-(1+\eta)X^{T}DX+\gamma
X^{T}DP\Pi_{X\theta^{u}_{t}}X)\theta^{u}_{t},$
$\displaystyle\frac{d}{dt}\theta^{l}_{t}$
$\displaystyle=-((1+\eta)X^{T}DX\theta^{l}_{t}+\gamma
X^{T}DP\Pi_{X\theta_{e}}X)\theta^{l}_{t},$

where $\theta^{u}_{t}$ denotes the state of the upper system, and
$\theta^{l}_{t}$ stands for the state of the lower system. We defer the
detailed construction of each system to Section A.6 of the supplemental
material. Establishing stability of upper and lower system gives the stability
of overall system.

######  Theorem 5.1.

Suppose that

  1. 1.

2.2 holds

  2. 2.

(18) holds

  3. 3.

a solution of (13) exists

Then, the solution is unique, and the origin is the unique globally
asymptotically stable equilibrium point of (20).

The detailed proof is given in Section A.6 of the supplemental material.

Building on previous results, we now use Borkar and Meyn’s theorem Lemma 2.7
to establish the convergence of regularized Q-learning algorithm.

######  Theorem 5.2.

Assume Robbins-Monro step-size, and (18). Then under 2.2 and 2.3, under the
stochastic update (15), $\theta_{k}\rightarrow\theta_{e}$ as $k\to\infty$ with
probability one, where $\theta_{e}$ satisfies (13).

The full proof is given in Section A.7 of the supplemental material.

##  6 Experiments

In this section, we present experimental results under well-known environments
(Tsitsiklis & Van Roy, 1996; Baird, 1995) where Q-learning with linear
function approximation diverges. We also show trajectories of upper and lower
systems to illustrate the theoretical results.

###  6.1 $\theta\rightarrow 2\theta$ (Tsitsiklis & Van Roy, 1996)

Even when there are only two states, Q-learning with linear function
approximation could diverge (Tsitsiklis & Van Roy, 1996). Depicted in Figure
4(a) in Section A.8.1 of the supplemental material, from state one ($\theta$),
the transition is deterministic to absorbing state two ($2\theta$), and reward
is zero at every time steps. Therefore, the episode length is fixed to be two.
Learning rate for Greedy GQ (GGQ) and Coupled Q Learning (CQL) are set as
$0.05$ and $0.25$, respectively as in Carvalho et al., 2020; Maei et al.,
2010. Since CQL requires normalized feature values, we scaled the feature
value with $\frac{1}{2}$ as in Carvalho et al., 2020, and initialized weights
as one. We implemented Q-learning with target network (Zhang et al., 2021)
without projection for practical reason (Qtarget). We set the learning rate as
$0.25$ and $0.05$ respectively, and the weight $\eta$ as two. For the
regularized Q-learning, we set the learning rate as $0.25$, and the weight
$\eta$ as two. It is averaged over $100$ runs. In Figure 2, we can see that
the regularized Q-learning achieves the fastest convergence rate.

Figure 2: Comparison with other algorithms in $\theta\rightarrow 2\theta$

###  6.2 Baird Seven Star Counter Example (Baird, 1995)

Baird, 1995 considers an overparameterized example, where Q-learning with
linear function approximation diverges. The overall state transition is
depicted in Figure 4(b) given in Section A.8.1 of the supplemental material.
There are seven states and two actions for each state, which are solid and
dash action. The number of features are $h=15$. At each episode, it is
initialized at random state with uniform probability. Solid action leads to
seventh state while dashed action makes transition uniformly random to states
other than seventh state. At seventh state, the episode ends with probability
$\frac{1}{100}$. The behavior policy selects dashed action with probability
$\frac{5}{6}$, and solid action with probability $\frac{1}{6}$. Since CQL
(Carvalho et al., 2020) converges under normalized feature values, we scaled
the feature matrix with $\frac{1}{\sqrt{5}}$. The weights are set as one
except for $\theta_{7}=2$. The learning rates and the weight $\eta$ are set as
same as the previous experiment.

Figure 3: Comparison with other algorithms in Baird seven star counter example

As in Figure 3, Qtarget shows the fastest convergence but to guarantee
convergence, it requires projection twice theoretically, which is not
implemented in this experiment. Our algorithm shows fastest convergence
compared to other two time scale algorithm, CQL and GGQ.

###  6.3 O.D.E. Experiment

Let us consider an MDP with $|{\cal S}|=2,|{\cal A}|=2$, and the following
parameters

$\displaystyle X$ $\displaystyle=\begin{bmatrix}1&0\\\ 0&2\\\ 1&0\\\
0&2\end{bmatrix},\quad D=\begin{bmatrix}\frac{1}{4}&0&0&0\\\
0&\frac{1}{4}&0&0\\\ 0&0&\frac{1}{4}&0\\\ 0&0&0&\frac{1}{4}\end{bmatrix}$
$\displaystyle P_{1}$ $\displaystyle=\begin{bmatrix}0.5&0.5\\\ 1&0\\\
\end{bmatrix},P_{2}=\begin{bmatrix}0.5&0.5\\\ 0.25&0.75\end{bmatrix},$
$\displaystyle R_{1}$ $\displaystyle=\begin{bmatrix}1\\\
1\end{bmatrix},R_{2}=\begin{bmatrix}1\\\ 1\end{bmatrix},\quad\gamma=0.99$

For this MDP, we will illustrate trajectories of the upper and lower system.
Each state action pair is sampled uniformly random and reward is one for every
time step. $\eta=2.25$ is chosen to satisfy conditions of Theorem 5.1. From
Figure 5 in Section A.8.2 of the supplemental material, we can see that the
trajectory of the original system is bounded by the trajectories of lower and
upper system.

##  7 Conclusion

In this paper, we presented a new convergent Q-learning with linear function
approximation, which is simple to implement. We provided theoretical analysis
on the proposed Q-learning algorithm with regularization term, and
demonstrated its performance on several experiments, where the original
Q-learning with linear function approximation diverges. Developing a new
Q-learning algorithm with linear function approximation without bias would be
one interesting future research topic. Moreover, considering the great success
of deep learning, it would be interesting to develop deep reinforcement
learning algorithms with appropriately preconditioned regularization term
instead of using the target network.

## References

  * Agarwal et al. (2021) Agarwal, N., Chaudhuri, S., Jain, P., Nagaraj, D., and Netrapalli, P.  Online target q-learning with reverse experience replay: Efficiently finding the optimal policy for linear mdps.  _arXiv preprint arXiv:2110.08440_ , 2021.
  * Agarwal et al. (2018) Agarwal, P., Jleli, M., and Samet, B.  Fixed point theory in metric spaces.  _Recent Advances and Applications_ , 2018.
  * Badia et al. (2020) Badia, A. P., Piot, B., Kapturowski, S., Sprechmann, P., Vitvitskyi, A., Guo, Z. D., and Blundell, C.  Agent57: Outperforming the atari human benchmark.  In _International Conference on Machine Learning_ , pp. 507–517. PMLR, 2020.
  * Baird (1995) Baird, L.  Residual algorithms: Reinforcement learning with function approximation.  In _Machine Learning Proceedings 1995_ , pp. 30–37. Elsevier, 1995\.
  * Bellemare et al. (2013) Bellemare, M. G., Naddaf, Y., Veness, J., and Bowling, M.  The arcade learning environment: An evaluation platform for general agents.  _Journal of Artificial Intelligence Research_ , 47:253–279, 2013.
  * Borkar & Meyn (2000) Borkar, V. S. and Meyn, S. P.  The ode method for convergence of stochastic approximation and reinforcement learning.  _SIAM Journal on Control and Optimization_ , 38(2):447–469, 2000.
  * Bradtke & Barto (1996) Bradtke, S. J. and Barto, A. G.  Linear least-squares algorithms for temporal difference learning.  _Machine learning_ , 22(1):33–57, 1996.
  * Carvalho et al. (2020) Carvalho, D., Melo, F. S., and Santos, P.  A new convergent variant of q-learning with linear function approximation.  _Advances in Neural Information Processing Systems_ , 33:19412–19421, 2020.
  * Chen et al. (2021) Chen, X., Wang, C., Zhou, Z., and Ross, K.  Randomized ensembled double q-learning: Learning fast without a model.  _arXiv preprint arXiv:2101.05982_ , 2021.
  * De Farias & Van Roy (2000) De Farias, D. P. and Van Roy, B.  On the existence of fixed points for approximate value iteration and temporal-difference learning.  _Journal of Optimization theory and Applications_ , 105(3):589–608, 2000.
  * Diddigi et al. (2019) Diddigi, R. B., Kamanchi, C., and Bhatnagar, S.  A convergent off-policy temporal difference algorithm.  _arXiv preprint arXiv:1911.05697_ , 2019.
  * Ghiassian et al. (2020) Ghiassian, S., Patterson, A., Garg, S., Gupta, D., White, A., and White, M.  Gradient temporal-difference learning with regularized corrections.  In _International Conference on Machine Learning_ , pp. 3524–3534. PMLR, 2020.
  * Gosavi (2006) Gosavi, A.  Boundedness of iterates in q-learning.  _Systems & control letters_, 55(4):347–349, 2006.
  * Hessel et al. (2018) Hessel, M., Modayil, J., Van Hasselt, H., Schaul, T., Ostrovski, G., Dabney, W., Horgan, D., Piot, B., Azar, M., and Silver, D.  Rainbow: Combining improvements in deep reinforcement learning.  In _Thirty-second AAAI conference on artificial intelligence_ , 2018\.
  * Hirsch & Smith (2006) Hirsch, M. W. and Smith, H.  Monotone dynamical systems.  In _Handbook of differential equations: ordinary differential equations_ , volume 2, pp. 239–357. Elsevier, 2006.
  * Horn & Johnson (2013) Horn, R. and Johnson, C.  Matrix analysis second edition, 2013.
  * Jaakkola et al. (1994) Jaakkola, T., Jordan, M. I., and Singh, S. P.  On the convergence of stochastic iterative dynamic programming algorithms.  _Neural computation_ , 6(6):1185–1201, 1994.
  * Khalil (2002) Khalil, H. K.  _Nonlinear systems; 3rd ed._ Prentice-Hall, Upper Saddle River, NJ, 2002.  URL https://cds.cern.ch/record/1173048.  The book can be consulted by contacting: PH-AID: Wallet, Lionel.
  * Lan et al. (2020) Lan, Q., Pan, Y., Fyshe, A., and White, M.  Maxmin q-learning: Controlling the estimation bias of q-learning.  _arXiv preprint arXiv:2002.06487_ , 2020.
  * Lee & He (2019) Lee, D. and He, N.  A unified switching system perspective and ode analysis of q-learning algorithms.  _arXiv preprint arXiv:1912.02270_ , 2019.
  * Lee et al. (2021) Lee, D., Lim, H.-D., Park, J., and Choi, O.  Versions of gradient temporal difference learning.  _arXiv preprint arXiv:2109.04033_ , 2021.
  * Liberzon (2003) Liberzon, D.  _Switching in systems and control_.  Springer Science & Business Media, 2003.
  * Maei (2011) Maei, H. R.  Gradient temporal-difference learning algorithms.  2011\.
  * Maei et al. (2010) Maei, H. R., Szepesvári, C., Bhatnagar, S., and Sutton, R. S.  Toward off-policy learning control with function approximation.  In _ICML_ , 2010.
  * Melo (2001) Melo, F. S.  Convergence of q-learning: A simple proof.  _Institute Of Systems and Robotics, Tech. Rep_ , pp. 1–4, 2001\.
  * Melo et al. (2008) Melo, F. S., Meyn, S. P., and Ribeiro, M. I.  An analysis of reinforcement learning with function approximation.  In _Proceedings of the 25th international conference on Machine learning_ , pp. 664–671, 2008.
  * Mnih et al. (2015) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al.  Human-level control through deep reinforcement learning.  _nature_ , 518(7540):529–533, 2015.
  * Schrittwieser et al. (2020) Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., et al.  Mastering atari, go, chess and shogi by planning with a learned model.  _Nature_ , 588(7839):604–609, 2020.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Sutton et al. (2009) Sutton, R. S., Maei, H. R., Precup, D., Bhatnagar, S., Silver, D., Szepesvári, C., and Wiewiora, E.  Fast gradient-descent methods for temporal-difference learning with linear function approximation.  In _Proceedings of the 26th Annual International Conference on Machine Learning_ , pp. 993–1000, 2009.
  * Sutton et al. (2016) Sutton, R. S., Mahmood, A. R., and White, M.  An emphatic approach to the problem of off-policy temporal-difference learning.  _The Journal of Machine Learning Research_ , 17(1):2603–2631, 2016.
  * Tsitsiklis & Van Roy (1996) Tsitsiklis, J. N. and Van Roy, B.  Feature-based methods for large scale dynamic programming.  _Machine Learning_ , 22(1):59–94, 1996.
  * Tsitsiklis & Van Roy (1997) Tsitsiklis, J. N. and Van Roy, B.  An analysis of temporal-difference learning with function approximation.  _IEEE transactions on automatic control_ , 42(5):674–690, 1997.
  * Watkins & Dayan (1992) Watkins, C. J. and Dayan, P.  Q-learning.  _Machine learning_ , 8(3-4):279–292, 1992.
  * Yang & Wang (2019) Yang, L. and Wang, M.  Sample-optimal parametric q-learning using linearly additive features.  In _International Conference on Machine Learning_ , pp. 6995–7004. PMLR, 2019.
  * Zhang et al. (2021) Zhang, S., Yao, H., and Whiteson, S.  Breaking the deadly triad with a target network.  _arXiv preprint arXiv:2101.08862_ , 2021.

##  Appendix A Appendix

###  A.1 Proof of Proposition 2.8

###### Proof.

To verify asymptotic stability of switching systems (9), one of the simplest
ways is to find a common quadratic Lyapunov function $V(x)=x^{T}Px$. In
particular, (9) is asymptotically stable if there exists a symmetric positive
definite matrix $P$ such that

$\displaystyle PA_{\sigma}+A^{T}_{\sigma}P\prec 0\quad\text{for
all}\quad\sigma\in\\{1,\dots,M\\}$

holds.

In our case, we assume that $A_{\sigma}$ is negative definite, which
significantly simplifies the analysis. In particular, if $A_{\sigma}$ is
negative definite, then from the definition of a negative definite matrix, we
have

$\displaystyle A_{\sigma}+A^{T}_{\sigma}\prec 0\quad\text{for
all}\quad\sigma\in\\{1,\dots,M\\}.$

Therefore, we can automatically choose $P=I$. This implies that for a
switching system with $A_{\sigma}$ being negative definite, we can ensure that
$V(x)=x^{T}x$ is a common quadratic Lyapunov function, and the system is
asymptotically stable. This completes the proof. ∎

###  A.2 Negative definiteness of $A_{\pi_{X\theta}}+\eta C$

We first introduce Gerschgorin circle theorem (Horn & Johnson, 2013) to prove
Lemma A.2.

######  Lemma A.1 (Gerschgorin circle theorem).

(Horn & Johnson, 2013) Let $A=[a_{ij}]\in\mathbb{R}^{n\times m}$ and
$R_{i}(A)=\sum\limits_{j\neq i}^{m}a_{ij}$. Consider the Gerschgorin circles

$\displaystyle\\{z\in\mathbb{C}|:|z-a_{ii}|\leq R_{i}(A)\\},\quad
i=1,\dots,n.$

The eigenvalues of $A$ are in the union of Gerschgorin discs

$\displaystyle G(A)=\cup^{n}_{i=1}\\{z\in\mathbb{C}|:|z-a_{ii}|\leq
R_{i}(A)\\}.$

Now, we state the lemma to guarantee negative definiteness of
$A_{\pi_{X\theta}}+\eta C$.

######  Lemma A.2.

Let

$\displaystyle M^{\pi_{X\theta}}:=D((1+\eta)I-\gamma P^{\pi_{X\theta}}).$

Under the following condition:

$\displaystyle\eta>\max_{\pi\in\Theta,s\in S,a\in A}\frac{\gamma
d^{T}P^{\pi}(e_{a}\otimes e_{s})}{2d(s,a)}-\frac{2-\gamma}{2}\quad,$

where $\Theta$ is the set of all deterministic policies, and $\otimes$ is the
Kronecker product, $M_{\pi_{X\theta}}$ is positive definite.

###### Proof.

We use Gerschgorin circle theorem for the proof. First, denote
$m_{ij}=[M_{\pi_{X\theta}}]_{ij}$. Then, one gets

$\displaystyle m_{ii}$ $\displaystyle=d_{i}((1+\eta)-\gamma
e^{T}_{i}P^{\pi_{X\theta}}e_{i}),$ $\displaystyle m_{ij}$
$\displaystyle=-d_{i}\gamma
e^{T}_{i}P^{\pi_{X\theta}}e_{j}\quad\text{for}\quad i\neq j.$

Except for the diagonal element, the row and column sums, respectively, become

$\displaystyle\sum\limits_{j\neq i}|m_{ij}|$ $\displaystyle=\gamma
d_{i}(1-e^{T}_{i}P^{\pi_{X\theta}}e_{i})$ $\displaystyle\sum\limits_{j\neq
i}|m_{ji}|$ $\displaystyle=\gamma d^{T}P^{\pi_{X\theta}}e_{i}-\gamma
d_{i}e^{T}_{i}P^{\pi_{X\theta}}e_{i}$

We need to show that $M^{\pi_{X\theta}}+M^{\pi_{X\theta}^{T}}$ is positive
definite. To this end, we use Lemma A.1 to have the following inequality:

$\displaystyle|\lambda-2m_{ii}|$ $\displaystyle\leq\sum\limits_{j\neq
i}|m_{ij}|+\sum\limits_{j\neq i}|m_{ji}|$

Considering the lower bound of $\lambda$, we have

$\displaystyle\lambda$ $\displaystyle\geq 2m_{ii}-\sum\limits_{j\neq
i}|m_{ij}|-\sum\limits_{j\neq i}|m_{ji}|$
$\displaystyle=(1+\eta-\gamma)d_{i}+((1+\eta)d_{i}-\gamma
d^{T}P^{\pi_{X\theta}}e_{i})$
$\displaystyle=\eta(2d_{i})+(2-\gamma)d_{i}-\gamma
d^{T}P^{\pi_{X\theta}}e_{i}.$

Hence, for $\lambda>0$, we should have

$\displaystyle\eta>\frac{\gamma
d^{T}P^{\pi_{X\theta}}e_{i}}{2d_{i}}-\frac{2-\gamma}{2}.$

Taking $\eta>\max_{\pi\in\Theta,s\in{\cal S},a\in{\cal A}}\frac{\gamma
d^{T}P^{\pi}(e_{a}\otimes e_{s})}{2d(s,a)}-\frac{2-\gamma}{2}$, we can make
$M^{\pi_{X\theta}}$ always positive definite.

∎

###  A.3 Proof of Lemma 3.1

To show existence and uniqueness of the solution of (13), we use Banach fixed-
point theorem (Agarwal et al., 2018). First, we define the operator
$\mathcal{T}_{\eta}$ as follows:

$\displaystyle\mathcal{T}_{\eta}(\theta):=\frac{1}{1+\eta}(X^{T}DX)^{-1}(X^{T}DR+\gamma
X^{T}DP\Pi_{X\theta}X\theta)$

We show that $\mathcal{T}_{\eta}$ is contraction mapping. The existence and
uniqueness of (13) follows from the Banach fixed-point theorem.

$\displaystyle||\theta_{1}-\theta_{2}||_{\infty}$
$\displaystyle=\frac{1}{1+\eta}||(X^{T}DX)^{-1}(\gamma
X^{T}DP\Pi_{X\theta_{1}}X\theta_{1}-\gamma
X^{T}DP\Pi_{X\theta_{2}}X\theta_{2})||_{\infty}$
$\displaystyle\leq\frac{\gamma}{1+\eta}||(X^{T}DX)^{-1}||_{\infty}||X^{T}||_{\infty}||\Pi_{X\theta_{1}}X\theta_{1}-\Pi_{\pi_{X\theta_{2}}}X\theta_{2}||_{\infty}$
$\displaystyle\leq\frac{\gamma}{1+\eta}||(X^{T}DX)^{-1}||_{\infty}||X^{T}||_{\infty}||\Pi_{X(\theta_{1}-\theta_{2})}(X\theta_{1}-X\theta_{2})||_{\infty}$
$\displaystyle\leq\frac{\gamma}{1+\eta}||(X^{T}DX)^{-1}||_{\infty}||X^{T}||_{\infty}||X\theta_{1}-X\theta_{2}||_{\infty}$
$\displaystyle\leq\frac{\gamma}{1+\eta}||(X^{T}DX)^{-1}||_{\infty}||X^{T}||_{\infty}||X||_{\infty}||\theta_{1}-\theta_{2}||_{\infty}$
$\displaystyle\leq\gamma||\theta_{1}-\theta_{2}||_{\infty}$

The first inequality follows from the submultiplicativity of matrix norm and
$||DP||_{\infty}\leq 1$. The second inequality follows from the fact that
$\max x-\max y\leq\max(x-y)$. The last inequality is due to the condition
$\eta>||(X^{T}DX)^{-1}||_{\infty}X_{\max}^{2}-1$. Since $\gamma<1$,
$\mathcal{T}_{\eta}$ is contraction mapping. Now we can use Banach fixed-point
theorem to conclude existence and uniqueness of (13).

###  A.4 Proof of Lemma 3.2

###### Proof.

The bias term of the solution can be obtained using simple algebraic
inequalities.

$\displaystyle||X\theta_{e}-Q^{*}||_{\infty}$ $\displaystyle\leq\left\lVert
X\theta_{e}-\frac{1}{1+\eta}Q^{*}\right\rVert_{\infty}+\left\lVert\frac{\eta}{1+\eta}Q^{*}\right\rVert_{\infty}$
$\displaystyle\leq\left\lVert X\theta_{e}-\frac{1}{1+\eta}\Gamma
Q^{*}\right\rVert_{\infty}+\left\lVert\frac{1}{1+\eta}Q^{*}-\frac{1}{1+\eta}\Gamma
Q^{*}\right\rVert_{\infty}+\left\lVert\frac{\eta}{1+\eta}Q^{*}\right\rVert_{\infty}$
$\displaystyle\leq\frac{1}{1+\eta}||\Gamma(\mathcal{T}X\theta_{e})-\Gamma\mathcal{T}Q^{*}||_{\infty}+\left\lVert\frac{1}{1+\eta}Q^{*}-\frac{1}{1+\eta}\Gamma
Q^{*}\right\rVert_{\infty}+\left\lVert\frac{\eta}{1+\eta}Q^{*}\right\rVert_{\infty}$
$\displaystyle\leq\frac{\gamma||\Gamma||_{\infty}}{1+\eta}||X\theta_{e}-Q^{*}||_{\infty}+\left\lVert\frac{1}{1+\eta}Q^{*}-\frac{1}{1+\eta}\Gamma
Q^{*}\right\rVert_{\infty}+\left\lVert\frac{\eta}{1+\eta}Q^{*}\right\rVert_{\infty}.$

The last inequality follows from the fact that the Bellman operator
$\mathcal{T}$ is $\gamma$-contraction with respect to the infinity norm.

Rearranging the terms, we have

$\displaystyle||X\theta_{e}-Q^{*}||_{\infty}\leq\frac{1}{1+\eta-\gamma||\Gamma||_{\infty}}||Q^{*}-\Gamma
Q^{*}||_{\infty}+\frac{\eta}{1+\eta-\gamma||\Gamma||_{\infty}}\frac{R_{\max}}{1-\gamma}.$

The bias is caused by projection and additional error term due to
regularization. ∎

###  A.5 Proofs for 2.6

In this section, we provide omitted proofs to check 2.6 for Theorem 5.2.

First of all, Lipschitzness of $f(\theta)$ ensures the unique solution of the
O.D.E..

######  Lemma A.3 (Lipschitzness).

Let

$f(\theta)=-(1+\eta)X^{T}DX\theta+\gamma X^{T}DP\Pi_{X\theta}X\theta+X^{T}DR$
(21)

Then, $f(\theta)$ is globally Lipschitzness continuous.

###### Proof.

Lipschitzness of $f(\theta)$ can be proven as follows:

$\displaystyle||f(\theta)-f(\theta^{\prime})||_{\infty}$
$\displaystyle\leq(1+\eta)||X^{T}DX(\theta-\theta^{\prime})||_{\infty}+\gamma||X^{T}DP(\Pi_{X\theta}X_{\theta}-\Pi_{X\theta^{\prime}}X\theta^{\prime})||_{\infty}$
$\displaystyle\leq(1+\eta)||X^{T}DX||_{\infty}||\theta-\theta^{\prime})||_{\infty}+\gamma||X^{T}DP||_{\infty}||\Pi_{X\theta}X\theta-\Pi_{X\theta^{\prime}}X\theta^{\prime}||_{\infty}$
$\displaystyle\leq(1+\eta)||X^{T}DX||_{\infty}||\theta-\theta^{\prime})||_{\infty}+\gamma||X^{T}DP||_{\infty}||\Pi_{X(\theta-\theta^{\prime})}X(\theta-\theta^{\prime})||_{\infty}$
$\displaystyle\leq((1+\eta)||X^{T}DX||_{\infty}+\gamma||X^{T}DP||_{\infty}||X||_{\infty})||\theta-\theta^{\prime})||_{\infty}$

Therefore $f(\theta)$ is Lipschitz continuous with respect to the
$||\cdot||_{\infty}$, ∎

Next, the existence of limiting O.D.E. of (19) can be proved using the fact
that policy is invariant under constant multiplication when linear function
approximation is used.

######  Lemma A.4 (Existence of limiting O.D.E. and stability).

Under (18), there exists limiting ode of (22) and its origin is asymptotically
stable.

$f(\theta)=-(1+\eta)X^{T}DX\theta+\gamma X^{T}DP\Pi_{X\theta}X\theta+X^{T}DR$
(22)

###### Proof.

The existence of limiting O.D.E can be obtained using the homogeneity of
policy, $\Pi_{X(c\theta)}=\Pi_{X\theta}$.

$\displaystyle f(c\theta)$ $\displaystyle=-(1+\eta)X^{T}DX(c\theta)+\gamma
X^{T}DP\Pi_{X(c\theta)}X(c\theta)+X^{T}DR,$
$\displaystyle\lim_{c\rightarrow\infty}\frac{f(cx)}{c}$
$\displaystyle=(-(1+\eta)X^{T}DX+\gamma X^{T}DP\Pi_{X\theta}X)\theta$

This can be seen as switching system and shares common Lyapunov function
$V=||\theta||^{2}$. Hence, the origin is asymptotically stable by Proposition
2.8. ∎

Lastly, we check conditions for martingale difference sequences.

######  Lemma A.5 (Martingale difference sequence, $m_{k}$, and square
integrability).

We have

$\displaystyle\operatorname{\mathbb{E}}[m_{k+1}|\operatorname{\mathcal{F}}_{k}]$
$\displaystyle=0,$
$\displaystyle\operatorname{\mathbb{E}}[||m_{k+1}||^{2}|\operatorname{\mathcal{F}}_{k}]$
$\displaystyle<C_{0}(1+||\theta||^{2}),$

where $C_{0}=\max(12X_{\max}^{2}R_{\max}^{2},12\gamma
X_{\max}^{4}+4\eta^{2}X^{2}_{\max})$.

###### Proof.

To show $\\{m_{k},k\in\mathbb{N}\\}$ is a martingale difference sequence with
respect to the sigma-algebra generated by ${\cal G}_{k}$, we first prove
expectation of $m_{k+1}$ is zero conditioned on $\mathcal{G}_{k}$.

$\operatorname{\mathbb{E}}[m_{k+1}|\mathcal{G}_{k}]=0$

This follows from definition of $b,C$ and $A_{\pi_{X\theta}}$.

The boundedness $\mathbb{E}[||n_{k}||]<\infty$ also follows from simple
algebraic inequalities. Therefore $\\{m_{k},\mathcal{G}),k\in\mathbb{N}\\}$ is
martingale difference sequence.

Now, we show square integrability of the martingale difference sequence, which
is

$\operatorname{\mathbb{E}}[||m_{k+1}||^{2}|\mathcal{G}_{k}]\leq
C_{0}(||\theta_{k}||^{2}+1).$

Using simple algebraic inequalities, we have

$\displaystyle\operatorname{\mathbb{E}}[||m_{k+1}||^{2}|\mathcal{G}_{k}]$
$\displaystyle=\operatorname{\mathbb{E}}[||\delta_{k}x(s_{k},a_{k})+\eta
x(s_{k},a_{k})^{T}x(s_{k},a_{k})\theta_{k}-\operatorname{\mathbb{E}}_{\mu}[\delta_{k}x(s_{k},a_{k})+\eta
x(s_{k},a_{k})^{T}x(s_{k},a_{k})\theta_{k}]||^{2}|\mathcal{G}_{t}]$
$\displaystyle\leq\operatorname{\mathbb{E}}[||\delta_{k}x(s_{k},a_{k})+\eta
x(s_{k},a_{k})^{T}x(s_{k},a_{k})\theta_{k}||^{2}+||\operatorname{\mathbb{E}}_{\mu}[\delta_{k}x(s_{k},a_{k})+\eta
x(s_{k},a_{k})^{T}x(s_{k},a_{k})\theta_{k}]||^{2}|\mathcal{G}_{t}]$
$\displaystyle\leq 2\operatorname{\mathbb{E}}[||\delta_{k}x(s_{k},a_{k})+\eta
x(s_{k},a_{k})^{T}x(s_{k},a_{k})\theta_{k}]||^{2}\mathcal{G}_{t}]$
$\displaystyle\leq
4\operatorname{\mathbb{E}}[||\delta_{k}x(s_{k},a_{k})||^{2}|\mathcal{G}_{t}]+4\eta^{2}\operatorname{\mathbb{E}}[|||x(s_{k},a_{k})^{T}x(s_{k},a_{k})\theta_{k}||^{2}|\mathcal{G}_{t}]$
$\displaystyle\leq
12X_{\max}^{2}\operatorname{\mathbb{E}}[||r_{k}||^{2}+||\gamma\max
x(s_{k},a_{k})\theta_{k}||^{2}+||x(s_{k},a_{k})\theta_{k}||^{2}|\mathcal{G}_{t}]+4\eta^{2}X_{\max}^{2}||\theta_{k}||^{2}$
$\displaystyle\leq 12X_{\max}^{2}R_{\max}^{2}+12\gamma
X_{\max}^{4}||\theta_{k}||^{2}+X_{\max}^{2}||\theta_{k}||^{2}+4\eta^{2}X^{2}_{\max}||\theta_{k}||^{2}$
$\displaystyle\leq C_{0}(1+||\theta_{k}||^{2}),$

where $C_{0}=\max(12X_{\max}^{2}R_{\max}^{2},12\gamma
X_{\max}^{4}+4\eta^{2}X^{2}_{\max})$. The fourth inequality follows from the
fact that $||a+b+c||^{2}\leq 3||a||^{2}+3||b||^{2}+3||c||^{2}$. This completes
the proof.

∎

###  A.6 Proof of Theorem 5.1

Before moving onto the proof of Theorem 5.1, in order to prove the stability
using the upper and lower systems, we need to introduce some notions such as
the quasi-monotone function and vector comparison principle. We first
introduce the notion of quasi-monotone increasing function, which is a
necessary prerequisite for the comparison principle for multidimensional
vector system.

######  Definition A.6 (Quasi-monotone function).

A vector-valued function $f:{\mathbb{R}}^{n}\to{\mathbb{R}}^{n}$ with
$f:=\begin{bmatrix}f_{1}&f_{2}&\cdots&f_{n}\\\ \end{bmatrix}^{T}$ is said to
be quasi-monotone increasing if $f_{i}(x)\leq f_{i}(y)$ holds for all
$i\in\\{1,2,\ldots,n\\}$ and $x,y\in{\mathbb{R}}^{n}$ such that $x_{i}=y_{i}$
and $x_{j}\leq y_{j}$ for all $j\neq i$.

Based on the notion of quasi-monotone function, we introduce the vector
comparison principle.

######  Lemma A.7 (Vector Comparison Principle).

(Hirsch & Smith, 2006) Suppose that $\bar{f},\underline{$f$}$ are globally
Lipschitz continuous. Let $v_{t}$ be a solution of the system

$\displaystyle\frac{d}{dt}x_{t}=\bar{f}(x_{t}),\qquad
x_{o}\in\operatorname{\mathbb{R}}^{n},\forall{t}\geq 0.$

Assume that $\bar{f}$ is quasi-monotone increasing, and let $v_{t}$ be a
solution of the system

$\displaystyle\frac{d}{dt}v_{t}=\underline{$f$}(v_{t}),\qquad
v_{0}<x_{0},\forall{t}\geq 0,$

where $\underline{$f$}(v)\leq\bar{f}(v)$ holds for any
$v\in\operatorname{\mathbb{R}}^{n}$. Then, $v_{t}\geq x_{t}$ for all $t\geq
0$.

The vector comparison lemma can be used to bound the state trajectory of the
original system by those of the upper and lower systems. Then, proving global
asymptotic stability of the upper and lower systems leads to global asymptotic
stability of original system. We now give the proof of Theorem 5.1.

###### Proof.

First we construct the upper comparison part. Noting that

$\gamma X^{T}DP\Pi_{X\theta_{e}}X\theta_{e}\geq\gamma
X^{T}DP\Pi_{X\theta}X\theta_{e}$ (23)

and

$\gamma X^{T}DP\Pi_{X(\theta-\theta_{e})}X(\theta-\theta_{e})\geq\gamma
X^{T}DP\Pi_{X\theta}X(\theta-\theta_{e}),$ (24)

we define $\bar{f}(y)$ and $\underline{$f$}(y)$ as follows:

$\displaystyle\bar{f}(y)$ $\displaystyle=(-(1+\eta)X^{T}DX+\gamma
X^{T}DP\Pi_{Xy}X)y,$ $\displaystyle\underline{$f$}(y)$
$\displaystyle=(-(1+\eta)X^{T}DXy+\gamma
X^{T}DP\Pi_{X(y+\theta_{e})}X)y+\gamma
X^{T}DP(\Pi_{X(y+\theta_{e})}-\Pi_{X\theta_{e}})X\theta_{e}$

Using using (23) and (24), we have $\bar{f}(y)\leq\underline{$f$}(y)$.

$\underline{$f$}$ is the corresponding O.D.E of original system and $\bar{f}$
becomes O.D.E of the upper system. $\bar{f}$ becomes switched linear system.

Now consider the O.D.E systems

$\displaystyle\frac{d}{dt}\theta^{u}_{t}$
$\displaystyle=\bar{f}(\theta^{u}_{t}),\qquad\theta^{u}_{0}>\theta_{0},$
$\displaystyle\frac{d}{dt}\theta_{t}$
$\displaystyle=\underline{$f$}(\theta_{t}).$

Next, we prove quasi-monotone increasing property of $\bar{f}$. For any
$z\in\operatorname{\mathbb{R}}^{|S||A|}$, consider a non-negative vector
$p\in\operatorname{\mathbb{R}}^{|S||A|}$ such that its $i$-th element is zero.
Then, for any $1\leq i\leq d$,we have

$\displaystyle e^{T}_{i}\bar{f}(y+p)$
$\displaystyle=e^{T}_{i}(-(1+\eta)X^{T}DX+\gamma X^{T}DP\Pi_{X(y+p)}X)(y+p)$
$\displaystyle=-(1+\eta)e^{T}_{i}X^{T}DXy-(1+\eta)e^{T}_{i}X^{T}DXp+\gamma
e^{T}_{i}X^{T}DP\Pi_{X(y+p)}X(y+p)$
$\displaystyle\geq-(1+\eta)e^{T}_{i}X^{T}DXy+\gamma
e^{T}_{i}X^{T}DP\Pi_{Xy}Xy$ $\displaystyle=e^{T}_{i}\bar{f}(y),$

where the inequality comes from $e^{T}_{i}X^{T}DXp=0$ due to 2.2.

Therefore by Lemma A.7, we can conclude that $\theta_{t}\leq\theta^{u}_{t}$.
The switching system matrices of the upper system are all negative definite by
Lemma A.2, The switching system shares $V(\theta)=||\theta||^{2}$ as common
Lyapunov function. Therefore by Proposition 2.8, we can conclude that the
upper comparison system is globally asymptotically stable.

For the lower comparison part, noting that

$\gamma X^{T}DP\Pi_{X\theta}X\theta\geq\gamma
X^{T}DP\Pi_{X\theta_{e}}X\theta,$

we can define $\underline{$f$}(y)$ and $\bar{f}(y)$ such that
$\underline{$f$}(y)\leq\bar{f}(y)$ as follows:

$\displaystyle\bar{f}(y)$ $\displaystyle=-(1+\eta)X^{T}DXy+\gamma
X^{T}DP\Pi_{Xy}Xy+X^{T}DR,$ $\displaystyle\underline{$f$}(y)$
$\displaystyle=-(1+\eta)X^{T}DXy+\gamma X^{T}DP\Pi_{X\theta_{e}}Xy+X^{T}DR$

The corresponding O.D.E system becomes

$\displaystyle\frac{d}{dt}\theta_{t}$ $\displaystyle=\bar{f}(\theta_{t}),$
$\displaystyle\frac{d}{dt}\theta^{l}_{t}$
$\displaystyle=\underline{$f$}(\theta^{l}_{t}),\quad\theta^{l}_{0}<\theta_{0}.$
(25)

Proving quasi-monotonicity of $\bar{f}$ is similar to previous step. Consider
non-negative vector $p\in\operatorname{\mathbb{R}}^{|S||A|}$ such that its
$i$-th element is zero.

$\displaystyle e^{T}_{i}\bar{f}(y+p)$
$\displaystyle=e_{i}^{T}(-(1+\eta)X^{T}DX(y+p)+\gamma
X^{T}DP\Pi_{X(y+p)}X(y+p)+X^{T}DR)$
$\displaystyle=e_{i}^{T}(-(1+\eta)X^{T}DXy+\gamma
X^{T}DP\Pi_{X(y+p)}X(y+p)+X^{T}DR)$ $\displaystyle\geq
e_{i}^{T}(-(1+\eta)X^{T}DXy+\gamma X^{T}DP\Pi_{Xy}Xy+X^{T}DR)$
$\displaystyle=e^{T}_{i}\bar{f}(y)$

The second equality holds since $X^{T}DX$ is diagonal matrix and $p_{i}=0$.
Therefore by Lemma A.7, we can conclude that $\theta^{l}_{t}\leq\theta_{t}$.
The lower comparison part is linear system with affine term, and the matrix is
negative definite by Lemma A.2. Therefore, we can conclude that (25) is
globally asymptotically stable.

To prove uniqueness of the equilibrium point, assume there exists two
different equilibrium points $\theta^{e}_{1}$ and $\theta^{e}_{2}$. The global
asymptotic stability implies that regardless of initial state,
$\theta_{t}\rightarrow\theta^{e}_{1}$ and
$\theta_{t}\rightarrow\theta^{e}_{2}$. However this becomes contradiction if
$\theta^{e}_{1}\neq\theta^{e}_{2}$. Therefore, the equilibrium point is
unique. ∎

###  A.7 Proof of Theorem 5.2

###### Proof.

To apply Lemma 2.7, let us check 2.6.

  1. 1.

First and second statement of 2.6 follows from Lemma A.4

  2. 2.

Third statement of 2.6 follows from Theorem 5.1

  3. 3.

Fourth statement of 2.6 follows from Lemma A.5

Since we assumed Robbins Monro step-size, we can now apply Lemma 2.7 to
complete the proof. ∎

###  A.8 Experiments

####  A.8.1 Diagrams for $\theta\rightarrow 2\theta$ and Baird Seven Star
Counter Example

The state transition diagrams of $\theta\rightarrow 2\theta$ and Baird seven-
star example are depicted.

(a) $\theta\rightarrow 2\theta$

(b) Baird seven star counter example

Figure 4: Counter-examples where Q-learning with linear function approximation
diverges

####  A.8.2 O.D.E. trajectories of MDP introduced in Section 6.3

The O.D.E. trajectories of MDP introduced in Section 6.3 are depicted.

(a) $\theta_{1}-\theta^{e}_{1}$

(b) $\theta_{2}-\theta^{e}_{2}$

Figure 5: Trajectories of upper and lower O.D.E.