Antakelsen om utforskende start er nyttig for å sikre at alle tilstander (tilstand-handlingspar) blir besøkt over tid. I de fleste reelle oppgaver har dette imidlertid en betydelig ulempe: det krever en modell for å initialisere agenten i vilkårlige tilstander.

I sjeldne tilfeller — når miljøet naturlig starter episoder fra tilfeldige tilstander som dekker hele tilstandsrommet — kan utforskende start brukes uten problemer. Men oftere har oppgaver et fast eller begrenset sett med starttilstander, noe som gjør slik randomisering umulig uten en delvis modell. Denne modellen må i det minste kunne simulere ett steg av miljøet fra en hvilken som helst tilstand. Selv om dette fortsatt er mindre krevende enn å trenge en full modell, er det ofte upraktisk.

Alternative utforskingsmetoder

Hvis det ikke er mulig å starte fra en tilfeldig tilstand (tilstand-handlingspar), er alternativet å sikre at hver handling har en ikke-null sannsynlighet for å bli valgt i hver tilstand. Dette garanterer at agenten over tid vil utforske alle tilgjengelige deler av tilstandsrommet. Hvis en tilstand kan nås gjennom en gyldig sekvens av handlinger, vil den til slutt bli besøkt; og hvis den ikke kan nås i det hele tatt under miljøets dynamikk, er den irrelevant for læringsprosessen.

Denne ideen fører til bruk av stokastiske strategier, der agenten ikke alltid velger den beste kjente handlingen, men i stedet velger handlinger med en viss grad av tilfeldighet. En vanlig strategi for dette er den velkjente $\varepsilon$-grådige strategien, som velger den grådige handlingen mesteparten av tiden, men med sannsynlighet $\varepsilon$ velger en tilfeldig handling i stedet. Dette sikrer kontinuerlig utforskning samtidig som handlinger med høy verdi foretrekkes.

På dette tidspunktet er det også nyttig å skille mellom to hovedklasser av metoder:

• On-policy-metoder evaluerer og forbedrer den samme strategien som brukes til å generere dataene;
• Off-policy-metoder evaluerer og forbedrer én strategi, og genererer dataene med en annen strategi.