预备知识：

监督学习和强化学习的区别:

数据的稳定性，监督学习数据稳定不变，强化学习数据从外界获得一直在变

基础篇

多臂老虎机（MAB问题--multi-armed bandit）

实例问题：

拥有 K根拉杆的老虎机，拉动每一根拉杆都对应一个关于奖励的R 。我们每次拉动其中一根拉杆，就可以从该拉杆对应的奖励概率分布中获得一个奖励r 。目标：奖励最多

数学化描述：

（A,R）：动作集合和奖励概率分布；     目标：最大化一段时间步内的累计奖励：

误差：    ，Q是期望值和实际值

转化目标;最小化累积误差

问题解决方法：

核心：找到每根拉杆的概率分布，进一步的估计每根拉杆的期望奖励（估计方法：增量式估计）

代码：

第一部分：生成老虎机

import numpy as np
import matplotlib.pyplot as plt

class Bernoullibandit:
    """伯努利老虎机，K表示拉杆个数"""
    def __init__(self,K):
        self.probs  = np.random.uniform(size=K) #K个数，作为“获奖概率使用”
        self.best_idx = np.argmax(self.probs)   #获奖概率最大的拉杆
        self.best_prob = self.probs[self.best_idx]  #最大的获奖概率
        self.K = K 
        
    def step(self,k):
        """根据概率返回奖励（1，0）"""
        if np.random.rand() < self.probs[k]:
            return 1
        else:
            return 0
np.random.seed(1)
K = 10
bandit_10_arm = Bernoullibandit(K)
print("随机生成了一个%d臂伯努利老虎机"%K)
print("获奖概率最大的拉杆为%d号，其获奖概率为%.4f"%(bandit_10_arm.best_idx,bandit_10_arm.best_prob))   
        

第二部分：解决方案(使用bandit实例对象,以及np.zero的使用,K是bandit的属性，相当于几根老虎机，k是Solver的属性，相当于本次动作选择的老虎机编号)

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)

现在位置基本的问题和代码框架已经有了，下一步就是完善Solver的run_one_step（）函数,也就是求出k----拉动哪根拉杆

问题转化-拉动哪根拉杆（策略）

根据增量式算法求均值，会涉及到探索和利用两个概念，探索：有限次数找到期望值，利用：利用上一步中最大的期望值进行继续继续实验，增量式算法有一个明显的缺点，期望值并不一定是准确的，所以我们现在将问题再次转化--探索最大化--平衡探索和利用

-贪心算法

对完全贪婪算法进行修改：

 第一种方法：探索次数增加,不变

增量式公式：

class EpsilonGreedy(Solver):
    """ epsilon贪婪算法,继承Solver类 """
    def __init__(self, bandit, epsilon=0.01, init_prob=1.0):
        super(EpsilonGreedy, self).__init__(bandit)  #继承构造函数
        self.epsilon = epsilon
        #初始化拉动所有拉杆的期望奖励估值----都为1
        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)  # 选择期望奖励估值最大的拉杆，参数0.01决定探索大小
        r = self.bandit.step(k)  # 得到本次动作的奖励
        #增量式公式
        self.estimates[k] += 1. / (self.counts[k] + 1) * (r - self.estimates[k])
        return k

def plot_results(solvers, solver_names):
    """生成累积懊悔随时间变化的图像。输入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 steps')
    plt.ylabel('Cumulative regrets')
    plt.title('%d-armed bandit' % solvers[0].bandit.K)
    plt.legend()
    plt.show()


np.random.seed(1)
epsilon_greedy_solver = EpsilonGreedy(bandit_10_arm, epsilon=0.01)
epsilon_greedy_solver.run(5000)
print('epsilon-贪婪算法的累积懊悔为：', epsilon_greedy_solver.regret)
plot_results([epsilon_greedy_solver], ["EpsilonGreedy"])

0.01时的结果

当参数变化：

np.random.seed(0)
epsilons = [1e-4, 0.01, 0.1, 0.25, 0.5]
epsilon_greedy_solver_list = [
    EpsilonGreedy(bandit_10_arm, epsilon=e) for e in epsilons
]
epsilon_greedy_solver_names = ["epsilon={}".format(e) for e in epsilons]
for solver in epsilon_greedy_solver_list:
    solver.run(5000)

plot_results(epsilon_greedy_solver_list, epsilon_greedy_solver_names)

可视化： 

 累计懊悔线性增长--每一次都与最佳值差一个误差--局部最优

第二种方法：探索次数增加,随时间变小，成反比

class DecayingEpsilonGreedy(Solver):
    """ epsilon值随时间衰减的epsilon-贪婪算法,继承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:  # 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


