Accession Number:



A multi-armed bandit approach to superquantile selection

Personal Author(s):

Corporate Author:

Naval Postgraduate School Monterey United States

Report Date:



We study a resource allocation problem in an intelligence setting. The intelligence cycle is comprised of three phases collection,processing, and analysis. Enhanced efficiency within the first two stages directly impacts the number and types of important items thatare considered by analysts, increasing the frequency of the most important documents that are reviewed. The dilemma here is that ananalyst needs to quickly determine which sources to investigate, in order to provide meaningful analysis to a request for information with, a concrete deadline. Initially, the value of each source is unknown so, too, is the probabilistic nature of the value derived from each item. Generally, more sources and documents are available to be considered within a limited time frame than could be overanalyzed, compounding the complexity of this problem. Our goal is to efficiently find the source that produces the largest fraction of relevant items with respect to a request for information. By efficiently, we mean that the analyst balances exploration versus exploitation of the different sources judiciously. As such, the theoretical framework for this problem is that of a multi-armed bandit, a classic iterative decision learning process. This thesis presents a new approach to identifying the optimal arms of a multi-arm bandit with the largest or smallest quantile or superquantile risk, under a loss constraint. This problem is not only important in intelligence applications, but in marketing and finance. We extend the existing theoretical framework of dealing with quantiles to a novel situation with estimators of conditional expectations over an unknown quantile. Two sequential elimination algorithms are developed that select the most important source for a given constraint level, sampling from the arms with the largest conditional expectation over a quantile.

Descriptive Note:

Technical Report



Subject Categories:

Communities Of Interest:

Distribution Statement:

Approved For Public Release;

File Size: