# Multi-Bellman operator for convergence of
$Q$-learning with linear function approximation

Diogo S. Carvalho, Pedro A. Santos, and Francisco S. Melo
Instituto Superior Técnico, University of Lisbon, and INESC-ID
<EMAIL_ADDRESS>
###### Abstract

We study the convergence of $Q$-learning with linear function approximation.
Our key contribution is the introduction of a novel multi-Bellman operator
that extends the traditional Bellman operator. By exploring the properties of
this operator, we identify conditions under which the projected multi-Bellman
operator becomes contractive, providing improved fixed-point guarantees
compared to the Bellman operator. To leverage these insights, we propose the
multi $Q$-learning algorithm with linear function approximation. We
demonstrate that this algorithm converges to the fixed-point of the projected
multi-Bellman operator, yielding solutions of arbitrary accuracy. Finally, we
validate our approach by applying it to well-known environments, showcasing
the effectiveness and applicability of our findings.

##  1 Introduction

Reinforcement learning aims to approximate the value of actions in different
states, considering the expected sum of time-discounted rewards in a Markovian
environment. The importance of this task cannot be overstated, as an accurate
value function enables an agent to make optimal decisions by selecting actions
with the highest value in a given state [Puterman, 2005]. Additionally, the
value function facilitates environment evaluation and enables comparisons
between different environments.

If we can use a tabular representation for the value function, meaning that we
can store the value of performing each action on each state individually, the
$Q$-learning algorithm converges to the correct value function [Watkins and
Dayan, 1992]. When it is not possible or desirable to store values in a table,
for example when there are too many states or actions, $Q$-learning can be
combined with function approximation [Melo and Ribeiro, 2007]. Unfortunately,
the combination of $Q$-learning and function approximation is troublesome.
Even when the function approximation space is linear, the algorithm is not
guaranteed to converge [Sutton and Barto, 2018]. In fact, the approximation
problem that $Q$-learning addresses does not have, in general, a solution
[Melo et al., 2008].

To address these limitations, we propose an alternative algorithm that
effectively solves the function approximation problem, unlike the original
$Q$-learning. Both the problem and the algorithm proposed can be seen as
extensions of the original. In this work, our contributions are as follows:

  * •

Introduction of the multi-Bellman operator and analysis of its functional
properties.

  * •

Identification of conditions under which the projected multi-Bellman operator
is contractive.

  * •

Proposal of the multi $Q$-learning algorithm with linear function
approximation.

  * •

Theoretical and empirical demonstrations of the convergence of multi
$Q$-learning.

  * •

Theoretical and empirical evidence that the obtained solution can achieve
arbitrary precision.

##  2 Background

A Markov decision problem (MDP) is a tuple
$(\mathcal{X},\mathcal{A},\mathcal{P},\mathcal{R},\gamma)$, where
$\mathcal{X}$ is a discrete set of states (the state space), $\mathcal{A}$ is
a finite set of actions (the action space), $\mathcal{P}$ is a set of
distributions over $\mathcal{X}$ for each state and action (the transitions),
$\mathcal{R}$ is a set of distributions over a bounded subset of $\mathbb{R}$
for each state and action with expected value $r$ (the rewards) and $\gamma$
is a real in $[0,1)$ (the discount).

Given an MDP, the value of a policy
$\pi:\mathcal{X}\to\Delta\left(\mathcal{A}\right)$ is the function
$q:\mathcal{X}\times\mathcal{A}\to\mathbb{R}$

$\displaystyle q(x,a)=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{t}\mid
x_{0}=x,a_{0}=a\right],$

where the expectation is with respect to rewards $r_{t}$ that are obtained
from performing action $a_{t}$ on state $x_{t}$, states $x_{t+1}$ that are
obtained by performing action $a_{t}$ on state $x_{t}$, and actions $a_{t}$
that are selected according to $\pi$. There is at least one policy $\pi^{*}$
that maximizes $q_{\pi}$ on every state and action Puterman [2005] and we
refer to its value as $q^{*}$. The value $q^{*}$ satisfies the Bellman
equation

$\displaystyle q^{*}=\mathbf{H}q^{*},$

where $\mathbf{H}$ is the Bellman operator defined for arbitrary
$q:\mathcal{X}\times\mathcal{A}\to\mathbb{R}$ as

$\displaystyle(\mathbf{H}q)(x,a)=\mathbb{E}\left[r(x,a)+\gamma\max_{a^{\prime}\in\mathcal{A}}q\left(x^{\prime},a^{\prime}\right)\right],$

where the expectation is with respect to the next state $x^{\prime}$ obtained
by performing action $a$ on state $x$.

Our goal is to approximate $q^{*}$. In other words, we want to find a good
parameterized representation of the value of an optimal policy for a given MDP
given a function approximation space.

###  2.1 Function approximation

Let us consider a differentiable function space
${\mathcal{H}=\\{h_{\omega}:\mathcal{Z}\to\mathbb{R},\omega\in\mathbb{R}^{k}\\}}$,
a distribution $\mu$ over a random $z$ in a discrete set $\mathcal{Z}$ and a
loss ${l(\omega)=\frac{1}{2}\left\lVert h-h_{\omega}\right\rVert^{2}}$ with
the $\mu$-norm $\left\lVert
h\right\rVert=\sqrt{\mathbb{E}_{\mu}\left[h^{2}(z)\right]}$.

To approximate a function $h$ is to find an element in the subset
$\operatorname*{Proj}h$ of $\mathcal{H}$ defined as

$\displaystyle\operatorname*{Proj}h=\operatorname*{argmin}_{h_{\omega}\in\mathcal{H}}l(\omega).$

Any $\omega$ parameterizing a $h_{\omega}$ in $\operatorname*{Proj}h$ is a
critical point of $l$ and must verify $\nabla_{\omega}l(\omega)=0$.

##### Linear function approximation

Given features $\phi:\mathcal{Z}\to\mathbb{R}^{k}$, a linear function
approximation space is given by the functions such that
$h_{\omega}(z)=\phi^{T}(z)\omega$. In this case, the gradient of the loss is

$\displaystyle\nabla_{\omega}l(\omega)=-\mathbb{E}\left[\phi(z)\left(h(z)-h_{\omega}(z)\right)\right].$

Solving for $\nabla_{\omega}l(\omega)=0$ we obtain that

$\displaystyle\omega=\mathbb{E}\left[\phi(z)\phi^{T}(z)\right]^{-1}\mathbb{E}\left[\phi(z)h(z)\right].$

Thus, if the inverted matrix above exists, the set $\operatorname*{Proj}h$ has
a single element and we can refer to both as $h_{\tilde{\omega}}$. The
solution $\tilde{\omega}$ is also the globally asymptotically stable
equilibrium of the dynamical system

$\displaystyle\dot{\omega}=\nabla_{\omega}l(\omega),$

and the limit of the sequence of $\omega_{t}$ obtained by performing a
discretized update with $z_{t}$ i.i.d. from $\mu$

$\displaystyle\omega_{t+1}=\omega_{t}+\alpha_{t}\left[\phi\left(z_{t}\right)\left(h(z_{t})-h_{\omega_{t}}(z_{t})\right)\right].$

##### Stochastic approximation

Without access to $h$, stochastic approximation performs the update

$\displaystyle\omega_{t+1}=\omega_{t}+\alpha_{t}\left[\phi\left(z_{t}\right)\left(\tau_{t+1}-h_{\omega_{t}}(z_{t})\right)\right],$

with $\tau_{t+1}$ a possibly $\omega_{t}$-dependent estimate of
${h\left(z_{t}\right)}$ called the target and $\alpha_{t}$ a small positive
real called the learning rate. If there exists an equilibrium for the ordinary
differential equation (o.d.e.)

$\displaystyle\dot{\omega}=\mathbb{E}\left[\phi\left(x,a\right)\left(\tau(\omega)-h_{\omega}(z)\right)\right],$

where $\tau(\omega)=\mathbb{E}\left[\tau_{t+1}\mid z_{t}\right]$, and it is
globally asymptotically stable, well-established conditions guarantee the
stochastic approximation update converges to such equilibrium [Borkar, 2008,
Chapter 2].

###  2.2 $Q$-learning with linear function approximation

We consider now features $\phi:\mathcal{X}\times\mathcal{A}\to\mathbb{R}^{k}$,
parameters $\omega$ in $\mathbb{R}^{k}$, a distribution over states and
actions $\mu$ and linearly parameterized functions
$q_{\omega}:\mathcal{X}\times\mathcal{A}\to\mathbb{R}$ such that
$q_{\omega}(x,a)=\phi^{T}(x,a)\omega$.

In reinforcement learning we want to approximate $q^{*}$. Formally, we want to
compute $\omega^{*}$ such that

$\displaystyle q_{\omega^{*}}=\operatorname*{Proj}q^{*}.$

We have no knowledge of $q^{*}$ and are unable to perform an exact stochastic
approximation update

$\displaystyle\omega_{t+1}=\omega_{t}+\alpha_{t}\left[\phi\left(x_{t},a_{t}\right)\left(q^{*}(x_{t},a_{t})-q_{\omega_{t}}(x_{t},a_{t})\right)\right].$

Thinking of the identity $q^{*}=\mathbf{H}q^{*}$, $Q$-learning performs
instead the stochastic approximation update

$\displaystyle\omega_{t+1}=\omega_{t}+\alpha_{t}\left[\phi\left(x_{t},a_{t}\right)\left(\tau_{t+1}-q_{\omega_{t}}(x_{t},a_{t})\right)\right],$

where the target $\tau_{t+1}$ is a sample for
$\left(\mathbf{H}q_{\omega_{t}}\right)(x_{t},a_{t})$ such that

