Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits

Contextual bandit is a widely used model for sequential decision making. The interaction between the learner and the environment proceeds in rounds: in each round, the environment provides a context; based on it, the learner chooses an action and receive a reward. The goal is to maximize the total reward across multiple rounds. This model has found extensive applications in fields such as medical treatment [Tewari and Murphy, 2017], personalized recommendations [Beygelzimer et al., 2011], and online advertising [Chu et al., 2011]. Algorithms for contextual bandits with provable guarantees have been developed under various assumptions. In the linear regime, the most extensively studied model is the stochastic linear contextual bandit, in which the context can be arbitrarily distributed in each round, while the reward is determined by a fixed linear function of the context-action pair. Near-optimal algorithms for this setting have been established in, e.g., [Chu et al., 2011, Abbasi-Yadkori et al., 2011, Li et al., 2019, Foster et al., 2020]. Another model, which is the focus of this paper, is the adversarial linear contextual bandit, in which the context is drawn from a fixed distribution, while the reward is determined by a time-varying linear function of the context-action pair.