Risk-Sensitive Online Algorithms

We initiate the study 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-Θ(1/1-δ), 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 - Θ(1/log B), after which the classic deterministic strategy is optimal. Similarly, one-max search exhibits a phase transition at δ = 1/2, after which the classic deterministic strategy is optimal; we also obtain an algorithm that is asymptotically optimal as δ ↓ 0 that arises as the solution to a delay differential equation.