Algoritmo ideal para resolver problemas de bandidos n-armados?

13

Eu li sobre uma série de algoritmos para resolver problemas de bandidos n-armados como -greedy, softmax e UCB1, mas eu estou tendo alguns problemas triagem através de qual abordagem é melhor para minimizar o arrependimento.ϵ

Existe um algoritmo ideal conhecido para resolver o problema dos bandidos n-armados? Existe uma escolha de algoritmo que parece ter o melhor desempenho na prática?

JS01
fonte
Presumivelmente, não há uma solução óptima reconhecido, caso contrário, a página da Wikipedia diria isso e não seria uma experimental página Sourceforge
Henry
Isso não deveria estar em Teoria da Ciência da Computação SE?
1
@mbq desde aprendizado por reforço é um ramo da aprendizagem de máquina, eu não penso assim;)
Steffen
@ steffen Claro, o nome parecia "tcsy".
@mbq Eu não entendi. O que significa "tscy"?
steffen 13/05

Respostas:

9

Aqui estão dois documentos de pesquisa que encontrei recentemente. Ainda não os li, mas os resumos parecem promissores.

Joor`s Vermorel e Mehryar Mohri: Algoritmos de Bandidos Multi-Armados e Avaliação Empírica (2005)

Do resumo:

O problema do bandido com várias armas para um jogador é decidir qual braço de uma máquina de caça-níqueis puxar para maximizar sua recompensa total em uma série de tentativas. Muitos problemas de aprendizado e otimização do mundo real podem ser modelados dessa maneira. Várias estratégias ou algoritmos foram propostos como uma solução para esse problema nas últimas duas décadas, mas, até onde sabemos, não houve uma avaliação comum desses algoritmos.

Volodymyr Kuleshov e Doina Precup: Algoritmos para o problema dos bandidos armados (2000)

Em segundo lugar, o desempenho da maioria dos algoritmos varia drasticamente com os parâmetros do problema do bandido. Nosso estudo identifica para cada algoritmo as configurações em que ele apresenta um bom desempenho e as configurações em que ele apresenta um desempenho ruim.

Steffen
fonte