MuZero:
– Works based on AlphaZero’s search and planning space – Learns optimal policy, reward functions, value functions automatically – The main idea of the algorithm is to predict those aspects of the future that are directly relevant for planning. – Observation image ===> Model ==> Encodes to hidden states ==> Hidden states updated using previous step’s hidden state and hypothetical next action – In each step, model predicts value fn, optimal policy, and immediate reward
– RL basically: – model based and model free methods – model based: construct an intermediate step from environment reprs – MDP with state transition model ~~~~+~~~~ Reward model – MCTree Search for optimal policy search or value based iteration methods – Representation learning, model learning , planning all must go together. – Common approach in environment repr: All pixels as describing the env state – But computationally intractable in most cases – So, build latent repr and predict next latent repr is good
– Different approach in this area: – End to end prediction of value functions – They construct abstract MDP s.t. planning in abstract MDP is same as planning in the given env space – Value Equivalence is the method that does all this: trying to copy values like student teacher model so that abstract MDP can copy to produce same value functions – Predictron : TD based learning , learns without learning transition functions – TreeQN: tree search for optimal value fn, using same abstract MDP – Value iteration models: Value iteration over the model to predict optimal value functions – Value prediction networks [28] are perhaps the closest precursor to MuZero: they learn an MDP model grounded in real actions; the unrolled MDP is trained such that the cumulative sum of rewards, conditioned on the actual sequence of actions generated by a simple lookahead search, matches the real environment. Unlike MuZero there is no policy prediction, and the search only utilizes value prediction.
– model consists of three connected components for representation, dynamics and prediction: A.
- – Inputs: –> Prev hidden state –> Candidate action –> Dynamics function ‘g’ – Outputs: –> Immediate reward –> Next hidden state
- From hidden state: Policy and value function are calculated using prediction function ‘f’
- Initial hidden state: Past observation into representation function ‘h’
B. How model acts:
- Performs MC tree search at timestamp ’t’ as described in [A]
- Action ’t+1’ sampled from search policy at time ’t'
- Env receives action and genereates new observation and reward ’t+1'
- At end of episode, trajectory data stored in replay buffer.
C. How training is done:
- Trajectory is sampled
- For initial step: ‘h’ receives input thee past observations from selected trajectory
- Model subsequently unrolled for ‘K’ steps
- At each step in unrolling, ‘g’ receives as input hidden state from previous unrolling and real action from a(t+k)
- Now all parameters,dynamics and pred functions are jointly trained by backprop thru time
D. Final output will be: Policy : ‘p[k]’ ===> ‘pie[t+k]’ Value function: ‘v[k]’ ====> ‘z[t+k]’ Reward: ‘r[t+k]’ =====> u[t+k]
z[t+k] == sample return : final reward in board games, n-step return in Atari
– AlphaZero vs MuZero:
– Specifically, AlphaGo Zero and AlphaZero use knowledge of the rules of the game in three places: (1) state transitions in the search tree, (2) actions available at each node of the search tree, (3) episode termination within the search tree. In MuZero, all of these have been replaced with the use of a single implicit model learned by a neural network
–
– Alpha Zero’s algorithm:
Mentally play through possible future scenarios, giving priority to promising paths, whilst also considering how others are most likely to react to your actions and continuing to explore the unknown.
After reaching a state that is unfamiliar, evaluate how favorable you believe the position to be and cascade the score back through previous positions in the mental pathway that led to this point.
After you’ve finished thinking about future possibilities, take the action that you’ve explored the most.
At the end of the game, go back and evaluate where you misjudged the value of the future positions and update your understanding accordingly.
– In simple terms: When you play a bad move, it’s either because you misjudged the future value of resulting positions, or you misjudged the likelihood that your opponent would play a certain move, so didn’t think to explore that possibility. These are exactly the two aspects of gameplay that AlphaZero is trained to learn.
–
– Alpha Zero : – The expert policy (pie) and approximate value function(W) are both NNs. – Neural net ‘f’ that takes in game state and produces both probabs over the next move and approx state value. – Leaves in search tree are expanded by evaluating them with NN.\ –
– Alpha Zero has only one NN while MuZero has 3. – We know both use MCTree Search (MCTS) for next best move selection. – What they do is they play out all likely future scenarios, evaluate value using NN and choose action that maxes the future expected value. – But muzero has a problem. It doesn’t know rules of game and has no idea how a given action will affect game state so can’t imagine future scenes in MCTS. It doesn’t even know whether one side has won or which moves are legal given a position. – AlphaZero has only function ‘f’. whereas Mu has ‘f’,‘g’, ‘h’ – ‘h’ is for representation: input pixels to state. – ‘g’ is for dynamics : it learns how to evolve given hidden repr – ‘f’ is same used for prediction: state to policy and value function – Unlike alphazero where next state in MCTS is simply case of asking the env, Muzero builds it’s own dynamic model ‘g’ to tell it how to move. – So, to make predictions from MCTS tree, Muzero needs two inference methods:
- Initial_inference: for current state ‘h’ followed by ‘f’
- Recurrent_inference: for moving between states in MCTS tree ‘g’ followed by ‘f’
–
– Understanding mu zero coding process:
-
Starts with the config object which stores important info about the parameters of the run. – There are two parts: – self-play: creating game data – training: producing improved NNs – They work by accessing SharedStorage and ReplayBuffer.
-
Shared Storage: – make a dictionary of networks – latest_network function to return latest network “-> Network” to specify that it returns a network object – check if no network, create one – else return max(dictionary of network’s keys) – save network function to add network to the existing dictionary.
-
ReplayBuffer: – params: window size, batch_size, buffer(list) :::: window_size : limit max no of games stored in buffer muzero: 1million – save game: if len(self.buffer) > self.window_size: self.buffer.pop(0) self.buffer.append(game) – sample batch: no_unroll_steps, td_steps as input – get games, game_pos then sample
– observation at chosen position .make_image(i) – list of next num_unroll_steps actions taken after chosen position if exists – list of targets to train neural nets: list of tuples target_value, target_reward, target_policy
--– sample_game: random.choice(self.buffer) – sample_position: random.choice(game.history)
-
Self play: – params: config, storage, replaybuffer – get latest_network, play_game(config, network), save game into replay buffer
4.1 Play_game function: – params: config, network ===> produce game as output – create new game from config – while(not game.terminal() and len(game.history) < config.max_moves): – start at root of tree, get root node – get current observation image – expand root node using known legal actions and inference about current observation provided by initial_inference function –
-
Node: – stores visit_count, to_play, prior, value_sum, children(dict), hidden_state, reward=0 – expanded: returns bool if it has childrens – value: if unvisited return 0 else: value_sum / visit_count – expand_node: node, to_play(instance of Player), actions: list_of_actions, network_output – policy is { action as keys and exp(policy_logit_for_a) as value} – policy_sum is sum over all policy.values() – now for action and p in policy.items(): node.children[action] = Node(p/policy_sum) – we also need to add exploration noise to root node actions: to ensure MCTS explores a range of possible actions rather than just what it believes is optimal: add_exploration_noise: takes config and node to work on – actions = list of node.children.keys() – noise = np.random.dirichlet() – frac = config.root_exploration_fraction – for a, n in zip(actions, noise): node.children[a].prior = it’s prior * ( 1 - frac) + n* frac
-
run_mcts : config, root, game.action_history, network
min_max_stats = Minmaxstats(config.known_bounds) # to store info on min and max rewards in order to normalize later
for _ in range(config.num_simulations):
history = action_history.clone()
node = root
search_path = [node]
while node.expanded():
action, node = select_child(config, node, min_max_stats) history.add_action(action) search_path.append(node)
parent = search_path[-2] network_output = network.recurrent_inference(parent.hidden_state, history.last_action())
expand_node(node, history.to_play(), history.action_space(), network_output)
backprop(search_path, network_output.value, history.to_play(),)
- select_child: config, node, min_max_stats _, action, child = max( (ucb_score(config, node, child, min_max_stats), action, child) for action, child in node.children.items()) return action, child
- Early in simulation, exploration bonus dominates. As total number of simulation increases, the value term becomes more important.
-
backprop: search_path(list of nodes) , value, to_play, discount, min_max_stats
for every node: node.value_sum += value if node.to_play
= to_play else -value node.visit_count +1 min_max_stats.update(node.value())
-
select_action: config, num_moves, node, network
visit_counts = [(child.visit_count, action) for action, child in node.children.items()] t = config.visit_softmax_temp_fn(num_moves, training_steps) _, action = softmax_sample(visit_counts, t) return action
visit_softmax_temp_fn(num_moves, training_steps): if num_moves < 30: return 1 else: return 0
- now chosen action is applied to true env, relevant values appended to game object: rewards, history, child_visits, root_values
-
train_network: config, storage, replay_buffer learning_rate = lr_init * lr_decay_rate ** (training_step / lr_decay_steps) optimizer (learning_rate, momentum) for i in range(trainig_steps): if i % checkpoint_interval == 0: storage.save_network(i, network) batch = replay_buffer.sample_batch(num_unroll_steps, td_steps) update_weights(optimizer, network, batch, wt_decay) storage.save_network(training_steps, network)
-
Game object: action_space_size, discount
history, rewards, child_visits, root_values = []
make_target: state_index, num_unroll_steps, td_steps, to_play targets = [] for curr_index in range(state_index, state_index+num_unroll_steps + 1): bootstrap_ind = curr_index + td_steps
if bootstrap_ind < len(root_values): value = root_values[bootstrap_ind] * discount ** td_steps else:
value = 0
for i, reward in enumerate(rewards[curr_index:bootstrap_ind]): value += reward * discount ** i
if curr_index < len(root_values): targets.append((value, rewards[curr_index], child_visits[curr_index])) else: targets.append((0, 0, []))
return targets
-
Update rule for weights: – three losses we are trying to minimize: – diff betn predicted reward ‘k’ steps ahead of turn ’t’ and actual reward ‘u’ – diff betn predicted value ‘k’ steps ahead of turn ’t’ and target TD value ‘z’ – diff betn predicted policy ‘k’ steps ahead of turn ’t’ and MCTS policy ‘pi’
– also regularization term is added – losses summed over num_unroll_steps to gen loss for given pos in batch
– Actual implementation: optimizer, network, batch, wt_decay for image, actions, targets in batch:
value, reward, policy_logits, hidden_state = initial_inference(image) preds = [(1.0, value, reward, policy_logits)]
for action in actions: value, reward, policy_logits, hidden_state = recurrent_inference(hidden_state, image) preds.append((1.0/ len(actions), value, reward, policy_logits))
hidden_state = tf.scale_gradient(hidden_state, 0.5)
for prediction, target in zip(predictions, targets):
grad_scale, value, reward, policy_logits = prediction target_value, target_reward, target_policy = target
l = ( scalar_loss(value, target_value) + scalar_loss(reward, target_reward) + softmax_cross_entropy_with_logits( logits=policy_logits, labels=target_policy))
loss += scale_gradient(1, grad_scale)
for wts in network.get_weights(): loss += wt_decay * regularization_loss(weights)
-
AlphaZero already knows: What happens to board when it moves What are legal moves given a position When game is over and who won
But muzero has no idea.