由于全文太长，只好分开发了。(已完结！在专栏查看本系列其他文章）

个人博客可以直接看全文~

本系列为在学习赵世钰老师的“强化学习的数学原理” 课程后所作笔记。

课堂视频链接https://www.bilibili.com/video/BV1sd4y167NS/

第八章 value function Approximation

在此之前，所有的state value和action value都是用表格表示出来的，例如：

	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$
$s_1$	$q_{\pi }(s_1,a_1)$	$q_{\pi }(s_1,a_2)$	$q_{\pi }(s_1,a_3)$	$q_{\pi }(s_1,a_4)$	$q_{\pi }(s_1,a_5)$
…	…	…	…	…	…
$s_9$	$q_{\pi }(s_9,a_1)$	$q_{\pi }(s_9,a_2)$	$q_{\pi }(s_9,a_3)$	$q_{\pi }(s_9,a_4)$	$q_{\pi }(s_9,a_5)$

使用表格的好处就是可以直观地分析

坏处就是无法处理很大的state space 或者action space、无法处理连续的state和action。泛化能力不强。

Value Function Approximation的含义

使用直线来拟合点：

$\hat{v}(s,w)=as+b=[s,1]\left[\begin{array}{c}a\\ b\end{array}\right]={\varphi }^T(s)w$

这里的w是parameter vector(参数向量)

$\varphi (s)$ 是s的feature vector(特征向量)

$\hat{v}(s,w)$ 是w的linear(线性关系)

使用函数来拟合可以节省存储空间(只需要存w的值(a,b)即可)

缺点是拟合后不太精确。

同样可以用二次函数来拟合：

$\hat{v}(s,w)=a{s}^2+bs+c={\varphi }^T(s)w$

(需要注意的是，这样的曲线对于w来说同样是一种线性的拟合)

• 使用Value Function Approximation的优点：

1. 便于存储，只需要存储w即可，不用存储大量数据。
2. 泛化能力更强，假设s2进行了更改，在表格存储中只会更改s2对应的内容，而使用value function approximation则会改变w的值，从而影响其他的值（如s1和s3），这样会增强泛化能力

objective funciton

令$v_{\pi }(s)$ 作为真正的state value。 $\hat{v}(s,w)$是函数的近似值。

我们目标就是找到最优的w来使得$\hat{v}(s,w)$ 可以很好的拟合出$v_{\pi }(s)$

目标函数objective function如下：
$$J(w)=\mathbb{E}[(v_{\pi }(S)-\hat{v}(S,w){)}^2]$$
我们目标就是找到最好的w使得$J(w)$ 最小化。

求解期望常见的两种方法：
uniform distribution 平均分布：
认为每一个状态都是同等重要的。那么每一个状态的权重就是$\frac{1}{|S|}$
$$J(w)=\mathbb{E}[(v_{\pi }(S)-\hat{v}(S,w){)}^2]=\frac{1}{|S|}\sum _{s\in S}(v_{\pi }(s)-\hat{v}(s,w){)}^2$$
使用均匀策略的缺点是，我们将很远处的状态和距离目标近处的状态设置权重一样。导致没有侧重点

第二个概率分布：

stationary distribution：

这是一种Markov下的long-run behavior

让 { d π ( s ) } s ∈ S \{d_\pi(s)\}_{s\in S} {dπ​(s)}s∈S​ 作为在策略$\pi$ 下的Markov stationary distribution，通过定义$d_{\pi }(s)\ge 0\text{ and }\sum _{s\in S}{d}_{\pi }(s)=1$

于是目标函数objective function可以被写为：
$$J(w)=\mathbb{E}[(v_{\pi }(S)-\hat{v}(S,w){)}^2]=\sum _{s\in S}{d}_{\pi }(s)(v_{\pi }(s)-\hat{v}(s,w){)}^2$$
Stationary distribution 也被称为steady-state distribution 或者limit distribution。

怎么求$d_{\pi }(s)$ ？给出一个很长很长的episode：

我们定义$n_{\pi }(s)$ 表示s出现的次数。于是我们用频率来近似估计$d_{\pi }(s)$
$$d_{\pi }(s)\approx \frac{n_{\pi }(s)}{\sum _{s^{\prime }\in S}{n}_{\pi }(s^{\prime })}$$
我们没必要真正的模拟这个episode并统计次数，可以通过数学公式得到：

最终趋于稳定的$d_{\pi }^T$ 要满足：
$$d_{\pi }^T=d_{\pi }^T{P}_{\pi }$$
这里的$P_{\pi }$ 是一个矩阵，代表从$s$ 到$s^{\prime }$ 转移的概率$p(s^{\prime }|s)$

optimization algorithms

目标函数的优化算法(optimization algorithms of objective function)

为了最小化目标函数$J(w)$ ，我们可以使用梯度优化gradient-descent
$$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}J(w_k)$$
这里的true gradient是:
$$\begin{array}{rl}{\nabla }_{w}J(w)& ={\nabla }_w\mathbb{E}[(v_{\pi }(S)-\hat{v}(S,w){)}^2]\\ & =\mathbb{E}[{\nabla }_w(v_{\pi }(S)-\hat{v}(S,w){)}^2]\\ & =2\mathbb{E}[(v_{\pi }(S)-\hat{v}(S,w))(-{\nabla }_w\hat{v}(S,w))]\\ & =-2\mathbb{E}[(v_{\pi }(S)-\hat{v}(S,w)){\nabla }_w\hat{v}(S,w)]\end{array}$$
但是求期望很麻烦，所以我们用sotcastic gradient descent来替代gradient descent
$$w_{t+1}=w_t+{\alpha }_k(v_{\pi }(s_t)-\hat{v}(s_t,wt)){\nabla }_w\hat{v}(s_t,w_t)$$
但是在现实中，我们是无法得知$v_{\pi }(s_t)$ 的。

有如下方法：

1. Monte Carlo learning 和 value function approximation结合

   让$g_t$ 表示从$s_t$ 开始的episode的return。那么

   $w_{t+1}=w_t+{\alpha }_t(g_t-\hat{v}(s_t,w_t)){\nabla }_w\hat{v}(s_t,w_t)$

2. TD learning 和value function approximation结合

   在TD算法中可以用$r_{t+1}+\gamma \hat{v}(s_{t+1},w_t)$ 来作为$v_{\pi }(s_t)$ 的一个估计值。于是有

   $w_{t+1}=w_t+{\alpha }_t[r_{t+1}+\gamma \hat{v}(s_{t+1},w_t)-\hat{v}(s_t,w_t)]{\nabla }_w\hat{v}(s_t,w_t)$

目前只能用来估计给定策略的state values。

selection of function approximators

函数的选取方法

1. 选择线性函数（之前广为使用）：
   $$\hat{v}(s,w)={\varphi }^T(s)w$$
   此处的$\varphi (s)$ 是特征向量，他是基于多项式的(polynomial basis),基于傅里叶的(Fourier basis),…

2. 选择神经网络（现在广为使用）：

   网络的参数是w，神经网络的输入是state，输出是估计值$\hat{v}(x,w)$

考虑线性函数：$\hat{v}(s,w)={\varphi }^T(s)w$ ,我们有
$${\nabla }_w\hat{v}(s,w)=\varphi (s)$$
代入TD算法可以得到TD-Linear：
$$w_{t+1}=w_t+{\alpha }_t[r_{t+1}+\gamma {\varphi }^T(s_{t+1})w_t-{\varphi }^T(s_t)w_t]\varphi (s_t)$$

Linear function approximation的劣势：、

• 很难去选择一个合适的feature vectors

Linear function approximation的优势：

• 数学原理清晰，能够可以帮助我们更透彻地研究。
• 表征能力还算可以。表格形式tabular representation是Linear function approximation 的特殊形式。

