Recently, there have been growing interests in exploiting sparsity to facilitate the acquisition of signals with multiple components. A motivating example is cognitive sensing of signals that have sparse components over a wide frequency band. In this talk, we focus on combining online cognitive radio learning algorithms and advances in compressive sensing as well as FRI sampling. We specifically propose to formulate as multi-armed bandit problem the optimal selection of a compressive sensing “arm” tuning the K branches of a finite rate of innovation sampling structure. Our results will enable sensing performance for cognitive radios that are not limited by the Nyquist sampling rate constraint but rather by the intrinsic scarcity of spectrum holes.