Efficient Algorithms for Adversarial Contextual Learning

Abstract

We provide the first oracle efficient sublinear regret algorithms for adversarial versions of the contextual bandit problem. In this problem, the learner repeatedly makes an action on the basis of a context and receives reward for the chosen action, with the goal of achieving reward competitive with a large class of policies. We analyze two settings: i) in the transductive setting the learner knows the set of contexts a priori, ii) in the small separator setting, there exists a small set of contexts such that any two policies behave differently in one of the contexts in the set. Our algorithms fall into the follow the perturbed leader family \cite{Kalai2005} and achieve regret $O(T^{3/4}\sqrt{K\log (N)})$ in the transductive setting and $O(T^{2/3}{d}^{3/4}K\sqrt{\log (N)})$ in the separator setting, where $K$ is the number of actions, $N$ is the number of baseline policies, and $d$ is the size of the separator. We actually solve the more general adversarial contextual semi-bandit linear optimization problem, whilst in the full information setting we address the even more general contextual combinatorial optimization. We provide several extensions and implications of our algorithms, such as switching regret and efficient learning with predictable sequences.

References in corpus (4)

• Efficient Optimal Learning for Contextual Bandits
• Adaptive Online Prediction by Following the Perturbed Leader
• Fast Convergence of Regularized Learning in Games
• BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits

Cited by in corpus (18)

• A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits
• Semiparametric Contextual Bandits
• Online learning in MDPs with linear function approximation and bandit feedback
• OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
• Taking a hint: How to leverage loss predictors in contextual bandits?
• Efficient Contextual Bandits with Continuous Actions
• Metric-Free Individual Fairness in Online Learning
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits
• Online Pricing with Reserve Price Constraint for Personal Data Markets
• Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Case
• Universal and data-adaptive algorithms for model selection in linear contextual bandits
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations
• Boosting for Online Convex Optimization
• Efficient Online Bandit Multiclass Learning with $\tilde{O}(\sqrt{T})$ Regret
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability
• Robust Bandit Learning with Imperfect Context