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