Abstract
This paper studies regret minimization in a multi-armed bandit. It is well known that side information, such as the prior distribution of arm means in Thompson sampling, can improve the statistical efficiency of the bandit algorithm. While the prior is a blessing when correctly specified, it is a curse when misspecified. To address this issue, we introduce the assumption of a random-effect model to bandits. In this model, the mean arm rewards are drawn independently from an unknown distribution, which we estimate. We derive a random-effect estimator of the arm means, analyze its uncertainty, and design a UCB algorithm ReUCB that uses it. We analyze ReUCB and derive an upper bound on its $n$-round Bayes regret, which improves upon not using the random-effect structure. Our experiments show that ReUCB can outperform Thompson sampling, without knowing the prior distribution of arm means.
Introduction
In the classic multi-armed bandit (MAB) problem, an agent aims to maximize rewards by selecting arms with unknown reward means. Standard frequentist approaches like UCB1 treat each arm in isolation, which often leads to slow convergence in environments with many arms. Conversely, Bayesian methods like Thompson Sampling (TS) leverage prior distributions to accelerate learning. While a correctly specified prior is a "blessing" for statistical efficiency, a misspecified prior—where the assumed distribution deviates from reality—can be a "curse," leading to high regret and sub-optimal decision-making.
This research addresses the "blessing and curse" trade-off by introducing the Random-Effect Bandit framework. The goal is to develop an algorithm that achieves the efficiency of Bayesian methods without the fragility associated with fixed, potentially incorrect priors.
Methodology: The ReUCB Algorithm
The core innovation is the application of a random-effect model to the bandit setting. Instead of treating arm means as fixed constants or requiring a pre-defined Bayesian prior, the authors assume arm means are drawn independently from an unknown global distribution.
Information Borrowing via BLUP
The algorithm utilizes the Best Linear Unbiased Predictor (BLUP) to estimate arm means. The BLUP estimator for an arm $k$ is a weighted combination of:
- Direct Evidence: The empirical mean of rewards observed for that specific arm.
- Global Evidence: An estimate of the common mean across all arms.
This "information borrowing" mechanism allows the agent to make informed guesses about "cold-start" arms (those with few observations) based on the aggregate performance of other arms. As more data is collected for a specific arm, the algorithm adaptively shifts weight from the global mean to the arm-specific mean.
Confidence Intervals and Parameter Estimation
ReUCB integrates the BLUP estimator into an Upper Confidence Bound (UCB) framework. By leveraging the random-effect structure, ReUCB generates tighter confidence intervals than UCB1, reducing unnecessary exploration of inferior arms. The algorithm also includes a variant that estimates variance parameters ($σ^2$ and $σ_0^2$) on the fly using the method of moments, ensuring practical applicability when environment parameters are unknown.
Empirical Evaluation
The authors evaluated ReUCB against UCB1 and Thompson Sampling across synthetic environments and real-world datasets.
Synthetic Experiments
In Gaussian and Bernoulli bandit simulations, ReUCB consistently achieved lower cumulative regret than UCB1. Notably, it often outperformed Thompson Sampling even when TS was given the correct prior, due to its adaptive nature.
Robustness to Misspecification
A critical finding is ReUCB's robustness. When Thompson Sampling is initialized with a "bad" prior (e.g., incorrect mean or variance), its performance degrades significantly, often resulting in linear regret. ReUCB avoids this failure mode by learning the distribution parameters directly from the observed data.
Real-World Application: MovieLens
The algorithm was tested on a recommendation task using the MovieLens dataset, where user groups were treated as bandit instances and movies as arms. ReUCB significantly outperformed baselines by effectively learning user preferences ("biases") across different groups, demonstrating its utility in practical recommendation systems.
Discussion and Future Work
ReUCB represents a frequentist alternative to hierarchical Bayesian models, capturing shared arm characteristics without hard-coded priors. Its adaptive weighting and narrower confidence intervals lead to superior exploration-exploitation trade-offs.
However, some limitations remain. The current framework is non-contextual; extending ReUCB to incorporate side information (e.g., user demographics) via "Random-Effect Contextual Bandits" is a promising future direction. Additionally, while empirically successful on binary data, the theoretical regret bounds currently rely on Gaussian or sub-Gaussian noise assumptions. Future work may focus on broadening these theoretical guarantees to a wider class of reward distributions.
Summary updated