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 B), after which the classic deterministic strategy is optimal. Similarly, one-max search exhibits a phase transition at = 12, 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.