acceptodds
Under review as a conference paper at ICLR 2027

UNCERTAINTY QUANTIFICATION OF RIEMANNIAN LOW-RANK TENSOR BANDITS WITH ROTATED ELIM- INATION

Abstract

Low-rank tensor bandits model multi-dimensional online decision problems, such as joint user segment–product–channel selection in online advertising. Existing tensor bandit algorithms focus on reward maximization but do not adequately address uncertainty quantification. To fill this gap, we study an inferential tensor bandit framework with a low-rank reward tensor and adaptively generated, batched online data. Two challenges arise. First, low-regret policies may prematurely stop sampling actions relevant to the inferential target, leaving insufficient information in its direction. Second, the low-rank constraint introduces nonlinear estimation bias, whereas policy-dependent sampling distributions invalidate conventional inference methods. We propose Rotated Inferential Tensor Elimination (RITE), an online, batched non-contextual bandit algorithm with a fixed rotated-elimination rule for decisions and an evolving low-rank nuisance estimator for quantification. RITE combines spectral rotation, maximum-confidence-width exploration, and active-set elimination, and uses Riemannian capped inverse-propensity updates for low-rank estimation. For inference, it constructs a stabilized one-step debiasing estimator that simultaneously handles low-rank estimation error and adaptive sampling. Theoretically, we establish a nonasymptotic error bound for Riemannian low-rank estimation, prove asymptotic normality for the efficient inference, and derive a finite-time regret bound that preserves the typical order of tensor elimination while adding only the cost of target exploration. Simulations and an online advertising experiment show that RITE yields confidence intervals with near-nominal coverage while maintaining regret close to tensor elimination.

Primary area:
learning theory
Keywords:
Low-Rank Bandits, Rotated Elimination, Remannian optimization, Uncertainty Quantification

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_GyWxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies statistical inference for prespecified linear functionals in low-rank tensor bandits, focusing on individual arm means and differences between two arm means. The proposed RITE algorithm combines tensor elimination in fixed spectral coordinates with target-specific exploration, while updating a low-rank nuisance estimator through capped inverse-propensity-weighted Riemannian regression. Its inference module constructs a one-step correction using the tangent space determined at the start of each batch and accounts for adaptive sampling through inverse-propensity ratios. Under the stated regularity conditions, the authors establish a low-rank estimation error bound and asymptotic normality, together with an additional target-exploration regret cost of order O(T)O(\sqrt{T}). Validation includes synthetic regret and coverage experiments, component ablations, and a simulated online environment constructed from advertising data.

Critical strengths
  1. The paper addresses a meaningful distinction between low-regret decision-making and valid statistical inference. In particular, elimination can leave a prespecified suboptimal arm with insufficient subsequent observations. This provides a clear statistical motivation for target-specific exploration.

  2. The integration of the decision and inference modules is well motivated. Keeping target-exploration observations outside the tensor-elimination decision state makes their additional regret cost transparent. Fixing the tangent space and correction direction at the beginning of each batch also supports a predictable score construction and a martingale analysis. These design choices provide a reasonable foundation for the proposed approach.

Critical weaknesses
  1. The connection between the proposed sampling policy and the conditions required for valid inference is not sufficiently established. Theorem 1 relies on local restricted curvature of the weighted design, sufficient effective information, and optimization iterates remaining in a stable neighborhood. Theorem 2 additionally requires negligible remainders, variance stabilization, variance-estimator consistency, and a Lindeberg condition. The supplement provides further sufficient conditions and remainder bounds, but it remains unclear in which explicit regime of dimensions, ranks, horizon, and exploration parameters RITE itself guarantees these requirements jointly. In particular, sufficient information for the specified target does not imply sufficient information in all directions needed to estimate the low-rank nuisance tensor. Section S.3.2 explicitly retains the need for an additional policy-coverage argument. This leaves an important gap in establishing the combined inferential and regret guarantees for the proposed algorithm.

  2. The benefit of the low-rank inference machinery over simpler alternatives is not sufficiently demonstrated. Since RITE explicitly samples the target arms and knows their sampling probabilities, informative comparisons would include estimators based directly on target-exploration observations and suitable IPW or augmented-IPW estimators accounting for adaptive sampling. The existing regret baselines do not establish whether tangent-space correction yields shorter, well-calibrated intervals at comparable regret. Moreover, the main regret and coverage experiments use different exploration strengths and initialization configurations; coverage is primarily evaluated under exact null constraints; and the advertising experiment adds Gaussian noise to an empirical reward tensor. These results provide preliminary support, but do not sufficiently establish the joint benefit under one operating configuration or clarify sensitivity to departures from the low-rank model.

Overall, the problem is worthwhile, but substantial uncertainty remains about the attainability of the theoretical conditions and the incremental value of the proposed inference procedure.

Questions for authors
  1. Clarification of the theoretical guarantees: Can the authors provide an explicit parameter regime in which RITE's actual sampling policy jointly satisfies the restricted-information conditions and the inferential product-rate conditions in the supplement? In particular, what growth rate of NkeffN_k^{\mathrm{eff}} can be guaranteed when εt≍t−1/2\varepsilon_t \asymp t^{-1/2} and the propensity cap is fixed?

  2. Validation of the inferential benefit: Under the same sampling policy, observations, and regret cost, how much does low-rank debiasing improve interval length and coverage relative to direct target-exploration estimators and suitable IPW or augmented-IPW baselines? Can coverage, interval length, and regret be reported jointly under one RITE configuration?

  3. Clarification of the scope of the current claims: Where are a prespecified target, exact Tucker rank, and fixed-horizon inference essential to the analysis? If the reward tensor is only approximately low-rank, what additional bias remains in the debiasing expansion, and how is this issue assessed in the advertising experiment? I do not require future extensions such as data-dependent target selection or anytime-valid inference, but the distinction between established guarantees and unsupported use cases should be explicit.

6 comments

Response to Q1 (Question1):

We thank the reviewer for raising this question. We have provided an explicit parameter regime in Section S.3.2 (Lines 1201–1254) and Section S.6.3 (Lines 1910–2000) of the supplementary material, under which RITE’s implemented sampling policy jointly satisfies the restricted-information conditions and the inferential product-rate conditions. We have also clarified the guaranteed effective-information growth under a fixed propensity cap. These additions are highlighted in red in the revised manuscript. Below, we provide further explanations.

(1)Information growth under a fixed propensity cap. Let P=∏j=1dpjP=\prod_{j=1}^d p_j. By construction, RITE employs the mixture policy $ \pi_t(i)=(1-\varepsilon_t)\mathbf 1\{i=I_t^{\rm TE}\}+\varepsilon_t q_H(i), \qquad q_H(i)\geq\frac{\eta}{P}, $ with εt=min⁡1/2,cε(t∨s0)−1/2\varepsilon_t=\min\\{1/2,c_\varepsilon(t\vee s_0)^{-1/2}\\}. For fixed πmin⁡>0\pi_{\min}>0, the capped-IPW design satisfies $ \begin{aligned} &\mathbb E\!\left[ \omega_t^{\rm lr} \langle\Delta,\mathcal A_t\rangle^2 \mid\mathcal F_{t-1}\right]\ =\sum_i \frac{\pi_t(i)}{\pi_t(i)\vee\pi_{\min}} \Delta_i^2\ \geq \min\left\{1,\frac{\eta\varepsilon_t}{P\pi_{\min}}\right\} \|\Delta\|_F^2. \end{aligned} $ Moreover, since ωtlr≥1\omega_t^{\rm lr}\geq1, the realized information is bounded below by the minimum number of target-exploration visits across actions. Concentration of these exploration counts yields, with high probability, Nkeff=Ωp(tk+1−s0){ N_k^{\rm eff} =\Omega_p\left( \sqrt{t_{k+1}}-\sqrt{s_0} \right) } for fixed dimensions and sufficiently large post-warm-up exploration counts.

Thus, RITE guarantees growing effective information even when tensor elimination concentrates on promising actions. This establishes the guaranteed growth rate under a fixed propensity cap.

(2)An explicit joint parameter regime. To verify the complete restricted-information conditions, consider fixed tensor dimensions and Tucker ranks, with the regularity conditions of Theorem 1 and Appendix S.3.2. We retain RITE’s original exploration schedule and choose πmin⁡(T)=ηcε2PT,\pi_{\min}(T)=\frac{\eta c_{\varepsilon}}{2P\sqrt{T}}, $ s_0\asymp\sqrt{T}[\log(pT)]^2,$ $ 2^{k_0-1}\asymp T^{7/8}.$

The propensity threshold is selected before sampling and remains fixed throughout the horizon. The warm-up length can be implemented using the existing initialization rule through a horizon-dependent cinit(T)c_{\rm init}(T). For sufficiently large TT, this choice ensures πt(i)≥πmin⁡(T)\pi_t(i)\geq\pi_{\min}(T) for every action. Hence, the capped-IPW weight coincides with ordinary IPW, and E![ωtlr⟨Δ,At⟩2∣Ft−1]=∣Δ∣F2.\mathbb E\\!\left[ \omega_t^{\rm lr} \langle\Delta,\mathcal A_t\rangle^2 \mid\mathcal F_{t-1}\right] =\\|\Delta\\|_F^2.

Consequently, the predictable restricted-information conditions in Appendix S.3.2 hold with N‾k=tk+1−1,Cri=1.\underline N_k=t_{k+1}-1,\quad C_{\rm ri}=1. Applying the restricted-curvature concentration result in Appendix S.5 gives $ { N_k^{\rm eff}\asymp t_{k+1}-1 } $ with high probability, uniformly over started batches.

(3)Verification of the inferential product-rate conditions. For an explicit sufficient inferential setting, additionally suppose that the optimal action is unique with a fixed positive reward gap, the prespecified nonzero entry or reward-gap target excludes the optimal action, and the noise is conditionally homoscedastic. We retain the local initialization, optimization-accuracy, and spectral-rotation conditions of the existing theoretical analysis. Under the phase-confidence and elimination results in Appendix S.7, the active set contracts to the optimal action before inference begins, with probability tending to one. The selected burn-in satisfies tk0≍pT7/8t_{k_0}\asymp_p T^{7/8}, while NTinf∼pTN_T^{\rm inf}\sim_p T. Since dT=O(Tlog⁡(pT))\mathfrak d_T=O(\sqrt T\log(pT)), Theorem 1 and the tangent-space perturbation bound yield max⁡k≥k0−1(rk+ηk)=Op(T−3/16log⁡T).\max_{k\geq k_0-1} (r_k+\eta_k) = O_p\left(T^{-3/16}\sqrt{\log T}\right). For completed inference batches, nkε‾k≳T3/8≫Deff+log⁡(pT).n_k\underline\varepsilon_k \gtrsim T^{3/8} \gg D_{\rm eff}+\log(pT). Substituting these rates into the checkable product-rate condition in Appendix S.6.3 gives $ \mathrm{Rem}_{\rm product}(H) = O_p(T^{-3/8}\log T). $ Under the specified target and noise conditions, the predictable inferential variance satisfies vT(H)≍T−1/2v_T(H)\asymp T^{-1/2}, so $ { T^{-3/8}\log T =o(T^{-1/4}) =o\bigl(v_T(H)^{1/2}\bigr) }, $ where the last equality indicates the inferential standard-error scale. The terminal short-batch contribution is likewise negligible; moreover, the maximal leverage satisfies $ \mathcal L_T(H)=O_p(T^{-1/4})\to0, $ and the nuisance-error contribution to the variance estimator vanishes. These verify the inferential remainder, leverage, and variance-consistency requirements of Appendix S.6 under the stated sufficient regime.

Therefore, the restricted-information and inferential conditions are jointly satisfied by an explicit configuration of RITE’s actual sampling policy. For fixed tensor dimensions, the warm-up and target-exploration costs remain O~(T)\widetilde O(\sqrt T), preserving sublinear regret under the existing regret regularity conditions.

Response to Q2:

We thank the reviewer for this suggestion. To isolate the benefit of low-rank debiasing, we have added a controlled comparison of RITE with direct target-arm estimation, stabilized IPW, and augmented IPW using the same low-rank Tucker estimator (AIPW) in Section S.1.6 (Lines 937–966, Table S7) of the supplementary material. The additions are highlighted in red in the revised manuscript, and the results are also presented below.

All methods use exactly the same adaptive RITE sampling policy, observations, and cumulative regret within each target experiment. The experimental configuration is fixed at p=6p=6, Tucker rank (2,2,2)(2,2,2), T=8000T=8000, σ=0.1\sigma=0.1, cε=7c_\varepsilon=7, and πmin⁡=10−3\pi_{\min}=10^{-3}, with uniform warm-up and four Riemannian steps per batch. The configuration was selected using independent pilot runs and evaluated over 250 new Monte Carlo replications. Each prespecified target uses its corresponding RITE exploration policy.

Table 1. Inferential comparison under identical RITE sampling trajectories (nonzero targets).

TargetMethodCoverageLengthRMSERegret
EntryRITE95.2%0.049080.0127211,495.53
Direct-target94.0%0.055440.0142911,495.53
IPW94.8%0.057420.0151311,495.53
AIPW96.0%0.058480.0149511,495.53
GapRITE94.4%0.088960.0233311,185.37
Direct-target92.8%0.106800.0266911,185.37
IPW94.0%0.109350.0284811,185.37
AIPW95.6%0.113120.0283311,185.37

From the results presented in Table 1, we observe that RITE achieves near-nominal coverage with the shortest confidence intervals and lowest RMSE for both targets. Relative to AIPW, RITE reduces average interval length by 16.1% for entry inference and 21.4% for reward-gap inference. Compared with direct target-arm estimation, the reductions are 11.5% and 16.7%, respectively.

The corresponding zero-target experiments exhibit the same pattern, with RITE attaining 94.8–97.2% coverage and reducing interval length by 17.5–22.9% relative to AIPW.

These results demonstrate the benefit of exploiting shared low-rank information across arms, particularly when direct observations of the inferential target are sparse. Importantly, these gains are achieved without any additional regret cost relative to the other estimators, since all methods share the same RITE decision trajectories.

Response to Q3:

Below, we clarify the scope of our inferential guarantees in (1), characterize the additional bias under approximate low-rank structure in (2), assess sensitivity through a rank-misspecification experiment in (3), and further examine this issue in the real-world advertising experiment in Point (4).

(1). Scope and practical relevance of the assumptions. Our inference framework focuses on a target HH, a fixed Tucker-rank model, and pointwise confidence intervals at a fixed horizon.The target HH is specified before online sampling because it determines the reference distribution qHq_H and the target-specific exploration policy. This does not require prior knowledge of the optimal action or the true tensor factors. The Tucker rank determines the low-rank manifold and its tangent space, which are central to the debiasing construction. In practice, the rank can be estimated from exploratory warm-up observations using mode-wise singular-value thresholding or validation-based selection, and then fixed for subsequent inference. The theoretical guarantees apply when the specified rank correctly describes the underlying tensor structure.

The fixed-horizon formulation provides pointwise asymptotic coverage for a specified target. Confidence intervals evaluated at multiple checkpoints are interpreted pointwise rather than as simultaneous confidence sequences.

(2). Additional bias under approximate low-rank structure. Suppose the true reward tensor admits the decomposition $ \mathcal T^\star=\mathcal T_r+\mathcal E, $ where Tr\mathcal T_r has Tucker rank r\mathbf r and E\mathcal E is the approximation residual.

Substituting this decomposition into RITE’s batch-wise one-step estimator yields the additional residual contribution $ { B_{{\rm app},k}(H) = -\langle\mathcal E,H\rangle + \frac1{n_k} \sum_{t\in\mathcal E_k} \rho_t^H (g_{H,k}^{\top}s_{I_t}^{(k)}) \mathcal E_{I_t}. } $ Using the target-reference identity E[ρtHf(It)∣Ft−1]=∑iqH(i)f(i),\mathbb E[ \rho_t^H f(I_t)\mid\mathcal F_{t-1}] = \sum_iq_H(i)f(i), the predictable component of this residual is B‾app,k(H)=−⟨E,H⟩+∑iqH(i)(gH,k⊤si(k))Ei.\overline B_{{\rm app},k}(H) = -\langle\mathcal E,H\rangle + \sum_iq_H(i) (g_{H,k}^{\top}s_i^{(k)}) \mathcal E_i.

The first term represents the approximation error in the target functional, while the second captures the portion corrected by the target-reference score. The difference characterizes the structural bias remaining after one-step debiasing.

