Combinatorial Pure Exploration with Limited Observation and Beyond
102022 Data-driven Optimization Workshop: Combinatorial Pure Exploration with Limited Observation and Beyond
Speaker: Yuko Kuroki, The University of Tokyo
Although most combinatorial optimization models require exact parameters as inputs, it is often impossible to obtain them due to privacy issues or system constraints, and we need to deal with such uncertainty. In this talk, I will introduce recent work on combinatorial pure exploration with limited feedback for solving such combinatorial optimization under uncertainty. We first study the combinatorial pure exploration over graphs with full-bandit feedback, which aims to identify a dense component in a network only together with a noisy evaluation for a sampled subgraph (the offline problem is called the densest subgraph problem). Then we also study the general combinatorial pure exploration with full-bandit or partial-linear feedback, which can work for general combinatorial structures including size-k subsets, matchings, and paths. Finally, I will discuss further extensions and several open problems for future work in this line of research.