A unifying framework for generalised Bayesian online learning in non-stationary environments
Authors: Gerardo Duran-Martin
Leandro Sánchez-Betancourt
Alex Shestopaloff
Kevin Patrick Murphy
Venue: Accepted by TMLR ()

Abstract: We propose a unifying framework for methods that perform probabilistic online learning in non-stationary environments.  We call the framework BONE, which stands for generalised (B)ayesian (O)nline learning in (N)on-stationary (E)nvironments.  BONE provides a common structure to tackle a variety of problems, including online continual learning, prequential forecasting,  and contextual bandits. The framework requires specifying three modelling choices: (i) a model for measurements (e.g., a neural network), (ii) an auxiliary process to model non-stationarity (e.g., the time since the last changepoint), and (iii) a conditional prior over model parameters  (e.g., a multivariate Gaussian). The framework also requires two algorithmic choices, which we use to carry out approximate inference under this framework: (i) an algorithm to estimate beliefs (posterior distribution) about the model parameters given the auxiliary variable, and (ii) an algorithm to estimate beliefs about the auxiliary variable. We show how the modularity of our framework allows for many existing methods to be reinterpreted as instances of BONE, and it allows us  to propose new methods. We compare experimentally existing methods with our proposed new method on several datasets, providing insights into the situations that make each method more suitable for a specific task. We provide a Jax open source library to facilitate the adoption of this framework.

Published in Transactions on Machine Learning Research (03/2025)
A unifying framework for generalised Bayesian online learning in non-stationary environments
Gerardo Duran-Martin
9. g.duran@me.com
School of Mathemationl Sciences Queen Mary University of London,
Leandro Senchez-Betancoure
swnchechellam@mutttssooccc.cc
Mathematical Institute &
Oxford-Mon Mon Institute of Quantitative Finance University of Onford, UK
Alexander Y. Shestopaloff
a.shestopplolff@qmuucccoo
School of Mathematical Sciences Queen Mary University of London, UK & Deportment of Mathematics and Stotistics Memorial University of Newfoundland, Canada
Kevin Murphy
kpmurphyy@ooglee..mm com
Google Mind
Moutain View, CA, USA
Reviewed on OpenReview: https: openreview. net/ net/ forum? id- osesu2V10u
Abstract
We propose a unifying framework for methods that perform probabilistic online learning in non-stationary environments. We call the framework BONE, which stands for generalised (B)ayesian nO)lliee learning (N)on-stationary (E)nvironmenns. BONE provides a common structure to tackle a variety of problems, including online continual learning, prequential forecasting, and contextual bandits. The framework requires specifying three modelling choices: (i) a model for measurements (c.g., neural network), (fi) an auxiliary process to model non-stationarity (e-g,, the time since the last changepoint), and (iii) a conditional prior over model parameters (e.g,, a multivariate Gaussian). The framework also requires two algorithmic choices, which we use to carry out approximate inference under this framework: (i) an algorithm to estimate beliefs (posterior distribution) about the model parameters given the auxiliary variable, and (ii) algorithm to estimate beliefs about the auxiliary variable. We show how the modularity of our framework allows for many existing methods to be reinterpreted as instances of BONE, and it allows to propose new methods. We compare experimentally existing methods with our proposed new method on several datasets, providing insights into the situations that make each mothod more suitable for a specific task. We provide Jax open source library to facilitate the adoption of this framework.
1 Introduction
In this paper, we unify adaptive probabilistic methods that learn to make predictions about the next output Vt+ based on the next input 2;+1 and a sequence of past inputs and outputs, (# Vi.), where t indexes time. This often called prequential forecasting (Gama al., 2008), online learning (Zhang, 2023, Chapter 1), sequential online prediction (Liu, 2023).

---

Published in Transactions on Machine Learning Research (03/2025)
Many probabilistic prediction methods assume that the data generating process (DGP) p(y++1 z++1, Fi.t Vr:)) is static through time. However, real-world data often comes from non-stationary distributions, where the underlying data distribution changes, either gradually (e.g,, rising mean temperature) or abruptly (e.g., price shocks after a major news event). In this paper we propose a unified framework for tackling (one-step-ahead) lorecasts in such (potentially) non-stationary environments. Building on recent advances in generalised (psoudo) Bayesian methods (Bissiri et al., 2016; Knoblauch et al., 2022; Khan & Rue, 2023), we show that our framework unifies classical Bayesian approaches and naturally extends to methods derived from Bayes' rule. We demonstrate that all these methods are related to three-layered hierarchical state-space model, where the top layer captures changes in the data, the second layer governs the evolution of model parameters, and the third layer represents the observations.
Our framework accommodates and extends many existing lines of work, including online continual learning (Dohare et al., 2024), prequential (one-step-ahead) forecasting (Liu, 2023), test-time adaptation (Schirmer et al., 2024), neural contextual bandits (Riquelme et al., 2018), filtering (Basseville et al., 1993), and changepoint detection or segmentation (Gupla et al., 2024). For example, methods that were originally developed to tackle changepoint detection can be reinterpreted and applied within our framework to address wider range of sequential online lcarning problems. This flexibility allows us to gather tools that were designed for specific tasks-offtr studied in isolation within distinct subfields- unifying framework for handling non-stationarity across various application domains.
The framework we propose in this paper, which we call BONE which stands for (B)ayesian (O)nline learning in (N onttatiionryyy (E)uviromments- is based on a form of generalised Bayesian inference in a hierarchical model, and is composed of three modelling choices and two algorithmic choices. The modelling choices are: (M.1) model for the measurements, (M.2) an auxiliary process to model non-stationarity, and (M.3) a prior over model parameters conditioned on the auxiliary process and the past data. The algorithmic choices are: (A.1) an algorithm to compute an approximate posterior over the model parameters given the auxiliary variables, and (A.2) an algorithm to compute an approximate postcrior-or more generally, a set of weights over the auxiliary variables. We show how these different axes of variation span a wide variety of existing and new methods." To illustrate this, Figure 1 shows how various methods can be written within the BONE framework. Here, we categorised methods by how the auxiliary variable is used to model non-stationarity and how it influences the prior over model parameters before observing new data point.
Examples demonstrating the use of an easy-to-use library that implements these methods, written in Jax (Bradbury et al., 2018), are available at https: bttps://githul hoom/ggedm//Bn /BONE.
To summarise, our contributions are threefold: (1) we provide an extensive literature review on methods that tackle non-stationarity, and show that they can all be written as instances of our unified BONE framework; (2) we use the BONE framework to develop new method; and (3) we perform an experimental comparison of many existing methods and the new method on environments with both abrupt changes and gradually-changing distributions.
2 The framework
Consider sequence of measurements V1:r (y1...., .r) with y: E Rd, and (unmodelled) features T1.T (#I,... (#1,...,,T) 2T) with a; E R2. Let D. = (æ,, yı) be a datapoint and Di.r = (Di...., Dr) the dataset at time T. Consider a conditional probabilistic model for yr, conditioned on æ,, and parametrised by O, e R", given by p(y: 0,, x.), and sometimes called the likelihood.
Assume that the conditional mean for ye is encoded in a parametric model 1(Or, æt); e.g., a neural network. A popular modelling choice for regression problems is to assume that p(y: 2x) = -N h(0,, æz), R2) for known covariance R,, Next, assume there exists auxiliary variable 4/, E I that evolves following the
BONE is designed for sequential prediction with time-indexed data, thus, it does not aim to find "global" fit over all possible data points. Instead, BONE focuses adaptive strategies that forecast the next datapoint (one at time). This is in contrast to global optimisation approaches, such as Luo et al. (2024), which focus on finding the best global model for all datapoints. There are a number of probabilistic methods that handle non-stationarity and not included in BONE. For example, Scalzo et (2021) and de Vilmarest & Wintenberger (2021) do not decouple the modelling non-stationarity and the modelling over model parameters, thus, they cannot be written within our formulation.
2

---

Published in Transactions on Machine Learning Research (03/2025)
Adams MacKay (2007)
abrupt with reset
Fearnhead & Liu (2007)
Wilson et al. (2010)
Knohlauch al. (2018)
Chang & Athans (1978)
mixture experts
Chaer al. (1997)
Liu (2023)
Ahélès et al. (2024)
Discrete auxiliary variable
choose from replay buffers
Nguyen et al. (2017)
al. (2021)
sbrupt and gradual
Fearnhead & Liu (2011)
New method in (19)
Continuous auxiliary variable
weighted from replay buffers
Nasmar et al. (2022)
Kurle et al. (2019)
degree forgetting
Titsias al. (2024)
No auxiliary variable
Galashov et al. (2024)
constant: change
Chang et al. (2023)
known dynamics
Kalman (1960)
Figure 1: Overview of BONE methods grouped by the qualitative nature of the auxiliary variable and the conditional prior. See Table 3 for detailed breakdown of these methods.
dynamics p(th (4-1) and encodes information about the non-stationarity of the sequence at time t. Here, V, is the set of possible values of the auxiliary variable tha The purpose of this variable is, for instance, to determine which past datapoints F1.1-1 most closely align with the most recent measurement ye. We describe the auxiliary variable in detail in Scction 2.4. Finally, the model paramctors 0g evolve following the dynamics p(0, 0,-1, We). This represents how much parameters change, given the stale of the auxiliary variable.
Figure 2 shows the probabilistic graphical model that motivates our formulation; this resembles the one in Doucet et al. (2000) with additional optional dependence between the auxiliary variable and the measurements; in what follows omit this dependence for brevity.
For an experiment of length T' E N, the joint conditional density over the model parameters, induced by the graphical model shown in Figure 2, is given by
T
P(yrrr Over, Vorl x1:T) = p(0v) p(p))) II
p(vn 0, p(0, 0: vh) (0 p(de) x1)))
(1)
1=1
In this paper, we are interested in methods that efficiently compute the so-called expected posterior predictive 0t+1 := Pp wr (M.,) #141)] in an online and recursive manner. our setting, one observes 04++1 just. before observing Ve+1; thus, make a prediction about Yt+1, we have I++1 and Di:t our disposal. For the case of a discrete auxiliary variable v/, v,, the form of the expected posterior predictive for yt+1; induced
2The input features F++1 and output measurements Ut+1 can correspond different time steps. For example, 2t+1 can be the of the stock market fixed date and yt+1 the return on stock some days into the future.
3

---

