差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
| 深度学习:强化学习 [2026/03/02 20:31] – 创建 张叶安 | 深度学习:强化学习 [2026/03/03 13:15] (当前版本) – [13.7.3 计算题] 张叶安 | ||
|---|---|---|---|
| 行 59: | 行 59: | ||
| 马尔可夫决策过程是强化学习的数学基础，为序列决策问题提供了一个严谨的建模框架。一个MDP由五元组$\langle S, A, P, R, \gamma \rangle$定义： | 马尔可夫决策过程是强化学习的数学基础，为序列决策问题提供了一个严谨的建模框架。一个MDP由五元组$\langle S, A, P, R, \gamma \rangle$定义： | ||
| - | - **状态空间$S$**：环境所有可能状态的集合。状态$s_t \in S$包含了智能体做决策所需的全部信息。 | + | |
| - | + | - **动作空间$A$**：智能体所有可能动作的集合。动作可以是离散的（如" | |
| - | - **动作空间$A$**：智能体所有可能动作的集合。动作可以是离散的（如" | + | - **状态转移概率$P$**：$P(s' |
| - | + | - **奖励函数$R$**：$R(s, | |
| - | - **状态转移概率$P$**：$P(s' | + | - **折扣因子$\gamma$**：$\gamma \in [0, |
| - | + | ||
| - | - **奖励函数$R$**：$R(s, | + | |
| - | + | ||
| - | - **折扣因子$\gamma$**：$\gamma \in [0, | + | |
| **马尔可夫性质**是MDP的核心假设：给定当前状态，未来状态的条件概率分布与历史状态无关。数学表达为： | **马尔可夫性质**是MDP的核心假设：给定当前状态，未来状态的条件概率分布与历史状态无关。数学表达为： | ||
| 行 278: | 行 274: | ||
| **Actor-Critic架构**结合了值函数估计和策略梯度： | **Actor-Critic架构**结合了值函数估计和策略梯度： | ||
| - | - **Actor（演员）**：策略网络$\pi(a|s, | + | |
| - | - **Critic（评论家）**：值函数网络$\hat{V}(s, | + | - **Critic（评论家）**：值函数网络$\hat{V}(s, |
| 使用TD误差代替累积回报： | 使用TD误差代替累积回报： | ||
| 行 308: | 行 304: | ||
| **问题**： | **问题**： | ||
| + | |||
| 1. 写出该MDP的五元组表示 | 1. 写出该MDP的五元组表示 | ||
| + | |||
| 2. 计算从(0, | 2. 计算从(0, | ||
| + | |||
| 3. 若采用随机策略（四个动作等概率），计算$V(0, | 3. 若采用随机策略（四个动作等概率），计算$V(0, | ||
| 行 315: | 行 314: | ||
| 1. **MDP五元组**： | 1. **MDP五元组**： | ||
| - | - $S = \{(i,j) | i,j \in \{0, | + | - $S = \{(i,j) | i,j \in \{0, |
| - | | + | - $A = \{\text{上}, |
| - | | + | - $P$是确定性的：$P((i', |
| - | | + | - $R((2,2), a) = +10$（终止），其他$R = -1$ |
| - | | + | - $\gamma = 0.9$ |
| 2. **最优路径**： | 2. **最优路径**： | ||
| - | 最优路径是走最短路径，如：右→右→下→下，或下→下→右→右。 | + | |
| + | 最优路径是走最短路径，如：右→右→下→下，或下→下→右→右。 | ||
| - | 路径：(0, | + | 路径：(0, |
| - | 累积奖励：$(-1) + (-1) \times 0.9 + (-1) \times 0.9^2 + 10 \times 0.9^3$ | + | 累积奖励：$(-1) + (-1) \times 0.9 + (-1) \times 0.9^2 + 10 \times 0.9^3$ |
| - | | + | |
| + | $= -1 - 0.9 - 0.81 + 7.29 = 4.58$ | ||
| 3. **随机策略的价值**： | 3. **随机策略的价值**： | ||
| - | 设$V(i, | + | |
| + | 设$V(i, | ||
| - | $$V(s) = -1 + \gamma \cdot \frac{1}{4}\sum_{s' | + | $$V(s) = -1 + \gamma \cdot \frac{1}{4}\sum_{s' |
| - | 设$V(2, | + | 设$V(2, |
| - | 平均需要较多步才能到达目标。估算$V(0, | + | 平均需要较多步才能到达目标。估算$V(0, |
| **例题2：Q-Learning更新** | **例题2：Q-Learning更新** | ||
| 智能体观察以下转移序列（$\gamma=0.9$，$\alpha=0.1$，初始$Q(s, | 智能体观察以下转移序列（$\gamma=0.9$，$\alpha=0.1$，初始$Q(s, | ||
| - | - $S_0=A, A_0=\text{右}, | + | |
| - | - $S_1=B, A_1=\text{右}, | + | - $S_1=B, A_1=\text{右}, |
| **问题**：计算两次Q值更新后的$Q(A, | **问题**：计算两次Q值更新后的$Q(A, | ||
| 行 372: | 行 374: | ||
| **问题**： | **问题**： | ||
| 1. 使用$\epsilon$-贪婪（$\epsilon=0.1$）策略，选择A的概率是多少？ | 1. 使用$\epsilon$-贪婪（$\epsilon=0.1$）策略，选择A的概率是多少？ | ||
| + | |||
| 2. 使用UCB（Upper Confidence Bound）策略，$c=2$，应该选择哪个摇臂？ | 2. 使用UCB（Upper Confidence Bound）策略，$c=2$，应该选择哪个摇臂？ | ||
| + | |||
| 3. 讨论$\epsilon$-贪婪和UCB的优缺点 | 3. 讨论$\epsilon$-贪婪和UCB的优缺点 | ||
| 行 378: | 行 382: | ||
| 1. **$\epsilon$-贪婪**： | 1. **$\epsilon$-贪婪**： | ||
| - | - 以$1-\epsilon=0.9$概率选择当前最优（A，因为$\hat{\mu}_A > \hat{\mu}_B$） | + | - 以$1-\epsilon=0.9$概率选择当前最优（A，因为$\hat{\mu}_A > \hat{\mu}_B$） |
| - | | + | - 以$\epsilon=0.1$概率随机选择（A或B各0.05） |
| - | | + | - 选择A的总概率：$0.9 + 0.05 = 0.95$ |
| 2. **UCB**： | 2. **UCB**： | ||
| - | 总拉动次数$n = 10 + 5 = 15$ | + | 总拉动次数$n = 10 + 5 = 15$ |
| - | $UCB_A = 0.7 + 2\sqrt{\frac{\ln 15}{10}} = 0.7 + 2\sqrt{0.27} = 0.7 + 1.04 = 1.74$ | + | $UCB_A = 0.7 + 2\sqrt{\frac{\ln 15}{10}} = 0.7 + 2\sqrt{0.27} = 0.7 + 1.04 = 1.74$ |
| - | $UCB_B = 0.3 + 2\sqrt{\frac{\ln 15}{5}} = 0.3 + 2\sqrt{0.54} = 0.3 + 1.47 = 1.77$ | + | $UCB_B = 0.3 + 2\sqrt{\frac{\ln 15}{5}} = 0.3 + 2\sqrt{0.54} = 0.3 + 1.47 = 1.77$ |
| - | 选择B（UCB值更高） | + | 选择B（UCB值更高） |
| 3. **优缺点分析**： | 3. **优缺点分析**： | ||
| - | - **$\epsilon$-贪婪**： | + | |
| - | | + | - 优点：简单易实现，计算开销小 |
| - | | + | - 缺点：探索是盲目的，持续以固定概率探索，不随知识增加而减少；对已充分探索的动作仍可能浪费探索 |
| - | - **UCB**： | + | |
| - | | + | - 优点：探索是有目的的，优先探索不确定性高的动作；随着采样增加，探索自然减少；有理论保证（对数遗憾界） |
| - | | + | - 缺点：需要知道尝试次数；在复杂环境（如MDP）中计算困难 |
| ===== 13.7 训练题 ===== | ===== 13.7 训练题 ===== | ||
| 行 437: | 行 441: | ||
| ==== 13.7.2 填空题 ==== | ==== 13.7.2 填空题 ==== | ||
| - | 1. MDP的五元组是：状态空间S、动作空间A、________、________、折扣因子$\gamma$。 | + | 1. MDP的五元组是：状态空间S、动作空间A、$\_\_\_\_$、$\_\_\_\_$、折扣因子$\gamma$。 |
| - | 2. 贝尔曼最优方程中，$V^*(s) = \max_a$________。 | + | 2. 贝尔曼最优方程中，$V^*(s) = \max_a$$\_\_\_\_$。 |
| - | 3. TD学习中，$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$被称为________。 | + | 3. TD学习中，$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$被称为$\_\_\_\_$。 |
| - | 4. Actor-Critic架构中，Actor负责________，Critic负责________。 | + | 4. Actor-Critic架构中，Actor负责$\_\_\_\_$，Critic负责$\_\_\_\_$。 |
| - | 5. 折扣因子$\gamma=0$时，智能体只关注________；$\gamma=1$时，智能体关注________。 | + | 5. 折扣因子$\gamma=0$时，智能体只关注$\_\_\_\_$；$\gamma=1$时，智能体关注$\_\_\_\_$。 |
| ==== 13.7.3 计算题 ==== | ==== 13.7.3 计算题 ==== | ||
| 1. 考虑以下MDP：状态$A, | 1. 考虑以下MDP：状态$A, | ||
| - | - 从$A$：动作1以概率1到$B$，奖励0；动作2以概率1到$C$，奖励+5 | + | |
| - | | + | - 从$B$：唯一动作以概率1到$C$，奖励+10 |
| - | | + | 设$\gamma=0.9$，计算最优价值$V^*(A)$和$V^*(B)$。 |
| 2. 使用Q-Learning（$\alpha=0.2$，$\gamma=0.9$），当前Q表如下： | 2. 使用Q-Learning（$\alpha=0.2$，$\gamma=0.9$），当前Q表如下： | ||
| + | | 状态 | 动作1 | 动作2 | ||
| + | | S1 | 5.0 | 3.0 | | ||
| + | | S2 | 2.0 | 4.0 | | ||
| - | | 状态 | 动作1 | 动作2 | | + | 观察到转移：$S_1 \xrightarrow{\text{动作2}} R=2 \rightarrow S_2$，更新$Q(S_1, |
| - | | + | |
| - | | S1 | 5.0 | 3.0 | | + | |
| - | | S2 | 2.0 | 4.0 | | + | |
| - | + | ||
| - | 观察到转移：$S_1 \xrightarrow{\text{动作2}} R=2 \rightarrow S_2$，更新$Q(S_1, | + | |
| 3. 在一个网格世界（4×4）中，从任意位置到目标的曼哈顿距离为$d$，每步奖励为-1，到达目标奖励为+10。设$\gamma=0.9$，写出最优策略下的价值函数表达式。 | 3. 在一个网格世界（4×4）中，从任意位置到目标的曼哈顿距离为$d$，每步奖励为-1，到达目标奖励为+10。设$\gamma=0.9$，写出最优策略下的价值函数表达式。 | ||
| 行 495: | 行 497: | ||
| 1. **解答**： | 1. **解答**： | ||
| - | 从$B$：唯一选择到$C$，$V^*(B) = 10 + \gamma \cdot 0 = 10$ | + | 从$B$：唯一选择到$C$，$V^*(B) = 10 + \gamma \cdot 0 = 10$ |
| - | 从$A$有两个选择： | + | 从$A$有两个选择： |
| - | | + | - 动作1：到$B$，价值为$0 + \gamma V^*(B) = 0.9 \times 10 = 9$ |
| - | | + | - 动作2：到$C$，价值为$5 + \gamma \cdot 0 = 5$ |
| - | 因此$V^*(A) = \max(9, 5) = 9$ | + | 因此$V^*(A) = \max(9, 5) = 9$ |
| - | **答案**：$V^*(A) = 9$，$V^*(B) = 10$ | + | **答案**：$V^*(A) = 9$，$V^*(B) = 10$ |
| 2. **解答**： | 2. **解答**： | ||
| - | Q-Learning更新：$Q(S_1, | + | Q-Learning更新：$Q(S_1, |
| - | $\max_a Q(S_2, a) = \max(2.0, 4.0) = 4.0$ | + | $\max_a Q(S_2, a) = \max(2.0, 4.0) = 4.0$ |
| - | 新值：$3.0 + 0.2 \times [2 + 0.9 \times 4.0 - 3.0]$ | + | 新值：$3.0 + 0.2 \times [2 + 0.9 \times 4.0 - 3.0]$ |
| - | | + | |
| - | | + | $= 3.0 + 0.2 \times [2 + 3.6 - 3.0]$ |
| - | | + | |
| + | $= 3.0 + 0.2 \times 2.6$ | ||
| + | |||
| + | $= 3.0 + 0.52 = 3.52$ | ||
| - | **答案**：更新后$Q(S_1, | + | **答案**：更新后$Q(S_1, |
| 3. **解答**： | 3. **解答**： | ||
| - | 设$d$为当前位置到目标的曼哈顿距离（最少步数）。 | + | 设$d$为当前位置到目标的曼哈顿距离（最少步数）。 |
| - | 最优策略下，每步向目标移动，实际经过$d$步到达目标。 | + | 最优策略下，每步向目标移动，实际经过$d$步到达目标。 |
| - | 价值函数为：$V^*(d) = (-1) + (-1)\gamma + (-1)\gamma^2 + ... + (-1)\gamma^{d-1} + 10\gamma^d$ | + | 价值函数为：$V^*(d) = (-1) + (-1)\gamma + (-1)\gamma^2 + ... + (-1)\gamma^{d-1} + 10\gamma^d$ |
| - | 前$d$项是等比数列：$-\frac{1-\gamma^d}{1-\gamma} = -\frac{1-0.9^d}{0.1} = -10(1-0.9^d) = -10 + 10 \times 0.9^d$ | + | 前$d$项是等比数列：$-\frac{1-\gamma^d}{1-\gamma} = -\frac{1-0.9^d}{0.1} = -10(1-0.9^d) = -10 + 10 \times 0.9^d$ |
| - | 加上终止奖励：$V^*(d) = -10 + 10 \times 0.9^d + 10 \times 0.9^d = -10 + 20 \times 0.9^d$ | + | 加上终止奖励：$V^*(d) = -10 + 10 \times 0.9^d + 10 \times 0.9^d = -10 + 20 \times 0.9^d$ |
| - | 简化：$V^*(d) = 20 \times 0.9^d - 10$ | + | 简化：$V^*(d) = 20 \times 0.9^d - 10$ |
| - | **答案**：$V^*(d) = 20 \cdot \gamma^d - 10 = 20 \times 0.9^d - 10$ | + | **答案**：$V^*(d) = 20 \cdot \gamma^d - 10 = 20 \times 0.9^d - 10$ |
张叶安