Bandido multi-armado para distribuição geral de recompensas

11

Estou trabalhando em um problema de bandidos com várias armas em que não temos informações sobre a distribuição de recompensas.

Eu encontrei muitos artigos que garantem limites de arrependimento para uma distribuição com limite conhecido e para distribuições gerais com suporte em [0,1].

Eu gostaria de descobrir se existe uma maneira de ter um bom desempenho em um ambiente em que a distribuição de recompensas não tem garantias sobre seu suporte. Estou tentando calcular um limite de tolerância não paramétrico e usando esse número para dimensionar a distribuição de recompensa, para que eu possa usar o algoritmo 2 especificado neste artigo ( http://jmlr.org/proceedings/papers/v23/agrawal12/agrawal12.pdf ) Alguém acha que essa abordagem funcionará?

Se não, alguém pode me apontar para o lugar certo?

Muitíssimo obrigado!

references multiarmed-bandit convidado
fonte

Respostas:

6

A pesquisa sobre algoritmos MAB está intimamente ligada às garantias teóricas de desempenho. De fato, o ressurgimento do interesse por esses algoritmos (lembre-se de que a amostragem de Thompson foi proposta nos anos 30) só aconteceu realmente desde o artigo de Auer, em 2002, que comprova lamentar os limites para os vários UCB e -greedy algoritmos. Como tal, há pouco interesse em problemas em que a distribuição de recompensas não tem limites conhecidos, uma vez que quase nada pode ser dito teoricamente.O(registro⁡(T))ϵ

Até o algoritmo simples de amostragem Thompson que você menciona exige recompensas distribuídas por Bernoulli, e até isso levou 80 anos para provar um arrependimento logarítmico!

Na prática, no entanto, nos casos em que você não conhece a distribuição de recompensa por certo, você pode simplesmente escalá-la para dividindo pelo grande número , e se observar uma recompensa acima de apenas o dobro do valor, . Porém, não há garantias de arrependimento usando essa abordagem, mas ela geralmente funciona muito bem.[0 0,1]SSS: =2S

Além disso, o algoritmo de amostragem Thompson que você mencionou precisa de testes de Bernoulli, para que você não possa usar recompensas contínuas arbitrárias. Você pode ajustar uma distribuição posterior gaussiana em vez de uma versão beta, mas isso é um pouco sensível à sua escolha anterior, portanto, você pode configurá-la para ser muito plana. Se você não quer provar nada sobre sua implementação, isso provavelmente funcionará muito bem.

fairidox
fonte
1
Muito obrigado pela resposta! Eu realmente gostei disso! Eu tinha uma pergunta, no entanto. Eu acho que o algoritmo 2 no papel (na parte superior da página 39.4) que mencionei não requer nada sobre a distribuição de recompensas, mas o fato de seu suporte estar em [0,1]. Talvez você estivesse olhando o algoritmo 1?
guest
Sim, legal, um truque bastante interessante para converter valores reais em amostras de Bernoulli, obrigado por apontar que os detalhes me escaparam. De qualquer forma, como você diz, ainda precisa de variáveis ​​limitadas, você pode fazer isso com o truque duplo barato que mencionei e usar esta versão da amostragem Thompson. Mas é melhor formular um método que use um posterior gaussiano.
fairidox
Analisarei mais o método posterior gaussiano, mas o que você quer dizer com "plano" em termos de gaussiano? Eu presumo que corresponderia a algo como um Beta (1,1) (uniforme) antes, correto?
guest
certo, mas você não pode obviamente ter um uniforme antes de um domínio ilimitado. Portanto, se você tem um modelo posterior gaussiano, provavelmente terá um gaussiano anterior, de modo que geralmente deseja tê-lo o mais "plano" ou pouco informativo possível. Isso geralmente significa tornar a variação o maior possível. Não sou especialista, mas há todo um campo de estudo sobre como construir antecedentes não informativos e potencialmente impróprios que você pode querer analisar. Além disso, se você tiver recompensas estritamente positivas, poderá considerar um modelo diferente.
fairidox