Source-linked AI summary
Bandit Algorithms for Tree Search
Pierre-Arnuad Coquelin, Remi Munos
TL;DR
Tree search with UCT can suffer very poor worst-case regret because its confidence bound may not remain valid under the node-selection process. The paper analyzes alternative tree-search algorithms, including smoothness-aware BAST and incremental expansion, and reports that BAST outperformed UCT and Flat UCB in the problems considered for an appropriate smoothness coefficient.
Problem
UCT’s confidence bound may not be a true upper confidence bound when tree-search rewards do not satisfy the i.i.d. assumptions of the concentration inequality under non-stationary node selection.
Source: §2 · p. 3Method
Results
BAST performed better than both UCT and Flat UCB in all problems considered for an appropriate smoothness coefficient δ.
Source: §7 · p. 8Takeaways & Limitations
BAST can use reward smoothness to cut suboptimal branches with high confidence, while incremental expansion indefinitely develops only optimal branches with high probability.
Source: §1 · p. 2The described UCB methods do not explicitly delete branches, despite the paper’s use of “cuts” for pruning suboptimal branches.
Source: §7 · p. 8
Abstract
from arXiv · showhide
Bandit based methods for tree search have recently gained popularity when applied to huge trees, e.g. in the game of go [6]. Their efficient exploration of the tree enables to re- turn rapidly a good value, and improve preci- sion if more time is provided. The UCT algo- rithm [8], a tree search method based on Up- per Confidence Bounds (UCB) [2], is believed to adapt locally to the effective smoothness of the tree. However, we show that UCT is "over-optimistic" in some sense, leading to a worst-case regret that may be very poor. We propose alternative bandit algorithms for tree search. First, a modification of UCT us- ing a confidence sequence that scales expo- nentially in the horizon depth is analyzed. We then consider Flat-UCB performed on the leaves and provide a finite regret bound with high probability. Then, we introduce and analyze a Bandit Algorithm for Smooth Trees (BAST) which takes into account ac- tual smoothness of the rewards for perform- ing efficient "cuts" of sub-optimal branches with high confidence. Finally, we present an incremental tree expansion which applies when the full tree is too big (possibly in- finite) to be entirely represented and show that with high probability, only the optimal branches are indefinitely developed. We illus- trate these methods on a global optimization problem of a continuous function, given noisy values.
1 Introduction
The introduction frames tree search as balancing exploration across branches to find an optimal leaf, then presents algorithms aimed at safer and more efficient search. Its main contribution is BAST, with additional analyses of UCT, Flat UCB, and incremental tree expansion.
1 Introduction
- The search objective is to minimize regret by exploring branches so an optimal leaf can be selected quickly.The paper defines regret as the loss from choosing suboptimal rather than optimal leaves.Source: §1 · p. 2
- UCT can have worst-case regret hyperexponential in tree depth, while increasing its exploration sequence improves but does not eliminate the poor worst-case behavior.The modified bound can still yield regret as bad as Ω(exp(exp(D))).Source: §1 · p. 2
- A further modified UCT scales its confidence interval exponentially with horizon depth to account for slower bias reduction at nodes nearer the root.The bias at a node takes longer to decrease as the remaining horizon grows.Source: §1 · p. 2
- Flat UCB applies UCB directly to the leaves rather than maintaining bounds through the tree.The introduction says this algorithm is analyzed next.Source: §1 · p. 2
- BAST uses reward smoothness to cut suboptimal branches with high confidence without exploring every leaf, and is presented as the paper’s main contribution.The paper reports regret analysis and improvement over both UCT and Flat UCB.Source: §1 · p. 2
- Incremental BAST expansion addresses trees too large to represent in memory and, with high probability, indefinitely develops only optimal branches.The resulting tree is asymmetric.Source: §1 · p. 2
2 Regret lower bound for UCT
The section argues that UCT’s confidence bounds can be unreliable under tree search’s non-stationary node selection, producing extremely long delays before the optimal leaf is found. Its lower-bound examples show that even a square-root confidence sequence can yield double-exponential regret in depth, while the usual logarithmic sequence can be hyperexponential.
2 Regret lower bound for UCT
- UCT’s bound may fail to be a true upper confidence bound because rewards at a node do not meet the concentration inequality’s i.i.d. assumptions under non-stationary leaf selection.The paper attributes the poor behavior to over-optimism during a potentially long transient period.Source: §2 · pp. 3–4
- Although UCT eventually follows only the optimal branch after a transient period, that period can be very long.The cited argument gives expected regret of order O(N0 + log(n)).Source: §2 · p. 3
- In the constructed tree, action 2 is tried first and initially appears best, delaying the first reward of 1 from the always-action-1 optimal branch for Ω(exp(…exp(1)…)) rounds.The nested exponential is composed D−1 times.Source: §2 · p. 3
- A square-root confidence sequence can still yield double-exponential regret in depth; for D = 20, the stated lower bound is n ≥10156837.The transient phase is Ω(exp(exp(D))).Source: §2 · p. 4
- UCT’s usual logarithmic confidence sequence can yield regret with D−1 composed exponential functions, a hyperexponential dependence on tree depth.The bound is Ω(exp(exp(· · · exp(1) · · · ))) + O(log(n)).Source: §2 · p. 4
3 Modified UCT
Modified UCT scales its confidence sequence with the remaining depth horizon, yielding a high-probability regret bound that grows exponentially with tree depth. Its confidence bounds are safe but do not adapt to actual tree smoothness.
3 Modified UCT
- The confidence sequence explores nodes nearer the root more, accounting for the longer horizon needed to reduce bias at greater remaining depth.The bound depends on the remaining horizon D−d for a node at depth d.Source: §3 · p. 4
- With probability at least 1−β, modified UCT bounds pseudo-regret by a quantity exponential in depth D and proportional to √n.The confidence sequence is designed to keep node values below their upper bounds with high probability.Source: §3 · p. 4
- At the root, the confidence interval is O(exp(D)/√n), so two branches can be sampled almost uniformly for O(exp(D)) rounds even when their rewards are all zeros versus all ones.In that example, the method does not account for the tree's smoothness, and regret may remain O(exp(D)√n).Source: §3 · p. 4
- Modified UCT is less optimistic than regular UCT and safer in the worst case, but its confidence bounds do not adapt to effective tree smoothness.The bounds are chosen to remain true upper confidence bounds on node values with high probability.Source: §3 · p. 4
4 Flat UCB
Flat UCB applies UCB to leaves and propagates the largest child bound to each non-leaf node. It has a high-probability regret bound independent of the number of rounds, but that bound still depends exponentially on tree depth.
4 Flat UCB
- Flat UCB applies a regular UCB algorithm to leaves and assigns each non-leaf the maximum upper confidence bound among its children.This tree-structured implementation combines leaf-level UCB with upward propagation of bounds.Source: §4 · p. 4
- With probability at least 1−β, Flat UCB's pseudo-regret is bounded by a constant independent of n.The regret still depends exponentially on depth because the tree has 2^D leaves.Source: §4 · pp. 4–5
- A suboptimal leaf's visit count is bounded using its reward gap and confidence intervals, with a rough threshold of 3w log(w2^D+1 β^-1).Here w = 2/∆_i^2, and the threshold bounds how many times that leaf is chosen.Source: §4 · p. 5
- Despite its high-probability safety, Flat UCB's regret bound remains exponential in depth because it accounts for all 2^D leaves.The following method is introduced to use reward smoothness to cut suboptimal branches without exploring all their leaves.Source: §4 · p. 5
5 Bandit Algorithm for Smooth Trees
BAST uses reward smoothness within branches to tighten confidence bounds and cut branches that are confidently suboptimal. The paper gives high-probability visitation and regret bounds and illustrates the approach on noisy continuous-function optimization.
High-probability bounds
- With probability 1−β, every suboptimal node is visited at most its recursively defined bound N_i, under the stated smoothness assumption along an optimal path.The theorem defines N_i recursively for suboptimal branches; its proof uses the high-probability confidence event and the optimal-path smoothness assumption.Source: §5 · p. 5
Comparison with Flat UCB
- For nodes with Δ_i>δ^d, the high-probability visit bound is O(1/(Δ_i−δ^d)^2), independent of the number of leaves below the node.The paper also anticipates improved bounds when, at some deeper level, all nodes in the branch satisfy the corresponding gap condition.Source: §5 · p. 6
- Under Aη and exponential smoothness δ_d=δγ^d, the regret bound sums over η-optimal leaves, and its second term depends weakly and linearly on depth D.The paper expects the reduction versus Flat UCB to be important when the number of η-optimal leaves is small relative to the total 2^D leaves.Source: §5 · p. 6
- The regret bound has no explicit exponential dependence on D, but its 1/Δ term can scale as O(1/γ^D) under the smoothness assumption.The paper notes that locally quadratic functions permit γ=1/4, compared with γ=1/2 for Lipschitz smoothness, and says this can cut suboptimal branches more efficiently.Source: §5 · pp. 6–7
Algorithm definition
- BAST interpolates between regular UCT at δ=0 and Flat UCB at δ=∞, allowing its bounds to use available information about tree smoothness.At δ=0 the bounds reduce to the leaf-level confidence bounds; at δ=∞ they take the maximum over children.Source: §5 · p. 6
Numerical experiments
- With δ=5, BAST concentrates visits on good leaves while the plotted function and rescaled visitation proportions show the search allocation.Figure 2 compares the function with visitation proportions for n=10^4 and n=10^6, at D=10 and a=0.1.Source: §5 · p. 6, Figure 2 · p. 7
- For a=0.01, BAST at δ=50 outperforms UCT and Flat UCB, with best performance at 0<δ<50; Flat UCB's regret is 0.23.Here δ=50 matches the function's Lipschitz smoothness; increasing δ first reduces regret, then increases it as cuts become less frequent.Source: Figure 3 · p. 7, §5 · p. 7
6 Growing trees
The incremental method grows a tree too large to represent in full, using O(n) memory after n rounds. Under the A* assumption, suboptimal branches are visited only finitely often, so only optimal branches are expanded indefinitely.
6 Growing trees
- The method starts with the root and expands one leaf at a time, adding its children and receiving one reward for each; its memory is O(n) after n rounds.This incremental representation is proposed for trees too large, possibly infinite, to represent in full.Source: §6 · p. 7
- Under A*, node values are maxima over child values, and expected rewards from an optimal leaf at depth d are within δd of the optimal value.The assumption bounds the conditional expected reward, not each reward’s specific value.Source: §6 · p. 7
- With probability at least 1−β, every suboptimal branch is visited finitely often, and the algorithm indefinitely expands only optimal branches.The theorem’s claim is for the incremental method under A* and its stated confidence procedure.Source: §6 · pp. 7–8
- For the function-optimization problem, the illustrated algorithm develops its tree asymmetrically, expanding the optimal branch in depth while leaving mainly unexplored sub-optimal branches.Source: §6 · p. 8
7 Conclusion
BAST uses possible tree smoothness to cut suboptimal branches with high confidence. In the considered problems, it outperformed UCT and Flat UCB for an appropriate smoothness coefficient, though experiments were needed to select that coefficient.
7 Conclusion
- In all considered problems, BAST outperformed UCT and Flat UCB for an appropriate smoothness coefficient δ, whose best value required experimental work.More smoothness information about the optimal branch may allow refinement of the smoothness sequence and improved performance.Source: §7 · p. 8
- “Cuts” do not explicitly delete branches; they describe high-confidence handling of suboptimal branches.The UCB-based methods retain branches rather than removing them from the tree.Source: §7 · p. 8
- Variance estimates [1] could tighten confidence intervals and improve performance, but true upper confidence bounds remain important to avoid regular UCT’s bad cases.Regular UCT’s bound may fail to be a true upper confidence bound because node rewards do not meet its independence assumptions.Source: §7 · p. 8
- The authors state that extending the method to two-player zero-sum minimax search is possible and would yield similar results.Source: §7 · p. 8