PaperlayerView exact revision on arXiv

Source-linked AI summary

Is Your Imitation Learning Policy Better than Mine? Policy Comparison with Near-Optimal Stopping

David Snyder, Asher James Hancock, Apurva Badithela, Emma Dixon, Patrick Miller, Rares Andrei Ambrus, Anirudha Majumdar, Masha Itkina, Haruki Nishimura

arXiv:2503.10966v4cs.ROstat.ML

TL;DR

Policy comparison is constrained by small feasible sample sizes, while batch tests require a fixed trial count and cannot safely be rerun after adding observations. STEP uses sequential testing to adapt trial counts to the comparison; it reduces required trials by up to 32% against state-of-the-art sequential methods while preserving probabilistic correctness.

  • Problem

    Policy comparisons have small feasible sample sizes, and batch tests require a predetermined trial count rather than adapting to sequentially observed results.

    Source: §I · p. 2

  • Method

    STEP is a sequential statistical framework for comparing two policies with tunable probabilistic correctness.

    Source: §I · p. 2

  • Results

    Up to 32% fewer evaluation trials than state-of-the-art sequential methods, without sacrificing probabilistic correctness.

    Source: §I · p. 2

  • Takeaways & Limitations

    STEP adapts the number of trials to comparison difficulty, stopping early when evidence suffices and avoiding decisions when evidence remains low.

    Source: §I · p. 2

    STEP’s current development relies on Bernoulli outcomes, requiring policy evaluations to use binary success/failure metrics.

    Source: §VII · p. 11

Abstract

from arXiv · show

Imitation learning has enabled robots to perform complex, long-horizon tasks in challenging dexterous manipulation settings. As new methods are developed, they must be rigorously evaluated and compared against corresponding baselines through repeated evaluation trials. However, policy comparison is fundamentally constrained by a small feasible sample size (e.g., 10 or 50) due to significant human effort and limited inference throughput of policies. This paper proposes a novel statistical framework for rigorously comparing two policies in the small sample size regime. Prior work in statistical policy comparison relies on batch testing, which requires a fixed, pre-determined number of trials and lacks flexibility in adapting the sample size to the observed evaluation data. Furthermore, extending the test with additional trials risks inducing inadvertent p-hacking, undermining statistical assurances. In contrast, our proposed statistical test is sequential, allowing researchers to decide whether or not to run more trials based on intermediate results. This adaptively tailors the number of trials to the difficulty of the underlying comparison, saving significant time and effort without sacrificing probabilistic correctness. Extensive numerical simulation and real-world robot manipulation experiments show that our test achieves near-optimal stopping, letting researchers stop evaluation and make a decision in a near-minimal number of trials. Specifically, it reduces the number of evaluation trials by up to 32% as compared to state-of-the-art baselines, while preserving the probabilistic correctness and statistical power of the comparison. Moreover, our method is strongest in the most challenging comparison instances (requiring the most evaluation trials); in a multi-task comparison scenario, we save the evaluator more than 160 simulation rollouts.

I. INTRODUCTION

Policy comparisons in robot learning are difficult to make reliable with few, sequentially arriving trials, while batch tests cannot safely adapt after seeing results. STEP enables adaptive sequential comparisons; the preliminaries formalize binary policy outcomes as a statistical test.

I. INTRODUCTION

  • Batch tests require a predetermined trial count, and retesting after adding trials can invalidate statistical assurances through p-hacking.Small feasible trial counts and sequentially revealed results make this inflexibility consequential.Source: §I · p. 1
  • STEP is a sequential framework that adapts trial counts to comparison difficulty while preserving probabilistic correctness and achieving near-minimal sample complexity.It can stop when evidence is sufficient or continue gathering trials within the experimental budget.Source: §I · pp. 1–2
  • The framework extends to multi-task and multi-policy comparisons by reducing them to pairwise statistical comparisons.The paper also evaluates a multi-task comparison of two imitation-learning policies in simulation.Source: §I · p. 2

II. PRELIMINARIES

  • Policy success is modeled as a binary outcome, with each policy’s success rate defined over independently sampled initial states and observations.The setup assumes i.i.d. evaluation trials and does not require knowing the underlying sampling distribution.Source: §II · p. 2
  • The comparison is a composite-hypothesis test: the null says the novel policy is no better than baseline, and the alternative says it is better.The hypotheses cover sets of possible success-rate pairs; each actual policy pair corresponds to one point.Source: §II · p. 3, Figure 2 · p. 3
  • The test controls worst-case Type-I error, while power measures correct rejection of the null under alternatives.The paper’s subsequent discussion uses a bidirectional test that can also decide in favor of the null.Source: §II · p. 3

III. PROBLEM FORMULATION

The evaluator chooses among continuing trials or making either comparison decision, under a fixed maximum budget and a Type-I error constraint. The formulation balances expected sample size and power, with the attainable power determining the trade-off.

III. PROBLEM FORMULATION

  • The evaluator’s decision rule must keep Type-I error at or below the selected significance level while seeking high power and fewer expected trials.A procedure that does not control Type-I error is infeasible.Source: §III · p. 3
  • At each step, the evaluator uses the collected-data state to continue, accept the null, or reject it, with at most Nmax trials per policy.The significance level α* and maximum trial count are selected in advance.Source: §III · p. 3
  • The objective trades off minimizing expected sample size against maximizing power, subject to validity and the attainable terminal power.The formulation sets the feasible power target based on Nmax, α*, and the unknown underlying distribution.Source: §III · pp. 3–4

IV. METHODOLOGY

STEP frames policy comparison as a sequential stopping problem: it tracks a compact state of evaluation outcomes and partitions states into stopping and continuation regions. The design seeks early decisions while controlling Type-I error, with risk accumulation tuned to comparison difficulty.

A. State Representation

  • After n trials per policy, the state uses each policy’s successful-trial count plus time, a near-minimal sufficient-statistic representation for Bernoulli outcomes.The success counts are sums of observed outcomes and form a first-order discrete integrator.Source: A. State Representation · p. 4

B. Decision Regions

  • The evaluator cannot steer the state; it decides when to stop by partitioning the state space into stopping and continuation regions.The decision rule is represented across time steps, and larger rejection or acceptance regions can reduce expected trials for the corresponding decision.Source: A. State Representation · p. 4, B. Decision Regions · p. 4
  • Larger rejection regions can shorten evaluation, but risk violating Type-I error control; risk must accumulate at a rate that balances easy and closely matched comparisons.The method allows probabilistic rejection and maximizes rejection-region size across time steps.Source: B. Decision Regions · p. 4

C. Type-I Error Control

STEP controls Type-I error uniformly over the composite null by reducing the null hypotheses to a finite set of worst-case cases. It propagates state occupancy under those cases to constrain rejection probabilities at each step.

C. Type-I Error Control

  • The composite null covers all pairs with p0 ≥ p1, so Type-I error must be controlled uniformly over that set.The paper frames this as analogous to distributionally robust control over the worst-case null pair.Source: C. Type-I Error Control · p. 4
  • Monotonicity, symmetry, and smoothness permit discretizing the null to finitely many worst-case equal-probability pairs, reducing error control to finite inequalities.The passage states that these properties support efficient discretization procedures that preserve safety.Source: C. Type-I Error Control · p. 5
  • A nonnegative matrix records state-reaching probabilities under each discretized null, and forward propagation updates those probabilities from the prior step.The constraints are expressed as Pnwn ≤ αn1, with rows representing the discretized null cases and entries corresponding to states.Source: C. Type-I Error Control · p. 5

D. Power Adaptivity to Varying Difficulty: Risk Budgets

STEP allocates a Type-I-error risk budget over time to balance early stopping on easier comparisons with waiting for evidence on harder ones. It then constructs rejection regions through sequential linear optimization under those risk constraints.

D. Power Adaptivity to Varying Difficulty: Risk Budgets

  • A nonnegative per-step risk budget summing to at most α* preserves Type-I error control; its temporal shape influences power and the balance between early and delayed stopping.The experiments use a uniform budget f(n) = α*/Nmax, described as heuristically reasonable while leaving room for improvement.Source: D. Power Adaptivity to Varying… · p. 5

E. Tractable Optimization

  • For each time step, STEP maximizes rejection-region size subject to the accumulated risk constraint and bounded rejection probabilities.The resulting linear programs are solved sequentially and can be computed offline before evaluation; the policy representation can be compressed from a vector to a set.Source: E. Tractable Optimization · p. 5

