many real-world scenarios, a robot may need to perform a diverse set of tasks.
As an example, socially assistive robots designed with the purpose of
assisting older people in their houses may need to accomplish several tasks
such as medication reminders, detecting issues, informing caregivers, and
managing plans. Multi-goal RL enables an agent to learn multiple goals, hence
the agent can generalize the desired behavior and transfer skills to unseen
goals and tasks (Bai et al., 2019). This has been applied on robotic
manipulation tasks in a simulated environment (Bai et al., 2019). However,
applying the multi-goal RL framework to social robots would be a fruitful area
for future work.

Another interesting future direction might be the application of multi-
objective RL in social robotics. The task efficiency and user satisfaction can
be two objectives where the robot would try to maximize both objectives by
formalizing the problem as a multi-objective MDP. As an example, Hao et al.
(2019) presents a multi-objective weighted RL in which the agent had two
objectives: minimizing the cost of service execution and eliminating the
user’s negative emotions. We refer the interested reader to the survey on
multi-objective decision making for a more detailed explanation of the topic
(Roijers et al., 2013).

Recent developments in the field of deep neural networks have led to an
increasing interest in DRL. Applying DRL in social robotics has also received
recent attention, however, studies focused on small sets of actions and single
task scenarios. In this regard, social robots with larger sets of actions
would be a promising area for further work. Another future direction can be a
further investigation of hyper-parameters of RL in social robotics. This was
briefly discussed in (Keizer et al., 2014), as an example, in turn-based
interactions relatively small discount factors (i.e., $0.7\leq\gamma\leq
0.95$) are more common, whereas for the frame-based interactions with rather
long trajectories, higher discount factors seem to be more suitable (i.e.,
$\gamma\geq 0.99$). In deep networks, the selection of different hyper-
parameters affects the accuracy of the algorithm (Zhang et al., 2017). This
also applies to DRL, Lathuilière et al. (2019) presented several experiments
to evaluate the impact of some of the principal parameters of their deep
network structure.

Thus far, model-free RL learning a value function or a policy through trial
and error is the most commonly used approach in social robotics. However,
model-based RL that focuses on learning a transition model of the environment
serving as a simulation remains to be further explored. In particular, having
a user model can ease the learning process. Although it is difficult to model
human reactions, having a model can play a crucial role in reducing the number
of required interactions in the real-world. The model-based approach can also
help with the problem of hardware depreciation which may arise in model-free
RL in robotics because of the considerable amount of interaction time.
Simulating the interaction environment can ease the training without manual
interventions and a need for maintenance. Nonetheless, transferring the
learned policies in simulation directly to the physical robot may not be
trivial due to undermodeling and uncertainty about system dynamics (Kober et
al., 2013). A common limitation is that most of the works are not
generalizable, i.e., utilizing the knowledge learned by one robot on the other
or utilizing the task knowledge for other tasks. The Google AI team trained a
model-based Deep Planning Network (PlaNet) agent which achieved six different
tasks (i.e., cartpole swing-up, cartpole balance, finger spin, cheetah run,
etc.) (Hafner et al., 2018). A similar approach for a physical social robot
would be an interesting future direction.

RL problems are formalized as MDPs in fully observable environments. However,
in the case of HRI not all of the required observations are available, due to
the underlying effect of psychological states on human behavior. It has been
demonstrated that POMDPs are able to model the uncertainties and inherent
interaction ambiguities in real-world HRI scenarios (Kostavelis et al., 2017).
Hausknecht and Stone (2015) proposed a method that couples a Long Short Term
Memory with a Deep Q-Network to handle the noisy observations characteristic
of POMDPs. A similar approach would be useful in social robotics problems to
better capture the dynamics of the environment. We included two examples of
POMDP approaches in social robotics, (Ramachandran et al., 2019; Martins et
al., 2019). Further investigation would constitute an interesting line of
research.

##  8\. Conclusion

In this work, we give an overview of the work on RL in social robotics. We
surveyed the literature and presented a thorough analysis of RL approaches in
social robotics. Social robots have two important characteristics: physical
embodiment and interaction/communication capabilities. Therefore, we included
studies with physically embodied robots. Moreover, we categorize the papers
based on the used RL type. In this categorization, we discuss and group the
papers based on the communication medium used for reward formulation.
Considering the importance of designing the reward function, we also
categorize the papers based on the nature of the reward. The evaluation
methods of the papers are also grouped by whether or not they use subjective
and algorithmic metrics. We then provide a discussion in the view of real-
world RL challenges and proposed solutions. The points that remain to be
explored, including the approaches that have thus far received less attention
are also given in the discussion section. To conclude, despite tremendous
leaps in computing power and advances in learning methods, we are still a long
way from general-purpose, robust, and versatile social robots that can learn
several skills from naive users with real-world interactions. In spite of the
immediate challenges, we see steady progress of RL applications in social
robotics with an increasing interest in recent years.

## Author Contributions

N.A. was the main author responsible for conducting literature research,
methodology definition, and paper writing. A.L. supervised the study, and has
been involved in structuring and writing the paper. All authors have read and
agreed to the published version of the manuscript.

## Funding

This research was funded by European Union’s Horizon 2020 research and
innovation program under the Marie Skłodowska-Curie grant agreement No 721619
for the SOCRATES project.

## References

  * Keizer et al. (2014) Keizer, S.; Ellen Foster, M.; Wang, Z.; Lemon, O.  Machine Learning for Social Multiparty Human–Robot Interaction.  ACM Trans. Interact. Intell. Syst. 2014, 4, 14:1–14:32, doi:10.1145/2600021.
  * de Greeff and Belpaeme (2015) de Greeff, J.; Belpaeme, T.  Why robots should be social: Enhancing machine learning through social human-robot interaction.  PLoS ONE 2015, 10, e0138061.
  * Hemminghaus and Kopp (2017) Hemminghaus, J.; Kopp, S.  Towards Adaptive Social Behavior Generation for Assistive Robots Using Reinforcement Learning.  In Proceedings of the 2017 ACM/IEEE International Conference on Human-Robot Interaction (HRI 2017), Vienna, Austria, 6–9 March 2017; pp. 332–340,  doi:10.1145/2909824.3020217.
  * Ritschel et al. (2019) Ritschel, H.; Seiderer, A.; Janowski, K.; Wagner, S.; André, E.  Adaptive linguistic style for an assistive robotic health companion based on explicit human feedback.  In Proceedings of the 12th ACM International Conference on PErvasive Technologies Related to Assistive Environments, Rhodes, Greece, 5–7 June 2019; pp. 247–255.
  * Sutton et al. (1998) Sutton, R.S.; Barto, A.G.  Introduction to Reinforcement Learning; MIT Press: Cambridge, UK, 1998; Volume 2.
  * Barto et al. (1989) Barto, A.G.; Sutton, R.S.; Watkins, C.  Learning and Sequential Decision Making; University of Massachusetts Amherst: Amherst, MA, USA, 1989.
  * Fong et al. (2003) Fong, T.; Nourbakhsh, I.; Dautenhahn, K.  A survey of socially interactive robots.  Robot. Auton. Syst. 2003, 42, 143–166.
  * Breazeal (2003) Breazeal, C.  Toward sociable robots.  Robot. Auton. Syst. 2003, 42, 167–175.
  * Duffy (2003) Duffy, B.R.  Anthropomorphism and the social robot.  Robot. Auton. Syst. 2003, 42, 177–190.
  * Bartneck and Forlizzi (2004) Bartneck, C.; Forlizzi, J.  A design-centred framework for social human-robot interaction.  In Proceedings of the 13th IEEE International Workshop on Robot and Human Interactive Communication (RO-MAN 2004), Kurashiki, Japan, 20–22 September 2004; pp. 591–594.
  * Hegel et al. (2009) Hegel, F.; Muhl, C.; Wrede, B.; Hielscher-Fastabend, M.; Sagerer, G.  Understanding social robots.  In Proceedings of the 2009 Second International Conferences on Advances in Computer-Human Interactions, Cancun, Mexico, 1–7 February 2009; pp. 169–174.
  * Yan et al. (2014) Yan, H.; Ang, M.H.; Poo, A.N.  A survey on perception methods for human–robot interaction in social robots.  Int. J. Soc. Robot. 2014, 6, 85–119.
  * Maroto-Gómez et al. (2018) Maroto-Gómez, M.; Castro-González, Á.; Castillo, J.; Malfaz, M.; Salichs, M.  A bio-inspired motivational decision making system for social robots based on the perception of the user.  Sensors 2018, 18, 2691.
  * Sutton and Barto (2018) Sutton, R.S.; Barto, A.G.  Reinforcement Learning: An Introduction; A Bradford Book: Cambridge, MA, USA, 2018.
  * Kober et al. (2013) Kober, J.; Bagnell, J.A.; Peters, J.  Reinforcement learning in robotics: A survey.  Int. J. Robot. Res. 2013, 32, 1238–1274.
  * Kormushev et al. (2013) Kormushev, P.; Calinon, S.; Caldwell, D.  Reinforcement learning in robotics: Applications and real-world challenges.  Robotics 2013, 2, 122–148.
  * Deisenroth et al. (2013) Deisenroth, M.P.; Neumann, G.; Peters, J.  A survey on policy search for robotics.  Found. Trends® Robot. 2013, 2, 388–403.
  * Garcıa and Fernández (2015) Garcıa, J.; Fernández, F.  A comprehensive survey on safe reinforcement learning.  J. Mach. Learn. Res. 2015, 16, 1437–1480.
  * Bhagat et al. (2019) Bhagat, S.; Banerjee, H.; Ho Tse, Z.T.; Ren, H.  Deep reinforcement learning for soft, flexible robots: Brief review with impending challenges.  Robotics 2019, 8, 4.
  * Oudeyer et al. (2008) Oudeyer, P.Y.; Kaplan, F.  How can we define intrinsic motivation.  In Proceedings of the 8th International Conference on Epigenetic Robotics: Modeling Cognitive Development in Robotic Systems, Brighton, UK, 30–31 July 2008; pp. 93–101.
  * Thomaz et al. (2016) Thomaz, A.; Hoffman, G.; Cakmak, M.  Computational human-robot interaction.  Found. Trends Robot. 2016, 4, 105–223.
  * Thomaz et al. (2006) Thomaz, A.L.; Breazeal, C.; Barto, A.G.; Picard, R.  Socially Guided Machine Learning. 2006. Available online: https://scholarworks.umass.edu/cs_faculty_pubs/183 (accessed on 2 February 2020).
  * Holzinger et al. (2016) Holzinger, A.; Plass, M.; Holzinger, K.; Crişan, G.C.; Pintea, C.M.; Palade, V.  Towards interactive Machine Learning (iML): Applying ant colony algorithms to solve the traveling salesman problem with the human-in-the-loop approach.  In Proceedings of the International Conference on Availability, Reliability, and Security (ARES 2016), Salzburg, Austria, 31 August–2 September 2016; pp. 81–95.
  * Knox and Stone (2012) Knox, W.B.; Stone, P.  Reinforcement learning from simultaneous human and MDP reward.  In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS ’12), Valencia, Spain, 4–8 June 2012; pp. 475–482.
  * Isbell et al. (2001) Isbell, C.; Shelton, C.R.; Kearns, M.; Singh, S.; Stone, P.  A social reinforcement learning agent.  In Proceedings of the Fifth International Conference on Autonomous Agents, (AGENTS ’01), Montreal, QC, Canada, 28 May–1 June 2001; pp. 377–384.
  * Suay and Chernova (2011) Suay, H.B.; Chernova, S.  Effect of human guidance and state space size on interactive reinforcement learning.  In Proceedings of the 20th IEEE International Workshop on Robot and Human Communication (RO-MAN 2011), Atlanta, GA, USA, 31 July–3 August 2011; pp. 1–6.
  * Thomaz et al. (2006) Thomaz, A.L.; Hoffman, G.; Breazeal, C.  Reinforcement learning with human teachers: Understanding how people want to teach robots.  In Proceedings of the 15th IEEE International Symposium on Robot and Human Interactive Communication (RO-MAN 2006), Hatfield, UK, 6–8 September 2006; pp. 352–357.
  * Thomaz and Breazeal (2008) Thomaz, A.L.; Breazeal, C.  Experiments in socially guided exploration: Lessons learned in building robots that learn with and without human teachers.  Connect. Sci. 2008, 20, 91–110, doi:10.1080/09540090802091917.
  * Knox et al. (2013) Knox, W.B.; Stone, P.; Breazeal, C.  Training a Robot via Human Feedback: A Case Study.  In _Social Robotics_ ; Herrmann, G., Pearson, M.J., Lenz, A., Bremner, P., Spiers, A., Leonards, U., Eds.; Springer International Publishing: Cham, Switzerland, 2013; pp. 460–470.
  * Suay et al. (2012) Suay, H.B.; Toris, R.; Chernova, S.  A Practical Comparison of Three Robot Learning from Demonstration Algorithm.  Int. J. Soc. Robot. 2012, 4, 319–330, doi:10.1007/s12369-012-0158-7.
  * Thomaz and Breazeal (2007) Thomaz, A.L.; Breazeal, C.  Asymmetric Interpretations of Positive and Negative Human Feedback for a Social Learning Agent.  In Proceedings of the 16th IEEE International Symposium Robot and Human Interactive Communication (RO-MAN 2007), Jeju, Korea, 26–29 August 2007; pp. 720–725,  doi:10.1109/ROMAN.2007.4415180.
  * Patompak et al. (2019) Patompak, P.; Jeong, S.; Nilkhamhang, I.; Chong, N.Y.  Learning Proxemics for Personalized Human–Robot Social Interaction.  Int. J. Soc. Robot. 2019, 12, 267–280,  doi:10.1007/s12369-019-00560-9
  * Chan and Nejat (2012) Chan, J.; Nejat, G.  Social Intelligence for a Robot Engaging People in Cognitive Training Activities.  Int. J. Adv. Robot. Syst. 2012, 9,  doi:10.5772/51171.
  * Pérula-Martínez et al. (2019) Pérula-Martínez, R.; Castro-Gonzalez, A.; Malfaz, M.; Alonso-Martín, F.; Salichs, M.A.  Bioinspired decision-making for a socially interactive robot.  Cogn. Syst. Res. 2019, 54, 287–301.
  * Cuayáhuitl (2019) Cuayáhuitl, H.  A data-efficient deep learning approach for deployable multimodal social robots.  Neurocomputing 2019, _396_ , 587–598.
  * Qureshi et al. (2016) Qureshi, A.H.; Nakamura, Y.; Yoshikawa, Y.; Ishiguro, H.  Robot gains social intelligence through multimodal deep reinforcement learning.  In Proceedings of the 16th IEEE-RAS International Conference on Humanoid Robots, Humanoids, Cancun, Mexico, 15–17 November 2016; pp. 745–751, doi:10.1109/HUMANOIDS.2016.7803357.
  * Zhang and Yu (2020) Zhang, H.; Yu, T. Taxonomy of Reinforcement Learning Algorithms.  In Deep Reinforcement Learning: Fundamentals, Research and Applications; Dong, H., Ding, Z., Zhang, S., Eds.; Springer: Singapore, 2020; pp. 125–133, doi:10.1007/978-981-15-4095-0_3.
  * Bellman (1952) Bellman, R.  On the theory of dynamic programming.  Proc. Natl. Acad. Sci. USA 1952, 38, 716.
  * Rummery and Niranjan (1994) Rummery, G.A.; Niranjan, M.  On-line Q-Learning Using Connectionist Systems; University of Cambridge, Department of Engineering: Cambridge, UK, 1994; Volume 37.
  * Watkins (1989) Watkins, C.J.C.H.  Learning from Delayed Rewards. 1989. Available online: http://www.cs.rhul.ac.uk/~chrisw/new_thesis.pdf (accessed on 7 December 2019).
  * Gosavi (2006) Gosavi, A.  Boundedness of iterates in Q-learning.  Syst. Control Lett. 2006, 55, 347–349.
  * Sigaud and Stulp (2019) Sigaud, O.; Stulp, F.  Policy search in continuous action domains: An overview.  Neural Netw. 2019, 113, 28–40.
  * Mnih et al. (2015) Mnih, V.; Kavukcuoglu, K.; Silver, D.; Rusu, A.A.; Veness, J.; Bellemare, M.G.; Graves, A.; Riedmiller, M.; Fidjeland, A.K.; Ostrovski, G.; et al.  Human-level control through deep reinforcement learning.  Nature 2015, 518, 529–533.
  * Schneider and Kummert (2017) Schneider, S.; Kummert, F.  Exploring embodiment and dueling bandit learning for preference adaptation in human-robot interaction.  In Proceedings of the 26th IEEE International Symposium on Robot and Human Interactive Communication (RO-MAN 2017), Lisbon, Portugal, 28 August–1 September 2017; pp. 1325–1331.
  * Leite et al. (2011) Leite, I.; Pereira, A.; Castellano, G.; Mascarenhas, S.; Martinho, C.; Paiva, A.  Modelling empathy in social robotic companions.  In Proceedings of the International Conference on User Modeling, Adaptation, and Personalization (UMAP 2011), Girona, Spain, 11–15 July 2011; pp. 135–147.
  * Ritschel et al. (2018) Ritschel, H.; Seiderer, A.; Janowski, K.; Aslan, I.; André, E.  Drink-o-mender: An adaptive robotic drink adviser.  In Proceedings of the 3rd International Workshop on Multisensory Approaches to Human-Food Interaction, Boulder, CO, USA, 16–20 October 2018; pp. 1–8.
  * Gao et al. (2018) Gao, Y.; Barendregt, W.; Obaid, M.; Castellano, G.  When robot personalisation does not help: Insights from a robot-supported learning study.  In Proceedings of the 27th IEEE International Symposium on Robot and Human Interactive Communication (RO-MAN 2018), Nanjing, China, 27–31 August 2018; pp. 705–712.
  * Bubeck and Cesa-Bianchi (2012) Bubeck, S.; Cesa-Bianchi, N.  Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems.  Found. Trends® Mach. Learn. 2012, 5, 1–122, doi:10.1561/2200000024.
  * Tseng et al. (2018) Tseng, S.H.; Liu, F.C.; Fu, L.C.  Active Learning on Service Providing Model: Adjustment of Robot Behaviors Through Human Feedback.  IEEE Trans. Cogn. Dev. Syst. 2018, 10, 701–711, doi:10.1109/TCDS.2017.2775621.
  * Martins et al. (2019) Martins, G.S.; Al Tair, H.; Santos, L.; Dias, J.  $\alpha$POMDP: POMDP-based user-adaptive decision-making for social robots.  Pattern Recognit. Lett. 2019, 118, 94–103.
  * Wiewiora (2010) Wiewiora, E. Reward Shaping.  In Encyclopedia of Machine Learning; Sammut, C., Webb, G.I., Eds.; Springer: Boston, MA, USA, 2010; pp. 863–865.
  * Barraquand and Crowley (2008) Barraquand, R.; Crowley, J.L.  Learning Polite Behavior with Situation Models.  In Proceedings of the 3rd ACM/IEEE International Conference on Human Robot Interaction (HRI 2008), Amsterdam, The Netherlands, 12–15 March 2008; pp. 209–216, doi:10.1145/1349822.1349850.
  * Yang et al. (2017) Yang, C.; Lu, M.; Tseng, S.; Fu, L.  A companion robot for daily care of elders based on homeostasis.  In Proceedings of the 56th Annual Conference of the Society of Instrument and Control Engineers of Japan (SICE 2017), Kanazawa, Japan, 19–22 September 2017; pp. 1401–1406, doi:10.23919/SICE.2017.8105748.
  * Zarinbal et al. (2019) Zarinbal, M.; Mohebi, A.; Mosalli, H.; Haratinik, R.; Jabalameli, Z.; Bayatmakou, F.  A New Social Robot for Interactive Query-Based Summarization: Scientific Document Summarization.  In Proceedings of the International Conference on Interactive Collaborative Robotics (ICR 2019), Istanbul, Turkey, 20–25 August 2019; pp. 330–340.
  * Addo and Ahamed (2014) Addo, I.D.; Ahamed, S.I.  Applying affective feedback to reinforcement learning in ZOEI, a comic humanoid robot.  In Proceedings of the 23rd IEEE International Symposium on Robot and Human Interactive Communication (RO-MAN 2014), Edinburgh, UK, 25–29 August 2014; pp. 423–428.
  * Chiang et al. (2014) Chiang, Y.S.; Chu, T.S.; Lim, C.; Wu, T.Y.; Tseng, S.H.; Fu, L.C.  Personalizing robot behavior for interruption in social human-robot interaction.  In Proceedings of the 2014 IEEE International Workshop on Advanced Robotics and its Social Impacts (ARSO 2014), Evanston, IL, USA, 11–13 September 2014; pp. 44–49,  doi:10.1109/ARSO.2014.7020978.
  * Ritschel et al. (2017) Ritschel, H.; Baur, T.; André, E.  Adapting a Robot’s linguistic style based on socially-aware reinforcement learning.  In Proceedings of the 26th IEEE International Symposium on Robot and Human Interactive Communication (RO-MAN 2017), Lisbon, Portugal, 28 August–1 September 2017; pp. 378–384, doi:10.1109/ROMAN.2017.8172330.
  * Park et al. (2019) Park, H.W.; Grover, I.; Spaulding, S.; Gomez, L.; Breazeal, C.  A model-free affective reinforcement learning approach to personalization of an autonomous social robot companion for early literacy education.  In Proceedings of the AAAI Conference on Artificial Intelligence, Honolulu, HI, USA, 27 January–1 February 2019; Volume 33, pp. 687–694.
  * Weber et al. (2018) Weber, K.; Ritschel, H.; Aslan, I.; Lingenfelser, F.; André, E.  How to Shape the Humor of a Robot - Social Behavior Adaptation Based on Reinforcement Learning.  In Proceedings of the International Conference on Multimodal Interaction, ICMI 2018, Boulder, CO, USA, 16–20 October 2018; pp. 154–162, doi:10.1145/3242969.3242976.
  * Papaioannou et al. (2017) Papaioannou, I.; Dondrup, C.; Novikova, J.; Lemon, O.  Hybrid chat and task dialogue for more engaging hri using reinforcement learning.  In Proceedings of the 26th IEEE International Symposium on Robot and Human Interactive Communication (RO-MAN 2017), Lisbon, Portugal, 28 August–1 September 2017; pp. 593–598.
  * Moro et al. (2018) Moro, C.; Nejat, G.; Mihailidis, A.  Learning and Personalizing Socially Assistive Robot Behaviors to Aid with Activities of Daily Living.  ACM Trans. Hum. Robot. Interact. 2018, 7, doi:10.1145/3277903.
  * Nejat and Ficocelli (2008) Nejat, G.; Ficocelli, M.  Can I be of assistance? The intelligence behind an assistive robot.  In Proceedings of the 2008 IEEE International Conference on Robotics and Automation (ICRA 2008), Pasadena, CA, USA, 19–23 May 2008; pp. 3564–3569.
  * Da Silva and Francelin Romero (2012) Da Silva, R.R.; Francelin Romero, R.A.  Modelling Shared Attention Through Relational Reinforcement Learning.  J. Intell. Robot. Syst. 2012, 66, 167–182, doi:10.1007/s10846-011-9624-y.
  * Castro-González et al. (2014) Castro-González, Á.; Malfaz, M.; Gorostiza, J.F.; Salichs, M.A.  Learning behaviors by an autonomous social robot with motivations.  Cybern. Syst. 2014, 45, 568–598.
  * Castro-González et al. (2013) Castro-González, Á.; Malfaz, M.; Salichs, M.A.  An autonomous social robot in fear.  IEEE Trans. Auton. Ment. Dev. 2013, 5, 135–151.
  * Castro-González et al. (2011) Castro-González, Á.; Malfaz, M.; Salichs, M.A.  Learning the Selection of Actions for an Autonomous Social Robot by Reinforcement Learning Based on Motivations.  Int. J. Soc. Robot. 2011, 3, 427–441, doi:10.1007/s12369-011-0113-z.
  * Chen et al. (2018) Chen, L.; Wu, M.; Zhou, M.; She, J.; Dong, F.; Hirota, K.  Information-Driven Multirobot Behavior Adaptation to Emotional Intention in Human–Robot Interaction.  IEEE Trans. Cogn. Dev. Syst. 2018, 10, 647–658, doi:10.1109/TCDS.2017.2728003.
  * Gordon et al. (2016) Gordon, G.; Spaulding, S.; Westlund, J.K.; Lee, J.J.; Plummer, L.; Martinez, M.; Das, M.; Breazeal, C. Affective personalization of a social robot tutor for children’s second language skills. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, Phoenix, AZ, USA, 12–17 February 2016.
  * Gamborino and Fu (2018) Gamborino, E.; Fu, L.C.  Interactive Reinforcement Learning based Assistive Robot for the Emotional Support of Children.  In Proceedings of the 18th International Conference on Control Automation and Systems (ICCAS 2018), Pyeong Chang, Korea, 17–20 October 2018; pp. 708–713.
  * Ranatunga et al. (2011) Ranatunga, I.; Rajruangrabin, J.; Popa, D.O.; Makedon, F.  Enhanced Therapeutic Interactivity Using Social Robot Zeno.  In Proceedings of the 4th International Conference on PErvasive Technologies Related to Assistive Environments (PETRA 2011), Crete, Greece, 25–27 May 2011; pp. 1–6, doi:10.1145/2141622.2141690.
  * Chan and Nejat (2011a) Chan, J.; Nejat, G.  Minimizing task-induced stress in cognitively stimulating activities using an intelligent socially assistive robot.  In Proceedings of the 20th International Symposium on Robot and Human Interactive Communication (RO-MAN 2011), Atlanta, GA, USA, 31 July–3 August 2011; pp. 296–301.
  * Chan and Nejat (2011b) Chan, J.; Nejat, G.  A learning-based control architecture for an assistive robot providing social engagement during cognitively stimulating activities.  In Proceedings of the 2011 IEEE International Conference on Robotics and Automation, Shanghai, China, 9–13 May 2011; pp. 3928–3933.
  * Qureshi et al. (2017) Qureshi, A.H.; Nakamura, Y.; Yoshikawa, Y.; Ishiguro, H.  Show, attend and interact: Perceivable human-robot social interaction through neural attention Q-network.  In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2017), Singapore, Singapore, 29 May–3 June 2017; pp. 1639–1645.
  * Qureshi et al. (2018) Qureshi, A.; Nakamura, Y.; Yoshikawa, Y.; Ishiguro, H.  Intrinsically motivated reinforcement learning for human–robot interaction in the real-world.  Neural Netw. 2018, 107, 23–33,  doi:10.1016/j.neunet.2018.03.014.
  * Thomaz and Breazeal (2006) Thomaz, A.; Breazeal, C.  Adding guidance to interactive reinforcement learning.  In Proceedings of the 20th Conference on Artificial Intelligence (AAAI 2006), Boston, MA, USA, 16–20 July 2006.
  * Loftin et al. (2016) Loftin, R.; Peng, B.; MacGlashan, J.; Littman, M.L.; Taylor, M.E.; Huang, J.; Roberts, D.L.  Learning behaviors via human-delivered discrete feedback: Modeling implicit feedback strategies to speed up learning.  Auton. Agents Multi Agent Syst. 2016, 30, 30–59.
  * Wagner et al. (2013) Wagner, J.; Lingenfelser, F.; Baur, T.; Damian, I.; Kistler, F.; André, E.  The social signal interpretation (SSI) framework: Multimodal signal processing and recognition in real-time.  In Proceedings of the 21st ACM International Conference on Multimedia, Barcelona, Spain, 21–25 October 2013; pp. 831–834.
  * McDuff et al. (2016) McDuff, D.; Mahmoud, A.; Mavadati, M.; Amr, M.; Turcot, J.; Kaliouby, R.E.  AFFDEX SDK: A cross-platform real-time multi-face expression recognition toolkit.  In Proceedings of the 2016 CHI Conference Extended Abstracts on Human Factors in Computing Systems, San Jose, CA, USA, 7–12 May 2016; pp. 3723–3726.
  * Chen et al. (2013) Chen, L.F.; Liu, Z.T.; Dong, F.Y.; Yamazaki, Y.; Wu, M.; Hirota, K.  Adapting multi-robot behavior to communication atmosphere in humans-robots interaction using fuzzy production rule based friend-Q learning.  J. Adv. Comput. Intell. Intell. Inform. 2013, 17, 291–301.
  * Schwartz (1993) Schwartz, A.  A Reinforcement Learning Method for Maximizing Undiscounted Rewards.  In Proceedings of the 10th International Conference on Machine Learning (ICML 1993), Amherst, MA, USA, 27–29 June 1993; Volume 298, pp. 298–305.
  * Mahadevan (1996) Mahadevan, S.  Average reward reinforcement learning: Foundations, algorithms, and empirical results.  Mach. Learn. 1996, 22, 159–195.
  * Mavridis (2015) Mavridis, N.  A review of verbal and non-verbal human–robot interactive communication.  Robot. Auton. Syst. 2015, 63, 22–35.
  * da Silva et al. (2009) Da Silva, R.R.; Policastro, C.A.; Romero, R.A.  Relational reinforcement learning applied to shared attention.  In Proceedings of the 2009 International Joint Conference on Neural Networks (IJCNN 2009), Atlanta, GA, USA, 14–19 June 2009; pp. 2943–2949.
  * Dietterich (2000) Dietterich, T.G.  Hierarchical reinforcement learning with the MAXQ value function decomposition.  J. Artif. Intell. Res. 2000, 13, 227–303.
  * Lathuilière et al. (2018) Lathuilière, S.; Massé, B.; Mesejo, P.; Horaud, R.  Deep Reinforcement Learning for Audio-Visual Gaze Control.  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2018), Madrid, Spain, 1–5 October 2018; pp. 1555–1562.
  * Lathuilière et al. (2019) Lathuilière, S.; Massé, B.; Mesejo, P.; Horaud, R.  Neural network based reinforcement learning for audio–visual gaze control in human–robot interaction.  Pattern Recognit. Lett. 2019, 118, 61–71, doi:10.1016/j.patrec.2018.05.023.
  * Churamani et al. (2018) Churamani, N.; Barros, P.; Strahl, E.; Wermter, S.  Learning Empathy-Driven Emotion Expressions using Affective Modulations.  In Proceedings of the International Joint Conference on Neural Networks (IJCNN 2018), Rio de Janeiro, Brazil, 8–13 July 2018; pp. 1–8, doi:10.1109/IJCNN.2018.8489158.
  * Xu et al. (2015) Xu, K.; Ba, J.; Kiros, R.; Cho, K.; Courville, A.; Salakhudinov, R.; Zemel, R.; Bengio, Y.  Show, attend and tell: Neural image caption generation with visual attention.  In Proceedings of the International Conference on Machine Learning (ICML 2015), Lille, France, 6–11 July 2015; pp. 2048–2057.
  * Breazeal (2009) Breazeal, C.  Role of expressive behaviour for robots that learn from people.  Philos. Trans. R. Soc. B Biol. Sci. 2009, 364, 3527–3538.
  * Mitsunaga et al. (2006) Mitsunaga, N.; Smith, C.; Kanda, T.; Ishiguro, H.; Hagita, N.  Robot behavior adaptation for human-robot interaction based on policy gradient reinforcement learning.  J. Robot. Soc. Jpn. 2006, 24, 820–829.
  * Mitsunaga et al. (2008) Mitsunaga, N.; Smith, C.; Kanda, T.; Ishiguro, H.; Hagita, N.  Adapting robot behavior for human–robot interaction.  IEEE Trans. Robot. 2008, 24, 911–916.
  * Tapus et al. (2008) Tapus, A.; Ţăpuş, C.; Matarić, M.J.  User—Robot personality matching and assistive robot behavior adaptation for post-stroke rehabilitation therapy.  Intell. Serv. Robot. 2008, 1, 169, doi:10.1007/s11370-008-0017-4.
  * Knox and Stone (2009) Knox, W.B.; Stone, P.  Interactively shaping agents via human reinforcement: The TAMER framework.  In Proceedings of the 5th International Conference on Knowledge Capture, Redondo Beach, CA, USA, 1–4 September 2009; pp. 9–16.
  * Celemin and Ruiz-del Solar (2019) Celemin, C.; Ruiz-del Solar, J.  An interactive framework for learning continuous actions policies based on corrective feedback.  J. Intell. Robot. Syst. 2019, 95, 77–97.
  * Thomaz and Breazeal (2008) Thomaz, A.L.; Breazeal, C.  Teachable robots: Understanding human teaching behavior to build more effective robot learners.  Artif. Intell. 2008, 172, 716–737.
  * Li et al. (2019) Li, G.; Gomez, R.; Nakamura, K.; He, B.  Human-centered reinforcement learning: A survey.  IEEE Trans. Hum. Mach. Syst. 2019, 49, 337–349.
  * Knox and Stone (2015) Knox, W.B.; Stone, P.  Framing reinforcement learning from human reward: Reward positivity, temporal discounting, episodicity, and performance.  Artif. Intell. 2015, 225, 24–50.
  * Thomaz et al. (2006) Thomaz, A.L.; Breazeal, C.  Reinforcement Learning with Human Teachers: Evidence of Feedback and Guidance with Implications for Learning Performance. In Proceedings of the 21st National Conference on Artificial intelligence (AAAI 2006),  Boston, MA, USA, 16–-20 July 2006; Volume 6, pp. 1000–1005.
  * Schmidt (2000) Schmidt, A.  Implicit human computer interaction through context.  Pers. Technol. 2000, 4, 191–199.
  * Grüneberg and Suzuki (2012) Grüneberg, P.; Suzuki, K.  A lesson from subjective computing: Autonomous self-referentiality and social interaction as conditions for subjectivity.  In Proceedings of the AISB/IACAP World Congress 2012: Computational Philosophy, Part of Alan Turing Year, Birmingham, UK, 2–6 July 2012; pp. 18–28.
  * Grüneberg and Suzuki (2013) Grüneberg, P.; Suzuki, K.  An approach to subjective computing: A robot that learns from interaction with humans.  IEEE Trans. Auton. Ment. Dev. 2013, 6, 5–18.
  * Ramachandran et al. (2019) Ramachandran, A.; Sebo, S.S.; Scassellati, B.  Personalized Robot Tutoring using the Assistive Tutor POMDP (AT-POMDP).  In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019), Honolulu, HI, USA, 27 January–1 February 2019; pp. 8050–8057.
  * Lerner et al. (2015) Lerner, J.S.; Li, Y.; Valdesolo, P.; Kassam, K.S.  Emotion and decision making.  Annu. Rev. Psychol. 2015, 66, 799–823.
  * Moerland et al. (2018) Moerland, T.M.; Broekens, J.; Jonker, C.M.  Emotion in reinforcement learning agents and robots: A survey.  Mach. Learn. 2018, 107, 443–480.
  * Ryan and Deci (2000) Ryan, R.M.; Deci, E.L.  Intrinsic and extrinsic motivations: Classic definitions and new directions.  Contemp. Educ. Psychol. 2000, 25, 54–67.
  * Oudeyer and Kaplan (2009) Oudeyer, P.Y.; Kaplan, F.  What is intrinsic motivation? A typology of computational approaches.  Front. Neurorobotics 2009, 1, 6.
  * Chentanez et al. (2004) Chentanez, N.; Barto, A.G.; Singh, S.P.  Intrinsically motivated reinforcement learning.  In Proceedings of the Advances in Neural Information Processing Systems (NIPS 2004), Vancouver, BC, Canada, 13–18 December 2004; pp. 1281–1288.
  * Malfaz et al. (2011) Malfaz, M.; Castro-González, Á.; Barber, R.; Salichs, M.A.  A biologically inspired architecture for an autonomous and social robot.  IEEE Trans. Auton. Ment. Dev. 2011, 3, 232–246.
  * Cannon (1939) Cannon, W.B.  The Wisdom of the Body; W.W. Norton & Company, Inc.: New York, NY, USA, 1939.
  * Berridge (2004) Berridge, K.C.  Motivation concepts in behavioral neuroscience.  Physiol. Behav. 2004, 81, 179–209.
  * Sim and Loo (2015) Sim, D.Y.Y.; Loo, C.K.  Extensive assessment and evaluation methodologies on assistive social robots for modelling human–robot interaction–A review.  Inf. Sci. 2015, 301, 305–344.
  * Dulac-Arnold et al. (2019) Dulac-Arnold, G.; Mankowitz, D.; Hester, T.  Challenges of real-world reinforcement learning.  arXiv 2019, arXiv:1904.12901.
  * Lockerd and Breazeal (2004) Lockerd, A.; Breazeal, C.  Tutelage and socially guided robot learning.  In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2004), Sendai, Japan, 28 September–2 October 2004; Volume 4, pp. 3475–3480.
  * Liu et al. (2014) Liu, L.; Li, B.; Chen, I.M.; Goh, T.J.; Sung, M.  Interactive robots as social partner for communication care.  In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2014), Hong Kong, China, 31 May–7 June 2014; pp. 2231–2236.
  * Bai et al. (2019) Bai, C.; Liu, P.; Zhao, W.; Tang, X.  Guided goal generation for hindsight multi-goal reinforcement learning.  Neurocomputing 2019, _359_ , 353–367.
  * Hao et al. (2019) Hao, M.; Cao, W.; Liu, Z.; Wu, M.; Yuan, Y.  Emotion Regulation Based on Multi-objective Weighted Reinforcement Learning for Human-robot Interaction.  In Proceedings of the 12th Asian Control Conference (ASCC 2019), Kitakyushu-shi, Japan, 9–12 June 2019; pp. 1402–1406.
  * Roijers et al. (2013) Roijers, D.M.; Vamplew, P.; Whiteson, S.; Dazeley, R.  A Survey of Multi-objective Sequential Decision-making.  J. Artif. Intell. Res. 2013, 48, 67–113.
  * Zhang et al. (2017) Zhang, X.; Yao, L.; Huang, C.; Sheng, Q.Z.; Wang, X.  Intent Recognition in Smart Living through Deep Recurrent Neural Networks.  In Proceedings of the International Conference on Neural Information Processing, Guangzhou, China, 14–18 November 2017; pp. 748–758.
  * Hafner et al. (2018) Hafner, D.; Lillicrap, T.; Fischer, I.; Villegas, R.; Ha, D.; Lee, H.; Davidson, J.  Learning Latent Dynamics for Planning from Pixels.  In Proceedings of the 36th International Conference on Machine Learning (ICML 2019), Long Beach, CA, USA, 9–15 June 2019; pp. 2555–2565.
  * Kostavelis et al. (2017) Kostavelis, I.; Giakoumis, D.; Malassiotis, S.; Tzovaras, D.  A POMDP Design Framework for Decision Making in Assistive Robots.  In Proceedings of the International Conference on Human-Computer Interaction (HCI 2017), Vancouver, BC, Canada, 9–14 July 2017; pp. 467–479.
  * Hausknecht and Stone (2015) Hausknecht, M.; Stone, P.  Deep Recurrent Q-Learning for Partially Observable MDPs.  In Proceedings of the 2015 AAAI Fall Symposium on Sequential Decision Making for Intelligent Agents (AAAI-SDMIA15), Arlington, VA, USA, 12–14 November 2015.


# A* Search Without Expansions: Learning Heuristic Functions with Deep
Q-Networks

Forest Agostinelli
Department of Computer Science and Engineering
University of South Carolina
<EMAIL_ADDRESS>
&Alexander Shmakov
Department of Computer Science
University of California, Irvine
<EMAIL_ADDRESS>
&Stephen McAleer
Department of Computer Science
University of California, Irvine
<EMAIL_ADDRESS>
&Roy Fox
Department of Computer Science
University of California, Irvine
<EMAIL_ADDRESS>
&Pierre Baldi
Department of Computer Science
University of California, Irvine
<EMAIL_ADDRESS>

###### Abstract

A* search is an informed search algorithm that uses a heuristic function to
guide the order in which nodes are expanded. Since the computation required to
expand a node and compute the heuristic values for all of its generated
children grows linearly with the size of the action space, A* search can
become impractical for problems with large action spaces. This computational
burden becomes even more apparent when heuristic functions are learned by
general, but computationally expensive, deep neural networks. To address this
problem, we introduce DeepCubeAQ, a deep reinforcement learning and search
algorithm that builds on the DeepCubeA algorithm and deep Q-networks.
DeepCubeAQ learns a heuristic function that, with a single forward pass
through a deep neural network, computes the sum of the transition cost and the
heuristic value of all of the children of a node without explicitly generating
any of the children, eliminating the need for node expansions. DeepCubeAQ then
uses a novel variant of A* search, called AQ* search, that uses the deep
Q-network to guide search. We use DeepCubeAQ to solve the Rubik’s cube when
formulated with a large action space that includes 1872 meta-actions and show
that this 157-fold increase in the size of the action space incurs less than a
4-fold increase in computation time when performing AQ* search and that AQ*
search is orders of magnitude faster than A* search.

##  1 Introduction

While the performance of A* search is often measured in the number of nodes it
expands, the number of nodes it generates through the expansion process has a
major impact on performance. Expanding a node requires that every possible
action be applied to the state associated with that node, thereby generating
new states and, subsequently, new nodes. After a node is generated, the A*
search algorithm computes the heuristic value of this newly generated node
using the heuristic function. Finally, each newly generated node is then
pushed to a priority queue. Therefore, for each iteration of A* search, the
number of new nodes generated, the number of applications of the heuristic
function, and the number of nodes pushed to the priority queue increases
linearly with the size of the action space. Furthermore, much of this
computation eventually goes unused as, in general, A* search does not expand
every node that it generates.

The need to reduce this linear increase in computational cost has become more
relevant with the more frequent use of deep neural networks (DNNs) [24] as
heuristic functions. While DNNs are universal function approximators [16],
they are computationally expensive when compared to heuristic functions based
on domain knowledge, human intuition, and pattern databases [10]. Nonetheless,
DNNs are able to learn heuristic functions to solve problems ranging from
puzzles [8, 3, 20, 1], to quantum computing [31], to chemical synthesis [7],
while making very few assumptions about the structure of the problem. Due to
their flexibility and ability to generalize, DNNs offer the promise of
learning heuristic functions in a largely domain-independent fashion. Removing
the linear increase in computational cost as a function of the size of the
action space would make DNNs practical for a wide range of applications with
large action spaces such as multiple sequence alignment, theorem proving,
program synthesis, and molecular optimization.

