Budgeted Multi-Armed Bandit in Continuous Action Space

被引:6
作者
Trovo, Francesco [1 ]
Paladino, Stefano [1 ]
Restelli, Marcello [1 ]
Gatti, Nicola [1 ]
机构
[1] Politecn Milan, Milan, Italy
来源
ECAI 2016: 22ND EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE | 2016年 / 285卷
关键词
D O I
10.3233/978-1-61499-672-9-560
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Multi-Armed Bandits (MABs) have been widely considered in the last decade to model settings in which an agent wants to learn the action providing the highest expected reward among a fixed set of available actions during the operational life of a system. Classical techniques provide solutions that minimize the regret due to learning in settings where selecting an arm has no cost. Though, in many real world applications the learner has to pay some cost for pulling each arm and the learning process is constrained by a fixed budget B. This problem is addressed in the literature as the Budgeted MAB (BMAB). In this paper, for the first time, we study the problem of Budgeted Continuous-Armed Bandit (BCAB), where the set of the possible actions consists in a continuous set (e.g., a range of prices) and the learner suffers from a random reward and cost at each round. We provide a novel algorithm, named B-Zoom, which suffers a regret of (O) over tilde (Bd+1/d+2), where d is the Zooming dimension of the problem. Finally, we provide an empirical analysis showing that, despite a lower average performance, the proposed approach is more robust to adverse settings as compared to existing algorithms designed for BMAB.
引用
收藏
页码:560 / 568
页数:9
相关论文
共 50 条
[11]   Satisficing in Multi-Armed Bandit Problems [J].
Reverdy, Paul ;
Srivastava, Vaibhav ;
Leonard, Naomi Ehrich .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2017, 62 (08) :3788-3803
[12]   Multi-armed Bandit with Additional Observations [J].
Yun, Donggyu ;
Proutiere, Alexandre ;
Ahn, Sumyeong ;
Shin, Jinwoo ;
Yi, Yung .
PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS, 2018, 2 (01)
[13]   IMPROVING STRATEGIES FOR THE MULTI-ARMED BANDIT [J].
POHLENZ, S .
MARKOV PROCESS AND CONTROL THEORY, 1989, 54 :158-163
[14]   MULTI-ARMED BANDIT ALLOCATION INDEXES [J].
JONES, PW .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1989, 40 (12) :1158-1159
[15]   THE MULTI-ARMED BANDIT PROBLEM WITH COVARIATES [J].
Perchet, Vianney ;
Rigollet, Philippe .
ANNALS OF STATISTICS, 2013, 41 (02) :693-721
[16]   The Multi-fidelity Multi-armed Bandit [J].
Kandasamy, Kirthevasan ;
Dasarathy, Gautam ;
Schneider, Jeff ;
Poczos, Barnabas .
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 29 (NIPS 2016), 2016, 29
[17]   Multi-armed Bandit with Additional Observations [J].
Yun D. ;
Ahn S. ;
Proutiere A. ;
Shin J. ;
Yi Y. .
2018, Association for Computing Machinery, 2 Penn Plaza, Suite 701, New York, NY 10121-0701, United States (46) :53-55
[18]   Mean Field Equilibrium in Multi-Armed Bandit Game with Continuous Reward [J].
Wang, Xiong ;
Jia, Riheng .
PROCEEDINGS OF THE THIRTIETH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI 2021, 2021, :3118-3124
[19]   Multi-Armed Bandit in Action: Optimizing Performance in Dynamic Hybrid Networks [J].
Henri, Sebastien ;
Vlachou, Christina ;
Thiran, Patrick .
IEEE-ACM TRANSACTIONS ON NETWORKING, 2018, 26 (04) :1879-1892
[20]   CONTEXTUAL MULTI-ARMED BANDIT ALGORITHMS FOR PERSONALIZED LEARNING ACTION SELECTION [J].
Manickam, Indu ;
Lan, Andrew S. ;
Baraniuk, Richard G. .
2017 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2017, :6344-6348