Introduction and Background:
David Silver is discussing a family of search algorithms, specifically focusing on AlphaZero. The goal is to unpack these algorithms, understand their building blocks, and investigate their potentials for improvement and new variant development.

Silver recognizes collaborations at DeepMind and his PhD thesis at the University of Alberta as crucial foundations for this talk.

Evolution of Search Algorithms:
The talk begins by discussing the evolution of search algorithms, starting with AlphaGo, which beat the human Go champion in 2016. This breakthrough combined neural networks with Monte Carlo tree search, utilizing a small amount of human data and knowledge.

The development of AlphaZero succeeded AlphaGo, which learned to play without any human knowledge, relying only on the known rules of the game. AlphaZero was then developed, which mastered multiple games (Go, Chess, and Shogi) at a superhuman level, using a single algorithm and knowing only the game rules.

The latest iteration, mu0, not only mastered the rules of various games but also learned them along the way, enabling it to master other environments with unknown dynamics.

AlphaZero and Its Implications:
AlphaZero started from zero prior knowledge, using a randomly initialized neural network, played thousands of self-play games, and after a few hours of training, defeated existing world champion programs in Chess, Shogi, and Go.

This self-play algorithm demonstrated that through the acquisition of knowledge and building on it, an AI could potentially understand more about these games than humans have discovered over thousands of years.

AlphaZero’s game strategies and play styles have led to reflections on game play by humans, resulting in several books about its strategies in different games. These books reveal how AlphaZero’s approaches have influenced human players and changed the way games are played and understood.

Focus on Fundamentals:
David Silver sets the agenda to go back to basics and focus on the underlying theory of various reinforcement learning algorithms. He plans to discuss algorithms such as Expecting Max Search, Monte Carlo Search, Nested Monte Carlo Search, and Alpha Zero Search.

The methods used to explain these algorithms will involve equations, diagrams, and pseudocode.

Common Characteristics of Algorithms:
All the algorithms under discussion have a common method: they evaluate a policy and estimate a value function.

The value function estimates the expected total reward for each state or each action within a state, termed as the state value function and the action value function, respectively.

Algorithms iteratively evaluate and improve policies using these value functions, with the aim to eventually arrive at the optimal value function and policy given enough time and resources.

Role of Backup Operators:
The concept of “backup operators” is introduced, represented by bold letters. These operators modify the value function or policy.

An algorithm is essentially a sequence or composition of these backup operators.

The primary goal is to find a composition of operators that will produce the optimal value and policy.

Types of Backups:
Two main kinds of backups are discussed: evaluation backups and improvement backups. The former evaluates the current policy and the latter improves the policy based on those values.

Backup diagrams, used to illustrate the dependencies involved in each backup, are also discussed.

Backup Operator Examples:
The Bellman evaluation backup operator is presented as an example. This operator computes the expected value for each state and updates the value function at the root state.

Improvement backups are achieved by updating the policy towards the action that has the maximum backed-up value.

Other backup operators like TD0, n-step TD backup, and Monte Carlo backups are also mentioned.

Sampling to Break Curse of Dimensionality:
Noting the high cost of the Bellman evaluation backups due to the consideration of the entire action and state space, Silver mentions a method to break the curse of dimensionality – by sampling.

Instead of considering all different successors, the backup can be achieved by sampling a pathway through the tree, and this sampling-based method leads to TD0 backup or n-step TD backup.

Composition of Backup Operators:
The composition of backup operators is an important concept introduced by Silver. By composing these operators in different orders, different results can be achieved.

Silver emphasizes that regardless of the operators used, if we repeatedly evaluate and improve using any of these operators infinitely often across the entire state space, the result will converge to the optimal value function and the optimal policy, an idea known as policy iteration.

Efficient Policy Iteration:
Towards the end of the discussion, Silver raises a key question about the efficiency of policy iteration. While the concept guarantees convergence to the optimal policy if applied infinitely, he asks which states should be prioritized for the iteration process to converge more rapidly and efficiently.

Concept of Search Control:
Search control refers to the strategy used to decide the order in which backup operations are applied in a state. There are many different strategies for search control, but the discussion focuses on two core ideas: recursion and rollouts.

Importance of Recursion in Search Control:
In recursion, improvements are made recursively at each successive state before performing a backup from the successor states. This approach essentially forms a search tree where the value and policy at each successor state are determined before backing up to the higher level.

If the problem structure is tree-like or even a directed acyclic graph (DAG), recursion provides a nice ordering of backups.

With recursion, once the right value of each successor state is computed, only a single backup is needed to ensure the correct value of a state. Recursion helps localize memory resources to the particular subtree being worked on, which is particularly useful when working with value functions or policies with vast memory requirements.

Rollouts as an Effective Strategy in Search Control:
Rollouts involve sampling future trajectories using the current policy, instead of considering the full exhaustive search tree. Rollouts focus on what’s likely to happen in the future according to your policy, ignoring improbable states. It allows for the correct calculation of the vast majority of values.

Importantly, rollouts enable deep search. As the computation grows exponentially with the depth of the search tree in an exhaustive depth-first search, rollouts break this “curse of dimensionality” by merely sampling. This allows for deep dives into the problem.

Combining Recursion and Rollouts: Recursive Rollout:
Recursive rollout attempts to combine the advantages of both recursion and rollouts. Examples include nested Monte Carlo search or nested Monte Carlo tree search.

The speaker argues that Alpha Zero, a highly successful AI algorithm, operates within the recursive rollout framework. At the outer level, it performs rollouts at the game level, and at the inner level, from each of the states it reaches, it performs inner rollouts within its Monte Carlo search.

Expecting Match Search:
Depth First Search is an example of expecting match search, used in stochastic environments. Search control in this case takes into consideration the expectation over the stochasticity of the environment.

Backup diagrams are used for evaluation and improvement backups.

Each recursion or search control procedure involves visiting successor states, invoking the same search control procedure, and applying evaluation and improvement backups.

The outcome is the value and policy for the state.

Rollout-Based Searches:
Newer and exciting search algorithms are based on rollouts.

Evaluation backups and improvement backups are combined using a search control diagram.

Monte Carlo Search involves visiting all states and actions from each rollout, updating only the root value and the root policy.

In contrast, Monte Carlo Tree Search (MCTS) updates all the intermediate states and actions that are visited along the way during rollouts. The MCTS process involves storing, caching, and improving all the values and policies encountered during the rollouts from a state.

Temporal Difference Search:
Another approach is the Temporal Difference (TD) search, which uses temporal difference backups, such as TD0, backing up from one step ahead.

This search still uses rollouts, but the evaluation backup at each step only looks one step ahead. So, for each of those states, updates occur only one step backwards.

Nested Monte Carlo Search:
The Nested Monte Carlo Search is a method that combines recursion and rollouts in Monte Carlo tree search. The approach uses recursion to perform additional rollouts from each state encountered during a rollout.

The nested rollouts undergo evaluation and improvement operations before the primary rollout is backed up. This method can be applied recursively to as many levels as needed.

The process is similar in the Nested Monte Carlo Tree Search, where inner rollouts are performed first followed by an outer backup using a Monte Carlo backup. The Monte Carlo backup could be replaced by Temporal Difference (TD) backup if preferred.

Pseudocode for Nested Monte Carlo Tree Search:
In a rollout procedure, actions are sampled from a policy and rewards are sampled from the environment/model iteratively until a terminal state or depth limit is reached.

In a search procedure, multiple rollouts are performed and evaluation backups are applied along the way to evaluate the process using Monte Carlo backups.

A nested Monte Carlo tree search includes a nested layer in the rollout procedure where, before proceeding at the current level of the algorithm, a search is performed one level lower, improving the value and policy.

Introduction of Function Approximators in RL:
Table lookup algorithms, although exact, are unfeasible in problems with large state spaces. Instead, function approximators like neural networks can be used.

A new projection operator is introduced that projects the results from lower-level searches onto a representation that the neural network can handle. The projection operator finds the best fit using the neural network parameters to backup targets, providing powerful algorithms when interleaved with evaluation and improvement backups. Every step involves evaluation, improvement, and a step of gradient descent to optimize parameters to fit the targets as well as possible.

Transient Approximations:
There are two methods of passing parameters in the function: call by reference and call by value. Using call by value allows for transient approximations, where a new set of parameters is instantiated each time the function recurses.

This approach enables the neural network to focus its resources on finding the best local approximation for the current point of nesting. This concept is akin to the depth of search idea but allows the consideration of a new approximation at every stage.

This strategy permits the memory resources to focus solely on the local search problem, compute the root value, discard the entire thing, and move to another part in the search.

AlphaZero’s Structure:
AlphaZero operates as a two-level nested Monte Carlo tree search with transient approximation.

The first level essentially conducts a Monte Carlo tree search. The inner level uses temporal difference backups as a valuation operator. It also uses a variant of UCT (Upper Confidence Bound applied to Trees) or PUCT (a variant of UCT that uses a prior probability distribution to guide the search) to improve the policy based on visit counts.

The outer level plays out games. From each state reached, several inner rollouts are performed.

In recent versions of AlphaZero, temporal difference learning is more effective than Monte Carlo backups. There is no improvement operator at this level, only an identity operator combined with the projection of the neural network.

MuZero Extension:
MuZero takes AlphaZero and learns a model in a value equivalent way, then applies value alpha zero to that learned model.

It constructs a composed value function. The model of the environment (which is being learned) is composed multiple times to give a sequence of actions.

This technique is successful in learning the rules and achieving superhuman performance in games like chess, shogi, and go. It also outperforms in standard reinforcement frameworks like Atari.

Gumbel AlphaZero Extension:
While the PUCT method used in AlphaZero is not a true improvement operator, it can be replaced with one, improving AlphaZero’s performance especially with small numbers of simulations.

With a true policy improvement operator, AlphaZero can run effectively even with limited inner rollouts for each state encountered in the outer rollouts.

Policy Improvement at Outer Level:
Policy improvement can be introduced at the outer level using a policy gradient operator. This can significantly enhance performance in certain environments, such as Atari.

Sampling for Large Action Spaces:
AlphaZero can handle large or continuous action spaces by using sampling. Actions are sampled using the agent’s policy at each level of recursion, and local Monte Carlo search is performed with respect to those actions.

A special improvement operator can correct for any bias introduced by this sampling method.

Recursion Levels:
The focus on two levels of recursion in AlphaZero and MuZero is pragmatic. The first level is special because it’s the only possible way to traverse a real environment, like a robot, without a reset.

More recursion levels could potentially provide better targets, especially when combined with approximation. Deeper recursion might be pursued as more computational resources become available.

Applications of AlphaZero:
AlphaZero has been successfully applied to various fields, including chemical synthesis and optimizing quantum dynamics.