acceptodds
Under review as a conference paper at ICLR 2027

Optimal and Dimension Free Regret For Multi-Index Bandits

Abstract

We introduce online learning in the *multi-index bandit* setting, a semiparametric generalization of -dimensional contextual bandits in which the expected reward depends on the context through multiple ( satisfying ) 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 . We further prove a minimax lower bound of showing that this rate is tight up to logarithmic factors. Notably, the regret becomes nearly linear as 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 , where the exponent of is independent of . 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 . We further establish a minimax lower bound of , 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.

Primary area:
reinforcement learning
Keywords:
Contextual bandits, multi-index models, online learning, coordinate-wise monotonicity, entire monotonicity

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_8e1AOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary
  • This paper studies a KK-armed bandit problem using a multi-index model, where the expected reward is determined by the context only through an unknown linear map L∈Rr×dL\in\mathbb R^{r\times d} with r≪dr \ll d: specifically, it is defined as ga(LXt)g_a(LX_t) where Xt∈RdX_t\in\mathbb R^d is a context shared by all actions and ga:Rr→Rg_a:\mathbb R^r\to\mathbb R is an action-specific reward function (need not be parametric).

  • Under specific constraints, especially on the shape of the reward function gag_a for all a∈[K]a \in [K], namely coordinate-wise monotonicity and entire monotonicity, the paper proposes 3 algorithms, all of which achieve sublinear regret bounds for both known and unknown LL.

  • Under the coordinate-wise monotonicity, where increasing any single coordinate of LXtLX_t does not decrease gag_a, the corresponding algorithm CM-MIB achieves an expected regret bound of order O~((KT)(r+1)/(r+2))\tilde{\mathcal O}((KT)^{(r+1)/(r+2)}), and the authors provide a matching lower bound (in terms of TT) for this problem under the same shape of reward.

  • Under entire monotonicity, which is stronger than coordinate-wise monotonicity when r≥2r\ge 2, the corresponding algorithms EM-MIB and EM-MIB+ achieve regret bounds of order O~(KT3/4+KT5/8)\tilde{\mathcal O}(KT^{3/4} + \sqrt{K}T^{5/8}) and O~(KT2/3)\tilde{\mathcal O}(KT^{2/3}), respectively. The authors also provide a lower bound for this setting, matching that of EM-MIB+ (in terms of TT).

Critical strengths
  1. The paper studies a shared multi-index contextual-bandit model with arm-specific multivariate monotone reward functions and characterizes how different shape restrictions affect the regret rate.

  2. I found a technical argument interesting.

    • Specifically, EM-MIB+ plugs the least-squares estimator into FALCON+, which reduces the contextual bandit to offline regression by refitting the reward estimates at the start of each doubling epoch and sampling arms by inverse-gap weighting.
    • The paper first analyzes this reduction under Assumption 12 (Theorem C.27), which imposes a density bound on the arm-conditional design induced by the algorithm’s own inverse-gap weighting, and then removes it (Proposition C.30).
    • Because Assumption 12 concerns the arm-conditional designs induced by data-dependent action-selection probabilities, it does not immediately follow from the stated assumptions on the context distribution.
      • Removing this additional condition while preserving the horizon exponent is therefore a useful technical contribution.
  3. This paper separates the cases between the two shape constraints on reward function, and the authors also provide lower bounds that match the upper bounds of CM-MIB and EM-MIB+ in terms of TT, up to logarithmic factors.

Critical weaknesses
  1. There seems to be a missing reference, and the novelty of the random-design regression result needs clarification.

    • The paper states: "To our knowledge, this is the first random-design population prediction guarantee of this form for entirely monotone regression and its transfer to bandit data." (Line 119-121)
    • However, Bibaut & van der Laan (2019) establish a random-design convergence rate for least squares over a larger function class, under assumptions that hold in this paper's model when LL is known.
      • Bibaut & van der Laan (2019) consider least squares over càdlàg functions on [0,1]r[0,1]^r with sectional (Hardy-Krause) variation norm at most MM, where ∥f∥v:=∣f(0)∣+∑∅≠s⊆[r]∫∣fs(dxs)∣\Vert f\Vert_v:=|f(0)|+\sum_{\emptyset\neq s\subseteq[r]}\int|f_s(dx_s)| and fs(xs)=f(xs,0−s)f_s(x_s)=f(x_s,0_{-s}).
      • By Eq. (3), every f∈FVf\in\mathcal F_V is a constant β\beta plus the nonnegative multiple f(1)−f(0)f(1)-f(0) of a distribution function (Line 314-317). Since a constant has norm ∣β∣|\beta| and a distribution function has norm one, ∥f∥v≤∣β∣+(f(1)−f(0))≤Gmax⁡+Vmax⁡=B0\Vert f\Vert_v\le|\beta|+(f(1)-f(0))\le G_{\max}+V_{\max}=B_0.
      • Hence FV\mathcal F_V is contained in the class considered by Bibaut & van der Laan (2019) with M=B0M=B_0.
      • Bibaut & van der Laan (2019) also assume a random design with a bounded density and sub-exponential noise independent of the covariates, which corresponds to Assumptions 3 and 4 in this work.
  2. Assumptions seem to be too strong.

    • The upper bounds for unknown LL rest on Assumption 7, but the authors do not show that any concrete estimator satisfies the assumption.
    • Assumption 8 requires the reward functions to be monotone in a specific canonical chart [Ir∣W][I_r \mid W], determined by a known set of rr anchor coordinates, rather than in some basis of the index space.
      • For example, let u=Mxu=Mx with M=(100−111)M=\begin{pmatrix}1&0&0\\\\-1&1&1\end{pmatrix} and g(u)=1/2+(1/π)arctan⁡(u2)g(u)=1/2+(1/\pi)\arctan(u_2). Then gg is coordinate-wise monotone in uu, since it is constant in u1u_1 and increasing in u2u_2.
      • Since the canonical chart does not depend on the choice of row basis, it can be computed directly from MM.
      • With VM=(10−11)V_M=\begin{pmatrix}1&0\\\\-1&1\end{pmatrix} and VM−1=(1011)V_M^{-1}=\begin{pmatrix}1&0\\\\1&1\end{pmatrix}, we obtain L=VM−1M=(100011)L=V_M^{-1}M=\begin{pmatrix}1&0&0\\\\0&1&1\end{pmatrix}, i.e., z=(x1,x2+x3)z=(x_1,x_2+x_3).
      • Since u=VMzu=V_Mz, the same reward in canonical coordinates is g(VMz)=1/2+(1/π)arctan⁡(z2−z1)g(V_Mz)=1/2+(1/\pi)\arctan(z_2-z_1), which is not coordinate-wise monotone. The same holds for every admissible choice of anchor coordinates.
  • Hence the learner must know the monotone orientation in advance, which the authors acknowledge (Line 99-100).
  1. The experiments use weak baselines.
    • In Fig. 3 (page 47), the comparison baselines seem to be limited to the unstructured Global-UCB and Uniform, whose regret grows essentially linearly. In my view, these baselines are weak, and a natural comparison with methods such as the single-index bandit method of Ma & Cai (2025) seems to be missing.

(minor suggestions)

  • Eq. (2) (Line 162-163): "the coordinates outside SS are fixed" leaves z(u)jz(u)_j for j∉Sj\notin S implicit. Please state explicitly that aj=bja_j=b_j for j∉Sj\notin S, as in Definition C.2.
  • Lemma C.14 (Line 1516): "The constant CC depends only on BB, σs\sigma s, and α\alpha" should read "BB, ss, and α\alpha". The quantity s2s^2 is the variance proxy defined in the lemma (Line 1499), and the proof itself uses "BB, ss, and α\alpha" (Line 1519).

References

  • Bibaut & van der Laan (2019), Fast rates for empirical risk minimization over càdlàg functions with bounded sectional variation norm.
  • Ma & Cai (2025), Nonparametric bandits with single-index rewards: Optimality and adaptivity.
Questions for authors
  1. How do Theorem 4.1 and Lemma C.14 differ from the results of Bibaut & van der Laan (2019), and what do they add beyond them?

  2. Which concrete subspace estimator provably satisfies Assumption 7 under the uniform-exploration distribution?

  3. Is explicit identification of the row space of LL needed for the regret guarantees, or is it mainly a computational device?

    • From my perspective, the regret analysis of EM-MIB+ seems to need only a regression oracle with a small prediction error under the joint context-action distribution (Line 405-408), not LL itself.
    • For example, one could fit the rewards directly by least squares over the composite class \left\\{(x,a)\mapsto f_a(S_M(Mx)): f_1,\ldots,f_K\in\mathcal F_V,\\ M\in\mathcal M\right\\}, where M\mathcal M is a bounded set of full-row-rank r×dr\times d matrices, and SMS_M is a coordinate-wise increasing affine rescaling of the bounding box of the support of MXMX to [0,1]r[0,1]^r, assuming the box is nondegenerate. In other words, the learner searches over the projection MM and the functions faf_a at the same time, instead of estimating LL first.
    • If least squares over this class attains a high-probability joint prediction error comparable to that of Theorem 4.1 under the action-selection distributions required by FALCON+, neither Assumptions 5-7 nor the known monotone orientation would be needed, since the class contains the true rewards as long as they are entirely monotone in some common basis M∈MM\in\mathcal M of the index space and satisfy the variation bound.
    • Could the authors comment on whether such an approach works, and if not, what prevents it?
  4. If possible, could the authors add context-aware baselines, including Ma and Cai (2025) on compatible single-index instances?

4 comments
AuthorsOpenReview ↗

Part 1/2: Questions 1-3

We thank the reviewer for the careful assessment and the specific suggestions.

