Parit

解决奇偶校验和支付游戏的最优策略改进算法⋆

摘要。本文提出了一种用于奇偶和支付游戏的新型策略改进算法，该算法保证在每个改进步骤中选择一个局部策略修改的最佳组合。当前的策略改进方法使用具有两个不同阶段的算法，根据某些排名函数逐步改进一个玩家的策略：它们首先从局部有利可图的更改列表中选择一个玩家策略的修改，然后评估修改后的策略。这种分离是不幸的，因为当前的策略改进算法除了将各个局部修改分类为有利可图、对抗性或陈旧性之外，没有有效的方法来预测单个局部修改的全局影响。此外，它们完全看不到不同修改的交叉影响：应用一种有利可图的修改可能会使所有其他有利可图的修改都具有对抗性。我们的新构造克服了传统的选择和评估策略修改之间的分离。因此，它通过在每个步骤中提供最佳改进，从所有有利可图和陈旧更改的超集中选择最佳的局部更新组合，从而改进了当前的策略改进算法。