This paper designs novel nonparametric Bellman mappings in
reproducing kernel Hilbert spaces (RKHSs) for
reinforcement learning (RL). The proposed mappings benefit
from the rich approximating properties of RKHSs, adopt no
assumptions on the statistics of the data owing to their
nonparametric nature, require no knowledge on transition
probabilities of Markov decision processes, and may
operate without any training data. Moreover, they allow
for sampling on-the-fly via the design of trajectory
samples, re-use past test data via experience replay,
effect dimensionality reduction by random Fourier
features, and enable computationally lightweight
operations to fit into efficient online or time-adaptive
learning. The paper offers also a variational framework to
design the free parameters of the proposed Bellman
mappings, and shows that appropriate choices of those
parameters yield several popular Bellman-mapping
designs. As an application, the proposed mappings are
employed to offer a novel solution to the problem of
countering outliers in adaptive filtering. More
specifically, with no prior information on the statistics
of the outliers and no training data, a policy-iteration
algorithm is introduced to select online, per time
instance, the “optimal” coefficient $p$ in the
least-mean-$p$-power-error method. Numerical tests on
synthetic data showcase, in most of the cases, the
superior performance of the proposed solution over several
RL and non-RL schemes.

Bellman mappings, reinforcement learning, nonparametric,
adaptive filtering, outliers.

§ INTRODUCTION

§.§ Motivation: Adaptive filters against outliers

The least-squares (LS) error/loss plays a pivotal role in
signal processing, e.g., adaptive filtering
(AdaFilt) <cit.>, and machine
learning <cit.>. Notwithstanding, the LS
loss is notoriously sensitive to the presence of
outliers <cit.>, where outliers are defined as
contaminating data that do not adhere to a nominal
data-generation model, and are often viewed as random
variables (RVs) with non-Gaussian heavy tailed
distributions, , $\alpha$-stable
ones <cit.>. To counter
outliers in AdaFilt, non-LS losses, such as the $p$-norm
($2 > p \in \RealPP$) <cit.> and correntropy <cit.> have been studied (henceforth,
$\RealPP$ will denote the set of all positive real numbers).

Consider the classical linear data-generation model in
$y_n = \vectgr{\theta}_*^{\intercal} \vect{x}_n + o_n$,
where $n\in\IntegerP$ denotes discrete time ($\IntegerP$ is
the set of all non-negative integers),
$\vectgr{\theta}_* \in \Real^{L}$ is the $L\times 1$
vector/system with real-valued entries that needs to be
estimated (estimandum), $o_n$ is the real-valued RV which
models outliers/noise, $(\vect{x}_n, y_n)$ stands for the
input-output pair of available data, where
$\vect{x}_n \in \Real^{L}$ and $y_n \in \Real$, and
$\intercal$ denotes vector/matrix transposition. The
online-learning setting is considered, that is, data
$(\vect{x}_n, y_n)_{n \in \IntegerP}$ appear to the
user/agent in a streaming fashion, a pair
$(\vect{x}_n, y_n)$ per time index $n$, while no training
data are available. All operations in the following
discussion are performed online, so that the time index $n$
coincides with the iteration index of the proposed
reinforcement-learning (RL) algorithm.

The least-mean-$p$-power-error (LMP)
method <cit.> counters outliers by applying
the classical stochastic-gradient-descent (SGD) iteration to
the $p$-power error/loss
$\lvert y_n - \vect{x}_n^{\intercal} \vectgr{\theta}
\rvert^p$, $p \in [1,2]$, to generate the following sequence
of estimates $(\vectgr{\theta}_n)_{n\in\mathbb{N}}$ of the
estimandum $\vectgr{\theta}_*$: for an arbitrarily fixed
$\vectgr{\theta}_0 \in \Real^L$,

\begin{align}
\vectgr{\theta}_{n+1} \coloneqq \vectgr{\theta}_n + \rho p
\lvert e_n \rvert^{p-1} \sign(e_n)\, \vect{x}_n
\,, \label{LMP}
\end{align}

$e_n \coloneqq y_n - \vect{x}_n^{\intercal}
\vectgr{\theta}_n = \vect{x}_n^{\intercal} (
\vectgr{\theta}_* - \vectgr{\theta}_n ) + o_n$ is the
classical a-priori error <cit.>, $\rho$ is
the learning rate (step size), and
$\sign(\cdot) \colon \Real \to \{ \pm 1\}$ provides the sign
of a real number. The $p$-power loss is a convex function of
$\vectgr{\theta}$ for $p \in [1,2]$. If $p = 1$ and $2$,
then (<ref>) boils down to the classical sign-LMS and
LMS, respectively <cit.>. The $p$-power
loss remains convex even if $p > 2$, but such values of $p$
may amplify large-variance outliers $o_n$ via
$\lvert e_n \rvert^{p-1}$ and inflict instabilities
on (<ref>).

Intuition suggests that the choice of $p$ in (<ref>)
should be based on the probability density function (PDF) of
the RV $o_n$. Indeed, if $o_n$ obeys a Gaussian PDF, then
$p = 2$ yields the $2$-power loss which agrees with the
maximum-likelihood criterion. Nevertheless, having prior
knowledge on the statistics of the outliers is usually
infeasible in practice, as in cases where no training data
are available, and in dynamic environments where the
statistics of the outliers may be time varying.

Combinations of LMP filters, with different $p$-power
losses <cit.> as well as forgetting
factors <cit.>, have been proposed to surmount
the problem of pinpointing the “best” $p$, but still, the
problem remains and translates to that of pinpointing the
“best” combination, which again depends on the underlying
outlier PDF. A data-driven solution to the
problem of dynamically selecting $p$, per time
instance $n$, from streaming data with no prior
knowledge on the statistics of $o_n$ and no
training data seems to be missing from the AdaFilt

§.§ Contributions

Building on its short preliminary
version <cit.>, this manuscript offers a
solution to the aforementioned AdaFilt problem by
reinforcement learning
(RL) <cit.>. In RL, an agent takes a
decision/action based on feedback provided by the
surrounding environment on the agent's past actions. RL is a
sequential-decision-making framework with the goal of
minimizing the long-term loss/price $Q$ (a.k.a. Q-function)
to be paid by the agent for its own decisions. Central to an
RL design are the Bellman mappings (B-Maps) which
operate on the Q-functions, have deep roots in dynamic
programming <cit.>, and a far-reaching range of applications
which extend from autonomous navigation, robotics, resource
planning, sensor networks, biomedical imaging, and can reach
even to gaming <cit.>.

Rather than adopting a popular off-the-shelf RL method, this
manuscript designs a novel family of B-Maps
(<ref>) to solve the AdaFilt
problem at hand. The contributions of this work are
summarized as follows.

* In contrast with the majority of existing B-Maps,
which are defined in Banach spaces (no inner product
available), the proposed B-Maps, as well as the
Q-functions, are specifically defined in reproducing
kernel Hilbert spaces (RKHSs) to take advantage of the
rich approximating properties of
RKHSs <cit.> and the
flexibility an RKHS inner product brings into the design
of loss functions and constraints.

* The proposed B-Maps possess ample degrees of freedom;
indeed, <ref> offers a variational
framework to identify their free parameters, and shows
that by appropriately designing those parameters, several
popular B-Maps fall as special cases under the umbrella of
the proposed design. <ref> provides
a thorough literature review on the prior art of B-Maps.

* Owing to the kernel functions, the proposed B-Maps are
rendered nonparametric, with no need for statistical
priors and assumptions on the data, in an effort to reduce
as much as possible the bias inflicted on data modeling by
the user <cit.>. The price to be paid
for this distribution-free approach is that the dimensions
of the Q-function estimates scale with the number of
observed data. To surmount this “curse of
dimensionality,” a dimensionality-reduction strategy
based on random Fourier features is offered in

*  The proposed B-Maps
allow for sampling on-the-fly via the design of trajectory
samples in <ref>, do not require any
knowledge on transition probabilities of Markov decision
processes, and enable computationally lightweight
operations to fit into the online or time-adaptive
learning required by the AdaFilt problem at hand.

* For the first time in the literature, this manuscript
and its short preliminary version <cit.>
offer an RL-based solution (<ref>) to the problem of
countering outliers in AdaFilt.

With regards to <ref>, it is worth
noting here that the recently popular deep learning (DeepL),
, <cit.>, offers an alternative parametric way of
designing rich approximating spaces for
Q-functions. However, this is achieved at the price of
requiring learning from training data prior to the online
mode of operation (test-stage), or even re-training during
the test-stage to address the often met scenario of facing
test data with different statistics than those of the
training data (dynamic environments). Such modes of learning
raise computational-complexity issues and discourage the
application of DeepL solutions to online modes of operation
where a small computational-complexity footprint is desired.

The proposed RL solution is built on a continuous state
space, because of the nature of $(\mathbf{x}_n, y_n)$. In
contrast with <cit.>, where the state space is
the high-dimensional $\Real^{2L+1}$, this study confines the
state space to the low-dimensional $\Real^4$. The action
space is considered to be discrete; an action is a value of
$p$ taken from a finite grid of the interval $[1, 2]$. The
well-known policy-iteration (PI)
strategy <cit.> is adopted in
<ref>, because of its well-documented merits (,
especially for continuous state spaces, over the popular
strategies of temporal-difference (TD) and
Q-learning <cit.>. To keep the
discussion simple, a quadratic loss on Q-functions is
defined via the proposed B-Maps, and the classical SGD rule
is applied to update the $Q$ estimates
(<ref>). To promote the use of past data,
experience replay <cit.> is employed in
<ref>, while <cit.> uses
rollout <cit.>.

Properties of the proposed B-Maps are established in
<Ref>, and a performance
analysis of <ref> is provided in
<ref>. Numerical tests on
synthetic data in <ref> support the theoretical
findings and demonstrate that the advocated framework
outperforms, in most of the cases, several RL and non-RL
schemes. Due to lack of space, all proofs are
included in the appendices of the manuscript.

§ NONPARAMETRIC BELLMAN MAPPINGS FOR RL

§.§ Notation and preliminaries

RL as a sequential-decision-making framework:
Identify the agent's policy $\mu(\cdot)$ (a decision- or
action-making function) which minimizes the total loss
($=$ one-step loss $+$ long-term loss) to be paid by the
agent for its sequence of

A continuous state space
$\mathfrak{S} \subset \Real^D$ is considered, with state
vector $\vect{s} \in \mathfrak{S}$, for some
$D\in \IntegerPP$ ($\IntegerPP$ is the set of all positive
integers). The action space is denoted by $\mathfrak{A}$,
with action $a\in \mathfrak{A}$. For convenience, the
state-action tuple is defined as
$\vect{z} \coloneqq (\vect{s}, a) \in \mathfrak{Z} \coloneqq
\mathfrak{S} \times \mathfrak{A}$. Moreover, let all
$\mathcal{M} \coloneqq \Set{ \mu(\cdot) \given \mu(\cdot)
\colon \mathfrak{S} \to \mathfrak{A} : \vect{s} \mapsto
\mu(\vect{s})}$, and define a policy
$\pi \in \Pi \coloneqq \mathcal{M}^{\IntegerP} \coloneqq
\Set{ (\mu_0, \mu_1, \ldots, \mu_n, \ldots) \given \mu_n\in
\mathcal{M}, n\in \IntegerP}$. Given $\mu\in \mathcal{M}$,
the stationary policy $\pi_{\mu} \in \Pi$ is defined as
$\pi_{\mu} \coloneqq ( \mu, \mu, \ldots, \mu, \ldots)$. By
abuse of notation, $\mu$ will hereafter denote also the
stationary policy $\pi_{\mu}$.

RL can be viewed as a sequential-decision framework; see
<ref>. In short, an agent, currently at state
$\vect{s}\in \mathfrak{S}$, takes an action/decision
$a\in \mathfrak{A}$ and transitions to a new state
$\vect{s}^{\prime} \in \mathfrak{S}$ with transition
(conditional) probability
$\Prob(\vect{s}^{\prime} \given \vect{s}, a)$ at the price
of the one-step loss $g(\vect{s}, a)$. Quantity
$Q(\vect{s}^{\prime}, \mu(\vect{s}^{\prime}))$ denotes the
long-term loss, or, the price to be paid if the
agent continues to take actions, from the state
$\vect{s}^{\prime}$ and on, according to the stationary
policy $\mu(\cdot)$. Typically,
$g(\cdot) \colon \mathfrak{Z}\to\Real$ and
$Q(\cdot) \colon \mathfrak{Z}\to\Real$ are considered points
of the functional Banach space $\mathcal{B}$ of all
(essentially) bounded functions, equipped with the
$\mathcal{L}_{\infty}$-norm <cit.>. Recall
that by definition a Banach space $\mathcal{B}$ is not
equipped with an inner product.

Departing from standard RL routes which revolve around
Banach spaces $\mathcal{B}$, this study considers a
reproducing kernel Hilbert space (RKHS)
$\mathcal{H}$ <cit.> as
the ambient space where $g$ and $Q$ belong to. The RKHS
$\mathcal{H}$ is a Hilbert space with inner product
$\innerp{\cdot}{\cdot}_{\mathcal{H}}$, norm
$\norm{\cdot}_{\mathcal{H}} \coloneqq
\innerp{\cdot}{\cdot}_{\mathcal{H}}^{1/2}$, and a
reproducing kernel
$\kappa(\cdot, \cdot): \mathfrak{Z}\times \mathfrak{Z} \to
\Real$ such that $\kappa(\vect{z}, \cdot)\in \mathcal{H}$,
$\forall \vect{z}\in \mathfrak{Z}$, and the
reproducing property holds true:
$Q(\vect{z}) = \innerp{Q}{\kappa(\vect{z},
\cdot)}_{\mathcal{H}}$, $\forall Q\in \mathcal{H}$,
$\forall \vect{z}\in \mathfrak{Z}$. Space $\mathcal{H}$ may
be infinite dimensional; , the case where
$\kappa(\cdot, \cdot)$ is a Gaussian
kernel <cit.>. For
compact notations, let the feature mapping
$\varphi(\vect{z}) \coloneqq \kappa(\vect{z},\cdot)$ and
$Q^{\intercal} Q^{\prime} \coloneqq
\innerp{Q}{Q^{\prime}}_{\mathcal{H}}$.

Finally, notation
$\mathcal{T}_{N} \coloneqq \{ (\vect{s}_i, a_i,
\vect{s}_i^{\prime}) \}_{i=1}^N \subset \mathfrak{S} \times
\mathfrak{A} \times \mathfrak{S}$, for $N \in \IntegerPP$,
will be used hereafter to denote a collection of trajectory
samples, with $\vect{s}_i^{\prime}$ being a potential
subsequent state of $\vect{s}_i$ after the agent takes
action $a_i$. Moreover, $g_i$ will stand for either
$g(\vect{s}_i, a_i, \vect{s}_i^{\prime})$ or
$g(\vect{s}_i, a_i)$, depending on the context of
discussion. For a reproducing kernel $\kappa(\cdot, \cdot)$
and its feature mapping $\varphi(\cdot)$, let for
$\vectgr{\Phi}_{\mathcal{T}_N} \coloneqq
[\varphi(\vect{z}_1), \ldots, \varphi(\vect{z}_N)]$, where
$\vect{z}_i \coloneqq (\vect{s}_i, a_i)$, and define then
$\vect{K}_{\mathcal{T}_N} \coloneqq
\vectgr{\Phi}_{\mathcal{T}_N}^{\intercal}
\vectgr{\Phi}_{\mathcal{T}_N}$ as the $N \times N$ kernel
matrix whose $(i,i^{\prime})$th entry is
$\kappa( \vect{z}_i, \vect{z}_{i^{\prime}})$. Moreover, let
$\vectgr{\Phi}_{\mu}^{\prime} \coloneqq [ \varphi(
\vect{s}_1^{\prime}, \mu( \vect{s}_1^{\prime} ) ), \ldots,
\varphi( \vect{s}_N^{\prime}, \mu( \vect{s}_N^{\prime} ) )
]$, and
$\vect{g} \coloneqq [ g(\vect{s}_1, a_1), \ldots,
g(\vect{s}_N, a_N) ]^{\intercal}$.

§.§ Prior art of Bellman mappings

The classical B-Maps are defined in a Banach space
$\mathcal{B}$ and quantify the total loss (= one-step loss +
expected long-term loss) to be paid by the agent when taking
action $a$ at state $\vect{s}$ <cit.>. More
$T_{\mu}^{\diamond}, T^{\diamond}\colon \mathcal{B} \to
\mathcal{B}$, where $\forall Q\in \mathcal{B}$,

\begin{align}
(T_{\mu}^{\diamond} Q)(\vect{s}, a)
& \coloneqq g( \vect{s}, a ) + \alpha
\expect_{\vect{s}^{\prime} \given (\vect{s}, a)} \{
Q(\vect{s}^{\prime}, \mu(\vect{s}^{\prime})) \}
\,, \label{classical.Bellman.mu} \\
(T^{\diamond} Q)(\vect{s}, a)
& \coloneqq g( \vect{s}, a ) + \alpha
\expect_{\vect{s}^{\prime} \given (\vect{s}, a)}
\{ \inf_{a^{\prime}\in \mathfrak{A}
}Q(\vect{s}^{\prime}, a^{\prime})
\}\,, \label{classical.Bellman.inf}
\end{align}

and where
$\expect_{\vect{s}^{\prime} \given (\vect{s}, a)}\{\cdot
\}$ stands for the conditional
expectation <cit.> over all
possible subsequent states $\vect{s}^{\prime}$ of
$\vect{s}$, conditioned on $(\vect{s}, a)$, and $\alpha$
is the discount factor with typical values in
$(0,1)$. Mapping (<ref>) refers to
the case where the agent takes actions according to the
stationary policy $\mu(\cdot)$,
while (<ref>) serves as a greedy
variation of (<ref>). Note
that (<ref>) can be recast in the
form of (<ref>) whenever the $\inf$
in (<ref>) is achievable:

(T^♢ Q)(s, a)

g( s, a ) + α_s^' (s, a)
{ Q(s^', μ_Q(s^'))

=        (T^♢_μ_Q Q)(s, a)  ,

