概念

前置知识：RL基础

• Q learning是属于TD算法更新的简单的价值学习方法，通过对每个状态s和动作a分配Q值建立Q表，通过动作-反馈来不断更新Q表，最终通过查表选择决策。
  步骤：

1. 0值初始化Q表，列为s，行为a
2. 根据s1选择Q1最大的a1，可附加随机性，如ε-greedy，当ε=0.9，代表有10%的概率会随机选择a（失去理性）
3. 执行a1进入s2，环境奖励R
4. 假想在s2下执行所有a，找哪个a能得到最大的Q，记为max Q 对应动作是a2，则δ = R + γ·max Q - Q1 = 实际 - 估计，γ是折扣因子。用δ更新↔用平方损失。
5. 更新Q1=Q1+α·δ，α即学习率
   注意第4步，只是假想了执行a2，以假想的最大Q来更新Q1，所以Q-learning是off-policy离线学习。

• Q learning和SARSA类似，区别仅在于第4步。
  Q learning没有实际执行a2，就以a2对应的max Q 来更新Q1，比较大胆、贪婪，因为最终解路径未必会采取a2。
  SARSA则在进入s2后执行了a2，以Q(s2,a2)代替前者的“max Q”，以此来更新Q1。SARSA是on-policy在线学习，走到哪就以哪的实际Q值来更新，是更符合直觉的做法，但也比较谨慎、保守（有时低效）。

简单二维迷宫的例子

Q learning代码
由于涉及二维动态展示所以调用了tkinter包，如果不想学tkinter可以只看main的update()方法，和上述步骤是一样的。RL_brain里的choose_action和learn方法是具体的更新，可以重点关注一下。

#每个episode的steps：
        while True:
            # fresh env
            env.render()

            # RL choose action based on observation
            action = RL.choose_action(str(observation))

            # RL take action and get next observation and reward
            observation_, reward, done = env.step(action)

            # RL learn from this transition
            RL.learn(str(observation), action, reward, str(observation_))

            # 将新观测赋值到观测变量
            observation = observation_

            # break while loop when end of this episode
            if done:
                break

    def choose_action(self, observation):
        self.check_state_exist(observation) # 如果是新状态就登记到Q表，赋0

        if np.random.uniform() < self.epsilon: # 按Q值选择最佳action
            state_action = self.q_table.loc[observation, :] # 找到当前state对应的所有action
            action = np.random.choice(state_action[state_action == np.max(state_action)].index) # 为避免Q的最大值相同时自动选第一个a，随机选择最大Q对应的a
        else:           # 随机选择action
            action = np.random.choice(self.actions)
        return action

    def learn(self, s, a, r, s_): # 更新Q表 
        self.check_state_exist(s_)
        q_predict = self.q_table.loc[s, a] # Q的估计值
        if s_ != 'terminal':
            q_target = r + self.gamma * self.q_table.loc[s_, :].max()  # Q的实际值
        else:
            q_target = r  # 到达终点，没有未来reward了
        self.q_table.loc[s, a] += self.lr * (q_target - q_predict)  # TD算法更新Q值

SARSA代码的区别：

1. learn方法需要下一步动作a_，Q的实际值计算：q_target = r + self.gamma * self.q_table.loc[s_, a_]；
2. 每个step先前向多做一次动作再更新Q值，或者说做完动作后更新的是往前数第二个状态Q值，而不是前一个状态的Q值。

SARSA(λ)

主要是多了一个eligibility_trace，可记录每回合的轨迹，对终点越近的节点记忆越强，每走一步对轨迹的记忆都会衰减，保存率就是λ，通常取如0.9这样的值。
TD算法的区别：eligibility_trace和Q表同型，Q表的更新不再是某个Q(s, a) += lr（学习率）· δ，而是整个Q表 += lr · δ · eligibility_trace
SARSA(λ)的目的主要是加强终点附近的权重，所以加速TD算法的收敛（但也因此更容易错失最佳路径）。

总结

以上三种方法都受限于Q表，因为实际问题往往有无限多的s，所以引入NN是自然的想法，一个NN即可将无数的(s, a)组合转化为相应的Q值，或将无数的s转化为有限的(Q, a)组合，这种用NN代替Q表的新方法就是DQN。