Visual Search with a Trembling Hand: An Analysis of Odd Arm Identification in Restless Multi-armed Bandits
# 22
Abstract
This work is motivated by a visual search experiment in which a human subject is shown a number of drifting-dots images. The direction of drift in one of these images (the odd image) is different from the common direction of drift in rest of the images. The goal of the human subject is to identify the location of the odd drifting-dots image in the shortest possible time while keeping his probability of decision error small. Our interest is in understanding the relation between (a) the amount of time taken by the human subject to identify the odd image, and (b) the “closeness” of the odd and the non-odd images used in the experiment. It is often the case that the human subjects participating in such visual search experiments tend to sample image locations uniformly at random in an attempt to complete the given task as soon as possible. In this work, we model the above visual search experiment as a problem of odd arm identification in a multi-armed bandit in which (a) each arm yields Markov observations, and (b) the arms are restless. Further, we model the tendency of human subjects to sample image locations randomly as a “trembling hand” for the human subject, and come up with a metric that captures the notion of “closeness” between the odd and the non-odd images. Our results generalize all the previously known results for odd arm identification in multi-armed bandits.
Karthik P. N
Karthik is a PhD student in the Wireless Information Systems Lab, Department of ECE, working under the supervision of Prof. Rajesh Sundaresan. Prior to joining for PhD, he served as a project assistant in the Signal Processing for Communications Lab of the Dept of ECE, where he worked with Prof. Chandra R. Murthy. Karthik holds a Bachelor’s degree in Electronics and Communications from RV College of Engineering, Bangalore, where he graduated from in 2014.