Optimal Regret for Single Index Bandits

We study the *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 $\tilde{\mathcal{O}}(T^{3/4})$ (under standard boundedness, nonzero first-order Stein signal ${\mu }^{\ast }$, and Lipschitz assumptions on the reward [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, Zooming Single Index Bandit with Upper Confidence Bound (“ZoomSIB-UCB“), that first estimates the projection direction via a normalized Stein estimator. With an adaptive exploration and discretization, it then runs UCB over the resulting one-dimensional bins. This approach achieves a regret of $\tilde{\mathcal{O}}(T^{2/3})$, and improves significantly upon prior work without knowing ${\mu }^{\ast }$ or a lower bound on its magnitude. We also prove a matching minimax lower bound of $\tilde{\Omega }(T^{2/3})$, showing that the dependence on $T$ is optimal up to logarithmic factors. Our upper and lower bounds together provide a sharp characterization of the regret in single-index bandits in terms of $T$. Empirical results further demonstrate the effectiveness and robustness of our approach.