Online Budget Allocation with Censored Semi-Bandit Feedback¶

会议: NeurIPS 2026
arXiv: 2508.05844
领域: 学习理论
关键词: 在线预算分配、截断半多臂老虎机、边际递减收益、乐观算法、极小化极大遗憾界

一句话总结¶

针对多任务在线预算分配难题，提出首个基于乐观原则的截断半多臂老虎机算法 UCBowski，在通用单调曲线上达到极小化极大最优的 $\widetilde{\mathcal{O}}(K\sqrt{T})$ 遗憾界与匹配下界，并在边际递减收益机制下免调参实现 $\mathcal{O}(\mathrm{poly}(K)(\log T)^2)$ 的多对数超快收敛率。

研究背景与动机¶

在现代众包平台薪酬激励、多平台自动化广告竞价（Autobidding）以及大语言模型分布式微调的算力分配等真实系统中，决策者在每一轮通常面临一个固定的单位总预算，并需要将其动态划分到 $K$ 个异质任务或子系统上。分配给任务的预算不仅直接影响该任务在当前轮次被成功完成的概率（通过单调不减的预算-成功曲线刻画），且只有当任务被成功触发并执行完毕时，平台才能观测到该任务的具体收益样本并获得回报。这类问题形式化了带有结构化动作空间的序列决策模型，构成了传统多臂老虎机与半多臂老虎机（Semi-Bandit）在连续单纯形空间上的重要推广。

然而，现有老虎机技术在此类问题上面临严重的结构性失效。首先，动作空间是连续的 $(K-1)$ 维单纯形 $\Delta_K$，简单的网格离散化方法（$\mathcal{X}$-armed bandits）受制于维度灾难，其覆盖数随维度呈指数爆炸，导致即使在 Lipschitz 连续假设下也只能得到极慢的非参数收敛率 $\mathcal{O}(T^{K/(K+1)})$；更为严重的是，预算-成功曲线并不一定满足全局 Lipschitz 光滑性。其次，若仅依赖汇总标量回报而退化为线性老虎机框架，算法将被迫舍弃各个任务实际是否完成的精细指示信息；理论上，这种信息贫瘠使得即使在极为良态的二任务凸曲面上，纯标量老虎机反馈算法的遗憾也无法突破 $\Omega(\sqrt{T})$ 的瓶颈。而在截断半多臂反馈（Censored Semi-Bandit Feedback）下，学习者能在任务成功时直接观测各分量奖励，反馈信息量与探索投入紧密耦合，但观测频率的随机性与内生相关性又阻碍了经典鞅集中不等式的直接套用。

针对这一挑战，本文深入探究了截断观测结构与任务凹性带来的内在正规化效应。核心 idea：通过构建自适应样本计数加权的经验均值置信上限（UCB）并在连续单纯形上直接求解凸规划选择分配，利用高预算高反馈的耦合自矫正效应打破离散化与线性老虎机下界，使边际递减收益下的瞬时遗憾向参数估计误差的二次方（Second-Order Regret）自退化，免调参达到多对数遗憾界。

方法详解¶

整体框架¶

在每一决策轮次 $t \ge 1$，学习者在概率单纯形 $\Delta_K = \{x \in [0,1]^K : \sum_{k=1}^K x_k = 1\}$ 上选取预算分配向量 $X_t = (X_{t,1}, \dots, X_{t,K})$。任务 $k$ 成功完成的概率由已知的单调不减曲线 $F_k(X_{t,k}) \in [0,1]$ 决定，记成功指示变量为 $B_{t,k}(X_{t,k}) \sim \mathrm{Bernoulli}(F_k(X_{t,k}))$。若任务 $k$ 成功，则生成均值为 $\mu_k \in [0,1]$ 的独立随机奖励 $G_{t,k} \in [0,1]$。算法在此轮获得的总期望回报为 $\langle \mu, F(X_t) \rangle$。环境向学习者反馈截断半多臂信号 $\mathscr{F}_t = \left(B_t(X_t), \left(B_{t,k}(X_{t,k}) G_{t,k}\right)_{k=1}^K\right)$，即仅当 $B_{t,k}=1$ 时，随机奖励 $G_{t,k}$ 才对学习者可见。

