Lære Bellman-Ligninger | Dynamisk Programmering

Definition

En Bellman-ligning er en funktionel ligning, der definerer en værdifunktion i rekursiv form.

For at præcisere definitionen:

En funktionel ligning er en ligning, hvis løsning er en funktion. For Bellman-ligningen er denne løsning værdifunktionen, som ligningen er formuleret for;
En rekursiv form betyder, at værdien i den nuværende tilstand udtrykkes ved hjælp af værdier i fremtidige tilstande.

Kort sagt, løsning af Bellman-ligningen giver den ønskede værdifunktion, og udledning af denne ligning kræver identifikation af et rekursivt forhold mellem nuværende og fremtidige tilstande.

Tilstands-værdifunktion

Som en påmindelse er her en tilstandsværdi-funktion i kompakt form:

\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

For at opnå Bellman-ligningen for denne værdifunktion, udvides højresiden af ligningen for at etablere en rekursiv relation:

\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}

Den sidste ligning i denne kæde er en Bellman-ligning for tilstandsværdifunktionen.

Intuition

For at finde værdien af en tilstand $s$ :

Overvej alle mulige handlinger $a$ , der kan udføres fra denne tilstand, vægtet efter sandsynligheden for at vælge denne handling under den nuværende politik $\pi(a | s)$ ;
For hver handling $a$ overvejes alle mulige næste tilstande $s'$ og belønninger $r$ , vægtet efter deres sandsynlighed $p(s', r | s, a)$ ;
For hvert af disse udfald tages den umiddelbare belønning $r$ plus den diskonterede værdi af næste tilstand $\gamma v_\pi(s')$ .

Ved at summere alle disse muligheder opnås den samlede forventede værdi af tilstanden $s$ under den nuværende politik.

Handlingsværdifunktion

Her er en handlingsværdifunktion i kompakt form:

\def\E{\operatorname{\mathbb{E}}} q_\pi(s, a) = \E_\pi[G_t | S_t = s, A_t = a]

Udledningen af Bellman-ligningen for denne funktion ligner meget den foregående:

\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}

Den sidste ligning i denne kæde er en Bellman-ligning for handlingsværdifunktionen.

Intuition

For at finde værdien af et tilstands-handlingspar $(s, a)$ , skal du:

Overveje alle mulige næste tilstande $s'$ og belønninger $r$ , vægtet efter deres sandsynlighed $p(s', r | s, a)$ ;
For hvert af disse udfald tager du den umiddelbare belønning $r$ , du modtager, plus den diskonterede værdi af den næste tilstand;
For at beregne værdien af den næste tilstand $s'$ , for alle handlinger $a'$ mulige fra tilstand $s'$ , multipliceres handlingsværdien $q(s', a')$ med sandsynligheden for at vælge $a'$ i tilstand $s'$ under den nuværende politik $\pi(a' | s'$ . Til sidst summeres alt for at opnå den endelige værdi.

Ved at summere alle disse muligheder sammen opnås den samlede forventede værdi af tilstands-handlingsparret $(s, a)$ under den nuværende politik.

Var alt klart?

Tak for dine kommentarer!

Sektion 3. Kapitel 2

Spørg AI

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Suggested prompts:

Can you explain the difference between the state value function and the action value function?

How does the Bellman equation help in reinforcement learning?

Can you provide a simple example illustrating the Bellman equation?

Awesome!

Completion rate improved to 2.7

Stryg for at vise menuen

Definition

En Bellman-ligning er en funktionel ligning, der definerer en værdifunktion i rekursiv form.

For at præcisere definitionen:

En funktionel ligning er en ligning, hvis løsning er en funktion. For Bellman-ligningen er denne løsning værdifunktionen, som ligningen er formuleret for;
En rekursiv form betyder, at værdien i den nuværende tilstand udtrykkes ved hjælp af værdier i fremtidige tilstande.

Tilstands-værdifunktion

Som en påmindelse er her en tilstandsværdi-funktion i kompakt form:

\def\E{\operatorname{\mathbb{E}}} v_\pi(s) = \E_\pi[G_t | S_t = s]

For at opnå Bellman-ligningen for denne værdifunktion, udvides højresiden af ligningen for at etablere en rekursiv relation:

\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}

Den sidste ligning i denne kæde er en Bellman-ligning for tilstandsværdifunktionen.

Intuition

For at finde værdien af en tilstand $s$ :

Overvej alle mulige handlinger $a$ , der kan udføres fra denne tilstand, vægtet efter sandsynligheden for at vælge denne handling under den nuværende politik $\pi(a | s)$ ;
For hver handling $a$ overvejes alle mulige næste tilstande $s'$ og belønninger $r$ , vægtet efter deres sandsynlighed $p(s', r | s, a)$ ;
For hvert af disse udfald tages den umiddelbare belønning $r$ plus den diskonterede værdi af næste tilstand $\gamma v_\pi(s')$ .

Ved at summere alle disse muligheder opnås den samlede forventede værdi af tilstanden $s$ under den nuværende politik.

Handlingsværdifunktion

Her er en handlingsværdifunktion i kompakt form:

\def\E{\operatorname{\mathbb{E}}} q_\pi(s, a) = \E_\pi[G_t | S_t = s, A_t = a]

Udledningen af Bellman-ligningen for denne funktion ligner meget den foregående:

\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}

Den sidste ligning i denne kæde er en Bellman-ligning for handlingsværdifunktionen.

Intuition

For at finde værdien af et tilstands-handlingspar $(s, a)$ , skal du:

Overveje alle mulige næste tilstande $s'$ og belønninger $r$ , vægtet efter deres sandsynlighed $p(s', r | s, a)$ ;
For hvert af disse udfald tager du den umiddelbare belønning $r$ , du modtager, plus den diskonterede værdi af den næste tilstand;
For at beregne værdien af den næste tilstand $s'$ , for alle handlinger $a'$ mulige fra tilstand $s'$ , multipliceres handlingsværdien $q(s', a')$ med sandsynligheden for at vælge $a'$ i tilstand $s'$ under den nuværende politik $\pi(a' | s'$ . Til sidst summeres alt for at opnå den endelige værdi.

Ved at summere alle disse muligheder sammen opnås den samlede forventede værdi af tilstands-handlingsparret $(s, a)$ under den nuværende politik.

Var alt klart?

Tak for dine kommentarer!

Sektion 3. Kapitel 2