A Simple Distribution-Free Approach to the Max k-Armed Bandit Problem

@inproceedings{citeulike:2521602, abstract = {The max k-armed bandit problem is a recently-introduced online optimization problem with practical applications to heuristic search. Given a set of k slot machines, each yielding payoff from a fixed (but unknown) distribution, we wish to allocate trials to the machines so as to maximize the maximum payoff received over a series of n trials. Previous work on the max k-armed bandit problem has assumed that payoffs are drawn from generalized extreme value (GEV) distributions. In this paper we present a simple algorithm, based on an algorithm for the classical k-armed bandit problem, that solves the max k-armed bandit problem effectively without making strong distributional assumptions. We demonstrate the effectiveness of our approach by applying it to the task of selecting among priority dispatching rules for the resource-constrained project scheduling problem with maximal time lags (RCPSP/max).}, author = {Streeter, Matthew J. and Smith, Stephen F. }, booktitle = {Principles and Practice of Constraint Programming (CP 2006)}, citeulike-article-id = {2521602}, doi = {10.1007/11889205\_40}, journal = {Principles and Practice of Constraint Programming - CP 2006}, keywords = {bandit\_problem, max\_bandit}, pages = {560--574}, posted-at = {2008-03-12 15:58:37}, priority = {0}, title = {A Simple Distribution-Free Approach to the Max k-Armed Bandit Problem}, url = {http://dx.doi.org/10.1007/11889205\_40}, year = {2006} }

TY - CONF ID - citeulike:2521602 L3 - citeulike-article-id:2521602 TI - A Simple Distribution-Free Approach to the Max k-Armed Bandit Problem T2 - Principles and Practice of Constraint Programming (CP 2006) JF - Principles and Practice of Constraint Programming - CP 2006 SP - 560 EP - 574 N2 - The max k-armed bandit problem is a recently-introduced online optimization problem with practical applications to heuristic search. Given a set of k slot machines, each yielding payoff from a fixed (but unknown) distribution, we wish to allocate trials to the machines so as to maximize the maximum payoff received over a series of n trials. Previous work on the max k-armed bandit problem has assumed that payoffs are drawn from generalized extreme value (GEV) distributions. In this paper we present a simple algorithm, based on an algorithm for the classical k-armed bandit problem, that solves the max k-armed bandit problem effectively without making strong distributional assumptions. We demonstrate the effectiveness of our approach by applying it to the task of selecting among priority dispatching rules for the resource-constrained project scheduling problem with maximal time lags (RCPSP/max). KW - bandit_problem KW - max_bandit AU - Streeter, Matthew AU - Smith, Stephen PY - 2006/// UR - http://dx.doi.org/10.1007/11889205_40 ER -