Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio
A classic problem in statistics is the estimation of the expectation of random variables from samples. This gives rise to the tightly connected problems of deriving concentration inequalities and confidence sequences, that is confidence intervals that hold uniformly over time. Previous work has shown how to easily convert the regret guarantee of an online betting algorithm into a time-uniform concentration inequality. In this paper, we show that we can go even further: We show that the regret of universal portfolio algorithms give rise to new implicit time-uniform concentrations and state-of-the-art empirically calculated confidence sequences. In particular, our numerically obtained confidence sequences can never be vacuous, even with a single sample, and satisfy the law of iterated logarithm.
Code (2)
Similar Papers 제목 키워드 기반
Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures
We present improved algorithms with worst-case regret guarantees for the stochastic linear bandit problem. The widely used "optimism in the face of uncertainty" principle reduces a stochastic bandit problem to the constr…
Confidence Estimation via Sequential Likelihood Mixing
We present a universal framework for constructing confidence sets based on sequential likelihood mixing. Building upon classical results from sequential analysis, we provide a unifying perspective on several recent lines…
Bayesian InferenceVariational InferenceOptimal Regret of Bernoulli Bandits under Global Differential Privacy
As sequential learning algorithms are increasingly applied to real life, ensuring data privacy while maintaining their utilities emerges as a timely question. In this context, regret minimisation in stochastic bandits un…
Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits
We study the linear contextual bandit problem with finite action sets. When the problem dimension is $d$, the time horizon is $T$, and there are $n \leq 2^{d/2}$ candidate actions per time period, we (1) show that the mi…
Multi-Armed BanditsOn Learning to Rank Long Sequences with Contextual Bandits
Motivated by problems of learning to rank long item sequences, we introduce a variant of the cascading bandit model that considers flexible length sequences with varying rewards and losses. We formulate two generative mo…
Learning-To-RankMulti-Armed Bandits