Structured pure exploration bandit problems and extensions

Abstract

The subject of this thesis is a study of several multi armed bandit problems (MAB), with a focus on structured pure exploration bandit problems. We begin with an extensive overview of the MAB literature, with specific weight given to classical techniques and results, for pure exploration bandit problems. Over the course of our analysis we will explore several novel extensions to the MAB. Our first contribution will be to classify the minimax rate for the Thresholding Bandit Problem (TBP). We will then go on to consider the TBP under several shape constraints and again classify the minimax rate in each of these cases. Our second contribution is to study the shape constrained TBP in a problem dependent setting. For the TBP, under both a monotone and concave constraint, we provide problem dependent upper and lower bounds, matching up to log terms. Our third contribution is to consider a potentially infinite armed formulation of the MAB, where a proportion of the arms are optimal. In this setting we provide problem dependent upper and lower bounds, matching up to log terms, for both cumulative regret and best arm identification.

Das Gegenstand dieser Dissertation ist die Untersuchung von mehreren Multi Armed Bandit-Probleme (MAB) mit einem Fokus auf Structured Pure Exploration Bandit- Probleme. Wir fangen mit einer umfangreichen Übersicht der MAB Literatur an, wobei wir in die klassischen Techniken und Ergebnisse für Pure Exploration Bandit-Probleme tiefer eingehen. Im Laufe unserer Analyse werden wir mehrere originelle Erweiterungen zur MAB untersuchen. Unser erstes Beitrag wird das Klassifizieren der Minimax- Raten für das Thresholding Bandit Problem (TBP) sein. Anschließend werden wir das TBP unter einigen Formbeschränkungen betrachten und die Minimax-Rate in jedem dieser Fälle klassifizieren. Unser zweites Beitrag wird die Untersuchung des formbeschränkten TBPs in einer problemabhängigen Umgebung sein. Für das TBP, unter sowohl einem monotonen, als auch konkaven Zwang, bieten wir problemabhängige Ober- und Untergrenzen an, die bis auf die Log-Terme übereinstimmt. Unser dritter Beitrag wird die Betrachtung einer potentiellen Infinite Armed Formulierung des MAB sein, wobei ein Anteil der Arme optimal sind. In dieser Umgebung schaffen wir problemabhängige Ober- und Untergrenzen, die für beide Cumulative Regret und Best Arm Identification bis auf die Log-Terme übereinstimmt. Das letzte Kapitel von dieser Dissertation widmet sich einer laufenden Arbeit, der Cluster-Identifikation mit Bandit Rückmeldung.