Combining e-values using demi-supermartingales

Abstract

We present a new method for combining e-variables through demi-supermartingales, which settles an old conjecture in the literature on nonparametric mean testing. It also provides an explicit concentration bound for a certain Kullback--Leibler-type statistic arising in the stochastic multi-armed bandit literature. All of these combination results hold for independent e-variables as well as for the class of co-valid e-variables, whose dependence structure lies somewhere between independence and sequential validity. The results are further generalized to compound e-variables. The proofs proceed by analyzing elementary symmetric polynomials and their behavior as nonnegative demi-supermartingales.