试错学习 — 这本书研究的问题到底是什么

这一章讲三件事: 强化学习与「监督、无监督」两条老路的分界线在哪; 它的系统由哪四个零件组成、各自管什么;以及用一个井字棋程序把「从互动里学」这件事完整走一遍。 读完你会拿到全书的第一张地图——后面十五章都在往这张地图上填东西。 不需要任何基础,遇到的生词都在当场解释。

1. 先看现象:没人给它标准答案,它要自己试

小孩学走路,没有人给他一本《走路原理》,他是摔出来的。这本书开篇就认这个理: 从互动中学习,几乎是所有学习和智能理论共同的地基¹。

但「从互动中学」具体指什么?先看它不是什么。

我们熟悉的那种学习方式(行业里叫监督学习)是这样的:给他看成千上万张标好答案的图片——这张是猫、那张是狗——他学会的是「照着标好的答案模仿」。监督学习里永远站着一个知道正确答案的老师²。

强化学习的处境完全不同。没有人告诉他此刻正确的动作是什么。 他能得到的只有一件事后的评分:这一步走完,结果好了一点还是坏了一点。书里给这类反馈起了个名字,叫评估性反馈(evaluative feedback)——它只评价你刚才那个动作好不好,不说正确动作是什么³。

这两者的差别,拿学下棋来说最清楚:

	监督学习	强化学习
拿到什么	「这个局面应该走马」	走完之后:赢了(+1)或输了(−1)
谁说的算	老师给的正确答案	只看结果评分
难在哪	模仿得像不像	不知道哪个动作才是对的,只能试

所以本书给强化学习下的定义是:学习「该做什么」——把局面映射(一一对应)到动作——以最大化一个数值奖励信号。学习者不会被告知该选哪些动作,必须自己试出来哪些动作带来最多奖励⁴。

2. 两个别人没有的麻烦

定义里藏着全书要对付的两件事。作者明说,这两点是强化学习最重要的标志⁵:

麻烦一:只能试错。 哪个动作好,事先不知道,唯一办法是把它做出来看结果。这就产生了一个别的学习方式里根本不存在的问题——探索与利用的两难(exploration–exploitation dilemma):只挑目前已知最好的动作(利用),可能永远发现不了更好的;总去试没试过的动作(探索),眼前又吃亏。作者特意点明,这个两难在监督学习和无监督学习(自己在没答案的数据里找结构)里压根不出现,而它在数学上被研究了几十年,至今没有定论⁶。第 02 章整章都在讲这个问题。

麻烦二:好处晚点到账。 现在走的这步棋,可能几十步之后才决定输赢。评分来得晚,意味着「刚才哪一步立了功」说不清。这个「功劳该记到谁头上」的问题,早在 1961 年就被 Minsky 点名为这类学习的核心难题(信用分配问题,credit-assignment problem)⁷——后文所有算法,某种意义上都是在解它。

顺带把「强化学习」这个词本身说清。作者提醒:这个词同时指三样东西——一个问题、一类解法、一个研究领域。问题和解法必须分开:把两者混为一谈,是这类研究里很多糊涂话的源头⁸。

3. 顶层全景:四个零件

             ┌─────────────────── agent(就是做决定的学习程序)───────────────────┐
             │  策略:局面 → 动作      值函数:这个局面长远看值多少   │
             │  (可选)想象力:猜环境会怎么回应(第 08 章正式讲)                        │
             └──────────┬───────────────────────────▲──────────────┘
                   动作 │                           │ 状态 + 奖励(评分)
                        ▼                           │
             ┌────────────────── 环境(environment)────────────────┐

  图说:智能体(就是那个做决定的学习程序)看局面、出动作;环境回以新局面和一个分数。循环往复。

除了智能体和环境,一个强化学习系统由四个零件组成,前三个必需,第四个可选⁹:

零件	管什么	一句话
策略(policy)	看到局面,选什么动作	行为本身
奖励信号(reward signal)	每一步环境打回来的那个数	定义「好」「坏」
值函数(value function)	这个局面长远看能攒多少奖励	看得远的眼光
模型(model)	猜环境会怎么回应	想象力,可选

四个零件里最要紧的区分是奖励与值的分别。奖励是眼前的快慢,值是长远的好坏——一个局面可能当下不产奖励,但因为它总通向高奖励的局面,值就高。作者用了一个很重的说法:奖励是第一位的,值是第二位的(没有奖励就没有值);但做决策时我们看的是值,不是奖励——找的是长远带来最多奖励的动作。而值没法直接得到,只能从一生的经验里反复估计。所以作者断言:几乎所有强化学习算法最重要的组成部分,就是一个高效估计值的方法;他还说,「以值估计为中心」也许是六十年来人们对强化学习最重要的一条认识¹⁰。

模型的有无也是一条分界线。用模型做规划的方法叫基于模型的方法(model-based),不要模型、直接靠试错学的方法叫无模型方法(model-free)——两者的整合要到第 08 章才完成,这里先记住:本书两种都讲,而且认为它们是同一件事的两个侧面¹¹。

4. 主走查:一个井字棋程序怎么「学会下棋」

  空棋盘 ──对手走──▶ 我方局面 ──我走(照值函数选)──▶ 新局面 ──…──▶ 终局(赢=1 / 输或和=0)
                                  │                        │
                                  └──── 赛后把后面的值往回传 ◀┘

  图说:值函数就是一张表,每个局面格子里存一个数:从这里出发,我赢下来的概率(赢的机会多大)是多少。

作者拿井字棋(tic-tac-toe)做全书第一个完整例子¹²。规则人人都懂,重点看程序怎么做:

第一步,给每个棋盘局面配一个数。 三子连成的局面=1(已经赢了);对手连成或棋盘下满=0;其余局面一律初始化为 0.5,意思是「五五开」¹³。

第二步,下棋时照表选格。 轮到自己时,把每个空格逐一试放,查出落子后局面的数值,通常选数值最高的那格;偶尔不选最高的,随机走一步——这叫探索性走法(exploratory move),专门去看那些平时看不到的局面¹⁴。

第三步,赢完一局回头改表。 对本局中每次「照表走」的落子,把落子前局面的数值,朝落子后局面的数值挪一小步。用书里的记号写出来就是:

  V(S(t)) ← V(S(t)) + α · [ V(S(t+1)) − V(S(t)) ]

  拿一局真下出来的数走一遍(这些数是本例的设定值,书里给的框架,具体数值为演示取的):
  落子前局面值 V(S(t)) = 0.5,落子后局面值 V(S(t+1)) = 0.9,步长 α = 0.1
  更新量 = 0.1 × (0.9 − 0.5) = 0.04
  更新后 V(S(t)) = 0.5 + 0.04 = 0.54   ← 只朝「更准」挪了一小步,不是一步改对

这个更新规则,就是时间差分学习(temporal-difference learning)——名字的来历是:改动量基于两个相继时刻的估计之差(V(S(t+1)) 减 V(S(t)))¹⁵。这是本书的看家算法,第 06 章整章展开;这里只需看见它的两个性质:

• 探索性走法不参与学习。试完就试完了,表不改¹⁶——不然程序会把「乱走」的经验当成常规。
• 步长 α 若随时间减小,表会收敛到真概率;若一直不减到零,程序还能跟上打法会变的对手¹⁷。

这个例子也顺手划清了另一条线。作者拿演化方法(evolutionary methods,如遗传算法(把好策略当物种一样繁衍淘汰)对比:演化方法整体评估一整套策略——固定一套打法打很多局,按胜率淘汰。作者挖苦得很准:它只看每局输赢,赢的那一局里每一步都记功——连没走出来的棋都记功!¹⁸ 而值函数方法能给每个局面单独打分,用上了对局过程中本来就有的信息。所以本书不讨论演化方法¹⁹。

井字棋太小,作者特意预防一个误会:别以为这法子只能玩小棋盘。Tesauro 把同样的算法接上神经网络(模仿脑细胞连成一网的可调函数)下西洋双陆棋,状态数约 10^20 个——一辈子连其中一小部分都见不全——照样学到了超越人类世界冠军的水平²⁰。(靠什么撑过这么大的状态数?函数逼近,第 09 章讲。)

5. 作者的判断与证据

书里给了证据的: 四个零件里「估值为核心」的判断,是作者对六十年领域史的总括,依据是此后各章反复出现的现象——TD 比蒙特卡洛学得快、bootstrap 带来的效率,都在后文有实验(第 06、07 章)。

作者立场、有待检验的: 强化学习是与监督、无监督并列的第三条路²¹——这是本书的立场表述,不是定理。演化方法不擅长这类问题,也是立场:作者自己也承认当策略空间很小或评估便宜时,演化方法可以有效¹⁹。

作者的史学判断: 这个领域的源头是两条独立线索的汇合——一条从动物学习心理学来的试错学习(Thorndike 1911 年的「效果律」:跟着满足感走的反应会被加强²²),一条从最优控制理论来的动态规划(Bellman 1957)。把两条线缝起来的第三条线是时间差分(Samuel 1959 年的跳棋程序最先用上);1989 年 Watkins 的 Q-learning 让三线合流,现代强化学习成型²³。图灵 1948 年就设计过按「快感-疼痛」学习的装置²⁴,MENACE 用火柴盒和彩珠下井字棋²⁵——试错学习的想法比计算机老得多。

6. 边界与局限

• 这本书不管状态信号怎么来。 「局面」长什么样、怎么从传感器数据里造出来,本书几乎不碰(只在第 17 章略提)——不是不重要,而是作者刻意把力气全部押在「给定局面信号之后怎么决策」上²⁶。
• 不管演化方法。 理由见上节,但读者应知道那是取舍不是定论。
• 探索-利用两难只有简单解法。 作者把丑话说在前面:本书不追求精细的平衡,只保证「有平衡」;复杂的理论保证依赖强假设,在实践中靠不住²⁷。
• 连续时间问题不覆盖。 理论更复杂,本书只在结尾声明原理同样适用²⁸。

7. 可带走的

1. 强化学习 = 只拿「事后评分」学习。没有标准答案,答案要靠试。
2. 两大麻烦:只能试错 + 好处晚点到账。全书的每个算法,都是在给这两个麻烦打补丁。
3. 四个零件:策略管行为,奖励定义好坏,值函数管长远,模型管想象(可选)。
4. 决策看值,不看奖励——奖励是老师给的分,值是学生自己攒出来的远见;估好值,是几乎所有算法的真正工作。
5. 井字棋三步:每局面存一个数 → 照数选格(偶尔探索)→ 赛后把后一个数往回传,差多少挪多少。这个「按相邻估计之差学习」的动作,就是全书的心脏:时间差分。
6. 只看最终输赢的方法(演化方法)浪费了过程信息——赢一局不代表每步都对。
7. 探索与利用的平衡至今没有数学定论;先记住问题,解法从下一章开始。

8. 原文地图

主题	原书章	原文位置
定义、两大特征	Introduction	text/04-fm-introduction.txt:25(搜「map situations to actions」) · text/04-fm-introduction.txt:30(搜「delayed reward」)
与监督/无监督之分、第三范式	Introduction	text/04-fm-introduction.txt:49(搜「supervised learning」) · text/04-fm-introduction.txt:70(搜「third machine learning paradigm」)
探索-利用两难无定论	Introduction	text/04-fm-introduction.txt:75(搜「exploration and exploitation」)
四要素、值比奖励难估	Introduction	text/04-fm-introduction.txt:209(搜「four main subelements」) · text/04-fm-introduction.txt:253(搜「efficiently estimating values」) · text/04-fm-introduction.txt:255(搜「six decades」)
模型与规划	Introduction	text/04-fm-introduction.txt:263(搜「model-based methods」)
不管状态信号、排除演化方法	Introduction	text/04-fm-introduction.txt:279(搜「constructing」) · text/04-fm-introduction.txt:291(搜「evolutionary methods」)
井字棋:0.5 初始化、探索步、更新式	Introduction	text/04-fm-introduction.txt:364(搜「50% chance」) · text/04-fm-introduction.txt:370(搜「exploratory moves」) · text/04-fm-introduction.txt:417(搜「step-size parameter」) · text/04-fm-introduction.txt:418(搜「temporal-difference」)
探索步不学习;α 收敛性质	Introduction	text/04-fm-introduction.txt:409(搜「do not result in any learning」) · text/04-fm-introduction.txt:422(搜「reduced properly」)
对比演化方法;无模型实现计划效果	Introduction	text/04-fm-introduction.txt:439(搜「never occurred」) · text/04-fm-introduction.txt:449(搜「planning and lookahead」)
双陆棋 10^20 状态	Introduction	text/04-fm-introduction.txt:467(搜「1020」)
历史两主线;效果律;图灵	Introduction	text/04-fm-introduction.txt:550(搜「two main threads」) · text/04-fm-introduction.txt:641(搜「Law of Effect」) · text/04-fm-introduction.txt:664(搜「pleasure-pain」)
Minsky 信用分配;MENACE;三线合流;多巴胺	Introduction	text/04-fm-introduction.txt:711(搜「credit-assignment」) · text/04-fm-introduction.txt:732(搜「MENACE」) · text/04-fm-introduction.txt:892(搜「Watkins」) · text/04-fm-introduction.txt:904(搜「dopamine」)

Footnotes

1. 出处:「Introduction」第 12 段(text/04-fm-introduction.txt:12,搜「foundational idea」)。原文说从互动中学习是「nearly all theories of learning and intelligence」的共同基础。 ↩

2. 出处:「Introduction」第 51 段(text/04-fm-introduction.txt:51,搜「external supervisor」)。原文定义监督学习为「learning from a training set of labeled examples provided by a knowledgable external supervisor」。 ↩

3. 出处:「Multi-armed Bandits」第 4 段(text/05-fm-multi-armed-bandits.txt:4,搜「evaluates the actions」)。原文:「training information that evaluates the actions taken rather than instructs by giving correct actions」——这是作者给出的、RL 与其他学习最重要的分界。 ↩

4. 出处:「Introduction」第 25 段(text/04-fm-introduction.txt:25,搜「map situations to actions」)。 ↩

5. 出处:「Introduction」第 30 段(text/04-fm-introduction.txt:30,搜「delayed reward」)。原文称这两点为「the two most important distinguishing features」。 ↩

6. 出处:「Introduction」第 75 段(text/04-fm-introduction.txt:75,搜「exploration and exploitation」)与第 85 段(text/04-fm-introduction.txt:85,搜「remains unresolved」)。「在监督/无监督里不出现」见第 86 段(text/04-fm-introduction.txt:86,搜「does not even arise」)。 ↩

7. 出处:「Introduction」第 711 段(text/04-fm-introduction.txt:711,搜「credit-assignment」)。Minsky 1961 年「Steps Toward Artificial Intelligence」一文的提法;作者补了一句:本书讲的所有方法,某种意义上都指向这个问题(第 713 段,搜「all of the methods」)。 ↩

8. 出处:「Introduction」第 33 段(text/04-fm-introduction.txt:33,搜「mountaineering」)。原文用 machine learning 与 mountaineering 这类以 -ing 结尾的词类比。 ↩

9. 出处:「Introduction」第 209 段(text/04-fm-introduction.txt:209,搜「four main subelements」)。 ↩

10. 出处:「Introduction」第 241 段(text/04-fm-introduction.txt:241,搜「primary」)与第 253 段(text/04-fm-introduction.txt:253,搜「efficiently estimating values」);「六十年」一句在第 255 段(text/04-fm-introduction.txt:255,搜「six decades」)。 ↩

11. 出处:「Introduction」第 263 段(text/04-fm-introduction.txt:263,搜「model-based methods」)。 ↩

12. 出处:「Introduction」第 311 段(text/04-fm-introduction.txt:311,搜「tic-tac-toe」)。 ↩

13. 出处:「Introduction」第 364 段(text/04-fm-introduction.txt:364,搜「50% chance」)。 ↩

14. 出处:「Introduction」第 370 段(text/04-fm-introduction.txt:370,搜「exploratory moves」)。原文:greedy 之外「occasionally, however, we select randomly from among the other moves」。 ↩

15. 出处:「Introduction」第 418 段(text/04-fm-introduction.txt:418,搜「temporal-difference」)。更新式在第 417 段(text/04-fm-introduction.txt:417,搜「step-size parameter」)。 ↩

16. 出处:「Introduction」第 409 段(text/04-fm-introduction.txt:409,搜「do not result in any learning」)。这是图 1.1 图注里的话。 ↩

17. 出处:「Introduction」第 422 段(text/04-fm-introduction.txt:422,搜「reduced properly」)与第 428 段(text/04-fm-introduction.txt:428,搜「slowly change」)。 ↩

18. 出处:「Introduction」第 439 段(text/04-fm-introduction.txt:439,搜「never occurred」)。 ↩

19. 出处:「Introduction」第 287 段(text/04-fm-introduction.txt:287,搜「genetic algorithms」)与第 307 段(text/04-fm-introduction.txt:307,搜「do not consider evolutionary」)。承认演化方法在特定条件下有效的段落见第 296 段(text/04-fm-introduction.txt:296,搜「can be effective」)。 ↩ ↩²

20. 出处:「Introduction」第 467 段(text/04-fm-introduction.txt:467,搜「1020」)与第 470 段(text/04-fm-introduction.txt:470,搜「world's best human players」)。Tesauro 1992/1995,即 TD-Gammon,第 16 章有专节。 ↩

21. 出处:「Introduction」第 70 段(text/04-fm-introduction.txt:70,搜「third machine learning paradigm」)。 ↩

22. 出处:「Introduction」第 641 段(text/04-fm-introduction.txt:641,搜「Law of Effect」)。Thorndike 1911 原文引用在第 633-640 段。 ↩

23. 出处:「Introduction」第 550 段(text/04-fm-introduction.txt:550,搜「two main threads」)、第 837 段(text/04-fm-introduction.txt:837,搜「Samuel」)、第 892 段(text/04-fm-introduction.txt:892,搜「Watkins」)。原文说三线「came together in the late 1980s」在第 559 段(搜「late 1980s」)。 ↩

24. 出处:「Introduction」第 664 段(text/04-fm-introduction.txt:664,搜「pleasure-pain」)。图灵 1948 年报告「pleasure-pain system」:痛觉刺激到来时撤销一切试验性配置,快感刺激到来时全部固定。 ↩

25. 出处:「Introduction」第 732 段(text/04-fm-introduction.txt:732,搜「MENACE」)。每个局面一个火柴盒,盒里彩色珠子对应各走法;赢了往盒里加珠、输了减珠。 ↩

26. 出处:「Introduction」第 279 段(text/04-fm-introduction.txt:279,搜「constructing」)。原文:「We do not address the issues of constructing, changing, or learning the state signal in this book」。 ↩

27. 出处:「Multi-armed Bandits」第 83 段(text/05-fm-multi-armed-bandits.txt:83,搜「worry only about balancing」)与第 80 段(text/05-fm-multi-armed-bandits.txt:80,搜「little comfort」)。 ↩

28. 出处:「Introduction」第 462 段(text/04-fm-introduction.txt:462,搜「continuous-time」)。 ↩