where, given $Q$, the stationary policy $\mu_Q(\cdot)$ is
defined as
$\mu_Q(\vect{s}^{\prime}) \coloneqq \arg \min_{a^{\prime}\in
\mathfrak{A}} Q(\vect{s}^{\prime}, a^{\prime})$, so that
$Q(\vect{s}^{\prime}, \mu_Q(\vect{s}^{\prime})) =
\min_{a^{\prime}\in \mathfrak{A}} Q(\vect{s}^{\prime},

Given a mapping $T\colon \mathcal{B} \to \mathcal{B}$, its
fixed-point set is defined as
$\Fix T \coloneqq \{ Q\in \mathcal{B} \given TQ = Q\}$. It
is well known that $\Fix T_{\mu}^{\diamond}$ and
$\Fix T^{\diamond}$ play a central role in identifying the
policy which minimizes the total
loss <cit.>. Typically, the
discount factor $\alpha \in (0,1)$ to render
$T_{\mu}^{\diamond}, T^{\diamond}$
contractions <cit.>,
so that $\Fix T_{\mu}^{\diamond}$ and $\Fix T^{\diamond}$
become singletons <cit.>.

Motivated by the Nadaraya-Watson kernel
estimate <cit.>, and for a non-negative
and not necessarily reproducing kernel function
$\chi(\cdot, \cdot)\colon \mathfrak{S} \times \mathfrak{S}
\to \Real$, kernel-based (KB)RL <cit.> is built on the following B-Maps;
$\forall (\vect{s}, a) \in \mathfrak{Z}$,

\begin{align}
T_{\textnormal{KBRL}, \mu}(Q) (\vect{s},a)
& \coloneqq \smashoperator{\sum_{(\vect{s}_i, a_i,
\vect{s}_i^{\prime}) \in
\mathcal{T}_N^a}} \chi(\vect{s}, \vect{s}_i) \bigl(g_i
+ \alpha Q(\vect{s}_i^{\prime},
\mu(\vect{s}_i^{\prime}) ) \bigr) \,, \label{KBRL.mu}
\\
T_{\textnormal{KBRL}}(Q) (\vect{s},a)
& \coloneqq \smashoperator{\sum_{(\vect{s}_i, a_i,
\vect{s}_i^{\prime}) \in
\mathcal{T}_N^a}} \chi(\vect{s}, \vect{s}_i) \bigl(g_i
+ \alpha
\inf_{a^\prime\in\mathfrak{A}}Q(\vect{s}_i^{\prime},
a^{\prime}) \bigr) \,, \label{KBRL.inf}
\end{align}

$\mathcal{T}_N^a \coloneqq \Set{ (\vect{s}_i, a_i,
\vect{s}_i^{\prime})\in \mathcal{T}_N \given a_i = a }$,
$\mathcal{T}_N$ is typically considered to comprise
“historical” (training) trajectory data,
$g_i \coloneqq g(\vect{s}_i, a_i, \vect{s}_i^{\prime})$, and
$\chi$ needs to satisfy
$\sum_{(\vect{s}_i, a_i, \vect{s}_i^{\prime}) \in
\mathcal{T}_N^a} \chi(\vect{s}, \vect{s}_i) =
1$. Following <cit.>, a simple way to
enforce the previous constraint on $\chi$ for every
$\vect{s}\in \mathfrak{S}$ is via another non-negative
“mother” kernel function $\zeta(\cdot, \cdot)$:

\begin{align}
\chi(\vect{s}, \vect{s}_i) \coloneqq \frac{\zeta(\vect{s},
\vect{s}_i)} {\sum_{(\vect{s}_j,
a_j, \vect{s}_j^{\prime}) \in \mathcal{T}_N^a } \zeta
(\vect{s}, \vect{s}_j)} \,. \label{average.function.KBRL}
\end{align}

Even if $\zeta$ is a reproducing kernel of an RKHS
$\mathcal{H}$ and $Q\in \mathcal{H}$, due to the denominator
of (<ref>), there is no guarantee, in
general, that $\chi$, $T_{\textnormal{KBRL}, \mu}(Q)$, and
$T_{\textnormal{KBRL}}(Q)$ belong to
$\mathcal{H}$ <cit.>. For such a reason,
the discussion in <cit.> stays in a Banach space, with no use of
an RKHS inner product. The KBRL mappings (<ref>)
have been also adopted in <cit.>.

RKHSs were used as approximating spaces for conditional
expectations via distribution embeddings
in <cit.>, where, for example, the
existence of an $h_{(\vect{s}, a)}^{\mu} \in\mathcal{H}$
such that
$\innerp{Q} {h_{(\vect{s}, a)}^{\mu} }_{\mathcal{H}} =
\expect_{\vect{s}^{\prime} \given (\vect{s}, a)} \{
Q(\vect{s}^{\prime}, \mu(\vect{s}^{\prime})) \}$,
$\forall (\vect{s}, a) \in \mathfrak{Z}$, is demonstrated
under certain conditions. By tailoring the arguments
of <cit.> to the current context,
the B-Map
$\mathcal{H} \ni Q \mapsto T_{\textnormal{emb}, \mu}(Q)
(\vect{s}, a) \coloneqq g(\vect{s}, a) + \alpha
\innerp{Q}{\hat{h}_{(\vect{s}, a)}^{\mu} }_{\mathcal{H}}$
can be defined, with

\begin{align*}
\hat{h}_{(\vect{s}, a)}^{\mu}
\coloneqq \sum\nolimits_{i=1}^{N} \frac{c_{i}(\vect{s},
a)}{\sum_{j = 1}^{N} \lvert
c_{j}(\vect{s}, a) \rvert }
\varphi(\vect{s}_i^\prime, \mu(\vect{s}_i^\prime) ) \in
\mathcal{H} \,, % \label{emb.map.xi.hat}
\end{align*}

serving as a substitute for the unknown
$h_{(\vect{s}, a)}^{\mu}$, where
$\vect{c}(\vect{s}, a) \coloneqq [ c_1 (\vect{s}, a),
c_2(\vect{s}, a), \ldots, c_N(\vect{s}, a)]^{\intercal}
\coloneqq ( \vect{K}_{{\mathcal{T}_N}} + \sigma \vect{I}_N
)^{-1} \vectgr{\Phi}_{\mathcal{T}_N}^\intercal \varphi
(\vect{s}, a)$. Similarly to the discussion
following (<ref>), $T_{\textnormal{emb}, \mu}(Q)$
is not guaranteed in general to belong to $\mathcal{H}$,
even if $Q\in\mathcal{H}$, and as such,
$T_{\textnormal{emb}, \mu}(Q)$ is treated as an element of a
Banach space in <cit.>. Moreover,
notice that $\vect{c}(\vect{s}, a)$ needs to be computed at
each point $(\vect{s}, a)\in \mathfrak{Z}$, which poses
computational obstacles in cases where $\mathfrak{Z}$ is
either continuous or of massive cardinality. Further, the
previous ideas to approximate conditional expectations does
not seem to be straightforward in the case
of (<ref>), because the existence of
an $h_{(\vect{s}, a)}$ that satisfies
$\innerp{Q}{ h_{(\vect{s}, a)} }_{\mathcal{H}} =
\expect_{\vect{s}^{\prime} \given (\vect{s}, a)} \{
\inf_{a^{\prime}\in \mathfrak{A} } Q(\vect{s}^{\prime},
a^{\prime} ) \}$, and the linearity of the inner product,
would suggest that the previous conditional expectation is a
linear function of $Q$; however, this is not true in

In quest of an inner product and more standard formulations,
the least-squares policy evaluation (LSPE) method was
introduced in Euclidean spaces in <cit.>, and extended into potentially
infinite dimensional RKHSs
in <cit.>. The basic LSPE
iteration <cit.> can be recast as a
Bellman mapping by the following variational form: for fixed
$\mu \in \mathcal{M}$, $\sigma \in \RealP$, and
$\forall Q\in \mathcal{H}$,

T_LSPE, μ (Q)

min_ Q^' ∈ℋ
∑_i=1^N [ Q^'(z_i) -

- αQ(s_i^', μ(s_i^')) ]^2

+ σQ^' -
Q_ℋ^2    .

The explicit form of $T_{\textnormal{LSPE}, \mu} (Q)$ can be
found in <ref>. LSPE shows strong
connections with the classical temporal-difference (TD)
learning <cit.>, whose recursion
is an SGD step on the loss in (<ref>) for $N=1$ and
$\sigma = 0$. Motivated by (<ref>), the popular LS
temporal difference (LSTD) method <cit.> computes a fixed point
$Q_{\textnormal{LSTD}, \mu}\in \Fix T_{\textnormal{LSPE},
\mu}$, where

\begin{align}
& \Fix T_{\textnormal{LSPE}, \mu} \notag \\
& = \Set*{ Q\in\mathcal{H} \given (
\vectgr{\Phi}_{\mathcal{T}_N}
\vectgr{\Phi}_{\mathcal{T}_N}^{\intercal} - \alpha
\vectgr{\Phi}_{\mathcal{T}_N}
\vectgr{\Phi}_{\mu}^{\prime \intercal} ) Q =
\vectgr{\Phi}_{\mathcal{T}_N} \vect{g} }
\,; \label{fix.LSPE}
\end{align}

see <ref> for a
proof of (<ref>). That fixed point becomes unique
$\vect{K}_{\mathcal{T}_N} - \alpha
\vectgr{\Phi}_{\mu}^{\prime \intercal}
\vectgr{\Phi}_{\mathcal{T}_N}$ is invertible:

\begin{align}
Q_{\textnormal{LSTD}, \mu} = \vectgr{\Phi}_{\mathcal{T}_N}
(\vect{K}_{\mathcal{T}_N} - \alpha
\vectgr{\Phi}_{\mu}^{\prime \intercal}
\vectgr{\Phi}_{\mathcal{T}_N})^{-1} \vect{g}
\,, \label{fixed.point.LSPE}
\end{align}

where (<ref>) follows easily
from (<ref>) after using
$( \vectgr{\Phi}_{\mathcal{T}_N}
\vectgr{\Phi}_{\mathcal{T}_N}^{\intercal} - \alpha
\vectgr{\Phi}_{\mathcal{T}_N} \vectgr{\Phi}_{\mu}^{\prime
\intercal} )^{-1} \vectgr{\Phi}_{\mathcal{T}_N} =
\vectgr{\Phi}_{\mathcal{T}_N} (\vect{K}_{\mathcal{T}_N} -
\alpha \vectgr{\Phi}_{\mu}^{\prime \intercal}
\vectgr{\Phi}_{\mathcal{T}_N})^{-1}$. Interestingly, it has
been demonstrated that, in general, LSPE/LSTD perform better
than TD in numerical tests <cit.>.

The Bellman-residual (BR) approach <cit.> originates from a variational task, which
can be readily recast into the following form to fit the
current RKHS context:

T_BR, μ(Q)

min_ Q^' ∈ℋ
∑_i=1^N [ Q^'(z_i) -
g_i - αQ^'(s_i^', μ(s_i^')) ]^2

+ σQ^' - Q_ℋ^2

The explicit form of (<ref>) can be found in
<ref>. Interestingly,
$T_{\textnormal{BR}, \mu}(Q) = \prox_{f/(2\sigma)}(Q)$,
where the popular proximal mapping is defined as
$\prox_{f/(2\sigma)}(Q) \coloneqq \arg\min_{ Q^{\prime} \in
\mathcal{H} } f(Q^{\prime}) + 2\sigma \cdot (1/2)\norm{Q -
Q^{\prime}}_{\mathcal{H}}^2$ <cit.>, with
$f(Q^{\prime}) \coloneqq \sum\nolimits_{i=1}^{N} [
Q^{\prime}(\vect{z}_i) - g_i - \alpha
Q^{\prime}(\vect{s}_i^{\prime}, \mu (\vect{s}_i^{\prime}))
]^2$. Extensions to cases where the loss in (<ref>)
is further regularized by additional convex functions, such
as $\ell_1$-norm loss, for example, to impose structure onto
the desired solutions, can be found
in <cit.>.

§.§ New Bellman mappings in RKHSs

Hereafter, losses $g, Q$ are assumed to belong to an RKHS
$\mathcal{H}$. For some
$N_{\textnormal{av}} \in \IntegerPP$, consider the
state-space vectors
$\mathcal{S}_{\textnormal{av}} \coloneqq \Set{
\vect{s}_i^{\textnormal{av}} }_{i=1}^{N_{\textnormal{av}}}
\subset \mathfrak{S}$, chosen by the user to enable sampling
of trajectory samples on-the-fly to approximate the
conditional expectation
in (<ref>). Define also, for
convenience in notation and for a $\mu \in \mathcal{M}$,
$\vectgr{\Phi}_{\mu}^{\textnormal{av}} \coloneqq [
\varphi(\vect{s}_1^{\textnormal{av}},
\mu(\vect{s}_1^{\textnormal{av}})), \ldots,
\varphi(\vect{s}_{N_{\textnormal{av}}}^{\textnormal{av}},
\mu(\vect{s}_{N_{\textnormal{av}}}^{\textnormal{av}}))
]$. Consider also the user-defined
$\{\psi_i\}_{i=1}^{N_{\textnormal{av}}} \subset
\mathcal{H}$, with
$\vectgr{\Psi} \coloneqq [ \psi_1, \ldots,
\psi_{N_{\textnormal{av}}} ]$. Then, the proposed B-Maps
$T_{\mu}, T\colon \mathcal{H} \to \mathcal{H}$ are defined
as follows: $\forall Q\in \mathcal{H}$,
$\forall \mu\in \mathcal{M}$,

T_μ (Q)

g + α∑_i=1^N_av
Q (s^av_i,
μ(s^av_i) ) ·ψ_i

g + αΨ
Φ_μ^av ⊺ Q

g + α∑_i=1^N_av
inf_a_i ∈𝔄 Q
(s^av_i, a_i) ·ψ_i

g + αΨ

where $\vecinf_{\mathcal{S}_{\textnormal{av}}} (Q)$ is
defined as the $N_{\textnormal{av}} \times 1$ vector whose
$i$th entry is
$\inf \nolimits_{ a \in \mathfrak{A} } Q
(\vect{s}^{\textnormal{av}}_i, a )$. The reproducing
property of the inner product in $\mathcal{H}$ was used to
obtain the latter formulation in (<ref>). Let
also the $N_{\textnormal{av}} \times N_{\textnormal{av}}$
kernel matrices
$\vect{K}_{\Psi} \coloneqq \vectgr{\Psi}^{\intercal}
\vectgr{\Psi}$ and
$\vect{K}_{\mu}^{\textnormal{av}} \coloneqq
\vectgr{\Phi}_{\mu}^{\textnormal{av}\intercal}
\vectgr{\Phi}_{\mu}^{\textnormal{av}}$. Further, it is worth
noting that vectors $\mathcal{S}_{\textnormal{av}}$ may be
also used to incorporate training data
in (<ref>).

In contrast with several of the popular B-Map designs in
<ref> which are defined in Banach
spaces, the proposed (<ref>) are defined
directly in an RKHS $\mathcal{H}$. To highlight the ample
degrees of freedom and flexibility offered by the
user-defined $\{\psi_i\}_i$, the following proposition
demonstrates that by appropriately tuning the $\{\psi_i\}_i$
through a variational framework, the proposed
B-Maps (<ref>) yield the popular
designs (<ref>), (<ref>),
(<ref>), as well as <cit.> and
<cit.> as special cases.

(Variational framework for B-Maps) Consider the
user-defined loss function
$\mathcal{L}\colon \Real^N \times \Real^{ N\times
N_{\textnormal{av}} } \to \Real \colon (\vectgr{\gamma},
\vectgr{\Upsilon}) \mapsto \mathcal{L}(\vectgr{\gamma},
\vectgr{\Upsilon})$ and the regularizing function
$\mathcal{R}\colon \Real^N \times \Real^{ N\times
N_{\textnormal{av}} } \to \Real \colon (\vectgr{\gamma},
\vectgr{\Upsilon}) \mapsto \mathcal{R}(\vectgr{\gamma},
\vectgr{\Upsilon})$, and let
$(\vectgr{\gamma}_{\star}, \vectgr{\Upsilon}_{\star})$
stand for the minimizers of the following variational

(γ_⋆, Υ_⋆) ∈min_γ
∈^N, Υ∈^ N ×N_av
ℒ( γ,
Υ ) + σℛ(
γ, Υ )

where $\sigma \in \RealP$.

*  Consider the stationary
policy $\mu$ in (<ref>). Let
$\mu_{\star} \in\mathcal{M}$ be a stationary policy
s.t. $\mu_{\star}( \vect{s}_i ) \coloneqq a_i$ and
$\mu_{\star}( \vect{s}_i^{\prime} ) \coloneqq \mu (
\vect{s}_i^{\prime} )$,
$\forall i\in \Set{1, \ldots, N}$. Define also
$\vect{s}_i^{\textnormal{av}} \coloneqq \vect{s}_i$,
$\forall i\in \Set{1, \ldots, N}$, and
$\vect{s}_i^{\textnormal{av}} \coloneqq
\vect{s}_{i-N}^{\prime}$,
$\forall i\in \Set{N+1, \ldots, 2N}$, so that
$\vectgr{\Phi}_{\mu_{\star}}^{\textnormal{av}} = [
\vectgr{\Phi}_{\mathcal{T}_N},
\vectgr{\Phi}_{\mu}^{\prime} ]$ and
$N_{\textnormal{av}} = 2N$. Then,
$T_{\textnormal{LSPE}, \mu}(Q)$ in (<ref>), and
thus (<ref>), are reproduced by
$T_{\mu_{\star}}(Q)$ in (<ref>) with

\begin{align*}
g \coloneqq \vectgr{\Phi}_{\mathcal{T}_N}
\vectgr{\gamma}_{\star} \,, \qquad
\vectgr{\Psi} \coloneqq \vectgr{\Phi}_{\mathcal{T}_N}
\vectgr{\Upsilon}_{\star} \,,
\end{align*}

where the

\begin{align}
\vectgr{\gamma}_{\star}
& \coloneqq ( \vect{K}_{\mathcal{T}_N} + \sigma
\vect{I}_N )^{-1} \vect{g}
\,, \label{gamma.LSPE}\\
\vectgr{\Upsilon}_{\star}
& \coloneqq ( \vect{K}_{\mathcal{T}_N} + \sigma
\vect{I}_N )^{-1} [ (\sigma/\alpha)
\vect{K}_{\mathcal{T}_N}^{\dagger} \,, \vect{I}_N
] \,, \label{Upsilon.LSPE}
\end{align}

satisfy (<ref>) with

ℒ(γ, Υ)

K_𝒯_N( γ
+ αΥ
⊺ Q )  - g - αΦ_μ^'⊺Q

ℛ(γ, Υ)
( γ + αΥ
Q - K_𝒯_N^†
Φ_𝒯_N^⊺Q )^⊺

·( γ + αΥ
Φ_μ_⋆^av ⊺
Q - K_𝒯_N^†
Φ_𝒯_N^⊺Q )

and $\vect{K}_{\mathcal{T}_N}^{\dagger}$ is the
Moore-Penrose pseudoinverse of

*  Consider the stationary
policy $\mu$ in (<ref>), and define $\mu_{\star}$
and $\vectgr{\Phi}_{\mu_{\star}}^{\textnormal{av}}$ as
in <ref>. Define also the
temporal-difference (TD) feature vectors
$\vectgr{\Phi}_{\textnormal{TD}} \coloneqq
\vectgr{\Phi}_{\mathcal{T}_N} - \alpha
\vectgr{\Phi}_{\mu_{\star}}^{\prime}$ and
$\vect{K}_{\textnormal{TD}} \coloneqq
\vectgr{\Phi}_{\textnormal{TD}}^{\intercal}
\vectgr{\Phi}_{\textnormal{TD}}$. Then,
$T_{\textnormal{BR}, \mu}(Q)$ in (<ref>) is
reproduced by $T_{\mu_{\star}}(Q)$
in (<ref>) with

\begin{align*}
g\coloneqq \vectgr{\Phi}_{\textnormal{TD}}
\vectgr{\gamma}_{\star} \,, \qquad
\vectgr{\Psi} \coloneqq \vectgr{\Phi}_{\textnormal{TD}}
\vectgr{\Upsilon}_{\star} \,,
\end{align*}

where the

\begin{align}
\vectgr{\gamma}_{\star}
& \coloneqq ( \vect{K}_{\textnormal{TD}} + \sigma
\vect{I}_N )^{-1} \vect{g} \,, \label{gamma.BR}\\
\vectgr{\Upsilon}_{\star}
& \coloneqq ( \vect{K}_{\textnormal{TD}} + \sigma
\vect{I}_N )^{-1}
\vect{K}_{\textnormal{TD}}^{\dagger} [
(\sigma/\alpha) \vect{I}_N \,, -\sigma \vect{I}_N
] \,, \label{Upsilon.BR}
\end{align}

satisfy (<ref>) with

ℒ(γ, Υ)

K_TD (
γ +
⊺ Q ) - g _^N^2

ℛ(γ, Υ)
( γ + αΥ
⊺ Q - K_TD^†

·( γ + αΥ
⊺ Q
- K_TD^†
)  .

*  Given a stationary policy
$\mu \in \mathcal{M}$, let $\mu_{\star} \coloneqq \mu$,
$\vect{s}_i^{\textnormal{av}} \coloneqq
\vect{s}_i^{\prime}$, $\forall i\in \Set{1, \ldots, N}$,
$\vectgr{\Phi}_{ \mu_{\star} }^{\textnormal{av}}
\coloneqq \vectgr{\Phi}_{\mu}^{\prime}$. For

\begin{align*}
g \coloneqq \vectgr{\Phi}_{\mathcal{T}_N}
\vectgr{\gamma}_{\star} \,, \qquad
\vectgr{\Psi} \coloneqq \vectgr{\Phi}_{\mathcal{T}_N}
\vectgr{\Upsilon}_{\star} \,,
\end{align*}

where the

\begin{align}
\vectgr{\gamma}_{\star}
& \coloneqq ( \vect{K}_{\mathcal{T}_N} + \sigma
\vect{I}_N )^{-1} \vect{g} \,, \label{gamma}\\
\vectgr{\Upsilon}_{\star}
& \coloneqq ( \vect{K}_{\mathcal{T}_N} + \sigma
\vect{I}_N )^{-1} \,, \label{Upsilon}
\end{align}

satisfy (<ref>) with

ℒ(γ, Υ)

K_𝒯_N( γ
+ αΥ
⊺ Q )  - g - αΦ_μ^'⊺Q
_^N^2  ,

ℛ(γ, Υ)
( γ + αΥ
Q )^⊺ K_𝒯_N (
γ + αΥ
⊺ Q )  ,

the B-Map $T_{ \mu_{\star} }(Q)$ in (<ref>)
takes the form

T_ μ_⋆ (Q)
Φ_𝒯_N (
K_𝒯_N + σI_N )^-1

+ αΦ_𝒯_N (
K_𝒯_N + σI_N )^-1
Φ_μ^av ⊺

Notice that operator
$\vectgr{\Phi}_{\mathcal{T}_N} (
\vect{K}_{\mathcal{T}_N} + \sigma \vect{I}_N )^{-1}
\vectgr{\Phi}_{\mu}^{\textnormal{av} \intercal}$
appears in <cit.> and
<cit.>. However, the B-Map
which is based on the previous operator and introduced
in <cit.> is defined
in a Banach space, and not a Hilbert one.

See <ref>.

More variations of (<ref>) can be generated
from (<ref>) by tuning the loss
functions $\mathcal{L}, \mathcal{R}$ appropriately. For
example, robust B-Map designs against outliers in sampling
can be obtained by letting the $\ell_1$-norm take the place
of the quadratic one in (<ref>)
(<ref>). Task (<ref>)
for general (non)smooth convex $\mathcal{L}$ and
$\mathcal{R}$ can be handled efficiently
by <cit.>. Such designs are deferred to
future publications.

(Lipschitz continuity)
Mappings (<ref>) are Lipschitz
continuous: $\forall Q_1, Q_2 \in \mathcal{H}$,

T_μ(Q_1) - T_μ (Q_2) _ℋ
≤βQ_1 - Q_2_ℋ

T(Q_1) - T(Q_2)_ℋ
≤βQ_1 - Q_2_ℋ

\begin{align}
\beta \coloneqq \alpha \left( \norm{ \vect{K}_{\Psi} }_2
\, \sup\nolimits_{\mu^{\prime}\in\mathcal{M}}
\norm{\vect{K}^{\textnormal{av}}_{\mu^{\prime}}}_2
\right)^{{1}/{2}} \,, \label{beta}
\end{align}

and $\norm{\cdot}_2$ stands for the spectral norm of a
matrix. Hence, if $\beta = 1$,
mappings (<ref>) are
nonexpansive <cit.>, whereas, if
$\beta < 1$, they are contractions <cit.> in
$(\mathcal{H}, \innerp{\cdot}{\cdot}_{\mathcal{H}})$.

See <ref>.

To state the following
<ref>, a probability space
$(\Omega, \mathcal{F}, \Prob)$ is necessary, with sample
space $\Omega$, $\sigma$-algebra $\mathcal{F}$ of events,
and probability measure
$\Prob$ <cit.>. A statement
$(\ldots)$ will be said to hold true almost surely (a.s.),
if $(\ldots)$ holds true on an event
$\mathcal{E} \in \mathcal{F}$ with
$\Prob( \mathcal{E} ) = 1$. Moreover, by a slight abuse of
terminology, a bounded linear and self-adjoint mapping
$\mathcal{A} \colon \mathcal{H} \to \mathcal{H}$ will be
called positive definite, if its minimum spectral value
$\sigma_{\min} ( \mathcal{A} ) > 0$, where
$\sigma_{\min}(\cdot)$ is defined by (<ref>).

*  The RKHS $\mathcal{H}$ is separable,
for a stationary policy $\mu(\cdot) \in \mathcal{M}$
$\Sigma_{zz}, \Sigma_{s^{\prime} z}^{\mu}, \Sigma_{
s^{\prime} \given z }^{\mu}$, defined
by (<ref>), are bounded linear, $\Sigma_{zz}$
of (<ref>) is positive definite, and
$\Sigma_{zz}^{-3/2} \Sigma_{ s^{\prime}z }^{\mu}$
of (<ref>) is Hilbert-Schmidt (see
<ref> in the appendices).

* Let $\vect{s}, a, \vect{s}^{\prime}$ be random
variables (RVs) on the probability space
$(\Omega, \mathcal{F}, \Prob)$, and assume that
trajectory points
$\{ (\vect{s}_i, a_i, \vect{s}_i^{\prime}) \}_{i=1}^N$
are also RVs, but independent and identically
distributed (IID) copies of
$(\vect{s}, a, \vect{s}^{\prime})$.

*  Motivated by
and <cit.>, let
$N_{\textnormal{av}} = N$, set
$\vect{s}_i^{\textnormal{av}} \coloneqq
\vect{s}_i^{\prime}$, $\forall i\in \Set{1, \ldots, N}$,
and define
$\vectgr{\Psi} \coloneqq \vectgr{\Phi}_{\mathcal{T}_N} (
\vect{K}_{\mathcal{T}_N} + N \sigma^{\prime}_N
\vect{I}_N )^{-1}$ so that (<ref>)
become: $\forall Q\in \mathcal{H}$,

\begin{align}
T_{\mu} (Q)
& = g + \alpha \vectgr{\Phi}_{\mathcal{T}_N} (
\vect{K}_{\mathcal{T}_N} + N \sigma^{\prime}_N
\vect{I}_N )^{-1}
\vectgr{\Phi}_{\mu}^{\textnormal{av} \intercal} Q
\,, \label{new.Bellman.mu.special} \\
& = g + \alpha \vectgr{\Phi}_{\mathcal{T}_N} (
\vect{K}_{\mathcal{T}_N} + N \sigma^{\prime}_N
\vect{I}_N )^{-1}
\vecinf_{\mathcal{S}_{\textnormal{av}}}(Q)
\,, \label{new.Bellman.inf.special}
\end{align}

where $\sigma^{\prime}_N \in \RealPP$ is a
regularization coefficient, dependent on $N$.

$\lim_{N \to \infty} \sigma^{\prime}_N = 0$ and
$\lim_{N \to \infty} N \sigma^{\prime\, 3}_N = +\infty$.

* The $\inf$ operators in (<ref>)
and (<ref>) are achievable.

*  There exists
$\beta_{\infty} \in (0,1)$ s.t. $\beta = \beta(N)$ in
(<ref>) satisfies $\beta(N) \leq \beta_{\infty}$,
$\forall N$, a.s.

(Consistency of fixed points) Under
$T_{\mu}^{\diamond}, T^{\diamond}$
in (<ref>) and $T_{\mu}, T$
in (<ref>) are contractions in
the Hilbert space $\mathcal{H}$, and thus possess unique
fixed points
$Q_{\mu}^{\diamond}, Q_*^{\diamond}, Q_{\mu}, Q_*$,
respectively, a.s. Notice that $Q_{\mu}, Q_*$ depend on
$N$, , $Q_{\mu} = Q_{\mu}(N)$ and $Q_* =
Q_*(N)$. Furthermore,

Q_μ^♢ -
= 0  ,

_N→∞ Q_*^♢
- Q_*(N)_ℋ
= 0  ,

where $\Plim$ stands for convergence in
probability <cit.>.

See <ref>.

§ APPLICATION TO ROBUST ADAPTIVE FILTERING

The following discussion applies the novel B-Maps of
<ref> to the setting
of <ref>. To abide by the online or
time-adaptive premise of <ref>, the
arguments of <ref> will be
equipped hereafter with a discrete time index
$n\in \IntegerP$. It is important to note that $n$ serves
also as the iteration index of the proposed
RL-based <ref>. Index $n$ appears in the following
discussion in various forms, such as a sub-/super-script, or
as $[n]$. For example, $N$ of <ref>
becomes $N[n]$ from now and on to highlight the fact that
$N$ depends on $n$.

Although (<ref>) and
<ref> introduce considerable freedom
in designing B-Maps, this manuscript focuses on the setting
of <ref> to avoid lengthy
discussions. The online variant $T_{\mu_n}^{(n)}$ of the
mapping in <ref> will be presented in
<ref>. Other designs are deferred to future

<ref> offers an RL way to robustify LMP (<ref>) by
letting the data themselves select the “optimal” $p_n$ per
time $n$ (see <ref> of <ref>),
without any assumptions and prior knowledge on the
statistics of the outliers. More specifically, instead
of (<ref>),

\begin{align}
\vectgr{\theta}_{n+1} \coloneqq \vectgr{\theta}_{n+1} (
a_n ) \coloneqq \vectgr{\theta}_n + \rho\, p_n \lvert e_n
\rvert^{p_n - 1} \sign(e_n)\, \vect{x}_n \,, \label{dLMP}
\end{align}

where $e_n$ is defined after (<ref>). It is clear
by (<ref>) and <ref> of <ref>
that $\vectgr{\theta}_{n+1}$ depends on the action
$a_n = p_n$. To highlight this observation,
$\vectgr{\theta}_{n+1}( a_n )$ is used together with
$\vectgr{\theta}_{n+1}$ in (<ref>), as well as in the
following discussion.

<ref> belongs to the class of policy-iteration
(PI) algorithms of
RL <cit.>. More precisely, it is
an approximate (A)PI algorithm, because the
expectation operators in (<ref>) are
approximated by sample averaging in
<ref>. Typically, (A)PI comprises two
major steps: policy improvement in
<ref> and policy evaluation in
<ref>. The following discussion
details <ref>.

[1]

Arbitrarily initialize $\vectgr{\theta}_0$,
$Q_0$, and $\vect{s}_{-1}$.

$n \in \IntegerP$

Data $(\vect{x}_n, y_n)$ become available to
the user/agent.

New state $\vect{s}_{n}$ is defined
by (<ref>).

Policy improvement: Let $a_{n}
\coloneqq \mu_{n}(\vect{s}_{n})$
by (<ref>).

Compute $\vectgr{\theta}_{n+1}$ by (<ref>),
with $p_{n} \coloneqq a_{n}$.

Policy evaluation: Compute $Q_{n+1}$
by (<ref>) and

Increase $n$ by one, and go to

Approximate policy iteration for LMP

§.§ State-action space and policy improvement

This subsection refers to
of <ref>. Action space $\mathfrak{A}$ is defined as
any finite grid of the interval $[1,2]$, and it is the
domain $p_n$ in (<ref>) takes values from. State space
is defined as $\mathfrak{S} \coloneqq \Real^4$, with the
dimension of $\mathfrak{S}$ rendered independent of the
filter length $L$. In contrast, the state space
in <cit.> is $\Real^{2L+1}$, directly
dependent on $L$, potentially high-dimensional in the case
of long filters $\vectgr{\theta}_*\in \Real^L$, with the
likely unpleasant side-effect of hindering learning due to
the notorious “curse of dimensionality.”  State-action
space is defined as
$\mathfrak{Z} \coloneqq \mathfrak{S}\times \mathfrak{A}
\coloneqq \Set{ \vect{z} \coloneqq (\vect{s}, a) \given
\vect{s}\in \mathfrak{S}, a\in \mathfrak{A}}$.

At time $n$, available to the user are the state-action pair
$(\vect{s}_{n-1}, a_{n-1})$, data
$\mathfrak{D}_{( n-M_{ \textnormal{av} } ):n} \coloneqq
((\vect{x}_{\nu}, y_{\nu}))_{\nu = n-M_{ \textnormal{av}
}}^{n}$, for some buffer length
$M_{ \textnormal{av} } \in \RealPP$, as well as estimates
$(\vectgr{\theta}_{n}, \vectgr{\theta}_{n-1})$. The new
state $\vect{s}_n$ is defined as

\begin{align}
\vect{s}_n \coloneqq \vect{s}_{n-1}^{\prime} = [
s_{n-1}^{\prime (1)}, s_{n-1}^{\prime (2)},
s_{n-1}^{\prime (3)}, s_{n-1}^{\prime (4)}]^{\intercal}
\,, \label{def.sn}
\end{align}

where $\vect{s}_{n-1}^{\prime}$ stands for the subsequent
state of $\vect{s}_{n-1}$, which depends on
$( \vect{s}_{n-1}, a_{n-1}, \mathfrak{D}_{( n-M_{
\textnormal{av} } ):n}, \vectgr{\theta}_{n},
\vectgr{\theta}_{n-1} )$ and is defined by

log  |e_n |^2  ,

log |y_n-m -
x_n-m |^2 / x_n-m _2^2

log  x_n_2  ,

ϖs_n-1^(4) + (1 - ϖ) log( 1ρ
θ_n(a_n-1) -
θ_n-1_2 )

ϖs_n-1^(4) + (1 - ϖ)( p_n-1 - 1 )
log|e_n-1 |

+ (1 - ϖ) log   x_n-1

+ (1 - ϖ) logp_n-1  ,

with $\varpi \in (0,1)$ being a user-defined parameter, while
$\rho$ comes from (<ref>). The $\log (\cdot)$ function
is employed to decrease the dynamic range of the positive
values in (<ref>). Any logarithmic function can
be used in (<ref>); the $10$-base one is used in
<ref>. The classical prior loss in
AdaFilt <cit.> is used in (<ref>),
an $M_{\textnormal{av}}$-length sliding-window sampling
average of the posterior loss <cit.> is
provided in (<ref>), normalized by the norm of the
input signal to remove as much as possible its effect on the
error, the instantaneous norm of the input signal in
(<ref>), and a smoothing auto-regressive process in
(<ref>) to monitor the consecutive displacement of
the estimates $(\vectgr{\theta}_n)_{n\in\IntegerP}$. The
reason for including $\rho$ in (<ref>) is to remove
$\rho$'s effect from $s_4^{(n)}$.

With the estimate $Q_n$ available to the user/agent, policy
improvement in <ref> is achieved by
the standard greedy rule <cit.>

\begin{align}
\mu_{n}(\vect{s}) \coloneqq \arg\min\nolimits_{a\in
\mathfrak{A}} Q_n( \vect{s}, a) \,, \quad \forall
\vect{s}\in \mathfrak{S} \,. \label{mu.n}
\end{align}

More specifically, the next action $a_n$ for the agent is
identified by plugging $\vect{s}_n$ in the place of
$\vect{s}$ in (<ref>). Now that
$a_n \coloneqq \mu_{n}(\vect{s}_{n})$ is available,
recursion (<ref>) is applied with $p_n \coloneqq a_n$
to <ref> of <ref> to obtain the new
estimate $\vectgr{\theta}_{n+1}$.

§.§ Defining $T_{\mu_n}^{(n)}$ and loss
$\mathcal{L}_{\mu_n}^{(n)} [ \cdot ]$

This subsection defines the online version $T_{\mu_n}^{(n)}$
of the B-Map discussed in
<ref>. State-action pair
$\vect{z}_{n} = (\vect{s}_{n}, a_{n})$ and stationary policy
$\mu_n$ are now available to the user/agent by the
discussion in <ref>, and therefore,
trajectory samples
$\mathcal{T}_{N[n]}^{(n)} \coloneqq \{ (\vect{s}_i[n],
a_i[n], \vect{s}_i^{\prime}[n]) \}_{i=1}^{N[n]}$ can be
now defined according to <ref>.

Let $N_{\textnormal{av}}[n] \coloneqq N[n]$,
$\vect{s}_i^{\textnormal{av}}[n] \coloneqq
\vect{s}_i^{\prime}[n]$,
$\forall i\in \Set{1, \ldots, N[n]}$, and for some
$\sigma\in \RealP$,

[ ψ_1[n], …, ψ_N[n][n] ]

Φ_𝒯_N[n]^(n) (
K_𝒯_N[n]^(n) +
σI_N[n] )^-1

[ φ(s_1[n], a_1[n]), …,
a_N[n][n])]  ,

[ φ(s_1^'[n],
μ_n(s_1^'[n]) ),

…, φ(s_N[n]^'
[n], μ_n(s_N[n]^'[n]) ) ]  ,
where $\Set{ \mu_n(\vect{s}_i^{\prime}[n]) }_{i=1}^{N[n]}$
are computed by (<ref>). As such,
(<ref>) takes the following form:

\begin{align}
T_{\mu_n}^{(n)}(Q) \coloneqq g + \alpha \vectgr{\Psi}[n]
\vectgr{\Phi}_{\mu_n}^{\textnormal{av}\intercal}[n] Q \,,
\quad \forall Q\in \mathcal{H} \,.
\label{new.Bellman.mu.online}
\end{align}

Computing $T_{\mu_n}^{(n)}(Q)$ for a given
$Q\in \mathcal{H}$ amounts to identifying
$(T_{\mu_n}^{(n)}(Q))(\vect{s}, a)$ for all
$\vect{z} = (\vect{s}, a)\in \mathfrak{S} \times
\mathfrak{A}$, which is a computationally infeasible task
given that $\mathfrak{S}$ is the continuous
$\Real^4$. To surmount this obstacle, this study uses the
point evaluation of $T_{\mu_n}^{(n)}(Q)$ at a
single state-action vector
$\vect{z}_{\nu_*} = (\vect{s}_{\nu_*}, a_{\nu_*})$, chosen
by the user from the history of state-action pairs
$\Set{ \vect{z}_{\nu} = (\vect{s}_{\nu}, a_{\nu})
}_{\nu=0}^{n-1}$, that is, $\nu_*\in \Set{ 0, \ldots, n-1}$,
to define the following superset of $\Fix T_{\mu_n}^{(n)}$:

H_μ_n^(n) [z_ν_*]

Q∈ℋ (T_μ_n^(n)(Q) - Q)
(z_ν_*) = 0

=         Q∈ℋ T_μ_n^(n)(Q) -
Qφ(z_ν_*)_ℋ = 0

=         Q∈ℋ Qh_μ_n^(n) [z_ν_*]
_ℋ = g(z_ν_*)

where (<ref>) follows by the reproducing property,
and (<ref>) by
incorporating (<ref>) with

\begin{align}
& h_{\mu_n}^{(n)} [\vect{z}_{\nu_*}] \notag \\
& \coloneqq \varphi(\vect{z}_{\nu_*}) - \alpha
\sum \nolimits_{i=1}^{N[n]} (\psi_i[n])
(\vect{z}_{\nu_*})\, \varphi (\vect{s}_i^{\prime}[n],
\mu_n (\vect{s}_i^{\prime}[n]) ) \label{def.vec.h}
\end{align}

in (<ref>). Notice that
$H_{\mu_n}^{(n)} [\vect{z}_{\nu_*}]$ is a hyperplane of
$\mathcal{H}$, with $h_{\mu_n}^{(n)} [\vect{z}_{\nu_*}]$
being its normal vector,
$\varphi(\vect{z}_{\nu_*}) = \kappa(\vect{z}_{\nu_*},
\cdot)$, and $(\psi_i[n]) (\vect{z}_{\nu_*})$ stands for the
value of $\psi_i[n]$ at $\vect{z}_{\nu_*}$. Hyperplane
$H_{\mu_n}^{(n)} [\vect{z}_{\nu_*}]$ is well defined and
non-empty even if $\Fix T_{\mu_n}^{(n)} = \emptyset$. Recall
here that the Banach-Picard fixed-point
theorem <cit.> guarantees that
$\Fix T_{\mu_n}^{(n)}$ is non-empty and a singleton in the
case where $T_{\mu_n}^{(n)}$ is a contraction. It is also
worth stressing here that exact knowledge of the one-step
loss $g$, as in $g(\vect{z})$ for all
$\vect{z}\in \mathfrak{S} \times \mathfrak{A}$, is no longer
necessary since the definition of
$H_{\mu_n}^{(n)} [\vect{z}_{\nu_*}]$ requires only a point
evaluation at $\vect{z}_{\nu_*}$, which, for the present
setting, is set to be

\begin{align}
g(\vect{z}_{\nu_*}) = g(\vect{s}_{\nu_*}, a_{\nu_*})
\coloneqq s^{\prime (2)}_{\nu_*} = s^{(2)}_{\nu_* + 1}
\,, \label{one.step.loss.value}
\end{align}

where the rightmost equality in (<ref>)
follows by (<ref>). Define also the quadratic loss
$\mathcal{L}_{\mu_n}^{(n)} [\vect{z}_{\nu_*}] (\cdot) \colon
\mathcal{H}\to \RealP$ as

ℒ_μ_n^(n) [ z_ν_*] (Q)

12 T_μ_n^(n)(Q) -

=        12 [
Qh_μ_n^(n) [z_ν_*]
_ℋ - g(z_ν_*) ]^2

It can be verified by (<ref>) that

\begin{align*}
H_{\mu_n}^{(n)} [\vect{z}_{\nu_*}] = \arg\min \nolimits_{Q
\in \mathcal{H}} \mathcal{L}_{\mu_n}^{(n)}
[\vect{z}_{\nu_*}] (Q) \,.
\end{align*}

§.§ Trajectory samples and policy evaluation

This subsection details the way the trajectory samples
$\mathcal{T}_{N[n]}^{(n)} \coloneqq \{ (\vect{s}_i[n],
a_i[n], \vect{s}_i^{\prime}[n]) \}_{i=1}^{N[n]}$ are
constructed. Instrumental to the construction is the buffer
$\mathfrak{B}_n \coloneqq \Set{ \mathfrak{b}_j \coloneqq
(\bar{\vect{s}}_j, \bar{a}_j, g( \bar{\vect{s}}_j,
\bar{a}_j), \bar{\vect{s}}^{\prime}_j ) }_{j=1}^{\lvert
\mathfrak{B}_n \rvert}$, where
$(\bar{\vect{s}}_j, \bar{\vect{s}}^{\prime}_j) \in
\mathfrak{S}^2$, $\bar{a}_j \in \mathfrak{A}$, and where
$\bar{\vect{s}}^{\prime}_j$ is determined by
$(\bar{\vect{s}}_j, \bar{a}_j)$. The way to update
$\mathfrak{B}_n$ is provided first, while the design of
trajectory samples follows next by utilizing the strategy of
experience replay <cit.>.

§.§.§ Updating $\mathfrak{B}_{n-1}$ to $\mathfrak{B}_n$

At time $n$, buffer $\mathfrak{B}_{n-1}$ and tuple
$( \vect{s}_{n-1}, a_{n-1}, g(\vect{s}_{n-1}, a_{n-1}),
\vect{s}_n )$ are available to the user. Given a
user-defined distance function
$\dist_{\mathfrak{S}}(\cdot, \cdot) \colon \mathfrak{S}
\times \mathfrak{S} \to \RealP$, for example,
$\dist_{\mathfrak{S}}(\cdot, \cdot) \coloneqq 1 -
\kappa_{\textnormal{G}}(\cdot, \cdot)$, where
$\kappa_{\textnormal{G}}(\cdot, \cdot)$ is a Gaussian
kernel, and a threshold $\delta_{\mathfrak{S}}\in \RealPP$,
consider the following criterion:

\begin{align}
\dist_{\mathfrak{S}} ( \vect{s}_{n-1}, \bar{\vect{s}}_j )
{} & {} > \delta_{\mathfrak{S}} \,, \notag \\
& \forall \mathfrak{b}_{j} = (\bar{\vect{s}}_j, \bar{a}_j,
g( \bar{\vect{s}}_j, \bar{a}_j),
\bar{\vect{s}}^{\prime}_j ) \in \mathfrak{B}_{n-1}
\,. \label{buffer.criterion.i}
\end{align}

If (<ref>) is satisfied, $\vect{s}_{n-1}$
is considered to be “different” enough from all
states $\bar{\vect{s}}_j$ which appear in the tuples
$\mathfrak{b}_{j}$ of $\mathfrak{B}_{n-1}$, and to carry
“sufficiently novel” information to be included in
$\mathfrak{B}_{n}$. Consequently, generate all tuples
$\mathfrak{C}_{n-1} \coloneqq \Set{ ( \vect{s}_{n-1}, a,
g(\vect{s}_{n-1}, a), \vect{s}_{n-1}^{\prime} (
\vect{s}_{n-1}, a, \mathfrak{D}_{( n-M_{ \textnormal{av} }
):n}, \vectgr{\theta}_{n}, \vectgr{\theta}_{n-1} )
\given a \in \mathfrak{A} }$, where
$\vect{s}_{n-1}^{\prime} ( \vect{s}_{n-1}, a,
\mathfrak{D}_{( n-M_{ \textnormal{av} } ):n},
\vectgr{\theta}_{n}, \vectgr{\theta}_{n-1} )$ is obtained by
replacing $a_{n-1}$ with $a$ in (<ref>). Define

\begin{align*}
\mathfrak{B}_n \coloneqq \mathfrak{B}_{n-1} \cup \Set{
( \vect{s}_{n-1}, a_{n-1}, g( \vect{s}_{n-1}, a_{n-1} ),
\vect{s}_n)} \cup \mathfrak{C}_{n-1} \,.
\end{align*}

On the other hand, if (<ref>) is not
satisfied, then $\mathfrak{B}_n \coloneqq
\mathfrak{B}_{n-1}$.

§.§.§ Experience replay

Now that buffer $\mathfrak{B}_n$ has been updated and given
a user-defined distance function
$\dist_{\mathfrak{Z}}(\cdot, \cdot) \colon \mathfrak{Z}
\times \mathfrak{Z} \to \RealP$, for example,
$\dist_{\mathfrak{Z}}(\cdot, \cdot) \coloneqq 1 -
\kappa_{\textnormal{G}}(\cdot, \cdot)$, where
$\kappa_{\textnormal{G}}(\cdot, \cdot)$ is a Gaussian
kernel, and a threshold $\delta_{\mathfrak{Z}}\in \RealPP$,

\begin{align}
\mathfrak{T}_{\vect{z}} \coloneqq \{ \mathfrak{b}_j =
{} & (\bar{\vect{s}}_j, \bar{a}_j, g( \bar{\vect{s}}_j,
\bar{a}_j), \bar{\vect{s}}^{\prime}_j
) \in \mathfrak{B}_n \notag \\
& \given \dist_{\mathfrak{Z}} ( \vect{z},
(\bar{\vect{s}}_j, \bar{a}_j ) ) \leq
\delta_{\mathfrak{Z}} \} \,, \quad \forall\vect{z}\in
\mathfrak{Z} \,. \label{mathfrakT.z}
\end{align}

In other words, $\mathfrak{T}_{\vect{z}}$ includes all
tuples $\mathfrak{b}_j$ of $\mathfrak{B}_n$ whose
state-action pairs $(\bar{\vect{s}}_j, \bar{a}_j )$ are
“sufficiently similar” with $\vect{z}$. Identify then
$\mathfrak{T}_{\vect{z}_{n-1}}$ by (<ref>), and
define the trajectory samples

=         ( s_i[n], a_i[n],
s_i^'[n] ) _i=1^N[n]

(s̅_j, a̅_j,
s̅_j^') 𝔟_j = (s̅_j, a̅_j, g(
s̅_j, a̅_j),
s̅^'_j ) ∈𝔗_z_n-1

∪ (s_n-1, a_n-1,
s_n-1^')   ,

where $\vect{s}_{n-1}^{\prime}$ is defined
by (<ref>). Consider also $T_{\mu_n}^{(n)}$ and
loss $\mathcal{L}_{\mu_n}^{(n)} [\vect{z}_{n-1}] (\cdot)$ as
in (<ref>)
and (<ref>), respectively, and apply the SGD
rule, with a learning rate $\eta\in \RealPP$, to form the

Q_n - η∇       ℒ_μ_n^(n) [z_n-1] (Q_n)

Q_n - η[

Q_nh_μ_n^(n) [z_n-1]

- g(z_n-1) ] ·h_μ_n^(n) [z_n-1]

where $g(\vect{z}_{n-1})$ is computed
by (<ref>), with $\vect{z}_{n-1}$ taking
the place of $\vect{z}_{\nu_*}$.

It is worth mentioning here that in the case where the set
$\mathcal{T}_{N[n]}^{(n)}$ of trajectory samples is a
singleton, more specifically,
$\mathcal{T}_{N[n]}^{(n)} = \{ (\vect{s}_{n-1}, a_{n-1},
\vect{s}_{n-1}^{\prime}) \}$, and whenever $\sigma = 0$
in (<ref>), then (<ref>)
corresponds to <cit.>.

To exploit also state-action pairs other than
$\vect{z}_{n-1}$, the strategy of experience replay is
adopted to choose a
$\mathfrak{b}_{j_*} \in \mathfrak{B}_n \setminus \Set{
(\bar{\vect{s}}_j, \bar{a}_j, g( \bar{\vect{s}}_j,
\bar{a}_j), \bar{\vect{s}}^{\prime}_j ) \in \mathfrak{B}_n
\given (\bar{\vect{s}}_j, \bar{a}_j) = \vect{z}_{n-1}}$
via a probability distribution, whose details are skipped
here but can be found in <cit.>. Having
identified such a
$\mathfrak{b}_{j_*} = ( \bar{\vect{s}}_{j_*}, \bar{a}_{j_*},
g( \bar{\vect{s}}_{j_*}, \bar{a}_{j_*}),
\bar{\vect{s}}^{\prime}_{j_*} )$, let
$\bar{\vect{z}}_{j_*} \coloneqq ( \bar{\vect{s}}_{j_*},
\bar{a}_{j_*} )$ and define
$\mathfrak{T}_{\bar{\vect{z}}_{j_*}}$ via
(<ref>). Next, let the trajectory samples

=         ( s_i[n+1/2], a_i[n+1/2],
s_i^'[n+1/2] ) _i=1^N[n+1/2]

(s̅_j, a̅_j,
s̅_j^') 𝔟_j = (s̅_j, a̅_j, g(
s̅_j, a̅_j),
s̅^'_j ) ∈𝔗_z̅_j_*   .

Define also $T_{\mu_n}^{(n+1/2)}$ and loss
$\mathcal{L}_{\mu_n}^{(n+1/2)} [\bar{\vect{z}}_{j_*}]
(\cdot)$ as in (<ref>)
and (<ref>), respectively, and apply again
the SGD rule to obtain the Q-function estimate of
<ref> in <ref>:

Q_n+1/2 - η∇       ℒ_μ_n^(n+1/2)
[z̅_j_*] (Q_n+1/2)

Q_n+1/2 - η[

h_μ_n^(n+1/2) [z̅_j_*]

- g(z̅_j_*) ] ·h_μ_n^(n+1/2) [z̅_j_*]

§.§ Dimensionality reduction by random Fourier

At every time instance $n$, <ref> adds new features
into the representation of $Q_{n+1}$ via (<ref>),
(<ref>), and (<ref>),
justifying the “nonparametric” characterization of the
proposed design. These new features contribute information
in $Q_{n+1}$ along novel dimensions of $\mathcal{H}$ which
may have not been explored prior to time $n$. Novel
dimensions are welcome since they lead into a “rich”
kernel-based representation of the Q-function. However,
due to the potentially infinite dimensionality of
$\mathcal{H}$, the length of the Q-function representation
may grow unbounded as new dimensions/features are added up,
raising in turn hardware/computational obstacles due to the
need for large storage space and large number of
computations to process the long Q-function
representations (“curse of dimensionality”). The desire
for low hardware/computational footprints calls for
dimensionality reduction, which is achieved here by
employing random Fourier features (RFF) <cit.> as

According to Bochner's theorem, there exist pairs
$(\kappa, \vect{v})$, where $\kappa$ is a real-valued
reproducing kernel and $\vect{v}$ an RV, s.t.$\kappa(\vect{z}, \vect{z}^{\prime}) =
\expect_{\vect{v}}\Set{ \cos
[{\vect{v}^{\intercal}(\vect{z}-\vect{z}^{\prime})} ] }$,
$\forall \vect{z}, \vect{z}^{\prime}\in
\Real^D$ <cit.>. An example of such a pair is
$(\kappa_{\textnormal{G}}, \vect{v}_{\textnormal{G}})$,
where $\kappa_{\textnormal{G}}$ is the Gaussian kernel and
$\vect{v}_{\textnormal{G}}$ follows the Gaussian
distribution $\mathcal{N}(0, \vect{I}_D)$. It can be
verified that
$\expect_{\vect{v}, u} \{\cos [\vect{v}^\intercal (\vect{z}
+ \vect{z}^{\prime} ) + 2u] \} = 0$, where $u$ is an RV
uniformly distributed over $[0, 2\pi)$ and independent of
$\vect{v}$. Hence, Bochner's theorem yields:

κ(z, z^')
_v { cos[v^⊺
(z - z^')] }

_v, u{ cos[
(v^⊺z + u) -
(v^⊺ z^' + u)]

+ cos[ (v^⊺ z + u) +
(v^⊺z^' +
u) ] }

2 _v, u { cos(v^⊺ z + u) ·cos(v^⊺ z^' + u)}

≈       2 1D_RFF
cos(v_i^⊺ z +
u_i) ·cos(v_i^⊺
z^' + u_i)

φ_RFF^⊺( z )
φ_RFF ( z^'
)  ,

where $\approx$ in (<ref>) holds true by the law
of large numbers <cit.> for a large
user-defined number $D_{\textnormal{RFF}}$ of IID copies
$\{ \vect{v}_i \}_{i=1}^{D_{\textnormal{RFF}}}$ and
$\{ u_i \}_{i=1}^{D_{\textnormal{RFF}}}$ of $\vect{v}$ and
$u$, respectively, and $\varphi_{\textnormal{RFF}}$ is the
feature mapping defined as

\begin{align}
\varphi_{\textnormal{RFF}}
& \colon \Real^D \to \Real^{D_{\textnormal{RFF}}} \notag\\
& \colon \vect{z} \mapsto \sqrt{
\tfrac{2}{D_{\textnormal{RFF}}} } [ \cos
(\vect{v}_1^{\intercal} \vect{z} + u_1), \ldots, \cos
(\vect{v}_{D_{\textnormal{RFF}}}^{\intercal} \vect{z} +
u_{D_{\textnormal{RFF}}})]^{\intercal} \,. \label{rff.phi}
\end{align}

Mapping (<ref>) serves as a low dimensional
rendition of the feature mapping
$\varphi\colon \Real^D \to \mathcal{H}$ introduced in
<ref>, since $D_{\textnormal{RFF}}$ can be
made smaller than the typically large and potentially
infinite $\dim\mathcal{H}$. The feature-mapping
$\varphi_{\textnormal{RFF}}$ and inner-product
$\varphi_{\textnormal{RFF}}^{\intercal}( \vect{z} ) \,
\varphi_{\textnormal{RFF}} ( \vect{z}^{\prime} )$
approximations of $\varphi$ and
$\kappa(\vect{z}, \vect{z}^{\prime})$, respectively, are
used in <ref> to bound the hardware/computational
complexity. The results of <ref> are based on
these approximations.

§ PERFORMANCE ANALYSIS OF <REF>

In the following discussion, a statement $( \ldots (n) )$,
which depends on the iteration index $n\in \IntegerP$, will
be said to hold true “for all sufficiently large $n$,” if
there exists a large $n_0\in \IntegerPP$ s.t.$( \ldots (n) )$ holds true $\forall n \geq n_0$. Moreover,
within the context of a probability space
$(\Omega, \mathcal{F}, \Prob)$ (see the discussion before
<ref>), a statement $(\ldots)$ will be
said to hold true with high probability (w.h.p.), if
$(\ldots)$ holds true on an event
$\mathcal{E} \in \mathcal{F}$ with
$\Prob( \mathcal{E} ) \geq 1 - \varepsilon$, for a
sufficiently small $\varepsilon \in \RealPP$.

Central to the following discussion are the sequence of
estimates $(Q_n)_{n\in \IntegerP}$ generated by <ref>,
the classical B-Maps $T^{\diamond}, T_{\mu_n}^{\diamond}$
in (<ref>), as well as the newly
proposed $T_{\mu_n}^{(n)}$ one in (<ref>)
for a stationary policy
$\mu_n(\cdot) \colon \mathfrak{S} \to \mathfrak{A}$. Recall
also that $Q_*^{\diamond}$ stands for a fixed point of
mapping $T^{\diamond}$, ,
$Q_*^{\diamond} \in \Fix ( T^{\diamond} ) \Leftrightarrow
Q_*^{\diamond} = T^{\diamond} (Q_*^{\diamond})$, that
$Q_{\mu_n}^{\diamond} \in \Fix ( T_{\mu_n}^{\diamond} )$ and
$Q_{\mu_n} \in \Fix ( T_{\mu_n}^{(n)} )$.

<ref> asserts that for an
arbitrarily fixed $\epsilon \in \RealPP$ and for any $n$,
$\norm{Q_{\mu_n}^{\diamond} - Q_{\mu_n}(N[n])}_{\mathcal{H}}
\leq \epsilon$ holds true w.h.p. for all sufficiently large
$N[n]$. By this result, it is expected that for sufficiently
large $N[n]$, the size of the event

\begin{align}
E_{n,N[n]}^{(\epsilon)} \coloneqq \Set*{ \omega \in
\Omega \given \norm{Q_{\mu_n}^{\diamond} -
Q_{\mu_n}(N[n])}_{\mathcal{H}} \leq \epsilon }
\,. \label{event.En.epsilon}
\end{align}

can be considered to be large. This observation serves as
the motivation behind the following <ref>.

*  Consider an
$\epsilon\in \RealPP$ s.t.
\begin{align}
E^{(\epsilon)} \coloneqq \liminf_{n\to \infty}
\liminf_{N[n] \to \infty} E^{(\epsilon)}_{n, N[n]} \neq
\emptyset \,, \label{event.E.epsilon}
\end{align}

where for events
$( \mathcal{E}_{\nu})_{\nu \in \IntegerP}$,
$\liminf_{\nu \to \infty} \mathcal{E}_{\nu} \coloneqq
\cup_{\nu} \cap_{\nu^{\prime} \geq \nu}
\mathcal{E}_{\nu^{\prime}}$ <cit.>.

* Presume <ref>.

*  In the current online
setting, <ref> takes the following
form. There exists $\beta_{\infty} \in (0,1)$ s.t.    $\beta_n = \beta_n(N[n]) \leq \beta_{\infty}$, for all
sufficiently large $n$ and $N[n]$, a.s., where $\beta_n$
is defined according to (<ref>) as

\begin{align}
\beta_n \coloneqq \alpha \left( \norm{
\vect{K}_{\Psi_n} }_2 \,
\sup\nolimits_{\mu^{\prime}\in\mathcal{M}}
\norm{\vect{K}^{\textnormal{av}, n}_{\mu^{\prime}}}_2
\right)^{{1}/{2}} \,. \label{beta.n}
\end{align}

*  There exists
$\Delta_0 \in \RealPP$ s.t.    $\norm{Q_{\mu_n} - Q_n}_\mathcal{H}\leq \Delta_0$, for
all sufficiently large $n$, a.s.

*  There exists
$\Delta_1\in \RealPP$ s.t.    $\norm{T_{\mu_{n+1}}^{\diamond} (Q_n) - T^{\diamond}
(Q_n)}_\mathcal{H} \leq \Delta_1$, for all
sufficiently large $n$, a.s.

*  There exists
$\Delta_2\in \RealPP$ s.t.    $\norm{ (T_{\mu_{n+1}}^{\diamond} -
\Id)(Q_{\mu_n}^{\diamond}) }_\mathcal{H} \leq
\Delta_2$, for all sufficiently large $n$, a.s.

The following theorem bounds the distance of the sequence of
estimates $(Q_n)_n$ from the fixed point $Q_*^{\diamond}$.

Under <ref>, for every $\omega \in
E^{(\epsilon)}$ of (<ref>),

\begin{align*}
\limsup\nolimits_{n\to\infty}\norm{ Q_n -
Q_*^{\diamond} }_{\mathcal{H}} \leq \Delta_3 \,,
\end{align*}

$\Delta_3 \coloneqq \epsilon + \Delta_0 + [ 2 \beta_\infty
(\Delta_0 + \epsilon) + \Delta_1 +
\Delta_2/(1-\beta_\infty) ] / (1-\beta_\infty)$.

See <ref>.

If the size of $E^{(\epsilon)}$ is large, which is something
anticipated by the discussion around
(<ref>), the assertion of
<ref> holds true w.h.p. Instead of the
point-wise, sample-point-based analysis of
<ref>, the following <ref>
provides a bound on the sequence $(Q_n)_n$ via the
expectation operator $\expect\{ \cdot \}$. To this end, the
following assumptions are necessary.

*  For simplicity, policy
evaluation in <ref> of
<ref> is performed without considering experience
replay (<ref>), that is,
$Q_{n+1} \coloneqq Q_n - \eta \nabla
\mathcal{L}_{\mu_n}^{(n)} [\vect{z}_{n-1}] (Q_{n})$.

*  There exists a policy
$\mu \colon \mathfrak{S} \to \mathfrak{A}$ s.t.    $\mu_n = \mu$ for all sufficiently large $n$.

*  There exists
$\beta_{\infty} \in (0,1)$ s.t. mapping
$T_{\mu_n}^{\diamond}$ is a $\beta_{\infty}$-contraction
for all sufficiently large $n$, a.s.

*  (Independency) The
$\sigma$-algebra $\sigma( \{\vect{z}_n, \xi_{n+1}\} )$,
generated by the state-action pair $\vect{z}_n$ and
$\xi_{n+1}$ (<ref>), is independent of the
filtration $\mathcal{F}_n$ for all sufficiently large
$n$, where
$\mathcal{F}_n \coloneqq \sigma( \{ Q_{\nu} \}_{\nu=0}^n
)$ is defined as the $\sigma$-algebra generated by the
sequence of estimates
$\{ Q_{\nu}
\}_{\nu=0}^n$ <cit.>.

*  (Stationary
moment) There exists
$\mathfrak{m}_{\xi}^{(4)} \in \RealPP$ s.t.    $\mathfrak{m}_{\xi}^{(4)} = \expect \{
\norm{\xi_n}_{\mathcal{H}}^4 \}$, for all sufficiently
large $n$, where $\xi_n$ is defined by (<ref>).

* (Stationary covariance operators) There
exist bounded linear operators
$\Sigma_{zz}, \Sigma_{\xi z}, \Sigma_{\xi \xi} \colon
\mathcal{H} \to \mathcal{H}$ s.t.    $\Sigma_{zz}^{(n)} = \Sigma_{zz}, \Sigma_{\xi z}^{(n)} =
\Sigma_{\xi z}$, and
$\Sigma_{\xi \xi}^{(n)} = \Sigma_{\xi \xi}$, for all
sufficiently large $n$, where
$\Sigma_{zz}^{(n)}, \Sigma_{\xi z}^{(n)}, \Sigma_{\xi
\xi}^{(n)}$ are defined
by (<ref>).

*  (Positive
definite $\mathcal{A}_{\mu_n}, \Sigma_{zz}$) For all
sufficiently large $n$, the linear bounded and
self-adjoint mappings
$\mathcal{A}_{\mu_n}$ (<ref>) and
$\Sigma_{zz}$ are positive definite, , their minimum
spectral values
$\sigma_{\min} ( \mathcal{A}_{\mu_n} ) > 0$ and
$\sigma_{\min} ( \Sigma_{zz} ) > 0$, where
$\sigma_{\min}(\cdot)$ is defined
by (<ref>).

* (Bounded kernel) There exists
$B_{\kappa} \in \RealPP$ s.t.    $\kappa( \vect{z}, \vect{z} ) \leq B_{\kappa}$,
$\forall \vect{z} \in \mathfrak{Z}$.

Under <ref>, for any sufficiently
small step size $\eta$, there exist
$\Delta_4, \Delta_5 \in \RealPP$ s.t.
≤  lim sup_n→∞ {  Q_n -
Q_*^♢ _ℋ^2 }

Δ_4 η^ T_1  +
Δ_5 lim sup_n→∞
{  Σ_ s^' z
^μ_n - Σ̂_ s^' z
^μ_n( N[n] ) ^2 } ^ T_2

+  2 lim sup_
n→∞   {
Q_μ_n^♢ - Q_*^♢
_ℋ^2 } _ T_3   ,

where operator
$\Sigma_{ s^{\prime} \given z }^{\mu_n}$ is defined
by (<ref>) and $\hat{\Sigma}_{
s^{\prime} \given z }^{\mu_n}( N[n] )$ is defined by

s^' z ^μ_n( N[n] )

1 √(N[n])  Φ_
𝒯_N[n]  ( 1N[n] K_
+ σ^'_N[n] I_N[n] )^-1

·1 √(N[n])
Φ_μ^av⊺  ;

see also (<ref>),
<ref>, and <ref>.

See <ref>.

Three terms
$\textnormal{T}_1, \textnormal{T}_2, \textnormal{T}_3$
contribute to the bound in <ref>:
$\textnormal{T}_1$ which stems from the
stochastic-gradient-descent recursion of
<ref>, $\textnormal{T}_2$ because of the
error in approximating the expectation operator by
trajectory sampling (<ref>), and
$\textnormal{T}_3$ which quantifies the disagreement between
$\mu_n$ and the “optimal” policy through the lenses of the
classical B-Maps (<ref>). It is worth
mentioning here that under <ref> and
according to <ref> in
$\norm{ \Sigma_{ s^{\prime} \given z }^{\mu_n} -
\hat{\Sigma}_{ s^{\prime} \given z }^{\mu_n}( N[n] ) }$
can be made arbitrarily small w.h.p. for sufficiently large

To establish bounds on the distance
$\norm{ \vectgr{\theta}_n - \vectgr{\theta}_* }$ between the
estimate $\vectgr{\theta}$ and the estimandum
$\vectgr{\theta}_*$ (see <ref>), standard
arguments from the analysis of stochastic gradient descent
(SGD) can be applied, because (<ref>) is nothing but
SGD on the convex $p$-power loss ($p\in [1,2]$). For example,
the discussion of <cit.> can
be followed by employing also the minimizer of the $p$-power
loss as an auxiliary quantity to facilitate the
analysis. Because of space limitations, rather than such a
straightforward but tedious performance analysis, this study
prefers to offer <ref> instead, which
showcases the connection between
$\norm{ \vectgr{\theta}_n - \vectgr{\theta}_* }$ and the
main mathematical object of this work, the Q-functions. To
this end, <ref> are needed.

* Presume <ref>.

* Presume <ref>.

* Let $\alpha\in (0,1)$.

* (Bounded errors) There exist
$\Delta_6, \Delta_7 \in \RealPP$ s.t.
\begin{align*}
\Delta_6 < \lvert y_{n-m} -
\vectgr{\theta}_{n}^{\intercal} \vect{x}_{n-m}
\rvert < \Delta_7 \,,
\end{align*}

$\forall m\in \{ 0, \ldots, M_{\textnormal{av}}-1 \}$
and for all sufficiently large $n$, a.s.

(Independency) The input-signal $\vect{x}_n$ is
independent of the outlier/noise $o_n$ for all
sufficiently large $n$. Moreover, the $\sigma$-algebra
generated by
$\{ \vect{x}_m \given m\in \{ n - M_{\textnormal{av}} +
1, \ldots, n\} \}$ and
$\{ o_m \given m\in \{ n - M_{\textnormal{av}} + 1,
\ldots, n\} \}$ is independent of the $\sigma$-algebra
generated by $\vectgr{\theta}_n$ for all sufficiently
large $n$.

* (Stationary $o_n$) There exists $\sigma_o
\in \RealPP$ s.t. $\expect \{ o_n^2 \} = \sigma_o^2$
and $\expect\{ o_n \} = 0$, for all sufficiently large

*  (Stationary
$\vect{x}_n$) There exists a positive definite matrix
$\Sigma_{xx} \in \Real^{L\times L}$, with
$\sigma_{\min}( \Sigma_{xx} ) = \lambda_{\min}(
\Sigma_{xx} ) > 0$ and where
$\lambda_{\min}( \Sigma_{xx} )$ stands for the minimum
eigenvalue of $\Sigma_{xx}$, s.t.    $\expect\{ \vect{x}_n \vect{x}_n^{\intercal} \} =
\Sigma_{xx}$, for all sufficiently large $n$. Moreover,
$\liminf_{n\to\infty} \expect \{ \log\, \norm{
\vect{x}_n }_2^2 \} > -\infty$.

*  For the sequence
of states $( \vect{s}_n )_n$ in <ref>,
$\limsup_{n\to \infty} \lvert \expect \{
Q_{\mu}^{\diamond} ( \vect{s}_n, \mu( \vect{s}_n ) ) \}
\rvert < +\infty$.

<ref>, there exist $\Delta_8\in
\RealPP$ and $\Delta_9 \in \RealP$ s.t. for all
sufficiently large $n$,

≤  {
θ_* - θ_n (μ(
s_n-1 )) _2^2 }

1 - α/Δ_8 λ_min
(Σ_xx) {
Q_μ^♢( s_n,
μ(s_n) ) }

+ 1/Δ_8 λ_min
(Σ_xx) [ log( Σ_xx )  -
Δ_8 σ_o^2 - Δ_9 ]  .

See <ref>.

Under the light of <ref>, the greedy
rule (<ref>) makes now sense in the context of AdaFilt,
because, choosing a policy by the greedy rule
$\arg\min_{ \mu(\cdot) \in \mathcal{M} } \expect \{
Q_{\mu}^{\diamond}( \vect{s}_{n}, \mu(\vect{s}_{n}) ) \}$
pushes the upper bound of <ref> to lower
levels, and, thus, potentially forces the estimate
$\vectgr{\theta}_n$ to approach $\vectgr{\theta}_*$.

§ NUMERICAL TESTS

<ref> is tested on synthetic data against

* Non-RL-based methods:

* LMP (<ref>), for values of
$p \in \mathfrak{A} \coloneqq \{1, 1.25, 1.5, 1.75, 2\}$
which are kept fixed throughout all iterations;

* <cit.>, which uses a combination of
adaptive filters with different forgetting factors but
with the same $p$-power loss;

* <cit.>, where two LMP
recursions (<ref>), with different $p$, are combined
to tackle outliers;

* the variable-kernel-width and correntropy-based
VKW-MCC <cit.>;

* RL-based methods:

* the kernel-based TD(0) <cit.>,
equipped with RFF (<ref>);

* the popular kernel (K)LSPI <cit.>; and

* the predecessor <cit.> of this work
which is based on RKHS arguments.

Action space is defined as
$\mathfrak{A} \coloneqq \{1, 1.25, 1.5, 1.75, 2\}$ for all
employed RL methods, including <ref>. Not only
<ref>, but all tested RL methods other
than <cit.> define state vectors
by (<ref>) and are equipped with experience
replay (<ref>). On the other hand,
<cit.> defines the state space as
$\mathfrak{S}\subset\Real^{2L+1}$ and utilizes no experience
replay, but uses rollout
instead <cit.>. Notice also
according to the discussion which
follows (<ref>) that <ref> with only one
trajectory sample, , $N[n] = 1$ per $n$, corresponds
to <cit.>. Nevertheless, <ref> is
equipped with RFF (<ref>) which is not available
in <cit.>.

The performance metric is the normalized deviation of the
estimate $\vectgr{\theta}_n$ from the estimandum
$\vectgr{\theta}_*$; see the vertical axes in all
figures. The classical Gaussian
kernel <cit.> was employed to define
$\mathcal{H}$, approximated by RFF with
$D_{\textnormal{RFF}} = 500$ as described in
<ref>. The dimension of
$\vect{x}_n, \vectgr{\theta}_*$ is set to $L = 100$, where
$\vect{x}_n$ and $\vectgr{\theta}_*$ are generated by the
Gaussian distribution $\mathcal{N}(\vect{0}, \vect{I}_{L})$,
with $(\vect{x}_n)_{n \in \IntegerP}$ designed to be
IID. The learning rate in (<ref>) is $\rho =
10^{-3}$. Moreover, $M_{\textnormal{av}} = 300$ and
$\varpi = 0.3$ in (<ref>), while $\eta = 0.1$ in
(<ref>) and
(<ref>). In (<ref>),
$\delta_{\mathfrak{S}} = 1 - 0.99$.

To study the effect of sampling size $N[n]$, controlled by
$\delta_{\mathfrak{Z}}$ in (<ref>), the
following sets of parameters were tested:

* $\delta_{\mathfrak{Z}} = 1 - 0.98$ in
(<ref>), which yields $N[n] \geq 1$,
and $\sigma = 10^{-1}$ in (<ref>); and

* $\delta_{\mathfrak{Z}} = 0$, which forces $N[n] = 1$,
and $\sigma = 0$, corresponding thus
to <cit.>.

Additionally, to study the effect of the long-term loss,
$\alpha = 0$ was also tested. Note that $\alpha = 0$
suggests that <ref> uses no trajectory samples.

In <ref>, policy improvement and evaluation are
scheduled to be run at every iteration $n$. Nevertheless, to
promote stability and allow the policy-iteration step reach
a “steady state” between two consecutive invocations of
the policy-improvement step, a less greedy approach is
followed here and <ref> of
<ref> is not run at every $n$, but it is invoked
periodically, every other $N_p = 500$ iterations, , at
iterations $\Set{ n = N_pk \given k\in\IntegerP }$. Between
two consecutive policy-improvement steps, that is, during
iterations $\{ N_pk, \ldots, N_p(k+1) - 1 \}$, the policy
stays fixed to $\mu_{ N_pk } (\cdot)$. The same strategy is
also followed for KLSPI <cit.>.

KLSPI <cit.> was originally designed to generate
trajectory samples offline by using training data. However,
since this work considers the online setting, where no
training data are available and only test data are
considered, and to ensure fairness among all competing
methods, matrix $\vect{A}$ and vector $\vect{b}$, which
appear in <cit.> and are learned from training
data, are substituted by the following online versions
$\vect{A}_n$ and $\vect{b}_n$: upon defining
$\vect{k}_n \coloneqq \vectgr{\Phi}_{ \textnormal{KLSPI}
}^{(n) \intercal}\, \varphi ( \vect{s}_n, \mu_n(\vect{s}_n)
)$, where $\vectgr{\Phi}_{ \textnormal{KLSPI} }^{(n)}$ is a
time-varying basis of RKHS vectors, constructed online by an
approximate-linear-dependency criterion <cit.>,

\begin{align*}
\vect{A}_{n}
& \coloneqq \vect{A}_{n-1} + \vect{k}_{n-1} (
\vect{k}_{n-1} - \alpha \vect{k}_{n} )^{\intercal} \,, \\
\vect{b}_{n}
& \coloneqq \vect{b}_{n-1} + g( \vect{s}_n,
\mu_n(\vect{s}_n) )\, \vect{k}_{n} \,,
\end{align*}

$\vect{A}_1 \coloneqq \vect{k}_0 ( \vect{k}_0 -
\alpha \vect{k}_1 )^{\intercal}$ and
$\vect{b}_0 \coloneqq g( \vect{s}_0, \mu_0(\vect{s}_0) )\,
\vect{k}_0$.

Two types of outliers are considered. Heavy-tailed
$\alpha$-stable outliers, generated
by <cit.> with parameters
$\alpha_{\textnormal{stable}} = 1$,
$\beta_{\textnormal{stable}} = 0.5$,
$\sigma_{\textnormal{stable}} = 1$, and “sparse” outliers
which appear in $10\%$ of the data, while Gaussian noise
with $\textnormal{SNR} = 30\textnormal{dB}$ is added to the
rest $90\%$. Sparse outliers are generated by the uniform
distribution and take values from the interval
$[-100, 100]$.

All methods were finely tuned to perform their best for
every considered setting of the environment. All curves in
the subsequent figures are the uniformly averaged results of
100 independent tests.

§.§ Scenario 1

<Ref> refer to the
scenario where the statistics (PDF) of the outliers stay
fixed throughout all iterations. Moreover, as it is
customary in the AdaFilt literature, system
$\vectgr{\theta}_*$ changes randomly at a specific time
index (here at time #20000) to test the tracking
ability of all competing methods.

<Ref> demonstrate
that <ref> shows high estimation accuracy while
tracking swiftly the estimandum $\vectgr{\theta}_*$. In
<ref>, <ref> reaches steady state faster
than the “best” versions of LMP ($p=1, 1.25$). An
inspection of <ref> suggests that <ref>
selects large values of $p$, within
$\{1, 1.25, 1.5, 1.75, 2\}$, in the beginning state of
learning to speed up convergence and then changes to select
small values of $p$ to score high accuracy in the steady

<ref> shows that <ref> outperforms
the kernel-based TD(0) <cit.> and
KLSPI <cit.>. The
predecessor <cit.> scores an almost identical
steady-state performance with <ref>, but with a slower
convergence speed. VKW-MCC <cit.> shows
excellent performance under sparse outliers. However, under
$\alpha$-stable outliers, it is outperformed by <ref>.

In <ref>, where several parameters of
<ref> are validated, $\alpha = 0.75$ shows the best
estimation accuracy among $\alpha \in \{ 0, 0.75, 0.9
\}$. Among them, $\alpha = 0$ does not perform well, which
strongly suggests that the long-term loss is crucial in
choosing $p$. The number of samples $N[n]$ does not seem to
affect performance significantly in this specific AdaFilt

[$\alpha$-stable outliers]
[Sparse outliers]

Scenario 1 (<ref>): <ref> against
LMP. [baseline = -0.5ex]
[mark size = 3pt, color = navy, line
width = .5pt ] o:
<ref> with $\alpha=0.9, N[n]\geq 1$. Marks
[baseline = -0.5ex] [mark
size = 3pt, color = black, line width = .5pt ]
x, [baseline
= -0.5ex] [mark size = 3pt, color =
americanrose, line width = .5pt ]
[baseline = -0.5ex] [mark
size = 3pt, color = applegreen, line width = .5pt ]
[baseline = -0.5ex] [mark
size = 3pt, color = darkmagenta, line width = .5pt ]
[baseline = -0.5ex] [mark
size = 3pt, color = peru, line width = .5pt ]
pentagon correspond to
(<ref>) with $p=1, 1.25, 1.5, 1.75, 2$,
respectively. Mark [baseline = -0.5ex]
[mark size = 3pt, color = burntorange,
line width = .5pt ]
10-pointed star denotes an
algorithm which randomly chooses $p$, $\forall n$.

[Sparse outliers]

Scenario 1 (<ref>): <ref> against
non-RL- and RL-based methods. [baseline =
-0.5ex] [mark size = 3pt, color = navy,
line width = .5pt ] o:
<ref> with $\alpha=0.9, N[n] \geq
1$. [baseline = -0.5ex] [mark
size = 3pt, color = black, line width = .5pt ]
x: <ref> with
$\alpha=0.9, N[n] = 1$. [baseline =
-0.5ex] [mark size = 3pt, color =
americanrose, line width = .5pt ]
triangle: Kernel-based
TD(0) with $\alpha =
0.9$ <cit.>. [baseline =
-0.5ex] [mark size = 3pt, color =
applegreen, line width = .5pt ]
square: <cit.>
with $p=1, \gamma_1 = 0.9, \gamma_2 =
0.99$. [baseline = -0.5ex]
[mark size = 3pt, color = darkmagenta,
line width = .5pt ]
diamond: KLSPI with
$\alpha=0.9$ <cit.>. [baseline
= -0.5ex] [mark size = 3pt, color = peru,
line width = .5pt ]
pentagon: mixed
norm <cit.>. [baseline =
-0.5ex] [mark size = 3pt, color =
burntorange, line width = .5pt ]
10-pointed star: the
predecessor <cit.> of the current
work. [baseline = -0.5ex]
[mark size = 3pt, color = magenta, line
width = .5pt ] |:
VKW-MCC <cit.>.

[Sparse outliers]

Scenario 1 (<ref>): Versions of
<ref> under several parameter
settings. [baseline = -0.5ex]
[mark size = 3pt, color = navy, line
width = .5pt ] o:
$\alpha = 0.9, N[n]\geq 1$. [baseline =
-0.5ex] [mark size = 3pt, color = black,
line width = .5pt ] x:
$\alpha=0.75, N[n]\geq 1$. [baseline =
-0.5ex] [mark size = 3pt, color =
americanrose, line width = .5pt ]
triangle: $\alpha = 0$.
[baseline = -0.5ex] [mark
size = 3pt, color = applegreen, line width = .5pt ]
$\alpha=0.9, N[n]=1$.  [baseline = -0.5ex]
[mark size = 3pt, color = darkmagenta,
line width = .5pt ]
$\alpha=0.75, N[n]=1$.

§.§ Scenario 2

<Ref> refer
to the scenario where the system $\vectgr{\theta}_*$ stays
fixed but the statistics (PDF) of the outliers change at a
specific time instance (here, at iteration
#20000). Both sparse and $\alpha$-stable outliers are
considered in the following two dynamic sub-scenarios:

* $\alpha$-stable outliers appear at
$n\in \{1, \ldots, \num{20000} \}$, followed by sparse
ones at $n\in \{\num{20001}, \ldots, \num{50000} \}$; and

* sparse outliers contaminate signals whenever
$n\in \{1, \ldots, \num{20000} \}$, while $\alpha$-stable
ones appear at
$n\in \{ \num{20001}, \ldots, \num{50000} \}$.

<Ref> show different steady-state performances of
<ref> after iteration #20000, despite the fact
that the statistics of the $\alpha$-stable outliers are the
same. More specifically, in <ref>, the steady-state
performance level of <ref> is almost identical to that
of LMP for $p = 1.25$, whereas LMP with $p = 1.25$ scores a
lower steady-state level than <ref> after iteration
#20000 in <ref>. On the other hand, <ref>
shows excellent performance in <ref> after the sudden
transition to sparse outliers. The previous discussion
concludes that <ref> appears to underperform in cases
where there is a sudden change from light-tailed outliers to
the heavy-tailed $\alpha$-stable ones. In contrast, notice
the excellent performance of <ref> under
$\alpha$-stable outliers in <ref>. Moreover, <ref>
demonstrates that kernel-based TD(0) <cit.>
deteriorates significantly whenever the outlier PDF suddenly
changes to $\alpha$-stable outliers. The rest of the
RL-based methods exhibit more or less robust performance
against the abrupt change to $\alpha$-stable outliers in

Finally, notice that under the heavy-tailed $\alpha$-stable
outliers, versions of <ref> with $\alpha > 0$ perform
better than version with $\alpha = 0$ in <ref>, whereas
versions $\alpha > 0$ and $\alpha = 0$ perform similarly
after iteration #20000 in <ref>.

[$\alpha$-stable $\to$
[Sparse $\to \alpha$-stable]

Scenario 2 (<ref>): <ref> against
LMP. [baseline = -0.5ex]
[mark size = 3pt, color = navy, line
width = .5pt ] o:
<ref> with $\alpha=0.9, N[n]\geq1$. Marks
[baseline = -0.5ex] [mark
size = 3pt, color = black, line width = .5pt ]
x, [baseline
= -0.5ex] [mark size = 3pt, color =
americanrose, line width = .5pt ]
[baseline = -0.5ex] [mark
size = 3pt, color = applegreen, line width = .5pt ]
[baseline = -0.5ex] [mark
size = 3pt, color = darkmagenta, line width = .5pt ]
[baseline = -0.5ex] [mark
size = 3pt, color = peru, line width = .5pt ]
pentagon correspond to
(<ref>) with $p=1, 1.25, 1.5, 1.75, 2$,
respectively. Mark [baseline = -0.5ex]
[mark size = 3pt, color = burntorange,
line width = .5pt ]
10-pointed star denotes an
algorithm which randomly chooses $p$, $\forall n$.

[$\alpha$-stable $\to$

Scenario 2 (<ref>): <ref> against
non-RL- and RL-based methods. [baseline =
-0.5ex] [mark size = 3pt, color = navy,
line width = .5pt ] o:
<ref> with $\alpha=0.9, N[n] \geq
1$. [baseline = -0.5ex] [mark
size = 3pt, color = black, line width = .5pt ]
x: <ref> with
$\alpha=0.9, N[n]=1$. [baseline = -0.5ex]
[mark size = 3pt, color = americanrose,
line width = .5pt ]
triangle: Kernel-based
TD(0) with $\alpha =
0.9$ <cit.>. [baseline =
-0.5ex] [mark size = 3pt, color =
applegreen, line width = .5pt ]
square: <cit.>
with $p=1, \gamma_1 = 0.9, \gamma_2 =
0.99$. [baseline = -0.5ex]
[mark size = 3pt, color = darkmagenta,
line width = .5pt ]
diamond: KLSPI with
$\alpha=0.9$ <cit.>. [baseline
= -0.5ex] [mark size = 3pt, color = peru,
line width = .5pt ]
pentagon: mixed
norm <cit.>. [baseline =
-0.5ex] [mark size = 3pt, color =
burntorange, line width = .5pt ]
10-pointed star: the
predecessor <cit.> of the current work.
[baseline = -0.5ex] [mark
size = 3pt, color = magenta, line width = .5pt ]
VKW-MCC <cit.>.

[$\alpha$-stable $\to$

Scenario 2 (<ref>): Versions of
<ref> under several parameter
settings. [baseline = -0.5ex]
[mark size = 3pt, color = navy, line
width = .5pt ] o:
$\alpha = 0.9, N[n]\geq 1$.  [baseline =
-0.5ex] [mark size = 3pt, color = black,
line width = .5pt ] x:
$\alpha = 0.75, N[n]\geq 1$.  [baseline =
-0.5ex] [mark size = 3pt, color =
americanrose, line width = .5pt ]
triangle: $\alpha = 0$.
[baseline = -0.5ex] [mark
size = 3pt, color = applegreen, line width = .5pt ]
$\alpha = 0.9, N[n]=1$.  [baseline =
-0.5ex] [mark size = 3pt, color =
darkmagenta, line width = .5pt ]
$\alpha = 0.75, N[n]=1$.

§ CONCLUSIONS

This paper designed novel nonparametric Bellman mappings
(B-Maps) in reproducing kernel Hilbert spaces (RKHSs) for
reinforcement learning (RL). The new B-Maps exhibit several
desirable features (see <ref>), with ample
degrees of freedom. To benefit from that freedom, a
variational framework (<ref>) was
provided to identify the free parameters of the B-Maps. As a
side effect, it was demonstrated that several
state-of-the-art designs become special cases of the
proposed B-Maps. Other non-trivial designs of B-Maps are
deferred to a future work. On the application front, the
manuscript considered the problem of selecting online, per
time instance, the “optimal” coefficient $p$ in the
least-mean-$p$-power method, with no prior information on
the outlier statistics and no training data. Interestingly,
the proposed design is general enough for the novel B-Maps
to be applied also to domains other than adaptive
filtering. Such application domains, together with their RL
designs, are currently under consideration and will be
presented soon at other publication venues.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

titleAdaptive Filters

titleMachine Learning—A Bayesian and Optimization Perspective

titleRobust Regression and Outlier Detection

journaltitleProc. IEEE
titleSignal processing with fractional lower order moments: Stable processes and their applications

journaltitleDigital Signal Processing
titleSmoothed least mean p-power error criterion for adaptive filtering

journaltitleMachine Learning
titleThe robustness of the p-norm algorithms

journaltitleDigital Signal Processing
titleNonlinear least $\ell_p$-norm filters for nonlinear autoregressive $\alpha$-stable processes

journaltitleIEEE Journal on Selected Areas in Communications
titleLeast mean p-power error criterion for adaptive FIR filter

booktitleIEEE Intern. Conf. on Acoustics, Speech and Signal Processing (ICASSP)
titleOutlier-robust kernel hierarchical-optimization RLS on a budget with affine constraints

journaltitleIEEE Trans. Signal Process.
titleCombination of recursive least p-norm algorithms for robust adaptive filtering in alpha-stable noise

journaltitleIEEE Trans. Signal Process.
titleAdaptive algorithm based on least mean p-power error criterion for Fourier analysis in additive noise

journaltitleIEEE Signal Processing Letters
titleA robust mixed-norm adaptive filter algorithm

booktitleInternational Joint Conference on Neural Networks
titleUsing correntropy as a cost function in linear adaptive filters

journaltitleIEEE Transactions on Circuits and Systems II: Express Briefs
titleAdaptive filtering under a variable kernel width maximum correntropy criterion

booktitleIEEE Intern. Conf. on Acoustics, Speech and Signal Processing (ICASSP)
titleDynamic selection of p-norm in linear adaptive filtering via online kernel-based reinforcement learning

Athena Scientific

titleReinforcement Learning and Optimal Control

Athena Scientific

titleNeuro-Dynamic Programming

Dover Publications

titleDynamic Programming

journaltitleTransactions of the American Mathematical Society
titleTheory of reproducing kernels

MIT Press

seriesAdaptive computation and machine learning
titleLearning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond

New York

titleA Distribution-Free Theory of Nonparametric Regression

booktitleAAAI Conference on Artificial Intelligence
titleDeep reinforcement learning with double Q-learning

journaltitleMachine Learning
titleKernel-based reinforcement learning

journaltitleIEEE Transactions on Automatic Control
titleKernel-based reinforcement learning in average-cost problems

journaltitleIEEE Transactions on Neural Networks
titleKernel-based least squares policy iteration for reinforcement learning

booktitleInternational Conference on Learning Representations
titlePrioritized experience replay

abstract$<$p$>$ This paper introduces new optimality-preserving operators on Q-functions. We first describe an operator for tabular representations, the consistent Bellman operator, which incorporates a notion of local policy consistency. We show that this local consistency leads to an increase in the action gap at each state; increasing this gap, we argue, mitigates the undesirable effects of approximation and estimation errors on the induced greedy policies. This operator can also be applied to discretized continuous space and time problems, and we provide empirical results evidencing superior performance in this context. Extending the idea of a locally consistent operator, we then derive sufficient conditions for an operator to preserve optimality, leading to a family of operators which includes our consistent Bellman operator. As corollaries we provide a proof of optimality for Baird's advantage learning algorithm and derive other gap-increasing operators with interesting properties. We conclude with an empirical study on 60 Atari 2600 games illustrating the strong potential of these new operators. $<$/p$>$
chapterTechnical Papers: Machine Learning Methods
journaltitleAAAI Conference on Artificial Intelligence
titleIncreasing the action gap: New operators for reinforcement learning

* Entry 'bellemare:16' (./refs.bib): Invalid format '2016/02/21' of date field 'date' - ignoring

Cambridge University Press

titleProbability with Martingales

New York

titleConvex Analysis and Monotone Operator Theory in Hilbert Spaces

titleReinforcement learning using kernel-based stochastic factorization

titleOn-line reinforcement learning using incremental kernel-based stochastic factorization

booktitleAAAI Conference on Artificial Intelligence
titleStructured kernel-based reinforcement learning

booktitleAAAI Conference on Artificial Intelligence
titleKernel-based reinforcement learning on representative states

booktitleIntern. Conf. on Machine Learning (ICML)
titleModeling transition dynamics in MDPs with RKHS embeddings

Montreal, Quebec, Canada

abstractIn this paper, we extend the Hilbert space embedding approach to handle conditional distributions. We derive a kernel estimate for the conditional embedding, and show its connection to ordinary embeddings. Conditional embeddings largely extend our ability to manipulate distributions in Hilbert spaces, and as an example, we derive a nonparametric method for modeling dynamical systems where the belief state of the system is maintained as a conditional embedding. Our method is very general in terms of both the domains and the types of distributions that it can handle, and we demonstrate the effectiveness of our method in various dynamical systems. We expect that conditional embeddings will have wider applications beyond modeling dynamical systems.
booktitleIntern. Conf. on Machine Learning (ICML)
titleHilbert space embeddings of conditional distributions with applications to dynamical systems

Haifa, Israel

abstractHidden Markov Models (HMMs) are important tools for modeling sequence data. However, they are restricted to discrete latent states, and are largely restricted to Gaussian and discrete observations. And, learning algorithms for HMMs have predominantly relied on local search heuristics, with the exception of spectral methods such as those described below. We propose a nonparametric HMM that extends traditional HMMs to structured and non-Gaussian continuous distributions. Furthermore, we derive a local-minimum-free kernel spectral algorithm for learning these HMMs. We apply our method to robot vision data, slot car inertial sensor data and audio event classification data, and show that in these applications, embedded HMMs exceed the previous state-of-the-art performance.
booktitleIntern. Conf. on Machine Learning (ICML)
titleHilbert Space Embeddings of Hidden Markov Models

New York: IEEE Press

journaltitleLearning and Approximate Dynamic Programming
titleImproved temporal difference methods with linear function approximation

abstractWe consider policy evaluation algorithms within the context of infinite-horizon dynamic programming problems with discounted cost. We focus on discrete-time dynamic systems with a large number of states, and we discuss two methods, which use simulation, temporal differences, and linear cost function approximation. The first method is a new gradient-like algorithm involving least-squares subproblems and a diminishing stepsize, which is based on the $\lambda$-policy iteration method of Bertsekas and Ioffe. The second method is the LSTD($\lambda$) algorithm recently proposed by Boyan, which for $\lambda$=0 coincides with the linear least-squares temporal-difference algorithm of Bradtke and Barto. At present, there is only a convergence result by Bradtke and Barto for the LSTD(0) algorithm. Here, we strengthen this result by showing the convergence of LSTD($\lambda$), with probability 1, for every $\lambda$ ∈ [0, 1].
journaltitleDiscrete Event Dynamic Systems
titleLeast Squares Policy Evaluation Algorithms with Linear Function Approximation

booktitleIEEE International Symposium on Approximate Dynamic Programming and Reinforcement Learning
titleKernelizing LSPE($\lambda$)

booktitleIEEE EMBS
titleReinforcement learning via kernel temporal difference

journaltitleIEEE Transactions on Automatic Control
titleAn analysis of temporal-difference learning with function approximation

abstractThis article introduces a class of incremental learning procedures specialized for prediction-that is, for using past experience with an incompletely known system to predict its future behavior. Whereas conventional prediction-learning methods assign credit by means of the difference between predicted and actual outcomes, the new methods assign credit by means of the difference between temporally successive predictions. Although such temporal-difference methods have been used in Samuel's checker player, Holland's bucket brigade, and the author's Adaptive Heuristic Critic, they have remained poorly understood. Here we prove their convergence and optimality for special cases and relate them to supervised-learning methods. For most real-world prediction problems, temporal-difference methods require less memory and less peak computation than conventional methods and they produce more accurate predictions. We argue that most problems to which supervised learning is currently applied are really prediction problems of the sort to which temporal-difference methods can be applied to advantage.
journaltitleMachine Learning
titleLearning to predict by the methods of temporal differences

abstractWe propose a new approach to reinforcement learning for control problems which combines value-function approximation with linear architectures and approximate policy iteration. This new approach is motivated by the least-squares temporal-difference learning algorithm (LSTD) for prediction problems, which is known for its efficient use of sample experiences compared to pure temporal-difference algorithms. Heretofore, LSTD has not had a straightforward application to control problems mainly because LSTD learns the state value function of a fixed policy which cannot be used for action selection and control without a model of the underlying process. Our new algorithm, least-squares policy iteration (LSPI), learns the state-action value function which allows for action selection without a model and for incremental policy improvement within a policy-iteration framework. LSPI is a model-free, off-policy method which can use efficiently (and reuse in each iteration) sample experiences collected in any manner. By separating the sample collection method, the choice of the linear approximation architecture, and the solution method, LSPI allows for focused attention on the distinct elements that contribute to practical reinforcement learning. LSPI is tested on the simple task of balancing an inverted pendulum and the harder task of balancing and riding a bicycle to a target location. In both cases, LSPI learns to control the pendulum or the bicycle by merely observing a relatively small number of trials where actions are selected randomly. LSPI is also compared against Q-learning (both with and without experience replay) using the same value function architecture. While LSPI achieves good performance fairly consistently on the difficult bicycle task, Q-learning variants were rarely able to balance for more than a small fraction of the time needed to reach the target location.
journaltitleJ. Mach. Learn. Res.
titleLeast-squares policy iteration

journaltitleJ. Machine Learning Research
titleRegularized policy iteration with nonparametric function spaces

abstractTD.$\lambda$/ is a popular family of algorithms for approximate policy evaluation in large MDPs. TD.$\lambda$/ works by incrementally updating the value function after each observed transition. It has two major drawbacks: it may make inefficient use of data, and it requires the user to manually tune a stepsize schedule for good performance. For the case of linear value function approximations and $\lambda$ = 0, the Least-Squares TD (LSTD) algorithm of Bradtke and Barto (1996, Machine learning, 22:1–3, 33–57) eliminates all stepsize parameters and improves data efficiency.
journaltitleMachine Learning
titleTechnical Update: Least-Squares Temporal Difference Learning

abstractWe introduce two new temporal diffence (TD) algorithms based on the theory of linear least-squares function approximation. We define an algorithm we call Least-Squares TD (LS TD) for which we prove probability-one convergence when it is used with a function approximator linear in the adjustable parameters. We then define a recursive version of this algorithm, Recursive Least-Squares TD (RLS TD). Although these new TD algorithms require more computation per time-step than do Sutton's TD($\lambda$) algorithms, they are more efficient in a statistical sense because they extract more information from training experiences. We describe a simulation experiment showing the substantial improvement in learning rate achieved by RLS TD in an example Markov prediction problem. To quantify this improvement, we introduce theTD error variance of a Markov chain, $\omega$TD, and experimentally conclude that the convergence rate of a TD algorithm depends linearly on $\omega$TD. In addition to converging more rapidly, LS TD and RLS TD do not have control parameters, such as a learning rate parameter, thus eliminating the possibility of achieving poor performance by an unlucky choice of parameters.
journaltitleMachine Learning
titleLinear Least-Squares algorithms for temporal difference learning

booktitleInternational Joint Conference on Artificial Intelligence
titleOnline Bellman residual and temporal difference algorithms with predictive error guarantees

abstractFitting the value function in a Markovian decision process by a linear superposition of M basis functions reduces the problem dimensionality from the number of states down to M, with good accuracy retained if the value function is a smooth function of its argument, the state vector. This paper provides, for both the discounted and undiscounted cases, three algorithms for computing the coefficients in the linear superposition: linear programming, policy iteration, and least squares.
journaltitleJournal of Mathematical Analysis and Applications
titleGeneralized polynomial approximations in Markovian decision processes

titleProximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces

Bejing, China

abstractWe propose two new algorithms for the sparse reinforcement learning problem based on different formulations. The first algorithm is an off-line method based on the alternating direction method of multipliers for solving a constrained formulation that explicitly controls the projected Bellman residual. The second algorithm is an online stochastic approximation algorithm that employs the regularized dual averaging technique, using the Lagrangian formulation. The convergence of both algorithms are established. We demonstrate the performance of these algorithms through two classical examples.
booktitleIntern. Conf. on Machine Learning (ICML)
month22–24 Jun
seriesProceedings of Machine Learning Research
titleSparse Reinforcement Learning via Convex Optimization

El Segundo, CA, USA

AI Access Foundation

abstractIn this paper, we introduce proximal gradient temporal difference learning, which provides a principled way of designing and analyzing true stochastic gradient temporal difference learning algorithms. We show how gradient TD (GTD) reinforcement learning methods can be formally derived, not by starting from their original objective functions, as previously attempted, but rather from a primal-dual saddle-point objective function. We also conduct a saddle-point error analysis to obtain finite-sample bounds on their performance. Previous analyses of this class of algorithms use stochastic approximation techniques to prove asymptotic convergence, and do not provide any finite-sample analysis. We also propose an accelerated algorithm, called GTD2-MP, that uses proximal "mirror maps" to yield an improved convergence rate. The results of our theoretical analysis imply that the GTD family of algorithms are comparable and may indeed be preferred over existing least squares TD methods for off-policy learning, due to their linear complexity. We provide experimental results showing the improved performance of our accelerated gradient TD methods.
journaltitleJ. Artif. Int. Res.
titleProximal Gradient Temporal Difference Learning: Stable Reinforcement Learning with Polynomial Sample Complexity

JMLR Workshop
Conference Proceedings

titleNonparametric tree graphical models via kernel embeddings

Taylor & Francis

titleFejér-monotone hybrid steepest descent method for affinely constrained and composite convex minimization tasks

seriesWiley Classics Library
titleIntroductory Functional Analysis with Applications

titleRandom features for large-scale kernel machines

Academic Press

edition2nd ed.
titleProbability and Measure Theory

Athena Scientific

titleConvex Analysis and Optimization

journaltitleJ. Machine Learning Research
titleDimensionality reduction for supervised learning with reproducing kernel Hilbert spaces

New York

edition2nd ed.
titleA Course in Functional Analysis

Now Publishers, Inc.

journaltitleFoundations and Trends in Machine Learning
titleAdaptation, learning, and optimization over networks

booktitleIEEE MLSP
titleStochastic kernel temporal difference for reinforcement learning

John Wiley & Sons

titleThe Elements of Integration and Lebesgue Measure

San Francisco, California

abstractWe describe the Fourier basis, a linear value function approximation scheme based on the Fourier series. We empirically demonstrate that it performs well compared to radial basis functions and the polynomial basis, the two most popular fixed bases for linear value function approximation, and is competitive with learned proto-value functions.
booktitleAAAI Conference on Artificial Intelligence
titleValue Function Approximation in Reinforcement Learning Using the Fourier Basis

titleRobust reinforcement learning using offline data

journaltitleIEEE Signal Processing Magazine
titleReinforcement learning in reproducing kernel Hilbert spaces

journaltitleIEEE Trans. Signal Process.
titleThe kernel recursive least-squares algorithm

booktitleIntern. Conf. on Machine Learning (ICML)
titleLeast-Squares Temporal Difference Learning

Institute of Mathematical Statistics

journaltitleThe Annals of Mathematical Statistics
titleA Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by Splines

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

titleAdaptive Filters

titleMachine Learning—A Bayesian and Optimization Perspective

titleRobust Regression and Outlier Detection

journaltitleProc. IEEE
titleSignal processing with fractional lower order moments: Stable processes and their applications

journaltitleDigital Signal Processing
titleSmoothed least mean p-power error criterion for adaptive filtering

journaltitleMachine Learning
titleThe robustness of the p-norm algorithms

journaltitleDigital Signal Processing
titleNonlinear least $\ell_p$-norm filters for nonlinear autoregressive $\alpha$-stable processes

journaltitleIEEE Journal on Selected Areas in Communications
titleLeast mean p-power error criterion for adaptive FIR filter

booktitleIEEE Intern. Conf. on Acoustics, Speech and Signal Processing (ICASSP)
titleOutlier-robust kernel hierarchical-optimization RLS on a budget with affine constraints

journaltitleIEEE Trans. Signal Process.
titleCombination of recursive least p-norm algorithms for robust adaptive filtering in alpha-stable noise

journaltitleIEEE Trans. Signal Process.
titleAdaptive algorithm based on least mean p-power error criterion for Fourier analysis in additive noise

journaltitleIEEE Signal Processing Letters
titleA robust mixed-norm adaptive filter algorithm

booktitleInternational Joint Conference on Neural Networks
titleUsing correntropy as a cost function in linear adaptive filters

journaltitleIEEE Transactions on Circuits and Systems II: Express Briefs
titleAdaptive filtering under a variable kernel width maximum correntropy criterion

booktitleIEEE Intern. Conf. on Acoustics, Speech and Signal Processing (ICASSP)
titleDynamic selection of p-norm in linear adaptive filtering via online kernel-based reinforcement learning

Athena Scientific

titleReinforcement Learning and Optimal Control

Athena Scientific

titleNeuro-Dynamic Programming

Dover Publications

titleDynamic Programming

journaltitleTransactions of the American Mathematical Society
titleTheory of reproducing kernels

MIT Press

seriesAdaptive computation and machine learning
titleLearning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond

New York

titleA Distribution-Free Theory of Nonparametric Regression

booktitleAAAI Conference on Artificial Intelligence
titleDeep reinforcement learning with double Q-learning

journaltitleMachine Learning
titleKernel-based reinforcement learning

journaltitleIEEE Transactions on Automatic Control
titleKernel-based reinforcement learning in average-cost problems

journaltitleIEEE Transactions on Neural Networks
titleKernel-based least squares policy iteration for reinforcement learning

booktitleInternational Conference on Learning Representations
titlePrioritized experience replay

abstract$<$p$>$ This paper introduces new optimality-preserving operators on Q-functions. We first describe an operator for tabular representations, the consistent Bellman operator, which incorporates a notion of local policy consistency. We show that this local consistency leads to an increase in the action gap at each state; increasing this gap, we argue, mitigates the undesirable effects of approximation and estimation errors on the induced greedy policies. This operator can also be applied to discretized continuous space and time problems, and we provide empirical results evidencing superior performance in this context. Extending the idea of a locally consistent operator, we then derive sufficient conditions for an operator to preserve optimality, leading to a family of operators which includes our consistent Bellman operator. As corollaries we provide a proof of optimality for Baird's advantage learning algorithm and derive other gap-increasing operators with interesting properties. We conclude with an empirical study on 60 Atari 2600 games illustrating the strong potential of these new operators. $<$/p$>$
chapterTechnical Papers: Machine Learning Methods
journaltitleAAAI Conference on Artificial Intelligence
titleIncreasing the action gap: New operators for reinforcement learning

* Entry 'bellemare:16' (./refs.bib): Invalid format '2016/02/21' of date field 'date' - ignoring

Cambridge University Press

titleProbability with Martingales

New York

titleConvex Analysis and Monotone Operator Theory in Hilbert Spaces

titleReinforcement learning using kernel-based stochastic factorization

titleOn-line reinforcement learning using incremental kernel-based stochastic factorization

booktitleAAAI Conference on Artificial Intelligence
titleStructured kernel-based reinforcement learning

booktitleAAAI Conference on Artificial Intelligence
titleKernel-based reinforcement learning on representative states

booktitleIntern. Conf. on Machine Learning (ICML)
titleModeling transition dynamics in MDPs with RKHS embeddings

Montreal, Quebec, Canada

abstractIn this paper, we extend the Hilbert space embedding approach to handle conditional distributions. We derive a kernel estimate for the conditional embedding, and show its connection to ordinary embeddings. Conditional embeddings largely extend our ability to manipulate distributions in Hilbert spaces, and as an example, we derive a nonparametric method for modeling dynamical systems where the belief state of the system is maintained as a conditional embedding. Our method is very general in terms of both the domains and the types of distributions that it can handle, and we demonstrate the effectiveness of our method in various dynamical systems. We expect that conditional embeddings will have wider applications beyond modeling dynamical systems.
booktitleIntern. Conf. on Machine Learning (ICML)
titleHilbert space embeddings of conditional distributions with applications to dynamical systems

Haifa, Israel

abstractHidden Markov Models (HMMs) are important tools for modeling sequence data. However, they are restricted to discrete latent states, and are largely restricted to Gaussian and discrete observations. And, learning algorithms for HMMs have predominantly relied on local search heuristics, with the exception of spectral methods such as those described below. We propose a nonparametric HMM that extends traditional HMMs to structured and non-Gaussian continuous distributions. Furthermore, we derive a local-minimum-free kernel spectral algorithm for learning these HMMs. We apply our method to robot vision data, slot car inertial sensor data and audio event classification data, and show that in these applications, embedded HMMs exceed the previous state-of-the-art performance.
booktitleIntern. Conf. on Machine Learning (ICML)
titleHilbert Space Embeddings of Hidden Markov Models

New York: IEEE Press

journaltitleLearning and Approximate Dynamic Programming
titleImproved temporal difference methods with linear function approximation

abstractWe consider policy evaluation algorithms within the context of infinite-horizon dynamic programming problems with discounted cost. We focus on discrete-time dynamic systems with a large number of states, and we discuss two methods, which use simulation, temporal differences, and linear cost function approximation. The first method is a new gradient-like algorithm involving least-squares subproblems and a diminishing stepsize, which is based on the $\lambda$-policy iteration method of Bertsekas and Ioffe. The second method is the LSTD($\lambda$) algorithm recently proposed by Boyan, which for $\lambda$=0 coincides with the linear least-squares temporal-difference algorithm of Bradtke and Barto. At present, there is only a convergence result by Bradtke and Barto for the LSTD(0) algorithm. Here, we strengthen this result by showing the convergence of LSTD($\lambda$), with probability 1, for every $\lambda$ ∈ [0, 1].
journaltitleDiscrete Event Dynamic Systems
titleLeast Squares Policy Evaluation Algorithms with Linear Function Approximation

booktitleIEEE International Symposium on Approximate Dynamic Programming and Reinforcement Learning
titleKernelizing LSPE($\lambda$)

booktitleIEEE EMBS
titleReinforcement learning via kernel temporal difference

journaltitleIEEE Transactions on Automatic Control
titleAn analysis of temporal-difference learning with function approximation

abstractThis article introduces a class of incremental learning procedures specialized for prediction-that is, for using past experience with an incompletely known system to predict its future behavior. Whereas conventional prediction-learning methods assign credit by means of the difference between predicted and actual outcomes, the new methods assign credit by means of the difference between temporally successive predictions. Although such temporal-difference methods have been used in Samuel's checker player, Holland's bucket brigade, and the author's Adaptive Heuristic Critic, they have remained poorly understood. Here we prove their convergence and optimality for special cases and relate them to supervised-learning methods. For most real-world prediction problems, temporal-difference methods require less memory and less peak computation than conventional methods and they produce more accurate predictions. We argue that most problems to which supervised learning is currently applied are really prediction problems of the sort to which temporal-difference methods can be applied to advantage.
journaltitleMachine Learning
titleLearning to predict by the methods of temporal differences

abstractWe propose a new approach to reinforcement learning for control problems which combines value-function approximation with linear architectures and approximate policy iteration. This new approach is motivated by the least-squares temporal-difference learning algorithm (LSTD) for prediction problems, which is known for its efficient use of sample experiences compared to pure temporal-difference algorithms. Heretofore, LSTD has not had a straightforward application to control problems mainly because LSTD learns the state value function of a fixed policy which cannot be used for action selection and control without a model of the underlying process. Our new algorithm, least-squares policy iteration (LSPI), learns the state-action value function which allows for action selection without a model and for incremental policy improvement within a policy-iteration framework. LSPI is a model-free, off-policy method which can use efficiently (and reuse in each iteration) sample experiences collected in any manner. By separating the sample collection method, the choice of the linear approximation architecture, and the solution method, LSPI allows for focused attention on the distinct elements that contribute to practical reinforcement learning. LSPI is tested on the simple task of balancing an inverted pendulum and the harder task of balancing and riding a bicycle to a target location. In both cases, LSPI learns to control the pendulum or the bicycle by merely observing a relatively small number of trials where actions are selected randomly. LSPI is also compared against Q-learning (both with and without experience replay) using the same value function architecture. While LSPI achieves good performance fairly consistently on the difficult bicycle task, Q-learning variants were rarely able to balance for more than a small fraction of the time needed to reach the target location.
journaltitleJ. Mach. Learn. Res.
titleLeast-squares policy iteration

journaltitleJ. Machine Learning Research
titleRegularized policy iteration with nonparametric function spaces

abstractTD.$\lambda$/ is a popular family of algorithms for approximate policy evaluation in large MDPs. TD.$\lambda$/ works by incrementally updating the value function after each observed transition. It has two major drawbacks: it may make inefficient use of data, and it requires the user to manually tune a stepsize schedule for good performance. For the case of linear value function approximations and $\lambda$ = 0, the Least-Squares TD (LSTD) algorithm of Bradtke and Barto (1996, Machine learning, 22:1–3, 33–57) eliminates all stepsize parameters and improves data efficiency.
journaltitleMachine Learning
titleTechnical Update: Least-Squares Temporal Difference Learning

abstractWe introduce two new temporal diffence (TD) algorithms based on the theory of linear least-squares function approximation. We define an algorithm we call Least-Squares TD (LS TD) for which we prove probability-one convergence when it is used with a function approximator linear in the adjustable parameters. We then define a recursive version of this algorithm, Recursive Least-Squares TD (RLS TD). Although these new TD algorithms require more computation per time-step than do Sutton's TD($\lambda$) algorithms, they are more efficient in a statistical sense because they extract more information from training experiences. We describe a simulation experiment showing the substantial improvement in learning rate achieved by RLS TD in an example Markov prediction problem. To quantify this improvement, we introduce theTD error variance of a Markov chain, $\omega$TD, and experimentally conclude that the convergence rate of a TD algorithm depends linearly on $\omega$TD. In addition to converging more rapidly, LS TD and RLS TD do not have control parameters, such as a learning rate parameter, thus eliminating the possibility of achieving poor performance by an unlucky choice of parameters.
journaltitleMachine Learning
titleLinear Least-Squares algorithms for temporal difference learning

booktitleInternational Joint Conference on Artificial Intelligence
titleOnline Bellman residual and temporal difference algorithms with predictive error guarantees

abstractFitting the value function in a Markovian decision process by a linear superposition of M basis functions reduces the problem dimensionality from the number of states down to M, with good accuracy retained if the value function is a smooth function of its argument, the state vector. This paper provides, for both the discounted and undiscounted cases, three algorithms for computing the coefficients in the linear superposition: linear programming, policy iteration, and least squares.
journaltitleJournal of Mathematical Analysis and Applications
titleGeneralized polynomial approximations in Markovian decision processes

titleProximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces

Bejing, China

abstractWe propose two new algorithms for the sparse reinforcement learning problem based on different formulations. The first algorithm is an off-line method based on the alternating direction method of multipliers for solving a constrained formulation that explicitly controls the projected Bellman residual. The second algorithm is an online stochastic approximation algorithm that employs the regularized dual averaging technique, using the Lagrangian formulation. The convergence of both algorithms are established. We demonstrate the performance of these algorithms through two classical examples.
booktitleIntern. Conf. on Machine Learning (ICML)
month22–24 Jun
seriesProceedings of Machine Learning Research
titleSparse Reinforcement Learning via Convex Optimization

El Segundo, CA, USA

AI Access Foundation

abstractIn this paper, we introduce proximal gradient temporal difference learning, which provides a principled way of designing and analyzing true stochastic gradient temporal difference learning algorithms. We show how gradient TD (GTD) reinforcement learning methods can be formally derived, not by starting from their original objective functions, as previously attempted, but rather from a primal-dual saddle-point objective function. We also conduct a saddle-point error analysis to obtain finite-sample bounds on their performance. Previous analyses of this class of algorithms use stochastic approximation techniques to prove asymptotic convergence, and do not provide any finite-sample analysis. We also propose an accelerated algorithm, called GTD2-MP, that uses proximal "mirror maps" to yield an improved convergence rate. The results of our theoretical analysis imply that the GTD family of algorithms are comparable and may indeed be preferred over existing least squares TD methods for off-policy learning, due to their linear complexity. We provide experimental results showing the improved performance of our accelerated gradient TD methods.
journaltitleJ. Artif. Int. Res.
titleProximal Gradient Temporal Difference Learning: Stable Reinforcement Learning with Polynomial Sample Complexity

JMLR Workshop
Conference Proceedings

titleNonparametric tree graphical models via kernel embeddings

Taylor & Francis

titleFejér-monotone hybrid steepest descent method for affinely constrained and composite convex minimization tasks

seriesWiley Classics Library
titleIntroductory Functional Analysis with Applications

titleRandom features for large-scale kernel machines

Academic Press

edition2nd ed.
titleProbability and Measure Theory

Athena Scientific

titleConvex Analysis and Optimization

journaltitleJ. Machine Learning Research
titleDimensionality reduction for supervised learning with reproducing kernel Hilbert spaces

New York

edition2nd ed.
titleA Course in Functional Analysis

Now Publishers, Inc.

journaltitleFoundations and Trends in Machine Learning
titleAdaptation, learning, and optimization over networks

booktitleIEEE MLSP
titleStochastic kernel temporal difference for reinforcement learning

John Wiley & Sons

titleThe Elements of Integration and Lebesgue Measure

San Francisco, California

abstractWe describe the Fourier basis, a linear value function approximation scheme based on the Fourier series. We empirically demonstrate that it performs well compared to radial basis functions and the polynomial basis, the two most popular fixed bases for linear value function approximation, and is competitive with learned proto-value functions.
booktitleAAAI Conference on Artificial Intelligence
titleValue Function Approximation in Reinforcement Learning Using the Fourier Basis

titleRobust reinforcement learning using offline data

journaltitleIEEE Signal Processing Magazine
titleReinforcement learning in reproducing kernel Hilbert spaces

journaltitleIEEE Trans. Signal Process.
titleThe kernel recursive least-squares algorithm

booktitleIntern. Conf. on Machine Learning (ICML)
titleLeast-Squares Temporal Difference Learning

Institute of Mathematical Statistics

journaltitleThe Annals of Mathematical Statistics
titleA Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by Splines

§ PROOF OF <REF>

First, recall that the orthogonal projection mapping
$P_{\vectgr{\Phi}_{\mathcal{T}_N}}$ onto the linear span of
$\{ \varphi(\vect{z}_i)\}_{i=1}^N$ is provided by
$P_{\vectgr{\Phi}_{\mathcal{T}_N}} =
\vectgr{\Phi}_{\mathcal{T}_N}
\vect{K}_{\mathcal{T}_N}^{\dagger}
\vectgr{\Phi}_{\mathcal{T}_N}^{\intercal}$. Moreover, let
$P_{\vectgr{\Phi}_{\mathcal{T}_N}^{\perp}}$ denote the
orthogonal projection mapping onto the orthogonal complement
of the linear span of $\{
\varphi(\vect{z}_i)\}_{i=1}^N$. The Pythagoras theorem
states that
$\Id = P_{\vectgr{\Phi}_{\mathcal{T}_N}} +
P_{\vectgr{\Phi}_{\mathcal{T}_N}^{\perp}}$, where $\Id$ is
the identity operator in $\mathcal{H}$.

$\vect{c}\coloneqq \vectgr{\gamma} + \alpha \vectgr{\Upsilon}
\vectgr{\Phi}_{\mu_{\star}}^{\textnormal{av} \intercal} Q$ for convenience, and observe that

\begin{align}
& ( \vect{c} - \vect{K}_{\mathcal{T}_N}^{\dagger}
\vectgr{\Phi}_{\mathcal{T}_N}^{\intercal}Q )^{\intercal}
\vect{K}_{\mathcal{T}_N}
( \vect{c} - \vect{K}_{\mathcal{T}_N}^{\dagger}
\vectgr{\Phi}_{\mathcal{T}_N}^{\intercal}Q ) \notag\\
& = ( \vect{c} - \vect{K}_{\mathcal{T}_N}^{\dagger}
\vectgr{\Phi}_{\mathcal{T}_N}^{\intercal}Q )^{\intercal}
\vectgr{\Phi}_{\mathcal{T}_N}^{\intercal}
\vectgr{\Phi}_{\mathcal{T}_N} ( \vect{c} -
\vect{K}_{\mathcal{T}_N}^{\dagger}
\vectgr{\Phi}_{\mathcal{T}_N}^{\intercal}Q ) \notag\\
& = \innerp{ \vectgr{\Phi}_{\mathcal{T}_N} (\vect{c} -
\vect{K}_{\mathcal{T}_N}^{\dagger}
\vectgr{\Phi}_{\mathcal{T}_N}^{\intercal}Q)}{
\vectgr{\Phi}_{\mathcal{T}_N}(\vect{c} -
\vect{K}_{\mathcal{T}_N}^{\dagger}
\vectgr{\Phi}_{\mathcal{T}_N}^{\intercal}Q)}_{\mathcal{H}}
\notag\\
& = \norm{ \vectgr{\Phi}_{\mathcal{T}_N} \vect{c} -
\vectgr{\Phi}_{\mathcal{T}_N}
\vect{K}_{\mathcal{T}_N}^{\dagger}
\vectgr{\Phi}_{\mathcal{T}_N}^{\intercal} Q
}^2_{\mathcal{H}} \notag\\
& = \norm{ \vectgr{\Phi}_{\mathcal{T}_N} \vect{c} - P_{\vectgr{\Phi}_{\mathcal{T}_N}}
Q  }^2_{\mathcal{H}} \,. \label{LSPE.regularizer}
\end{align}

A change of variables and the Pythagoras theorem suggest that

=   T_LSPE, μ(Q)

=         min_ Q^' ∈ℋ
Q^' - g - αΦ_μ^'⊺Q _^N^2

+ σ Q^' - Q ^2_ℋ

=        min_ Q^' ∈ℋ

Φ_𝒯_N^⊺ (Q^' -
P_Φ_𝒯_N^⊥ Q) -
g - αΦ_μ^'⊺Q _^N^2

+ σ Q^' - Q ^2_ℋ

=        min_ Q^'' ∈ℋ
Q^'' - g -

+ σ Q^'' +
P_Φ_𝒯_N^⊥ Q - Q

=        min_ Q^'' ∈ℋ
Q^'' - g - αΦ_μ^'⊺Q _^N^2

+ σ Q^'' -
P_Φ_𝒯_N Q

=        Φ_𝒯_N (
+ σI_N )^-1 g

+ σΦ_𝒯_N (
+ σI_N )^-1
Φ_𝒯_N^⊺ Q

+ αΦ_𝒯_N (
+ σI_N )^-1
Φ_μ^'⊺ Q

$\vectgr{\Phi}_{\mathcal{T}_N} ( \vect{K}_{\mathcal{T}_N} +
\sigma \vect{I}_N )^{-1} = ( \vectgr{\Phi}_{\mathcal{T}_N}
\vectgr{\Phi}_{\mathcal{T}_N}^{\intercal} + \sigma\Id)^{-1}
\vectgr{\Phi}_{\mathcal{T}_N}$ was used in the last

Moreover, notice again by the Pythagoras theorem and
$P_{\vectgr{\Phi}_{\mathcal{T}_N}}^2 =
P_{\vectgr{\Phi}_{\mathcal{T}_N}}$ that

Q^'' - g - αΦ_μ^'⊺Q _^N^2
+ σ Q^'' -
P_Φ_𝒯_N Q ^2_ℋ

Q^'' - g - αΦ_μ^'⊺Q _^N^2
+ σ P_Φ_𝒯_N(
Q^'' - P_Φ_𝒯_N
Q) ^2_ℋ

P_Φ_𝒯_N Q^'' -
g - αΦ_μ^'⊺ Q _^N^2

+ σ P_Φ_𝒯_N
Q^'' - P_Φ_𝒯_N Q
^2_ℋ  ,

which clearly suggests that the minimizer in
(<ref>) lies in the linear span of
$\{ \varphi(\vect{z}_i)\}_{i=1}^N \Leftrightarrow (
Q^{\prime\prime} = \vectgr{\Phi}_{\mathcal{T}_N} \vect{c},\
\text{for}\ \exists \vect{c}\in \Real^N) \Leftrightarrow (
Q^{\prime\prime} = P_{\vectgr{\Phi}_{\mathcal{T}_N}}
Q^{\prime\prime} )$. Hence,

=   T_LSPE, μQ

min_ Q^'' ∈ℋ
Q^'' =
P_Φ_𝒯_N Q^''
Q^'' - g - αΦ_μ^'⊺Q _^N^2

+ σ Q^'' -
P_Φ_𝒯_N Q ^2_ℋ

=        Φ_𝒯_N c_⋆  ,

where $\vect{c}_{\star}$ satisfies

=   min_ c∈^N
Φ_𝒯_N c -
g - αΦ_μ^'⊺ Q _^N^2

=    + σ
Φ_𝒯_N c -
P_Φ_𝒯_N Q

min_ c∈^N    K_𝒯_N
c - g - αΦ_μ^'⊺Q _^N^2
^ ℒ(γ, Υ )

=    + σ
( c - K_𝒯_N^†
Φ_𝒯_N^⊺ Q
)^⊺ K_𝒯_N ( c -
Φ_𝒯_N^⊺ Q)_
ℛ(γ, Υ )

( K_𝒯_N + σI_N )^-1
( g + σK_𝒯_N^†
Φ_𝒯_N^⊺ Q + αΦ_μ^'⊺Q )

( K_𝒯_N + σI_N )^-1

+ ( K_𝒯_N + σI_N
[ σK_𝒯_N^†  ,
αI_N ]

( K_𝒯_N + σI_N )^-1

+ α( K_𝒯_N + σI_N )^-1 [ (σ/α)
K_𝒯_N^†  , I_N ]
⊺ Q

γ_⋆ + αΥ_⋆
⊺ Q  ,
and where
$\vectgr{\gamma}_{\star} \coloneqq (
\vect{K}_{\mathcal{T}_N} + \sigma \vect{I}_N )^{-1}
\vect{g}$ and
$\vectgr{\Upsilon}_{\star} \coloneqq (
\vect{K}_{\mathcal{T}_N} + \sigma \vect{I}_N )^{-1} [
(\sigma/\alpha) \vect{K}_{\mathcal{T}_N}^{\dagger} \,,
\vect{I}_N ]$.

Under the light of (<ref>), the previous
findings are summarized as follows:
$(\vectgr{\gamma}_{\star}, \vectgr{\Upsilon}_{\star})$
satisfies (<ref>) iff
$\vect{c}_{\star} = \vectgr{\gamma}_{\star} + \alpha
\vectgr{\Upsilon}_{\star}
\vectgr{\Phi}_{\mu_{\star}}^{\textnormal{av} \intercal} Q$
is one of the minimizers in (<ref>) iff
$T_{\textnormal{LSPE}, \mu}(Q) =
\vectgr{\Phi}_{\mathcal{T}_N} \vect{c}_{\star} =
T_{\mu_{\star}}(Q)$. These equivalences establish the claim
of <ref>. As an additional remark,
notice that $T_{\textnormal{LSPE}, \mu}(Q) = Q$
in (<ref>) yields (<ref>).

The proofs of <Ref>
follow similar steps with the proof of
<ref> and are thus skipped.

§ PROOF OF <REF>

First, the following lemma and its proof are in order.

For any $Q_1,Q_2\in\mathcal{H}$,
$\vect{s}\in\mathfrak{S}$, there exists $\delta \neq 0$
s.t. for any
$\epsilon \in ( 0, \sqrt{\lvert\delta\rvert})$ an
$a^{\prime} \in\mathfrak{A}$ can be always selected s.t.
\begin{align}
\bigl[ \inf\nolimits_{a\in\mathfrak{A}}Q_1(\vect{s},a)
& - \inf\nolimits_{a\in\mathfrak{A}}Q_2(\vect{s},a)
\bigr]^2 \notag\\
& \leq \left[ Q_1(\vect{s},a^\prime) -
Q_2(\vect{s},a^\prime) \right]^2 + \epsilon
\,. \label{epsilon-threshold}
\end{align}

$\delta \coloneqq \inf_{a\in\mathfrak{A}}Q_1(\vect{s},a) -
\inf_{a\in\mathfrak{A}}Q_2(\vect{s},a)$. Whenever
$\delta = 0$, (<ref>) holds true
trivially. Consider now the case where $\delta > 0$, take
any $\epsilon \in (0, \sqrt{\delta})$, and define
$\epsilon^{\prime} \coloneqq \delta - \sqrt{\delta^2 -
\epsilon} > 0$ so that
$\epsilon = 2\epsilon^{\prime} \delta -
\epsilon^{\prime}{}^2$ and
$\delta - \epsilon^{\prime} >0$. Then,
$\exists a^\prime\in\mathfrak{A}$ s.t.  $Q_2(\vect{s}, a^{\prime}) \leq \inf_{a\in\mathfrak{A}}
Q_2(\vect{s}, a) + \epsilon^{\prime}$. This result
together with
$\inf_{a\in\mathfrak{A}} Q_1(\vect{s}, a) \leq
Q_1(\vect{s}, a^{\prime})$ suggest:

\begin{align*}
Q_1(\vect{s}, a^{\prime}) - Q_2(\vect{s}, a^{\prime}) \geq
\inf_{a\in\mathfrak{A}}Q_1(\vect{s}, a) -
\inf_{a\in\mathfrak{A}} Q_2(\vect{s}, a) -
\epsilon^{\prime}\,,
\end{align*}

where the right-hand side is positive, and

\begin{align*}
& \left[ Q_1(\vect{s},a^\prime)-Q_2(\vect{s},a^\prime)
\right]^2 \\
& \geq \left[ \inf\nolimits_{a\in\mathfrak{A}} Q_1(\vect{s}, a) -
\inf\nolimits_{a\in\mathfrak{A}}Q_2(\vect{s}, a)
\right]^2 - 2\epsilon^{\prime} \delta +
\epsilon^{\prime}{}^2 \\
& = \left[ \inf\nolimits_{a\in\mathfrak{A}} Q_1(\vect{s}, a) -
\inf\nolimits_{a\in\mathfrak{A}}Q_2(\vect{s}, a) \right]^2 - \epsilon
\,,
\end{align*}

which establishes (<ref>). The proof for
the case $\delta < 0$ follows exactly the previous steps
by using $-\delta$ instead of $\delta$ and by
interchanging $Q_1$ with $Q_2$.

Property (<ref>) is established as follows:
$\forall Q_1,Q_2\in\mathcal{H}$,

\begin{align*}
& \norm{T_{\mu} (Q_1) - T_{\mu}(Q_2)}_{\mathcal{H}}^2 \\
& = \alpha^2\innerp{
\vectgr{\Psi}\vectgr{\Phi}^{\textnormal{av}}_{\mu}{}^{\intercal}
(Q_1-Q_2) }{
\vectgr{\Psi}\vectgr{\Phi}^{\textnormal{av}}_{\mu}{}^{\intercal}
(Q_1-Q_2)}_{\mathcal{H}} \\
& = \alpha^2\innerp{
\vectgr{\Phi}^{\textnormal{av}}_{\mu}{}^{\intercal}
(Q_1-Q_2) }{ \vectgr{\Psi}^{\intercal}
\vectgr{\Psi}\vectgr{\Phi}^{\textnormal{av}}_{\mu}{}^{\intercal}
(Q_1-Q_2)} \\
& \leq \alpha^2 \norm{\vectgr{\Psi}^\intercal
\vectgr{\Psi}}_2 \innerp{
Q_1-Q_2 }{ \vectgr{\Phi}^{\textnormal{av}}_{\mu}
\vectgr{\Phi}^{\textnormal{av}}_{\mu}{}^{\intercal}
(Q_1-Q_2)}_{\mathcal{H}} \\
& \leq \alpha^2 \norm{ \vect{K}_{\Psi} }_2 \cdot \norm{
\vectgr{\Phi}^{\textnormal{av}}_{\mu}
\vectgr{\Phi}^{\textnormal{av}}_{\mu}{}^{\intercal} }_2
\cdot \norm{ Q_1-Q_2 }^2_{\mathcal{H}} \\
& \leq \beta^2 \norm{Q_1-Q_2}^2_{\mathcal{H}} \,,
\end{align*}

where observation
$\norm{ \vectgr{\Phi}^{\textnormal{av}}_{\mu}
\vectgr{\Phi}^{\textnormal{av}}_{\mu}{}^{\intercal} }_2 =
\norm{ \vectgr{\Phi}^{\textnormal{av}}_{\mu}{}^{\intercal}
\vectgr{\Phi}^{\textnormal{av}}_{\mu} }_2 = \norm{
\vect{K}_{\mu}^{\textnormal{av}} }_2$ and (<ref>)
were used to obtain the last inequality.

The proof of (<ref>) follows. For any
$Q_1, Q_2 \in \mathcal{H}$,

\begin{align}
& \norm{T(Q_1) - T(Q_2)}_{\mathcal{H}}^2 \notag \\
& = \alpha^2 \norm{ \vectgr{\Psi}
(\vecinf_{\mathcal{S}_{\textnormal{av}}}(Q_1) -
\vecinf_{\mathcal{S}_{\textnormal{av}}}(Q_2)
)}_{\mathcal{H}}^2 \notag\\
& \leq \alpha^2 \norm{ \vect{K}_{\Psi} }_2 \, \norm{
\vecinf_{\mathcal{S}_{\textnormal{av}}}(Q_1) -
\vecinf_{\mathcal{S}_{\textnormal{av}}}(Q_2)
}^2 \notag\\
& = \alpha^2 \norm{ \vect{K}_{\Psi} }_2
\sum_{i=1}^{N_{\textnormal{av}}}
\bigl[ \inf_{a_i \in\mathfrak{A}}
Q_1(\vect{s}_i^{\textnormal{av}}, a_i) -
\inf_{a_i\in\mathfrak{A}}
Q_2(\vect{s}_i^{\textnormal{av}}, a_i) \bigr]^2
\,. \label{T.Lip.step.1}
\end{align}

According to <ref>, there exist
$\{ \delta_i \neq 0 \}_{i=1}^{N_{\textnormal{av}}}$ s.t.for any
$\epsilon\in (0, \min_{i\in \{ 1, \ldots,
N_{\textnormal{av}}\}}\{ \sqrt{\lvert \delta_i \rvert} \}
)$ actions $\{ a_i^{\prime} \}_{i=1}^{N_{\textnormal{av}}}$
can be selected so that (<ref>) yields

≤  T(Q_1) -

α^2  K_Ψ _2
[ Q_1(s_i^av, a_i^') -
a_i^') ]^2

+ ϵα^2 N_av
K_Ψ _2  .

Take now any stationary policy
$\mu^{\prime} \in \mathcal{M}$ s.t.$\mu^{\prime}( \vect{s}_i^{\textnormal{av}} ) =
a_i^{\prime}$, $\forall i$. Then, by
$\vectgr{\Phi}_{\mu^{\prime}}^{\textnormal{av}} \coloneqq [
\varphi(\vect{s}_1^{\textnormal{av}}, \mu^{\prime}(
\vect{s}_1^{\textnormal{av}} ) ), \ldots,
\varphi(\vect{s}_{N_{\textnormal{av}}}^{\textnormal{av}},
\mu^{\prime}(
\vect{s}_{N_{\textnormal{av}}}^{\textnormal{av}} ) )]$,

\begin{align*}
& \sum\nolimits_{i=1}^{N_{\textnormal{av}}}