Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation

Abstract

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.

arXiv commentPreprint of an Invited Review Article, In Fields Institute

References in corpus (16)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Best-Arm Identification in Linear Bandits
• Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
• Gamification of Pure Exploration for Linear Bandits
• Top-k Combinatorial Bandits with Full-Bandit Feedback
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits
• Graph Mining Meets Crowdsourcing: Extracting Experts for Answer Aggregation
• Robust Densest Subgraph Discovery
• Polynomial-time Algorithms for Multiple-arm Identification with Full-bandit Feedback
• Online Dense Subgraph Discovery via Blurred-Graph Feedback
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners
• Combinatorial Pure Exploration of Dueling Bandit
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting
• Towards Optimal and Efficient Best Arm Identification in Linear Bandits
• PAC Identification of Many Good Arms in Stochastic Multi-Armed Bandits