OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits

Niladri S. Chatterji, Vidya Muthukumar, Peter L. Bartlett

Introduction

In the field of online decision-making, contextual bandits serve as the foundation for personalized recommendation systems. However, practitioners often face a critical model selection dilemma. If one employs a simple Multi-Armed Bandit (MAB) model that ignores context, the algorithm is highly efficient and learns quickly if the context is irrelevant. Yet, if context does matter, this simplicity leads to high "regret"—the lost potential reward from failing to personalize.

Conversely, adopting a complex linear contextual model (such as LinUCB or OFUL) introduces a "complexity tax." These algorithms have regret bounds that scale with the dimension of the context ($d$), causing them to learn significantly slower in simple environments where context is unnecessary. This paper introduces OSOM (Optimistic Selection Of Models), a single algorithm designed to be simultaneously optimal for both simple and complex environments.

The OSOM Algorithm

OSOM operates on a "start simple, then upgrade" philosophy, designed to achieve the instance-optimal $O(\log n)$ regret rate in simple environments and the minimax-optimal $O(\sqrt{n})$ rate in linear contextual models without prior knowledge of the environment's complexity.

  1. Initial Phase: The algorithm begins by playing a simple UCB-style strategy, assuming rewards are independent of context.
  2. Statistical Monitoring: At each round, OSOM performs a sequential statistical test. It maintains a "shadow" estimate of rewards using a complex linear model (via $\ell_2$-regularized least-squares).
  3. The Switch: The algorithm compares the estimated cumulative reward of the complex shadow model against the actual rewards earned by the simple model. If the difference exceeds a threshold ($W_\delta$)—constructed using self-normalized concentration bounds and the Matrix Freedman inequality—it concludes the simple model is insufficient.
  4. Complex Phase: Once the threshold is crossed, the algorithm switches permanently to a linear contextual bandit strategy.

Experimental Evaluation

The researchers evaluated OSOM using synthetic datasets to test theoretical limits across two primary scenarios: a Simple Instance (where context is irrelevant, $\theta^* = 0$) and a Complex Instance (where context significantly impacts rewards, $\|\theta^*\|_2 = 1$). The simulations utilized $K=5$ arms and a context dimension of $d=50$ over $n=300$ rounds.

Comparison of expected regret for OSOM, UCB, and OFUL under simple (MAB) and complex (linear contextual) models.

As shown in the figures, OSOM achieves the "best of both worlds." In the simple model, OSOM's regret curve tracks perfectly with UCB, avoiding the high regret incurred by OFUL. In the complex model, OSOM quickly detects the need for complexity and matches the performance of OFUL, whereas the simple UCB model suffers from linear regret because it cannot adapt to the context.

Key Insights

  • Exploiting Nested Structure: By treating the MAB model as a nested sub-case of the linear model, OSOM uses the simple model as a baseline to detect when more complexity is required.
  • One-Way Switch: Unlike "meta-algorithms" that constantly swap between learners (often leading to sub-optimal regret), OSOM’s definitive, statistically-backed switch preserves the $O(\log n)$ rate in simple regimes.
  • Regret as a Detection Tool: The algorithm specifically monitors if it is losing significant reward by not treating the environment as linear, rather than just testing for linearity itself. This distinction is vital for maintaining low regret.

Limitations and Future Work

While OSOM is computationally efficient and theoretically sound, it currently relies on the assumption of stochastic contexts with well-conditioned covariance matrices. Extending this to adversarial contexts remains an open challenge. Additionally, the current "permanent switch" mechanism may not be suitable for non-stationary environments where a model might transition from complex back to simple; future work may explore bi-directional adaptation.

Summary updated

BibTeX
@inproceedings{chatterji2020osom,
  author = {Niladri S. Chatterji and Vidya Muthukumar and Peter L. Bartlett},
  title = {{OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=gPN6bWJcusS},
}
Figure