Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits

Abstract

Regret bounds in online learning compare the player's performance to $L^{\ast }$, the optimal performance in hindsight with a fixed strategy. Typically such bounds scale with the square root of the time horizon $T$. The more refined concept of first-order regret bound replaces this with a scaling $\sqrt{L^{\ast }}$, which may be much smaller than $\sqrt{T}$. It is well known that minor variants of standard algorithms satisfy first-order regret bounds in the full information and multi-armed bandit settings. In a COLT 2017 open problem, Agarwal, Krishnamurthy, Langford, Luo, and Schapire raised the issue that existing techniques do not seem sufficient to obtain first-order regret bounds for the contextual bandit problem. In the present paper, we resolve this open problem by presenting a new strategy based on augmenting the policy space.

arXiv comment15 pages

Cited by in corpus (8)

• A Contextual Bandit Bake-off
• Model selection for contextual bandits
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
• Taking a hint: How to leverage loss predictors in contextual bandits?
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits
• A Closer Look at Small-loss Bounds for Bandits with Graph Feedback
• Explaining Fast Improvement in Online Imitation Learning