MCTransformer: Combining Transformers And Monte-Carlo Tree Search For Offline Reinforcement Learning
Authors: Gur Yaari
Lior Rokach
Rami Puzis
Gilad Katz
Venue: Submitted to ICLR 2023 (2023)
Keywords: Transformer
Monte Carlo Tree Search
Offline Reinforcement Learning
SameGame

Abstract: Recent studies explored the framing of reinforcement learning as a sequence modeling problem, and then using Transformers to generate effective solutions. In this study, we introduce MCTransformer, a framework that combines Monte-Carlo Tree Search (MCTS) with Transformers. Our approach uses an actor-critic setup, where the MCTS component is responsible for navigating previously-explored states, aided by input from the Transformer. The Transformer controls the exploration and evaluation of new states, enabling an effective and efficient evaluation of various strategies. In addition to the development of highly effective strategies, our setup enables the use of more efficient sampling compared to existing MCTS-based solutions. MCTransformer is therefore able to perform a small number of evaluations for each newly-explored node, and to do so without degrading its performance. Our evaluation, conducted on the challenging and well-known problem of SameGame, shows that our approach outperforms both Transformer-based and MCTS-based solutions.

Under review as a conference paper at ICLR 2023
MCTRANSFORMER: COMBINING TRANSFORMERS AND MONTE-CARLO TREE SEARCH FOR OFFLINE RE- INFORCEMENT LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
Recent studies explored the framing of reinforcement learning as a sequence mod- eling problem, and then using Transformers to generate effective solutions. In this study, we introduce MCTrassformer, framework that combines Monte-Carlo Tree Search (MCTS) with Transformers. Our approach uses an actor-critic setup, where the MCTS component is responsible for navigating previously-explore states, aided by input from the Transformer. The Transformer controls the explo- ration and evaluation of new states, enabling effective and efficient evaluation of various strategies. In addition to the development of highly effective strate- gies, setup enables the of more efficient sampling compared to existing MCTS-base solutions. MCTrasnformer, therefore, is able to effectively learn from small number of simulations for each newly-explored node, without de- grading performance. Evaluation conducted on the challenging and well-known problem of SameGame, shows that MCTrasnformer outscores Transformer-only and MCTS-only solutions by a factor of three and more.
INTRODUCTION
Transformers have recently been shown to be very effective in the field of reinforcement learning (RL) Chen et al.] (202T); Janner et al. (2021). This was achieved by converting offline RL to classification problem, which facilitates advanced sequence modeling abilities using Transformers. At evaluation time, the Transformer functions as autoregressive model, generating sequences of future actions.
The main shortcoming of the aforementioned approach is the absence of exploration during online evaluation. The Transformer model is, therefore, limited in its ability to adjust to novel circum- stances. While online fine-tuning of the model was recently proposed [Zoposed[hheng et al. (2022a), it re- quires a relatively large number of training samples. Moreover, one-time fine-tuning approach is not suitable for problems with high degrees of volatility, that require continuous exploration.
We introduce MCTrasnformer, a RL framework that enables cost-effective exploration of planning problems. Our approach combines Monte-Carie Tree Search (MCTS) with the Transformer archi- tecture in an actor-critic setup. The MCTS component of MCTrasnformer is tasked with balancing the exploration/exploitaiin trade-off needed in most RL tasks, while the Transformer component tasked with predicting the utility of -unxppllo-de nodes. Additionally, we use the Trans- former carry out the simulation phase of the MCTS (i.e., the rollout policy), where the former's advanced and effective modeling allows us to use vary small number of simulations, thus keeping our approach efficient.
We evaluate the proposed approach SameGame, challenging and well-known problem. This game considered challenging due to the high variance of its initial states. Game boards are ran- domly initialized, which forces any solver to perform great deal of exploration from the first step. Another factor that adds complexity to the planning process is the large bonus score that is awarded only when the board is fully cleared. The ability to correctly assess whether the board can be cleared has significant effect on the planner's behavior. Our evaluation shows that MCTrasnformer signifi- cantly outperforms perfprrnngnnng methods in budget-based setting.

---

Under review as a conference paper at ICLR 2023
2
PRELIMINARIES
2.1 BACKGROUND SAMEGAME
Game rules. SameGame is single-player game, played on rectangular board of height H and width W. The board is randomly filled with tiles of C different color Two tiles are considered adjacent they are connected either vertically or horizontally. A block tiles is group of two or more adjacent tiles of the same color. A tile with no adjacent tiles of the same colors is singleton. At each turn, the player selects single block (one cannot select singletons), which is then removed from the board. When block is removed, the board is reorganized as follows: a) tiles above the removed tiles "fall down" (a physics-basee based model); b) when an entire column is removed, all the columns its right shift left. The game continues until more blocks exist on the board, i.e., an empty board or one or more singletons.
Reward function. The reward is calculated each turn as follows: (n:- - 2)", where ni is the size of block chosen by the user at step If the board empty when the game concludes, the player receives an additional 1000 points bonus. If tiles remain on the board, a penalty of Σ, (n: 2) where is the number of tiles left of color i, is exacted. The score is the sum of all the rewards. This setup creates two (potentially conflicting) goals for the player: the first goal to create blocks that are large possible; the second goal is to empty the board, which may require larger number of steps, as a result of the need to select smaller blocks.
Complexity. A SameGame board is defined as solvable if sequence of actions exists so that the board can be emptied. As shown in Schadd et al. (2008 Takes Kosters (2009), determining whether randomly-initialin actions that maximizes the score, regardless of whether the board is solvable, also NP-complete. The main reasons for this difficulty are the game's 's high branching factor around 17, initially- and the fact that the length of an average game in our setup is approximately 27.
board is solvable Is NP-complete. Therefore, finding sequence of
Training
6.4.
Erger cal
Inference (Eveluation)
MCTransformer
Me Aeou
Figure The proposed MCTrasnformer approach
3 PROPOSED METHOD
3.1
OVERVIEW
Our proposed approach presented in Figure 1 Our training phase (steps #1-#5) as follows: we begin by generating batch of randomly-inttalized SameGame boards (step #1). Next, for each
Our description refers to the version of SameGame used in this study, which is of the common.
2

---

Under review as a conference paper at ICLR 2023
board run fixed number of MCTS simulations (step #2). Each simulation is played until the conclusion of the game, at which point all of its relevant information is saved to the replay buffer (step #3). Next, of our states and actions (step #4), which are then used in the training of our Transformer (step #5).
all the games stored in our buffer to generate representations (embeddings)
During the test phase, MCTrasnformer performs as follows: at each step, approach MCTS model to select actions until a leaf is reached (i.e., the selection phase). Then, instead of using existing expansion methods, we use our transformer assign initial scores to each potential action, and then select one based on an upper confidence bound. Next, we use our transformer as rollout policy: the transformer plays a small set of games to their conclusion, and the scores are used to update values through the MCTS's moves tree.
the
In addition to its novel architecture, MCTrasnformer has important advantages over existing solu- tions. First, by using transformers to explore and expand the moves tree, we are able to outperform other budget-based methods such as MCTS, as well as wansformer-basee solutions (as shown in Section 4 Secondly, MCTrasfformer requires a smaller number of simulations compared to other methods, a fact that makes more efficient. Thirdly, our incorporation of the transformer within the MCTS algorithm makes the overall approach more flexible and adaptive: because the trans- former learns across multiple board positions, the MCTS does not start as a blank slate with each new board a highly impactful fact, given that the boards are randomly initialized and have high variance.
3.2 GENERATING MCTS-BASES TRAJECTORIES
The goal of this step is generate large volume of games that will enable us to train our Trans- former model. We use an MCTS model to generate a large set of games (250,000 in our evalua- tion), and store the final trajectory of each game in our buffer. Each game begins with randomly- initialized board, which ensures a diverse set of games. It is important to note that our MCTS model selects the node whose children produced the highest score of each set of simulations, since SameGame is single-player game that does not involve an adversary. Additionally, we improve the efficiency of the MCTS by unifying all the tiles of a block into a single action, thus significantly reducing the search space. We use the UCT algorithm Matsuzaki (2018) to navigate tree:
In N(s))
UCT(SE, a) = @orm (s, a) + Guct
N(s,,a)
where Cuet is a hapee--paraettr, (sx) denotes the number of time the MCTS simulations visit state St, N (ss a) denotes the number of time the MCTS simulations visited state st and chose action a. Note that Qnorm (s, a) is defined in Equation 4
This process is the most cone-con part of our methods, because of the need to play large number of games to completion. This difficulty mitigated by two factors: first, this process takes place during the offfine training of our model, meaning that it does not affect evaluation time. Secondly, this process can be easily parallelized, since each game can be played independently.
3.3 STATE AND ACTION SPACE REPRESENTATIONS
The Action Space. Our action space is represented by vector whose size is equal the number of tiles on the board. The values, generated by the Transformer's output layer, are produced using the logits activation function and softmax operation. is important note that while SameGame rules require that we select blocks, our action representation assigns value to each tile. This is the case for two reasons: first, the number, shapes and sizes of blocks changes throughout the game, and architecture requires a fixed-size representation. Secondly, tile-based representation is more nuanced, and provides additional information to the transformer in future time steps. We elaborate on the action selection process, i.e., the transformation of tile-based values to block-based values, in Section 3.4
The state space. Our SameGame board consists of 100 tiles, ordered in 10x10 matrix. Our goal for our representation is to capture not only the color each tile, but also the size of the block to which it belongs. Therefore, represent each tile using the following one-hot representation, with
3

---

Under review as a conference paper at ICLR 2023
each entry in the vector representing single color. Note that empty tiles assigned their own color. The vector representation of each individual tile is in the following form: (0, ..... 00.0..... O..,),, where denotes the size of the tile's block, and n denotes the total number of tiles the board. This representation maintains the simplicity of a one-hot representation, while also making it easier for model to identifier larger (i.e., impactful) blocks. Using the one-hot transformation described above, we represent the board as H X W x (C + 1) matrix, where C' is the size of the vector representing each tile (i.e., the number of tile colors background). We then use a convolutional architecture to transform this representation into a vector of size 128.
3.4 PRELIMINARY TRAINING THE TRANSFORMER ARCHITECTURE
Our Transformer receives three inputs at each time step: a) the state representation; b) the action representation, and; c) temporal (i.e., positional) encoding that represents the turns of the game. We first use an embedding layer to convert the all three representations to size of 128. Then, we add (using summation) the temporal encoding to both the state and action representations.
The training of our Transformer is performed similarly to that of Transformer-basee text generation tasks Chen et al. 2021): ): Vaswani et al. (2017). Upon receiving a sequence of states and actions
{so, Gas St-1, 1, f. the goal of our model is to predict 0g. It is important to note that we full information, deterministic game, and states can be therefore easily inferred from chosen actions.
only predict actions and not states, because SameGame
One important difference between the MCTS and Transformer components of MCTrasnformer lies in the fact that while the former selects blocks, the latter selects tiles. To bridge this gap, we consider the top-left tile of each block to be the block representative. This means that when a given block is chosen, the Transformer will be considered to be correct only if the top-left tile of that block is selected. The loss function used by our Transformer is cross entropy.
3.5 DEPLOYING MCTrasnformer AT TEST TIME
One of the main challenges in efficiently exploring SameGame is the random initialization of the board. This setup makes the use of standard MTCS difficult, since the process needs to start 'from scratch' for every new board, which would make the process computationally expensive. Using fully Transeormer-based solution would also be effective, but its inability effectively balance exploration and exploitation would result in a very long iterative training period (as described in Anthony al. (0017).
MCTrasfformer combines the strengths of both MCTS and Transformers to create a more efficient solution. The MCTS component manages the exploration/eeploiaaiioon trade-offs, while the Trans- former component is tasked with selecting highly effective actions and optimizing the chosen game trajectories. We begin by using the a PUCT-based version of the MCTS algorithm to reach leaf in our current search tree. Next, we use the Transformer component to perform the rollout phases. We now describe each phase in detail:
The selection phase The goal of this phase is to use a PUCT-based version of MCTS algorithm to reach one of the leaves of the current tree. The selection is carried out the using standard Predictor- Silver et al. (2017):
= arg
(st, a) + Us2,
(2)
where
V (s()
Ust, a) Cpuct Tip (p a) I+ N(s a))
(3)
Opuct is a hhper--paaatt param-ear (e(s;: a) denotes the action probabilities of the stochastic policy π pa- rameterized by 0. N(ss) denotes the number of times state 8, was visited by the MCTS, with st being the parent node of node (s,,a). Similarly, N(s a) is the number of time the MCTS simula- tions visit state 8, and choose action a.
In order to use UCT or PUCT as a selection strategy, the return to go need to be in the range of [-1,1] 1]. In our case, however, the range of return go has hugh variance and unkown. Therefore,
4

---

Under review as a conference paper at ICLR 2023
normalization method is required. We choose to use Shefi's Seeify & Buro (020) marmin value normalization method which requires no domain knowledge and no assumption or statistics on the values. This scaling is applied locally at the node level as follows:
Qnorm (3,0) 2(Q(s, a) min, Q(s.
(4)
max Q(s a') min,, min,,
When no action has been taken it is equal to 1, being optimistic. Q(s, a) the mean of all sum of rewards from state 8 that took action a. maz, Q(s, as) the action a that return the highest sum of rewards on the trajectory started at state the same applies for min, (s,
The expansion phase. In this phase, we need to select the next node to be expanded. The selection will be governed by the P-UCT algorithm, with the Transformer setting the initial probabilities of each expansion candidate. For each legal action we can take in the leaf, Va E actionSpacee calculate the prior probabilities (T a). These probabilities
calculated for each action (i.e.. block) by summing the probabilities assigned to all of its tiles. To(s a) is then used in Equation to select the node that will be expanded.
The rollout phase. Once a node has been selected for expansion, we need play the game to its end to obtain a score. Instead of using multiple MCTS simulations, we use MCTrasfforme'' Transformer component to play a single game to its end. The final score obtained by this run is used to update all the nodes in the trajectory from the MCTS tree's root to the newly expanded leaf.
Following the single rollout run described above, we conduct a small number of additional simu- lations. These runs algorithm until they reach a leaf. Then, without any additional expansion of nodes, the Transformer component plays the games to their end, and updates the relevant nodes according to the obtained score. We found that this small number of runs (4-16 in our experiments) significantly contribute to the performance out runs, the Transformer's policy is deterministic, with the probability of each block obtained by summing the individual probabilities allocated to its tiles.
from the root of the tree (not the expanded node), and follow the MCTS
our proposed approach,
relatively small computational cost. all roll-
3.6 FINAL ACTION SELECTION
Once all rollouts are completed for the given root, MCTrasnformer is faced with the final step of selecting the next move. This selection will be made based on the Q-values of all legal actions (i.e., nodes). It is important to note that this decision only applies to a single step forward, upon the completion of which the MCTS-based process will resume. The root of the MCTS will also be reallocated to the current state of the board.
Our logic in selecting the path with the highest possible Q-value is simple: given that we play a deterministic one-player game, single simulation where we able to obtain a given score ensures that this trajectory can be repeated, and that the obtained value is lower bound on possible performance.
4 EVALUATION
Our evaluation has several goals. Primarily, our aim is to evaluate the efficacy and computational efficiency of MCTrasnformer compared to standard Transformer and MCTS-based solutions. Addi- tionally, we will explore the ability of the Transformer-basee player to learn the joint distributions of states and actions from our generated datasets, and use several metrics to analyze the perofmance of our proposed appraoch.
4.1 EXPERIMENTAL SETUP
Model architecture. We use a Transformer architecture with three layers and single self-attention head. The dimension of each token embedding is 128. We apply Dropout at the end of each decoder block with a probability 0.1. We follow the learning rate scheduling proposed by Radford et al. 20188). with the learning rate increasing linearly from to 6 10-1 over the course of 3600 updates,
5

---

Under review as a conference paper at ICLR 2023
and then using cosine decay for up 7200 steps. We use batch size of 64. The full details of the architecture are presented the Appendix.
MCTS---aaaa -SaSs--adddd-e model to generate 250,000 games. We use these games to train MCTrasiformer's Transformer component. To generate this dataset, ran 30 distributed MCTS random boards, configured with simulation decay and an initial value 16 simulations per move. Note that full list our model's hyperparameters is presented in the Appendix.
Initial training set. As described in Section 3.2
Evaluation datasets. We evaluate MCTrasnformer and the baselines on three data-sets. All datasets consist of boards whose dimensions are 10 10, and have five colors each. The configurations of the datasts are as follows:
100 fully-random boards all tile colors are assigned randomly.
25 balanced boards each board contains exactly 20 tiles of each color. This dataset represent more difficult planning problem, since the likelihood of creating large blocks is smaller than in cases where one of the colors dominant.
25 dominant-color boards one of the five colors consists of more than 40 tiles. This setup consists of a less challenging planning problem, because the chances of creating larger blocks (that will assist in clearing the board) is larger.
Hardware and training time: MCTrusnformer's training took place nl al-highhem-8 instance on Google Cloud with 2 NVIDIA Tesla T4 GPUs, for 8 epochs, taking approximately hours.
4.2 PERFORMANCE INDICATORS
We record and analyze multiple indicators of the performance of our analyzed methods. The goal is not to only evaluate models based on their final score (although it is the primary metric), but also based on efficiency and relative efficacy per step. Our metrics are:
1. Score RTG((s)) = -' r(8,, 0z). The primary indicator, used to evaluate overall per- formance.
2. Net Score. The sum of all the rewards throughout game, but without the bonus of clearing the board, and also without the penalty for remaining tiles. Specifically, a policy that aims create large blocks will score higher this metric.
3. Final Reward. The last reward is either a bonus of 1000 points for clearing the board, or penalty for remaining tiles (see Section section 2.1p
4. Total Removed Tiles. The total number of tiles removed in a game. This indicator is equivalent to the score, but the defined reward function (see Section 2.1 can change the policy puts accordingly.
5. Number Cleared Boards. This metric measures the number of games in which the board was cleared. This metric less noisy that evaluating the overall score and the associated 1000 point bonus.
6. Average Reward per Move RTG(Se)
T-1 An strong model would seek to optimize its moves (i.e., clear blocks that are as large as possible) while also aiming to obtain the bonus. Mod- els that can effectively pursue these two goals will score higher this metric.
7. Number of Simulations. Because our framework is based on MCTS, we choose the num- ber of total simulations per episode as an indicator for the method efficiency. This metric is not relevant for the transformer-basee player (see next section).
We report mean and standard deviation for each indicator when applicable.
4.3 TRANSFORMER BASED PLAYER
We begin by evaluating the Transformer- based component of our model. Our goal is determine whether our Transformer is indeed capable of learning across multiple boards and positions, and select effective moves. The training process of the model is identical to the described in Section

---

Under review as a conference paper at ICLR 2023
100 random hoards
25 balanced boards
dominant color boards
random
transformer
random
transformer
random
transformer
Total Score
3229
13517
647
2600
18727
29118
Score
42.2(135)
183.(888)
25.9(83.6)
104(61.5)
766(356)
1173(437)
Net. Score
78.8(58.3)
155(78.4)
25.9(83.6)
119(52.0)
766(356)
1173(437)
Final Reward
336,((177)
-20.5(24.6)
-50.7(57.7)
-14.7(19.6)
-16.8(21.5)
-8(12.6)
Removed Tiles
79.9(9.13)
84.6(6.74)
71.7(7.97)
86.7(6.68)
85.7(6.19)
88.8(4.92)
Moves
27.0(3.96)
26.1(3.01)
26.0(3.70)
27.4(3.15)
18.7(2.99)
16.6(2.12)
Avg. Reward
3.08(2.64)
6.25(3.86)
3.06(1.96)
4.47(2.26)
42.9(22)
72.7(31.3)
Table 1:
The performance of Transformer-basel player against a random player on three sets of boards. All performance indicators except Total Score are provided as mean(std).
3.4 The input of the Transformer the sequence of all states and actions from the start of the game (i.c.. non-Markovian). We evaluate our Transformer in a straightforward manner: at each state, our model receives its input, and then selects an action (the model deterministic). There are no multiple simulations at any stage, and this step is repeated until the game ends.
Given that our Transformer does not have an explorationeexploitaiin mechanism, would require significant amounts of time and computing resources to achieve top performance. This type of evaluation beyond the scope of this study, which focuses on efficiency. We therefore compare our performance to that of random agent, with the simple goal of demonstrating that Transformer is capable of meaningful and effective learning. The results of our evaluation are presented in Table I and they show that our Transformer significantly outperforms the random baselines in all metrics. The average reward per move metric, for example, shows that the Transformer is much more capable in selecting larger blocks, which also help drive up its total score.
Finally, we evaluate the Transformer's ' performance when it only receives the current state as input (i.e., Markovian model). Our goal is determine whether providing the Transformer with the full trajectory (up to the current state) would reduce its performance. Our results, presented in Table Ōlin the Appendix, clearly show that the lack trajectory history significantly reduces performance. For example, the total score for the 100 random boards setup, decreases by 62%, from 13,517 to 5,085. We therefore conclude that providing full trajectory history to our model is required for its performance.
4.4 MCTrasnformer
We now compare MCTrasnformer various versions of the MCTS algorithm. Because of its ability to balance exploration and exploitation, MCTS is a high-preforming baseline. The quality of its performance, however, highly-depender on the number of simulations per move.
Our evaluation is conducted as follows: for the 100 random boards dataset, we evaluate the MC- Trasnformer with 8, 16 and 20 simulation per move, while the MCTS evaluated with 8. 16, 32, 64 and 128. Our results, presented in Table (where we only show the x16 configutaion due to space constraits) and Figure 2 shows that MCTrasnformer outperforms even the MCTS configura- tion with the 128 simulations per move. The figure also clearly shows that MCTrasnformer forms Pareto front compared to MCTS (i.e., a better score/number of simulations trade-off at all points). Even more importantly, MCTrusfformer leads in three key metrics: total score, net score and aver- age reward/move. These results show that not only does our approach consists of very few dominant boards. Our model therefore has greater difficulty in planning for such scenarios.
RELATED WORK
5.1 THE MONTE-CARLO TREE SEARCI ALGORITIM
Monte Carlo Tree Search (MCTS) is a heuristic search algorithm, that has proven itself highly ef- fective in multiple domains Browne al. 2012); Swiechowski et al. (202)) The method navigates through a search tree in a manner that balances exploration (evaluating new options) and exploita- tion (taking advantage of existing knowledge). MCTS is often used general-purpose planning

---

Under review as a conference paper at ICLR 2023
1000
25
MCTransformer
MCTransformer
800
MCTS
20
MCTS
avg. reward
600
15
400
10
200
50
100
150
simulations/move
simulation/move
1200
MCTransformer
MCTransformer
1000
reward
800
net. score
400
600
400
200
200
100
100
150
simulation/move
simulations/mave
Figure 2: The performance of MCTrasnformer against MCTS on 100 random boards as a function of the number of simulations per move.
model
MCTrusnformer x16
MCTS 8
MCTS
MCTS 32
MCTS 64
MCTS 128
Total Score
47704
15088
26340
28951
37506
455667
Score
477.044383.06
250.884250.14
263.42236.19
289.514261.1
375.064388.5
455.67#388.55
Net Score
300.39+127.82
94*42.87
218.6=114.8
229.5
260.29+121 .88
268.68#100)
Final Reward
176.65#387.75
56.884239.66 62
44.814220.64
55.891239.8
114.774328.6
186.994395.77
Removed Tiles
92.27=5.5
93.5245.25
90.51#5.24
90.7424.78
90.2945.53
92.4245.26
Simulations
433.28=55.36
261. 261.28=25.3
446,7=52.5
873.62103.7
1711#238
3480+410
Moves
27.08:3.46
31.6643.16
26.943.29
26.323.24
25.7413.73
29.12.3.2
Cleared Boards
5
12
Avg. Reward
12.1326.36
3.085+1.68
8.56255.48
9,345.03
10.73*6.13
10.7845.68
Table 2: MCTrasnformer with 16 simulations per move compared to MCTS on on 100 random boards
algorithm, and it was effectively applied to diverse domains such as Bayesian reinforcement learning Vien et (2013), multi-party negotiations Golpayegani et al. (2016). combinatorial optimization Ontanón 2013). and sigle-player games Schadd et al. (2008); y; Seify & Buro (2020); Rosin (201T);
Méhat ( 2010). More recently, MCTS has been an important part of the highly influential AlphaGo Silver et al. (2016) and AlphaZero Silver et al. (2017) architectures.
MTCS- solutions have several important strengths. First, the approach does not require domain-specific knowledge Klein (2013) Jacobsen et al. (2014) Hu et al.] (2019). and thus is easily applied to any domain that can be represented as set of sequential decisions. Secondly, while heuris- tics and prior knowledge are not required for it to perform well, MCTS can be augmented with such techniques to improve its ability to assess alternative actions. Thirdly, the training of the model can be performed on any available budget; once the budget is exhausted, the MCTS can utilize whatever knowledge it has been able to obtain.
5.2 UTILIZING TRANSFORMERS IN REINFORCEMENT LEARNING
Despite their state-of-the-an performance in many domains, Transformers have only been recently introduced to the field of RL. The first attempts in this field sought to adapt Transformers so that they can be used within existing solutions. In Parisotto et al. (2020), the authors present the Gated Transformer architecture. By integrating a gating mechanism into the original transformer architec- ture, the authors able to improve the model's stability and successfully utilize it for RL tasks.
8

---

Under review as a conference paper at ICLR 2023
model
MCTrastoommr
MCTS 8
MCTS 16
MCTS
MCTS 64
MCTS 128
Total Score
12173
3944
5516
6084
6908
11193
Score
486.92+422..5
157.76476.99
220.644232.18
243.364210.88
276.324215.71
447.72#394.58
Score
249.08286,48
161.56477.6
184473.2
207.16=82.7
241.52478.6
249.8476,66
Final Reward
237.842437.14
-3.826.27
36.64200.82
36.24200.92
34.8+201.25
197.924409.33
Removed Tiles
93.32+5.38
90.68+4.14
91.12+4.15
90.6+2.92
90.6424.46
93.72+4.77
Simulations
219.52427.24
226.56428.72
449.92440.08
871.68493.42
1725.444215.88
3481.62419.66
Moves
26.444334
27.3243.59
27.1242.5
26.24#2.92
25.96*3.37
26.243.28
Cleared Boards
6
0
5
Avg. Reward
9.8324.25
6.2943.66
7.0243.3
8.13+3.62
9.67=3.9
9.88+3.88
Table 3: MCTrasnformer with 8 simulations per move compared to MCTS on 25 balanced boards
model
MCTrasnfommer x8
MCTS 8
MCTS 16
MCTS
MCTS 64
MCTS 128
Total Score
42062
42880
44209
46435
50156
52584
Score
1682.484426.74
1715.24502.82
3768.361491.37
1857.44525,2
2006.242553.15
2103.362-48351
Net Score
1602.228447.99
1640.96=522.9
1731 4331.644499.52
1823.41517.87
1809.88#499.06
1745.24571.99
Final Reward
76,24278.09
74.241279
34+201.49
110.79
196.362410.18
358,161491.32
Removed Tiles
91.24+5.07
91.36+5.75
91.96+5.077
90.6845.65
92.7645.84
95.245.05
Simulations
136.64424.32
226.56428.72
290.56240.96
556.8475.05
1192.962168.19
2447 3447.66558..4
Depth
16.0823.04
17.3642.94
17.1642.56
16.422.35
17.6442.63
18.1243.97
Cleared Boards
2
2
5
6
Reward
105.07=39.2
99.98441.43
107.
107.4440.74
116.67445.17
107.4140.7
104. 104.88448.04
Table 4: MCTrasnformer with 8 simulations per move compared to MCTS on 25 dominant color boards
In Zambaldi et al. (2018). Transformers and other advanced architectures were using to better model advanced relationships in the problem domain.
Instead of integrating them in existing RL frameworks, other studies seek to develop ways to utilize the strengths of Transformers. In Chen et al.] (202I), the authors present the Decision Trans- former, whose goal is to model the planning problem The model receives as input the state and action representations, as well as the sum of remaining future rewards. The Transformer is then tasked with completing the sequence of states and actions in a way that obtains the specified reward. Another sequence modeling-baat basidgg--ddddddd approach was proposed Janner al. (202T), where instead of future rewards, the model receives the rewards incurred by its current actions. Another difference between the two approaches is the use of Beam Search Zhuo al. (2020) to improve the planning process.
of autoregressive sequence completion.
One of the main challenges in the modeling of RL problems as those of sequence comple- tion/generation,
difficulty of performing efficient exploration. While exploration is an integral part of many RI. algorithms (e.g.. MCTS) This is not the case here. As a result, using Transformers to discover effective solutions may require very long training times and be computationally pro- hibitive. In Zheng et al.| (022bb), the authors seek mitigate this problem by proposing online training phase, where the Transformer can be fine-tunes to respond to changing circumstances. An- other approach presented in Correia & Alexandre (2022), where hierarchical Transformer with sub- lob-goals was used to improve the exploration process.
CONCLUSIONS
One of the main challenges in using Transformers in the field RL. the need to perform effective exploration and planning. Studies that seek to utilize the strengths of the architecture use model the RL as one of sequence modeling, i.c.. supervised learning. This setup makes exploration, key component of RL, more difficult. In this study we proposed novel approach for integrating Transformers into the MCTS algorithm. This combination enables us to use the latter for effective exploration, while utilizing the former's advanced modeling abilities to identify high-reward paths of action. Evaluation on the challenging domain of SameGame demonstrates that our approach outperforms both the MCTS and Transformer algorithms.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Thomas Anthony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. Advances in Neural Information Processing Systems, 30, 2017.
Cameron Browne, Edward Jack Powley, Daniel Whitehouse, Simon M. M. Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez Liebana, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in Games, 4:1-43, 2012.
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch, Decision transformer: Reinforcement learnin via sequence modeling. Advances in neural information processing systems, 34:15084-15097 2021.
André Correia and Luis A Alexandre. 17Xiv22299100477 2022.
Hierarchical decision transformer.
arXiv preprint
Fatemeh Golpayegani, Ivana Dusparic, Adam Taylor, and Siobhán Clarke. Multi-agent collaboration for conflict management in residential demand response. Computer Communications, 96:63-72,
2016.
Zhiming Hu, James Tu, and Baochun Li. Spear: Optimized dependency-aware task scheduling with deep reinforcement learning. In 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), pp. 2037-2046, 2019, doi: 10.1 10.1109/C 2019.0001.. 10.100000........00000....
Emil Juul Jacobsen, Rasmus Greve, and Julian Togelius. Monte mario: platforming with mets. In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, pp- 293-300, 2014.
Michael Janner, Qiyang Li, and Sergey Levine. Offline reinforcement learning as one big sequence modeling problem. Advances in neural information processing systems, 34:1273-1229 2021.
Simon Klein. Attacking samegame using monte-carlo tree search: using randomness guidance in puzzles, 2015.
Kiminori Matsuzaki. Empirical analysis of puct algorithm with evaluation functions of different quality. In 2018 Conference on Technologies and Applications of Artificial Intelligence (TAAI),
pp. 142-147, 2018. doi: 10. (0.110)) 1091TAAAAAA2111 201.000433...
Jean Méhat and Tristan Cazenave. Combining uct and nested monte carlo search for single-player general game playing. IEEE Transactions on Computational Intelligence and Al Games, 2(4): 271-277, 2010.
Santiago Ontanón. The combinatorial multi-armed bandit problem and its application real-time strategy games. In Ninth Artificial Intelligence and Interactive Digital Entertainment Conference, 2013.
Emilio Parisotto, Francis Song, Jack Rae, Razvan Pascanu, Caglar Gulcehre, Siddhant Jayakumar, Max Jaderberg, Raphael Lopez Kaufman, Aidan Clark, Seb Noury, et al. Stabilizing transformers for reinforcement learning. In International conference on machine learning, pp. 7487-7498. PMLR, 2020.
Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, al. Improving language under- standing by generative pre-training. 2018.
Christopher D Rosin. Nested rollout policy adaptation for monte carlo tree search. In Swenty-Second International Joint Conference on Artificial Intelligence, 2011.
Maarten PD Schadd, Mark HM Winands, HJVD Herik, Guillaume MJ-B Chaslot, and Jos WHM Uiterwijk. Single-player monte-carlo tree search. In International Conference on Computers and Games, pp. 1-12. Springer, 2008
Arta Seify and Michael Buro. Single-agent optimization through policy iteration using monte-carlo tree search. arXiv preprint arXiv:2005. 1335, 2020.
10

---

Under review as a conference paper at ICLR 2023
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354 55077676):334-3359, 2004,-1,,1, 2017.
Maciej Swiechowski, Konrad Godlewski, Bartosz Sawicki, and Jacek Ma'ndziuk. Monte carlo tree search: A review of recent modifications and applications. ArXiv, abs/2103.04931, 2022.
Frank W. Takes and Walter A. Kosters. Solving samegame and its chessboard variant. 2009.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Ngo Anh Vien, Wolfgang Ertel, Viet-Hung Dang, and TaeChoong Chung. Monte-carlo tree search for bayesian reinforcement learning. Applied intelligence, 39(2):345-353, 2013.
Vinicius Zambaldi, David Raposo, Adam Santoro, Victor Bapst, Yujia Li, Igor Babuschkin, Karl Tuyls, David Reichert, Timothy Lillicrap, Edward Lockhart, et al. Deep reinforcement learning with relational inductive biases. In International conference learning representations, 2018.
Qinging Zheng, Amy Zhang, and Aditya Grover. Online decision transformer. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Pro- ceedings of Machine Learning Research, pp. 27042- PMLR, 17-23 Jul 2022a. URL https::/ iegooeeeeinng....... ngs..... m www.ppees//.. 62/ 222/2hhng22chtte
Qinqing Zheng, Amy Zhang, and Aditya Grover. Online decision transformer. arXiv preprint arXiv:2202.05667 2022b.
Jingwei Zhuo, Ziru Xu, Wei Dai, Han Zhu, Han Li, Jian Xu, and Kun Gai. Learning optimal tree models under beam search. In International Conference on Machine Learning, pp. 16500-11659. PMLR, 2020.

---

Under review as a conference paper at ICLR 2023
A APPENDIX
1000
20
1000
400
Mean Avg, Reward
750
750
15
Final Reward
Net. Score
300
500
500
Score
250
200
10
250
0
0
100
-250
-250
trans rand Players
trans rand Players
trans rand Players
trans rand Players
(a) 100 random boards
250
0
200
10
Mean Avg. Reward
200
-50
8
Final Reward
100
Net. Score
Score
150
-100
0
100
4
-150
-100
50
2
-200
-200
0
trans rand Players
trans rand Players
trans rand Players
trans rand Players
(b) 25 balanced boards
2000
2000
120
Mean Avg. Reward
-20
1500
1500
100
Final Reward
Net. Score
Score
80
-40
1000
1000
60
-60
40
500
500
20
-80
trans rand Players
trans rand Players
trans Players
trans rand
Players
(c) 25 dominant color boards
Figure 3: The performance Transformer-based player against a random player on three sets of boards
12

---

Under review as a conference paper at ICLR 2023
Table 5: Hyperparameters of Transformer
Hyperparameter
Value
Number of layers
3
Number of attention heads
Embedding dimension
128
Batch size
64
Max sequence length
45
Activation Functions
ELU, encoder, state embedding
GeLU, otherwise
tanh, embedding
State embedding channels
64
State embedding filter sizes
(3,3)
State embedding strides
Epochs
Dropout
0.1
Learning Rate
x 10-4
Adam betas
(0.9, 0.95)
Weight decay
0.1
Learning rate decay
Linear warmup(3600) and cosine decay
KPI
transformer
Total Score
5085
Score
50.85+63.1 1
Net. Score
82.73+45.75
Final Reward
-31.8833.999
Removed Tiles
82,0947.64
Moves
25.89+3.35
Avg. Reward
3.38+2.36
Table 6: Transformer performance on 100 random boards with no attention
13


Reviews:
[{"review_id": "uEAej3YiOBN", "reviewer": "Reviewer_cK37", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes MCTransformer by incorporating Transformer into Monte-Carlo Tree Search. The MCTransformer is then applied to SameGame, and the experiments show that MCTransformer outperforms both Transformer-only and MCTS-only solutions.\n", "summary_of_the_review": "The novelty of this paper is very poor. The structure is similar to AlphaGo/AlphaZero’s setting except only replacing the neural network from Resnet to Transformer. Overall, I did not find any new results in this paper.", "strength_and_weaknesses": "The main concern for this paper is the novelty. The authors simply used supervised learning to train the transformer network from the data generated by the MCTS-Based program on SameGame. Then, they apply the transformer network to MCTS. The structure is identical to AlphaGo/AlphaZero’s setting except only replacing the neural network from Resnet to Transformer.\n\nBesides, the experiment is unfair and not convincing:\n- Without using neural networks, the MCTS-based program can execute more simulation counts. The author should provide more experiment results to show that the comparison is fair, e.g. comparing the experiment with the same time limit rather than simulation counts.\n- It is very common to combine the MCTS with neural networks, such as AlphaGo, AlphaZero, or MuZero. The authors should compare the MCTransformer to other MCTS-based programs with neural networks.\n\nOther minor issues:\n- The author should consider using MCTransformer to generate the training dataset (step#2 in Figure1) as AlphaZero did. Currently, the performance of MCTransformer may be bound by the MCTS-based program.\n- In Figure 1: The definition of the step#6 and step#7 are unclear.\n- In section 3.5, “... standard MTCS difficult … ” should be “... standard MCTS difficult …”.\n- In section 5.1, “MTCS-based solutions …” should be “MCTS-based solutions …”.\n- Does it require a lot of time for using the Transformer in the rollout?\n- It’s meaningless to compare a well-trained network to a random play in Table 1.\n- The authors should try more simulation counts in the experiment in Figure 2 instead of using the regression line.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "LVcs9WJPFej", "reviewer": "Reviewer_scYv", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposed MCTransformer, a framework that combines Monte-Carlo Tree Search (MCTS) with the Transformer architecture in offline reinforcement learning. \nThe MCTS component is responsible for navigating and balancing the exploration/exploitation trade-off, while the Transformer component is responsible for evaluating the new states and also serves as a rollout policy to carry out the simulation phase of the MCTS.\nThe evaluation on SameGame shows that MCTrasnformer outscores Transformer-only and MCTS-only solutions.\n", "summary_of_the_review": "As described in the weaknesses above, it is hard to recommend this paper. ", "strength_and_weaknesses": "**Strength:**\nThe main idea of this paper is to combine Monte-Carlo Tree Search (MCTS) with the Transformer architecture in offline reinforcement learning. \n\n**Weakness:**\n- The method seems simply a combination of existing solutions (MCTS and Transformer) with limited novelty. Readers do not learn much from it. \n- Why does this paper choose the game of SameGame only to demonstrate their method? How about 2-player games?\n- In addition, the experiments are not convincing for the following. The authors only compare their method (a combination of Transformer and MCTS) with the random player, the Transformer-only and the MCTS-only. As a combination of existing solutions, the authors need to compare it with many other methods to support their claims. For example, those in Schadd et al. (2008); Takes & Kosters (2009); Schadd et al. (2012); Cazenave (2016); Seify (2020); Cazenave(2020). Even, it is probably more critical to compare with AlphaZero. More are listed as follows. \n  - To evaluate the effectiveness of MCTransformer on the SameGame, the authors should consider evaluating the proposed method with a standardized test set of 20 positions (these positions can be found at www.js-games.de/eng/games/samegame), which were reported in many prior works such as Schadd et al. (2008); Takes & Kosters (2009); Schadd et al. (2012); Cazenave (2016); Seify (2020); Cazenave(2020). \n  - Since the authors use offline data to train the Transformer policy, the author should compare the performance to other offline RL methods, or imitation learning methods (e.g behavior cloning).\n  - To show the effectiveness of using Transformer architecture in controlling the exploration and evaluation, the authors should compare the performance of using a Transformer architecture vs other deep neural network architecture.\n  - To show the effectiveness of the Transformer to carry out the simulation phase (i.e., the rollout policy) in MCTS, the authors should consider comparing the Transformer to heuristic-based policies or other learning-based policies.\n  - Since the author claims the effectiveness of using Transformer as the rollout policy, there is a need to describe the policy in the rollout phase of the MCTS-based method. For example: Is the rollout policy of the MCTS-based is a random policy or heuristic? And how many rollout simulations were performed at the selected leaves?\n\n**Comments for presentation:**\n- “Our approach combines Monte-Carlo Tree Search (MCTS) with the Transformer architecture in an actor-critic setup” is not well-explained in the paper.\n- Need more discussion for Table 3 and  Table 4.\n- Increase the font size of labels in Figure 1.\n- There are some typo mistakes and missing punctuations in the paper. For example: in the first line on page 5, the authors mentioned “Shefi’s Seify & Buro (2022) maxmin value normalization method”. Should “Shefi’s” be “Seify’s”?\n\n\n**References**\n\n[1]The positions can be found at www.js-games.de/eng/games/samegame.\n Maarten PD Schadd, et al. Single-player Monte-Carlo tree search for SameGame. Knowledge-Based Systems 34, 2012\n\n[2] Cazenave Tristan. Nested rollout policy adaptation with selective policies. Computer Games. Springer, Cham, 2016.\n\n[3] Cazenave Tristan, et al. Stabilized nested rollout policy adaptation. Monte Carlo Search International Workshop. Springer, Cham, 2020.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "95-V2Bisg8", "reviewer": "Reviewer_XF4h", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes to combine Decision/Trajectory Transformers (DTs) with MCTS, in order to improve the performance of DTs and also enable better exploration during online evaluation. The paper uses transformers as a prior policy for MCTS during the expansion phase, and also uses the same transformer to perform rollouts. The experiments are performed in the SameGame domain, which is a fully-observable Tetris like game with state-based inputs. The experiments show benefit over using using vanilla MCTS that learns only from monte-carlo returns.", "summary_of_the_review": "This paper proposes an elegant idea to combine MCTS with Trajectory Transformers to enable the latter to perform online improvement / exploration. While the idea itself is promising, the paper lacks in empirical execution and evidence (it terms of the domains and compared algorithms). The writing and exposition itself need some work. Owing to these factors, I don't think the paper is ready for acceptance at this time, but I do see a lot of legroom in the idea itself so this could be a great paper once the issues are fixed. ", "strength_and_weaknesses": "Strengths:\n* The paper tries to fix a key issue with Decision Transformers (DTs; transformers for sequence modelling of RL trajectories) like methods which is that they can't adapt easily at test time to explore more or improve their performance.\n* The particular setup of combining DTs and MCTS is novel, and I could see follow-up working building further on it.\n\nWeaknesses:\n* The writing and presentation is the paper is extremely unclear. The exposition of the method could be a lot better. See the below section for some suggestions. \n* The evaluation is extremely limited and non-standard, both in terms of the domains and algorithms. This makes is hard to assess if the original pitch of the paper empirically holds. \n  * The experiments performed are on a single, non-standard domain of SameGame which is relatively toy-ish as well. I would have liked seeing comparisons on more well-benchmarked domains like MiniGo or Atari. Similarly, there were no comparisons to DecisionTransformers or Online DTs which the paper supposedly improves upon.\n  * I am also not sure what to make of the MCTS comparisons, since from my understanding the paper doesn't use a learned prior policy or value function in the MCTS experiments (similar to AG/AGZ/Muzero), which makes the comparisons a bit unfair IMO. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject