Independent Reading · 2022

Contextual Bandits with Large Action Spaces: Made Practical

Yinglun Zhu, Dylan J. Foster, John Langford, and Paul Mineiro · arXiv preprint

Contextual BanditsLarge Action SpacesOnline Learning

Full text

Read the Paper

Use View PDF or Download PDF to read the full paper on this device.

Paper Information

Authors
Yinglun Zhu, Dylan J. Foster, John Langford, and Paul Mineiro
Venue
arXiv preprint · 2022
Open official paper

Summary

This paper develops practical contextual-bandit algorithms for large or continuous linearly structured action spaces.

Core Idea

Regression and action-optimization oracles can avoid enumerating every action while preserving statistical guarantees.

Method

The authors propose SpannerIGW and a faster SpannerGreedy variant, derive action-space-independent guarantees, and evaluate them at scale.

Key Takeaways

  • Large action spaces need not imply runtime or memory linear in the number of actions.
  • Oracle-based design supports flexible reward models and efficient exploration.
  • Practical variants trade stronger regret guarantees for faster execution.

Questions

  • How sensitive is performance to approximate action-optimization oracles?
  • Can the approach handle action spaces without a known linear embedding?