强化学习复习站KNOWLEDGE & PRACTICE
FORM B · WORKED SOLUTIONS

B 卷 · 中文详细解析

逐题说明考什么、怎么想、如何代入,以及容易出错的地方。每题末尾附英文答案要点;简答每个有效得分点 1 分,计算题允许保留正确方法分。

先做题再看解析。标为“进一步理解”的补充不额外计分。

10 questions × 2 points

I. Single-choice questions

20 points

A1. The meaning of k [2 points]

先把题目读懂

同步策略评估中的 Vₖ,k 到底在数什么?需要区分电脑更新了几轮与智能体走了几步。

第一步该想什么?

把 V₀ 想成第一张空白估计表。填完一整张新表得 V₁,再依据它填下一张得 V₂;这个计数才是 k。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

In synchronous policy evaluation, k in Vₖ denotes which quantity?

A. The number of completed value-update sweeps.

B. The number of available actions.

C. The number of steps in the current sampled episode.

D. The learning rate.

下面跟着题目逐步算

正确答案:A

V₀ 是初始价值表;计算完第一整轮得到 V₁;再用完整的 V₁ 计算 V₂。k 是“更新了几轮”,不是机器人走到了第几个格子。

为什么同步很重要

计算 V₂ 的所有格子都读取 V₁。即使你刚算出了某格的 V₂,也不能立刻拿它算同一轮其他格子。若这样做,属于原地更新,数值过程会不同。

B 是动作集合大小,C 是环境时间 t,D 是学习率 α,均不是 k。

A2. A sufficient state [2 points]

先把题目读懂

机器人要先拿钥匙才能开门。如果状态只记位置,应该补充什么信息?题目要你找出能消除预测歧义的状态表示。

第一步该想什么?

想象两个机器人站在同一门口:一个有钥匙,一个没有。对它们都下“开门”指令,结果相同吗?如果不同,状态必须能把它们区分开。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

A robot must collect a key before opening a door. Which state representation most directly fixes the missing information if position alone is not Markov?

A. Position only, with a smaller learning rate.

B. Position together with whether the key is held.

C. The most recent reward only.

D. A fixed action at every position.

下面跟着题目逐步算

先理解题意

机器人站在同一个门口,有钥匙时能开门,没有钥匙时不能。仅知道“位置”无法判断下一步结果,所以缺了有用的信息。

正确答案:B

把“是否持有钥匙”放进状态,才能区分这两种情况。Markov 的要求是:给定当前状态和动作后,过去不再额外影响下一结果的条件分布。

逐项排除

A 改学习率只影响更新幅度,不能补回状态信息。C 丢失位置与钥匙信息。D 固定动作改变了策略,也不能修复状态表示。

A3. A DQN target [2 points]

先把题目读懂

非终止转移奖励 2,γ=0.5,目标网络在下一状态给出 6、2。问普通 DQN 的训练目标。

第一步该想什么?

先在题给目标网络里找最大值,再只对未来部分打折,最后加刚收到的奖励。题目没让你再做一次学习率更新。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

A nonterminal transition has r=2 and γ=0.5. The target network outputs (6, 2) at the next state. What is the standard DQN target?

A. 5

B. 3

C. 6

D. 2

下面跟着题目逐步算

正确答案:A

标准 DQN 用目标网络在下一状态的最大动作值,然后折扣并加即时奖励。

y=2+0.5\max(6,2)=5

B 相当于选了值为 2 的动作;C 只报了下一状态最大 Q,未加奖励和折扣;D 只适用于没有未来项的终止转移,本题明确非终止。

A4. Bellman expectation [2 points]

先把题目读懂

两个动作的价值是 8、4;策略以 0.25、0.75 的概率选择它们。问尚未选第一步动作时,状态平均值是多少。

第一步该想什么?

你还没指定动作,所以必须同时考虑两种走法。先分别算“动作概率×动作价值”,再相加;这里不是让你改成总选最好动作。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

A policy selects a₁ with probability 0.25 and a₂ with probability 0.75. If qπ(s,a₁)=8 and qπ(s,a₂)=4, what is vπ(s)?

A. 4

B. 6

C. 8

D. 5

下面跟着题目逐步算

正确答案:D

V 表示尚未指定第一步动作时的期望;Q 已经指定第一步动作。因此 V 要按策略概率把两个 Q 加权。

v_\pi(s)=0.25(8)+0.75(4)=5

A 只选了 a₂;B 按各一半平均,和给定策略不符;C 取最大,回答的是贪心选择,而不是该固定策略的价值。

A5. Bootstrapping [2 points]

先把题目读懂

哪些学习目标里,用到了“我们现在猜的未来价值”?题目用 bootstrapping 表示这种借估计更新估计的做法。

第一步该想什么?

找目标中的 V 或 Q。完整回报是后来实际收到的奖励和;TD 的未来项则是还没等全部未来发生,就先用当前估计代替。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

Which target bootstraps from an estimated state value?

A. The observed full episodic return Gₜ.

B. The sum of all rewards in a finished episode without a value estimate.

C. Rₜ₊₁ + γV(Sₜ₊₁).

D. The empirical average of complete returns.

下面跟着题目逐步算

正确答案:C

Bootstrapping 指“用已有估计帮助更新另一个估计”。TD 目标中的 V(Sₜ₊₁) 不是已知真值,而是我们当前对未来的估计。

Y^{TD}=R_{t+1}+\gamma V(S_{t+1})

A、B、D 都只依赖已经采集到的完整回报,没有在目标末尾接一个价值估计,属于 MC 思路。不要把“随机抽样”和“自举”当成一回事:TD 两者都有,MC 抽样但不自举。

A6. An action-independent baseline [2 points]

先把题目读懂

REINFORCE 为什么可以从回报中减去只依赖状态的基线,而不改变梯度估计的期望?

第一步该想什么?

基线相当于在同一状态给所有动作使用同一个比较标准。关键是:将这个相同常数乘上各动作的概率梯度后求和,附加项能否抵消。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

In REINFORCE, why can a state-dependent, action-independent baseline be subtracted from the return without changing the expected policy-gradient estimator?

A. The baseline must equal zero.

B. The expected score function at a fixed state is zero.

C. Every sampled gradient becomes zero.

D. The rewards are replaced by the baseline.

下面跟着题目逐步算

正确答案:B

固定状态 s 后,对动作分布求和:Σₐπ(a|s)∇logπ(a|s)=Σₐ∇π(a|s)=∇1=0。基线 b(s) 与动作无关,可以从求和中提出,因此被减掉的那一项期望为零。

\sum_a\pi(a\mid s)b(s)\nabla\log\pi(a\mid s)=b(s)\nabla 1=0

A 不要求基线为零;C 说的是每个样本,实际上只有附加基线项的期望为零;D 不是替换环境奖励,而是调整梯度权重。

A7. Discounted return [2 points]

先把题目读懂

一回合依次得 −2、4、8 分后结束,γ=0.5。问站在最开始时,折扣后的总回报是多少。

第一步该想什么?

把三笔奖励按收到时间排成一行。第一笔乘 1,第二笔乘 0.5,第三笔乘 0.5²,然后相加;先不要管 V、Q 或学习率。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

The rewards are -2, 4, 8, followed by termination. With γ = 0.5, what is G₀?

A. 10

B. 0

C. 2

D. 4

下面跟着题目逐步算

正确答案:C

回报从下一次奖励开始计数:第一项不打折,第二项乘 γ,第三项乘 γ²。

G_0=-2+0.5(4)+0.5^2(8)=2

也可以倒推:G₂=8,G₁=4+0.5×8=8,G₀=-2+0.5×8=2。

其他选项为何不对

A 的 10 是直接相加,忽略折扣;B 的 0 漏掉第三项;D 的 4 不是按题定时序得到的起点回报。终止只是后面没有奖励,不意味着入终点前的 8 要删除。

A8. Function approximation [2 points]

先把题目读懂

线性价值函数中,更新一个状态却也影响另一个状态,这说明了什么?

第一步该想什么?

想象许多状态共用一套评分系数。改一个系数,所有使用它的状态分数都可能改变;这就是共享参数带来的信息传播。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

Two states have similar feature vectors in a linear value approximator. Updating the weights using one state may affect the estimate of the other state. This illustrates:

