用.net做购物网站,一个外国人做的汉子 网站,兰州官网优化技术厂家,wordpress 二次元马尔可夫决策过程是强化学习中的基本问题模型之一#xff0c;而解决马尔可夫决策过程的方法我们统称为强化学习算法。
动态规划#xff08; dynamic programming, DP #xff09;具体指的是在某些复杂问题中#xff0c;将问题转化为若干个子问题#xff0c;并在求解每个子…马尔可夫决策过程是强化学习中的基本问题模型之一而解决马尔可夫决策过程的方法我们统称为强化学习算法。
动态规划 dynamic programming, DP 具体指的是在某些复杂问题中将问题转化为若干个子问题并在求解每个子问题的过程中保存已经求解的结果以便后续使用。
常见的动态规划算法包括
值迭代value iteration, VI策略迭代policy iteration, PIQ-learning 算法等。
动态规划三个基本原理
最优化原理问题的最优解所包含的子问题的解也是最优的就称该问题具有最优子结构无后效性某阶段状态一旦确定就不受这个状态以后决策的影响重叠子问题不是动态规划问题的必要条件
马尔可夫决策过程的目标是最大化累积回报 G t R t 1 γ G t 1 G_t R_{t1} \gamma G_{t1} GtRt1γGt1
我们要解决 G t 1 G_{t1} Gt1的问题可以一次拆分成解决 G t , G t − 1 , . . . , G 1 G_{t},G_{t-1},...,G_1 Gt,Gt−1,...,G1的问题这其实就满足动态规划性质中的最优化原理
策略迭代与价值迭代
但如果只给定马尔可夫决策过程该如何寻找最佳策略从而得到最佳价值函数optimal value function
最佳价值函数寻找一种策略 π \pi π使得每个状态的价值最大。即使得V最大的 π \pi π V ∗ ( s ) m a x π V π ( s ) V^*(s) max_{\pi}V_{\pi}(s) V∗(s)maxπVπ(s)
最佳策略下每个状态的价值函数都为最大值如果可以求得最佳价值函数就认为该决策过程的环境可解在可解环境下最佳价值函数是一致的但可以有多个策略达到最佳价值函数。换句话说存在最优值但解。
当得到最佳价值函数后可以通过对Q函数最大化来得到最佳策略使得Q函数最大化的动作就是最佳的动作进而可以提取出最佳策略。 π ∗ ( a ∣ s ) { 1 , a a r g m a x a ∈ A Q ∗ ( s , a ) 0 , 其他 {\pi}^{*}(a|s) \left\{ \begin{matrix} 1 , a argmax{ \atop a \in A}Q^{*}(s,a)\\ 0,其他 \end{matrix} \right. π∗(a∣s){1,aargmaxa∈AQ∗(s,a)0,其他
Q怎样进行策略搜索
方法一穷举法假设有S个状态A个动作。总共 ∣ A ∣ ∣ S ∣ |A|^{|S|} ∣A∣∣S∣个策略。
方法二策略迭代和价值迭代
策略迭代
策略迭代包括策略评估和策略改进
策略评估给定马尔可夫决策过程和策略评估我们可以获得多少价值即对于当前策略我们可以得到多大的价值。
在下图左侧先进行策略评估即基于给定的策略 π \pi π先求得价值函数V。然后基于奖励函数和状态转移函数可以计算得到Q函数。 Q π i ( s , a ) R ( s , a ) γ ∑ s ′ ∈ S p ( s ′ ∣ s , a ) V π i ( s ′ ) Q_{\pi_i}(s,a) R(s,a) \gamma\sum{ \atop s \in S}p(s|s,a)V_{\pi_i}(s) Qπi(s,a)R(s,a)γ∑s′∈Sp(s′∣s,a)Vπi(s′)
在下图右侧随后进行策略改进基于Q函数取使得Q取最大值的动作做为下一个策略。 π i 1 ( s ) a r g m a x a Q π i ( s , a ) \pi_{i1}(s) argmax_aQ_{\pi_i}(s,a) πi1(s)argmaxaQπi(s,a) 因此可以将Q函数看做一个表格Q-table得到Q函数也就得到Q表格。 对每一列取使得Q函数最大的动作即为最应该采取的动作。
通过argmax操作我们会得到更好或者不变的策略而不会使价值函数变差当改进停止后会得到一个最佳策略。策略确定后动作a确定Q函数 Q ( s , a ) Q(s,a) Q(s,a)就会变为价值函数 V ( s ) V(s) V(s) Q π ( s , π ′ ( s ) ) max a ∈ A Q π ( s , a ) Q π ( s , π ( s ) ) V π ( s ) Q_{\pi}\left(s,\pi^{\prime}(s)\right)\operatorname*{max}_{a\in A}Q_{\pi}(s,a)Q_{\pi}(s,\pi(s))V_{\pi}(s) Qπ(s,π′(s))a∈AmaxQπ(s,a)Qπ(s,π(s))Vπ(s)
进而得到贝尔曼最优方程Bellman optimality equation V π ( s ) m a x a ∈ A Q π ( s , a ) V_{\pi}(s) max_{a \in A}Q_{\pi}(s,a) Vπ(s)maxa∈AQπ(s,a)
贝尔曼最优方程表明最佳策略下的一个状态的价值必须等于在这个状态下采取最好动作得到的回报的期望。 当马尔可夫决策过程满足贝尔曼最优方程的时候整个马尔可夫决策过程已经达到最佳的状态。
当整个状态已经收敛后我们得到最佳价值函数后贝尔曼最优方程才会满足。满足贝尔曼最优方程后我们可以采用最大化操作即。 公式 1 V ∗ ( s ) m a x a Q ∗ ( s , a ) 公式1V^{*}(s) max_{a}Q^{*}(s,a) 公式1V∗(s)maxaQ∗(s,a)
Q函数的贝尔曼方程如下 公式 2 Q π i ( s , a ) R ( s , a ) γ ∑ s ′ ∈ S p ( s ′ ∣ s , a ) V ∗ ( s ′ ) 公式2Q_{\pi_i}(s,a) R(s,a) \gamma\sum{ \atop s \in S}p(s|s,a)V^{*}(s) 公式2Qπi(s,a)R(s,a)γ∑s′∈Sp(s′∣s,a)V∗(s′)
将公式1代入公式2即可得到Q函数之间的转移。将公式2代入公式1即可得到价值函数之间的转移。 价值迭代
策略迭代比价值迭代更快地接近最优解 基本概念 有模型算法状态转移概率已知例如动态规划 免模型算法大部分情况下对于智能体来说环境是未知的即状态转移概率未知
除了动态规划之外基础的强化学习算法都是免模型的。
预测免模型情况下去近似环境的状态价值函数。主要目的是估计或计算环境中的某种期望值比如状态价值函数 V ( s ) V(s) V(s)或动作价值函数 Q ( s , a ) Q(s,a) Q(s,a)。
控制目标则是找到一个最优策略该策略可以最大化期望的回报。换句话说你不仅想知道按照某种策略你的预期得分是多少还想知道如何选择动作以最大化这个得分。
控制问题通常涉及
策略评估policy evaluation策略改进policy improvement 在实际应用中预测和控制问题经常交织在一起。例如在使用 Q-learning一种免模型的控制算法时我们同时进行预测更新 Q值和控制基于Q值选择动作。之所以提到这两个概念是因为很多时候我们不能一蹴而就解决好控制问题而需要先解决预测问题进而解决控制问题。 什么情况下MDP是已知的即奖励函数R和状态转移函数P被提供给智能体时。
因此可以基于策略评估和策略改进来计算出最优策略和最优状态价值函数。 Model-free RL
背景策略迭代和价值迭代需要用到MDP但在现实生活中MDP往往不已知或者较复杂。下图是有模型方法。 Model-free 方法通过智能体与环境交互得到一系列轨迹基于这些轨迹计算状态和策略。 蒙特卡罗 这里提供一种增量求均值的方法现在时刻的均值可以和上一时刻的均值建立联系。这种方法可以应用到增量求状态价值函数V上。 Temporal-DifferenceTD
结合了MC和DP的方法
免模型通过bootstrapping可以从不完整回合中学习可以在不完整的环境上学习
TD(0)
TD target sample bootstrapping TD learning只往前走了一步就开始更新V而MC需要走完一个轨迹
TD(n)
往前走n步再更新通过步数来调整。当步数无穷大时TD target变为MC target 最右下角是穷举法TD在广度增加就变为了DP在深度增加就变为了MC。
策略迭代分两步
计算状态价值函数V根据v计算q。通过greedy更新策略
但计算Q需要奖励函数和状态转移矩阵但在MDP未知的情况下无法计算。
因此采用广义的策略迭代。通过MC来计算Q函数
