Statistical Methods in Finance 2019

---

Abstract

Partition identification using multi-armed bandits for general distribution

by Sandeep Juneja, TIFR, Mumbai

Given a vector of unknown probability distributions, or arms, each of which can be sampled independently, we consider the problem of identifying the partition to which this vector belongs from a finitely partitioned universe of such vector of distributions. We primarily consider partitions where the vector of means of arms lie either in a given set or its complement in a Euclidean space. The sets considered correspond to half spaces or where either the set or its complement is a polytope, or more generally, a convex set. In these settings, exploiting the problem geometry, we characterize the lower bounds on mean number of samples from each arm that any δ-correct algorithm (algorithm that restricts wrong identification probability to a pre-specified δ) must satisfy. Further, we propose δ-correct algorithms that for small δ can match these bounds. Traditionally multi-armed bandit literature focusses on restrictive distribution families such as Bernoulli distributions, sub-Gaussian distributions or those belonging to the single parameter exponential family. We discuss how our analysis extends to general distributions where an explicit upper bound on 1+ε moment is available. This framework lends itself to many applications including in portfolio selection and portfolio risk measurement in finance.

---