Thesis
Finding hidden state
Washington State University
Master of Science (MS), Washington State University
2013
Handle:
https://hdl.handle.net/2376/103417
Abstract
We compare two approaches for learning environments without knowledge of the underlying state-graph of the environment: the Rule Template Tree (RTT) and Holmes and Isbell’s Looping Suffix Tree (LST). Using these approaches, we compare performance on a variety of environments ranging in complexity from a simple two-state environment called Flip to two 4x3 environments. We identify ambiguities in the pseudocode description of Holmes and Isbell’s LST algorithm and present two potential implementations—each distinctly unique. Because no reference code for the LST is available, our implementations are guided by intuition, interpretation, and in the case of our second implementation, guidance from the original authors. Despite this, it is not certain that our implementation is identical to the original. On our simplest environments, results using the RTT are characterized by a rapid decrease in the error rate followed by a gradual thinning out. The LST1 and LST2 learn those same environments quickly and achieve a perfect prediction rate. However, in our most difficult environment the LST1 loses its advantage over the RTT by failing to learn the environment perfectly and the LST2 quickly learns to predict the same result for every action.
Metrics
11 Record Views
Details
- Title
- Finding hidden state
- Creators
- Evan Dickinson
- Contributors
- Scott Andrew Wallace (Degree Supervisor)
- Awarding Institution
- Washington State University
- Academic Unit
- Electrical Engineering and Computer Science, School of
- Theses and Dissertations
- Master of Science (MS), Washington State University
- Publisher
- Washington State University; [Pullman, Washington] :
- Identifiers
- 99900525290201842
- Language
- English
- Resource Type
- Thesis