Published in Transactions on Machine Learning Research (03/2025)
--
4/r
0
0++1
yt-1
y+
y
27
at 0++1
Figure 2: Two-levelled hierarchical state-space model (SSM) with known dynamics, motivating our BONE framework Solid arrows indicate required dependencies, while dashed arrows represent optional dependencies. Rectangles denote exogenous variables, and circles represent random variables. Observed elements are shaded in gray. The left shift. in æ; represents that features observed before observing y:-
by (1),
Úc+1 Ep(ee.. Da.) (h,))h(O,, 2.+1)
=E
p( the Diaeddo,
(2)
plere p / (100))/(((..0)) h(01, 1/, Di.)do,,
Σ NEEV
where
p(021 w/, Da:e) plve 0,, xx) p(0e the D1:t-1);
(3)
p(0, 1 the D 1) = p(0, 00-1, we) p(0,-1 11 d0
(4)
p( 1 Diat) p( D4, vh, D
Σ
p(u--1 (1 D
(5)
From (2), (3), (4), and (5) we argue that there are three key modelling choices and two algorithmic choices. Specifically, the three key modelling choices are: (M.1) the conditional mean 1(0, x) together with the likelihood p(y 0, æ); (M.2) the auxiliary variable dh: and (M.3) the conditional prior p(0, the Dra-1). Additionally, the two algorithmic choices are: (A.1) the algorithm compute (or approximate) the conditional posterior over model parameters p(0; 1/, Dıæ), and (A.2) the algorithm that computes (or approximates) the posterior over weights p(vh,, (D..).
The BONE framework generalises these choices, allowing for greater flexibility while maintaining the motivating probabilistic structure. Instead of the likelihood model p(y (;, with conditional mean h(6,, æz), we consider a general function exp(-f(y;; 0,, ax)),, where f(y:: 0z, could be either loss function or a log- likelihood. Next, instead of the conditional prior p(O; v/, D1a-1), we introduce a more general modelling function, 7 (0,; th,, 1). that governs the prior over model parameters." 3 Similarly, instead of the posterior density p(0,1 th, Pı:), we employ the function g(0; vh, Di.):: e.g., an approximation of the posterior,
3This function adopts ad hoc approach to parameter evolution instcad of explicitly solving the integration step (4). In Appendix C, we detail how the inference is carried when the dynamics known. More precisely, conduct full-Bayesian treatment by calculating the posteriar model parameters t++ and using this for inference.
4

---

Published in Transactions on Machine Learning Research (03/2025)
generalised posterior (Bissiri et al., 2016). Finally, instead of the posterior over weights p(t Pı:)), we consider a weighting function ((tr: Dıa), which can be the Bayesian posterior or an ad-hoc time-dependent weighting function.
This generalisation important because unifies a wide range of existing methods under a common framework. Many well-known approaches the literature can be written as elements of BONE by appropriately selecting the model for measurements, the conditional prior, and the posterior approximations. BONE highlights connections between different methods, it also enables systematic comparisons under common umbrella, and it allows us to develop novel algorithms. Table 1 explicitly contrasts the choices in BONE with those in the classical Bayesian formalism.
component
BONE
Bayes
(M.1: model)
h(O,, ax) & exp exp(-E(y::: O,, 2x))
h(O,, Φ+) & p(y: O,, vx,)
(M.2: auxvar)
(M.3: prior)
(0,; the) = x(0,; w/+ 1
p(O, the D1.t11)
(A.1: posterior)
(0(0))))) = q(Oi 1he, Di:e)
p(0, the, Dise)
(A.2: weighting)
(e(1)) ((1i;; 11.))
p(ve. Dia)
Table 1: Components of the BONE framework.
With these modifications, the expected posterior predictive under BONE is
/
ÿt = E P1a))
h(00, g(O:: ve, D1a) d0..
(6)
VIEV (A.2: weighting)
(M.1: model) (A.1: posterior)
where
(0, sh. Di.e) x (0r; vr, D1.--) exp(-((y:: Oz, xz))
(7)
(M.3: prior)
(M.1: model)
takes the form of generalised posterior (Bissiri et al., 2016). In classical Bayesian setting, the loss function takes the form of the negative log- liceiiool, i.c.,
E(y;; 0, ..) - log 0g, .x))
Unless stated otherwise, we work with the negative log- ligeellldoodd in (8) found in the classical Bayesian setting.
A prediction for you1 given Dis ae41, and the is
= Eyg [h(O;; 21+1) [ := f h(e;;
th, Di.)dd..
(9)
Here we use the shorthand notation = ((;;; the DT.)) and Ey [b] to highlight dependence on v/2-
Algorithm provides pseudocode for the prediction and update steps in the BONE framework. Notably, these components can be broadly divided into two categories: modelling and algorithmic. The modelling components determine the inductive biases the model, and correspond h, f, v/, and æ. The algorithmic components dictate how operations are carried out to produce final prediction this corresponds to qe and 44
5

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 1 Generic predict and update step of BONE with discrete the at time L.
Require: Dia // past data
Require: 2++1 // optional imputs
Require: h(O, æz) // Choice of (M.1: model)
Require: Pr // Choice of (M.2: auxvar)
for th E W do
2: (0s;; th)) +- =(0s; vh, Dia-1) // choice of (M.3: prior)
3: q:(0;; th) t q(0;; Ve, D1a) x Te( th2) exp(-f(y:;0, (,
choice (A.1: posterior)
4: ve(1))) v(pee D1a) // choice of (A.2: weighting)
5: 9i41 + Eg [h(Oe, m+tt); the]
conditional prequential prediction
6: end for
7: De+1 + Ev, (((tr) v(+1) // weighted prequential prediction
2.1 Example tasks that can be solved with BONE
Before going into more detail about BONE, we give some concrele examples of tasks in which the BONE framework can be applied. We group these examples into unsupervised tasks and supervised tasks.
2.1.1
Unsupervised tasks
Unsupervised tasks involve estimating unobservable quantities of interest from the data Dia- Below, we present three common tasks in this category.
Segmentation Segmentation involves partitioning the data stream into contiguous subsequences or "blocks" [Dia, Dig+ where the DGP for each block is governed by sequence of unknown functions (Barry & Hartigan, 1992). The goal is to determine the points in time when new block begins, known changepoints. This is useful in many applications, such as finance, where detecting changes in market trends is critical. In this setting, non-stationarity assumed to be abrupt and occurring at unknown points in time. We study an example in Section 4.3.1. For a survey of segmentation methods, see c.g, Aminikhanghahi & Cook (2017); Gupta et al. (2024).
Filtering using state-space models (SSM) Filtering estimates underlying latent state 0, that evolves over time (often representing meaningful concept). The posterior estimate of O, is computed by applying Bayesian inference to the corresponding state space model (SSM), which determines the choice of (M.1: model), and how the state changes over time, through the choice of (M.3: prior). Examples include estimating the state of the atmosphere (Evensen, 1994), tracking the position of a moving object (Battin, 1982), or recovering signal from noisy system (Basscville et al., 1993). In this setting, non-stationarity is usually assumed to be continuous and occurring at possible time-varying rates. For a survey of filtering methods, see e.g., Chen et al. (2003).
Segmentation using Switching stace models (SSSM) In this task, the modeller extends the standard SSM with a set of discrete latent variables Ni E [I,... K), which may change value at cach time step according to a state transition matrix. The parameters of the rest of the DGP depend on the discrete state v/., The objective is infer the sequence of underlying discrete states that best "explains" the observed data (Ostendorf et al., 1996; Ghahramani & Hinton, 2000; Beal al., 2001; Fox al., 2007; Van Gael et al., 2008: Linderman et al., 2017). In this context, non-stationarity arises from the switching behaviour of the underlying discrete process.
2.1.2 Supervised tasks
Supervisod tasks involve predicting measurable outcome y:- Unlike unsupervisod tasks, this allows the performance of the model to be assessed objectively, since we can compare the prediction the actual observation. We present three common tasks in this category below.

---

Published in Transactions on Machine Learning Research (03/2025)
Prequential forecasting Prequential (or one-step-ahead) forecasting (Gama et al., 2008) seeks to predict the value Dt+1 given D1a and #++1- This is distinct from time-series forecasting, which typically does not consider exogenous variables It. and thus can forecast (or "roll out") many steps into the future. We study an example in Section 4.1. For a survey on prequential forecasting under non-stationarity, see c.g., Lu et al. (2018).
Online continual learning (OCL) OCL is a broad term used for learning regression or classification models online, typically with neural networks. These methods usually assume that the underlying data generating mechanism could shift. The objective of OCL methods is to train model that performs consistently across both past and future data, rather than just focusing on future forecasting (Cai et al., 2021). The changepoints (corresponding to different. "tasks") may or may not be known. This setting addresses the dilemma, focusing on retaining previously learned knowledge while adapting to new tasks. We study an example of OCL for classification, when the task boundaries are not known, in Section 4.1.2. For survey on recent methods for OCL, see e.g., Gunasekara et al. (2023).
(Non-stationaryy contextual bandits In contextual bandit problems, the agent is presented with fea- tures 1t+1, and must choose an action (arm) that yields the highest expected reward (Li et al., 2010). We let Yo+1 E IR where A > 2 is the number of possible actions; this is vector where the a-th entry contains the reward one would have obtained had one chosen arm a. Let y: (()) be the observed reward time t after choosing arm a, i.c., the a-th entry of yv- A popular approach for choosing the optimal action (while tackling the exploration-exploilatioo tradeoff) at each step is Thomson sampling (TS) (Thompson, 1933), which in our setting works as follows: first, sample parameter vector from the posterior, O, from q(0;; the Dıa); then, greedily choose the best arm (the one with the highest expected payoff), at+1 arg max, 0.4), where (at+1), The goal is to seleet f++1 h(00;; 1)) and 0l4) is the a-th entry of Úc+1; finally, reccive reward V1+1
sequence of arms {.,,..., aT) .r) that maximises the cumulative reward Ex yi y(aa), When the mapping function h is a neural network, this model is called neural bandit. TS for neural bandits has been studied in many papers, see e.g., Duran-Martin et al. (2022) and references therein. Non-stationary bandits have been studied in Mellor & Shapiro (2013); Cartea et al. (2023a); Alami (2023); Liu et al. (2023). We study an example in Section 4.2.
2.2 Details of BONE
In the following subsections, we describe each component of the BONE framework in detail, provide illustrative examples, and reference relevant literature for further reading.
2.3 The measurement model (M.1)
Recall that h(0,2) x) is a parametric model that encodes the conditional mean for y, given O and æ. For linear measurement models, h(0,ar x)) is given by:
@Tx
(regression), y E IR (binary classification), y E {0. 1} (mmlti-class classification). y E {0, 1]c
h(0, x)-
(0Tx)
(10)
Softmax((Taz)
where o(z) = (1 + exp(-2))~ is the sigmoid function, C E N is the number of classes, Softmax(z); exp(2x)/2 exp(2;) represents the softmax function with z E Rd and z the i-th element of z. In the machine learning literature, the vector z is called the logits of the classifier. For non-linear measurement models, such as neural networks, 1(0,x)) represents the output of the network paramcterised by 0. The best choice of h will depend on the nature of the data, as well as the nature of the task, in particular, whether supervised unsupervised. We give some examples in Section 4.
7

---

Published in Transactions on Machine Learning Research (03/2025)
2.4 The auxiliary variable (M.2)
The choice of auxiliary variable d) is crucial to identify changes in the data-generating process, allowing our framework track non-stationarity. Below, we give a list of the common auxiliary variables used in the literature.
RL (rumlength): 1 = E (o. is scalar representing lookback window, defined as the number of steps since the last regime change. The value T = 0 indicates the start of a new regime at time t, while To 2 denotes the continuation of regime with a lookback window of length rr. This choice of auxiliary variable is common in the changepoint detection literature. See e.g., Adams & MacKay (2007); Knoblauch et al. (2018); Alami et al. (2020); Agudelo- España et al. (2020); Altamirano et al. (2023); Alami (2023). This auxiliary variable is useful for non-stationary data with non-repeating temporal segments, provided we know the intensity with which new segments appear.
RLCC (runlength and changepoint count): t/2 (r), E (0....,.t .. x (0...... . is a vector that represents both the runlength and the total number of changepoints, as proposed in Wilson et al. (2010). When rı 4, this implies C2- = 0, meaning no changepoints have occurred. Conversely, Te = 0 indicates the start of a new regime and implics a E (1....,t), .t), accounting for at least one changcpoint. For a given Tt 2 0, the changepoint As with RL, this auxiliary variable assumes consecutive time blocks, but additionally allows us estimate the likelihood of entering a new regime by tracking the number of changepoints seen so far. This auxiliary variable is useful for non-stationary data with non-repeating temporal segments when the intensity with which new segments appear is unknown.
count et belongs to the range (l....,4- -., rt).
CPT (changepoint timestep): 1i = St. with S = (S........G..l ),,r), is a set of size E (O....t) containing the times at which there was a changepoint, with the convention that 0 S C1, < S2 < < Cr., S t. This choice of auxiliary variable was introduced in Fearnhead & Liu (2007) and has been studied in Fearnhead & Liu (2011); Fearnhead & Rigaill (2019). Under mild assumptions, it can be shown that CPT is equivalent. to RL, see e.g., Knoblauch & Damoulas (2018). This auxiliary variable is useful for non-stationary data with non-repeating temporal segments when the probability of new segment appearing is unknown and knowledge of the changepoint location is required.
CPL (changepoint location): 2/2 = $1. E f0, 13 is a binary vector. In one interpretation, s; 1 indicates the occurrence of a changepoint at time i, as in Li el al. (2021), while in another, it means that D. belongs to the current regime, as in Nassar et al. (2022). This auxiliary variable is useful for non-stationary data with repcating temporal segments. It is uscful when the segments are formed of non-consocutive datapoints.
CPV (changepoint probability vector): die = u1a E (0,1)) 1)a is i-dimensional random vector representing the probability of each element in the history belonging to the current regime. This generalises CPL and was introduced in Nassar et al. (2022) for online continual learning, allowing for a more fine-grained representation of changepoints over time. This auxiliary variable is useful for non-stationary data with repeating temporal segments. Unlike CPL, it takes a vector of weights in (0, 1) which allows for higher flexibilty when compared to CPL.
CPP (changepoint probability): v = vs E (0, 1) represents the probability of a changepoint. This is a special case of CPV that tracks only the most recent changepoint probability; this choice was used in Titsias et al. (2024) for online continual learning.
ME (mixture of experts): 1 a, E (1,..., K} represents one of K experts. Each expert corresponds to either a choice of model or one of K possible hyperparameters. This approach has been applied to filtering (Chaer et al., 1997) and prequential forecasting (Liu, 2023; Abélès et al., 2024). This auxiliary variable facilitates the weighting of predictions made by models when one has a fixed number of competing models.
C: 1/2 = represents a constant auxiliary variable, where is just a placeholder or dummy value. This is equivalent to not having an auxiliary variable, or alternatively, to having a single expert that encodes all available information.
Space-time complexity There is a tradeoff between the complexity that va is able encode and the computation power needed to perform updates. Loosely speaking, this can be seen in the cardinality of
8

---

Published in Transactions on Machine Learning Research (03/2025)
the set of possible values of du through time. Let v be the space of possible values for th.. Depending the choice of the, the cardinality of V either stay constant or increase over time, iee. ;- C v, for all t = l,.,..,, T. For instance, the possible values for RL increase by one at each timestep; the possible values of CPL double at cach timestep; finally, the possible values for ME do not increase. Table 2 shows the space of values and cardinality that Ve takes as a function of the choice of auxiliary variable.
name
C
CPT 2
CPP J0,
CPL
CPV
ME {l...,,) K}
RL
RLCC ([0.4)...... (t,0))
values cardinality
{c)
(0, 1)3
(0, 1)*
(0.1.....t)
2'
oc
2
inf
+ t(t + 1)/2
Table 2:
Design space for the auxiliary random variables the, Here, T denotes the total number of timesteps and K denotes a fixed number of candidates.
2.5
Conditional prior (M.3)
This component defines the prior predictive distribution over model parameters conditioned on the choice of (M.2: auxvar) vu, and the dataset Dia-1- In some cases, explicit access to past data is not needed.
For example, a common assumption is have Gaussian conditional prior over model parameters. Tn this case, assume that, given data D1:-1 and the auxiliary variable 1h, the conditional prior takes the form
T6 v/,, 11=-1) (O 9 (th, P1r-1); Ge D1a-1)),
(11)
with 9t Mr x (tm+t)(t--)) + R" a function that returns the mean vector of model parameters, EiO: 1/, D1,- and G. : D x R(m+d)(t-1) - mm a function that returns a m-dimensional covari- ance matrix, Cov[O, b., Dia-i]. In what follows, we let (Mo. Eo) be the pre-defined initial prior mean and covariance. Furthermore, we denote (14-1, E,1) be the posterior mean and covariance found at time - 1, which is used as a prior time
Below, we provide non-exhaustive list of possible combinations of choices for (M.2: auxvar) and (M.3: prior) of the form (11) that can be found in the literature, and we also introduce new combination.
C-LSSM (constant linear with affine state-space model). We assume the parameter dynamics can be modeled by a Ganssian state space model (LSSM), i.c., EiO, 0.-1] = Fe 9 + b, and Cov[o, C = Qs for given (m m) dynamics matrix F,, (m x 1) bias vector b,, and (m x m) positive semi-definite matrix Q.- We also assumee th: c is fixed (dummy) constant, which equivalent not having an auxiliary variable. The characterisation of the conditional prior takes the form
(e,c, 112-1) = F, 14-1 + b., G. D1a-1) = F, ET + Q
(12)
This is a common bascline model that we will specialise below.
C-OU (constant with Ornstein-Uhlenbeck process). This is a special case of the C-LSSM model where F, = ?I, b. = (1 - -7) Q, = (1- - ~2) E. = I 7 E [0, 1] is the fixed rate, and a 2 The conditional prior mean and covariance are convex combination of the form
g(c, D1a-1) = 7/411 + (1-7) = G(c,, - -,, + (1 72
(13)
This combination is used in Kurle et al. (2019). Smaller values of the rate parameter y correspond to faster resetting, i.e., the distribution of model parameters revert more quickly to the prior belief (Ho, En), which means the past data will be forgotten.
CPP-OU (changepoint probability with probability that we use as the rate of an Ornstein-Uhlenbeck (OU) process, as proposed in Titsias al. (2024); Galashov al. (2024). The characterisation of the conditional prior takes the form
Ubleebbce process). Here dù = i E [0, 1] is the changepoint
g(v, D1=-1) = 14 1 + (1 vt)
(14)
1 + (1 of Eg. G(v,, D1.-1) = E
9

---

Published in Transactions on Machine Learning Research (03/2025)
An example how to compute vt using empirical Bayes procedure is given in (42).
C-ACI (constant with additive covariance inflation). This corresponds to special case of C-LSSM in which F = I, b = O, and Q= al for a > 0 is the amount of noise added at each step. This combination is used in Kuhl (1990); Muran-Martin et al. (2022); Chang et al. (2022; 2023) The characterisation of the conditional prior takes the form
((.-11 14-1+ G(e, D1.t1) E, + Q:-
(15)
This is similar C-OU with y however, here we inject new noise at each step. Another variant of this scheme, known shrink-and-perlun (Ash & Adams, 2020), takes g(c, 11=-1) 9 and (1a-) Σ, + Qu, where 0 < is the shrinkage parameters, and Q: o
C-Static (constant with static parameters). Here 1/2 = c (with c dummy variable). This is a special case of the C-ACI configuration in which a = 0. The conditional prior is characterised by
gole, DI.-1) 14-1
(16)
Gr(c, D1:t-) E.
ME-LSSM (mixture of experts with LSSM). Here vi = 04 {1...., K}, and we have a bank of K independent LSSM models; the auxiliary variable specifies which model to use at each step. The characterisation of the conditional prior takes the form
(o D1a-1) = p((x)) (ac)
14-1 + (ax)
(17)
Ge(ar, D1a--) = f(a)) > (0) F. (a.).
The superscript (at) denotes the conditional prior for the k-th expert. More precisely, p[_) E are the posterior at time L using p(n) and Q,")) from the k-th expert. This combination was introduced Chaer al. (1997).
RL-PR (rumlength with prior reset): for 4h = re, this choice of auxiliary variable constructs mean and covariance considering the past - rt observations. We have
ge(ri, D1a-1) = 14 (r: = 0) + 1 (m 1 1rr > 0),
(18)
G.(ri, D1=-1) = En 11 (r: = 0) + E (r..)) (r: > 0),
where (( (r.-i) denotes the posterior belief computed using observations from indices t- rt to 1. The case Tt = 0 corresponds to choosing the initial pre-defined prior mean and covariance M4 and Eg. This combination assumes that data from a single regime arrives in sequential blocks of time of length rt. This choice of (M.3: prior) was first studied in Adams & MacKay (2007).
[1]-UUR (greedy runlength with OU and prior reset): This is new combination we consider in this paper, which is designed to accommodate both gradual changes and sudden changes. More precisely, we assume 1/ = rt, and we choose the conditional prior as either a hard reset to the prior, (e(r)) >> E, or a convex combination the prior and the previous belicf state (using an OU process), if (r(r $ E. That is, we define the conditional prior as
Mo (L-r((r)) + M6)) ve(re) (((r)
v((r)) > E, u((1)) Se,
(r,, D1---))
(19)
140
En (1 - (r(r)))) + E()) ur(ri)2 ur(r)) > e,
Gelri, D1=-1)=
(20)
En
m(()) Se.
Here (r(r)) p(re Pi.), with r, = rt- 1, the probability we are continuing a segment, and (r.)) with Ft the probability of changepoint. For details on how to compute (r(r,), see (37). The value of the threshold parameter controls whether an abrupt change or gradual change should take place. In the limit.
10

---

Published in Transactions on Machine Learning Research (03/2025)
when 1, this new combination does not learn, since it is always doing hard reset to the initial beliefs at time / = 0. Conversely, when O, we obtain an OU-type update weighted by When e = 0.5, we revert back to prior beliefs when the most likely hypothesis is that a changepoint has just occurred. Finally, we remark that the above combination allows us to make use of non-Markovian choices for (M.1: model), as we see in Section 4.3.1. This is, the best. of our knowledge, new combination that has not been proposed the previous literature; for further details see Appendix A.3.
CPL-Sub (changepoint location with subset of data): for 2/. St41 this conditional prior constructs the mean and covariance as
(e(L, D1a-1) (osa-1))
(21)
Gi(Sia, D1a-1)= -===-ig (11a-1))
where (1) (1)))))) denotes the posterior belief computed using the observations for entries where $1t-1 have value of 1. This combination assumes that data from the current regime is scattered from the past history. That is, it assumes that data from a past regime could become relevant again at later date. This combination has been studied in Nguyen al. (2017).
CPL-MCI (changepoint location with multiplicative covariance matrix): for di = $1:1, this choice of conditional prior maintains the prior mean, but increases the norm of the prior covariance by constant term 3 E (0, 1). More preciscly, we have that
9e(81 Di:e-1)= -M
8-1
8- E (sta-1)
8t 1,
(22)
Ge(S1a, D1-0-1)=
E (snn-1)
8, 0.
This combination was first proposed in Li et al. (2021).
CPT-MMPR (changepoint timestep using moment-matched prior reset): for th, = Se. with S. = (G..t....,,e.. and Se, the position of the last changepoint, the work of Fearnhead & Liu (2011) assumes dependence structure between changepoints. That is, to build the conditional prior mean and covariance, they consider the past D datapoints whenever Ç.. S t 1 and a moment-matched approximation the mixture density all possible subset. densities since the last changepoint whenever Ce l. For example of MMPR with RL choice of (M.2: auxvar), Appendix A.2.
2.6 Algorithm to compute the posterior over model parameters (A.1)
This section presents algorithms for estimating the density q(Or; the, Di.e); we focus on methods that yield Gaussian posterior densities. Specifically, we are interested in practical approaches for approximating the conditional Bayesian posterior, as given in (7).
There is a vast body of literature on methods for estimating the posterior over model parameters. Here, we focus on three common approaches for computing the Gaussian posterior: conjugate updates (Cj), linear- Gaussian approxinations (LG), and variational Bayes (VB). For an overview of choices of (A.l: posterior) and comparison in terms of their computational complexity, see Table 3 in Jones et al. (2024).
2.6.1 Conjugate updates (Cj)
Conjugate updates (Cj) provide classical approach for computing the posterior by leveraging conjugate prior distributions. Conjugate updates occur when the functional form of the conditional prior π ( vr, D1:-1) matches that of the measurement model P(u+ 0, æx) (Robert et al., 2007, Section 3.3). This property allows the posterior to remain within the same family as the prior, which leads to analytically tractable updates and facilitates efficient recursive estimaiion.
A common example the conjugate Gaussian model, where the measurement model is Gaussian with known variance and the prior multivariate Gaussian. This results closed-form updates for both the mean and covariance. Another example is the Beta-Bernoulli pair, where the measurement model follows Bernoulli
11

---

Published in Transactions on Machine Learning Research (03/2025)
distribution with unknown probability, and the prior is a Beta distribution. See e.g., Bernardo & Smith (1994); West & Harrison (1997) for details.
The recursive nature of conjugate updates makes them particularly useful for real-time or sequential learning scenarios, where fast and efficient updates are crucial.
2.6.2 Laussin approximation (LG)
The linear-Gaussin (LG) method builds on the conjugate updates (Cj) above. More precisely, the prior is Gaussian and the measurement model is approximated by a linear Gaussian model, which simplifies computations.
The prior over model parameters taken as:
π (0 the Dia-1) = (0. (0.1m-1 u
(0r) x
(23)
(ilt) where P4-1 and (w))) are the mean and covariance, respectively. We use the measurement function h to define first-order approximation ht around the prior mean which is given by
he vz) (10) 2.) + H. (0: p
(16)
(24)
Here, H, is the Jacobian of h(0, æ.) with respect to 0, evaluated at p1-1. The approximate posterior measure is given by
((0,; we, D1.)) x Noy hh (0,, R2),, R.) (0,; vh, D1a-1) = -M he xz). R. (0. 1 ((())) W(0 m4 (wc) Σ ()),
(1b)
(25)
where R2 is a known noise covariance matrix of the measurement yo Under the LG algorithmic choice, the updated equations are
w h M1-1, Lt
(12)
s((() = H. H + R.,
K (wh) ((U)) H (s(*M)
(26)
He (8)) = 1 + (1)) y/: 0 ).
M (1)) [ (w)) ( (s) (K(*))
This linear approximation enables efficient computation of the posterior in Gaussian form. Examples include the extended Kalman filter (EKF) (Haykin, 2004), which applies local linearisation to non-linear systems, the exponential family EKF (Ollivier, 2018), which approximates the measurement model as Gaussian by matching the first two moments, and the low-rank Kalman filter (LoFi) method (Chang et al., 2023), which (DLR) posterior precision matrix. See Särkkä Svensson (2023) for more details on such Gaussian filtering methods.
assumes a diagonal-pluu-low--r
2.6.3 Variational Bayes (VB)
Variational Bayes (VB) popular method for approximating a postcrior distribution of model paramoters by choosing parametric family (such as Gaussians) that computationally tractable. The primary objective of VB is to minimise the Kullback-Libler (KL) divergence between a candidate Gaussian distribution and the density ge. It can be shown that we can safely ignore the normalisation constant for a. which is often computationally expensive,
replace qi with its unnormalised form. We have the following optimisation problem for the posterior variational parameters:
(m Ex) arg min DKL (N(0,) p. E) p 0, 2,) (0;; vh. D1)-1)),
(27)
12

