Name
Abstract | ||
|---|---|---|
We study the adversarial multi-armed bandit problem where the learner is supplied with partial observations modeled by afeedback graphand where shifting to a new action incurs a fixed switching cost. We give two new algorithms for this problem in the informed setting. Our best algorithm achieves a pseudo-regret of (O) over bar(gamma(G)T-1/3(2/3)), where gamma(G) is the domination number of the feedback graph. This significantly improves upon the previous best result for the same problem, which was based on the independence number of G. We also present matching lower bounds for our result that we describe in detail. Finally, we give a new algorithm with improved policy regret bounds when partial counterfactual feedback is available. |
Year | Venue | Keywords |
|---|---|---|
2019 | ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 32 (NIPS 2019) | domination number,independence number |
Field | DocType | Volume |
Graph,Mathematical optimization,Computer science,Theoretical computer science | Conference | 32 |
ISSN | Citations | PageRank |
1049-5258 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| R. Arora | 1 | 489 | 35.97 |
| Teodor Marinov | 2 | 7 | 3.54 |
| Mehryar Mohri | 3 | 4502 | 448.21 |