算法 UCBowski 维持针对每个任务的置信上限向量 $\mathrm{UCB}_{t-1}^\delta$。在每轮开始时，算法求解连续非线性规划 $\operatorname{argmax}_{x \in \Delta_K} \langle \mathrm{UCB}_{t-1}^\delta, F(x) \rangle$ 获取乐观最优分配 $X_t$；在环境揭示完成状态与完成任务的奖励后，算法仅累加成功触发的历史样本，并据此收缩该任务的置信区间宽度，完成自闭环策略更新。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["历史截断观测数据<br/>{B_{s,k}, B_{s,k} G_{s,k}}"] --> B["自适应有效样本计数与均值置信上界更新"]
    B --> C["连续单纯形乐观最优化分配求解"]
    C --> D["执行预算分配 X_t ∈ Δ_K<br/>任务独立触发 B_{t,k} ~ Bernoulli(F_k(X_{t,k}))"]
    D --> E["截断半多臂反馈观测<br/>揭示完成状态与对应奖励 G_{t,k}"]
    E -->|增量递推更新有效次数 N_{t,k}| A

关键设计¶

1. 自适应有效样本计数与均值置信上界更新：精准解耦观测频率与截断偏差 由于只有成功的任务才能被观测到其实际奖励值，若简单按照总轮次 $t$ 进行归一化，置信区间将严重偏离真实置信水平。为此，算法对每个任务 $k$ 显式跟踪成功完成次数 $N_{t,k} = \sum_{s=1}^t B_{s,k}(X_{s,k})$，并基于鞅停时理论证明了按成功时刻抽取的奖励子序列严格服从均值为 $\mu_k$ 的独立同分布。设目标失败概率为 $\delta = 1/(KT)^2$，对于任务 $k$，算法构建如下 UCB 估计器： $$\mathrm{UCB}_{t,k}^\delta = \frac{\sum_{s=1}^t B_{s,k}(X_{s,k}) G_{s,k}}{N_{t,k}} + \sqrt{\frac{\log(2/\delta)}{1 + N_{t,k}}}$$ 其中约定 $0/0 = 0$。该设计保证了在高概率良好事件 $\mathcal{E}_T^\delta$ 下，所有任务在任意时刻的真实均值均被其置信上限单侧控制：$\mu_k \le \mathrm{UCB}_{t,k}^\delta \le \mu_k + 2\sqrt{\frac{\log(2/\delta)}{1 + N_{t,k}}}$。这种依观测动态收缩的机制使得探索与利用能够针对异质任务的实际触发频率自动匹配精度。

2. 边际递减收益下的边界排斥与二阶瞬时遗憾退化：从参数误差到平方遗憾 当预算-成功曲线呈现边际递减效应（即 $F_k$ 具有凹性，且满足导数在原点发散 $\lim_{u \to 0^+} F_k'(u) = +\infty$）且任务均值 $\mu_k > 0$ 时，任何将预算压缩为 0 的动作都会在边际收益上遭到极大的梯度惩罚。算法通过一阶最优化条件证明了稳态最优解 $x^\star(\mu)$ 以及历史步长充分时的乐观解 $X_t$ 均被严格推离单纯形边界，统一存在远离原点的严格正下界 $u_{\inf} = D_{\min}^{-1}\left(\frac{2}{\mu_{\inf}} D_{\max}\left(\frac{1}{K}\right)\right) > 0$。在远离原点的紧致集 $[u_{\inf}, 1]$ 上，$F_k$ 具备强凹性与局部 Lipschitz 连续性。由于最优化目标函数 $\Phi_m(x) = \sum_{k=1}^K m_k F_k(x_k)$ 在单纯形内点的一阶投影梯度为零，参数偏差对最优动作诱发的瞬时遗憾由一阶线性项退化为二阶平方项： $$\Phi_\mu(x^\star(\mu)) - \Phi_\mu(x^\star(\mathrm{UCB}_{t-1}^\delta)) \le \frac{2 M(u_{\inf})^2}{\mu_{\inf} \alpha(u_{\inf})} \|\mu - \mathrm{UCB}_{t-1}^\delta\|_2^2$$ 这一二阶自稳定性质是算法跨越 $\sqrt{T}$ 屏障并达成 $(\log T)^2$ 超快收敛率的根本核心。

3. 椭圆势能式的反馈率鞅集中控制：实现与完备反馈对齐的高速累积 要将瞬时平方遗憾转化为多对数界，必须保证每个任务收集到足够多的观测，从而使置信半径以 $\mathcal{O}(1/t)$ 的速度衰减。通过引入 Bernstein 鞅差不等式，证明了高概率事件 $\mathcal{G}_T$：一旦分配给某任务的累积成功概率满足 $\sum_{s=1}^t F_k(X_{s,k}) \ge 100 (\log T)^2$，其实际成功次数必然满足 $N_{t,k} \ge \frac{1}{2} \sum_{s=1}^t F_k(X_{s,k})$。结合边界排斥性质，$F_k(X_{s,k}) \ge F_k(u_{\inf}) > 0$，这意味着在经过至多 $T_0 = \mathcal{O}((\log T)^2)$ 步之后，每一个任务的观测次数都随轮次呈线性增长 $N_{t,k} \ge c \cdot t$。在一般非减曲线的极小化极大分析中，瞬时遗憾则利用类似线性老虎机椭圆势能引理的级数伸缩技巧控制： $$\sum_{t=1}^T \frac{B_{t,k}(X_{t,k})}{\sqrt{1 + N_{t-1,k}}} = \sum_{\tau=1}^{N_{T,k}} \frac{1}{\sqrt{\tau}} \le 2\sqrt{1 + N_{T,k}}$$ 最后借助 Jensen 不等式对 $\sum_{k=1}^K \sqrt{1 + N_{T,k}}$ 求和，在不依赖任何凹性假设的前提下统一输出 $\widetilde{\mathcal{O}}(K\sqrt{T})$ 极小化极大界。

一个完整示例¶

考虑 $K=2$ 的算力竞价场景，两个异质推理模型 $k \in \{1, 2\}$ 的性能均值分别为 $\mu_1 = 0.8, \mu_2 = 0.4$，成功概率曲线满足典型的幂函数凹衰减 $F_1(x) = x^{0.5}, F_2(x) = x^{0.5}$。初始时 $N_{0,1}=N_{0,2}=0$，算法初始化 $\mathrm{UCB}_{0,1}^\delta = \mathrm{UCB}_{0,2}^\delta = \sqrt{\log(2/\delta)}$。 1. 第 1 轮：由于两任务置信上限相等，目标函数 $\sqrt{\log(2/\delta)} (x_1^{0.5} + x_2^{0.5})$ 在单纯形 $x_1 + x_2 = 1$ 上的对称极大值点为 $X_1 = (0.5, 0.5)$。环境采样指示变量，假设两模型均在 0.5 预算下成功运行 ($B_{1,1}=1, B_{1,2}=1$)，算法观测到实际奖励反馈 $G_{1,1}=0.85, G_{1,2}=0.38$。 2. 状态更新：有效计数更新为 $N_{1,1}=1, N_{1,2}=1$。计算新置信上限：$\mathrm{UCB}_{1,1}^\delta = 0.85 + \sqrt{\log(2/\delta)/2}$，$\mathrm{UCB}_{1,2}^\delta = 0.38 + \sqrt{\log(2/\delta)/2}$。 3. 第 2 轮决策：此时 $\mathrm{UCB}_{1,1}^\delta > \mathrm{UCB}_{1,2}^\delta$。求解带权凸优化 $\max_{x_1+x_2=1} \mathrm{UCB}_{1,1} \sqrt{x_1} + \mathrm{UCB}_{1,2} \sqrt{x_2}$，其解析最优解满足 $x_1/x_2 = (\mathrm{UCB}_{1,1}/\mathrm{UCB}_{1,2})^2$。算法自适应向高收益任务倾斜预算，分配 $X_2 = (0.75, 0.25)$。 4. 收敛态演化：伴随分配倾斜，任务 1 以更高概率 $F_1(0.75) \approx 0.866$ 被观测并快速锁定估计，而任务 2 虽分配较低预算 $0.25$，但因边界排斥绝不会被饿死（$F_2(0.25) = 0.5$），在 $T_0$ 步后两者置信区间均以 $1/\sqrt{t}$ 收敛，总瞬时遗憾由二次衰减控制在 $\mathcal{O}(1/t)$，累积和收敛为 $\mathcal{O}((\log T)^2)$。

损失函数 / 训练策略¶

作为免调参的在线学习算法，UCBowski 无需离线梯度训练，其内循环核心是求解单步非线性凹规划： $$X_t = \underset{x \in \Delta_K}{\operatorname{argmax}} \sum_{k=1}^K \mathrm{UCB}_{t-1,k}^\delta F_k(x_k)$$ 当 $F_k$ 满足凹性时，该问题是具有单纯形等式约束的强凹优化问题，可通过拉格朗日乘子法转化为单变量单调方程求根，利用二分法或牛顿迭代在 $\mathcal{O}(K \log(1/\epsilon))$ 时间复杂度内求得 $\epsilon$-精确解。置信参数统一设为理论最优值 $\delta = 1/(KT)^2$，无需任何问题依赖的启发式调优。

实验关键数据¶

主实验：理论遗憾界与信息反馈模式比较¶

论文通过严格的信息论下界推导与渐近极小化极大分析，建立了截断半多臂反馈与全反馈、纯标量线性老虎机在不同收益曲率下的完整理论界限图谱。

算法 / 理论设定	反馈信息类型	收益曲线假设 $F_k$	累积遗憾上界 $R_T$	匹配下界	核心结论与理论依据
UCBowski (本文)	截断半多臂 (Censored)	边际递减 (凹幂函数 $x^{a_k}$)	$\mathcal{O}(\mathrm{poly}(K) (\log T)^2)$	$\Omega(K (\log T)^2)$ (渐近匹配)	免调参实现超快对数收敛；二阶遗憾退化与边界排斥
UCBowski (本文)	截断半多臂 (Censored)	通用单调非减曲线	$\widetilde{\mathcal{O}}(K \sqrt{T})$	$\Omega(K \sqrt{T})$ (紧确极小极大)	势能伸缩控制，严格达到极小化极大最优率
线性老虎机 (Dani et al.)	纯标量汇总反馈	边际递减 ($F_k(b)=\sqrt{b}$)	$\mathcal{O}(K \sqrt{T \log T})$	$\Omega(\sqrt{T})$ (Theorem 2)	无法突破根号下界；标量反馈在最优方向附近存在信息盲区
组合半多臂 (Chen et al.)	标准半多臂反馈	阶跃曲线 $\mathbb{I}_{[1/M, 1]}$	$\widetilde{\mathcal{O}}(\sqrt{K M T})$	$\Omega(\sqrt{K M T})$	本文 Corollary 1 作为特例完全恢复其已知最优界
任意在线学习算法	全反馈 (Full-Feedback)	通用单调非减曲线	$\widetilde{\mathcal{O}}(K \sqrt{T})$	$\Omega(K \sqrt{T})$ (Theorem 4)	即使观测所有未完成任务的奖励，极小极大界依然为 $\Omega(K\sqrt{T})$
未知曲线设定	截断半多臂 (未知 $F_k$)	阶跃指示曲线	$\Omega(T)$ (线性遗憾)	$\Omega(T)$ (Theorem 5)	不可能定理：若预算-成功曲线未知，任意算法必遭受线性遗憾

消融与特例分析：参数依赖性与收敛常数核算¶

针对边际递减幂函数族 $F_k(x) = x^{a_k}$ 与典型二任务实例，论文在附录 C 与 F 中对收敛常数与各结构分量贡献进行了显式消融核算。

实例配置	任务数 $K$	幂指数区间 $[a_{\min}, a_{\max}]$	均值下界 $\mu_{\inf}$	遗憾显式常数 / 表达式主导项	结构贡献与失效机理分析
对称开方基准 (K=2)	$K=2$	$a_1 = a_2 = 0.5$	$\mu_{\inf} \ge 1/4$	$R_T \le 1.48 \times 10^6 \log(8T^2) \log T + 2.56 \times 10^4 (\log T)^2$	二阶平滑与对称极值诱发极佳收敛，主导项为 $(\log T)^2$
非对称幂律分布	$K=10$	$a_{\min}=0.2, a_{\max}=0.8$	$\mu_{\inf} = 0.1$	$c_K = K^{1 + \frac{(2(1-a_{\min})+a_{\max})(1-a_{\min})}{1-a_{\max}}} = K^{6.8}$	极端曲率差异推大边界排斥下界 $u_{\inf}$，导致常数因子增大
硬实例下界构造 (Thm 4)	$2K$ 任务 ($K$ 对)	阈值曲线 $\mathbb{I}_{[1/K, 1]}$	$\mu \in \{0.5, 0.5 + 1/\sqrt{T}\}$	$R_T \ge \frac{1}{2}\sqrt{T} \sum_{i=1}^K p(i) = \Omega(K\sqrt{T})$	将连续分配离散投影为 $K$ 个独立的双臂困难老虎机
标量反馈反例 (Thm 2)	$K=2$	$F_k(b)=\sqrt{b}$ (角度参数化)	$\min(\mu_1, \mu_2) \ge 3/8$	$R_T \ge \frac{1}{140} \sqrt{T}$ (扰动 $\epsilon = \Theta(T^{-1/4})$)	角度位于 $\pi/4$ 时 KL 散度受控于 $\mathcal{O}(\epsilon^2

关键发现¶

信息反馈结构决定收敛速度阶跃：在相同的边际递减物理模型下，截断半多臂反馈能够精确记录各分量的微观成功事件，从而实现多对数遗憾 $\mathcal{O}((\log T)^2)$；而仅能获知标量总和的线性老虎机被严格限制在 $\Omega(\sqrt{T})$，证明了半多臂微观指示信息在连续动作空间中的决定性价值。
强凹性扮演隐式正规化器：在连续单纯形上，当导数具有奇点时，最优解天然位于内部，算法不仅免除了由于离散化网格误差引入的偏置，而且一阶项相互抵消直接诱发二阶瞬时遗憾，使得在线估计方差向损失的传导被二次方压缩。
极小化极大下界在全反馈下依然成立：构造的 $2K$ 任务配对硬实例证明，即便赋予算法“洞悉所有未执行任务随机收益”的完备反馈神谕，只要收益曲线不具备强凹性，由于必须在 $K$ 个独立方向上识别 $1/\sqrt{T}$ 的微弱增益，$\Omega(K\sqrt{T})$ 的下界仍然不可逾越，印证了 UCBowski 算法在最坏情形下的紧确最优性。

亮点与洞察¶

将连续单纯形优化与乐观原则深度结合：直接将 UCB 估计向量代入凹泛函目标并在单纯形上全局求解，绕开了所有连续空间老虎机依赖的局部核平滑或离散网格化陷阱，保持了计算的高效性与理论上的紧凑性。
揭示了“高投入-高反馈”的内在自稳定机制：算法倾向于向高期望分量追加预算，而这恰好单调提高了该分量在后续轮次中成功触发并被观测的概率，使得有潜力的臂能够以超快速度积累统计证据，而低效臂在早期即可被安全抑制。
理论下界构建中的独立双臂降维投影技术：在证明 Theorem 4 时，论文通过精妙的随机化重新分配变换，证明了任意连续单纯形分配策略均可保遗憾地等价映射为 $K$ 对独立两臂选择，首次在连续预算约束下完成了向经典信息论下界的严密约简。

局限与展望¶

依赖预算-成功曲线的先验可知性：算法严格假设函数族 $F_k$ 已知；根据 Theorem 5 的不可能定理，若 $F_k$ 全未知则即便在确定性环境下也会遭受线性遗憾。未来工作可探索 $F_k$ 属于具有弱参数化先验（如已知参数形式但未知参数）下的松弛边界。
局限于单轮刚性预算约束：目前模型假设每轮预算固定归一化在 $\Delta_K$ 上，未考虑跨轮次的全局背包式软预算（Knapsack Bandits）或随时间随机波动的动态资源约束。
缺少上下文与延迟反馈建模：在实际推荐与分布式训练中，任务到达通常携带上下文特征（Contextual），且任务执行时间长短不一并存在异步延迟完成现象，将 UCBowski 扩展至带延迟的上下文截断半多臂框架是极具价值的后续方向。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统性形式化截断半多臂预算分配模型，并在连续单纯形上给出免调参的多对数与紧确极小极大上界。
理论完备度: ⭐⭐⭐⭐⭐ 理论体系严密，同时包含正向算法收敛性、匹配极小极大下界、标量反馈分离下界以及未知曲线不可能定理。
写作质量: ⭐⭐⭐⭐⭐ 概念清晰，数学推导详实，主文与附录的定理结构层层递进、逻辑自洽。
价值: ⭐⭐⭐⭐⭐ 对算力调度、众包支付与多平台竞价等前沿工业在线分配问题具有极其深厚的基础理论指导价值。

实例配置	任务数 \(K\)	幂指数区间 \([a_{\min}, a_{\max}]\)	均值下界 \(\mu_{\inf}\)	遗憾显式常数 / 表达式主导项	结构贡献与失效机理分析
对称开方基准 (K=2)	\(K=2\)	\(a_1 = a_2 = 0.5\)	\(\mu_{\inf} \ge 1/4\)	\(R_T \le 1.48 \times 10^6 \log(8T^2) \log T + 2.56 \times 10^4 (\log T)^2\)	二阶平滑与对称极值诱发极佳收敛，主导项为 \((\log T)^2\)
非对称幂律分布	\(K=10\)	\(a_{\min}=0.2, a_{\max}=0.8\)	\(\mu_{\inf} = 0.1\)	\(c_K = K^{1 + \frac{(2(1-a_{\min})+a_{\max})(1-a_{\min})}{1-a_{\max}}} = K^{6.8}\)	极端曲率差异推大边界排斥下界 \(u_{\inf}\)，导致常数因子增大
硬实例下界构造 (Thm 4)	\(2K\) 任务 (\(K\) 对)	阈值曲线 \(\mathbb{I}_{[1/K, 1]}\)	\(\mu \in \{0.5, 0.5 + 1/\sqrt{T}\}\)	\(R_T \ge \frac{1}{2}\sqrt{T} \sum_{i=1}^K p(i) = \Omega(K\sqrt{T})\)	将连续分配离散投影为 \(K\) 个独立的双臂困难老虎机
标量反馈反例 (Thm 2)	\(K=2\)	\(F_k(b)=\sqrt{b}\) (角度参数化)	\(\min(\mu_1, \mu_2) \ge 3/8\)	\(R_T \ge \frac{1}{140} \sqrt{T}\) (扰动 \(\epsilon = \Theta(T^{-1/4})\))	角度位于 \(\pi/4\) 时 KL 散度受控于 $\mathcal{O}(\epsilon^2

算法 / 理论设定	反馈信息类型	收益曲线假设 \(F_k\)	累积遗憾上界 \(R_T\)	匹配下界	核心结论与理论依据
UCBowski (本文)	截断半多臂 (Censored)	边际递减 (凹幂函数 \(x^{a_k}\))	\(\mathcal{O}(\mathrm{poly}(K) (\log T)^2)\)	\(\Omega(K (\log T)^2)\) (渐近匹配)	免调参实现超快对数收敛；二阶遗憾退化与边界排斥
UCBowski (本文)	截断半多臂 (Censored)	通用单调非减曲线	\(\widetilde{\mathcal{O}}(K \sqrt{T})\)	\(\Omega(K \sqrt{T})\) (紧确极小极大)	势能伸缩控制，严格达到极小化极大最优率
线性老虎机 (Dani et al.)	纯标量汇总反馈	边际递减 (\(F_k(b)=\sqrt{b}\))	\(\mathcal{O}(K \sqrt{T \log T})\)	\(\Omega(\sqrt{T})\) (Theorem 2)	无法突破根号下界；标量反馈在最优方向附近存在信息盲区
组合半多臂 (Chen et al.)	标准半多臂反馈	阶跃曲线 \(\mathbb{I}_{[1/M, 1]}\)	\(\widetilde{\mathcal{O}}(\sqrt{K M T})\)	\(\Omega(\sqrt{K M T})\)	本文 Corollary 1 作为特例完全恢复其已知最优界
任意在线学习算法	全反馈 (Full-Feedback)	通用单调非减曲线	\(\widetilde{\mathcal{O}}(K \sqrt{T})\)	\(\Omega(K \sqrt{T})\) (Theorem 4)	即使观测所有未完成任务的奖励，极小极大界依然为 \(\Omega(K\sqrt{T})\)
未知曲线设定	截断半多臂 (未知 \(F_k\))	阶跃指示曲线	\(\Omega(T)\) (线性遗憾)	\(\Omega(T)\) (Theorem 5)	不可能定理：若预算-成功曲线未知，任意算法必遭受线性遗憾