Information-Theoretic Analysis of Multi-Objective Bandits: Pareto Violations and Gap-Based Regret

We study Bayesian multi-objective bandits and ask a basic information-theoretic question: what aspects of an unknown environment must be resolved to achieve low regret? We show that the answer depends on the regret criterion and on the resolution of information needed to represent the corresponding loss. We first consider Pareto-violation regret, which incurs unit loss whenever the selected action is dominated. Because this loss depends only on Pareto membership, the Pareto-optimal set provides a natural information target. We introduce a separation-based measure of the difficulty of distinguishing among competing candidate Pareto sets, relate it to information gain about the unknown Pareto-optimal set, and use this connection to analyze Thompson Sampling and develop an Information-Directed Sampling strategy. We establish sublinear Bayesian regret under uniform and polynomially decaying separation and prove a lower bound showing that weak separability can impose an unavoidable statistical cost. We then consider gap-based Pareto regret, which measures the magnitude of Pareto suboptimality. Here, Pareto-set information is generally too coarse for a direct magnitude-sensitive analysis: distinct environments can share the same Pareto set while inducing different reward geometries and hence different Pareto gaps, and averaging over environments consistent with the same Pareto set need not preserve the Pareto dominance relations. This motivates retaining finer information about the environment that preserves the relevant reward geometry. We develop parameter-level information-theoretic analyses of Thompson Sampling and Information-Directed Sampling to derive gap-based Pareto regret guarantees. Together, our results reveal a hierarchy in the information needed for multi-objective learning: binary Pareto membership can be controlled through information about the Pareto set, whereas quantitative Pareto-gap suboptimality can require a finer representation of reward geometry.