Budgeted Combinatorial Multi-Armed Bandits
We consider a budgeted combinatorial multi-armed bandit setting where, in every round, the algorithm selects a super-arm consisting of one or more arms. The goal is to minimize the total expected regret after all rounds within a limited budget. Existing techniques in this literature either fix the budget per round or fix the number of arms pulled in each round. Our setting is more general where based on the remaining budget and remaining number of rounds, the algorithm can decide how many arms to be pulled in each round. First, we propose CBwK-Greedy-UCB algorithm, which uses a greedy technique, CBwK-Greedy, to allocate the arms to the rounds. Next, we propose a reduction of this problem to Bandits with Knapsacks (BwK) with a single pull. With this reduction, we propose CBwK-LPUCB that uses PrimalDualBwK ingeniously. We rigorously prove regret bounds for CBwK-LP-UCB. We experimentally compare the two algorithms and observe that CBwK-Greedy-UCB performs incrementally better than CBwK-LP-UCB. We also show that for very high budgets, the regret goes to zero.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Armed BanditsSimilar Papers 제목 키워드 기반
Meritocratic Fairness via $K$-Shapley Values in Budgeted Combinatorial Bandits with Full-Bandit Feedback
We study meritocratic fairness in budgeted combinatorial multi-armed bandits with full-bandit feedback, where a learner selects at most $K$ arms per time step and observes only the noisy aggregate reward of the selected …
Multi-Armed BanditsFederated LearningThompson Sampling for Budgeted Multi-armed Bandits
Thompson sampling is one of the earliest randomized algorithms for multi-armed bandits (MAB). In this paper, we extend the Thompson sampling to Budgeted MAB, where there is random cost for pulling an arm and the total co…
Multi-Armed BanditsThompson SamplingImproving Thompson Sampling via Information Relaxation for Budgeted Multi-armed Bandits
We consider a Bayesian budgeted multi-armed bandit problem, in which each arm consumes a different amount of resources when selected and there is a budget constraint on the total amount of resources that can be used. Bud…
Multi-Armed BanditsThompson SamplingCombinatorial Semi-Bandits with Knapsacks
We unify two prominent lines of work on multi-armed bandits: bandits with knapsacks (BwK) and combinatorial semi-bandits. The former concerns limited "resources" consumed by the algorithm, e.g., limited supply in dynamic…
Multi-Armed BanditsAdaptive Budgeted Multi-Armed Bandits for IoT with Dynamic Resource Constraints
Internet of Things (IoT) systems increasingly operate in environments where devices must respond in real time while managing fluctuating resource constraints, including energy and bandwidth. Yet, current approaches often…
Multi-Armed Bandits