强化学习复习笔记#2

蒙特卡罗方法（Monte Carlo Methods）

Policy evaluation:

我们知道：

\[
v_{\pi} (s) \doteq \mathbb{E}_{\pi}[G_t | S_t = s] = \mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \bigg| S_t = s\right],\mbox{ for all } s \in \mathcal{S}
\]

根据大数定律，我们可以通过对状态 \(s\) 之后观测到的回报求均值，来估计值函数。随着观测到的回报越来越多，它的均值会收敛到期望值，也就是我们需要的 \(v_{\pi} (s)\)。

First-visit MC method：用第一次出现状态 \(s\) 后产生的回报的均值来估计 \(v_{\pi} (s)\)

Every-visit MC method：用所有出现状态 \(s\) 后的回报的均值来进行估计 \(v_{\pi} (s)\)

Policy improvement:

我们使用贪婪策略：

\[
\pi_{k+1}(s) := \underset{a}{\mathrm{argmax}} \ q_{\pi_k}(s, a)
\]

Incremental Implementation

直接计算平均值比较麻烦，所以我们使用递增式的方法：

\[
\begin{equation}
\begin{split}
Q_{n+1} &= \frac{1}{n+1} \sum_{i=1}^{n+1}g_i \\
&= Q_n + \frac{1}{n+1} (g_n - Q_n)
\end{split}
\end{equation}
\]

其中 \(g_i\) 表示的是第 \(i\) 次迭代的样本回报。

时序差分学习（Temporal Difference Learning）

\[
V_{n+1}(s) \approx V_n(s) + \alpha [r(s, a) + \gamma V_n(s’) - V_n(s)]
\]

\[
Q_{n+1}(s, a) = Q_n(s, a) + \alpha [r(s, a) + \gamma Q_n(s’, a’) - Q_n(s, a)]
\]

其中，\(r(s, a) + \gamma Q_n(s’, a’) - Q_n(s, a)\) 是 TD error，\(r(s, a) + \gamma Q_n(s’, a’)\) 是 TD target。\(\alpha\) 是学习率，学习率高的时候学习更快，但是会增加更新的权重，有可能造成估计值（\(Q\)）的震荡。

使用 TD error 进行估计的过程即是 policy evalution 部分。至于 policy improvement 则和前面的一样。

TD VS MC

TD can learn from incomplete sequences
MC needs complete sequences
TD works in continuing environments
MC only works for episodic environments

Sarsa

给定一个元组 \((S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})\)，我们根据 \(Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha (R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t))\) 来进行更新。

𝜀 - greedy policy:

With probability 1 - 𝜀 : A = \(a^* \in \underset{a}{\mathrm{argmax}}\ Q(s, a)\)
With probability 𝜀 : A = an action uniformly randomly selected from all other actions available at state s

为了让 Sarsa 最终收敛到最优值，我们可以使 𝜀 逐渐接近 0。