@inproceedings{3c60f47684bd47f08bada048d74f37c9,
title = "Long-term values in markov decision processes, (Co)algebraically",
abstract = "This paper studies Markov decision processes (MDPs) from the categorical perspective of coalgebra and algebra. Probabilistic systems, similar to MDPs but without rewards, have been extensively studied, also coalgebraically, from the perspective of program semantics. In this paper, we focus on the role of MDPs as models in optimal planning, where the reward structure is central. The main contributions of this paper are (i) to give a coinductive explanation of policy improvement using a new proof principle, based on Banach{\textquoteright}s Fixpoint Theorem, that we call contraction coinduction, and (ii) to show that the long-term value function of a policy with respect to discounted sums can be obtained via a generalized notion of corecursive algebra, which is designed to take boundedness into account. We also explore boundedness features of the Kantorovich lifting of the distribution monad to metric spaces.",
keywords = "Algebra, Coalgebra, Corecursive algebra, Discounted sum, Fixpoint, Long-term value, Markov decision process, Metric space",
author = "Feys, {Frank M.V.} and Hansen, {Helle Hvid} and Moss, {Lawrence S.}",
year = "2018",
doi = "10.1007/978-3-030-00389-0_6",
language = "English",
isbn = "9783030003883",
volume = "11202 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "78--99",
booktitle = "Coalgebraic Methods in Computer Science - 14th IFIP WG 1.3 International Workshop, CMCS 2018, Colocated with ETAPS 2018, Revised Selected Papers",
note = "14th International Workshop on Coalgebraic Methods in Computer Science, CMCS 2018 Colocated with ETAPS 2018 ; Conference date: 14-04-2018 Through 15-04-2018",
}