We formulate the novel class of contextual games, a type of repeated games driven by contextual information at each round. By means of kernel-based regularity assumptions, we model the correlation between different contexts and game outcomes and propose a novel online (meta) algorithm that exploits such correlations to minimize the contextual regret of individual players. We define game-theoretic notions of contextual Coarse Correlated Equilibria (c-CCE) and optimal contextual welfare for this new class of games and show that c-CCEs and optimal welfare can be approached whenever players' contextual regrets vanish. Finally, we empirically validate our results in a traffic routing experiment, where our algorithm leads to better performance and higher welfare compared to baselines that do not exploit the available contextual information or the correlations present in the game.
翻译:我们设计了新的背景游戏类别, 一种由每回合背景信息驱动的重复游戏类型。 我们通过基于内核的规律性假设, 模拟不同背景和游戏结果之间的相互关系, 并提出一种新的在线( meta) 算法, 利用这些关联来最大限度地减少个别玩家的背景遗憾。 我们定义了背景Cor- 相关 Equilibria (c- CCE) 的游戏理论概念, 以及这一新类型的游戏的最佳背景福利, 并显示当玩家的背景后悔消失时, 可以使用 C- CEC 和最佳福利 。 最后, 我们用经验验证了交通路线实验的结果, 我们的算法导致更好的性能和更高的福利, 而不是利用现有背景信息或游戏中存在的关联的基线 。