{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"toc": "true"
},
"source": [
"# Table of Contents\n",
" <p><div class=\"lev1 toc-item\"><a href=\"#背景介绍\" data-toc-modified-id=\"背景介绍-1\"><span class=\"toc-item-num\">1 </span>背景介绍 </a></div><div class=\"lev2 toc-item\"><a href=\"#Riding-bike\" data-toc-modified-id=\"Riding-bike-11\"><span class=\"toc-item-num\">1.1 </span>Riding bike</a></div><div class=\"lev2 toc-item\"><a href=\"#源头\" data-toc-modified-id=\"源头-12\"><span class=\"toc-item-num\">1.2 </span>源头 </a></div><div class=\"lev2 toc-item\"><a href=\"#在动物界的灵感\" data-toc-modified-id=\"在动物界的灵感-13\"><span class=\"toc-item-num\">1.3 </span>在动物界的灵感 </a></div><div class=\"lev3 toc-item\"><a href=\"#RL:-Prediction\" data-toc-modified-id=\"RL:-Prediction-131\"><span class=\"toc-item-num\">1.3.1 </span>RL: Prediction</a></div><div class=\"lev3 toc-item\"><a href=\"#RL:-Control\" data-toc-modified-id=\"RL:-Control-132\"><span class=\"toc-item-num\">1.3.2 </span>RL: Control</a></div><div class=\"lev3 toc-item\"><a href=\"#Model-free-VS-Model-based\" data-toc-modified-id=\"Model-free-VS-Model-based-133\"><span class=\"toc-item-num\">1.3.3 </span>Model-free VS Model-based</a></div><div class=\"lev1 toc-item\"><a href=\"#应用介绍\" data-toc-modified-id=\"应用介绍-2\"><span class=\"toc-item-num\">2 </span>应用介绍 </a></div><div class=\"lev2 toc-item\"><a href=\"#RL-in-Games\" data-toc-modified-id=\"RL-in-Games-21\"><span class=\"toc-item-num\">2.1 </span>RL in Games</a></div><div class=\"lev2 toc-item\"><a href=\"#RL-in-Real-World\" data-toc-modified-id=\"RL-in-Real-World-22\"><span class=\"toc-item-num\">2.2 </span>RL in Real World</a></div><div class=\"lev1 toc-item\"><a href=\"#Multi-arm-Bandit\" data-toc-modified-id=\"Multi-arm-Bandit-3\"><span class=\"toc-item-num\">3 </span>Multi-arm Bandit</a></div><div class=\"lev2 toc-item\"><a href=\"#价值与奖励\" data-toc-modified-id=\"价值与奖励-31\"><span class=\"toc-item-num\">3.1 </span>价值与奖励 </a></div><div class=\"lev2 toc-item\"><a href=\"#探索与开拓\" data-toc-modified-id=\"探索与开拓-32\"><span class=\"toc-item-num\">3.2 </span>探索与开拓 </a></div><div class=\"lev2 toc-item\"><a href=\"#非静态-Bandit-问题\" data-toc-modified-id=\"非静态-Bandit-问题-33\"><span class=\"toc-item-num\">3.3 </span>非静态 Bandit 问题 </a></div><div class=\"lev2 toc-item\"><a href=\"#高级探索\" data-toc-modified-id=\"高级探索-34\"><span class=\"toc-item-num\">3.4 </span>高级探索 </a></div><div class=\"lev2 toc-item\"><a href=\"#小结1\" data-toc-modified-id=\"小结1-35\"><span class=\"toc-item-num\">3.5 </span>小结 1</a></div><div class=\"lev2 toc-item\"><a href=\"#梯度上升\" data-toc-modified-id=\"梯度上升-36\"><span class=\"toc-item-num\">3.6 </span>梯度上升 </a></div><div class=\"lev1 toc-item\"><a href=\"#总结\" data-toc-modified-id=\"总结-4\"><span class=\"toc-item-num\">4 </span>总结 </a></div><div class=\"lev2 toc-item\"><a href=\"#汇总\" data-toc-modified-id=\"汇总-41\"><span class=\"toc-item-num\">4.1 </span>汇总</a></div><div class=\"lev2 toc-item\"><a href=\"#Gittins-Index\" data-toc-modified-id=\"Gittins-Index-42\"><span class=\"toc-item-num\">4.2 </span>Gittins Index</a></div><div class=\"lev2 toc-item\"><a href=\"#Missing\" data-toc-modified-id=\"Missing-43\"><span class=\"toc-item-num\">4.3 </span>Missing</a></div>"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"说明：来自李飞飞教授博士范麟熙个人公众号：心有麟熙"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 背景介绍"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Riding bike\n",
"\n",
"- trial and error：试错法\n",
"- reward：可以使正的奖励或负的惩罚 \n",
"\n",
"使用 trial and error 不断尝试，在每一次尝试中总结经验，然后再提高下一次的 reward，这就是**强化学习的精髓**。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 源头\n",
"\n",
"- 1948 Alan Turing 提出 pleasure-pain system 的概念，如果一个系统能够把 pleasure 最大化，把 pain 最小化，就相当于从经验中不断 “学习”。\n",
"- 1952 Claude Shannon 设计了一个机械装置：Shannon Maze-runner，实现了最基本的强化学习算法，老鼠根据试错法自己走出迷宫。Claude Shannon 1948 年的论文 Mathematical Theory of communication 创立现代信息学理论，1937 年 21 岁，MIT 硕士论文奠定了电路设计的基础。\n",
"- 1961 Marvin Minsky 论文《走向人工智能之路》，提到了 trial and error 这种学习方式，以及一个新概念 “credit assignment”：同时存在的因素，最终起作用的是哪个？这是强化学习的核心问题之一。 \n",
"- Arthur Samuel，IBM 研究员，在 IBM 设计了一台能下跳棋的电脑：TD Learning，是强化学习的重要算法。此人创造了 MachineLearning 这个词组。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 在动物界的灵感\n",
"\n",
"\n",
"### RL: Prediction\n",
"\n",
"- Classical Conditioning\n",
" - Pavlov's dog\n",
" - 在强化学习里，经典条件反射，对应的就是 Prediction（预测）。当你看到一个信号（比如铃铛）时，你会预测将获得怎样的奖励，然后再根据这个预测来采取行动。当然，经典条件反射是一个相对被动的过程。\n",
"- Law of Effect\n",
" - Thorndike 提出了Law of Effect（效果律），维基百科上的定义是，在一个特定的情景下可以得到满意的效果的反应，在该情景下重复出现的概率会上升，而得到不满意的效果的反应重复出现的概率则会下降。\n",
" - Thorndike's Cat：Thorndike设 计了一个装置。在这个笼子里，如果猫按了踩板，那么笼子的门就会打开。实验发现，开始时，猫咪会在笼子里不停地打转，一点头绪都没有，但是偶尔会随机地踏到踩板，然后笼子就打开了。之后第二次，猫咪再被放到笼子里时，它就会直接去踏踩板，而不会再像无头苍蝇一样浪费时间。\n",
"\n",
"\n",
"\n",
"### RL: Control\n",
"\n",
"- Operant Conditioning\n",
" - 如果说巴普洛夫的狗是一种非自愿的条件反射，那么上述 Thorndike 的猫就是一种自愿的条件反射。这种自愿的行为，在后来被心理学巨匠B. F. Skinner 总结为 Operant Conditioning（操控反射）。\n",
" - Skinner Box：在研究操控反射时，Skinner 设计了一个动物实验装置 ── Skinner Box。在这个盒子里，设有一只老鼠，和一个它能够操控的装置。如果按下杠杆，就会有食物从管中掉落；亦或是在另一种实验中，如果小鼠按下杠杆，盒子就会发出很大响声让小鼠受到惊吓。Skinner 就用这样一种装置来研究动物行为，和动物与环境的交互，即获得奖励（食物）或是惩罚（响声）。Skinner 观察到，当获得奖励时，小鼠会非常频繁地按动杠杆；而当获得惩罚时，小鼠则会尽力避免触动杠杆。\n",
" - 在强化学习的语言里，Skinner 的 Operant Conditioning（操控反射）对应的概念是 Control，即能够根据对环境的认识，来操控环境，从而使对自己的奖励最大化。\n",
"\n",
"\n",
"### Model-free VS Model-based\n",
"\n",
"- Model-free RL \n",
" Trial & Error（试错法）是强化学习的核心思想，但它并不是唯一的思想。Trial & Error 及其对应的一套算法，称为Model-free Reinforcement Learning，即没有模型的强化学习。这可认为是，人们在不断试错的过程中，养成的一种习惯。\n",
"- Model-based RL \n",
" 这种强化学习涉及到 Planning（规划）：正因为脑海中有了环境模型，所以在第二次行动时就不需要东奔西跑，可以直接根据地图来做详细的规划。\n",
"- 可以用1929年美国心理学家做的小鼠实验来概括。在这个实验中有两组老鼠： \n",
" - 第一组老鼠被置于迷宫里，迷宫中央设有食物。小鼠会顺着气味行动，最后取得食物，假设这组老鼠获得食物花了10分钟。这就是我们说的Trial & Error，通过不断试错（在迷宫中走到死路就往另外一边走）来达成目的。 \n",
" - 第二组老鼠，一开始时被放置在同样的迷宫里，但这个迷宫中央并没有食物，也就是说，这个环境中并无任何奖励，小鼠在迷宫中完全是想怎么打转就怎么打转。这一阶段并不存在Trial & Error，因为小鼠没有试图去获得某种奖励。实验人员发现，如果紧接着把这组小鼠放在相同的但是有食物的迷宫里，那么这些小鼠就能够在短短 3 分钟内就找到食物。这个实验结果表明，虽然在第一阶段没有任何奖励机制，但是小鼠脑子里已经建立起了一个 “环境模型” ── **Cognitive Map**，也就是这个迷宫的地图。接着在第二阶段中设置了奖励时，小老鼠就能利用它们存在脑海里的地图，快速地找到食物。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 应用介绍"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## RL in Games\n",
"\n",
"\n",
"- IBM 研究员 **Arthur Samuel**，是世界上第一个把强化学习应用在一个主流的棋盘（跳棋）游戏上的人。\n",
"- 在 1989 年到 2007 年之间，加拿大阿尔伯坦大学的团队，做了一个跳棋的人工智能 —— **Chinook**，在真正意义上破解了跳棋。\n",
"- IBM 的研究员 **Gerald Tesauro**，他最著名的成就，就是写了一个能够超越人类 Backgammon 世界冠军的人工智能。Backgammon 是一个有一定随机性的掷骰子的概率游戏。Tesauro 的引擎叫做 **TD-Gammon**，TD 就是时间差学习。**Deep Blue** 是一个规则系统，并不是一个学习系统。\n",
"- DeepMind 2013 年在 Nature 上发表的 Human-level control through deep reinforcement learning 提出了一个新的概念，结合了深度学习革命和古老的强化学习，变成了深度强化学习。论文中，他们发明了一个新的算法 —— **Deep Q-Network，简称 DQN**。Deepmind 用同一个算法，代码一行不改，就能够玩遍所有 Atari Game。训练完之后，大家发现算法学会的策略比某些最好的人类玩家还要强大。\n",
" - Atari 虽然是在一个很小的屏幕上玩的游戏，但其信息量非常大。比如说，提供一幅游戏截屏的图片，你要学会理解如何操控 Pacman，什么是豆子，以及怪物的行走轨迹，你要有一个对应的策略来避开怪物。所以 Atari 牵涉到计算机视觉，它不是一个简单的用几条规则就能够确定的游戏。在这个意义上，Atari 比跳棋之类的游戏都复杂很多。**2013 年前，如果说要用同一个智能体来玩所有 Atari 游戏，那简直是天方夜谭。**\n",
" - DQN 是一个现代强化学习的分水岭，因为在此之前，强化学习都只能做一些低维度的环境，对于图片这种高维度的信息，之前的算法都无法处理（比如一张游戏截图中可能包含几十万像素）。所以 **DQN 的过人之处，就在于把深度学习、卷积神经网络等计算机视觉的一些突破应用在强化学习上，让强化学习算法也能够处理高维度的信息**。\n",
"- Doom 3D shooter\n",
"- 2016 年，DeepMind AlphaGo 在围棋上 4:1 战胜李世石。同年在 Nature 上发表了《Mastering the Game of Go with Deep Neural Networks and Tree Search》，详细介绍了如何用深度学习和蒙特卡洛树搜索的方法来学习下围棋。\n",
"- 2017 年，DeepMind AlphaGo Zero，完全抛弃人类知识，从零开始，通过自己和自己不断对弈，用纯粹的强化学习方法来学习围棋策略（之前 AlphaGo 是通过大量学习人类棋谱，再用强化学习进行微调），并最终棋力远超 AlphaGo。同年在 Nature 上发表了《Mastering the Game of Go without Human Knowledge》。\n",
"- 2017 年，DeepMind Alpha Zero **基本用的是 AlphaGo Zero 的算法：自我对弈、蒙特卡洛树搜索、纯粹的强化学习**，用同一套算法学习了 chess（国际象棋） 和 shogi（日本将棋），并分别在这两个领域中远远超过之前世界上最强的人工智能：**【鳕鱼】国际象棋引擎和【Elmo】将棋引擎**。同时发表了《Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm》。\n",
"- 下阶段：魔兽争霸、王者荣耀、英雄联盟、GTA V 高仿真赛车游戏等等……"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## RL in Real World\n",
"\n",
"- Robotics: 一个方法是搭建物理模型，精确描述骑自行车的机理，然后求解复杂的微分方程组。**另一个简单很多的方法就是用强化学习让机器人通过不断试错，自己找到最佳决策方案**。\n",
"- World of Bits: 因为它的**终极目标是让人工智能学会如何上网**。\n",
"- 金融领域：我们可以认为股票市场交易就是一个游戏，所获得的奖励就是最后的利润。我们的**目标是把利润最大化，但是这牵涉到一个复杂的决策过程**：何时买？何时卖？何时转移投资方向？等等。\n",
"- Advertising: **Multi-arm Bandit** 问题。\n",
"- 能源控制：机房制冷系统，对于不同的负载情况、不同时间点、不同天气、都能合理分配最佳的制冷能源额度。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Multi-arm Bandit"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 价值与奖励\n",
"\n",
"\n",
"- Action（决策）: 比如现有 10 台老虎机，那么 action space 就有 10 个选择。（例：第一次拉第 3 台，则 a1 = 3，此处下标表示 time step。）\n",
"- Reward（奖励）: 即每次拉老虎机所获奖励。（例：第一次毫无收获，第二次吐出 100 枚金币，则 r1 = 0，r2 = 100。）但这是一个随机过程，且符合一定 distribution（概率分布）p(r)。要在规定时间内获得最多 reward，即表示 ∑(reward) 最大。\n",
"- Action Value（决策价值）：`q(a) = E[R_t|A_t = a]`，如 `q(3) = E[R_t|A_t = 3]` 表示第三台老虎机的期望奖励就是其决策价值。\n",
" - q(a) 是 Action Value，亦称 Q-value\n",
" - E 是 Expected VAlue\n",
" - R\\_t 是第 t 步获得的 Reward\n",
" - A\\_t 是第 t 步采取的 Action\n",
"- Reward ≠ Value\n",
" - Value（价值）体现的是长远利益，而 Reward（奖励）体现的是眼前的利益。\n",
" - Value 越高意味着对应的决策越好。\n",
" - 下一个 time step 中的 reward 高不代表 value 也高。\n",
"- Q-table：\n",
" - 由于不知道 Q 表格中的真实数值（价值），所以只能用各种方法估算。\n",
" - `Q_t(a) = (R_1 + R_2 +...+ R_n)/N(a)`\n",
" - R\\_n 是每次拉动老虎机得到的奖励值\n",
" - N(a) 是拉第 a 个老虎机的次数\n",
" - `A* = argmax Q_t(a)` 就是我们要选择的老虎机。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 探索与开拓\n",
"\n",
"\n",
"思想实验：假设用上述方法，第⑤号老虎机的三次实验平均奖励最高，那么剩下的拉老虎机的机会将全部给予⑤号。然而，很有可能第⑦号老虎机的真正长远价值要大于⑤号，只是在你尝试⑦号老虎机的三次实验，不巧是手气不好的三次。正是因为你没有给第⑦号足够的机会，所以就导致你误判了⑤号老虎机是长远来看最好的选择。 \n",
"\n",
"当你专注于一个选项，每次都采取同一个 action 时，就好比在打一口油田，疯狂地针对一个地方往下钻。在强化学习中，我们把这个过程称为 Exploit，中文是 “开采”、“开拓” 的意思。当你把目前看上去最好的选项放在一边，去尝试别的选项时，我们称这个过程为 Explore，即 “探索”。 \n",
"\n",
"\n",
"- 学而不思则罔，思而不学则殆。“学” 就是探索，“思” 就是开拓。\n",
"- Exploitation 和 Exploration 是一对好基友，又是一对死对头。如果不开拓，就无法很快获得足够的奖励，也就迷失了强化学习的目的。但从长远来看，如果不探索，那就无法发现潜在的更好的选项来进一步开拓。\n",
"- **Exploitation 是深度，而 Exploration 是广度。深度和广度缺一不可**。\n",
"- 因为资源有限，所以要在有限的资源内把累计奖励最大化。\n",
" - “greedy algorithm”（贪心算法）：各三次实验求平均，估计完 Q 值，之后只选最大 Q 值所对应的老虎机来拉。顾名思义就是贪婪地冲着目前奖励最高的老虎机。贪心算法把所有的资源都分配给了 exploitation。\n",
" - “ε-greedy”（epsilon 贪心）：**每次以 ε 的概率，随机地选下一步要拉哪个老虎机，以 1 - ε 的概率（剩下的概率） 选目前获得奖励最高的 action**。ε 一般是比较小的数字，比如 0.1。意思是 10% 的情况下我们在探索，90% 的情况在开拓。在这个过程中，Q-table 里的十个数字的相对大小会根据目前最新的奖励情况不断改变。当探索率为 10% 时，有 80% 的情况（最终实验结果）下都选对了最好的 action。探索率越低，押对最优老虎机的比例就越低。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 非静态 Bandit 问题\n",
"\n",
"\n",
"- M → Motivation：为什么要解决非静态的多臂老虎机问题？ \n",
" 之前，我们假设在皇家赌场呆的一百天里，每台老虎机每天的概率分布都不变。但如果赌场老板中途悄悄给老虎机做了手脚，那之前我们对每台老虎机做出的价值估计就是错误的，需要及时更新。\n",
"- IN → Intuition：解决这个问题的最直观的思路是什么？ \n",
" 之前我们用了很简单的 “平均法”，即只要记录拉过多少次指定老虎机，把所有获得奖励总和除以拉动次数，就可获得对其 Q 值的估计。这个总和包含了所有的历史数据，从第一天到最后一天都是同等对待。 \n",
" **解决非静态强化学习的思路就是摒弃过期很久的历史数据，把更多的权重放在最近获得的新数据上**。\n",
"- T → Technicality：\n",
" - $$Q_n = \\frac{1}{(n-1)} \\sum_{i=1}^{n-1} R_i$$\n",
" - $$Q_{n+1} = \\frac{1}{n} \\sum_{i=1}^{n} R_i$$ \n",
" - **新值 Q(n+1) = 旧值 Q(n) + 权重 1/n ✖️ (目标值 R(n) - 旧值 Q(n) )**，这种描述方式特别像梯度下降算法（Gradient Descent），即 R(n) 是目前的最新值，我们把曾经旧的期望 Q(n) 往新值的方向推进。\n",
" - 用 α 代替 1/n。**此处 α 可以是一个较复杂的关于 n 的函数**，或是一个常数。如果赌场老板中途改变了某些老虎机的概率，那么我们的策略就需要跟着更新。如果 α = 1/n ，就意味着之前的 reward 在以相同权重做平均。可以在 α 上做文章，给最新获得的 reward 更多权重。\n",
" - **解决非静态 Bandit 的核心就是合理运用 α**。 \n",
" - $$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$$\n",
" - Incremental Q Update: 如果 0 <α < 1，即 1-α < 1，那么此处 (1-α)^(n-i) 会从非常小的数逐渐增加，也就意味着对后面的 R 赋予较高权重（最高为 α）。 Incremental Q update 算法，R1 权重非常小，之后的权重以指数增长的趋势逐渐变大，最大的权重位于最新的 Rn 上。以这样的分布做平均的算法，我们称之为 **Exponential Recency Weighted Average（近因指数加权平均）**。\n",
" - **遗忘，是应对变幻莫测的最佳方法。**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 高级探索\n",
"\n",
"\n",
"- Optimistic Exploration（乐观探索法），也叫 Optimistic Initial Value（乐观初始值）。\n",
" - 假设一开始刻意地高估每个老虎机的价值。那么，直到它们让你 “失望” 之前，你都在探索新的老虎机。\n",
" - 例子：假设你面前有三台老虎机（即三个 action），且已知每台老虎机奖励你的金币数目最少是 1 枚，最多是 3 枚。之前的做法是把每台老虎机的初始价值估计设为 0。现在**故意把每台的初始价值估计设为 5 枚金币**。因为每次奖励最多只有 3 枚金币，所以这个初始值很明显是高估的。我们称之为 **“乐观估计”**。之后仍然遵循**纯贪心算法**，即我们每次选择目前拥有最大价值估计的老虎机 —— argmax Q(a)。如果出现两台老虎机的 Q 值并列冠军的情况，那么就在它们之间随机选择。因为无论哪台老虎机都不会给出超过 3 枚金币，所以刚开始的一段时间里无论作何选择都只会降低 Q 值。\n",
" - 算法：\n",
" - Step 1：Ⓐ Ⓑ Ⓒ 刚开始都是并列最大（都是 Q = 5)。我们随机选择 Ⓑ 机器，获得 2 枚金币，与初始 Q 值做平均，得 Ⓑ 最新 Q 值 为 (5+2)/2 = 3.5。\n",
" - Step 2：Ⓐ = Ⓒ = 5，继续采用贪心算法，在并列最大的 Ⓐ Ⓒ 老虎机中随机选择。假设我们的选择是 Ⓐ，得金币 1 枚，那 Ⓐ的新估计就变为 (5+1)/2 = 3.0。\n",
" - Step 3：现在只有 Ⓒ 机拥有最大 Q 值，根据贪心算法，只可能选择 Ⓒ 机作为这一步的 action。\n",
" - 从这个实例可以看出，**即使用绝对贪心算法，也可以实现轮流选择不同 action，而非固定 exploit 某一个选项。乐观探索法通过在初始值上做手脚，机智地平衡了 exploration 与 exploitation**。\n",
"- Upper-Confidence Bound（简称 UCB，上限置信区间算法）。该算法相对比较复杂， 且只适用于 Multi-arm Bandit 问题，对别的强化学习问题并没有显著帮助。\n",
" - M -> Motivation：为什么要发明这个算法？ \n",
" ε 贪心算法以 ε 概率随机选择一个非最佳的 action 来进行探索。问题在于，很可能一台老虎机你已经试了 1000 次，但另一台你只试了 50 次。从统计上说，试验次数越多，得到价值估计就越准确；反之，试验次数越少，价值估计的不确定性就越大。但 ε 贪心算法完全没有考虑这一点，它只会不顾任何情况地**随机试验**。\n",
" - IN -> Intuition：解决这个问题的直观思路是什么？ \n",
" Upper-Confidence Bound 的中心思想，就是把上文提到的不确定性纳入探索过程，根据一个数学公式调整 Q 值的相对大小对最终决策的影响。校正过 Q 值之后，下一步的 action 就由**纯贪心（简单的取最大值）**来决定。\n",
" - T -> Technicality：\n",
" - Q\\_t(a) 是原本未校正的 Q 值估计\n",
" - t 是目前总共试验次数\n",
" - N\\_t(a) 是尝试某一个老虎机 a 的次数\n",
" - c 是超参数，控制探索与开拓的平衡，平方根可以直观认为是某 action 的标准差\n",
" \n",
" 其中，第二项分母 N\\_t(a)，即某个 action 的实验次数越大，表达式的值就越小，意味着 argmax 越不容易选择这个 action。换言之，当尝试某个 action 次数越多，那么 Confidence（置信度）就越高，自然不需要更多的探索。 \n",
" 第二项分子中 t 越大，表达式的值也越大，argmax 更可能探索这个 action。直观的说，两个赌场里，假设 ③ 号老虎机的试验次数都是 1000 次（即 N\\_t(③) = 1000）。如果第一个赌场的总次数是 100 万次，第二个赌场的总次数是 2000 次，则对 ③ 号老虎机的相对置信度是第一个赌场更低。 \n",
" 当 c 越大，第二项的值也越大，意味着我们越多地做探索。当 c = 0，此式等价于未校正过的 Q\\_t(a)，UCB 算法退化为简单的纯贪心算法，相当于没有任何探索成分。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 小结1\n",
"\n",
"\n",
"- 乐观探索法第四步开始依然执行同样的策略与初始值取平均，还是所有值取平均，还是与最近一次的值取平均，还是用非静态的方法求解，还是其他方法…… \n",
"- UCB 算法中，t 是总的可试验次数还是截止当前 action 已试验次数，直觉上好像都可以。 而且 UCB 是不是也可以用非静态的方法求解 Q，或者用乐观探索法求解 Q……有没有把所有方法综合起来的……\n",
"\n",
"其实，关键就集中在两个问题上： \n",
"\n",
"- 如何尽量准确估计 Q（Q 表格）\n",
" - ε-greedy: 不估计\n",
" - 平均 + greedy，非静态\n",
" - 乐观探索 + greedy\n",
" - UCB + greedy"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 梯度上升\n",
"\n",
"- Motivation\n",
"\n",
" - Implicit Policy（隐性策略）：Q-table 与 ε-Greedy 相结合的方法来选择下一步的决策。此策略是根据 Q-table 推导出，而非以直接形式呈现。\n",
" - Explicit Policy（显性策略）：即每一步都由直接的函数来体现，函数的输出就是选择老虎机的概率分布。π 表示 policy，`π(a)` 是所有 action 的概率分布。 从 explicit policy 的视角，多臂老虎机问题就转化为**学习最佳 π(a)，即策略的概率分布问题**。 \n",
" ```\n",
" 假设现有 10 台老虎机，则 π(1) = 0.1 表示选择第①台老虎机的概率是 10%；π(9) = 0.3 表示第⑨九台老虎机更可能被选择，概率为 30%。```\n",
"\n",
" 皇家赌场里有 10 台老虎机，π(a) 是离散概率，可以由 10 个数表示：`π(a) = [p1, p2, ... p10]`，其中每个数字代表尝试每台老虎机的概率，所有概率相加等于 1。该如何学习组成 `π(a)` 概率分布的 10 个数，使得长远奖励的总和最大化？\n",
"\n",
"- Intuition \n",
" Hill Climbing，选择最陡峭的山坡移动。\n",
"\n",
"- Technicality\n",
"\n",
" - $$H_{t+1}(a) = H_t(a) + \\frac {\\partial \\mathbb{E} [R_t]}{\\partial H_t(a)} \\cdot \\alpha$$\n",
" - a 表示 action\n",
" - `H_t(a)` 表示上一步 “爬山” 的 x，`H_(t+1)(a)` 是爬山之后的 x\n",
" - `E[R_t]` 是奖励期望值 expectation of reward，也就是老虎机的目标函数\n",
" - α 是学习率 Learning rate\n",
" \n",
" - 如何求 `E[R_t]` 关于 `H(a)` 的梯度？\n",
" - 最后目标是为求得 `π(a)`，action probability，有 10 个数，每个数代表每台老虎机被选择概率，相加总和为 1。\n",
" - `H(a)` 中每个数本身的大小并不很重要，加起来也不需要等于 1，但他们的**相对大小**表达了我们策略的偏好。**H(a) 直观可以理解为坐标 x，也就是一种选择，或者选择的结果，其中有 10 个参数，10维，可以转换为 softmax 的概率，也就是最应该选择哪一个老虎机。**\n",
" - 如何把 `H(a)` 转化为 `π(a)`？\n",
" - Softmax：总和为 1，只对相对大小有意义。 \n",
" $$\\pi(a) = \\frac {e^{H(a)}}{\\sum_b e^{H(b)}}$$\n",
" - 目标函数： \n",
" - $$\\mathbb{E}[R_t] = \\sum_b \\pi(b) \\cdot q^*(b)$$\n",
" - `q*` 为每个老虎机真实的长远价值；\n",
" - `π` 为是选择老虎机的概率分布。\n",
" - `E[R_t]` 和 H 值的关系是什么？ \n",
" - $$\\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))$$\n",
" - `q*(b)` 的期望值，即每个 action 的长期价值，在 expectation 上应等于 `R(t)`。\n",
" - 梯度下降\n",
" - $$H_{t+1}(a) = H_t(a) + \\alpha \\cdot R_t \\cdot (\\mathbb{1}_{a=A_t} - \\pi_t(a))$$\n",
" - $$H_{t+1}(a) = H_t(a) + \\alpha \\cdot R_t \\cdot (1 - \\pi_t(a)) ,\\ \\ a=A_t$$\n",
" - $$H_{t+1}(a) = H_t(a) - \\alpha \\cdot R_t \\cdot \\pi_t(a) ,\\ \\ a \\ne A_t$$\n",
" - 当真正采取的 action 是 a 时，indicator 为 1；当 action 没有采用 a 时，indicator 为 0 。\n",
" - 这组方程非常好地印证了之前提到的 Thorndike 效果律 —— **当一个 action 所给出的 reward 始终是正的，那么就多做这个 action，少做别的 action；反之亦然**。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 总结"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 汇总\n",
"\n",
"- ε-greedy: 以 ε 的概率选择一个随机的 action，以 1-ε 的概率选择目前最优的 action。当 ε = 0，为纯贪心算法，也是ε-Greedy 的一种特殊情况。\n",
"- Optimistic Initial Value: 即乐观的 exploration，故意高估初始值，之后无论获得什么奖励，Q 值总是下降，用这种方法来鼓励你更多地探索没有尝试过的选项。\n",
"- Upper Confidence Bound: 其中心思想是，不断地调整你对每个 action 的 confidence。如果你对一个 action 的长远价值越不确定，你就应该更多地尝试这个 action；如果你对其价值已很确定，就不需再浪费时间试验这个 action。\n",
"- Bandit Gradient: 以全新的视角来学习 Explicit Policy（显性策略）的 π(a)。π 是关于每个 action 的概率分布。我们用梯度上升（Gradient Acsent）的方法来学习π这个参数，求的是最后的目标函数，即 R 的期望值。\n",
"\n",
"\n",
"\n",
"1. 红线 ε：指ε-greedy 的超参数，需要手动设置。当ε = 1/16，即 5%~6% 之间的 exploration，ε-greedy 获得的分数最好。 \n",
"极端情况下，如果 explore 了太多，比如当ε = 1/4，意味着 25% 的时间都在做随机决定，并不妥善；如果 explore 太少，就成了贪心算法，也是非最佳状态。\n",
"\n",
"2. 黑线 Q\\_0：指 Optimistic Initialization 的超参数，即最初的取值。同样，Q\\_0 不可太大也不可太小。当 Q\\_0 = 1，取得最大奖励值；当 Q\\_0 很大，过于乐观，那么大部分时间都在 explore，浪费精力；当 Q\\_0 很小，不够乐观，也对获得理想奖励值无益。\n",
"\n",
"3. 蓝线 c：指 UCB(Upper Confidence Bound) 算法的超参数 confidence。同样，c 越大，意味着做越多 exploration。图中可见，随着 c 的增大，UCB 最后获得的奖励退步很明显。当 c = 0，UCB 与贪心算法等价。 \n",
"\n",
"4. 绿线 α：指 Gradient Bandit 的超参数，即 step size，或 learning rate。\n",
"α与 exploration 和 exploitation 的关系并没这么明显，α控制的是梯度上升的速率。如果α过大，会造成数值不稳定，偏移你的本来目标；但如果α过小，学习的速率就会太慢。\n",
"因为 Gradient Bandit 的 explicit policy 是一个概率分布，所以，在做下一步决策时，本身就是随机采样。从这种意义上，explicit policy 是自带 exploration 的。\n",
"\n",
"\n",
"## Gittins Index\n",
"\n",
"Gittins Index: **通过计算一个复杂函数，把在每一步取到最大值的 x，作为这一步采取的 action**。Gittins 算法不仅比 UCB 更好，而且还可被在数学上证明是多臂老虎机的最优解。其大概基于的原理是：用贝叶斯统计来计算出一个最优的 exploration 和 exploitation 的平衡。一般情况下，这个平衡点无法被计算出，但是因为多臂老虎机过于简单，所以 Gittins Index 足够解决这个问题。但是，任何更复杂的问题，都没有 Gittins Index 的用武之地。\n",
"\n",
"## Missing\n",
"\n",
"- Stateless: 多臂老虎机是一个 Stateless，即没有状态的问题。比如，今天拉了第③号老虎机，到了第二天，别的老虎机并不会因为你昨天的行为而改变今天奖励的概率。\n",
"- Credit assignment: 因为没有状态，所以不存在 credit assignment 的问题。这是继 Exploration 和 Exploitation 之后，第二个强化学习的心脏问题。（每一步对最后获得奖励的贡献不同）**理清楚每一步决定对最后奖励的贡献，就是 Credit assignment 的核心**。"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.2"
},
"toc": {
"colors": {
"hover_highlight": "#DAA520",
"running_highlight": "#FF0000",
"selected_highlight": "#FFD700"
},
"moveMenuLeft": true,
"nav_menu": {
"height": "66px",
"width": "252px"
},
"navigate_menu": true,
"number_sections": true,
"sideBar": true,
"threshold": 4,
"toc_cell": true,
"toc_section_display": "block",
"toc_window_display": true
}
},
"nbformat": 4,
"nbformat_minor": 2
}