acceptodds
Under review as a conference paper at ICLR 2027

Tree-based Adaptive Block Elimination with Exemplar Sampling for Best Arm Identification

Abstract

We study fixed-budget best-arm identification over a finite set of candidate arms equipped with a metric. The finite action set may be large, making exhaustive arm-level exploration costly even when nearby arms have similar mean rewards. We propose TABLE (Tree-based Adaptive Block Elimination with Exemplar Sampling), which maintains a hierarchical partition of the candidate set, represents each active block by a small set of geometrically selected exemplars, uses top-two posterior sampling to focus exploration on competitive exemplars, and eliminates or refines blocks using confidence evidence. The resulting algorithm trades exhaustive arm-level sampling for a combination of statistical uncertainty and geometric approximation error. We provide a structured certification analysis that makes this trade-off explicit. Under valid adaptive confidence radii, a representability condition, and stated progress and terminal-state conditions, TABLE safely preserves the optimal block and identifies the best arm once statistical and geometric uncertainty fall below the global arm gap. For sub-Gaussian rewards, we give an implementable fixed-parameter confidence calibration and an oracle exponential expression for the error probability intersected with the favorable trajectory event; the unconditional bound retains the probability of its complement. Experiments on Bernoulli metric bandit and a structured dynamic-pricing benchmark show that TABLE is especially effective in low- and moderate-budget regimes.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Multi-Armed Bandits, Best Arm Identification, Pure Exploration, Limited Budget, Sequential Learning, Online Learning

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_3RE5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper proposes TABLE, a metric-aware best-arm identification algorithm that exploits the Lipschitz structure of the reward function to reduce sampling effort. It groups arms into nodes, selects representative exemplars, and combines posterior-guided exploration, balanced sampling, confidence-based block elimination, and adaptive node splitting. The theoretical analysis establishes safe elimination of the node containing the optimal arm under a simultaneous confidence event and provides a finite-horizon exact-identification bound under additional structural and trajectory conditions. However, the validation of the overall identification guarantee remains incomplete, as the probability of failure of the required progress and terminal conditions is not generally bounded, limiting the strength of the unconditional guarantee.

Critical strengths
  1. The paper develops a principled approach to best-arm identification that leverages Lipschitz continuity and representative arms to eliminate entire groups of arms rather than evaluating each arm independently. This is a meaningful contribution because it exploits the metric structure of the problem to potentially improve sampling efficiency.

  2. The theoretical analysis separates safe block elimination (Prop 4) from exact identification and explicitly states the additional structural and trajectory conditions required for the latter. This transparency strengthens the analysis by avoiding overstated claims and clarifying the limitations of the proposed guarantees.

Critical weaknesses

As stated before, my major concern is that the misidentification bound depends on an additional trajectory event C_T, whose failure probability is not bounded under general conditions. Although the paper establishes safe block elimination, it does not demonstrate that the required progress and terminal conditions hold with high probability under the proposed algorithm. This limits the strength of the main theoretical guarantee.

Questions for authors
  1. What is the practical value of the finite-horizon certificate when the probability of satisfying its additional conditions is unknown?

  2. What happens when the optimal node survives but repeatedly fails the splitting eligibility conditions? I ask this because I have a confusion about the relation of the two events: (1) the event that optimal group is never eliminated and (2) the optimal arm is recommended.

  3. If a simpler confidence-radius condition is sufficient for correct arm identification once the optimal arm is a surviving exemplar, why does Theorem 5 require the stronger gap condition involving the additional geometric term?

  4. A minor question out of curiosity: What happens to the guarantee in the limiting case where all arms must be represented individually?

1 comment
AuthorsOpenReview ↗

Response to the Review by Reviewer 3RE5

CW1

The distinction between block-certification validity and adaptive-trajectory guarantees is central to our theoretical contribution and is explicitly acknowledged in the paper. What we prove is under valid confidence intervals and Lipschitz continuity, TABLE establishes LCSu≤μ⋆(u)≤UCSu,LCS_u\leq\mu^\star(u)\leq UCS_u, ensuring that the optimal block is preserved on the confidence event, without requiring exhaustive arm-level sampling.`

We explicitly state Pr⁡(a^T≠a⋆)≤δ+Pr⁡(CTc),\Pr(\hat a_T\neq a^\star) \leq\delta+\Pr(\mathcal C_T^c), rather than claiming an unconditional identification guarantee. Bounding Pr⁡(CTc)\Pr(\mathcal C_T^c) requires additional assumptions on optimal-arm representation, split activation, adaptive allocation, and terminal sampling.

We strengthened the experiments with execution diagnostics covering refinement, elimination, persistent representation, ladder balance, and terminal sampling (In appendix). These results provide additional insight into TABLE's actual trajectories, although they do not establish bound on CT\mathcal C_T. We acknowledge that controlling the trajectory-failure probability would strengthen the identification theorem. However, this is a limitation explicitly identified by the paper, not a flaw in the block-certification result it proves. We respectfully ask that the established theoretical contribution be assessed within its stated scope.

Q1) The practical value of finite-horizon certificate is that it establishes precisely when exemplar-based block elimination can guarantee correct identification without exhaustively sampling every arm.

 1) It provides a rigorous certification mechanism: under valid confidence intervals and Lipschitz continuity, block-level bounds preserve the optimal block, independently of the additional trajectory conditions.

2) It identifies explicit, verifiable sufficient conditions on optimal-arm representation, sampling precision, and refinement. This separates statistical uncertainty from geometric approximation and clarifies which aspects of the adaptive trajectory require further control.

Q2) Survival of the optimal block and recommendation of the optimal arm are distinct guarantees.

1) Optimal-block survival: Under valid confidence intervals and Lipschitz continuity, TABLE's block bounds ensure that the block containing optimal arm is never incorrectly eliminated. This guarantee does not depend on whether the block satisfies the splitting criterion.

2) Repeated failure to split: If the optimal block remains geometrically coarse and repeatedly fails splitting eligibility, it may survive without ever selecting optimal arm as an exemplar. Thus, preserving the optimal block does not automatically imply identifying the optimal arm.

3) Correct recommendation: Exact identification additionally requires optimal arm to become a surviving exemplar and to be sufficiently sampled. Appendix B.4 establishes it.

Q3) Theorem 5 and Appendix B.4 establish two different guarantees, which explains the difference in their gap conditions.

 Theorem 5 - block-level certification: The theorem establishes the stronger guarantee of eliminating all suboptimal blocks. Its condition accounts for both statistical uncertainty and geometric approximation error, since an entire block is certified using only its exemplars.
 Appendix B.4 - correct final recommendation: Once optimal arm is a surviving exemplar and all surviving exemplars are sufficiently sampled, the recommendation compares empirical arm means directly. The geometric correction is therefore unnecessary, and the condition in B.4 suffices for correct identification on the confidence event.

The distinction is fundamental: certifying an entire block requires controlling geometric approximation error; selecting the best among sufficiently sampled surviving exemplars does not. The stronger condition in Theorem 5 is required for its stronger block-elimination conclusion, not because exact recommendation inherently requires the additional geometric term.

Q4) When every arm is individually represented, TABLE's guarantee reduces to the standard arm-level confidence-based identification setting.

1) Geometric approximation disappears. If every arm is an exemplar, the covering error is zero. Consequently, the block confidence scores reduce to LCSu=max⁡a∈C(u)(μ^a−ra),UCSu=max⁡a∈C(u)(μ^a+ra).LCS_u=\max_{a\in\mathcal C(u)}(\widehat\mu_a-r_a),\quad UCS_u=\max_{a\in\mathcal C(u)}(\widehat\mu_a+r_a).

2) Safe elimination remains valid. Under simultaneous confidence coverage, the optimal block is still preserved. No Lipschitz approximation is needed, since every arm is directly observed.

3) Identification requires only statistical precision. Once all surviving arms are sufficiently sampled, the recommendation-only condition Δmin⁡>2rT(δ)\Delta_{\min}>2r_T(\delta) suffices for exact identification on the confidence event.

In limiting case, TABLE naturally recovers arm-level confidence-based identification.

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

The paper studies fixed-budget best-arm identification over a finite metric arm set with a known Lipschitz constant. TABLE maintains a tree of active blocks, represents each block by at most bb geometrically chosen exemplars, samples active exemplars using a one-draw top-two rule plus a least-sampled balancing mode, and eliminates or splits blocks using exemplar confidence intervals enlarged by Lκ(u)rds⁡(u)L\kappa(u)\operatorname{rds}(u).

The theory first proves that these block scores are valid on a simultaneous confidence event, so the block containing the best arm is not eliminated. Exact identification is then proved on an additional event CT\mathcal C_T that requires persistent representation of the best arm, enough optimal-path refinement, no late splits, enough final samples, and a terminal geometric stopping condition. The experiments compare TABLE with SH, SR, VBR, SBE, and TBE on a Bernoulli metric instance and a simulated pricing task.

Critical strengths
  1. The block certificate is simple and useful. Given valid exemplar confidence intervals and a valid Lipschitz upper bound LL, the term Lκ(u)rds⁡(u)L\kappa(u)\operatorname{rds}(u) transfers an exemplar bound to the whole block. This can protect the optimal block even before the best arm inside that block has been sampled.

  2. The paper is careful about the scope of its theorem. It keeps the Pr⁡(CTc)\Pr(\mathcal{C}_T^c) term in the unconditional statement and does not claim that the sampling rule automatically satisfies the representation, progress, and terminal conditions. That restraint makes the limit of the result easy to see.

Critical weaknesses

1. The fixed-horizon result does not yet analyze the adaptive-refinement behavior of TABLE.

The hard algorithmic steps are placed inside CT\mathcal{C}_T, and the default parameters make this issue concrete. With c0=16c_0=16, H=3H=3, b=3b=3, and ladder base 10, Umax⁡=128U_{\max}=128. For any Mrep≥1M_{\mathrm{rep}}\ge 1, the paper's representation envelope satisfies

Trep≥1+2Umax⁡b(10)=7681,T_{\mathrm{rep}} \ge 1+2U_{\max}b(10) = 7681,

even before adding the nonnegative qjq_j terms. The largest main-curve budget is 7500. Thus the main theorem can cover the reported default configurations only through Mrep=0M_{\mathrm{rep}}=0, meaning that a⋆a^\star is already an initial exemplar. In that case the paper defines Trep=1T_{\mathrm{rep}}=1, while CT\mathcal{C}_T requires no regular geometric split after TrepT_{\mathrm{rep}}. The main theorem therefore does not cover a reported run that actually uses later tree refinement.

The recommendation-only proposition removes the no-split condition, but the displayed sub-Gaussian calibration is still non-informative at the largest Bernoulli budget. At T=3000T=3000,

sT≤⌊29992(128)(3)⌋=3.s_T \le \left\lfloor \frac{2999}{2(128)(3)} \right\rfloor = 3.

Even taking the favorable choice Mconf=1M_{\mathrm{conf}}=1 and the Bernoulli proxy σ2=1/4\sigma^2=1/4, the paper's radius gives rT≥1.396r_T\ge 1.396. Proposition 21 would then require Δmin⁡>2.792\Delta_{\min}>2.792, which is impossible for Bernoulli means in [0,1][0,1]. This does not show that TABLE fails. It shows that the calibrated bound currently proved in the paper does not explain the reported Bernoulli results.

2. The pricing experiment does not have a matching validity argument for its elimination rule, and the source of the empirical gain is not isolated.

The pricing observations contain an unbounded LogNormal factor, while the implementation uses an empirical-Bernstein-style radius whose exact formula, small-count handling, and correction over adaptive checks are not stated. The paper itself notes that standard bounded empirical-Bernstein coverage and pathwise monotonicity do not follow in this setting. The implementation also sets L=1L=1 as an arbitrary value. Unless the action metric or revenue was normalized in an unreported way, this is difficult to reconcile with raw batch revenue from 500 customers. If LL is too small, the block upper score need not contain the block optimum, and the safe-elimination proof no longer applies.

The experiments also do not report how often the events used in the theorem occur or isolate the parts that appear new. This matters because TBE/ReBEl already has recursive confidence-based block elimination, zooming, and top-two variants. CluE also uses clustered Thompson sampling, confidence-based block elimination, and a top-two extension under a limited budget. FWS is in the fixed-confidence setting, so I would not require it as a fixed-budget baseline, but it is still an important reference for finite-arm Lipschitz BAI. My reading is that TABLE's main new element is the multi-exemplar Lipschitz block certificate. The current sensitivity plots do not show how much of the empirical gain comes from that element.

Questions for authors
  1. Can the authors give a non-empty guarantee for any reported default configuration that permits at least one post-initial optimal-path split? If the calculation above is incorrect, please identify the incorrect step. Otherwise, please report how often a⋆a^\star is already an initial exemplar, how often it remains an exemplar after later splits, and how often each component of CT\mathcal{C}_T and CTrec\mathcal{C}_T^{\mathrm{rec}} holds in the experiments.

  2. What exact empirical-Bernstein radius was used in the code, including its treatment of small counts and its correction over possible exemplars and adaptive check times? Were prices, rewards, or distances normalized? Please provide a valid Lipschitz upper bound for the pricing mean under the metric used by the implementation. Results using a valid time-uniform radius and a justified LL would change my assessment.

  3. Please explain the contribution relative to TBE/ReBEl, CluE, and FWS. I would also like to see ablations for one versus multiple exemplars, balancing on versus off, top-two versus uniform or least-count sampling, and fixed blocks versus adaptive splitting. These comparisons would show whether the gain comes from the multi-exemplar certificate or from the surrounding block-search procedure.

2 comments
AuthorsOpenReview ↗

Response to the Review by Reviewer hLFF

CW1

The argument conflates worst-case sufficient conditions with TABLE's actual refinement and sampling behavior. We clarify two points. 1) 7681 is not TABLE's actual sampling requirement. Your calculation uses the full-tree maximum Umax⁡=128U_{\max}=128 blocks and 384384 exemplars. TABLE starts with only 16 blocks and at most 48 exemplars. Moreover, the stated ladder nm=10⋅22mn_m=10\cdot2^{2^m} gives a first threshold of 20, not 10. The initial balancing pull is therefore 960. After one split, TABLE has at most 17 blocks and 51 exemplars, still far below the worst-case maxima. Your calculation characterizes a conservative global certificate, not a minimum budget required for actual refinement or optimal-arm representation. 2) The radius calculation is also conservative. The algorithm begins with only 48 exemplars. Applying the same factor-two accounting to 48 exemplars gives sT=⌊29992(48)⌋=31.s_T=\left\lfloor\frac{2999}{2(48)}\right\rfloor =31. The corresponding radius is 0.434 for Mconf=1M_{conf}=1, or 0.548 when accounting for 1000 arms.

CW2

We have added the pricing calibration and execution-diagnostics concerns in the revised appendix and clarified the scope of our empirical claims.

1) Our implementation assigns infinite radius at n=0n=0, zero empirical variance at n=1n=1, and distributes confidence levels across blocks, depths, ladder stages, and exemplars. We have derived a valid upper bound for the raw 500-customer MNL revenue model: $ L\le500\left(1+\frac{70}{4}\sqrt{0.18^2+0.06^2}\right)<2161.$ We have added a new pricing experiment using L=2161 in Appendix C.4, We also report the budgets where the more conservative setting performs worse. We do not claim that correcting LL alone certifies the original confidence procedure. 2) TABLE's distinguishing theoretical contribution is its multi-exemplar Lipschitz block certificate, combining geometric exemplar coverage with confidence-based certification of entire blocks. Figure 2 examines the relevant representation parameters, while the new appendix provides additional trajectory-level evidence.

Q1) Please see the answer to CW1 and CW2.

Q2) We used $r_{\mathrm{impl}}= \left[\sqrt{\frac{2\widehat v\log(3/\alpha)}{n}}+\frac{3(R_{\max}-R_{\min})\log(3/\alpha)}{n} \right]$. This heuristic does not establish time-uniform coverage across repeated adaptive checks. The prices, rewards, and geometric distances are unnormalized. For the raw 500-customer MNL revenue model, we derive L≤500(1+7040.182+0.062)<2161.L\le500\left(1+\frac{70}{4}\sqrt{0.18^2+0.06^2}\right)<2161. We have rerun the pricing benchmark with the justified value (L=2161) and included the results in the revised appendix. The new experiment provides a separate time-uniform confidence procedure using reward clipping and explicit LogNormal tail-bias correction.

Q3) TABLE's primary novelty is the multi-exemplar Lipschitz block-certification mechanism, not recursive partitioning, Thompson sampling, or top-two exploration individually.

Unlike the mechanisms emphasised in TBE/ReBEl and CluE, TABLE explicitly combines geometrically selected exemplars, their covering error κ(u)rds⁡(u)\kappa(u)\operatorname{rds}(u), and Lipschitz-corrected confidence bounds to certify entire blocks without sampling every arm. Most importantly, none of these approaches provide theoretical validation. As you mentioned, FWS is relevant to finite-arm Lipschitz best-arm identification but addresses the fixed-confidence rather than fixed-budget setting.

Regarding ablations, Figure 2 examines the effects of exemplar count bb and initial partition size c0c_0. We have further strengthened the revised appendix with refinement, elimination, persistent-representation, and terminal-sampling diagnostics. We acknowledge that these diagnostics do not replace controlled component-wise ablations, and we do not claim that the individual contributions have been causally isolated. Our theoretical contribution establishes the multi-exemplar certificate, while the reported experiments evaluate the combined TABLE algorithm.

Thank you for the detailed response and additional experiments. I appreciate the effort to address my concerns.

I agree that my earlier calculation reflects a conservative theoretical bound rather than TABLE's actual refinement cost. However, under the stated theorem, Trep≥15,361T_{\mathrm{rep}}\geq 15,361 when Mrep≥1M_{\mathrm{rep}}\geq1, still exceeding the experimental budgets. I remain concerned that the current guarantee does not meaningfully explain the observed performance.

I also appreciate the corrected pricing experiment with L=2161L=2161 and the new diagnostics. However, the time-uniform confidence procedure is still not fully specified in the revised manuscript, and persistent optimal-arm representation remains very low (0.5–6%).

Overall, while I appreciate the improvements and feel more positive about the paper after the rebuttal, my main concerns remain unresolved, so I will maintain my rating at Weak Reject.

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

This paper studies fixed-budget best-arm identification over a finite set of arms with a known metric and Lipschitz mean rewards. The proposed algorithm, TABLE, maintains a hierarchical partition of the candidate set and represents each active block using a small set of geometrically selected exemplar arms. Sampling combines initialization, minimum-count balancing, and a one-draw top-two posterior sampling heuristic. At designated checks, exemplar confidence intervals are extended to block-level bounds using a Lipschitz covering term. Blocks are then eliminated or refined, and the final recommendation is the empirically best surviving exemplar.

The analysis establishes safe block elimination under valid adaptive confidence intervals. Exact identification additionally requires persistent representability, refinement progress, and terminal sampling and geometry conditions. The resulting error bound retains the probability that these execution conditions fail. Experiments on Bernoulli metric bandits and a simulated dynamic-pricing task report competitive identification accuracy, particularly at low budgets.

Critical strengths

The exemplar-cover construction gives a principled way to certify unsampled arms. Combining exemplar confidence intervals with the covering allowance Lκ(u)rds(u)L\kappa(u)r_{\mathrm{ds}}(u) yields valid bounds on a block’s maximum mean under the stated assumptions. This supports whole-block elimination without requiring observations from every contained arm. The mechanism addresses a relevant difficulty when the candidate set is large relative to the sampling budget.

The empirical results are encouraging, and the theoretical claims are carefully qualified. TABLE achieves the lowest reported point estimates at four of five Bernoulli budgets and all five pricing budgets, with 200 repetitions per configuration. The paper explicitly distinguishes the guarantees derived from confidence validity from additional execution conditions, and retains the unresolved trajectory-failure term in its unconditional statement. This makes the scope of the contribution easier to assess.

Critical weaknesses

The main identification theorem leaves the central algorithmic difficulty unresolved and does not explain the reported budget regime. The guarantee Pr⁡(a^T≠a⋆)≤δ+Pr⁡(CTc)\Pr(\hat a_T\neq a^\star)\leq \delta+\Pr(C_T^c) requires representability and favorable refinement and terminal behavior, but the paper does not bound Pr⁡(CTc)\Pr(C_T^c) for the proposed algorithm on a substantive class of metric instances. These conditions encompass much of the difficulty of ensuring that exemplar-based exploration actually finds the best arm.

The gap is concrete under the default settings. With (c_0=16), (H=3), (b=3), and (n_0=10), any representation path requiring at least one split has Trep≥1+2(16⋅23)⋅3⋅10=7681T_{\mathrm{rep}}\geq 1+2(16\cdot 2^3)\cdot 3\cdot 10=7681 even before adding the nonnegative progress allowances. This exceeds the largest main-curve budgets of 3000 and 7500. Consequently, the stated theorem cannot certify those runs through this envelope when the optimum requires refinement to become persistently represented. This is a limitation of the certificate, not a lower bound on the algorithm’s actual identification time.

Appendix B.4 provides a weaker recommendation-only condition, but its representation and sampling event also lacks a probability bound. Thus, the analysis offers a useful sufficient-condition framework without yet demonstrating a quantitative identification advantage from the proposed allocation and refinement mechanism.

The experiments do not sufficiently isolate the contribution beyond recursive block elimination or connect the gains to valid certification. The closely related TBE/ReBEl work already includes recursive partitioning, posterior-guided exploration, and a top-two variant. TABLE’s distinguishing elements therefore require controlled evaluation of exemplar coverage, geometric correction, and sampling/refinement control. Figure 2 varies the initial block count and exemplar count, but does not isolate the effects of balancing, top-two sampling, or adaptive refinement. The available comparisons consequently provide limited evidence about which new component produces the improvement.

Moreover, the experiments use an empirical-Bernstein-style radius whose adaptive coverage and required monotonicity are not established. The pricing rewards are unbounded because of multiplicative LogNormal noise, and (L=1) is explicitly described as an arbitrary implementation choice. The pricing results therefore demonstrate empirical performance without validating the assumptions supporting safe elimination. Exact low-budget adaptations of the arm-level baselines are also insufficiently specified for a fully reproducible comparison. Together, these issues limit both attribution of the gains and the connection between the experimental and theoretical contributions.

Questions for authors

Applicability of the guarantee. Can the authors provide a substantially tighter representation/progress analysis for the default settings, or identify a nontrivial metric instance class for which the actual algorithm satisfies the required conditions with a controlled failure probability? For the reported experiments, how often does the optimal arm become a persistent exemplar, at what sampling time, and how often are the terminal sampling conditions satisfied? These diagnostics would clarify whether the theoretical mechanism explains the observed performance.

1 comment
AuthorsOpenReview ↗

Response to the Review by Reviewer b46Y

CW1

The comment overlooks the distinction between block certification and adaptive-trajectory guarantees. Our paper proves that exemplar-level confidence intervals yield valid block-level certificates: LCSu≤μ⋆(u)≤UCSu,LCS_u\leq\mu^\star(u)\leq UCS_u, ensuring that the optimal block is preserved on the confidence event.

Bounding Pr⁡(CTc)\Pr(\mathcal C_T^c) is a separate challenge requiring additional assumptions and guarantees for optimal-arm representation, split activation, adaptive allocation, and terminal sampling. These properties do not follow from Lipschitz continuity alone.

Crucially, this limitation is explicitly acknowledged in the Introduction, theoretical discussion, and main theorem. We do not claim an unconditional allocation guarantee. The review identifies an important extension, but it does not undermine the validity of the block-certification result actually established.

CW2

The reviewer's calculation demonstrates the conservatism of our worst-case certificate, not TABLE's actual sampling requirements. The calculation uses a 128 blocks and 384 exemplars. However, TABLE starts with only 16 blocks and at most 48 exemplars. Under the stated ladder, the first threshold is 20, requiring at most 16×3×20=96016\times3\times20=960 balancing pulls. After one split, there are at most 17 active blocks and 51 exemplars, still far below the global maxima.

Thus, 7681 is not a lower bound on TABLE's actual refinement or representation time. We acknowledge that the current global theorem does not certify a post-initial optimal-path split within the reported budgets. Establishing that stronger guarantee requires further trajectory analysis; it does not follow from the worst-case accounting alone.

CW3

Appendix B.4 establishes a stronger recommendation result than the review's interpretation suggests. The main theorem requires Δmin⁡>2(2+ηκˉ)rT(δ),\Delta_{\min}>2(2+\eta\bar\kappa)r_T(\delta), whereas B.4 shows that Δmin⁡>2rT(δ)\Delta_{\min}>2r_T(\delta) suffices for correct recommendation when the optimum is represented and all surviving exemplars are sufficiently sampled. This removes the stronger terminal geometric requirement without requiring complete elimination of suboptimal blocks. It does not establish a probability bound for representation or a superior allocation exponent, neither of which we claim. Our contribution is a valid block-certification mechanism and sharper sufficient conditions for identification, while the allocation mechanism is evaluated empirically.

CW4

TABLE's novelty is the multi-exemplar Lipschitz block certificate, not recursive partitioning or posterior sampling in isolation. TABLE combines geometrically selected exemplars, an explicit covering correction κ(u)rds⁡(u)\kappa(u)\operatorname{rds}(u), and confidence-based block elimination without exhaustive arm-level sampling. Figure 2 directly examines the representation parameters b and c0c_0, characterizing exemplar coverage, sampling cost, and initial geometric resolution.

We have further strengthened the empirical analysis in the revised appendix, adding Lipschitz-corrected pricing results and execution diagnostics, including mean splits, eliminations and persistent optimal-exemplar representation etc. These results provide additional insight into TABLE's refinement mechanism. We do not claim these results alone establish component-level causality; the reported performance concerns the combined algorithm.

CW5

The original pricing benchmark was presented as an empirical application, not as verification of theoretically safe elimination. This distinction is explicitly stated in the manuscript. To address the reviewer's concern, we have added a Lipschitz-corrected pricing evaluation. We report the resulting identification performance and additional refinement diagnostics in the appendix. We have also included the source code. These additions directly address the concerns about geometric calibration, execution behavior, and implementation transparency.

Q1

A stronger representation/progress guarantee requires assumptions beyond Lipschitz continuity. Specifically, controlling Pr⁡(CTc)\Pr(\mathcal C_T^c) requires quantitative guarantees for optimal-path splitting, persistent representation, adaptive allocation, and terminal sampling.

Our paper deliberately considers general finite metric spaces and explicitly identifies these requirements. Hierarchically well-separated instances with small local covering numbers are promising candidates for stronger results, but we do not claim a controlled trajectory-failure probability without additional analysis.

The revised appendix now includes execution diagnostics. Finally, the theoretical conditions are sufficient, not necessary, for successful identification. Their failure does not imply incorrect recommendation. Our paper establishes rigorous multi-exemplar block certification under explicit assumptions, while a general high-probability characterization is a future work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.