2021 重启强化学习(3) 多摇臂老虎机

2021-03-24 本文已影响0人 zidea

020.jpg

如果想观看相关视频可以在西瓜视频(账号zidea)或者哔哩哔哩(账号zidea2015)找到我发布视频解说，注意头像和简书使用头像一致。

多摇臂老虎机

在强化学习中多摇臂老虎机相对比较简单，所以我们就从这个多摇臂老虎机说起，看如何将解决多摇臂老虎机的方法应用到推荐系统中。一个赌徒，要去摇老虎机，走进赌场一看，一排老虎机，外表一模一样，但是每个老虎机吐钱的概率可不一样，他不知道每个老虎机吐钱的概率分布是什么，那么每次该选择哪个老虎机可以做到最大化收益呢？这就是多臂老虎机问题 ( Multi-armed bandit problem, K-armed bandit problem, MAB )。

接下来我们数学的语言简单描述一些摇臂老虎机问题，以及如何用强化学习方法来解决这个问题。多摇臂老虎机是一个单一状态的蒙特卡洛规划，是一种序列决策的问题，这种问题是在利用(exploitation)和探索(exploration)之间保持平衡。

在多摇臂老虎机是简单强化学习问题

无需考虑状态
没有延时奖励问题，不会考虑当前状态对以后发生事情有任何影响
所以就只需要学习 State-Action Value 状态行动价值函数

在摇臂老虎机中状态、动作和奖励

动作: 摇哪个臂，用 $A_t$ 表示第 $t$ 轮的行为
$Action = (0,1,0,0)$
奖励: 每次摇臂获得的奖金 $R_t$ 表示 t 时刻获取的奖励
$Reward = (0,1)$
状态行动价值函数(State-Action Value)
$Q^{*}(a) = \mathbb{E}[R_t|A_t=a]$

假设摇臂 $T$ 次，那么按照什么策略摇臂，才能使期望累积奖励最大，当 $Q^{*}(a)$ 已知时，每次都选择 $Q^{*}(a)$ 最大的 $a$ (贪心策略)

接下来介绍几种策略来解决摇臂老虎机问题

贪心策略

一般情况下， $Q^{*}(a)$ 对于玩家而言是未知的或具有不确定性。
在玩家在第 $t$ 轮时只能依赖于当时对 $Q^{*}(a)$ 估计值 $Q_t(a)$ 进行选择
此时，贪心策略在第 $t$ 轮选择 $Q_t(a)$ 最大的 $a$

利用和探索

利用(Exploitation)

所谓利用就是在保证过去的决策中得到最佳回报，按照贪心策略进行选择的话，也就是选择估计的 $Q_t(a)$ 最大的行为 $a$ ,这样做虽然最大化即时奖励，但是可能由于 $Q_t(a)$ 只是对 $q(a)$ 的估计，估计的不确定性导致按照贪心策略选择行为不一定 $q^*(a)$ 最大的行为

探索(Exploration)

所谓探索就是寄希望在未来得到跟大的回报，选择贪心策略之外的行为(non-greedy actions) 可能短期奖励会比较低，但是长期奖励比较高，通过探索可以找到奖励更大的行为，供后续选择。

贪心策略和 $\epsilon$ 贪心策略

贪心策略形式化地表示
$A_t = \argmax_{a} Q_t(a)$

$\epsilon$ 贪心策略

以概率 $1 - \epsilon$ 按照贪心策略进行行为选择
以概率 $\epsilon$ 在所有行为中随机选择一个
$\epsilon$ 的取值取决于 $q^*(a)$ 的方差，方差越大 $\epsilon$ 取值应该越大

根据历史观测样本的平均值对 $q^*(a)$ 进行估计

$Q_t(a) = \frac{\sum_{i=1}^{t-1} R_i \mathbb{I}_{A_i=\alpha}}{\sum_{i=1}^{t-1} \mathbb{I}_{A_i=\alpha}}$

约定: 当分母等于 0 时， $Q_t(a) = 0$
当分母趋于无穷大时， $Q_t(a)$ 收敛于 $q^*(a)$

行为估值的增量式

$Q_n = \frac{R_1 + R_2 + \cdots + R_{n-1}}{n-1}$

增量式实现
$\begin{aligned} Q_{n+1} = \frac{1}{n} \sum_{i=1}^n R_i\\ = \frac{1}{n} \left( R_n + \sum_{i=1}^{n-1} R_i \right)\\ = \frac{1}{n} \left( R_n + (n-1) \frac{1}{n-1} \sum_{i=1}^{n-1} R_i \right)\\ \frac{1}{n} \left( R_n + (n-1) Q_n \right)\\ \frac{1}{n} \left( R_n + nQ_n - Q_n \right)\\ Q_n + \frac{1}{n}\left[ R_n - Q_n \right] \end{aligned}$

这一轮收益以及之前的均值，好处是无需每次求和。过去均值以及当前收益就可以计算出当前均值。而且可以看成更新就是将当前值更新到过去的值来实现更新。

$Q_{n+1} = Q_n + \frac{1}{n}\left[ R_n - Q_n \right]$

$\frac{1}{n}$ 是学习率，在梯度下降中设定 $\eta$
看起来是不是有点熟悉，

2021 重启强化学习(3) 多摇臂老虎机

多摇臂老虎机

在多摇臂老虎机是简单强化学习问题

在摇臂老虎机中状态、动作和奖励

贪心策略

利用和探索

利用(Exploitation)

探索(Exploration)

贪心策略和 $\epsilon$ 贪心策略

$\epsilon$ 贪心策略

根据历史观测样本的平均值对 $q^*(a)$ 进行估计

行为估值的增量式

猜你喜欢

热点阅读

2021 重启强化学习(3) 多摇臂老虎机

多摇臂老虎机

在多摇臂老虎机是简单强化学习问题

在摇臂老虎机中状态、动作和奖励

贪心策略

利用和探索

利用(Exploitation)

探索(Exploration)

贪心策略和 贪心策略

贪心策略

根据历史观测样本的平均值对 进行估计

行为估值的增量式

猜你喜欢

热点阅读

贪心策略和 $\epsilon$ 贪心策略

$\epsilon$ 贪心策略

根据历史观测样本的平均值对 $q^*(a)$ 进行估计