一个 agent 在 1×4 的走廊里移动，状态记为 S1、S2、S3、S4，动作只有向左(L)和向右(R)，在 S1 向左仍在 S1。每次状态转移的 reward 都是 -0.01；但转移到 S4 的那一次转移 reward 为 +1，并且回合立即终止。折扣因子 γ=0.9。请写出这个问题的 MDP 五元组（S、A、P、R、γ 的具体内容），并求出最优策略下 V*(S2) 的值，给出计算过程。

面试官在考什么

是否能把一个口语化场景翻译成 MDP 的形式化定义，并把终止状态、即时奖励和折扣回报算清楚。

MDP

回答框架 · 前两步

1. 五元组：S={S1,S2,S3,S4}；A={L,R}；P 为确定性转移（S1 向左自环，S4 为吸收终止态）；R 在一般转移为 -0.01、转入 S4 的那次为 +1；γ=0.9。
2. 终止状态的价值为 0，到达 S4 的那一步拿到 +1 后不再 bootstrap，因此 V*(S3)=-0.01+0.9×1=0.89 应修正为：V*(S3)=+1（若该步只给 +1）或 = -0.01+1 取决于奖励约定，关键是要说明奖励与后续价值不重复计算。

同一能力域的其他题

• 你要给一个 3 台 AGV 的仓库分拣场景建 MDP：决策频率 1 Hz，一个班次 8 小时（28800 步），要求班次结束前清空所有任务。你初始定 γ=0.99。请回答两件事：(1) 你会不会改这个 γ，改成多少，依据是什么，改完会连带影响哪些训练环节；(2) 如果状态只记录“每台 AGV 当前坐标 + 是否空闲”，它在什么情况下不满足马尔可夫性，你打算怎么判断，并补哪些量。
• 你要给一个仓库机器人调度问题建 MDP：状态=(机器人位置, 剩余电量, 已取货任务集合)。位置是 50x50 网格，电量 0-100，任务列表最多 20 个。粗算状态空间约 2.6e11，动作空间 20（去某个货架）。单次环境 step 平均 0.5ms，你有 8 张卡并行采样。有人提出用表格型 Q-Learning 精确求解。请你估算并判断：这个方案是否可行？如果不可行，你会优先降低状态空间还是降低动作空间？为什么？
• 你在给一个补货场景建模成 MDP：决策周期 1 天，动作是每个 SKU 的补货量，奖励是「毛利 − 缺货惩罚 − 持有成本」。团队里有人主张状态直接塞过去 14 天的日销量序列，有人主张只放当前库存 + 未来 7 天需求预测。你怎么判断哪些信息必须进状态、哪些可以丢？给出你会做的验证实验和判断标准，并说明状态维度放大会付出什么代价。
• 你用表格 Q-Learning 做一个离散库存补货问题，状态 200 个、动作 5 个，奖励是单步利润（可正可负）。学习率固定 0.1，ε 固定 0.2，跑了 10 万步以后发现 Q 值一直在某个区间来回震荡，贪心策略时好时坏。请说明：这算不算不收敛？可能的原因有哪些？你会按什么顺序排查和修？
• 场景：20 个货架的拣货路径优化，状态=(当前位置, 已拣货集合)，动作=去下一个货架。状态约 2^20 * 21 ≈ 2200 万，动作 20。你用表格型 Q-Learning 训练 500 万步，发现部分状态的 Q 值来回震荡不收敛。请给出一个具体的排查顺序，并说明每一步你会看什么指标、怎么改。
• 你手上只有一份历史运营日志：过去一年每天的定价决策由一套人工规则加运营干预产生，奖励是当天毛利。业务方要求你直接在这份日志上跑 Q-Learning 学一个新定价策略并替换规则。你会不会直接跑？如果不，你怎么改？并且说明你怎么判断改完之后这个策略能不能信。