More explicitly, by Cauchy–Schwarz and the definition of JH,kJ_{H,k}, $ \begin{aligned} |\overline B_{{\rm app},k}(H)| \leq{}& \|\mathcal E\|_F\|H\|_F\ + \sqrt{ h_{k-1}(H)^\top J_{H,k}^{\dagger} h_{k-1}(H) } \,\|\mathcal E\|_{q_H}, \end{aligned} $ where $ \|\mathcal E\|_{q_H}^2 = \sum_iq_H(i)\mathcal E_i^2. $ Under the existing target-information bound, this gives ∣B‾app,k(H)∣=O(∣E∣F).{ |\overline B_{{\rm app},k}(H)| = O(\\|\mathcal E\\|_F). }

Thus, the residual structural bias is controlled by the approximation error and its alignment with the inferential target. The one-step correction can partially cancel this error, but does not generally eliminate it. A sufficient requirement for negligible structural bias is that its aggregated contribution be op(vT(H)1/2)o_p(v_T(H)^{1/2}). The stronger condition $ \|\mathcal E\|_F=o(v_T(H)^{1/2}) $ also ensures this under bounded target-information constants, together with the corresponding nuisance-estimation and variance conditions. This identifies the scale at which approximate low-rank structure preserves the original inferential approximation.

(3). Empirical sensitivity to Tucker-rank misspecification. To assess the sensitivity highlighted in the reviewer’s weakness, we conducted an additional experiment with true Tucker rank (2,2,2)(2,2,2) and fitted ranks (1,1,1)(1,1,1), (2,2,2)(2,2,2), and (3,3,3)(3,3,3).

We used p=8p=8, T=3000T=3000, σ=0.1\sigma=0.1, w=0.8w=0.8, a fixed warm-up of 400 rounds, and 60 independent replications with paired environment seeds. The table reports nominal 95% confidence interval coverage, average interval length, and RMSE for entry and reward-gap targets.

Table 2. Sensitivity of RITE inference to Tucker-rank misspecification

Fitted rankTargetCoverageLengthRMSE
(1,1,1)(1,1,1)Entry91.791.7\\%0.14350.0561
(2,2,2)(2,2,2)Entry95.095.0\\%0.04420.0153
(3,3,3)(3,3,3)Entry95.095.0\\%0.05430.0181
(1,1,1)(1,1,1)Gap88.388.3\\%0.20590.0823
(2,2,2)(2,2,2)Gap96.796.7\\%0.05880.0172
(3,3,3)(3,3,3)Gap96.796.7\\%0.07300.0205

Note: Entry and Gap denote inference on a prespecified action’s expected reward and the expected reward difference between two prespecified actions, respectively. Fitted rank ( the Tucker rank assumed by RITE); the true Tucker rank (2,2,2)(2,2,2).

The results in Table 2 show that the correctly specified rank achieves near-nominal coverage with the shortest intervals and lowest RMSE. Rank underestimation increases estimation error and reduces coverage, particularly for reward-gap inference, while moderate overestimation maintains near-nominal coverage with somewhat wider intervals.

These findings illustrate how misspecification affects the complete RITE decision-inference procedure and complement the theoretical residual-bias characterization above.

(4). Interpretation of the advertising experiment. We thank the reviewer for this valuable suggestion. To strengthen the empirical evaluation, we have replaced the previous semi-synthetic experiment with a real-data experiment using the publicly available Outbrain Click Prediction dataset, with empirical rewards derived from actual impressions and click outcomes. We have updated Section 6, Figure 4, and Supplementary Section S.2 accordingly. Using the dataset's advertising and event information, we construct a third-order empirical reward tensor of size 14×12×714\times12\times7, indexed by advertiser, publisher, and day of week, with 1,176 possible actions.

We compare RITE against Tensor Elimination, Tensor Epoch-Greedy, Matricized ESTR-style, and Vectorized UCB over T=30,000T=30{,}000 rounds and 30 independent runs. The final mean cumulative regrets are 1,845.2 for Tensor Elimination, 1,949.9 for RITE, 4,936.5 for Tensor Epoch-Greedy, 5,363.1 for Matricized ESTR-style, and 7,641.4 for Vectorized UCB.

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

The paper proposes Rotated Inferential Tensor Elimination (RITE), a method for online batched non-contextual tensor bandits. RITE transforms the original tensor bandit into a lower-dimensional linear bandit via spectral rotation and then performs confidence-width exploration. This allows the construction of low-rank estimators and associated error estimators during online inference. The authors prove asymptotic normality of the estimators and derive regret bounds with order preservation. The stated claim is modest: RITE yields regret confidence intervals with near-nominal coverage while maintaining regret close to that of tensor elimination.

Critical strengths
  1. The paper gives a theoretical treatment of a new method (asymptotic normality, regret bounds with order preservation) together with simulation results that illustrate the main claims. In simulations, RITE achieves better regret than several standard baselines (tensor epoch-greedy, naive vectorized UCB, matricized bandits), underperforms the tensor elimination baseline, and additionally provides 95% confidence interval estimates.
Critical weaknesses
  1. The claim is limited. The new method is comparable to the tensor elimination baseline on regret; its distinguishing contribution is that it provides confidence estimates.
  2. No online experiments. The evidence is confined to controlled simulation environments. The paper states that results are shown “in simulations and an online advertising experiment,” but only simulation results are discussed, including semi-synthetic simulations. Figure 3 is captioned as “empirical coverage over 300 independent online experiments”; invites the reading that online experiment was run.
  3. The contribution is limited to establishing theoretical bounds for the proposed method; no other contributions are specified.
Questions for authors
  1. What are the “300 independent online experiments” in Figure 3? Are these simulation runs, or real online experiments? If the latter, where are the online advertising experiment results referred to in the text?

  2. Table S2 shows that tensor elimination and RITE share hyperparameters (c_init = 24, γ = 0.75, active-set multiplier 2.0), which makes the comparison controlled. Figure 2 nonetheless shows RITE underperforming tensor elimination. Do the authors understand why, and can they explain the source of the gap?

