2026 RL Summer School Summary: Day 6

Day 5 从有限马尔可夫决策过程与贝尔曼方程出发，梳理了强化学习中的价值估计与最优控制。本文进一步在确定性 GridWorld 上实现两类表格型控制方法：一类利用显式环境模型进行规划，包括 Policy Iteration 与 Value Iteration；另一类直接从交互样本中学习，包括 Q-learning 与 SARSA。四种算法被组织在统一的 tabularRL package 中，从而清楚地区分环境模型、价值表示、决策规则与算法更新。

完整实现已发布至 GitHub：JulyThirteenth/tabularRL。仓库提供可编辑安装配置、环境依赖说明和四种算法的可复现运行入口，可作为表格型强化学习的最小教学实现。

1. Tabular RL Package

#

代码按“环境—共享抽象—具体算法”组织：

tabularRL/
├── grid_env/                 # GridWorld 环境与 Gymnasium 注册
├── dp_method/
│   ├── model.py              # 显式状态转移模型
│   ├── common.py             # DynamicProgramming
│   ├── policy_interation.py  # Policy Iteration
│   └── value_interation.py   # Value Iteration
└── td_learning/
    ├── common.py             # TabularTDAgent 与统一评估
    ├── q_learning.py         # Q-learning
    └── sarsa.py              # SARSA

内部模块统一使用 package import，例如：

from tabularRL.dp_method.common import DynamicProgramming
from tabularRL.td_learning.common import TabularTDAgent
import tabularRL.grid_env

克隆仓库后，可以使用 Python 3.10 及 Conda 创建独立环境：

git clone https://github.com/JulyThirteenth/tabularRL.git
cd tabularRL
conda create -n tabularrl python=3.10 -y
conda activate tabularrl
python -m pip install -e .

安装后，tabularRL 及其内置 GridWorld 可从任意工作目录导入。完整项目结构、算法说明和运行结果见仓库 README。

这种结构并不试图用同一个循环掩盖算法差异，而只复用状态编码、表格表示、Bellman backup、动作选择和评估等真正相同的部分。

2. GridWorld 与状态表示

#

GridWorld 的观测同时包含智能体位置与目标位置：

对于边长为 $n$ 的网格，完整状态空间大小为

坐标状态通过以下映射编码为表格索引：

环境具有四个离散动作，分别对应右、上、左、下。转移是确定性的，智能体到达目标时获得奖励 $1$，其余转移奖励为 $0$：

动态规划与 TD 控制虽然使用同一个 GridWorld，但访问环境信息的方式不同：

• DP 使用 GridWorldModel.transition(s, a) 查询任意状态—动作对；
• TD 方法使用 env.step(a)，只观察当前轨迹中实际发生的转移。

这一差异对应 model-based planning 与 model-free learning 的基本边界。

3. Model-based Dynamic Programming

#

3.1 共享 Bellman 抽象

#

DynamicProgramming 保存状态价值函数 $V$ 与确定性策略 $\pi$，并统一实现一步动作价值、Bellman sweep 和贪心策略提取。在确定性模型中，一步动作价值为

若 $s'$ 为终止状态，则 bootstrap 项取零。核心实现可概括为：

class DynamicProgramming:
    def action_value(self, state, action):
        next_state, reward, done = self.model.transition(state, action)
        bootstrap = 0.0 if done else self.value_function[next_state]
        return reward + self.discount_factor * bootstrap

    def bellman_sweep(self, backup):
        delta = 0.0
        for state in range(self.model.state_space):
            old_value = self.value_function[state]
            self.value_function[state] = (
                0.0 if self.model.is_terminal(state) else backup(state)
            )
            delta = max(delta, abs(old_value - self.value_function[state]))
        return delta

因此，两个 DP 算法共享相同的价值表示与 Bellman 计算，只在每次 sweep 使用的 backup operator 上不同。

3.2 Policy Iteration

#

策略迭代交替执行策略评估与策略改进。对当前确定性策略 $\pi_k$，策略评估反复应用贝尔曼期望备份：

直到

随后进行贪心策略改进：

在共享抽象之上，策略评估只需指定当前策略对应的 backup：

def policy_evaluation(self):
    while self.bellman_sweep(
        lambda state: self.action_value(state, self.policy[state])
    ) >= self.theta:
        pass

当贪心改进前后的策略完全一致时，策略迭代终止。

3.3 Value Iteration

#

价值迭代直接应用贝尔曼最优算子：

对应实现被压缩为一次共享 Bellman sweep：

def value_update(self):
    return self.bellman_sweep(
        lambda state: self.action_values(state).max()
    )

价值函数收敛后，再提取贪心策略

Policy Iteration 显式分离 evaluation 与 improvement；Value Iteration 则将策略改进隐含在每一步的 $\max$ 运算中。二者都是 Generalized Policy Iteration 的不同计算组织方式。

4. Model-free TD Control

#

4.1 共享表格型智能体

#

当完整模型不可用时，可以从样本转移

中直接更新动作价值。TabularTDAgent 统一负责：

