Bandidos multi-armados: a melhor solução de aprendizado por reforço para sua tarefa

Multi-Armed Bandits (MABs) formam uma pedra angular no mundo do Reinforcement Learning, oferecendo um poderoso mecanismo para negociar cenários que exigem um equilíbrio ideal entre exploração e exploração. A exploração refere-se a experimentar novas opções, enquanto a exploração significa aderir à melhor opção atual. Em tais circunstâncias, MABs muitas vezes provam ser uma escolha estelar devido aos seus mecanismos de aprendizagem inteligentes.

Primeiro, vamos desvendar o conceito por trás dos MABs. Imagine um jogador cercado por uma série de máquinas caça-níqueis, cada uma conhecida como "bandido de um braço só". As decisões críticas a serem tomadas aqui envolvem determinar quais máquinas jogar, a ordem do jogo e a frequência do jogo. O problema é que cada máquina oferece uma recompensa diferente e incerta. O objetivo final é acumular a maior recompensa cumulativa em uma sequência de jogadas.

O que é um bandido multi-armado?

O nome "bandido de vários braços" vem de um experimento mental envolvendo um jogador em uma fileira de máquinas caça-níqueis (geralmente conhecidas como "bandidos de um braço só"). O apostador precisa decidir em quais máquinas jogar, quantas vezes jogar em cada máquina e em que ordem, com o objetivo de maximizar sua recompensa total.

Em uma definição mais formal, um problema MAB é uma tupla (A, R)

O objetivo no problema MAB é encontrar uma política π (um mapeamento de dados históricos para ações) que maximize a recompensa total esperada Q em um determinado número de rodadas.

O principal dilema no MAB é o trade-off entre "exploração" e "exploração":

1. A exploração envolve tentar armas diferentes para aprender mais sobre a recompensa que elas podem render. Isso pode envolver puxar braços abaixo do ideal, mas ajuda a coletar informações sobre o sistema.
2. A exploração envolve puxar o braço que o agente atualmente acredita ter a maior recompensa esperada, com base nas informações coletadas até o momento.

Equilibrar exploração e exploração é um desafio central no aprendizado por reforço e nos problemas MAB.

Para resolver esse problema, uma série de algoritmos foi desenvolvida, incluindo as estratégias Epsilon-Greedy, Upper Confidence Bound (UCB) e Thompson Sampling.

A revisão detalhada do Contextual Bandits como uma extensão do MAB será abordada nos próximos artigos.

O Epsilon(ε)-Gancioso

A estratégia Epsilon(ε)-Greedy segue um princípio direto. Na maioria das vezes, quantificado como (1 - ε), ele opta pela ação que rende a maior recompensa estimada, explorando assim a opção mais conhecida. Porém, no restante do tempo, quantificado como ε, ele escolhe uma ação aleatória, explorando assim novas possibilidades. A engenhosidade dessa estratégia reside em sua simplicidade e eficácia, apesar da ressalva de que pode selecionar ações menos recompensadoras com a mesma probabilidade das mais recompensadoras durante sua fase de exploração e o valor de ε determina o equilíbrio entre exploração e exploração.

Matematicamente pode ser definido como:

Isso pode ser definido pelo seguinte pseudocódigo:

 Initialize Q(a) for all a Repeat: Generate a random number p between 0 and 1 If p < epsilon: Select a random action a Else: Select action a with the highest Q(a) Execute action a and observe reward r Update Q(a) = Q(a) + alpha * (r - Q(a))

A implementação Pythonic da estratégia Epsilon-Greedy é bastante direta:

 import numpy as np class EpsilonGreedy: def __init__(self, epsilon, counts, values): self.epsilon = epsilon self.counts = counts self.values = values def select_arm(self): if np.random.random() < self.epsilon: return np.random.choice(len(self.values)) else: return np.argmax(self.values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

O algoritmo ε-greedy tem o benefício da simplicidade e a garantia de que continuará explorando (um pouco) mesmo depois de muitos passos. No entanto, não leva em conta o quanto se sabe sobre cada ação quando explora, ao contrário do UCB ou Thompson Sampling.

UCB

Por outro lado, a estratégia UCB considera tanto a recompensa estimada quanto a incerteza ou variação associada ao decidir sobre uma ação. Apresenta preferência por ações com alta incerteza, buscando diminuí-la e garantindo uma fase de exploração mais produtiva. A estratégia UCB é definida matematicamente da seguinte forma:

Sua implementação Python é a seguinte:

 class UCB: def __init__(self, counts, values): self.counts = counts self.values = values def select_arm(self): n_arms = len(self.counts) for arm in range(n_arms): if self.counts[arm] == 0: return arm ucb_values = [0.0 for arm in range(n_arms)] total_counts = sum(self.counts) for arm in range(n_arms): bonus = sqrt((2 * log(total_counts)) / float(self.counts[arm])) ucb_values[arm] = self.values[arm] + bonus return np.argmax(ucb_values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

O equilíbrio entre exploração e exploração no UCB vem de sua fórmula: o valor estimado de uma ação mais um termo que diminui com o tempo (à medida que se aprende mais sobre a ação), mas aumenta com a incerteza sobre essa ação. Assim, o algoritmo tende a explorar braços com alta incerteza e alto potencial de recompensa.

Amostragem de Thompson

Thompson Sampling é um algoritmo de inspiração bayesiana para o problema do bandido multi-armado. Ele atribui uma distribuição a priori às probabilidades de recompensa de cada bandido (ou cada ação) e atualiza essas a priori conforme as recompensas são observadas. A seleção da ação é probabilística, de acordo com a distribuição posterior sobre a melhor ação.

Em uma estrutura Beta-Bernoulli, consideramos a distribuição de recompensa de cada bandido como uma distribuição de Bernoulli (ou seja, recompensas binárias 0 ou 1). Em seguida, atribuímos um Beta antes da probabilidade de obter uma recompensa. A distribuição Beta é a priori conjugada da distribuição de Bernoulli, o que permite uma fácil atualização posterior.

Lógica:

1. Atribua a cada bandido uma distribuição Beta com parâmetros α=1, β=1 (Uniform prior).

2. Para cada rodada:

   1. Experimente um número aleatório da distribuição Beta atual de cada bandido.
   2. Selecione o bandido com o maior número amostrado e puxe esse bandido.
   3. Observe a recompensa do bandido puxado. Se for um sucesso (1), aumente o α do bandido em um; se for uma falha (0), aumente o β do bandido em um.
   4. Repita os passos 2 e 3.

 import numpy as np from scipy.stats import beta class Bandit: def __init__(self, true_probability): self.true_probability = true_probability self.alpha = 1 self.beta = 1 def pull(self): return np.random.random() < self.true_probability def sample(self): return np.random.beta(self.alpha, self.beta) def update(self, reward): self.alpha += reward self.beta += (1 - reward) def Thompson(bandits, num_trials): rewards = np.zeros(num_trials) for i in range(num_trials): # Thompson sampling j = np.argmax([b.sample() for b in bandits]) # Pull the arm for the bandit with the largest sample reward = bandits[j].pull() # Update rewards log rewards[i] = reward # Update the distribution for the bandit whose arm we just pulled bandits[j].update(reward) return rewards # Suppose we have 3 bandits with these true probabilities true_probabilities = [0.2, 0.5, 0.75] bandits = [Bandit(p) for p in true_probabilities] # Run experiment rewards = Thompson(bandits, num_trials=10000) # Print the total reward print("Total reward earned:", rewards.sum()) print("Overall win rate:", rewards.sum() / len(rewards))

Thompson Sampling, portanto, "explora" ações sobre as quais é incerto (aquelas para as quais a distribuição de valores é espalhada) e "explora" ações que acredita que podem ter alto valor (aquelas para as quais a distribuição é distorcida para valores altos).

Com o tempo, quanto mais se aprende sobre cada ação, as distribuições se tornam mais pontiagudas e as ações escolhidas pelo algoritmo tendem a convergir para aquela com o maior valor esperado.

O balanço exploração/exploração na Thompson Sampling vem naturalmente da forma das distribuições. Este método é bastante eficaz, mas pode ser mais complexo de implementar do que UCB ou ε-greedy, particularmente para problemas com espaços de ação grandes ou contínuos ou estruturas de recompensa complexas.

Por que bandidos multiarmados são os melhores RL para sua tarefa?

1. Simplicidade : os algoritmos MAB são mais simples e computacionalmente mais eficientes do que os algoritmos RL completos, que requerem manutenção e atualização de uma tabela ou aproximador de valores de ação de estado potencialmente grande.
2. Equilíbrio de exploração e exploração : os algoritmos MAB fornecem métodos robustos para gerenciar o trade-off entre tentar novas ações e manter boas ações conhecidas.
3. Adaptabilidade em tempo real : os algoritmos MAB podem se adaptar em tempo real às mudanças nas distribuições de recompensa das ações.
4. Fácil integração : A simplicidade e eficiência dos MABs permitem fácil integração em sistemas existentes, proporcionando benefícios imediatos com interrupção mínima.
5. Ampla aplicabilidade : os MABs foram aplicados com sucesso em diversos campos, incluindo publicidade (escolher qual anúncio exibir para maximizar a taxa de cliques), saúde (personalizar estratégias de tratamento) e otimização de páginas da web (teste A/B).

Aplicações de MABs

Multi-Armed Bandits (MABs) têm uma ampla gama de aplicações em vários setores e domínios. Aqui estão alguns exemplos de como eles podem ser usados:

1. Publicidade on-line : os MABs podem ser usados para ajustar dinamicamente a seleção de anúncios a serem exibidos aos usuários com base em suas interações. Isso ajuda a maximizar as taxas de cliques ou conversões ao longo do tempo.
2. Ensaios Clínicos : Na pesquisa médica, os algoritmos MAB podem ser usados para atribuir dinamicamente pacientes a diferentes tratamentos. Isso garante que mais pacientes recebam os tratamentos mais eficazes, reduzindo o arrependimento, ou seja, a perda por nem sempre escolher o melhor tratamento.
3. Recomendação de artigos de notícias : sites de notícias podem usar MABs para personalizar os artigos exibidos para cada usuário. O algoritmo MAB pode aprender ao longo do tempo em quais tipos de artigos cada usuário está interessado e ajustar as recomendações de acordo.
4. Preços dinâmicos : plataformas de comércio eletrônico ou companhias aéreas podem usar algoritmos MAB para otimizar suas estratégias de preços em tempo real, maximizando a receita com base no comportamento do cliente e na dinâmica do mercado.
5. Roteamento de Rede : Em redes de computadores, os algoritmos MAB podem ser usados para gerenciar o congestionamento e otimizar o roteamento de pacotes. Cada rota pode ser tratada como um braço, e o algoritmo pode selecionar rotas dinamicamente para minimizar a perda ou latência de pacotes.
6. Ajuste de hiperparâmetros de aprendizado de máquina : os MABs também podem ser usados para otimizar a seleção de hiperparâmetros em modelos de aprendizado de máquina. Cada conjunto de hiperparâmetros pode ser tratado como um braço, e o algoritmo pode refinar iterativamente a seleção para encontrar a configuração ideal do modelo.

Em essência, a utilidade dos MABs se estende muito além das tarefas convencionais de aprendizado por reforço. Eles simbolizam uma estrutura eficaz para aprimorar os processos de tomada de decisão em ambientes de incerteza, fornecendo soluções práticas para problemas do mundo real em vários domínios. Portanto, quando a tarefa envolve equilibrar exploração e exploração, os MABs geralmente surgem como a opção ideal, fornecendo uma solução versátil, robusta e adaptável para os dilemas da tomada de decisões.

Conclusão

Multi-Armed Bandits, com sua capacidade de equilibrar exploração e exploração de forma eficaz, fornecem uma solução robusta para muitos problemas de tomada de decisão do mundo real. Sua adaptabilidade e versatilidade inerentes os tornam uma ferramenta valiosa, não apenas no domínio do aprendizado por reforço, mas também em uma ampla gama de aplicações, desde assistência médica até publicidade online. Seja você um cientista de dados, um entusiasta de aprendizado de máquina ou um profissional que busca aprimorar seus processos de tomada de decisão, entender e implementar estratégias MAB pode ser uma experiência enriquecedora e recompensadora.