Abstract
Linear contextual bandits (LCB) are a cornerstone of modern recommendation systems and online decision-making. However, a persistent gap has existed between practical algorithms with sub-optimal $O(d\sqrt{T})$ regret and theoretical models achieving $O(\sqrt{dT})$ regret at the cost of practicality. We present HyRan (Hybridization by Randomization), a novel algorithm that bridges this gap. By employing a "Squeeze All" estimator that leverages context information from all available arms and utilizing explicit randomization, HyRan achieves a near-optimal $O(\sqrt{dT \log T})$ regret bound while remaining fully adaptive. Empirical results demonstrate that HyRan significantly outperforms standard benchmarks, particularly in high-dimensional settings with correlated features.
Introduction
In the Linear Contextual Bandit (LCB) framework, a learner selects an action (arm) from a set of candidates based on observed feature vectors (contexts) to maximize cumulative rewards. The efficiency of such a learner is measured by "regret"—the difference between the reward of the optimal policy and the learner's actual reward.
Historically, practitioners have relied on algorithms like LinUCB or Thompson Sampling (LinTS). While effective, their regret scales linearly with the feature dimension $d$ ($O(d\sqrt{T})$). Conversely, theoretical algorithms like SupLinUCB achieve the optimal $\sqrt{d}$ scaling ($O(\sqrt{dT})$) but are often unusable in practice due to their "phased" learning approach, which discards valuable data to maintain statistical independence. HyRan addresses this by providing an adaptive, high-performance algorithm with optimal theoretical guarantees.
The HyRan Algorithm: Squeezing Information
The core innovation of HyRan lies in its estimator. Traditional LCB algorithms only update their internal models using the context and reward of the chosen arm. HyRan introduces a "Squeeze All" approach using a Doubly Robust (DR) estimator. This estimator incorporates the context vectors of every available arm at each time step, regardless of whether they were selected.
To maintain analytical tractability without resorting to inefficient phased learning, HyRan employs Explicit Randomization. A hybridization variable $h_t$ determines whether the algorithm updates using a standard ridge regression score or the more complex DR score. This randomization allows for a novel decomposition of cumulative regret into additive dimension-dependent terms, effectively reducing the regret factor from $d$ to $\sqrt{d}$.
Theoretical and Empirical Results
The authors establish a self-normalized bound for the HyRan estimator, proving a regret bound of $\tilde{O}(\sqrt{dT})$. They also provide a new lower bound of $\Omega(\sqrt{dT})$ for stochastic contexts, confirming HyRan's near-optimality.
Empirically, HyRan was tested against LinUCB, LinTS, and SupLinUCB in synthetic environments with varying dimensions ($d$) and arm counts ($N$). To simulate real-world challenges, the experiments included severe multicollinearity between arm contexts.
As shown in the results, HyRan consistently maintains lower cumulative regret than all competitors. Notably, as the feature dimension $d$ increases, the performance gap between HyRan and standard $O(d\sqrt{T})$ algorithms widens, validating the theoretical $\sqrt{d}$ advantage in practice.
Conclusion
HyRan represents a significant step forward in contextual bandit research, offering an algorithm that is both theoretically optimal and practically superior. By "squeezing" information from all available contexts and using randomization as a tool for better estimation, it overcomes the limitations of previous phased-learning models. Future work will focus on relaxing the stochastic context assumptions to handle adversarial environments and further optimizing the computational overhead associated with processing all arm contexts.
Summary updated