Bundle Selling by Online Estimation of Valuation Functions

Abstract

We consider the problem of online selection of a bundle of items when the cost of each item changes arbitrarily from round to round and the valuation function is initially unknown and revealed only through the noisy values of selected bundles (the bandit feedback setting). We are interested in learning schemes that have a small regret compared to an agent who knows the true valuation function. Since there are exponentially many bundles, further assumptions on the valuation functions are needed. We make the assumption that the valuation function is supermodular and has non-linear interactions that are of low degree in a novel sense. We develop efficient learning algorithms that balance exploration and exploitation to achieve low regret in this setting.