Meta-learning improves decisions in adversarial linear bandit problems
Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
Machine Learning
Summary
Some computer programs learn to make decisions by trying different options and learning from past experience. This paper studies a scenario where the choices and outcomes can change in tricky, potentially opposing ways. The authors created an approach called Meta-LinEXP3 that helps a program learn better over time by using knowledge from previous tasks to guide future ones. Their method adjusts even when the context or pattern of choices is not fully known and shows improved performance in tests.
What this means in practice
- •For mobile app developers: Optimize in-app decision making under changing user contexts using transferred knowledge from past user interactions.
- •For remote sensing analysts: Improve structured sampling strategies in hyperspectral imaging tasks by leveraging learned priors from previous data captures.
Authors
Hao Li, Jie Xu, Zheng Xie
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.