# Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits

arXiv: https://arxiv.org/abs/1606.00313 · HTML: https://mlsanity.com/paper/1606.00313/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2016.

## Built on by (most cited first, 13 of 13)

- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Boosting for Online Convex Optimization](https://mlsanity.com/paper/2102.09305/) (2021)
- [Contextual Games: Multi-Agent Learning with Side Information](https://mlsanity.com/paper/2107.06327/) (2021)
- [Regret Minimization in Stackelberg Games with Side Information](https://mlsanity.com/paper/2402.08576/) (2024)
- [Incentivizing High-Quality Content in Online Recommender Systems](https://mlsanity.com/paper/2306.07479/) (2023)
- [Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information](https://mlsanity.com/paper/2502.00204/) (2025)
- [On Efficient Online Imitation Learning via Classification](https://mlsanity.com/paper/2209.12868/) (2022)
- [Oracle-Efficient Hybrid Online Learning with Unknown Distribution](https://mlsanity.com/paper/2401.15520/) (2024)
- [LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2403.03219/) (2024)
- [Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs](https://mlsanity.com/paper/2609.33760/) (2026)
- [An Improved Relaxation for Oracle-Efficient Adversarial Contextual Bandits](https://mlsanity.com/paper/2310.19025/) (2023)
- [Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2312.16489/) (2023)

## Abstract (arXiv)

We give an oracle-based algorithm for the adversarial contextual bandit problem, where either contexts are drawn i.i.d. or the sequence of contexts is known a priori, but where the losses are picked adversarially. Our algorithm is computationally efficient, assuming access to an offline optimization oracle, and enjoys a regret of order O((KT)^frac23(log N)^frac13), where K is the number of actions, T is the number of iterations and N is the number of baseline policies. Our result is the first to break the O(T^frac34) barrier that is achieved by recently introduced algorithms. Breaking this barrier was left as a major open problem. Our analysis is based on the recent relaxation based approach of (Rakhlin and Sridharan, 2016).