Multi-armed bandit problems with dependent arms

ABSTRACT

We provide a framework to exploit dependencies among arms in multi-armed bandit problems, when the dependencies are in the form of a generative model on clusters of arms. We find an optimal MDP-based policy for the discounted reward case, and also give an approximation of it with formal error guarantee. We discuss lower bounds on regret in the undiscounted reward scenario, and propose a general two-level bandit policy for it. We propose three different instantiations of our general policy and provide theoretical justifications of how the regret of the instantiated policies depend on the characteristics of the clusters. Finally, we empirically demonstrate the efficacy of our policies on large-scale real-world and synthetic data, and show that they significantly outperform classical policies designed for bandits with independent arms.

REFERENCES

• 1: Agrawal, R. (1995). Sample mean based index policies with O(log n) regret for the multi-armed bandit problem. Advances in Applied Probability, 27, 1054--1078.
• 2: Chang, F., & Lai, T. L. (1987). Optimal stopping and dynamic allocation. Advances in Applied Probability, 19, 829--853.
• 3: Dasgupta, S. (2005). Coarse sample complexity bounds for active learning. NIPS.
• 4: Frostig, E., & Weiss, G. (1999). Four proofs of Gittins' multiarmed bandit theorem. Applied Probability Trust.
• 5: J. C. Gittins (1979). Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society, Series B, 41, 148--177.
• 6: Kocsis, L., & Szepesváári, C. (2006). Bandit based monte-carlo planning. ECML.
• 7: Lai, T. L. (1987). Adaptive treatment allocation and multi-armed bandit problem. Annals of Statistics, 15(3), 1091--1114.
• 8: Lai, T. L., & Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6, 4--22.
• 9: David J. C. MacKay, Information-based objective functions for active data selection, Neural Computation, v.4 n.4, p.590-604, July 1992 [doi>10.1162/neco.1992.4.4.590]
• 10: Pandey, S., Agarwal, D., Chakrabarti, D., & Josifovski, V. (2007). Bandits for taxonomies: A model-based approach. SDM.
• 11: 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]
• 12: Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., New York, NY, 1994
• 13: Schneider, J., & Moore, A. (2002). Active learning in discrete input spaces. The 34th Interface Symposium.
• 14: Wang, C.-C., Kulkarni, S. R., & Poor, H. (2005). Bandit problems with side observations. IEEE Transactions on Automatic Control, 50(3), 338--355.
• 15: Whittle, P. (1980). Multi-armed bandits and the Gittins index. Journal of the Royal Statistcal Society B, 42, 143--149.