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.

Introduction

In online learning, multi-armed bandit (MAB) models are essential for sequential decision-making under uncertainty. Standard algorithms like Upper Confidence Bound (UCB) treat each action independently, which becomes inefficient as the number of actions grows. Linear bandit algorithms, such as Optimism in the Face of Uncertainty Linear bandit (OFUL), address this by assuming rewards are a linear function of arm features. This allows for generalization across arms, significantly reducing regret in high-dimensional spaces.

However, this efficiency is fragile. The assumption of perfect linearity rarely holds in real-world scenarios where features may be noisy or relationships complex. While previous work suggested linear bandits could handle minor deviations, this research demonstrates that even a single "mismatched" arm (a sparse perturbation) can cause state-of-the-art linear algorithms to suffer linear regret—meaning they fail to converge on the optimal strategy. This paper introduces the Robust Linear Bandit (RLB) to bridge the gap between specialized efficiency and general robustness.

The Robust Linear Bandit (RLB) Algorithm

The RLB algorithm employs a "best-of-both-worlds" strategy by incorporating a hypothesis test to detect model misspecification. The algorithm operates in three distinct phases:

  1. Initial Sampling: The algorithm pulls $d+1$ arms (where $d$ is the feature dimension) multiple times ($k$ samples each) to establish a baseline reward estimate.
  2. Hypothesis Testing: Using the first $d$ arms, RLB constructs a confidence ellipsoid for the hidden linear parameters ($\theta$). It then projects this ellipsoid onto the $(d+1)$-th arm to predict an expected reward interval. If the actual sampled reward for that arm falls outside this predicted interval, the model is flagged as misspecified.
  3. Strategic Switching:
    • If the test suggests linearity, RLB proceeds with the OFUL algorithm to exploit the linear structure.
  4. If misspecification is detected, RLB discards the potentially misleading features and falls back to the standard UCB algorithm, treating arms independently.

Empirical Evaluation

The authors tested RLB on both synthetic data and the Yahoo! Learning to Rank Challenge dataset. The results highlight the algorithm's ability to adapt to the underlying model structure.

Regret performance of RLB with varying sampling sizes k compared to OFUL and UCB.

A critical finding is the sensitivity to the initial sampling parameter $k$. As shown in the figures above, if $k$ is too small, the hypothesis test may fail to correctly identify the model type. Conversely, a very large $k$ increases the initial exploration cost, though it leads to more reliable long-term performance.

Performance in a misspecified environment where OFUL's linear assumption fails, causing linear regret, while RLB successfully reverts to UCB performance.

In misspecified settings, such as those found in the Yahoo! dataset, the standard OFUL algorithm often suffers from high regret because it attempts to fit a linear model to non-linear data. RLB successfully detects this mismatch and switches to a UCB-style strategy, avoiding the linear regret trap and significantly outperforming the pure linear approach.

Conclusion

RLB provides a robust framework for linear bandits by acknowledging that features can sometimes act as "distractors" rather than descriptors. By combining a rigorous hypothesis test with a fallback mechanism, RLB achieves $\tilde{O}(d\sqrt{T})$ regret in linear environments and $\tilde{O}(\sqrt{NT})$ in misspecified ones. Future work may involve extending this logic to Bayesian frameworks or more complex non-linear structures.

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