- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies graph-unimodal stochastic bandits with symmetric heavy-tailed rewards and unknown moment parameters. It combines amplified constant-rank resampled median-of-means confidence bounds, dyadic prefix caching, and robust leader scores. The main result is an anytime logarithmic regret guarantee whose growing term involves only neighbors of the optimal arm. A graph-free specialization improves the published RMM-UCB horizon dependence from to . Both proposed configurations have theoretical guarantees. Experiments investigate finite-horizon performance, cache activation, and the effects of graph localization and robust leader estimation.
Critical strengths
-
A meaningful theoretical improvement. Obtaining logarithmic regret without knowing either the moment order or its bound, while localizing the growing exploration cost to optimal-arm neighbors, is a useful contribution under the stated symmetry assumption. The practical configuration also satisfies the main regret guarantee.
-
Careful treatment of adaptive reuse. The analysis explicitly charges a failed cached endpoint by the number of decisions it can influence. The resulting pathwise local-selection bound can be evaluated at adaptive leader counts. The robust-ascent argument then establishes finite expected suboptimal-leader occurrences. This connection, particularly Proposition 22, is the most interesting technical aspect of the paper.
-
Informative and transparent experiments. The matched-budget, empirical-leader, and sign-budget comparisons help separate the effects of different components. The paper reports paired uncertainty estimates and includes unfavorable results, delayed activation, and sensitivity to departures from symmetry. These diagnostics make the practical behavior easier to assess.
Critical weaknesses
-
The heavy-tail dependence remains potentially loose. For , the upper-bound coefficient differs substantially from the Gaussian benchmark . Appendix G.5 acknowledges this correctly. Nevertheless, the lower bound establishes the logarithmic horizon order and necessary neighbor exploration, rather than matching optimality in the heavy-tailed regime. The quadratic information modulus in Proposition 24 makes the remaining gap particularly interesting.
-
The finite remainder limits the practical interpretation of localization. The constant can depend on the entire graph and on difficult local ascent gaps. Its magnitude is difficult to assess from the displayed rate. The activation studies illustrate a substantial transient: in Table 18, the certified configuration has no finite endpoint by rounds at degree eight, despite much earlier leader resolution. The practical configuration improves this behavior, but a more interpretable bound on the transient would strengthen the result.
-
The empirical advantage depends on the regime. Practical APR-Local performs well on the larger paths, but uniINF has significantly lower regret on the 15-arm Pareto instance. Table 8 also shows that APR-Local saves regret on distant arms while spending considerably more on optimal-arm neighbors. Thus, the evidence supports a useful localization tradeoff rather than a general finite-horizon advantage of the confidence construction. The predominantly homogeneous reward settings also provide limited evidence about the benefits of arm-wise adaptation.
Questions for authors
-
Given Proposition 24, what moment-and-gap dependence do the authors conjecture is achievable over the symmetric distribution class? Which part of the proposed construction is responsible for the heavier dependence?
-
Can the ascent proof yield a compact upper bound on in terms of local ascent gaps, moment parameters, and graph degree? A loose but interpretable expression would help explain when the neighbor-local leading term becomes relevant.
-
Can the authors explain the relatively large optimal-neighbor regret compared with uniINF? Appendix J.6 indicates that much of this cost persists with a correct leader and finite candidate endpoints, so delayed activation alone does not explain it.
2 comments
Thank you for the detailed response. The explanation of the block-mean concentration step clarifies the source of the heavier gap dependence. The explicit decomposition of the finite remainder and the distinction between leader resolution and cache formation also address my questions. Please ensure that the revised manuscript includes Appendix N and the complete proof of Proposition 34.
The regret decomposition clarifies why substantial neighbor exploration persists even with a correct leader and finite endpoints. I appreciate the acknowledgment that the experiments primarily demonstrate localization and robust leadership, while the benefit of adaptation to heterogeneous arm-wise tails remains unmeasured.
The gap between the upper and lower bounds and the potentially large activation cost remain limitations, but the response improves their interpretation. I maintain my weak-accept recommendation.
Response to Reviewer tzv3: Gap dependence, activation, and regret decomposition
We thank the reviewer for the helpful comments.
W1 / Q1. Which gap dependence might be achievable? At a common centered (1+a)-moment envelope M, Proposition 24 gives a KL information modulus of order Δ2/M2/(1+a), with a Gaussian pair attaining the order. This suggests a neighbor coefficient of order M2/(1+a)/Δ for small gaps. The current upper bound uses the raw block-mean radius M1/(1+a)g−a/(1+a). For each g≥2, put mass 1/(2g) at each of ±(Mg)1/(1+a) and the remaining mass at zero. The moment is M. With probability (1−1/g)g−1≥e−1 there is exactly one nonzero observation, so the block mean has absolute error M1/(1+a)g−a/(1+a). Requiring this radius to be of order Δ and multiplying the sample count by Δ gives the heavier Δ−1/a dependence. Achieving the quadratic-information target with unknown moment order and scale calls for a different confidence construction that uses symmetry in estimating the center.
W2 / Q2. Instance dependence and activation. Page 6 states the explicit remainder. Proposition 34 (Appendix N) bounds the expected count of each suboptimal leader i by
+\frac{16}{7}\sum_{h\in\{i\}\cup\mathcal B_i}\frac{2^{-3r_{ih}}}{v_{ih}} +\frac{8|\mathcal D_i|}{\lambda c}.$$ Here $\mathcal B_i$ contains the locally best arms, $\mathcal D_i$ the other candidates in $\mathcal N^+(i)$, and $\lambda=\gamma/[2(\gamma+1)]$ for maximum degree $\gamma$. The score threshold uses the sufficient epoch $r_{ih}$ defined just before Eq. (266) for radius at most $g_i/4$, where $g_i=\max_{j\in\mathcal N(i)}\mu_j-\mu_i$. Its group-size scale is $[M_h/(g_i/4)^{1+a_h}]^{1/a_h}$, with a minimum of one. The leader-count conversion uses fractions $v_{ii}=1/(\gamma+1)$ and $v_{ih}=\lambda/|\mathcal B_i|$ for locally best arms. The count threshold in Eq. (266) uses the local gaps $\max_{h\in\mathcal N^+(i)}\mu_h-\mu_j$ and moments for $j\in\mathcal D_i$. The explicit regret remainder is $$\begin{aligned} \overline C_{\rm climb} &=\sum_j\Delta_j+\sum_{i\ne i^\star} C_i\max_{j\in\mathcal N^+(i)}\Delta_j\\ &\quad+\sum_{j\in\mathcal N(i^\star)}\Delta_j[B_j(\Delta_j/2;c)+4/c]. \end{aligned}$$ For $T\ge K$, the leading term is $\log T\sum_{j\in\mathcal N(i^\star)}\Delta_j A_j(\Delta_j/2)$. The middle sum can include every suboptimal leader. The final sum pays the finite cache terms, with $B_j$ from Eq. (265) and $c$ the budget divisor. Increasing $c$ reduces the expected cache charge in $C_i$, while $B_j$ grows with $\log c$ because more samples are needed at the tighter confidence budget. The score and count thresholds therefore quantify different sources of a large transient. In particular, small ascent gaps away from the optimum can delay the regime described by the leading neighbor term. The sufficient thresholds concern accuracy. Table 18 measures formation separately. At degree eight, 0 of 30 certified runs have a finite endpoint by 90,000 rounds, the balanced formation prediction is 147,456, and median leader resolution is 4,676. **W3(a) / Q3. Why neighbor regret remains high.** A correct leader restricts the action to its closed neighborhood. On nonforced rounds, the optimistic endpoint can still select a neighbor even when all candidate endpoints are finite. Appendix J.6 splits both policies at the practical policy's first finite endpoint in each paired trial. On the 15-arm Pareto path, practical minus uniINF regret is $-24.69$ before that split and $+211.77$ from the split onward. Unforced neighbor pulls with a correct leader and finite candidate endpoints account for 86.84% of the practical policy's own post-activation regret. Section 6.3 (p. 10) compares three Pareto paths at $T=50{,}000$. Pairs list practical APR-LOCAL first (Table 8). | Arms | Optimal neighbors | Outside the closed neighborhood | |---:|---:|---:| | 15 | 458.37 / 62.80 | 120.45 / 328.94 | | 31 | 448.93 / 63.74 | 136.62 / 761.22 | | 63 | 482.96 / 70.90 | 171.39 / 2495.20 | The extra neighbor cost exceeds savings outside the optimal closed neighborhood at 15 arms. The paired excess is 187.08 [127.07, 245.91] (Appendix K). At 31 and 63 arms the savings cover the extra cost. The paired uniINF-minus-practical differences are 239.41 [179.16, 298.70] and 1911.75 [1844.17, 1984.70] (pointwise 95% intervals over 30 trials, Table 6). **W3(b). Evidence for arm-wise adaptation.** The guarantee permits different $(a_i,M_i)$ across arms, and the proof enters their values individually through each accuracy threshold. The main path comparisons use one reward law per instance. They measure the effect of localization and robust leadership under those laws. The empirical gain attributable specifically to heterogeneity in tail order remains unmeasured in those comparisons.