Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits

• URL: http://arxiv.org/abs/2609.09907v2
• Date: Tue, 15 Sep 2026 12:35:28 GMT
• Title: Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
• Abstract summary: We propose an online-within-online algorithm that constructs a predictable task-level prior from completed tasks to guide the inner LinEXP3 learner.<n>Experiments demonstrate the effectiveness of Meta-LinEXP3, including its application to structured hyperspectral tensor sampling.
• Score: 13.847359093328222
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Meta-learning has emerged as an effective paradigm for transferring knowledge across sequential bandit tasks. While substantial progress has been made for stochastic bandits and non-contextual adversarial bandits, meta-learning for adversarial linear contextual bandits (ALCBs) with random action sets remains largely unexplored. To address this problem, we propose Meta-LinEXP3, an online-within-online algorithm that constructs a predictable task-level prior from completed tasks to guide the inner LinEXP3 learner. For known context distributions, we develop a policy-centered estimator that achieves an intrinsic-dimension $\mathcal{O}(\sqrt{n})$ per-task regret bound. For unknown distributions, we introduce a past-only regularized moment estimator with an $\mathcal{O}(n^{2/3})$ leading regret term and explicit finite-sample error. We further establish a direct connection between prior accuracy and transfer regret, showing that increasingly accurate priors yield sublinear transfer-dependent regret across tasks. Experiments demonstrate the effectiveness of Meta-LinEXP3, including its application to structured hyperspectral tensor sampling.

Related papers

• To Retain or to Adapt? Generalizing Continual Learning [39.95178050304739]
  We argue that in non-stationary environments prioritizing retention can impede real-time adaptation.<n>We formalize CL as an online optimization problem governed by the interaction between environmental and learning dynamics.<n>We propose a new general class of continual learning algorithms, which we call Predictive Continual Learning.
  arXiv  Detail & Related papers  (2026-07-06T20:11:53Z)
• Learning Shared Representations for Multi-Task Linear Bandits [7.978226788634307]
  Multi-task representation learning is an approach that learns shared latent representations across related tasks.<n>We consider a setting with T concurrent linear bandit tasks, each with feature dimension d, that share a common latent representation of dimension r ll mind,T$.<n>We propose a new Optimism in the Face of Uncertainty Linear (OFUL) algorithm that leverages shared low-rank representations to enhance decision-making.
  arXiv  Detail & Related papers  (2026-04-01T06:18:17Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function.<n>GLBs are widely applicable to real-world scenarios, but their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency.<n>We propose a jointly efficient algorithm that attains a nearly optimal regret bound with $mathcalO(1)$ time and space complexities per round.
  arXiv  Detail & Related papers  (2025-07-16T02:24:21Z)
• Distributed No-Regret Learning for Multi-Stage Systems with End-to-End Bandit Feedback [7.8539454948826375]
  This paper studies multi-stage systems with end-to-end bandit feedback. Each job needs to go through multiple stages, each managed by a different agent, before generating an outcome. The goal of this paper is to develop distributed online learning algorithms that achieve sublinear regret in adversarial environments.
  arXiv  Detail & Related papers  (2024-04-06T05:34:12Z)
• Random Representations Outperform Online Continually Learned Representations [68.42776779425978]
  We show that existing online continually trained deep networks produce inferior representations compared to a simple pre-defined random transforms. Our method, called RanDumb, significantly outperforms state-of-the-art continually learned representations across all online continual learning benchmarks. Our study reveals the significant limitations of representation learning, particularly in low-exemplar and online continual learning scenarios.
  arXiv  Detail & Related papers  (2024-02-13T22:07:29Z)
• Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
  We study online meta-learning with bandit feedback. We learn to tune online mirror descent generalization (OMD) with self-concordant barrier regularizers.
  arXiv  Detail & Related papers  (2023-07-05T13:52:10Z)
• Meta-Learning Adversarial Bandits [49.094361442409785]
  We study online learning with bandit feedback across multiple tasks, with the goal of improving average performance across tasks if they are similar according to some natural task-similarity measure. As the first to target the adversarial setting, we design a meta-algorithm that setting-specific guarantees for two important cases: multi-armed bandits (MAB) and bandit optimization (BLO) Our guarantees rely on proving that unregularized follow-the-leader combined with multiplicative weights is enough to online learn a non-smooth and non-B sequence.
  arXiv  Detail & Related papers  (2022-05-27T17:40:32Z)
• 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)
• Meta-learning with Stochastic Linear Bandits [120.43000970418939]
  We consider a class of bandit algorithms that implement a regularized version of the well-known OFUL algorithm, where the regularization is a square euclidean distance to a bias vector. We show both theoretically and experimentally, that when the number of tasks grows and the variance of the task-distribution is small, our strategies have a significant advantage over learning the tasks in isolation.
  arXiv  Detail & Related papers  (2020-05-18T08:41:39Z)

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.