香洲网站建设,宿迁百度,公司变更地址需要多少费用,seo推广和百度推广的区别参考
Reinforcement Learning, Second Edition
An Introduction
By Richard S. Sutton and Andrew G. Barto动态规划 (Dynamic Programming, DP) 是一类优化方法#xff0c;在给定一个用马尔可夫决策过程 (MDP) 描述的完备环境模型的情况下#xff0c;其可以计算最优的策…参考
Reinforcement Learning, Second Edition
An Introduction
By Richard S. Sutton and Andrew G. Barto动态规划 (Dynamic Programming, DP) 是一类优化方法在给定一个用马尔可夫决策过程 (MDP) 描述的完备环境模型的情况下其可以计算最优的策略。 Recall: Bellman Equation
我们知道 v π v_\pi vπ的贝尔曼方程可以写作如下形式 v π ( s ) ∑ a π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r γ v π ( s ′ ) ] v_\pi(s)\sum_a \pi(a|s) \sum_{s,r} p(s,r|s,a)[r\gamma v_{\pi}(s)] vπ(s)a∑π(a∣s)s′,r∑p(s′,r∣s,a)[rγvπ(s′)] 如何求解最优策略 v ∗ ( s ) v_*(s) v∗(s)呢 实际上对于每一个可能的状态 s ∈ S s\in \mathcal{S} s∈S都有这样的一个方程因此可以通过解这样一组贝尔曼方程组来直接求解出 v ∗ ( s ) v_*(s) v∗(s)。但是问题在于许多场景的状态空间很大因此难以直接利用解方程的方式来求。因此我们考虑迭代的方式。
Example Task —— 最短路径任务 为了说明以下三个不同的算法我们引入一个 exmaple task。 智能体的目标是找到从任意一个点出发怎么走才能最快到达图上的两个终止状态。每走一步 r − 1 r-1 r−1如果出界就保持原来的状态不动。 我们希望智能体能够找到最优价值函数 v ∗ ( s ) v_*(s) v∗(s) 或者最优策略 π ∗ ( a ∣ s ) \pi_*(a|s) π∗(a∣s)以矩阵表示
策略评估算法
策略评估Policy Evaluation算法的核心思想在于如果存在最优价值函数 v ∗ ( s ) v_*(s) v∗(s)那么 v ∗ ( s ) v_*(s) v∗(s)实际上就是贝尔曼方程的一个不动点我们从任意一个 V 0 V_0 V0出发不断迭代贝尔曼方程最终收敛到的价值函数就是最优价值函数。 Δ \Delta Δ记录前后两个价值函数矩阵的最大差值当差值足够小就认为找到了 v ∗ ( s ) v_*(s) v∗(s)
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
plt.rcParams[font.sans-serif] [Microsoft YaHei]
plt.rcParams[axes.unicode_minus] False # 用来正常显示负号STOP np.array([[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]
])
V np.array([[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]
]).astype(float)
V_new V.copy()
actions [(0,1),(1,0),(0,-1),(-1,0)]
gamma 1.0
states [(i,j) for i in range(4) for j in range(4)]
print(states)for step in range(100): # 对应贝尔曼方程for state in states: # for s \in Sif STOP[state]:continuev V[state]res 0for action in actions: # \sum as_next [action[0]state[0], action[1]state[1]]# 处理边界动作if s_next[0]0:s_next[0]0if s_next[0]3:s_next[0]3if s_next[1]0:s_next[1]0if s_next[1]3:s_next[1]3# print(state,a:,action,- s,s_next)r -1 # 每走一步奖励固定是 -1res 1/4 * (r gamma * V[tuple(s_next)]) # \pi(a|s) [r \gamma V(s)]V_new[state] resdelta (abs(V_new-V)).max()V V_new.copy()if delta 0.01:plt.figure(figsize(3,2))sns.heatmap(V,annotTrue,cmapBlues_r)plt.title($V_\pi(s)$ step{} $\Delta${:0.4f}.format(step,delta),colorgreen)plt.xlabel(x66ccff)plt.ylabel(迭代策略评估)plt.show()print(break at delta{:.4f}, step{}.format(delta, step))breakelif step 3:plt.figure(figsize(3,2))sns.heatmap(V,annotTrue,cmapBlues_r)plt.title($V_\pi(s)$ step{} $\Delta${:0.4f}.format(step,delta),colorblack)plt.ylabel(迭代策略评估)plt.show()策略评估使用了长达 88 步才达到收敛
价值迭代Value Iteration 价值迭代仅仅是将贝尔曼最优方程变为一条更新规则。另外除了从达到最大值的状态更新以外价值迭代与策略评估的更新公式几乎完全相同 价值迭代v 更新取 max和策略评估不动点的区别仅仅在于多了一个取所有后继状态的价值的 max \max max 而不是平均期望价值。
STOP np.array([[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]
])
V np.array([[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]
]).astype(float)
V_new V.copy()
actions [(0,1),(1,0),(0,-1),(-1,0)]
gamma 1.0
states [(i,j) for i in range(4) for j in range(4)]
print(states)for step in range(100): # 对应贝尔曼方程for state in states: # for s \in Sif STOP[state]:continuev V[state]# res 0res_a_ls [] # ------ 修改的地方for action in actions: # \sum as_next [action[0]state[0], action[1]state[1]]# 处理边界动作if s_next[0]0:s_next[0]0if s_next[0]3:s_next[0]3if s_next[1]0:s_next[1]0if s_next[1]3:s_next[1]3# print(state,a:,action,- s,s_next)r -1 # 每走一步奖励固定是 -1# res 1/4 * (r gamma * V[tuple(s_next)]) # \pi(a|s) [r \gamma V(s)]res_a (r gamma * V[tuple(s_next)]) # ------ 修改的地方res_a_ls.append(res_a) # ------ 修改的地方V_new[state] max(res_a_ls) # ------ 修改的地方 delta (abs(V_new-V)).max()V V_new.copy()if delta 0.01:plt.figure(figsize(3,2))sns.heatmap(V,annotTrue,cmapBlues_r)plt.title($V_\pi(s)$ step{} $\Delta${:0.4f}.format(step,delta),colorgreen)plt.xlabel(x66ccff)plt.ylabel(价值迭代)plt.show()print(break at delta{:.4f}, step{}.format(delta, step))breakelif step 3:plt.figure(figsize(3,2))sns.heatmap(V,annotTrue,cmapBlues_r)plt.title($V_\pi(s)$ step{} $\Delta${:0.4f}.format(step,delta),colorblack)plt.ylabel(价值迭代)plt.show()注意到价值迭代只用了3步就达到了收敛比策略评估算法快得多。
策略迭代Policy Iteration
策略迭代与前两者不同不仅仅维护 V π ( s ) V_\pi(s) Vπ(s)矩阵还维护表示策略的 π ( a ∣ s ) \pi(a|s) π(a∣s)矩阵两者交替进行更新。
其分为两个阶段
策略评估根据最优动作 π ( a ∣ s ) \pi(a|s) π(a∣s) 更新 V π V_\pi Vπ而不是求平均策略改进根据 V π V_\pi Vπ 更新每一个状态 s s s 的最优动作 π ( a ∣ s ) \pi(a|s) π(a∣s)
因此策略迭代相当于在策略评估算法但没有求平均而是 π \pi π直接给出 a a a的基础上加了一个策略改进的部分。
STOP np.array([[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]
])
V np.array([[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]
]).astype(float)
V_new V.copy()
actions [(0,1),(1,0),(0,-1),(-1,0)]
gamma 1.0
states [(i,j) for i in range(4) for j in range(4)]
print(states)# 策略迭代新增
np.random.seed(42)
Policy np.random.randint(0,4,16).reshape(4,4) # 随机初始化策略
Policyarray([[2, 3, 0, 2], [2, 3, 0, 0], [2, 1, 2, 2], [2, 2, 3, 0]])
for step in range(100): # 对应贝尔曼方程######################## a) 先根据策略Policy进行价值更新for state in states: # for s \in Sif STOP[state]:continuev V[state]res 0# res_a_ls [] # ------修改的地方# for action in actions: # ------修改的地方 # 不需要 for aaction actions[Policy[state]] # ------修改的地方 # 根据 Policy 选择as_next [action[0]state[0], action[1]state[1]]# 处理边界动作if s_next[0]0:s_next[0]0if s_next[0]3:s_next[0]3if s_next[1]0:s_next[1]0if s_next[1]3:s_next[1]3r -1 # 每走一步奖励固定是 -1res (r gamma * V[tuple(s_next)]) # \pi(a|s) [r \gamma V(s)]# res_a (r gamma * V[tuple(s_next)]) # ------修改的地方# res_a_ls.append(res_a) # ------修改的地方# V_new[state] max(res_a_ls) # -------修改的地方V_new[state] resdelta (abs(V_new-V)).max()V V_new.copy()############################ b) 对每一个状态更新策略for state in states:res_ls []for i in range(4):s_next [actions[i][0] state[0] , actions[i][1] state[1]]# 处理边界动作if s_next[0]0:s_next[0]0if s_next[0]3:s_next[0]3if s_next[1]0:s_next[1]0if s_next[1]3:s_next[1]3res_a (r gamma * V[tuple(s_next)])res_ls.append(res_a)best_action_index np.argmax(res_ls)Policy[state] best_action_indexif delta 0.01:plt.figure(figsize(3,2))sns.heatmap(V,annotTrue,cmapBlues_r)plt.title($V_\pi(s)$ step{} $\Delta${:0.4f}.format(step,delta),colorgreen)plt.xlabel(x66ccff)plt.ylabel(策略迭代)plt.show()print(break at delta{:.4f}, step{}.format(delta, step))breakelif step 3:plt.figure(figsize(3,2))sns.heatmap(V,annotTrue,cmapBlues_r)plt.title($V_\pi(s)$ step{} $\Delta${:0.4f}.format(step,delta),colorblack)plt.ylabel(策略迭代)plt.show()策略迭代也用了3步达到最优。这三种方法最终得到的 V π V_\pi Vπ都不同但是都是最优策略看图容易验证只要往浅色区域走总能最快到达终止位置
异步动态规划
上面的三种算法都是完全遍历完所有状态 s s s再进行策略/价值的更新的实际上也就是存储了新旧两个矩阵。关键问题在于遍历所有状态很多情况下是不可能的比如围棋的合法状态空间大概为 1 0 170 10^{170} 10170这是没法遍历的。
异步 DP 就是选择性地更新某些状态从而增加了算法的灵活性。可以选择任意的状态 s s s进行更新有的状态可能已经更新了很多次但是有的状态甚至可以没有更新。
异步 DP 的优势在于
有可能减少计算量并不需要完全遍历所有状态有可能多考虑一些关键状态从而提高效率
广义策略迭代GPI 广义策略迭代 (GPI) 指让策略评估和策略改进相互作用的一般思路 策略迭代包含两个过程
用 π \pi π 更新 V V V a arg max a π ( a ∣ s ) , a → s ′ → V ( s ′ ) a\arg \max_a \pi(a|s), a \to s \to V(s) aargmaxaπ(a∣s),a→s′→V(s′)用 V V V 更新 π \pi π选择 max r γ V ( s ′ ) r\gamma V(s) rγV(s′) 的动作
这两个过程交替进行。
但是在广义策略迭代中交替不是必须的也不是必须要更新所有状态 GPI 允许在某些特殊情况下甚至有可能仅有一个状态在评估流程中得到更新用 π \pi π 更新 V V V然后马上就返回到改进流程用 V V V 更新 π \pi π。 几乎所有的强化学习方法都可以被描述为 GPI 。也就是说几乎所有方法都包含明确定义的策略和价值函数且如右图所示策略总是基于特定的价值函数进行改进价值函数也始终会向对应特定策略的真实价值函数收敛。GPI 中我们也可以让每次走的步子小一点部分地实现其中一个目标。无论是哪种情况尽管没有直接优化总目标但评估和改进这两个流程结合在一起就可以最终达到最优的总目标
