CS188：从搜索问题到 RL——人工智能决策算法的演进之路

UC Berkeley 的 CS188 课程（人工智能导论）以“构建智能体的决策能力”为核心，从经典的搜索算法到现代强化学习（Reinforcement Learning, RL），系统性地揭示了人工智能如何在复杂环境中规划路径、解决问题并优化策略。本文将沿着课程脉络，梳理从基础搜索到强化学习的演进逻辑，并探讨其背后的核心思想。

第一部分：确定性世界的决策基础——搜索问题

1. 搜索问题的数学定义

搜索问题的目标是找到从初始状态到目标状态的最优路径（或满足条件的可行路径）。其核心在于形式化环境的结构，使智能体能够系统化地探索可能的行动序列。

2. 搜索问题的构成要素

(1) 状态空间（State Space）

定义：所有可能状态的集合，描述智能体在环境中的可能配置。
示例：
- 迷宫问题：状态是坐标 (x, y)。
- 拼图游戏：状态是棋盘的布局（如八数码问题）。
- 机器人导航：状态是机器人的位置与朝向。

(2) 动作集合（Actions）

定义：在某个状态下可执行的操作集合，记为 Actions(s)。
示例：
- 迷宫中：{上, 下, 左, 右}。
- 拼图游戏：{空格与相邻数字交换}。
- 自动驾驶：{加速, 刹车, 左转, 右转}。

(3) 转移模型（Transition Model）

定义：函数 Result(s, a) → s'，描述在状态 s 执行动作 a 后到达的下一状态 s'。
示例：
- 迷宫中：Result((x,y), 上) → (x, y+1)（假设坐标系向上为y轴正方向）。
- 拼图游戏：Result(当前布局, 左移空格) → 新布局。

(4) 动作成本（Action Cost）

定义：从状态 s 通过动作 a 转移到 s' 的即时成本，记为 Cost(s, a, s')。
作用：用于衡量路径的优劣（如最短路径、最低能耗）。
示例：
- 迷宫中：每步成本为1（路径长度即总成本）。
- 导航问题：成本为道路长度或行驶时间。

(5) 初始状态（Start State）

定义：智能体开始执行任务时的初始配置。
示例：
- 罗马尼亚度假问题：初始状态是城市 Arad。
- 拼图游戏：初始状态是打乱的棋盘布局。

(6) 目标测试（Goal Test）

定义：函数 GoalTest(s) → True/False，判断状态 s 是否为目标状态。
示例：
- 迷宫问题：GoalTest((x,y)) → (x,y)是否为终点坐标。
- 拼图游戏：GoalTest(s) → s是否为目标布局。

3. 搜索问题的求解目标

智能体需要找到从初始状态到目标状态的最优路径（或可行路径），其中“最优”由路径总成本定义。例如：

最短路径：动作成本为1时，BFS可找到最优解。
最低成本路径：动作成本不同时，需使用一致代价搜索（UCS）。

4. 示例：罗马尼亚度假问题

状态空间：罗马尼亚城市（如Arad, Bucharest, Sibiu等）。
动作：从当前城市可直达的相邻城市（如从Arad可到Sibiu、Timisoara等）。
转移模型：Result(Arad, 前往Sibiu) → Sibiu。
动作成本：城市间的道路长度（如Arad到Sibiu为140公里）。
初始状态：Arad。
目标测试：当前城市是否为Bucharest。

求解目标：找到从Arad到Bucharest的最短路径（如Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest）。

5. 搜索问题与智能体的关系

理性决策：智能体需在有限计算资源下，选择能最大化未来累积奖励（或最小化成本）的行动。
搜索算法的角色：通过系统化地探索状态空间（如BFS、A*、UCS等），找到满足目标的最优路径。

6. 关键挑战

状态空间爆炸：状态数量可能随问题规模指数增长（如棋盘游戏）。
最优性与效率的权衡：如何在合理时间内找到最优解（如启发式搜索A*）。
动态环境：若环境变化（如交通拥堵），需重新规划路径（需结合在线搜索）。

总结

搜索问题的形式化定义为智能体提供了在复杂环境中规划行动的数学框架。通过明确状态空间、动作、转移模型等要素，结合适当的搜索算法（如BFS、A*、UCS），智能体能够高效地找到从初始状态到目标状态的最优路径。这一过程是构建理性规划智能体的基础，也是后续学习更高级算法（如强化学习）的前提。

[!NOTE] 搜索问题的解法
把搜索问题抽象成图论问题
把每个状态看成一个节点
把每个action 看成节点之间的有向边
用图的搜索算法来解决搜索问题

第二部分：不确定性与动态环境——从 MDP 到强化学习

1. 马尔可夫决策过程（MDP）

MDP 是建模随机环境的数学框架，包含：

状态 $s$ 、动作 $a$ 、转移概率 $T(s,a,s’)$：动作可能导致多个后续状态。
**奖励函数 $R(s,a,s’)$ **：定义每个状态的即时收益。
**折扣因子 $\gamma$ **：权衡当前与未来奖励。
求解方法：
值迭代：通过贝尔曼方程迭代更新值函数，收敛到最优策略。
- 公式： $$V_{k+1}(s) = \max_{a}\sum_{s'}T(s,a,s')[R(s,a,s')+\gamma V_{k}(s')]$$
  - 用 $s$ 的下一个状态 $s’$ 的第 $k$ 次迭代的V 值 $V_{k}(s’)$ 来更新第 $k+1$ 迭代的状态 $s$ 的V 值 $V_{k+1}(s)$
策略迭代：交替执行策略评估与改进，直接优化策略。两个步骤：
- 策略评价
  - 目标：计算当前策略 $\pi$ 的状态值函数 $V^\pi(s)$ 。
  - 方法：通过迭代求解贝尔曼期望方程： $$V^\pi(s) = \sum_{a} \pi(a|s) \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^\pi(s') \right]$$ 其中：
    - $R(s,a)$ 是即时奖励，
    - $P(s’|s,a)$ 是状态转移概率，
    - $\gamma$ 是折扣因子。
  - 终止条件：当值函数的变化小于阈值 $\theta$（如 $10^{-3}$）时停止迭代。
- 策略改进/策略提取
  - 目标：基于当前值函数 $V^\pi(s)$ 生成更优策略 $\pi’$ 。
    - 方法：对每个状态 $s$，选择使动作值函数 $Q^\pi(s,a)$ 最大的动作： $$\pi'(s) = \arg\max_{a} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^\pi(s') \right]$$
    - 若新策略 $\pi’$ 与原策略 $\pi$ 相同，则停止迭代；否则，用 $\pi’$ 替代 $\pi$ ，重复策略评估。

2. 强化学习（RL）：无模型的动态决策

RL 问题：仍然是MDP 模型，但是不知道 $T(s,a,s’)$ 或 $R(s,a,s’)$
- 两个主要问题：
  - 怎么从尝试过的动作中学习（被动RL）
    - 两种解决办法：
      - 基于模型的RL：尝试获取 $T(s,a,s’)$ 或者 $R(s,a,s’)$ ，从而变回MDP 问题，用策略迭代或者值迭代即可
      - 不基于模型的RL：不获取 $T(s,a,s’)$ 或者 $R(s,a,s’)$ ，直接通过 $Q$ 值来学习策略 $\pi$
  - 怎么基于学到的东西去选择执行的动作（在探索（尝试新动作以发现更好策略）和利用（选择当前最优动作）之间权衡）（主动RL）：
    - $\epsilon$ -贪心： $\epsilon$ 的概率随机探索（exploration）， $1-\epsilon$ 的概率采取利用（exploitation）当前数据得出的最佳值
    - exploration function
    - 等等

被动RL

基于模型的RL和不基于模型的RL 的区别：

[!NOTE] Title
左侧：基于数据去获取P（a），可以理解为对世界建模，理解概率的分布
右侧：基于采样的数据直接获取A 的期望，并不知道概率分布（对世界的具体模型没有了解）

不基于模型的RL：当环境模型未知时，强化学习通过试错直接学习策略。核心算法 Q 学习通过时序差分更新逐步逼近最优动作价值函数：
$$ Q (s, a) \leftarrow Q (s, a) + \alpha \left[ R (s, a) + \gamma \max_{a'} Q (s', a') - Q (s, a) \right] $$

[!NOTE] Q-learning 是离策略 (Off-policy)
离策略算法的核心是将目标策略（Target Policy）的学习与行为策略（Behavior Policy）的数据收集过程分离。
目标策略（π）：希望学习的最优策略，通常通过最大化期望回报得到（如 Q-learning 中的贪婪策略）。
行为策略（μ）：用于与环境交互、生成训练数据的策略，通常包含探索机制（如ε-greedy、Boltzmann 探索）。

特性	离策略（Off-Policy）	在线策略（On-Policy）
策略关系	目标策略 ≠ 行为策略	目标策略 = 行为策略
数据来源	可复用历史数据或外部数据	必须实时与环境交互生成新数据
典型算法	Q-learning、DQN、DDPG、SAC	SARSA、REINFORCE、PPO
数据效率	高（数据可重复使用）	低（需持续交互）
实现复杂度	高（需处理分布偏移）	低（策略一致性）

解释：
- 为什么学习 $Q$ 值而不是 $V$ 值：
  - 如果使用 V 值，智能体需要知道环境的动态模型（即状态转移概率 $T(s,a,s’)$ 和奖励函数 $R(s,a,s’)$ ），才能通过贝尔曼方程计算动作的期望价值. 而通过直接学习 Q(s,a)，绕过了对环境模型的依赖
  - Q值的灵活性与V值的不足：Q(s,a) 显式地为每个动作分配价值，允许智能体在探索（如随机动作）和利用（选择当前最优动作）之间灵活切换。若使用 V 值，智能体需要额外机制（如策略函数）将状态价值映射到动作选择，这会增加复杂度。

Q 学习 vs. MDP：

MDP 需已知环境模型（转移概率与奖励函数），RL 无需模型。
Q 学习通过经验（状态-动作-奖励序列）直接学习，适用于动态环境。

主动RL

$\epsilon$ - greedy
exploration function
- 把通过某个 action $a’$ 到达某个状态 $s’$ 的次数 $N(s’,a’)$ 纳入考虑，用 $f(Q(s’,a’), N(s’,a’))$ 取代原先的 $Q(s’,a’)$ $$Q(s,a) \leftarrow (1-\alpha)Q(s,a) + \alpha[R(s,a,s') + \gamma \max_{a'}f(Q(s',a'), N(s',a'))]$$

Approximate Q-learning 介绍

Approximate Q-learning 是经典 Q-learning 算法的扩展，旨在解决传统 Q-learning 在高维或连续状态空间中的维度灾难问题。其核心思想是通过函数逼近（Function Approximation）代替传统的表格（Tabular）存储，利用参数化的函数（如线性模型、神经网络）近似表示 Q 值，从而实现对大规模状态空间的泛化能力。

1. 为什么需要 Approximate Q-learning？

传统 Q-learning 的局限性
在表格型 Q-learning 中，Q 值存储为一个二维表 $Q(s, a)$，每个状态-动作对需要单独维护一个值。当状态空间巨大（如围棋的 $10^{170}$ 种状态）或连续（如机器人传感器数据）时，表格存储和更新变得不可行。
函数逼近的优势
使用参数化函数 $Q(s, a; \theta)$（如线性模型、神经网络）代替表格，通过调整参数 $\theta$ 逼近真实 Q 值。这种方法可以：
- 泛化：相似状态共享参数，避免重复学习。
- 处理连续状态：直接接受实数向量作为输入（如传感器数据）。
- 降低存储成本：参数规模远小于状态-动作组合数。

2. 算法原理

Approximate Q-learning 的更新规则基于传统 Q-learning，但引入函数逼近和梯度下降优化：

目标 Q 值计算
与传统 Q-learning 类似，目标 Q 值为：
$$\text{Target} = r + \gamma \max_{a'} Q(s', a'; \theta)$$
其中 $s’$ 是下一状态，$\gamma$ 是折扣因子。
损失函数与参数更新
定义损失函数为预测 Q 值与目标 Q 值的均方误差：
$$L(\theta) = \frac{1}{2} \left[ Q(s, a; \theta) - \text{Target} \right]^2$$
通过梯度下降更新参数 $\theta$：
$$\theta \leftarrow \theta - \alpha \nabla_\theta L(\theta)$$
其中 $\alpha$ 是学习率，梯度方向由链式法则计算：
$$\nabla_\theta L(\theta) = \left( Q(s, a; \theta) - \text{Target} \right) \nabla_\theta Q(s, a; \theta)$$

伪代码示例

1
2
3
4
5
6
7
8
9
for each episode:
    initialize state s
    while not terminal:
        choose action a via ε-greedy(Q(s, a; θ))
        execute a, observe reward r and next state s'
        target = r + γ * max_a' Q(s', a'; θ)
        loss = 0.5 * (Q(s, a; θ) - target)^2
        θ = θ - α * (Q(s, a; θ) - target) * ∇θ Q(s, a; θ)
        s = s'

3. 函数逼近方法

线性函数逼近
用线性组合表示 Q 值：
$$Q(s, a; \theta) = \theta^T \phi(s, a)$$

其中 $\phi(s, a)$ 是状态-动作的特征向量（如人工设计的特征或自动编码的特征）。
非线性函数逼近（如神经网络）
使用深度神经网络（DQN）自动提取状态特征：
$$Q(s, a; \theta) = \text{NeuralNetwork}(s, a; \theta)$$

深度 Q 网络（DQN）通过经验回放（Experience Replay）和目标网络（Target Network）稳定训练。

4. 优缺点分析

优点	缺点
可处理高维/连续状态空间	收敛性不保证（函数逼近可能发散）
泛化能力强，避免维度灾难	需谨慎设计特征或网络结构
适用于真实场景（如图像、传感器输入）	超参数（学习率、网络架构）敏感

5. 应用场景

游戏 AI：如 Atari 游戏（DQN 直接以像素为输入）
机器人控制：连续传感器数据映射到动作（如机械臂抓取）
资源调度：大规模状态空间下的动态决策（如云计算资源分配）

6. 扩展与改进

深度 Q 网络（DQN）：结合神经网络与经验回放、目标网络（见 Nature DQN）。
Double Q-learning：减少最大化偏差（Maximization Bias）。
Dueling DQN：分离状态价值 $V(s)$ 和动作优势 $A(s, a)$，提升策略评估效率。

1. 策略搜索（Policy Search）

当基于特征的策略难以通过 Q-learning 直接优化时，策略搜索通过直接优化策略参数（而非 Q 值）提升性能。

核心思想
- Q-learning 的局限：Q-learning 优先准确估计 Q 值（建模），但特征设计的偏差可能导致策略次优。
- 策略搜索的目标：直接优化策略参数，最大化累积奖励（预测），而非精确拟合 Q 值。
方法分类
- 简单策略搜索：通过扰动特征权重（如线性 Q 函数的权重），评估策略改进方向（需大量采样）。
- 策略梯度（Policy Gradient）：基于蒙特卡洛采样，通过梯度上升更新策略参数，使高奖励轨迹的动作概率增加。
- 近端策略优化（PPO）：改进策略梯度，限制策略更新的幅度，提升训练稳定性。
应用场景
- 连续动作空间（如机器人关节控制）：Q-learning 需计算 $\max_a Q(s,a)$，而连续动作难以枚举，策略搜索直接输出动作分布。
- 高维/复杂策略（如语言生成）：直接优化生成策略（如选择下一个词的概率分布）。

2. 案例分析（Case Studies）

强化学习在多个领域展现强大能力，以下是三个典型应用：

案例 1：Atari 游戏（Atari Game Playing）

MDP 设置
- 状态：游戏屏幕的像素（$84 \times 84$ 图像）。
- 动作：手柄按键组合（如 18 种离散动作）。
- 挑战：状态空间巨大（$256^{84 \times 84}$），无法使用表格法。
解决方案
- 深度 Q 网络（DQN）：用卷积神经网络逼近 Q 值，结合经验回放和目标网络稳定训练。
- 探索策略：ε-greedy 平衡探索与利用。

案例 2：机器人运动控制（Robot Locomotion）

MDP 设置
- 状态：机器人传感器数据（关节角度、加速度等连续向量）。
- 动作：电机指令（连续向量）。
- 挑战：真实世界训练成本高、风险大。
解决方案
- 仿真训练迁移：先在模拟器中训练策略，再部署到真实机器人。
- 策略搜索方法：PPO 优化连续动作策略，最大化前进速度、保持平衡等奖励。

案例 3：语言助手（Language Assistants）

MDP 设置
- 状态：已生成的文本序列（如“What is population of Berkeley?”）。
- 动作：选择下一个词（词汇表大小约 10 万）。
- 奖励：人工标注或奖励模型（如回答准确性、流畅性）。
解决方案
- 策略梯度：直接优化生成策略，调整词的概率分布。
- 挑战：动作空间极大（10 万词），需高效采样与梯度估计。

3. 后续方向与总结

课程后续内容：转向 不确定性（Uncertainty） 与 学习理论（Learning），涵盖贝叶斯网络、隐马尔可夫模型等。
强化学习的核心挑战：
- 探索与利用的平衡：如何在复杂环境中高效探索（如基于好奇心的内在奖励）。
- 样本效率：减少真实环境中的交互次数（如元学习、模仿学习）。
- 安全与鲁棒性：确保策略在真实场景中的可靠性（如安全约束强化学习）。

CS188从搜索问题，MDP到RL

【技术要点】基于MDP与Q学习的RL框架实现动态决策优化【核心价值】通过无模型强化学习解决状态空间爆炸问题