# 隨機近似法

## 簡介

在第五章，我們介紹了基於蒙地卡羅估計的第一類無模型增強學習算法。下一章（第七章）將介紹另一類無模型增強學習算法：時間差分學習。然而，在進入下一章之前，我們需要暫停，以更好地準備自己。這是因為時間差分算法與我們迄今為止研究的算法非常不同。許多讀者在首次接觸時間差分算法時常會疑惑這些算法是如何設計的，為什麼它們能夠有效地運行。事實上，之前的章節與後續章節之間存在一個知識鴻溝：到目前為止，我們研究的算法都是非增量的，而我們將要研究的算法則是增量的。

本章旨在通過介紹隨機近似的基本原理來填補這一知識鴻溝。儘管本章不介紹任何具體的增強學習算法，但它奠定了後續章節的必要基礎。我們將在第七章中看到，時間差分算法可以看作是一種特殊的隨機近似算法。本章還引入了機器學習中廣泛使用的隨機梯度下降算法。

## 6.1 動機範例：均值估計

我們將通過均值估計問題展示如何將一個非增量算法轉換為增量算法。假設隨機變量 $X$ 從有限集合 $X$ 中取值，我們的目標是估計 $E[X]$。假設我們有一組獨立同分布的樣本 $\{x_i\}_{i=1}^n$，則可以用以下方式近似 $X$ 的期望值：

$$
E[X] \approx \bar{x} = \frac{1}{n} \sum_{i=1}^n x_i
$$

這個估計方法在第五章中被稱為蒙地卡羅估計方法。根據大數法則，當 $n \to \infty$ 時，$\bar{x} \to E[X]$。

我們展示兩種計算均值 $\bar{x}$ 的方法。第一種是非增量方法，它先收集所有樣本，然後計算平均值。該方法的缺點在於，如果樣本數量較大，我們可能需要等待很長時間才能收集到所有樣本。第二種方法可以避免這一缺點，因為它以增量方式計算平均值。

假設我們用以下遞迴公式計算平均值：

$$
w_{k+1} = w_k - \frac{1}{k}(w_k - x_k)
$$
# 均值估計的增量公式推導

假設我們希望計算均值 $w_{k+1}$，並將其轉換為增量方式。首先，考慮傳統的均值定義：

$$
w_{k+1} = \frac{1}{k} \sum_{i=1}^k x_i
$$

為了簡化計算，我們希望在每次收到新樣本 $x_k$ 時就能更新均值，而不必重新計算所有樣本的和。

### 用 $w_k$ 表示前 $k-1$ 步的均值

首先，我們定義前 $k-1$ 步的均值 $w_k$ 如下：

$$
w_k = \frac{1}{k-1} \sum_{i=1}^{k-1} x_i
$$

因此，$\sum_{i=1}^{k-1} x_i$ 可以表示為 $(k-1)w_k$。現在，我們可以將 $w_{k+1}$ 的計算式改寫為：

$$
w_{k+1} = \frac{1}{k} \left( \sum_{i=1}^{k-1} x_i + x_k \right)
$$

代入 $\sum_{i=1}^{k-1} x_i = (k-1)w_k$，得：

$$
w_{k+1} = \frac{1}{k} \left( (k-1)w_k + x_k \right)
$$

### 展開和整理公式

進一步將公式展開並整理，我們得到：

$$
w_{k+1} = w_k - \frac{1}{k}(w_k - x_k)
$$

這樣的遞迴公式使得我們在每次新樣本到來時，只需依據當前均值 $w_k$ 和新樣本 $x_k$ 即可更新均值 $w_{k+1}$，而不必重新計算所有樣本的和。

這個算法可以在每次收到一個新樣本時立即更新均值。隨著樣本數量的增加，根據大數法則，估計精度也會逐漸提高。

## 6.2 Robbins-Monro 算法

隨機近似法是一類針對根求解或優化問題的隨機迭代算法。與其他根求解算法相比，隨機近似的優勢在於它不需要目標函數的表達式或其導數。

Robbins-Monro (RM) 算法是隨機近似領域的先驅工作。隨機梯度下降算法則是 RM 算法的一種特殊形式。假設我們希望找到方程 $g(w) = 0$ 的根，其中 $g : \mathbb{R} \rightarrow \mathbb{R}$ 是一個未知的函數。我們僅能得到 $g(w)$ 的帶有隨機噪聲的觀察值：

$$
\tilde{g}(w, \eta) = g(w) + \eta
$$

其中 $\eta$ 是觀察誤差。RM 算法表達式如下：

$$
w_{k+1} = w_k - a_k \tilde{g}(w_k, \eta_k)
$$

即便觀察值受噪聲干擾，RM 算法仍能使 $w_k$ 收斂至真根。

### 6.2.1 收斂特性

為什麼RM算法（公式 (6.5)）能找到 $g(w) = 0$ 的根？接下來我們將通過一個範例來說明這個概念，並提供嚴謹的收斂分析。

考慮範例，其中假設 $g(w) = \tanh(w - 1)$，此時 $g(w) = 0$ 的真實根是 $w^* = 1$。我們應用 RM 算法，設初始值為 $w_1 = 3$ 且 $a_k = \frac{1}{k}$。為了更好地展示收斂的原因，我們設 $\eta_k \equiv 0$，則 RM 算法簡化為 $w_{k+1} = w_k - a_k g(w_k)$。RM 算法生成的 $\{w_k\}$ 隨著 $k$ 的增加收斂至真實根 $w^* = 1$。

#### 收斂性分析

這個簡單例子顯示 RM 算法的收斂原因：

1. 當 $w_k > w^*$ 時，我們有 $g(w_k) > 0$，則 $w_{k+1} = w_k - a_k g(w_k) < w_k$。如果 $a_k g(w_k)$ 足夠小，我們會得到 $w^* < w_{k+1} < w_k$，結果是 $w_{k+1}$ 比 $w_k$ 更接近 $w^*$。

2. 當 $w_k < w^*$ 時，我們有 $g(w_k) < 0$，則 $w_{k+1} = w_k - a_k g(w_k) > w_k$。如果 $|a_k g(w_k)|$ 足夠小，我們會得到 $w^* > w_{k+1} > w_k$，結果是 $w_{k+1}$ 比 $w_k$ 更接近 $w^*$。

無論是哪種情況，$w_{k+1}$ 都比 $w_k$ 更接近 $w^*$。因此，我們可以直觀地認為 $w_k$ 會收斂到 $w^*$。

### Robbins-Monro 定理

**定理 6.1 (Robbins-Monro 定理)**
在公式 (6.5) 所描述的 RM 算法中，如果滿足以下條件，則 $w_k$ 幾乎必然（almost surely）收斂於滿足 $g(w^*) = 0$ 的根 $w^*$。

- (a) 對於所有 $w$ 都有 $0 < c_1 \leq \nabla_w g(w) \leq c_2$；
- (b) $\sum_{k=1}^{\infty} a_k = \infty$ 且 $\sum_{k=1}^{\infty} a_k^2 < \infty$；(不要太快為0)
- (c) $E[\eta_k | H_k] = 0$ 且 $E[\eta_k^2 | H_k] < \infty$；

此定理的證明將推遲到 6.3.3 節。
## 6.2.2 應用於均值估計

我們將應用 Robbins-Monro 定理來分析均值估計問題，這個問題已在第 6.1 節討論過。回顧增量均值估計算法：

$$
w_{k+1} = w_k + a_k(x_k - w_k)
$$

當 \( a_k = \frac{1}{k} \) 時，我們可以獲得 \( w_{k+1} \) 的解析表達式：

$$
w_{k+1} = \frac{1}{k} \sum_{i=1}^k x_i
$$

然而，在給定 \( a_k \) 的一般情況下，我們無法得到解析表達式，這時收斂分析變得非平凡。我們可以證明該算法是一種特殊的 RM 算法，因此它的收斂性自然由 **Robbins-Monro 定理** 保證。

### 將均值估計表示為根求解問題

具體來說，定義一個函數：

$$
g(w) = w - E[X]
$$

原問題的目標是估計 \( E[X] \) 的值，這個問題可以表述為求解 $g(w) = 0$ 的根。給定 $w$ 的值，我們可以得到一個噪聲觀測值：

$$
\tilde{g} = w - x
$$

其中 \( x \) 是 \( X \) 的樣本。因此，我們可以將 $\tilde{g}$表示為：

$$
\tilde{g}(w, \eta) = w - x = (w - E[X]) + (E[X] - x) = g(w) + \eta
$$

這裡的 $\eta = E[X] - x$ 是觀測誤差項。

### 利用 RM 算法進行均值估計

解決該問題的 Robbins-Monro 算法表達式為：

$$
w_{k+1} = w_k - a_k \tilde{g}(w_k, \eta_k) = w_k - a_k (w_k - x_k)
$$

這正是增量均值估計算法的更新公式，因此，我們可以將該均值估計算法視為 RM 算法的一個特例。

### 收斂性分析

由於這是一種 RM 算法的特殊情況，因此我們可以應用 Robbins-Monro 定理來確保收斂性。具體而言，如果步長序列 \( \{a_k\} \) 滿足以下條件：

1. $\sum_{k=1}^{\infty} a_k = \infty$，
2. $\sum_{k=1}^{\infty} a_k^2 < \infty$，

並且假設 \( \{x_k\} \) 是一組獨立同分布的樣本，則 \( w_k \) 幾乎必然收斂於 \( E[X] \)。

值得一提的是，該收斂性不依賴於 \( X \) 的分佈假設，只需滿足步長條件和樣本獨立同分佈的要求即可。

---

## 6.3 Dvoretzky 收斂定理

# Dvoretzky 定理的證明

## 定理陳述

考慮一個隨機過程：

$$
\Delta_{k+1} = (1 - \alpha_k)\Delta_k + \beta_k \eta_k
$$

其中 $\{\alpha_k\}_{k=1}^{\infty}$、$\{\beta_k\}_{k=1}^{\infty}$ 和 $\{\eta_k\}_{k=1}^{\infty}$ 是隨機序列。此處 $\alpha_k \geq 0$ 和 $\beta_k \geq 0$ 對於所有 $k$ 都成立。如果滿足以下條件，則 $\Delta_k$ 幾乎必然收斂於零：

1. $\sum_{k=1}^{\infty} \alpha_k = \infty$ 且 $\sum_{k=1}^{\infty} \alpha_k^2 < \infty$；
2. $\sum_{k=1}^{\infty} \beta_k^2 < \infty$；
3. $E[\eta_k | H_k] = 0$ 且 $E[\eta_k^2 | H_k] \leq C$，其中 $C$ 為常數，$H_k$ 表示歷史資訊，即 $\{ \Delta_j, \alpha_j, \beta_j, \eta_j \}_{j=1}^{k}$。

## 證明步驟

### 1. 定義輔助變量

設輔助變量 $h_k = \Delta_k^2$。則可以得到以下關係：

$$
h_{k+1} - h_k = \Delta_{k+1}^2 - \Delta_k^2
$$

### 2. 展開 $h_{k+1} - h_k$

代入 $\Delta_{k+1} = (1 - \alpha_k)\Delta_k + \beta_k \eta_k$，並展開得到：

$$
h_{k+1} - h_k = ((1 - \alpha_k) \Delta_k + \beta_k \eta_k)^2 - \Delta_k^2
$$

進一步展開右邊的平方項：

$$
= (1 - \alpha_k)^2 \Delta_k^2 + 2 (1 - \alpha_k) \Delta_k \beta_k \eta_k + \beta_k^2 \eta_k^2 - \Delta_k^2
$$

將其整理為：

$$
h_{k+1} - h_k = -\alpha_k (2 - \alpha_k) \Delta_k^2 + 2 (1 - \alpha_k) \Delta_k \beta_k \eta_k + \beta_k^2 \eta_k^2
$$

### 3. 對 $h_{k+1} - h_k$ 取條件期望

接下來，對 $h_{k+1} - h_k$ 取條件期望值 $E[\cdot | H_k]$：

$$
E[h_{k+1} - h_k | H_k] = E[-\alpha_k (2 - \alpha_k) \Delta_k^2 + 2 (1 - \alpha_k) \Delta_k \beta_k \eta_k + \beta_k^2 \eta_k^2 | H_k]
$$

由於 $\Delta_k$、$\alpha_k$ 和 $\beta_k$ 都包含在條件 $H_k$ 中，因此它們可以從期望中移出：

$$
E[h_{k+1} - h_k | H_k] = -\alpha_k (2 - \alpha_k) \Delta_k^2 + \beta_k^2 E[\eta_k^2 | H_k] + 2 (1 - \alpha_k) \Delta_k \beta_k E[\eta_k | H_k]
$$

根據條件 3，$E[\eta_k | H_k] = 0$，所以第三項為零。根據條件 $E[\eta_k^2 | H_k] \leq C$，我們有：

$$
E[h_{k+1} - h_k | H_k] \leq -\alpha_k (2 - \alpha_k) \Delta_k^2 + \beta_k^2 C
$$

### 4. 累加期望並使用準鞅收斂性

將上述不等式在 $k$ 上累加並取期望：

$$
\sum_{k=1}^{\infty} E[h_{k+1} - h_k | H_k] \leq \sum_{k=1}^{\infty} \left( -\alpha_k (2 - \alpha_k) \Delta_k^2 + \beta_k^2 C \right)
$$

由於條件 1 和條件 2，我們可以應用準鞅收斂性定理，得出 $h_k$ 幾乎必然收斂。

### 5. 確定 $\Delta_k \to 0$

從準鞅收斂性定理可以確定 $h_k$ 收斂，因此 $\Delta_k^2 \to 0$，即 $\Delta_k \to 0$ 幾乎必然成立。

## 結論

因此，我們證明了若滿足定理條件，則 $\Delta_k$ 幾乎必然收斂於零，這完成了證明。

---

## 6.4 隨機梯度下降

本節介紹機器學習領域廣泛應用的隨機梯度下降 (SGD) 算法。SGD 是 RM 算法的一種特殊形式，用於解決優化問題。

### 6.4.1 優化問題與隨機梯度下降

考慮優化問題：

$$
\min_w J(w) = E[f(w, X)]
$$

SGD 更新公式為：

$$
w_{k+1} = w_k - a_k \nabla_w f(w_k, x_k)
$$

當樣本數據逐漸增加，SGD 漸進地接近最佳解。

### 6.4.2 SGD 的收斂性分析

**定理 6.4 (SGD 收斂性)**
考慮 SGD 用於解決如下凸優化問題：

$$
\min_w J(w) = \mathbb{E}[f(w, X)]
$$

假設 $J(w)$ 是凸的，並且存在 $w^*$ 使得 $J(w^*) = \min_w J(w)$。若滿足以下條件，則 $w_k$ 幾乎必然收斂至 $w^*$：

(a) 梯度有限：存在常數 $C$ 使得對於所有 $w$ 和 $x$ 有 $ \|\nabla_w f(w, x)\| \leq C$。

(b) 步長：步長 $ \{a_k\} $ 滿足 $\sum_{k=1}^{\infty} a_k = \infty$ 和 $\sum_{k=1}^{\infty} a_k^2 < \infty$。

滿足條件的常用步長選擇包括 $a_k = \frac{1}{k}$ 和 $a_k = \frac{c}{\sqrt{k}}$。

### 6.4.5 收斂性證明

在強凸情況下，$J(w)$ 滿足：

$$
J(w) \geq J(w^*) + \frac{\lambda}{2} \|\Delta_k\|^2
$$

通過展開 SGD 的更新公式並取期望值，我們得到：

$$
\mathbb{E}[\|\Delta_{k+1}\|^2 | w_k] \leq (1 - a_k \lambda) \|\Delta_k\|^2 + a_k^2 C^2
$$

從而證明 SGD 的收斂性。

---

## 6.5 小結

本章介紹了隨機近似的基本概念，並詳細介紹了 Robbins-Monro 和 SGD 算法。這些算法奠定了後續增強學習技術的理論基礎。特別地，我們展示了均值估計作為一個隨機近似範例，並證明了 SGD 在求解涉及隨機變量的優化問題中的有效性。

## 6.6 問答

- **隨機近似是什麼？**
隨機近似是指一類用於求解根或優化問題的隨機迭代算法。

- **為什麼要學習隨機近似？**
因為第七章將介紹的時間差分增強學習算法可視為隨機近似算法。

- **RM 算法相比其他根求解算法有什麼優勢？**
RM 算法不需要目標函數或其導數的表達式，這使得它成為一種黑箱技術。

- **SGD 的基本原理是什麼？**
SGD 用於處理涉及隨機變量的優化問題，通過樣本估計而不是確定的概率分佈來解決問題。

- **SGD 能快速收斂嗎？**
當估計值遠離最佳解時，收斂速度較快；當估計值接近最佳解時，收斂速度會下降。