前言
哈喽 Everyone ! 又见面了~
今天阿南想和大家讲一讲玩赌博机的策略。 这个学期开了一门课 “强化学习与动态规划” 里面第一节课就有提到利用 ”强化学习 (Reinforcing Learning)“ 的概念达到收益最大化并以 多臂赌博机 (Multi-arm Bandits) 为例分别介绍了三种算法：
- 贪婪算法 (Greedy algorithm)
- $\epsilon-$贪婪算法 ($\epsilon-$Greedy algorithm)
- 上置信区间带 (Upper-Confidence-Bound, UCB)
接下来我将尽可能通俗易懂地讲解这三种算法。 Here we go ~
正文
首先，用图片给大家介绍一下啥子是 赌博机 (Bandits)
如下图所示机器旁边有一个把手，当拉下这个把手屏幕就会转动然后显示所得到的奖励，这个就是基本的 单臂赌博机。
接下来正式介绍 多臂赌博机 (Multi-arm Bandits)：
因为在网上找不到实体的多臂赌博机，故用这个漫画图作为说明。首先我们看到它们最明显的区别就是机器旁边把手数量的不同。多臂赌博机拥有多个把手分别对应着特定的 动作 (action), 并且每个动作所带来的回报也是不相同的。
我们目的当然是使我们的收益最大化。所以如果我们知道拉动哪根杆子能给我们带来最大的收益的话那么问题就很简单了。我们就只需不断地拉动那根能给我们带来最大收益的拉杆，即一直执行能给我们带来最大收益的动作。然而现实却并不总是那么美好，我们往往不可能提前知道每个动作能带来的收益，也不可能知道每个动作收益所服从的分布。
那么我们要怎么样才能实现收益最大化，完成一夜暴富的梦想呢？好的，接下来阿南就要开始介绍之前所提到那三种方法了。首先介绍各个符号的定义，以防大家迷失在后来的公式中。
\[\begin{aligned} t&: 当前是第t次实验 \\ R_t(a)&: t 时刻选择动作 a 所实际得到的奖励 \\ Q_t(a) &: t 时刻选择行为 a 所能得到奖励的数学期望 \\ q_*(a) &: 动作 a 能够带来的真实回报（这个是上帝视角，凡人往往不知道）\\ N_t(a) &：截止至时刻 t ，动作 a 被选择的次数 \end{aligned} \tag{1}\]
刚开始我对 $R_t(a)$, $Q_t(a)$ 和 $q_*(a)$ 这三个参数傻傻分不清楚，为了避免后人走弯路我来简单地讲解一下这几个参数。
首先是 $R_t(a)$ 代表的是我此刻在现实中拉下第 $a$ 跟杆，或是说执行第 $a$ 个动作时赌博机实际给我的回报。而 $Q_t(a)$ 的含义则是在 $t$ 时刻我还没有执行动作 $a$ ，但是我能用过去的 $t-1$ 个时刻的已知数据去估计当前时刻 $t$ 的奖励，这个估计值是当前 $t$ 时刻对于动作 $a$ 的奖励的数学期望。 $q_*(a)$ 的含义就是动作 $a$ 的实际奖励值，这个实际中并不知道（要是知道这个阿南也不用写这篇文章了）。
咳咳！接下来介绍第一个算法：
贪婪算法(Greedy algorithm)
贪婪算法，顾名思义即一味地追求回报最高的行为。并且贪婪算法是一种 短视的 (short-sighted) 算法，即只考虑当前时刻所能取得的最大收益而不去考虑以后的情况。这就导致了贪婪算法时常陷入 局部最优(Local optimum)，往往达不到 全局最优(Global optimum)。
输入： $n$ 个待选择的动作 $a_i, i\in 1,2,3…,n$
输出： ”最优“回报
贪婪算法的步骤如下：
- 将 $n$ 个动作全部执行一遍，记录下每个动作 $a_i$ 的回报 R_t(a_i)
- 计算每个动作 $a_i$ 在下一个时刻的期望回报 $Q_t(a_i)$
- 选择期望回报最大的动作 $a_i$
- 按实际实验次数重复步骤 $2 \to 3$
这种每台机器上试验几次，之后找出收益最多的一个一直玩，这种策略被称作 $sample-then-greedy$，类似于年轻时尝试几个行业，之后就一直在这个行业做下去。
$\epsilon-$贪婪算法 ($\epsilon-$Greedy algorithm)
第一个介绍的贪婪算法有一个缺点就是只 利用(exploitation) 当前时刻的最优值，而不去 探索(exploration) 潜在的更大收益的可能操作。
现在介绍基于贪婪算法的改良版 $\epsilon-$贪婪算法:
其在贪婪算法的基础上引入了参数 $\epsilon$，该参数使得模型可以探索尽管当前时刻表现比较差但是有很大潜力的行为。
\[\epsilon: 有 \epsilon 的几率探索非最优选项。并且对于剩下的 n-1 种非最优选项被选择的几率是均等的，均为 \frac{\epsilon}{n-1}\]输入： $n$ 个待选择的动作 $a_i, i\in 1,2,3…,n$
输出： ”最优“回报
$\epsilon-$贪婪算法的步骤如下：
- 将 $n$ 个动作全部执行一遍，记录下每个动作 $a_i$ 的回报 R_t(a_i)
- 计算每个动作 $a_i$ 在下一个时刻的期望回报 $Q_t(a_i)$
- 以 $1-\epsilon$ 的概率选择期望回报最大的动作 $a_i$，以 $\frac{\epsilon}{n-1}$ 的概率选择剩下的 $n-1$ 个非最优行为。
- 按实际实验次数重复步骤 $2 \to 3$
置信上界选择方法 (Upper-Confidence-Bound, UCB)
这个乍一听挺唬人的，学术的解释就是比较置信区间，不断的选择拥有最大回报上界的行为 $a_i$。简单滴可理解为求每个行动的最大可信值，选择最大可信值最大的行动。
那么如何计算这个上界呢？我们给出如下公式：
\[A_t = arg\,\max_a [Q_t(a) + c\sqrt{\frac{\ln t}{N_t(a)}}] \tag{2}\]其中参数 $c$ 是一个调节参数，$c$ 越大则对于出现频率较小的行为比较有利，反之亦然。通常取值为 $(0,1]$。
好了，到这里关于解决多臂赌博机收益问题的三种算法就介绍完啦~ 大家要是发现有哪些错误或者有什么疑问可以私聊阿南共同进步！
谢谢观看！ :)
