  Value-at-risk (VaR) is an established measure to assess risks in critical
real-world applications with random environmental factors. This paper presents
a novel VaR upper confidence bound (V-UCB) algorithm for maximizing the VaR of
a black-box objective function with the first no-regret guarantee. To realize
this, we first derive a confidence bound of VaR and then prove the existence of
values of the environmental random variable (to be selected to achieve no
regret) such that the confidence bound of VaR lies within that of the objective
function evaluated at such values. Our V-UCB algorithm empirically demonstrates
state-of-the-art performance in optimizing synthetic benchmark functions, a
portfolio optimization problem, and a simulated robot task.
