首页 > 编程语言 >强化学习——多臂老虎机问题（MAB）【附python代码】

强化学习——多臂老虎机问题（MAB）【附python代码】

时间：2024-07-17 16:27:10浏览次数：18  
标签：solver python epsilon self 多臂 bandit MAB greedy np

文章目录

一、问题描述

1.1 问题定义

  有一个用于 K 根拉杆的老虎机，每一根拉杆都对应一个关于奖励的概率分布 R 。每拉动一个拉杆，就可以从该拉杆的奖励概率分布中获得一个奖励 r 。在各拉杆的奖励概率分布未知的情况下，从头开始尝试，目标是在操作 T 次拉杆后获得尽可能高的累积奖励。

  由于奖励的概率分布是未知的，因此我们需要在“探索拉杆的获奖概率”和“根据经验选择获奖多的拉杆”中进行权衡。

【通俗易懂：有 K 个机器，你不知道每个机器的奖励概率分布，你只有 T 次机会选择机会，探索机器的奖励概率分布也算在 T 次内，然后尽可能获得最多的奖励。】

【示例：有 1 个 10 臂老虎机，你有 20 次选择机会，你可以花 10 次机会探索前 5 臂，根据获得的奖励，选择奖励期望最大的一个，剩下 10 次都选择最大的那 1 臂。（有可能奖励期望最大在没有探索的 5 臂中，也有可能在前 5 臂中，但是不是你选择的那个）】

1.2 形式化描述

  多臂老虎机问题可以表示为一个元组 < A ,    R > <A,\;R> <A,R>，其中：

  • A 为动作集合，其中一个动作表示拉动一根拉杆，若多臂老虎机有 K 个拉杆，则动作空间就是集合 { a 1 , a 2 , . . . , a K } \{a_1,a_2,...,a_K\} {a1​,a2​,...,aK​}，用 a t ∈ A a_t \in A at​∈A 表示任意一个动作；
  • R 为概率分布，拉动每一根拉杆的动作 a 都对应一个奖励概率分布 R ( r ∣ a ) R(r|a) R(r∣a)，拉动不同拉杆的奖励分布通常是不同。

  假设每个时间步只能拉动 1 根拉杆，多臂老虎机的目标为最大化一段时间步 T 内累积的奖励： m a x ∑ t = 1 T r t ,    r t ∼ R ( ⋅ ∣ a t ) max\sum^T_{t=1}r_t,\;r_t\sim R(\cdot|a_t) max∑t=1T​rt​,rt​∼R(⋅∣at​)。其中 a t a_t at​ 表示在第 t 时间步拉动某一拉杆的动作， r t r_t rt​ 表示动作 a t a_t at​ 获得的奖励。

1.3 累积懊悔

  对于每一个动作 a ，我们定义其期望奖励为 Q ( a ) = E r ∼ R ( ⋅ ∣ a ) [ r ] Q(a)=E_{r\sim R(\cdot | a)}[r] Q(a)=Er∼R(⋅∣a)​[r] 。于是，至少存在一根拉杆，它的期望奖励不小于任意一根拉杆，将该最优期望奖励表示为 Q ∗ = max ⁡ a ∈ A Q ( a ) Q^*=\max_{a\in A}Q(a) Q∗=maxa∈A​Q(a) 。

  • 懊悔：当前动作 a 与最优拉杆期望奖励的差距，即 R ( a ) = Q ∗ − Q ( a ) R(a)=Q^*-Q(a) R(a)=Q∗−Q(a)
  • 累积懊悔：操作 T 次拉杆后累积的懊悔总量，对于一次完整的 T 步决策 { a 1 , a 2 , . . . , a T } \{a_1,a_2,...,a_T\} {a1​,a2​,...,aT​} ，累积懊悔为： σ R = ∑ t = 1 T R ( a t ) \sigma_R=\sum^T_{t=1}R(a_t) σR​=∑t=1T​R(at​) 。

  所以求解 MAB 问题等价于最小化累积懊悔。

1.4 估计期望奖励

  为了知道拉动哪一根拉杆可以获得更高的奖励，所以我们需要估计这根拉杆的期望奖励。

算法流程：

对于 ∀ a ∈ A \forall a\in A ∀a∈A ，初始化计算器 N ( a ) = 0 N(a)=0 N(a)=0 和 期望奖励估值 Q ^ ( a ) = 0 \hat{Q}(a)=0 Q^​(a)=0
for t = 1 → T t=1 \rightarrow T t=1→T do
  选取某根拉杆，该动作记为 a t a_t at​
  得到奖励 r t r_t rt​
  更新计数器： N ( a t ) + = 1 N(a_t)+=1 N(at​)+=1
  更新期望奖励估值： Q ^ ( a t ) + = 1 N ( a t ) [ r t − Q ^ ( a t ) ] \hat{Q}(a_t)+=\frac{1}{N(a_t)}[r_t-\hat{Q}(a_t)] Q^​(at​)+=N(at​)1​[rt​−Q^​(at​)]

示例：

  编写一个拉杆为 10 的多臂老虎机。其中每个拉杆的奖励服从伯努利分布，即每次有 p 的概率获得奖励 1 ，有 1-p 的概率获得奖励 0 。【0 表示没有获奖，1 表示获奖。】

在 MAB 目录下新建 BernoulliBandit.py 文件
在这里插入图片描述
代码如下：

import numpy as np
import matplotlib.pyplot as plt


class 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=K

    def step(self, k):
        if np.random.rand() < self.probs[k]:
            return 1
        else:
            return 0


np.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 np


class Solver:
    """多臂老虎机解决方案抽象类"""

    def __init__(self, bandit):
        self.bandit = bandit
        self.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 NotImplementedError

    def run(self, num_steps):
        # 运行一定次数，num_steps为总运行次数
        for _ in range(num_steps):
            k = self.run_one_step()
            self.counts[k] += 1
            self.actions.append(k)
            self.update_regret(k)

配置 numpy 和 matplotlib 模块：

访问文章：配置 numpy 和 matplotlib 模块

二、解决方法

2.1 ϵ-贪婪算法

  完全贪婪算法就是在每一刻都采取期望奖励估值最大的动作，这就是纯粹的利用，没有探索。而 ε-贪婪算法则是在其基础上添加了噪声，每次以 1-ε 的概率选择以往经验中期望奖励估值最大的那根拉杆【利用】，以 ε 的概率随机选择一根拉杆【探索】，公式如下：

a t = { a r g    max ⁡ a ∈ A Q ^ ，采样概率： 1 − ϵ 从 A 中随机选择，采样概率： ϵ a_t= \left\{ \begin{array}{ll} arg\; \max\limits_{a\in A} \hat{Q}，采样概率：1-\epsilon \\ 从A中随机选择，采样概率：\epsilon \end{array} \right. at​={arga∈Amax​Q^​，采样概率：1−ϵ从A中随机选择，采样概率：ϵ​

  随着探索次数不断的增多，对各个动作的奖励估计越来越准确，所以没必要继续花费大力气进行探索。所以我们可以让 ε 随着时间衰减，但是不会到 0 。因为基于有限步观测的完全贪婪算法仍然是一个局部信息的贪婪算法，永远离最优解有一个固定的差距。

项目结构：

在这里插入图片描述

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

import numpy as np

from Solver import Solver


class EpsilonGreedy(Solver):
    def __init__(self,bandit,epsilon=0.01,init_prob=1.0):
        super(EpsilonGreedy,self).__init__(bandit)
        self.epsilon = epsilon
        self.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 plt

from BernoulliBandit import bandit
from EpsilonGreedy import EpsilonGreedy


def 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 plt

from BernoulliBandit import bandit
from EpsilonGreedy import EpsilonGreedy


def 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 = 1 t \epsilon_t=\frac1t ϵt​=t1​

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

import numpy as np

from Solver import Solver


class EpsilonGreedy(Solver):
    def __init__(self, bandit, epsilon=0.01, init_prob=1.0):
        super(EpsilonGreedy, self).__init__(bandit)
        self.epsilon = epsilon
        self.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


class 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 = 0

    def run_one_step(self):
        self.total_count += 1
        if 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 plt

from BernoulliBandit import bandit
from EpsilonGreedy import EpsilonGreedy, DecayingEpsilonGreedy


def 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 X_1,X_2,...,X_n X1​,X2​,...,Xn​ 为 n 个独立同分布的随机变量，取值范围为 [0,1] ，其经验期望为 x ˉ = 1 n ∑ j = 1 n X j \bar{x}=\frac1n\sum ^n_{j=1}X_j xˉ=n1​∑j=1n​Xj​ ，则有 P ( E [ X ] ≥ x ˉ + u ) ≤ e − 2 n u 2 P(E[X]\ge\bar{x}+u)\le e^{-2nu^2} P(E[X]≥xˉ+u)≤e−2nu2

  将霍夫丁不等式运用到多臂老虎机问题中。 Q ^ \hat{Q} Q^​ 代入 x ˉ \bar{x} xˉ，不等式中 u = U ^ ( a t ) u=\hat{U}(a_t) u=U^(at​) 代表不确定性度量。给定一个概率 p = e − 2 N ( a t ) U ( a t ) 2 p=e^{-2N(a_t)U(a_t)^2} p=e−2N(at​)U(at​)2 ，根据上述不等式， Q ( a t ) < Q ^ ( a t ) + U ^ ( a t ) Q(a_t)<\hat{Q}(a_t)+\hat{U}(a_t) Q(at​)<Q^​(at​)+U^(at​) 至少以概率 1 − p 1 - p 1−p 成立，当 p 很小时， Q ( a t ) < Q ^ ( a t ) + U ^ ( a t ) Q(a_t)<\hat{Q}(a_t)+\hat{U}(a_t) Q(at​)<Q^​(at​)+U^(at​) 就以很大概率成立，所以 Q ^ ( a t ) + U ^ ( a t ) \hat{Q}(a_t)+\hat{U}(a_t) Q^​(at​)+U^(at​) 就是期望奖励上界。

  根据 p = e − 2 N ( a t ) U ( a t ) 2 p=e^{-2N(a_t)U(a_t)^2} p=e−2N(at​)U(at​)2 得知 U ^ ( a t ) = − log ⁡ p 2 N ( a t ) \hat{U}(a_t)=\sqrt{\frac{-\log p}{2N(a_t)}} U^(at​)=2N(at​)−logp​ ​ ，其中 N ( a t ) N(a_t) N(at​) 是该拉杆的已经拉动的次数。确定概率 p 就可以计算 U ^ ( a t ) \hat{U}(a_t) U^(at​) 。

  在实际编程中，令 p = 1 t p=\frac1t p=t1​ ；令 U ^ ( a t ) = − log ⁡ p 2 ( N ( a t ) + 1 ) \hat{U}(a_t)=\sqrt{\frac{-\log p}{2(N(a_t)+1)}} U^(at​)=2(N(at​)+1)−logp​ ​ ，以免出现分母为 0 的情况；令 a t = a r g    m a x a ∈ A [ Q ^ ( a ) + c ⋅ U ^ ( a ) ] a_t=arg\;max_{a\in A}[\hat{Q}(a)+c\cdot\hat{U}(a)] at​=argmaxa∈A​[Q^​(a)+c⋅U^(a)] ，用系数 c 来控制不确定性比重。

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

import numpy as np

from Solver import Solver


class UCB(Solver):
    def __init__(self, bandit, c, init_prob=1.0):
        super(UCB, self).__init__(bandit)
        self.total_count = 0
        self.estimates = np.array([init_prob] * self.bandit.K)
        self.c = c

    def run_one_step(self):
        self.total_count += 1
        ucb = 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 plt

from BernoulliBandit import bandit
from EpsilonGreedy import EpsilonGreedy, DecayingEpsilonGreedy
from UCB import UCB


def 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 m_1 m1​ 次奖励为 1， m 2 m_2 m2​ 次奖励为 0，则该拉杆服从参数为 ( m 1 + 1 , m 2 + 1 ) (m_1+1,m_2+1) (m1​+1,m2​+1) Beta 分布。

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

import numpy as np

from Solver import Solver


class 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] += r
        self._b[k] += (1 - r)
        return k

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

import numpy as np
from matplotlib import pyplot as plt

from BernoulliBandit import bandit
from EpsilonGreedy import EpsilonGreedy, DecayingEpsilonGreedy
from ThompsonSampling import ThompsonSampling
from UCB import UCB


def 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 小结

算法累积懊悔与时间步的关系
ε-贪婪算法线性
ε-衰减贪婪算法次线性（对数）
上置信界算法次线性（对数）
汤普森采样算法次线性（对数）

标签：solver,python,epsilon,self,多臂,bandit,MAB,greedy,np
From： https://blog.csdn.net/yyh520025/article/details/140497612

相关文章

  • python基础语法
    一、python常用内置对象1、常量与变量常量即字面值无法改变的量，例如一个确定的数字、列表、字符串，如“Helloworld”就是一个典型的字符串常量，变量是指值可以发生改变的量，在python中，不仅变量的值可以任意变化，变量的值也可以随时发生改变。这是因为python变量并不直接存储值，而是......
  • 计算机毕业设计必看必学75435企业OA系统的设计与实现原创定制程序,java、PHP、python
    SSM企业OA系统摘 要在现今这个信息社会的高速发展的影响下，人们的衣食住行逐渐信息化。当各种当今时代的产物进入我们的生活中，我们要从容面对。在网络硬件与软件的完美结合下，我们的生活、工作将会事倍功半，往往工作中繁琐的事情会花费大量的人力物力，在相关的管理软件的运作......
  • python 操作mysql
    1.引入pymysql包importpymysql2.建立连接conn=pymysql.connect(host='********.com',user='lionmile',password='***********',database='lionmile')3.创建游标cursor=conn.cursor()4.执行sqlinsterS......
  • [附开题]flask框架web的酒店管理系统4yv4w（源码+论文+python）
    本系统（程序+源码+数据库+调试部署+开发环境）带论文文档1万字以上，文末可获取，系统界面在最后面。系统程序文件列表开题报告内容研究背景随着旅游业的蓬勃发展和商务活动的日益频繁，酒店行业迎来了前所未有的发展机遇与挑战。传统的人工管理模式已难以满足现代酒店对高效、精准......
  • [附开题]flask框架Web的汽车配件管理系统的设计与实现zt81o（源码+论文+python）
    本系统（程序+源码+数据库+调试部署+开发环境）带论文文档1万字以上，文末可获取，系统界面在最后面。系统程序文件列表开题报告内容研究背景随着汽车行业的快速发展，汽车配件市场日益繁荣，配件种类繁多，管理难度也随之增加。传统的手工管理模式已难以满足现代汽车配件企业的管理需求......
  • 使用Python编写webshell及防范措施
    本文使用python编写一个简单的webshell脚本，并讨论如何防范webshell。 文章目录前言一、pandas是什么？二、使用步骤1.引入库2.读入数据总结前言        在渗透测试和网络安全领域，Webshell是一种用于远程控制和管理受害服务器的工具。Webshell通常是一个脚......
  • 基于SSM的校园志愿者管理系统小程序+99213（免费领源码）可做计算机毕业设计JAVA、PHP、爬
    小程序+springboot校园志愿者管理系统摘 要随着我国经济迅速发展，人们对手机的需求越来越大，各种手机软件也都在被广泛应用，但是对于手机进行数据信息管理，对于手机的各种软件也是备受用户的喜爱，校园志愿者管理系统被用户普遍使用，为方便用户能够可以随时进行在线查看校园志愿......
  • IPython：提升Python编程效率的强大工具与技巧整理
    IPython：提升Python编程效率的强大工具与技巧整理IPython，作为一个增强的交互式Python解释器，自其诞生以来，就以其丰富的功能集和高效的工作流赢得了广大Python开发者的青睐。它不仅仅是一个简单的命令行界面，更是集成了代码补全、魔术命令、交互式调试、富文本展示、历史命令回......
  • 使用python输出长方形、三角形
    长方形i=0whilei<3:print('*'*4)i+=1运行结果：直角三角形i=0whilei<5:print('*'*(i+1))i+=1倒立直角三角形foriinrange(1,6):forjinrange(1,7-i):print('*',end='')print()##换行等腰三角形......
  • Python中常见的异常类型
    Python中常见的异常类型1、ZeroDivisionError-------除数为零2、IndexError------索引超出范围3、KeyError------字典取值时key不存在4、NameError------使用一个没有声明的变量时引发的异常5、SyntaxError------Python中的语法错误6、ValueError------传入的值错误7、A......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99