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:  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) , where \epsilon can be arbitrarily small. With a view towards practice, we also show that one can always operate strictly under the budget. Our algorithm also allows us to quantify the effect of errors in click-through rate estimation on the achieved revenue. We show that we lose at most \frac{\Delta{1+\Delta} fraction of the revenue if \Delta is the percentage error in click-through rate estimation.