  Optimal regret bounds for Multi-Armed Bandit problems are now well
documented. They can be classified into two categories based on the growth rate
with respect to the time horizon $T$: (i) small, distribution-dependent, bounds
of order of magnitude $\ln(T)$ and (ii) robust, distribution-free, bounds of
order of magnitude $\sqrt{T}$. The Bandits with Knapsacks model, an extension
to the framework allowing to model resource consumption, lacks this clear-cut
distinction. While several algorithms have been shown to achieve asymptotically
optimal distribution-free bounds on regret, there has been little progress
toward the development of small distribution-dependent regret bounds. We
partially bridge the gap by designing a general-purpose algorithm with
distribution-dependent regret bounds that are logarithmic in the initial
endowments of resources in several important cases that cover many practical
applications, including dynamic pricing with limited supply, bid optimization
in online advertisement auctions, and dynamic procurement.
