arXiv:2605.09754cs.ITcs.DC2026-05被引 1

在开放系统中学习如何应对隐藏动机的恶意数据提交者。

Learning from Acceptance: Cumulative Regret in the Game of Coding

论文配图:Learning from Acceptance: Cumulative Regret in the Game of Coding
图 1 · 摘自论文原文
  • 设计算法通过反复交互逐步学习最优数据接受规则。
  • 证明算法累积遗憾呈次线性增长,长期表现渐趋最优。
  • 适合研究去中心化系统中的激励兼容与鲁棒性设计。

经典编码理论保证常依赖于信任假设,例如诚实节点数量需超过恶意节点。但在开放去中心化系统中,参与者无中央认证,此类假设难以强制执行。同时,这类环境常包含激励机制:只有当提交数据被接受且系统保持运行时,参与者才会获奖励。这改变了攻击者的角色——其不再纯粹破坏,而是提交看似合理但会降低最终估计质量的数据。本文提出游戏编码框架,建模数据收集者(DC)与攻击者间的策略互动。现有研究多集中于完全信息情形,即DC知晓攻击者在接收率与估计误差间的权衡。本文研究不完全信息版本,其中作为斯塔克尔伯格领导者,DC未知攻击者效用权衡,必须通过重复交互学习。此前针对未知攻击者的研究仅关注探索后固定策略的性能评估,而本文考察整个学习轨迹:每次采用的接受规则均影响整体表现。我们提出一种算法,在有希望的接受规则附近不断优化,证明其可实现次线性累积遗憾,并通过数值实验验证其性能。

原文摘要 · Abstract (English)

Classical coding-theoretic guarantees often rely on trust assumptions, such as requiring sufficiently many honest nodes compared with adversarial ones. These assumptions are difficult to enforce in open decentralized systems where participants are not centrally certified. At the same time, such environments often contain incentive mechanisms: participants may be rewarded only when their submitted data are accepted and the system remains functional. This changes the role of an adversary. Rather than acting as a pure saboteur, a strategic adversary may submit data that are consistent enough to be accepted while still degrading the quality of the final estimate. The game-of-coding framework models this strategic interaction between a data collector (DC) and an adversary. Existing works on the game of coding mostly consider the complete-information case, where the DC knows how the adversary trades off acceptance and estimation error. In this paper, we study an incomplete-information version of the game of coding in which the DC, acting as a Stackelberg leader, does not know the adversary's utility trade-off and must learn through repeated interaction. Prior work on the unknown-adversary setting considered an explore-then-commit objective, where only the final selected acceptance rule is evaluated. In contrast, we study the full learning trajectory: every acceptance rule used during the algorithm is executed and contributes to performance. We propose an algorithm that refines its search around promising acceptance rules, prove that it achieves sublinear cumulative regret, and evaluate its performance through numerical experiments.

博弈论去中心化学习算法

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