深度强化学习基本算法——Q-Learning解释与简单复现

Author： SZnCu
发布时间：March 10, 2021
1618views
No comments
3837 words
Categories： Python 笔记机器学习

前言

前几个月看了下DRL与网络集群优化相关的一些文献，以及了解了一些基本的DRL的算法，这里做一个笔记来记录一下，也显得blog的内容会稍微高大上一点

什么是强化学习？

如图所示，在机器学习领域中主要有三类的学习方式，分别是监督学习、非监督学习和强化学习

监督学习用通俗的话就是，你给与机器一个输入，并且告诉机器它应该输出(预期输出)什么，让机器来学习如何让自己能够更好的将它的输出和你的预期输出贴近。因此监督学习通常用来做一些回归预测，分类等等问题。

非监督学习是直接对数据进行建模。没有给定事先标记过的训练范例，事先不知道输入数据对应的输出结果是什么，自动对输入的资料进行分类或分群，以寻找数据的模型和规律。因此通常用于聚类和降维等问题。

而强化学习更像是全开放式的机器学习，通过让机器不断地去进行某项任务，根据我们定义的奖赏措施来不断地优化自己的行为，从而让自己的表现能够能好，例如游戏AI(大名鼎鼎的AlphaGo)等。

强化学习相关算法

强化学习主要算法分为Value Based和Policy Based两种：

Value Based
- Q-Learning
- DQN
- Sarsa
Policy Based
- Policy Gradient
- PPO
- A2C/A3C
- Actor-Critic

当然还有将上面的算法模型进行结合来得到的新算法例如DDPG(Actor-Critic + DQN)或者RDRL(DDPG+LSTM)等

Q-Learning

在了解Q-Learning之前，先要弄清楚强化学习一些基本的概念，其中State、Actor和Reward联系紧密因此放在一起来说

1. 状态State, 2. 动作Actor, 3. 奖赏Reward

State&Actor&Reward

首先说下Reward

所谓Reward就是机器学习智能体根据自己行为(Action)所获得的奖赏，这个是由你自己来定义的，而且定义的奖赏值和整体性能关系非常之大。

狼吃羊小游戏

例如前些时间就出现了一个新闻：某DRL开发者在训练一个狼吃羊的游戏AI时，发现经过五万次训练之后，狼上去就选择直接一头撞死。看起来非常的荒谬，但问题也是相当的简单。在作者对Reward的定义中，包括：

原地站着15秒得-1.5分；
一头扎死得-1.1分；
尝试绕路但是撞死得-1.1 到-2.4分。

所以由于狼根本没有吃到过羊，正数的奖赏一直不会出现，因此狼在-1.1到-2.4分之间选择了-1.1，也就是自杀。

再说说State与Actor

State就是AI智能体当前所处的状态，例如上面的狼吃羊的游戏中，游戏的每一帧都对应一个状态。例如狼即将撞到墙时，狼看见羊时。

而Actor就是狼具体采取的动作，比如快撞到墙的时候它可以选择直接装上去，或者按其他的键逃离现场等等。。

最开始那个图就是AI智能体首先观测到State1，然后根据某种算法选择了一个Actor(Action)，开火，最后打死一只敌人，得到我们定义的奖赏Reward=5。这样以后机器人在遇见同一种情况的话，他就会直到此时应该开火而不是逃避才能获得更高的分数。

4. Episode

所谓Episode就是一次完整的训练，例如AI智能体的一次完整的游戏过程。

Episode

因此一个Episode可以看成是State,Action,Reward的集合，比如在s1(state 1)下，采取了a1(action 1)，得到了r1(reward 1)，然后进入s2...

5. Critic

Critic可以看做是一个状态价值函数，自变量是state，输出是累积reward。他根据当前的state，采取一系列动作Actor π后，评估可以之后得到的期望总和。

Critic

如图，当游戏刚开始时，未来可以得到的期望总和很多(因为还有很多敌人没死，每个敌人都有得分)。而第二张图表示游戏快要结束了，此时我们在未来能得到的Reward就很少了，此时状态价值函数的值也很少。