$\displaystyle\tau_{t+1}=r_{t}+\gamma\max_{a_{t+1}\in\mathcal{A}}q_{\omega_{t}}\left(x_{t+1},a_{t+1}\right).$

A solution to $Q$-learning with linear function approximation must then be the
fixed-point of the projected Bellman operator, verifying the equation

$\displaystyle
q_{\omega}=\operatorname*{Proj}\left(\mathbf{H}q_{{\omega}}\right).$

Unfortunately, in general such fixed-point equation does not have a solution
and, even when it does, the solution may not be an asymptotically stable
equilibrium of the associated dynamical system

$\displaystyle\dot{\omega}=\mathbb{E}\left[\phi\left(x,a\right)\left(\tau(\omega)-q_{\omega}(x,a)\right)\right].$

Consequently, $Q$-learning with linear function approximation can diverge.

The divergence of $Q$-learning is evidenced in classic counter-examples where
the parameters of the approximator do not approach any solution, either
oscillating within a window [Boyan and Moore, 1995, Gordon, 2001] or growing
without bound [Tsitsiklis and Van Roy, 1996, Baird, 1995]. In practice, there
is also evidence of phenomena of catastrophic forgetting [Cahill, 2011] and of
convergence to incompetent solutions [van Hasselt et al., 2018]. Currently,
the theoretical results that establish convergence of $Q$-learning restrict
the data or the features too much [Szepesvári and Smart, 2004a, Melo et al.,
2008], and the proposed variants of $Q$-learning that are guaranteed to
converge under more general conditions [Carvalho et al., 2020, Zhang et al.,
2021, Lim et al., 2022] converge to biased limit solutions that do not hold
good performance guarantees [Chen et al., 2022]. Differently, our approach
does not bias the solution nor restricts the data and the features too much.

##  3 Multi-Bellman operator

Let us define a multi-Bellman operator $\mathbf{H}^{n}$ from the space of
functions $q:\mathcal{X}\times\mathcal{A}\to\mathbb{R}$ to itself such that
$\mathbf{H}^{n+1}q=\mathbf{H}\left(\mathbf{H}^{n}q\right)$ and
$\mathbf{H}^{1}q=\mathbf{H}q$. For example, we have that

$\displaystyle(\mathbf{H}^{2}q)\left(x_{0},a_{0}\right)=\mathbb{E}\left[r\left(x_{0},a_{0}\right)+\gamma\max_{{a_{1}}\in\mathcal{A}}\mathbb{E}\left[r(x_{1},a_{1})+\gamma\max_{a_{2}\in\mathcal{A}}q\left(x_{2},a_{2}\right)\right]\right].$

and, more generally,

$\displaystyle\left(\mathbf{H}^{n}q\right)(x_{0},a_{0})=\mathbb{E}\left[r\left(x_{0},a_{0}\right)+\gamma\max_{a_{1}\in\mathcal{A}}\mathbb{E}\left[r\left(x_{1},a_{1}\right)+\gamma\max_{a_{2}\in\mathcal{A}}\mathbb{E}\left[\cdots+\gamma\max_{a_{n}}q\left(x_{n},a_{n}\right)\right]\right]\right].$

Since ${q^{*}=\mathbf{H}q^{*}}$, also ${q^{*}=\mathbf{H}^{2}q^{*}}$ and, for
every, $n$ in $\mathbb{N}$ we have that

$\displaystyle q^{*}=\mathbf{H}^{n}q^{*}.$

First, we present the following lemma.

######  Lemma 1.

The operation $\mathbf{H}^{n}$ is a contraction in the $\infty$-norm with
contraction factor $\gamma^{n}$.

While unsurprising, the result has profound implications on the use of linear
function approximation.

###  3.1 Linear function approximation

We consider the following assumption.

######  Assumption 1.

The features are such that the covariance matrix
$\mathbb{E}_{\mu}\left[\phi(x,a)\phi^{T}(x,a)\right]$ is invertible.

Under the assumption above, we set the following result.

######  Proposition 1.

There exists $N\in\mathbb{N}$ such that, for all $n\geq N$,
$\operatorname*{Proj}\mathbf{H}^{n}$ is a contraction in the $\mu$-norm.

######  Corollary 1.

There exists $N\in\mathbb{N}$ such that, for all $n\geq N$, there exists a
unique solution $\tilde{\omega}^{n}$ to

$\displaystyle q_{\omega}=\operatorname*{Proj}(\mathbf{H}^{n}q_{\omega}).$ (1)

The result states that, while the projected Bellman operator may not be
contractive in the $\mu$-norm, the projected multi-Bellman operator is
contractive in the $\mu$-norm for sufficiently large $n$. As a consequence,
whereas the fixed-point equation of the projected Bellman operator may fail to
have any solution, the fixed-point equation of the projected multi-Bellman
operator has a unique solution.

The previous result establishes existence and uniqueness of solution. However,
it says nothing about the quality of such solution. In the following, we
analyze $\tilde{\omega}^{n}$ in comparison with the projected
$q_{\omega^{*}}$.

######  Proposition 2.

For all $n\geq N$, where $N$ is identified in Corollary 1,
$\tilde{\omega}^{n}$ is such that

$\displaystyle\left\lVert
q^{*}-q_{\tilde{\omega}^{n}}\right\rVert\leq\frac{1}{1-\frac{\sigma_{\mathrm{max}}\phi_{\mathrm{max}}^{2}}{\mu_{\mathrm{min}}}\gamma^{n}}\left\lVert
q^{*}-q_{\omega^{*}}\right\rVert,$ (2)

where
$\sigma_{\mathrm{max}}=\left\lVert\mathbb{E}\left[\phi(x,a)\phi^{T}(x,a)\right]^{-1}\right\rVert_{2}$
and $\phi_{\mathrm{max}}=\max_{x,a}\left\lVert\phi(x,a)\right\rVert_{2}$.

######  Corollary 2.

The sequence $\\{\tilde{\omega}^{n}\\}_{n\geq N}$ such that $N$ and
$\tilde{\omega}^{n}$ are identified in Corollay 1 gives

$\displaystyle\lim_{n\to\infty}\left\lVert\omega^{*}-\tilde{\omega}^{n}\right\rVert_{2}=0.$

The result states that, as $n$ increases, $\tilde{\omega}^{n}$ (resp.
$q_{\tilde{\omega}^{n}}$) becomes arbitrarily close to $\omega^{*}$ (resp.
$q_{\omega^{*}}$).

In the following, we propose a stochastic approximation algorithm for
computing $\tilde{\omega}^{n}$ for given $n$.

##  4 Multi $Q$-learning

We want to solve the fixed-point equation

$\displaystyle\omega=\operatorname*{Proj}(\mathbf{H}^{n}q_{\omega}).$

for arbitrary $n\in\mathbb{N}$. We propose to perform the multi $Q$-learning
update

$\displaystyle\omega_{t+1}^{n}=\omega_{t}^{n}+\alpha_{t}\left[\phi(x_{t},a_{t})\left(\tau^{n}_{t+1}-q_{\omega_{t}^{n}}(x_{t},a_{t})\right)\right],$

where the target $\tau_{t+1}^{n}$ is a sample for
$\left(\mathbf{H}^{n}q_{\omega_{t}^{n}}\right)(x_{t},a_{t})$ such that

$\displaystyle\tau_{t+1}^{n}=r_{t}+\gamma\max_{\bar{a}\in\mathcal{A}^{n}}\left[r_{t+1}+\gamma^{1}r_{t+2}+\ldots+\gamma^{n-1}q_{\omega_{t}^{n}}\left(x_{t+n},a_{t+n}\right)\right],$

with $\bar{a}=\left(a_{t+1},a_{t+2},\ldots,a_{t+n}\right)$ and $r_{t+m}$ and
$x_{t+m+1}$ are obtained by performing action $a_{t+m}$ on state $x_{t+m}$ for
$m$ between $1$ and $n$. In practice, at time step $t$, instead of building a
$1$-step greedy target, multi $Q$-learning builds an $n$-step target that is
obtained by trying every action on every state encountered along an $n$-step
trajectory starting at $x_{t+1}$. If we were to use terminology from the
planning literature, we could say the algorithm searches with fixed-depth and
full-breadth, a rather unexplored setting in reinforcement learning according
to [Moerland et al., 2023, Section 5.3].

Before we present our convergence result, let us consider a couple more of
assumptions.

######  Assumption 2.

For all $t\in\mathbb{N}$, states and actions are i.i.d. from $\mu$ and
$\mu(x,a)\geq\mu_{\mathrm{min}}$, with $\mu_{\mathrm{min}}>0$.

######  Assumption 3.

The learning rates satisfy the conditions
$\sum_{t=0}^{\infty}\alpha_{t}=\infty$ and
$\sum_{t=0}^{\infty}\alpha_{t}^{2}<\infty$.

The existence of a solution is guaranteed by Corollary 1, whose proof resorted
to Banach’s fixed-point theorem and Proposition 1. To establish global
asymptotic stability, we make use of a Lyapunov argument. Then, we have the
following result.

######  Theorem 1.

There exists $N$ such that, for all $n$ larger than $N$, the sequence of
$\omega_{t}^{n}$ is such that

$\displaystyle\lim_{t\to\infty}\left\lVert\tilde{\omega}^{n}-\omega_{t}^{n}\right\rVert_{2}=0.$

