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

Summary

Meta-LinEXP3 tackles meta-learning for adversarial linear contextual bandits (ALCBs) with random action sets, in an online-within-online design: an outer learner compresses completed-task summaries into a fixed-within-task prior vector that biases the inner LinEXP3 action distribution. Three loss estimators are analyzed: PC-KDE, which requires the context distribution plus exact policy-induced moments and is exactly unbiased on the decision-relevant subspace, yielding an intrinsic-dimension O(√n) per-task bound; PRME, which uses only past contexts, a ridge-regularized spectrally clipped second moment, and inverse-propensity weighting, yielding an O(n^{2/3}) leading term plus an explicit finite-sample moment error; and LPE, a cheap projection estimator whose residual bias can be Θ(n). Under a weak margin condition and a prior-accuracy assumption, transfer complexity decays so total regret is sublinear in the number of tasks; a finite recurrent-type construction shows that premise is attainable in principle. All proofs are machine-checked in Lean 4 (mathlib, no sorry). Experiments on synthetic tasks, an estimator comparison, MovieLens 100K, and KSC hyperspectral sampling show 5.1–22.1% synthetic regret reductions, roughly 15% MovieLens reward-gap improvement, and about 1.1% cumulative KSC MSE reduction with larger early-round gains. Key limitations: PRME's rate is weaker than existing single-task ~O(√n) results; the transfer theorem rests on accuracy conditions not verified for the priors used in experiments; and the spectral clipping threshold λ is hard to set when the distribution is unknown.