2.1根据查阅资料，编写出MAB的 Softmax算法（或Epsilon-Greedy算法），BetaThompson sampling算法，UCB算法以及LinUCB算法。 2.2编写评估方法对（1）各算法的累积reward（2）各算法每轮的reward（3）各算法选取最优arm的概率变化情况（4）算法选取arm的方差情况进行可视化呈现。 2.3编写程序产生一个数据集，文件名为data.txt。本数据集为10000行110列的由数字组成的文本文件，第一列由1-10产生的随机整数，第二列由0-1组成的随机整数，第3列至110列由0-99产生的稀疏矩阵，0占80%。 2用该数据集进行对上述算法进行测试，计算出四种算法平均reward值，绘制单次模拟后每轮累计reward,测试轮数设置为1000.

2.1 MAB算法介绍：

1. Softmax算法

Softmax算法是基于概率选择的一种算法，每个动作的选择概率根据动作的潜在价值来确定。Softmax算法的公式如下：

$$ P(A_t=a) = \frac{e^{Q_t(a)/\tau}}{\sum_{i=1}^{k}e^{Q_t(i)/\tau}} $$

其中，$Q_t(a)$ 表示在时间 $t$ 选择动作 $a$ 的平均奖励，$\tau$ 为温度参数，控制选择概率的分布程度。$\tau$ 越大，选择概率越平均，$\tau$ 越小，选择概率越趋向于贪心。

2. Epsilon-Greedy算法

Epsilon-Greedy算法是一种简单的贪心算法，以 $\epsilon$ 的概率随机选择一个动作，以 $1-\epsilon$ 的概率选择当前平均奖励最高的动作。Epsilon-Greedy算法的公式如下：

$$ A_t=\begin{cases}argmax_aQ_t(a) & with \ probability\ 1-\epsilon \\ random\ action & with\ probability\ \epsilon\end{cases} $$

3. BetaThompson sampling算法

BetaThompson sampling算法是一种基于贝叶斯公式的概率选择算法，每个动作的选择概率由该动作的奖励分布的后验概率密度函数决定。BetaThompson sampling算法的公式如下：

$$ P(A_t=a) = \int_0^1 f(Q(a); \alpha, \beta) dQ(a) $$

其中，$f(Q(a); \alpha, \beta)$ 表示参数为 $\alpha$ 和 $\beta$ 的Beta分布的概率密度函数，$Q(a)$ 表示动作 $a$ 的奖励分布，$\alpha$ 和 $\beta$ 为Beta分布的参数。在每次选择动作后，更新 $\alpha$ 和 $\beta$ 的值。

4. UCB算法

UCB算法是一种基于置信区间的算法，动作的选择概率取决于当前动作的置信上限。UCB算法的公式如下：

$$ A_t=argmax_a(Q_t(a)+c\sqrt{\frac{ln(t)}{N_t(a)}}) $$

其中，$c$ 是一个常数，控制置信区间的大小，$N_t(a)$ 表示在时间 $t$ 之前选择动作 $a$ 的次数。

5. LinUCB算法

LinUCB算法是一种基于线性模型的算法，每个动作的价值由一个线性模型预测，同时使用置信上限来探索新的动作。LinUCB算法的公式如下：

$$ A_t=argmax_a(x_t(a)^T\theta_t + \alpha \sqrt{x_t(a)^T P_t x_t(a)}) $$

其中，$x_t(a)$ 是动作 $a$ 在时间 $t$ 的特征向量，$\theta_t$ 是线性模型的参数向量，$P_t$ 是协方差矩阵，$\alpha$ 是一个常数，控制置信区间的大小。在每次选择动作后，更新线性模型的参数和协方差矩阵的值。

2.2 评估方法介绍：

1. 各算法的累积reward

对每个算法进行多次模拟，记录每次模拟的累积奖励，求平均值。

2. 各算法每轮的reward

对每个算法进行多次模拟，记录每轮的奖励，求平均值。

3. 各算法选取最优arm的概率变化情况

对每个算法进行多次模拟，记录每轮选择最优动作的概率，绘制概率随时间的变化曲线。

4. 算法选取arm的方差情况进行可视化呈现

对每个算法进行多次模拟，记录每轮选择的动作，计算每个动作的选择次数，绘制每个动作的选择次数的方差图。

2.3 编写程序

以下是基于Python的MAB算法实现，包括数据集的生成和对算法的测试：