GWidExplore: Computationally-Efficient Exploration in Contextual Linear Bandits

Achieving nearly optimal $\tilde{O}(d\sqrt{T})$ regret with efficient optimization over large action sets has remained an open problem in contextual linear bandits. Dani, Hayes, and Kakade (2008) gave an efficient algorithm, but with $\tilde{O}(d^{3/2}\sqrt{T})$ regret. The problem was posed by Agrawal and Goyal in 2014 and revisited by Kim and Tewari (2020). The oracle-efficient linear Thompson-sampling and spanner-based methods of have guarantees that incur the additional $\sqrt{d}$ factor. We close this gap for compact convex action sets. Under standard boundedness and sub-Gaussian noise assumptions, our algorithm achieves $\tilde{O}(d\sqrt{T})$ regret with high probability using polylogarithmically many linear optimizations over convex sets per round. The algorithm progressively removes actions that are suboptimal by adding linear constraints to the current action set. It measures the remaining uncertainty using the Gaussian width of a rescaled feasible set, where the rescaling reflects information from previously sampled actions. When the width is small, the algorithm shrinks the set while preserving an optimal action with high probability. When the width is large, it samples a random direction and chooses uniformly between the two feasible actions that are farthest apart in that direction.