说明:来自李飞飞教授博士范麟熙个人公众号:心有麟熙

背景介绍

Riding bike

  • trial and error:试错法
  • reward:可以使正的奖励或负的惩罚

使用 trial and error 不断尝试,在每一次尝试中总结经验,然后再提高下一次的 reward,这就是强化学习的精髓

源头

  • 1948 Alan Turing 提出 pleasure-pain system 的概念,如果一个系统能够把 pleasure 最大化,把 pain 最小化,就相当于从经验中不断 “学习”。
  • 1952 Claude Shannon 设计了一个机械装置:Shannon Maze-runner,实现了最基本的强化学习算法,老鼠根据试错法自己走出迷宫。Claude Shannon 1948 年的论文 Mathematical Theory of communication 创立现代信息学理论,1937 年 21 岁,MIT 硕士论文奠定了电路设计的基础。
  • 1961 Marvin Minsky 论文《走向人工智能之路》,提到了 trial and error 这种学习方式,以及一个新概念 “credit assignment”:同时存在的因素,最终起作用的是哪个?这是强化学习的核心问题之一。
  • Arthur Samuel,IBM 研究员,在 IBM 设计了一台能下跳棋的电脑:TD Learning,是强化学习的重要算法。此人创造了 MachineLearning 这个词组。

在动物界的灵感

RL: Prediction

  • Classical Conditioning
    • Pavlov's dog
    • 在强化学习里,经典条件反射,对应的就是 Prediction(预测)。当你看到一个信号(比如铃铛)时,你会预测将获得怎样的奖励,然后再根据这个预测来采取行动。当然,经典条件反射是一个相对被动的过程。
  • Law of Effect
    • Thorndike 提出了Law of Effect(效果律),维基百科上的定义是,在一个特定的情景下可以得到满意的效果的反应,在该情景下重复出现的概率会上升,而得到不满意的效果的反应重复出现的概率则会下降。
    • Thorndike's Cat:Thorndike设 计了一个装置。在这个笼子里,如果猫按了踩板,那么笼子的门就会打开。实验发现,开始时,猫咪会在笼子里不停地打转,一点头绪都没有,但是偶尔会随机地踏到踩板,然后笼子就打开了。之后第二次,猫咪再被放到笼子里时,它就会直接去踏踩板,而不会再像无头苍蝇一样浪费时间。

RL: Control

  • Operant Conditioning
    • 如果说巴普洛夫的狗是一种非自愿的条件反射,那么上述 Thorndike 的猫就是一种自愿的条件反射。这种自愿的行为,在后来被心理学巨匠B. F. Skinner 总结为 Operant Conditioning(操控反射)。
    • Skinner Box:在研究操控反射时,Skinner 设计了一个动物实验装置 ── Skinner Box。在这个盒子里,设有一只老鼠,和一个它能够操控的装置。如果按下杠杆,就会有食物从管中掉落;亦或是在另一种实验中,如果小鼠按下杠杆,盒子就会发出很大响声让小鼠受到惊吓。Skinner 就用这样一种装置来研究动物行为,和动物与环境的交互,即获得奖励(食物)或是惩罚(响声)。Skinner 观察到,当获得奖励时,小鼠会非常频繁地按动杠杆;而当获得惩罚时,小鼠则会尽力避免触动杠杆。
    • 在强化学习的语言里,Skinner 的 Operant Conditioning(操控反射)对应的概念是 Control,即能够根据对环境的认识,来操控环境,从而使对自己的奖励最大化。

Model-free VS Model-based

  • Model-free RL
    Trial & Error(试错法)是强化学习的核心思想,但它并不是唯一的思想。Trial & Error 及其对应的一套算法,称为Model-free Reinforcement Learning,即没有模型的强化学习。这可认为是,人们在不断试错的过程中,养成的一种习惯。
  • Model-based RL
    这种强化学习涉及到 Planning(规划):正因为脑海中有了环境模型,所以在第二次行动时就不需要东奔西跑,可以直接根据地图来做详细的规划。
  • 可以用1929年美国心理学家做的小鼠实验来概括。在这个实验中有两组老鼠:
    • 第一组老鼠被置于迷宫里,迷宫中央设有食物。小鼠会顺着气味行动,最后取得食物,假设这组老鼠获得食物花了10分钟。这就是我们说的Trial & Error,通过不断试错(在迷宫中走到死路就往另外一边走)来达成目的。
    • 第二组老鼠,一开始时被放置在同样的迷宫里,但这个迷宫中央并没有食物,也就是说,这个环境中并无任何奖励,小鼠在迷宫中完全是想怎么打转就怎么打转。这一阶段并不存在Trial & Error,因为小鼠没有试图去获得某种奖励。实验人员发现,如果紧接着把这组小鼠放在相同的但是有食物的迷宫里,那么这些小鼠就能够在短短 3 分钟内就找到食物。这个实验结果表明,虽然在第一阶段没有任何奖励机制,但是小鼠脑子里已经建立起了一个 “环境模型” ── Cognitive Map,也就是这个迷宫的地图。接着在第二阶段中设置了奖励时,小老鼠就能利用它们存在脑海里的地图,快速地找到食物。

应用介绍

RL in Games

  • IBM 研究员 Arthur Samuel,是世界上第一个把强化学习应用在一个主流的棋盘(跳棋)游戏上的人。
  • 在 1989 年到 2007 年之间,加拿大阿尔伯坦大学的团队,做了一个跳棋的人工智能 —— Chinook,在真正意义上破解了跳棋。
  • IBM 的研究员 Gerald Tesauro,他最著名的成就,就是写了一个能够超越人类 Backgammon 世界冠军的人工智能。Backgammon 是一个有一定随机性的掷骰子的概率游戏。Tesauro 的引擎叫做 TD-Gammon,TD 就是时间差学习。Deep Blue 是一个规则系统,并不是一个学习系统。
  • DeepMind 2013 年在 Nature 上发表的 Human-level control through deep reinforcement learning 提出了一个新的概念,结合了深度学习革命和古老的强化学习,变成了深度强化学习。论文中,他们发明了一个新的算法 —— Deep Q-Network,简称 DQN。Deepmind 用同一个算法,代码一行不改,就能够玩遍所有 Atari Game。训练完之后,大家发现算法学会的策略比某些最好的人类玩家还要强大。
    • Atari 虽然是在一个很小的屏幕上玩的游戏,但其信息量非常大。比如说,提供一幅游戏截屏的图片,你要学会理解如何操控 Pacman,什么是豆子,以及怪物的行走轨迹,你要有一个对应的策略来避开怪物。所以 Atari 牵涉到计算机视觉,它不是一个简单的用几条规则就能够确定的游戏。在这个意义上,Atari 比跳棋之类的游戏都复杂很多。2013 年前,如果说要用同一个智能体来玩所有 Atari 游戏,那简直是天方夜谭。
    • DQN 是一个现代强化学习的分水岭,因为在此之前,强化学习都只能做一些低维度的环境,对于图片这种高维度的信息,之前的算法都无法处理(比如一张游戏截图中可能包含几十万像素)。所以 DQN 的过人之处,就在于把深度学习、卷积神经网络等计算机视觉的一些突破应用在强化学习上,让强化学习算法也能够处理高维度的信息
  • Doom 3D shooter
  • 2016 年,DeepMind AlphaGo 在围棋上 4:1 战胜李世石。同年在 Nature 上发表了《Mastering the Game of Go with Deep Neural Networks and Tree Search》,详细介绍了如何用深度学习和蒙特卡洛树搜索的方法来学习下围棋。
  • 2017 年,DeepMind AlphaGo Zero,完全抛弃人类知识,从零开始,通过自己和自己不断对弈,用纯粹的强化学习方法来学习围棋策略(之前 AlphaGo 是通过大量学习人类棋谱,再用强化学习进行微调),并最终棋力远超 AlphaGo。同年在 Nature 上发表了《Mastering the Game of Go without Human Knowledge》。
  • 2017 年,DeepMind Alpha Zero 基本用的是 AlphaGo Zero 的算法:自我对弈、蒙特卡洛树搜索、纯粹的强化学习,用同一套算法学习了 chess(国际象棋) 和 shogi(日本将棋),并分别在这两个领域中远远超过之前世界上最强的人工智能:【鳕鱼】国际象棋引擎和【Elmo】将棋引擎。同时发表了《Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm》。
  • 下阶段:魔兽争霸、王者荣耀、英雄联盟、GTA V 高仿真赛车游戏等等……

