arXiv:2604.20172cs.LGmath.ST2026-04

新策略在随机数据上实现近乎确定的双对数悔悟,同时保护对抗性数据。

Cover meets Robbins while Betting on Bounded Data: $\ln n$ Regret and Almost Sure $\ln\ln n$ Regret

  • 融合Robbins与Cover思想,构造混合投注策略。
  • 几乎所有路径下悔悟为O(ln ln n),仅极少数路径为O(ln n)。
  • 适合需自适应应对随机与对抗数据的场景。

考虑在[0,1]区间内对数据序列进行投注,允许的投注策略在条件均值m₀∈(0,1)时是公平的。Cover的通用投资组合算法相比事后最优常数投注,最坏情况悔悟为O(ln n),且该界在对抗生成数据下不可改进。本文提出一种新颖的混合投注策略,结合Robbins与Cover的洞见:在几乎所有路径上(若每个条件均值等于m₀且内在方差趋于∞,则测度为1),悔悟为O(ln ln n);而在补集路径上(测度为零),悔悟为O(log n)。这是首个指出通过对冲两种截然不同策略以实现对随机数据的自适应与对抗数据的防护的论文。与Agrawal和Ramdas [2026]在无界子高斯混合下的结果对比,后者最坏悔悟必无界,但类似对冲可同时实现最优投注增长率与几乎确定的ln ln n悔悟。此外,该策略展现出尖锐的博弈论上迭代对数律,类似于Shafer和Vovk [2005]。

原文摘要 · Abstract (English)

Consider betting against a sequence of data in $[0,1]$, where one is allowed to make any bet that is fair if the data have a conditional mean $m_0 \in (0,1)$. Cover's universal portfolio algorithm delivers a worst-case regret of $O(\ln n)$ compared to the best constant bet in hindsight, and this bound is unimprovable against adversarially generated data. In this work, we present a novel mixture betting strategy that combines insights from Robbins and Cover, and exhibits a different behavior: it eventually produces a regret of $O(\ln \ln n)$ on almost all paths (a measure-one set of paths if each conditional mean equals $m_0$ and intrinsic variance increases to $\infty$), but has an $O(\log n)$ regret on the complement (a measure zero set of paths). Our paper appears to be the first to point out the value in hedging two very different strategies to achieve a best-of-both-worlds adaptivity to stochastic data and protection against adversarial data. We contrast our results to those in Agrawal and Ramdas [2026] for a sub-Gaussian mixture on unbounded data: their worst-case regret has to be unbounded, but a similar hedging delivers both an optimal betting growth-rate and an almost sure $\ln\ln n$ regret on stochastic data. Finally, our strategy witnesses a sharp game-theoretic upper law of the iterated logarithm, analogous to Shafer and Vovk [2005].

在线学习后悔最小化博弈论

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。