In recent years, reinforcement learning (RL) has emerged as a new, promising way to solve old problems. The algorithms’ role in finding approximate solutions in NP-hard complex- ity became crucial for developing modern intelligent deci- sions. In this paper, we consider the human resource alloca- tion problem, which is one of classical NP-hard complexity problem, with the fixed number of workers and tasks, using various RL methods, such as deep contextual bandit, double deep Q-learning network (DDQN), and a combined approach of DDQN with the Monte Carlo Tree Search (MCTS). The deep contextual bandit algorithm showed good performance for the low dimensional cases, but it is inappropriate for real problems in the chosen setting. To overcome such barriers, we decomposed the task in terms of Markov decision processes and reduced the action space so that all sequential RL meth- ods became available. In this paper, we proposed a way to deal with NP-hard problems via modern RL approaches and compare different methods’ performance. We studied differ- ent algorithms in the RL family, namely Contextual Bandit, DDQN, DDQN with MCTS. Those algorithms worked with appropriate settings and improved at least 30% in time reduc- tion compared to random assignment.

Research paper: Can Reinforcement Learning solve the Human Allocation Problem?

Phong Nguyen, Matsuba Hiroya, Tejdeep Hunabad, Dmitrii Zhilenkov, Hung Nguyen, Khang Nguyen