Paper ID: 2203.16810

Adaptive Estimation of Random Vectors with Bandit Feedback: A mean-squared error viewpoint

Dipayan Sen, L. A. Prashanth, Aditya Gopalan

We consider the problem of sequentially learning to estimate, in the mean squared error (MSE) sense, a Gaussian $K$-vector of unknown covariance by observing only $m < K$ of its entries in each round. We first establish a concentration bound for MSE estimation. We then frame the estimation problem with bandit feedback, and propose a variant of the successive elimination algorithm. We also derive a minimax lower bound to understand the fundamental limit on the sample complexity of this problem.

Submitted: Mar 31, 2022