跳到主要内容

通读笔记( reinforcement-learning-sutton-barto )

引用格式备忘:「章名」第 N 段 (text/NN-xxx.txt:N,搜「真实短语」)。行号以磁盘清洗文本为准。

文件 01-02 前言(两版)​

  • 二版前言:1998 出一版;2012 开始写二版(text/01:8,搜「2012」);目标不变「clear and simple account」(text/01:10);二版约为初版两倍大(text/01:62,搜「twice as large」);选材反映「long-standing interests in inexpensive model-free methods」(text/01:60,搜「inexpensive」);Sutton 感谢 DeepMind「support in the last six months of writing」(text/01:168,搜「DeepMind」)。
  • 三部分结构:第一部分 tabular(2–8 章)、第二部分 function approximation(9–13 章)、第三部分心理/神经/案例/前沿(14–17 章)(text/01:42-58,搜「tabular case」)。
  • Klopf 故事:二版前言 91-122 行;Klopf 主张「systems that try to maximize something ... qualitatively different from equilibrium-seeking」(text/01:100,搜「maximize something」);Sutton Stanford 本科与 Harry 通信、后成 Barto 的 UMass 博士生(text/01:110-114,搜「corresponding with Harry」)。
  • 一版前言:1979 年底开始关注 RL(text/02:3,搜「late 1979」);「a learning system that wants something」(text/02:13,搜「wants something」);不做定理-证明式处理(text/02:45-47,搜「theorem」)。

