Can I read Combinatorial Pure Exploration with Bottleneck Reward Function on EtoBox?

Combinatorial Pure Exploration with Bottleneck Reward Function by Du, Yihan; Kuroki, Yuko; Chen, Wei is a scholarly article available to read on EtoBox.

What is Combinatorial Pure Exploration with Bottleneck Reward Function about?

In this paper, we study the Combinatorial Pure Exploration problem with the Bottleneck reward function (CPE-B) under the fixed-confidence (FC) and fixed-budget (FB) settings. In CPE-B, given a set of base arms and a collection of subsets of base arms (super arms) following a certain combinatorial constraint, a learner sequentially plays a base arm and observes its random reward, with the objective of finding the optimal super arm with the maximum bottleneck value, defined as the minimum expected reward of the base arms contained in the super arm. CPE-B captures a variety of practical scenarios such as network routing in communication networks, and its \emph{unique challenges} fall on how to utilize the bottleneck property to save samples and achieve the statistical optimality. None of the existing CPE studies (most of them assume linear rewards) can be adapted to solve such challenges, and thus we develop brand-new techniques to handle them. For the FC setting, we propose novel algorithms with optimal sample complexity for a broad family of instances and establish a matching lower bound to demonstrate the optimality (within a logarithmic factor). For the FB setting, we design an al

Author

Du, Yihan; Kuroki, Yuko; Chen, Wei

Published

2021

Language

EN