[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}