1. 将字典观测编码为整数状态；
2. 维护 $Q(s,a)$ 表；
3. 执行 $\epsilon$-greedy 动作选择；
4. 在并列最优动作中随机选择，避免固定动作偏置；
5. 根据算法给出的 TD target 更新一个 Q 值。

共享更新写为

其中 $Y_t$ 由具体算法定义。

4.2 Q-learning

#

Q-learning 使用贪心 bootstrap target：

其行为策略仍可使用 $\epsilon$-greedy 探索，但更新目标对应贪心目标策略，因此属于 off-policy TD control：

def update(self, state, action, reward, next_state, done):
    td_target = reward + (
        0 if done else self.discount_factor * self.q_table[next_state].max()
    )
    self.update_toward(state, action, td_target)

4.3 SARSA

#

SARSA 使用行为策略实际选择的下一动作 $A_{t+1}$：

因此其更新显式依赖序列

算法名称 SARSA 即来自这五个量。由于学习目标与行为策略一致，它属于 on-policy TD control：

def update(self, state, action, reward, next_state, next_action, done):
    td_target = reward + (
        0
        if done
        else self.discount_factor * self.q_table[next_state, next_action]
    )
    self.update_toward(state, action, td_target)

这里没有进一步强行统一 Q-learning 与 SARSA 的轨迹循环，因为 SARSA 必须先选择并保留 $A_{t+1}$，而 Q-learning 的更新不需要该动作。保留这一差异能使 on-policy 与 off-policy 的边界在代码中保持可见。

5. Experimental Setting

#

所有实验均在 py10 环境中运行。两组实验使用不同网格规模，以分别验证精确规划与较大表格下的采样学习。

运行命令采用 package module 入口：

conda run -n py10 python -m tabularRL.dp_method.policy_interation
conda run -n py10 python -m tabularRL.dp_method.value_interation
conda run -n py10 python -m tabularRL.td_learning.q_learning
conda run -n py10 python -m tabularRL.td_learning.sarsa

6. Final Results

#

6.1 Dynamic Programming

#

目标位置固定为 $[2,2]$。Policy Iteration 与 Value Iteration 均在 9 次外层迭代后收敛，并得到相同策略：

> > v < <
> > v < <
> > T < <
> > ^ ^ ^
> > ^ ^ ^

其中 T 表示目标位置，其余符号表示对应状态下的贪心动作。对全部 625 个状态进行验证，结果如下：

两种方法的价值函数和策略完全一致，说明不同 Bellman 更新组织最终求得了同一个最优解。这里的“9 次迭代”含义并不完全相同：Policy Iteration 的一次外层迭代内部包含完整策略评估，而 Value Iteration 的一次迭代只包含一次最优 Bellman sweep，因此不能仅凭外层次数比较计算成本。

6.2 TD Control

#

训练结束后提取确定性贪心策略，并在一组固定的 500 个初始状态—目标组合上评估。评估阶段不再执行 $\epsilon$-greedy 探索。

在当前 GridWorld 中，两种方法表现接近。该环境没有悬崖或高代价危险区域，普通转移奖励为 0，因此 SARSA 不具备 Cliff Walking 中“学习更安全路径”的结构性优势。另一方面，10000 个训练回合相对于 10000 个可能状态仍不足以保证充分覆盖；未充分访问的状态会降低最终贪心策略的成功率。

因此，这组结果只能说明：在相同训练预算、相同超参数与相同评估初始状态下，两种 one-step TD control 方法取得了近似表现。若要比较算法总体优劣，还需要多随机种子统计、训练回报曲线、置信区间，以及具有风险—路径权衡的测试环境。

7. From Planning to Learning

#

四种算法可以通过 bootstrap target 统一理解：

DP 与 TD 方法都利用自举把后继状态的信息传播到当前状态，但它们解决信息缺失的方式不同：DP 枚举显式模型中的所有状态—动作对；TD 则只更新实际访问到的状态—动作对。Q-learning 进一步用最大化操作近似最优目标策略，SARSA 则把当前行为策略的探索影响保留在学习目标中。

8. Takeaway

#

本次实现得到以下几点认识：

1. Gymnasium 的 env.step() 是交互接口，不能替代动态规划所需的任意状态转移模型；显式 GridWorldModel 是 DP 抽象成立的前提。
2. Policy Iteration 与 Value Iteration 可以共享价值表示、Bellman backup、策略提取和展示逻辑，但应保留各自不同的迭代算子。
3. Q-learning 与 SARSA 可以共享状态编码、Q 表、$\epsilon$-greedy 和 TD 误差更新，但必须保留 off-policy 与 on-policy 的动作时序差异。
4. 单次成功率不是算法优劣的普遍结论。公平比较必须统一训练预算、评估状态与随机种子，并报告多次独立实验的不确定性。
5. 从 DP 到 TD 的核心变化不是贝尔曼思想消失，而是完整期望被样本 bootstrap 所替代。

整体而言，tabularRL 将经典表格型强化学习组织为一条连续主线：从显式模型上的精确规划，过渡到未知模型下的在线价值学习，并通过共享抽象展示不同算法之间真正相同与真正不同的部分。