AI Academy

Safe Exploration-Exploitation: come conciliare performance e garanzie sul comportamento dell’AI

Il principio alla base è la ricerca del migliore trade-off tra una sufficiente raccolta di dati (Exploration) e un utilizzo efficace di questi ultimi (Exploitation) per trovare la soluzione ottimale al problema di decisione da affrontare

Pubblicato il 12 Set 2022

Francesco Emanuele Stradi

AI Scientist AIRIC (AI Research and Innovation Center) - Politecnico di Milano

online learning

L’Online Learning è un paradigma dell’apprendimento automatico (machine learning) molto studiato dalla comunità scientifica per i problemi decisionali in tutti quei casi in cui i dati diventano disponibili solo durante l’esecuzione degli algoritmi. Il principio alla base del suo funzionamento è la ricerca del migliore trade-off tra una sufficiente raccolta di dati (Exploration) e un utilizzo efficace di questi ultimi (Exploitation) per trovare la soluzione ottimale al problema di decisione da affrontare. Nonostante la grande mole di articoli scientifici prodotta sull’argomento, l’applicazione dell’Online Learning in domini reali legati al mondo delle imprese presenta alcune criticità. Queste riguardano principalmente il modo con cui gli algoritmi esplorano. Infatti, una esplorazione troppo limitata può impedire agli algoritmi di trovare buone soluzioni e di conseguenza dare risultati non del tutto soddisfacenti all’azienda. Dall’altra parte, una esplorazione incontrollata può portare a prestazioni molto oscillanti nelle fasi iniziali dell’apprendimento (ad esempio in termini di fatturato) che solitamente spaventano i decisori umani, spingendoli a spegnere gli algoritmi. In questo articolo, proponiamo quella che si sta dimostrando la soluzione più promettente a queste criticità: costruire algoritmi di apprendimento online che siano safe, cioè che controllino in modo opportuno l’esplorazione in modo tale da avere sia garanzie di prestazioni stabili e non oscillanti nel tempo che il raggiungimento della soluzione ottima.

Cos’è l’Online Learning?

L’Online Learning (o apprendimento sequenziale) è quella branca dell’apprendimento automatico finalizzata a risolvere problemi di decisione in cui l’agente (alias, decisore) riceve un dato alla volta nell’arco di un orizzonte temporale, e perciò ha una visione parziale del problema da affrontare. In contrapposizione a quanto avviene per i paradigmi standard del Machine Learning, gli algoritmi di apprendimento online non hanno a disposizione un dataset iniziale da cui imparare un modello, bensì l’apprendimento deve essere eseguito in maniera sequenziale (turno dopo turno), spesso in un ambiente di interazione non noto a priori.

L’esempio più intuitivo per comprendere l’utilità dell’Online Learning è il lancio di un nuovo prodotto sul mercato e la conseguente scelta del prezzo (pricing di prodotti). Dal momento che la novità dell’articolo rende difficile avere uno storico dei dati, non è possibile imparare un modello che associ a ogni prezzo i possibili guadagni. È proprio questa tipologia di problemi a essere risolvibile mediante l’utilizzo di un algoritmo di apprendimento online, il quale quotidianamente propone un prezzo (in base ai dati raccolti nei turni passati), ne osserva il guadagno generato a fine giornata e aggiorna la propria politica decisionale di conseguenza. Da notare che l’Online Learning è di cruciale importanza in tutte quelle situazioni in cui degli eventi modificano in modo radicale il comportamento del mercato, ad esempio le pandemie, i conflitti bellici, gli sconvolgimenti climatici.

Negli ultimi anni, l’Online Learning ha guadagnato molta attenzione da parte delle industrie tech (e non), in quanto permette di risolvere problemi di decisione ad esse ben familiari quali, tra gli altri, problemi di pricing come quello nell’esempio appena visto, e di ottimizzazione di campagne pubblicitarie. Questo paradigma di apprendimento è inoltre utile laddove la scarsità di dati, un ambiente dinamico o altre difficoltà tipiche di scenari reali non permettano di costruire dataset statici affidabili per l’utilizzo di algoritmi offline. Perciò, non solo gran parte delle compagnie della Silicon Valley ricorrono quotidianamente a questi approcci – basti pensare all’importanza che le campagne pubblicitarie hanno in grandi aziende come Google e Facebook -, ma è nostro parere che, presto, anche aziende operanti in settori più tradizionali dovranno ricorrere a questo tipo di soluzioni per rimanere competitive sul mercato.

Exploration contro Exploitation: come trovare il giusto trade-off

Prima di soffermarsi sulle applicazioni concrete dell’Online Learning è necessario comprendere a grandi linee i principi teorici che ne permettono il funzionamento. La difficoltà principale di apprendere in maniera sequenziale è che, in molti domini applicativi, il dato raccolto in un singolo turno dipende dalla soluzione (o azione) scelta al turno precedente (il cosiddetto feedback). Se a ciò si aggiunge che i guadagni ottenuti scegliendo un’azione variano in maniera randomica attorno a un valore medio non noto, come ad esempio il numero di prodotti venduti in un giorno, si intuisce facilmente che il modo in cui le azioni devono essere selezionate può non essere banale. Infatti, per capire quale sia l’azione ottima, cioè quella corrispondente ad un guadagno maggiore (o costo minore, a seconda del problema specifico), è necessario variare la selezione delle azioni nel tempo. Questa difficoltà è conosciuta nella letteratura scientifica come Exploration-Exploitation dilemma. L’Exploration (o esplorazione) serve a raccogliere dati in aree dello spazio delle soluzioni poco esplorate: scegliere tutte le azioni disponibili più volte permette infatti di comprendere quali di esse siano vincenti e quali invece portino a guadagni ridotti. L’Exploitation (lett. sfruttamento), invece, consiste nello sfruttare la conoscenza accumulata per dedurre l’azione che ha più probabilità di essere ottimale e applicarla. Trovare un giusto compromesso tra queste due fasi è la chiave per ottenere una buona performance.

La tecnica più nota, oltre che la più impiegata, per risolvere l’Exploration-Exploitation dilemma è conosciuta come ‘Optimism in face of uncertainty’ (lett. ottimismo per contrastare l’incertezza): si impone che l’azione scelta ad ogni turno non dipenda solamente dai guadagni ottenuti nel passato dall’azione stessa ma anche da un bonus dovuto alla mancata esplorazione. Perciò, una soluzione poco esplorata, nonostante nei round passati abbia fornito un guadagno basso, potrebbe essere scelta al posto di azioni con valori più alti ma anche molto esplorati. Ovviamente, la scelta del bonus deve essere tale da ottenere buone performance, cioè si deve garantire che la differenza tra i guadagni ottenuti dalle azioni scelte e quelli che si sarebbero ottenuti conoscendo a priori l’ottimo del problema diminuisca nel tempo.

Multi-Armed Bandit problem: uno dei problemi più studiati dell’Online Learning

Quando l’Esplorazione tout court non è possibile: il principio di safety

Conseguenza dell’Exploration-Exploitation dilemma è che, all’inizio della dinamica di apprendimento (cioè quando si è raccolta solo una piccola quantità di dati), molte tecniche online prediligano la scelta di soluzioni significativamente diverse tra loro, in modo tale da osservarne i relativi guadagni. Infatti, per imparare che risultati aspettarsi nello scegliere determinate azioni, esse devono essere selezionate più di una volta nell’arco dell’orizzonte temporale, comprese quelle con un guadagno medio irrisorio.

Dal punto di vista teorico, dove il guadagno ottenuto in un singolo turno ha poca rilevanza, questo tipo di esplorazione garantisce una convergenza più rapida alla soluzione ottima, ed è perciò stato per molti anni esente da critiche. Sovente però, in particolar modo in applicazioni orientate al mondo delle imprese, una esplorazione tout court mostra le sue criticità: un turno, infatti, non rappresenta più un’istanza astratta del processo di ottimizzazione, bensì una giornata (mese, anno…) di lavoro, con tutte le difficoltà che ciò comporta. Per supportare questa tesi è sufficiente fare riferimento a domini applicativi specifici quali finanza, sanità, e-commerce o molti altri.

Exploration-Exploitation: alcuni esempi

Per quanto concerne la finanza, e nello specifico il mercato azionario, un singolo turno può spesso rappresentare una giornata di investimenti. Le azioni, quindi, possono essere specifiche allocazioni di un portfolio azionario, o qualsiasi altra operazione di mercato. Qualora venisse applicato un algoritmo online standard, ciò potrebbe comportare scelte di investimenti sensibilmente rischiose, o peggio, dannose. Dal momento che il successo di un fondo dipende dalla variazione del valore degli asset under management (AUM), l’algoritmo potrebbe perdere gran parte delle risorse nei primi turni (alias, prime giornate di investimenti), e raggiungere la soluzione ottima solo quando le disponibilità economiche della compagnia sono ormai esaurite.

La situazione peggiora se ci spostiamo nel mondo della sanità, in particolare dei trials clinici. In questo caso, l’insieme delle soluzioni è rappresentato da possibili cure da fornire ad un paziente. Non è neanche necessario soffermarsi per comprendere a pieno le enormi criticità che ciò comporti in termini di rischio. Un’azione sbagliata, anche al primo turno, potrebbe infatti portare a danni per il paziente curante.

Come ultimo esempio, l’e-commerce apparirà sicuramente meno evidente dei precedenti. Ebbene, inseriamoci in un contesto di campagna pubblicitaria, in cui l’azienda desidera scegliere la puntata giornaliera migliore per vincere le “aste” che le permetterebbero la disposizione delle proprie inserzioni sul web; aggiudicarsi il maggior numero di aste significa mostrare i propri annunci ad un numero maggiore di persone. La funzione da imparare in questo caso potrebbe essere il numero di click sulla specifica inserzione, essendo esso un diretto indicatore dei profitti potenziali. Il problema si presenta nel momento in cui l’algoritmo scelga puntate che abbiano costi giornalieri troppo alti rispetto al guadagno, cioè soluzioni che portano notevoli entrate non curandosi però delle risorse che dovranno essere spese per garantirle.

Dagli ultimi esempi risulta chiaro come per ovviare a questi problemi sia necessario sviluppare algoritmi che lavorino su porzioni limitate dello spazio delle soluzioni, come investimenti con indici di rischio (ad esempio la volatilità del portafoglio azionario) di valore ragionevole o il sottoinsieme delle cure che sono sicure per il paziente.

La Safe Exploration nell’online learning

Recentemente, sostanziale attenzione da parte della comunità scientifica è stata dedicata a questa tipologia di algoritmi online, atti a vincolare la selezione delle azioni per garantire “sicurezza” nell’esplorazione (Safe Exploration). Molti algoritmi di Online Learning sono stati rivisitati per crearne una versione safe: molti di essi hanno solo garanzie teoriche, mentre altri sono stati costruiti per applicazioni specifiche.

Le tecniche che garantiscono Safe Exploration hanno diverse caratteristiche in comune: molte si basano sul partire da azioni sicure note a priori e sull’espandere questo insieme di soluzioni quando si hanno stime più sicure sui possibili guadagni. Esistono invece algoritmi che non richiedono di conoscere a priori scelte sicure; essi garantiscono però che la probabilità di safety cresca col numero di turni giocati (cioè in base al numero di dati raccolti).

Algoritmi safe nel campo della robotica

Notevole attenzione da parte della comunità scientifica è stata dedicata allo sviluppo di algoritmi safe con applicazioni nel campo della robotica; nel dettaglio, quando qualsiasi operazione deve essere compiuta da un robot, è necessario inserire nel sistema dei parametri (detti iperparametri) che ne permettano il funzionamento. Partendo da algoritmi safe dello stato dell’arte, si può opportunamente modificarli per poi calarli nel contesto della ricerca di iperparametri sicuri. La stima di questi ultimi infatti deve essere safe, dal momento che una esplorazione eccessiva potrebbe comportare il danneggiamento o perfino la rottura dell’automa, con conseguenti danni economici per l’azienda che lo possiede. Da sottolineare il fatto che, in questo settore, è relativamente facile trovare una politica safe iniziale, dal momento che la conoscenza di dominio degli esperti in robotica è ormai ampia (per chi fosse interessato ad approfondire l’argomento: Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Robotics”).

Ottimizzazione di campagne pubblicitarie e giochi

Un’altra applicazione interessante, di cui sono state descritte le criticità nella sezione precedente, è l’ottimizzazione di campagne pubblicitarie. È possibile, infatti affrontare il problema di scegliere una puntata ottimale per le aste pubblicitarie, tenendo allo stesso tempo conto del ROI (Return on Investment) potenziale. Come? Utilizzando un algoritmo online standard per stimare (sia ottimisticamente che pessimisticamente) i possibili costi e i possibili click che una pubblicità potrebbe ricevere date determinate puntate, mentre la scelta della puntata nel giorno successivo è ottenuta limitando lo spazio delle azioni a quelle puntate che, nel caso peggiore, raggiungano comunque la soglia minima di ROI. L’ottimizzazione, dunque, rimane guidata dal numero di click, ma l’esplorazione viene incentrata su puntate che siano safe ad alta probabilità (Per chi fosse interessato ad approfondire l’argomento: Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty”).

Per concludere, è interessante presentare un dominio applicativo meno business-oriented, ma che comunque si colloca tra i precursori della ricerca nel Safe Online Learning: i giochi. Negli ultimi anni, notevoli progressi sono stati fatti nello sviluppo di algoritmi di learning in grado di battere professionisti in giochi come il Poker (Libratus, 2017), Go (AlphaGo, 2015) e molti altri. Il problema di questi algoritmi è che sono talmente abili da disincentivare chiunque nel provare a sfidarli, e di conseguenza risultano inutilizzabili: dopotutto, chi vorrebbe perdere tempo nel fronteggiare un super-computer? Spinta da questi motivi, la comunità scientifica ha devoluto notevoli risorse nel creare algoritmi in grado di giocare e vincere, mantenendo allo stesso tempo il guadagno dell’avversario superiore a una soglia minima, in modo tale che l’incentivo a giocare non diminuisca nel tempo.

L’utilizzo di tecniche safe supporterà l’apprendimento delle strategie di gioco da parte di utenti umani, proprio grazie alla possibilità di tenere gli utenti il più possibile ingaggiati. Questo tipo di utilizzo potrà essere diretto anche a tutti quei giochi detti serious games, in cui l’obiettivo è insegnare la risoluzione di task non ricreativi, come ad esempio task scolastici oppure lavorativi.

Libratus, bot che sfrutta l’AI per giocare a Poker

[Fonte: Carnegie Mellon University]

Conclusioni

Come visto nelle sezioni precedenti, l’Online Learning può presentare criticità quando utilizzato in scenari reali; queste difficoltà sono dovute all’impossibilità, da parte di aziende operanti in determinati settori, di garantire l’esplorazione tout court che sarebbe ottimale per gli algoritmi di apprendimento sequenziale. Fortunatamente, soluzioni efficienti sono state trovate. Abbiamo approfondito la proprietà di safety, in grado di garantire un buon compromesso tra l’exploration, imprescindibile per una buona performance teorica, e l’exploitation, necessaria per assicurare all’azienda i dovuti guadagni e minimizzare i rischi.

Valuta la qualità di questo articolo

La tua opinione è importante per noi!

Articoli correlati