Convergence Criterion (MCTS)

The search halts after a predetermined number of MCTS iterations (Selection, Expansion, Simulation, Backpropagation). This is the simplest and most common criterion.

• Guarantees deterministic runtime, crucial for real-time systems like game AI.
• Does not adapt to problem complexity; the same budget is used for easy and hard decisions.
• Example: A chess engine might be configured to run exactly 10,000 simulations per move.

The search runs for a predefined duration (e.g., 100 milliseconds). This is practical for systems interacting in real-time environments.

• Aligns with wall-clock constraints in competitive or interactive settings.
• Performance varies with hardware and implementation efficiency.
• Used in AlphaZero and similar agents during gameplay, where a move must be chosen within a fixed time per turn.

The search stops when the estimated value of the best action stabilizes, indicating confidence. This is measured by tracking changes in the root node's action values over iterations.

• Halts early for clear-cut decisions, saving computation.
• Requires defining a convergence metric (e.g., value change < 0.01 over N iterations).
• More common in optimization and planning domains than in fast-paced games.

Convergence is declared when one child of the root node accumulates a dominant share of the total visits, signaling a strong consensus. A common threshold is when the most-visited child's count exceeds a percentage (e.g., 95%) of the root's visits.

• Directly reflects the tree policy's confidence (e.g., UCT).
• The principal variation becomes clearly defined.
• Prone to early convergence in deceptive states if exploration is insufficient.

Search continues until the uncertainty (or variance) in the value estimates for the top actions falls below a threshold. This leverages the statistical nature of MCTS.

• Can use confidence intervals derived from Central Limit Theorem assumptions on rollout outcomes.
• Provides a formal, probabilistic guarantee on decision quality.
• Computationally more expensive to evaluate per iteration.

The search stops when a computational resource limit is reached, such as memory capacity for the tree or a maximum node count. This prevents the process from exhausting system resources.

• Essential for long-running or unbounded problems where other criteria may not fire.
• Often used in conjunction with other criteria as a safety fallback.
• Triggers mechanisms like tree pruning to manage growth.

UCT is the canonical selection policy that drives the tree traversal in MCTS. It formalizes the exploration-exploitation tradeoff by treating each node as a multi-armed bandit problem. The formula balances choosing nodes with:

• High average reward (exploitation).
• High uncertainty due to low visit counts (exploration). This policy is fundamental to the algorithm's asymptotic convergence to the optimal action, as it ensures all promising branches are eventually explored given sufficient time.

The visit count is a core statistic stored in every MCTS node, incrementing each time the node is traversed during the selection phase. It serves multiple critical functions:

• Drives exploration in policies like UCT, where less-visited nodes are prioritized.
• Indicates convergence confidence; a high visit count on a child node suggests it is the robust best action.
• Is used directly in some convergence criteria, such as halting when the root's most-visited child exceeds a certain threshold of total visits. It is updated during the backpropagation phase.

Progressive widening is a technique for managing continuous or vast discrete action spaces where enumerating all child nodes at once is infeasible. Instead, the number of actions (child nodes) considered for a parent node grows gradually as the parent's visit count increases.

• This creates a dynamic branching factor.
• It is a form of action-space exploration that directly impacts convergence, as the algorithm must first discover high-value actions before it can refine their estimates.
• Convergence criteria must account for this staged expansion of the search tree.

Virtual loss is a parallelization technique for tree parallelization MCTS. When a thread selects a node during the selection phase, it temporarily adds a 'virtual' loss to that node's statistics.

• This artificially lowers the node's estimated value via the UCT formula.
• It discourages other threads from simultaneously exploring the same path, reducing wasteful search overhead.
• The loss is removed after the thread completes its simulation and backpropagation. This mechanism ensures more efficient parallel convergence but requires careful tuning to avoid overly pessimistic exploration.

RAVE is an enhancement that accelerates value estimation in MCTS, particularly effective in games like Go. It shares simulation statistics across all nodes in the tree where a given action was taken, not just along the specific path.

• Provides faster, coarser value estimates, especially in the early phases of search.
• The final node value is a weighted combination of the standard Monte Carlo average and the RAVE estimate.
• This can lead to faster convergence on a best action by reducing the variance of early estimates, though the bias introduced must decay appropriately for asymptotic correctness.

The principal variation (PV) is the sequence of moves considered optimal for both players from the current root state. In MCTS, it is typically extracted after search concludes by:

• Starting at the root.
• Selecting the child with the highest visit count.
• Repeating this process at the selected child, moving down the tree. The stability of the PV is a practical, real-time convergence indicator. If the first move of the PV remains unchanged over many iterations, it suggests the search has stabilized on a candidate action.