Optimistic Hedge

Optimistic Hedge算法在3+玩家游戏中显示指数级遗憾

一篇新论文介绍了用于General-Sum Games的Optimistic Hedge算法，并分析了其遗憾界限。研究人员发现，在两人游戏中，Optimistic Hedge可以实现与时间无关的$O(n\log n)$遗憾。然而，对于三个或更多玩家，不可能存在这样的恒定遗憾界限，遗憾可能随行动数量呈指数级增长，并随时间呈线性增长。