Optimal Regret for Single Index Bandits
Authors: Devdan Dey, Sujoy Bhore, Avishek Ghosh
Summary
The paper studies single-index bandits, where rewards depend on a one-dimensional projection of high-dimensional context vectors through an unknown (possibly non-monotone) reward function. This generalizes linear bandits to settings where you don't know the reward function's form. Previous work achieved Õ(T^(3/4)) regret for non-monotone functions; this paper closes the gap by proving Õ(T^(2/3)) regret is achievable and optimal. Their algorithm first estimates the projection direction using a normalized Stein estimator, then reduces to a one-dimensional bandit problem via discretization and UCB. They also prove a matching lower bound, showing T^(2/3) is the right rate.
Main takeaways:
- Single-index bandits: rewards depend on an unknown one-dimensional projection of high-dimensional contexts via an unknown function
- Prior best regret for non-monotone functions was Õ(T^(3/4)); this paper achieves Õ(T^(2/3))
- Two-phase algorithm: estimate the projection direction, then discretize and use UCB in one dimension
- Prove a matching Ω̃(T^(2/3)) lower bound, establishing optimality
- No additional assumptions (like monotonicity) needed; empirical results confirm effectiveness
Relevance
Not related to my work on language model personas or behavioral installation—this is about optimal algorithms for contextual bandits with unknown reward functions.
Abstract
arXiv:2605.09454v1 Announce Type: new Abstract: We study the $\textit{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 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 ($\texttt{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 $\tilde{\mathcal{O}}(T^{2/3})$, and improves significantly upon prior work without any additional assumptions. We also prove a matching minimax lower bound of $\tilde{\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.