  Bin packing is an algorithmic problem that arises in diverse applications
such as remnant inventory systems, shipping logistics, and appointment
scheduling. In its simplest variant, a sequence of $T$ items (e.g., orders for
raw material, packages for delivery) is revealed one at a time, and each item
must be packed on arrival in an available bin (e.g., remnant pieces of raw
material in inventory, shipping containers). The sizes of items are i.i.d.
samples from an unknown distribution, but the sizes are known when the items
arrive. The goal is to minimize the number of non-empty bins (equivalently
waste, defined to be the total unused space in non-empty bins). This problem
has been extensively studied in the Operations Research and Theoretical
Computer Science communities, yet all existing heuristics either rely on
learning the distribution or exhibit $o(T)$ additive suboptimality compared to
the optimal offline algorithm only for certain classes of distributions (those
with sublinear optimal expected waste). In this paper, we propose a family of
algorithms which are the first truly distribution-oblivious algorithms for
stochastic bin packing, and achieve $\mathcal{O}(\sqrt{T})$ additive
suboptimality for all item size distributions. Our algorithms are inspired by
approximate interior-point algorithms for convex optimization. In addition to
regret guarantees for discrete i.i.d. sequences, we extend our results to
continuous item size distribution with bounded density, and also prove a family
of novel regret bounds for non-i.i.d. input sequences. To the best of our
knowledge these are the first such results for non-i.i.d. and
non-random-permutation input sequences for online stochastic packing.
