【强化学习】07——规划与学习（Dyna

Dyna"/>

【强化学习】07——规划与学习（Dyna

文章目录

• 前置知识回顾
• • 策略值函数估计（Policy Evaluation）
  • 策略提升（Policy Improvement）
• 模型（Model）
• 规划(Planning)
• 规划与学习(Planning and Learning)
• Dyna (集成规划、决策和学习）
• • Dyna的框架
  • Dyna伪代码
  • Example1：Dyna Maze
  • Example2：Blocking Maze
  • Example3：Shortcut Maze
  • 代码
  • 结果
• 参考

前置知识回顾

详见

策略值函数估计（Policy Evaluation）

给定环境MDP和策略𝜋，策略值函数估计如下
V π ( s ) = E [ R ( s 0 , a 0 ) + γ R ( s 1 , a 1 ) + γ 2 R ( s 2 , a 2 ) + ⋯ ∣ s 0 = s , π ] = E a ∼ π ( s ) [ R ( s , a ) + γ ∑ s ′ ∈ S P s π ( s ) ( s ′ ) V π ( s ′ ) ] = E a ∼ π ( s ) [ Q π ( s , a ) ] Q π ( s , a ) = E [ R ( s 0 , a 0 ) + γ R ( s 1 , a 1 ) + γ 2 R ( s 2 , a 2 ) + ⋯ ∣ s 0 = s , a 0 = a , π ] = R ( s , a ) + γ ∑ s ′ ∈ S P s π ( s ) ( s ′ ) V π ( s ′ ) \begin{aligned} V^{\pi}(s)& =\mathbb{E}[R(s_{0},a_{0})+\gamma R(s_{1},a_{1})+\gamma^{2}R(s_{2},a_{2})+\cdots|s_{0}=s,\pi] \\ &=\mathbb{E}_{a\sim\pi(s)}\left[R(s,a)+\gamma\sum_{s^{\prime}\in S}P_{s\pi(s)}(s^{\prime})V^{\pi}(s^{\prime})\right] \\ &=\mathbb{E}_{a\sim\pi(s)}[Q^{\pi}(s,a)] \\ Q^{\pi}(s,a)& =\mathbb{E}[R(s_{0},a_{0})+\gamma R(s_{1},a_{1})+\gamma^{2}R(s_{2},a_{2})+\cdots|s_{0}=s,a_{0}=a,\pi] \\ &=R(s,a)+\gamma\sum_{s^{\prime}\in S}P_{s\pi(s)}(s^{\prime})V^{\pi}(s^{\prime}) \end{aligned} Vπ(s)Qπ(s,a)​=E[R(s0​,a0​)+γR(s1​,a1​)+γ2R(s2​,a2​)+⋯∣s0​=s,π]=Ea∼π(s)​[R(s,a)+γs′∈S∑​Psπ(s)​(s′)Vπ(s′)]=Ea∼π(s)​[Qπ(s,a)]=E[R(s0​,a0​)+γR(s1​,a1​)+γ2R(s2​,a2​)+⋯∣s0​=s,a0​=a,π]=R(s,a)+γs′∈S∑​Psπ(s)​(s′)Vπ(s′)​

策略提升（Policy Improvement）

• 对于两个策略𝜋，𝜋′，如果满足如下性质，𝜋′是𝜋的策略提升：
• 对于任何状态𝑠，有 Q π ( s , π ′ ( s ) ) ≥ V π ( s ) Q^{\pi}(s,\pi^{\prime}(s))\geq V^{\pi}(s) Qπ(s,π′(s))≥Vπ(s)
• 进而， 𝜋和𝜋′满足：对任何状态𝑠，有 V π ′ ( s ) ≥ V π ( s ) V^{\pi^{\prime}}(s)\geq V^{\pi}(s) Vπ′(s)≥Vπ(s)
• 也即是 𝜋′的策略价值（期望回报）超过𝜋， 𝜋′比𝜋更加优秀。
  证明：
  v π ( s ) ≤ q π ( s , π ′ ( s ) ) = E [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s , A t = π ′ ( s ) ] = E π ′ [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s ] ≤ E π ′ [ R t + 1 + γ q π ( S t + 1 , π ′ ( S t + 1 ) ) ∣ S t = s ] = E π ′ [ R t + 1 + γ E [ R t + 2 + γ v π ( S t + 2 ) ∣ S t + 1 , A t + 1 = π ′ ( S t + 1 ) ] ∣ S t = s ] = E π ′ [ R t + 1 + γ R t + 2 + γ 2 v π ( S t + 2 ) S t = s ] ≤ E π ′ [ R t + 1 + γ R t + 2 + γ 2 R t + 3 + γ 3 v π ( S t + 3 ) ∣ S t = s ] ⋮ ≤ E π ′ [ R t + 1 + γ R t + 2 + γ 2 R t + 3 + γ 3 R t + 4 + ⋯ ∣ S t = s ] = v π ′ ( s ) . \begin{aligned} v_{\pi}(s)& \leq q_{\pi}(s,\pi'(s)) \\ &=\mathbb{E}[R_{t+1}+\gamma v_{\pi}(S_{t+1})\mid S_{t}=s,A_{t}=\pi'(s)] \\ &=\mathbb{E}_{\pi'}[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_{t}=s] \\ &\leq\mathbb{E}_{\pi'}[R_{t+1}+\gamma q_{\pi}(S_{t+1},\pi'(S_{t+1}))|S_{t}=s] \\ &=\mathbb{E}_{\pi'}[R_{t+1}+\gamma\mathbb{E}[R_{t+2}+\gamma v_{\pi}(S_{t+2})|S_{t+1},A_{t+1}=\pi'(S_{t+1})]\mid S_{t}=s] \\ &=\mathbb{E}_{\pi'}\big[\begin{matrix}R_{t+1}+\gamma R_{t+2}+\gamma^{2}v_{\pi}(S_{t+2})&S_{t}=s\big]\end{matrix} \\ &\le\mathbb{E}_{\pi'}\big[R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\gamma^3v_\pi(S_{t+3})\big|S_t=s\big] \\ &\vdots\\ &\leq\mathbb{E}_{\pi'}\big[R_{t+1}+\gamma R_{t+2}+\gamma^{2}R_{t+3}+\gamma^{3}R_{t+4}+\cdots\big|S_{t}=s\big] \\ &=v_{\pi^{\prime}}(s). \end{aligned} vπ​(s)​≤qπ​(s,π′(s))=E[Rt+1​+γvπ​(St+1​)∣St​=s,At​=π′(s)]=Eπ′​[Rt+1​+γvπ​(St+1​)∣St​=s]≤Eπ′​[Rt+1​+γqπ​(St+1​,π′(St+1​))∣St​=s]=Eπ′​[Rt+1​+γE[Rt+2​+γvπ​(St+2​)∣St+1​,At+1​=π′(St+1​)]∣St​=s]=Eπ′​[Rt+1​+γRt+2​+γ2vπ​(St+2​)​St​=s]​≤Eπ′​[Rt+1​+γRt+2​+γ2Rt+3​+γ3vπ​(St+3​) ​St​=s]⋮≤Eπ′​[Rt+1​+γRt+2​+γ2Rt+3​+γ3Rt+4​+⋯ ​St​=s]=vπ′​(s).​

模型（Model）

在强化学习中，无特殊说明的话，模型通常指的是环境模型，而非智能体模型。
定义：给定一个状态和动作，模型能够预测下一个状态和奖励的分布: 即 P ( s ′ , r ∣ s , a ) \mathcal P(s',r|s,a) P(s′,r∣s,a)
模型的分类

• 分布模型(distribution model)
  • 描述了轨迹的所有可能性及其概率
  • 相当于白盒模型
• 样本模型(sample model)
  • 根据概率进行采样，只产生一条可能的轨迹
  • 相当于黑盒模型

模型的作用

• 得到模拟的经验数据(simulated experiences)
  

规划(Planning)

定义：输入一个模型，输出一个策略的搜索过程
规划的分类：

• 状态空间的规划 (state-space planning)
  • 在状态空间搜索最佳策略
• 规划空间的规划 (plan-space planning)
  • 在规划空间搜索最佳策略，包括遗传算法和偏序规划
  • 这时，一个规划就是一个动作集合以及动作顺序的约束
  • 这时的状态就是一个规划，目标状态就是能完成任务的规划

规划的通用框架

• 通过模型采样得到模拟数据
• 利用模拟数据更新值函数从而改进策略
  
  规划的好处
• 任何时间点可以被打断或者重定向
• 在复杂问题下，进行小而且增量式的时间步规划是很有效的

规划与学习(Planning and Learning)

• 不同点
  • 规划：利用模型产生的模拟经验
  • 学习：利用环境产生的真实经验
• 相同点
  • 通过回溯(back-up)更新值函数的估计
  • 统一来看，学习的方法可以用在模拟经验上

注意：Q-learning用的是真实环境产生的经验数据，而Q-planning则是利用模型产生的模拟经验。

Dyna (集成规划、决策和学习）

通过于环境交互产生的经验可以有以下两种途径：

• 用于更新模型
  • 模型学习, 或间接强化学习
  • 对经验数据的需求少
• 用于直接更新值函数和策略
  • 直接强化学习（无模型强化学习）
  • 简单且不受模型偏差的影响

Dyna的框架

• 和环境交互产生真实经验
• 左边代表直接强化学习
  • 更新值函数和策略
• 右下角落边代表学习模型
  • 使用真实经验更新模型
• 右边代表基于模型的规划
  • 基于模型随机采样得到模拟经验
  • 只从以前得到的状态动作对随机采样
  • 使用模拟经验做规划更新值函数和策略

Dyna伪代码

Example1：Dyna Maze

环境
• 4个动作(上下左右)
• 碰到障碍物和边界静止
• 到达目标（𝐺），得到奖励+1
• 折扣因子 0.95
结果
• 横轴代表游戏轮数
• 纵轴代表到达 𝐺 花的时间步长
• 不同曲线代表采用不同的规划步长
• 规划步长越长，表现收敛越快

那么为什么Dyna算法会更快呢？

通过更多的sample，可以使得策略更优，更容易靠近终点。

模型不准？
原因：

• 环境是随机的，并且只观察到了有限的样本
• 模型使用了泛化性不好的函数估计
• 环境改变了，并且还没有被算法检测到

Example2：Blocking Maze

Dyna-Q+：

• 奖励更改为 r + κ τ r+\kappa\sqrt{\tau} r+κτ ​
  • r r r原来的奖励
  • κ \kappa κ小的权重参数
  • τ \tau τ某个状态多久未到达过了

Example3：Shortcut Maze

Dyna-Q+能够发现捷径(鼓励探索)

代码

class DynaQ():def __init__(self, env, gamma, alpha, epsilon, numOfEpisodes, numOfTrainQLearning, numOfActions=4):self.env = envself.gamma = gammaself.alpha = alphaself.epsilon = epsilonself.numOfEpisodes = numOfEpisodesself.numOfActions = numOfActions# 初始化Q(s, a)表self.Q_table = np.zeros([self.env.nrows * self.env.ncols, numOfActions])# 初始化模型self.Model = dict()# Q-learning 训练次数self.numOfTrainQLearning = numOfTrainQLearning# Choose A from S using policy derived from Q (e.g., epsilon-greedy)def ChooseAction(self, state):if np.random.random() < self.epsilon:action = np.random.randint(self.numOfActions)else:action = np.argmax(self.Q_table[state])return actiondef DynaQRun(self):# 记录每一条序列的回报returnList = []# 显示10个进度条for i in range(10):# tqdm的进度条功能with tqdm(total=int(self.numOfEpisodes / 10), desc='Iteration %d' % i) as pbar:# 每个进度条的序列数for episode in range(int(self.numOfEpisodes / 10)):# initialize statestate = self.env.Reset()done = FalseepisodeReward = 0# Loop for each step of episode:while not done:# Choose A from S using policy derived from Q (e.g., epsilon-greedy)action = self.ChooseAction(state)# Take action A, observe R, S'stateprime, reward, done = self.env.Step(action)episodeReward += reward# UpdateTD_error = reward + self.gamma * self.Q_table[stateprime].max() \- self.Q_table[state, action]self.Q_table[state,action] += self.alpha * TD_error# 将数据添加到模型中self.Model[(state, action)] = stateprime, reward# Q-planning循环for i in range(self.numOfTrainQLearning):# 随机选择曾经遇到过的状态动作对(s, a), (s_next, r) = random.choice(list(self.Model.items()))# Q-plannnigTD_error = r + self.gamma * self.Q_table[s_next].max() \- self.Q_table[s, a]self.Q_table[s, a] += self.alpha * TD_errorstate = stateprimereturnList.append(episodeReward)if (episode + 1) % 10 == 0:  # 每10条序列打印一下这10条序列的平均回报pbar.set_postfix({'episode':'%d' % (self.numOfEpisodes / 10 * i + episode + 1),'return':'%.3f' % np.mean(returnList[-10:])})pbar.update(1)return returnList

结果

Q-planning训练次数为0

可以看到，当Dyna-Q的Q-planning训练次数为0时，Dyna-Q就退化成了Q-learning。

十次训练平均：

随着 Q-planning 步数的增多，Dyna-Q 算法的收敛速度也随之变快。当然，并不是在所有的环境中，都是 Q-planning 步数越大则算法收敛越快，这取决于环境是否是确定性的，以及环境模型的精度。在上述悬崖漫步环境中，状态的转移是完全确定性的，构建的环境模型的精度是最高的，所以可以通过增加 Q-planning 步数来直接降低算法的样本复杂度。

参考

[1] 伯禹AI
[2]
[3] 动手学强化学习
[4] Reinforcement Learning