summaries: The paper investigate how optimal recurrent neural networks (RNNs) are at storing past information such that it is useful for predicting the future. The authors estimated optimality in terms of mutual information between the past and the future. If the RNN was able to retain MI between the past and the future, it then has kept optimal information from the past for predicting the future. The experiments suggest that RNNs are not optimal in terms of prediction of the future. It also suggest that this is due to the maximum likelihood training objective.

summaries: This manuscript shows that good ability to compress past information in RNNs help them to predict the future, and that improving upon this ability leads to more useful RNNs. The manuscript first adapts modern mutual-information estimators to mini-batch settings in order to measure the information that an RNN has on the past. It then considers stochastic training, adding Gaussian noise to the hidden states during the training of the RNNs to limit past information. A significant section is dedicated to an empirical study that shows that classically-train MLE RNNs lead to internal representations with a suboptimal mutual-information to the past and the future. For LSTM and GRU architecture, stochastic training actually significantly helps. Experiments on applications such as synthetizing hand-drawn sketches suggest that stochastic training leads to more useful RNNs.

summaries: This paper certainly poses an interesting question: How well do RNNs compress the past while retaining relevant information about the future. In order to quantitatively answer this question, the authors suggest to look at (the optimal solutions of) the Information Bottleneck Lagrangian (IBL). The investigated RNNs need to solve the task of next-step prediction, which can be used to evaluate the IBL. In the paper, the (deterministic) hidden state h is transformed through simple additive Gaussian noise into a stochastic representation which then is utilized to compute the IBL. In general the IBL is not tractable and hence the paper uses approximate computations.

abstractText: Certain biological neurons demonstrate a remarkable capability to optimally compress the history of sensory inputs while being maximally informative about the future. In this work, we investigate if the same can be said of artificial neurons in recurrent neural networks (RNNs) trained with maximum likelihood. In experiments on two datasets, restorative Brownian motion and a hand-drawn sketch dataset, we find that RNNs are sub-optimal in the information plane. Instead of optimally compressing past information, they extract additional information that is not relevant for predicting the future. We show how constraining past information by injecting noise into the hidden state can improve the ability of RNNs to extract predictive information for both maximum likelihood and contrastive loss training.

authors:
D Barber
FV Agakov

title: The IM algorithm: A variational approach to information maximization

venue: In NIPS,

authors:
William Bialek
Ilya Nemenman
Naftali Tishby

title: Predictability, complexity, and learning

venue: Neural computation,

authors:
Gal Chechik
Amir Globerson
Naftali Tishby
Yair Weiss

title: Information bottleneck for gaussian variables

authors:
Kyunghyun Cho
Bart van Merrienboer
Çaglar Gülçehre
Fethi Bougares
Holger Schwenk
Yoshua Bengio

title: Learning phrase representations using RNN encoder-decoder for statistical machine

venue: translation. CoRR,

authors:
Junyoung Chung
Kyle Kastner
Laurent Dinh
Kratarth Goel
Aaron C Courville
Yoshua Bengio

title: A recurrent latent variable model for sequential data

venue: In Advances in neural information processing systems,

authors:
Thomas M Cover
Joy A Thomas

title: Elements of information theory

authors:
Xavier Glorot
Yoshua Bengio

title: Understanding the difficulty of training deep feedforward neural networks

venue: Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics,

authors:
Ian Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron Courville
Yoshua Bengio

title: Generative adversarial nets

venue: In Advances in Neural Information Processing Systems

authors:
David Ha
Douglas Eck

title: A neural representation of sketch drawings

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification

venue: In The IEEE International Conference on Computer Vision (ICCV),

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Long short-term memory

venue: Neural Comput.,

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: In 3rd International Conference on Learning Representations,

authors:
David McAllester
Karl Stratos

title: Formal limitations on the measurement of mutual information, 2019

authors:
Simon F. Nørrelykke
Henrik Flyvbjerg

title: Harmonic oscillator in heat bath: Exact simulation of time-lapse-recorded data and exact analytical benchmark statistics

venue: Phys. Rev. E,

authors:
Aaron van den Oord
Yazhe Li
Oriol Vinyals

title: Representation learning with contrastive predictive coding

venue: arXiv preprint arXiv:1807.03748,

authors:
Stephanie E Palmer
Olivier Marre
Michael J Berry
William Bialek

title: Predictive information in a sensory population

venue: Proceedings of the National Academy of Sciences,

authors:
Ben Poole
Sherjil Ozair
Aaron Van Den Oord
Alex Alemi
George Tucker

title: On variational bounds of mutual information

venue: In International Conference on Machine Learning,

title: On the momentum term in gradient descent learning algorithms

venue: Neural Networks,

authors:
Nitish Srivastava
Geoffrey E. Hinton
Alex Krizhevsky
Ilya Sutskever
Ruslan Salakhutdinov

title: Dropout: a simple way to prevent neural networks from overfitting

authors:
Naftali Tishby
Fernando C.N. Pereira
William Bialek

title: The information bottleneck method

venue: CoRR, physics/0004057,

authors:
Gašper Tkačik
William Bialek

title: Information processing in living systems

venue: Annual Review of Condensed Matter Physics,

title: Attention is all you need

heading: 1 INTRODUCTION

text:
Remembering past events is a critical component of predicting the future and acting in the world. An information-theoretic quantification of how much observing the past can help in predicting the future is given by the predictive information (Bialek et al., 2001). The predictive information is the mutual information (MI) between a finite set of observations (the past of a sequence) and an infinite number of additional draws from the same process (the future of a sequence). As a mutual information, the predictive information gives us a reparameterization independent, symmetric, interpretable measure of the co-dependence of two random variables. More colloquially, the mutual information tells us how many bits we can predict of the future given our observations of the past.1 Asymptotically, a vanishing fraction of the information in the past is relevant to the future (Bialek et al., 2001), thus systems which excel at prediction need not memorize the entire past of a sequence.
Intriguingly, certain biological neurons extract representations that efficiently capture the predictive information in sequential stimuli (Palmer et al., 2015; Tkačik & Bialek, 2016). In Palmer et al. (2015), spiking responses of neurons in salamander retina had near optimal mutual information with the future states of sequential stimuli they were exposed to, while compressing the past as much as possible.
Do our artificial neural networks perform similarly? In this work, we aim to answer this question by measuring artificial recurrent neural networks’ (RNNs) capacity to compress the past while retaining relevant information about the future.
Our contributions are as follows:
• We demonstrate that RNNs are suboptimal at extracting predictive information on the tractable sequential stimuli used in Palmer et al. (2015).
• We thoroughly validate the accuracy of our mutual information estimates on RNNs and optimal models.
• We repeat our analysis on the real-world Aaron Koblin Sheep sketch dataset (Ha & Eck, 2017), demonstrating that deterministic RNNs continue to perform suboptimally.
• We demonstrate that on small datasets, models trained to compress the past have improved sample quality over naively-trained RNNs.
1 Because of its symmetry, this is equivalent to the number of bits we can reconstruct of the past given observations of the future.

heading: 2 BACKGROUND AND METHODS

text: We begin by providing additional background on predictive information, mutual information estimators, stochastic RNNs, and Gaussian Information Bottleneck. These tools are neccessary for accurately evaluating the question of whether RNNs are optimal in the information plane, as we require knowledge of the optimal frontier, and accurate estimates of mutual information for complex RNN models.

heading: 2.1 PREDICTIVE INFORMATION

text:
Imagine an infinite sequence of data: Xt. The predictive information (Bialek et al., 2001) in the sequence is the mutual information between some finite number of observations of the past (T ) and the infinite future of the sequence:
Ipred(T ) = I(Xpast;Xfuture) = I({Xt−T+1, . . . , Xt}; {Xt+1, . . . }). (1)
For a process for which the dynamics are not varying in time, this will be independent of the particular time t chosen to be the present. More specifically, the predictive information is an expected log ratio between the likelihood of observing a future given the past, versus observing that future in expectation over all possible pasts:
Ipred ≡ E [ log
p(xfuture|xpast) p(xfuture)
] = E [ log
p(xfuture|xpast) Ex′past [ p(xfuture|x′past) ]] . (2) A sequential model such as an RNN provides a stochastic representation of the entire past of the sequence Z ∼ p(z|xpast). For any such representation, we can measure how much information it retains about the past, a.k.a. the past information: Ipast = I(Z;Xpast), and how informative it is about the future, a.k.a. the future information: Ifuture = I(Z;Xfuture). Because the representation depends only on the past, our three random variables satisfy the Markov relations: Z ← Xpast ↔ Xfuture and the Data Processing Inequality (Cover & Thomas, 2012) ensures that the information we have about the future is always less than or equal to both the true predictive information of the sequence (Ifuture ≤ Ipred) as well as the information we retain about the past (Ifuture ≤ Ipast). For any particular sequence, there will be a frontier of solutions that optimally tradeoff between Ipast and Ifuture. A common method for tracing out this frontier is through the Information Bottleneck (Tishby et al., 2000) Lagrangian:
min p(z|xpast)
I(Z;Xpast)− βI(Z;Xfuture), (3)
where the parameter β controls the tradeoff. An efficient representation of the past is one that lies on this optimal frontier, or equivalently is a solution to Eqn. 3 for a particular choice of β. For simple problems, where the sequence is jointly Gaussian, we will see that the optimal frontier can be identified analytically.

heading: 2.2 MUTUAL INFORMATION ESTIMATORS

