Robust approachability and regret minimization in games with partial monitoring
author: Vianney Perchet,
Probabilities and Random Models Laboratory, Université Pierre et Marie Curie (UPMC)
published: Aug. 2, 2011, recorded: July 2011, views: 3070
published: Aug. 2, 2011, recorded: July 2011, views: 3070
Slides
Related content
Report a problem or upload files
If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Description
Approachability has become a standard tool in analyzing learning algorithms in the adversarial online learning setup. We develop a variant of approachability for games where there is ambiguity in the obtained reward that belongs to a set, rather than being a single vector. Using this variant we tackle the problem of approachability in games with partial monitoring and develop simple and efficient algorithms (i.e., with constant per-step complexity) for this setup. We finally consider external and internal regret in repeated games with partial monitoring, for which we derive regretminimizing strategies based on approachability theory.
Link this page
Would you like to put a link to this lecture on your homepage?Go ahead! Copy the HTML snippet !
Write your own review or comment: