序贯决策是时间序列中，多个阶段需要连续决策，决策是分前后顺序的，前一步的选择直接影响后一步的选择，就像走迷宫一样，走错一步，可能后续就到了死胡同。上一篇笔记已经了解了一些基本概念。这一篇举一个实例。
QLearning算法是一个经典算法，是一种强化学习中的异策略算法。所谓异就是action的策略使用贪婪策略，即选择的结果就是行为值函数最大的action，或者说最优的action。而状态行为（state_action）的选择策略是epsilon贪婪策略，这是在贪婪策略中加入了一个修正epsilon，相当于增加了一个探索利用。这导致每次选择的action不一定都是最优的。不是最优的action也有很小的概率被选择，但是最优的action被选择的概率仍然是最大的。而不是最优的action即使被选择了，也不会影响学习的结果，因为在迭代训练的过程中，不是最优的action的回报并不是最大的。
我们仍然使用上一篇的图。上一篇中，是随机初始化一个位置，每次action选择都是随机的，没有QLearning算法，所以结果可能不是找到金币，而是走到死胡同。这一篇中，加入QLearning算法，使得最终无论起点在哪，蓝点都可以按照最优的路径找到金币。
我们先人工设置一个最优回报（见下图），我们可以人工赋一些初值，也可以把模型迭代的最后结果作为best，因为我们的目的就是将学习的效果进行对比。

在qlearning代码开始的时候，读入人工赋值的回报，记为best，然后每次迭代，计算一次学习结果与best的误差。

register(
    id="GridWorld-v0",
    entry_point="Grid_MDP:GridEnv",
    max_episode_steps=200,
    reward_threshold=100.0,
)
grid = gym.make('GridWorld-v0')
states = grid.env.getStates()  # 获得网格世界的状态空间
actions = grid.env.getAction()  # 获得网格世界的动作空间
gamma = grid.env.getGamma()  # 获得折扣因子
best = dict()  # 储存最优行为值函数

def read_best():
    f = open("best.txt")
    for line in f:
        line = line.strip()
        if len(line) == 0: continue
        eles = line.split(":")
        best[eles[0]] = float(eles[1])

# 计算误差
def compute_error(qfunc):
    sum1 = 0.0
    for key in qfunc:
        error = qfunc[key] - best[key]
        sum1 += error * error
    return sum1

然后就是策略。

#贪婪策略
def greedy(qfunc, state):
    amax = 0
    key = "%d_%s" % (state, actions[0])
    qmax = qfunc[key]
    for i in range(len(actions)):  # 扫描动作空间得到最大动作值函数
        key = "%d_%s" % (state, actions[i])
        q = qfunc[key]
        if qmax < q:
            qmax = q
            amax = i
    return actions[amax]
#epsilon贪婪策略
def epsilon_greedy(qfunc, state, epsilon):
    amax = 0
    key = "%d_%s" % (state, actions[0])
    qmax = qfunc[key]
    for i in range(len(actions)):  # 扫描动作空间得到最大动作值函数
        key = "%d_%s" % (state, actions[i])
        q = qfunc[key]
        if qmax < q:
            qmax = q
            amax = i
            
    # 概率部分
    pro = [0.0 for i in range(len(actions))]
    pro[amax] += 1 - epsilon
    for i in range(len(actions)):
        pro[i] += epsilon / len(actions)

    ##选择动作
    r = random.random()
    s = 0.0
    for i in range(len(actions)):
        s += pro[i]
        if s >= r: return actions[i] # r很小，则可能选择的不是最优
    return actions[len(actions) - 1]

然后，主程序开始的时候，我们设置500次迭代，首先看看，学习的结果。


左侧是学习结果，右侧是best，可以看到，结果很接近。最后，我们连续启动多次运行，看一下运行结果。仍然使用上一篇的GridEnv，下边是主程序入口。

import sys
import gym
from qlearning import *
import time
from gym import wrappers


# main函数
if __name__ == "__main__":

    sleeptime = 1
    terminate_states = grid.env.getTerminate_states()
    # 读入最优值函数
    read_best()
    # 训练
    qfunc = qlearning(num_iter1=500, alpha=0.2, epsilon=0.2)
    time.sleep(sleeptime)
    # 学到的策略为：
    print("the learned policy is:")
    for i in range(len(states)):
        if states[i] in terminate_states:
            print("the state %d is terminate_states" % (states[i]))
        else:
            print("the policy of state %d is (%s)" % (states[i], greedy(qfunc, states[i])))
    # 设置系统初始状态
    s0 = 1
    grid.env.setAction(s0)
    # 对训练好的策略进行测试
    # 随机初始化，寻找金币的路径
    for i in range(7):
        # 随机初始化
        s0 = grid.reset()
        grid.render()
        time.sleep(sleeptime)
        t = False
        count = 0
        # 判断随机状态是否在终止状态中
        if s0 in terminate_states:
            print("reach the terminate state %d" % (s0))
        else:
            while False == t and count < 100:
                a1 = greedy(qfunc, s0)
                print(s0, a1)
                grid.render()
                time.sleep(sleeptime)

                # 与环境进行一次交互，从环境中得到新的状态及回报
                s1, r, t, i = grid.step(a1)
                if True == t:
                    # 打印终止状态
                    print(s1)
                    grid.render()
                    time.sleep(sleeptime)
                    print("reach the terminate state %d" % (s1))
                # s1处的最大动作
                s0 = s1
                count += 1

把上一篇的GridEnv最后改成下面这样，其他不变。

        if self.state is None: return None
        self.robotrans.set_translation(self.x[self.state - 1], self.y[self.state - 1])
        return self.viewer.render(return_rgb_array=mode == 'rgb_array')

下图就是运行结果，无论初始化在哪，都可以最快找到金币。