 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
 |
|
|||||||||||||
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
|||
 |
 |
 |
 |
|
||||||||||
 |
|
|||||||||||||
 |
|
|||||||||||||
 |
 |
|
||||||||||||
| Seminar Schedule (Seminar Organizer: Prof. Ziv Bar-Joseph) | |
Machine Learning Lunch Seminar
|
Fall 2008 Seminar
Date: November 3, 2008 Time: 4:30 PM - 00:00 AM Location: CIC Bldg, Lower Level Other Speaker: Robert Kleinberg Assistant Professor, Cornell University Title: Multi-armed bandit problems in metric spaces Abstract: Multi-armed bandit problems constitute a well-studied abstraction of the exploration/exploitation tradeoffs inherent in many sequential decision making problems. A broad range of computing applications require bandit algorithms with a large but structured set of alternatives. Often this structure takes the form of a metric: a distance function expressing the decision-maker's prior knowledge that certain alternatives will have similar payoffs. This talk focuses on two such applications, one in electronic commerce and the other in web advertising. We will show how both applications can be formulated as special cases of a general problem, the "Lipschitz multi-armed bandit problem," which generalizes the classical multi-armed bandit problem by allowing for a large (possibly uncountable) decision set comprising the points of a metric space. We will define an invariant that precisely determines the performance of the best possible algorithm for this problem in a given metric, and we will describe an algorithm that meets this bound. This is joint work with Alex Slivkins and Eli Upfal.
