Knapsack based Optimal Policies for Budget-Limited Multi-Armed Bandits

Abstract

In budget-limited multi-armed bandit (MAB) problems, the learner's actions are costly and constrained by a fixed budget. Consequently, an optimal exploitation policy may not be to pull the optimal arm repeatedly, as is the case in other variants of MAB, but rather to pull the sequence of different arms that maximises the agent's total reward within the budget. This difference from existing MABs means that new approaches to maximising the total reward are required. Given this, we develop two pulling policies, namely: (i) KUBE; and (ii) fractional KUBE. Whereas the former provides better performance up to 40% in our experimental settings, the latter is computationally less expensive. We also prove logarithmic upper bounds for the regret of both policies, and show that these bounds are asymptotically optimal (i.e. they only differ from the best possible regret by a constant factor).

References in corpus (1)

• Pure Exploration for Multi-Armed Bandit Problems

Cited by in corpus (19)

• Bandits with Knapsacks
• An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
• Thompson Sampling for Budgeted Multi-armed Bandits
• Multi-Armed Bandit for Energy-Efficient and Delay-Sensitive Edge Computing in Dynamic Networks with Uncertainty
• Group-Fair Online Allocation in Continuous Time
• Optimal Resource Allocation with Semi-Bandit Feedback
• Logarithmic regret bounds for Bandits with Knapsacks
• Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration
• Bandit Algorithms for Precision Medicine
• Budget-Constrained Bandits over General Cost and Reward Distributions
• An Incentive Compatible Multi-Armed-Bandit Crowdsourcing Mechanism with Quality Assurance
• Continuous-Time Multi-Armed Bandits with Controlled Restarts
• Bandits with Knapsacks beyond the Worst-Case
• The Survival Bandit Problem
• Budgeted and Non-budgeted Causal Bandits
• A Farewell to Arms: Sequential Reward Maximization on a Budget with a Giving Up Option
• Multi-armed Bandits with Cost Subsidy
• Identifying Influential Users in Unknown Social Networks for Adaptive Incentive Allocation Under Budget Restriction
• OL4EL: Online Learning for Edge-cloud Collaborative Learning on Heterogeneous Edges with Resource Constraints