Det är särskilt användbart inom förstärkningsinlärning (RL) för att effektivt lösa Markovbeslutsprocesser (MDP) när en fullständig modell av miljön finns tillgänglig.

Villkor för att tillämpa DP

Inte alla problem kan lösas med DP. Det finns två viktiga egenskaper som ett problem måste ha för att DP ska fungera:

• Optimal delstruktur: den optimala lösningen på ett problem härleds från de optimala lösningarna på dess delproblem. I MDP:er innebär detta att den optimala policyn i ett tillstånd beror på de optimala policyerna för efterföljande tillstånd. Eftersom besluten i en MDP är sekventiella leder lösningen av mindre delproblem (att hitta den bästa åtgärden för framtida tillstånd) till att lösa det övergripande problemet (att hitta den bästa åtgärden för det aktuella tillståndet);
• Överlappande delproblem: lösningar på delproblem återanvänds för att lösa större problem. I MDP:er är detta tydligt eftersom värdet av ett tillstånd beräknas upprepade gånger i olika beslutssekvenser. Eftersom tillstånd ofta återbesöks kan tidigare beräknade värden lagras och återanvändas, vilket minskar onödiga beräkningar och förbättrar effektiviteten.

Varje nod på bilden representerar ett rekursivt anrop för att beräkna Fib(n), och trädstrukturen visar hur dessa anrop delas upp i mindre delproblem. Observera att delproblem som Fib(2) och Fib(1) förekommer flera gånger, vilket visar överlappande delproblem, medan lösningen på Fib(5) byggs upp från de optimala lösningarna på dess delproblem, vilket visar optimal delstruktur. Denna redundans är vad dynamisk programmering syftar till att eliminera genom att lagra och återanvända resultat.

Eftersom MDP:er uppvisar både optimal delstruktur och överlappande delproblem är de väl lämpade för DP-baserade lösningar.

Varför använda DP i RL?

• Optimalitetsgarantier: DP-metoder är garanterade att konvergera till den optimala policyn när hela modellen är känd;
• Effektivitet för generella lösningar: med hjälp av DP kan generella lösningar erhållas effektivt, vilket innebär att den resulterande policyn blir optimal för varje enskilt tillstånd;
• Grundläggande för andra metoder: koncept från DP utgör grunden för andra RL-metoder, såsom Monte Carlo och temporal difference learning.

Dock är DP inte genomförbart för storskaliga problem på grund av dess beroende av en fullständig modell och höga beräkningskrav, vilket leder till de utmaningar som diskuteras härnäst.

Utmaningar och begränsningar med dynamisk programmering

Även om DP erbjuder en elegant ram för att lösa RL-problem, medför det betydande utmaningar som begränsar dess användbarhet i verkliga scenarier:

• Beräkningskomplexitet: DP-metoder kräver beräkningar för varje enskilt tillstånd i en miljö. När tillståndsrymden växer ökar antalet nödvändiga beräkningar avsevärt, vilket gör DP opraktiskt för komplexa problem;
• Krav på känd modell: DP förutsätter att miljöns övergångssannolikheter och belöningar är kända i förväg. I många verkliga RL-tillämpningar är denna information dock inte tillgänglig, vilket gör modellfria metoder mer praktiska.