Optimal and Dimension Free Regret For Multi-Index Bandits

We introduce online learning in the *multi-index bandit* setting, a semiparametric generalization of $d$-dimensional contextual bandits in which the expected reward depends on the context through multiple ($r$ satisfying $r\ll d$) unknown latent projections, composed with an unknown multivariate reward function. Moving from a single index to multiple latent directions captures richer dependencies, but it also introduces fundamental statistical challenges: the learner must simultaneously recover a latent subspace and learn an unknown multivariate reward function. In this work, we focus on monotone reward functions and develop algorithms with provably sublinear regret. We first consider the class of coordinate-wise monotone functions. We propose *Coordinate-wise Monotone Multi-Index Bandits* (`CM-MIB`), a variant of the successive elimination algorithm that suitably discretizes the underlying function class, and establish a regret upper bound of $\tilde{\mathcal{O}}\left(T^{\frac{r+1}{r+2}}\right)$. We further prove a minimax lower bound of $\tilde{\Omega }\left(T^{\frac{r+1}{r+2}}\right),$ showing that this rate is tight up to logarithmic factors. Notably, the regret becomes nearly linear as $r$ grows, which shows that coordinate-wise monotonicity alone is too weak a structure in high effective dimensions. To address this limitation, we impose a stronger condition on the reward function, namely *entire monotonicity*. Under this assumption, we propose and analyze *Entirely Monotone Multi-Index Bandits* (`EM-MIB`), which achieves a regret of $\tilde{\mathcal{O}}(T^{3/4})$, where the exponent of $T$ is independent of $r$. Our analysis employs chaining arguments based on bracketing entropy to show that the entirely monotone least squares estimator attains the near-optimal rate under random design. Moreover, by using an offline regression oracle along with inverse-gap-weighting scheme, we improve the regret to $\tilde{\mathcal{O}}(T^{2/3})$. We further establish a minimax lower bound of $\tilde{\Omega }(T^{2/3})$, showing that this result cannot be improved. To the best of our knowledge, this work provides the first regret guarantees for multi-index bandits and precisely characterize the trade-offs between structural assumptions and statistical efficiency.