Elicitation and Decision Geometry in Single-Index Bandits

Sakshi Arya; Cheng Soon Ong

stat.MLSep 28, 2026

Elicitation and Decision Geometry in Single-Index Bandits

Authors: Sakshi Arya, Cheng Soon Ong

Organizations: Case Western Reserve University, USA · CSIRO, Australia

Abstract

We study two-arm contextual bandits with arm-specific single indices and a shared unknown monotone link. Monotonicity makes the optimal action depend only on the contrast between the index directions, hence arm-specific reward functions need not be estimated. We introduce Natural Boundary Learning (NBL), a greedy procedure that uses a sequential Stein contrast to learn the optimal boundary directly, without estimating the reward functions or the common link. We characterize the local Riemannian dynamics of NBL through a decision stability coefficient balancing arm separation, link geometry, and the context distribution. We show that this stability is connected to the elicitation geometry of the underlying convex potential. Under local decision stability, NBL contracts toward the optimal boundary and achieves $O(\log n)$ expected regret. Numerical experiments illustrate the predicted stability regimes and compare NBL with a parametric greedy benchmark under link misspecification.

Figures & tables

Panel of Figure 1 — Figure 1: Tangent projection in NBL. The Stein signal decomposes as $W_{t}=(v^{\top}W_{t})v+P_{v}^{\perp}W_{t}$ . The orthogonal component $G_{t}=P_{v}^{\perp}W_{t}$ defines the tangent update direction at $v\in\mathbb{S}^{d-1}$ .

Panel of Figure 2 — Figure 2: Numerical illustration of decision stability and link misspecification. Top: two-transition links yielding stable, near-critical, and unstable dynamics, their curvature, the resulting decision stability coefficient $\lambda_{\star}$ , and stochastic NBL regret. Bottom: the elicitation-induced link family, its decision stability under weak separation, and comparisons of NBL with Greedy Logistic under link misspecification.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Local stability geometry in two dimensions. The tangent vector $v_{\perp}(\alpha)$ points in the direction of increasing $\alpha$ . For $\alpha_{+}>0$ , a restoring population field points opposite to $v_{\perp}(\alpha_{+})$ , toward decreasing $\alpha$ . For $\alpha_{-}<0$ , it points in the same direction as $v_{\perp}(\alpha_{-})$ , toward increasing $\alpha$ . In both cases the population field moves the candidate direction back toward $v^{\star}$ .

$\varphi(r)$	$w(r)=\varphi^{\prime\prime}(r)$	$\vartheta=\varphi^{\prime}(r)$	$g_{\varphi}(\vartheta)$
$\frac{1}{2}r^{2}$	$1$	$r$	$\vartheta$
$r\log r-r$	$\frac{1}{r}$	$\log r$	$\exp(\vartheta)$
$-\log r$	$\frac{1}{r^{2}}$	$-\frac{1}{r}$	$-\frac{1}{\vartheta}$
$r\log r+(1-r)\log(1-r)$	$\frac{1}{r(1-r)}$	$\log\!\left(\frac{r}{1-r}\right)$	$\displaystyle\frac{\exp(\vartheta)}{1+\exp(\vartheta)}$

Appendix

Table 1: Examples of convex potentials, Bregman weights, dual coordinates, and induced response maps.

Panel of Figure 4 — Figure 4: Elicitation geometry of the asymmetric weighted negative-entropy family. Panel (a) shows $\varphi_{\rho}$ , while panel (b) shows the dual map $z=\varphi_{\rho}^{\prime}(m)$ . The induced link $g_{\rho}=(\varphi_{\rho}^{\prime})^{-1}$ is shown in Figure 2 (e).

Figure 5: Components determining the sign of the decision stability coefficient at

\Delta_{\beta}=0.2

. For visual comparison, the figure shows the half-scaled restoring contribution

(\Delta_{\beta}/2)\mu^{\star}

and curvature contribution

\phi_{0}(0)(m_{2})_{+}(1-\Delta_{\beta}^{2}/4)

. Their equality corresponds to

\lambda_{\star}=0

Figure 6: Decision-stability phase diagram for the two-transition shared-link family. The shaded region corresponds to $\lambda_{\star}<0$ , while the solid curve marks the stability boundary $\lambda_{\star}=0$ . The dotted horizontal line indicates the reference separation $\Delta_{\beta}=0.2$ , and the three points correspond to the representative links used in the main numerical experiments.

Panel of Figure 7 — Figure 7: Effect of arm separation on the population weighting of a fixed unknown link. The link is locally unstable at $\Delta_{\beta}=0.2$ and is held fixed as $\Delta_{\beta}$ varies. The shaded regions correspond to $U\sim N(0,1-\Delta_{\beta}^{2}/4)$ for $\Delta_{\beta}=0.2$ , $1.0$ , and $1.8$ , and are rescaled by a common factor for visual comparison. In panel (b), the densities are reflected about zero only for visual reference.

Panel of Figure 8 — Figure 8: Signed angular error of NBL over 100 Monte Carlo replications. Panel (a) fixes $\Delta_{\beta}=0.2$ and varies the shared link across the stable, near-critical, and unstable population regimes. Panel (b) fixes the link with $\mu_{2}=1.244122$ , which is unstable at $\Delta_{\beta}=0.2$ , and varies the arm separation. Curves show Monte Carlo means and shaded regions show pointwise approximate 95% Monte Carlo confidence intervals for the mean trajectories.

Explore similar work

Optimal Regret for Single Index Bandits
May 10, 2026Devdan Dey, Sujoy Bhore, Avishek GhoshStochastic Multi-Armed Bandits Optimal Regret
Department of Computer Science and Engineering, Indian Institute of Technology Bombay.
Active Context Selection Improves Simple Regret in Contextual Bandits
May 19, 2026Mohammad Shahverdikondori, Jalal Etesami, Negar KiyavashAdaptive Sampling
College of Management of Technology, EPFL · Department of Computer Science, TU Munich
Trading off rewards and errors in multi-armed bandits
May 1, 2026Akram Erraqabi, Alessandro Lazaric, Michal Valko +2Stochastic Multi-Armed Bandits Regret
Inria SequeL · CMU · EnLearn

May 10, 2026, stat.MLJ/K move · Enter open · S save

Optimal Regret for Single Index Bandits

Devdan Dey, Sujoy Bhore, Avishek Ghosh

Department of Computer Science and Engineering, Indian Institute of Technology Bombay.

Stochastic Multi-Armed Bandits Optimal Regret Regret Projection

Open paper AskPDF arXiv

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Ω(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

Explore similar work

Optimal Regret for Single Index Bandits

Active Context Selection Improves Simple Regret in Contextual Bandits

Trading off rewards and errors in multi-armed bandits