欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

强化学习(2)-Bandit问题

熟悉EE的对这个问题应该不陌生,可以看文章:推荐系统的EE问题及Bandit算法得到更多信息。

文中evaluative feedback和instructive feedback愣是没看懂啥意思

WIKI有很清楚的说明:Multi-armed_bandit

对Bandit问题,核心就是exploit和explore之间的平衡,如果没有explore,每次保持「贪心策略」即可得到最大回报。在现实的场景中,需要做explore的原因为:

  1. 会有新的老虎机加入游戏
  2. value的预估需要积累一定的样本才可以预估准确
  3. 随着时间的推移,reward本身的分布本身会变化,这个时候需要对value预估也动态变化

动态确定explore的强度是算法的核心问题,在实际中,下图可能成立:

QQ20170408-222941

\(\varepsilon= 0\) 表示绝对贪心, \(\varepsilon\) 越大表示explore的强度越大。随着时间的推移,对reward的预估越来越准确的时候,贪心策略将会是最优策略。这个策略就是 \(\varepsilon - greedy\) 策略,很值得关注的,还有Softmax Action Selection策略;这两个策略哪个更好,依赖具体的数据分布、实际场景。

SoftMax Action公式为:

QQ20170408-233032

其中 \(\tau\) 为「温度参数」,可以发现,当 \(\tau \rightarrow 0\) 这个方法退化为 \(\varepsilon - greedy\) 。由于温度参数不好确定,所以此方法不太受欢迎。

无状态场景

在现实的场景中,多数是无状态的Bandit问题,也就是说随着时间的推移,奖励(环境)的分布会发生变化;常用的解决方案就是对距离比较近的奖励权重适当的调大。如果每一条反馈权重一样,预估value更新为:

\(Q_{k+1} = Q_k + \frac{1}{k} [R_k - Q_k]\)

其中 \(\frac{1}{k}\) 可以看做步长,步长大于 \(\frac{1}{k}\) 表示加大距离比较近的权重。上面式子通用的形式为:

\(Q_{k+1} = Q_k + \alpha [R_k - Q_k]=(1-\alpha)Q_k + \alpha R_k\)

那么问题来了,如果合理的确定这个超参数 \(\alpha\) 呢,这里需要一种方式衡量分布变化的「速度」,如果变化的快就需要适当增加 \(\alpha\) 的值。

一个简单想到的方式,假如有1000条样本,average的方式分别计算前后500条的value,通过「线性插值」得到 \(Q_{250}\)\(Q_{750}\) 之间的所有预估值,然后可以通过最小二乘(或者别的损失函数),学出来一个 \(\alpha\) ;这个方法不一定合理,只是提供一个学习 \(\alpha\) 的思路。

Optimistic Initial Values

初始值设置过高会增加explore的概率(即使对greedy方式),过低会降低explore的概率。下图很有意思:

QQ20170409-113034

 

Associative Search (Contextual Bandits)

上面介绍的bandit问题中,考虑这样一个场景:有100个独立的Bandit问题,编号为 \(B_1,B_2,...,B_{100}\) ,每次系统随机的给你选择一个 \(B_i\) ,然后你对 \(B_i\) 再选择一个action;如果每次选择的 \(B_i\) 是哪个对你不可见,并且不同的 \(B_i\) 下,相同的action得到的reward的分布不一致,这种情况下, 就很难学习出来一个合理的模型。这里解决方案就是将不同的 \(B_i\) 区分出来。

说白了,其实就是,当前时刻的行为,会影响下一个时刻的环境和反馈;确定当前行为的时候,需要考虑环境因素。

资料

《Reinforcement Learning: An Introduction》第二章

未经允许不得转载:大数据算法 » 强化学习(2)-Bandit问题

分享到:更多 ()

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站