Introdução aos Bandidos Multi-Armados

Copyright 2021 Os autores do TF-Agents.

Introdução

Multi-Armed Bandit (MAB) é uma estrutura de aprendizado de máquina em que um agente deve selecionar ações (armas) para maximizar sua recompensa cumulativa a longo prazo. A cada rodada, o agente recebe algumas informações sobre o estado atual (contexto), a seguir escolhe uma ação com base nessas informações e na experiência adquirida nas rodadas anteriores. Ao final de cada rodada, o agente recebe a recompensa associada à ação escolhida.

Talvez o exemplo mais puro é o problema que emprestou seu nome ao MAB: imaginar que somos confrontados com k máquinas caça-níqueis (slot machines), e precisamos descobrir qual deles tem a melhor pagamento, sem perder muito dinheiro.

Tentar cada máquina uma vez e, em seguida, escolher a que pagou mais não seria uma boa estratégia: o agente pode cair na escolha de uma máquina que teve um resultado feliz no início, mas é subótima em geral. Em vez disso, o agente deve voltar repetidamente a escolher as máquinas que não parecem muito boas, a fim de coletar mais informações sobre elas. Este é o principal desafio em Multi-Armed Bandits: o agente tem que encontrar a mistura certa entre explorar o conhecimento prévio e explorar, de forma a evitar negligenciar as ações ótimas.

As instâncias mais práticas do MAB envolvem um pedaço de informação lateral sempre que o aluno toma uma decisão. Chamamos essas informações secundárias de "contexto" ou "observação".

Bandidos Multi-Armados e Aprendizagem por Reforço

Por que há um MAB Suite na biblioteca TF-Agents? Qual é a conexão entre RL e MAB? Os Bandidos Multi-Armados podem ser vistos como um caso especial de Aprendizagem por Reforço. Para citar Introdução à RL :

Em cada passo de tempo, o agente realiza uma ação sobre o meio ambiente com base em sua política $\pi(a_t|s_t)$, onde $s_t$ é a observação atual do meio ambiente, e recebe uma recompensa $r_{t+1}$ ea próxima observação $s_{t+1}$ do ambiente . O objetivo é aprimorar a política de forma a maximizar a soma das recompensas (retorno).

No caso geral RL, a próxima observação $s_{t+1}$ depende do estado anterior $s_t$ ea ação $a_t$ tomado pela política. Esta última parte é o que separa o MAB do RL: no MAB, o próximo estado, que é a observação, não depende da ação escolhida pelo agente.

Essa semelhança nos permite reutilizar todos os conceitos existentes nos TF-Agents.

• Um ambiente saídas observações e responde a ações com recompensas.
• A política gera uma ação baseada em uma observação, e
• Um agente atualiza repetidamente a política com base em tuplas observação-ação-recompensa anteriores.

O ambiente do cogumelo

Para fins ilustrativos, usamos um exemplo de brinquedo chamado "Ambiente de cogumelo". O conjunto de dados de cogumelo ( Schlimmer, 1981 ) consiste de exemplos marcados de cogumelos comestíveis e venenosos. As características incluem formas, cores, tamanhos de diferentes partes do cogumelo, bem como odores e muito mais.

O conjunto de dados cogumelo, assim como todos os conjuntos de dados de aprendizagem supervisionada, pode ser transformado em um problema MAB contextual. Usamos o método também usado por Riquelme et al. (2018) . Nessa conversão, o agente recebe as características de um cogumelo, decide comê-lo ou não. Comer um cogumelo comestível resulta em uma recompensa de +5, enquanto comer um cogumelo venenoso dará +5 ou -35 com a mesma probabilidade. Não comer o cogumelo resulta em 0 recompensa, independentemente do tipo de cogumelo. A tabela a seguir resume as atribuições de recompensa:

           | edible | poisonous
-----------|--------|----------
eating it  |     +5 | -35 / +5
leaving it |      0 |        0

O Agente LinUCB

Ter um bom desempenho em um ambiente de bandido contextual requer uma boa estimativa da função de recompensa de cada ação, dada a observação. Uma possibilidade é estimar a função de recompensa com funções lineares. Ou seja, para cada ação $i$, estamos tentando encontrar o parâmetro $\theta_i\in\mathbb R^d$ para o qual as estimativas

$r_{t, i} \sim \langle v_t, \theta_i\rangle$

estão o mais próximos possível da realidade. Aqui $v_t\in\mathbb R^d$ é o contexto recebida no passo de tempo $t$. Então, se o agente está muito confiante em suas estimativas, ele pode escolher $\arg\max_{1, ..., K}\langle v_t, \theta_k\rangle$ para obter a maior recompensa esperada.

Conforme explicado acima, simplesmente escolher o braço com a melhor estimativa de recompensa não leva a uma boa estratégia. Há muitas maneiras diferentes para misturar a exploração e exploração de agentes estimador lineares, e uma das mais famosas é a confiança Linear Limite Superior (LinUCB) algoritmo (ver, por exemplo Li et al. 2010 ). LinUCB tem dois blocos de construção principais (com alguns detalhes omitidos):

1. Mantém estimativas para os parâmetros de cada braço com linear de mínimos quadrados: $\hat\theta_i\sim X^+_i r_i$, onde $X_i$ e $r_i$ são os contextos e recompensas de rodadas empilhadas onde braço $i$ foi escolhido, e $()^+$ é o inverso pseudo .
2. Ele mantém elipsóides de confiança definidos pelo inverso covariância $X_i^\top X_i$ para as estimativas anteriores.

A ideia principal do LinUCB é "Otimismo em Frente à Incerteza". O agente incorpora a exploração por meio do aumento das estimativas em um montante que corresponde à variância dessas estimativas. É aí que os elipsóides confiança entram em cena: para cada braço, a estimativa otimista é $\hat r_i = \max_{\theta\in E_i}\langle v_t, \theta\rangle$, onde $E_i$ é o elipsóide em torno $\hat\theta_i$. Os escolhe agente mais bonito braço $\arg\max_i\hat r_i$.

Claro que a descrição acima é apenas um resumo intuitivo, mas superficial do que o LinUCB faz. Uma implementação pode ser encontrado na nossa base de código aqui

Qual é o próximo?

Se você quiser ter um tutorial mais detalhadas sobre a nossa biblioteca Bandits dar uma olhada em nosso tutorial para bandidos . Se, em vez disso, você gostaria de começar a explorar nossa biblioteca imediatamente, você pode encontrá-lo aqui . Se você está ainda mais ansioso para começar a treinar, olhada em alguns dos nossos exemplos end-to-end aqui , incluindo o ambiente cogumelo acima descrito com LinUCB aqui .