I detta dokument överväger vi den modellfria förstärkningen inlärningsproblem och studera den populära Q-learning algoritm med linjär funktion approximation för att hitta den optimala politiken. Trots dess popularitet är det känt att Q-learning med linjär funktion approximation kan skilja sig i allmänhet på grund av icke-policy provtagning. Vårt huvudsakliga bidrag är att ge en ändlig tidsbegränsning för Q-learning med linjär funktions approximation med konstant stegstorlek enligt ett antagande om provtagningspolicyn. Till skillnad från vissa tidigare arbeten i litteraturen behöver vi inte göra det onaturliga antagandet att proverna är i.i.d. (eftersom de är Markovian), och inte kräver en ytterligare projektion steg i algoritmen. För att visa detta resultat, vi först överväga en mer allmän icke-linjär stokastisk approximation algoritm med markovian brus, och härleda en ändlig tid bunden på medel-kvadrat fel, som vi tror är av oberoende intresse. Vårt bevis är baserat på Lyapunov drift argument och utnyttjar den geometriska blandning av den underliggande Markov kedjan. Vi tillhandahåller också numeriska simuleringar för att illustrera effektiviteten i vårt antagande om urvalspolitiken och visa graden av konvergens när det gäller Q-learning. Föravtryck. Under granskning. Med tanke på Q-lärandets popularitet och framgång har dess prestationer studerats i litteraturen. Den asymptotiska konvergensen av Q-learning har studerats i [29, 12, 27] med martingale-baserad metod, medan konvergenshastigheten har karakteriserats i [8, 25, 2, 9, 7]. Eftersom Q-learning kräver att Q-funktionsvärdena lagras för alla stat-action par, har det begränsats till problem med små tillstånd och aktionsutrymmen, och denna utmaning kallas ofta dimensionalitetens förbannelse i RL. För att övervinna denna nackdel kan vi approximera Q-funktionen genom en parameteriserad funktionsklass med mycket mindre dimension. Q-lärande med funktionstillnärmning kan dock generellt skilja sig [1, 23]. Den främsta orsaken är att Q-learning använder icke-policy provtagning för att samla in data, vilket gör det potentiellt en expansion kartläggning [10, 1]. Av denna anledning, konvergens Q-learning med funktion approximation har begränsats till specialfall, såsom, för optimal stoppa problem [28], eller vid användning av stat aggregering funktioner [4], eller vid användning av icke-parametriska regressionsmetod (nerest granne Q-learning) [19]. I denna uppsats fokuserar vi på att studera Q-learning med linjär funktions approximation [16, 31], där Q-funktionen approximeras av en linjär kombination av en given uppsättning basfunktioner (eller egenskaper). Q-lärande med linjär funktions approximation kan i allmänhet skilja sig åt, vilket illustreras av kontraexemplen i [1, 23]. Vi måste därför införa vissa villkor för provtagningspolitiken för att garantera stabiliteten i denna strategi. Ett sådant villkor föreslogs i [16] för att begränsa provtagningspolitiken så att den ligger tillräckligt nära den optimala politiken. Vi kunde dock inte kontrollera riktigheten i huvudteoremet (Theorem 1) i [16] inte ens efter personlig kommunikation med motsvarande författare. Å andra sidan studerar arbetet i [31] den finita tidsanalysen av Q-learning med linjär funktions approximation. I synnerhet är tillvägagångssättet i [31] främst motiverat av arbetet i [5], där konvergensen i den populära timlig-differentiering inlärningsmetod för att lösa politiska utvärderingsproblem undersöktes. En nackdel med de tekniker som används i [5, 31] är att deras algoritm kräver ytterligare ett projektion steg på en begränsad uppsättning relaterade till den okända stationära fördelningen av den underliggande Markov kedjan. Ett sådant projektion steg som används för att kontrollera storleken på iteraterna är opraktiskt. Vi noterar också att arbetet i [31] bygger på resultatet i [16], av vilka vi inte kunde verifiera riktigheten, som nämnts ovan.
En liknande analys utvidgades också till Q-learning med linjär funktions approximation REF.
Performance of Q-learning with Linear Function Approximation: Stability and Finite-Time Analysis
{'venue': None, 'journal': 'arXiv: Optimization and Control', 'mag_field_of_study': ['Mathematics', 'Computer Science']}