Robust Contextual Linear Bandits

Rong Zhu, Branislav Kveton

Standard contextual bandits often struggle when features fail to perfectly explain rewards—a phenomenon known as model misspecification. This research introduces a "robust" linear model that incorporates arm-specific random effects alongside shared contextual parameters, offering a flexible middle ground that is both statistically efficient and computationally fast.

The Challenge of Model Misspecification

In contextual bandit problems, a learning agent selects an "arm" (e.g., a recommendation) based on a "context" (e.g., user features). The standard approach uses a linear model, assuming the reward is the dot product of the context and an unknown parameter.

However, real-world features are rarely exhaustive. An item might possess an "intrinsic popularity" or specific quirk not captured in its metadata. Current solutions typically fall into two extremes:

  1. Separate parameters per arm: Highly flexible but "data hungry," as information is not shared across arms.
  2. Shared global parameter: Efficient to learn but brittle; if features are incomplete, the model fails to identify the optimal arm.

The authors propose a hybrid reward model to bridge this gap: $$\mu_{i,t} = x_{i,t}^\top \theta + v_i$$ Here, $\theta$ represents a shared contextual parameter, while $v_i$ is an arm-specific random variable (the "robust" offset) that accounts for what the features miss.

Algorithmic Innovations

The paper introduces RoLinUCB (Upper Confidence Bound) and RoLinTS (Thompson Sampling) based on this hybrid model. A key technical contribution is the use of Maximum a Posteriori (MAP) estimation to learn $\theta$ and $v_i$ simultaneously. This allows the model to interpolate between a pure contextual bandit (when features are highly predictive) and a standard multi-armed bandit (when features are poor).

Regret comparison across varying levels of model misspecification ($\sigma_0$) in synthetic environments.

A significant hurdle for such hybrid models is computational complexity. A naive implementation requires inverting a $(d+K) \times (d+K)$ matrix (where $d$ is feature dimension and $K$ is the number of arms), leading to $O((d+K)^3)$ per round. By leveraging the Woodbury matrix identity to exploit the covariance structure, the authors reduce this to $O(d^2(d+K))$, enabling scalability to thousands of arms.

Key Results and Insights

The approach was evaluated using synthetic data and the MovieLens 1M recommendation dataset. In synthetic tests, as misspecification ($\sigma_0$) increases, standard models like LinTS suffer from linear regret, whereas RoLinTS maintains sublinear regret by effectively learning the arm-specific offsets.

On the MovieLens 1M dataset, the researchers simulated misspecification by using only a tiny fraction (1% to 5%) of the data to pre-train item features. This resulted in "poor" features that did not fully explain user ratings.

Performance on the MovieLens 1M dataset with 1% training data, simulating high feature misspecification.

As shown in the results, RoLinTS significantly outperforms standard LinTS when feature quality is low (1% training data). While all methods improve as feature quality increases (5% training data), RoLinTS maintains its lead. Furthermore, the optimized implementation proved to be up to 1,000 times faster than naive versions in benchmarks with over 1,000 arms.

Conclusion and Future Directions

The "Robust Contextual Linear Bandit" framework provides a practical "baseline + correction" mechanism. It automatically balances shared information and arm-specific data: early on, it relies on the shared parameter $\theta$; as more data is gathered for a specific arm, it shifts focus to the learned offset $v_i$.

Future work includes tightening the theoretical regret bounds, extending the framework to Generalized Linear Models (e.g., Logistic Regression for click-through rates), and refining methods for automatic hyper-parameter tuning of noise variances.

Summary updated

Abstract

Model misspecification is a major consideration in applications of statistical methods and machine learning. However, it is often neglected in contextual bandits. This paper studies a common form of misspecification, an inter-arm heterogeneity that is not captured by context. To address this issue, we assume that the heterogeneity arises due to arm-specific random variables, which can be learned. We call this setting a robust contextual bandit. The arm-specific variables explain the unknown inter-arm heterogeneity, and we incorporate them in the robust contextual estimator of the mean reward and its uncertainty. We develop two efficient bandit algorithms for our setting: a UCB algorithm called RoLinUCB and a posterior-sampling algorithm called RoLinTS. We analyze both algorithms and bound their $n$-round Bayes regret. Our experiments show that RoLinTS is comparably statistically efficient to the classic methods when the misspecification is low, more robust when the misspecification is high, and significantly more computationally efficient than its naive implementation.
BibTeX
@misc{zhu2022robust,
  author = {Rong Zhu and Branislav Kveton},
  title = {{Robust Contextual Linear Bandits}},
  year = {2022},
  eprint = {2210.14483},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.14483},
}
Figure