CPH Algorithm

Parlando sempre di approccio del tipo discretization-free, è stato da poco presentato un nuovo algoritmo che cerca di migliorare i risultati ottenuti con quello di Lazy Approximation: la sua sigla è CPH, e sta per continuous (= C) state MDP through phase-type (= PH) distributions [31]. Questo nome infatti deriva dal fatto che, invece di discretizzare la funzione di tran- sizione o di usare una sua approssimazione con funzioni PWC, questo algo- ritmo utilizza distribuzioni phase-type, le quali permettono di approssimare funzioni di transizione arbitrarie usando delle catene di Markov con tran- sizioni di tipo esponenziale; l'uso di distribuzioni esponenziali per creare i blocchi basilari per le distribuzioni Phase-type è dovuto alle loro particolari proprietà, che permettono di calcolare in modo molto eciente le varie iter- azioni di risoluzione sull'Equazione di Bellaman tramite soluzione analitica del processo di convoluzione all'interno dell'equazione stessa.

Passando alla descrizione del problema MDP risolvibile tramite CPH, si assumerà per semplicità di esposizione che lo spazio degli stati abbia un'uni- ca dimensione continua, solitamente la durata temporale dell'azione eseguita dall'agente nello stato, il cui valore associato decresce esponenzialmente una volta che l'azione viene eseguita. Questo algoritmo quindi, rispetto ad LA, permette l'uso di variabili t > 0 di tipo temporale, che potremmo vedere come delle deadline per l'esecuzione di una determinata azione in un dato stato. Impostando poi il time-to-deadline come t − t0_{, si possono ridenire}

la probabilità di transizione come P (s0_{, s, a) ∗ p(t}0_{) e il reward associato al-}

l'esecuzione, con successo, dell'azione come R(s, a) ∗ p(t0_{), con t}0 _{che indica il}

tempo di esecuzione eettivo di un'azione in accordo con la funzione di den- sità di probabilità esponziale p(t0_{) = λe}−λt0

. In questo caso quindi l'agente raggiungerà il suo obiettivo eseguendo l'azione tale che

arg max a∈A X s0_∈S P (s0, s, a) Z t 0 p(t0)((V_s∗0(t − t0) + R(s, a, s0))dt0)

Un'altra novità di questo algoritmo è data dal fatto che le funzioni d'util- ità Vn

s sono del tipo piecewise Gamma (PWG), cioè funzioni Gamma a tratti,

e sono rappresentate con il simbolo Υs; l'uso di questo tipo di funzioni sarà

ora mostrato nel caso in cui si cerchi di valutare delle Policy Incondizionate, cioè tali per cui la scelta dell'azione non dipende dal tempo corrente.

Si assuma che le transizioni tra i vari stati s1, ..., sn siano deterministiche;

sia ri il reward accumulato dall'agente nel caso si esegua ai rispettando la

deadline e si denoti con il simbolo 3 l'operazione di convoluzione, tale che (p3Vs)(t) =

Rt

0 p(t−y)Vs(y)dy, e quindi (p3ri)(t)= R t

quindi l'equazione di Bellman associata cercando di srotolarla partendo dallo stato iniziale s1: V_sn−1₁ = p3r1+ p3Vsn−22 = p3r1+ p3p3r2+ p3Vsn−33 = . . . = p3r1+ p3p3r2+ · · · + p3 . . . 3p | {z } n−1 3rn−1

Poiché p3 . . . 3p risulta essere molto simile alla funzione Gamma incom- pleta di Eulero, per una qualche costante c avremo che:

(p3 . . . 3p | {z } n 3c)(t) = c(1 − e−λt (1 + (λt) 1 1! + · · · + (λt)n−1 (n − 1)!)) Grazie a questa somiglianza possiamo riscrivere Vn−1

s1 in un modo più compatto: V_sn−1₁ = c1− e−λt(c2+ c3(λt) + · · · + cn(λt) n−2 (n−2)!)= Γs1 con [c1, c2, ..., cn]= [P n−1 t=1 ri, Pn−1 t=1 ri, Pn−1 t=2 ri, . . . , Pn−1 t=n−1ri]

Possiamo quindi aermare che Vn−1

s1 risulta formulabile come funzione

PWG con un'unica componente Γs1; quest'ultima inne può esser salvata

sotto forma di vettore del tipo:

Γs1 =        c1 c2 c3 ... cn        =       r1+ r2+ · · · + rn−1 r1+ r2+ · · · + rn−1 r2+ · · · + rn−1 . . . rn−1      

Grazie alle nozioni appena presentate è possibile creare una procedura ricorsi- va molto veloce che ricava le funzioni d'utilità usando semplici trasformazioni vettoriali, di cui parleremo direttamente all'interno della descrizione specica dell'algoritmo.

Un altro vantaggio di questa procedura è che permette di controllare l'errore di approssimazione in modo da limitarlo al di sotto di una certa soglia voluta dall'utente: questa cosa è possibile perché si può calcolare il minimo numero di iterazioni (n) dell'algoritmo tali da garantire che l'errore

di approssimazione reale sia inferiore l'errore massimo voluto (). La relazione tra questi è espressa come segue:

n∗ ≥ logeλ∆−1 eλ∆



Rmax(eλ∆− 1)

Prima di passare al cuore dell'algoritmo però abbiamo bisogno di pre- sentare un'ulteriore parte, più precisamente un teorema, che sarà fondamen- tale per la descrizione dell'algoritmo iterativo.

Teorema 7. Se Γ = [c1, c2, ..., cn], allora possiamo associare alla funzione

p3Γ il vettore dei coecienti (p3Γ) = [c1, c2, ..., cn].

Possiamo ora iniziare a descrivere l'algoritmo caratterizzante l'approccio CPH. Questo inizia ricevendo in ingresso sia la struttura del problema MDP continuo sia il livello d'errore d'approssimazione  tollerato dall'utente, poi lancia una funzione che calcola il valore di λ che uniformerà le transizioni con funzioni di probabilità esponenziali ed un'altra funzione che determina il valore n∗ _{di iterazioni minime per garantire che sia rispettato il vincolo}

sull'errore di approssimazione.

Dopo questi passaggi, e superata una fase di preparazione di dati e tem- plate, si passa al cuore dell'algoritmo, dove è implementato il metodo di calcolo del valore delle funzioni d'utilità formulato tramite programmazione dinamica, diviso in 3 passaggi principali. Sapendo che, per costruzione prima derivata, Vn

s sarà composto da segmenti Γs,i|i∈Is, si imposteranno i segmenti

Γs,i|i∈Is relativi a V

n+1

s attraverso i seguenti tre passaggi:

1. per ogni intervallo, si aggiungono le funzioni d'utilità convolute future tramite la tecnica vista nel Teorema 7, tali che:

Γs,i←− [Γs,i[1] | Γs,i]

dove [A|B] indica la concatenazione di A e B, e Γs,i[1]accede al primo

coeciente c1 di Γs,i.

2. Per tutti gli intervalli con i > 1 si aggiunge a Γs,iun valore di breakpoint

regolarizzante per l'i-esimo intervallo; Γs,isarà quindi modicata come

segue:

Γs,i←− Γs,i− [0, constant, 0, . . . , 0].

3. Inne per ogni intervallo si aggiunge p3r; grazie al Teorema 7 avremo che (p3r) = [r, r], quindi esprimeremo quanto segue:

Per concludere la trattazione si può dire che, oltre alle varie proprietà dell'algoritmo già presentate, le prove sperimentali mostrano che si ha un miglioramento prestazionale dei tempi di computazione pari ad un paio di ordini di grandezza rispetto al metodo di Lazy Approximation.