强化学习（1）：Q-Learning 算法

最近自己会把自己个人博客中的文章陆陆续续的复制到CSDN上来，欢迎大家关注我的 个人博客，以及我的github。

本文主要讲解有关 Q-Learning 算法的内容，主要包括 on-policy 和 off-policy 的概念、Q-Learning 算法的基本思想和算法流程，最后还会讲解一个莫烦大神的例子。

1. on-policy 和 off-policy

on-policy（同策略）： 智能体在自己做的过程中学习，即选择动作的策略和更新值函数的策略是同一个策略。；

off-policy（异策略）： 智能体在看别人做的过程中学习，即选择动作的策略和更新值函数的策略不是同一个策略。；

上述两种也被译作在线学习和离线学习。

同策略时间差分： sarsa、sarsa( λ \lambda λ)

异策略时间差分： 重要性采样、Q-learning、Deep Q Network

关于时间（时序）差分（TD）算法这里只提一句我的理解：时间差分是和蒙特卡洛（MC）方法相对应的，后者是对一个回合（episode）的数据采样，而前者是对一步或多步的数据采样。采样完毕之后再去计算数据的均值啊之类的。

2. Q-Learning 算法

Q-Learning 就是创造一个 Q 表来指导智能体的行动，Q 表的行是状态，列是动作。一个状态对应的动作的数值越大，则智能体采用该动作的概率越大。Q 表的每个值就是在上篇文章中提到的动作值函数 Q(s,a)。

Q 表更新公式如下：

Q ( S t , A t ) ← Q ( S t , A t ) + α [ R t + 1 + γ ⋅ max ⁡ Q ( S t + 1 ) − Q ( S t , A t ) ] Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma\cdot\max Q(S_{t+1})-Q(S_t,A_t)] Q(St​,At​)←Q(St​,At​)+α[Rt+1​+γ⋅maxQ(St+1​)−Q(St​,At​)]

其中 γ \gamma γ 为衰减值； α \alpha α 是学习率； max ⁡ Q ( S t + 1 ) \max Q(S_{t+1}) maxQ(St+1​) 是状态 S t + 1 S_{t+1} St+1​ 下概率最大的动作对应的 Q 表值，但是在实际行动时并不一定采取该行动； R t + 1 + γ max ⁡ Q ( S t + 1 ) R_{t+1}+\gamma\max Q(S_{t+1}) Rt+1​+γmaxQ(St+1​) 是根据贝尔曼方程得到的 Q ( S t + 1 , A t + 1 ) Q(S_{t+1},A_{t+1}) Q(St+1​,At+1​) 的推导值，后面称为 Q-target；而 Q ( S t , A t ) Q(S_t,A_t) Q(St​,At​) 是 Q ( S t + 1 , A t + 1 ) Q(S_{t+1},A_{t+1}) Q(St+1​,At+1​) 的估计值，后面称为 Q-eval。 R t + 1 + γ max ⁡ Q ( S t + 1 ) − Q ( S t , A t ) R_{t+1}+\gamma\max Q(S_{t+1})-Q(S_t,A_t) Rt+1​+γmaxQ(St+1​)−Q(St​,At​) 就是两者的误差值，在后面的文章中也称其为 TD-error（时分误差）。

根据动作值函数的定义（见上一篇文章）有：

Q ( S 1 ) = R 2 + γ Q ( S 2 ) = R 2 + γ [ R 3 + γ Q ( S 3 ) ] Q(S_1)=R_2+\gamma Q(S_2)=R_2+\gamma [R_3+\gamma Q(S_3)] Q(S1​)=R2​+γQ(S2​)=R2​+γ[R3​+γQ(S3​)]

= R 2 + γ [ R 3 + γ [ R 4 + γ Q ( S 4 ) ] ] = . . . =R_2+\gamma [R_3+\gamma [R_4+\gamma Q(S_4)]]=... =R2​+γ[R3​+γ[R4​+γQ(S4​)]]=...

所以：

Q ( S 1 ) = R 2 + γ R 3 + γ 2 R 4 + γ 3 R 5 + . . . Q(S_1)=R_2+\gamma R_3+\gamma^2 R_4+\gamma^3 R_5+... Q(S1​)=R2​+γR3​+γ2R4​+γ3R5​+...

当 γ = 1 \gamma=1 γ=1 时：

Q ( S 1 ) = R 2 + R 3 + R 4 + R 5 + . . . Q(S_1)=R_2+R_3+R_4+R_5+... Q(S1​)=R2​+R3​+R4​+R5​+...

也就是动作值函数与该状态之后的所有奖励有关，并且其权重相等。

当 γ = 0 \gamma=0 γ=0 时：

Q ( S 1 ) = R 2 Q(S_1)=R_2 Q(S1​)=R2​

也就是动作值函数只与该状态的前后一个奖励有关。

当 0 < γ < 1 0<\gamma<1 0<γ<1 时：

