强化学习与Q-learning的简单实现
冒个泡..昨天是立冬啦（虽然福州还是艳阳天）~时间很快，学习也要抓紧鸭！今天就来看一下强化学习。
强化学习
定义
什么是强化学习呢？其实强化学习在我们的生活中并不陌生，比如前阵子的Alpha go就是一个典型的例子。简单来说，深度学习是通过学习选择能达到目标最优动作的一个策略过程，本质是在解决 decision making 问题，即自动进行决策，并且可以做连续决策。
image.png
一个完整的强化学习过程：让计算机实现从一开始什么都不懂, 脑袋里没有一点想法, 通过不断地尝试, 从错误中学习, 最后找到规律, 学会了达到目的的方法。
要素
【可参考马尔可夫决策过程（Markov Decision Process，简称MDP）】
image.png
状态（x）：机器对环境的感知，所有可能的状态称为状态空间；
动作（a）：机器所采取的动作，所有能采取的动作构成动作空间；
转移概率（p）：当执行某个动作后，当前状态会以某种概率转移到另一个状态
奖赏函数（r）：在状态转移的同时，环境给反馈给机器一个奖赏。
因此，强化学习的主要任务就是通过在环境中不断地尝试，根据尝试获得的反馈信息调整策略，最终生成一个较好的策略，机器根据这个策略便能知道在什么状态下应该执行什么动作。
辨析
a.强化学习与监督学习的区别
1.首先，监督学习, 是已经有了数据和数据对应的正确标签，而强化学习是在没有任何标签的情况下，通过先尝试做出一些行为得到一个结果，通过这个结果是对还是错的反馈，调整之前的行为，就这样不断的调整，算法能够学习到在什么样的情况下选择什么样的行为可以得到最好的结果。
对比图.png
2.两种学习方式都会学习出输入到输出的一个映射，监督式学习出的是之间的关系，可以告诉算法什么样的输入对应着什么样的输出，强化学习出的是给机器的反馈，即用来判断这个行为是好是坏。
3.强化学习的结果反馈有延时，有时候可能需要走了很多步以后才知道以前的某一步的选择是好还是坏，而监督学习做了比较坏的选择会立刻反馈给算法。
4.强化学习面对的输入总是在变化，每当算法做出一个行为，它影响下一次决策的输入，而监督学习的输入是独立同分布的。
b.强化学习与无监督学习的区别
非监督式不是学习输入到输出的映射，而是模式。
例如在向用户推荐新闻文章的任-务中，非监督式会找到用户先前已经阅读过类似的文章并向他们推荐其一（聚类），而强化学习将通过向用户先推荐少量的新闻，并不断获得来自用户的反馈，最后构建用户可能会喜欢的文章的“知识图”。
（总的来说，强化学习的重在通过反馈去做决策。）
接下来介绍一下强化学习中的Q-learning以及简单实现
Q-learning
首先，Q-learning是强化学习中的一种算法。
image.png
Q-learning关键在于是Q-table。Q-table的行和列分别表示state和action的值，Q-table的值Q(s,a)衡量当前state采取action到底好不好，即接受反馈。*
Q函数
Q-table中的值根据如下的公式来进行不断更新：
image.png
在这个公式里:
s→当前状态
a→当前动作
r→当前的收益
γ→折扣因子，表示时间的远近对回报的影响程度（通常在0-1之间）
s'→下一个状态
a'→下一个动作（Q(s',a'）要在Q-Table里面查询）
接下来就举个栗子来说明Q-learning：
假设我们在一个由门连接的建筑物中有5个房间，如下图所示。我们将每个房间编号为0到4.建筑物的外部可以被认为是一个大房间（5）。请注意，1号门和4号门从5号房间（外部）通向建筑物。
image.png
对于这个例子，我们想把一个代理人放在任何房间，从那个房间，走到大楼外面（这将是我们的目标房间，也就是5号房间）。要将此房间设置为目标，我们会将奖励值与每个门相关联（即节点之间的链接）。直接通向目标的门具有100的即时奖励。与目标房间没有直接连接的其他门没有奖励。
对于这个问题我们可以先简化为点线且线之间具有值的网络图。
image.png
接下来我们可以根据这个图来创建一个R矩阵。
（没有相连的点之间为-1，相连但是不与目标相连的为0，与目标相连的为100）
image.png
这个时候也要创建一个Q-Table,来不断更新。（Q表要求和R行列一致且都为0）
image.png
然后随机选择一个状态，比如选取1，查看状态1所对应的R表（值不为-1的），也就是1可以到达3或5，我们随机我们选择5，则Q函数和更新后的Q表可为：
image.png
这样的话，就到达目标5号，一次尝试结，成功。
再选择一个随机状态，比如3，3对应的下一个状态有1，2，4，我们随机选择1，则Q函数和更新后的Q表可为：
image.png
然后经过不断迭代最后得到的表如下：
image.png
综上可以得到Q-learning的算法步骤为：
利用Q矩阵的算法：
1.设置当前状态=初始状态。
2.从当前状态，找到具有最高Q值的动作。
3.设置当前状态=下一状态。
4.重复步骤2和3，直到当前状态=目标状态。
用代码实现：
import numpy as np
# 将Q矩阵初始化为0
q = np.matrix(np.zeros([6, 6]))
# 报酬矩阵为提前定义好的
#-1表示无相连接的边，100为最后通向出口，0表示有连接。
r = np.matrix([[-1, -1, -1, -1, 0, -1],
[-1, -1, -1, 0, -1, 100],
[-1, -1, -1, 0, -1, -1],
[-1, 0, 0, -1, 0, -1],
[ 0, -1, -1, 0, -1, 100],
[-1, 0, -1, -1, 0, 100]])
#折扣因子（γ）
gamma = 0.8
#是否选择最后策略的概率
e= 0.4
# the main training loop
for time in range(101):
# random initial state
state = np.random.randint(0, 6)
# 如果不是最终转态
while (state != 5):
# 选择可能的动作
possible_actions = []
possible_q = []
for action in range(6):
if r[state, action] >= 0:
possible_actions.append(action)
possible_q.append(q[state, action])
action = -1
if np.random.random() < e:
# 随意选择
action = possible_actions[np.random.randint(0, len(possible_actions))]
else:
action = possible_actions[np.argmax(possible_q)]
# 更新
q[state, action] = r[state, action] + gamma * q[action].max()
#下一步
state = action
# 输出训练过程
if time % 10 == 0:
print("------------------------------------------------")
print("训练的次数为: %d" % time)
print(q)
结果为：
训练的次数为: 0
[[ 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 0. 100.]
[ 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 0. 0.]]
------------------------------------------------
训练的次数为: 10
[[ 0. 0. 0. 0. 80. 0.]
[ 0. 0. 0. 0. 0. 100.]
[ 0. 0. 0. 64. 0. 0.]
[ 0. 0. 0. 0. 80. 0.]
[ 64. 0. 0. 0. 0. 100.]
[ 0. 0. 0. 0. 0. 0.]]
------------------------------------------------
训练的次数为: 20
[[ 0. 0. 0. 0. 80. 0.]
[ 0. 0. 0. 0. 0. 100.]
[ 0. 0. 0. 64. 0. 0.]
[ 0. 80. 0. 0. 80. 0.]
[ 64. 0. 0. 0. 0. 100.]
[ 0. 0. 0. 0. 0. 0.]]
------------------------------------------------
训练的次数为: 30
[[ 0. 0. 0. 0. 80. 0.]
[ 0. 0. 0. 0. 0. 100.]
[ 0. 0. 0. 64. 0. 0.]
[ 0. 80. 0. 0. 80. 0.]
[ 64. 0. 0. 64. 0. 100.]
[ 0. 0. 0. 0. 0. 0.]]
------------------------------------------------
训练的次数为: 40
[[ 0. 0. 0. 0. 80. 0. ]
[ 0. 0. 0. 0. 0. 100. ]
[ 0. 0. 0. 64. 0. 0. ]
[ 0. 80. 51.2 0. 80. 0. ]
[ 64. 0. 0. 64. 0. 100. ]
[ 0. 0. 0. 0. 0. 0. ]]
------------------------------------------------
训练的次数为: 50
[[ 0. 0. 0. 0. 80. 0. ]
[ 0. 0. 0. 64. 0. 100. ]
[ 0. 0. 0. 64. 0. 0. ]
[ 0. 80. 51.2 0. 80. 0. ]
[ 64. 0. 0. 64. 0. 100. ]
[ 0. 0. 0. 0. 0. 0. ]]
------------------------------------------------
训练的次数为: 60
[[ 0. 0. 0. 0. 80. 0. ]
[ 0. 0. 0. 64. 0. 100. ]
[ 0. 0. 0. 64. 0. 0. ]
[ 0. 80. 51.2 0. 80. 0. ]
[ 64. 0. 0. 64. 0. 100. ]
[ 0. 0. 0. 0. 0. 0. ]]
------------------------------------------------
训练的次数为: 70
[[ 0. 0. 0. 0. 80. 0. ]
[ 0. 0. 0. 64. 0. 100. ]
[ 0. 0. 0. 64. 0. 0. ]
[ 0. 80. 51.2 0. 80. 0. ]
[ 64. 0. 0. 64. 0. 100. ]
[ 0. 0. 0. 0. 0. 0. ]]
------------------------------------------------
训练的次数为: 80
[[ 0. 0. 0. 0. 80. 0. ]
[ 0. 0. 0. 64. 0. 100. ]
[ 0. 0. 0. 64. 0. 0. ]
[ 0. 80. 51.2 0. 80. 0. ]
[ 64. 0. 0. 64. 0. 100. ]
[ 0. 0. 0. 0. 0. 0. ]]
------------------------------------------------
训练的次数为: 90
[[ 0. 0. 0. 0. 80. 0. ]
[ 0. 0. 0. 64. 0. 100. ]
[ 0. 0. 0. 64. 0. 0. ]
[ 0. 80. 51.2 0. 80. 0. ]
[ 64. 0. 0. 64. 0. 100. ]
[ 0. 0. 0. 0. 0. 0. ]]
------------------------------------------------
训练的次数为: 100
[[ 0. 0. 0. 0. 80. 0. ]
[ 0. 0. 0. 64. 0. 100. ]
[ 0. 0. 0. 64. 0. 0. ]
[ 0. 80. 51.2 0. 80. 0. ]
[ 64. 0. 0. 64. 0. 100. ]
[ 0. 0. 0. 0. 0. 0. ]]
参考资料：（http://mnemstudio.org/path-finding-q-learning-tutorial.htm）
（https://morvanzhou.github.io/tutorials/machine-learning/）
（https://blog.csdn.net/aliceyangxi1987/article/details/73327378）
Finally~好好学习鸭！
