Budget-Constrained Multi-Armed Bandits With Multiple Plays

Authors

  • Datong Zhou University of California, Berkeley
  • Claire Tomlin University of California, Berkeley

DOI:

https://doi.org/10.1609/aaai.v32i1.11629

Keywords:

Multi-Armed Bandits, Online Learning, Machine Learning

Abstract

We study the multi-armed bandit problem with multiple plays and a budget constraint for both the stochastic and the adversarial setting. At each round, exactly K out of N possible arms have to be played (with 1 ≤ K <= N). In addition to observing the individual rewards for each arm played, the player also learns a vector of costs which has to be covered with an a-priori defined budget B. The game ends when the sum of current costs associated with the played arms exceeds the remaining budget. Firstly, we analyze this setting for the stochastic case, for which we assume each arm to have an underlying cost and reward distribution with support [cmin, 1] and [0, 1], respectively. We derive an Upper Confidence Bound (UCB) algorithm which achieves O(NK4 log B) regret. Secondly, for the adversarial case in which the entire sequence of rewards and costs is fixed in advance, we derive an upper bound on the regret of order O(√NB log(N/K)) utilizing an extension of the well-known Exp3 algorithm. We also provide upper bounds that hold with high probability and a lower bound of order Ω((1 – K/N) √NB/K).

Downloads

Published

2018-04-29

How to Cite

Zhou, D., & Tomlin, C. (2018). Budget-Constrained Multi-Armed Bandits With Multiple Plays. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.11629