序列决策问题的精确求解方法

### 序列决策问题的精确求解方法 在许多实际问题中，我们往往需要做出一系列决策，而非单一决策。这就涉及到序列决策问题，尤其是在随机环境下。本文将介绍用于解决这类问题的马尔可夫决策过程（MDP）以及相关的精确求解方法。 #### 1. 马尔可夫决策过程（MDP） MDP 是用于表示序列决策问题的数学模型，其中行动的效果是不确定的。下面我们详细了解其相关概念： - **基本元素**： - **状态空间（S）**：所有可能状态的集合。 - **行动空间（A）**：所有可能行动的集合。 - **状态转移模型（T）**：$T(s' | s, a)$ 表示在状态 $s$ 执行行动 $a$ 后转移到状态 $s'$ 的概率。 - **奖励函数（R）**：$R(s, a)$ 表示在状态 $s$ 执行行动 $a$ 时获得的期望奖励。 - **折扣因子（γ）**：用于处理无限期问题，范围在 0 到 1 之间。 以下是 MDP 的数据结构表示： ```julia struct MDP γ # discount factor 𝒮 # state space 𝒜 # action space T # transition function R # reward function TR # sample transition and reward end ``` - **马尔可夫假设**：下一个状态仅依赖于当前状态和行动，而与之前的状态和行动无关。 - **决策网络表示**：MDP 可以用决策网络表示，如图 7.1 和 7.2 所示。 - **奖励与效用**： - **有限期问题**：效用是奖励的总和，即 $\sum_{t=1}^{n} r_t$。 - **无限期问题**：有两种定义效用的方法： - **折扣回报**：$\sum_{t=1}^{\infty} \gamma^{t - 1} r_t$，其中 $0 \leq \gamma < 1$ 且奖励有限时，效用有限。 - **平均回报**：$\lim_{n \to \infty} \frac{1}{n} \sum_{t=1}^{n} r_t$。通常我们更关注折扣回报，因为它在计算上更简单。 - **策略**：策略告诉我们在给定状态和行动历史时应选择的行动。在 MDP 中，我们主要关注确定性策略，并且在无限期问题中，如果转移和奖励是平稳的，我们可以关注平稳策略。 - **最优策略与价值函数**： - **价值函数**：$U^{\pi}(s)$ 表示从状态 $s$ 执行策略 $\pi$ 的期望效用。 - **最优策略**：$\pi^*(s) = \arg \max_{\pi} U^{\pi}(s)$，即最大化期望效用的策略。 - **最优价值函数**：与最优策略相关的价值函数，记为 $U^*$。 #### 2. 策略评估 在计算最优策略之前，我们需要进行策略评估，即计算价值函数 $U^{\pi}$。有两种方法可以实现： - **迭代方法**： - 单步效用：$U^{\pi}_1(s) = R(s, \pi(s))$。 - 多步效用：$U^{\pi}_{k + 1}(s) = R(s, \pi(s)) + \gamma \sum_{s'} T(s' | s, \pi(s)) U^{\pi}_k(s')$。 以下是实现迭代策略评估的代码： ```julia function lookahead(𝒫::MDP, U, s, a) 𝒮, T, R, γ = 𝒫.𝒮, 𝒫.T, 𝒫.R, 𝒫.γ return R(s,a) + γ*sum(T(s,a,s′)*U(s′) for s′ in 𝒮) end function lookahead(𝒫::MDP, U::Vector, s, a) 𝒮, T, R, γ = 𝒫.𝒮, 𝒫.T, 𝒫.R, 𝒫.γ return R(s,a) + γ*sum(T(s,a,s′)*U[i] for (i,s′) in enumerate(𝒮)) end function iterative_policy_evaluation(𝒫::MDP, π, k_max) 𝒮, T, R, γ = 𝒫.𝒮, 𝒫.T, 𝒫.R, 𝒫.γ U = [0.0 for s in 𝒮] for k in 1:k_max U = [lookahead(𝒫, U, s, π(s)) for s in 𝒮] end return U end ``` 迭代更新是一个收缩映射，因此保证收敛。收敛时满足 Bellman 期望方程：$U^{\pi}(s) = R(s, \pi(s)) + \gamma \sum_{s'} T(s' | s, \pi(s)) U^{\pi}(s')$。 - **直接求解方法**：将 Bellman 期望方程转化为矩阵形式： - $U^{\pi} = R^{\pi} + \gamma T^{\pi} U^{\pi}$ - $(I - \gamma T^{\pi}) U^{\pi} = R^{\pi}$ - $U^{\pi} = (I - \gamma T^{\pi})^{-1} R^{\pi}$ 以下是实现直接求解的代码： ```julia function policy_evaluation(𝒫::MDP, π) 𝒮, R, T, γ = 𝒫.𝒮, 𝒫.R, 𝒫.T, 𝒫.γ R′ = [R(s, π(s)) for s in 𝒮] T′ = [T(s, π(s), s′) for s in 𝒮, s′ in 𝒮] return (I - γ*T′)\R′ ```