有关多臂老虎机问题的一些算法

李傲

发布于：2021年12月2日

用数理统计方法解决多臂老虎机问题

摘要

多臂老虎机问题（Multi-Armed Bandit problem，简称MAB问题）是概率论与数理统计中一个经典问题，也属于机器学习中强化学习的范畴。

在这个问题中，赌徒必须决定在一系列试验中使用不同的老虎机中的哪一个，以最大化他的回报。这一经典问题之所以受到广泛关注，是因为它提供了一个简单的模型，在探索（尝试每个机器以找到回报最好的一台）、利用（使用带来最好回报的老虎机）之间进行权衡。强化学习现在也面对着同样的困境，即探索和利用( Explore ＆ Exploit，简称 E＆E) 问题。

下文我将建立MAB问题的数学模型，并探讨一些基于数理统计方法的多臂老虎机问题的近似最优解决方案。

关键词：概率论数理统计强化学习贪心算法假设检验汤普森抽样

1简介

用科学的语言来阐述这个问题，即为我们必须以最大化其预期收益的方式在备选选择之间分配固定的有限资源，而每个选择的属性在分配时仅部分已知，通过将资源分配给选择并得到结果后，我们会对每种选择有更深入的了解，以此不断优化自己的选择。

多臂老虎机这个名字来自一个设想，一个赌徒面前有个老虎机，事先他不知道每台老虎机的真实盈利情况，他只能根据每次玩老虎机的结果来选择下次拉哪台老虎机的摇杆（Arm）或者停止赌博，来最大化自己整个过程中的收益。

每台机器都会根据特定于该机器的概率分布提供一个随机奖励，分布对于赌徒是未知的。赌徒的目标是通过一系列摇杆拉动来最大化获得的奖励总额。赌徒在每次试验中面临的关键权衡是利用（Explosit）预期收益最高的机器，和探索（Explore）以获得更多关于其他机器预期收益的信息。

机器学习中的强化学习（Reinforcement Learning，RL），用于描述和解决智能体（Agent）在与环境的交互过程中通过学习策略以达成回报最大化或实现特定目标的问题，即为复杂的MAB问题，赌徒可以看作智能体，拉动摇杆可以视作与环境的交互。

2模型建立

多臂老虎机问题可以看作是一组真实分布，每个分配都与其中一个提供的奖励相关联。是与这些奖励分布相关的平均值。赌徒每轮重复地玩一个老虎机并观察相关的奖励，目标是最大化收集到的奖励的总和。是剩余的回合数。多臂老虎机在形式上等价于单状态马尔可夫决策过程。轮后，我们定义遗憾为最佳策略相奖励总和与收集的奖励总和之间的差：

其中是最大奖励均值，，是第轮的实际奖励。

我们的目标可以近似转化为：

3模型假设

（1）假设每台老虎机每轮提供的奖励总体服从正态分布。

（2）假设老虎机可能会产生负的奖励。

（3）假设赌徒是理性的。

4解决问题前的准备

4.1 normrnd()函数

下文中的代码主要是MATLAB语言，我选择使用normrnd()函数来生成正态分布随机数，在使用之前先测试实验多少次会具有显著的正态分布特征。

注意：该函数的使用需要安装Statistics and Machine Learning Toolbox

图 2：10次实验

图 3：100次实验

图 4：1000次实验

我们可以显著看到当试验次数达到1000次及以上时，抽样结果非常接近于正态分布。

4.2 randn()函数

生成平均奖励值主要使用randn()函数，我测试了10000次，其中函数生成的最大值与最小值如下图所示

图 5：randn函数生成的最大值与最小值

5 MAB问题的解决方案

5.1 ϵ-greedy算法

Step 1：选定一个之间的基准，记为。

Step 2：先进行一定次数的探索，选定一个当前平均回报较高的选择。

Step 3：开始利用，每次先生成一个随机数，若，则选择当前最优选择，反之，从个选择中任选。

Step 4：利用结束之后更新每个选择的平均回报，并返回Step 4，直到全部试验结束。

