强化学习

简介

强化学习是机器学习的一个分支，由如下几个元素组成：

• 状态(State):也就是所处的环境
• 动作(Action): 在每个状态下，有哪些可采取的动作
• 奖励(Reward): 在采取动作后进入新的状态后，获得的价值，可能为正或者负
• 策略(Policy): 在某个状态下，要如何采取行动

当然我们还可以增加agent和environment来统一整个模型:

整个过程可以如下描述:

1. 获得初始state
2. 根据policy选择action
3. 由agent执行action
4. 执行action后，获得环境返回的reward和新state

而强化学习的目的就是，以state,action,reward(可以统称为environment)作为输入，获得输出policy使得通过这个policy能获得最大的reward

根据这些元素我们也可以对强化学习进行分类：

1.Model-free 和 Model-based

Model-free 即机器人不知道外界环境信息，只能在机器人执行每一步动作后从环境中得到反馈然后去学习，只能按部就班，一步一步等待真实世界的反馈，再根据反馈采取下一步行动。诸如Q Learning， Sarsa，Policy Gradients等算法。

Model-based 指机器人对环境有一定的了解，可以对环境进行建模，通过模型机器人再也不必等真实世界的反馈做出动作。可以这么理解，当机器人要学习的时候，由于有了环境的模型，机器人可以将建立的环境模型当做是真实世界，不断的学习。在模型世界中，选择学习情况最好的那一种。

2.基于概率和基于价值（value）

基于概率：是强化学习中最直接的一种，通过state（观测）直接输出下一步采取的action（动作）的概率，然后根据概率采取行动，所以每一种action（动作）都有可能被选中，只是可能性不同。诸如 Policy Gradient。

基于价值：输出所有动作的价值，相比基于概率的方法，基于价值的决策部分更为铁定，即选择价值最高的。诸如 Q Learning， Sarsa 等算法。

3.回合更新（Monte-Carlo update，蒙特卡洛更新）和单步更新（Temporal-Difference update）

回合更新：指游戏开始到结束整一个过程，只有等到结束后，才能够总结这个回合的所有转折点，再更新我们的行为准则。诸如Monte-carlo Learning 和 基础版的 policy gradient等。

单步更新：在游戏中的每一步都可以更新其行为准则（例如如何选择action等），不用等到整个过程都结束。诸如Qlearning、Sarsa 和升级版的 policy gradient 等都是单步更新的。

4.在线学习（On-Policy）和 离线学习（Off-Policy）

在线学习（On-Policy）：在当前时间当前采取的动作紧接着通过得到的反馈下进行学习。诸如 Sarsa 算法 和 Sarsa lambda 算法。

离线学习（Off-Policy）：可以根据过往的经验及数据进行学习，举个例子，就是白天收集的数据可以在晚上通过离线学习进行。诸如 Q-Learning，Deep-Q-Network 等算法。

项目中使用DQN就是一种model-free， value-based，td更新，off-policy的算法

价值 Utility

既然我们要找到policy使得价值最大化，那么首先要定义什么是价值。 简单的说，价值是一系列在某state采取某action后获得的reward的期望，而且我们要考虑到未来所有的可能性，而不是仅仅是当前的reward：

$$U\left(S_{0}\right)=\mathbb{E}\left[\sum_{t=0}^{\infty} \gamma^{t} R\left(S_{t}\right)\right]$$

也就是说，某一个state的价值，是这个state后所有reward的和的期望，而$\gamma$是一个discount factor，越大说明越考虑长远的价值，越小越考虑当下的价值。

Bellman condition

Bellman equation 说的是： 「如果从最佳选择的路径的末端截除一小部分，馀下的路径仍然是最佳路径。」换句话说，如果一系列的选择 A B C D E…… 是最优的，那么这系列除去开始的 A，那 B C D E …… 系列应用在后继的状态上也是最优的。就是一个类似动态规划的问题，我们用方程表示:

$$U^{*}(S)=\max _{a}\left\{R(a)+U^{*}\left(S^{\prime}\right)\right\}$$

也就是说，最佳的路径可以被划分为两个部分，当下的选择+余下的最佳路径

