论文标题
组合纯探索与全班姓氏反馈及其他：在不确定性下解决组合优化，观察到有限的观察
Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation
论文作者
论文摘要
组合优化是在理论计算机科学和运营研究中广泛研究的基本研究领域之一。当开发用于组合优化的算法时，通常假定诸如边缘权重的参数被称为输入。但是，由于输入参数通常不确定或最初在许多应用程序（例如推荐系统，众包，通信网络和在线广告）中通常不确定或最初未知，因此可能无法实现此假设。为了解决这种不确定性，对多军匪徒（CPE）及其变体组合纯粹探索的问题引起了人们的关注。较早的CPE工作已经研究了半一样的反馈，或者假设每个单独的边缘的结果始终均可在所有一轮中访问。但是，由于诸如预算上限或隐私问题之类的实际限制，这种强烈的反馈并不总是在最近的应用中获得。在本文中，我们回顾了最近提出的针对有限反馈的组合纯探索问题的技术。
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.
