Independent Reading · 2016
Combinatorial Multi-Armed Bandit with General Reward Functions
Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu · NeurIPS
Multi-Armed BanditsCombinatorial OptimizationOnline Learning
Full text
Read the Paper
Use View PDF or Download PDF to read the full paper on this device.
Paper Information
- Authors
- Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu
- Venue
- NeurIPS · 2016
Summary
This paper generalizes combinatorial bandits to nonlinear rewards that may depend on complete outcome distributions rather than only their means.
Core Idea
Learning distributional confidence bounds enables online optimization when mean estimates are insufficient for evaluating a reward function.
Method
The authors introduce the stochastically dominant confidence bound algorithm and analyze it for general rewards, K-MAX, and expected-utility maximization.
Key Takeaways
- Nonlinear rewards may require learning distributions instead of expected values.
- Stochastic dominance provides an optimistic principle for distribution-dependent objectives.
- The framework gives logarithmic distribution-dependent and square-root distribution-independent regret.
Questions
- How does distribution estimation scale with many base arms?
- Can the method accommodate dependence among arm outcomes?