Material Detail

Explorations in Computer Go, Web Search, and Online Advertising

Explorations in Computer Go, Web Search, and Online Advertising

This video was recorded at Workshop on On‐lineTrading of Exploration and Exploitation 2, Washington 2011. In computer go, the goal is to find a good move in a given position by exploring the associated game tree, which is far too large to enumerate and hence requires sophisticated methods for navigation. I will discuss our combined Monte-Carlo Tree Search and Bayesian Pattern Ranking approach to accomplish this task under severe resource constraints in the go engine of the Xbox Live Arcade title The Path of Go. In web search, decisions about ranking documents can depend on explicit feedback from external judges and on implicit feedback from users through their interaction with search results. In the latter case, user feedback about a query-URL pair can only be obtained if the URL is actually shown to the user, i.e., exploring it. I will discuss bandit approaches to address this problem, and the need to present diverse search results. Paid search advertising differs from web search in a number of ways, including a smaller, better curated set of documents (ads) and an auction driven allocation mechanism explicitly based on click-through rate. I will describe the adPredictor system used for click-through rate prediction today, and discuss the causal loop created by the fact that only ads shown can be clicked on by the user and are hence available as training examples in the future. I will discuss possible approaches to exploration vs exploitation in practice, and mention some of the open problems arising in such large-scale closed-loop systems. People involved in this work include Filip Radlinski, Joaquin Quiñonero Candela, Ralf Herbrich, and David Stern.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.