A parallel scheduling algorithm for reinforcement learning in large state space  

作　　者：Quan LIU Xudong YANG Ling JING Jin LI Jiao LI 

机构地区：[1]Institute of Computer Science and Technology,Soochow University,Suzhou 215006,China [2]Department of Computer Science and Technology,Nanjing University,Nanjing 210093,China [3]Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education,Jilin University,Changchun 130012,China

出　　处：《Frontiers of Computer Science》2012年第6期631-646,共16页中国计算机科学前沿（英文版）

基　　金：Acknowledgements This paper was supported by the National Natural Science Foundation of China （Grant Nos. 61272005, 61070223, 61103045, 60970015, and 61170020）, Natural Science Foundation of Jiangsu （BK2012616, BK2009116）, High School Natural Foundation of Jiangsu （09KJA520002）, and Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University （93K172012K04）.

摘　　要：The main challenge in the area of reinforcement learning is scaling up to larger and more complex problems. Aiming at the scaling problem of reinforcement learning, a scalable reinforcement learning method, DCS-SRL, is proposed on the basis of divide-and-conquer strategy, and its convergence is proved. In this method, the learning problem in large state space or continuous state space is decomposed into multiple smaller subproblems. Given a specific learning algorithm, each subproblem can be solved independently with limited available resources. In the end, component solutions can be recombined to obtain the desired result. To ad- dress the question of prioritizing subproblems in the scheduler, a weighted priority scheduling algorithm is proposed. This scheduling algorithm ensures that computation is focused on regions of the problem space which are expected to be maximally productive. To expedite the learning process, a new parallel method, called DCS-SPRL, is derived from combining DCS-SRL with a parallel scheduling architecture. In the DCS-SPRL method, the subproblems will be distributed among processors that have the capacity to work in parallel. The experimental results show that learning based on DCS-SPRL has fast convergence speed and good scalability.The main challenge in the area of reinforcement learning is scaling up to larger and more complex problems. Aiming at the scaling problem of reinforcement learning, a scalable reinforcement learning method, DCS-SRL, is proposed on the basis of divide-and-conquer strategy, and its convergence is proved. In this method, the learning problem in large state space or continuous state space is decomposed into multiple smaller subproblems. Given a specific learning algorithm, each subproblem can be solved independently with limited available resources. In the end, component solutions can be recombined to obtain the desired result. To ad- dress the question of prioritizing subproblems in the scheduler, a weighted priority scheduling algorithm is proposed. This scheduling algorithm ensures that computation is focused on regions of the problem space which are expected to be maximally productive. To expedite the learning process, a new parallel method, called DCS-SPRL, is derived from combining DCS-SRL with a parallel scheduling architecture. In the DCS-SPRL method, the subproblems will be distributed among processors that have the capacity to work in parallel. The experimental results show that learning based on DCS-SPRL has fast convergence speed and good scalability.

关 键 词：divide-and-conquer strategy parallel schedule SCALABILITY large state space continuous state space 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP301.6[自动化与计算机技术—控制科学与工程]