Metalearning Linear Bandits by Prior Update

Amit Peleg, Naama Pearl, Ron Meir

Introduction

Multi-armed bandit problems center on the fundamental trade-off between exploration and exploitation. Bayesian approaches offer an elegant solution by utilizing a "prior" distribution to guide decision-making. However, in practice, the "true" prior is rarely known. Incorrectly specifying this prior can lead to significant performance degradation, where the agent either over-explores suboptimal actions or misses high-reward opportunities.

Metalearning—learning a prior from a sequence of related tasks—has emerged as a powerful remedy. Yet, existing theoretical frameworks often rely on restrictive assumptions, such as knowing the covariance of the reward distribution, or they produce "regret" bounds that scale poorly with time ($T$), limiting their practical utility for long-horizon tasks.

The $MQB_\tau$ Algorithm

To address these challenges, the authors introduce Metalearning Quasi-Bayesian ($MQB_\tau$). This algorithm operates across two distinct scales:

  1. Within-Instance Exploration: For each new task, the agent performs a "pure exploration" phase for the first $\tau$ steps. By taking random actions, the agent gathers unbiased data that spans the entire problem space.
  2. Between-Instance Learning: Once a task instance concludes, the agent updates its "meta-prior." It employs Ordinary Least Squares (OLS) to estimate task parameters and a bias-corrected Maximum Likelihood Estimator (MLE) to refine its understanding of the covariance structure.
  3. Quasi-Bayesian Execution: For the remainder of the task (steps $\tau+1$ to $T$), the agent uses standard Bayesian strategies (like Thompson Sampling) but substitutes the learned meta-prior for the unknown true prior.
Timeline of the between-instance and within-instance phases in the MQB algorithm.

The core innovation lies in a "two-stage alignment" proof. The authors demonstrate that after the initial exploration phase, the performance of an agent using an estimated prior mathematically converges to that of an agent using the true prior.

Key Results and Theoretical Impact

The $MQB_\tau$ framework provides the first theoretical guarantee of $\sqrt{T}$ regret scaling in a setting where both the prior mean and covariance are unknown. As shown in the comparison table below, this represents a significant improvement over previous state-of-the-art methods that scaled with $T^{3/2}$ or $T^2$.

Comparison of regret bounds and assumptions against state-of-the-art metalearning bandit algorithms.

Empirical simulations on synthetic $d$-dimensional linear bandits confirm these findings. The algorithm's estimated parameters converge to the true values as the number of tasks ($N$) increases. Notably, learning the covariance—the correlation between different actions—proved more critical for reducing regret than simply knowing the mean reward.

Conclusion and Future Work

$MQB_\tau$ demonstrates that an estimated prior is "good enough" to achieve near-optimal performance, provided the estimation process is sufficiently robust. By learning both mean and covariance, the algorithm bridges the gap between theoretical Bayesian optimality and practical frequentist constraints.

Future research aims to eliminate the need for the "forced exploration" phase ($\tau$). While necessary for the current mathematical proof of unbiasedness, reducing or removing this phase could further enhance the algorithm's efficiency in the early stages of each task.

Summary updated

BibTeX
@inproceedings{peleg2022metalearning,
  author = {Amit Peleg and Naama Pearl and Ron Meir},
  title = {{Metalearning Linear Bandits by Prior Update}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=WZDKOvZ4iz},
}
Figure