重新学习强化学习--数学理论_迭代法 rm算法

感谢up主提供的学习视频：
【【强化学习的数学原理】课程：从零开始到透彻理解（完结）】

文章脉络:

第一课

1. 奖励折扣率γ

1. if γ is close to 0, then the user put more emphasis on the reward obtained in the near future. The resulting policy would be short-sighted.
2. If γ is close to 1, then the agent put more emphasis on the far future rewards. In this case, the resulting policy would dare to take risks of getting negative rewards in the near future.

2. Markov decision processes (MDP)

1. Sets
   
2. Model:
   
3. Policy: at state s, the probability to choose action a is $\pi (a|s)$
4. Markov property:memoryless property
   

第二课：贝尔曼公式

1. 简单例子

直观理解：

根据以上策略写出所有的return值

矩阵表示：


这样就根据Bootstraping的一个例子求得到了向量v，上述v的公式也是一个简单的贝尔曼公式！

2. State Value

we define the mean of all possible returns starting from a state as the state value.

注意，他们都是随机变量，同时选定一个action后，获得的reward是记做Rt+1（和有些资料不同）。然后，可以定义discount return：Gt：

当确定一个状态s后，根据不同的action，有不同的return，然后就可以计算期望或平均：

随机性

随机性有两个来源：策略函数与状态转移函数。（大写字母表示随机变量）

• 动作的随机性来自于随机决策。
• 状态的随机性来自于状态转移函数。当状态 s 和动作 a 都被确定下来，下一个状态仍然有随机性。环境（比如游戏程序）用状态转移函数 p(s ′ |s,a) 计算所有可能的状态的概率，然后做随机抽样，得到新的状态。

注意，为什么Gt是个随机变量：Gt取决于未来很多步的奖励，当然具有随机性。

3. 贝尔曼公式的推导

1. 对第一项展开：
   
2. 开展第二项：
   
3. 合并
   
4. 理解
   

4. 贝尔曼公式的矩阵向量形式

1）表达

Rewrite the Bellman ：

第一项可以理解成及时奖励的一个期望；第二项也是消去action，从s到s’的概率的期望（under policy
π），也就是说这个表达式是计算给定的一个策略下，对应的state value的值，因此计算state value也可以评价当前策略好还是不好。紧接着：

2）求解State Value

解析解：

迭代法求解：

5. 贝尔曼公式-Action Value

1. 定义假设我们已经观测到状态 st，而且做完决策，选中动作at,$G_t$中的随机性来自于 t + 1 时刻起的所有的状态和动作,关于变量 S t+1 ,A t+1 ,··· ,S n ,A n 求条件期望于是定义：（注意，都是在策略π的前提下计算的）
   
2. 与state value的关系
   根据state value的定义，易得以下等式：
   
   因此：
   
   继续回忆Vπ的定义，并将上式关联起来：
   
   因此，又得到了Action Value的另一个表示式：
   
   观察上面两个式子，于是有一下结论：
   • one shows how to obtain state values from action values,
   • another one shows the reverse that is how to obtain action values from state values.

第三课-贝尔曼最优公式

1. Action Value改进策略？

以下是一个简单例子。

对于每个状态都预定义了一个策略π，因此可以计算state和action value：

可以看到a3下的action value值是最大的，因此可以改进原有策略（在s1下选择a2），选择a3为动作。注意，这里s2，s3情况下的策略是最优的，所有改进策略一定是有效的，但可以证明，无论后面的策略是否最优，都可以经过action value的迭代最终达到最优策略。

2. 最优贝尔曼公式BOE

1. 先给出公式：
   where v(s),v(s’ ) are unknowns.
2. 求解前的例子
   
   
   即，将权重系数全部分配给最大的$q(s,a)$.因此，可以推理得出贝尔曼最优公式变形：
   
   
3. Matrix-vector form of the BOE（先记住）

求解BOE

1）不动点和Contraction mapping

2）Contraction mapping theorem

For any equation that has the form of x = f(x) where x and f(x) are real vectors, if f is a contraction mapping, then

因此根据Contraction mapping theorem可以得到迭代求解算法可写作：

3）求解

贝尔曼最优公式就是满足Contraction Mapping（证明略）

举个例子如下：
先根据初始状态的vk和策略计算q table，然后由argmax得到下一个策略π*，根据上面的公式计算得到vk+1，然后计算


（注意，上面的π表示策略，相当于是s1下只会选择动作ar，概率值为1）
然后继续迭代：

最终的策略会成为：

贝尔曼最优公式是一个特殊的贝尔曼公式

3）贝尔曼最优策略

1. 关于γ的作用
   γ越大agent越重视未来的收益，即使当前的reward小一点，但总体来看回报更大；γ越小agent越短视，当γ=0时，即agent只会根据即使奖励进行take aciton
2. 关于reward的设置
   • 对reward加上系数和偏置不影响最终的最优策略；
   • reward设为0时，由于0<γ<1，因此agent不会在一个状态内反复横跳；
3. 总结
   
   

第四课：值迭代和策略迭代（Model Based）

1. 值迭代

decompose every iteration into two steps：

1. The first step in every iteration is called policy update
   
2. The second step is called value update
   

其中，$v_k(s^{\prime })$的意思是从状态s下采用动作a时到达的状态记做s’。

2. 策略迭代

定理：（证明见书）

定理说明了${\pi }_{k+1}$ is better than ${\pi }_k$

---

3. 两个迭代算法的区别

• 策略迭代寻找最优策略，而值迭代寻找最优值函数。
• 策略迭代在每次迭代中需要执行策略评估和策略改进两个步骤，而值迭代只需执行值迭代更新一个步骤。
• 策略迭代通常收敛比较快（因为要算无穷多步v值才能收敛），但每次迭代的计算开销较大。值迭代可能需要更多的迭代步骤，但每次迭代的计算开销较小。

在实际应用中，选择策略迭代还是值迭代取决于问题的复杂性、计算资源和收敛速度的要求。通常情况下，值迭代更适合在状态空间较小且计算资源有限的情况下使用，而策略迭代适用于状态空间较大且计算资源较充足的情况。

4. Truncated policy iteration截断策略迭代

在上图中，Value iteration直接求得了v1的值，而在Policy iteration需要迭代无穷多步才收敛到v1，将Policy iteration的value update公式按迭代次数写出来如下：

而Truncated policy iteration算法就是取其中的一步的v值，作为v1的值！

第五课：蒙特卡洛方法（Model Free）

2023年8月2日15:43:26

1. MC Basic

一句话解释，就是基于大数定律。而Model-based很多是需要模型的具体设置的，比如转移概率、概率分布等。例如在 policy improvement中：

It can be seen from the above equation that $q_{\pi k}(s,a)$ is the core.而上面的公式依赖于 system model {$p(r|s,a)$,$p(s^{\prime }|s,a)$}.

2. The simplest MC learning algorithm

1）分析

采用MC算法计算 $q_{\pi k}(s,a)$。

Suppose there are n episodes and denote the return of the ith episode as $g^{(i)}(s,a)$.$g^{(i)}(s,a)$就是Gt的一个随机采样。 Then, $q_{\pi k}(s,a)$ can be approximated as:
也就是说Model-free的方法就需要data，在RL中称之为Experience。

2）算法

注意，在此算法中，直接计算得到了action value；而在policy iteration中是先计算state value然后计算得到action value。
例子：

由于这里的策略和环境转移都是确定的，因此只需要采样一次就能确定$q_{\pi k}(s,a)$的值，这里拿s
1举例计算：

---

关于 Episode length的设置，理论上应该是无穷大的（agent到达目标点后选择action为不动），但实际中需要一个确切的值，值越大越接近最优的策略，此时对应的state value也是最终的值。当 Episode length从1开始增大时，会发现以target目标点为中心扩大，附近的策略会依次变好。

3. MC Expering Starts算法

为了避免一个eposide的数据只利用一次（从哪个(s,a)pair出发就只计算该sa的action value）造成的数据利用不高效的问题，采用类似截断的方法，对此eposide中间的(s,a)pair进行计算。如下图所示：

伪代码：

注意，t是反着计算的，有利于直接利用r+γGt的公式计算得到前面的Return值。

---

但这种方法无法保证截断后拿去计算的eposide是最优的，是否漏掉最优的action。It requires generating sufficiently many episodes starting from every state-action pair.

最重要的是在MC Basic or MC Exploring Starts算法中，都需要从每个（s，a）pair出发得到一个eposide，这被称之为Exploring Starts条件。

4. Soft Policy

1）算法

前面采用的都是greedy的策略，因此结果一定是determinal，而后面的ε-greedy是stochastic的策略，也是属于soft policy。A policy is soft if the policy has a positive probability to take any action at any state.这也就弥补了前面两个算法可能不能找到所有sa pair的缺点，并且不用满足Exploring Starts条件，因为由于随机性的策略，一条trajectory基本会覆盖所有的sa pair。

|A(s)| denotes the number of actions associated with s。此公式可以保证greedy action一定会大于other action。

在之前的MC Basic or MC Exploring Starts算法中：（where Π denotes the set of all possible policies.）

而在本算法中改成了：（Πε denotes the set of all ε-greedy policies with a fixed value of ε）


注意，用every-visit strategy比较好一点。

2）例子

在不同ε设置下，观察action value的值：

注意两个结论或者说现象：

1. when the value of ε increases, the state values of the ε-greedy policies diverge from the optimal ones.
   ε增大到0.5时，target的value居然还是最小的。这是因为有随机性的存在，target处四周都是forbiden，所以导致它本身的值也很小；
2. consistent性质。最开始ε=0.1时，可以发现最终的策略取最大的那个action时，得到的就是最优策略的action；而随着ε的增大，两者的策略不再相关，因此ε不能设置太大！

第六课：随机近似和随机梯度

1. Iterative mean estimation

关于求平均，之前是采用下面的公式：

它的问题在于每次都要重新求和，因此下面推导出一种增量式的算法（迭代）：令

---

Furthermore, consider an algorithm with a more general expression:
Iterative mean estimation是一个特殊的RM算法！（证明见下）

2.Robbins-Monro（RM）Algorithm

• RM算法是Stochastic approximation（SA）随机近似的开创性工作；
• 最著名的SDD算法也是RM算法的一种特殊形式；

关于求解方程$g(w)=0$，此时我们不知道g(w)的具体表达式，如果有一个神经网络可以拟合g(w)，我们可以将输入w看做方程的解，输出y需要等于0！！

1）算法

（ak is selected to be ak = 1/k）

2）Robbins-Monro Theorem

很显然$a_k$满足这样的条件。
Application to mean estimation：
在不知道X的统计特性下，求解w的值！

注意，这里$g(w,\eta ）$的推导后面直接把g(w)=0代入，然后只剩个η！！于是代入RM算法公式，即推导出了mean estimation公式。

3. Stochastic gradient descent（SGD）

考虑下面的优化问题：(X是一个随机变量)

1） gradient-descent algorithm(GD)

采用梯度下降的方法求解优化问题：

然而， the distribution is often unknown in practice.

2） batch gradient descent (BGD)

利用蒙特卡洛方法的思想，将GD算法中的期望改成采样求平均值，于是得到：

The problem of the BGD algorithm in is that it requires all the samples in each iteration.

3）stochastic gradient descent（SGD） algorithm

可以看做是BGD算法中的n=1的情况下得到SGD算法，相当于只采样一次。

注意，这里原本$f()$里面的X改成了一次采样值$x_k$

---

SGD也是一种特殊RM算法！证明如下，以求mean estimation的列子说明：

---

4. Convergence pattern of SGD

有以下结论：（具体证明见书上）
δ表示 relative error between the stochastic and batch gradients:

• when |wk − w∗ | is large, δ k is small. In this case, the SGD algorithm behaves like the gradient descent algorithm and hence w k approach w∗ quickly.
• when w k is close to w∗ , the relative error δk may be large and the convergence exhibits more randomness.

5. A deterministic formulation of SGD

前面介绍的SGD中都包含一个随机变量在里面，One may often encounter a deterministic formulation of SGD without involving any random variables.该优化问题可以写成：

注意，这里的xi是一组数的集合，并不涉及随机变量。然后使用GD算法求解：

若此时只取一个值，得到：

思考：这个算法是不是SGD呢？抽取的这个值是按某种顺序拿还是随机取呢？能不能重复拿呢

---

强行引入一个随机变量X:

此时就能使用SGD算法了，刚好就是对应前面的算法公式！同时，xi的抽取是需要满足在这个取值集合里面均匀分布的，因此是可能抽取多次的。

6. BGD, SGD, and Mini-batch GD

其中，Ik is a subset of {1,…,n} with the size as |Ik | = m.
注意：

• MBGD是介于BGD（n取所有的sample）和SGD（n=1）之间的。
• m=n时，MBGD并不完全等价于BGD，因为BGD是用直接用所有的sample，而MBGD是采样n个sample值。

---

收敛性展示：

可以看到，mBGD中的m值越大，收敛速度越快，但SGD依旧可以收敛的。