Approximation algorithms for budgeted learning problems

ABSTRACT

We present the first approximation algorithms for a large class of budgeted learning problems. One classicexample of the above is the budgeted multi-armed bandit problem. In this problem each arm of the bandithas an unknown reward distribution on which a prior isspecified as input. The knowledge about the underlying distribution can be refined in the exploration phase by playing the arm and observing the rewards. However, there is a budget on the total number of plays allowed during exploration. After this exploration phase,the arm with the highest (posterior) expected reward is hosen for exploitation. The goal is to design the adaptive exploration phase subject to a budget constraint on the number of plays, in order to maximize the expected reward of the arm chosen for exploitation. While this problem is reasonably well understood in the infinite horizon discounted reward setting, the budgeted version of the problem is NP-Hard. For this problem and several generalizations, we provide approximate policies that achieve a reward within constant factor of the reward optimal policy. Our algorithms use a novel linear program rounding technique based on stochastic packing.

REFERENCES

• 1: [1] Q. An, H. Li, X. Liao, and L. Carin. Active feature acquisition with POMDP models. Submitted to Pattern Recognition Letters, 2006.
• 2: Dimitri P. Bertsekas, Dynamic Programming and Optimal Control, Athena Scientific, 2001
• 3: [3] D. Bertsimas, D. Gamarnik, and J. Tsitsiklis. Performance of multiclass markovian queueing networks via piecewise linear Lyapunov functions. Annals of Applied Probability, 11(4):1384-1428, 2002.
• 4: 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]
• 5: 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]
• 6: [6] D. Bertsimas, I. Paschalidis, and J. N. Tsitsiklis. Optimization of multiclass queueing networks: Polyhedral and nonlinear characterizations of achievable performance. Annals of Applied Probability, 4(1):43-75, 1994.
• 7: [7] M. Charikar, C. Chekuri, and M. Pál. Sampling bounds for stochastic optimization. In APPROX-RANDOM, pages 257-269, 2005.
• 8: [8] D. A. Cohn, Z. Ghahramani, and M. I. Jordan. Active learning with statistical models. In G. Tesauro, D. Touretzky, and T. Leen, editors, Advances in Neural Information Processing Systems, volume 7, pages 705-712. The MIT Press, 1995.
• 9: [9] V. Conitzer and T. Sandholm. Definition and complexity of some basic metareasoning problems. In IJCAI, pages 1099-1106, 2003.
• 10: Brian Christopher Dean , Michel X. Goemans, Approximation algorithms for stochastic scheduling problems, Massachusetts Institute of Technology, Cambridge, MA, 2005
• 11: Brian C. Dean , Michel X. Goemans , Jan Vondrak, Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.208-217, October 17-19, 2004 [doi>10.1109/FOCS.2004.15]
• 12: Brian C. Dean , Michel X. Goemans , Jan Vondrák, Adaptivity and approximation for stochastic packing problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 13: [13] 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.
• 14: 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]
• 15: Ashish Goel , Piotr Indyk, Stochastic Load Balancing and Related Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.579, October 17-18, 1999
• 16: [16] S. Guha and K. Munagala. Model driven optimization using adaptive probes. Proc. ACM-SIAM Symp. on Discrete Algorithms, 2007.
• 17: [17] S. Guha and K. Munagala. Approximation Algorithms for Budgeted Learning Problems. Available at http://www.cs.duke.edu/~kamesh/bandits.pdf.
• 18: [18] S. Guha, K. Munagala, and S. Sarkar. Jointly optimal probing and transmission strategies for multi-channel wireless systems. Submitted to IEEE Transactions on Information Theory, 2007. Available at http://www.cs.duke.edu/~kamesh/partialinfo.pdf.
• 19: David Heckerman , Dan Geiger , David M. Chickering, Learning Bayesian Networks: The Combination of Knowledge and Statistical Data, Machine Learning, v.20 n.3, p.197-243, Sept. 1995 [doi>10.1023/A:1022623210503]
• 20: [20] M. J. Kearns, Y. Mansour, and A. Y. Ng. Approximate planning in large POMDPs via reusable trajectories. In NIPS, pages 1001-1007, 1999.
• 21: Jon Kleinberg , Yuval Rabani , Éva Tardos, Allocating Bandwidth for Bursty Connections, SIAM Journal on Computing, v.30 n.1, p.191-217, 2000 [doi>10.1137/S0097539797329142]
• 22: Anton J. Kleywegt , Alexander Shapiro , Tito Homem-de-Mello, The Sample Average Approximation Method for Stochastic Discrete Optimization, SIAM Journal on Optimization, v.12 n.2, p.479-502, 2002 [doi>10.1137/S1052623499363220]
• 23: [23] A. Krause and C. Guestrin. Near-optimal nonmyopic value of information in graphical models. Proc. 21st Conf. on Uncertainty in Artificial Intelligence, 2005.
• 24: Steven H. Low , David E. Lapsley, Optimization flow control—I: basic algorithm and convergence, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.861-874, Dec. 1999 [doi>10.1109/90.811451]
• 25: Omid Madani , Daniel J. Lizotte , Russell Greiner, Active model selection, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.357-365, July 07-11, 2004, Banff, Canada
• 26: Rolf H. Möhring , Andreas S. Schulz , Marc Uetz, Approximation in stochastic scheduling: the power of LP-based priority policies, Journal of the ACM (JACM), v.46 n.6, p.924-942, Nov. 1999 [doi>10.1145/331524.331530]
• 27: Andrew W. Moore , Jeff G. Schneider , Justin A. Boyan , Mary S. Lee, Q2: Memory-Based Active Learning for Optimizing Noisy Continuous Functions, Proceedings of the Fifteenth International Conference on Machine Learning, p.386-394, July 24-27, 1998
• 28: Raymond H. Myers , Douglas C. Montgomery, Response Surface Methodology: Process and Product in Optimization Using Designed Experiments, John Wiley & Sons, Inc., New York, NY, 1995
• 29: [29] J. Schneider and A. Moore. Active learning in discrete input spaces. The 34th Interface Symposium, Montreal, Quebec, 2002.
• 30: David B. Shmoys , Chaitanya Swamy, Stochastic Optimization is (Almost) as easy as Deterministic Optimization, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.228-237, October 17-19, 2004 [doi>10.1109/FOCS.2004.62]
• 31: Martin Skutella , Marc Uetz, Scheduling precedence-constrained jobs with stochastic processing times on parallel machines, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.589-590, January 07-09, 2001, Washington, D.C., United States
• 32: [32] J. N. Tsitsiklis. A short proof of the Gittins index theorem. Annals of Applied Probability, 4(1):194-199, 1994.
• 33: [33] P. Whittle. Restless bandits: activity allocation in a changing world. Journal of applied probability, 25(A):287-298, 1988.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
algorithms, approximation, learning