1. A computer system for an online advertising auction, comprising: a multi-armed bandit engine comprising: an input/output interface for receiving from each of a plurality of advertisers bidding for advertising slots in the online advertising auction: a bid for an advertising slot based on a keyword, wherein said bid comprises: an arrival time at the online advertising auction; a departure time at the online advertising auction; a budget that may not be exceeded between the arrival time and the departure time, wherein said budget may not be exceeded; and a value per click; a processor device for: selecting a subset of the plurality of the advertisers; allocating a plurality of web page placements of different quality to the subset of the advertisers for sampling the advertisements in the online advertising auction, wherein quality is defined as a probability of a click-through if an advertisement appears in said web page placement, wherein said quality is known; learning a valuation of the advertisements through sampling by scheduling the advertisements for web page placements of different quality in the online advertising auction to optimize payments for maximizing welfare of the advertisers; updating a click-through rate using a normalized number of clicks for each of the subset of the plurality of advertisers sampled in the online advertising auction; updating a payoff rate for receiving a click; updating a remaining budget of each of the subset of the plurality of advertisers; and charging the plurality of advertisers departing from the online advertising auction; and a storage device operably coupled to the multi-armed bandit engine for storing a plurality of budgets and a plurality of bids each associated with an advertisement allocated to web page placements in the online advertising auction with budget and time constraints; wherein the computer system selects a plurality of advertisers for sampling advertisements in the online advertising auction and samples advertisements for a subset of the plurality of advertisers.