Modellfri förstärkningslära (RL) algoritmer, såsom Q-learning, direkt parameterisera och uppdatera värdefunktioner eller policyer utan att uttryckligen modellera miljön. De är vanligtvis enklare, mer flexibla att använda, och därmed mer utbredda i moderna djupa RL än modellbaserade metoder. Men empiriskt arbete har föreslagit att modellfria algoritmer kan kräva fler prover för att lära [7, 22]. Den teoretiska frågan om "om modellfria algoritmer kan göras proveffektiva" är en av de mest grundläggande frågorna i RL, och förblir olöst även i grundscenariot med ändligt många tillstånd och handlingar. Vi bevisar att Q-learning med UCB-prospektering, i en tillfällig MDP-inställning, leder till ånger O( ❌ H 3 SAT ), där S och A är antalet stater och åtgärder, H är antalet steg per episod, och T är det totala antalet steg. Detta urval effektivitet motsvarar den optimala ånger som kan uppnås genom alla modellbaserade tillvägagångssätt, upp till en enda ε H faktor. Såvitt vi vet är detta den första analysen i den modellfria miljö som etablerar ε T ånger utan att kräva tillgång till en "simulator".
För den tabulära episodiska inställningen med icke-stationär dynamik och inga simulatorer, de bästa ångern som uppnåtts av befintliga modellbaserade och modellfria algoritmer är Õ( ε H 2 SAT ) ( Azar et al., 2017) och Õ( ε H 3 SAT ) REF, respektive, där S är antalet stater, A är antalet åtgärder, H är längden på varje episod, och T är det totala antalet spelade steg.
Is Q-learning Provably Efficient?
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}