Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lære Bellman-Ligninger | Dynamisk Programmering
Introduktion til Reinforcement Learning

bookBellman-Ligninger

Note
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:

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

For at opnå Bellman-ligningen for denne værdifunktion, udvider vi højresiden af ligningen og etablerer en rekursiv relation:

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}

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

Intuition

For at finde værdien af en tilstand ss:

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

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

Aktionsværdifunktion

Her er en aktionsværdifunktion i kompakt form:

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]

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

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}

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

Intuition

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

  1. Overvej alle mulige næste tilstande s′s' og belønninger rr, vægtet efter deres sandsynlighed p(s′,r∣s,a)p(s', r | s, a);
  2. For hvert af disse udfald tages den umiddelbare belønning rr plus den diskonterede værdi af den næste tilstand;
  3. For at beregne værdien af den næste tilstand s′s', for alle handlinger a′a' mulige fra tilstand s′s', multipliceres handlingsværdien q(s′,a′)q(s', a') med sandsynligheden for at vælge a′a' i tilstand s′s' under den nuværende politik π(a′∣s′)\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)(s, a) under den nuværende politik.

question mark

Hvilket af følgende beskriver bedst funktionen af Bellman-ligningen?

Select the correct answer

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 3. Kapitel 2

Spørg AI

expand

Spørg AI

ChatGPT

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

Awesome!

Completion rate improved to 2.7

bookBellman-Ligninger

Stryg for at vise menuen

Note
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:

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

For at opnå Bellman-ligningen for denne værdifunktion, udvider vi højresiden af ligningen og etablerer en rekursiv relation:

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}

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

Intuition

For at finde værdien af en tilstand ss:

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

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

Aktionsværdifunktion

Her er en aktionsværdifunktion i kompakt form:

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]

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

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}

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

Intuition

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

  1. Overvej alle mulige næste tilstande s′s' og belønninger rr, vægtet efter deres sandsynlighed p(s′,r∣s,a)p(s', r | s, a);
  2. For hvert af disse udfald tages den umiddelbare belønning rr plus den diskonterede værdi af den næste tilstand;
  3. For at beregne værdien af den næste tilstand s′s', for alle handlinger a′a' mulige fra tilstand s′s', multipliceres handlingsværdien q(s′,a′)q(s', a') med sandsynligheden for at vælge a′a' i tilstand s′s' under den nuværende politik π(a′∣s′)\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)(s, a) under den nuværende politik.

question mark

Hvilket af følgende beskriver bedst funktionen af Bellman-ligningen?

Select the correct answer

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 3. Kapitel 2
some-alt