永久建站平台,在网上怎么赚钱?,建筑工程网点代表什么,搭建网站程序文章目录 概览#xff1a;RL方法分类蒙特卡洛方法#xff08;Monte Carlo#xff0c;MC#xff09;MC BasicMC Exploring Starts#x1f7e6;MC ε-Greedy 本系列文章介绍强化学习基础知识与经典算法原理#xff0c;大部分内容来自西湖大学赵世钰老师的强化学习的数学原理… 文章目录 概览RL方法分类蒙特卡洛方法Monte CarloMCMC BasicMC Exploring StartsMC ε-Greedy 本系列文章介绍强化学习基础知识与经典算法原理大部分内容来自西湖大学赵世钰老师的强化学习的数学原理课程参考资料1并参考了部分参考资料2、3的内容进行补充。
系列博文索引
强化学习的数学原理学习笔记 - RL基础知识强化学习的数学原理学习笔记 - 基于模型Model-based强化学习的数学原理学习笔记 - 蒙特卡洛方法Monte Carlo强化学习的数学原理学习笔记 - 时序差分学习Temporal Difference强化学习的数学原理学习笔记 - 值函数近似Value Function Approximation强化学习的数学原理学习笔记 - 策略梯度Policy Gradient强化学习的数学原理学习笔记 - Actor-Critic
参考资料
【强化学习的数学原理】课程从零开始到透彻理解完结主要Sutton Barto Book: Reinforcement Learning: An Introduction机器学习笔记
*注【】内文字为个人想法不一定准确
概览RL方法分类 *图源https://zhuanlan.zhihu.com/p/36494307
蒙特卡洛方法Monte CarloMC
求解RL问题要么需要模型要么需要数据。之前介绍了基于模型model-based的方法。然而在实际场景中环境的模型如状态转移函数往往是未知的这就需要用无模型model-free方法解决问题。
无模型的方法可以分为两大类蒙特卡洛方法Monte CarloMC和时序差分学习Temporal DifferenceTD。本文介绍蒙特卡洛方法。
蒙特卡洛思想通过大数据量的样本采样来进行估计【本质上是大数定律的应用基于独立同分布采样】将策略迭代中依赖于model的部分替换为model-free。
MC的核心idea并非直接求解 q π ( s , a ) q_{\pi} (s, a) qπ(s,a)的准确值而是基于数据sample / experience来估计 q π ( s , a ) q_{\pi} (s, a) qπ(s,a)的值。MC直接通过动作值的定义进行均值估计即 q π ( s , a ) E π [ G t ∣ S t s , A t a ] ≈ 1 N ∑ i 1 N g ( i ) ( s , a ) q_{\pi}(s, a) \mathbb{E}_\pi [ G_t | S_t s, A_t a ] \approx \frac{1}{N} \sum^N_{i1} g^{(i)} (s, a) qπ(s,a)Eπ[Gt∣Sts,Ata]≈N1i1∑Ng(i)(s,a) 其中 g ( i ) ( s , a ) g^{(i)} (s, a) g(i)(s,a)表示对于 G t G_t Gt的第 i i i个采样。
MC Basic
算法步骤在第 k k k次迭代中给定策略 π k \pi_k πk随机初始策略 π 0 \pi_0 π0
策略评估对每个状态-动作对 ( s , a ) (s, a) (s,a)运行无穷或足够多次episode估算 q π k ( s , a ) q_{\pi_{k}} (s, a) qπk(s,a)策略提升基于估算的 q π k ( s , a ) q_{\pi_{k}} (s, a) qπk(s,a)求解迭代策略 π k 1 ( s ) arg max π ∑ a π ( a ∣ s ) q π k ( s , a ) \pi_{k1}(s) \argmax_\pi \sum_a \pi(a|s) q_{\pi_{k}}(s, a) πk1(s)argmaxπ∑aπ(a∣s)qπk(s,a)
MC Basic与策略迭代的区别在第 k k k次迭代中
策略迭代使用迭代方法求出状态值 v π k v_{\pi_k} vπk并基于状态值求出动作值 q π k ( s , a ) q_{\pi_k} (s, a) qπk(s,a)MC Basic直接基于采样/经验均值估计 q π k ( s , a ) q_{\pi_k} (s, a) qπk(s,a)不需要估计状态值
*MC Basic只是用来说明MC的核心idea并不会在实际中应用因为其非常低效。
MC Exploring Starts
思想提升MC Basic的效率
利用数据对于一个轨迹从后往前利用 ( s , a ) (s, a) (s,a)状态-动作对采样做估计 例如对于轨迹 s 1 → a 2 s 2 → a 4 s 1 → a 2 s 2 → a 3 s 5 → a 1 ⋯ s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_4} s_1 \xrightarrow{a_2} s_2 \xrightarrow{a_3} s_5 \xrightarrow{a_1} \cdots s1a2 s2a4 s1a2 s2a3 s5a1 ⋯从后往前采样即先估计 q π ( s 5 , a 1 ) q_\pi(s_5, a_1) qπ(s5,a1)再估计 q π ( s 2 , a 3 ) R t 4 γ q π ( s 5 , a 1 ) q_\pi(s_2, a_3) R_{t4} \gamma q_\pi(s_5, a_1) qπ(s2,a3)Rt4γqπ(s5,a1)进而估计 q π ( s 1 , a 2 ) R t 3 γ q π ( s 2 , a 3 ) q_\pi(s_1, a_2) R_{t3} \gamma q_\pi(s_2, a_3) qπ(s1,a2)Rt3γqπ(s2,a3)以此类推 更新策略不必等待所有episode的数据收集完毕直接基于单个episode进行估计类似于截断策略迭代单次估计不准确但快 这是通用策略迭代Generalized Policy IterationGPI的思想
MC Exploring Starts
Exploring探索每个 ( s , a ) (s, a) (s,a)状态-动作对Starts从每个状态-动作对开始一个episode 与Visit对应从其他的状态-动作对开始一个episode但其轨迹能经过当前的状态-动作对
MC ε-Greedy
Exploring Starts在实际中难以实现考虑引入soft policy随机stochastic选择动作
ε-Greedy策略 π ( a ∣ s ) { 1 − ε ∣ A ( s ) ∣ ( ∣ A ( s ) ∣ − 1 ) , for the greedy action, ε ∣ A ( s ) ∣ , for other ∣ A ( s ) ∣ − 1 actions. \pi(a|s) \begin{cases} 1-\frac{\varepsilon}{|\mathcal{A}(s)|} (|\mathcal{A}(s)|-1), \text{for the greedy action, } \\ \frac{\varepsilon}{|\mathcal{A}(s)|}, \text{for other } |\mathcal{A}(s)|-1 \text{ actions.} \end{cases} π(a∣s){1−∣A(s)∣ε(∣A(s)∣−1),∣A(s)∣ε,for the greedy action, for other ∣A(s)∣−1 actions. 其中 ε ∈ [ 0 , 1 ] \varepsilon \in [0,1] ε∈[0,1] ∣ A ( s ) ∣ |\mathcal{A}(s)| ∣A(s)∣表示状态 s s s下的动作数量。
直观理解以较高概率选择贪心动作greedy action以较低均等概率选择其他动作特性选择贪心动作的概率永远不低于选择其他动作的概率目的平衡exploitation探索和exploration利用 ε 0 \varepsilon 0 ε0侧重于利用永远选择贪心动作 ε 1 \varepsilon 1 ε1侧重于探索以均等概率选择所有动作均匀分布
MC ε-Greedy在策略提升阶段求解下式 π k 1 ( s ) arg max π ∈ Π ε ∑ a π ( a ∣ s ) q π k ( s , a ) \pi_{k1}(s) \argmax_{\color{red}\pi \in \Pi_\varepsilon} \sum_a \pi(a|s) q_{\pi_{k}}(s, a) πk1(s)π∈Πεargmaxa∑π(a∣s)qπk(s,a)
其中 π ∈ Π ε \pi \in \Pi_\varepsilon π∈Πε表示所有ε-Greedy策略的集合。得到的最优策略为 π k 1 ( a ∣ s ) { 1 − ε ∣ A ( s ) ∣ ( ∣ A ( s ) ∣ − 1 ) , a a k ∗ , ε ∣ A ( s ) ∣ , a ≠ a k ∗ . \pi_{k1}(a|s) \begin{cases} 1-\frac{\varepsilon}{|\mathcal{A}(s)|} (|\mathcal{A}(s)|-1), a a_k^*, \\ \frac{\varepsilon}{|\mathcal{A}(s)|}, a \neq a_k^*. \end{cases} πk1(a∣s){1−∣A(s)∣ε(∣A(s)∣−1),∣A(s)∣ε,aak∗,aak∗.
MC ε-Greedy与MC Basic和MC Exploring Starts的区别
后二者求解的范围是 π ∈ Π \pi \in \Pi π∈Π即所有策略的集合后二者得到的是确定性策略前者得到的是随机策略
MC ε-Greedy与MC Exploring Starts的唯一区别在于ε-Greedy策略因此MC ε-Greedy不需要Exploring Starts。
MC ε-Greedy通过探索性牺牲了最优性但可以通过设置一个较小的ε如0.1进行平衡
在实际中可以为ε设置一个较大的初始值随着迭代轮数逐渐减小其取值ε的值越大最终策略的最优性越差
最终训练得到的策略可以去掉ε直接使用greedy的确定性策略consistent。
