Abstract
In real-time search, the standard heuristic is to explore the most promising path. This paper demonstrates that when search resources are extremely limited, this greedy approach can be mathematically suboptimal. By modeling search as a scouting mission with a fixed budget, we prove that it is sometimes better to gather information on a "second-best" path to minimize the final expected cost.
Introduction
Most heuristic search research focuses on the speed of finding an optimal solution. However, real-time AI systems, such as chess engines or speech recognizers, often operate under strict time constraints where they must provide the best possible answer within a fixed resource budget. This paper addresses the "inverse question": given exactly $n$ search resources, how can we allocate them to find the best possible solution?
In this framework, search is viewed as a "scouting" mission. A scout has a limited budget of arc expansions to reveal the true costs of a tree. Subsequently, a "general" must select a path based on this incomplete data. The objective is to determine the optimal allocation of these few scouting steps to minimize the final expected path cost.
Methods
The study employs a formal probabilistic model based on a complete binary tree of depth $N$. Each edge in the tree is assigned a cost of 1 with probability $p$ and a cost of 0 with probability $1-p$, independently.
The scout can "expand" $n$ arcs to observe their true values. After $n$ expansions, the general selects the leaf with the lowest "zero-value"—the sum of known arc costs plus the expected cost of the remaining unknown segments. The paper compares a Greedy Policy, which always expands the arc leading to the leaf with the lowest current expected cost, against an Optimal Policy. To establish the "Bad-News Theorem," a "MIMIC" proof technique is used to show that in certain states, scouting a rival path yields a lower average final cost than refining the current leader. Anecdotal support for these conjectures was also gathered through mechanical computation of optimal decisions for small values of $n$ ($n \le 10$).
Key Insights and Results
The core finding is that the "best" path to choose is not always the "best" path to research. Information gained from scouting a slightly worse path can be more valuable for the final decision than refining the estimate of the current leader.
The Role of Probability $p$
The optimality of the greedy strategy depends heavily on the probability $p$:
- $p \le 0.5$: The greedy strategy is always optimal.
- $0.5 < p \le 0.618$: Greedy is optimal if at least 2 resources ($n \ge 2$) remain.
- $0.618 < p \le 0.682$: Greedy is optimal if at least 3 resources ($n \ge 3$) remain.
The "Bad-News" and "Good-News" Theorems
The "Bad-News" theorem states that if $p$ is sufficiently high, there are always scenarios where the greedy choice is a mistake, regardless of the total resources $n$. Conversely, the "Good-News" corollary suggests that for a wide range of $p$ values (up to ~0.682), the greedy policy remains optimal as long as a minimum number of steps are available. Greedy search only becomes "dangerous" when resources are nearly exhausted.
The author conjectures that for any fixed $p$, there exists a threshold $M = \log_p(1-p)$ such that if more than $M$ resources remain, the greedy policy is optimal.
Conclusion
While the model is simplified to binary trees and binary costs, it captures a fundamental trade-off in resource-constrained search. The results suggest that for most practical values of $p$, greedy search is a robust approximation. However, as resources dwindle or the probability of high-cost edges increases, non-greedy "information-gathering" strategies become superior. Future work could extend these findings to more complex branching factors and continuous cost distributions.
Summary updated