The Pitfalls of Regularization in Off-Policy TD Learning
Authors: Gaurav Manek
J Zico Kolter
Venue: NeurIPS 2022 Accept (2022)
Keywords: regularization
ridge
td
rl
reinforcement learning
theory

Abstract: Temporal Difference (TD) learning is ubiquitous in reinforcement learning, where it is often combined with off-policy sampling and function approximation.  Unfortunately learning with this combination (known as the deadly triad), exhibits instability and unbounded error.  To account for this, modern Reinforcement Learning methods often implicitly (or sometimes explicitly) assume that regularization is sufficient to mitigate the problem in practice; indeed, the standard deadly triad examples from the literature can be ``fixed'' via proper regularization. In this paper, we introduce a series of new counterexamples to show that the instability and unbounded error of TD methods is not solved by regularization. We demonstrate that, in the off-policy setting with linear function approximation, TD methods can fail to learn a non-trivial value function under any amount of regularization; we further show that regularization can induce divergence under common conditions; and we show that one of the most promising methods to mitigate this divergence (Emphatic TD algorithms) may also diverge under regularization. We further demonstrate such divergence when using neural networks as function approximators.  Thus, we argue that the role of regularization in TD methods needs to be reconsidered, given that it is insufficient to prevent divergence and may itself introduce instability. There needs to be much more care in the practical and theoretical application of regularization to Reinforcement Learning methods.


The Pitfalls of Regularization in Off-Policy TD Learning
Gaurav Manek
Zico Kolter
Computer Science Department Carnegie Mellon University Pittsburgh, PA 15213 gmanekkcs cmu. edu
Computer Science Department Carnegie Mellon University Pittsburgh, PA 15213 zkolterêcs. cmu. edu
Abstract
Temporal Difference (TD) learning is ubiquitous in reinforcement learning, where it is often combined with off-policy sampling and function approximation. Un- fortunately learning with this combination (known the deadly triad), exhibits instability and unbounded eπror. To account for this, modern RL methods often implicitly (or sometimes explicitly) assume that regularization is sufficient to miti- gate the problem in practice; indeed, the standard deadly triad examples from the literature can be "fixed" via proper regularization. series of new counterexamples to show that the instability and unbounded error of TD methods is not solved by regularization. We demonstrate that, in the off- policy setting with linear function approximation, TD methods can fail to learn a non-trivial value function under any amount of regularization; we further show that regularization can induce divergence under common conditions; and we show that one of the most promising methods to mitigate this divergence (Emphatic TD algorithms) may also diverge under regularization. We further demonstrate such divergence when using neural networks as function approximators. Thus, we argue that the role of regularization in TD methods needs to be reconsidered, given that it is insufficient to prevent divergence and may itself introduce instability. There needs to be much more in the practical and theoretical application of regularization to RL methods.
this paper, we introduce a
Introduction
Temporal Difference (TD) learning is a method for learning expected duture-discounted quantities from Markov processes, using transition samples iteratively improve estimates. This is most commonly used to estimate expected future-discounted rewards (the value function) in Reinforcement Learning (RL). Advances in RL allow us use powerful function approximators, and also to use sampling strategies other than naively following the Markov process (MP). When TD, function approximation, and off-policy training are all combined. learned functions exhibit severe instability and divergence, as classically observed by Williams and Baird III [18), Tsitsiklis and Van Roy [1]. This combination is known in the literature as the deadly triad [I]] pg. 264], and while many contemporary variants of TD are designed to converge despite the instability, the quality of the solution at convergence may be arbitrarily poor.
common technique to avoid unbounded error is E regularization 14 i.e. penalizing the squared norm of the weights in addition the TD error. This is generally understood bound the worst-case error in exchange for biasing the model and potentially increasing the error everywhere else. When used on three common examples of the deadly triad 6 pg. 260), regularization appears
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

