TD(0): Værdifunktionsestimering

Den simpleste version af TD-læring kaldes TD(0). Den opdaterer værdien af en tilstand baseret på den umiddelbare belønning og den estimerede værdi af den næste tilstand. Det er en ét-trins TD-metode.

Opdateringsregel

Givet en tilstand $S_t$ , belønning $R_{t+1}$ og næste tilstand $S_{t+1}$ , ser opdateringsreglen således ud:

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

hvor

$\alpha$ er en læringsrate eller skridtlængde;
$\delta_t = R_{t+1}+\gamma V(S_{t+1}) - V(S_t)$ er en TD-fejl.

Intuition

Tilstandsværdifunktionen $v_\pi$ kan defineres og udvides 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 giver den første del af $\delta_t$ — den oplevede afkast $R_{t+1} + \gamma V(S_{t+1})$ . Og den anden del af $\delta_t$ er det forventede afkast $V(S_t)$ . TD-fejlen $\delta_t$ er derfor den observerbare forskel mellem det, der faktisk skete, og det, vi tidligere troede ville ske. Så opdateringsreglen justerer den tidligere antagelse en smule for hvert trin, så den kommer tættere på sandheden.

TD(0) vs Monte Carlo Estimation

Både TD(0) og Monte Carlo-estimering anvender samplede erfaringer til at estimere tilstands-værdi funktionen $v_\pi(s)$ for en politik $\pi$ . Under standard konvergensbetingelser konvergerer begge til den sande $v_\pi(s)$ , når antallet af besøg til hver tilstand går mod uendelig. I praksis har vi dog kun en begrænset mængde data, og de to metoder adskiller sig væsentligt i, hvordan de anvender disse data, samt hvor hurtigt de lærer.

Bias-Variance Tradeoff

Fra et bias–varians tradeoff-perspektiv:

Monte Carlo-estimering venter, indtil en episode slutter, og bruger derefter den fulde returnering til at opdatere værdier. Dette giver ubiaserede estimater — returneringerne afspejler faktisk den underliggende fordeling — men de kan svinge voldsomt, især i lange eller meget stokastiske opgaver. Høj varians betyder, at mange episoder er nødvendige for at udligne støjen og opnå stabile værdiestimater.

TD(0) anvender bootstrapping ved at kombinere hver ét-trins belønning med det aktuelle estimat af næste tilstands værdi. Dette introducerer bias — tidlige opdateringer er afhængige af ufuldkomne estimater — men holder variansen lav, da hver opdatering er baseret på en lille, inkrementel fejl. Lavere varians gør det muligt for TD(0) at sprede belønningsinformation gennem tilstandsrum hurtigere, selvom indledende bias kan forsinke konvergensen.

Læringsdata vs Læringsmodel

En anden måde at betragte disse to metoder på er at analysere, hvad hver af dem egentlig lærer:

Monte Carlo-estimering lærer direkte fra de observerede returneringer og tilpasser effektivt sine værdiestimater til de specifikke episoder, den har set. Det betyder, at den minimerer fejl på disse træningsforløb, men fordi den aldrig opbygger en eksplicit forståelse af, hvordan tilstande fører til hinanden, kan den have svært ved at generalisere til nye eller lidt forskellige situationer.

TD(0) derimod anvender bootstrapping på hver ét-trins overgang og kombinerer den umiddelbare belønning med sit estimat af næste tilstands værdi. På denne måde opfanger den effektivt relationerne mellem tilstande — en implicit model af miljøets dynamik. Denne model-lignende forståelse gør det muligt for TD(0) at generalisere bedre til usete overgange og giver ofte mere præcise værdiestimater på nye data.