CASIA OpenIR  > 09年以前成果
Infinitely Many-Armed Bandits with Budget Constraints
Li HF(李海芳)1; Yingce Xia2; Haifang Li
Conference NameThe 31st AAAI Conference on Artificial Intelligence
Conference Date2017/2/4-2017/2/9
Conference PlaceSan Francisco, California USA
AbstractWe study the infinitely many-armed bandit problem with budget constraints, where the number of arms can be infinite and much larger than the number of possible experiments. The player aims at maximizing his/her total expected reward under a budget constraint B for the cost of pulling arms. We introduce a weak stochastic assumption on the ratio of expected-reward to expected-cost of a newly pulled arm which characterizes its probability of being a near-optimal arm. We propose an algorithm named RCB-I to this new problem, in which the player first randomly picks K arms, whose order is sub-linear in terms of B, and then runs the algorithm for the finite-arm setting on the selected arms. Theoretical analysis shows that this simple algorithm enjoys a sub-linear regret in term of the budget B. We also provide a lower bound of any algorithm under Bernoulli setting. The regret bound of RCB-I matches the lower bound up to a logarithmic factor. We further extend this algorithm to the any-budget setting (i.e., the budget is unknown in advance) and conduct corresponding theoretical analysis.
KeywordMulti-armed Bandits Budget Constraints Infinitely Many Arms
Document Type会议论文
Corresponding AuthorHaifang Li
Recommended Citation
GB/T 7714
Li HF,Yingce Xia,Haifang Li. Infinitely Many-Armed Bandits with Budget Constraints[C],2016.
Files in This Item: Download All
File Name/Size DocType Version Access License
aaai_17_full.pdf(307KB)会议论文 开放获取CC BY-NC-SAView Download
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Li HF(李海芳)]'s Articles
[Yingce Xia]'s Articles
[Haifang Li]'s Articles
Baidu academic
Similar articles in Baidu academic
[Li HF(李海芳)]'s Articles
[Yingce Xia]'s Articles
[Haifang Li]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Li HF(李海芳)]'s Articles
[Yingce Xia]'s Articles
[Haifang Li]'s Articles
Terms of Use
No data!
Social Bookmark/Share
File name: aaai_17_full.pdf
Format: Adobe PDF
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.