一、問題描述

1.1 問題定義

??有一個用于 K 根拉桿的老虎機，每一根拉桿都對應一個關于獎勵的概率分布 R 。每拉動一個拉桿，就可以從該拉桿的獎勵概率分布中獲得一個獎勵 r 。在各拉桿的獎勵概率分布未知的情況下，從頭開始嘗試，目標是在操作 T 次拉桿后獲得盡可能高的累積獎勵。

??由于獎勵的概率分布是未知的，因此我們需要在“探索拉桿的獲獎概率”和“根據經驗選擇獲獎多的拉桿”中進行權衡。

【通俗易懂：有 K 個機器，你不知道每個機器的獎勵概率分布，你只有 T 次機會選擇機會，探索機器的獎勵概率分布也算在 T 次內，然后盡可能獲得最多的獎勵。】

【示例：有 1 個 10 臂老虎機，你有 20 次選擇機會，你可以花 10 次機會探索前 5 臂，根據獲得的獎勵，選擇獎勵期望最大的一個，剩下 10 次都選擇最大的那 1 臂。（有可能獎勵期望最大在沒有探索的 5 臂中，也有可能在前 5 臂中，但是不是你選擇的那個）】

1.2 形式化描述

??多臂老虎機問題可以表示為一個元組 $<A,R>$，其中：

• A 為動作集合，其中一個動作表示拉動一根拉桿，若多臂老虎機有 K 個拉桿，則動作空間就是集合 { a 1 , a 2 , . . . , a K } \{a_1,a_2,...,a_K\} {a1?,a2?,...,aK?}，用 $a_t\in A$ 表示任意一個動作；
• R 為概率分布，拉動每一根拉桿的動作 a 都對應一個獎勵概率分布 $R(r|a)$，拉動不同拉桿的獎勵分布通常是不同。

??假設每個時間步只能拉動 1 根拉桿，多臂老虎機的目標為最大化一段時間步 T 內累積的獎勵：$max{\sum }_{t=1}^T{r}_t,r_t～R(?|a_t)$。其中 $a_t$ 表示在第 t 時間步拉動某一拉桿的動作，$r_t$ 表示動作 $a_t$ 獲得的獎勵。

1.3 累積懊悔

??對于每一個動作 a ，我們定義其期望獎勵為 $Q(a)=E_{r～R(?|a)}[r]$ 。于是，至少存在一根拉桿，它的期望獎勵不小于任意一根拉桿，將該最優期望獎勵表示為 $Q^{?}={\max }_{a\in A}Q(a)$ 。

• 懊悔：當前動作 a 與最優拉桿期望獎勵的差距，即 $R(a)=Q^{?}?Q(a)$
• 累積懊悔：操作 T 次拉桿后累積的懊悔總量，對于一次完整的 T 步決策 { a 1 , a 2 , . . . , a T } \{a_1,a_2,...,a_T\} {a1?,a2?,...,aT?} ，累積懊悔為：${\sigma }_R={\sum }_{t=1}^{T}R(a_t)$ 。

??所以求解 MAB 問題等價于最小化累積懊悔。

1.4 估計期望獎勵

??為了知道拉動哪一根拉桿可以獲得更高的獎勵，所以我們需要估計這根拉桿的期望獎勵。

算法流程：

對于 $?a\in A$ ，初始化計算器 $N(a)=0$ 和 期望獎勵估值 $\hat{Q}(a)=0$
for $t=1\to T$ do
??選取某根拉桿，該動作記為 $a_t$
??得到獎勵 $r_t$
??更新計數器：$N(a_t)+=1$
??更新期望獎勵估值：$\hat{Q}(a_t)+=\frac{1}{N(a_t)}[r_t?\hat{Q}(a_t)]$

示例：

??編寫一個拉桿為 10 的多臂老虎機。其中每個拉桿的獎勵服從伯努利分布，即每次有 p 的概率獲得獎勵 1 ，有 1-p 的概率獲得獎勵 0 。【0 表示沒有獲獎，1 表示獲獎。】

在 MAB 目錄下新建 BernoulliBandit.py 文件

代碼如下：

import numpy as np
import matplotlib.pyplot as pltclass BernoulliBandit:"""伯努利多臂老虎機，輸入 K 表示拉桿個數"""def __init__(self, K):self.probs = np.random.uniform(size=K)  # 隨機生成 K 個 0-1 的數，表示每個拉桿的獲獎概率self.best_idx = np.argmax(self.probs)  # 獲獎概率最大的拉桿self.best_prob = self.probs[self.best_idx]  # 最大的獲獎概率self.K=Kdef step(self, k):if np.random.rand() < self.probs[k]:return 1else:return 0np.random.seed(1)
K = 10
bandit = BernoulliBandit(K)
print("隨機生成了一個 %d 臂的伯努利多臂老虎機" % K)
print("獲獎概率最大的拉桿為 %d 號，其獲獎概率為 %.4f" % (bandit.best_idx, bandit.best_prob))

運行結果如下：

D:\RL\MAB\.venv\Scripts\python.exe D:\RL\MAB\BernoulliBandit.py 
隨機生成了一個10臂的伯努利多臂老虎機
獲獎概率最大的拉桿為1 號，其獲獎概率為0.7203進程已結束，退出代碼為 0

??接下來編寫 Solver 基礎類來解決 MAB 問題。具體的解決策略由每個繼承 Solver 的類來實現。

??新建 Solver.py 文件，文件代碼如下：

import numpy as npclass Solver:"""多臂老虎機解決方案抽象類"""def __init__(self, bandit):self.bandit = banditself.counts = np.zeros(self.bandit.K) # 每根拉桿的嘗試次數self.regret = 0 # 當前步的累積懊悔self.actions = []   # 記錄每一步的動作self.regrets = []   # 記錄每一步的累積懊悔def update_regret(self, k):# 記錄累積懊悔并保存，k為本次動作選擇的拉桿的編號self.regret += self.bandit.best_prob - self.bandit.probs[k]self.regrets.append(self.regret)def run_one_step(self):# 返回當前動作選擇的拉桿，由具體的策略實現raise NotImplementedErrordef run(self, num_steps):# 運行一定次數，num_steps為總運行次數for _ in range(num_steps):k = self.run_one_step()self.counts[k] += 1self.actions.append(k)self.update_regret(k)

配置 numpy 和 matplotlib 模塊：

訪問文章：配置 numpy 和 matplotlib 模塊

二、解決方法

2.1 ?-貪婪算法

??完全貪婪算法就是在每一刻都采取期望獎勵估值最大的動作，這就是純粹的利用，沒有探索。而 ε-貪婪算法則是在其基礎上添加了噪聲，每次以 1-ε 的概率選擇以往經驗中期望獎勵估值最大的那根拉桿【利用】，以 ε 的概率隨機選擇一根拉桿【探索】，公式如下：

$$a_t=\{\begin{array}{l}arg\underset{a\in A}{\max }\hat{Q}，采樣概率：1??\\ 從A中隨機選擇，采樣概率：?\end{array}$$

??隨著探索次數不斷的增多，對各個動作的獎勵估計越來越準確，所以沒必要繼續花費大力氣進行探索。所以我們可以讓 ε 隨著時間衰減，但是不會到 0 。因為基于有限步觀測的完全貪婪算法仍然是一個局部信息的貪婪算法，永遠離最優解有一個固定的差距。

項目結構：

新建 EpsilonGreedy.py 文件，文件代碼如下：

import numpy as npfrom Solver import Solverclass EpsilonGreedy(Solver):def __init__(self,bandit,epsilon=0.01,init_prob=1.0):super(EpsilonGreedy,self).__init__(bandit)self.epsilon = epsilonself.estimates=np.array([init_prob]*self.bandit.K)def run_one_step(self):if np.random.random()<self.epsilon:k=np.random.randint(0,self.bandit.K)else:k=np.argmax(self.estimates)r=self.bandit.step(k)self.estimates[k]+=1./(self.counts[k]+1)*(r-self.estimates[k])return k

在新建 Main.py 文件，文件代碼如下：

import numpy as np
from matplotlib import pyplot as pltfrom BernoulliBandit import bandit
from EpsilonGreedy import EpsilonGreedydef plot_results(solvers, solver_names):"""輸出解決方法的累積懊悔變化圖"""for idx, solver in enumerate(solvers):time_list = range(len(solver.regrets))plt.plot(time_list, solver.regrets, label=solver_names[idx])plt.xlabel('Time Step')plt.ylabel('Cumulative regrets')plt.title('%d-arm bandit' % solvers[0].bandit.K)plt.legend()plt.show()np.random.seed(1)
epsilon_greedy_solver = EpsilonGreedy(bandit, epsilon=0.01)
epsilon_greedy_solver.run(5000)
print('epsilon-貪婪算法的累積懊悔為：', epsilon_greedy_solver.regret)
plot_results([epsilon_greedy_solver], ["EpsilonGreedy"])

運行 Main.py 文件，結果如下：

隨機生成了一個 10 臂的伯努利多臂老虎機
獲獎概率最大的拉桿為 1 號，其獲獎概率為 0.7203
epsilon-貪婪算法的累積懊悔為： 25.526630933945313

??接下來嘗試不同 ε 取值的結果：

修改 Main.py 代碼如下：

import numpy as np
from matplotlib import pyplot as pltfrom BernoulliBandit import bandit
from EpsilonGreedy import EpsilonGreedydef plot_results(solvers, solver_names):"""輸出解決方法的累積懊悔變化圖"""for idx, solver in enumerate(solvers):time_list = range(len(solver.regrets))plt.plot(time_list, solver.regrets, label=solver_names[idx])plt.xlabel('Time Step')plt.ylabel('Cumulative regrets')plt.title('%d-arm bandit' % solvers[0].bandit.K)plt.legend()plt.show()# np.random.seed(1)
# epsilon_greedy_solver = EpsilonGreedy(bandit, epsilon=0.01)
# epsilon_greedy_solver.run(5000)
# print('epsilon-貪婪算法的累積懊悔為：', epsilon_greedy_solver.regret)
# plot_results([epsilon_greedy_solver], ["EpsilonGreedy"])np.random.seed(0)
epsilons = [1e-4, 0.01, 0.1, 0.25, 0.5]
epsilon_greedy_solver_list = [EpsilonGreedy(bandit, epsilon=e) for e in epsilons]
epsilon_greedy_solver_names = ['epsilon={}'.format(e) for e in epsilons]
for epsilon_greedy_solver in epsilon_greedy_solver_list:epsilon_greedy_solver.run(5000)plot_results(epsilon_greedy_solver_list, epsilon_greedy_solver_names)

運行 Main.py 文件，結果如下：

隨機種子為 0 的結果很完美，但是選擇隨機種子為 1 的話，這是實驗結果：

但是將時間步擴大為 50000，實驗結果又變回來了

??接下來嘗試 ε 隨著時間反比例衰減，公式為：${?}_t=\frac{1}{t}$

修改 EpsilonGreedy.py 文件，文件代碼如下：

import numpy as npfrom Solver import Solverclass EpsilonGreedy(Solver):def __init__(self, bandit, epsilon=0.01, init_prob=1.0):super(EpsilonGreedy, self).__init__(bandit)self.epsilon = epsilonself.estimates = np.array([init_prob] * self.bandit.K)def run_one_step(self):if np.random.random() < self.epsilon:k = np.random.randint(0, self.bandit.K)else:k = np.argmax(self.estimates)r = self.bandit.step(k)self.estimates[k] += 1. / (self.counts[k] + 1) * (r - self.estimates[k])return kclass DecayingEpsilonGreedy(Solver):def __init__(self, bandit, init_prob=1.0):super(DecayingEpsilonGreedy, self).__init__(bandit)self.estimates = np.array([init_prob] * self.bandit.K)self.total_count = 0def run_one_step(self):self.total_count += 1if np.random.random() < 1 / self.total_count:k = np.random.randint(0, self.bandit.K)else:k = np.argmax(self.estimates)r = self.bandit.step(k)self.estimates[k] = 1. / (self.counts[k] + 1) * (r - self.estimates[k])return k

修改 Main.py 文件，文件代碼如下：

import numpy as np
from matplotlib import pyplot as pltfrom BernoulliBandit import bandit
from EpsilonGreedy import EpsilonGreedy, DecayingEpsilonGreedydef plot_results(solvers, solver_names):"""輸出解決方法的累積懊悔變化圖"""for idx, solver in enumerate(solvers):time_list = range(len(solver.regrets))plt.plot(time_list, solver.regrets, label=solver_names[idx])plt.xlabel('Time Step')plt.ylabel('Cumulative regrets')plt.title('%d-arm bandit' % solvers[0].bandit.K)plt.legend()plt.show()# np.random.seed(1)
# epsilon_greedy_solver = EpsilonGreedy(bandit, epsilon=0.01)
# epsilon_greedy_solver.run(5000)
# print('epsilon-貪婪算法的累積懊悔為：', epsilon_greedy_solver.regret)
# plot_results([epsilon_greedy_solver], ["EpsilonGreedy"])# np.random.seed(1)
# epsilons = [1e-4, 0.01, 0.1, 0.25, 0.5]
# epsilon_greedy_solver_list = [EpsilonGreedy(bandit, epsilon=e) for e in epsilons]
# epsilon_greedy_solver_names = ['epsilon={}'.format(e) for e in epsilons]
# for epsilon_greedy_solver in epsilon_greedy_solver_list:
#     epsilon_greedy_solver.run(50000)
# plot_results(epsilon_greedy_solver_list, epsilon_greedy_solver_names)np.random.seed(1)
decaying_epsilon_greedy_solver = DecayingEpsilonGreedy(bandit)
decaying_epsilon_greedy_solver.run(5000)
print('epsilon 反比衰減的貪婪算法的累積懊悔為：', decaying_epsilon_greedy_solver.regret)
plot_results([decaying_epsilon_greedy_solver], ["DecayingEpsilonGreedy"])

運行 Main.py 文件，結果如下：

D:\RL\MAB\.venv\Scripts\python.exe D:\RL\MAB\Main.py 
隨機生成了一個 10 臂的伯努利多臂老虎機
獲獎概率最大的拉桿為 1 號，其獲獎概率為 0.7203
epsilon 反比衰減的貪婪算法的累積懊悔為： 10.114334931260183進程已結束，退出代碼為 0

這是擴大時間步至 50000 的結果：

??從實驗結果可以發現，反比例衰減的 ε-貪婪算法可以使得累積懊悔與時間步的關系變為次線性，這明顯優于固定 ε 值的 ε-貪婪算法。

2.2 上置信界算法

??對于多臂老虎機來說，一根拉桿的探索次數較少，它的不確定性就很高。不確定越高，它具有的探索價值就越大。為此，引入不確定性度量 U(a) ，它隨著一個動作被嘗試次數的增加而減少。【說白了就是新鮮感】

??上置信界（UCB）算法是一種經典的基于不確定性的策略算法，其思想是基于霍夫丁不等式。在霍夫丁不等式中，令 $X_1,X_2,...,X_n$ 為 n 個獨立同分布的隨機變量，取值范圍為 [0,1] ，其經驗期望為 $\bar{x}=\frac{1}{n}{\sum }_{j=1}^n{X}_j$ ，則有 $$P(E[X]\ge \bar{x}+u)\le e^{?2n{u}^2}$$

??將霍夫丁不等式運用到多臂老虎機問題中。$\hat{Q}$ 代入 $\bar{x}$，不等式中 $u=\hat{U}(a_t)$ 代表不確定性度量。給定一個概率 $p=e^{?2N(a_t)U(a_t{)}^2}$ ，根據上述不等式，$Q(a_t)<\hat{Q}(a_t)+\hat{U}(a_t)$ 至少以概率 $1?p$ 成立，當 p 很小時，$Q(a_t)<\hat{Q}(a_t)+\hat{U}(a_t)$ 就以很大概率成立，所以 $\hat{Q}(a_t)+\hat{U}(a_t)$ 就是期望獎勵上界。

??根據 $p=e^{?2N(a_t)U(a_t{)}^2}$ 得知 $\hat{U}(a_t)=\sqrt{\frac{?\log p}{2N(a_t)}}$ ，其中 $N(a_t)$ 是該拉桿的已經拉動的次數。確定概率 p 就可以計算 $\hat{U}(a_t)$ 。

??在實際編程中，令 $p=\frac{1}{t}$ ；令 $\hat{U}(a_t)=\sqrt{\frac{?\log p}{2(N(a_t)+1)}}$ ，以免出現分母為 0 的情況；令 $a_t=argma{x}_{a\in A}[\hat{Q}(a)+c?\hat{U}(a)]$ ，用系數 c 來控制不確定性比重。

新建 UCB.py 文件，文件代碼如下：

import numpy as npfrom Solver import Solverclass UCB(Solver):def __init__(self, bandit, c, init_prob=1.0):super(UCB, self).__init__(bandit)self.total_count = 0self.estimates = np.array([init_prob] * self.bandit.K)self.c = cdef run_one_step(self):self.total_count += 1ucb = self.estimates + self.c * np.sqrt(np.log(self.total_count) / (2 * (self.counts + 1)))  # 計算上置信界k = np.argmax(ucb)r = self.bandit.step(k)self.estimates[k] += 1. / (self.counts[k] + 1) * (r - self.estimates[k])return k

修改 Main.py 文件，文件代碼如下：

import numpy as np
from matplotlib import pyplot as pltfrom BernoulliBandit import bandit
from EpsilonGreedy import EpsilonGreedy, DecayingEpsilonGreedy
from UCB import UCBdef plot_results(solvers, solver_names):"""輸出解決方法的累積懊悔變化圖"""for idx, solver in enumerate(solvers):time_list = range(len(solver.regrets))plt.plot(time_list, solver.regrets, label=solver_names[idx])plt.xlabel('Time Step')plt.ylabel('Cumulative regrets')plt.title('%d-arm bandit' % solvers[0].bandit.K)plt.legend()plt.show()def apply_epsilon_greedy_1():np.random.seed(1)epsilon_greedy_solver = EpsilonGreedy(bandit, epsilon=0.01)epsilon_greedy_solver.run(5000)print('epsilon-貪婪算法的累積懊悔為：', epsilon_greedy_solver.regret)plot_results([epsilon_greedy_solver], ["EpsilonGreedy"])def apply_epsilon_greedy_2():np.random.seed(1)epsilons = [1e-4, 0.01, 0.1, 0.25, 0.5]epsilon_greedy_solver_list = [EpsilonGreedy(bandit, epsilon=e) for e in epsilons]epsilon_greedy_solver_names = ['epsilon={}'.format(e) for e in epsilons]for epsilon_greedy_solver in epsilon_greedy_solver_list:epsilon_greedy_solver.run(50000)plot_results(epsilon_greedy_solver_list, epsilon_greedy_solver_names)def apply_decaying_epsilon_greedy():np.random.seed(1)decaying_epsilon_greedy_solver = DecayingEpsilonGreedy(bandit)decaying_epsilon_greedy_solver.run(50000)print('epsilon 反比衰減的貪婪算法的累積懊悔為：', decaying_epsilon_greedy_solver.regret)plot_results([decaying_epsilon_greedy_solver], ["DecayingEpsilonGreedy"])def apply_UCB():np.random.seed(1)c = 1  # 不確定性比重UCB_solver = UCB(bandit, c)UCB_solver.run(5000)print('上置信界算法累積懊悔為：', UCB_solver.regret)plot_results([UCB_solver], ["UCB"])apply_UCB()

運行 Main.py 文件，結果如下：

D:\RL\MAB\.venv\Scripts\python.exe D:\RL\MAB\Main.py 
隨機生成了一個 10 臂的伯努利多臂老虎機
獲獎概率最大的拉桿為 1 號，其獲獎概率為 0.7203
上置信界算法累積懊悔為： 70.45281214197854進程已結束，退出代碼為 0

2.3 湯普森采樣算法

??MAB問題還有一種經典算法——湯普森采樣，先假設每個拉桿的獎勵服從特定的概率分布，然后根據每個拉桿的期望獎勵來進行選擇。但是計算所有拉桿的期望獎勵的代價比較高，所以該算法使用采樣的方式，即根據當前每個動作 a 的獎勵概率分布進行一輪采樣，得到一組拉桿的獎勵樣本，再選擇樣本中獎勵最大的動作。【湯普森采樣是一種計算所有拉桿的最高獎勵概率的蒙特卡洛采樣方法】

??在實際中，通常用 Beta 分布對當前每個動作的獎勵概率分布進行建模。具體來說，若某拉桿被選擇了 k 次，其中 $m_1$ 次獎勵為 1，$m_2$ 次獎勵為 0，則該拉桿服從參數為 $(m_1+1,m_2+1)$ Beta 分布。

新建 ThompsonSampling.py 文件，文件代碼如下：

import numpy as npfrom Solver import Solverclass ThompsonSampling(Solver):def __init__(self, bandit):super(ThompsonSampling, self).__init__(bandit)self._a = np.ones(self.bandit.K)self._b = np.ones(self.bandit.K)def run_one_step(self):samples = np.random.beta(self._a, self._b)k = np.argmax(samples)r = self.bandit.step(k)self._a[k] += rself._b[k] += (1 - r)return k

修改 Main.py 文件，文件代碼如下：

import numpy as np
from matplotlib import pyplot as pltfrom BernoulliBandit import bandit
from EpsilonGreedy import EpsilonGreedy, DecayingEpsilonGreedy
from ThompsonSampling import ThompsonSampling
from UCB import UCBdef plot_results(solvers, solver_names):"""輸出解決方法的累積懊悔變化圖"""for idx, solver in enumerate(solvers):time_list = range(len(solver.regrets))plt.plot(time_list, solver.regrets, label=solver_names[idx])plt.xlabel('Time Step')plt.ylabel('Cumulative regrets')plt.title('%d-arm bandit' % solvers[0].bandit.K)plt.legend()plt.show()def apply_epsilon_greedy_1():np.random.seed(1)epsilon_greedy_solver = EpsilonGreedy(bandit, epsilon=0.01)epsilon_greedy_solver.run(5000)print('epsilon-貪婪算法的累積懊悔為：', epsilon_greedy_solver.regret)plot_results([epsilon_greedy_solver], ["EpsilonGreedy"])def apply_epsilon_greedy_2():np.random.seed(1)epsilons = [1e-4, 0.01, 0.1, 0.25, 0.5]epsilon_greedy_solver_list = [EpsilonGreedy(bandit, epsilon=e) for e in epsilons]epsilon_greedy_solver_names = ['epsilon={}'.format(e) for e in epsilons]for epsilon_greedy_solver in epsilon_greedy_solver_list:epsilon_greedy_solver.run(50000)plot_results(epsilon_greedy_solver_list, epsilon_greedy_solver_names)def apply_decaying_epsilon_greedy():np.random.seed(1)decaying_epsilon_greedy_solver = DecayingEpsilonGreedy(bandit)decaying_epsilon_greedy_solver.run(50000)print('epsilon 反比衰減的貪婪算法的累積懊悔為：', decaying_epsilon_greedy_solver.regret)plot_results([decaying_epsilon_greedy_solver], ["DecayingEpsilonGreedy"])def apply_UCB():np.random.seed(1)c = 1  # 不確定性比重UCB_solver = UCB(bandit, c)UCB_solver.run(5000)print('上置信界算法累積懊悔為：', UCB_solver.regret)plot_results([UCB_solver], ["UCB"])def apply_thompson_sampling():np.random.seed(1)thompson_sampling_solver = ThompsonSampling(bandit)thompson_sampling_solver.run(5000)print('湯普森采樣算法累積懊悔為：', thompson_sampling_solver.regret)plot_results([thompson_sampling_solver], ["ThompsonSampling"])apply_thompson_sampling()

運行 Main.py 文件，結果如下：

D:\RL\MAB\.venv\Scripts\python.exe D:\RL\MAB\Main.py 
隨機生成了一個 10 臂的伯努利多臂老虎機
獲獎概率最大的拉桿為 1 號，其獲獎概率為 0.7203
湯普森采樣算法累積懊悔為： 57.19161964443925進程已結束，退出代碼為 0

2.4 小結

算法	累積懊悔與時間步的關系
ε-貪婪算法	線性
ε-衰減貪婪算法	次線性（對數）
上置信界算法	次線性（對數）
湯普森采樣算法	次線性（對數）