The DeepCubeA algorithm used deep reinforcement learning and A* search to
solve puzzles such as the Rubik’s cube [1] and has since been used in
applications such as quantum computing [31] and cryptography [17]. DeepCubeA
uses approximate value iteration [5] to train a heuristic function without
relying on domain specific heuristic information. However, the computation
required for approximate value iteration also grows linearly with the size of
the action space. Therefore, the practicality of both the training phase and
the search phase of DeepCubeA reduces as the size of the action space
increases.

While previous attempts at reducing the number of generated nodes involve
using domain knowledge to partially expand a node by generating only a subset
of its children [12], in this work, we introduce the DeepCubeAQ algorithm,
which removes the need to expand nodes, entirely. DeepCubeAQ uses Q-learning
to train a deep Q-network (DQN) which is then integrated with A* search to
create an algorithm we call AQ*. DQNs are DNNs that map a single state to the
sum of the transition cost and the heuristic value for each of its successor
states. This removes the need for node expansions as we can obtain the
information needed to estimate the cost of all children with a single forward
pass through a DQN. In addition, the number of times the heuristic function
must be applied is constant with respect to the size of the action space
instead of linear. To track actions, each node is also associated with an
action, which gets applied to its corresponding state when removed from the
priority queue. As a result, the only aspect of AQ* search that depends on the
action space is pushing a node, along with each of its possible actions, to
the priority queue. This is also more memory efficient than explicitly
generating all children nodes as, in our implementation, each action is only
an integer.

We show that DeepCubeAQ can train a heuristic function and use search to solve
problems orders of magnitude faster than DeepCubeA. DeepCubeAQ also generates
orders of magnitude fewer nodes than DeepCubeA, thus using less memory. As the
size of the action space grows, DeepCubeA becomes impractical while DeepCubeAQ
sees only a relatively small increase in runtime and memory usage.

##  2 Related Work

Partial expansion A* search (PEA*) [29] was proposed for problems with large
action spaces. PEA* first expands a node by generating all of its children,
however, it only keeps the children whose cost is below a certain threshold.
It then adds a bookkeeping structure to remember the highest cost of the
discarded nodes. The intention of PEA* is to save memory, however, the
computational requirements do not reduce as every node has to be expanded and
the heuristic function has to be applied to all of its children. Enhanced
partial expansion A* search (EPEA*) [12] uses a domain-dependent operator
selection function to only generate a subset of children based on their cost.

DNNs have been used to address large action spaces in adversarial search. In
particular, when combined with Monte-Carlo tree search (MCTS) [9], DNNs with
multi-dimensional outputs that represent policies have been used to learn to
play Go [25], as well as chess and Shogi [26], at superhuman levels. In
addition to adversarial search, MCTS combined with DNNs has been applied to
combinatorial optimization problems [19] and hard Sokoban problems [13]. In
the original DeepCube algorithm, MCTS was combined with DNNs to solve the
Rubik’s cube [20]. However, DeepCubeA showed that A* search solves the Rubik’s
cube using shorter solutions in less time than MCTS [1].

##  3 Preliminaries

###  3.1 Deep Approximate Value Iteration

Value iteration [23] is a dynamic programming algorithm and a central
algorithm in reinforcement learning [4, 5, 27] that iteratively improves a
cost-to-go function $J$, that estimates the cost to go to from a given state
to the closest goal state via a shortest path. This cost-to-go function can be
readily used as a heuristic function for A* search.

In traditional value iteration, $J$ takes the form of a lookup table where the
cost-to-go $J(s)$ is stored for each possible state $s$. Value iteration loops
through each state $s$ and computes an updated $J^{\prime}(s)$ using the
Bellman equation:

$J^{\prime}(s)=\min_{a}\sum_{s^{\prime}}P^{a}(s,s^{\prime})(g^{a}(s,s^{\prime})+\gamma
J(s^{\prime}))$ (1)

Here $P^{a}(s,s^{\prime})$ is the transition matrix, representing the
probability of transitioning from state $s$ to state $s^{\prime}$ by taking
action $a$; $g^{a}(s,s^{\prime})$ is the transition cost, the cost associated
with transitioning from state $s$ to $s^{\prime}$ by taking action $a$; and
$\gamma\in[0,1]$ is the discount factor. The action $a$ is an action in a set
of actions $\mathcal{A}$. Value iteration has been shown to converge to the
optimal cost-to-go, $j_{*}$ [6]. That is, $j_{*}(s)$ will return the cost of a
shortest path to the closest goal state for every state $s$.

In the case of the Rubik’s cube, all transitions are deterministic. This is
also generally the case for problems solved with A* search. Therefore, we can
simplify Equation 1 as follows:

$J^{\prime}(s)=\min_{a}(g^{a}(s,A(s,a))+\gamma J(A(s,a)))$ (2)

where $A(s,a)$ is the state obtained from taking action $a$ in state $s$. We
set all transition costs to 1 and set $\gamma$ to 1 for all experiments.

However, representing $J$ as a lookup table is too memory intensive for
problems with large state spaces. For instance, the Rubik’s cube has
$4.3\times 10^{19}$ possible states. Therefore, we turn to approximate value
iteration [5] where $J$ is represented as a parameterized function,
$\operatorname{\mathit{j_{\theta}}}$, with parameters
$\operatorname{\mathit{\theta}}$. We choose to represent
$\operatorname{\mathit{j_{\theta}}}$ as a deep neural network (DNN). The
parameters $\operatorname{\mathit{\theta}}$ are learned by using stochastic
gradient descent to minimize the following loss function:

$L(\operatorname{\mathit{\theta}})=(\min_{a}{g^{a}(s,A(s,a))+\gamma
j_{\operatorname{\mathit{\theta}}^{-}}(A(s,a))}-\operatorname{\mathit{j_{\theta}}})^{2}$
(3)

Where $\operatorname{\mathit{\theta}}^{-}$ are the parameters for the “target”
DNN that is used to compute the updated cost-to-go. Using a target DNN has
been shown to result in a more stable training process. The parameters
$\operatorname{\mathit{\theta}}^{-}$ are periodically updated to
$\operatorname{\mathit{\theta}}$ during training. While we cannot guarantee
convergence to $j_{*}$, approximate value iteration has been shown to
approximate $j_{*}$ [5]. This combination of deep neural networks and
approximate value iteration is referred to as deep approximate value iteration
(DAVI).

###  3.2 A* Search

A* search [14] is an informed search algorithm which finds a path between the
node, $n_{0}$, associated with the start state, $s_{0}$, and a node, $n_{g}$,
associated with a goal state, $s_{g}$, in a set of goal states. A* search
maintains a priority queue, OPEN, from which it iteratively removes and
expands the node with the lowest cost and a dictionary, CLOSED, that maps
nodes that have already been generated to their path costs. The cost of each
node is $f(n)=g(n)+h(n)$, where $g(n)$ is the path cost, the distance between
$n_{0}$ and $n$, and $h(n)$ is the heuristic value, the estimated distance
between the state associated with $n$ and the nearest goal state. After a node
is expanded, its children that are not already in CLOSED are added to CLOSED
and then pushed to OPEN. If a child node $n$ is already in CLOSED, but a less
costly path from $n_{0}$ to $n$ has been encountered, then the path cost of
$n$ is updated in CLOSED and $n$ is added to OPEN. The algorithm starts with
only $n_{0}$ in OPEN and terminates when the node associated with a goal state
is removed from OPEN. In this work, the heuristic function is a DNN
$\operatorname{\mathit{j_{\theta}}}$. Pseudocode for the A* search algorithm
is given in Algorithm 1.

Algorithm 1 A* Search

Input: starting state $s_{0}$, DNN $\operatorname{\mathit{j_{\theta}}}$

OPEN $\leftarrow$ priority queue

CLOSED $\leftarrow$ dictionary that maps nodes to path costs

$n_{0}=\textrm{NODE}(s=s_{0},g=0)$

$c_{0}=\operatorname{\mathit{j_{\theta}}}(s_{0})$

Push $n_{0}$ to OPEN with cost $c_{0}$

while not $\textrm{IS\\_EMPTY}(\textrm{OPEN})$ do

$n=\textrm{POP(OPEN)}$

$s=n.s$

if $\textrm{IS\\_GOAL}(s)$ then

return $\textrm{PATH\\_TO\\_GOAL}(n)$

end if

for $a$ in $0$ to $|\mathcal{A}|$ do

$s^{\prime}=A(s,a)$

$g^{\prime}=g^{a}(s,s^{\prime})+n.g$

$n^{\prime}=\textrm{NODE}(s=s^{\prime},g=g^{\prime})$

if $n^{\prime}$ not in CLOSED or $g^{\prime}<\textrm{CLOSED}[n^{\prime}]$ then

$\textrm{CLOSED}[n^{\prime}]=g^{\prime}$

$c^{\prime}=\operatorname{\mathit{j_{\theta}}}(s^{\prime})$

Push $n^{\prime}$ to OPEN with cost $c^{\prime}$

end if

end for

end while

return failure

###  3.3 DeepCubeA

DeepCubeA [1] learns a cost-to-go function
$\operatorname{\mathit{j_{\theta}}}$ using DAVI and then uses that function as
a heuristic function for A* search. The states used for training
$\operatorname{\mathit{j_{\theta}}}$ with DAVI are generated by randomly
scrambling the goal state between 0 and $K$ times. This allows learning to
propagate from the goal state to all other states in the training set.

Because the learned heuristic function is a DNN, computing heuristic values
can make A* search computationally expensive. To alleviate this issue, one can
take advantage of the parallelism provided by graphics processing units (GPUs)
by expanding the $N$ lowest cost nodes and computing their heuristic values in
parallel. Furthermore, even with a computationally cheap and informative
heuristic, A* search can be both time and memory intensive. To address this,
one can trade potentially more costly solutions with potentially faster
runtimes and less memory usage with a variant of A* search called weighted A*
search [22]. Weighted A* search computes the cost of each node as
$f(n)=\lambda g(n)+h(n)$ where $\lambda\in[0,1]$ is a scalar weighting. This
combination of expanding $N$ nodes at every iteration and weighting the path
cost by $\lambda$ is referred to as batch-weighted A* search (BWAS).

##  4 Methods

###  4.1 Q-learning

Instead of learning a function, $\operatorname{\mathit{j_{\theta}}}$, that
maps a state, $s$, to its cost-to-go, one can learn a function,
$\operatorname{\mathit{q_{\phi}}}$, that maps $s$ to its Q-factors, which is a
vector containing $Q(s,a)$ for all actions $a$ [6]. In a deterministic
environment, the Q-factor is defined as:

$Q(s,a)=g^{a}(s,A(s,a))+\gamma J(A(s,a))$ (4)

where $J(A(s,a))$ can be expressed in terms of $Q$ with
$J(A(s,a))=\min_{a^{\prime}}{Q(A(s,a),a^{\prime})}$. Learning $Q$ by
iteratively updating the left-hand side of (4) toward its right-hand side is
known as Q-learning [28]. Like for DAVI, $Q$ is represented as a parameterized
function, $\operatorname{\mathit{q_{\phi}}}$, and we choose a deep neural
network for $\operatorname{\mathit{q_{\phi}}}$. This is also known as a deep
Q-network (DQN) [21]. The architecture of the DQN is constructed such that the
input is the state, $s$, and the output is a vector that represents
$\operatorname{\mathit{q_{\phi}}}(s,a)$ for all actions $a$. The parameters
$\operatorname{\mathit{\phi}}$ are learned using stochastic gradient descent
to minimize the loss function:

$L(\operatorname{\mathit{\phi}})=(g^{a}(s,A(s,a))+\gamma\min_{a^{\prime}}{q_{\operatorname{\mathit{\phi}}^{-}}(A(s,a),a^{\prime})}-\operatorname{\mathit{q_{\phi}}}(s,a))^{2}$
(5)

Just like in DAVI, the parameters $\operatorname{\mathit{\phi}}^{-}$ of the
target DNN are periodically updated to $\operatorname{\mathit{\phi}}$ during
training.

Similar to value iteration, Q-learning has been shown to converge to the
optimal Q-factors, $q_{*}$, in the tabular case [28]. In the approximate case,
Q-learning has a computational advantage over DAVI because, while the number
of parameters of the DQN grows with the size of the action space, the number
of forward passes needed to compute the loss function stays constant for each
update. We will show in our results that, in large action spaces, the training
time for Q-learning can be up to 127 times faster than DAVI.

###  4.2 AQ* Search

We present AQ* search, a search algorithm that builds on A* search to take
advantage of DQNs. AQ* search uses tuples containing a node and an action,
which we will refer to as node_actions, to search for a path to the goal. The
cost of a node_action with node $n$ and action $a$ is
$g(n)+g^{a}(s,s^{\prime})+h(n^{\prime})$ where $s$ is the state associated
with node $n$ and $s^{\prime}=A(s,a)$ is the successor of $s$ when taking
action $a$, and $s^{\prime}$ is associated with node $n^{\prime}$. The
Q-factor $Q(s,a)$ is equal to $g^{a}(s,s^{\prime})+h(n^{\prime})$. Therefore,
using DQNs, the transition cost and cost-to-go of all child nodes can be
computed using $\operatorname{\mathit{q_{\phi}}}$ without having to expand
$n$.

At every iteration, AQ* search pops a node_action, $(n,a)$, from OPEN, creates
a new state, $s^{\prime}=A(s,a)$, by applying action $a$ to the state $s$
associated with $n$, and generates a new node $n^{\prime}$ with corresponding
state $s^{\prime}$. Instead of expanding $n^{\prime}$, AQ* search applies the
DQN to $s^{\prime}$ to obtain the sum of the transition cost and the cost-to-
go for all of its children. AQ* search then pushes the new node_actions
$(n^{\prime}$, $a^{\prime})$ to OPEN for all actions $a^{\prime}$ where the
cost is computed by summing the path cost of $n$ and the output of the DQN
corresponding to action $a^{\prime}$. In AQ* search, the only part that
depends on the size of the action space is pushing nodes to OPEN. Unlike A*
search, no nodes are expanded and the heuristic function only needs to be
applied once per iteration. Pseudocode for the AQ* search algorithm is given
in Algorithm 2. In our results, we will show that AQ* search is orders of
magnitude faster than A* search.

###  4.3 DeepCubeAQ

DeepCubeAQ uses the same process as DeepCubeA to generate states for training.
Instead of DAVI, DeepCubeAQ uses Q-learning to train a DQN. This DQN is then
used in AQ* search. Like DeepCubeA, DeepCubeAQ also performs AQ* in batches of
size $N$ and with a weight $\lambda$. We also note that the cost of a
node_action for the weighted version of AQ* is $\lambda
g(n)+g^{a}(s,s^{\prime})+h(n^{\prime})$. However, $\lambda$ should also be
applied to the transition cost $g^{a}(s,s^{\prime})$. This does not happen
because the transition cost is not computed separately from the cost-to-go. In
this work, all the transition costs are the same, therefore, this constant
offset does not affect the order in which nodes are expanded. However, in
future work, this could be remedied by training a DQN that separates the
transition cost and the cost-to-go of the subsequent state.

