強化學習（11）隨機近似

計算均值的新方法

有兩種方法。第一種方法很直接，即收集所有樣本后計算平均值；但這種方法的缺點是，若樣本是在一段時間內逐個收集的，我們必須等到所有樣本都收集完畢。第二種方法可避免此缺點，因為它以增量迭代的方式計算平均值，來幾個就計算幾個，不需要等了。

步驟

假設

由此可得

則有

最終推導出?增量更新公式：

一般性替換

此算法是一種特殊的?SA 算法（隨機近似算法），也是一種特殊的?隨機梯度下降算法

Robbins-Monro 算法?

隨機梯度下降算法是 RM 算法的特殊形式

RM算法的目的是在不知道方程表達式、只進行采樣的前提下求方程的解

為了求解 $g(\omega)=0$ 的解，我們采用 $\omega_{k+1}=\omega_k-a_k\widetilde{g}(\omega_k,\eta_k)$ （*），其中 $\widetilde{g}(\omega_k,\eta_k)$ 是第k次帶噪聲的觀測

具體的實現步驟是，輸入一個 $\omega_1$ ，我們可以得到一個帶噪聲的觀測值 $\widetilde{g_1}$ ，通過（*）式可以得到 $\omega_2$ ，又可以據此我們可以得到一個帶噪聲的觀測值 $\widetilde{g_2}$ ，由 $\widetilde{g_2}$ 通過（*）式可以得到 $\omega_3$ ......

如果我們能證明這樣的序列 $\omega_k,k=1,2,3\dots$ 會收斂于 $g(\omega)=0$ 的解 $\omega^*$ ，那這樣的一個算法就是可行的

下面我們引入Robbins-Monro定理來證明這個序列 $\omega_k,k=1,2,3\dots$ 收斂于 $g(\omega)=0$ 的解 $\omega^*$

Robbins-Monro定理

若有

滿足 $\sum_{k = 1}^{\infty} a_k = \infty, \sum_{k = 1}^{\infty} a_k^2 < \infty$ 的一個典型序列是 $\frac{1}{k}$ ，其無窮級數發散，其無窮平方和= $\frac{\pi^2}{6}$ ，實際常把 $a_k$ 選為足夠小的常數，這雖然違反條件，但是可以避免 $\frac{1}{k}$ 帶來的后端序列權重過低的問題

是一種特殊的RM算法

隨機梯度下降

Stochastic Gradient Descent (SGD)

隨機梯度下降算法是為了解決一個優化問題? $\begin{aligned} \min_{w} J(w) = \mathbb{E}[f(w, X)] \end{aligned}$

我們要優化 $\omega$ 來使 $J(\omega)$ 的值最小

$X$ 是隨機變量， $f$ 是 $\omega$ 和 $X$ 的函數； $X$ 這個隨機變量的概率分布已經給定但是暫時是未知的， $\begin{aligned} \mathbb{E}[f(w, X)] \end{aligned}$ 的 $\begin{aligned} \mathbb{E} \end{aligned}$ 就是對 $X$ 求期望； $\omega$ 和 $X$ 既可以是向量也可以是標量， $f$ 的值是標量

方法一：梯度下降GD

$\begin{aligned} w_{k+1} = w_k - \alpha_k \nabla_{w} \mathbb{E}[f(w_k, X)] = w_k - \alpha_k \mathbb{E}[\nabla_{w} f(w_k, X)] \end{aligned}$

隨機梯度下降通過在每次迭代中，沿著目標函數期望梯度的負方向來更新參數 $\omega$ ，逐步逼近目標函數的最小值點。實際應用中，由于計算整個數據集上目標函數的期望梯度（全量梯度）計算量過大，通常會采用小批量數據或者單個數據來近似計算期望梯度，從而實現高效的參數更新。

方法二：批量梯度下降BGD

$\begin{aligned} \mathbb{E}[\nabla_{w} f(w_k, X)] \approx \frac{1}{n} \sum_{i = 1}^{n} \nabla_{w} f(w_k, x_i) \quad w_{k + 1} = w_k - \alpha_k \frac{1}{n} \sum_{i = 1}^{n} \nabla_{w} f(w_k, x_i). \end{aligned}$

當?n = 1時，就是每次只用一個樣本進行梯度更新，即SGD；當?n?為整個數據集樣本數時，就退化為批量梯度下降。這種基于樣本近似計算梯度的方式，在大規模數據場景下極大地降低了計算復雜度，使得優化算法能夠高效運行

方法三：隨機梯度下降SGD

$\begin{aligned} w_{k + 1} = w_k - \alpha_k \nabla_{w} f(w_k, x_k) \end{aligned}$

式子等號右邊，原來的 $X$ 變成了對 $X$ 的隨機采樣 $x_k$ ；true gradient $\begin{aligned} \mathbb{E}[\nabla_{w} f(w_k, X)] \end{aligned}$ 變成了stochastic gradient $\begin{aligned} \nabla_{w} f(w_k, x_k) \end{aligned}$ 。這就是BGD里令n=1的情況

例子

考慮一個優化問題 $\begin{aligned} \min_{w} J(w) = \mathbb{E}[f(w, X)] = \mathbb{E}\left[ \frac{1}{2} \| w - X \|^2 \right] \end{aligned}$

其中 $\begin{aligned} f(w, X) = \frac{\| w - X \|^2}{2} \quad \nabla_{w} f(w, X) = w - X \end{aligned}$

其最優解為 $\begin{aligned} w^* = \mathbb{E}[X] \end{aligned}$

GD

$\begin{aligned} w_{k + 1} &= w_k - \alpha_k \nabla_{w} J(w_k) &= w_k - \alpha_k \mathbb{E}[\nabla_{w} f(w_k, X)] &= w_k - \alpha_k \mathbb{E}[w_k - X]. \end{aligned}$

SGD
$\begin{aligned} w_{k+1} = w_k - \alpha_k \nabla_{w} f(w_k, x_k) = w_k - \alpha_k (w_k - x_k) \end{aligned}$

收斂性

從GD到SGD：

$\begin{aligned} w_{k + 1} &= w_k - \alpha_k \mathbb{E}[\nabla_{w} f(w_k, X)] \\ &\Downarrow \\ w_{k + 1} &= w_k - \alpha_k \nabla_{w} f(w_k, x_k) \end{aligned}$

$\begin{aligned} \nabla_{w} f(w_k, x_k) \end{aligned}$ 可以看作是 $\begin{aligned} \mathbb{E}[\nabla_{w} f(w_k, X)] \end{aligned}$ 的帶噪聲的觀測值：

$\begin{aligned} \nabla_{w} f(w_k, x_k) = \mathbb{E}[\nabla_{w} f(w, X)] + \underbrace{\nabla_{w} f(w_k, x_k) - \mathbb{E}[\nabla_{w} f(w, X)]}_{\eta} \end{aligned}$

下面我們證明SGD是一個特殊的RM算法，由此來證明SGD在滿足某些條件的情況下是收斂的

proof:

SGD是要解決一個優化問題： $\begin{aligned} J(w) = \mathbb{E}[f(w, X)] \end{aligned}$ ，令 $J(w)$ 最小。這樣的優化問題可以轉化為尋找 $\begin{aligned} \nabla_{w} J(w) = \mathbb{E}[\nabla_{w} f(w, X)] = 0 \end{aligned}$ 的根，因為其梯度為0是取得極小值的必要條件。

下面即求 $\begin{aligned} g(w) = \nabla_{w} J(w) = \mathbb{E}[\nabla_{w} f(w, X)]=0 \end{aligned}$ 的根

我們用RM算法來求 $g(w)=0$ 的根

$\begin{aligned} \tilde{g}(w, \eta) &= \nabla_{w} f(w, x) \\ &= \underbrace{\mathbb{E}[\nabla_{w} f(w, X)]}_{g(w)} + \underbrace{\nabla_{w} f(w, x) - \mathbb{E}[\nabla_{w} f(w, X)]}_{\eta} \end{aligned}$

$\begin{aligned} w_{k + 1} = w_k - a_k \tilde{g}(w_k, \eta_k) = w_k - a_k \nabla_{w} f(w_k, x_k) \end{aligned}$ ?這實際上就是SGD算法

SGD算法的有趣性質

由于隨機梯度是隨機的，因此其近似并不精確，那么隨機梯度下降法（SGD）的收斂過程是緩慢的還是隨機的呢？

$\begin{aligned} \delta_{k} \leq \frac{\left| \nabla_{w} f(w_k, x_k) - \mathbb{E}[\nabla_{w} f(w_k, X)] \right|}{c \left| w_k - w^* \right|} \end{aligned}$

上述等式揭示了隨機梯度下降法（SGD）一種有趣的收斂模式：

BGD & MBGD & SGD

$\begin{aligned} w_{k + 1} &= w_k - \alpha_k \frac{1}{n} \sum_{i = 1}^{n} \nabla_{w} f(w_k, x_i), & \text{(BGD)} \\ w_{k + 1} &= w_k - \alpha_k \frac{1}{m} \sum_{j \in \mathcal{I}_k} \nabla_{w} f(w_k, x_j), & \text{(MBGD)} \\ w_{k + 1} &= w_k - \alpha_k \nabla_{w} f(w_k, x_k). & \text{(SGD)} \end{aligned}$

總結

參考文章

S. Zhao. Mathematical Foundations of Reinforcement Learning. Springer Nature Press, 2025. ?【【強化學習的數學原理】課程：從零開始到透徹理解（完結）】

https://www.bilibili.com/video/BV1sd4y167NS/?? p=2&share_source=copy_web&vd_source=52164f68a5f27ac2e86f0e7963ea966c?

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/88774.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/88774.shtml
英文地址，請注明出處：http://en.pswp.cn/web/88774.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！