论文标题
带有强盗反馈的矩阵游戏
Matrix games with bandit feedback
论文作者
论文摘要
我们研究了带有未知的回报矩阵和匪徒反馈的经典零和矩阵游戏的版本，在那里玩家只观察到彼此的动作和嘈杂的回报。这概括了通常的矩阵游戏，其中播放器已知收益矩阵。尽管有许多应用，但这个问题的关注却相对较少。尽管对抗性的匪徒算法会产生低遗憾，但它们并没有利用矩阵结构，并且相对于新算法的表现不佳。主要的贡献是对UCB和K-Learning的变体的遗憾分析，例如，即使对手对手对学习者的混合策略发挥了最佳反应，也是如此。在此过程中，我们表明汤普森在这种情况下灾难性失败，并提供了与现有算法的经验比较。
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.
