<jupyter_start><jupyter_text>**Monte Carlo Tree Search Implementation****In this notebook we implement Upper Confidence Bound (UCB) based MCTS algorithm for performing the stated tasks in a given environment.**    **We revisit `Taxi-v3` environment for implementing this agent. Also, we experiment on different max-depth values for a given MCTS tree values and analyze its effect on the performance of the agent.**  **Monte Carlo Tree Search Component Declarations**<jupyter_code>import os
import gym
import sys
import random
import itertools
from time import time
from copy import copy
from math import sqrt, log
# Defining node class and associated properties with it.
class Node:
    def __init__(self, parent, action):
        self.parent = parent
        self.action = action
        self.children = []
        self.explored_children = 0
        self.visits = 0
        self.value = 0
# This function determine complete exhaustive list of all the nodes.
def node_expansion(space):
    if isinstance(space, gym.spaces.Discrete):
        return range(space.n)
    elif isinstance(space, gym.spaces.Tuple):
        return itertools.product(*[node_expansion(s) for s in space.spaces])
    else:
        raise NotImplementedError
# Upper Confidence Bound U(s,a) calculation formula.
def upper_conf_bound(node):
    return node.value / node.visits + sqrt(log(node.parent.visits)/node.visits)

def moving_averages(v, n):
    n = min(len(v), n)
    ret = [.0]*(len(v)-n+1)
    ret[0] = float(sum(v[:n]))/n
    for i in range(len(v)-n):
        ret[i+1] = ret[i] + float(v[n+i] - v[i])/n
    return ret
# MCTS denotes Monte Carlo Tree Search
class MCTS:
    def __init__(self, env_name, num_execs=300, max_tree_depth=1000, episodes=10000):
        self.env_name = env_name

        self.num_execs = num_execs
        self.max_tree_depth = max_tree_depth
        self.episodes = episodes
    
    def print_stats(self, num_exec, score, avg_time):
        sys.stdout.write('execution number: \r%3d   total reward:%10.3f   average time:%4.1f s' % (num_exec, score, avg_time))
        sys.stdout.flush()
        if (num_exec % 10) == 0:
            print("execution number: \r%4d   total reward: %4.3f   average time: %4.2f s" % (num_exec, score, avg_time))

    def execute(self):
        print(self.env_name)
        # For maintaining list of best rewards.
        best_rewards = []
        start_time = time()
        env = gym.make(self.env_name)
 
        for loop in range(self.num_execs):
            env.reset()
            root = Node(None, None)
            # For capturing list of best actions taken by the agent.
            best_actions = []
            best_reward = float("-inf")

            for _ in range(self.episodes):
                state = copy(env)

                sum_reward = 0
                node = root
                terminal = False
                actions = []

                # selection of suitable node children
                while node.children:
                    if node.explored_children < len(node.children):
                        child = node.children[node.explored_children]
                        node.explored_children += 1
                        node = child
                    else:
                        node = max(node.children, key=upper_conf_bound)
                    _, reward, terminal, _ = state.step(node.action)
                    sum_reward += reward
                    actions.append(node.action)

                # expansion of all the children nodes
                if not terminal:
                    node.children = [Node(node, a) for a in node_expansion(state.action_space)]
                    random.shuffle(node.children)

                # creating exhaustive list of actions
                while not terminal:
                    action = state.action_space.sample()
                    _, reward, terminal, _ = state.step(action)
                    sum_reward += reward
                    actions.append(action)

                    if len(actions) > self.max_tree_depth:
                        sum_reward -= 100
                        break

                # retaining the best reward value and actions
                if best_reward < sum_reward:
                    best_reward = sum_reward
                    best_actions = actions

                # backpropagating in MCTS for assigning reward value to a node.
                while node:
                    node.visits += 1
                    node.value += sum_reward
                    node = node.parent

                
            sum_reward = 0
            for action in best_actions:
                _, reward, terminal, _ = env.step(action)
                sum_reward += reward
                if terminal:
                    break

            best_rewards.append(sum_reward)
            score = max(moving_averages(best_rewards, 100))
            avg_time = (time() - start_time) / (loop + 1)
            self.print_stats(loop + 1, score, avg_time)<jupyter_output><empty_output><jupyter_text>**Executing MCTS for `Taxi-v3 ` and reward function calculation.**<jupyter_code>def main():
    MCTS('Taxi-v3', num_execs=200, max_tree_depth=512, episodes=5000).execute()
# Printing average achieved score by the MCTS algorithm in Taxi-v3 environment
if __name__ == "__main__":
    main()<jupyter_output>Taxi-v3
  10   total reward: 0.100   average time: 2.08 s
  20   total reward: 0.900   average time: 1.98 s
  30   total reward: 3.600   average time: 2.19 s
  40   total reward: 3.700   average time: 2.05 s
  50   total reward: 4.360   average time: 2.12 s
  60   total reward: 2.483   average time: 2.06 s
  70   total reward: 3.414   average time: 1.97 s
  80   total reward: 3.987   average time: 1.91 s
  90   total reward: 3.867   average time: 1.87 s
 100   total reward: 4.720   average time: 1.79 s
 110   total reward: 5.780   average time: 1.80 s
 120   total reward: 5.870   average time: 1.79 s
 130   total reward: 5.870   average time: 1.79 s
 140   total reward: 5.870   average time: 1.79 s
 150   total reward: 5.870   average time: 1.78 s
 160   total reward: 5.870   average time: 1.80 s
 170   total reward: 5.870   average time: 1.78 s
 180   total reward: 5.870   average time: 1.85 s
 190   total reward: 5.870   average time: 1.89 s
 200   total reward: 5.870   average time:[...]
{'fraction_non_alphanumeric': 0.08653241032095657, 'fraction_numerical': 0.03901825047199497, 'mean_word_length': 1.952624245239201, 'pattern_counts': {'":': 1, '<': 10, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '186815', 'license': 'Unlicense', 'n_tokens_mistral': 2058, 'n_tokens_neox': 1801, 'n_words': 582, 'path': 'milestone-three/monte_carlo_tree_search_taxi_v3.ipynb', 'repo_name': 'galleon/prototyping-self-driving-agents', 'size': '6356'}