Meta-Learning Bandit Policies by Gradient Ascent

Abstract

Most bandit policies are designed to either minimize regret in any problem instance, making very few assumptions about the underlying environment, or in a Bayesian sense, assuming a prior distribution over environment parameters. The former are often too conservative in practical settings, while the latter require assumptions that are hard to verify in practice. We study bandit problems that fall between these two extremes, where the learning agent has access to sampled bandit instances from an unknown prior distribution $\mathcal{P}$ and aims to achieve high reward on average over the bandit instances drawn from $\mathcal{P}$. This setting is of a particular importance because it lays foundations for meta-learning of bandit policies and reflects more realistic assumptions in many practical domains. We propose the use of parameterized bandit policies that are differentiable and can be optimized using policy gradients. This provides a broadly applicable framework that is easy to implement. We derive reward gradients that reflect the structure of bandit problems and policies, for both non-contextual and contextual settings, and propose a number of interesting policies that are both differentiable and have low regret. Our algorithmic and theoretical contributions are supported by extensive experiments that show the importance of baseline subtraction, learned biases, and the practicality of our approach on a range problems.

References in corpus (22)

• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Playing Atari with Deep Reinforcement Learning
• A Contextual-Bandit Approach to Personalized News Article Recommendation
• A Simple Neural Attentive Meta-Learner
• Analysis of Thompson Sampling for the multi-armed bandit problem
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Algorithms for multi-armed bandit problems
• Cascading Bandits: Learning to Rank in the Cascade Model
• On the Global Convergence Rates of Softmax Policy Gradient Methods
• Combinatorial Cascading Bandits
• Provable Meta-Learning of Linear Representations
• Sequential Transfer in Multi-armed Bandit with Finite Set of Models
• Efficient Learning in Large-Scale Combinatorial Semi-Bandits
• Meta-learning of Sequential Strategies
• TopRank: A practical algorithm for online stochastic ranking
• Structure Adaptive Algorithms for Stochastic Bandits
• Empirical Bayes Regret Minimization
• Policy Gradient Optimization of Thompson Sampling Policies
• Differentiable Linear Bandit Algorithm
• Meta-learning with Stochastic Linear Bandits
• A Novel Confidence-Based Algorithm for Structured Bandits

Cited by in corpus (3)

• Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models
• Policy Gradient Optimization of Thompson Sampling Policies
• Learning to Actively Learn: A Robust Approach