强化学习中的值函数近似算法

在这里插入图片描述

在开始说值函数近似方法之前，我们先回顾一下强化学习算法。强化学习算法主要有两大类Model-based 的方法和Model-free的方法，model based 的方法也可以叫做 dynamic programming ：

Model-based dynamic programming

在model-based的动态规划算法中，核心概念是值迭代和策略迭代。在值迭代算法中是通过对未来状态的价值估计和及时奖励来估计当前状态的价值；在策略迭代算法中，主要是通过贪婪策略进行迭代，而要使得贪婪策略能够进行下去，依然还是会需要对状态的估计，也就是需要值迭代，但是可以不用值迭代收敛才进行策略改进，这样能够使得算法收敛地快一些。其核心公式如下所示：

Value iteration： $V(s) = R(s) + \max_{a \in A} \gamma \sum_{s^{\prime} \in S}P_{sa}(s^{\prime})V(s^{\prime})$ 。
Policy iteration： $\pi(s) = \argmax_{a \in A} \sum_{s^{\prime} \in S}P_{sa}(s^{\prime})V(s^{\prime})$

Model-free reinforcement learning

在model-free的强化学习算法中，主要是通过蒙特卡洛的方法和TD的方法来估计state value。在TD算法中又分为On policy的sarsa算法和off-policy的q-learning算法。

On-Policy MC： $V(s_{t}) \leftarrow V(s_{t}) + \alpha(G_{t}-V(s_{t}))$ 。
On-Policy TD： $V(s_{t}) \leftarrow V(s_{t}) + \alpha (r_{t+1} + \gamma V(s_{t+1})-V(s_{t}))$ 。
On-policy TD SARSA ：

$Q\left(s_{t}, a_{t}\right) \leftarrow Q\left(s_{t}, a_{t}\right)+\alpha\left(r_{t+1}+\gamma Q\left(s_{t+1}, a_{t+1}\right)-Q\left(s_{t}, a_{t}\right)\right)$

Off-policy TD Q-learning ：

$Q\left(s_{t}, a_{t}\right) \leftarrow Q\left(s_{t}, a_{t}\right)+\alpha\left(r_{t+1}+\gamma \max _{a^{\prime}} Q\left(s_{t+1}, a_{t+1}\right)-Q\left(s_{t}, a_{t}\right)\right)$

处理大规模状态、动作空间

In all previous models, we have created a lookup table to maintain a variable $V(s)$ for each state or $Q(s,a)$ for each state-action。

当state or state-action space 太大的话，或者state or action is continuous就没办法created the lookup table。

解决上述问题主要有两种方式，一种就是将大的连续的状态空间或者动作空间离散化，变成一块一块地，这种做法控制效果不会太好，另外一种办法呢，就是建立一个参数化的值函数来近似，后面这种方法也是比较常见的。

Discretization Continuous MDP

对于连续状态下的MDP问题，我们可以将状态离散化为概率，比如在这个状态下采取什么动作会以多大的概率转移到下一个状态，进而可以离散化为一个表格的形式。这种方法非常地繁琐。

这里要注意的就是state transition需要对连续量积分，离散化。

Bucketize Large Discrete MDP

对于大规模的离散化状态空间，我们可以通过domain knowledge将相似的离散state聚合在一起。上述操作不管怎么离散聚合都会存在误差。因此现在的主流方法还是值函数近似算法。

Parametric Value Function Approximation

Create parametric (thus learnable) functions to approximate the value function

$\begin{aligned} V_{\theta}(s) & \simeq V^{\pi}(s) \\ Q_{\theta}(s, a) & \simeq Q^{\pi}(s, a) \end{aligned}$

$\theta$ is the parameters of the approximation function, which can be updated by reinforcement learning。

这种做法一方面解决了维度灾难的问题，另一方面可以Generalize from seen states to unseen states，这也是整个machine learning最强大，最具有魅力的地方。

Many function approximations

(Generalized) linear model
Neural network
Decision tree
Nearest neighbor
Fourier / wavelet bases

上述算法都可以做 function approximations 但是决策树、随机森林的灵活性没有那么强，因为强化学习算法中参数经常会被用来更新。因此我们很多时候用Differentiable functions 像(Generalized) linear model 、Neural network来做。

