Selecting k Paths with the Minimum Longest Path Length in the Stochastic Semi-Bandit Setting
Shunsuke Aoki, Atsuyoshi Nakamura
cs.LG
Quick verdict
Proposes SDCB-based k-path min-max semi-bandit method with capacity constraints and DKW regret bounds; sound but loose bounds, exponential oracle limits use.
Summary
This paper studies an online combinatorial semi-bandit problem motivated by parallel data transmission: each round a player selects k capacity-feasible paths from source to sink in a directed multigraph and observes stochastic traversal times for each traversed edge, seeking to minimize the expected maximum path time among the k selected paths. Since this bottleneck objective depends on the full shape of the edge time distributions rather than only their means, mean-based CUCB methods are fundamentally mismatched. The authors propose SDCB-MMLP, which maintains per-edge empirical CDFs, forms stochastically dominant optimistic distributions using DKW-inequality confidence widths, and plays the path set minimizing the expected bottleneck under the optimistic model, following the SDCB framework of Chen et al. (2016). They prove a distribution-dependent regret bound proportional to ā²κ ln n/Δ_min summed over suboptimal edges and a distribution-independent bound of order √(6|E|K̄ n ln n), plus initialization and concentration terms. On a 25-vertex, 40-edge grid graph with k=2 over 250,000 rounds and 20 runs, SDCB-MMLP's regret converges while the CUCB-based CLCB-MMLP grows roughly linearly in many trials; a four-vertex counterexample with equal-mean parallel edges (Table 1: 4963 vs 37 selections) confirms the baseline's failure. Key limitations: the inner optimization uses exhaustive search (NP-hardness conjectured), per-round computation grows linearly in t, and only one synthetic graph and one baseline are evaluated.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
4 strengths · 4 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- The k-path min-max path selection problem with edge capacities is a stochastic semi-bandit problem whose optimal action depends on the full shape of edge reward distributions, not merely their means, so CUCB-style mean-based optimism is fundamentally mismatched (Secs. 1, 6.4).
- SDCB-MMLP, which plays the feasible path set minimizing the expected bottleneck under DKW-based stochastically dominant optimistic distributions, achieves distribution-dependent regret Σ_{i∈Ebad} 534ā²κ ln n/Δ_i,min and distribution-independent regret (1+√2)√(6|E|K̄ n ln n) plus lower-order terms (Lemma 5.1, Theorem 5.3).
- There exist graphs where CUCB-based methods provably cannot learn the optimal path set because equal-mean edges have different distributions; the 4-vertex example of Sec. 6.4 with Table 1 demonstrates this empirically (selection split 2510/2490 vs 4963/37).
- In grid-graph experiments (|V|=25, |E|=40, k=2, 250,000 rounds, 20 runs), SDCB-MMLP's regret converges while the CUCB-based CLCB-MMLP does not converge and grows roughly linearly in many trials (Sec. 6.3).
Strengths
Novel, well-motivated problem formulation
Section 1 and Fig. 1 articulate why minimizing summed path time differs from minimizing the longest path; the capacity-constrained k-path bottleneck semi-bandit setting (Sec. 3) extends Gai et al.'s linear-reward formulation to distribution-shape-dependent objectives.
Sound adaptation of SDCB theory to a nonlinear objective
Lemma A.3's tail-integral identity (via Fubini–Tonelli) and Lemma A.4's hybrid argument, bounding the objective shift under per-edge stochastic dominance by Σ_i ai(p)Λi, correctly extend dominance-based optimism to an expected-max objective, yielding Lemma 5.1 and Theorem 5.3 via DKW concentration.
Decisive, quantified counterexample against mean-based baselines
Honest limitations discussion
Weaknesses
Exponential-time inner optimization
Loose bounds, no lower bound
Narrow empirical evidence
Questionable independence assumption
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper formulates a new stochastic combinatorial semi-bandit problem motivated by parallel data transmission (Sections 1, 3): each round the player selects k cycle-free source-to-sink paths in a directed multigraph with per-edge capacities ai(p) ≤ ui, observes a random traversal time per traversed edge, and suffers the maximum of the k path times. Central claims: (i) the bottleneck objective r_D(p)=E[max_j Σ_{i∈pj} X_ij] depends on the full shape of edge time distributions, not just means, so mean-based CUCB optimism is fundamentally mismatched (Fig. 1 motivation; Sec. 6.4 counterexample); (ii) SDCB-MMLP, built on the SDCB policy of Chen et al. (2016), attains a distribution-dependent regret bound Σ_{i∈Ebad} 534ā²κ ln n/Δ_i,min and a distribution-independent bound (1+√2)√(6|E|K̄ n ln n)+(π²ā/3+1)K|E| (Lemma 5.1, Theorem 5.3); (iii) simulations show SDCB-MMLP converging while a CUCB-based baseline, CLCB-MMLP, fails to converge (Sec. 6).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 4 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What problem does the SDCB-MMLP algorithm solve?
It solves an online routing problem: every round, an algorithm must pick k paths from a source to a sink in a directed graph with per-edge capacity limits, learns from observed random edge traversal times, and tries to minimize the expected time of the slowest selected path (a bottleneck objective). The key twist is that the best choice can depend on the shapes of the edge time distributions, not just their averages.
Why do mean-based bandit algorithms like CUCB fail on this min-max path problem?
Because the expected maximum of random path times is not determined by the edge means. The paper gives a 4-vertex example where two parallel edges have identical means (both equal to 1) but different distributions; the optimal choice is the constant edge, yet CUCB, which only estimates means, cannot distinguish them and keeps switching — in Table 1 its selections split 2510 vs 2490, while SDCB-MMLP picks the optimal edge 4963 times vs 37.
What regret guarantees are proven for SDCB-MMLP?
Under i.i.d. edge traversal times bounded in [0,1], the paper proves a distribution-dependent bound of order (534·ā²κ·ln n)/Δ_min summed over suboptimal edges and a distribution-independent bound of order √(6·|E|·K̄·n·ln n), where K̄ is the total length of the k selected paths, plus initialization and concentration-failure terms. No matching lower bound is provided.
Is code available for SDCB-MMLP?
The paper does not mention any code or data release. The experiments are fully synthetic and the algorithm is given in pseudocode, so independent reimplementation is feasible — but note the per-round path optimization is conjectured NP-hard and was solved by exhaustive search, so scaling to large graphs is unclear.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures 1–3 are images: Figure 3's regret curves could not be inspected numerically, so the main experimental claims rest on the text's qualitative description plus Table 1.
- Some math was flattened by extraction: Theorem 5.3(1) prints the Δ_i,min factor multiplicatively while the Appendix A proof concludes the reciprocal — flagged as a likely typography/extraction artifact, not treated as a paper error.
- The peeling sequences (αu, βu) with Σαu/βu < 267 are inherited from Chen et al. (2016) and could not be independently verified here.
- The appendix proofs otherwise appear complete in the extracted text; no obvious truncation of sections.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.