欺骗性神谕下的序列预测

# 撒谎预言机下的序列预测
来源：https://arxiv.org/html/2608.14102  
Puspabeethi Samanta Nikhil Karamchandani  
隶属：印度理工学院孟买分校电气工程系  
nikhilk@ee\.iitb\.ac\.in  
Jayakrishnan Nair  
隶属：印度理工学院孟买分校电气工程系  
jayakrishnan\.nair@ee\.iitb\.ac\.in  

###### 摘要  
我们研究m元序列的序列预测问题，其中在每个时刻 \(i\) 环境从m元字母表中选择一个结果，\(ii\) 学习者选择同一字母表上的概率分布（对环境生成的结果不知情），最后，\(iii\) 学习者产生一个依赖于分配给该结果的概率的代价。我们考虑的代价函数捕捉了在以下场景中预测环境所生成结果的复杂性：上述预测通过对撒谎预言机进行比较查询来完成。我们考虑随机和对抗两种环境，为这两种场景提出算法，并建立了它们的对数遗憾上界。  

## I 引言  
离散结果的序列预测是信息论、统计学和在线学习中的一个核心问题。在此设定中，每一轮 \(t\)，学习者预测一个有限字母表上的概率分布 \(p_t\)，然后观察一个结果 \(y_t\)。学习者的性能通过损失函数 \(l(p_t, y_t)\) 来衡量，不同的损失函数选择会导致不同的最优性概念和不同的算法行为。常见的例子包括对数损失、平方损失和绝对损失\[3 (https://arxiv.org/html/2608.14102#bib.bib6),13 (https://arxiv.org/html/2608.14102#bib.bib11),6 (https://arxiv.org/html/2608.14102#bib.bib10)\]。其中，对数损失 \(\log \frac{1}{p_t(y_t)}\) 因其与编码、赌博和通用预测的联系而扮演着特别重要的角色。特别是，累积对数损失对应于在分配概率下观测序列的码长，而在对数损失下最小化遗憾等价于在通用编码中实现最优冗余\[11 (https://arxiv.org/html/2608.14102#bib.bib4),9 (https://arxiv.org/html/2608.14102#bib.bib5),3 (https://arxiv.org/html/2608.14102#bib.bib6)\]。这种联系催生了大量关于序列概率分配的工作，包括经典的 \(\beta\) 添加族估计器（如拉普拉斯 (\(\beta=1\)) 和克里切夫斯基–特罗菲莫夫 (\(\beta=1/2\)) 估计器），这些估计器在对数损失下实现了最优或近优遗憾\[9 (https://arxiv.org/html/2608.14102#bib.bib5),3 (https://arxiv.org/html/2608.14102#bib.bib6),10 (https://arxiv.org/html/2608.14102#bib.bib7),2 (https://arxiv.org/html/2608.14102#bib.bib8)\]。  

对数损失的另一种解释源于经典的二十问题问题\[12 (https://arxiv.org/html/2608.14102#bib.bib13),4 (https://arxiv.org/html/2608.14102#bib.bib12)\]，这是一个通过查询预言机来识别未知符号的序列博弈。在无噪声设定中，如果一个符号 \(x\) 从分布 \(\mu\) 中抽取，那么识别 \(x\) 所需的“是/否”查询数量（忽略低阶项）与 \(\log(1/\mu(x))\) 成比例，而查询的期望数量由熵 \(H(\mu)\) 给出。当底层分布先验未知时，这在最优查询策略与对数损失下的序列概率分配之间建立了直接联系\[1 (https://arxiv.org/html/2608.14102#bib.bib2)\]。  

该问题的一个自然扩展，称为雷尼–乌拉姆游戏\[14 (https://arxiv.org/html/2608.14102#bib.bib9)\]，允许预言机撒有限次谎。在这种设定下，谎言的存在增加了识别未知符号所需的查询复杂度。最近的结果显示，允许最多 \(k\) 次谎言会在经典 \(\log(1/\mu(x))\) 项之外，引入大约 \(k \log \log(1/\mu(x))\) 的额外开销\[5 (https://arxiv.org/html/2608.14102#bib.bib1),14 (https://arxiv.org/html/2608.14102#bib.bib9)\]。  

基于这种联系，我们考虑以下扰动损失函数。在每一轮 \(t\)，学习者在预测分布 \(p_t\) 并观察结果 \(y_t\) 后，产生的损失为  
\(l(p_t, y_t) = \log \frac{1}{p_t(y_t)} + k \log \log \left( \frac{1}{p_t(y_t)} + c \right)\)，  
其中 \(k \geq 0\) 表示允许的谎言次数，\(c \geq 1\) 是一个常数。第一项对应于经典的对数损失，第二项捕捉了不可靠预言机响应引起的额外复杂性。我们研究在此扰动损失下的序列概率分配，分别考虑随机和对抗两种设定。  

在随机设定中，结果独立同分布地来自未知分布 \(p\)，性能通过期望遗憾（即相对于每一轮预测真实分布 \(p\) 的累积损失）来衡量。我们首先分析 \(\beta\) 添加族估计器在此损失下的性能，如前所述，该估计器在通用预测理论中至关重要，并在对数损失下实现了最优或近优遗憾\[9 (https://arxiv.org/html/2608.14102#bib.bib5),3 (https://arxiv.org/html/2608.14102#bib.bib6),10 (https://arxiv.org/html/2608.14102#bib.bib7),2 (https://arxiv.org/html/2608.14102#bib.bib8)\]。然后我们转向对抗设定，其中结果序列是任意的，性能相对于事后最佳固定分布来衡量。为了解决这一设定，我们考虑指数加权在线优化器 (EWOO)\[7 (https://arxiv.org/html/2608.14102#bib.bib3),3 (https://arxiv.org/html/2608.14102#bib.bib6)\]。我们证明扰动损失函数是指数凹的，这使我们能够应用EWOO并获得遗憾保证。最后，我们通过数值实验来补充我们的理论分析，这些实验阐明了所提损失和算法的行为，并突出了遗憾对时间范围 \(n\)、参数 \(k\) 以及估计器选择的依赖关系。  

## II 问题建模  
### II-A 一般模型  
我们考虑m元序列的序列预测问题。更具体地说，在每一轮 \(t \in [n] := \{1, 2, \ldots, n\}\)，环境生成一个符号 \(y_t \in \mathcal{Y} = \{1, 2, \ldots, m\}\)，这对学习者来说是先验未知的。基于先前结果的历史 \(y_1, y_2, \ldots, y_{t-1}\)，学习者被要求分配一个概率质量函数 \(p_t = (p_t(1), p_t(2), \ldots, p_t(m))\) 到 \(\mathcal{Y}\) 上。然后结果 \(y_t\) 被揭示给学习者，学习者产生损失 \(l(p_t, y_t)\)。这标志着学习问题一轮的完成，随后轮次的过程类似地继续。  

### II-B 随机遗憾  
在随机设定中，环境按照未知（对学习者先验）的固定分布 \(p\) 独立同分布地生成 \(y_t\)，对所有 \(t \in [n]\)。最后，学习者的性能通过累积期望遗憾来衡量，其定义为：  
\[
R_n^S \triangleq \sum_{t=1}^{n} \mathbb{E}_{y_t \sim p} \mathbb{E}_{y_{\tau} |_{\tau=1}^{t-1}} \left[ l(p_t, y_t) - l(p, y_t) \right] = \sum_{t=1}^{n} \sum_{j=1}^{m} p(j) \mathbb{E}_{y_{\tau} |_{\tau=1}^{t-1}} \left[ l(p_t, j) - l(p, j) \right]
\]  

### II-C 最坏情况遗憾  
在此设定中，结果序列 \(y_1, y_2, \ldots, y_n\) 是任意的（甚至可以是敌对确定的）。对于每个这样的序列，学习者的遗憾通过其累积损失与事后“最佳”分布损失之间的差距来衡量，即：  
\[
R_n^A(y_t |_{t=1}^{n}) \triangleq \sum_{t=1}^{n} l(p_t, y_t) - \underset{p \in \mathcal{D}}{\text{min}} \sum_{t=1}^{n} l(p, y_t) = \sum_{t=1}^{n} \left[ l(p_t, y_t) - l(p^*(y_t |_{t=1}^{n}), y_t) \right]
\]  
其中 \(\mathcal{D}\) 表示所有m元概率分布的集合，\(p^*(y_t |_{t=1}^{n}) = \underset{p \in \mathcal{D}}{\text{arg min}} \sum_{t=1}^{n} l(p, y_t)\)。学习者的总体遗憾然后通过取所有可能序列在 \(\mathcal{Y}^n\) 上的上确界来定义，如下详述：  
\[
R_n^A \triangleq \underset{y_t |_{t=1}^{n} \in \mathcal{Y}^n}{\text{sup}} R_n^A(y_t |_{t=1}^{n}) = \underset{y_t |_{t=1}^{n} \in \mathcal{Y}^n}{\text{sup}} \sum_{t=1}^{n} \left[ l(p_t, y_t) - l(p^*(y_t |_{t=1}^{n}), y_t) \right]
\]  

### II-D 损失函数  
如引言中强调，本文我们关注一个特定的损失函数，它受撒谎猜测问题\[5 (https://arxiv.org/html/2608.14102#bib.bib1)\]的启发，对于任何 \(p \in \mathcal{D}, y \in [m]\)，给出如下：  
\[
l(p, y) := f(p(y)) = \log \frac{1}{p(y)} + k \log \log \left( \frac{1}{p(y)} + c \right)
\]  
其中 \(k \geq 0, c \geq 1\) 是常数；\(k\) 是整数，\(c\) 是实数。注意当 \(k=0\) 时，这与广泛研究的对数损失函数一致\[11 (https://arxiv.org/html/2608.14102#bib.bib4)\]。  

## III 随机设定  
对于此设定，我们考虑流行的 \(\beta\) 添加估计器\[9 (https://arxiv.org/html/2608.14102#bib.bib5),3 (https://arxiv.org/html/2608.14102#bib.bib6)\]，它与对称狄利克雷先验下的贝叶斯后验分布一致。它也可以表示为均匀先验和经验估计的凸组合，如下所示：  
\[
p_t(j) = \frac{\beta + N_{j, t-1}}{t-1 + m\beta} = (1 - \lambda_t) \frac{1}{m} + \lambda_t \bar{p}_{j, t-1}, \quad \forall j \in [m]
\]  
其中 \(\lambda_t = 1 - \frac{m\beta}{t-1 + m\beta}\)，\(\bar{p}_{j, t-1} = \frac{N_{j, t-1}}{t-1}\)，\(N_{j, t-1}\) 表示符号 \(j\) 在 \(y_1, \ldots, y_{t-1}\) 中的出现次数。  

以下定理给出了在随机设定下，\(\beta\) 添加估计器在 \(n\) 轮中产生的累积遗憾 \(R_n^S\) 的对数上界。  

###### 定理 1  
对于m元序列 \((y_1, \cdots, y_n) \in \mathcal{Y}^n\) 的序列预测问题，其中每个符号 \(y_t, t \in [n]\) 按固定分布 \(p\) 独立同分布地生成，且损失函数如 (7) (https://arxiv.org/html/2608.14102#S2.E7) 所述，则 \(\beta\) 添加估计器产生的累积遗憾为对数级别，具体为：  
\[
R_n^S \leq \left( m\beta \log m + \frac{4m}{\ln 2} + \frac{k}{(\ln 2) l} \left( m^2 \beta + \frac{8m}{p_{\min}} \right) \right) \ln\left( \frac{n-1}{\lfloor m\beta \rfloor} + 1 \right) + O(1)
\]  
其中 \(l = \left( \frac{1}{p_{\max}} + c \right) \ln\left( \frac{1}{p_{\max}} + c \right)\)，\(p_{\max} = \max_{j \in \mathcal{Y}} p(j)\)，且 \(p_{\min} = \min_{j \in \mathcal{Y}} p(j)\)。  

定理 1 的证明记录在第七章A节中。注意该界随时间范围 \(n\) 对数增长，随底层分布的支撑大小 \(m\) 线性增长。这与广泛研究的对数损失函数的遗憾行为相同\[11 (https://arxiv.org/html/2608.14102#bib.bib4),9 (https://arxiv.org/html/2608.14102#bib.bib5)\]，对应于此处研究的损失模型中的 \(k=0\)。另外，注意遗憾随 \(k\) 线性增长，\(k\) 表示第I章 (https://arxiv.org/html/2608.14102#S1) 中提到的查询模型中允许的谎言次数，这构成了此处研究的损失函数的动机。  

## IV 对抗设定  
本节，我们考虑结果序列任意的设定。对于此设定，我们采用一种称为*指数加权在线优化器 (EWOO)*的估计器，已知当损失函数是指数凹的时候，它可以实现 \(O(\log n)\) 的累积遗憾\[7 (https://arxiv.org/html/2608.14102#bib.bib3)\]。该估计器通过对单纯形上的加权平均来生成概率估计，其中权重基于事后累积损失的指数分配。  

我们首先证明第II-D节给出的损失函数 \(f(p(y_t))\) 不仅是 \(p(y_t) \in (0,1]\) 上的凸函数，而且对于合适的 \(\alpha\) 选择，是 \(\alpha\)-指数凹函数。  

###### 定义 1  
一个凸函数 \(f: \mathcal{X} \rightarrow \mathcal{R}\) 在 \(\mathcal{X} \subseteq \mathcal{R}\) 上是 \(\alpha\)-指数凹的，如果函数 \(g: \mathcal{X} \rightarrow \mathcal{R}\) 定义为 \(g(x) = e^{-\alpha f(x)}\) 是凹的。  

###### 定理 2  
令 \(k \geq 0\)，\(c \geq 1\)。则凸函数 \(f: (0,1] \rightarrow \mathcal{R}\) 定义为 \(f(x) = \log \frac{1}{x} + k \log \log \left( \frac{1}{x} + c \right)\) 是 \(\frac{a^*}{\log_2 e}\)-指数凹的，其中  
\[
a^* := \underset{x \in (0,1]}{\text{min}} \frac{(1+xc)^2 (\ln(\frac{1}{x}+c))^2 + k(1+2xc) \ln(\frac{1}{x}+c) - k}{(1+xc)^2 (\ln(\frac{1}{x}+c))^2 + 2k(1+xc) \ln(\frac{1}{x}+c) + k^2}.
\]  
或者，可以得到一个更简单的结果形式，即 \(f(x)\) 是 \(\frac{a^{**}}{\log_2 e}\)-指数凹的，其中  
\[
a^{**} = 1 - \frac{k}{\gamma(c) + k} - \frac{k}{(\gamma(c) + k)^2}
\]  
其中 \(\gamma(c) = \min_{x \in (0,1]} \left[ (1+xc) \ln\left( \frac{1}{x} + c \right) \right]\)。  

定理 2 (https://arxiv.org/html/2608.14102#Thmtheorem2) 的证明可在附录中找到。  

算法 1 (https://arxiv.org/html/2608.14102#alg1) 描述了 EWOO 方案，该方案在每个时间步输出一个概率分配，由所有m元离散分布上的加权混合给出，其中权重与它们事后累积损失的指数函数成正比。