会员服务 ·

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

2021 年 11 月 28 日 PaperWeekly

©PaperWeekly 原创 · 作者 | 孙裕道

学校 | 北京邮电大学博士生

研究方向 | GAN图像生成、情绪对抗样本生成

强化学习

强化学习注重智能体（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 或者状态 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)