Abstract
In recent years, machine learning has become a pivotal field in computer science. This paper introduces a novel method using the K-Nearest Neighbors (KNN) classification algorithm to identify layered boundaries and discover subgoal conditions. By automatically classifying large state spaces, the method achieves significant dimension reduction. These classified subspaces form the basis for structured subtasks, enabling autonomous hierarchical learning. Experimental results demonstrate that this approach improves learning efficiency for agents in complex environments by automating task assignment through environmental interaction. This work provides a framework for selecting effective reinforcement learning algorithms for classification-based task decomposition.
Introduction
Reinforcement Learning (RL) agents typically learn by exploring an environment and receiving rewards. However, as environments scale, they encounter the "curse of dimensionality," where the sheer number of possible states leads to slow convergence. Hierarchical Reinforcement Learning (HRL) addresses this by decomposing complex tasks into smaller, reusable "Options" or macro-actions. Traditionally, these hierarchies required manual definition by human experts. This research focuses on automated subgoal discovery, allowing agents to autonomously partition state spaces and identify transition points (bottlenecks) to improve learning speed.
Methodology
The proposed framework integrates supervised learning, evolutionary computation, and RL to automate hierarchy generation.
State Space Partitioning and Optimization
The core of the approach involves using the KNN algorithm to cluster the state space into distinct regions. To ensure these partitions are optimal, a Genetic Algorithm (GA) is employed to evolve the "centers" of the KNN classification. This evolutionary process selects classification schemes that best capture the underlying structure of the environment.
Automatic Option Generation
Once the state space is partitioned, the boundaries between clusters are identified as subgoals. The system automatically generates "Options"—defined by an entry state set, an internal policy, and a termination condition—to facilitate navigation between these subspaces.
Hierarchical Q-Learning
The agent utilizes these discovered Options within a modified Q-learning framework. This allows for high-level decision-making (e.g., moving between rooms) rather than relying solely on low-level primitive actions, effectively reducing the problem's dimensionality.
Experimental Evaluation
The method was evaluated using the Taxi Problem, a standard RL benchmark. In this environment, a taxi must navigate a grid to pick up a passenger and deliver them to one of four designated locations (R, G, Y, B). Despite the discrete nature of the grid, the combination of taxi and passenger variables creates a state space complex enough to test hierarchical efficiency.
Results
The performance of the proposed method (referred to as Ant-o) was compared against standard Q-learning (Q-Study) and State-Cluster-Classification (SCC).
As shown in the results, the Ant-o algorithm reaches the optimal path in far fewer learning cycles. The "steps to goal" metric drops sharply and stabilizes early, proving that KNN-based partitioning successfully identifies effective subgoals that guide the agent through the environment more efficiently than non-hierarchical methods.
Conclusion and Future Work
This research demonstrates that combining KNN classification with Genetic Algorithms can effectively automate the creation of task hierarchies in RL. While successful, the authors note that the computational cost of KNN and the sensitivity of parameters like $k$ remain challenges. Future work will explore scaling this logic to continuous, high-dimensional spaces and integrating more advanced classifiers like Support Vector Machines or Neural Networks to further enhance accuracy and speed.
Summary updated