下载掌阅APP，畅读海量书库
立即打开
如果有足够的假设条件，马尔可夫决策过程（Markov Decision Process）是解决随机动态规划问题的一种很好的方法。首先，假设问题具有离散状态集S=（1，2，…，|S|），且状态集数量小到可以遍历。其次，假设决策集也相对较小，而且可以计算给定状态和决策情况下的成本函数。最后，假设转移函数矩阵已知，即如果当前系统处于状态S t 同时采取策略a t ，则系统将转移到状态S t+1 的概率。但在实际问题中，以上的假设都不能同时成立。例如，许多问题涉及连续状态或是状态变量为向量，这种情况下状态集很大且不可能遍历。进而，一步转移概率矩阵就很难计算甚至是无法计算。既然上述假设在实际问题中并不能都成立，为什么还要研究这些理论上的问题呢？首先，实际中确实存在一些小规模的问题满足以上假设。其次，马尔可夫决策可以帮助我们识别问题的结构特点从而大大降低算法的计算量。当然，更为重要的是马尔可夫决策过程是近似动态规划的基础，这一部分的内容将为我们之后讨论和研究近似动态规划奠定基础。
多数随机问题可以通过以下目标函数来建模：
。而对于大多数问题而言，求解这一方程的计算量巨大，但该方程却是识别最优解性质、求解和比较最优解的基础。仔细观察我们可以发现，其实并不需要一次完成整个求解。例如，我们在求解确定性最短路问题时，状态S
t
为当前所在的节点，并且选择下一个节点。如果当前状态S
t
=i，采取行动a
t
=j，通过转移函数S
{t+1}
=S
M
（S
t
，a
t
）就可以得到下一个状态S
{t+1}
=j。如果值函数V
{t+1}
（S
{t+1}
）已知的话，我们就可以通过比较C
t
（S
t
，a
t
）+V
{t+1}
（S
{t+1}
）来进行决策并选择在状态S
t
时的最优化行动方案。通常未来周期的成本或收益都是用货币来度量，我们需要对未来的成本或收益进行折现，即求解以下最优方程
在研究随机问题时，我们需要意识到新的外生信息是在我们采取行动a t 之后，因此在计算收益或成本及确定下一个状态时这部分信息是不确定的。但是如果我们知道外生信息所服从的概率分布，就可以推断出转移概率P（S t+1 |S t ，a t ），即给定状态和策略的前提下，系统转移到S {t+1} 的概率。进而，最优方程为
该方程也称为贝尔曼方程的标准形式。这种形式在动态规划中常用，而在近似动态规划中，更为常用的是贝尔曼方程的期望形式，即
在随机动态规划中通常会假设一步转移概率矩阵P π 已知。在实际中，我们可以假设转移函数S M （S t ，a t ，W {t+1} ）已知，从而进一步推导出一步转移概率。假设在时刻t和t+1之间产生的外生随机信息ω {t+1} 独立于所有之前的历史信息。Ω {t+1} 是ω {t+1} 所有可能出现的结果，P（ω {t+1} ）为结果ω {t+1} 发生的概率。同时，定义以下指标函数。
我们可以将一步转移概率P（S t+1 |S t ，a t ）写成
因此，构造一步转移概率只需从一个特定的状态-行为对（S t ，a t ）到状态S {t+1} 的所有概率加起来即可。有的情况下，以上的计算很简单，但另外一些情况下，计算基本不可能。例如，ω {t+1} 可以是价格或需求的一个向量，这样Ω {t+1} 就会大到无法进行遍历。当然，我们可以从统计的角度对转移概率矩阵进行估计。
在许多实际应用中，当前周期的贡献函数为S t 和a t 的确定性函数。因此，通常我们会将贡献函数写成确定性函数C t （S t ，a t ），但也有例外。例如，一辆车在一个随机交通网络中行驶，它可能会选择从i到j，但这一段路的成本是在做出决策后才可以知道，这样的话贡献函数就是随机的了。
有限周期问题通常分为两种情形：首先，许多实际问题本身就有一个确定的计划周期。比如，美国期权定价问题，由于资产必须在t≤T卖出，T是期权执行日期。这个问题中计划周期就是有限的。另一个例子是航空公司机票定价问题，同样决策日期受航班时间的影响为有限周期问题。其次，某些问题虽然实际上是无限周期，但求解的目的是研究系统某一段时间的变化。例如，物流公司将司机与货物分配的问题，该问题当期的决策势必会影响未来周期的决策，因此只考虑有限计划周期T。
而对有限周期问题，我们通常假设V T （S t ，a t ）已知，多数情况下为了简便将其设为零。因为我们关注的是当期应该做什么样的决策，以及这之后每一个周期对应的决策。如果计划周期T足够大，我们可以假设每个周期对应的决策是足够好的。求解有限周期问题相对简单。我们只需从最后一个周期开始，计算每个状态对应的值函数，然后逐个周期逆向求解。这就是所谓的逆向动态规划。这一算法的关键点在于要对所有状态求解值函数。最简单的逆向动态规划是决策树。
当所研究的问题中关于贡献函数、转移函数和控制外生信息产生过程的参数都不随时间变化，尽管有时具有周期性时，我们通常会利用无限周期问题来求解，如太阳能的能量取决于所处时间段。同时，我们主要希望研究的是该问题的稳定状态，更为重要的是无限周期问题可以帮助我们发现问题和算法的性质，并为该类问题提供有效的理论基础。无限周期问题可以帮助我们更好地了解较为复杂的非稳态问题。
稳态问题可以看成一个没有时间维度的问题，即V（S）=lim t→∞ V t （S t ），则稳态最优方程为
该方程等同于求解以下无限周期问题
令P
π，t
=t步转移矩阵
，P
{π，0}
为单位矩阵，
为给定状态s和行动a
t
的前提下系统的期望收益，行动a
t
从t时刻开始的无限周期折现值为
假设初始策略为π 0 ，接下来的行动都相同，即π 1 =π 2 =…=π，上式可以写成
求解无限周期问题的方法很多，其中值函数迭代是应用较为广泛的一种，它主要是通过不断对值函数进行逼近，每一次迭代的值函数逼近值决定了将要采取的行动，进而构成策略。第二种方法是策略迭代，即根据某一策略，可以确定该策略对应的值函数值。从以上的描述可以发现，以上两种方法可以看成一类特殊的策略和值函数迭代方法。最后一种主要的方法则将值函数看成一类特殊结构的线性规划问题进行求解。