Q1 / Weakness 1. Relation to Bibaut and van der Laan (2019).

We agree that their results give the same offline polynomial estimation rate under their specific assumptions. We have cited their work and acknowledged this overlap in lines 121 to 130 and Remark 4.3, lines 365 to 377 in blue.

Our priority claim concerns regret guarantees for multi-index bandits under monotonicity. Achieving this bandit result requires overcoming two major limitations in their offline setting.

  • First, their theorems assume perfectly known contexts, exact optimization, and noise that is strictly independent of the contexts. In our problem, the true projection is unknown and must be estimated. Evaluating rewards at estimated coordinates introduces a residual error that depends on the context. Lemma C.14 solves this. It establishes a finite-sample prediction bound that accounts for estimated coordinates, context-dependent residuals, and approximate optimization.

  • Second, their work relies on a stable and fixed offline data distribution. Our EM-MIB+ algorithm adaptively skews the data distribution based on the arm selection policy. Proposition C.30 transfers the estimation guarantee to these skewed distributions. It achieves this without requiring an unrealistic bound on the arm conditional density.

We provide a detailed mathematical comparison in our response to Reviewer pVEY (Part 2, Question 2).

Q2. Which concrete subspace estimator satisfies Assumption 7?

We use an unregularized version of the slicing-free inverse regression estimator of Mai, Shao, Wang and Zhang (2025) [Slicing-Free Inverse Regression in High-Dimensional Sufficient Dimension Reduction], applied to XX with response Z=(A,arctan⁡Y)Z=(A,\arctan Y). This bounds the response while preserving all information in (A,Y)(A,Y).

The method constructs a matrix MM capturing the directions in which E[X∣A,Y]\mathbb E[X\mid A,Y] varies, corrects for the covariance of XX, and estimates the rr projection directions. Assumptions 5 and 6 ensure these identify the subspace of LL.

Their stated theorem does not directly provide the expected squared error required by Assumption 7. A short additional argument bridges this gap. Because both XX and ZZ are bounded, we obtain an expected squared error of O(1/n)O(1/n) for both the sample matrix and the sample covariance. This holds for the sample matrix because terms involving disjoint observations are statistically independent.

The invertible population covariance and positive population eigenvalue gap then allow eigenvector perturbation bounds to give E[∥P^−PL∥op2]≤C(P)n\mathbb E\left[\Vert{}\widehat P-P_L\Vert{}_{\mathrm{op}}^2\right]\le\frac{C(P)}{n}, where P^\widehat P and PLP_L project onto the estimated and true subspaces. The poorly conditioned sample covariance event contributes to this same order, since its probability is O(1/n)O(1/n) and the projector loss is bounded.

Taking C2=C(P)λr/(dr)C_2=C(P)\lambda_r/(dr) verifies Assumption 7 exactly as stated. Its constant may depend on the exploration distribution, including covariance conditioning and the population eigenvalue gap. Thus our upper bounds can use this concrete estimator without separately assuming that a suitable oracle exists. The construction and proof are now in Proposition A.1, lines 740 to 778 in blue.

Q3. Can the projection and reward functions be fitted jointly?

The proposed joint fit is a plausible alternative, but it requires two major difficulties that our two-stage procedure intentionally avoids:

  • Prediction error after choosing the projection. Joint estimation uses the same rewards to choose both the projection matrix MM and the monotone arm functions. Changing MM can change the ordering of the projected contexts, allowing a monotone function to spuriously fit noise patterns in the rewards that a fixed projection would rule out. Our procedure prevents this by freezing L^\widehat{L} on an independent block before the reward fit, locking the context ordering. Bounding the prediction error over the massive composite class of all projections and monotone functions is non-trivial, and it is not immediate to us whether it achieves the same O~(n−2/3)\widetilde{O}(n^{-2/3}) squared prediction rate.

  • Loss of Convexity. Our current optimization procedure in Appendix D relies on fixed projected contexts to reduce the fit to a finite convex program. Jointly optimizing over MM continuously changes the contexts and their relative ordering. This destroys the convexity of the formulation and invalidates our specific computational guarantee, requiring a completely different algorithmic approach.

Establishing such a bound requires additional statistical analysis and a fundamentally different optimization procedure from ours. Developing and verifying this alternative is therefore beyond the scope of our paper.

AuthorsOpenReview ↗

Part 2/2: Assumption 8, baselines and minor points

Weakness 2. Is Assumption 8 too strong?

We agree that Assumption 8 restricts the class of functions our algorithm can handle. However, studying multi-index models under this structural assumption is an established approach, and the condition is neither too strong nor impractical.

The identity-block normalization L=[Ir∣W]L=[I_r\mid W] is a standard technique in sufficient dimension reduction literature (e.g., Ma and Zhu, 2013, [Efficient Estimation in Sufficient Dimension Reduction]). Our additional requirement is that the reward functions are monotone in these particular coordinates.

In practice, this represents scenarios where we know certain "anchor" features drive the outcome monotonically, but we do not know how the other background features combine with them.. The following examples explain how such anchor information can arise.

  • Resource allocation. Suppose x1x_1 and x2x_2 measure dedicated CPU and memory capacities, and ss measures an additional resource contributing unknown amounts of both. Effective capacities are z1=x1+w1sz_1=x_1+w_1s and z2=x2+w2sz_2=x_2+w_2s. The dedicated capacities are known anchors from their physical interpretation, while w1,w2w_1,w_2 must be learned. For a job with random resource requirements, the probability of meeting both requirements is their joint distribution function evaluated at (z1,z2)(z_1,z_2), which is EM. This example appears in Appendix B.1, lines 851-855 (in blue).

  • Paired event-time regression. A statistical example follows from Komárek and Lesaffre (2006) [Bayesian Semiparametric Accelerated Failure Time Model for Paired Doubly-Interval-Censored Data]. Let T1,T2T_1,T_2 be two event times for the same subject and qq the observed covariates. Under the model log⁡Tj=bj⊤q+εj\log T_j=b_j^\top q+\varepsilon_j, the probability that both events occur by deadlines t1,t2t_1,t_2 is $ F(\log t_1-b_1^\top q,\ \log t_2-b_2^\top q),$ where FF is the joint error distribution function. Increasing log⁡t1\log t_1 changes only the first threshold; increasing log⁡t2\log t_2 changes only the second. Thus, for X=(log⁡t1,log⁡t2,q⊤)⊤X=(\log t_1,\log t_2,q^\top)^\top, the two log-deadlines are known anchors and L=[I2∣W]L=[I_2\mid W]. The effects b1,b2b_1,b_2 remain unknown. The function FF is EM because its rectangular increments are probabilities. This example is added in Section 2, lines 179-187 (in blue).

In our algorithm, the anchors allow us to convert an estimated subspace into coordinates in which the reward functions are monotonic. An arbitrary basis returned by a subspace estimator can change the coordinate-wise order, so estimating the subspace alone is insufficient for this procedure.

Our main separation between CM and EM already holds when the true LL is supplied. The minimax horizon exponents are (r+1)/(r+2)(r+1)/(r+2) and 2/32/3, respectively. Thus, the separation persists even after the difficulty of estimating LL is removed. Whether the same unknown-projection upper bounds can be achieved without known anchors remains open under our present scope.

Q4 / Weakness 3. Context-aware baselines.

We have added our scalar implementation of Ma and Cai (2025) [Nonparametric Bandits with Single-Index Rewards: Optimality and Adaptivity] on a compatible r=d=1r=d=1, K=3K=3 instance. The scalar context uu is uniform on [0,1][0,1], and the three arm mean-reward functions are

g_2(u)=\frac{13}{60}+0.35u,\qquad g_3(u)=0.30+0.10u.$$ All three are increasing and therefore entirely monotone. They are unknown to the learners. All methods are evaluated on these same reward functions, with independent Gaussian reward noise of standard deviation $0.05$. The optimal arm changes with the context at $u=1/3$ and $u=2/3$. Figure 4 compares all four methods on the same contexts and reward-noise streams. Mean cumulative regret over ten runs is: | $T$ | `CM-MIB` | Ma-Cai | `EM-MIB` | `EM-MIB+` | |---:|---:|---:|---:|---:| | 5,000 | 76.56 | 70.83 | **15.31** | 29.18 | | 50,000 | 297.08 | 279.18 | 71.56 | **58.73** | | 200,000 | 494.72 | 616.45 | 199.95 | **113.16** | Both EM methods have lower mean regret than Ma-Cai at all three horizons. `EM-MIB` has the lowest mean regret at the shortest horizon, and `EM-MIB+` at the two larger horizons. The comparison is described in lines 2630-2646 and 2675-2680 (in blue). **Minor points.** Equation (2) now explicitly states $a_j=b_j$ and $z(u)_j=a_j=b_j$ for $j\notin S$ (lines 169-170, in blue). Lemma C.14 now correctly states that $C$ depends only on $B$, $s$ and $\alpha$ (lines 1624-1625).
Reviewer_8e1AOpenReview ↗

Response to rebuttal

I appreciate the reviewers for detailed responses and revision, and they have addressed most of my concerns. I raised my rating to 3.

AuthorsOpenReview ↗

A Warm Thank You!

We value your constructive feedback, thoughtful engagement, and positive reassessment of our work. Thank you for your support.

Reviewer_vsKZOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies multi-index bandits, where the expected reward is an unknown function of several unknown linear projections of the context. The authors consider two monotonicity assumptions: coordinate-wise monotonicity and entire monotonicity. They propose algorithms for both settings and establish regret bounds that match the lower bounds in the exponent of the horizon TT. In particular, under entire monotonicity, the regret exponent is independent of the effective dimension. The authors also evaluate the proposed methods through synthetic and semi-synthetic experiments.