The result establishes conditions under which multi $Q$-learning converges to
the unique solution of the fixed-point equation of the projected multi-Bellman
operator (1). The assumptions are commonplace [Tsitsiklis and Van Roy, 1996,
Carvalho et al., 2020, Melo et al., 2008]. Assumptions 1 and 3 are mild.
Assumption 2 is the most restrictive of the three, as it requires the data
distribution to have no shift during training. In practice, that is usually
not the case. For example it is common that throughout the interaction of the
agent with the environment, the policy used to collect data changes in
response to changes in the approximated value function. Consequently, in
general, the samples are not i.i.d. to a fixed distribution. Nevertheless, we
can use replay buffers to slow down the data distribution shift. In the limit,
the case of offline reinforcement learning, where the replay buffer is
completed before reinforcement learning starts, the distribution is indeed
fixed and samples are independent and identically distributed. Nevertheless,
we do believe our result still holds if the data distribution, while changing
in response to the reinforcement learning, converges.

For performing the maximization in the target for the update of multi
$Q$-learning, we require the ability to simulate transitions and rewards. For
our experiments, we assume access to a simulator. We highlight the limitation
in Section 7.1. Nevertheless, we highlight that it is possible to use a
learned model of the transitions and rewards. Such use would not harm the
convergence guarantees of multi $Q$-learning. In fact, it is even possible to
use non-parametric models, such as replay buffers, to sample transitions and
rewards, without prejudice of the convergence established. It is also possible
to concurrently learn parametric models in a supervised way, even though the
theoretical analysis for the extension to this model-learning interaction
would require additional mathematical machinery.

We finish the section with a sketch of the proof of Theorem 1, referring to
the appendix for details.

###### Proof.

Under assumptions 1, 2 and 3, respectively on the data distribution, the
features and the learning rates, multi $Q$-learning satisfies conditions under
which a stochastic approximation algorithm converges to the equilibrium of the
associated dynamical system described in Section 2.

We consider the result of Borkar [2008] that we reproduce in the supplementary
material as Theorem  ‣ A.2.1. Therein, we identify four conditions that we
need to prove that hold for multi $Q$-learning.

First, the expected update must be a smooth function of the parameters
$\omega$. To verify this condition, we consider, for some $n\in\mathbb{N}$,
the expected update map $g:\mathbb{R}^{k}\to\mathbb{R}^{k}$ such that

$\displaystyle
g(\omega)=\mathbb{E}\left[\phi(x,a)\left(\tau^{n}(\omega)-q_{\omega}(x,a)\right)\right]$

and show that it is a Lipschitz function of the parameters in Lemma 2.

Second, the expected difference between the expected update and the actual
update, i.e., the noise, must equal zero when conditioned on the past, have
bounded expectation and bounded variance. We consider the noise sequence
$\\{m_{t}\\}_{t\in\mathbb{N}}$ such that

$\displaystyle
m_{t+1}=\phi(x_{t},a_{t})\left(\tau^{n}_{t+1}-q_{\omega_{t}}(x_{t},a_{t})\right)-g(\omega_{t})$

and verify it forms a martingale difference sequence with bounded variance in
Lemma 3.

Third, in Lemma 4, we show that, for sufficiently large $N$ and $n\geq N$, the
o.d.e.

$\displaystyle\dot{\omega}=g(\omega)$

has a unique and globally asymptotically stable equilibrium
$\tilde{\omega}^{n}$ that solves the fixed-point equation

$\displaystyle\omega=\mathbb{E}\left[\phi\left(x,a\right)\phi^{T}\left(x,a\right)\right]^{-1}\mathbb{E}\left[\phi\left(x,a\right)\tau^{n}(\omega)\right].$

To establish the existence and uniqueness of a solution we use Corollary 1,
which in turn uses Banach’s fixed-point theorem and Proposition 1. To
establish global asymptotic stability, we make a Lyapunov argument. We
establish the result for all $n\geq N$ with
$N=-\log_{\gamma}\left(\frac{\sigma_{\mathrm{max}}\phi_{\mathrm{max}}^{2}}{\mu_{\mathrm{min}}}\right)$.
We do not say, however, that this is the minimum $N$ such that result would
hold. Specifically, we do not guarantee our convergence result is the tightest
possible.

The first three conditions ensure that, if the updates remain bounded, they
converge to $\tilde{\omega}^{n}$ [Borkar, 2008, Chapter 2]. The fourth
condition, that we verify in Lemma 5, ensures such boundedness.

Having verified the conditions of Theorem  ‣ A.2.1, we are able to conclude
that, for sufficiently large $N$, the sequence of $\omega_{t}^{n}$ generated
by multi $Q$-learning converges to $\tilde{\omega}^{n}$ with probability 1. ∎

##  5 Experiments

First, we evaluate multi $Q$-learning for growing $n$ first in the task of
approximating $q^{*}$. We use the classic counter-examples for the convergence
of $Q$-learning with linear function approximation. Then, we consider the task
of using a learned approximation of $q^{*}$ to select actions. We use the
classic control environments. For the function approximation space, we use
discretized Gaussian features. We use an $\epsilon$-greedy policy where
$\epsilon$ decays linearly from 100% to 5% during the first half of
interactions and remains constant afterwards. We use a replay buffer with 20%
of the total number of timesteps used for the environment. We further detail
hyperparameters used for each environment in the corresponding paragraph. We
average the results across five runs, with standard deviation intervals, and
plot a moving average of the last $5\%$ of the total number of time steps.

###  5.1 Classic counter-examples

##### $\omega\to 2\omega$

The $\omega\to 2\omega$ classic counter-example is due to Tsitsiklis and Van
Roy [1996]. Here, the MDP has two states $y_{1}$ and $y_{2}$ and only one
action $b_{1}$. Performing the action on any of the two states always takes
the agent to the second state. The reward received is always zero. Therefore,
$q^{*}$ is zero. To approximate $q^{*}$ we consider features
$\phi:\mathcal{X}\times\mathcal{A}\to\mathbb{R}$ such that
$\phi(y_{1},b_{1})=1$ and $\phi(y_{2},b_{1})=2$. The projection of $q^{*}$ is
$\omega^{*}=0$ and $q_{\omega^{*}}$ equals the solution $q^{*}$. $\omega^{*}$
also verifies the Bellman fixed-point equation
$q_{\omega^{*}}=\operatorname*{Proj}\left(\mathbf{H}q_{\omega^{*}}\right)$.
Regardless, considering a discount factor of $0.9$ and a learning rate of
$10^{-2}$, when the distribution over states and actions is uniform, the
parameters of $Q$-learning, that is multi $Q$-learning with $n=1$, diverge to
infinity. Figure 1(a) shows that for sufficiently large $n$, specifically
$n=4$, we have convergence to the correct solution.

##### Star

The Star classic counter-example is due to Baird [1995]. Here, the MDP has six
states $y_{1}$ to $y_{6}$ and two actions $b_{1}$ and $b_{2}$. The first
action always takes the agent two the last state, the second action takes the
agent to any of the first five states uniformly. The reward received is always
zero. Therefore, $q^{*}$ is zero. To approximate $q^{*}$ we consider features
$\phi:\mathcal{X}\times\mathcal{A}\to\mathbb{R}^{13}$ such that, for $j$
between $1$ and $6$, for all $i$ between $1$ and $13$
$\phi_{i}(y_{j},b_{2})=\mathbf{1}(i=j+1)$, for $i$ between $2$ and $6$
$\phi_{i}(y_{j},b_{1})=2\cdot\mathbf{1}(i=j+1)$, for $j$ between $1$ and $5$
$\phi_{1}(y_{j},b_{1})=\mathbf{1}(j\leq 5)$ and $\phi_{1}(y_{6},b_{1})=2$,
$\phi_{i}(y_{j},b_{1})=0$ otherwise. The projection of $q^{*}$ is
$\omega^{*}=0$ and $q_{\omega^{*}}$ equals the solution $q^{*}$. $\omega^{*}$
also verifies the Bellman fixed-point equation
$q_{\omega^{*}}=\operatorname*{Proj}\left(\mathbf{H}q_{\omega^{*}}\right)$.
Despite the apparently benign conditions, considering a discount factor of
$0.995$ and a learning rate of $10^{-2}$, when the distribution over states
and action is generated by selecting the first action one sixth of the times
and the second action five sixths of the times, the parameters of
$Q$-learning, that is multi $Q$-learning with $n=1$, diverge to infinity.
Figure 1(b) shows that for sufficiently large $n$, specifically $n=4$, we have
convergence to the correct identically zero solution.

(a) $\omega\to 2\omega$.

(b) Star.

Figure 1: Classic counter-examples. The $x$-axis shows the number of
environment steps. The $y$-axis shows the estimate of $q$-values of the state
visited. In both environments, $n=4$ was necessary and sufficient to achieve
convergence to the exact optimal $q$-values which are identically zero.

###  5.2 Classic control

##### Cartpole

Cartpole is a classic control problem proposed by Barto et al. [1983], where a
cart balances a pole. The actions of the agent are to push the cart left or
right. The state space is a four-tuple with the position and velocity of the
cart and the angle and angular velocity of the pole. The reward is always one
unless the pole falls and the agent reaches a terminal state with reward zero.
During training, episodes last at most five hundred interactions. We use
Gaussian features in $\mathbb{R}^{16}$, obtained by discretizing each
dimension of the state space in two, a discount factor of $0.99$ and a
learning rate of $3\cdot 10^{-2}$. Figure 2(a) shows the results. $Q$-learning
can not perform. When $n\geq 2$, multi $Q$-learning is able to balance the
pole and collect rewards.

##### Mountaincar

Mountaincar is a classic control problem proposed by Moore [1990] where a car
must climb a valley. The actions of the agent are to push the car left, push
the car right or do nothing. The state space is a double of position and
velocity of the car. The reward is always minus one unless the car is at the
top of the valley, after which the agent reaches a terminal state with reward
zero. During training, episodes last a maximum of two hundred interactions. We
use Gaussian features in $\mathbb{R}^{256}$ obtained by discretizing each
dimension of the state space in sixteen, a discount factor of $0.99$ and a
learning rate of $3\cdot 10^{-3}$. Figure 2(b) shows the results. For all $n$,
multi $Q$-learning is able to select actions to successfully climb the hill
and solve the problem.