mitigate the worst aspects of the divergence in practice. Consequently, it has become an essential as- g and is seen as routine and innocuous.
sumption made by many RL algorithms [C 12
19
20
21
We argue that this perspective on regularization in off-policy TD is fundamentally mistaken. While regularization is indeed reasonably well-hehaved and innocuous in classic fully-supervised contexts, the use of bootstrapping in TD means that even small amounts of model bias induced by regularization can cause divergence. This is an oft-ignored phenomenon in the literature, and so we introduce a series of new counterexamples (summarized in Table T to show how regularization can have counterintuitive and destructive effects in TD. We show that vacuous solutions and training instability are not solved by the use of regularization; that applying regularization can sometimes induce divergence and increase worst-case error; and that Emphatic TD algorithms-whic are the most promising solution to this divergence- can themselves diverge when regularized. We finally also illustrate mishehaving regularization the context of neural network value function approximation, demonstrating the general pitfalls of regularization possible in RI. algorithms. Regularization needs to be treated cautiously in the context of kL., as it behaves differently than in supervised settings.
Our counterexamples demonstrate these core ideas:
TD learning off- off-policy can be unstable and/or have unbounded error even when it converges. Following well-established methods we show there is some off- policy distribution under which TD with linear value function approximation diverges and learns model with unbounded error (even if it were able to converge to the TD fixed point). This concisely demonstrates key features of the training error: the error is small when the distribution is close to on-policy, but the error diverges around specific off- aff-policy distributions. The intuition behind this, explained in Section 3 is that the off-po off-policy[]1 policy[TDD TD update involves a projection operation that depends on the sampling distribution and can be arbitrarily far away from the true value. This basic fact has already been established by past work [88 (). but our example is based upon a particular simple three-state MP, drawn in Figure Ia
Regularization cannot always mitigate off-policy training error. We next introduce regulariza- tion into our setting, and show how it changes the relationship between training error and off-policy training. As explained in Section we penalize the &g norm of learned (linear) weights with some coefficient ry; as 7) increases, the learned weights approach zero However, in Example]] that there exists off-policy distribution such that for any n) 2 0 < co, the regularized TD fixed point attains strictly higher approximation error than the zero solution (i.e., the infinitely regularized point). We call such examples vacuous. In other words, vacuous value functions never do better than guessing zero for all states, for any amount of regularization.
[ we show
We further analyze this vacuous example in the context of the algorithm in (21]. In this work, the authors assume the use of regularization to derive bounds on the learned error under off-policy sampling. Although these bounds are technically correct in the case of our counterexample, they very loose, at about 2000 times the threshold of vacuity. This highlights the challenge of formally relying on regularization to bound model error.
Small amounts of regularization can cause model divergence or large errors. There is a general implicit assumption in much ML. literature that regularlization monotonically shrinks learned weights. This intuition comes from classic fully-supervised machine learning where it typically holds. But because TD bootstraps value estimates (i.e. learns values using its own output), it possible for small amounts of bias to be arbitrarily magnified. We dub this phenomenon "small-eta error" and illustrate in Example We relate this to the presence of negative eigenvalues in an intermediate step of the solution and show that, in some settings, the eтror of the TD solution may be relatively small when applied with no regularization but adding regularization causes the model to have worse error than the zero solution.
One common solution this problem is to lower-bound v) to guarantee that reguarlization behaves monotonically. However, we further show that such a lower bound may occur after the point of vacuity: model that is not vacuous becomes vacuous for any regularization parameter above this lower bound. We also show that it is not always possible to select single 7) a priori, with examples of
We consider a sampling distribution to be on-policy if it follows the stationary distribution of the MP: we do not explicitly consider separate policy in this paper.
2

---

