Het is bijzonder nuttig in reinforcement learning (RL) voor het efficiënt oplossen van Markov-beslissingsprocessen (MDP's) wanneer een volledig model van de omgeving beschikbaar is.

Voorwaarden voor het toepassen van DP

Niet elk probleem kan met DP worden opgelost. Er zijn twee belangrijke eigenschappen waaraan een probleem moet voldoen om DP toe te kunnen passen:

• Optimale substructuur: de optimale oplossing voor een probleem wordt afgeleid uit de optimale oplossingen van de deelproblemen. In MDP's betekent dit dat het optimale beleid in een bepaalde toestand afhankelijk is van de optimale beleidskeuzes in de volgende toestanden. Omdat beslissingen in een MDP sequentieel zijn, leidt het oplossen van kleinere deelproblemen (het vinden van de beste actie voor toekomstige toestanden) tot het oplossen van het totale probleem (het vinden van de beste actie voor de huidige toestand);
• Overlappende deelproblemen: oplossingen voor deelproblemen worden hergebruikt om grotere problemen op te lossen. In MDP's is dit duidelijk omdat de waarde van een toestand herhaaldelijk wordt berekend in verschillende beslissingsreeksen. Omdat toestanden vaak opnieuw worden bezocht, kunnen eerder berekende waarden worden opgeslagen en hergebruikt, waardoor dubbele berekeningen worden verminderd en de efficiëntie toeneemt.

Elke knoop op de afbeelding stelt een recursieve aanroep voor om Fib(n) te berekenen, en de boomstructuur laat zien hoe deze aanroepen worden opgesplitst in kleinere deelproblemen. Merk op dat deelproblemen zoals Fib(2) en Fib(1) meerdere keren voorkomen, wat overlappende deelproblemen aantoont, terwijl de oplossing voor Fib(5) is opgebouwd uit de optimale oplossingen van de deelproblemen, wat optimale substructuur illustreert. Deze redundantie is precies wat dynamisch programmeren probeert te elimineren door resultaten op te slaan en te hergebruiken.

Omdat MDP's zowel optimale substructuur als overlappende deelproblemen vertonen, zijn ze zeer geschikt voor DP-gebaseerde oplossingen.

Waarom DP gebruiken in RL?

• Optimaliteitsgaranties: DP-methoden zijn gegarandeerd convergent naar het optimale beleid wanneer het volledige model bekend is;
• Efficiëntie voor algemene oplossingen: met behulp van DP kunnen algemene oplossingen efficiënt worden verkregen, wat betekent dat het resulterende beleid optimaal zal zijn voor elke afzonderlijke toestand;
• Fundamenteel voor andere methoden: concepten uit DP vormen de basis voor andere RL-methoden, zoals Monte Carlo en temporal difference learning.

DP is echter niet haalbaar voor grootschalige problemen vanwege de afhankelijkheid van een volledig model en de hoge computationele eisen, wat leidt tot de uitdagingen die hierna worden besproken.

Uitdagingen en beperkingen van Dynamic Programming

Hoewel DP een elegant raamwerk biedt voor het oplossen van RL-problemen, brengt het aanzienlijke uitdagingen met zich mee die de toepasbaarheid in praktijksituaties beperken:

• Computationele complexiteit: DP-methoden vereisen berekeningen voor elke afzonderlijke toestand in een omgeving. Naarmate de toestandsruimte toeneemt, groeit het aantal benodigde berekeningen aanzienlijk, waardoor DP onpraktisch wordt voor complexe problemen;
• Noodzaak van een bekend model: DP gaat ervan uit dat de overgangswaarschijnlijkheden en beloningen van de omgeving vooraf bekend zijn. In veel realistische RL-toepassingen is deze informatie echter niet beschikbaar, waardoor modelvrije benaderingen praktischer zijn.