Taxman Scheduling: Bidding Rules for Interleaving Search Heuristics

Planners and solvers often keep several heuristics, which are rules of thumb that guess how far a state is from a goal. No single heuristic wins everywhere, so the practical question is how to share search effort among them while a single problem is being solved. Current answers fall at two extremes. Rigid round-robin gives every heuristic equal turns. A learned controller, a neural network trained offline, picks which heuristic expands the next node. We propose a middle option taken from game theory. Each heuristic holds a budget of "bidding tokens." At each step, the heuristics bid tokens for the right to choose the next node to expand. The payment rule then decides where the winner's tokens go: to the losers, or out of the system.

The literature on bidding games on graphs supplies one dial for this choice, the tax parameter $\tau$. Under that dial the scheduler moves smoothly from self-correcting fairness to winner-take-most exploitation. The same literature predicts that behavior changes sharply as soon as $\tau$ leaves 1. The result is a training-free scheduler with a single interpretable parameter. The parameter can also be picked per domain by an ordinary algorithm selector. We test whether such a scheduler reaches the coverage of a learned deep-RL controller on the same planning benchmarks.

Core Claim

In a Taxman bidding game, the winner of a bid pays a fraction $\tau$ of it to the opponent and loses the remaining $1-\tau$ to a "bank." Setting $\tau=1$ gives Richman bidding, where all payments go to the opponent. Setting $\tau=0$ gives Poorman bidding, where all payments are burned. Bidding mechanisms in graph games introduces this rule. For strongly connected mean-payoff games it proves that optimal play behaves like a random-turn game in which player 1 moves with probability

$$F(\tau, r) = \frac{r + \tau(1-r)}{1+\tau},$$

where $r$ is player 1's initial share of the total budget. At $\tau=1$ this equals $1/2$ whatever the budgets are. That matches the budget-insensitivity result in Infinite-duration Bidding Games. For any $\tau<1$ the value depends on $r$.

Read as a scheduling rule, the Richman end is self-correcting. A heuristic that keeps winning transfers its tokens to its rivals, so no heuristic starves. The Poorman end lets a heuristic that is making progress convert its budget into a long run of control. Our claim is that a multi-queue search scheduler built on this rule, with bids driven by a cheap local progress signal, can match or approach the learned controller of Learning Heuristic Selection with Dynamic Algorithm Configuration. It would do so without offline training. We also claim that coverage as a function of $\tau$ has structure the theory anticipates: a qualitative change between $\tau=1$ and $\tau$ slightly below 1.

The transfer from theory is a hypothesis, not a theorem. The random-turn results assume optimal, zero-sum, two-player play. Our heuristics bid by a fixed rule and are not adversaries. Part of the contribution is measuring how far the prediction survives that gap.

Research Program

The scheduler runs a greedy best-first search with one open list per heuristic, the same multi-queue setting Speck et al. use. Each heuristic $i$ starts with budget $B_i$. At each expansion step, every heuristic bids a fraction of its current budget, and that fraction grows with its recent progress. For example, a heuristic bids high if one of its last $k$ expansions reached a new lowest heuristic value on its own queue, and bids a small floor otherwise. The highest bidder expands the top node of its queue. It then pays $\tau$ times its bid, split evenly among the losers, and the rest is removed.

Under Poorman-leaning rules the total budget would drain away. We counter this with a slow uniform recharge, modeled on the charging vertices of Bidding Games with Charging. The recharge rate is a second, secondary parameter.

The analysis has three parts. First, we restrict the scheduler to two heuristics, $h_{\text{ff}}$ versus $h_{\text{cg}}$, so the setup matches the two-player theory. We then compare the empirical fraction of expansions each heuristic wins against $F(\tau,r)$ as we vary $r$ and $\tau$. Second, we run the full four-heuristic portfolio ($h_{\text{ff}}, h_{\text{cg}}, h_{\text{cea}}, h_{\text{add}}$) and sweep $\tau$. Third, we treat $\tau$ as the thing to be selected. A per-domain or per-instance selector, in the style of AutoFolio: An Automatically Configured Algorithm Selector, picks $\tau$ from cheap problem features. This is where the algorithm-selection literature enters. We do not select a solver. We select a mechanism parameter, and the choice space is one-dimensional with smooth, interpretable behavior.

The related work plays distinct roles. Learning Static Parallel Portfolios of Algorithms motivates the problem. It fits fixed CPU shares per solver, 9% for zChaff and over 85% for eqsatz, which shows that good shares are very uneven. Those shares cannot change within an instance, and our budgets can. Speck et al. supply the benchmark and the strongest competitor. They also expose a cost we avoid: a trained agent that talks to the planner over inter-process communication. Online Algorithm Selection constrains the design. It shows that unbudgeted exploration across solvers loses to greedy selection because one bad choice costs a full timeout. The file does not show whether that finding carries over to expansion-level choices, where a single mistake is cheap, so we test it directly rather than assume it. Understanding Iterative Combinatorial Auction Designs via Multi-Agent Reinforcement Learning studies how sensitive auction rules are when played by learned bidders in economic auctions. We share its empirical question about sensitivity to the rules, but our "market" is internal to a solver.

Baselines

The naive reference points are the best single heuristic and round-robin alternation, both from Speck et al. Round-robin is also exactly what our scheduler should reduce to under Richman rules with constant bids. On the 600 test instances across six domains of the International Planning Competition (IPC), Speck et al. report total coverage of 425.0 for $h_{\text{ff}}$ alone and 488.2 for alternation. Coverage is the number of instances solved within the time limit.

The strongest existing method is Speck et al.'s Double DQN controller, a deep reinforcement learning agent that picks the heuristic at each expansion. It reports total coverage of 505.1, and 92.9 versus 83.7 for alternation on Blocksworld. It is the strongest competitor because it adapts within a single search, which is exactly what our scheduler does. We will use their domains, their instance generation, and their 100/100 train/test split per domain. We will use the same planner and match time and memory limits. We will report both the published numbers and our own rerun, so that differences in hardware do not decide the comparison.

Tuning budgets will be matched. The bidding scheduler's parameters ($\tau$, the recharge rate, and the bid fraction) will be tuned only on the training instances. The file gives no report of the DQN's training compute, so we will log our tuning compute in CPU-hours alongside theirs. The scheduler beats the DQN if its total coverage with one global $\tau$ is at least 505.1. It is competitive if it falls within the run-to-run variation of our DQN rerun while needing no learned model.

Two ablations isolate the key ingredient. The first, "progress-greedy," keeps the same progress signal but removes budgets and payments: the heuristic with the most recent progress always expands. The second keeps the budgets but uses random bids. If progress-greedy matches the bidding scheduler, the payment rule is doing nothing.

Why not just…?

Why not just use the DQN controller? It already achieves 505.1 coverage in Learning Heuristic Selection with Dynamic Algorithm Configuration. However, it needs offline training for each setting and a separate agent process with communication overhead. Its policy is opaque, and no parameter tells you how exploitative it is. If our scheduler falls well short of 505.1, the DQN simply wins. The coverage comparison and the logged training cost settle this directly.

Why not just a non-stationary bandit over heuristics, such as sliding-window UCB rewarded by progress? This is the most serious threat, because at the expansion level a bandit and a bidding scheduler both reallocate effort toward the heuristic that is currently productive. Degroote's negative result about exploration was measured at the level of whole instances, where one mistake costs a timeout. It is not evidence against cheap exploration within a single search. We therefore run a tuned sliding-window UCB under the same progress reward and the same tuning budget. If it matches the bidding scheduler, we will conclude that the budget structure adds nothing. The remaining claim would then shrink to whether $\tau$ is a better-behaved dial than UCB's exploration constant, which we measure as how steeply coverage changes with each parameter.

Why not just always follow whichever heuristic made progress most recently? This is the progress-greedy ablation. A known failure is a heuristic that makes steady but misleading progress, for instance on a plateau that leads to a dead end. Under greedy rules it can monopolize the search. Under Richman-style payments, its rivals accumulate tokens and eventually outbid it. The per-domain coverage gap between progress-greedy and the $\tau\approx1$ scheduler measures whether this protection matters. Domains like Sokoban, where Speck et al. found $h_{\text{ff}}$ chosen 98% of the time, are where greedy should do well. Mixed domains are where the protection should show.

Proposed Experiments

The first experiment tests the theory in the two-heuristic setting. We vary the initial budget share $r$ over a grid at $\tau\in\{1, 0.99, 0.9, 0.5, 0\}$. The prediction is that at $\tau=1$ the long-run share of expansions won barely moves with $r$, and at $\tau<1$ it tracks $r$ roughly as $F(\tau,r)$ does. A clear change between $\tau=1$ and $\tau=0.99$ would support the transfer. A smooth curve would show that the fixed bidding rules break the random-turn correspondence.

The second experiment is the main comparison. We sweep $\tau$ for the four-heuristic portfolio on all six IPC domains, reporting coverage and expansions, and compare against $h_{\text{ff}}$, alternation, the DQN, sliding-window UCB, and both ablations. The third experiment adds $\tau$ selection. We compare one global $\tau$, a best $\tau$ per domain chosen by oracle (an upper bound), and a $\tau$ predicted from features by a random-forest selector trained on training instances. The random forest follows the regression-forest choice that ASlib: A Benchmark Library for Algorithm Selection found strongest on 13 of 17 scenarios.

The decisive checks follow from these experiments. The project succeeds if a global-$\tau$ scheduler beats the 488.2 alternation baseline and progress-greedy, and at least one of the two lines of analysis holds: the $\tau$ sensitivity predicted in the first experiment, or the domain dependence of the best $\tau$ that the third experiment exploits. It is refuted if tuned UCB or progress-greedy matches it, or if performance is flat in $\tau$.