Bandido bom é bandido de IA
Em inteligência artificial (IA), o termo algoritmo de bandido não tem nada a ver com Brasília… hahaha! Na verdade, algoritmos de bandidos são ferramentas excelentes e com múltiplas utilidades. Portanto, hoje apresentaremos os algoritmos de bandido (bandit) e como eles podem ser empregados para a tomada de decisões usando técnicas de IA!
Algoritmos de bandido lidam com cenários de incerteza. Como a incerteza é um desafio que todos enfrentamos, os algoritmos de bandidos fornecem um modelo simples, mas muito útil. Portanto, os algoritmos de bandidos têm muitas aplicações práticas.
Afinal, o que são algoritmos de bandidos?
Os algoritmos bandit (ou algoritmos de bandidos) são uma classe de técnicas de machine learning. Elas projetadas especificamente para resolver problemas de tomada de decisão sob incerteza. Em essência, eles são algoritmos de aprendizado por reforço que visam maximizar a recompensa cumulativa explorando ou aproveitando de forma inteligente diferentes ações em um ambiente incerto.
Os algoritmos de bandido se originam do problema do bandido multi-armado (Multi-Armed Bandit, MAB). Este problema se refere a cenário hipotético em que um jogador deve escolher entre várias máquinas caça-níqueis (bandidos) com probabilidades de recompensa desconhecidas para maximizar os ganhos. O jogador (agente) precisa tomar decisões sequenciais enquanto equilibra o balanço entre explorar novas opções e aproveitar a melhor opção conhecida.
Por que esse nome?
O termo bandido foi inspirado em máquinas caça-níquéis de cassinos. Mas é aqui que divergimos do jogo para a ciência da computação e IA. Os algoritmos de bandidos lidam direta e indiretamente com tarefas de tomada de decisão sob incerteza. Consequentemente, eles são componentes vitais da IA!
Principais casos de uso
Grandes empresas de tecnologia usam algoritmos bandit para configurar interfaces da web e para tarefas que incluem recomendação de notícias, preços dinâmicos e posicionamento de anúncios. Um algoritmo de bandido também tem um papel no Monte Carlo Tree Search, um algoritmo que ficou famoso pelo sucesso do AlphaGo.
No mundo dos negócios, algoritmos de bandidos são muito relevantes porque podem ser usados para otimizar processos e estratégias que envolvem a tomada de decisões sequenciais, como preços, publicidade e alocação de recursos. Eles também ajudam a identificar a melhor abordagem em situações em que há incerteza ou informações limitadas, o que é comum em muitos cenários.
A ideia geral dos algoritmos de bandidos
Algoritmos de bandidos são um tipo de algoritmo de otimização estocástica usado para otimizar a tomada de decisões em situações em que há várias ações possíveis e recursos limitados. Portanto, eles são ideais para cenários onde várias ações podem ser selecionadas de um conjunto limitado, mas sem que o agente tenha conhecimento prévio sobre o caráter reforçador relativo (recompensa) de cada uma delas.
Nos problemas tradicionais de tomada de decisão, normalmente temos informações completas sobre as opções disponíveis e podemos escolher a melhor com base nisso. No entanto, em muitos cenários reais, como publicidade online e sistemas de recomendação, nem sempre esse é o caso. Para lidar com esses cenários, os algoritmos de bandido não dependem de conhecimento prévio sobre as opções disponíveis.
O objetivo principal dos algoritmos bandidos é equilibrar a exploração (tentar novas opções) e o aproveitamento (escolher uma boa opção conhecida). Eles são particularmente projetados para lidar com ambientes incertos, onde a qualidade das opções pode variar aleatoriamente.
A entrada para o algoritmo do bandido são informações sobre as diferentes ações que podem ser tomadas num certo contexto e a saída é uma estratégia para escolher a melhor ação em cada situação. Essa estratégia é baseada em uma combinação de dados anteriores e na exploração de novas opções para melhorar as decisões futuras.
Entre os principais tipos de algoritmos de bandidos estão o epsilon greedy e o UCB que tratamos recentemente.
Exemplo de algoritmo de bandido em código
Existem vários tipos de algoritmos de bandidos e maneiras de implementá-los. Para esse post, usaremos uma das implementações mais simples possíveis baseada no épsilon ganancioso (epsilon greedy). Embora simples, não subestime o poder deste algoritmo! Veja o código abaixo:
import numpy as np
import random
# BracoBernoulli: O braço de Bernoulli simula uma máquina caça-níqueis com probabilidade p de ganhar
class BracoBernoulli:
def __init__(self, p):
self.p = p
def draw(self):
return 1.0 if random.random() < self.p else 0.0
# agente com Epsilon-Greedy
class EpsilonGreedy:
def __init__(self, epsilon, n_bracos):
self.epsilon = epsilon
self.n_bracos = n_bracos
self.contagem = [0] * n_bracos # Número de vezes que cada braço foi jogado
self.valores = [0.0] * n_bracos # Recompensa média por braço
def seleciona_braco(self):
# Aproveitamento: escolhe o melhor braço até agora
if random.random() > self.epsilon:
return np.argmax(self.valores)
# Exploração: escolhe um braço aleatório
else:
return random.randrange(self.n_bracos)
def atualiza(self, indice_braco, recompensa):
self.contagem[indice_braco] += 1
n = self.contagem[indice_braco]
valor_antigo = self.valores[indice_braco]
# Atualiza a recompensa média de execução para o braço
valor_novo = ((n - 1)/float(n)) * valor_antigo + (1/float(n)) * recompensa
self.valores[indice_braco] = valor_novo
# Parâmetros de simulação
n_bracos = 5
n_passos = 1000
epsilon = 0.1
probabilidades = [0.1, 0.3, 0.5, 0.7, 0.9] # Probabilidade de pagamento de cada braço
bracos = [BracoBernoulli(p) for p in probabilidades]
agente = EpsilonGreedy(epsilon, n_bracos)
recompensas = []
for step in range(n_passos):
braco_selecionado = agente.seleciona_braco()
recompensa = bracos[braco_selecionado].draw()
agente.atualiza(braco_selecionado, recompensa)
recompensas.append(recompensa)
print("Recompensa média:", np.mean(recompensas))
print("Número de vezes que cada braço foi jogado:", agente.contagem)
print("Recompensa média por braço:", np.round(agente.valores, 3))
# exemplo de resultados:
# Recompensa média: 0.868
# Número de vezes que cada braço foi jogado: [29, 22, 16, 21, 912]
# Recompensa média por braço: [0.034 0.273 0.688 0.762 0.914]
A implementação acima é um exemplo direto de um algoritmo multi-armed bandit usando a estratégia epsilon-greedy (épsilon ganancioso). Ela simula cinco máquinas caça-níqueis (os braços do bandido) com probabilidades diferentes de recompensas. O objetivo do algoritmo é combinar exploração com aproveitamento para identificar o melhor braço.
Como já explicamos, o algoritmo épsilon ganancioso segue uma política de seleção de braço ganancioso. Ou seja, ele seleciona o braço de melhor desempenho em cada passo. No entanto, numa pequena porcentagem das vezes (definida por épsilon), ele sai da política e escolhe um braço aleatoriamente. O valor de épsilon determina a fração do tempo em que o algoritmo explora os braços disponíveis ou aproveita aqueles que tiveram o melhor desempenho historicamente no resto do tempo.
No código acima, usamos duas classes. A primeira (BracoBernoulli) simula as recompensas geradas por cada braços com distribuição de Bernoulli. A segunda define nosso epsilon-greedy explorando e aproveitando seu conhecimento para identificar o melhor braço do bandido. Na classe EpsilonGreedy, a primeira função (seleciona_braco) decide entre explorar e aproveitar. Ou seja, ela é o epsilon-greedy. A segunda função atualiza o valor das recompensas de cada braco conforme o bandido adquire conhecimento.
Conclusão
Os algoritmos de bandidos oferecem um conjunto poderoso de ferramentas para otimizar os processos de tomada de decisão em ambientes incertos. Ao dominar esses algoritmos, você poderá se beneficiar de técnicas relativamente simples, mas extremamente versáteis e com muitas aplicações comerciais!
