Before revision:  With a small customizable parameter \epsilon which is the step size used in each iteration of the online algorithm, we have shown that our online algorithm achieves a long-term average revenue which is within O(\epsilon) of the optimal revenue and the overdraft level of this algorithm is upper-bounded by O(1/\epsilon) {1+\Delta} fraction of the revenue if \Delta is the percentage error in click-through rate estimation.
After revision:  Unlike prior models, we do not assume that the number of query arrivals is known. Due to the stochastic nature of the arrival process considered here, either temporary "free" service, i.e., service above the specified budget (which we call "overdraft") or under-utilization of the budget (which we call "underdraft") is unavoidable. We prove that our online algorithm achieves a long-term average revenue which is within O(\epsilon) of the optimal revenue and the overdraft level of this algorithm is upper-bounded by O(1/\epsilon) {1+\Delta} fraction of the revenue if \Delta is the percentage error in click-through rate estimation.