Sequential Learning of the Pareto Front for Multi-objective Bandits
We study the problem of sequential learning of the Pareto front in multi-objective multi-armed bandits. An agent is faced with K possible arms to pull. At each turn she picks one, and receives a vector-valued reward. When she thinks she has enough information to identify the Pareto front of the different arm means, she stops the game and gives an answer. We are interested in designing algorithms such that the answer given is correct with probability at least 1-$\delta$. Our main contribution is an efficient implementation of an algorithm achieving the optimal sample complexity when the risk $\delta$ is small. With K arms in d dimensions p of which are in the Pareto set, the algorithm runs in time O(Kp^d) per round.
Code (1)
Tasks
Multi-Armed BanditsSimilar Papers 제목 키워드 기반
Multi-Objective Generalized Linear Bandits
In this paper, we study the multi-objective bandits (MOB) problem, where a learner repeatedly selects one arm to play and then receives a reward vector consisting of multiple objectives. MOB has found many real-world app…
Multi-Armed BanditsSURF: Steering the Scalarization Weight to Uniformly Traverse the Pareto Front
Scalarization is widely used in multi-objective optimization owing to its simplicity and scalability. In many applications, the goal is to generate solutions that represent diverse user preferences, ideally with uniform …
Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Bandits
Identifying Pareto optimal solutions is critical to support multi-objective decision-making. We introduce the first anytime Multi-Objective Multi-Armed Bandit algorithm for the Pareto Set Identification problem, taking a…
Multi-Armed BanditsAchieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits
We study the Pareto frontier of two archetypal objectives in multi-armed bandits, namely, regret minimization (RM) and best arm identification (BAI) with a fixed horizon. It is folklore that the balance between exploitat…
Multi-Armed BanditsProbe-then-Commit Multi-Objective Bandits: Theoretical Benefits of Limited Multi-Arm Feedback
We study an online resource-selection problem motivated by multi-radio access selection and mobile edge computing offloading. In each round, an agent chooses among $K$ candidate links/servers (arms) whose performance is …