2.3 最优策略及其性质

前一节我们为策略定义了价值函数。价值函数实际上给出了策略的一个偏序关系：对于两个策略π和π'，如果对于任意s∈，都v_π(s)≤v_π'(s)，则称策略π小于等于π'，记作π≤π'。本节将基于这个偏序关系来定义最优策略，并考虑最优策略的性质和求解。

2.3.1 最优策略与最优价值函数

·对于一个动力而言，总是存在着一个策略π_*，使得所有的策略都小于等于这个策略。这时，策略π_*就称为最优策略（optimal policy）。最优策略的价值函数称为最优价值函数。最优价值函数包括以下两种形式。

·最优状态价值函数（optimal state value function），即

·最优动作价值函数（optimal action value function），即

对于一个动力，可能存在多个最优策略。事实上，这些最优策略总是有相同的价值函数。所以，对于同时存在多个最优策略的情况，任取一个最优策略来考察不失一般性。其中一种选取方法是选择这样的确定性策略：

其中，如果有多个动作a使得q*(s,a)取得最大值，则任选一个动作即可。从这个角度看，只要求得了最优价值函数，就可以直接得到一个最优策略。所以，求解最优价值函数是一个值得关注的重要问题。

2.3.2 Bellman最优方程

最优价值函数具有一个重要的性质——Bellman最优方程（Bellman optimal equation）。Bellman最优方程可以用于求解最优价值函数。

回顾2.2节，策略的价值函数满足Bellman期望方程，最优价值函数也是如此。与此同时，将最优函数的性质：

代入Bellman期望方程，就可以得到Bellman最优方程。

Bellman最优方程有以下两个部分。

·用最优动作价值函数表示最优状态价值函数，备份图见图2-4a：

·用最优状态价值函数表示最优动作价值函数，备份图见图2-4b：

图2-4 最优状态价值函数和最优动作价值函数互相表示的备份图

基于最优状态价值函数和最优动作价值函数互相表示的形式，可以进一步导出以下两种形式。

·用最优状态价值函数表示最优状态价值函数，备份图见图2-5a：

·用最优动作价值函数表示最优动作价值函数，备份图见图2-5b：

图2-5 最优状态价值函数和最优动作价值函数自我表示的备份图

例如，对于表2-1的动力系统，我们可以列出其Bellman最优方程为：

v_π(饿)=max{q_π(饿,不吃),q_π(饿,吃)}

v_π(饱)=max{q_π(饱,不吃),q_π(饱,吃)}

q_π(饿,不吃)=1·(-2+γv_π(饿))+0

q_π(饿,吃)=(1-α)(-3+γv_π(饿))+α(+1+γv_π(饱))

q_π(饱,不吃)=β(-2+γv_π(饿))+(1-β)(+2+γv_π(饱))

q_π(饱,吃)=0+1·(+1+γv_π(饱))

用这个方程可以求得最优价值函数。

接下来我们用sympy求解这个方程。Bellman最优方程含有max()运算，可以通过分类讨论来化解这个max()运算，将优化问题转为普通线性规划问题。如果用这种方法，可以将这个方程组分为以下4类情况讨论，用代码清单2-2求解。

代码清单2-2 求解示例Bellman最优方程

from IPython.display import display
import sympy
from sympy import symbols
sympy.init_printing()
alpha, beta, gamma = symbols('alpha beta gamma')
v_hungry, v_full = symbols('v_hungry v_full')
q_hungry_eat, q_hungry_none, q_full_eat, q_full_none = \
        symbols('q_hungry_eat q_hungry_none q_full_eat q_full_none')
xy_tuples = ((1, 1), (1, 0), (0, 1), (0, 0))
for x, y in xy_tuples: # 分类讨论
    system = sympy.Matrix((
            (1, 0, x-1, -x, 0, 0, 0),
            (0, 1, 0, 0, -y, y-1, 0),
            (-gamma, 0, 1, 0, 0, 0, 1),
            ((alpha-1)*gamma, -alpha*gamma, 0, 1, 0, 0, 2*alpha-3),
            (-beta*gamma, (beta-1)*gamma, 0, 0, 1, 0, -5*beta+3),
            (-2*gamma,  0, 0, 0, 0, 1, 2) ))
    result = sympy.solve_linear_system(system,
            v_hungry, v_full,
            q_hungry_eat, q_hungry_none, q_full_eat, q_full_none)
    print('==== x = {}, y = {} ===='.format(x, y))
    display(result)
    print('q_hungry_eat - q_hungry_none =')
    display(sympy.simplify(result[q_hungry_eat] - result[q_hungry_none]))
    print('q_full_eat - q_full_none =')
    display(sympy.simplify(result[q_full_eat] - result[q_full_none]))

代码清单2-2求得以下4种情况的解如下。

情况I：q*(饿,不吃)≥q*(饿,吃)且q*(饱,不吃)≥q*(饱,吃)。这时v*(饿)=q*(饿,不吃)且v*(饱)=q*(饱,不吃)。这种情况的求解结果为：

其中△_I=2αγ²-αγ+γ+1。此时，q_*(饿,不吃)≥q_*(饿,吃)且q_*(饱,不吃)≥q_*(饱,吃)可以化简为：

(αγ-2α-4γ+4)(2αγ²-αγ+γ-1)≥0

(6αβγ²-3αβγ-3αγ+8βγ²-5β-8γ²+7γ+1)(2αγ²-αγ+γ-1)≥0

情况II：q_*(饿,不吃)≥q_*(饿,吃)且q_*(饱,不吃)<q_*(饱,吃)。这时v_*(饿)=q_*(饿,不吃)且v_*(饱)=q_*(饱,吃)。这种情况的求解结果为：

其中△_II=αγ²-αγ+βγ²-βγ-γ²+2γ-1。此时，q_*(饿,不吃)≥q_*(饿,吃)且q_π(饱,不吃)<q_π(饱,吃)可以化简为：

-3αβγ+2α-4βγ+4γ-4≥0

6αβγ²-3αβγ-3αγ+8βγ²+4βγ+5β-8γ²+3γ-1>0

情况III：q_π(饿,不吃)<q_π(饿,吃)且q_π(饱,不吃)≥q_π(饱,吃)。这时v_π(饿)=q_π(饿,吃)且v_*(饱)=q_*(饱,不吃)。这种情况的求解结果为：

此时，q_*(饿,不吃)<q_*(饿,吃)且q_*(饱,不吃)≥q_*(饱,吃)可以化简为：

αγ-2α-4γ+4>0

4βγ-5β-γ+1≤0

情况IV:q_*(饿,不吃)<q_*(饿,吃)且q_*(饱,不吃)<q_*(饱,吃)。这时v_*(饿)=q_*(饿,吃)且v_*(饱)=q_*(饱,吃)。这种情况的求解结果为：

其中△_IV=βγ²-βγ-γ²+2γ-1。此时，q_*(饿,不吃)<q_*(饿,吃)且q_*(饱,不吃)<q_*(饱,吃)可以化简为：

-3αβγ+2α-4βγ+4γ-4<0

4βγ-5β-γ+1>0

对于给定数值的情况，更常将松弛为v_*(s)≥q_*(s,a)（s∈,a∈(s)），并消去q_*(s,a)以减少决策变量，得到新的线性规划：

其中c(s)（s∈）是一组任意取值的正实数。Bellman最优方程的解显然在线性规划的可行域内。而由于c(s)>0（s∈），因此线性规划的最优解肯定会让约束条件中的某些不等式取到等号，使得Bellman最优方程成立。可以证明，这个线性规划的最优解满足Bellman最优方程。

例如，在之前的例子中，如果限定，我们用这个线性规划求得最优状态价值为

进而由最优状态价值推算出最优动作价值为

2.3.3 用Bellman最优方程求解最优策略

在理论上，通过求解Bellman最优方程，就可以找到最优价值函数。一旦找到最优价值函数，就能很轻易地找到一个最优策略：对于每个状态s∈，总是选择让q_*(s,a)最大的动作a。

例如，对于表2-1的动力系统，我们已经通过分类讨论求得了Bellman最优方程。那么它的最优策略也可以通过分类讨论立即得到：

情况I：q_*(饿,不吃)≥q_*(饿,吃)且q_*(饱,不吃)≥q_*(饱,吃)，即(αγ-2α-4γ+4)(2αγ²-αγ+γ-1)≥0且(6αβγ²-3αβγ-3αγ+8βγ²-5β-8γ²+7γ+1)(2αγ²-αγ+γ-1)≥0。这种情况的最优策略是

π_*(饿)=不吃,π(饱)=不吃

即一直不吃。

情况II：q_*(饿,不吃)≥q_*(饿,吃)且q_*(饱,不吃)<q_*(饱,吃)，即-3αβγ+2α-4βγ+4γ-4≥0且6αβγ²-3αβγ-3αγ+8βγ²+4βγ+5β-8γ²+3γ-1>0。这种情况的最优策略是π_*(饿)=不吃,π(饱)=吃

即饿了不吃，饱时吃。

情况II：q_*(饿,不吃)<q_*(饿,吃)且q_*(饱,不吃)≥q_*(饱,吃)，即αγ-2α-4γ+4>0且4βγ-5β-γ+1≤0。这种情况的最优策略是

π_*(饿)=吃,π(饱)=不吃

即饿了吃，饱时不吃。

情况IV：q_π(饿,不吃)<q_π(饿,吃)且q_π(饱,不吃)<q_π(饱,吃)，即-3αβγ+2α-4βγ+4γ-4<0且4βγ-5β-γ+1>0。这种情况的最优策略是

π_*(饿)=吃,π(饱)=吃

即一直吃。

对于一个特定的数值，求解则更加明显。例如，当，2.3.2节已经求得了最优动作价值，此时最优动作价值满足q_π(饿,不吃)<q_π(饿,吃)且q_π(饱,不吃)<q_π(饱,吃)。所以，它对应的最优策略为

π(吃|饿)=π(吃|饱)=1

π(不吃|饿)=π(不吃|饱)=0

但是，实际使用Bellman最优方程求解最优策略可能会遇到下列困难。

·难以列出Bellman最优方程。列出Bellman最优方程要求对动力系统完全了解，并且动力系统必须可以用有Markov性的Mar kov决策过程来建模。在实际问题中，环境往往十分复杂，很难非常周全地用概率模型完全建模。

·难以求解Bellman最优方程。在实际问题中，状态空间往往非常巨大，状态空间和动作空间的组合更是巨大。这种情况下，没有足够的计算资源来求解Bellman最优方程。所以这时候会考虑采用间接的方法求解最优价值函数的值，甚至是近似值。