Vi anser dynamiken i en linjär stokastisk approximationsalgoritm driven av markoviskt brus, och härleda ändliga tidsbegränsningar på ögonblicken av felet, dvs avvikelse av algoritmens utgång från jämviktspunkten i en associerad vanlig differentialekvation (ODE). Vi får ändliga tidsbegränsningar på medel-kvadrat fel i fallet med konstant steg-storlek algoritmer genom att överväga drift av en lämpligt vald Lyapunov funktion. Lyapunov-funktionen kan tolkas antingen i termer av Steins metod för att erhålla gränser för steady-state-prestanda eller i termer av Lyapunov-stabilitetsteori för linjära ODE. Vi ger också en omfattande behandling av ögonblicken i kvadraten av 2-normen av approximation fel. Vår analys ger följande resultat: (i) för en given steg-storlek, visar vi att de lägre-ordning stunder kan göras små som en funktion av steg-storlek och kan vara övre begränsas av ögonblicken i en Gaussian slumpmässig variabel; (ii) vi visar att de högre-ordning ögonblicken bortom en tröskel kan vara oändliga i steady-state; och (iii) vi karakteriserar antalet prover som behövs för att de finita-tidsgränserna ska vara i samma ordning som steady-state gränser. Som en biprodukt av vår analys, löser vi också det öppna problemet med att erhålla ändliga tidsbegränsningar för utförandet av temporal skillnad lärande algoritmer med linjär funktion approximation och en konstant steg-storlek, utan att kräva en projektion steg eller en i.i.d.. bullerförutsättningar.
På senare tid har REF fastställt den ändliga tidskonvergensen för TD-lärande algoritmer med linjär funktion approximation och en konstant stegstorlek utan extra projektion steg under non-i.i.d.
Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}