arXiv:2502.07109cs.ITcs.LG2025-02被引 5

在未知对手下,让解码器自适应调整策略以逼近最优平衡点。

Game of Coding With an Unknown Adversary

  • 利用接受概率与误差间的不变关系,无需知道对手目标函数。
  • 通过迭代观测参数,解码器可逼近纳什均衡点。
  • 适用于去中心化系统中对手行为不透明的场景。

受新兴去中心化应用启发,'编码博弈'框架被提出以应对传统编码理论极限无法覆盖的对手控制编码符号情形。在该框架中,解码器(数据收集者)具有接受/拒绝机制及估计模块,而对手则追求自身效用最大化,其效用随接受概率(提升奖励)和估计误差而增加。解码器同样优化自身效用,即接受概率越高越好,但估计误差越低越好。以往工作假设双方完全了解对方效用函数,但现实中解码器往往不知对手目标。为此,本文提出一种算法,使解码器在不知对手效用函数的情况下,仍能承诺策略并逼近均衡。核心思想是:在均衡状态下,接受概率与均方误差(MSE)的关系遵循与具体效用函数无关的预定曲线。解码器通过观测这一关系,迭代优化策略,收敛至近优解。我们提供了样本复杂度和精度的理论保证。

原文摘要 · Abstract (English)

Motivated by emerging decentralized applications, the \emph{game of coding} framework has been recently introduced to address scenarios where the adversary's control over coded symbols surpasses the fundamental limits of traditional coding theory. Still, the reward mechanism available in decentralized systems, motivates the adversary to act rationally. While the decoder, as the data collector (DC), has an acceptance and rejection mechanism, followed by an estimation module, the adversary aims to maximize its utility, as an increasing function of (1) the chance of acceptance (to increase the reward), and (2) estimation error. On the other hand, the decoder also adjusts its acceptance rule to maximize its own utility, as (1) an increasing function of the chance of acceptance (to keep the system functional), (2) decreasing function of the estimation error. Prior works within this framework rely on the assumption that the game is complete, that is, both the DC and the adversary are fully aware of each other's utility functions. However, in practice, the decoder is often unaware of the utility of the adversary. To address this limitation, we develop an algorithm enabling the DC to commit to a strategy that achieves within the vicinity of the equilibrium, without knowledge of the adversary's utility function. Our approach builds on an observation that at the equilibrium, the relationship between the probability of acceptance and the mean squared error (MSE) follows a predetermined curve independent of the specific utility functions of the players. By exploiting this invariant relationship, the DC can iteratively refine its strategy based on observable parameters, converging to a near-optimal solution. We provide theoretical guarantees on sample complexity and accuracy of the proposed scheme.

博弈论编码理论去中心化自适应策略

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