Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits

Abstract

We consider an adversarial variant of the classic $K$-armed linear contextual bandit problem where the sequence of loss functions associated with each arm are allowed to change without restriction over time. Under the assumption that the $d$-dimensional contexts are generated i.i.d.~at random from a known distributions, we develop computationally efficient algorithms based on the classic Exp3 algorithm. Our first algorithm, RealLinExp3, is shown to achieve a regret guarantee of $\tilde{O}(\sqrt{KdT})$ over $T$ rounds, which matches the best available bound for this problem. Our second algorithm, RobustLinExp3, is shown to be robust to misspecification, in that it achieves a regret bound of $\tilde{O}((Kd{)}^{1/3}{T}^{2/3})+\epsilon \sqrt{d}T$ if the true reward function is linear up to an additive nonlinear error uniformly bounded in absolute value by $\epsilon$. To our knowledge, our performance guarantees constitute the very first results on this problem setting.

References in corpus (7)

• Efficient Optimal Learning for Contextual Bandits
• Model selection for contextual bandits
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• Online combinatorial optimization with stochastic decision sets and adversarial losses
• First-order regret bounds for combinatorial semi-bandits
• Randomized Exploration for Non-Stationary Stochastic Linear Bandits

Cited by in corpus (1)

• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity