Standard contextual bandits often struggle when features fail to perfectly explain rewards—a phenomenon known as model misspecification. This research introduces a "robust" linear model that incorporates arm-specific random effects alongside shared contextual parameters, offering a flexible middle ground that is both statistically efficient and computationally fast.
The Challenge of Model Misspecification
In contextual bandit problems, a learning agent selects an "arm" (e.g., a recommendation) based on a "context" (e.g., user features). The standard approach uses a linear model, assuming the reward is the dot product of the context and an unknown parameter.
However, real-world features are rarely exhaustive. An item might possess an "intrinsic popularity" or specific quirk not captured in its metadata. Current solutions typically fall into two extremes:
- Separate parameters per arm: Highly flexible but "data hungry," as information is not shared across arms.
- Shared global parameter: Efficient to learn but brittle; if features are incomplete, the model fails to identify the optimal arm.
The authors propose a hybrid reward model to bridge this gap: $$\mu_{i,t} = x_{i,t}^\top \theta + v_i$$ Here, $\theta$ represents a shared contextual parameter, while $v_i$ is an arm-specific random variable (the "robust" offset) that accounts for what the features miss.
Algorithmic Innovations
The paper introduces RoLinUCB (Upper Confidence Bound) and RoLinTS (Thompson Sampling) based on this hybrid model. A key technical contribution is the use of Maximum a Posteriori (MAP) estimation to learn $\theta$ and $v_i$ simultaneously. This allows the model to interpolate between a pure contextual bandit (when features are highly predictive) and a standard multi-armed bandit (when features are poor).
A significant hurdle for such hybrid models is computational complexity. A naive implementation requires inverting a $(d+K) \times (d+K)$ matrix (where $d$ is feature dimension and $K$ is the number of arms), leading to $O((d+K)^3)$ per round. By leveraging the Woodbury matrix identity to exploit the covariance structure, the authors reduce this to $O(d^2(d+K))$, enabling scalability to thousands of arms.
Key Results and Insights
The approach was evaluated using synthetic data and the MovieLens 1M recommendation dataset. In synthetic tests, as misspecification ($\sigma_0$) increases, standard models like LinTS suffer from linear regret, whereas RoLinTS maintains sublinear regret by effectively learning the arm-specific offsets.
On the MovieLens 1M dataset, the researchers simulated misspecification by using only a tiny fraction (1% to 5%) of the data to pre-train item features. This resulted in "poor" features that did not fully explain user ratings.
As shown in the results, RoLinTS significantly outperforms standard LinTS when feature quality is low (1% training data). While all methods improve as feature quality increases (5% training data), RoLinTS maintains its lead. Furthermore, the optimized implementation proved to be up to 1,000 times faster than naive versions in benchmarks with over 1,000 arms.
Conclusion and Future Directions
The "Robust Contextual Linear Bandit" framework provides a practical "baseline + correction" mechanism. It automatically balances shared information and arm-specific data: early on, it relies on the shared parameter $\theta$; as more data is gathered for a specific arm, it shifts focus to the learned offset $v_i$.
Future work includes tightening the theoretical regret bounds, extending the framework to Generalized Linear Models (e.g., Logistic Regression for click-through rates), and refining methods for automatic hyper-parameter tuning of noise variances.
Summary updated