Lære Optimalitetsbetingelser | Dynamisk Programmering

Stryg for at vise menuen

I det forrige kapitel lærte du om Bellman-ligninger for tilstandsværdi- og tilstands-handlingsværdi-funktioner. Disse ligninger beskriver, hvordan tilstandsværdier kan defineres rekursivt gennem værdierne af andre tilstande, hvor værdierne afhænger af en given politik. Dog er ikke alle politikker lige effektive. Faktisk giver værdifunktioner en delvis orden for politikker, som kan beskrives således:

\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Så politik $\pi$ er bedre end eller lig med politik $\pi'$ , hvis den forventede gevinst for politik $\pi$ ikke er mindre end den forventede gevinst for politik $\pi'$ for alle mulige tilstande.

Studér mere

En delvis orden følger de sædvanlige ordensregler, men kræver ikke, at alle par sammenlignes. I vores tilfælde kan vi kun rangere to politikker, hvis de giver samme resultat, eller hvis den ene tydeligt overgår den anden. I alle andre tilfælde forbliver politikker ukomparable.

Optimal politik

Definition

For enhver MDP findes der mindst én politik, der er lige så god som eller bedre end alle andre politikker. Denne politik kaldes en optimal politik $\pi_*$ . Selvom der kan være mange optimale politikker, betegnes de alle som $\pi_*$ .

Hvorfor eksisterer en optimal politik altid?

Du undrer dig måske over, hvorfor en optimal politik altid eksisterer for enhver MDP. Det er et godt spørgsmål, og intuitionen bag er overraskende enkel. Husk, at tilstande i en MDP fuldstændigt afspejler miljøets tilstand. Dette indebærer, at hver tilstand er uafhængig af alle andre: handlingen valgt i én tilstand påvirker ikke de belønninger eller resultater, der kan opnås i en anden. Derfor, ved at vælge den optimale handling i hver tilstand separat, opnås naturligt den samlet bedste rækkefølge af handlinger gennem hele processen. Og dette sæt af optimale handlinger i hver tilstand udgør en optimal politik.

Derudover findes der altid mindst én politik, der både er optimal og deterministisk. Faktisk, hvis der for en tilstand $s$ er to handlinger $a$ og $a'$ , der giver samme forventede udbytte, vil det ikke påvirke politikkens optimalitet at vælge blot én af dem. Anvendes dette princip på hver enkelt tilstand, bliver politikken deterministisk samtidig med, at dens optimalitet bevares.

Optimale værdifunktioner

Optimale politikker deler de samme værdifunktioner — dette bliver tydeligt, når vi overvejer, hvordan politikker sammenlignes. Det betyder, at optimale politikker deler både tilstandsværdifunktion og aktionsværdifunktion.

Derudover har optimale værdifunktioner deres egne Bellman-ligninger, som kan skrives uden reference til en specifik politik. Disse ligninger kaldes Bellman-optimalitetsligninger.

Optimal tilstandsværdifunktion

Definition

Optimal tilstandsværdifunktion $V_*$ (eller $v_*$ ) repræsenterer den maksimale forventede belønning, der kan opnås fra en given tilstand ved at følge en optimal politik.

Det kan matematisk defineres således:

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

Bellmans optimalitetsligning for denne værdifunktion kan udledes således:

\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuition

Som du allerede ved, findes der altid mindst én politik, der er både optimal og deterministisk. En sådan politik vil for hver tilstand konsekvent vælge én bestemt handling, der maksimerer den forventede belønning. Derfor vil sandsynligheden for at vælge denne optimale handling altid være 1, og sandsynligheden for at vælge enhver anden handling vil være 0. Givet dette behøver den oprindelige Bellman-ligning ikke længere summationstegnet. I stedet, da vi ved, at vi altid vælger den bedst mulige handling, kan vi blot erstatte summen med at tage et maksimum over alle tilgængelige handlinger.

Optimal handlingsværdifunktion

Definition

Optimal action value function $Q_*$ (eller $q_*$ ) repræsenterer den maksimale forventede belønning, der kan opnås ved at tage en bestemt handling i en bestemt tilstand og derefter følge den optimale politik.

Det kan matematisk defineres således:

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

Bellmans optimalitetsligning for denne værdifunktion kan udledes således:

\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuition

På samme måde som tilstandsværdifunktionen kan summen erstattes med at tage maksimum over alle tilgængelige handlinger.

Var alt klart?

Tak for dine kommentarer!

Sektion 3. Kapitel 3

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

Sektion 3. Kapitel 3