An improved system and method is provided for using sampling for scheduling advertisements in an online auction. A multi-armed bandit engine may be provided for learning the valuation of advertisements through sampling in an online advertising auction. To do so, the multi-armed bandit may schedule advertisements for web page placements in an online advertising auction to optimize payments for maximizing the welfare of the advertisers. An initial list of advertisements may be created that is ordered by expected payment, and an optimal subset of advertisements may be determined from the initial list of advertisements for web page placements by iterative sampling. A web page placement may then be determined and allocated for each advertisement in the optimal subset in order to maximize revenue. And a charge may be calculated for each advertisement allocated the web page placement and sampled in the online advertising auction.