Contextual Bandit Algorithms with Supervised Learning Guarantees

TLDR

The study seeks to learn in an online bandit setting where a learner selects among K actions but receives only partial feedback. The authors introduce two algorithms—Exp4.P, which competes with N experts with regret \(O(\sqrt{KT\ln(N/\delta)})\) and is evaluated on a large real‑world dataset, and VE, which competes with a VC‑dimension \(d\) policy class with regret \(O(\sqrt{T(d\ln T+\ln(1/\delta))})\). These algorithms achieve regret bounds that improve upon all previous methods in both stochastic and adversarial environments, bringing the contextual bandit setting closer to supervised‑learning guarantees.

Abstract

We address the problem of learning in an online, bandit setting where the learner must repeatedly select among $K$ actions, but only receives partial feedback based on its choices. We establish two new facts: First, using a new algorithm called Exp4.P, we show that it is possible to compete with the best in a set of $N$ experts with probability $1-δ$ while incurring regret at most $O(\sqrt{KT\ln(N/δ)})$ over $T$ time steps. The new algorithm is tested empirically in a large-scale, real-world dataset. Second, we give a new algorithm called VE that competes with a possibly infinite set of policies of VC-dimension $d$ while incurring regret at most $O(\sqrt{T(d\ln(T) + \ln (1/δ))})$ with probability $1-δ$. These guarantees improve on those of all previous algorithms, whether in a stochastic or adversarial environment, and bring us closer to providing supervised learning type guarantees for the contextual bandit setting.