跳到主要内容

老虎机 — 只靠评分学习,第一步怎么走

这一章讲三件事: 「行动值」这个概念和估计它的最朴素办法; 为什么「永远选当前最好」会卡死,几种简单平衡术各自怎么破局; 以及一个将来处处出现的更新模板。 读完你会明白,探索不是玄学,是一组可以挑着用的具体手段。

1. 问题设定:十个拉杆,只能瞎蒙着试​

k 臂赌博机问题:你面前有 k 个拉杆(原型是只有一根杆的老虎机,这里是 k 根),每拉一次,机器从一个概率分布(各种结果各占多少机会的一张清单)里抽一个数给你——这个数就是奖励,拉哪个杆、这份清单就跟着换成哪份。连拉 1000 次,让总奖励尽量多1。

每个拉杆有个真值:拉它的奖励的平均数,记作 q*(a)。如果一开始就告诉你十个真值,问题毫无难度——永远拉最大的那个。难就难在没人告诉你,你手上只有自己的估计 Q(a),它随你试拉的经验不断修正2。

于是每个时刻只有两种选择:

  • 挑估计值最高的拉——利用(exploit),赚眼前的;
  • 挑别的拉——探索(explore),花点成本换情报。

书里把话说得很直白:单独哪一种都不行,只利用会错过其实更好的拉杆,只探索永远攒不下收益;通常人们干脆把这叫「探索与利用的冲突」3。而作者对本章的定位更低调也更诚实:他不去追求精巧的最优平衡(那些理论的保证依赖现实中验证不了的假设),只求「有平衡」——并证明这么朴素的做法,就已经远胜从不探索4。

2. 顶层全景:先估计,再带随机性地选​

   经验(拉了哪根、得了几分)
        │  样本平均:把该拉杆历次得分求平均
        ▼
   估计值 Q(a) ──▶ 选举:大多挑 Q 最高的,小概率随机
        ▲                                      │
        └────────── 新的奖励 ◀── 环境 ──────────┘

   图说:估计和选择咬合成一个环;探索就是往「选」这一环里掺随机。

3. 核心原理一:ε-greedy,以及那个卡死的贪婪​

最朴素的选举规则是贪婪:永远挑 Q 最大的拉杆。它的病,书里用一组实验钉死了——10 臂试验台:2000 个随机生成的十臂问题,每臂真值从均值 0、方差 1 的正态分布抽;每次拉杆的奖励再从以该臂真值为均值、方差 1 的正态分布抽;每个问题拉 1000 步,取 2000 次的平均5。

ε-greedy 在贪婪上加一味药:以小概率 ε(比如 0.1)不看估计、均匀随机拉一根6。看试验台上的成绩(下面的数全部来自书里的实验,不是演示值):

方法长期每步奖励备注
可能的最好约 1.54十个真值里最大的那个
贪婪(ε=0)约 1起步快,早早躺平
ε=0.1更接近 1.54选择最优动作的比例封顶在 91%
ε=0.01慢,但最终反超 0.1探索少,犯错也少

贪婪为什么烂?在约三分之二的任务里,它第一次试到最优拉杆时手气太差,从此再没回去过7。它不是不努力,是信息结构坑了它:估计只来自亲身经验,没试够就下结论,结论错了还自我加固。

ε-greedy 的代价也写在表里:哪怕学会之后,它仍按 ε 的比例乱拉,所以成绩封顶在 1−ε≈91%。所以存在一个反直觉的次序:ε 大的先上去、ε 小的后到但走得远。作者补了一句要紧的限定——ε-greedy 的好处依赖任务:奖励噪声(同一拉杆得分的抖动)越大它越占便宜;若奖励毫无噪声,贪婪试一次就知道答案,可能反而最好;但只要任务会变(非平稳),哪怕无噪声也必须探索——不然别的拉杆变好了你永远不知道8。而非平稳,恰恰是强化学习最常见的情形。

4. 核心原理二:增量更新——全书共用的模板​

估计怎么算?最自然的是样本平均:把某拉杆历次得分加起来除以次数。但每次都重算全部历史太浪费。书里给出增量式:来第 n 次奖励 R(n) 时,旧的估计 Q(n) 只需挪一小步9:

  Q(n+1) ← Q(n) + (1/n) · [ R(n) − Q(n) ]

  演示(数值为演示编的):某拉杆已拉 4 次,平均 3.0;第 5 次得了 7。
  Q(6) = 3.0 + (1/5) × (7 − 3.0) = 3.0 + 0.8 = 3.8
  验算:(3+3+2+4+7)/5 = 19/5 = 3.8 ✓

作者随即把这个式子抽象成全书所有学习算法共用的形状10:

新估计 ← 旧估计 + 步长 ×(目标 − 旧估计)

「目标」是本次经验给出的、更好的那个数;「目标 − 旧估计」是估计误差;每次朝目标挪一小步。第 06 章的时间差分、后面的 Sarsa、Q-learning,全是往这个模板里换不同的「目标」。

5. 核心原理三:任务会变,就得「偏心」最近的经验​

样本平均对所有历史一视同仁,这在会变的任务上是坏事——十年前的情报早过期了。办法是把步长换成固定的 α,比如 0.1:新奖励的权重(在加权平均里占的份额)永远是 0.1,越老的奖励这份份额按 (1−α) 逐年连乘衰减——学名叫近因加权平均(老情报的分量按固定比例逐次缩水)11。

代价是数学上的:固定 α 不满足随机逼近的收敛条件,估计永远不完全收敛,会一直随最近的奖励抖动。作者的态度很鲜明:这在非平稳环境里恰恰是想要的——收敛了才糟糕;而且满足收敛条件的步长序列(一串预设的步长)往往慢得没法用,理论里常见、实践里少用12。

6. 其余三种平衡术,各一句话​

乐观初值。 把所有初始估计故意设成大得离谱的数(真值均值 0,初值给 +5)。于是每个拉杆第一次被拉都「令人失望」,贪婪程序也被赶着去试下一个,实际上靠失望实现了探索。作者评价:平稳问题上是个好用的简单技巧,但对非平稳无效——探索的劲头是暂时的,任务一变它就没了;他还有句格言式的话:「时间的开端只发生一次,不该在它身上放太多心思」13。

UCB(置信上界)。 ε-greedy 的随机探索不看对象——快要把估计值试熟的冷门拉杆和从没试过的拉杆一视同仁。UCB 改成确定性偏心:给每个拉杆的估计加一项「不确定度补贴」√(ln t / N(a))(N(a) 是它被拉的次数,越小补贴越大;分母里的 ln t 让补贴随时间整体缩水但仍不为零),选加了补贴后最大的14。直观读法:久未试过的、没试过的,优先。试验台上 UCB 整体比 ε-greedy 好,但作者提醒:它比 ε-greedy 难推广到完整强化学习——非平稳和大状态空间(状态多到没法逐一存放)两关都难过15。

梯度赌博机。 干脆不估「值」,改学每个拉杆一个偏好数 H(a):偏好经 soft-max(把一组数变成一组加起来等于 1 的概率)变成选择概率。每次拉完,拉中的那根,偏好朝「奖励高于平均多少」的方向加,其余朝反方向减16。这里藏着本章埋得最深的一招——基线(baseline):更新里减掉的那个「平均奖励」。把所有奖励整体抬高 4 个点,带基线的算法毫无感觉,去掉基线则显著变差;而且数学上基线怎么选都不影响更新的期望,只影响方差——选「奖励的平均值」简单好用17。这一节是第 13 章策略梯度的单状态预演,书里自己承认的18。

跨出单局面。 如果拉杆机每隔几步换一台,但每次给你个提示(比如机器换了颜色),那就得学「什么颜色拉哪根」——关联搜索(associative search,文献里也叫 contextual bandit)。它开始像完整的强化学习(要学局面到动作的映射),但动作还只影响眼前奖励;一旦动作开始影响下一个局面,就是第 03 章的完整问题19。

7. 作者的判断与证据​

有实验的: 10 臂试验台上贪婪只在约 1/3 的任务找到最优动作、ε=0.1 封顶 91%、最优约 1.54,都是 2000 次重复实验的平均值57;UCB 与梯度法在同一试验台的对比、参数研究里所有算法都呈「倒 U」形(参数太小不行、太大也不行)同样是实验结论20。

作者的立场: 「本章这些简单方法,可以公平地认为是(就完整强化学习可用的方法而言)最好水平」——作者明说这是他的看法(opinion),更精巧的方法被复杂性和假设拖累,搬不进完整问题21。

至于探索问题本身,书里点名三条更精细的路,但都只提名不展开:Gittins 指数(给每个拉杆算一个「值得一试度」的经典公式)。

Thompson 采样(按当前胜率抽着选)是一路。

贝叶斯(把未知当成一整张可能性清单来推断的数学流派)精确最优是另一路——展开来是一棵 2^2000 片叶子的树,算不动22。

8. 边界与局限​

  • 本章的问题没有局面:不管面对的是什么,只有拉哪个的选择。一旦「不同局面不同最佳动作」,就是下一章的事19。
  • 假设奖励分布平稳(或缓变)。突变的任务本章方法只能迟钝追赶8。
  • UCB 与乐观初值的推导都依赖「每个动作独立、奖励有界」这类良性质;完整 RL 里它们通常只剩思想,不剩公式15。
  • 最优探索没有免费午餐:要么接受 ε 的永久浪费,要么接受估计永不收敛的抖动——两样都是换取适应性付的租12。

