Search papers, labs, and topics across Lattice.
This paper explores multiobjective optimization in probabilistic programs by introducing a multiobjective preexpectation transformer that maps postexpectations to achievable values along a Pareto front. The authors extend existing frameworks to synthesize strategies that optimize multiple outcomes simultaneously, demonstrating soundness against operational semantics in infinite Markov Decision Processes (MDPs). Key results include the development of new synthesis rules that allow for mixed determinizations, showcasing practical applications through various case studies.
Achieving optimal outcomes in probabilistic programs is now possible with a novel framework that synthesizes strategies across multiple objectives simultaneously.
Probabilistic programs with nondeterminism model planning problems in which a strategy resolves the nondeterminism to optimize an expected outcome. We study the multiobjective setting, optimizing several outcomes at once along a Pareto front, and provide a deductive, program-level account of strategy synthesis. Its core is a multiobjective preexpectation transformer mapping a tuple of postexpectations to the set of simultaneously achievable values, an element of the convex Hoare powerdomain. It conservatively extends weakest preexpectations and lifts standard loop rules. We develop rules to synthesize witnessing strategies as mixed determinizations that randomize over non-probabilistic determinizations. We prove the transformer and synthesis rules sound against an operational MDP semantics, without requiring a finite state space: our approach can be seen as a symbolic approach - at program level - for multiobjective optimization over infinite MDPs. We demonstrate our machinery using various case studies.