Tabular representation 是Linear funciton的一种特殊情况：

首先考虑如下的特征向量：
$$\varphi (s)=e_s\in {\mathbb{R}}^{|S|}$$
这里的$e_s$ 是一个只有一个1，其他都是0的向量。

那么这样的话$\hat{v}(s,w)=e_s^{T}w=w(s)$ , 这样$w(s)$ 就是w的第s个元素了。也就是tabular representation。

然后我们把$\varphi (s_t)=e_s$ 带入到TD-Linear中。
$$w_{t+1}=w_t+\alpha (r_{t+1}+\gamma w_t(s_{t+1})-w_t(s_t))e_{S_t}$$
因为$e_{s_t}$ 只有在$w_t$ 的位置是1，其他位置是0，所以在$w_t$ 中只有$S_t$的位置被更新了。
$$w_{t+1}(s_t)=w_t(s_t)+{\alpha }_t(r_{t+1}+\gamma w_t(s_{t+1})-w_t(s_t))$$
于是我们发现这个式子和之前tabular的TD算法是一样的。

Sarsa

Sarsa和value function estimation结合：
KaTeX parse error: Invalid color: ' #0000FF' at position 12: \textcolor{̲ ̲#̲0̲0̲0̲0̲F̲F̲}̲{w_{t+1}} = \te…
除了标蓝的地方略有差别，其他和tabular是一样的。

1. 因为我们描述的参数从state变为了parameter, 所以更新的内容从$q(s,a)$变为了$w$
2. 使用估计值来估计一个点的state，所以原先的$q(s,a)$ 变为了由函数估计产生的$\hat{q}(s,a,w)$
3. 最后乘上$\hat{q}$ 的梯度来使得向零点移动。

步骤如下：

1. 对每个episode 执行如下操作：

2. 遵循${\pi }_t(s_t)$ 执行动作$a_t$ ，然后生成$r_{t+1},s_{t+1}$ ，然后遵循${\pi }_t(s_{t+1})$执行$a_{t+1}$ .

3. 更新值（parameter update）：
   KaTeX parse error: Invalid color: ' #0000FF' at position 13: \textcolor{̲ ̲#̲0̲0̲0̲0̲F̲F̲}̲{w_{t+1}} = \te…

4. 更新策略(policy update):

KaTeX parse error: Invalid color: ' #0000FF' at position 133: …s_t)}\textcolor{̲ ̲#̲0̲0̲0̲0̲F̲F̲}̲{ \hat q(s_t,a,…

Q-learning

Q-learning 和value function estimation 结合：
KaTeX parse error: Invalid color: ' #0000FF' at position 28: …ned} \textcolor{̲ ̲#̲0̲0̲0̲0̲F̲F̲}̲{w_{t+1}} = \te…
蓝色部分为value function estimation 版本的Q-learning和tabular 版本之间的区别。

步骤如下（on-policy）：

1. 对每个episode 执行如下操作：

2. 遵循${\pi }_t(s_t)$ 执行动作$a_t$ ，然后生成$r_{t+1},s_{t+1}$

3. 更新值（parameter update）：
   KaTeX parse error: Invalid color: ' #0000FF' at position 30: …ed} \textcolor{̲ ̲#̲0̲0̲0̲0̲F̲F̲}̲{w_{t+1}} = \te…

4. 更新策略(policy update)：
   KaTeX parse error: Invalid color: ' #0000FF' at position 135: …s_t)}\textcolor{̲ ̲#̲0̲0̲0̲0̲F̲F̲}̲{ \hat q(s_t,a,…

Deep Q-learning(deep Q-network)

首先定义损失函数：objective function/loss function:
$$J(w)=\mathbb{E}[(R+\gamma \underset{\alpha \in \mathrm{A}(S^{\prime })}{\max }\hat{q}(S^{\prime },a,w)-\hat{q}(S,A,w){)}^2]$$
这是一个贝尔曼最优误差，下式为Q-learning的Bellman optimality error：
$$q(s,a)=\mathbb{E}[R_{t+1}+\gamma \underset{\alpha \in \mathrm{A}(S-t+1)}{\max }q(S_{t+1},a)|S_t=s,A_t=a],\forall s,a$$
因此$R+\gamma \underset{\alpha \in \mathcal{A}(S^{\prime })}{\max }\hat{q}(S^{\prime },a,w)-\hat{q}(S,A,w)$ 的期望应该是0.

如何最小化这个损失函数？ 使用梯度下降法 Grradient-descent：

求$J(w)$ 关于w的梯度，难点在于表达式中由两个地方出现了$w$ ，于是基本思想为我们把前半部分当作一个常数y：
$$y=R+\gamma \underset{\alpha \in \mathrm{A}(S^{\prime })}{\max }\hat{q}(S^{\prime },a,w)$$
这样就只有$\hat{q}(S,A,w)$ 项包含w了，就可以比较简单地求解梯度。

求解方法：

引入两个网络

• main network 表示$\hat{q}(s,a,w)$
• target network $\hat{q}(s,a,w_T)$

将损失函数改写为：
KaTeX parse error: Invalid color: ' #FF0000' at position 79: …max} \textcolor{̲ ̲#̲F̲F̲0̲0̲0̲0̲}̲{\hat q(S',a,w_…
即我们保持target network一段时间不动，因此就能将前半部分作为常数，然后来更新main network。 之后再更新target network。这样也能保证两个网络最后都收敛。

DQN-Experience replay

Experience replay经验回放 ，具体为：

• 我们在收集完数据后，并不根据他们被收集的顺序来使用他们。
• 而是我们把他们存储到一个集合replay buffer 中， $\mathcal{B}=\{(s,a,r,s^{\prime })\}$
• 每次训练神经网络的时候， 把他们混到一起，然后取出一些样本(mini-batch)来进行训练。
• 在取出样本的时候一定要服从均匀分布(uniform distribution)

为什么需要经验回放？为什么必须服从均匀分布？

我们观察损失函数：
$$J(w)=\mathbb{E}[(R+\gamma \underset{\alpha \in \mathrm{A}(S^{\prime })}{\max }\hat{q}(S^{\prime },a,w)-\hat{q}(S,A,w){)}^2]$$

• $(S,A)\sim d$ 我们根据索引(S,A) 就能够找到一个唯一的随机变量d
• $R\sim p(R|S,A),S^{\prime }\sim p(S^{\prime }|S,A)$ ， R和S’ 由给定的模型决定。
• 在数据采集的时候，我们可能并不是按照均匀分布采样的。因为他们被确定的策略产生。
• 为了打破连续样本之间的相关性(通常他们有很强的时间相关性)，我们可以从replay buffer中进行随机均匀采样。
• 这就是为什么经验回放是必须的，并且是必须均匀分布采样的。

Deep Q-learning

off-policy version:
目标是从通过 behavior policy ${\pi }_b$ 生成的一些经验中学习一个优化的target network来逼近最优action values 。

步骤如下：

1. 存储由behavior policy 生成的经验，存放到replay buffer中 $\mathcal{B}=\{(s,a,r,s^{\prime })\}$
2. 对每一次迭代重复如下动作：
3. 从$\mathcal{B}$ 中均匀提取一些样本(mini-batch)
4. 对于每个样本$(s,a,r,s^{\prime })$ ,计算target value $y_T=r+\gamma ma{x}_{\alpha \in \mathcal{A}(s^{\prime })}(\hat{q},a,w_T)$ , 在这之中$w_T$ 是target network(两个网络之一)
5. 使用mini-batch$\{(s,a,y_T)\}$ 更新main network 来最小化$(y_T-\hat{q}(s,a,w){)}^2$
6. 每进行C次迭代，更新target network：$w_T=w$