Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Impara Equazioni di Bellman | Programmazione Dinamica
Introduzione al Reinforcement Learning

bookEquazioni di Bellman

Note
Definizione

Un'equazione di Bellman è un'equazione funzionale che definisce una funzione di valore in forma ricorsiva.

Per chiarire la definizione:

  • Un'equazione funzionale è un'equazione la cui soluzione è una funzione. Per l'equazione di Bellman, questa soluzione è la funzione di valore per cui l'equazione è stata formulata;
  • Una forma ricorsiva significa che il valore nello stato attuale è espresso in termini di valori negli stati futuri.

In breve, risolvere l'equazione di Bellman fornisce la funzione di valore desiderata e derivare questa equazione richiede l'identificazione di una relazione ricorsiva tra stati attuali e futuri.

Funzione di valore dello stato

Come promemoria, ecco una funzione di valore di stato in forma compatta:

vπ(s)=E⁡π[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

Per ottenere l'equazione di Bellman per questa funzione di valore, espandiamo il lato destro dell'equazione e definiamo una relazione ricorsiva:

vπ(s)=E⁡π[Gt∣St=s]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s]=E⁡π[Rt+1+γGt+1∣St=s]=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &= \E_\pi[G_t | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s]\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

L'ultima equazione di questa catena è un'equazione di Bellman per la funzione di valore di stato.

Intuizione

Per determinare il valore di uno stato ss, occorre:

  1. Considerare tutte le possibili azioni aa che si possono intraprendere da questo stato, ciascuna ponderata in base alla probabilità di scelta secondo la politica corrente π(a∣s)\pi(a | s);
  2. Per ogni azione aa, considerare tutti i possibili stati successivi s′s' e ricompense rr, ponderati in base alla loro probabilità p(s′,r∣s,a)p(s', r | s, a);
  3. Per ciascuno di questi esiti, sommare la ricompensa immediata rr ottenuta più il valore scontato dello stato successivo γvπ(s′)\gamma v_\pi(s').

Sommando tutte queste possibilità si ottiene il valore atteso totale dello stato ss secondo la politica corrente.

Funzione di valore d'azione

Ecco una funzione di valore d'azione in forma compatta:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_\pi(s, a) = \E_\pi[G_t | S_t = s, A_t = a]

La derivazione dell'equazione di Bellman per questa funzione è abbastanza simile a quella precedente:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s,At=a]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s,At=a]=E⁡π[Rt+1+γGt+1∣St=s,At=a]=∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)(E⁡π[Gt+1∣St+1=s′,At+1=a′]))=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)q(s′,a′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} q_\pi(s, a) &= \E_\pi[G_t | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') \Bigl(\E_\pi\Bigl[G_{t+1} | S_{t+1} = s', A_{t+1} = a'\Bigr]\Bigr)\Biggr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') q(s', a')\Biggr) \end{aligned}

L'ultima equazione di questa catena è un'equazione di Bellman per la funzione di valore d'azione.

Intuizione

Per trovare il valore di una coppia stato-azione (s,a)(s, a), occorre:

  1. Considerare tutti i possibili stati successivi s′s' e ricompense rr, pesati in base alla loro probabilità p(s′,r∣s,a)p(s', r | s, a);
  2. Per ciascuno di questi esiti, sommare la ricompensa immediata rr ottenuta più il valore scontato dello stato successivo;
  3. Per calcolare il valore dello stato successivo s′s', per tutte le azioni a′a' possibili dallo stato s′s', moltiplicare il valore dell'azione q(s′,a′)q(s', a') per la probabilità di scegliere a′a' nello stato s′s' secondo la politica attuale π(a′∣s′\pi(a' | s'. Infine, sommare tutto per ottenere il valore finale.

Sommando tutte queste possibilità, si ottiene il valore atteso totale della coppia stato-azione (s,a)(s, a) sotto la politica attuale.

question mark

Quale delle seguenti descrive meglio la funzione dell'equazione di Bellman?

Select the correct answer

Tutto è chiaro?

Come possiamo migliorarlo?

Grazie per i tuoi commenti!

Sezione 3. Capitolo 2

Chieda ad AI

expand

Chieda ad AI

ChatGPT

Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione

Awesome!

Completion rate improved to 2.7

bookEquazioni di Bellman

Scorri per mostrare il menu

Note
Definizione

Un'equazione di Bellman è un'equazione funzionale che definisce una funzione di valore in forma ricorsiva.

Per chiarire la definizione:

  • Un'equazione funzionale è un'equazione la cui soluzione è una funzione. Per l'equazione di Bellman, questa soluzione è la funzione di valore per cui l'equazione è stata formulata;
  • Una forma ricorsiva significa che il valore nello stato attuale è espresso in termini di valori negli stati futuri.

In breve, risolvere l'equazione di Bellman fornisce la funzione di valore desiderata e derivare questa equazione richiede l'identificazione di una relazione ricorsiva tra stati attuali e futuri.

Funzione di valore dello stato

Come promemoria, ecco una funzione di valore di stato in forma compatta:

vπ(s)=E⁡π[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

Per ottenere l'equazione di Bellman per questa funzione di valore, espandiamo il lato destro dell'equazione e definiamo una relazione ricorsiva:

vπ(s)=E⁡π[Gt∣St=s]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s]=E⁡π[Rt+1+γGt+1∣St=s]=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑aπ(a∣s)∑s′,rp(s′,r∣s,a)(r+γvπ(s′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &= \E_\pi[G_t | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s]\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_a \pi(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_\pi(s')\Bigr) \end{aligned}

L'ultima equazione di questa catena è un'equazione di Bellman per la funzione di valore di stato.

Intuizione

Per determinare il valore di uno stato ss, occorre:

  1. Considerare tutte le possibili azioni aa che si possono intraprendere da questo stato, ciascuna ponderata in base alla probabilità di scelta secondo la politica corrente π(a∣s)\pi(a | s);
  2. Per ogni azione aa, considerare tutti i possibili stati successivi s′s' e ricompense rr, ponderati in base alla loro probabilità p(s′,r∣s,a)p(s', r | s, a);
  3. Per ciascuno di questi esiti, sommare la ricompensa immediata rr ottenuta più il valore scontato dello stato successivo γvπ(s′)\gamma v_\pi(s').

Sommando tutte queste possibilità si ottiene il valore atteso totale dello stato ss secondo la politica corrente.

Funzione di valore d'azione

Ecco una funzione di valore d'azione in forma compatta:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_\pi(s, a) = \E_\pi[G_t | S_t = s, A_t = a]

La derivazione dell'equazione di Bellman per questa funzione è abbastanza simile a quella precedente:

qπ(s,a)=E⁡π[Gt∣St=s,At=a]=E⁡π[Rt+1+γRt+2+γ2Rt+3+...∣St=s,At=a]=E⁡π[Rt+1+γ∑k=0∞γkRt+k+2∣St=s,At=a]=E⁡π[Rt+1+γGt+1∣St=s,At=a]=∑s′,rp(s′,r∣s,a)(r+γE⁡π[Gt+1∣St+1=s′])=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)(E⁡π[Gt+1∣St+1=s′,At+1=a′]))=∑s′,rp(s′,r∣s,a)(r+γ∑a′π(a′∣s′)q(s′,a′))\def\E{\operatorname{\mathbb{E}}} \begin{aligned} q_\pi(s, a) &= \E_\pi[G_t | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma \sum_{k=0}^\infty \gamma^k R_{t+k+2} | S_t = s, A_t = a]\\ &= \E_\pi[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \E_\pi\Bigl[G_{t+1} | S_{t+1} = s'\Bigr]\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') \Bigl(\E_\pi\Bigl[G_{t+1} | S_{t+1} = s', A_{t+1} = a'\Bigr]\Bigr)\Biggr)\\ &= \sum_{s', r} p(s', r | s, a)\Biggl(r + \gamma \sum_{a'} \pi(a' | s') q(s', a')\Biggr) \end{aligned}

L'ultima equazione di questa catena è un'equazione di Bellman per la funzione di valore d'azione.

Intuizione

Per trovare il valore di una coppia stato-azione (s,a)(s, a), occorre:

  1. Considerare tutti i possibili stati successivi s′s' e ricompense rr, pesati in base alla loro probabilità p(s′,r∣s,a)p(s', r | s, a);
  2. Per ciascuno di questi esiti, sommare la ricompensa immediata rr ottenuta più il valore scontato dello stato successivo;
  3. Per calcolare il valore dello stato successivo s′s', per tutte le azioni a′a' possibili dallo stato s′s', moltiplicare il valore dell'azione q(s′,a′)q(s', a') per la probabilità di scegliere a′a' nello stato s′s' secondo la politica attuale π(a′∣s′\pi(a' | s'. Infine, sommare tutto per ottenere il valore finale.

Sommando tutte queste possibilità, si ottiene il valore atteso totale della coppia stato-azione (s,a)(s, a) sotto la politica attuale.

question mark

Quale delle seguenti descrive meglio la funzione dell'equazione di Bellman?

Select the correct answer

Tutto è chiaro?

Come possiamo migliorarlo?

Grazie per i tuoi commenti!

Sezione 3. Capitolo 2
some-alt