TD(0): Verdifunksjonsestimering

Den enkleste versjonen av TD-læring kalles TD(0). Den oppdaterer verdien til en tilstand basert på umiddelbar belønning og estimert verdi for neste tilstand. Dette er en ett-trinns TD-metode.

Oppdateringsregel

Gitt en tilstand $S_t$ , belønning $R_{t+1}$ og neste tilstand $S_{t+1}$ , ser oppdateringsregelen slik ut:

V(S_t) \gets V(S_t) + \alpha\Bigl(R_{t+1}+\gamma V(S_{t+1}) - V(S_t)\Bigr)

hvor

$\alpha$ er læringsrate, eller steglengde;
$\delta_t = R_{t+1}+\gamma V(S_{t+1}) - V(S_t)$ er TD-feil.

Intuisjon

Tilstandsverdifunksjonen $v_\pi$ kan defineres og utvides som følger:

\def\E{\operatorname{\mathbb{E}}} \begin{aligned} v_\pi(s) &= \E_\pi[G_t | S_t = s] \\ &= \E_\pi[R_t + \gamma G_{t+1} | S_t = s] \\ &= \E_\pi[R_t + \gamma v_\pi(S_{t+1}) | S_t = s] \end{aligned}

Dette gir den første delen av $\delta_t$ — den erfarte avkastningen $R_{t+1} + \gamma V(S_{t+1})$ . Og den andre delen av $\delta_t$ er den forventede avkastningen $V(S_t)$ . TD-feilen $\delta_t$ er derfor det observerbare avviket mellom det som faktisk skjedde og det vi tidligere trodde ville skje. Oppdateringsregelen justerer derfor den tidligere antakelsen litt for hvert steg, slik at den kommer nærmere sannheten.

TD(0) vs Monte Carlo-estimering

Både TD(0) og Monte Carlo-estimering bruker samplede erfaringer for å estimere tilstandsverdifunksjonen $v_\pi(s)$ for en politikk $\pi$ . Under standard konvergensbetingelser vil begge konvergere mot den sanne $v_\pi(s)$ når antall besøk til hver tilstand går mot uendelig. I praksis har vi imidlertid kun en begrenset mengde data, og de to metodene skiller seg betydelig fra hverandre i hvordan de bruker disse dataene og hvor raskt de lærer.

Bias-varians-avveining

Fra et bias–varians-avveiningsperspektiv:

Monte Carlo-estimering venter til en episode er ferdig og bruker deretter hele avkastningen til å oppdatere verdiene. Dette gir upartiske estimater — avkastningene gjenspeiler faktisk den underliggende fordelingen — men de kan variere kraftig, spesielt i lange eller svært stokastiske oppgaver. Høy varians betyr at mange episoder kreves for å jevne ut støyen og oppnå stabile verdiestimater.

TD(0) benytter bootstrap ved å kombinere hver ett-trinns belønning med det nåværende estimatet av neste tilstands verdi. Dette introduserer skjevhet — tidlige oppdateringer er avhengige av ufullstendige estimater — men holder variansen lav, siden hver oppdatering er basert på en liten, inkrementell feil. Lavere varians gjør at TD(0) kan spre belønningsinformasjon gjennom tilstandsrommet raskere, selv om innledende skjevhet kan gjøre at konvergensen går saktere.

Lære data vs lære modell

En annen måte å se på disse to metodene er å analysere hva hver av dem faktisk lærer:

Monte Carlo-estimering lærer direkte fra observerte avkastninger, og tilpasser sine verdiestimater til de spesifikke episodene den har sett. Dette betyr at den minimerer feil på disse treningsforløpene, men fordi den aldri bygger et eksplisitt bilde av hvordan tilstander fører til hverandre, kan den ha problemer med å generalisere til nye eller litt forskjellige situasjoner.

TD(0), derimot, benytter bootstrap på hver ett-trinns overgang, og kombinerer den umiddelbare belønningen med sitt estimat av neste tilstands verdi. På denne måten fanger den effektivt opp relasjonene mellom tilstander — en implisitt modell av miljøets dynamikk. Denne modell-lignende forståelsen gjør at TD(0) kan generalisere bedre til ukjente overganger, og gir ofte mer nøyaktige verdiestimater på nye data.