Humans possess the remarkable ability to navigate through large-scale spaces, such as a building or a city, with remarkable ease and proficiency. The current series of studies uses uses Partially Observable Markov Decision Processes (POMDP) to better understand how humans navigate through large-scale spaces when they have state uncertainty (i.e., lost in a familiar environment.). To investigate this question, we familiarized subjects with a novel, indoor, virtual reality environment. After familiarizing the subject with the environment, we measured subject’s efficiency for navigating from an unspecified location within the environment to a specific goal state. The environments were visually sparse and thus produced a great deal of perceptual aliasing (more than one state produced the same observation). We investigated whether human inefficiency was due to: 1) accessing their cognitive map; 2) Updating their belief vector; or 3) An inefficient decision process. The data clearly show that subjects are limited by an inefficient belief vector updating procedure. We discuss the ramifications of these finding on human way-finding behavior in addition to more general issues associated with decision making with uncertainty.