aiqbench analysis
This research establishes the optimal regret bounds for single-index bandits by introducing a two-phase algorithm that effectively handles non-monotone reward functions in high-dimensional settings. By proving matching upper and lower bounds of $\tilde{\mathcal{O}}(T^{2/3})$, the study provides a sharp theoretical characterization that closes existing gaps left by prior work relying on monotonicity assumptions or weaker convergence rates. The proposed method leverages normalized Stein estimators to identify projection directions before reducing complexity, offering significant improvements for reinforcement learning applications involving unknown nonparametric reward structures.
Optimal Regret for Single Index Bandits
arXiv:2605.09454v3 Announce Type: replace-cross 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.
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.
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2605.09454 [stat.ML]
(or arXiv:2605.09454v3 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2605.09454 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 299 words
Related coverage
Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping
arXiv · Sep 22, 2026
Low-Rank Single-Index Bandits with Unknown Links: From Matrices to Tensors
arXiv · Sep 30, 2026
Elicitation and Decision Geometry in Single-Index Bandits
arXiv · Sep 30, 2026
Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits
arXiv · Aug 20, 2026