Covariance Matrix Adaptation for Multiobjective Multiarmed Bandits.

Area of Science:

• Machine Learning
• Optimization
• Decision Theory

Background:

• Multiarmed bandit algorithms, like upper confidence bound (UCB), are effective for regret minimization.
• Handling stochastic reward vectors with correlated objectives requires advanced techniques.
• Covariance matrix adaptation for Pareto UCB (CMA-PUCB) addresses multi-objective bandit problems with correlated rewards.

Purpose of the Study:

• To theoretically bound the cumulative pseudoregret for the CMA-PUCB algorithm.
• To establish bounds for approximating unknown covariance matrices in this context.
• To demonstrate the practical applicability of the CMA-PUCB method in complex environments.

Main Methods:

• Utilized a variant of Bernstein inequality for matrices to derive pseudoregret bounds.
• Developed an upper bound for approximating unknown covariance matrices based on sample size.
• Conducted simulations in a three-objective stochastic environment to validate the method.

Main Results:

• Established a logarithmic upper bound on cumulative pseudoregret concerning the number of arms, objectives, and samples.
• Provided an upper bound for covariance matrix approximation dependent on sample size and regret.
• Simulations confirmed the effectiveness and applicability of the CMA-PUCB algorithm.

Conclusions:

• The CMA-PUCB algorithm offers a principled approach to regret minimization in multi-objective bandit settings with correlated rewards.
• The derived theoretical bounds provide valuable insights into the algorithm's performance and sample complexity.
• The method is shown to be effective in practical, complex stochastic environments.