Extensions of the multiarmed bandit problem: The discounted case Export

@article{citeulike:3415603, abstract = {There are <tex>N</tex>independent machines. Machine i is described by a sequence<tex>X^i(s), F^i(s)</tex>where<tex>X^i(s)</tex>is the immediate reward and F^i(s) is the information available before i is operated for the sth lime. At each time one operates exacfiy one machine; idle machines remain frozen. The problem is to schedule the operation of the machines so as to maximize the expected total discounted sequence of rewards. An elementary proof shows that to each machine is associated an index, and the optimal policy operates the machine with the largest current index. When the machines are completely observed Markov chains, this coincides with the well-known Gittins index rule, and new algorithms are given for calculating the index. A reformulation of the bandit problem yields the tax problem, which includes, as a special case, Klimov's waiting time problem. Using the concept of superprocess, an index rule is derived for the case where new machines arrive randomly. Finally, continuous time versions of these problems are considered for both preemptive and nonpreemptive disciplines.}, author = {Varaiya, Pravin P. and Walrand, Jean C. and Buyukkoc, Cagatay}, booktitle = {Automatic Control, IEEE Transactions on}, citeulike-article-id = {3415603}, citeulike-linkout-0 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1103989}, journal = {IEEE Transactions on Automatic Control}, keywords = {bandit\_problem, markov\_chains}, number = {5}, pages = {426--439}, posted-at = {2008-10-15 20:45:59}, priority = {3}, title = {Extensions of the multiarmed bandit problem: The discounted case}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1103989}, volume = {30}, year = {1985} }

TY - JOUR ID - citeulike:3415603 L3 - citeulike-article-id:3415603 N2 - There are <tex>N</tex>independent machines. Machine i is described by a sequence<tex>X^i(s), F^i(s)</tex>where<tex>X^i(s)</tex>is the immediate reward and F^i(s) is the information available before i is operated for the sth lime. At each time one operates exacfiy one machine; idle machines remain frozen. The problem is to schedule the operation of the machines so as to maximize the expected total discounted sequence of rewards. An elementary proof shows that to each machine is associated an index, and the optimal policy operates the machine with the largest current index. When the machines are completely observed Markov chains, this coincides with the well-known Gittins index rule, and new algorithms are given for calculating the index. A reformulation of the bandit problem yields the tax problem, which includes, as a special case, Klimov's waiting time problem. Using the concept of superprocess, an index rule is derived for the case where new machines arrive randomly. Finally, continuous time versions of these problems are considered for both preemptive and nonpreemptive disciplines. IS - 5 JF - IEEE Transactions on Automatic Control EP - 439 TI - Extensions of the multiarmed bandit problem: The discounted case VL - 30 T2 - Automatic Control, IEEE Transactions on SP - 426 KW - bandit_problem KW - markov_chains AU - Varaiya, Pravin AU - Walrand, Jean AU - Buyukkoc, Cagatay PY - 1985/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1103989 ER -