Reinforcement Learning for Test Case Prioritization

1 INTRODUCTION

• Frequent code and test changes, long run-all regression suites, and quick CI build cycles make test prioritization both dynamic and time-constrained.Prioritization aims to detect faults early while reducing the testing burden.Source: §1 · p. 1
• CI prioritization must adapt to incoming history, whereas batch supervised models can require costly retraining and become outdated.The cited example, MART, does not support incremental learning because it is designed for static data.Source: §1 · p. 1
• The paper models sequential CI-agent interactions as RL using pairwise, listwise, and pointwise ranking, and introduces pairwise and listwise ranking as RL for this task.It implements the models with selected state-of-the-art RL techniques.Source: §1 · p. 2
• On enriched datasets, the best RL configurations improve ranking accuracy over previous RL work and MART and produce prioritizations close to optimal.The paper identifies pairwise ranking combined with state-of-the-art RL techniques as its most accurate approach.Source: §1 · p. 2
• The evaluation examines 21 RL configurations and addresses issues in prior empirical studies to seek more realistic results.The configurations combine ranking models and RL algorithms.Source: §1 · p. 2

2.1 Test Case Prioritization

• Test-case inputs combine execution verdict, average execution time, prior verdict history, and test age with lightweight code-based features derived from covered classes.The feature pipeline relates changed classes to impacted files, identifies covered impacted classes per test, and calculates features from those classes.Source: §2.1 · p. 3
• At each CI cycle, prioritization orders test cases for execution; the reference ranking puts failing tests first and breaks equal-verdict ties by shorter execution time.The paper treats the reference as tunable when the relative importance of failures and execution time differs by context.Source: §2.1 · pp. 2–3

2.2 Illustrative Example

• The illustrative CI history varies in test count across cycles, while a cycle’s optimal ranking must be estimated from history because execution times and verdicts are not yet known.Test ages increase after each completed cycle.Source: §2.2 · p. 3

2.3 Reinforcement Learning (RL)

• Because test execution outcomes are unknown before execution, the study uses model-free RL, in which agents learn from interaction rather than prior knowledge of environment dynamics.The RL framing represents interaction through observations, actions, and rewards.Source: §2.3 · p. 4

2.4 State-of-the-art RL Algorithms and Frameworks

• The paper uses deep-neural-network implementations from Stable Baselines, selecting state-of-the-art algorithms whose applicability depends on each ranking model’s action space.A2C, PPO1, PPO2, and TRPO apply to all three models; DQN, ACKTR, and ACER to pairwise and listwise; DDPG, TD3, and SAC to pointwise ranking.Source: §2.4 · p. 5, Table 2 · p. 5, §2.3 · p. 5

Heuristic-based Test Prioritization

• Heuristic prioritization uses coverage, models, history, or requirements, but is described as not adaptive to rapidly changing environments.Coverage-based methods also face collection and maintenance costs, accuracy trade-offs, and applicability constraints.Source: §3 · pp. 5–6

History-based approaches

• History-based methods are inexpensive, but history alone may be insufficient for complex systems and may adapt poorly to changing code and test suites.The paper combines historical information with code-based features in its RL approach.Source: §3 · p. 6

ML-based Test Prioritization Techniques

• Supervised and unsupervised ML can be impractical when prediction models must adapt continuously and quickly to new CI data.Prior supervised ranking work used pairwise and listwise methods as well as SVM Rank.Source: §3 · p. 6

RL-based Test Prioritization

• Earlier CI test-prioritization RL work used pointwise ranking, while this paper investigates pairwise, listwise, and pointwise models with applicable state-of-the-art algorithms.The earlier approach by Spieker et al. used Q-learning; the paper also contrasts its broader evaluation with Bertolino et al. [6].Source: §3 · pp. 6–7
• Bertolino et al. found RL approaches more robust to code changes, but their pointwise RL configuration was less accurate than leading supervised methods such as MART.The paper notes that prior RL work tested a small subset of implementations compared with modern libraries.Source: §3 · pp. 6–7

4 REINFORCEMENT LEARNING FOR TEST CASE PRIORITIZATION

• The proposed RL approach trains agents offline on test-execution history and code features, then updates them online with cycle feedback or replayed logs to adapt prioritization to changes.The goal is to learn a strategy close to a predetermined optimal ranking; a CI simulator supports offline training before deployment.Source: §4 · p. 7

4.1 Creation of the RL Environment

• The CI environment maps prioritization to pointwise, pairwise, or listwise ranking, defining observations, actions, rewards, and episode endings for each formulation.The section describes replaying test-execution history to train agents with selected state-of-the-art RL techniques.Source: §4 · p. 7, §4.1 · pp. 7–8

4.1.1 Listwise solution

• Listwise ranking selects the highest-priority test case at each step and pads shorter cycles with dummy cases, but its observation and action spaces grow with test-suite size and pose scalability challenges.The observation can become high-dimensional, while the agent must evaluate all possible actions at each step.Source: §4.1.1 · p. 8

4.1.2 Pointwise solution.

• Pointwise ranking assigns each test case a score from its individual features, then sorts cases by score; its observation is smaller than listwise, and rewards compare assigned scores with normalized optimal ranks.The environment provides feedback per case because final ranks are unavailable until the episode ends.Source: §4.1.2 · p. 9

4.1.3 Pairwise solution.

• Pairwise ranking compares two test cases at a time and uses a sorting algorithm to assemble the ranking; selection sort requires quadratic steps, while the experiments use merge sort to reduce episode length.The observation contains two test-case feature records and the action chooses which case has higher priority.Source: §4.1.3 · p. 9
• Pairwise ranking uses small action and observation spaces, potentially improving scalability, but imperfect comparisons leave its ability to achieve accurate rankings uncertain.Rewards distinguish desirability: failed tests are prioritized over execution-time savings, with a relatively large reward of 0.5 for ranking tests with the same verdict because failures are rare.Source: §4.1.3 · p. 10

4.2 Train an RL agent.

• A2C, PPO1, PPO2, and TRPO apply to all ranking models; DQN, ACKTR, and ACER to pairwise and listwise, and DDPG, TD3, and SAC to pointwise ranking.Source: §4.2 · p. 10
• Offline training starts from execution history and replays each cycle’s new logs after ranking, enabling adaptation without policy updates during prediction.The agent ranks test cases, the cycle’s executions produce logs, and those logs train the agent offline; this training uses only one cycle’s logs and is described as fast.Source: §4.2 · p. 10

4.3 Integration of an RL agent into CI Environments

• In the CI integration, setup and adaptation replay execution logs offline, while test-case ranking and feature calculation can occur during a build.The agent is trained using execution history and source-code-history features, then invoked with test-case features each cycle; ranking time is negligible, while feature-calculation time is not specified in the supplied passage.Source: §4.3 · p. 10, Figure 3 · p. 10

• The experiments assess the accuracy and cost of proposed RL configurations and compare them with baselines.Source: §5 · p. 11
• The section first covers datasets, evaluation metrics, comparison baselines, research questions, and experimental setup.Source: §5 · p. 11
• It then presents results and discusses their practical implications.Source: §5 · p. 11

• Six enriched datasets combine execution history and code features from Apache Commons projects, while two simple datasets contain execution history only.The simple datasets are described as representative of settings where source code is unavailable; enriched datasets represent settings where it is available but full coverage analysis is infeasible under CI time constraints.Source: §5.1 · p. 11
• Datasets contain 55–438 CI cycles and 2,207–32,118 test-case execution logs; cycles with fewer than six test cases were excluded.The authors state that prioritization offers little benefit for a few tests and that ranking a few tests can inflate accuracy results.Source: §5.1 · p. 11
• Enriched datasets have failure rates of 0–0.06 and 0–7 failed cycles, versus 19.36%–28.43% and 203–252 for simple datasets.Source: §5.1 · p. 11
• Enriched-feature calculation takes 1.78–9.46 seconds per cycle, which the authors consider reasonable overhead in practice.Source: §5.1 · p. 11

5.2.1 Normalized Rank Percentile Average (NRPA)

• NRPA measures how close a predicted ranking is to the optimal ranking, ranges from 0 to 1, and assigns higher values to better rankings.It is used to assess ranking performance independently of context and to compare with related work using NRPA.Source: §5.2.1 · p. 11

5.2.2 Average Percentage of Faults Detected (APFD)

• For the Paint-Control dataset, Figure 4 shows that A2C using the pairwise model performs poorly at prioritizing failed test cases in cycles 1–10, 13, and 40, as reflected by lower APFD values.Source: §5.2.2 · p. 11, Figure 4 · p. 11
• The authors observed NRPA–APFD contradictions across datasets and caution that NRPA can remain relatively high even for random rankings.NRPA treats every test case equally, so it can mislead when only a small share of tests fail.Source: §5.2.2 · p. 12
• APFD measures the weighted average percentage of faults detected in a test execution order, with higher values indicating faster fault detection.The paper uses APFD because prioritizing failed test cases correctly matters more for regression testing than ranking the remaining tests.Source: §5.2.2 · pp. 11–12
• The authors omit APFD when a cycle has no failed tests and exclude cycles with fewer than six tests from both metrics.They report that random rankings for five or fewer items have high worst and average NRPA values, which could inflate evaluation results.Source: Figure 5 · p. 11, §5.2.2 · p. 12

5.3 Comparison Baselines

• RL-BS1 is the first RL baseline, evaluated on the two simple datasets it originally used, excluding GSDTR.GSDTR combines execution results from multiple Google products, but product identifiers are missing, preventing the authors from separating product-specific datasets.Source: §5.3 · p. 12
• RL-BS2 uses the best configuration from Bertolino et al. on the six enriched datasets originally used in that work.The prior work's datasets, implementations, and detailed experimental results were publicly available.Source: §5.3 · p. 12
• Baseline results differ from published results because the authors changed metric handling and excluded cycles with fewer than five tests.Each baseline was run only on its original datasets because its implementation did not support other datasets without potentially error-prone changes.Source: §5.3 · p. 12
• MART is the supervised-learning baseline, selected as the best ranking technique based on reported results from Bertolino et al..The authors note that MART does not support incremental learning, which they identify as essential for frequently changing CI environments.Source: §5.3 · p. 12

5.4 Research Questions

• RQ1 asks how selected state-of-the-art RL solutions perform in prioritization accuracy and cost on simple and enriched datasets.Its subquestions examine algorithm–ranking-model combinations, ranking models across algorithms, and differences among RL algorithms.Source: §5.4 · p. 13
• RQ2 asks how the best RL solution identified in RQ1 compares with baselines on their respective original datasets.The comparisons cover previous RL baselines and MART.Source: §5.4 · p. 13

5.5 Experimental Setup and Configurations

• The study ran 168 experiments across datasets and ranking-model/RL-algorithm combinations, yielding 308,448 training and evaluation instances.Each agent was trained on a cycle's execution logs and tested on the subsequent cycle, then updated as the next cycle's logs were replayed.Source: §5.5 · p. 13
• The authors implemented pairwise, listwise, and pointwise ranking with RL algorithms supported by each model's action space.They simulated CI with Gym and used Stable Baselines v2.10.0; listwise ranking with ACKTR was dropped because training took more than 12 hours per cycle.Source: §5.5 · p. 13
• Training stopped at the minimum of 200*n*log2(n) steps and one million steps, or when episode reward plateaued for over 100 consecutive episodes.The step budget reflects the worst-case pairwise training cost; default RL parameters were used without tuning.Source: §5.5 · p. 13
• Each experiment ran once, while the analysis covered many cycles and 308K training and evaluation instances.The full computation required more than 46 days on three CPU cores and 20 GiB of memory.Source: §5.5 · p. 13

5.6.1 RQ1.

• Pairwise-ACER had the best averages across configurations and performed best on all but one dataset in post-hoc comparisons.Pairwise-A2C and pairwise-PPO2 followed; all listwise configurations, pointwise-TD3, and pointwise-SAC performed worst.Source: Table 4 · p. 14, §5.6.1 · p. 14
• Pairwise and pointwise prediction times stayed below 2.22 seconds across datasets, while listwise prediction sometimes exceeded 200 seconds.The authors report that training-time differences, measured in minutes, do not constitute a practical issue because training can run in the background.Source: §5.6.1 · p. 15
• Across shared algorithms, pairwise ranking performed better than pointwise and listwise for both enriched and simple datasets; pointwise generally beat listwise.The exception was PPO1, for which pointwise and listwise were comparable.Source: §5.6.1 · p. 16
• The authors recommend pairwise ranking with PPO2, A2C, or ACER, citing relatively fast training, prediction under 2.22 seconds, and especially good accuracy for ACER.Listwise configurations combine relatively low accuracy with the worst prediction times.Source: §5.6.1 · p. 17

5.6.2 RQ2

• Pairwise-ACER significantly beat RL-BS2 across datasets and MART on four datasets, with CODEC and MATH equivalent; its average CLE against MART was 0.75.The CLE against RL-BS2 ranged from 0.89 to 0.98.Source: Table 8 · p. 17, §5.6.2 · p. 18
• RL agents can be incrementally trained as execution logs and code changes arrive, whereas MART is described as not directly and easily applicable to online or incremental learning.The authors say RL adaptation avoids retraining a new model from scratch.Source: §5.6.2 · p. 18

5.7 Threats to validity

• Different failure rates between enriched and simple datasets may threaten generality; the authors therefore limit claims to relative effectiveness, not absolute effectiveness.They report broadly consistent trends, but not magnitudes, across the low- and high-failure-rate datasets.Source: §5.7 · p. 18
• For ML evaluation, injected faults are not considered valid because they add faults randomly, unrelated to execution history.The authors note that low failure rates also characterize datasets commonly used to evaluate test selection and prioritization.Source: §5.7 · pp. 18–19
• The authors identify standard evaluation metrics as a threat to validity and discuss their limitations, interpretation, and appropriate use.Source: §5.7 · p. 19

6 CONCLUSION

• The evaluation combined 10 RL algorithms with three ranking models into 21 configurations, with pairwise ranking plus ACER achieving the best ranking accuracy.The formalization covers pairwise, pointwise, and listwise ranking models.Source: §6 · p. 19
• Pairwise-ACER’s near-optimal accuracy depends on enriching test execution history with lightweight code features; execution-history-only datasets did not yield satisfactory results with any learning technique.The paper concludes that pairwise-ACER can provide a reliable and adaptive CI prioritization solution based on adequate history and code data.Source: §6 · p. 19
• On enriched datasets, pairwise-ACER improved NRPA by +0.1 over previous RL work and +0.027 over MART, reaching NRPA > 0.96.The accuracy is also described as very close to the optimal ranking based on actual failure data and execution times when history is enriched with lightweight code features.Source: §6 · p. 19
• The algorithms used default hyperparameters and only a limited set of reward functions, leaving systematic optimization of pairwise-ACER as future work.The authors identify automated, systematic tuning with search-based frameworks such as Optuna as a next step.Source: §6 · p. 19
• The available datasets were limited in features, product count, and failure-rate diversity, and no common benchmark used identical representative datasets.The authors describe extending TravisTorrent to analyze detailed test execution data and source-code history.Source: §6 · p. 19
• Whether pairwise ranking also outperforms state-of-the-art ranking models beyond test case prioritization remains an open evaluation question.The authors call for extended evaluation in a more general context.Source: §6 · p. 19