Correlated combinatorial bandits for online resource allocation
Correlated combinatorial bandits for online resource allocation
复制标题
DOI：
10.1145/3492866.3549727
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Samarth Gupta;Jinhang Zuo;Carlee Joe-Wong;Gauri Joshi;Osman Yağan
中科院分区：
文献类型：
--
作者：
Samarth Gupta;Jinhang Zuo;Carlee Joe-Wong;Gauri Joshi;Osman Yağan
我们研究了一个连续的资源分配问题，在每一轮，决策者需要分配其有限的预算之间的不同可用的实体。通过这样做，决策者将获得该轮中每个实体的奖励。决策者的目标是在总共T轮中最大化期望的累积奖励或等价地最小化累积遗憾。顺序资源分配可以被建模为一个组合的强盗，通过查看分配的预算实体作为一个基地arm.In资源分配的上下文中，在不同的预算分配下收到的奖励可能是相关的。我们提出了一个新的相关组合的强盗框架，明确地模拟这种相关性。我们开发了一种新的相关的UCB算法在线资源分配，产生显着减少遗憾相对于相关性不可知的算法。在某些情况下，我们提出的算法甚至实现了有限的遗憾，这是一个有序的减少相对于相关性不可知的方法，在所有情况下会招致对数遗憾的遗憾。我们通过实验验证了这些性能的提高，如在无线信道上的在线功率分配，在多服务器系统中的作业调度和在线信道分配时隙ALOHA协议的应用。
We study a sequential resource allocation problem where, at each round, the decision-maker needs to allocate its limited budget among different available entities. In doing so, the decision-maker obtains the reward for each entity in that round. The goal of the decision-maker is to maximize the expected cumulative reward or equivalently minimize cumulative regret over a total of T rounds. Sequential resource allocation can be modeled as a combinatorial bandit by viewing the allocation of a budget to an entity as a base arm. In the context of resource allocation, the rewards received under different budget allocations are likely to be correlated. We propose a novel correlated combinatorial bandit framework that explicitly models such correlations. We develop a novel Correlated-UCB algorithm for online resource allocation, which yields significantly reduced regret relative to correlation-agnostic algorithms. In certain cases, our proposed algorithm even achieves bounded regret, which is an order-wise reduction in the regret relative to the correlation-agnostic approach, which incurs logarithmic regret under all scenarios. We validate these performance gains through experiments on several applications such as online power allocation across wireless channels, job scheduling in multi-server systems and online channel assignment for the slotted ALOHA protocol.