[RL Note] K 臂赌博机

1. 问题描述

  $k$ 臂赌博机问题指的是在一个具有 $k$ 个拉杆的老虎机上进行赌博,每次赌博可以选择拉动一个拉杆,然后会得到一定的奖金收益。每个拉杆所带来的收益分布可能是不同的。通过重复地赌博,玩家可以学会只拉动带来收益最高的拉杆,从而最大化收益。

  更一般的,$k$ 臂赌博机问题指的是重复地在 $k$ 个动作中进行选择,每次动作后会得到一定的收益,收益由所选动作决定的平稳概率分布产生。目标是在一段时间内最大化收益的期望。

2. 动作价值

  $k$ 臂赌博机问题中拉动每个拉杆都对应了一个动作,一共有 $k$ 个动作。选择每个动作时都有一个期望收益,称为动作的价值(Action Values)或动作价值函数。记 $A_t$ 为 $t$ 时刻选择的动作,$R_t$ 是对应的收益,则任一动作 $a$ 的价值 $q_*(a)$ 定义为选择动作 $a$ 时收益的期望,即

\begin{align}
q_*(a) &\doteq \mathbb{E}[R_t|A_t = a] \qquad \forall a \in {1, \cdots, k} \\
&= \sum_r p(r|a)r \tag{1}
\end{align}

  在 $k$ 臂赌博机问题中,如果已经知道了每个动作的价值,要最大化期望收益,则只要每次都选择价值最高的动作即可,即选择

\begin{equation}
\underset{a}{\arg\max} \, q_*(a) \tag{2}
\end{equation}

指定的动作。

3. 估计动作的价值

  在实际中,往往不能事先知道如果每个动作的准确价值。此时可以动过反复尝试各种动作并记录价值,对动作的价值进行估计。动作 $a$ 在 $t$ 时刻的价值的估计记为 $Q_t(a)$,为了更好地选择动作来最大化收益,希望 $Q_t(a)$ 尽可能接近 $q_*(a)$。

  估计动作价值的方法之一是计算选择动作所带来收益的平均值,称为采样平均方法(Sample Average Method),定义为

\begin{align}
Q_t(a) &\doteq \frac{t\;时刻前选择动作\;a\;得到的收益总和}{t\;时刻前选择动作\;a\;的次数} \\
&= \frac{\sum_{i=1}^{t-1} R_i \cdot 1_{A_i = a} }{\sum_{i=1}^{t-1} 1_{A_i = a} } \tag{3}
\end{align}

其中 $1_{A_i = a}$ 当 $A_i = a$ 时为 $1$,否则为 $0$。注意上式中求和上限为 $t-1$,在 $t$ 时刻,使用 $t$ 时刻前的数据进行估计。如果 在 $t$ 时刻前某个动作从来没有被选择过,则上式的分母会变为零,此时将 $Q_t(a)$ 定义为某个默认值,比如 $0$。

4. 动作选择

  有了对动作价值的估计,一个简单的策略是每次都选择具有最高估计价值的动作,称为贪心动作。如果有多个贪心动作,则随机选择一个。这种动作选择方法记为

\begin{equation}
\underset{a}{\arg\max} \, Q_t(a) \tag{4}
\end{equation}

注意式 $(4)$ 与式 $(2)$ 的区别:式 $(2)$ 的前提是已经知道了动作的真实价值 $q_*(a)$,只需选择具有最大价值的动作,即可最大化收益;而式 $(4)$ 的前提是并不知道 $q_\ast(a)$,根据历史数据估计动作的价值 $Q_t(a)$,选择具有最大估计价值的动作。

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注