\section{Introduction} \label{sec:intro}
\input{sources/introduction}

\section{Related Work} \label{sec:related}
\input{sources/related}

\section{Problem Formulation} \label{sec:problem}
\input{sources/problem}

\section{Learning Algorithms and Regret Bounds}\label{sec:case1}

\textbf{A Learning Algorithm for Case 1:}
\input{sources/case1}

\textbf{A Learning Algorithm for Case 2:}
\input{sources/case2}

\textbf{A Learning Algorithm for Case 3:}
\input{sources/case3}

\section{Experiments} \label{sec:experiments}
\input{sources/experiments}

\section{Conclusion and Future Work} \label{sec:conc}
We proposed a new multiobjective MAB problem, called the Lex-MAB, where the learner aims to minimize its regret with respect to lexicographic optimal arms. We studied the Lex-MAB with and without prior information on the expected rewards. We proved that the regret is uniformly bounded when the learner knows either the lexicographic optimal expected rewards or near-lexicographic optimal expected rewards. \reva{We also made a connection between knowing near-lexicographic optimal expected rewards and satisficing, and proved that uniformly bounded regret can be achieved for the MAB with satisficing objectives.} Interestingly, we showed that the regret incurred in an objective also depends on the prior information and observations from the other objectives. We also showed that the learner can still achieve $\tilde{O}(T^{2/3})$ gap-free regret without prior information. An important open question is whether $O(\sqrt{T})$ gap-free regret can be achieved in the Lex-MAB. This will answer the question of whether learning in the Lex-MAB without prior information is fundamentally more difficult than learning in the classical stochastic MAB without prior information. The case where there is prior information only for a subset of objectives is also worth investigating in the future. Another important future research direction is to extend the current work in the multiobjective MAB to minimize the regret with respect to a target arm other than a lexicogrpahic optimal arm by exploiting the prior information about the expected rewards of the target arm. 

\newpage

\bibliographystyle{IEEEtran}












\subsection{MAB with Prior Information}

\citet{lai1985asymptotically} shows that in the classical stochastic MAB problem, for any uniformly good policy the regret grows at least logarithmically over time. As opposed to this, \citet{lai1984optimal} proves for the two-armed stochastic bandit that when the learner has prior information on the maximum expected reward $\mu^*$ and the minimum nonzero suboptimality gap $\Delta$, there exists policies that can achieve uniformly bounded regret. This idea is further investigated in \citet{bubeck2013bounded}, which shows that bounded regret of order $1/\Delta$ is achieved for the case with finitely many arms when the learner knows $\mu^*$ and a positive lower bound on $\Delta$. 
\rev{\citet{garivier} studies the case where only $\mu^*$ is known and proposes an algorithm with bounded regret of order $\log(1/\Delta) (1/\Delta)$, and also proves a lower bound of order $1/\Delta$. This paper also provides a generic tool to prove gap-dependent lower bounds on the regret.} Similarly, \citet{bubeck2013prior} considers Thompson sampling and shows that its regret is uniformly bounded when $\mu^*$ and a positive lower bound on $\Delta$ are known. On the other hand, \citet{vakili2013achieving} considers a weaker prior information model where the learner knows a near-optimal expected reward $\eta$, which can be computed using $\mu^*$ and a positive lower bound on $\Delta$. The proposed algorithm obtains $\sum_a \Delta_a/\delta^3$ regret, where $\delta=\mu^*-\eta<\Delta$ and $\Delta_a$ is the suboptimality gap of arm $a$.
\citet{mersereau2009structured} and \citet{lattimore2014bounded} consider as prior information the knowledge of parametrized expected reward functions for each arm. In these works, the only unknown is the true parameter, which can be estimated by using reward observations from all of the arms. 

Different from the works mentioned above, in this paper we consider a multiobjective MAB problem with lexicographically ordered objectives. We design algorithms that exploit the prior information in all objectives simultaneously to rule out arms that are not lexicographic optimal. \rev{Our regret bounds match the one in \cite{garivier} and improve the one in \cite{vakili2013achieving} for the case with a single objective.}




Numerous works have investigated regret minimization in multiobjective variants of the MAB problem. For instance, \citet{drugan2013designing} defines for each suboptimal arm its distance to the Pareto front as the Pareto suboptimality gap and the regret as the sum of the Pareto suboptimality gaps of the arms chosen by the learner. It proposes a learning algorithm that achieves $O(\log T)$ gap dependent Pareto regret. \citet{turgay2018multi} considers the multiobjective contextual MAB problem with similarity information, and extends the contextual zooming algorithm in \citet{slivkins2014contextual} to minimize the Pareto regret while making fair selections among the estimated Pareto optimal arms. The proposed algorithm is shown to achieve $\tilde{O}(T^{(1+d_p)/(2+d_p)})$ Pareto regret where $d_p$ is the Pareto zooming dimension. In addition, \citet{tekin2018multi} considers a biobjective contextual MAB problem with lexicographically ordered objectives. Unlike this work, we study the general case with $D$ lexicographically ordered objectives and focus on the importance of prior information in learning. 


Our problem is also related to the tresholding MAB studied in \citet{locatelli2016optimal} and satisficing MAB studied in \citet{reverdy2017satisficing}. Specifically, if the prior information is given with respect to a target arm which is not necessarily a lexicographic optimal arm, and the regret in each objective is defined with respect to the expected reward of the target arm in that objective, then our algorithms for the cases with prior information can easily be adapted to minimize the regret with respect to the target arm. \reva{Specifically, we adapt our second case to the satisfaction-in-mean-reward problem introduced in \cite{reverdy2017satisficing} and prove that our algorithm achieves bounded regret for this problem as well.}\footnote{\reva{See Section \ref{sec:satisficing} for our results on the multiarmed bandit with satisficing objectives.}}
 