Delta rule

其实跟梯度下降很相似，就是逐步修改当前状态，使其慢慢接近最佳值，而调整的方向就是理想和当前状态的差值(梯度)

$$当前状态 = 当前状态 + \alpha(理想状态-当前状态)$$

其实$\alpha$就是常见的学习率

时序差分 Temporal difference (TD) learning

我们的目标是学习到每个state的价值(用于后面的policy)，那么将 delta rule 应用到 Bellman condition 上，去寻找真正的（理想的）价值，这就是 temporal difference learning。
让我们回顾一下：

1. 根据贝尔曼方程，我们可以描述每个状态的真实价值

$$U^{*}(S)=\max _{a}\left\{R(a)+U^{*}\left(S^{\prime}\right)\right\}$$

1. 根据Delta rule，我们知道如何使得当前状态的价值接近真实值 $$当前状态 = 当前状态 + \alpha(理想状态-当前状态)$$

那么将两者结合起来，同时假设我们的其他状态的价值 $\mathrm{U}\left(\mathrm{S}^{\prime}\right)$ 正确，就得到了时序差分的公式：

$$U(S) = U(S) + \alpha\left(R(S)+\gamma U\left(S^{\prime}\right)-U(S)\right)$$

$\alpha$依旧为学习率，括号里面是理想状态减去当前状态

Q-learning

对应到 Q-learning 中的q值，其实就是价值U的一个变形，U是对一个状态而言的价值，而Q是对应一个状态下采取action A的价值。我们希望价值最大，那么就可以获得两者之间的关系式：

$$U(S)=\max _{A} Q(A, S)$$

然后再代入之前的时序差分方程，就获得了更新Q值的方程：

$$Q(A, S) = Q(A, S) + \alpha\left(R(S)+\gamma \max _{A^{\prime}} Q\left(A^{\prime}, S^{\prime}\right)-Q(A, S)\right)$$

Action的选择

现在我们已经有了由state 和 action映射到q值的一个q表，那么每次在一个state的时候，我只需选择q值最大的动作就可以了。但是这只是理想状态，因为在建立时序差分的q值更新方程时，我们假设了其他状态的价值已经是正确的，然而实际上却不一定。所以，我们需要有一定的探索能力，这一能力可以通过引入$\epsilon-greedy$来实现。$\epsilon$是一个0到1之间的数，我们在每次选择动作的时候，有$\epsilon$的概率不选择q值最大的动作，而是随机选择其他动作，这样就增加了探索的能力。$\epsilon$的值也不是不变的，随着我们探索的内容增加，$\epsilon$可以逐渐递减以加快算法的收敛。

DQN 和其改进

因为Q表可能会占据极大的空间，可以使用神经网络的映射来代替Q表，如下图

输入为一个状态，输出为这个状态下每个动作相应的q值

经验池

Experiment replay： DQN 有一个记忆库用于学习之前的经历。Q-Learning 是一种 off-policy 离线方法，可以学习当前经历的，也能学习过去的，甚至学习别人经历的。每次DQN更新的时候，都会从之前的经历进行学习。随机抽取的做法打乱了经历的之间的相关性，使得神经网络的更新更有效率。

Nature DQN

由于目标函数在更新后是变化的，训练十分不稳定。
我们采用两个结构完全相同的网络，一个用来训练映射，一个用来计算目标Q值（成为target网络），训练时target网络不更新参数。当训练一定epoch后再用训练网络的参数更新target 网络的参数。

Double DQN

在之前的DQN中，计算目标Q值和action的选择都是通过target网络完成，假设某个a被高估了，则target会选择被高估的a，那么这个Q值可能会虚高。DoubleDQN就把action的选择从target网络中拿出来放到训练网络中：

1. 在训练网络中选择Q值最大的action
2. 使用这个aciton到target网络估计Q值

这样双重决策，只要有一个函数没有高估q值，就可以缓解情况

Prioritized Replay

改变sample data的分布，增加那些损失大的样本从经验池中被选择的概率，因为loss打更新的步长也大，加快收敛