简单的Q-learning|小明的一维世界(1)

简单的Q-learning|小明的一维世界（1）
简单的Q-learning|小明的一维世界（2）
简单的Q-learning|小明的一维世界（3）

Q-learning 已经成为强化学习中最有效的算法之一。虽然，它也存在一些缺点，例如离散的动作。不管怎样，Q-learning在许多应用中的有效性已经得到验证。另一方面，在众多强化学习算法中，Q-learning的原理相对简单，适合作为强化学习的入门算法。本篇旨在将最简单的基于Q-table的Q-learning算法应用在一维环境的简单应用，让我们从复杂的算法世界中抽身出来，只感受Q-learning。

小明的一维世界

大家去过有湖的公园，可能会见过下图所示的水中一个个石墩构成的水中小路。这水中的小路就是小明的一维世界。假设每次小明只允许站在其中某一个石墩上，从第一个石墩走向另一个石墩的过程不算。

我们把这个水中的石墩小路抽象成小明的一维世界。最中间的那块石墩上有100块钱（别问是谁闲的没事，是我闲的没事放的好吧=v=）。现在小明需要拿到那100块钱。我们很容易理解，如果小明在中间石墩的两边，需要往中间走就可以。完全正确！！！

以上的假设是小明能控制左移一格、右移一格、或者不动。那假如小明只能控制自己的速度加一个单位、减一个单位、或者不变呢；又假如小明只能控制自己的加速度增减一个单位、或不变呢。小明该怎么控制自己能控制的量使得自己最终正好到达中间那块石头上时是稳态（速度，加速度都为零）。注意，只有在稳态时，小明才能拿到钱哦！

拿出笔纸了？先别急，我们肯定是可以通过数理分析得出合适的策略。让我们先看看Q-learning是怎么做到的。

重新整理三种不同的小明的一维世界：

1. 位置世界：小明能控制自己左移一格、右移一格、或者不移动。
2. 速度世界：小明能控制自己的速度增减一、或者不变。
3. 加速度世界：小明能控制自己的加速度增减一、或者不变。

下面分别介绍Q-learning算法对于三种不同的小明的一维世界，怎么计算出合适的策略给小明。让小明成功的拿到100块钱。

Q-learning简介

由于介绍Q-learning原理的博客很多、很多！此处不详细说明，只列出本文要用的概念和公式。如果想要了进一步了解Q-learning算法可参考深度强化学习|知乎。

Q-learning算法的训练样本是一个四元组$<s_t, a_t, s_{t+1}, r_t>$。从状态$s_t$选择动作$a_t$后，转移到下一个状态$s_{t+1}$，并获得回报值$r_t$。

此处的状态空间是离散的**[离散的位置（石墩）、离散的速度（增量减量为1或者0）、离散的加速度（增量减量为1或者0）]**。

假设状态的个数为$N$，动作的个数为$M$，我们利用Q-table存储每个状态-动作对的Q value。而这个Q value是一个$N\times M$的矩阵。

假设此时获得样本$<s_t, a_t, s_{t+1}, r_t>$,我们利用以下公式对Q-table进行更新：$Q(s_t, a_t)=r_t+\gamma \max_{a\in A} Q(s_{t+1}, a)$其中,$\gamma$为步长折扣， $Q(s,a)$表示状态$s$与动作$a$对应Q-table中的值。

只要充足的探索样本，Q-table中的Q value就会收敛到真实的值。

而每个状态对应动作的Q值$Q(s, a)$，表示在当前状态下采取某个动作的价值，价值最大的动作被认为是当前状态的最优动作。所以，我们可以从收敛的Q-table中导出策略：$a^*=arg\max_{a\in A} Q(s,a)$

对于理解Q-learning算法并不难，可能更加重要的是对状态空间、动作空间以及reward函数的定义，如果这些准备工作做的很好，基本上Q-learning的训练已经成功了90%了。另外10%是训练算法的流程和一些小trick。例如：利用neural network 替代Q-table,利用一个经验回放单元来存储固定窗口内的样本等等(还有很多)……以提高Q-learning的学习效率。但是，但是，但是，这些不是本篇的目的。因为这些思想已经形成大篇已经发表的文章和很透彻的博客文章。而本篇重点在状态空间、动作空间以及reward函数定义。这个简单的环境，可以让我们从复杂的算法世界中抽身出来，更好的理解Q-learning。

一维的位置世界

小明在位置世界，只能控制自己的位置左移一格、右移一格、或不动。小明在每块石头上，也只有这三个动作可以选择。由于太过直观，在中间石头两边的石头上时，小明只需要向中间走就可以了。那么，我们来看看Q-learning怎么做的。

这个世界真的很简单，小明的状态只是一些位置，重复引这张图。小明总共有21个状态，我们将它们从左到右依标记为——状态空间

