Deep learning helps us handle unstructured environments and RL provides a formalism for behavior
使用深度学习而不用人工去设计特征不仅仅代表节省工作量，很多时候神经网络学出来的特征都比人工设计的要好。
Deep models are what allow RL to solve complex problems end to end
- Advances in DL
- Advances in RL
- Advances in computational capability
Beyond learning from reward, for we human beings, we always have some experience only for once or twice 奖励函数决定了我们是否可以在现实世界中使用强化学习这种时序学习
- Learning reward functions from examples (inverse RL)
- Transfer knowledge between domains (transfer learning , meta learning)
- Learning to predict and using prediction to act (model-based learning)
Interpret rich sensory inputs and choose complex actions, like the DRL does because deep means it can process complex sensory input and RL means it can choose complex actions. That's why DRL is so important now.
- Acquire high degree of proficiency in domains governed by simple, known rules
- Learn simple skills with raw sensory inputs, given enough experience
- Learn from imitating enough human-provided expert behavior
- Humans can learn incredibly quickly but Deep RL methods are usually slow 人总是可以学的很快
- Humans can reuse past knowledge but Transfer learning in deep RL is an open problem 人总是可以用过去的经验
- Not clear what the reward function should be 奖励函数该是什么是一个问题
- Not clear what the role of prediction should be. Should we learn from trial and error or prediction or both? 不清楚预测在这个过程种的作用，我们是应该只通过试错还是通过先预测还是把这两个结合起来。
这几块前面都讲过了，就不再赘述了。
轨迹trajectory：$$\tau:=\left(\mathbf{s}{1}, \mathbf{a}{1}, \ldots, \mathbf{s}{T}, \mathbf{a}{T}\right)$$
任意一条trajectory的概率：$$p_{\theta}\left(\mathbf{s}{1}, \mathbf{a}{1}, \ldots, \mathbf{s}{T}, \mathbf{a}{T}\right)=p\left(\mathbf{s}{1}\right) \prod{t=1}^{T} \pi_{\theta}\left(\mathbf{a}{t} \mid \mathbf{s}{t}\right) p\left(\mathbf{s}{t+1} \mid \mathbf{s}{t}, \mathbf{a}_{t}\right)$$
$$\begin{array}{l} p\left(\left(\mathbf{s}{t+1}, \mathbf{a}{t+1}\right) \mid\left(\mathbf{s}{t}, \mathbf{a}{t}\right)\right)= p\left(\mathbf{s}{t+1} \mid \mathbf{s}{t}, \mathbf{a}{t}\right) \pi{\theta}\left(\mathbf{a}{t+1} \mid \mathbf{s}{t+1}\right) \end{array}$$
强化学习的目标：最大化所有轨迹上能获得的reward总和的期望：$$\theta^{\star}=\arg \max {\theta} E{\tau \sim p_{\theta}(\tau)}\left[\sum_{t} r\left(\mathbf{s}{t}, \mathbf{a}{t}\right)\right]$$
当task是finite horizon，也就是说task是回合制的，从起始到结束之间的状态是有限的，假设是小于T的。那么就可以RL的goal进行转化：
$$\theta^{\star}=\arg \max {\theta} E{\tau \sim p_{\theta}(\tau)}\left[\sum_{t} r\left(\mathbf{s}{t}, \mathbf{a}{t}\right)\right]=\arg \max {\theta} \sum{t=1}^{T} E_{\left(\mathbf{s}{t}, \mathbf{a}{t}\right) \sim p_{\theta}\left(\mathbf{s}{t}, \mathbf{a}{t}\right)}\left[r\left(\mathbf{s}{t}, \mathbf{a}{t}\right)\right]$$
将对于所有trajectory的期望转化为对于在trajectory在从1～T步长上的可能到达的状态得expected reward，进而对这个目标进行最大化。那么我们也就最多只需要计算在T步之内的结果，从而将复杂抽象的trajectory具体化了。
当task是infinite horizon的情况下，此时的T是无穷的。
我们首先来证明一下，$$p\left(\mathbf{s}{t}, \mathbf{a}{t}\right)$$是否是一个稳态分布，$$\mu=p_{\theta}(\mathbf{s}, \mathbf{a})$$，$$\mu=\mathcal{T} \mu$$，$$(\mathcal{T}-\mathbf{I}) \mu=0$$，u是T的特征值为1的特征向量，在大部分情况下，这个特征向量都是存在的。因此我们就证明了$$p\left(\mathbf{s}{t}, \mathbf{a}{t}\right)$$是否是一个稳态分布。
那么在进入stationary之后，由于stationary前的state是有限项，而stationary后的state是无限项，所以整个trajectory的期望累积reward其实就是由稳态后的state决定，因此只要找到的stationary state-action是最大reward的，那么最终累积reward就是最大的。
$$\begin{array}{r} \theta^{\star}=\arg \max {\theta} \frac{1}{T} \sum{t=1}^{T} E_{\left(\mathbf{s}{t}, \mathbf{a}{t}\right) \sim p_{\theta}\left(\mathbf{s}{t}, \mathbf{a}{t}\right)}\left[r\left(\mathbf{s}{t}, \mathbf{a}{t}\right)\right] \rightarrow E_{(\mathbf{s}, \mathbf{a}) \sim p_{\theta}(\mathbf{s}, \mathbf{a})}[r(\mathbf{s}, \mathbf{a})] \ (\text { in the limit as } T \rightarrow \infty) \end{array}$$
也可以留意到的是RL中通常是带有expectation的，这个expectation从优化的角度其实是起到十分重 要的作用的。如果reward function本身是不smooth的：例如正常行驶的reward是1，掉海里的 reward是-1。而假设policy对于掉在海里的概率是
上面是一个强化学习的基本框架：首先有一个初始的policy，第一步是运行这个policy与environment进行交互，获得新的样本，这也就是橙色的部分。在得到一批数据之后，进行绿色部分的步骤，一方面可以利用数据来得到关于environment的model，另一方面也可以利用数据来进行policy evaluation。最后再利用上面的model或者是evaluation进行policy improvement。根据蓝色部分和绿色部分的差异，可以将不同类型的强化学习算法进行区分。
我们下来看一下，在上面的几个步骤中，哪些步骤会花费比较多的资源呢？
- 首先对于绿色的框框来说，如果我们只是评估最后返回的累积奖励，那么这个过程是trivial和fast的，但是如果我们要用model-based的方法去fit一个model，那么这个过程就会变得expensive。
- 然后对于蓝色的框框来说，我们通过拟合的model或者奖励去做梯度下降的时候也是比较expensive的
- 对于橙色的框框来说，如果是在一些现实的比如机器人、车等环境中，我们只能一倍速去做，因此这个过程也是比较expensive的，但是如果我们在MoJoCo等环境中，我们可以进行一万倍速的仿真，那这个过程就会变得trivial。
model-based的方法就是通过一定的方法学出状态概率转移矩阵，如下图所示：
在这个 a few options 中，会有几个常见的做法：
- Just use the model to plan (no policy)
- Trajectory optimization/optimal control (primarily in continuous spaces) essentially backpropagation to optimize over actions
- Discrete planning in discrete action spaces - e.g., Monte Carlo tree search
- Backpropagate gradients into the policy
- Requires some tricks to make it work
- Use the model to learn a value function
- Dynamic programming
- Generate simulated experience for model-free learner
除了上面图上提到的直接对Q值求argmax（这种情况并不需要进行显示地表示policy，直接通过Q推导即可，这时在value估计准确的情况下，可以保证improvement之后的policy至少不差于当前的policy。）还有其他的方法：我们会学习一个policy, 通过判定
如上图，基于这个目标，在采集到数据之后，进入绿色的evaluation部分。它直接计算采样到的trajectory的return：也就是累积reward，利用sample代替expectation，将它作为需要最大化的目标。在蓝色的improvement部分，计算这个累积reward关于policy的梯度，进行梯度上升，修正policy的参数，最大化累积reward。这也就是policy-based方法的基本迭代思路
actor-critic方法学习value function，但并不直接使用value function得到策略，而是利用value function辅助policy的学习。前面提到了policy-based方法中存在方差过大的问题，而value function的提出本身也就是在概括trajectory中的信息。但是如果我们还是想要利用policy gradient的方法进行学习，那是否能够有办法结合value function的优势的，这个也就是actor-critic方法的出发点了：这里在evaluation的部分评估了value function，而相比policy gradient，在蓝色的部分则是基于value function，用value function替代原先的RL goal中的累积reward，并对这个部分进行gradient，从而在降低方差的情况下进行了policy improvement。
Sample efficiency表征的是我们需要多少样本来学习一个好的策略，各个方法的sample efficiency的比较可以看下面的这个图：
这里需要注意几个点：
-
第一个是model-based的方法比model-free的方法具有更高的sample efficiency，这是因为如果我们能够学出一个model，最简单地我们可以通过这个model生成一些数据而不需要实际与环境去进行交互。
-
第二个是off-policy的方法比on-policy的方法具有更高的sample-efficiency，这是因为off-policy的方法可以在采样新的数据的情况下提升策略，而on-policy的方法一旦策略进行了更新，就必须去生成一些新的数据。
-
另外一个需要指出的是，sample efficient不代表run time efficient，因为许多时候学习效率还取决于算法运行的效率，对于样本的吞吐量。
-
为什么我们还要选择一下sample-efficiency的方法：因为这是一些取舍，比如off-policy经常要用importance sampling，使得算法变得更加复杂也增加了其不稳定性。
关于稳定性有灵魂三问：
- 方法收敛吗？
- 收敛到哪里？
- 每次都收敛吗？
监督学习而言，它就是朝着实际目标做gradient descent的，但是对于强化学习中的许多方法，情况大多数不是这样的。
-
Q-learning: fixed point iteration
$\quad$ fixed point iteration 不保证收敛 -
Model-based RL: model is not optimized for expected reward
-
Policy gradient: is gradient descent, but also often the least efficient!
首先对于value-based的方法而言，在tabular case下，通过contracting mapping，算法通常是可以保证收敛的。但是如果引入了function approximation，contraction性质就被破坏了，收敛保证也就因此失去了。另外，即使能够很好的拟合了bellman error，由于引入了bootstrap，实际上也不等同于expected reward。在最坏的情况下，基于值的强化学习方法不会收敛到任何点。
对于model-based的方法，model拟合误差最小化，这是可以收敛的，但是问题在于并不能保证好的model就能导出好的policy，两者之间还是需要进一步学习去得到的。
也就只有policy-based的方法才是真正向着RL的objective的方向直接做gradient descent的，虽然如果用神经网络，也可能出现局部最优的情况。
- 首先是是否fully observability，在value-based方法中通常是要求fully observability，主要是因为它是基于state去做学习的，所以state的完整性对于学习是比较重要的，如果每次观测到的同一个state的不同部分，那么就会导致confusion。一般而言，我们会通过recurrence去降低它的影响：加入多帧或者使用RNN、LSTM。
- 第二个是是否是episodic learning，在最原始的policy gradient中通常是要求episodic的，因为它需要估计到结束时的整段轨迹的reward。而一些model-based方法中也会有这样的要求。
- 第三个就是是否continuity或者smoothness，对于continuous value function learning中可能会有这个要求，因为有些方法往往是跟求导的链式法则相关。同样某些model-based的方法也会有相关的要求。
Value function fitting methods
- Q-learning, DQN
- Temporal difference learning Fitted value iteration Policy gradient methods
- REINFORCE Natural policy gradient
- Trust region policy optimization Actor-critic algorithms
- Asynchronous advantage actor-critic (A3C) Soft actor-critic (SAC) Model-based RL algorithms
- Dyna
- Guided policy search