  We consider a finite-armed structured bandit problem in which mean rewards of
different arms are known functions of a common hidden parameter $\theta^*$.
Since we do not place any restrictions of these functions, the problem setting
subsumes several previously studied frameworks that assume linear or invertible
reward functions. We propose a novel approach to gradually estimate the hidden
$\theta^*$ and use the estimate together with the mean reward functions to
substantially reduce exploration of sub-optimal arms. This approach enables us
to fundamentally generalize any classic bandit algorithm including UCB and
Thompson Sampling to the structured bandit setting. We prove via regret
analysis that our proposed UCB-C algorithm (structured bandit versions of UCB)
pulls only a subset of the sub-optimal arms $O(\log T)$ times while the other
sub-optimal arms (referred to as non-competitive arms) are pulled $O(1)$ times.
As a result, in cases where all sub-optimal arms are non-competitive, which can
happen in many practical scenarios, the proposed algorithms achieve bounded
regret. We also conduct simulations on the Movielens recommendations dataset to
demonstrate the improvement of the proposed algorithms over existing structured
bandit algorithms.
