This paper focuses on best-arm identification in multi-armed bandits with bounded rewards. We develop an algorithm that is a fusion of lil-UCB and KL-LUCB, offering the best qualities of the two algorithms in one method. This is achieved by proving a novel anytime confidence bound for the mean of bounded distributions, which is the analogue of the LIL-type bounds recently developed for sub-Gaussian distributions. We corroborate our theoretical results with numerical experiments based on the New Yorker Cartoon Caption Contest.

This paper investigates the problem of recovering the support of structured signals via adaptive compressive sensing. We examine several classes of structured support sets, and characterize the fundamental limits of accurately recovering such sets through compressive measurements, while simultaneously providing adaptive support recovery protocols that perform near optimally for these classes. We show that by adaptively designing the sensing matrix, we can attain significant performance gains over non-adaptive protocols. These gains arise from the fact that adaptive sensing can: 1) better mitigate the effects of noise and 2) better capitalize on the structure of the support sets.

In many practical settings one can sequentially and adaptively guide the collection of future data, based on information extracted from data collected previously. These sequential data collection procedures are known by different names, such as sequential experimental design, active learning, or adaptive sensing/sampling. The intricate relation between data analysis and acquisition in adaptive sensing paradigms can be extremely powerful, and often allows for reliable signal estimation and detection in situations where nonadaptive sensing would fail dramatically. In this paper, we investigate the problem of estimating the support of a structured sparse signal from coordinate-wise observations under the adaptive sensing paradigm. We present a general procedure for support set estimation that is optimal in a variety of cases and shows that through the use of adaptive sensing one can: 1) mitigate the effect of observation noise when compared with nonadaptive sensing and 2) capitalize on structural information to a much larger extent than possible with nonadaptive sensing. In addition to a general procedure to perform adaptive sensing in structured settings, we present both performance upper bounds, and corresponding lower bounds for both sensing paradigms.