##### Acrobot

Acrobot is a classic control problem proposed by Sutton [1995] where a joint
actuates two links such that one end is fixed and the other is free. The
actions of the agent are to apply a negative torque to the joint, apply a
positive torque to the joint or do nothing. The state space is the six-tuple
composed of sine, cosine and angular velocity of each link. The reward is
always minus one unless the free end of the links reaches a target height,
after which the agent reaches a terminal state with reward zero. During
training, each episode last a maximum number of five hundred interactions. We
use Gaussian features in $\mathbb{R}^{4096}$ obtained by discretizing each
dimension of the state space in four, a discount factor of $0.99$ and a
learning rate of $3\cdot 10^{-3}$. Figure 2(c) shows the results. As $n$
increases, the performance of multi $Q$-learning increases and becomes more
stable.

(a) Cartpole.

(b) Mountaincar.

(c) Acrobot.

Figure 2: Classic control problems. The $x$-axis shows the number of
environment steps. The $y$-axis shows the average return achieved over 30
evaluation episodes. We can see that, as $n$ increases, the performance of
multi $Q$-learning with linear function approximation remains or improves.

##  6 Related work

###  6.1 Convergence results

We analyze results on the convergence of $Q$-learning with linear function
approximation. A few works provide conditions under which the standard
$Q$-learning method converges. Others, propose a different learning objective
and thus result in significantly modified variants of $Q$-learning, which are
the gradient-TD methods. More recently, other works exploit the finding that
regularization can ensure convergence of the $Q$-learning updates. From a
different perspective, a few works have analyzed the impact of lookahead in
policy improvement and evalutation steps.

##### Convergence conditions

Around the time the divergence of $Q$-learning was established, some works
aimed at reaching conditions under which $Q$-learning or small variants of it
would converge. The first works proposed restrictions of the function
approximation spaces themselves. They establish that with some specific
choices of features, $Q$-learning is guaranteed to converge [Singh et al.,
1994, Ormoneit and Sen, 2002, Szepesvári and Smart, 2004b]. The linear
architectures considered across the three works are extensions of what would
be the one-hot representation in the tabular case. Afterwards, another work
considered again general linear function approximation architectures. Melo et
al. [2008] prove that $Q$-learning with linear function approximation
converges if the distribution of state-action pairs the agent uses to learn is
sufficiently close to the distribution that the optimal policy would induce.
Such case restricts the convergence of $Q$-learning closer to on-policy
settings.

##### Gradient-TD methods

Instead of finding conditions under which $Q$-learning converges, a different
line of works proposes to take a step back and modify the objective that
$Q$-learning is trying to solve. Maei et al. [2010] propose to perform full-
gradient descent on a different objective, called the projected Bellman error.
The resulting algorithm, called Greedy-GQ, is part of a class of gradient-TD
methods. Being a full gradient method, Greedy-GQ is provably convergent to a
minimum in the linear approximation space. However, the method can converge to
strictly local minima and there is no guarantee that the resulting greedy
policy is a good control policy [Scherrer, 2010]. Gradient-TD methods are also
less efficient than semi-gradient methods [Mahadevan et al., 2014, Du et al.,
2017].

##### Regularized methods

The problem of divergence of $Q$-learning with function approximation was
significantly revived after an empirical success story of $Q$-learning with
deep neural networks [Mnih et al., 2015]. One of the components of the
renowned deep $Q$-network (DQN) therein is a target network that aims at
compensating the instability generated by the $Q$-learning updates. While the
DQN is not provably convergent, its empirical success inspired theoretical
results. The works of Carvalho et al. [2020], Zhang et al. [2021] and Chen et
al. [2022] provided convergence guarantees for variants with target networks.
Additionally, another work points out that the target network can be seen as a
regularizer Piché et al. [2021]. As hinted by Farahmand [2011], several works
prove that various forms of regularization of the $Q$-values or the parameters
themselves can stabilize $Q$-learning, resulting in a convergent algorithms
[Zhang et al., 2021, Lim et al., 2022, Agarwal et al., 2021]. However, the
introduction of any of the regularizers biases the limit solution encountered.

##### Non-linear function approximation

The behaviour of $Q$-learning with linear function approximation has been the
focus of several theoretical works. In practice, however, $Q$-learning is
mostly used with non-linear function approximation, especially through neural
networks [Mnih et al., 2015]. Still, there are works that address this more
general setting. A recent work suggests a loss function that is decreasing
over time, assuming the neural network converges to a target network at each
step [Wang and Ueda, 2021]. However, having a loss function that is
monotonically decreasing does not imply that neither the parameters of the
approximator are converging nor that the $Q$-values are converging. Cai et al.
[2019] and Xu and Gu [2020] provide finite-time analysis of $Q$-learning with
over-parameterized neural networks that imply that as the size of the network
grows to infinity, convergence is guaranteed at a sub-linear rate. We note
that as the size of the network grows to infinity, the learning architecture
also grows closer to a tabular representation. Therefore, despite interesting,
the results do not imply convergence when a practical neural network is
employed.

###  6.2 Lookahead, planning and model-based reinforcement learning

The multi-Bellman operator considered relates to other operators that
lookahead. The multi $Q$-learning algorithm relates to other planning and
model-based reinforcement learning algorithms.

##### Lookahead

In the context of policy iteration, several works hinted at the theoretical
benefits of lookahead in the tabular case De Asis et al. [2018], Efroni et al.
[2018a]. Efroni et al. [2018b] then identified a problem with soft policy
improvement for lookahead policies, which happens if function approximation is
used. Specifically, contrarily to what happens with a single-step policy
improvement step, a multistep policy improvement step is not necessarily
monotonically increasing. However, Efroni et al. [2020] and Winnicki and
Srikant [2022] respectively provide finite-time and asymptotic results for
lookahead in approximate policy iteration. Our work differs both on the
problem side and on the solution side. On the problem side, we focus on the
problem of divergence of $Q$-learning, a value-based algorithm, when used with
linear function approximation architectures that are not tables. The projected
multi-Bellman operator that we introduced differs from ones in the referred
works in that it is designed for evaluation of the optimal policy, not
evaluating or improving on a given policy.

##### Planning and model-based reinforcement learning

Multi $Q$-learning can be casted under the umbrella of multi-step real time
dynamic programming algorithms, as defined by Efroni et al. [2018b] and
discussed in Moerland et al. [2020]. Such algorithms integrate planning and
learning and have several successful practical applications [Silver et al.,
2017, 2018]. We refer to the survey of Moerland et al. [2023] for varied
interesting algorithms that include $Q(\sigma)$ [De Asis et al., 2018], tree-
backup [Precup, 2000] and multi-step expected SARSA [Sutton and Barto, 2018].
While most such algorithms are policy-based and work on-policy, requiring
separate value and policy networks and behavior-dependent solutions, in our
case, we have an off-policy, value-based algorithm. Moreover, multi
$Q$-learning plans exclusively at training time—planning is not necessary in
order to select an action to execute. Multi $Q$-learning plans with fixed
depth and full breadth, which is a rather unexplored setting according to
[Moerland et al., 2023]. Specifically, the depth is not adaptive nor full and
every action is tried on every state along a planning tree. Unfortunately, we
do not believe adaptive depth or limited breadth would result in convergence.
The setting could, however, bring computational benefits that could make multi
$Q$-learning more practical.

##  7 Conclusion

In conclusion, our work has made significant contributions to addressing the
convergence challenge in $Q$-learning with linear function approximation. By
introducing the multi-Bellman operator and demonstrating its contractive
nature, we have paved the way for improved convergence properties. The
proposed multi $Q$-learning algorithm effectively approximates the fixed-point
solution of the projected multi-Bellman operator. Importantly, we have shown
that the algorithm converges under relatively mild conditions. The
implications of our findings extend beyond this study, as they represent a
substantial breakthrough in the problem of convergence in $Q$-learning with
linear function approximation. Our work has the potential to inspire further
advancements in theory and algorithm development within the field of
reinforcement learning research.

We highlight two limitations of our work below. Afterwards, we link them with
future work.

###  7.1 Limitations

Even though our algorithm can be combined with models that are learned
concurrently to the reinforcement learning update, in our experiments, we used
a known model of the environment. It is not the case that such known model is
always available in applications.

Besides, multi $Q$-learning plans by performing every action on every reached
state along trajectories of $n$ steps. Thus, the computational cost of
performing an update grows exponentially with $n$, where the base for the
exponent is the size of the action space.

###  7.2 Future work

There are several techniques for learning a model of the environment. For
example, we can learn the model previously or concurrently to reinforcement
learning; the model can be exact or inexact; the model can be parametric or
non-parametric. Multi $Q$-learning can be combined with any of the mentioned
model-based approaches in order to remove the need for a known model.

Multi $Q$-learning does not hold so benign properties when we are unable to
perform every action on every state along $n$ step trajectories. In case only
some actions are performed on each state, we cannot show convergence to the
solution to an appropriate fixed-point equation. Nevertheless, we expect that,
in some cases, the computational benefits of not performing every action on
every state to outweigh the theoretical comfort. A practical analysis of this
trade-off would be valuable.

It would also be interesting to analyze multi $Q$-learning with non-linear
function approximation, theoretically and empirically. Specifically, under
which conditions and function approximation architectures would our
convergence result still hold? How would multi $Q$-learning with non-linear
function approximation compare, in practice, with relevant policy-free
reinforcement learning algorithms such as the DQN [Mnih et al., 2015]?

