Approachability, fast and slow
Approachability, fast and slow
复制标题
平易近人，快和慢
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Shie Mannor
中科院分区：
文献类型：
--
作者：
Vianney Perchet;Shie Mannor
可接近性已经成为分析重复游戏和在线学习的核心工具。一个参与者与自然进行重复的向量值博弈，她的目标是让她的长期平均奖励在某个目标集内。著名的结果Blackwell提供了一个1= p n收敛速度的预期点到集的距离，如果这是可以实现的，即，如果可以接近的话。在本文中，我们提供了一个表征的收敛速度的可逼近性，并表明，在某些情况下，一组可以接近1=n的速度。我们的特征是完全基于几何属性的集合与重复游戏的属性的组合，而不是对自然的行为的额外限制性假设。
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= p 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.