Efficient exploration of zero-sum stochastic games
Efficient exploration of zero-sum stochastic games
复制标题
DOI：
--
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Carlos Martin;T. Sandholm
中科院分区：
文献类型：
--
作者：
Carlos Martin;T. Sandholm
我们研究日益重要和常见的游戏解决设置，在这种设置中，我们没有对游戏的明确描述，而只能通过游戏玩法（例如在金融或军事模拟和计算机游戏中）访问它。在有限持续时间的学习阶段，算法可以控制两个玩家的动作，以便尝试学习游戏以及如何玩好游戏。之后，算法必须产生可利用性较低的策略。我们的动机是在评估查询策略配置文件的回报成本高昂的情况下快速学习可利用性较低的策略。对于随机博弈设置，我们建议使用由可能环境上的信念分布引起的状态动作价值函数的分布。我们比较了此任务的各种探索策略的性能，包括 Thompson 采样和 Bayes-UCB 对此新设置的概括。这两种策略始终优于其他策略。
We investigate the increasingly important and common game-solving setting where we do not have an explicit description of the game but only oracle access to it through gameplay, such as in financial or military simulations and computer games. During a limited-duration learning phase, the algorithm can control the actions of both players in order to try to learn the game and how to play it well. After that, the algorithm has to produce a strategy that has low exploitability. Our motivation is to quickly learn strategies that have low exploitability in situations where evaluating the payoffs of a queried strategy profile is costly. For the stochastic game setting, we propose using the distribution of state-action value functions induced by a belief distribution over possible environments. We compare the performance of various exploration strategies for this task, including generalizations of Thompson sampling and Bayes-UCB to this new setting. These two consistently outperform other strategies.