intro_bandit.ipynb

Kernel: Python 3

Copyright 2023 The TF-Agents Authors.

#@title Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# https://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

Introdução aos Multi-Armed Bandits

Ver em TensorFlow.org

Executar no Google Colab

Ver fonte no GitHub

Baixar notebook

Introdução

O Multi-Armed Bandit (MAB) é um framework de aprendizado de máquina em que o agente precisa selecionar ações (braços) para maximizar a recompensa cumulativa a longo prazo. Em cada rodada, o agente recebe algumas informações sobre o estado atual (contexto) e escolhe uma ação com base nessas informações e na experiência coletada nas rodadas anteriores. No final de cada rodada, o agente recebe a recompensa associada à ação escolhida.

Talvez o exemplo mais puro seja o problema que deu nome ao MAB (bandido multibraço): imagine que estamos com k caça-níqueis (chamados de bandidos de um braço, ou one-armed bandits) e precisamos descobrir qual dá o melhor prêmio sem perder muito dinheiro.

Testar cada máquina uma vez e depois escolher a que paga mais não seria uma boa estratégia: o agente pode escolher uma máquina que, apesar da sorte no começo, tenha um desempenho geral inferior. Em vez disso, o agente precisa voltar repetidamente a escolher máquinas que não foram tão bem, para coletar mais informações sobre elas. Esse é o principal desafio no Multi-Armed Bandits: o agente precisa encontrar a combinação ideal entre explorar o conhecimento anterior para evitar ignorar ótimas ações.

Casos mais práticos de MAB envolvem uma informação secundária sempre que o learner toma uma decisão. Chamamos essa informação secundária de "contexto" ou "observação".

Multi-Armed Bandits e Aprendizado por Reforço

Por que há uma Suíte MAB na biblioteca do TF-Agents? Qual é a conexão entre RL e MAB? Os Multi-Armed Bandits podem ser considerados como um caso especial de Aprendizado por Reforço. Para citar a Introdução ao RL:

A cada timestep, o agente realiza uma ação no ambiente com base na sua política $\pi(a_t|s_t)$, onde $s_t$ é a observação atual do ambiente, e recebe uma recompensa $r_{t+1}$ e a próxima observação $s_{t+1}$ do ambiente. O objetivo é melhorar a política maximizando a soma das recompensas (retorno).

No caso de RL geral, a próxima observação $s_{t+1}$ depende do estado anterior $s_t$ e da ação $a_t$ realizada pela política. Essa ú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 permite a reutilização de todos os conceitos existentes no TF-Agents.

• Um ambiente gera observações e responde a ações com recompensas.

• Uma política gera uma ação com base em uma observação, e

• Um agente atualiza repetidamente a política com base nas tuplas anteriores de observação-ação-recompensa.

Ambiente Mushroom

Para fins ilustrativos, vamos usar um exemplo de brinquedo chamado "Ambiente Mushroom". O dataset mushroom (Schlimmer, 1981) consiste em exemplos rotulados de cogumelos comestíveis e venenosos. As características incluem formatos, cores, tamanhos de diferentes partes do cogumelo, além de odor e muito mais.

O dataset mushroom, como todos os datasets de aprendizado supervisionado, pode ser transformado em um problema de MAB contextual. Usamos o método também utilizado por Riquelme et al. (2018). Nessa conversão, o agente recebe as características de um cogumelo e decide ou não comer. Comer um cogumelo comestível resulta em uma recompensa de +5, enquanto comer um cogumelo venenoso resulta em +5 ou -35, com a mesma probabilidade. Não comer o cogumelo resulta em uma recompensa de 0, 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

Agente LinUCB

Ter um bom desempenho em um ambiente bandit contextual exige uma boa estimativa da função de recompensa para cada ação, considerando 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 a qual as estimativas

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

são as mais próximas possíveis da realidade. Aqui, $v_t\in\mathbb R^d$ é o contexto recebido no timestep $t$. Em seguida, se o agente tiver bastante confiança nas suas estimativas, ele poderá escolher $\arg\max_{1, ..., K}\langle v_t, \theta_k\rangle$ para obter a recompensa mais alta possível.

Conforme explicado acima, simplesmente escolher o braço com a melhor recompensa estimada não é uma boa estratégia. Há várias maneiras diferentes de combinar a exploitation e exploration nos agentes estimadores lineares, e uma das mais famosas é o algoritmo Linear Upper Confidence Bound (LinUCB) (veja, por exemplo, Li et al. 2010). O LinUCB tem dois pilares principais (com alguns detalhes omitidos):

1. Ele mantém as estimativas para os parâmetros de cada braço com o método dos mínimos quadrados: $\hat\theta_i\sim X^+_i r_i$, onde $X_i$ e $r_i$ são os contextos e recompensas empilhados de rodadas em que o braço $i$ foi escolhido e $()^+$ é a pseudo-inversa.

2. Ele mantém elipsoides de confiança definidos pela covariância inversa $X_i^\top X_i$ para as estimativas acima.

A principal ideia do LinUCB é o "Otimismo diante da incerteza". O agente incorpora a exploração ao aumentar as estimativas por um valor correspondente à variância dessas estimativas. É aí que entram os elipsoides de confiança: para cada braço, a estimativa otimista é $\hat r_i = \max_{\theta\in E_i}\langle v_t, \theta\rangle$, em que $E_i$ é o elipsoide em volta de $\hat\theta_i$. O agente escolhe o braço de melhor aparência $\arg\max_i\hat r_i$.

É claro que a descrição acima é só um resumo intuitivo e superficial do que o LinUCB faz. Uma implementação pode ser encontrada na nossa base de código aqui

Próximos passos

Se você quiser um tutorial mais detalhado sobre nossa biblioteca de Bandits, confira nosso tutorial para Bandits. Se, em vez disso, você quiser começar a explorar imediatamente nossa biblioteca, ela pode ser encontrada aqui. Se você estiver ainda mais ansioso para começar a treinar, confira alguns dos nossos exemplos completos aqui, incluindo o ambiente mushroom descrito acima com o LinUCB aqui.