Mehr als Einzel-Schritt-Updates: RL für Heuristiken mit begrenzter Suche
In vielen Aufgaben der sequenziellen Entscheidungsfindung lässt sich das Ziel, von einem Startzustand zu einem Zielzustand zu gelangen, als kürzeste-Pfad-Problem formulieren. Klassische Heuristik-Suchalgorithmen nutzen eine Schätzwertfunktion, die den verbleibenden Aufwand zum Ziel für jeden Zustand angibt.
Neuere Methoden kombinieren Heuristik-Suche mit Reinforcement Learning und lernen die Schätzwertfunktion durch tiefe Approximation der Wertiteration. Dabei werden üblicherweise Einzel-Schritt-Bellman-Updates verwendet, bei denen die Heuristik eines Zustands nur anhand seines besten Nachbarn und der zugehörigen Kantengewichte angepasst wird.
Die vorgestellte Arbeit erweitert diesen Ansatz, indem sie sowohl die Zustandsauswahl als auch die Heuristik-Updates verbessert. Durch begrenzte Suchhorizonte wird jeder Zustand anhand des kürzesten Pfades zum Suchrand aktualisiert, wobei sowohl Kantengewichte als auch die Heuristikwerte der Randzustände berücksichtigt werden. Diese Methode liefert robustere Heuristiken und kann komplexere Entscheidungsprobleme effizienter lösen.