9. 可带走的​

  1. 真值 vs 估计:每个动作都有个平均回报(真值),你永远只掌握估计;学习=把估计往真值凑。
  2. 贪婪死于自证:早期手气差的最优动作可能永远沉底(2/3 的任务如此);探索是对「我的估计可能错」买的保险。
  3. 新估计 ← 旧估计 + 步长 ×(目标 − 旧估计):全书一切更新规则的模板,记住它,后面每章都眼熟。
  4. 任务会变就别平均太久的历史:固定步长=偏心新情报;估计永不收敛在变化的世界里是优点不是缺点。
  5. 乐观初值:让每个选项第一次都「令人失望」,失望逼出探索;但只管开局,不管变局。
  6. UCB 的口诀:谁最少被试、谁久未被试,就补贴谁;比乱探索聪明,但难搬家到完整问题。
  7. 基线思维:和「平均水准」比,而不是和零比;基线不影响学什么,只影响学多稳。
  8. 探索-利用两难没有已知的完美解;工程上挑简单的够用,并保持对参数的敏感(倒 U 形)。

10. 原文地图​

主题原书章原文位置
评估性反馈 vs 指导性反馈Multi-armed Banditstext/05-fm-multi-armed-bandits.txt:4(搜「evaluates the actions」)
k 臂问题设定、真值与估计Multi-armed Banditstext/05-fm-multi-armed-bandits.txt:29(搜「stationary probability distribution」) · text/05-fm-multi-armed-bandits.txt:42(搜「expected or mean reward」)
利用/探索、冲突Multi-armed Banditstext/05-fm-multi-armed-bandits.txt:55(搜「greedy actions」) · text/05-fm-multi-armed-bandits.txt:69(搜「conflict」)
只求平衡不求精巧Multi-armed Banditstext/05-fm-multi-armed-bandits.txt:83(搜「worry only about balancing」)
样本平均、ε-greedyMulti-armed Banditstext/05-fm-multi-armed-bandits.txt:105(搜「sample-average」) · text/05-fm-multi-armed-bandits.txt:124(搜「-greedy methods」)
10 臂试验台Multi-armed Banditstext/05-fm-multi-armed-bandits.txt:134(搜「10-armed testbed」)
贪婪 1 vs 1.54、三分之一、91%Multi-armed Banditstext/05-fm-multi-armed-bandits.txt:180(搜「1.54」) · text/05-fm-multi-armed-bandits.txt:213(搜「one-third」) · text/05-fm-multi-armed-bandits.txt:218(搜「91%」)
任务依赖与非平稳Multi-armed Banditstext/05-fm-multi-armed-bandits.txt:222(搜「depends on the task」) · text/05-fm-multi-armed-bandits.txt:230(搜「nonstationary」)
增量式与一般形状Multi-armed Banditstext/05-fm-multi-armed-bandits.txt:296(搜「holds even for」) · text/05-fm-multi-armed-bandits.txt:302(搜「NewEstimate」)
指数近因加权、永不收敛Multi-armed Banditstext/05-fm-multi-armed-bandits.txt:480(搜「exponential recency-weighted」) · text/05-fm-multi-armed-bandits.txt:381(搜「never completely converge」)
乐观初值、时间开端Multi-armed Banditstext/05-fm-multi-armed-bandits.txt:424(搜「optimistic initial values」) · text/05-fm-multi-armed-bandits.txt:456(搜「beginning of time」)
UCB 公式与难推广Multi-armed Banditstext/05-fm-multi-armed-bandits.txt:493(搜「ln t」) · text/05-fm-multi-armed-bandits.txt:513(搜「more difficult」)
梯度赌博机、基线、+4Multi-armed Banditstext/05-fm-multi-armed-bandits.txt:544(搜「preference」) · text/05-fm-multi-armed-bandits.txt:575(搜「baseline」) · text/05-fm-multi-armed-bandits.txt:581(搜「+4」)
关联搜索Multi-armed Banditstext/05-fm-multi-armed-bandits.txt:768(搜「associative search」)
倒 U、作者自认最好水平、GittinsMulti-armed Banditstext/05-fm-multi-armed-bandits.txt:810(搜「inverted-U」) · text/05-fm-multi-armed-bandits.txt:836(搜「state of the art」) · text/05-fm-multi-armed-bandits.txt:845(搜「Gittins index」)

Footnotes​

  1. 出处:「Multi-armed Bandits」第 29 段(text/05-fm-multi-armed-bandits.txt:29,搜「stationary probability distribution」)。原文设定连做 1000 次选择;医生在病人身上试验疗法的比喻在第 37 段(搜「experimental treatments」)。 ↩

  2. 出处:「Multi-armed Bandits」第 42 段(text/05-fm-multi-armed-bandits.txt:42,搜「expected or mean reward」)与第 52 段(text/05-fm-multi-armed-bandits.txt:52,搜「estimated value」)。 ↩

  3. 出处:「Multi-armed Bandits」第 69 段(text/05-fm-multi-armed-bandits.txt:69,搜「conflict」)。 ↩

  4. 出处:「Multi-armed Bandits」第 83 段(text/05-fm-multi-armed-bandits.txt:83,搜「worry only about balancing」);复杂方法假设靠不住的批评在第 77 段(搜「stationarity」)。 ↩

  5. 出处:「Multi-armed Bandits」第 134 段(text/05-fm-multi-armed-bandits.txt:134,搜「10-armed testbed」)。 ↩ ↩2

  6. 出处:「Multi-armed Bandits」第 124 段(text/05-fm-multi-armed-bandits.txt:124,搜「-greedy methods」)。 ↩

  7. 出处:「Multi-armed Bandits」第 213 段(text/05-fm-multi-armed-bandits.txt:213,搜「one-third」);1.54 与 1 的对比在第 180 段(text/05-fm-multi-armed-bandits.txt:180,搜「1.54」);91% 在第 218 段(搜「91%」)。 ↩ ↩2

  8. 出处:「Multi-armed Bandits」第 222 段(text/05-fm-multi-armed-bandits.txt:222,搜「depends on the task」)与第 230 段(text/05-fm-multi-armed-bandits.txt:230,搜「nonstationary」);「非平稳是强化学习最常见情形」在第 234 段(搜「most commonly encountered」)。 ↩ ↩2

  9. 出处:「Multi-armed Bandits」第 308 段(text/05-fm-multi-armed-bandits.txt:308,搜「step-size parameter」)。 ↩

  10. 出处:「Multi-armed Bandits」第 302 段(text/05-fm-multi-armed-bandits.txt:302,搜「NewEstimate」)。原文:「This update rule (2.3) is of a form that occurs frequently throughout this book」(第 299 段,搜「occurs frequently」)。 ↩

  11. 出处:「Multi-armed Bandits」第 480 段(text/05-fm-multi-armed-bandits.txt:480,搜「exponential recency-weighted」)。 ↩

  12. 出处:「Multi-armed Bandits」第 381 段(text/05-fm-multi-armed-bandits.txt:381,搜「never completely converge」)与第 385 段(text/05-fm-multi-armed-bandits.txt:385,搜「very slowly」)。 ↩ ↩2

  13. 出处:「Multi-armed Bandits」第 424 段(text/05-fm-multi-armed-bandits.txt:424,搜「optimistic initial values」)与第 456 段(text/05-fm-multi-armed-bandits.txt:456,搜「beginning of time」);不适合非平稳的批评在第 426 段(搜「inherently」)。 ↩

  14. 出处:「Multi-armed Bandits」第 493 段(text/05-fm-multi-armed-bandits.txt:493,搜「ln t」);不确定度的解读在第 501 段(搜「uncertainty or variance」)。 ↩

  15. 出处:「Multi-armed Bandits」第 513 段(text/05-fm-multi-armed-bandits.txt:513,搜「more difficult」)。 ↩ ↩2

  16. 出处:「Multi-armed Bandits」第 544 段(text/05-fm-multi-armed-bandits.txt:544,搜「preference」)与第 549 段(搜「soft-max」)。 ↩

  17. 出处:「Multi-armed Bandits」第 575 段(text/05-fm-multi-armed-bandits.txt:575,搜「baseline」)与第 583 段(搜「significantly degraded」);基线不影响期望只影响方差见边栏第 740 段(搜「does not affect the expected update」)。 ↩

  18. 出处:「Multi-armed Bandits」第 915 段(text/05-fm-multi-armed-bandits.txt:915,搜「Williams」)。梯度赌博机是 Williams 1992 年策略梯度算法的特例。 ↩

  19. 出处:「Multi-armed Bandits」第 768 段(text/05-fm-multi-armed-bandits.txt:768,搜「associative search」)与第 775 段(搜「full reinforcement learning problem」)。 ↩ ↩2

  20. 出处:「Multi-armed Bandits」第 810 段(text/05-fm-multi-armed-bandits.txt:810,搜「inverted-U」);UCB 在此题上最好见第 834 段(搜「UCB seems to perform best」)。 ↩

  21. 出处:「Multi-armed Bandits」第 836 段(text/05-fm-multi-armed-bandits.txt:836,搜「state of the art」)。 ↩

  22. 出处:「Multi-armed Bandits」第 867 段(text/05-fm-multi-armed-bandits.txt:867,搜「22000」)。原文排版把 2^2000 印成了「22000」;Gittins index 在第 845 段(搜「Gittins index」),Thompson 采样在第 856 段(搜「Thompson sampling」)。 ↩