Steady-State Planning in Expected Reward Multichain MDPs
This work provides a method for formally synthesizing decision-making policies with asymptotic steady-state guarantees for agents operating in general multichain MDP environments, which is a significant challenge in planning.
This paper addresses the steady-state planning problem in multichain Markov Decision Processes (MDPs), where the goal is to derive a policy that satisfies constraints on the proportion of time an agent spends in each state over an indefinite period. The authors propose a linear programming solution for this general case, proving that optimal solutions yield stationary policies with rigorous behavioral guarantees.
The planning domain has experienced increased interest in the formal synthesis of decision-making policies. This formal synthesis typically entails finding a policy which satisfies formal specifications in the form of some well-defined logic. While many such logics have been proposed with varying degrees of expressiveness and complexity in their capacity to capture desirable agent behavior, their value is limited when deriving decision-making policies which satisfy certain types of asymptotic behavior in general system models. In particular, we are interested in specifying constraints on the steady-state behavior of an agent, which captures the proportion of time an agent spends in each state as it interacts for an indefinite period of time with its environment. This is sometimes called the average or expected behavior of the agent and the associated planning problem is faced with significant challenges unless strong restrictions are imposed on the underlying model in terms of the connectivity of its graph structure. In this paper, we explore this steady-state planning problem that consists of deriving a decision-making policy for an agent such that constraints on its steady-state behavior are satisfied. A linear programming solution for the general case of multichain Markov Decision Processes (MDPs) is proposed and we prove that optimal solutions to the proposed programs yield stationary policies with rigorous guarantees of behavior.