OMSCS-RL课程笔记07-Exploring Exploration

这个系列是Gatech OMSCS 强化学习课程(CS 7642: Reinforcement Learning)的同步课程笔记。课程内容涉及强化学习算法的理论和相关应用，本节主要介绍强化学习中的探索问题。

探索(explore)是强化学习中非常重要的概念，甚至可以说”探索”是强化学习与通常意义下机器学习的主要区别。在本节课中我们会从赌博机模型、确定性MDP以及随机MDP三个方面来讨论探索在强化学习中的意义。

Bandits

K-armed Bandits

K臂赌博机模型(K-armed bandits)是经典的强化学习问题。在K臂赌博机模型中一共有K个不同的赌博机，每一轮游戏中智能体需要选择其中的一个，然后选择的机器会根据自身设置的概率给予智能体0或1作为奖励。智能体的目标是最大化累计奖励，也即选择回报概率最大的机器。由于智能体对每个机器的奖励概率一无所知，因此它需要首先对每个机器进行探索从而对概率进行建模。

Confidence-Based Exploration

当智能体对每个赌博机进行一定的探索后就可以利用这些经验来选择最优的机器。最直观的方法是利用这些数据来计算每个机器给出奖励的概率，其中概率最大的机器即为智能体的最优选择。显然当观测到的样本数不足时对概率的估计会具有很大的误差，此时智能体的选择往往是错误的。从这个角度上讲智能体在每一次进行决策时需要考虑是否利用当前观测到的数据执行最优策略还是继续对环境进行探索，这样的问题称为exploration-exploitation困境(exploration-exploitation dilemma)。

Metrics for Bandits

我们需要建立某种指标来平衡智能体的exploration和exploitation行为。这样当智能体基于该指标进行决策时可以找到最优的机器并获得最大累计奖励。有时可能没有办法在有限的探索中计算出最优的机器，但我们希望基于该指标仍然可以在多项式时间内以一个比较大的概率寻找到近似最优的机器。

Hoeffding Bound

实际上对于K臂赌博机问题我们可以利用Hoeffding界(Hoeffding bound)作为概率估计的置信区间。

更进一步还可以利用Hoeffding bound来选择最优的机器。

除此之外，也可以利用Hoeffding bound来计算获得可靠估计所需的样本数。

Exploring Deterministic MDPs

在K臂赌博机模型的基础上我们来考虑MDP。当MDP是确定性环境时我们可以在每个状态下尝试所有可能的行为并记录下奖励从而获得整个MDP的模型，然后使用求解MDP的相关算法来计算最优策略。但在很多情况下这样的计算代价是过于巨大的，因此更好的选择是在与环境进行交互时使用一些随机探索的策略来估计环境的模型。