A. Exact tabular independence.

B. A known transition model.

C. Guaranteed optimality.

D. Generalization through shared parameters.

下面跟着题目逐步算

正确答案:D

线性近似写作 V̂(s,w)=x(s)ᵀw。不同状态共用同一个 w,因此在一个状态更新 w,其他状态的输出也可能改变。这是泛化的来源,也可能造成互相干扰。

A 错在表格通常为各状态存独立数值;B 的转移模型预测下一状态或奖励,与价值近似不同;C 的共享参数没有保证一定能精确表示或学到最优价值。

A9. Ties in ε-greedy [2 points]

先把题目读懂

四个动作中有两个并列最高,ε=0.2。问每一个最高动作分别有多大概率被选中。

第一步该想什么?

选中最高动作有两条途径:进入利用分支并分到它,或进入探索分支又抽到它。两条互斥途径的概率要相加。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

There are four actions. Exactly two tie for the largest Q value. If ε = 0.2, what is the probability of EACH greedy action?

A. 0.80

B. 0.45

C. 0.40

D. 0.05

下面跟着题目逐步算

正确答案:B

总利用概率 1-ε=0.8,要平分给两个并列最优动作,所以每个得到 0.4。探索时从全部四个动作均匀选,每个又得到 0.2/4=0.05。

\pi(a_{\rm greedy}\mid s)=\frac{0.8}{2}+\frac{0.2}{4}=0.45

两个非贪心动作各为 0.05,总和 0.45+0.45+0.05+0.05=1。A 忘了并列分配;C 漏了探索也会选中最优动作;D 仅是探索部分。

A10. Dueling aggregation [2 points]

先把题目读懂

Dueling 网络给出状态分量 V=3、原始优势 (4,0)。问减去平均优势后的两个 Q 值。

第一步该想什么?

先算原始优势平均值,再从每个优势里减去同一个平均值,最后各加 V。三个步骤不能跳过中间那一步。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

A dueling network has V(s)=3 and raw advantages (4, 0). Using mean-subtracted advantages, what are the Q values?

A. (7,3)

B. (4,0)

C. (5,1)

D. (3,3)

下面跟着题目逐步算

正确答案:C

先算平均优势 (4+0)/2=2,再把每个原始优势减去 2,最后加 V=3。

Q_1=3+4-2=5,\qquad Q_2=3+0-2=1

A 直接 V+A,漏减平均;B 忽略 V 与中心化;D 抹掉动作差异。原始优势头的输出不必本来就均值为零,组合层负责中心化。

5 questions × 5 points

II. Short-answer questions

25 points

B1. Prediction versus control [5 points]

先把题目读懂

解释 prediction 和 control;描述策略迭代的两个阶段;说明求策略为什么写 argmax。

第一步该想什么?

先用“评价现有走法”和“寻找更好走法”区分任务,再说明先算分、后挑动作。最后用一个具体动作表区分最大分数与拿到该分数的动作。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

Explain prediction and control. Describe the two stages of policy iteration, and explain why a greedy policy improvement uses argmax rather than max. [5 points]

下面跟着题目逐步算

题目在问什么

先分清“评价已有做法”和“寻找更好做法”,再说明策略迭代怎样交替完成它们。

五个得分点(各 1 分)

① Prediction 在固定 π 下估计 vπ 或 qπ;它不负责主动换成另一策略。② Control 寻找最优策略或最优价值。

③ Policy evaluation:把当前 π 固定,解 Bellman 期望方程或迭代近似求 vπ。④ Policy improvement:对每个动作计算一步奖励加后继 vπ 的期望,再选择最大者,形成 π′。

⑤ max 返回最大的数值;argmax 返回达到该最大值的动作。策略需要“做哪一个动作”,因此写 argmax。

\pi'(s)\in\arg\max_a\sum_{s',r}p(s',r\mid s,a)[r+\gamma v_\pi(s')]

例如动作 Left、Right 对应 Q=2、5:max=5,argmax=Right。两动作并列时,可以选择任一最大动作或在最大动作之间随机。

B2. GLIE is a property [5 points]

先把题目读懂

写出 GLIE 的两个条件,判断它属于算法、选动作公式还是长期性质,并分析固定 ε 与只要求 ε→0 的情况。

第一步该想什么?

把三个层次分开:MC/SARSA 怎么学;ε-greedy 怎么选;GLIE 要求长期做到什么。分别检查“还会不会充分尝试”和“最终是否集中到贪心动作”。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

State both GLIE conditions. Is GLIE itself a learning update or an action-selection formula? Discuss fixed ε = 0.1 and explain why merely requiring εₜ → 0 is insufficient. [5 points]

下面跟着题目逐步算

先说结论

GLIE 是一组关于行为策略序列的长期要求,不是 MC 的别名,也不是独立的 Q 更新公式。

评分与推理

① Infinite exploration(1 分):在收敛定理所要求的状态动作范围内,各状态动作对被无限次访问。② Greedy in the limit(1 分):行为策略在极限中把概率集中到当前价值估计的贪心动作上。

③ 分类(1 分):MC、SARSA 是学习方式;ε-greedy 是选动作的方法;GLIE 是探索与极限行为的性质。

④ 固定 ε=0.1(1 分):若存在非贪心动作,其探索概率始终为正,极限不纯贪心,因此通常不满足 GLIE。

⑤ εₜ→0 不充分(1 分):例如下降太快会导致总探索次数不足;而且某些状态需要连续若干探索动作才可到达,单凭 ε 衰减不能保证所有状态动作充分访问。还要检查环境可达性和实际访问条件。

B3. DQN and Double DQN [5 points]

先把题目读懂

给出 DQN 与 Double DQN 的目标,解释两张网络分别负责什么,以及为何能缓解过估计。

第一步该想什么?

把“挑一个动作”与“给这个动作打分”当成两个岗位。逐个写清在线网络、目标网络在两个算法中分到哪个岗位,再讨论为什么同一误差同时做两件事会偏乐观。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

Give the standard DQN and Double DQN nonterminal targets. Explain which network selects and evaluates the next action in each case, and why Double DQN can reduce overestimation. [5 points]

下面跟着题目逐步算

把“选动作”和“评估动作”拆开

网络输出都有估计误差。对同一组带噪估计既取最大又报告其值,容易选中因为正误差而显得最大的动作。

y^{DQN}=r+\gamma\max_a Q(s',a;\theta^-)
a^*=\arg\max_a Q(s',a;\theta),\qquad y^{DDQN}=r+\gamma Q(s',a^*;\theta^-)

五分怎么拿

DQN 目标 1 分;Double 目标 1 分;DQN 由目标网络同时选择、评价 1 分;Double 由在线网络选择、目标网络评价 1 分;解释分离两种角色可缓解最大化偏差 1 分。

不要写成 Double 从两个目标里取最小,也不要说它保证永远没有过估计。它改变的是训练目标的构造,不是把两个网络平均。

B4. Prioritized replay [5 points]

先把题目读懂

解释优先经验回放如何设优先级、归一化抽样、再用重要性权重修正,并说明两个小参数的作用。

第一步该想什么?

把经验池想成几张复习卡:错得多的多抽,但要承认抽得不均匀。按“先分配抽签权重,再算抽中概率,最后修正训练贡献”的顺序回答。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

Describe proportional prioritized experience replay. State a priority, a sampling probability and an importance-sampling weight. Explain the roles of the small positive priority offset and the correction exponent β. [5 points]

下面跟着题目逐步算

先理解为什么优先抽

TD error 大表示这条经验与当前预测差得多,可能更值得学习。因此抽样概率可依赖误差,而不是每条经验一样大。

p_i=|\delta_i|+\epsilon_p,\quad P(i)=\frac{p_i^{\alpha_p}}{\sum_jp_j^{\alpha_p}},\quad w_i=(N P(i))^{-\beta}

五个得分点(各 1 分)

① 用 |δ|+小正数设优先级;② 按优先级的 αₚ 次幂归一化抽样;③ 给出重要性权重,可除以当前最大权重归一化;④ εₚ>0 使零误差经验仍有非零抽取机会;⑤ β 控制对非均匀抽样偏差的修正程度,β=0 不修正,β=1 对给定经验池的均匀平均目标作完整重要性修正。

这里 αₚ 是“优先程度”,不是 TD 更新的学习率。εₚ 是优先级偏置,也不是 ε-greedy 的探索概率。权重修正不等于整个非线性训练过程必然无偏或收敛。

B5. REINFORCE and Actor–critic [5 points]

先把题目读懂

写带基线的无折扣 REINFORCE 更新,再说明 actor、critic 和 TD error 信号。

第一步该想什么?

先说谁负责选择、谁负责评价。完整回报减基线是本次表现相对参考水平的好坏;critic 可以用一步 TD 误差提供更及时的近似反馈。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

For an undiscounted episodic task, write a REINFORCE update with a state baseline. Then describe the actor and critic, and give a one-step TD-error signal commonly used by the actor. [5 points]

下面跟着题目逐步算

把两个角色分开

Actor 决定动作概率;critic 评价状态或动作有多好。REINFORCE 用完整回报作反馈,actor–critic 常用 critic 产生的自举信号。

\theta\leftarrow\theta+\alpha[G_t-b(S_t)]\nabla_\theta\log\pi_\theta(A_t\mid S_t)
\delta_t=R_{t+1}+\gamma V_w(S_{t+1})-V_w(S_t)

评分:5 分

正确梯度上升更新 1 分;完整回报及动作无关基线 1 分;actor 参数化策略 1 分;critic 估计价值 1 分;TD error 作优势的近似信号 1 分。本题 undiscounted 表示 γ=1;第二式保留 γ 表示一般写法。

当 G-b>0 时,更新倾向增加被选动作的概率;当 G-b<0 时,倾向降低。TD error 不是精确优势真值,critic 不准时会带来误差。

3 questions: 8 + 8 + 9 points

III. Calculation — MDP

25 points

C1. A two-state Markov reward process [8 points]

先把题目读懂

只有 A、B、终点 T,没有可选动作。A 每步奖励 2,一半留 A、一半去 B;B 奖励 −1,一半去 A、一半结束;γ=0.5。要求写矩阵、算一条样本的回报、解真实值,再从零更新两轮。

第一步该想什么?

分开三个问题:矩阵描述“所有可能怎么走”;样本回报只看 A→B→T 已发生的路径;真实值要平均所有分支。最后的 V₁、V₂ 只是一轮、两轮近似,不等于解方程所得真值。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

There are nonterminal states A, B and terminal state T. γ=0.5. From A, the immediate reward is always 2; the next state is A or B with probability 0.5 each. From B, the reward is always -1; the next state is A or T with probability 0.5 each. T is absorbing with zero reward.

(a) Write the transition matrix in the order (A,B,T) and the expected reward vector. [2]

(b) For the observed episode A → B → T, compute G₀ and G₁. [2]

(c) Write and solve the Bellman equations for v(A),v(B). [2]

(d) From V₀=(0,0), calculate the synchronous vectors V₁ and V₂. [2]

下面跟着题目逐步算

读题:样本回报与真实价值不同

这一题没有让你选择动作,所以是 MRP。小问 (b) 只沿已经发生的路径计算;(c) 则要对所有可能下一状态求期望。

(a) 转移与奖励(2 分)

当前状态到 A到 B到 T期望即时奖励
A0.50.502
B0.500.5-1
T0010

矩阵每行和为 1,奖励向量 r=(2,-1,0)ᵀ。到终点这一步仍领取 B 的 -1。

(b) 沿单条轨迹倒推(2 分)

G_1=-1,\qquad G_0=2+0.5(-1)=1.5

(c) Bellman 方程(2 分)

v_A=2+0.25v_A+0.25v_B,\qquad v_B=-1+0.25v_A

将第二式代入第一式:vA=2+0.25vA-0.25+0.0625vA,所以 0.6875vA=1.75。

v_A=\frac{28}{11},\qquad v_B=-\frac{4}{11}

路径回报 1.5 不等于期望价值 28/11;某一次样本不能代表全部可能未来。

(d) 同步迭代(2 分)

V₁ 只剩即时奖励,得到 (2,-1)。第二轮所有右侧都用 V₁:A=2+0.25×2+0.25×(-1)=2.25;B=-1+0.25×2=-0.5。

C2. Policy evaluation and one improvement [8 points]

先把题目读懂

S 有 stay(得 1、回 S)与 move(得 0、去 U);U 有 cash(得 4、结束)与 reset(得 0、回 S)。γ=0.5,旧策略每处各选一半。要求评估旧策略、比较四个动作、评估新策略并检查并列。

第一步该想什么?

先坚持题给各一半,不能先贪心。得到旧 V 后,逐个指定第一动作算 Q,才知道如何改进。改完策略后要重新算 V,因为后续走法已经改变。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

γ=0.5. In S, action stay gives reward 1 and returns to S; move gives reward 0 and goes to U. In U, cash gives reward 4 and terminates; reset gives reward 0 and goes to S. Policy π selects each available action with probability 0.5.

(a) Write the Bellman expectation equations under π. [2]

(b) Solve for vπ(S) and vπ(U). [2]

(c) Compute qπ for all four state-action pairs, and give a greedy improved policy π′. [2]

(d) Evaluate π′. Is its action at S uniquely greedy with respect to vπ′? Explain. [2]

下面跟着题目逐步算

本题主线

先固定随机策略算 V;再指定第一步动作算四个 Q;最后根据 Q 换策略并重新评估。不要一开始就把策略平均替换成 max。

(a) 期望方程(2 分)

v_S=0.5(1+0.5v_S)+0.5(0.5v_U),\quad v_U=0.5(4)+0.5(0.5v_S)

(b) 联立求解(2 分)

vU=2+0.25vS,代入第一式得 0.75vS=0.5+0.25(2+0.25vS),因此 0.6875vS=1。

v_S=\frac{16}{11},\qquad v_U=\frac{26}{11}

(c) 比较四个动作(2 分)

状态动作代入qπ
S, stay1+0.5×16/1119/11
S, move0+0.5×26/1113/11
U, cash4+0.5×04
U, reset0+0.5×16/118/11

所以 π′(S)=stay,π′(U)=cash。这里 Q 的后续价值必须用刚求出的 vπ。

(d) 评估新策略(2 分)

选择 stay 后 v′_S=1+0.5v′_S,得 2;U 直接 cash,得 4。此时 S 的 stay 值 1+0.5×2=2,move 值 0+0.5×4=2,出现并列。因此 stay 仍贪心,但不唯一。

C3. A 2 × 3 grid [9 points]

先把题目读懂

2 行 3 列格子,左上和右下是终点;四方向各 1/4,撞墙留原地,每步扣 1,γ=1。要求从全零表得到 V₁、V₂、部分 V₃,再用 V₂ 选动作。

第一步该想什么?

先画好终点,再为每个格子列出上下左右后继。每轮只读上一轮整张表。最后指定一个动作算 Q 时不再除以四,因为你已不是对四方向平均。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

The grid has two rows and three columns. (1,1) and (2,3) are terminal. Four actions (up, down, left, right) are equiprobable. A move outside the grid leaves the state unchanged. Every move FROM a nonterminal state gives reward -1, including a move entering a terminal. γ=1; terminal values are fixed at zero.

(a) Write the synchronous random-policy update equation. [1]

(b) Starting from V₀=0, give the whole V₁ grid. [2]

(c) Give the whole V₂ grid. [2]

(d) Calculate V₃(1,2) and V₃(2,1). [2]

(e) Using V₂ for successor values, compute all four one-step action values at (1,2) and identify every greedy action. [2]

下面跟着题目逐步算

先画出状态

第一行是 T、(1,2)、(1,3);第二行是 (2,1)、(2,2)、T。出界会停在原格,但仍扣 1 分。

(a) 更新式(1 分)

V_{k+1}(s)=-1+\frac14\sum_{a\in\{U,D,L,R\}}V_k(s_a),\quad V_k(T)=0

(b) 第一轮(2 分)

所有未来估计为零,因此所有非终止格为 -1。两行分别为 [0,-1,-1]、[-1,-1,0]。

(c) 第二轮(2 分)

每个非终止格四个方向中恰有一个能进入终点,另三个后继值为 -1。因此 -1+(0-1-1-1)/4=-1.75。

行第 1 列第 2 列第 3 列
V₂ 第一行0-1.75-1.75
V₂ 第二行-1.75-1.750

(d) 第三轮(2 分)

(1,2) 的上、下、左、右后继值为 -1.75,-1.75,0,-1.75;(2,1) 为 0,-1.75,-1.75,-1.75。两者都为 -1-5.25/4=-2.3125。

(e) 指定动作后,不再除以四(2 分)

从 (1,2) 出发,用 V₂ 算动作值 U=-2.75,D=-2.75,L=-1,R=-2.75。最大数是 -1;对应动作 Left。负数中,越接近零越大。

2 questions × 10 points

IV. Calculation — Learning algorithms

20 points

D1. Repeated states: MC and online TD [10 points]

先把题目读懂

回合为 A 得2→B 得−1→A 得4→T,γ=0.5。常数步长方法初值 A=0、B=2,α=0.5。要求回报、首次访问 MC、重新计数的每次访问均值、在线 TD,并解释更新顺序。

第一步该想什么?

先列每次访问的完整回报。然后开三份独立草稿:首次访问只用第一次 A;样本均值平均两次 A 的回报;TD 按发生顺序改表,后面会读到前面刚改过的 A。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

An episode is A --2→ B --(-1)→ A --4→ T. γ=0.5. For constant-step-size algorithms initialize V(A)=0, V(B)=2 and use α=0.5. Run each named algorithm independently from these initial values.

(a) Compute G₀,G₁,G₂. [2]

(b) Apply first-visit MC with the stated constant α once per visited state. [2]

(c) Using ONLY this episode and fresh zero counts, compute every-visit sample-mean MC estimates. [2]

(d) Apply online TD(0) in chronological order; show the value after each update. [3]

(e) Explain why the TD update at the second transition uses a value that has already changed. [1]

下面跟着题目逐步算

先别把三个算法串起来

(b)、(c)、(d) 是独立实验;特别是 (c) 明确要求新计数的样本均值,不从 V(A)=0、V(B)=2 做常数步长更新。

(a) 三个回报(2 分)

G_2=4,\quad G_1=-1+0.5(4)=1,\quad G_0=2+0.5(1)=2.5

(b) 首次访问 MC(2 分)

A 只用第一次出现的回报 2.5:V(A)=0+0.5(2.5-0)=1.25。B 只出现一次:V(B)=2+0.5(1-2)=1.5。再次出现的 A 不再更新。

(c) 每次访问、样本均值(2 分)

A 两次出现对应回报 2.5 与 4,均值 (2.5+4)/2=3.25;B 只有回报 1,所以 V(B)=1。这不是把奖励 2 与 4 直接平均。

(d) 在线 TD 三步(3 分,每步 1 分)

V(A):0+0.5[2+0.5(2)-0]=1.5
V(B):2+0.5[-1+0.5(1.5)-2]=0.875
V(A):1.5+0.5[4+0-1.5]=2.75

最终 (2.75,0.875)。终点价值为零,但最后一步奖励 4 仍计入。

(e) 为什么读取 1.5(1 分)

在线更新意味着第一步处理后,表中的 A 已经改为 1.5;第二步的后继就是 A,因此读取当前表中的新值。只有题目明确冻结表时才使用旧的 A=0。

D2. Four targets from one transition [10 points]

先把题目读懂

旧 Q=1,奖励−1,γ=0.8,α=0.25;在线下一状态值 (5,2,0),实际下一动作 a₂;目标网络值 (1,4,3),ε=0.3。比较行为概率、SARSA、Q-learning、DQN、Double,以及终止情况。

第一步该想什么?

先把数据分成“在线表”“目标表”“实际动作”三个框。SARSA 取实际动作,Q-learning 取在线最大,DQN 取目标最大,Double 在线选后再去目标表查同一列。每种更新都从旧 Q=1 重启。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

A nonterminal transition has current Q(S,A)=1, reward r=-1, γ=0.8 and learning rate α=0.25. Online next-state values for (a₁,a₂,a₃) are (5,2,0). The actual next action is a₂. The behaviour is ε-greedy with ε=0.3. Target-network next-state values are (1,4,3). Compute each algorithm independently.

(a) Give the behaviour probabilities of a₁,a₂,a₃. [2]

(b) Give the SARSA target and updated Q(S,A). [2]

(c) Give the Q-learning target and updated Q(S,A). [2]

(d) Give the standard DQN and Double DQN targets. Show which next action each selects. [3]

(e) If the transition instead terminates, give its target and tabular update. [1]

下面跟着题目逐步算

通用更新先写在纸上

Q_{new}=Q_{old}+\alpha(y-Q_{old})

只有目标 y 随算法改变。不要把 ε 当学习率,也不要先做 SARSA 再把结果送进 Q-learning。

(a) 行为概率(2 分)

a₁ 唯一最优,概率 1-0.3+0.3/3=0.8;另两个动作各 0.1。

(b) SARSA(2 分)

实际下一动作 a₂,对应在线 Q=2。所以 y=-1+0.8×2=0.6,新值 1+0.25(0.6-1)=0.9。

(c) Q-learning(2 分)

取在线表最大值 5,对应 a₁。y=-1+0.8×5=3;新值 1+0.25(3-1)=1.5。

(d) DQN 与 Double(3 分)

DQN 看目标网络 (1,4,3),在 a₂ 达到最大 4,所以 y=-1+0.8×4=2.2。Double 先由在线网络 (5,2,0) 选 a₁,再读取目标网络同一动作的值 1,所以 y=-1+0.8×1=-0.2。

(e) 终止(1 分)

没有下一状态的回报,y=-1。表格更新 1+0.25(-1-1)=0.5。DQN 输出的数值即使非零也要被终止掩码去掉。

1 question, 4 subquestions

V. Calculation — Optimal policy

10 points

E1. An optimal policy with a tie [10 points]

先把题目读懂

X 的 safe 得2结束,travel 得0去Y;Y 的 collect 得4结束,cycle 得1回X;γ=0.5,旧策略是 travel、cycle。要评估、改进、检查全部最优策略,再做两轮价值迭代。

第一步该想什么?

旧策略下 X 与 Y 相互依赖,先联立两个式子。改进后重新检查每个动作是否并列;“最优价值只有一个”不意味着“最优动作只能一个”。价值迭代则另从全零开始。

这个前置概念还不懂?从具体例子重新学 →
展开英文原题

γ=0.5. In X, safe gives reward 2 and goes to T; travel gives reward 0 and goes to Y. In Y, collect gives reward 4 and goes to T; cycle gives reward 1 and goes to X. Start policy iteration with π₀=(travel,cycle).

(a) Evaluate π₀ exactly. [2]

(b) Compute all four qπ₀ values and make a greedy improvement π₁. [3]

(c) Evaluate π₁, verify Bellman optimality, and list ALL deterministic optimal policies. [3]

(d) From V₀=0, give the synchronous value-iteration vectors V₁ and V₂. [2]

下面跟着题目逐步算

题目关键:最优策略未必唯一

策略给的是动作,价值给的是数字。多个策略可以达到同一最优价值。

(a) 旧策略评估(2 分)

v_X=0.5v_Y,\quad v_Y=1+0.5v_X\quad\Rightarrow\quad(v_X,v_Y)=(2/3,4/3)

(b) 用旧价值算动作(3 分)

X: safe=2,travel=0.5×4/3=2/3;Y: collect=4,cycle=1+0.5×2/3=4/3。所以 π₁=(safe,collect)。

(c) 新价值与最优性(3 分)

新策略一步终止,vπ₁=(2,4)。现在重新比较:X 的 safe=2,travel=0.5×4=2,并列;Y 的 collect=4,cycle=1+0.5×2=2,collect 更好。

v^*_X=\max(2,0.5\times4)=2,\qquad v^*_Y=\max(4,1+0.5\times2)=4

满足 Bellman 最优方程,所以 v*=(2,4)。所有确定性最优策略为 (safe,collect) 与 (travel,collect)。不能漏掉 X 的并列动作。

(d) 价值迭代(2 分)

V₁(X)=max(2,0)=2,V₁(Y)=max(4,1)=4;再用这张表计算,V₂=(2,4),已经稳定。