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
Open official paper

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?