While the objective in traditional multi-armed bandit problems is to find the arm with the highest mean, in many settings, finding an arm that best captures information about other arms is of interest. This objective, however, requires learning the underlying correlation structure and not just the means. Sensors placement for industrial surveillance and cellular network monitoring are a few applications, where the underlying correlation structure plays an important role. Motivated by such applications, we formulate the correlated bandit problem, where the objective is to find the arm with the lowest mean-squared error (MSE) in estimating all the arms. To this end, we derive first an MSE estimator based on sample variances/covariances and show that our estimator exponentially concentrates around the true MSE. Under a best-arm identification framework, we propose a successive rejects type algorithm and provide bounds on the probability of error in identifying the best arm. Using minimax theory, we also derive fundamental performance limits for the correlated bandit problem.

Consider a Gaussian memoryless multiple source (GMMS) with m components with joint probability distribution known only to lie in a given class of distributions. A subset of k ≤ m components is sampled and compressed with the objective of reconstructing all the m components within a specified level of distortion under a mean-squared error criterion. In Bayesian and nonBayesian settings, the notion of universal sampling rate-distortion function for Gaussian sources is introduced to capture the optimal tradeoffs among sampling, compression rate, and distortion level. Single-letter characterizations are provided for the universal sampling rate-distortion function. Our achievability proofs highlight the following structural property: it is optimal to compress and reconstruct first the sampled components of the GMMS alone, and then form estimates for the unsampled components based on the former.

We examine the coordinated and universal rate-efficient sampling of a subset of correlated discrete memoryless sources followed by lossy compression of the sampled sources. The goal is to reconstruct a predesignated subset of sources within a specified level of distortion. The combined sampling mechanism and rate distortion code are universal in that they are devised to perform robustly without exact knowledge of the underlying probability distribution of the sources. Single-letter characterizations are provided for a universal sampling rate distortion function for fixed-set and independent random sampling.

Consider a discrete memoryless multiple source with m component sources. A subset of k ≤ m sources are sampled at each time instant and jointly compressed in order to reconstruct all the m sources under a given distortion criterion. A sampling rate distortion function is studied for two main sampling schemes. First, for independent random sampling performed without knowledge of the source outputs, it is shown that the sampling rate distortion function is the same regardless of whether the decoder is informed or not of the sequence of sampling sets. Next, memoryless random sampling is considered with the sampler depending on the source outputs and with an informed decoder. It is shown that deterministic sampling, characterized by a conditional point-mass, is optimal and suffices to achieve the sampling rate distortion function. For memoryless random sampling with an uninformed decoder, an upper bound for the sampling rate distortion function is seen to possess a similar property of conditional point-mass optimality. It is shown by example that memoryless sampling with an informed decoder can outperform strictly any independent random sampler, and that memoryless sampling can do strictly better with an informed decoder than without.

Consider a discrete memoryless multiple source with m components of which k ≤ m possibly different sources are sampled at each time instant and jointly compressed in order to reconstruct all the m sources under a given distortion criterion. A new notion of sampling rate distortion function is introduced, and is characterized first for the case of fixed-set sampling. Next, for independent random sampling performed without knowledge of the source outputs, it is shown that the sampling rate distortion function is the same regardless of whether or not the decoder is informed of the sequence of sampled sets. Furthermore, memoryless random sampling is considered with the sampler depending on the source outputs and with an informed decoder. It is shown that deterministic sampling, characterized by a conditional point-mass, is optimal and suffices to achieve the sampling rate distortion function. For memoryless random sampling with an uninformed decoder, an upper bound for the sampling rate distortion function is seen to possess a similar property of conditional point-mass optimality. It is shown by example that memoryless sampling with an informed decoder can outperform strictly any independent random sampler, and that memoryless sampling can do strictly better with an informed decoder than without.