RL in Real World

  • Robotics: 一个方法是搭建物理模型,精确描述骑自行车的机理,然后求解复杂的微分方程组。另一个简单很多的方法就是用强化学习让机器人通过不断试错,自己找到最佳决策方案
  • World of Bits: 因为它的终极目标是让人工智能学会如何上网
  • 金融领域:我们可以认为股票市场交易就是一个游戏,所获得的奖励就是最后的利润。我们的目标是把利润最大化,但是这牵涉到一个复杂的决策过程:何时买?何时卖?何时转移投资方向?等等。
  • Advertising: Multi-arm Bandit 问题。
  • 能源控制:机房制冷系统,对于不同的负载情况、不同时间点、不同天气、都能合理分配最佳的制冷能源额度。

Multi-arm Bandit

价值与奖励

  • Action(决策): 比如现有 10 台老虎机,那么 action space 就有 10 个选择。(例:第一次拉第 3 台,则 a1 = 3,此处下标表示 time step。)
  • Reward(奖励): 即每次拉老虎机所获奖励。(例:第一次毫无收获,第二次吐出 100 枚金币,则 r1 = 0,r2 = 100。)但这是一个随机过程,且符合一定 distribution(概率分布)p(r)。要在规定时间内获得最多 reward,即表示 ∑(reward) 最大。
  • Action Value(决策价值):q(a) = E[R_t|A_t = a],如 q(3) = E[R_t|A_t = 3] 表示第三台老虎机的期望奖励就是其决策价值。
    • q(a) 是 Action Value,亦称 Q-value
    • E 是 Expected VAlue
    • R_t 是第 t 步获得的 Reward
    • A_t 是第 t 步采取的 Action
  • Reward ≠ Value
    • Value(价值)体现的是长远利益,而 Reward(奖励)体现的是眼前的利益。
    • Value 越高意味着对应的决策越好。
    • 下一个 time step 中的 reward 高不代表 value 也高。
  • Q-table:
    • 由于不知道 Q 表格中的真实数值(价值),所以只能用各种方法估算。
    • Q_t(a) = (R_1 + R_2 +...+ R_n)/N(a)
      • R_n 是每次拉动老虎机得到的奖励值
      • N(a) 是拉第 a 个老虎机的次数
    • A* = argmax Q_t(a) 就是我们要选择的老虎机。

探索与开拓

思想实验:假设用上述方法,第⑤号老虎机的三次实验平均奖励最高,那么剩下的拉老虎机的机会将全部给予⑤号。然而,很有可能第⑦号老虎机的真正长远价值要大于⑤号,只是在你尝试⑦号老虎机的三次实验,不巧是手气不好的三次。正是因为你没有给第⑦号足够的机会,所以就导致你误判了⑤号老虎机是长远来看最好的选择。

当你专注于一个选项,每次都采取同一个 action 时,就好比在打一口油田,疯狂地针对一个地方往下钻。在强化学习中,我们把这个过程称为 Exploit,中文是 “开采”、“开拓” 的意思。当你把目前看上去最好的选项放在一边,去尝试别的选项时,我们称这个过程为 Explore,即 “探索”。

  • 学而不思则罔,思而不学则殆。“学” 就是探索,“思” 就是开拓。
  • Exploitation 和 Exploration 是一对好基友,又是一对死对头。如果不开拓,就无法很快获得足够的奖励,也就迷失了强化学习的目的。但从长远来看,如果不探索,那就无法发现潜在的更好的选项来进一步开拓。
  • Exploitation 是深度,而 Exploration 是广度。深度和广度缺一不可
  • 因为资源有限,所以要在有限的资源内把累计奖励最大化。
    • “greedy algorithm”(贪心算法):各三次实验求平均,估计完 Q 值,之后只选最大 Q 值所对应的老虎机来拉。顾名思义就是贪婪地冲着目前奖励最高的老虎机。贪心算法把所有的资源都分配给了 exploitation。
    • “ε-greedy”(epsilon 贪心):每次以 ε 的概率,随机地选下一步要拉哪个老虎机,以 1 - ε 的概率(剩下的概率) 选目前获得奖励最高的 action。ε 一般是比较小的数字,比如 0.1。意思是 10% 的情况下我们在探索,90% 的情况在开拓。在这个过程中,Q-table 里的十个数字的相对大小会根据目前最新的奖励情况不断改变。当探索率为 10% 时,有 80% 的情况(最终实验结果)下都选对了最好的 action。探索率越低,押对最优老虎机的比例就越低。

非静态 Bandit 问题

  • M → Motivation:为什么要解决非静态的多臂老虎机问题?
    之前,我们假设在皇家赌场呆的一百天里,每台老虎机每天的概率分布都不变。但如果赌场老板中途悄悄给老虎机做了手脚,那之前我们对每台老虎机做出的价值估计就是错误的,需要及时更新。
  • IN → Intuition:解决这个问题的最直观的思路是什么?
    之前我们用了很简单的 “平均法”,即只要记录拉过多少次指定老虎机,把所有获得奖励总和除以拉动次数,就可获得对其 Q 值的估计。这个总和包含了所有的历史数据,从第一天到最后一天都是同等对待。
    解决非静态强化学习的思路就是摒弃过期很久的历史数据,把更多的权重放在最近获得的新数据上
  • T → Technicality:
    • $$Q_n = \frac{1}{(n-1)} \sum_{i=1}^{n-1} R_i$$
    • $$Q_{n+1} = \frac{1}{n} \sum_{i=1}^{n} R_i$$
    • 新值 Q(n+1) = 旧值 Q(n) + 权重 1/n ✖️ (目标值 R(n) - 旧值 Q(n) ),这种描述方式特别像梯度下降算法(Gradient Descent),即 R(n) 是目前的最新值,我们把曾经旧的期望 Q(n) 往新值的方向推进。
    • 用 α 代替 1/n。此处 α 可以是一个较复杂的关于 n 的函数,或是一个常数。如果赌场老板中途改变了某些老虎机的概率,那么我们的策略就需要跟着更新。如果 α = 1/n ,就意味着之前的 reward 在以相同权重做平均。可以在 α 上做文章,给最新获得的 reward 更多权重。
    • 解决非静态 Bandit 的核心就是合理运用 α
    • $$Q_{n+1} = Q_n + \alpha (R_n-Q_n) = \alpha R_n + (1-\alpha)Q_n = \sum_{i=1}^n \alpha (1-\alpha)^{n-i} R_i + (1-\alpha)^{n} Q_1$$
    • Incremental Q Update: 如果 0 <α < 1,即 1-α < 1,那么此处 (1-α)^(n-i) 会从非常小的数逐渐增加,也就意味着对后面的 R 赋予较高权重(最高为 α)。 Incremental Q update 算法,R1 权重非常小,之后的权重以指数增长的趋势逐渐变大,最大的权重位于最新的 Rn 上。以这样的分布做平均的算法,我们称之为 Exponential Recency Weighted Average(近因指数加权平均)
    • 遗忘,是应对变幻莫测的最佳方法。

高级探索

  • Optimistic Exploration(乐观探索法),也叫 Optimistic Initial Value(乐观初始值)。
    • 假设一开始刻意地高估每个老虎机的价值。那么,直到它们让你 “失望” 之前,你都在探索新的老虎机。
    • 例子:假设你面前有三台老虎机(即三个 action),且已知每台老虎机奖励你的金币数目最少是 1 枚,最多是 3 枚。之前的做法是把每台老虎机的初始价值估计设为 0。现在故意把每台的初始价值估计设为 5 枚金币。因为每次奖励最多只有 3 枚金币,所以这个初始值很明显是高估的。我们称之为 “乐观估计”。之后仍然遵循纯贪心算法,即我们每次选择目前拥有最大价值估计的老虎机 —— argmax Q(a)。如果出现两台老虎机的 Q 值并列冠军的情况,那么就在它们之间随机选择。因为无论哪台老虎机都不会给出超过 3 枚金币,所以刚开始的一段时间里无论作何选择都只会降低 Q 值。
    • 算法:
      • Step 1:Ⓐ Ⓑ Ⓒ 刚开始都是并列最大(都是 Q = 5)。我们随机选择 Ⓑ 机器,获得 2 枚金币,与初始 Q 值做平均,得 Ⓑ 最新 Q 值 为 (5+2)/2 = 3.5。
      • Step 2:Ⓐ = Ⓒ = 5,继续采用贪心算法,在并列最大的 Ⓐ Ⓒ 老虎机中随机选择。假设我们的选择是 Ⓐ,得金币 1 枚,那 Ⓐ的新估计就变为 (5+1)/2 = 3.0。
      • Step 3:现在只有 Ⓒ 机拥有最大 Q 值,根据贪心算法,只可能选择 Ⓒ 机作为这一步的 action。
    • 从这个实例可以看出,即使用绝对贪心算法,也可以实现轮流选择不同 action,而非固定 exploit 某一个选项。乐观探索法通过在初始值上做手脚,机智地平衡了 exploration 与 exploitation
  • Upper-Confidence Bound(简称 UCB,上限置信区间算法)。该算法相对比较复杂, 且只适用于 Multi-arm Bandit 问题,对别的强化学习问题并没有显著帮助。

    • M -> Motivation:为什么要发明这个算法?
      ε 贪心算法以 ε 概率随机选择一个非最佳的 action 来进行探索。问题在于,很可能一台老虎机你已经试了 1000 次,但另一台你只试了 50 次。从统计上说,试验次数越多,得到价值估计就越准确;反之,试验次数越少,价值估计的不确定性就越大。但 ε 贪心算法完全没有考虑这一点,它只会不顾任何情况地随机试验
    • IN -> Intuition:解决这个问题的直观思路是什么?
      Upper-Confidence Bound 的中心思想,就是把上文提到的不确定性纳入探索过程,根据一个数学公式调整 Q 值的相对大小对最终决策的影响。校正过 Q 值之后,下一步的 action 就由纯贪心(简单的取最大值)来决定。
    • T -> Technicality:

      • Q_t(a) 是原本未校正的 Q 值估计
      • t 是目前总共试验次数
      • N_t(a) 是尝试某一个老虎机 a 的次数
      • c 是超参数,控制探索与开拓的平衡,平方根可以直观认为是某 action 的标准差

      其中,第二项分母 N_t(a),即某个 action 的实验次数越大,表达式的值就越小,意味着 argmax 越不容易选择这个 action。换言之,当尝试某个 action 次数越多,那么 Confidence(置信度)就越高,自然不需要更多的探索。
      第二项分子中 t 越大,表达式的值也越大,argmax 更可能探索这个 action。直观的说,两个赌场里,假设 ③ 号老虎机的试验次数都是 1000 次(即 N_t(③) = 1000)。如果第一个赌场的总次数是 100 万次,第二个赌场的总次数是 2000 次,则对 ③ 号老虎机的相对置信度是第一个赌场更低。
      当 c 越大,第二项的值也越大,意味着我们越多地做探索。当 c = 0,此式等价于未校正过的 Q_t(a),UCB 算法退化为简单的纯贪心算法,相当于没有任何探索成分。

小结1

  • 乐观探索法第四步开始依然执行同样的策略与初始值取平均,还是所有值取平均,还是与最近一次的值取平均,还是用非静态的方法求解,还是其他方法……
  • UCB 算法中,t 是总的可试验次数还是截止当前 action 已试验次数,直觉上好像都可以。 而且 UCB 是不是也可以用非静态的方法求解 Q,或者用乐观探索法求解 Q……有没有把所有方法综合起来的……

其实,关键就集中在两个问题上:

  • 如何尽量准确估计 Q(Q 表格)
    • ε-greedy: 不估计
    • 平均 + greedy,非静态
    • 乐观探索 + greedy
    • UCB + greedy

梯度上升

  • Motivation

    • Implicit Policy(隐性策略):Q-table 与 ε-Greedy 相结合的方法来选择下一步的决策。此策略是根据 Q-table 推导出,而非以直接形式呈现。
    • Explicit Policy(显性策略):即每一步都由直接的函数来体现,函数的输出就是选择老虎机的概率分布。π 表示 policy,π(a) 是所有 action 的概率分布。 从 explicit policy 的视角,多臂老虎机问题就转化为学习最佳 π(a),即策略的概率分布问题
      假设现有 10 台老虎机,则 π(1) = 0.1 表示选择第①台老虎机的概率是 10%;π(9) = 0.3 表示第⑨九台老虎机更可能被选择,概率为 30%。

    皇家赌场里有 10 台老虎机,π(a) 是离散概率,可以由 10 个数表示:π(a) = [p1, p2, ... p10],其中每个数字代表尝试每台老虎机的概率,所有概率相加等于 1。该如何学习组成 π(a) 概率分布的 10 个数,使得长远奖励的总和最大化?

  • Intuition
    Hill Climbing,选择最陡峭的山坡移动。

  • Technicality

    • $$H_{t+1}(a) = H_t(a) + \frac {\partial \mathbb{E} [R_t]}{\partial H_t(a)} \cdot \alpha$$

      • a 表示 action
      • H_t(a) 表示上一步 “爬山” 的 x,H_(t+1)(a) 是爬山之后的 x
      • E[R_t] 是奖励期望值 expectation of reward,也就是老虎机的目标函数
      • α 是学习率 Learning rate
    • 如何求 E[R_t] 关于 H(a) 的梯度?

      • 最后目标是为求得 π(a),action probability,有 10 个数,每个数代表每台老虎机被选择概率,相加总和为 1。
      • H(a) 中每个数本身的大小并不很重要,加起来也不需要等于 1,但他们的相对大小表达了我们策略的偏好。H(a) 直观可以理解为坐标 x,也就是一种选择,或者选择的结果,其中有 10 个参数,10维,可以转换为 softmax 的概率,也就是最应该选择哪一个老虎机。
    • 如何把 H(a) 转化为 π(a)
      • Softmax:总和为 1,只对相对大小有意义。
        $$\pi(a) = \frac {e^{H(a)}}{\sum_b e^{H(b)}}$$
    • 目标函数:
      • $$\mathbb{E}[R_t] = \sum_b \pi(b) \cdot q^*(b)$$
      • q* 为每个老虎机真实的长远价值;
      • π 为是选择老虎机的概率分布。
    • E[R_t] 和 H 值的关系是什么?
      • $$\frac {\partial \mathbb{E}[R_t]} {\partial H(a)} = \sum_b q^*(b) \frac {\partial \pi(b)}{\partial H(a)} = \sum_b q^*(b) \pi(b) (\mathbb{1}_{a=b} - \pi(a)) = \mathbb{E}[q^*(b)(\mathbb{1}_{a=b} - \pi(a)] = R_t (\mathbb{1}_{a=A_t} - \pi(a))$$
      • q*(b) 的期望值,即每个 action 的长期价值,在 expectation 上应等于 R(t)
    • 梯度下降
      • $$H_{t+1}(a) = H_t(a) + \alpha \cdot R_t \cdot (\mathbb{1}_{a=A_t} - \pi_t(a))$$
        • $$H_{t+1}(a) = H_t(a) + \alpha \cdot R_t \cdot (1 - \pi_t(a)) ,\ \ a=A_t$$
        • $$H_{t+1}(a) = H_t(a) - \alpha \cdot R_t \cdot \pi_t(a) ,\ \ a \ne A_t$$
      • 当真正采取的 action 是 a 时,indicator 为 1;当 action 没有采用 a 时,indicator 为 0 。
      • 这组方程非常好地印证了之前提到的 Thorndike 效果律 —— 当一个 action 所给出的 reward 始终是正的,那么就多做这个 action,少做别的 action;反之亦然

总结

汇总

  • ε-greedy: 以 ε 的概率选择一个随机的 action,以 1-ε 的概率选择目前最优的 action。当 ε = 0,为纯贪心算法,也是ε-Greedy 的一种特殊情况。
  • Optimistic Initial Value: 即乐观的 exploration,故意高估初始值,之后无论获得什么奖励,Q 值总是下降,用这种方法来鼓励你更多地探索没有尝试过的选项。
  • Upper Confidence Bound: 其中心思想是,不断地调整你对每个 action 的 confidence。如果你对一个 action 的长远价值越不确定,你就应该更多地尝试这个 action;如果你对其价值已很确定,就不需再浪费时间试验这个 action。
  • Bandit Gradient: 以全新的视角来学习 Explicit Policy(显性策略)的 π(a)。π 是关于每个 action 的概率分布。我们用梯度上升(Gradient Acsent)的方法来学习π这个参数,求的是最后的目标函数,即 R 的期望值。

  1. 红线 ε:指ε-greedy 的超参数,需要手动设置。当ε = 1/16,即 5%~6% 之间的 exploration,ε-greedy 获得的分数最好。
    极端情况下,如果 explore 了太多,比如当ε = 1/4,意味着 25% 的时间都在做随机决定,并不妥善;如果 explore 太少,就成了贪心算法,也是非最佳状态。

  2. 黑线 Q_0:指 Optimistic Initialization 的超参数,即最初的取值。同样,Q_0 不可太大也不可太小。当 Q_0 = 1,取得最大奖励值;当 Q_0 很大,过于乐观,那么大部分时间都在 explore,浪费精力;当 Q_0 很小,不够乐观,也对获得理想奖励值无益。

  3. 蓝线 c:指 UCB(Upper Confidence Bound) 算法的超参数 confidence。同样,c 越大,意味着做越多 exploration。图中可见,随着 c 的增大,UCB 最后获得的奖励退步很明显。当 c = 0,UCB 与贪心算法等价。

  4. 绿线 α:指 Gradient Bandit 的超参数,即 step size,或 learning rate。 α与 exploration 和 exploitation 的关系并没这么明显,α控制的是梯度上升的速率。如果α过大,会造成数值不稳定,偏移你的本来目标;但如果α过小,学习的速率就会太慢。 因为 Gradient Bandit 的 explicit policy 是一个概率分布,所以,在做下一步决策时,本身就是随机采样。从这种意义上,explicit policy 是自带 exploration 的。

Gittins Index

Gittins Index: 通过计算一个复杂函数,把在每一步取到最大值的 x,作为这一步采取的 action。Gittins 算法不仅比 UCB 更好,而且还可被在数学上证明是多臂老虎机的最优解。其大概基于的原理是:用贝叶斯统计来计算出一个最优的 exploration 和 exploitation 的平衡。一般情况下,这个平衡点无法被计算出,但是因为多臂老虎机过于简单,所以 Gittins Index 足够解决这个问题。但是,任何更复杂的问题,都没有 Gittins Index 的用武之地。

Missing

  • Stateless: 多臂老虎机是一个 Stateless,即没有状态的问题。比如,今天拉了第③号老虎机,到了第二天,别的老虎机并不会因为你昨天的行为而改变今天奖励的概率。
  • Credit assignment: 因为没有状态,所以不存在 credit assignment 的问题。这是继 Exploration 和 Exploitation 之后,第二个强化学习的心脏问题。(每一步对最后获得奖励的贡献不同)理清楚每一步决定对最后奖励的贡献,就是 Credit assignment 的核心
In [ ]: