貝葉斯在線模型選擇

Bayesian Online Model Selection

貝葉斯在線模型選擇

https://arxiv.org/pdf/2602.17958

摘要

貝葉斯強盜（Bayesian bandits）中的在線模型選擇提出了一個根本性的探索挑戰：當環境實例是從先驗分布中采樣得到時，我們如何設計一種自適應策略，既能探索多個強盜學習器，又能在事后與其中最好的一個相競爭？我們通過引入一種用于隨機強盜在線模型選擇的新貝葉斯算法來解決這個問題。我們證明了貝葉斯遺憾（Bayesian regret）具有
的 Oracle 風格保證，其中 M 是基學習器的數量，是最優基學習器的遺憾系數， T 是時間范圍。我們還在一系列隨機強盜設置中對我們的方法進行了實證驗證，展示了其與最佳基學習器具有競爭力的性能。此外，我們研究了在基學習器之間共享數據的效果及其在緩解先驗誤設（prior mis-specification）中的作用。

1 引言

隨機強盜問題（stochastic bandit problem）是交互式決策的一個基礎模型 [Lattimore and Szepesvári, 2020]。在每一輪交互中，學習器從幾個動作中選擇一個，每個動作都關聯著一個未知的獎勵分布，并觀察從該分布中抽取的隨機獎勵。學習器的性能通常用遺憾（regret）來衡量：即所選動作的累積獎勵與該環境中最佳可能策略的累積獎勵之間的差值。目標是設計能夠實現次線性遺憾（sublinear regret）的算法，確保隨著學習器與環境交互次數的增加，其平均遺憾趨于消失。這個簡單而強大的框架捕捉了從（部分）反饋中學習的本質，并且處于許多現實世界應用的核心，例如推薦系統、機器人技術和金融 [Silva et al., 2022; Ni et al., 2023; Klarich et al., 2024]。

在其貝葉斯公式化中，隨機強盜問題假設未知獎勵分布上存在一個先驗分布，以捕捉關于環境的現有信念。這種視角催生了諸如 Thompson Sampling [Thompson, 1933; Russo et al., 2020] 等強大的算法，該算法通過從后驗分布中采樣并選擇對采樣實例最優的動作來誘導探索 [Agrawal and Goyal, 2012]。當可以通過易處理的后驗推斷（tractable posterior inference）來整合和更新先驗知識時（例如在存在共軛先驗的情況下），貝葉斯強盜特別具有吸引力。當共軛性不可用且精確推斷難以處理時，人們通常訴諸近似方法：馬爾可夫鏈蒙特卡洛（MCMC）方法，其漸近地逼近真實后驗；或者確定性替代方案，如拉普拉斯近似（Laplace approximations）和變分推斷（variational inference），它們提供了易處理的代理后驗 [Shahriari et al., 2016; Mazumdar et al., 2020]。

在本文中，我們研究了最初在頻率學派（frequentist）設定中引入的在線模型選擇問題 [Agarwal et al., 2017; Pacchiano et al., 2020b; Marinov and Zimmert, 2021]。在該問題中，學習者被給定一組有限的 bandit 算法（“模型”），我們將其稱為基學習器（base learners）。每個基學習器可能都適合不同的環境實例，例如，一個基學習器可能針對稀疏線性結構進行了調整，而另一個則針對低維廣義線性獎勵進行了優化。我們在貝葉斯（Bayesian）設定下研究這個問題，在交互開始時，環境是從一個已知的先驗分布中采樣的，并且學習者隨時間與該固定實例進行交互。在每一輪中，學習者選擇一個基學習器，遵循其策略選擇一個動作，并觀察產生的獎勵。我們的目標是設計一種貝葉斯模型選擇策略，該策略在貝葉斯遺憾（Bayesian regret）上具有預言機最優（oracle-best）保證：即在對從先驗中抽取環境的期望下，學習者的遺憾與一個預言機（oracle）的遺憾具有競爭力；該預言機知曉實現的環境實例，并會針對該實例固定選擇單個最佳的基算法。

