BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits

Abstract

We present efficient algorithms for the problem of contextual bandits with i.i.d. covariates, an arbitrary sequence of rewards, and an arbitrary class of policies. Our algorithm BISTRO requires d calls to the empirical risk minimization (ERM) oracle per round, where d is the number of actions. The method uses unlabeled data to make the problem computationally simple. When the ERM problem itself is computationally hard, we extend the approach by employing multiplicative approximation algorithms for the ERM. The integrality gap of the relaxation only enters in the regret bound rather than the benchmark. Finally, we show that the adversarial version of the contextual bandit problem is learnable (and efficient) whenever the full-information supervised online learning problem has a non-trivial regret guarantee (and efficient).

References in corpus (2)

• Efficient Optimal Learning for Contextual Bandits
• Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints

Cited by in corpus (7)

• Efficient Algorithms for Adversarial Contextual Learning
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Sequential Batch Learning in Finite-Action Linear Contextual Bandits
• OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
• Efficient Contextual Bandits with Continuous Actions
• Self-Tuning Bandits over Unknown Covariate-Shifts
• Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm