Strategy-Based Warm Starting for Regret Minimization in Games
Strategy-Based Warm Starting for Regret Minimization in Games
复制标题
基于策略的热启动，最大限度地减少游戏中的遗憾
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
T. Sandholm
中科院分区：
文献类型：
--
作者：
Noam Brown;T. Sandholm
反事实遗憾最小化 (CFR) 是一种流行的迭代算法，用于在不完美信息多步两人零和博弈中逼近纳什均衡。我们介绍第一个通用的、原则性的热启动 CFR 方法。我们的方法只需要每个玩家一个策略，并以单次遍历博弈树为代价完成热启动。事实证明，该方法可以将 CFR 热启动到达到与输入策略相同质量的策略配置文件所需的迭代次数，并且不会改变算法的收敛范围。与之前的热启动方法不同，我们的方法可以应用于所有情况。我们的方法与输入策略的起源无关。例如，它们可以基于人类领域知识、观察到的强代理策略、较粗略抽象的解决方案，或者某些算法的输出，该算法首先快速收敛，但随着接近平衡而缓慢收敛。实验表明，通过首先在更小、更粗糙的游戏抽象上运行 CFR，然后使用抽象游戏中的策略在完整游戏中热启动 CFR，可以提高游戏中的整体收敛性。
Counterfactual Regret Minimization (CFR) is a popular iterative algorithm for approximating Nash equilibria in imperfect-information multi-step two-player zero-sum games. We introduce the first general, principled method for warm starting CFR. Our approach requires only a strategy for each player, and accomplishes the warm start at the cost of a single traversal of the game tree. The method provably warm starts CFR to as many iterations as it would have taken to reach a strategy profile of the same quality as the input strategies, and does not alter the convergence bounds of the algorithms. Unlike prior approaches to warm starting, ours can be applied in all cases. Our method is agnostic to the origins of the input strategies. For example, they can be based on human domain knowledge, the observed strategy of a strong agent, the solution of a coarser abstraction, or the output of some algorithm that converges rapidly at first but slowly as it gets closer to an equilibrium. Experiments demonstrate that one can improve overall convergence in a game by first running CFR on a smaller, coarser abstraction of the game and then using the strategy in the abstract game to warm start CFR in the full game.