Bayesian Online Model Selection

Aida Afshar; Yuke Zhang; Aldo Pacchiano

cs.LGFeb 20, 2026

Bayesian Online Model Selection

Authors: Aida Afshar, Yuke Zhang, Aldo Pacchiano

Organizations: Boston University · Broad Institute of MIT and Harvard

Abstract

Online model selection in Bayesian bandits raises a fundamental exploration challenge: When an environment instance is sampled from a prior distribution, how can we design an adaptive strategy that explores multiple bandit learners and competes with the best one in hindsight? We address this problem by introducing a new Bayesian algorithm for online model selection in stochastic bandits. We prove an oracle-style guarantee of $O\left( d^* M \sqrt{T} + \sqrt{(MT)} \right)$ on the Bayesian regret, where $M$ is the number of base learners, $d^*$ is the regret coefficient of the optimal base learner, and $T$ is the time horizon. We also validate our method empirically across a range of stochastic bandit settings, demonstrating performance that is competitive with the best base learner. Additionally, we study the effect of sharing data among base learners and its role in mitigating prior mis-specification.

Figures & tables

n^{i_{t}}_{t+1}\leftarrow n^{i_{t}}_{t}+1,\quad n^{i^{\prime}}_{t+1}\leftarrow n^{i^{\prime}}_{t}\text{ for }i^{\prime}\neq i_{t},\quad\text{ and }\quad\mathcal{I}_{t+1}^{i}=\{l\in[t]:i_{l}=i\}\text{ for }i\in[M]

Algorithm 1 B-MS: Bayesian Online Model Selection Algorithm

Panel of Figure 1 — Figure 1: Empirical Bayesian regret for B-MS vs. TS base learners with different prior specifications ( $T=5\times 10^{3}$ , $R=500$ , $K=2$ , $M=4$ ).

Panel of Figure 2 — Figure 2: B-MS vs. UCB base learners with confidence radius $c$ ( $T=10^{3},R=100,K=5,M=6$ ).

Panel of Figure 3 — Figure 3: B-MS vs. LinTS base learners with confidence radius $c$ ( $T=1.5\times 10^{4},R=100,K=1000,M=5,d=10$ ).

Panel of Figure 4 — Figure 4: B-MS vs. base learners (TS and ILS algorithm) for $T=10^{3}$ , $R=60$ , $K=8$ , $M=3$ .

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

\text{UCB}_{\tau}(a)=\hat{\mu}_{\tau}^{i}(a)+c_{i}\sqrt{\frac{\log{(2\cdot\sum_{a\in\mathcal{A}}n_{\tau}^{i}(a)K)/\delta)}}{n_{\tau}^{i}(a)}}

Appendix

Algorithm 2 UCB for Multi-armed Bandit

V_{\tau+1}^{i}=V_{\tau}^{i}+a_{\tau}a_{\tau}^{\top}\quad\text{and}\quad\hat{\theta}_{\tau+1}^{i}=V_{\tau+1}^{i,-1}(\hat{\theta}_{\tau-1}V_{\tau}^{i}+a_{\tau}r_{\tau})

Appendix

Algorithm 3 Linear Thompson Sampling

Figure 5: Empirical Bayesian regret for B-MS vs. TS and Fixed Arm base learners with action index

a

(

T=10^{3},R=10^{3},K=M=5

)

Panel of Figure 6 — Figure 6: Optimal action selection rate for B-MS vs. TS base learners with prior specifications ( $T=5\times 10^{3}$ , $R=500$ , $K=2$ , $M=4$ )

Explore similar work

Offline-to-Online Learning in Linear Bandits
Jun 3, 2026Kushagra Chandak, Toshinori Kitamura, Xiaoqi TanMulti-Armed Bandits Contextual Bandits
Department of Computing Science, University of Alberta, Canada
Dynamic Decision-Making under Model Misspecification: A Stochastic Stability Approach
Feb 19, 2026Xinyu Dai, Daniel Chen, Yian QianThompson Sampling Model Misspecification
Department of Economics, Brown University. · Department of Applied Mathematics, Brown University.
Bayesian Nonparametric Thompson Sampling for Multi-Armed Bandits
Aug 8, 2018Iñigo Urteaga, Chris H. WigginsMulti-Armed Bandits Thompson Sampling
Department of Applied Physics and Applied Mathematics Data Science Institute Columbia University New York City, NY 10027

Jun 3, 2026J/K move · Enter open · S save

Offline-to-Online Learning in Linear Bandits

Kushagra Chandak, Toshinori Kitamura, Xiaoqi Tan

Department of Computing Science, University of Alberta, Canada

Multi-Armed Bandits Contextual Bandits

Open paper AskPDF arXiv

We study online learning with an additional offline dataset in the stochastic linear bandit setting. Although this problem arises frequently in practice, the offline-to-online tradeoff remains poorly understood in structured environments. We propose a linear bandit algorithm that balances this tradeoff: it relies on offline data during early rounds, and increasingly favors exploration as the horizon grows. We establish regret bounds showing that our method is simultaneously competitive with both purely online and purely offline solutions. In particular, it achieves sublinear regret relative to the optimal action in the number of online interactions, while its regret relative to an offline reference decreases as the number of offline samples grows. Empirical results further demonstrate its effectiveness across various problem parameters.

Abstract

Explore similar work

Offline-to-Online Learning in Linear Bandits

Dynamic Decision-Making under Model Misspecification: A Stochastic Stability Approach

Bayesian Nonparametric Thompson Sampling for Multi-Armed Bandits