Human-inspired Algorithms for Search: A Framework for Human-machine Multi-armed Bandit Problems

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.