Q ( S 1 ) = R 2 + γ R 3 + γ 2 R 4 + γ 3 R 5 + . . . Q(S_1)=R_2+\gamma R_3+\gamma^2 R_4+\gamma^3 R_5+... Q(S1​)=R2​+γR3​+γ2R4​+γ3R5​+...

也就是说 Q 表实现了奖励值的衰减，离当前状态越远的奖励衰减的越严重。

3. Q-Learning 算法流程

（1）初始化 Q 表（值全为 0 ）

（2）根据当前状态选择一个 Action

（3）执行 Action 并获得相应的奖励，以及下一个状态

（4）按照公式更新 Q 表

（5）将下一个状态设为当前状态

（6）重复 2-5 步

值得注意的是在 Q-Learning 算法中有两个“ 策略”，一个是选取动作的策略，另一个是更新 Q 表的策略。这两个策略分别采用的是 ϵ \epsilon ϵ贪婪算法和最大值算法，所以 Q-Learning 是 off-policy 的。

4. 探索-利用困境

如果智能体仅仅按照 Q 表的最大概率指导行动的话，很多状态可能根本没办法达到，学习效率是比较低的，这就是探索-利用困境（Explore-Exploit dilemma）。可以用 ϵ \epsilon ϵ 贪婪（ ϵ − G r e e d y \epsilon-Greedy ϵ−Greedy）方法解决。

ϵ \epsilon ϵ 贪婪方法就是设定一个 0 < ϵ < 1 0<\epsilon<1 0<ϵ<1，并以 ϵ \epsilon ϵ 的概率按照 Q 表数值最大的动作行动，以 1 − ϵ 1-\epsilon 1−ϵ 的概率随机行动。

5. Q-Learning 版寻找宝藏的例子

以下代码实现了一个智能体（用字符 ‘o’ 表示）寻找宝藏（用字符 ‘T’ 表示）的强化学习过程，所用的算法是 Q-Learning 算法。当智能体找到宝藏时奖励值为 1，反之为 0。智能体的动作只有两个—— left 和 right，即向左移动和向右移动。程序会显示智能体和宝藏的位置、每个回合的奖励值以及终止状态时 Q 表的情况。

import numpy as np
import pandas as pd
import time

np.random.seed(2)

N_STATES = 6
ACTIONS = ['left', 'right']
EPSILON = 0.9
ALPHA = 0.1
GAMMA = 0.9
MAX_EPISODES = 10  # 回合数
FRESH_TIME = 0.3


def build_q_table(n_states, actions):  # 初始化 Q 表
    table = pd.DataFrame(
        np.zeros((n_states, len(actions))),
        columns=actions,  # 列的名称
    )
    return table


def choose_action(state, q_table):  # 根据当前状态和 Q 表选择一个动作
    # 如果随机数的值大于 EPSIlON 或者 Q 表的当前列都是 0 （即第一次到达该状态）
    if (np.random.uniform() > EPSILON or (q_table.iloc[state, :] == 0).all()):
        action_name = np.random.choice(ACTIONS)  # 随机选择一个动作
    else:
        action_name = q_table.iloc[state, :].idxmax()  # 选择当前状态对应的值最大的动作
    return action_name


def get_env_feedback(S, A):  # 获取新的状态和对应的奖励
    R = 0
    if A == "right":  # 往右
        S_ = S + 1
    else:  # 往左
        S_ = S - 1
        if S_ < 0:  # 如果到达最左端
            S_ = 0
    if S_ == N_STATES - 1:  # 如果找到宝藏
        S_ = "terminal"
        R = 1
    return S_, R


def update_env(S, episode, step_counter):  # 更新环境，主要是用来显示，可以不必搞懂
    env_list = ['-'] * (N_STATES - 1) + ['T']
    if S == "terminal":
        interaction = "Episode %s: total_steps = %s" % (episode + 1, step_counter)
        print("\r{}".format(interaction), end="")
        time.sleep(2)
        print("\r                                  ", end="")
    else:
        env_list[S] = 'o'
        interaction = "".join(env_list)
        print("\r{}".format(interaction), end="")
        time.sleep(FRESH_TIME)


def q_learning():  # Q-Learning 算法
    q_table = build_q_table(N_STATES, ACTIONS)
    for episode in range(MAX_EPISODES):
        S = 0
        step_counter = 0 # 共走了多少步
        is_terminal = False
        update_env(S, episode, step_counter)
        while not is_terminal:
            A = choose_action(S, q_table)
            S_, R = get_env_feedback(S, A)
            # 下面的代码是为了更新 Q 表
            q_predict = q_table.loc[S, A]
            if S_ != 'terminal':
                q_target = R + GAMMA * q_table.iloc[S_, :].max()
            else:  # 终止状态
                q_target = R
                is_terminal = True
            q_table.loc[S, A] += ALPHA * (q_target - q_predict)  # 根据公式更新
            S = S_
            step_counter += 1
            update_env(S, episode, step_counter)
    return q_table


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