Hierarchical Reinforcement Learning Based on KNN Classification Algorithms

Shanhong Zhu, Weipeng Dong, Wei LiuInternational Journal of Hybrid Information Technology 2015 · DOI

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.

The proposed algorithm flowchart illustrating the iterative process of state observation, option updating, and automated subspace clustering.

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).

Comparison of learning cycles vs. steps to goal. The Ant-o method demonstrates significantly faster convergence and higher efficiency compared to baseline algorithms.

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

Abstract

In recent years, machine learning is increasingly becoming an important field of computer science. A new method using KNN classification algorithm identifies the layered boundary to find subgoal condition, to automatic classifying of large state space, reaches the dimension reduction of state space, and on the basis of generated subspace classifying to structure subtasks, and then realizes the hierarchical learning tasks automatically. In autonomous system, Agent assigns to their task through interaction with the environment, using hierarchical reinforcement learning technology can help the Agent in the large, complex environment to improve learning efficiency. Through the experimental results the effectiveness of the proposed algorithm is demonstrated. The goal of this paper is to provide a basic overview for both specialists and non-specialists to how to decide a good reinforcement learning algorithm for classification.
BibTeX
@article{zhu2015hierarchical,
  author = {Shanhong Zhu and Weipeng Dong and Wei Liu},
  title = {{Hierarchical Reinforcement Learning Based on KNN Classification Algorithms}},
  journal = {International Journal of Hybrid Information Technology},
  year = {2015},
  doi = {10.14257/ijhit.2015.8.8.17},
}
Figure