$\{s_1=-10, s_2=-9, …, s_{11}=0, …, s_{20}=9, s_{21}=10\}$

小明总共有三个可用动作，左移一格、右移一格、以及不移动。我们将这三个动作标记为——行动空间

$\{a_1=-1, a_2=0, a_3=1\}$

Q-table
$Q_{table}=\left[\begin{matrix} & a_1& a_2& a_3 \\ s_1 & * & * & * \\ s_2 & * & * & * \\ … & … &…&… \\ s_N & *&*&* \end{matrix}\right]$
其中，$N$为状态的个数，$Q_{table}$矩阵中的元素为对应$Q(s,a)$。此处，在算法初始化时，$Q_{table}$中的元素全部初始化为0。

假定经过一段时间训练后，得到训练收敛的$Q_{table}$，我们怎么利用这些$Q$值来引导小明在特定状态下采取正确的行动呢——也即导出策略,可利用下式：
$a^*= arg\max_{a\in A} Q(s, a)$

不同的奖励函数设置

给出代码

import numpy as np

def model_update(x,a): # 位置模型
    x = x+a
    if x < -10:   # 保持状态不超出区间
        x = -10
    if x > 10:
        x = 10    
    return x
xt = np.random.randint(-9, 10) # 随机初始化一个状态（位置）
Q_table = np.zeros((21, 3)) # 初始化Q table，全为零
for i in range(1000):
    r = 0.0        
    a = np.random.randint(0,3)-1
    xt1 = model_update(xt, a) #调用模型生成下一个状态
#     if xt1 == 0: # 稀疏奖励
#         r = 10.0
    r = -abs(xt1) # 稠密奖励
    Q_table[xt+10, a+1] = r+0.9*np.max(Q_table[xt1+10]) # 更新Q table
    xt = xt1   
print(Q_table) # 打印Q table
复制代码

1. 稀疏的奖励函数

中间的位置能拿到100块钱，所以中间的位置的奖励最大。我们赋予它一个很大的正奖励$r(s=0)=10.0$。而其它的位置即无害也无明显的益处，故将它们的奖励设为0。收敛步长需要2000步左右。

• $Q_{table}$

2. 稠密的奖励函数

$r(s)=-|s|$

这样的话，所有状态都对应一个有意义的奖励值$\{r(s_1)=r(s_{21})=-10\}\\ \{r(s_2)=r(s_{20})=-9\} \\ \{r(s_3)=r(s_{19})=-8\} \\ \{r(s_4)=r(s_{18})=-7\} \\ \{r(s_5)=r(s_{17})=-6\} \\ \{r(s_6)=r(s_{16})=-5\} \\ \{r(s_7)=r(s_{15})=-4\} \\ \{r(s_8)=r(s_{14})=-3\} \\ \{r(s_9)=r(s_{13})=-2\} \\ \{r(s_{10})=r(s_{12})=-1\} \\ \{r(s_{11})=0\}$

解释为，离中间石头越远的石头，需要到达中间石头的代价越大，也即奖励值越小。最短的时候，200步就收敛了。

• $Q_{table}$

总之，最后都能收敛。总体上，稠密的奖励要比稀疏的奖励收敛速度要快很多。最终学习到的策略都能引导小明从任意位置到达中间位置，并停在那儿——拿那一百块钱。

• 假定小明在最左的位置，学到的策略使它一步一步向中间靠近。

import matplotlib
import matplotlib.pyplot as plt
import time
%matplotlib inline

/*** plt 动态显示 ***/
is_ipython = 'inline' in matplotlib.get_backend()
if is_ipython:
    from IPython import display   
plt.ion()

x = np.arange(-10, 11)
y = np.zeros(21)
xt = -10
for i in range(20):
    a = np.argmax(Q_table[xt+10])-1  # Q值导出策略
    xt1 = model_update(xt, a)
#     print(xt, a, xt1)
    xt = xt1
    plt.clf()
    plt.plot(x, y, 'ob')
    plt.plot(0.0,0.0,'or')
    plt.plot(xt,0, 'og')
    plt.pause(0.1)
    if is_ipython:
        display.clear_output(wait=True)
        display.display(plt.gcf())
复制代码

step.$(s_t, a_t, s_{t+1})$
1.$(-10, 1, -9)$
2.$(-9, 1, -8)$
3.$(-8, 1, -7)$
4.$(-7, 1, -6)$
5.$(-6, 1, -5)$
6.$(-5, 1, -4)$
7.$(-4, 1, -3)$
8.$(-3, 1, -2)$
9.$(-2, 1, -1)$
10.$(-1, 1, 0)$
11.$(0, 0, 0)$

动态图——绿色的点代表小明——红色的点代表小明要到达的位置。

简单的Q-learning|小明的一维世界（2）
简单的Q-learning|小明的一维世界（3）