Deterministic policies based on maximum regrets in MDPs with imprecise rewards

Article type: Research Article

Authors: Alizadeh, Pegah^{a; *} | Traversi, Emiliano^b | Osmani, Aomar^b

Affiliations: [a] Léonard de Vinci Pôle Universitaire, Research Center, 92 916 Paris, La Défense, France. E-mail: pegah.alizadeh@devinci.fr | [b] LIPN-UMR CNRS 7030, Université Sorbonne Paris Nord, Villetaneuse, France. E-mails: emiliano.traversi@lipn.univ-paris13.fr, aomar.osmani@lipn.univ-paris13.fr

Correspondence: [*] Corresponding author. E-mail: pegah.alizadeh@devinci.fr.

Abstract: Markov Decision Process Models (MDPs) are a powerful tool for planning tasks and sequential decision-making issues. In this work we deal with MDPs with imprecise rewards, often used when dealing with situations where the data is uncertain. In this context, we provide algorithms for finding the policy that minimizes the maximum regret. To the best of our knowledge, all the regret-based methods proposed in the literature focus on providing an optimal stochastic policy. We introduce for the first time a method to calculate an optimal deterministic policy using optimization approaches. Deterministic policies are easily interpretable for users because for a given state they provide a unique choice. To better motivate the use of an exact procedure for finding a deterministic policy, we show some (theoretical and experimental) cases where the intuitive idea of using a deterministic policy obtained after “determinizing” the optimal stochastic policy leads to a policy far from the exact deterministic policy.

Keywords: Markov Decision Process, minimax regret, unknown rewards, branch-and-bound, deterministic policy, stochastic policy

DOI: 10.3233/AIC-190632

Journal: AI Communications, vol. 34, no. 4, pp. 229-244, 2021