published_or_final_version / abstract / toc / Computer Science and Information Systems / Doctoral / Doctor of Philosophy

published_or_final_version / abstract / toc / Computer Science and Information Systems / Doctoral / Doctor of Philosophy

published_or_final_version / Computer Science / Master / Master of Philosophy

Probabilistic bisimulation is a widely studied equivalence relation for stochastic systems. However, it requires the behavior of the states to match on actions with matching labels. This does not allow bisimulation to capture symmetries in the system. In this thesis we define lax probabilistic bisimulation, in which actions are only required to match within given action equivalence classes. We provide a logical characterization and an algorithm for computing this equivalence relation for finite systems. We also specify a metric on states which assigns distance 0 to lax-bisimilar states. We end by examining the use of lax bisimulation for analyzing Markov Decision Processes (MDPs) and show that it corresponds to the notion of a MDP homomorphism, introduced by Ravindran & Barto. Our metric provides an algorithm for generating an approximate MDP homomorphism and provides bounds on the quality of the best control policy that can be computed using this approximation.

No description available.

No description available.

No description available.

Learning agents often find themselves in environments in which rare significant events occur independently of their current choice of action. Traditional reinforcement learning algorithms sample events according to their natural probability of occurring, and therefore tend to exhibit slow convergence and high variance in such environments. In this thesis, we assume that learning is done in a simulated environment in which the probability of these rare events can be artificially altered. We present novel algorithms for both policy evaluation and control, using both tabular and function approximation representations of the value function. These algorithms automatically tune the rare event probabilities to minimize the variance and use importance sampling to correct for changes in the dynamics. We prove that these algorithms converge, provide an analysis of their bias and variance, and demonstrate their utility in a number of domains, including a large network planning task.

Thesis (M.S.)--West Virginia University, 2007. / Title from document title page. Document formatted into pages; contains xiv, 174 p. : ill. (some col.). Includes abstract. Includes bibliographical references (p. 172-174).

Thesis (Ph.D.)--Tufts University, 2001. / Adviser: Alva Couch. Submitted to the Dept. of Computer Science. Includes bibliographical references (leaves 231-234). Access restricted to members of the Tufts University community. Also available via the World Wide Web;