Timezone: »

 
Poster
Rotting Infinitely Many-Armed Bandits
Jung-hun Kim · Milan Vojnovic · Se-Young Yun

Tue Jul 19 03:30 PM -- 05:30 PM (PDT) @ Hall E #1017
in Poster Session 1 »
We consider the infinitely many-armed bandit problem with rotting rewards, where the mean reward of an arm decreases at each pull of the arm according to an arbitrary trend with maximum rotting rate $\varrho=o(1)$. We show that this learning problem has an $\Omega(\max\{\varrho^{1/3}T, \sqrt{T}\})$ worst-case regret lower bound where $T$ is the time horizon. We show that a matching upper bound $\tilde{O}(\max\{\varrho^{1/3}T, \sqrt{T}\})$, up to a poly-logarithmic factor, can be achieved by an algorithm that uses a UCB index for each arm and a threshold value to decide whether to continue pulling an arm or remove the arm from further consideration, when the algorithm knows the value of the maximum rotting rate $\varrho$. We also show that an $\tilde{O}(\max\{\varrho^{1/3}T, T^{3/4}\})$ regret upper bound can be achieved by an algorithm that does not know the value of $\varrho$, by using an adaptive UCB index along with an adaptive threshold value.
Keywords: T: Learning Theory · T: Online Learning and Bandits
[ Slides]  [ Poster]  [ Paper PDF] 

Author Information

Jung-hun Kim (KAIST)
Milan Vojnovic (London School of Economics)
Se-Young Yun (KAIST)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors