Introdução aos Problemas Multi-Armed Bandit

Muitas aplicações práticas exigem problemas de tomada de decisão sequencial onde um agente deve selecionar a melhor ação entre várias alternativas. Exemplos de tais aplicações incluem ensaios clínicos, sistemas de recomendação e detecção de anomalias. Em alguns casos, informações secundárias ou contexto estão associadas a cada ação (por exemplo, perfil do usuário), e o feedback, ou recompensa, é limitado à opção escolhida. Por exemplo, em ensaios clínicos, o contexto é o prontuário médico do paciente (por exemplo, estado de saúde, histórico familiar, etc.), as ações correspondem às opções de tratamento comparadas, e a recompensa representa o resultado do tratamento proposto (por exemplo, sucesso ou fracasso). Um aspecto importante que afeta o sucesso de longo prazo em tais contextos é encontrar um bom equilíbrio entre exploração (por exemplo, experimentar um novo tratamento) e exploração (escolher o tratamento mais conhecido até o momento).

Este trade-off inerente entre exploração e exploração existe em muitos problemas de tomada de decisão sequencial e é tradicionalmente formulado como o problema do bandit, que se apresenta da seguinte forma: Dadas K ações possíveis, ou "braços", cada um associado a uma distribuição de probabilidade de recompensa fixa mas desconhecida, em cada iteração, um agente seleciona um braço para jogar e recebe uma recompensa, amostrada da distribuição de probabilidade do respectivo braço independentemente de ações anteriores. A tarefa do agente é aprender a escolher suas ações para que as recompensas cumulativas ao longo do tempo sejam maximizadas.

Formulação do Problema Multi-Armed Bandit

O problema clássico do multi-armed bandit (MAB) é definido por K braços, cada um com uma distribuição de recompensa desconhecida. A cada passo de tempo t, o agente escolhe um braço a_t ∈ {1, 2, ..., K} e recebe uma recompensa r_t amostrada da distribuição do braço escolhido. O objetivo é maximizar a recompensa cumulativa ao longo de T rodadas, ou equivalentemente, minimizar o arrependimento, que é a diferença entre a recompensa cumulativa do braço ótimo e a recompensa cumulativa dos braços escolhidos.

Note que o agente deve experimentar diferentes braços para aprender suas recompensas (ou seja, explorar o ganho), e também usar essa informação aprendida para receber o melhor ganho (explorar os ganhos aprendidos). Há um trade-off natural entre exploração e exploração. Por exemplo, experimentar cada braço exatamente uma vez, depois jogar o melhor entre eles. Essa abordagem frequentemente tende a levar a soluções muito subótimas quando as recompensas dos braços são incertas.

Diferentes soluções foram propostas para este problema, baseadas na formulação estocástica e na formulação bayesiana; no entanto, essas abordagens não levavam em conta o contexto ou informações secundárias disponíveis para o agente.

Multi-Armed Bandits Contextuais

Uma versão particularmente útil do MAB é o multi-armed bandit contextual (CMAB), ou simplesmente bandit contextual, onde em cada rodada, antes de escolher um braço, o agente observa um vetor de contexto x_t que pode influenciar a distribuição de recompensa dos braços. O contexto pode incluir características do usuário, variáveis ambientais ou qualquer informação lateral relevante. O objetivo permanece maximizar a recompensa cumulativa, mas agora a política pode depender do contexto observado.

Bandits contextuais ganharam atenção significativa devido à sua aplicabilidade em sistemas de recomendação personalizados, onde o contexto normalmente representa características do usuário, e os braços correspondem a diferentes itens ou conteúdos para recomendar. A recompensa pode ser um clique, uma compra ou qualquer outra forma de engajamento.

Vários algoritmos foram desenvolvidos para bandits contextuais, incluindo o LinUCB, que assume uma relação linear entre o contexto e a recompensa esperada de cada braço, e a amostragem de Thompson com modelos lineares. Esses algoritmos mostraram forte desempenho empírico em várias aplicações.

Aplicações no Mundo Real dos Multi-Armed Bandits

Ensaios Clínicos

Em ensaios clínicos, a estrutura multi-armed bandit fornece uma abordagem ética para a alocação de tratamento. O contexto inclui prontuários médicos do paciente, informações demográficas e marcadores genéticos. Os braços representam diferentes opções de tratamento, e a recompensa indica o sucesso ou fracasso do tratamento. Algoritmos bandit podem alocar dinamicamente mais pacientes para tratamentos promissores enquanto ainda exploram alternativas, potencialmente levando a melhores resultados para os pacientes e ensaios mais eficientes.

Sistemas de Recomendação

Sistemas de recomendação representam uma das aplicações mais bem-sucedidas dos algoritmos bandit. Grandes plataformas usam bandits contextuais para personalizar conteúdo, produto e recomendações de anúncios. O componente de exploração permite que o sistema descubra as preferências do usuário para novos itens, enquanto a exploração aproveita as preferências conhecidas para maximizar o engajamento do usuário. Essa abordagem aborda o problema do início a frio para novos itens e se adapta às mudanças de interesses do usuário ao longo do tempo.

Detecção de Anomalias

Em sistemas de detecção de anomalias, algoritmos bandit podem otimizar a alocação de recursos de inspeção limitados. O contexto pode incluir métricas do sistema, padrões de tráfego de rede ou características de comportamento do usuário. Os braços representam diferentes estratégias de inspeção ou modelos de detecção de anomalias, e a recompensa reflete se uma anomalia real foi identificada. Essa abordagem permite a alocação adaptativa de recursos para os métodos de detecção mais promissores.

Outras Aplicações

Aplicações adicionais incluem otimização de portfólio em finanças, teste A/B em desenvolvimento web, alocação de recursos em computação em nuvem e tecnologia educacional para aprendizagem adaptativa. A flexibilidade da estrutura bandit a torna aplicável a qualquer cenário que exija tomada de decisão sequencial sob incerteza com feedback limitado.

Algoritmos e Abordagens Bandit

Bandits Estocásticos

Bandits estocásticos assumem que as recompensas de cada braço são extraídas independentemente de uma distribuição fixa. Algoritmos-chave incluem ε-guloso, que seleciona o melhor braço com probabilidade 1-ε e um braço aleatório com probabilidade ε; algoritmos Upper Confidence Bound (UCB), que selecionam braços com base em estimativas otimistas de seu potencial; e amostragem de Thompson, que usa distribuições posteriores bayesianas para equilibrar exploração e exploração.

Bandits Adversariais

Bandits adversariais não fazem suposições estatísticas sobre a geração de recompensas, tratando-as como sequências arbitrárias potencialmente escolhidas por um adversário. O algoritmo Exp3 e suas variantes são projetados para esse cenário, usando esquemas de ponderação exponencial para alcançar arrependimento sublinear contra qualquer sequência de recompensas.

Bandits Bayesianos

Bandits bayesianos mantêm uma distribuição de probabilidade sobre as possíveis distribuições de recompensa dos braços. A amostragem de Thompson é a abordagem bayesiana mais proeminente, que amostra da distribuição posterior dos parâmetros de recompensa de cada braço e seleciona o braço com o maior valor amostrado. Isso equilibra elegantemente a exploração e a exploração de acordo com a incerteza atual.

Algoritmos de Bandit Contextual

Algoritmos de bandit contextual estendem essas abordagens para incorporar informações de contexto. O LinUCB assume funções de recompensa lineares e mantém elipsoides de confiança em torno das estimativas de parâmetros. Bandits neurais usam redes neurais profundas para modelar relações complexas entre contexto e recompensas. Esses algoritmas demonstraram forte desempenho em aplicações de larga escala com contextos de alta dimensão.

Tendências Atuais e Perspectivas Futuras

O campo dos multi-armed bandits está passando por um renascimento, com novos parâmetros de problemas e algoritmos motivados por diversas aplicações práticas sendo introduzidos, além do problema clássico do bandit. Tendências atuais importantes incluem a integração de bandits com aprendizado profundo, levando a algoritmos de bandit contextual mais poderosos capazes de lidar com contextos complexos e de alta dimensão.

Outra tendência significativa é o desenvolvimento de algoritmos bandit para ambientes não estacionários, onde as distribuições de recompensa mudam ao longo do tempo. Isso é crucial para muitas aplicações do mundo real onde as preferências do usuário, condições de mercado ou comportamentos do sistema evoluem. Algoritmos como UCB de janela deslizante e técnicas de desconto abordam esse desafio.

Há um interesse crescente em bandits colaborativos e distribuídos, onde múltiplos agentes aprendem simultaneamente e podem compartilhar informações. Isso é relevante para configurações de aprendizagem federada onde a privacidade de dados é importante. Além disso, bandits com restrições e considerações de segurança estão ganhando atenção, particularmente para aplicações em saúde e finanças onde certas ações devem ser evitadas.

Direções futuras de pesquisa incluem desenvolver algoritmos mais eficientes para espaços de ação muito grandes, incorporar informações estruturais sobre o espaço de ação e melhorar a compreensão teórica dos algoritmos de bandit profundos. A interseção de bandits com inferência causal representa outra direção promissora, permitindo uma melhor tomada de decisão quando as intervenções podem ter efeitos de longo prazo.

Conclusão

Multi-armed bandits fornecem uma estrutura poderosa para a tomada de decisão sequencial sob incerteza com feedback limitado. O trade-off fundamental de exploração-exploração aparece em inúmeras aplicações práticas, desde ensaios clínicos até sistemas de recomendação. A extensão do bandit contextual provou ser particularmente valiosa para sistemas personalizados que se adaptam a características individuais.

Este levantamento forneceu uma visão geral abrangente dos principais desenvolvimentos em multi-armed bandits, com foco em aplicações do mundo real. Examinamos a formulação do problema, os principais algoritmos e os diversos domínios de aplicação. O campo continua a evoluir rapidamente, com novos algoritmos abordando desafios como não estacionariedade, grandes espaços de ação e restrições de segurança.

À medida que os algoritmos bandit se tornam mais sofisticados e são aplicados a problemas cada vez mais complexos, eles continuarão a desempenhar um papel crucial na otimização da tomada de decisão em vários domínios. A pesquisa contínua nesta área promete produzir algoritmos ainda mais eficazes e aplicações mais amplas no futuro.