Reproduce “Contextual Bandit Algorithms with Supervised Learning Guarantees” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, Robert E. Schapire
Exp4.P adapts exponential-weights contextual bandits with variance-aware confidence corrections, achieving high-probability regret of order O(√(KT ln(N/δ))) against the best of N policies under adversarial feedback. A VC-dimension extension gives a roughly O(√(T(d ln T + ln(1/δ)))) guarantee for stochastic contextual problems, while a Yahoo! news recommendation study shows that stronger exploration can produce the best deployed policy despite lower online learning rewards.
Key insights
- Variance control, rather than unbiasedness alone, is central to obtaining reliable square-root regret under contextual bandit feedback.
- The cost of competing with a finite expert class scales logarithmically with the number of experts and as √K with the number of actions, while the VC extension replaces class size with combinatorial complexity.
- More exploitative behavior can improve rewards during online learning without producing the best final policy; in the recommendation experiment, Exp4.P had lower learning-bucket reward but the strongest deployment performance.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.