Study and implementation of online algorithms based on reinforcement learning for the K-servo problem.

The problem of K-servos is to allocate servos to meet requests in a metric, minimizing the cost of travel. This work compares the performance of the Work Function (WF) and Harmonic algorithms, a theoretical reference for the problem, with Q-Learning, a reinforcement learning technique. Simulations were performed with different instance configurations, varying number of servos, state space and distribution of requests. The results indicate that Q-Learning, well parameterized, achieves similar costs to WF in simple scenarios and surpasses it in environments with stable standards, due to its ability to adapt online. WF, on the other hand, has lower performance in adverse and complex situations. Statistical tests confirm the significance of the differences observed in instances with up to 5 servants. It is concluded that Q-Learning is a promising alternative to WF in practical contexts, although it faces limitations with the increase in state space, and the use of techniques such as deep Q-learning is suggested.