Learning from Acceptance: Cumulative Regret in the Game of Coding

• URL: http://arxiv.org/abs/2605.09754v1
• Date: Sun, 10 May 2026 21:04:43 GMT
• Title: Learning from Acceptance: Cumulative Regret in the Game of Coding
• Abstract summary: We study an incomplete-information version of the game of coding in which the data collector does not know the adversary's utility trade-off.<n>We propose an algorithm that refines its search around promising acceptance rules, prove that it achieves sublinear cumulative regret, and evaluate its performance.
• Score: 15.178727194172161
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• The Evaluation Game: Beyond Static LLM Benchmarking [2.168753020470345]
  We introduce a game-theoretic framework in which the interaction between an evaluator and a trainer is formalized as a two-player game.<n>We provide empirical evidence supporting locality-dependence of the model.<n>Our framework recasts the central object of adversarial evaluation: a benchmark is not a static set of prompts but an orbit under the evaluator's group action.
  arXiv  Detail & Related papers  (2026-05-19T05:22:21Z)
• \mathsf{VISTA}: Decentralized Machine Learning in Adversary Dominated Environments [21.69919643934826]
  Decentralized machine learning often relies on outsourcing computations, such as evaluations, to untrusted worker nodes.<n>We study this adversary-dominated setting through an incentive-oriented framework in which reports are accepted and rewarded only when they are mutually consistent up to a threshold.<n>We propose mathsfVISTA, an adaptive algorithm that tunes the acceptance threshold using the optimization history.
  arXiv  Detail & Related papers  (2026-05-08T15:07:15Z)
• Partial Identification Approach to Counterfactual Fairness Assessment [50.88100567472179]
  We introduce a Bayesian approach to bound unknown counterfactual fairness measures with high confidence.<n>Our results reveal a positive (spurious) effect on the COMPAS score when changing race to African-American (from all others) and a negative (direct causal) effect when transitioning from young to old age.
  arXiv  Detail & Related papers  (2025-09-30T18:35:08Z)
• Beyond Agreement: Rethinking Ground Truth in Educational AI Annotation [1.8434042562191815]
  We argue that overreliance on human inter-rater reliability (IRR) as a gatekeeper for annotation quality hampers progress in classifying data.<n>We highlight five examples of complementary evaluation methods, such as multi-label annotation schemes, expert-based approaches, and close-the-loop validity.<n>We call on the field to rethink annotation quality and ground truth--prioritizing validity and educational impact over consensus alone.
  arXiv  Detail & Related papers  (2025-07-31T20:05:26Z)
• Probably Approximately Precision and Recall Learning [60.00180898830079]
  A key challenge in machine learning is the prevalence of one-sided feedback.<n>We introduce a Probably Approximately Correct (PAC) framework in which hypotheses are set functions that map each input to a set of labels.<n>We develop new algorithms that learn from positive data alone, achieving optimal sample complexity in the realizable case.
  arXiv  Detail & Related papers  (2024-11-20T04:21:07Z)
• Decoupling the Class Label and the Target Concept in Machine Unlearning [81.69857244976123]
  Machine unlearning aims to adjust a trained model to approximate a retrained one that excludes a portion of training data. Previous studies showed that class-wise unlearning is successful in forgetting the knowledge of a target class. We propose a general framework, namely, TARget-aware Forgetting (TARF)
  arXiv  Detail & Related papers  (2024-06-12T14:53:30Z)
• Online Decision Mediation [72.80902932543474]
  Consider learning a decision support assistant to serve as an intermediary between (oracle) expert behavior and (imperfect) human behavior. In clinical diagnosis, fully-autonomous machine behavior is often beyond ethical affordances.
  arXiv  Detail & Related papers  (2023-10-28T05:59:43Z)
• Binary Classification with Confidence Difference [100.08818204756093]
  This paper delves into a novel weakly supervised binary classification problem called confidence-difference (ConfDiff) classification. We propose a risk-consistent approach to tackle this problem and show that the estimation error bound the optimal convergence rate. We also introduce a risk correction approach to mitigate overfitting problems, whose consistency and convergence rate are also proven.
  arXiv  Detail & Related papers  (2023-10-09T11:44:50Z)
• Unsupervised Dense Retrieval with Relevance-Aware Contrastive Pre-Training [81.3781338418574]
  We propose relevance-aware contrastive learning. We consistently improve the SOTA unsupervised Contriever model on the BEIR and open-domain QA retrieval benchmarks. Our method can not only beat BM25 after further pre-training on the target corpus but also serves as a good few-shot learner.
  arXiv  Detail & Related papers  (2023-06-05T18:20:27Z)
• A Call to Reflect on Evaluation Practices for Failure Detection in Image Classification [0.491574468325115]
  We present a large-scale empirical study for the first time enabling benchmarking confidence scoring functions. The revelation of a simple softmax response baseline as the overall best performing method underlines the drastic shortcomings of current evaluation.
  arXiv  Detail & Related papers  (2022-11-28T12:25:27Z)
• Evaluating Machine Unlearning via Epistemic Uncertainty [78.27542864367821]
  This work presents an evaluation of Machine Unlearning algorithms based on uncertainty. This is the first definition of a general evaluation of our best knowledge.
  arXiv  Detail & Related papers  (2022-08-23T09:37:31Z)
• ConQUR: Mitigating Delusional Bias in Deep Q-learning [45.21332566843924]
  Delusional bias is a fundamental source of error in approximate Q-learning. We develop efficient methods to mitigate delusional bias by training Q-approximators with labels that are "consistent" with the underlying greedy policy class.
  arXiv  Detail & Related papers  (2020-02-27T19:22:51Z)

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.