PaperlayerView exact revision on arXiv

Source-linked AI summary

AnyRank: Reliable Anytime Policy Ranking via Sequential Testing

Apurva Badithela, David Snyder, Tenny Yin, Jade Sceats, George Pappas, Nikolai Matni, Masha Itkina, Haruki Nishimura, Anirudha Majumdar

arXiv:2610.14603v1cs.ROcs.SYeess.SY

TL;DR

Costly hardware trials leave robot-policy rankings vulnerable to finite-sample error, particularly across many policies. AnyRank combines sequential pairwise testing with graphical multiple-hypothesis correction and adaptively allocates trials. It uses up to 50% fewer hardware evaluations than existing statistically rigorous approaches while guarding against incorrect rankings.

  • Problem

    Costly hardware trials leave small samples, making multi-policy rankings vulnerable to finite-sample statistical error.

    Source: §3 · p. 4

  • Method

    AnyRank combines sequential pairwise tests with graphical multiple-hypothesis correction and adaptively allocates evaluations, optionally using prior information.

    Source: §4 · pp. 4–6

  • Results

    Up to 50% fewer hardware evaluations are required than with existing statistically rigorous approaches, while guarding against incorrect rankings from imperfect priors or benchmark heuristics.

    Source: §1 · p. 2

  • Takeaways & Limitations

    AnyRank can provide partial rankings at stopping times while bounding the probability of one or more incorrect decisions by α*.

    Source: §4 · p. 7, §6 · p. 11

    Its statistical assurances assume i.i.d. evaluation data, and existing simulation and off-the-shelf video-world-model priors were not sufficiently predictive at scale.

    Source: §6 · p. 11

Abstract

from arXiv · show

Due to the high cost of hardware experiments, robot policies are predominantly evaluated by comparing their empirical performance on a limited number of hardware trials. However, finite-sample statistical uncertainty can lead to erroneous conclusions, especially when ranking multiple policies using a fixed batch of evaluation data. We propose AnyRank: a sequential method for multi-policy ranking that (i) adaptively allocates trials to hard-to-separate policies, (ii) provides (partial) rankings at any stopping time while bounding the probability of an incorrect ranking, and (iii) optionally exploits prior information to prioritize hardware evaluations more efficiently. This prior information could be informed from expert intuition, a small set of held-out hardware evaluations, or from policy rollouts in a simulator or an action-conditioned video world model. Notably, the prior can be imperfect; while a strong prior can provide efficiency gains on hardware, any inaccuracies in prior policy rankings do not invalidate the statistical assurances of AnyRank. We achieve the aforementioned properties through novel theoretical contributions that combine sequential testing with multiple-hypothesis graphical testing approaches. Experiments in simulation and real-world policy evaluation benchmarks show that AnyRank requires up to 50% fewer hardware evaluations compared to existing statistically rigorous approaches, while guarding against the incorrect rankings produced by heuristic methods used by state-of-the-art benchmarks.

1 Introduction

Robot policy rankings are difficult to trust when costly hardware trials leave only small samples, especially for many policies. AnyRank combines sequential testing with graphical multiple-hypothesis testing to produce reliable rankings while allocating evaluations efficiently.

1 Introduction

  • Small hardware samples make empirical policy comparisons vulnerable to chance reversals, especially when many policies must be ranked from a fixed batch.The introduction notes that a few extra successful rollouts can flip the ranking of close competitors.Source: §1 · p. 1
  • Existing approaches trade off indeterminate rankings against error risk, while simulation-based estimates may not reflect real-world performance.Confidence-interval comparisons can leave many ties, whereas preference-based rankings can have high error rates in the non-asymptotic regime.Source: §1 · p. 2
  • AnyRank combines sequential data collection with graphical multiple-hypothesis testing to allocate evaluations to hard-to-distinguish policies and control family-wise error.Its testing procedure can incorporate prior information while guarding against imperfect priors.Source: §1 · p. 2
  • Up to 50% fewer hardware evaluations are required than with existing statistically rigorous approaches, while guarding against incorrect rankings from imperfect priors or benchmark heuristics.The reported experiments include RoboArena and the TRI-LBM dataset.Source: §1 · p. 2

2 Related Work

Prior work offers pieces of rigorous robot policy evaluation, but does not directly provide efficient, reliable rankings of multiple policies under sequential evaluation. AnyRank combines sequential pairwise tests with graphical correction for multiple comparisons.

Heuristic Approaches

  • Hardware evaluation is costly and small-sample results are often inconclusive; preference-based Bradley-Terry rankings provide no statistical guarantee of correctness.Simulation and video world models scale evaluation but do not provide statistical assurances for relative rankings.Source: §2 · pp. 2–3

Sequential Hypothesis Testing

  • Sequential, non-asymptotic tests permit optional stopping while controlling Type-I error, but prior robotics work mainly addresses pairwise comparisons.Safe anytime-valid inference supports online adaptation to evaluation evidence.Source: §2 · p. 3

Rigorous Robot Policy Evaluation

  • Bonferroni correction can limit power in multi-policy ranking because the number of pairwise hypotheses grows quadratically with the policy count.Graphical tests reallocate risk to harder comparisons, but existing batch procedures do not directly extend to sequential evaluation.Source: §2 · p. 3
  • AnyRank extends graphical testing to adaptive sampling and sequential evaluation, addressing both sources of inefficiency while maintaining valid rankings.The passage identifies both contributions as necessary for efficiency gains over classical Bonferroni corrections.Source: §2 · p. 3

3 Problem Formulation: Policy Ranking as Hypothesis Testing

The paper frames ranking M policies as a multiple-hypothesis problem over pairwise comparisons of their mean performance. Its objective is to minimize evaluation effort while retaining statistical power and controlling the probability of any incorrect pairwise decision.

Problem Formulation: Policy Ranking as Hypothesis Testing

  • Policies are ranked by their unknown mean performance on i.i.d. task and environment samples, using a shared bounded performance metric.A ranking orders the policies’ expected metric values over the real-world distribution.Source: §3 · p. 3
  • Ranking multiple policies requires deciding pairwise hypotheses; a ranking may be partial, and the family-wise error rate is the chance of at least one incorrect decision.Splitting the risk budget across all pairs can reduce power because the number of tests grows quadratically with the policy count.Source: §3 · p. 4
  • The goal is to rank policies with as few evaluations as possible while balancing expected sample complexity and statistical power under a specified FWER bound.Different pairwise hypotheses can require different amounts of evidence, making active choice of the next policy important for efficiency.Source: §3 · p. 4

4 Method: Multi-Policy Ranking via Sequential Graphical Testing

AnyRank separates multi-policy ranking into graphical correction over pairwise tests and sequential, nonparametric evaluation of each comparison. It uses prior information and adaptive sampling while preserving family-wise error control under the stated conditions.

4 Method: Multi-Policy Ranking via Sequential Graphical Testing

  • AnyRank reduces multi-policy ranking to pairwise decisions corrected through a graphical procedure, and incorporates prior knowledge into the graph to accelerate ranking.Pairwise evaluations use the sequential, nonparametric procedures of Snyder et al. [51].Source: §4 · p. 4
  • Graphical tests assign portions of the global risk budget to hypotheses and recycle a rejected hypothesis’s budget to others.The initial allocations sum to α*, and graph weights determine how rejected hypotheses redistribute risk.Source: §4 · p. 4
  • A softmax-style prior allocation gives larger risk budgets to pairs predicted to be easier to distinguish; γ=0 is uniform allocation, while γ=∞ gives a prior-ordered chain.The corresponding batch special cases are Holm’s procedure and fixed-sequence testing.Source: §4 · pp. 4–5
  • N-SCORE supplies anytime-valid pairwise p-values, allowing comparisons to stop once evidence is sufficient or remain open for further evaluations.The method can use these p-values at any stopping time without invalidating the comparison’s Type-I error control.Source: §4 · p. 5
  • AnyRank samples policies associated with active comparisons that have high α[i], using the less-evaluated policy in a pair as its binding constraint.A hedged selection rule chooses the next policy based on its largest advantage score.Source: §4 · pp. 5–6
  • Anytime-valid p-values remain valid under adaptive sampling and stopping, so simulated graph updates can be used while the initial risk allocation and graph weights remain fixed before evaluation.This reconciliation permits sequential evaluation with graphical risk reallocation.Source: §4 · pp. 4, 6, 7
  • Under a valid graphical test and a measurable sampling rule with finite optional stopping, AnyRank bounds the probability of one or more incorrect ranking decisions by α*.The guarantee is stated in Theorem 1.Source: §4 · p. 7
  • Transitive closure can add implied pairwise rankings without further evaluation, and the resulting procedure retains FWER control while being more powerful.For example, deciding A<B and B<C implies A<C.Source: §4 · p. 7

5 Experiments

Experiments across RoboArena, TRI-LBM, DROID-task, and synthetic settings assess reliability, efficiency, prior information, and scalability. AnyRank generally rejects more hypotheses with fewer samples while retaining partial rankings when evidence is insufficient.

Experiment Setup

  • The experiments cover over 7000 policy rollouts across 20+ policies, using world-model and held-out evaluations as priors as well as synthetic data for scalability analysis.The hardware evaluations include RoboArena, Large Behavior Models, and DROID-task policies.Source: §5 · p. 7

Reliability of Policy Rankings (R1)

  • Bradley–Terry variants can produce incorrect and self-inconsistent RoboArena rankings, whereas AnyRank returns rankings that remain consistent as evaluations accumulate.At 2450 total trials, AnyRank's ranking remains consistent even though fewer hypotheses are decided.Source: Figure 3 · p. 8, §5 · p. 9
  • AnyRank's ranking guarantee persists with an imperfect world-model prior whose ranking correlation with real evaluations is r = 0.05.Its sample complexity remains comparable to the no-prior AnyRank0 ablation.Source: §5 · p. 9

Policy Evaluation Efficiency (R2)

  • Across RoboArena and TRI-LBM, AnyRank variants reject more hypotheses with fewer samples; on RoboArena4, they use around 50% fewer hardware trials than Bonferroni.The comparison concerns trials needed to fully decide the ranking on RoboArena4.Source: Figure 4 · p. 9, §5 · p. 9
  • AnyRank∞ can be more efficient when all policies are separable, but can stall on difficult hypotheses; AnyRank reallocates confidence budget using evaluation data and rejects more hypotheses across harder cases.The passage reports a complete RoboArena4 ranking and more hypotheses rejected in RoboArena7 and TRI-LBM.Source: §5 · p. 9

AnyRank Improves with Good Priors (R3)

  • With a strong DROID-task prior (r = 0.89), AnyRank requires fewer samples than AnyRank0, while AnyRank∞ has 188 trials in the example.The authors note that efficiency gains over no-prior graphical methods need not be substantial and identify hardware evaluation requirements as a bottleneck.Source: §5 · p. 10

Scalability (R4)

  • On synthetic data, increasing the number of policies raises total sample complexity, while AnyRank uniformly outperforms standard Bonferroni.In a 15-policy RoboArena evaluation, AnyRank returns a partial ranking reflecting uncertainty around policies with limited evidence.Source: §5 · pp. 10–11

6 Conclusion

AnyRank provides anytime-valid partial rankings with statistical assurances and adaptively allocated evaluations, optionally using prior information. Its graph design balances efficient decisions against the risk of getting stuck, while prior-based allocation can favor comparisons predicted to be easier without invalidating the procedure when priors are inaccurate.

6 Conclusion

  • AnyRank produces anytime-valid partial rankings with statistical assurances and adaptively allocates trials, optionally using prior information; the paper reports improved reliability and sample efficiency on real-world benchmarks.The framework assumes i.i.d. evaluation data, and the authors report that simulation and off-the-shelf video world-model priors are not sufficiently predictive at scale.Source: §6 · p. 11

A.1 Strategies for Graph Propagation and Risk Reallocation

  • Fixed-sequence testing is most efficient when every hypothesis is decidable, but can get stuck on hard comparisons; Holm-like allocation trades some per-hypothesis efficiency for a hedge against that risk.The graph specification spans a continuum of trade-offs between hedging and performance, controlled by initial risk allocation and reallocation weights.Source: §A.1 · p. 17

A.2 Graph Initialization using a Prior

  • Prior estimates of pairwise performance gaps guide both initial significance levels and graph weights, directing more risk toward predicted-easier comparisons for faster decisions and subsequent risk recycling.The prior can be inaccurate without invalidating family-wise error control; later significance transfers adapt the allocation.Source: §A.2 · pp. 17–18

A.3 Proof of Theorem 1

Theorem 1’s proof separates adaptive sampling decisions from the terminal graphical evaluation. With a graph initialized before evaluation and valid anytime p-values, the resulting rankings retain the global error guarantee.

A.3 Proof of Theorem 1

  • The proof isolates the choice of which policies to sample next from the terminal graphical evaluation, so sampling decisions do not determine the graph’s initial risk allocation or weights.Reallocation follows a fixed graph update rule rather than collected evaluation outcomes.Source: §A.3 · p. 18
  • Anytime p-values remain uniformly valid under the stated independence and stopping-time conditions, supporting the validity of the graphical decisions.The graph’s initial allocations and weights are independent of evaluation data, and its subsequent reallocation uses a fixed update rule.Source: §A.3 · p. 18
  • With a finite evaluation budget, the graphical procedure runs with probability one and controls the ranking decisions at α* when each constituent hypothesis has valid p-values.The proof relies on the validity of the graphical multiple-hypothesis procedure given those inputs.Source: §A.3 · p. 18

B Proof of Validity Under Transitive Closure

The transitive-closure argument represents full rankings through pairwise-comparison belief sets and shows that closure adds no rejections beyond those implied by the underlying decisions. The accompanying remarks state assumptions and clarify evaluation baselines.

B.1 The Lifted Representation

  • The lifted representation associates each pairwise comparison with the full rankings consistent with it, creating belief copies over candidate rankings.For each comparison, half of the candidate true rankings are consistent with it.Source: §B.1 · pp. 18–19

B.2 Transitive Closure as Set Inclusion

  • A transitive comparison’s belief set is included in the union implied by its two constituent comparisons, so rejecting those constituents already implies the closure decision.For γ > α, every ranking implies γ > β or β > α.Source: §B.2 · p. 19

B.3 A Consistent AnyRank Decision Rule

  • AnyRank rejects a candidate ranking when any of its belief copies rejects, equivalent to rejecting when a pairwise implication conflicts with accumulated evidence.This lifted-space rule permits transitive closure without increasing FWER.Source: §B.3 · p. 19

B Proof of Validity Under Transitive Closure

C Additional Technical Remarks

  • The analysis assumes i.i.d. draws across tasks and environments, but not i.i.d. increments within policy rollouts; the authors report no significant drift among the 34 evaluated policies at α = 0.1.This drift check indicates no significant evidence of violation of the i.i.d. assumption in the paper’s data.Source: C Additional Technical Remarks · pp. 19–20
  • When equal means make both mirrored directional nulls true, strict ranking generally requires running each one-sided test at α/2; the paper also defines power as the expected fraction of atomic hypotheses rejected.Full-ranking power is the probability that all atomic hypotheses reject and is no greater than the stated multihypothesis power.Source: C Additional Technical Remarks · p. 20

D Choice of Baselines

  • Sequentialized AnyRank0 and AnyRank∞ are compared with sequentialized Bonferroni to measure risk-recycling benefits, while comparisons with AnyRankγ assess prior benefits.A weighted Bonferroni baseline also helps isolate graph asymmetry from risk recycling.Source: D Choice of Baselines · pp. 20–21

E Hardware Experiments

Hardware experiments show that AnyRank can recover complete or partial policy rankings, while remaining valid with imperfect priors. Results also expose settings where weak priors reduce efficiency and where Bradley–Terry rankings are unreliable.

