MEC--a near-optimal online reinforcement learning algorithm for continuous deterministic systems.

Area of Science:

• Machine Learning
• Control Theory
• Reinforcement Learning

Background:

• Continuous deterministic systems pose challenges for learning optimal control policies.
• Existing methods often require system dynamics knowledge or are computationally intensive.
• Efficient exploration and sample utilization are critical for effective learning in these systems.

Purpose of the Study:

• To propose the first probably approximately correct (PAC) algorithm for continuous deterministic systems that does not require prior system dynamics knowledge.
• To develop an algorithm that efficiently utilizes online observed samples and balances exploration-exploitation.
• To achieve near-optimal policies within a PAC framework with provable performance bounds.

Main Methods:

• State aggregation using a grid to partition the continuous state space.
• Definition of a near-upper Q operator for generating a near-upper Q function within each state cell.
• Implementation of a greedy policy that balances exploration and exploitation.
• Rigorous analysis to establish polynomial time bounds for non-optimal actions.

Main Results:

• The proposed algorithm achieves a polynomial time bound for executing non-optimal actions.
• The algorithm converges to a near-optimal policy in finite steps under the PAC framework.
• The implementation requires no system dynamics knowledge and exhibits lower computational complexity.
• Simulation studies indicate superior performance compared to other similar PAC algorithms.

Conclusions:

• The developed PAC algorithm offers an effective and efficient approach for learning control policies in continuous deterministic systems.
• The method's independence from system dynamics and reduced complexity make it broadly applicable.
• The algorithm provides a strong theoretical guarantee of convergence to near-optimal solutions.