强化学习笔记

本文主要记录Reinforcement Learning中可能经常被遗忘的知识点。主要内容参考easy-rl仓库

Chapter 1. 强化学习基础

强化学习和监督学习的区别

监督学习的输入数据是没有关联的，且需要提供正确的标签，以修正自己的预测。 强化学习不满足这两个假设。例如雅达利打砖块游戏，模型得到的连续两帧的输入有非常强的连续性，且游戏并没有告诉模型哪个动作是正确的。即使模型预测出了下一步应该把木板往哪个方向移动，这个决策导致的游戏结果也不会立即反馈给模型。 强化学习任务的最终奖励在多步动作之后才能观察到。

强化学习的目标就是让模型（智能体）在这种环境中学习：智能体的动作会影响它随后得到的数据。目标：让智能体的动作稳定地提升。

预演（rollout）：从当前帧对动作采样，生成很多局游戏。每个游戏（可称为回合episode或者试验trial，可以看成一个轨迹（trajectory）: \(\tau = (s_0, a_0, s_1, a_1, \cdots)\) 其中，$s_i$为第$i$帧，$a_i$为第$i$帧时智能体采取的动作。 为了训练模型，我们可以用观测序列和最终奖励。 奖励：标量的反馈信号，模型的目的是最大化期望累计奖励(expected cumulative reward)，奖励包含游戏分数、股票收益等。

标准强化学习：手工特征提取+分类 深度强化学习：端到端特征提取+分类

状态和观测：状态是完整的描述（用角度和速度表示一个机器人的状态；用RGB表示一个视觉的观测）。 历史是观测、动作、奖励的序列。

动作空间(action space)：智能体的决策集合。

策略(policy)：将输入的状态映射到动作的函数。

随机性策略(stochastic policy)：$\pi$函数，输入为状态$s$，输出为概率$a$： \(\pi (a|s) = p(a_t = a|s_t = s)\) 每一种动作都对应一个概率值。随机性策略按照概率对动作采样，得到智能体将采取的动作。

确定性策略(deterministic policy)：智能体直接采取最有可能的动作: \(a^* = \text{argmax}_a \pi (a|s)\)

价值函数：评估状态的好坏，对未来奖励的预测。 Q价值函数（Q函数）：包含状态和动作，反映我们在使用策略$\pi$时，得到多少奖励: $ Q_{\pi}(s, a) $

模型：依据当前的状态和动作决定下一步的状态。

基于策略的强化学习(policy-based RL)：学习环境，在每个状态，都有一个最佳策略。策略梯度属于此类方法。 基于价值的强化学习(value-based RL)：每个状态会返回一个价值（比如迷宫问题中，每个格子状态的价值就是离终点的最短步数）。根据未来状态的价值，选择动作。Q-learning、Sarsa属于此类方法。

演员-评论员智能体(actor-critic agent): 同时学习策略和价值函数，并通过交互得到最佳动作。

model-based: 学习状态转移来采取动作； model-free：学习价值函数和策略函数来决策（没有估计状态的转移、也没有得到环境的具体转移变量），免模型方法不需要对环境进行建模，直接与真实环境进行交互即可

强化学习任务的定义：马尔科夫过程($S, A, P, R$)：状态集合、动作集合、状态转移函数、奖励函数

如果智能体能根据当前的状态和采取的动作得知下一个时间的状态和奖励($P(s_{t+1} | s_t, a_t), R(s_t, a_t)$)，则称为有模型强化学习。 难点：状态转移函数、奖励函数很难估计；环境状态很可能未知。 model-based比model-free多出一个步骤：对真实环境建模。

目前的RL研究的默认假设：环境是静态的、可描述的，智能体的状态是离散的、可观察的。不需要评估状态转移函数和奖励函数，可直接采用免模型强化学习。

探索：探索环境、尝试不同动作来得到最佳策略； 利用：不去尝试新动作、采取已知的带来很大奖励的动作。

多臂赌博机：赌徒在投入一个硬币后可以按下其中一个摇臂，每个摇臂有一定概率吐出硬币，但赌徒不知道这个概率。 目标：通过一定策略最大化奖励。 仅探索法：尝试每个摇臂，以平均吐币概率作为奖励期望的估计。 仅利用法：按下目前最优的摇臂（平均奖励最大的）。 尝试次数有限，导致了探索-利用窘境(exploration-exploitation dilemma)

用python的gym框架可以实现一个简单的强化学习框架：

