【强化学习】值函数逼近

发表于 | 分类于   |   字数统计: 1,122(字)   |   热度  °C

0 引言

为什么要进行值函数逼近呢？
建立一个表格保存所有的状态以及对应的值函数值，这种方法在解决大规模问题上，会遇到两个问题，一是状态空间很大，内存无法保存Q表；二是对于很大的状态空间，学习起来也非常慢。于是，一个自然的想法就是用函数逼近状态值函数或者动作-状态值函数，这样就可以从有限的状态中学习到一个近似的状态值函数，而且可以泛化到没有见过的状态。使用MC或者TD学习来更新函数参数。

$$
\hat{v}(s,w) \approx v_{\pi}(s) \
or \hat{q}(s,a,w) \approx q_{\pi}(s,a)
$$

本文主要将近似方法分为两大类，增量法和批处理法。增量法主要用于在线更新，每一步都会更新近似函数；批处理法一次处理一批数据，并从这批数据中拟合出最好的近似函数。

值函数逼近包含三种类型：

1 增量法 Incremental Methods

使用梯度下降法来逼近值函数：
目标函数：
$$
J(w)=\mathbb{E}_{\pi}[(v_{\pi}(S)-\hat{v}(S,w))^2]
$$
定义梯度：
$$
\nabla_w J(w)=(\frac{\partial J(w)}{\partial w_1}, \cdots, \frac{\partial J(w)}{\partial w_n})^T
$$
梯度下降：
$$
\Delta w=-\frac{1}{2}\alpha\nabla_w J(w) = \alpha \mathbb{E}_{\pi}[(v_{\pi}(S)-\hat{v}(S,w))\nabla_w \hat{v}(S,w)]
$$
随机梯度下降：
$$
\Delta w=\alpha(v_{\pi}(S)-\hat{v}(S,w))\nabla_w\hat{v}(S,w)
$$
注：随机梯度下降和梯度下降的区别见【机器学习】梯度下降GD,SGD

将特征表示成向量的形式：
$$
x(S)=(x_1(S),\cdots,x_n(S))^T
$$
则值函数可以用线性模型来估计：
$$
\hat{v}(S,w)=x(S)^Tw=\sum^n_{j=1}x_j(S)w_j
$$
将上式代入目标函数可以求的随机梯度为：
$$
\Delta w=\alpha(v_{\pi}(S)-\hat{v}(S,w))x(S)
$$

问题出现了，这并不是监督学习，并没有$v_{\pi}(S)$，只有奖励值rewards.于是，只能用奖励返回值来代替$v_{\pi}(S)$。
对于MC
$$
\Delta w=\alpha(G_t-\hat{v}(S_t,w))\nabla_w\hat{v}(S_t,w)
$$
对于TD(0)
$$
\Delta w=\alpha(R_{t+1} + \gamma\hat{v}(S_{t+1},w)-\hat{v}(S_t,w))\nabla_w\hat{v}(S_t,w)
$$
对于TD($\lambda$)
$$
\Delta w=\alpha(G^{\lambda}_t-\hat{v}(S_t,w))\nabla_w\hat{v}(S_t,w)
$$

那么如何进行学习呢？这里仅举TD($\lambda$),其他相似
准备训练数据：
$$
\langle S_1, G^{\lambda}_1 \rangle , \langle S_2, G^{\lambda}_2 \rangle, \cdots, \langle S_{T-1}, G^{\lambda}_{T-1} \rangle
$$
前向看：
$$
\Delta w=\alpha(G^{\lambda}_t-\hat{v}(S_t,w))x(S_t)
$$
向后看：
$$
\delta_t = R_{t+1}+\gamma\hat{v}(S_{t+1},w)-\hat{v}(S_t,w)
$$
$$
E_t = \gamma\lambda E_{t-1} + x(S_t)
$$
$$
\Delta w = \alpha\delta_t E_t
$$

从一个开始的参数，一直迭代直到收敛。

状态-动作值函数的逼近原理相同。

2 批处理法 Batch Methods

梯度下降法比较简单，但是并不是很有效。批处理方法引入经验的概念，将经验作为训练数据，然后利用监督学习的方法，拟合出该数据集最好的值函数。

经验数据：
$$
\mathcal{D}={\langle s_1,v^{\pi}_1 \rangle,\langle s_2,v^{\pi}_2 \rangle,\cdots,\langle s_T,v^{\pi}_T \rangle}
$$

最小二乘法：
$$
LS(w)=\sum^T_{t=1}(v^{\pi}_t-\hat{v}(s_t,w))^2=\mathbb{E}_{\mathcal{D}}[(v^{pi}-\hat{v}(s_t,w))^2]
$$

利用经验回放的随机梯度下降：

  1. 从经验中采样
    $$
    \langle s, v^{\pi} \rangle \sim \mathcal{D}
    $$

  2. 使用随机梯度下降更新参数
    $$
    \Delta w = \alpha (v^{\pi}-\hat{v}(s_t,w)) \nabla_w\hat{v}(S,w)
    $$

  3. 收敛到最优解
    $$
    w^{\pi}=arg\min\limits_{w} LS(w)
    $$

DQN
两个要点：一是经验回放，Experience Replay;二是fixed Q-targets
算法的伪代码：

最小二乘法：
$$
\mathcal{L}(w_i)=\mathbb{E}_{s,a,r,s^{\prime}\sim \mathcal{D}_i}[(r+\gamma\max\limits_{a^{\prime}}Q(s^{\prime},a^{\prime};w^-_i)-Q(s,a;w_i))^2]
$$

算法的要点有：

  • 根据$\epsilon$-greedy策略选择动作$a_t$
  • 将状态转换$\langle s_t,a_t,r_{t+1},s_{t+1}\rangle$存放在经验集$\mathcal{D}$中
  • 从经验集$\mathcal{D}$随机采样得到一个子集$\langle s,a,r,s^{\prime}\rangle$
  • 根据未更新的固定参数$w^-$来计算Q-learning targets
  • 最优化Q-network和Q-learning targets之间的平方误差
  • 使用SGD

参考文献

[1] 周志华,《机器学习》,清华大学出版社,2016
[2] David Silver, reinforcement learning lecture 6
[3] Mnih V, Kavukcuoglu K, Silver D, et al. Human-level control through deep reinforcement learning[J]. Nature, 2015, 518(7540): 529-533.

显示 Gitment 评论