强化学习中的无模型控制

在上一篇文章强化学习中的无模型预测中，有说过这个无模型强化学习的预测问题，通过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

Two categories of 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

强化学习中的无模型控制

其算法也是大体分为两步：

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

其算法流程分为以下几步：

At state $s$ , take action $a$ ;
Observe reward $r$ ;
Transit to the next state $s^{\prime}$ ;
At state $s^{\prime}$ , take action $a^{\prime}$ 。

Updating action-value functions with SARSA：

$Q(s,a) \leftarrow Q(s,a) + \alpha(r + \gamma Q(s^{\prime},a^{\prime})-Q(s,a))$

强化学习中的无模型控制

SARSA算法的整个流程如下所示：

强化学习中的无模型控制

NOTE: on-policy TD control sample actions by the current policy, i.e., the two ‘ $A$ ’s in SARSA are both chosen by the current policy。

Off-Policy Learning

我们能否从 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，其兼容性更强一点。

Why off-policy learning is important?

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呢？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)$

Cannot use if $\mu$ is zero when $\pi$ non-zero
Importance sample can dramatically increase variance

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)$

Much lower variance than Monte-Carlo importance sampling
Policies only need to be similar over a single step

上述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)$ ，其实tack这个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 update：

$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)$

Why Q-learning is an off-policy control method?

Learning from SARS generated by another policy $\mu$
The first action aand 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})$ 。