Bridging the Gap Between Target Networks and Functional Regularization

Alexandre Piché* Valentin Thomas* Joseph Marino Rafael Pardiñas

Mila, Université de Montréal ServiceNow Research Mila, Université de Montréal
DeepMind ServiceNow Research

Gian Maria Marconi Christopher Pal Mohammad Emtiyaz Khan

RIKEN Mila, Polytechnique Montréal Canada CIFAR AI Chair RIKEN

###### Abstract

Bootstrapping is behind much of the successes of Deep Reinforcement Learning.
However, learning the value function via bootstrapping often leads to unstable
training due to fast-changing target values. Target Networks are employed to
stabilize training by using an additional set of lagging parameters to
estimate the target values. Despite the popularity of Target Networks, their
effect on the optimization is still misunderstood. In this work, we show that
they act as an implicit regularizer. This regularizer has disadvantages such
as being inflexible and non convex. To overcome these issues, we propose an
explicit Functional Regularization that is a convex regularizer in function
space and can easily be tuned. We analyze the convergence of our method
theoretically and empirically demonstrate that replacing Target Networks with
the more theoretically grounded Functional Regularization approach leads to
better sample efficiency and performance improvements.

##  1 Introduction

Value functions are at the core of deep Reinforcement Learning (RL)
algorithms. In order to learn a value function via regression, we need to
estimate the target value of the state. Estimating the target value using
Monte Carlo roll-outs requires complete trajectories and can have high
variance. These issues make value estimation via Monte Carlo inefficient and
unpractical in complex environments. Temporal Difference (TD) (Sutton,, 1988)
algorithm addresses these issues by using bootstrapping (Sutton and Barto,,
2018). Specifically, the value of a state is estimated using the immediate
reward and the discounted predicted value of its successor. Bootstrapping has
potentially lower variance than Monte Carlo, particularly in the off-policy
settings, and does not require entire trajectories to estimate the target
value. Bootstrapping can unfortunately be unstable as the target value is
estimated with constantly updated parameters.

To stabilize value function training, Mnih et al., (2013) proposed using
Target Networks (TN): an additional set of lagging parameters to estimate the
target value. Today TNs are central to most modern deep RL algorithms (Mnih et
al.,, 2013; Lillicrap et al.,, 2015; Abdolmaleki et al., 2018b, ; Haarnoja et
al.,, 2018; Fujimoto et al.,, 2018; Hausknecht and Stone,, 2015; Van Hasselt
et al.,, 2016; Hessel et al.,, 2018). Their popularity is due to the ease of
implementation, no computation overhead, and their demonstrated effectiveness
in a range of domains. Despite their popularity, the inner workings of TNs and
how they stabilize the optimization of the value function remain unclear.
While Van Hasselt et al., (2018) empirically shows that TNs help but do not
prevent divergence, Zhang et al., (2021) shows that a variant of TNs can
prevent divergence in simple cases.

In this work, we shed light on the regularization implicitly performed by TNs
and how it is related to a regularization in the $Q$-function space whose
strength is dictated by the discount factor $\gamma$. However, this
regularization cannot be written as the gradient of a convex regularizer, as
is commonplace in optimization. We prove that, because of this, TNs can
unstabilize TD instead of making it more stable. This leads us to propose a
simple Functional Regularization (FR) alternative that has the advantages of
provably ensuring TD remains stable while being more flexible than TN.

We then empirically confirm our theoretical results. We first compare the
stability of TN and FR on a simple two-state MDP (Tsitsiklis and Van Roy,,
1996). Then, in the Four Rooms environment (Sutton et al.,, 1999), we find
that when combined with Deep Neural Networks (DNNs), the added flexibility of
FR results in better performance, especially when learning with off-policy
data. Finally, on the Atari suite (Bellemare et al.,, 2013), we demonstrate
that replacing TN with FR on 3 popular algorithms leads to performance gains.

##  2 Background

Preliminaries. We consider the general case of a Markov Decision Process (MDP)
(Puterman,, 2014) defined by
$\\{{\mathcal{S}},{\mathcal{A}},p,r,\gamma,\mu\\}$, where ${\mathcal{S}}$ and
${\mathcal{A}}$ respectively denote the finite state and action spaces,
$p({\mathbf{s}}^{\prime}|{\mathbf{s}},{\mathbf{a}})$ represents the
environment transition dynamics, i.e the distribution of the next state taking
action ${\mathbf{a}}$ in state ${\mathbf{s}}$.
$r\colon{\mathcal{S}}\times{\mathcal{A}}\to\mathbb{R}$ denotes the reward
function, $\gamma\in[0,1)$ is the discount factor, and $\mu$ is the initial
state distribution. For a given policy,
$\pi:{\mathcal{S}}\rightarrow\Delta({\mathcal{A}}$), a starting state
${\mathbf{s}}$ and action ${\mathbf{a}}$, the value function
$Q^{\pi}\in\mathbb{R}^{|{\mathcal{S}}|\times|{\mathcal{A}}|}$ is the expected
discounted sum of rewards:

$Q^{\pi}({\mathbf{s}},{\mathbf{a}})=\mathbb{E}_{\pi}\bigg{[}\sum_{t\geq
0}\gamma^{r}r({\mathbf{s}}_{t},{\mathbf{a}}_{t})|{\mathbf{s}}_{0}={\mathbf{s}},{\mathbf{a}}_{0}={\mathbf{a}}\bigg{]}.$
(1)

Additionally, the value function satisfies the Bellman equation (Bellman,,
1966)

$\displaystyle Q^{\pi}$ $\displaystyle=R+\gamma
P^{\pi}Q^{\pi}\equiv{\mathcal{T}}Q^{\pi}$ (2)

where $R\in\mathbb{R}^{|S|\cdot|A|}$ the reward vector and the state-action to
state-action transition matrix
$P^{\pi}\in\mathbb{R}^{|{\mathcal{S}}|\cdot|{\mathcal{A}}|\times|{\mathcal{S}}|\cdot|{\mathcal{A}}|}$
where
$P^{\pi}\big{[}({\mathbf{s}},{\mathbf{a}}),({\mathbf{s}}^{\prime},{\mathbf{a}}^{\prime})\big{]}=\pi({\mathbf{a}}^{\prime}|{\mathbf{s}}^{\prime})\cdot
p({\mathbf{s}}^{\prime}|{\mathbf{s}},{\mathbf{a}})$ and
${\mathcal{T}}:\mathbb{R}^{|{\mathcal{S}}|\cdot|{\mathcal{A}}|\times|{\mathcal{S}}|\cdot|{\mathcal{A}}|}\rightarrow\mathbb{R}^{|{\mathcal{S}}|\cdot|{\mathcal{A}}|\times|{\mathcal{S}}|\cdot|{\mathcal{A}}|}$
is the Bellman operator.

Linear Function Approximation (LFA). The value function $Q^{\pi}$ can be
approximated via a linear function. For a fixed feature matrix
$\Phi\in\mathbb{R}^{|S|\cdot|A|\times p}$, our aim is to learn a parameter
vector of dimension $p$, $w\in\mathbb{R}^{p}$, so that $Q_{w}\equiv\Phi w$
approximates $Q^{\pi}$. We denote the the off-policy sampling distribution by
the diagonal matrix $D\in\mathbb{R}^{|S|\cdot|A|\times|S|\cdot|A|}$ with
diagonal entries $d(s,a)$, positive and summing to 1. The update rule given by
the TD(0) semi-gradient (Sutton and Barto,, 2018) is given by

$\nabla_{w}\ell^{\text{TD}}(w)=-\Phi^{\top}D(R+\gamma P^{\pi}\Phi w-\Phi w)$
(3)

where the remainder of the return is estimated via bootstrapping, i.e.,
$P^{\pi}\Phi w$.

Deep Neural Networks (DNNs) Approximation. In complex environments, linear
functions can result in a poor approximation of $Q^{\pi}$. Instead, non-linear
functions, such as DNNs, are used to parametrize $Q_{w}$ and improve the
approximation to $Q^{\pi}$. But using DNNs to estimate $Q^{\pi}$ using off-
policy data and bootstrapping can be unstable and diverge (Sutton and Barto,,
2018; Van Hasselt et al.,, 2018). It is common to use a lagging set of weights
$\bar{w}$ to estimate the next value function to mitigate divergence (Mnih et
al.,, 2013; Lillicrap et al.,, 2015). The network parametrized by the set of
lagging weights is commonly referred to as a target network. Despite the
popularity of target networks, there are still gaps in our understanding of
the impact it has on learning dynamics.

##  3 Functional Regularization for stable Reinforcement Learning

###  3.1 Understanding Target Network’s implicit regularization

In this subsection, we will look more closely at the effects TNs have on the
optimization. We place ourselves in the classical Linear Function
Approximation (LFA) setting (Sutton and Barto,, 2018) in order to be able to
make theoretical contributions.

Target Networks (Mnih et al.,, 2013) are a popular approach to stabilize
Temporal Difference learning. A periodically updated copy, $Q_{\bar{w}}$, of
$Q_{w}$ is used to estimate the next state value. This causes the regression
targets to no longer directly depend on the most recent estimate of $w$. With
this, the Mean Squared Bellman Error for a given state transition is

$\ell^{\text{TN}}=\|R+\gamma P^{\pi}Q_{\bar{w}}-Q_{w}\|^{2}_{D}.$ (4)

The semi-gradient (Sutton and Barto,, 2018) of the expected squared Bellman
error with a TN can be decomposed as (see proof in Appendix A)

$\displaystyle\nabla_{w}\ell^{\text{TN}}(w)=\underbrace{-\Phi^{\top}D(R+\gamma
P^{\pi}\Phi w-\Phi w)}_{\text{TD}(0)}+$ $\displaystyle\underbrace{{\gamma\
\Phi^{\top}DP^{\pi}\Phi(w-\bar{w})}}_{``Regularizer"}.$ (5)

Written in this form, the effects of using TNs become clearer. The first term
is the usual TD(0) update that we will not attempt to modify in this paper,
and the second term can be interpreted as a “regularization” term that
encourages the weights $w$ to stay close to the frozen weights $\bar{w}$. This
is in line with the intuition that TNs “slow down” or “stabilize” the
optimization. However, this “regularizer” suffers from two main issues.

  * •

The first one is the weighting of the regularization which is equal to the
discount factor $\gamma$. This may be problematic as $\gamma$ controls the
agent’s effective horizon (Sutton and Barto,, 2018) and is part of the problem
definition. Therefore TNs are inflexible in the sense that the weight of the
regularizer cannot be controlled independently from the agent’s effective
horizon, and can only be controlled through the target update period $T$. We
show experimentally in Section 4.2 that the update period $T$ can be
ineffective at controlling the strength of the regularization.

  * •

The second and most important point is that the “regularization” is not a
proper regularization term. It may be interpreted as the gradient of a
quadratic when $\Phi^{\top}DP^{\pi}\Phi$ is symmetric and positive, which is
not the case in general. The underlying issue is that if
$\Phi^{\top}DP^{\pi}\Phi$ has a negative eigenvalue, the “regularizer” will
actually push $w$ away from $\bar{w}$ instead of bringing them closer and thus
will render the whole optimization unstable. This is an important theoretical
issue as usually a basic requirement for a regularizer is that it cannot cause
the original method to diverge. It is verified in Section 4.1 that TN can
create additional divergence zones that were not present in TD(0).

Both aforementioned issues can be resolved simply. For the first point, we
replace $\gamma$ by a separate hyper-parameter $\kappa\geq 0$. As for the
second point, changing $\Phi^{\top}DP^{\pi}\Phi$ to $\Phi^{\top}D\Phi$ ensures
that the second term is a proper quadratic regularizer that cannot destabilize
the optimization (Tihonov,, 1963; Tikhonov,, 1943; Lyapunov,, 1992).

###  3.2 Introducing Functional Regularization

Following the reasoning developed in the previous subsection, we would like to
design a loss $\ell$ whose semi-gradient is

$\displaystyle\nabla_{w}\ell(w)={\Phi^{\top}D(R+\gamma P^{\pi}\Phi w-\Phi
w)}+$ $\displaystyle{\kappa\ {\Phi^{\top}D\Phi}(w-\bar{w})}.$ (6)

The term $\kappa\ {\Phi^{\top}D\Phi}(w-\bar{w})$ is the gradient of the
quadratic form

$\frac{\kappa}{2}(w-\bar{w})^{\top}{\Phi^{\top}D\Phi}(w-\bar{w})=\frac{\kappa}{2}\|Q_{w}-Q_{\bar{w}}\|_{D}^{2}$

as $Q_{w}=\Phi w$. We see that the natural resulting regularizer is a
Functional Regularizer in norm $\|\cdot\|_{D}$, the usual norm when studying
the convergence of TD in RL (Bertsekas and Tsitsiklis,, 1996). This leads to
the _Functionally regularized_ Mean Square Bellman Error which penalizes the
norm between the current Q-value estimate $Q_{w}({\mathbf{s}},{\mathbf{a}})$
and a lagging version of it $Q_{\bar{w}}({\mathbf{s}},{\mathbf{a}})$, giving
us

$\ell^{\text{FR}}(w)=\frac{1}{2}\|R+\gamma
P^{\pi}Q_{w}-Q_{w}\|_{D}^{2}+\frac{\kappa}{2}\|Q_{w}-Q_{\bar{w}}\|_{D}^{2}$
(7)

We observe that the up-to-date parameter $w$ is used in the Squared Bellman
Error and there is the additional decoupled FR loss to stabilize $w$ by
regularizing the $Q$ function. $\kappa\geq 0$ is the regularization parameter
and we recover TD learning for $\kappa=0$.

Critically, unlike Equation 4, the target $Q$-value estimates are supplied by
the up-to-date $Q$-network, with the explicit regularization now separately
serving to stabilize training. As with a TN, we can update the lagging network
periodically to control the stability of the $Q$-value estimates. Overall,
$\ell^{\text{FR}}$ is arguably similar in complexity to $\ell^{\text{TN}}$,
requiring only an additional function evaluation for
$Q_{w}({\mathbf{s}}_{t+1},{\mathbf{a}}_{t+1})$ and an additional hyper-
parameter, $\kappa$.

###  3.3 Stability of Target Network regularization and Functional
Regularization

Now that we have highlighted potential issues that could arise when using TNs
and proposed an alternative objective function, we will show that indeed TN
can _unstabilize_ Temporal Difference learning while FR, under some
conditions, does not.

######  Theorem 3.1 (Target Networks can unstabilize TD).

Using TD(0) with Target Networks ( Equation 4) can diverge while using TD(0)
only would converge.

A simple example of this situation is exhibited in Section 4.1.

Note that in Section B.2 we characterize precisely the domain of convergence
of TD(0) with TN for large $T$ and show that it changes the convergence domain
of TD(0), leading to the theorem above.

On the other hand, for FR, we have

######  Proposition 3.2 (Convergence of Temporal Difference with Functional
Regularization).

If $\Phi,D,P^{\pi}$ are chosen so that TD(0) converges, then for $\kappa$
small enough, for $T$ large enough, TD(0) with Functional Regularization is
guaranteed to converge.

###### Proof.

The proof can be found in Section B.3. ∎

The results above highlight the intuition of the last subsections: while TNs
can slow down learning they also interfere with TD learning, changing its
convergence domain. On the other hand, FR with appropriately chosen parameters
does not impact convergence while still being able to regularize the
algorithm.

Finally, note here that the results above do not mean that using TD(0) with FR
is always more stable than using it with TN. When TD(0) is already unstable,
depending on the interplay between the features, the off-policy distribution
and the transition matrix it would be possible in some cases for TNs to make
the iteration stable. However this is unlikely and show that it is impossible
when the features are low dimensional (see Corollary B.4).

$s_{0}$$s_{1}$$0.05$$0.05$$0.95$$0.95$ (a) 2-state MDP

(b) TD(0)

(c) TN

(d) FR

Figure 1: 2-state MDP. We show here the spectral radius for TD(0) (b) only,
(c) with Target Network, and (d) with Functional Regularization on the simple
MDP (a). For any point in the disk, its radius represents the off-policy
distribution of $s_{0}$ while the angle is the same as the vector
$[\phi(s_{0}),\phi(s_{1})]$. The color represents the value of the spectral
radius for each method while the contour is the frontier $\rho=1$ separating
the convergence domain (shades of blue) from the divergent domain (shades of
red). The black circle has a radius $\pi(s_{0})$, the stationary distribution
of $P$ for which TD is guaranteed to converge as it would be on-policy.

##  4 Experiments

In this section, we investigate empirically the differences between FR and TN.
For this, we perform three different experiments. With the first experiment,
we aim at understanding the convergent and divergent behaviors of both
algorithms. We use a novel visualization to give intuition and validate our
theoretical results. The second experiment analyzes the stability and
performance of TN and FR with respect to the regularization strength for
varying degrees of off-policiness. Finally, we demonstrate that replacing TN
with FR improves performance for popular algorithms on the Atari benchmark
(Bellemare et al.,, 2013).

###  4.1 Simple 2-state MDP - Off Policy Evaluation

####  4.1.1 Experimental Set-Up

In this subsection, we visualize the behavior of TN and FR on a simple MDP.
This illustrates the theory developed in Section 3 on the convergence
properties of both algorithms. Baird, (1995); Tsitsiklis and Van Roy, (1996)
and Kolter, (2011) introduced simple reward-less MDPs with few states on which
TD(0) can exhibit divergence. Similarly, we define a 2-state MDP in Figure
1(a), which is conceptually close to Tsitsiklis and Van Roy, (1996). Each
state transitions to the other with probability $0.95$ or transitions to
itself with probability $0.05$. We use 1-d features for these two states:
$\phi(s_{0})$ and $\phi(s_{1})$. We denote the off-sampling distribution of
$s_{0}$ by $d(s_{0})$ and by $\pi(s_{0})$ the on-policy sampling distribution
of $s_{0}$ which is equal to $1/2$ in this specific case. We use
$\gamma=0.995$.

Instead of just exhibiting a single instance $D,\Phi$ for which we have
divergence, we showcase the convergent or divergent behavior of TD(0), TD(0)
with TN and TD(0) with FR _for all combinations_ of $D$ and $\Phi$
simultaneously. The Euclidean norm of $\Phi$, $\|\Phi\|_{2}$ does not impact
the convergence of any of the aforementioned algorithms as $\Phi$ can be
renormalized if we scale the learning rate $\eta$ by its squared norm.
Therefore, only the angle of the vector $\Phi=[\phi(s_{0}),\phi(s_{1})]$ is
needed to describe all representations. In our context, there are only two
states, and thus, the off-policy distribution is entirely determined by
$d(s_{0})$. Thus, quite naturally, one can represent the set of all
representations and all off-policy distributions $(D,\Phi)$ as a disk or
radius $1$ 111Note that we technically only need a half-disk to illustrate the
convergence behavior, but we plot the whole disk for aesthetic reasons.. In
polar coordinates, the radius of a point on the disk represents $d(s_{0})$
while its angle is the one of the vector $\Phi$, i.e.,
$\varphi(\Phi)=\arctan\tfrac{\phi(s_{1})}{\phi(s_{0})}$.

(a) Effect of $\epsilon$ on the average regret.

(b) Effect of $\epsilon$ on $Q$-value error.

(c) Effect of $T$ on regret for $\epsilon=0.5$.

(d) Effect of $T$ on error for $\epsilon=0.5$.

(e) Effect of $T$ on regret for $\epsilon=0.95$.

(f) Effect of $T$ on error for $\epsilon=0.95$.

Figure 2:  Four Rooms Comparison. On the top row (2(a), 2(c) and 2(e)) we draw
the regret per episode for TN and FR for varying $\kappa$’s. On the bottom row
(2(b), 2(d) and 2(f)) we plot the distribution of errors on the $Q$-value for
the same set of algorithms. Each of the three columns represents one
experimental setting. In the first column, we vary the degree of “off-
policiness” (via $\epsilon$) and report the best-performing algorithms. In the
last two columns, we fix $\epsilon$ and show the impact of the target update
period $T$ and the behavior policy exploration noise $\epsilon$ on performance
and $Q$-error.

####  4.1.2 Results

We draw the above-mentioned disks for the algorithms: TD(0), TD(0) with TN,
and TD(0) with FR (Figure 1(b), 1(c), and 1(d)). On these disks, the colors
represent the spectral radius $\rho$ of the iteration matrix for each
algorithm. Recall that $\rho<1$ (blue) implies convergence, while $\rho>1$
(red) implies divergence to $+\infty$. We plot the contour lines $\rho=1$ to
ease visualization. Additionally, we draw the circle of radius
$d(s_{0})=\pi(s_{0})$ (in black), which denotes the stationary distribution.
As predicted by theory, TD(0) converges on this circle for all
representations. We use the regularization coefficient $\kappa=\gamma=0.995$
and target update period $T=10,000$ for TD(0) with TN and TD(0) with FR.

As seen in Figure 1, FR (Figure 1(d)) and TN (Figure 1(c)) show less extreme
values (lighter blue) compared to TD(0) (Figure 1(b)). This finding implies
that both the convergence and divergence are slowed down, which is expected
for regularization methods.

We recover the classical divergence example for TD(0) (Tsitsiklis and Van
Roy,, 1996; Van Hasselt et al.,, 2018): if $\phi(s_{1})>\phi(s_{0})>0$ and the
behavior distribution $d(s_{0})$ is close to 1, the point
($d(s_{0}),\varphi(\Phi)$) in polar coordinates lies in the large upper red
region of Figure 1(b), thus TD(0) will diverge.

As proved in Proposition 3.2, the convergence domain of TD(0) with FR is
similar to the one of TD(0). Interestingly, and as shown in Theorem 3.1, TD(0)
with TN may diverge in regions where TD(0) with FR does not. For example, in
Figure 1(c) we see four smaller (symmetric) additional divergence regions
(red) in the lower right and upper left regions of the disk for $d(s_{0})$
close to $1$ and two symmetric ones near the center of the disk. This can
happen when $\Phi^{\top}DP^{\pi}\Phi$ which appears in the implicit
regularization of TN has negative eigenvalues.

These depictions of the convergence or divergence behaviors of TD(0) with FR
and TD(0) with TN hint at the fact that TN-based algorithms may be more
unstable than FR-based algorithms for strongly off-policy distributions. This
hypothesis is studied empirically in the next subsection. We provide more
figures in Section C.1 where we also discuss the impact of the discount factor
$\gamma$.

###  4.2 Four Rooms

####  4.2.1 Experimental Set-Up

In this section, we investigate the impact of changing the regularization
strength and the off-policy distribution for both TN and FR. These experiments
are run in the Four Rooms environment (Sutton et al.,, 1999) (Figure 6 in
Appendix) which is comprised of four rooms divided by walls with a single gap
in each wall allowing an agent to move between rooms. The environment size is
11 $\times$ 11\. The agent’s position is given by a one-hot encoding. The
agent’s available actions are up, down, left, and right. The agent starts in
the bottom right position and must reach the goal in the top left position.
The rationale for using this environment is that it allows us to compute the
true Q values, which can then be compared with the ones learned by our
Q-function approximator, a DNN composed of 2 hidden layers (details in Table
2).

To study the behavior of TN and FR under different off-policy data
collections, the data is collected under a behavior policy that takes a random
action with probability $\epsilon$ and takes
${\mathbf{a}}=\operatorname*{arg\,max}_{\mathbf{a}}Q_{w}({\mathbf{s}},{\mathbf{a}})$
with probability $1-\epsilon$. As $\epsilon$ tends towards 1, the data
collection becomes more off-policy and makes the $Q$-value estimation more
difficult.

During training we measure
$\max_{{\mathbf{s}},{\mathbf{a}}}\|Q_{w}({\mathbf{s}},{\mathbf{a}})-Q^{\pi}({\mathbf{s}},{\mathbf{a}})\|^{2}_{2}$,
where $Q^{\pi}$ was obtained in closed form and $\pi$ is the greedy policy. In
Figure 2(b), 2(d), 2(f), the red line indicates an error of $1$, and in our
MDP, all true $Q$-values are between $0$ and $1$. Thus any point above the red
line has $Q$-value estimates outside of this feasible range, indicating soft-
divergence (Van Hasselt et al.,, 2018). We also evaluate the average per-
episode regret for 100 episodes collected under
$\epsilon_{\text{eval}}-$greedy policy with $\epsilon_{\text{eval}}=0.1$ as it
is common for RL agents in deterministic environments such as the Atari suite.

####  4.2.2 Results

#####  Figures 2(a) and 2(b): Best hyper-parameters over all $\epsilon$.

For both methods, we observe a large average regret for smaller $\epsilon$
which is due to less exploration early on. On the other hand, the average
regret is increased for larger $\epsilon$ due to the behavior policy being
more off-policy. Furthermore, we observe that for near-on-policy data
collection, the difference in performance between TN and FR is negligible.
However, for a behavior policy with $\epsilon\geq 0.5$, the difference in
performance increases, and TN performs much worse than FR. While FR, by
itself, does not impact exploration, its increased stability allows us to
learn from more exploratory policies than TN (larger $\epsilon$). To better
understand the additional flexibility provided by $\kappa$, we closely
investigate the behavior policy $\epsilon=0.5$ and $\epsilon=0.95$.

#####  Figures 2(c) and 2(d): Behavior Policy with $\epsilon=0.5$.

In Figure 2(c), we observe that TN’s performance improves as we increase $T$
until it reaches $100$, then the performance degrades. Interestingly, the poor
performances for small and large $T$ are caused by two different reasons. On
the one hand, for $T=10$, we observe a median error slightly above $1$
indicating soft-divergence which results in high regret Figure 2(c). As we
increase $T$ up to $250$, we can see that the median error decreases and that
the outliers are also less extreme. This translates into better average
regrets. On the other hand, as we increase $T$ past $250$ the distribution of
errors is concentrated slightly below $1$, and the average regret is high
again. This can be understood as TN over-regularizing which greatly slows down
training.

The behavior is quite different for FR with $\kappa=0.5$. For $T=10$, the
median error is close to 1 and there are a few outliers that result in a high
average regret. As $T$ increases the median error falls until $T$ reaches 250
where the lowest average regret is achieved. As $T$ increases past 250, the
error and the regret slightly increase hinting that the regularization might
be too strong.

#####  Figures 2(e) and 2(f): Behavior Policy with $\epsilon=0.95$.

In Figure 2(e) for FR $\kappa=2.5$, we observe that the regret decreases as we
increase $T$ up to $500$. This indicates that increasing regularization is
beneficial as can be seen by the reduction in median error in Figure 2(f). For
$T$ larger than $500$, the regret and the median error increase indicating
over-regularization, thus slowing down learning. For $T=10$, TN and FR
$\kappa=2.5$ have similar regret and error, but as we increase $T$, TN’s
regret does not improve. This can be explained by carefully examining Figure
2(f). We can see that the error stays very close to $1$ which indicates over-
regularization, leading to as slow training.

In summary, we have shown that changing the update period $T$ combined with
Target Networks is not a regularizer flexible enough to obtain good
performance. On the other hand, FR can reach higher performance by tuning
$\kappa$ and $T$ jointly as it results in better regularization trade-offs.

###  4.3 Atari

Table 1: Atari Comparisons. We report the average of the last 10 test episodes
on the Atari benchmark and the standard error. See Appendix A, Figures 7, 8,
and 9 for full training curves.

Environment | Beam Rider | Breakout | Enduro | Qbert | Seaquest | Space Invaders
---|---|---|---|---|---|---
Agent |  |  |  |  |  |
TN DQN | 7266 +/- 112 | 320 +/- 6 | 463 +/- 22 | 7321 +/- 412 | 2392 +/- 246 | 1375 +/- 46
FR DQN $\kappa=0.75$ (Ours) | 7939 +/- 138 | 339 +/- 4 | 576 +/- 22 | 10118 +/- 346 | 3387 +/- 334 | 1495 +/- 38
TN Double DQN | 12316 +/- 259 | 310 +/- 7 | 693 +/- 44 | 11890 +/- 277 | 10638 +/- 454 | 2009 +/- 46
FR Double DQN $\kappa=0.75$ (Ours) | 11739 +/- 285 | 383 +/- 3 | 1181 +/- 28 | 12705 +/- 211 | 7124 +/- 2160 | 2692 +/- 120
TN Rainbow | 15398 +/- 816 | 375 +/- 1 | 2307 +/- 7 | 30911 +/- 666 | 18916 +/- 7130 | 9907 +/- 3055
FR Rainbow $\kappa=2.5$ (Ours) | 18216 +/- 757 | 350 +/- 5 | 2302 +/- 8 | 31521 +/- 1115 | 22976 +/- 12546 | 17127 +/- 3117

####  4.3.1 Experimental Set-Up

The Arcade Learning Environment (Bellemare et al.,, 2013) provides a set of
benchmark Atari games for evaluating RL agents. These environments are a
popular benchmark as they possess rich visual observations and diverse reward
functions. We evaluate the impact of using Functional Regularization instead
of Target Networks on several RL algorithms.

As we observed in Section 4.2.2, tuning $T$ and $\kappa$ can result in great
performance gains and we encourage practitioners to perform a sweep over these
two hyper-parameters if possible. However, due to the computational
constraints of the Atari benchmark, we only tuned $\kappa$ and used the same
$T$ as the one used by TN. All results are reported in Table 1.

We used the baselines provided in the DQN Zoo library (Quan and Ostrovski,,
2020) and easily replaced the Target Network loss with Functional
Regularization loss in a few lines of code using Jax (Bradbury et al.,, 2018)
and Haiku (Hennigan et al.,, 2020). For DQN and Double DQN, we tuned $\kappa$
for each FR agent by performing experiments on 2 seeds (only 1 set of global
hyper-parameters was used for every task). Once the best set of hyper-
parameters for each method has been selected, we used 10 additional seeds (and
exclude the 2 initial seeds) to compare the algorithms. All hyper-parameters
we used are displayed in Table 3 in the Appendix. We used the same suite of
representative environments used in Mnih et al., (2013)222excluding Pong for
which all algorithms achieve the same high performance.. Each seed took 48
hours to run on our resources for a total of 14,400 hours of GPU usage.
Additional experimental details can be found in the Appendix.

####  4.3.2 Results

##### Comparison with DQN.

DQN (Mnih et al.,, 2013) was the first RL algorithm to reach human performance
on a subset of the Atari suite. It learns the value function by minimizing the
TN loss as defined in Equation 4. We replace the TN loss by the FR loss
defined in Equation 7. Across all environments, using the FR loss with a
$\kappa=0.75$ significantly improves the performance of the DQN algorithm.
Additionally, Figure 7 in Section C.3 presents the training curves for FR DQN,
TN DQN, and other baselines such as Polyak DQN.

##### Comparison with Double DQN.

Similarly to DQN, Double DQN (Van Hasselt,, 2010) minimizes the TN loss, but
decouples the “action-selection” from the “action-evaluation” to estimate the
next value function countering the maximum bias. Double DQN has been shown to
significantly improves upon DQN on the Atari suite. We observe that replacing
the TN loss with the FR loss significantly improves the performance of Double
DQN on 4 of the 6 Atari games studied. The training curves are provided in
Figure 8.

##### Comparison with Rainbow DQN.

Rainbow DQN (Hessel et al.,, 2018) obtains state-of-the-art results on the
Atari benchmark. Rainbow learn the values by using a very sophisticated
objective. Specifically, they use multi-step returns as a way to trade-off
between bias and variance of the target value. Additionally, they use
distributional DQN (Bellemare et al.,, 2017) which requires to discretize the
Q value, to project the target between -10 and 10, and to minimize the
Wasserstein metric. Furthermore, they use noisy network to improve exploration
(Fortunato et al.,, 2017), prioritized experience replay (Schaul et al.,,
2015), and dueling networks. Overall, Rainbow requires 12 additional hyper-
parameters. For simplicity, we kept all the hyper-parameters constant and
simply tuned $\kappa$ when introducing Functional Regularization. We observe
that replacing TN with FR matches Rainbow on 3 tasks, outperforms it on 2
tasks, and under-performs it on Breakout. See Figure 9 for the training
curves.

In summary, we have shown that the FR loss can be used as a drop-in
replacement for the TN loss across a variety of RL algorithms - even by
keeping all hyper-parameters fixed. We observed that using the FR loss instead
of the TN loss drastically improves the performances of DQN and Double DQN,
but that its effectiveness decreases as it is combined with more sophisticated
methods, i.e. Rainbow DQN.

##  5 Related work

Multiple previous works have investigated how to improve value estimation
through various constraints and regularizations. Shao et al., (2020) proposed
adding an additional backward Squared Bellman Error loss to the next $Q$-value
to stabilize training and remove the need for a target network on some control
problems. Farahmand et al., (2009) is perhaps the closest work to our own,
they regularize the $L_{2}$ norm of the $Q$-value estimates, i.e., penalizing
$\kappa||Q_{w}||^{2}$. However, penalizing the magnitude of the $Q$-values
would prevent the algorithm from converging to $Q^{*}$ if $\kappa$ does not
tend towards $0$. Penalizing the output of a DNN draws connections with
popular regularization methods in the field of policy optimization which were
inspired by trust-region algorithms (Schulman et al., 2015a, ; Abdolmaleki et
al., 2018b, ; Abdolmaleki et al., 2018a, ) in which the policy is KL
regularized towards its past values. In the same spirit, for value-based
methods, our proposed Functional Regularization regularizes the $Q$ function
estimates towards their past values. Alternatively, Kim et al., (2019) showed
that by using the mellow max operator as an alternative to the max operator
used in bootstrapping, it was possible to stabilize training and train without
a target network on some Atari games.

Other works have sought to stabilize the $Q$-value estimates by constraining
parameter updates, e.g., through regularization (Farebrother et al.,, 2018),
conjugate gradient methods (Schulman et al., 2015b, ), pre-conditioning the
gradient updates (Knight and Lerner,, 2018; Achiam et al.,, 2019), or using
Kalman filtering (Shashua and Mannor,, 2019, 2020). However, weight
regularization might be ineffective in DNNs. For neural networks, the network
outputs depend on the weights in a complex way and the exact value of the
weights may not matter much. What ultimately matters is the network outputs
(Benjamin et al.,, 2018; Khan et al.,, 2019), and it is better to directly
regularize those. For instance, while Polyak’s averaging (Lillicrap et al.,,
2015), a common weight regularization technique, has found success in control
problems (Haarnoja et al.,, 2018; Fujimoto et al.,, 2018), periodically
updating the parameters is usually preferred for complex DNN architectures
(Mnih et al.,, 2013; Hausknecht and Stone,, 2015; Hessel et al.,, 2018;
Kapturowski et al.,, 2018; Parisotto et al.,, 2020).

Finally, neither FR nor TN have convergence guarantees for all representations
and off-policy distributions when using bootstrapping: they still suffer from
the deadly triad (Sutton,, 1995; Tsitsiklis and Van Roy,, 1997; Sutton and
Barto,, 2018) as shown in Section 3. Several works have proposed algorithms
with stronger convergence guarantees such as gradient TD methods (Sutton et
al.,, 2008, 2009), TDC (Maei et al.,, 2009) or Emphatic weights (Sutton et
al.,, 2016). However, these methods are often computationally significantly
more expensive or haven’t been shown to scale favorably with DNNs. Recently
(Zhang et al.,, 2021) studied how Target Networks can help stabilize the TD
algorithm, which is seemingly at odds with our Theorem 3.1. However, in their
paper, they study a variant of DQN with TN which involves projection steps
while our analysis focuses on the version used in practice.

##  6 Conclusion

In this paper, we cast a light on the implicit regularization performed by
using Target Networks in RL. We have shown that despite being used as a
regularizer Target Networks can cause instabilities while also being
inflexible as the regularization depends on the discount factor $\gamma$. To
overcome these issues, we introduced Functional Regularization which directly
regularizes the value network towards a network parameterized by lagging
parameters.

We demonstrated empirically in a 2-state MDP that using Target Networks is a
poor regularizer and can unstabilize TD for off-policy data. In opposition,
Functional Regularization does not suffer from these issues and effectively
slows down the optimization.

Furthermore, in the Four Rooms domain, we show that changing the update period
$T$ is not enough to have a flexible regularizer for Target Networks. On the
other hand, for Functional Regularization, by controlling the regularization
scaling parameter $\kappa$, we can obtain better regularization trade-offs
than by varying $T$ only. This is further exacerbated when the “off-
policiness” is high.

Finally, we have shown that Functional Regularization can be used as a drop-in
replacement for Target Networks on 3 popular RL algorithms resulting in
matching or outperforming Target Networks for most of the scenarios studied.

## References

  * (1) Abdolmaleki, A., Springenberg, J. T., Degrave, J., Bohez, S., Tassa, Y., Belov, D., Heess, N., and Riedmiller, M. (2018a).  Relative entropy regularized policy iteration.  arXiv preprint arXiv:1812.02256.
  * (2) Abdolmaleki, A., Springenberg, J. T., Tassa, Y., Munos, R., Heess, N., and Riedmiller, M. (2018b).  Maximum a posteriori policy optimisation.  arXiv preprint arXiv:1806.06920.
  * Achiam et al., (2019) Achiam, J., Knight, E., and Abbeel, P. (2019).  Towards characterizing divergence in deep q-learning.  arXiv preprint arXiv:1903.08894.
  * Baird, (1995) Baird, L. (1995).  Residual algorithms: Reinforcement learning with function approximation.  In Machine Learning Proceedings 1995, pages 30–37. Elsevier.
  * Bellemare et al., (2017) Bellemare, M. G., Dabney, W., and Munos, R. (2017).  A distributional perspective on reinforcement learning.  In International Conference on Machine Learning, pages 449–458. PMLR.
  * Bellemare et al., (2013) Bellemare, M. G., Naddaf, Y., Veness, J., and Bowling, M. (2013).  The arcade learning environment: An evaluation platform for general agents.  Journal of Artificial Intelligence Research, 47:253–279.
  * Bellman, (1966) Bellman, R. (1966).  Dynamic programming.  Science, 153(3731):34–37.
  * Benjamin et al., (2018) Benjamin, A. S., Rolnick, D., and Kording, K. (2018).  Measuring and regularizing networks in function space.  arXiv preprint arXiv:1805.08289.
  * Bertsekas and Tsitsiklis, (1996) Bertsekas, D. P. and Tsitsiklis, J. N. (1996).  Neuro-dynamic programming.  Athena Scientific.
  * Bradbury et al., (2018) Bradbury, J., Frostig, R., Hawkins, P., Johnson, M. J., Leary, C., Maclaurin, D., Necula, G., Paszke, A., VanderPlas, J., Wanderman-Milne, S., and Zhang, Q. (2018).  JAX: composable transformations of Python+NumPy programs.
  * Farahmand et al., (2009) Farahmand, A. M., Ghavamzadeh, M., Szepesvári, C., and Mannor, S. (2009).  Regularized fitted q-iteration for planning in continuous-space markovian decision problems.  In 2009 American Control Conference, pages 725–730. IEEE.
  * Farebrother et al., (2018) Farebrother, J., Machado, M. C., and Bowling, M. (2018).  Generalization and regularization in dqn.  arXiv preprint arXiv:1810.00123.
  * Fortunato et al., (2017) Fortunato, M., Azar, M. G., Piot, B., Menick, J., Osband, I., Graves, A., Mnih, V., Munos, R., Hassabis, D., Pietquin, O., et al. (2017).  Noisy networks for exploration.  arXiv preprint arXiv:1706.10295.
  * Fujimoto et al., (2018) Fujimoto, S., Hoof, H., and Meger, D. (2018).  Addressing function approximation error in actor-critic methods.  In International Conference on Machine Learning, pages 1587–1596. PMLR.
  * Haarnoja et al., (2018) Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S. (2018).  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor.  In International Conference on Machine Learning, pages 1861–1870. PMLR.
  * Hausknecht and Stone, (2015) Hausknecht, M. and Stone, P. (2015).  Deep recurrent q-learning for partially observable mdps.  arXiv preprint arXiv:1507.06527.
  * Hennigan et al., (2020) Hennigan, T., Cai, T., Norman, T., and Babuschkin, I. (2020).  Haiku: Sonnet for JAX.
  * Hessel et al., (2018) Hessel, M., Modayil, J., Van Hasselt, H., Schaul, T., Ostrovski, G., Dabney, W., Horgan, D., Piot, B., Azar, M., and Silver, D. (2018).  Rainbow: Combining improvements in deep reinforcement learning.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32.
  * Kapturowski et al., (2018) Kapturowski, S., Ostrovski, G., Quan, J., Munos, R., and Dabney, W. (2018).  Recurrent experience replay in distributed reinforcement learning.  In International conference on learning representations.
  * Khan et al., (2019) Khan, M. E. E., Immer, A., Abedi, E., and Korzepa, M. (2019).  Approximate inference turns deep networks into gaussian processes.  In Advances in neural information processing systems, pages 3094–3104.
  * Kim et al., (2019) Kim, S., Asadi, K., Littman, M., and Konidaris, G. (2019).  Deepmellow: removing the need for a target network in deep q-learning.  In Proceedings of the Twenty Eighth International Joint Conference on Artificial Intelligence.
  * Kingma and Ba, (2014) Kingma, D. P. and Ba, J. (2014).  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980.
  * Knight and Lerner, (2018) Knight, E. and Lerner, O. (2018).  Natural gradient deep q-learning.  arXiv preprint arXiv:1803.07482.
  * Kolter, (2011) Kolter, J. (2011).  The fixed points of off-policy td.  Advances in Neural Information Processing Systems, 24:2169–2177.
  * Lillicrap et al., (2015) Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. (2015).  Continuous control with deep reinforcement learning.  arXiv preprint arXiv:1509.02971.
  * Lyapunov, (1992) Lyapunov, A. M. (1992).  The general problem of the stability of motion.  International journal of control, 55(3):531–534.
  * Maei et al., (2009) Maei, H. R., Szepesvari, C., Bhatnagar, S., Precup, D., Silver, D., and Sutton, R. S. (2009).  Convergent temporal-difference learning with arbitrary smooth function approximation.  In NIPS, pages 1204–1212.
  * Mnih et al., (2013) Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M. (2013).  Playing atari with deep reinforcement learning.  arXiv preprint arXiv:1312.5602.
  * Parisotto et al., (2020) Parisotto, E., Song, F., Rae, J., Pascanu, R., Gulcehre, C., Jayakumar, S., Jaderberg, M., Kaufman, R. L., Clark, A., Noury, S., et al. (2020).  Stabilizing transformers for reinforcement learning.  In International Conference on Machine Learning, pages 7487–7498. PMLR.
  * Puterman, (2014) Puterman, M. L. (2014).  Markov decision processes: discrete stochastic dynamic programming.  John Wiley & Sons.
  * Quan and Ostrovski, (2020) Quan, J. and Ostrovski, G. (2020).  DQN Zoo: Reference implementations of DQN-based agents.
  * Schaul et al., (2015) Schaul, T., Quan, J., Antonoglou, I., and Silver, D. (2015).  Prioritized experience replay.  arXiv preprint arXiv:1511.05952.
  * (33) Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. (2015a).  Trust region policy optimization.  In International conference on machine learning, pages 1889–1897. PMLR.
  * (34) Schulman, J., Moritz, P., Levine, S., Jordan, M., and Abbeel, P. (2015b).  High-dimensional continuous control using generalized advantage estimation.  arXiv preprint arXiv:1506.02438.
  * Shao et al., (2020) Shao, L., You, Y., Yan, M., Sun, Q., and Bohg, J. (2020).  Grac: Self-guided and self-regularized actor-critic.  arXiv preprint arXiv:2009.08973.
  * Shashua and Mannor, (2019) Shashua, S. D.-C. and Mannor, S. (2019).  Trust region value optimization using kalman filtering.  arXiv preprint arXiv:1901.07860.
  * Shashua and Mannor, (2020) Shashua, S. D.-C. and Mannor, S. (2020).  Kalman meets bellman: Improving policy evaluation through value tracking.  arXiv preprint arXiv:2002.07171.
  * Sutton, (1988) Sutton, R. S. (1988).  Learning to predict by the methods of temporal differences.  Machine learning, 3(1):9–44.
  * Sutton, (1995) Sutton, R. S. (1995).  On the virtues of linear learning and trajectory distributions.  In Proceedings of the Workshop on Value Function Approximation, Machine Learning Conference, page 85.
  * Sutton and Barto, (2018) Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * Sutton et al., (2009) Sutton, R. S., Maei, H. R., Precup, D., Bhatnagar, S., Silver, D., Szepesvári, C., and Wiewiora, E. (2009).  Fast gradient-descent methods for temporal-difference learning with linear function approximation.  In Proceedings of the 26th Annual International Conference on Machine Learning, pages 993–1000.
  * Sutton et al., (2016) Sutton, R. S., Mahmood, A. R., and White, M. (2016).  An emphatic approach to the problem of off-policy temporal-difference learning.  The Journal of Machine Learning Research, 17(1):2603–2631.
  * Sutton et al., (1999) Sutton, R. S., Precup, D., and Singh, S. (1999).  Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning.  Artificial intelligence, 112(1-2):181–211.
  * Sutton et al., (2008) Sutton, R. S., Szepesvári, C., and Maei, H. R. (2008).  A convergent o (n) algorithm for off-policy temporal-difference learning with linear function approximation.  Advances in neural information processing systems, 21(21):1609–1616.
  * Tihonov, (1963) Tihonov, A. N. (1963).  Solution of incorrectly formulated problems and the regularization method.  Soviet Math., 4:1035–1038.
  * Tikhonov, (1943) Tikhonov, A. N. (1943).  On the stability of inverse problems.  In Dokl. Akad. Nauk SSSR, volume 39, pages 195–198.
  * Tsitsiklis and Van Roy, (1996) Tsitsiklis, J. N. and Van Roy, B. (1996).  Feature-based methods for large scale dynamic programming.  Machine Learning, 22(1):59–94.
  * Tsitsiklis and Van Roy, (1997) Tsitsiklis, J. N. and Van Roy, B. (1997).  Analysis of temporal-diffference learning with function approximation.  In Advances in neural information processing systems, pages 1075–1081.
  * Van Hasselt, (2010) Van Hasselt, H. (2010).  Double q-learning.  Advances in neural information processing systems, 23:2613–2621.
  * Van Hasselt et al., (2018) Van Hasselt, H., Doron, Y., Strub, F., Hessel, M., Sonnerat, N., and Modayil, J. (2018).  Deep reinforcement learning and the deadly triad.  arXiv preprint arXiv:1812.02648.
  * Van Hasselt et al., (2016) Van Hasselt, H., Guez, A., and Silver, D. (2016).  Deep reinforcement learning with double q-learning.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30.
  * Zhang et al., (2021) Zhang, S., Yao, H., and Whiteson, S. (2021).  Breaking the deadly triad with a target network.  In International Conference on Machine Learning, pages 12621–12631. PMLR.

##  Appendix A Appendix

###  A.1 $Q$-learning with Target Network

Letting $R^{(t)}\equiv R({\mathbf{s}}_{t},{\mathbf{a}}_{t})$, $Q^{(t)}\equiv
Q({\mathbf{s}}_{t},{\mathbf{a}}_{t})$ and $\Delta
Q^{(t)}_{\bar{w}}\equiv\mathbb{E}[Q_{\bar{w}}^{(t+1)}-Q_{\bar{w}}^{(t)}|{\mathbf{s}}_{t},{\mathbf{a}}_{t}]=\mathbb{E}[Q_{\bar{w}}^{(t+1)}|{\mathbf{s}}_{t},{\mathbf{a}}_{t}]-Q_{\bar{w}}^{(t)}$

$\displaystyle\nabla_{w}l^{\text{target}}(w)$
$\displaystyle=-\big{(}R^{(t)}+\gamma\mathbb{E}_{P,\pi}[Q_{\bar{w}}^{(t+1)}]-Q_{w}^{(t)}\big{)}\nabla_{w}Q_{w}^{(t)}$
$\displaystyle=-\big{(}R^{(t)}+\gamma(Q_{\bar{w}}^{(t)}+\Delta
Q^{(t)}_{\bar{w}})-Q_{w}^{(t)}\big{)}\nabla_{w}Q_{w}^{(t)}$
$\displaystyle=-\big{(}R^{(t)}+\gamma(Q_{\bar{w}}^{(t)}+\Delta
Q^{(t)}_{\bar{w}})-(1-\gamma+\gamma)Q_{w}^{(t)}\big{)}\nabla_{w}Q_{w}^{(t)}$
$\displaystyle=-\big{(}R^{(t)}+\gamma Q_{\bar{w}}^{(t)}+\gamma\Delta
Q^{(t)}_{\bar{w}}-(1-\gamma)Q_{w}^{(t)}-\gamma
Q_{w}^{(t)}\big{)}\nabla_{w}Q_{w}^{(t)}$
$\displaystyle=-\big{(}R^{(t)}+\gamma\Delta
Q^{(t)}_{\bar{w}}-(1-\gamma)Q_{w}^{(t)}\big{)}\nabla_{w}Q_{w}^{(t)}+\gamma\big{(}Q_{\bar{w}}^{(t)}-Q_{w}^{t}\big{)}\nabla_{w}Q_{w}^{(t)}$
$\displaystyle=-\big{(}R^{(t)}+\gamma\Delta
Q^{(t)}_{\bar{w}}-Q_{w}^{(t)}+\gamma
Q_{w}^{(t)}\big{)}\nabla_{w}Q_{w}^{(t)}+\gamma\big{(}Q_{\bar{w}}^{(t)}-Q_{w}^{(t)}\big{)}\nabla_{w}Q_{w}^{(t)}$
$\displaystyle=-\big{(}R^{(t)}+\gamma(Q_{w}^{(t)}+{\hbox
to0.0pt{\leavevmode\hbox{\set@color$\Delta
Q^{(t)}_{\bar{w}}$}\hss}\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\rule[-2.72531pt]{22.6167pt}{0.5pt}})-Q_{w}^{(t)}\big{)}\nabla_{w}Q_{w}^{(t)}+{\hbox
to0.0pt{\leavevmode\hbox{\set@color$\gamma$}\hss}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\rule[-2.33331pt]{5.1773pt}{0.5pt}}\big{(}Q_{\bar{w}}^{(t)}-Q_{w}^{(t)}\big{)}\nabla_{w}Q_{w}^{(t)}$

###  A.2 $Q$-learning with Functional Regularization

$\displaystyle\nabla_{w}l^{\text{FR}}(w)$
$\displaystyle=-\big{(}R^{(t)}+\gamma\mathbb{E}_{P,\pi}[Q_{w}^{(t+1)}]-Q_{w}^{(t)}\big{)}\nabla_{w}Q_{w}^{(t)}+\kappa\big{(}Q_{\bar{w}}^{t}-Q_{w}^{(t)}\big{)}\nabla
Q_{w}^{(t)}$ $\displaystyle=-\big{(}R^{(t)}+\gamma(Q_{\theta}^{(t)}+{\hbox
to0.0pt{\leavevmode\hbox{\set@color$\Delta
Q^{(t)}_{\theta}$}\hss}\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\rule[-2.33331pt]{22.6167pt}{0.5pt}})-Q_{w}^{(t)}\big{)}\nabla_{w}Q_{w}^{(t)}+{\hbox
to0.0pt{\leavevmode\hbox{\set@color$\kappa$}\hss}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\rule[0.0pt]{5.76158pt}{0.5pt}}\big{(}Q_{\bar{w}}^{(t)}-Q_{w}^{t}\big{)}\nabla
Q_{w}^{(t)}$

###  A.3 Polyak Averaging

To better understand the implicit regularization perform by Polyak averaging,
let us consider a situation in which after each gradient step (indexed by
$i$), we identified the target network as the solution to the problem:

$\bar{w}_{i+1}=\min_{\bar{w}}\frac{1}{2}\|\bar{w}-w\|^{2}+\frac{1-\tau}{2\tau}\|\bar{w}-\bar{w}_{i}\|^{2}$
(8)

whereby $w$ is the latest set of weights of the $Q$-network and $\bar{w}_{i}$
is the previous instance of the target network, and $\tau$ is the exponential
averaging step size. Minimizing $\bar{w}$ is obtained by computing the
gradient of the problem and equating it $0$, leading to
$\bar{w}_{i+1}=(1-\tau)w+\tau\bar{w}$, which is exactly Polyak’s updating.
This derivation illustrates that Polyak’s update is indeed a form of weight
regularization with respect to the most recent target network weights.

##  Appendix B Proofs for Linear Function Approximation case

###  B.1 Supporting lemma

######  Lemma B.1 (Difference of inverses).

For $A$ and $B$ two non-singular matrices

$A^{-1}-B^{-1}=A^{-1}(B-A)B^{-1}$

###### Proof.

We multiply each side by $A$ on the left and $B$ on the right and show they
are equal. Left hand term:

$\displaystyle A(A^{-1}-B^{-1})B=B-A$

And for the right hand term:

$\displaystyle AA^{-1}(B-A)B^{-1}B=B-A$

By equating both terms and multiplying by $A^{-1}$ on the left and $B^{-1}$ on
the right we have the equality.

∎

######  Proposition B.2 (Convergence of TD-TN).

For $\Pi_{\Phi}=\Phi(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}D$, the projection
matrix onto the span of $\Phi$, if $\rho(\Pi_{\Phi}P^{\pi})<\frac{1}{\gamma}$
then for $T$ large enough, Target Network Value Iteration is guaranteed to
converge.

###  B.2 Proof for the domain of convergence of TD(0) with TN

The solution for the TD iteration is

$\boxed{w^{\ast}=(\Phi D(I-\gamma P^{\pi})\Phi)^{-1}\Phi^{\top}DR}$ (9)

####  B.2.1 Regularized iteration

Let us call $\bar{w}$ the frozen weight. We consider in this subsection only
the ”inner loop iteration”, i.e the ones for a fixed frozen weight vector. The
update for TD with target network is

$\displaystyle w_{t+1}=w_{t}+\eta\Phi^{\top}D(R+\gamma P^{\pi}\Phi\bar{w}-\Phi
w_{t})$

We call $w^{\ast}(\bar{w})$ the fixed point of that iteration rule which
satisfies

$\boxed{w^{\ast}(\bar{w})=(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}D(R+\gamma
P^{\pi}\Phi\bar{w})}$ (10)

Thus our updates satisfy

$\displaystyle w_{t+1}-w^{\ast}(\bar{w})$
$\displaystyle=w_{t}+\eta\Phi^{\top}D(R+\gamma P^{\pi}\Phi\bar{w}-\Phi
w_{t})-w^{\ast}(\bar{w})$
$\displaystyle=(I-\eta\Phi^{\top}D\Phi)w_{t}+\eta\Phi^{\top}D(R+\gamma
P^{\pi}\Phi\bar{w})-w^{\ast}(\bar{w})$
$\displaystyle=(I-\eta\Phi^{\top}D\Phi)w_{t}+\eta\Phi^{\top}D\Phi
w^{\ast}(\bar{w})-w^{\ast}(\bar{w}),\text{using \ref{eq:fixed_point_target}}$
$\displaystyle=(I-\eta\Phi^{\top}D\Phi)(w_{t}-w^{\ast}(\bar{w}))$

So

$\boxed{w_{t}-w^{\ast}(\bar{w})=(I-\eta\Phi^{\top}D\Phi)^{t}(w_{0}-w^{\ast}(\bar{w}))}$
(11)

As $\Phi^{\top}D\Phi$ is symmetric real with positive eigenvalues,
$\eta\leq\frac{2}{\lambda_{1}}$ with $\lambda_{1}$ its largest eigenvalue,
$w_{t}$ is guaranteed to converge linearly to $w^{\ast}(\bar{w})$.

####  B.2.2 Distance between regularized and original optima

Now we look at the vector $w^{\ast}(\bar{w})-w^{\ast}$