import gym 
env = gym.make("Taxi-v3")   # 取出环境
observation = env.reset()   # 初始化环境
agent = load_agent()
for step in range(100):
    action = agent(observation) 
    observation, reward, done, info = env.step(action)              # 执行环境

环境提交一个智能体动作后，返回四个信息：

• observation: 状态，屏幕像素值等等；
• reward: 奖励值，动作提交之后能够获得的奖励值；
• done: 游戏是否已经完成；
• info: 用于诊断和调试的信息

在gym中，可以获取观测空间、动作空间等信息：

import gym
env = gym.make('MountainCar-v0')    # 取出环境
print('观测空间 = {}'.format(env.observation_space))
print('动作空间 = {}'.format(env.action_space))
print('观测范围 = {} ~ {}'.format(env.observation_space.low,
        env.observation_space.high))
print('动作数 = {}'.format(env.action_space.n))

输出：

观测空间 = Box(2,)
动作空间 = Discrete(3)
观测范围 = [-1.2  -0.07] ~ [0.6  0.07]
动作数 = 3    

强化学习的目标（损失函数）是使总奖励的期望尽可能大。

Chapter 2. 马尔科夫决策过程(MDP)

智能体与环境的交互过程：

1. 智能体得到环境状态$s_t$，并计算得到奖励$r_t$
2. 智能体采取某个动作$a_t$
3. 环境得到该动作，并进入下一个环境状态$s_{t+1}$

回顾马尔科夫性质：随机过程的未来条件概率分布仅依赖于当前状态，也即：未来的状态和过去状态是独立的。

马尔科夫奖励过程(Markov reward process)：马尔科夫链+奖励函数，当我们到达一个状态时，可以获得多大的奖励。

折扣回报函数： \(G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots\)

$\gamma$是折扣因子，从当前状态$s_t$开始的某一条状态轨迹是$s_{t+1}, s_{t+2}, \cdots$，对应的奖励为$r_{t+1}, r_{t+2}, \cdots$。越往后的奖励折扣越多，我们希望模型能够更关注现有的奖励。