E Hardware Experiments

  • RoboArena priors based on held-out evaluations or world-model rollouts do not strongly rank the remaining policies when the outlier PG-Bin is excluded.The evaluation uses 20 held-out evaluations per policy or Ctrl-World rollouts on 40 randomly selected DROID environments.Source: E Hardware Experiments · p. 21, Figure 9 · p. 21

E.2 Sample Efficiency

  • TRI-LBM results continue to show AnyRank's advantages over other baselines, although two nominal PushCoasterToMug policies remain statistically indistinguishable after 50 trials per policy.The passage also reports that γ = 1 may have limited sample complexity and leaves tuning γ for future study.Source: E Hardware Experiments · p. 21, §E.2 · p. 23, Figure 11 · p. 23

E.1 Statistical Reliability of Ranking

  • AnyRank and its variants recover a complete ranking for four RoboArena policies, whereas weighted Bonferroni cannot distinguish the top two; across all seven policies, no FWER-controlling method produces a full ranking.With all seven policies, AnyRank separates A, E, F, and G while B, C, and D remain statistically indistinguishable from one another and from A and E; fixed-sequence AnyRank∞ also fails to distinguish B, C, and D from A, E, and F under the imperfect prior.Source: §E.1 · pp. 22–23, Table 3 · p. 23

E.3 Reliability Against Imperfect Simulation Priors

  • 130 trials: AnyRank at γ = 10 requires slightly more trials than AnyRank0 when the Put carrot in bowl world-model prior has correlation r = 0.18 with real-world performance.The weak prior can make AnyRank marginally less efficient than AnyRank0, but does not sacrifice validity; RoboArena and LBM also have weak simulation priors and can be less efficient than AnyRank0.Source: §E.3 · p. 23, Figure 12 · p. 24

E.4 Scalability

  • Bradley–Terry rankings are susceptible to miscalibration and inconsistency at small sample sizes; Table 4 covers preference rankings for all 15 RoboArena policies.The accompanying discussion notes that many policies remain statistically indistinguishable in Figure 8.Source: §E.4 · p. 24, Table 4 · p. 24

F Synthetic Experiments

  • Synthetic experiments use oracle-known means because real evaluations cannot establish FWER control or asymptotic inconsistency when true policy means are unknown.Real-data checks can partially assess baseline miscalibration against AnyRank and inconsistency across data subsets.Source: F Synthetic Experiments · p. 25

F.1 Ranking Procedures

  • Bootstrapped Bradley–Terry compares pairwise confidence intervals with a Bonferroni correction, but its brittle construction makes more efficient graphical corrections infeasible.The implementation uses M = 5000 bootstrap redraws and hypothesizes that the variants may lose power and inherit standard Bradley–Terry inconsistency.Source: §F.1 · p. 25

F.2 Experiments with Synthetic Data

The synthetic experiments test ranking procedures under known policy means, where error rates can be measured directly. They compare AnyRank and Bradley–Terry approaches across settings that vary in ranking difficulty and full-ranking feasibility.

F.2 Experiments with Synthetic Data

  • Because robot performance is directly observed, the paper distinguishes this setting from Bradley–Terry uses where preferences proxy an unobservable metric.The authors identify difficulty ascertaining Type-1 error on practical datasets as Bradley–Terry's central limitation.Source: §F.2 · p. 25
  • Synthetic Bernoulli instances with known means allow repeated evaluation of FWER control and empirical power, which cannot generally be validated on real datasets.The experiments run each ranking procedure on 200 independent redraws, measuring time to full ranking and the fraction of hypotheses rejected over time.Source: §F.2 · pp. 25–26
  • The design uses five policies and three settings: homogeneous feasible, heterogeneous feasible, and homogeneous infeasible rankings.The infeasible setting has two equal means; each procedure is capped at Nmax = 2000 evaluations per policy and the global ranking FWER target is α = 0.05.Source: §F.2 · p. 26

F.2.1 Limitations of Bradley–Terry: Asymptotic Inconsistency

A synthetic three-policy example demonstrates that Bradley–Terry rankings based on empirical performance preferences can converge to an ordering inconsistent with the policies’ true means. The constructed outcome distributions make a higher-variance policy appear preferable more often.

