PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Hao Li, Jie Xu, Zheng Xie

arXiv:2609.09907v1cs.LGmath.OC

TL;DR

Meta-LinEXP3 addresses the underexplored problem of meta-learning for adversarial linear contextual bandits with random action sets. It builds a predictable task-level prior from completed tasks for an inner LinEXP3 learner, obtaining estimator-specific regret guarantees and showing transfer benefits under accurate priors. Experiments report gains across synthetic, recommendation, and structured tensor-sampling settings.

  • Problem

    Meta-learning for adversarial linear contextual bandits with random action sets remains largely unexplored, despite existing progress for stochastic and non-contextual adversarial bandits.

  • Method

    Meta-LinEXP3 constructs a predictable prior from completed-task summaries and combines it with an inner adversarial LinEXP3 learner, using PC-KDE or PRME estimators.

  • Results

    Across the reported experiments, Meta-LinEXP3 variants show transfer gains, including lower MovieLens reward gaps and about a 1.1% cumulative KSC reduction versus zero-prior LinEXP3.

  • Takeaways & Limitations

    Under stated margin and prior-accuracy conditions, increasingly accurate priors yield sublinear transfer-dependent terms across structured task sequences.

  • Takeaways & Limitations

    Transfer improvements require predictable task structure; unrelated tasks need not yield gains, and MovieLens and KSC do not exactly satisfy the noiseless-linear/common-context-distribution model.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies cross-task transfer for adversarial linear contextual bandits, where restarting single-task learners discards useful information. Meta-LinEXP3 combines a task-level prior with an inner LinEXP3 learner and develops estimator-specific guarantees for known and unknown context distributions.

  • Existing ALCB methods analyze one task at a time, so restarting them across related tasks discards potentially useful information when horizons are short.
  • Meta-LinEXP3 couples an outer task-level transfer mechanism with an inner adversarial LinEXP3 learner.
  • PCRW and a uniform baseline construct predictable priors from completed-task summaries and keep them fixed throughout the next task.
  • PC-KDE achieves an intrinsic-dimension O(√n) per-task bound, while PRME has an O(n^2/3) leading term with explicit moment-estimation error.
  • Experiments cover bounded synthetic tasks, estimator comparisons, MovieLens recommendation, and structured KSC tensor sampling.
  • The guarantees rely on a fixed-within-task prior and estimator-specific verification of selection correction, score range, variance, and bias.

2 Related Work

Prior work provides single-task adversarial contextual-bandit methods and meta-learning results mainly for stochastic or simpler adversarial settings. Meta-LinEXP3 targets repeated random-action-set ALCBs, where selection bias and context-dependent comparators create additional challenges.

  • PRME has a general O(n^2/3) rate, while prior single-task unknown-distribution methods report sharper rates; PRME instead exposes cross-task context reuse and meta-prior dependence.
  • Most bandit meta-learning work assumes stochastic rewards, so its guarantees do not directly extend to adversarial within-task loss sequences.
  • Existing adversarial online-within-online guarantees do not cover repeated random-action-set ALCBs, where both comparator actions and sampling designs depend on the current context set.
  • Figure 1 situates Meta-LinEXP3 between single-task LinEXP3 and related meta-bandit settings.
  • Selection bias arises because the selected context need not follow the marginal context distribution after the learner observes the entire action set.

3 Preliminaries

The problem consists of sequential ALCB tasks with fresh random context sets, adaptive loss vectors, and losses given by context–loss-vector inner products. Performance uses a policy comparator, while LinEXP3 supplies the within-task learner and Meta-LinEXP3 adds a fixed task prior.

  • 3.1 Notation: The global setup has m tasks, n rounds per task, k actions per round, and context dimension d, with T = mn total task–round pairs.
  • 3.2 Online-within-Online ALCB Problem: At each round, the environment independently samples k context vectors, the learner observes the set, and then selects an action.
  • 3.2 Online-within-Online ALCB Problem: The selected-action loss is the inner product ⟨b_s,t,A_s,t, θ_s,t⟩ between its context vector and the environment’s loss vector.
  • 3.2 Online-within-Online ALCB Problem: The common context distribution generates independent ordered context sets, and regret is measured against a policy fixed independently of the realized context trajectory.
  • 3.2 Online-within-Online ALCB Problem: The adversary may adapt to the history, but the current context set is fresh and independent of the current loss vector conditional on pre-context history.
  • 3.3 Inner Learner: LinEXP3 updates exponential weights from observed loss estimates and mixes its decision distribution with uniform exploration of total mass γ.

4 The Meta-LinEXP3 Algorithm

Meta-LinEXP3 combines a predictable task-level prior with LinEXP3 and uses estimator-specific constructions for known or unknown context distributions. The prior is fixed within each task, while PC-KDE and PRME address selection bias and moment estimation under different distributional information.

  • Overall algorithm: Meta-LinEXP3 maps completed-task summaries to a predictable prior that remains fixed during the next task, removing within-task prior-variation terms from the analysis.The outer learner updates the stored summaries after each task and combines the induced softmax prior with within-task loss estimates.
  • Task similarity and transfer: Decision-relevant task similarity is measured by signed cosine between projected task means in U, because positive rescaling preserves optimal action selection while negative alignment can reverse loss ordering.Full-space distance or cosine can be misleading when components orthogonal to U do not affect action comparisons.
  • Known context distributions: PC-KDE uses policy-induced selected moments and recovers all loss differences on the decision-relevant subspace, even when ambient covariance is singular.It is exactly unbiased when C is nonsingular and remains sufficient for regret analysis when context differences lie in U.
  • Unknown context distributions: PRME uses strictly past contexts, inverse propensities, regularization, and spectral clipping to control selection bias and estimator range when the context distribution is unknown.Its finite-sample regularization error is explicit, and the streaming implementation uses O(d2) memory with O(d3 + kd2) update cost.
  • Task weightings: PCRW aggregates positively aligned historical directions before each task and keeps the result fixed, while zero-prior and uniform-convex alternatives remain valid predictable priors.Anti-aligned tasks receive only smoothing mass, and the transfer theorem applies to any predictable prior fixed within a task.

5 Theoretical Analysis

The analysis establishes regret guarantees for fixed predictable task priors and connects prior accuracy to sublinear aggregate transfer regret under margin and feasibility conditions.

  • For d_U = 0, every action has the same context almost surely and regret is zero.
  • The tuned bounds require feasibility; when tuned exploration exceeds 1/2, the untuned or trivial G n bound can be used instead.
  • The margin requirement is weak: it imposes neither a power-law exponent nor a pointwise positive gap, while Φ_F(µ) converges to zero as µ increases.
  • Theorem 5.7 links transfer regret to prior accuracy under bounded geometry, predictable priors, oblivious tasks, and a margin condition.
  • PC-KDE and PRME yield aggregate learning terms scaling as √n o(m) and n^2/3 o(m), respectively, with sublinear regret across tasks for fixed problem constants.The PRME moment term is eO(mn/k), and its aggregate failure remainder is O(δ).
  • With µ_s = c log(s + 1), ε_s = O(1/log s) and δ_s = o(1/log s) suffice for B_s → 0 under any admissible F satisfying the stated condition.
  • The transfer theorem is conditional on prior accuracy and does not establish that the experimental PCRW or Uniform priors satisfy its assumption.A separate sufficient construction uses an exogenous descriptor, PC-KDE, and finitely many recurrent task types, but does not cover PRME or LPE.
  • Core guarantees require predictable structure for task-number improvements, whereas unrelated tasks can still incur linear total regret.

6 Experiments

Experiments evaluate Meta-LinEXP3 across synthetic transfer, estimator comparison, MovieLens recommendation, and KSC tensor sampling. The results show transfer gains, estimator trade-offs, and application-level improvements, while noting that KSC does not test the linear theory directly.

  • 6.1 Synthetic Transfer Experiment: At the final synthetic task, PCRW reduces LinEXP3 regret by approximately 5.1%, 11.7%, 18.5%, and 22.1% as CSmin increases from −1 to 1.The corresponding PCRW means are 99.10, 93.29, 87.27, and 80.20 versus LinEXP3 means of 104.40, 105.63, 107.12, and 102.98.
  • 6.2 Estimator Comparison: At round 40, PC-KDE has mean cumulative estimation error 3.25 ± 0.50, compared with 4.44 ± 0.69 for PRME and 6.90 ± 1.03 for LPE.PC-KDE uses exact policy-induced moments, PRME incurs finite-sample moment and inverse-propensity error, and LPE recovers only the selected-context component.
  • 6.3 Movie Recommendation Task: At MovieLens task 200, PCRW and Uniform achieve mean cumulative reward gaps of 1917.9 and 1931.8, lower than LinEXP3's 2256.7 and tested Meta-TS's 1966.6.Relative to LinEXP3, the reductions are about 15.0% and 14.4%; the comparison is not a general method ranking because both model classes approximate MovieLens.
  • 6.4 Structured Tensor Sampling for Hyperspectral Data: On the reported KSC suffix, PCRW and Uniform have cumulative best-observed MSEs of 69929.56 ± 62.95 and 69911.67 ± 56.90, versus 70715.18 ± 77.57 for zero-prior LinEXP3.Paired confidence intervals support lower MSE for both transferred priors, while the comparison does not isolate sequential search, feedback, proposal design, and transfer separately.
  • 6.4 Structured Tensor Sampling for Hyperspectral Data: On KSC, PCRW and Uniform improve the early-search score by 1.294% and 1.282% relative to zero-prior LinEXP3.The corresponding means are 473.509 ± 0.434, 473.568 ± 0.485, and 479.719 ± 0.533.
  • 6.4 Structured Tensor Sampling for Hyperspectral Data: The KSC study provides application-level evidence for fixed cross-task priors but does not validate the linear/common-context-distribution theorem.Direct-construction baselines use different search procedures and computational costs, so their final solution-quality comparison is not an equal-effort search comparison.

7 Conclusion

Meta-LinEXP3 combines task-level transfer with adversarial linear contextual bandit learning, with estimator-specific guarantees and empirical gains under structured transfer.

  • 7 Conclusion: Meta-LinEXP3 constructs a predictable prior from completed tasks and keeps it fixed throughout the next ALCB task.The approach couples task-level transfer with an inner LinEXP3 learner.
  • 7 Conclusion: PC-KDE achieves an intrinsic-dimension O(√n) per-task guarantee, while PRME provides an O(n2/3) leading term with finite-sample moment error.
  • 7 Conclusion: On MovieLens, both Meta-LinEXP3 variants have lower mean final reward gaps than the tested baselines.
  • 7 Conclusion: On KSC, the shared sequential comparison reduces cumulative loss by about 1.1% and improves early recovery by about 1.2–1.3% relative to zero-prior LinEXP3.The early-recovery comparison covers the first 10 rounds and uses the centered relative loss summary in (52).
  • 7 Conclusion: Transfer improvement depends on predictable structure that makes the prior increasingly accurate, while unrelated tasks need not provide transfer gains.The application settings also do not exactly satisfy the noiseless-linear/common-context-distribution model.

Funding

The paper reports external project support and includes a local notation clarification for the derivations.

  • Funding: The work was supported by the Major Scientific and Technological Innovation Platform Project of Hunan Province (2024JC1003).
  • Funding: Boldface is omitted locally when vector or matrix type is unambiguous, with symbols corresponding to their boldface counterparts in the main text.
  • Funding: The notation clarification applies specifically to the derivations below.

A.1 Technical Results Deferred from the Main Text

The deferred technical results formalize changing-prior transfer, estimator-specific regret and bias decompositions, and fast-rate consequences under additional assumptions.

  • A.1 Technical Results Deferred from the Main Text: Changing-prior exponential-weights analysis decomposes performance into comparator terms, prior drift, and estimator-related corrections.The framework applies to predictable strictly positive prior kernels and fixed comparator sequences.
  • A.1 Technical Results Deferred from the Main Text: The PC-KDE results provide average regret guarantees and refinements under known-distribution assumptions, including fixed-prior transfer bounds.
  • A.1 Technical Results Deferred from the Main Text: The transfer analysis also covers uniform-gap and Gaussian specializations, with the Gaussian calculation requiring a separate truncation argument from the bounded-support theorem.
  • A.1 Technical Results Deferred from the Main Text: PRME admits a finite-sample decomposition with explicit failure and signed-bias terms, while its uniform-gap corollary gives a fast-rate result under stated tuning conditions.
  • A.1 Technical Results Deferred from the Main Text: LPE has regret and exact projection-bias results, but without directional coverage its average bias can remain of order n.

A.3 Known-Distribution Estimator

The known-distribution analysis uses selected-covariance structure and cross-task prior accuracy to derive PC-KDE regret and sublinear transfer consequences.

  • A.3 Known-Distribution Estimator: Selected contexts lie in the covariance range, enabling affine-support arguments and decision-relevant unbiasedness for the policy-centered estimator.
  • A.3 Known-Distribution Estimator: The PC-KDE regret analysis combines exploitation, uniform exploration, and signed correction terms under a fresh-context construction.
  • A.3 Known-Distribution Estimator: Prior prediction error controls transfer complexity through a margin-based bound, with uniform-prior initialization giving Γ1(π1) = log k.
  • A.3 Known-Distribution Estimator: For oblivious tasks, the fixed policy attains the comparator supremum because components orthogonal to the covariance range add the same offset to all actions.
  • A.3 Known-Distribution Estimator: Under calibrated prior accuracy, PC-KDE and PRME learning terms become sublinear in task count, while PRME retains an eO(√(mn/k)) moment-learning term.

A.4 A Concrete Recurrent-Type Sufficient Condition for Prior Consistency

The appendix gives a recurrent-type construction under which descriptor-gated PC-KDE summaries satisfy the prior-consistency premise. With fixed descriptor types and past-only estimation, tuning violations become finite and transfer bounds follow.

  • A.4: The descriptor-gated prior is measurable before within-task decisions and can be maintained with one running sum and count per descriptor.Raw projected summaries are averaged before normalization, so positive magnitudes along a decision direction reinforce the recurrent type.
  • A.4: Fixed recurrent descriptors and descriptor-gated historical summaries provide a sufficient construction for prior consistency.The descriptor sequence and task losses are fixed before interaction, while the prior uses same-descriptor history.
  • A.4: Historical PC-KDE summaries therefore satisfy Theorem 5.7’s prior-consistency premise in the finite recurrent-type model.The theorem assumes the recurrent-type construction and concludes the desired consistency on every task, with a constant initialization term independent of m.
  • A.4: ε_N = O((log N)^3/2 / √N) tends to zero, so tuned exploration eventually becomes feasible and only finitely many descriptor occurrences violate it.The remaining exceptional tasks, including first occurrences, contribute a constant initialization term.

B MovieLens Data Preparation and Attribute-Clustering Completion

The data-preparation section describes attribute-based completion for MovieLens and introduces structured tensor slices for hyperspectral sampling. It treats related slices or bands as a source of cross-task information while stating rank and invertibility requirements.

  • MovieLens Data Preparation: MovieLens 100K contains 943 users, 1,682 movies, 100,000 ratings, and 19 non-exclusive genre indicators.The sparse rating matrix is paired with a binary movie-genre indicator matrix.
  • MovieLens Data Preparation: Movies form genre clusters, while each user is assigned to the genre with the largest valid mean observed rating.Users without a valid genre mean are placed in a general cluster.
  • Attribute-Clustering Completion: Missing MovieLens entries are imputed with the maximum available cluster–genre mean among the movie’s genres, or remain unavailable when no candidate exists.The imputation uses the user’s cluster and the movie’s genre set.
  • Structured Tensor Sampling: Hyperspectral tensor slices share structural or statistical features along the third mode, motivating cross-task transfer between spectral bands.For KSC, each band is treated as a task and band similarity supplies cross-task information.
  • Structured Tensor Sampling: The sampling formulation selects sensor subsets under rank constraints that ensure the Gram matrices in the inverse-based MSE are invertible.The inverse-based MSE is defined only when both relevant submatrices have full column rank K.

C.2 Algorithm Implementation

The implementation builds rank-safe candidate banks and evaluates Meta-LinEXP3 on nonlinear hyperspectral recovery loss. It uses completed centered summaries for fixed cross-task priors while retaining absolute-MSE updates within tasks.

  • C.2 Algorithm Implementation: The KSC case study uses selected sensor sets as actions and inverse-Gram recovery MSE as feedback, outside the exact linear-loss theorem assumptions.The objective is nonlinear in the incidence vector, so the ALCB architecture is applied beyond the theorem’s exact setting.
  • C.2 Algorithm Implementation: Candidate actions are generated without replacement and retained only when both factor submatrices have rank K and Gram matrices have reciprocal condition numbers at least 10^-3.Candidate generation stops after acceptance or a fixed maximum number of attempts, and the resulting bank is reused across 60 repetitions.
  • C.2 Algorithm Implementation: Meta-LinEXP3 applies absolute-MSE LPE updates within slices but uses centered relative loss summaries for cross-task representation.Centering removes the taskwise MSE offset while preserving relative sampling-set information, and completed summaries prevent current-task feedback from entering the fixed prior.
  • C.2 Algorithm Implementation: The protocol calibrates μ on slices 1:24, builds a separate final candidate bank, and reports slices 25:176 under paired sequential comparisons.PCRW and Uniform are compared with zero-prior LinEXP3, while FFW and Greedy-FP are computed separately.
  • C.2 Algorithm Implementation: Each evaluation run selects candidates from the common bank, observes recovery MSE, updates within-task scores, and stores best-observed trajectories plus completed summaries.The fixed PCRW or Uniform prior is formed from completed centered relative-loss summaries.
Loading 2609.09907v1…