np.random.seed(1)
decaying_epsilon_greedy_solver = DecayingEpsilonGreedy(bandit_10_arm)
decaying_epsilon_greedy_solver.run(5000)
print('epsilon值衰减的贪婪算法的累积懊悔为：', decaying_epsilon_greedy_solver.regret)
plot_results([decaying_epsilon_greedy_solver], ["DecayingEpsilonGreedy"])

 非线性，并且累计懊悔趋向不变--达到最佳值

 上置信界算法

核心：引入不确定度量，随着单一动作的次数的增加而减小，也就是拉动杆少的继续拉

基于不确定性的策略算法--上置信界

原理：霍夫丁不等式

目的：选出期望值奖励上界最大的拉杆--选出最有可能获得最大期望奖励的拉杆

核心：计算置信上界

原理（可跳过）

公式：                                      

这个公式从左到右表示：

某个概率（均值>=（增量式算法确定的均值+不确定值） ）<= 这个上界

当p很小时，就很有机会成立，所以就是奖励上界最大的动作，不确定度量根据可以就解出来

再简单点（不可跳过）：

其中  Q是第 i 根拉杆的期望奖励估值（self.estimates）， c 是控制不确定性比重的系数（self.coef）， t是总的尝试次数（self.total_count）， n是第 i 根拉杆的尝试次数（self.counts[i]）。这样就可以输出置信上界

class UCB(Solver):
    """ UCB算法,继承Solver类 """
    def __init__(self, bandit, coef, init_prob=1.0):
        super(UCB, self).__init__(bandit)
        self.total_count = 0
        self.estimates = np.array([init_prob] * self.bandit.K)
        self.coef = coef

    def run_one_step(self):
        self.total_count += 1
        #这里的ucb是一个列表
        ucb = self.estimates + self.coef * 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


np.random.seed(1)
coef = 1  # 控制不确定性比重的系数
UCB_solver = UCB(bandit_10_arm, coef)
UCB_solver.run(5000)
print('上置信界算法的累积懊悔为：', UCB_solver.regret)
plot_results([UCB_solver], ["UCB"])

 汤普森采样算法 

思路：其实是蒙特卡洛方法（利用随机变量的概率分布和大数定律，用样本的统计特征来估计总体的特征），简述：根据每个动作a的奖励概率分布进行下一轮采样，根据样本计算出所有的杆的期望奖励，然后取最大的。

转化：怎样得到每个动作a的奖励概率分布并且更新。

解决：使用beta分布建模，具体：某个拉杆选择k次，次奖励1，次奖励0，则服从

（）的beta分布

class ThompsonSampling(Solver):
    """ 汤普森采样算法,继承Solver类 """
    def __init__(self, bandit):
        super(ThompsonSampling, self).__init__(bandit)
        #生成列表，初始次数都为1
        self._a = np.ones(self.bandit.K)  # 列表,表示每根拉杆奖励为1的次数
        self._b = np.ones(self.bandit.K)  # 列表,表示每根拉杆奖励为0的次数

    def run_one_step(self):
        samples = np.random.beta(self._a, self._b)  # 按照Beta分布采样一组奖励样本
        k = np.argmax(samples)  # 选出采样奖励最大的拉杆
        r = self.bandit.step(k)

        #更新次数列表
        self._a[k] += r  # 更新Beta分布的第一个参数
        self._b[k] += (1 - r)  # 更新Beta分布的第二个参数
        return k


np.random.seed(1)
thompson_sampling_solver = ThompsonSampling(bandit_10_arm)
thompson_sampling_solver.run(5000)
print('汤普森采样算法的累积懊悔为：', thompson_sampling_solver.regret)
plot_results([thompson_sampling_solver], ["ThompsonSampling"])

 结论：

 -贪婪算法的累积懊悔是随时间线性增长的，而另外 3 种算法（ -衰减贪婪算法、上置信界算法、汤普森采样算法）的累积懊悔都是随时间次线性增长的（具体为对数形式增长）。

入门了，开始强化学习，强化学习和老虎机相比，就是智能体与环境的交互并不会改变环境，也就是说老虎机的交互结果和以往的动作无关，所以老虎机就是无状态的强化学习。