提出在线探测框架，优化资源未知场景下的连续选择决策。
Online Learning with Probing for Sequential User-Centric Selection
- 通过探测获取资源与收益信息，再分配动作，兼顾成本与收益。
- 在线算法实现近似最优的√T + ln²T 误差，优于传统方法。
- 适用于网约车、推荐系统等实际场景，实测效果显著。
我们将带有信息获取的序列决策问题形式化为探查增强的用户中心选择（PUCS）框架：学习者先对部分臂进行探查以获取资源与收益的附加信息，随后在M个臂中分配K次操作。该框架涵盖网约车、无线调度和内容推荐等应用场景，其中资源与回报初始未知，且探查成本较高。针对已知分布的离线情形，我们提出一种贪心探查算法，具有常数因子近似保证ζ = (e−1)/(2e−1)。对于分布未知的在线情形，我们引入OLPA——一种随机组合强化学习算法，其遗憾上界为𝒪(√T + ln²T)，并证明下界为Ω(√T)，表明上界在对数因子内紧致。基于真实数据集的实验验证了所提方案的有效性。
原文摘要 · Abstract (English)
We formalize sequential decision-making with information acquisition as the probing-augmented user-centric selection (PUCS) framework, where a learner first probes a subset of arms to obtain side information on resources and rewards, and then assigns $K$ plays to $M$ arms. PUCS covers applications such as ridesharing, wireless scheduling, and content recommendation, in which both resources and payoffs are initially unknown and probing is costly. For the offline setting with known distributions, we present a greedy probing algorithm with a constant-factor approximation guarantee $ζ= (e-1)/(2e-1)$. For the online setting with unknown distributions, we introduce OLPA, a stochastic combinatorial bandit algorithm that achieves a regret bound $\mathcal{O}(\sqrt{T} + \ln^{2} T)$. We also prove a lower bound $Ω(\sqrt{T})$, showing that the upper bound is tight up to logarithmic factors. Experiments on real-world data demonstrate the effectiveness of our solutions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。