Critical strengths

Although I am not familiar with semiparametric bandits, I found the paper easy to follow. The contributions and the challenges of the problem are clearly explained, particularly why the two monotonicity assumptions lead to different regret rates.

The proposed algorithms achieve regret bounds that match the lower bounds in the exponent of the horizon TT under both monotonicity settings. I believe that these results provide a clear understanding of how the strength of the monotonicity assumption affects the difficulty of the problem. In particular, I find it surprising that under entire monotonicity, the regret exponent is independent of the effective dimension rr.

Critical weaknesses

Some implementation details of the algorithms could be explained more clearly. For example, although the paper describes estimating the projected support and rescaling it to [0,1]r[0,1]^r, I found it difficult to understand the precise construction of the rescaling map S^\hat S from the pseudocode alone. An explicit formula would make the procedure easier to follow.

Additionally, the algorithms rely on grid partitioning or repeated fitting of entirely monotone functions, with the simpler EM-MIB using an explore-then-commit strategy. These choices make the theoretical analysis clear, but I am less certain about their scalability in practical problems. A discussion of the computational cost and experiments with larger effective dimensions would help clarify their practical applicability.

Questions for authors
  1. Could the authors explicitly describe how the rescaling map S^\hat S is constructed from the exploration data?
  2. In Algorithm 1, could the authors explain how selecting the least-sampled active arm within each cell provides sufficient exploration, and how the resulting cell-wise guarantees lead to sublinear regret overall?
  3. How do the proposed methods scale as the effective dimension and the number of observations increase? What would be the main computational bottlenecks in practical applications?
1 comment

We thank the reviewer for the positive assessment and the questions about implementation and scalability. The additions described below are marked in blue in the revised manuscript.

Q1. Explicit construction of the rescaling map.

We have added the explicit construction in Section 3.1, lines 239-241. After estimating and freezing L^\widehat L on the first exploration block, we use the independent box-estimation block IboxI_{\rm box} to set

u_j=\max_{i\in I_{\rm box}}(\widehat L X_i)_j.$$ The estimated box is $\widehat{\mathcal B}=\prod_{j=1}^r[\ell_j,u_j]$, and its rescaling is $\widehat S(z)_j=(z_j-\ell_j)/(u_j-\ell_j)$. For a later context, algorithms clip each projected coordinate to this box before rescaling, as stated in lines 241-245. If any side length is zero, it plays a fixed fallback arm. This affine transformation is strictly increasing in each coordinate, i.e., it preserves both Coordinate-wise and Entire Monotonicity within the estimated box. > **Q2. Why the least-sampled rule gives sufficient exploration and overall sublinear regret.** - **Sufficient exploration within cells.** By prioritizing the least-sampled active arm, the algorithm forces balanced exploration among all surviving arms in a cell, preventing starvation. Because this selection completely ignores the context's exact location within the cell, it avoids adaptive selection bias. The observations therefore yield an unbiased estimate of the cell-average reward, allowing Lemma B.3 to establish a standard statistical learning cost of $\widetilde O(\sqrt{Kn})$ for a cell visited $n$ times. - **Overall sublinear regret.** Summing this statistical error across all $m^r$ cells yields an aggregate learning cost of $\widetilde O(\sqrt{KTm^r})$. If the grid is too fine (i.e., large $m$), the statistical error explodes. If the grid is too coarse (small $m$), the approximation error dominates. Coordinate-wise monotonicity solves this tension: Lemma B.2 guarantees that the sum of reward variations across all cells is strictly bounded, yielding a global approximation error of $O(KT/m)$ under bounded design density. Setting the grid resolution $m \asymp (KT)^{1/(r+2)}$ perfectly balances these two competing errors (Equation 13, lines 1005–1012), securing the overall sublinear regret bound. (Theorem B.10 handles the additional costs for estimated coordinates). We have added a concise explanation of this exploration mechanism and grid-size trade-off to Section 3.1, lines 251–253. > **Q3. Computational cost and larger effective dimensions.** We have added the main computational bottlenecks in Section 4.1 (lines 398-401) and the runtime comparison in Appendix E.8 (lines 3058-3070) and Table 7 (lines 3079-3086). For `CM-MIB`, the primary bottleneck is memory. The algorithm must store active arm counts and empirical means for every visited cell in the grid. For the entirely monotone algorithms `EM-MIB` and `EM-MIB+`, the main bottleneck is the regression optimization step. While the Frank-Wolfe solver only needs $O(n^{2/3})$ iterations to reach the required statistical tolerance, the number of basis functions it must search over scales exponentially with the effective dimension $r$ up to $(n+1)^r-1$ atoms. `EM-MIB+` is substantially more computationally expensive than `EM-MIB` because it repeatedly refits these functions at the start of every doubling epoch, whereas `EM-MIB` fits them only once. To illustrate this scaling in practice, Table 7 reports the mean runtime in seconds over three runs with $K=10$ arms, using identical context and noise streams across all methods. | $r$ | $T$ | `CM-MIB` | `EM-MIB` | `EM-MIB+` | |---:|---:|---:|---:|---:| | 3 | 4,096 | 0.0521 | 0.0093 | 0.0380 | | 3 | 16,384 | 0.2086 | 0.0450 | 0.1210 | | 5 | 4,096 | 0.0525 | 0.0496 | 0.3388 | | 5 | 16,384 | 0.2078 | 0.1438 | 1.9811 | These measurements confirm that repeated reward fitting is the major bottleneck. At $r=5$ and $T=16{,}384$, `EM-MIB+` spends 1.9161 of its total 1.9811 seconds purely on fitting rewards. To make this empirical evaluation computationally feasible at these dimensions, the timed implementation uses a practical quantile grid with the standard tolerance $\eta_n=n^{-2/3}$ rather than the full theoretical sample dictionary, as explicitly stated in lines 3061-3065.
Reviewer_pVEYOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies contextual bandits under a multi-index reward model, in which the expected reward depends on a high-dimensional context through a shared low-dimensional projection and an unknown arm-specific multivariate function. The authors focus on two nested function classes: coordinate-wise monotone (CM) and entirely monotone (EM) reward functions.

For the CM class, the paper proposes CM-MIB, which combines discretization of the projected context space with successive elimination, and establishes a regret upper bound of O~((KT)(r+1)/(r+2))\widetilde O((KT)^{(r+1)/(r+2)}), together with a matching minimax lower bound in the horizon exponent. For the EM class, the authors establish an O~(n−2/3)\widetilde O(n^{-2/3}) squared prediction error bound for entirely monotone least-squares regression under random design. Using this regression result, they develop EM-MIB, an explore-then-commit algorithm achieving O~(KT3/4)\widetilde O(KT^{3/4}) regret, and EM-MIB+, an epoch-based inverse-gap-weighting algorithm achieving O~(KT2/3)\widetilde O(KT^{2/3}) regret. A corresponding lower bound establishes the minimax optimality of the latter horizon exponent.

The paper also addresses unknown latent projections under explicit subspace-estimation and coordinate-identification assumptions. The theoretical results are complemented by synthetic and semi-synthetic experiments examining dimension dependence, structural assumptions, and finite-horizon performance.

The main contribution lies in theoretical characterization of how different multivariate monotonicity assumptions affect the statistical complexity and achievable regret rates in multi-index contextual bandits.

Critical strengths
  1. The paper investigates a well-motivated generalization of single-index contextual bandits to settings with multiple latent directions and unknown multivariate reward functions. A significant contribution is the theoretical distinction between coordinate-wise monotonicity and entire monotonicity. The authors establish matching upper and lower bounds in the horizon exponent for both classes, showing that coordinate-wise monotonicity leads to an intrinsic dependence on the effective dimension, whereas entire monotonicity allows a dimension-independent polynomial regret exponent. The lower-bound constructions remain valid even when the latent projection is known, which convincingly separates the statistical difficulty of learning the reward functions from that of estimating the latent representation. These results provide useful insights into how structural assumptions determine the statistical complexity of online decision-making.

  2. The analysis of entirely monotone regression under random design provides a connection between nonparametric regression and online learning. By exploiting the representation of entirely monotone functions through multivariate distribution functions and associated bracketing entropy bounds, the authors obtain an O~(n−2/3)\widetilde O(n^{-2/3}) squared prediction error guarantee. They then incorporate this statistical result into contextual bandit algorithms, culminating in the O~(KT2/3)\widetilde O(KT^{2/3}) regret guarantee of EM-MIB+. The corresponding minimax lower bound establishes optimality in the horizon exponent under the stated assumptions. The paper also carefully distinguishes known-chart and unknown-chart settings and explicitly acknowledges the remaining gap in the dependence on the number of arms. Overall, the results constitute a coherent theoretical contribution connecting structured function estimation, representation learning, and contextual bandit regret.

Critical weaknesses

The empirical validation of the optimal regret scaling could be more convincing. The experiment in Appendix E.4, which is intended to illustrate the improved horizon scaling of EM-MIB+, uses a K=10K=10, r=3r=3 instance where Arm 1 is uniformly optimal with a minimum reward gap of 0.20. On this instance, identifying the optimal action does not fundamentally require learning a context-dependent policy, since a standard stochastic multi-armed bandit algorithm can achieve logarithmic gap-dependent regret.

Moreover, EM-MIB and EM-MIB+ use initial exploration budgets scaling as T3/4T^{3/4} and T2/3T^{2/3}, respectively. Since uniform exploration necessarily incurs positive expected regret on this instance, these exploration stages alone contribute regret of the corresponding orders. Consequently, the observed empirical exponents of approximately 0.743 and 0.666 may largely reflect the prescribed exploration schedules rather than the intrinsic learning difficulty characterized by the minimax bounds.

