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

Wonyoung Kim, Min-hwan Oh, Myunghee Cho Paik

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.

Figure 1: Comparison of parameter estimation between HyRan and LinTS. The HyRan estimator (blue) is centered on the true parameter (star), while LinTS (orange) exhibits bias due to multicollinearity.

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.

Figure 2: Cumulative regret across different dimensions (d) and number of arms (N). HyRan (black line) consistently achieves the lowest regret, with its advantage becoming more pronounced as the dimension d increases.

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

Abstract

We propose a linear contextual bandit algorithm with $O(\sqrt{dT\log T})$ regret bound, where $d$ is the dimension of contexts and $T$ isthe 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 contributions 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 \textit{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 Min-hwan Oh and Myunghee Cho Paik},
  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