Variance-Aware Lexicographic Generalized Linear Bandits: Unknown Variance and Tighter Bounds

This paper investigates the Lexicographic Multi-Objective Generalized Linear Bandit problem, in which a learner optimizes $m$ hierarchically ordered objectives by sequentially selecting arms and observing their corresponding reward vectors. While multi-objective bandits have been widely studied, existing work largely overlooks the exploitation of reward variance. Furthermore, current variance-aware approaches for generalized linear bandits typically require prior knowledge of the variance and suffer from a suboptimal variance-independent regret term of $\tilde{O}(\sqrt{dT})$. To address these limitations, we propose a novel variance-aware algorithm that achieves a regret bound of $\tilde{O}(d\sqrt{{\sum }_{t=1}^T({\sigma }_t^i{)}^2}+d)$ for any objective $i\in [m]$, where $({\sigma }_t^i{)}^2$, $d$, and $T$ represent the reward variance, arm dimension, and time horizon, respectively. Crucially, our algorithm eliminates the need for prior variance knowledge and significantly reduces the variance-independent term to $\tilde{O}(d)$. While this method relies on maximum likelihood estimation, which can be computationally intensive, we further propose a computationally efficient online alternative that achieves a regret bound of $\tilde{O}(d\sqrt{T})$. Finally, we validate our theoretical findings through both numerical simulations and real-world experiments.