Lookahead Pathology in Monte-Carlo Tree Search

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 04:27:53

Abstract: Monte-Carlo Tree Search (MCTS) is an adversarial search paradigm that first found prominence with its success in the domain of computer Go. Early theoretical work established the game-theoretic soundness and convergence bounds for Upper Confidence bounds applied to Trees (UCT), the most popular instantiation of MCTS; however, there remain notable gaps in our understanding of how UCT behaves in practice. In this work, we address one such gap by considering the question of whether UCT can exhibit lookahead pathology --- a paradoxical phenomenon first observed in Minimax search where greater search effort leads to worse decision-making. We introduce a novel family of synthetic games that offer rich modeling possibilities while remaining amenable to mathematical analysis. Our theoretical and experimental results suggest that UCT is indeed susceptible to pathological behavior in a range of games drawn from this family.

Main paper: 
 introduction: 
 Monte-Carlo Tree Search (MCTS) is an online planning framework that first found widespread use in game-playing applications (Coulom 2007; Finnsson and Björnsson 2008;  20 Arneson, Hayward, and Henderson 2010) , culminating in the spectacular success of AlphaGo (Silver et al. 2016 (Silver et al. , 2017)) . MCTS-based approaches have since been successfully adapted to a broad range of other domains, including combinatorial search and optimization (Sabharwal, Samulowitz, and Reddy 2012; Goffinet and Ramanujan 2016) , malware analysis (Sartea and Farinelli 2017) , knowledge extraction (Liu et al. 2020) , and molecule synthesis (Kajita, Kinjo, and Nishi 2020) .Despite these high-profile successes, however, there are still aspects of the algorithm that remain poorly understood.Early theoretical work by Kocsis and Szepesvári introduced the Upper Confidence bounds applied to Trees (UCT) algorithm, now the most widely used variant of MCTS. Their work established that in the limit, UCT correctly identified the optimal action in sequential decision-making tasks, with the regret associated with choosing sub-optimal actions increasing at a logarithmic rate (Kocsis and Szepesvári 2006) .Coquelin and Munos, however, showed that in the worstcase scenario, UCT's convergence could take time superexponential in the depth of the tree (Coquelin and Munos 2007) . More recent work by Shah, Xie, and Xu proposes a "corrected" UCT with better convergence properties (Shah, Xie, and Xu 2020) .In parallel, there has been a line of experimental work that has attempted to understand the reasons for UCT's success in practice and characterize the conditions under which it may fail. Ramanujan, Sabharwal, and Selman considered the impact of shallow traps -highly tactical positions in games like Chess that can be established as wins for the opponent with a relatively short proof tree -and argued that UCT tended to misevaluate such positions (Ramanujan, Sabharwal, and Selman 2010a; Ramanujan and Selman 2011) . Finnsson and Björnsson considered the performance of UCT in a set of artificial games and pinpointed optimistic moves, a notion similar to shallow traps, as a potential Achilles heel (Finnsson and Björnsson 2011) . James, Konidaris, and Rosman studied the role of random playouts, a key step in the inner loop of the UCT algorithm, and concluded that the smoothness of the payoffs in the application domain determined the effectiveness of playouts (James, Konidaris, and Rosman 2017) . Our work adds to this body of empirical research, but is concerned with a question that has thus far not been investigated in the literature: can UCT behave pathologically?The phenomenon of lookahead pathology was first discovered and analyzed in the 1980s in the context of planning in two-player adversarial domains (Beal 1980; Nau 1982; Pearl 1983) . Researchers found that in a family of synthetic board-splitting games, deeper Minimax searches counterintuitively led to worse decision-making. In this paper, we present a novel family of abstract, two-player, perfect information games, inspired by the properties of real games such as Chess, in which UCT-style planning displays lookahead pathology under a wide range of conditions.Consider a planning instance where an agent needs to determine the best action to take in a given state. An MCTS algorithm aims to solve this problem by iterating over the following steps to build a search tree.• Selection: Starting from the root node, we descend the tree by choosing an action at each level according to some policy ⇡. UCT uses UCB1 (Auer, Cesa-Bianchi, and Fischer 2002) , an algorithm that optimally balances exploration and exploitation in the multi-armed bandit problem, as the selection policy. Specifically, at each state s, UCT selects the action a = ⇡(s) that maximizes the following upper confidence bound:⇡(s) = argmax a Q(T (s, a)) + c • s log n(s) n(T (s, a))Here, T (s, a) is the transition function that returns the state that is reached from taking action a in state s, Q(s) is the current estimated utility of state s, and n(s) is the visit count of state s. The constant c is a tunable exploration parameter. In adversarial settings, the negamax transformation is applied to the UCB1 formula, to ensure that utilities are alternatingly maximized and minimized at successive levels of the search tree. • Evaluation: The recursive descent of the search tree using ⇡ ends when a node s 0 that is previously unvisited, or that corresponds to a terminal state (i.e., one from which no further actions are possible), is reached. If s 0 is nonterminal, then an estimate R of its utility is calculated. This calculation may take the form of random playouts (i.e., the average outcome of pseudorandom completions of the game starting from s 0 ), handcrafted heuristics, or the prediction of a learned estimator like a neural network. For terminal nodes, the true utility of the state is used as R instead. The node s 0 is then added to the search 100 tree, so that the size of the search tree grows by one after each iteration.• Backpropagation: Finally, the reward R is used to update the visit counts and the utility estimates of each state s that was encountered on the current iteration as follows:Q(s) n(s)Q(s) + R(s) n(s) + 1 n(s) n(s) + 1This update assigns to each state the average reward accumulated from every episode that passed through it. We repeat the above steps until the designated computational 105 budget is met; at that point, the agent selects the action a = argmax a 0 Q(T (r, a 0 )) to execute at the root node r.Searching deeper is generally believed to be more beneficial in planning domains. Indeed, advances in hardware that permitted machines to tractably build deeper Minimax search trees for Chess were a key reason behind the success of Deep Blue (Campbell, Hoane, and hsiung Hsu 2002) . However, there are settings in which this property is violated, such as the P-games investigated by several researchers in the 1980s (Beal 1980; Nau 1982; Pearl 1983) . Over the years, many have attempted to explain the causes of pathology and why it is not encountered in real games like Chess. Nau et al. reconciled these different proposals and offered a unified explanation that focused on three factors: the branching factor of the game, the degree to which the game demonstrates local similarity (a measure of the correlation in the utilities of nearby states in the game tree), and the granularity of the heuristic function used (the number of distinct values that the heuristic takes on) (Nau et al. 2010) . They concluded that pathology was most pronounced in games with a high branching factor, low local similarity and low heuristic granularity.There is a long tradition of using abstract, artificial games to empirically understand the behavior of search algorithms. The P-game model is a notable example, that constructs a game tree in a bottom-up fashion (Pearl 1980) . To create a P-game instance, the values of the leaves of the tree are carefully set to win/loss values (Pearl 1980) , though variants using real numbers instead have also been studied (Luštrek, Gams, and Bratko 2005) . The properties of the tree arise organically from the distribution used to set the leaf node values. P-games were the subject of much interest in the 1980s, as the phenomenon of lookahead pathology was first discovered in the course of analyzing the behavior of Minimax search in this setting (Beal 1980; Nau 1982) . While the model's relative simplicity allows for rigorous mathematical analysis, P-games also suffer from a couple of drawbacks. Firstly, computing the value of the game and the minimax value of the internal nodes requires search, and that all the leaf nodes of the tree be retained in memory, which restricts the size of the games that may be studied in practice. Secondly, the construction procedure only models a narrow class of games, namely, ones where the values of leaf nodes are independent of each other.Other researchers have proposed top-down models, where each internal node of the tree maintains some state information that is incrementally updated and passed down the tree. The value of a leaf node is then determined by a function of the path that was taken to reach it. For example, in the models studied by Nau and Scheucher and Kaindl, values are assigned to the edges in the game tree and the utility of a leaf node is determined by the sum of the edge values on the path from the root node to the leaf (Nau 1983; Scheucher and Kaindl 1998) . These models were used to demonstrate that correlations among sibling nodes were sufficient to eliminate lookahead pathology in Minimax. However, search is still required to determine the true value of internal nodes, thereby only allowing for the study of small games. Furtak and Buro proposed prefix value trees that extend the model of Scheucher and Kaindl by observing that the minimax value of nodes along a principal variation can never worsen for the player on move (Furtak and Buro 2009) . Setting the values of nodes while obeying this constraint during top-down tree construction obviates the need for search, which allowed them to generate arbitrarily large games.Finally, synthetic game tree models have also been used to study the behavior of MCTS algorithms like UCT. For example, Finnsson and Björnsson used variations of Chess to identify the features of the search space that informed the success and failure of UCT (Finnsson and Björnsson 2011) . Ramanujan, Sabharwal, and Selman studied P-games augmented with "critical moves" -specific actions that an agent must get right at important junctures in the game to ensure victory (Ramanujan, Sabharwal, and Selman 2010b) .We refine this latter idea and incorporate it into a top-down model, which we present in the following section. 