---

Published in Transactions on Machine Learning Research (03/2025)
where (0(: v1) is the chosen prior distribution (M.3: prior).
An example of VB for neural network models is the backpooooppooooaaioonnn method (BBB) of Blundell et al. (2015); which assumes a diagonal posterior covariance (more expressive forms are also possible). Nguyen et al. (2017) extended BBB to non-stationary settings. More recent approaches involve recursive estimation, such as the recursive variational Gaussian approximation (R-VGA) method of Lambert et al. (2022) which uses full rank Gaussian variational approximation; the low-rank RVGA (L-RVGA) method of Lambert et al. (2023), which uses diagonal plus low-rank (DLR) Gaussian variational approximation; the Bayesian online natural gradient (BONG) method of Jones et al. (2024), which combines the DLR. approximation with EKF-style lincarisation for additional speedups; the natural gradient Gaussian approximation (NANO) method of Cao et al. (2024), which uses diagonal Gaussian approximation similar to VD-EKF in Chang et al. (2022); and the projection- based unification of last-layer and subspace estimation (PULSE) method of Cartea et al. (2023b), which targets different posterior densities for a subspace of the hidden layers and a full-rank covariance over the final layer of neural network.
2.6.4 Alternative methods
Alternative approaches for handling nonlinear or nonconjugate measurements have been proposed, such as sequential Monte Carlo (SMC) methods (de Freitas al., 2000), and ensemble Kalman filters (EnKF) (Roth et al., 2017). These sample-based based methods particularly advantageous when the dimensionality of 0 is large, or when more exact posterior approximation is required, providing greater flexibility in non-linear and non-Gaussian environments.
Generalised Bayesian methods, such as Mishkin et al. (2018); Knoblauch et al. (2022), generalise the VB update of (27) by allowing the right-hand side to a loss function. Alternatively, online gradient descent methods like Bencomo et al. (2023) emulate state-space modelling via gradient- based optimisation.
2.7 Weighting function for auxiliary variable (A.2)
The term (()c) defines the weights over possible values of the auxiliary variable (M.2: auxvar). We compute it the marginal posterior distribution vx((h)) p(tx (Di:)) (see e.g., Adams & MacKay (2007); Fearnhead & Liu (2007; 2011); Li et al. (2021)) or with ad-hoc rules (see e.g., Nassar et al. (2022); Abélès et al. (2024); Titsias et al. (2024)). In the former case, the weighting function takes the form
(1)))) p(v/ (D:1))
/
(28)
= p(Be xe, the D1.-1)
- /
11 1h Dia 11d--)
where one assumes that ye conditionally independent of e given th, and x, an exogenous vector. The first term on the right hand side of (28) is known the conditional posterior predictive, and is given by
p(yel We vr, D1a-1) / plyi 0,, xx) (0 vr, d10
(29)
This integral over O, may require approximations, we discussed in Section 2.6. Furthermore, the integral over 1/+-1 in (28) may also require approximations, depending on the nature of the auxiliary variable the, and the modelling assumptions for p(de vt-11 D1a-1). We provide some examples below.
2.7.1 Discrete auxiliary variable (DA)
Here we assume the auxiliary variable takes values in a discrete space tोx E e The weights for the discrete auxiliary variable (DA) can be computed with fixed number of hypotheses K 2 or with a growing number of hypotheses if the cardinality of I increases through time; we denote these cases by DA [K] and DA [inf] respectively. Below, we provide three examples that estimate the weights under DA [inf] recursively.
13

---

Published in Transactions on Machine Learning Research (03/2025)
RL (runlength with Markovian assumption): for 2/2 rt, the work of Adams & MacKay (2007) takes
1 - ((r-1))
d -1-1+
p(r P1t-1)=
H(r-1)
r2 r;
(30)
0
otherwise,
where H No - (0,1) is the hazard function. A popular choice is to take H(r) = x E (0, to be a fixed constant hyperparameter known as the hazard rate. The choice [L[in]] -PR is known as the Bayesian online changepoint detection model (BOCD).
CPL (changepoint location): for the S14,, the work of Li al. (2021) takes
K if (51. \ 8.] = $1:-11 and & = 1, 1 K if ([3 \. [,] = $1:t-1 and it = 0,
p( 11--1, D1s-1)
(31)
0 otherwise,
i.e., the sequence of changepoints at time correspond to the sequence of changepoints up to time 1, plus a newly sampled value for See Appendix A.4 for details on how to compute (=(1):)).
CPT (changepoint timestep with Markovian assumption): for t/+ Se: the work of Fearnhead & Liu (2007) takes
p(s: 11,1, p(Ce,e Ge,- J(E St,t-1);
(32)
with No (0,1) a probability mass function. Note that Çe,t - Ge,-11 is the distance between two changepoints, i.c., runlength. In this sense, Çe,t - rt, which relates CPT to RL. See their paper for details on how to compute (e(S)).
Low-memory variants - from Di[in]] to DA[K] In the examples above, the number of computations to obtain Ex, (e(1))) grows in time. To fix the computational cost, one can restrict the sum to be over a subset A₁ of the space of ii with cardinality [Ad] = K 2 1. Each element in the set A, is called a hypothesis and given 2 1, we keep the K most likely clements according to (x(e)) in A.. We then define the normalised weighting function
(1(1h)
D((()) EVEEA "c(x)))
(33)
which we instead of (vkt). For example, in RL above, Ar-1 (r/ : =. K} the unique K most likely runlengths where the superscript represents the ranking according to vt-1(-). Then, at time the augmented set Ar becomes (Ai-1 + {0), where the sum is element-wise and we then compute the K most likely elements of A. to define A,. In CPL, A:-1 contains the most likely sequences of changepoints, A, is defined as the collection the 2 K sequences where each sequence of A has a zero or one concatenated at the end. Finally, the most likely elements Ar define A.. This style of pruning is common segment ation methods; see, e.g., Saatçi al. (2010), but other pruning are also possible, such those proposed by Li et al. (2021), sampling- basod approaches; c.g. Doucet et al. (2000).
Other choices for DA [K] Finally, some choices of weighting functions are derived using ad-hoc rules, mcaning that explicit or approximate solutions to the Bayesian posterior are not needed. One of the most popular choices of ad-hoc weighting functions are mixture of experts, which weight different models according to given criterion.
ME (mixture of experts with algorithmic weighting): Consider ti = at Let ar = k denote the k-th configuration over (M.3: prior). Next, denote by w, (we,,...., (. a set of weights, where wi,s corresponds the weight for the k-th expert at time The work of Chaer et al. (1997) considers the weighting function
exp(wi,x yi)
vw(w) = E exp(wil y1)
(34)
14

---

Published in Transactions on Machine Learning Research (03/2025)
for k 1, 1..... K. The set of weights w, are determined by maximising the surrogate gain function
(e(wi) = p(ye Tte D D1a-1)
Σ plys De, ate D12-1) (we)))
(35)
with respect wr, for all 1,..., K at every timestep
We write DA [K], where is the number hypothesis, for methods that use hypotheses at most. On the other hand, write DA [inf] when do not impose bound on the number of hypotheses used. Note that even when the choice of (A.2: weighting) is built using DA DA[if]] one can modily it to make it DA[K].
Discrete auxiliary variable with greedy hypothesis selection (DA[1]) A special case of the above is DA [1], where we employ single hypothesis. In these scenarios, we set v((t)) = where t/s is the most likely hypothesis.
RL (Greedy runlength): For the = r, and DA[1], we take
if r--
p(ra (1-,1, =
if if = 0, otherwise.
(36)
Our choice of (A.2: weighting) is based on the marginal predictive likelihood ratio, which is derived from the computation of p(r,) D1a) under either either an increase in the runlength (re r2-1 + 1) or a reset of the (0) 0). Under these assumptions, the form of ve(r!))
runlength (r,
p ( vt, D1a 1) k)
(37)
p(u, (0) 3e. D 11=-1) + ply, ((()) Bz D1s-1) x)
For details on the computation of (A.2: weighting), Appendix A.3. For detailed implementation of (M.2: auxvar) RL, (M.3: prior) OUPR, (A.2: weighting) DA[1], and (A.1: posterior) LG, see Algorithm 4 in the Appendix.
For example, [L[1] is a runlength with a single hypothesis. We provide another example next.
CPL (changepoint location with retrospective membership): for the = 8is, the work of Nassar et al. (2022) evaluates the probability of past datapoints belonging in the current regime. In this scenario,
p(81a 81:-1, D1a-1) =pst:: (Da--))
(38)
that
p( D1a)) p(11a (1:t-1) p(y: Øe, 81:1; D12-1)-
(39)
This method allows for exact computation by summing all possible 2' elements. However, to reduce the computational cost, they propose discrete optimisation over possible values (2(($1a) $La E 1))),
where (=(::) p(s1. Di.)). Then, the hypothesis with highest probability is stored and gets assigned a weight of one.
2.7.2 Continuous auxiliary variable (CA)
Here, we briefly discuss continuous auxiliary variables (CA). For some choices th and transition densitics p(yb v P1. compulation of (28) becomes infeasible. In these scenarios, we use simpler approximations. We give example below.
CPP (Changepoint probability with empirical Bayes estimate): for ahh = vt, consider
p(us Ut-1, D12-1) p(v)):
(40)
15

---

Published in Transactions on Machine Learning Research (03/2025)
that
1x+) & p(p)) I vx)
(41)
The work of Titsias et al. (2024) takes v2(1r) = 6(vg - o;), where 8 the Dirac delta function and of is a point estimate centred at the maximum of the marginal posterior predictive likelihood:
4 = arg max max 2z 111-11). we[o.1]
(42)
In practice, (42) is approximated by taking gradient steps towards the minimum. This is form of empirical Bayes approximation, since we compute the most likely value of the prior after marginalizing out 0,. The work of Galashov et al. (2024) considers a modified configuration with choice of (M.2: auxvar) Vr E (0, 1)m
3 Unified view of examples in the literature
Table 3 shows that many existing methods can be writlen as instances of BONE. Rather than specifying the choice of (M.1), we instead write the task for which was designed, as discussed Section 2.1. We will experimentally compare subsct these methods in Scction 4.
The methods presented in Table 3 be directly applied to lackle any of the problems mentioned in Section 2.1. However, as choice of (M.1: model), specify the task under which the configuration was introduced.
Reference
Task
auxvar
M.3: prior
A.1: posterior
A.2: weight
Kalman (1960)
filtering
C
LSSM
LG
DA[1]
Magill (1965)
filtering
ME
LSSH
LG
DA[K]
Chang Athans (1978)
filtering
ME
LSSM
LG
CA
Chacr et al. (1997)
filtering
ME
LSSM
LC
DA[K]
Chahramani & Hinton (2000)
SSSM
ME
Static
VB
CA
Adams & MacKay (2007)
seg.
RL
C1
DA[inf]
Fearnhead & Liu (2007)
seg. preq.
CPT/ME
Any
[inf]
Wilson et al. (2010)
seg-
RLCC
PR
cj
DA [inf]
Fearnhead & Liu (2011)
seg-
CPT/ME
MMPR
Any
[inf]
Mellor Shapiro (2013)
bandits
RL
Cj
DA [Anff]]
Nguyen et al. (2017)
OCL
CPL
Sub
VB
DA
Knoblauch Damoulas (2018)
seg.
RL/ME
C1
[A[inf]
Kurle al. (2019)
OCL
CPV
Sub
DA(1]
Li et al. (2021)
OCL
CPL
MCI
VB
DA [A[ff]]
Nassar et al. (2022)
bandits OCL
CPV
Sub
DA[1]
Liu (2023)
preq-
ME
C,LSSM
Any
DA[K]
Chang et al. (2023)
OCL
C
ACI
LG
DA[1]
Titsias et al. (2024)
OCL
CPP
LG
CA
Galashov et al. (2024)
CL
CPP
CA
Abélès et al. (2024)
proq.
ME
LSSH
LC
DA[K]
-OUURR (ours)
any
RL
SPR
Any
DA[1]
Table 3: List of methods ordered by publication date. The tasks are discussed in Section 2.1. We the following abbreviations: SSSM means switching state space model; (O)CL means (online) continual learning: seg, means segmentation; preq, means prequential. Methods that consider two choices of (M.2: auxvar) are denoted by 'XYY.. This corresponds to double expectation in (6) for each choice of auxiliary variable.
4 Experiments
In this section we experimentally evaluate different. algorithms within the BONE framework on a number of tasks.
IIn general, the components of BONE can thought the building blocks for methods. Some these combinations would be useful, but they can employed nonetheless.
16

---

Published in Transactions on Machine Learning Research (03/2025)
Each experiment consists of wormup period where the hyperparameters are chosen, and deploy period where sequential predictions and updates are performed. In each experiment, we fix the choice of measurement model / (M.1: model) and posterior inference method (A.1: posterior), and then compare different methods with respect to their choice of (M.2: auxvar), (M.3: prior), and (A.2: weighting). For DA methods, we append the number of hypotheses in brackets to determine how many hypotheses are being considered. For example, [1] denotes one hypothesis, [K] -PR denotes K hypotheses, and [inf] denotes all possible hypotheses. In all experiments, unless otherwise stated, we consider single hypothesis for choices of DA. See Table for the methods compare.
M.2-M.3
Eq.
A.2
Description
Sections
static
C-Static
(16)
This corresponds the static with classical Bayesian update. method does
1.3.1, 1.3.2
changes in the euvironment.
abrupt changes
RL-PR
(18)
DA [inf]
This approach, commonly referred to as Bayesian online change- point detection (BOCD), assumes that non-stationarity arises from Independent blocks of time, each with stationary data. Esti- mates are made using data from the current block. See Appendix A.1 for more details.
4.1.1, 4.1.2,
4.2, 4.3.1,
4.3.2,
MoLF+RL-PR**
(18)
DA [inf]
Special case of RL-PR with explicit choice of (M.1: model) which makes it robust to outliers.
4.3.2
gradual changes
CPP-OU
(14)
Updates are done using discounted mean covariance accord-
4.1.1,
4.1.2,
ing probability estimate
change occurred.
4.2
C-ACI
(15)
each timestep, this method assumes that the parameters evolve
1.1.1, 4.1.2,
according to a linear map Fr, at a rate given by a known positive semideflaite covariance matrix Q..
4.2.
abrupt & gradual changes
RL-MMPR
(58)
DA [inf]
Modification of CPT-MMPR that assumes dependence between any two consecutive blocks of time and with choice of RL. This combination employs nomentt-atching approach when evaluating the prior and covariance under changepoint. See Appendix A.2 for details.
4.3.1
AL-OUPR
(19)
DA[1]
Depending on the threshold parameter, updates involve either (i) convex combination the prior belief with the previous mean and covariance based on the estimated probability of change (given the length), (fi) hard reset mean and covariance, reverting them to prior beliefs. See Appendix A.3 for more details.
4.1.1, 4.1.2,
4.2,
Table 4: List of methods compare in experiments. The first column, M.2-M.3, is defined by the choices of (M.2: auxvar) and (M.3: prior). The second column, Eq., references the equation that define M.2 M.3. The third column, A.2, determines the choice of (A.2: weighting). The fourth column, Description, provides a brief summary of the method. The fifth column, Sections, shows the sections where the method is evaluated. The choice of (M.1: model) and (A.1: posterior) are defined on a per-experiment basis. (The only exception being WoLF+RL-PR). For (M.2: auxvar) the acronyms are as follows: RL means runlength, CPP means changepoint, probability, C means constant, and CPT means changepoint timestep. For (M.3: prior) the acronyms as follows: PR means prior reset, OU means Ornstein Uhhenbechlee LSSM means lincar state-space model, Static means full Bayesian update, MMR means moment-matched prior reset, and OUPR means Frnstein-Uhlenbee and prior reset. We use the convention in Hušková (1999) for the terminology abrupt/graduaa gradual changes.
4.1
Prequential prediction
In this section, we give several examples of non-stationary prequential prediction problems.
4.1.1
Online regression for hour-ahead electricity forecasting
In this experiment, we consider the task of predicting the hour-ahead electricity load before and after the Covid pandemic. We the dataset presented in Farrokhabadi et al. (2022), which has 31,912 observations;
17

---

Published in Transactions on Machine Learning Research (03/2025)
each observation contains 7 features 2, and single target variable yt- The 7 features correspond to pressure (kPa), cloud cover (%), humidity (%), temperature (C) wind direction (deg), and wind speed (KmH). The target variable is the hour-ahead electricity load (kW). To preprocess the data, we normalise the target variable Yi by subtracting an exponentially weighted moving average (EWMA) mean with a half-life of hours, then dividing the resulting series by an EWMA standard deviation with the same half-life. To normalise the features 24, we divide each by a 20-hour half-life EWMA. The features are laggod by one hour.
Our choice of measurement model h is two-hidden layer multilayered perceptron (MLP) with four units per layer and ReLU activation function.
For this experiment, we consider RL [L[1] -OUPR* (our proposed method), RL[1] [1] (a classical method), C-ACI (a simple benchmark), and CPP-OU (a modern method). For computational convenience, we plug in a point- estimate (MAP estimate) of the neural network parameters when making predictions using h. More precisely, given thy, we use h(0r, I1+1) make (conditional) prediction, where 0 arg max, q(0; th, D1:)). For a fully Bayesian treatment of neural network predictions, Immer et al. (2021); leave the implementation of these approaches for future work.
The hyperparamcters of cach method are found using the first 300 observations (around 13 days) and deployed on the remainder of the dataset. Specifically, during the warmup period we tune the value of the probability of a changepoint for RL [1] -OUPR* and RL -PR For C-ACI we tune Q2, and for CPP-OU we tune the learning rate. See the open-source notebooks for more details.
In the top panel of Figure 3 we show the evolution of the target variable yr between March 3 2020 and March 10 2020. The bottom panel of Figure 3 shows the 12-hour rolling predictions made by the methods. We see that there is changepoint around March 7 2020 as pointed out in Farrokhabadi et al. (2022). This is likely due to the introduction of Covid lockdown rules. Among the methods considered, C-ACI and RL [1] ~OUPR* adapt the quickest after the changepoint and maintain low rolling MAE compared to RL [1] -PR and CPP-OU.
absolute error (MAE) of
x 106
1.25
1.00
rolling MAE
0.75
C-ACI
0.50
CPP-OU
0.25
[L[1]
[L[1]
04
05
06
07
08
09
10
Mar
2020
Figure 3: The top panel shows the larget variable (electricity consumption) from March 1 2020 to March 12 2020. The bottom panel shows the twelve-hour rolling relative absolute error of predictions for the same time window. The dotted black line corresponds to March 7 2020, when Covid lockdown began.
Next, Figure 4, shows the forecasts made by each method between March 4 2020 and March March 8 2020. We observe clear cyclical pattern before March 7 2020 but less so afterwards, indicating a change in daily electricity usage from diurnal to constant.
We also observe that RL [1]-PR and CPP-OU slow-down their rate of adaptation. One possible explanation of this behaviour is that the changes are not abrupt enough be captured by the algorithms. To provide evidence for this hypothesis, Figure shows, on the left y-axis, the predictions for RL [1] -PR and the target variable y:- On the right y-axis, we show the estimated runlength.
18

---

Published in Transactions on Machine Learning Research (03/2025)
x10e
forecasts at 1, observation at t
1.4
C-ACI
Load (kW)
CPP-DU
1.2
[L[1]-OPPR
RL [1]RRPP
target
1.0
05
06
07
08
Mar
2020
Figure 4: One day ahead electricity forecasting results for Figure 3. The dotted black line corresponds to March 2020.
X10
RL [1] -PR prediction
1.3
RL PPR
runlength
40
target
1.2
20
1.1
1.0
04
05
06
08
Mar
2020
Figure 5: One day ahead electricity forecasting results for RL together with the larget variable on the left y-axis, and the value for runlength (RL) on the right y-axis. We see that after the 7 March changepoint, the runlength monotonically increases, indicating a stationary regime.
We see that RL [1]R] resets approximately twice every day until the time of the changepoint. After that, there is no evidence of changepoint (as provided by the hyperparameters and the modelling choices), so RL [PR does not reset which translates to less adaptation for the period to the right of the changepoint.
Finally, we compare the error of predictions made by the competing methods. This quantified Figure 6, which shows box-plot of the five-day MAE for each of the competing methods over the whole dataset, from March 2017 to November 2020. Our RL [1] * method has the lowest MAE.
4.1.2 Online classification with periodic drift
In this section study the performance of C-ACI, CPP-OU, RL[1] and [L[1]-OUPR= for the classification
experiment of Section 6.2 in Kurle et al. (2019). More precisely, in this experiment 24,; ~ Unif[-3, 3] for
E (1,2), 2, = (#r,1; 2x,2) RR2 1/1 Bernoulli(a æx)) with o.") 10 sin(5 t) and o.2) cos t). Thus the unknown values of model parameters are slowly drifting deterministically according sine and cosine functions. The timesteps go from 0 to 720.
19

---

Published in Transactions on Machine Learning Research (03/2025)
d-y MAE
0.6
0.4
0.2
C-ACI
CPP-OU
RL-OUPR*
RL-PA
Figure 6: Distribution of the 5-day mean absolute error (MAE) for each of the competing methods on electricity forecasting over the entire period. For this calculation we split the dataset into consecutive buckets containing five days of data each, and for a given bucket we compute the average absolute error of the predictions and observations that fall within the bucket.
Misclassification rate
0.4
0.2
0.0
C-ACI
CPP-OU
RL [1] -OUPR*
[L[1]-PR
Figure 7: Misclassification rate of various methods the online classification with periodic drift task.
Figure 7 summarises the results of the experiment where show the misclassification rate (which is minus the accuracy) for the competing methods. Our RL[1]-OUPR* method works the best, and signifcantly outperforms RL [L[1]-PR, since we use an OU drift process with a soft prior reset rather than assuming constant parameter with a hard prior rset.
We can improve the performance of [L[K] if the number of hypotheses K increascs, and we vary the changepoint probability threshold K, as shown in Figure 8. However, even then the performance of this method still does match our method.
20

---

Published in Transactions on Machine Learning Research (03/2025)
π
0.2
0.3
0.4
0.5
0.6
0.7
0.8
RL. [K) -PR misclassification
0.5
0.4
0.3
0.2
[L[1] OUPR*
2
10
12
14
number of hypotheses (k)
Figure 8: Accuracy of predictions for [L[1]-PR as function of the number of hypothesis and the prior
probability of changepoint k. The black dotted line is the performance of RL [L[1] -OUPR* reported in Figure 7.
4.1.3 Online classification with drift and jumps
In this section study the performance of C-ACI, CPP-OU, RL [L[1]-PE, and RL [L[1]-OUPH for experiment with drift and sudden changes. More precisely, assume that the parameters of a logistic regression problem evolve according to
01-1 - 0,
w.p. 1 -
(43)
11 2,
w.p. Pe.
with p. = 0.01, 0o 211222,,, and E, is a zero-mean distributed random vector with isotropic covariance matrix (0.01)²Iz (where I2 2 identity matrix). Intuitively, this experiment has model parameters that drift slowly with occasional abrupt changes (at rate of 0.01).
Misclassification rate
0.6
0.4
0.2
0.0
C-ACI
CPP-OU
RL [L] DUPRR
RL[1]
Figure 9: Misclassification rate of various methods on the online classification with drift and jumps task.
Figure shows the missclasification rate among the competing methods. We obscrve that C-ACI, CPP-OU, and [1] -OUPR* have comparable performance, whereas RL [1] -PR is the method with highest misclassification rate.
21

---

Published in Transactions on Machine Learning Research (03/2025)
π
0.2
0.3
0.4
0.5
0.6
0.7
0.8
RL [K] -PR misclassification
0.5
0.4
0.3
RL OUPR*
0.2
2
6
10 12
14
number of hypotheses (K)
Accuracy of predictions for RL -PR as function of the number of hypotheses (K) and the probability of a changepoint k. The black dotted line is the performance of RL [L[1]-OPPH reported in Figure 9.
Figure 10:
To explain this behaviour, Figure 10 shows the performance of RL [L[K]-PR -PR as a function of number of hypot and prior probability of a changepoint K. We observe that up to three hypotheses, the lowest misclassification error of RL [L]]]]P -PR is higher than that [L[]-OURR++ which only considers one hypothesis. However, as we increase the number of hypotheses, the best performance for RL [K] -PR obtains a lower misclassification rate than RL (OUPPRR This is in contrast to the results in Figure 5. Here,
that with more hypotheses RL [K] -PR outperforms our new method at the expense of being more memory intensive.
4.2 Contextual bandits
In this section, study the performance of C-ACI, CPP-OU, RL [L[1]-PR, and RL -OUPR* for the simple Bernoulli bandit from Section 7.3 of Mellor & Shapiro (2013). More preciscly, we consider multi-armed bandit problem with 10 arms, 10,000 steps per simulation, and 100 simulations. The payoll of a given arm is the outcome of a Bernoulli random variable with unknown probability 0, = min (om(max(ee + 0.03 Ze, 0), for (1.),,.1.2.....0.0000 independent and identically distributed standard normal random variables. We take Ou Unif [0, 1] and use the same formulation for all ten arms with independence across arms. The observations are the rewards and there
features (non-contextual).
The idea of using RL [1]-PR in multi-armed bandits problems With this experiment, we extend the concept to other members of the BONE framework. We use Thompson sampling for each of the competing methods. Figure 11 shows the regret of using C-ACI, CPP-OU, RL [1]-RR, and RL [O]RR for the above multi-armed bandits problem. The results we obtain are similar to those of Section 4.1.2. This because both problems have a similar drift structure.
introduced in Mellor & Shapiro (2013).
Regret
C-ACI
4000
CPP-OU
[1] +
2000
[1] [P]
2000
4000
6000
8000
10000
timestep
Figure 11: Regret of competing methods on the contextual bandits task. Confidence bands are computed with hundred simulations.
22

---

Published in Transactions on Machine Learning Research (03/2025)
4.3 Segmentation and prediction
In this section, we evaluate methods both in terms of their ability to "correctly" segment the observed output signal, and to do one-step-ahead predictions. Note that by "correct segmentation", we mean one that matches the ground truth data generating process. This metric can only be applied to synthetic data.
4.3.1 Autoregression with dependence across the segments
In this experiment, we consider the synthetic autoregressive datasct introduced in Section of Fearnhead & Liu (2011), consisting of a set of one dimensional polynomial curves that are constrained to match up segmentation boundaries, as shown in the top left of Figure 12.
We compare the performance of the three methods in the previous subsection. For this experiment, employ probability of changepoint K = 0.01. Since this dataset has dependence of the parameters across segments, we allow for the choice of (M.1: model) to be influenced by the choice of (M.2: auxvar), i.e., our choice of model is given by h(0r vz). For this experiment, we take (M.2: auxvar) to be RL and our choice of (M.1: model) becomes
h(0 re. 114) = 0. h(T1..
(44)
with h( A,), A- x,), and Tr, 2 z₁. Intuitively this represents quadratic curve fit to the beginning Fr, and end points of the current segment. Given the form of (M.1: model) in (44), here we do not consider C-ACI nor CPP-OU. Instead, we use rumlength with moment moment-matching prior reset, i.c.,
RL-MMPR (see Table 4) which was designed for segmentation with dependence.
Sample run
RMSE
2.5
RL111 RL.11- -0UPh RIC11-18P3 10011PP samples
0.0
C-F
2.5
[1]-FF
50
0.0
000
(1) SeeR
2.5
250
0.0
ne (300
2.5
500
00
0.0
0
5
100
101
102
Figure 12: The left panel shows a sample run of the piecewise polynomial regression with dependence across segments. The x-axis is for the features, the (left) y-axis for measurements together with the est imtations made by RL[1] FL-MMPR, and [1] -OUPR*, the (right) y-axis for the value of rt under each model. The orange line denotes the true data-generating process and the red line denotes the value of the hypothesis RL. The right panel shows the RMSE of predictions over 100 trials.
Figure 12 shows the results. On the right, we observe that RL[1] -OUPR* has the lowest RMSE. On the left, we plot the predictions of each method, so we can visualise the nature of their errors. For RL [1] -PR, the spikes occur because the method has many false positive beliefs in a changepoint occurring, and this causes breaks in the predictions due the explicit dependence of h on r, and the hard parameter reset upon changepoints. For RL-MMPR, the slow adaptation (especially when 2, E [1, 5]) because the method does not adjust beliefs as quickly as it should. Our RL [L[1]-OPPR method strikes a good compromise.
23

---

Published in Transactions on Machine Learning Research (03/2025)
Changepoint count
10
10"
RL [1] -MPP
RL [1] -OUPR*
RL [L[1]-PR
Figure 13: Count of changepoints over an experiment for 100 trials. The orange line shows the true number of changepoints for all trials.
Figure shows the distribution (over 100 simulations) of the number of detected changepoints, i.c., instances where (r(r)) with ri = 0 is the highest. We observe that superior predictive performance in Figure 12 does not necessarily translate to a better segmentation capability. For example, the distribution produced by RL-MMPR sits around the actual number of changepoints (better at segmenting) whereas RL [OUPRR which is detecting far fewer changepoints, is the best performing prediction method. This reflects the discrepancy ween the objectives of segmentation and prediction. For a more thorough analysis and evaluation of changepoint detection methods on time-series data, see Van den Burg Williams (2020).
4.3.2 Non-stationary heavy-tailed regression with DA [inf]
Tt is well-known that the combination RL-PR is sensitive to outliers the choice of (M.1: model) is misspecified, since an observation that is "umusual" may trigger a changepoint unnocessarily. As a consoquence, various works have proposed outlier-robust variants the RL [iif]]-PP for segmentation (Knoblauch et al., 2018; Fearnhead & Rigaill, 2019; Altamirano et al., 2023; Sellier & Dellaportas, 2023) and for filtering (Reimann, 2024). In what follows, show how can casily accomodate robust methods into the BONE framework by changing the way compute the likelihood and/or posterior. In particular, we consider the WoLF-IMQ method of Duran-Martin et al. (2024). We use WoLF-IMQ because it is provably robust algorithm and it is a straightforward modification of the linear Gaussian posterior update equations. We denote RL [inf] -PR with (A.1: posterior) taken to be LG as LG+RL [inf]-PR and RL [inf] -PR with (A.1: posterior) taken to be WoLF-IMQ as WoLF+RL [PR
To demonstrate the utility of robust method, we consider a piecewise linear regression model with Student-t
errors, where the measurement sampled according ~ 21 2], y1 St(o(z;)T0... 2.01) Student- distribution with location T(x scale degrees of freedom 2.01, and o(x,) = (1, æ, x²). At every timestep, the parameters take the value
0. 01-1 31333333
w.p. 1- -PP
(45)
w.p. Pc,
with 0.01, and On 31-3,3]3 Intuitively, at each timestep, there is probability Pe of changepoint, and conditional on changepoint occurring, the each of the entries of the new parameters O, are sampled from a uniform 1-3.33 3]. Figure 14 shows a sample data generated by this process.
SO
S1
S2
S3
S4
S5
10
:10
2-2
2-2
2-2
2-2
X
X
X
X
Figure 14: segment.
Sample run of the heavy-taileed-rggesssio process. Each box corresponds to the samples within a
24

---

Published in Transactions on Machine Learning Research (03/2025)
To process this data, choice of (M.1: model) is h(0.. 0, o(x)) with
(y: 0,, Ft) W2 (yr. ((0,, xx)) log (3 h(O,, ((0,,)),,10) 1.0).
(46)
weighted Gaussian log- likelihood and W (u, 2) = (1+ -يسي the inverse multi-quadratic (IMQ) function with soft threshold value = 4, representing four standard deviations of tolerance to outliers. Here u, 2 E R.
The left panel in Figure shows the rolling mean (with a window of size 10) of the RMSE for - NoLF+RL[inf]] -PR*, and LG+C-Static. The right panel Figure 15 shows the distribution of the RMSE for all methods after 30 trials.
rolling(10) RMSE
10
mnn
5-
RMSE
01-
50
100
150
200
250
300
num.
LC+C+Static
LG+RL [G+RL[inf)
WoLF+RL (inf) -PR
Figure 15: The left panel shows the rolling RMSE using a window of the 10 previous observations. The right panel shows the distribution of final RMSE over 30 runs. The vertical dotted line denotes a change the true model parameters.
The left panel of Figure 15 shows that LG+C-Static has a lower rolling RMSE error than LG+RL [inf] -PR up to first changepoint (around 100 steps). The performance of LG+C-Static significantly deteriorates afterwards. Next, LG+RL [inf]] wrongly detects changepoints and resets its parameters frequently. This results in periods of increased rolling RMSE. Finally, WoLF+RL [inf]-PR= has the lowest error among the methods. After the regime change, its error increases at a similar rate to the other methods, however, it correctly adapts to the regime and its error decreases soon after the changepoint.
LG+RL [inf] -PR
WoLF+RL [nn++L[[nn]]]]] -PR
279
279
248
248
217
217
50
186
186
runlength
155
100
155
124
Junio
124
93
62
150
150
31
200
160
176
192
208
224
240
256
272
2866
112
122
1ap
160
C 176
192
208
224
240
250
772
208
timestep
timestap
Segmentation of the non-stationary linear regression problem. The left panel shows the segmentation done by LG+RL [inf]-PR, The right panel shows the segmentation done by [inf]] The z-axis is the timestep f, the y-axis is the runlength re (note that it is always the case that < f), and the color bar shows the value log p(r. y1=). The red line in either plot is the trajectory of the mode, i.c., the set Fia = (arg max,, p(r1 D.)....,aa arg max,, p(r: (..))). Note that the non-robust method (left) oversegments the signal. See this url for video comparison between LG+RL [inf] -PR and WoLF+RL [PR+]
Figure 16:
Figure 16 shows the posterior belief of the value of the ruulength using LG+RL [inf] -PR and WoLF+RL [inf] -PR*. The constant reaction to outliers in the case LG+RL -PR means that the parameters keep reseting back the initial prior belief. As a consoquence, the RMSE of LG+RL [inf] deteriorates. On the other hand, WoLF+RL [inf] -PR* resets less often, and accurately adjusts to the regime changes when they do happen. This results in the lowest. RMSE among the three methods.
25

---

Published in Transactions on Machine Learning Research (03/2025)
5 Conclusions
We introduced a unified Bayesian framework to perform online prodictions in non-stationary environments, and showed how it covers many prior works. We also used our framework to design a new method, RL [L[1]-UPR++ which is suited to tackle prediction problems when the observations exhibit both abrupt and gradual changes. In future work, we aim to investigate other novel variants and applications to newer model architectures such as transformers and graph neural networks (Moreno- Pino et al., 2024; Arroyo et al., 2025).
Aknowledgments
We thank Matias Altamirano, François-Xavias Xavier Briol, Patrick Chang, Alex Galashov, Matt Jones, Jeremias Knoblauch, and Radford Neal for insightful comments and discussions earlier versions of this paper.
References
Baptiste Abélès, Joseph de Vilmarest, and Olivier Wintemberger. Adaptive time series forecasting with markovian variance switching, 2024.
Ryan Prescott Adams and David C. MacKay, Bayesian online changepoint detection, 2007.
Diego Agudelo-Espann Sebastian Comez-Gonzale Stefan Bauer, Bernhard Schölkopf, and Jan Peters. Bayesian online prediction of change points. In Conference on Uncertainty in Artificial Intelligence, pp. 220. PMLR, 2020.
Reda Alami. Bayesian change-point detection for bandit feedback in non-stationary environments. In Asian Conference on Machine Learning, pp. 17-31. PMLR, 2023.
Réda Alami, Odalric Maillard, and Raphael Féraud. Restarted bayesian online change-point detector achieves optimal delection delay. In International conference machine learning, pp. 211-221. PMLR, 2020.
Matias Altamirano, François-Xans Xavier Briol, and Jeremias Knoblauch. Robust and scalable bayesian online changepoint detection, 2023.
Samanch Aminikhanghahi and Diane J Cook. A survey of methods for time series change point detection. Knowledge and information systems, (2):3339 367, 2017.
Álvaro Arroyo, Alessio Gravina, Benjamin Gutteridge, Federico Barbero, Claudio Gallicchio, Xiaowen Dong,
Michael Bronstein, and Pierre Vandergheynst. On vanishing gradients, over-smoothing, and over-squashing in gnns: Bridging recurrent and graph learning. arXiv preprint arXiv:2502. 10818, 2025.
Jordan T Ash and Ryan P Adams. On warm-starting neural network training. In NIPS, 2020. URL
attp://arxiv org/ abs/a9/0. 08475.
Daniel Barry and John A Hartigan. Product partition models for change point problems. The Annals of Slatistics, pp. 260 279, 1992.
Michele Basseville, Igor V Nikiforov, al. Detection of abrupt changes: theory and application, volume 104. Prentice hall Englewood Cliffs, 1993.
Richard H Battin. Space guidance evolution-a personal narrative. Journal of Guidance, Control, and Dynamics, 5(2):97-110, 1982.
Matthew Beal, Zoubin Ghahramani, and Carl Rasinussn.. The infinite hidden markov model. Advances in neural information processing systems, 14, 2001.
Gianluca M. Bencomo, Jake C. Snell, and Thomas L. Grilfiths. Implicit maximum posteriori filtering via adaptive optimization, 2023.
J. Bernardo and A. Smith. Bayesian Theory. John Wiley, 1994.
26

---

Published in Transactions on Machine Learning Research (03/2025)
Pier Giovanni Bissiri, Chris C Holmes, and Stephen G Walker. A general framework for updating belief distributions. Journal of the Royal Stalistical Sociely: Series B (Stalistionl Methodology), 78(5):1103-1138) 2016.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1613 1622, Lille, France, 07-09 Jul 2015. PMLR. URL https::/procceedingg .ml...m......... mlr waa.r.peess/vve pprss/v37// /13s///uunee115555 1ammmmmm11...m........
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+Nummly programs, 2018. URL http://githun com/ www/ gom/ggogle/jax.
Zhipeng Cai, Ozan Sener, and Vladlen Koltun. Online continual learning with natural distribution shifts: An empirical study with visual data. Proceedings of the IEEE/CVE international conference on computer vision, pp. 8281-8290, 2021.
Wenhan Cao, Tianyi Zhang, Zeju Sun, Chang Liu, Stephen S-T Yau, and Shengbo Eben Li. Nonlinear bayesian filtering with natural gradient gaussian approximation. ar [eess.SY], October 2024. URL http://arxiv org/ abss//10..... .
Álvaro Cartea, Fayçal Drissi, and Pierre Osselin. Bandits for algorithmic trading with signals. Available at SSRN 4484004, 2023a.
Álvaro Cartea, Gerardo Duran-Martin, and Leandro Sánchez-Retancom Detecting toxic flow, 2023b.
Wassim S Chaer, Robert H Bishop, and Joydeep Ghosh. mixture-of-experts framework for adaptive kalman filtcring. IEEE Transactions Systems, Man, and Cybernctics, Part B (Cybernetics), 27):4455 464, 1997.
Chaw-Bing Chang and Michael Athans. State estimation for discrete systems with switching parameters. IEEE Transactions on Aerospace and Electronic Systems, AES-)4(33:4133 425, 1978.
Peter G Chang, Kevin Patrick Murphy, and Matt Jones. On diagonal approximations to the extended kalman filter for online training of bayesian neural networks. In Continual Lifelong Learning Workshop at ACML 2022, 2022.
Peter G Chang, Gerardo Duran-Martin, Alex Shestopaloff, Matt Jones, and Kevin Patrick Murphy. Low-rank extended kalman filtering for online learning of neural networks from streaming data. In Conference Lifelong Learning Agents, pp. 1023-1071. PMLR, 2023.
Zhe Chen et al. Bayesian filtering: From kalman filters to particle filters, and beyond. Statistics, 182(1):1 69, 2003.
Joao FG de Freitas, Mahesan Niranjan, Andrew H. Gee, and Arnaud Doucet. Sequential monte carlo methods train neural network modcls. Neural computation, 12(4):955-993, 2000.
Joseph de Vilmarest and Olivier Wintenberger. Viking: Variational bayesian variance tracking, ar preprint arXiv:2104.10771 2021.
Shibhansh Dohare, J Fernando Hernandez-Garcia, Qingleng Lan, Parash Rahman, A Rupam Mahmood, and Richard S Sutton. Loss of plasticity in deep continual learning. Nature, 632(8006):768 774, 2024.
Arnaud Doucet, Nando de Freitas, Kevin Murphy, and Stuart Russell. Rao-Blackwellised particle filtering for dynamic bayesian networks. In UAI, 2000. URL
Gerardo Duran- Aleyna Kara, and Kevin Murphy. Efficient online bayesian inference for neural bandits. In International Conference Artificial Intelligence and Statistics, pp. 6002-002000000 6021. PMTR, 2022.
27

---

Published in Transactions on Machine Learning Research (03/2025)
Gerardo Duran-Martin, Matias Altamirano, Alexander Y. Shestpaloff, Leandro Sánchez-Betancourf, Jeremias Knoblauch, Matt Jones, Briol François-Xavier, and Kevin P. Murphy. Outlier-robust kalman filtering through generalised bayes. In International Conference on Machine Learning. PMLR, 2024.
Geir Evensen. Sequential data assimilation with a nonlinear quasi-geostrophic model using monte carlo methods to forceast error statistics. Journal of Geophysical Research: Oceans, (9(C5)1001433100 1994.
Mostafa Farrokhabadi, Jethro Browell, Yi Wang, Stephen Makonin, Wencong Su, and Hamidreza Zareipour. Day-ahead electricity demand lorecasting compelition: Post-covid paradigm. IEEE Open Access Journal of Power and Energy, 9:185 191, 2022. doi: 10. /LL.0///A..P..222........
Paul Fearnhead and Zhen Liu. On-line inference for multiple changepoint problems. Journal of the Royal Statistical Society Series B: Statisticol Methodology, 69(4))589-600 2007.
Paul Fearnhead and Zhen Liu. Efficient bayesian analysis of multiple changepoint models with dependence across segments. Statistics and Computing, 21:217-221 229, 2011.
Paul Fearnhead and Guillem Rigaill. Changepoint detection in the presence of outliers. Journal of the American Statistical Association, 114(525):109-188, 2019.
Emily B Fox, Erik B Sudderth, Michael 1 Jordan, and Alan Willsky, The sticky hdd-hmmm Bayesian nonparametrie hidden markov models with persistent states. Arziu preprint, 2, 2007.
Alexandre Galashov, Michalis K Tilsias, András György, Clare Lyle, Razvan Pascanu, Teh Yee Whye, and Maneesh Sahani. Non-stationary learning of neural networks with automatic soft parameter reset. In NIPS, November 2024. URL https:://artttt http://xxxv.oorgrbaaraa/a arggabs/2411 24410004444. 04034.
Joao Gama, Jesus Aguilar-Ruiz and Ralf Klinkenberg. Knowledge discovery from data streams. Intelligent Dala Analysis, 12(3):251 252, 2008.
Zoubin Ghahramani and Geoffrey E Hinton. Variational learning for switching state-space models. Newral computation, 12(4):831-864 2000.
Nuwan Gunasekara, Bernhard Pfahringer, Heitor Murilo Gomes, and Albert Bifet. Survey on online streaming continual learning. In IJCAT, pp. 6628-6637, 2023.
Muktesh Gupta, Rajesh Wadhvani, and Akhtar Rasool. Comprehensive analysis of change-point dynamics detection in time series data: A review. Expert Systems with Applications, pp. 123342, 2024.
Simon Haykin. Kalman fillering and neural nelworks. John Wiley & Sons, 2004.
M Hušková. Gradual changes versus abrupt changes. Journal of Statistical Plansing and Inference, 76(1-2): 109- 129, 1999.
Alexander Immer, Maciej Korzepa, and Matthias Bauer. Improving predictions of bayesian neural nets via local lincarization. In International conference artificial intelligence and statistics, pp. 703-711. PMLR, 2021.
Matt Jones, Peter Chang, and Kevin Murphy. Bayesian online natural gradient (BONG). In Advances in Neural Information Processing Systems, May 2024. URL sttp:///arav..or//bbs//0000 19681.
Rudolph Emil Kalman. A new approach to linear filtering and prediction problems. Transactions of the ASME- Journal of Basic Engineering, 82(Series D):35 45, 1960.
Mohammad Emtiyaz Khan and Håvard Rue. The bayesian learning rule. Journal of Machine Learning Research, 24(281):1-46, 2023.
Jeremias Knoblauch and Theodoros Damoulas. ceatio-temporal bayesian on-line changepoint detection with model selection. In International Conference on Machine Learning, pp. 2718 27277. PMLR, 2018.
28

---

Published in Transactions on Machine Learning Research (03/2025)
Jeremias Knoblauch, Jack E Jewson, and Theodoros Damoulas. Doubly robust bayesian inference for non-stationary streaming data with ß-divergences. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018. URL https: httpppprreennnnnnerrrr...r www..ps..c/pppppeeeeee files/ files/paapar22118/f11. pdf.
Jeremias Knoblauch, Jack Jewson, and Theodoros Damoulas, An optimization- view on bayes' rule: Reviewing and generalizing variational inference. Journal of Machine Learning Research, 23(13)): 2022. URL htap:://jmrr.orrr paaaprs/v3/19--1
html.
Mark Kuhl. Ridge regression signal processing. NASA, Langley Research Center, Joint University Program for Air Transportation Research, 1989-1989 1990, 1990.
Richard Kurle, Botond Cseke, Alexej Klushyn, Patrick Van Der Smagt, and Stephan Günnemann. Continual learning with bayesian neural networks for non-stationary data. In International Conference on Learning Representations, 2019.
Mare Lambert, Silvère Bomnabel, and Francis Bach. The recursive variational gaussian approximation (r-vga). Statistics and Computing, 32(1):10, 2022.
Mare Lambert, Silvère Bonnabel, and Francis Bach. The limited-memory recursive variational gaussian approximation (I-rvga). Statistics and Computing, 33(3):70, 2023.
Aodong Li, Alex Boyd, Padhraic Smyth, and Stephan Mandt. Detecting and adapting to irregular distribution shifts in bayesian online learning, 2021.
Lihong Li, Wei Chu, John Langford, and Robert. E Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp- 661 670, 2010.
Scott Linderman, Matthew Johnson, Andrew Miller, Ryan Adams, David Blei, and Liam Paninski. Bayesian learning and inference in recurrent switching linear dynamical systems. In Artificial intelligence and statistics, pp. 914 922. PMLR, 2017.
Bin Liu. Robust sequential online prediction with dynamic ensemble of multiple models: A review. Newro- computing, pp. 126553, 2023.
Yueyang Liu, Benjamin Van Roy, and Kuang Xu. Nonstationary bandit learning via predietive sampling. Tn International Conference on Artificial Intelligence and Statistics, pp. 6215 6244. PMLR, 2023.
Jie Lu, Anjin Liu, Fan Dong, Feng Gu, Joao Gama, and Guangquan Zhang. Learning under concept drift: A review. IEEE transactions on knowledge and dala engineering, 31 (11)):3346-238 2018.
Hengrui Luo, Younghyun Cho, James W Demmel, Igor Kozachenko, Xiaoye S Li, and Yang Liu. Non-smooth bayesian optimization in tuning scientific applications. The International Journal of High Performance Compuling Applications, 38(6):633 657, 2024. doi: 10.1777/09933420241778888 URL https://doi.. org/ 10. 10.117/10943222227888
David Magill. Optimal adaptive estimation of sampled stochastic processes. IEEE Transactions on Automatic Control, 10(4):434 439, 1965.
Joseph Mellor and Jonathan Shapiro. Thompson sampling in switching environments with bayesian online change point detection. arXiu preprint 1rXi::1302.3722 2013.
Aaron Mishkin, Frederik Kunstner, Didrik Niclsen, Mark Schmidt, and Mohammad Emtiyaz Khan. Slang: Fast structured covariance approximations for bayesian deep learning with natural gradient. Advonces in neural information processing systems, 31, 2018.
29

---

Published in Transactions on Machine Learning Research (03/2025)
Fernando Moreno-Pino Álvaro Arroyo, Harrison Waldon, Xiaowen Dong, and Álvaro Cartea. Rough transformers: wight and continuous time series modelling through signature patching. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang (eds.), Advonces in Neural Information Processing Systems, volume 37, pp. 106264-106294. Curran Associales, Inc., 2024. URL https://prooceedunge newpeeeeednngn...eippp.s.. wttppps....ppp..ppppprrrre wwtpppper.illee/eeeeeeeeeeeeeeee htt.://///aapee/////eleeee See1877eeeb2220222fff44446777 wwwp:r/rr2p--Ppp--ooooeeee Con.perr-oooeeeeceeee.e
Josue Nassar, Jennifer Brennan, Ben Evans, and Kendall Lowrey. Bam: Bayes with adaptive memory. arXiv preprint arXim:2202.02406, 2022.
Cuong V Nguyen, Yingzhen Li, Thang D Bui, and Richard E Turner. Variational continual learning. arXiv preprint (r1i::1710. 10628, 2017.
Yann Ollivier. Online natural gradient as a Kalman filter. Electronic Journal of Statistics, 12(2):2930 2961, 2018. doi: 10.1214/18 111214/18-EJS1441 EJS1468. URL attps:///oli htt////i.orgg////// org/10..//..o 1.....11//111 11144/88-EJ14666
Mari Ostendorf, Vassilios V Digalakis, and Owen A Kimball. From hmm's to segment models: A unified view of stochastic modeling for speech rocognition. IEEE Transactions on speech and andio processing, 4(5): 360-378, 1996.
Hans Reimann. Towards robust inference for bayesian filtering of linear gaussian dynamical systems subject to additive change. masterthesis, Universität Potsdam, 2024.
Carlos Riquelme, George Tucker, and Jasper Snock. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling, 2018.
Christian P Robert et al. The Bayesian choice: from theosiin- foundations to computational implementation, volume 2. Springer, 2007.
Michael Roth, Gustaf Hendeby, Carsten Fritsche, and Fredrik Gustafsson. The ensemble kalman filter: a signal processing perspective. EURASIP J. Adv. Signal Processing, 2017(1):56, 2017. URL https: //doi.org/10.....///o 10. 0008///133--017-099999
Yunus Saatci, Ryan D Turner, and Carl E Rasmussen. Gaussian process change point models. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pp. 2010.
Simo Särkkä and Lennart Svensson. Bayesian filtering and smoothing, volume 17. Cambridge university press, 2023.
Bruno Scalzo, Alvaro Arroyo, Ljubiša Stanković, and Danilo P Mandic. Nonstationary portfolios: Diversifica- tion in the spectral domain. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5155-5159. IEEE, 2021.
Mona Schirmer, Dan Zhang, and Eric Nalisnick. Test-time adaptation with state-space models. arXiv preprint 1rX4v:2407.12492, 2024.
Jeremy Sellier and Petros Dellaportas. Bayesian online change point detection with hilbert space approximate student-t process. In International Conference Machine Learning, pp. 30553 30569. PMLR, 2023.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4))285-294 1933.
Michalis K Titsias, Alexandre Galashov, Amal Rannen-Trie Triki, Razvan Pascanu, Yee Whye Teh, and Jorg Bornschein. Kalman filter for online classification of non-stationary data. In ICLR, 2024.
Gerrit JJ Van den Burg and Christopher KI Williams. An evaluation of change point detection algorithms. arXiv preprint arXi::2003.066 06222, 2020.
Jurgen Van Gael, Yunus Saatei, Yoe Whye Teh, and Zoubin Ghahramani. Beam sampling for the infinite hidden markov model. In Proceedings of the 25th international conference on Machine learning, pp. 1088-1099 2008.
30

---

Published in Transactions on Machine Learning Research (03/2025)
Mike
West and Jeff Harrison. Bayesian forecasting and dynamic models. Springer, 1997.
Robert C Wilson, Matthew R Nassar, and Joshua Gold. Bayesian online learning of the hazard rate in change-point problems. Neural computation, 22(9):2452-244 2476, 2010.
Tong Zhang. Mathematical Analysis of Machine Learning Algorithms. Cambridge University Press, 2023, doi: 10.1017/97S10099933077
A Worked examples for BONE methods
this section, we provide detailed calculation of (4(1)) for some choices vh. We consider a choice of (M.1: model) be linear Gaussian with known observation variance R,, i.e,
ply 0, Ny. x. 0,, R,).
(47)
A.1 Runlength with prior reset (RL-PR)
A.1.1 Unbounded number of hypotheses [inf] -PR
The work in Adams & MacKay (2007) takes 1/2 = to be the runlength, with E {0, l........ tt, that that counts the number of steps since the last changepoint. Assume the runlength follows the dynamics (30). We consider (r(r)) = p(re(Di:t) such that
p(r. Di:e) = p(re, D1:))
(48)
Σi,= plfe, D1:1)
l). The RL-PR method estimates p(r:, Pis)) for all Tr E (O....,{} (} at every timestep. To estimate this value recursively, we all possible previous runlengths follows
for Te E (O....,t).
prr,, Dra))
[-1
Σ (1r,
1=
(49)
Σ p(rz-1, Di:t Pis (1,, D1a--)
1=
[-1
= ply [r,, Rt, D1a-1)
Σ r2-1=0
p(r.-1, Dis 1
In the last equality, there are two implicit assumptions, (i) the runlength time conditionally independent
of the data Di.--1 given the runlength at time L 1- 1, and (ii) the model is Markovian in the runlength, Tt, the value of rt-1 bears no information. Mathematically, this means that (i)
that is, conditioned p(ra rt-1, D1.-1) p(r, (r-1) and (ii) p(u. 1r,,,-11 D1a-1) p(y: rt, D1a-1). From (49), we observe there are only two possible scenarios for the value of r,. Either r; = 0 or = Tt-1 + with T--1 E t.....,/-1......... 1}.
Thus, p(r.. D1a) becomes
p(r., D1a) = p(vel rt, 3t, D1a Pia
r 2
(50)
p(r D1a) = p(v. ær, xt, 11
Σ PH= T6-1=
if = 0.
The joint density (50) considers two possible scenarios: either we stay a regime considering the past
re observations, or we are in new regime, in which r, 0. Finally, note that (50) depends on three terms: (i) the transition probability p(ra r2-1), which it is assumed to be known, (ii) the previous log-joint.
31

---

Published in Transactions on Machine Learning Research (03/2025)
p(r--1, D1.-1), with rt-1 {0, 1, l.....t - 1}, which is estimated at the previous timestep, and (ii)) the prior predictive density
ply rts Rt. 11--1) / plys x1) p(O, r., P1=-1)d0,
(51)
For a choice of (M.1: model) given by (47) and choice of (M.3: prior) given by (18), the posterior predictive (51) takes the form.
ply re, 3t, D1a-1) = / N (yr x. 0,, R,) N (0, |1()) x/-1 d0,
(52)
(nd) mt 2 xt R.)) =N yv a: afu
(nt) with r1 .t-1.. Here, (M1-1 2 are the posterior mean and covariance at time t 1 built using
the last r 2 1 observations. II = O, then (T)) x = (No: Eo)
A.1.2 Bounded number of hypotheses RL [K]
If we maintain of possible hypotheses, then vi (r fr.-1......
( fo.....,t t 13 collection of
K unique runlengths obtained at time 1. Next, (49) takes the form
p(r,, D1:1)= = p(y: Tre Tt, P(rc-) D1a-1) p(r: (r(-1)
if 2 1, rf =
(53)
p(r,, D1:1) = p(ye rre 22, D1a-1)
Σ PT-IEV.-
p(n-11
(54)
Here, we have that either T2 = Tt-1 + when Tt-1 E 1 or Tr 0. After computing p(rr. Dia)) for all K + possibles values of rt, a choice is made to keep K hypotheses. For timesteps S K, we evaluate all possible hypotheses until > K.
Algorithm 2 shows an update step under this process when we maintain set of K possible hypotheses.
A.2 Runlength with moment-matched prior reset (RL-MMPR)
Here, we consider a modified version of the method introduced in Fearnhead Liu (2011). We consider the choice of RL and adjust the choice of (M.3: prior) for RL-PR introduced in Appendix A.1 whenever r 0. In this combination, for = 0, take r(0, rr. P1a-1) p(O, Fe, D1a-1). Next
p002 r2, D1a-1) = Σ
p0,, r-- 1 D1=-1)
Σ
p(r-11
(55)
T
Σ T=
p(r--1 11a-1
|n-1) (r 1جا 1) I(1 1))
Because (55) is mixture model, choose conditional prior to be Gaussian that approximates the first. two moments. We obtain
0 res V1--11
Σ
p(r--1 D (e-1) (1-1)
(56)
1=-1=0
for the first moment, and
EiO, 07 rt, 11--11
Σ p(r--1 D1a- p(r: Pir-:IPiat-Dbbrr1nze (I(m)a) 1) (r. 1) (n 1)T
p pt-
(57)
32

---

Published in Transactions on Machine Learning Research (03/2025)
for the second moment.
The conditional prior mean and prior covariance under ra take the form
# 0 rT, V1.-11,,
(58)
Σ 0 0 re. V1:--11 - (E(0,) | rı, V1:--11) (E res V1a-11)"
Algorithm 3 shows an update step under this process when we maintain set of K possible hypotheses.
A.3 Runlength with OU dynamics and prior reset (RL [1] [1]-DUPR*)
In this section, provide pseudocode for the new hybrid method we propose. Specifically, choices in BONE are: RL[1]-OUPR* for (M.2: auxvar) and (M.3: prior), LG for (A.1: posterior), and DA [1] for (A.2: weighting). Because of our choice of (A.2: weighting), [L[)ROURR= considers a single hypothesis (or runlength) which, at every timestep, is either increased by one or set back to zero, according to the probability of a changepoint and a threshold E (0,
In essence, -OUPRR follows the logie behind RL [1[1]_PR introduced in Section A.1 with K hypothesis and different. choice of (M.3: prior). To derive the algorithm for RL [1]]-UUPR* at time > 1, suppose r is available (the only hypothesis we track). Denote by r the hypothosis of a runlength increase, i.c., r Tt-1 and denote by r(") the hypothesis of runlenght reset, i.e,, Pt 0. The probability of a runlength increase under single hypothesis takes the form:
()(rr() p(r: Di:1)
p(r!
(1) D..))
p(r(") (1) Di.e) + +l(1 (0) ,D11)
ply ri (1)
3t. D p(ri D1.-1) k)
(59)
p(y 1r 2,, D D 1) p(r(-1: D 11:-11 ) 1 + p(y xe, Pl-n xx)
p rt 32, D (1 k)
ply: (0) ,,, D 1:r--1
ply r Iz, D (1
where x = p(r: 12-1) with r is the prior probability of a changepoint and and k: = p(r. rt-1 with Tt T ( is the probability of continuation of the current segment.
Next, use (r:) to decide whether to update parameters reset them according to prior belief according to some threshold c. This implements our choice of (M.3: prior) given in (19) and (20). Because we maintain a single hypothesis, the weight at the end of the update step is set to 1. Algorithm shows an update step for RL [1] * under the choice of (M.1: model) given by (47).
A.4 Changepoint location with multiplicative covariance inflation CPL-MCI
The work Li et al. (2021) takes vhe = $1at to be a t-dimensional vector where the i-th element is a binary vector that determines changopoint at time Then, the sum of the entries of S1a represents the total number of changepoints up to, and including, time
We take (11a)) (PI.), which is recursively expressed as
p(s1a D1.)) = p(3,, 81:-1 ye, L, D1:-1)
(60)
p(s 11.-1)p( $1:-1, 34, Vt, D1:
Here, p($ (D).-1) is inferred at the previous timestep t - 1. The estimate of a changepoint conditioned on the past changes and the measurements is
p(s: 1 11s1-11,,1 D1s))
p(x: = 1 1)p(() 21, 1,
Di:t-1)
p(st = 11)((1
1, Rt, 1 -11-11)
p(s: 0)p(シ, st = 0, $1, D1.-1)) p(s: = 1)p(y, 5, = 1, $1:1-11111-- 11:--11 -1
(61)
-11 -1+expp exp (-log
= =m(m); p(s: = 0)p(Ar s, 0, 81 D(sc-1)
33

---

Published in Transactions on Machine Learning Research (03/2025)
where o(x) 1/(1 exp(-x)) and
p(ye 8: 1, 81:4-1; 1
((s 1) p(st 0)
m log
log
(62)
p(y: 8t 0, Fe 11.111, 1 1
and similarly,
= 1
D1:)) a(m)).
(63)
Finally, the transition between states is given by p(31. $14-1) = p(s:).
B Algorithms
Algorithm 2 Implementation of RL [K] -PR. We consider update at time t and onc-step ahcad forccasting at time + 1 under Gaussian linear model with known observation variance.
Require: (Nu: En) // default prior beliefs
Require: D. = (a,, Me) // current observation
Require: (r) (ri-1) K E {O....,, 13x // bank of runlengths at time
D1a)] // joint from past hypotheses Require: (11 (8) (1))
Require:
// beliefs from past hypotheses Require: Z141 next-step observation
k=1
Require: pyyl6 0, = NW (Tx,R. // Choice of (M.1: model) // Evaluate hypotheses if there changepoint
2: for k == L....,, K do
......K
((( (k)
-rr-1+1
4: p(y: (((9) , ,,rr:ii D1tt1) f- N(ve |o (8) mi 1/ De + R.) // posterior predictive k-th hypothesis
5: p(r(") Dza) +p(y; r(( Dz. 11a-1) 1 p( p(r (1) (m(2)) // update joint density
6: (#( {(()} - -Hi I(A))
7: (0 (k)) + +N(0: p. Ex) // choice of (M.3: prior)
8: q: (0,; (K) (0 p(y: oN, R2) x NiO, μ (M) ) // following (26)
end for
10: // Evaluate hypothesis under a changepoint
11: (4+1) -0
12: p(u |r( (1++1) .z, D1at-1) +- (y wi Mo: w. En æ. + Re) // posterior predictive for k-th hypothesis
13: p(r? (1+1) Dr.) + p(y 1 (b+1) æt, Dia-1) Ex p(r:") (k) Pr.) ((r((=1) [r," -))
14: // Extend number of hypotheses to K and keep top K hypotheses
15: has ttpp.k(fpr!!), Pi.)....,ppf p() (k+1) Dra)}, K)
16: (p(r!") (K) D
([ice.a(((((]] (K) K+1 II.K)
17: ((1)) ( " slice.at((() (K) ) 141 I..k)
(((())
18: 1/ build weight and make prequential prediction "(r (ia))
19: v)(1(0)) + Ex p(r)), p.1)) for = -,...,,
9ett + al41 Ex ve(r(()) 114 (1) // prequential prediction under linear-Gaussiag model
21: return ((Hb (1)) , ) 9:41
In Algorithm& 2, the function top.k(A, K) returns the indices of the top K 2 clements of A with highest value. The function ati B) returns the elements in according the list of indices B. If |A| & [B), return all elements in A.
34

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 3 Implementation of [L -MPR. We consider updale at time and one-step ahead forecasting at time t + 1 under a Gaussian linear model with known observation variance.
Require: D; = (æ,, yt) // current observation
Require: {r/-1 1 E t 1 // bank of runlengths at time - (k)
Require: (p(r(-), D1:)) // joint from past hypotheses
Require: { [14 21-1) k=1
// beliefs from past hypotheses Require: 2141 // next-step observation
Require: p(y 0, Nyy 0' Ra) // Choice of (M.1: model) // Evaluate hypotheses there no changepoint
2: for & == 1, ..... K do
3: x!() r1-1
4: ply: rr It, (i:-11 t N(Be ae] 11-11 x1 21_1 + Re) // posterior predictive for k-th hypothesis
(k)
5: p(r(") D2.1) +pyy |,(0) Te: 11:--1 11 p(r D1e-1) (-(-)) // update joint density
6: (ig ((()) - (Hi-1: (1A)
7: T: (0 (1)) - NO: Tr. Σ() // choice of (M.:: prior)
8: (0,; ) x 7. (0..re (k)) plys OT., R.) x N(O, 1 = // following (26)
9: end for
10: // Evaluate hypothesis under changepoint
11: Ti [k+1) 6-0
Ho + -,O, rc, 11 // following (56)
13: Eo 6., 0: re, Vv.-1] (B|6: Fr, V1:a-1)) (B rr, V1.c-1))* // following (56) and (57)
14: l (r(())) (k+1) F. D1.t1) + (3: [ Mo: x2 Eg + R.) // posterior predictive for k-th hypothesis
15: p(r D1.)) + p(u r (((+1))
D1=-1) _k=1 p(r? -1=+)p(((" Ir? 1)
16: // Extend number of hypotheses to K + and keep top hypotheses
17: l top.k(fp(r))) Di.)....,, p() (E+1) 11a)), K)
((r(++1)
18: (p(rt)) D + slice.at((p(r 11 JIRK
K+
19: {(u) (k) 2 + slice.at( (m)) )())) Iuk)
build weight and make prequential prediction
pir! Pr.)) for == L...,,K
21: m((r
Σ plr Mirt),Pia
22: D.+1 t 214 Exm pe(r (k) )u( // prequential prediction under a Gaussin model (k)
23: return {(u) (1)) ) Dc+1
35

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 4 Implementation of -OUPRR, with update at time and for one-step ahead forecasting at time ++ 1, under a Gaussian linear model with known observation variance.
Require: D: (z:, y:) // current observation
Require: #++1 // next-step observation
Require: E (0, // restart. threshold
Require: 7t-1 E (0,...,t-1, // runlength at time t --1 1
Require: (Py: 2b) // defanit prior beliefs
Require: (H,-1, 11- // belief's from prior step
Require: p(y (, /
0rx R.) // Choice of (M.1: model)
(r ) - (0, -1 // choice of (M.2: auxvar)
ply (1( Be, D1a-1) + (y, a! Po: m/ E. 24 + R,) // posterior predictive changepoint
p(y (r()) Bt, P1t-1) - Ny: 2 11-1 x2 Et-1 ot Rτ) // posterior predictive no changepoint
p(v. (r(") 111-11177)))
4: ()
plue lr m.. (1- p -mc-)) // probability of uo-changepoint at timestep /
6: if v(ri ((())>>))
> then
7: To +- ri
(()
(m(-1) v(((1) Mu (1 v(r!"))
Pi-1
5(()) t -,-1 v(ri )2 Eo (1- 11-u(r(())"
9:
10: else if v(r())
< then
11:
Ti Ti,
(0)
(r+) t Hb
12:
13: I(1)) Eo
14: end if
15: n00r))) N(O, E.,
E.) choice of (M.3: prior)
16: (:(00: re) x (0: it,, p(ye 1 R,) x N00 (10 E,) // choice of (A.1: posterior) via (26)
Dc+1 &- m1 M4 // prequential prediction (given linear-Gaussian model)
18: return (M rt), ÿt+1
C Bayesian inference when the dynamics are known
If the dynamics of model parameters p(0 O, 1/++1) and the dynamics for auxiliary variable p(sh++1 I (/)) are known, then a full-Bayesian treatment of the prediction at time + is given by predicting the expected model parameters and then performing inference.
Specifically, given the prior belief state p(v. 0, Dı:)) and the new input æ441, the predictive distribution over the output y141 is given by
p 11+1, Dia) = Σ
E/
Lf/ p( 1141, O.+ 1 Oc+1 D1x) d0++1
(64)
0041
Vets
where the parameter predictive distribution
p(v1+1.0 Oct1 Pia) = Σ E/
p(1(+1,00 0.41 vh, 0.)((hh 0, (Da)) do,-
(65)
1he
Here, the parameter dynamics factorises as
p(v Oct1 1// 0,) = p(be4t (4t)p(0++1 10,, veet))
(66)
and the prior belief state factorises as
p(,,, 0: D1:.) p(tbe Pi: wi, D1z)-
(67)
36

---

Published in Transactions on Machine Learning Research (03/2025)
Combining all the above equations, can derive expression for the posterior predicted mean
ÿr+1 = Elys+1 11+1, 21a]
= Σ Σ p(u 115)p(()) D1.))
(68)
+1+1
/ (0144000 O0 0141)((0 the D1:e) do, d0
0
After making the prediction, we observe the outcome yt+1, and then update the belief state for the parameter O.+1 (for each value of w(+1) using
1 p(y++1 x1+1, 1c+1)p(00+1 1e+11, D1s),
p(0 1.04113/443 1/+1, D1.t+1)
pe+1 p( (181+1/2044 2141, Dia, ve+1) = / p(y1+1 11 0c+1))(0+++ 1 D1a) d0++1, (69)
/ p(0++1 0z, 1e)))(00 (1a)d0.
p(0 Me+1, D1.))
Jo.
Similarly we update the belief state for the auxiliary variable using
1
p(v++1 (2a41)
7,41" p B1+1, (2+1)p((1 P1:0);
Ze+1 p(y F4+1, DIt) = Σ z p(1e441 (Da))
(70)
t/+t1
p(d'+1 (Da)) E(b14 (1))) p(db D1.)).
This full Bayesian treatment is different from BONE, because we do not assume well-specified dynamics. Thus, BONE makes predictions at time + with only the posterior at time 6, ie., does not require a prealet step.
37


Reviews:
[{"review_id": "zEqKGr8Drg", "reviewer": "Reviewer_dPSS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well written in the sense of writing style, structure and the mathematical notation is consistent and the paper is well structured.  The authors appear to have a good command of the literature from an algorithmic point of view and make numerous insightful observations comparing an impressive number of different algorithms and models.\n\nThe experiments appear to be well conducted and the examples are interesting.\n\nWhat I find to be the main limitation of the paper is that the paper is not motivated in a particularly clear way from a usual Bayesian standpoint (despite the title of the paper).  I recognize that footnote 1 is intended to explain this, although I must confess I find this footnote confused as to what \"Bayesian\" means.  As the main contribution of this paper is to provide a unifying framework I do find this limitation concerning, but I do think it is fixable with (significant) revisions.  I should add here, that my taste and view is not always in concordance with others so If other referees or the editor disagree with me here I will happily defer to them.  In any event, I will elaborate on my concerns below.\n\nA second point, the author(s) appear to suggest that the BONE framework not only allows cataloguing methods as per Table 2, but also building new methods like LEGO.  Is this the case?  If it is, then it seems like a very useful contribution (reminiscent of the graphical model work popular a decade ago) that should be developed a little more strongly.  Perhaps the JAX library (redacted for now) implements exactly this, this doesn't come through strongly enough in the paper!\n\nGiven this important contribution, I think it is worth considering a presentation that is easier to digest from the Bayesian point of view, which would mean addressing some of these oddities:\n* I don't understand the use of the $h(\\theta_t;x_t)$ notation (Equation 5).  It seems to hide the model and tie the use to squared loss / expectation.  While it is used in Equation 22-26, it does seem to me like a more traditional approach would be both clearer and more general.\n* If I am not wrong, parameters are indexed for two reasons.  One is to allow non-stationarity i.e. theta is changing over time so it is indexed theta_t; and a second reason, knowledge of theta is changing over time.  I assume this is the reason that the indexing is present even in the stationary case (Equation 1 and 2).  I think it would prefer the clarity significantly to only use the indexing by t for the first situation and use conditioning to illustrate the information used to inform the distribution of the parameter.  For this reason I think theta ought to be indexed but and not psi\n* Algorithm 1 seems to reduce predicting y to a finite mixture and computes the weights and parameters to the mixing components.  This would be much easier to follow if it was taken back to first principles, Starting with the joint posterior on $\\theta$ and $\\psi$ and then introducing approximations would likely help with the explanation.  I attempt to outline how this might look in the next section, but please correct or clarify..\n* The paper in many places uses the word \"likelihood\" where I think the author(s) mean \"model\".\n* Actually writing down the likelihood might help clarify the paper (with a product of i.i.d densities conditional on a fixed in the stationary case and a product sign of i.i.d densities conditioned on a moving parameter in other cases).  I understand the paper focuses on recursive updates, but this can still help explain the approximate inference being applied.\n* The term \"conditional prior M3\" in section 2.7 is potentially confusing (although the contradictory nature of the name should give the reader a hint to pay attention).  If I understand correctly the author(s) mean the choice of parametric form used for approximate recursive posterior updates.  I think the fundamental insight of BONE is that under certain assumptions exact or approximate recursive updates are possible. A bit more care here needed could greatly improve clarity.  The term conditional prior is confusing as it mixes the concept of approximate inference and an approximate parametric posterior (say using VB) and actual model assumptions in the usual sense of a prior.\n* The non-stationarity in the paper AFAICT applies to the case of stationarity if the \"regime\" is known, but is non-stationary when it is unknown, this is an interesting case but there are others.  Please correct me if I am wrong here.\n* Table 2 is quite important to defend the power of the unifying framework yet it is not easy to read.\n\nEquation 7 does not say what the expectation is under.\nEquation 8 shouldn’t $\\theta$ be a $d$ by $q$ matrix (why the transpose on theta in equation 8?).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This interesting paper proposes a unifying online learning framework that applies to both stationary and non-stationary environments.  It is particularly concerned with applying Bayesian inference to non-stationary regression problems where the non-stationarity is caused by a non-stationary discrete latent variable and conditional on the parameters and the discrete latent variable a (stationary) regression model is applied.\n\nThe paper then does a comprehensive review of the literature and shows that many existing algorithms can be formulated within their (\"BONE\") framework.  They also show that the framework allows the development of new algorithms and demonstrate them on both an electricity dataset and a bandit problem.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "This is my (provisional) attempt to write down the core insight of BONE.  My request is to ask if this line of reasoning can be used to improve the clarity of the paper.  I may not be completely correct here, but I think amendments to the paper presenting the approximate inference in these terms could be very enlightening.\n\nI will try to rewrite the model only using the index to implement non-stationary.  Starting with the non-stationary case we have:\n$p(y_{1:t},\\theta|x_1:t) = p(\\theta) \\prod_i^t p(y_i|x_i,\\theta)$\n\nThe posterior is:\n$P(\\theta|x_{1:t},y_{1:t}) \\propto p(\\theta) \\prod_i^t p(y_i|x_i,\\theta)$\nwhen we incorporate non-stationary, it becomes the case that $\\theta$ can change in time (so we index it $theta_t$), but the new parameter $\\psi$ does not change in time.\n$p(y_{1:t},\\theta_{1:t},\\psi|x_1:t) = p(\\psi) \\prod_i^t p(y_i|x_i,\\theta_i)p(\\theta_i|\\psi,x_i)$\nThe posterior is then\n$P(\\theta_{1:t},\\psi|x_{1:t},y_{1:t}) \\propto p(\\psi) \\prod_i^t p(y_i|x_i,\\theta_i)p(\\theta_i|\\psi,x_i)$\n\nImportantly $\\theta$ is now indexed, but $\\psi$ is not.\n\nThis paper is concerned mostly with recursive updates (which is one reason why product signs never appear in the paper – also the paper uses the word likelihood for what I think is more traditionally called the model)\nThe update of $\\theta_t,\\psi$ has a recursive form which exploits the fact that we can summarize past knowledge with:\n$p(\\psi|y_{1:t-1},x_{1:t-1})$, and we can safely neglect the posterior on $\\theta_{1:t-1}$.\n\nGiven $x_t$ a prediction of $y_t$ can be made with:\n$\\int \\int p(y_t|x_t,\\theta_t)p(\\theta_t|\\psi,x_t) p(\\psi|y_{1:t-1},x_{1:t-1}) d \\theta_t d\\psi$\n\nWe can also update knowledge of $\\psi$ with\n$p(\\psi,\\theta_t|y_{1:t},x_{1:t}) \\propto p(y_t|x_t,\\theta_t) p(\\theta_t|\\psi,x_t) p(\\psi|y_{1:t-1},x_{1:t-1})$, which we can marginalize to $p(\\psi|y_{1:t},x_{1:t})$ to enable the next update.\n\nBONE applies in the simple but useful case where $\\psi$ is discrete with $l$ states.  This means that there are $l$ mixture components  $p(\\theta_t|\\psi=1,x_t),...,p(\\theta_t|\\psi=l,x_t)$.  BONE propose an approximate inference algorithm framework for solving this problem (Algorithm 1), it then performs a thorough literature review and shows many methods are instances of BONE (Table 2) and proposes and tests some new algorithm/models that belong to the BONE framework.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CnF1XvM9I4", "reviewer": "Reviewer_jXLu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n## Clarity\n\nOverall, the paper is well structured and easy to understand.\n\n## Contribution and relevance\n\nThis paper reviews many different Bayesian methods that can be used in online learning, which could fit into two kinds of TMLR papers:\n 1. development of new analytical frameworks that advance theoretical studies of practical learning methods;\n 2. surveys that draw new connections, highlight trends, and suggest new problems in an area.\n\nHowever, although this paper proposes a new analytical framework, there is no clear development towards further theoretical study. So, it should probably be considered as a survey.\n\nAnyway, the review work is useful and the \"BONE\" formalism makes it easier to classify the various techniques.\n\nAlso, RL[1]-OUPR* is competitive with the other methods in the tested settings.\n\n## Originality\n\nThis work is original.\n\n## Soundness\n\nThe experimental section shows that RL[1]-OUPR* is competitive with the other methods in several settings, including a non-synthetic one.\n\n# Weaknesses\n\n## Clarity\n\np. 6 and after: formal definitions of $\\boldsymbol{\\mu}$ and $\\boldsymbol{\\Sigma}$ should be introduced somewhere.\n\n## Contributions\n\nSince this paper reviews existing techniques in Bayesian online learning, it should cite relevant reviews that already exist, if any (if not, the absence of such reviews should be indicated in the Introduction).\n\nThe possible limitations of the proposed formalism BONE are not evoked. For instance, is there any Bayesian online learning technique that does not fit BONE?\n\nThe justification (either theoretical or experimental) of the non-trivial methods is not always present. Examples: C-ACI, ME-LSSM.\n\nThe Experiments Section is not entirely adapted to a review paper such as this one. For instance, the selection of the algorithms to be tested is not explained or motivated. Are the selected algorithms known for performing better than other?\n\n## Soundness\n\nThe elements (M1, M2, M3) of the BONE framework are not bricks that can be stacked independently: there are some combinations of \"auxiliary variables\" M2 and \"conditional priors\" M3 that are incompatible (either because they are useless or because they are meaningless). For instance, ME-Static is theoretically possible, but is (intuitively) useless to do, and C-PR does not make any sense. \nSo, presenting an algorithm as combination (M1, M2, M3, A1, A2) is potentially misleading. The same remarks holds for the choice of the algorithm A1.\n\nIt is true that the choice of (M1, M2, M3, A1, A2) can be regarded as a way to classify existing algorithms, but it cannot really be used to build new algorithms from existing bricks. So, it is unsure that the BONE *formalism* would be helpful for future research (which is distinct from the *review* itself).\n\n## Minor errors\n\np. 2: \"Our estimate of the mean\" -> \"Our estimate of the expectation\"\n\nSection 3: \"tackle any of the the problems mention in Section 2.3\" -> \"tackle any of the problems mentioned in Section 2.3\"\n\nSection 2.8.3: \"Bayesian online natural gradien\" -> \"Bayesian online natural gradient\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper is mostly a review extracting a common structure from articles about *Bayesian online learning in non-stationary environments*. The paper distinguishes 3 different elements:\n 1. (M1) the model performing the prediction (given an input), whose parameters are denoted by $\\theta$;\n 2. (M2) the \"auxiliary variables\" $\\psi \\in \\Psi$, containing the information about the non-stationarity;\n 3. (M3) the \"conditional prior\" over $\\theta$, which depends on $\\psi$ and information on the past.\n\nAlso, the paper distinguishes 2 methods to choose to compute:\n 1. (A1) the posterior distribution of $\\theta$, given the conditional prior and an input data point;\n 2. (A2) the weights $\\nu(\\psi)$ over the different auxiliary variables $\\psi \\in \\Psi$.\n\nThe paper reviews the various models and methods solving at least one of these 5 elements of the problem. \n\nAdditionally, the paper proposes a new model for M3, named RL[1]-OUPR*.\n\nThe Experiments section focuses on evaluation of RL[1]-OUPR*, mainly in a problem of electricity forecasting, and additionally on synthetic datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Is there any existing review in the same area?\n 2. Is there any Bayesian online algorithm that does not fit into BONE?\n 3. Explain the idea of the algorithms when it is lacking.\n 4. Explain the selection of algorithms made in Section 4.\n 5. Discuss the purpose of the separation (M1, M2, M3, A1, A2) (classification of existing algorithms? designing new algos? ...)", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DiiYSUKMeg", "reviewer": "Reviewer_j55f", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1)The BONE framework unifies diverse methods, bridging gaps between changepoint detection, continual learning, and adaptive forecasting, and making it accessible to both ML and statistical communities.\n2)The RL[1]-OUPR* algorithm innovatively reconciles gradual and abrupt non-stationarity, addressing limitations in existing approaches that focus on only one type of change. The experimental section spans various real-world tasks, offering robust evidence of the framework's versatility. They also claimed to provide a library implemented in Jax enhances accessibility and reproducibility for researchers and practitioners.\n\nWeaknesses:\n1) The paper references changepoint methods (e.g., Adams & MacKay, Gupta et al.) but does not clearly articulate how BONE innovates upon these approaches.\n2) Non-stationary processes addressed by BONE appear conflated with changepoint detection, leading to ambiguity in the problem setting. while the introduction highlights the modularity of BONE, it lacks a focused literature review to clarify how the framework differs from prior work in Bayesian online learning (e.g., dynamic priors, ensemble Kalman filters).\n3)Terms like \"continual learning\" are used broadly but are not directly tied to the problem of non-stationarity. This may confuse readers unfamiliar with OCL and its overlap with BONE.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces BONE (Bayesian Online learning in Non-stationary Environments), a unifying framework that integrates diverse methodologies for addressing non-stationarity in Bayesian learning. The contributions are:\nUnified software and model framework: BONE presents a modular structure comprising three modeling components (measurement model, auxiliary process, and conditional prior) and two algorithmic components (posterior estimation and auxiliary variable weighting). This provides a comprehensive view of existing approaches under a common framework.\n\nThe authors propose novel approach (which should be highlighted among the dense literature) RL[1]-OUPR*, a method designed to handle mixed non-stationary data regimes by combining mechanisms for gradual and abrupt changes. Then theydemonstrated the adaptability of BONE across multiple tasks, including segmentation and forecasting, with RL[1]-OUPR* achieving state-of-the-art performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1)Scalability in Large-Scale Settings: Although theoretical generality is demonstrated, there is little discussion on practical efficiency or scalability for high-dimensional data or long-horizon tasks. In section 2.8 the authors talked about several fitting methods, without discussing the possbile scalability issue (which is the best and why), which is a key question in change-point detection. It would be helpful to discuss the computational complexity of posterior estimation and auxiliary weighting in high-dimensional settings. For instance, how does BONE handle scaling issues in DA[inf] models where hypothesis spaces grow exponentially?\n\n2) Strengthen the introduction by explicitly stating how BONE diverges from changepoint-specific methods like Bayesian online changepoint detection (e.g., Adams & MacKay 2007). In addition, there are lines from other communities treating similar problems, if the authors can make in-depth, more focused review, perhaps focus on change-poing literature. \nFrom the SciML community, recent efforts have been extended to auxilliary-free change-point in online setting:\nLuo et.al (2024) Non-smooth Bayesian optimization in tuning scientific applications, The International Journal of High Performance Computing Applications. From the statistical community, Hartigan (1993) A bayesian analysis for change point problems. Journal of the American Statistical Association. (which is more appropriate than Barry&Hartigan 1993 cited now.)\nThe lack of in-depth literature review in the introduction section makes readers confused the problem setting: how the non-stationarity BONE attempts to tackle, is different from non-smooth/change-point data generating process. Non-stationary stochastic process can be continuouts and even smooth.\n\n3)On the other hand, Section 2.3 is un-necessarily lengthy, but still does not make it clear how it is different from existing change-point or online literature. The use of the term \"continual learning\" is argubly too broad, since the OCL usually means that the underlying data generating mechanism could shift. For another example, it does not make a compelling case for how auxiliary variables (e.g., RL) differ from existing changepoint models. I would suggest to condense this section by focusing on the essential differences and remove overly broad discussions of continual learning, which dilute the focus. It may be more clear if the comparison Table 2 is shown at the beginning, then short explanations about the difference follow after.\n\n4) From a practical perspective, it would be good to provide heuristics or examples for choosing auxiliary processes like RL[1] or CPP for different types of non-stationarity. I think this is a  key component since it represents the evolution of non-stationary latent states. Practitioners will benefit from clear guidelines on tailoring these components to specific applications. Or the author could give several examples where some well-known methods cannot handle (e.g., GP with non-stationary kernels when underlying environment has shifts) and then the BONE handles well. \n \n5) Error Analysis for Mixed Regimes: It would be interesting to see a qualitative breakdown of errors when handling both gradual and abrupt non-stationarity in the same dataset. This would better demonstrate RL[1]-OUPR*'s robustness. Since there lacks usual theory (I understood that for a highly complicated model, theoretic guarantee may not be feasible), there seems more room for refined error analysis. \n6) How does the current BONE scales when the input lives in higher dimensions?\n \nPoints 1 to 4 must be addressed.", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There has been some debate between the reviewers and with the authors regarding the nature of the contribution. In light of the interesting discussions that took place, I think the proposed manuscript revision makes it clearer that it does not correspond to a review or extensive literature survey (in particular the text does not discuss theoretical performance guarantees for any of the methods). On the other hand, it does propose an original view (with companion implementation library), aimed at unifying the many algorithms proposed in the literature for recursive prediction under assumed non-stationary behavior. Again, an interesting topic that has been discussed is the "Bayesianism" of the approach and this is also a point that has been clarified: the general point of view is Bayesian (as most often in filtering and prediction) but the emphasis is put on scalable recursive computations (typically not through Monte Carlo methods) and there is an interesting taxonomy (which is part of the proposed BONE framework) of various approximate prediction updates that can be performed, depending on the nature of the underlying non-stationarity representation. While it does not provide, strictly speaking, new methods the proposed BONE framework is modular and can be used to assemble together ideas that were proposed in different contexts (as is done in the experimentation section).

Overall, this is a valuable contribution to the field of applied online prediction in non-stationary environments that deserves tor be published in TMLR.
Decision: Accept (poster)