Preference-Based Monte Carlo Tree Search

Tobias Joppen, Christian Wirth, Johannes FürnkranzarXiv 2018 · DOI · arXiv

TL;DR

This paper introduces Preference-Based Monte Carlo Tree Search (PB-MCTS), a novel algorithm that replaces traditional numeric rewards with qualitative, pairwise comparisons. By leveraging "dueling bandits" at each node, the authors demonstrate that MCTS can achieve state-of-the-art performance even when exact reward values are unavailable or biased, while also proving more robust to hyperparameter tuning than standard variants.

What Problem Does This Paper Address?

Monte Carlo Tree Search (MCTS) is a cornerstone of modern AI, famously powering systems like AlphaGo. However, it has a fundamental dependency: it requires a precise numeric reward signal to calculate expectations and guide its search.

In many real-world scenarios, defining these numbers is surprisingly difficult. For instance, in complex navigation or human-in-the-loop tasks, we might know that "State A is better than State B," but assigning them values like 0.72 and 0.45 feels arbitrary and prone to bias. These "erroneous heuristics" can lead standard MCTS to get stuck in local optima. The authors argue that since many underlying problem structures are ordinal (based on rank) rather than numerical, we should design algorithms that reflect this reality.

Methods

The core innovation is the transition from Markov Decision Processes (MDPs) to Ordinal Reward MDPs (OMDPs). To solve these, the authors adapt the principles of preference-based (or dueling) bandits to the tree search structure.

Fig. 1: Research in Monte Carlo methods

Key technical components include:

  • Relative Upper Confidence Bound (RUCB): Instead of the standard UCT formula, each node uses a modified RUCB to select a pair of actions ($a_1, a_2$). The first action is a potential "Condorcet winner" (an action that beats all others), and the second is its toughest competitor.
  • Binary Tree Traversal: Because two actions are selected at each node, the algorithm traverses a binary subtree, leading to multiple rollouts per iteration.
  • Pairwise Feedback: Feedback is derived solely from comparing the outcomes of these rollouts (e.g., "Rollout 1 reached a state closer to the goal than Rollout 2").
  • Best Preference Policy (BPP): To prevent an exponential explosion of data during backpropagation, the algorithm uses a "return policy" that propagates only the preferred trajectory back up the tree, ensuring numerical stability.
Fig. 2: Comparisons of MCTS (top) and preference-based MCTS (bottom)

Datasets

The authors evaluate their approach using the 8-puzzle domain.

  • Why 8-puzzle? It is a deterministic puzzle with a massive state space where simple but imperfect heuristics—like Manhattan Distance (MD) and Manhattan Distance with Linear Conflicts (MDC)—already exist.
  • Evaluation Setup: They compared PB-MCTS against a baseline called Heuristic MCTS (H-MCTS). While H-MCTS saw the raw numeric values of the heuristics, PB-MCTS only saw the preferences derived from those same values.

Key Insights and Ideas

  • Ordinality as a Feature, Not a Bug: The paper suggests that stripping away absolute numeric differences and focusing on rank doesn't necessarily lose information; rather, it removes the "biases caused through absolute annotation."
  • Hyperparameter Robustness: One of the most striking findings is that PB-MCTS is significantly less sensitive to hyperparameter settings (like the exploration-exploitation trade-off) than standard MCTS.
  • Condorcet Winners in Trees: Successfully adapting dueling bandits to a tree structure requires careful management of the "return policy." Propagating both rollouts would cause an exponential explosion in comparisons, so the choice to propagate only the "winner" is crucial for efficiency.

Key Results

  • Comparable Performance: PB-MCTS reached a win rate comparable to the numeric H-MCTS baseline. In fact, with a high number of samples (above $10^4$), PB-MCTS slightly outperformed the baseline.
  • Graceful Degradation: When analyzing the distribution of all hyperparameter configurations, PB-MCTS showed a much more robust curve. While H-MCTS win rates dropped off a cliff if the parameters weren't in the top 20%, PB-MCTS maintained high performance across a wider range of settings.
  • Convergence: While PB-MCTS converges slightly slower initially (likely due to the overhead of binary trajectories), it eventually reaches a similar or superior performance level to tuned numeric versions.

Limitations and Future Work

  • Exponential Trajectory Growth: The primary drawback is the exponential growth in the number of explored trajectories per iteration due to the binary selection at each node. Although the authors mitigated this in backpropagation, the selection phase remains computationally heavier than standard MCTS.
  • Pruning: The authors suggest that future work could involve "pruning" the binary subtree—similar to alpha-beta pruning in classical game-tree search—to remove this exponential growth while maintaining the integrity of the preference feedback.
  • Real-World Human Feedback: While this paper used heuristics to generate preferences, the ultimate goal is to apply this to domains where humans provide the qualitative feedback directly.

Summary updated

Abstract

Monte Carlo tree search (MCTS) is a popular choice for solving sequential anytime problems. However, it depends on a numeric feedback signal, which can be difficult to define. Real-time MCTS is a variant which may only rarely encounter states with an explicit, extrinsic reward. To deal with such cases, the experimenter has to supply an additional numeric feedback signal in the form of a heuristic, which intrinsically guides the agent. Recent work has shown evidence that in different areas the underlying structure is ordinal and not numerical. Hence erroneous and biased heuristics are inevitable, especially in such domains. In this paper, we propose a MCTS variant which only depends on qualitative feedback, and therefore opens up new applications for MCTS. We also find indications that translating absolute into ordinal feedback may be beneficial. Using a puzzle domain, we show that our preference-based MCTS variant, wich only receives qualitative feedback, is able to reach a performance level comparable to a regular MCTS baseline, which obtains quantitative feedback.
BibTeX
@misc{joppen2018preference,
  author = {Tobias Joppen and Christian Wirth and Johannes Fürnkranz},
  title = {{Preference-Based Monte Carlo Tree Search}},
  year = {2018},
  eprint = {1807.06286},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1807.06286},
}
Figure