Sulla espressività del Markov Reward

Markov Reward expressiveness.

La ricompensa è la forza trainante per gli agenti di apprendimento per rinforzo (RL). Data la sua importanza centrale nell’RL, si assume spesso che la ricompensa sia sufficientemente generale nella sua espressività, come riassunto dall’ipotesi di ricompensa di Sutton e Littman:

“…tutto ciò che intendiamo per obiettivi e scopi può essere ben pensato come massimizzazione del valore atteso della somma cumulativa di un segnale scalare ricevuto (ricompensa).” ‍ – SUTTON (2004), LITTMAN (2017)

Nel nostro lavoro, compiamo i primi passi verso uno studio sistematico di questa ipotesi. Per farlo, consideriamo il seguente esperimento mentale che coinvolge Alice, una designer, e Bob, un agente di apprendimento:

• Esplorando la bellezza della matematica pura in modi nuovi.
• Creazione di agenti interattivi con apprendimento per imitazione
• Migliorare i modelli linguistici recuperando da trilioni di token

Supponiamo che Alice pensi a un compito che potrebbe piacere a Bob imparare a risolvere – questo compito potrebbe essere sotto forma di una descrizione in linguaggio naturale (“bilancia questo palo”), uno stato immaginato (“raggiungi una delle configurazioni vincenti di una scacchiera”) o qualcosa di più tradizionale come una funzione di ricompensa o valore. Quindi, immaginiamo che Alice traduca la sua scelta di compito in un generatore che fornirà un segnale di apprendimento (come una ricompensa) a Bob (un agente di apprendimento), che imparerà da questo segnale per tutta la sua vita. Poi ancoriamo il nostro studio dell’ipotesi di ricompensa affrontando la seguente domanda: dato la scelta di Alice di un compito, esiste sempre una funzione di ricompensa che può trasmettere questo compito a Bob?

Cosa è un compito?

Per rendere concreto il nostro studio di questa domanda, limitiamo prima la nostra attenzione a tre tipi di compiti. In particolare, introduciamo tre tipi di compiti che riteniamo catturino tipi sensati di compiti: 1) Un insieme di politiche accettabili (SOAP), 2) Un ordine di politiche (PO) e 3) Un ordine di traiettorie (TO). Questi tre tipi di compiti rappresentano istanze concrete dei tipi di compiti che potremmo volere che un agente impari a risolvere.

Studiamo quindi se la ricompensa è in grado di catturare ciascuno di questi tipi di compito in ambienti finiti. In modo cruciale, concentriamo la nostra attenzione solo sulle funzioni di ricompensa di Markov; ad esempio, dato uno spazio di stati sufficiente a formare un compito come le coppie (x, y) in un mondo a griglia, esiste una funzione di ricompensa che dipende solo da questo stesso spazio di stati e può catturare il compito?

Primo risultato principale

Il nostro primo risultato principale mostra che per ciascuno dei tre tipi di compito, ci sono coppie ambiente-compito per le quali non esiste una funzione di ricompensa di Markov che può catturare il compito. Un esempio di una tale coppia è il compito “andare tutto intorno alla griglia in senso orario o antiorario” in un tipico mondo a griglia:

Questo compito è naturalmente catturato da un SOAP che consiste di due politiche accettabili: la politica “in senso orario” (in blu) e la politica “in senso antiorario” (in viola). Perché una funzione di ricompensa di Markov esprima questo compito, dovrebbe rendere queste due politiche strettamente più elevate in valore rispetto a tutte le altre politiche deterministiche. Tuttavia, non esiste una tale funzione di ricompensa di Markov: l’ottimalità di un’unica azione “muoversi in senso orario” dipenderà dal fatto che l’agente si stava già muovendo in quella direzione in passato. Poiché la funzione di ricompensa deve essere Markoviana, non può trasmettere questo tipo di informazione. Esempi simili dimostrano che la ricompensa di Markov non può catturare ogni ordine di politiche e ordine di traiettorie.

Secondo risultato principale

Dato che alcuni compiti possono essere catturati e altri no, esploriamo quindi se esiste una procedura efficiente per determinare se un dato compito può essere catturato dalla ricompensa in un dato ambiente. Inoltre, se esiste una funzione di ricompensa che cattura il compito dato, vorremmo idealmente essere in grado di produrre una tale funzione di ricompensa. Il nostro secondo risultato è un risultato positivo che afferma che per qualsiasi coppia ambiente-compito finita, esiste una procedura che può 1) decidere se il compito può essere catturato dalla ricompensa di Markov nell’ambiente dato, e 2) produrre la funzione di ricompensa desiderata che trasmette esattamente il compito, quando esiste una tale funzione.

Questo lavoro stabilisce percorsi iniziali per comprendere l’ambito dell’ipotesi di ricompensa, ma c’è ancora molto da fare per generalizzare questi risultati oltre gli ambienti finiti, le ricompense di Markov e le nozioni semplici di “compito” e “espressività”. Speriamo che questo lavoro offra nuove prospettive concettuali sulla ricompensa e il suo ruolo nell’apprendimento per rinforzo.