Example
There exist off-policy distributions under which TD learns a vacuous model (one which- despite any amount of regularization-never does better than guessing zeros). Small values of the regularization parameter 1 can make TD diverge in models that otherwise converge. This is an unavoidable effect of bootstrapping TD, and setting a lower-bound to exclude this may render models vacuous.
Example2
Example
Emphatic- Srpphati-TDD-nsspiiee -D-isspired algorithms are a promising way to reweight samples and mitigate the effects of training off off-po.lcy. But if this reweighting is learned using TD, then using regularization can bias the emphasis model and cause the value model itself to diverge. Training instability and increased error due to the deadly triad also occur when neural networks are used. We construct an empirical example and draw qualitative comparisons.
Example
Table 1: Summary of theorems.
1/5
1/4
83
1/4
1/4
$3,1
1/2
1/2
1/2
1/2
1/4
82
$1,1
$2,1
1/4
1/4
1/4
(a) Three-state MP.
(b) Nine-state MP.
Figure I: Our three- and nine-state counterexample MPs. We use these to illustrate how TD models can fail despite common mitigating strategies in linear and neural network cases respectively.
muttuall-incompatiine off- off-poolcy distributions where there is no that achieves better than vacuous or nearly-vacuous results different distributions.
Emphatic-TDD-asse TD-based algorithms are vulnerable to instability from regularization. Emphatic- TD [13 fundamentally solves the problem of training off-policy by resampling TD updates so they appear to be on-policy. This technique requires an emphasis model that decides how scale each TD update, and learning this has been the key challenge preventing widespread adoption of Emphatic-TDD A recent paper (20) proposed learning this emphasis model using "reversed" TTD while simultaneously learning the value model using regular TD. The resultant algorithm called COF-PAC, and employs regularization to ensure that the two TD models eventually converge.
We show that regularization, while necessary, can be harmful for such models in Example 3 Specifically, we construct model that converges to the correct solution without regularization but to an arbitrarily poor solution when regularized. The intuition behind this is that regularizing the emphasis model changes the effective distribution of the TD updates to the value model, which can cause the value model to have arbitrarily large error. We complete the example by showing that regularizing the value function separately does not restore performance.
Regularization can cause model divergence in neural networks. So far most analysis of the deadly triad in the literature focuses on the linear case. We extend our example to nine-state Markov chain (shown in Figure lb), and show how the previously identified problems persist into the neural network case in Example 4 We show two key similarities: first, models trained at certain off policy distributions may vacuous. Second, small amounts of regularization counterintuitively increase emror. This illustrates Example 2 in the NN case.
2 Preliminaries and Notation
Consider the n-state Markov chain (S, P. RR with state space S, state-dependent reward R + R, and discount factor 7 E [0, 1). P E Rexa is the transition matrix, with P.₃ encoding the probability of moving from state i to We wish to estimate the value function V S + R, defined
3

---

as the expected discounted future reward of being in each state: V(s) EE= ( - s|. key property that it follows the Bellman equation:
R PV
Using linear function approximation to learn V, we assume a matrix of feature-vectors & E R"*k that is fixed, and vector of parameters w I2 that learned. The Bellman equation then:
vw R po
When w is learned with TD, this equation is only valid if the TD updates are on-policy (that is, they are distributed according to the steady-state probability of visiting each state, written as π E IR"). In the general case, where TD updates follow (possibly) different distribution μ E 18g. the TD solution is a fixed point of the Bellman operator followed by projection 6
tw = 1 (R+
where the matrix IT ( D D projects the Bellman backup onto the columnspace of 4 reweighted by the diagonal matrix D = diag(1) This yields the closed-form solution:
w A-
Where = T 7P) and 5 DR. When this solution subject to regularization, some non-negative is added to ensure the matrix being inverted is positive definite:
(1)
(A + n
(5)
As will be important later, we note that as 77 increases it drives w" (17 towards zero.
Our Counterexamples
When deadly triad conditions are present, TD may learn a value function with arbitrarily large error even if the true value function can be represented with low error. Consider the threc-state MP in Figure la which we instantiate with the value function V [1, 2.2, 1.05] T and discount factor 0.99. The reward function is computed as R + (1 V. We choose basis d with small
representation error [II,
VII S
1
0 1//2(1.0 +c) -1/2(1.05 + +e]
-22
where O
(6)
We first consider the unregularized (17 0) case, closely following the derivation in 6 We wish to show there is some sampling distribution such that error in the learned value function is unbounded.
To do this, set μ [0.56(1 p), 0.56p, 0.44), where p (0, 1). We e 1 and find p around which A is ill-conditioned by solving det (A) 0:
p = 0.102631
V
0.807255
A (and consequently the error) can be made arbitrarily large by selecting p close these values, which completes the introductory example. Now we look at the behavior of TD under regularization, which is the main contribution of our paper.
3.1 Regularization cannot always mitigate off-policy training error.
There is belief in the literature that regularization is trade-off between reducing the blow-up of asymptotic emror and accurately learning the value function everywhere else 21 However, this belief does not accurately capture the nature of regularization: we show that it is possible to learn models that never perform better than always guessing zero despite any amount of regularization. That is, the TD error at all ry is at least much as the error 1 oo. We call such models vacuous.

---

Example 1. When TD is regularized, there may exist some off- off-policy distribution at which TD learns a vacuous model. In notation:
| (n) Vil 2 lim |l (n) - VII = | - VII = | Vin E R
(8)
17000
Details. We use the same setting as in Section 3 A detailed derivation is provided in Appendix [.2
We begin by noting that we can easily find the solution d that minimizes the least-squares error || VIl. If we consider this solution as vector (as drawn in Figure 2a), we can immediately see that there is an Ez-ball around ú corresponding to the set of w= (n) with no more than [| error.
trace the trajectory that the TD solution w" (1) takes as 7) is increased from 0 to co. We know that, as + 0o, w² (1) is crushed to zero and so all trajectories must eventually terminate at the origin. When regularized models are not vacuous, the trajectory intersects the non-vacuous-error ball. We see this in trajectory 2, where the error briefly dips below [ in Figure 2b
Similarly,
Intuitively, sufficient condition for solution to be vacuous is that it remains in the half-space that is tangent to and excludes the non-vacuous parameter ball. This is equivalent to finding some distribution μ such that ú w² (m) S 0 for all 17, which numerically solve to obtain the model in trajectory 1. From Figure 2a we can see the trajectory remains in the half-space, and from Figure 2b we can see that the error never less than [V]. Trajectory 1 is vacuous example.
Th""" (17) s 0, could easily We observe that Example 1, because it remains entirely in the halfspace v w= be generalized to other forms of regularization. We leave this for future work.
Breaking the Deadly Triad and our counterexample. In light of our example we examine the work of [2I] in which the authors derive a bound for the regularized TD error under a novel double- projection update rule. We apply our example to their bound and show that their method may produce loose bounds on TD solutions, and so doesn't quite break the deadly triad:
max )))
Iow" VII S
|| + | - -VI)
(9)
T (m) (D)2.5
for & E [0, 1]. where Tmax and amin denote the largest and smallest singular value respectively. Theorem 2 from [2] bounds 7, and therefore also b:
7 > arg inf | Coll 0.177/(1 -1 e)²
(10)
inf b(E = 5.20 x 10 2 2000 |V|
(11)
Their method bounds the error in our example by 2000 ||V||, which is tremendously loose. (We analyze a different example in Appendix B.3 showing still-loose but improved bound of 8 * [[]] This illustrates the risk of relying on regularization to formally bound model error.
3.2 Small amounts of regularization can cause large increases in training error.
There a general assumption in the literature that &g regularization monotonically shrinks the learned weights. While this is true in classification, regression, and other non-bootstgapping contexts, this is not true in TD. Because TD bootstraps values, is possible for model bias to he arbitrarily magnified.
This can be understood in terms of the eigenvalues of the matrix A in Equation 5 By increasing values along the diagonal, lg regularization increases eigenvalues of the matrix (A + +nd) to ensure is positive definite. Under off-policy distributions, it is possible for A to have eigenvalues that are negative or zero. This implies that there are 1y for which det(AA + 7/) = O, and selecting 1) close to these values allows us achieve arbitrarily high error. We show one such case in Example 2 This is not merely theoretical-ve we demonstrate this in the neural network case in Section 3.4
Example 2. When TD is regularized, the model may diverge around (typically small) values of n-. Lower-bounding 7, a common mitigation, can make well-behaved models vacuous. It is not always possible to select a single value of 1) that makes models vacuous at different sampling distributions.
Details. Using our three-state example, we set μ [0.05, 0.05, 0.9) and solve for det(AA + m/)
0 = dct(A A + nT) = n² + 5.45 X 10 2n 7.47 x 10-3
0.0634
(12)
5

---

10a
(1)
Error at convergence
10
(2)
|
10
(3)
10-
10-6
10
10
10
10
10
Regularization parameter
(a) As 17 increases, w" (17) traces different trajectories different μ.. úà minimizes the error, and shade the area with TD error less than [V]
(b) We plot the error curves corresponding to the three w (n) trajectories, along with [|V]], Trajectory 1 is vacuous because the error at least |V]] for all 1).
Figure 2: Plotting the trajectory of the parameters the left and the errors the right, show how our counterexample is never better than ||V|| because remains in halfspace where u " w=())) & 0. For comparison, show trajectory 2 that is improved by regularization, and 3, which exhibits small-n errors. (The trajectories are stretched, so the errors in the two plots are not directly comparable.)
As in the introductory example, the error can be made arbitrarily large by setting 17 0.0634.
This small-n divergence effect can appear in several ways, illustrated in Figure 3a Typically, this appears
more points at which TD error diverges before the region which regularization reduces the model error below |[ The first and second plot in Figure 3a show two such cases, where the error increases sharply at two and one points respectively.
In the literature, it is commonly assumed that A "nearly" positive definite, where only a few eigenvalues non-positive, and those are close to zero. This gives rise to the common mitigation of setting a lower-bound 7/o such that (A + n/) is positive definite for > 7Jo- This may render an otherwise well belavee model vacuous. The third plot in Figure 3a illustrates this: the model is not vacuous when unregularized, but is vacuous in the domain 77 > 10 where divergence is prohibited.
A common practice in the literature is to set 7 before training. without regard for the sampling distribution. This ill advised, as the value may be under- or over-regulariving depending on the sampling distribution. One such example is illustrated in Figure 3bb where selecting 1) that minimizes the error for one distribution will lead vacuous or nearly-vacuour results in the other two. A second example in Figure 2b has single 7) for which trajectories 2 and 3 are both non-vacuous. This is especially relevant as regularization is commonly used to permit distribution drift during training, as discussed in Section 4 If the training distribution changes while is fixed, then algorithms that can be proven to converge to good solutions under some original distribution may converge to poor solutions as the distribution drifts.
3.3 Emphatic approaches and our counterexample
Emphatic-TTe TD eliminates instability from off- off-policy sampling by reweighting incoming data (via an importance function) so it appears to be on on-policy. There is considerable interest in making this more practical, especially by learning the importance and value models simultaneously. A leading example of this work is COF-PAC (20). which uses éz-regllarized versions of GTD2 [12] to learn both the value and emphasis models. The authors rely on regularization, particularly because the target policy changes during learning. This makes COF-PAC vulnerable to regularization-cause error. We illustrate this with Example in which COF-PAC learns correctly when unregularized, but has large error when regularized. (Mathematical details deferred to Appendix BB5))
Example 3. COF-PAC may learn the value function with low error when unregularized, but with arbitrarily high error when regularized.
Details. Conceptually, COF-PAC maintains two separate models that are each updated by TD: the emphasis and the value models. This emphasis model is used to reweight TD updates to the value

---

10
I
10
[V]
TD error
I
100
10
V
10
10
10
10
10
10
10-5
10
10
10
Regularization parameter
Regularization parameter
(a) Different MPs off-policy distributions selected show small-n error. The error may increase at multiple and may even occur after the optimal
(b) Three off-policy distributions with mutually in- compatible 1,. There is no at which all models not vacuous nearly vacuous.
Figure 3: We plot TD error against 17 to show small-n errors (left) and mututally-incompaa incompatible (right). We also plot the error at the limit of vacuity [[V]
and the representation error
Emphasis Model Error
Value Model Error
Value Model Error
0.4
IA
2
2-10
0
10 5
10-2 2
10-7
10 4
10-1
10-7
10
10
Emphasis 7mm
Emphasis 7mm.
Value The
(a) Tm distorts the emphasis model.
(b) 7/m distorts value.
(c) can't 't fix this.
Figure 4: Regularization on the emphasis model (7m) distorts the effective distribution (Figure 4a). Specific values of 7m induce the value function diverge (Figure 4b). The resultant value function is vacuous (Figure 4ch. Under COF-PAC, regularization can greatly increase model error.
function so they appear to come from the on-policy distribution. Our strategy is to first show how regularization biases the emphasis model, and then how this bias causes the value model diverge. We begin with our three-state MP, noting its on-policy distribution is π = [.25 .25, .5]. We wish to learn the values using COF-PAC while sampling off-policy f [.2 2 .6).
Now we introduce a key conceptual tool: v(mm), which the effective distribution seen by the TD-updates, influenced by the emphasis regularization parameter 7ma Unregularized, COF-PAC able to resample off-policy updates to the on-policy distribution: v(0) = π. If the model is regularized, then the effective distribution moves away from Figure illustrates the distance between m()) and as the regularlization parameter increases.
We can the effective distribution to compute the error in the value model. Plotting the relationship between the value function error and Thn in Figure 4b we can see the value function has asymptotic error around 7mm. x 10-4 This shows how COF-PAC may diverge with specific regularization.
COF-PAC also allows for the value function to separately regularized with parameter 1)., We show the effect of this in Figure 4c where the value function never does much better than ||V]| making it (nearly) vacuous. We can conclude that regularizing the emphasis model may cause the value model to diverge, and this cannot be fixed by regularizing the value function separatcly.
D

---

10
4
3.5
10
||V|22
3
10
unregularized regularized
2.5
10
2
0.2
0.4
0.6
0.8
10
5
10
10
10
2
10
10
Distribution parameter p
Regularization parameter 1)
(a) Mean and 10th 90th percentile errors of 100 NN value models trained to convergence.
(b) The relationship between error and n at the off- policy distribution p = 0.31.
Figure We illustrate how regularization interacts with NN value functions, showing that the problems identified in this paper persist in the NN case.
COF-PAC makes the strong assumption that Kolter's relaxed-contraction condition 66 eqn. 10] holds in both the emphasis and value models [20 asm. 4]. We discuss this in Appendix B.5.1
3.4 Applied to multi-layer networks
We use 9-state variant of our example to study the deadly triad in multi-layer neural networks (NNs). deterministic observation function is chosen so we can control the degree of function approximation. We train simple two-layer neural network with 3 neurons in the hidden layer. The value function is assigned pseudo-randomly in range [-1, 1]. (See Appendix [or details.)
Example 4. Vacuous models and small-7 eтrоr also occur in neural network conditions.
Details. We train 100 models using simple semi-gradient TD updates under fixed learning rate. We plot the mean and the 1hth percentile range Figure 5a with and without regularization. TD known to exhibit high variance, and regularization is the traditional remedy for that. We corroborate this by noting that the performance of the unregularized model varies widely, but regularization leads to similar performance across initializations at the cost of increased error.
First, we show that vacuous models may exist in the neural network case. In Figure 5a note how there are some off-policy distributions under which both the regularized and unregularized models perform worse than the threshold of vacuity. We can numerically verify that vacuous models exist. Second, we show the small-m етrоr problem in the neural network case in Figure 5b, where we plot the TD error against n) at a fixed off policc distribution. We observe that around > 10-3 30 the TD Error unexpectedly increases before decreasing, which clearly illustrates this phenomenon.
These qualitative links show clear connection between the neural network case and the linear case, and highlights the importance of correctly handling off-policy sampling.
Related Work
Three examples of the deadly triad are common in the literature: the classic Tsitsiklis and Van Roy
(w, 2w) example [II p. 260], Kolter's s example 6 and Baird's 's counterexample which shows how training instability can exist despite overparameterizztion [18].
l2 regularization is common when proving that an algorithm converges under a changing sampling policy. This is in GTD (analyzed in [19), GTD2 [12), RO-TD [10], and COF-PAC (00] This assumption may also be used to ensure convergence when training with a target network 21, Despite the prevalence regularization, the induced bias from using is not well studied. It often dismissed as a mere technical assumption, as in []] We contradict that: using regularization for convergence proofs may induce catastrophic bias. By showing concrete examples, this work hopes to inspire further investigation into regularization-induee bias in the same vein as [9
Alternatives to regularization and TD the & fomm of the learned weights; it is also possible to use l regularization with proximal
We focus on Ea regularization in this paper, which penalizes

---

operator/saddle point formulation as in [10], or any convex regularization term under a fixed target policy 19. Instead of directly regularizing the weights, COP-TD uses discounted update [4]
DisCor 7 propagates bounds on Q-value estimates to quickly converge TD learning in the face of large bootstrapping error; it is not clear if DisCor can overcome off off-policy sampling.
separate primal-dual saddle point method has also been adapted to l2 regularization [2] and is known to converge under deadly triad conditions, and recent work [17] has derived error bounds with improved scaling properties in the linear setting, offering promising line of research.
Emphatic- TD 13 fixes the fundamental problem in off off-po TD by reweighting updates so they appear on-policy. The core idea underlying these techniques is to estimate the "followon trace" for each state, the (weighted, A- and y disccuuutt probability mass of all states whose value estimates it influences. This trace is then used to estimate the emphasis, which is the reweighting factor for each update. While this family of methods provably optimal in expectation, is subject to tremendous variance in theory and practice, especially when the importance is estimated using Monte-Carlo sampling ? In practice, these methods learn the follow-on trace using TD 20 or similar [16] which makes them vulnerable to bias induced by the use of regularization.
5
Conclusion
There is a tremendous focus in the RL. literature on proving convergence of novel algorithms, but not the error at convergence. Papers like [21] are laudable because they provide error bounds; even the current bounds are loose, future work will no doubt tighten them. In this work, we show that the popular technique of & regularization does introduce catastrophic divergence. We show this with a new counterexample that elegantly illustrates the problems with learning off-policy and how it persists into the NN case.
always prevent singularities and could even
Even though regularization can catastrophically fail in the ways we illustrate, it remains a reasonable method that may offer fair tradcoff- long of the failure modes we explain in the paper. may be possible to design an adaptive regularization scheme that can avoid these pathologies. For now, testing the model performance regularization parameters (spanning several orders of magnitude) is the best option we have to detect such pathological behavior.
careful to check that are not running afoul
range of
Emphatic-TDD is perhaps the most promising area of research for mitigating off-policy TD-learning. The key problem preventing its widespread adoption is the difficulty in estimating the emphasis function, but future work in this area may be able to overcome this. Our example shows the risk of relying on regularization in practical implementations of such methods. It is absolutely critical that Emphatic algorithms correctly manage regularization to avoid the risks that we highlight in this paper.
[1] says about Emphatic-TD TD that "it is nigh impossible to get consistent results computational experiments." (when applied to Baird's example).
"Sutton and Barto's textbook

---

References
[1] R. B. Diddigi, C. Kamanchi, and S. Bhatnagar. A convergent off off-policy temporal difference algorithm. arXiv preprint arXiv:1911 1.05697, 2019.
[2] S. S. Du, J. Chen, Li, Xiao, and D. Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, pages 1049-1058. PMLR, 2017.
[3] W. Fedus, P. Ramachandran, R. Agarwal, Y. Bengio, H. Larochelle, M. Rowland, and W. Dabney, Revisiting fundamentals of experience replay. In International Conference on Machine Learning. pages 3061-3071. PMLR, 2020.
[4] C. Gelada and M. G. Bellemare. Off-policy deep reinforcement learning by bootstrapping the covariate shift. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3647-3655, 2019.
[5] R. Jiang, S. Zhang, V. Chelu, A. White, and H. van Hasselt. Learning expected emphatic traces for deep rl. arXiv preprint (.Xiv:2107.054440 2021.
[6] J. Kolter. The fixed points of off-policy td. Advances in Neural Information Processing Systems, 24:2169-211 (111999--77,22 2011.
[7] A. Kumar, A. Gupta, and Levine. Discor: Corrective feedback in reinforcement learning via distribution correction. arXiv preprint arXiv:2003.07303 2020.
[8] A. Kumar, R. Agarwal, T. Ma, A. Courville, G. Tucker, and S. Levine. DR3: Value- deep reinforcement learning requires explicit regularization. In International Conference on Learning Representations, 2022. URL httpps:/ net/forum? (iwfrrmmmmmddP0vvii111111111 POVMvL191f
[9] S. Levine, A. Kumar, G. Tucker, and J. Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. CoRR, abs/2005.01643, 2020. https///////axxi abs/2005, 01643
[10] S. Mahadevan, B. Liu, P. Thomas, W. Dabney, S. Giguere, N. Jacek, I. Gemp, and J. Liu. Proximal reinforcement learning: A new theory of sequential decision making in primal-dual spaces. arXiv preprint arXiv:1405.6755 2014.
[11] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, second edition edition, 2020.
[12] R. S. Sutton, H. R. Maci, D. Precup, S. Bhatnagar, D. Silver, C. Szepesvári, and E. Wiewiora. Fast gradient-descent methods for temporal-differenee learning with linear function approxima- tion. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 993-1000, 2009.
[13] R. S. Sutton, R. Mahmood, and M. White. An emphatic approach to the problem of off-policy temporal-differcen
learning. The Journal of Machine Learning Research, 17:2603-200 2631, 2016.
[14] A. N. Tikhonov. On the stability of inverse problems. In Dokl. Akad. Nauk SSSR, volume 39, pages 195-198, 1943.
[15] Tsitsiklis and B. Van Roy. An analysis of temporal-difference learning with function ap- proximation. Rep. LIDS-P-2320 Lab. Inf. Decis. Syst. Massachusetts Inst. Technol. Tech. Rep. 1996.
[16] H. van Hasselt, S. Madjiheurem, M. Hessel, D. Silver, A. Barreto, and D. Borsa. Expected eligibility traces. arXiv preprint arXiv:2007.018399 2021.
[17] A. J. Wagenmaker, Y. Chen, M. Simchowitz, S. Du, and K. Jamieson. First-order regret in reinforcement learning with linear function approximation: A robust estimation approach. In K. Chaudhuri, S. Jegelka, Song, Szepesvari, G. Niu, and S. Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 22384-22429. PMLR, 17-23 Jul 2022. URL https
//proceedings mlr wwwppressssss... sesees/vv62//ee v122/ 2e/./////wwnaaa222aaa.. html
[18] R. J. Williams and L. C. Baird III. Analysis of some incremental variants of policy iteration: First steps toward understanding actor-critic learning systems. Technical report, Citeseer, 1993.
[19] H. Yu. On convergence of some gradient-based temporal-difffrences algorithms for off-policy learning, arXiv preprint arXiv: 1712.0962... 2017.
10

---

[20] S. Zhang, B. Liu, H. Yao, and S. Whiteson. Provably convergent wwo-timescale off-policy actor-critic with function approximation. International Conference on Machine Learning. pages 11204-1123. PMLR, 2020.
[21] S. Zhang, H. Yao, and S. Whiteson. Breaking the deadly triad with target network. CoRR, abs/2101.08862, 2021. URL https: /tap:s///rxiv...
//arxivvv... org/ htt//bb/221000 08862
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We clearly specify that this paper contains counterexamples illustrating possible outcome.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] The total compute time replicate
all results in this paper less than one CPU-hour.
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A] We only use academic writing, not code with separate license.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]


Reviews:
[{"review_id": "wPo-yeBbV89", "reviewer": "Reviewer_zUeM", "summary": "This paper proposes and analyzes a set of simple counter examples to show that l2 regularization can not mitigate the problems faced value estimation in the deadly triad setting consisting of off-policy learning under function approximation with bootstrap. The authors also analyze emphatic TD approaches and show that l2 regularization on the weight norm is insufficient.\n\n", "questions": "* What is the precise definition of a \"vacuous model\"? Anything that achieves an error worse than the trivial zero-prediction solution? An alternate threshold for vacuity could be the variance of the value function as opposed to the l2 norm. Can the authors make this a bit more clear as this term is repeatedly used through the paper across multiple sections? \n\n* The takeaways from Section 3.4 are a bit unclear. It appears to mainly imply that there are situations where the resulting solution from TD is not useful. What could be more interesting is some evidence that these phenomena can occur with neural nets occur outside of the specific counter examples considered. \n\n* What is the distribution parameter p in Fig 5(a)?  \n\n* Nit: small-eta in L230.", "limitations": "Adequate", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* This is a well written paper with simple but non-trivial examples that demonstrate concretely that l2 regularization can not solve the convergence issues highlighted in the \"deadly triad\" problem in off-policy learning under function approximation.\n\n* The analysis over a range of regularization strengths and comparison against \"vacuous bounds\" helps understand when prior bounds like Eq (9) are not informative.\n\n* The analysis showing how the off-policy distributions can influence the optimum regularization, specifically causing different non-overlapping ranges of $\\eta$ to be necessary for non-vacuous performance seems like a helpful qualitative insight even though it arises out of very specific counter examples. \n\nWeaknesses:\n\n* I'm not sure that there was a widespread belief that regularization necessarily solves the deadly triad, so in that sense the demonstrated phenomenon is not necessarily surprising even if valuable\n\n* The paper is presented as a general study of regularization though the results are specific to l2 weight regularization. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RwZjvughZMA", "reviewer": "Reviewer_cP3d", "summary": "Off-policy RL can be divergent when function approximation and bootstrapping are utilized, and it is commonly believed that $l^2$ regularization prevents divergence in this case. The authors show that there are problems where linear models with any amount of $l^2$ regularization produce worse error than the trivial zero solution does. An analytical and geometric argument is presented, and experiments on linear and nonlinear models demonstrate specific examples in which $l^2$ regularization can increase value-estimation error or lead to divergence.", "questions": "1. In Example 1, how can you guarantee that $\\hat{w}^Tw^*(\\eta) \\leq 0$, $\\forall~\\eta$? Do you have any theoretical results for when a distribution $\\mu$ that causes this either exists or does not exist?\n1. The geometric interpretation of a vacuous model (a trajectory within the halfplane tangent to the $l^2$ ball) makes sense for linear models, but I don’t see why it would necessarily extend to nonlinear (NN) models. Could you elaborate on why you think these results are transferrable?\n1. In Figure 5b, what would happen if you used a NN with more than just 3 neurons in each layer? Would you still expect to see an increase in error for some $\\eta$-values?\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- The paper addresses a fundamental issue in off-policy RL with function approximation, with the potential for significant practical implications. I expect these findings will be of interest to a wide audience of RL researchers.\n- The paper is very well written. There are lots of motivating examples presented in a logical, cohesive flow---almost like reading a chapter of a textbook.\n- The geometric interpretation in Figure 2a was helpful for developing an intuition for the problem addressed by the authors.\n\n**Weaknesses**\n- Overall, I finished reading the paper feeling a lack of clear instruction about “the pitfalls of regularization.” The authors’ general takeaway seems to be that regularization is bad and should be avoided. In reality, the issue seems to be far more nuanced than that. The paper would benefit from further discussion about when regularization is good, too, and what the practical trade-offs may be. For instance, it was not clear to me how pertinent the specific counterexamples in the paper are to off-policy RL in general.\n- I am not totally convinced by the neural network (NN) experiment in Example 4, Figure 5b. The authors claim that their divergence results in the linear approximation case carry over to nonlinear approximation as well, since there are some $\\eta$-values that increase the error of the learned NN value function. In reality, I think this conclusion is based somewhat on the misleading x-axis log scale, and the fact that the y-axis does not start at the origin. To me, it looks like, below $\\eta=10^{-3}$, there is effectively no regularization, and the error is a plateau. If the x-axis were linear, then this region would be essentially negligible. Then, at $\\eta=10^{-3}$, after a short uptick in error, the error starts to decrease rapidly for about two orders of magnitude, before the regularization becomes too strong and starts to worsen again. The takeaway I ultimately got from this graph is that a moderate amount of regularization is actually quite helpful!\n\n**Minor Edits**\n- Line 48: The grammar in this sentence sounds incorrect to me.\n- Line 96: Typo in “regularization.”\n- Line 129: Don’t end a paper section with a colon.\n- Lines 145, 149: I would change the notation “trajectory (1),” since it looks like you are referencing an equation there.\n- Line 195: I think it should be “reweighting,” not “reweighing.”\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RtUBEJYenPf", "reviewer": "Reviewer_NoAj", "summary": "It is well-known that TD methods diverge when used in\nconjunction with value function approximation and off-policy learning.\nSeveral recent works have proposed the use of additional regularization to\nprevent divergence in this setting. This paper provides several counterexamples\ndemonstrating that adding regularization to linear TD methods can lead to\nvacuous value estimates, and that regularization can in fact cause divergence\nin certain settings. Counterexamples are also given for a popular emphatic TD algorithm,\nand for non-linear TD. Taken together, the results suggest that the role of regularization\nbeing proposed by recent works needs reconsideration.\n", "questions": "- Emphatic approaches:\n  - The conclusions in section 3.3 hold only for a specific\n    algorithm, COF-PAC, which simultaneously learns both a\n    value model and emphasis model, but not necessarily to\n    emphatic methods in general; am I understanding this correctly?\n  - Do you expect similar conclusions could hold under more general assumptions\n    on the emphasis model? or is the core problem specifically the *learning* of the emphasis model\n    in parallel with the value model?\n", "limitations": "yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I thought the paper was excellent --- easily the best I reviewed this round of reviews --- and recommend acceptance.\nThe results are novel, thorough, and clearly relevant to\non-going discourse in the community; the\npaper is well-written and the explanations were clear.\nI really only have minor comments and questions, which I provide below.\n\n### Minor Comments\n- Line 266: \"A separate primal-dual saddle point method has also been adapted to $\\ell_2$ regularization,\n  but error bounds at convergence are not yet known\"\n  - I think this may no longer be true; the results in Du et al. (2022) capture\n    the regularized MSPBE as a special case. This paper was posted after the NeurIPS deadline I believe,\n    but I think it is worth revising this sentence. I don't think the existence of such bounds for\n    the $\\ell_2$ regularized MSPBE takes anything away from the results presented here anyways\n- Line 158, typo: $\\xi\\in[0..1]$ should read $\\xi\\in[0,1]$\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5dhVt5HWfFj", "reviewer": "Reviewer_EBcQ", "summary": "This submission is a theoretical paper which investigates a common belief in the community around the problem of the deadly triad: regularization would prevent instability and divergence of TD methods with function approximation in an off-policy setting. This paper provides four counter-examples showing that this is not the case and that l2 regularization can lead to instability and divergence in the context of function approximation and even with neural networks. The paper also shows that emphatic methods can also suffer from these divergence issues. This paper is an invitation to reconsider the use of regularization in off-policy TD learning.\n", "questions": "What are promising solutions to address the issues highlighted in the paper? While regularization can be harmful as the paper shows, itsnt there a tradeoff given it can help in other examples under the same off-policy setting?", "limitations": "There is no dedicated section to limitations. I would say this work highlights issues in the off-policy setting but is limited in terms of practical solutions.\n\n\nPost-rebuttal update:\n\nI want to thank the authors for engaging into this discussion. After carefully reading other reviews, I will update my score to 7 and recommend acceptance.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Contribution**\nThe paper provides interesting new counter-examples showing some issues of TD methods under regularization. I also appreciated the explanatory figures 2, 3, 4 , 5 illustrating the counter examples from the text. \nAs mentioned by the submission, the fact that off-policy TD learning can be unstable or have unbounded error when it converges is already know in the literature but the authors provide a simpler example. The other insights and examples from sections 3.2, 3.3 and 3.4 are new as far as I am aware.\n\nIt would be interesting to understand whether these counter examples could have an impact on current RL algorithms that have been used on common benchmarks, ie are these counter examples extreme situations or can they explain empirical results from past papers?\n\nIn particular, the analysis from section 3.4 is limited to two-layer neural networks and it could be interesting to see if the insights would hold for overparametrized architectures too. This shouldn't prevent acceptance of the paper though. \nOne weakness I see is that given the dynamics of sgd with off-policy TD are unknown it is hard to conclude that the issues highlighted by the paper are a practical issue for current deep rl algorithms. This aspect is briefly mentioned by the authors line 246.\n\n**Organization and Clarity**\nThe paper is overall well-written and well-organized.\nL70 \"error of the zero model\": at this point in the text it is not clear what this means.\nL 122 inconsistencies \\Pi_\\mu vs \\Pi_D: does the representation error depend on the distribution \\mu ? if so, this is the error in the learnt value function and what is the distribution under which the representation error is bounded?\n\n**Related work**\nThe related work seems overall well covered.\n\n**Typos**:\nL 48: as it differently than in supervised settings,\nL107-109: inconsistencies for real numbers \\mathcal{R} , \\mathbb{R}\nL109 : [0..1]\nL253: some training methods / a training method\nL376: to fails", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept