- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
-
This paper studies a -armed bandit problem using a multi-index model, where the expected reward is determined by the context only through an unknown linear map with : specifically, it is defined as where is a context shared by all actions and is an action-specific reward function (need not be parametric).
-
Under specific constraints, especially on the shape of the reward function for all , namely coordinate-wise monotonicity and entire monotonicity, the paper proposes 3 algorithms, all of which achieve sublinear regret bounds for both known and unknown .
-
Under the coordinate-wise monotonicity, where increasing any single coordinate of does not decrease , the corresponding algorithm
CM-MIBachieves an expected regret bound of order , and the authors provide a matching lower bound (in terms of ) for this problem under the same shape of reward. -
Under entire monotonicity, which is stronger than coordinate-wise monotonicity when , the corresponding algorithms
EM-MIBandEM-MIB+achieve regret bounds of order and , respectively. The authors also provide a lower bound for this setting, matching that of EM-MIB+ (in terms of ).
Critical strengths
-
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.
-
I found a technical argument interesting.
- Specifically,
EM-MIB+plugs the least-squares estimator intoFALCON+, 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.
- Specifically,
-
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-MIBandEM-MIB+in terms of , up to logarithmic factors.
Critical weaknesses
-
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 is known.
- Bibaut & van der Laan (2019) consider least squares over càdlàg functions on with sectional (Hardy-Krause) variation norm at most , where and .
- By Eq. (3), every is a constant plus the nonnegative multiple of a distribution function (Line 314-317). Since a constant has norm and a distribution function has norm one, .
- Hence is contained in the class considered by Bibaut & van der Laan (2019) with .
- 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.
-
Assumptions seem to be too strong.
- The upper bounds for unknown 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 , determined by a known set of anchor coordinates, rather than in some basis of the index space.
- For example, let with and . Then is coordinate-wise monotone in , since it is constant in and increasing in .
- Since the canonical chart does not depend on the choice of row basis, it can be computed directly from .
- With and , we obtain , i.e., .
- Since , the same reward in canonical coordinates is , 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).
- 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 are fixed" leaves for implicit. Please state explicitly that for , as in Definition C.2.
- Lemma C.14 (Line 1516): "The constant depends only on , , and " should read ", , and ". The quantity is the variance proxy defined in the lemma (Line 1499), and the proof itself uses ", , and " (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
-
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?
-
Which concrete subspace estimator provably satisfies Assumption 7 under the uniform-exploration distribution?
-
Is explicit identification of the row space of 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 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 is a bounded set of full-row-rank matrices, and is a coordinate-wise increasing affine rescaling of the bounding box of the support of to , assuming the box is nondegenerate. In other words, the learner searches over the projection and the functions at the same time, instead of estimating 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 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?
- From my perspective, the regret analysis of
-
If possible, could the authors add context-aware baselines, including Ma and Cai (2025) on compatible single-index instances?
4 comments
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 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 and measure dedicated CPU and memory capacities, and measures an additional resource contributing unknown amounts of both. Effective capacities are and . The dedicated capacities are known anchors from their physical interpretation, while must be learned. For a job with random resource requirements, the probability of meeting both requirements is their joint distribution function evaluated at , 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 be two event times for the same subject and the observed covariates. Under the model , the probability that both events occur by deadlines is $ F(\log t_1-b_1^\top q,\ \log t_2-b_2^\top q),$ where is the joint error distribution function. Increasing changes only the first threshold; increasing changes only the second. Thus, for , the two log-deadlines are known anchors and . The effects remain unknown. The function 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 is supplied. The minimax horizon exponents are and , respectively. Thus, the separation persists even after the difficulty of estimating 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 , instance. The scalar context is uniform on , 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).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.
A Warm Thank You!
We value your constructive feedback, thoughtful engagement, and positive reassessment of our work. Thank you for your support.
Part 1/2: Questions 1-3
We thank the reviewer for the careful assessment and the specific suggestions.
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).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 X with response Z=(A,arctanY). This bounds the response while preserving all information in (A,Y).
The method constructs a matrix M capturing the directions in which E[X∣A,Y] varies, corrects for the covariance of X, and estimates the r projection directions. Assumptions 5 and 6 ensure these identify the subspace of L.
Their stated theorem does not directly provide the expected squared error required by Assumption 7. A short additional argument bridges this gap. Because both X and Z are bounded, we obtain an expected squared error of 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]≤nC(P), where P and PL 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) and the projector loss is bounded.
Taking C2=C(P)λ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.
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 M and the monotone arm functions. Changing M 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 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) 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 M 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.