深度强化学习（二）：基本原理与结构

一、组成与结构

1.1、基本概念

强化学习通常使用马尔可夫决策过程（Markov Decision Process,MDP）来描述，具体而言：机器处在一个环境中，每个状态为机器对当前环境的感知；机器只能通过动作来影响环境，当机器执行一个动作后，会使得环境按某种概率转移到另一个状态；同时，环境会根据潜在的奖赏函数反馈给机器一个奖赏。综合而言，强化学习主要包含四个要素：状态、动作、转移概率以及奖赏函数。 $~~$ ——周志华《机器学习》

基本结构

智能体(Agent): 学习器与决策者的角色。
环境(Environment): 智能体之外一切组成的、与之交互的事物。
动作(Actions): 智能体的行为表征。
状态(State): 智能体从环境获取的信息。
奖励(Reward): 环境对于动作的反馈。
策略(Policy): 智能体根据状态进行下一步动作的函数。
状态转移概率:智能体做出动作后进入下一状态的概率。

1.2、马尔可夫决策过程

马尔可夫决策过程

马尔可夫性:系统的下一个状态仅与当前状态有关，而与历史状态无关，即：
$p\left(s_{t+1} | s_{t}, \ldots, s_{0}\right)=p\left(s_{t+1} | s_{t}\right)$
为最大化长期累积奖赏，定义当前时刻后的累积奖赏为回报(Return)，考虑折扣因子(避免时间过长时，总回报无穷大)：
$R_{t}=r_{t+1}+\gamma r_{t+2}+\gamma^{2} r_{t+3}+\ldots=\sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1}$
强化学习的目标是学习到一个策略来最大化期望，即希望智能体执行一系列的动作来获得尽可能多的平均回报。为评估一个策略的期望回报，需要定义值函数。
状态值函数: $V^{\pi}(s)=E_{\pi}\left[R_{t} | s_{t}=s\right]=E_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1} | s_{t}=s\right]$
状态-动作值函数: $Q^{\pi}(s, a)=E_{\pi}\left[R_{t} | s_{t}=s, a_{t}=a\right]=E_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1}| s_{t}=s,a_{t}=a\right]$
根据马尔可夫特性，二者有如下关系：
$Q^{\pi}(s, a)=\mathbb{E}\left[ r_{t+1}+\gamma V^{\pi}\left(s_{t+1}\right)\right]$
$V^{\pi}(s)=\mathbb{E}_{a \sim \pi(a | s)}\left[Q^{\pi}(s, a)\right]$ 即状态值函数 $V^{\pi}(s)$ 是动作-状态值函数 $Q^{\pi}(s, a)$ 关于动作 $a$ 的期望。
值函数是对策略的评估，在策略有限时，可以对所有策略进行评估并选出最优策略：
$V^{*}(s)=\max _{\pi} V^{\pi}(s)$ $\pi^{*}=\arg \max _{\pi} V^{\pi}(s)$

二、数学基础

2.1、贝尔曼方程

根据状态值函数的表达式，可以进行如下推导，此即贝尔曼方程(Bellman equation)，其意义在于当前状态的值函数可以通过下一状态的值函数来计算。
$\begin{aligned} V^{\pi}(s_{t})&=E\left[R_{t} | s_{t}=s\right]=E\left[r_{t+1}+\gamma r_{t+2}+\ldots | s_{t}=s\right] \\&=E[ r_{t+1}+\gamma\left(r_{t+2}+\gamma r_{t+3}+\ldots\right) | s_{t}=s ] \\&=E\left[r_{t+1}+\gamma R_{t+1} | s_{t}=s\right] \\&=E\left[r_{t+1}+\gamma V^{\pi}\left(s_{t+1}\right) | s_{t}=s\right] \end{aligned}$
同理，状态-动作值函数也有类似关系。
$Q^{\pi}(s_{t}, a_{t})=E_{\pi}\left[r_{t+1}+\gamma Q^{\pi}\left(s_{t+1},a_{t+1}\right)| s_{t}=s, a_{t}=a\right]$
下图为状态值函数的具体计算过程，其中空⼼圆圈表⽰状态，实⼼圆圈表⽰状态-动作对。计算状态值函数的目的是为了构建学习算法从数据中得到最优策略，每个策略对应着一个状态值函数，最优策略对应着最优状态值函数。

状态值函数计算过程

2.2、基于值函数的学习方法

由于值函数是对策略的评估，为不断优化直至选出最优策略，一种可行的方式是依据值函数选取策略更新的方式。以下介绍几种常见的策略：

贪婪策略：

$\pi^{*}(a | s)=\{\begin{array}{ll}{1} & {\text { if } a=\underset{a}{\arg \max } Q^{\pi}(s, a)} \\ {0} & {\text { otherwise }}\end{array}$
贪婪策略是一个确定性策略，即始终选取使值函数最大的策略。

ε-greedy策略：

$\pi(a | s) \leftarrow \{\begin{array}{ll}{1-\varepsilon+\frac{\varepsilon}{|A(s)|}} & {\text { if } a=\underset{a}{\arg \max} Q^{\pi}(s, a)} \\ {\frac{\varepsilon}{|A(s)|}} & {\text { if } a \neq \underset{a}{\arg \max} Q^{\pi}(s, a)}\end{array}$
ε-greedy策略平衡了探索(exploration)和利用(exploitation)，即选取使值函数最大的动作的概率为 $1-\varepsilon+\frac{\varepsilon}{|A(s)|}$ ，其它动作的等概率，为 $\frac{\varepsilon}{|A(s)|}$ ，是一种常用的随机策略。
其它的策略还有高斯策略和基于玻尔兹曼分布的随机策略，在此不做详述。

三、基于模型的迭代方法

基于模型的强化学习可以用动态规划的思想来解决。利用动态规划解决的问题需要满足两个条件：1.整个优化问题可以分解为多个子优化问题；2.子优化问题可以解，且解能够被存储和重复利用。由贝尔曼方程可知，马尔科夫决策过程满足动态规划的条件，因此动态规划的方法适用。此时常用的方法有策略迭代和值迭代算法。

3.1、策略迭代(Policy Iteration)

策略迭代算法包括策略评估和策略改进两个步骤。策略评估，即在给定策略下通过数值迭代算法不断计算每个状态的值函数；策略改进，即利用值函数来更新策略，不断循环，直至收敛到最优策略。

策略迭代过程

策略迭代算法

3.2、值迭代(Value Iteration)

策略迭代中策略评估和策略改进交替进行，其中策略评估内部还需要迭代（而事实上不必要执行到完全收敛），因此计算量大。值迭代将策略评估和策略改进两个过程整合，直接计算出最优策略。

策略迭代与值迭代的更新方式

根据贝尔曼方程，最优状态值函数 $V^{*}(s)$ 和最优状态-动作值函数 $Q^{*}(s, a)$ 可以进行迭代计算。
$V^{*}(s)=\max _{a} \mathbb{E}\left[ r_{t+1}+\gamma V^{*}\left(s_{t+1}\right)\right]$
$Q^{*}(s, a)=\mathbb{E} [ r_{t+1}+\gamma \max _{a_{t+1}} Q^{*}\left(s_{t+1}, a_{t+1})]$
此即贝尔曼最优方程，即可通过迭代最优值函数来得到最优策略，充分体现了动态规划的思想。

值迭代算法

值迭代和策略迭代都是基于模型的强化学习算法，一方面要求模型完全已知，另一方面要求复杂度较小，因此实际应用的场合较少。

四、案例实践

本节将通过一个简单的小例子来说明基于模型的强化学习的组成、结构、迭代过程、优化目标等因素。

4.1 背景介绍

网格世界(Grid World) $~~$ 规则：网格中的每一个小格都对应于环境中的状态. 在一个小格上, 有 4 种可能的动作: 北移, 南移,东移, 西移, 其中各个动作都确定性地使智能体在网格上沿对应的方向移动一格. 如果所采取的动作将令智能体脱离网格, 那么该动作的结果为智能体的位置保持不变, 且造成 −1 的奖赏. 除了上述动作与将智能体移出特殊状态 A 与 B 的动作外, 其他的动作只会造成 0 的奖赏.在状态 A 上, 所有的 4 个动作会产生 +10 的奖赏, 并将智能体带至 A’. 在状态 B 上, 所有的 4个动作会产生 +5 的奖赏, 并将智能体带至 B’.

网格世界

4.2 解决过程

导入模块及数据初始化

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.table import Table

WORLD_SIZE = 5
A_POS = [0, 1]
A_PRIME_POS = [4, 1]
B_POS = [0, 3]
B_PRIME_POS = [2, 3]
discount = 0.9
world = np.zeros((WORLD_SIZE, WORLD_SIZE))

动作空间，即在每一格上下左右动作的概率相同

# left, up, right, down
actions = ['L', 'U', 'R', 'D']
actionProb = []    #生成5*5的每个单元包括4个方向概率的list
for i in range(0, WORLD_SIZE):
    actionProb.append([])
    for j in range(0, WORLD_SIZE):
        actionProb[i].append(dict({'L':0.25, 'U':0.25, 'R':0.25, 'D':0.25}))

环境（状态空间），即确定在每一格在某一动作后的下一状态和反馈值

nextState = []    #确定每一位置的下一状态
actionReward = []   #按照规则确定奖惩函数
for i in range(0, WORLD_SIZE):
    nextState.append([])
    actionReward.append([])
    for j in range(0, WORLD_SIZE):
        next = dict()
        reward = dict()
        if i == 0:
            next['U'] = [i, j]
            reward['U'] = -1.0
        else:
            next['U'] = [i - 1, j]
            reward['U'] = 0.0
        if i == WORLD_SIZE - 1:
            next['D'] = [i, j]
            reward['D'] = -1.0
        else:
            next['D'] = [i + 1, j]
            reward['D'] = 0.0
        if j == 0:
            next['L'] = [i, j]
            reward['L'] = -1.0
        else:
            next['L'] = [i, j - 1]
            reward['L'] = 0.0
        if j == WORLD_SIZE - 1:
            next['R'] = [i, j]
            reward['R'] = -1.0
        else:
            next['R'] = [i, j + 1]
            reward['R'] = 0.0
        if [i, j] == A_POS:
            next['L'] = next['R'] = next['D'] = next['U'] = A_PRIME_POS
            reward['L'] = reward['R'] = reward['D'] = reward['U'] = 10.0
        if [i, j] == B_POS:
            next['L'] = next['R'] = next['D'] = next['U'] = B_PRIME_POS
            reward['L'] = reward['R'] = reward['D'] = reward['U'] = 5.0

        nextState[i].append(next)
        actionReward[i].append(reward)

随机优化策略，即在每个格子上下左右选择是随机的，不采取任何措施

while True:
    # keep iteration until convergence
    newWorld = np.zeros((WORLD_SIZE, WORLD_SIZE))
    for i in range(0, WORLD_SIZE):
        for j in range(0, WORLD_SIZE):
            for action in actions:
                newPosition = nextState[i][j][action]
                # bellman equation
                newWorld[i, j] += actionProb[i][j][action] * (actionReward[i][j][action] + discount * world[newPosition[0], newPosition[1]])
    if np.sum(np.abs(world - newWorld)) < 1e-4:
        print('Random Policy')
        draw_image(np.round(newWorld, decimals=2))
        break
    world = newWorld

值迭代的优化策略，即每次总选择使值函数最大的策略，通过不断地迭代过程直至收敛

world = np.zeros((WORLD_SIZE, WORLD_SIZE))
while True:
    # keep iteration until convergence
    newWorld = np.zeros((WORLD_SIZE, WORLD_SIZE))
    for i in range(0, WORLD_SIZE):
        for j in range(0, WORLD_SIZE):
            values = []
            for action in actions:
                newPosition = nextState[i][j][action]
                # value iteration
                values.append(actionReward[i][j][action] + discount * world[newPosition[0], newPosition[1]])
            newWorld[i][j] = np.max(values)
    if np.sum(np.abs(world - newWorld)) < 1e-4:
        print('Optimal Policy')
        draw_image(np.round(newWorld, decimals=2))
        break
    world = newWorld

4.3 结果分析

经过多次重复实验，能够看出采用优化策略得到的反馈值要显著高于随机策略，而事实上优化策略的结果与理论最优解相比已经非常接近，通过调整收敛的阈值，将能使结果无限逼近于理论最优解。

随机策略结果

优化策略

理论最优解结果

为进一步展示迭代过程，绘制了两种策略下值函数的变化。可以看出，随机策略下，值函数的变化方向多样，有的朝值函数增大的方向变化，有的朝值函数减小的方向变化，还有的出现了变化的波动。与之相比，优化策略下可以清晰地看出值函数在迭代过程中不断增长直至收敛的过程。

随机策略