We study a version of the classical zero-sum matrix game with unknown payoff matrix and bandit feedback, where the players only observe each others actions and a noisy payoff. This generalizes the usual matrix game, where the payoff matrix is known to the players. Despite numerous applications, this problem has received relatively little attention. Although adversarial bandit algorithms achieve low regret, they do not exploit the matrix structure and perform poorly relative to the new algorithms. The main contributions are regret analyses of variants of UCB and K-learning that hold for any opponent, e.g., even when the opponent adversarially plays the best-response to the learner's mixed strategy. Along the way, we show that Thompson fails catastrophically in this setting and provide empirical comparison to existing algorithms.


翻译:我们研究经典零和矩阵游戏的版本,其报酬矩阵和强盗反馈未知,玩家只观察对方的行动和吵闹的回报。这概括了通常的矩阵游戏,玩家们知道报酬矩阵。尽管有许多应用,但这个问题相对没有引起注意。虽然对抗性强盗算法取得了低度的遗憾,但它们并没有利用矩阵结构,并且与新的算法相比表现不佳。主要贡献是对UCB和K学习的变量进行遗憾分析,这些变量支持任何对手,例如,即使敌对对手对学习者的混合策略发挥最佳反应。顺便一提,我们表明Thompson在这种环境下没有灾难性的失败,并且提供了与现有算法的实验性比较。

0
下载
关闭预览

相关内容

【图与几何深度学习】Graph and geometric deep learning,49页ppt
【反馈循环自编码器】FEEDBACK RECURRENT AUTOENCODER
专知会员服务
22+阅读 · 2020年1月28日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
神器Cobalt Strike3.13破解版
黑白之道
12+阅读 · 2019年3月1日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2021年8月11日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关资讯
神器Cobalt Strike3.13破解版
黑白之道
12+阅读 · 2019年3月1日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员