标签：周博磊 强化学习 视频课程
强化学习的目的：最大化长期奖励
根据智能体能看到的状态可以分为两种情况：
- Full observability：智能体可以看到所有的环境状态，比如马尔科夫决策过程MDP
- Partial observability：只能部分观测到环境，Parital Observce MDP
RL agent的组成：
- policy：Agent's behaviour function
- value function: how good is each state or action
- model: agent's state representation of the environment
策略是智能体的决策模型，是一个从状态到动作的映射。
有两种策略：
- Stochastic policy：给出的是所有行为的一个概率$\pi (a|s) = P[A_t=a|S_t=s]$
- Deterministic policy:$a^*=argmax_a\pi(a|s)$
以雅达利游戏为例，输入为每一帧的图像，输出为往上走或往下走两个动作
价值函数：折扣的未来奖励的加和，即进行行为之后未来可以获得什么样的奖励。
我们的目的是在尽量少的时间内尽可能多的获得奖励，因此要有折扣率。
Q函数用来选择最佳的动作
模型根据当前状态和动作进行状态转移。
另一个组成是奖励函数，在当前状态下采取某个行为会获得什么样的奖励。
例子：走迷宫
- 每走一步奖励-1
- 动作为上下左右
根据已知和未知可以分为三种Agent
Value-based agent
- Explicit:价值函数
- Implicit:策略（可以根据价值函数推断）
Policy-based agent:
- Explicit:策略
- No value function
Actor-Critic agent:
- Explicit: policy and value function
另外可以根据Agent是否有环境模型来分类（是否对状态转移去进行估计，或者对环境进行建模）
Model-based
- Explicit: model
- may or may not have policy and/or value function
Model-free
- Explicit: value function and/or policy function
- No model
智能体只能通过试错来理解采取行为后的奖励。
- Exploration: 尝试新事物，探索未知
- Exploitation：只选择已知的最优解
trade-off: 如何牺牲短期的奖励来获得长期最优解
强化学习是理论与实现相结合的学科，最终结果都需要落在实践上，通过实践来证明。
环境：
CartPole环境
- 动作：左移、右移
- 状态：杆的位置、杆的移动速度、杆的角度
- 奖励：尽可能长的存活
Pong from pixel，深度强化学习
马尔科夫决策过程中对环境是全可观测的，但是部分可观测环境也可以建立马尔科夫。
马尔科夫性质：一个状态是马尔科夫的，当且仅当其只受过去状态的影响
马尔科夫奖励过程：马尔科夫链+奖励函数，奖励函数是一个期望，在到达某个状态之后能获得多少奖励。
Return是当前获得的价值，Reward是一次获得的奖励，return是reward的期望，value是return的期望
为什么需要折扣系数Discount Factor：
- 避免带环的马尔科夫链
- 表示出不确定性，希望尽可能快的得到奖励
- 对立刻奖励的偏向性
- 当系数=0时，只关系当前奖励；系数=1时，未来奖励与现在奖励相同。
return的计算如上，那value of state该如何计算？
BellmanEquation：当前状态的价值 = 当前状态的奖励+未来的折扣奖励和
定义了状态之间的迭代关系
直接通过矩阵求逆可以解出V，但是矩阵求逆的计算量是O(n^3)
只能用迭代方法来计算状态较多的马尔科夫过程：
- 动态规划
- 蒙特卡洛方法
- Temporal-Difference learning（1与2的结合）
一次轨迹作为一次采样，在轨迹底部更新过去的状态。相当于模拟
利用Bellman Equation进行状态转移，并不断更新状态值。
与奖励过程不同，有一个决策过程：当前状态与在当前状态所采取的行为共同决定未来状态的走向。
Policy:定义了在每个状态应该采取什么样的行为，是一个概率的表示（70%往左走，30%往右走），或者也可以是一个值。
这个概率函数是静态的，不同时间点的决策实际上都是对同一个概率函数进行采样。
马尔科夫决策过程与马尔科夫奖励过程的转换： 已经知道Policy的时候可以进行
下图很好的说明了如何计算是V(s)
可以对MDP中的价值函数进行定义，与Policy相关
同时引入了Q函数，某一个状态、某一个行为得到某个奖励的期望
已经知道MDP和采取的策略，对策略进行评估，计算v^\pi(s)
- Prediction：给定MDP和一个策略，输出value function（评价一个指定策略）
- Control：给定MDP，输出最佳的value function以及策略（找寻最佳的策略）
上述两点都可以通过动态规划来解决
动态规划：将问题分解成最佳子结构，将子结构的解组成最优解
马尔科夫过程符合上述性质，只要子状态能够得到一个值，未来状态可以推断出来。
Policy Evaluation是什么？
给定MDP，给定policy，可以估算出价值函数V
得到上一时刻的V(t)，可以得到下一时刻，反复迭代可以计算出最终结果（式14）
gridworld例子
没有MDP，去搜索一种Policy，使得value最大。此时这个策略为最佳策略，称此MDP环境被解。
可以证明存在唯一的最佳价值，但不一定只有一个策略。
可以通过对Q函数极大化来获得最佳的价值。Q函数是关于状态和动作的函数，如果采取某种行为使Q函数最大化，则该行为为最佳的行为。、
一种策略方法是Policy Search
有有限种状态，直接穷举一遍，计算出value function，并进行对比。
问题是效率低下，而且不一定能够进行穷举
另外两种：policy iteration和value iteration
对于事先确定好的MDP过程，最佳策略是静态的、决定性的，但不一定是唯一的。
两个步骤：
- Policy Evaluation，评价已有的策略，计算出V函数，推算出Q函数
- 在Q函数上取极大化（贪心搜索），改进策略
迭代进行上述两个步骤，直到收敛
上面Policy Iteration的第二个步骤，根据Q函数改进策略。
首先计算Q函数的最大值，然后基于此改进策略。
单调的递增过程如下，以上过程只会使得策略变得更好
更新终止时，策略取得最优。
为了得到每个状态最大的Value V*(s)，直接进行迭代
Policy Iteration和Value Iteration的对比，都是对MDP Control问题的解法
下节对应章节：第五章和第六章
本节课:
- Model-free prediction: estimate value function of an unknown MDP
- Model-free control: optimize value function of an unknown MDP
区别：是否已经知道MDP。
什么时候说MDP已经知道：Agent知道奖励函数R和转移矩阵P。此时等式中可以直接使用R和P。
但是现实生活中很多时候是不知道的，特别是转移矩阵P，有时候也不能很及时地获得奖励函数R。
Model-free算法，根据智能体和环境的交互获得轨迹数据，去估计一个状态的价值，改进策略。
基于采样的方法，让Agent和环境进行交互获得数据，进行估计。
只能用于有终止的马尔科夫决策过程
简单概括：
可以将平均值写成叠加形式，这样可以只用记录一个值。
其中\alpha为learning rate，通过控制这个值可以调整算法的过程。
MC与DP的差异
DP中需要使用bootstraping的方法去估计，估计一个量是通过对之前估计的量的迭代来进行的。DP可以通过一个加和来完成迭代，并期望其收敛。
MC方法是通过实际得到的收益来更新它。给定一个轨迹数据，用这个轨迹数据更新其经过的所有状态，跟这个轨迹没有关系的状态是没有更新的。
MC方法的好处：
- 可以在不知道奖励函数R和转移矩阵P的情况下工作。
- MC方法只需要更新轨迹上的状态，因此更新的成本较低。DP需要更新所有状态，在已知状态很多的时候更新代价高。
TD是介乎MC和DP之间的方法：
- model-free方法，不需要知道奖励函数R和转移矩阵P
- 结合了bootstarping思想，可以在不知道完整的轨迹数据时完成更新。
对于给定的policy，如何计算价值函数：
最简单的TD算法：TD(0)。每次向前走一步，并进行估计。
TD和MC的区别
通过调整TD的步长值，可以使得算法在MC和DP之间进行转变。比如TD的步长取无穷时，TD实际上等同于MC，用所有实际获得的奖励来更新return。否则，TD取0的时候，实际上是DP的局部更新。
Bootstrapping and Sampling的区别
在不知道R和P的时候，就无法计算出Q函数。因此，使用Generalized policy Iteration with Action-Value function
使用MC方法来估计Q函数。
如何确保MC算法能有足够的探索：epsilon-greedy
推导：此时价值函数单调递增
算法主体：
只有同一个Policy，用这个Policy来采集数据，同时使用这个Policy来进行更新
与TD类似，直接估计Q表的值。
n-step Sarsa
On-policy学习的时候只利用一种策略，同时用这个策略进行轨迹的采集与优化。
Off-policy学习，在学习过程中保留两种不同的策略：
- 保证一个优化的最佳策略
- 留存一个用来探索的策略，可以更激进的对环境进行探索。
学习的是一个策略，但数据采集又是通过另一个策略。
优化策略可以不直接与环境进行交互，在探索策略得到轨迹之后再进行优化。
好处：
- 可以使用更激进的策略学到最优解法
- 学习其他Agent/专家的做法
- 利用老的策略产生的轨迹
Q-Learning算法
- target policy：选择使Q值最大的动作
- behaviour policy：使用epsilon-greedy进行搜索
具体算法
- Sarsa的两个动作是用同一个policy采样得到的。
- Q-Learning的第二个动作是想象的解
例子：Cliff Walk环境
sarsa会倾向于保守策略，reward会逐渐往上走；Q-Learning会倾向于激进策略，学习过程中奖励相对会更低。
但QLearning得到的最佳策略会更接近于实际的最佳策略
