Introduction
In online decision-making environments, such as personalized recommendation systems or digital advertising, the multi-armed bandit (MAB) framework is a foundational tool. However, practitioners often face a critical choice: should they use a simple model that ignores context to learn quickly, or a complex linear model that utilizes side information but requires more data to converge? This paper introduces OSOM (Optimistic Selection Of Models), an algorithm designed to bridge this gap by automatically adapting to the underlying reward structure without prior knowledge.
The Model Selection Dilemma
Standard MAB algorithms, like Upper Confidence Bound (UCB), achieve an instance-optimal regret of $O(\log n)$ when rewards are independent of context. However, if the environment is truly contextual, these simple models suffer linear regret because they ignore the very information that determines success.
Conversely, linear contextual bandit algorithms like OFUL (Optimistically Facing Uncertainty under Linearity) are minimax-optimal—$\tilde{O}(\sqrt{n})$—in complex environments. However, they incur a heavy "regret penalty" proportional to the context dimension ($d$) even when the context is irrelevant. Existing meta-algorithms designed to combine strategies often fail to preserve the fast $O(\log n)$ rate of simple models. OSOM aims to achieve the best of both worlds: the fast rate for simple models and the minimax rate for complex ones.
The OSOM Algorithm
OSOM operates on a "best-of-both-worlds" principle through a structured four-step process:
- Initial Simplicity: The algorithm begins by selecting arms based on a standard UCB-style estimate, treating the problem as a simple MAB.
- Parallel Estimation: While executing the simple strategy, OSOM maintains a ridge-regression estimate of a more complex linear model in the background.
- Sequential Testing: In each round, the algorithm performs a statistical test comparing the cumulative rewards received by the simple model against an optimistic projection of what the complex linear model could have achieved.
- The Switch: If the potential gains from the complex model significantly exceed the actual rewards of the simple model—beyond a threshold defined by self-normalized concentration bounds—the algorithm concludes the simple model is insufficient. It then permanently switches to a linear contextual strategy (a variant of OFUL).
Theoretical and Empirical Results
The key innovation lies in exploiting the nested structure of these models; a simple MAB is essentially a linear model where the context-coefficient vector $\theta^*$ is zero. By assuming stochastic contexts, OSOM can effectively learn the complex model's parameters even while primarily playing the simple strategy.
Theoretically, OSOM achieves:
- Simple Regime: $O(\sum \frac{\log n}{\Delta_i})$ regret, matching the instance-optimal rate of UCB.
- Complex Regime: $\tilde{O}((\sqrt{d} + \sqrt{K})\sqrt{n})$ regret, matching the minimax-optimal rate of OFUL.
Empirical simulations with $K=5$ arms and $d=50$ dimensions confirm these results. In synthetic tests, OSOM's regret curve perfectly tracks UCB when context is irrelevant (where OFUL performs poorly) and tracks OFUL when context is significant (where UCB fails with linear regret). It effectively "picks the winner" automatically.
Limitations and Future Work
While OSOM provides a robust solution for nested linear models, several challenges remain. The current framework relies heavily on the assumption of stochastic contexts and linear reward structures. Future research may explore:
- Generalization: Extending the logic to non-linear or non-nested models.
- Adversarial Contexts: Adapting the statistical tests for scenarios where contexts might be chosen by an adversary.
- Problem-Dependent Rates: Achieving logarithmic regret rates within the complex regime, rather than just the minimax-optimal rate.
Summary updated