critical win-loss games: 
 Our goal in this paper is to determine the conditions under which UCT exhibits lookahead pathology. To conduct this study, we seek a class of games that satisfy several properties. Firstly, we desire a model that permits us to construct arbitrarily large games to more thoroughly study the impact of tree depth on UCT's performance. We note that most of the game tree models discussed in Section 2 do not meet this requirement. The one exception is the prefix value tree model of Furtak and Buro that, however, fails a different test: the ability to construct games with parameterizable difficulty. Specifically, we find that prefix value games are too "easy" as evidenced by the fact that a naïve planning algorithm that combines minimal lookahead with purely random playouts achieves perfect decision-making accuracy in this setting (see Appendix A for a proof of this claim). In this section, we describe critical win-loss games, a new generative model of extensive-form games, that addresses both these shortcomings of existing models.Our model generates game trees in a top-down fashion, assigning each node a true utility of either +1 or 1. In principle, every state in real games like Chess or Go can be labeled in a similar fashion (ignoring the possibility of draws) with their true game-theoretic values. Thus, we do not lose any modeling capacity by limiting ourselves to just win-loss values. The true minimax value of a state imposes constraints on the values of its children as noted by Furtak and Buroin our setting, this leads to two kinds of internal tree nodes. A forced node is one with value 1 (+1) at a maximizing (minimizing) level. All the children of such a node are constrained to also be 1 (+1). A choice node, on the other hand, is one with value +1 ( 1) at a maximizing (minimizing) level. At least one child of such a node must have the same minimax value as its parent. Figure 1 presents examples of these concepts.All the variation that is observed in the structures of different game trees is completely determined by what happens at choice nodes. As noted earlier, exactly one child of a choice node must share the minimax value of its parent; the values of the remaining children are unconstrained. We introduce a parameter called the critical rate ( ) that determines the values of these unconstrained children. We now describe our procedure for growing a critical win-loss tree rooted at a node s with minimax value v(s):• Let S = {s 1 , s 2 , . . . , s b } denote the b children of s. • If s is a forced node, then we set v(s 1 ) = v(s 2 ) = . . . = v(s b ) = v(s), and continue recursively growing each subtree. • If s is a choice node, then we pick an s i 2 {s 1 , . . . , s b } uniformly at random and set v(s i ) = v(s), designating s i to be the child that corresponds to the optimal action choice at s. For all s j such that j 6 = i, we set v(s j ) = v(s) with probability and we set v(s j ) = v(s) with probability 1 , before recursively continuing to grow each subtree.We make several observations about the trees grown by 240 this model. Firstly, one can apply the above growth procedure in a lazy manner, so that only those parts of the game tree that are actually reached by the search algorithm need to be explicitly generated. Thus, the size of the games is only limited by the amount of search effort we wish to expend. 245 Secondly, the critical rate parameter serves as a proxy for game difficulty. At one extreme, if = 0, then every child at every choice node has the same value as its parent -in effect, there are no "wrong" moves for either player, and planning becomes trivial. At the other extreme, if = 1, 250 then every sub-optimal move at every choice node leads to a loss and the game becomes unforgiving. A single blunder at any stage of the game instantly hands the initiative to the opponent. Figure 2 gives examples of game trees generated with different settings of . For the sake of simplicity, we fo-255 cus on trees with a uniform branching factor b in this study.Before proceeding, we pause to validate our model by measuring the critical rates of positions in Chess (see Appendix E for similar data on Othello). We begin by first sampling 260 a large set of positions that are p plies deep into the game. These samples are gathered using two different methods:• Light playouts: each side selects among the legal moves uniformly at random. • Heavy playouts: each side runs a 10-ply search using the Stockfish 13 Chess engine (Romstad et al. 2017 ) (freely available online under a GNU GPL v3.0 license) and then selects among the top-3 moves uniformly at random. We approximate v(s) for these sampled states using deep Minimax searches. Specifically, we use v(s) ⇡ sgn (ṽ d (s)), where ṽd (s) denotes the result of a d-ply Stockfish search.To compute the empirical critical rate ˜ (s) for a particular choice node s, we begin by computing ṽ20 (s) and ṽ19 (s 0 ) for all the children s 0 of s and then calculate:˜ (s) = 1 b 1 X s 0 1[sgn (ṽ 19 (s 0 )) 6 = sgn (ṽ 20 (s))]Admittedly, using the outcome of a deep search as a stand-in for the true game theoretic value of a state is not ideal. How-270 ever, strong Chess engines are routinely used in this manner as analysis tools by humans, and we thus believe this to be a reasonable approach. Figure 3 presents histograms of ˜ data collected for p = 10 and p = 36, using both light and heavy playouts. Each histogram aggregates data over ⇠ 20, 000 positions.We note that about 40-50% of the positions sampled have ˜ values higher than 0.9, which is consistent with Chess's reputation for being a highly tactical game. We also see that the ˜ values collected for Chess form a distribution that is 280 non-stationary with respect to game progression, unlike in our proposed game tree model where is fixed to be a constant. Nonetheless, we believe that this simplification in our modeling is reasonable: at deeper plies, the distribution of ˜ becomes strikingly bimodal, with most of the mass accumulating in the ranges [0.0, 0.1] and [0.9, 1.0]. This clustering means that one could partition Chess game tree into two very different kinds of subgames (with high and low ), within each of which the critical rate remains within a narrow range.Before we can run UCT search experiments on critical winloss games, we need to resolve one more issue: how should UCT estimate the utility of non-terminal nodes? One popular approach to constructing artificial heuristics is the additive noise model -the heuristic estimate h(s) for a node s is computed as h(s) = v(s)+✏, where ✏ is a random variable drawn from a standard distribution, like a Gaussian (Luštrek, Gams, and Bratko 2005; Ramanujan, Sabharwal, and Selman 2011). However, as we will see, static evaluations of positions in real games often follow complex distributions.To better understand the behavior of heuristic functions in real games, we once again turn to Chess and the Stockfish engine. We sample ⇠ 100, 000 positions each using light and heavy playouts for p = 10. As before, we use sgn (ṽ 20 (s)) as a proxy for v(s) for each sampled state s. We also compute ṽ0 (s) for each s, which we normalize to the range [0, 1] -this is the static evaluation of each s without any lookahead. Figure 4 presents histograms of ṽ0 (s), broken out by v(s). A clearer separation between the orange and blue histograms (i.e., between the evaluations of +1 and 1 nodes) indicates that the heuristic is better at telling apart winning positions from losing ones. Indeed, the ideal heuristic would score every +1 position higher than every 1 position, thus ordering them perfectly. We see in Figure 4 that such clear sorting does not arise in practice in Chess, particularly for positions that are encountered with strong play. Moreover, the valuations assigned to positions do not follow a Gaussian distribution, and attempts to model them as such are likely too simplistic. However, these histograms also suggest an empirical method for generating heuristic valuations of nodes -we can treat the histograms as probability density functions and sample from them. For example, to generate a heuristic estimate for a 1 node s in our synthetic game, we can draw h(s) 2 [0, 1] according to the distribution described by one of the blue histograms in Figure 4 . Of course, given the sensitivity of the shape of these histograms to the sampling parameters, it is natural to wonder which histogram should be used. Rather than make an arbitrary choice, we run experiments using a diverse set of such histogram-based heuristics, generated from different choices of p, different playout sampling strategies, and Additionally, we note that one can also use random playouts as heuristic evaluations, like in the original formulation of UCT. One advantage of our critical win-loss game tree model is that we can analytically characterize the density of +1 and 1 nodes at a depth d from the root node, given a critical rate and branching factor b. Specifically, for a tree rooted at a maximizing choice node, the density of +1 nodes at depths 2d and 2d + 1 (denoted as f 2d and f 2d+1 respectively) are given by:f 2d = k 2d + 1 k 2d+2 1 + k (1) f 2d+1 = f 2d • k (2)where k = 1 + /b. We refer the reader to Appendix B for the relevant derivations. Access to these expressions means that we can cheaply simulate random playouts of depth 2d: the outcome of a single playout (`1) corresponds to sampling from the set {+1, 1} with probabilities f 2d and 1 f 2d respectively. For lower variance estimates, we can use the mean of this distribution instead, which would correspond to averaging the outcomes of a large number of playouts (`1).In our experiments, we explore the efficacy of the heuristics `1 and `1 as well.We begin with our main theoretical result and provide a sketch of the proof.Theorem 1. In a critical win-loss game with = 1.0, UCT with a search budget of N nodes will exhibit lookahead pathology for choices of the exploration parameter c q N 3 2 log N , even with access to a perfect heuristic.The key observation underpinning the result is that the densities of +1 nodes in both the optimal and sub-optimal subtrees rooted at a choice node (given by equations ( 1) and ( 2)) begin to approach the same value for large enough depths. This in turn suggests a way to lead UCT astray, namely to force UCT to over-explore so that it builds a search tree in a breadth-first manner. In such a scenario, the converging +1 node densities in the different subtrees, together with the averaging back-up mechanism in the algorithm, leaves UCT unable to tell apart the utilities of its different action choices. Notably, this happens even though we provide perfect node evaluations to UCT (i.e., the true minimax value of each node) -the error arises purely due to the structural properties of the underlying game tree. All that remains to be done is to characterize the conditions under which this behavior can be induced, which is presented in detail in Appendix C. Our experimental results suggest that the bound in Theorem 1 can likely be tightened, since in practice, we often encounter pathology at much lower values for c than expected. We further find that the pathology persists even when we relax the assumption that = 1.0, as described in the following sections. We now describe our experimental methodology for investigating pathology in UCT. Without loss of generality, we focus on games that are rooted at maximizing choice nodes (i.e., root node has a value of +1). We set the maximum game tree depth at 50, which ensures that relatively few terminal nodes are encountered within the search horizon (other depths are explored in the supplementary material, see Appendix F). We present results from a 4-factor experimental design: 2 choices of critical rate ( ) ⇥ 3 choices of branching factor (b) ⇥ 2 choices of heuristic models ⇥ 5 choices of the UCT exploration constant (c). A larger set of results, exploring a wider range of these parameter settings, is presented in Appendices F-H. For each chosen parameterization, we generate 500 synthetic games using our critical win-loss tree model. We run UCT with different computational budgets on each of these trees, as measured by the number of search iterations (i.e., the size of the UCT search tree). We define the decision accuracy (denoted as i ) to be the number of times that UCT chose the correct action at the root node, when run for i iterations, averaged across the 500 members of each tree family sharing the same parameter settings. Our primary performance metric is the pathology index P j defined as:P j = j 10where j 2 {10, 10 2 , 10 3 , 10 4 , 10 5 }. Values of P j < 1 indicate that additional search effort leads to worse outcomes (i.e., pathological behavior), while P j > 1 indicates that search is generally beneficial. We ran our experiments on an internal cluster of Intel Xeon Gold 5128 3.0GHz CPUs with 512G of RAM. We estimate that replicating the full set of results presented in this paper, with 96 jobs running in parallel, would take about three weeks of compute time on a similar system. The code for reproducing our experiments is hosted at https://github.com/redacted-for-double-blind-review.Figure 5 presents our main results. Our chief finding is that the choice of is the biggest determinant of pathological behavior in UCT. For games generated with = 1, we find that UCT exhibits lookahead pathology regardless of all other parameters -the exploration constant, the branching factor, or how the heuristic is constructed. Appendices F and H confirm the robustness of this result using additional data collected for other game tree depths and for heuristics constructed using data collected from Othello. For smaller values of , the effect is not as strong and other factors begin to play a role. For example, with = 0.9, pathological behavior is most apparent at higher branching factors and with more uniform exploration strategies (i.e., higher settings of c), consistent with Theorem 1. For = 0.5, pathology is almost completely absent, regardless of other parameters (see Appendix G).Poor performance from UCT in a synthetic domain, particularly when it is forced to over-explore, may seem unsurprising at first glance -so we will pause here to address these concerns, clearly elucidate the significance and novelty of these results, and to contextualize them better. Firstly, we note that lookahead pathology is distinct from poor planning performance. Practitioners routinely encounter domains where MCTS-style approaches simply fail to produce good results (for example, see (Ramanujan, Sabharwal, and Selman 2010a,b) ), regardless of the size of the computational budget, but our work demonstrates a subtly different phenomenon. Namely, there are situations where UCT will initially make good decisions (when it is allowed to build a tree of size, say, 100 nodes), but that its performance will degrade as it is afforded more "thinking" time (on trees of size 10k nodes). Moreover, we have done so in a two-player setting, where winning strategies for a player need to be robust to any counter-move by the opponent. In practice, this means that there are an exponential number of winning leaf nodes for both players. Thus, demonstrating degenerate behavior Figure 5 : Measuring pathological behavior in UCT on critical win-loss games of depth 50 with = 0.9 (left) and = 1 (right). The heuristic to guide UCT is constructed from histograms of Stockfish evaluations of positions sampled at depth 10, using both light and heavy playouts. Each colored line corresponds to an instantiation of UCT with a different exploration constant. Note that the x-axis is plotted on a log-scale. using constructions such as those of Coquelin and Munos, where the optimal leaf node is strategically hidden in the midst of an exponential number of suboptimal nodes, are not possible (Coquelin and Munos 2007) . In fact, our model is symmetric; we use the same critical rate for both players so that the game is equally (un)forgiving for both players, without stacking the deck against one player or the other. Seeing pathology arise under these conditions is thus more unexpected. We also note that more uniform exploration has been proposed in the past as an antidote to undesirable behavior in UCT (Coquelin and Munos 2007) . Our results indicate that over-exploration may create new problems of its own.Finally, for the sake of completeness, we also evaluate the performance of Minimax search with alpha-beta pruning on our critical win-loss games. These results are presented in Appendix J. We find that Minimax is similarly susceptible to lookahead pathology in our setting, particularly in games where 0.7. Games with high critical rates correspond to those with a high clustering factor f (Sadikov, Bratko, and Kononenko 2005) , and thus, low local similarity -in such games, there is a lower degree of correlation among the true utilities of nodes that are near each other in the game tree, 445 which has been identified as a key driver of pathology (Nau et al. 2010) . Our results are thus consistent with the findings of Nau et al. (Nau et al. 2010) . One point of departure from their findings, however, is that pathology arises in our experiments even though we use a highly granular heuristic. In 450 their work, Nau et al. create heuristic estimates for node utilities via an additive Gaussian noise model (Nau et al. 2010) , whereas ours are derived from binning Stockfish's evaluation function and treating that as a distribution. This suggests that the manner in which heuristics are modeled may 455 contribute to pathology, in addition to their resolution.This paper highlights a counter-intuitive failure mode for MCTS that deserves broader appreciation and recognition from researchers and practitioners. The fact that UCT has the potential to make worse decisions when given additional compute time means that the algorithm needs to be used with greater care. We recommend that users generate scaling plots such as those shown in Figure 5 to better understand whether UCT is well-behaved in their particular application 465 domain, before wider deployment. 
