Antagelsen om exploring starts er nyttig for at sikre, at alle tilstande (tilstand-handlingspar) besøges over tid. Dog har den i de fleste virkelige opgaver en væsentlig ulempe: den kræver en model for at initialisere agenten i vilkårlige tilstande.

I sjældne tilfælde — når miljøet naturligt starter episoder fra tilfældige tilstande, der dækker hele tilstandsrum — kan exploring starts anvendes uden problemer. Men oftere har opgaver et fast eller begrænset sæt af starttilstande, hvilket gør sådan randomisering umulig uden en delvis model. Denne model skal som minimum kunne simulere ét skridt af miljøet fra en hvilken som helst tilstand. Selvom dette stadig er mindre krævende end at have brug for en fuld model, er det ofte upraktisk.

Alternative udforskningsmetoder

Hvis det ikke er muligt at starte fra en tilfældig tilstand (tilstand-handlingspar), er alternativet at sikre, at hver handling har en ikke-nul sandsynlighed for at blive valgt i hver tilstand. Dette garanterer, at agenten over tid vil udforske alle tilgængelige dele af tilstandsrum. Hvis en tilstand kan nås gennem en gyldig sekvens af handlinger, vil den før eller siden blive besøgt; og hvis den slet ikke kan nås under miljøets dynamik, er den irrelevant for læringsprocessen.

Denne idé fører til brugen af stokastiske politikker, hvor agenten ikke altid vælger den bedst kendte handling, men i stedet vælger handlinger med en vis grad af tilfældighed. En almindelig strategi for dette er den velkendte $\varepsilon$-grådige politik, som vælger den grådige handling det meste af tiden, men med sandsynlighed $\varepsilon$ vælger en tilfældig handling i stedet. Dette sikrer kontinuerlig udforskning, samtidig med at handlinger med høj værdi favoriseres.

På dette tidspunkt er det også nyttigt at skelne mellem to hovedklasser af metoder:

• On-policy metoder evaluerer og forbedrer den samme politik, som bruges til at generere dataene;
• Off-policy metoder evaluerer og forbedrer én politik, og genererer dataene med en anden politik.