Początkowa ignorancja agentów wyszukiwania online daje kilka możliwości uczenia się. Po pierwsze, agenci uczą się „mapy” środowiska – a dokładniej wyniku każdego działania w każdym stanie – po prostu przez rejestrowanie każdego ze swoich doświadczeń. Po drugie, lokalni agenci wyszukiwania uzyskują dokładniejsze oszacowania kosztów każdego stanu za pomocą lokalnych reguł aktualizacji, jak w LRTA*. Pokazujemy, że te aktualizacje ostatecznie zbiegają się do dokładnych wartości dla każdego stanu, pod warunkiem, że agent we właściwy sposób eksploruje przestrzeń stanów. Gdy znane są dokładne wartości, optymalne decyzje można podejmować po prostu, przechodząc do następcy o najniższych kosztach — to znaczy, że czysta wspinaczka górska jest wówczas optymalną strategią. Jeśli zastosowałeś się do naszej sugestii, aby prześledzić zachowanie ONLINE-DFS-AGENT w środowisku z rysunku 4.19, zauważysz, że agent nie jest zbyt jasny. Na przykład, po zobaczeniu, że akcja W górę przechodzi od (1,1) do (1,2), agent nadal nie ma pojęcia, że akcja W dół wraca do (1,1) lub że akcja W górę również przechodzi od (2,1) do (2,2), od (2,2) do (2,3) i tak dalej. Ogólnie rzecz biorąc, chcielibyśmy, aby agent dowiedział się, że Up zwiększa współrzędną -, chyba że na drodze jest ściana, że Down ją zmniejsza i tak dalej. Aby tak się stało, potrzebujemy dwóch rzeczy. Po pierwsze, potrzebujemy formalnej i wyraźnie manipulowalnej reprezentacji tego rodzaju ogólnych reguł; do tej pory ukrywaliśmy informacje w czarnej skrzynce zwanej funkcją RESULT. Temu zagadnieniu poświęcone są rozdziały od 8 do 11. Po drugie, potrzebujemy algorytmów, które potrafią skonstruować odpowiednie reguły ogólne na podstawie konkretnych obserwacji dokonanych przez agenta. Zostały one omówione później. Jeśli przewidujemy, że będziemy wezwani do rozwiązania wielu podobnych problemów w przyszłości, warto zainwestować czas (i pamięć), aby ułatwić te przyszłe poszukiwania.
Można to zrobić na kilka sposobów, z których wszystkie należą do kategorii wyszukiwania przyrostowego. Moglibyśmy zachować drzewo wyszukiwania w pamięci i ponownie wykorzystać jego niezmienione części w nowym problemie. Moglibyśmy zachować heurystyczne wartości h i aktualizować je w miarę zdobywania nowych informacji — albo dlatego, że świat się zmienił, albo dlatego, że obliczyliśmy lepsze oszacowanie. Lub możemy zachować wartości g najlepszej ścieżki, używając ich do złożenia nowego rozwiązania i aktualizując je, gdy świat się zmieni.