Risk-Sensitive Online Algorithms

We study the design of risk-sensitive online algorithms, in which risk measures are used in the competitive analysis of randomized online algorithms. We introduce the CVaRδ-competitive ratio (δ-CR) using the conditional value-at-risk of an algorithm's cost, which measures the expectation of the (1-δ)-fraction of worst outcomes against the offline optimal cost, and use this measure to study three online optimization problems: continuous-time ski rental, discrete-time ski rental, and one-max search. The structure of the optimal δ-CR and algorithm varies significantly between problems: we prove that the optimal δ-CR for continuous-time ski rental is 2-2^-Theta(frac11-δ), obtained by an algorithm described by a delay differential equation. In contrast, in discrete-time ski rental with buying cost B, there is an abrupt phase transition at δ = 1 - Theta(frac1log B), after which the classic deterministic strategy is optimal. Similarly, one-max search exhibits a phase transition at δ = frac12, after which the classic deterministic strategy is optimal; we also obtain an algorithm that is asymptotically optimal as δ downarrow 0 that arises as the solution to a delay differential equation.