Combinatorial Pure Exploration with Full-bandit Feedback and Beyond:
  Solving Combinatorial Optimization under Uncertainty with Limited Observation
  Combinatorial optimization is one of the fundamental research fields that has
been extensively studied in theoretical computer science and operations
research. When developing an algorithm for combinatorial optimization, it is
commonly assumed that parameters such as edge weights are exactly known as
inputs. However, this assumption may not be fulfilled since input parameters
are often uncertain or initially unknown in many applications such as
recommender systems, crowdsourcing, communication networks, and online
advertisement. To resolve such uncertainty, the problem of combinatorial pure
exploration of multi-armed bandits (CPE) and its variants have recieved
increasing attention. Earlier work on CPE has studied the semi-bandit feedback
or assumed that the outcome from each individual edge is always accessible at
all rounds. However, due to practical constraints such as a budget ceiling or
privacy concern, such strong feedback is not always available in recent
applications. In this article, we review recently proposed techniques for
combinatorial pure exploration problems with limited feedback.
