On Two Continuum Armed Bandit Problems in High Dimensions |
| |
Authors: | Hemant Tyagi Sebastian U. Stich Bernd Gärtner |
| |
Affiliation: | 1. Department of Computer Science, Institute of Theoretical Computer Science, ETH Zürich, Zürich, Switzerland
|
| |
Abstract: | We consider the problem of continuum armed bandits where the arms are indexed by a compact subset of (mathbb {R}^{d}). For large d, it is well known that mere smoothness assumptions on the reward functions lead to regret bounds that suffer from the curse of dimensionality. A typical way to tackle this in the literature has been to make further assumptions on the structure of reward functions. In this work we assume the reward functions to be intrinsically of low dimension k ? d and consider two models: (i) The reward functions depend on only an unknown subset of k coordinate variables and, (ii) a generalization of (i) where the reward functions depend on an unknown k dimensional subspace of (mathbb {R}^{d}). By placing suitable assumptions on the smoothness of the rewards we derive randomized algorithms for both problems that achieve nearly optimal regret bounds in terms of the number of rounds n. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|