Stochastic continuum armed bandit problem of few linear parameters in high dimensions
This addresses a high-dimensional bandit optimization problem with low intrinsic dimensionality, offering theoretical guarantees for efficient exploration.
The paper tackles the stochastic continuum armed bandit problem in high dimensions with reward functions depending on few linear parameters, and derives an efficient randomized algorithm achieving a regret bound of O(C(k,d) n^{(1+k)/(2+k)} (log n)^{1/(2+k)}) with high probability.
We consider a stochastic continuum armed bandit problem where the arms are indexed by the $\ell_2$ ball $B_{d}(1+ν)$ of radius $1+ν$ in $\mathbb{R}^d$. The reward functions $r :B_{d}(1+ν) \rightarrow \mathbb{R}$ are considered to intrinsically depend on $k \ll d$ unknown linear parameters so that $r(\mathbf{x}) = g(\mathbf{A} \mathbf{x})$ where $\mathbf{A}$ is a full rank $k \times d$ matrix. Assuming the mean reward function to be smooth we make use of results from low-rank matrix recovery literature and derive an efficient randomized algorithm which achieves a regret bound of $O(C(k,d) n^{\frac{1+k}{2+k}} (\log n)^{\frac{1}{2+k}})$ with high probability. Here $C(k,d)$ is at most polynomial in $d$ and $k$ and $n$ is the number of rounds or the sampling budget which is assumed to be known beforehand.