OMSCS-ML课程笔记14-Reinforcement Learning

这个系列是Gatech OMSCS 机器学习课程(CS 7641: Machine Learning)的同步课程笔记。课程内容涉及监督学习、无监督学习和强化学习三个部分，本节介绍强化学习的相关内容。

MDP vs. RL

在上一节中我们介绍了如何通过求解Bellman方程来解决MDP或者说是强化学习的问题。而实际上MDP与强化学习还是有一定的区别的，它们的主要区别在于智能体是否知道外界环境的状态转移$T$：在MDP中智能体可以利用外界环境的状态转移$T$来计算最优策略；而在强化学习中智能体对环境是一无所知的，只能通过观测得到的状态转移序列$⟨s,a,r,s^{\prime }⟩$来学习到最优策略。

API

我们需要对一些常见的概念进行区分：

• 如果我们已知外界环境的状态转移$T$以及回报函数$R$，我们可以通过一些算法来计算出最优策略，这样的过程称为规划(planning)；

• 如果我们只能通过观测得到的状态转移序列$⟨s,a,r,s^{\prime }⟩$，我们希望通过这些观测来学习到最优策略，这样的过程称为强化学习(reinforcement learning)；

• 我们可以利用观测得到的状态转移序列$⟨s,a,r,s^{\prime }⟩$来估计真实的外界环境，这样的过程称为建模(modeling)；

• 此外我们还可以利用已有的模型来获取状态转移序列，这样的过程称为仿真(simulation)。

Three Approaches to RL

根据计算目标的不同我们可以把强化学习分成大致三种类型：

• 直接取计算策略$\pi$的算法称为策略搜索(policy search)；
• 通过计算效用$U$来获得策略的算法称为基于价值函数(value-function based)的强化学习；
• 此外我们还可以对外界环境进行建模并在此基础上获得最优策略，这类算法称为基于模型(model based)的强化学习。

实际上这三种类型的算法是相互关联的：在大多数情况下直接进行策略搜索会比较困难，但我们可以先计算价值函数然后通过价值函数来获得最优策略；如果获得了外界环境的模型，我们通过求解Bellman方程来计算价值函数并获得最优策略。

以上这三种强化学习算法在实际中都有各自的应用，不过在本课程中我们主要关注基于价值函数的强化学习算法。

Q-Learning

Q-function

在上节课中我们介绍过最优策略需要满足Bellman方程：

$$U(s)=R(s)+\gamma \cdot \underset{a\in A(s)}{max}\sum _{s^{\prime }}T(s,a,s^{\prime })U(s^{\prime })$$ $$\mathrm{\Pi }(s)=\arg \underset{a\in A(s)}{max}\sum _{s^{\prime }}T(s,a,s^{\prime })U(s^{\prime })$$

这里我们把行为$a$加入到价值函数中从而得到一个新的价值函数，一般称为Q函数(Q-function)：

$$Q(s,a)=R(s)+\gamma \cdot \sum _{s^{\prime }}T(s,a,s^{\prime })\underset{a^{\prime }}{max}Q(s^{\prime },a^{\prime })$$

实际上Q函数表示在状态$s$下执行$a$所对应的最优价值，这样我们就可以比较不同行为之间的好坏。

不难发现我们可以利用Q函数来重新定义最优价值以及策略：

$$U(s)=\underset{a}{max}Q(s,a)$$ $$\mathrm{\Pi }(s)=\arg \underset{a}{max}Q(s,a)$$

也就是说如果我们计算得到了Q函数也就等于计算出了最优策略，而计算Q函数的过程则称为Q-learning。

Estimating Q-function

由于我们不知道外界环境的状态转移$T$，我们不能显式地去计算Q函数。假设我们观测到了状态转移序列$⟨s,a,r,s^{\prime }⟩$，我们可以使用下式来更新Q函数：

$$\hat{Q}(s,a)=\hat{Q}(s,a)+{\alpha }_t\cdot (r+\gamma \cdot \underset{a^{\prime }}{max}\hat{Q}(s^{\prime },a^{\prime })-\hat{Q}(s,a))$$

其中${\alpha }_t$称为学习率，一般可以取${\alpha }_t=\frac{1}{t}$。可以证明当状态$s$和行为$a$能够无限次地重新访问时，按照上式更新的Q函数会收敛到Bellman方程的解，即$\hat{Q}(s,a)\to Q(s,a)$。

Choosing Actions

在实际应用Q-learning时有很多需要考虑的内容，包括：

• 如何初始化Q函数？
• 如何设置衰减的学习率${\alpha }_t$？
• 如何选择行为$a$？

其中最重要的一点在于选择行为$a$。如果我们在迭代时总是选择当前的最优策略，则违背了Q函数的收敛条件；而如果我们总是选择一个随机行为则可以保证Q函数的收敛，但却没有利用到Q函数的信息。显然我们需要在迭代中不断尝试各种各样的行为，同时尽可能利用学习到的信息。因此一种合适的策略是在每一步中以概率$\epsilon$对$a$进行随机采样，否则选择当前的最优行为：

$$\hat{\mathrm{\Pi }}(s)=\{\begin{array}{rlrl}& \arg \underset{a\in A(s)}{max}\hat{Q}(s,a),& & \text{with probability}1-\epsilon \\ & \text{random action},& & \text{otherwise}\end{array}$$

这样的策略称为$\epsilon \epsilon$-greedy exploration。当我们对$\epsilon$进行衰减时，我们不仅能够保证Q函数的收敛，同时学习到的策略$\hat{\mathrm{\Pi }}$也会收敛到最优策略。

从一个更高的层面上讲，我们希望策略$\hat{\mathrm{\Pi }}$能够在学习过程中探索不同的可能性，同时利用到已经学习到的内容，这种情况称为Explore-Exploit dilemma。Explore-Exploit dilemma是强化学习的基本问题，我们需要智能体在和环境的互动中尽可能多地探索不同的可能性，同时还要利用已有的信息做出最优的决策，这就需要对explore和exploit这两个过程进行权衡。

Reference

• Wikipedia: Q-learning