IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 强化学习第3章——动态规划 -> 正文阅读

[数据结构与算法]强化学习第3章——动态规划

三、动态规划

满足条件:最优子结构,重复子问题

bellman递归方程可以用动态规划求解

Vlaue function记录子问题的解

Planning(规划):

规划: 环境是已知或近似已知的,个体并不与环境发生实际的交互,而是利用其构建的模型进行计算,在此基础上改善其行为策略。

MDP认为已知所有的环境信息,所以可以用动态规划。

预测:求基于当前策略π的价值函数

input: MDP and π \pi π

? MRP

Output: value function

控制:求最优价值函数和最优策略

input : MDP

Output: 最优路径value funtion最大和最优策略

迭代策略评估

目的:计算给定策略下的状态价值函数。(k表示迭代测试,s’是后续状态,s是当前状态

方法:同步反向迭代,即策略和价值函数同步更新全部状态。在每次迭代过程中,对于第k+1次迭代,所有的状态s的价值用$v_k(s’) 计 算 并 更 新 该 状 态 第 ! [ [ 公 式 ] ] ( h t t p s : / / w w w . z h i h u . c o m / e q u a t i o n ? t e x = k 计算并更新该状态第 ![[公式]](https://www.zhihu.com/equation?tex=k%2B1) 次迭代中使用的价值 ![[]](https://www.zhihu.com/equation?tex=kv_k(s) , 中 s ’ 是 s 的 后 继 状 态 。 最 终 收 敛 到 ,中s’是s的后继状态。最终收敛到 ssv_{\pi}$。
v k + 1 ( s ) = ∑ a ∈ A π ( a ∣ s ) ( R s a + γ ∑ s ′ ∈ S P s s ′ a v k ( s ′ ) ) v k + 1 = R π + γ P π v k v_{k+1}(s)=\sum_{a \in A} \pi(a \mid s)\left(R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P_{s s^{\prime}}^{a} v_{k}\left(s^{\prime}\right)\right)\\ \mathbf{v}^{k+1}=\mathcal{R}^{\pi}+\gamma \mathcal{P}^{\pi} \mathrm{v}^{k} vk+1?(s)=aA?π(as)(Rsa?+γsS?Pssa?vk?(s))vk+1=Rπ+γPπvk
由策略(e.g.均一随机贪心策略)计算状态价值,然后采用贪心策略得到最佳策略

k = 1 随机策略

k > 1 采取v更大的值移动

迭代时可以提前停止,不必完全等到收敛才停止

策略迭代

目的:在当前策略上迭代计算价值函数,再根据价值函数贪婪地更新策略,如此反复多次,最终得到最优策略 π ? \pi_* π??和最优状态函数 v ? v_* v??

策略评估evaluation -> 策略提升improvement:

策略提升:基于原来的策略采用贪心算法从而产生新的价值函数,并得到最优价值和最优策略 π ′ = g r e e d y ( v π ) \pi' = greedy(v_{\pi}) π=greedy(vπ?)

方法:每一步迭代先评估,更新value,然后再采用贪心,找到最优策略

收敛速率独立与初始值和采用的策略?

得到最优值的方式:

不断迭代更新value,直到收敛

提前到达某个点停止:不需要精确算出value,只需要得到最优的价值

价值迭代

目的:不依赖任何策略,直接通过贝尔曼最优方程从前次迭代的价值函数中计算得到当次迭代的价值函数

(由于使用贝尔曼最优方程进行价值迭代时类似于贪婪地选择了最有行为对应的后续状态 的价值,因而价值迭代其实等效于策略迭代中每迭代一次价值函数就更新一次策略的过程)

bellman最优方程:
v ? ( s ) = max ? a ∈ A ( R s a + γ ∑ s ′ ∈ S P s s ′ a v ? ( s ′ ) ) v_{*}(s)=\max _{a \in A}\left(R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P_{s s^{\prime}}^{a} v_{*}\left(s^{\prime}\right)\right) v??(s)=aAmax?(Rsa?+γsS?Pssa?v??(s))
更新价值函数公式:
v k + 1 ( s ) = max ? a ∈ A ( R s a + γ ∑ s ′ ∈ S P s s ′ a v k ( s ′ ) ) v_{k+1}(s)=\max _{a \in A}\left(R_{s}^{a}+\gamma \sum_{s^{\prime} \in S} P_{s s^{\prime}}^{a} v_{k}\left(s^{\prime}\right)\right) vk+1?(s)=aAmax?(Rsa?+γsS?Pssa?vk?(s))

考虑两种情形:

  1. 个体知道环境的动力学特征的情形。
  2. 个体不知道环境动力学特征的情形。

两者的差别体现在:

前者从终止状态位置由进及远开始计算,每次迭代仅计算相关的状态的价值,而且一次计算即得到最优状态价值,

后者在每次迭代时要更新所有状态的价值。

PS:在价值迭代寻找最优策略的过程中,迭代过程中产生的状态价值函数不一定对应一个策略。

ProblemBellman EquationAlgorithm
PredictionBellman Expectation EquationIterative Policy Evaluation
ControlBellman Expectation Equation + Greedy Policy ImprovementPolicy Iteration
ControlBellman Optimality EquationValue Iteration

迭代时间复杂度: O ( m n 2 ) O(mn^2) O(mn2)

总结

使用动态规划求解最优策略和最优价值函数,包括2种方法。

策略评估+策略迭代,是基于bellman迭代方程和贪心策略求解价值函数,然后使用贪心更新策略,继续迭代直到收敛。

价值迭代,是基于bellman最优方程直接求解最优价值函数和最优策略,中间不依靠其他策略决策。注意,价值迭代需要对所有状态价值函数进行更新,并且中间状态价值并不对应一定某种策略(通过某种策略可以求的该价值)。

从动态规划本身性质来看,不需要知道各状态转移概率和具体奖励的函数,甚至不需要精确求出具体价值,而是使用采样产生的奖励和状态转移概率(自己设置)。但是由于基于迭代,需要知道所有后续状态的价值函数,所以对于状态数目较多的情况,计算量较大。

  数据结构与算法 最新文章
LeetCode 383 赎金信[数组] HERODING的Leet
matlab中fill函数的使用方法
动态规划总结篇一
LeetCode530 二叉搜索树的最小绝对差
单链表的增删改查
拓扑排序 golang实现
用栈实现队列的功能Java(leetcode)
两数相加
动态规划思路
希尔排序——C++实现
上一篇文章      下一篇文章      查看所有文章
加:2021-10-28 12:36:29  更:2021-10-28 12:38:49 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2021年12日历 -2021/12/4 22:51:24-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码