线性值函数近似法
之前的时序差分强化学习，一般针对的是离散空间，用的是
动作值函数表格（状态动作对）去近似目标值；现在用一个
函数表达式去近似目标值，可以应用于离散空间和连续空间
$$
Q:\mathbb{S} \times \mathbb{A} \stackrel{w}{\longrightarrow}R
$$
线性值函数近似时序差分
用简单的线性函数近似，动作值函数可以表示为一个
线性函数$$
\hat{Q}_{\pi}(s, a ; \theta) = \phi(s, a) \cdot \theta \quad \phi: \mathbb{S} \times \mathbb{A} \longrightarrow R^{l} \tag{15-1}
$$
其中，自变量是 $(s,a)$，$\phi$ 称为特征函数，代表映射到一个 $l$ 维空间（向量），$\theta$ 代表参数
简单的特征函数，直接将自变量拼接起来：
$$
s=\left(s_{1}, s_{2}, \cdots, s_{n}\right)^{\top} \in \mathbb{S} \subseteq R^{n}, \quad a=\left(a_{1}, a_{2}, \cdots, a_{m}\right)^{\top} \in \mathbb{A} \subseteq R^{m} \\
~\\
\phi(s, a) = \left(s_{1}, s_{2}, \ldots, s_{n}, a_{1}, a_{2}, \ldots, a_{m}\right)^{\top} \in R^{n+m} \tag{15-2}
$$
按照之前的做法，可以得到损失函数：
$$
L(\theta)=E_{\pi}\left[\left(Q_{\pi}(s,a)-\hat{Q}_{\pi}(s,a;\theta)\right)^{2}\right]
~\\
Q_{\pi}(s, a) \approx R(s, a)+\gamma\ \hat{Q}_{\pi}\left(s^{\prime}, a^{\prime} ; \theta\right) \tag{15-3}
$$
现在要做的训练就是最小化损失函数，找到合适的参数 $\theta$
（1）线性值函数近似 $Sarsa$ 算法（15-4）- 输入：环境模型 $MDP(S,A,R,\gamma)$，学习率 $\alpha =0.1$，贪婪系数 $\epsilon=0.1$，最大迭代局数 $num\_episodes=1000$
- 初始化：随机初始化动作值参数 $\theta$，初始策略求解 $\pi(s)=\arg\max_{a\in \mathbb{A}} \hat{Q}(s,a;\theta)$
- 过程：
- $\qquad$ 循环：$i=1\sim num\_episodes$
- $\qquad \qquad$ 初始状态：$s=s_0$
- $\qquad \qquad$ 根据当前 $\epsilon$ 贪婪策略选择动作：$a=\pi_\epsilon(s)$
- $\qquad \qquad$ 循环：直到到达终止状态，即 $end=True$
- $\qquad \qquad \qquad$ 执行动作：$s,a,R,s',end$
- $\qquad \qquad \qquad$ 根据当前 $\epsilon$ 贪婪策略选择动作：$a’=\pi_\epsilon(s')$
- $\qquad \qquad \qquad$ 参数更新： $\theta \leftarrow \theta +\alpha \left(R+\gamma\ \phi(s',a')\cdot \theta - \phi(s,a)\cdot \theta \right) \phi(s,a)$
- $\qquad \qquad \qquad$ 策略改进：$\pi(s)=\arg \max _{a \in \mathbb{A}} \hat{Q}(s, a;\theta)$
- $\qquad \qquad \qquad$ 状态更新：$s \leftarrow s',\ a \leftarrow a'$
- 输出：最终策略 $\pi^*$，最终动作值 $Q^*$
说明：参数更新其实就是策略评估，用的是梯度下降，$\nabla_{\theta} L(\theta)=\left(R+\gamma\ \phi(s',a')\cdot \theta - \phi(s,a)\cdot \theta \right) \phi(s,a)$
$\ $
（2）线性值函数近似 $Q-learning$ 算法（15-5）- 输入：环境模型 $MDP(S,A,R,\gamma)$，学习率 $\alpha =0.1$，贪婪系数 $\epsilon=0.1$，最大迭代局数 $num\_episodes=1000$
- 初始化：随机初始化动作值参数 $\theta$，初始策略求解 $\pi(s)=\arg\max_{a\in \mathbb{A}} \hat{Q}(s,a;\theta)$
- 过程：
- $\qquad$ 循环：$i=1\sim num\_episodes$
- $\qquad \qquad$ 初始状态：$s=s_0$
- $\qquad \qquad$ 循环：直到到达终止状态，即 $end=True$
- $\qquad \qquad \qquad$ 根据当前 $\epsilon$ 贪婪策略选择动作：$a=\pi_\epsilon(s)$
- $\qquad \qquad \qquad$ 执行动作：$s,a,R,s',end$
- $\qquad \qquad \qquad$ 参数更新： $\theta \leftarrow \theta +\alpha \left(R+\gamma\ \max_{a\in \mathbb{A}}\left(\phi(s',a')\cdot \theta\right) - \phi(s,a)\cdot \theta \right) \phi(s,a)$
- $\qquad \qquad \qquad$ 策略改进：$\pi(s)=\arg \max _{a \in \mathbb{A}} \hat{Q}(s, a;\theta)$
- $\qquad \qquad \qquad$ 状态更新：$s \leftarrow s'$
- 输出：最终策略 $\pi^*$，最终动作值 $Q^*$
特征函数
多项式特征函数
对状态 $\mathbb{S}$ 和动作 $\mathbb{A}$ 都可以去做映射，简单起见，只讨论状态 $\mathbb{S}=(s_1,s_2,\cdots,s_n)$
特征函数 $\phi$ 是状态 $\mathbb{S}$ 到 $R^l$ 的映射，$\phi:\mathbb{S} \rightarrow R^l$，$\phi(s)=\left(\varphi_1(s),\varphi_2(s), \cdots ,\varphi_l(s)\right)^{\top}$
$$
S=\left(\xi_{1}, \xi_{2}, \cdots, \xi_{m}\right)^{\top} \in \mathbb{S} \subseteq R^{m}
~\\
\varphi_{i}(s)=\varphi_{i}\left(\xi_{1}, \xi_{2}, \cdots, \xi_{m}\right)=\prod_{j=1}^{m} \xi_{j}^{C_{i j}} \tag{15-6}
$$
其中，$i=1,2, \ldots, l$，$C_{i j} \in \{0,1,2,\cdots,k\}$
举两个例子：
（1）$\mathbb{S}=R^5$，$k=2 \quad C_{i j} \in \{0,1,2\} \quad s=\{\xi_1,\xi_2,\xi_3,\xi_4,\xi_5 \}$
最简单的：$\varphi_1(s)=\xi_1={\xi_1}^1 \cdot {\xi_2}^0 \cdot {\xi_3}^0 \cdot {\xi_4}^0 \cdot {\xi_5}^0$
令 $\xi_i(s)=\xi_i \quad i=0,1,\cdots,5$，则 $\phi(s)=(\xi_1,\xi_2,\cdots,\xi_5)^{\top}$
（2）更复杂的，每个分量都是多项式：
$$
\phi(s)=\left(1, \xi_{1}, \xi_{2}, \cdots, \xi_{5}, \xi_{1}^{2}, \cdots ,\xi_{5}^{2}, \xi_{1} \xi_{2}, \xi_{1} \xi_{3},\cdots, \xi_{4} \xi_{5}\right)^{\top}
$$
其中每个分量都可以用 $\varphi_{i}(s)=\prod_{j=1}^{m} \xi_{j}^{C_{i j}}$ 表示
$\ $
傅里叶特征函数
（1）傅里叶函数，是对于一个函数的逼近：
$$
f(t)=\sum_{n=0}^{\infty} a_{n} \cos (n \pi t)+b_{n} \sin (n \pi t) \quad t \in (-\infty,+\infty)
$$
（2）周期延拓
（3）傅里叶基
$$
\varphi_i(s)=cos(\pi s^T c_i) \quad i=1,2,\cdots,l \quad s=(\xi_1,\xi_2,\cdots,\xi_m)
~\\
c_i=(c_{i1},c_{i2},\cdots,c_{im})^{\top} \quad c_{ij} \in \{0,1,\cdots,k\}
$$
说明：以上两个函数都是用连续函数去近似
粗编码
粗编码（$Coarse\ \ Coding$）将一个连续的状态空间映射到一个离散的特征向量空间，
用离散的方式去近似连续的空间，该特征向量空间的元素是由 $0$ 或 $1$ 作为分量的向量。对于一个连续的状态空间，可以将其用一些相互重叠的区域覆盖，每个区域对应着特征向量的一个维度，如果一个状态落在了某个区域，则在特征向量中该区域所对应的维度为 $1$，否则为 $0$
瓦片编码
瓦片编码（$Tile\ \ Coding$）是多维连续空间的一种粗编码形式，它具有灵活性好和计算效率高的特点，是比较实用的特征表示方法。在瓦片编码中，用一个被划分成不同特征区域的网状结构覆盖连续状态空间，每一个这样的网状结构称为一个瓦片网（$Tiling$），瓦片网中的每一个特征区域称为一块瓦片（$Tile$）
径向基函数
相较于二值特征向量，径向基函数的一个主要优势在于它能够产生十分光滑和可微的近似函数。这虽然是很好的性质，但在实际应用中并不是非常必须；反而，使用径向基函数会导致计算复杂度增加，特别是在维度较高时， 所以径向基函数在高维特征上表现并不好
参考
