A stochastic multi-armed bandit approach to nonparametric H∞-norm estimation

We study the problem of estimating the largest gain of an unknown linear and time-invariant filter, which is also known as the H-infinity norm of the system. By using ideas from the stochastic multi-armed bandit framework, we present a new algorithm that sequentially designs an input signal in order to estimate this quantity by means of input-output data. The algorithm is shown empirically to beat an asymptotically optimal method, known as Thompson Sampling, in the sense of its cumulative regret function. Finally, for a general class of algorithms, a lower bound on the performance of finding the H-infinity norm is derived.