赞
踩
首先,我们指出在bandit算法中主要有两类流行的算法,一类是贪心算法(如uniform exploration, -greedy算法),还有一类是基于upper confidence bound的UCB算法。他们二者的具体差别在哪里呢?简单来说,就是他们二者对exploration和exploitation的分配思路不太一样。对这方面不太熟悉的同学,可见:
覃含章:在线学习(MAB)与强化学习(RL)[2]:IID Bandit的一些算法zhuanlan.zhihu.com
话又说回来,在经典bandit算法当中,我们要做的无非就是通过一类pull arm的策略,尽快找到比较好的“arm”(reward较高的arm),然后尽可能多的去拉这些比较好的arm就是了。贪心算法无非就是永远以当前对每个arm的reward的估计直接作为依据,而UCB算法则是考虑了置信度的问题,因此考虑的是每个arm reward的置信区间的上界。
那么这个思想推广到更一般的马尔科夫决策过程问题中,可不可以呢?答案自然也是可以的。具体来说,我们考虑一般的episodic Markov decision process, 。其中 是所有状态(state)的集合,且状态数量有限, 则是所有行动(action)的集合,行动数量也有限, , 则是每个episode中MDP状态转移的次数(因此这个MDP可以认为是finite horizon的)。 就是我们熟知的状态转移矩阵(注意因为这里我们的状态和行动空间都是有限的,所以这个矩阵的维度也是有限的),即我们可以定义 来表示在 步中选择action 和处在state 情况下转移到其它state的分布。类似的,我们定义 为一个确定性的reward函数(与 有关)。
注意,我们这边考虑的是一个episodic MDP,也就是说这个MDP允许被重复很多个episodes。这也很好理解,比如我们如果要训练AlphaGo,那么每个episode就可以看作一局棋,我们势必要重复下很多盘棋才可能对一个比较好的下棋“策略”(policy)有所了解,而如果只下一盘或者很少盘数的棋,我们可能都没有办法对于怎么下棋这件事情,和不同的下棋策略赢的几率,有一个好的exploration。
那么我们就发现有两个核心的概念:
策略:policy的概念。在MDP中,我们定义一个policy 是 个函数的集合: 。也就是说,在每一步 ,在不同的state下我们应该选择哪个action。
价值函数:value function的概念。这里我们需要定义著名的 function和 function。我们称 这个函数是在step 和state 上,根据policy 所能获得的期望剩余reward。也就是说, 。至于 function,它和 function主要的区别在于多一个自变量 ,即,我们称 这个函数是在step 和state 上选择了action 之后,根据policy 所能获得的期望剩余reward。如果你对动态规划(dynamic programming)不熟悉,你可能会问,为什么要定义两个看起来很像的函数。一方面来说,这样子我们很方便就可以写出DP里著名的Bellman equation(或者说optimal induction,直接可以得到最优的policy的表达式);另一方面来说, 我们也可以说 function就可以刻画DP本身的逻辑。而 function则可以刻画我们实际算法做 learning的作用对象。
本节最后说明,在我们的epsiode MDP setting,每个episode一开始,我们可以不失一般性地认为 是被某个adversary任意挑选(arbitrarily picked)的。
我们注意到,因为只是考虑有限的状态空间和行动空间,所以最优policy是一定存在的(这是DP的经典结果)。那么用 function我们就可以刻画最优的policy :即让 对所有 的函数。因此,根据DP的最优迭代公式(Bellman equation),我们知道如下迭代成立:
注意这里我们用了简化的notation: 如果你不熟悉DP,我们稍微来看一下这个迭代意味着什么。简单来说,核心是迭代的第二步,即最优的 函数的值应该是当前的reward ,加上最优的 函数从 步开始的值(这个在DP里面也叫做cost-to-go)。这其实也是DP所谓的tail-optimality。结合迭代的第一步说了最优的 函数值应该是 最优的 函数取得最好的action的值,即从后往前推,你在step 的时候,最优的policy就是要最大化 函数的值,也就是要最大化当前的reward加上从 步开始最优policy所带来的期望reward。这点,希望不熟悉DP的同学们好好体会。
说明这一点更简单的例子见上图,即所谓的最短路(shortest path)问题。这个问题显然也可以看成是episodic MDP,在每个episode我们都想找到这个固定的图上的最短路,假设每两个节点之间我们事先不知道要花多少时间,而它符合某些随机变量的分布。那么,这个问题的最优policy显然就是满足tail optimality的,这是因为,如果我找到了一套走最短路的方法,那么很显然,即使我走到了途中某个节点,比如B,那么我从B走到F的最短路一定可以通过B->C + C->F的最短路(最优policy给出) 或者 B->D + D->F的最短路(最优policy给出)来比较得到。
那么说到这里,Q-learning的想法也就呼之欲出了。因为我们知道,如果我们能知道 的具体分布,我们马上就能求得 ,也就能求出最优的policy。当然,实际情况中我们规定我们事先并不知道 的分布,我们能做的,只有在每个episode中的每步step,根据当前的state选择适当的action,并且根据我们选择的action随机(根据 )跳到下个state,并且观察到对应的reward的一个sample。那么,一个很自然的想法,当我们收集了越来越多这些sample之后,我们就可以比较好的去估计这个 函数,估计好了这个 函数之后,我们的policy其实就是去最大化这个估计的 函数。嗯,思路其实就这么简单。
所以核心问题就是如何去估计这个 函数。如果沿用 -greedy,自然意思就是直接用sample mean(对每个 来说)。而如果要用UCB的话,我们就需要对 函数求置信区间。这个自然就比bandit里面求置信区间要复杂了,因为 现在可不是什么IID的随机变量了,而是跟MDP有关的一个更加复杂的随机变量。好在Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, Michael Jordan这几个人最近确定了准确的形式把UCB的思想套用了过来(见开头的参考文献)。
他们的算法有两个形式,但其实大同小异,区别在于通过不同的集中不等式所需要的不同形式的upper confidence bound。简单来说,Bernstein不等式相比Hoeffding不等式还有对二阶矩的精细控制(即Algorithm 2中的 项),所以他们的Algorithm 2比起Algorithm 1能得到更好的regret bound。
不过我们这里因为只是谈一下大概的思想,所以后面只会具体提及Algorithm 1相关的分析思路。毕竟大的思想其实是一样的。这边我们看Algorithm 1,思路就如前面所说,是很直接的,算法中第7行就是如何对Q函数进行估计,一共有两项组成,第一项可以看成是优化算法中的momentum项,第二项就是核心的UCB bound迭代。这里我们注意到置信区间的长度,忽略log项,大概是 的, 是 目前有的sample数量。那么当然,这边 步长的选取也是非常关键的。几位大佬机智地发现把步长取成 ,而非传统一阶算法里常用的 就能得到满意的结果,意思就是单纯的uniform weight是不行的,而要给比较近的项更高的权重才可以。
好了,本节我们就稍微具体看下Algorithm 1为什么可以work。尤其比如说步长为什么要选成 。当然这边也不可能照搬所有细节,所以想学完整proof的同学还是建议直接去翻原paper。
这边先重申下regret的定义(其实是expected regret,或者按照上次的说法是pseudo regret),很简单,就是
其中 是episode的总数, 就是我们算法在episode 所用的policy, 就是每个episode 最开始初始的state。
这边需要用一个额外的notation来说。我们让 表示在episode 的step 我们实际观察到的state和选择的action。然后如果我们让 表示episode 刚开始的 函数估计。我们就注意到Algorithm 1的第七行其实可以写成:
这个式子其实更能反应算法的本质:这也是Q-learning利用多个episode学习的关系式。对于分析来说,我们就希望能说明利用合适的步长 ,我们这边估计出来的 相比 它的error不会累积地过于快。
对于步长,我们再定义这样一些量:
,
那么我们可以进一步把上面的式子展开,得到
.
这边我们令 到第k个episode为止,在每个episode的第h个step,观测到 的次数, 则是之前在step 选择action 和处在state 的episodes。那么我们就发现,其实是这个量 (当然它由 决定)来反应我们的Q-learning算法(Algorithm 1)对之前的UCB bound的权重分配。
那么这边就有张图,画出了取不同 我们的 随次数增长的曲线。我们注意到相比我们最终选取的 , 的步长完全是uniform分配的,不偏不倚,而 的步长则基本把所有权重都分配给了最近的15%左右的sample(对于分析来说,这个步长会导致很大的variance,导致过高的regret)。这么来看,我们选取的步长倒是显得比较中规中矩了~
具体来说,我们容易验证当 ,我们有 对所有正整数 成立。而这也是每个episode我们能累计regret的阶,也就是说总共在这种步长下我们的regret累计最多也就是 的阶,而这算是个常数了。
那么之后的analysis都基于前面的式子,简单来说我们需要能够用 来bound住 ,然后利用DP的迭代我们就能推出 ,也就是regret的bound。具体的步骤其实也不算长,当然也不是说就可以一蹴而就,有兴趣的同学们可以自己先尝试推推看,然后再去看大佬在paper里的推法。
忽略log项,Algorithm 1可以得到 的regret bound( 是总共的步数),而Algorithm 2因为用了更精细的集中不等式,可以改进到 的regret bound。
之后再提一下他们得到的其它一些结果。主要还有两个:
1.他们构造了一个MDP的例子并说明 greedy算法在这个例子上的regret至少是exponential的(exponential in )。这确实就说明在更一般的情形下 greedy和UCB算法在理论上的表现被进一步拉开了。。
2.他们也给了一个一般情形的lower bound,对任意算法,存在一个 epsiode的MDP,使得算法的regret至少是 的。所以我们看到他们的Algorithm 2只和这个lower bound差了 ,已经非常接近了。接下来就看谁能把这个gap close了,呵呵。
最后多说一句,其实bandit文献里面经常需要自己去”造“一些特殊的不等式然后算法配合之达到比较好的regret bound,这往往都是因为只控制一阶矩不够精细,需要引入二阶矩的一些精确估计才ok。当然可能有些人会觉得这些纯属是在玩bound,不过在bandit领域里应该都算是共识了。。。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。