{'fraction_non_alphanumeric': 0.027470093043863535, 'fraction_numerical': 0.014621178555604785, 'mean_word_length': 5.451428571428571, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
RANDOMIZED ALLOCATION WITH NONPARAMETRIC ESTIMATION FOR A MULTI-ARMED BANDIT PROBLEM WITH COVARIATES

We study a multi-armed bandit problem in a setting where covariates are available. We take a nonparametric approach to estimate the functional relationship between the response (reward) and the covariates. The estimated relationships and appropriate randomization are used to select a good arm to play for a greater expected reward. Randomization helps balance the tendency to trust the currently most promising arm with further exploration of other arms. It is shown that, with some familiar nonparametric methods (e.g., histogram), the proposed strategy is strongly consistent in the sense that the accumulated reward is asymptotically equivalent to that based on the best arm (which depends on the covariates) almost surely. 1. Introduction. Multi-armed bandit problems have been extensively studied in probability and statistics in the past few decades and still receive considerable interest in these and related fields. Readers are referred to Berry and Fristedt (1985) and Gittins (1989) and the references cited therein for the history, many elegant results and applications in clinical trials, scheduling and other industrial problems. Some recent developments have been reported in, for example, Lai and Yakowitz (1995) who considered the situation in which observations are dependent, Berry, Chen, Zame, Heath and Shepp (1997) who considered infinitely many arms and Auer, Cesa-Bianchi, Freund and Schapire (1995) who considered worst-case performances. In classic bandit problems, each arm sequentially generates rewards based on a distribution with some unknown parameters, and one needs to sequentially select one arm to play for the maximum expected reward. In a majority of the earlier work, no auxiliary information beyond the observed rewards was considered when selecting an arm to play. Exceptions include Woodroofe (1979), Sarkar (1991) and Clayton (1989) who considered one-armed bandit problems with covariates. The first two papers studied Bayesian sequential allocation in non-Bernoulli bandit models with parametric frameworks and showed that the myopic rule is asymptotically optimal. The third studied Bernoulli bandit problems