$B \ge \Omega(\frac{m \log n}{\epsilon^3})$ and ${\ensuremath{\textrm{OPT}}}\ge \Omega(\frac{\pi_{\max} m \log n}{\epsilon})$, where $\pi_{\max}$ is the largest profit. In the second paper, the authors present an algorithm which obtains a solution of expected value at least $(1 - \epsilon) {\ensuremath{\textrm{OPT}}}$ under the weaker assumptions $B \ge \Omega\left(\frac{m}{\epsilon^2} \log \frac{n}{\epsilon}\right)$ or ${\ensuremath{\textrm{OPT}}}\ge \Omega\left(\frac{\pi_{\max} m^2}{\epsilon^2} \log \frac{n}{\epsilon}\right)$. One other way of stating this result is that the algorithm obtains a solution with competitive ratio $1 - O(\sqrt{\frac{m \log(n) \log B}{B}})$; notice that the guarantee degrades as $n$ increases. The current lower bound on $B$ to allow $(1 - \epsilon)$-competitive algorithms is $B \ge \frac{\log m}{\epsilon^2}$, also presented in [@agrawal]. We remark that these algorithms actually work for more general allocation problems, where a set of columns representing various options arrive at each step and the solution may choose at most one of the options.

Both of the above algorithms use a connection between solving the online LP and PAC-learning [@cucker] a linear classification of its columns, which was initiated by Devanur and Hayes [@DevanurHayes09] in the context of the AdWords problem. Here we further explore this connection and our improved bounds can be seen as a consequence of making the learning algorithm more 