Long-term values in markov decision processes, (Co)algebraically

Conference paper (2018)

Authors

F.M.V. Feys Energy and Industry
H.H. Hansen Energy and Industry
Lawrence S. Moss Indiana University - Purdue University
Research Group
Energy and Industry
Algebra Markov decision process Coalgebra Metric space Corecursive algebra Discounted sum Fixpoint Long-term value
More Info
expand_more

Published Date

2018

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Research Group

Energy and Industry

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’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.