Bayesian Online Model Selection

貝葉斯在線模型選擇

https://arxiv.org/pdf/2602.17958

摘要

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

1 引言

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

在其貝葉斯公式化中，隨機(jī)強(qiáng)盜問題假設(shè)未知獎(jiǎng)勵(lì)分布上存在一個(gè)先驗(yàn)分布，以捕捉關(guān)于環(huán)境的現(xiàn)有信念。這種視角催生了諸如 Thompson Sampling [Thompson, 1933; Russo et al., 2020] 等強(qiáng)大的算法，該算法通過從后驗(yàn)分布中采樣并選擇對采樣實(shí)例最優(yōu)的動(dòng)作來誘導(dǎo)探索 [Agrawal and Goyal, 2012]。當(dāng)可以通過易處理的后驗(yàn)推斷（tractable posterior inference）來整合和更新先驗(yàn)知識時(shí)（例如在存在共軛先驗(yàn)的情況下），貝葉斯強(qiáng)盜特別具有吸引力。當(dāng)共軛性不可用且精確推斷難以處理時(shí)，人們通常訴諸近似方法：馬爾可夫鏈蒙特卡洛（MCMC）方法，其漸近地逼近真實(shí)后驗(yàn)；或者確定性替代方案，如拉普拉斯近似（Laplace approximations）和變分推斷（variational inference），它們提供了易處理的代理后驗(yàn) [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）。每個(gè)基學(xué)習(xí)器可能都適合不同的環(huán)境實(shí)例，例如，一個(gè)基學(xué)習(xí)器可能針對稀疏線性結(jié)構(gòu)進(jìn)行了調(diào)整，而另一個(gè)則針對低維廣義線性獎(jiǎng)勵(lì)進(jìn)行了優(yōu)化。我們在貝葉斯（Bayesian）設(shè)定下研究這個(gè)問題，在交互開始時(shí)，環(huán)境是從一個(gè)已知的先驗(yàn)分布中采樣的，并且學(xué)習(xí)者隨時(shí)間與該固定實(shí)例進(jìn)行交互。在每一輪中，學(xué)習(xí)者選擇一個(gè)基學(xué)習(xí)器，遵循其策略選擇一個(gè)動(dòng)作，并觀察產(chǎn)生的獎(jiǎng)勵(lì)。我們的目標(biāo)是設(shè)計(jì)一種貝葉斯模型選擇策略，該策略在貝葉斯遺憾（Bayesian regret）上具有預(yù)言機(jī)最優(yōu)（oracle-best）保證：即在對從先驗(yàn)中抽取環(huán)境的期望下，學(xué)習(xí)者的遺憾與一個(gè)預(yù)言機(jī)（oracle）的遺憾具有競爭力；該預(yù)言機(jī)知曉實(shí)現(xiàn)的環(huán)境實(shí)例，并會(huì)針對該實(shí)例固定選擇單個(gè)最佳的基算法。

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

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

2 預(yù)備知識

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

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

4 方法論與算法

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

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

5 分析

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

5.1 假設(shè)

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

5.2 關(guān)鍵引理

6 與 Thompson 采樣的比較

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

7 實(shí)驗(yàn)

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

7.2 結(jié)果

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

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

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

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

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

8 討論與未來工作

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

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

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

9 結(jié)論

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

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

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