Antakelsen om exploring starts er nyttig for å sikre at alle tilstander (tilstand-handlingspar) blir besøkt over tid. I de fleste reelle oppgaver har den imidlertid en betydelig ulempe: den 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 exploring starts 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 bør i det minste være i stand til å 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 utforskningsmetoder

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 policyer, der agenten ikke alltid velger den best kjente handlingen, men i stedet velger handlinger med en viss grad av tilfeldighet. En vanlig strategi for dette er den velkjente $\varepsilon$-grådige policyen, 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 favoriseres.

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

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