V. EXPERIMENTS

The experiments assess STEP’s statistical validity, performance across comparison difficulty, and sample efficiency. They use numerical success/failure simulations as well as simulated rollouts and physical-robot tasks.

V. EXPERIMENTS

  • The evaluation asks whether sequential testing matches batch testing in statistical validity, measured by Type-I error.The supplied experiment description lists this as one of the study’s questions, not as a reported result.Source: §V · p. 6
  • The experiments examine STEP’s advantages across sequential comparison problems of varying difficulty.The supplied passages state this as an evaluation question without reporting its outcome.Source: §V · p. 6
  • The study evaluates sample efficiency using numerical success/failure simulations, simulated rollouts, and physical-hardware tasks.These evaluation settings are described as the means of addressing the experiment questions.Source: §V · p. 6

A. Baseline Procedures

STEP and the sequential baselines control Type-I error, unlike repeatedly applying a batch test; across comparison settings, STEP’s finite-sample procedure balances power and stopping efficiency. Lai can perform well when its asymptotic approximation fits, while SAVI’s anytime validity can cost power under finite budgets.

A. Baseline Procedures

  • Lai is asymptotically optimal under a pre-set Nmax but assumes normality of empirical means; STEP solves the exact testing PDE at finite-sample resolution.SAVI remains valid for arbitrary Nmax, trading that generality for sample complexity when a finite trial limit applies.Source: A. Baseline Procedures · p. 6

B. Numerical Simulation

  • The simulation evaluates 45 alternatives with 5,000 trajectories each and 400 worst-case-null trajectories per alternative, using Nmax = 500 and α∗ = 0.05.The reported metrics are Type-I error, terminal power, and cumulative power.Source: B. Numerical Simulation · p. 6

1) How does sequential testing compare with batch testing in Type-I Error control?

  • In sequence, Barnard’s batch test violates Type-I error control, while sequential methods maintain it; STEP uses the risk budget most efficiently.Lai is more conservative in lower-variance settings, while SAVI is weaker more generally.Source: 1) How does sequential testing compare… · p. 6

2) What are the unique advantages of STEP in comparison problems of varying difficulty?

  • At a 10-percentage-point gap, SAVI has significantly lower terminal power in difficult cases than Lai and STEP, which closely approximate the SPRT Oracle.SAVI’s validity for arbitrarily large Nmax imposes finite-time costs.Source: 2) What are the unique advantages of… · p. 7, Figure 4 · p. 7
  • In a difficult, lower-variance, skewed setting with a 10-percentage-point performance gap, Lai cannot effectively adapt, while STEP significantly outperforms it by deciding more quickly for the alternative.Source: 2) What are the unique advantages of… · p. 7

C. How sample efficient is STEP in practical policy comparison settings?

STEP is evaluated in robot manipulation hardware tasks and a multi-task simulation comparison. It often stops well before the available trial budget for clear gaps, while closely matched comparisons can remain undecided; in uniform certification across three tasks, it saves more than 160 trials versus either feasible baseline.

C. How sample efficient is STEP in practical policy comparison settings?

  • The practical evaluations include hardware policy comparisons and simulation, with the simulation comparing two state-of-the-art imitation-learning policies across tasks.The hardware studies include clear-gap and closely competing policy settings.Source: C. How sample efficient is STEP in… · p. 7

1) Hardware Evaluation in the Large/Medium-Gap Regime:

  • A 36-percentage-point FoldRedTowel success-rate gap (56% to 92%) was detected in 17–23 trials by each sequential method, out of 50 total trials.For CleanUpSpill, a 52-percentage-point gap was detected in 7–14 trials, despite methods being tuned to Nmax values up to 30–70 times larger; STEP’s efficiency minimally degrades from Nmax = 200 to 500.Source: 1) Hardware Evaluation in the… · p. 8

2) Hardware Evaluation in the Small-Gap Regime:

  • More than 160 trials are saved by STEP in uniform certification across three tasks, compared with either feasible baseline.The multi-task stopping time sums the stopping times for the three tasks.Source: 2) Hardware Evaluation in the… · p. 9
  • With Nmax = 100, no method found a significant result for either the 59% versus 68% distribution-shift comparison or the 8-percentage-point Octo–OpenVLA gap.If the ground truth matched empirical success rates, the paper estimates Nmax = 500 would be required to determine p1 > p0.Source: 2) Hardware Evaluation in the… · p. 9

