Anytime Model Selection in Linear Bandits

• URL: http://arxiv.org/abs/2307.12897v2
• Date: Sun, 12 Nov 2023 12:00:32 GMT
• Title: Anytime Model Selection in Linear Bandits
• Authors: Parnian Kassraie, Nicolas Emmenegger, Andreas Krause, Aldo Pacchiano
• Abstract summary: 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.
• Score: 61.97047189786905
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Model selection in the context of bandit optimization is a challenging problem, as it requires balancing exploration and exploitation not only for action selection, but also for model selection. One natural approach is to rely on online learning algorithms that treat different models as experts. Existing methods, however, scale poorly ($\text{poly}M$) with the number of models $M$ in terms of their regret. Our key insight is that, for model selection in linear bandits, we can emulate full-information feedback to the online learner with a favorable bias-variance trade-off. This allows us to develop ALEXP, which has an exponentially improved ($\log M$) dependence on $M$ for its regret. ALEXP has anytime guarantees on its regret, and neither requires knowledge of the horizon $n$, nor relies on an initial purely exploratory stage. Our approach utilizes a novel time-uniform analysis of the Lasso, establishing a new connection between online learning and high-dimensional statistics.

Related papers

• Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits [43.65904435249823]
  We propose a time-increasing bandit algorithm TI-UCB, which effectively predicts the increase of model performances. Our results highlight the importance of utilizing increasing-then-converging pattern for more efficient and economic model selection.
  arXiv  Detail & Related papers  (2024-03-11T23:52:46Z)
• 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)
• Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver [32.212146650873194]
  We provide approaches to learn an RL model efficiently without the guidance of a reward signal. In particular, we take a plug-in solver approach, where we focus on learning a model in the exploration phase. We show that, by establishing a novel exploration algorithm, the plug-in approach learns a model by taking $tildeO(d2H3/epsilon2)$ interactions with the environment.
  arXiv  Detail & Related papers  (2021-10-07T07:59:50Z)
• Towards Costless Model Selection in Contextual Bandits: A Bias-Variance Perspective [7.318831153179727]
  We study the feasibility of similar guarantees for cumulative regret minimization in the contextual bandit setting. Our algorithm is based on a novel misspecification test, and our analysis demonstrates the benefits of using model selection for reward estimation.
  arXiv  Detail & Related papers  (2021-06-11T16:08:03Z)
• Exploring Sparse Expert Models and Beyond [51.90860155810848]
  Mixture-of-Experts (MoE) models can achieve promising results with outrageous large amount of parameters but constant computation cost. We propose a simple method called expert prototyping that splits experts into different prototypes and applies $k$ top-$1$ routing. This strategy improves the model quality but maintains constant computational costs, and our further exploration on extremely large-scale models reflects that it is more effective in training larger models.
  arXiv  Detail & Related papers  (2021-05-31T16:12:44Z)
• Exploring Bayesian Deep Learning for Urgent Instructor Intervention Need in MOOC Forums [58.221459787471254]
  Massive Open Online Courses (MOOCs) have become a popular choice for e-learning thanks to their great flexibility. Due to large numbers of learners and their diverse backgrounds, it is taxing to offer real-time support. With the large volume of posts and high workloads for MOOC instructors, it is unlikely that the instructors can identify all learners requiring intervention. This paper explores for the first time Bayesian deep learning on learner-based text posts with two methods: Monte Carlo Dropout and Variational Inference.
  arXiv  Detail & Related papers  (2021-04-26T15:12:13Z)
• Non-Stationary Latent Bandits [68.21614490603758]
  We propose a practical approach for fast personalization to non-stationary users. The key idea is to frame this problem as a latent bandit, where prototypical models of user behavior are learned offline and the latent state of the user is inferred online. We propose Thompson sampling algorithms for regret minimization in non-stationary latent bandits, analyze them, and evaluate them on a real-world dataset.
  arXiv  Detail & Related papers  (2020-12-01T10:31:57Z)
• Generative Temporal Difference Learning for Infinite-Horizon Prediction [101.59882753763888]
  We introduce the $gamma$-model, a predictive model of environment dynamics with an infinite probabilistic horizon. We discuss how its training reflects an inescapable tradeoff between training-time and testing-time compounding errors.
  arXiv  Detail & Related papers  (2020-10-27T17:54:12Z)
• Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design [12.465883735626605]
  We study the impact of adaptivity constraints to linear contextual bandits, a central problem in online active learning. We show that, when the context vectors are adversarially chosen in $d$-dimensional linear contextual bandits, the learner needs $O(d log d log T)$ policy switches to achieve the minimax-optimal regret.
  arXiv  Detail & Related papers  (2020-07-04T01:34:22Z)

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.