BAM: Bayes with Adaptive Memory
Authors: Josue Nassar
Jennifer Rogers Brennan
Ben Evans
Kendall Lowrey
Venue: ICLR 2022 Poster (2022)
Keywords: Bayesian learning
online learning

Abstract: Online learning via Bayes' theorem allows new data to be continuously integrated into an agent's current beliefs. However, a naive application of Bayesian methods in non-stationary environments leads to slow adaptation and results in state estimates that may converge confidently to the wrong parameter value. A common solution when learning in changing environments is to discard/downweight past data; however, this simple mechanism of "forgetting" fails to account for the fact that many real-world environments involve revisiting similar states. We propose a new framework, Bayes with Adaptive Memory (BAM), that takes advantage of past experience by allowing the agent to choose which past observations to remember and which to forget. We demonstrate that BAM generalizes many popular Bayesian update rules for non-stationary environments. Through a variety of experiments, we demonstrate the ability of BAM to continuously adapt in an ever-changing world.

Published as a conference paper at ICLR 2022
BAM: BAYES WITH ADAPTIVE MEMORY
Josue Nassar"
Jennifer Brennan
Department of Electrical and Computer Engineering Stony Brook University josue www.sarstttybboooo....o. edu
Department of Computer Science
University of Washington
j jrbbcs wwwhington. edu
Ben Evans
Kendall Lowrey"
Department of Computer Science
Department of Computer Science
New York University
University Washington
Sonevans@nyu.com edu
k owreyêca washi ngtton edu
ABSTRACT
Online learning via Bayes' theorem allows new data to be continuously integrated into an agent's current beliefs. However, a naive application of Bayesian methods in non-stationary environments leads to slow adaptation and results in state esti- mates that may converge confidently to the wrong parameter value. A common solution when learning in changing environments is to discard//owwwweihh past data; however, this simple mechanism "forgetting" fails to account for the fact that many real-world environments involve revisiting similar states. We propose a new framework, Bayes with Adaptive Memory (BAM), that takes advantage of past experience by allowing the agent choose which past observations remember and which to forget. We demonstrate that BAM generalizes many popular Bayesian update rules for non-stationary environments. Through variety of experiments, we demonstrate the ability of BAM to continuously adapt in an ever-changing world.
INTRODUCTION
The ability of an agent to continuously modulate its belief while interacting with a non-stationary environment a hallmark of intelligence and has garnered a lot of attention recent years (Zhang et al., 2020; Ebrahimi al., 2020; Xie et al., 2020). The Bayesian framework enables online learning by providing a principled way to incorporate new observations into an agent's 's model of the world (Jaynes, 2003; Gelman et al., 2013). Through the use of Bayes' theorem, the agent can combine its own (subjective) a priori knowledge with data to achieve an updated belief encoded by the posterior distribution.
The Bayesian framework a particularly appealing option for online learning because Bayes' theorem is closed under recursion, enabling continuous updates in what is commonly referred to as the recursive Bayes method (Wakefield, 2013). As an example, suppose the agent first observes batch of data, D, and then later observes another batch of data, D2. We express the agent's posterior distribution over the world, where the world is represented by 0, as
p())D1, = p((
(I)
D(D2(Di)
where
P(D2|Di) = pp(1)))(
(2)
Equation demonstrates the elegance and simplicity of recursive Bayes: time t, the agent recycles its previous posterior, ce)) where Dzt {DI.-- Dr-1h, into its current prior and then combines with newly observed batch of data, D,, obtain an updated posterior, P()).
"corresponding authors

---

