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

Author: nex3z 2019-11-09

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 在计算输出的动作价值时，每个动作其使用的权重都不相同。为了能在动作间进行泛化，可以同时将状态 $s$ 和动作作 $a$ 为网络的输入，网络输出一个值，即 $\hat{q}(s, a, \boldsymbol{\mathrm{w}})$，如图 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}$$