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
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?