Compare DP, Monte Carlo and TD(0) in terms of model requirements, sampled versus expected backups, bootstrapping, and whether an entire episode is needed. Explain the usual MC–TD bias/variance trade-off. [5 points]
下面跟着题目逐步算
按五个维度答题(每个维度 1 分)
维度
DP
MC
TD(0)
已知环境模型
需要
通常不需要
通常不需要
备份来源
对所有后继求模型期望
完整轨迹的样本回报
一步转移的样本目标
Bootstrapping
有
无
有
等待回合结束
不需要真实回合
标准 episodic MC 需要
不需要
第五分:偏差与方差
MC 完整回报在固定策略、正确采样条件下是价值的无偏样本,但跨越很多随机步骤,常有较高方差。TD 用当前价值估计接在一步奖励后,通常方差较小,但估计不准会引入自举偏差。
不要写成 MC 的有限样本估计永远等于真值,或 TD 在任何问题上方差都更小。这里描述的是常见取舍。
Explain why a policy greedy with respect to vπ is no worse than π in a finite discounted MDP. State the one-step comparison, explain the repeated-improvement intuition, and distinguish policy stability from unchanged values after one approximate sweep. [5 points]
Explain behaviour and target policies in Q-learning. Contrast its target with SARSA, and explain how exploration can affect their learned behaviour near a costly cliff. [5 points]
下面跟着题目逐步算
每一句一个得分点
① Behaviour policy 是真实收集数据时选动作的规则,可为 ε-greedy。② Target policy 是希望评价或改进的策略,Q-learning 的 max 对应贪心目标。
③ Q-learning 用 r+γmaxₐQ(s′,a),不要求下一步真实执行该最大动作。④ SARSA 用 r+γQ(s′,a′),把真实后续探索动作的后果包含在目标中。
State the mean-subtracted dueling aggregation formula. Explain the roles of the value and advantage streams, why an aggregation constraint is useful, and how dueling differs from Double DQN. [5 points]
下面跟着题目逐步算
五个得分点
① 正确公式;② V stream 表示状态共享的价值成分;③ A stream 区分各动作相对于状态基准的优劣;④ 直接 V+A 存在分解不唯一:给 V 加常数、给所有 A 减同一常数,Q 不变;中心化规定一种组合方式;⑤ Dueling 改网络结构,Double 改目标计算中的选择与评价,可同时使用。
例如 V=5、原始 A=(2,0),平均 A=1,输出 Q=(6,4)。原始 A 不要求已经零均值。
Why is function approximation useful when tabular methods are impractical? Explain generalization, a linear approximation and a semi-gradient value update. Mention a limitation of shared parameters. [5 points]
下面跟着题目逐步算
从一张大表变成一个函数
① 大状态空间或连续状态无法逐个存储和充分访问,所以用有限参数近似价值。② 相似状态通过特征共享信息,可对未访问状态作估计。
③ 给出线性形式,x 是状态特征、w 是待学权重。④ 更新把目标 y 暂时当常数;若 y=r+γV̂(s′,w) 也依赖 w,却不对目标求导,这称 semi-gradient。
States are A,B,C,T, with T terminal and γ=0.5. A gives reward 1 and transitions to B or C with probability 0.5 each. B gives reward 0 and moves to C. C gives reward 4 and terminates.
(a) Write the transition matrix and reward vector in order (A,B,C,T). [2]
(b) Compute all returns in the sampled episode A → B → C → T. [2]
(c) Compute the exact values of C, B and A by backward substitution. [2]
(d) Starting at V₀=0, give synchronous V₁,V₂,V₃ for (A,B,C). [2]
γ=0.5. At S, safe gives reward 2 and terminates; bold gives reward 5 and moves to T or L with probability 0.5 each. At L, quit gives reward 0 and terminates; recover gives reward -2 and returns to S. A policy chooses each available action with probability 0.5.
(a) Derive the two Bellman expectation equations. [2]
(b) Solve for vπ(S),vπ(L). [2]
(c) Calculate the four qπ values and a greedy improved policy. [2]
(d) Evaluate the improved policy and determine whether it is already optimal. Justify your answer by checking both actions at L. [2]
下面跟着题目逐步算
两层概率要分清
0.5 选 bold 是策略概率;bold 内部 0.5 到 L 是环境概率。两者都要乘,不能漏掉一个。
γ=0.5. In S, action a gives reward 1 and moves to S or U with probability 0.5 each; action b gives reward 0 and terminates. In U, action c gives reward 2 and terminates; action d gives reward 0 and moves to S.
(a) Write both Bellman optimality backup formulas. [1]
(b) From V₀=(0,0), compute V₁. [2]
(c) Compute V₂. [2]
(d) Compute V₃ and the actions selected in this third backup. [2]
(e) Evaluate the stationary policy (a,c) exactly and check Bellman optimality. [2]
Two episodes are observed in this order: (1) A --1→ B --2→ T; (2) A --2→ T. γ=1. For TD use α=0.5 and initial V(A)=V(B)=0. Independent methods reset to their specified initial conditions.
(a) List the return for each visit to A and B. [2]
(b) Compute first-visit sample-mean MC estimates using only these episodes. [2]
(c) Apply online TD(0) in the order the transitions were observed. Show all three updates. [2]
(d) Starting again at zero, perform ONE frozen batch TD sweep: compute TD errors using the initial zero table, average the errors separately for each state, then update each state once using α=0.5. [3]
(e) Explain why the two TD results need not agree. [1]
A nonterminal transition has Q(S,A)=-3, r=-2, γ=0.5 and α=0.2. Online next-state Q values (a₁,a₂,a₃) are (-2,-4,-1); the actual next action is a₁. Behaviour is ε-greedy with ε=0.2. Target-network values are (-3,-1,-2). Treat algorithms independently.
(a) Give the ε-greedy action probabilities. [2]
(b) Compute the SARSA target and update. [2]
(c) Compute the Q-learning target and update. [2]
(d) Compute DQN and Double DQN targets, identifying the selected actions. [3]
(e) Recompute the target and tabular update if this transition is terminal. [1]
γ=0.8. At S, stop gives reward 3 and terminates; wait gives reward 1 and returns to S. At U, exit gives reward 2 and terminates; join gives reward 0 and moves to S. Start with π₀=(stop,exit).
(a) Evaluate π₀. [2]
(b) Calculate all qπ₀ values and find a greedy π₁. [3]
(c) Evaluate π₁ and verify its optimality. [3]
(d) From V₀=0 give V₁ and V₂ under synchronous value iteration. Explain why they do not equal the final values. [2]