$f(\cdot) \asymp g(\cdot)$ for $f(\cdot) = \Theta(g(\cdot))$. Throughout this paper, we will use $C_0, C_1, C_2，\ldots$ to denote universal constants. For a vector $v$ and a matrix $M$, we will use $\|v\|_2$ and $\|M\|_{\op}$ to denote the vector $\ell_2$-norm and the matrix spectral norm (i.e., the maximum singular value), respectively. Moreover, for a real-valued symmetric matrix $M$, we denote the maximum eigenvalue and the minimum eigenvalue of $M$ by $\lambda_{\max}(M)$ and $\lambda_{\min}(M)$, respectively, and define $\|v\|_M^2:=v^T M v$ for any given vector $v$. For a given integer $N$, we denote the set $\{1,\ldots, N\}$ by $[N]$.

The rest of the paper is organized as follows. In Section \[sec:model\], we introduce the mathematical formulation of our models and define the regret. In Section \[sec:UCB\], we describe the proposed MLE-UCB policy and provide the regret analysis. The lower bound result is provided in Section \[sec:lower\]. In Section \[sec:comb\], we investigate the combinatorial optimization problem in MLE-UCB and propose the approximation algorithm and greedy heuristic. The multivariate case of the approximation algorithm is relegated to the appendix. In Section \[sec:numerical\], we provide the numerical studies. The conclusion and future directions are discussed in Section \[sec:conclusion\]. Some technical proofs are provided in the online 