A Practical Algorithm for Feature-Rich, Non-Stationary Bandit Problems
Authors: William Loh
Sajib Kumer Sinha
Ankur Agarwal
Pascal Poupart
Venue: Accepted by TMLR ()

Abstract: Contextual bandits are incredibly useful in many practical problems. We go one step further by devising a more realistic problem that combines: (1) contextual bandits with dense arm features, (2) non-linear reward functions, and (3) a generalization of correlated bandits where reward distributions change over time but the degree of correlation maintains. This formulation lends itself to a wider set of applications such as recommendation tasks. To solve this problem, we introduce *conditionally coupled contextual* ($C_3$) Thompson sampling for Bernoulli bandits. It combines an improved Nadaraya-Watson estimator on an embedding space with Thompson sampling that allows online learning without retraining. Empirical results show that $C_3$ outperforms the next best algorithm by 5.7% lower average cumulative regret on four OpenML tabular datasets as well as demonstrating a 12.4% click lift on Microsoft News Dataset (MIND) compared to other algorithms.

Published in Transactions on Machine Learning Research (03/2026)
A Practical Algorithm for Feature-Rich, Non-Stationary Bandit Problems
Wei Min Loh University of Waterloo, Vector Institute
wmloh@@uattrloo.cco
Sajib Kumer Sinha Manulife Financial
Sajib_ Sinha Smanalffaai
Ankur Agarwal Manulife Financial
Ankur_ Agwwaaalmmmmmmnli..cco
Pascal Poupart
ypoupart@uwsaerrtoo.cr
University of Waterloo, Vector Institute
Reviewed on OpenReview: o/penreveeeee net/ forun? id- tRbwfej9uY
Abstract
Contextual bandits are incredibly useful in many practical problems. We go one step further by devising a more realistic problem that combines: (1) contextual bandits with dense arm features, (2) non-linear reward functions, and (3) a generalization of correlated bandits where reward distributions change over time but the degroe of correlation maintains. This formulation lends itself to wider set of applications such recommendation tasks. To solve this problem, we introduce conditionally coupled conteztual (C₃) Thompson sampling for Bernoulli bandits. It combines an improved Nadaraya- Watson estimator on an embedding space with Thompson sampling that allows online learning without retraining. Empirical results show that C3 outperforms the next best algorithm by 5.7% lower average cumulative regret on four OpenML tabular datasets well as demonstrating 12.4% click lift on Microsoft News Dataset (MIND) compared to other algorithms
1 Introduction
Multi-armed bandits are applicable in many domains where there is high stochasticity and limited oppor- tunities to fully explore all possible arms
[Lattimore & Szepesvári 2020). A more useful variant of the problem called contezlual bundil (Lu et al. 2010) lackles a signilicantly harder problem where it aims to op- timize for the best arm for given context. Contextual bandits find applications in many domains including recommender systems, online advertising, dynamic pricing, and alternatives to A/B testing.
In several applications, the arms can be decomposed into a set of features such that different arms share some features and therefore their reward distributions may be dependent (which we refer to as coupled arms). Furthermore, the reward distributions of the arms may evolve over time, leading to non-stationarity. This paper focuses non-stationary contextual bandits with coupled arms.
To motivate the investigation into coupled arms, or coupling in general, we consider an example of strong coupling in product recommendation. Complementary goods such as bicycles and helmets are typically strongly coupled. the demand for bicycles rises, it is likely that the demand for helmets would go up too. Cycling, in some countries, seasonal activity where sales bicycles and helmets differ during summer and winter.
'Our implementation can found GitHub (attpe://githubb.comm///)

---

Published in Transactions on Machine Learning Research (03/2026)
This provides useful information for an agent when recommending products. Unlike time-series forecasting, we do not directly model the demand over a future time period. Instead, we capture features that might suggest coupling, then if one product has a high demand, it would immediately infer that a strongly coupled product would also have a high demand. This is beneficial for any bandit algorithm that has to balance exploration and exploitation of information.
Main Contributions One of our contributions is introducing the notion of coupled arms that are ubiqui- tous in many practical applications. The primary contribution is developing an algorithm called conditionally coupled contextual (Ca) Thompson sampling that solves contextual bandits with correlated/couppa /coupled arms in bandit or recommendation tasks. To the best of our knowledge, is the first algorithm that can solve contex- tual bandits with correlated/ /coupled arms non-stationary setting. Unlike many other neural contextual bandit approaches, there are no lengthy gradient-based updates at inference time. C3 can also leverage arm features, which reduces the cold-start problem arms, with the added benefit of working with a variable set of valid arms.
2 Related Works
2.1 Contextual Bandits
On the contextual bandit front, LinUCB by Li et al. (2010) can be considered one of the pioncering contextual bandit algorithms that demonstrated success through the use of simulated evaluation based on the Yahoo! news dataset. Chu et al. (2011) followed up with rigorous theoretical analysis of variant of LinUCB. The other popular paradigm is the Bayesian approach where Agrawal & Goyal (2013) developed a contextual bandit algorithm with Thompson sampling with a Gaussian likelihood and prior, assuming a lincar payoff function. Unfortunately, there was no empirical evaluation on a practical problem.
With deep neural approaches on the rise, the contextual bandit community has been focusing on algorithms that learn non-lincar reward functions. One of the carlier algorithms was the KernelUCB by [aako et al. (2013) which extends LinUCB by exploiting reproducing kernel Hilbert space (RKHS). Similarly, Srinivas et al. (2009) generalized Gaussian processes for a contextual bandit setting by introducing the GP-UCB algorithm. While both algorithms attain a sublinear regret, practicality is limited since both have cubic time complexity in terms the number of samples. After the breakthrough in the theoretical understanding of neural networks, particularly the neural tangent kernel (NTK) by Jacot et al. (2018). Zhou et al. (2020) developed NeuralUCB which neural network-based contextual bandit algorithm with complete theoretical analysis and suite of empirical analysis which oulperforms many algorithms in tabular dataset benchmarks from OpenML.
More recent advancements include SquareCB Footeer & Rakhlin 2020) which reduces the problem of con- ual bandits to an online regression problem. Under mild conditions, SquareCB along with a black-box online regression oracle has optimal bounded regret with no overhead in runtime or memory requirements. While they work on most regression models, the performance is highly dependent on the quality of the selected oracle. Kveton al. (2020) introduced their take on randomized algorithms for contextual bandits. Their novel contributions include additive Gaussian noise for bandit. setting that can be introduced to complex models such as neural networks.
2.2 Other Relevant Bandits
Several specialized bandit algorithms may be relevant to our problem. Basu et al. (2021) introduced variant called contextual blocking bandit that handles a variable set of arms but assumes the selected arms of an agent influence the future set of valid armss Their work revolves around this idea but ultimately differs in having a fixed, finite set of overall arms.
The problem of non-stationary reward distributions in bandits is usually referred to as restless bandit, which proposed by Whittle (1988). Wang et al. (2020) introduced the Restless-UCB algorithm which provably solves restless bandits, but does not account for context in the environment. Chen & Hou (024)
2

---

Published in Transactions on Machine Learning Research (03/2026)
improves upon this by leveraging context and budget constraints. A specialized solution by [Slikkins & Cpfal 2008) assumes that reward distribution changes gradually and works by continuously exploring while sometimes following the best arm based on the last two observations. However, they assume that all armss are independent and can be modelled as a Brownian motion which is uncommon in practice.
In the realm of sleeping bandits where some arms are occasionally not valid, (Slikinns (2011) introduced the contextual zooming algorithu that adaptively forms partitions in a similarity space. Operating on space, opposed to having fixed arms, allows them to effectively tackle the sleeping bandit problem. While they offer innovative framework, it is likely that partitions in tigh-dimensiona spaces (e.g. from large language models) would not be tractable.
Kleine Buening el al. (2024) proposed a situation that is potentially relevant to many applications from a game-theoretin perspective. Goals of agents could conflict for example, an arm could be a video from a content creator on a public platform. In the current state, "clickbait" videos would maximize the reward for the content creator but are seen as negative phenomenon overall the platform. Kleine Buening et al.] (024h devised an incentive-aware learning algorithm to ensure that the learner obtains the right signal.
2.3
Recommender Systems
There is growing interest in applying contextual bandits on recommender systems (Ban et al. 2024). On the topic of recommender systems, the more prevalent form of recommendation models in recent years is typically based on neural networks Dong et al. (2022). popular approach the two-tower neural network employed by Huang et al. (2020) and Yi et al. (2019). A major benefit of such designs includes incredibly efficient retrieval within the learned embedding space as well the ability to learn complex relationships of queries and items. Another design called BERT4Ree Sun et al. (2019) leverages the power of transformers in sequential problems to provide recommendations. However, in the ment ioned recommender designs, there is no element of exploration, unlike contextual bandits, resulting in a possibly greedy approach that may get stuck in a suboptimal policy. This can also be a major problom when user bchaviour changes since all gradient updates to the models are based on historical data alone, and frequent retraining of the models can be expensive.
3 Problem Formulation
3.1 Contextual Bandit
In this paper, we focus on Bernoulli bandits where the conditional reward distribution is Bernoulli(u(c,)) a)) and C is the current context, is left be an arbitrary space as long it can be appropriately encoded. Each arm A is discrete class. The Bernoulli mean parameter μ C A - [0, 1] is continuous function whose value represents the probability of the reward being one. is assumed to be Lipschitz continuous in C x A.
3.2 Coupled Arms: An Extension Correlated Arms
Gupta et al. 2021 formulated the correlated multi-armed bandit problem where pulling an amm provides some information about another arm that is correlated. We view this as special case of coupling.
Conditional reward distributions tend to be non-stationary in practice but we can still exploit some infor- mation arms. While μ could change with time, there is an inherent structure to how μ of certain arms change. For example, the marginal probabilities of shoppers buying snowboards and skis are likely to be coupled, even though both probabilities would drop during the summer and rise during winter in similar fashion.
In reference Figure T up to the present, we see that the expected rewards for arms and 2 are very similar and evolve similarly together in the time interval. We call these strongly coupled orms. Pulling one will give some information about the her arm in any time period, in contrast to correlated arms where
3

---

Published in Transactions on Machine Learning Research (03/2026)
Visualization of concept drift in bandits
Condiconnl reward probabilty
0.8
Flreward aamm 1]
0.2
Elreward aarm 2]
Clreward arrm 3]
Present
0.0
Figure 1: A three-arm example of strong and weak coupling during concept drift of expected reward distri- bution. Arms and 2 are said to be strongly coupled, while arms 1 and 3 are said to be weakly coupled.
this condition is only true at particular point in time. Conversely, arms 1 and 3 are weekly coupled arms since they have mostly different historical expected rewards.
Concept drift, in the context of bandits, can be defined as: there exist some times t 12 E f1,2,... T} where P(rle, a, (1) # P(rle, a, 12) (r the reward, the context and a is an arm) (Lu et al. 2018). The degree of coupling between arms and d' for a given context
1 pla,d' c) = 1- -1- T
E
where DJs is the Jensen-Shannon divergence over the reward distributions. Arms a and a' are said to be perfectly coupled for context c if p(a, c))
3.3 non-stationary Contextual Bandits with Coupled Arms
We extend vanilla contextual bandits to a more general problem. The Bernoulli mean parameter plcc a, t) is now a function of time too. We also assume that y is Tipschitz continuous with respect time.
Each arm E A Rd can be characterized with vector of dense features, which implies that there are infinitely many possible arms but a finite number of arms presented to an agent at each time step. We call them valid arms when they are presented to the agent at that particular time step. In special case where arms do not have dense features, they can still be represented as one-hot encoded vectors.
the presence of concept drift, ie. p(c, t) # a't generally for t + t', and infinitely many possible arms, this can be very difficult task. Here, we assume that there are strongly coupled arms that can be exploited. The degree of coupling is learnable from the arm fcatures, conditioned on the context c.
3.4 Objective
The goal in both problems is minimize the cumulative regret which is the cunulative difference between the reward of the best arm in hindsight a" and the reward of the chosen arm a, for given context G, over all time steps (Lattimore & Szepesvári 2020
CumilativeRograt(TT (T) = Σ afcr,at plce, tr,
(2)
4 Methodology
4.1
Embedding Model
This section pertains the process of training an offline regression oracle, class of optimization oracles for contextual bandits described by Bietti et al. (2021)
4

---

Published in Transactions on Machine Learning Research (03/2026)
Importance Weighted Kernel Regression The chosen approach to capture coupling between arms is based on the hypothesis that the empirical rewards of relevant subset of reference samples can be used to estimate the reward of some unseen sample. Madaraya-Watson kernel regression (NWKR) is a well-known nonparametric regression method NNadaaaaa 1964) that uses a weighted average of labels of neighbouring samples, weighted by a kernel function that satislies some conditions.
Suppose there a learnable space S C Rd that represents some joint space of contexts Candd arms A, similar to the formulation by [Slivkins (2011). We could use NWKR on some reference dataset Dret r() containing historical context-arm embeddings 8; S and rewards r; E R, with 8 x S + IR being the radial basis function (RBF) kernel to estimate the mcan reward of an unseen sample 8 E S
((s) = EM.NED K(8, 8()r
(3)
Ex,eDK(s, n(s,
Note that j introduced in Section 3.3 is a function of context, arm, and time while á in Equation B is a function of context-arm (jointly) and reference dataset D. Unlike time series algorithms,, we do not directly model time as an independent variable since we have make assumptions on how the reward distribution changes over time. Instead, we use historical examples in D that close to the present time to indirectly condition the time.
An issue with NWKR is the susceptibility to bias from drifts in the sampling distribution. The overall weight of samples may dominate the regression due to the disproportionately many samples in the vicinity of a query sample. This is particularly an issue in bandit algorithms where the distribution of arms selected will likely change as more data is ingested. The points in S provide information about μ in that subspace, but the frequency of points should not affect f., except for a measure of confidence which will be discussed To mitigate sampling bias, we introduce importance weights. A sample is assigned lower importance weight if it is located in the vicinity of many samples, and higher importance weight otherwise. More precisely, the importance weight is defined as
in Section 4. 4.2
w(s) = E. k(s,s)( E (0, 1]
(4)
The importance weighted kernel regression (IWKR) is defined as
E En. n(s, ((ss))(()) A(8) ENED nis8, ws)w(s;)
(5)
Theorem 1. Suppose a vector of importance weights w of samples has been computed. The time complexity of updating the importance weights, given a new sample, O(n).
A naive implementation of the importance weights computation would incur a quadratic time complexity. However, this can be optimized to be linear time as shown in the proof in Supplementary Material A.
Theorem 2. Suppose jus) is Lipschitz continuous S. In the limit of the size of the reference dataset Dref where points are sufficiently sampled from the neighbourhood of some query point s, the importance weighted kernel regression with radial bosis function kernel is approrimate estimator of u(s).
The proof of Theorem 2 can be found in Supplementary Material
A.2
Parametrization of Embedding Space While IWKR can estimate values, the input space may not be sufficiently calibrated with respect to the fixed kernel function. This can be rectified by training a multilayer perceptron as an embedding model o: :CC. A with IWKR towards a classification objective.
min E (Cncr(((((c + XC
(6)
where LBCE is the binary cross entropy loss and LECE the expected calibration error (Nacini et al. 2015 Every context-arm pair will be embedded as = Φ(c, a) that. IWKR acts on optimal space.
5

---

Published in Transactions on Machine Learning Research (03/2026)
We incorporate calibration as auxiliary objective to reduce overconfidence which is notoriously common in deep neural networks (Guo et al. 2017). In bandit algorithm involving neural networks, calibration is important to avoid biases when facing a lack of data.
An optimal model would tightly cluster strongly coupled context-arm pairs. To encourage the learning of coupling in 9, we can partition the reference dataset by time intervals Dref D U ... U D so that IWKR only uses samples from the relevant time interval only for a given query. This avoids averaging reward values from a different time period which may be subject to concept drift. The training process is described in Algorithm
Algorithm C3 training process
Inputs: Training dataset D {(G, ri)) neural network Ø
2: for epoch e do
3: Randomly split D into Drof = (Cref, Ovets Pret), and D,
4: Embed reference f- ó(Cref: arat)
5: Compute importance weights w for 8
for (c, (c,a.r) E Dg do Embed query q f- Φ(c,a)
8:
s', rr'o f filter for samples in T such that they are in the same time interval as q Compute RBF weights between s' and
10:
Estimate weighted mean reward fi()) using the RBF weights and rief
11:
Compute the sum of losses with f and r
12:
Perform gradient descent on ó
Algorithm Details The training is done batch-wise. The randomization in Step forms a self-supervised learning objective by masking certain samples and creating a predictive subtask. Dvet can be seen as the set of in-context samples and Dy contains the training samples. All samples (both in Dref and Dy) are embodded with Φ, and the objective to optimize the embedding space produced by d.
Step 9 computes the RBF weights between g and every embedded reference sample in s'. Then in Step 10, we apply Equation 5 on g using the RBF weights, importance weights, and r'er to compute p(g). The gradient update should update & to embed context-arm pairs with similar rewards closely.
4.2 Inference
This section extends the offline regression oracle by incorporating exploration with a Beta distribution and Thompson sampling.
Thompson Sampling The embedding model with IWKR is trained towards a classification objective for prodicting the expected reward. To incorporate an element of exploration, we adopt Thompson sampling. The conjugate prior of Bernoulli bandit is Beta distribution with parameters a and 3, where a usually refers to the counts of r===1 1. The notion of counts in continuous embedding space S can be solved using partial counts of rewards weighted by the RBF kernel. However, this is complicated by importance weights since S was learned with IWKR.
The expected value of the Beta distribution should be impacted by w(s) since it makes f less biased and robust against sampling distribution shifts. However, the variance of the Beta distribution should not be impacted by wss) since it would cause a and B lose information on the number of times the neighbourhood sampled. A solution to this to introduce some modifications to the computation of the parameters to

---

Published in Transactions on Machine Learning Research (03/2026)
3.5
(NNKR) 5' (MIKR)
Embeoding dimersion
2DF of Beta distributiine
5' (NWKK)
2.5
2.0
1.0
Historical pic, s)) semples
((c,a)
0.5
a').aa)
Embedding dimension
0.0
0.2
0.4
0.6
0.8
1.0
Value
Figure 2: An example of Thompson sampling exploration in continuous spaces: [lest] embedding space con- taining reference samples Dref (circles) and different arms (stars) for given context c, and [right] constructed Beta distribution with (IWKR) and without (NWKR) importance weights. The true a of both arms for that context is 0.6.
the conjugate prior. Let n(s)= = Ei= k(8, si). Define
E x(s, (i)((s))) =s)(((()))
a(s) = 11())
(7)
Σ k(s, s.)))
(()sss) (1))[1 A(s))
B(s) = n(s)
(8)
Di= k(s, )
With this, sample the posterior p(s) (cta( from the resulting Beta distribution. mean simplifies to
The
a(s) = M(s)
B[((s)) a(s) B(s)
(9)
which is exactly IWKR. On the other hand, the information of the frequency the neighbourhood was sampled is still preserved because it can be shown that the total count is still function of n,
Σ s(s
(10)
The left side of Figure illustrates two arms a, a' when jointly embedded with context The gray circles refer to previously pulled arms at's 's for different contexts q's ass. For a new query with context e, arm a (bluc) is embedded closer to more samples hence it has essentially been pulled more often for context c. Using partial counts weighted by an RBF kernel, this manifests as a more peaked Beta distribution as shown on the right side, resulting in less exploration compared a' (red).
The combination of IWKR and Thompson sampling gives rise conditionally coupled contertual Thompson sampling (Cs). The term "conditionally' in C3 refers to the degree of coupling being conditional on the context.
Figure 2 also shows the effectiveness of importance weights in a non-uniform sampling setting. The mean of distributions formed with TWKR closer to 0.6 compared NWKR, iec. without importance weights.
Approximate Bayesian Update Recall that IWKR dependent on a reference dataset D. of the posterior weighs every sample with the RBF kernel relative to some query point. This can be seen as type of conditioning on a local subspace. After an arm pulled and the reward is observed, we should have the triplet (Gn+1, Cn Tu+1). Since the algorithm operates S and requires the updated importance
The sampling

---

Published in Transactions on Machine Learning Research (03/2026)
Comparison between algorithms where linear refers to both LinUCB, LinTS, and SquareCB while neural refers to both NeuralUCB and NeuralTS. n refers the number of samples seen.
Table 1:
Inference time
Update time
Non-linear rewards
Non-stationary tasks
Arm features
Algorithm
C3
(n)
(1)
Linear
(()
0(1)
X
X
partially
Neural
((1)
(n)
X
x
weights, to conserve time and memory, we can directly store the triplet (ó(en+1, an+1), Tn+1, 2 w (
into D.
This is an approximate Bayesian update and is important for the online learning element.
Bayesian update typically assumes that every random variable a sequence is identically distributed. The information gathered is directly stored in the parameter space of some statistical distribution, which will be updated using some closed-form algebraic expression. For C3, the information is stored in the reference dataset D embedded on S. This allows flexibility to both append and remove samples from D. In problems with concept drift, the conditional reward distribution shifts as function of time but a typical Bayesian update does not effectively handle this since it might simply average the distributions across time.
To mitigate the issues presented by non-stationarity without frequent retraining, C3 allows the removal of older samples while appending the latest samples. Time can be seen as a special case of context and since p is assumed be Lipschitz continuous, samples nearer in the time dimension would be more relevant.
The entire inference pipeline can be summarized in Algorithm 2 The update process does not include any gradient updates, unlike many neural contextual bandit algorithms. The properties of C3 and other contextual bandit algorithms are summarized in Table
Algorithm C3 inference process
1: Inputs: Reference dataset Drof = (K, Pref, w), context e, set of valid arms {ai,..., Jn trained embedding model ø
for each valid arm index i E [b]] do
Embed queries di t -p(ccaa)
Compute a<q:); ((q:)) with respect to Dret
Sample f; (eta((a(g)) 3(a))
6: Play best arm j +- argmax;e[1]] A
7: Observe reward r
Append (q,,r) r) to Dref Update w in Dref
Assume p T.- T--āipschilz. In. stalionary bandil Theorem 3. Let the embedding space of & S c 11d. scenario, Cg incurs an expected regret of
B[R E O (LataT (log a
Proof of Theorem can be found in Appendix A.3
5 Experiments
Section 5.1 is the only experiment using synthetic data to demonstrate the hypothesis between coupling and embedding distance. Sections 5.2 and 5.3 real-world datasets.

---

Published in Transactions on Machine Learning Research (03/2026)
2.5
Mean distance
Line
2.0
Distance from anchor
1.5
1.0
0.5
0.0
-1.0
-0.6
-0.2
0.2
0.6
100
True Correlation
Figure 3: Distance from the anchor arm embedding as a function of correlation with 1.96 sigma error bars over 10 random seeds.
5.1 Coupled Arms Simulation
The following simulated example demonstrates that ø can capture the notion of coupling. Recall coupled arms generalize correlated arms by ensuring that correlation persists over time.
Suppose there is a set of arms {ao, a1,..,,a6) a6). We call as the anchor arm where the corresponding reward distribution is Bernoulli(Ho). At time t, Ao is randomly sampled from a Uniform(0, 1) distribution. Then, the remaining 14 for the rest of the arms are sampled such that they are either positively or negatively correlated with μo- The chosen degree of correlation is fixed for any time for all arms with respect to the anchor arm. Arms can be sampled to obtain (a)) pairs to learn μ4 until the end of the episode where this entire process repeats for time t + 1.
Complete details of the generation of coupled arms are described in Supplementary Material A.4 The chosen true correlations for arms 01,..., are -1.0, -0.6, -0.2, 0.2, 0.6, 1.0 respectively. For example, since a is strongly negatively correlated to the anchor, μ4 = 0.9 then it is very likely that μr 2 0.1. On the other hand, H45 would be in the vicinity of 0.9.
All ue's are sampled 200 times where for each time, 100 reward samples are collected. These reward samples are used to train & using Algorithm with T 200 time intervals. A summary of arm embeddings is visualized in Figure 3 It follows the expectation where the more correlated a, is to do, the distance to is lower, and vice versa. To view one example of the spatial positioning of the arm embeddings in scatter plot, see Supplementary Material A.6
5.2 Contextual Bandit Experiments
This experiment demonstrates the efficacy of C33 on the problem described in Section 3.1 In the footsteps of the work by Zhhou et al. (2020), we evaluate using the same datasets from the OpenML repository by Vanschoren al. (2014), namely shuttle (King et al.; 1995). MagicTelescope (Bock 2007), covertype [Blackard] 1998) and mnist (LeCun) 1998). For this set of experiments, the context space is the input space, and A is the corresponding label space. The reward one if the selected arm matches the ground truth label, otherwise zero. Unlike Zhou et al. (2020), we do not standardize the inputs because gives the models some hindsight information which goes against the philosophy of multi-armed bandits. Note that this does not usually fit the typical setting of a bandit problem and C3 targets a more general problem.
believe that
C3 requires historical samples for ó to be trained, where historical samples are uncommon for bandit ex- periments but incredibly common for industry use cases. To ensure fair comparison, we ensure that other baseline methods, such as LinUCB (Li et al.] 2010), Thompson sampling for contextual bandits (LinTS) AAgraaal & Goyal 2013), SquareCB Footer & Rakhlin 2020 NeuralUCB (Zhou et al. 2020), and neural
9

---

Published in Transactions on Machine Learning Research (03/2026)
shuttie
MagicTelescope
1000
Cumulative regret
Cumulative regret
750
LinUC
LinUCB
NeuralUCB
400
NeuralUCB
500
LinTS
LinTS
NeuralTS
200
NeuralTS
250
SquareCB
SquareCB
0
0
200
400
600
800
1000
0
200
400
600
800
1000
steps
Number steps
covertype
MNIST
1000
Cumulaaivv regret
Cumulativv regret
750
LinUCB
750
LinUCB
NeuralUCB
NeuralUCH
LinTs
500
NeuraITS
SquareCB
SquareCB
250
200
1000
Number of steps
Number of steps
Figure 4: Cumulative regret of the test split of the four datasets with 1.96 sigma error bars over 10 random seeds. Note that in MNIST, LinTS cannot be computed due to numerical issues from the high dimensionality. In Telesoeee,,,,,, NeuralUCB and LinTS almost completely overlap because they all repeatedly exploit the same action after the initial steps.
Thompson sampling (NcuralTS) (Zhang et al. 2021). are given the same amount of information. All algo- rithms updated using subset for training and evaluated on different test subset. This is necessary to avoid contamination when training d. The test split contains 1000 unseen samples. Appendix A.9 contains an ablation study of C3 with different RBF bandwidth values.
The results are shown in Figure 4 C3 outperforms most of the algorithms most datasets. C3 outper- forms the next best algorithm for each dataset by 5.7% lower cumulative regret on average. In shuttle, MagicTelescope, and covertype, these problems are of lower dimensionality and more linearly separable hence LinUCB and SquareCB (with linear regression oracle) perform well. On the other hand, NeuralUCB excels in the MNIST dataset since the multilayer perceptron works well with high- digh-dimensional data.
5.3 News Recommendation
Ca will be evaluated on news recommendation which is a realistic example for the problem described Section 3.3 This paper uses the Microsoft News Dataset (MIND) by Wu al. (2020) for evaluation. The context will be the frequency of a user's historical visits by news category. The news articles to recommend. The reward is whether the user clicks the chosen news article. The objective of algorithm is to minimize the cumulative regret. For clarity in results, regret is measured relative to the best performing algorithm where at time t, 0 is given to the best performing algorithm and the rest of the algorithms are given their respective relative regret.
space is the set of valid
We form dense representations of news articles from their titles using the pooler output of BERT model (Devlin et al. 2019). We use principal component analysis reduce the dimensions 64 to be used arm embeddings. Whenever eight articles, but the valid arm set varies for each user.
visits, there is small collection of possible articles to recommend, up to
In this set of experiments, Cg will be configured so that every 100 steps, it will randomly remove approx- imately 20% of samples in Dref to account for the concept. drift. The hypothesis is that because of the Lipschitz assumption, more recent samples would be more relevant estimating the mean rewards.
Due to the rigidity of assumptions of other bandit algorithms tailored for theoretical results, some bascline algorithms in Section 5.2 could effectively target all complexities of the problem for various reasons.
10

---

Published in Transactions on Machine Learning Research (03/2026)
MIND
BayesLR
(small)
Tvo Tower (aarge)
Cumulative regret
SW-LinUCB
90
D-UnnUCB
Caussian Process
80
Orline-NUCB
Online-NIS
40
CRB
20
100
200
400
500
Number of steps
Figure 5: Cumulative regret of the MIND dataset with 1 sigma error bars over 10 random seeds. "small" and "large' refers to the relative number parameters in the two tower models.
However, we add more specialized algorithms. We compare C3 with one of the most popular recent designs for recommender systems: the two-tower neural net work. Huang et al.] (2020) uses a deep encoder for query information and another deep encoder for item information then uses the cosine similarity between the two embeddings. A Gaussian process with forgetting also included Kaufmann et al. (2012), where the forgetting is necessary since it could not handle the entire history and needs to account for the non-stationarity. A similar baseline is using Bayesian linear regression model that takes concatenated vector of user and article features and returns the mean and standard deviation of estimated rewards, similar to the Gaussian process. Linear and neural baselines from Section 5.2 are modified to handle the non-stationarity elements. We also compare with the contextual restless bandit algorithm Chen & Hou (2024). Full experimental details are found Supplementary Material A.11
The result can be seen in Figure C3 demonstrates click lift of 12.4% compared to the baselines. Initially, C3 does do as well as the two tower approaches (which are static). As the drift of click rate increases in magnitude, C3 begins to adapt to the drift as it removes older samples in Dret while the other algorithms incur regret at the same rate.
6 Discussions
Effective Data Utilization Unlike typical contextual bandit settings, C3 requires the use of historical data to "warm-start' the algorithm. In reality, advertisement campaigns, pricing schemes, etc. will involve some degree of human-designed policy the initial stages which means there could be some data albeit possibly sub-optimal. Sub-optimality is not an issue for the training of since the main objective of á is to learn reward distributions and coupling, not optimality. As result, can effectively utilize samples from prior campaigns or trials in an off-policy manner. Furthermore, & can be resilient to concept. drifts so data from different time period may still be utilized.
Generalization to Embedding Models This paper demonstrates that Thompson sampling acting embedding space can offer method of exploration. However, only simple multi-layer perceptron is used as an embedding model. There should be no restrictions on the model design or inputs as long as it is cost- sensitive regression model. A side effect of operating on an embedding model is the ability to visualize the Icarnod embodding space which can be useful for applications that require some aaansparency/epplannaltl
Limitations of C3 The transductive lcarning aspect and importance weight updates can result in high numerical instability since it relies on many sum and division operations of floating points. This effectively disallows quantization to be used. Also, as an algorithm that relies on a dataset for inference, it may not scale millions of points without some type of sampling if speed crucial the use case. The hyperparameter tuming of can be slightly challenging because the RBF kernel used in IWKR can result in vanishing gradients if points too far from some query point, the choice of bandwidth of the RBF kernel
11

---

Published in Transactions on Machine Learning Research (03/2026)
is important. More crucially, the performance of C2 is dependent on heuristics and whether the learned embedding space is well-calibrated.
7 Conclusion and Future Works
The design of the C3 algorithm sets applied perspective of using a contextual bandit algorithm bandits and recommendation problems. Contextual bandit algorithms have built-in exploration and online learning components while recommender systems have deep encoders that scale well with high dimensional data. By combining the best of worlds, we gain several advantages in practice such as the ability to handle non-stationarity from concept drift, no retraining needed, and leveraging arm features. While this work contributes to the practical side of bandit algorithms, future works should inchude obtaining a con-stationary bound that extends the stationary regret bound in Theorem
Broader Impact Statement
To be best of our knowledge, our work does not have a direct negative impact it outlines algorithm to dynamically learn patterns. External factors such the data by others on the C3 algorithm, the application of the algorithm on malicious lask would be out of our control.
Acknowledgments
We thank Manulife Financial for the funding, guidance and exposure that motivated this work. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, companies sponsoring the Vector Institute attps::/vectorinstiiuue httpptteeae.pptteerspppp/////// current- pereent-patterss// the Natural Sciences and Engincering Council of Canada and grant from IITP & MSIT of Korea (No. RRS-2024-00457882, AI Research Hub Project).
12

---

Published in Transactions on Machine Learning Research (03/2026)
References
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with lincar payoffi.. In Inter- national conference machine learning, pp. 127 135. PMLR, 2013.
Yikun Ban, Yunzhe Qi, and Jingrui He. Neural contextual bandits for personalized recommendation. In Companion Proceedings of the ACM Web Conference 2024, pp. 1246-1249, 2024.
Soumya Basu, Orestis Papadigenopoulos, Constantine Caramanis, and Sanjay Shakkottai. Contextual block- ing bandits. In International Conference on Artificial Intelligence and Statistics, pp. 271-279. PMLR, 2021.
Alberto Bietti, Alekh Agarwal, and John Langford. A contextual bandit bake-off. Journal of Machine Learning Research, 22 (133))11-49, 2021.
Jock Blackard.
Covertype. https::/doi.org//// (t//dd..oo/0..24/333333 11..1.42.222.. C50K5N. 10.24443//C5KK55
UCI
Machine
Learning
Repository, 1998.
DOL:
Bock. MAGIC
Gammaa Telescope.
UCI
Machine
Learning
Repository, 2007.
DOL:
https:/ https::/doi.org//// wtw.org//........ 11..1102222222 C52C8B. 22522228
Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Ar- naud Joly, Brian Holt, and Gaël Varoquaux. API design for machine learning software: experiences from the scikit-learn project. In ECML PKDD Workshop: Languages for Data Mining and Machine Learning, pp. 108-122, 2013.
Xin Chen and I-Hong Hou. Contextual restless multi-armed bandits with application to demand response maaisi. In 2024 IEEE 63rd Conference on Decision and Control (CDC), pp. 2652-2657. IEEE, 2024.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208 214. JMLR Workshop and Conference Proceedings, 2011.
Jacob Devlin, Ming-
Sing-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirec- tional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguislies: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 4171 411144 Min- neapolis, Minnesota, June 2019. Association for Computational Linguisties. doi: 10.18653/v1/NBB 1423. URL httpp:://cclanthooogg. -twpoooooooooo//--119999990
Zhenhua Dong, Zhe Wang, Jun Xu, Ruiming Tang, and Jirong Wen. A brief history of recommender systems. arXiv preprint Xrx:::2209. 01860, 2022.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pp. 3199 3210. PMLR, 2020.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pp. 1321 1330. PMLR, 2017.
Samarth Gupta, Shreyas Chaudhari, Gauri Joshi, and Osman Yagan. Multi-armed bandits with correlated arms. IEEE Transactions on Information Theory, 67(10):6711 1-112,6722222 2021.
Jui-Ting Huang, Ashish Sharma, Shuying Sun, Li Xia, David Zhang, Philip Pronin, Janani Padmanabhan, Giusoppe Ottaviano, and Linjun Yang. Embodding-ben retricval in facebook search. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2553-25611 2020.
13

---

Published in Transactions on Machine Learning Research (03/2026)
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Emilie Kaulmann, Olivier Cappé, and Aurélien Garivier. On bayesian upper confidence bounds for bandit problems. In Artificial intelligence and statistics, pp. 592-600. PMLR, 2012.
Ross D. King, Cao Feng, and Alistair Sutherland. Statlog: comparison of classification algorithms on large real-world problems. Applied Artificial Intelligence an International Journal, 9(3):289 333, 1995.
Thomas Kleine Bucning, Andirupa Saha, Christos Dimitrakakis, and Haifeng Xu. Strategic linear contextual bandils. Advances in Neural Information Processing Systems, 37:116638 116675, 2024.
Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. Tn International Conference on Arli- ficial Intelligence and Statistics, pp. 2066 2076. PMLR, 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. htt////mm/mmss///////////// 1998.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandie approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661 670, 2010.
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(12)23346 2363, 2018.
Tyler Lu, Dávid Pál, and Martin Pál. Contextual multi-armed bandits. In Proceedings of the Thirteenth international conference on Artificial Intelligence and Statistics, pp. 485-492. JMLR Workshop and Con- ference Proceedings, 2010.
Elizbar A Nadaraya. On estimating regression. Theory of Probability & Its Applications, 9(1):141-142, 1964.
Mahdi Pakdaman Nacini, Gregory Cooper, and Milos Hauskrocht. Obtaining well calibrated probabilities using bayesian binning, In Proceedings of the AAAI conference on artificial intelligence, volume 29, 2015.
Yoan Russac, Claire Vernade, and Olivier Cappé. Weighted linear bandits for non-stationary environments. Advances in Newral Information Processing Systems, 32, 2019.
Aleksandrs Slivkins. Contextual bandits with similarity information. In Proceedings of the 24th annual Conference On Learning Theory, pp. 679-702. JMLR Workshop and Conference Proceedings, 2011.
Aleksandrs Slivkins and Eli Upfal. Adapting a changing environment: the brownian restless bandits. In COLT, pp. 343-354, 2008.
Niranjan Srinivas, Andreas Kranse, Sham M Kakade, and Matthias Seoger. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXio:0912.3995, 2009.
Fei Sun, Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang. Bert4rec: Sequential recommendation with bidirectional encoder representations from transformer. In Proceedings of the 28th ACM international conference information and knowledge management, pp. 1441-1450, 2019.
Michal Valko, Nathaniel Korda, Rémi Munos, This Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint orXiw:1309 6869, 2013.
Laurens Van der Maaten and Gcoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
Joaquin Vanschoren, Jan N Van Rijn, Bernd Bischl, and Luis Torgo Openml: networked science in machine learning. ACM SIGKDD Faplorations Newsletter, 15(2):49 60, 2014.
14

---

Published in Transactions on Machine Learning Research (03/2026)
Siwei Wang, Longbo Huang, and John Lui. Restless-ucb, efficient and low-complexity algorithm for online restless bandits. Advances in Neural Informalion Processing Systems,
2020.
Peter Whittle. Restless bandits: Activity allocation in changing world. Journal of applied probability, 25 (A):287 298, 1988.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowiez, et al. Huggingface's transformers: State-of-the-art natural language processing, Xr preprint arXiv:1910.05: 037771, 2019.
Fangzhao Wu, Ying Qiao, Jiun Jiun-Hung Chen, Chuhan Wu, Tao Qi, Jianxun Lian, Danyang Liu, Xing Xie, Jianfeng Gao, Winnie Wu, et al. Mind: A large-scale dataset for news recommendation. In Proceedings of the 58th anmual meeting of the association for compulational linguistics, pp. 3597 3606, 2020.
Xinyang Yi, Ji Yang, Lichan Hong, Derek Zhiyuan Cheng, Lukasz Heldt, Aditee Kumthekar, Zhe Zhao, Li Wei, and Ed Chi. Sampling-bias-corroetts neural modeling for large corpus item recommendations. In Proceedings of the 13th ACM Conference Recommender Systems, pp. 269 277, 2019.
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In International Conference Learning Representation (TCLR), 2021.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-basod exploration. International Conference on Machine Learning, pp. 11492 11502. PMLR, 2020.
A Appendix
A.1 Memoization of Importance Weight Computation
Theorem 1 Suppose a vector of importance weights w of n samples has been computed. The time complexity of updating the importance weights, given a new sample, (()).
Proof. Suppose there are samples in the embedding space {s, E S E [n]]. Consider the kernel matrix I. E RRnx which holds all pairwise RBF kernel values between every sample. From Equation 4 we can deduce that the sum of the ith row matrix will be w(s:), and similarly for the sum of the th column since L is symmetric. The importance weight of the initial reference dataset Diet can be calculated this way which takes on average ((n) per sample.
Suppose there is already the vector of importance weights for all samples in Dret denoted as w(x) (w(")... ... """"...,))]]]
[0,1]". We want to obtain an efficient update equation for w(++1), Naively computing L with sample will result in O(n2) time update. To update efficiently, memoization would be useful since wi(h) (n) itself stores the reciprocal of a sum. During inference, the unweighted RBF similarity score will need to be computed. This result can be stored, and is denoted as ((++1) = [*($*+1, 91) .. (($n41,8x))
There are two steps here: update the existing wn for i E [m] and append (n+1) to the new vector. To obtain w:" (n+1) for i e [n], the update equation can be expressed as a function of its previous value
(n+1) 1
E5tl 1((81, 83)
1
K(8i, 8x+ 1) + 2ÿ (5))
(x+1)
w
15

---

Published in Transactions on Machine Learning Research (03/2026)
which is constant time operation for each i [n] since all of the required values have already been computed. To compute the new importance weight,
(x++)
1
W wn+1
n+ j-= k(8n+1,88)
x(sp+1:8nt1) + Σj= 8(5
1 2 (n+1)
which is an (n) time operation for the new sample. Therefore, the entire update equation for the importance weight given new sample linear time operation.
A.2 Proof of Importance Weighted Kernel Regression Approximation
Theorem Suppose pls) is Lipschitz continuous on S. In the limit of the size of the reference dataset Pret where points are sufficiently sampled from the neighbourhood of some query point s, the importance weighted kernel regression with radial basis function kernel is approximate ostimator of μ(s).
Proof. The importance weighted kernel regression estimator of μ with RBF kernel is defined in Equation As the number of samples approaches n over space centered at the importance weight converges to the inverse of the sampling distribution. The effective contribution of each neighbouring subspace becomes approximately uniform and the estimate becomes
A(s) = Is n(s, (.s.s') R()sss) ds'
Is (x)s ds'
x((,88) L Is s"s ds
R(s')d ds'
Now, we focus the fractional term and show that it is simply the density of a Gaussian distribution.
||a-o'||
k((s Is k(s, 8") do""
exp
2n²
Ss exp
|--0"|
ds
2n
| s'll
((27)
101)
= =xx
20
Pr(X = s') where X ~ N(s.001)
Since we know that the conditional reward distribution is defined as R ~ Bernoull((((s),, for a sufficiently small RBF kernel bandwidth a,, under the Lipschitz continuity assumption,
A(s) [ P(X s')R(s')ds
ERR'S s] ((s)
o
A.3 Proof of Regret Bound in Theorem
For fixed embedding map dfc, a) trained offiine, C [0, 1]d is the learned joint embedding space, and we analyze directly on S. Assume that the true mean reward function μ S [0, 1] Lipschitz. There exists
16

---

Published in Transactions on Machine Learning Research (03/2026)
L 0 such that for all s, E S
lu(s) p(s') - L| s'Il
Cumulative regret is formalized follows. Let 8 argmax pls) be optimal action, where SA is the set of embeddings of all valid arms at time t. The expected cumulative regret is
Ry E u(s)) u(st)
We standardize the notions. The RBF kernel kx())) has bandwidth h > 0. The reference datasel Dr-1 {st, r=)) stores all embeddinggrreaard tuples up to time t- 1. The values of the Beta parameters az-1 (8) and 8 (8) are obtained by comparing query embedding E S to every embedding in the reference dataset, and their sum is the kernel mass
Tt 11-1(8) = Σ (8,888))
The IWKR procedure samples from the constructed Beta distribution
O₂(s) ~ (sta( B
and plays = argmax,ESA, (s).
For the analysis of Ca, truncated RBF kernel (compact support) for exact locality.
Kn(s, (a(=,,'):=exx) (-1l-- [_1ss- s'112)
1 [[]
s'll s h}
2h2
Proof. Let S C [0, 1]d without loss of generality by rescaling necessary. Partition [0, 1j into axis- axis-aligned hypercubes (cells) of length h. Let denote the set of all such cells intersocting S. The number of cells satisfies
2 h
g S
for h S 1
(11)
For each cell G, fix a representative point Ta n S, i.e. any point in the intersection. Define the cell index of any point E S as g(s) E G, and the best cell representative g* as
g argmax j(zg))
gEg
Because s² E S lies in some cell g(*"), the cell representative Ig(s-) is at distance of at. most the cell diameter
|| _g(a>) /l vdh
By the Lipschitz property,
m(s*) (1F S Lvdh
Since 9" maximizes p(zrg) over g, we have plxgr) 2 (((rg(e))). Hence,
pls*) u(æ,)) pls*) - u(zg(())) LVdh
17

---

Published in Transactions on Machine Learning Research (03/2026)
Decomposing regret gives
mls") - -p(s)) - (u(ss)) ) ((xgg)) )) + (A(ag)) - (lss))
S ITVoh (m((g)) -((s))
(12)
Up to this point, we approximated the continuum optimum 8 to the best cell representation at a regret cost of (Lh). The next step is to bound the second term, which is the regret relative to the best cell representation. To do so, we exploit the locality of the truncated kernel.
For any query 8, the kernel sums only involve past points 8; from the same cell g(s). Let the number of times we have played in cell g up to time - be
No - 1) = 1t = g
The cell's respective cumulative binary reward counts are
-t 1):
ri
Ft 1): N2 - 1) - -Sy(t 1)
ist =9
Now, fix query E g. The kernel mass is
1-1
Th- (8) = Σ (s) =
E (1)
igp(sc)=
Moreover, within cell g, any points have distance at most Vill, hence for 8, 84 E 9:
|| -|1-~all" 8:112]
d' 2
exp
2 exp
212
We call the right hand side E (0, 1). Therefore,
Na,V - 1) m- S Nt - 1)
(13)
Lemma 1. Let X ~ Beta(a, 3) with a, 3 1, and let p a/(a + B). Then for any E (0, (0,1-p),
Pr(X 2 2 < exp( ((a a + 3- 1)
Similarly, for any (0,p),
Pr(X p = exp(-22) + ))
Proof. Let ~ Beta(a, 9) and Y Binomial(n, x) where n = a + 3 1. By writing the regularized incomplete beta function representation of the Beta CDF and comparing the Binomial tail expression, one can obtain
Pr(X 2 x) = Pr(Y 1
Take p
&. e. Then E| n(p t). Note that p < 1, thus
S np because
a
np = (a + 3 - 1)
+ 3
= 0 a+? 3
0 p
18

---

Published in Transactions on Machine Learning Research (03/2026)
Therefore, the event Y I a implies Y mp
Pr(X 2 p +) = Pr(Y S a 5 & S <mp)
Note that n(p +e ne B|y - ne. Applying the Hocffding, random variables gives
Seefdding/hhroofffi Chernoff lower-tail bound for Binomial
Pr(Y < E|y] nE) -
Connecting both gives
Pr(X p < Pr(Y s mp) = Pr(Y z E|y] - 8 3-1)*²
Define the gap of a cell representative
Ag = ((xggg)) - 1( 2 0
Cells with Ag 0 are optimal within the grid. We want to show that each suboptimal cell g is selected only Ollog T/A times in expectation. Fix suboptimal cell with Ag > 0. Consider the event at time that IWKR selects a point in cell g. This can happen only if the Beta sample for cell is unusually high or the Beta sample for the best cell g* is unusually low.
Concretely, good event refers to
Eg = {
Sg Ng
Ag
mxx,)
1
and similarly
{S5 Sgr Ng- [N0-
Ag
Eg
u(xg))
By Hoeffding's inequality for Bernoulli sums, conditional
Ng n1
A
2
n1
Pr(EgIN, = n) s exxp
-2n
4 = 2 exp
Let Or,y be the cell-level random variable for the Beta sample corresponding to any query point in cell g at time L. They are all functions the same within-cell data, only differing constants via kernel weights. Its parameters satisfy a + = 17 and with Equation 13 we have 1) 2 CaNNg.
On event Eg. the empirical mean is close p(z;)) and because the posterior mean is equal to the IWKR mean, which (within cell) is weighted average of the ry's, can bound the posterior mean deviation by the same scale (absorbing weigtt constants into a dimension constant). Denoting Fi as the history to 1-
A 2
[F-1] -0(x))()) S
implies
A Fr-1
A 2
Pr Org 2 p( +
< exp
-2(11 1)
Cam
$ exp
19

---

Published in Transactions on Machine Learning Research (03/2026)
when using Lemma with Ag/2 and n can. Similarly, for the optimal cell g", event Eg. with Ng
Au Pr 0r.- S ((xge)
camA 3
2 Fi-1 S exp
2
Now, define the "bad event" that could cause selecting
B((g) = (Or. 2 rg
If g's sample is below p(xz)) + A and gn sample is above ulzgg) 4g/2, event Be(g) cannot occur because
Ag
2 < (1(1))) +
4g = - 2
(A, = ((xgg))) u(xzg)
< rr.
Therefore,
B((g)= S { 0ig 2 m(1g) Ag u uooo S (((zg') Ag
2
Applying the union bound on (g(g) gives
A
Pr(B:(g))N, =n, =m) s Pr(EgIN, =) + Pr(Eg 1N =m) +r
Ono 2 ((1g))
Fi-11
2
Ag
Pr O $ S((xg') )
FF
nA?
mA? 2 9
Gadd
cam 9
< 2 exp
4
+ 2 exp
exp
+ exp
8
2
2
Since m 2 0, the terms involving m only help. upper bound, we drop them and keep only the n-dependent decay
nA
Can
Pr(B.(g))N, = n, N₂- m) S 2exp
+ exp
+
8
2
For it to a useful bound, we want to set a rule where once n exceeds a logarithmic threshold, the probability of selecting g becomes most 1/T Let
16
Bg =
CaA2 log T
Then for all 2 ng.
C 2
Aa
exp
< exp
2
2
< exp(
-8 Slog 2')
7
20

---

Published in Transactions on Machine Learning Research (03/2026)
and similarly exp(-nA3/8) ST- for suitable constant. Hence, for 2 ng
Pr(Br(g) N₂ =n) CCT
(14)
for some constant C1 depending only on d.
To bound the expected number of times cell is selected, we split the sum according to whether (t 1) ng or No(1- 1) 2 Rg
EIN, (T)
Pr(g(si) = g))
T S n2
Pr(g(se)= = g. Ntt 11) 2 nn)
On (Ng(t - 1) 2 ng): selecting g implies Be(g). So,
Pr(g(s:)= g, (t 1) 2 n3) - Pr(B.(o). N, -1 n2y
((g())) = 9) S B,(o))
= - ny - EETT -t nn
(Fi-1
measurable/ non mea-uraaraa split)
canssurable/oon-meeet
(result from Equation
CTT-
Therefore, with C1/T for T 223,
(T), S ng + TCTT-2 = =ng + C.T -1 S 2ng
and finally substituting the value of n gives
log T
([N,(T) S C2
A y
for each suboptimal cell g where C2 only depends on To summarize, the cumulative regret relative to the best cell
E
Σ p(xg)) -m(s))
Σ ([N
BEg
log
Σ
A
C2
A
g:A,>0
C2 log
Σ
1
(15)
A
9:A,>0
Next, we bound the worst case control of the gap-dependent term via an E-split. For any threshold e > 0, split cell into: near optimal G5e {g Ag {) and clearly suboptimal G>E = {g A, > e). Trivially, regret from near-optimal cells is at most Ts because each play can be upper bounded by regret.
Σ A,ENN
S Σ (TN,(T)) = ET
9
21

---

Published in Transactions on Machine Learning Research (03/2026)
For clearly suboptimal cells, using Equation 15
Σ AB s C2 Σ
1
A
g:A.7E
g:A,7E
C2 log T
g:g22
g
C2 log T
h-d S Czlog
using Equation
E
for some constant C3- Combining results from the E splits,
Σ p(=g)) m(si) SET Cs log h-d
E
Since within one cell, the Lipschitz variation is O(Li), the grid optimum u(xg)) is only meaningful up to Lh, so we Lh. Upon substitution, the cumulative regret relative the best cell is
Σ p(xgg) m(si) s LLT + Css log T (d+1)
E
(16)
L
Continuing from Equation
12
we begin to form the overall cumulative regret bound.
T
T
E E( = Σ uls*)= - m(xg.) ) +
Σ u(xg)) - u((s))
1=1
< TLvdh dh + Σ [(xgg))) sp(se)
from Equation 12
S C,LhT CG h (d+1)
from Equation and C₁ 1 1 vd
What remains is to optimize the bandwidth with schedule so as to obtain useful regret bound. By finding the stationary point,
S(h) C, + C3 log T (d+1)
L
f'(h) C,LT - -Cs log T
L + 1d++2
we obtain the optimal value of h
log T
212
1,2T
Plugging h into the regret bound gives
E[ & CL 1 2 (log ata
This is standard nonparametric Tipschitz-type rate T T with mild (log T) factor.
7
22

---

Published in Transactions on Machine Learning Research (03/2026)
A.4 Generation of Correlated Arms
p= 0.5 50
p= 0 =
p= 0.5 c=
0.70
0.65
0.7
0.60
0.7
0.55
0.6
0.50
0.4
0.45
0.40
0.3
0.2
0.35
0.2
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
He
0.5 5
p=0|c=5
0=5. c
1.0
1.0
0.8
0.8
0.6
0.6
0.5
0.4
0.4
0.4
0.2
0.2
0.0
0.1
0.25
0.50
0.75
1.00
0.25
0.50
0.75
1.00
0.25
0.50
0.75
1.00
40
Figure 6: Visualization of impacts of various correlation p and e parameters on the μ of non-anchor arms. Each subplot contains 500 random samples.
Suppose Ho has been sampled from the Uniform(0, 1) distribution. Now, suppose we want to generate the reward distribution for arm with correlation pe with po- The mean parameter for arm is generated follows:
sample
Beta(2o(pp(He 0.5) + 2c(p,(000 - (o) + 0.5))
(17)
where is hyperparameter that controls the variance of the reward distribution of the correlated arm; the higher e is, the lower the variance. In our experiments, the value of e is chosen to be 50. Examples of sampled correlated fı's can be found in Figure
A.5 Correlation Experiment Details
The training dataset consists of 200 random but correlated values of 14's, and 100 samples of arm-reward pairs with arms being uniformly sampled. & is a multilayer perceptron that takes a 7-dimensional vector (one-hot encoded for each arm including the anchor arm), has single hidden layer of size 256 and an output dimension of 2. Each set of weights is interleaved with Softplus activation layer. The bandwidth parameter of the RBF kernel is chosen to be a =
The loss function for & is chosen to be L(ā,r) LaCR(D, r) (A, where the ECE loss uses bins. For each the training epochs, 50% the entire training dataset is sampled to be used for training, of which 20% will be used as the reference datasct and the remaining 80% contains the querics. The learning rate 10-3 (Adam optimizer with default configurations) with an exponential decay rate of 0.99 per epoch. Since no validation dataset is used, the resultant model of the final epoch will be used.
23

---

Published in Transactions on Machine Learning Research (03/2026)
A.6 Scatter plot of Correlated Arm Embeddings
Randomly initialized ø
Trained 6
-0.15
0.50
-0.20
0.25
Arm (o- target)
Later: dimension 2
Latant Latant dimension 2
0.00
Arm (o- 1.0)
-0.25
-0.25
Arm -021
-0.50
Arm (o 0.6)
Arm (o 1.0)
-0.75
-0.35
-1.00
-0.40
-1.25
0.44
0.46
0.48
0.50
0.52
0.54
-0.50
-0.25
0.00
0.25
0.50
0.75
1.00
1.25 3.50
Latent dimension
Latent dimension
Figure 7: The left figure shows the arm embeddings prior to any fitting while the right figure shows the arm embeddings after training using A Algorithm 1 The blue point is the anchor point and the green points are positively correlated to the μ of the blue point while the red points are negatively correlated.
A.7 Contextual Bandit Experiment Details
The four datasets obtained using scikit-learn's APT by Buitinck et al. (2013)- There is minimal data preprocessing done in this set of experiments: converting the labels to one-hot representations and converting MNIST's pixel values from bit unsigned integers to floating points between 0 and 1.
Only 50% of all datasets were used because of two reasons: (1) using all takes a long time to evaluate
especially for NeuralUCB and NeuralTS, (2) the additional 50% during evaluation would only show a longer "linear' portion in the cumulative regret curve since contextual bandit algorithms tend be unable practically avoid any mistakes.
All algorithms are given 4 samples to update, followed by 1 evaluation sample (which is also used to update the algorithm). This repeats until 1000 evaluation samples are provided. The datasets are shuflle at the beginning of each of the 10 experiments, so different 4000 training samples and 1000 evaluation samples are used cach time. For the offline training of 6, the training split was used to optimize for Φ. This explains why there must training and evaluation split this set of experiments.
Let de be the dimension of the context vector and de be the dimension of the arm vectors. Due to the varying complexities of each dataset, have to vary the number of layers. Each set of weights is interleaved with Softplus activation layer. Consider the layers [e,,.., Em] where E, indicates the size of each layer, and the leftmost and rightmost elements in the array represent the input and output dimensions respectively.
1. shuttle: [d. da 32, 4
MagicTelescope: [d. + d,y 64, 8)
3. covertype: [dg + da 64. 8]
mnist: [de + d, 64,8]
The following hyperparamcters are the same for all C3 experiments of every datasct. The RBF bandwidth is 1 and the loss functions LBCB(f, 2Cgcu(A.)) where the ECE loss uses bins. The learning rate is set to 10-3 (Adam optimizer with default configurations) with exponential decay rate of 0.99 per epoch.
24

---

Published in Transactions on Machine Learning Research (03/2026)
The batch size is 16. During each epoch, 10% of the entire training split is sampled to be used for training, of which 20% will be used as the reference dataset and the remaining 80% contains the queries. There is no partitioning of the reference dataset since this is a stationary problem.
The implementation of LinUCB and LinTS was obtained from a package called striatum, while the imple- mentation of NeuralUCB and NeuralTS was obtained directly from the GitHub repository of the authors. SquareCB was obtained from Coba, which uses a linear model as regression oracle. In LinUCB, we selected to be 1.96 which controls the exploration factor. In LinTS, select the default configurations with 6 0.5 and R 0.01 which are the parameters used in the theoretical regret analysis. For epsilon, it was set to the reciprocal of the number of steps which is the rocommended value. For NeuralUCB, we followed the exact hyperparameters that were used in their paper which is 10-5 and À = 10-5 (Zhou et al. 2020). For NeuralTS, we set == 10-6 and À = 10 which obtained from Zhang et al. (2021)'s 'ss repository. The update schedule for NeuralUCB and NeuralTS is as follows: for the first 2000 steps, the gradient descent optimization is performed for every step. Afterwards, it performed only once every 200 steps.
A.8 Scatterplot of MNIST Context- Arm Embeddings
2D embedding plot of MNIST
t-SNE reduced embedding plot of MNIST
8
30
20
10:
Latent dimension
4-
Latent dimension
-10
-30
-2-
-2
-40
-20
20
40
Latent /mmension
Latent dimension
Figure Embedding space of MNIST digits with correct arms chosen where the left shows the embedding vectors of with output dimension of 2, and the right shows the embedding vectors of another with output dimension of but uses t-SNE (Van der Maaten & Hinton 2008) for visualization.
25

---

Published in Transactions on Machine Learning Research (03/2026)
A.9
Ablation RBF Bandwidth in C3
ablation study (on Cover dataset)
d= 0.33
800
0= 0.5
1.0
0=2
Cumulative regret
600
0=
400
200
200
400
600
800
1000
Number of steps
Figure 9: Cumulative regret of C3 with varying parameter (for the RBF kernel) the Cover dataset with 1.96 sigma error bars over 10 random seeds.
To demonstrate the effects of varying the RBF kernel, we conduct ablation study to identify: (1) possible failure cases, and (2) potential robustness across parameters. In experiments in the main paper, the RBF bandwidth a was set to a = We vary a by 2 and times larger and smaller, leading to new combinations: 0.33, 0.5, 3. There are two groups of results in Figure g The obvious outlier is a 0.33 which essentially could not learn a failure case. We postulate this because the effective "search' radius is too small and did not leverage (or condition on) neighbouring points make an estimate. The other group, the of the o's, showed invariance to the choice of they are statistically identical in performance. This is advantage this simplifies the hyperparameter luning process as long as is not too small.
A.10 Hardware Usage for Experiments
Ca, NeuralUCB and NeuralT'S use GPU-acceleration since they have many parameters that need to be optimized. LinUCB, LinTSS and SquareCB use CPU only, The GPU used for all experiments in this paper was NVIDIA T4V2 with 16 GB of VRAM. 12 CPU cores with 48 GB of RAM were used for all experiments.
A.11 MIND Experiment Details
Prior to the experiments, the titles of all news articles are converted to BERT embeddings. The specific pretrained model for BERT from Hugginglace (Wolf et al.] 2019) is bert-base-uncant The resultant vectors that summarize the entire news article are of size 768 so we used PCA to downsample to 64 dimensions and saved the embedding vectors as a file.
The test dataset provided by MIND does not include labels WW et al. 2020 so we could not use that split. Instcad, we combine the training and validation datasets that span days. These datascts contain information on article impressions and clicks, i.e. what the users see and which ones do they interact with. Since there are many of them, we decided to be selective and remove instances with nine or more articles shown and sample 20% of the entire datasot. This limits the initial amount of information given to the models and forces the evaluation to be based on incremental learning and exploration strategies.
The first three days were selected to be used as training and validation datasets 80% training and 20% validation. This implics that reference datasets during the training of & will be partitioned into 3 partitions. The remaining four days will be used as pool of test data. Given computational constraints, especially over 10 random seeds, we pick only 500 points to be tested. However, the chosen 500 points are
26

---

Published in Transactions on Machine Learning Research (03/2026)
Table 2: Augmenting and diminishing probability schedules by day
Day
Probability
0.00
10
0.00
11
0.10
12
0.15
13
0.20
14
0.25
0.30
selected in a way that takes into account the date. Specifically, every jth (fixed) entry is selected as test points such that the first and last points are close to the start of the fourth day and end of the seventh day respectively.
To demonstrate stronger concept drift so that its effect can be seen in fewer test samples, we gradually modify the click rate that the sports category will have higher click rate over time and all other categories will have a lower click rate in the same time span. An optimal agent should recognize this change and adapt to it.
We augment the click rates of the sports category and diminish the click rate of every other category. For augmenting, for any sports instance which is not a click, we sample a Bernoulli random variable (1 mcans click, 0 means no click) with probability Pr(X- = 1) = P: and assign that value to be click value. Similarly, for diminishing, for any non-sports instance which is click, we sample Bernoulli random variable with probability Pr(X 0) p; and assign that value to be the click value. The probabilities by day are shown in Table 2
Φ was trained with the loss function r(A,r) = LBCE(A, r) + 0.01 LECE r), where the ECF loss uses 5 bins. à is initialized to be a multilayer perceptron with input dimension of 82 (18 news categories for context and 64 dimensional arm fcatures), single hidden layer of dimension 512 and an output dimension of 128. The bandwidth for the RBF kernel is chosen to be 0.6. o is trained for 20 epochs with a batch size of 32. The learning rate is set 10-3 (Adam optimizer with default configurations) with exponential decay rate of 0.9. At each epoch, only 10% of the training data is used for training, where 1% of them are used reference samples while the rest are used as query points. The & chosen for testing is the one that attains the lowest validation loss.
For the Bayesian linear regression model, the a parameter, which controls the degree of exploration through the coefficient of the standard deviation of reward, set 1.96. X, the parameter for numerical stability and regularization, and o, the standard deviation of the residuals, are set to
Two towers refer to the context encoder and arm encoder, which are both mappings to the same embedding space. The dot product between the context vector and arm vector represents the logits which are then passed to a softmax layer. The two towers implementation has two variants: small and large. For the small variant, the context encoder layers are [18, 64, 32] and the arm encoder layers are [64, 128, 32]. For the large variant, the context encoder layers are [18, 64, 64) and the arm encoder layers are [64, 256, 64). The linear layers of both variants are interleaved with a ReLU activation layer. The small variant was trained for 5 epochs while the large variant was trained for 40 epochs. The learning rates 8 10-3 3 (Adam optimizer with default 31, (8)) and the batch sizes are 32. For each variant, the model chosen for testing is the one that attains the lowest validation loss.
The modifications to the linear baseline algorithms are sliding window (SW) and discounting (D). Sliding window means that they are refitted with the most recent subset (50000 samples), while discounting uses a weighted lincar regression Russac et al. (2019) with y of 0.95. For the neural basclines, the online modification changing the buffer into sliding window (2000 samples). Note that the neural models are initially trained with the intire training size, the sliding window buffer is only used during test time.
27

---

Published in Transactions on Machine Learning Research (03/2026)
The Gaussian process, due to its cubic time complexity with respect to the number of samples, is restricted to subsampling of 0.05. The forgetting element works by replacing the oldest sample with the newly seen sample, keeping the buffer the same size. The contextual restless bandit (CRB) requires heavy modification. Since the arms vary with almost no repeating arms, the state space is incredibly sparse and a transition dynamic that is unknown with minimal samples. Our problem does not have complex budget constraint so the linear programming component ignored.
A.12 MIND Time Plot
MIND time analysis
C₁ BayesLR
Two Tower (small)
Two Tower llarge)
SW-LinUCB
D-LinUCB
1000
Gaussian Process
Time
Online NUCB
Online-NV
CRB
300
400
Number of steps
Figure 10: Time taken in seconds against timesteps for each algorithm.
Figure 10 shows a measure of time efficiency for each algorithm. The plot for some algorithms do not start at zero as they require some amount of warmup. The most prominent the two lower approaches as they are relatively large models. The stepwise pattern in C33 is attributed an unoptimized approach of dropping samples in its buffer. As mentioned in Section [.3] 20% of its samples are dropped every 100 steps. This implementation could be improved in future work.
28


Reviews:
[{"review_id": "jYmHsp54Hz", "reviewer": "Reviewer_23th", "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": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 work studies the learning problem of contextual bandits with correlated arms in a non-stationary reward setting. They devised a conditionally coupled contextual Thompson sampling (C3) algorithm, evaluated its empirical performance with some classical algorithms such as LinUCB and LinTS, and demonstrated that its empirical performance outperforms the compared algorithms.", "claims_and_evidence_yn": "No", "claims_explanation": "1. The literature discussion is not sufficient. All the references in this work are pretty out-of-date. The most recent cited work is from 2023. The majority of the references are around 2020. For the past 5 years, there have been plenty of learning algorithms for solving contextual bandit and Gaussian process bandit problems. \n\n2. This work does not provide any meaningful theoretical results. \n\n3. Empirically, C3 algorithm is not compared to the state-of-the-art algorithms. Also, as compared to LinTS, I suspect the empirical performance improvement is from the choice of priors. Usually, we have beta prior gives better performance than Gaussian priors. So, it is not a fair comparison.", "audience_yn": "Yes", "audience_explanation": "The same as above.\n\nAfter reading the rebuttals:\n\nI do believe and am convinced that practitioners will be more interested in this work.", "requested_changes": "1. I suggest to adding more recent literatures.\n\n2. Empirical experiments also need to use the state-of-the-art algorithms as the baseline.", "broader_impact_concerns": "N/A", "additional_comments": "I also have some questions. \n\n1. For problem set-up in Section 3.1, the key feature is the Bernoulli mean parameter function $\\mu: \\mathcal{C} \\times \\mathcal{A} \\rightarrow [0,1]$ is assumed to be Lipschitz continuous. If I assume that the context for each arm $a \\in \\mathcal{A}$ is a Lipschitz continuous function, can you clarify the difference between your setting and the setting I have mentioned?\n\n2. What is the key technical difficulty between the stationary and non-stationary reward setting, i.e., \n$\\mu: \\mathcal{C} \\times \\mathcal{A} \\rightarrow [0,1]$ vs $\\mu: \\mathcal{C} \\times \\mathcal{A} \\times [T] \\rightarrow [0,1]$ in terms of developing algorithms?", "extra_scores": {}, "extra_text": {}}, {"review_id": "lA97wll5Cq", "reviewer": "Reviewer_cc5g", "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": "", "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": "### New Problem Setting\nThis paper introduces a new contextual bandit framework that combines non-linear reward functions and non-stationary reward distributions, with additional assumption that the arms can be conditionally coupled. This new problem setting is realistic in many practical applications.  \n\n### Introduction of C3 Thompson sampling Algorithm\nThis paper proposes the C3 Thompson sampling algorithm to solve the contextual bandit problem with coupled arms, which is the the first algorithm in this non-stationary setting. By leveraging Importance Weighted Kernel Regression (IWKR) as a nonparametric reward estimator, the algorithm avoids gradient-based updates during inference, improving the efficiency of the method.  \n\n### Empirical Evaluation with Practical Datasets\nThis paper use experiments on real-world datasets to demonstrate the superiority of the performance of the C3 Thompson sampling algorithm. Compared to baseline algorithms such as NeuralTS and NeuralUCB, the new algorithm demonstrates lower cumulative regret in the experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper claims that the C3 algorithm can effectively handle dense arm features, non-linear reward functions, and non-stationarity and outperforms the prior state-of-the-art algorithms in regret minimization. These claims are supported by experiments across different real-world datasets and are convincing.  \n\nAlthough the empirical performance of the C3 algorithm is convincing, the authors didn't provide any formal theoretical guarantees of the regret bound and how it compares to baseline algorithms theoretically. Also, the paper could add comparisons to recent non-stationary bandit algorithms such as Restless UCB to strengthen the claim.", "audience_yn": "Yes", "audience_explanation": "This paper focuses on non-linear, non-stationary contextual bandit problems and proposed new algorithm framework for these settings, which would be of interest to researchers working on contextual bandits, real-world RL systems, recommendation algorithms, and adaptive learning under drift. Despite lacking theoretical regret bounds, its focus on bridging algorithmic ideas with practical scalability and the demonstrated strong performance make it a useful contribution for applied ML researchers.", "requested_changes": "### The following proposed adjustments would strengthen the work but are not critical:  \n(1) Add recent bandit algorithms specifically designed for non-stationary settings such as Restless-UCB into the baseline comparisons.  \n(2) In Section 3.2, add extra explanations of coupled arms and how coupling persists over time in non-stationary environments.  \n(3) Add comparisons of runtime and memory usage between different algorithms to further demonstrate the efficiency of the new algorithm", "broader_impact_concerns": "Not Applicable", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Orv8h1FaM6", "reviewer": "Reviewer_7iGu", "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": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 proposes a practical Thompson-sampling approach for feature-rich, non-stationary contextual bandits using\n(1) learned embeddings, (2) importance-weighted kernel regression, (3) Beta mapping to enable TS without online backprop.\n\n Strengths\n- Practical, deployable design (append/prune ref set; no online gradients).\n- Clear method; IW-kernel + Beta posterior is neat.\n- Competitive results on OpenML; adapts under synthetic drift on MIND.", "claims_and_evidence_yn": "No", "claims_explanation": "Several central claims are not convincingly supported. Key drift-aware baselines (e.g., sliding-window/discounted LinUCB/TS, online NeuralUCB/TS, kernel/GP with forgetting) are missing; the notion of “coupling” is not measured; there are no regret guarantees for stationary or drifting regimes; scalability ($O(kn)$ inference) isn’t validated; and reproducibility details (code/configs) are incomplete. These gaps make the evidence insufficient to fully support the paper’s claims.", "audience_yn": "Yes", "audience_explanation": "The paper presents a practical, deployable bandit approach for feature-rich, non-stationary settings (e.g., recommenders) that enables TS without online backprop. Even if evidence is incomplete, these ideas are of clear interest to practitioners and researchers working on real-time decision systems.", "requested_changes": "See additional comments,", "broader_impact_concerns": "N.A", "additional_comments": "Weaknesses\n- Missing drift-aware baselines (sliding-window/discounted LinUCB/TS, online NeuralUCB/TS, kernel/GP with forgetting).\n- No regret guarantees (stationary or drifting); theory limited to consistency and $O(n)$ updates.\n- “Coupling” notion not learned/quantified; little analysis vs. coupling strength.\n- Scalability not validated ($O(kn)$ inference; no ANN/coreset study).", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)