text:
In order to measure whether a representation is efficient, we need a way to measure its past and future informations. While mutual information estimation is difficult in general (McAllester & Stratos, 2019), recent progress has been made on a wide range of variational bounds on mutual information (Poole et al., 2019). While these provide bounds and not exact estimates of mutual information, they allow us to compare mutual information quantities in continuous spaces across models. There are two broad families of estimators: variational lower bounds powered by a tractable generative model, or contrastive lower bounds powered by an unnormalized critic.
The former class of lower bounds, first presented in Barber & Agakov (2003), are powered by a variational generative model:
Ifuture = E [ log
p(xfuture|z) p(xfuture)
] ≥ H(xfuture) + E [log q(xfuture|z)] . (4)
A generative model provides a demonstration that there exists at least some information between the representation z and the future of the sequence. For our purposes, H(xfuture), the entropy of the
future of the sequence is a constant, determined by the dynamics of the sequence itself and outside our control. For tractable problems, such as the toy problem we investigate below, this value is known. For real datasets, this value is not known so that we cannot produce reliable estimates of the mutual information. It does, however, still provide reliable gradients of a lower bound. One example of such a generative model is the loss used to train the RNN to begin with.
Contrastive lower bounds can be used to estimate Ifuture for datasets where building a tractable generative model of the future is challenging. InfoNCE style lower bounds (van den Oord et al., 2018; Poole et al., 2019) only require access to samples from both the joint distribution and the individual marginals:
I(X;Z) ≥ INCE(X;Z) , EpK(x,z)
[ 1
K K∑ i=1 log ef(xi,zi) 1 K ∑K j=1 e f(xj ,zi)
] . (5)
Here f(xj , zi) is a trained critic that plays a role similar to a discriminator in a Generative Adversarial Network (Goodfellow et al., 2014). It scores pairs, attempting to determine if an (x, z) pair came from the joint (p(x, z)) or the factorized marginal distributions (p(x)p(z)).
When forming estimates of Ipast, we can leverage additional knowledge about the known encoding distribution from the stochastic RNN p(z|xpast) to form tractable upper and lower bounds without having to learn an additional critic (Poole et al., 2019):
E
[ 1
K K∑ i=1 log p(zi|xipast) 1 K ∑ j p(z i|xjpast)
] ≤ I(Z;Xpast) ≤ E [ 1
K K∑ i=1 log p(zi|xipast) 1 K−1 ∑ j 6=i p(z i|xjpast)
] . (6)
We refer to these bounds as minibatch upper and lower bounds as they are computed using minibatches of size K from the dataset. As the minibatch size K increases, the upper and lower bounds can become tight. When logK I(Z;Xpast) the lower bound saturates at logK and the upper bound can be loose, thus we require using large batch sizes to form accurate estimates of Ipast.

heading: 2.3 STOCHASTIC RNNS

text: Deterministic RNNs can theoretically encode infinite information about the past in their hidden states (up to floating point precision). To limit past information, we devise a simple stochastic RNN. Given the deterministic hidden state ht, we output a stochastic variable zt by adding i.i.d. Gaussian noise to the hidden state before reading out the outputs: zt ∼ N (ht, σ2). These stochastic outputs are then used to predict the future state: x̂t+1 ∼ N (gdecoder(zt), σ2o), as illustrated in Figure 1. With bounded activation functions on the hidden state ht, we can use σ2 to upper bound the information stored about the past in the stochastic latent zt. This choice of stochastic recurrent model yields a tractable conditional distribution p(zt|x≤t) ∼ N (ht, σ2), which we can use in Eq. 6 to form tractable upper and lower bounds on the past information. We will consider two different settings for our stochastic RNNs: (1) where the RNNs are trained deterministically and the noise on the hidden state is added only at evaluation time, and (2) where the RNNs are trained with noise, and evaluated with noise.

heading: 2.4 GAUSSIAN INFORMATION BOTTLENECK

text:
To evaluate optimality of RNNs, we first focus on the tractable sequential stimuli of a simple Brownian Harmonic Oscillator as used in (Palmer et al., 2015). A crucial property of this dataset is that we can analytically calculate the optimal trade-off between past and future information as it is an instance of the Gaussian Information Bottleneck (Chechik et al., 2005).
Consider jointly multivariate Gaussian random variables X ∈ RDX and Y ∈ RDY , with covariance ΣX and ΣY and cross-covariance ΣXY . The solution to the Information Bottleneck objective:
min T I(X;T )− βI(Y ;T ), (7)
is given by a linear transformation T = AX + ε with ε ∼ N (0,Σε). The projection matrix A projects along the lowest eigenvectors of ΣX|Y Σ −1 X , where the trade-off parameter β decides how many of the eigenvectors participate. Further details can be found in Appendix A.1.

heading: 3 RESULTS

heading: 3.1 BROWNIAN HARMONIC OSCILLATOR

text:
We begin by considering the Brownian harmonic oscillator (BHO) dataset, a form of restorative Brownian motion, as in Palmer et al. (2015). This system has the benefit of having fully tractable
predictive information. The dynamics are given by:
xt+∆t = xt + vt∆t, vt+∆t = [1− Γ∆t]vt − ω2xt∆t+ ξt √ D∆t.
(8)
where ξt is a standard Gaussian random variable. Additional details can be found in Appendix A.2. Examples of the trajectories for this system can be seen in Figure 2a.
Given its analytical tractability we can explicitly compare the estimated RNN performance against optimal performance. We compared three major variants of RNNs, including fully-connected RNNs, gated recurrent units (GRU, Cho et al. (2014)), and LSTMs (Hochreiter & Schmidhuber, 1997). Each network had 32 hidden units and tanh activations. Full training details are in Appendix A.2.
Figure 2 contains the results for both stochastic RNNs and deterministic RNNs with noise added only at evaluation time. By varying the strength of the noise, networks trace out a trajectory on the information plane. We find that networks trained with noise are close to the optimal frontier (black), in terms of optimally extracting information about the past that is useful for predicting the future. While injecting noise at evaluation time produces networks with compressed representations, these deterministically trained networks perform worse than their stochastically trained counterparts.
Training with noise injection can make the networks more efficiently capture the predictive information than post-hoc noise injection. At the same noise level (the color coding in Figure 2) stochastically trained RNNs have both higher I(z;xpast) and higher I(z;xfuture). By limiting the capacity of the models during training, they were able to extract more efficient representations. For this task, we find that more complex RNN variants such as LSTMs are less efficient at encoding predictive information.
Dropout (Srivastava et al., 2014) is a potential alternative way to eliminate information. In Appendix A.5, we demonstrate that RNNs trained with dropout extract less information than the ones trained without dropout, and that our simple noise injection technique can find equivalent models. To access whether the observed sub-optimality was a consequence of our choice of maximum likelihood (MLE) as a training objective, in Appendix A.4 we demonstrate the effect of using contrastive predictive coding (CPC) (Oord et al., 2018) as the training objective. We find that models trained with CPC loss perform similarly to models trained with MLE, as measured on the information plane. However, this may be due to the BHO dataset having Markovian dynamics, and optimizing for onestep-ahead prediction with MLE is sufficient to maximize mutual information with the future of the sequence.

heading: 3.2 ACCURACY OF MUTUAL INFORMATION ESTIMATES

text:
Our claim that RNNs are suboptimal in capturing predictive information hinges on the quality of our MI estimates. Are the RNNs truly suboptimal or is it just that our MI estimates are inaccurate? Here we provide several experiments further validating the accuracy of our MI estimates.
Comparison among estimators. There are many different mutual information estimators. In Figure 3, we compare various mutual information lower bounds with learned critics: InfoNCE, NWJ and JS, as summarized in Poole et al. (2019). NWJ and JS show higher variance and worse bias than InfoNCE. The second panel of Figure 3 demonstrates that InfoNCE outperforms a variational Barber-Agakov style variational lower bound at measuring the future information. Therefore, we adopted InfoNCE as the critic based estimator for the future information in the previous section.
For the past information, we could generate both tractable upper and lower bounds, given our tractable likelihood, p(zt|x≤t ∼ N (ht, σ2). In the third panel of Figure 3 we demonstrate that these bounds become tight as the sample size increases. However they require a large number of samples before they converge. Fundamentally, the lower bound itself is upper-bounded by the log of the number of samples used.
Estimator training with finite dataset. Training the learned critic on finite datasets for a large number of iterations resulted in problematic memorization and overestimates of MI. To counteract the overfitting, we performed early stopping using the MI estimate with the learned critic on a validation set. Unlike the training MI, this is a valid lower bound on the true MI. We then report estimates of mutual information using the learned critic on an independent test set, as Figure 4.
Analytical Agreement As a final and telling justification of the efficiency of our estimators, Figure 5 demonstrates that our estimators accurately estimate the mutual information in our region of interest,
for analytically derived optimal projections. Background for the Gaussian Information Bottleneck is in Section 2.4 and details of the calculation can be found in Appendix A.1.

heading: 3.3 VECTOR DRAWING DATASET

text:
In order to assess whether the sub-optimality of RNNs was an artifact of the BHO dataset, we performed additional experimentson a real world sequential dataset. We used the Aaron Koblin Sheep Sketch Dataset2. Full experimental details are in Appendix A.3. We adopted the SketchRNN architecture and online data augmentation procedure used in Ha & Eck (2017).
Figure 6 (Left) shows the estimates on the information plane for the trained networks. Again, the networks that were trained explicitly with noise dominate on the information plane. For this real world task we no longer know the optimal information tradeoff, but still see that the deterministically trained networks evaluated with noise are demonstrably suboptimal compared to some simple stochastic networks trained with noise injection.
Besides demonstrating sub-optimality in capturing predictive information on the information plane, in Figure 6 (Right), we demonstrate that the deterministic RNNs are wasteful. Networks with higher levels of compression (marked by higher noise levels) were able to obtain similar average test set performance with noticeably lower variance than the deterministic networks. They also show a smaller generalization gap. By explicitly training the networks to operate within some constrained information budget reduced variance between runs without substantially reducing test set performance.
In Figure 7 we show some generated completions from the models trained on the full dataset with varying degrees of noise. The models trained with the highest noise levels show a noticeable degredation in sample quality.

heading: 3.4 SMALL DATASETS

text:
We expect the benefits of training compressed representations to be most marked on limited datasets where the compression can prevent the network from memorizing too many spurious correlations.
To investigate, we repeated the experiments of the previous section with limited dataset with only 100 examples. Figure 8 (Upper Left) shows the corresponding information plane points for stochastically trained RNNs with various noise levels. Notice that at about 4 nats of past information, the networks future information essentially saturates. While it seems as though the networks don’t suffer even when asked to learn richer representations, this is largely an artifact of our training procedure which included early stopping. As can be seen in Figure 8 (Lower Left), all of our networks overfit in terms of evaluation loss, but the onset of overfitting was strongly controlled by the degree of compression.
2Available from https://github.com/hardmaru/sketch-rnn-datasets/tree/master/ aaron_sheep
Most noticeably, in the limited data regime, compressed representations lead to improved sample quality, as seen in Figure 8 (Right). Models with intermediately-sized compressed representations show the best generated samples while retaining a good amount of diversity. Models with either too little or too much past information tend to produce nonsensical generations.

heading: 4 CONCLUSION AND DISCUSSION

text:
In this work, we have demonstrated how analyzing recurrent neural networks in terms of predictive information can be a useful tool in probing and understanding behavior. We find that RNNs trained with maximum likelihood are sub-optimal on the information plane, extracting more information about the past than is required to predict the future. By analyzing different training objectives and noise injection approaches in the information plane, we can better understood the tradeoffs made by different models, and identify models that are closer to the optimality demonstrated by biological neurons (Palmer et al., 2015).
While the simple strategy of adding noise to a bounded hidden state can be used to constrain information, setting the amount of noise and identifying where one should be on the information plane remains an open problem. Additionally, studying the impact of other architecture choices, such as stochastic latent variables in variational RNNs (Chung et al., 2015), or attention-based Transformers (Vaswani et al., 2017) in the information plane could yield insights into their better performance on several tasks.

heading: A APPENDIX

heading: A.1 GAUSSIAN INFORMATION BOTTLENECKS

text:
Consider jointly multivariate Gaussian random variables X ∈ RDX and Y ∈ RDY , with covariance ΣX and ΣY and cross-covariance ΣXY . The solution to the Information Bottleneck objective:
min T I(X;T )− βI(Y ;T ), (9)
is given by a linear transformation T = AX + ε with ε ∼ N (0,Σε). The projection matrix A projects along the lowest eigenvectors λi(i ∈ [1, DX ]) of ΣX|Y Σ−1X , where the trade-off parameter β decides how many of the eigenvectors participate, vTi (i ∈ [1, DX ]). The projection matrix A could be analytically derived as
A = [α1v T 1 , α2v T 2 , . . . , αDXv T DX ], Σε = I (10)
where the projection coefficients α2i = max( β(1−λi)−1 λiri , 0), ri = v T i ΣXvi, with proof in Appendix A.1.1.
Given the optimally projected states T , the optimal frontier (black curve in Figure 5) is:
I(T ;Y ) = I(T ;X)− nI 2 log( nI∏ i=1 (1− λi) 1 nI + e 2I(T ;X) nI nI∏ i=1 λ 1 nI i ), cnI ≤ I(T ;X) ≤ cnI+1 (11)
where nI is the cutoff number indicating the number of smallest eigenvalues being used. The critical points cnI , changing from using nI = N eigenvalues to N + 1 eigenvalues, can be derived given the concave and C1 smoothness property for the optimal frontier, with proof in Appendix A.1.2:
cnI = 1
2 N∑ i=1 log λN+1 λi 1− λi 1− λN+1
(12)

heading: A.1.1 PROOF OF OPTIMAL PROJECTION

text:
By Theorem 3.1 of Chechik et al. (2005), the projection matrix for optimal projection is given by
A =  [ α1v T 1 ,0,0, . . . ,0 ] , 0 ≤ β ≤ β1[ α1v T 1 , α2v T 2 ,0, . . . ,0 ] , β1 ≤ β ≤ β2[ α1v T 1 , α2v T 2 , α2v T 2 , . . . ,0 ] , β2 ≤ β ≤ β3
...  (13) where vTi (i ∈ [1, DX ]) are left eigenvectors of ΣX|Y Σ −1 X sorted in ascending order by the eigenvalues λi(i ∈ [1, DX ]); βi = 11−λi are critical values for trade-off parameter β; and the projection coefficients are α2i = β(1−λi)−1 λiri
, ri = vTi ΣXvi. In practice, noticing that β∗(1−λi)−1 < 0 when β < βi, we simplify Equation (13) as A = [α1vT1 , α2v T 2 , . . . , αDXv T DX ] with α2i = max( β(1−λi)−1 λiri , 0).

heading: A.1.2 PROOF OF CRITICAL POINTS ON OPTIMAL FRONTIER

text:
By Eq.15 of Chechik et al. (2005)
I(T ;Y ) = I(T ;X)− nI 2 log( nI∏ i=1 (1− λi) 1 nI + e 2I(T ;X) nI nI∏ i=1 λ 1 nI i ) (14)
where nI is the cutoff on the number of eigenvalues used to compute the bound segment, with eigenvalues sorted in ascending order.
In order to calculate the changing point, where one switching from choosing nI = N to N + 1, by C1 smoothness conditions:
dInI=N (T ;Y )
dI(T ;X) =
dInI=N+1(T ;Y )
dI(T ;X) (15)
LHS is
1− dInI=N (T ;Y ) dI(T ;X) =
N∏ i=1 (λi) 1 N e 2I(T ;X) N
N∏ i=1 (1− λi) 1 N + e 2I(T ;X) nI N∏ i=1 λ 1 N i
(16)
= e
2I(T ;X) N
e 2I(T ;X) N + N∏ i=1 ( 1−λiλi ) 1 N
(17)
Thus, Equation (15) could be rewritten as
e 2I(T ;X) N
e 2I(T ;X) N + N∏ i=1 ( 1−λiλi ) 1 N = e
2I(T ;X) N+1
e 2I(T ;X) N+1 + N+1∏ i=1 ( 1−λiλi ) 1 N+1
(18)
Rewrite RHS of above equation, and noticing 1n(n+1) = 1 n − 1 n+1
e 2I(T ;X) N+1
e 2I(T ;X) N+1 + N+1∏ i=1 ( 1−λiλi ) 1 N+1 = e
2I(T ;X) N
e 2I(T ;X) N + e 2I(T ;X) N(N+1) N+1∏ i=1 ( 1−λiλi ) 1 N+1
(19)
The term in lower right corner could be written as
N+1∏ i=1 ( 1− λi λi ) 1 N+1 = N∏ i=1 ( 1− λi λi ) 1 N+1 ( 1− λN+1 λN+1 ) 1 N+1 (20)
= ( N∏ i=1 ( 1− λi λi ) 1 N N∏ i=1 ( λi 1− λi ) 1 N(N+1) ) ( 1− λN+1 λN+1 ) N (N+1)N (21)
= ( N∏ i=1 ( 1− λi λi ) 1 N )( N∏ i=1 ( λi(1− λN+1) (1− λi)λN+1 ) 1 N(N+1) ) (22)
Putting RHS together
e 2I(T ;X) N
e 2I(T ;X) N + N∏ i=1 ( 1−λiλi ) 1 N = e
2I(T ;X) N
e 2I(T ;X) N + e 2I(T ;X) N(N+1) ( N∏ i=1 ( 1−λiλi ) 1 N )( N∏ i=1 ( λi(1−λN+1) (1−λi)λN+1 ) 1 N(N+1) ) (23)
To let LHS = RHS, one trivial solution is
1 = e 2I(T ;X) N(N+1) ( N∏ i=1 ( λi(1− λN+1) (1− λi)λN+1 ) 1 N(N+1) ) (24)
Taking log and cancelling out multiplicative factors, one get the critic point to change from ni = N to ni = N + 1 happens at
I(T ;X) = 1
2 N∑ i=1 log λN+1 λi 1− λi 1− λN+1
(25)
The original result written in Chechik et al. (2005) missing a factor of 12 .

heading: A.1.3 OPTIMAL PROJECTION

text: The optimal frontier is generated by joining segments described by Equation (11), as illustrated in Figure 9.

heading: A.2 DETAILS FOR BROWNIAN HARMONIC OSCILLATOR

text:
To generate the sample trajectories, we set the undamped angular velocity ω = 1.5 × 2π(rad), damping coefficient Γ = 20.0, and the dynamical range of external forces D = 1000.0, with integration time step-size ∆t = 0.01667. The stationary distribution of Equation (8) is analytically derived in Nørrelykke & Flyvbjerg (2011).
We train RNNs with infinite number of training samples, which are generated online and divided into batches of 32 sequences. RNNs, including fully connected RNN, GRU and LSTM, are all with 32 hidden units and tanh activation. They are trained with momentum optimizer (Qian, 1999) for 20000 steps, with momentum = 0.9 and gradient norm being clipped at 5.0. Learning rate for training is exponentially decayed in a stair-case fashion, with initial learning rate 10−4, decay rate 0.9 and decay steps 2000.
The mutual information estimators, with learned critics, are trained for 200000 steps with Adam optimizer (Kingma & Ba, 2015) at a flat learning rate of 10−3. The training batch size is 256, and the validation and evaluation batch sizes are 2048. We use early stopping to deal with overfitting. The training is stopped when the estimation on validation set does not improve for 10000 steps, or when it drops by 3.0 from its highest level, whichever comes first. We use separable critics (Poole et al., 2019) for training the estimators. Each of the critics is a three-layer MLP, with [256, 256, 32] hidden units and [ReLU, ReLU, None] activations. The weights for each layer are initialized with Glorot uniform initializer (Glorot & Bengio, 2010), and the biases are with He normal initializer (He et al., 2015). For the minibatch upper and lower bounds, they are estimated on batches of 4096 sequences.
To train the critics, we feed 100-step BHO sequences into trained RNN to get RNN hidden states and conditional distribution parameters. From each sequence, we use last 36 steps for the inputs to the estimators, where first 18 steps as xpast[t], t = [1, 2, . . . 18], and the other 18 steps as xfuture[t], t = [19, 20, . . . 36]. The hidde state z18 is extracted at the last time step of xpast.

heading: A.3 TRAINING DETAILS FOR VECTOR DRAWING DATASET

text:
We train decoder-only SketchRNN (Ha & Eck, 2017) on Aaron Koblin Sheep Dataset, as provided in https://github.com/hardmaru/sketch-rnn-datasets/tree/master/ aaron_sheep. The SketchRNN uses LSTM as its RNN cell, with 512 hidden units.
For RNN training, We adopt the identical hyper-parameters as in https://github.com/ tensorflow/magenta/blob/master/magenta/models/sketch_rnn/model.py, except that we turn off the recurrent drop-out, since drop-out masks out informations and will interfere with noise injection.
For mutual information estimations, we use the identical hyper-parameters as descibed in Appendix A.2, except that: the evaluation batch size for critic based estimator, InfoNCE, is set to be 4096, and 16384 for minibatch bounds; early stopping criteria are changed to that either the estimation does not improve for 20000 steps or drops by 10.0 from its highest level, whichever comes first.
Due to the limitation of the sequence length of Aaron’s Sheep, we use the samples with at least 36 steps long. The xpast and xfuture are split at the middle of the sequences, and each with 18 steps.
Due to the limitation of the dataset size of Aaron’s Sheep, we augment the dataset with randomly scale the stroke by a factor sampled from N (0, 0.15) for each sequence to generate a large dataset. Figure 4 (Right) shows that the augmentation helps in training the estimator.

heading: A.4 EFFECT OF CHANGING TRAINING OBJECTIVES: MAXIMUM LIKELIHOOD AND CONTRASTIVE LOSS TRAINING

text:
To access whether the observed suboptimality in the information plane was due to the maximum likelihood (MLE) objective itself, we additionally trained constrastive predictive coding (CPC) models (Oord et al., 2018). We used the identical model architecture as described in the Section 2.3. The CPC loss lower bounds the mutual information between the current time step and K steps into the future. For our experiments on the Brownian harmonic oscillator (BHO), we look into K = 30 steps future, and use a linear readout from the hidden states to a time-independent embedding of the
inputs. As shown in Figure 10, we found that models trained with CPC loss had similar frontiers as those trained with MLE. The loss function does not appear to have a substantive effect.

heading: A.5 EFFECT OF DROPOUT

text: Dropout (Srivastava et al., 2014) is a common method applied on neural network training to prevent overfitting. We trained fully connected RNNs and LSTMs with different levels of dropout probability. As shown in Figure 11, we find that RNNs trained with dropout extract less information than the ones without it, but the information frontier of the models does not change, when we sweep dropout rate and additive noise. In other words, we can find models that are equivalent to dropout models by simply adding Gaussian noise to the output at training time.


summaries: A recent paper by Lu et al introduced delusional bias in Q-learning, an error due to the max in the Bellman backup not being consistent with the policy representation implied by the greedy operator applied to the approximated value function. That work proposed a consistent algorithm for small and finite state spaces, which essentially enumerates over realizable policies. This paper proposes an algorithm for overcoming delusional bias in large state spaces. The idea is to add to the Q-learning objective a smooth penalty term that induces approximate consistency, and search over possible Q-function approximators. Several heuristic methods are proposed for this search, and results are demonstrated in Atari domains.

summaries: This paper presents a solution to tackling the problem of delusional bias in Deep Q-learning, building upon Lu et.al. (NeuRIPS 2018).  Delusional bias arises because independently choosing maximizing actions at a state may be inconsistent as the backed-up values may not be realizable by any policy. They encourage non-delusional Q-functions by adding a penalty term that enforces that the max_a in Q-learning chooses actions that do not give rise to actions outside the realizable policy class. Further, in order to keep track of all consistent assignments, they pose a search problem and propose heuristics to approximately perform this search. The heuristics are based on sampling using exponentiated Q-values and scoring possible children using scores like Bellman error, and returns of the greedy policy. Their final algorithm is evaluated on a DQN and DDQN, where they observe some improvement from both components (consistency penalty and approximate search).

summaries: This paper focuses on addressing the delusional bias problem in deep Q-learning, and propose a general framework (ConQUR) for integrating policy-consistent backups with regression-based function approximation for Q-learning and for managing the search through the space of possible regressors. Specifically, it proposes a soft consistency penalty to alleviate the delusional bias problem while avoiding the expensive exact consistency testing. This penalty encourages the parameters of the model to satisfy the consistency condition when solving the MSBE problem.

abstractText: Delusional bias is a fundamental source of error in approximate Q-learning. To date, the only techniques that explicitly address delusion require comprehensive search using tabular value estimates. In this paper, we develop efficient methods to mitigate delusional bias by training Q-approximators with labels that are “consistent” with the underlying greedy policy class. We introduce a simple penalization scheme that encourages Q-labels used across training batches to remain (jointly) consistent with the expressible policy class. We also propose a search framework that allows multiple Q-approximators to be generated and tracked, thus mitigating the effect of premature (implicit) policy commitments. Experimental results demonstrate that these methods can improve the performance of Q-learning in a variety of Atari games, sometimes dramatically.

authors:
Oron Anschel
Nir Baram
Nahum Shimkin

title: Averaged-dqn: Variance reduction and stabilization for deep reinforcement learning

title: Residual algorithms: Reinforcement learning with function approximation

venue: In Proceedings of the International Conference on Machine Learning

authors:
M.G. Bellemare
Y. Naddaf
J. Veness
M. Bowling

title: The arcade learning environment: An evaluation platform for general agents

venue: Journal of Artificial Intelligence Research,

authors:
Marc Bellemare
Will Dabney
Remi Munos

title: A distributional perspective on reinforcement learning

authors:
Justin A. Boyan
Andrew W. Moore

title: Generalization in reinforcement learning: Safely approximating the value function

venue: Advances in Neural Information Processing Systems

authors:
Edoardo Conti
Vashisht Madhavan
Felipe Petroski Such
Joel Lehman
Kenneth O. Stanley
Jeff Clune

title: Improving exploration in evolution strategies for deep reinforcement learning via a population of novelty-seeking agents

authors:
Damien Ernst
Pierre Geurts
Louis Wehenkel

title: Tree-based batch mode reinforcement learning

venue: Journal of Machine Learning Research,

authors:
Stefan Faußer
Friedhelm Schwenker

title: Neural network ensembles in reinforcement learning

venue: Neural Processing Letters,

title: Approximation Solutions to Markov Decision Problems

venue: PhD thesis,

title: Stable function approximation in dynamic programming

venue: In Proceedings of the Twelfth International Conference on Machine Learning

authors:
Sergio Guadarrama
Anoop Korattikara
Pablo Castro Oscar Ramirez
Ethan Holly
Sam Fishman
Ke Wang
Ekaterina Gonina
Neal Wu
Chris Harris
Vincent Vanhoucke
Eugene Brevdo

title: TF-Agents: A library for reinforcement learning in tensorflow

venue: https://github.com/ tensorflow/agents,

authors:
Hado van Hasselt
Arthur Guez
David Silver

title: Deep reinforcement learning with double q-learning

venue: In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence,

authors:
Matteo Hessel
Joseph Modayil
Hado van Hasselt
Tom Schaul
Georg Ostrovski
Will Dabney
Dan Horgan
Bilal Piot
Mohammad Azar
David Silver

title: Rainbow: Combining improvements in deep reinforcement learning

authors:
Shauharda Khadka
Kagan Tumer

title: Evolution-guided policy gradient in reinforcement learning

authors:
Tyler Lu
Dale Schuurmans
Craig Boutilier

title: Non-delusional Q-learning and value iteration

authors:
Hamid Maei
Csaba Szepesvári
Shalabh Bhatnagar
Richard Sutton

title: Toward off-policy learning control wtih function approximation

venue: In International Conference on Machine Learning, Haifa, Israel,

authors:
Francisco Melo
M. Isabel Ribeiro

title: Q-learning with linear function approximation

venue: In Proceedings of the International Conference on Computational Learning Theory (COLT),

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei Rusu
Joel Veness
Marc Bellemare
Alex Graves
Martin Riedmiller
Andreas Fidjeland
Georg Ostrovski
Stig Petersen
Charles Beattie
Amir Sadik
Ioannis Antonoglou
Helen King
Dharshan Kumaran
Daan Wierstra
Shane Legg
Demis Hassabis

title: Human-level control through deep reinforcement learning

authors:
Remi Munos
Thomas Stepleton
Anna Harutyunyan
Marc Bellemare

title: Safe and efficient off-policy reinforcement learning

authors:
Ian Osband
Charles Blundell
Alexander Pritzel
Benjamin Van Roy

title: Deep exploration via bootstrapped dqn

title: Neural fitted q iteration—first experiences with a data efficient neural reinforcement learning method

venue: In Proceedings of the 16th European Conference on Machine Learning,

authors:
David Silver
Aja Huang
Chris J Maddison
Arthur Guez
Laurent Sifre
George Van Den Driessche
Julian Schrittwieser
Ioannis Antonoglou
Veda Panneershelvam
Marc Lanctot

title: Mastering the game of Go with deep neural networks and tree

venue: search. Nature,

authors:
Richard S. Sutton
Andrew G. Barto

title: Reinforcement Learning: An Introduction

authors:
Csaba Szepesvári
William Smart

title: Interpolation-based Q-learning

authors:
John H. Tsitsiklis
Benjamin Van Roy

title: An analysis of temporal-difference learning with function approximation

venue: IEEE Transactions on Automatic Control,

title: Statistical Learning Theory

authors:
Ziyu Wang
Tom Schaul
Matteo Hessel
Hado van Hasselt
Marc Lanctot
Nando de Freitas

title: Dueling network architectures for deep reinforcement learning

title: Learning from Delayed Rewards

venue: PhD thesis, King’s College,

venue: We describe an example,

heading: 1 INTRODUCTION

text:
Q-learning (Watkins & Dayan, 1992; Sutton & Barto, 2018) lies at the heart of many of the recent successes of deep reinforcement learning (RL) (Mnih et al., 2015; Silver et al., 2016), with recent advancements (e.g., van Hasselt (2010); Bellemare et al. (2017); Wang et al. (2016); Hessel et al. (2017)) helping to make it among the most widely used methods in applied RL. Despite these successes, many properties of Q-learning are poorly understood, and it is challenging to successfully apply deep Q-learning in practice. When combined with function approximation, Q-learning can become unstable (Baird, 1995; Boyan & Moore, 1995; Tsitsiklis & Roy, 1996; Sutton & Barto, 2018). Various modifications have been proposed to improve convergence or approximation error (Gordon, 1995; 1999; Szepesvári & Smart, 2004; Melo & Ribeiro, 2007; Maei et al., 2010; Munos et al., 2016); but it remains difficult to reliably attain both robustness and scalability.
Recently, Lu et al. (2018) identified a source of error in Q-learning with function approximation known as delusional bias. It arises because Q-learning updates the value of state-action pairs using estimates of (sampled) successor-state values that can be mutually inconsistent given the policy class induced by the approximator. This can result in unbounded approximation error, divergence, policy cycling, and other undesirable behavior. To handle delusion, the authors propose a policy-consistent backup operator that maintains multiple Q-value estimates organized into information sets. Each information set has its own backed-up Q-values and corresponding “policy commitments” responsible for inducing these values. Systematic management of these sets ensures that only consistent choices of maximizing actions are used to update Q-values. All potential solutions are tracked to prevent premature convergence on any specific policy commitments. Unfortunately, the proposed algorithms use tabular representations of Q-functions, so while this establishes foundations for delusional bias, the function approximator is used neither for generalization nor to manage the size of the state/action space. Consequently, this approach is not scalable to RL problems of practical size.
In this work, we propose CONQUR (CONsistent Q-Update Regression), a general framework for integrating policy-consistent backups with regression-based function approximation for Q-learning and for managing the search through the space of possible regressors (i.e., information sets). With suitable search heuristics, our framework provides a computationally effective means for minimizing the effects of delusional bias in Q-learning, while admitting scaling to practical problems.
Our main contributions are as follows. First we define novel augmentations of standard Q-regression to increase the degree of policy consistency across training batches. While testing exact consistency
is expensive, we introduce an efficient soft-consistency penalty that promotes consistency of new labels with earlier policy commitments. Second, drawing on the information-set structure of Lu et al. (2018), we define a search space over Q-regressors to allow consideration of multiple sets of policy commitments. Third, we introduce heuristics for guiding the search over regressors, which is critical given the combinatorial nature of information sets. Finally, we provide experimental results on the Atari suite (Bellemare et al., 2013) demonstrating that CONQUR can offer (sometimes dramatic) improvements over Q-learning. We also show that (easy-to-implement) consistency penalization on its own (i.e., without search) can improve over both standard and double Q-learning.

heading: 2 BACKGROUND

text:
We assume a discounted, infinite horizon Markov decision process (MDP), M = (S, A, P, p0, R, γ). The state space S can reflect both discrete and continuous features, but we take the action space A to be finite (and practically enumerable). We consider Q-learning with a function approximator Qθ to learn an (approximately) optimal Q-function (Watkins, 1989; Sutton & Barto, 2018), drawn from some approximation class parameterized by Θ (e.g., the weights of a neural network). When the approximator is a deep network, we generically refer to the algorithm as DQN, the method at the heart of many recent RL successes (Mnih et al., 2015; Silver et al., 2016).
For online Q-learning, at a transition s, a, r, s′, the Q-update is given by: θ ← θ + α ( r + γmax
a′∈A Qθ(s
′, a′)−Qθ(s, a) ) ∇θQθ(s, a). (1)
Batch versions of Q-learning, including DQN, are similar, but fit a regressor repeatedly to batches of training examples (Ernst et al., 2005; Riedmiller, 2005). Batch methods are usually more data efficient and stable than online Q-learning. Abstractly, batch Q-learning works through a sequence of (possibly randomized) data batches D1, · · ·DT to produce a sequence of regressors Qθ1 , . . . , QθT = Qθ, estimating the Q-function.1 For each (s, a, r, s′) ∈ Dk, we use a prior estimator Qθk−1 to bootstrap the Q-label q = r + γmaxa′ Qθk−1(s
′, a′). We then fit Qθk to this training data using a suitable regression procedure with an appropriate loss function. Once trained, the (implicit) induced policy πθ is the greedy policy w.r.t. Qθ, i.e., πθ(s) = arg maxa∈AQθ(s, a). Let F(Θ), resp. G(Θ), be the corresponding class of expressible Q-functions, resp. greedy policies.
Intuitively, delusional bias occurs whenever a backed-up value estimate is derived from action choices that are not (jointly) realizable in G(Θ) (Lu et al., 2018). Standard Q-updates back up values for each (s, a) pair by independently choosing maximizing actions at the corresponding next states s′. However, such updates may be “inconsistent” under approximation: if no policy in G(Θ) can jointly express all past action choices, backed up values may not be realizable by any expressible policy. Lu et al. (2018) show that delusion can manifest itself with several undesirable consequences. Most critically, it can prevent Q-learning from learning the optimal representable policy in G(Θ); it can also cause divergence. To address this, they propose a non-delusional policy consistent Q-learning (PCQL) algorithm that provably eliminates delusion. We refer to the original paper for details, but review the main concepts we need to consider below.
The first key concept is that of policy consistency. For any S ⊆ S , an action assignment σS : S → A associates an action σ(s) with each s ∈ S. We say σ is policy consistent if there is a greedy policy π ∈ G(Θ) s.t. π(s) = σ(s) for all s ∈ S. We sometimes equate a set SA of state-action pairs with an implied assignment π(s) = a for all (s, a) ∈ SA. If SA contains multiple pairs with the same state s, but different actions a, it is a multi-assignment (though we loosely use the term “assignment” in both cases when there is no risk of confusion).
In (batch) Q-learning, each successive regressor uses training labels generated by assuming maximizing actions (under the prior regressor) are taken at its successor states. Let σk reflect the collection of states and corresponding maximizing actions taken to generate labels for regressor Qθk (assume it is policy consistent). Suppose we train Qθk by bootstrapping on Qθk−1 and consider a training sample (s, a, r, s′). Q-learning generates label r + γmaxa′ Qθk−1(s ′, a′) for input (s, a). Notice,
1We describe our approach using a straightforward form of batch Q-learning, but it can accommodate many variants, e.g., where the regressor used for bootstrapping is some earlier Q-estimator, or the estimators generating the max-actions and the value estimates are different as in double Q-learning (van Hasselt, 2010; Hasselt et al., 2016); indeed, we experiment with such variants.
however, that taking action a∗ = argmaxa′ Qθk(s ′, a′) at s′ may not be policy consistent with σk. Thus Q-learning will estimate a value for (s, a) assuming the execution of a policy that cannot be realized given the limitations of the approximator. The PCQL algorithm (Lu et al., 2018) prevents this by insisting that any action assignment σ used to generate bootstrapped labels is consistent with earlier assignments. Notice that this means Q-labels will often not be generated using maximizing actions relative to the prior regressor.
The second key concept is that of information sets. One will generally not be able to use maximizing actions to generate labels, so tradeoffs can be made when deciding which actions to assign to different states. Indeed, even if it is feasible to assign a maximizing action a to state s early in training, say at batch k, since it may prevent assigning a maximizing a′ to s′ later, say batch k + `, we may want to consider a different assignment to s to give more flexibility to maximize at other states later. PCQL doesn’t try to anticipate the tradeoffs—rather it maintains multiple information sets, each corresponding to a different assignment to the states seen in the training data so far. Each gives rise to a different Q-function estimate, resulting in multiple hypotheses. At the end of training, the best hypothesis is the one maximizing expected value w.r.t. an initial state distribution.
PCQL provides strong convergence guarantees, but it is a tabular algorithm: the function approximator retricts the policy class, but is not used to generalize Q-values. Furthermore, its theoretical guarantees come at a cost: it uses exact policy consistency tests—tractable for linear approximators, but not practical for large problems; and it maintains all consistent assignments. As a result, PCQL cannot be used for large RL problems of the type tackled by DQN.

heading: 3 THE CONQUR FRAMEWORK

text: We develop the CONQUR framework to provide a practical approach to reducing delusion in Qlearning, specifically addressing the limitations of PCQL identified above. CONQUR consists of three main components: a practical soft-constraint penalty that promotes policy consistency; a search space to structure the search over multiple regressors (information sets, action assignments); and heuristic search schemes (expansion, scoring) to find good Q-regressors.

heading: 3.1 PRELIMINARIES

text:
We assume a set of training data consisting of quadruples (s, a, r, s′), divided into (possibly nondisjoint) batches D1, . . . DT for training. This perspective is quite general: online RL corresponds to |Di| = 1; off-line batch training (with sufficiently exploratory data) corresponds to a single batch (i.e., T = 1); and online or batch methods with replay are realized when the Di are generated by sampling some data source with replacement.
For any data batch D, let χ(D) = {s′ : (s, a, r, s′) ∈ D} denote the collection of successor states of D. An action assignment σD for D is an assignment (or multi-assignment) from χ(D) to A: this dictates which action σD(s′) is considered “maximum” for the purpose of generating a Q-label for pair (s, a); i.e., (s, a) will be assigned training label r + γQ(s′, σ(s′)) rather than r + γmaxa′∈AQ(s
′, a′). The set of all such assignments is Σ(D) = Aχ(D); note that it grows exponentially with |D|. Given Q-function parameterization Θ, we say σD is Θ-consistent (w.r.t. D) if there is some θ ∈ Θ s.t. πθ(s′) = σ(s′) for all s′ ∈ χ(D).2 This is simple policy consistency, but with notation that emphasizes the policy class. Let ΣΘ(D) denote the set of all Θ-consistent assignments over D. The union σ1 ∪ σ2 of two assignments (over D1, D2, resp.) is defined in the usual way.

heading: 3.2 CONSISTENCY PENALIZATION

text:
Enforcing strict Θ-consistency as regressors θ1, θ2, . . . , θT are generated is computationally challenging. Suppose assignments σ1, . . . , σk−1, used to generate labels for D1, . . . Dk−1, are jointly Θ-consistent (let σ≤k−1 denote their multi-set union). Maintaining Θ-consistency when generating θk imposes two requirements. First, one must generate an assignment σk over Dk s.t. σ≤k−1 ∪ σk is consistent. Even testing assignment consistency can be problematic: for linear approximators this is a
2We suppress mention of D when clear from context or implied by the assignment under consideration.
linear feasibility program (Lu et al., 2018) whose constraint set grows linearly with |D1 ∪ . . . ∪Dk|. For DNNs, this is a complex, and much more expensive, polynomial program. Second, the regressor θk should itself be consistent with σ≤k−1 ∪ σk. Again, this imposes a significant constraint on the regression optimization: in the linear case, this becomes a constrained least-squares problem (solvable, e.g., as a quadratic program); while with DNNs, it could be solved, say, using a much more complicated projected SGD. However, the sheer number of constraints makes this impractical.
Rather than enforcing consistency, we propose a simple, computationally tractable scheme that “encourages” it: a penalty term that can be incorporated into the regression itself. Specifically, we add a penalty function to the usual squared loss to encourage updates of the Q-regressors to be consistent with the underlying information set, i.e., the prior action assignments used to generate its labels.
When constructing θk, let D≤k = ∪{Dj : j ≤ k}, and σ ∈ ΣΘ(D≤k) be the collective (possibly multi-) assignment used to generate labels for all prior regressors (including θk itself). The multiset of pairs B = {(s′, σ(s′))|s′ ∈ χ(D≤k)}, is called a consistency buffer. The collective assignment need not be consistent (as we elaborate below), nor does the regressor θk need to be consistent with σ. Instead, we incorporate the following soft consistency penalty when constructing θk:
Cθ(s ′, a) = ∑ a′∈A [Qθ(s ′, a′)−Qθ(s′, a)]+ Cθ(B) = ∑ (s′,σ(s′))∈B Cθ(s ′, σ(s′)),
where [x]+ = max(0, x). This penalizes Q-values of actions at state s that are larger than that of action σ(s). We note that σ is Θ-consistent if and only if minθ∈Θ Cθ(B) = 0. We incorporate this penalty into our regression loss for batch Dk:
Lθ(Dk, B) = ∑
(s,a,r,s′)∈Dk
[r + γQθk−1(s ′, σ(s′))−Qθ(s, a)]2 + λCθ(B). (2)
Here Qθk is prior estimator on which labels are bootstrapped (other prior regressors may be used). The penalty effectively acts as a “regularizer” on the squared Bellman error, where λ controls the degree of penalization, allowing a tradeoff between Bellman error and consistency with the action assignment used to generate labels. It thus promotes consistency without incurring the expense of testing strict consistency. It is a simple matter to replace the classical Q-learning update (1) with one using a consistency penalty:
θk ← θk−1 +  ∑ (s,a,r,s′)∈Dk α[r + γQθk−1(s ′, σ(s′))−Qθ(s, a)]∇θQθ(s, a)  + αλ∇θCθ(B) ∣∣∣ θ=θk−1 . (3)
This scheme is quite general. First, it is agnostic as to how the prior action assignments are made, which can be the standard maximizing action at each stage w.r.t. the prior regressor like in DQN, Double DQN (DDQN) (Hasselt et al., 2016), or other variants. It can also be used in conjunction with a search through alternate assignments (see below).
Second, the consistency buffer B may be populated in a variety of ways. Including all max-action choices from all past training batches promotes full consistency in an attempt to minimize delusion. However, this may be too constraining since action choices early in training are generally informed by very inaccurate value estimates. Hence, B may be implemented in other ways to focus only on more recent data (e.g., with a sliding recency window, weight decay, or subsampling); and the degree of recency bias may adapt during training (e.g., becoming more inclusive as training proceeds and the Q-function approaches convergence). Reducing the size of B also has various computational benefits. We discuss other practical means of promoting consistency in Sec. 5.
The proposed consistency penalty resembles the temporal-consistency loss of Pohlen et al. (2018), but our aims are very different. Their temporal consistency notion penalizes changes in a next state’s Q-estimate over all actions, whereas we discourage inconsistencies in the greedy policy induced by the Q-estimator, regardless of the actual estimated values.

heading: 3.3 THE SEARCH SPACE

text:
Ensuring optimality requires that PCQL track all Θ-consistent assignments. While the set of such assignments is shown to be of polynomial size (Lu et al., 2018), it is still impractical to track this set in realistic problems. As such, in CONQUR we recast information set tracking as a search problem and propose several strategies for managing the search process. We begin by defining the search space and discussing its properties. We discuss search procedures in Sec. 3.4.
As above, assume training data is divided into batches D1, . . . DT and we have some initial Qfunction estimate θ0 (for bootstrapping D1’s labels). The regressor θk for Dk can, in principle, be trained with labels generated by any assignment σ ∈ ΣΘ(Dk) of actions to its successor states χ(Dk), not necessarily maximizing actions w.r.t. θk−1. Each σ gives rise to a different updated Q-estimator θk. There are several restrictions we could place on “reasonable” σ-candidates: (i) σ is Θ-consistent; (ii) σ is jointly Θ-consistent with all σj , for j < k, used to construct the prior regressors on which we bootstrap θk−1; (iii) σ is not dominated by any σ′ ∈ ΣΘ(Dk), where we say σ′ dominates σ if Qθk−1(s
′, σ′(s′)) ≥ Qθk−1(s′, σ(s′)) for all s′ ∈ χ(D), and this inequality is strict for at least one s′. Conditions (i) and (ii) are the strict consistency requirements of PCQL. We will, however, relax these below for reasons discussed in Sec. 3.2. Condition (iii) is inappropriate in general, since we may add additional assignments (e.g., to new data) that render all non-dominated assignments inconsistent, requiring that we revert to some dominated assignment.
This gives us a generic search space for finding policy-consistent, delusion-free Q-function, as illustrated in Fig. 1. Each node nik at depth k in the search tree is associated with a regressor θ i k defining Qθik and action assignment σ i k that justifies the labels used to train θ i k (σ i k can also be viewed as an information set). We assume the root n0 is based on an initial regression θ0, and has an empty action assignment σ0. Nodes at level k of the tree are defined as follows. For each node nik−1 at level k − 1—with regressor θik−1 and Θ-consistent assignment σik−1—we generate a child n j k for each σjk ∈ ΣΘ(Dk) such that σik−1 ∪ σ j k is Θ-consistent. Node n j k’s assignment is σ i k−1 ∪ σ j k, and its regressor θik is trained using the following data set:
{(s, a) 7→ r + γQθik−1(s ′, σjk(s ′)) : (s, a, r, s′) ∈ Dk}.
The entire search space constructed in this fashion to a maximum depth of T . See Appendix B, Algorithm 1 for pseudocode of a simple depth-first recursive specification.
The exponential branching factor in this search tree would appear to make complete search intractable; however, since we only allow Θ-consistent “collective” assignments we can bound the size of the tree—it is polynomial in the VC-dimension of the approximator.
Theorem 1. The number of nodes in the search tree is no more than O(nm · [ ( m 2 ) n]VCDim(G)) where VCDim(·) is the VC-dimension (Vapnik, 1998) of a set of boolean-valued functions, and G is the set of boolean functions defining all feasible greedy policies under Θ:
G = {gθ(s, a, a′) := 1[fθ(s, a)− fθ(s, a′) > 0],∀s, a 6= a′ | θ ∈ Θ}. (4)
A linear approximator with a fixed set of d features induces a policy-indicator function class G with VC-dimension d, making the search tree polynomial in the size of the MDP. Similarly, a fixed ReLU
DNN architecture with W weights and L layers has VC-dimension of size O(WL logW ) again rendering the tree polynomially sized.
Even with this bound, navigating the search space exhaustively is generally impractical. Instead, various search methods can be used to explore the space, with the aim of reaching a “high quality” regressor at some leaf of the tree (i.e., trained using all T data sets/batches). We discuss several key considerations in the next subsection.

heading: 3.4 SEARCH HEURISTICS

text:
Even with the bound in Theorem 1, traversing the search space exhaustively is generally impractical. Moreover, as discussed above, enforcing consistency when generating the children of a node, and their regressors, may be intractable. Instead, various search methods can be used to explore the space, with the aim of reaching a “high quality” regressor at some (depth T ) leaf of the tree. We outline three primary considerations in the search process: child generation, node evaluation or scoring, and the search procedure.
Generating children. Given node nik−1, there are, in principle, exponentially many action assignments, or children, ΣΘ(Dk) (though Theorem 1 significantly limits the number of children if we enforce consistency). For this reason, we consider heuristics for generating a small set of children. Three primary factors drive these heuristics.
The first factor is a preference for generating high-value assignments. To accurately reflect the intent of (sampled) Bellman backups, we prefer to assign actions to state s′ ∈ χ(Dk) with larger predicted Q-values over actions with lower values, i.e., a preference for a over a′ if Qθjk−1(s ′, a) > Qθjk−1 (s′, a′). However, since the maximizing assignment may be Θ-inconsistent (in isolation, or jointly with the parent’s information set, or with future assignments), candidate children should merely have higher probability of a high-value assignment. The second factor is the need to ensure diversity in the assignments among the set of children. Policy commitments at stage k constrain the possible assignments at subsequent stages. In many search procedures (e.g., beam search), we avoid backtracking, so we want the policy commitments we make at stage k to offer as much flexibility as possible in later stages. The third is the degree to which we enforce consistency.
There are several ways to generate such high-value assignments. We focus on just one natural technique: sampling action assignments using a Boltzmann distribution. Specifically, let σ denote the assignment (information set) of some node (parent) at level k − 1 in the tree. We can generate an assignment σk for Dk as follows. Assume some permutation s′1, . . . , s ′ |Dk| of χ(Dk). For each s ′ i in turn, we sample ai with probability proportional to e τQθk−1 (s ′ i,ai). This can be done without regard to consistency, in which case we would generally use the consistency penalty when constructing the regressor θk for this child to “encourage” consistency rather than enforce it. If we want strict consistency, we can use rejection sampling without replacement to ensure ai is consistent with σjk−1 ∪ σ≤i−1 (we can also use a subset of σ j k−1 as a less restrictive consistency buffer).
3 The temperature parameter τ controls the degree to which we focus on purely maximizing assignments versus more diverse, random assignments. While stochastic sampling ensures some diversity, this procedure will bias selection of high-value actions to states s′ ∈ χ(Dk) that occur early in the permutation. To ensure sufficient diversity, we use a new random permutation for each child.
Scoring children. Once the children of some expanded node are generated (and, optionally, their regressors constructed), we need some way of evaluating the quality of each child as a means of deciding which new nodes are most promising for expansion. Several techniques can be used. We could use the average Q-label (overall, or weighted using some initial state distribution), Bellman error, or loss incurred by the regressor (including the consistency penalty or other regularizer). However, care must be taken when comparing nodes at different depths of the search tree, since deeper nodes have a greater chance to accrue rewards or costs—simple calibration methods can be used. Alternatively, when a simulator is available, rollouts of the induced greedy policy can be used evaluate the quality of a node/regressor. Notice that using rollouts in this fashion incurs considerable computational expense during training relative to more direct scoring based on properties on the node, regressor, or information set.
3Notice that at least one action for state s′i must be consistent with any previous (consistent) information set.
Search Procedure. Given any particular way of generating/sampling and scoring children, a variety of different search procedures can be applied: best-first search, beam search, local search, etc. all fit very naturally within the CONQUR framework. Moreover, hybrid strategies are possible—one we develop below is a variant of beam search in which we generate multiple children only at certain levels of the tree, then do “deep dives” using consistency-penalized Q-regression at the intervening levels. This reduces the size of the search tree considerably and, when managed properly, adds only a constant-factor (proportional to beam size) slowdown to standard Q-learning methods like DQN.

heading: 3.5 A CONCRETE INSTANTIATION OF THE CONQUR FRAMEWORK

text:
We now outline a specific instantiation of the CONQUR framework that can effectively navigate the large search space that arises in practical RL settings. We describe a heuristic, modified beamsearch strategy with backtracking and priority scoring. Pseudocode is provided in Algorithm 2 (see Appendix B); here we simply outline some of the key refinements.
Our search process grows the tree in a breadth-first manner, and alternates between two phases. In an expansion phase, parent nodes are expanded, generating one or more child nodes with action assignments sampled from the Boltzmann distribution. For each child, we create target Q-labels, then optimize the child’s regressor using consistency-penalized Bellman error (Eq. 2) as our loss. We thus forego strict policy consistency, and instead “encourage” consistency in regression. In a dive phase, each parent generates one child, whose action assignment is given by the usual max-actions selected by the parent node’s regressor as in standard Q-learning. No additional diversity is considered in the dive phase, but consistency is promoted using consistency-penalized regression.
From the root, the search begins with an expansion phase to create c children—c is the splitting factor. Each child inherits its parent’s consistency buffer from which we add the new action assignments that were used to generate that child’s Q-labels. To limit the size of the tree, we only track a subset of the children, the frontier nodes, selected using one of several possible scoring functions. We select the top `-nodes for expansion, proceed to a dive phase and iterate.
It is possible to move beyond this “beam-like” approach and consider backtracking strategies that will return to unexpanded nodes at shallower depths of the tree. We consider this below as well.

heading: 3.6 RELATED WORK

text: Other work has considered multiple hypothesis tracking in RL. One particularly direct approach has been to use ensembling, where multiple Q-approximators are updated in parallel (Faußer & Schwenker, 2015; Osband et al., 2016; Anschel et al., 2017) then combined straightforwardly to reduce instability and variance. An alternative approach has been to consider population-based methods inspired by evolutionary search. For example, Conti et al. (2018) combine a novelty-search and quality diversity technique to improve hypothesis diversity and quality in RL. Khadka & Tumer (2018) consider augmenting an off-policy RL method with diversified population information from an evolutionary algorithm. Although these techniques do offer some benefit, they do not systematically target an identified weakness of Q-learning, such as delusion.

heading: 4 EMPIRICAL RESULTS

text: We experiment using the Atari test suite (Bellemare et al., 2013) to assess the performance of CONQUR. We first assess the impact of using the consistency penalty in isolation (without search) as a “regularizer” that promotes consistency with both DQN and DDQN. We then test the modified beam search described in Appendix B to assess the full power of CONQUR.

heading: 4.1 IMPACT OF CONSISTENCY PENALIZATION

text:
We first study the effects of introducing the soft-policy consistency in isolation, augmenting both DQN and DDQN with the consistency penalty term. We train our models using an open-source implementation (Guadarrama et al., 2018) of both DQN and DDQN (with the same hyperparameters). We call these modified algorithms DQN(λ) and DDQN(λ), respectively, where λ is the penalty coefficient defined in Eq. 2. Note that λ = 0 recovers the original methods. This is a lightweight
0
1
2
3
4
5
6 1e2 Gravitar
DQN(λ=0) DQN(λ=0.25) DQN(λ=0.50) DQN(λ=1.00) DQN(λ=1.50) DDQN(λ=0) DDQN(λ=0.25) DDQN(λ=0.50) DDQN(λ=1.00) DDQN(λ=1.50)
0.00 0.25 0.50 0.75 1.00 1.25 1e7
0.0
0.5
1.0
1.5
2.0
2.5
3.0 1e3 SpaceInvaders
QN(λ=0)
DQN(λ=0.50) DQN(λ=2.00) DDQN(λ=0) DDQN(λ=0.50) DDQN(λ=2.00)
Fig. 2: Varying penalization λ (no search procedure).
1
2
3
4
1e3 Alien 8 nodes
initial baseline ConQUR( =10) 1 2
3
4
1e3 Alien 16 nodes
initial baseline ConQUR( =10)
0 20 40 60 80 100 iterations
0
1
2
3
4 1e3 Solaris 8 nodes
initial baseline ConQUR( =10)
0 20 40 60 80 100 iterations
0
1
2
3
4 1e3 Solaris 16 nodes
initial baseline ConQUR( =10)
Fig. 3: Effects of increasing the number of nodes.
0
1
2 1e3 Solaris node_id=1
ConQUR baseline
0
1
2 1e3 Solaris node_id=2
ConQUR baseline
0
1
2 1e3 Solaris node_id=3
ConQUR baseline
0
1
2 1e3 Solaris node_id=4
ConQUR baseline
0 20 40 60 80 100 iterations
0
1
2 1e3 Solaris node_id=5
ConQUR baseline
0 20 40 60 80 100 iterations
0
1
2 1e3 Solaris node_id=6
ConQUR baseline
0 20 40 60 80 100 iterations
0
1
2 1e3 Solaris node_id=7
ConQUR baseline
0 20 40 60 80 100 iterations
0
1
2 1e3 Solaris node_id=8
ConQUR baseline
Fig. 5: Training curves of 8 (of 16) sorted nodes.
modification that can be applied readily to any regression-based Q-learning method, and serves to demonstrate the effectiveness of soft-policy consistency penalty. Since we don’t consider search (i.e., don’t track multiple hypotheses), we maintain a small consistency buffer using only the current data batch by sampling from the replay buffer—this prevents getting “trapped” by premature policy constraints. As the action assignment is the maximizing action of some network, σ(s′) can be computed easily for each batch. This results in a simple algorithmic extension that adds only an additional penalty term to the original TD-loss.
We train and evaluate DQN(λ) and DDQN(λ) for λ = {0.25, 0.5, 1, 1.5, 2} on 19 Atari games. In training, λ is initialized to 0 and slowly annealed to the desired value to avoid premature commitment to poor action assignments. Without annealing, the model tends fit to poorly informed action assignments during early phases of training, and thus fails to learn a good model.
The best λ is generally different across games, depending on the nature of the game and the extent of delusional bias. Though a single λ = 0.5 works well across all games tested, Fig. 2 illustrates the effect of increasing λ on two games. In Gravitar, increasing λ generally results in better performance for both DQN and DDQN, whereas in SpaceInvaders, λ = 0.5 gives improvement over both baselines, but performance starts to degrade for λ = 2.
We compare the performance of the algorithms using each λ value separately, as well as using the best λ for each game. Under the best λ, DQN(λ) and DDQN(λ) outperform their “potentially delusional” counterparts on all except 3 and 2 games, respectively. In 9 of these games, each of DQN(λ) and DDQN(λ) beats both baselines. With a constant λ = 0.5, each algorithm still beats their respective baseline in 11 games. These results suggest that consistency penalization (independent of the general CONQUR model) can improve the performance of DQN and DDQN by addressing the delusional bias that is critical to learning a good policy. Moreover, we see that consistency penalization seems to have a different effect on learned Q-values than double Q-learning, which addresses maximization bias. Indeed, consistency penalization, when applied to DQN, can achieve gains that are greater than DDQN (in 15 games). Third, in 9 games DDQN(λ) provides additional performance gains over DQN(λ).
A detailed description of the experiments and further results can be found in Appendix C.

heading: 4.2 CONQUR RESULTS

text:
We test the full CONQUR framework using the modified beam search discussed above. Rather than training a full Q-network, for effective testing of its core principles, we leverage pre-trained networks from the Dopamine package Castro et al. (2018).4. These networks have the same architecture as in Mnih et al. (2015) and are trained on 200M frames with sticky actions using DQN. We use CONQUR to retrain only the last (fully connected) layer (implicitly freezing the other layers), which can be viewed as a linear Q-approximator over the features learned by the CNN. We run CONQUR using only 4M addtional frames to train our Q-regressors.5
We consider splitting factors c of 2 and 4; impose a limit on the frontier size of 8 or 16; and an expansion factor of 2 or 4. The dive phase is always of length 9 (i.e., 9 batches of data), giving an expansion phase every 10 iterations. Regressors are trained using the loss in Eq. 2 and the consistency buffer comprises all prior action assignments. (See Appendix D for details, hyperparameter choices and more results.)
We run CONQUR with λ = {1, 10, 100, 1000} and select the best performing policy. We initially test two scoring approaches, policy evaluation using rollouts and scoring using the loss function (Bellman error with consistency penalty). Results comparing the two on a small selection of games are shown in Table 1. While rollouts, not surprisingly, tend to give rise to better-performing policies, consistent-Bellman scoring is competitive. Since the latter much less computationally intense, and does not require sampling the environment, we use it throughout our remaining experiments.
We compare CONQUR with the value of the pre-trained DQN. We also evaluate a “multi-DQN” baseline that applies multiple versions of DQN independently, warm-starting from the same pretrained DQN. It uses the same number of frontier nodes as CONQUR, and is otherwise trained identically as CONQUR but with direct Bellman error (no consistency penalty). This gives DQN the same advantage of multiple-hypothesis tracking as CONQUR but without policy consistency.
We test on 59 games, comparing CONQUR with frontier size 16 and expansion factor 4 and splitting factor 4 (16-4-4) with backtracking (as described in the Appendix D) resulted in significant improvements to the pre-trained DQN, with an average score improvement of 125% (excluding games with non-positive pre-trained score). The only games without improvement are Montezuma’s Revenge, Tennis, PrivateEye and BankHeist. This demonstrates that, even when simply retraining the last layer of a highly tuned DQN network, removing delusional bias has the potential to offer strong improvements in policy performance. It is able exploit the reduced parameterization to obtain these gains with only 4M frames of training data. Roughly, a half-dozen games have outsized score improvements, including Solaris (11 times greater value), Tutankham (6.5 times) and WizardOfWor (5 times).6
Compared to the stronger multi-DQN baseline (with 16 nodes), CONQUR wins by at least a 10% margin in 20 games, while 22 games see improvements of 1–10% and 8 games show little effect
4See https://github.com/google/dopamine 5This approach is simply to reduce the computational and memory footprint of our experiments. The
framework is not limited to this approach. 6This may be in part, but not fully, due to the sticky-action training of the pre-trained model.
(plus/minus 1%) and 7 games show a decline of greater than 1% (most are 1–6% with the exception of Centipede at -12% and IceHockey at -86%). Results are similar when comparing CONQUR and multi-DQN each with 8 nodes (8-2-2): 9 games exhibit 10%+ improvement, 21 games show 1–8% improvement, 12 games perform comparably and 7 games do worse under CONQUR. A table of complete results appears in Appendix D.3, Table 4, and training curves (all games, all λ) in Fig. 11.
Increasing the number of nodes from 8 to 16 generally leads to better performance for CONQUR, with 38 games achieving strictly higher scores with 16 nodes (16-4-4): 16 games with 10%+ improvement, 5 games tied and the remaining 16 games performing worse (only a few with a 5%+ decline). Fig. 3 shows the (smoothed) effect of increasing the number of nodes for a fixed λ = 10. The y-axis represents the rollout value of the best frontier node (i.e., the greedy policy of its Q-regressor) as a function of the training iteration. For both Alien and Solaris, the multi-DQN (baseline) training curve is similar with both 8 and 16 nodes, but CONQUR improves Alien from 3k to 4.3k while Solaris improves from 2.2k to 3.5k.
Fig. 4 and Fig. 5 (smoothed, best frontier node) shows node policy values and training curves, respectively, for Solaris. When considering nodes ranked by their policy value, comparing nodes of equal rank generated by CONQUR and by multi-DQN (baseline), we see that CONQUR nodes dominate their multi-DQN counterparts: the three highest-ranked nodes achieve a score improvement of 18%, 13% and 15%, respectively, while the remaining nodes achieve improvements of roughly 11–12%. Fig. 6 (smoothed, best frontier node) shows the effects of varying λ. In Alien, increasing λ from 1 to 10 improves performance, but it starts to decline for higher values of 100 and 1000. This is similar to patterns observed in 4.1 and represents a trade-off between emphasizing consistency and not over-committing to action assignments. In Atlantis, stronger penalization tends to degrade performance. In fact, the stronger the penalization, the worse the performance.

heading: 5 CONCLUDING REMARKS

text:
We have introduced CONQUR, a framework for mitigating delusional bias in value-based RL that relaxes some of the strict assumptions of exact delusion-free algorithms to ensure scalability. Its two main components are (a) a tree-search procedure used to create and maintain diverse, promising Q-regressors (and corresponding information sets); and (b) a consistency penalty that encourages “maximizing” actions to be consistent with the FA class. CONQUR embodies elements of both value-based and policy-based RL: it can be viewed as using partial policy constraints to bias the value estimator or as a means of using candidate value functions to bias the search through policy space. Empirically, we find that CONQUR can improve the quality of existing approximators by removing delusional bias. Moreover, the consistency penalty applied on its own, directly in DQN or DDQN, itself can improve the quality of the induced policies.
Given the generality of the CONQUR framework, there remain numerous interesting directions for future research. Other methods for nudging regressors to be policy-consistent include exact consistency (constrained regression), other regularization schemes that bias the regressor to fall within the information set, etc. Given its flexibility, more extensive exploration of search strategies (e.g., best first), child-generation strategies, and node scoring schemes should be examined within CONQUR. Our (full) experiments should also be extended beyond those that warm-start from a DQN model, as should testing CONQUR in other domains.
Other connections and generalizations are of interest as well. We believe our methods can be extended to both continuous actions and soft max-action policies. We suspect that there is a connection between maintaining multiple “hypotheses” (i.e., Q-regressors) and notions in distributional RL, which maintains distributions over action values Bellemare et al. (2017).

heading: A AN EXAMPLE OF DELUSIONAL BIAS

text:
We describe an example, taken directly from (Lu et al., 2018), to show concretely how delusional bias causes problems for Q-learning with function approximation. The MDP in Fig. 7 illustrates the phenomenon: Lu et al. (2018) use a linear approximator over a specific set of features in this MDP to show that:
(a) No π ∈ G(Θ) can express the optimal (unconstrained) policy (which requires taking a2 at each state);
(b) The optimal feasible policy in G(Θ) takes a1 at s1 and a2 at s4 (achieving a value of 0.5). (c) Online Q-learning (Eq. 1) with data generated using an ε-greedy behavior policy must converge
to a fixed point (under a range of rewards and discounts) corresponding to a “compromise” admissible policy which takes a1 at both s1 and s4 (value of 0.3).
Algorithm 1 CONQUR SEARCH (Generic, depth-first)
Input: Data sets Dk, Dk+1, . . . DT ; regressor Q̂k−1; and assignment σ over D≤k−1 = ∪1≤j≤k−1Dj reflecting prior data; policy class Θ.
1: Let ΣΘ,σ = {σk ∈ ΣΘ(Dj) : σk ∪ σ is consistent} 2: for all σjk ∈ ΣΘ,σ do 3: Training set S ← {} 4: for all (s, a, r, s′) ∈ Dk do 5: q ← r + γQ̂k−1(s′, σjk(s′)) 6: S ← S ∪ {((s, a), q)} 7: end for 8: Train Q̂jk using training set S 9: if k = T then
10: Return Q̂jk // terminate 11: else 12: Return SEARCH(Dk+1, . . . DT ; Q̂ j k; σ j k ∪ σ; Θ) // recurse 13: end if 14: end for
Q-learning fails to find a reasonable fixed-point because of delusion. Consider the backups at (s2, a2) and (s3, a2). Suppose θ̂ assigns a “high” value to (s3, a2), so that Qθ̂(s3, a2) > Qθ̂(s3, a1) as required by πθ∗ . They show that any such θ̂ also accords a “high” value to (s2, a2). But Qθ̂(s2, a2) > Qθ̂(s2, a1) is inconsistent the first requirement. As such, any update that makes the Q-value of (s2, a2) higher undercuts the justification for it to be higher (i.e., makes the “max” value of its successor state (s3, a2) lower). This occurs not due to approximation error, but the inability of Q-learning to find the value of the optimal representable policy.

heading: B ALGORITHMS

text: The pseudocode of (depth-first) version of the CONQUR search framework is listed in Algorithm 1. As discussed in Sec. 3.5, a more specific instantiation of the CONQUR algorithm is listed in Algorithm. 2.

heading: C ADDITIONAL DETAIL: EFFECTS OF CONSISTENCY PENALIZATION

heading: C.1 DELUSIONAL BIAS IN DQN AND DDQN

text:
Both DQN and DDQN uses a delayed version of the Q-network Qθ−(s′, a′) for label generation, but in a different way. In DQN, Qθ−(s′, a′) is used for both value estimate and action assignment σDQN(s ′) = argmaxa′ Qθk(s ′, a′), whereas in DDQN, Qθ−(s′, a′) is used only for value estimate and the action assignment is computed from the current network σDDQN(s′) = argmaxa′ Qθk(s ′, a′).
With respect to delusional bias, action assignment of DQN is consistent for all batches after the latest network weight transfer, as σDQN(s′) is computed from the same Qθ−(s′, a′) network. DDQN, on the other hand, could have very inconsistent assignments, since the action is computed from the current network that is being updated at every step.
Algorithm 2 Modified Beam Search Instantiation of CONQUR Algorithm Input: Search control parameters: m, `, c, d, T
1: Maintain list of data batches D1, ..., Dk, initialized empty 2: Maintain candidate pool P of at most m nodes, initialized P = {n0} 3: Maintain frontier list F of `c nodes 4: Maintain for each node nik a regressor θ i k and an ancestor assignment σ i k
5: for each search level k ≤ T do 6: Find top scoring node n1 ∈ P 7: Use ε-greedy policy extracted from Qθ1 to collect next data batch Dk 8: if k is an expansion level then 9: Select top ` scoring nodes n1, ..., n` ∈ P
10: for each selected node ni do 11: Generate c children ni,1, ..., ni,c using Boltzmann sampling on Dk with Qθi 12: for each child ni,j do 13: Let assignment history σi,j be σi ∪ {new assignment} 14: Determine regressor θi,j by applying update (3) from θi 15: end for 16: Score and add child nodes to the candidate pool P 17: Assign frontier nodes to set of child nodes, F = {ni,j} 18: if |P | > m then 19: evict bottom scoring nodes, keeping top m in P 20: end if 21: end for 22: end if 23: if k is a refinement ("dive") level then 24: for each frontier node ni,j ∈ F do 25: Update regressor θi,j by applying update (3) to θi,j 26: end for 27: end if 28: Run d "dive" levels after each expansion level
29: end for

heading: C.2 TRAINING METHODOLOGY AND HYPERPARAMETERS

text:
We implement consistency penalty on top of the DQN and DDQN algorithm by modifying the opensource TF-Agents library (Guadarrama et al., 2018). In particular, we modify existing DqnAgent and DdqnAgent by adding a consistency penalty term to the original TD loss.
We use TF-Agents implementation of DQN training on Atari with the default hyperparameters, which are mostly the same as that used in the original DQN paper (Mnih et al., 2015). For conveniece to the reader, some important hyperparameters are listed in Table 2. The reward is clipped between [−1, 1] following the original DQN.

heading: C.3 EVALUATION METHODOLOGY

text: We empirically evaluate our modified DQN and DDQN agents trained with consistency penalty on 15 Atari games. Evaluation is run using the training and evaluation framework for Atari provided in TF-Agents without any modifications.

heading: C.4 DETAILED RESULTS

text:
Fig. 8 shows the effects of varying λ on both DQN and DDQN. Table 3 summarizes the best penalties for each game and their corresponding scores. Fig. 9 shows the training curves of the best penalization constants. Finally, Fig. 10 shows the training curves for a fixed penalization of λ = 1/2. The datapoints in each plot of the aforementioned figures are obtained by taking windows of size 30
steps, and within each window, we take the largest policy value (and over ≈2–5 multiple runs). This is done to reduce visual clutter.

heading: D ADDITIONAL DETAIL: CONQUR RESULTS

text:
Our results use a frontier queue of size (F ) 8 or 16 (these are the top scoring leaf nodes which receive gradient updates and rollout evaluations during training). To generate training batches, we select the best node’s regressor according to our scoring function, from which we generate training samples (transitions) using ε-greedy. Results are reported in Table 4 and 5, and related figures where max number of nodes are 8 or 16. We used Bellman error plus consistency penalty as our scoring function. During the training process, we also calibrated the scoring to account for the depth difference between
the leaf nodes at the frontier versus the leaf nodes in the candidate pool. We calibrated by taking the mean of the difference between scores of the current nodes in the frontier with their parents. We scaled this difference by multiplying with a constant of 2.5.
In our implementation, we initialized our Q-network with a pre-trained DQN. We start with the expansion phase. During this phase, each parent node splits into l children nodes and the Q-labels are generated using action assignments from the Boltzmann sampling procedure, in order to create high quality and diversified children. We start the dive phase until the number of children generated is at least F . In particular, with F = 16 configuration, we performed the expansion phase at the zero-th and first iterations, and then at every tenth iteration starting at iteration 10, then at 20, and so on until ending at iteration 90. In the F = 8 configuration, the expansion phase occurred at the zero-th and first iterations, then at every tenth iterations starting at iterations 10 and 11, then at iterations 20 and 21, and so on until ending at iterations 90 and 91. All other iterations execute the “dive” phase. For every fifth iteration, Q-labels are generated from action assignments sampled according to the Boltzmann distribution. For all other iterations, Q-labels are generated in the same fashion as the standard Q-learning (taking the max Q-value). The generated Q-labels along with the consistency penalty are then converted into gradient updates that applies to one or more generated children nodes.

heading: D.1 TRAINING METHODOLOGY AND HYPERPARAMETERS

text: Each iteration consists of 10k transitions sampled from the environment. Our entire training process has 100 iterations which consumes 1M transitions or 4M frames. We used RMSProp as the optimizer with a learning rate of 2.5 × 10−6. One training iteration has 2.5k gradient updates and we used a batch size of 32. We replace the target network with the online network every fifth iteration and reward is clipped between [−1, 1]. We use a discount value of γ = 0.99 and ε-greedy with ε = 0.01 for exploration. Details of hyper-parameter settings can be found in Table 6 (for 16 nodes) and Table 7 (for 8 nodes).

heading: D.2 EVALUATION METHODOLOGY

text: We empirically evaluate our algorithms on 59 Atari games (Bellemare et al., 2013), and followed the evaluation procedure as in Hasselt et al. (2016). We evaluate our agents every 10th iterations (and also the initial and first iteration) by suspending our training process. We evaluate on 500k frames, and we cap the length of the episodes for 108k frames. We used ε-greedy as the evaluation policy with ε = 0.001.

heading: D.3 DETAILED RESULTS

text: Fig. 11 shows training curves of CONQUR with 16 nodes under different penalization strengths λ. Each plotted step of each training curve (including the baseline) shows the best performing node’s policy value as evaluated with full rollouts. Table 4 shows the summary of the highest policy values achieved for all 59 games for CONQUR and the baseline under 8 and 16 nodes. Table 5 shows a similar summary, but without no-op starts (i.e. policy actions are applied immediately). Both the baseline and CONQUR improve overall, but CONQUR’s advantage over the baseline is amplified. This may suggest that for more deterministic MDP environments, CONQUR may have even better improvements. The results on 16 and 8 nodes use a splitting factor of 4 and 2, respectively.

heading: Hyperparameters Description Value

title: CONQUR: MITIGATING DELUSIONAL BIAS IN DEEP Q-LEARNING