Abstract
Standard multi-armed bandit (MAB) algorithms often face a trade-off between the robustness of frequentist methods like UCB1 and the efficiency of Bayesian methods like Thompson Sampling (TS). While TS is highly efficient when given a perfect prior distribution, its performance degrades significantly if the prior is misspecified. This paper introduces Random Effect Bandits, a framework that treats arm means as being drawn from an unknown common distribution and estimates that distribution dynamically. The resulting algorithm, ReUCB, leverages the statistical efficiency of Bayesian methods while maintaining the robustness of frequentist approaches. Empirical evaluations show that ReUCB consistently outperforms traditional benchmarks, even when they have access to the true prior.
Introduction
In the multi-armed bandit problem, an agent must balance exploring new actions with exploiting known high-reward actions. Traditional approaches generally fall into two categories:
- Frequentist (e.g., UCB1): These treat each arm's mean as a fixed, independent value. While robust, they can be slow to converge because they do not assume any shared structure between arms.
- Bayesian (e.g., Thompson Sampling): These assume arm means are drawn from a known prior distribution. If the prior is correct, learning is rapid. However, if the prior is "misspecified" (incorrect), the agent may suffer from high regret for an extended period.
The Random Effect Bandit framework bridges this gap by exploiting shared structure (the "random effect") without requiring a perfectly guessed prior distribution.
Methodology: The ReUCB Algorithm
The authors propose a Random-Effect Model where each arm's mean reward $\mu_k$ is defined as: $$\mu_k = \mu_0 + \delta_k$$ where $\mu_0$ is a common global mean and $\delta_k$ is a random offset. Unlike standard Bayesian methods, $\mu_0$ and the associated variances are unknown and must be estimated from observed data.
Best Linear Unbiased Predictor (BLUP)
ReUCB utilizes the BLUP estimator, a statistical tool that "borrows strength" from all arms. Instead of relying solely on an arm's individual sample mean, the BLUP estimator calculates a weighted average of the specific arm's performance and the estimated global mean. An adaptive weighting mechanism automatically balances these terms: in "cold-start" scenarios with few samples, the algorithm relies more on the global average; as more data is collected, it shifts focus to the specific arm's performance.
Tighter Confidence Bounds
By integrating the BLUP estimator into an Upper Confidence Bound (UCB) framework, the authors derive tighter confidence intervals. They prove that the variance of the random-effect estimator is strictly smaller than that of a standard sample mean, allowing for less "optimistic" and more efficient exploration.
Experimental Results
The paper evaluates ReUCB against UCB1 and Thompson Sampling across synthetic environments and the real-world MovieLens dataset.
As shown in Figure 1, ReUCB achieves significantly lower regret than UCB1 across various reward distributions (Gaussian and Uniform). Notably, it often matches or exceeds the performance of Thompson Sampling even when TS is initialized with the correct prior.
Robustness to Misspecification
A key advantage of ReUCB is its resilience to incorrect assumptions about the reward distribution. While Thompson Sampling can fail catastrophically if given a biased prior, ReUCB remains stable because it learns the "prior" parameters directly from the data.
Figure 3 illustrates this robustness. In scenarios where TS variants suffer from linear regret due to misspecification (such as TSm2 in panel a), ReUCB continues to converge efficiently. This stability extends to non-Gaussian rewards, such as Bernoulli and Truncated Gaussian distributions.
Conclusion and Future Work
ReUCB demonstrates that modeling shared structure through random effects provides a powerful middle ground between frequentist and Bayesian bandit algorithms. It offers the "blessing" of structure—using global knowledge to inform exploration of new arms—without the fragility of fixed priors.
Future research directions include extending this framework to contextual bandits, where arm rewards also depend on external features, and providing a more rigorous theoretical analysis for cases where reward variances are entirely unknown.
Summary updated