提出有限探查机制,提升多目标资源选择的效率与准确性。
Probe-then-Commit Multi-Objective Bandits: Theoretical Benefits of Limited Multi-Arm Feedback
- 采用先探测后决策框架,仅允许探查最多q个候选路径,再选一个执行。
- 理论证明探查数每增加一倍,误差下降约1/√2,显著提升学习效率。
- 适用于移动边缘计算、多无线接入等需权衡多指标的实时系统。
我们研究一种在线资源选择问题,源于多无线接入和移动边缘计算卸载。每轮中,智能体从K个候选链路/服务器(臂)中选择,其性能为一个随机的d维向量(如吞吐量、时延、能耗、可靠性)。关键交互机制是“探查后承诺”(PtC):智能体可最多探查q>1个候选者以获取其向量结果,但必须在数据平面中执行恰好一个。该受限多臂反馈机制严格介于经典多臂赌博机(q=1)与全信息专家(q=K)之间,但现有理论多集中于两极。本文提出 extsc{PtC-P-UCB}算法,其核心技术是在帕累托前沿下的不确定性感知探查:通过近似最大化类似超体积的前沿覆盖潜力选择前q个探查对象,并基于边际超体积增益决定最终执行。我们证明了主导超体积前沿误差为$ ilde{O}(K_P d / \ \sqrt{qT})$,其中$K_P$为帕累托前沿大小,$T$为时间范围;标量化遗憾为$ ilde{O}(L_ϕ d \sqrt{(K/q)T})$,其中$ϕ$为标量化函数。这清晰揭示了探查数带来的$1/\sqrt{q}$加速效果。此外,我们扩展至多模态探查:每次探查返回M种模态(如信道状态、队列长度、计算遥测),通过不确定性融合得到方差自适应版本的上述界限,依赖有效噪声尺度。
原文摘要 · Abstract (English)
We study an online resource-selection problem motivated by multi-radio access selection and mobile edge computing offloading. In each round, an agent chooses among $K$ candidate links/servers (arms) whose performance is a stochastic $d$-dimensional vector (e.g., throughput, latency, energy, reliability). The key interaction is \emph{probe-then-commit (PtC)}: the agent may probe up to $q>1$ candidates via control-plane measurements to observe their vector outcomes, but must execute exactly one candidate in the data plane. This limited multi-arm feedback regime strictly interpolates between classical bandits ($q=1$) and full-information experts ($q=K$), yet existing multi-objective learning theory largely focuses on these extremes. We develop \textsc{PtC-P-UCB}, an optimistic probe-then-commit algorithm whose technical core is frontier-aware probing under uncertainty in a Pareto mode, e.g., it selects the $q$ probes by approximately maximizing a hypervolume-inspired frontier-coverage potential and commits by marginal hypervolume gain to directly expand the attained Pareto region. We prove a dominated-hypervolume frontier error of $\tilde{O} (K_P d/\sqrt{qT})$, where $K_P$ is the Pareto-frontier size and $T$ is the horizon, and scalarized regret $\tilde{O} (L_ϕd\sqrt{(K/q)T})$, where $ϕ$ is the scalarizer. These quantify a transparent $1/\sqrt{q}$ acceleration from limited probing. We further extend to \emph{multi-modal probing}: each probe returns $M$ modalities (e.g., CSI, queue, compute telemetry), and uncertainty fusion yields variance-adaptive versions of the above bounds via an effective noise scale.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。