- 看了看之前写的那篇博客，感觉并没有真的总结清楚DRL是什么，难怪我一直不懂什么是DRL，原来是以前就没学好，所以现在从RL开始了解了解，了解RL之后再去了解DRL。
- setup大部分，还是来自原本的博客，加了点注释。reform了一下，懒得再打公式了。
什么是RL
简介
什么是MDP Markov Decision Process
- MDP基于一种假设：未来取决于当前
- 马尔可夫性质：系统下一时刻的状态仅由当前时刻的状态决定。
- \(P(s_{t+1}|s_t)=P(s_{t+1}|s_t,s_{t-1},...,s_1,s_0)\)
- agent在environment下， take action, 使得有一定概率从当前状态转到另一个状态。
- 马尔可夫决策四元组：\(E=<S, A, P, R>\)
- \(P: S \times A \times S \to R\) ，状态转移概率。
- \(R: S \times A \times S \to R\) or \(R: S \times S \to R\): 奖赏。
Set Up
-
action: 例如你给不给西瓜浇水。
-
state: observation的集合就作为agent所在的状态state。例如你看这个西瓜是缺水，还是健康还是溢水。
-
observation：每个时间片，agent都是更剧当前的观察来确定下一步的动作
-
reward: agent执行了action，与环境交互后，环境会变化，变化的好坏就用reward表示。
-
policy: state到action的过程
- 两类policy：
- 找\(a=\pi(s)\) ：一一对应表示， Deterministic policy(确定性策略)，输入一个状态，输出一个确定的action。（例如，如果西瓜缺水就浇水）
- 找\(\pi(a|s)\)：概率表示，Stochastic policy（随机性策略），输入一个状态s，输出每个action a的概率分布。（例如，如果西瓜缺水那就0.6的概率浇水，0.4的概率不教水）。
- 两类policy：
-
任务：找到一个最优的策略policy从而使得reward最好。
长期累积奖赏
- 通常有两种计算方法：
- T步累积奖赏：\(E[\frac1T\sum_{t=1}^T r_t]\)
- λ折扣累积奖赏：\(E[\sum_{t=0}^{+\infty}\lambda^tr_{t+1}]\)
- \(G_t=R_{t+1}+\lambda R_{t+2}+...=\sum_{k=0}^{\infty}\lambda^{k}R_{t+k+1}\)
- \(G_t\)又称 cumulative discounted reward （累积折扣奖励）
- 其中R为Reward。
- \(\lambda\)为discount factor（折扣因子），一般小于1
- 越大：看得越远，注重长期奖励
- 越小：越短视，注重眼前奖励
- 实际上除非整个过程结束，否则显然我们无法获取所有的reward来计算出每个状态的Return。
状态值函数 State Value Function
- v(s): 表示一个状态未来的潜在价值。
- 定义上看，value function就是Return的期望
- \(v(s)=E[G_t|S_t=s]\)
- 计算：根据有两种累积函数的计算方法，有对应状态值函数：
- \(v_\lambda ^\pi(s)=E_\pi[\sum_{t=0}^{+\infty}\lambda^tr_{t+1}|s_0=s]\)， λ折扣累积奖赏。
- \(v_T ^\pi(s)=E(\frac1T\sum_{t=1}^T r_t|s_0=s)\)，T步累积奖赏。
- \(s_0\): 初始状态。
- \(a_0\): 初始状态上采取的第一步动作。
动作价值函数 State-Action Value Function
- \(Q^\pi(s,a)\)：表示从状态s，采取动作a后再采用策略π带来的累积奖励。
- 如果知道了每个动作的价值，那么就可以选择一个价值最大的动作去执行了。
- 这里使用的reward和之前的reward不一样。
- 之前State Value Function对应的reward是多种动作对应的reward的期望值。
- 这里的是执行完这一个动作a得到的reward。
- 注意看两个函数的参数数量都不一样。
- 计算：根据有两种累积函数的计算方法，有不同的Q函数：
- \(Q^\pi(s,a)=E[r_{t+1}+\lambda r_{t+2}+\lambda^2 r_{t+3}...|s,a]=E[r+\lambda Q^\pi (s',a')|s,a]\)
K-armed Bandit
问题
- multi-armed bandit, k-armed bandit.
- 单步强化学习任务对应了一个理论模型”k-armed bandit“。
- 一个有k个臂的machine，你完全不知道摇哪个臂得到的reward最大，你肯定是想要有最大的cumulative reward，那怎么办呢？
- Exploration-only：你可以将尝试机会平分给所有的臂，玩完之后，你就会得到每个臂的expected reward。
- Exploitation-only：你就只按当前知道的reward期望最大的那个来玩，如果有多个reward期望最大那就随机选来玩。
- Exploration-Exploitation dilemma：但是明显，exploration and exploitation是矛盾的，你需要平衡它们来玩游戏。
ε-Greedy
- ε：有ε的概率会去explore，有1-ε的概率会去exploit。
- Q(k)：记录第k个arm在尝试n次下的平均奖赏。
- \(Q(k)=\frac 1n \sum_{i=1}^nv_i\)：得记录每轮的v，和一共尝试了多少次。
- 增量计算式：每尝试一次就更新
- \(Q_n(k)=\frac 1 n((n-1)Q_{n-1}(k)+v_n) = Q_{n-1}(k)+\frac 1 n (v_n - Q_{n-1}(k))\).
- 只用记录尝试次数n 和 最近的平均奖赏\(Q_n(k)\).
- 算法
Softmax
- 基于当前的平均奖赏来对exploration, exploitation进行折中。
- Softmax算法中的摇臂概率的分配基于Boltzmann分布：
- τ>0：称为"温度"，τ越小则平均奖赏高的arm被选中的概率越高。
- τ趋于0时，Softmax 趋于 exploitation-only。
- τ趋于无穷大时，Softmax 趋于 exploration-only。
- 算法
- τ用在了第四行，根据摇臂概率来选这次挑哪个arm。
Model-based Learning
- Model-based Learning：对多步强化学习任务，在模型已知的环境下进行训练。
- 模型已知：即马尔科夫决策过程四元组\(E=<S, A, P, R>\)都已知。
- 后续假设状态空间S和动作空间A已知。
- 有模型的时候，一般使用Dynamic Programing：policy evaluation, value iteration, policy iteration.
- Model-free的一些RL methods also works for model-based learning.
策略评估
- 评估这个策略好不好，那就得求出它的V, Q。
- MDP具有马尔可夫性质：系统下一时刻的状态仅由当前时刻的状态决定，不依赖之前的状态。所以V函数由很简单的递归形式，这样的递归等式叫Bellman等式。
- 是由于我们这是在模型已知情况下讨论的，P和R已知，才能继续全概率展开。（所以model-free的情况下，无法展开）
- 基于T步累积奖赏的策略评估算法：
- 从\(V_0^\pi\)开始，一步步算到\(V_T^\pi\)。
- 得到V之后就可以直接计算State-action function Q:
- 其实从这里可以看出Q和V的关系：
- V(s)不知道action，所以把所有action情况考虑一遍再求期望。
- Q则是确定action之后的reward期望。
策略改进
- 你通过策略评估，发现这个策略不是最好的，所以就改进。
策略迭代 值迭代
- 策略迭代（Policy Iteration）：求最优解的方法，先评估策略，然后改进策略，再评估，再改进...
- 值迭代 (Value Iteration)：策略迭代和值函数的改进是一致的，对Policy iteration进行改进的算法。
Model-free Learning
Monte-Carlo Approach
- 蒙特卡罗强化学习：由于模型未知，不能直接评估策略。通过多次“采样”，然后求平均累积奖励作为期望累计奖赏的近似。
- 采样：从起始状态开始，通过使用某个策略进行采样可以得到一条轨迹。\(<x_0, a_0, x_1, a_1, ..., x_{T-1}, a_{T-1}, ..., x_T, a_T>\)
- 所以是要对多条轨迹进行平均，得到状态-动作值函数的估计。
- ε-贪心法：因为可能使用确定性策略，导致总是走出同样的轨迹，所以用ε-Greedy。
- On-policy（同策略）蒙特卡罗强化学习算法
- On-policy：被评估和被改进的是同一个策略。
- Off-policy 蒙特卡罗强化学习算法
Temporal Difference Learning
- 时序差分学习，TD learning：结合了动态规划和蒙特卡罗方法（通过多次尝试后求平均来作为expected cumulative reward，求平均的时候用的是"批处理式"的）的思想。
- TD learning learns V(s) directly from experience with TD eror, with bootstrapping, in a model-free, online, and fully incremental way.
- TD learning is a prediction probelm.
- TD Learning：求平均的过程通过增量式进行。
- 将\(\frac 1 {t+1}\)替换为\(\alpha _{t+1}\)。一般将\(\alpha _{t+1}\)设为一个较小的正数α。
- 更新步长()\(\alpha\)越大，越靠后的cumulative reward就越重要。
- SARSA：每次更新值函数需要知道前一步的State, Action, Reward, State(next), Action(next)，所以叫Sarsa算法。
- 是个同策略算法。
- Q-Learning：将Sarsa修改为off-policy算法。
- tabular Q(0) learning:
- 注意和tabular SARSA(0) 区别。SARSA是通过Q来选action，并把这个action作为下一个action。但Q-learning只是用这个Q最大的action计算Q值，并不直接用这个action作为future action。
MC v.s. TD
- 注意TD方法中，考虑了可能是sample不够的因素，有sa的恰好后面sb的那个episode恰好是0，但是sb的expected value 是3/4，所以TD加上了sb的V值。
模仿学习 Imitation Learning
- 模仿：给你一个专家浇西瓜的轨迹，你让机器人学学人家专家怎么浇水的。
直接模仿
- 给你m条专家的决策轨迹数据\(\{\tau_1,\tau_2,...,\tau_m\}\)。
- 每条轨迹包含状态和动作。 \(\tau_i=<s_1^i,a_1^i, s_2^i,a_2^i,...,s_{n_i+1}^i>\)
- 将所有轨迹的所有"状态-动作对"抽出来，构造一个新的dataset
- 把状态作为特征，把action作为label，进行有监督学习，得到一个初步策略。
- 之后再通过强化学习基于环境反馈进行修改。
逆强化学习
- background：设计奖赏函数困难。
- 逆强化学习（inverse reinforcement learning）：从人类专家的范例数据中反推奖赏函数。
- 推导
- 算法
Reference
- 整理自网络资源
- 《机器学习》周志华
- Deep Reinforcement Learning: An Overview
- 李宏毅 DRL, RL相关视频