%0 Conference Proceedings
%T Long-Term Values in Markov Decision Processes, (Co)Algebraically
%+ Department of Engineering Systems and Services [Delft ] (ESS)
%+ Department of mathematics [Bloomington]
%A Feys, Frank
%A Hansen, Helle, Hvid
%A Moss, Lawrence, S.
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 14th International Workshop on Coalgebraic Methods in Computer Science (CMCS)
%C Thessaloniki, Greece
%Y Corina Cîrstea
%I Springer International Publishing
%3 Coalgebraic Methods in Computer Science
%V LNCS-11202
%P 78-99
%8 2018-04-14
%D 2018
%R 10.1007/978-3-030-00389-0_6
%K Markov decision process
%K Long-term value
%K Discounted sum
%K Coalgebra
%K Algebra
%K Corecursive algebra
%K Fixpoint
%K Metric space
%Z Computer Science [cs]Conference papers
%X 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’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.
%G English
%Z TC 1
%Z WG 1.3
%2 https://inria.hal.science/hal-02044650/document
%2 https://inria.hal.science/hal-02044650/file/473364_1_En_6_Chapter.pdf
%L hal-02044650
%U https://inria.hal.science/hal-02044650
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG1-3
%~ IFIP-CMCS
%~ IFIP-LNCS-11202