揭示在线决策中延迟与顺序效应的理论下界，可指导系统优化
Latency and Ordering Effects in Online Decisions
- 基于Bregman散度构建含延迟与顺序敏感性的损失下界
- 四类误差项可量化：延迟、顺序、交互及非凸性，总和为正
- 提供可实时监测的实验设计与诊断工具，适合系统级调优
在线决策系统常面临反馈延迟和顺序敏感（非交换）动态：行动影响观测结果的到达时机与顺序。以Bregman散度 $D_Φ$ 为损失基准，我们证明其超额基准损失存在结构化下界 $L \ge L_{\mathrm{ideal}} + g_1(λ) + g_2(\varepsilon_\star) + g_{12}(λ,\varepsilon_\star) - D_{\mathrm{ncx}}$，其中 $g_1$ 与 $g_2$ 分别为延迟与顺序敏感的校准惩罚，$g_{12}$ 捕捉二者几何交互，$D_{\mathrm{ncx}}\ge 0$ 为非凸性/近似惩罚，在凸Legendre假设下消失。该不等式扩展至prox-regular与弱凸情形，获得超越凸情况的鲁棒保证。同时提出通过简单 $2\times 2$ 随机实验与流式诊断（有效样本量、截断率、交互热图）估计并监控四项的实用方案。该框架将异构的延迟、非交换性与实现差距效应整合为单一可解释的下界陈述，支持真实系统中的压力测试与调优。
原文摘要 · Abstract (English)
Online decision systems routinely operate under delayed feedback and order-sensitive (noncommutative) dynamics: actions affect which observations arrive, and in what sequence. Taking a Bregman divergence $D_Φ$ as the loss benchmark, we prove that the excess benchmark loss admits a structured lower bound $L \ge L_{\mathrm{ideal}} + g_1(λ) + g_2(\varepsilon_\star) + g_{12}(λ,\varepsilon_\star) - D_{\mathrm{ncx}}$, where $g_1$ and $g_2$ are calibrated penalties for latency and order-sensitivity, $g_{12}$ captures their geometric interaction, and $D_{\mathrm{ncx}}\ge 0$ is a nonconvexity/approximation penalty that vanishes under convex Legendre assumptions. We extend this inequality to prox-regular and weakly convex settings, obtaining robust guarantees beyond the convex case. We also give an operational recipe for estimating and monitoring the four terms via simple $2\times 2$ randomized experiments and streaming diagnostics (effective sample size, clipping rate, interaction heatmaps). The framework packages heterogeneous latency, noncommutativity, and implementation-gap effects into a single interpretable lower-bound statement that can be stress-tested and tuned in real-world systems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。