The Hierarchical Discrete Pursuit Learning Automaton: A Novel Scheme With Fast Convergence and Epsilon-Optimality.

Area of Science:

• Artificial Intelligence
• Machine Learning
• Reinforcement Learning

Background:

• Learning automata (LA) have been foundational to reinforcement learning (RL) since the 1960s.
• Previous advancements include probability updating, discretization, the Pursuit concept, and hierarchical structures.
• The hierarchical continuous pursuit LA (HCPA) improved performance for large action sets but faced speed impediments.

Purpose of the Study:

• To introduce a novel hierarchical discretized pursuit LA (HDPA) by integrating existing LA concepts.
• To address the speed limitations of HCPA, particularly when action probabilities approach unity.
• To demonstrate the robustness, optimality, and convergence properties of the proposed HDPA.

Main Methods:

• Developed the hierarchical discretized pursuit LA (HDPA) by incorporating discretization into the action probability updating mechanism.
• Applied the discretization recursively at each stage of the hierarchical structure.
• Formally proved epsilon-optimality using the moderation property and convergence to unity using the submartingale characteristic.

Main Results:

• The HDPA overcomes the speed impediment faced by HCPA when action probabilities are close to unity.
• Formal proofs confirm the HDPA's epsilon-optimality and the convergence of optimal action probability to unity.
• Numerical results show a significant reduction in convergence iterations for HDPA compared to HCPA.

Conclusions:

• The novel HDPA offers enhanced speed and accuracy in learning automata and reinforcement learning.
• Discretization effectively resolves the convergence speed limitations of previous hierarchical models.
• HDPA represents a significant advancement, demonstrating faster convergence and robust performance.