补充：如何评估状态价值函数(Critic)呢？

主要有两种方式，分别是基于蒙特卡洛的方式和TD方式

Monte-Carlo方式

通俗的说就是，我们人为来观察一整场游戏来定义一个理想Reward总和(图上的Ga,Gb)，然后训练Critic函数让自己算得的实际Reward总和不断地来逼近我们的这个理想值。

Temporal-Difference方式

TD方式

TD方式主要是通过两个state之间的收益差来实现，因为当从一个state进入下一个state之后，我们总能得到一个reward，这样我们只要让我们得到的reward尽量去逼近理想的reward就好了。

Q-Function

对比于状态价值函数，Q-Function叫做动作价值函数，是用来评估action的好坏程度的

Q-Function

注意Actor π是一个动作集合，而不是单一动作。也就是当π固定之后，此时Q会根据在某个state下采取action的好坏程度。

对比一下Q-Function和State Value Function

简而言之就是一个是评估在具体state下采取action的好坏程度的，另一个是评估当前state好坏程度的

Q-Table

有了上面的铺垫，接下来就可以理解Q-Learning的核心——Q-Table了

简单Q表说明

Q-Table是一个表，是一个在具体state下采取action的reward值集合

例如上图，在熊吼的时候，如果装死的话，我们可以暂避危险，此时定义reward为0(因为人还没有脱险)

而如果在熊吼的时候，我们选择跑的话，大概率就要被熊给吃了，此时reward为很大的负值

而当熊回头不看我们的时候，我们也可以选择继续装死或者跑，如果我们跑了的话，此时离危险也就越来越远了，可以得到正的reward。而继续不动的话，仍然没有脱离险境，定义reward仍然为0(不好也不坏)。

训练Q-Table

使用TD方式来训练Q表的过程如下图所示

用伪代码描述的话，就是

