Sarsa
Sarsa原理
Sarsa的决策过程和Q-Learning类似，都是在Q表中挑选值较大的动作值施加在环境中来换取奖惩。不同之处在于更新方式。
如下图所示，在状态s采取行动a，到达下一个状态s'时，Q-Learning算法会根据Q(s')的最大值，假设自己走能使maxQ(s')这条路，来更新刚刚走过的Q(s,a)。此时在s‘的agent还没做出任何决策。
与Q-Learning不同，Sarsa会在状态s’做出实际的行为（该行为并不一定能使Q(s')最大化），并根据实际做出行为的Q值来更新刚刚走过的Q(s,a)。
Sarsa是一种on-policy在线学习算法，Q-learning是一种off-policy离线学习算法。
Q-Learning更新状态s时只看到maxQ(s')，忽视掉该行为可能带来的惩罚，因此它是一个大胆、贪婪的策略。Sarsa算法在接近收敛时，允许对探索性的行动进行可能的惩罚（Q-Learning会直接忽略）这使得Sarsa算法更加保守。
Sarsa算法更新
还是agent走迷宫的例子
与Q-Learning的不同在于
- 两个choose_action，第一个在循环外面（真的做出了行为并刷新了环境
- RL.learn(str(observation), action, reward, str(observation_), action_)这里多了一个action_
def update():
for episode in range(100):
# 初始化环境
observation = env.reset()
# Sarsa 根据 state 观测选择行为
action = RL.choose_action(str(observation))
while True:
# 刷新环境
env.render()
# 在环境中采取行为, 获得下一个 state_ (obervation_), reward, 和是否终止
observation_, reward, done = env.step(action)
# 根据下一个 state (obervation_) 选取下一个 action_
action_ = RL.choose_action(str(observation_))
# 从 (s, a, r, s, a) 中学习, 更新 Q_tabel 的参数 ==> Sarsa
RL.learn(str(observation), action, reward, str(observation_), action_)
# 将下一个当成下一步的 state (observation) and action
observation = observation_
action = action_
# 终止时跳出循环
if done:
break
# 大循环完毕
print('game over')
env.destroy()
if __name__ == "__main__":
env = Maze()
RL = SarsaTable(actions=list(range(env.n_actions)))
env.after(100, update)
env.mainloop()
Sarsa思维决策
定义一个RL父类
import numpy as np
import pandas as pd
class RL(object):
def __init__(self, action_space, learning_rate=0.01, reward_decay=0.9, e_greedy=0.9):
... # 和 QLearningTable 中的代码一样
def check_state_exist(self, state):
... # 和 QLearningTable 中的代码一样
def choose_action(self, observation):
... # 和 QLearningTable 中的代码一样
def learn(self, *args):
pass # 每种的都有点不同, 所以用 pass
定义Q-Learning子类
class QLearningTable(RL): # 继承了父类 RL
def __init__(self, actions, learning_rate=0.01, reward_decay=0.9, e_greedy=0.9):
super(QLearningTable, self).__init__(actions, learning_rate, reward_decay, e_greedy) # 表示继承关系
def learn(self, s, a, r, s_): # learn 的方法在每种类型中有不一样, 需重新定义
self.check_state_exist(s_)
q_predict = self.q_table.loc[s, a]
if s_ != 'terminal':
q_target = r + self.gamma * self.q_table.loc[s_, :].max()
else:
q_target = r
self.q_table.loc[s, a] += self.lr * (q_target - q_predict)
定义Sarsa子类
class SarsaTable(RL): # 继承 RL class
def __init__(self, actions, learning_rate=0.01, reward_decay=0.9, e_greedy=0.9):
super(SarsaTable, self).__init__(actions, learning_rate, reward_decay, e_greedy) # 表示继承关系
def learn(self, s, a, r, s_, a_):
self.check_state_exist(s_)
q_predict = self.q_table.loc[s, a]
if s_ != 'terminal':
q_target = r + self.gamma * self.q_table.loc[s_, a_] # q_target 基于选好的 a_ 而不是 Q(s_) 的最大值
else:
q_target = r # 如果 s_ 是终止符
self.q_table.loc[s, a] += self.lr * (q_target - q_predict) # 更新 q_table
Sarsa(lambda)
Sarsa(lambda)是一种Sarsa的提速算法
上述Sarsa算法是单步更新法，即每次获取到reward，只更新获取到reward的前一步
Sarsa-lambda就是更新获取到reward的前lambda步
lambda就是一个衰变值，取值在0-1之间。当lambda取0，就变成了Sarsa的单步更新，当lambda取 1，就变成了回合更新。lambda取值越大，离宝藏越近的步更新力度越大。
Sarsa(lambda)例子
还是那个走迷宫的例子
SarsaLambdaTable在算法更新迭代的部分，和SarsaTable 是一样的，思维决策部分有所不同，如下图所示：
从上图可以看出，和Sarsa相比，Sarsa(lambda)算法中多了一个矩阵E (eligibility trace)，它是用来保存在路径中所经历的每一步，因此在每次更新时也会对之前经历的步进行更新
"""
This part of code is the Q learning brain, which is a brain of the agent.
All decisions are made in here.
View more on my tutorial page: https://morvanzhou.github.io/tutorials/
"""
import numpy as np
import pandas as pd
# 预设值里增加了trace_decay=0.9,也就是lambda的值
class SarsaLambdaTable(RL): # 继承RL父类
def __init__(self, actions, learning_rate=0.01, reward_decay=0.9, e_greedy=0.9, trace_decay=0.9):
super(SarsaLambdaTable, self).__init__(actions, learning_rate, reward_decay, e_greedy)
# backward view, eligibility trace.
self.lambda_ = trace_decay
self.eligibility_trace = self.q_table.copy()
def check_state_exist(self, state):
if state not in self.q_table.index:
# append new state to q table
to_be_append = pd.Series(
[0] * len(self.actions),
index=self.q_table.columns,
name=state,
)
self.q_table = self.q_table.append(to_be_append)
# also update eligibility trace
self.eligibility_trace = self.eligibility_trace.append(to_be_append)
def learn(self, s, a, r, s_, a_):
self.check_state_exist(s_)
q_predict = self.q_table.loc[s, a]
if s_ != 'terminal':
q_target = r + self.gamma * self.q_table.loc[s_, a_] # next state is not terminal
else:
q_target = r # next state is terminal
error = q_target - q_predict
# increase trace amount for visited state-action pair
# Method 1:
# self.eligibility_trace.loc[s, a] += 1
# Method 2:
self.eligibility_trace.loc[s, :] *= 0
self.eligibility_trace.loc[s, a] = 1
# Q update
self.q_table += self.lr * error * self.eligibility_trace
# decay eligibility trace after update
self.eligibility_trace *= self.gamma*self.lambda_
除了图中和上面代码这种更新方式, 还有一种会更加有效率. 我们可以将上面的这一步替换成下面这样：
# 上面代码中的方式:
self.eligibility_trace.ix[s, a] += 1
# 更有效的方式:
self.eligibility_trace.ix[s, :] *= 0
self.eligibility_trace.ix[s, a] = 1
他们的不同之处可以用这张图来概括：
这是针对于一个 state-action 值按经历次数的变化，最上面是经历 state-action 的时间点，第二张图是使用这种方式所带来的 “不可或缺性值”：
self.eligibility_trace.ix[s, a] += 1
下面图是使用这种方法带来的 “不可或缺性值”：
self.eligibility_trace.ix[s, :] *= 0; self.eligibility_trace.ix[s, a] = 1
最后不要忘了，eligibility trace只是记录每个回合的每一步，新回合(episode)开始的时候需要将 Trace 清零
for episode in range(100):
...
# 新回合, 清零
RL.eligibility_trace *= 0
while True: # 开始回
