Mikä on dynaaminen ohjelmointi?

Se on erityisen hyödyllinen vahvistusoppimisessa (RL) Markovin päätösprosessien (MDP) tehokkaaseen ratkaisemiseen, kun ympäristöstä on saatavilla täydellinen malli.

DP:n soveltamisen ehdot

Kaikkia ongelmia ei voida ratkaista DP:llä. Jotta DP toimisi, ongelmalla tulee olla kaksi keskeistä ominaisuutta:

• Optimaalinen osarakenne: optimaalinen ratkaisu ongelmaan muodostuu sen osaratkaisujen optimaalisuudesta. MDP:issä tämä tarkoittaa, että optimaalinen politiikka missä tahansa tilassa riippuu seuraavien tilojen optimaalisista politiikoista. Koska päätökset MDP:ssä ovat peräkkäisiä, pienempien osatehtävien ratkaiseminen (parhaan toiminnon löytäminen tuleville tiloille) johtaa koko ongelman ratkaisemiseen (parhaan toiminnon löytäminen nykyiselle tilalle);
• Päällekkäiset osatehtävät: osatehtävien ratkaisuja käytetään uudelleen suurempien ongelmien ratkaisemiseksi. MDP:issä tämä näkyy siinä, että tilan arvo lasketaan toistuvasti eri päätösjaksoissa. Koska tiloihin palataan usein, aiemmin lasketut arvot voidaan tallentaa ja käyttää uudelleen, mikä vähentää turhaa laskentaa ja parantaa tehokkuutta.

Kuvassa jokainen solmu edustaa rekursiivista kutsua laskea Fib(n), ja puun rakenne näyttää, miten nämä kutsut jaetaan pienempiin osatehtäviin. Huomaa, että osatehtävät kuten Fib(2) ja Fib(1) esiintyvät useita kertoja, mikä havainnollistaa päällekkäisiä osatehtäviä, kun taas ratkaisun Fib(5) muodostuminen perustuu sen osatehtävien optimaalisiin ratkaisuihin, mikä osoittaa optimaalisen osarakenteen. Tämä toisteisuus on juuri se, minkä dynaaminen ohjelmointi pyrkii poistamaan tallentamalla ja hyödyntämällä tuloksia uudelleen.

Koska MDP:t sisältävät sekä optimaalisen osarakenteen että päällekkäiset osatehtävät, ne soveltuvat hyvin DP-pohjaisiin ratkaisuihin.

Miksi käyttää DP:tä RL:ssä?

• Optimaalisuustakuut: DP-menetelmät takaavat konvergenssin optimaaliseen politiikkaan, kun koko malli tunnetaan;
• Tehokkuus yleisissä ratkaisuissa: DP:n avulla yleiset ratkaisut voidaan saavuttaa tehokkaasti, mikä tarkoittaa, että tuloksena oleva politiikka on optimaalinen jokaisessa tilassa;
• Perusta muille menetelmille: DP:n käsitteet toimivat perustana muille RL-menetelmille, kuten Monte Carlo ja temporal difference learning.

DP ei kuitenkaan ole soveltuva suurille ongelmille sen täyden mallin tarpeen ja laskennallisen vaativuuden vuoksi, mikä johtaa seuraavaksi käsiteltäviin haasteisiin.

Dynaamisen ohjelmoinnin haasteet ja rajoitukset

Vaikka DP tarjoaa elegantin viitekehyksen RL-ongelmien ratkaisemiseen, siihen liittyy merkittäviä haasteita, jotka rajoittavat sen sovellettavuutta todellisissa tilanteissa:

• Laskennallinen monimutkaisuus: DP-menetelmät vaativat laskentaa jokaiselle ympäristön tilalle. Kun tila-avaruus kasvaa, tarvittavien laskutoimitusten määrä kasvaa huomattavasti, mikä tekee DP:stä epäkäytännöllisen monimutkaisissa ongelmissa;
• Tunnetun mallin tarve: DP olettaa, että ympäristön siirtymätodennäköisyydet ja palkkiot tunnetaan etukäteen. Kuitenkin monissa todellisissa RL-sovelluksissa tämä tieto ei ole saatavilla, mikä tekee mallittomista lähestymistavoista käytännöllisempiä.