深入理解强化学习，看这篇就够了

孙裕道

强化学习

强化学习注重智能体（agent）与环境之间的交互式学习：

• 强化学习的数据集不是训练初始阶段就有的，而是来自智能体与环境交互才能获得；
• 强化学习不追求单步决策的最优策略，而是追求与环境交互获得的长期累积奖励。强化学习需要从整体上衡量整个交互过程。智能体在做决策时，会更加偏向于历史交互中带来更多奖励的动作。同时正如发现这些动作一样，未曾选择的动作中可能蕴藏着更优的决策，这鼓励着智能体尝试未曾选择的动作。因此智能体需要平衡利用（exploitation）和探索（exploration）。

马尔可夫决策过程

通常使用马尔可夫决策过程（Markov Decision Process，MDP）来描述强化学习问题。马尔可夫决策过程过程定义为一个六元组 ：

• 表示所有状态（state）的集合，也称为状态空间。状态空间的大小可以是有限的，也可以是无限的。
• 表示初始状态 的分布。
• 表示所有动作（action）的集合，也称为动作空间。动作空间同样可以是有限的，也可以是无限的。
• 表示状态转移概率（state transition probability）。具体来说， 表示在状态 上执行动作 ，状态转移到状态 的概率。显然，对于任意 而言，都有 ，并且 。
• 表示状态转移过程的奖励函数（reward function）。 简记作为 ，表示在状态 上执行动作 后转移到状态 得到的数值奖励。
• 表示状态转移过程中的折扣系数（discount coefficient），通常在区间 中。

不同设定的马尔可夫决策过程，会影响到强化学习算法设计以及理论分析。马尔可夫决策过程有一个重要性质—— 马尔可夫性质。

表示下一个时间步的状态只受到当前状态和动作的影响。马尔可夫性质简化了交互过程中状态动作之间的相互影响。

如上图所示是智能体与环境之间交互的示意图，首先从初始状态分布中产生一个初始状态 。然后智能体采用策略 产生当前状态对应的动作 ，并在环境中执行动作 。环境将根据智能体的行为产生对应的奖励 和下一个状态 。

重复进行这个交互过程，智能体就可以得到一系列状态，动作和奖励，，称为当前策略的一个轨迹（trajectory）。这个轨迹可以拆分成一个一个的 ，将其称为状态转移样本。如果这个交互过程是周期的，那么智能体与环境交互一定的时间步之后，整个交互过程会重置。如果这个交互过程是无限期的，那么智能体与环境可以一直交互下去，直到触发终止条件。

强化学习的优化目标

强化学习考虑智能体与环境交互产生的长期累积奖励。具体来说，对于每条轨迹，如果给未来的奖励加上折扣系数 ，可以计算一个累积奖励 。

如果智能体和环境的交互是无限的，即 ，此时累计奖励 的计算公式为：

折扣系数通常在 0 到 1 之间，从而使得以上优化目标在无穷时间步的情况下具有数学意义的上界，便于研究分析。折扣系数越趋近于 0，优化目标越注重短期收益；越趋近于 1，优化目标越注重长期累积收益。

如果有两个策略，一个策略在初始步中具有短暂非常高的奖励，但之后得分较低；另一个策略在整个过程中都保持着比较稳定的奖励。这两个策略长期累积奖励是一样的。平均累积奖励将无法区分这两种策略。折扣累积奖励在折扣系数趋于 0 时将更加偏好第一个策略。强化学习领域通常使用折扣累积奖励作为优化目标。

值函数和贝尔曼方程

值函数（value funciton）用来描述当前状态对应的预期累积奖励。值函数分为两种，状态值函数（state value function）和状态动作值函数（state-action value functon）， 区别在于前者将状态映射到未来期望累积奖励，即 ；后者将状态动作映射到未来期望累积奖励，即 。

给定马尔可夫决策过程 和策略 ，状态价值函数定义如下，

其中， 表示轨迹来自策略 与环境的交互。上式表示从状态 出发，智能体使用策略 与环境交互得到的期望累积奖励。类似地，可以定义状态动作价值函数。

表示从状态 出发，执行动作 后，智能体使用策略 与交互得到的期望累积奖励。

贝尔曼方程（Bellman equation）是一个动态规划方程。它是强化学习算法中的核心等式，构建了状态转移前后值函数之间的递归关系。对于任意概率性策略 而言，状态价值的贝尔曼期望方程为：

状态动作价值函数的贝尔曼期望方程为：

由上公式推导可以发现状态价值函数和状态动作价值函数可以相互转换

和 的探讨

当前状态 ，执行动作 ，和下一状态 ，以及相关的概率分布 和 的关系示意图如下所示。策略 是状态价值函数 和状态动作价值函数 里非常重要的一个概率分布，它表示的是给定状态 ，动作 的概率分布。当 是确定性策略的时候，即给定状态 后，输出的动作 就是明确的，则有 或 。当 是一个随机性策略的时候，即给定状态 后，输出的动作 是一个概率分布，则有 。

移概率 是状态动作价值函数 中一个非常重要的概率分布，它表示的是给定当前状态 和动作 ，下一个状态 的概率分布。这里需要值得注意的是，动作空间 的划分的不同会对转移概率 有很直接的影响。

中国象棋棋盘里“仕”只能在四宫格里进行对角走动，假定当前状态 表示的是“仕”在四宫格的中心位置，执行动作空间 仕五进六，仕五进四，仕五退六，仕五退四 里的一个动作 ，进入到一下个状态 ，此时则有转移概率，即给定当前状态 和动作 ，那么下一个状态 就确定了。

如下图所示，当把动作空间划分为 进仕，退仕，相对动作空间 的划分颗粒度更大，其中“进仕”这个动作又可以划分为仕五进六，仕五进四这两个动作；“退仕”这个动作又可以划分为仕五进六，仕五进四这两个动作。此时给定当前状态 和动作 ，那么下一个状态 具有概率性，即。

相关定理证明

定理1：给定一个策略 ，状态价值函数 的贝尔曼算子 为：

可知状态价值函数 的贝尔曼算子 是收敛的。

证明：在策略 下，给定任意两个在状态 下的状态价值函数 和 ，则有：

由上公式可以推知，给定一个状态空间 ，则有：

当 的时，状态价值函数的贝尔曼算子 是一个收缩映射，进而则有：

当 趋近于无穷时， 和 的差值会趋近于 0，所以序列 是收敛的，并且会收敛到一个不动点上。

定理2：给定任意两个确定的策略 和 ，对任意状态 ，如果有：

其中 ，那么则有：

此时则称策略 会优于策略 。

证明：已知给定任意两个确定的策略 和 ，且对任意状态 ，有：

进而可推知：

进而则有：

由定理 2 可知，给定一个策略 ，已知当前状态 ，根据状态动作函数 找到一个最优动作所得到的新的策略 会优于或等于原始策略 。如果对所有的状态 都这么操作，则可以得到新的策略 。当策略改进方法收敛到最优策略时，则有 ，此时则有：

最后一个等式就是贝尔曼最优方程。

定理3：状态价值函数 的贝尔曼最优算子 为：

则可知状态价值函数 的贝尔曼最优算子 是收敛的。

证明：状态价值函数 的贝尔曼最优算子 为：

则有：

当 的时，状态价值函数的贝尔曼最优算子 是一个收缩映射，进而则有：

当 趋近于无穷时， 和 的差值会趋近于 0，所以序列 是收敛的，并且会收敛到一个不动点上。

值迭代法介绍

价值迭代法有两种形式，一种是利用状态动作价值函数的贝尔曼最优方程迭代求解状态动作矩阵 ，这也是俗称的 - 算法；另一种利用状态价值函数的贝尔曼最优方程迭代求解状态向量 。这一节主要介绍利用状态价值迭代法求解状态向量 的贝尔曼最优迭代公式为：

其中 第 次迭代函数， 和 分别表示的是当前的状态和执行的动作并且它们分别属于状态空间 和动作空间 ， 表示的是在状态 执行动作 后的即时奖励， 表示的是下一个的状态， 表示的是状态转移概率， 表示的是折扣系数。

如下左半图显示，该图共有九个状态分别是状态 至 ，右半图为左半图的状态转移过程的抽象示意图。现在的问题是如果有一个人在任意的一个房间里，给他支个招让他走出房间外。我们就可以通过强化学习中的价值迭代法来求解这个问题。

假定状态空间 ，动作空间为 分别表示向上走，向右走，向下走，向左走。如上右半图所示，当状态为 和 时的动作即时奖励的取值为 ，其它的行为奖励取值全为 ，即时奖励矩阵 表示为：

其中矩阵的行表示的是状态 ，列表示的是动作 。

首先令折扣系数 ，并将向量 初始化为一个零向量：

第一轮第一次迭代随机选取初始状态为房间 ，利用矩阵 的第二列（对应房间 1 或者状态 1）和向量 通过方程：

分别求出动作空间 中所有四个动作下的收益：

然后找出在状态 下，这四个动作的最大收益，并把此值赋给 ，即有：

第一轮第二次迭代随机选取初始状态为房间 ，利用矩阵 的第 5 列（对应房间 4 或者状态 4）和向量 分别求出动作空间 中所有四个动作下的收益：

然后找出在状态 下，这四个动作的最大收益，并把此值赋给 ，即有：

此时的向量 为：

每一轮中需要将向量 每个状态进行都进行迭代更新，多轮之后直至向量 收敛，收敛后的向量 为：

向量 并不能显式地告诉我们具体的行动策略是什么，但是可以利用向量 和矩阵 通过方程：

求解出具体的行为策略 为：

其中 表示的是在状态 时，最好的行动策略是往下走。

以上实例中值迭代算法的核心代码如下所示，实现起来并不复杂。其完整的github 代码链接为：

https://github.com/guidao20/RL_Value_Iteration

def state_value_iteration(env, theta=0.0001, discount_factor=0.8):
    def one_step_action_choice(state, V):
        A = np.zeros(env.nA)
        for a in range(env.nA):
            for prob, next_state, reward, done in env.P[state][a]:
                A[a] += prob * (reward + discount_factor * V[next_state])
        return A
    V = np.zeros(env.nS)
    while True:
        delta = 0
        for s in range(env.nS):
            # find the best action
            A = one_step_action_choice(s, V)
            best_action_value = np.max(A)
            # Calculate terminate condition
            delta = max(delta, np.abs(best_action_value - V[s]))
            # Update the value function
            V[s] = best_action_value
        # Check if we can stop
        if delta < theta:
            break
    policy = np.zeros([env.nS, env.nA])
    for s in range(env.nS):
        A = one_step_action_choice(s, V)
        best_action = np.argmax(A)
        policy[s, best_action] = 1.0
    return policy, V


实验结果如下所示，大约训练 200 轮之后状态向量 就可以收敛到理论值，然后通过收敛后的状态向量 得到动作策略向量 。

- 原理介绍

- 是强化学习的算法之一，- 的主要目的就是学习状态动作价值函数的 ，其中 表示的是在给定当前状态 和采取动作 之后能够获得的收益期望。- 利用状态 和动作 张成一个 表来储存 值，然后根据 值来选取能够获得最大收益的动作。- 采用是值迭代的方法进行求解，其核心的迭代公式为：

其中 第 次迭代函数， 和 分别表示的是当前的状态和执行的动作并且它们分别属于状态空间 和动作空间 ， 表示的是在状态 执行动作 后的即时奖励， 和 表示的是下一个的状态和行为， 表示的是状态转移概率， 表示的是折扣系数。

当动作空间 中的动作 划分的足够细时候，给定当前状态 和执行的动作 ，就能够明确确定下一个状态 ，进而则有 ，对上迭代公式进一步化简则有：

一般情况下 - 算法用到的都是以上的迭代公式。

如下左半图显示，该图共有六个状态，五个房间分别是状态 ，，， 和 ，以及房间外状态 ，右半图为左半图的状态转移过程的抽象示意图。现在的问题是如果有一个人在任意的一个房间里，给他支个招让他走出房间外。我们就可以通过强化学习中的 -方法来解决这个问题。

在解决这个问题之前需要先确定奖励矩阵 ，其元素表示的是当一个给定一个状态 ，当执行某个动作 后，它的即时奖励 的取值。规定当走出房间外到达状态 的动作奖励为 ，如果没有走出房间外但在房间内可以走通的是奖励为 ，如果房间内也不能走通的动作奖励为 。

奖励矩阵 具体取值如下所示。

首先确定折扣系数 ，并将 初始化为一个零矩阵。

第一轮第一次迭代随机选择初始状态为房间 ，然后观察矩阵 的第二行（对应房间 或者状态 ），这一行中有两个非负值，即当前状态 的下一步行为有两种可能：转至状态 或 ，此时选择随机选择转至状态 。观察矩阵 的第六行（对应房间 或者状态 ），这一行有三个非负值，即当前状态 的下一步行为有三种可能：转至状态 ， 或 。根据 - 值迭代公式则有：

则此时将矩阵 位置（即该矩阵的第二行第六列）用 进行数值更新。

第一轮第二次迭代随机选择状态为房间 ，然后观察矩阵 的第四行（对应房间 或者状态 ），这一行中有三个非负值，即当前状态 的下一步行为有三种可能：转至状态 ， 或 ，此时随机选择转至状态 。观察矩阵 的第二行（对应房间 或者状态 ），这一行中有两个非负值，即当前状态 的下一步行为有两种可能：转至状态 或 。根据 - 值迭代公式则有：

则此时将矩阵 位置（即该矩阵的第二行第六列）用 进行数值更新。

迭代多轮迭代之后直至 矩阵收敛，则此时的 即为所求，最后对 矩阵进行归一化。

下图表示的是经过 - 算法学习之后得到的最终的状态转移示意图，其中每个带有箭头的线上标明这个动作对应的即时收益。所以不管在哪个状态下，只要利用贪心策略找即时收益最大的行为就可以走出房间。

以上实例中 - 算法的完整代码如下所示，代码比较简单大约50行就可以完整实现该功能。

import numpy as np
import os
import random

def random_action(V):
    index_list = []
    for index, s in enumerate(list(V)):
        if s >= 0:
            index_list.append(index)
    return random.choice(index_list)

def reward_setting(state_num, action_num):
    R = -1 * np.ones((state_num , action_num))
    R[0,4] = 0
    R[1,3] = 0
    R[1,5] = 100
    R[2,3] = 0
    R[3,1] = 0
    R[3,2] = 0
    R[3,4] = 0
    R[4,0] = 0
    R[4,3] = 0
    R[4,5] = 100
    R[5,1] = 0
    R[5,4] = 0
    R[5,5] = 100
    return R


if __name__ == '__main__':
    action_num = 6
    state_num = 6
    gamma = 0.8
    epoch_number = 200
    condition_stop = 5

    Q = np.zeros((state_num , action_num))
    R = reward_setting(state_num , action_num)

    for epoch in range(epoch_number):
        for s in range(state_num):
            loop = True
            while loop:
                # Obtain random action a
                a = random_action(R[s,:])
                # Calculate maximum Q value
                q_max = np.max(Q[a,:])
                # Bellman optimal iteration equation
                Q[s,a] = R[s,a] + gamma * q_max
                s = a
                if s == condition_stop:
                    loop = False
    Q = (Q / 5).astype(int)
    print(Q)

实验结果如下所示，大约训练 200 轮之后 矩阵就可以收敛到理论值，并且理论推导与实验结果一致。

特别鸣谢

感谢 TCCI 天桥脑科学研究院对于 PaperWeekly 的支持。TCCI 关注大脑探知、大脑功能和大脑健康。