# RL **Repository Path**: tyloeng/RL ## Basic Information - **Project Name**: RL - **Description**: notes of reinforcement learning - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2020-06-23 - **Last Updated**: 2020-12-18 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # RL 增强学习（Reinforcement Learning，RL），是监督学习（supervised learning）、非监督学习（un-supervised learning）之外的一种学习范式。 ## Task RL 任务的场景是：智能体（agent）与环境（environment，env）进行一系列的交互，即 agent 根据所处的状态（status）决策出一个行为（action），执行之后会获得来自 env 的一个反馈/收益（reward），并转移到一个新状态，直到达到终止状态。 这样一次完整的过程称为一个 episode，看成一条轨迹（trajectory）：$\tau=\{s_0,a_0,(s_1,r_1),a_1,\dots,(s_t,r_t),a_t,(s_{t+1},r_{t+1}),\dots,(s_T,r_T)\}$。其中 $a_t$ 是 agent 根据 $(s_t,r_t)$ 做出的决策，如果将 $(s_{t+1},r_{t+1})$ 看作 env（上帝）根据 $a_t$ 作出的反应，那这个过程就看成 agent 跟 env 两者交互的过程。其中第 t 步行动 $a_t$ 的 reward 在 t+1 步才拿到，即有延迟。 agent 的目的是最终获得最大的总收益 $\sum_t r_t$，为此要学习决策（policy） $\pi:S\rightarrow A$，根据 status 选 action，选择的原则就是未来期望总收益 $\bar R$ 可以达到最大。 ## value-based v.s. policy-based 根据决策的方式，RL 算法可以分为 value-based 和 policy-based 两种。value-based 的方法学习一个价值函数 Q 来评估各候选 actions 的价值，并据此用某种策略选出 action；policy-based 的方法则直接输出选择各 actions 的概率。 在 value-based 方法中，因为策略 $\pi$ 是要学习的，而不是预知的，所以 $\bar R$（依赖于 $\pi$）的真实值不知道，要估计：在 $\pi$ 策略下处于 $s_t$ 状态、采取 $a_t$ 行动时，未来的总收益真实值记为 $\bar R_t=\sum_{i=t+1}^Tr_i=r_{t+1}+\sum_{j=t+2}^Tr_j=r_{t+1}+\bar R_{t+1}$，为评估 $a_t$ 的价值，用 $q(s_t,a_t)$ 估计 $r_t$ 、$Q(s_t,a_t)$ 估计 $\bar R_t$，套前面公式就是 $Q(s_t,a_t)=r_{t+1}+Q(s_{t+1},a_{t+1})$，但考虑到只有 $r_{t+1}$ 是真实的，$Q(s_{t+1},a_{t+1})$ 只是估计，可以加个衰减系数 $\gamma$ 来权衡对「眼前真实的 reward」和「估计的未来 reward」的考虑，于是：$Q(s_t,a_t)=r_{t+1}+\gamma q(s_{t+2},a_{t+2})+\gamma^2q(s_{t+3},a_{t+3})+\dots=r_{t+1}+\gamma Q(s_{t+1},a_{t+1})$。 有了 Q，决策就可以根据 $a=\mathbb{argmax}_{a'} Q(s,a')$ 选择，即 $\pi$ 的核心是 Q。 状态集 S 可以是有限取值的（棋盘）或无限的（cart-pole 中棒的倾斜角），行动集 A 也可以是有限（棋盘上下左右）或无限的（cart-pole 中小车要向左/右移动多少），不同设置中对 Q 的建模方式不同，用到不同模型： | | A 有限 | A 无限 | | :----: | :------------------: | :----: | | S 有限 | Sarsa，Q-learning | | | S 无限 | DQN，Policy Gradient | DDPG | ## Learning 学习主要是学 Q，使其尽量接近 $\bar R$。 训练数据的形式是 $(s_t,a_t,r_{t+1},s_{t+1},a')$。在产生数据时涉及到动态交互：对于状态 $s_t$ ，$a_t$ 是基于 agent（当前）的 $\pi$ 决策出的，然后再由 env 根据 $a_t$ 返回 $(r_{t+1},s_{t+1})$，再用某种方式基于 $s_{t+1}$ 决策一次得到 a’，其中 a’ 可以就是 $a_{t+1}$（on policy），亦可以不一定是（off policy）。这看起来像是 agent 用自己产生的数据训练自己，但监督信息的源头是 env 的 reward。 有个细节：为了搜索更多路径，agent 选 $a_t$ 未必按 Q 选，而是以概率 $\epsilon$ 进行随机选择、$1-\epsilon$ 的概率按照 Q 找最优 action，这个操作叫 $\epsilon$-greedy，思想类似 PageRank。 根据 Q 的公式，更新方式就是：$Q(s_t,a_t):=Q(s_t,a_t)+\alpha[r_{t+1}+\gamma Q(s_{t+1},a')-Q(s_t,a_t)]$，其中 $\alpha$ 是学习率，$r_{r+1}+Q(s_{t+1}, a')$ 看成对 $Q(s_t,a_t)$ 新的估计，又称 target。当达到终止状态时，新的估计就只剩 $r_{t+1}$ 而无 $\gamma Q(s_{s+1},a')$。 这有个时序差分（Temporal Difference，TD）的概念。更新公式类似 BP 的参数更新公式：$w:=w-\alpha\frac{\partial L}{\partial w}$，更新项是个微分。由于： - 差分是离散版微分； - $r_{r+1}+Q(s_{t+1}, a')$ 可以看作 $\bar R$ 在 t+1 时刻的估计、$Q(s_t,a_t)$ 是在 t 时刻的估计； 所以更新公式右边第二项可以看作 $\bar R$ 沿时间这一维的微分？ 学习流程就是：从初始状态 $s_0$ 开始，agent 基于 $s_t$ 选 $a_t$，env 根据 $a_t$ 反馈 $r_{t+1}$ 和 $s_{t+1}$，选出 a’，更新 Q，更新状态 $s_t:=s_{t+1}$，直到 episode 结束。 # Sarsa，Q-learning 当 S 和 A 都取值有限时，Q 可以用二维表表示，称为 Q-table。Sarsa 和 Q-learning 其中是两种算法，学习过程如前，两者的区别在于 a’ 和 $a_{t+1}$ 的关系，即 on-policy 和 off-policy 的分别： - Sarsa 只有一套策略，选 a’ 时，就按这套策略选，所以 $a'=a_{t+1}$，即用于更新的 a’ 就是用 $\epsilon$-greedy 选出来的下一步的实际 action $a_{t+1}$； - Q-learning 在更新 Q 和更新 $a_t$ 时用来两套不同的策略：$a'=\mathbb{argmax}_a Q(s_t,a)$，而用 $a_{t+1}$ 则是用 $\epsilon$-greedy 另自选一个，两者不必相同。 # DQN DQN 是 Q-learning 的扩展。当 S 扩展成无限的空间（如连续），Q 就不能用表格。但只要 S 维度有限，就可以用神经网络建模 Q，类似分类模型，输出给定 s 时各 actions 的 Q 值向量。 DQN 组织数据的方式跟 Q-learning 不同：Q-learning 的数据是在动态交互中实时获取的，用完就扔；而 DQN 采用 experience replay 的策略，将产生的数据存进数据池，以后会反复用到。因为神经网络一次输入一批，打乱数据的顺序可以促使网络学到的决策仅基于状态，而跟状态之间的关系无关，而 off-policy 的更新并不需要 $a_{t+1}$。 数据形式是 $(s_t,a_t,r_{t+1},s_{t+1})$，target 值就是 $r_{t+1}+\gamma\max_a\hat Q(s_{t+1},a)$，此处 $\hat Q$ 是所谓 target 网，用来算 target 的。由于新、旧预测都是 Q 网的输出，可能会训练不稳定，DQN 用了一个 trick：将 Q 网复制一份作为作为 target 网 $\hat Q$，其参数保持若干步训练不变，这样 target 的输出就相对稳定，然后定期从正常学习的 Q 网同步参数。 # Policy Gradient 策略梯度（Policy Gradient，PG）是一种 policy-based 的方法，可与 DQN 对比着看，根据输入的 s 输出各 actions 的概率向量，记为 $\pi_\theta(a|s)$，其中 $\theta$ 是参数，然后据此抽 action。 将一个 episode 的轨迹 $\tau$ 看作一个马尔可夫过程，则 $\tau$ 在策略 $\pi_\theta$ 下发生的概率为 $p_\theta(\tau)=p(s_1)\pi_\theta(a_1|s_1)p(s_2|s_1,a_1)\pi_\theta(a_2|s_2)\dots$，所以持策略 $\pi_\theta$ 的期望收益就是 $\bar R_\theta=E_{\tau\sim p_\theta}R(\tau)\approx\frac{1}{N}\sum_{i=1}^NR(\tau_i)$，而目标函数就是最大化期望收益：$\text{maximize}_\theta \bar R_\theta$。 先推下梯度： $$\begin{align}\nabla_\theta\bar R_\theta&=\nabla_\theta E_{\tau\sim p_\theta}R(\tau) \\ &=\int_\tau R(\tau)\nabla_\theta p_\theta(\tau) \mathrm{d}\tau \\ &=\int_\tau R(\tau)p_\theta(\tau)\frac{\nabla_\theta p_\theta(\tau)}{p_\theta(\tau)}\mathrm{d}\tau \\ &=\int_\tau [R(\tau)\nabla_\theta\ln p_\theta(\tau)]p_\theta(\tau)\mathrm{d}\tau \\ &\approx \frac{1}{N}\sum_{i=1}^N R(\tau_i)\nabla_\theta\ln p_\theta(\tau_i) \end{align}$$ ，用到蒙特卡罗估算积分。而 $\nabla_\theta\ln p_\theta(\tau_i)=\nabla_\theta\sum_{t=1}^{T_i}[\ln \pi_\theta(a_t|s_t)+\ln p(s_t|s_{t-1},a_{t-1})]$，由于其中 $p(s_t|s_{t-1},a_{t-1})$ 的项跟 $\theta$ 无关，一微分就是 0，所以 $\nabla_\theta\ln p_\theta(\tau_i)=\nabla_\theta\sum_{t=1}^{T_i}\ln \pi_\theta(a_t|s_t)=\sum_{t=1}^{T_i}\nabla_\theta\ln \pi_\theta(a_t|s_t)$，所以上面的梯度就是：$\nabla_\theta\bar R_\theta\approx\frac{1}{N}\sum_{i=1}^N R(\tau_i)\sum_{t=1}^{T_i}\nabla_\theta\ln\pi_\theta(a_t^{(i)}|s_t^{(i)})$。 梯度重需要修改下：因为轨迹 $\tau$ 不一定系**最优**的，所以梯度需要根据 reward 加权。对于 $\tau$，得到的 reward 序列记为 $\{r_t\}$，求加权**后**缀和 $\{G_t=\sum_{i=t}^T\gamma^{i-t}r_i=r_t+\gamma G_{t+1}\}$，加权之后的梯度变成：$\frac{1}{N}\sum_{i=1}^N R(\tau_i)\sum_{t=1}^{T_i}G_t^{(i)}\nabla_\theta\ln\pi_\theta(a_t^{(i)}|s_t^{(i)})$。 数据形式是 $(s_t^{(i)}, a_t^{(i)},G_t^{(i)})$，是针对每一个 action 的，所以据此设计对于某一个 episode 的轨迹 $\tau$ 其中第 t 个决策的损失：$L=-G_t\ln\pi_\theta(a_t|s_t)$，一求导就是上面嘅其中一项（省略常系数，但留下权重 $G_t$）。 # DDPG DDPG 是 DQN 的扩展，将 A 扩展成无限取值的空间。比如打方向盘转的角度，action 是连续量。 分两个网络： 1. 策略网络，记为 $P:S\rightarrow A$，根据 s 输出 a； 2. Q 网络，$Q:S\times A\rightarrow R$，估计 Q(s,a)，评估策略网络当前的 action 未来期望收益有几多，即评估 action 的价值； 架构有点像 GAN，P 根据 Q 的反馈更新，Q 就好像 DQN 那样，根据 reward 更新估计。对比两者优化目标： - DQN 是 $\text{argmax}_{a\sim\pi_w(a|s)} Q(s,a)$，只有 $\pi_w$ 嘅参数 w，a 是根据 $\pi_w(a|s)$ 用**确定**策略拣出来嘅； - DDPG 是 $\text{argmax}_{a\sim P_\theta(s)}Q_w(s,a)$，参数有 P 网的 $\theta$、Q 网的 w。P 同 DQN 的 $\pi$ 分别就是：DQN 的 A 有限，$\pi_w(a|s)$ 就是离散的概率分布，而 DDPG 的 action 是无限/连续取值的，所以用 P 预测； DDPG 对 DQN 的扩展，类似 DQN 对 Q-learning 的扩展： - DQN 将 S 展成无限，所以 Q-table 变成 $\pi_w$，但 A 还是有限的，$\pi_w$ 是离散分布，action 是基于 $\pi_w(a|s)$ 抽样（或者取最大概率者，亦可以理解成抽样）； - DDPG 继续将 A 扩展到无限， 即 S 同 A 都是无限的，即 $\pi_w$ 无限长，无办法再用概率向量表示，故此索性构造一个决策函数 P，直接输出 action，可以理解成 P 包了 $\pi_w$ 估计、抽样两步，只不过抽样过程亦是用网络做的，即用网络实现了抽样函数，对应 DQN 里的 np.random.choice、np.argmax。 Q 网更新过程同 DQN 一样，故此同样需要分 $Q_{learn}$ 同 $Q_{target}$，由于 Q 的 a 输入是由 P 网的输出给出的，所以 P 网亦分 $P_{learn}$ 和 $P_{target}$。 数据形式： $(s,a,r,s')$，而 a’ 就由 $P_{target}$ 输出，Q 的估计就是 $r + \gamma Q_{target}(s',a')$，更新 $Q_{learn}$ 的操作同 DQN。而更新 $P_{learn}$ 时，损失：$L=-Q_{learn}(s',a')$，用 $P_{learn}$ 计 a’ 套 $Q_{learn}$，优化时要**回避 $Q_{learn}$ 的参数**（stop gradient，或者指定 $P_{learn}$ var_list）。 为了稳定，定期同步两个 target 网参数时，可以用指数平滑：$W_{target}=\mu W_{learn}+(1-\mu)W_{target}$（W 指代两个 target 网的参数）。 生成数据时，可以对 action 加 [-1,1] 的高斯噪声，算是 augmentation？ # References 1. [强化学习（一）模型基础](https://www.cnblogs.com/pinard/p/9385570.html) 2. [MCMC(一)蒙特卡罗方法](https://www.cnblogs.com/pinard/p/6625739.html) 3. [马尔可夫链蒙特卡罗算法（MCMC）](https://zhuanlan.zhihu.com/p/37121528)