Relational Expressivity Coverage: Comparing Risk-Sensitive Criteria for SSP Problems

• Igor Miyamura Agostinho USP
• Valdinei Freire da Silva USP

Resumo

Markov Decision Processes (MDPs) are commonly used to model sequential decision-making under uncertainty. A notable subclass is the Stochastic Shortest Path (SSP) problem, in which an agent aims to reach a goal state, modeled as absorbing, while minimizing accumulated costs. Policies in SSPs induce the random variable accumulated cost and its corresponding probability distribution function, and decision criteria summarize these distributions into scalar values to guide policy comparison and define optimality. In this work, we propose the Relational Expressivity Coverage method, which quantifies a criterion’s ability to represent preference relations through parameter variation. We apply this framework to the One-State Many-Actions (OSMA) problem and compare multiple risk-sensitive criteria from the literature in terms of their expressivity.