在上一篇文章强化学习中的无模型预测中，有说过这个无模型强化学习的预测问题，通过TD、n-step TD或者MC的方法能够获得值函数，那拿到value之后如何获取policy呢？
Model-Free Control in Reinforcement Learning
在model free control中的第一个概念就是on-policy 和 off-policy，在现实中的很多问题都是这样的，我们得不到environment的白盒模型，我们就需要去与环境互动，获取经验数据，然后基于经验数据进行学习。或者是MDP的内部模型已知，但是状态空间、动作太大了无法对其采样。model free的方法就可以去解决这个问题。
On-and Off-Policy Learning
- 两类model-free RL
在model-free这个设定下面有两个概念，一个是on-policy learning一个是off-policy learning。
- On-policy learning
On policy “Learn on the job” ，意思是说马上要给policy喂进来的数据都是刚刚采出来的数据。
Learn about policy $\pi$ from experience sampled from $\pi$。
- Off-policy learning
Off-policy “Look over someone’s shoulder” 当前学习的策略$\pi$的数据从另外一个策略$\mu$采样出来的。
Learn about policy $\pi$ from experience sampled from another policy $\mu$。
Model-Free Policy Iteration
如果我们用state value去更新的话，我们就需要去知道state transition，而基于state-action value的情况就好很多：
- Greedy policy improvement over $V(s)$ requires model of MDP：
$$ \pi^{\text{new}}(s) = \argmax_{a \in A} \{ R(s,a)+\gamma \sum_{s^{\prime} \in S} \mathcal{P}_{sa}(s^{\prime})V^{\pi}(s^{\prime})\} $$
But we don't know the state transition probability. 如果我们基于state-action value更新的话我们就不需要知道state transition probability。
- Greedy policy improvement over $Q(s,a)$ is model-free
$$ \pi^{new}(s) = \argmax_{a \in A} Q(s,a) $$
因此计算state-value 和计算state-action value有本质的区别。之后的方法基本上都是基于state-action value的。
Generalized Policy Iteration with Action-Value Function
在给定某一个policy之后，我们就可以去算$Q_{\pi}$。以前的文章马尔可夫决策过程与动态规划算的是state value，这里算的是state-action value。得到这个$Q$之后我们就能够依据$\pi^{new}(s) = \argmax_{a \in A} Q(s,a)$得到我们的策略。
Control Policy
基于$Q$ value 我们具体怎么去做control policy？就是我们具体怎么来 choose action？
Example of Greedy Action Selection
在Greedy Action中每次都去选择state-action value最大的那一个：
$$ \pi^{new}(s) = \argmax_{a \in A} Q(s,a) $$
但是这里有问题，就是当你采样到了一个动作之后，拿到了reward，你之后就不会去选择探索其它的动作了。
The policy would be suboptimal if there is no exploration.
$\varepsilon$-Greedy Policy Exploration
最简单的办法就是让这个policy有一些随机，或者称之为exploration。于是就变成了：
- With probability $1-\varepsilon$, choose the greedy action.
- With probability $\varepsilon$, choose an action at random.
于是在状态$s$下选择动作$a$的概率$\pi(a|s)$可表示为如下形式：
$$ \pi(a | s)=\left\{\begin{array}{ll} {\epsilon / m+1-\epsilon} & {\text { if } a^{*}=\arg \max _{a \in A} Q(s, a)} \\ {\epsilon / m} & {\text { otherwise }} \end{array}\right. $$
$\varepsilon$-Greedy Policy Improvement
那$\varepsilon$-Greedy Policy能不能往前推进我们的state value呢？我们需要去证明一下：
- Theorem：For any $\varepsilon$-greedy policy $\pi$ ,the $\varepsilon$-greedy policy $\pi^{\prime}$ w.r.t $Q^{\pi}$ is an improvement, i.e. $V^{\pi^{\prime}}(s) \geq V^{\pi}(s)$。
$$ \begin{aligned} V^{\pi^{\prime}}(s)=Q^{\pi}\left(s, \pi^{\prime}(s)\right) &=\sum_{a \in A} \pi^{\prime}(a | s) Q^{\pi}(s, a) \\ &=\frac{\epsilon}{m} \sum_{a \in A} Q^{\pi}(s, a)+(1-\epsilon) \max _{a \in A} Q^{\pi}(s, a) \\ & \geq \frac{\epsilon}{m} \sum_{a \in A} Q^{\pi}(s, a)+(1-\epsilon) \sum_{a \in A} \frac{\pi(a | s)-\epsilon / m}{1-\epsilon} Q^{\pi}(s, a) \\ &=\sum_{a \in A} \pi(a | s) Q^{\pi}(s, a)=V^{\pi}(s) \end{aligned} $$
其中$m$表示$\text { actions }$个数，这里其实就是在证明，用$\pi^{\prime}$得到的state value与之前的$\pi$得到的state value是有所改进的。上述公式中推导比较难懂的就是$\sum_{a \in A} \frac{\pi(a | s)-\epsilon / m}{1-\epsilon}$，这一步了。这里把：
$$ \pi(a | s)=\left\{\begin{array}{ll} {\epsilon / m+1-\epsilon} & {\text { if } a^{*}=\arg \max _{a \in A} Q(s, a)} \\ {\epsilon / m} & {\text { otherwise }} \end{array}\right. $$
带入到$\sum_{a \in A} \frac{\pi(a | s)-\epsilon / m}{1-\epsilon}$就会发现，其实这也是个概率，一旦它是个概率，那么一定会小于等于$\max _{a \in A} Q^{\pi}(s, a)$。这里也就证明了其实 $\varepsilon$-greedy 是做到了policy improvement 这一步。
Monte-Carlo Control
一种比较经典的Control方法就是MC Control：
其算法也是大体分为两步Policy evaluation和Policy improvement：
- Policy evaluation: Monte-Carlo policy evaluation,$Q \approx Q^{\pi}$。
- Policy improvement: $\varepsilon$-greedy policy improvement。
MC Control vs. TD Control
MC Control中看一整个episode，然后estimate value 然后做更新，TD Control只是看一小个片段进行更新。
- Temporal-difference (TD) learning has several advantages over Monte-Carlo (MC) ：
Lower variance、Online、Incomplete sequences。
On-Policy SARSA
其算法流程主要分为以下4步：
- 在状态 $s$, 采取
action$a$ ; - 环境反馈
reward$r$ ; - 转移到下一个
state$s^{\prime}$; - 在
state$s^{\prime}$, 采取action$a^{\prime}$。
用SARSA更新action-value functions ：
$$ Q(s,a) \leftarrow Q(s,a) + \alpha(r + \gamma Q(s^{\prime},a^{\prime})-Q(s,a)) $$
SARSA算法的整个流程如下所示：
上述sarsa算法需要注意state-action中的‘$A$’都是基于current policy采样出来的。SARSA是一种非常典型的On-Policy方法，但是Off-Policy的算法往往更重要。
Off-Policy学习方式
我们能否从 policy $\mu(a|s)$ 采出来的数据 $\left\{s_{1}, a_{1}, r_{2}, s_{2}, a_{2}, \dots, s_{T}\right\} \sim \mu$ 去学习策略 $\pi(a|s)$ ？当$\mu(a|s) = \pi(a|s)$这个算法就是on policy的，因此off-policy的算法都可以做on-policy，其兼容性更强一点。
为什么我们需要off-policy的学习方式?
其实主要就是在数据利用上面会方便很多，on-policy的方法需要当前智能体去采样，然后学习一次之后智能体的策略就发生了改变，那这些数据就无法使用了。然而在现实生活中我们能够拿到很多很好的数据，是其他智能体所产生了，为了很好地去利用这些数据，我们需要off-poicy的采样方式。
- Learn from observing humans or other agents
比如在自动驾驶中，我们可以先学习一点人类经验数据，相当于做个预训练。
- Re-use experience generated from old policies
虽然是自己之前的数据，但是由于现在的参数和之前的参数不一样，所以off policy的方法可以重复使用之前的训练数据。
强化学习需要的data是非常大的，因为它有三个自由度的分布函数$R(s)$、$P_{sa}(s^{\prime})$、$\pi(a|s)$。想要从数据中把这些分布关系给学到，就需要大量地去采样这些样本，然后通过强化学习算法学到其中的关联。
因此使用之前的data就比较重要了。
还有一点就是商业上面就没办法使用当前采样出来的数据直接进行训练。比如像淘宝用强化学习做的推荐系统。
- Learn about optimal policy while following exploratory policy
- Learn about multiple policies while following one policy
Importance Sampling
那off-policy怎么来做off policy的learning呢？通常的做法都是引入Importance Sampling。Q值的更新可表达为以下形式：
$$ Q(s,a) \leftarrow Q(s,a) + \alpha(r + \gamma Q(s^{\prime},a)-Q(s,a)) $$
我们是拿后面采样出来的$Q(s^{\prime},a)$，去更新前面采样所得到的$Q(s,a)$，前面采样策略与后面采样策略不一样，那肯定就会有些问题。这个时候重要性采样就非常重要了。
Importance Sampling can estimate the expectation of a different distribution ：
$$ \begin{aligned} \mathbb{E}_{x \sim p}[f(x)] &=\int_{x} p(x) f(x) d x \\ &=\int_{x} q(x) \frac{p(x)}{q(x)} f(x) d x \\ &=\mathbb{E}_{x \sim q}\left[\frac{p(x)}{q(x)} f(x)\right] \end{aligned} $$
Re-weight each instance by $\beta(x) = \frac{p(x)}{q(x)}$ 。
这里把从分布$p$中采样的数据求期望，转变成了从分布$q$中去采样数据求期望。这里只是把每个数据的权重做了些许改变，因此在Importance Sampling里面我们往往也会去计算$\beta(x) = \frac{p(x)}{q(x)}$，甚至有机器学习专门去学习这个$\beta(x)$，然后去做一个比较好的Importance Sampling。
在机器学习里面，我们经常会优化这样一个式子：
$$ \min _{\theta} \frac{1}{|D|} \sum_{x \in D} \mathcal{L}\left(y, f_{\theta}(x)\right)=\mathbb{E}_{x \sim p(x)}\left[\mathcal{L}\left(y, f_{\theta}(x)\right)\right] $$
但很多时候我们拿到的数据并不满足$p(x)$分布，而满足$q(x)$分布，因此做个重要性采样就很好地解决这个问题。
Importance Sampling for Off-Policy Monte-Carlo
通过重要性采样我们仍然需要去计算值函数。比如我们如何使用策略$\mu$所获得的return去评估策略$\pi$? 依据Importance Sampling我们可以weight return $G_{t}$，对于一个episode，
$$ \left\{s_{1}, a_{1}, r_{2}, s_{2}, a_{2}, \dots, s_{T}\right\} \sim \mu $$
Multiply importance ratio along with episode：
$$ G_{t}^{\pi / \mu}=\frac{\pi\left(a_{t} | s_{t}\right)}{\mu\left(a_{t} | s_{t}\right)} \frac{\pi\left(a_{t+1} | s_{t+1}\right)}{\mu\left(a_{t+1} | s_{t+1}\right)} \cdots \frac{\pi\left(a_{T} | s_{T}\right)}{\mu\left(a_{T} | s_{T}\right)} G_{t} $$
表示在策略$\pi$下会以更多或者更小的概率去看到$G_{t}$，然后再以这个新的$G_{t}$去更新算法：
$$ V\left(s_{t}\right) \leftarrow V\left(s_{t}\right)+\alpha\left(G_{t}^{\pi / \mu}-V\left(s_{t}\right)\right) $$
当$\mu$为0的时候上述公式处理起来就会比较困难，但是往往这种情况出现地比较少，通常不给予考虑。重要性采样所带来的问题就是多引入了一个变量，因此其方差会增加。TD算法相比较MC算法会减少方差，因此很自然的一个想法是：可以将TD算法引入Importance Sampling来减少方差。
Importance Sampling for Off-Policy TD
将 Importance Sampling用在TD上面会更容易一点，因为TD算法只走一步。因此只有TD target $r + \gamma V(s^{\prime})$是在做importance sampling，so only need a single importance sampling correction ：
$$ V\left(s_{t}\right) \leftarrow V\left(s_{t}\right)+\alpha\left(\frac{\pi\left(a_{t} | s_{t}\right)}{\mu\left(a_{t} | s_{t}\right)}\left(r_{t+1}+\gamma V\left(s_{t+1}\right)\right)-V\left(s_{t}\right)\right) $$
这种方式相比较于Monte-Carlo importance sampling方差会大大降低，因为此时需要在a single step上保持similar。
上述importance sampling过程是一个unbias过程，但是variance可能特别大，因为$\mu\left(a_{t} | s_{t}\right)$可能特别小，一除就变大了。
因此在做off-policy的时候，我们很少会用传统的importance的办法，它虽然可以做，但是不做改进的话还是不太好。
Q-Learning
Q-Learning focus 在state-action value上面，这一点具有特别深远的意义。我们是在更新$Q(s,a)$ 这样一个state-action value function，因为如果我们更新$V(s)$的话，它上来就需要策略，$V^{\pi}(s) = \sum_{a}\pi(a|s)(R+V^{\pi}(s^{\prime}))$。而如果更新的是$Q(s,a)$，其实take这个action跟policy没有关系，无论policy是什么，我都会去更新$Q(s,a)$，也就是state $s_{t}$和$a_{t}$和policy是解耦合关系，之后环境给及时奖励 $r$ 和下一个状态$s_{t+1}$，这都是和环境有关的东西，我可以采样，但跟policy没关系，就不会像Importance sampling那样还需要除一下。之后的$a_{t+1}$不一样可能会产生点区别，前面的 $a_{t}$ 是用 $\pi$ 采样出来的，还是$\mu$采样出来的都没有关系。
上面说了这么多，其实就是需要注意：No importance sampling is required (why?)
$$ 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^{\prime}\right)-Q\left(s_{t}, a_{t}\right)\right) $$
- The target policy $\pi$ is greedy w.r.t. $Q(s,a)$：
$$ \pi(s_{t+1}) = \argmax_{a^{\prime}}Q(s_{t+1},a^{\prime}) $$
- The behavior policy $\mu$ is e.g. $\varepsilon$-greedy policy w.r.t. $Q(s,a)$：
$$ \begin{aligned} r_{t+1} + \gamma Q(s_{t+1},a^{\prime}) &= r_{t+1} + \gamma Q(s_{t+1},\argmax_{a^{\prime}}Q(s_{t+1},a^{\prime}))\\ & = r_{t+1} + \gamma \max_{a^{\prime}}Q(S_{t+1},a^{\prime}) \end{aligned} $$
因此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^{\prime}\right)-Q\left(s_{t}, a_{t}\right)\right) $$
为什么 Q-learning 会被称作一种off-policy control方法?
- Learning from SARS generated by another policy $\mu$
- The first action a and the corresponding reward rare from $\mu$
- The next action $a^{\prime}$ is picked by the target policy $\pi(s_{t+1}) = \argmax_{a^{\prime}}Q(s_{t+1},a^{\prime})$。
上述这么多就是为什么q-learning是off policy却不用importance sampling.
我的微信公众号名称：深度学习与先进智能决策
微信公众号ID：MultiAgent1024
公众号介绍：主要研究分享深度学习、机器博弈、强化学习等相关内容！期待您的关注，欢迎一起学习交流进步！
