# Risk-Sensitive Online Algorithms

arXiv: https://arxiv.org/abs/2405.09859 · HTML: https://mlsanity.com/paper/2405.09859/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2024.

## Built on by (most cited first, 2 of 2)

- [Smoothed Online Optimization for Target Tracking: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2509.05930/) (2025)
- [Rethinking Deep Alignment Through The Lens Of Incomplete Learning](https://mlsanity.com/paper/2511.12155/) (2025)

## Abstract (arXiv)

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.