Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination

Contextual bandits encompass both the general problem of statistical learning with function approximation (specifically, cost-sensitive classification) and the classical multi-armed bandit problem, yet present algorithmic challenges greater than the sum of both parts.