Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood
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.
Characterizes the minimax regret of sequential probability assignment with contexts (log loss, arbitrary hypothesis classes, multiary labels) via a worst-case contextual Shtarkov sum, derives the minimax-optimal cNML strategy, and gives a short proof of a sequential-entropy regret bound.
Problem
Minimax regret for online learning with logarithmic loss over arbitrary (possibly nonparametric) contextual hypothesis classes; sequential l_infinity entropy was shown not to characterize it.
Approach
Introduces the contextual Shtarkov sum (Shtarkov sum over a context tree) and shows the worst-case log of it equals minimax regret, with no regularity assumptions; the minimax optimal strategy cNML is the NML distribution using contextual Shtarkov sums with prefix.
Key results
- Minimax regret equals the worst-case log contextual Shtarkov sum over context trees, for arbitrary hypothesis classes and finite label sets (no regularity assumption).
- cNML is shown to be a minimax optimal algorithm; in the context-free case it reduces to NML.
- New regret bound R_T(F) <= inf_alpha [T log(1+2alpha) + sequential l_inf entropy], which unifies and sharpens prior bounds; a Omega(sqrt(T)) lower bound for linear class is shown, with sequential covering failing to characterize minimax regret (T^{2/3} for absolute linear class).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the worst-case contextual Shtarkov sum to characterize regret | Sequential probability assignment with contexts · Sequential probability assignment with contexts | minimax regret characterization | Helped |
| use contextual Normalized Maximum Likelihood (cNML) | Sequential probability assignment with contexts · Sequential probability assignment with contexts | minimax regret | Helped |
| use sequential \ell_{\infty} entropy in the new regret bound | Sequential probability assignment with contexts · Binary labels, non-sequential experts | regret upper bound | Helped |
| use the sequential entropy upper bound instead of the cited state-of-the-art bounds | Sequential probability assignment with contexts · Binary labels, non-sequential experts | regret upper bound | Helped |
| use sequential \ell_{\infty} covering number bounds for both classes | Sequential covering-number regret analysis · Linear class versus absolute linear class | minimax regret rate characterization: \tilde O(\sqrt{T}) versus \tilde\Theta(T^{2/3}) | Mixed |
Surprising findings
- Sequential l_infinity covering numbers are of the same order for linear and absolute-linear classes, yet minimax regrets differ (sqrt(T) vs T^{2/3}), so covering numbers alone do not characterize minimax regret.
Limitations
- cNML is computationally inefficient in general, requiring contextual Shtarkov sums with prefix.
- Results are nonconstructive for the minimax regret characterization and the analysis is theoretical only.
- Infinite label sets are left to future work and require further regularity conditions.
Experimental setup
Metrics: minimax regret log contextual Shtarkov sum
Baselines: sequential l_infinity covering bound (Bilodeau et al., 2020) global sequential covering bound (Wu et al., 2023)
Builds on: Shtarkov sum / NML (Shtarkov 1987) Rakhlin, Sridharan, Tewari 2010 sequential Rademacher complexity Bilodeau et al. 2020 sequential entropy bound Wu et al. 2023 global sequential covering bound
Closest papers by meaning
- Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm (NeurIPS 2022 · similarity 0.92)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.89)
- Eluder-based Regret for Stochastic Contextual MDPs (ICML 2024 · similarity 0.88)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · similarity 0.87)
- Contextual Bandits for Unbounded Context Distributions (ICML 2025 · similarity 0.87)
- Nearly Minimax Optimal Regret for Multinomial Logistic Bandit (NeurIPS 2024 · similarity 0.87)
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.