Greedy Algorithm 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingMulti-Armed BanditsSimilar Papers 제목 키워드 기반
Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis
Bandit learning algorithms typically involve the balance of exploration and exploitation. However, in many practical applications, worst-case scenarios needing systematic exploration are seldom encountered. In this work,…
Multi-Armed BanditsStochastic Low-rank Tensor Bandits for Multi-dimensional Online Decision Making
Multi-dimensional online decision making plays a crucial role in many real applications such as online recommendation and digital marketing. In these problems, a decision at each time is a combination of choices from dif…
Decision MakingMarketingWhen Are Linear Stochastic Bandits Attackable?
We study adversarial attacks on linear stochastic bandits: by manipulating the rewards, an adversary aims to control the behaviour of the bandit algorithm. Perhaps surprisingly, we first show that some attack goals can n…
Decision MakingRecommendation SystemsSharp Convergence Rates for Matching Pursuit
We study the fundamental limits of matching pursuit, or the pure greedy algorithm, for approximating a target function $ f $ by a linear combination $f_n$ of $n$ elements from a dictionary. When the target function is co…
MINTS: Minimalist Thompson Sampling
The Bayesian paradigm offers principled tools for sequential decision-making under uncertainty, but its reliance on a probabilistic model for all parameters can hinder the incorporation of complex structural constraints.…
Multi-Armed Bandits