This does not contradict the theoretical regret guarantees, but an experiment where the optimal arm genuinely varies with the context, together with a decomposition of initialization and subsequent learning regret, would provide more convincing empirical support for the theoretical improvement. Stronger contextual bandit baselines would also help isolate the benefit of exploiting the proposed structural assumptions.

Questions for authors
  1. In the K=10K=10, r=3r=3 experiment, Arm 1 is uniformly optimal with a minimum gap of 0.20. Since the initial exploration budgets of EM-MIB and EM-MIB+ already scale as T3/4T^{3/4} and T2/3T^{2/3}, respectively, could the authors clarify to what extent the reported empirical exponents reflect these exploration schedules rather than the difficulty of learning the context-dependent reward functions? Would it be possible to report initialization and post-initialization regret separately, and to evaluate the algorithms on an entirely monotone instance where the optimal arm varies with the context?

  2. The paper presents the random-design entirely monotone regression rate as an important theoretical contribution. However, Bibaut and van der Laan (2019), \emph{Fast Rates for Empirical Risk Minimization over Càdlàg Functions with Bounded Sectional Variation Norm}, have established closely related random-design ERM rates for the more general class of càdlàg functions with bounded sectional variation norm. In particular, the variation-constrained entirely monotone class considered here is contained in a bounded sectional-variation class. Under bounded responses and exact empirical risk minimization, the O~P(n−1/3)\widetilde O_P(n^{-1/3}) population L2L_2 rate, corresponding to a O~P(n−2/3)\widetilde O_P(n^{-2/3}) squared-error rate, appears to follow from their Theorem 1 by taking the EM class as the estimation sieve. The current paper provides additional guarantees involving conditional sub-Gaussian noise, approximate minimization, expectation bounds, and robustness to an estimated chart, which are not direct consequences of the earlier theorem statements. Could the authors clarify this distinction and explain the independent technical contributions of Theorem 4.1 and Lemma C.14 relative to the existing bounded-variation regression literature?

2 comments
AuthorsOpenReview ↗

Part 1/2: Experiments (Question 1)

We thank the reviewer for the positive assessment and the suggestions. We have added the requested regret decomposition and an experiment where the optimal arm changes with the context.

Original experiment: initialization and subsequent regret.

We agree that, when Arm 1 is uniformly optimal, the observed slopes do not establish the difficulty of learning a context-dependent policy. Table 3 (in manuscript) now separates initialization and subsequent regret at every original horizon (lines 2863-2878, in blue). The three horizons used for the reported tail slopes give:

T=262,144T=262{,}144

MethodInitial roundsInitial regretSubsequent regretTotal regret
EM-MIB14,4824826.4040.884867.29
EM-MIB+20.523517.633518.15

T=524,288T=524{,}288

MethodInitial roundsInitial regretSubsequent regretTotal regret
EM-MIB24,3558114.992.428117.41
EM-MIB+20.525582.785583.30

T=1,048,576T=1{,}048{,}576

MethodInitial roundsInitial regretSubsequent regretTotal regret
EM-MIB40,96013642.770.0413642.81
EM-MIB+20.528861.818862.33

Entries are means over 20 runs. EM-MIB's regret arises almost entirely during the exploration phase, as expected. Once its reward estimates identify the uniformly optimal arm, it incurs almost no subsequent regret.

In contrast, the plotted EM-MIB+ implementation initializes with only two uniform rounds rather than a full T2/3T^{2/3} exploration phase. . It then continues randomized arm selection and updates its reward estimates between epochs. Its subsequent regret includes both continued exploration and prediction errors. We have clarified this distinction and the interpretation of the slopes in Appendix E.4, lines 2802-2807 (in blue). The slopes describe performance on this fixed instance; the minimax exponent is established by the theoretical bounds.

New experiment: the optimal arm changes with the context.

We retain K=10K=10 and r=3r=3. We use uniform contexts u∈[0,1]3u\in[0,1]^3. The entirely monotone rewards are: ga(u)=0.45+0.43∑j=13(2va,jh(uj)−va,j2),h(s)=s+s22.g_a(u)=0.45+\frac{0.4}{3}\sum_{j=1}^3\bigl(2v_{a,j}h(u_j)-v_{a,j}^2\bigr),\qquad h(s)=\frac{s+s^2}{2}. Ten fixed, distinct vectors va∈(0,1)3v_a\in(0,1)^3 define the arms. Each reward is an increasing sum of one-dimensional functions. This ensures it is entirely monotone (EM). The optimal arm is the one whose vector vav_a is closest to (h(u1),h(u2),h(u3))(h(u_1),h(u_2),h(u_3)). As a result, every arm is optimal in a specific context region. We specify the exact numerical coefficients in lines 2843-2856.

Both EM methods use the same regression solver. The solver uses a stopping tolerance of 0.01n−2/30.01n^{-2/3} for nn arm observations. Both methods face identical context and noise streams. Each learner observes only the reward of its selected arm. We describe this in lines 2857-2861 (in blue).