我们现在知道从当前状态出发，沿着某一条轨迹的回报函数。但如何评估当前状态的价值函数？我们在上一个状态时，如何评价当前状态的价值呢？引入贝尔曼方程计算状态$s$的价值$V(s)$： \(V(s) = R(s) + \gamma \sum_{s' \in S}p(s'\lvert s) V(s')\) 易知，这是一个迭代的公式，右边包含了未来某个状态的价值$V(s’)$。当前状态的价值为所有未来价值的组合、以及即时奖励$R(s)=E[r_{t+1} \lvert s_t = s]$。

贝尔曼公式由全期望公式推导而来，本质上就是当前状态下的折扣汇报函数。

$N$个状态下的贝尔曼方程与价值函数解析解(analytic solution): \(\mathbf{V} = \mathbf{R} + \gamma \mathbf{PV}\) \(\mathbf{V} = (\mathbf{I} - \gamma \mathbf{P})^{-1}\mathbf{R}\) 复杂度为$O(N^3)$，因此解析解仅适用于少量的马尔科夫奖励过程。

蒙特卡罗算法：采样N条轨迹，将其折扣汇报函数取平均值作为当前状态的价值。

马尔科夫决策过程：把当前状态代入策略函数得到概率分布： \(\pi(a \lvert s) = p(a_t = a \lvert s_t = s)\) 奖励函数： \(r_{\pi}(s) = \sum_{a \in A} \pi(a\lvert s) R(s, a)\) 注意：当状态和智能体的动作确定后，未来的状态也是一个概率分布。

Q函数（动作价值函数）：决定策略$\pi$后，在某一个状态采取某一个动作，它可能得到的回报的期望。可以写作贝尔曼期望方程： \(Q_{\pi}(s, a) = \mathbb{E}_{\pi}[G_t\lvert s_t = s, a_t = a]\)

在该策略$\pi$下的状态价值函数，即每一种不同策略的价值和选择该策略的概率之组合：

从此可以得到动作价值函数： \(Q_{\pi}(s, a) = R(s, a) + \gamma \sum_{s' \in S} p(s' \lvert s, a) V_{\pi} (s')\)

我们可以把状态价值函数$V_{\pi}(s)$和动作价值函数$Q_{\pi}(s)$分解为即时奖励$R(s,a)$+后续状态的折扣价值两部分。

\(V_{\pi}(s) = \sum_{a\in A} \pi(a \lvert s) \left(R(s, a) + \gamma \sum_{s' \in S} p(s' \lvert s, a) V_{\pi}(s')\right)\) 将$V_{\pi}(s’)$关于$Q_{\pi}(s, a)$的表达式代入$Q_{\pi}(s, a)$中，即可得 \(Q_{\pi}(s, a) = R(s,a) + \gamma \sum_{s' \in S} p(s' \lvert s, a) \sum_{a' \in A} \pi(a' \lvert s') Q_{\pi} (s', a')\)

从这两个公式可以看出，当前的函数是未来函数的线性组合。因此我们可以画出由$V_{\pi}(s)$和$Q_{\pi}(s, a)$相互穿插的备份图。

策略评估

马尔科夫决策过程和马尔科夫过程/奖励过程的区别：前者在每一个状态时，智能体都会采取动作改变状态的未来发展；后者的状态变化是“随波逐流”的。前者与后者相比，智能体具有策略$\pi$和动作$a = \pi(s)$。

预测与控制

预测：输入马尔科夫决策过程、策略$\pi$，输出价值函数$V_{\pi}$，计算每个状态的价值函数。

控制：输入马尔科夫决策过程，输出最佳价值函数$V^$和最佳策略$\pi^$

强化学习中，先解决预测问题，再解决控制问题。

这一节有个经典的网格问题。

问题重述：一个$5\times 5$的网格中，每个网格的动作预先被设定，即上下左右移动一格的概率均为$\frac{1}{4}$。在特殊的方格$A$和$B$中，任意动作均会移动到对应的$A’$和$B’$，并获得奖励值；除此之外的奖励为-1。

用迭代法求解$V_{\pi}(s)$时，初始值均设置为0，新一轮次的价值函数为未来状态的价值+即时奖励。

从控制的角度思考网格问题，则我们还需要求出每个状态下的最佳策略概率分布。

马尔科夫决策过程控制

最佳价值函数：找到一个策略$\pi$，使得每个状态$s$的价值$V(s)$最大： \(V^*(s) = \mathop{\text{max}}\limits_{\pi} V_{\pi}(s)\)

策略迭代

策略和状态函数的迭代：策略评估和策略改进。

1. 策略评估：用当前的策略$\pi$评估状态价值$V_{\pi}(s)$。
2. 策略改进：从状态价值函数得到动作价值函数（Q函数），采用贪心的策略选取一个新的动作（即Q值最高对应的动作）$\pi_{\text{new}}$，作为新策略，重复这两个流程以进入下一轮迭代。

当改进停止后，Q函数的最大值对应的就是价值函数$V_{\pi}(s)$。此即贝尔曼最优方程： \(V_{\pi}(s) = \mathop{\text{max}}\limits_{a \in A}Q_{\pi}(s, a)\) 最佳策略下的一个状态的价值必须等于在这个状态下采取最好动作得到的回报的期望。

通过贝尔曼最优方程，我们可以得到最优动作价值$Q^(s, a)$和最优状态价值$V^(s)$的转移函数： \(Q^*(s, a) = R(s, a) + \gamma \sum_{s'\in S}p(s' \lvert s, a) \mathop{\text{max}}\limits_{a'}Q^*(s', a')\)

价值迭代

最优性原理：当某个策略下某个状态最优，当且仅当此状态可达的其他状态在该策略下也最优。（提示：未来状态的组合）

价值迭代的迭代过程像是一个从某一个状态（这里是我们的终点）反向传播到其他各个状态的过程，因为每次迭代只能影响到与之直接相关的状态。

策略迭代和价值迭代，这两个算法都可以解马尔可夫决策过程的控制问题。策略迭代分两步。首先进行策略评估，即对当前已经搜索到的策略函数进行估值。得到估值后，我们进行策略改进，即把 Q 函数算出来，进行进一步改进。不断重复这两步，直到策略收敛。价值迭代直接使用贝尔曼最优方程进行迭代，从而寻找最佳的价值函数。找到最佳价值函数后，我们再提取最佳策略。

Chapter 3. 表格型方法

表格型方法主要包括蒙特卡罗、Q学习和Sarsa。

状态$S$、动作$A$、状态转移概率$P$和奖励$R$

免模型的经典算法：环境是未知的。我们处在未知的环境里，也就是这一系列的决策的概率函数和奖励函数是未知的，这就是有模型与免模型的最大的区别。

免模型强化学习方法没有获取环境的状态转移和奖励函数，而是让智能体与环境进行交互，采集大量的轨迹数据，智能体从轨迹中获取信息来改进策略，从而获得更多的奖励。