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

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 𝒪(√n) per-task regret bound. For unknown distributions, we introduce a past-only regularized moment estimator with an 𝒪(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.

Online Autotuning of Algebraic Multigrid via Contextual Bandits and Reinforcement Learning
Xudong He, Ruiyu Wang, Yilang Ding +2
arXiv1 Nov 2026PreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
Optimal Learning in Fairness-Aware Contextual Bandits
Gengyu Xue, Fan Wang, Feiyu Jiang +2
arXiv1 Nov 2026PreprintCC BY 4.0Full textStatisticsarXiv
m-Set Adversarial Bandits with Winner Feedback
Nicolò Cesa-Bianchi, Matteo Papini
arXiv7 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
Set Membership Estimation for Stochastic Linear Contextual Bandits
Haonan Xu, Yingying Li
arXiv15 Oct 2026PreprintarXiv licenceFull textOptimisation & control StatisticsarXiv
Diversified Multinomial Logit Contextual Bandits
Heesang Ann, Taehyun Hwang, Min-hwan Oh
arXiv28 Sep 2026PreprintCC BY-SA 4.0Full textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{li2026metalinexp3,
  title = {{Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits}},
  author = {Hao Li and Jie Xu and Zheng Xie},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.09907},
  eprint = {2609.09907},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.09907},
}

RIS

TY  - UNPB
TI  - Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
AU  - Hao Li
AU  - Jie Xu
AU  - Zheng Xie
PY  - 2026
DA  - 2026/09/15
PB  - arXiv
DO  - 10.48550/arxiv.2609.09907
UR  - https://arxiv.org/abs/2609.09907
AB  - 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 𝒪(√n) per-task regret bound. For unknown distributions, we introduce a past-only regularized moment estimator with an 𝒪(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.
ER  -

Abstract

Related

Cite