|
|
|
 |
Robert Kleinberg
MIT
Friday, February 20, 2004, 11:00am - 12:00pm
LC 102, Brooklyn Campus, Polytechnic University
In the classical "multi-armed bandit" problem, a gambler in a casino with K slot machines must pick one slot machine in each of a series of consecutive trials, in the face of uncertainty about the current and future payoff distributions of the various alternatives. Algorithms for this problem and related online decision problems have been studied since the 80's and 90's and have been applied in a broad range of contexts from machine learning theory, to data structures, to economics and game theory, to medical decision-making.
A major limitation of the classical algorithms for such problems is their dependence on K, the number of available strategies. In many natural applications, where the set of available strategies is exponential or even infinite, it is necessary to consider algorithms which don't even have enough time to sample each strategy once. We will present two such applications. The first (based on joint work with Tom Leighton) involves pricing strategies for selling a good when the demand curve is unknown to the seller. The second (based on joint work with Baruch Awerbuch) involves online algorithms for selecting a minimum-delay route in a network where the edge delays may vary unpredictably over time.
For more information please contact Joel Wein [wein@mem.poly.edu].