使用R中MDPToolbox解决离散吃蛋糕问题：策略为何显示超量吃蛋糕？

问题核心 #

你得到的不合理策略，本质是转移矩阵与奖励矩阵未对“动作（吃蛋糕数量）不能超过当前状态（剩余蛋糕数）”做合法性约束，导致算法认为“吃超过存量的蛋糕”是可行动作，进而得出违背实际的结果。

具体错误点 #

• 非法动作未被限制：你允许了如“剩余1块蛋糕时吃2/3块”这类不可能的动作，MDPToolbox会默认这类动作有效，转移逻辑完全混乱。
• 转移矩阵定义错误：没有针对非法动作设置正确的转移规则（比如这类动作的转移概率应为0，或直接排除），导致算法误以为可以凭空获取更多蛋糕。
• 奖励矩阵定义错误：非法动作的奖励未设置惩罚（比如负无穷），反而可能给了与合法动作相同的奖励，让算法优先选择高奖励但不符合实际的动作。

修正步骤 #

1. 明确合法的状态与动作映射 #

状态对应剩余蛋糕数：0、1、2、3（MDPToolbox中状态索引从1开始，对应状态0→索引1，状态3→索引4）。每个状态s仅允许动作0~s（即最多吃掉当前全部存量）。

2. 构建正确的转移矩阵与奖励矩阵 #

用循环生成符合约束的矩阵，示例代码：

library(MDPtoolbox)
# 状态数：4个（0,1,2,3），动作数：4个（0,1,2,3）
S <- 4
A <- 4
# 初始化转移矩阵（动作×当前状态×下一状态）
P <- array(0, dim = c(A, S, S))
# 初始化奖励矩阵，默认非法动作奖励为负无穷
R <- matrix(-Inf, nrow = A, ncol = S)

for (s in 0:(S-1)) {
  s_idx <- s + 1
  # 仅遍历当前状态下的合法动作
  for (a in 0:s) {
    a_idx <- a + 1
    next_s <- s - a
    next_s_idx <- next_s + 1
    # 合法动作的转移概率设为1（无随机）
    P[a_idx, s_idx, next_s_idx] <- 1
    # 奖励设为吃到的蛋糕数（可根据你的需求调整）
    R[a_idx, s_idx] <- a
  }
}

3. 重新运行策略迭代 #

# 无随机场景下折扣因子设为1
mdp_result <- mdp_policy_iteration(P, R, discount = 1)
# 输出最优策略：每个状态对应动作（索引-1为实际吃的蛋糕数）
print(mdp_result$policy - 1)

此时输出的最优策略会符合实际：状态3（剩余3块）→吃3，状态2→吃2，状态1→吃1，状态0→吃0，不会出现超量食用的情况。

内容的提问来源于stack exchange，提问作者EconJohn