怎么用html做移动网站吗,网站首图怎么做,网站开发制作公司排行,网站论坛模板下载RL基本框架、MDP概念 MDP是强化学习的基础。MDP能建模一系列真实世界的问题#xff0c;它在形式上描述了强化学习的框架。RL的交互过程就是通过MDP表示的。RL中Agent对Environment做出一个动作#xff08;Action#xff09;#xff0c;Environment给Agent一个反馈#xff…RL基本框架、MDP概念 MDP是强化学习的基础。MDP能建模一系列真实世界的问题它在形式上描述了强化学习的框架。RL的交互过程就是通过MDP表示的。RL中Agent对Environment做出一个动作ActionEnvironment给Agent一个反馈Reward同时Agent从原状态变为新状态。这里的反馈可以是正、负反馈Agent执行动作是根据某个策略Policy进行的。
可以看到强化学习和传统机器学习的区别是 它不能立即得到标记而只能得到一个暂时的反馈多为人为经验设定。因此可以说强化学习是一种标记延迟的监督学习 。
思考MDP中Environment是全部可观测的部分可观测问题也能转化为MDP如何理解
Markov Property
假设状态的历史序列{, , ... }状态具有马尔科夫性当且仅当
p(|)p(|)即“当给定现在(present)未来(future)独立于过去(past)”。
换言之马尔科夫性是指不具备记忆特质。未来的状态与任何历史的状态无关仅与当前状态相关。
Markov Chain
马尔科夫链(Markov Chain)和马尔科夫过程(Markov Process)基本等价。具备离散状态的马尔可夫过程通常被称为马尔可夫链。例如下图中有4个状态箭头表示状态转移数字表示转移概率。从一个节点出发的概率之和为1. 我们将状态转移矩阵用P表示其中每个元素为p(|) 同样P的每一行之和为1.举一个具体例子 上图的马尔科夫过程(MP)有7个状态图中标出了每个状态去相邻状态或保留原地的概率。从出发的采样转移结果可能为1) 2) 3) 等等可以说马尔科夫过程Markov process是一个具备了马尔科夫性质的随机过程。
马尔科夫奖励过程MRP
MRP等于Markov Chain加上奖励即MRPMarkov ChainReward。其中奖励函数(Reward function)是关键R()E[|s]。
现在针对上述例子把奖励放进去假设对应奖励为5对应奖励为10其余状态奖励为0我们得到R的向量为[5,0,0,0,0,0,10]。
值函数Value Function
首先定义反馈值的折扣求和Discounted sum其中
再定义值函数E[|s]E[|s]表示从t时刻开始的未来的奖励。
为啥需要折扣因子
1. 避免在循环MRP中返回无限大的反馈值
2. 对未来的不确定性需要被完全表示出来
3. 有一层类似金融背景的含义即时的反馈总是能赚取比延迟反馈更多的利益对人类来说更倾向于即时反馈
4. 若使用没有折扣的MRP如1那么未来的反馈值就等于即时的反馈值如0那么相当于只关心即时的反馈值
MRP的奖励计算举例
取0.5那么上图中对于采样路径的奖励值是00.5*0 0.25*0 0.125*10 1.25对于采样路径的奖励值是00.5*0 0.25*0 0.125*50.625对于采样路径的奖励值是0
值函数的计算
利用Bellman equation贝尔曼方程即 V(s)包括两部分即时奖励和未来奖励的折扣求和。
它的另一种表达方式是 Bellman equation描述了状态或状态的值的迭代关系举例说明
假如有以下状态和状态转移矩阵下图左那么对于状态它和它的下一个状态、、的状态转移关系和值迭代关系如下图右所示。 Bellman equation也可以写成矩阵的形式 即在MRP中以及
因为矩阵的逆求解复杂度为其中N为状态数。因此直接线性代数求解只适用于较小规模的MRP问题。
真正通用的求解方法是迭代算法如动态规划算法(DP)、蒙特卡洛算法(MC)、时序差分算法(TD)。其中MC和TD都是无模型强化学习适用于不知道概率转移情况的模型 但要注意无模型强化学习并不代表不能被MDP描述 而是指其中的参数是未知的。
蒙特卡洛算法(MC)
MC用“采样”代替直接的策略评估然后求平均累积奖励作为期望累积奖励。关于某个状态的奖励返回的经验样本越多能够得到的平均奖励值就越接近于期望的状态奖励值井且收敛于这个值。具体如下 以下算法是等价的 对于前面例子中的反馈值V()可能有如下采样过程和奖励返回值从而计算平均值
对于采样路径的奖励值是00.5*0 0.25*0 0.125*10 1.25对于采样路径的奖励值是00.5*0 0.25*0 0.125*50.625对于采样路径的奖励值是0以此类推最终求平均即可。
动态规划算法(DP)
如果说MC是一种基于一个事件又一个事件的算法Episode by Episode那么DP就是一个基于动作选择的算法Step-by-Step。两者具有非常多的相似之处。具体如下 其中核心语句是第4行即Bellman equation
Markov Decision Process (MDP)
MDP是带有决策的MRP即MDPMRPactions或MDPMRPdecisions。MDP一般用5元组表示即(S,A,P,R,)。其中S是有限状态的集合A是有限动作的集合P是状态转移矩阵对于每个action有P(s|s,a)R是反馈函数(或奖励值函数)每个状态对应一个值或每个状态-动作对(State-Action)对应一个值即R(s,a)E(|s,a)仍是折扣因子。
MDP中策略(Policy)是指每个状态下应该执行什么动作即它指定了动作的分布。策略表示为即它是与时间t无关的。对于任意的t0有~
MDP和MRP的转换 上图中等式左边是MRP等式右边是MDP右边对动作a求和消掉a因此左边都没有a
MDP和MRP的比较 上图中左边是MRP右边是MDP右边比左边多了一层a节点黑色节点表示动作MRP直接从s状态映射转移到s状态而MDP先把状态s映射到动作a通过再把动作a和状态s的组合映射到新的状态s通过P(s|s,a)体现了MDPMRPactions
MDP中的值函数
在策略下状态s的值函数为表示在初始状态为s的情况下采取策略得到的累积期望奖励值。动作值函数为二者的关系是 以上两式展开变为迭代形式
值函数为
动作值函数为
这两公式叫Bellman Expectation Equation贝尔曼期望方程
思考贝尔曼期望方程只是比贝尔曼方程多了个期望
和的关系 分别将的展开式插入的公式以及将的展开式插入的公式得到更复杂的两个迭代式如下 上式的含义可用一颗三层的树描述根节点是要求的黑色节点是对所有动作求和底层白色节点是对所有状态求和。 类似的也可以用一颗树描述根节点是要求的中间白色节点是对所有状态求和底层黑色节点是对所有动作求和。 策略评估Policy Evaluation
首先关于MDP和MRP的区别做一个形象的补充MRP更像随波逐流MDP更像有人掌舵和前文说的MDPMRPactions一致。 策略评估是指给定一个策略求该策略下的值函数越大越好
下面举例说明策略评估的过程 假设一艘船有两个方向向左或向右还是有7个状态如图所示在的奖励为5在的奖励为10其余奖励为0因此有R[5,0,0,0,0,0,10]
当策略是一直往left同时取0时利用 迭代计算最终收敛得到[5,0,0,0,0,0,10]
思考一策略不变同时取0.5时得到的是多少
思考二策略变为一半概率left一半概率right即P((s)left)0.5P((s)right)0.5同时取0.5时得到的是多少
上式也可以写为 以及MRP形式
策略搜索Policy Search
最优状态值函数对应一个最优策略后者在所有策略中取得最大值函数即 而最优策略就是。当最优值被找到就认为MDP被解决。一般认为只存在唯一的最优值函数但可能会存在多个最优策略。
为了寻找最优策略需要最大化即 对于任意MDP总是存在确定性的最优策略如果已知就能立即得到最优策略
策略求解之策略迭代
策略迭代包括两个步骤策略评估在当前策略更新各个状态的值函数策略更新基于当前的值函数采用-贪心算法找到当前最优的策略即 迭代过程的形象化描述如上图。伪代码如下 思考怎么证明策略一直在提升且策略迭代一定能收敛 最优值函数是在贝尔曼最优方程满足时达到的即 上面两式互相插入得到 策略求解之值迭代
值迭代也是将贝尔曼最优方程作为更新规则 在每一次值迭代中都能找到让当前值函数最大的更新方式 并且用这种方式来更新值函数。不断更新迭代直到值函数不再发生变化。完整伪代码如下 另一个等价的实现算法 思考如何证明策略的改进和值函数的改进是一致的
策略迭代和值迭代的对比
无论策略迭代还是值迭代都属于动态规划算法。
策略迭代包括策略评估 和 策略提升或策略更新
值迭代包括找到最优值函数 和 策略抽取这里不需要重复两个动作因为一旦值函数是最优的那么相应的策略就一定是最优的也就是收敛了。所以你会发现策略迭代的算法有两层loop而值迭代的算法只有一层。
值迭代中寻找最优值函数也可以看成是一种策略提升因为有个max操作和 简化的策略评估的结合体因为无论收敛与否都只有一次v(s)的赋值。
策略迭代更像是一种累计平均的计算方式而值迭代更像是一种单步最好的方式。 从速度来说值迭代更加迅速特别是在策略空间较大的时候。从准确度来说策略迭代更接近于样本的真实 分布。
MDP和RL扩展链接
https://github.com/ucla-rlcourse/RLexample/tree/master/MDP
REINFORCEjs: Gridworld with Dynamic Programming
