Introduzione ai banditi multi-armati

Copyright 2021 Gli autori degli agenti TF.

introduzione

Multi-Armed Bandit (MAB) è un framework di Machine Learning in cui un agente deve selezionare azioni (arms) al fine di massimizzare la sua ricompensa cumulativa a lungo termine. In ogni round, l'agente riceve alcune informazioni sullo stato attuale (contesto), quindi sceglie un'azione in base a queste informazioni e all'esperienza acquisita nei round precedenti. Alla fine di ogni round, l'agente riceve la ricompensa associata all'azione scelta.

Forse l'esempio più puro è il problema che ha dato il nome al MAB: immaginiamo che siamo di fronte a k slot machine (banditi con un braccio), e abbiamo bisogno di capire quale ha la migliore vincita, pur non perdendo troppi soldi.

Provare ogni macchina una volta e poi scegliere quella che ha pagato di più non sarebbe una buona strategia: l'agente potrebbe cadere nella scelta di una macchina che all'inizio ha avuto un esito fortunato ma in generale non è ottimale. Invece, l'agente dovrebbe tornare ripetutamente a scegliere macchine che non sembrano così buone, al fine di raccogliere più informazioni su di esse. Questa è la sfida principale in Multi-Armed Bandits: l'agente deve trovare il giusto mix tra lo sfruttamento delle conoscenze pregresse e l'esplorazione per evitare di trascurare le azioni ottimali.

Istanze più pratiche di MAB coinvolgono un'informazione secondaria ogni volta che lo studente prende una decisione. Chiamiamo questa informazione secondaria "contesto" o "osservazione".

Banditi multi-armati e apprendimento di rinforzo

Perché c'è una MAB Suite nella libreria TF-Agents? Qual è la connessione tra RL e MAB? I banditi multi-armati possono essere considerati un caso speciale di apprendimento per rinforzo. Per citare Introduzione a RL :

Ad ogni passo, l'agente compie un'azione sull'ambiente base alla sua politica $\pi(a_t|s_t)$, dove $s_t$ è la corrente osservazione dall'ambiente, e riceve un premio $r_{t+1}$ e la successiva osservazione $s_{t+1}$ dall'ambiente . L'obiettivo è quello di migliorare la politica in modo da massimizzare la somma delle ricompense (rendimento).

Nel caso generale RL, il seguente osservazione $s_{t+1}$ dipende dallo stato precedente $s_t$ e l'azione $a_t$ preso dalla politica. Quest'ultima parte è ciò che separa MAB da RL: in MAB, lo stato successivo, che è l'osservazione, non dipende dall'azione scelta dall'agente.

Questa somiglianza ci permette di riutilizzare tutti i concetti che esistono in TF-Agents.

• Un ambiente uscite osservazioni, e risponde alle azioni con ricompense.
• Una politica emette un'azione sulla base dell'osservazione, e
• Un agente aggiorna più volte la politica sulla base di precedenti tuple di osservazione-azione-ricompensa.

L'ambiente dei funghi

A scopo illustrativo, utilizziamo un esempio di giocattolo chiamato "Ambiente dei funghi". Il set di dati di funghi ( Schlimmer 1981 ) si compone di esempi etichettate di funghi commestibili e velenosi. Le caratteristiche includono forme, colori, dimensioni delle diverse parti del fungo, nonché odore e molto altro.

Il dataset del fungo, proprio come tutti i dataset dell'apprendimento supervisionato, può essere trasformato in un problema MAB contestuale. Usiamo il metodo utilizzato anche da Riquelme et al. (2018) . In questa conversione, l'agente riceve le fattezze di un fungo, decide di mangiarlo o meno. Mangiare un fungo commestibile si traduce in una ricompensa di +5, mentre mangiare un fungo velenoso darà +5 o -35 con uguale probabilità. Non mangiare il fungo porta a 0 ricompensa, indipendentemente dal tipo di fungo. La tabella seguente riassume le assegnazioni dei premi:

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

L'agente LinUCB

Eseguire bene in un ambiente bandito contestuale richiede una buona stima sulla funzione di ricompensa di ogni azione, data l'osservazione. Una possibilità è stimare la funzione di ricompensa con funzioni lineari. Cioè, per ogni azione $i$, stiamo cercando di trovare il parametro $\theta_i\in\mathbb R^d$ per i quali le stime

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

sono il più vicino possibile alla realtà. Qui $v_t\in\mathbb R^d$ è il contesto pervenute in tempo passo $t$. Quindi, se l'agente è molto fiducioso nelle sue stime, si può scegliere $\arg\max_{1, ..., K}\langle v_t, \theta_k\rangle$ per ottenere il massimo premio previsto.

Come spiegato sopra, scegliere semplicemente il braccio con la migliore ricompensa stimata non porta a una buona strategia. Ci sono molti modi diversi di mescolare lo sfruttamento e l'esplorazione in agenti stimatori lineari, e uno dei più famosi è la fiducia lineare limite superiore (LinUCB) algoritmo (si veda ad esempio Li al. Et 2010 ). LinUCB ha due elementi costitutivi principali (con alcuni dettagli omessi):

1. Mantiene le stime per i parametri di ogni braccio con lineare dei minimi quadrati: $\hat\theta_i\sim X^+_i r_i$, dove $X_i$ e $r_i$ sono i contesti impilati ed i benefici di colpi in cui braccio $i$ è stato scelto, e $()^+$ è la pseudo inversa .
2. Mantiene ellissoidi di fiducia definiti per l'inverso covarianza $X_i^\top X_i$ per le stime di cui sopra.

L'idea principale di LinUCB è quella di "Ottimismo di fronte all'incertezza". L'agente incorpora l'esplorazione aumentando le stime di un importo che corrisponde alla varianza di tali stime. È qui che gli ellissoidi fiducia entrano in foto: per ogni braccio, la stima ottimistica è $\hat r_i = \max_{\theta\in E_i}\langle v_t, \theta\rangle$, dove $E_i$ è l'ellissoide intorno $\hat\theta_i$. I sceglie agente più bello braccio $\arg\max_i\hat r_i$.

Ovviamente la descrizione di cui sopra è solo un riassunto intuitivo ma superficiale di ciò che fa LinUCB. Un'implementazione può essere trovato nel nostro codice di base qui

Qual è il prossimo?

Se si desidera avere un tutorial più dettagliate sulla nostra biblioteca Bandits dare un'occhiata al nostro tutorial per Bandits . Se, invece, si desidera iniziare ad esplorare la nostra biblioteca subito, lo si può trovare qui . Se siete ancora più ansiosi di iniziare la formazione, un'occhiata ad alcuni dei nostri esempi end-to-end qui , compreso l'ambiente di funghi sopra descritta con LinUCB qui .