最大累计回报（Return，$G_t$）#

回报是从 t 时刻开始，直到过程结束（或无限远）所获得的全部折扣奖励之和：

$G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$

• 如果 γ≈0，智能体变”近视”，只看重眼前利益。

• 如果 γ≈1，智能体变”远见”，更看重未来的长期收益。

状态价值函数（State Value Function, $V(s)$）#

价值函数用于衡量一个状态$s$的”好坏”。它的定义是该状态下回报的期望值：

$V(s) = \mathbb{E}[G_t | S_t = s]（蒙特卡洛 Monte Carlo）$

使用这个公式衡量一个状态的好坏，只能靠”硬算”未来的所有奖励之和。这需要有全局的视野，使得在数学和计算上都会遇到巨大的阻碍。后来人们使用 贝尔曼方程 去解决这一问题。

数学表达#

一个马尔可夫奖励过程通常由一个四元组$\langle S, P, R, \gamma \rangle$表示：

• S (State space)：有限的状态集合。

• P (Transition probability matrix)：状态转移概率矩阵。

• R (Reward function)：奖励函数，表示在状态 s 时能获得的即时奖励期望：

  $R_s = \mathbb{E}[R_{t+1} | S_t = s]$

• γ (Discount factor)：折扣因子，γ∈[0,1]，用于平衡当前奖励与未来长期奖励的权重。

策略（Policy, $π$）#

策略是智能体（Agent）的”行为指南”。它可以是确定性的，也可以是随机性的：

随机性策略：$π(a∣s)=P(A_t=a∣S_t=s)$，即在状态$s$下选择动作$a$的概率分布。

数学表达#

一个标准的马尔可夫决策过程通常由一个五元组 $\langle S, A, P, R, \gamma \rangle$来表示：

• S (State space)：有限的状态集合。

• A (Action space)：有限的动作集合。

• P (Transition probability matrix)：状态转移概率，表示在状态 s 采取动作 a 后，转移到状态 s ′的概率：

  $P(s' | s, a) = \mathbb{P}(S_{t+1} = s' | S_t = s, A_t = a)$

• R (Reward function)：奖励函数，表示在状态 s 采取动作 a 转移到 s′ 后获得的即时收益：

  $R(s, a, s') = \mathbb{E}[R_{t+1} | S_t = s, A_t = a, S_{t+1} = s']$

• γ (Discount factor)：折扣因子，$γ∈[0,1]$，用于平衡当前奖励与未来长期奖励的权重。

1. 场景建模#

• 状态 (S)：网络中的 5 个路由器节点$\{S_1, S_2, S_3, S_4, G\}$。

• 动作 (A)：选择将数据包转发给哪一个邻居节点。

• 奖励 (R)：每经过一条链路，由于存在延迟，奖励为负值。

  • 普通链路：R = -1。

  • 拥堵链路：R = -10。

  • 到达目标$G$：R = 0（过程结束）。

• 不确定性 (P)：网络是不稳定的，即使你选择了某条路径，由于链路抖动，数据包有 20% 的概率会被误传到另一个错误的节点。

2. 传统方式的困境：蒙特卡洛（Monte Carlo）穷举#

在传统思维中，我们要评估节点$S_1$ 的价值，必须进行大量的”全路径模拟”。

计算过程：

1. 采样路径 1：$S_1 \to S_2 \to S_4 \to G$，总回报$G_t = (-1) + (-1) + (-1) = -3$。

2. 采样路径 2（遇到拥堵和错误转向）：$S_1 \to S_3 \to S_2 \to S_4 \to G$，总回报$G_t = (-10) + (-1) + (-1) + (-1) = -13$。

3. 计算平均值：经过 1000 次这样的随机模拟，求出$S_1$ 的期望价值。

这种方式的致命缺点：

• 计算极其冗余：如果$S_1$ 和$S_3$ 都经过$S_4$ 到达$G$，传统方式会分别在两者的采样中重复计算$S_4 \to G$ 这段路程。

• 无法应对 “无限循环”：如果网络中存在环路（如 $S_2 \leftrightarrow S_3$），采样可能会陷入死循环，导致永远算不出结果。

3. 贝尔曼方式：迭代传播（Value Iteration）#

贝尔曼方程通过”空间换时间”和”局部一致性”，将问题拆解。它不急着去跑通全路径，而是在每个节点建立一个”价值档案”。

第 0 轮（初始化）：

所有节点都不知道自己离终点多远。

$V_0(S_1)=0, V_0(S_2)=0, V_0(S_3)=0, V_0(S_4)=0, V_0(G)=0$

第 1 轮（发现终点）：

只有紧挨着终点$G$ 的节点（假设是$S_4$）感知到了奖励。

根据贝尔曼更新规则：

$V_1(S_4) \leftarrow R(S_4 \to G) + \gamma V_0(G) = -1 + 0 = -1$

此时，$V_1(S_1)$依然是$0$。

第 2 轮（价值回传）：

连接$S_4$ 的节点（比如$S_2$）开始更新。

$V_2(S_2) \leftarrow R(S_2 \to S_4) + \gamma V_1(S_4) = -1 + 0.9 \times (-1) = -1.9$

第$k$ 轮（全网收敛）：

就像往水池里丢了一块石头（终点奖励），价值信息像涟漪一样，每经过一次迭代就向外扩散一圈。最终，$S_1$ 会通过邻居的”价值档案”计算出自己的最优价值，而无需亲自跑完一万次模拟。

4. 时序差分学习方式：边走边修正#

在 TD 看来，它既不需要上帝视角，也不需要像蒙特卡洛那样等数据包真的到家。

初始状态： 你对网络的初次印象非常模糊（随机初始化），假设你认为 V(S1)=−5,V(S2)=−5。

动作发生： 数据包从 S1 出发，经过链路到达了 S2。

关键瞬间：

1. 观察到的现实： 这一段链路花了 1 毫秒延迟（R=−1）。

2. 新的发现： 当你到达 S2 时，你低头看了一眼 S2 的”价值档案”，上面写着 V(S2)=−5。

3. 产生冲突（TD Error）：

• 旧的看法： 站在 S1 时，你以为价值是 −5。

• 新的依据： 走了一步后，你发现 S1 的价值应该是 这一步的开销(-1) + 下一站的预估(-5)，也就是 −6。

• 修正： 现实比你想象的更糟糕（误差为 −1）。你不会立刻把 V(S1) 改成 −6，而是用学习率 α（假设为 0.1）轻轻修正：

  $V(S1)←−5+0.1×[−1+(−5)−(−5)]=−5.1$