3) Multi-Task Evaluation in SimplerEnv Simulation:

In SimplerEnv, STEP is applied to three task comparisons of differing difficulty, with a Bonferroni correction combining their decisions. The section also situates policy comparison within statistical testing and related work.

3) Multi-Task Evaluation in SimplerEnv Simulation:

  • The three comparisons involved EggplantInBasket, SpoonOnTowel, and StackCube, with performance gaps of 16.4, 30, and 3 percentage points, respectively.The authors report the observed success rates as consistent with Li et al. [32].Source: 3) Multi-Task Evaluation in SimplerEnv… · p. 9
  • Bonferroni correction at α*[τ] = 0.01 for each of three tests confirmed the combined decision at α = 0.03.The combined decision was to reject the null because every subtest rejected it.Source: 3) Multi-Task Evaluation in SimplerEnv… · p. 10
  • STEP saved 160 simulation rollouts per policy versus other sequential procedures across the three-task comparison, while sequential methods used fewer than 40 rollouts on the easiest task.The fixed-batch approach would require 1,500 rollouts per policy across the tasks.Source: 3) Multi-Task Evaluation in SimplerEnv… · p. 10

A. Statistical Testing and Policy Evaluation

  • Neyman-Pearson testing has been used in robotics for fixed-sample policy characterization, while Barnard’s test is a powerful batch procedure without a direct way to select batch size in advance.The related-work discussion frames sequential testing as a response to the difficulty of choosing an appropriate batch size.Source: A. Statistical Testing and Policy… · p. 10
  • Multi-hypothesis testing can also extend to multi-policy comparison by examining pairwise comparisons simultaneously.Source: A. Statistical Testing and Policy… · p. 10

B. Sequential Statistical Evaluation Methods

The paper reviews sequential testing approaches and positions STEP against optimal-stopping, anytime-valid, and numerical methods. It concludes that STEP adapts trial counts to comparison difficulty and reports near-optimal stopping, while noting implementation limits and future extensions.

B. Sequential Statistical Evaluation Methods

  • In simple-vs-simple testing, the SPRT minimizes expected sample count among tests controlling Type-I and Type-II error; composite-testing work extends near-optimality through minimax or weighted alternatives.Source: B. Sequential Statistical Evaluation… · p. 10

1) Optimal Stopping-Based Methods:

  • Optimal-stopping methods reduce testing to a free-boundary PDE, but composite-null parameterization is difficult; asymptotic approximations can lose decision information at finite Nmax.Source: 1) Optimal Stopping-Based Methods · p. 10

2) Safe, Anytime-Valid Inference (SAVI) Methods:

C. Numerical Implementations

  • The related-work review identifies the lack of a numerical implementation of near-optimal policy comparison procedures for the full multidimensional composite-vs-composite setting.Source: C. Numerical Implementations · p. 11

VII. LIMITATIONS

  • STEP currently relies on Bernoulli outcomes, requiring binary success/failure metrics, and users must specify its risk accumulation rate f(k).The authors identify broader discrete or continuous distributions and improved rate selection as future work.Source: §VII · p. 11

VIII. FUTURE WORK

  • Future work includes principled multi-policy evaluation and extending STEP to multinoulli partial-credit schemes, which is direct in theory but brings implementation challenges.Source: §VIII · p. 11

IX. CONCLUSION

  • STEP adapts the number of evaluation trials to comparison difficulty, with sample efficiency for clear winners and abstention when closely competing policies leave insufficient evidence.The conclusion reports near-optimal expected trial counts and performance matching or exceeding state-of-the-art baselines across numerical and robotic simulation and hardware demonstrations.Source: §IX · p. 11

X. SUPPLEMENT

Supplementary material details the hardware evaluations and additional simulations, including low power for small gaps and substantial uncertainty in close CarrotOnPlate comparisons. It also reports a near-optimal oracle benchmark and regenerated-sequence analyses.

A. Details of Real-World Robot Experiments

  • The hardware evaluation details describe bimanual towel-folding and spill-cleanup tasks, carrot placement under environment variations, and practices to mitigate distribution shift during trials.The bimanual policies used 300 demonstrations for FoldRedTowel and 150 for CleanUpSpill.Source: A. Details of Real-World Robot… · p. 15

B. Additional Numerical Simulation Results

  • At Nmax = 100, sequentialized Barnard loses significant power after Bonferroni correction, while the Lai procedure shows inefficiency in skewed settings relative to STEP and SPRT.Source: B. Additional Numerical Simulation… · p. 15, Figure 7 · p. 16
  • For Nmax = 100, no procedure exceeds 50% power in the hardest regimes, and power is low for gaps of approximately 10 percentage points or smaller.A significant part of the low power reflects fundamental outcome variance, implying that meaningful comparisons with small gaps require substantially more trials.Source: B. Additional Numerical Simulation… · p. 15

C. Empirical Results with Regenerated Sequences

  • The counterfactual analysis regenerated Bernoulli sequences using each task’s empirical success rates and estimated mean sample complexities with standard deviations over 400 sequences per task.Source: C. Empirical Results with Regenerated… · p. 15

D. Further Analysis of CarrotOnPlate Experiments

  • CarrotOnPlate success-rate trajectories fluctuate and sometimes reverse their relative ordering, making the close policy comparisons difficult to resolve.The oracle analysis uses empirical terminal rates as its assumed true distributions.Source: D. Further Analysis of CarrotOnPlate… · p. 15
  • At 200 trials per policy, the SPRT Oracle has about a 50% rejection chance on the observed CarrotOnPlate gaps; at 500 trials, this reaches about 80%.The accompanying analysis reports nearly 400 trials for an approximately 75% rejection chance.Source: D. Further Analysis of CarrotOnPlate… · pp. 15, 17, Table II · p. 17

E. Additional CarrotOnPlate Experiments

Additional CarrotOnPlate evaluations use a 200-trial budget, while the supplement describes an approximation for selecting worst-case null hypotheses and checking error control.

E. Additional CarrotOnPlate Experiments

  • With Nmax = 200, no procedure resolved the PolicyA-versus-PolicyB comparison, but all methods stopped after 150 trials in the PolicyA environment comparison, saving 50 hardware evaluations.PolicyA and PolicyB labels replace Octo and OpenVLA because of a hardware implementation error in an earlier experiment.Source: E. Additional CarrotOnPlate Experiments · p. 17, Table III · p. 18

1) Worst-Case Null Hypotheses:

  • The proposed worst-case null lies at p0 = p1 = p, and its approximation interpolates between p0 and p1 in Bernoulli natural-parameter space.The authors note that the true worst-case null is difficult to compute exactly, while alternative estimates are generally similar and support numerical error-control verification.Source: 1) Worst-Case Null Hypotheses · pp. 17–18

2) Discretizing the Null Hypotheses:

The method discretizes the null hypotheses over an interior range while accounting for extremal cases, and the accompanying technical discussion describes filtration choices and error tradeoffs. In multitask comparisons, it reduces expected evaluation time relative to feasible baselines.

2) Discretizing the Null Hypotheses:

  • Approximately 100 discretization points were used for Nmax up to 500, with extremal nulls handled separately to avoid rapid variance decay near 0 and 1.Pinsker’s inequality can bound false-rejection error from discretization, which can be made arbitrarily small with a sufficiently dense grid.Source: 2) Discretizing the Null Hypotheses · p. 18
  • 110 to 170 trials are saved in expectation in uniform certification across three tasks versus either feasible baseline.The reported 160-trial simulation saving is consistent with the results in Table I.Source: Table IV · p. 19

3) Technical Setting:

  • The natural filtration contains observations through time n, while sufficient statistics for exponential families motivate using a compressed filtration in practice.Source: 3) Technical Setting · p. 19
  • In the fixed, finite-sample batch setting, the Neyman-Pearson lemma allows instances where Type-I and Type-II errors cannot both be controlled.Source: 3) Technical Setting · p. 19
  • The two-dimensional state is a lossy compression because constructing the optimal exact SPRT requires a three-dimensional state.Source: 3) Technical Setting · p. 19

4) Intuition for Tests:

  • Never rejecting the null ensures Type-I safety, while randomizing a decision can combine Type-I safety with small sample size; power with small samples can violate Type-I error.Source: 4) Intuition for Tests · p. 19

Related papers

Loading 2503.10966v4…