Learning by Consequence: A Narrative Review of Reinforcement Learning from Thorndike's Law of Effect to Deep Q-Networks and AlphaGo

Abstract

Reinforcement learning---learning what to do from reward and punishment rather than from instruction---unifies animal psychology, optimal control, and machine learning into one computational program, and its deep-learning era delivered the field's most visible artificial intelligence achievements. This article presents a narrative review of the canonical line: Thorndike's 1911 law of effect, Bellman's 1957 dynamic programming, Samuel's 1959 checkers player, Sutton's 1988 temporal-difference learning, Watkins and Dayan's 1992 Q-learning, Tesauro's 1995 TD-Gammon, Sutton and Barto's 1998 synthesis, Mnih and colleagues' 2015 Deep Q-Network, Silver and colleagues' 2016 AlphaGo and 2017 AlphaGo Zero, Lillicrap and colleagues' continuous control with DDPG, and Schulman and colleagues' 2017 proximal policy optimization. The synthesis is organized around three themes: foundations, in which the credit-assignment problem received formal solutions in value functions and temporal difference; scaling, in which function approximation, experience replay, and self-play converted tabular theory into high-dimensional control; and algorithmic consolidation, in which actor-critic methods and policy gradients stabilized practice. It is concluded that reinforcement learning's contribution is a general grammar of goal-directed learning---and that its open problems, sample efficiency and reward specification, define the frontier between artificial and natural intelligence.