cs234-4: SARSA、Q-learning、On policy 和off policy简单理解

Sheldon Zheng2022-11-162024-09-02

Lecture 4

Epsilon greedy

仔细想了想贪心算法，回顾一下并没有那么简单。贪心算法的定义是：

\[ \begin{equation} \pi(a \mid s)= \begin{cases}a & \text { with probability } \frac{\epsilon}{|A|} \\ \arg \max _a Q^\pi(s, a) & \text { with probability } 1-\epsilon\end{cases} \end{equation} \]

也就是使用一个小的概率\(\epsilon\)来决定是探索还是深挖，即以\(\epsilon\) 的概率进行随机动作探索，从而获得那些潜在的可以带来更高未来回报的动作（当前一步不可见，但是在后续步骤中有可能拥有更多回报，也就是潜力更大），以1-\(\epsilon\) 的概率选择最大Q值的动作作为策略更新。

贪心算法是具有递增特性的，即如果对一个本身就是贪心算法进行贪心行为，那么可以得到其递增性，这里不容易想象到具体的案例，但是可以用公式表达：

\[ \begin{aligned} Q^{\pi_i}\left(s, \pi_{i+1}(s)\right) &=\sum_{a \in A} \pi_{i+1}(a \mid s) Q^{\pi_i}(s, a) \\ &=\frac{\epsilon}{|A|} \sum_{a \in A} Q^{\pi_i}(s, a)+(1-\epsilon) \max _{a^{\prime}} Q^{\pi_i}\left(s, a^{\prime}\right) \\ &=\frac{\epsilon}{|A|} \sum_{a \in A} Q^{\pi_i}(s, a)+(1-\epsilon) \max _{a^{\prime}} Q^{\pi_i}\left(s, a^{\prime}\right) \frac{1-\epsilon}{1-\epsilon} \\ &=\frac{\epsilon}{|A|} \sum_{a \in A} Q^{\pi_i}(s, a)+(1-\epsilon) \max _{a^{\prime}} Q^{\pi_i}\left(s, a^{\prime}\right) \sum_{a \in A} \frac{\pi_i(a \mid s)-\frac{\epsilon}{|A|}}{1-\epsilon} \\ &=\frac{\epsilon}{|A|} \sum_{a \in A} Q^{\pi_i}(s, a)+(1-\epsilon) \sum_{a \in A} \frac{\pi_i(a \mid s)-\frac{\epsilon}{|A|}}{1-\epsilon} \max _{a^{\prime}} Q^{\pi_i}\left(s, a^{\prime}\right) \\ & \geq \frac{\epsilon}{|A|} \sum_{a \in A} Q^{\pi_i}(s, a)+(1-\epsilon) \sum_{a \in A} \frac{\pi_i(a \mid s)-\frac{\epsilon}{|A|}}{1-\epsilon} Q^{\pi_i}(s, a) \\ &=\sum_{a \in A} \pi_i(a \mid s) Q^{\pi_i}(s, a) \\ &=V^{\pi_i}(s) \end{aligned} \]

值得注意的是第一个\(Q^{\pi_i}\left(s, \pi_{i+1}(s)\right)\) 中的动作使用的是贪心算法下的Q值代入使用贪心算法选择到的动作，求得该Q值大于等于贪心策略下的状态值，从而证明贪心算法是递增的

Now from the policy improvement theorem, we have that \(Q^{\pi_i}\left(s, \pi_{i+1}(s)\right) \geq V^{\pi_i}(s)\) implies \(V^{\pi_{i+1}}(s) \geq\) \(V^{\pi_i}(s)\) for all states \(s\), as desired.

SARSA

Q-learning

二者区别

SARSA和Q-learning的区别非常简单，就是在第二部对策略评估的方式不一样。网上查了一下，发现一群人在那翻译教材，还举什么走迷宫的例子，看的眼都要花，就是因为策略评估的方式不一样,Q-learning和sarsa都是在使用e-greedy的行动策略所得到的的动作后得到新的状态 \(s'\) 和回报 \(r\) ，不同的是Q-learning不管三七二十一直接在新的状态\(s'\)中选择最大的Q值来更新Q-table，而Sarsa则依旧使用e-greedy来更新Q-table，即在状态\(s'\)上先把所有的动作的Q值算出来，然后用e-greedy方法依照Q值和概率\(\epsilon\) 选取一个动作\(a'\)，再用这个动作的Q值更新下Q-table。知乎果然是装逼为主，感觉这个图片的作者自己就没弄懂两者的区别，就跑出来写文章讲区别。