OMSCS-DL课程笔记17-Deep Reinforcement Learning

这个系列是Gatech OMSCS 深度学习课程(CS 7643: Deep Learning)的同步课程笔记。课程内容涉及深度学习的基本理论方法以及它在计算机视觉、自然语言处理以及决策理论等领域中的应用，本节主要介绍深度强化学习。

Reinforcement Learning Introduction

到目前为止本课程主要介绍了深度学习在监督学习(supervised learning)中的应用，除了监督学习之外机器学习的范畴还包括无监督学习(unsupervised learning)以及强化学习(reinforcement learning)。

强化学习的目标是求解一个序列决策问题。我们希望智能体(agent)能够通过与环境(environment)的互动和反馈来学习到合适的策略(policy)，从而最大化奖励(reward)。

和监督学习相比，强化学习不存在一个明确的学习目标，智能体只能通过环境给出的反馈信号进行学习。同时反馈信号往往是滞后的，即在很多情况下只会在最后一步才能得到奖励。

强化学习的常见难点如下：

从更严格的角度来看，强化学习可以按照如下方式进行建模。在任意时刻$t$，智能体根据观测$o_t$执行了行为$a_t$，而环境则根据智能体给出的行为返回下一时刻的观测$o_{t+1}$以及奖励$r_{t+1}$。

目前强化学习在很多领域都取得了令人瞩目的研究成果。

Markov Decision Processes

MDPs in the Context of RL

要严格介绍强化学习则需要引入Markov决策过程(Markov decision process, MDP)。一个MDP包括状态空间$\mathcal{S}$、行为空间$\mathcal{A}$、奖励函数$\mathcal{R}(s, a, s’)$、转移概率$\mathbb{T}(s, a, s’)$以及折扣系数$\gamma$。同时MDP假定了转移概率$\mathbb{T}(s, a, s’)$满足一阶Markov性，即$t$时刻到$t+1$时刻的转移概率只与$t$时刻的状态和行为有关，与状态和行为的历史无关。

在强化学习中转移概率和奖励函数对于智能体是未知的，智能体只能通过和环境的互动来学习最优策略。当然在编程时程序员是需要知道转移概率和奖励函数的，毕竟这样才能编写出运行环境。

以二维格子世界为例，智能体从三角形位置出发到达对应的格子时会获得相应的奖励。这个MDP的状态空间包括所有格子的坐标，行为空间为上下左右四个可能的前进方向，而奖励函数则是在指定格子上得到的反馈。需要说明的是由于环境自身随机性的存在，智能体实际的行为不一定完全符合规划的预期。

Solving MDPs: Optimal Policy

求解MDP意味着寻找到当前环境下的最优策略(optimal policy)。智能体的策略可以是确定性的也可以是随机的，而一个好的策略不仅仅要考虑当前状态下的奖励，更要保证在将来的状态中有着比较高的奖励。

我们为每一时刻$t$获得的奖励乘上一个折扣系数$\gamma^t$，定义策略$\pi$的回报为按照该策略执行后未来所有可能状态奖励的期望。这样最优策略$\pi^*$就是最大化这个折扣后奖励期望的策略。

Discounting Future Rewards

之所以考虑折扣后的奖励一方面是为了保证奖励序列可以收敛，另一方面通过折扣系数来控制智能体更关注于近期的奖励。一般来说$\gamma$越趋向于1越关注长期的奖励，而$\gamma$越趋向于0则会更关注短期的奖励。

Value Function

描述未来折扣后奖励期望的函数称为价值函数(value function)。在强化学习中包括两种价值函数：首先是描述状态$s$自身好坏的函数，称为状态价值函数(state value function)记为$V(s)$；另一种是描述在状态$s$下采取行为$a$的好坏的价值函数，称为状态-行为价值函数(state-action value function)记为$Q(s, a)$。

状态价值函数定义为从$s$状态出发按照策略$\pi$选择动作后所有可能轨迹的折扣回报之和的期望。

状态-行为价值函数与之类似，只不过除了$s$状态还需要考虑该时刻的行为$t$作为条件再计算期望。

Algorithms for Solving MDPs

Optimal V & Q functions

我们把最优策略$\pi^*$对应的价值函数记为$V^*(s)$和$Q^*(s, a)$，显然最优策略在状态$s$下给出的行为等于给定$s$条件下$Q^*(s, a)$取最大值时的动作$a$，同时两个价值函数需要满足如下关系：

Bellman Optimality Equations

求解MDP的理论基础是Bellman最优方程(Bellman optimality equation)。我们把$Q^*(s, a)$进行展开，得到0时刻奖励和后续时刻最优价值函数需要满足的关系式如下：

再利用$Q$函数和$V$函数之间的关系，可以得到最优价值函数的递推公式：

Value Iteration

利用$V$函数的递推关系可以得到价值迭代(value iteration)算法。在每一步迭代中需要对所有可能的状态和行为进行求和，因此价值迭代在每一步的计算复杂度为$O(\vert \mathcal{S} \vert^2 \vert \mathcal{A} \vert)$。

Q-Iteration

如果使用$Q$函数来代替$V$函数则可以另一个价值迭代(Q-iteration)算法。

Policy Iteration

类似于价值迭代，我们还可以从策略函数出发进行迭代求解。此时每个迭代中需要先估计当前策略的价值函数，然后按照估计出的价值函数来更新策略。可以证明这样的策略迭代算法同样能够收敛到最优策略，而且迭代次数一般要远小于价值迭代。

Deep Q-Learning

在深度学习时代人们还开发出了deep Q-learning算法来处理更加复杂环境下的强化学习问题。它的思想在于使用一个神经网络来表示$Q$函数，然后通过最小化当前时刻$Q$函数的预测值和下一时刻$Q$函数的目标值之间的误差来更新价值函数。实际编程时为了提高求解的稳定性一般会考虑使用两个网络来表示$Q$函数。这样在最小化误差时需要先冻结$Q_\text{old}$的参数只更新$Q_\text{new}$，然后再把更新后的参数赋值给$Q_\text{old}$进行新一轮的迭代。

这样整个算法的流程为收集一系列的状态-动作-奖励样本，然后使用两个$Q$函数网络估计价值函数，最后通过最小化误差来更新$Q_\text{new}$并把更新后的参数赋给$Q_\text{old}$进入下一次迭代。

Exploration Problem

为了使用deep Q-learning算法我们还需要一套收集数据的机制，这实际上是一个相当复杂的问题。它的难点之一在于如何去平衡智能体对环境的探索(exploration)以及利用(exploitation)当前的策略；同时我们还需要考虑数据样本之间往往不满足独立同分布假设，事实上使用同一策略进行采样时得到的状态序列必然是相互关联的。