## References

  * Agarwal et al. [2021] Naman Agarwal, Syomantak Chaudhuri, Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli.  Online target q-learning with reverse experience replay: Efficiently finding the optimal policy for linear mdps.  _arXiv preprint arXiv:2110.08440_ , 2021.
  * Baird [1995] Leemon Baird.  Residual algorithms: Reinforcement learning with function approximation.  In _Proceedings of the 12th International Conference on Machine Learning_ , pages 30–37, 1995.
  * Barto et al. [1983] Andrew G Barto, Richard S Sutton, and Charles W Anderson.  Neuronlike adaptive elements that can solve difficult learning control problems.  _IEEE transactions on systems, man, and cybernetics_ , (5):834–846, 1983.
  * Borkar [2008] Vivek Borkar.  _Stochastic Approximation: A Dynamical Systems Viewpoint_.  Cambridge University Press, 2008.
  * Boyan and Moore [1995] Justin A. Boyan and Andrew W. Moore.  Generalization in reinforcement learning: Safely approximating the value function.  In _Advances in Neural Information Processing Systems 7_ , pages 369–376, 1995.
  * Cahill [2011] Andy Cahill.  _Catastrophic forgetting in reinforcement-learning environments_.  PhD thesis, University of Otago, 2011.
  * Cai et al. [2019] Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang.  Neural temporal-difference learning converges to global optima.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/98baeb82b676b662e12a7af8ad9212f6-Paper.pdf.
  * Carvalho et al. [2020] Diogo S. Carvalho, Francisco S. Melo, and Pedro A. Santos.  A new convergent variant of q-learning with linear function approximation.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Chen et al. [2022] Zaiwei Chen, John Paul Clarke, and Siva Theja Maguluri.  Target network and truncation overcome the deadly triad in q-learning.  _arXiv preprint arXiv:2203.02628_ , 2022.
  * De Asis et al. [2018] Kristopher De Asis, J Hernandez-Garcia, G Holland, and Richard Sutton.  Multi-step reinforcement learning: A unifying algorithm.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Du et al. [2017] Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou.  Stochastic variance reduction methods for policy evaluation.  In _International Conference on Machine Learning_ , pages 1049–1058. PMLR, 2017.
  * Efroni et al. [2018a] Yonathan Efroni, Gal Dalal, Bruno Scherrer, and Shie Mannor.  Beyond the one-step greedy approach in reinforcement learning.  In _International Conference on Machine Learning_ , pages 1387–1396. PMLR, 2018a.
  * Efroni et al. [2018b] Yonathan Efroni, Gal Dalal, Bruno Scherrer, and Shie Mannor.  Multiple-step greedy policies in approximate and online reinforcement learning.  _Advances in Neural Information Processing Systems_ , 31, 2018b.
  * Efroni et al. [2020] Yonathan Efroni, Mohammad Ghavamzadeh, and Shie Mannor.  Online planning with lookahead policies.  _Advances in Neural Information Processing Systems_ , 33:14024–14033, 2020.
  * Farahmand [2011] Amir-massoud Farahmand.  Regularization in reinforcement learning.  2011\.
  * Gordon [2001] Geoffrey J. Gordon.  Reinforcement learning with function approximation converges to a region.  In _Advances in neural information processing systems_ , pages 1040–1046, 2001.
  * Lim et al. [2022] Han-Dong Lim, Do Wan Kim, and Donghwan Lee.  Regularized q-learning.  _arXiv preprint arXiv:2202.05404_ , 2022.
  * Maei et al. [2010] Hamid R. Maei, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S. Sutton.  Toward off-policy learning control with function approximation.  In _Proceedings of the 27th International Conference on Machine Learning_ , pages 719–726, 2010.
  * Mahadevan et al. [2014] Sridhar Mahadevan, Bo Liu, Philip Thomas, Will Dabney, Steve Giguere, Nicholas Jacek, Ian Gemp, and Ji Liu.  Proximal reinforcement learning: A new theory of sequential decision making in primal-dual spaces.  _arXiv preprint arXiv:1405.6757_ , 2014.
  * Melo and Ribeiro [2007] Francisco S Melo and M Isabel Ribeiro.  Q-learning with linear function approximation.  In _Learning Theory: 20th Annual Conference on Learning Theory, COLT 2007, San Diego, CA, USA; June 13-15, 2007. Proceedings 20_ , pages 308–322. Springer, 2007.
  * Melo et al. [2008] Francisco S. Melo, Sean Meyn, and M. Isabel Ribeiro.  An analysis of reinforcement learning with function approximation.  In _Proceedings of the 25th International Conference on Machine learning_ , pages 664–671, 2008.
  * Mnih et al. [2015] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.  Human-level control through deep reinforcement learning.  _nature_ , 518(7540):529–533, 2015.
  * Moerland et al. [2020] Thomas M Moerland, Anna Deichler, Simone Baldi, Joost Broekens, and Catholijn M Jonker.  Think too fast nor too slow: the computational trade-off between planning and reinforcement learning.  _arXiv preprint arXiv:2005.07404_ , 2020.
  * Moerland et al. [2023] Thomas M Moerland, Joost Broekens, Aske Plaat, Catholijn M Jonker, et al.  Model-based reinforcement learning: A survey.  _Foundations and Trends® in Machine Learning_ , 16(1):1–118, 2023.
  * Moore [1990] Andrew William Moore.  Efficient memory-based learning for robot control.  Technical report, University of Cambridge, 1990.
  * Ormoneit and Sen [2002] Dirk Ormoneit and Śaunak Sen.  Kernel-based reinforcement learning.  _Machine learning_ , 49(2):161–178, 2002.
  * Piché et al. [2021] Alexandre Piché, Joseph Marino, Gian Maria Marconi, Christopher Pal, and Mohammad Emtiyaz Khan.  Beyond target networks: Improving deep $q$-learning with functional regularization.  _arXiv preprint arXiv:2106.02613_ , 2021.
  * Precup [2000] Doina Precup.  Eligibility traces for off-policy policy evaluation.  _Computer Science Department Faculty Publication Series_ , page 80, 2000.
  * Puterman [2005] Martil L. Puterman.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  John Wiley & Sons, 2005.
  * Scherrer [2010] Bruno Scherrer.  Should one compute the temporal difference fix point or minimize the bellman residual? the unified oblique projection view.  _arXiv preprint arXiv:1011.4362_ , 2010.
  * Silver et al. [2017] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al.  Mastering the game of go without human knowledge.  _nature_ , 550(7676):354–359, 2017.
  * Silver et al. [2018] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al.  A general reinforcement learning algorithm that masters chess, shogi, and go through self-play.  _Science_ , 362(6419):1140–1144, 2018.
  * Singh et al. [1994] Satinder Singh, Tommi Jaakkola, and Michael Jordan.  Reinforcement learning with soft state aggregation.  _Advances in neural information processing systems_ , 7, 1994.
  * Sutton and Barto [2018] Richard Sutton and Andrew Barto.  _Reinforcement Learning: An Introduction_.  MIT Press, 2nd edition, 2018.
  * Sutton [1995] Richard S Sutton.  Generalization in reinforcement learning: Successful examples using sparse coarse coding.  _Advances in neural information processing systems_ , 8, 1995.
  * Szepesvári and Smart [2004a] C. Szepesvári and W. Smart.  Interpolation-based $Q$-learning.  In _Proceedings of the 21st International Conference on Machine learning_ , pages 100–107, 2004a.
  * Szepesvári and Smart [2004b] Csaba Szepesvári and William D Smart.  Interpolation-based q-learning.  In _Proceedings of the twenty-first international conference on Machine learning_ , page 100, 2004b.
  * Tsitsiklis and Van Roy [1996] John N. Tsitsiklis and Benjamin Van Roy.  Feature-based methods for large scale dynamic programming.  _Machine Learning_ , 22:59–94, 1996.
  * van Hasselt et al. [2018] Hado van Hasselt, Yotam Doron, Florian Strub, Matteo Hessel, Nicolas Sonnerat, and Joseph Modayil.  Deep reinforcement learning and the deadly triad.  _CoRR_ , abs/1812.02648, 2018.
  * Wang and Ueda [2021] Zhikang T. Wang and Masahito Ueda.  A convergent and efficient deep q network algorithm.  _arXiv preprint arXiv:2106.15419_ , 2021.
  * Watkins and Dayan [1992] Christopher JCH Watkins and Peter Dayan.  Q-learning.  _Machine learning_ , 8(3):279–292, 1992.
  * Winnicki and Srikant [2022] Anna Winnicki and R Srikant.  Reinforcement learning with unbiased policy evaluation and linear function approximation.  In _2022 IEEE 61st Conference on Decision and Control (CDC)_ , pages 801–806. IEEE, 2022.
  * Xu and Gu [2020] Pan Xu and Quanquan Gu.  A finite-time analysis of q-learning with neural network function approximation.  In _International Conference on Machine Learning_ , pages 10555–10565. PMLR, 2020.
  * Zhang et al. [2021] Shangtong Zhang, Hengshuai Yao, and Shimon Whiteson.  Breaking the deadly triad with a target network.  _arXiv preprint arXiv:2101.08862_ , 2021.

##  Appendix A Appendix

In this appendix, we provide proof of all theoretical results presented in the
main document. In Section A.2, we reproduce a general convergence result for
stochastic approximation that was referred to in Section 2 of the main
document. In Section A.3, we provide proof for the theoretical results we
presented in Section 3, referring to properties of the multi-Bellman operator
proposed. Finally, in Section A.4, we prove the convergence result for multi
$Q$-learning that appeared in Section 4 of the main document. The latter proof
combined the general stochastic approximation convergence result of Section
A.2 and the properties of the multi-Bellman operator of Section A.3.