F.2.1 Limitations of Bradley–Terry: Asymptotic Inconsistency

  • The constructed task gives three policies true means μ1 = 0.3, μ2 = 0.7, and μ3 = 0.85, with discrete partial-credit outcomes across ten subgoals.The first two policies have Bernoulli rewards, while the third receives 0.8 or 0.9 with equal probability.Source: §F.2.1 · pp. 26–27
  • In the infinite-data limit, Bradley–Terry ranks μ1 < μ3 < μ2 instead of the true order μ1 < μ2 < μ3.The preference indicator is empirical performance, yet the resulting ranking remains inconsistent with the policies’ mean performance.Source: §F.2.1 · p. 27
  • The 0.7-mean policy can beat both alternatives about 70% of the time, so more data can increase confidence in the incorrect ordering even with bootstrap correction.The counterexample illustrates Bradley–Terry inconsistency in general, including robust bootstrapping corrections.Source: §F.2.1 · p. 27, Figure 14 · p. 27

F.3 Validating Type-1 Error (FWER) Control on Synthetic Data

Synthetic experiments test FWER control where true policy means are known, including a setting with tied means where any full ranking is erroneous. They also compare direct empirical-mean rankings with preference-based Bradley–Terry rankings when FWER control is not the goal.

F.3 Validating Type-1 Error (FWER) Control on Synthetic Data

  • In the homogeneous-infeasible setting, AnyRank uses nearly the full α* = 0.05 risk budget, with empirical error 0.045, while bootstrapped BTα is safe but more conservative.Nine of ten hypotheses are decidable; a full ranking would incorrectly order the tied-mean policies and count as a Type-1 error.Source: §F.3 · p. 27
  • Standard Bradley–Terry is correct at most 50% of the time in this tied-mean setting, and its instability cannot be quantitatively evaluated on real data.BT is not shown in Figure 13; in the theoretical identical-means case, it almost never produces ties.Source: §F.3 · p. 27

F.4 Note: Empirical Performance is as Strong as Non-Bootstrapped BT

  • Across synthetic data scales, ranking by current empirical means is as effective on aggregate as preference-based Bradley–Terry when FWER control is not a concern.The paper concludes that directly observed metrics are generally best estimated from their constituent observations rather than proxy measures.Source: §F.4 · p. 28

F.5 Investigating Empirical Power Of Valid Methods On Synthetic Data

On synthetic data, AnyRank reaches partial and full rankings faster than Bradley–Terry variants across feasible settings. In the counterexample, bootstrapped EM Bradley–Terry fails FWER control and selects an incorrect mean-performance ranking.

F.5 Investigating Empirical Power Of Valid Methods On Synthetic Data

  • In HO-I, AnyRank rejects more hypotheses sooner than bootstrapped BT, with its advantage growing as hypotheses become harder to distinguish.Source: §F.5 · p. 28
  • On HE-F, AnyRank reaches full empirical ranking power at approximately 1,000 evaluations, while BTα reaches only 60% power after 2,000.Source: §F.5 · p. 28
  • In this setting, preference scores and evaluation rollout scores cost approximately the same per pair of policy rollouts.The cited example of cheaper simulation-proxy evaluations assumes similar relative data availability.Source: §F.5 · p. 28
  • At approximately 750 evaluations, AnyRank reaches full empirical power on HO-F, versus just over 2,000 for BTα.Figure 19 describes the HO-F comparison; the reported evaluation counts are given in the accompanying text.Source: §F.5 · pp. 28–29, Figure 19 · p. 31

F.6 Counterexample and Bradley-Terry Variants

  • On the counterexample, bootstrapped EM Bradley-Terry failed FWER control in five of six reruns at α = 0.05 and selected an incorrect mean-performance ranking.Source: §F.6 · p. 29
  • Comparison-based flattening can erase performance-difference magnitudes, skewing rankings when those magnitudes are asymmetric.Source: §F.6 · p. 29

Related papers

Loading 2610.14603v1…