O problema do bandido multi-armado, às vezes chamado de problema do bandido K- ou N-armado, é um conceito fundamental na teoria das probabilidades e no aprendizado de máquina. Ele recebe esse nome em referência a um jogador que enfrenta uma fileira de caça-níqueis, frequentemente chamados de "bandidos de um braço", que deve decidir quais máquinas jogar, quantas vezes jogar em cada uma e em que ordem, além de decidir se continua com uma máquina atual ou tenta uma diferente. De modo mais geral, descreve um tomador de decisão que seleciona iterativamente uma entre várias escolhas fixas, conhecidas como braços ou ações, quando as propriedades de cada escolha são apenas parcialmente conhecidas no momento da alocação e podem se tornar mais bem compreendidas ao longo do tempo. Um aspecto fundamental é que escolher um braço não afeta as propriedades desse braço nem de qualquer outro, distinguindo-o de problemas mais amplos de aprendizado por reforço, nos quais as ações podem alterar estados futuros e distribuições de recompensa.
O problema exemplifica o dilema de exploração versus exploração de ganhos, um dilema central no aprendizado de máquina. O jogador deve equilibrar a "exploração de ganhos" da máquina com o maior retorno esperado conhecido contra a "exploração" para reunir mais informações sobre outras máquinas. O objetivo é maximizar a recompensa total obtida por meio de uma sequência de acionamentos de alavanca. Esse dilema aparece em muitas aplicações práticas, incluindo ensaios clínicos, roteamento adaptativo de redes, projeto de carteiras financeiras e alocação de recursos em organizações de pesquisa.
O problema do bandido multi-armado foi originalmente considerado por cientistas aliados durante a Segunda Guerra Mundial, mas se mostrou tão intratável que, segundo Peter Whittle, foi proposto que fosse lançado sobre a Alemanha para que os cientistas alemães também perdessem tempo com ele. A versão agora comumente analisada foi formulada por Herbert Robbins em 1952, que construiu estratégias convergentes de seleção populacional em seu artigo "Some Aspects of the Sequential Design of Experiments". Um resultado teórico notável é o índice de Gittins, publicado pela primeira vez por John C. Gittins, que fornece uma política ótima para maximizar a recompensa esperada descontada.
Modelo Formal
O bandido multi-armado pode ser modelado como um conjunto de distribuições reais \(B = \{R_1, \dots, R_K\}\), em que cada distribuição está associada às recompensas entregues por uma das \(K\) alavancas, com \(K \in \mathbb{N}^+\). Sejam \(\mu_1, \dots, \mu_K\) os valores médios dessas distribuições de recompensa. O jogador joga iterativamente uma alavanca por rodada e observa a recompensa associada, com o objetivo de maximizar a soma das recompensas coletadas ao longo de um horizonte \(H\), que é o número de rodadas restantes. O problema do bandido é formalmente equivalente a um processo de decisão de Markov de um único estado.
O arrependimento, denotado por \(\rho\), mede a diferença esperada entre a soma de recompensas de uma estratégia ótima e as recompensas coletadas após \(T\) rodadas. Ele é definido como \(\rho = T\mu^ - \sum_{t=1}^T \hat{r}_t\), em que \(\mu^\) é a média máxima de recompensa e \(\hat{r}_t\) é a recompensa obtida na rodada \(t\). Minimizar o arrependimento é um objetivo primário em algoritmos de bandido.
Exploração versus Exploração de Ganhos
O dilema de exploração versus exploração de ganhos é o desafio central em problemas de bandido multi-armado. A exploração de ganhos envolve escolher o braço com a maior recompensa estimada com base no conhecimento atual, enquanto a exploração envolve tentar outros braços para reduzir a incerteza sobre suas recompensas potenciais. Estratégias eficazes devem equilibrar esses objetivos concorrentes para maximizar a recompensa cumulativa de longo prazo. Esse dilema não é exclusivo dos bandidos; ele aparece em todo o aprendizado de máquina, incluindo em sistemas de aprendizado por reforço e inteligência artificial que devem decidir entre usar estratégias conhecidas e descobrir novas.
Na prática, os bandidos multi-armados têm sido usados para modelar problemas como a gestão de projetos de pesquisa em grandes organizações, como uma fundação de ciências ou uma empresa farmacêutica. Por exemplo, um gerente de pesquisa deve decidir quais projetos financiar, equilibrando a exploração de ganhos de projetos com potencial conhecido contra a exploração de novas ideias incertas. O modelo também foi aplicado ao roteamento adaptativo para minimizar atrasos de rede e ao projeto de carteiras financeiras, em que a escolha de ativos envolve dilemas semelhantes.
Algoritmos e Estratégias
Vários algoritmos foram desenvolvidos para abordar o problema do bandido multi-armado. Um dos primeiros é a estratégia épsilon-gulosa, em que o agente escolhe um braço aleatório com probabilidade \(\epsilon\) (exploração) e, caso contrário, seleciona o braço com a maior recompensa estimada (exploração de ganhos). Outra abordagem popular é o algoritmo de limite superior de confiança (UCB), que seleciona braços com base tanto em sua recompensa média quanto na incerteza dessa estimativa, equilibrando efetivamente exploração e exploração de ganhos de maneira fundamentada. A amostragem de Thompson, um método bayesiano, mantém uma distribuição a posteriori para a recompensa de cada braço e amostra dessas distribuições para decidir qual braço jogar.
O índice de Gittins, introduzido por John C. Gittins, fornece uma política ótima para maximizar a recompensa esperada descontada em certos cenários de bandido. Ele atribui um índice a cada braço com base em seu estado, e a estratégia ótima é jogar o braço com o maior índice. Esse resultado tem sido influente em pesquisa operacional e economia.
Aplicações e Evidências Empíricas
O arcabouço do bandido multi-armado tem inúmeras aplicações práticas. Em ensaios clínicos, pode ser usado para alocar pacientes a diferentes tratamentos, minimizando perdas de pacientes enquanto reúne informações sobre a eficácia do tratamento. No roteamento adaptativo, ajuda a minimizar atrasos ao selecionar dinamicamente caminhos de rede. No projeto de carteiras financeiras, orienta a alocação de recursos entre opções de investimento concorrentes.
Um estudo de 2024 que usou registros de jogos de cassino tratou as escolhas repetidas dos jogadores entre máquinas caça-níqueis com probabilidades desconhecidas como um problema de bandido multi-armado em grande escala. O estudo descobriu que jogadores mais experientes tendiam a selecionar máquinas com melhores probabilidades e mostravam maior consistência em suas escolhas de máquinas ao longo do tempo, padrões consistentes com aprendizado e maior exploração de ganhos de opções mais bem conhecidas. Essa evidência empírica apoia a relevância dos modelos de bandido para a tomada de decisão no mundo real.
O modelo também tem sido usado para controlar a alocação dinâmica de recursos a diferentes projetos, respondendo à pergunta de em qual projeto trabalhar dada a incerteza sobre dificuldade e retorno. Essa aplicação é particularmente relevante em pesquisa e desenvolvimento, em que organizações devem decidir como alocar recursos limitados entre iniciativas concorrentes.
Relação com o Aprendizado por Reforço
O problema do bandido multi-armado é um problema clássico de aprendizado por reforço que exemplifica o dilema de exploração versus exploração de ganhos. No entanto, é mais simples do que o aprendizado por reforço geral porque as ações selecionadas não afetam a distribuição de recompensa dos braços. Em contraste, no aprendizado por reforço geral, as ações podem mudar o estado do ambiente, influenciando recompensas futuras. Essa distinção torna os bandidos um ponto de partida tratável para estudar dilemas de exploração versus exploração de ganhos, e muitos algoritmos desenvolvidos para bandidos foram estendidos para cenários mais complexos de aprendizado por reforço.
O problema também se enquadra na ampla categoria de agendamento estocástico, em que decisões devem ser tomadas sob incerteza sobre os resultados de diferentes ações. Essa conexão destaca a ampla aplicabilidade dos modelos de bandido em vários domínios, desde pesquisa operacional até inteligência artificial.
Em resumo, o problema do bandido multi-armado é um modelo fundamental para a tomada de decisão sob incerteza, com raízes teóricas profundas e ampla relevância prática. Seu estudo produziu algoritmos elegantes e insights que continuam a informar a pesquisa em aprendizado de máquina e além.