Risk-Sensitive Online Algorithms (Extended Abstract) |
Original Papers |
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$_\delta$-competitive ratio ($\delta$-CR) using the conditional value-at-risk of an algorithm’s cost, which measures the expectation of the $(1-\delta)$-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 $\delta$-CR and algorithm varies significantly between problems: we prove that the optimal $\delta$-CR for continuous-time ski rental is $2-2^{-\Theta(\frac{1}{1-\delta})}$, 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 $\delta = 1 - \Theta(\frac{1}{\log B})$, after which the classic deterministic strategy is optimal. Similarly, one-max search exhibits a phase transition at $\delta = \frac{1}{2}$, after which the classic deterministic strategy is optimal; we also obtain an algorithm that is asymptotically optimal as $\delta \todown 0$ that arises as the solution to a delay differential equation. |
inproceedings |
Proceedings of Machine Learning Research |
PMLR |
2640-3498 |
christianson24a |
0 |
Risk-Sensitive Online Algorithms (Extended Abstract) |
1140 |
1141 |
1140-1141 |
1140 |
false |
Christianson, Nicolas and Sun, Bo and Low, Steven and Wierman, Adam |
| given |
family |
Nicolas |
Christianson |
|
|
|
| given |
family |
Adam |
Wierman |
|
|
2024-06-30 |
|
Proceedings of Thirty Seventh Conference on Learning Theory |
247 |
inproceedings |
|
|
|