Reinforcement Learning:An Introduction Chapter 2 Multi-armed Bandits
文章目录
- Abstract
- 2.1 A k-armed Bandit Problem
- 2.2 Action-value Methods
- 2.3 The 10-armed Testbed
- 2.4 Incremental Implementation
- 2.5 Tracking a Nonstationary Problem
- 2.6 Optimistic Initial Values
- 2.7 Upper-Confidence-Bound Action Selection
- 2.8 Gradient Bandit Algorithms
- 2.9 Associative Search (Contextual Bandits)
- References
Abstract
强化学习使用训练信息来评估所采取的动作,而非使用正确的动作来指导动作的选择。评估性反馈完全依赖于所采取的动作,而指示性反馈独立于所采取的动作。本章讨论的是在单个状态下学习如何采取动作,即非关联性(nonassociative)。
2.1 A k-armed Bandit Problem
-
问题描述:
k-摇臂**机可以看做k个*,每个*的奖赏都是从某个固定的概率分布中采样得到的。每一时间步我们只能摇k个*中的一个,即为动作,所得奖赏为该*被选中后所得到的回报。在有限步内我们希望最大化期望累积奖励。 -
问题表示:
k个动作中的每一个动作都各自有其期望或平均的奖赏,我们称之为值。任一动作的记为,是被选择后的期望奖赏:
如果你知道了每个动作的值, 那么只要一直选择值最高的动作即可。现假设不能确定动作的值, 虽然可能有其估计值。 我们将动作 在时步t的估计值记为. 我们希望 尽可能接近。 -
问题难点:
该问题的难点即exploration和exploitation矛盾问题。每一时间步的时候都会有一个最大的,这个是greedy ,选择这个(exploitation)满足了我们最大化回报的目的,但是我们并不知道其他的会不会有更大的回报,选择其他的(exploration)可能会造成短期的回报减少,但当找到回报更大的时,我们的长期回报就会增加。
2.2 Action-value Methods
估计动作值的方法, 以及使用估计值来做出动作选择的决策的方法,两者合称为动作值方法。
-
样本平均方法
-
-贪心方法
在做选择时最简单的方法就是选最大的(greedy action)
而若希望算法能够有一定的探索的能力,则可以引入一个较小的概率,使得每一步中有概率会不选择贪心动作,二是从所有动作中随机进行选择。
2.3 The 10-armed Testbed
假设10个动作的真实值都是从均值为0方差为1的正态分布中采样得到的(如下图所示),且实际奖赏是从均值为方差为1的正态分布中采样得到的。
使用上述测试工具对贪心方法以及两个-贪心方法(=0.01及=0.1)进行对比,结果如下图所示。
可以看出贪心方法刚开始增长的最快,但在一个很低的水平就趋于平稳。=0.1的方法探索更多,能够更早地发现最优动作,但其不会以超过91%的概率选择这一动作。=0.01的方法增长缓慢,但最终效果回事最好的一个。因此我们实际上可以随时间逐步减小。
-贪心方法的优势视具体任务而定。如奖赏方差很大或存在噪声的情况下,智能体需要做更多次探索以发现最优动作,因此-贪心方法更具优势。另一方面,若奖赏方差为0,那么贪心方法试过一次后就知道所有动作的真实值,这种情况下贪心方法表现更好。
但即使是在确定性(deterministic)的情况下,探索也能很有优势。例如,假设k-armed bandit是非固定性的(nonstationary),动作的真实值会随着时间变化,这种情况下探索是必要的。因此,强化学习需要对探索与利用的平衡。
2.4 Incremental Implementation
如何使得样本平均值可以更有效的计算出来(常数的内存大小,每步一次计算):
(表示在选择了n-1次该动作后其奖赏的估计值)
变化为:
得到范式:
其中[Target - OldEstimate]是估计中的误差(error)。
一个简单的**机算法:
(函数 假定为以动作为参数, 返回相应奖赏的函数)
2.5 Tracking a Nonstationary Problem
当奖赏的概率分布会随时间变化时,即非固定性问题,相对于较早的奖赏, 将更多的权重给予较近的奖赏是很有意义的。比较好的解决方法是将步长(α)设为一个常数。
可证权重之和。从式子中我们可以看出由于,说明越早的reward的影响力在越小,这种方法也叫exponential recency-weighted average。
不是所有的 都确保能收敛。一个随机逼近理论(stochastic approximation theory)中的著名结论, 为我们提供了能以1的概率保证收敛的条件:
我们需要第一个条件来保证这些步长对“最终克服初始条件或随机波动的影响”而言足够大。第二个条件确保最终步长变得足够小以确保收敛。
当是常数的时候不满足后面的条件所以它是不收敛的。这样的步长是不稳定状态下所需要的。虽然满足上述收敛条件的步长参数序列常常用于理论研究中, 但极少用于实际应用或实证研究中。
两个非常重要的概念:non-deterministic和non-stationary
non-deterministic:action对应的value有一个分布,而不是一个确定的值(这个分布是不变化的);action的真值不变,但是是不确定的(理解不确定的最简单方法就是认为有一个分布)
non-stationary:action对应value的分布在不断变化,(如果action只对应一个值,那么这个值在不断变化);action的真值在不断变化(不管是分布变化还是单个值变化)
实际问题多是non-stationary并且non-deterministic。即使environment是stationary and deterministic,exploration也是很必要的,因为the learner faces a set of banditlike decision tasks each of which changes over time as learning proceeds and the agent’s policy changes。说白了就是,即使是完全确定的,也需要探索以便知道其它的action效果,否则怎么确定哪个最优?
2.6 Optimistic Initial Values
之前讨论的所有方法或多或少依赖于初始的动作值的估计值。这些方法因初始的估计值产生了偏差(bias)。对于样本平均方法来说,当所有的动作都被选择了一次后偏差就消失了;但对值恒定的方法来说,这一偏差会永远存在, 但会随时间逐步减小(见式2.6)。
初始动作值也可以以一种简单的鼓励探索的方式来使用。如在10-摇臂测试中,我们将初始估计值设为+5,则无论开始选择哪个动作,收到的奖赏都会低于初始估计值,所以所有的action都会被尝试。这种方法被称为optimistic initial values,这个方法在稳定的情况下比较有效。
2.7 Upper-Confidence-Bound Action Selection
如果选择的时候更偏向于有潜力成为最优的non-greedy actions会更好,将它们的估值与最大值的差距以及它们估值的不确定性都考虑进来。
其中表示的自然对数( 2.71828),表示在时间之前动作被选择的次数(2.2节中公式的分母),以及常数控制了探索的程度。如果,那么被认为是最优动作。
其中平方根项为a value的不确定性或者说是方差。这整个项便是action a可能最大值的上限,c决定了可信度。每次某个action被选择了,那么其不确定性就会降低。相反,当t增加,但是不变其不确定性就会增大。对数的应用则是随着时间的增加,其增长会变小,但是无限的。所有actions都会被选择到,但是随着时间的增加value小的action被选择到的频率就会更小。
2.8 Gradient Bandit Algorithms
在本节中,我们将考虑如何为每一个动作学得各自实数型的偏好,我们将其记为。偏好是相对的,对比之后才有意义。各动作被选择的概率由如下soft-max分布决定:
(表示在时间步采取动作的可能性)
在每次选择了action 之后的更新如下(梯度上升):
其中为步长参数,且,为时步及之前的所有奖赏的平均,可以如2.4节(如果问题是非固定性的话,那么如2.5节)中所述的那样进行增量式的计算。这一项是作为比较奖赏的基准线的。如果奖赏高于基准线,那么将来采取动作的概率增加,反之降低。而未被选择的动作的概率朝相反方向移动。
2.9 Associative Search (Contextual Bandits)
本节主要讨论结合不同的action到不同的场景中去的做法。
举个例子, 假如有数个不同的k-摇臂**机任务, 并且在每一步随机地遇到其中的某一个。因此在每一步**机任务都可能会变动。这看上去像一个简单的、非固定性的k-摇臂**机任务,只是其中真实的动作值在每一步都会随机发生变化。你可以尝试使用本章前面部分所述的、处理非固定性任务的方法,但除非真实的动作值变动得很缓慢,否则这些方法无法表现得好。现在假设,当某一个**机任务被选中时,你被给予了关于**机身份(而非动作值) 的区分线索。比如你面对着一个现实中的*,当其改变各个动作值时其外表的颜色也会发生变化。现在你可以学得一个策略,将由颜色标识的任务,同该任务下最佳的动作关联起来——例如,如果为红色,选择第1条摇臂;如果为绿色,选择第2条摇臂。在正确的策略下,这常常可以做得远比在缺失**机的辨别信息的条件时好。
References
[1] 强化学习导论(Reinforcement Learning: An Introduction)读书笔记(二):多臂**机(Multi-arm Bandits):https://blog.csdn.net/y954877035/article/details/54429630
[2] 《reinforcement learning:an introduction》第二章《Multi-arm Bandits》总结:https://blog.csdn.net/mmc2015/article/details/74936739
[3] https://github.com/KunBB/rl-cn