Bayesian Online Model Selection

• URL: http://arxiv.org/abs/2602.17958v1
• Date: Fri, 20 Feb 2026 03:23:55 GMT
• Title: Bayesian Online Model Selection
• Authors: Aida Afshar, Yuke Zhang, Aldo Pacchiano,
• Abstract summary: We prove an oracle-style guarantee of $Oleft$ 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.<n>We validate our method empirically across a range of bandit settings, demonstrating performance that is competitive with the best base learner.
• Score: 26.288734995761516
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Lift What You Can: Green Online Learning with Heterogeneous Ensembles [3.5523355921740163]
  We present a policy for choosing which models to train on incoming data.<n>Most notably, we propose the novel $zeta$-policy, which focuses on training near optimal models at reduced costs.<n>In our experiments across 11 benchmark datasets, we find empiric evidence that our $zeta$-policy is a strong contribution to the state-of-the-art.
  arXiv  Detail & Related papers  (2025-09-23T13:14:37Z)
• Online Learning with Probing for Sequential User-Centric Selection [8.45399786458738]
  We present a probing-augmented user-centric selection (PUCS) framework, where a learner first probes a subset of arms to obtain side information on resources and rewards, and then assigns $K$ plays to $M$ arms.<n>For the offline setting with known distributions, we present a greedy probing algorithm with a constant-factor approximation guarantee $zeta = (e-1)/ (2e-1)$.<n>For the online setting with unknown distributions, we introduce OLPA, a bandit algorithm that a regret a bound $mathcalO(sqrtT +
  arXiv  Detail & Related papers  (2025-07-27T03:32:51Z)
• BAPE: Learning an Explicit Bayes Classifier for Long-tailed Visual Recognition [78.70453964041718]
  Current deep learning algorithms usually solve for the optimal classifier by emphimplicitly estimating the posterior probabilities.<n>This simple methodology has been proven effective for meticulously balanced academic benchmark datasets.<n>However, it is not applicable to the long-tailed data distributions in the real world.<n>This paper presents a novel approach (BAPE) that provides a more precise theoretical estimation of the data distributions.
  arXiv  Detail & Related papers  (2025-06-29T15:12:50Z)
• Best Policy Learning from Trajectory Preference Feedback [11.896067099790962]
  Preference-based Reinforcement Learning (PbRL) offers a more robust alternative.<n>We study the best policy identification problem in PbRL, motivated by post-training optimization of generative models.<n>We propose Posterior Sampling for Preference Learning ($mathsfPSPL$), a novel algorithm inspired by Top-Two Thompson Sampling.
  arXiv  Detail & Related papers  (2025-01-31T03:55:10Z)
• Anytime Model Selection in Linear Bandits [61.97047189786905]
  We develop ALEXP, which has an exponentially improved dependence on $M$ for its regret. Our approach utilizes a novel time-uniform analysis of the Lasso, establishing a new connection between online learning and high-dimensional statistics.
  arXiv  Detail & Related papers  (2023-07-24T15:44:30Z)
• Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
  We study the problem of online generalized linear regression in the setting of a generalized linear model with possibly unbounded additive noise. We provide a sharp analysis of the classical follow-the-regularized-leader (FTRL) algorithm to cope with the label noise. We propose an algorithm based on FTRL to achieve the first variance-aware regret bound.
  arXiv  Detail & Related papers  (2022-02-28T08:25:26Z)
• Universal and data-adaptive algorithms for model selection in linear contextual bandits [52.47796554359261]
  We consider the simplest non-trivial instance of model-selection: distinguishing a simple multi-armed bandit problem from a linear contextual bandit problem. We introduce new algorithms that explore in a data-adaptive manner and provide guarantees of the form $mathcalO(dalpha T1- alpha)$. Our approach extends to model selection among nested linear contextual bandits under some additional assumptions.
  arXiv  Detail & Related papers  (2021-11-08T18:05:35Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  Intrinsic rewards play a central role in handling the exploration-exploitation trade-off. We introduce emphanti-concentrated confidence bounds for efficiently approximating the elliptical bonus. We develop a practical variant for deep reinforcement learning that is competitive with contemporary intrinsic rewards on Atari benchmarks.
  arXiv  Detail & Related papers  (2021-10-21T15:25:15Z)
• Pareto Optimal Model Selection in Linear Bandits [15.85873315624132]
  We study a model selection problem in the linear bandit setting, where the learner must adapt to the dimension of the optimal hypothesis class on the fly. In this paper, we first establish a lower bound showing that, even with a fixed action set, adaptation to the unknown intrinsic dimension $d_star$ comes at a cost.
  arXiv  Detail & Related papers  (2021-02-12T16:02:06Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  We consider the contextual bandit problem under the high dimensional linear model. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. We propose doubly growing epochs and estimating the parameter using the best subset selection method.
  arXiv  Detail & Related papers  (2020-09-04T04:10:39Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  We develop a meta-algorithm that selects between base algorithms. We show through a lower bound that even when one of the base algorithms has $O(sqrtT)$ regret, in general it is impossible to get better than $Omega(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2020-03-03T18:46:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.