On Identifying Good Options under Combinatorially Structured Feedback in Finite Noisy Environments

Yifan Wu, Andras Gyorgy, Csaba Szepesvari
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1283-1291, 2015.

Abstract

We consider the problem of identifying a good option out of finite set of options under combinatorially structured, noisy feedback about the quality of the options in a sequential process: In each round, a subset of the options, from an available set of subsets, can be selected to receive noisy information about the quality of the options in the chosen subset. The goal is to identify the highest quality option, or a group of options of the highest quality, with a small error probability, while using the smallest number of measurements. The problem generalizes best-arm identification problems. By extending previous work, we design new algorithms that are shown to be able to exploit the combinatorial structure of the problem in a nontrivial fashion, while being unimprovable in special cases. The algorithms call a set multi-covering oracle, hence their performance and efficiency is strongly tied to whether the associated set multi-covering problem can be efficiently solved.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-wub15, title = {On Identifying Good Options under Combinatorially Structured Feedback in Finite Noisy Environments}, author = {Wu, Yifan and Gyorgy, Andras and Szepesvari, Csaba}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {1283--1291}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/wub15.pdf}, url = {https://proceedings.mlr.press/v37/wub15.html}, abstract = {We consider the problem of identifying a good option out of finite set of options under combinatorially structured, noisy feedback about the quality of the options in a sequential process: In each round, a subset of the options, from an available set of subsets, can be selected to receive noisy information about the quality of the options in the chosen subset. The goal is to identify the highest quality option, or a group of options of the highest quality, with a small error probability, while using the smallest number of measurements. The problem generalizes best-arm identification problems. By extending previous work, we design new algorithms that are shown to be able to exploit the combinatorial structure of the problem in a nontrivial fashion, while being unimprovable in special cases. The algorithms call a set multi-covering oracle, hence their performance and efficiency is strongly tied to whether the associated set multi-covering problem can be efficiently solved.} }
Endnote
%0 Conference Paper %T On Identifying Good Options under Combinatorially Structured Feedback in Finite Noisy Environments %A Yifan Wu %A Andras Gyorgy %A Csaba Szepesvari %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-wub15 %I PMLR %P 1283--1291 %U https://proceedings.mlr.press/v37/wub15.html %V 37 %X We consider the problem of identifying a good option out of finite set of options under combinatorially structured, noisy feedback about the quality of the options in a sequential process: In each round, a subset of the options, from an available set of subsets, can be selected to receive noisy information about the quality of the options in the chosen subset. The goal is to identify the highest quality option, or a group of options of the highest quality, with a small error probability, while using the smallest number of measurements. The problem generalizes best-arm identification problems. By extending previous work, we design new algorithms that are shown to be able to exploit the combinatorial structure of the problem in a nontrivial fashion, while being unimprovable in special cases. The algorithms call a set multi-covering oracle, hence their performance and efficiency is strongly tied to whether the associated set multi-covering problem can be efficiently solved.
RIS
TY - CPAPER TI - On Identifying Good Options under Combinatorially Structured Feedback in Finite Noisy Environments AU - Yifan Wu AU - Andras Gyorgy AU - Csaba Szepesvari BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-wub15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 1283 EP - 1291 L1 - http://proceedings.mlr.press/v37/wub15.pdf UR - https://proceedings.mlr.press/v37/wub15.html AB - We consider the problem of identifying a good option out of finite set of options under combinatorially structured, noisy feedback about the quality of the options in a sequential process: In each round, a subset of the options, from an available set of subsets, can be selected to receive noisy information about the quality of the options in the chosen subset. The goal is to identify the highest quality option, or a group of options of the highest quality, with a small error probability, while using the smallest number of measurements. The problem generalizes best-arm identification problems. By extending previous work, we design new algorithms that are shown to be able to exploit the combinatorial structure of the problem in a nontrivial fashion, while being unimprovable in special cases. The algorithms call a set multi-covering oracle, hence their performance and efficiency is strongly tied to whether the associated set multi-covering problem can be efficiently solved. ER -
APA
Wu, Y., Gyorgy, A. & Szepesvari, C.. (2015). On Identifying Good Options under Combinatorially Structured Feedback in Finite Noisy Environments. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:1283-1291 Available from https://proceedings.mlr.press/v37/wub15.html.

Related Material