6 comments

Response to Q1(Question 1) and W2(Weaknesse 2):

Our wording in the previous manuscript was indeed misleading. First, the “300 independent online experiments” in Figure 3 refer to 300 independent simulated online decision-making trajectories. Each replication simulates the sequential sampling process and evaluates the resulting confidence intervals. Figure 3 therefore reports coverage under simulated settings.

In response to the weakness you raised, we have conducted new online experiments using the publicly available Outbrain Click Prediction dataset to strengthen the empirical evaluation. The new dataset, experimental setup, and results are presented in Section 6 (Lines 507–534, including Figure 4) of the revised manuscript and Section S.2 (Lines 1072–1125) of the supplementary material. All corresponding additions and modifications are highlighted in red.

The revised Figure 4 presents an experiment using real historical advertising records from the Outbrain Click dataset. We construct a 14×12×714\times12\times7 empirical reward tensor indexed by advertiser, publisher, and day of week, corresponding to 1,176 possible actions. We evaluate five online decision policies over T=30,000T=30{,}000 rounds and 30 independent runs.

The results of the new real-data experiment using the Outbrain Click Prediction dataset are summarized in the following table. In Table 1 below, we report the cumulative regret at T=3,0000T=3{,}0000.

Table1. Final mean cumulative regret on the Outbrain Click Prediction dataset.

MethodRegret
Tensor Elimination1,845.2
RITE1,949.9
Tensor Epoch-Greedy4,936.5
Matricized ESTR-style5,363.1
Vectorized UCB7,641.4

The online advertising experiment further demonstrates that RITE maintains decision performance close to Tensor Elimination, with a final mean cumulative regret of 1,949.9 versus 1,845.2 (a 5.7% difference). Both methods substantially outperform Tensor Epoch-Greedy, Matricized ESTR-style, and Vectorized UCB, while exhibiting flatter late-stage regret trajectories. These results further support our theoretical finding that target-specific exploration preserves the leading regret order of Tensor Elimination.

Response to Q2:

Yes, the gap is the cost of preserving information about the prespecified target. Under fixed Tucker ranks and comparable mode dimensions, the leading regret orders of Tensor Elimination and RITE are

R_T^{\rm TE}&=\widetilde O\\!\left(p^{d/2}+p^{(d-1)/2}\sqrt T\right),\\\\ R_T^{\rm RITE}&=\widetilde O\\!\left(p^{d/2}+p^{(d-1)/2}\sqrt T+\sqrt T\right), \end{aligned}$$ where $p$ is the common mode size, $d$ the tensor order, and $T$ the time horizon. More precisely, Theorem 3 gives $$R_T^{\rm RITE}\le s_0\Delta_{\max}+R_{M_T}^{\rm TE}+\Delta_{\max}N_T^{\rm tar}, \qquad \Delta_{\max}=\max_{i\in\mathcal I}\bigl(\mathcal T^\star_{i^\star}-\mathcal T^\star_i\bigr),$$ where $s_0$ is the warm-up length, $i^\star$ is an optimal arm, $M_T$ the number of executed TE proposals, and $N_T^{\rm tar}$ the number of target-exploration draws. Because $\varepsilon_t\asymp t^{-1/2}$, $\mathbb EN_T^{\rm tar}=O(\sqrt T)$. Target draws advance the calendar clock but are excluded from the TE elimination state; their additional regret does not change the leading order. Supplementary Figure S8 further reports the regret–coverage–interval-length trade-off as $c_\varepsilon$ varies. **Therefore, RITE’s slightly higher cumulative regret than Tensor Elimination in Figure 2 is consistent with our theoretical analysis: the additional regret arises from target-specific exploration required for statistical inference, while the leading regret order remains unchanged.** # Response to W1 and W3: We thank the reviewer for these comments. Regarding the reviewer’s concerns about our contributions, we emphasize that this research problem is both important and technically challenging. As discussed in our Abstract and Introduction, low-regret policies progressively concentrate on promising actions, potentially leaving insufficient information for inference on prespecified targets. Moreover, nonlinear low-rank estimation introduces structural bias, while history-dependent adaptive sampling complicates conventional statistical inference. Addressing these challenges is essential for reliable uncertainty quantification in tensor bandits. **Our contributions go beyond adding confidence intervals to tensor elimination and can be summarized as follows.**

(i) RITE introduces a two-branch architecture that decouples rotated tensor elimination for online decision-making from exploration and statistical inference. Observations are excluded from the elimination design but retained for estimation and inference, preserving the decision dynamics of tensor elimination while maintaining the information required for valid inference. Importantly, this modular design is not inherently restricted to tensor elimination and provides a general framework for integrating statistical inference with other tensor bandit decision policies.

(ii) We develop a unified estimation and inference procedure combining capped-IPW Riemannian updates on fixed-rank Tucker manifolds with stabilized one-step debiasing. The capped-IPW updates control sampling-weight variability while preserving low-rank structure, whereas batch-start tangent-space correction and target-reference importance weighting address nonlinear estimation bias and adaptive sampling, respectively. Together, these components enable valid uncertainty quantification under history-dependent sampling.

(iii) We establish nonasymptotic low-rank estimation error bounds under adaptive sampling, asymptotic normality and valid confidence intervals for tensor functionals, and a finite-time regret bound. In particular, RITE preserves the leading regret order of tensor elimination with an additional O~(T)\widetilde O(\sqrt{T}) cost, providing joint theoretical guarantees for inference and online decision-making.

To make these contributions more explicit, we have revised Section 1 (Introduction, Lines 118–136) of the revised manuscript to summarize the three main contributions. All modifications are highlighted in red.

Dear Reviewer DMk1,

