Introduction
In the field of online decision-making, the Linear Contextual Bandit (LCB) framework is a cornerstone for applications ranging from personalized medicine to recommendation systems. In LCB, an agent observes a context, chooses an action (arm) from a set of candidates, and receives a reward based on a linear relationship between the context and an unknown parameter. The goal is to minimize cumulative regret—the difference between the rewards obtained by an optimal policy and those obtained by the agent.
Historically, a significant gap has existed between practical and theoretical algorithms. Adaptive algorithms like LinUCB and Thompson Sampling (LinTS) are efficient but suffer from a regret bound that scales linearly with the dimension $d$ (specifically $O(d\sqrt{T})$). Conversely, "phased" algorithms like SupLinUCB achieve the theoretically optimal $O(\sqrt{dT})$ scaling but are often impractical due to their data-inefficient exploration phases. This paper introduces HyRan (Hybridization by Randomization) Bandit, an algorithm that bridges this gap by being both fully adaptive and theoretically near-optimal.
The HyRan Estimator: Squeezing Data from Every Arm
The core innovation of HyRan is its novel estimator. Standard bandit algorithms typically update their world model using only the context and reward of the arm that was actually selected. HyRan, however, leverages a Doubly Robust (DR) approach to "squeeze" information from the contexts of all available arms, including those not pulled.
To maintain statistical validity without the rigid structure of phased algorithms, HyRan employs explicit randomization. In each round, the algorithm uses a hybridization variable $h_t$ to decide between a standard Ridge update and a complex DR update. This randomization allows the algorithm to mimic the independence properties required for tight theoretical bounds while remaining fully adaptive.
As shown in the figure above, the HyRan estimator provides a much tighter cluster around the true parameter compared to traditional methods like LinTS, particularly in settings with complex context distributions.
Theoretical Advancements
The authors establish a new self-normalized bound for the HyRan estimator. This mathematical tool is pivotal because it allows for an additive decomposition of cumulative regret. Instead of the dimension $d$ multiplying the $\sqrt{T}$ term, the new bound allows these factors to interact additively, effectively reducing the regret bound from $O(d\sqrt{T})$ to $O(\sqrt{dT} \log T)$.
Furthermore, the paper proves a new lower bound of $\Omega(\sqrt{dT})$ for this problem setting. This confirms that HyRan is near-optimal, matching the lower bound up to logarithmic factors.
Empirical Performance
The researchers evaluated HyRan through extensive numerical simulations, focusing on scenarios with high multicollinearity—a common challenge where features are highly correlated. They tested various configurations of arm counts ($N$) and dimensions ($d$).
The experimental results demonstrate that HyRan consistently outperforms established baselines like LinUCB, LinTS, and DRTS. Notably, while SupLinUCB is theoretically optimal, its performance in practice is poor due to its aggressive exploration and data-discarding nature. HyRan maintains the best of both worlds: the low regret of an optimal algorithm and the practical efficiency of an adaptive one.
Conclusion
HyRan represents a significant step forward in linear contextual bandits. By utilizing the contexts of all arms through a randomized hybrid estimator, it achieves a near-optimal regret bound of $O(\sqrt{dT} \log T)$. This "squeeze all" approach not only provides theoretical guarantees but also translates into superior empirical performance, especially as the dimensionality of the problem increases. Future work may involve relaxing the stochastic context assumptions to accommodate adversarial environments and optimizing the computational overhead for large-scale applications.
Summary updated