悉尼科大应明生团队 | AI+量子计算：量子MDP的最优决策

论文题名：Optimal Policies for Quantum Markov Decision Processes

论文作者：Ming-Sheng Ying, Yuan Feng, Sheng-Gang Ying

全文链接：https://link.springer.com/article/10.1007/s11633-021-1278-z

马尔可夫决策过程(MDP)为序贯决策建模构建了一个通用框架，特别是为强化学习提供了一个数学框架。本文将MDP扩展为量子MDP(qMDP)，qMDP可以作为量子系统决策的数学模型。本文还提出了一种动态规划算法，可用于策略评估，在有限视域(finite-horizon)中找到qMDPs的最优策略。本文所得到的结论为强化学习技术应用于量子世界提供了一些有用的数学工具。

图片来自Springer

马尔可夫决策过程(Markov Decision Process, MDP)是序贯决策(sequential decision)的数学模型，用于在系统状态具有马尔可夫性质的环境中模拟智能体可实现的随机性策略与回报。MDP的得名来自于俄国数学家安德雷·马尔可夫，以纪念其为马尔可夫链所做的研究。

MDP基于一组交互对象，即智能体和环境进行构建，所具有的要素包括状态、动作、策略和奖励。在MDP的模拟中，智能体会感知当前的系统状态，按策略对环境实施动作，从而改变环境的状态并得到奖励，奖励随时间的积累被称为回报。

在应用方面，MDP被用于机器学习中强化学习问题的建模。通过使用动态规划、随机采样等方法，MDP可以求解使回报最大化的智能体策略，并在自动控制、推荐系统等主题中得到应用。

作为强化学习的模型，MDP适用于很多与强化学习有关的实际问题，包括自动控制领域的人机交互系统、自动驾驶系统、导航系统；运筹学领域的广告/销售问题、投资组合问题等。MDP也可以作为模型构建一些具有博弈性质的强化学习系统，例如国际象棋和围棋AI。

1.1 量子马尔科夫决策过程(Quantum Markov decision processes)

最近，MDPs以两种稍有不同的方式进入了量子世界：

1)Barry等人提出量子可观察马尔可夫决策过程(quantum observable Markov decision process, QOMDP)的概念。这一概念是对Kaelbling等人POMDP概念的在量子领域的泛化(quantum generalisation)。

2)另一种对MDPs量子泛化的概念为qMDP，qMDP由应明生等人提出。QOMDPs和qMDPs的主要区别在于QOMDP中的策略是直接将(纯的或混合的)量子态映射到动作，而qMDP则是将量子态的测量结果映射到动作。

1.2 量子机器学习(Quantum machine learning)

在过去的五至十年间，一条新的研究路线在量子物理(quantum physics)和人工智能&机器学习的交叉领域迅速兴起。这两个领域之间的交流是双向的：

1) 通过量子计算(quantum computation)，量子物理有助于解决人工智能及机器学习中的问题。

2) 人工智能&机器学习的方法和技术可用来解决量子物理中的问题。

强化学习是一种基本的机器学习范式(paradigm)，在这种范式中，智能体通过与动态环境的试错交互来学习行为。当前学界已经提出几种量子强化学习模型，可在量子世界中应用强化学习，或基于量子优势来提升强化学习。由此便产生了一个问题：量子马尔可夫决策过程(quantum Markov decision processes)是如何作为量子强化学习的数学框架的？

1.3 本文贡献

经典强化学习中的关键一步是找到智能体的最优行为，该最优行为通常能帮助制定MDPs中的最优策略(optimal policy)。本文解决了量子马尔可夫决策过程的最优策略问题，为量子世界中的决策和强化学习提供了一个有用的数学工具。本文主要研究有限视域(finite horizon)的情形。本文采用了一个模型，该模型扩展了此前所定义的qMDP。

本文结构如下：第二部分以AI界更易理解的方式简要综述了量子力学(Quantum mechanics)。第三部分定义了几个基本概念，包括qMDP、策略(policy)和预期回报(expected reward)。第四部分为确定策略下(with a given policy)的预期回报(expected reward)建立了一种后向回归机制(backward recursion)，并基于此提出了可计算预期回报的算法。第五部分将Bellman的最优性原理(Bellman principle of optimality)推广(generalised)到qMDPs，给出了qMDPs最优策略的求解算法。第六部分集中讨论量子概率的计算，并在第七部分举出实例验证。本文最后给出了结论及未来的研究方向。

来源：《International Journal of Automation and Computing》编辑部