注意将代码和下面公式推导结合起来。还要注意一下q_target和q_predict之间的关系。其实算法的更新是需要使用q_predict来逼近q_target，当两者相等时，算法将停止更新，当传统的qlearning转化为deep Qlearning,也是这样操作的，只是深度qlearning使用一个神经网络来表示q表。

这篇文章将要介绍传统的qlearning算法，使用的是迭代的方法更新q表，更新q表的方法类似于向前推进，而不是使用梯度下降方法，因为这里介绍的不是Deep QLearning方法。

一、算法介绍以及推导

注：这里更新的不是agent，而是一个q表，q表里面记录的是agent在某个状态采取某个的动作的好坏，q表可以起到间接决定agent采取什么决策。q表就类似一个critic，一个评论家，来指导agent。

1.1、$Q(s,a)$是什么？

$Q(s,a)$是状态动作价值函数，是在状态$s$时采取动作$a$之后，可以获得的奖励的期望值。$Q(s,a)$越大表示在agent在看到状态$s$是采取动作$a$比较好。

1.2、q表

q表	a1	a2	a3
s1	q(s1,a1)	q(s1,a2)	q(s1,a3)
s2	q(s2,a1)	q(s2,a2)	q(s2,a3)
s3	q(s3,a1)	q(s3,a2)	q(s3,a3)
s4	q(s4,a1)	q(s4,a2)	q(s4,a3)

q表里面记录的都是状态动作价值函数，前面说到q表可以间接决定agent采取什么样的决策，就是因为q表记录了所有的状态和动作的组合情况，比如agent看到状态$s_2$时，就会在状态$s_2$所在的行选取最大的q值所对应的动作。

1.3、如何根据q表进行决策？

假设下表是我们已经更新完成了的q表

q表	a1	a2	a3
s1	- 1	1	3
s2	2	0	1
s3	1	5	7
s4	5	6	3

Q表指导agent决策的过程：t=1时，agent观测到环境的状态s2，于是查找状态s2所在的行，发现Q(s2,a1)>Q(s2,a3)>Q(s2,a2),因此选择动a1,此时环境发生变化，agent观测到环境的状态s4，接着查找状态s4所在的行，agent发现q(s4,a2)>q(s4,a1)>q(s4,a3)，于是agent采取决策选择动作a2，一直进行下去，直到结束。

1.4、$\epsilon -greedy$选择动作

有上面的决策过程我们可以看到，在给定一个状态s时，会选择q值最大的动作，这样会导致一个问题：因为是随机初始化的，由于选择最大值，可能会使得一些动作无法被选择到，也就是无法更新q值，这样q值就一直是随机初始化的那个值。

$\epsilon -greedy$选择动作的流程如下：agent观测到状态s时，采取动作时会以$1-\epsilon$的概率在Q表里面选择q值最大所对应的动作，以$\epsilon$的概率随机选择动作。
不再使用完全贪婪的算法，而是有一定的动作选择的完全随机性，这样就可以保证在迭代次数足够多的情况下Q表中的所有动作都会被更新到。

1.5、如何更新Q表？

算法开始的时候，我们需要随机初始化q表，那么如何更新q表就是一件非常关键的事情。

参数解释：
更新公式为$$Q(s,a{)}^{new}=Q(s,a{)}^{old}+\alpha [r+\gamma ma{x}_{a^{\prime }}Q(s^{\prime },a^{\prime })-Q(s,a{)}^{old}]\text{\hspace{1em}(1)}$$

1. $\alpha$指学习率，其实也是一个权值，我们将公式1进行改写得到如下的公式$$Q(s,a{)}^{new}=(1-\alpha )Q(s,a{)}^{old}+\alpha [r+\gamma ma{x}_{a^{\prime }}Q(s^{\prime },a^{\prime })]\text{\hspace{1em}(2)}$$
   我们从公式2可以看到，$Q(s,a{)}^{new}$是两部分的凸组合。

2. $\gamma$ 是衰减值

首先我们随机初始化一个Q表，然后任意初始化一个状态$s$，也可以理解为，agent观测到的环境的状态，根据Q表使用$\epsilon -greedy$算法选择状态$s$对应的动作$a$,因为agent做出了一个动作，会从环境中获得一个奖励 $r$，环境发生变化，agent又观测到一个新的状态 $s^{\prime }$，根据Q表在状态 $s^{\prime }$ 所在的行，查询Q表，求得最大值，然后更新按照公式更新Q表。

Question 1：什么时候才会迭代收敛？
答：由公式（1）可以看到当 $r+\gamma ma{x}_{a^{\prime }}Q(s^{\prime },a^{\prime })==Q(s,a{)}^{old}$时，迭代格式收敛，也就是Q表的更新完成。

1.6、TD方法（时间差分更新法）

假设$...,s_t,a_t,r_t,s_{t+1},...$
我们要更新Q值使 $r_t和Q(s_t,a_t{)}^{old}-\gamma ma{x}_{a^{\prime }}Q(s_{t+1},a^{\prime })$越接近越好，这里用了两个相邻时刻的状态价值函数

二、两个个小疑问

