Game of Coding With an Unknown Adversary

• URL: http://arxiv.org/abs/2502.07109v1
• Date: Mon, 10 Feb 2025 23:06:10 GMT
• Title: Game of Coding With an Unknown Adversary
• Authors: Hanzaleh Akbarinodehi, Parsa Moradi, Mohammad Ali Maddah-Ali,
• Abstract summary: Motivated by emerging decentralized applications, the emphgame of coding framework has been introduced to address scenarios where the adversary's control over coded symbols surpasses the fundamental limits of traditional coding theory. 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. 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.
• Score: 15.839621757142597
• License:
• Abstract: 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.

Related papers

• Deceptive Sequential Decision-Making via Regularized Policy Optimization [54.38738815697299]
  Two regularization strategies for policy synthesis problems that actively deceive an adversary about a system's underlying rewards are presented. We show how each form of deception can be implemented in policy optimization problems. We show that diversionary deception can cause the adversary to believe that the most important agent is the least important, while attaining a total accumulated reward that is $98.83%$ of its optimal, non-deceptive value.
  arXiv  Detail & Related papers  (2025-01-30T23:41:40Z)
• Learning a Factorized Orthogonal Latent Space using Encoder-only Architecture for Fault Detection; An Alarm management perspective [0.2455468619225742]
  This paper introduces a novel encoder-based residual design that effectively decouples erroneously identified and deterministic components of process variables. The proposed model employs two distinct encoders to factorize the latent space into two spaces: one for the deterministic part and the other for the part. The proposed model significantly enhances prediction quality while achieving nearly zero false alarms and missed detections.
  arXiv  Detail & Related papers  (2024-08-24T09:00:45Z)
• Exploiting hidden structures in non-convex games for convergence to Nash equilibrium [62.88214569402201]
  A wide array of modern machine learning applications can be formulated as non-cooperative Nashlibria. We provide explicit convergence guarantees for both deterministic and deterministic environments.
  arXiv  Detail & Related papers  (2023-12-27T15:21:25Z)
• Distributional Shift-Aware Off-Policy Interval Estimation: A Unified Error Quantification Framework [8.572441599469597]
  We study high-confidence off-policy evaluation in the context of infinite-horizon Markov decision processes. The objective is to establish a confidence interval (CI) for the target policy value using only offline data pre-collected from unknown behavior policies. We show that our algorithm is sample-efficient, error-robust, and provably convergent even in non-linear function approximation settings.
  arXiv  Detail & Related papers  (2023-09-23T06:35:44Z)
• When Does Confidence-Based Cascade Deferral Suffice? [69.28314307469381]
  Cascades are a classical strategy to enable inference cost to vary adaptively across samples. A deferral rule determines whether to invoke the next classifier in the sequence, or to terminate prediction. Despite being oblivious to the structure of the cascade, confidence-based deferral often works remarkably well in practice.
  arXiv  Detail & Related papers  (2023-07-06T04:13:57Z)
• Interpreting Primal-Dual Algorithms for Constrained Multiagent Reinforcement Learning [4.67306371596399]
  Most C-MARL algorithms use a primal-dual approach to enforce constraints through a penalty function added to the reward. We show that the standard practice of using the constraint function as the penalty leads to a weak notion of safety. We propose a constrained multiagent advantage actor critic (C-MAA2C) algorithm.
  arXiv  Detail & Related papers  (2022-11-29T10:23:26Z)
• Beyond the Return: Off-policy Function Estimation under User-specified Error-measuring Distributions [8.881195152638986]
  Off-policy evaluation often refers to two related tasks: estimating the expected return of a policy and estimating its value function. We provide guarantees for off-policy function estimation under only realizability, by imposing proper regularization on the marginalized importance sampling objectives.
  arXiv  Detail & Related papers  (2022-10-27T15:34:17Z)
• Linear Stochastic Bandits over a Bit-Constrained Channel [37.01818450308119]
  We introduce a new linear bandit formulation over a bit-constrained channel. The goal of the server is to take actions based on estimates of an unknown model parameter to minimize cumulative regret. We prove that when the unknown model is $d$-dimensional, a channel capacity of $O(d)$ bits suffices to achieve order-optimal regret.
  arXiv  Detail & Related papers  (2022-03-02T15:54:03Z)
• Robustness and Accuracy Could Be Reconcilable by (Proper) Definition [109.62614226793833]
  The trade-off between robustness and accuracy has been widely studied in the adversarial literature. We find that it may stem from the improperly defined robust error, which imposes an inductive bias of local invariance. By definition, SCORE facilitates the reconciliation between robustness and accuracy, while still handling the worst-case uncertainty.
  arXiv  Detail & Related papers  (2022-02-21T10:36:09Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Trust but Verify: Assigning Prediction Credibility by Counterfactual Constrained Learning [123.3472310767721]
  Prediction credibility measures are fundamental in statistics and machine learning. These measures should account for the wide variety of models used in practice. The framework developed in this work expresses the credibility as a risk-fit trade-off.
  arXiv  Detail & Related papers  (2020-11-24T19:52:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.