The biobjective multiarmed bandit: learning approximate lexicographic optimal allocations

Abstract

We consider a biobjective sequential decision-making problem where an allocation (arm) is called ϵ lexicographic optimal if its expected reward in the first objective is at most ϵ smaller than the highest expected reward,and its expected reward in the second objective is at least the expected reward of a lexicographic optimal arm. Thegoal of the learner is to select arms that are ϵ lexicographic optimal as much as possible without knowing the armreward distributions beforehand. For this problem, we first show that the learner’s goal is equivalent to minimizing theϵ lexicographic regret, and then, propose a learning algorithm whose ϵ lexicographic gap-dependent regret is boundedand gap-independent regret is sublinear in the number of rounds with high probability. Then, we apply the proposedmodel and algorithm for dynamic rate and channel selection in a cognitive radio network with imperfect channel sensing.Our results show that the proposed algorithm is able to learn the approximate lexicographic optimal rate–channel pairthat simultaneously minimizes the primary user interference and maximizes the secondary user throughput.