机构名称：
¥ 2.0
我们提出了一种通用策略改进算法 (GSIA) 来寻找简单随机博弈 (SSG) 的最优策略。我们证明了 GSIA 的正确性，并推导出一个一般复杂度界限，它暗示并改进了几篇文章的结果。首先，我们删除了 SSG 停止的假设，这通常是通过博弈的多项式爆炸获得。其次，我们证明了与策略相关的值的分母的严格界限，并使用它来证明所有策略改进算法实际上都是随机顶点数量 r 的固定参数可处理的。所有已知的策略改进算法都可以看作是 GSIA 的实例，这允许分析 Condon [ 14 ] 从下方收敛的复杂性，并提出一类推广 Gimbert 和 Horn 算法的算法 [ 16 ， 17 ]。这些算法最多在 r 中终止！迭代次数，对于二进制 SSG，它们的迭代次数比 Ibsen-Jensen 和 Miltersen [18] 给出的当前最佳确定性算法要少。
简单随机博弈的通用策略改进方法
主要关键词
相关文件推荐
