On Polynomial Sized MDP Succinct Policies

Details On Polynomial Sized MDP Succinct Policies On Polynomial Sized MDP Succinct Policies

2011-06-24

arxiv.org/abs/1106.4866v1

Journal Of Artificial Intelligence Research, Volume 21, pages 551-577, 2004

Computer Science

Artificial Intelligence

Scientific paper

10.1613/jair.1134

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.

Affiliated with

Also associated with

No associations

Rating

On Polynomial Sized MDP Succinct Policies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Polynomial Sized MDP Succinct Policies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Polynomial Sized MDP Succinct Policies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-393614