文件 04 = 原书第 1 章 Introduction​

  • RL 定义:learning what to do—how to map situations to actions—to maximize a numerical reward signal;text/04:25-26,搜「map situations to actions」。两大特征:trial-and-error search + delayed reward(text/04:29-31,搜「delayed reward」)。
  • RL = problem + methods + field 三个东西共用一个名(text/04:32-34,搜「mountaineering」)。
  • 形式化为「optimal control of incompletely-known Markov decision processes」(text/04:39,搜「incompletely-known」)。
  • 与监督学习区别:无标签数据、无正确动作可给(text/04:49-60);与无监督区别:目标是最大化奖励信号不是找结构(text/04:61-71)。RL 是第三种范式(text/04:70,搜「third machine learning paradigm」)。
  • 探索-利用两难(text/04:74-87,搜「exploration and exploitation」):「remains unresolved」(text/04:85)。
  • 四要素:policy / reward signal / value function / (可选)model(text/04:209-211,搜「four main subelements」)。
  • reward 即时、value 长期;「rewards are in a sense primary, whereas values ... are secondary」(text/04:241,搜「primary」);「most important component of almost all reinforcement learning algorithms ... efficiently estimating values」(text/04:251-253,搜「efficiently estimating values」);「The central role of value estimation ... most important thing that has been learned ... last six decades」(text/04:254-255,搜「six decades」)。
  • model-based vs model-free(text/04:256-268,搜「model-based methods」)。
  • 范围:不学状态信号的设计(text/04:279-284);不覆盖演化方法(genetic algorithms 等)(text/04:287-309,搜「evolutionary methods」)。
  • 井字棋例子(1.5, text/04:311 起):每个状态一个数=获胜概率的最新估计;已知三连=1、已输/和=0、其余初始化 0.5(text/04:360-364,搜「0.5」);greedy + 偶尔 exploratory moves(text/04:367-371);更新 V(St) ← V(St) + α[V(St+1) − V(St)] (text/04:415,搜「step-size parameter」)——temporal-difference method(text/04:418,搜「temporal-difference」);探索步不学习(text/04 图注 409,搜「do not result in any learning」)。
  • 对比演化方法:「Credit is even given to moves that never occurred!」(text/04:439,搜「never occurred」)。
  • RL 能「achieve the effects of planning and lookahead without using a model」(text/04:448-450,搜「planning and lookahead」)。
  • Tesauro 西洋双陆棋 ~10^20 状态(text/04:467,搜「1020」)。
  • 1.7 历史两主线+TD 第三线(text/04:550-560,搜「two main threads」):trial-and-error(动物学习心理学)与 optimal control(DP/Bellman 1957/MDP/Howard 1960 policy iteration,text/04:564-575);Bellman「curse of dimensionality」(text/04:577,搜「curse of dimensionality」);Thorndike Law of Effect 引文(text/04:633-640,搜「Thorndike」);「reinforcement」一词来自 Pavlov 1927 英译(text/04:651-654,搜「Pavlov」);Turing 1948「pleasure-pain system」(text/04:663-665,搜「pleasure-pain」);Minsky 1954 SNARC、1961 credit-assignment 问题(text/04:711-713,搜「credit-assignment」);Michie MENACE 火柴盒(text/04:730-733,搜「MENACE」);Samuel 1959 跳棋 TD 思想(text/04:837-839,搜「Samuel」);Sutton 1988 分离 TD 与控制、TD(λ)(text/04:879-881,搜「TD(」;Watkins 1989 Q-learning 三线合流(text/04:891-893,搜「Watkins」);TD-Gammon 1992(text/04:898,搜「TD-Gammon」);多巴胺相似性(text/04:900-907,搜「dopamine」)。
  • Part I 开场(text/04:929-956):DP 数学成熟但要完整准确模型;MC 不要模型、概念简单但不适合逐步增量计算;TD 不要模型、完全增量但更难分析(text/04:943-950,搜「not well suited」)。

文件 05 = 原书第 2 章 Multi-armed Bandits​

  • 章旨:RL 与其他学习的最重要区别是「training information that evaluates the actions taken rather than instructs」(text/05:3-5,搜「evaluates the actions」)。evaluative vs instructive feedback。
  • k 臂赌博机定义(2.1, text/05:26-31):k 个选项、每选一次从依赖所选动作的平稳分布得数值奖励、1000 步最大化总奖励。q*(a)=E[Rt|At=a] (text/05:45-47);Qt(a) 估计(text/05:52)。
  • greedy/explore/exploit 定义(text/05:54-59,搜「greedy actions」);「one often refers to the "conflict" between exploration and exploitation」(text/05:69-70,搜「conflict」)。
  • 「we do not worry about balancing ... in a sophisticated way; we worry only about balancing them at all」(text/05:82-84,搜「worry only about balancing」)。
  • 2.2 样本平均法式 (2.1)(text/05:96-99);greedy = argmax Qt(a)(text/05:115);ε-greedy:概率 ε 随机选(text/05:122-124,搜「-greedy methods」);极限保证(text/05:126-129)。
  • 2.3 10 臂 testbed:2000 个随机问题、k=10、qN(0,1)、rewardN(q(At),1)、1000 步(text/05:134-173,搜「10-armed testbed」)。结果:greedy 长期 reward≈1,最优可能≈1.54(text/05:179-181,搜「1.54」);greedy 只在约 1/3 任务找到最优动作(text/05:213-215,搜「one-third」);ε=0.1 上限 91%(text/05:218,搜「91%」);ε=0.01 慢但最终更好(text/05:219-220)。方差变大 ε-greedy 更优;方差 0 时 greedy 可能最好;非平稳时必须探索(text/05:222-237,搜「nonstationary」)。
  • 2.4 增量实现:Qn+1 = Qn + (1/n)[Rn − Qn] (式 2.3,text/05:294);一般形 NewEstimate ← OldEstimate + StepSize[Target − OldEstimate] (式 2.4,text/05:302,搜「NewEstimate」)——全书的形状。
  • 2.5 非平稳:常数 α → 指数近因加权平均(text/05:363-364,搜「exponential recency-weighted」);收敛条件 (2.7) 对常数 α 不满足,永不完全收敛,但这在非平稳环境恰恰是想要的(text/05:379-384,搜「never completely converge」)。
  • 2.6 乐观初值:Q1(a)=+5(远超 q*~N(0,1)),greedy 也被迫探索(text/05:411-419,搜「optimistic」);只适合平稳问题(text/05:426-428,搜「stationary」);「The beginning of time occurs only once, and thus we should not focus on it too much」(text/05:456-457,搜「beginning of time」)。
  • 2.7 UCB:A_t = argmax Qt(a) + c·sqrt(ln t / Nt(a))(式 2.10,text/05:492-495);不确定度度量解释(text/05:501-511,搜「uncertainty」);UCB 比 ε-greedy 难推广(text/05:512-519,搜「more difficult」)。
  • 2.8 梯度赌博机:学 preference Ht(a),softmax 分布(text/05:544-554,搜「soft-max」);更新式 (2.12):H 朝 R_t − R̄_t 方向动(text/05:565-569);R̄_t 是 baseline,只影响方差不影响期望(text/05:571-578, 框注 737-743,搜「baseline」);把奖励整体抬高到 +4 对算法无影响(text/05:579-585,搜「+4」)。是 Williams 1992 policy gradient 的特例(text/05:914-916,搜「Williams」)。
  • 2.9 关联搜索/contextual bandits:给线索区分任务→学策略(text/05:746-777,搜「associative search」);动作影响下一状态=完整 RL(text/05:775-777)。
  • 2.10 参数研究:全部算法呈倒 U(text/05:810-811,搜「inverted-U」);此题上 UCB 最好(text/05:834,搜「UCB seems to perform best」);「in our opinion the methods presented in this chapter can fairly be considered the state of the art」(text/05:835-837,搜「state of the art」);Gittins index / Thompson sampling / Bayesian 精确最优不可行(2^2000 片叶子的树,text/05:866-868,搜「22000」→实际是 2^2000,写引用时直接搜「Gittins」等)。
  • 文献注:action value 一词出自 Watkins 1989(text/05:900);UCB1 出自 Auer et al. 2002(text/05:911-912,搜「UCB1」);softmax 一词 Bridle 1990(text/05:921)。

文件 06 = 原书第 3 章 Finite MDPs​

  • 章旨:MDP = 「mathematically idealized form of the reinforcement learning problem for which precise theoretical statements can be made」(text/06:15-16,搜「mathematically idealized」);bandits 估 q*(a),MDP 估 q*(s,a) 与 v*(s)(text/06:11-13,搜「state-dependent quantities」)。
  • 轨迹 S0,A0,R1,S1,A1,…(式 3.1,text/06:47);动力学 p(s′,r|s,a)(式 3.2,text/06:56,搜「dynamics of the MDP」)。
  • Markov 性质是对状态的限制:「The state must include information about all aspects of the past agent–environment interaction that make a difference for the future」(text/06:87-89,搜「make a difference」)。
  • 边界:「anything that cannot be changed arbitrarily by the agent is considered to be outside of it」(text/06:140-141,搜「changed arbitrarily」);「The agent–environment boundary represents the limit of the agent's absolute control, not of its knowledge」(text/06:149-150,搜「absolute control」)。奖励算在环境侧。
  • 三个信号:actions/states/rewards(text/06:160-164,搜「three signals」)。
  • 回收机器人例(Example 3.3,text/06:217 起):S={high,low};A(high)={search,wait},A(low)={search,wait,recharge};每罐 +1、救援 −3;rsearch>rwait(text/06:244-245,搜「rsearch」→实际写作「r search」需查;安全短语「expected number of cans」)。写作引用时搜「collecting empty soda cans」。
  • 奖励假说(3.2,text/06:292-296,搜「reward hypothesis」):「all of what we mean by goals and purposes can be well thought of as the maximization of the expected value of the cumulative sum of a received scalar signal」。出自 Littman 个人通信(text/06:1170,搜「Littman」)。
  • 奖励设计:「a chess-playing agent should be rewarded only for actually winning, not for achieving subgoals」(text/06:317-319,搜「subgoals」);「The reward signal is your way of communicating to the agent what you want achieved, not how you want it achieved」(text/06:322-323,搜「what you want achieved」)。
  • 回报 Gt:episodic 式 3.7;continuing 用折扣式 3.8;γ=0 myopic(text/06:375,搜「myopic」);Gt = R(t+1) + γG(t+1)(式 3.9,text/06:388);常数 +1 回报=1/(1−γ)(式 3.10,text/06:396)。
  • 统一记法:吸收态(text/06:462-464,搜「absorbing state」)。
  • 策略 π(a|s)(text/06:495-496,搜「mapping from states to probabilities」);vπ(式 3.12)、qπ(式 3.13);值函数可从经验平均估出=Monte Carlo(text/06:527-536,搜「Monte Carlo methods」)。
  • Bellman 方程 for vπ(式 3.14,text/06:555):值=期望下一步奖励+折扣后继值;backup diagrams(text/06:567,搜「Bellman equation for」;图 3.4 标题 text/06:897,搜「Backup diagrams」)。
  • Gridworld 例(3.5):5×5,A→+10 到 A′,B→+5 到 B′(text/06:677-678,搜「+10」或「yield a reward」);随机等概率策略;「State A is the best state to be in under this policy」(text/06:699-700,搜「best state to be in」);A 的期望回报<10 因为 A′ 靠边;B 估>5 因为 B′ 为正。
  • 高尔夫例(3.6):状态=球位置,值=−杆数(text/06:721-724,搜「Golf」);q*(s,driver) 例:text/06:838-850,搜「driver」。
  • 最优:π≥π′ iff 所有 s 上 vπ≥vπ′(text/06:813-815,搜「partial ordering」);v*=maxπ vπ(3.15);q*(3.16);Bellman 最优方程(3.18/3.19,text/06:859-871);「any policy that is greedy with respect to the optimal evaluation function v∗ is an optimal policy」(text/06:910-911,搜「greedy with respect to」);「one-step-ahead search yields the long-term optimal actions」(text/06:923,搜「one-step-ahead search」);q*「caches the results of all one-step-ahead searches」(text/06:926-927,搜「caches」);有 q* 不必知道环境动力学(text/06:928-931,搜「environment's dynamics」→搜索短语「without having to know」)。
  • 精确解贝尔曼方程的三个假设(动力学已知/算力够/Markov 性)「rarely true in practice」(text/06:988-991,搜「rarely true」);双陆棋 10^20 状态要解几千年(text/06:994-997,搜「thousands of years」)。
  • tabular case 定义(text/06:1050-1052,搜「tabular case」);RL 特有:把力气花在常遇到的状态上(text/06:1063-1067,搜「frequently encountered」)。

文件 07 = 原书第 4 章 Dynamic Programming​

  • DP 定义:「compute optimal policies given a perfect model of the environment as a Markov decision process」(text/07:2-4,搜「perfect model」);「all of these methods can be viewed as attempts to achieve much the same effect as DP, only with less computation and without assuming a perfect model」(text/07:7-9,搜「much the same effect」)——全书其余方法都拿这句自我定位。
  • DP 的关键想法:「the use of value functions to organize and structure the search for good policies」(text/07:19-20,搜「organize and structure」)。
  • 核心手法:「DP algorithms are obtained by turning Bellman equations such as these into assignments, that is, into update rules」(text/07:39-41,搜「turning Bellman」)。
  • 4.1 策略评估(prediction):把 vπ 的 Bellman 方程当更新规则反复扫(text/07:65-76,搜「iterative policy evaluation」);「expected update」=对全部可能后继按期望更新,DP 的更新都叫这个(text/07:81-89,搜「expected update」);in-place 单数组通常更快(text/07:96-101,搜「in place」)。
  • 例 4.1:4×4 gridworld,非终止态 14 个,每步奖励 −1,终止即停;vπ 的最终值=−期望步数(text/07:125-148,搜「undiscounted, episodic」;图 4.1 k=0,1,2,3,10,∞)。k=3 之后 greedy 策略已最优(text/07:214-216,搜「third iteration」)。
  • 4.2 策略改进定理:若 qπ(s,π′(s))≥vπ(s) 对所有 s,则 vπ′(s)≥vπ(s)(式 4.7/4.8,text/07:229-236,搜「policy improvement theorem」);greedy w.r.t. vπ 的新策略(text/07:269-287,搜「policy improvement」);若新策略不比旧好 ⟹ 已最优(text/07:288-300,搜「already optimal」)。
  • 4.3 策略迭代:π0 →E vπ0 →I π1 →…→ π*,v*(text/07:326-333,搜「monotonically improving」);有限 MDP 有限步收敛(text/07:331-333,搜「finite number」);评估用上一轮值函数做起点,收敛大加速(text/07:335-338,搜「great increase」)。
  • 例 4.2 Jack 租车:text/07:365-383;$10/辆、挪车 $2、泊松(需求 3/4、归还 3/2)、每地上限 20 辆、每夜最多挪 5 辆、γ=0.9;策略迭代从「从不挪车」出发(图 4.2)。
  • 4.4 值迭代:策略评估只做一扫就切改进(text/07:469-471,搜「value iteration」);式 4.10 = max 版期望更新;「value iteration effectively combines, in each of its sweeps, one sweep of policy evaluation and one sweep of policy improvement」(text/07:511-512,搜「combines, in each of its sweeps」)。
  • 例 4.3 赌徒问题:text/07:520-559;$100 目标、ph=0.4;最优策略形状奇特:资本 50 全押、51 不全押(text/07:557-559,搜「curious form」)。
  • 4.5 异步 DP:双陆棋 >10^20 状态、每秒更新一百万状态也要一千多年做一扫(text/07:572-575,搜「thousand years」);任意顺序更新、每态无限次必收敛(text/07:576-587,搜「Asynchronous DP」);边体验边解(text/07:602-608,搜「real-time interaction」)。
  • 4.6 GPI:「Almost all reinforcement learning methods are well described as GPI」(text/07:631-632,搜「well described as GPI」);两过程互拉:让策略 greedy 会破坏值一致性、让值一致会让策略不再 greedy(text/07:646-652,搜「competing and cooperating」);两条线不垂直的几何图(text/07:653-673,搜「orthogonal」)。
  • 4.7 效率:多项式时间 vs 策略总数 k^n(text/07:679-684,搜「exponentially faster」);线性规划在状态数少约 100 倍时就不可行(text/07:686-689,搜「Linear programming」);维数灾难是问题本身的、不是 DP 的(text/07:690-694,搜「curse of dimensionality」)。
  • 4.8 bootstrapping 定义:「update estimates of the values of states based on estimates of the values of successor states ... update estimates on the basis of other estimates. We call this general idea bootstrapping」(text/07:742-745,搜「bootstrapping」);下一章 MC 不要模型不 bootstrap,再下一章 TD 不要模型但 bootstrap(text/07:746-750,搜「separable」)。
  • 文献:policy improvement theorem 与 policy iteration 出自 Bellman 1957a 与 Howard 1960(text/07:774-775,搜「Howard」);modified policy iteration=Puterman & Shin 1978(text/07:778,搜「modified policy iteration」)。
  • 注意:text/07:127-129 有一处乱排(「Rtr == !1 1」),例 4.1 的奖励是每转移 −1,别引那行,引 143 行「1 on all transitions」。

文件 08 = 原书第 5 章 Monte Carlo Methods​

  • MC 定义:「require only experience—sample sequences of states, actions, and rewards from actual or simulated interaction」(text/08:3-6,搜「require only experience」);只对 episodic 任务;「incremental in an episode-by-episode sense, but not in a step-by-step (online) sense」(text/08:19-20,搜「episode-by-episode」);本书的 Monte Carlo 专指「averaging complete returns」(text/08:20-23,搜「complete returns」)。
  • 多状态=多个互相关联的老虎机;从早期状态看问题是非平稳的(text/08:24-31,搜「nonstationary」);解法=沿用 GPI。
  • 5.1 first-visit vs every-visit(text/08:49-54,搜「first visit」);first-visit 每个回报是 i.i.d.、误差标准差按 1/√n 降(text/08:79-83,搜「law of large numbers」)。
  • 二十一点例(5.1,text/08:86-118):200 个状态(点数 12–21 × 庄家明牌 A–10 × 有无可用 A);策略=20/21 才停;1 万局 vs 50 万局对比(图 5.1)。DP 难用:算「14 点停牌的获胜概率」这类转移概率复杂易错,而模拟对局容易(text/08:145-155,搜「error-prone」)。
  • MC 不 bootstrap:每个状态的估计互相独立;单状态值的计算成本与状态总数无关(text/08:169-179,搜「independent of the number of states」)。
  • 肥皂泡例(5.2,text/08:181-210):膜上每点高度=邻域平均;随机游走到边界取边界高度平均——MC 解狄利克雷问题。
  • 5.2 动作值:无模型时状态值不够用,必须显式估 q(text/08:212-219,搜「not sufficient」);确定性策略只观测到一个动作的回报→「maintaining exploration」问题→exploring starts 假设(text/08:232-245,搜「exploring starts」)。
  • 5.3 Monte Carlo ES(text/08:343-358 伪代码);「Convergence to this optimal fixed point seems inevitable ... but has not yet been formally proved. In our opinion, this is one of the most fundamental open theoretical questions in reinforcement learning」(text/08:370-373,搜「fundamental open」)——重要坦白。
  • 二十一点最优策略=Thorp 基本策略(差一处缺口)(text/08:380-385,搜「Thorp」)。
  • 5.4 on/off-policy 定义:「On-policy methods attempt to evaluate or improve the policy that is used to make decisions, whereas off-policy methods evaluate or improve a policy different from that used to generate the data」(text/08:458-463,搜「on-policy」);soft/ε-soft/ε-greedy 定义(text/08:467-480,搜「-soft」);on-policy MC 控制收敛到 ε-soft 里最好的(text/08:584-587,搜「-soft policies」)。
  • 5.5 target/behavior 策略(text/08:596-600,搜「target policy」);coverage 假设(text/08:617-619,搜「coverage」);重要性采样比 ρ(式 5.3):MDP 动力学在分子分母相消,比值只依赖两策略与序列(text/08:649-652,搜「cancel」)。
  • ordinary vs weighted IS:text/08:678-711(搜「ordinary importance sampling」);ordinary 无偏但方差可无界;weighted 有偏但方差有限、实践中强烈偏好(text/08:708-709,搜「strongly preferred」)。
  • 例 5.4:单个二十一点状态(庄家 2、玩家 13、可用 A)真值≈0.27726,用一亿局确定(text/08:733-735,搜「0.27726」)。
  • 例 5.5 无穷方差:text/08:758-803(搜「Infinite Variance」);单状态、左 0.9 回环、目标=总往左、回报恒 1;ordinary IS 数百万局仍不收敛;weighted 一局后恒等于 1。
  • 增量实现:V(n+1) = Vn + (Wn/Cn)[Gn − Vn] (式 5.8,text/08:893,搜「weighted average」附近)。
  • 5.7 off-policy MC 控制:「learns only from the tails of episodes」(text/08:979-980,搜「tails of episodes」);非贪婪动作多则学习慢,补救=TD(text/08:980-985)。
  • 5.8 折扣感知 IS(flat partial returns)、5.9 per-decision IS(星标)。
  • 5.10 总结:对 DP 的三个优势(真实交互学习/可用模拟模型/可只算感兴趣的状态)+第四个「less harmed by violations of the Markov property」,因为它不 bootstrap(text/08:1171-1174,搜「less harmed」)。
  • 文献:「Monte Carlo」一词出自 1940s 洛斯阿拉莫斯(text/08:1216-1218,搜「Los Alamos」);MC ES 首次出现在 1998 第一版(text/08:1232-1234,搜「1998 edition」)。

文件 09 = 原书第 6 章 Temporal-Difference Learning(前言点名最重要的一章,text/01:75-76 搜「Chapter 6 is the most」)​

  • 开篇定位:「If one had to identify one idea as central and novel to reinforcement learning, it would undoubtedly be temporal-difference (TD) learning」(text/09:3-4,搜「central and novel」);TD = MC 的采样 + DP 的 bootstrap(text/09:4-9,搜「they bootstrap」)。
  • 6.1 TD(0) 更新式 (6.2):V(St) += α[R(t+1) + V(S(t+1)) − V(St)] (text/09:37,搜「one-step TD」);MC 的目标 Gt、TD 的目标 R(t+1)+V(S(t+1))(text/09:39-41,搜「target for the TD update」)。
  • TD 目标两头都是估计:采样了期望 + 用了当前估计 V;「TD methods combine the sampling of Monte Carlo with the bootstrapping of DP」(text/09:73-77,搜「combine the sampling」)。
  • sample updates vs DP 的 expected updates(text/09:83-89,搜「Sample updates」)。
  • TD 误差 δt = R(t+1) + γV(S(t+1)) − V(St)(式 6.5,text/09:95,搜「TD error」);MC 误差=TD 误差之和(式 6.6,text/09:113,搜「sum of TD errors」);「arises in various forms throughout reinforcement learning」(text/09:92-93,搜「various forms」)。
  • 开车回家例(6.1,text/09:124-200):预测 30 分钟、下雨改 40、出高速改 35…;MC 必须到家才能学;TD 立刻把 30 往 50 挪(text/09:195-197,搜「learn immediately」);「each error is proportional to the change over time of the prediction, that is, to the temporal differences in predictions」(text/09:199-200,搜「temporal differences in predictions」)。
  • 6.2 优势:不要模型;在线完全增量(text/09:225-228,搜「online, fully incremental」);TD(0) 收敛已证(text/09:238-241,搜「proved to converge」);哪个学得快是 open question、连提问的正确形式都还没有(text/09:247-251,搜「open question」);实践上 TD 通常更快(text/09:251-252,搜「converge faster」)。
  • 随机游走例(6.2,text/09:255-306):5 态 A–E、起点 C、右端 +1;真值 1/6…5/6;TD 一致优于 MC(text/09:305-306,搜「consistently better」)。
  • 6.3 batch updating:text/09:326-341(搜「batch updating」);batch MC 收敛到训练集上的最小均方误差解;batch TD(0) 收敛到 certainty-equivalence 估计(text/09:407-421,搜「certainty-equivalence」)。
  • 例 6.4「You are the Predictor」(text/09:372-406):8 条经验,A→B 一次、B 终止七次(六次 1 两次 0);V(B)=3/4 无争议;V(A):MC=0(训练集零误差),TD=3/4(先建最大似然模型再算);「If the process is Markov, we expect that the first answer will produce lower error on future data, even though the Monte Carlo answer is better on the existing data」(text/09:404-406,搜「future data」)。
  • certainty-equivalence 直接算要 O(n²) 内存 O(n³) 计算;TD 用 O(n) 内存逼近同解;text/09:432-440(搜「striking」)。
  • 6.4 Sarsa(式 6.7,text/09:467);名字来自五元组 (St, At, Rt+1, St+1, At+1)(text/09:469-474,搜「quintuple」);收敛条件:所有 state–action 无穷次访问+策略极限变 greedy(text/09:479-484,搜「infinite number of times」)。
  • 风中网格例(6.5,text/09:504-535):各列风力 0 0 0 1 1 1 2 2 1 0(text/09:517);ε=0.1、α=0.5;8000 步后 greedy 已最优;带探索平均约 17 步(最小 15)(text/09:528-530,搜「17 steps」);MC 难用于此:有的策略永不终止(text/09:530-533,搜「termination is not guaranteed」)。
  • 6.5 Q-learning(式 6.8,Watkins 1989):「One of the early breakthroughs」(text/09:552-553,搜「early breakthroughs」);直接逼近 q*、与所执行策略无关(text/09:558-559,搜「independent of the policy being followed」);收敛要求所有 state–action 持续被更新(text/09:561-564,搜「continue to be updated」)。
  • 悬崖行走例(6.6,text/09:588-633):悬崖 −100;Q-learning 学到贴崖最优路径但 ε-greedy 会偶尔掉崖;Sarsa 学到绕上面的更安全长路;在线表现 Sarsa 更好(text/09:624-631,搜「online performance」→ 实际短语「worse than that of Sarsa」);ε 逐渐减小则两者都收敛到最优(text/09:632-633,搜「asymptotically converge」)。
  • 6.6 Expected Sarsa(式 6.9):用期望替代 max;消除随机选 A(t+1) 的方差(text/09:684-686 乱排区,别引;干净区 text/09:774-786);「Expected Sarsa subsumes and generalizes Q-learning while reliably improving over Sarsa ... may completely dominate both」(text/09:783-786,搜「completely dominate」);确定性环境下可安全用 α=1(text/09:775-777,搜「safely set」)。
  • 6.7 最大化偏差:max of estimates 用作 estimate of max 产生正偏(text/09:793-798,搜「maximization bias」);例 6.7:A 左→B(B 有多动作、奖励~N(0.1,1));左边期望回报 0.1>右边 0,但 Q-learning 初期强偏好左;渐近还多走约 5%(text/09:799-838,搜「always a mistake」)。
  • double learning:Q1 选动作、Q2 估值 → 无偏(text/09:844-851,搜「double learning」);「doubles the memory requirements, but does not increase the amount of computation per step」(text/09:852-854,搜「doubles the memory」);Double Q-learning 式 6.10;出处 van Hasselt 2010/2011(text/09:1042-1044,搜「van Hasselt」)。
  • 6.8 afterstates(走完棋后的局面)(text/09:903-910,搜「afterstates」)。
  • 6.9:「The methods presented in this chapter are today the most widely used reinforcement learning methods」(text/09:958-959,搜「most widely used」);TD 是一般的长程预测方法(金融/天气/选举)(text/09:972-977,搜「long-term predictions」)。
  • 文献:Sarsa 算法 Rummery & Niranjan 1994(原名 Modified Connectionist Q-learning)、「Sarsa」名由 Sutton 1996 起(text/09:1011-1013,搜「Connectionist」);TD(0) 术语与算法出自 Sutton 1988(text/09:991-993,搜「Sutton (1988)」)。注意 text/09:640-774 与图 6.3 混排,引用避开这段。

文件 10 = 原书第 7 章 n-step Bootstrapping​

  • 主旨:统一 MC 与 one-step TD;「n-step methods span a spectrum with MC methods at one end and one-step TD methods at the other. The best methods are often intermediate」(text/10:6-8,搜「spectrum」);「free you from the tyranny of the time step」(text/10:10,搜「tyranny」)。
  • n-step return(式 7.1):前 n 个真实奖励+γ^n·V(S(t+n))(text/10:85);n-step TD 更新式 (7.2)(text/10:98)。
  • 误差缩减性质(error reduction property,式 7.3):期望 n-step 回报的最坏误差 ≤ γ^(n/2)·V 的最坏误差(text/10:141-148,搜「error reduction property」)→ 全族收敛。
  • 例 7.1:19 态随机游走,中间的 n 最好(text/10:163-172,搜「19-state」或「intermediate value of n」)。
  • 7.2 n-step Sarsa(式 7.4/7.5);图 7.4:一条路,one-step 只强化最后一个动作、10-step 强化最后 10 个(text/10:262-274,搜「10-step」)。
  • 7.5 tree-backup:n-step 离策学习不要重要性采样;未选动作按目标策略概率加权进目标(text/10:469-505,搜「tree-backup」);「it is an update from the entire tree of estimated action values」(text/10:492 附近,搜「entire tree」)。
  • 7.6 统一算法 n-step Q(σ):σ=1 全采样(Sarsa)、σ=0 全期望(tree-backup)、Expected Sarsa 是「除最后一步都采样」(text/10:581-593,搜「unify」)。
  • 文献:Q(σ) 是二版新算法(text/10:738,搜「new to this text」)。

文件 11 = 原书第 8 章 Planning and Learning(模型与无模型的大一统)​

  • 开篇:统一视角;model-based 靠 planning、model-free 靠 learning,但「the heart of both kinds of methods is the computation of value functions」(text/11:10-11,搜「heart of both」)。
  • 8.1 模型定义:「anything that an agent can use to predict how the environment will respond to its actions」(text/11:20-21,搜「predict how the environment」);distribution model vs sample model(掷十二颗骰子例)(text/11:23-36,搜「distribution model」);sample model 容易得、distribution model 难(20-21 点例)。
  • planning 定义:「any computational process that takes a model as input and produces or improves a policy」(text/11:43-45,搜「takes a model as input」)。
  • 状态空间规划共同结构:(1) 都算值函数;(2) 都靠对模拟经验做 backup 更新(text/11:60-66,搜「two basic ideas」)。
  • 学习与规划的唯一差别:planning 用模拟经验、learning 用真实经验(text/11:82-89,搜「simulated experience」);「possibly identical algorithms operating on two different sources of experience」(text/11:1319-1321,搜「identical algorithms」)。
  • 8.2 Dyna-Q:direct RL / model-learning / planning 三个角色;同一 Q-learning 更新,经验来源不同;「The reinforcement learning method is thus the "final common path" for both learning and planning」(text/11:182-185,搜「final common path」);每步真实动作后做 n 次规划更新(伪代码 (a)-(f),text/11:217-230)。
  • 例 8.1 Dyna Maze:text/11:232-254;n=0(纯直接 RL)约 25 幕达标、n=5 约 5 幕、n=50 仅 3 幕(搜「three episodes」);图 8.3:第二幕中途 n=50 已铺出接近全程的策略(text/11:276-284,搜「halfway through」)。
  • 「The agent is always reactive and always deliberative」(text/11:298-299,搜「reactive and always deliberative」)。
  • 8.3 模型错了怎么办:乐观误差自我纠正(blocking maze);变好却看不到(shortcut maze:Dyna-Q 永远发现不了捷径,text/11:355-377,搜「never switched」→短语「never realized that it existed」);Dyna-Q+ 奖励探索加成 r + κ√τ(text/11:386-397,搜「bonus reward」);「this kind of computational curiosity is well worth the extra exploration」(text/11:396-397,搜「computational curiosity」)。
  • 8.4 prioritized sweeping:优先更新值变化会向上游传播的(text/11:416+,搜「prioritized sweeping」)。
  • 8.11 MCTS:「MCTS is largely responsible for the improvement in computer Go from a weak amateur level in 2005 to a grandmaster level (6 dan or more) in 2015」(text/11:1195-1197,搜「grandmaster」);四步:Selection/Expansion/Simulation/Backup(text/11:1246-1267,搜「Selection. Starting at the root」);树内用 tree policy、树外 rollout policy(text/11:1224-1227);每步重跑、可复用子树(text/11:1276-1280);「MCTS effectively grows a lookup table to store a partial action-value function」(text/11:1296-1298,搜「lookup table」)。
  • 8.13 第一部分总结·维度(text/11:1347-1453):三个共同点——估价值函数、沿轨迹 backup、GPI(text/11:1355-1362,搜「three key ideas」);两主维度=更新的宽度(样本/期望)×深度(bootstrap 程度),四角=TD/MC/DP/穷举搜索(text/11:1363-1407,搜「depth and width」);第三维=on/off-policy(text/11:1408-1416);其他维度:回报定义、状态值 vs 动作值 vs afterstate 值、探索方式、同步/异步、真实/模拟、更新位置、更新时机、记忆时长(text/11:1420-1440);未被覆盖的最重要维度=函数逼近(text/11:1449-1453,搜「function approximation. Function approximation can be viewed as an orthogonal spectrum」→短语「orthogonal spectrum」)。

文件 12 = 原书第 9 章 On-policy Prediction with Approximation​

  • 开篇:值函数不再是一张表,而是参数化函数 v̂(s,w)≈vπ(s);权重数远小于状态数(d≪|S|),改一个权重影响许多状态→泛化,「more powerful but also potentially more difficult to manage and understand」(text/12:15-20,搜「generalization」)。
  • 函数逼近使 RL 适用于部分可观测问题(text/12:21-29,搜「partially observable」)。
  • 9.1 把每次更新 s↦u 当一条监督学习训练样例(text/12:30-53,搜「training example」);RL 对函数逼近的特殊要求:在线增量+非平稳目标(text/12:59-70,搜「nonstationary」)。
  • 9.2 预测目标 VE:必须指定状态分布 μ(「We are obligated then to say which states we care most about」,text/12:80-82,搜「care most about」);on-policy distribution=按策略停留在各状态的时间占比(text/12:93-96,搜「on-policy distribution」);「It is not completely clear that the VE is the right performance objective」(text/12:123-126,搜「right performance objective」);可能发散:text/12:135-137(搜「diverge」)。
  • 9.3 SGD:式 (9.4/9.5);semi-gradient:bootstrap 目标里含 w 但求梯度时不当真→「semi-gradient」(text/12:1714-1718,搜「semi-gradient methods. In such bootstrapping methods」→短语「they are semi」)。
  • 9.4 线性方法:v̂(s,w)=wᵀx(s),特征向量/基函数(text/12:342-363,搜「feature vector」);线性情形几乎所有收敛定理都成立(text/12:373-375,搜「Almost all useful convergence results」);TD fixed point w_TD=A⁻¹b(text/12:409,搜「TD fixed point」);收敛证明核心:D(I−γP) 正定、列和 (1−γ)μ(text/12:442-475);TD fixed point 处 VE(w_TD) ≤ 1/(1−γ)·min VE(text/12:479-485,搜「bounded expansion」或「1 1 times」→短语「substantial potential loss」在 486-487);「the asymptotic error of the TD method is no more than 1/(1−γ) times the smallest possible error」(text/12:484-485)。
  • 9.5 特征构造:polynomials/coarse coding/tile coding/RBF/Fourier basis(摘要见 9.12)。
  • 9.7 非线性:神经网络+反向传播;「these methods have become very popular in recent years under the name deep reinforcement learning」(text/12:1732-1734,搜「deep reinforcement learning」)。
  • 9.12 总结:线性 n-step semi-gradient TD 对所有 n 收敛、n 越大界越紧、n→∞ 界为零,但实践中小 bootstrap 更快(text/12:1735-1741,搜「just as we saw」)。

文件 13 = 原书第 10 章 On-policy Control with Approximation​

  • 开篇惊人转折:「once we have genuine function approximation we have to give up discounting and switch to a new "average-reward" formulation」(text/13:10-13,搜「average-reward」)。
  • 10.1 episodic semi-gradient Sarsa(式 10.2)。
  • 例 10.1 Mountain Car(text/13:72-130):动力不足的车,必须先远离目标借惯性;「things have to get worse in a sense (farther from the goal) before they can get better」(text/13:111-113,搜「get worse」);每步 −1 直到到达。
  • 10.3 平均奖励设定:r(π)=Σ μ(s)Σ π(a|s)Σ p·r;差分值函数与差分 TD 误差。
  • 10.4 废弃折扣设定(text/13:475-555):「in the approximate case it is questionable whether one should ever use this problem formulation」(text/13:478-480,搜「questionable whether」);对称论证:平均折扣回报=r(π)/(1−γ),γ 对策略排序零影响、「It could in fact be zero and the ranking would be unchanged」(text/13:494-496,搜「no effect on the problem formulation」→短语「ranking would be unchanged」);「discounting has no role to play in the definition of the control problem with function approximation」(text/13:508-510,搜「no role to play」);γ 从问题参数降格为解法参数(text/13:510-511,搜「solution method parameter」);根源:函数逼近下丢了策略改进定理(text/13:514-518,搜「policy improvement theorem」);「With function approximation we have lost it!」(text/13:544);ε-greedification 可能来回抖(text/13:552-555,搜「chatter」)。
  • 文献:10.4 指出折扣局限的「recognition」是近年事(text/13:642-644,搜「Deprecating」→短语「limitations of discounting」)。

文件 14 = 原书第 11 章 Off-policy Methods with Approximation(全书最长,206k 字符)​

  • 11.2 发散例:两个状态值 w 和 2w 的碎片例:text/14:128-176;初值 w=10,TD 误差=2γw−w,更新系数 1+α(2γ−1)>1 ⟹ w→∞;「Stability does not depend on the specific step size」(text/14:159-160,搜「does not depend on the specific」)。「Eventually the piper must be paid」(text/14:173,搜「piper must be paid」);「in the off-policy case, a promise can be made and then ... forgotten and forgiven」(text/14:174-176,搜「forgotten and forgiven」)。
  • Baird 反例(text/14:180-260,搜「Baird's counterexample」):7 态 2 动作、8 维线性特征、真值全 0;semi-gradient TD(0) 对任意正步长发散,连 DP 期望更新也发散(text/14:213-225,搜「no matter how small」);把更新分布换成 on-policy 分布就稳定(text/14:226-228,搜「on-policy distribution」);「even the simplest combination of bootstrapping and function approximation can be unstable if the updates are not done according to the on-policy distribution」(text/14:249-251,搜「simplest combination」)。
  • Q-learning 也有发散反例;ε-greedy 行为策略下未见过发散但无理论(text/14:252-259,搜「never been found to diverge」)。
  • Tsitsiklis & Van Roy 反例:即使每步求最小二乘最优也发散(text/14:270-291,搜「least-squares」)。
  • 11.3 致命三件套(deadly triad,text/14:299-330,搜「deadly triad」):函数逼近+bootstrapping+离策训练;危险不在控制、不在 GPI、不在学习本身(DP 完全已知环境也炸)(text/14:317-322,搜「not due to」);三个里只能丢一个:函数逼近最不能丢(text/14:326-331);丢 bootstrap 代价=计算与数据效率(text/14:332-357,搜「extremely valuable」);丢 off-policy 的代价=没法从一条经验流并行学多个预测(text/14:358-377,搜「one stream of experience」)。
  • 11.4 线性值函数几何(v_π, Π, Π_TDE 投影等,星标)。
  • 11.5/11.6:贝尔曼误差 BE 不可学(text/14:875,搜「Not Learnable」)——「The contents of this section are new to this text」(text/14:2071)。
  • 11.7 Gradient-TD(把投影贝尔曼误差当目标、是真梯度)(text/14:1684+,搜「Gradient-TD」);GTD(λ);11.8 Emphatic-TD(改写 on-policy 分布)(text/14:1871+,搜「Emphatic-TD」);11.9 降方差。文献:Gradient-TD=Sutton, Szepesvári & Maei 2009(text/14:2073);Emphatic-TD=Sutton, Mahmood & White 2016(text/14:2082);deadly triad 首次点名=Sutton 1995b(text/14:2052,搜「1995b」)。
  • 11.10 Summary 有 11.1-11.9 的浓缩(text/14:1992-2032),写章时再查。

文件 15 = 原书第 12 章 Eligibility Traces​

  • 定位:「Eligibility traces are one of the basic mechanisms of reinforcement learning」(text/15:3-4,搜「basic mechanisms」);统一并泛化 TD 与 MC;λ=1 端是 MC、λ=0 端是 one-step TD,中间往往更好(text/15:7-11,搜「spectrum」);还能让 MC 在线、用于无回合的持续问题(text/15:11-12)。
  • 超越 n-step 的地方:只需一个短期记忆向量 zt(资格迹),不必存最近 n 个特征向量(text/15:16-26,搜「short-term memory」);「when a component of wt participates in producing an estimated value, then the corresponding component of zt is bumped up and then begins to fade away」(text/15:17-19,搜「bumped up」)。
  • 前向视角(forward view)vs 后向视角(backward view):forward=从被更新状态向前看;text/15:27-42(搜「forward views」);后向=拿当前 TD 误差往回分给带迹的旧状态(text/15:300 附近,搜「riding along the stream」→实际短语「shouting them back」需查,安全用「oriented backward in time」text/15:317)。
  • λ-return(式 12.2):所有 n-step return 按 λ^(n-1) 加权平均;text/15:85-98(搜「-return」;安全短语「compound update」text/15:73);λ=0 ⟹ TD(0),λ=1 ⟹ MC(text/15:142-146,搜「one-step TD method」)。
  • TD(λ) 机制(线性):z_t = γλ·z(t-1) + x_t(式 12.5,text/15:259);w(t+1) = w_t + α·δt·z_t(式 12.7,text/15:273);「weight vector is a long-term memory ... the eligibility trace is a short-term memory」(text/15:247-249,搜「long-term memory」)。
  • TD(λ) 对离线 λ-return 的三点改进:每步更新更早、计算均匀分布、可用于持续问题(text/15:238-243,搜「improves over」)。
  • 12.5 true online TD(λ)(van Seijen)精确等价;text/15:581+(搜「True Online」);12.7 Sarsa(λ);12.10 Watkins's Q(λ)→Tree-Backup(λ)。
  • 文献:TD(λ) accumulating traces=Sutton 1988(text/15:1606,搜「accumulating traces」)。

文件 16 = 原书第 13 章 Policy Gradient Methods​

  • 开篇:「So far in this book almost all the methods have been action-value methods ... In this chapter we consider methods that instead learn a parameterized policy that can select actions without consulting a value function」(text/16:3-8,搜「parameterized policy」);唯一例外是 2.8 梯度赌博机(脚注,text/16:31-34)。
  • actor–critic 定义:actor=学到的策略、critic=学到的值函数(text/16:26-28,搜「actor–critic」)。
  • 13.1 策略参数化的优势:(1) soft-max in action preferences 可逼近确定性策略,ε-greedy 永远留着 ε 的随机(text/16:69-79,搜「approach a deterministic policy」);(2) 能表示随机最优策略——扑克诈唬例(text/16:86-92,搜「bluffing」);例 13.1 短走廊:text/16:94-126;ε-greedy 两个策略 <−44 / <−82,最优随机策略(以 0.59 概率右移)≈−11.6(text/16:106-109,搜「0.59」);(3) 策略本身可能比值函数好近似(Tetris)(text/16:127-131,搜「Tetris」);(4) 注入先验知识的最重要途径(text/16:132-135,搜「prior knowledge」)。
  • 13.2 策略梯度定理(式 13.5):∇J ∝ Σ μ(s)Σ qπ(s,a)∇π(a|s,θ);连续性→更强的收敛保证(text/16:141-149,搜「continuity of the policy」)。
  • 13.3 REINFORCE(式 13.8):θ += α·Gt·∇ln π(At|St,θt)(text/16:298-300,搜「REINFORCE update」);直觉:回报大→更倾向重复该动作;除以概率防高频动作占便宜(text/16:301-310,搜「intuitive appeal」);MC 方法、只在幕末更新(text/16:311-314,搜「Monte Carlo algorithm」);方差高(text/16:377-378,搜「high variance」)。
  • 13.4 baseline(式 13.10/13.11):b(s) 不随 a 变则期望不变、只影响方差(text/16:390-409,搜「baseline」);MDP 里 baseline 应随状态变(text/16:412-415,搜「vary with state」)。
  • 13.5 actor–critic:critic=把值函数用于评估动作(one-step return)(text/16:473-490,搜「called a critic」);一步 actor–critic 更新 θ += α·δt·∇ln π(text/16:518-524,搜「fully online, incremental」)。
  • 13.7 连续动作:高斯策略参数化(text/16:680+,搜「Gaussian」)。
  • 文献:REINFORCE=Williams 1987/1992(text/16:838,搜「Williams」);baseline 也出自 Williams(text/16:847)。

文件 17 = 原书第 14 章 Psychology​

  • 章旨:「The clear formalism provided by reinforcement learning ... is proving to be enormously useful in making sense of experimental data」(text/17:5-9,搜「making sense of experimental data」);接触点是「independently arising」的对应,暴露的是跨人工/自然系统通用的计算原则(text/17:10-17,搜「computational principles」)。
  • 14.2 经典条件反射:Pavlov 狗/节拍器(text/17:97-110,搜「metronome」);CS/US/CR/UR 术语(text/17:110-118,搜「conditioned stimulus」);delay vs trace conditioning(text/17:120-140)。
  • blocking(阻滞):兔子瞬膜实验——先训练音调,再加光,兔子对光学不到;挑战「时间接近性就够」(text/17:162-178,搜「Blocking」);Rescorla–Wagner 模型(1972)解释之(text/17:176-178,搜「Rescorla–Wagner」)。
  • higher-order conditioning:黑方块→节拍器(已被条件化)→10 次后黑方块也引发分泌;text/17:180-198(搜「black square」);TD 模型用 bootstrapping 同时解释 blocking+高级条件化+CR 的提前性(text/17:196-198,搜「bootstrapping idea」)。
  • secondary/conditioned reinforcer(text/17:200-208,搜「secondary reinforcer」)。
  • 14.3 工具性条件反射;14.4 延迟强化(Sidman avoidance 等);14.5 认知地图(latent learning)。
  • 14.6 习惯 vs 目标导向 = model-free vs model-based:「Habits are sometimes said to be controlled by antecedent stimuli, whereas goal-directed behavior is said to be controlled by its consequences」(text/17:1007-1009,搜「antecedent stimuli」);outcome devaluation 检验;text/17:1012-1075 图 14.5 大鼠迷宫例(model-free 存动作值、model-based 建模型模拟)(搜「Model-Free」)。
  • 文献:TD 条件反射模型=Sutton & Barto 1981a/1990(text/17:1275+ 附近,搜「Sutton and Barto」需核)。

文件 18 = 原书第 15 章 Neuroscience​

  • 15.3 奖励预测误差假说:「one of the functions of the phasic activity of dopamine-producing neurons in mammals is to deliver an error between an old and a new estimate of expected future reward to target areas throughout the brain」(text/18:190-193,搜「Reward Prediction Error Hypothesis」);首次明确表述=Montague, Dayan & Sejnowski 1996(text/18:193-195,搜「Montague」);实验来自 Schultz 实验室 1980s-90s(text/18:196-198,搜「Schultz」)。
  • 假设:多巴胺对应 δ(t−1)+b_t,b_t 是背景放电率;负 δ=低于基线(text/18:213-216,搜「background firing rate」);CSC(完整串复合)表示让 TD 误差能对上「何时」(text/18:216-228,搜「complete serial compound」)。
  • 四个平行特征:①只有未预测的奖励才有 phasic 反应;②学习后预测性线索获得多巴胺反应;③更早线索出现后反应转移给更早线索;④预测的奖励缺席→低于基线(text/18:231-240,搜「(1) the」→短语「omitted」text/18:239)。
  • 15.4 多巴胺:SNpc 与 VTA;动机/学习/动作选择/成瘾/帕金森;neuromodulator(text/18:264-276,搜「substantia nigra」)。
  • 15.6 TD 误差/多巴胺对应:理想化猴子任务、TD(0)、表格、γ≈1;text/18:534-600(搜「TD Error/Dopamine Correspondence」);猴子把反应前移到最早预测性线索等。
  • 15.7 神经 actor–critic:basal ganglia;text/18:753+(搜「basal ganglia」);15.9 Klopf 的 hedonistic neuron 假说(text/18:1099,搜「Hedonistic Neurons」);15.12 成瘾(text/18:1396,搜「Addiction」)。
  • 文献:Schultz 1998 综述(text/18:1637,搜「1998 survey」)。

文件 19 = 原书第 16 章 Applications and Case Studies​

  • 16.1 TD-Gammon(text/19:15-75):Tesauro;TD(λ)+多层 ANN+反向传播 TD 误差;「required little backgammon knowledge, yet learned to play extremely well, near the level of the world's strongest grandmasters」(text/19:17-19,搜「grandmasters」);分支因子约 400,常规启发式搜索没法用(text/19:60-64,搜「400」);v̂=获胜概率、自他对弈。TD-Gammon 0.0 raw 输入≈此前最好程序;加特征后 1.0 超越所有程序(text/19:856-862,搜「TD-Gammon 1.0」);影响了 IBM 的 backgammon 圈外人也改打法(text/19:190 附近,搜「backgammon community」需核)。
  • 16.2 Samuel 跳棋(1959):最早的 TD 思想(text/19:422,搜「Samuel」);learns by self-play。
  • 16.3 Watson 的 Daily-Double 下注(text/19:537,搜「Watson」):2011 年 Jeopardy!;action values+smoothed 下注曲线。
  • 16.4 内存控制(text/19:667,搜「Memory Control」):IBM 服务器的访存调度。
  • 16.5 DQN/Atari(text/19:841-950):DeepMind(Mnih et al. 2013/2015);「an impressive demonstration that a deep multi-layer ANN can automate the feature design process」(text/19:845-847,搜「automate the feature design」);49 个 Atari 2600 游戏、同一原始输入/架构/参数、只重置权重(text/19:863-871,搜「49 different」);Q-learning+深度卷积网络;经验回放(搜「experience replay」text/19:905 附近);comparison:此前 RL 应用都靠手工特征(text/19:841-844,搜「handcrafted」)。
  • 16.6 AlphaGo(text/19:1082-1200):DeepMind(Silver et al. 2016);「combining deep ANNs, supervised learning, Monte Carlo tree search, and reinforcement learning」(text/19:1094-1096,搜「combining deep」);胜樊麾 5:0、胜李世石 4:1(2016)(text/19:1096-1102,搜「Lee Sedol」);AlphaGo Zero 只用 RL、无人类数据(text/19:1104-1108,搜「AlphaGo Zero」);谱系:Samuel→TD-Gammon→AlphaGo(text/19:1110-1114,搜「descendants of Tesauro」);Go 难在评估函数:text/19:1140-1150(搜「evaluation function」;Müller 2002 引语「No simple yet reasonable evaluation function will ever be found for Go」text/19:1147-1149)。
  • 16.7 个性化 Web 服务;16.8 热气流滑翔。

文件 20 = 原书第 17 章 Frontiers​

  • 17.1 泛值函数 GVF:为每个问题(不仅奖励)学的值函数;text/20:8+(搜「General Value Functions」);17.2 options/时间抽象(text/20:98,搜「Options」)。
  • 17.3 观测与状态:历史、POMDP、PSR、 Ring 世界(text/20:223,搜「Observations and State」)。
  • 17.4 奖励设计(text/20:447-590):「designing a reward signal is a critical part of any application of reinforcement learning」(text/20:451-452,搜「designing a reward signal is a critical」);「generating a reward signal does not depend on knowledge of what the agent's correct actions should be」(text/20:447-449,搜「detailed instructional information」);动物脑内奖励信号演化了数百万年,别以为容易(text/20:455-458,搜「millions of years」);agent 会发现意想不到的拿奖励方式,可能危险——「a longstanding and critical challenge for any method ... based on optimization」(text/20:463-466,搜「unexpected ways」→安全短语「undesirable, or even dangerous」text/20:465);稀疏奖励问题=Minsky 1961「plateau problem」(text/20:470-473,搜「plateau」);加子目标奖励有风险(可能学偏)、更好是给值函数初值(式 17.11)(text/20:477-483,搜「well-intentioned supplemental rewards」)。
  • 17.5 六个遗留问题(text/20:591-714):①适合在线增量环境的强大函数逼近——「An honest assessment has to be that current deep learning methods are not well suited to online learning」(text/20:611-613,搜「not well suited to online」);灾难性干扰/replay buffer(text/20:606-610,搜「catastrophic interference」);②表示学习/特征学习(text/20:613-640,搜「representation learning」);还有四个写章时再查(text/20:640-714)。
  • 17.6 RL 与 AI 的未来(text/20:715-874):「the gulf between artificial intelligence and the intelligence of humans ... remains great」(text/20:723-726,搜「remains great」);Herbert Simon 2000 Prometheus/Pandora 演讲(text/20:744-753,搜「Prometheus」);「can benefit society but can also produce undesirable outcomes if it is carelessly deployed」(text/20:753-755,搜「carelessly deployed」);模拟经验 vs 真实世界嵌入(text/20:756-780,搜「real world」)。
  • 全书收尾(text/20 末尾,搜「common thread」附近):Dyna 式 model-free+model-based 结合+函数逼近+off-policy 是本书路线(text/20:593-598,搜「Dyna architecture」)。
  • 注意:text/07:127-129 有一处乱排(「Rtr == !1 1」),例 4.1 的奖励是每转移 −1,别引那行,引 143 行「1 on all transitions」。