Prioritized epoch - incremental Q - learning algorithm

• Autorzy: Zajdel R.
• Języki publikacji: EN

Abstrakty

EN

The basic reinforcement learning algorithms, such as Q-learning or Sarsa, are characterized by short time-consuming single learning step, however the number of epochs necessary to achieve the optimal policy is not acceptable. There are many methods that reduce the number of' necessary epochs, like TD(lambda greather than 0), Dyna or prioritized sweeping, but their computational time is considerable. This paper proposes a combination of Q-learning algorithm performed in the incremental mode with the method of acceleration executed in the epoch mode. This acceleration is based on the distance to the terminal state. This approach ensures the maintenance of short time of a single learning step and high efficiency comparable with Dyna or prioritized sweeping. Proposed algorithm is compared with Q(lambda)-learning, Dyna-Q and prioritized sweeping in the experiments of three grid worlds. The time-consuming learning process and number of epochs necessary to reach the terminal state is used to evaluate the efficiency of compared algorithms.

PL

Efektywność podstawowych algorytmów uczenia ze wzmocnieniem Q-learning i Sarsa, mierzona liczbą prób niezbędnych do uzyskania strategii optymalnej jest stosunkowo niewielka. Stąd też możliwości praktycznego zastosowania tego algorytmu są niewielkie. Zaletą tych podstawowych algorytmów jest jednak niewielka złożoność obliczeniowa, sprawiająca, że czas wykonania pojedynczego kroku uczenia jest na tyle mały, że znakomicie sprawdzają się one w systemach sterowania online. Stosowane metody przyśpieszania procesu uczenia ze wzmocnieniem, które pozwalająna uzyskanie stanu absorbującego po znacznie mniejszej liczbie prób, niż algorytmy podstawowe powodują najczęściej zwiększenie złożoności obliczeniowej i wydłużenie czasu wykonania pojedynczego kroku uczenia. Najczęściej stosowane przyśpieszanie metodą różnic czasowych TD(lambda znak większości 0) wiąże się z zastosowaniem dodatkowych elementów pamięciowych, jakimi są ślady aktywności (eligibility traces). Czas wykonania pojedynczego kroku uczenia w takim algorytmie znacznie się wydłuża, gdyż w odróżnieniu od algorytmu podstawowego, gdzie aktualizacji podlegała wyłącznie funkcja wartości akcji tylko dla stanu aktywnego, tutaj aktualizację przeprowadza się dla wszystkich stanów. Bardziej wydajne metody przyśpieszania, takie jak Dyna, czy też prioritized sweeping również należą do klasy algorytmów pamięciowych, a ich główną ideą jest uczenie ze wzmocnieniem w oparciu o adaptacyjny model środowiska. Metody te pozwalają na uzyskanie stanu absorbującego w znacznie mniejszej liczbie prób, jednakże, na skutek zwiększonej złożoności obliczeniowej, czas wykonania pojedynczego kroku uczenia jest już istotnym czynnikiem ograniczającym zastosowanie tych metod w systemach o znacznej liczbie stanów. Istotą tych algorytmów jest dokonywanie ustalonej liczby aktualizacji funkcji wartości akcji stanów aktywnych w przeszłości, przy czym w przypadku algorytmu Dyna są to stany losowo wybrane, natomiast w przypadku prioritized sweeping stany uszeregowane wg wielkości błędu aktualizacji. W niniejszym artykule zaproponowano epokowo-inkrementacyjny algorytm uczenia ze wzmocnieniem, którego główną ideą jest połączenie podstawowego, inkrementacyjnego algorytmu uczenia ze wzmocnieniem Q-lerning z algorytmem przyśpieszania wykonywanym epokowo. Zaproponowana metoda uczenia epokowego w głównej mierze opiera się na rzeczywistej wartości sygnału wzmocnienia obserwowanego przy przejściu do stanu absorbującego, który jest następnie wykładniczo propagowany wstecz w zależności od estymowanej odległości od stanu absorbującego. Dzięki takiemu podej- ściu uzyskano niewielki czas uczenia pojedynczego kroku w trybie inkrementacyjnym (Tab. 2) przy zachowaniu efektywności typowej dla algorytmów Dyna, czy też prioritized sweeping (Tab. 1 i Fig. 5).

