|
Activity Number:
|
402
|
|
Type:
|
Invited
|
|
Date/Time:
|
Wednesday, August 5, 2009 : 8:30 AM to 10:20 AM
|
|
Sponsor:
|
IMS
|
| Abstract - #303214 |
|
Title:
|
Combinatorial Problems in Randomized Sequential Prediction
|
|
Author(s):
|
Gabor Lugosi*+
|
|
Companies:
|
ICREA and Pompeu Fabra University, Barcelona
|
|
Address:
|
, , ,
|
|
Keywords:
|
|
|
Abstract:
|
We discuss sequential prediction problems in which a decisionmaker repeatedly chooses an action and suffers a loss related to that action. The goal of the decisionmaker is to accumulate a total loss that is not much larger than the best fixed action that could have been chosen if all losses were known in advance. This problem and its variants have been thoroughly studied in statistics, game theory, learning theory, and information theory, and various well-performing randomized strategies exist. We consider cases in which the set of actions is large and has some combinatorial structure. We study multi-armed bandit problems, that is, when the decisionmaker only observes the loss of the selected action. We present a general strategy that allows one to achieve near-optimal performance in many cases. This is joint work with Nicolò Cesa-Bianchi.
|
- The address information is for the authors that have a + after their name.
- Authors who are presenting talks have a * after their name.
Back to the full JSM 2009 program |
