An improved system and method is provided for using sampling for scheduling advertisements in slots of different quality in an online auction with budget and time constraints. A multi-armed bandit engine may be provided for sampling new advertisements by allocating advertisements for web page placements of different quality and optimizing payments to maximize the welfare of the advertisers while remaining within advertiser's budget and time constraints. Advertisers may report their private information including arrival time, departure time, value per click, and budget. And the multi-armed bandit mechanism may approximate the maximal welfare that may be achieved under budget and time constraints by bounding the possible gain from any possible lie an advertiser might submit in reporting private information. Advertisers departing from the online auction may be charged using a payment method that may provide truthful guarantees on budget, arrivals, departures, and valuations for a budget-constrained online auction.