Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation
| Title: | Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation |
|---|---|
| Authors: | Kuroki, Yuko, Honda, Junya, Sugiyama, Masashi |
| Publication Year: | 2020 |
| Collection: | Computer Science Statistics |
| Subject Terms: | Computer Science - Machine Learning, Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms, Computer Science - Social and Information Networks, Statistics - Machine Learning |
| More Details: | 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. Comment: Preprint of an Invited Review Article, In Fields Institute |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2012.15584 |
| Accession Number: | edsarx.2012.15584 |
| Database: | arXiv |
| FullText | Text: Availability: 0 CustomLinks: – Url: http://arxiv.org/abs/2012.15584 Name: EDS - Arxiv Category: fullText Text: View this record from Arxiv MouseOverText: View this record from Arxiv – Url: https://resolver.ebsco.com/c/xy5jbn/result?sid=EBSCO:edsarx&genre=article&issn=&ISBN=&volume=&issue=&date=20201231&spage=&pages=&title=Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation&atitle=Combinatorial%20Pure%20Exploration%20with%20Full-bandit%20Feedback%20and%20Beyond%3A%20Solving%20Combinatorial%20Optimization%20under%20Uncertainty%20with%20Limited%20Observation&aulast=Kuroki%2C%20Yuko&id=DOI: Name: Full Text Finder (for New FTF UI) (s8985755) Category: fullText Text: Find It @ SCU Libraries MouseOverText: Find It @ SCU Libraries |
|---|---|
| Header | DbId: edsarx DbLabel: arXiv An: edsarx.2012.15584 RelevancyScore: 1008 AccessLevel: 3 PubType: Report PubTypeId: report PreciseRelevancyScore: 1007.76666259766 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Kuroki%2C+Yuko%22">Kuroki, Yuko</searchLink><br /><searchLink fieldCode="AR" term="%22Honda%2C+Junya%22">Honda, Junya</searchLink><br /><searchLink fieldCode="AR" term="%22Sugiyama%2C+Masashi%22">Sugiyama, Masashi</searchLink> – Name: DatePubCY Label: Publication Year Group: Date Data: 2020 – Name: Subset Label: Collection Group: HoldingsInfo Data: Computer Science<br />Statistics – Name: Subject Label: Subject Terms Group: Su Data: <searchLink fieldCode="DE" term="%22Computer+Science+-+Machine+Learning%22">Computer Science - Machine Learning</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Discrete+Mathematics%22">Computer Science - Discrete Mathematics</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Data+Structures+and+Algorithms%22">Computer Science - Data Structures and Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Social+and+Information+Networks%22">Computer Science - Social and Information Networks</searchLink><br /><searchLink fieldCode="DE" term="%22Statistics+-+Machine+Learning%22">Statistics - Machine Learning</searchLink> – Name: Abstract Label: Description Group: Ab Data: 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.<br />Comment: Preprint of an Invited Review Article, In Fields Institute – Name: TypeDocument Label: Document Type Group: TypDoc Data: Working Paper – Name: URL Label: Access URL Group: URL Data: <link linkTarget="URL" linkTerm="http://arxiv.org/abs/2012.15584" linkWindow="_blank">http://arxiv.org/abs/2012.15584</link> – Name: AN Label: Accession Number Group: ID Data: edsarx.2012.15584 |
| PLink | https://login.libproxy.scu.edu/login?url=https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsarx&AN=edsarx.2012.15584 |
| RecordInfo | BibRecord: BibEntity: Subjects: – SubjectFull: Computer Science - Machine Learning Type: general – SubjectFull: Computer Science - Discrete Mathematics Type: general – SubjectFull: Computer Science - Data Structures and Algorithms Type: general – SubjectFull: Computer Science - Social and Information Networks Type: general – SubjectFull: Statistics - Machine Learning Type: general Titles: – TitleFull: Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Kuroki, Yuko – PersonEntity: Name: NameFull: Honda, Junya – PersonEntity: Name: NameFull: Sugiyama, Masashi IsPartOfRelationships: – BibEntity: Dates: – D: 31 M: 12 Type: published Y: 2020 |
| ResultId | 1 |