做广告公司网站建设,win7自己电脑做网站,wordpress自带重定向,英语网站源码文章目录 Reinfocement Learning一、基本概念二、贝尔曼公式#xff08;bellman equation#xff09;2.1 为什么return重要2.2 state value function的定义2.3 贝尔曼公式推导2.4 如何求解贝尔曼公式2.5 Action value的定义 三、贝尔曼最优公式#xff08;bellman optimalit… 文章目录 Reinfocement Learning一、基本概念二、贝尔曼公式bellman equation2.1 为什么return重要2.2 state value function的定义2.3 贝尔曼公式推导2.4 如何求解贝尔曼公式2.5 Action value的定义 三、贝尔曼最优公式bellman optimality equation3.1 最优策略和公式推导3.2 公式求解3.3 最优策略的有趣性质 四、值迭代和策略迭代Value Iteration Policy Iteration4.1 值迭代算法4.2 策略迭代算法4.3 二者区别4.4 截断策略迭代算法Truncated Policy Iteration 五、蒙特卡洛方法Monte Carlo Learning5.1 有模型与免模型强化学习5.2 MC Basic算法5.3 MC Exploring Starts算法5.4 MC Epsilon-Greedy算法 Reinfocement Learning
一、基本概念 强化学习Reinfocement Learning智能体agent可以在与复杂且不确定的环境进行交互时尝试使所获得的奖励最大化的算法寻找最优策略。 动作action环境接收到的智能体基于当前状态的输出即智能体采取什么动作。 状态state智能体从环境中获取的状态。 状态转移state transition采取动作智能体从一个状态转变到另一个状态。 策略policy对每个状态而言智能体会用策略来选取下一步的动作。 随机性策略stochastic policy π \pi π 函数即 π ( a ∣ s ) p ( a t a ∣ s t s ) \pi(a|s)p(a_ta|s_t s) π(a∣s)p(ata∣sts)。输入一个状态 s s s输出一个概率。 确定性策略deterministic policy智能体直接采取最有可能的动作。 奖励reward智能体从环境中获取的反馈信号这个信号指定了智能体在某一步采取了某个策略以后是否得到奖励以及奖励的大小。 轨迹trajectory状态—动作—奖励链 回报return奖励的逐步叠加。如上述 t r a j e c t o r y trajectory trajectory 的 r e t u r n return return 为 0 0 0 1 1 00011 00011 折扣回报discounted return引入了一个折扣因子discounted rate γ \gamma γ则折扣回报 G t G_t Gt为 G t r t 1 γ r t 2 γ 2 r t 3 γ 3 r t 4 . . . γ T − t 1 r T G_tr_{t1}\gamma r_{t2}\gamma^2 r_{t3}\gamma^3 r_{t4}...\gamma^{T-t1}r_T Gtrt1γrt2γ2rt3γ3rt4...γT−t1rT 有些马尔可夫过程带环它并不会终结我们想避免无穷的奖励 把折扣因子设为0我们就只关注当前的奖励把折扣因子设为1对未来的奖励并没有打折扣未来获得的奖励与当前获得的奖励是一样的 episodeagent在环境里面执行某个策略从开始到结束到达terminal state这一过程。 马尔可夫决策过程Markov decision process MDP key elements of MDP 集合sets state状态的集合 S S Saction动作的集合 A ( s ) A(s) A(s)即在状态 s s s 下智能体可采取的动作有哪些reward奖励的集合 R ( s , a ) R(s, a) R(s,a)即在当前状态 s s s 下采取动作 a a a 将会获得多少奖励 概率分布probabiliy distribution state transition probability在状态 s s s 下采取动作 a a a转移到下一状态 s ′ s s′ 的概率即 p ( s ′ ∣ s , a ) p(s|s,a) p(s′∣s,a)reward probability在状态 s s s 下采取动作 a a a获得奖励 r r r 的概率即 p ( r ∣ s , a ) p(r|s,a) p(r∣s,a) 策略policy在状态 s s s 下采取动作 a a a 的概率即 π ( a ∣ s ) \pi(a|s) π(a∣s) 马尔可夫性质Markov propertymemoryless property下一状态和奖励只跟当前状态和采取的动作有关跟之前所有的都无关。 p ( s t 1 ∣ a t 1 , s t , . . . , a 1 , s 0 ) p ( s t 1 ∣ a t 1 , s t ) p ( r t 1 ∣ a t 1 , s t , . . . , a 1 , s 0 ) p ( r t 1 ∣ a t 1 , s t ) p(s_{t1}|a_{t1},s_t,...,a_1,s_0)p(s_{t1}|a_{t1},s_t) \\ p(r_{t1}|a_{t1},s_t,...,a_1,s_0)p(r_{t1}|a_{t1},s_t) p(st1∣at1,st,...,a1,s0)p(st1∣at1,st)p(rt1∣at1,st,...,a1,s0)p(rt1∣at1,st)
如图为一个markov process而不是markov decision process因为policy已经确定 二、贝尔曼公式bellman equation
2.1 为什么return重要 r e t u r n return return 可作为评估策略好坏的依据。
由图可知 r e t u r n 1 r e t u r n 3 r e t u r n 2 return_1return_3return_2 return1return3return2故策略1是最好的策略2是最差的。
2.2 state value function的定义
折扣回报discounted return: G t r t 1 γ r t 2 γ 2 r t 3 γ 3 r t 4 . . . γ T − t 1 r T G_tr_{t1}\gamma r_{t2}\gamma^2 r_{t3}\gamma^3 r_{t4}...\gamma^{T-t1}r_T Gtrt1γrt2γ2rt3γ3rt4...γT−t1rT s t a t e v a l u e f u n c t i o n state \ value \ function state value function 就是折扣回报discounted return的期望。即从一个状态出发agent能获得的折扣回报的期望 v π ( s ) E [ G t ∣ S t s ] v_\pi(s)\mathbb{E}[G_t|S_ts] vπ(s)E[Gt∣Sts] 这是关于状态 s s s 的函数从不同的状态出发得到的 t r a j e c t o r y trajectory trajectory 是不同的 d i s c o u n t e d r e t u r n discounted\ return discounted return 的期望也是不同的 这是基于策略 π \pi π 的函数采取不同的策略得到的 t r a j e c t o r y trajectory trajectory 是不同的 d i s c o u n t e d r e t u r n discounted\ return discounted return 的期望也是不同的 当一个 s t a t e v a l u e f u n c t i o n state \ value \ function state value function 比较大时代表这个状态是比较有价值的因为从这个状态出发会得到更多的 r e t u r n return return r e t u r n return return 是由一条确定 t r a j e c t o r y trajectory trajectory 得到的而 s t a t e v a l u e state \ value state value 是从当前状态出发可能会得到多条 t r a j e c t o r y trajectory trajectory对其 r e t u r n return return 求平均 2.3 贝尔曼公式推导 E [ R t 1 ∣ S t s ] \mathbb{E}[R_{t1}|S_ts] E[Rt1∣Sts] 表示的是当前奖励的平均 E [ G t 1 ∣ S t s ] \mathbb{E}[G_{t1}|S_ts] E[Gt1∣Sts] 表示下一回报的平均
由此可得贝尔曼公式 贝尔曼公式就是 s t a t e v a l u e state \ value state value的表现形式贝尔曼公式描述了不同 s t a t e v a l u e state \ value state value 之间的关系对于状态空间中的所有状态均成立贝尔曼公式依赖于给定的策略 π \pi π这样才能求解计算状态价值函数的过程就是策略评估 p o l i c y e v a l u a t i o n policy \ evaluation policy evaluation其实直观上是非常好理解的因为 G t r t 1 γ r t 2 γ 2 r t 3 γ 3 r t 4 . . . γ T − t 1 r T r t 1 γ G t 1 G_tr_{t1}\gamma r_{t2}\gamma^2 r_{t3}\gamma^3 r_{t4}...\gamma^{T-t1}r_T r_{t1}\gamma G_{t1} Gtrt1γrt2γ2rt3γ3rt4...γT−t1rTrt1γGt1我要求 G t G_t Gt 的期望其实就是求即刻奖励的期望和下一折扣回报的期望。
2.4 如何求解贝尔曼公式 对于 n n n 个状态而言 用矩阵形式表示假设共有四个状态 例子 2.5 Action value的定义 s t a t e v a l u e state \ value state value 关注的是从一个状态出发 a g e n t agent agent 能获得的折扣回报的期望。它体现了每个状态的价值。 a c t i o n v a l u e action \ value action value 关注的是从状态出发采取某个 a c t i o n action action 能获得的折扣回报的期望。它体现了每个动作的价值。有如下数学定义 q π ( s , a ) E [ G t ∣ S t s , A t a ] q_\pi(s,a)\mathbb{E}[G_t|S_ts,A_ta] qπ(s,a)E[Gt∣Sts,Ata] 两者可以互相求解 因此上图有推导 三、贝尔曼最优公式bellman optimality equation
3.1 最优策略和公式推导
最优策略当一个策略 π ∗ \pi^* π∗ 的所有状态对应的 s t a t e v a l u e state \ value state value 值都大于其他任何一个策略时即 $v_\pi^*(s)v_\pi(s) $ 时称 π ∗ \pi^* π∗ 是最优策略。
贝尔曼最优公式就是当贝尔曼公式中的策略不再给定而是要求解采用什么策略是最优的一个过程知道了最优策略过后当然可以求出最优的 s t a t e v a l u e state \ value state value。贝尔曼最优公式就是当给定的策略为最优策略时的一个特殊的贝尔曼公式 假设所有 q ( s , a ) q(s,a) q(s,a) 已知时一定存在一个最大的 q ( s , a ) q(s,a) q(s,a) 我们想让 v ( s ) v(s) v(s) 最大那就是让最大的 q ( s , a ) q(s,a) q(s,a) 所占的权重最大而权重代表概率最大为1。所以采取的策略就是让 a c t i o n v a l u e action \ value action value 最大的 a c t i o n action action 发生概率为1此时得到的 s t a t e v a l u e state \ value state value 值即为 a c t i o n v a l u e action \ value action value。 以矩阵形式表示为 3.2 公式求解
基于 c o n t r a c t i o n m a p p i n g t h e o r e m contraction \ mapping \ theorem contraction mapping theorem 对任意状态 s s s都先给出一个估计值 v k ( s ) v_k(s) vk(s) k k k 表示迭代次数根据 a c t i o n v a l u e action \ value action value 公式可以求解出 q k ( s , a ) q_k(s,a) qk(s,a)根据 m a x max max 可以求解出 q k ( s , a ) q_k(s,a) qk(s,a) 对应的策略 π \pi π就是选择最大的 q k ( s , a ) q_k(s,a) qk(s,a) 的策略此时得到当前的最优策略 π ∗ \pi^* π∗将 m a x a q k ( s , a ) max_{a} \ q_k(s,a) maxa qk(s,a) 的值计算出来带入 v k 1 ( s ) v_{k1}(s) vk1(s)不断迭代至 v ∗ v^* v∗ 收敛即 v k ( s ) v_k(s) vk(s) 与 v k 1 ( s ) v_{k1}(s) vk1(s) 的差值很小时
例子 表格中存储的是 a c t i o n v a l u e action \ value action value此表即为 Q − t a b l e Q-table Q−table 第一轮迭代 k 0 k0 k0假设 v 0 ( s 1 ) v 0 ( s 2 ) v 0 ( s 3 ) 0 v_0(s_1)v_0(s_2)v_0(s_3)0 v0(s1)v0(s2)v0(s3)0下标0表示迭代次数 k k k可得表格 由表得到第一轮迭代的最优策略和最优 s t a t e v a l u e state \ value state value 第二轮迭代 k 1 k1 k1将第一轮的最优 s t a t e v a l u e state \ value state value 带入得到新的表格 由表得到第二轮迭代的最优策略和最优 s t a t e v a l u e state \ value state value 不断迭代下去直到第 k k k 轮的 v ∗ v^* v∗ 收敛可停止迭代得到最终的最优策略和最优 s t a t e v a l u e state \ value state value。
3.3 最优策略的有趣性质
影响最优策略的因素奖励 r e w a r d reward reward 和折扣因子 γ \gamma γ 会影响到最优策略
当奖励发生线性变化时最优策略并不会改变 Q Q Q为了寻找最短路径防止绕远路有必要将每走一步的 r e w a r d reward reward 设置为负数吗 A A A没有必要因为不仅是 r e w a r d reward reward 限制折扣因子也会限制绕远路意味着拿到奖励会打折的非常厉害为了获取最大 s t a t e v a l u e state \ value state value 肯定选近路。
贝尔曼最优公式一定存在解且解唯一最优策略不唯一最优 s t a t e v a l u e state \ value state value 唯一
四、值迭代和策略迭代Value Iteration Policy Iteration
二者都属于 d y n a m i c p r o g r a m m i n g dynamic \ programming dynamic programming 的方法或者说是 m o d e l − b a s e d model-based model−based 的方法
4.1 值迭代算法
其实就是贝尔曼最优公式的求解过程。 s t e p 1 p o l i c y u p d a t e step1policy \ update step1policy update
由前面的贝尔曼最优公式可知最优策略的数学表示为 a r g m a x a f ( a ) arg \ \underset {a}{max}f(a) arg amaxf(a) 表示 f ( a ) f(a) f(a) 取最大时 a a a 的值。故上述式子的含义为后面这一长串即 s t a t e v a l u e state \ value state value取最大值时所采取的策略即最优策略表示为 即采取的策略为选取对应 q k ( s , a ) q_k(s,a) qk(s,a) 最大的那个 a c t i o n action action概率为1。 s t e p 2 v a l u e u p d a t e step2value \ update step2value update
此时策略已定贝尔曼最优公式转变为贝尔曼公式 得到最优 s t a t e v a l u e state \ value state value就是最大的 a c t i o n v a l u e action \ value action value因为最优策略选取最大 a c t i o n v a l u e action \ value action value 对应 a c t i o n action action 的概率为1所以只有一条 t r a j e c t o r y trajectory trajectory 概括为先定 v k v_k vk 求 q k q_k qk 再求 π k 1 \pi_{k1} πk1 最后得到 v k 1 v_{k1} vk1迭代至其收敛。 完整例子 表格中存储的是 a c t i o n v a l u e action \ value action value此表即为 Q − t a b l e Q-table Q−table 第一轮迭代 表中状态为 s 1 s_1 s1 时选的动作 a 3 a_3 a3 和 a 5 a_5 a5 得到的 a c t i o n v a l u e action \ value action value 值相同此时随机选择一个假设为 a 5 a_5 a5 得到新的策略图 第二轮迭代 得到新的策略图 继续往下迭代知道 ∣ ∣ v k − v k 1 ∣ ∣ ||v_k-v_{k1}|| ∣∣vk−vk1∣∣ 很小时即收敛到 v ∗ v^* v∗ 时停止。
4.2 策略迭代算法 P E P o l i c y E v a l u a t i o n PEPolicy \ Evaluation PEPolicy Evaluation P I P o l i c y I m p r o v e m e n t PIPolicy \ Improvement PIPolicy Improvement s t e p 1 p o l i c y e v a l u a t i o n step1policy \ evaluation step1policy evaluation
给定策略求解贝尔曼方程不断迭代 j j j 轮至 v π k v_{\pi_k} vπk 收敛 s t e p 2 p o l i c y i m p r o v e m e n t step2policy \ improvement step2policy improvement
根据上一步得到的 s t a t e v a l u e state \ value state value 求解贝尔曼最优公式更新策略 同值迭代一样选取最大 a c t i o n v a l u e action \ value action value 对应 a c t i o n action action使其概率为1更新策略 简单例子 第一步策略评估即求解贝尔曼公式 因为例子比较简单可以直接联系方程组解出 如果当式子较难解出一般采用迭代的算法让其收敛即当 v π k ( j 1 ) v_{\pi_k}^{(j1)} vπk(j1) 与 v π k ( j ) v_{\pi_k}^{(j)} vπk(j) 差值很小时 第二部策略优化将上述得到的 s t a t e v a l u e state \ value state value 带入此时就跟值迭代算法一样了 得到新的策略 4.3 二者区别 上图中当 v v v 的下标为 π \pi π 时表示的是由确切的策略求解出的 s t a t e v a l u e state \ value state value当 v v v 的下标为数字时表示的只是迭代过程中的一个中间量是用这个中间两来不断逼近真正的 s t a t e v a l u e state \ value state value可以看作是未收敛的 s t a t e v a l u e state \ value state value。
策略迭代是由初始时给定的策略来计算出 s t a t e v a l u e state \ value state value而值迭代是直接给出一个估计值之后求解贝尔曼最优方程时的步骤时策略迭代带入的是由确切的策略通过求解贝尔曼方程出的 s t a t e v a l u e state \ value state value而值迭代带入的是未收敛的 s t a t e v a l u e state \ value state value。相当于在每一轮迭代开始前策略迭代多了一步求 s t a t e v a l u e state \ value state value 的过程这个过程也是一个迭代的过程。
4.4 截断策略迭代算法Truncated Policy Iteration 五、蒙特卡洛方法Monte Carlo Learning
5.1 有模型与免模型强化学习
有模型model-based强化学习 a g e n t agent agent 通过学习状态的转移来采取动作。具体来说当 a g e n t agent agent 知道状态转移函数和奖励函数即 M D P MDP MDP 中的两个概率分布后它就能知道在某一状态下执行某一动作后能带来的奖励和环境的下一状态。
免模型model-free强化学习 a g e n t agent agent 没有直接去估计状态的转移也没有得到环境的具体转移变量它通过学习状态价值函数和策略函数进行决策。免模型强化学习没有对真实环境进行建模 a g e n t agent agent 只能在真实环境中通过一定的策略来执行动作等待奖励和状态迁移然后根据这些反馈信息来更新动作策略反复迭代直到学习到最优策略。
用通俗的话解释大数定理在不知道模型参数的情况下经过多次实验将所得参数的平均近似为期望。大数定理是免模型的而蒙特卡洛估计也是免模型的二者不谋而合。
5.2 MC Basic算法
如何做到从有模型到免模型的转变或者说如何在不知道两个概率分布的条件下得到 a c t i o n v a l u e action \ value action value 进而更新策略呢
为了回答上述问题我们需要借助 p o l i c y i t e r a t i o n policy \ iteration policy iteration。
即问题转变为如何把 p o l i c y i t e r a t i o n policy \ iteration policy iteration 这种 m o d e l − b a s e d model-based model−based 算法转变为 m o d e l − f r e e model-free model−free 的算法呢
算法中涉及两个概率分布的只有 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) 回到 q π k ( s , a ) q_{\pi_k}(s,a) qπk(s,a) 最初始的定义 q π k ( s , a ) E [ G t ∣ S t s , A t a ] q_{\pi_k}(s,a)\mathbb{E}[G_t|S_ts,A_ta] qπk(s,a)E[Gt∣Sts,Ata]也是要求期望何不用蒙特卡洛估计呢
从 ( s , a ) (s,a) (s,a) 开始采取策略 π k \pi_k πk生成一个 e p i s o d e episode episode一个 e p i s o d e episode episode 的 r e t u r n return return 称为 g ( s , a ) g(s,a) g(s,a)。 e p i s o d e episode episode 长度的选取会影响到策略的选择 e p i s o d e l e n g t h episode \ length episode length 越大离目标越远的状态也能找到正确的策略。 g ( s , a ) g(s,a) g(s,a) 即为 G t G_t Gt 的一个采样sample对每一个 s s s 的每一个 a a a生成一系列 e p i s o d e episode episode对其每个 r e t u r n return return 相加求平均近似为 q π k ( s , a ) q_{\pi_k}(s,a) qπk(s,a)即 q π k ( s , a ) E [ G t ∣ S t s , A t a ] ≈ 1 N ∑ N i 1 g ( s , a ) q_{\pi_k}(s,a)\mathbb{E}[G_t|S_ts,A_ta]\approx \frac{1}{N}\underset{i1}{\overset{N} \sum} g(s,a) qπk(s,a)E[Gt∣Sts,Ata]≈N1i1∑Ng(s,a)更新策略
其实就是用蒙特卡洛估计来直接得到 q π k ( s , a ) q_{\pi_k}(s,a) qπk(s,a)然后进行 p o l i c y i m p r o v e m e n t policy \ improvement policy improvement。MC Basic算法需要采样的 e p i s o d e episode episode 过多效率efficiency较低。
为什么不用 v a l u e i t e r a t i o n value \ iteration value iteration 进行转换呢因为 v a l u e i t e r a t i o n value \ iteration value iteration 事先不知道策略也就无法生成 r e t u r n return return 作为采样结果。
例子 这个例子其实是有模型的但并不妨碍介绍蒙特卡洛的思想。以 s 1 s_1 s1 为例因为此时给定的策略概率都为1所以采样一次即可即使采样多次结果平均下来结果还是和采样一次一样。先是求状态 s 1 s_1 s1 每个动作对应的 a c t i o n v a l u e action \ value action value 然后根据 a c t i o n v a l u e action \ value action value 更新策略 5.3 MC Exploring Starts算法
核心思想在每个 e p i s o d e episode episode 中充分利用数据 现在要求得每一个 ( s , a ) (s,a) (s,a) 的 a c t i o n v a l u e action \ value action value 有两种方法一种是从 ( s ′ , a ′ ) (s,a) (s′,a′) 开始经历一个 e p i s o d e episode episode另一种是从别的 ( s , a ) (s,a) (s,a) 开始在其 e p i s o d e episode episode 中找到我需要的 ( s , a ) (s,a) (s,a)。但第二种方法是不确定会不会经过我需要的这样一个 ( s , a ) (s,a) (s,a) 的。
5.4 MC Epsilon-Greedy算法
如何确保MC Exploring Starts算法中提到的可以从别的 ( s , a ) (s,a) (s,a) 开始在其 e p i s o d e episode episode 中找到我需要的 ( s , a ) (s,a) (s,a) 呢
采用 ϵ − g r e e d y \epsilon-greedy ϵ−greedy 策略保证在选择 a c t i o n action action 时是 s t o c h a s t i c stochastic stochastic 的这样做能保证每个 ( s , a ) (s,a) (s,a) 都有概率能取到即使概率较小较大的概率还是取最大的 a c t i o n v a l u e action \ value action value 对应的 a c t i o n action action 保证其有 e x p l o r a t i o n exploration exploration 。 如何将其与前面所讲的两个算法结合起来。其实就是在求出了 q π k ( s , a ) q_{\pi_k}(s,a) qπk(s,a) 后进行 p o l i c y i m p r o v e m e n t policy \ improvement policy improvement 时采用 ϵ − g r e e d y \epsilon-greedy ϵ−greedy 策略 这样就可以做到从一个或几个 ( s , a ) (s,a) (s,a) 出发得到的 e p i s o d e episode episode 能覆盖到几乎所有的 ( s , a ) (s,a) (s,a)。
注意 ϵ \epsilon ϵ 的值不宜过大
