Optimal Regret for Single Index Bandits

arXiv:2605.09454v1 Announce Type: cross Abstract: We study the extit{single-index bandit} problem, where rewards depend on an unknown one-dimensional projection of high-dimensional contexts through an unknown reward function. This model extends linear and generalized linear bandits to a nonparametric setting, and is particularly relevant when the reward function is not known in advance. While optimal regret guarantees are known for monotone reward functions, the general non-monotone case remains poorly understood, with the best known bound being ilde{O}(T^{3/4}) (under standard boundedness and Lipschitz assumptions on the reward function [Kang et al., 2025]). We close this gap by establishing the optimal regret for general single-index bandits. We propose a simple two-phase algorithm, namely, Zoomed Single Index Bandit with Upper Confidence Bound (exttt{ZoomSIB-UCB}), that first estimates the projection direction via a normalized Stein estimator, and then reduces the problem to a one-dimensional bandit using discretization and finally use UCB. This approach achieves a regret of ilde{O}(T^{2/3}), and improves significantly upon prior work without any additional assumptions. We also prove a matching minimax lower bound of ilde{Omega}(T^{2/3}), showing that the upper bound is essentially tight. Our upper and lower bounds together provide a sharp characterization of the regret in single-index bandits. Moreover, the empirical results further demonstrate the effectiveness and robustness of our approach.

Source: arXiv cs.LG | 2026-05-12