[RL Notes] 分幕式 Sarsa 的函数逼近

1. 函数逼近中的动作价值

  线性方法近似的价值函数为权重向量和特征向量的内积

\begin{equation}
v_\pi(s) \approx \hat{v}(s, \boldsymbol{\mathrm{w}}) \doteq \boldsymbol{\mathrm{w}}^\mathsf{T} \boldsymbol{\mathrm{x}} \tag{1}
\end{equation}

可以使用类似地形式估计动作价值函数,此时需要让特征能够表示动作,即

\begin{equation}
q_\pi(s, a) \approx \hat{q}(s, a, \boldsymbol{\mathrm{w}}) \doteq \boldsymbol{\mathrm{w}}^\mathsf{T} \boldsymbol{\mathrm{x}}(s, a) \tag{2}
\end{equation}

  构造特征来表示动作的方法之一是让每个动作使用相同的状态特征,然后将这些状态的特征堆叠起来。例如现有 $4$ 个特征和 $3$ 个动作

\begin{equation}
\boldsymbol{\mathrm{x}} = \begin{bmatrix}
x_0(s) \\
x_1(s) \\
x_2(s) \\
x_3(s)
\end{bmatrix} \\
\mathcal{A}(s) = \{\color{red}{a_0}, \color{green}{a_0}, \color{blue}{a_0}\}
\end{equation}

则构造的状态动作特征为

\begin{equation}
\boldsymbol{\mathrm{x}}(s, a) = \begin{bmatrix}
\color{red}{x_0(s)} \\
\color{red}{x_1(s)} \\
\color{red}{x_2(s)} \\
\color{red}{x_3(s)} \\
\color{green}{x_0(s)} \\
\color{green}{x_1(s)} \\
\color{green}{x_2(s)} \\
\color{green}{x_3(s)} \\
\color{blue}{x_0(s)} \\
\color{blue}{x_1(s)} \\
\color{blue}{x_2(s)} \\
\color{blue}{x_3(s)}\end{bmatrix}
\end{equation}

$\boldsymbol{\mathrm{x}}(s, a)$ 将 $4$ 个状态的特征重复堆叠了 $3$ 组,每一组对应一个动作。当一个动作发生时,只有该动作对应的状态特征被激活,其他状态特征置 $0$。例如选择动作 $a_0$ 时,有

\begin{equation}
\boldsymbol{\mathrm{x}}(s, a_0) = \begin{bmatrix}
\color{red}{x_0(s)} \\
\color{red}{x_1(s)} \\
\color{red}{x_2(s)} \\
\color{red}{x_3(s)} \\
\color{green}{0} \\
\color{green}{0} \\
\color{green}{0} \\
\color{green}{0} \\
\color{blue}{0} \\
\color{blue}{0} \\
\color{blue}{0} \\
\color{blue}{0}
\end{bmatrix}
\end{equation}

  举例来说,给定 $\boldsymbol{\mathrm{x}}(s_0)$ 和 $\boldsymbol{\mathrm{w}}$,计算 $\hat{q}(s_0, a_0, \boldsymbol{\mathrm{w}})$ 的过程如下。

\begin{align}
& \boldsymbol{\mathrm{x}}(s_0) = \begin{bmatrix}
1 \\
0 \\
0 \\
1
\end{bmatrix}
\quad
\boldsymbol{\mathrm{w}} = \begin{bmatrix}
\color{red}{0.7} \\
\color{red}{0.1} \\
\color{red}{0.4} \\
\color{red}{0.3} \\
\color{green}{2.2} \\
\color{green}{1.0} \\
\color{green}{0.6} \\
\color{green}{1.8} \\
\color{blue}{1.3} \\
\color{blue}{1.1} \\
\color{blue}{0.9} \\
\color{blue}{1.7}\end{bmatrix}
\quad
\boldsymbol{\mathrm{x}}(s_0, a_0) = \begin{bmatrix}
\color{red}{1} \\
\color{red}{0} \\
\color{red}{0} \\
\color{red}{1} \\
\color{green}{0} \\
\color{green}{0} \\
\color{green}{0} \\
\color{green}{0} \\
\color{blue}{0} \\
\color{blue}{0} \\
\color{blue}{0} \\
\color{blue}{0}
\end{bmatrix}
\quad
\hat{q}(s_0, a_0, \boldsymbol{\mathrm{w}}) = 1 * 0.7 + 1 * 0.3 = 1 \\
& \mathcal{A}(s) = \{\color{red}{a_0}, \color{green}{a_0}, \color{blue}{a_0}\}
\end{align}

  除了在线性方法中通过堆叠特征来表示动作价值,还可以通过神经网络为每一个动作输出一个值,此时神经网络的输入为状态 $s$,输出为每一个动作的动作价值,如 $\hat{q}(s, a_0, \boldsymbol{\mathrm{w}}), \hat{q}(s, a_1, \boldsymbol{\mathrm{w}}), \cdots, \hat{q}(s, a_d, \boldsymbol{\mathrm{w}})$,如图 1 所示。

图 1

  注意图 1 在计算输出的动作价值时,每个动作其使用的权重都不相同。为了能在动作间进行泛化,可以同时将状态 $s$ 和动作作 $a$ 为网络的输入,网络输出一个值,即 $\hat{q}(s, a, \boldsymbol{\mathrm{w}})$,如图 2 所示。

图 2

2. 通过函数逼近进行 Sarsa 控制

  有了动作价值的表示之后,完整的分幕式半梯度 Sarsa 算法如下所示。


分幕式半梯度 Sarsa,用于估计 $\hat{q} \approx q$
输入:一个参数化的可微动作价值函数 $\hat{q} = \mathcal{S} \times \mathcal{A} \times \mathbb{R}^d \rightarrow \mathbb{R}$
算法参数:步长 $\alpha > 0$,很小的 $\varepsilon$,$\varepsilon > 0$
任意初始化价值函数的权值 $\boldsymbol{\mathrm{w}} \in \mathbb{R}^d$,比如 $\boldsymbol{\mathrm{w}} = \boldsymbol{0}$
对每一幕循环:
  $S, A \leftarrow$ 幕的初始状态和动作(如 $\varepsilon$-贪心策略)
  对该幕的每一步循环:
    采取动作 $A$,观察 $R, S’$
    如果 $S’$ 为终止状态:
      $\boldsymbol{\mathrm{w}} \leftarrow \boldsymbol{\mathrm{w}} + \alpha [R – \hat{q}(S, A, \boldsymbol{\mathrm{w}})] \nabla \hat{q}(S, A, \boldsymbol{\mathrm{w}})$
      到下一幕
    通过 $\hat{q}(S’, \cdot, \boldsymbol{\mathrm{w}})$ 选取 $A’$(如 $\varepsilon$-贪心策略)
    $\boldsymbol{\mathrm{w}} \leftarrow \boldsymbol{\mathrm{w}} + \alpha [R + \gamma \hat{q}(S’, A’, \boldsymbol{\mathrm{w}}) – \hat{q}(S, A, \boldsymbol{\mathrm{w}})] \nabla \hat{q}(S, A, \boldsymbol{\mathrm{w}})$
    $S \leftarrow S’$
    $A \leftarrow A’$


3. 通过函数逼近进行期望 Sarsa 控制

  回顾 Sarsa 使用后继状态和动作的价值进行更新,其表格方法的更新为

\begin{equation}
Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \big[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) – Q(S_t, A_t) \big] \tag{3}
\end{equation}

函数逼近方法的更新为

\begin{equation}
\boldsymbol{\mathrm{w}} \leftarrow \boldsymbol{\mathrm{w}} + \alpha \big[R_{t+1} + \gamma \hat{q}(S_{t+1}, A_{t+1}, \boldsymbol{\mathrm{w}}) – \hat{q}(S_t, A_t, \boldsymbol{\mathrm{w}})\big] \nabla \hat{q}(S_t, A_t, \boldsymbol{\mathrm{w}}) \tag{4}
\end{equation}

  期望 Sarsa 使用当前策略下的期望价值进行更新,其表格方法的更新为

\begin{equation}
Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \Big[ R_{t+1} + \gamma \sum_{a}\pi(a|S_{t+1})Q(S_{t+1}, a) – Q(S_t, A_t) \Big] \tag{5}
\end{equation}

在函数逼近方法中计算式 $(5)$ 中的期望,可以得到期望 Sarsa 的函数逼近方法的更新

\begin{equation}
\boldsymbol{\mathrm{w}} \leftarrow \boldsymbol{\mathrm{w}} + \alpha \Big[R_{t+1} + \gamma \sum_{a’}\pi(a’|S_{t+1})\hat{q}(S_{t+1}, a’, \boldsymbol{\mathrm{w}}) – \hat{q}(S_t, A_t, \boldsymbol{\mathrm{w}})\Big] \nabla \hat{q}(S_t, A_t, \boldsymbol{\mathrm{w}}) \tag{6}
\end{equation}