acceptodds
Under review as a conference paper at ICLR 2027

Constant-Rank Confidence Amplification for Parameter-Free Heavy-Tailed Graph-Unimodal Bandits

Abstract

We study stochastic graph-unimodal bandits with arm-wise symmetric rewards and unknown finite centered -th moments. Fixed-sample coverage alone does not control the decision cost of adaptive cache reuse, so we charge each fixed-prefix failure by the maximum number of decisions its cached endpoint can govern. Amplified prefix reuse with localization (\algname) pairs constant-rank resampled-median-of-means (RMM) endpoints with dyadic median-of-means (MoM) leader scores; independent-base amplification makes the confidence dependence logarithmic, and prefix–epoch budgets keep the expected total bad-cache decision charge finite. The charge bounds suboptimal local choices in the leader's own clock, and periodic leader pulls with summable MoM score tails make suboptimal-leader occurrences finite in expectation. Both the certified and practical settings attain expected regret plus a finite term. Under a global clock, \globalalg attains the all-arm guarantee, improving the published RMM-UCB horizon factor from . A symmetry-preserving Gaussian-subfamily lower bound matches the horizon order and optimal-neighbor support, with equal moment–gap powers at . Across 30 paired trials on two infinite-variance path instances, matched comparisons place most of the certified–practical regret gap before cache activation and show the MoM leader raising the optimal-neighborhood pull share.

Primary area:
reinforcement learning
Keywords:
heavy-tailed bandits, graph-unimodal bandits, parameter-free learning, adaptive confidence reuse, regret analysis

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_tzv3OpenReview ↗
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 log⁡2T\log^2 T to log⁡T\log T. 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
  1. 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.

  2. 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.

  3. 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
  1. The heavy-tail dependence remains potentially loose. For aj<1a_j<1, the upper-bound coefficient Mj1/ajΔj−1/ajM_j^{1/a_j}\Delta_j^{-1/a_j} differs substantially from the Gaussian benchmark Mj2/(1+aj)Δj−1M_j^{2/(1+a_j)}\Delta_j^{-1}. 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.

  2. The finite remainder limits the practical interpretation of localization. The constant CclimbC_{\mathrm{climb}} 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 90,00090{,}000 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.

  3. 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
  1. 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 Δj−1/aj\Delta_j^{-1/a_j} dependence?

  2. Can the ascent proof yield a compact upper bound on CclimbC_{\mathrm{climb}} 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.

  3. 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
AuthorsOpenReview ↗

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)(1+a)-moment envelope MM, Proposition 24 gives a KL information modulus of order Δ2/M2/(1+a)\Delta^2/M^{2/(1+a)}, with a Gaussian pair attaining the order. This suggests a neighbor coefficient of order M2/(1+a)/ΔM^{2/(1+a)}/\Delta for small gaps. The current upper bound uses the raw block-mean radius M1/(1+a)g−a/(1+a)M^{1/(1+a)}g^{-a/(1+a)}. For each g≥2g\ge2, put mass 1/(2g)1/(2g) at each of ±(Mg)1/(1+a)\pm(Mg)^{1/(1+a)} and the remaining mass at zero. The moment is MM. With probability (1−1/g)g−1≥e−1(1-1/g)^{g-1}\ge e^{-1} there is exactly one nonzero observation, so the block mean has absolute error M1/(1+a)g−a/(1+a)M^{1/(1+a)}g^{-a/(1+a)}. Requiring this radius to be of order Δ\Delta and multiplying the sample count by Δ\Delta gives the heavier Δ−1/a\Delta^{-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 ii 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.

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.

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

This paper studies graph-unimodal bandits with symmetric heavy-tailed rewards, where the tail exponents and moment bounds are unknown. The proposed APR-LOCAL algorithm combines amplified constant-rank RMM confidence bounds with cached estimates and a robust median-of-means leader. The analysis accounts for repeated use of each cached bound and establishes that suboptimal leaders occur only finitely often in expectation. This yields O(log⁡T)O(\log T) expected regret whose growing term involves only the optimal arm’s neighbors. The global variant, APR-UCB, improves the published RMM-UCB regret bound from log⁡2T\log^2 T to log⁡T\log T, without requiring knowledge of the tail parameters or horizon.

Critical strengths
  1. The treatment of adaptive cache reuse is interesting. Fixed sample coverage alone does not control the regret caused by repeatedly using an erroneous confidence bound. The authors address this by weighting failures by their maximum reuse counts and deriving a pathwise selection bound that remains valid at random leader counts. The subsequent ascent argument also explains why a leader-local clock is needed.

  2. The theoretical method combines adaptation to unknown tail parameters with neighbor-localized logarithmic regret. The general ascent proposition separates the requirements on confidence bounds from those on leader scores, making the argument easier to follow and potentially useful beyond this particular construction. The practical configuration is also covered by a separate proof, so the main experimental algorithm has a corresponding theoretical guarantee.

  3. The experiments help explain the algorithm’s behavior. Paired trials, leader ablations, matched-budget comparisons, and cache-activation measurements provide evidence about where the performance differences arise. The paper also reports settings where a baseline performs better, which gives a more informative picture of the method’s strengths and limitations.

Critical weaknesses
  1. The upper and lower bounds do not match in their dependence on the moment parameters and gaps when aj<1a_j<1. The Gaussian-subfamily lower bound establishes the logarithmic horizon dependence and the need to explore optimal arm neighbors, but leaves a substantial gap between Mj2/(1+aj)Δj−1M_j^{2/(1+a_j)}\Delta_j^{-1} and the upper bound coefficient Mj1/ajΔj−1/ajM_j^{1/a_j}\Delta_j^{-1/a_j}. The paper acknowledges this gap, yet it remains unclear whether it reflects a limitation of the algorithm, the analysis, or the lower-bound construction.

  2. I view the improvement from log⁡2T\log^2 T to log⁡T\log T as useful but relatively modest on its own. For assessing the strength of a heavy-tailed bandit guarantee, I would place more weight on the dependence on gaps, moment bounds, and tail exponents, as well as the size of the finite remainder. These dependencies can be more consequential than an additional logarithmic factor. Since the moment gap powers remain unchanged relative to RMM-UCB, the significance of the rate improvement needs a stronger discussion.

  3. The CclimbC_{\rm climb} term needs a more informative explanation. The proof establishes its finiteness and notes that it can depend on the full graph and instance, but does not make its magnitude easy to assess. In particular, its dependence on the number of arms, local gaps, and moment parameters matters for understanding when the neighbor-localized logarithmic term becomes dominant. Without such a characterization, the finite horizon implications of the localization result remain difficult to judge.

  4. I am not yet convinced that the graph extension provides substantial additional novelty. Neighbor-localized exploration is already a central feature of OSUB, so obtaining a similar qualitative result after imposing graph unimodality is reasonably expected. The cache-reuse accounting and robust-ascent argument contain technical work, but the paper should distinguish more clearly which steps require new ideas and which follow from adapting existing RMM and OSUB machinery.

  5. The introduction is too compressed in its explanation of the motivation and contributions. It moves quickly into the technical mechanisms without giving enough context for why this particular combination of assumptions is important or what the main conceptual advance is. A clearer account of the research gap, the relationship to existing results, and the significance of the guarantees would make the paper easier to assess. There is considerable room to improve the presentation here.

Questions for authors
  1. Can the authors outline a plausible route to closing the upper–lower bound gap for aj<1a_j<1? In particular, would a matching lower bound require a different family of symmetric hard instances, or do the authors expect that the upper bound can be improved? A discussion or detailed proof of the likely optimal moment–gap dependence and the main obstacle would be helpful.

  2. Can the authors make the dependence of CclimbC_{\rm climb} on the instance parameters more explicit? A bound in terms of graph size, degree, local gaps, and moment parameters would help explain the size of the term.

  3. Could the authors articulate the paper’s main novelty and contributions more clearly, particularly relative to RMM-UCB and existing graph-unimodal bandit methods? Beyond removing one logarithmic factor, what new algorithmic or theoretical insights does the paper provide, and how significant are the gains once the moment–gap dependence and finite-horizon costs are taken into account? A clearer discussion of these points in the introduction would help readers understand the contribution.

I am open to raising my score if the authors satisfactorily address my concerns, particularly the tightness of the bounds and the dependence of CclimbC_{\rm climb} on the problem parameters.

2 comments
AuthorsOpenReview ↗

Response to Reviewer 2mfR: Gap dependence and explicit regret remainder

We thank the reviewer for the helpful comments.

W1 / Q1. Moment and gap dependence. The upper-bound factor Mj1/ajΔj−1/ajM_j^{1/a_j}\Delta_j^{-1/a_j} comes from the accuracy requirement for a raw block mean. For p=1+ap=1+a and block size g≥2g\ge2, put mass 1/(2g)1/(2g) at each of ±(Mg)1/p\pm(Mg)^{1/p} and the remaining mass at zero. The centered pp-th moment is MM. Exactly one nonzero observation occurs with probability (1−1/g)g−1≥e−1(1-1/g)^{g-1}\ge e^{-1} and yields a block-mean deviation of M1/pg−a/pM^{1/p}g^{-a/p}. This gives a matching scale for that proof step. Proposition 24 gives a quadratic KL modulus within the symmetric class at a common moment envelope. Its proof separates nearby centers with a bounded characteristic function. A route to Mj2/(1+aj)/ΔjM_j^{2/(1+a_j)}/\Delta_j is to estimate its phase at a frequency selected without moment inputs. This route requires control of phase ambiguity and fixed-prefix confidence compatible with the cache. The Gaussian lower bound certifies horizon order and neighbor support.

W3 / Q2. Explicit remainder. Page 6 states ERT≤L⋆log⁡T+C‾climb\mathbb E R_T\le L_\star\log T+\overline C_{\mathrm{climb}} for both configurations. Proposition 34 (Appendix N) proves it for T≥KT\ge K, with L⋆=∑j∈N(i⋆)ΔjAj(Δj/2)L_\star=\sum_{j\in\mathcal N(i^\star)}\Delta_j A_j(\Delta_j/2) and

\overline C_{\mathrm{climb}} &=\sum_j\Delta_j+\sum_{i\ne i^\star}\Big(\max_{j\in\mathcal N^+(i)}\Delta_j\Big)C_i\\ &\quad+\sum_{j\in\mathcal N(i^\star)}\Delta_j[B_j(\Delta_j/2;c)+4/c],\\ C_i&=\max\{s_i^{\rm score},s_i^{\rm count}\}-1 +\frac{16}{7}\sum_{h\in\{i\}\cup\mathcal B_i}\frac{2^{-3r_{ih}}}{v_{ih}} +\frac{8|\mathcal D_i|}{\lambda c}. \end{aligned}$$ Here $\mathcal N^+(i)$ is the closed neighborhood, $\mathcal B_i$ its locally best arms, $\mathcal D_i=\mathcal N^+(i)\setminus\mathcal B_i$, $\lambda=\gamma/[2(\gamma+1)]$ for maximum degree $\gamma$, and $c$ is the confidence-budget divisor. The score threshold is $\max_h\lceil2^{r_{ih}}/v_{ih}\rceil$. Its scale is $\max_h V_{ih}\log(eV_{ih})/v_{ih}$ up to a constant, with $V_{ih}=\max\{1,[8M_h/(g_i/4)^{1+a_h}]^{1/a_h}\}$ and $g_i=\max_{j\in\mathcal N(i)}\mu_j-\mu_i$. The fractions are $v_{ii}=1/(\gamma+1)$ and $v_{ih}=\lambda/|\mathcal B_i|$ for $h\in\mathcal B_i$. The count threshold in Eq. (266) uses $A_i^{\rm loc}=\sum_{j\in\mathcal D_i}A_j(\delta_{ij}/2)$ and the corresponding sum $B_i^{\rm loc}$, where $\delta_{ij}$ is the gap from $j$ to the best local mean. Eq. (265) specifies both functions through the group-size requirement at that gap. The threshold is $$s_i^{\rm count}=\left\lceil\frac4\lambda\left[B_i^{\rm loc}+2+ A_i^{\rm loc}\log(4A_i^{\rm loc}/\lambda)\right]\right\rceil.$$ Above the threshold, the deterministic local count plus two is at most $\lambda s/2$. An occurrence with few samples from $\mathcal B_i$ then requires a cache charge $Y_i\ge\lambda s/2$, where $\mathbb E Y_i\le4|\mathcal D_i|/c$ by summing the local error bounds. The remainder includes up to $K-1$ leader charges, with both a difficult local ascent gap and difficult local comparisons contributing. The comparison of $L_\star\log T$ with this remainder concerns the bound. Table 18 separately measures activation. **W2 / Q3. Global horizon improvement.** The global variant uses constant-rank resampled median-of-means (RMM) bases with each tail error bounded by $\beta < 1/2$ at the target group size. A median of independent bases gives $L(p,\beta)=O(\log(1/p))$, with the bases partitioning a single prefix. The certified version uses three sign vectors per observation regardless of confidence level. This reduces the published RMM-UCB horizon factor from $\log^2T$ to $\log T$ with the same moment–gap powers. **W4 / Q3. Graph contribution.** The additional graph step is a pathwise choice-count guarantee at the leader's own clock. At each fixed key the confidence error is weighted by its maximum reuse, and summing those charges bounds inferior local choices at an adaptive leader count (Lemmas 21 and 30). Proposition 22 then combines that count with forced leader pulls and score errors to bound each suboptimal leader's expected count. In the 63-arm Pareto experiment, regret outside the optimal closed neighborhood is 171.39 for practical APR-LOCAL and 2495.20 for uniINF, while optimal-neighbor regret is 482.96 and 70.90 (Table 8). **W5. Motivation and presentation.** Sign resampling uses symmetry for fixed-prefix coverage without moment inputs. The moment condition controls how quickly the endpoint becomes accurate. Graph unimodality makes local improvement possible when the current leader is suboptimal. Appendix N combines fixed-prefix coverage with graph-local improvement through a count of cache-influenced choices. The two thresholds in Eq. (266) distinguish a score comparison from a shortage of samples from better local arms. The endpoint constants give each configuration's score and count thresholds in Eq. (266).

Thank the authors for responding. Their discussion of the moment and gap dependence, including a possible route to improving the tightness, has partially addressed my concern in W1/Q1.

However, I still find the bound on CclimbC_{\text{climb}} difficult to interpret. The revision gives an explicit expression, but it is hard to read how the term depends on basic instance parameters. It is also quite unclear when this term might dominate the main terms in the regret bound. A simplified regret order bound and more discussion in the main text would help. When discussing the tightness of the regret bound, I think the authors should also address how tight the parameter dependence in CclimbC_{\text{climb}} is, since it seems not an instance-independent constant currently.

Furthermore, I believe the paper's presentation still needs improvement, as also raised by reviewer 4n6r. I found the paper difficult to read in many places, and the work should explain the novelty and contributions more clearly.

In the future, I believe the work would benefit greatly from improving the presentation and, more importantly, making the dependence of the regret bounds on the instance parameters clearer instead of leaving some of that dependence buried in the expression for CclimbC_{\text{climb}}. Given these remaining concerns, I would like to keep my score unchanged.

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

This paper studies stochastic graph-unimodal multi-armed bandits with symmetric heavy-tailed rewards, where the tail exponents and moment bounds are unknown. The authors propose APR-LOCAL, a parameter-free and anytime algorithm that combines constant-rank resampled median-of-means (RMM) confidence endpoints, independent-base confidence amplification, dyadic caching, and robust leader estimation.

Critical strengths
  1. The paper addresses a technical challenge in applying fixed-sample robust confidence bounds to sequential decision-making. In particular, the decision-weighted cache analysis accounts for the number of actions influenced by an inaccurate cached endpoint, rather than relying solely on fixed-sample coverage guarantees. The resulting framework provides a principled way to control errors under adaptive cache reuse and is potentially useful beyond the specific RMM construction considered here.
  2. The proposed algorithm achieves logarithmic expected regret without requiring the tail exponents, moment bounds, or time horizon as inputs. Its analysis further establishes that the horizon-dependent regret term involves only the optimal arm's neighbors. The robust ascent argument connecting local selection counts to finite expected suboptimal-leader occurrences is particularly interesting. The accompanying experiments and ablations provide useful evidence about localization, robust leader estimation, and the practical cost of confidence amplification.
Critical weaknesses
  1. The proposed approach combines several established ingredients, including RMM confidence endpoints, median-based confidence amplification, and the leader-based neighborhood exploration strategy of OSUB. Moreover, the Gaussian-subfamily lower bound matches the logarithmic dependence on the horizon and the optimal-neighbor exploration structure, but not the moment-gap dependence of the upper bound when the moment exponent is below two. Consequently, the extent to which the proposed regret guarantee is optimal for the full symmetric heavy-tailed class remains unclear. These issues make it difficult to assess the full significance of the theoretical contribution.
  2. The certified confidence construction requires substantial sample sizes before finite endpoints become available. In several reported configurations, certified endpoints activate only late in the experiment or fail to activate within the evaluated horizon. The experiments also reveal a considerable performance difference between the certified and practical configurations, much of which arises before cache activation. Although the practical configuration is theoretically supported, these observations raise questions about how effectively the proposed confidence-amplification mechanism translates its asymptotic guarantees into useful finite-horizon performance.
  3. The manuscript has a rather AI-generated feel, with overly dense technical descriptions, excessive details, and insufficient explanations of the key ideas. This significantly affects its readability and makes it difficult to identify the main contributions.
Questions for authors
  1. Could the authors clarify which technical components of the adaptive cache-reuse analysis and robust ascent argument cannot be obtained through a more direct combination of existing RMM confidence bounds and the classical OSUB framework?
  2. The Gaussian-subfamily lower bound matches the logarithmic horizon dependence and optimal-neighbor support, but its dependence on the reward gaps differs from the proposed upper bound when the moment exponent is below two. Do the authors have evidence suggesting that this gap is intrinsic to parameter-free learning under symmetry, or might it reflect looseness in the current upper-bound analysis?
3 comments
AuthorsOpenReview ↗

Response to Reviewer 4n6r: Graph extension and finite-time evidence

We thank the reviewer for the helpful comments.

W1(a) / Q1. What the graph extension requires. Resampled median-of-means (RMM) gives a confidence statement at a deterministic sample prefix. Optimal Sampling for Unimodal Bandits (OSUB) supplies the rule for choosing which neighborhood to explore. In our setting the observations used to choose the leader also determine which cached endpoints are queried. If a key has failure probability pp and can govern 2q2^q decisions, its expected bad-decision charge is at most 2qp2^qp. This bound follows by charging the full 2q2^q on every trajectory on which the fixed-prefix event occurs. Eq. (8) pays for these charges over sample epochs rr and leader epochs qq. The calculation uses unconditional coverage of deterministic-prefix events.

The local bound in Lemmas 21 and 30 counts choices of a locally inferior arm up to every realized leader occurrence ss. It consists of a deterministic accuracy threshold of order log⁡s\log s and a random charge with finite mean. Proposition 22 uses this count in both cases of the ascent proof. If the locally best arms have too few observations, a linear number of nonforced choices must have gone to inferior arms, which the local count can sustain only for a finite expected number of occurrences. If the locally best arms have enough observations, a suboptimal leader must have survived a robust score comparison. Forced pulls provide the leader with enough samples for this comparison, and the dyadic median-of-means score errors are summable after weighting by their exposure. This leads to finite expected time at each suboptimal leader, even when the graph has a long ascent path. The growing regret then comes from the optimal neighborhood.

W1(b) / Q2. Source of the gap exponent. The block-mean accuracy radius scales as M1/(1+a)g−a/(1+a)M^{1/(1+a)}g^{-a/(1+a)} for groups of size gg. For g≥2g\ge2, a symmetric law with mass 1/(2g)1/(2g) at each of ±(Mg)1/(1+a)\pm(Mg)^{1/(1+a)} and the remaining mass at zero attains this deviation with probability at least (1−1/g)g−1≥e−1(1-1/g)^{g-1}\ge e^{-1}. This follows when exactly one nonzero observation. Taking gg large enough for accuracy at scale Δ\Delta and charging Δ\Delta per pull produces the factor M1/aΔ−1/aM^{1/a}\Delta^{-1/a}. The example establishes the scale of the block-mean step. For the symmetric class with a common moment envelope, Proposition 24 gives a quadratic KL information modulus for small gaps, with the Gaussian pair realizing the order Δ2/M2/(1+a)\Delta^2/M^{2/(1+a)}. This points to M2/(1+a)/ΔM^{2/(1+a)}/\Delta as a target coefficient. A confidence construction that uses symmetry in estimating the center, while adapting to unknown moments, is the remaining step. The current lower bound establishes the logarithmic horizon dependence and necessary exploration of optimal neighbors.

W2. Activation and finite-horizon evidence. At matched confidence budget pr,qp_{r,q} on the 63-arm Pareto path, Table 7 gives mean pre-activation regret of 831.84 for the certified setting and 118.91 for the practical setting. From their respective first finite endpoints onward the means are 413.01 and 488.75. The practical tuple's lower total is accounted for by the pre-activation difference, with a higher post-activation mean. At degree eight, the certified setting reaches a finite endpoint in 0 of 30 trials through round 90,000, while the median retrospective leader resolution is 4,676 rounds (Table 18). The balanced calculation predicts 147,456 rounds to formation. These are different events from the sufficient accuracy thresholds in Appendix N.

On the 15-arm Pareto path (Section 6.3, p. 10), we split both regret traces at the practical tuple's first finite endpoint in each pair. The mean difference, practical minus uniINF, is −24.69-24.69 before that round and +211.77+211.77 from it onward. With the optimal leader and finite candidate endpoints, unforced neighbor pulls account for 86.84% of practical post-activation regret (Appendix J.6). Savings outside the optimal closed neighborhood cover the extra neighbor cost at 31 and 63 arms. At 15 arms those savings are smaller than the neighbor cost. At 63 arms the paired mean advantage over uniINF is 1911.75 [1844.17, 1984.70] (95% interval, Tables 6 and 8).

W3. Presentation. Appendix N gives a worked cache example and locates the two quantities that the ascent proof needs. A cache failure is charged once for each decision it can influence. Those charges bound the number of choices that can keep a suboptimal leader in place. The two ways that can happen give the score and count terms of Eq. (266). The proof's accuracy radii use moment information to quantify when comparisons become reliable. The policy sets its confidence budget from the two observed epochs and uses no moment inputs. The global log⁡2T\log^2T to log⁡T\log T result uses the same confidence construction on a round clock. The graph proof runs on a leader's own clock because it needs a count that is small relative to that leader's occurrences.

I thank the authors for their detailed response. The clarifications on adaptive cache reuse and robust ascent help address my concerns about the technical novelty. I also appreciate the additional explanation of the regret bounds and finite-horizon experiments.

However, the upper and lower bounds still do not match in their gap dependence for the general heavy-tailed setting, and the substantial activation cost of the certified configuration remains a concern. The response has improved my assessment of the technical contributions, although I remain concerned about the theoretical gap and finite-horizon practicality.

AuthorsOpenReview ↗

follow-up on gap dependence and activation costs

Thank you for identifying and recognizing the contributions of adaptive prefix reuse and robust ascent. We address the two concerns separately.

1. Gap dependence. The upper bound has optimal-neighbor terms of order [Δj+Mj1/ajΔj−1/aj]log⁡T[\Delta_j+M_j^{1/a_j}\Delta_j^{-1/a_j}]\log T. The Gaussian-subfamily lower bound has terms of order Mj2/(1+aj)Δj−1log⁡TM_j^{2/(1+a_j)}\Delta_j^{-1}\log T. The moment-gap powers agree at aj=1a_j=1. For aj<1a_j<1, the result matches the logarithmic horizon order and the required optimal-neighbor exploration.

The power of the exponential term in the upper bound comes from the sample mean within each RMM block. Its upper-lower gap is Mj1/(1+aj)g−aj/(1+aj)M_j^{1/(1+a_j)}g^{-a_j/(1+a_j)} for block size gg. Resolving a gap Δj\Delta_j therefore uses gg of order (Mj/Δj1+aj)1/aj(M_j/\Delta_j^{1+a_j})^{1/a_j} in this argument, giving the regret coefficient Mj1/ajΔj−1/ajM_j^{1/a_j}\Delta_j^{-1/a_j}. The symmetric rare-draw example in Appendix N attains this gap with probability at least e−1e^{-1}. It establishes sharpness of this concentration step. Section 5 and the appendix subsection "Exact upper-lower comparison" distinguish this fact from the scope of the regret lower bound.

The contribution of all aj∈(0,1]a_j\in(0,1] is a parameter-free logarithmic regret guarantee whose growing term involves only optimal-arm neighbors, together with finite expected suboptimal-leader occurrences. The algorithm receives neither the arm-wise moment orders and bounds, nor the gaps.

2. Activation cost and finite-horizon performance. There are three relevant distinctions.

(a) We provide a complete regret proof for the practical configuration. Theorem 32 in Appendix I covers the implemented tuple (m,r0,k,gmin⁡)=(8,1,9,1)(m,r_0,k,g_{\min})=(8,1,9,1) under the same assumptions. We prove a finite-time bound and the same neighbor-local logarithmic rate, for both budget divisors c=1c=1 and c=K(γ+1)c=K(\gamma+1), where γ\gamma is the maximum degree. The latter is our main experimental setting.

The practical base has upper-tail failure probability 7{B9(1/12)+B9(47/256)}<1/87\{B_9(1/12)+B_9(47/256)\}<1/8 once each group has six observations, where Bk(u)=Pr⁡{Bin⁡(k,u)≥(k+1)/2}B_k(u)=\Pr\{\operatorname{Bin}(k,u)\ge(k+1)/2\}. Runtime formation still uses gmin⁡=1g_{\min}=1; selections before the accuracy threshold are included in the deterministic sample-count term of the proof. At a fixed confidence budget pp, finite-endpoint formation needs 63L(p,1/4)63L(p,1/4) observations for the certified tuple and 9L(p,1/8)9L(p,1/8) for the practical tuple, with LL the odd amplification count defined in Section 3. This explains how the practical setting reduces startup while retaining a proved regret guarantee.

(b) A matched-budget experiment isolates the endpoint configuration. Table 7 uses the same budget pr,qp_{r,q} for both configurations, separately from the main practical budget pr,q/[K(γ+1)]p_{r,q}/[K(\gamma+1)]. On the 63-arm path at T=50,000T=50{,}000, the mean regrets over 30 trials are shown below; total entries include 95% Student-tt half-widths:

RewardConfigurationBeforeAfterTotal
ParetoCertified831.84413.011244.85±31.401244.85\pm31.40
ParetoPractical118.91488.75607.66±57.56607.66\pm57.56
Student-ttCertified759.93424.951184.87±14.891184.87\pm14.89
Student-ttPractical99.93402.48502.40±57.31502.40\pm57.31

Column "Before" and "After" split each policy at its own first finite endpoint. The reduction is concentrated before endpoint formation; the Pareto post-formation mean is higher for the practical configuration. The same comparison on 31 arms gives total regrets 1213.41 versus 575.44 (Pareto) and 1151.42 versus 468.10 (Student-tt), certified versus practical.

(c) Certified activation remains a separate finite-horizon cost. In Table 18's degree-eight experiment, the certified configuration forms no finite endpoint by T=90,000T=90{,}000 in any of the 30 trials, although retrospective leader resolution has median 4676. The practical-path results above concern a different configuration and graph family.

Section 4 and Corollary 35 also give the explicit upper bound on the remainder

$ \overline C_{\mathrm{climb}}\le C_{\mathrm{cfg}}(K-1)\Delta_{\max} [dH\log(ecdH)+d^2], $

where d=γ+1d=\gamma+1, Δmax⁡=max⁡jΔj\Delta_{\max}=\max_j\Delta_j, δ\delta is the smallest positive local comparison gap, and

H=max⁡j{h0,⌈(12⋅81+ajMjδ1+aj)1/aj⌉}.H=\max_j\left\lbrace h_0,\left\lceil\left(\frac{12\cdot8^{1+a_j}M_j}{\delta^{1+a_j}}\right)^{1/a_j}\right\rceil\right\rbrace. Here h0=3h_0=3 or 66 for certified or practical, respectively; CcfgC_{\mathrm{cfg}} depends only on fixed endpoint parameters. Appendix N gives its expression in Eq. (273) and the complete proof. Thus the finite term explicitly retains dependence on arm count, degree, gaps, and moments. The practical guarantee and matched-budget measurements provide an alternative with substantially lower startup cost on the tested paths.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.