Figure 10 and Table 4 report the new results. Entries below are mean regret ±\pm one standard error:

TTEM-MIBEM-MIB+Best fixed arm
4,09686.50±2.1686.50\pm2.16126.49±1.13126.49\pm1.13112.00±0.26112.00\pm0.26
16,384237.56±5.99237.56\pm5.99361.05±2.96361.05\pm2.96448.36±0.58448.36\pm0.58
65,536602.55±11.29602.55\pm11.291025.18±3.621025.18\pm3.621794.91±0.881794.91\pm0.88

The best fixed arm baseline selects the single arm with the highest total mean reward over the same contexts. Both EM methods beat this baseline at the two largest horizons. At T=65,536T=65{,}536, EM-MIB and EM-MIB+ have mean regrets of 602.55602.55 and 1025.181025.18, compared with 1794.911794.91 for always choosing the best fixed arm. These correspond to reductions of 66.466.4\\% and 42.942.9\\%, respectively. This proves that both methods successfully learn to use the context. In this specific instance, EM-MIB achieves lower regret than EM-MIB+.

AuthorsOpenReview ↗

Part 2/2: Question 2

Thank you for bringing Bibaut and van der Laan (2019) to our attention. We were unaware of this work when preparing the submission. We agree that, for bounded responses and exact least squares, their Theorem 1 applies to our entirely monotone class and gives the same O~P(n−2/3)\widetilde O_P(n^{-2/3}) squared prediction rate. Their Theorem 2 also treats independent sub-exponential errors over the full sectional-variation ball. We have cited these results and acknowledged the offline-rate overlap in the contribution statement, lines 121-130, and Remark 4.3, lines 365-377 (in blue). We narrow our priority claim to the first regret guarantees for multi-index bandits and the transfer of entirely monotone regression to adaptive bandit data.

However, transferring their offline regression rate to our adaptive bandit setting requires overcoming two structural challenges not covered by their results:

1. Estimated projection and approximate optimization (Lemma C.14.)

When LL is unknown, we fit rewards using U=S^(L^X)U=\widehat S(\widehat L X). For a fixed arm aa, the function we seek to predict is

=\mathbb E[g_a(LX)\mid U=u,A=a], {\text{which introduces three specific issues:}}$$ - (i) Although $g_a$ is entirely monotone (EM) in the true coordinates, $m$ may violate EM in the estimated coordinates. - (ii) The residual $Y-m(U)$ can depend on $U$, so the independent-error assumption of their Theorem 2 need not hold. - (iii) We need finite-sample bounds that allow an approximate least-squares fit. *Lemma C.14 handles all three issues simultaneously.* Section C.2 (lines 1795-1800) constructs an EM surrogate function $f_0(u)=g_a(\widehat S^{-1}u)$ that uniformly approximates $m$ within the projection error $\beta = L_g C_X \epsilon_W$, satisfying $\Vert{}m - f_0\Vert{}_\infty \le \beta$. Here $\epsilon_W$ measures the projection estimation error. Lemma C.14 then shows that any $\eta_n$-approximate least-squares estimator $\widehat{f} \in \mathcal{F}_V$ satisfies, with high probability and in expectation, $$\\|\widehat f-m\\|_{L_2}^2 \le 2\\|\widehat f-f_0\\|_{L_2}^2+2\beta^2 \lesssim \underbrace{\widetilde O(n^{-2/3})}_{\text{finite-sample error}} +\underbrace{\beta^2}_{\text{projection error}} +\underbrace{\eta_n}_{\text{optimization error}}.$$ The norm uses the input distribution conditional on arm $a$. > **2. Arm selection changes the regression design (Proposition C.30)** Bibaut and van der Laan operate under a stable, fixed offline data distribution. In contrast, `EM-MIB+` uses adaptive inverse-gap weighting, meaning the context distribution collected for any specific arm is highly skewed by the sampling policy. If an arm is pulled rarely with probability $q_a$, its context density spikes by $1/q_a$, which breaks standard offline regression bounds. *Proposition C.30 proves this density spike does not ruin the regression.* It carefully tracks both the sample size and the density changes. For well-sampled arms, the statistical error scales as $q_a^{-1/3}(nq_a)^{-2/3}$ up to logarithms. To find the overall joint prediction error, we weight this arm-conditional error by the selection probability $q_a$. This causes the dependence on $q_a$ to cancel out exactly. Rarely sampled arms contribute negligibly because their selection probabilities $q_a$ are small and rewards are bounded. Summing over all $K$ arms gives the policy-independent joint prediction bound $\widetilde{O}(K n^{-2/3} + \beta^2)$. This gives `EM-MIB+` its required prediction guarantee without forcing an unrealistic uniform density bound on every arm. We have explicitly clarified this step in Section 4.3, lines 449 to 463. This includes a new dedicated discussion in lines 458 to 463 (in blue).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.