Fast Planning in Stochastic Games
Fast Planning in Stochastic Games
复制标题
随机游戏中的快速规划
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Satinder Singh
中科院分区：
文献类型：
--
作者：
M. Kearns;Y. Mansour;Satinder Singh
随机游戏将马尔可夫决策过程（MDP）推广到多智能体环境，允许状态转换共同依赖于所有玩家的行为，并在每个状态下由多人矩阵游戏确定奖励。我们考虑在随机博弈中计算纳什均衡的问题，类似于MDP中的规划。我们开始通过提供一个简单的推广有限时域值迭代计算一般和随机博弈中每个玩家的纳什策略。该算法采用任意的纳什选择函数作为输入，它允许将多个纳什均衡之间的局部选择转化为单个全局纳什均衡的选择。
我们的主要技术成果是一个算法计算近纳什均衡在大型或无限的状态空间。该算法建立在我们的有限时域值迭代算法的基础上，并将Kearns，Mansour和Ng（1999）的稀疏采样方法应用于随机博弈。最后，我们通过描述一个反例表明，无穷时域贴现值迭代，这是由Shapley收敛于零和的情况下（结果，我们给稍微扩展这里），不收敛于一般和的情况下。
Stochastic games generalize Markov decision processes (MDPs) to a multiagent setting by allowing the state transitions to depend jointly on all player actions, and having rewards determined by multiplayer matrix games at each state. We consider the problem of computing Nash equilibria in stochastic games, the analogue of planning in MDPs. We begin by providing a simple generalization of finite-horizon value iteration that computes a Nash strategy for each player in general-sum stochastic games. The algorithm takes an arbitrary Nash selection function as input, which allows the translation of local choices between multiple Nash equilibria into the selection of a single global Nash equilibrium.
Our main technical result is an algorithm for computing near-Nash equilibria in large or infinite state spaces. This algorithm builds on our finite-horizon value iteration algorithm, and adapts the sparse sampling methods of Kearns, Mansour-and Ng (1999) to stochastic games. We conclude by describing a counterexample showing that infinite-horizon discounted value iteration, which was shown by Shapley to converge in the zero-sum case (a result we give extend slightly here), does not converge in the general-sum case.