# Learning from Acceptance: Cumulative Regret in the Game of Coding

arXiv: https://arxiv.org/abs/2605.09754 · HTML: https://mlsanity.com/paper/2605.09754/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 47 references that are in the map.
- First posted on arXiv 10 May 2026.

## Builds on (most cited first, 17 of 17)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy](https://mlsanity.com/paper/1806.00939/) (2018)
- [Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication](https://mlsanity.com/paper/1705.10464/) (2017)
- [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (2022)
- [On the Optimal Recovery Threshold of Coded Matrix Multiplication](https://mlsanity.com/paper/1801.10292/) (2018)
- [Learning to Play Sequential Games versus Unknown Opponents](https://mlsanity.com/paper/2007.05271/) (2020)
- [CodedSketch: A Coding Scheme for Distributed Computation of Approximated Matrix Multiplication](https://mlsanity.com/paper/1812.10460/) (2018)
- [Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier](https://mlsanity.com/paper/2001.05101/) (2020)
- [Robust Stackelberg Equilibria](https://mlsanity.com/paper/2304.14990/) (2023)
- [Game of Coding: Sybil Resistant Decentralized Machine Learning with Minimal Trust Assumption](https://mlsanity.com/paper/2410.05540/) (2024)
- [Survey on the Convergence of Machine Learning and Blockchain](https://mlsanity.com/paper/2201.00976/) (2022)
- [General Coded Computing: Adversarial Settings](https://mlsanity.com/paper/2502.08058/) (2025)
- [SoK: Blockchain Technology and Its Potential Use Cases](https://mlsanity.com/paper/1909.12454/) (2019)
- ["Zero Cost'' Majority Attacks on Permissionless Blockchains](https://mlsanity.com/paper/2308.06568/) (2023)
- [Game of Coding With an Unknown Adversary](https://mlsanity.com/paper/2502.07109/) (2025)
- [Game of Coding: Coding Theory in the Presence of Rational Adversaries, Motivated by Decentralized Machine Learning](https://mlsanity.com/paper/2601.02313/) (2026)

## Abstract (arXiv)

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.