Informational Confidence Bounds for Self-Normalized Averages and Applications

Abstract

We present deviation bounds for self-normalized averages and applications to estimation with a random number of observations. The results rely on a peeling argument in exponential martingale techniques that represents an alternative to the method of mixture. The motivating examples of bandit problems and context tree estimation are detailed.

References in corpus (5)

• On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems
• Kullback-Leibler upper confidence bounds for optimal sequential allocation
• Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws
• Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems
• Testing statistical hypothesis on random trees and applications to the protein classification problem

Cited by in corpus (13)

• Time-uniform, nonparametric, nonasymptotic confidence sequences
• Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
• Conservative Bandits
• Combinatorial semi-bandit with known covariance
• Regret Analysis of the Anytime Optimally Confident UCB Algorithm
• On the bias, risk and consistency of sample means in multi-armed bandits
• Martingale Methods for Sequential Estimation of Convex Functionals and Divergences
• Adaptive Monte Carlo via Bandit Allocation
• Online Learning of Optimally Diverse Rankings
• Optimal Confidence Regions for the Multinomial Parameter
• Non-Asymptotic Pure Exploration by Solving Games
• PAC Mode Estimation using PPR Martingale Confidence Sequences
• Learning Nearest Neighbor Graphs from Noisy Distance Samples