$\displaystyle w^{\ast}(\bar{w})-w^{\ast}$
$\displaystyle=(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}D(R+\gamma
P^{\pi}\Phi\bar{w})-(\Phi D(I-\gamma P^{\pi})\Phi)^{-1}\Phi DR$
$\displaystyle=((\Phi^{\top}D\Phi)^{-1}-(\Phi^{\top}D(I-\gamma
P^{\pi})\Phi)^{-1})\Phi^{\top}DR+(\Phi^{\top}D\Phi)^{-1}\gamma\Phi^{\top}DP^{\pi}\Phi\bar{w}$
$\displaystyle=-\gamma(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi(\Phi
D(I-\gamma
P^{\pi})\Phi)^{-1})\Phi^{\top}DR+\gamma(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP\Phi\bar{w},\
\text{using Lemma \ref{lemma:inverse_diff}}$
$\displaystyle=-\gamma(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi
w^{\ast}+\gamma(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP\Phi\bar{w},\ \text{By
definition of}\ w^{\ast}$
$\displaystyle=\gamma(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi(\bar{w}-w^{\ast})$

We summarize it here, this is the bias between the regularized and true optima

$\boxed{w^{\ast}(\bar{w})-w^{\ast}=\gamma(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi(\bar{w}-w^{\ast})}$
(12)

####  B.2.3 Distance between inner loop iterate and optimum

$\displaystyle\mathcal{T}_{K}(\bar{w})-w^{\ast}$
$\displaystyle=\mathcal{T}_{K}(\bar{w})-w^{\ast}(\bar{w})+w^{\ast}(\bar{w})-w^{\ast}$
$\displaystyle=(I-\eta\Phi^{\top}D\Phi)^{K}(\bar{w}-w^{\ast}(\bar{w})+\gamma(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi(\bar{w}-w^{\ast})$
$\displaystyle=(I-\eta\Phi^{\top}D\Phi)^{K}(\bar{w}-w^{\ast}-(w^{\ast}(\bar{w})-w^{\ast}))+\gamma(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi(\bar{w}-w^{\ast})$
$\displaystyle=[(I-\eta\Phi^{\top}D\Phi)^{K}(I-\gamma(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi)+\gamma(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi](\bar{w}-w^{\ast})$

It is possible to rewrite it in value space by multiplying by $\Phi$ on the
left

$\displaystyle\mathcal{T}_{K}(\bar{Q})-Q^{\ast}$
$\displaystyle=\Phi(I-\eta\Phi^{\top}D\Phi)^{K}(I-\gamma(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi})(\bar{Q}-Q^{\ast})+\gamma\Phi(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi(\bar{w}-w^{\ast})$
$\displaystyle=\Phi(I-\eta\Phi^{\top}D\Phi)^{K-1}((\Phi^{\top}D\Phi)^{-1}-\eta
I)\Phi^{\top}D\Phi(I-\gamma(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi)(\bar{w}-w^{\ast})+\gamma\Pi_{\Phi}P^{\pi}(\bar{Q}-Q^{\ast})$
$\displaystyle=\Phi(I-\eta\Phi^{\top}D\Phi)^{K-1}((\Phi^{\top}D\Phi)^{-1}-\eta
I)\Phi^{\top}D(I-\gamma\Phi(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi)(\bar{Q}-Q^{\ast})+\gamma\Pi_{\Phi}P^{\pi}(\bar{Q}-Q^{\ast})$
$\displaystyle=\Phi(I-\eta\Phi^{\top}D\Phi)^{K-1}((\Phi^{\top}D\Phi)^{-1}-\eta
I)\Phi^{\top}D(I-\gamma\Pi_{\Phi}P^{\pi})(\bar{Q}-Q^{\ast})+\gamma\Pi_{\Phi}P^{\pi}(\bar{Q}-Q^{\ast})$
$\displaystyle=\big{[}\Phi(I-\eta\Phi^{\top}D\Phi)^{K-1}((\Phi^{\top}D\Phi)^{-1}-\eta
I)\Phi^{\top}D(I-\gamma\Pi_{\Phi}P^{\pi})+\gamma\Pi_{\Phi}P^{\pi}\big{]}(\bar{Q}-Q^{\ast})$

The interesting bit here when analyzing how this behaves for large $K$ is that
$(I-\eta\Phi^{\top}D\Phi)^{K-1}$ is essentially a matrix that can become
arbitrarily small when $K$ is large.

$\mathcal{T}_{\infty}(Q(\bar{w}))-Q^{\ast}=\gamma\Pi_{\Phi}P^{\pi}(Q(\bar{w})-Q^{\ast})$
(13)

This is guaranteed to converge if $\Pi_{\Phi}P$ is a contraction, which is the
case for instance when $D$ is the stationary distribution of $P$.

Also as $Q^{\ast}=\Phi w^{\ast}$ is the fixed point of the projected Bellman
iteration, we have

$\mathcal{T}_{\infty}(Q(\bar{w}))=\Pi_{\Phi}\big{(}R+\gamma
P^{\pi}Q(\bar{w})\big{)}$

This is the _projected value iteration_ or _projected policy evaluation_
algorithm (Bertsekas and Tsitsiklis,, 1996).

####  B.2.4 Continuity of norms and spectral radius

Now if we suppose that $\rho(\Pi_{\Phi}P^{\pi})<\frac{1}{\gamma}$ or written
differently $\rho(\gamma\Pi_{\Phi}P^{\pi})\leq\alpha<1$, as $\rho$ is a
continuous function of its input entries, for $K$ large enough, we can
guarantee that

$\forall\epsilon>0,\exists
K\in\mathbb{N}/\rho(\Phi(I-\eta\Phi^{\top}D\Phi)^{K-1}((\Phi^{\top}D\Phi)^{-1}-\eta
I)\Phi^{\top}D(I-\gamma\Pi_{\Phi}P^{\pi}\Phi)+\gamma\Pi_{\Phi}P^{\pi})<\alpha+\epsilon$

In particular for $\epsilon<1-\alpha$ which would ensure the convergence of
the algorithm.

The lower bound on $K$ can be made more precise using the Bauer-Fike theorem
$\rho(A+B)\leq\rho(A)+\|B\|\kappa(P_{A})$

We can write

$\displaystyle\rho_{K}$
$\displaystyle\leq\gamma\rho(\Pi_{\Phi}P^{\pi})+\kappa\|(I-\eta\Phi^{\top}D\Phi)^{K}(I-\gamma(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi)\|$
$\displaystyle\leq\gamma\rho(\Pi_{\Phi}P^{\pi})+C\|(I-\eta\Phi^{\top}D\Phi)\|^{K}\cdot$

where $C=\kappa\|I-\gamma(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi)\|$
for $\kappa$ the condition number of the eigenvector matrix of $\Pi_{\Phi}P$.

So we can take

$K>\frac{\log\frac{C}{1-\gamma\rho(\Pi_{\Phi}P^{\pi})}}{\log\frac{1}{\|(I-\eta\Phi^{\top}D\Phi)\|}}$

which ensures the spectral radius of TD-TN is $<1$.

###  B.3 Proof for TD-FR, Proposition 3.2

Let us consider the case where parametrize $Q$ with a linear function
approximation, $Q=\Phi w$,
$\Phi\in\mathbb{R}^{|\mathcal{S}|\cdot|\mathcal{A}|\times
p},w\in\mathbb{R}^{p}$.

####  B.3.1 Part 1: Fixed point of the regularized loss

Let us look at when the gradient is $0$:

$-\Phi^{\top}D(R+\gamma P^{\pi}\Phi w-\Phi
w)+\kappa\Phi^{\top}D\Phi(w-\bar{w})=0$

Thus $\Phi^{\top}D(I+\kappa-\gamma P^{\pi})\Phi
w=\Phi^{\top}DR+\kappa\Phi^{\top}D\Phi\bar{w}$. We call

$\boxed{w_{\kappa}(\bar{w})=(\Phi^{\top}D(I+\kappa-\gamma
P^{\pi})\Phi)^{-1}(\Phi^{\top}DR+\kappa\Phi^{\top}D\Phi\bar{w})}$

the solution of the regularized problem. We denote
$A_{\kappa}=\Phi^{\top}D(I+\kappa-\gamma P^{\pi})\Phi$ the regularized
_iteration_ matrix. The TD(0) update is therefore

$\displaystyle w_{t+1}$ $\displaystyle=$ $\displaystyle(I-\eta
A_{\kappa})w_{t}+\eta(\Phi^{\top}DR+\kappa\Phi^{\top}D\Phi\bar{w})$
$\displaystyle=$ $\displaystyle(I-\eta A_{\kappa})w_{t}+\eta
A_{\kappa}w_{\kappa}(\bar{w})$

Therefore

$w_{t+1}-w_{\kappa}(\bar{w})=(I-\eta A_{\kappa})(w_{t}-w_{\kappa}(\bar{w}))\\\
$ (14)

####  B.3.2 Part 2: Difference between regularized optima and true optima

Let us look at the quantity $w_{\kappa}(\bar{w})-w^{\ast}$ where
$w^{\ast}=A_{0}^{-1}\Phi^{\top}DR$, the solution of the unregularized problem.
First, we will use the fact that $A^{-1}-B^{-1}=A^{-1}(B-A)B^{-1}$ to get

$\displaystyle w_{\kappa}(\bar{w})-w^{\ast}$
$\displaystyle=A_{\kappa}^{-1}(\Phi^{\top}DR+\kappa\Phi^{\top}D\Phi\bar{w})-A_{0}^{-1}\Phi^{\top}DR$
$\displaystyle=-\kappa A_{\kappa}^{-1}\Phi^{\top}D\Phi
A_{0}^{-1}\Phi^{\top}DR+\kappa A_{\kappa}^{-1}\Phi^{\top}D\Phi\bar{w}$
$\displaystyle=\kappa A_{\kappa}^{-1}\Phi^{\top}D\Phi(\bar{w}-w^{\ast})$

Thus we have

$w_{\kappa}(\bar{w})-w^{\ast}=\kappa
A_{\kappa}^{-1}\Phi^{\top}D\Phi(\bar{w}-w^{\ast})$ (15)

####  B.3.3 All together

$\displaystyle\mathcal{T}^{T}_{\kappa}(w_{t})-w^{\ast}$
$\displaystyle=\mathcal{T}^{T}_{\kappa}(w_{t})-w_{\kappa}(w_{t})+w_{\kappa}(w_{t})-w^{\ast}$
$\displaystyle=(I-\eta A_{\kappa})^{T}(w_{t}-w_{\kappa}(w_{t}))+\kappa
A_{\kappa}^{-1}\Phi^{\top}D\Phi(w_{t}-w^{\ast}),\ \text{using
\ref{eq:iter_reg} and \ref{eq:reg_opt}}$ $\displaystyle=(I-\eta
A_{\kappa})^{T}(w_{t}-w^{\ast}-(w_{\kappa}(w_{t})-w^{\ast}))+\kappa
A_{\kappa}^{-1}\Phi^{\top}D\Phi(w_{t}-w^{\ast})$ $\displaystyle=(I-\eta
A_{\kappa})^{T}(w_{t}-w^{\ast}-\kappa
A_{\kappa}^{-1}\Phi^{\top}D\Phi(w_{t}-w^{\ast}))+\kappa
A_{\kappa}^{-1}\Phi^{\top}D\Phi(w_{t}-w^{\ast}),\ \text{Using \ref{eq:reg_opt}
again}$ $\displaystyle=\big{[}(I-\eta A_{\kappa})^{T}(I-\kappa
A_{\kappa}^{-1}\Phi^{\top}D\Phi)+\kappa
A_{\kappa}^{-1}\Phi^{\top}D\Phi\big{]}(w_{t}-w^{\ast})$

####  B.3.4 Studying $I-\eta A_{\kappa}$

For this, let us study the eigenvalues of $A_{\kappa}$, and make sure they
have a positive real part. Then by choosing $\eta\leq 2\
\mathfrak{Re}(\frac{1}{\lambda_{\text{max}}})$ the matrix will be stable.

For this, we will need, an assumption, i.e that TD(0) converges for that
combination of $\Phi,D,P$ and $\gamma$.

######  Assumption B.3.

$Sp(\Phi^{\top}D\Phi-\gamma\Phi^{\top}DP^{\pi}\Phi)\subset\mathbb{C}^{+}$

Let us call $\epsilon_{\kappa}=\min_{\lambda\in
Sp(A_{\kappa})}\mathfrak{Re}(\lambda)$.

As $\lim_{\kappa\to
0^{+}}A_{\kappa}=\Phi^{\top}D\Phi-\gamma\Phi^{\top}DP^{\pi}\Phi$, we have
$\epsilon_{0}>0$ and by continuity of the spectrum, $\exists\delta$ so that
$\forall\kappa<\delta$, $\epsilon_{\kappa}\geq\frac{\epsilon_{0}}{2}>0$. Thus
we just showed that for $\kappa$ small enough the matrix $A_{\kappa}$ was also
stable.

####  B.3.5 Studying $\kappa A_{\kappa}^{-1}\Phi^{\top}D\Phi$

Here we just need to show that for $\kappa$ small enough this matrix will be
stable, i.e have a spectral radius bounded by $1$. It is sufficient to notice
that $A_{\kappa}^{-1}\Phi^{\top}D\Phi$ has a finite limit when $\kappa\to 0$,
which is equal to $A_{0}^{-1}\Phi^{\top}D\Phi$ which is indeed bounded as
$A_{0}=\Phi^{\top}D\Phi-\gamma\Phi^{\top}DP^{\pi}\Phi$ has non-zero
eigenvalues as they are $\subset\mathbb{C}^{+}$ as per the Assumption above.

Thus, for $\lim_{\kappa\to 0}\kappa A_{\kappa}^{-1}\Phi^{\top}D\Phi=0$ which
has a spectral radius of $0$. Then again, by continuity of the spectrum thus
spectral radius, for $\kappa$ small enough, $\kappa
A_{\kappa}^{-1}\Phi^{\top}D\Phi$ has a spectral radius $<1$.

######  Corollary B.4 (Stability of TD-FR and TD-TN).

When $p=1$, for $T$ large enough, the convergence domain of TD-TN is included
in the one of FR-TN.

###  B.4 Proof for Corollary B.4

We first need to show that
$Sp(\Phi^{\top}D\Phi-\gamma\Phi^{\top}DP^{\pi}\Phi)\subset\mathbb{C}^{+}$
implies that
$\rho\big{(}(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi)\big{)}<\frac{1}{\gamma}$.

Let us consider ${\mathbf{v}}$ a eigenvector of
$(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi$ associated with the
eigenvalue $\lambda$. Thus

$\Phi^{\top}DP^{\pi}\Phi{\mathbf{v}}=\lambda\Phi^{\top}D\Phi{\mathbf{v}}$

From this we multiply by $\gamma$ and substract and add
$\Phi^{\top}D\Phi{\mathbf{v}}$:

$\big{(}\Phi^{\top}D\Phi-\gamma\Phi^{\top}DP^{\pi}\Phi\big{)}{\mathbf{v}}=(1-\lambda\gamma)\Phi^{\top}D\Phi{\mathbf{v}}$

Multiplying by ${\mathbf{v}}^{\top}$:

${\mathbf{v}}^{\top}\big{(}\Phi^{\top}D\Phi-\gamma\Phi^{\top}DP^{\pi}\Phi\big{)}{\mathbf{v}}=(1-\lambda\gamma){\mathbf{v}}^{\top}\Phi^{\top}D\Phi{\mathbf{v}}$

As $\Phi^{\top}D\Phi$ is positive definite (non-singular by assumption),
${\mathbf{v}}^{\top}\Phi^{\top}D\Phi{\mathbf{v}}>0$. However we can’t conclude
anything in the general case with non-symmetric matrices. When $p=1$, these
matrix products become real scalars as all the coefficients are real. So for
$x^{2}=\Phi^{\top}D\Phi$

$\big{(}\Phi^{\top}D\Phi-\gamma\Phi^{\top}DP^{\pi}\Phi\big{)}=(1-\lambda\gamma)x^{2}$

so $\big{(}\Phi^{\top}D\Phi-\gamma\Phi^{\top}DP^{\pi}\Phi\big{)}>0$ implies
that $(1-\lambda\gamma)>0$, thus $\lambda<\frac{1}{\gamma}$ the maximum and
only eigenvalue, thus the spectral radius of
$(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi$ is smaller than
$\frac{1}{\gamma}$.

We denote by
${\mathcal{D}}_{\text{TD}}=\\{\Phi,D|Sp(\Phi^{\top}D\Phi-\gamma\Phi^{\top}DP^{\pi}\Phi)\subset\mathbb{C}^{+}\\}$
and
${\mathcal{D}}_{\text{TN}}=\\{\Phi,D|\rho\big{(}(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}DP^{\pi}\Phi)\big{)}<\frac{1}{\gamma}\\}$
the convergence domains of TD and TN ($T=+\infty)$. We just proved for $p=1$
that ${\mathcal{D}}_{\text{TN}}\subset{\mathcal{D}}_{\text{TD}}$. We know from
Proposition B.2 and 3.2 that for $\kappa$ small enough, FR(T) and TN(T) (FR
and TN using a period update of $T$) and ${\mathcal{D}}_{\text{FR(T)}}$,
${\mathcal{D}}_{\text{TN(T)}}$ their convergence domains that
$\lim_{T\to+\infty}{\mathcal{D}}_{\text{FR(T)}}={\mathcal{D}}_{\text{TD}}$ and
$\lim_{T\to+\infty}{\mathcal{D}}_{\text{TN(T)}}={\mathcal{D}}_{\text{TN}}$.
Thus by taking the limit we have the inclusion we needed.

##  Appendix C Additional Results and Hyper-parameters

###  C.1 2-state MDP

We see on Section C.1 that increasing the discount factor leads to larger
divergence regions. However, the circle of radius $\pi(s_{0})$ which
corresponds to the on-policy algorithm stays in the convergent domain as
predicted by theory.

(a) TD(0)

(b) TN

(c) FR

Figure 3: 2-state MDP. $\gamma=0.9995$

(a) TD(0)

(b) TN

(c) FR

Figure 4: 2-state MDP. $\gamma=0.995$

(a) TD(0)

(b) TN

(c) FR

Figure 5: 2-state MDP. $\gamma=0.95$

###  C.2 Four Rooms

Figure 6: 4 Rooms environment. The agent starting position is denoted in red and the goal in blue. Table 2: Four Rooms Hyper-parameters Hyperparameter | Value
---|---
learning rate | 1e-4
optimizer | adam (Kingma and Ba,, 2014)
discount factor $\gamma$ | 0.99
DNN layers | [128, 128, 4]
dimension | $11\times 11$

###  C.3 Atari

Figure 7: DQN Atari Comparison. Performance curves for the subset of Atari
games from Mnih et al., (2013). The returns are averaged over 10 trials using
the $\epsilon$-greedy policy with $\epsilon=0.05$. Figure 8: Double DQN Atari
Comparison. Performance curves for the subset of Atari games from Mnih et al.
(Mnih et al.,, 2013).  Figure 9: Rainbow DQN Atari Comparison. Performance
curves for the subset of Atari games from Mnih et al. (Mnih et al.,, 2013).

Most of the hyper-parameters have been kept from the defaut DQN and Double DQN
respectively. Here is a list of the tuning that has been performed and the
resulting best hyper-parameters.

Table 3: Atari Hyper-parameters Hyperparameter | Polyak DQN | FR DQN | FR Double DQN | Deep Mellow | FR Rainbow
---|---|---|---|---|---
$\tau$ | 5e-5, 2.5e-5, 1e-5, 5e-6 | - | - | - | -
TN Update Period | 100 | - | - | - | -
FR Update Period | - | 4e4 | 4e4 | - | 3.2e4
$\kappa$ | - | 0.25, 0.5, 0.75 | 0.75 | - | 0.25, 0.5, 0.75, 1, 2.5, 5
Mellow Temperature | - | - | - |  25, 50, 75, 100 | -