Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits

2016-06-01 · NeurIPS 2016 12 · Vasilis Syrgkanis, Haipeng Luo, Akshay Krishnamurthy, Robert E. Schapire

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)^{\frac{2}{3}}(\log N)^{\frac{1}{3}})$, 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^{\frac{3}{4}})$ 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).

📄 PDF Abstract BibTeX arXiv:1606.00313

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-Armed Bandits

An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction

2025-08-16 · Tim van Erven, Jack Mayo, Julia Olkhovskaya, Chen-Yu Wei arxiv

We present an oracle-efficient, near-optimal algorithm for linear contextual bandits with adversarial losses and stochastic action sets, only requiring a linear optimization oracle for the action sets in each round. Our …

Smoothed Online Learning is as Easy as Statistical Learning

2022-02-09 · Adam Block, Yuval Dagan, Noah Golowich, Alexander Rakhlin

Much of modern learning theory has been split between two regimes: the classical offline setting, where data arrive independently, and the online setting, where data arrive adversarially. While the former model is often …

Learning Theory Multi-Armed Bandits

Active Learning Multi-Armed Bandits reinforcement-learning Reinforcement Learning+1

Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits

Code (0)

Tasks

Similar Papers 제목 키워드 기반

An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction

Smoothed Online Learning is as Easy as Statistical Learning

Oracle-Efficient Hybrid Online Learning with Unknown Distribution

Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback

Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective