[RL Notes] K 臂赌博机

Author: nex3z 2019-10-11

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\limits_{i=1}^{t-1} R_i \cdot 1_{A_i = a} }{\sum\limits_{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)$，选择具有最大估计价值的动作。