現有的貝葉斯遺憾最小化方法，例如 Thompson 采樣（TS）及其變體，在隨機 bandit 問題中表現出強大的實證性能并享有次線性遺憾保證 [Zhang, 2022]。然而，它們并非專為在線模型選擇量身定制。經典 TS 是為決策集設計的，其中每個動作都有一個固定的獎勵分布；相比之下，在模型選擇中，學習者在基學習器之間進行選擇，每個基學習器本身就是一個 bandit 算法，其行為和性能隨著運行而演變。因此，識別實現環境下的最佳基學習器需要跨學習器的刻意元探索（meta-exploration），而不僅僅是單個學習者內部的動作層面探索。此外，標準 TS 通過后驗采樣進行探索，隨后針對采樣出的模型進行貪婪博弈（greedy play），并且沒有明確利用額外的結構信號（例如，某些動作的信息價值），而這些信號對于快速區分競爭的學習者可能至關重要。

這種局限性在具有“信息鎖”（information locks）的環境中變得尤為明顯，在這些環境中，某些動作在先驗中的每個環境下都是一致次優的，但對于哪些動作是最優的卻具有高度的信息量 [Brukhim et al., 2025; Pacchiano et al., 2023]。在這種設定下，故意查詢信息豐富動作的專用策略可以顯著優于標準 TS。這些觀察結果激發了一種用于在線模型選擇的貝葉斯方法，該方法能夠結合互補的算法行為并自動適應實現的環境實例。雖然先前的文獻已經為頻率學派設定下的模型選擇開發了預言機風格的保證 [Dann et al., 2024b; Cutkosky et al., 2021]，但具有可比理論保證的貝葉斯對應方法仍未被探索。為此，我們提出了一種用于一般隨機 bandit 問題的在線模型選擇的新貝葉斯算法。我們將我們的貢獻總結如下：

2 預備知識

貝葉斯序貫決策已經在一系列設定中得到了廣泛研究，包括強化學習、上下文老虎機（contextual bandits）以及更一般的部分觀測環境 [Fu et al., 2022; Ghavamzadeh et al., 2015]。

3 問題設定 (Problem Setup)

4 方法論與算法

貝葉斯在線模型選擇算法利用后驗樣本在整個訓練過程中估計基學習器的性能。在時刻 t ∈ [ T ] ，元學習器從后驗分布中采樣對應于每個動作的平均獎勵，

貝葉斯在線模型選擇算法的一個關鍵性質是，它在所有基學習器之間維護一個全局后驗分布，利用所有基學習器收集到的動作-獎勵對來更新該后驗分布。因此，盡管基學習器之間不進行直接通信，它們通過后驗分布共享信息，從而獲得了統計效率。貝葉斯在線模型選擇算法的偽代碼如算法 1 所示。

5 分析

在接下來的章節中，我們將提供算法 1 的理論分析。我們首先陳述我們的假設，以及我們在分析中使用的一些關鍵引理。然后，我們提供預言機最優保證（oracle-best guarantee）的證明概要，并指引讀者參閱附錄 A.1 以獲取完整證明。

5.1 假設

我們在分析中考慮以下假設：

5.2 關鍵引理

6 與 Thompson 采樣的比較

附錄中的圖 5 顯示，我們的算法（簡稱為 B-MS），當配備 K K 個隨時間推移具有不同固定臂選擇的基學習器時，其實現的貝葉斯遺憾與 Thompson 采樣高度重合。這提供了強有力的證據，表明在這種 的特殊情況下，我們的貝葉斯遺憾界與 TS 的既定界限相吻合，因為最優基學習器總是選擇最優臂，從而導致零遺憾。

7 實驗

為了評估我們算法的性能，我們進行了實驗研究，將我們提出的元學習器與基學習器的單獨運行進行了比較。給定從先驗分布中采樣的環境，該框架允許基學習器是不同的老虎機（bandit）算法，或者是具有不同配置的相同算法。

7.2 結果

我們的元學習器在 UCB 和 LinTS 老虎機設定中都實現了與表現最佳的基學習器相當的性能。平均累積遺憾曲線與最優基學習器緊密跟蹤，而最優動作選擇率提供了令人信服的證據：B-MS 算法在 UCB 設定（c = 1）中實現了與最佳基學習器幾乎相同的性能，并在 LinTS 設定（c = 0.16）中接近最佳表現者。

此外，我們的算法成功地避免了探索不足和過度探索。在圖 2 中，B-MS 的平均遺憾曲線呈現出次線性增長，這與在近乎貪婪的策略（c = 0.01, c = 0.1）中觀察到的近似線性遺憾累積形成了對比。同時，與那些過度探索的配置（c = 5, c = 10）相比，它保持了顯著更低的遺憾。圖 3 進一步證明，極端的參數選擇會導致次優行為：c = 0 代表一種純粹的利用策略，會迅速累積高額遺憾，而像 c = 25 這樣的大值則會引發過度探索，同樣導致性能不佳。元學習器成功適應了這些配置，其遺憾表現與最佳的 LinTS 變體相當。

我們還研究了在基學習器之間共享數據對元學習器性能的影響。結果如圖 1 所示。我們可以看到，在所有圖表中存在一個共同趨勢：共享數據提高了元學習器的性能，并使算法更加高效。這與我們的理論預期一致，因為共享數據使得每個基學習器能夠觀察到更多樣本，從而在其學習曲線上更快地進步。

我們在圖 1 中進一步挑戰了我們關于設定正確的先驗（well-specified prior）的假設 5.1。我們考慮元學習器設定錯誤（mis-specified），但其中一個基學習器設定正確的情況（圖 1b）。有趣的是，我們觀察到，即使元學習器設定錯誤，池中存在一個設定正確的基學習器也有助于元學習器從設定錯誤中恢復。在沒有任何設定正確的基學習器的情況下（即圖 1d 的設定），設定錯誤的元學習器不會表現出具有競爭力的性能，這反映了關于設定正確的先驗這一假設的重要性。

在最后一個實驗中，我們將基學習器指定為 Thompson 采樣算法和信息鎖求解器（Information Lock Solver）算法，并應用我們提出的元算法 1。如圖 4a 所示，元學習器成功地利用了這些基學習器的多樣化建模范式，實現了比樸素 Thompson 采樣基線更低的累積遺憾。重要的是，該框架并不局限于那些共享相同算法但僅通過超參數配置而有所不同的基學習器。

8 討論與未來工作

我們提出的算法適用于一個靈活的在線模型選擇框架，其中任何隨機老虎機（bandit）算法都可以作為基學習器。從理論角度來看，一個有趣的擴展是分析在線模型選擇的貝葉斯遺憾下界。正如 5.3 節所討論的，先前的工作 [Marinov and Zimmert, 2021] 已經為頻率學派設定下的在線模型選擇建立了
的下界，但貝葉斯下界仍然是一個未解決的問題。

從應用角度來看，該框架特別適用于在線超參數調優，在這種情況下，必須在有限的計算預算下自適應地評估多種算法或參數配置。更廣泛地說，我們的方法論涵蓋了隨機老虎機之外的應用，例如具有非線性獎勵結構的在線學習場景，或具有結構化先驗的強化學習，其中不同的基學習器編碼了不同的模型假設。

繼擴散 Thompson 采樣（Diffusion Thompson Sampling）以及 [Hsieh et al., 2023; Aouali, 2024] 的發展之后，一個有趣的方向是在貝葉斯在線模型選擇中利用擴散先驗（diffusion priors）。這一擴展將使得更具表達力的先驗分布成為可能，從而能夠涵蓋更廣泛變化的模型選擇問題。

9 結論

在本文中，我們研究了貝葉斯隨機老虎機（Bayesian stochastic bandits）中的在線模型選擇問題，并引入了貝葉斯在線模型選擇（Bayesian Online Model Selection）算法。我們的選擇策略利用從后驗分布中抽取的樣本來為每個基學習器計算一個勢函數。該勢函數提供了對實現遺憾（realized regret）的一種隨機估計，并且隨著后驗采樣的進行而不斷改進。

我們在多臂老虎機（multi-armed）和線性老虎機（linear bandit）算法的模型選擇任務上評估了我們方法的實證性能。我們的算法能夠調整 UCB 和 LinTS 的超參數，實現了與我們的理論分析相一致的實證性能。此外，實驗表明，在基學習器之間共享數據提高了算法的整體性能，這在元學習器具有誤設先驗（mis-specified prior）時尤為有益。

原文鏈接：https://arxiv.org/pdf/2602.17958