Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Methods for computing state similarity in Markov Decision Processes
Norman Ferns, Pablo Castro, Doina Precup, Prakash Panangaden
Abstract:
A popular approach to solving large probabilistic systems relies on aggregating states based on a measure of similarity. Many approaches in the literature are heuristic. A number of recent methods rely instead on metrics based on the notion of bisimulation, or behavioral equivalence between states (Givan et al, 2001, 2003; Ferns et al, 2004). An integral component of such metrics is the Kantorovich metric between probability distributions. However, while this metric enables many satisfying theoretical properties, it is costly to compute in practice. In this paper, we use techniques from network optimization and statistical sampling to overcome this problem. We obtain in this manner a variety of distance functions for MDP state aggregation, which differ in the tradeoff between time and space complexity, as well as the quality of the aggregation. We provide an empirical evaluation of these trade-offs.
Keywords:
Pages: 174-181
PS Link:
PDF Link: /papers/06/p174-ferns.pdf
BibTex:
@INPROCEEDINGS{Ferns06,
AUTHOR = "Norman Ferns and Pablo Castro and Doina Precup and Prakash Panangaden",
TITLE = "Methods for computing state similarity in Markov Decision Processes",
BOOKTITLE = "Proceedings of the Twenty-Second Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-06)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2006",
PAGES = "174--181"
}


hosted by DSL   •   site info   •   help