We evaluate AI agents in an online setting where tasks arrive sequentially and, before running each task, we construct an upper predictive bound on its time-to-success---the number of interactions until the task is completed successfully. Under a limited budget, some runs are stopped early, so their time-to-success is unobserved (right-censored), and the correctness of the bound may be unknown. We introduce PRedictive Bounds for Online Budget Efficiency (PROBE), a method for constructing calibrated upper predictive bounds while adaptively allocating a limited budget across agent tasks to reduce the anticipated coverage deficit. Our method calibrates the bounds online using inverse-probability-weighted feedback together with a correction designed to minimize coverage deficit while remaining unbiased. We prove that PROBE provides a coverage guarantee for any finite time horizon while satisfying the budget constraint.
Experiments on software engineering, retrieval-augmented generation, and instruction following show that PROBE attains a coverage rate closer to the target level with tighter predictive bounds than a calibrated baseline.