kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Combinatorial Pure Exploration with Continuous and Separable Reward Functions and Its Applications
Tsinghua Univ, Beijing, Peoples R China..ORCID iD: 0000-0003-1193-6157
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Decision and Control Systems (Automatic Control).ORCID iD: 0000-0003-4742-2473
Ant Financial Grp, Hangzhou, Peoples R China..
Microsoft Res, Beijing, Peoples R China..
2018 (English)In: Proceedings Of The Twenty-Seventh International Joint Conference On Artificial Intelligence / [ed] Lang, J, IJCAI-INT JOINT CONF ARTIF INTELL , 2018, p. 2291-2297Conference paper, Published paper (Refereed)
Abstract [en]

We study the Combinatorial Pure Exploration problem with Continuous and Separable reward functions (CPE-CS) in the stochastic multi-armed bandit setting. In a CPE-CS instance, we are given several stochastic arms with unknown distributions, as well as a collection of possible decisions. Each decision has a reward according to the distributions of arms. The goal is to identify the decision with the maximum reward, using as few arm samples as possible. The problem generalizes the combinatorial pure exploration problem with linear rewards, which has attracted significant attention in recent years. In this paper, we propose an adaptive learning algorithm for the CPE-CS problem, and analyze its sample complexity. In particular, we introduce a new hardness measure called the consistent optimality hardness, and give both the upper and lower bounds of sample complexity. Moreover, we give examples to demonstrate that our solution has the capacity to deal with non-linear reward functions.

Place, publisher, year, edition, pages
IJCAI-INT JOINT CONF ARTIF INTELL , 2018. p. 2291-2297
Series
IJCAI International Joint Conference on Artificial Intelligence, ISSN 1045-0823
National Category
Business Administration Other Mathematics Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:kth:diva-319028DOI: 10.24963/ijcai.2018/317ISI: 000764175402060Scopus ID: 2-s2.0-85055687549OAI: oai:DiVA.org:kth-319028DiVA, id: diva2:1698857
Conference
27th International Joint Conference on Artificial Intelligence (IJCAI), JUL 13-19, 2018, Stockholm, SWEDEN
Note

Part of proceedings: ISBN 978-0-9992411-2-7

QC 20220926

Available from: 2022-09-26 Created: 2022-09-26 Last updated: 2023-02-06Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Ok, Jungseul

Search in DiVA

By author/editor
Huang, WeiranOk, Jungseul
By organisation
Decision and Control Systems (Automatic Control)
Business AdministrationOther MathematicsProbability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 21 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf