说明：来自李飞飞教授博士范麟熙个人公众号：心有麟熙
背景介绍¶
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：
- Qn=1(n−1)n−1∑i=1Ri
- Qn+1=1nn∑i=1Ri
- 新值 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 的核心就是合理运用 α。
- Qn+1=Qn+α(Rn−Qn)=αRn+(1−α)Qn=n∑i=1α(1−α)n−iRi+(1−α)nQ1
- Incremental Q Update: 如果 0 <α < 1，即 1-α < 1，那么此处 (1-α)^(n-i) 会从非常小的数逐渐增加，也就意味着对后面的 R 赋予较高权重（最高为 α）。 Incremental Q update 算法，R1 权重非常小，之后的权重以指数增长的趋势逐渐变大，最大的权重位于最新的 Rn 上。以这样的分布做平均的算法，我们称之为 Exponential Recency Weighted Average（近因指数加权平均）。
- 遗忘，是应对变幻莫测的最佳方法。
- Qn=1(n−1)n−1∑i=1Ri
高级探索¶
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
- Ht+1(a)=Ht(a)+∂E[Rt]∂Ht(a)⋅α
- a 表示 action
H_t(a)表示上一步 “爬山” 的 x，H_(t+1)(a)是爬山之后的 xE[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，只对相对大小有意义。
π(a)=eH(a)∑beH(b)
- Softmax：总和为 1，只对相对大小有意义。
目标函数：
- E[Rt]=∑bπ(b)⋅q∗(b)
q*为每个老虎机真实的长远价值；π为是选择老虎机的概率分布。
- E[Rt]=∑bπ(b)⋅q∗(b)
E[R_t]和 H 值的关系是什么？- ∂E[Rt]∂H(a)=∑bq∗(b)∂π(b)∂H(a)=∑bq∗(b)π(b)(1a=b−π(a))=E[q∗(b)(1a=b−π(a)]=Rt(1a=At−π(a))
q*(b)的期望值，即每个 action 的长期价值，在 expectation 上应等于R(t)。
- ∂E[Rt]∂H(a)=∑bq∗(b)∂π(b)∂H(a)=∑bq∗(b)π(b)(1a=b−π(a))=E[q∗(b)(1a=b−π(a)]=Rt(1a=At−π(a))
梯度下降
- Ht+1(a)=Ht(a)+α⋅Rt⋅(1a=At−πt(a))
- Ht+1(a)=Ht(a)+α⋅Rt⋅(1−πt(a)), a=At
- Ht+1(a)=Ht(a)−α⋅Rt⋅πt(a), a≠At
- Ht+1(a)=Ht(a)+α⋅Rt⋅(1−πt(a)), a=At
- 当真正采取的 action 是 a 时，indicator 为 1；当 action 没有采用 a 时，indicator 为 0 。
- 这组方程非常好地印证了之前提到的 Thorndike 效果律 —— 当一个 action 所给出的 reward 始终是正的，那么就多做这个 action，少做别的 action；反之亦然。
- Ht+1(a)=Ht(a)+α⋅Rt⋅(1a=At−πt(a))
- Ht+1(a)=Ht(a)+∂E[Rt]∂Ht(a)⋅α
总结¶
汇总¶
- ε-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 的期望值。
- 红线 ε：指ε-greedy 的超参数，需要手动设置。当ε = 1/16，即 5%~6% 之间的 exploration，ε-greedy 获得的分数最好。
极端情况下，如果 explore 了太多，比如当ε = 1/4，意味着 25% 的时间都在做随机决定，并不妥善；如果 explore 太少，就成了贪心算法，也是非最佳状态。
黑线 Q_0：指 Optimistic Initialization 的超参数，即最初的取值。同样，Q_0 不可太大也不可太小。当 Q_0 = 1，取得最大奖励值；当 Q_0 很大，过于乐观，那么大部分时间都在 explore，浪费精力；当 Q_0 很小，不够乐观，也对获得理想奖励值无益。
蓝线 c：指 UCB(Upper Confidence Bound) 算法的超参数 confidence。同样，c 越大，意味着做越多 exploration。图中可见，随着 c 的增大，UCB 最后获得的奖励退步很明显。当 c = 0，UCB 与贪心算法等价。
绿线 α：指 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 的核心。