Monte Carlo Tree Search With Iteratively Refining State Abstractions
Authors: Samuel Sokota
Caleb Ho
Zaheen Farraz Ahmad
J Zico Kolter
Venue: NeurIPS 2021 Poster (2021)
Keywords: decision-time planning
stochasticity
reinforcement learning
tree search

Abstract: Decision-time planning is the process of constructing a transient, local policy with the intent of using it to make the immediate decision. Monte Carlo tree search (MCTS), which has been leveraged to great success in Go, chess, shogi, Hex, Atari, and other settings, is perhaps the most celebrated decision-time planning algorithm. Unfortunately, in its original form, MCTS can degenerate to one-step search in domains with stochasticity. Progressive widening is one way to ameliorate this issue, but we argue that it possesses undesirable properties for some settings. In this work, we present a method, called abstraction refining, for extending MCTS to stochastic environments which, unlike progressive widening, leverages the geometry of the state space. We argue that leveraging the geometry of the space can offer advantages. To support this claim, we present a series of experimental examples in which abstraction refining outperforms progressive widening, given equal simulation budgets.

Monte Carlo Tree Search With Iteratively Refining State Abstractions
Samuel Sokota Carnegie Mellon University ssokota@andrew. cmu. cm.. edu
Caleb Ho Independent Researcher caleb. yh. ho@gmail....m..m..mm...m.......a com
Zaheen Ahmad University of Alberta zf afaaad@uulbeert.ccommmmm
J. Zico Kolter Carnegie Mellon University zkolter cmu edu
Abstract
Decision-ting time planning is the process of constructing transient, local policy with the intent of using it to make the immediate decision. Monte Carlo tree search (MCTS), which has been leveraged great success in Go, chess, shogi, Hex, Atari, and other settings, is perhaps the most celebrated decision-time planning algorithm. Unfortunately, its original form, MCTS can degenerate to one-step search domains with stochasticity. Progressive widening is one way to ameliorate this issue, but we argue that possesses undesirable properties for some settings. In this work, we present method, called abstraction refining, for extending MCTS to stochastic environments which, unlike progressive widening, leverages the geometry of the state space. We argue that leveraging the geometry of the space can offer advantages. To support this claim, we present a series of experimental examples in which abstraction refining outperforms progressive widening, given equal simulation budgets.
Introduction
In control problems, agent makes sequential decisions toward the end of accumulating large amount of reward [21]. Many reinforcement learning algorithms approach this task by computing policy, which, given state, dictates the agent's behavior; others operate under the paradigm of decision-time planning, in which, after the agent has arrived at a state, it spends additional computation constructing or revising its policy for the immediate decision(s). The decision-time planning paradigm can be advantageous because it allows for an additional step of policy improvement that is not available agents acting according to predetermined policy.
Of the numerous ways to perform decision-time planning. Monte Carlo tree search (MCTS) is among the most influential 66 [0 [15). Algorithms powered by MCTS, like AlphaZero and MuZero, yield strong performance in games with complex value function landscapes, like Go, chess, Hex, and shogi MuZero even shows strong performance Atari games, where model-free algorithms had previously been the most performant.
2 20
Unfortunately, in its original form, MCTS can degenerate to one-step search when the transition function has an infinite support. Even the support is finite but non-trivial, MCTS may be relegated to building shallow search trees. However, despite the importance of stochasticity in real-world problems, relatively little attention has been paid to this issue, perhaps as result of the fact that many popular benchmarks are deterministic tooos-tt-detemmnnstee
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

One way to address this issue is by using progressive widening 19. Progressive widening works by alternating between adding new children and selecting among existing children such that, asympototi- cally, the search tree becomes both infinitely deep and infinitely wide. Progressive widening is also advantageous because includes hyperparameters that control its propensity to add new children (as opposed to selecting among existing children). These hyperparameters can interpolate between width-wise expansion only (vanilla MCTS) and depth-wise expansion only (transition determiniza- tion). As result, with proper tuning, progressive widening is capable of performing well in both settings with important stochasticity and in settings with unimportant (or non-existent) stochasticity.
However, progressive widening's 's decision rule for expansion is the same for every transition. In settings with non-unifee non-uniform stochasticity, we argue that this property is undesirable, it requires progressive widening to compromise between focusing on unimportant stochasticity and ignoring important stochasticity.
In this work, we propose a new method, called abstraction refining, for extending MCTS to stochastic settings. Abstraction refining uses random and iteratively refining state abstractions defined by the geometry of the state space. If a newly sampled state is similar to state that is already in the tree, it discarded in favor of the pre-established state; otherwise, the newly sampled state is added the tree. Because the criteria for similarity becomes more strict the more often an abstraction is used, abstraction refining guarantees that, in the limit, the search tree will grow both infinitely wide and infinitely deep.
In addition proposing the abstraction refining algorithm, our contributions twofold. First, we present both a proof that, when used for policy evaluation, abstraction refining converges almost surely in finite MDPs. Second, we make empirical case that, provided a good notion of state similarity, abstraction refining can outperform progressive widening in settings with stochasticity of varying importance, given an equal simulation budget. To make this case, we present a series of domains in which i) stochasticity is sometimes, but not always, relevant to performing well on the task and ii) the naive notion of distance between states is reflective of behavioral similarity (though we also include some settings in which we use learned notion of distance). In these domains, we find that abstraction refining can outperform progressive widening.
2 Background
We consider a Markov decision process (MDP) setting (S.A. R, 7). with state space S, action space A, transition function T, reward function R and discount factor 7. The objective is to determine a policy æ that achieves a large expected cumulative reward E,, 1Et= ? (RR(st, at)]. Rather than explicitly computing function n, decision-time planning algorithms' policies are defined implicitly by their planning procedures. These planning procedures are given generative access to (i.e., the ability to sample from) the transition function T.
We also consider Markov reward process (MRP) setting (8, T, 7), with state space S, transition function T, reward function R, and discount factor An MRP is like an MDP, except that the agent passive observer, rather than a participator. Equivalently, one could also think of an MRP as an MDP in which the policy has been fixed and baked into the transition and reward functions. For the purposes of this work, the goal of an agent in an MRP is to evaluate the expected return from state-ie.., to perform policy evaluation.
2.1 Monte Carlo Tree Search
MCTS works by iteratively building a look-ahead tree of states. For each action a at a state s, the algorithm keeps track of the number of times the action has been selected at that state N(s, a) and the average of the value assessments of that action ((s, a). At each iteration, the agent (i) selects a leaf node to expand; (ii) expands the tree by adding child node of the leaf node; (ii) evaluates the newly added state, and (iv) backpropagates the evaluation from the new child to the root.
Selection In the selection phase, starting from the root node, which corresponds to the state so currently occupied by the agent, MCTS traverses the tree until a leaf node reached. The tree traversal is dictated by a selection policy. The most commonly used selection policies are based on the UCT algorithm [5), or its variants, like PUCT 18. Although it is less common, MCTS can also be used as policy evaluation algorithm. In this case, the selection policy is set to the target policy.

---

Expansion Once a leaf node is reached, the tree is expanded by adding a child of the leaf node to the tree. If the leaf node a terminal state, no children are added.
Evaluation Whenever MCTS adds a new state to the tree, it evaluates the state. Traditionally, MCTS practitioners performed evaluation by generating rollout to the end of the game using fast-to- evaluate simulation policy. Modern implementations often use a parameterized value function in lieu of simulation rollouts.
Backpropagation After MCTS evaluates a state, it updates the nodes along the path from the root to the evaluated state. Denote the path from the root to the leaf using Su, ao, Po..... Sy. Then for each pair (Sk, a&). MCTS updates Q(sk, 4+) using a weighted average between the existing value (sk: ax) and the leaf evaluation summed with the accumulated reward rk+1 +... +r.. Additionally each visit counter (88,, ax) gets incremented by one.
Selecting an Action To Execute After the search is over, MCTS selects an action for the agent to take. Common ways of doing this include selecting the action at the root node with the highest average Q-value, the action with highest lower confidence value or the action with the highest visit count. When used in an evaluation context, MCTS returns the average value of the root node.
What about Stochasticity? The description of MCTS above assumes that the environment is determinstic. In games with stochasticity, the selection process has an additional complication. Specifically, after an action a is selected at a state there is no uniquely determinable next state s', but rather, distribution over next states T(8, a). The most obvious way to extend MCTS to this setting is to sample s' ~ T(s.a). If there is already a child node for s', then that node is selected and the selection process continues. Otherwise, there no child node for 8', one added to the tree and evaluated. The consequence of this modification is that, for a fixed number of iterations, the search tree cannot be as deep as it would be a deterministic setting. In the most extreme case, where there are an infinite number of possible next states, this modification can degenerate MCTS into one-step search (because it may be the case that no state is sampled twice). This means that the performance of MCTS in games in which deep search trees are crucial for good performance could be ruined by arbitrarily small (but infinite support) perturbations to state representations.
2.2 Progressive Widening
Progressive widening [9] is one way to augment MCTS in such way that it can build deep search trees in arbitrarily stochastic domains The basic idea behind progressive widening is to alternate between sampling new next states and sampling among the next states that are already in the tree. If the state-action pair (s, a) has been tried a large number of times relative to the number of successor states in the tree, progressive widening adds a new state. On the other hand, if there are large number of successor states relative to the number of times N(s, a) has been tried, progressive widening samples among the successor states already in the tree. Whether or not to sample is determined by the boolean num_chiieee caann_cchceenss...m a] < - N(s, a) where a E [0, 1] and k E I4 are hyperparameters. Simplified pseudocode for the sampling step of progressive widening shown in Algorithm I
Informally, the hyperparameter a can be thought of as a propensity to select among existing children, progressive widening reduces to transition
rather than adding new children. When k = 1, a first time that a state-action pair is visited, a successor state is sampled and added the tree; thereafter, the same successor state is selected every time the state-action pair is visited. When l = 1, a = 1, progressive widening reduces to vanilla MCTS- time a state action pair is encountered, a new successor state sampled and added to the tree.
determinization
If k and a can be properly tuned, progressive widening offers flexibility. In domains in which stochasticity is important, can be set to one or close one. In domains in which stochasticity can be ignored, a can be set to zero or close to zero. Otherwise, an intermediate value often works well.
However, there is downside to progressive wideming. In particular, it cannot discriminate between stochasticity that matters and stochasticity can safely be ignored. This means that, if some stochasticity
NNte that we call progressive widening here is generally referred to as double progressive widening. Double progressive widening uses progressive widening over both the action space and the state space. For simplicity, this work restricts its attention to small action spaces, and therefore uses the term progressive widening to refer to the state space behavior.
3

---

is important but some is unimportant, the best thing that progressive widening can do requires either placing too much emphasis on unimportant stochasticity, or too little on important stochasticity.
Algorithm Progressive Widening
Algorithm 2 Abstraction Refining
procedure SAMPLE(S, a)
procedure SAMPLE(S, a)
N + num_ a)
5' TTssss a)
if num ham__hilldenn ss < kN then
~ T(x
s" -- mwaaneeatneeeeeee Srearest_neighbor(( children(s,d) al)
if d(('ss"") < (nnum_viit((s.a.. then
if s' E children(s, a) then children(s, ss, al sdd
return s" else
return s'
children|s, al.add(ss)
else
return s'
return sample(children(sssd))
Abstraction Refining
In this work, we introduce an alternative to progressive widening that we call abstraction refining. Abstraction refining is motivated by the deficiency of progressive widening described above: in settings with heterogeneous stochasticity, progressive widening is forced to make an undesirable compromise. Rather than defining expansion rate purely based on visit-count, progressive widening does, abstraction refining determines whether or not to expand using state similarity. At each selection step, abstraction refining samples new state and checks if similar to an existing child. If is, abstraction refining abstracts them together and selects the similar, existing child; if it is not, abstraction refining adds the new avoids the weakness of progressive widening: when stochasticity is unimportant, abstraction refining can cluster states together but when it is important, abstraction refining can cluster states separately. Simplified pseuodocode for abstraction refining is given in Algorithm
the tree. In doing so, in principle, abstraction refining
Each state abstraction is defined by princi- ples. The first principle is that, if a state to be abstracted, it should be abstracted to its near- est neighbor among states already in the tree. Equivalently, this principle states that, when ab- stractions take place, they should use mapping induced by the Voronoi diagram over the chil- dren in the tree.
The second idea is that, if abstraction is used many times, its notion of similarity should be- come more precise. This idea is motivated by controlling the amount of error that is introduced by state abstraction. A necessary condition for asymptotic correctness is that state abstrac- tions become arbitrarily small in the limit. To- ward that end, abstraction refining makes use of sequence {en JeE that is strictly decreasing (En >> 6m for < m) and going to zero in the limit (lim,,+oc 6, 0). A state that has been selected n times previously can only abstract new states within distance of G..
Figure 1: A visual depiction of an example low dimensional state space. There three states al- ready in the tree, represented by the black dots. The Voronoi diagram is shown using the colors blue, red and purple. The intersection of the Voronoi cells with each child's epsilon ball (shaded darker), corresponds to states that would be ab- stracted if they were sampled. The lighter shading shows the states that would be added to the tree if they were sampled.
low dimensional example is shown Figure
3.1 Consistency
Used for policy evaluation a finite MDP, abstraction refining is asymptotically consistent.

---

Proposition 1. Let (. be a finite Markov reward process with horizon h and bounded reward. Then for any s E S, abstraction refining' assessment of state s converges to u(s), almost surely, where uss) E
Σ d ((a)) Sa =
8 given a bounded evaluation function.
Proof. We proceed by induction. First, consider that for any state 84-1- abstraction refining converges surely after one iteration because v($)-1) = R(s;-1). Now consider some state sa at arbitrary depth d. The value assessed by abstraction refining after iterations is Vn(sa) = (sa) + E.ES... N.. VN (s) where Na. denotes the number of times that state s has been n
visited by the nth iteration. By Lemma [ we have that Na.n/n converges to T(s 8a) almost
surely. Note that by Lemma 2 and by inductive hypothesis, VN.... converges to v(s) almost surely. Then invoking the fact that the term-wise product of sequences of almost surely convergent random variables converges almost surely the product of the limits, and the fact that the term-wise sum of sequences of almost surely convergent random variables converges almost surely to the sum of the limits, and Lemma we conclude that Vn (sy) converges ((sa)+=Ess T(s sg)e(s) e(sa) almost surely.
Proofs for the lemmas below can be found in the appendix.
Lemma 1. For a fixed the sequence Na / converges almost surely to T(s |8a).
Lemma 2. For a fixed 8 with T(s sa) > O, the sequence Na.a diverges almost surely.
Lemma 3. Let X, be sequence converging to x almost surely. Let f: N + N be monotonically increasing, onto function. Then Yn X f(n) converges to z almost surely.
Given Proposition [
the extension to the discounted infinite horizon is relatively straightforward.
Corollary 1. Abstraction refining also converges almost surely in a policy evaluation setting for infinite horizon finite Markov reward processes, with rewards discounted by 7 [0,
Proof. (Sketch) Fix > O. Select h such Lish 7'm < </4, where m is a bound on the reward and evaluation function. Then the amount of error that can be accrued from states beyond time is bounded by c/2, surely. Additionally, by Proposition [ the amount of error that can be accrued over finite horizon is bounded by c/2 for all sufficiently large n, almost everywhere. Therefore, the aggregate error is bounded by e, almost everywhere for all sufficiently large n.
is important to note that convergence in the policy evaluation case does not guarantee convergence in combination with tree search algorithms (16). In contrast to abstraction refining, there do exist variants of progressive widening for which such guarantees have been proven [3]. In other words, the theoretical justification for abstraction refining presented here is less strong than the existing theoretical justification for progressive widening.
3.2 Runtime Discussion
In a decision-time planning paradigm, which is where MCTS is most often used, planning time is scarce. Thus, the runtime of algorithmic extensions to MCTS is important. However, high performance MCTS implementations almost ubiquitously use large amounts of parallelization [8]. As result, the most important analysis regards non-parallelizabl runtime. We discuss abstraction refining's 's runtime for both serial and parallelized cases.
Abstraction refining performs two potentially expensive computations. The first of these is sampling states s' ~ T(s,a), which could be costly if the simulator is slow, or if sampling is being executed from a large learned model. Abstraction refining must perform this sampling at each state it visits during its selection process. In contrast, progressive widening only needs to perform sampling once each selection process. Thus, in settings where sampling states is a bottleneck, abstraction refining could add significant amount of additional overhead on top of progressive widening. However, if sampling can be parallelized, this cost can be amortized by sampling a large number of next states in parallel the first time state-action pair is visited.
The second potentially expensive computation computing the nearest neighbor. This operation takes linear time serially (in the number of children) and logarithmic time when fully parallelized, and
5

---

Level One Chiidren
Level Two
Visual Depiction
Value Error
Chiidren
500
200
400
PWN230
150
300
PA32.5) 50
100
200
P0331
100
AR
0.1
100
200
900
400
500
0
100
200
300
400
500
100
200
500
400
900
Iterations
A comparison between progressive widening and abstraction refining designed to illustrate the drawback of progressive widening's s global hyperparameters. (far left) A visualization of the MRP: (middle left) value error, shown (middle right) number of nodes at depth one of the tree as a function of the number of iterations; (far right) number of at depth two of the tree function of the number of iterations.
Figure 2:
toy MRP
log scale, function of iterations;
must be performed at each step of the selection process. In contrast, progressive widening requires no such operation. Therefore, for systems in which nearest neighbor computation would be the bottleneck for MCTS, abstraction refining would be substantially more expensive per iteration than progressive widdnnin. On the other hand, for systems in which this would not be the case, perhaps such as those that use large networks to perform evaluations, abstraction refining may offer a cost per iteration competitive with that of progressive widening.
In our experiments, we compare abstraction refining and progressive widening given equal numbers of search iterations. It is worth bearing in mind, given the discussion above, that this is not always fair comparison.
Experiments
We present four sets of experiments in the main body of the paper. The first two investigate the prediction (policy evaluation) problem; the second two investigate the control problem. fifth set of experiments, as well as complementary experiments those in the main body of the paper, included in the appendix. In all plots, bands depict estimates of 95% confidence intervals computed using bootstrapping, except those in the pendulum plots in the appendix, which were computed using the central limit theorem.
Illustrating Progressive Widening's Weakness For our first experiment, we seek to confirm the claim made in previous parts the paper-that progressive widening is forced to make an undesirable compromise in situations with heterogeneous stochasticity. Toward that end, construct toy Markov reward process, depicted visually in Figure 2 (far left). In the MRP, the agent begins in the single state at the top. The first transition moves the agent to one of infinite number of very similar states (level one), shown in the middle. At these states, the reward function is zero and the transition function is nearly identical. The second transition moves the agent one of infinite number of dissimilar states (level two), shown at the bottom. The agent is given a bad value function for the level one states and a good value function for the level two states, reflecting a situation in which searching deeply is important. To evaluate the expected return in the fewest number of iterations, the optimal behavior for a state selector is to add as few level one children as possible and many level two children as possible.
This problem is difficult for progressive widening to address. For k = setting to small value restricts the number of level one children but also restricts the number of level two children (sce blue and orange in middle right and far right plots; Figure 2). But setting to large value causes progressive widening to repeatedly add a large number of Tevel one children, preventing focus on level two children (see purple in middle and far right plots: Figure ( Intermediate values of (see red and greed middle and far right plots; Figure 2 offer the best compromise but, nevertheless, add too many level one children and too few level two children.
In contrast, ahstraction refining is perfectly suited to address this problem-it can abstract the very similar level one states together while treating the dissimilar level two states separately using

---

1)(k=1)
PW(k=2)
PW(k=3)
PW((=4)
Valuee Error
PWaippal
-2
200
420
050
830
1000
200
-20
600
000
200
623
1000
230
400
800
800
1003
Iterations
Figure Abstraction refining (brown), with fixed set of hyperparameters, compared against progressive widening with various hyperparameter values on policy evaluation in continuous variant of blackjack. The value error (y-axis) shown on log scale.
En = 0.1 As a result, it can spend its entire quota on level two states (see brown in middle and far right plots; Figure These distinctions manifest directly in prediction error, as shown in Figure middle left plot, where abstraction refining outperformed progressive widening over each a value.
We also these experiments using other values of ic for progressive widening and found qualitatively similar results. For these plots and a specification of the MRP, see the appendix.
Policy Evaluation in Blackjack The previous section illustrated that, in policy evaluation setting designed adversarially for progressive widening, abstraction refining can offer superior per iteration performance. To confirm that the qualitative takeaway of the previous section not solely result of the adversarial design, this section investigates policy evaluation on less contrived setting a variant of blackjack with continuous card values. We chose a policy described by Wizard Odds Consulting. Details for the game, the policy, and plots with additional hyperparameters can be found in the appendix.
The results are shown in Figure 3 Abstraction refining with 6, = 2n -0.1 is shown in brown each subplot. The l value of progressive widening increases from one four from left to right. Darker colors correspond to smaller lighter values of alpha. An effort was made to prune noncompetitive a values from the graph to reduce visual clutter.
0.1
There are a number of observations make. First, notice the relationship between A and for progressive widening. As & becomes the larger, the most competitive values of a become smaller, reflecting the fact that l also plays a role progressive widening's 's propensity In general, the role k plays is fubtle-for k 1, the number of children at particular grows as min(n, "). This means that, for the first 11((-a) times a node is visited, it always adds a child but, thereafter, only adds new child much smaller proportion of the time.
expand its width.
Second, notice the instability that can result from small a values. This reflects the reality that small values build deep trees quickly, which can be advantageous, but expand slowly width-wise, leading to repeated evaluations states that do not accurately reflect the distribution.
Lastly, notice that while some settings of progressive widening perform competitively with abstraction refining for some iteration numbers, there is no setting that performs competitively across all iterations. In other words, progressive widening does not perform competitively with abstraction refining anytime basis. While this is not necessarily problematic in strictly policy evaluation context, it an undesirable for subcomponent of MCTS, used for control, for two reasons: first, because MCTS uses previous evaluations to inform its selection decisions, performing inaccurate evaluations at some iteration horizon could cause misallocate its budget to the wrong actions; second, because MCTS visits different actions and states vastly different numbers of times fashion that is not initially predictable, there is no good way to determine the iteration horizon for which to optimize.
Control in Trap Thus far, we have focused on comparing state selectors in a policy evaluation setting. While such comparisons make sense, as state selectors serve an evaluatory purpose, MCTS is rarely used for policy evaluation. result, the utility state selector closely linked to its ability to increase performance on control tasks. For first control experiment, use variant of the trap
7

---

PW(K=1/50)
PW(k=1/20)
PW(k=1)
PW(k=2)
120
Expected Return
165-
193
PW(alpha)
150
142
550
430
660
1000
200
800
662
662
1000
553
400
630
600
1000
500
400
000
600
1300
Iterations
Figure Abstraction refining (brown), with fixed set of hyperparameters, compared against progressive widening with various hyperparameter values on control in a variant of the trap problem.
problem, which first introduced in the original progressive widening paper 9 demonstrate the advantages of progressive widening compared to vanilla MCTS. The basic idea of problem is that an agent must move from one platform another without falling into the trap. Stochasticity comes in the form of actuator error-the amount the agent intends to move differs from the amount the agent actually moves by stochastic noise. specification of the problem, hyperparameter settings, and plots for additional hyperparameter values can be found in the appendix.
The results are shown in Figure 4 Abstraction refining with en 0.1n-0.1 is shown in brown in each subplot. Again, the value of progressive widening is shown increasing from left to right, the value is depicted by hue, with darker values meaning smaller as, and the plots pruned of non-competitive results to result visual clutter.
In the results, we see that single hyperparameter configuration of abstraction refining is able to outperform progressivew widening across a wide range of hyperparameters, One reason for abstraction refinement's strong performance here is likely that it is able to discriminate between having fallen into the trap and not having fallen into the trap. On the other hand, progressive widening has no mechanism for making this distinction, which may lead to it being overly confident about the safety large jumps. In the appendix, we show additional results for abstraction refining with distance function that does not allow for such distinction. We find that, given this distance function, abstraction refining is unable to reproduce the level of performance shown in Figure
Opponent Exploitation in Five by Five Go For our fourth experiment, we use AlphaZero to compare abstraction refining and progressive widening in opponent exploitation in five by five Go. In our setup, the first moving player (Black) is controlled by AlphaZero policy network. The second moving player (White) performs search using the latent state representation of the AlphaZero network its state representation of the system. Because Black's 's policy is fixed, White view the game as a stochastic MDP in which the transition function is dictated by Black's 's policy. We also add small amount of noise to the observation function to increase the difficulty of the search problem. We quantify performance using the amount of territory controlled by player at the end of game (i.e., the margin of victory), rather than the win-loss value. We modified OpenSpiel's [I7] AlphaZero and Go implementations for this experiment. Discussion of these design choices and the experimental setup can be found in the appendix.
Results are shown in F where uncertain, there appears to be upward trends in suggests that larger values of perform better, and in the number rollouts, suggesting that larger rollout budgets perform better, as expected. seems to be the case that abstraction refining able to outperform progressive able to abstract together board states that are behaviorally identical but differing superficially by the stochastic noise. In contrast, progressive widening is forced to treat these states separately.
for progressive widening. While results are somewhat
sooeminggpossbblly because it
Control in Pendulum An additional set of experiments performed on variant of pendulum in which the agent experiences actuator error are included in the appendix.

---

Bol B
17
PV/0.11
V B1
W 24
PWD.3)
PW/D.)
Expected
PWO
PINTT .0
:9 Wet
AR
W1 PASS vi
1988 w at (SBS widt a PAS8 w
Figure 5: (left) Abstraction refining (brown), compared against progressive widening with is 1 and various a values for opponent exploitation in five by five Go; (right) an example game in which the exploiter wins by the maximum margin (25).
Closing Discussion
On The Distance Function An important facet of abstraction refining that, heretofore, has gone largely uncommented upon, is that it requires a notion of distance between states in order to compute the nearest neighbor. It is readily apparent that using Euclidean distance representations, as we did in our first three experiments, would perform poorly in many cases. And while our 5x5 Go and pendulum experiments (the latter of which are included in the appendix) offer some initial work suggesting that using abstraction refining over learned state embedding can be successful, would be better to have a more principled way for constructing this distance metric. Perhaps the most natural notion of state similarity for abstraction refining is a bisimulation metric [1] Informally, under a bisimulation metric, two states are similar if, for all actions, the states yield similar rewards and (ii) the states have similar transition distributions (defined recursively in terms the bisimulation metric)-in short, if they are behaviorally similar. However, while there has been recent progress in learning bisimulation metrics [24 7 doing so in large MDPs with arbitrary transition distributions remains a challenging problem.
the canonical state
Related Work There are a number of works related to this one in that they use notion of distance between actions limit the branching factor and improve action selection. [hhmad al, show how to
leverage Delaunay triangulation for action selection in a single-decision setting [1] Yee et al. propose incorporating kernel regression into MCTS for continuous action spaces 123] Most recently, Kim et al. show how Voronoi diagrams can be applied to extend MCTS to a continuous action space [14]
Our work can be viewed as following in the spirit of that of Kim et al.] but focused on states (and evaluations) rather than actions (and control).
There has also been work leveraging state similarity for MCTS. Specifically, Xiao al. propose using kernel regression to improve state evaluations for MCTS (22). Experimentally, they show that using an intermediate layer of AlphaZero's policy-value network 19x19 Go compute similarity performs well in practice.
Outside of progressive widening 9 there also additional work performing state abstractions during search [13]. Specifically, Hostetler et al. al.. investigaee two mechanisms for adapatively refining state abstractions. The first, called random refinement, randomly divides existing state abstractions. The second, called decision tree-based refinement, uses a decision tree over feature space of the successor states to determine state abstractions, and adds new splits the for refinement.
Finally, there also additional work motivated by the deficiencies of MCTS in settings with large branching factors arising from stochasticity B 4 Antthny proposes
prohosss performing additional policy gradient updates to the network to improve the policy during decision time, rather than maintaining a tabular tree of visited nodes. Results suggest that this approach, called policy gradient search, can achieve performance comparable or superior to that of MCTS in Hex.
Summarizing Remarks This work introduces abstraction refining, new method for performing state selection for MCTS in stochastic environments. We prove that abstraction refining converges almost surely when used for policy evaluation in finite MDPs and, through a series of experiments, show evidence suggesting that abstraction refining can offer advantages over progressive widening in settings with stochasticity of varying importance, given an equal number of simulations.

---

Acknowledgments and Disclosure of Funding
We thank Ryan D'Orazio, Alexander Robey and Yiding Jiang for providing helpful feedback for this work.
This work was supported by funding from the Bosch Center for Artificial Intelligence.
References
[1] Z. F. Ahmad, R. Holte, and M. Bowling. Action selection for hammer shots in curling. In IJCAI, 2016.
[2] T. Anthony, Z. Tian, and D. Barber. Thinking fast and slow with deep learning and tree search. In Advances in Neural Information Processing Systems 30. 2017.
[3] T. Anthony, R. Nishihara, P. Moritz, T. Salimans, and J. Schulman. Policy gradient search: Online planning and expert iteration without search trees, 2019.
[4] T. W. Anthony. Expert iteration. PhD thesis, UCL (University College London), 2021.
[5] D. Auger, A. Couëtoux, and O. Teytaud. Continuous upper confidence trees with polynomial exploration - consistency. In H. Blockeel, K. Kersting, S. Nijssen, and F. Zelezný, editors, Machine Learning and Knowledge Discovery in Databases, pages 194-209, Berlin, Heidelberg. 2013. Springer Berlin Heidelberg. ISBN 978-3-642-40988-2.
[6] C. Browne, E. Powley, D. Whitehouse, S. Lucas, P. Cowling, S. Tavener, D. Perez, S. Samoth- rakis, S. Colton, and et al. A survey of monte carlo tree search methods. IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI, 2012.
[7] P. S. Castro. Scalable methods for computing state similarity in deterministic markov decision processes. In AAAL, 2020.
[8] G. M. J. B. Chaslot, M. H. M. Winands, and H. J. van den Herik. Parallel Monte-Carlo tree search. In H. J. van den Herik, X. Xu, Ma, and M. H. Winands, editors, Computers and Games, pages 60-71, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. ISBN 978-3-540- 87608-3.
[9] A. Couêtoux, J.-B. Hoock, N. Sokolovska, O. Teytaud, and N. Bonnard. Continuous upper confidence trees. In Proceedings of the 5th International Conference on Learning and Intelligent Optimization, LION'05. 05, page 433 345, Berlin, Heidelberg, 2011. Springge-Veelag. ISBN 9783642255656. doi: 10.
URL http::ttt//oooo org0/00.00/7
[10] R. Coulom. Efficient selectivity and backup operators in Monte-Carlo tree search. In H. J. van den Herik, P. Ciancarini, and H. H. L. M. Donkers, editors, Computers and Games, pages 72 83, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. ISBN 978-3-540-75538.8
[11] N. Ferns, P. Panangaden, and D. Precup. Bisimulation metrics for continuous Markov decision processes. SIAM J. Comput., 40(6): 662-1714, Dec. 2011. ISSN 0097-5397. doi: 10. 1377/ 10080484X. URL htLphttps://doi
[12] N. Ferns, P. Panangaden, and D. Precup. Metrics for finite Markov decision processes. AAAI, 2012.
[13] Hostetler, A. Fern, and Dietterich. Sample-based tree search with fixed and adaptive state abstractions. J. Artif. Int. Res., 60(1):717-777, Sept. 2017. ISSN 1076-9757.
[14] B. Kim, K. Lee, S. Lim, Kaelbling, and T. Lozano-Perez. Monte Carlo tree search in continuous spaces using Voronoi optimistic optimization with regret bounds. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06):9916-9924, Apr. 2020. doi: 10. 1609/ aaai. v4ii..340066646 URLhttps httph:://////t/ aaai, orraaaiiorrr///ooo http:///.w...aaaao.oooo////////a 6644
10

---

[15] L. Kocsis and C. Szepesvári. Bandit based Monte-carlo planning. In Proceedings the the 17th European Conference on Machine Learning, ECML'06, pages 282-293, Berlin, Heidelberg. 2006. Springer- Verlag. ISBN 3-540-45375-x, 978-3-540-45375-8 URL 0tt.ittp://da.......r/0000000000 10.
doi:
doi.
10007/118777184
[16] L. Kocsis, C. Szepesvári, and J. Willemson. Improved monte-carlo search.
[17] M. Lanctot, E. Lockhart, J.-B. Lespiau, V. Zambaldi, S. Upadhyay, J. Pérolat, S. Srinivasan, F. Timbers, K. Tuyls, S. Omidshafiei, D. Hennes, D. Morrill, P. Muller, T. Ewalds, R. Faulkner, J. Kramár, B. D. Vylder, B. Saeta, J. Bradbury, D. Ding, S. Borgeaud, M. Lai, J. Schrit- twieser, T. Anthony, E. Hughes, I. Danihelka, and J. Ryan-Davis. Openspiel: A framework for reinforcement learning in games, 2019.
[18] C. D. Rosin. armed bandits with episode context. Ann. Math. Artif. Intil, 61(3:203333 2011. URL htttt://bb/l //tblp..bpppp/ uni trier. de/dd////b/b. jtwrnaals/o//////////aa/a amaa ham.aa/mmmmi..... htthasssnn.tmmm1Roii1n11111
[19] Schrittwieser, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E, Lock- hart, D. Hassabis, T. Graepel, T. P. Lillicrap, and D. Silver. Mastering Atari, Go, chess and shogi by planning with learned model. Nature, 588 7839:604-609, 2020.
[20] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. P. Lillicrap, K. Simonyan, and D. Hassabis. Mastering chess and shogi by self-play with general reinforcement learning algorithm. ArXiv, abs/1712.01815,, 2017.
[21] R. S. Sutton and A. Barto. Reinforcement Learning: An Introduction, chapter 8.9, A Bradford Book, USA, 2018. ISBN 0262039249, 9780262039246.
[22] C. Xiao, J. Mei, and M. Müller. Memory-augmented monte carlo tree search. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018. URL https:://jjs.aat
org/ ttg/index.co php/ TAAT/aatticleevie//ISSS.
[23] T. Yee, V. Lisy, and M. Bowling. Monte Carlo tree search in continuous action spaces with execution uncertainty. In Proceedings of the Twenty-Fifh International Joint Conference on Artificial Intelligence, IJCAI' 16, page 690-696. AAAI Press, 2016. ISBN 9781577357704.
[24] A. Zhang, R. T. McAllister, R. Calandra, Y. Gal, and S. Levine. Learning invariant representa- tions for reinforcement learning without reconstruction. In International Conference on Learn- ing Representations, 2021. URL htttps://openreeiier www.rriwwwwieeteeieeeee...ee.mem ?id=- 2F

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See discussions on convergence,
runtime and distance function.
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See appendix
(b) Did you include complete proofs of all theoretical results? [Yes] See appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [No] We included each of the codebases used for the experiments the main body of the paper in the supplementary material and included descriptions of our experiments in the appendix. We did not record the specific seeds or include pretrained models. The AlphaZero results also depend the number of actors and the number and quality of devices, which would be difficult to replicate. We also did not include all of the code used to generate the experiments in the appendix.
(b)
Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [No] We included a substantial amount of detail about the training process, as well as each of the codebases for the experiments the main body of the paper in the supplementary material. We included plots for variety of hyperparameter settings in the main paper and in the appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See plots
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] We did not keep track of the total amount of compute used. We used an internal cluster.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] OpenSpiel
(b) Did you mention the license of the assets? [No] Can be found OpenSpiel Github.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "nIpBI0HeYI", "reviewer": "Reviewer_pc96", "summary": "The authors present MCTS with abstraction refining based on the nearest neighbor algorithm.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "MCTS has been a topic of interest in the AI/Machine Learning community over a decade and the authors address an important issue about MCTS. The paper is understandable with some interesting results. However, I have the following comments some of which could be clarified in the rebuttal phase:\n\n1. If I understand the algorithm correctly, how states are abstracted depends on the order of states selected during iterations of MCTS. I wonder how robust abstract refining is due to different orderings of the states.\n\n2. Some researchers have worked on MCTS with state abstractions. Particularly, the following paper might be related to the task they address. I wonder why iterative abstraction refinement was not compared against it. \n\nJesse Hostetler, Alan Fern, Thomas Dietterich. \"Sample-Based Tree Search with Fixed and Adaptive State Abstractions\", JAIR 2017. \n\nhttps://jair.org/index.php/jair/article/view/11096\n\n3. AlphaZero does not account for the size of the territory once a position is likely to be a win/loss -- it only cares about whether to win or loss. Therefore, it is not a good idea to evaluate the algorithm performance based on the territory size. Also, in my understanding, AlphaZero is not combined with search in section 4.4. If this is correct, what would the performance comparison be like if AlphaZero is combined with search? \n\nMiscellaneous\n\nThe authors should check the captions in the references (e.g,  Monte Carlo Tree Search which is currently with lowercase). \n\nUPDATE\n------------\nThanks for your response. I had discussions with other reviewers and am happy to increase my score. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "LAIJs5DS8T4", "reviewer": "Reviewer_MmsP", "summary": "The paper proposes a novel extension of MCTS to tackle stochastic state transitions with infinite support. It does so by leveraging the geometry of the state space to \"abstract\" \"similar\" states together during the tree building phase. Abstraction refining is introduced to assure that in the limit of infinite samples, the search-tree converges to the full tree, by introducing a schedule on the maximum abstraction distance, based on the number of samples observed.\nThe authors provide a proof of asymptotic convergence of abstraction refining in the policy evaluation setting.\nA brief discussion is done on the choice of distance function to employ during the state abstraction.\nFinally, an experimental campaign is conducted in several evaluation and control tasks, that show that abstraction refining consistently outperforms it's main competitor (progressive widening) in handling stochastic transitions with infinite or very large support.", "questions": "", "limitations": "", "rating": 6, "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": "The authors tackle the really important topic of planning in environments with stochastic transitions and infinite next-state support. The introduce abstraction refining, as a way to progressive build the full (infinite) search tree, by leveraging the geometry of the state space. \nThe authors, mainly compare their work, with progressive widening, the only method (apart from open-loop planning) able to tackle these kind of problem. \nThey provide a proof of convergence in the policy evaluation case, but do not provide a proof of convergence in the control case, which is a disadvantage compared with progressive  widening, which when used together with UCT, for an appropriate choice of schedule for the \\alpha parameter is shown to converge [1].\n\nThe authors provide a brief consideration of the additional computational costs of the method which show a limited additional cost, based on the dimensionality of the state space (or learned feature space) used to compute the distance.\n\nThe authors provide some experimental results both in the policy evaluation and in the control settings. The proposed method consistently shows better results than progressive widening in all the baselines. Nevertheless, the choice of baselines seems rather odd. While some simple baselines are chosen to study in detail the performance of abstraction refining (like the toy MDP, and the Trap environment), the authors also evaluate in a more complex scenario of 5x5 GO, which intrinsically has no stochasticity, bu the stochasticity is induced by considering the environment as a single player, and fixing the stochastic policy of the opponent. While this makes the environment stochastic, it still does not capture the main contribution of the paper, the capacity to handle larger (or infinite) branch factors of the tree, since the authors report that the best performing algorithm in this setting was Vanilla MCTS (in the appendix) and they were force to introduce an additional source of stochasticity to require the use of PW or AR. \nThe authors have a brief discussion of the choice of distance measure, since it is a crucial component of AR, but a more thorough experimental campaign is needed. Three of the presented domains, were simple enough to use Euclidean distance. In the 5x5 Go, the distance was employed on a learned state embedding, and nevertheless failed to improve on vanilla MCTS without an additional noise. \n\nI think the paper tackles an extremely important problem but more careful consideration of the distance measures needs to be adressed, at least experimentally.\n[1] Adrien Couetoux. Monte Carlo Tree Search for Continuous and Stochastic Sequential Decision Making\nProblems. Data Structures and Algorithms [cs.DS]. Université Paris Sud - Paris XI, 2013.\n\n======== Update ==≠====\n I have had a thorough discussion with the authors, during which the authors have agreed to the limitations that I pointed out, and also have conducted some experiments that demonstrate these limitations. In my opinion, it is ok to have limitations but they should be made clear, and especially better if demonstrated empirically. As a result, I will raise my score from 5 to 6, but this if the authors include a final experiment promised in the last rebuttle. While I am aware that as reviewers we cannot enforce the addition of the experiment, the authors have already made 3 new experiments during the rebuttle so I would be inclined to 'trust' the authors for this final experiment.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Main limitation is:\nThe need for a carefully thought distance measure.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "05haNYZryB", "reviewer": "Reviewer_b8VZ", "summary": "This paper proposes a method, called abstraction refining, for extending MCTS to stochastic environments that leverages the geometry of the state space. Compared to progressive widening with global hyperparameters for every state, abstraction refining groups the states together dynamically depending on each state. Their results show abstraction refining outperforms progressive widening in the way of their experiments of this paper.", "questions": "", "limitations": "", "rating": 6, "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": "While it is interesting for the proposed method to reduce the large search space like progressive widening, there are the following major concerns. \nThis paper gives four examples in the experiments, but experimental analyses are most based on value errors. It is not convincing in this way since the most important criteria for MCTS is the strength, not just value errors. This paper still needs more experiments including the strength to demonstrate the idea is working.  \nIn addition, in these examples, the nearest neighbors are calculated all based on the geometry of state  space (or Euclidean distance). It is very hard to convince people to believe that this would work for some games, like Go. This paper mentions we could use better distance functions for the nearest neighbors in the Discussion section; however, actually, it is the most important work that this paper needs to do to showcase the excellence of their method. \nThe proposed idea for grouping state by abstraction refining to reduce the branching factor is somewhat similar to [11], which is applied to many continuous action space problems. What’s the main difference between the presented method and their work? A continuous action space can also be viewed as a large action space problem. \nThis paper tries to justify the computation cost for the nearest neighbor in the last paragraph of Section 3.2, where the cost is derived to be O(log p) or O(log num_children[s, a]) in the parallel time complexity based on the assumption of unlimited (or a large number of) processors. Unfortunately, this assumption is strange and not realistic. It is more important and interesting to justify it through experiments. \n\n\nOther comments:\nThe abstraction refining hyperparameters (epsilon_n) are quite different in each experiment. Why? Any guideline to set the hyperparameters? Or, it is a need to do more experiments for different epsilon_n in abstraction refining?\nIt is also required to analyze the branch factor for abstraction refining and progressive widening for each experiment. \n\nAbout presentation:\n* In line 176, c in R_{s’’}^{c} is undefined. \n* What is the epsilon_n used in five by five Go? BTW, it is suggested using “5x5 Go”. \n* Some typos:\n** Line 40: and and -> and\n** Line 98: determinstic -> deterministic\n** Line 147: pseuodocode -> pseudocode\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper generated a good amount of discussion between the authors and reviewers, which helped resolve some issues in the original reviews. Certain issues remain, but the paper does seem to be making a reasonable and novel contribution in light of those issues. 

The reviewers have worked hard to suggest improvements and the authors have already indicated the inclusion of new experiments and adjustments to the text. It is expected that the authors will follow through on these promises. 

Finally, I would like to point out that the authors have not properly characterized the related paper pointed out by one of the reviewers.

Jesse Hostetler, Alan Fern, Thomas Dietterich. "Sample-Based Tree Search with Fixed and Adaptive State Abstractions", JAIR 2017

The authors indicate in their response that the paper assumes more than a sample-based model, but that is not accurate. It does not assume access to the entire set of next states. Also note that the algorithm in the experiments of that paper is based on forward-search sparse sampling, which is a trajectory-sampling algorithm in the spirit of MCTS/UCT. Thus a modification to MCTS is not as distance as the authors may think. 
Decision: Accept (Poster)