Le problème de Warren Buffett

Voici une abstraction d'un problème d'apprentissage en ligne / bandit sur lequel j'ai travaillé l'été. Je n'ai jamais vu un problème comme celui-ci auparavant, et cela semble assez intéressant. Si vous connaissez un travail connexe, j'apprécierais les références.

Le problème Le réglage est celui des bandits multi-armés. Vous avez N bras. Chaque bras i a une distribution de probabilité inconnue mais fixe sur les récompenses qui peuvent être gagnées en le jouant. Pour le concret, supposons que chaque bras i paie une récompense de 10 $ avec une probabilité p [i] et une récompense de 0 $ avec une prob. 1-p [i] .

À chaque tour t, vous sélectionnez un ensemble S [t] d'armes à jouer. Pour chaque branche que vous sélectionnez, vous payez des frais de 1 $ à l'avance. Pour chaque bras sélectionné, vous collectez une récompense tirée de la distribution de probabilité de récompense (inconnue) de ce bras. Toutes les récompenses sont créditées sur votre compte bancaire et tous les frais sont déduits de ce compte. De plus, vous obtenez un crédit de 1 $ au début de chaque itération.

Le problème est de développer une politique pour sélectionner un sous-ensemble d'armes à jouer à chaque itération pour maximiser le profit (c'est-à-dire les récompenses moins les frais de jeu) sur un horizon suffisamment long, sous la contrainte qu'il doit maintenir un solde de compte non négatif à chaque fois.

Je n'ai pas précisé si les distributions de récompense par bras sont choisies parmi une distribution antérieure ou choisies par un adversaire. Les deux choix ont du sens. La formulation de l'adversaire est plus attrayante pour moi, mais probablement plus difficile à progresser. Ici, l'adversaire choisit un vecteur (D1, D2, .., DN) de distributions. Compte tenu des distributions, la politique d'équilibre budgétaire optimale consiste à jouer toutes les armes dont la récompense attendue est supérieure à 1 $. Soit P le bénéfice par étape de cette politique omnisciente optimale. Je veux que ma politique en ligne minimise les regrets (c'est-à-dire la perte de profit sur une fenêtre de temps T) par rapport à cette politique omnisciente.

J'imagine qu'il y a beaucoup d'approches possibles à ce problème (dont beaucoup, j'en suis sûr, vous avez considéré) - voici quelques idées / références.

• $N$
• Permettez à chaque ensemble de bras d'être un nouveau bras et exécutez un algorithme de type Exp3. Cela donne un $O(2^{N/2} T^{1/2})$
• Dans un prochain article du NIPS 2010, Saten Kale, Rob Schapire et moi considérons le cas où l'on joue à la fois une série d'armes. Dans notre travail, cependant, la taille de l'ardoise est fixe. Ce document examine également un problème similaire. Un autre travail similaire est apparu dans ALT 2010. Peut-être que certaines des idées sont transférées.
• Si vous le traitez comme un problème d'experts (chaque expert recommande un autre de $2^N$regrette maisO$O(N\sqrt{T})$$O(2^N T)$

MODIFIER ci-dessous:

$0$$1$$(n-1)/n$$T$$T$$(n-1)T/n$

$B$$0$$2B$$1/B$