环信出品《深度学习理论与实战：提高篇》：强化学习简介(20)

编者按：环信开源国内首本免费深度学习理论和实战专著《深度学习理论与实战：提高篇 》，内容涵盖听觉，视觉，语言和强化学习，七百多页详尽的理论和代码分析。本文节选自《深度学习理论与实战：提高篇 》一书，原文链接http://fancyerii.github.io/2019/03/14/dl-book/ 。作者李理，环信人工智能研发中心vp，有十多年自然语言处理和人工智能研发经验，主持研发过多款智能硬件的问答和对话系统，负责环信中文语义分析开放平台和环信智能机器人的设计与研发。

目录

• 简介

• 策略评估(Policy Evaluation)

• 策略评估代码示例

• gridworld.py

• Policy Evaluation.ipynb

• 策略提升(Policy Improvement)

• 策略提升定理

• 策略迭代(Policy Iteration)

• 策略迭代代码示例

• 价值迭代(Value Iteration)

• 价值迭代代码示例

• 通用策略迭代(Generalized Policy Iteration/GPI)

简介

动态规划是一种算法，对于简单的MDP问题可以用它来求解最优解。但是实际问题很少能用到这种算法，因为它的假设很难满足以及它计算复杂度太高了。不过学习这种算法依然很有用处，因为后面介绍的方法都想达到动态规划一样的效果，只不过它们能降低计算复杂度并且在非理想的环境下也可以使用。

这一节我们假设MDP是有限的，包括状态、行为和Reward，并且环境完全由p(s′,r|s,a)$p(s^{\prime },r|s,a)$确定。如果读者学习过计算机的算法课程，可能也会学到动态规划算法，它的基本思想是：一个”大”的问题的最优解，可以分解成一些小的问题，并且把小问题的的最优解的组合起来得到大问题的最优解。本书后文很多算法都是动态规划算法。

使用动态规划来解决强化学习问题的核心是使用价值函数来搜索好的策略。如果有了最优价值函数（不管是状态价值函数还是状态价值函数），我们就可以用它来计算最优的策略。最优价值函数满足如下的贝尔曼方程：

v∗(s)=maxaE[Rt+1+γv∗(St+1)|St=s,At=a] =maxa∑s′,rp(s′,r|s,a)[r+γv∗(s′)]$$v_{\ast }(s)=\underset{a}{max}\mathbb{E}[R_{t+1}+\gamma v_{\ast }(S_{t+1})|S_t=s,A_t=a]=\underset{a}{max}\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\ast }(s^{\prime })]$$

我们来理解一下这个公式，在状态s下最优的价值是什么呢？我们遍历所有可能的行为a，得到Reward值Rt+1$R_{t+1}$然后进入新的状态St+1$S_{t+1}$。这个过程由p(s′,r|s,a)$p(s^{\prime },r|s,a)$确定，所以加一个E$\mathbb{E}$。当t+1时刻我们处于St+1$S_{t+1}$时，我们仍然要遵循最优的策略，所以第二项是γv∗(St+1)$\gamma v_{\ast }(S_{t+1})$。把E$\mathbb{E}$根据期望的定义展开成求和就得到第二个等号。Q的贝尔曼方程也是类似的：

q∗(s,a)=E[Rt+1+γmaxa′q∗(St+1,a′)|St=s,At=a] =∑s′,rp(s′,r|s,a)[r+γmaxa′q∗(St+1,a′)]$$q_{\ast }(s,a)=\mathbb{E}[R_{t+1}+\gamma \underset{a^{\prime }}{max}{q}_{\ast }(S_{t+1},a^{\prime })|S_t=s,A_t=a]=\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma \underset{a^{\prime }}{max}{q}_{\ast }(S_{t+1},a^{\prime })]$$

我们同样可以这样解读：在状态s采取a，Agent会得到Rt+1$R_{t+1}$和进入状态St+1$S_{t+1}$，在这个状态时我们有很多选择，但是我们要选择最大的那个a’。而动态规划就是根据上面的贝尔曼方程来得到迭代更新的算法。

策略评估(Policy Evaluation)

首先我们来计算一个给定的策略的价值函数vπ(s)$v_{\pi }(s)$，这叫策略评估(Policy Evaltuion)，有时我们也把这个问题叫做预测(Prediction)问题。

vπ(s)≡Eπ[Gt|St=s]=Eπ[Rt+1+γGt+1|St=s]=Eπ[Rt+1+γvπ(St+1)|St=s]=∑aπ(a|s)∑s′,rp(s′,r|s,a)[r+γvπ(s′)]$$\begin{array}{rl}{v}_{\pi }(s)& \equiv {\mathbb{E}}_{\pi }[G_t|S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s]\\ & =\sum _a\pi (a|s)\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })]\end{array}$$

其中π(a|s)$\pi (a|s)$是给定策略π$\pi$时，在状态s下采取行为a的概率。公式的期望Eπ${\mathbb{E}}_{\pi }$说明是在策略π$\pi$下变量Rt+1$R_{t+1}$和Gt+1$G_{t+1}$的概率。

如果环境的动力系统(p(s′,r|s,a)$p(s^{\prime },r|s,a)$)是完全已知的，而策略π(a|s)$\pi (a|s)$也是已知的情况下，我们可以通过线性方程直接解出vπ(s)$v_{\pi }(s)$。因为假设状态s有n种可能，那么就是n个变量，n个等式的线性方程，可以证明，如果γ<1$\gamma <1$，则方程有唯一解。这是一个线性代数的问题，但是这里我们会介绍一种迭代算法，这和梯度下降的思路有一些类似。因为迭代算法更容易推广到动态规划之外的算法，所以我们需要学习这种方法。下图是算法的伪代码：

图：策略评估算法伪代码

这个算法过程如下：首先把所有的V0(s)$V_0(s)$都初始化成0，然后根据V0$V_0$计算V1$V_1$，…，一直继续下去直到收敛。根据Vk(s)$V_k(s)$计算Vk+1(s)$V_{k+1}(s)$的公式如下：

Vk+1(s)=∑aπ(a|s)∑s′,rp(s′,r|s,a)[r+γVk(s′)]$$V_{k+1}(s)=\sum _a\pi (a|s)\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V_k(s^{\prime })]$$

这个迭代算法的证明本书从略，有兴趣的读者可以参考这里。我们可以看一下收敛的时候，Vk+1=Vk，Δ=0$V_{k+1}=V_k，\mathrm{\Delta }=0$，那么上面的迭代公式正好就是贝尔曼方程！有了上面的迭代算法，任何给定的策略π$\pi$，我们都可以计算出它的价值函数。

策略评估代码示例

接下来我们用代码来实现上面的算法，在介绍具体算法之前，先介绍Grid World。

图：Grid World

如上图所示，非终止状态共有14个S={1,2,…,14}$\mathcal{S}=\{1,2,\dots ,14\}$，每个状态下都可以采取4个Action，A={up,down,left,right}$\mathcal{A}=\{up,down,left,right\}$，这些Action会确定(概率为1)的把Agent带到相应的位置，如果碰到墙了那就保持状态不变。因此p(6,−1|5,right)=1$p(6,-1|5,right)=1$, p(7,−1|7,right)=1$p(7,-1|7,right)=1$，p(10,r|5,right)=0$p(10,r|5,right)=0$。左上和右下是结束状态(迷宫出口)，如果没到结束状态，则reward是-1，因此这个任务期望Agent尽快找到出口。注意：p(6,−1|5,right)=1$p(6,-1|5,right)=1$的意思是如果处于状态5并且Action是right，那么它一定会进入状态6并且reward是-1。因为概率和为1，因此p(6,1.5|5,right)=0$p(6,1.5|5,right)=0$，p(4,−1|5,right)=0$p(4,-1|5,right)=0$。

我们首先实现这个Environment，代码在envs/gridworld.py，本系列完整代码在这里。

gridworld.py

import numpy as np
import sys
from gym.envs.toy_text import discrete

UP = 0
RIGHT = 1
DOWN = 2
LEFT = 3

class GridworldEnv(discrete.DiscreteEnv):
    """
    Grid World environment。
    Agent在一个MxNd的网格里，目标是尽快走到最上角或者右下角

    例如, 一个4x4的网格如下：
    
    T  o  o  o
    o  x  o  o
    o  o  o  o
    o  o  o  T

    x是Agent当前的位置。T是结束状态。

    """
    metadata = {'render.modes': ['human', 'ansi']}

    def __init__(self, shape=[4,4]):
        if not isinstance(shape, (list, tuple)) or not len(shape) == 2:
            raise ValueError('shape argument must be a list/tuple of length 2')

        self.shape = shape

        nS = np.prod(shape)
        nA = 4

        MAX_Y = shape[0]
        MAX_X = shape[1]

        P = {}
        grid = np.arange(nS).reshape(shape)
        it = np.nditer(grid, flags=['multi_index'])

        while not it.finished:
            s = it.iterindex
            y, x = it.multi_index

            P[s] = {a : [] for a in range(nA)}

            is_done = lambda s: s == 0 or s == (nS - 1)
            reward = 0.0 if is_done(s) else -1.0

            # We're stuck in a terminal state
            if is_done(s):
                P[s][UP] = [(1.0, s, reward, True)]
                P[s][RIGHT] = [(1.0, s, reward, True)]
                P[s][DOWN] = [(1.0, s, reward, True)]
                P[s][LEFT] = [(1.0, s, reward, True)]
            # Not a terminal state
            else:
                ns_up = s if y == 0 else s - MAX_X
                ns_right = s if x == (MAX_X - 1) else s + 1
                ns_down = s if y == (MAX_Y - 1) else s + MAX_X
                ns_left = s if x == 0 else s - 1
                P[s][UP] = [(1.0, ns_up, reward, is_done(ns_up))]
                P[s][RIGHT] = [(1.0, ns_right, reward, is_done(ns_right))]
                P[s][DOWN] = [(1.0, ns_down, reward, is_done(ns_down))]
                P[s][LEFT] = [(1.0, ns_left, reward, is_done(ns_left))]

            it.iternext()

        # Initial state distribution is uniform
        isd = np.ones(nS) / nS

        # We expose the model of the environment for educational purposes
        # This should not be used in any model-free learning algorithm
        self.P = P

        super(GridworldEnv, self).__init__(nS, nA, P, isd)

    def _render(self, mode='human', close=False):
        if close:
            return

        outfile = StringIO() if mode == 'ansi' else sys.stdout

        grid = np.arange(self.nS).reshape(self.shape)
        it = np.nditer(grid, flags=['multi_index'])
        while not it.finished:
            s = it.iterindex
            y, x = it.multi_index

            if self.s == s:
                output = " x "
            elif s == 0 or s == self.nS - 1:
                output = " T "
            else:
                output = " o "

            if x == 0:
                output = output.lstrip() 
            if x == self.shape[1] - 1:
                output = output.rstrip()

            outfile.write(output)

            if x == self.shape[1] - 1:
                outfile.write("\n")

            it.iternext()

代码非常易读，最主要的几点如下：

• 这个类继承了discrete.DiscreteEnv，因此构造函数需要调用父类的构造函数。

• metadata = {‘render.modes’: [‘human’, ‘ansi’]}。

OpenAI  Gym的Env对象需要实现render，也就是把当前的状态“画”出来，这样便于调试和展示。最常见的“画”法是rgb_array，也就是一幅位图。这里使用了简单的ansi方式，直接通过字符的方式输出到控制台。比如：

    T  o  o  o
    o  x  o  o
    o  o  o  o
    o  o  o  T

它表示Agent现在处于第二行第二列。

• 系统的动力系统由env.P确定，它的值就是上面我们描述的概率。