Research map / Probabilistic and scientific modeling / Variational and generative sampling
Gambling-Based Confidence Sequences for Bounded Random Vectors
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends the coin-toss/two-horse-race gambling framework for bounded scalar CSs to categorical and probability-vector-valued observations, using Krichevsky–Trofimov and Cover's universal portfolio mixtures, and shows the KT CS for sampling without replacement is provably tighter than the posterior-prior ratio CS.
Problem
Constructing tight, time-uniform confidence sequences for means of bounded vector-valued (categorical / probability-vector) stochastic processes, where existing gambling CS methods are scalar-only.
Approach
Treat a categorical or probability-vector observation as the odds vector of a K-horse (continuous) horse race, so that any subfair odds sequence gives a supermartingale wealth; mix constant-bettor wealths with a Dirichlet prior (KT mixture or Cover's universal portfolio) to get tight, convex, always non-vacuous CSs.
Key results
- For sampling without replacement, KT CS is provably always at least as large a wealth as the PPR CS (tighter with probability 1), and on average decides color rank about 26% faster than PPR CS in the 1000-ball simulation.
- Simulations show KT(K) gains over Bonferroni/mixture aggregations increase with dimension K, though baselines can win in long runs.
- UP CS gives much tighter sets than KT(K) for concentrated Dirichlet observations, but its computation costs O(T^(K-1)) per round.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the KT confidence sequence instead of the PPR confidence sequence | Sampling without replacement for categorical data · Finite population of 1000 balls | stopping time: 26% faster | Helped |
| Use multivariate KT(K) instead of aggregated KT(2) confidence sequences | Categorical data · Categorical simulations with K∈{3,4,5} | relative confidence-set volume | Mixed |
| Use KT(K) instead of Sanov confidence sets | Categorical data · Categorical simulations | confidence-set tightness | Helped |
| Use KT confidence sequences instead of the improved non-time-uniform bound | Categorical data · Categorical simulations after the improved bound kicks in | confidence-set tightness | No clear effect |
| Use CP(2)+Bonferroni intervals instead of KT confidence sequences | Categorical data · Categorical simulations | confidence-set tightness | Hurt |
| Use Sison–Glaz instead of KT confidence sequences | Categorical data · Categorical simulations | coverage | Hurt |
| Use multivariate UP(K) instead of KT(K) | Probability-vector-valued observations · Dirichlet observations with K∈{3,4} | confidence-set tightness | Helped |
| Use multivariate gambling confidence sequences instead of Bonferroni correction or averaged-wealth baselines | Categorical and probability-vector-valued observations · Simulations | confidence-set tightness | Helped |
Surprising findings
- Bonferroni-style and mixture-based baselines outperform the multivariate KT CS in the long run.
- The Sison-Glaz method yields very small sets but its empirical coverage falls well below the nominal level.
Limitations
- UP confidence sets are implicit and computationally prohibitive in high dimension (O(T^K)).
- Only bounded vector observations are covered; extension to kernel or linear bandits left open.
- Multivariate KT CS is looser than baselines in the long run.
Experimental setup
Metrics: relative volume of confidence set per-time-step coverage stopping time ratio
Baselines: Bonferroni-aggregated KT(2) mixture-aggregated KT(2) Sanov-based bounds Clopper-Pearson with Bonferroni Sison-Glaz posterior-prior ratio CS
Builds on: Cover's universal portfolio coin-toss betting CS framework Krichevsky-Trofimov estimator posterior-prior ratio CS for sampling without replacement
Closest papers by meaning
- On the Tightness and Computational Tractability of Higher-Dimensional Confidence Sequences (NeurIPS 2026 · similarity 0.89)
- STAR-Bets: Sequential TArget-Recalculating Bets for Tighter Confidence Intervals (NeurIPS 2025 · similarity 0.87)
- Asymptotically Log-Optimal Bayes-Assisted Confidence Sequences for Bounded Means (NeurIPS 2026 · similarity 0.84)
- A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits (NeurIPS 2024 · similarity 0.84)
- Peeking with PEAK: Sequential, Nonparametric Composite Hypothesis Tests for Means of Multiple Data Streams (ICML 2024 · similarity 0.82)
- Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization (ICML 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.