Skip navigation
Please use this identifier to cite or link to this item:
Title: Human-inspired Algorithms for Search: A Framework for Human-machine Multi-armed Bandit Problems
Authors: Reverdy, Paul Benjamin
Advisors: Leonard, Naomi E
Holmes, Philip J
Contributors: Mechanical and Aerospace Engineering Department
Keywords: Bayesian machine learning
Heuristic algorithms
Human-in-the-loop system
Multi-armed bandit
Subjects: Mechanical engineering
Electrical engineering
Issue Date: 2014
Publisher: Princeton, NJ : Princeton University
Abstract: Search is a ubiquitous human activity. It is a rational response to the uncertainty inherent in the tasks we seek to accomplish in our daily lives, from retrieving information to making important decisions. Engineers have developed numerous tools to perform automated search, but many tasks have too much uncertainty for these tools to perform adequately without human intervention. Engineering solutions to such tasks therefore consist of human-machine hybrid systems, where human supervisors interact with automated tools and make high-level decisions to guide them. Novel rigorous models of human decision making in such situations are required to facilitate the principled design of human-machine systems. In this thesis, we develop a rigorous model of human decision-making behavior in search tasks. We formally model search using the <italic>multi-armed bandit</italic> problem from the machine learning literature, which allows us to derive bounds on optimal decision-making performance. We focus on spatial search, for which we introduce the <italic>spatial multi-armed bandit</italic> problem. We develop several models of human decision-making behavior in this problem by extending heuristics from the neuroscience and machine learning literatures, and prove conditions under which one model (UCL) achieves optimal performance. We study human-subject data from a spatial multi-armed bandit problem and show that human performance in this problem falls into several categories. Some humans outperformed standard algorithms for multi-armed bandit problems, which we attribute to humans having good intuition for spatial search. We show that the UCL model can achieve performance that falls in the different categories by tuning the model parameters. The model parameters quantify a human's intuition and make it available to a human-machine system. We develop a parameter estimator for the UCL model by relating it to the Generalized Linear Model from the statistics literature. The UCL model together with the estimator represent a plant--observer pair for human decision making which can be used for system design. Finally, we consider a so-called &ldquo;satisficing&rdquo; objective as an alternative to the maximizing objective of the standard multi-armed bandit problem. We derive performance bounds in terms of this new objective and develop an algorithm that achieves optimal performance.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Mechanical and Aerospace Engineering

Files in This Item:
File Description SizeFormat 
Reverdy_princeton_0181D_11100.pdf1.17 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.