Słowa kluczowe

EN

reinforcement learning; Q-learning; grid world

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2012
• Tom: Vol. 24, No. 2
• Strony: 159--171
• Opis fizyczny: Bibliogr. 20 poz., rys.

Twórcy

autor

Zajdel R.

• Department of Electrical Engineering and Informatics Rzeszow University of Technology al. Powstańców Warszawy 12, Rzeszów, Poland,

Bibliografia

• 1. A. Barto, S. Bradtke, S. Singh: Learning to Act using Real-Time Dynamic Programming,Artificial Intelligence, Special Volume on Computational Research on Interaction and Agency, 72 (1), pp. 81-138, 1995.
• 2. A. Barto, R. Sutton, C. Anderson: Neuronlike adaptive elements that can solve difficult learning problem, IEEE Trans. SMC, 13, pp. 834-847, 1983.
• 3. P. Cichosz: Systemy ucza˛ce sie˛, WNT, Warszawa, 2000 (in Polish).
• 4. P. Crook, G. Hayes: Learning in a State of Confusion: Perceptual Aliasing in Grid World Navigation, Proc. of Towards Intelligent Mobile Robots, 2003.
• 5. L. Kaelbing, M. Litman, A. Moore: Reinforcement Learning: A Survey, Journal of Artificial Intelligence Research, 4, pp. 237-285, 1996.
• 6. P. Lanzi: Adaptive Agents with Reinforcement Learning and Internal Memory, Proc. of the Sixth International Conference on the Simulation of Adaptive Behavior (SAB’2000),pages 333-342. The MIT Press, Cambridge, MA, 2000.
• 7. J. Loch, S. Singh: Using eligibility traces to find the best memoryless policy in partially observable markov decision processes, In ICML, pp. 323-331, 1998.
• 8. A. Moore, C. Atkeson: Prioritized sweeping: Reinforcement learning with less data and less time, Machine Learning, 13, pp. 103-130, 1993.
• 9. J. Peng, R. Williams: Efficient learning and planning within the Dyna framework, Proceedings of the 2nd International Conference on Simulation of Adaptive Behavior, Hawai, pp. 281-290, 1993.
• 10. M. Pickett, A. Barto: PolicyBlocks: An Algorithm for Creating Useful Macro-Actions in Reinforcement Learning, Proc. of the International Conference on Machine Learning, 19. pp. 506-513, 2002.
• 11. G. Rummery, M. Niranjan: On line q-learning using connectionist systems, Technical Report CUED/F-INFENG/TR 166, Cambridge University Engineering Department, 1994.
• 12. A. Sherstov, P. Stone: Improving Action Selection in MDP’s via Knowledge Transfer, Proc of the Nation Conference on Artificial Intelligence, 20(2), pp. 1024-1029, 2005.
• 13. R. Sutton: Integrated Architectures for Learning, Planning, and Reacting Based on Approximating Dynamic Programming, Proc. of Seventh Int. Conf. on Machine Learning, pp. 216-224, 1990.
• 14. R. Sutton: Planning by incremental dynamic programming, Proc. of the Ninth Conference on Machine Learning, pp. 353-357, 1991.
• 15. R. Sutton, A. Barto: Reinforcement learning: An Introduction, MIT Press, Cambridge, 1998.
• 16. P. Tadepalli, D. Ok: Model-Based Average Reward Reinforcement Learning, Artificial Intelligence, 100, pp. 177-224, 1998.
• 17. B. Tanner, S. Sutton: Temporal-Difference Networks with History, Proc. of the 2005 International Joint Conference on Artificial Intelligence, pp 865-870, 2005.
• 18. C. Watkins: Learning from delayed Rewards, PhD thesis. Cambridge University, Cambridge, England. 1989.
• 19. P.E. Wellstead: Introduction to Physical System Modelling, Control System Principles, 2000.
• 20. R. Zajdel: Epoch-Incremental Queue-Dyna Algorithm, Lecture Notes in Artificial Intelligence 5097, pp. 1160-1170, 2008