Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits

Wonyoung Kim, Myunghee Cho Paik, Min-hwan Oh

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.

HyRan's estimator (blue) is significantly more accurate than LinTS (orange) in recovering the true parameter (star).

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$).

Cumulative regret across different arm counts (N) and dimensions (d). HyRan (black) consistently achieves the lowest regret.

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

Abstract

We propose a linear contextual bandit algorithm for linear contextual bandits with $O(\sqrt{dT \log T})$ regret bound, where $d$ is the dimension of contexts and $T$ is the time horizon. Our proposed algorithm is equipped with a novel estimator in which exploration is embedded through explicit randomization. Depending on the randomization, our proposed estimator takes contribution either from contexts of all arms or from selected contexts. We establish a self-normalized bound for our estimator, which allows a novel decomposition of the cumulative regret into additive dimension-dependent terms instead of multiplicative terms. We also prove a novel lower bound of $\Omega(\sqrt{dT})$ under our problem setting. Hence, the regret of our proposed algorithm matches the lower bound up to logarithmic factors. The numerical experiments support the theoretical guarantees and show that our proposed method outperforms the existing linear bandit algorithms.
BibTeX
@inproceedings{kim2023squeeze,
  author = {Wonyoung Kim and Myunghee Cho Paik and Min-hwan Oh},
  title = {{Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=23yKg7N63Q},
}
Figure