We have endeavored to address each of your concerns point by point and have revised the manuscript accordingly. We would welcome the opportunity to discuss these issues with you further, as we believe that continued dialogue will help us improve the quality and rigor of the manuscript. We would be grateful if you could take the time to discuss them with us.

Thank you for your time and consideration.

Sincerely,

The Authors

Reviewer_6H16OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a method to compute the confidence interval of the expected reward for multi-armed bandits, motivated by a real-world application of online advertising. As a natural mathematical embodiment, the authors employ a low-rank tensor regression model within the bandit setting.

The proposed framework consists of two parallel modules: a decision branch and an inference branch. The decision branch uses a spectral rotation technique to transform the problem into a lower-dimensional linear bandit, where candidate actions are sequentially eliminated based on a UCB formalism. The inference branch, on the other hand, continuously updates the low-rank tensor estimator by minimizing a capped inverse-probability-weighted squared loss via Riemannian gradient descent on the Tucker manifold.

The main theoretical contributions of the paper are proving an error bound for tensor low-rank estimation (Theorem 1) and establishing the CI for the estimated reward gap based on asymptotic normality (Theorem 2) .

Critical strengths
  • The paper provides a formal tensor low-rank estimation error bound, which is a solid technical contribution.

  • It establishes the CI for fixed targets via a debiased estimator. The mathematical techniques used appear to be solid.

Critical weaknesses

1. Lack of comparison with major alternatives.

The authors make a strong claim that "Existing tensor bandit algorithms focus on reward maximization but do not adequately address uncertainty quantification". However, a quick literature search shows that there have been significant advances in probabilistic tensor regression in recent years addressing similar challenges. The authors seem to completely ignore those UQ approaches designed for exploration and predictive distributions, possibly by narrowly defining UQ as building frequentist confidence intervals.

In particular, the paper ignores recent developments in variational inference and Thompson sampling for tensors. Since the paper cites Zhou et al. (2024), the authors must be aware of those prior work. It is not clear why the paper does not compare the proposed method against the Thompson sampling approach explicitly discussed in Zhou et al. (2024). As discussed in Introduction, online advertising is the main motivating application of this paper. In exactly the same context, several papers provide solutions for UQ by explicitly deriving the predictive distribution for the reward using variational Bayesian approaches. I strongly encourage the authors to acknowledge these works, clarify the difference in UQ objectives, and make direct theoretical and empirical comparisons.

  • Thompson sampling approach: Zhou, J., Hao, B., Wen, Z., Zhang, J., & Sun, W. W. (2024). “Stochastic Low-Rank Tensor Bandits for Multi-Dimensional Online Decision Making.” JASA. (Cited, but Thompson sampling is omitted from the baselines).
  • Online Bayesian Tucker decomposition: Fang, S., et al. (2021). “Bayesian Streaming Sparse Tucker Decomposition (BASS-Tucker).” UAI.
  • Variational Bayes UQ for online advertisement: Ide, T., et al. (2024). “Sequential uncertainty quantification with contextual tensors for social targeting.” Knowledge and Information Systems.

2. Lack of end-to-end description of the learning algorithm.

From a machine learning perspective, the description of the algorithm appears incomplete, which significantly hurts readability and reproducibility. Examples include:

  • How the tensor is initialized through "low-rank tensor completion" during the warm-up period.
  • How the exact Tucker ranks are estimated or specified in practice.
  • How the orthogonal projection onto the tangent space of the Tucker manifold is actually computed using factor matrices and core tensors, which is critical for computational complexity.
  • How hyperparameters like η\eta are determined or tuned.
  • How gH,kg_{H,k} is sequentially calculated in the one-step debiasing step.

3. Strong theoretical assumptions that hurt practical usability.

While establishing the bounds in Theorems 1 and 2 is a solid theoretical achievement, the proposed framework relies on a series of strong assumptions, many of which can be highly unrealistic in real-world scenarios or are not even verifiable. Unlike the probabilistic alternative methods introduced above, where assumptions like prior distributions are explicit and easily debuggable, the mathematical assumptions are embedded behind the theorems in a cascading fashion and significantly hurt practical utility, potentially making the algorithm vulnerable in an uncontrollable manner. Those assumptions include:

  • The true reward tensor has an exact and known Tucker rank throughout the online session. Model misspecification is not allowed.
  • The reward perfectly follows a linear tensor inner product with additive sub-Gaussian noise, which can be unnatural for marketing metrics that typically require non-linear link functions.
  • The initial warm-up estimate invariably falls within the local stability neighborhood of the true tensor. It is unclear how the confidence interval in Theorem 2 behaves when the true environment deviates from the exact low-rank structure.

4. Misleading claims regarding the online advertisement application.

In Section 6, the authors evaluate the proposed framework in an "online advertising" setting to demonstrate practical utility. However, Appendix S.2.1 reveals that this is a semi-synthetic simulation. While an empirical tensor from a previous study is used as the fixed ground-truth mean, the authors simply added simulated Gaussian noise ξt∼N(0,30002)\xi_t \sim N(0, 3000^2) to generate observations. Claiming this as a demonstration of real-world applicability sounds extremely misleading.

Questions for authors
  1. Please provide theoretical and empirical comparisons against the probabilistic alternative methods listed above, particularly clarifying why the proposed approach is practically superior to scalable Variational Inference methods.

  2. Please provide explicit mathematical formulations for the tangent space projection, retraction, and the full end-to-end learning algorithm in the supplementary material to ensure reproducibility.

  3. Please elaborate on how users should tune the aforementioned hyperparameters in practice, and discuss the robustness of the derived CI when the true tensor rank is misspecified.

  4. Please clarify the semi-synthetic nature of the experiment in Section 6 in the main text, or provide empirical evaluation results using actual logged bandit feedback rather than simulated Gaussian noise.

8 comments

Response to Q1 (Question 1):

We thank the reviewer for pointing this out. Our previous discussion of uncertainty quantification focused primarily on frequentist confidence intervals and did not sufficiently consider Bayesian posterior and predictive uncertainty quantification. We have clarified the theoretical distinction between Bayesian uncertainty quantification and frequentist statistical inference in Section 1 (Lines 80–87) of the revised manuscript, and added empirical comparisons with TES, TensorUCB, and BASS-Tucker in Section S.1.5 (Lines 851–912) of the supplementary material. We next explain these theoretical differences, particularly the advantages of RITE over scalable variational inference methods.

We carefully read through the three methods you mentioned:

a. Tensor Ensemble Sampling (Zhou et al., 2024). TES constructs an ensemble of low-rank reward models by perturbing observed rewards and prior centers. An ensemble member is sampled to guide arm selection. The paper also proves a Bayesian regret statement for its general approximate Thompson-sampling scheme (Supplementary Theorem 3). This bound involves the posterior distribution of the optimal arm, the approximate arm-sampling distribution, and their Hellinger distance. The additional term captures approximation error in action selection; Zhou et al. explicitly note that deriving an explicit TES-specific bound requires further control of this term. Thus, this is a decision-regret result, not a guarantee that ensemble quantiles cover a fixed entry or reward gap with probability 1 − α. Moreover, the frequentist ridge-regression confidence bounds used by their tensor-elimination algorithm are not confidence bounds for TES ensemble samples.

b. Online variational TensorUCB (Idé et al., 2022). TensorUCB applies variational Bayesian tensor regression with a factorized Gaussian approximation to estimate latent factors and their uncertainty. It uses approximate predictive uncertainty to construct upper confidence bounds for online action selection. The method establishes sublinear regret for its scaled influence-maximization objective. However, predictive uncertainty used for exploration does not directly establish calibrated frequentist confidence intervals for tensor entries or reward gaps under adaptive sampling.

c. BASS-Tucker (Fang et al., 2021). BASS-Tucker performs scalable streaming Bayesian Tucker factorization using a spike-and-slab prior on each core coefficient and approximate posterior updates. Its streaming update projects the updated distribution back to a tractable posterior approximation by moment matching. This is an efficient posterior reconstruction procedure. Its formulation does not specify an adaptive bandit policy or a regret bound. It also does not establish frequentist coverage for a fixed tensor functional under policy-dependent sampling.

(1) Regarding your question of “why the proposed approach is practically superior to scalable variational inference methods,” the distinction is not whether variational inference (VI) can efficiently quantify posterior or predictive uncertainty,but whether the resulting interval is calibrated for a tensor entry or reward gap under adaptive bandit sampling.

To make this distinction explicit, let θH⋆=⟨T⋆,H⟩\theta_H^\star=\langle\mathcal T^\star,H\rangle and write the error of a VI-based point estimate as θ^VI(H)−θH⋆=bH+ξH\widehat\theta_{\mathrm{VI}}(H)-\theta_H^\star=b_H+\xi_H, where bHb_H is its estimation bias and ξH\xi_H has repeated-sampling variance vHv_H. A nominal 9595\\% interval based on the approximate VI variance v~H\widetilde v_H need not attain 9595\\% frequentist coverage. Under an illustrative Gaussian error approximation, its actual coverage is

\mathrm{Cov}_{\mathrm{VI}}(H) &\approx \Phi\\!\left(\frac{1.96\sqrt{\widetilde v_H}-b_H}{\sqrt{v_H}}\right) -\Phi\\!\left(\frac{-1.96\sqrt{\widetilde v_H}-b_H}{\sqrt{v_H}}\right),\\ =2\Phi\\!\left(1.96\sqrt{\widetilde v_H/v_H}\right)-1 \quad\text{if }b_H=0. \end{aligned}$$ Thus, whenever $\widetilde v_H<v_H$, even an unbiased estimate under-covers. Mean-field factorization can omit dependence among latent factors when propagating uncertainty to $\theta_H$, while regularization can contribute to $b_H$; neither discrepancy is automatically corrected by an uncertainty estimate designed for UCB prediction. RITE instead targets the repeated-sampling distribution directly: inverse-propensity weighting accounts for policy-dependent observations, and a tangent-space one-step correction removes the leading low-rank plug-in bias. Under our stated assumptions, these steps yield $$\frac{\widehat\theta_{\mathrm{db}}(H)-\theta_H^\star} {\sqrt{\widehat V_T(H)}}\\ \Rightarrow\\ N(0,1), \qquad \Pr\\!\left\\{\theta_H^\star\in \left[\widehat\theta_{\mathrm{db}}(H) \pm1.96\sqrt{\widehat V_T(H)}\right]\right\\}\longrightarrow0.95.$$ The resulting advantage for the reviewer’s inferential objective is coverage calibration. **This can also be seen from the results presented in Tables 1 and 2 below.** With $100$ independent repetitions and nominal $95\\%$ intervals, RITE achieves $95\\%/92\\%$ empirical coverage for zero-target Entry/Gap, versus $62\\%/70\\%$ for the online variational TensorUCB baseline. For nonzero targets, the corresponding coverages are $92\\%/91\\%$ (RITE) and $87\\%/85\\%$ (TensorUCB). Although TensorUCB’s intervals are shorter, they exhibit substantial under-coverage in the zero-target experiments. These observations support the value of RITE’s adaptive-sampling-aware debiasing for *reliable target-specific inference*, precisely the distinction raised by the reviewer. **(2)Empirical comparison** We conducted additional empirical comparisons with Tensor Ensemble Sampling (TES; Zhou et al., 2024), TensorUCB (Idé et al., 2022), and BASS-Tucker (Fang et al., 2021). The experimental settings and implementation details are provided in Section S.1.5 of the supplementary material. We first compare RITE, TES, and TensorUCB in four tensor-bandit settings. BASS-Tucker is excluded because it does not define a bandit action-selection policy or a corresponding cumulative regret measure. **Table 1.** regret . | Setting | RITE | TES | TensorUCB | |:----------------------------|-------------------:|-------------------:|-------------------:| | $p=15,\\ w=0.5,\\ T=15{,}000$ | $30\\,986\pm3\\,172$ | $10\\,721\pm1\\,893$ | $25\\,059\pm6\\,243$ | | $p=20,\\ w=0.5,\\ T=20{,}000$ | $47\\,022\pm4\\,792$ | $35\\,125\pm3\\,509$ | $27\\,938\pm7\\,164$ | | $p=15,\\ w=0.8,\\ T=10{,}000$ | $32\\,308\pm3\\,973$ | $16\\,453\pm2\\,464$ | $33\\,408\pm5\\,047$ | | $p=20,\\ w=0.8,\\ T=20{,}000$ | $39\\,868\pm2\\,418$ | $28\\,858\pm3\\,152$ | $27\\,811\pm4\\,280$ | |||| **Uncertainty quantification comparison.** We further compare all four methods for target-specific uncertainty quantification using identical RITE-generated adaptive trajectories. We report empirical coverage, mean interval length, and RMSE over 100 independent replications for each truth setting.

