Selecting k Paths with the Minimum Longest Path Length in the Stochastic Semi-Bandit Setting

Shunsuke Aoki; Atsuyoshi Nakamura

cs.LGSep 13, 2026

Selecting k Paths with the Minimum Longest Path Length in the Stochastic Semi-Bandit Setting

Authors: Shunsuke Aoki, Atsuyoshi Nakamura

Organizations: Graduate School of Information Science and Technology, Hokkaido University Kita 14, Nishi 9, Kita-ku, Sapporo, Hokkaido, 060-0814, Japan

Abstract

When performing parallel data transmission through a network using multiple paths, it is practically important to minimize the maximum transmission time among the selected paths. This study addresses an online problem in which $k$ paths from an origin vertex to a destination vertex must be selected at each time step within a network represented as a directed graph. Here, the number of paths going through each edge in each parallel data transmission is limited to its capacity, and the time required for transmission is determined stochastically. We formulate the semi-bandit problem of selecting a set of paths to minimize the maximum traversal time among the selected paths and propose an algorithm to solve it.

Figures & tables

Panel of Figure 1 — Figure 1: Candidates for the selection of two paths; each edge is labeled with the expected traversal time / capacity (the number of paths that can pass through).

Panel of Figure 2 — Figure 2: The graph used in the experiment.

Panel of Figure 4 — Figure 4: Graph that CLCB-MMLP fails (its source and sink vertices are $0$ and $3$ , respectively). $X$ and $u$ denote the traversal time and capacity of an edge, respectively. $1\to 2$ is a multiple edge, and $X_{A}(\equiv 1)$ and $X_{B}$ ( $\Pr[X_{B}=0]=\Pr[X_{B}=2]=1/2$ ) have the same mean ( $\mathbb{E}[X_{A}]=\mathbb{E}[X_{B}]=1$ ).

Algorithm	#selections of edge $1\rightarrow 2$		Cumulative regret
Algorithm	upper edge	lower edge	Cumulative regret
CLCB-MMLP	2510	2490	1245
SDCB-MMLP	4963	37	18.5

Table 1: Experimental results

Graph Bandits

Graph bandits use relationships among actions, items, or observations to guide sequential decisions and reduce the cost of learning rewards.

See all 16 papers

Online Packet Scheduling with Deadlines and Learning
May 30, 2026Gianmarco Genalti, Achraf Azize, Vianney PerchetCompetitive Analysis Multi-Armed Bandits
Politecnico di Milano · FairPlay Joint Team, CREST, ENSAE, IP Paris · FairPlay Joint Team, CREST, ENSAE, IP Paris, CRITEO AI Team
Semi-Bandit Learning for Monotone Stochastic Optimization
Dec 24, 2023Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan +1Stochastic Optimization Multi-Armed Bandits
Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumbai, India. · Department of Information, Risk, and Operations Management, University of Texas at Austin, Austin, USA. · Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA.
Offline Local Search for Online Stochastic Bandits
Apr 10, 2026Gerdus Benadè, Rathish Das, Thomas LavastidaCombinatorial Multi-Armed Bandits Stochastic Optimization
Boston University, MA, USA. · University of Houston, TX, USA. · University of Texas at Dallas, TX, USA.

May 30, 2026J/K move · Enter open · S save

Online Packet Scheduling with Deadlines and Learning

Gianmarco Genalti, Achraf Azize, Vianney Perchet

Politecnico di Milano · FairPlay Joint Team, CREST, ENSAE, IP Paris · FairPlay Joint Team, CREST, ENSAE, IP Paris, CRITEO AI Team

Competitive Analysis Multi-Armed Bandits

Open paper AskPDF arXiv

Network routers that enforce Quality-of-Service (QoS) guarantees must decide, at every clock cycle, which expiring packet of information to transmit, even when the value of the packet is unknown until it is processed. We frame this problem as the Online Packet Scheduling with Deadlines (OPSD) problem under Partial Feedback: packets arrive at every clock cycle, with different deadlines, but the weights are only observed after execution. Under a stochastic assumption on the unknown weights, we explore different variants of the OPSD problem with bandit feedback. We establish a connection between our setting and the sleeping bandits problem, and set our learning goal to

α

-regret minimization. We provide algorithms with provable

α

-regret guarantees under different spans of slackness, distinguishing systems allowing for randomization and systems that do not. In every scenario, our algorithms achieve an

α

-regret upper bound of

\widetilde{\mathcal{O}}\left(\sqrt{KT}\right)

, matching the lower bound for the standard bandit setting. In the practically relevant case of

2

-bounded deadline instances, where the deadline is set at most one clock cycle away from the arrival, our deterministic algorithm achieves the provably tightest possible competitive ratio. Remarkably, when the number of distinct packet types

K\ge 2

is finite, it is possible to break the well-established

Φ= \frac{1+\sqrt{5}}{2}

competitive ratio barrier and attain a tighter competitive ratio

θ_K

ranging in

[\sqrt{2}, Φ)

Abstract

Graph Bandits

Explore similar work

Online Packet Scheduling with Deadlines and Learning

Semi-Bandit Learning for Monotone Stochastic Optimization

Offline Local Search for Online Stochastic Bandits