文章解析
文章针对大规模马尔可夫决策过程(MDPs)中优化可解释策略计算难题,改进单调策略迭代算法(MPI),提出 MMPI 算法,研究不同状态排序规则对其影响,并通过实验对比分析,为求解可解释策略提供参考。
创新点
分析MPI算法的收敛性和最优性,证明其存在不收敛及不收敛到最优解的情况,为改进算法提供依据。
提出MMPI算法,通过改变终止条件和记录最优策略,保证算法收敛且在一定条件下优于MPI算法。
设计19种状态排序规则,量化其对MMPI算法性能影响,发现随机排序规则在最优性差距上表现出色。
研究方法
理论分析:推导MPI和MMPI算法的相关性质,证明收敛性、最优性等理论结果。
构建模型:构建具有可证明存在最优单调策略的机器维护问题模型,作为实验测试平台。
实验设计:在机器维护和随机生成的MDPs上,用多种状态排序规则测试MMPI算法性能。
对比分析:对比不同状态排序规则下MMPI算法的计算时间、最优性差距等指标。
研究结论
MMPI算法比MPI算法具有更好的理论性质,在求解可解释策略时能找到更高质量的策略。
选择MMPI算法的状态排序规则时存在计算时间和最优性差距的权衡,随机排序规则在保证较低最优性差距上有优势。
结构化问题更利于MMPI算法和MILP求解,为实际应用中选择算法和排序规则提供指导。