Lessons from AlphaZero for Optimal, Model Predictive, and Adaptive Control

Description

The purpose of this book is to propose and develop a new conceptual framework for approximate Dynamic Programming (DP) and Reinforcement Learning (RL). This framework centers around two algorithms, which are designed largely independently of each other and operate in synergy through the powerful mechanism of Newton's method. We call these the off-line training and the on-line play algorithms; the names are borrowed from some of the major successes of RL involving games. Primary examples are the recent (2017) AlphaZero program (which plays chess), and the similarly structured and earlier (1990s) TD-Gammon program (which plays backgammon). In these game contexts, the off-line training algorithm is the method used to teach the program how to evaluate positions and to generate good moves at any given position, while the on-line play algorithm is the method used to play in real time against human or computer opponents. Both AlphaZero and TD-Gammon were trained off-line extensively using neural networks and an approximate version of the fundamental DP algorithm of policy iteration. Yet the AlphaZero player that was obtained off-line is not used directly during on-line play (it is too inaccurate due to approximation errors that are inherent in off-line neural network training). Instead a separate on-line player is used to select moves, based on multistep lookahead minimization and a terminal position evaluator that was trained using experience with the off-line player. The on-line player performs a form of policy improvement, which is not degraded by neural network approximations. As a result, it greatly improves the performance of the off-line player. Similarly, TD-Gammon performs on-line a policy improvement step using one-step or two-step lookahead minimization, which is not degraded by neural network approximations. To this end it uses an off-line neural network-trained terminal position evaluator, and importantly it also extends its on-line lookahead by rollout (simulation with the one-step lookahead player that is based on the position evaluator). Significantly, the synergy between off-line training and on-line play also underlies Model Predictive Control (MPC), a major control system design methodology that has been extensively developed since the 1980s. This synergy can be understood in terms of abstract models of infinite horizon DP and simple geometrical constructions, and helps to explain the all-important stability issues within the MPC context. An additional benefit of policy improvement by approximation in value space, not observed in the context of games (which have stable rules and environment), is that it works well with changing problem parameters and on-line replanning, similar to indirect adaptive control. Here the Bellman equation is perturbed due to the parameter changes, but approximation in value space still operates as a Newton step. An essential requirement here is that a system model is estimated on-line through some identification method, and is used during the one-step or multistep lookahead minimization process. In this monograph we aim to provide insights (often based on visualization), which explain the beneficial effects of on-line decision making on top of off-line training. In the process, we will bring out the strong connections between the artificial intelligence view of RL, and the control theory views of MPC and adaptive control. Moreover, we will show that in addition to MPC and adaptive control, our conceptual framework can be effectively integrated with other important methodologies such as multiagent systems and decentralized control, discrete and Bayesian optimization, and heuristic algorithms for discrete optimization. One of our principal aims is to show, through the algorithmic ideas of Newton's method and the unifying principles of abstract DP, that the AlphaZero/TD-Gammon methodology of approximation in value space and rollout applies very broadly to deterministic and stochastic optimal control problems. Newton's method here is used for the solution of Bellman's equation, an operator equation that applies universally within DP with both discrete and continuous state and control spaces, as well as finite and infinite horizon.

Get the book

Amazon.com

Search the book

eBay.com

Search the book

Similar books

• 

  Rollout, Policy Iteration, and Distributed Reinforcement Learning

  By Dimitri Bertsekas

  Reinforcement Learning and Dynamic Programming Using Function Approximators, CRC Press, N. Y. [BBD10b] Busoniu, L., ... “Ellipsoidal Reachable Sets of Linear Time-Varying Continuous and Discrete Systems in Control and Estimation ...

• 

  Reinforcement Learning and Optimal Control

  By Dimitri Bertsekas

  This book considers large and challenging multistage decision problems, which can be solved in principle by dynamic programming (DP), but their exact solution is computationally intractable.

• 

  Abstract Dynamic Programming: 3rd Edition

  By Dimitri Bertsekas

  This is the 3rd edition of a research monograph providing a synthesis of old research on the foundations of dynamic programming (DP), with the modern theory of approximate DP and new research on semicontractive models.

• 

  Parallel and Distributed Computation: Numerical Methods

  By Dimitri Bertsekas, John Tsitsiklis

  This highly acclaimed work, first published by Prentice Hall in 1989, is a comprehensive and theoretically sound treatment of parallel and distributed numerical methods.

• 

  Stochastic Optimal Control: The Discrete Time Case

  By Dimitri P. Bertsekas

  Stochastic Optimal Control: The Discrete Time Case

• 

  Dynamic Programming and Optimal Control

  By Dimitri P. Bertsekas

  The text contains many illustrations, worked-out examples, and exercises."--Publisher's website.

• 

  Reinforcement Learning, second edition: An Introduction

  By Richard S. Sutton, Andrew G. Barto

  Technical Report CUED/F-INFENG/TR 166. Engineering Department, Cambridge ... Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I., Wen, Z. (2018). ... Saddoris, M. P., Cacciapaglia, F., Wightmman, R. M., Carelli, R. M. (2015).

• 

  Artificial Intelligence in Asset Management

  By Jürgen Branke, Söhnke M. Bartram, Mehrshad Motahari

  Artificial intelligence (AI) has grown in presence in asset management and has revolutionized the sector in many ways.

• 

  Reinforcement Learning and Stochastic Optimization: A Unified Framework for Sequential Decisions

  By Warren B. Powell

  This book highlights twelve types of uncertainty that might enter any model and pulls together the diverse set of methods for making decisions, known as policies, into four fundamental classes that span every method suggested in the ...

• 

  Algorithms for Decision Making

  By Mykel J. Kochenderfer, Tim A. Wheeler, Kyle H. Wray

  The book first addresses the problem of reasoning about uncertainty and objectives in simple decisions at a single point in time, and then turns to sequential decision problems in stochastic environments where the outcomes of our actions ...