initialize Q = {};
while Q 未收敛:
    初始化actor位置S，开始新一轮episode
    while S != terminate:
        使用策略π，获得动作a=π(s)
        进行动作a，获取S`,与奖励R(S,a)
        更新Q表：Q[S,A] <- (1-α)*Q[S,A] + α*(R(S,a) + γ*max Q[S`,a])
        S <- S`

简单的Q-Learning复现

☺— — — — — — — ☆ 小游戏

我们让AI来操作上面的笑脸去吃最右边的星星，操作只有向左或者向右，定义Reward为吃到星星为1，没吃到为0

第一个Episode的时候Q表为空，因此只能靠随机选取左右的方式，但随着Episode的增加，Q表内容逐渐被填充。

选择动作的策略是根据贪婪因子来决定的，下面的设置为0.9，代表90%的概率来选择Q表中reward大的动作，10%来选择另外一个动作(为了防止陷入局部最优解)

大家跑一下就会发现，一开始人工智障需要操作50甚至上百次才能吃到星星，但经过几轮Episode的训练之后，就已经收敛到了8步就吃到星星了。

源码：

import numpy as np
import pandas as pd
import time

N_STATES = 9    # 游戏中位置个数
ACTIONS = ['left', 'right']        # 动作集合
GREEDY_POLICY = 0.9        # 贪婪策略
ALPHA = 0.1        # Learning rate
GAMMA = 0.95    # 衰减因子
MAX_EPISODES = 10    # Episode数
TIME_JG = 0.2    # 小人动作的时间间隔


def build_q_table(n_states, actions):
    table = pd.DataFrame(
        np.zeros((n_states, len(actions))), columns=actions,
    )
    return table


def choose_action(state, q_table):
    state_actions = q_table.iloc[state, :]
    if (np.random.uniform() > GREEDY_POLICY) or ((state_actions == 0).all()):
        action_name = np.random.choice(ACTIONS)
    else:
        action_name = state_actions.idxmax()
    return action_name


def get_env_feedback(S, A):
    if A == 'right':
        if S == N_STATES - 2:
            S_ = 'terminal'
            R = 1
        else:
            S_ = S + 1
            R = 0
    else:
        R = 0
        if S == 0:
            S_ = S
        else:
            S_ = S - 1
    return S_, R


def update_env(S, episode, step_counter):
    env_list = ['—'] * (N_STATES - 1) + ['☆']
    if S == 'terminal':
        interaction = '第 %s 个episode,总共步数为 = %s' % (episode + 1, step_counter)
        print('\r{}'.format(interaction), end='')
        time.sleep(3)
        print('\r                                ', end='')
    else:
        env_list[S] = '☺'
        interaction = ''.join(env_list)
        print('\r{}'.format(interaction), end='')
        time.sleep(TIME_JG)


def ql():
    q_table = build_q_table(N_STATES, ACTIONS)
    for episode in range(MAX_EPISODES):
        step_counter = 0
        S = 0
        is_terminated = False
        update_env(S, episode, step_counter)
        print('\n', q_table)
        while not is_terminated:
            A = choose_action(S, q_table)
            S_, R = get_env_feedback(S, A)
            q_predict = q_table.loc[S, A]
            if S_ != 'terminal':
                q_target = R + GAMMA * q_table.iloc[S_, :].max()
            else:
                q_target = R
                is_terminated = True

            q_table.loc[S, A] += ALPHA * (q_target - q_predict)
            S = S_

            update_env(S, episode, step_counter + 1)
            step_counter += 1
    return q_table


if __name__ == "__main__":
    q_table = ql()
    print('\r\nQ-table:\n')
    print(q_table)

Q-Learning存在的不足

1. Only support discrete

首先最关键的一点就是Q表只能存储离散的动作形式，例如向左或者向右或者上下，而很多游戏中人物的操作都是连续的。

对于这种情况可以考虑使用化连续为离散来初步解决，例如将连续的动作划分为很多离散的部分组合，这样就能够继续填充Q表

2. Curse of dimension

最大的缺陷还是对于具体应用中，Q表的维度可能会爆表。

例如国际象棋总共有10^47次方个state，而围棋更是有10^170个state，而在FPS游戏中，state数量是uncountable的

解决方式

为了解决上面的不足，于是DQN算法(Deep Q-Learning)就于2015年发表在Nature上的一篇文献提出来了

有兴趣的同学可以去看一看，文献为

Mnih et al. Human-Level control through deep reinforcement learning. Nature, 2015.

DQN对于Q-Learning有三个比较大的改进

Import Neural Network
- 通过导入神经网络，使得强化学习可以叫做深度强化学习了
Q-Table -> Neural Network(using CNN)
- 通过使用CNN神经网络来代替Q表，使得处理连续动作成为可能
Import experience replay
- 经验回放也是DQN的非常重要的创新点，本来它是1993年就被提出了，但是一直到2015年DQN出现之前经验回放一直无人问津，而DQN的出现也成功推广了经验回放机制

Last modification：March 10th, 2021 at 04:46 pm

深度强化学习基本算法——Q-Learning解释与简单复现

SZnCu • 2021 年 03 月 10 日

前言

前几个月看了下DRL与网络集群优化相关的一些文献，以及了解了一些基本的DRL的算法，这里做一个笔记来记录一下，也显得blog的内容会稍微高大上一点

什么是强化学习？

如图所示，在机器学习领域中主要有三类的学习方式，分别是监督学习、非监督学习和强化学习

强化学习相关算法

强化学习主要算法分为Value Based和Policy Based两种：

Value Based
- Q-Learning
- DQN
- Sarsa
Policy Based
- Policy Gradient
- PPO
- A2C/A3C
- Actor-Critic

当然还有将上面的算法模型进行结合来得到的新算法例如DDPG(Actor-Critic + DQN)或者RDRL(DDPG+LSTM)等

Q-Learning

在了解Q-Learning之前，先要弄清楚强化学习一些基本的概念，其中State、Actor和Reward联系紧密因此放在一起来说

1. 状态State, 2. 动作Actor, 3. 奖赏Reward

State&Actor&Reward

首先说下Reward

所谓Reward就是机器学习智能体根据自己行为(Action)所获得的奖赏，这个是由你自己来定义的，而且定义的奖赏值和整体性能关系非常之大。

狼吃羊小游戏

原地站着15秒得-1.5分；
一头扎死得-1.1分；
尝试绕路但是撞死得-1.1 到-2.4分。

所以由于狼根本没有吃到过羊，正数的奖赏一直不会出现，因此狼在-1.1到-2.4分之间选择了-1.1，也就是自杀。

再说说State与Actor

State就是AI智能体当前所处的状态，例如上面的狼吃羊的游戏中，游戏的每一帧都对应一个状态。例如狼即将撞到墙时，狼看见羊时。

而Actor就是狼具体采取的动作，比如快撞到墙的时候它可以选择直接装上去，或者按其他的键逃离现场等等。。

4. Episode

所谓Episode就是一次完整的训练，例如AI智能体的一次完整的游戏过程。

Episode

因此一个Episode可以看成是State,Action,Reward的集合，比如在s1(state 1)下，采取了a1(action 1)，得到了r1(reward 1)，然后进入s2...

5. Critic

Critic可以看做是一个状态价值函数，自变量是state，输出是累积reward。他根据当前的state，采取一系列动作Actor π后，评估可以之后得到的期望总和。

Critic

补充：如何评估状态价值函数(Critic)呢？

主要有两种方式，分别是基于蒙特卡洛的方式和TD方式

Monte-Carlo方式

Temporal-Difference方式

TD方式

Q-Function

对比于状态价值函数，Q-Function叫做动作价值函数，是用来评估action的好坏程度的

Q-Function

注意Actor π是一个动作集合，而不是单一动作。也就是当π固定之后，此时Q会根据在某个state下采取action的好坏程度。

对比一下Q-Function和State Value Function

简而言之就是一个是评估在具体state下采取action的好坏程度的，另一个是评估当前state好坏程度的

Q-Table

有了上面的铺垫，接下来就可以理解Q-Learning的核心——Q-Table了

简单Q表说明

Q-Table是一个表，是一个在具体state下采取action的reward值集合

例如上图，在熊吼的时候，如果装死的话，我们可以暂避危险，此时定义reward为0(因为人还没有脱险)

而如果在熊吼的时候，我们选择跑的话，大概率就要被熊给吃了，此时reward为很大的负值

训练Q-Table

使用TD方式来训练Q表的过程如下图所示

用伪代码描述的话，就是

initialize Q = {};
while Q 未收敛:
    初始化actor位置S，开始新一轮episode
    while S != terminate:
        使用策略π，获得动作a=π(s)
        进行动作a，获取S`,与奖励R(S,a)
        更新Q表：Q[S,A] <- (1-α)*Q[S,A] + α*(R(S,a) + γ*max Q[S`,a])
        S <- S`

简单的Q-Learning复现

☺— — — — — — — ☆ 小游戏

我们让AI来操作上面的笑脸去吃最右边的星星，操作只有向左或者向右，定义Reward为吃到星星为1，没吃到为0

第一个Episode的时候Q表为空，因此只能靠随机选取左右的方式，但随着Episode的增加，Q表内容逐渐被填充。

大家跑一下就会发现，一开始人工智障需要操作50甚至上百次才能吃到星星，但经过几轮Episode的训练之后，就已经收敛到了8步就吃到星星了。

源码：

import numpy as np
import pandas as pd
import time

N_STATES = 9    # 游戏中位置个数
ACTIONS = ['left', 'right']        # 动作集合
GREEDY_POLICY = 0.9        # 贪婪策略
ALPHA = 0.1        # Learning rate
GAMMA = 0.95    # 衰减因子
MAX_EPISODES = 10    # Episode数
TIME_JG = 0.2    # 小人动作的时间间隔


def build_q_table(n_states, actions):
    table = pd.DataFrame(
        np.zeros((n_states, len(actions))), columns=actions,
    )
    return table


def choose_action(state, q_table):
    state_actions = q_table.iloc[state, :]
    if (np.random.uniform() > GREEDY_POLICY) or ((state_actions == 0).all()):
        action_name = np.random.choice(ACTIONS)
    else:
        action_name = state_actions.idxmax()
    return action_name


def get_env_feedback(S, A):
    if A == 'right':
        if S == N_STATES - 2:
            S_ = 'terminal'
            R = 1
        else:
            S_ = S + 1
            R = 0
    else:
        R = 0
        if S == 0:
            S_ = S
        else:
            S_ = S - 1
    return S_, R


def update_env(S, episode, step_counter):
    env_list = ['—'] * (N_STATES - 1) + ['☆']
    if S == 'terminal':
        interaction = '第 %s 个episode,总共步数为 = %s' % (episode + 1, step_counter)
        print('\r{}'.format(interaction), end='')
        time.sleep(3)
        print('\r                                ', end='')
    else:
        env_list[S] = '☺'
        interaction = ''.join(env_list)
        print('\r{}'.format(interaction), end='')
        time.sleep(TIME_JG)


def ql():
    q_table = build_q_table(N_STATES, ACTIONS)
    for episode in range(MAX_EPISODES):
        step_counter = 0
        S = 0
        is_terminated = False
        update_env(S, episode, step_counter)
        print('\n', q_table)
        while not is_terminated:
            A = choose_action(S, q_table)
            S_, R = get_env_feedback(S, A)
            q_predict = q_table.loc[S, A]
            if S_ != 'terminal':
                q_target = R + GAMMA * q_table.iloc[S_, :].max()
            else:
                q_target = R
                is_terminated = True

            q_table.loc[S, A] += ALPHA * (q_target - q_predict)
            S = S_

            update_env(S, episode, step_counter + 1)
            step_counter += 1
    return q_table


if __name__ == "__main__":
    q_table = ql()
    print('\r\nQ-table:\n')
    print(q_table)

Q-Learning存在的不足

1. Only support discrete

首先最关键的一点就是Q表只能存储离散的动作形式，例如向左或者向右或者上下，而很多游戏中人物的操作都是连续的。

对于这种情况可以考虑使用化连续为离散来初步解决，例如将连续的动作划分为很多离散的部分组合，这样就能够继续填充Q表

2. Curse of dimension

最大的缺陷还是对于具体应用中，Q表的维度可能会爆表。

例如国际象棋总共有10^47次方个state，而围棋更是有10^170个state，而在FPS游戏中，state数量是uncountable的

解决方式

为了解决上面的不足，于是DQN算法(Deep Q-Learning)就于2015年发表在Nature上的一篇文献提出来了

有兴趣的同学可以去看一看，文献为

Mnih et al. Human-Level control through deep reinforcement learning. Nature, 2015.

DQN对于Q-Learning有三个比较大的改进

Import Neural Network
- 通过导入神经网络，使得强化学习可以叫做深度强化学习了
Q-Table -> Neural Network(using CNN)
- 通过使用CNN神经网络来代替Q表，使得处理连续动作成为可能
Import experience replay
- 经验回放也是DQN的非常重要的创新点，本来它是1993年就被提出了，但是一直到2015年DQN出现之前经验回放一直无人问津，而DQN的出现也成功推广了经验回放机制

前言

什么是强化学习？

强化学习相关算法

Q-Learning

1. 状态State, 2. 动作Actor, 3. 奖赏Reward

首先说下Reward

再说说State与Actor

4. Episode

5. Critic

补充：如何评估状态价值函数(Critic)呢？

Monte-Carlo方式

Temporal-Difference方式

Q-Function

对比一下Q-Function和State Value Function

Q-Table

训练Q-Table

简单的Q-Learning复现

Q-Learning存在的不足

1. Only support discrete

2. Curse of dimension

解决方式