[论文] An LP-based Sampling Policy for Multi-Armed Bandits with Side-Observat...

论文概要

研究领域: ML 作者: Ashutosh Soni, Peizhong Ju, Atilla Eryilmaz 发布时间: 2025-03-30 arXiv: 2503.23700

中文摘要

我们研究了随机多臂老虎机（MAB）问题，其中底层网络结构使得跨相关动作的旁观察成为可能。我们使用二分图将动作连接到一组未知量，使得选择动作会揭示与其连接的所有未知量的观察。虽然之前的工作依赖于所有动作永久可访问的假设，但我们研究了更实际的随机可用性设置，其中可行动作集（"激活集"）在每一轮动态变化。该框架模拟具有结构依赖性和波动性的真实系统，如社交网络，其中用户提供关于同伴偏好的旁信息，但并不总是在线可查询。为解决这一挑战，我们提出了UCB-LP-A，一种利用线性规划（LP）方法在随机可用性下优化探索-利用权衡的新策略。与假设恒定访问的标准网络bandit算法不同，UCB-LP-A计算可实现激活集上的最优采样分布，确保仅使用当前活跃臂收集必要观察。我们推导了策略遗憾的理论上界，表征了网络结构和激活概率的影响。最后，我们通过数值模拟证明了UCB-LP-A显著优于忽略旁信息或可用性约束的现有启发式方法。

原文摘要

We study the stochastic multi-armed bandit (MAB) problem where an underlying network structure enables side-observations across related actions. We use a bipartite图将动作连接到一组未知量，使得选择动作会揭示与其连接的所有未知量的观察。虽然之前的工作依赖于所有动作永久可访问的假设，但我们研究了更实际的随机可用性设置，其中可行动作集（"激活集"）在每一轮动态变化。该框架模拟具有结构依赖性和波动性的真实系统，如社交网络，其中用户提供关于同伴偏好的旁信息，但并不总是在线可查询。为解决这一挑战，我们提出了UCB-LP-A，一种利用线性规划（LP）方法在随机可用性下优化探索-利用权衡的新策略。与假设恒定访问的标准网络bandit算法不同，UCB-LP-A计算可实现激活集上的最优采样分布，确保仅使用当前活跃臂收集必要观察。我们推导了策略遗憾的理论上界，表征了网络结构和激活概率的影响。最后，我们通过数值模拟证明了UCB-LP-A显著优于忽略旁信息或可用性约束的现有启发式方法。

--- *自动采集于 2026-03-31*

#论文 #arXiv #ML #小凯