马尔可夫决策问题的关键状态优先学习算法

白尘

[摘 要] 针对传统强化学习算法的维数灾难问题，首先提出了用于识别关键状态的“决策收益率”概念及其估算方法，然后借鉴学习范围扩展的思想，以经典Q-Learning学习算法为基础，提出了关键状态优先学习算法（Critical States Prioritized Learning，CSPL）。最后本文实现了机器人寻径实验，并比较了CSPL算法与Q-Learning算法的实验结果。

[关键词] 马尔可夫决策；关键状态；决策收益率；关键状态优先学习算法

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2016. 07. 092

[中图分类号] TP311 [文献标识码] A [文章编号] 1673 - 0194（2016）07- 0198- 05

1 引 言

马尔可夫决策过程（Markov Decision Process，MDP）模型被广泛用于描述通讯网络、金融工程、制造系统和人工智能等领域的序贯决策问题[1]。强化学习算法（Reinforcement Learning，RL）是MDP问题的一类重要解决方法[2]。在解决复杂MDP问题时，传统强化学习算法面临着“维数灾难”问题，即随着状态空间和行为空间维数增大，算法的学习空间和学习时间呈指数增长[3]。

维数灾难问题的常用解决方法是分层强化学习（Hierarchical Reinforcement Learning）[4]和学习范围扩展（Learning Scale Extension）[5]。分层强化学习将原有决策问题分解为由多个子任务构成的层次结构以提高整体效率，但是构建层次结构需要依赖大量先验知识；学习范围扩展是通过学习状态空间结构信息以扩大一次学习所影响的状态范围，若学习范围设定不合理，需要耗费大量运算时间和空间记忆额外信息。两种解决方法的实用性较低。

本文针对传统强化学习算法的维数灾难问题，提出了一种新的思路：优先学习对整体决策效果影响较大的“关键状态”，从而提高复杂状态空间下的整体决策效率。本文首先提出“决策收益率”的概念和估计方法，解决了“如何识别关键状态”的问题；然后提出“逆向学习”的方法，解决了“如何优先学习关键状态”的问题；并借鉴学习范围扩展的思想，以经典Q-Learning学习算法[6]为基础，提出了关键状态优先学习算法。