###  A.2 Background

In this section, we reproduce a general convergence result on stochastic
approximation algorithms, as our own convergence result presented as Theorem 1
in the main paper heavily relies on it.

####  A.2.1 Stochastic approximation

Here we reproduce a convergence result for stochastic approximation[Borkar,
2008, Chapter 2]. The result establishes conditions under which a stochastic
approximation algorithm converges.

######  Theorem 0.

Let us suppose that the following hold for the stochastic approximation
setting of Sec. 2.

  1. 1.

The map $g:\mathbb{R}^{k}\to\mathbb{R}^{k}$ such that

$\displaystyle
g(\omega)=\mathbb{E}\left[\phi\left(z\right)\left(\tau(\omega)-g_{\omega}(x,a)\right)\right]$

is Lipschitz;

  2. 2.

The sequence of $m_{t}$ such that

$\displaystyle
m_{t+1}=\phi(z_{t})\left(\tau_{t+1}-g_{\omega_{t}}(z_{t})\right)-g(\omega_{t});$

is a martingale difference sequence with respect to
$\\{(\tau_{s},\omega_{s}):s\leq t\\}$ and is such that

$\displaystyle\mathbb{E}\left[\left\lVert
m_{t+1}\right\rVert^{2}\mid\\{(\tau_{s},\omega_{s}):s\leq t\\}\right]\leq
c_{m}\left(1+\left\lVert\omega_{t}\right\rVert^{2}\right).$

  3. 3.

The o.d.e

$\displaystyle\dot{\omega}=g(\omega)$

has a unique and globally asymptotically stable equilibrium $\omega^{*}$ such
that

$\displaystyle\omega^{*}=\mathbb{E}\left[\phi\left(z\right)\phi^{T}\left(z\right)\right]^{-1}\mathbb{E}\left[\phi\left(z\right)\tau(\omega)\right];$

  4. 4.

The map $g_{c}:\mathbb{R}^{k}\to\mathbb{R}^{k}$ such that

$\displaystyle g_{c}(\omega)=\frac{g(c\omega)}{c}$

is such that $\lim_{c\to\infty}\left\lVert
g_{c}(\omega)-g_{\infty}(\omega)\right\rVert$ uniformly on compacts for a
$g_{\infty}:\mathbb{R}^{k}\to\mathbb{R}^{k}$ and that the origin is the unique
and globally asymptotically stable equilibrium of

$\displaystyle\dot{\omega}=g_{\infty}(\omega).$

Then, the sequence of stochastic approximation updated $\omega_{t}$ converges
to $\omega^{*}$.

The result we reproduced guarantees that if, on expectation, the stochastic
approximation update is smooth, the noise is well-behaved, the underlying
dynamical system is asymptotically stable and the iterates remain bounded, the
stochastic approximation update converges to the solution of the underlying
dynamical system.

The proof of the convergence of the proposed multi $Q$-learning appears later,
on Section A.4, and heavily resorts on Theorem  ‣ A.2.1. In the next section,
we prove the results that appeared in Section 3 of the main document. The
results are useful properties of the multi-Bellman operator.

###  A.3 Multi-Bellman operator

In this section, we reproduce the theoretical results established in Section 3
and present their proofs. The results refer to useful properties of the multi-
Bellman operator.

We start with Lemma 1 of the main paper, which establishes that the multi-
Bellman operator with parameter $n$ is contractive and that the contraction
improves exponentially as $n$ increases.

######  Lemma 1.

The operator $\mathbf{H}^{n}$ is a contraction in the $\infty$-norm with
contraction factor $\gamma^{n}$.

###### Proof.

We establish the result by induction. First, we show that $\mathbf{H}$
contracts in the $\infty$-norm. We start by writing the expression
$\left\lVert\mathbf{H}q-\mathbf{H}p\right\rVert_{\infty}$ in simpler terms,
where $q$ and $p$ are value functions.

$\displaystyle\left\lVert\mathbf{H}q-\mathbf{H}p\right\rVert_{\infty}$
$\displaystyle=\max_{x,a}\left|\mathbb{E}\left[r(x,a)+\gamma\max_{a^{\prime}\in\mathcal{A}}q\left(x^{\prime},a^{\prime}\right)\right]-\mathbb{E}\left[r(x,a)+\gamma\max_{a^{\prime}\in\mathcal{A}}p\left(x^{\prime},a^{\prime}\right)\right]\right|$
$\displaystyle=\gamma\max_{x,a}\left|\mathbb{E}\left[\max_{a^{\prime}\in\mathcal{A}}q\left(x^{\prime},a^{\prime}\right)-\max_{a^{\prime}\in\mathcal{A}}p\left(x^{\prime},a^{\prime}\right)\right]\right|.$

Next, we make use of Jensen’s inequality to establish that

$\displaystyle\left\lVert\mathbf{H}q-\mathbf{H}p\right\rVert_{\infty}$
$\displaystyle\leq\gamma\max_{x,a}\mathbb{E}\left[\left|\max_{a^{\prime}\in\mathcal{A}}q\left(x^{\prime},a^{\prime}\right)-\max_{a^{\prime}\in\mathcal{A}}p\left(x^{\prime},a^{\prime}\right)\right|\right].$

We use that the absolute difference of maxima is less or equal than the maxima
of absolute difference.

$\displaystyle\left\lVert\mathbf{H}q-\mathbf{H}p\right\rVert_{\infty}$
$\displaystyle\leq\gamma\max_{x,a}\mathbb{E}\left[\max_{a^{\prime}\in\mathcal{A}}\left|q\left(x^{\prime},a^{\prime}\right)-p\left(x^{\prime},a^{\prime}\right)\right|\right].$

Then, we use that the expectation of a random function is less or equal than
its maximum.

$\displaystyle\left\lVert\mathbf{H}q-\mathbf{H}p\right\rVert_{\infty}$
$\displaystyle\leq\gamma\max_{x^{\prime}\in\mathcal{X}}\max_{a^{\prime}\in\mathcal{A}}\left|q\left(x^{\prime},a^{\prime}\right)-p\left(x^{\prime},a^{\prime}\right)\right|$
$\displaystyle=\gamma\max_{x^{\prime},a^{\prime}}\left|q\left(x^{\prime},a^{\prime}\right)-p\left(x^{\prime},a^{\prime}\right)\right|$
$\displaystyle=\gamma\left\lVert q-p\right\rVert_{\infty}$

Now, we make the induction step for
$\mathbf{H}^{n+1}=\mathbf{H}\mathbf{H}^{n}$, observing that

$\displaystyle\left\lVert\mathbf{H}\left(\mathbf{H}^{n}q\right)-\mathbf{H}\left(\mathbf{H}^{n}p\right)\right\rVert_{\infty}$
$\displaystyle\leq\gamma\left\lVert\mathbf{H}^{n}q-\mathbf{H}^{n}p\right\rVert_{\infty}$
$\displaystyle=\gamma\gamma^{n}\left\lVert q-p\right\rVert_{\infty}$
$\displaystyle=\gamma^{n+1}\left\lVert q-p\right\rVert_{\infty}.$

We conclude the proof. ∎

Now, we prove Proposition 1, stating the contractiveness of the projected
multi-Bellman operator.

######  Proposition 1.

There exists $N\in\mathbb{N}$ such that, for all $n\geq N$,
$\operatorname*{Proj}\mathbf{H}^{n}$ is a contraction in the $\mu$-norm.

###### Proof.

We want to show that there exists $\lambda:\mathbb{N}\to\mathbb{R}$ such that

$\displaystyle\left\lVert\operatorname*{Proj}\left(\mathbf{H}^{n}q\right)-\operatorname*{Proj}\left(\mathbf{H}^{n}p\right)\right\rVert\leq\lambda(n)\left\lVert
q-p\right\rVert$

and such that, for all $n$ greater than an existing $N$, $\lambda(n)$ is
strictly smaller than 1.

We start by showing that $\operatorname*{Proj}$ satisfies

$\displaystyle\left\lVert\operatorname*{Proj}q-\operatorname*{Proj}p\right\rVert\leq\phi^{2}_{\mathrm{max}}\sigma_{\mathrm{max}}\left\lVert
q-p\right\rVert_{\infty}.$

To see that, we start by recalling that

$\displaystyle\left(\operatorname*{Proj}q\right)(x,a)=\phi^{T}(x,a)\mathbb{E}\left[\phi(x,a)\phi^{T}(x,a)\right]^{-1}\mathbb{E}\left[\phi(x,a)q(x,a)\right].$

Then, we have that

$\displaystyle\left\lVert\operatorname*{Proj}q-\operatorname*{Proj}p\right\rVert=\sqrt{\mathbb{E}\left[\left(\phi^{T}(x,a)\mathbb{E}\left[\phi(x,a)\phi^{T}(x,a)\right]^{-1}\mathbb{E}\left[\phi(x,a)\left(q(x,a)-p(x,a)\right)\right]\right)^{2}\right]}.$

Now, we make use of a Cauchy-Schwarz inequality to say that

$\displaystyle\left\lVert\operatorname*{Proj}q-\operatorname*{Proj}p\right\rVert\leq\sqrt{\mathbb{E}\left[\left\lVert\phi^{T}(x,a)\mathbb{E}\left[\phi(x,a)\phi^{T}(x,a)\right]^{-1}\right\rVert_{2}^{2}\left\lVert\mathbb{E}\left[\phi(x,a)\left(q(x,a)-p(x,a)\right)\right]\right\rVert_{2}^{2}\right]}$

and we can write

$\displaystyle\left\lVert\operatorname*{Proj}q-\operatorname*{Proj}p\right\rVert$
$\displaystyle\leq\sqrt{\mathbb{E}\left[\left\lVert\phi^{T}(x,a)\mathbb{E}\left[\phi(x,a)\phi^{T}(x,a)\right]^{-1}\right\rVert_{2}^{2}\right]}\sqrt{\left\lVert\mathbb{E}\left[\phi(x,a)\left(q(x,a)-p(x,a)\right)\right]\right\rVert_{2}^{2}}$
$\displaystyle=\sqrt{\mathbb{E}\left[\left\lVert\phi^{T}(x,a)\mathbb{E}\left[\phi(x,a)\phi^{T}(x,a)\right]^{-1}\right\rVert_{2}^{2}\right]}\left\lVert\mathbb{E}\left[\phi(x,a)\left(q(x,a)-p(x,a)\right)\right]\right\rVert_{2}$

Now, we use the definition of the matrix norm induced by the euclidean norm in
$\mathbb{R}^{k}$ for the first term and Jensen’s inequality. We obtain that

$\displaystyle\left\lVert\operatorname*{Proj}q-\operatorname*{Proj}p\right\rVert$
$\displaystyle\leq\sqrt{\mathbb{E}\left[\left\lVert\phi(x,a)\right\rVert_{2}^{2}\left\lVert\mathbb{E}\left[\phi(x,a)\phi^{T}(x,a)\right]^{-1}\right\rVert_{2}^{2}\right]}\mathbb{E}\left[\left\lVert\phi(x,a)\left(q(x,a)-p(x,a)\right)\right\rVert_{2}\right]$
$\displaystyle\leq\sqrt{\phi^{2}_{\mathrm{max}}\sigma_{\mathrm{max}}^{2}}\cdot\mathbb{E}\left[\left\lVert\phi(x,a)\right\rVert_{2}\left|q(x,a)-p(x,a)\right|\right]$
$\displaystyle\leq\phi_{\mathrm{max}}^{2}\sigma_{\mathrm{max}}\left\lVert
q-p\right\rVert_{\infty}.$

To conclude the proof, we start by combining the inequality we just
established and Lemma 1.

$\displaystyle\left\lVert\operatorname*{Proj}\left(\mathbf{H}^{n}q\right)-\operatorname*{Proj}\left(\mathbf{H}^{n}p\right)\right\rVert$
$\displaystyle\leq\phi^{2}_{\mathrm{max}}\sigma_{\mathrm{max}}\left\lVert\mathbf{H}^{n}q-\mathbf{H}^{n}p\right\rVert_{\infty}$
$\displaystyle\leq\phi^{2}_{\mathrm{max}}\sigma_{\mathrm{max}}\gamma^{n}\left\lVert
q-p\right\rVert_{\infty}$

Let us consider $\mu_{\mathrm{min}}$ the probability of the least likely
state-action pair according to distribution $\mu$, assuming all state-action
pairs have a non-zero probability of being visited—that is bigger or equal
than $\mu_{\mathrm{min}}$ (we are defining the constant in revised Assumption
2 of the revised paper). Finally, we use that $\left\lVert
q\right\rVert_{\infty}\leq\frac{1}{\mu_{\mathrm{min}}}\left\lVert
q\right\rVert$ and finish the proof by using
$\lambda(n)=\frac{\phi^{2}_{\mathrm{max}}\sigma_{\mathrm{max}}}{\mu_{\mathrm{min}}}\gamma^{n}$.
It is true that $\lambda(n)<1$ for all $n\geq N$ when we consider
$N=\lceil-\log_{\gamma}\left(\frac{\phi_{\mathrm{max}}^{2}\sigma_{\mathrm{max}}}{\mu_{\mathrm{min}}}\right)\rceil$.111$\lceil\cdot\rceil:\mathbb{R}^{+}\to\mathbb{N}$
is the ceiling function, giving the smallest natural that is larger or equal
to its argument. ∎

######  Proposition 2.

For all $n\geq N$, where $N$ is identified in Corollary 1,
$\tilde{\omega}^{n}$ is such that

$\displaystyle\left\lVert
q^{*}-q_{\tilde{\omega}^{n}}\right\rVert\leq\frac{1}{1-\frac{\sigma_{\mathrm{max}}\phi_{\mathrm{max}}^{2}}{\mu_{\mathrm{min}}}\gamma^{n}}\left\lVert
q^{*}-q_{\omega^{*}}\right\rVert,$ (3)

where
$\sigma_{\mathrm{max}}=\left\lVert\mathbb{E}\left[\phi(x,a)\phi^{T}(x,a)\right]^{-1}\right\rVert_{2}$
and $\phi_{\mathrm{max}}=\max_{x,a}\left\lVert\phi(x,a)\right\rVert_{2}$.

In Proposition 2 of the main text submitted, the constant $\mu_{\mathrm{min}}$
is missing. We are adding it in the revised version of the manuscript.

###### Proof.

Let us use the triangle inequality with vertex $q_{\omega^{*}}$.

$\displaystyle\left\lVert
q^{*}-q_{\tilde{\omega}^{n}}\right\rVert\leq\left\lVert
q^{*}-q_{\omega^{*}}\right\rVert+\left\lVert
q_{\omega^{*}}-q_{\tilde{\omega}^{n}}\right\rVert.$

Now we focus on the second term of the right-hand side above. We have that

$\displaystyle\left\lVert q_{\omega^{*}}-q_{\tilde{\omega}^{n}}\right\rVert$
$\displaystyle=\left\lVert\operatorname*{Proj}\left(\mathbf{H}^{n}q^{*}\right)-\operatorname*{Proj}\left(\mathbf{H}^{n}q_{\tilde{\omega}^{n}}\right)\right\rVert.$

From Proposition 1, we have that

$\displaystyle\left\lVert q_{\omega^{*}}-q_{\tilde{\omega}^{n}}\right\rVert$
$\displaystyle\leq\frac{\sigma_{\mathrm{max}}\phi_{\mathrm{max}}^{2}}{\mu_{\mathrm{min}}}\gamma^{n}\left\lVert
q^{*}-q_{\tilde{\omega}^{n}}\right\rVert.$

We can conclude the result taking algebraic operations. ∎

###  A.4 Multi $Q$-learning

In this section, we prove Theorem 1, that we reproduce below for convenience.

######  Theorem 1.

There exists $N$ such that, for all $n$ larger than $N$, the sequence of
$\omega_{t}^{n}$ is such that

$\displaystyle\lim_{t\to\infty}\left\lVert\tilde{\omega}^{n}-\omega_{t}^{n}\right\rVert_{2}=0.$

To establish the result, we verify that we are in the conditions where Theorem
‣ A.2.1 holds. We do so by proving the following lemmas, one for each of the
asumptions of the theorem.

######  Lemma 2.

The map $g:\mathbb{R}^{k}\to\mathbb{R}^{k}$ such that

$\displaystyle
g(\omega)=\mathbb{E}\left[\phi(x,a)\left(\tau^{n}(\omega)-q_{\omega^{n}}(x,a)\right)\right]$

is Lipschitz.

###### Proof.

We start by writing

$\displaystyle\left\lVert g(\omega)-g(\theta)\right\rVert_{2}$
$\displaystyle=\left\lVert\mathbb{E}\left[\phi(x,a)\left(\tau^{n}(\omega)-q_{\omega}(x,a)\right)\right]-\mathbb{E}\left[\phi(x,a)\left(\tau^{n}(\theta)-q_{\theta}(x,a)\right)\right]\right\rVert_{2}$
$\displaystyle\leq\left\lVert\mathbb{E}\left[\phi(x,a)\left(\tau^{n}(\omega)-\tau^{n}(\theta)\right)\right]\right\rVert_{2}+\left\lVert\mathbb{E}\left[\phi(x,a)\left(q_{\theta}(x,a)-q_{\omega}(x,a)\right)\right]\right\rVert_{2}.$

For the first term, we can observe that it equals.

$\displaystyle\left\lVert\mathbb{E}\left[\phi(x,a)\phi^{T}(x,a)\right]\left(\operatorname*{Proj}\left(\mathbf{H}^{n}q_{\omega}\right)-\operatorname*{Proj}\left(\mathbf{H}^{n}q_{\theta}\right)\right)\right\rVert_{2}$

Using Jensen’s and Cauchy-Schwarz inequality and Proposition 1, we conclude
that

$\displaystyle\left\lVert\mathbb{E}\left[\phi(x,a)\left(\tau^{n}(\omega)-\tau^{n}(\theta)\right)\right]\right\rVert_{2}$
$\displaystyle\leq\mathbb{E}\left[\left\lVert\phi(x,a)\right\rVert_{2}\left|\tau^{n}(\omega)-\tau^{n}(\theta)\right|\right]$
$\displaystyle\leq\sigma_{\mathrm{max}}\phi^{2}_{\mathrm{max}}\gamma^{n}\left\lVert
q_{\omega}-q_{\theta}\right\rVert_{\infty}$
$\displaystyle\leq\frac{\sigma_{\mathrm{max}}\phi^{3}_{\mathrm{max}}}{\mu_{\mathrm{min}}}\gamma^{n}\left\lVert\omega-\theta\right\rVert_{2}$

Now we can take care of the second term by making use of Jensen’s and Cauchy-
Schwarz’ inequality.

$\displaystyle\left\lVert\mathbb{E}\left[\phi(x,a)\left(q_{\theta}(x,a)-q_{\omega}(x,a)\right)\right]\right\rVert_{2}$
$\displaystyle\leq\mathbb{E}\left[\left\lVert\phi(x,a)\right\rVert_{2}\left|q_{\theta}(x,a)-q_{\omega}(x,a)\right|\right]$
$\displaystyle\leq\phi_{\mathrm{max}}\left\lVert
q_{\theta}-q_{\omega}\right\rVert_{\infty}$
$\displaystyle\leq\frac{\phi_{\mathrm{max}}^{2}}{\mu_{\mathrm{min}}}\left\lVert\omega-\theta\right\rVert_{2}.$

Finally, by considering the sum of the coefficients from the first and second
terms, we have that

$\displaystyle\left\lVert g(\omega)-g(\theta)\right\rVert_{2}$
$\displaystyle\leq\frac{\sigma\phi^{3}_{\mathrm{max}}\gamma^{n}+\phi^{2}_{\mathrm{max}}}{\mu_{\mathrm{min}}}\left\lVert\omega-\theta\right\rVert_{2},$

or, equivalently, that $g$ is Lipschitz continuous. ∎

######  Lemma 3.

The sequence of $m_{t}$ such that

$\displaystyle
m_{t+1}=\phi(x_{t},a_{t})\left(\tau^{n}_{t+1}-g_{\omega_{t}}(x_{t},a_{t})\right)-g(\omega_{t})$

is a martingale difference sequence with respect to
$\\{(\tau^{n}_{s},\omega_{s}):s\leq t\\}$ and is such that

$\displaystyle\mathbb{E}\left[\left\lVert
m_{t+1}\right\rVert^{2}\mid\\{(\tau^{n}_{s},\omega_{s}):s\leq t\\}\right]\leq
c_{m}\left(1+\left\lVert\omega_{t}\right\rVert^{2}\right).$

###### Proof.

A martingale difference sequence has zero expectation conditioned on the past.
Such condition is evident once we consider Assumption 2. Then, a martingale
difference sequence also has finite first moment. That becomes evident when we
observe that every term on the definition is bounded. Finally, since, again,
every term on the definition is also bounded, the second moment is bounded. ∎

######  Lemma 4.

The o.d.e

$\displaystyle\dot{\omega}=g(\omega)$

has a unique and globally asymptotically stable equilibrium $\omega^{*}$ such
that

$\displaystyle\omega^{*}=\mathbb{E}\left[\phi\left(x,a\right)\phi^{T}\left(x,a\right)\right]^{-1}\mathbb{E}\left[\phi\left(x,a\right)\tau^{n}(\omega^{*})\right].$

###### Proof.

We already know that the equilibrium $\omega^{*}$ exists and is unique. Let us
consider a Lyapunov function $l:\mathbb{R}^{k}\to\mathbb{R}$ such that
$l(\omega)=\frac{1}{2}\left\lVert\omega^{*}-\omega\right\rVert^{2}$. Existence
of $\omega^{*}$ is guaranteed from Banach’s fixed-point theorem and
Proposition 1. It is clear that $l(\omega)=0$ if $\omega=\omega^{*}$ and that
$l(\omega)>0$ if $\omega\neq\omega^{*}$. Now, we show that $\dot{l}(\omega)<0$
if $\omega\neq\omega^{*}$.

We start by noticing that $\dot{l}(\omega)=\nabla l\cdot\dot{\omega}$. Since
$\nabla l=-\left(\omega^{*}-\omega\right)$ and $\dot{\omega}=g(\omega)$, we
have that

$\displaystyle\dot{l}(\omega)=-\left(\omega^{*}-\omega\right)g(\omega).$

Since $g(\omega^{*})=0$, it is also true that

$\displaystyle\dot{l}(\omega)$
$\displaystyle=-\left(\omega^{*}-\omega\right)\left(g\left(\omega\right)-g\left(\omega^{*}\right)\right)$

For now, let us focus on the second term of the right hand side and write

$\displaystyle g(\omega)-g(\omega^{*})$
$\displaystyle=\mathbb{E}\left[\phi(x,a)\left(\tau^{n}(\omega)-\tau^{n}(\omega^{*})\right)\right]-\mathbb{E}\left[\phi(x,a)\left(q_{\omega^{*}}(x,a)-q_{\omega}(x,a)\right)\right]$

Let us make two assertions, one for each of the terms on the right-hand side
of the equation. First,

$\displaystyle\left\lVert\mathbb{E}\left[\phi(x,a)\left(\tau^{n}(\omega)-\tau^{n}(\omega^{*})\right)\right]\right\rVert_{2}=\left\lVert\mathbb{E}\left[\phi(x,a)\left(\tau^{n}(\omega^{*})-\tau^{n}(\omega)\right)\right]\right\rVert_{2}.$

Using Jensen’s and Cauchy-Schwarz’ inequality, we get that

$\displaystyle\left\lVert\mathbb{E}\left[\phi(x,a)\left(\tau^{n}(\omega)-\tau^{n}(\omega^{*})\right)\right]\right\rVert_{2}$
$\displaystyle\leq\mathbb{E}\left[\left\lVert\phi(x,a)\right\rVert_{2}\left|\tau^{n}(\omega^{*})-\tau^{n}(\omega)\right|\right]$

and, using the fact that
$\left|\max_{z}f(z)-\max_{z}g(z)\right|\leq\max_{z}\left|f(z)-g(z)\right|$,
consequently that

$\displaystyle\left\lVert\mathbb{E}\left[\phi(x,a)\left(\tau^{n}(\omega)-\tau^{n}(\omega^{*})\right)\right]\right\rVert_{2}$
$\displaystyle\leq\phi_{\mathrm{max}}\gamma^{n}\left\lVert
q_{\omega^{*}}-q_{\omega}\right\rVert_{\infty}$
$\displaystyle\leq\frac{\phi_{\mathrm{max}}^{2}}{\mu_{\mathrm{min}}}\gamma^{n}\left\lVert\omega^{*}-\omega\right\rVert$

Second, we have that

$\displaystyle\mathbb{E}\left[\phi(x,a)\left(q_{\omega^{*}}(x,a)-q_{\omega}(x,a)\right)\right]=\mathbb{E}\left[\phi(x,a)\phi^{T}(x,a)\right]\left(\omega^{*}-\omega\right).$

Having established the two assertions mentioned, we make use of them in the
following.

$\displaystyle\dot{l}(\omega)$
$\displaystyle=-(\omega^{*}-\omega)\mathbb{E}\left[\phi(x,a)\left(\tau^{n}(\omega)-\tau^{n}(\omega^{*})\right)\right]-$
$\displaystyle\qquad\qquad-(\omega^{*}-\omega)\mathbb{E}\left[\phi(x,a)\phi^{T}(x,a)\right](\omega^{*}-\omega)$
$\displaystyle\leq\left\lVert\left(\omega^{*}-\omega\right)\mathbb{E}\left[\phi(x,a)\left(\tau^{n}(\omega)-\tau^{n}(\omega^{*})\right)\right]\right\rVert_{2}-$
$\displaystyle\qquad\qquad-(\omega^{*}-\omega)\mathbb{E}\left[\phi(x,a)\phi^{T}(x,a)\right](\omega^{*}-\omega)$
$\displaystyle\leq\frac{\phi_{\mathrm{max}}^{2}}{\mu_{\mathrm{min}}}\gamma^{n}\left\lVert\omega^{*}-\omega\right\rVert^{2}_{2}-\lambda_{\mathrm{max}}\left\lVert\omega^{*}-\omega\right\rVert^{2}_{2}$
$\displaystyle=\left(\frac{\phi_{\mathrm{max}}^{2}}{\mu_{\mathrm{min}}}\gamma^{n}-\lambda_{\mathrm{max}}\right)\left\lVert\omega^{*}-\omega\right\rVert_{2}^{2},$

where $\lambda_{\mathrm{max}}$ is the largest eigenvalue of the covariance
matrix $\mathbb{E}\left[\phi(x,a)\phi^{T}(x,a)\right]$. The expression is
negative if n is large enough. That concludes the proof.

∎

######  Lemma 5.

The map $g_{c}:\mathbb{R}^{k}\to\mathbb{R}^{k}$ such that

$\displaystyle g_{c}(\omega)=\frac{g(c\omega)}{c}$

is such that $\lim_{c\to\infty}\left\lVert
g_{c}(\omega)-g_{\infty}(\omega)\right\rVert=0$ uniformly on compacts for some
$h_{\infty}:\mathbb{R}^{k}\to\mathbb{R}^{k}$ and that the origin is the unique
and globally asymptotically stable equilibrium of

$\displaystyle\dot{\omega}=g_{\infty}(\omega).$

###### Proof.

Let us expand the definition and obtain

$\displaystyle g_{c}(\omega)$
$\displaystyle=\frac{\mathbb{E}\left[\phi(x,a)\left(\tau^{n}-q_{c\omega^{n}}(x,a)\right)\right]}{c}$
$\displaystyle=\frac{\mathbb{E}\left[\phi(x,a)\tau^{n}\right]}{c}-\mathbb{E}\left[\phi(x,a)q_{\omega}(x,a)\right].$

As $c\to\infty$, we have that $g_{c}(\omega)\to g_{\infty}(\omega)$ uniformly,
using $g_{\infty}(\omega)=-\mathbb{E}\left[\phi(x,a)q_{\omega}(x,a)\right]$.

We then have that the ordinary differential equation

$\displaystyle\dot{\omega}$ $\displaystyle=g_{\infty}(\omega)$
$\displaystyle=-\mathbb{E}\left[\phi(x,a)q_{\omega}(x,a)\right]$
$\displaystyle=-\mathbb{E}\left[\phi(x,a)\phi^{T}(x,a)\right]\omega$

is linear and time-invariant. Since the matrix above is invertible, we have
that the origin is its unique and globally asymptotically stable equilibrium.
We conclude the result. ∎