Asymptotically Optimal Algorithms for Budgeted Multiple Play Bandits
We study a generalization of the multi-armed bandit problem with multiple plays where there is a cost associated with pulling each arm and the agent has a budget at each time that dictates how much she can expect to spend. We derive an asymptotic regret lower bound for any uniformly efficient algorithm in our setting. We then study a variant of Thompson sampling for Bernoulli rewards and a variant of KL-UCB for both single-parameter exponential families and bounded, finitely supported rewards. We show these algorithms are asymptotically optimal, both in rateand leading problem-dependent constants, including in the thick margin setting where multiple arms fall on the decision boundary.
Code (0)
등록된 구현이 없습니다.
Tasks
Thompson SamplingSimilar Papers 제목 키워드 기반
An Asymptotically Optimal Algorithm for Communicating Multiplayer Multi-Armed Bandit Problems
We consider a decentralized stochastic multi-armed bandit problem with multiple players. Each player aims to maximize his/her own reward by pulling an arm. The arms give rewards based on i.i.d. stochastic Bernoulli distr…
Minimax Optimal Algorithms for Adversarial Bandit Problem with Multiple Plays
We investigate the adversarial bandit problem with multiple plays under semi-bandit feedback. We introduce a highly efficient algorithm that asymptotically achieves the performance of the best switching $m$-arm strategy …
Online Learning with Cumulative Oversampling: Application to Budgeted Influence Maximization
We propose a cumulative oversampling (CO) method for online learning. Our key idea is to sample parameter estimations from the updated belief space once in each round (similar to Thompson Sampling), and utilize the cumul…
Thompson SamplingCurriculum learning for multilevel budgeted combinatorial problems
Learning heuristics for combinatorial optimization problems through graph neural networks have recently shown promising results on some classic NP-hard problems. These are single-level optimization problems with only one…
Combinatorial OptimizationMulti-agent Reinforcement LearningBudget-constrained Active Learning to Effectively De-censor Survival Data
Standard supervised learners attempt to learn a model from a labeled dataset. Given a small set of labeled instances, and a pool of unlabeled instances, a budgeted learner can use its given budget to pay to acquire the l…
Active Learning