Approachability, fast and slow
published: Aug. 9, 2013, recorded: June 2013, views: 3036
Report a problem or upload filesIf 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.
Approachability has become a central tool in the analysis of repeated games and online learning. A player plays a repeated vector-valued game against Nature and her objective is to have her long-term average reward inside some target set. The celebrated results of Blackwell provide a 1/n−√ convergence rate of the expected point-to-set distance if this is achievable, i.e., if the set is approachable. In this paper we provide a characterization for the convergence rates of approachability and show that in some cases a set can be approached with a 1/n rate. Our characterization is solely based on a combination of geometric properties of the set with properties of the repeated game, and not on additional restrictive assumptions on Nature’s behavior.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !