Po każdej akcji agent online w obserwowalnym środowisku otrzymuje percept informujący go, jaki stan osiągnął; na podstawie tych informacji może uzupełnić swoją mapę środowiska. Zaktualizowana mapa jest następnie wykorzystywana do planowania dalszych kroków. To przeplatanie się planowania i działania oznacza, że algorytmy wyszukiwania online różnią się znacznie od algorytmów wyszukiwania offline, które widzieliśmy wcześniej: algorytmy offline eksplorują swój model przestrzeni stanów, podczas gdy algorytmy online eksplorują świat rzeczywisty. Na przykład A* może rozwinąć węzeł w jednej części przestrzeni, a następnie natychmiast rozwinąć węzeł w odległej części przestrzeni, ponieważ rozwinięcie węzła obejmuje działania symulowane, a nie rzeczywiste. Z drugiej strony algorytm online może odkryć następców tylko dla stanu, który fizycznie zajmuje. Aby uniknąć podróżowania aż do stanu odległego w celu rozszerzenia następnego węzła, wydaje się, że lepiej jest rozszerzać węzły w kolejności lokalnej. Wyszukiwanie według głębokości ma dokładnie tę właściwość, ponieważ (z wyjątkiem sytuacji, gdy algorytm cofa) następny rozwinięty węzeł jest potomkiem poprzedniego rozwiniętego węzła. Internetowy agent eksploracji w głąb (dla deterministycznych, ale nieznanych działań) pokazano na rysunku. Ten agent przechowuje swoją mapę w tabeli result[s,a], która rejestruje stan wynikający z wykonania akcji w state s. (W przypadku działań niedeterministycznych agent może zarejestrować zestaw stanów w wyniku[s,a].) Zawsze, gdy bieżący stan zawiera niezbadane działania, agent próbuje wykonać jedną z nich. Trudność pojawia się, gdy agent wypróbował wszystkie działania w stanie. W trybie wyszukiwania głębokiego offline stan jest po prostu usuwany z kolejki; w wyszukiwarce online agent musi cofnąć się do świata fizycznego. W wyszukiwaniu dogłębnym oznacza to powrót do stanu, z którego agent ostatnio wszedł w obecny stan. Aby to osiągnąć, algorytm przechowuje kolejną tabelę, która dla każdego stanu zawiera poprzednie stany, do których agent jeszcze się nie cofnął. Jeśli agentowi zabrakło stanów, do których może się cofnąć, wyszukiwanie jest zakończone.
Zalecamy czytelnikowi prześledzenie postępu ONLINE-DFS-AGENT po zastosowaniu go w labiryncie przedstawionym na rysunku powyżej. Dość łatwo zauważyć, że w najgorszym przypadku agent przejdzie przez każde łącze w przestrzeni stanów dokładnie dwa razy. W przypadku eksploracji jest to optymalne; z drugiej strony, jeśli chodzi o znalezienie celu, współczynnik konkurencyjności agenta może być arbitralnie zły, jeśli wyrusza na długą wycieczkę, gdy cel znajduje się tuż obok stanu początkowego. Internetowy wariant pogłębiania iteracyjnego rozwiązuje ten problem; dla środowiska, które jest drzewem jednorodnym, stosunek konkurencyjności takiego agenta jest małą stałą. Ze względu na metodę cofania, ONLINE-DFS-AGENT działa tylko w przestrzeniach stanów, w których akcje są odwracalne. Istnieją nieco bardziej złożone algorytmy, które działają w ogólnych przestrzeniach stanów, ale żaden taki algorytm nie ma ograniczonego współczynnika konkurencyjności.