强化学习笔记

教材：蘑菇书

绪论

• 强化学习与监督学习的不同

  • 强化学习输入的样本是序列数据，而不像监督学习里面样本都是独立的。
  • 强化学习需要不断的试错探索。探索和利用是强化学习里核心的问题。需要在探索和利用之间找到一个权衡。
  • 强化学习里没有强监督者，只有奖励信号，并且奖励信号是延迟的。
  • 强化学习可以达到超人例子，而监督学习只能接近人。

• 一些术语和概念

  • 通过预演(rollout)获取一系列观测

  • 每个观测称之为一个轨迹(trajectory)

  • 轨迹是当前帧状态以及它的策略动作的序列：$(s_0, a_0, s_1, a_1,…)$

  • 每个观测结束，我们可以通过观测序列以及最终奖励(eventual reward)来训练智能体

  • 一场游戏成为一个回合(episode)或者实验(trial)

    强化学习 -> 深度强化学习
    
    将特征工程并入深度学习中
    

序列决策

智能体和环境

• 概念
  • 强化学习研究的问题是智能体与环境交互的问题

奖励

• 概念
  • 奖励是由环境给的一种标量的反馈信号，可以显示智能体在某一步的某个策略的表现。
  • 强化学习的目的是最大化期望的累积奖励

序列决策

奖励分为近期奖励和远期奖励，两者的权衡是强化学习的重要课题之一

历史是观测、动作、奖励的序列：
$$H_t=o_1, a_1, r_1,…,o_t,a_t,r_t$$

