arXiv:2509.09933cs.LG2025-09

扩展了组合半竞争模型,支持多单位选择与反馈,适用于运输和背包等实际问题。

Multi-Play Combinatorial Semi-Bandit Problem

  • 允许每轮选择非负整数动作,可从单个臂获取多次反馈。
  • 提出两种算法:一种基于汤普森采样,实现对数级分布依赖后悔;另一种兼顾随机与对抗情形。
  • 适合需处理流量分配或资源调度的强化学习研究者,尤其关注高效在线决策场景。

在组合半竞争(CSB)问题中,玩家从组合动作集中选择一个动作,并观察所包含基础臂的反馈。尽管CSB广泛适用于组合优化问题,但其仅限于二值决策空间,排除了涉及非负整数流或分配的重要情况,如最优传输和背包问题。为克服此限制,我们提出多播放组合半竞争(MP-CSB),允许玩家每轮选择非负整数动作,并在每轮中从单个臂观察多个反馈。我们提出了两种算法:一种基于汤普森采样的算法,在动作空间指数级增长时仍计算可行,且在随机情形下达到$O(\log T)$分布依赖后悔,其中$T$为时间范围;另一种为“双世界最优”算法,在随机情形下实现$O(\log T)$方差依赖后悔,在对抗情形下达到$\tilde{\mathcal{O}}\left( \sqrt{T} \right)$后悔,且其后悔量为数据相关,适应最优动作的累积损失、总二次变差及损失序列路径长度。最后,数值实验表明所提算法优于现有CSB方法。

原文摘要 · Abstract (English)

In the combinatorial semi-bandit (CSB) problem, a player selects an action from a combinatorial action set and observes feedback from the base arms included in the action. While CSB is widely applicable to combinatorial optimization problems, its restriction to binary decision spaces excludes important cases involving non-negative integer flows or allocations, such as the optimal transport and knapsack problems.To overcome this limitation, we propose the multi-play combinatorial semi-bandit (MP-CSB), where a player can select a non-negative integer action and observe multiple feedbacks from a single arm in each round. We propose two algorithms for the MP-CSB. One is a Thompson-sampling-based algorithm that is computationally feasible even when the action space is exponentially large with respect to the number of arms, and attains $O(\log T)$ distribution-dependent regret in the stochastic regime, where $T$ is the time horizon. The other is a best-of-both-worlds algorithm, which achieves $O(\log T)$ variance-dependent regret in the stochastic regime and the worst-case $\tilde{\mathcal{O}}\left( \sqrt{T} \right)$ regret in the adversarial regime. Moreover, its regret in adversarial one is data-dependent, adapting to the cumulative loss of the optimal action, the total quadratic variation, and the path-length of the loss sequence. Finally, we numerically show that the proposed algorithms outperform existing methods in the CSB literature.

强化学习在线决策组合优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。