1. 等eposide结束之后，进行反向更新
   从公式 $$Q(s,a{)}^{new}=Q(s,a{)}^{old}+\alpha [r+\gamma ma{x}_{a^{\prime }}Q(s^{\prime },a^{\prime })-Q(s,a{)}^{old}]$$ 可以看到，$Q(s,a)$的更新会使用到状态
   $s^{\prime }$的Q值，从而基于TD方法进行更新Q表。但是每次更新我们都利用了下一个时刻的Q值，比如$Q(s^{\prime },a^{\prime })$，假设agent完了一个episode的游戏，得到 τ = { s 1 , a 1 , r 1 , s 2 , a 2 , r 2 , . . . , s T , a T , r T , E N D } \tau =\{s_{1},a_{1},r_{1},s_{2},a_{2},r_{2},...,s_{T},a_{T},r_{T},END\} τ={s1​,a1​,r1​,s2​,a2​,r2​,...,sT​,aT​,rT​,END},假如我们先从后面的状态开始更新，这样前面的状态更新的时候就可以使用已经更新了的后面的状态，也就是反向更新
   不知道这样是否可行，这样有个问题就是：原始的方法每一时间步都可以更新，就是在episode进行的时候更新，换成上面我说的这样的更新方法，还要将状态，动作，价值先存储起来，要等到episode结束才能更新。

2. agent观测一个状态，能不能选择做出多个动作回应这个状态？
   例子：太空入侵者游戏
   
   在这个游戏中，agent可以做出动作有三种：开火（fire）,向右移动（right）,向左移动（left）.
   假设上图为agent观测到的一个状态，但是这是agent同时选择了开火和向右移动的动作。感觉这样也是合理的，只要做出的动作不相互矛盾就可以。比如动作向右移动和向左移动就不能同时发生。

三、代码

import numpy as np
import pandas as pd
import time

np.random.seed(2)  # reproducible


N_STATES = 6   # the length of the 1 dimensional world
ACTIONS = ['left', 'right']     # available actions
EPSILON = 0.9   # greedy police
ALPHA = 0.1     # learning rate
GAMMA = 0.9    # discount factor
MAX_EPISODES = 13   # maximum episodes
FRESH_TIME = 0.3 # fresh time for one move


'''
所构造的q表的大小是：行数是财产的探索者总共所处的位置数，列数就是动作的数量
'''
def build_q_table(n_states, actions):
    table = pd.DataFrame(
        np.zeros((n_states, len(actions))),     # q_table initial values
        columns=actions,    # actions's name
    )
    # print(table)    # show table
    return table


def choose_action(state, q_table):
    # This is how to choose an action
    state_actions = q_table.iloc[state, :] #将现在agent观测到的状态所对应的q值取出来
    if (np.random.uniform() > EPSILON) or ((state_actions == 0).all()):  #当生撑随机数大于EPSILON或者状态state所对应的q值全部为0时，就随机选择状态state所对应的动作
        action_name = np.random.choice(ACTIONS)
    else:   # act greedy
        action_name = state_actions.idxmax()    # 选择状态state所对应的使q值最大的动作
    return action_name


def get_env_feedback(S, A):
    # 选择动作之后，还要根据现在的状态和动作获得下一个状态，并且返回奖励，这个奖励是环境给出的，用来评价当前动作的好坏。
    #这里设置的是，只有在获得宝藏是才给奖励，没有获得奖励时，无论是向左移动还是向右移动，给出的即时奖励都是0.
    if A == 'right':    # move right
        if S == N_STATES - 2:   # terminate
            S_ = 'terminal'
            R = 1
        else:
            S_ = S + 1
            R = 0
    else:   # move left
        R = 0
        if S == 0:
            S_ = S  # reach the wall
        else:
            S_ = S - 1
    return S_, R


def update_env(S, episode, step_counter):
    # 更新环境的函数，比如向右移动之后，o表示的agent就距离宝藏进了一步，将agent随处的位置实时打印出来
    env_list = ['-']*(N_STATES-1) + ['T']   # '---------T' our environment
    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 rl():
    # 开始更新q表
    q_table = build_q_table(N_STATES, ACTIONS)#随机初始化一下q表
    for episode in range(MAX_EPISODES):
        step_counter = 0#记录走了多少步
        S = 0#每个episode开始时都将agent初始化在最开始的地方
        is_terminated = False
        update_env(S, episode, step_counter)#打印的就是o-----T
        while not is_terminated:#判断episode是否结束

            A = choose_action(S, q_table)#agent根据当前的状态选择动作
            S_, R = get_env_feedback(S, A)  # 上一步已经获得了s对应的动作a，接着我们要获得下一个时间步的状态
            q_predict = q_table.loc[S, A]
            if S_ != 'terminal':#要判断一下，下一个时间步的是不是已经取得宝藏了，如果不是，可以按照公式进行更新
                q_target = R + GAMMA * q_table.iloc[S_, :].max()   # next state is not terminal
            else:#如果已经得到了宝藏，得到的下一个状态不在q表中，q_target的计算也不同。
                q_target = R     # next state is terminal
                is_terminated = True    # terminate this episode

            q_table.loc[S, A] += ALPHA * (q_target - q_predict)  # update
            S = S_  # move to next state

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


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

可以参看下面的链接
莫烦python