Q-learning是RL最基础的算法，于1989年由Watkins被提出来，与同样经典的SARSA算法非常类似。
按木盏习惯，本文依旧不会大量堆公式，尽量以易理解的方式来表达Q-Learning。

1. 查表操作

“查表操作”这四个字足以概括Q-Learning的精髓。大家都知道强化学习的用处就是“做决策”，翻译成计算机科学语言就是：在当前的state下选择对应的action。
这一步完全可以用查表法来操作：

上表所示就是一张Q值表，当机器处于某个state时，它会查表来告诉自己该做什么action。它会选择Q值最大的那个action。比如AlphaGo在写围棋的时候，脑子里也有这么个东西，指导自己下一步棋该落在哪里。

2.马尔可夫域

Q-Learning是有使用范围的。首先，你的使用场景必须能被马尔可夫域建模。
满足：1. 机器所处的状态必须有限，这就是“状态机收敛”；
2. 机器所处的状态是连通的，不然机器可能永远困在子状态机里；
概括一下就是：Q-Learning本质上也是一个马尔可夫模型，是马尔科夫链的高级用法。
本科时学过两门课，数字电路和计算机网络。数字电路中时序逻辑电路的状态机就是马尔科夫链的方法，而查表的套路就和计算机网络中路由表的套路如出一辙。所以，知识还是互通的~

3. R-table

R表是reward table，即奖赏表。查寻R表给与机器足够的奖励，让机器知道从哪个方向努力。R表具有与Q表一样的结构：column由action构成，row由state构成。
R表就是我们事先要告诉机器的，可以理解为对目前环境的抽象表达。

4. 一个Q-Learning实例

引用自：http://mnemstudio.org/path-finding-q-learning-tutorial.htm

这是一个机器人出房间的例子。我们可以看到，只有到5号区域才算出门。主要信息有2个：你现处于哪个房间(即state)以及你下一步去哪个房间(即action)。
用马尔可夫模型来建模：

圆圈表示你现在所出的state，箭头表示你可以做的action。

我们把机器人放在2号房间，等它到5号区域才算完成任务。所以，我们可以根据场地建立如下模型：

只有到5号，我们才给100块作为奖赏，其他的情况都不给钱。这就是我们的实际环境，我们只需要告诉机器到哪一步才能尝到甜头，剩下的路径，需要机器自己一边学习一边规划。
还有一些不可能的case，比如，0号房间不能到2号房间，它的下一步action只能是4号房间。我们的R表会把奖赏值设为-1。
所以，这里的R表就可以是：

对照着上面的图看，应该很容易理解吧。R表就是对目前环境的抽象描述。
好，现在来开始Q-Learning：
第一步，初始化Q表，可以设置为全0：

Q表在机器学习的过程中会不断更新，而更新的法则只有一行公式：（读懂这行公式，你就完全掌握Q-Learning了）

$s$表示state,a表示action。Q(s,a)即访问Q 表的对应位置，R(s,a)即访问R表的对应位置。

表示选取下一个状态中，最大Q值的那个action，并且获取它的Q值。
γ你可以理解成学习率啦，设置0.8就可以了。
以这个更新法则，在不停地迭代之后，我们可以得到一张最终的Q表：

到这一步，Q-Learning就完成咯~
附个python代码：python2/3

import numpy as np
import random

r = np.array([[-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]])

q = np.zeros([6,6],dtype=np.float32)

gamma = 0.8

step = 0
while step < 1000:
    state = random.randint(0,5)
    if step%100 ==0:
        print('step %d:' % step)
        print(q)
    if state != 5:
        next_state_list=[]
        for i in range(6):
            if r[state,i] != -1:
                next_state_list.append(i)
        next_state = next_state_list[random.randint(0,len(next_state_list)-1)]
        qval = r[state,next_state] + gamma * max(q[next_state])
        q[state,next_state] = qval
        step += 1


for i in range(10):
    print("\nvalidation epoch: {}".format(i + 1))
    state = random.randint(0, 5)
    print('robot state: {}'.format(state))
    count = 0
    while state != 5:
        if count > 20:
            print('fail')
            break
        q_max = q[state].max()

        q_max_action = []
        for action in range(6):
            if q[state, action] == q_max:
                q_max_action.append(action)

        next_state = q_max_action[random.randint(0, len(q_max_action) - 1)]
        print("the robot goes to " + str(next_state) + '.')
        state = next_state
        count += 1