Bayesian Online Model Selection

貝葉斯在線模型選擇

https://arxiv.org/pdf/2602.17958

摘要

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

1 引言

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

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

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

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

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

2 預(yù)備知識

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

3 問題設(shè)定 (Problem Setup)

4 方法論與算法

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

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

5 分析

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

5.1 假設(shè)

我們在分析中考慮以下假設(shè)：

5.2 關(guān)鍵引理

6 與 Thompson 采樣的比較

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

7 實驗

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

7.2 結(jié)果

我們的元學(xué)習(xí)器在 UCB 和 LinTS 老虎機設(shè)定中都實現(xiàn)了與表現(xiàn)最佳的基學(xué)習(xí)器相當(dāng)?shù)男阅?。平均累積遺憾曲線與最優(yōu)基學(xué)習(xí)器緊密跟蹤，而最優(yōu)動作選擇率提供了令人信服的證據(jù)：B-MS 算法在 UCB 設(shè)定（c = 1）中實現(xiàn)了與最佳基學(xué)習(xí)器幾乎相同的性能，并在 LinTS 設(shè)定（c = 0.16）中接近最佳表現(xiàn)者。

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

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

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

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

8 討論與未來工作

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

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

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

9 結(jié)論

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

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

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