Covariance Matrix Adaptation for Multiobjective Multiarmed Bandits

摘要

Upper confidence bound (UCH) is a successful multiarmed bandit for regret minimization. The covariance matrix adaptation (CMA) for Pareto UCB (CMA-PUCB) algorithm considers stochastic reward vectors with correlated objectives. We upper bound the cumulative pseudoregret of pulling suboptimal arms for the CMA-PUCB algorithm to logarithmic number of arms K, objectives D, and samples n, 0(In(n DK) Sigma(i) (parallel to Sigma(i)parallel to(2)/Delta(i))), using a variant of Berstein inequality for matrices, where Delta(i) is the regret of pulling the suboptimal arm i. For unknown covariance matrices between objectives Sigma(i), we upper bound the approximation of the covariance matrix using the number of samples to o(n ln(n DK) + ln(2)(nDK) Sigma(i) (1/Delta(i))) Simulations on a three objective stochastic environment show the applicability of our method.