L'assunzione degli exploring starts è utile per garantire che tutti gli stati (coppie stato-azione) vengano visitati nel tempo. Tuttavia, nella maggior parte dei compiti reali, presenta un notevole svantaggio: richiede un modello per inizializzare l'agente in stati arbitrari.

In rari casi — quando l'ambiente inizia naturalmente gli episodi da stati casuali che coprono l'intero spazio degli stati — gli exploring starts possono essere applicati senza problemi. Più comunemente, però, i compiti hanno un insieme fisso o limitato di stati iniziali, rendendo tale randomizzazione impossibile senza un modello parziale. Questo modello dovrebbe almeno essere in grado di simulare un passo dell'ambiente da qualsiasi stato. Sebbene ciò sia comunque meno impegnativo rispetto alla necessità di un modello completo, spesso risulta poco pratico.

Approcci alternativi all'esplorazione

Se non è possibile iniziare da uno stato casuale (coppia stato-azione), l'alternativa è garantire che ogni azione abbia una probabilità diversa da zero di essere selezionata in ogni stato. Questo assicura che, nel tempo, l'agente esplori tutte le parti raggiungibili dello spazio degli stati. Se uno stato può essere raggiunto tramite una sequenza valida di azioni, prima o poi lo sarà; se invece non può essere raggiunto affatto secondo la dinamica dell'ambiente, allora è irrilevante per il processo di apprendimento.

Questa idea porta all'uso di policy stocastiche, in cui l'agente non sceglie sempre l'azione migliore conosciuta, ma seleziona le azioni con un certo grado di casualità. Una strategia comune per questo è la nota $\varepsilon$-greedy policy, che sceglie l'azione greedy la maggior parte delle volte, ma con probabilità $\varepsilon$ seleziona invece un'azione casuale. Questo garantisce un'esplorazione continua pur privilegiando le azioni di valore elevato.

A questo punto, è anche utile distinguere tra due principali classi di metodi:

• I metodi on-policy valutano e migliorano la stessa policy utilizzata per generare i dati;
• I metodi off-policy valutano e migliorano una policy, e generano i dati con un'altra policy.