# Bi-Objective Lexicographic Optimization in Markov Decision Processes with Related Objectives

arXiv: https://arxiv.org/abs/2305.09634 · HTML: https://mlsanity.com/paper/2305.09634/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2023.

## Built on by (most cited first, 2 of 2)

- [Mixing Any Cocktail with Limited Ingredients: On the Structure of Payoff Sets in Multi-Objective POMDPs and its Impact on Randomised Strategies](https://mlsanity.com/paper/2502.18296/) (2025)
- [Composition of Nondeterministic and Stochastic Services for LTLf Task Specifications](https://mlsanity.com/paper/2311.18114/) (2023)

## Abstract (arXiv)

We consider lexicographic bi-objective problems on Markov Decision Processes (MDPs), where we optimize one objective while guaranteeing optimality of another. We propose a two-stage technique for solving such problems when the objectives are related (in a way that we formalize). We instantiate our technique for two natural pairs of objectives: minimizing the (conditional) expected number of steps to a target while guaranteeing the optimal probability of reaching it; and maximizing the (conditional) expected average reward while guaranteeing an optimal probability of staying safe (w.r.t. some safe set of states). For the first combination of objectives, which covers the classical frozen lake environment from reinforcement learning, we also report on experiments performed using a prototype implementation of our algorithm and compare it with what can be obtained from state-of-the-art probabilistic model checkers solving optimal reachability.