# On Polynomial Sized Mdp Succinct Policies

Paolo Liberatore **paolo@liberatore.org**
Dipartimento di Informatica e Sistemistica Universit`a di Roma "La Sapienza" Via Salaria 113, 00198, Roma, Italy

## Abstract

Policies of Markov Decision Processes (MDPs) determine the **next action to execute**
from the current state and, possibly, the history (the past states). When the number of states is large, succinct representations are often used to **compactly represent both the** MDPs and the policies in a reduced amount of space. In this paper, some problems related to the size of succinctly represented policies are analyzed. Namely, it is shown that some MDPs have policies that can only be represented in space super-polynomial in the size of the MDP, unless the polynomial hierarchy collapses. This fact motivates the study of the problem of deciding whether a given MDP has a policy of a given **size and reward. Since** some algorithms for MDPs work by finding a succinct representation of the value function, the problem of deciding the existence of a succinct representation of a value function of a given size and reward is also considered.

## 1. Introduction

Markov Decision Processes (MDPs) (Bellman, 1957) have been **used in AI for planning** when the effects of actions are only probabilistically known **(Puterman, 1994). The partially** observable extension (POMDP) formalizes scenarios in which the observations do not give a complete description of the state.

The best plan in such domains may not be a simple sequence of actions. Indeed, the best action to take may depend on the current state, which is known **(partially, for POMDPs)** only when the previous actions have been executed. Such conditional plans are named
"policies". Finding policies for MDPs is a problem that has been deeply investigated; algorithms have been developed, e.g., value iteration, policy iteration, and methods based on linear programming (Littman, Dean, & Kaebling, 1995). For POMDPs, variants of the value iteration algorithm have been developed (Cassandra, **Littman, & Zhang, 1997; Zhang**
& Zhang, 2001).

Formally, an MDP is composed of a set of states, a set of actions, the specification of the
(probabilistic) effects of actions, and a measure of how good **a state is considered (reward** function). Initially, MDPs were defined in an explicit form: **the states are the elements of**
a given set {s1, . . . , sn}; what is true or false in each state si**is not specified. The effects of**
the actions and the reward function are represented in an explicit form, e.g., if there are n states, a vector of n **elements represents the reward function (each element of the vector is** the reward of a state.)
While such explicit representation is simple, it is not practical to use in many cases.

Indeed, many real-world scenarios can be described by a set of variables (state variables);
for example, a set of Boolean variables can specify what is true or false in the current