Dr. V. Avanesov (WIAS Berlin)
Tuesday, December 3, 2019 - 15:00
Weierstraß-Institut
Mohrenstr. 39, 10117 Berlin, Raum: 405/406, 4. Etage
Seminar Modern Methods in Applied Stochastics and Nonparametric Statistics
In X-armed bandit problem an agent sequentially interacts with environment which yields a reward based on the vector input the agent provides. The agent's goal is to maximise the sum of these rewards across some number of time steps. The problem and its variations have been a subject of numerous studies, suggesting sub-linear and sometimes optimal strategies. The given paper introduces a new variation of the problem. We consider an environment, which can abruptly change its behaviour an unknown number of times. To that end we propose a novel strategy and prove it attains sub-linear cumulative regret. Moreover, the obtained regret bound matches the best known bound for GP-UCB for a stationary case, and approaches the minimax lower bound in case of highly smooth relation between an action and the corresponding reward. The theoretical result is supported by experimental study.
submitted by chschnei (christine.schneider@wias-berlin.de, 030 20372574)