[RFC] A Scheduler for Multi-Take Tests to Improve Efficiency

[drauh]

Disclaimer: As a new contributor, I might have overlooked important context or constraints of the Fishtest ecosystem.

This RFC proposes the implementation of a test scheduler on Fishtest to manage groups of related tests (e.g., multiple "takes" of a single patch idea). This scheduler would automatically allocate testing resources to the most promising candidates and terminate the entire group of tests early based on statistical dominance. Simulations show this can reduce game consumption by over 60% and provide a definitive result for the best take up to 3-4 times faster, all while maintaining high statistical accuracy (though further work might be needed to ensure this across all scenarios).

This proposal provides a statistically sound framework to address the problem of manual early stopping discussed in #2125, where stopping tests based on arbitrary LLR values invalidates the SPRT's error guarantees.

Motivation

Developers often submit multiple variations of a single idea for testing. Each test runs independently until it meets its SPRT criteria, or developers manually stop some based on the current top performers. This is inefficient for several reasons:

1. Wasted Resources: Games are spent on takes that are clearly inferior to others in the same group.
2. Slow Feedback: A developer must wait for all tests to complete to determine the best version, even if a winner is statistically obvious much earlier.
3. Risk of Misses: As discussed in Early stopping #2125, stopping runs with arbitrary criteria can lead to incorrect rejections of valuable patches. A formal scheduler mitigates this risk.

Proposal

We could add a feature where a user can group several new tests into a single "multi-take" run. This run would be managed by a scheduler with user-selectable options for allocation and stopping.

1. Allocation Policies:
The scheduler intelligently allocates game tasks to active candidates. Following the literature on the Multi-armed bandit problem, I explored two policies that are smarter than the current round-robin approach:

• UCB (Upper Confidence Bound): Prioritizes the candidate with the highest upper bound of its ELO confidence interval.
• TS (Thompson Sampling): Samples an ELO value from each candidate's estimated distribution and plays the one with the highest sample.

2. Stopping Conditions:
The scheduler decides when the "meta-test" is complete. I considered two options:

• UCB-Dominance: The run terminates when a single winning candidate (LLR > 2.94) has an Elo estimate that is higher than the UCB of all other active candidates. This is a heuristic that balances speed and safety. A more rigorous but potentially too restrictive rule would be to stop when the highest LCB of winning candidates is above the UCB of all remaining active ones. The UCB-Dominance approach can provide several strong winning candidates that can then be confidently promoted to LTC testing.
• Stop-at-First: This is an even more aggressive option than UCB-Dominance. The run terminates as soon as the first candidate passes (LLR > 2.94). This could be an option for developers who want to test dozens of candidates at once, aiming for a clear and high ELO improvement.

Supporting Data

Extensive Monte Carlo simulations (10,000 runs) validate this proposal. The data shows a clear win for the proposed strategies over the current baseline of running all tests to completion. The table below includes the average number of games until a winner first passes its SPRT test, highlighting the faster feedback loop.

Strategy (Stopping, Policy)	Avg. Total Games (Efficiency)	Avg. Games to First Winner (Feedback Speed)	Winner: corradj4 (%) (Accuracy)	Avg. True Elo of Winner (Quality)	Throughput (Positives/M Games)
complete, sequential	1,221,225	442,136	71.7%	1.28	6.79
first, sequential	441,412 (-64%)	441,412	72.4%	1.28	2.27
ucb-dominance, ucb	385,648 (-68%)	209,283	68.3%	1.24	7.47
ucb-dominance, thompson	488,182 (-60%)	244,227	71.1%	1.27	7.15
first, ucb	210,280 (-83%)	210,200	66.0%	1.22	4.76
first, thompson	242,345 (-80%)	242,275	68.7%	1.25	4.13

Key takeaways from the data:

• Theucb-dominance, thompson strategy offer the best balance, saving 60% of games while being on parity with complete, sequential while completing many more tests than first, sequential.
• For fastest results, the first stopping strategy with either thompson or ucb provides best results 2x faster than baseline first, sequential.

The full simulation repository and results are available for review:

• Simulation Code: https://github.com/drauh/multitakes_simul_rs
• Full Experiment Results: 10,000 Run Artifacts

Discussion Points

• UI Implementation: How should users group tests? A drop-down list on the "New Test" page to add a test to a new or existing group seems plausible. This would automatically prioritize newly added takes to the pool to reduce their initial uncertainty but it might be ok.
• Policy Choice: Should Fishtest implement both UCB and Thompson Sampling, or enforce one? My data suggests Thompson Sampling is safer but slightly less efficient.
• Further Simulation: Would you require more simulations with different distributions of "true Elo" among candidates or with a larger number of simultaneous tests?

I am willing to write a PR for this feature if it receives positive feedback.