[Colloquium] Kleinberg talk 6/17 12:15 at TTI

[Meridel Trimble]

TOYOTA TECHNOLOGICAL INSTITUTE TALK

Speaker: Robert Kleinberg
MIT

Title: Online Geometric Optimization: New Algorithms and Applications
Time: Thursday, June 17th, 12:15 p.m.

Place: TTI-C (1427 E. 60th St. – 2nd Floor)
LUNCH PROVIDED

Speaker 's Homepage: http://www-math.mit.edu/~rdk/

Abstract:
Imagine that you are a commuter trying to find the fastest way to drive to work.
Each day you choose a route, drive to work along this route, and observe the
total driving time. The delays on the various roads vary from day to day, so
prior observations are not necessarily predictive of future observations. How
should you plan your route based on past experience? In this talk I will present
a randomized algorithm which solves this problem, in the sense that the expected
average cost of the routes chosen by the algorithm exceeds the average cost of
the optimal static route by an amount tending to zero as the number of days
tends to infinity.

This path planning problem is a special case of a "multi-armed bandit problem,"
in which a learner must select a strategy from among a fixed set of alternatives
in each of T consecutive trials so as to minimize the cost of the chosen
strategies, in an environment where the learner is informed of the chosen
strategy's cost, but not the cost of any other strategy. For the case of a small
finite strategy set, efficient algorithms have been known for at least ten
years, and such algorithms have diverse applications in computer science as well
as other fields including economics (pricing strategies), game theory (adaptive
game playing), and medical decision making (optimal design of clinical trials).
However, many potential applications (such as the path planning problem
described above) require us to consider settings where the size of the strategy
set is exponential or even infinite. I will present some new algorithms for
efficiently solving multi-armed bandit problems in this setting, if the strategy
set is embedded in a finite-dimensional vector space and the cost functions are
linear or convex. The solution of the path planning problem follows as a special
case.

Part of this talk is joint work with Baruch Awerbuch of Johns Hopkins University.

If you have questions, or would like to meet the speaker, please contact
Meridel at 4-9873 or mtrimble at tti-c.org