强化学习的第一天

动手学习强化学习

强化学习这门课程要求写一个AI进行五子棋，我找了个Alpha zero的算法
但我其实并不太明白的

所以说我又找了一下深度强化学习的资料，看到一篇知乎里的评论给了很多很多的学习资料

然后我就选择其中一本动手学习深度学习这本书，感觉是和dive into deep learning是差不多的类型

等我花一周时间拿下这本书

多臂老虎机

多臂老虎机是相当简化的强化学习问题（但我觉得其实也可以非常复杂），里面只有动作和价值。
问题主题就是有K个老虎机，你摆动其中的摇杆，然后获得奖励，问题核心在于如何动作获得最大的价值，
在一定时间步内的动作要想获取最大价值，就需要每次动作都要在最能（概率最大的）获得更多奖励的老虎机上扳动摇杆
然后我们先初始化一下老虎机

class BernoulliBandit:
    def __init__(self, k) -> None:
        self.K = k
        """初始化K个老虎机，每个老虎机的获奖概率不同"""
        self.probs = np.random.uniform(size=k)
        self.best_prob_idx = np.argmax(self.probs)
        self.best_prob = self.probs[self.best_prob_idx]

    def step(self, k):
        """
        选择第K个摇杆
        """
        return 1 if np.random.rand() < self.probs[k] else 0

下面有三个算法，是在一次动作中做不同的决策，因此搭建一个总体框架

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)
            
    """为什么会有这个函数是因为我在jupyter中实验因为没有对每个算法进行初始化，导致不同算法间的迭代次数不一样不能绘图"""
    def reset(self):
        self.counts = np.zeros(self.bandit.K)
        self.regret = 0.
        self.actions = []
        self.regrets = []

ϵ-贪心算法

这个算法的核心就是每次决策过程中，以1-ε的概率选择已知期望最优的老虎机，以ε的概率随机选取
所以要多维护一个期望

class EpsilonGreedy(Solver):
    """ epsilon贪婪算法,继承Solver类 """
    """注意这里的init_prob要等与1.0不能等于1，不然之后的后悔值全是线性的，我也不知道为什么"""
    def __init__(self, bandit, epsilon=0.01, init_prob=1.0):
        super(EpsilonGreedy, self).__init__(bandit)
        self.epsilon = epsilon
        self.init_prob = init_prob
        #初始化拉动所有拉杆的期望奖励估值
        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)  # 得到本次动作的奖励
        """期望的迭代更新，公式 E = E + 1/N(reward - E)"""
        self.estimates[k] += 1. / (self.counts[k] + 1) * (r - self.estimates[k])
        return k

    def reset(self):
            super().reset()
            self.estimates = np.array([self.init_prob] * self.bandit.K)

这个算法ε越小最后累计的后悔值越小，因为ε越小的话算符自主探索的可能性就更小，每一次迭代都会最大可能地选取期望最高的老虎机
但是我感觉ε太小了可能会导致算法一直找不到最优的老虎机。
因此有了下面的递减ε算法，ε赋值为时间步的倒数，这样就会在开始时候让算法自由探索，再在一定时间步后尽可能地选取期望最高的老虎机，
这个方法也是这一节中后悔值后期累计最小最不容易变的

class DecayEpsilonGreedy(Solver):
    """ decay epsilon贪婪算法,继承Solver类,这里的epsilon变成时间的倒数 """
    def __init__(self, bandit, init_prob=1.0):
        super(DecayEpsilonGreedy, self).__init__(bandit)
        #初始化拉动所有拉杆的期望奖励估值
        self.time_count = 0
        self.init_prob = init_prob
        self.estimates = np.array([init_prob] * self.bandit.K)

    def run_one_step(self):
        self.time_count += 1
        if np.random.random() < 1/self.time_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

    def reset(self):
        super().reset()
        self.time_count = 0
        self.estimates = np.array([self.init_prob] * self.bandit.K)

上置信界算法

这个算法后悔值叠加的是最大的，它的依据来自于霍夫丁不等式
X1…..Xn属于[0,1]，那么P{E[X] >= x_n + u } < e^(-2nu^2), 其中x_n是x的n个采样均值，u是不确定度。
我们取等式右边为概率p，Q(a)为期望，那么我们就可以知道P{Q(a) < Q`(a) + u}>1-p,
此时如果p非常小，那么就有趋近于1的概率我们能取到动作价值的上界
但我们仍然不知道不确定度是多少，我们又希望p能随着算法的进行越来越小，那么我们就让p=1/t
然后再依据p=e^(-2nu^2)计算出不确定度，这个就是我们要找的上界，每次迭代过程中选择上界最大的那个动作

class UCB(Solver):
    def __init__(self, bandit, coef=1., init_prob=1.0):
        super(UCB, self).__init__(bandit)
        self.estimates = np.array([init_prob] * bandit.K)
        self.coef = coef
        self.total_count = 0
        self.init_prob = init_prob
    
    def run_one_step(self):
        self.total_count += 1
        upper_bouds = self.estimates + self.coef*np.sqrt(np.log(self.total_count)/(2*(self.counts + 1)))
        k = np.argmax(upper_bouds)
        reward = self.bandit.step(k)
        self.estimates[k] += 1./(self.counts[k] + 1) * (reward - self.estimates[k])
        return k
        
    def reset(self):
        super().reset()
        self.total_count = 0
        self.estimates = np.array([self.init_prob] * self.bandit.K)

汤普森采样算法

这里面有个beta分布我其实没有太搞懂，不过看代码就能知道个大概
这个算法的思路就是每次在参数为（每个老虎机获得奖励的次数，每个老虎机没获得奖励的次数）的beta分布中采样
选取值最大的那个为idx作为动作
后续有个画图我们可以看到随着算法的进行，能更高概率获得奖励的老虎机第一个参数越来越大，被采样的可能性也被提高，而那些很难获得奖励的则可能性被降低了。

class TompsonSampling(Solver):
    def __init__(self, bandit):
        super(TompsonSampling, self).__init__(bandit)
        self._a = np.ones(self.bandit.K)  # 列表,表示每根拉杆奖励为1的次数
        self._b = np.ones(self.bandit.K)
        self.probs = []
    
    def run_one_step(self):
        samples = np.random.beta(self._a, self._b)
        self.probs.append(samples)
        k = np.argmax(samples)
        reward = self.bandit.step(k)
        self._a[k] += reward
        self._b[k] += 1. - reward
        return k
    
    def reset(self):
        super().reset()
        self._a = np.ones(self.bandit.K)
        self._b = np.ones(self.bandit.K)
        self.probs = []

后续一定要了解一下beta分布到底是什么东西

然后是一些utils

def plot_result(solvers, solver_names):
    for idx, solver in enumerate(solvers):
        time_list = range(len(solvers[0].regrets))
        plt.plot(time_list, solver.regrets, label=solver_names[idx])
    plt.xlabel("time step")
    plt.ylabel("cumulate regrets")
    plt.title(f"{solvers[0].bandit.K}-arms")
    plt.legend()
    plt.show()

def run_all(solvers, solver_names, random_seed=1, T=5000):
    np.random.seed(random_seed)
    for s in solvers:
        s.reset()
        s.run(T)
    plot_result(solvers, solver_names)

solvers = [
    EpsilonGreedy(bandit),
    DecayEpsilonGreedy(bandit),
    UCB(bandit)
]

solver_names = [
    "eps_bandit",
    "dc_eps_bandit",
    "ucb_bandit"
]

run_all(solvers, solver_names, random_seed=42, T=5000)

todo

• 看完动手学习深度学习
• 看alpha zero的论文
• 实现alpha zero五子棋对弈（自我对弈）