在这个算法中，每次利用时，当前最优选择会有的概率会被选中，随着时间的流逝，最好的机器会越来越频繁地被选择。

简而言之，ϵ-greedy策略意味着大多数时候都选择当前最佳选项（“贪婪”），但有时选择概率很小的随机选项

一些变体：

ϵ-decreasing算法

类似于ϵ-greedy算法，不同之处在于随着实验的进行而减少，导致开始时的高度探索行为和结束时的高度剥削行为。

ϵ-first算法

类似于ϵ-greedy算法，不同之处在于纯探索阶段之后是纯开发阶段。{\displaystyle N}探索阶段占据试验，利用阶段占据次{\displaystyle (1-\epsilon )N}试验。在探索阶段，随机选择一个选项（概率均匀），在开发阶段，总是选择最好的选项。

这几种算法的比较如下图，每种情况下算法的优劣不一定相同，下图仅随机列举一种，但是我们可以发现所有的算法都会比完全随机的情况要好。

图 6：不同算法间的累计获利

5.2 UCB算法

UCB算法全称是Upper Confidence Bound（置信区间上界），该算法的精神被认为是乐观地面对不确定性。

Step 1：在前轮，每个摇杆各选择一次。

Step 2：在轮中，选择指数最大的选项，指数定义为：

其中，是选项当前的奖励均值，是选项当前累计被选择的次数。

Step 3：记录获得的奖励,并更新和。

其中叫做Bonus，本质上是均值的标准差。这个公式反映：均值越大，标准差越小，被选中的概率会越来越大，起到了Exploit的作用。同时那些些被选次数较少的臂也会得到试验机会，起到了Explore的作用。

一些变体：

LCB算法

LCB算法的全称是Upper Confidence Bound(置信区间上界)，相较于UCB算法，它会选择置信区间下界，即把UCB算法中的更新为：

LCB算法是一种悲观保守的算法。不过随着时间的流逝，它的效果会逐渐趋近于UCB算法。

图 7：不同算法间的累计获利

5.3 汤普森采样（Thompson sampling）算法

假设每个摇杆是否产生收益，其背后有一个概率分布，产生的平均收益的为p。我们只要不断的实验，去估计出一个置信度较高的“的概率分布”就可以了，而分布就可以看作是概率的概率分布，可以给出所有概率出现的可能性大小。

Step 1：设每个摇杆都维护一个分布的概率密度函数，初始都设置为。

Step 2：先进行一定次数的探索，若被选中的摇杆的收益大于1（条件可以根据不同的多臂老虎机条件来设定），则，反之。

Step 3：在利用阶段，用每个摇杆现在的分布产生一个随机数，选择所有摇杆产生的随机数中最大的那个摇杆去摇，并更新分布的参数。

图 8：不同算法间的累计获利

6解决方案的优缺点

6.1方案的优点

1）所有的算法均达到了预期效果，即比随机情况要好。

2）所有的算法的复杂度都在可接受的范围内，耗时较短。

6.2方案的缺点

1）找不到最优解。

2）不同算法之间的差别没体现出来，或许是条件设置不够。

7总结

通过这次自主探索，我学习到了强化学习和数理统计相关的知识，并深刻地认识到了概率论在人工智能领域的重要作用。

8参考文献

Wikipedia，Multi-armed bandit， https://en.wikipedia.org/wiki/Multi-armed_bandit#cite_note-29，2021-12-2。
刑无刀，专治选择困难症—bandit算法，https://zhuanlan.zhihu.com/p/21388070，2021-12-2。
用户5753894，小孩都看得懂的多臂老虎机和汤姆森采样， https://cloud.tencent.com/developer/article/1853831，2021-12-2。

附录

1、测试normrnd()与·randn()函数：

clc,clear

N=10;%这里可以改变

answer=zeros(1,N);

for n=1:N

answer(n)=normrnd(1,1);

end

subplot(1,2,1);

normplot(answer);

subplot(1,2,2);

hist(answer);

K = 10;

for n=1:100000

    AverReward = randn([1 K]);
    
    maxx(n)=max(AverReward);
    
    minn(n)=min(AverReward);
    
end

max(maxx)

min(minn)

2、 ϵ-greedy算法：

% 10-Armed Bandit

K = 10;

AverReward = randn([1 K]);

N = 10000; % 10000 experiments

j=1;

%epsilon-greedy策略

for epsilon=[0,0.1:0.2:0.9,1]

%当epsilon=0时近似看作epsilon-decreasing策略

%当epsilon=1时为完全随机策略

SumSum=zeros(1,N);

SumReward=zeros(1,K);

for n=1:1000

Action = unidrnd(K);

Reward(Action) = normrnd(AverReward(Action), 1);

SumReward(Action)=SumReward(Action)+Reward(Action);

SumSum(n)=sum(SumReward);

end

Q=SumReward./n;

%Q为经过探索后获得的平均奖励序列

for n = 1000:N

[maxx, i] = max(Q);

if(maxx\~=0 && rand(1) \< 1 - epsilon)

Action = i;

else

Action = unidrnd(K);

end

Reward(Action) = normrnd(AverReward(Action), 1);

SumReward(Action)=SumReward(Action)+Reward(Action);

SumSum(n)=sum(SumReward);

Q(Action) = SumReward(Action)/n;

end

plot(1:N,SumSum,'LineWidth',2);

hold on;

legend_str{j}=['\$\\epsilon\$=' num2str(epsilon)];

j=j+1;

end

%epsilon-first策略

epsilon=0.1;

SumSum=zeros(1,N);

SumReward=zeros(1,K);

for n=1:N\*epsilon

Action = unidrnd(K);

Reward(Action) = normrnd(AverReward(Action), 1);

SumReward(Action)=SumReward(Action)+Reward(Action);

SumSum(n)=sum(SumReward);

end

Q=SumReward./n;

[maxx, i] = max(Q);

action=i;

for n=N\*epsilon:N

Reward(Action) = normrnd(AverReward(Action), 1);

SumReward(Action)=SumReward(Action)+Reward(Action);

SumSum(n)=sum(SumReward);

end

plot(1:N,SumSum,LineWidth=2);

legend_str{j}=['\$epsilon\$=' num2str(j)];

legend(legend_str);

3、UCB算法：

% 10-Armed Bandit

K = 10;

AverReward = randn([1 K]);

N = 10000; % 10000 experiments

j=1;

%UCB策略

SumReward=zeros(1,K);

SumSum=zeros(1,N+K);

for n=1:K

Action=n;

Reward(Action) = normrnd(AverReward(Action), 1);

SumReward(Action)=SumReward(Action)+Reward(Action);

SumSum(n)=sum(SumReward);

end

I=SumReward;

T=ones(1,K);

%前K次实验之后

for n=1:N

[maxx, i] = max(I);

Action=i;

Reward(Action) = normrnd(AverReward(Action), 1);

SumReward(Action)=SumReward(Action)+Reward(Action);

SumSum(n+K)=sum(SumReward);

T(Action)=T(Action)+1;

I(Action)=SumReward(Action)/T(Action)+2\*sqrt(2\*log(n+K)/T(Action));

end

plot(SumSum,LineWidth=2);

legend_str{j}=['UCB'];

j=j+1;

hold on;

for epsilon=[0,0.1,1]

%当epsilon=0时近似看作epsilon-decreasing策略

%当epsilon=1时为完全随机策略

SumSum=zeros(1,N);

SumReward=zeros(1,K);

for n=1:1000

Action = unidrnd(K);

Reward(Action) = normrnd(AverReward(Action), 1);

SumReward(Action)=SumReward(Action)+Reward(Action);

SumSum(n)=sum(SumReward);

end

Q=SumReward./n;

%Q为经过探索后获得的平均奖励序列

for n = 1000:N

[maxx, i] = max(Q);

if(maxx\~=0 && rand(1) \< 1 - epsilon)

Action = i;

else

Action = unidrnd(K);

end

Reward(Action) = normrnd(AverReward(Action), 1);

SumReward(Action)=SumReward(Action)+Reward(Action);

SumSum(n)=sum(SumReward);