conclusions: 
 In this paper, we explored the question of whether MCTS algorithms like UCT could exhibit lookahead pathology -an issue hitherto overlooked in the literature. Due to the shortcomings of existing synthetic game tree models, we introduced our own novel generative model for extensive-form games. We used these critical win-loss games as a vehicle for exploring search pathology in UCT and found it to be particularly pronounced in high critical rate regimes. Important 475 avenues for follow-up work include generalizing the theoretical results presented in this paper to games where 6 = 1 and deriving tighter bounds for the exploration parameter c, as well as investigating whether such pathologies emerge in real-world domains. 
 
 Appendix:  


Decision: This paper studied so-called "lookahead pathology" of UCT algorithm
where deeper search harms the performance.

The paper proposed a synthetic game tree model that can generate arbitrary large instances
and is parameterized by $\gamma$ for flexible configuration.
The authors first empirically analyzed Chess to see if its search space can be seen as an instance of such a synthetic game tree
with a particular $\gamma$.
They then proposed a theorem that when the exploration coefficient $c$ is large, pathology is possible.
# 
Finally, by running
UCT guided by analytically available heuristics on the proposed synthetic model,
they confirmed the existence of pathology.

Although there were minor initial confusions,
the reviewers reached a consensus and generally found the paper valuable.
After the rebuttal the score changed +1/+1/+2, leaning toward acceptance.



