Lexicographic Multi-Objective Bandits and Reinforcement Learning: Algorithms and Theory

Abstract

This thesis investigates a broad family of lexicographic multi-objective online decision-making problems, where an agent repeatedly selects actions and observes vector-valued rewards, each element corresponding to an objective of different priority. The agent first maximizes the most important objective. It looks at the second objective only among actions that are equally good on the first, and continues in this way down the priority list. Owing to its intuitive structure and strict priority semantics, the lexicographic model naturally arises in many real-world applications. For example, in recommendation systems, relevance is often prioritized over diversity. In medical resource allocation, critical-care outcomes typically take precedence over efficiency. This thesis develops a unified theoretical framework for lexicographic learning, proposing novel algorithms and regret analysis across multi-armed bandits, generalized linear bandits, Lipschitz bandits, and reinforcement learning.

First, in the classical multi-armed bandit setting, we bridge regret minimization and best arm identification under lexicographic preferences. To this end, we propose an elimination-based algorithm that exploits cross-objective reward information. By leveraging the structure of multiple objectives, our algorithm can surpass the lower bounds of single-objective settings.

Second, we investigate lexicographic Lipschitz bandits, which are characterized by continuous decision spaces and nonparametric reward functions. We design a zooming-based algorithm and derive its regret bounds, followed by a matching lower bound that establishes its optimality. We further propose an algorithm that does not require knowledge of the trade-off parameter between objectives.

Third, we extend lexicographic learning to generalized linear bandits, where the parametric reward model enables faster learning and leads to smaller regret than in nonparametric settings. In this framework, we introduce the first variance-aware multi-objective algorithm, whose regret bounds explicitly depend on reward variances. Compared with existing single-objective methods, it removes the need for prior variance knowledge and improves the variance-independent terms. We further design an efficient online variant for lexicographic generalized linear bandits, which achieves near-optimal worst-case regret.

Finally, we study lexicographic multi-objective reinforcement learning with linear transition dynamics. We develop the first multi-objective reinforcement learning algorithm with provable regret guarantees, achieving bounds that scale with the feature dimension, and episode horizon. The method extends naturally to misspecified linear models, where we provide robust regret guarantees.

Together, these results establish a comprehensive theoretical framework for lexicographic multi-objective decision-making across discrete, structured, continuous, and sequential environments. The thesis demonstrates that hierarchical objectives not only introduce new algorithmic challenges but also create opportunities: information sharing across objectives can fundamentally accelerate learning beyond what is achievable in single-objective settings.

Date of Award	15 Apr 2026
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Qingfu ZHANG (Supervisor)