Approximation algorithms for restless bandit problems

ABSTRACT

In this paper, we consider the restless bandit problem, which is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit problem in decision theory. In its ultimate generality, the restless bandit problem is known to be PSPACE-Hard to approximate to any non-trivial factor, and little progress has been made on this problem despite its significance in modeling activity allocation under uncertainty. We make progress on this problem by showing that for an interesting and general subclass that we term Monotone bandits, a surprisingly simple and intuitive greedy policy yields a factor 2 approximation. Such greedy policies are termed index policies, and are popular due to their simplicity and their optimality for the stochastic multi-armed bandit problem. The Monotone bandit problem strictly generalizes the stochastic multi-armed bandit problem, and naturally models multi-project scheduling where the state of a project becomes increasingly uncertain when the project is not scheduled. We develop several novel techniques in the design and analysis of the index policy. Our algorithm proceeds by introducing a novel "balance" constraint to the dual of a well-known LP relaxation to the restless bandit problem. This is followed by a structural characterization of the optimal solution by using both the exact primal as well as dual complementary slackness conditions. This yields an interpretation of the dual variables as potential functions from which we derive the index policy and the associated analysis.

REFERENCES

• 1: D. Adelman and A. J. Mersereau. Relaxations of weakly coupled stochastic dynamic programs. Operations Research, 2008.
• 2: Peter Auer, Using confidence bounds for exploitation-exploration trade-offs, The Journal of Machine Learning Research, 3, 3/1/2003
• 3: Peter Auer , Nicolò Cesa-Bianchi , Paul Fischer, Finite-time Analysis of the Multiarmed Bandit Problem, Machine Learning, v.47 n.2-3, p.235-256, May-June 2002 [doi>10.1023/A:1013689704352]
• 4: P. Auer , N. Cesa-Bianchi , Y. Freund , R. E. Schapire, Gambling in a rigged casino: The adversarial multi-armed bandit problem, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.322, October 23-25, 1995
• 5: Dimitri P. Bertsekas, Dynamic Programming and Optimal Control, Two Volume Set, Athena Scientific, 2001
• 6: Dimitris Bertsimas , José Niño-Mora, Conservation laws, extended polymatroids and multiarmed bandit problems; a polyhedral approach to indexable systems, Mathematics of Operations Research, v.21 n.2, p.257-306, May 1996 [doi>10.1287/moor.21.2.257]
• 7: Dimitris Bertsimas , José Niño-Mora, Restless Bandits, Linear Programming Relaxations, and a Primal-Dual Index Heuristic, Operations Research, v.48 n.1, p.80-90, January 2000 [doi>10.1287/opre.48.1.80.12444]
• 8: Nicolò Cesa-Bianchi , Yoav Freund , David Haussler , David P. Helmbold , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Journal of the ACM (JACM), v.44 n.3, p.427-485, May 1997 [doi>10.1145/258128.258179]
• 9: Daniela Pucci De Farias , Nimrod Megiddo, Combining expert advice in reactive environments, Journal of the ACM (JACM), v.53 n.5, p.762-799, September 2006 [doi>10.1145/1183907.1183911]
• 10: Abraham D. Flaxman , Adam Tauman Kalai , H. Brendan McMahan, Online convex optimization in the bandit setting: gradient descent without a gradient, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 11: J. C. Gittins and D. M. Jones. A dynamic allocation index for the sequential design of experiments. Progress in statistics (European Meeting of Statisticians), 1972.
• 12: Ashish Goel , Sudipto Guha , Kamesh Munagala, Asking the right questions: model-driven optimization using probes, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142380]
• 13: Katerina Goseva-Popstojanova , Kishor S. Trivedi, Stochastic Modeling Formalisms for Dependability, Performance and Performability, Performance Evaluation: Origins and Directions, p.403-422, January 2000
• 14: Sudipto Guha , Kamesh Munagala, Approximation algorithms for budgeted learning problems, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250807]
• 15: Sudipto Guha , Kamesh Munagala, Approximation Algorithms for Partial-Information Based Stochastic Control with Markovian Rewards, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.483-493, October 21-23, 2007 [doi>10.1109/FOCS.2007.12]
• 16: Sudipto Guha , Kamesh Munagala, Model-driven optimization using adaptive probes, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.308-317, January 07-09, 2007, New Orleans, Louisiana
• 17: S. Guha, K. Munagala, and S. Sarkar. Information acquisition and exploitation in multichannel wireless systems. CoRR, arXiv:0804.1724, 2008.
• 18: Sudipto Guha , Kamesh Munagala, Approximation algorithms for budgeted learning problems, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250807]
• 19: J. T. Hawkins. A Langrangian decomposition approach to weakly coupled dynamic optimization problems and its applications. PhD thesis, Operations Research Center, Massachusetts Institute of Technology, 2003.
• 20: T. Javidi, B. Krishnamachari, Q. Zhao, and M. Liu. Optimality of myopic sensing in multi-channel opportunistic access. In Proc. IEEE International Conf. in Communications (ICC '08), 2008.
• 21: S. M. Kakade and M. J. Kearns. Trading in markovian price models. In COLT, pages 606--620, 2005.
• 22: R. Levi, M. Pál, R. Roundy, and D. B. Shmoys. Approximation algorithms for stochastic inventory control models. In IPCO, pages 306--320, 2005.
• 23: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 24: Carsten Lund , Mihalis Yannakakis, The Approximation of Maximum Subgraph Problems, Proceedings of the 20th International Colloquium on Automata, Languages and Programming, p.40-51, July 05-09, 1993
• 25: K. Munagala and P. Shi. The stochastic machine replenishment problem. In IPCO, 2008.
• 26: J. Le Ny, M. Dahleh, and E. Feron. Multi-UAV dynamic routing with partial observations using restless bandits allocation indices. In Proceedings of the 2008 American Control Conference, 2008.
• 27: Christos H. Papadimitriou , John N. Tsitsiklis, The Complexity of Optimal Queuing Network Control, Mathematics of Operations Research, v.24 n.2, p.293-305, February 1999 [doi>10.1287/moor.24.2.293]
• 28: A. Slivkins and E. Upfal. Adapting to a changing environment: The Brownian restless bandits. In COLT, 2008.
• 29: J. N. Tsitsiklis. A short proof of the Gittins index theorem. Annals of Appl. Prob., 4(1):194--199, 1994.
• 30: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 31: G. Weiss. Branching bandit processes. Probab. Engng. Inform. Sci., 2:269--278, 1988.
• 32: P. Whittle. Arm acquiring bandits. Ann. Probab., 9:284--292, 1981.
• 33: P. Whittle. Restless bandits: Activity allocation in a changing world. Appl. Prob., 25(A):287--298, 1988.
• 34: N. E. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11(6):525--541, 1994.
• 35: Q. Zhao, B. Krishnamachari, and K. Liu. On myopic sensing for multi-channel opportunistic access, 2007. CoRR, arXiv:0712.0035, 2007.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming