Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract
Will Ma · 2013
The multi-armed bandit (MAB) problem features the classical tradeoff between exploration and exploitation. The input specifies several stochastic arms which evolve with each pull, and the goal is to maximize the expected reward after a fixed budget of pulls. The celebrated work of Gittins et al., surveyed in [8], presumes a condition on the arms called the martingale assumption. In [9], A. Gupta et al. obtained an LP-based -approximation for the problem with the martingale assumption removed. We improve the algorithm to a -approximation, with simpler analysis. Our algorithm also generalizes to the case of MAB superprocesses with (stochastic) multi-period actions. This generalization captures the framework introduced by Guha and Munagala in [11], and yields new results for their budgeted learning problems.