（链接未公开） 是一类非常常见的算法。在 RL 中，我们可以使用 DP 来递推计算价值。

策略迭代

策略评估

使用如下迭代方程，可以通过迭代计算一个给定策略 \pi 的价值函数：

上述方法进行一次迭代的时间复杂度是 O \left(|\mathcal{S}|^2 |\mathcal{A}| \right)。

策略提升

根据 策略提升定理，使用如下方法构造一个新的策略，就可以得到一个更好的策略：

价值迭代

根据 Markov 决策过程的 价值提升迭代算子，对价值函数 V_k(s) 使用以下迭代可以逐渐计算出最优价值：

进行一次价值迭代的时间复杂度是 O \left(|\mathcal{S}|^2 |\mathcal{A}| \right)，对于转移概率已知并且情形较小的 RL 问题可以接受。

求得最优价值 V^* 后，使用如下方法得到最优策略：

以上公式的含义是：\pi^*(a \, | \, s) 中，概率非 0 的 a 只能在 \arg \max_{a \in \mathcal{A}} 中取得，对于不能取得最大值的动作 a'，令 \pi^*(a' \, | \, s) = 0。可以直接将 \pi^* 实现为一个确定性策略，任取一个取得最大价值的动作。

应用

走迷宫问题

出口或陷阱的设置：此时通常设置这个状态为吸收态。

奖励的获取可能和下一个状态有关，此时要注意状态价值的定义是可获得的收益的期望，可能需要再代码中手动计算。

冰湖问题

冰湖（frozen lake）是走迷宫问题的变形，此时一个行动并不确定性地到达目标位置，而是以一定概率到达。

冰湖的环境代码如下。这里通过设置额外的吸收态 self.absorption，使得到达终点或者落入湖中（陷阱）的智能体不可能再返回，也不可能再获得奖励。

class FrozenLake:
    def __init__(self, nrow: int, ncol: int, holes: list[int]):
        self.nrow = nrow
        self.ncol = ncol
        self.n_states = nrow * ncol + 1
        # 0 for a empty slot, 1 for the terminal, -1 for a hole, 2 for an absorption
        self.states = np.zeros(self.n_states, dtype=np.int32)
        self.states[holes] = -1
        self.states[self.n_states - 2] = 1
        self.states[self.n_states - 1] = 2
        self.absorption = self.n_states - 1
        # for action: 0 for up, 1 for down, 2 for left, 3 for right.
        self.n_actions = 4
        # Initialize transition matrix and reward
        self.transition = np.zeros(
            (self.n_states, self.n_actions, self.n_states), dtype=np.float64
        )
        self.reward = np.zeros(
            (self.n_states, self.n_actions), dtype=np.float64
        )
        for action in range(self.n_actions):
            self.transition[self.absorption, action, self.absorption] = 1
        
        for x in range(nrow):
            for y in range(ncol):
                state = x * ncol + y
                if self.states[state] != 0:
                    if self.states[state] == -1:
                        reward = -100
                    elif self.states[state] == 1:
                        reward = 1000
                    # Terminate
                    for action in range(self.n_actions):
                        self.transition[state, action, self.absorption] = 1
                        self.reward[state, action] = reward
                    continue
                can_up = can_down = can_left = can_right = True
                if x == 0:
                    can_up = False
                if x == nrow - 1:
                    can_down = False
                if y == 0:
                    can_left = False
                if y == ncol - 1:
                    can_right = False
                for action in range(self.n_actions):
                    if can_up and action != 1:
                        next_state = (x - 1) * ncol + y
                        self.transition[state, action, next_state] = 1
                    if can_down and action != 0:
                        next_state = (x + 1) * ncol + y
                        self.transition[state, action, next_state] = 1
                    if can_left and action != 3:
                        next_state = x * ncol + y - 1
                        self.transition[state, action, next_state] = 1
                    if can_right and action != 2:
                        next_state = x * ncol + y + 1
                        self.transition[state, action, next_state] = 1
                    if (s := np.sum(self.transition[state, action])) != 0:
                        self.transition[state, action] *= 1 / s
    
    def step(self, state: int, action: int) -> tuple[int, float, bool]:
        """
        return (state, reward, is_end)
        """
        reward = self.reward[state, action]
        if self.states[state] != 0:
            return (-1, reward, True)
        distribution = self.transition[state, action]
        next_state = random.choices(np.arange(self.n_states), distribution)
        return (next_state, reward, False)

依据两个公式，使用 DP 可以获得冰壶问题的最优状态和策略：

v_state = np.zeros(env.n_states, dtype=np.float64)
v_state_old = np.zeros_like(v_state)
gamma = 0.95
for k in tqdm(range(10000)):
    v_state_old, v_state = v_state, v_state_old
    for state in range(env.n_states):
        v_state[state] = np.max([
            env.reward[state, action] + gamma * np.sum([
                env.transition[state, action, next_state] * v_state_old[next_state] 
                for next_state in range(env.n_states)
            ])
            for action in range(env.n_actions)
        ])

policy = np.zeros(env.n_states, dtype=np.int32)
for state in range(env.n_states):
    policy[state] = np.argmax([
        env.reward[state, action] + gamma * np.sum([
            env.transition[state, action, next_state] * v_state[next_state]
            for next_state in range(env.n_states)
        ])
        for action in range(env.n_actions)
    ])

np.array(list(map(lambda x: "^v<>"[x], policy)))[:-1].reshape(4, 4)

DP 的缺陷

使用 DP 求解 RL 时，要求我们已知转移概率 p(s' \, | \, s, a)，并且状态集合 \mathcal{S} 和动作集合 \mathcal{A} 都是取值较小的有限集。这在大多数情形下都是不可能的，特别是当引入神经网络时。许多强化学习的实际任务只能基于多次采样获得的轨迹来估计概率。