---
bibliography:
- 'bibliography.bib'
---

Introduction
============

The contextual bandit problem is a fundamental framework for online decision making and interactive machine learning, with diverse applications ranging from hearthcare to electronic commerce, see a NIPS 2013 tutorial ([https://hunch.net/$\sim$jl/interact.pdf](https://hunch.net/~jl/interact.pdf)) for the theoretical background, and a recent ICML 2017 tutorial ([https://hunch.net/$\sim$rwil/](https://hunch.net/~rwil/)) for further illustrations on its practical importance.

Broadly speaking, approaches to contextual bandits can be put into two groups (see @foster2018practical): *realizability-based* approaches which rely on weak or strong assumptions on the model representation, and *agnostic* approaches which are completely model-free. While many different contextual bandit algorithms (realizability-based or agnostic) have been proposed over the past twenty years, most of them suffer from either theoretical or practical issues (see @bietti2018contextual). Existing algorithms built on upper confidence bounds (e.g., @filippi2010parametric [@abbasi2011improved; @chu2011contextual; @li2017provably]) and Thompson sampling (e.g., @agrawal2013thompson [@russo2018tutorial]) rely on strong assumptions on the model representation and are only tractable for specific parametrized families of models like generalized linear models. Meanwhile, algorithms that make no assumption on the model representation (e.g., @dudik2011efficient [@agarwal2014taming]) may lead to overly conservative exploration in practice (@bietti2018contextual), and their reliance on an *offline cost-sensitive classification oracle* as a subroutine typically causes implementation difficulties as the oracle 