On Confidence Sequences for Bounded Random Processes via Universal Gambling Strategies
Lists
Only you see this
Abstract
This paper considers the problem of constructing a confidence sequence, which is a sequence of confidence intervals that hold uniformly over time, for estimating the mean of bounded real-valued random processes. This paper revisits the gambling-based approach established in the recent literature from a natural two-horse race perspective, and demonstrates new properties of the resulting algorithm induced by Cover (1991)’s universal portfolio. The main result of this paper is a new algorithm based on a mixture of lower bounds, which closely approximates the performance of Cover’s universal portfolio with constant per-round time complexity. A higher-order generalization of a lower bound on a logarithmic function in (Fan et al., 2015), which is developed as a key technique for the proposed algorithm, may be of independent interest.
BibTeX
@article{ryu2024confidence,
author = {J. Jon Ryu and Alankrita Bhatt},
title = {{On Confidence Sequences for Bounded Random Processes via Universal Gambling Strategies}},
journal = {IEEE Trans. Information Theory},
year = {2024},
url = {https://openreview.net/forum?id=tgFxOPfgXI},
}Loading related content...