No-Regret Linear Bandits beyond Realizability

Chong Liu, Ming Yin, Yu-Xiang Wang

Abstract

Standard guarantees for stochastic linear bandits typically rely on the "realizability" assumption, which posits that the true reward function is perfectly linear. In practice, this assumption is rarely met, and traditional theory suggests that even minor misspecification leads to linear regret. This paper challenges that pessimism by introducing the $\rho$-gap-adjusted misspecification ($\rho$-GAM) model. We demonstrate that the classic LinUCB algorithm is inherently robust to this form of misspecification, achieving near-optimal $\tilde{O}(\sqrt{T})$ regret as long as the model is accurate near the optimal action, regardless of its accuracy elsewhere.

Introduction

The stochastic linear bandit is a cornerstone of online learning, providing a framework for sequential decision-making in applications ranging from personalized medicine to recommendation systems. The efficacy of these models usually hinges on the belief that the reward function $f_0$ resides within a known linear class $\mathcal{F}$.

When this "realizability" fails, the standard approach is to assume a uniform error $\epsilon$ across the entire action space. However, this leads to a discouraging result: the algorithm eventually accumulates linear regret, meaning it never stops making significant errors relative to the optimum. This paper argues that such a global error requirement is unnecessarily strict. In most optimization tasks, we do not require a perfect global map; we only need the model to be accurate enough to distinguish the best actions from the rest.

The $\rho$-Gap-Adjusted Misspecification ($\rho$-GAM) Model

To bridge the gap between theory and practical robustness, we introduce a more flexible error model called $\rho$-GAM. Instead of a uniform error bound, $\rho$-GAM allows the approximation error at any point $x$ to be proportional to that point's suboptimality gap. Formally, we assume:

$$|f(x) - f_0(x)| \leq \rho(f^* - f_0(x))$$

where $f^*$ is the maximum possible reward and $\rho$ is a scaling constant. This condition captures a vital intuition: we can tolerate massive errors in "bad" regions of the action space as long as the model remains precise in "near-optimal" regions. This allows for non-linearities that would traditionally break linear bandit guarantees.

Algorithm and Analysis

One of the most surprising findings of this work is that we do not need to design a new, complex algorithm to handle $\rho$-GAM. The classic LinUCB (Linear Upper Confidence Bound) algorithm—originally designed for perfectly linear environments—is automatically robust to this type of misspecification.

The Self-Bounding Argument

The technical core of our proof is a "self-bounding" argument. In standard misspecified bandit analysis, the error is treated as external noise that accumulates over time. Under $\rho$-GAM, however, the error is proportional to the suboptimality gap, which is the very definition of instantaneous regret. This allows us to bound the misspecification error using the regret itself. By absorbing the error term into the main regret analysis, we prevent the regret from blowing up linearly, maintaining the sublinear growth required for "no-regret" performance.

Empirical Validation

While primarily a theoretical contribution, we validated the $\rho$-GAM framework using a synthetic 1D simulation. We tested a non-linear, piece-wise function that violates standard linearity but satisfies the $\rho$-GAM condition.

In these experiments, uniform sampling (which does not exploit the linear structure) accumulated linear regret as expected. In contrast, LinUCB quickly identified the optimal region. Once the algorithm focused its sampling on the near-optimal area—where the $\rho$-GAM condition ensures high accuracy—the cumulative regret curve flattened, confirming the $\tilde{O}(\sqrt{T})$ theoretical bound in practice.

Key Results and Insights

  • Near-Optimal Regret: We prove that LinUCB achieves a cumulative regret of $\tilde{O}(\frac{\sqrt{T}}{1-\rho})$. This represents an exponential improvement in average regret ($R_T / T$) compared to the uniform misspecification setting, where average regret does not vanish.
  • Local vs. Global Accuracy: Our results suggest that for optimization, "good enough" is often sufficient. Robustness is achieved not by being right everywhere, but by being right where it matters.
  • Robustness Threshold: The current proof holds as long as $\rho$ is roughly $O(1/\sqrt{d \log T})$. While this suggests $\rho$ might need to decrease for very large $T$, for practical horizons (e.g., $T = 10^{12}$), $\rho$ can remain a significant constant (approximately 0.19).

Conclusion and Future Work

This work demonstrates that linear bandit algorithms are far more robust than previously thought. By shifting the focus from global realizability to local, gap-adjusted accuracy, we provide a theoretical foundation for why simple linear models often perform well in complex, non-linear worlds.

Future research may explore whether specific algorithm designs can handle a constant $\rho$ up to 1 without requiring it to shrink with $T$. Additionally, the $\rho$-GAM framework is generic and could be extended to more complex settings, such as Kernelized Bandits or Reinforcement Learning, where function approximation is almost inevitably misspecified.

Summary updated

BibTeX
@inproceedings{liu2023no,
  author = {Chong Liu and Ming Yin and Yu-Xiang Wang},
  title = {{No-Regret Linear Bandits beyond Realizability}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=wKaF6UBPIp},
}
Figure