时序差分简介
时序差分(Temporal Difference,TD),也有资料称其为时间差分。
我们先通过一个通俗易懂的例子来讨论时序差分。
现在,我们开车从"上海"去"南昌",然后我们打开导航软件,预估时间是8 8 8 个小时,在这个过程中,存在一个神经网络模型Q ( s , d ; ω ) Q(s,d;\omega) Q ( s , d ; ω ) ,其中s s s 是状态,在这里就是"上海",d d d 是动作,在这里就是"去南昌",ω \omega ω 就是模型的参数。神经网络模型Q ( s , d ; ω ) Q(s,d;\omega) Q ( s , d ; ω ) 的输出就是模型估计的值,在这里q = Q ( s , d ; ω ) = 8 q = Q(s,d;\omega) = 8 q = Q ( s , d ; ω ) = 8 。然后我们真实的去开了一次,这时候就有了一个真实值,比如y = 7 y=7 y = 7 。
所以,其损失函数是:
L ( ω ) = 1 2 ( q − y ) 2 L(\omega) = \frac{1}{2}(q - y)^2
L ( ω ) = 2 1 ( q − y ) 2
梯度是:
∂ L ∂ ω = ( q − y ) ∂ Q ( s , d ; ω ) ω \frac{\partial L}{\partial \omega} = (q - y)\frac{\partial Q(s,d;\omega)}{\omega}
∂ ω ∂ L = ( q − y ) ω ∂ Q ( s , d ; ω )
梯度下降是:
ω ← ω − α ∂ L ∂ ω \omega \leftarrow \omega - \alpha \frac{\partial L}{\partial \omega}
ω ← ω − α ∂ ω ∂ L
我们的导航软件可以根据这种方法来更新预估时间,最后得到更准确的预估时间。
那么,假如我们现在到了"杭州",耗费的时间是3 3 3 。这时候我们准备换一个导航软件,所以上一个导航软件只收集到了我们从"上海"到"杭州"所耗费的时间3 3 3 个小时,那么这个数据有价值吗?
也有价值。
模型再估计一下从"杭州"到"南昌"所需要的时间,比如模型估计从"杭州"到"南昌"需要4.5 4.5 4 . 5 小时,那么从"上海"到"南昌"的估计时间就是7.5 7.5 7 . 5 小时。
现在提一个问题:在上文中,模型一共做了两次估计,一次是直接估计"上海"到"南昌"所需要的时间,一次是基于"上海"到"杭州"的实际时间,在这个基础上估计"上海"到"南昌"所需要的时间,哪个估计更可靠?
当然是第二次的估计,因为第二次的估计含有真实成分在其中。
那么,我们也可以用第二次的估计近似看成"真实值",来更新我们的模型。
第二次的估计,也被称为TD目标(TD Target) 。
所以,我们有如下的式子
T 上海 → 南昌 ≈ T 上海 → 杭州 + T 杭州 → 南昌 T_{\text{上海}\rightarrow\text{南昌}} \approx \bold{T_{\text{上海}\rightarrow\text{杭州}}} + T_{\text{杭州}\rightarrow\text{南昌}}
T 上海 → 南昌 ≈ T 上海 → 杭州 + T 杭州 → 南昌
T 上海 → 杭州 \bold{T_{\text{上海}\rightarrow\text{杭州}}} T 上海 → 杭州 是真实值
然后,我们再把我们刚刚的模型Q ( s , d ; ω ) Q(s,d;\omega) Q ( s , d ; ω ) 代入上式,则有
Q ( s t , a t ; ω ) ≈ r t + Q ( s t + 1 , a t + 1 ; ω ) Q(s_t,a_t;\omega) \approx r_t + Q(s_{t+1},a_{t+1};\omega)
Q ( s t , a t ; ω ) ≈ r t + Q ( s t + 1 , a t + 1 ; ω )
时序差分应用
继续看上面的例子,我们再来梳理一遍。
如果顺利的话,导航软件能成功的收集到我们从"上海"到"南昌"所耗费的时间,那么每收集到一条从"上海"到"南昌"所耗费的时间,导航软件就对预估时间更新一次。更新方法如下:
V ← V + α ( G − V ) V \leftarrow V + \alpha(G - V)
V ← V + α ( G − V )
V V V 是导航软件的预估时间
G G G 是导航软件收集到的时间
α \alpha α 是学习率
这个是不是和上一章的蒙特卡洛非常相似?
我们把耗费的时间换成状态价值,则有:
V ( s t ) ← V ( s t ) + α ( G t − V ( s t ) ) V(s_t) \leftarrow V(s_t) + \alpha(G_t - V(s_t))
V ( s t ) ← V ( s t ) + α ( G t − V ( s t ) )
用图表示如下:
可是,如果不顺利呢?不顺利的话,导航软件只能收集到我们从"上海"到"杭州"所耗费的时间,那么这时候怎么更新预估时间呢?
V ← V + α ( H + V ′ − V ) V \leftarrow V + \alpha(H + V' - V)
V ← V + α ( H + V ′ − V )
V V V 是从"上海"到"南昌"的时间
H H H 是从"上海"到"杭州"的时间
V ′ V' V ′ 是从"杭州"到"南昌"的预估时间
α \alpha α 是学习率
同样,我们把耗费的时间换成状态价值,则有:
V ( s t ) ← V ( s t ) + α ( r t + 1 + γ 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))
V ( s t ) ← V ( s t ) + α ( r t + 1 + γ V ( s t + 1 ) − V ( s t ) )
用图表示如下:
除了这两种方法,在第二章我们还讨论了"动态规划",更新方法如下:
V ( s t ) ← E π [ r t + 1 + γ V ( s t + 1 ) ] V(s_t) \leftarrow \mathbb{E}_{\pi}[r_{t+1} + \gamma V(s_{t+1})]
V ( s t ) ← E π [ r t + 1 + γ V ( s t + 1 ) ]
用图表示如下:
SARSA:在线策略时序差分方法
所以呢,我们现在又有了一种评估策略的方法,时序差分。现在,我们把时序差分应用到强化学习中。
同时,时序差分方法,只是一种评估策略的方法,我们依旧要依赖的策略迭代这个框架,策略评估和策略改进交替进行,直至得到最优解。
题外话,其实不仅是是动态规划、蒙特卡洛和这一章的时序差分,我们的整个强化学习,甚至包括我们之前深度学习,都蕴含着迭代的思想在其中,我们把迭代的过程称之为学习的过程。我在一本描写费马大定理的四百年的证明过程的书中,看到这么一段。
当时,我的第一感受是,欧拉没有把故事讲好啊,他那时候应该说这是"人工智能"。但,或许又是那时候,没人需要人工智能这个故事把。
SARSA的过程
回到主题。
SARSA是一种在线策略方法。
在线策略是指产生数据的策略与要评估改进的策略是同一个策略。其基本思想是遵循一个已有策略进行采样,根据样本数据中的回报更新值函数。或者遵循该策略采取动作,根据动作得到的回报更新值函数。最后根据更新的值函数来优化这个已有的策略,以得到更优的策略。由于要优化改进的策略就是当前遵循的策略,所以此方法被称为在线策略。
SARSA的名字,来自于我们之前讨论的轨迹,在当前状态S S S 下,我们基于一个已有的策略,采取动作A A A ,得到回报R R R ,然后进入到下一个状态S ′ S' S ′ ,我们再做出动作A ′ A' A ′ ,连起来就是SARSA。(所以呢,我个人观点,有些资料把SARSA写成Sarsa,是不合适的。)
那么,现在我们可以利用时序差分方法了,我们用动作价值Q ( s t + 1 , a t + 1 ) Q(s_{t+1},a_{t+1}) Q ( s t + 1 , a t + 1 ) 来更新动作价值Q ( s t , a t ) Q(s_t,a_t) Q ( s t , a t ) :
Q ( s t , a t ) ← Q ( s t , a t ) + α ( r + γ Q ( s t + 1 , a t + 1 ) − Q ( s t , a t ) ) Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha(r + \gamma Q(s_{t+1},a_{t+1}) - Q(s_t,a_t))
Q ( s t , a t ) ← Q ( s t , a t ) + α ( r + γ Q ( s t + 1 , a t + 1 ) − Q ( s t , a t ) )
SARSA的更新方法就是这么一个更新方法,在具体实现方面,我们可以再利用我们上一章讨论的ε \varepsilon ε 探索策略。
具体算法流程如
SARSA算法 输入 : 环境输出 : 最优动作价值估计Q ( s , a ) , s ∈ S , a ∈ A ( s ) Q(s,a),s \in \mathcal{S},a \in \mathcal{A}(s) Q ( s , a ) , s ∈ S , a ∈ A ( s ) 参数 : 学习率α \alpha α 折扣因子γ \gamma γ 初始化 : 动作价值估计Q ( s , a ) ← 任意值 , s ∈ S , a ∈ A Q(s,a) \leftarrow \text{任意值},s \in \mathcal{S},a \in \mathcal{A} Q ( s , a ) ← 任意值 , s ∈ S , a ∈ A 。如果有终止状态,令Q ( s 终止 , a ) ← 0 , a ∈ A Q(s_{\text{终止}},a) \leftarrow 0,a \in \mathcal{A} Q ( s 终止 , a ) ← 0 , a ∈ A 。时序差分 :(对每一条轨迹执行以下操作) 初始化状态s 0 s_0 s 0 根据动作价值估计Q Q Q 得到ε \varepsilon ε 探索策略,并以此采取动作a 0 a_0 a 0 ,得到第一个状态动作对( s 0 , a 0 ) (s_0,a_0) ( s 0 , a 0 ) 对于t = 0 , 1 , 2 , ⋯ , T t=0,1,2,\cdots,T t = 0 , 1 , 2 , ⋯ , T ,依此执行以下操作,直到t = T t=T t = T ,s t = s 终止 s_t=s_{\text{终止}} s t = s 终止 : 采样,环境反馈执行动作a t a_t a t 所得到的回报r t r_t r t 和状态s t + 1 s_{t+1} s t + 1 基于s t + 1 s_{t+1} s t + 1 ,同样通过ε \varepsilon ε 探索策略采取动作a t + 1 a_{t+1} a t + 1 ,得到状态动作对s t + 1 , a t + 1 s_{t+1},a_{t+1} s t + 1 , a t + 1 更新Q ( s t , a t ) Q(s_t,a_t) Q ( s t , a t ) :Q ( s t , a t ) ← Q ( s t , a t ) + α ( r t + γ Q ( s t + 1 , a t + 1 ) − Q ( s t , a t ) ) Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha(r_t + \gamma Q(s_{t+1},a_{t+1}) - Q(s_t,a_t)) Q ( s t , a t ) ← Q ( s t , a t ) + α ( r t + γ Q ( s t + 1 , a t + 1 ) − Q ( s t , a t ) ) * 其中r t + γ Q ( s t + 1 , a t + 1 r_t + \gamma Q(s_{t+1},a_{t+1} r t + γ Q ( s t + 1 , a t + 1 )就是TD目标
SARSA的实现
接下来,我们实现SARSA算法,以调度系统为例。调度系统在我们生活中非常的常见,比如外卖配送调度,网约车调度等。这些系统都极其的庞大复杂,我们只能以一个非常简单的DEMO为例,Gym中的出租车调度。
该例子来自《强化学习:原理与Python实现(肖智清著)》这本书的第五章。
出租车调度问题描述
如图所示,是一个用5×5方格表示的地图,有4个出租车停靠点,分别是B
、G
、R
、Y
。在每个回合开始时,有一个乘客会随机出现在4个出租车停靠点中的一个,并想在任意一个出租车停靠点下车。出租车会随机出现在25个位置的任意一个位置。出租车需要通过移动自己的位置,到达乘客所在的位置,并将乘客接上车,然后移动到乘客想下车的位置,再让乘客下车。出租车只能在地图范围内上下左右移动一格,并且在有竖线阻拦地方不能横向移动。出租车完成一次任务可以得到20个奖励,每次试图移动得到-1个奖励,不合理地邀请乘客上车(例如目前车和乘客不在同一位置,或乘客已经上车)或让乘客下车(例如车不在目的地,或车上没有乘客)得到-10个奖励。希望调度出租车让总奖励的期望最大。
环境及其使用
示例代码:
1 2 3 4 5 6 7 8 9 10 11 import numpy as npnp.random.seed(0 ) import gymenv = gym.make('Taxi-v3' ) env = env.unwrapped env.seed(0 ) print('观察空间 = {}' .format(env.observation_space)) print('动作空间 = {}' .format(env.action_space)) print('状态数量 = {}' .format(env.observation_space.n)) print('动作数量 = {}' .format(env.action_space.n))
运行结果:
1 2 3 4 观察空间 = Discrete(500) 动作空间 = Discrete(6) 状态数量 = 500 动作数量 = 6
然后,我们试着来操作一下。
示例代码:
1 2 3 4 5 6 7 8 9 state = env.reset() taxirow, taxicol, passloc, destidx = env.unwrapped.decode(state) print(taxirow, taxicol, passloc, destidx) print('的士位置 = {}' .format((taxirow, taxicol))) print('乘客位置 = {}' .format(env.unwrapped.locs[passloc])) print('目标位置 = {}' .format(env.unwrapped.locs[destidx])) env.render()
运行结果:
1 2 3 4 0 1 1 2 的士位置 = (0, 1) 乘客位置 = (0, 4) 目标位置 = (4, 0)
解释一下,这个环境中的观测是一个范围为[ 0 , 500 ) [0,500) [ 0 , 5 0 0 ) 的int型数值,用env.decode()
函数进行解码,得到长度为4的元组(tarrow,taxicab,passloc,destidx)
,其各元素含义如下:
taxirow
和taxicol
是取值为{0,1,2,3,4}的int型变量,表示当前出租车的位置。
passloc
是取值为{0,1,2,3,4}的int型数值,表示乘客的位置,其中{0,1,2,3}表示乘客在"出租车停靠点表"中对应的位置等待,4表示乘客在车上。
destidx
是取值为{0,1,2,3}的int型数值,表示目的地,目的地的位置同样由"出租车停靠点表"给出。
乘客的位置、目地会用彩色字母显示、出租车的位置会高亮显示。
如果乘客不在车上,乘客等待地点(位置)的字母会显示为蓝色、目的地所在的字母会显示为洋红色、出租车所在的位置会用黄色高亮
如果乘客在车上,出租车所在的位置会用绿色高亮。
出租车停靠点表
passloc或destidx
字母
坐标
0
R
(0,0)
1
G
(0,4)
2
Y
(4,0)
3
B
(4,3)
再移动一下出租车。
示例代码:
1 2 3 4 5 6 s = env.step(0 ) print(s) s = env.step(0 ) print(s) env.render()
运行结果:
1 2 (126, -1, False, {'prob': 1.0}) (226, -1, False, {'prob': 1.0})
解释一下,其中env.step()
传入动作,用{0,1,2,3,4,5}表示,具体含义参考"出租车动作表"。
出租车动作表
动作数值
含义
env.render()的提示
执行后的奖励
0
向下
South
-1
1
向上
North
-1
2
向右
East
-1
3
向左
West
-1
4
上车
Pickup
-1或-10
5
下车
Dropoff
+20或-10
SARSA的代码
首先,我们创建一个SARSA智能体类。
示例代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class SARSAAgent : def __init__ (self, env, gamma=0.9 , learning_rate=0.2 , epsilon=.01 ) : ''' 初始化 :param env: 环境 :param gamma: 折扣因子 :param learning_rate: 学习率 :param epsilon: epsilon贪心策略 ''' self.gamma = gamma self.learning_rate = learning_rate self.epsilon = epsilon self.action_n = env.action_space.n self.q = np.zeros((env.observation_space.n, env.action_space.n)) def decide (self, state) : ''' epsilon贪心策略 :param state: 状态 :return: ''' if np.random.uniform() > self.epsilon: action = self.q[state].argmax() else : action = np.random.randint(self.action_n) return action def learn (self, state, action, reward, next_state, next_action ,done) : ''' 学习,也就是价值函数更新方法 :param state: 状态 :param action: 动作 :param reward: 奖励 :param next_state: 下一个状态 :param next_action: 下一个动作 :param done: 是否结束 :return: ''' u = reward + self.gamma * self.q[next_state, next_action] * (1. - done) td_error = u - self.q[state, action] self.q[state, action] += self.learning_rate * td_error
智能体负责决策和学习,决策就是我们上文提到的ε \varepsilon ε 贪心策略,学习就是我们上文提到的价值函数更新。
接下来是SARSA算法,就是我们上文所讨论的SARSA的过程。
示例代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 def play_sarsa (env, agent, train=False, render=False) : ''' SARSA :param env: 环境 :param agent: 智能体 :param train: 是否训练 :param render: 是否render :return: ''' episode_reward = 0 observation = env.reset() action = agent.decide(observation) while True : if render: env.render() next_observation, reward, done, _ = env.step(action) episode_reward += reward next_action = agent.decide(next_observation) if train: agent.learn(observation, action, reward, next_observation, next_action, done) if done: break observation, action = next_observation, next_action return episode_reward
然后,我们可以实例化智能体,并进行训练,再试一试效果。
实例化智能体,并训练。
示例代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 import matplotlib.pyplot as pltagent = SARSAAgent(env) episodes = 3000 episode_rewards = [] for episode in range(episodes): episode_reward = play_sarsa(env, agent, train=True ) episode_rewards.append(episode_reward) plt.plot(episode_rewards)
运行结果:
试一试效果。
示例代码:
1 2 3 4 5 agent.epsilon = 0. episode_rewards = [play_sarsa(env, agent) for _ in range(100 )] print('平均回合奖励 = {} / {} = {}' .format(sum(episode_rewards),len(episode_rewards), np.mean(episode_rewards)))
运行结果:
1 平均回合奖励 = 817 / 100 = 8.17
Q-Learning:离线策略时序差分方法
接下来,我们讨论离线策略方法。
Q-Learning的过程
离线策略是指产生数据的策略与评估改进的策略不是同一个策略。其基本思想是,虽然已有一个原始策略,但是并不针对这个原始策略进行采样,而是基于另一个策略进行采样。这另一个策略可以是先前学习到的策略,也可以是人类的策略等一些较为成熟的策略。观察这类策略的行为和回报,并根据这些回报评估和改进原始策略,以此达到学习的目的。
这么说或许略显晦涩难懂,我们来看具体的。
很多资料会在这时候讨论"重要性采样",因为离线策略的理论基础就是重要性采样。我们在这里不讨论,在《6.策略梯度》 这一章,再讨论"重要性采样",因为我认为,我们反过来,先弄明白什么是离线策略,再去讨论重要性采样,或许更容易理解。
在Q-Learning方法中,实际在与环境交互的时候,我们遵循的依旧是一个ε \varepsilon ε 探索策略,以保证经历足够丰富的新状态,我们把遵循的策略记作μ \mu μ 。但是我们的目标策略是一个单纯的贪心策略,保证策略最终收敛到最佳,我们把目标策略记作π \pi π 。
π ( s ) = arg max a ∈ A ( s ) Q ( s , a ) \pi(s) = \argmax_{a\in\mathcal{A}(s)} Q(s,a)
π ( s ) = a ∈ A ( s ) a r g m a x Q ( s , a )
我们的更新方法是:
Q ( s , a ) ← Q ( s , a ) + α ( r + γ max a t + 1 Q ( s t + 1 , a t + 1 ) − Q ( s , a ) ) Q(s,a) \leftarrow Q(s,a) + \alpha(r + \gamma \max_{a_{t+1}}Q(s_{t+1},a_{t+1}) - Q(s,a))
Q ( s , a ) ← Q ( s , a ) + α ( r + γ a t + 1 max Q ( s t + 1 , a t + 1 ) − Q ( s , a ) )
具体算法流程如下:
Q-Learning算法 输入 : 环境输出 : 最优动作价值估计Q ( s , a ) , s ∈ S , a ∈ A ( s ) Q(s,a),s \in \mathcal{S},a \in \mathcal{A}(s) Q ( s , a ) , s ∈ S , a ∈ A ( s ) 。参数 : 学习率α \alpha α 折扣因子γ \gamma γ 初始化 : 动作价值估计Q ( s , a ) ← 任意值 , s ∈ S , a ∈ A Q(s,a) \leftarrow \text{任意值},s \in \mathcal{S},a \in \mathcal{A} Q ( s , a ) ← 任意值 , s ∈ S , a ∈ A 。如果有终止状态,令Q ( s 终止 , a ) ← 0 , a ∈ A Q(s_{\text{终止}},a) \leftarrow 0,a \in \mathcal{A} Q ( s 终止 , a ) ← 0 , a ∈ A 。时序差分更新 :(对每一条轨迹执行以下操作) 初始化状态s 0 s_0 s 0 对于t = 0 , 1 , 2 , ⋯ t=0,1,2,\cdots t = 0 , 1 , 2 , ⋯ ,依此执行以下操作,直到s t = s 终止 s_t=s_{\text{终止}} s t = s 终止 : 在状态s t s_t s t 下,根据ε \varepsilon ε 探索策略μ \mu μ ,采取动作a t a_t a t 环境反馈执行动作a t a_t a t 所得到的回报r t r_t r t 和状态s t + 1 s_{t+1} s t + 1 更新Q ( s , a ) Q(s,a) Q ( s , a ) :Q ( s , a ) ← Q ( s , a ) + α ( r + γ max a t + 1 Q ( s t + 1 , a t + 1 ) − Q ( s t , a t ) ) Q(s,a) \leftarrow Q(s,a) + \alpha(r + \gamma \max_{a_{t+1}}Q(s_{t+1},a_{t+1}) - Q(s_t,a_t)) Q ( s , a ) ← Q ( s , a ) + α ( r + γ max a t + 1 Q ( s t + 1 , a t + 1 ) − Q ( s t , a t ) )
注意和SARSA的区别。
在SARSA中,要基于s t + 1 s_{t+1} s t + 1 ,同样通过ε \varepsilon ε 探索策略采取动作a t + 1 a_{t+1} a t + 1 ,得到状态动作对s t + 1 , a t + 1 s_{t+1},a_{t+1} s t + 1 , a t + 1 。然后更新更新Q ( s t , a t ) Q(s_t,a_t) Q ( s t , a t )
Q ( s t , a t ) ← Q ( s t , a t ) + α ( r t + γ Q ( s t + 1 , a t + 1 ) − Q ( s t , a t ) ) Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha(r_t + \gamma Q(s_{t+1},a_{t+1}) - Q(s_t,a_t))
Q ( s t , a t ) ← Q ( s t , a t ) + α ( r t + γ Q ( s t + 1 , a t + 1 ) − Q ( s t , a t ) )
而在Q-Learning中,不需要再去采取动作a t + 1 a_{t+1} a t + 1 ,以此得到状态动作对s t + 1 , a t + 1 s_{t+1},a_{t+1} s t + 1 , a t + 1 。直接选最大的。
Q ( s , a ) ← Q ( s , a ) + α ( r + γ max a t + 1 Q ( s t + 1 , a t + 1 ) − Q ( s t , a t ) ) Q(s,a) \leftarrow Q(s,a) + \alpha(r + \gamma \max_{a_{t+1}}Q(s_{t+1},a_{t+1}) - Q(s_t,a_t))
Q ( s , a ) ← Q ( s , a ) + α ( r + γ a t + 1 max Q ( s t + 1 , a t + 1 ) − Q ( s t , a t ) )
Q-Learning的实现
接下来,我们来实现一个Q-Learning算法,继续以出租车调度为例。
首先,我们创建一个Q-Learning智能体。
示例代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class QLearningAgent : def __init__ (self, env, gamma=0.9 , learning_rate=0.1 , epsilon=.01 ) : ''' 初始化 :param env: 环境 :param gamma: 折扣因子 :param learning_rate: 学习率 :param epsilon: epsilon贪心策略 ''' self.gamma = gamma self.learning_rate = learning_rate self.epsilon = epsilon self.action_n = env.action_space.n self.q = np.zeros((env.observation_space.n, env.action_space.n)) def decide (self, state) : ''' epsilon贪心策略 :param state: 状态 :return: ''' if np.random.uniform() > self.epsilon: action = self.q[state].argmax() else : action = np.random.randint(self.action_n) return action def learn (self, state, action, reward, next_state, done) : ''' 学习,也就是更新 :param state: 状态 :param action: 动作 :param reward: 奖励 :param next_state: 下一个状态 :param done: 是否完成 :return: ''' u = reward + self.gamma * self.q[next_state].max() * (1. - done) td_error = u - self.q[state, action] self.q[state, action] += self.learning_rate * td_error
接下来是Q-Learning算法,就是我们上文所讨论的Q-Learning的过程。
示例代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 def play_qlearning (env, agent, train=False, render=False) : ''' qlearning算法 :param env: 环境 :param agent: 智能体 :param train: 是否训练 :param render: 是否render :return: ''' episode_reward = 0 observation = env.reset() i = 0 while True : i = i+1 if i > 10000 : return 'drop' if render: env.render() action = agent.decide(observation) next_observation, reward, done, _ = env.step(action) episode_reward += reward if train: agent.learn(observation, action, reward, next_observation,done) if done: break observation = next_observation return episode_reward
然后,我们可以实例化智能体,并进行训练,再试一试效果。
实例化智能体,并训练。
示例代码:
1 2 3 4 5 6 7 8 9 10 11 12 import matplotlib.pyplot as pltagent = QLearningAgent(env) episodes = 4000 episode_rewards = [] for episode in range(episodes): episode_reward = play_qlearning(env, agent, train=True ) episode_rewards.append(episode_reward) plt.plot(episode_rewards)
试一试效果。
示例代码:
1 2 3 4 5 6 7 agent.epsilon = 0. episode_rewards = [play_qlearning(env, agent) for _ in range(100 )] episode_rewards = [e for e in episode_rewards if e != 'drop' ] print('平均回合奖励 = {} / {} = {}' .format(sum(episode_rewards),len(episode_rewards), np.mean(episode_rewards)))
运行结果:
1 平均回合奖励 = 759 / 98 = 7.744897959183674
多步时序差分法
在上文,我们有这么两张图片。
第一张是蒙特卡洛的,第二张是时序差分的。这两张图片很好的反映了两种方法的关键不同点。
更新当前状态的值函数的时候,基于当前状态往未来看的距离不同。
在蒙特卡洛中,这个距离是整个轨迹的长度N N N 。更新方法如下
V ( s t ) ← V ( s t ) + α ( G t − V ( s t ) ) V(s_t) \leftarrow V(s_t) + \alpha(G_t - V(s_t))
V ( s t ) ← V ( s t ) + α ( G t − V ( s t ) )
G t G_t G t 为累积回报
G t = r t + γ r t + 1 + γ 2 r t + 2 + ⋯ + γ T − t r T G_t = r_{t} + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots + \gamma^{T-t} r_T
G t = r t + γ r t + 1 + γ 2 r t + 2 + ⋯ + γ T − t r T
而在时序差分中,距离是1 1 1 ,即
G t = G t 1 = r t + γ V ( s t + 1 ) G_t = G_t^1 = r_{t} + \gamma V(s_{t+1})
G t = G t 1 = r t + γ V ( s t + 1 )
那么,如果在( 1 , N ) (1,N) ( 1 , N ) 之间呢,这个就是多步时序差分法(Multi-Step TD Targets)。
G t m = r t + γ r t + 1 + ⋯ + γ m − 1 r t + m − 1 + γ m G t + m = [ ∑ i = 0 m − 1 γ i r t + i ] + G t + m \begin{aligned}
G_t^m & = r_{t} + \gamma r_{t+1} + \cdots + \gamma^{m-1} r_{t+m-1} + \gamma^m G_{t+m} \\
& = \bigg[\sum_{i=0}^{m-1} \gamma^i r_{t+i}\bigg] + G_{t+m}
\end{aligned}
G t m = r t + γ r t + 1 + ⋯ + γ m − 1 r t + m − 1 + γ m G t + m = [ i = 0 ∑ m − 1 γ i r t + i ] + G t + m
在SARSA和Q-Learning中,γ m Q ( s t + m , a t + m ) \gamma^m Q(s_{t+m},a_{t+m}) γ m Q ( s t + m , a t + m ) 不一样。
在SARSA中,γ m Q ( s t + m , a t + m ) = Q ( s t + m , a t + m ) \gamma^m Q(s_{t+m},a_{t+m}) = Q(s_{t+m},a_{t+m}) γ m Q ( s t + m , a t + m ) = Q ( s t + m , a t + m ) 。
在Q-Learning中,γ m Q ( s t + m , a t + m ) = max a t + m Q ( s t + m , a t + m ) \gamma^m Q(s_{t+m},a_{t+m}) = \max_{a_{t+m}}Q(s_{t+m},a_{t+m}) γ m Q ( s t + m , a t + m ) = max a t + m Q ( s t + m , a t + m ) 。
多步时序差分比单步时序差分更准一些,毕竟"从上海到杭州的实际时间加上杭州到南昌的预估时间"总是比"从上海到嘉兴的实际时间加上嘉兴到南昌的预估时间"要准一些。但是呢,时序差分可每一步在线学习,不必等到回合结束,可以从不完整的序列中学习,虽然收敛性差,但是耗费的时间少。蒙特卡洛必须等到回合结束,虽然收敛性较好,但是耗费的时间多。
所以有一个话题就是,有没有折衷的办法?这个涉及到资格迹,我们不作太多的讨论。