Q(Action) = SumReward(Action)/n;

end

plot(1:N,SumSum,'LineWidth',2);

hold on;

legend_str{j}=['\$\\epsilon\$=' num2str(epsilon)];

j=j+1;

end

legend(legend_str);

4、汤普森抽样算法（Thompson Sampling）

% 10-Armed Bandit

K = 10;

AverReward = randn([1 K]);

N = 10000; % 10000 experiments

j=1;

%汤普森策略

beta=ones(K,2);

SumReward=zeros(1,K);

SumSum=zeros(1,N);

for n=1:1000

Action = unidrnd(K);

Reward(Action) = normrnd(AverReward(Action), 1);

if(Reward(Action)\>1)

beta(Action,1)=beta(Action,1)+1;

else

beta(Action,2)=beta(Action,2)+1;

end

SumReward(Action)=SumReward(Action)+Reward(Action);

SumSum(n)=sum(SumReward);

end

ch=zeros(1,K);

%前1000次实验之后

for n=1000:N

for choice=1:K

ch(choice)=betarnd(beta(choice,1),beta(choice,2));

end

[maxx, i] = max(ch);

Action=i;

Reward(Action) = normrnd(AverReward(Action), 1);

if(Reward(Action)\>1)

beta(Action,1)=beta(Action,1)+1;

else

beta(Action,2)=beta(Action,2)+1;

end

SumReward(Action)=SumReward(Action)+Reward(Action);

SumSum(n+K)=sum(SumReward);

end

plot(SumSum,LineWidth=2);

legend_str{j}=['Thompson Sampling'];

j=j+1;

hold on;

SumReward=zeros(1,K);

SumSum=zeros(1,N+K);

for n=1:K

Action=n;

Reward(Action) = normrnd(AverReward(Action), 1);

SumReward(Action)=SumReward(Action)+Reward(Action);

SumSum(n)=sum(SumReward);

end

I=SumReward;

T=ones(1,K);

%前K次实验之后

for n=1:N

[maxx, i] = max(I);

Action=i;

Reward(Action) = normrnd(AverReward(Action), 1);

SumReward(Action)=SumReward(Action)+Reward(Action);

SumSum(n+K)=sum(SumReward);

T(Action)=T(Action)+1;

I(Action)=SumReward(Action)/T(Action)+2\*sqrt(2\*log(n+K)/T(Action));

end

plot(SumSum,LineWidth=2);

legend_str{j}=['UCB'];

j=j+1;

hold on;

for epsilon=[0,0.1,1]

%当epsilon=0时近似看作epsilon-decreasing策略

%当epsilon=1时为完全随机策略

SumSum=zeros(1,N);

SumReward=zeros(1,K);

for n=1:1000

Action = unidrnd(K);

Reward(Action) = normrnd(AverReward(Action), 1);

SumReward(Action)=SumReward(Action)+Reward(Action);

SumSum(n)=sum(SumReward);

end

Q=SumReward./n;

%Q为经过探索后获得的平均奖励序列

for n = 1000:N

[maxx, i] = max(Q);

if(maxx\~=0 && rand(1) \< 1 - epsilon)

Action = i;

else

Action = unidrnd(K);

end

Reward(Action) = normrnd(AverReward(Action), 1);

SumReward(Action)=SumReward(Action)+Reward(Action);

SumSum(n)=sum(SumReward);

Q(Action) = SumReward(Action)/n;

end

plot(1:N,SumSum,'LineWidth',2);

hold on;

legend_str{j}=['\$\\epsilon\$=' num2str(epsilon)];

j=j+1;

end

legend(legend_str);

更新于：2022年7月10日

算法

机器学习

数学

有关电磁学的笔记

电场强度库仑定律： \[ F=\frac{1}{4 \pi \varepsilon_{0}} \frac{q \cdot q_{0}}{r^{2}} \] 真空介电常量： \[ \va...

有关平方根倒数速算法的小感想

今天偶然看到了一个来自《Quake III》（雷神之锤III）的算法，平方根倒数速算法（Fast Inverse Square Root），不得不感叹卡神的智慧。 123456789101...