- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
cuBCR allocates avoidable failure risk using Shapley values in finite stochastic multi-agent models. It combines paired-permutation sampling with batched GPU backward induction for coalition recovery queries. The evaluation separates sampling savings from hardware acceleration and checks numerical results against exhaustive calculations and independent verification tools.
Critical strengths
The computational decomposition is well explained. Sharing a transition model across many policy-restriction queries is a sensible way to exploit GPU parallelism.
The validation is stronger than a CPU/GPU agreement check alone. Identical-query comparisons, batching ablations, reachability-pruning controls, and checks against PRISM-games and Storm provide useful support for correctness and performance.
Critical weaknesses
The headline 233× speedup combines GPU execution with savings from established permutation sampling. The paper appropriately separates these effects, but does not compare against stronger Shapley estimators mentioned in the related work. Equal-error comparisons would clarify how competitive the complete attribution pipeline is.
All reported attribution timings exclude model construction and engine initialization, which the paper notes can dominate small jobs. This matters for the proposed interactive debugging use case, where a policy or system revision may require rebuilding parts of the computation. Cold-start and incremental-update measurements would establish when the acceleration translates into practical savings.
The demonstrated scope is restricted. The implementation permits at most three simultaneously active agents and 64 joint-action rows per state, and assumes an explicit transition model. These limits make the tested workloads manageable but leave denser concurrent systems unexplored. The deployment discussion should remain tied to these assumptions.
Questions for authors
- How does paired-permutation sampling compare with alternative estimators under the same attribution-error target?
- What are cold-start latency and update costs after changing policies or transition probabilities?
- How do memory use and runtime grow as the number of simultaneously active agents increases?
2 comments
Dear Reviewer BvDQ,
Thank you for suggesting a comparison at the same attribution-error target. All four estimators met the 1% target on held-out runs across twelve TicketBench games. Leverage SHAP took 40% of the paired sampler’s warm runtime on a typical game, and Stratified SVARM took 42% (median per-game ratios, Table 5). Appendices C.2 and C.4 also report cold-start and update costs and show how runtime grows as more agents act at once. Could you let us know whether these results address the concerns behind your initial rating? If they do, we hope you will consider raising it.
Best regards, The Authors
Response to BvDQ: estimator comparisons, complete costs, and scaling
Thank you for recognizing the computational design and validation, and for suggesting comparisons with stronger estimators and measurements of complete analysis costs and scaling. Below, we respond to your comments and explain the changes made in the revised paper.
Weakness 1 / Question 1: Alternative estimators at the same attribution-error target.
The new comparisons show that better sampling methods can directly benefit from cuBCR's GPU engine. Leverage SHAP, 2-ADD-SHAP, and Stratified SVARM run on the unchanged engine across seven whole-agent TicketBench tasks with 16–28 agents. All 162 runs with exhaustive references reproduce their table-based estimates bit for bit. Thus, the engine's value extends beyond the paired-permutation estimator used in the original experiments.
Appendix C.3 compares the number of distinct coalition evaluations needed at the same error target. Each query evaluates recovery after fixing a set of agents' policies. On 12 TicketBench games with 20 agents, the median budgets are:
Total attributable risk is the failure risk that coordinated recovery can avoid. These empirical budgets use exact references and 30-seed error curves, interpolated where the observed 95th percentile of the largest error across agents reaches the target. They measure empirical error, without online coverage guarantees.
Table 5 measures warm attribution time using budgets calibrated against exhaustive references on separate seeds, then frozen for 30 held-out seeds per game. We report the 1% target because all four methods meet the empirical 95th-percentile maximum-error criterion on all twelve games (at 5%, paired permutations pass 6/12). Leverage SHAP and Stratified SVARM are faster on every game, taking 40% and 42% of paired time (median per-game ratios). For 2-ADD-SHAP, the group median is slower at 961 states and faster at 9,961 states.
Online stopping does not require exhaustive Shapley references to decide when to stop. Across 12 games, 30 seeds, and 2 tolerances, all 720 runs reach tolerance; every agent's error against the FP64 reference lies within its half-width. Median warm times are 0.224 s at 5% and 1.193 s at 1% (medians of game medians). Containment is empirical; coverage remains conditional on Theorem 1 (Appendix C.3).
Weakness 2 / Question 2: Cold start and revision costs.
Complete first attribution takes 0.438–1.42 s across 20 primary configurations. These measurements include process startup, model construction, initialization, upload, and attribution. Complete policy re-attribution takes 0.074–1.06 s with the process and model structure retained.
For the 28-agent example, first attribution takes 0.438 s, policy re-attribution 0.112 s, and a transition-probability revision 0.106 s when the possible transitions remain unchanged. Policy changes reuse the transition structure and refresh reduction weights. Probability changes upload new values; changes to the possible transitions require rebuilding.
Overcooked shows why retaining the model matters. First attribution takes 13.2 s, and rebuilding in a warm process still takes 12.7 s. Policy re-attribution with the model retained takes 1.69 s. The update interface was added for the rebuttal around unchanged solve kernels. All 171 complete sampler comparisons match fresh builds bit for bit. Appendix C.2 gives the timing breakdown and reuse requirements.
Weakness 3 / Question 3: Memory and runtime with more agents acting at once.
Appendix C.4 separates state count from concurrent actions. At a batch of 65,536 coalitions and horizon 50, tenfold state growth raises runtime about tenfold. Across 8–64 action combinations per state, memory is 0.975–0.984 GiB at about 1,000 states and 9.79–9.88 GiB at about 10,000, dominated by value buffers. Increasing action combinations from 8 to 64 raises runtime 13.4–16.7×. For a fixed number of actions per agent, combinations grow exponentially with the number of agents acting at the same step.
The GPU code used for the main experiments supports up to three agents acting at the same step and up to 64 action combinations per state. For additional scaling tests, we used a separate extended CUDA kernel. With 993 states and a batch of 65,536 coalitions, it takes 13.2 s for 256 action combinations per state and 26 s for 512. These tests use synthetic models with explicitly listed transitions.