We present Monte Carlo Tree Search with Tabular Model Learning (MCTS-TML), an extension of MCTS that does not require to know the transition model of the environment, since it learns/adapts the model while interacting with the environment. MCTS-TML assumes discrete states and actions, hence it uses a tabular representation of the transition model. The model update strategy is inspired by that of Dyna-Q but the sample eficiency of MCTS-TML is higher, therefore it requires less interactions with the environment to learn a good policy. Furthermore, MCTS-TML can scale to much larger state spaces (i.e., environments) since it computes the policy online, focusing only on the current state of the system, instead of on all possible states. We also show that MCTS-TML outperforms Q-learning, a popular model-free RL algorithm equivalent to Dyna-Q with no planning steps. Empirical evaluation of MCTS-TML is performed on both deterministic and stochastic environments showing that its sample eficiency is higher than that of Dyna-Q and Q-learning.
CEUR ceur-ws.org
Monte Carlo Tree Search (MCTS) [
A key issue for the use of MCTS in real-world applications such as robot navigation [13, 14, 15, 16] and autonomous driving, is the definition of the environment model [ 17] that the algorithm uses to perform simulations. This model is in fact very complex in real-world domains and usually it is impossible to know it precisely in advance. In this perspective an interesting IPS-RCRA-SPIRIT 2023: Italian Workshop on Planning and Scheduling, RCRA Workshop on Experimental evaluation of algorithms for solving problems with combinatorial explosion, and SPIRIT Workshop on Strategies, Prediction, Interaction, CEUR Workshop Proceedings trend aims at estimating the environment model used by MCTS [18, 19]. In this paper we tackle this problem. Namely, we assume the model of the environment to be unknown and we propose a methodology to learn it from data acquired online by the agent. We assume discrete state and action spaces, in which the model can be represented in a tabular way. We collect counts of observed transactions between states, and we use these counts to update transaction probabilities. Then we use these probabilities, together with minimal prior knowledge about the environment, as an estimated transition model to perform MCTS simulations.
We compare the performance of the proposed MCTS algorithm with learned model (in the following called MCTS-TML, for brevity) with that of two popular state-of-the-art tabular reinforcement learning (RL) algorithms, namely, the model-free Q-learning [20] and the modelbased Dyna-Q [21, 20]. As expected, MCTS-TML outperforms Q-learning in terms of sample eficiency on a standard benchmark domain. More interestingly, the sample eficiency of MCTS-TML results higher than that of Dyna-Q, hence MCTS-TML reaches optimality earlier than Dyna-Q. In our empirical test we first analyze the behaviour of the two algorithms on deterministic environments, then we investigate the performance on stochastic environments, and finally we identify and explain the reasons of this diference in sample eficiency.
Although preliminary, this work provides new insight on model learning in MCTS, a topic which has so far only been addressed from a Bayesian RL perspective. In Bayesian Adaptive Monte Carlo Planning (BAMCP) [18] and Bayesian Adaptive Partially Observable Monte Carlo Planning (BAPOMCP) [19], model learning is seen as a part of planning under uncertainty, since model parameters are inserted in the state of the system and actions are performed to decrease model parameter uncertainty, until an increasingly certain dynamical model is found. In contrast, our algorithm follows a diferent perspective building on the basic idea proposed by Dyna-Q. Essentially, the approach stores in a tabular model the knowledge about the dynamics of the environment. This knowledge is collected using a policy which is initially random and then becomes more and more eficient using the dynamics model for planning (i.e., generating rollouts and computing Q-values from them). The main contributions of this work are therefore threefold: • we propose a model-based RL and Dyna-inspired algorithm called MCTS-TML that introduces model learning in MCTS; • we compare the performance of MCTS-TML with that of Dyna-Q and Q-learning in deterministic and stochastic environments; • we investigate the motivations of the improvement achieved by MCTS-TML with respect to Dyna-Q highlighting the key elements for the superior performance of our approach and paving the way for future research directions in this are.
A Markov Decision Process (MDP) [22] is a tuple = ⟨, , , , ⟩ , where is a finite set of states, is a finite set of actions (we represent each action with its index, i.e., = {1, … , ||} ), ∶ × → () is a stochastic transition function, where () denotes the space of probability value, i.e.,
≤ 1− .
distributions over the finite set , therefore (, , ′) indicates the probability of reaching the state ′ ∈ after executing ∈ in ∈ , ∶ × → [− , ] is a bounded stochastic reward function, and ∈ [0, 1) is a discount factor. The set of stochastic policies for is Π = { ∶ → ()} .
Given an MDP and a policy we can compute state values (), ∈ , namely, the expected
value acquired by from ; and action values (, ), ∈ , ∈ , namely, the expected value
acquired by when action is performed from state . To evaluate the performance of a policy
in an MDP , i.e., ( , ) , we compute its expected return (i.e., its value) in the initial state 0,
namely, ( , ) = ( 0). The goal of MDP solvers, such as value iteration and policy iteration
[20], is to compute optimal policies, namely, policies having maximal values (i.e., expected
return) in all their states. We use to denote the known upper bound of the return’s absolute
MCTS [
We assume the transition model (or equivalent simulator) used by MCTS (to perform the steps of the Monte Carlo simulations) to be unknown. Our goal is to provide a method for learning this transition model from data acquired from the environment as the agent acts. We want to learn the model as quickly as possible and to use it eficiently to provide a high-performance policy. Sample eficiency is key in this context. Consolidated planning methods are available to solve the planning problem when the transition model is known but the model learning and adaptation problem in sampling-based (i.e., scalable) planning methods, such as MCTS, is still not completely explored. The research questions we want to answer are the following: Q1 “How eficient is, in terms of policy performance, to learn the transition model in the context of MCTS compared to learning it in the context of Q-learning, as in Dyna-Q?”; Q2 - “How eficient is, in terms of policy performance, to learn the policy by explicitly learning the transition model and using it in the context of MCTS compared to learning directly the policy as in model-free RL methods, e.g., Q-learning?”.
We propose a method to learn the transition model inspired by that used in Dyna-Q. The technique assumes both the state space and the action space to be discrete. The environment dynamics can be deterministic or stochastic. The transition model, called in the following, is tabular and it is implemented as a dictionary.
For each transition performed in the environment from a state ∈ to a state ′ ∈ applying an action ∈ we collect a triplet ⟨, , ′⟩ (dictionary key) and update a related set of information about the transition ⟨(, , ′), (, , ′), ( ′), (, , ′)⟩ (dictionary value), namely, a count (, , ′) of the number of times the transition has been observed until the current step (considering also previous episodes), the estimated probability (, , ′) = ∑ ″(∈,, (,, ′) ″) to reach state ′ performing action from state according to the current counts (, , ⋅) , a boolean ( ′) ∈ {0, 1} which is 1 if the transition ends the episode (i.e., ′ is a terminal state), 0 otherwise, and the reward (, , ′) ∈ ℝ achieved performing the transition. For instance, if we perform in the real environment a transition from state = 2 to state ′ = 5 by action 3, and if this is the ifrst time the transition was performed, than we set ( 2, 3, 5) = 1. If applying action 3 from state 2 we previously also reached state 0 two times, then we set ( 2, 3, 5) = 1/3 (and update ( 2, 3, 0) to 2/3). If 5 is not terminal, then we set ( 5) = 0. Finally, if the reward achieved in the transition from state 2 to state 5 by action 3 is -1, we set ( 2, 3, 5) = −1. The model of the environment is then updated by adding the key-value element ⟨ 2, 3, 5⟩ → ⟨1, 1/3, 0, −1⟩ since the transition from 2 to 5 with action 3 was performed for the first time.
The integration between the MCTS action-selection strategy and the proposed model-learning strategy is formalized in Algorithm 1. At the beginning the model does not contain any information hence is an empty dictionary (line 2 of Algorithm 1). For each episode the algorithm initializes the state to 0 (line 4), then for each step of the episode it: i) performs MCTS to select the action (line 6), ii) performs the selected action in the real environment (line 7), iii) updates the model (lines 9-16) by adding a new key-value entry (lines 9-13) if the transition has been observed for the first time, iv) updates the current state (line 17), v) starts a new episode if the new state is terminal (lines 18-20).
Notice that the action selection function _ _ ( , , ) performs MCTS using the current estimation of the transition model (i.e., model ) and also the prior knowledge about the environment (model ). is used to perform random but realistic steps of simulations in states never observed before (for which no entry is present in ). For instance, in a GridWorld environment says that if the agent is in a cell (i.e., state ) and performs an action (e.g., move right), it can reach randomly one of the four neighbour cells (i.e., ′), get a random reward (i.e., ) among those compatible with the transition, and randomly reach/not reach a final state (i.e., ) compatibly with the transition and reward previously selected. This prior knowledge is available in all domains and it does not provide any unfair advantage to MCTS-TML since it only describes realistic transitions in the specific domain. In the worst (i.e., less informative) case is completely random, namely, it allows transitions to any possible next state, with completely random reward and random terminal states. is used only if no entry is available in for the current state . When at least 1 entries are available the model is used to perform simulation steps from that state.
The performance of the proposed approach is here evaluated and compared with that of stateof-the-art methodologies. 1In this work we use = 1 but future work will be dedicated to develop methods that best tune this parameter since this parameter is important for guaranteeing model precision (see Section 5).
• MCTS_ORACLE [
This algorithm is used only as an oracle to estimate the best performance reachable using an exact model; • Dyna-Q [21]: it is a model-based tabular RL algorithm from which we took inspiration to implement the model learning strategy. Basically, Dyna-Q and MCTS-TML use the same tabular representation of the transition model and they update it in the same way as new observations are collected. Therefore, the only diference between Dyna-Q and MCTS-TML is the way in which the two algorithms use the learned transition model to update the policy. MCTS-TML uses this model to performs Monte Carlo simulations (according to the UCT action selection strategy) and estimates the Q-values of all actions in the current state according to the MCTS strategy. Dyna-Q uses the model to generate single virtual steps from several observed states and updates the Q-values of all considered state-action pairs according to the Q-learning (i.e., temporal diference) strategy. • Q-learning [20]: is a model-free tabular RL algorithm that corresponds to Dyna-Q with no planning steps. Namely, it updates the Q-values of only the state-action pairs that the agent actually visits using the Q-learning (i.e., temporal diference) strategy. We use this algorithm to analyze the performance of an approach that does not explicitly learn the transition model.
The domain used in our tests is the Gymnasium implementation of Frozen Lake2. We selected this domain because it has discrete state and action spaces, hence its model can be represented by a table. This is a requirement to use MCTS-TML. Furthermore, the domain has a deterministic and a stochastic version. Both versions can be solved by MCTS-TML. An agent moves in a 4x4 grid starting from the top-left corner and aiming to reach the goal in the bottom-right corner. Four holes in the grid must be avoided by the agent since they end the episode (without reaching the goal). The states are the 16 possible positions of the agent in the grid. Terminal states are those in which the agent reaches a hole or the goal. The actions are the four movements (left, down, right, up) the agent can do. The transition model can be set as deterministic (each action always moves the agent in the selected direction) or stochastic (each action moves the agent in the selected direction with probability 0.9 and in directions perpendicular to the chosen one with probability 0.05 for each perpendicular direction). If the agent tries to move out of the board it stays in the cell where it is. The reward function returns +1 when the agent reaches the goal state, 0 when the agent reaches any other cell (standard or hole).
We first perform our tests on the deterministic environment, in which the transition model is simpler to learn because each transition must be observed only once to learn its probability.
Then, we switch to the stochastic environment, in which transition probabilities require several observations to be estimated precisely. We run each algorithm 50 times. Each time it performs 200 episodes and in each episode it performs at most 100 steps (less steps are performed if the agent reaches the goal or a hole in advance). MCTS-TML and MCTS-ORACLE perform at each step = 1000 simulations starting from the current state to evaluate the action Q-values. This parameter has been tuned in advance on MCTS-ORACLE to be sure the number of simulations are enough to reach almost optimal performance in the Frozen Lake environment. Constant in MCTS (see UCT algorithm) is set to 11. In Dyna-Q we used = 0.7 , = 1 , -decay-rate= 0.7 and 25 planning steps (see [20] page 164 for details). All parameters were tuned manually to get the best performance. The discount factor is = 1 in all tests. Experiments are performed with a laptop with processor Intel Core i7 - 6500 CPU 2.50 GHz x 4, RAM 16 GB and operating system Ubuntu 20.04.5 LTS. The code is implemented in Python.
Performance is computed by averaging at each episode the return of the episode across the 50 repeats. For instance, at the end of episode 1 we compute the average return across the 50 repeats of that episode. After episode 2 the model is improved because it contains observations of both episode 1 and 2, hence we expect the average return after episode 2 is higher than that after episode 1, and so on until episode 200. We call this measure return per episode.
To deepen our analysis we also investigate the reason why the performance of an algorithm are higher than that of another algorithm. To this end we compute the distance of the estimated model from the true model (which is known in our synthetic domain). This distance is computed as the sum of the absolute values of the diferences between the transition probabilities of the true model and those of the estimated model. In other words, the probability of each transition of the real model is subtracted to the probability of the same transition in the estimated model. We compute the absolute values of all these diferences and we sum up all these absolute values. In this way, if the estimated model is equal to the real model the distance is zero and we expect that the distance decrease as the episodes go on, since the model should become more precise.
The results of our experiments on the deterministic environment are reported in Figures 1.a and 1.b. In Figure 1.a MCTS-TML (blue line) reaches the performance of MCTS-ORACLE3 in about 3The performance of MCTS-TML is slightly higher than that of MCTS-ORACLE because of the (small) number of simulations used in our experiments. With this number of simulations MCTS-ORACLE cannot completely converge to the optimal policy, hence it happens that it selects suboptimal actions by (wrongly) estimating their Q-values. On the other hand, MCTS-TML with partial models (i.e., considering only some transitions, because others still have to be learned) can be more simulation-eficient by focusing on fewer actions while computing Q-values. In particular, this happens when in MCTS-TML the transition associated to the best action has been learned but several transitions associated to suboptimal actions are still unknown. In these cases, the Q-value of the optimal action, computed by MCTS, tends to be higher than that of other actions related to unknown transitions (because of the lack of knowledge about those actions). This reduces the error-rate made by MCTS-TML while selecting the optimal action. In the deterministic Frozen Lake environment this situation occurs quite often, bringing MCTS-TML to show slightly better performance than MCTS-ORACLE with small number of simulations, however it is not a general property. 15 episodes, while the performance of Dyna-Q (orange line) grow more slowly and after 200 episodes it still has sub-optimal performance. Q-learning (green line) which does not learn any model has a still slower increase of performance but after episode 140 it surpasses Dyna-Q. The diference in performance between MCTS-TML and Dyna-Q can be explained by the chart in Figure 1.b. It shows that the distance between the model estimated by MCTS-TML and the true model (blue line) decreases much faster than the distance between the model estimated by Dyna-Q and the true model (orange line). Furthermore, the model estimated by Dyna-Q after about 125 episodes tends to stabilize to a value close to 0.15. This means that Dyna-Q almost stops to learn after episode 125 and this is the reason why also the performance of Dyna-Q tends to stabilize at a sub-optimal value.
The results for the stochastic environment are reported in Figures 1.c (algorithm performance) and 1.d (distance from the true model). In this case the performance variability increases because the learning strategy needs several observations to precisely estimate transition probabilities. The performance improvement also of MCTS-TML is a bit slower than that of the deterministic case but we mainly observe that it tends to stabilize to a value which is lower than the optimal one reached by MCTS-ORACLE. Interestingly, Dyna-Q performance increase even more slowly and they stabilize to a much lower value than that of MCTS-TML. Q-learning has an even slower increase of performance but its performance surpasses that of Dyna-Q at epoch 75 and it almost reaches that of MCTS-TML at epoch 200. The reason why performance of MCTS-TML and Dyna-Q stabilize at a sub-optimal value seem to depend on the fact that both of them tend to reduce their distance to the true model slowly from a certain episode. However, the distance of the model learned by MCTS-TML is much lower than that achieved by Dyna-Q.
The reason of these diferences could be found in diferent factors. One is that MCTS-TML performs long simulations to estimate the Q-values, and in this simulations it uses information from the estimated model where it is available and information from the model containing prior knowledge in transitions that have never been seen before. To investigate this possibility we tried to modify Dyna-Q [26] allowing it to perform several steps (instead of a single one) starting from an already observed transition and continuing in known or unknown transitions, also using model in the first case and model in the second, but also in that case MCTS-TML outperforms Dyna-Q. We are still investigating the theoretical reason why MCTS-TML outperforms Dyna-Q, but our most accredited hypothesis is that this reason is related to the use of UCT made by MCTS-TML which is more eficient in estimating Q-values than the strategy used by Dyna-Q.
We presented MCTS-TML, a model-based RL algorithm based on MCTS. The algorithm learns the model of the environment used to perform Monte Carlo simulations from data acquired while interacting with the environment. The first results achieved by MCTS-TML in the FrozenLake domain are encouraging since it shows better performance and mainly higher sample eficiency than Dyna-Q and Q-learning. Our future work will focus on evaluating the algorithm on other domains and comparing its performance with other model-based and model-free RL algorithms, such as Bayesian Adaptive Monte Carlo Planning (BAMCP) [18], Model Based Policy Optimization (MBPO) [27] and PPO [28]. Moreover, we want to better understand the theoretical reason behind the better performance achieved by MCTS-TML compared to Dyna-Q, and the reason why the distance between the model estimated by MCTS-TML and the true model tends to stabilize to a value diferent to zero in cases of stochastic environments. Furthermore, we want to implement strategies based on the confidence interval of the transition probabilities to guarantee the safety of the transitions in the simulation process (since imprecise transition probabilities estimated using only few observations can bias the policy towards suboptimal behaviours). Finally, we would like to consider non-tabular representations of the model to allow for greater scaling capabilities. policy improvement via Monte Carlo tree search, in: Proceedings of the 40th International Conference on Machine Learning (ICML 2023), PMLR, 2023, pp. 3732–3756. [13] M. Zuccotto, M. Piccinelli, A. Castellini, E. Marchesini, A. Farinelli, Learning state-variable relationships in POMCP: A framework for mobile robots, Frontiers in Robotics and AI 9 (2022). [14] A. Castellini, E. Marchesini, A. Farinelli, Partially Observable Monte Carlo Planning with state variable constraints for mobile robot navigation, Engineering Applications of Artificial Intelligence 104 (2021) 104382. [15] Y. Wang, F. Giuliari, R. Berra, A. Castellini, A. D. Bue, A. Farinelli, M. Cristani, F. Setti, POMP: pomcp-based online motion planning for active visual search in indoor environments, in: 31st British Machine Vision Conference 2020, BMVC 2020, Virtual Event, UK, September 7-10, 2020, BMVA Press, 2020. [16] A. Castellini, G. Chalkiadakis, A. Farinelli, Influence of state-variable constraints on partially observable monte carlo planning, in: Proc. 28th International Joint Conference on Artificial Intelligence, IJCAI-19, ijcai.org, 2019, pp. 5540–5546. [17] M. Zuccotto, A. Castellini, A. Farinelli, Learning state-variable relationships for improving POMCP performance, in: Proceedings of the 37th ACM/SIGAPP Symposium on Applied Computing, SAC ’22, Association for Computing Machinery, 2022, p. 739–747. [18] A. Guez, D. Silver, P. Dayan, Scalable and eficient bayes-adaptive reinforcement learning based on Monte-Carlo Tree Search, Journal of Artificial Intelligence Research 48 (2013) 841–883. [19] S. Katt, F. A. Oliehoek, C. Amato, Learning in POMDPs with Monte Carlo tree search, in: Proceedings of the 34th International Conference on Machine Learning, PMLR, 2017, pp. 1819–1827. [20] R. Sutton, A. Barto, Reinforcement Learning, An Introduction, 2nd ed., MIT Press, 2018. [21] R. S. Sutton, Dyna, an integrated architecture for learning, planning, and reacting, SIGART
Bull. 2 (1991) 160–163. [22] M. L. Puterman, Markov decision processes: discrete stochastic dynamic programming,
John Wiley & Sons, 2014. [23] G. Chaslot, S. Bakkes, I. Szita, P. Spronck, Monte-Carlo Tree Search: A new framework for game AI, in: Proceedings of the Fourth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE’08, AAAI Press, 2008, p. 216–217. [24] P. Auer, N. Cesa-Bianchi, P. Fischer, Finite-time analysis of the multiarmed bandit problem,
Machine Learning 47 (2002) 235–256. [25] L. Kocsis, C. Szepesvári, Bandit based Monte-Carlo planning, in: Machine Learning: ECML 2006. 17th European Conference on Machine Learning, volume 4212 of LNCS, Springer-Verlag, 2006, pp. 282–293. [26] G. Z. Holland, E. Talvitie, M. H. Bowling, The efect of planning shape on dyna-style planning in high-dimensional state spaces, ArXiv abs/1806.01825 (2018). [27] M. Janner, J. Fu, M. Zhang, S. Levine, When to trust your model: Model-based policy optimization, in: Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019, p. 12519–12530. [28] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, O. Klimov, Proximal policy optimization algorithms., CoRR abs/1707.06347 (2017).