Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure

We study the greedy (exploitation-only) algorithm in bandit problems with a known reward structure. We allow arbitrary finite reward structures, while prior work focused on a few specific ones. We fully characterize when the greedy algorithm asymptotically succeeds or fails, in the sense of sublinear vs. linear regret as a function of time. Our characterization identifies a partial identifiability property of the problem instance as the necessary and sufficient condition for the asymptotic success. Notably, once this property holds, the problem becomes easy-any algorithm will succeed (in the same sense as above), provided it satisfies a mild non-degeneracy condition. Our characterization extends to contextual bandits and interactive decision-making with arbitrary feedback. Examples demonstrating broad applicability and extensions to infinite reward structures are provided.

We have action set A and context set X . In each round t = 1, 2, . . ., a context x t ∈ X arrives, an algorithm chooses an action (arm) a t ∈ A, and a reward r t ∈ R is realized. The context is drawn 2. E.g., for Bayesian bandits with ≫ √ T arms, where the arms' mean rewards are sampled uniformly. 3. Essentially, the prior covers all reward functions arms → [0, 1] with probability density at least p > 0.