cs.LGMar 17, 2026

A Practical Algorithm for Feature-Rich, Non-Stationary Bandit Problems

Authors: Wei Min Loh, Sajib Kumer Sinha, Ankur Agarwal, Pascal Poupart

Organizations: University of Waterloo, Vector Institute · Manulife Financial

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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 C3 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 as well as demonstrating a 12.4% click lift on Microsoft News Dataset (MIND) compared to other algorithms.

Figures & tables

Figure 1: A three-arm example of strong and weak coupling during concept drift of expected reward distribution. Arms 1 and 2 are said to be strongly coupled , while arms 1 and 3 are said to be weakly coupled .
Figure 2: An example of Thompson sampling exploration in continuous spaces: [left] embedding space containing reference samples Dref\mathcal{D}_{\text{ref}} (circles) and different arms (stars) for a given context cc , and [right] constructed Beta distribution with (IWKR) and without (NWKR) importance weights. The true μ\mu of both arms for that context is 0.6.
AlgorithmInference timeUpdate timeNon-linear rewardsNon-stationary tasksArm features
C3C_{3}O(n)\mathcal{O}(n)O(1)\mathcal{O}(1)✓✓✓
LinearO(1)\mathcal{O}(1)O(1)\mathcal{O}(1)✗✗partially
NeuralO(1)\mathcal{O}(1)O(n)\mathcal{O}(n)✓✗✗
Table 1: Comparison between algorithms where linear refers to both LinUCB, LinTS, and SquareCB while neural refers to both NeuralUCB and NeuralTS. nn refers to the number of samples seen.
Figure 3: Distance from the anchor arm embedding as a function of correlation ρ\rho with 1.96 sigma error bars over 10 random seeds.
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 MagicTelescope, NeuralUCB and LinTS almost completely overlap because they all repeatedly exploit the same action after the initial 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 of parameters in the two tower models.
Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Visualization of impacts of various correlation ρ\rho and cc parameters on the μ\mu of non-anchor arms. Each subplot contains 500 random samples.
Figure 7: The left figure shows the arm embeddings prior to any fitting while the right figure shows the arm embeddings after training using Algorithm 1 . The blue point is the anchor point and the green points are positively correlated to the μ\mu of the blue point while the red points are negatively correlated.
Figure 8: Embedding space of MNIST digits with correct arms chosen where the left shows the embedding vectors of ϕ\phi with an output dimension of 2, and the right shows the embedding vectors of another ϕ\phi with an output dimension of 8 but uses tt -SNE ( Van der Maaten and Hinton, 2008 ) for visualization.
Figure 9: Cumulative regret of C3C_{3} with varying σ\sigma parameter (for the RBF kernel) on the Cover dataset with 1.96 sigma error bars over 10 random seeds.
DayProbability
90.00
100.00
110.10
120.15
130.20
140.25
Appendix
Table 2: Augmenting and diminishing probability schedules by day
Figure 10: Time taken in seconds against timesteps for each algorithm.

Explore similar work

CardsList

  1. Active Context Selection Improves Simple Regret in Contextual Bandits

    May 19, 2026Mohammad Shahverdikondori, Jalal Etesami, Negar KiyavashMulti-Armed BanditsBest-Arm Identification

    College of Management of Technology, EPFL · Department of Computer Science, TU Munich

  2. Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits

    Oct 12, 2025Jiazheng Sun, Weixin Wang, Pan XuEnsemble LearningContextual Bandits

    Duke University

  3. Flow-Corrected Thompson Sampling for Non-Stationary Contextual Bandits

    Jun 22, 2026AmirHossein Naghdi, Ali BaheriThompson SamplingNon-Stationary Bandits

    Sharif University of Technology, Iran · Rochester Institute of Technology, USA