# Tensor Implementation of Monte-Carlo Tree Search for Model-Based Reinforcement Learning
## 2 Related Work  
### Mcts and Reinforcement Learning  
RL agents are usually divided into two categories--model-based, and model-free. One of the most important parts of model-based agents is the model of the environment. By environment model, we mean a function that predicts the next state and reward given a combination of the current state and action. In other words, the model allows inferences to be made about how the environment will behave [18]. Therefore, these models are frequently used for planning, e.g., in combination with MCTS. Agents such as AlphaGO and AlphaZero use a given model of the environment in the form of game simulators to achieve the best results. Other model-based agents such as MuZero, SimPLE [19], and I2A [20] do not require a given model and instead incorporate a learned model into the training procedure. Model-free agents do not use a model of the environment, so they cannot reason about how their environments will change based on a given state and action [18]. Model-free agents rely on a trial-and-error approach. They tend to be easier to implement and tune. Model-free agents are divided by their learning approach into Q-learning agents (e.g., DQN [21]) and policy optimization agents (e.g., A2C [22], PPO [23]). In 2016, the algorithm AlphaGO defeated world champion [PERSON] in game GO [1]. This event was another milestone in the dominance of artificial intelligence against human players. Last generation of algorithms based on AlphaGO is MuZero. It is model-based RL algorithm that combines MCTS and DNN [2]. It is useful in domain without own copy of environment, e.g., domain of Atari games. Due to this approach, MuZero has achieved SOTA results in several Atari games [24]. Atari games are often used as benchmarks for RL algorithms [21; 25]. In addition of Atari games, MuZero has been applied in real-world tasks such as autonomous defense of SDN Networks [26] or air traffic optimization [27]. The DNN in MuZero consists of three connected components for representation, dynamics and prediction. The representation function \(f_{r}(o|\theta_{r})\) takes past observation (e.g., the Go board or Atari screen) and transforms it into hidden state \(s\). The hidden state \(s\) is a representation of the real environmental state by DNN. Because we do not have a copy of environment, we use hidden states in MCTS instead of environment observations. Given a state \(s_{t}\) and an action \(a_{t}\), the dynamics function \(f_{d}(s,a|\theta_{d})\) predicts an immediate reward \(R(s_{t}|\theta_{d})\) and a new state \(s_{t+1}\). In each state, the prediction function \(f_{p}(s|\theta_{p})\) proposes probability distribution of actions \(P(s,\cdot|\theta_{p})\) and state value \(V(s|\theta_{p})\). State value is expected return of rewards from the current state. MCTS is used to build tree of possible actions (represented as edges) and hidden states (nodes) in order to support decision making process. Tree is build by process called simulation. Simulation consists of four base MCTS phases (selection, expansion, simulation and backpropagation). Each simulation explores existing tree, finds next unexplored combination of state \(s\) and action \(a\), and extends the tree by adding new node (state \(s\)). Simulations are executed sequentially. One simulation consists of following phases:  
* Phase of selection--the tree is traversed from the root to find next unexplored combination of state and action. In each node (assigned to specific state), the edges (represent actions) are chosen by the PUCT (Predictor + Upper Confidence Bound applied to trees) (Equation (1)). PUCT represents trade-off between exploitation and exploration. Exploitation is solved via q values. \(Q(s_{t},a)\) is expected value of future rewards after taking action \(a\)[18]. In our case, it could be computed as a sum of immediate reward \(r_{t}\) and state value of next state \(V(s_{t+1}|\theta_{p})\) discounted by discount factor \(\gamma\in[0,1]\) (Equation (2)).