Meta-reviewer comments:

Personally the characterization of $c$ feels odd from the multi-armed bandit standpoint;
Although it might be a common practice to tune $c$,
in UCB1's proof $c$ is the range of reward values,
which is 1 because rewards in the win/loss game is in [0,1],
i.e., theoretically the only correct value of $c$ in these games is $c=1$.

That being said, large $c$ does not invalidate the convergence characteristics of UCB1.
The asymptotic optimality (logarithmic regret) does not hold if the reward violates the range $[0,c]$,
but making $c$ larger does not cause such a violation.
As Reviewer oPUt pointed out, larger $c$ naturally causes issues even without Theorem 1,
but having the issue formalized is probably an important contribution.

For bounded-reward setting like games,
there are plenty of bandit algorithms other than UCB1,
although I do not know if they have been applied to adversarial games in a competitive setting.
For example, UCB-V selects actions according to $\mu + \sigma \sqrt{ (2\log T)/t } + (3c \log T)/t$
where $\sigma$ is a backed-up variance of Q while $\mu$ is a backed-up average of Q.
I wonder if the pathology still exists with those alternative bandits.

Reviews: review: strength_weakness: strength_weakness: - Although a theoretical analysis is given for games with critical rate = 1 is a good starting point, it would be interesting to see if the proposed game model is able to bring us good theoretical results on values != 1.
- The main aspect that should be analysed in the paper, which is lookahead pathology, is not mathematically defined.
- There is a lot of focus on the introduction of the Critical Win-Loss games and the critical rate parameter . The game model is an important contribution. However, I feel a lot is missing on explaining and analysing what the paper title actually attracts the reader for, which is lookahead pathology.
questions: questions: - How can one formally detect a pathology? Moreover, formally/mathematically define a pathology.

- There is an inconsistency in the explanation in section "Game Tree Model". You first say that choice nodes must have at least one child with the same minimax value. In the following paragraph, you emphasize that "exactly one" child of a choice node must share the minimax value. Please clarify or correct me if I am wrong. This is an important piece of explanation as it is about one of the main contributions.

Small refinements:
- Adjust figure one, it is currently stacked instead of side-by-side.
- Consider Figure 2 nodes in red to a more contrasting colour, or a lighter red, to make the visualisation easier (personal opinion). It would become easier to visualise if printed as well.
strength_weakness: strength_weakness: - It is unclear how Theorem 1 is correlated to the experiments where parameter c is set to small. In my understanding, in Theorem 1, a large value of c is necessary for a pathological behavior. For example, for N=50, c needs to be set to c>126. Such a large parameter leads UCT to merely selecting a move with the highest node visit, because the exploitation term for accumulating the rewards becomes much smaller than the value for the exploration term. Therefore, Theorem 1 just indicates a natural outcome of the pathology caused by ignoring the reward and selecting a move with the highest visit count. 

- I wonder why the authors do not show the distribution for the game of Go. Both chess and Othello are the games in which UCT has had a difficulty in outperforming alpha-beta (with a recent exception of AlphaZero in chess). In contrast, Go is a game where alpha-beta has never worked efficiently than UCT. Analysis with a Go-like distribution would be important in the community even if a pathology is not observed. 

This is a very minor point but parallel UCT in the following paper uses a synthetic game for performance measurement. Although they use a different type of a synthetic game and for a different purpose, I think it must be cited as related work, considering they use the synthetic game.

Kazuki Yoshizoe, Akihiro Kishimoto, Tomoyuki Kaneko, Haruhiro Yoshimoto, Yutaka Ishikawa: Scalable Distributed Monte-Carlo Tree Search. SOCS 2011: 180-187
questions: questions: Could you have any response to the first and second weaknesses I pointed out?
strength_weakness: strength_weakness: The submission devotes only a few lines to explaining why UCT exhibits pathology on the proposed trees.  I wished for more detail here, since this appears to be the core of the paper and there is plenty of room before hitting the page limit.  Furthermore, the hypothesis given is, as far as I can tell, not tested in any of the experiments.  The crux of the problem appears to be the fact that MCTS averages returns within each subtree of the root rather than, for example, taking mins and maxs to approximate the minimax value.  Would substituting min/max solve the problem?  On a related note, there is no discussion of how this flaw in adversarial applications relates to the guarantee of UCT to converge to the optimal action choice in an MDP.

The paper does not demonstrate that any of the previously-proposed tree models used to demonstrate pathology in minimax are insufficient to show pathology in UCT.  This would clarify how the new results relate to existing work, and how UCT compares to minimax.  (It would also be neat to see examples where minimax is not pathological but UCT is, but perhaps that's another paper.)

The relation of the new parameter gamma to the previously-proposed problem feature "local similarity" (Nau et al, 2010) is not explained either empirically or theoretically.  In essence, this paper is proposing an alternative set of conditions for pathology which will then need to be reconciled with the previous explanation of pathology for minimax.  This fragmentation is unfortunate and it is not clear that it is necessary.


little things:

1.1 (page 1 line 1) my understanding is that UCT was proposed for MDPs and its use for adversarial search is a bastardization.  is the use of the adjective "adversarial" really justified here?

in multiple places, the paper intends to use the authors of a specific reference as a subject.  a nice way of doing this is to say "Jones (2017) reported ...".  the current manuscript uses "Jones reported ... (Jones 2017)" which seems redundant and takes more space.  eg 1.57

1.71 my understanding is that Nau et al (2010) showed that pathology arises in real games such as mancala and chess, not just in synthetic trees.  perhaps this is important enough to mention here?

2.107 I assume \overbar{Q} is meant, instead of Q?

2.113 citation typo

2.115 P-games have not been introduced yet

2.128 would it be worth mentioning that lookahead pathology has also been found in real-time search (eg, the work of Bulitko)?

3.185 "determine the conditions" - that's a tall order!  perhaps you want to limit the reader's expectations by something qualified like "determine some sufficient conditions"?

3.225 I understand that this is a subjective point on which the authors should have the final say, but I wanted to mention that I am not entirely comfortable with the term "critical rate".  it only indirectly controls the rate at which critical moves are generated (and the connection is never mentioned, let alone explored, in the paper at all).  a more concrete term would be something like "value flip probability".

3.236 I feel that this definition is potentially ambiguous: is there one random draw to decide the value of all non-optimal children, or a separate one for each?

4.285-290 it is not clear why this implies reasonableness

4.315 pedantry: does an optimal heuristic really need to put all +1 positions above every -1 position?  perhaps there is a proper subset of -1 states against which a +1 position is actually compared (directly or indirectly)?

4.320 "likely too simplistic" - why?  please clarify/explain your argument here.

it would be nice if the columns and rows in the figure matrices were labeled (currently info is only in caption)

5. 334 personally I find 1 - \gamma (1 + \frac{1}{b}) more intuitive, but this is subjective

5.361 more detail here would be great.  is this a UCT-specific problem (would you expect UCT to fare worse than minimax)?  does this hypothesis imply that UCT will do worse on deeper states than shallower ones (when number of iterations is held constant)?

how will the appendices be handled in the final version?  reference to an arXiv version?

6.399 not clear what "uniform" means here

6.404 how can you tell that UCT is being forced to over-explore?  why would this hurt the algorithm more when more iterations are used?

6.454-456 this was not clear to me - why does this suggest that?
questions: questions: Would substituting min/max solve the problem?

Are there tests of your hypothesis that would be feasible to add to the paper?

What justifies using a new tree model rather than providing results on the old ones?  (I see this as a separate question from why is the new tree model better, which the paper already argues nicely.)