Selecting k Paths with the Minimum Longest Path Length in the Stochastic Semi-Bandit Setting
cs.LG
Submitted: 2026-09-13
Updated: 2026-09-13
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
Terminology
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.
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: Local-Consistency Optimisation for Bayesian Neural Networks
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks