The ratio index for budgeted learning, with applications

ABSTRACT

In the budgeted learning problem, we are allowed to experiment on a set of alternatives (given a fixed experimentation budget) with the goal of picking a single alternative with the largest possible expected payoff. Constant factor approximation algorithms for this problem were developed by Guha and Munagala by rounding a linear program that couples the various alternatives together. In this paper we present an index for this problem, which we call the ratio index, which also guarantees a constant factor approximation. Index-based policies have the advantage that a single number (i.e. the index) can be computed for each alternative irrespective of all other alternatives, and the alternative with the highest index is experimented upon. This is analogous to the famous Gittins index for the discounted multi-armed bandit problem.

The ratio index has several interesting structural properties. First, we show that it can be computed in strongly polynomial time. Second, we show that with the appropriate discount factor, the Gittins index and our ratio index are constant factor approximations of each other, and hence the Gittins index also gives a constant factor approximation to the budgeted learning problem. Finally, we show that the ratio index can be used to create an index-based policy that achieves an O(1)-approximation for the finite horizon version of the multi-armed bandit problem. Moreover, the policy does not require any knowledge of the horizon (whereas we compare its performance against an optimal strategy that is aware of the horizon). This yields the following surprising result: there is an index-based policy that achieves an O(1)-approximation for the multi-armed bandit problem, oblivious to the underlying discount factor.

REFERENCES

• 1: P. Bhattacharya, L. Georgiadis, and P. Tsoucas. Extended Polymatroids, Properties, and Optimization. Integer Programming and Combinatorial Optimization, IPCO2, ed. E. Bala, G Cornnejols, and R. Kannan, Carnegie-Mellon University 298--315, 1992.
• 2: R. Bellman. A Problem in the Sequential Design of Experiments. Sankhia, 16:221--229, 1956.
• 3: 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]
• 4: 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]
• 5: A. Blum and Y. Mansour. Learning, Regret Minimization, and Equilibria. Algorithmic Game Theory, ed. N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani. 79--102, 2007.
• 6: M. Charikar, C. Chekuri, and M. Pal. Sampling Bounds for Stochastic Optimization. APPROX-RANDOM 257--269, 2005.
• 7: 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, p.208-217, October 17-19, 2004 [doi>10.1109/FOCS.2004.15]
• 8: 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
• 9: E. Frostig and G. Weiss. Four Proofs of Gittins' Multiarmed Bandit Theorem. Applied Probability Trust, November 10, 1999.
• 10: J. C. Gittins and D. M. Jones. A Dynamic Allocation Index for the Sequential Design of Experiments. Progress in Statistics: European Meeting of Statisticians, Budapest, 1972, ed. J. Ganu, K. Sarkadi, and I. Vince. 241--266, 1974.
• 11: J. C. Gittins. Bandit Processes and Dynamic Allocation Indices. J Royal Statistical Societe Series B, 14:148--167, 1979.
• 12: J. C. Gittins. Multiarmed Bandits Allocation Indices, Wiley, New York, 1989.
• 13: K. D. Glazebrook and R. Garbe. Almost Optimal Policies for Stochastic Systems which Almost Satisfy Conservation Laws. Annals of Operations Research, 92:19--43, 1999.
• 14: K. D. Glazebrook and D. J. Wilkinson. Index-Based Policies for Discounted Multi-armed Bandits on Parallel Machines. The Annals of Applied Probability, 10:3:877--896, 2000.
• 15: 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]
• 16: 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
• 17: A. Goel, S. Khanna, and B. Null. The Ratio Index for Budgeted Learning, with Applications. Math arXiv:0810.0558v1, http://arxiv.org/abs/0810.0558.
• 18: 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
• 19: 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]
• 20: 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]
• 21: D. Luenberger. Linear and Nonlinear Programming, Reading, MA, 1984.
• 22: 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
• 23: Paat Rusmevichientong , David P. Williamson, An adaptive algorithm for selecting profitable keywords for search-based advertising services, Proceedings of the 7th ACM conference on Electronic commerce, p.260-269, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134736]
• 24: J. Schneider and A. Moore. Active Learning in Discrete Input Spaces. Proceedings of the 34th Interface Symposium, 2002.
• 25: 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, p.228-237, October 17-19, 2004 [doi>10.1109/FOCS.2004.62]
• 26: P. Tsoucas. The Region of Achievable Performance in a Model of Klimov. Research Report RC16543, IBM T. J. Watson Research Center, Yorktown Heights, New York, 1991.
• 27: A. Wald. Sequential Analysis, J. Wiley & Sons, New York, 212p, 1947.
• 28: P. Whittle. Restless Bandits: Activity Allocation in a Changing World. A Celebration of Applied Probability. J. Applied Probability, 25A:287--298, 1988.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation