Chapter 2 multi-armed Bandit

2024-09-03 03:18
文章标签 multi chapter bandit armed

本文主要是介绍Chapter 2 multi-armed Bandit,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  引用:https://blog.csdn.net/mmc2015/article/details/51247677

https://blog.csdn.net/coffee_cream/article/details/58034628

https://blog.csdn.net/heyc861221/article/details/80129310

 

The most important feature distinguishing reinforcement learning from other types of learning is that it uses training information that evaluates the actions taken rather than instructs by giving correctactions. This is what creates the need for active exploration, for an explicit search for good behavior。

描述

假设有个老虎机并排放在我们面前,我们首先给它们编号,每一轮,我们可以选择一个老虎机来按,同时记录老虎机给出的奖励. 假设各个老虎机不是完全相同的,经过多轮操作后,我们可以勘探出各个老虎机的部分统计信息,然后选择那个看起来奖励最高的老虎机. 在多臂赌博机中,我们把老虎机称为臂.

随机式(stochastic bandit): 臂的奖励服从某种固定的概率分布

Multi-armed bandit原本是从赌场中的多臂老虎机的场景中提取出来的数学模型,其中 arm 指的是老虎机(slot machine)的拉杆,bandit 是多个拉杆的集合,bandit=arm1,arm2,……,armk。每个 bandit setting 对应一个回报函数(reward function),现在需要经过多次的尝试,来评估每个 bandit 的reward,这个问题的目标是如何最大化总的回报。
  显然,在这个问题中一共包含 k 个 actions,每个 action 都有一个期望的或者平均的 reward,称为是这个action的 value。记时间 t 选择的行为为At,其相对应的reward为Rt,任意一个行为a的value记为 q∗(a),因此,a

期望的 reward 为:

q∗(a)=E[Rt|At=a]


  显然,如果我们知道了每个 action 的 value,只有每次选择具有最大 value 的 action 就可以解决这个问题,这里令action a在时间 t 的估计 value 为 Qt(a)≈q∗(a)。
  如果在实验中,在当前时刻评估的value值最大的action就称为是greedy actions,如果在下个时刻选择的是 greedy actions,那么这次选择就可以视为是 exploiting 当前已有的信息,相反如果在下个时刻选择的是 non-greedy actions,那么这次选择就可以视为是 exploring。下面将会介绍几种平衡 exploit 和 explore 的方法。

2、Action-Value Methods

  对一个行为 a

,最简单的评估方法就是用行为a

所返回的所有rewards进行平均,即:

Q∗(a)≐sum of rewards when a taken prior to tnumber of times a taken prior to t=∑t−1i=1Ri⋅lAi=a∑t−1i=1lAi=a


其中,

lpredicate={1,0,predicate is trueotherwise


  若分母为0则令Q∗(a)为一个默认的值。根据大数理论,当分母趋于无穷时,则 Qt(a) 趋近于 q∗(a),我们将这种估计action values的方法称为是 sample−average 方法。
  最简单的策略就是每个时间t都选择当前的greedy actions,这种方法称为是greedy action selection method,该方法的选择策略可以记为是:

At≐argmaxaQt(a)


  可以看出,greedy action selection 每次都只会对当前的信息进行开发,而不会探索新的信息,对这种方法最简单的改进方式就是引入一个小的变量 ε,每次选择actions时,以 1−ε 的概率选择 greedy acitons,以 ε 的概率从所有actions中以相等的概率随机选择,这种方法称为是 ε−greedy method,这种方法的优点在于在无限的时间下所有的 actions 都有机会被选择过,因此所有的 Qt(a) 都会趋近于 q∗(a) 。

 

3、Incremental Implementation(增量式实现)

  上一节介绍的方法是将所有的历史信息全部记录下来然后求平均,不仅耗费内存也浪费时间,这一节介绍的增量式的方法仅耗费固定大小的内存,并且每个时间都可以进行更新。
  为了简化符合,这里只关注一个action,令 Ri

代表第i次选择这个 action 获得的 reward,Qn 代表这个action被选择了 n−1

次之后评估的 value 值,则有下面的等式成立:


 

  上式中最后的更新规则可以写作是:

NewEstimate←OldEstimate+StepSize [Target–OldEstimate]


  其中,表达式 [Target–OldEstimate] 是估计中的 error 项,可以看出在增量式学习方法中的 StepSize项为 1/n,是随时间不断变化的,之后会用 α 或 αt(a) 来代表 step-size 参数。
  算法的伪代码为:

 


 

4、针对非固定的问题

  之前考虑的都是一个不变的环境,但如果bandit随时间不断变化该如何处理呢?这时有必要将当前的rewards赋予更高的权重,而过去的赋予较小的权重,最常用的实现方法就是使用一个固定的step-size参数,例如将上一节中的更新规则改为:

Qn+1≐Qn+α[Rn−Qn]


  其中,α∈(0,1] 是个常数。对该式进行分解就会得到

 


 

  因为 (1−α)n+∑ni=1α(1−α)n−i=1

, 因此可以将上式视为是一种加权平均。由于 1−α<1,因此 i 越大赋予 Ri 的权重越大。通常将这种更新方式称作是 exponential, recency−weighted average

5、优化的初始值

  前面介绍的几种方法都与初始的action-value的评估值 Q1(a)

有关,在统计学方面这称为是“有偏的(biased)”。对于 sample-average 方法,这种 bias 在所有的 actions 都被最少选择过一次之后会消失;而对于具有常量 α 的方法,这种 bias 是一直存在的。但是这种 bias 也不常常是有坏处的,也可以被利用起来,例如我们考虑 10-armed testbed 的问题,如果所有的初始值全部设为 0,第一个被随机选择的action只要回报不是0一定会成为其中的 greedy action,但如果所有的初始值全部设为5,若初始选择的action的回报小于5

则它的估计值就会降低,从而促进算法进行explore的过程。

6、Upper-Confidence-Bound Action Selection

UCB算法全称是Upper Confidence Bound(置信区间上界),它的算法步骤如下[4]:

  • 初始化:先对每一个臂都试一遍;
  • 按照如下公式计算每个臂的分数,然后选择分数最大的臂作为选择:

图片描述

图3 UCB算法

  • 观察选择结果,更新t和Tjt。其中加号前面是这个臂到目前的收益均值,后面的叫做bonus,本质上是均值的标准差,t是目前的试验次数,Tjt是这个臂被试次数。

这个公式反映一个特点:均值越大,标准差越小,被选中的概率会越来越大,同时哪些被选次数较少的臂也会得到试验机会。

  在action选择过程中,greedy actions是当前认为最优的行为,但是最优的行为可能并非是它们,因此就需要exploration过程,ε

-greedy action selection强制使non-greedy的行为也有机会被选择,但这并不是最优的exploration方式,最好的方式应该是将每个action的评估值和不确定性值均考虑在内,这种有效的选择规则为:

At≐argmaxa[Qt(a)+clogtNt(a)−−−−−√]


  其中 log 指的是自然对数,Nt(a) 指的是行为a在时间t已经被选择的次数,常数 c>0 代表的是赋予exploration的权重。
  这种选择方式称为是upper confidence bound (UCB) action selection,选择函数中的平方根项代表了对行为 a 的不确定性,分子中对时间t取自然对数是为了使分子的增长速度减慢。

Softmax 函数的特点和作用

----------

因为这里不太方便编辑公式,所以很多公式推导的细节都已经略去了,如果对相关数学表述感兴趣的话,请戳这里的链接Softmax的理解与应用 - superCally的专栏 - 博客频道 - http://CSDN.NET

----------


 

Softmax在机器学习中有非常广泛的应用,但是刚刚接触机器学习的人可能对Softmax的特点以及好处并不理解,其实你了解了以后就会发现,Softmax计算简单,效果显著,非常好用。

我们先来直观看一下,Softmax究竟是什么意思

我们知道max,假如说我有两个数,a和b,并且a>b,如果取max,那么就直接取a,没有第二种可能

但有的时候我不想这样,因为这样会造成分值小的那个饥饿。所以我希望分值大的那一项经常取到,分值小的那一项也偶尔可以取到,那么我用softmax就可以了 现在还是a和b,a>b,如果我们取按照softmax来计算取a和b的概率,那a的softmax值大于b的,所以a会经常取到,而b也会偶尔取到,概率跟它们本来的大小有关。所以说不是max,而是 Soft max 那各自的概率究竟是多少呢,我们下面就来具体看一下

定义

假设我们有一个数组,V,Vi表示V中的第i个元素,那么这个元素的Softmax值就是

S_i = \frac{e^{V_i}}{\sum_j{e^{V_j}}}

也就是说,是该元素的指数,与所有元素指数和的比值

这个定义可以说非常的直观,当然除了直观朴素好理解以外,它还有更多的优点

 

这篇关于Chapter 2 multi-armed Bandit的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1131873

相关文章

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

Chapter 13 普通组件的注册使用

欢迎大家订阅【Vue2+Vue3】入门到实践 专栏,开启你的 Vue 学习之旅! 文章目录 前言一、组件创建二、局部注册三、全局注册 前言 在 Vue.js 中,组件是构建应用程序的基本单元。本章详细讲解了注册和使用 Vue 的普通组件的两种方式:局部注册和全局注册。 本篇文章参考黑马程序员 一、组件创建 ①定义 Vue 组件是一种具有特定功能的 Vue 实

Chapter 10 Stability and Frequency Compensation

Chapter 10 Stability and Frequency Compensation Chapter 8介绍了负反馈, 这一章介绍稳定性, 如果设计不好, 负反馈系统是要发生震荡的. 首先我们学习理解稳定判断标准和条件, 然后学习频率补偿, 介绍适用于不同运放的补偿方式, 同时介绍不同补偿对两级运放slew rate的影响, 最后介绍Nyquist’s判断标准 10.1 Gener

【硬刚ES】ES基础(二十一) 单字符串多字段查询:Multi Match

本文是对《【硬刚大数据之学习路线篇】从零到大数据专家的学习指南(全面升级版)》的ES部分补充。

2015 Multi-University Training Contest 5 1009 MZL#39;s Border

MZL's Border  Problem's Link:  http://acm.hdu.edu.cn/showproblem.php?pid=5351   Mean:  给出一个类似斐波那契数列的字符串序列,要你求给出的f[n]字符串中截取前m位的字符串s中s[1...i] = s[s.size()-i+1....s.size()]的最大长度。 analyse:   过计算

Segmentation简记-Multi-stream CNN based Video Semantic Segmentation for Automated Driving

创新点 1.RFCN & MSFCN 总结 网络结构如图所示。输入视频得到图像分割结果。 简单粗暴

[学习笔记]《CSAPP》深入理解计算机系统 - Chapter 3 程序的机器级表示

总结一些第三章的一些关键信息 Chapter 3 程序的机器级表示结构 updating... Chapter 3 程序的机器级表示 局部变量通常保存在寄存器中,而不是内存中,访问寄存器比内存快的多. 有些时候,局部数据必须存放在内存中, 寄存器不足够存放所有的本地数据对一个局部变量使用地址运算符 &, 因此必须能够为它产生一个地址某些局部变量是数组或结构,因此必须能够通过数组或