导图社区 强化学习1-5
强化学习第二版 1-5 章知识点,原书为 Reinforcement Learning 2nd Edition,本图知识梳理清楚,非常实用,值得收藏。
编辑于2021-09-09 23:19:18强化学习1-5
基本要素
环境状态
个体动作
动作奖励
这里为了刻画问题共性,动作奖励和动作导致的下一状态有关,也不是固定的,也是有概率的
动作奖励总是延后一个时间段的 t 时刻动作的奖励是在 t+1 时刻的
个体策略
状态价值函数
奖励衰减因子
环境状态转化模型
探索率
不同强化学习模型中包含的要素不尽相同 也可能出现其它要素的情况
马尔科夫决策过程(MDP)
需要对模型进行简化才有求解的可能性
简化假设
转化到下一个状态的概率仅与上一个 状态有关,与之前的状态无关
在状态 s 采用动作 a 的概率仅与 当前状态 s 有关,与其他要素无关
动作价值函数仅依赖于当前状态,Gt 代表 收获,直到终止状态的有衰减奖励之和
这样即使终止状态无穷远,也能够通过衰减因子控制长度
动作价值函数
状态价值函数的贝尔曼方程
动作价值函数与状态价值函数的递推关系
动作价值函数的贝尔曼方程
状态价值函数的动作 a 不确定,所以贝尔曼方程是到下一层; 动作价值函数的当前动作已确定,所以是到第二层。
v 中没有 q, q 中没有 v,意味着能够组成方程组求解了
最优价值函数:寻找一个最优策略使得 个体获得的奖励价值比其他策略高
每个状态 s 时,只选具有最高动作价值的动作 a
动态规划
预测问题(策略评估):已知 ①②③④⑥⑦ 求解 ⑤ 即求解给定策略的状态价值函数
基本公式
迭代策略评估,利用基本公式 不断迭代,直到变化在要求范围内

策略提升:已知 ①②③④⑥⑦ 求解更好的 ④⑤ 即寻找更好的策略及状态价值函数
All of them update estimates of the values of states based on estimates of the values of successor states. That is, they update estimates on the basis of other estimates. We call this general idea bootstrapping
策略提升定理
贪婪策略,根据策略提升定理可知, 每一步选择最优的即可
当新策略与旧策略一样好的时候, 价值函数 v 形式与 v* 一致,此时 的新策略一定是最优策略
策略迭代,E 表示策略评估,I 表示策略提升
价值迭代,策略迭代中需要 I,也是一个迭代过程, 在部分迭代轮次中是可以省略掉 I,直接贪婪的。 而价值迭代最终也会迭代到 v*

控制问题(Control Problem)
异步动态规划:每一次迭代并不对所有状态的价值进行更新, 而是依据一定的原则有选择性的更新部分状态的价值
原位动态规划:此时我们不会另外保存一份上一轮计算出的状态价值。而是即时计算即时更新。这样可以减少保存的状态价值的数量,节约内存。代价是收敛速度可能稍慢。
优先级动态规划:该算法对每一个状态进行优先级分级,优先级越高的状态其状态价值优先得到更新。通常使用贝尔曼误差来评估状态的优先级,贝尔曼误差即新状态价值与前次计算得到的状态价值差的绝对值。这样可以加快收敛速度,代价是需要维护一个优先级队列。
实时动态规划:实时动态规划直接使用个体与环境交互产生的实际经历来更新状态价值,对于那些个体实际经历过的状态进行价值更新。这样个体经常访问过的状态将得到较高频次的价值更新,而与个体关系不密切、个体较少访问到的状态其价值得到更新的机会就较少。收敛速度可能稍慢。
性能:相较于其它解 MDP 的算法,DP 是足够高效的,即使状态空间很大,也是多项式时间
蒙特卡洛法
不基于模型/⑦未知
预测问题:已知 ①②③④⑥ 求解 ⑤
策略提升:已知①②③④⑥⑧ 求解更好的 ④⑤
预测问题
基于 episode:从某个状态开始一直到终止状态的完整序列; 通过采样的方式获得很多的 episodes ,并基于此学习
first-visit:尽管目标状态 s 在一个 episode 中出现多次,只使用第一次 出现的回报做平均

every-visit:每次的回报都纳入计算
较于动态规划的优势
从实际经验中学习
从模拟经验中学习
评估一个状态不基于其它状态的评估(非 bootstrap)
当只关注部分状态时,可以只从这些状态开始采样
动作状态评估
也分为 first-visit 与 every-visit
maintaining exploration
显然对于状态 s,episodes 只能处理出现的 q(s, a) 但是选择动作 a 需要评估状态 s 的所有动作
exlporing starts
所有的 (s, a) 对都有非零概率作为采样开始点
不适用于必须从物理环境中产生实际交互的问题
使用所有动作均有非零概率被选中的策略
控制问题
with exploring starts

两个不太可能的假设
exploring starts
策略评估能够在有限的 episodes 内完成
适用策略提升理论
without exploring starts
on-policy
评估/提升的策略与实际用于采样的策略相同
soft:一开始所有的动作 a 都有大于0的几率选中, 之后越来越趋向于最优策略
所有满足一下条件的策略:
允许有一定概率自由探索
off-policy
评估/提升的策略与实际用于采样的策略不同
target policy: 评估/提升的策略
behavior policy: 生成动作的策略
会更慢收敛,但是允许比如来自专家知识类型的"策略"
预测问题
收敛假设(assumpation of converge) behavior policly 比 target policy 更"宽容":
重要性采样:基于其它分布的采样来估计一个分布的期望值
状态-动作链出现的概率:
重要性采样率:
一般重要性采样(ordinary importance sampling): 无偏的(unbiased),采样率的存在方差(variance)大
加权重要性采样(weighted importance sampling): 有偏的(biased),分子分母同时存在采样率约去, 使其有着较小的方差(variance)
实践中,加权方式有着很低的 方差(variance),更经常使用。
Off-policy Monte Carlo Control
使用条件
满足收敛假设
behavior policy 是 soft 的(即所有动作都有不为0的概率被选中)
浮动主题