Algorithm 2 AQ* Search

Input: starting state $s_{0}$, DQN $\operatorname{\mathit{q_{\phi}}}$

OPEN $\leftarrow$ priority queue

CLOSED $\leftarrow$ dictionary that maps nodes to path costs

$n_{0}=\textrm{NODE}(s=s_{0},g=0)$

$a=\textrm{NO\\_OP}$

$c_{0}=\min_{a^{\prime}}{q(s_{0},a^{\prime})}$

Push $(n_{0},a)$ to OPEN with cost $c_{0}$

while not $\textrm{IS\\_EMPTY}(\textrm{OPEN})$ do

$(n,a)=\textrm{POP(OPEN)}$

$s=n.s$

$s^{\prime}=A(s,a)$

if $\textrm{IS\\_GOAL}(s^{\prime})$ then

return $\textrm{PATH\\_TO\\_GOAL}(n,a)$

end if

$g^{\prime}=n.g+g^{a}(s,s^{\prime})$

$n^{\prime}=\textrm{NODE}(s=s^{\prime},g=g^{\prime})$

if $n^{\prime}$ not in CLOSED or $g^{\prime}<\textrm{CLOSED}[n^{\prime}]$ then

$\textrm{CLOSED}[n^{\prime}]=g^{\prime}$

$\mathbf{q}=\operatorname{\mathit{q_{\phi}}}(s^{\prime},.)$

for $a^{\prime}$ in $0$ to $|\mathcal{A}|$ do

$c^{\prime}=g^{\prime}+\mathbf{q}[i]$

Push $(n^{\prime},a^{\prime})$ to OPEN with cost $c^{\prime}$

end for

end if

end while

return failure

##  5 Results

The Rubik’s cube action space has 12 different actions: each of the six faces
can be turned clockwise or counterclockwise. We refer to this action space as
RC(12). To determine how well DeepCubeAQ can find solutions in large action
spaces, we add meta-actions to the Rubik’s cube action space, creating RC(156)
and RC(1884). RC(156) has all the actions in RC(12) plus all combinations of
actions of size two (144). RC(1884) has all the actions in RC(156) plus all
combinations of actions of size three (1728). To ensure none of these
additional meta-actions are redundant, the cost for all meta-actions is also
set to one. The machines we use for training and search have 48 2.4 GHz Intel
Xeon central processing units (CPUs), 190 GB of random access memory, and two
32GB NVIDIA V100 GPUs.

We train the cost-to-go function with the same architecture described in [1],
which has a fully connected layer of size 5,000, followed by another fully
connected layer of size 1,000, followed by four fully connected residual
blocks of size 1,000 with two hidden layers per residual block [15]. The DQN
also has the same architecture with the exception that the output is a vector
that estimates the cost-to-go for taking every possible action. For generating
training states, the number of times we scramble the Rubik’s cube, $K$, is set
to 30. For Q-learning, we select actions according to a Boltzmann distribution
where each action $a$ is selected with probability:

$p_{s,a}=\frac{e^{(\operatorname{\mathit{q_{\phi}}}(s,a)/T)}}{\sum_{a^{\prime}=1}^{|\mathcal{A}|}e^{(\operatorname{\mathit{q_{\phi}}}(s,a^{\prime})/T)}}$
(6)

where we set the temperature $T=\frac{1}{3}$.

We train with a batch size of 10,000 for 1.2 million iterations using the ADAM
optimizer [18]. We update the target networks with the same schedule defined
in the DeepCubeA source code [2]. However, as the size of the action space
increases, training with a batch size this large becomes infeasible for
DeepCubeA. Table 1 shows that DeepCubeA would take over a month to train on
RC(156) and almost a year to train on RC(1884). Therefore, we reduce the batch
size in proportion to the differences in the size of the action space with
RC(12). Since RC(156) has 13 times more actions, we train DeepCubeA with a
batch size of 769 and since RC(1884) has 157 times more actions, we train
DeepCubeA with a batch size of 63.

Table 1: The table shows the number of training iterations per second with a
batch size of 10,000 and the projected number of days to train for 1.2 million
iterations. DeepCubeA (DCA) is significantly slower than DeepCubeAQ (DCQ),
especially when the size of the action space is large.
Puzzle | Method | Itrs/Sec | Train Time
---|---|---|---
RC(12) | DCA | 3.96 | 3.5d
DCQ | 8.55 | 1.6d
RC(156) | DCA | 0.42 | 33d
DCQ | 7.46 | 1.9d
RC(1884) | DCA | 0.04 | 347d
DCQ | 5.08 | 2.7d

###  5.1 Performance During Search

The original work on DeepCubeA used $\lambda=0.6$ and $N=10000$ for BWAS.
However, since these search parameters create a tradeoff between speed, memory
usage, and path cost, we also examine the performance with different parameter
settings to understand how A* search and AQ* search compare along these
dimensions. Therefore, we try all combinations of
$\lambda\in\\{0.0,0.2,0.4,0.6,0.8,1.0\\}$ and $N\in\\{100,1000,10000\\}$. For
each method and each action space, we prune all combinations that cause our
machine to run out of memory or that require over 24 hours to complete. We use
the same 1,000 test states used in [1], where each test state was obtained by
scrambling the Rubik’s cube between 1,000 and 10,000. Due to the increase in
solving time from DeepCubeA, for RC(156), we use a subset of 100 states and
for RC(1884), we use a subset of 20 states. We examine the results both in
terms of the lowest path cost averaged over all the test states as well as
hypothetical cases where there is some threshold for an acceptable average
path cost.

(a) RC(12)

(b) RC(156)

(c) RC(1884)

Figure 1: The figures shows the relationship between the average path cost and
the average time to find a solution. The y-axis has a logarithmic scale. Each
dot represents a search parameter setting. The dashed line represents the
lowest average path cost found. The solid line represents the fastest solution
time as a function of a hypothetical threshold for an acceptable average path
cost. For almost all thresholds, DeepCubeAQ is significantly faster than
DeepCubeA. For RC(1884), DeepCubeAQ is up to 129 times faster than DeepCubeA.

(a) RC(12)

(b) RC(156)

(c) RC(1884)

Figure 2: The figures shows the relationship between the average path cost and
the average number of nodes generated. The y-axis has a logarithmic scale.
Each dot represents a search parameter setting. The dashed line represents the
lowest average path cost found. The solid line represents the fewest number of
nodes generated as a function of a hypothetical threshold for an acceptable
average path cost. For almost all thresholds, DeepCubeAQ generates
significantly fewer nodes than DeepCubeA. For RC(1884), DeepCubeAQ generates
up to 1288 times fewer nodes than DeepCubeA.

(a) RC(12)

(b) RC(156)

(c) RC(1884)

Figure 3: Percentage of training states solved with a greedy policy as a
function of training iteration.

The results show that, as the size of the action space increases, the speed
and memory advantages of DeepCubeAQ becomes significant. In the largest action
space, RC(1884), the lowest average path cost is the same for DeepCubeA and
DeepCubeAQ, however, DeepCubeAQ is orders of magnitude faster and more memory
efficient. In the case of RC(12), the lowest average path cost that DeepCubeA
finds is 21.493 while for DeepCubeAQ it is 21.529. This is on par with the
original DeepCubeA results that obtained an average path cost of 21.50. In the
case of RC(156), the lowest average path cost that DeepCubeA finds is 11.15
while for DeepCubeAQ it is 11.38. Finally, in the case of RC(1884), the lowest
average path cost for both DeepCubeA and DeepCubeAQ is 7.9. The average cost
becomes smaller as the size of the action space increases because the
additional meta-actions allow the Rubik’s cube to be solved in fewer moves.

In Figure 1, we can see the relationship between the average path cost and the
time to find a solution for all search parameter settings. In Figure 2, we can
see the relationship between the average path cost and the number of nodes
generated for all search parameter settings. The figures show that, for almost
any possible path cost threshold, DeepCubeAQ is significantly faster and
generates significantly fewer nodes than DeepCubeA. In the most extreme case,
the cheapest average path cost for DeepCubeA and DeepCubeAQ is identical for
RC(1884), however, DeepCubeAQ is 129 times faster and generates 1228 times
fewer nodes than DeepCubeA. These ratios for different path costs thresholds
are show in Tables 2, 3, and 4.

When comparing DeepCubeA and DeepCubeAQ to themselves for different action
spaces, Table 5 shows that, though RC(1884) has 157 times more actions than
RC(12), DeepCubeAQ only takes 3.7 times as long to find a solution and
generates only 2.3 times as many nodes. On the other hand, in this same
scenario, DeepCubeA takes 37 times as long and generates 62.7 times as many
nodes.

Table 2: The ratio between DeepCubeA and DeepCubeAQ for the solution time and
number of nodes generated for hypothetical acceptable path cost thresholds for
RC(12). DeepCubeA only outperforms DeepCubeAQ in one instance.
| Path Cost Thresh
---|---
| 22 | 24 | 26 | 30
Time | 0.8 | 1.8 | 5.1 | 1.7
Nodes Gen | 1.4 | 1.9 | 36.2 | 6.8
Table 3: The ratio between DeepCubeA and DeepCubeAQ for the solution time and
number of nodes generated for hypothetical acceptable path cost thresholds for
RC(156). DeepCubeAQ outperforms DeepCubeA in all instances.
| Path Cost Thresh
---|---
| 22 | 24 | 26 | 30
Time | 51.5 | 23.1 | 10.5 | 10.5
Nodes Gen | 92.0 | 64.0 | 34.5 | 34.5
Table 4: The ratio between DeepCubeA and DeepCubeAQ for the solution time and
number of nodes generated for hypothetical acceptable path cost thresholds for
RC(1884). DeepCubeAQ is up to 129 times faster and generates up to 1288 times
fewer nodes.
| Path Cost Thresh
---|---
| 22 | 24 | 26 | 30
Time | 129.7 | 38.2 | 28.5 | 72.7
Nodes Gen | 1288.4 | 342.3 | 282.8 | 725.0
Table 5: The table shows each puzzle with an action space augmented with meta-
actions along with the ratio between the size of the action space and the size
of the action space for RC(12). It then shows the ratio for the time and
number of nodes generated for each method when compared to its own performance
on RC(12) averaged over all search parameter settings with the standard
deviation in parenthesis. DeepCubeAQ has much better performance for both
metrics. For RC(156) DeepCubeAQ finds solutions in even less time than it did
for RC(12) due to the addition of meta-actions.
Puzzle | Actions | Method | Time | Nodes Gen
---|---|---|---|---
RC(156) | x13 | DCA | 3.5(1.6) | 8.7(2.2)
DCQ | 0.9(0.7) | 1.4(1.3)
RC(1884) | x157 | DCA | 37.0(6.5) | 62.7(5.2)
DCQ | 3.7(4.0) | 2.3(3.6)

###  5.2 Performance During Training

To monitor performance during training, we track the percentage of states that
are solved by simply behaving greedily with respect to the cost-to-go
function. We generate these states the same way we generate the training
states. Figure 3 shows this metric as a function of training time. The results
show that, in the case of RC(12), DeepCubeA is slightly better than
DeepCubeAQ. In RC(156) and RC(1884), even though the batch size for DeepCubeA
is smaller, the performance is on par with DeepCubeAQ. This may be due to the
fact that DeepCubeA is only learning the cost-to-go for a single state while
DeepCubeAQ must learn the sum of the transition cost and cost-to-go for all
possible next states.

##  6 Discussion

As the size of the action space increases, DeepCubeAQ becomes significantly
more effective than DeepCubeA in terms of training time, solution time, and
the number of nodes generated. In the largest action space, DeepCubeAQ is
orders of magnitude faster and generates orders of magnitude fewer nodes than
DeepCubeA while finding solutions with the same average path cost. For smaller
action spaces, while DeepCubeAQ is almost always faster and more memory
efficient, DeepCubeA is capable of finding solutions that are slightly cheaper
than DeepCubeAQ. This could be due to the difference in what
$\operatorname{\mathit{j_{\theta}}}$ and $\operatorname{\mathit{q_{\phi}}}$
are being trained to do. Since the forward pass performed by the DQN,
$\operatorname{\mathit{q_{\phi}}}$, is the same as doing a one-step lookahead
with $\operatorname{\mathit{j_{\theta}}}$, perhaps learning is more difficult
for the DQN. However, since training and search are significantly faster for
DeepCubeAQ, this gap could be closed with longer training times and searching
with larger values of $\lambda$ or $N$.

While the DQN used in this work was for a fixed action space, modifying
architectures such as graph convolutional policy networks [30] to estimate
Q-factors would allow DeepCubeAQ to be used on problems with variable action
spaces. This would have a direct application to problems with large, but
variable, action spaces such as chemical synthesis, molecular optimization,
theorem proving, program synthesis, and web navigation.

A* search is guaranteed to find a shortest path if the heuristic function is
admissible. An admissible heuristic function is a function that never
overestimates the cost of a shortest path. While there is little work on
learning admissible heuristic functions using nonlinear function approximators
[11], future work can extend these theoretical guarantees to AQ*.

##  7 Conclusion

The DeepCubeAQ algorithm uses Q-learning to train a DQN to be used as a
heuristic function in a novel variant of A* search called AQ* search. AQ*
search eliminates the need for node expansions. When increasing the size of
the action space by 157 times, AQ* search only takes 3.7 times as long and
generates only 2.3 times more nodes. When compared to A* search, AQ* search is
up to 129 times faster and generates up to 1288 times fewer nodes. The ability
that DeepCubeAQ has to efficiently scale up to large action spaces could play
a significant role in finding solutions to many important problems with large
action spaces.

## References

  * Agostinelli et al. [2019] Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi.  Solving the Rubik’s cube with deep reinforcement learning and search.  _Nature Machine Intelligence_ , 1(8):356–363, 2019.
  * Agostinelli et al. [2020] Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi.  DeepcubeA.  https://github.com/forestagostinelli/DeepCubeA, 2020.
  * Arfaee et al. [2011] Shahab Jabbari Arfaee, Sandra Zilles, and Robert C Holte.  Learning heuristic functions for large state spaces.  _Artificial Intelligence_ , 175(16-17):2075–2098, 2011.
  * Bellman [1957] Richard Bellman.  _Dynamic Programming_.  Princeton University Press, 1957.
  * Bertsekas and Tsitsiklis [1996] Dimitri P Bertsekas and John N Tsitsiklis.  _Neuro-dynamic programming_.  Athena Scientific, 1996.  ISBN 1-886529-10-8.
  * Bertsekas et al. [1995] Dimitri P Bertsekas, Dimitri P Bertsekas, Dimitri P Bertsekas, and Dimitri P Bertsekas.  _Dynamic programming and optimal control_ , volume 1.  Athena scientific Belmont, MA, 1995.
  * Chen et al. [2020] Binghong Chen, Chengtao Li, Hanjun Dai, and Le Song.  Retro*: learning retrosynthetic planning with neural guided A* search.  In _International Conference on Machine Learning_ , pages 1608–1616. PMLR, 2020.
  * Chen and Wei [2011] Hung-Che Chen and Jyh-Da Wei.  Using neural networks for evaluation in heuristic search algorithm.  In _Twenty-Fifth AAAI Conference on Artificial Intelligence_ , 2011\.
  * Coulom [2006] Rémi Coulom.  Efficient selectivity and backup operators in monte-carlo tree search.  In _International conference on computers and games_ , pages 72–83. Springer, 2006.
  * Culberson and Schaeffer [1998] Joseph C Culberson and Jonathan Schaeffer.  Pattern databases.  _Computational Intelligence_ , 14(3):318–334, 1998.
  * Ernandes and Gori [2004] Marco Ernandes and Marco Gori.  Likely-admissible and sub-symbolic heuristics.  In _Proceedings of the 16th European Conference on Artificial Intelligence_ , pages 613–617. Citeseer, 2004.
  * Felner et al. [2012] Ariel Felner, Meir Goldenberg, Guni Sharon, Roni Stern, Tal Beja, Nathan Sturtevant, Jonathan Schaeffer, and Robert Holte.  Partial-expansion A* with selective node generation.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 26, 2012.
  * Feng et al. [2020] Dieqiao Feng, Carla P Gomes, and Bart Selman.  A novel automated curriculum strategy to solve hard sokoban planning instances.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Hart et al. [1968] Peter E Hart, Nils J Nilsson, and Bertram Raphael.  A formal basis for the heuristic determination of minimum cost paths.  _IEEE transactions on Systems Science and Cybernetics_ , 4(2):100–107, 1968.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Hornik et al. [1989] Kurt Hornik, Maxwell Stinchcombe, and Halbert White.  Multilayer feedforward networks are universal approximators.  _Neural networks_ , 2(5):359–366, 1989.
  * Jin and Kim [2020] Jungha Jin and Keecheon Kim.  3D cube algorithm for the key generation method: Applying deep neural network learning-based.  _IEEE Access_ , 8:33689–33702, 2020.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Laterre et al. [2018] Alexandre Laterre, Yunguan Fu, Mohamed Khalil Jabri, Alain-Sam Cohen, David Kas, Karl Hajjar, Torbjorn S Dahl, Amine Kerkeni, and Karim Beguir.  Ranked reward: Enabling self-play reinforcement learning for combinatorial optimization.  _arXiv preprint arXiv:1807.01672_ , 2018.
  * McAleer et al. [2019] Stephen McAleer, Forest Agostinelli, Alexander Shmakov, and Pierre Baldi.  Solving the Rubik’s cube without human knowledge.  2019\.
  * Mnih et al. [2015] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, 2015.
  * Pohl [1970] Ira Pohl.  Heuristic search viewed as path finding in a graph.  _Artificial intelligence_ , 1(3-4):193–204, 1970\.
  * Puterman and Shin [1978] Martin L Puterman and Moon Chirl Shin.  Modified policy iteration algorithms for discounted markov decision problems.  _Management Science_ , 24(11):1127–1137, 1978\.
  * Schmidhuber [2015] Jürgen Schmidhuber.  Deep learning in neural networks: An overview.  _Neural networks_ , 61:85–117, 2015.
  * Silver et al. [2016] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  _nature_ , 529(7587):484–489, 2016.
  * Silver et al. [2018] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al.  A general reinforcement learning algorithm that masters chess, shogi, and go through self-play.  _Science_ , 362(6419):1140–1144, 2018.
  * Sutton and Barto [1998] Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_ , volume 1.  MIT press Cambridge, 1998.
  * Watkins and Dayan [1992] Christopher JCH Watkins and Peter Dayan.  Q-learning.  _Machine learning_ , 8(3-4):279–292, 1992.
  * Yoshizumi et al. [2000] Takayuki Yoshizumi, Teruhisa Miura, and Toru Ishida.  A* with partial expansion for large branching factor problems.  In _AAAI/IAAI_ , pages 923–929, 2000.
  * You et al. [2018] Jiaxuan You, Bowen Liu, Rex Ying, Vijay Pande, and Jure Leskovec.  Graph convolutional policy network for goal-directed molecular graph generation.  _arXiv preprint arXiv:1806.02473_ , 2018.
  * Zhang et al. [2020] Yuan-Hang Zhang, Pei-Lin Zheng, Yi Zhang, and Dong-Ling Deng.  Topological quantum compiling with reinforcement learning.  _Physical Review Letters_ , 125(17):170501, 2020\.