Budgeted Combinatorial Multi-Armed Bandits

Abstract

Multi-armed bandits (MABs) have various applications in real life, however, most of these applications require certain variations to the classic MAB problem. In this thesis, we focus on one such variant - budgeted combinatorial MAB (BCMAB). A BCMAB allows for multiple arms to be pulled in each round with no restrictions on the number of arms selected per round or the budget consumed per round, as long as the arms pulled do not exceed the total budget. The reward structure is taken to be additive, i.e., the reward obtained on pulling a set of arms in a round is the sum of the rewards obtained by the individual arms. We study relevant problems and develop our solutions to BCMAB. We come up with the algorithms CBwK-Greedy-UCB and CBwK-LP-UCB. We mathematically prove regret bound for CBwKLP-UCB. We experimentally analyze our algorithms and compare them with each other and with the previous most suited algorithm.