强化学习(reinforcement learning,RL)是机器学习的一个领域,主要通过在环境(environment)中采取动作(action),来最大化某些指标,例如累计奖赏(cumulative reward)的一种学习方法。强化学习有监督学习(supervised learning)与无监督学习(unsupervised learning)三者共同构成了机器学习的三个重要方面

Reinforcement learning (RL) is an area of machine learning concerned with how software agents ought to take actions in an environment in order to maximize some notion of cumulative reward. Reinforcement learning is one of three basic machine learning paradigms, alongside supervised learning and unsupervised learning. (WikiPedia)

任务与奖赏

一个简单的强化学习模型如图所示

强化学习任务通常用马尔可夫决策过程(Markov Decision Process,MDP)来描述:机器处于环境E中,状态空间为X,其中每个状态x∈X是机器感知到的环境的描述,机器能采取的动作构成了动作空间A,若某个动作a∈A作用在当前状态x上,则潜在的转移函数P将使得环境从当前状态按某种概率转移到另一个状态,同时,环境会根据潜在的奖赏函数R反馈给机器一个奖赏。综合起来,强化学习任务对应了四元组E=<X,A,P,R>,其中P:X×A×X→R指定了状态转移概率,R:X×A×X→R(或者R:X×X→R)指定了奖赏。

如下图所示是一个在培育农作物的过程中,浇水与否(两个动作:浇水与不浇水)与农作物的状态(健康、缺水、溢水、凋亡)的马尔可夫决策过程:

在强化学习中,机器要做的即通过在环境中不断尝试而学得一个策略(policy)π,根据这个策略,在状态x下得到要执行的动作或者以多少概率执行动作空间中的任意动作。

在强化学习中,并没有监督学习中的有标记样本,动作是否正确以及接下来要做哪些动作,需要机器通过反思之前的动作与累积奖赏进行学习。因此,强化学习在某种意义上可看作具有延迟标记信息的监督学习问题。

探索与利用

强化学习的任务的最终奖赏是多部动作之后才能观察到的,所以对于每次的动作选择,可以分成两种情况:

  • 探索(exploration):若只想获得每个动作的期望奖赏是多少,则采用“仅探索”(exploration-only)策略,即将所有的尝试机会都均匀的分到每个可以执行的动作中去,从而根据最后每个动作多次尝试得到的奖赏来计算每个动作的期望奖赏。“探索”可以很好地估计每个动作的奖赏期望,但是却失去了很多选择最优动作的机会。
  • 利用(exploitation):若只想通过执行动作得到最大的奖赏,则采用“仅利用”(exploitation-only)策略,即根据到目前为止已知的经验中得到平均奖赏最大的动作(若有多个这样的动作就随机选取一个),将所有的机会都用在这个动作上从而得到奖赏。“利用”没有很好地估计各个动作所带来的奖赏,执着于重复已知的奖赏最大的动作,从而可能经常选不到最优的动作。

事实上,“探索”和“利用”两者是矛盾的,因为尝试次数有限,加强了一方则会自然削弱另一方,这就是强化学习所面临的探索-利用窘境(Exploration-Exploitation dilemma),所以必须在探索与利用之间达成较好的折中。

ϵ-贪心算法

ϵ-贪心算法基于一个概率来对探索和利用进行折中:每次尝试时以ϵ的概率进行探索,以1-ϵ的概率进行利用。

令Q(k)表示n次动作所得到的平均奖赏,每次得到的奖赏为v1, v2, v2, …, vn,则平均奖赏为:

使用增量式计算平均奖赏的方式即每次通过单次奖赏与前边所有次的平均奖赏来计算本次动作后的平均奖赏:

在增量计算下,每次动作仅需记录两个值:已尝试次数n-1和最近平均奖赏Qn-1即可。

ϵ-贪心算法描述如下:

  • 若每个动作奖赏的不确定性较大,如概率分布较宽时,则需更多的探索,此时需要较大的ϵ值
  • 若每个动作奖赏的不确定性较小,如概率分布较集中时,则少量的尝试就能很好地近似真实奖赏,此时需要的ϵ较小
  • 通常令ϵ取一个较小的常数,如0.1或0.01
  • 若尝试次数非常大,则在一段时间后,奖赏都能很好地近似出来,不再需要探索,这种情形下可让ϵ随着尝试次数的增加而逐渐减小,例如 ϵ=1∕√t

Softmax算法

Softmax算法基于当前已知的动作的平均奖赏来对探索和利用进行折中。若个动作的平均奖赏相当,则选取各摇臂的概率也相当;若某些动作的平均奖赏明显高于其他动作,则它们被选取的概率也明显更高。

Softmax算法中动作概率的分配是基于Boltzmann分布:

其中,Q(i)记录当前动作完成后的平均奖赏,τ>0称为“温度”,τ越小则平均奖赏高的动作被选取的概率越高,τ趋近于0时Softmax算法趋于仅利用,τ趋于无穷大时Softmax算法趋于仅探索,算法描述如下:

以上两种算法的好坏很难对比,也和其所取的参数有关,比如下图是一个在 2-摇臂赌博机上的性能比较:

全文参考:周志华 著 《机器学习》