How to solve large scale deterministic games with mean payoff by policy iteration
How to solve large scale deterministic games with mean payoff by policy iteration
复制标题
DOI：
10.1145/1190095.1190110
复制
发表时间：
2006-10
期刊：
影响因子：
--
通讯作者：
Vishesh Dhingra;S. Gaubert
中科院分区：
文献类型：
--
作者：
Vishesh Dhingra;S. Gaubert
最小-最大函数是具有有限状态和动作空间的零和确定性博弈的动态编程运算符。计算最小-最大函数的轨道（周期时间）线性增长率的问题，相当于计算具有平均收益的确定性博弈的值，出现在离散事件系统的性能分析中。我们在这里提出了 Gaubert 和 Gunawardena 在 1998 年提出的策略迭代算法的改进版本，用于计算最小-最大函数的周期时间。改进包括对光谱投影仪的快速评估，该光谱投影仪适用于大型稀疏图的情况。我们在随机生成的实例和具体示例上进行了详细的数值实验，表明该算法在实验上速度很快。
Min-max functions are dynamic programming operators of zero-sum deterministic games with finite state and action spaces. The problem of computing the linear growth rate of the orbits (cycle-time) of a min-max function, which is equivalent to computing the value of a deterministic game with mean payoff, arises in the performance analysis of discrete event systems. We present here an improved version of the policy iteration algorithm given by Gaubert and Gunawardena in 1998 to compute the cycle-time of a min-max functions. The improvement consists of a fast evaluation of the spectral projector which is adapted to the case of large sparse graphs. We present detailed numerical experiments, both on randomly generated instances, and on concrete examples, indicating that the algorithm is experimentally fast.