Learning Multiuser Channel Allocations in Cognitive Radio Networks: A Combinatorial Multi-Armed Bandit Formulation

The authors have presented in this paper a new kind of bandit problem that they refer to as a combinatorial multi-armed bandit. The key distinction of this formulation from the classic non-Bayesian multi-armed bandit problem is each arm is itself a combinatorial "Bundle" of components. The number of arms is consequently quite large and there are dependencies between the rewards provided by arms sharing common components. A slightly different formulation of their problem is to think of arms as being the components themselves, with multiple plays allowed simultaneously. But from this perspective too, there is a key difference from prior work: in their formulation, there are pre-specified restrictions on exactly which bundles of plays are allowed simultaneously.