O Problema de Warren Buffett

Aqui está uma abstração de um problema de aprendizado / bandido on-line em que estive trabalhando no verão. Eu nunca vi um problema como esse antes e parece bastante interessante. Se você conhece algum trabalho relacionado, eu gostaria de receber referências.

O problema A configuração é a de bandidos com várias armas. Você tem N braços. Cada braço i tem uma distribuição de probabilidade desconhecida, mas fixa, sobre recompensas que podem ser obtidas ao jogá-lo. Por concretude, vamos supor que cada braço i pague recompensa $ 10 com probabilidade p [i] e recompensa $ 0 com prob. 1-p [i] .

Em cada rodada t você seleciona um conjunto de armas [t] para jogar. Para cada braço selecionado, você paga uma taxa de US $ 1 adiantado. Para cada braço selecionado, você recebe uma recompensa extraída da distribuição de probabilidade de recompensa (desconhecida) desse braço. Todas as recompensas são creditadas na sua conta bancária e todas as taxas são deduzidas dessa conta. Além disso, você recebe um crédito de US $ 1 no início de cada iteração.

O problema é desenvolver uma política para selecionar um subconjunto de armas para jogar em cada iteração, a fim de maximizar o lucro (ou seja, recompensas menos taxas por jogar) em um horizonte longo o suficiente, sujeito à restrição de que ele deve manter um saldo não negativo da conta em todas as vezes.

Não especifiquei se as distribuições de recompensa por braço são escolhidas de uma distribuição anterior ou escolhidas por um adversário. Ambas as escolhas fazem sentido. A formulação do adversário é mais atraente para mim, mas provavelmente mais difícil de avançar. Aqui, o adversário escolhe um vetor (D1, D2, .., DN) de distribuições. Dadas as distribuições, a política ideal de orçamento equilibrado é jogar todos os braços cuja recompensa esperada seja superior a US $ 1. Seja P o lucro por etapa dessa política onisciente ideal. Quero que minha política on-line minimize o arrependimento (ou seja, perda de lucro ao longo de uma janela de tempo T) com essa política onisciente.

Eu imagino que existem muitas abordagens possíveis para esse problema (muitas das quais tenho certeza de que você considerou) - aqui estão algumas idéias / referências.

• Você poderia jogar isso como $N$ jogos paralelos independentes de bandidos de braço único, decidindo puxar ou não puxar cada braço de forma independente. Isso deve funcionar especialmente bem se as recompensas forem distribuídas independentemente.
• Permita que cada conjunto de armas seja um novo braço e execute um algoritmo do tipo Exp3. Isso fornece um $O(2^{N/2} T^{1/2})$
• Em um próximo artigo do NIPS 2010, Saten Kale, Rob Schapire e eu consideramos o caso em que se joga de armas de uma só vez. Em nosso trabalho, no entanto, o tamanho da ardósia é fixo. Este artigo também considera um problema semelhante. Outro trabalho semelhante apareceu no ALT 2010. Talvez algumas das idéias sejam transferidas.
• $2^N$$O(N\sqrt{T})$$O(2^N T)$

EDITAR abaixo:

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

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