We assume the model is suitable to be trained for nonstationary, non-iid data

Value Function Approx. by SGD

Goal: find parameter vector $\theta$ minimizing mean-squared error between approximate value function $V_{\theta}(s)$ and true value $V^{\pi}(s)$ 。

$J(\theta)=\mathbb{E}_{\pi}\left[\frac{1}{2}\left(V^{\pi}(s)-V_{\theta}(s)\right)^{2}\right]$

Gradient to minimize the error

$-\frac{\partial J(\theta)}{\partial \theta}=\mathbb{E}_{\pi}\left[\left(V^{\pi}(s)-V_{\theta}(s)\right) \frac{\partial V_{\theta}(s)}{\partial \theta}\right]$

Stochastic gradient descent on one sample

$\begin{aligned} \theta & \leftarrow \theta-\alpha \frac{\partial J(\theta)}{\partial \theta} \\ &=\theta+\alpha\left(V^{\pi}(s)-V_{\theta}(s)\right) \frac{\partial V_{\theta}(s)}{\partial \theta} \end{aligned}$

Linear Value Function Approximation

举个实际的例子：

Represent value function by a linear combination of features

$V_{\theta}(s) = \theta^{T}x(s)$

Objective function is quadratic in parameters $\theta$

$J(\theta)=\mathbb{E}_{\pi}\left[\frac{1}{2}\left(V^{\pi}(s)-\theta^{T}x(s)\right)^{2}\right]$

Thus stochastic gradient descent converges on global optimum

$\begin{aligned} \theta & \leftarrow \theta-\alpha \frac{\partial J(\theta)}{\partial \theta} \\ &=\theta+\alpha\left(V^{\pi}(s)-V_{\theta}(s)\right) x(s) \end{aligned}$

那上述公式中的 $V^{\pi}(s)$ 是怎么求的呢？

Monte-Carlo with Value Function Approx

如果不知道真正的value是多少就无法更新，之前的方法就可以拿过来用了。

For each data instance $<s_{t}，G_{t}>$ ：

$\theta \leftarrow \theta +\alpha(G_{t}-V_{\theta}(s))x(s_{t})$

可以证明MC evaluation at least converges to a local optimum ，如果环境本身是In linear case it converges to a global optimum。

TD Learning with Value Function Approx

现在就是在找这个target learning用什么东西来替代它，在TD Learning中For each data instance $<s_{t},r_{t+1} + \gamma V_{\theta}(s_{t+1})>$ ：

$\theta \leftarrow \theta +\alpha(r_{t+1}+\gamma V_{\theta}(s_{t+1})-V_{\theta}(s))x(s_{t})$

Linear TD converges (close) to global optimum。

Action-Value Function Approximation

Approximate the action-value function：

$Q_{\theta}(s,a) \simeq Q^{\pi}(s,a)$

Minimize mean squared error：

$J(\theta) = \mathbb{E} [\frac{1}{2}(Q^{\pi}(s,a)-Q_{\theta}(s,a))^{2}]$

Stochastic gradient descent on one sample：

$\begin{aligned} \theta & \leftarrow \theta-\alpha \frac{\partial J(\theta)}{\partial \theta} \\ &=\theta+\alpha\left(Q^{\pi}(s)-Q_{\theta}(s)\right) \frac{\partial Q_{\theta}(s,a)}{\partial \theta} \end{aligned}$

Linear Action-Value Function Approx

Represent state-action pair by a feature vector

这里就需要从state-action pair上面去抽取 fearure。

$x(s, a)=\left[\begin{array}{c} {x_{1}(s, a)} \\ {\vdots} \\ {x_{k}(s, a)} \end{array}\right]$

Parametric Q function, e.g., the linear case

$Q_{\theta}(s, a)=\theta^{\top} x(s, a)$

Stochastic gradient descent update

$\begin{aligned} \theta & \leftarrow \theta-\alpha \frac{\partial J(\theta)}{\partial \theta} \\ &=\theta+\alpha\left(Q^{\pi}(s)-\theta^{\top} x(s, a)\right) x(s,a) \end{aligned}$

TD Learning with Value Function Approx.

$\theta \leftarrow \alpha(Q^{\pi}(s,a)-Q_{\theta}(s,a)) \frac{\partial Q_{\theta}(s,a)}{\partial \theta}$

For MC, the target is the return $G_{t}$ ：

$\theta \leftarrow \alpha(G_{t}-Q_{\theta}(s,a)) \frac{\partial Q_{\theta}(s,a)}{\partial \theta}$

For TD，the target is $r_{t+1} + \gamma Q_{\theta}(s_{t+1}, a_{t+1})$ ：

$\theta \leftarrow \alpha(r_{t+1} + \gamma Q_{\theta}(s_{t+1}, a_{t+1})-Q_{\theta}(s,a)) \frac{\partial Q_{\theta}(s,a)}{\partial \theta}$

Control with Value Function Approx

Value Function Approx下的收敛方式

上图中无法达到上界的原因是由于值函数近似逼近无法趋近于真实 $Q^{\pi}$ 所导致的。

Policy evaluation: approximatelypolicy evaluation $Q_{\theta} \simeq Q^{\pi}$ 。
Policy improvement: $\varepsilon$ -greedy policy improvement。

NOTE of TD Update

For TD(0), the TD target is

State value

$\begin{aligned} \theta & \leftarrow \theta+\alpha\left(V^{\pi}\left(s_{t}\right)-V_{\theta}\left(s_{t}\right)\right) \frac{\partial V_{\theta}\left(s_{t}\right)}{\partial \theta} \\ &=\theta+\alpha\left(r_{t+1}+\gamma V_{\theta}\left(s_{t+1}\right)-V_{\theta}(s)\right) \frac{\partial V_{\theta}\left(s_{t}\right)}{\partial \theta} \end{aligned}$

Action value

$\begin{aligned} \theta & \leftarrow \theta+\alpha\left(Q^{\pi}(s, a)-Q_{\theta}(s, a)\right) \frac{\partial Q_{\theta}(s, a)}{\partial \theta} \\ & =\theta+\alpha\left(r_{t+1}+\gamma Q_{\theta}\left(s_{t+1}, a_{t+1}\right)-Q_{\theta}(s, a)\right) \frac{\partial Q_{\theta}(s, a)}{\partial \theta} \end{aligned}$

Although $\theta$ is in the TD target, we don’t calculate gradient from the target. Think about why.

对上述问题主要有两方面的理解：1. 更新方程中是用后面的估值更新前面的，而不需要去更新后面的，这也是马尔可夫性所决定的大体思想(在无近似值函数的算法中也是这么做的)；2. 在做神经网络的时候，可以更新后面的那一项都不去做更新，因为会使得算法更新不稳定。

Deep Q-Network (DQN)

在2013年年底的时候DeepMind就基于深度学习和强化学习做出来了直接估计像素状态值函数的深度强化学习算法。

【5分钟 Paper】Playing Atari with Deep Reinforcement Learning

看似比较简单的更新的trick，在深度强化学习里面往往是比较重要的method，原因是因为当你神经网络变得复杂的时候，很多以前经典的算法都会不那么work，而如果能真正理解深度神经网络，而应用在强化学习里面，这些看起来像一些trick的东西，往往会是深度强化学习里面最重要的算法。

VolodymyrMnih, KorayKavukcuoglu, David Silver et al. Playing Atari with Deep Reinforcement Learning. NIPS 2013 workshop.
VolodymyrMnih, KorayKavukcuoglu, David Silver et al. Human-level control through deep reinforcement learning. Nature 2015.

我的微信公众号名称：深度学习与先进智能决策
微信公众号ID：MultiAgent1024
公众号介绍：主要研究分享深度学习、机器博弈、强化学习等相关内容！期待您的关注，欢迎一起学习交流进步！

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 196,302评论 5赞 462
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 82,563评论 2赞 373
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 143,433评论 0赞 325
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,628评论 1赞 267
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,467评论 5赞 358
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,354评论 1赞 273
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,777评论 3赞 387
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,419评论 0赞 255
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,725评论 1赞 294
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,768评论 2赞 314
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,543评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,387评论 3赞 315
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,794评论 3赞 300
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,032评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,305评论 1赞 252
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,741评论 2赞 342
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,946评论 2赞 336