首页 > 其他分享 >强化学习 --K臂老虎机(2)

强化学习 --K臂老虎机(2)

时间:2024-07-07 16:55:18浏览次数:17  
标签:solver -- epsilon self bandit 算法 强化 老虎机 拉杆

3.1 前提

在前一节我们提出了一个强化学习经典问题“K臂老虎机”,并将这个问题数学形式化,并将求解“最大奖励概率分布”变换为求解“最小化累计懊悔”问题。之后又给出了K臂老虎机的环境生成问题,以及解决K臂老虎机算法的框架。在这节中,我们将会实现几个策略来解决K臂老虎机问题。

3.2 试探与开发(探索与利用)的平衡

还记得我们上一节提出的股票的例子吗?你购买5只股票,每月固定都能获得1W,但是这个月你想换一下其它股票。你可能会赚的更多,也可能会亏一些。那么我们就可以定义:你选择原有的几只股票获得固定收益的这一方式被称为开发或利用。而你试着去买其它股票的行为则被称为试探或探索

在第2节中,针对K臂老虎机,我们没有提出任何策略,所以在这一节,我们将会学习如何设计一个策略。最简单的策略,就是随机选择一个拉杆,但是这获得最大期望奖励的可能性太小了,所以并不合适。在多臂老虎机问题中,一个经典的问题就是探索和利用的平衡问题。在这个问题里面,探索指的是尝试拉动更多的拉杆,不一定每个拉杆都会获得最大的奖励,但是这种方式可以探索出所有拉杆的奖励情况。利用是指拉动已知期望奖励最大的那根拉杆,但是因为已知信息仅仅来自有限次的交互,所以当前的最优拉杆不一定是全局最优的。例如,对于一个 10 臂老虎机,我们只拉动过其中 3 根拉杆,接下来就一直拉动这 3 根拉杆中期望奖励最大的那根拉杆,但很有可能期望奖励最大的拉杆在剩下的 7 根当中,即使我们对 10 根拉杆各自都尝试了 20 次,发现 5 号拉杆的经验期望奖励是最高的,但仍然存在着微小的概率—另一根 6 号拉杆的真实期望奖励是比 5 号拉杆更高的。(为什么我们都尝试了20次,还会出现存在6号拉杆的真实期望奖励是比5号拉杆更高的情况呢,这是因为呢,我们尝试的次数可能不够多,所以其真实奖励期望是高于预估奖励期望的)

于是在多臂老虎机问题中,设计策略时就需要平衡探索和利用的次数,使得累积奖励最大化。一个比较常用的思路是在开始时做比较多的探索,在对每根拉杆都有比较准确的估计后,再进行利用。目前已有一些比较经典的算法来解决这个问题,例如\varepsilon-贪婪算法上置信界算法汤普森采样算法等,我们接下来将介绍\varepsilon-贪婪算法

3.3 \varepsilon-贪婪算法

完全贪婪算法:在每一时刻采取期望奖励估值最大的动作(拉动拉杆),这就完全没有探索,保守的一批。举个言简意赅的例子:闭眼看世界,闭门造车。

所以我们对完全贪婪算法进行了改进,其中经典的一种方法是\varepsilon -贪婪算法。每次以概率(1 - \varepsilon )选择以往经验中期望奖励估值最大的那根拉杆,以概率\varepsilon随机选择一个拉杆探索。这个公式如下:

随着时间进行,我们对各个动作的奖励估计的越来越准确,此时就不需要进行很大的探索,而在初期,因为对每个拉杆的奖励期望并不清楚,所以需要进行较多探索。所以我们可以设置\epsilon的值随着时间进行而逐渐减小。但并不会缩减到0.

PS:发现第二章代码BernoulliBandit类中存在一个错误,修改如下:

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

接下来编写一个\epsilon -探索算法,用其解决上一章的10臂老虎机问题,之前的代码在K臂赌博机(1)-CSDN博客。我们在这里设置\epsilon = 0.01 , T = 5000

# -*- coding: utf-8 -*-
"""
@File    : epsilon-Tansuo.py
@Author  : Administrator
@Time    : 2024-07-06 15:29
@IDE     : PyCharm
@Version :
@comment : ···
"""
import numpy as np
import matplotlib.pyplot as plt
from Solver import Solver
from BernoulliBandit import BernoulliBandit

class EpsilonGreedy(Solver):
    """ epsilon贪婪算法,继承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.counts[k] += 1
        self.estimates[k] += 1. / self.counts[k] * (r - self.estimates[k])
        self.regret += self.bandit.best_prob - r
        self.regrets.append(self.regret)
        return k

    def run(self, num_steps):
        for _ in range(num_steps):
            self.run_one_step()

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()

if __name__ == '__main__':
    np.random.seed(1)
    K = 10
    bandit_10_arm = BernoulliBandit(K)
    epsilon_greedy_solver = EpsilonGreedy(bandit_10_arm, epsilon=0.1)  # 增加 epsilon 值
    epsilon_greedy_solver.run(5000)
    print('epsilon-贪婪算法的累积懊悔为:', epsilon_greedy_solver.regret)
    plot_results([epsilon_greedy_solver], ["EpsilonGreedy"])

运行结果为:

epsilon-贪婪算法的累积懊悔为: 203.62246721078048

通过上面的实验可以发现,在经历了开始的一小段时间后,\epsilon-贪婪算法的累积懊悔几乎是线性增长的。这是  \epsilon = 0.01时的结果,因为一旦做出了随机拉杆的探索,那么产生的懊悔值是固定的。其他不同的 取值又会带来怎样的变化呢?我们继续使用该 10 臂老虎机,我们尝试不同的参数\{10^{-4}, 0.01, 0.1 0.25, 0.5}\},查看相应的实验结果

代码:

np.random.seed(0)
    K = 10
    bandit_10_arm = BernoulliBandit(K)
    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)

通过实验发现,无论\epsilon取值为多少,累计懊悔都是线性增长的,随着\epsilon的增大,累计懊悔增长的速率也会增大。接下来可以尝试一下\epsilon值随时间衰减的\epsilon-贪婪算法,公式为\epsilon_t = 1/t

代码如下:

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
        # epsilon随着时间减小
        epsilon = 1 / self.total_count
        if np.random.random() < 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)
    K = 10
    bandit_10_arm = BernoulliBandit(K)
    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"])

从实验结果图中可以发现,随时间做反比例衰减的\varepsilon -贪婪算法能够使累积懊悔与时间步的关系变成次线性(sublinear)的,这明显优于固定 \varepsilon值的\varepsilon -贪婪算法

标签:solver,--,epsilon,self,bandit,算法,强化,老虎机,拉杆
From: https://blog.csdn.net/qq_45481856/article/details/140228821

相关文章

  • P1093 [NOIP2007 普及组] 奖学金【排序】
    [NOIP2007普及组]奖学金题目背景NOIP2007普及组T1题目描述某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前555名学生发奖学金。期末,每个学生都......
  • Numerical Results of T3DFP-N1 and irT3DFP-N1
    ......
  • 7.7
    今天主要完成数据结构第二阶段的作业迷宫问题学习时间2小时代码时间1小时#include<stdio.h>#include<malloc.h>#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10//记录通道块在迷宫矩阵当中的横、纵坐标structPosition{intx;inty;};//放入栈当中的通道......
  • Django详细笔记
    django学习特点快速开发安全性高可伸缩性强URL组成部分URL:同意资源定位符一个URL由以下几部分组成scheme://host:port/path/?query-string=xxx#anchorscheme:代表的是访问的协议,一般为http或https协议host:主机名,域名port:端口http默认:80端口https默......
  • java 如何暴露header给前端
    在Java中,将HTTP响应的Header暴露给前端通常涉及在Web应用程序的服务器端代码中设置这些Header。这可以通过不同的JavaWeb框架来实现,比如SpringMVC、JAX-RS(Jersey)、Servlet等。这里,我将提供一个使用SpringMVC框架的示例,因为它在JavaWeb开发中非常流行且易于理解。1.示例:使用S......
  • WPF常见控件(包含materialDesign)与属性
    materialDesign:ColorZone:用于在应用界面中创建有色区域,增加层级感和视觉吸引力。materialDesign:DrawerHost:用于实现从屏幕一侧滑出的抽屉控件,经常与materialDesign:DrawerHost.LeftDrawerContent配套使用(这里的例子是设置左抽屉)。DockPanel:布局控件,用于将其子元素排列在特......
  • 网络通信系统的voronoi图显示与能耗分析matlab仿真
    1.程序功能描述       两层基站(BS)组成整个通讯网络,第1层为Macro基站记为,第2层为Micro基站记为,均服从泊松分布,相互独立,在坐标为10×10km的面积内、按照泊松分布随机生成若干个点(随机抛洒两遍nodes,两层叠加起来)。然后画成voronoi图:也就是在相邻两个点(同种......
  • 实战篇——文件包含漏洞一
    实战篇——文件包含漏洞(1)本地文件包含本地文件包含一般需要依赖文件上传漏洞。如果文件上传漏洞限制上传文件的后缀必须为.jpg,那么配合本地文件包含,就可以通过上传图片木马获得服务器权限。上传图片木马:利用本地文件包含,成功连接一句话木马:可见本地文件包含最大的缺陷在......
  • Nuxt框架中内置组件详解及使用指南(二)
    title:Nuxt框架中内置组件详解及使用指南(二)date:2024/7/7updated:2024/7/7author:cmdragonexcerpt:摘要:“本文详细介绍了Nuxt3中和组件的使用方法,包括组件的基本概念、属性、自定义属性、获取引用以及完整示例,展示了如何在Nuxt项目中有效利用这两个组件。categories......
  • 关于虚拟机的使用
    1、从网上下载了Centos7  2024年CentOS镜像下载地址,包括CentOS官网、国内镜像下载,超详细教学,小白也能学会。-CSDN博客2、通过VMware添加了该iso文件,打开虚拟机之后安装该系统就可以了3、进入之后我们需要进行软件安装、安装位置、KDUMP、网络和主机名的修改操作其中,为了......