【强化学习】2.1 k臂赌博机(k-armed bandits)问题

Abstract: 在强化学习中,平衡Exploitation和Exploration将会是一个从始至终的问题,我们本章用简单的k臂赌博机问题来从具体的每一步来分析和研究这个问题,本节先介绍下问题的描述和大概的解决思路,为本章后面的问题解决做好铺垫
Keywords: 强化学习,k臂赌博机,多臂赌博机,利用,探索,Exploitation,Exploration

k臂赌博机(k-armed bandits)问题

赌博机,说到赌博,大家都觉得这是一个非常不好的活动,但是说回来,赌博是催生数理统计和概率的主要动力,具体可以看未完成的系列:数理统计学简史
作为不赌博的好孩子,大部分人对k臂赌博机可能不是很了解,首先我们来介绍一下这种赌博机:

这就是为什么是k臂赌博机,那个臂就是旁边的控制器,通过拉动控制器就能出发机器开关,当出现指定的图案就会有相应的奖励,这是1臂赌博机,如果有多个这种机器放在一排,那么这就是k臂赌博机。

k臂赌博机问题描述

下面我们来从学术的角度描述一下这个问题,描述如下:
我们面对的选择包含 $k$ 个选项,或者 $k$ 种可选的行为,每一个选择或者行为都对应了一个奖励信号(rewarding signal,忘记了回到前面看看) 每种选择对应的奖励信号是随机的,但是都来自固定的分布,当然来自不同选择的奖励信号服从的分布都不同,但是不会随时间改变,比如,$k$ 种可选的行为中 $f_1$ 表示第一种行为的奖励信号的随机分布,其可以不同于 $f_2$ 也就是第二种行为的奖励信号的随机分布,但是为了简化问题,我们目前研究的问题中 $f_1,f_2,\dots,f_k$ 都不随时间变化。
我们的目的是通过每一步观察,选择,执行不同行为来最大化我们的奖励信号,当然这个过程需要长时间,或者是多步以后来观察结果,一次或者两次的观察是没有研究意义的。

k臂赌博机

经过上面的描述,我们就可以把描述和赌博机联系在一起了,首先我们对赌博机进行如下假设:

  1. 赌博机出现的结果都是满足某种随机分布的,当然这个可能是赌场老板设定的,也可以是自然产生的
  2. 赌场里面有很多赌博机可以供我们选择,如果赌场就一个赌博机,我们就要换一家研究k-armed bandits problem了
  3. 赌博机的内的设置不会随时间改变,也就是1中的分布不随时间改变,没有幕后黑手操控比赛

有上面三点假设,我们就可以解释为什么我们本章研究的问题的是k臂赌博机了,我们面对 $k$ 个赌博机,我们的目的是最大化我们的收益,所以我们的做法是选择一个赌博机,然后下注(假定从始至终都不变)启动所有机器,获得结果,观察其他机器的行为,决定下一局是否换别的机器下注,对应上面的问题:

  • 奖励信号 对应 单次赌博收益
  • 可选行为 对应 本次使用哪台机器
  • 每个行为对应的奖励信号的随机分布 对应 每台赌博机出现不同结果的随机分布

所以这就是我们上面描述的问题的生活中的例子,或者说我们可以通过生活中这个例子来得到问题。

上面的例子是赌博机的例子,下面还有一个类似的类比,就是医生看病的例子,医生每天要面对一些列的病人,每个病人用什么样的治疗方案就是一个选择的过程,而每种选择都对应着不同效果,而治疗效果就是奖励信号,当医生面对络绎不绝的病人时,医生的目标就是把奖励信号最大化,也就是最大程度的让更多人康复,这个类比也符合上面我们的问题描述

  • 奖励信号 对应 病人康复程度
  • 可选行为 对应 可选的治疗方案
  • 每个行为对应的奖励信号的随机分布 对应 每种治疗方案对当前患者的效果的随机分布

数学描述

把上面的语言描述转换成数学描述就是如下了:
当前为第 $t$ 次选择(对应赌博中的第 $t$ 局,医生的第 $t$ 个患者), 有 $k$ 中选择,我们在此次选择的行为是: $A_t$ 对应获得的奖励信号是 $R_t$ ,那么对于这一轮选择,假设我们选择了 $a$ 我们获得奖励信号的期望 $q_*$ 就是:
$$
q_{\ast}(a)\doteq\mathbb{E}[R_t|A_t=a]
$$

如果你对 $A_t$ 和 $a$ 搞不清楚,我可以大概说一下,$A_t$ 是一个总称,本轮的所有选择的总称, 而 $a$ 是特定的一个行为,所以期望的公式就可以解释的清楚了,因为不同行为对应不同的分布,而我们希望使用期望来衡量这个行为的奖励信号。
如果我们明确知道每一步(局)每个行为(机器)将会出什么结果,那么我们就不需要选择了,直接选最大的那个就好了,所以我们这里假定我们不知道,也许你大概知道期望,但是对结果还是无法确定的(你可以一直观察某个赌博机的结果,利用大数定理通过采样结果来估计原始分布的结果)
这里我们对 $t$ 步的特定行为 $a$ 的评价(前面说的value function中value,和rewarding signal直接相关)的期望进行定义:
$$
Q_t(a)\approx q_*(a)
$$

这样就可以利用我们上面对问题的分析,以及使用前面提到的value function来解决这个问题了

强化学习解决k臂赌博机问题

上面我们应该已经能从整体上掌握k臂赌博机的问题过程了,那么我们接下来就要用我们前面提到的一些概念来解决这个问题了。
如果从我们自身出发,我们希望每一步都能最大化我们的收益(或者叫做奖励信号),我们自身会对所有赌博机都有一个评估,无论是感性的还是理性的,我们都会认为某个或者某几个赌博机获得高回报的可能性大一些,那么我们就有很多种玩法了:

  1. 贪婪的我 —— 每次都玩那个我认为回报高的赌博机
  2. 任性的我 —— 每次随便玩,就是不选我认为回报高的
  3. 会强化学习的我 —— 每贪婪若干次后任性一次(玩自认为回报高的机器几次后,随机玩一次别的机器,看看是否会改变自己前面的观点)

前面我们反复说过两个单词(第一次考托福的时候我还用这两个单词写过作文😜)”exploitation” or “exploration” ,上面1中的贪婪也被称为 “greedy actions” 当你选择这种action的时候,你的action对应的就是”exploitation”;相反,如果我们就是不选我们认为回报高的,也就是2的这种行为,我们称为 “exploration”,如果我们还是想赢点钱,这种行为也不是完全傻瓜的,因为我们可以通过这种行为来纠正我们对每台机器回报高低的期望(有可能你对机器回报高低的判断是错误的,实际上也是这样的),换句话说,每台机器回报高低我们根本就是乱猜,所以1中的贪婪也有可能执迷不悟,而通过偶尔的”2”一下,没准会得到更多的收获,也就是3中给出的做法,会有更多收获。
Exploitation的做法肯定是正确的,但是从长期来看Exploration可能会产生更高的收益(短期来看exploration的收益大概率不如exploitation),因为exploration很有可能找到比当前执行的action收益更高的其他action。但是具体怎么安排或者说怎么平衡Exploitation和exploration就是我们今后要一直研究的问题了。我们经常会用 “conflict” 来形容Exploitation和Exploration之间的选择。
是Exploitation还是Exploration这个问题理论上是没有通用解的,每一个环境,每一个问题,每一步都是不一样的,也无法确定,对于k臂赌博机问题,目前有一些专用的数学公式可以比较好的平衡Exploitation和Exploration之间的关系,但是这些公式或多或少都对问题的某些方面进行了限制和假设,这就使得这些方法在相似问题的不同环境下可能会失效。在后面章节我们研究的全面的强化学习(Fall Reinforcement Learning Problem, k臂赌博机 问题是简化后的问题)的时候,对应的环境会变得不同,一些假设条件也会不成了,这时候这些方法也会失效。这时候(某些假设不成立的时候)算法对应的收敛性和收敛边界都会失效。
我们目前的研究不关心是否以一种高效,漂亮的(sophisticated)方法来平衡Exploitation和Exploration,而是只要能平衡就行,不管漂不漂亮,高不高效,本章我们就列举几个简单的方法来平衡他们来获得比只 exploitation更好的结果。

总结

在强化学习中,平衡Exploitation和Exploration将会是一个从始至终的问题,我们本章用简单的k臂赌博机问题来从具体的每一步来分析和研究这个问题,从而获得更直观,更详细的理解。

References

  1. Sutton R S, Barto A G. Reinforcement learning: An introduction[J]. 2011.

原文地址: https://face2ai.com/RL-RSAB-2-1-A-k-armed-Bandit-Problem

0%