Exploration scavenging

ABSTRACT

We examine the problem of evaluating a policy in the contextual bandit setting using only observations collected during the execution of another policy. We show that policy evaluation can be impossible if the exploration policy chooses actions based on the side information provided at each time step. We then propose and prove the correctness of a principled method for policy evaluation which works when this is not the case, even when the exploration policy is deterministic, as long as each action is explored sufficiently often. We apply this general technique to the problem of offline evaluation of internet advertising policies. Although our theoretical results hold only when the exploration policy chooses ads independent of side information, an assumption that is typically violated by commercial systems, we show how clever uses of the theory provide non-trivial and realistic applications. We also provide an empirical demonstration of the effectiveness of our techniques on real ad placement data.

REFERENCES

• 1: Alon, N., & Spencer, J. (2000). The probabilistic method. Interscience Series in Discrete Mathematics and Optimization. John Wiley. Second edition.
• 2: 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]
• 3: 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 (FOCS'95), p.322, October 23-25, 1995
• 4: Berry, D. A., & Fristedt, B. (1985). Bandit problems: Sequential allocation of experiments. London, UK: Chapman and Hall.
• 5: Christian Borgs , Jennifer Chayes , Nicole Immorlica , Kamal Jain , Omid Etesami , Mohammad Mahdian, Dynamics of bid optimization in online advertisement auctions, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242644]
• 6: Dupret, G., Murdock, V., & Piwowarski, B. (2007). Web search engine evaluation using clickthrough data and a user model. 16th Intl. World Wide Web Conference.
• 7: Eyal Even-Dar , Shie Mannor , Yishay Mansour, Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems, The Journal of Machine Learning Research, 7, p.1079-1105, 12/1/2006
• 8: Heckman, J. (1979). Sample selection bias as a specification error. Econometrica, 47, 153--161.
• 9: Kalervo Järvelin , Jaana Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM Transactions on Information Systems (TOIS), v.20 n.4, p.422-446, October 2002 [doi>10.1145/582415.582418]
• 10: Leslie Pack Kaelbling, Associative Reinforcement Learning: A Generate and Test Algorithm, Machine Learning, v.15 n.3, p.299-319, June 1994 [doi>10.1023/A:1022642026684]
• 11: Sébastien Lahaie , David M. Pennock, Revenue analysis of a family of ranking rules for keyword auctions, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250918]
• 12: T L Lai, Asymptotically efficient adaptive control in Stochastic regression models, Advances in Applied Mathematics, v.7 n.1, p.23-45, March 1986 [doi>10.1016/0196-8858(86)90004-7]
• 13: Langford, J., & Zhang, T. (2007). The epoch greedy algorithm for contextual multi-armed bandits. Advances in Neural Information Processing Systems.
• 14: Wang, C.-C., Kulkarni, S. R., & Poor, H. V. (2005). Bandit problems with side observations. IEEE Transactions on Automatic Control, 50, 338--355.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory