强化学习的数学原理-第5课
2025年11月24日
14:49
(在不知道模型表达式的情况下求最优policy)
当我们不知道模型的具体表达式时，需要进行采样，来估计
即用多次采样的平均值，作为X的期望的估计，这就是morto carlo estimation 的思想
这个估计值准不准确 呢？可以由大数定理回答：
是一个随机变量，作为E[X]的估计量，这个估计是无偏估计，即E[x_bar]=E[x]，且采样数量越多，这个估计的方差越小。
由于state value and action valueare defined as expectations of random variables!，所以我们可以
用这个方法进行估计。
当我们不知道Model时，无法通过公式，上图中的expression 1来计算得到state action value q，
可以通过q的原始定义，q的原始定义就是Gt的期望，这个期望可以通过采样得到的均值来估计。
MC Basic
════════════════════════════════════════════════════════════════════════════════════════════════════
Why does MC Basic estimate action values instead of state values?
policy iteration中第一步policy evaluation中是求v，而不是q，为什么MC估计时不估计v，而
直接估计q呢？因为v没啥用，q有用，q才是用来确定最优policy时用到的。
That is because state values cannot be used to improve policies directly. When
models are not available, we should directly estimate action values.
Since policy iteration is convergent, the convergence of MC Basic is also
guaranteed to be convergent given sucient episodes.
关于episode走多少步，不能太少，太少的话只有靠近target的状态才估计得准确 ，需要取一个合适的长度。
MC Exploring starts
════════════════════════════════════════════════════════════════════════════════════════════════════
上面的这个Naïve MC方法效率较低，可以有2个方面的优化，
1）如下图所示，从s1,a2出发的episode，在这个episode的过程中，还访问了其他的state action，
这相当于是从其他的state action出发的episode（但是步数变少了，但影响不大，反正是估计），
可以用来估计它们的q。
这样可以充分利用数据 ，有2种方法，一种是first visit(什么是
Visit: every time a state-action pair appears in the episode, it is called a visit
of that state-action pair.
)，也就是在一个episode中，只有第一次访问到某个state action时，用这个时候的q作为估计，
另一种是every visit，在一个episode中，每次访问到这个state action时，都用于这个state action的q的
估计（取平均）。
2）另一个可以优化的地方，Navie MC 的做法是
in the policy evaluation step, to collect all the episodes
starting from a state-action pair and then use the average return to
approximate the action value.。我们可以在得到一个episode的结果后，就进行策略的更新。
其实类似移动平均的思想！！！！
下图是MC Exploring starts的流程
对每一个episode：
1）随机选择一个state action pair s0,a0（确保每个pair都能被选中），follow当前的policy，得到一条trajectory
2）对这个trajectory，从后往前（主要 是为了计算方便，工程上的小小变化 ，实际的算法原理仍然是从前往后进行这个trajectory，得到这个state action pair的return），每个state action pair 的g等于ϒg+r_t+1，如果这个state action pair 是第一次出现
（first visit的策略），就记录下这个state action pair的g，即这个episode的这个state action pair的
Returns（st, at），然后这个state aciton pair 的q就是所有episode的Returns（st, at）的平均值 。
有了新的q之后，就可以更新policy。
为什么叫Exploring starts?
1)Exploring指的是在每个episode时，确保所有的state action pair都能被选到，防止某个state action pair没有
访问到，影响最优策略
2）starts指的是我要得到state action pair 如s0,a0 的g，我有两种方法，一种是episode直接从s0,a0出发，另一种是
从别的state aciton pair出发 ，然后经过s0a0，starts就是第一种方法，因为这种方法能确定肯定访问到s0,a0，
第二种方法不一定能访问到s0,a0。
In practice, exploring starts is dicult to achieve. For many applications,
especially those involving physical interactions with environments, it is
dicult to collect episodes starting from every state-action pair.需要把机器人移到网格的多个位置，
设置程序等，比较麻烦。
MC without Exploring starts
════════════════════════════════════════════════════════════════════════════════════════════════════
那么如何去掉exploring starts这个条件呢？
答案是用soft policy，soft policy是stochastic的，因此可以保证所有的state action pair都会被采样到，而
不需要exloring starts。
What is a soft policy?
A policy is soft if the probability to take any action is positive.
Deterministic policy: for example, greedy policy
Stochastic policy: for example, soft policy
. Why introducing soft policies?
With a soft policy, a few episodes that are suciently long can visit every
state-action pair.
Then, we do not need to have a large number of episodes starting from every
state-action pair. Hence, the requirement of exploring starts can be removed.
soft policy就平衡了exploration和exploitation
MC Є-greedy和MC exploring starts的区别就是在做policy improvment时，不用greedy的策略
，而是用Є-greedy的策略
也就是MC exploring starts做policy imporvment时，是以1的概率选择最优action（q（s,a）最大的
那个action），而MC Є-greedy则是以Є 的概率选择最优action，MC exploring starts和
MC Є-greedy 更新策略时，最优action
是一样的，只是选择的概率不同。
Demonstrate the MC "-Greedy algorithm.
In every iteration, do the following:
In the episode generation step, use the previous policy generates a single
episode of 1 million steps! 一个episode足够长，有100w步
In the rest steps, use the single episode to update the policy.按照MC exploration starts一样的算法来更新策略
Two iterations can lead to the optimal "-greedy policy. 只需要2个episode即可收敛，因为每个episode的step足够长。
总结：MC Є-greedy的策略其实并不是最优的，因为最优的策略就是以概率1来选择最优action，只是为了避免
exploring starts这个条件而采取的折中做法。
Є不能太大，否则就和greedy得到的最优策略不一致了。实际 中，可以刚开始Є大一些，后面Є小一点（和学习率一样）