Many decision problems can be characterized by a set of possible states and a cost associated with each possible state transition, hi this paper we discuss how to select a policy from a set of possible policies in the long term. If the cost matrix is not available the transition matrix can be used to compare expected return times to states. In our setting the transition matrix is defined by use of linguistic terms and as a consequence, the expected return times are fuzzy. In the case where the cost matrix is available, fuzzy average costs are computed. The resulting fuzzy quantities are compared by introducing the concept of minimizing sets. Finally, we look at the case where the transition takes place from a state to a state that is known to be an element of some subset of states, but we do not know which one. We use the Dempster–Shafer theory [Shafer 1976] together with techniques of Norton [Norton 1988] and Smetz [Smetz 1976] to approximate the transition probabilities