证明了一种经典混合方法在无界数据下可实现几乎必然的双对数后悔界。
Eventually LIL Regret: Almost Sure $\ln\ln T$ Regret for a sub-Gaussian Mixture on Unbounded Data
- 基于维尔事件构造路径依赖的确定性后悔上界，适用于无界数据。
- 在概率为1的事件上，后悔值最终被控制在$\ln \ln V_T$量级。
- 连接了对抗学习与博弈统计，适合关注理论边界的研究者。
我们证明了罗宾斯提出的一种经典子高斯混合方法，在随机设定下实际上满足路径无关（确定性）的后悔上界。对于自然的“维尔事件”$\mathcal E_α$中的每一条路径，时间$T$前的后悔上界为$\ln^2(1/α)/V_T + \ln (1/α) + \ln \ln V_T$，其中$V_T$是非负、非递减的累积方差过程（当$V_T \geq \ln(1/α)$时，上界简化为$\ln(1/α) + \ln \ln V_T$）。若数据为随机生成，则在广泛分布类（如子高斯、对称、方差有界等）下，$\mathcal E_α$的概率至少为$1-α$。事实上，我们在概率为1的维尔事件$\mathcal E_0$上表明，每条路径的后悔值最终被控制在$\ln \ln V_T$量级（常数倍内）。该工作揭示了条件后悔界如何在对抗在线学习（通常处理有界数据）与博弈统计（可处理无界数据但需随机假设）之间架起桥梁，说明条件后悔界是连接随机与对抗投注的关键工具。
原文摘要 · Abstract (English)
We prove that a classic sub-Gaussian mixture proposed by Robbins in a stochastic setting actually satisfies a path-wise (deterministic) regret bound. For every path in a natural ``Ville event'' $\mathcal E_α$, this regret till time $T$ is bounded by $\ln^2(1/α)/V_T + \ln (1/α) + \ln \ln V_T$ up to universal constants, where $V_T$ is a nonnegative, nondecreasing, cumulative variance process. (The bound reduces to $\ln(1/α) + \ln \ln V_T$ if $V_T \geq \ln(1/α)$.) If the data were stochastic, then one can show that $\mathcal E_α$ has probability at least $1-α$ under a wide class of distributions (eg: sub-Gaussian, symmetric, variance-bounded, etc.). In fact, we show that on the Ville event $\mathcal E_0$ of probability one, the regret on every path in $\mathcal E_0$ is eventually bounded by $\ln \ln V_T$ (up to constants). We explain how this work helps bridge the world of adversarial online learning (which usually deals with regret bounds for bounded data), with game-theoretic statistics (which can handle unbounded data, albeit using stochastic assumptions). In short, conditional regret bounds serve as a bridge between stochastic and adversarial betting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。