Risk-Sensitive Online Algorithms (Extended Abstract)

Nicolas Christianson; Bo Sun; Steven Low; Adam Wierman

Risk-Sensitive Online Algorithms (Extended Abstract)

Nicolas Christianson, Bo Sun, Steven Low, Adam Wierman

Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1140-1141, 2024.

Abstract

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.

Cite this Paper

BibTeX


@InProceedings{pmlr-v247-christianson24a,
  title = 	 {Risk-Sensitive Online Algorithms (Extended Abstract)},
  author =       {Christianson, Nicolas and Sun, Bo and Low, Steven and Wierman, Adam},
  booktitle = 	 {Proceedings of Thirty Seventh Conference on Learning Theory},
  pages = 	 {1140--1141},
  year = 	 {2024},
  editor = 	 {Agrawal, Shipra and Roth, Aaron},
  volume = 	 {247},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {30 Jun--03 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v247/christianson24a/christianson24a.pdf},
  url = 	 {https://proceedings.mlr.press/v247/christianson24a.html},
  abstract = 	 {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.}
}

Endnote

%0 Conference Paper
%T Risk-Sensitive Online Algorithms (Extended Abstract)
%A Nicolas Christianson
%A Bo Sun
%A Steven Low
%A Adam Wierman
%B Proceedings of Thirty Seventh Conference on Learning Theory
%C Proceedings of Machine Learning Research
%D 2024
%E Shipra Agrawal
%E Aaron Roth	
%F pmlr-v247-christianson24a
%I PMLR
%P 1140--1141
%U https://proceedings.mlr.press/v247/christianson24a.html
%V 247
%X 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.

APA


Christianson, N., Sun, B., Low, S. & Wierman, A.. (2024). Risk-Sensitive Online Algorithms (Extended Abstract). Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:1140-1141 Available from https://proceedings.mlr.press/v247/christianson24a.html.

Related Material

Download PDF