Controlling Tail Risk in Online Ski-Rental

Date:

A common principle in decision theory is to look for procedures with good expected performance. For example, statisticians look for estimators with low mean-squared error, and operations researchers look for policies which maximize expected utility or minimize expected cost. However, procedures derived from this principle sometimes exhibit undesirable properties, such as exhibiting a higher variance in their performance. This talk focuses on the case of the online ski-rental problem, a fundamental primitive in the study of online algorithms from computer science, which encapsulates the trade-off between acquiring limited access of a resource for a small cost (renting) and that of incurring a large cost (buying) in exchange for less restricted access. The aim is to find algorithms with a small expected competitive ratio, which measures the ratio of the expected cost of the algorithm to that of the hindsight optimal cost. This problem admits a 2-competitive deterministic algorithm, and a simple randomized algorithm that is e/(e-1)-competitive in expectation. The randomized algorithm, while optimal in expectation, has a large variance in its performance: it has more than a 37% chance of the competitive ratio exceeding 2.

We ask what happens to the optimal solution if we insist that the tail risk, i.e., the chance of the competitive ratio exceeding a specific value, is bounded by a given constant. We find that this additional modification significantly changes the structure of the optimal solution. The probability of purchasing skis on a given day becomes non-monotone, discontinuous, and arbitrarily large (for sufficiently small tail risk and large purchase cost).