表格型方法
对于免模型的强化学习方法，agent多次尝试与environmet交互之后，就能对其不同状态做出判断，用状态动作价值来表达在某个状态下某个动作的好坏。如果Q表格是一张已经训练好的表格，这张表格就像是一本生活手册。通过查看这本手册，我们就知道在熊发怒的时候，装死的价值会高一点；在熊离开的时候，我们 偷偷逃跑会比较容易获救。这张表格里面 Q 函数的意义就是我们选择了某个动作后，最后能不能成功，就 需要我们去计算在某个状态下选择某个动作，后续能够获得多少总奖励。如果可以预估未来的总奖励的大 小，我们就知道在当前的状态下选择哪个动作价值更高。我们选择某个动作是因为这样未来可以获得的价 值会更高。所以强化学习的目标导向性很强，环境给出的奖励是非常重要的反馈，它根据环境的奖励来做选择。
我们所求的Q表格，它的行数是所有状态的数量，列数是所有可采取的动作数量，在格子世界中大概如图所示：
最开始的时候，Q 表格会全部初始化为 0。智能体会不断和环境交互得到不同的轨迹，当交互的 次数足够多的时候，我们就可以估算出每一个状态下，每个动作的平均总奖励，进而更新 Q 表格。
在强化学习里面，我们可以每走一步更新一次 Q 表格，用下一个状态的 Q 值来更新当前状态的 Q 值，这 种单步更新的方法被称为时序差分方法。
免模型方法
蒙特卡洛
蒙特卡洛方法是基于采样的方法，就是把多次采样值的均值作为该随机变量的期望。
给定策略$\pi$，我们让我们让智能体与环境进行交互，可以得到很多轨迹。 每个轨迹都有对应的回报：
$$
G_t=r_{t+1}+\gamma r_{t+2}+\gamma^2r_{t+3}+…
$$
我们求出从状态s出发所有轨迹的回报的平均值，将其作为一个策略s状态的价值：$V_\pi(s)$
假设现在有样本$x_1,x_2,…,x_t$,我们可以把均值转化成均值增量的形式：
若在每个回合中，如果时间t时状态s被访问了，那么：
- 状态s 的访问数$N(s)$增加1，$N(s) \leftarrow N(s)+1$
- 状态s的总回报$S(s)$增加$G_t$,$S(s)\leftarrow S(s)+G_t$
状态s的价值可以通过回报的平均来估计，即$V(s)=S(s)/N(s)$
那将均值增量应用到蒙特卡洛方法中：
时序差分
比如我们需要使用模型估计从纽约到亚特兰大的时间，模型初始时估计值为1000分钟
而我们真实的时间为860分钟，传统的BP算法会计算真实时间与估计时间的loss，然后求导进行参数更新。
但是若我们没有到亚特兰大，而是在中途有事耽误了呢？传统的BP算法就无法计算了，因为我们没有y label。
比如我们花了300分钟到了华盛顿之后就不走了，TD算法会给出华盛顿到亚特兰大的时间估计，然后：
$$
loss=\frac{1}{2}(T_{NYC2At}^e-(T_{NYC2DC}^a+T_{DC2At}^e))^2
$$
$$
=\frac{1}{2}(T_{NYC2DC}^e-T_{NYC2DC}^a)^2
$$
其中上标表示：e-估计值，a-实际值，下标表示不同城市
$$
TD target=T_{NYC2DC}^a+T_{DC2At}^e
$$
TDtaeget肯定比模型最开始的估计值要好，因为其中有一部分是真实值。
$$
Q(s_t,a_t;w)\approx R_t^a+\gamma Q(s_{t+1},a_{t+1};w)
$$
对比一下，也是一个真实值加上一个预测值！左边为模型预测值，右边为TDtarget。上述公式又是哪来的呢？
$$
\begin{aligned}
G_t&=R_t+\gamma R_{t+1}+\gamma^2R_{t+2}+…\\
&=R_t+\gamma(R_{t+1}+\gamma R_{t+2}+…)\\
&=R_t+\gamma G_{t+1}
\end{aligned}
$$
那么用估计得到的回报$r_{t+1}+\gamma V(s_{t+1})$更新上一时刻的值$V(s_t)$:
$$
V(s_t)\leftarrow V(s_t)+\alpha(r_{t+1}+\gamma V(s_{t+1})-V(s_t))
$$
对比一下蒙特卡洛方法和时序差分方法。在蒙特卡洛方法里面，$G_{i,t}$ 是实际得到的值（可以看成 目标），因为它已经把一条轨迹跑完了，可以算出每个状态实际的回报。时序差分不等轨迹结束，往前走 一步，就可以更新价值函数.
进一步比较时序差分方法和蒙特卡洛方法:
- 时序差分方法可以在线学习（online learning），每走一步就可以更新，效率高。蒙特卡洛方法必 须等游戏结束时才可以学习
- 时序差分方法可以从不完整序列上进行学习。蒙特卡洛方法只能从完整的序列上进行学习
- 时序差分方法可以在连续的环境下（没有终止）进行学习。蒙特卡洛方法只能在有终止的情况下 学习。
- 时序差分方法利用了马尔可夫性质，在马尔可夫环境下有更高的学习效率。蒙特卡洛方法没有假设环境具有马尔可夫性质，利用采样的价值来估计某个状态的价值，在不是马尔可夫的环境下更加有效.
我们可以把时序差分方法进行进一步的推广。之前是只往前走一步，即 TD(0)。我 们可以调整步数（step），变成 n 步时序差分（n-step TD）。比如 TD(2)，即往前走两步，利用两步得到 的回报，使用自举来更新状态的价值。这样我们就可以通过步数来调整算法需要的实际奖励
如果时序差分方法需要更广度的更新，就变成了动态规划方法（因为动态规划方法 是把所有状态都考虑进去来进行更新）。如果时序差分方法需要更深度的更新，就变成了蒙特卡洛方法
Sarsa算法：同策略时序差分控制
时序差法方法是给定一个策略，然后我们去估计他的价值函数，Sarsa算法很简单，他将原本时序差分方法更新V的过程，变成了更新Q的过程：
$$
Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha[r_{t+1}+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)]
$$
Sarsa直接估计Q表格，得到Q表格后，就可以更新策略。
该算法由于需要知道当前的状态、当前的动作、奖励、下一步状态、下一步动作，即$(s_t,a_t,R_t,s_{t+1},a_{t+1})$,所以叫做Sarsa算法。
上述算法每执行一个动作就更新一次价值和策略，所以也叫做单步Sarsa算法，那很明显，也有n步Sarsa算法：
对于Sarsa，在t时刻的价值为：
$$
Q_t=r_{t+1}+\gamma Q(s_{t+1},a_{t+1})
$$
对于n步Sarsa，其n步回报为：
$$
Q_t^n=r_{t+1}+\gamma r_{t+2}+…\gamma^{n-1}r_{t+n}+\gamma ^nQ(s_{t+n},a_{t+n})
$$
加上资格迹衰减参数得Sarsa$(\lambda)$的Q回报：
$$
Q_t^\lambda=(1-\lambda)\sum_{n=1}^\infty\lambda^{n-1}Q_t^n
$$
n步Sarsa更新策略为：
$$
Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha(Q_t^\lambda-Q(s_t,a_t))
$$
Q-learning:异策略时序差分控制
Sarsa 是一种同策略（on-policy）算法，它优化的是它实际执行的策略，它直接用下一步会执行的动作去优化 Q 表格。同策略在学习的过程中，只存在一种策略，它用一种策略去做动作的选取，也用一种策略去做优化。所以 Sarsa 知道它下一步的动作有可能会跑到悬崖那边去，它就会在优化自己的策略的时 候，尽可能离悬崖远一点。这样子就会保证，它下一步哪怕是有随机动作，它也还是在安全区域内。
Q 学习是一种异策略（off-policy）算法。如图 3.31 所示，异策略在学习的过程中，有两种不同的策 略：目标策略（target policy）和行为策略（behavior policy）。目标策略是我们需要去学习的策略，一 般用 π 来表示。目标策略就像是在后方指挥战术的一个军师，它可以根据自己的经验来学习最优的策略， 不需要去和环境交互。行为策略是探索环境的策略，一般用 µ 来表示。行为策略可以大胆地去探索到所有 可能的轨迹，采集轨迹，采集数据，然后把采集到的数据“喂”给目标策略学习。而且“喂”给目标策略的数据中并不需要 $a_{t+1}$ ，而 Sarsa 是要有$a_{t+1}$ 的。行为策略像是一个战士，可以在环境里面探索所有的 动作、轨迹和经验，然后把这些经验交给目标策略去学习。比如目标策略优化的时候，Q 学习不会管我们下一步去往哪里探索，它只选取奖励最大的策略。
Q 学习有两种策略：行为策略和目标策略。目标策略 π 直接在 Q 表格上使用贪心策略，取它下一步能得到的所有状态，即
$$
\pi(s_{t+1})=\arg\max_{a’} Q(S_{t+1},a’)
$$
行为策略 µ 可以是一个随机的策略，但我们采取 ε-贪心策略，让行为策略不至于是完全随机的，它是基 于 Q 表格逐渐改进的.
那么Q-learning的更新公式为：
$$
Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha[r_{t+1}+\gamma\max_aQ(s_{t+1},a)-Q(s_t,a_t)]
$$
Sarsa 在更新 Q 表格的时候，它用到的是 A′ 。我们要获取下一个 Q 值的时候，A′ 是下一个步骤一定会执行的动作，这个动作有可能是 ε-贪心方法采样出来的动作，也有 可能是最大化 Q 值对应的动作，也有可能是随机动作，但这是它实际执行的动作。但是 Q 学习在更新 Q 表格的时候，它用到的是 Q 值 Q(S ′ , a) 对应的动作，它不一定是下一个步骤会执行的实际的动作，因为我们下一个实际会执行的动作可能会探索。Q 学习默认的下一个动作不是通过行为策略来选取的,Q 学习直接看 Q 表格，取它的最大化的值，它是默认 A′ 为最佳策略选取的动作，所以 Q 学习在学习的时候，不需要传入 A′，即$a_{t+1}$的值。
Q-learning和Sarsa算法分别实现CliffWalking
我们首先简单介绍 CliffWalking-v0 环境，该环境中文名为悬崖寻路（cliffwalking），是一个迷宫类问 题。如图 3.36 所示，在一个 4 × 12 的网格中，智能体以网格的左下角位置为起点，以网格的右下角位置 为终点，目标是移动智能体到达终点位置，智能体每次可以在上、下、左、右这 4 个方向中移动一步，每 移动一步会得到 −1 单位的奖励。
起终点之间是一段悬崖，即编号为 37 46 的网格，智能体移动过程中会有如下的限制：
- 智能体不能移出网格，如果智能体想执行某个动作移出网格，那么这一步智能体不会移动，但是 这个操作依然会得到 −1 单位的奖励
- 如果智能体“掉入悬崖”，会立即回到起点位置，并得到 −100 单位的奖励
- 当智能体移动到终点时，该回合结束，该回合总奖励为各步奖励之和。
from argparse import Action
from time import sleep
import gym
import math
import numpy as np
import turtle
import argparse
parse=argparse.ArgumentParser()
parse.add_argument('-lr',default=0.1)
parse.add_argument('-gamma',default=0.9)
parse.add_argument('-epsilon_start',default=0.1)
parse.add_argument('-epsilon_end',default=0.01)
parse.add_argument('-epsilon_decay',default=20)
parse.add_argument('-train_eps',default=1000)
args=parse.parse_args()
class CliffWalkingWapper(gym.Wrapper):
def __init__(self, env):
gym.Wrapper.__init__(self, env)
self.t = None
self.unit = 50
self.max_x = 12
self.max_y = 4
def draw_x_line(self, y, x0, x1, color='gray'):
assert x1 > x0
self.t.color(color)
self.t.setheading(0)
self.t.up()
self.t.goto(x0, y)
self.t.down()
self.t.forward(x1 - x0)
def draw_y_line(self, x, y0, y1, color='gray'):
assert y1 > y0
self.t.color(color)
self.t.setheading(90)
self.t.up()
self.t.goto(x, y0)
self.t.down()
self.t.forward(y1 - y0)
def draw_box(self, x, y, fillcolor='', line_color='gray'):
self.t.up()
self.t.goto(x * self.unit, y * self.unit)
self.t.color(line_color)
self.t.fillcolor(fillcolor)
self.t.setheading(90)
self.t.down()
self.t.begin_fill()
for i in range(4):
self.t.forward(self.unit)
self.t.right(90)
self.t.end_fill()
def move_player(self, x, y):
self.t.up()
self.t.setheading(90)
self.t.fillcolor('red')
self.t.goto((x + 0.5) * self.unit, (y + 0.5) * self.unit)
def render(self):
if self.t == None:
self.t = turtle.Turtle()
self.wn = turtle.Screen()
self.wn.setup(self.unit * self.max_x + 100,
self.unit * self.max_y + 100)
self.wn.setworldcoordinates(0, 0, self.unit * self.max_x,
self.unit * self.max_y)
self.t.shape('circle')
self.t.width(2)
self.t.speed(0)
self.t.color('gray')
for _ in range(2):
self.t.forward(self.max_x * self.unit)
self.t.left(90)
self.t.forward(self.max_y * self.unit)
self.t.left(90)
for i in range(1, self.max_y):
self.draw_x_line(
y=i * self.unit, x0=0, x1=self.max_x * self.unit)
for i in range(1, self.max_x):
self.draw_y_line(
x=i * self.unit, y0=0, y1=self.max_y * self.unit)
for i in range(1, self.max_x - 1):
self.draw_box(i, 0, 'black')
self.draw_box(self.max_x - 1, 0, 'yellow')
self.t.shape('turtle')
x_pos = self.s % self.max_x
y_pos = self.max_y - 1 - int(self.s / self.max_x)
self.move_player(x_pos, y_pos)
class Qlearning():
def __init__(self,n_states,n_actions,args) -> None:
self.Q_table=np.zeros((n_states,n_actions))
self.epsilon_start=args.epsilon_start
self.epsilon_end=args.epsilon_end
self.epsilon_decay=args.epsilon_decay
self.choose_action_dim=np.array([0,1,2,3])
self.lr=args.lr
self.gamma=args.gamma
self.sample_count=0
def choose_action(self,state):
self.sample_count+=1
self.epsilon=self.epsilon_end+(self.epsilon_start-self.epsilon_end)*math.exp(-1*self.sample_count/self.epsilon_decay)
if np.random.uniform(0,1)<1-self.epsilon+(self.epsilon/4):
action=np.argmax(self.Q_table[state])
else:
action=np.random.choice(self.choose_action_dim)
return action
def update(self,state,action,reward,next_state,done):
if done:
Q_target=reward
else:
Q_target=reward+self.gamma*np.max(self.Q_table[next_state])
self.Q_table[state][action]+=self.lr*(Q_target-self.Q_table[state][action])
def test_action(self,state):
return np.argmax(self.Q_table[state])
class Sarsa():
def __init__(self,n_states,n_actions,args) -> None:
self.Q_table=np.zeros((n_states,n_actions))
self.epsilon_start=args.epsilon_start
self.epsilon_end=args.epsilon_end
self.epsilon_decay=args.epsilon_decay
self.choose_action_dim=np.array([0,1,2,3])
self.lr=args.lr
self.gamma=args.gamma
self.sample_count=0
def choose_action(self,state):
self.sample_count+=1
self.epsilon=self.epsilon_end+(self.epsilon_start-self.epsilon_end)*math.exp(-1*self.sample_count/self.epsilon_decay)
if np.random.uniform(0,1)<1-self.epsilon+(self.epsilon/4):
action=np.argmax(self.Q_table[state])
else:
action=np.random.choice(self.choose_action_dim)
return action
def update(self,state,action,reward,next_state,done,next_action):
if done:
Q_target=reward
else:
Q_target=reward+self.gamma*(self.Q_table[next_state][next_action])
self.Q_table[state][action]+=self.lr*(Q_target-self.Q_table[state][action])
def test_action(self,state):
return np.argmax(self.Q_table[state])
def play(type):
env=gym.make('CliffWalking-v0')
env=CliffWalkingWapper(env)
n_states=env.observation_space.n
n_actions=env.action_space.n
print('状态数：{}，动作数：{}'.format(n_states,n_actions))
n_reward=[]
env.seed(0)
if type=='Q-learning':
agent=Qlearning(n_states,n_actions,args)
for i in range(args.train_eps):
ep_reward=0
state=env.reset()
step=0
while True:
step+=1
action=agent.choose_action(state)
if i%50==0:
env.render()
sleep(0.1)
next_state,reward,done,_=env.step(action)
agent.update(state,action,reward,next_state,done)
state=next_state
ep_reward+=reward
if done:
n_reward.append(ep_reward)
print('episode:{}:step:{},reward:{}'.format(i,step,ep_reward))
break
print('训练平均奖励：{}'.format(np.mean(n_reward)))
print(agent.Q_table)
step=0
state=env.reset()
test_reward=0
while True:
step+=1
sleep(1)
action=agent.test_action(state)
env.render()
next_state,reward,done,_=env.step(action)
state=next_state
test_reward+=reward
if done:
print('test:step:{},reward:{}'.format(step,test_reward))
break
elif type=='Sarsa':
agent=Sarsa(n_states,n_actions,args)
for i in range(args.train_eps):
ep_reward=0
state=env.reset()
step=0
while True:
step+=1
action=agent.choose_action(state)
if i%100==0:
env.render()
sleep(0.1)
next_state,reward,done,_=env.step(action)
next_action=agent.choose_action(next_state)
agent.update(state,action,reward,next_state,done,next_action)
state=next_state
ep_reward+=reward
if done:
n_reward.append(ep_reward)
print('episode:{}:step:{},reward:{}'.format(i,step,ep_reward))
break
print('训练平均奖励：{}'.format(np.mean(n_reward)))
print(agent.Q_table)
step=0
state=env.reset()
test_reward=0
while True:
step+=1
sleep(0.5)
action=agent.test_action(state)
env.render()
next_state,reward,done,_=env.step(action)
state=next_state
test_reward+=reward
if done:
print('test:step:{},reward:{}'.format(step,test_reward))
break
if __name__ == '__main__':
play('Sarsa')
|
Q-learning 效果：最后一次慢的为测试，之前为训练
Sarsa算法效果：最后一次慢的为测试，之前为训练
