Graph-based chain construction approach to landmark-guided reinforcement learning

Date

2026-8-13

Author

Derinöz, Anıl Erdem

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

27
views

9
downloads

Cite This

Reinforcement Learning (RL) provides a powerful framework for autonomous decision making; however, its real-world applicability is often bottlenecked by the assumption of perfect environmental observability. While Partially Observable Markov Decision Processes (POMDPs) provide a more realistic formulation for these problems, they lead perceptual aliasing which makes long-horizon planning highly unstable for the agent. Landmark-based task decomposition offers a promising solution by utilizing critical environmental waypoints to break complex, global navigation problems into localized, manageable sub-tasks. Despite this, a fundamental challenge persists: once landmarks are identified, determining the optimal sequence to visit them remains mathematically and computationally difficult. Current baseline approaches typically rely on passive, stochastic random walks to build transitional associations. This passive methodology artificially restricts topological discovery, struggles with stochastic sparsity, and suffers from reward agnosticism, fundamentally failing to capture optimal trajectories. To overcome these limitations, this thesis introduces Graph-Based Chain Construction (GBCC), a novel hierarchical decomposition framework that shifts the learning paradigm from passive association to active, concurrent exploration. Rather than relying on a single agent's random walk, GBCC dynamically spawns a swarm of goal-conditioned sub-agents at each discovered landmark, effectively transforming the global exploration burden into localized sub-tasks. These agents systematically construct a directed, value-embedded reachability graph of the environment. Comprehensive empirical evaluations in complex grid-world domains demonstrate that GBCC significantly outperforms existing benchmark methods. The proposed framework achieves complete and robust topological coverage in dense connectivity scenarios, successfully identifying optimal, high-yield paths while managing computational trade-offs, thereby establishing a highly scalable approach.

Subject Keywords

Partially observable markov decision processes, Reinforcement learning, Graph-based chain construction, Task decomposition

URI

https://hdl.handle.net/11511/121027

Collections

Graduate School of Natural and Applied Sciences, Thesis