Table 2. Uncertainty quantification (9595\\% nominal intervals; 100100 repetitions per truth setting).

TruthTargetMethodCoverageLengthRMSE
ZeroEntryRITE95%0.020860.00673
ZeroEntryTES99%0.624490.16825
ZeroEntryTensorUCB62%0.011220.00658
ZeroEntryBASS-Tucker100%0.073630.00094
ZeroGapRITE92%0.033100.01082
ZeroGapTES99%1.100910.24434
ZeroGapTensorUCB70%0.017470.00803
ZeroGapBASS-Tucker100%0.115710.00135
NonzeroEntryRITE92%0.061410.02190
NonzeroEntryTES60%1.039170.83195
NonzeroEntryTensorUCB87%0.019530.00922
NonzeroEntryBASS-Tucker86%0.234080.04864
NonzeroGapRITE91%0.101460.02953
NonzeroGapTES68%1.805971.15143
NonzeroGapTensorUCB85%0.029370.01083
NonzeroGapBASS-Tucker93%0.367330.05521

Note: Entry denotes the expected reward of a prespecified action, and Gap denotes the expected reward difference between two prespecified actions. Zero and Nonzero indicate whether the true target value equals zero or is nonzero.

Tables 1 and 2 show that TES achieves lower cumulative regret, consistent with Zhou et al. (2024), while RITE provides better-calibrated target-specific confidence intervals. For zero-valued Entry and Gap targets, RITE achieves coverage of 95% and 92%, compared with 62% and 70% for TensorUCB. For nonzero targets, RITE achieves 92% and 91% coverage, exceeding TensorUCB (87% and 85%) and TES (60% and 68%). RITE also yields substantially shorter intervals than TES and BASS-Tucker while maintaining near-nominal coverage. These results highlight RITE’s advantage in target-specific statistical inference with theoretical regret guarantees.

Response to Q2:

We thank the reviewer for pointing out that the algorithmic implementation was not described in sufficient detail. We have expanded Section S.4 (Full RITE Procedure, Lines 1368–1473) of the supplementary material to provide a more detailed end-to-end description of RITE. All additions and modifications are highlighted in red in the revised manuscript. Below, we address the implementation details raised by the reviewer.

For warm-up initialization, we now explicitly describe how the initial Tucker estimate is constructed from the warm-up observations. The implementation employs inverse-propensity-weighted tensor filling, followed by truncated HOSVD and capped-IPW low-rank gradient refinement. The resulting factor spaces determine the fixed rotation used in subsequent tensor elimination.

Regarding Tucker rank specification, we explicitly clarify that the Tucker rank vector r=(r1,…,rd)\mathbf r=(r_1,\ldots,r_d) is a prespecified input, following the standard fixed-rank setting commonly adopted in low-rank tensor inference. It determines the factor dimensions, the low-rank manifold, and the tangent-space coordinates used for estimation and inference.

For tangent-space projection and low-rank updating, we provide an explicit mode-wise tangent-space projection using the factor-space projectors and their orthogonal complements. We further specify the capped-IPW gradient, the projected-gradient update, and the truncated-HOSVD retraction:

\= \operatorname{HOSVD}_{\mathbf r} \left( \mathcal T^{(j)} - \alpha_{k,j} \mathcal P_{\mathcal T^{(j)}} \bigl(G_k^{(j)}\bigr) \right).$$ The corresponding step-size rule and iteration procedure are also detailed in Appendix S.4. For the computation of the inferential direction, we clarify how the batch-start tangent coordinates are constructed and how the target-specific information matrix is formed. The inferential direction is then computed by solving \$ J_{H,k}\,g_{H,k}=h\_{k-1}(H), \\quad g\_{H,k}=J\_{H,k}^{\\dagger}\,h\_{k-1}(H), \$ using the Moore–Penrose pseudoinverse. Both the reference distribution and the inferential direction are fixed before observing rewards from the corresponding inference batch. Regarding hyperparameters and algorithmic execution, we clarify the roles of the warm-up iteration count, capped-IPW truncation, Riemannian step size, and low-rank update iterations. We also refine Algorithm S1 to explicitly connect initialization, batch-start inferential-direction computation, tensor elimination, target-directed exploration, and low-rank updating.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.