智能体的当前动作依赖于它之前得到的历史，整个游戏的(智能体）状态可以看为关于历史的函数：
$$s_t=f(H_t)$$

此外，环境有自己的函数：
$$s^e_t=f^e(H_t)$$

智能体自身的函数：
$$s^a_t=f^a(H_t)$$

观测与状态：

状态是对世界的完整描述
观测是对状态的部分描述（通常是智能体能获取的信息）

完全可观测和部分可观测

完全可观测指智能体状态和环境状态等价，此时通常建模为马尔可夫决策过程，此时$o_t=s^e_t=s^a_t$
部分可观测指智能体无法获取环境运作的所有状态，此时通常建模为部分可观测马尔可夫决策过程

动作空间

动作空间指给定环境下，有效动作的集合

离散动作空间
连续动作空间

智能体的组成成分和类型

策略，智能体用策略选择下一步的动作
价值函数，用价值函数评估智能体当前的状态
模型，表示智能体对环境状态的理解

策略

策略是一个函数，将输入状态映射到动作

随机性策略，使用$\pi$函数，$\pi(a|s)=p(a_t=a|s_t=s)$，根据概率分布选择动作。
确定性策略，$a = argmax\pi(a|s)$，容易被对手预测

价值函数

价值函数的值是对未来奖励的预测，用于评估状态的好坏。

折扣因子是将收益从时间向收益的转换

价值函数定义：
$$V_{\pi}(s)=E_{\pi}[G_t|s_t=s]=E[\sum_{k=0}^{\INF}\gamma^kr_{t+k+1}|s_t=s]，对于所有的s\inS$$

另一种价值函数Q函数，包含两个变量，状态和动作，定义为
$$Q_{\pi}(s)=E_{\pi}[G_t|s_t=s, a_t=a]=E[\sum_{k=0}^{\INF}\gamma^kr_{t+k+1}|s_t=s, a_t=a]$$

Q函数是需要学习的函数，可以获取某个状态需要采取的最优动作。

模型

模型由转移概率和奖励函数组成。

转移概率：
$$p^a_{ss’}=p(s_{t+1}=s’|s_t=s,a_t=a)$$

奖励函数值当前状态采取某动作，可以获得的奖励：
$$R(s, a)=E[r_{t+1}|s_t=s, a_t=a]$$

策略 + 价值函数 + 模型 => 马尔可夫决策过程

智能体分类

学习过程

基于策略的学习，基于策略的智能体，有策略梯度算法
基于价值的学习，基于价值的智能体，有Q学习，Sarsa算法，适用离散环境，连续环境下效果差
演员-评论员智能体，类似上述两者的集成

模型

有模型，通过学习状态的转移来采取策略，类似多了特征工程，可以一定程度减缓数据匮乏的问题
免模型，通过学习价值函数和策略函数做决策，泛化性强，消除了特征工程与真实环境之间的信息损失

学习与规划

学习与规划是序列决策的两个基本问题。

探索和利用

探索和利用是强化学习的两个核心问题。

探索-利用窘境

单步强化学习

知道每个动作的奖励
执行奖励最大的动作

单步强化学习对应K-臂赌博机模型。

仅探索法 (类似创业
仅利用法 (类似上班

马尔可夫决策过程

马尔可夫过程

掠过

马尔可夫性质

齐次马尔可夫，简化版

马尔可夫链

马尔可夫奖励过程

比马尔可夫链多了一个奖励函数

回报与价值函数

注意这里，回报、价值、奖励是不同的概念

奖励 r: 奖励是当前时刻触发的收益
回报 g: 回报是当前状态往后，直到最终时刻所获的所有收益
价值 v: 价值函数是回报的期望

贝尔曼方程

贝尔曼方程是价值函数的另一种形式

价值函数 = 即时奖励 + 未来所有奖励

可以通过价值函数的贝尔曼形式得到解析解，问题在于通常来说P是不知道的，需要学习

解析解的问题在于复杂度很高，对于高状态的矩阵算起来非常困难

迭代算法

蒙特卡洛

动态规划

时序差分学习

马尔可夫决策过程

决策过程中多一个智能体做决策的动作

价值函数 V

Q 函数

Q 函数是基于 V 函数的动作层面的空间划分

Q 是某个动作的价值，指站在此状态，选择某个动作的价值

V 是所有动作总空间的期望价值，指站在此状态，对所有动作的价值的期望

贝尔曼期望方程

先把价值函数写成Q函数的分解，再对Q函数作贝尔曼方程分解，得到一个贝尔曼期望方程的一种形式

先把价值函数写成即时奖励和后续奖励的分解，再将后续奖励中的价值函数作贝尔曼方程分解，得到贝尔曼期望方程的另一种形式

备份图

备份图描述了状态价值函数的计算分解

策略评估

前提：已经马尔可夫决策过程、策略

此时不断迭代，所有的价值函数最终都会收敛

预测与控制

预测：已知马尔可夫决策过程，策略，计算每个状态的价值

控制：已知马尔可夫决策过程，虚招最佳策略，以及最佳价值函数

动态规划

dp 解决同时有最优子结构和重叠子问题性质的问题。马尔可夫决策过程就具有这种性质，可以用动态规划去解。

马尔可夫决策过程中的策略评估

前提：已经马尔可夫决策过程、策略

将贝尔曼期望备份转换为迭代过程，直到收敛，这个过程是同步备份。

马尔可夫决策过程的控制

如何寻找最优策略，进而计算最佳价值函数

朴素方法：穷举

迭代算法：策略迭代、价值迭代

策略迭代

策略评估 + 策略改进

巨大的基础：马尔可夫过程已知。

1. 初始化策略，和价值函数
2. 根据当前策略，计算状态新价值函数
3. 根据状态价值函数，推算Q 函数
4. 最优化Q 函数，得到新策略
5. 判断迭代是否结束，未结束，则跳转到2

基础：马尔可夫过程已知

策略 + 价值函数 –贝尔曼方程迭代–> 新价值函数
价值函数 –> Q 函数
最大化Q 函数 –> 新的策略

Q 函数可以看成一个Q 表格

这个是大致的策略迭代算法

价值迭代

最优性原理: 一个策略在状态s达到最优价值的充要条件是，任何可以从s到达的状态s’都达到了最优价值。

算法：

更新Q ，更新V 若干次
从最后的V中提取最优策略

表格型方法

使用查找表

比如蒙特卡洛、Q学习、Sarsa

有模型

使用概率函数和奖励函数来描述环境

免模型

因为很多时候环境未知，概率函数甚至奖励函数都未知。

此时免模型需要通过试探来估计概率函数等环境信息。

有模型和免模型

有模型可以直接从环境推导智能体
免模型需要不断和环境交互，迭代智能体

Q 表格

Q 表格是主要的训练对象

强化是指用下一个状态的价值来更新当前状态的价值。

免模型预测

前提：无法获取马尔可夫决策过程模型

蒙特卡洛方法

蒙特克罗使用采样，使用经验品君回报估计价值函数

优点：不需要状态转移函数和奖励函数，也不用动态规划中的自举。

缺点：只能用于有终止的马尔可夫决策过程

算法：

蒙特克罗和动态规划比较

1. 蒙特克罗适用于环境未知，而且更新速度快
2. 动态规划适用于有模型，但每次迭代需要更新所有状态，速度很慢

时序差分方法(TD)

免模型控制

策略迭代进行广义推广，兼容蒙特卡洛和时序差分，也就是广义策略迭代。

Sarsa 同策略时序差分控制

Q 学习 异策略时序差分控制

同策略和异策略的区别

一个例子：用Q 学习解决悬崖寻路问题

策略梯度

策略梯度算法

策略梯度实现技巧

1. 添加基线

2. 分配合适的分数

蒙特卡洛策略梯度

一个例子：用策略梯度算法解决悬崖寻路问题

近端策略优化

一个例子：用近端策略优化算法解决悬崖寻路问题

深度Q 网络