Published as a conference paper at ICLR 2022
At first glance, it would appear that naive application of recursive Bayes would suffice for most online learning tasks. However, the recursive Bayes method relies on the assumption that the world is stationary, i.c. D1, D2.... all independent and identically distributed. When this assumption is violated, recursive Bayes can fail catastrophically. As an illustration, consider the law of total variance:
(ar( VV De) Var(E[ Dil(e))..
(3)
Since both terms on the right hand side are positive, equation 3 reveals that in expectation, the variance of the posterior decreases as more data is seen regardless of the actual distribution of D,. i.c.
Var(0)D<.)) >
(4)
In fact, for some models equation is true with probability I; we demonstrate examples in Appendix A. Thus, if the parameters of the environment, 0, were to change, the variance of the posterior would still decrease, becoming more certain of a potentially obsolete parameter estimate. Modeling the environment stationary when it is actually changing also keeps the learning speed of the agent artificially low, as tighter posteriors prevent large jumps in learning. This is the opposite of what an intelligent agent should do in such an event: if the environment changes, would expect the agent's uncertainty and learning speed to increase in response.
As was elegantly stated by Monton (2002), the problem with naive use of recursive Bayes is that "Such a Bayesian never forgets." Previous approaches on enabling recursive Bayes to work in non-stationary settings have primarily focused on forgetting past experience either through the use of changepoint detection (Adams & MacKay, 2007: Li et al., 2021), or by exponentially weighting past experiences (Moens, 2018; Moens & Zénon, 2019; Masegosa al., 2020). While empirically successful, their focus on forgetting the past means that revisited states are treated as novel. In this work we take an alternative approach to online Bayesian learning agent with an explicit memory module. Crucially, the addition of a memory buffer equips the agent with the ability to modulate its uncertainty by choosing what past experiences to both forget and remember. We call our approach Bayes with Adaptive Memory (BAM) and demonstrate its wide applicability and effectiveness on a number of non-stationary learning tasks.
-ta-stationary environments by endowing an
2 BAYES WITH ADAPTIVE MEMORY
The generative model is assumed to evolve according to
0, p(0, (0-,, D ~ (D) = p(D(o.).
(5)
(6)
where equation 5 is the latent dynamics that dictate the evolution of the environment parameters. 8, and equation is the likelihood whose parametric form is fixed throughout time, i.c. P. (D) (10,,, o²). Equations 5 and 6 define state-space model, which allows one to infer 0, through Bayesian filtering (Särkkä, 2013)
(())De)) x xP(())).)p(0)
p(0,)De)) = p(0100-1.11)(001111PP
(8)
The parameterization of equations 5 and dictate the tractability of equations 7 and 8. If priori an agent knew that equation 5 is a linear dynamical system with additive white Gaussian noise and equation 6 is also Gaussian whose conditional mean is a linear function of 9,, then the Kalman filter can be used (Kalman, 1960). For more complicated latent dynamics and/or likelihood models, methods such as particle filtering (Doucet & Johansen, 2009) and unscented Kalman filtering (Julier & Uhlmann, 1997) can be used. Crucially, Bayesian filtering methods assume that the latent dynamics governed by equation are known; however, this is rarely the case in practice. Instead of making assumptions the parametric form of equation 5, we take different approach.
In BAM, the agent maintains a memory buffer, Dec, that stores previous observations of the environ- ment. At time t the agent obtains new batch of data, D, pr (D). How should the agent combine the newly observed data, D., with its stored memory, D Decs to update its belief as encoded by the posterior distribution?
2

---

Published as a conference paper at ICLR 2022
In recursive Bayes, the posterior distribution is computed according to p(O,|Dr, Det) x (D) (O):)D))),
(9)
[-1
Dx)) & p(0,) II 10,) ==1
(10)
where we refer to p(O,) as the base prior. Equation 10 allows us to interpret recursive Bayes as the agent constructing dynamic prior, p(O,)Dee), using all the experiences stored in its memory buffer. This works under the stationarity assumption; when this assumption is violated, the application of Bayes' theorem can lead to confidently wrong results as the "distance" between Pr(D) and (D( can be vast. An alternative is for the agent to completely forget all of its past experiences
(Dt) & ((D())))p(()).
(11)
While equation 11 may be viable in situations where DD is sufficiently informative, it is wasteful when experiences in the memory buffer may help infer 0,.
BAM dynamically finds middle ground between these two extremes of remembering (equation 10) and forgetting (equation 11) everything by allowing the agent to choose which data to use from its memory buffer to construct the prior. Specifically, the agent endowed with time-dependent readout weight, W [wt,1, W2,,," We,t-1] where was E [0, Given a new datum D,, BAM constructs its posterior according to
p(0, Del, Wi) a p(0))p(D,(0) II p (D,10
(12)
We rewrite equation 12
p0,,),, Dea, D,,,,,,))))) W,) = (( Wi)
(13)
DD Wi)
where
2-1
p(0, D(r, Wi) & p(0.) II (D)
(14)
and
p(D W.) W (DD W.)d0.
(15)
The prior construction in equation 14 is akin to recursive Bayes, but now the agent can dynamically and adaptively change its prior by using the readout weights. W,, to weigh the importance of previous experience where at the extreme, it can choose to completely forget a previous experience, Wr, = 0, or fully remember it, Waj 1. For simplicity, restrict the readout weights to be binary, i.c. Wr, E 13.
The combination of a memory buffer, Des. with time-dependent readout weight, W,, allows BAM to generalize many previously proposed approaches. By setting W/,1 = W1.2 ..... Wr = 1, W1 a, where 0 < we recover the power priors approach of Ibrahim et al. (2015). By setting Wa.j 1-1-j where < a < 1, we recover exponential forgetting (Moens, 2018; Moens Zénon, 2019; Masegosa al., 2020). Lastly, by setting particular subset of the readout weights to be O, we recover Bayesian unlearning (Nguyen et al., 2020).
recover recursive Bayes (equation 10). By setting W/,1 W1,2
The ability adaptively change its prior implies that BAM can increase/decrease its uncertainty as the situation demands; subsequently, this modulates the agent's learning speed. Using variance as a proxy for uncertainty, one would expect that the variance of the prior used in BAM (equation 14)
is always at least as large as the variance of the prior used in recursive Bayes (equation 10). We formalize this for the case of binary readout weights in the following proposition.
Proposition 1. Let p(0 Det, Wt) be the prior used by BAM, defined in equation 14 and let ((8 be the recursive Bayes prior, defined in equation 13. Then E[Var(@ Det, Wo) W:] 2 E(Var(8|Dee)].
YW, E 10.1)
(16)
Proof. Proof is in Appendix B.
Recursivv Bayes equivalent Bayesian filtering when p(0, () 5(0, (c-1))-
3

---

Published as a conference paper at ICLR 2022
2.1 SELECTION OF READOUT WEIGHTS VIA BAYESIAN MODEL-SELECTION
While the previous section demonstrated the flexibility of BAM, the question remains: how should the readout weights, W,, be set? Equation 13 allows us view different readout weights as different models. Through this lens, we can follow the spirit of Bayesian model selection (Gelman et al., 2013) and compute posterior over the readout weights
(D, Del) & (PW, Dz)).
(17)
For practicality, we compute the maximum a posteriori (MAP) estimate of equation 17 (Gelman et al., 2013) and use that the value of the readout weight
We
argmax log ((,, LogD(W(Dee),
(18)
argmax log ((D.)))) ((D,,00))((01WW + log (D) WE(O.1)
(19)
The first term of equation 18 is the log marginal likelihood, which measures the likelihond of DD being distributed according to the predictive distribution, p(D) W, Dec) while the prior, log pWW)Dee)) acts as regularizer. This procedure of constantly updating the readout weights through equation 18 can be interpreted as providing Bayes a feedback mechanism: equation 18 allows the agent directly measure its ability to fit the observed data using different combination of experiences in its buffer via the readout weight, and then choosing the readout weight that leads best fit. In contrast, standard Bayesian inference is an open-loop procedure: data, likelihood and prior are given and posterior is spat out, irrespective of the of the model to the data (Simpson et al., 2017).
Still left is the question of how do we design the prior, p [W[) In certain scenarios, using an uninformative prior, i.e. pW (t) x 1, may suffice if the data is very informative and/or the number of data points in D, is large. In scenarios where these conditions are not met, it is important to use an informative prior as it reduces the chance of overfitting. In general, the design of priors is highly nontrivial (Winkler, 1967; Gelman et al., 2013; Simpson et al., 2017). While there exists many potential options, we use penalized model complexity priors proposed by Simpson et al. (2017) as they designed to reduce the chance of overfitting. Following Simpson et al. (2017), we parameterize the prior as
p (Dee) exp (-XV/11)2 22 De.e)llll (ct)))
(20)
where À E [0, oo) is a hyperparameter that controls the strength of the prior. Equation 20 encodes our prior belief that we favor values of W, that produce simpler models, where simplicity is quantified as the Dallback-Leiblee
divergence between p(0, WW. Det) and the base prior, p(0.).
Plugging equation 20 into equation 18 we get
W₁ argmax log Dog.DD/W.DDD--NNDDDbbtH wWD.D/////////..///leeele.. we(0.1)
(21)
In general, solving equation 21 is difficult as the number of possible readout weights is 2(t-1), making brute force solutions practically infeasible. While there exists many approaches for performing discrete optimization, we found that using a simple greedy approach sufficed for our experiments; in the interest of space, defer discussion regarding this to Appendix C.
RELATED WORKS
A variety of approaches have been proposed for learning in non-stationary environments. In signal processing, adaptive filtering techniques such as recursive least squares (RLS) and least mean square filtering (LMS) are the de facto approaches for filtering in non-stationary environments (Haykin, 2008). While empirically successful, RLS and LMS are only applicable for limited range of models, i.e. linear models. In contrast, BAM is a general purpose algorithm that can be deployed on wide variety models.
A 0 recovers the uninformative prior case, (WW(Dec) x 1.
4

---

Published as a conference paper at ICLR 2022
If the latent dynamics are known or assumed to be known- then Bayesian filtering can be employed. popular approach is to model the latent dynamics (equation 5) as an autoregressive process (Kurle et al., 2020; Rimella & Whiteley, 2020). While this approach has been popular, it only applicable for models where the parameters are real-valued. A seminal work on Bayesian filtering is the Bayesian online changepoint detction (BOCD) algorithm of Adams & MacKay (2007), where the latent dynamics (equation 5) are modeled to be picce-wise constant. While BOCD is broadly applicable and has seen empirical success, the caveat that an agent forgets all previous experience when a change is detected; thus, previously visited states appear novel to the agent and learning must begin from scratch. An extension to BOCD was proposed by Li al. (2021), where when change is detected a scaled version of the previous posterior is used as the prior. While similar in spirit to BAM, we note that the approach proposed in Li et al. (2021) is designed for Gaussian distributions, while BAM can work with arbitrary distributions. Moreover, the approach in Li et al. (2021) can only increase the uncertainty by a fixed pre-determined amount while BAM can adaptively modulate its uncertainty.
Previous works have proposed solutions for making recursive Bayes more suited for use in non- stationary environments through exponential forgetting of past data (Moens, 2018; Moens & Zénon, 2019; Masegosa et al., 2020). While these models have also seen empirical success, their focus have been on forgetting past experiences which prevents the agent to leverage past experiences that relevant. In BAM, the agent is focused not only forgetting irrelevant experiences but remembering relevant experiences as well.
The of readout weights in BAM can be seen as an instance of likelihood tempering, which has been used to perform robust Bayesian inference (Wang et al., 2017) and to help with approximate Bayesian inference schemes (Neal, 1996; 2001; Mandt al., 2016). While previous works focus on the offline case where data has already been collected, BAM focuses on the online case where the agent adaptively tempers the likelihood.
The concept of an external memory buffer has recently been explored in machine learning (Gemici al., 2017; Wu et al., 2018; Marblestone et al., 2020). While similar in spirit BAM, most works use softmax as their readout weight. As byproduct, the agent must select an element from the buffer even if it isn't 't applicable to the task at hand! BAM has no such restriction, and can ignore all the previous data in the buffer, resetting back to the base prior.
4 EXPERIMENTS
To demonstrate the versatility of BAM, we apply it in variety of scenarios. As BAM is a learning paradigm, it can be implemented as a module a larger framework allowing it to be easily used in settings such as controlreiinorreemnnt learning and domain adaptation (Thompson, 1933; Osband et al., 2018: 8; Lowrey et al., 2018; Yoon et al., 2018). BAM requires the ability to construct the posterior, p(0, (Der. Wt), and evaluate the log marginal likelihood, log p(D, [D<r. Wt). In general, the posterior and log marginal likelihood are only available analytically for conjugate priors (Gelman et al., 2013). While approaches exist for approximating the posterior (Robert et al., 2004; Brooks et al., 2011; Blei et al., 2017) and the log marginal likelihood (Robert et al., 2004; Gelman et al., 2013: Grosse et al., 2015), we restrict ourselves to only use conjugate priors to ensure any benefits of BAM are not due to uncertain effects of approximations. The use of conjugate priors also allows us use sufficient statistics compute posteriors, allowing BAM to scale amicably when the number of data points in a batch is large (Casella & Berger, 2021).
4.1 EXPERIMENT 1: INFERENCE IN A NON-STATIONARY ENVIRONMENT
To evaluate BAM on online inference in a non-stationary environment, we generate data from the following model
2TT
0: = a ainn
+ 6,
(22)
100
p ( = Binomial (15,, 0,),
(23)
where 0.3 and b = 0.5 are chosen such that the lower and upper bounds for 0 are 0.2 and 0.8, respectively. We evaluate BAM with no regularization, À = 0, and with regularization, where
x = 0.1; the data is discrete, there is a possibility that BAM could overfit, thus priori
5

---

Published as a conference paper at ICLR 2022
would expect the regularized BAM to perform better. We compare against recursive Bayes, Bayesian
exponential forgetting (BF) and Bayesian online changepoint detection (BOCD).
True
Recur. Bayes
BOCD
w/ reg
1.0
Log posterior variance
-6
0.4
0.2
-10
0.0
100
200
300
400
500
100
200
300
600
500
Time
Time
Figure Comparison of recursive Bayes, BOCD, BF, BAM and BAM with regularization on inferring time-varying parameter. Results computed over 20 random seeds. Solids lines the median and and error bars represent the 10% and 90% quantiles. Left: Temporal evolution of the posterior mean. Right: Temporal evolution of the log posterior variance.
Figure demonstrates the weakness of recursive Bayes; as it views more data, the posterior gets more confident. This reduces the learning speed of the agent, preventing from accurately tracking O,, and causing it to converge to the average with an extremely low posterior variance. BOCD tracks the parameter relatively well, though its estimates are slightly delayed. As BOCD lacks the ability to recall useful data from the past, its posterior variance resets every time changepoint is detected. BAM able to track and doesn't 't suffer from temporal lag seen in the BOCD results, though the lack of regularization leads to estimates that are not as smooth BOCD. The posterior variance of BAM reflects that the agent remembers relevant history and forgets irrelevant history, reducing the jump in posterior variance when revisiting previously seen state. Lastly, with regularization leads to smoother estimates but tends to be less confident compared to the other methods.
that BAM
4.2 EXPERIMENT 2: CONTROLS
In this section we illustrate the benefit of memory by applying BAM on a learning task to model non-linear dynamics for controls. The task is analytical version of Cartpole (Barto al., 1983), where the goal is to swing-up pole on a moving cart. Non-stationarity introduced by changing the environment's gravity information models. In the episodic setting, the agent told when change occurs, but not the value of the gravity parameter. In the continual learning setting, the agent is not informed of environmental changes.'
time. We explore the performance of BAM under different
The reward for the task is the cosine of the angle of the pole on the cart, where an angle of (0 is the vertical 'up' position. To make the problem amenable for analytical posterior and log marginal likelihood computations. we model the nonlinear dynamics using linear regression with random Fourier features (RFF) (Rahimi & Recht, 2007)
21-1 M6(xL-1.a)) + + ~~~ (~0,000021))
(24)
2 'hhe timescale parameter for BOCD is 1/100, which is the frequency of the sinusoid. The weighting term for BF
"For both settings, the number of data points in hatch is relatively large, leading the log marginal likelihond overtake the prior in equation 21. As regularization has little effect, results shown for À 0.

---

Published as a conference paper at ICLR 2022
where 2, E IR is the state vector, de E Rd is the action vector, Et E R is state noise and is RFF function. For simplicity, we assume a fixed noise variance o² 10 This parameterization allows to perform Bayesian linear regression over M which is analytically tractable (Gelman et al., 2013). Full details can be found in Appendix D.I.
4.2.1 EPISODIC ONE-SHOT
In this setting our simulated Cartpole hypothetically moves between different planets-hemt a change in gravity-while still being asked to swing the pole up. In an episode, gravity is fixed for the duration of 15 trials, where each trial resets the Cartpole trajectory of states and actions of length H that are batched into one unit of data, such that each episode contributes 15 experiences; thus the datum for trial / Dr = [[[z}, ag}s I [r, - -
random initial state, Zg. Each trial produces
We compare BAM to recursive Bayes in one-shot manner: after the first trial of a new episode, BAM computes a weight vector over all previously encountered trial data to inform a posterior for the duration of the episode. Recursive Bayes is reset to the base prior at the beginning of new episode. Both proceed to update their belicf every trial in an episode.
We show in Figure 2 results over 5 random seeds where the expected score for ground truth model is shown as reference. The first time BAM encounters a novel planet, it resets its prior to the base prior and starts learning from scratch, similar to recursive Bayes. On subsequent visits however, BAM able to leverage its past experiences to quickly adapt and recover high levels of performance. As recursive Bayes starts from scratch, it will again need multiple trials to develop competent model.
Episodic Model Learning for Control
Reward
GT MPC
Recur. Bayes
BAM
-180
Episodes
Figure 2: We compare BAM recursive Bayes in episodic model learning for control setting where the agent knows when the cartpole dynamics have changed. For reference, the ground-truth scores (GT MPC) are also plotted for the different settings; all methods were averaged across random seeds with 10-90% quantiles shown. In this sequence, the values of gravity per episode are 9.81, 11.15, 3.72, 15, 3.72, 9.81.
4.2.2 CONTINUAL LEARNING
In addition to the challenge of adapting to a different environment, we also test BAM when the agent not informed the change, such that adaption must happen continually. In this scenario without explicit episodes, the gravity of the world can change after trial, unbeknownst to the agent. Similar to the previous setting, a datum for trial is D. = {(I=, az], [z,- - =))1))
While it is straightforward to run BAM in this setting, also investigate combining BAM with BOCD, which we denote as BAM + BOCD. In BOCD, the detection posterior distribution to be reset to the base prior. In BAM BOCD, the detection of changepoint is used as signal for when the agent should adapt its prior by computing W,, to obtain p(@, Det); this avoids rerunning the optimization procedure after each trial.
changepoint causes the
We show in Figure that while BOCD works as intended, without BAM the Cartpole has to relearn a model from the prior belief, leading to significant dips in the expected reward. While all methods
7

---

Published as a conference paper at ICLR 2022
able to adapt when the environment is in constant state, the of past information allows BAM and BAM + BOCD to quickly adapt. We can see that BAM and BAM + BOCD perform very similarly to each other, suggesting that can bypass unnecessary computation.
Continual Model Adaptation
100
M
Reward
BOCD
BAM
-100
BAM+3OCD
200
30
60
10
Gravity
0 10
30 40
60
Figure 3: The bottom plot shows the gravity value changing time; the performance of the learned model in the swing-up task shown above for random seeds with 10-90% quantiles. Initially all methods perform similarly until BAM encounters environment it has experienced before, in which adapts more quickly than BOCD. The initial similarity is due to both methods detecting similar changepoints and reverting to un-informed priors. Naive BAM performs well, albeit with weight optimization after each trail versus only during detected changepoints for the other methods (60 optimizations versus ~)).
4.3
EXPERIMENT 3: NON-STATIONARY BANDIT
Recursive Bayes
Bayesian Forgetting
BOCD
UCB
UCBAM
Cumulative regret, 10 Arms
Cumulative regret, 50 Arms
5000
8000
Cumulative regret
4000
6000
3000
2000
2000
1000
2500
5000
7500
10000
2500
5000
7500
10000
Iterations
Iterations
Figure 4: Cumulative regret over time between Thompson sampling (recursive Bayes), Bayesian exponential forgetting, BOCD, UCB, and UCBAM for different numbers of non-stationary arms, where results are averaged over 5 random arm configurations, where for each arm configuration results were collected over different random seeds. Shaded bars represent 25-75% quantiles.
A common environment for testing the performance of online learning algorithms is the bandits setting (Sutton & Barto, 2018). We study a non-stationary version the bandits setting where each arm switches between time, previously low value arm. Gaussian noise with o = 0.25 is additionally added to the current arm value. Sample arm values can be found in Figure 5.
values asynchronously, such that the best could be, any point in
For stationary bandits, a popular algorithm is Thompson sampling (Thompson, 1933) in which posterior each arm is continually updated via recursive Bayes. These posteriors then
8

---

Published as a conference paper at ICLR 2022
leveraged to decide which arm the agent should pull. where the posterior uncertainty allows the agent to automatically switch between exploration and exploitation. In the non-stationary setting, we would expect vanilla Thompson sampling to fail as the arm posteriors would continue becoming more certain, as is evident from section 4.1. While there are many approaches for how to adapt BAM to perform well in the non-stationary bandits setting, we take simple approach and combine BAM with the upper confidence bound (UCB) bandit algorithm (Agrawal, 1995), which we call UCBAM; in the interest of space, we provide an algorithm table in Appendix D.3.1. We compare UCBAM against UCB, Thompson sampling, Bayesian exponential forgetting + Thompson sampling and a BOCD+ + Thompson sampling scheme proposed by Mellor & Shapiro (2013); hyperparameter values can be found in Appendix D.3. From Figure 4, we see that UCBAM outperforms the other methods for both 10 and 50 arms. Thompson sampling fails to capture the true current values of the arms and suffers a large penalty while exploration afforded by UCB enables better performance. BOCD achieves low regret in the 10 arm setting, but reverts to its prior too often to perform well with 50 arms.
4.4 EXPERIMENT 4: DOMAIN ADAPTATION WITH ROTATED MNIST
In the image classification setting, we often want to operate across a variety of domains. Traditional approaches include learning single high capacity model or encoding assumptions about the domain structure into the system (Jaderberg et al., 2015; Worrall et al., 2017). Instead, we use a simple multivariate linear regression model where the targets are one-hot encoded labels, taking the highest output as the selected class. We consider a setting where the distribution of domains known and the same at both train and test time and evaluate BAM's ability to classify given small number of labeled examples from the domains to adapt its belief. To achieve this, we create a rotated MNIST dataset. 32 domains were created, where each domain
comprised of 1,875 randomly sampled without replacement from the training set. In a domain, the images are rotated by an angle sampled uniformly at random from 0 и. Each domain is treated as batch of data in the memory buffer,
i.e D, = (<x), } } We split and rotate the test set similarly into 8 domains and give 10 labeled examples from each to find readout weights over the training data. We calculate the average accuracy over all test domains and collect results over 10 random seeds. While OLS trained over all domains get a mean and standard deviation accuracy of 55% 3.7% accuracy, BAM is able to achieve test set accuracy of 71.8% % + 5.2%. showing that BAM is able to leverage previous experiences to adapt to novel domains.
5 CONCLUSION AND FUTURE WORK
In this work we present BAM, flexible Bayesian framework that allows agents to adapt to non- stationary environments. Our key contribution is the addition of a memory buffer to the Bayesian framework, which allows the agent to adaptively change its prior by choosing which past experiences to remember and which to forget. Empirically, we show the proposed approach is general enough to be deployed in variety of problem settings such online inference, control, non-stationary bandits and domain adaptation. To ensure that we isolated the benefits of BAM, the experiments it allowed
focused conjugate-pric priir distributions log-marginal likelihood in closed form. Future work will focus on leveraging advance in streaming variational inference (Broderick al., 2013; Kurle al., 2020) to allow BAM to be deployed on more complicated models. i.e. Bayesian deep neural networks. For simplicity, we focused on binary values for the readout weights as it allowed for a simple greedy discrete optimization algorithm to be used. We imagine that allowing the weights to be any value between O and 1 will increase performance in certain settings and allow BAM to have a much larger repertoire of priors that it can construct, as well as suggest different optimization algorithms to use within the framework. Finally, efficient memory buffer schemes will be explored to avoid the 'infinite memory' problem of continual learning, enabling BAM to operate with efficiency indefinitely.
compute the prior/posterior and the
ACKNOWLEDGMENTS
The authors thank Ayesha Vermani, Matthew Dowling and II Memming Park for insightful discussions and feedhack.

---

Published as a conference paper at ICLR 2022
REFERENCES
Ryan Prescott Adams and David JC MacKay. Bayesian online changepoint detection. arXiv preprint arXiv:0710.3742. 2007.
Rajeev Agrawal. Sample mean based index policies by O(log n) regret for the multi-armed bandit problem. Advances in Applied Probability, 1995.
Andrew Barto, Richard S Sutton, and Charles Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE transactions on systems, man, and cybernetics, 1983.
David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational inference: A review for statisticians. Journal of the American statistical Association, 2017.
Tamara Broderick, Nicholas Boyd, Andre Wibisono, Ashia Wilson, and Michael I Jordan. Stream- ing variational bayes. In Advances in Neural Information Processing Systems, 2013.
Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. Handbook of Markov Chain Monte Carlo. CRC press, 2011.
George Casella and Roger L. Berger. Statistical inference. Cengage Learning. 2021.
Arnaud Doucet and Adam M Johansen. A tutorial on particle filtering and smoothing: Fifteen years later. Handbook of nonlinear fintinearfiltering. 2009.
Sayna Ebrahimi, Franziska Meier, Roberto Calandra, Trevor Darrell, and Marcus Rohrbach. Adver- sarial continual learning, arXiv preprint arXiv:2003.088 09555,,3.. 2020.
Andrew Gelman, John B Carlin, Hal S Stern, David B Dunson, Aki Vehtari, and Donald B Rubin. Bayesian data analysis. Chapman and Hal//CRC, 2013.
Mevlana Gemici, Chia-Chun Hung, Adam Santoro, Greg Wayne, Shakir Mohamed, Danilo Rezende, David Amos, and Timothy Lillicrap. Generative temporal models with memory. arXiv preprini arXiv 1702.00649, 2017.
Roger Grosse, Zoubin Ghahramani, and Ryan P Adams. Sandwiching the marginal likelihood using bidirectional monte carlo. arXiv preprint arXiv:1511.02544 2015.
Simon S Haykin. Adaptive filter theory. Pearson Education India, 2008
Ronald R Hocking. A biometries invited paper. the analysis and selection of variables in linear regression. Biometrics, 1976.
Joseph G Ibrahim, Ming-Hui
Chen, Yeongjin Gwon, and Fang Chen. The power prior: theory and applications. Statistics in medicine, 2015.
Max Jaderberg. Karen Simonyan, Andrew Zisserman, and Koray Kavukcuoglu. Spatial transformer networks. In Advances in Neural Information Processing Systems, 2015.
Edwin Jaynes. Probability theory: The logic of science. Cambridge university press, 2003.
Simon J Julier and Jeffrey K Uhlmann. New extension of the kalman filter to nonlinear systems. In Signal processing. sensor fusion, and target recognition VI. International Society for Optics and Photonics, 1997.
Rudolph Emil Kalman. new approach to linear filtering and prediction problems. Transactions of the JouEnJournal of Basic Engineering, 1960.
Richard Kurle, Botond Cseke, Alexej Klushyn, Patrick van der Smagt, and Stephan Günnemann. Con- tinual learning with bayesian neural networks for non-stationary data. In International Conference Learning Representations 2020.
Aodong Li, Alex Boyd, Padhraic Smyth, and Stephan Mandt. Detecting and adapting to irregular distribution shifts bayesian online learning. Advances in Neural Information Processing Systems, 2021.
10

---

Published as a conference paper at ICLR 2022
Kendall Lowrey, Aravind Rajeswaran, Sham Kakade, Emanuel Todorov, and Igor Mordatch. Plan online, learn offline: Efficient learning and exploration via model- based control. In International Conference Learning Representations, 2018.
Stephan Mandt, James McInerney, Farhan Abrol, Rajesh Ranganath, and David Blei. Variational tempering. In Artificial Intelligence and Statistics, 2016.
Adam Marblestone, Yan Wu, and Greg Wayne. Product kanerva machines: Factorized bayesian memory. arXiv preprint arXiv:2002.02385 2020.
Andrés R Masegosa, Darío Ramos-López, Antonio Salmerón, Helge Langseth, and Thomas D Nielsen. Variational inference over nonstationary data streams for exponential family models.
Mathematics, 2020.
Joseph Mellor and Jonathan Shapiro. Thompson sampling in switching environments with bayesian online change detection. Artificial Intelligence and Statistics, 2013.
Vincent Moens. The hierarchical adaptive forgetting variational filter. International Conference on Machine Learning, 2018.
Vincent Moens and Alexandre Zénon. Learning and forgetting using reinforced bayesian change detection. PLoS computational biology, 2019.
Bradley Monton. Sleeping beauty and the forgetful bayesian. Analysis, 2002.
Radford M Neal. Sampling from multimodal distributions using tempered transitions. Statistics and computing, 1996.
Radford M Neal. Annealed importance sampling. Statistics and computing, 2001.
Quoe Phong Nguyen, Bryan Kian Hsiang Low, and Patrick Jaillet. Variational bayesian unlearning. In Advances in Neural Information Processing Systems, 2020.
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. Advances in Neural Information Processing Systems, 2018.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems, 2007.
Lorenzo Rimella and Nick Whiteley. Dynamic bayesian neural networks. arXiv preprint arXiv:2004.06963, 2020.
Christian P Robert, George Casella, and George Casella. Monte Carlo statistical methods. Springer, 2004.
Simo Särkkä. fiterinn and smoothing. Cambridge University Press, 2013.
Daniel Simpson, Hävard Rue, Andrea Riebler, Thiago G. Martins, and Sigrumn H. Sørbye. Penalising Model Component Complexity: Principled, Practical Approach to Constructing Priors. Statistical Science, 2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 1933.
Jon Wakefield. Bayesian and frequentist regression methods. Springer Science & Business Media, 2013.
Yixin Wang, Alp Kucukelbir, and David M Blei. Robust probabilistic modeling with bayesian data reweighting, In International Conference Machine Learning, 2017.
Grady Williams, Nolan Wagener, Brian Goldfain, Paul Drews, James M Rehg, Byron Boots, and Evangelos A Theodorou. Information theoretic mpe for model-based reinforcement learning. In 2017 IEEE International Conference Robotics and Automation (ICRA). IEFE, 2017.

---

Published as a conference paper at ICLR 2022
Robert L Winkler. The assessment of prior distributions in bayesian analysis. Journal of the American Statistical association, 1967.
Daniel E. Worrall, Stephan Garbin, Daniyar Turmukhambetov, and Gabriel J. Brostow. Harmonic networks: Deep translation and rotation equivariance. IEEE Conference Computer Vision and Pattern Recognition, 2017.
Yan Wu, Greg Wayne, Alex Graves, and Timothy Lillicrap. The kanerva machine: A generative
distributed memory. International Conference Learning Representations, 2018.
Annie Xie, James Harrison, and Chelsea Finn. Deep reinforcement learning amidst lifelong non- stationarity. arXiv preprint Stti:22006.170.00 2020.
Jaesik Yoon, Taesup Kim, Ousmane Dia, Sungwoong Kim, Yoshua Bengio, and Sungjin Ahn. Bayesian aades-agnostic meta-learning In Advances in Neural Information Processing Systems, 2018.
Jeffrey O Zhang, Alexander Sax, Amir Zamir, Leonidas Guibas, and Jitendra Malik. Side-tuning: a baseline for network adaptation via additive side networks. In European Conference Computer Vision. Springer, 2020.
A EXAMPLES OF POSTERIORS WITH DECREASING VARIANCE
In this section we will provide two cases where the variance of the posterior is non-inerease ion-increasing with probability more data is collected, regardless of the observed data. For simplicity we stick to only ID, though we are confident these results extend to their multi-dimensional extensions.
A.I BAYESIAN ESTIMATION OF MEAN OF NORMAL DISTRIBUTION
The likelihood is of the form
p(yl0)= -N(,
(25)
where o² > is known. We use normal prior
p(0) N (Bu, To):
(26)
where T > 0. Given arbitrary data yı, yN ~ p(u).N) we get that the posterior is of the form
p(0 = W(ON,TN))
(27)
where
2
TN (Tō) + NNo 2)-1
(28)
0² + NTO
0x TN 10 + oor
yn
(29)
We observe that the posterior variance, equation 28, not a function of the observed data. In fact, the posterior variance is deterministic given N, and a², In this particular setting, we can show that TN a strictly decreasing function of N.
To prove that
Tn TN, it suffices to show that
Ta-1 Tas
Vn (1,...N),
(30)
which is cquivalent to showing that
1,
Vn. E (1,...N} NJ.
(31)
Before proceeding, we note that as Bayes' theorem closed under recursion, we can always express the posterior variance
o² 22T=-1
= (5n-1 +
-
(32)
0² Tn-1
12

---

Published as a conference paper at ICLR 2022
Computing Tn-Tn
Ta
0 T'Tn
1
(33)
7 1
r² nn-1
7n-
o²
(34)
0² Tn-1
Because
Tn > 0, Vn E {0,--. , we have that x² < 0² + Tn-1, and conclude that Tn/ Tn < 1.
(35)
A.2 BAYESIAN LINEAR REGRESSION
Next, we consider the setting of Bayesian linear regression with known variance. The likelihood is of the form
22 8) (Oxx; o²), 24 E R
(36)
where x² is known, We use normal prior
p(0) No0,, TO);
(37)
where Tp > the form
Given arbitrary observations (11, ...,, (Frs yn), we have that the posterior is of
p(O|Z1,N, M1NN) = N(NN:TN)
(38)
where
a N
TN
(39)
σ² To E F
N NN = TN(TO 10 + o
1
InDn).
(40)
n=1
To prove that To 2 2
Tn
TN, suffices to show that
Tn 1 Vr, E TR, Vn E (1, .N.
(41)
n-
Again, due to the Bayes being closed under recursion,
always rewrite the posterior variance as
T²T
(T + -222
(42)
0²
So
Tn
Tn
(43)
Tn
x2 + T
n
Tn-1
(44)
x2 + Tn T
As 2 2 O, we have that T./Tn-1 S which completes the proof.
B PROOF OF PROPOSITION 1
For clarity, we rewrite the proposition below Proposition. Let
De W.) p(0)
()D))))mm ==1
II
whs E (0,1), 1),
(45)
be the prior used in BAM and let
p(0 x (()
II ID,
(46)
be the recursive Bayes prior. Then
E. [Var(()) (o) 2 E(Var(0|D VA, E (0, 13.1
(47)
13

---

Published as a conference paper at ICLR 2022
Proof. We begin by describing some simple cases, before presenting the proof for the general case.
Case 1: All the readout weights are 1. If all the readout weights are 1, i.c W, then
<t, W; 1) - <()
(48)
recovering the recursive Bayes prior. Thus
E War( W, W, 1] E[Var(()
(49)
Case 2: All the readout weights are O. If all the readout weights are 0, i.e. W, then
D<t W, = 0) = =(())
(50)
recovering the base prior. The law of total variance states
Var(0) E. [Var(0) Dc))] Var(E[0 c.))-
(51)
As both terms on the right-hand side are positive, this implies that
Var W; = W) W. = 0] = Var(0) 2 [ar
(52)
Case 3: General case
Let r be the indices of the readout weight set to 1 ("remembered") and be the indices of the readout weights set to 0 ("forgotten")). We can express the memory buffer Dec D, U D, where D, the data points selected by the readout weights and Dr are the data points that are ignored. We can rewrite the BAM prior as
p(0 <t, W,) = p()(D,),
(53)
which is equivalent to applying Bayes theorem using D,- Similarly, we can rewrite the recursive Bayes prior
D()) = p() Dt) x p(Di)))p((1D..)
(54)
Using the law of total variance, we get
Var(0)Dea, W) = Var(o)D,) E (Vrr()) D.] Var (E|0
(55)
where again, the above implies
Var () 2 E. [Var
(56)
As the above inequality holds for all values of Dr, also holds under expectation as well
[[Var())D))[ 2 E [Var(0/Dex)
(57)
Since Var(O|D<a)) is the variance under the recursive Bayes model, it is not a function of W,, allowing the conditioning on W, be dropped
E Var(0) W.] E [Var(0/Dz))]
(58)
Applying our definition of D, recovers the desired result:
E ([Var(B|De.. Wi) W.] 2 E [V
(59)
C DISCUSSION OF GREEDY DISCRETE OPTIMIZATION
As the number of choices is (1111), it is impractical to use brute force methods for solving the discrete optimization problem defined in equation 21. For simplicity, we use two types of greedy approaches for discrete optimization. In both cases, each element in memory is evalu- ated against a target datum with the inner term of equation 19, the log marginal likelihood and regularization term. The first is bottom-up approach, where start with all readout weights set to and greedily add the most beneficial associated datum until the combined score de- creases. Pseudo code is displayed in Algorithm 1. Note that this is similar in spirit to the
14

---

Published as a conference paper at ICLR 2022
stepwise selection approach used for selecting variables in linear regression (Hocking, 1976).
Algorithm 1: Bottom- Up Greedy for BAM
Dota: memory Dices target D. p. regularizer strength priorscore +- log :
for sizerDD<s
for each D; in De: do if W/i] then
scoresli] +- log (P Dex)d0, + log (WW(ee)))
ebse
scores IIf
end
score, idi findmax(scorcs); If score priorscore then
W Widr]
priorscore e- scare: p posteriurip. (
else
return
end
end
Result: Readout weights W
In the second approach, the readout weight starts at O. The contribution of each datum in Des is evaluated independently (and can done practically in parallel with either multi-core CPUs or GPUs). These scores are filtered to only be scores better than the base prior's likelihood. The top 9% percentile remaining scores are chosen and their corresponding readout weight value are set to 1. Pseudo code is displayed in Algorithm 2. This approach is faster than bottom-up only one round of optimization is needed but the combination of each of the individual experiences could potentially lead to sub-optimal performance. Additionally, the percentile cutoff may needlessly include or exclude weight values.
In practice, found that the two approaches performed similarly with the main exception be- ing the MNIST experiment, where the parallel approach was significantly worse than bottom-up.
Algorithm 2: Parallel selection for BAM
Data: memory D.y., larget Dt, regularizer streugth A. prior distribution p. cutoll g priorscore log ; for each D; in D.c do scoresfil + log p(D. 0e (p). + logp(W
end
cutoff = quantile(scores > priorscore, i); for each scores
if sccoresfl > cutoff then
Wlil
clse
Wiil 0
end
end
Result: Readout weights W
D EXPERIMENTAL SETTINGS
D.I CONTROLS
For controls experiments, used Model Predictive Path Integral control (Williams et al., 2017). a model predictive control (MPC) algorithm with a planning horizon of 50 timesteps and 32 sample trajectories. Our sampling covariance 0.4 for each controlled joint-in the case of Cartpole, the action space is 1. The temperature parameter we used was 0.5.
Planning with a probabilistic model involves each sampling trajectory use a different model sampled from the current belief (as opposed to a sampled model per timestep); planning rollouts included noise, such that
2r _e-1 + M' ((z 0x) + Ex, E, ~ N=(00001),
(60)
where M' is sampled from the current belief. is the random Fourier features function from (Rahimi Recht, 2007) where we use 200 features with a bandwidth calculated as the mean pairwise distance of the inputs (states and actions) which is 6.0. To learn M, use Bayesian linear regression where
15

---

Published as a conference paper at ICLR 2022
each row of M is modeled being independent. We place multivariate Normal prior each of the rows with a prior mean of all Os and prior precision of 10 10-+I.
The Cartpole model's 's initial state distribution for positions and velocities were sampled uniformly from -0.05 to 0.05, with the angle of the cart being π such that it points down. This sets up the swing-up problem.
For the episodic one-shot experiment, we perform MPC for 200 timesteps as one trial. 15 trials make episode, with the dynamical properties of the environment (i.e. gravity) fixed for the duration of the trial. We vary the gravity parameter of the model by selecting gravity values from celestial bodies of the Solar System; At the start of new episode, each method's 's beliefs are reset to the base prior, and each method proceeds to update their respective beliefs accordingly. BAM retains each trail's datum memory across episodes.
used Earth, Mars, and Neptune at 9.81, 3.72, and 11.15 m/s² respectively.
For the continual learning experiment, we do not inform our agent that the model dynamics have changed, i.e. we never reset the agent's 's belief to prior. Instead, we use Bayesian Online Changepoint Detection (BOCD) to discern if the underlying model distribution has changed. BOCD is compared against BAM, both with and without changepoint detection; while BOCD resets prior when change detected, BAM optimizes for weight vector over the previously experienced data. The BOCD switching parameter À for its hazard function was set to 0.11. The agent attempts the task for 60 trials, with the environment experiencing changes 3 times during said trials.
D.2 DOMAIN ADAPTATION WITH ROTATED MNIST
We ran 10 independent Bayesian linear regressions, one for each dimension of the one-hot encoded target, As the prior. we use a multivariate Normal distribution with a prior mean of all Os and prior precision of 0.11. Similar to the controls experiment, we assume the additive noise is fixed and set to o² 10- As regularization had little effect, we set 0.
D.3 NON-STATIONARY BANDITS
For both UCB and UCBAM, we use a confidence-level function of f(t) + tto The timescale parameter for BOCD Thompson sampling is 0.016, which is the expected frequency of the arm switches. The weighting term for Bayesian exponential forgetting + Thompson sampling is 0.8.
D.3.1 DESCRIPTION OF UCBAM
The challenge of bandit settings is the need explore, especially in the non-stationary setting we devised. As such, UCB is well known algorithm for leveraging the uncertainty in the arm values to enable exploration. We combine this frequentist method with BAM as follows. When we assume to "know' the current best arm value, we exploit it and keep belief over its distribution with BAM. The signal for whether the best arm 'known' with our current arm belief or higher with the naive base prior. If the base prior produces higher likelihood, we assume the current arm distribution incorrect (and will be updated with BAM), and default to the UCB metric for arm selection. This simple combination of methods in this setting allows for the exploration benefits UCB with the quick recognition of high value arms due to BAM and subsequent exploitation.
the likelihood of the current arm's value is higher
16

---

Published as a conference paper at ICLR 2022
Arm Values, 10 Arms
1.0
0.5
Arm Values
0.0
-0.5
-1.0
500
1000
1500
2000
Time
Figure 5: For reference, the arm values of the bandit experiments without added noise (ar = 0.25). with only 2000 time steps for clarity. Each arm switches between high and low value at variable times, such that the highest value arm may be a previously low value arm. The simplest strategy would to find the highest mean value arm, which what UCB does in this case. Recursive Bayes attempts the same, but does not explore sufficiently to achieve an accurate estimate of the mean arm values.
Algorithm 3: UCBAM
Data: prior distribution p
K number of arms;
b == cppy(p), empty D. K times; belief and memory per arm known < false; for each iteration do
if known then
arm thompson(b1...k)
else
UCB choice
end
v < pull(arm):
if log(p(v)) > log(barm (u)) then
I known < false else
I known < true
end
barm BAM Darm v
# BAM posterior update
Der [De, 0
add value to memory
end
17


Reviews:
[{"review_id": "kkBdUwwVv8F", "reviewer": "Reviewer_4Gvr", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- The theoretical development is principled;\n\n- This approach seems to be novel (though I'm not familiar with the literature on Bayesian methods for non-stationary environments);\n\n- The paper is clearly written.\n\nConcerns:\n\nNone.\n\nMinor points:\n\n- In equations (11) and (12), shouldn't $\\theta_t$ be $\\theta$, as it is assumed not to change with $t$ here?\n\n- Equation (17) is just a normalisation constant. Since (14) and (16) are also given only up to constants, is it worthwhile to include?\n\n- Several times in section 2.1: \"preventing BAM from overfitting\" sounds like BAM won't overfit at all. Could you change the wording to reflect that regularisation reduces the chance/severity of overfitting, without preventing it altogether?\n\n- Below equation (23) and in appendix C: $(t-1)!$ should be $2^{t-1}$\n\n- Algorithm 1: While \"Bottom's Up\" [sic] is a nice name, I think the term you're looking for is \"Bottom-Up\" :)", "summary_of_the_paper": "In this paper, a method BAM is proposed for Bayesian learning in non-stationary environments: basically, at each time step, each previous datum may or may not be incorporated into the new posterior, so that old data from different states can be ignored, while old data from the same or similar states is remembered. The method doesn't rely on parametric assumptions. Experiments demonstrate it to work well in various scenarios.", "summary_of_the_review": "I enjoyed reading this paper. Assuming that this idea is as novel as claimed, I think this is a valuable contribution to the community and recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Z5kJfA_C3Dk", "reviewer": "Reviewer_o4TK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and easy to follow. The motivation is clear and the problem is well set. The proposed learning framework is a reasonable solution in principle. The experiments clearly demonstrate the benefit of BAM, especially its ability to adapt to the change of environments.\n\nHowever, I'm a bit skeptical about the practicability of the proposed framework. All the elements of the algorithm, including the posterior updates and greedy selection procedure, assume the traceability of the marginal likelihood, which is not true in most non-trivial real-world applications.  As the authors stated in the conclusion, one can introduce variational approximations or MCMC to conduct approximate inference, but these are way harder than it looks since now each evaluation of $p(\\theta_t|W, D_{<t})$ requires an iterative procedure requiring heavy computation until convergence, so the greedy selection procedure can be prohibitively time-consuming. As the authors pointed out when relating BAM to the existing works, and also suggested as future work, one can allow the selection variables $W$ to be any real number between $[0,1]$. Then we can resort to gradient-based approximate optimization techniques (e.g., based on variational approximation with Gumbel-softmax), but at this time it is not clear how accurate all such approximate inference techniques (especially for high-dimensional models such as deep neural networks applied to large-scale data). One should also think about an alternative prior $p(W|\\theta_t)$ because the KL-divergence needed for the current prior is intractable.\n\nSo my point is, there are many obstacles to be addressed if we are to extend the current BAM framework for realistic scenarios, and all of such issues pose their own research problems that might require contributions significant enough to write standalone papers. Therefore, I think the current submission is quite incomplete, although I agree that the research direction itself is interesting.\n\nAnother practical aspect that is worth pondering is how the proposed framework compares to existing continual learning techniques introduced for deep neural networks. There are plenty of works for deep continual learning, where the goal is to learn large-scale deep neural networks while taking a continuous stream of non-stationary task data. Existing continual learning techniques learn to adaptively forget or retain past experiences, and also try to minimize the cost of learning and the complexity of the model (minimize the unnecessary expansion of the model).  Especially, an important consideration in continual learning is that it typically assumes that an agent doesn't have access to the previous data ($D_{<t}$), but only to the model learned from it. This is a reasonable assumption because keeping all the past data requires huge memory. So the difficulty in continual learning comes from the fact that it should learn continuously adapting model which keeps a balance between 1) how much to forget and 2) how much to retain past experiences, without access to the previous data. For instance, variational continual learning (Nguyen et al., 2018) constructs a lightweight summary of previous data that can be used as a representative for the subsequent learning. As far as I can see, BAM assumes access to all the previous data whenever updating the posteriors, and this again can be a significant challenge for more realistic learning scenarios.\n\nI'm also quite confused with the name \"Bayes augmented with memory\". What does the \"memory\" stand for? If it is for the past data being used for the update of the posteriors, isn't the vanilla recursive Bayes also augmented with memory? The difference between BAM and the recursive Bayes is in BAM's use of the readout variable $W$, but I don't think the variable $W$ itself stands for the \"memory\".\n\nReferences\n(Nguyen et al., 2018) Nguyen, C. V., Li, Y., Bui, T. D., and Turner, R. E. Variational continual learning. ICLR, 2018.", "summary_of_the_paper": "This paper proposes a learning framework called Bayes Augmented with Memory (BAM), where a recursive adaptation of the Bayes formula is augmented with selection variables $W$ to allow an agent to adaptively choose past experiences to forget. The original recursive Bayes formula assumes the stationarity of the data generating distribution, so keep all the past data for updating the posteriors for newly arriving data, and thus always tends to decrease the variance of the posteriors as it is meant to be. However, this can severely fail when the stationarity assumption is violated; when an agent encounters a change in the environment, it should somehow discard the past experience and quickly adapt to new data. BAM explicitly models this procedure with the binary selection variables, and by greedily optimizing those selection variables at each entrance of new data, quickly adapt to the change of environment and still leverages the past experiences. Various experiments with non-stationary environments demonstrate the usefulness of the proposed framework.", "summary_of_the_review": "I think the proposed framework can be potentially interesting and useful, but at current presentation lacks many practical considerations to be dealt with, especially how it can be applied to non-trivial models requiring approximate inference for computing posteriors. It is quite disappointing thus to only see experiments on conjugate models. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4s825UcQCGK", "reviewer": "Reviewer_1Svc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In this paper, the authors propose a new framework, Bayes Augmented with Memory (BAM), that takes advantage of past experience by allowing the agent to choose which past observations to remember and which to forget and demonstrate that BAM generalizes many popular Bayesian update rules for non-stationary environments. The variety of experiments demonstrate the ability of BAM to continuously adapt in an ever-changing world.\n\nTo the best of my knowledge, this is generally a good paper with a clear central idea. I have only two minor concerns:\n\nFor simplicity, this paper focused on binary values for the readout weights as it allowed for a simple greedy discrete optimization algorithm to be used. This assumption limits its practical application scenarios.\n\nAlthough a simple greedy discrete optimization algorithm to be used, it still makes the proposed BAM have a relatively high time complexity. The paper could be improved if the authors can provide the time complexity of the proposed BAM. If it is difficulty, the comparison results in terms of the running time are needed.\n", "summary_of_the_paper": "In this paper, the authors propose a new framework, Bayes Augmented with Memory (BAM), that takes advantage of past experience by allowing the agent to choose which past observations to remember and which to forget and demonstrate that BAM generalizes many popular Bayesian update rules for non-stationary environments. ", "summary_of_the_review": "In this paper, the authors propose a new framework, Bayes Augmented with Memory (BAM), that takes advantage of past experience by allowing the agent to choose which past observations to remember and which to forget and demonstrate that BAM generalizes many popular Bayesian update rules for non-stationary environments. The variety of experiments demonstrate the ability of BAM to continuously adapt in an ever-changing world.\n\nTo the best of my knowledge, this is generally a good paper with a clear central idea. I have only two minor concerns:\n\nFor simplicity, this paper focused on binary values for the readout weights as it allowed for a simple greedy discrete optimization algorithm to be used. This assumption limits its practical application scenarios.\n\nAlthough a simple greedy discrete optimization algorithm to be used, it still makes the proposed BAM have a relatively high time complexity. The paper could be improved if the authors can provide the time complexity of the proposed BAM. If it is difficulty, the comparison results in terms of the running time are needed.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "0XEgCA3zGO1", "reviewer": "Reviewer_EUxk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper tackles an important problem of Bayesian online learning in a non-stationary environment. The main contribution is BAM, an algorithm that constructs an informative prior distribution for current observations based on stored previous data. While the method seems technically sound, the method still falls short of the following points:\n\n1) **Scalability**: the algorithm remembers all the data so far, which requires infinite memory in an ever-running system. So as to the computation. The algorithm will fail in an online learning environment. An immediate improvement would be to use a fixed memory. A similar idea occurs in continual learning with a memory system where people only select representative data into a fixed memory (see the following point).\n\n2) **Proper related work discussion**: At least there are two highly-related papers not mentioned in the current version:\n\n    - Li, Aodong, et al., “Detecting and Adapting to Irregular Distribution Shifts in Bayesian Online Learning”, NeurIPS 2021 (previously occurred in workshops).\n    - Kurle, Richard, et al., \"Continual learning with bayesian neural networks for non-stationary data.\" ICLR 2020.\n\n    *(Possibly) related work in other fields*:\n\n    *Continual learning with a fixed-size memory*:\n    - Aljundi, Rahaf, et al. \"Gradient-based sample selection for online continual learning.\" Advances in Neural Information Processing Systems 32 (2019): 11816-11825.\n\n    *Bayesian inference with weighted likelihood*:\n    - Wang, Yixin, Alp Kucukelbir, and David M. Blei. \"Robust probabilistic modeling with bayesian data reweighting.\" International Conference on Machine Learning. PMLR, 2017.\n    - Mandt, Stephan, et al. \"Variational tempering.\" Artificial Intelligence and Statistics. PMLR, 2016.\n\n3) **Large-scale experiments**: Current experiments are all analytical. However, practical systems could be complex, intractable, and large-scale in time. Without demonstrating the applicability in these environments, the approach may be not convincing.\n\n4) **Baseline comparisons**: The paper conducted thorough experiments with baselines including ordinary Bayesian online learning and BOCD. However, existing baselines have obvious limitations and couldn’t properly illustrate the benefits of the additional memory and re-visited states. More adaptive baselines like Bayesian Forgetting or Bayesian filter can be desirable to exemplify the usefulness of memory in a changing environment.\n\nOther additional comments/suggestions:\n* $p(W_t|D_{<t}) \\propto 1$: Should $W_t$ take some value?\n* May consider change colors in Fig. 1 (left). Hard to distinguish methods.\n* Fig. 5 is out of the main text.\n", "summary_of_the_paper": "The paper aims to solve the downside of the posterior shrinkage of Bayesian online learning when applied in a non-stationary environment. The previously posterior (a.k.a., the current prior) could be misspecified for current observations with the posterior shrinkage due to the environment change. To solve this misspecification problem, the proposed method constructs an adaptive prior that is correctly specified for current observations. This adaptive prior distribution is constructed by selecting the previous relevant data samples, which requires storing the whole history. The method is evaluated on various analytical experiments.", "summary_of_the_review": "The paper could be an interesting contribution in the area of Bayesian online learning in a non-stationary environment. However, unless solving the scalability problem and demonstrating the benefits of the memory, the paper isn’t persuasive enough.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The article introduces a Bayesian approach for online learning in non-stationary environments. The approach, which bears similarities with weighted likelihood estimation methods, associate a binary weight to each past observation, indicating if this observation should be including or not to compute the posterior. The weights are estimated via maximum a posteriori. 

The paper is well written, the approach is novel and its usefulness demonstrated on a number of different experiments. The original submission missed some relevant references that have been added in the revision. The approach has some limitations, highlighted by the reviewers:
* it requires to solve a binary optimisation problem whose complexity scales exponentially with the size of the dataset; although the greedy procedure proposed by the authors seems to work fine on the examples shown, the approach may not be applicable to larger datasets
* it requires to store all the data
* it requires the traceability of the marginal likelihood

Despite these limitations, there was a general agreement that this paper offers a novel and useful contribution, and I recommend acceptance. 

As noted by reviewer o4TK, I also think that the title is not very accurate. Bayesian methods naturally allow recursive updates of one's beliefs, and therefore have "memory". Maybe change the title for "Bayes with augmented selective/adaptive memory"?
Decision: Accept (Poster)