Misspecified Linear Bandits

Avishek Ghosh, Sayak Ray Chowdhury, Aditya Gopalan

Abstract: We consider the problem of online learning in misspecified linear stochastic multi-armed bandit problems. Regret guarantees for state-of-the-art linear bandit algorithms such as Optimism in the Face of Uncertainty Linear bandit (OFUL) hold under the assumption that the arms' expected rewards are perfectly linear in their features. It is, however, of interest to investigate the impact of potential misspecification in linear bandit models, where the expected rewards are perturbed away from the linear subspace determined by the arms' features. Although OFUL has recently been shown to be robust to relatively small deviations from linearity, we show that any linear bandit algorithm that enjoys optimal regret performance in the perfectly linear setting (e.g., OFUL) must suffer linear regret under a sparse additive perturbation of the linear model. In an attempt to overcome this negative result, we define a natural class of bandit models characterized by a non-sparse deviation from linearity. We finally develop a novel bandit algorithm, comprising a hypothesis test for linearity followed by a decision to use either the OFUL or Upper Confidence Bound (UCB) algorithm. For perfectly linear bandit models, the algorithm provably exhibits OFUL's favorable regret performance, while for misspecified models satisfying the non-sparse deviation property, the algorithm avoids the linear regret phenomenon and falls back on UCB's sublinear regret scaling. Numerical experiments on synthetic data, and on recommendation data from the public Yahoo! Learning to Rank Challenge dataset, empirically support our findings.

Introduction

Multi-Armed Bandit (MAB) problems are central to modern recommendation systems and online advertising. While standard algorithms like UCB are effective, they scale poorly with the number of arms. Linear bandits address this by assuming rewards are a linear function of arm features, allowing for efficient learning across massive action spaces. However, this "Linearity Assumption" is a strong one, and real-world data is often "misspecified"—meaning the relationship between features and rewards is almost linear, but not quite. This paper explores the fragility of linear bandit algorithms and proposes a robust alternative.

The Fragility of Linear Bandits

Standard linear bandit algorithms, such as OFUL (Optimism in the Face of Uncertainty Linear bandit), are designed to aggressively exploit the linear structure of the reward model. While this leads to optimal $O(d\sqrt{T})$ regret in perfectly linear settings, it creates a significant vulnerability. The authors demonstrate that even a tiny, sparse deviation—where only a single arm's reward deviates from the linear model—can cause these algorithms to suffer linear regret. They essentially get "trapped" by an outlier and stop exploring the true optimal arm.

The Robust Linear Bandit (RLB) Algorithm

To address this, the authors introduce the Robust Linear Bandit (RLB). RLB is a meta-algorithm that adaptively chooses between linear and non-linear strategies based on a hypothesis test. It operates in three phases:

  1. Initial Sampling: The algorithm begins by sampling $d+1$ arms multiple times to gather empirical data.
  2. Hypothesis Testing: Using data from the first $d$ arms, it constructs a linear model to predict the reward of the $(d+1)$-th arm. If the observed reward falls within a specific confidence interval of the prediction, the linear hypothesis ($H_0$) is accepted. Otherwise, it is rejected in favor of a misspecified model ($H_1$).
  3. Adaptive Execution:
    • If $H_0$ is accepted, RLB runs OFUL, reaping the efficiency of the linear model.
  4. If $H_1$ is accepted, it ignores the features and falls back to UCB, treating arms as independent. This ensures sublinear regret even when the linear model is useless.

Notably, RLB is designed to target "non-sparse" deviations, where error is distributed across the feature space, overcoming the theoretical impossibility of being optimal for both perfectly linear models and sparse deviations.

Empirical Evaluation

The RLB algorithm was tested on both synthetic and real-world datasets to verify its theoretical guarantees.

Regret performance on synthetic data comparing UCB, OFUL, and RLB with varying parameters.

In synthetic environments (Figure 1), RLB demonstrates its ability to match the performance of the best-suited algorithm. When the model is misspecified, RLB avoids the catastrophic linear regret seen in standard linear algorithms like OFUL.

Regret curves on the Yahoo! Learning to Rank dataset, showing RLB's robustness to real-world misspecification.

On the Yahoo! Learning to Rank Challenge dataset (Figure 2), RLB correctly identifies the presence of misspecification. In these scenarios, OFUL suffers from high regret due to its rigid adherence to a flawed linear model, while RLB switches to a UCB-style strategy and significantly outperforms it.

Conclusion

The RLB algorithm provides a "best-of-both-worlds" solution for linear bandit problems. By incorporating a hypothesis test for linearity, it reaps the benefits of linear models when they are accurate while maintaining robustness through a fallback mechanism when they are not. This approach ensures sublinear regret across a wider range of practical scenarios, making it a valuable tool for real-world recommendation systems.

Summary updated

Abstract

We consider the problem of online learning in misspecified linear stochastic multi-armed bandit problems. Regret guarantees for state-of-the-art linear bandit algorithms such as Optimism in the Face of Uncertainty Linear bandit (OFUL) hold under the assumption that the arms expected rewards are perfectly linear in their features. It is, however, of interest to investigate the impact of potential misspecification in linear bandit models, where the expected rewards are perturbed away from the linear subspace determined by the arms features. Although OFUL has recently been shown to be robust to relatively small deviations from linearity, we show that any linear bandit algorithm that enjoys optimal regret performance in the perfectly linear setting (e.g., OFUL) must suffer linear regret under a sparse additive perturbation of the linear model. In an attempt to overcome this negative result, we define a natural class of bandit models characterized by a non-sparse deviation from linearity. We argue that the OFUL algorithm can fail to achieve sublinear regret even under models that have non-sparse deviation.We finally develop a novel bandit algorithm, comprising a hypothesis test for linearity followed by a decision to use either the OFUL or Upper Confidence Bound (UCB) algorithm. For perfectly linear bandit models, the algorithm provably exhibits OFULs favorable regret performance, while for misspecified models satisfying the non-sparse deviation property, the algorithm avoids the linear regret phenomenon and falls back on UCBs sublinear regret scaling. Numerical experiments on synthetic data, and on recommendation data from the public Yahoo! Learning to Rank Challenge dataset, empirically support our findings.
BibTeX
@inproceedings{ghosh2017misspecified,
  author = {Avishek Ghosh and Sayak Ray Chowdhury and Aditya Gopalan},
  title = {{Misspecified Linear Bandits}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  url = {https://openreview.net/forum?id=r1ZVTRxubB},
}
Figure