Linear Bandits in Unknown Environments

Thibault Gisselbrecht, Sylvain Lamprier, Patrick Gallinari

Introduction

Standard contextual bandit algorithms have become a cornerstone of modern recommendation systems and decision-making frameworks. These models typically operate under the assumption that the "features" or "contexts" of the available choices (arms) are perfectly known at each time step. For instance, a recommendation engine might assume it has access to a complete and accurate profile of a user before deciding which advertisement to display.

However, in many real-world applications, this assumption of perfect information fails. In "unknown environments," feature vectors are not directly observable; instead, they must be estimated from noisy, sparse samples. Consider the challenge of identifying influential voices on social media during a rapidly evolving event like an election. An agent does not know a user's intrinsic interests or influence (their "true profile") upfront. It only observes noisy samples—individual tweets—and due to API constraints or the sheer volume of data, it may only be able to sample a small fraction of the user base. This creates a "double uncertainty" problem: the agent is uncertain about the global reward parameters (how features map to outcomes) and the specific features of each individual arm.

The SampLinUCB Algorithm

To address this challenge, the authors introduce SampLinUCB (Sampled Linear Upper Confidence Bound). This approach extends the classical LinUCB algorithm to account for the noise inherent in feature estimation.

Core Innovation: Dual Optimism

In a standard linear bandit, the algorithm calculates an Upper Confidence Bound (UCB) based on the uncertainty of a learned weight vector $\theta$. SampLinUCB introduces an additional "bonus" term that accounts for the uncertainty in the estimated feature vectors $\hat{x}_{a,t}$. The algorithm maintains an empirical mean of the samples observed for each arm to approximate its true profile. The resulting UCB score is designed to be optimistic in two distinct ways:

  1. Model Optimism: It assumes the reward model (the mapping from features to rewards) might be more favorable than current estimates suggest.
  2. Feature Optimism: It assumes an arm's true underlying profile might be better than the noisy samples observed thus far.

Sampling Scenarios

The paper explores the robustness of SampLinUCB across three distinct sampling regimes:

  • Case 1 (Full Observation): Every arm provides a feature sample at every time step. While theoretically useful, this is rarely achievable in large-scale systems.
  • Case 2 (Probabilistic Observation): Each arm has a fixed probability $p$ of providing a sample at any given step, representing random data availability.
  • Case 3 (Selection-Based Observation): Only the arm selected by the agent in the previous round provides a new sample. This is the most restrictive and realistic scenario, as it forces the agent to use its choices to actively gather information about the environment.

Experimental Evaluation: Twitter Social Monitoring

The authors validated SampLinUCB using a large-scale dataset of Twitter activity during the 2012 US Presidential Elections. The simulation involved 5,000 users over a 10-day period, encompassing approximately 2.15 million messages.

Feature and Reward Engineering

To translate raw social media data into a bandit framework, the researchers employed Latent Dirichlet Allocation (LDA) to compress tweets into 30-dimensional topic vectors. The "reward" for selecting a user was defined by the retweet count of their messages, provided the content fell into specific relevant categories (e.g., politics, science, or religion). A pre-trained Support Vector Machine (SVM), trained on the 20 Newsgroups dataset, was used to classify the tweets and filter the rewards.

Key Results and Insights

Theoretical Performance

The authors derived a finite-time, high-probability upper bound on regret, proving that SampLinUCB achieves sublinear regret—specifically $O(\log(n)\sqrt{n})$. This theoretical guarantee ensures that the agent will eventually converge toward an optimal strategy even in the presence of feature noise.

Empirical Superiority

In the Twitter simulation, SampLinUCB consistently outperformed non-contextual bandit baselines such as CUCB and CUCBV. The algorithm demonstrated remarkable robustness to data sparsity; even when samples were available for only 1% of the environment (mimicking the limitations of the Twitter Sample API), the agent successfully learned to identify high-reward users.

Active Learning Synergy

A particularly striking result was observed in Case 3. The algorithm performed significantly better when it "actively" chose which users to sample compared to receiving random samples at the same rate (Case 2). This suggests that SampLinUCB effectively balances exploitation (choosing known high-performers) with active exploration (choosing arms specifically to reduce feature uncertainty).

Limitations and Future Directions

While SampLinUCB represents a significant step forward for bandits in noisy environments, several challenges remain:

  • Stationarity: The model assumes a user's "true profile" is constant. In reality, social media interests are dynamic, suggesting a need for non-stationary extensions that can track shifting features.
  • Sample Bias: The mathematical proofs rely on samples being centered on the true profile. If samples are biased (e.g., a user only tweets about specific topics during outliers), the model's accuracy may degrade.
  • Scalability: The algorithm requires matrix inversions that may become computationally expensive as the number of features ($d$) or arms ($K$) increases, necessitating further optimization for web-scale applications.

Conclusion

SampLinUCB provides a robust framework for decision-making when the characteristics of the choices are not fully known. By explicitly modeling uncertainty in both rewards and features, the algorithm enables effective learning in complex, real-world environments where data is noisy and information must be actively sought.

Summary updated

Abstract

In contextual bandit problems, an agent has to choose an action among a bigger set of available ones at each decision step, according to features observed on them. The goal is to define a decision strategy that maximizes the cumulative reward of actions over time. We focus on the specific case where the features of each action correspond to some kind of a constant profile, which can be used to determine its intrinsic utility for the task in concern. If there exists an unknown linear application that allows rewards to be mapped from profiles, this can be leveraged to greatly improve the exploitation-exploration trade-off of stationary stochastic methods like UCB. In this paper, we consider the case where action profiles are unknown beforehand. Instead, the agent only observes sample vectors, with mean equal to the true profiles, for a subset of actions at each decision step. We propose a new algorithm, called SampLinUCB, and derive a finite time high probability upper bound on its regret. We also provide numerical experiments on a task of focused data capture from online social networks.
BibTeX
@inproceedings{gisselbrecht2016linear,
  author = {Thibault Gisselbrecht and Sylvain Lamprier and Patrick Gallinari},
  title = {{Linear Bandits in Unknown Environments}},
  booktitle = {ECML/PKDD},
  year = {2016},
  doi = {10.1007/978-3-319-46227-1\_18},
}

Loading related content...

Figure