Thompson Sampling for Budgeted Multi-armed Bandits

Abstract

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 cost is constrained by a budget. We start with the case of Bernoulli bandits, in which the random rewards (costs) of an arm are independently sampled from a Bernoulli distribution. To implement the Thompson sampling algorithm in this case, at each round, we sample two numbers from the posterior distributions of the reward and cost for each arm, obtain their ratio, select the arm with the maximum ratio, and then update the posterior distributions. We prove that the distribution-dependent regret bound of this algorithm is $O(\ln B)$, where $B$ denotes the budget. By introducing a Bernoulli trial, we further extend this algorithm to the setting that the rewards (costs) are drawn from general distributions, and prove that its regret bound remains almost the same. Our simulation results demonstrate the effectiveness of the proposed algorithm.

References in corpus (7)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Analysis of Thompson Sampling for the multi-armed bandit problem
• The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
• Further Optimal Regret Bounds for Thompson Sampling
• Bandits with Knapsacks
• Knapsack based Optimal Policies for Budget-Limited Multi-Armed Bandits
• Budget Optimization for Sponsored Search: Censored Learning in MDPs

Cited by in corpus (11)

• Achieving Fairness in the Stochastic Multi-armed Bandit Problem
• Bandit Algorithms for Precision Medicine
• Budget-Constrained Bandits over General Cost and Reward Distributions
• Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs
• On the Prior Sensitivity of Thompson Sampling
• Continuous-Time Multi-Armed Bandits with Controlled Restarts
• The Survival Bandit Problem
• Incentivized Bandit Learning with Self-Reinforcing User Preferences
• Identifying Influential Users in Unknown Social Networks for Adaptive Incentive Allocation Under Budget Restriction
• Thompson Sampling for Linearly Constrained Bandits
• Simple Algorithms for Dueling Bandits