图 书 馆
凸对策中的无遗憾学习No-Regret Learning in Convex Games |
|
| 课程网址: | http://videolectures.net/icml08_gordon_nrl/ |
| 主讲教师: | Geoffrey J. Gordon |
| 开课单位: | 卡内基梅隆大学 |
| 开课时间: | 2008-08-07 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Quite a bit is known about minimizing different kinds of regret in experts problems, and how these regret types relate to types of equilibria in the multiagent setting of repeated matrix games. Much less is known about the possible kinds of regret in online convex programming problems (OCPs), or about equilibria in the analogous multiagent setting of repeated convex games. This gap is unfortunate, since convex games are much more expressive than matrix games, and since many important machine learning problems can be expressed as OCPs. In this paper, we work to close this gap: we analyze a spectrum of regret types which lie between external and swap regret, along with their corresponding equilibria, which lie between coarse correlated and correlated equilibrium. We also analyze algorithms for minimizing these regret types. As examples of our framework, we derive algorithms for learning correlated equilibria in polyhedral convex games and extensive-form correlated equilibria in extensive-form games. The former is exponentially more efficient than previous algorithms, and the latter is the first of its type. |
| 关 键 词: | 重复矩阵; 均衡类型; 线凸规划 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-04-18：cwx |
| 阅读次数: | 104 |