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

Wei Min Loh [email protected], Sajib Kumer Sinha [email protected], Ankur Agarwal [email protected], Pascal Poupart [email protected] · 2026

Read A Practical Algorithm for Feature-Rich, Non-Stationary Bandit Problems by Wei Min Loh [email protected], Sajib Kumer Sinha [email protected], Ankur Agarwal [email protected], Pascal Poupart [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-16755.txt.

Introduction

Loh and co-authors tackle a harder form of the contextual bandit problem. Each choice has rich features, payoffs follow nonlinear rules, and payoffs drift over time while links between choices persist. Their method, C3 Thompson sampling, pairs a kernel-based estimator with Thompson sampling on an embedding space. It learns online with no retraining. The authors report average regret 5.7 percent lower than the next best method on four OpenML datasets. On Microsoft news data they report a 12.4 percent click lift.

Catalog record

CREATORWei Min Loh [email protected], Sajib Kumer Sinha [email protected], Ankur Agarwal [email protected], Pascal Poupart [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70382
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2603.16755

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Practical Algorithm for Feature-Rich, Non-Stationary Bandit Problems Wei Min Loh [email protected], Sajib Kumer Sinha [email protected], Ankur Agarwal [email protected], Pascal Poupart [email protected] 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 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 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. 1 1 1 Our implementation can be found on GitHub ( https://github.com/wmloh/c3 ). . 1 Introduction Multi-armed bandits are applicable in many domains where there is high stochasticity and limited opportunities to fully explore all possible arms ( 21 ) . A more useful variant of the problem called contextual bandit ( 25 ) tackles a significantly harder problem where it aims to optimize for the best arm for a 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 on 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. If the demand for bicycles rises, it is likely that the demand for helmets would go up too. Cycling, in some countries, is a seasonal activity where sales of bicycles and helmets differ during summer and winter. 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 ubiquitous in many practical applications. The primary contribution is developing an algorithm called conditionally coupled contextual ( C_{3} ) Thompson sampling that solves contextual bandits with correlated/coupled arms in bandit or recommendation tasks. To the best of our knowledge, it is the first algorithm that can solve contextual bandits with correlated/coupled arms in a non-stationary setting. Unlike many other neural contextual bandit approaches, there are no lengthy gradient-based updates at inference time. C_{3} can also leverage arm features, which reduces the cold-start problem on 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 23 can be considered one of the pioneering contextual bandit algorithms that demonstrated success through the use of simulated evaluation based on the Yahoo! news dataset. 9 followed up with a rigorous theoretical analysis of a variant of LinUCB. The other popular paradigm is the Bayesian approach where 1 developed a contextual bandit algorithm with Thompson sampling with a Gaussian likelihood and prior, assuming a linear 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 can learn non-linear reward functions. One of the earlier algorithms was the KernelUCB by 33 which extends LinUCB by exploiting reproducing kernel Hilbert space (RKHS). Similarly, 31 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 of the number of samples. After the breakthrough in the theoretical understanding of neural networks, particularly the neural tangent kernel (NTK) by 16 , 42 developed NeuralUCB which is a neural network-based contextual bandit algorithm with a complete theoretical analysis and a suite of empirical analysis which outperforms many algorithms in tabular dataset benchmarks from OpenML. More recent advancements include SquareCB ( 12 ) which reduces the problem of contextual 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. 20 introduced their take on randomized algorithms for contextual bandits. Their novel contributions include an additive Gaussian noise for a 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. 3 introduced a 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 arms. 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 a restless bandit, which is proposed by 37 . 36 introduced the Restless-UCB algorithm which provably solves restless bandits, but does not account for context in the environment. 8 improves upon this by leveraging context and budget constraints. A specialized solution by 29 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 arms 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, 30 introduced the contextual zooming algorithm that adaptively forms partitions in a similarity space. Operating on a space, as opposed to having fixed arms, allows them to effectively tackle the sleeping bandit problem. While they offer an innovative framework, it is likely that partitions in high-dimensional spaces (e.g. from large language models) would not be tractable. 19 proposed a situation that is potentially relevant to many applications from a game-theoretic 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 a negative phenomenon overall on the platform. 19 devised an incentive-aware learning algorithm to ensure that the learner obtains the right signal. 2.3 Recommender Systems There

Read the complete text