| Autor: |
Dagan, Yuval, Crammer, Koby |
| Rok vydání: |
2018 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
We study a sequential resource allocation problem between a fixed number of arms. On each iteration the algorithm distributes a resource among the arms in order to maximize the expected success rate. Allocating more of the resource to a given arm increases the probability that it succeeds, yet with a cut-off. We follow Lattimore et al. (2014) and assume that the probability increases linearly until it equals one, after which allocating more of the resource is wasteful. These cut-off values are fixed and unknown to the learner. We present an algorithm for this problem and prove a regret upper bound of $O(\log n)$ improving over the best known bound of $O(\log^2 n)$. Lower bounds we prove show that our upper bound is tight. Simulations demonstrate the superiority of our algorithm. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
