Learning from Acceptance: Cumulative Regret in the Game of Coding Hanzaleh Akbari Nodehi, Parsa Moradi, and Mohammad Ali Maddah-Ali
arXiv:2605.09754v1 [cs.IT] 10 May 2026
University of Minnesota, Twin Cities, Minneapolis, MN, USA
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 completeinformation 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.
I. I NTRODUCTION Classical coding theory provides fundamental tools for reliable communication, storage, and computation, but it relies on strict trust assumptions. Successful recovery is typically guaranteed only when honest nodes sufficiently outnumber adversarial ones. For example, in a system with a set of honest nodes H and adversarial nodes T , standard repetition coding requires |H| ≥ |T |+1 to guarantee recovery. Similarly, Reed–Solomon codes, which encode K symbols into N coded symbols, require |H| ≥ |T | + K [1]. Comparable threshold requirements also appear in coded computation, as well as analog and real-valued settings [2]–[10]. These trust assumptions are difficult to enforce in open decentralized systems where participants are not centrally certified [11]–[13]. This issue is particularly relevant in blockchainbased platforms [14]–[16], including decentralized machine learning and oracle systems [17]–[21]. However, these platforms are not purely worst-case environments. Participants are incentive-driven and may receive rewards only when their contribution is accepted and the system remains functional. Therefore, an adversarial participant may not wish to destroy recoverability completely. Instead, it may try to keep the
system live while still degrading the quality of the estimate or computation. This incentive structure suggests that adversarial behavior in these settings should be modeled strategically, rather than purely as arbitrary corruption. To capture this strategic behavior, recent literature in coding theory introduced the game-of-coding [22]–[26]. In this framework, a data collector (DC) interacts with an adversary, and the utility of each player depends on two key quantities: the probability that the DC accepts the submitted reports and the estimation error conditioned on acceptance. This creates a trade-off. The adversary wants to increase the error, but it must avoid causing rejection and losing its reward. Conversely, the DC wants to reduce the error while maintaining enough acceptance probability to keep the system live. A basic two-node model of the game of coding is illustrated in Fig. 1. The system consists of one honest node, one adversarial node, and a DC. The DC aims to estimate an unknown random variable u, but it does not observe u directly. Instead, it receives two reported values. The honest node sends yh = u + nh , where the honest noise is bounded by ∆, while the adversarial node sends ya = u+na , where the distribution of na is strategically chosen by the adversary. The DC receives y = {y1 , y2 } and does not know which report is honest. A natural consistency check accepts the reports only if |y1 − y2 | ≤ 2∆, since any two honest reports would satisfy this bound. However, this rule can be overly conservative. Reports outside this narrow region may still yield a sufficiently accurate estimate of u, and rejecting them may unnecessarily reduce system functionality. Therefore, the DC may instead use a more flexible acceptance rule of the form |y1 − y2 | ≤ η∆. In this setting, the DC acts as a Stackelberg leader by committing to the threshold η, while the adversary observes η and strategically chooses its noise distribution in response. The equilibrium and optimal strategies for this game were first analyzed in [22], and subsequent works extended the framework to vector-valued computations, multi-node systems, Sybil attacks, and advanced coding techniques [23]–[25]. The works above consider a complete-information game, where the DC and the adversary know each other’s utility. This assumption is restrictive in many practical settings. It is reasonable to assume that the adversary know the DC’s utility, but the DC may not know how the adversary trades off error and probability of acceptance. As a result, the DC may not know the adversary’s best response to a committed threshold η. This leads to an incomplete-information game, where the DC must learn the effect of its committed thresholds
through repeated interaction. Learning in games with unknown follower utilities has been studied in several settings [27]–[36]. The unknown-adversary version of the game of coding was first studied in [26]. In that formulation, the DC interacts with the adversary for several rounds and is evaluated only through the final selected threshold. This explore-then-commit objective is appropriate when the learning phase is separated from the deployment phase. In many decentralized systems, however, this separation is not available. Every threshold used during learning is actually executed, and each accepted or rejected report affects the system’s performance. Motivated by this observation, we study a trajectory-level objective in which every round contributes to the DC’s performance. We measure performance by cumulative regret with respect to the best fixed threshold in hindsight. This objective connects the problem to the multi-armed bandit framework, where a learner repeatedly chooses actions, observes feedback, and aims to minimize regret relative to the best fixed action [37]–[41]. Since the DC’s threshold η belongs to a continuum, our setting is especially related to continuumarmed and metric-space bandits [42]–[46]. Nevertheless, the feedback in our problem is different from standard bandit. In a classical bandit problem, after choosing an action, the learner observes a reward sample and can use it to evaluate that action. In our setting, after the DC commits to a threshold, the adversary strategically responds, and the DC observes only whether the submitted reports were accepted or rejected. The DC does not observe its utility, nor does it observe the estimation error in that round, because the true value of u is unknown. Thus, the feedback is both partial and strategic: the observed binary acceptance event is generated after the adversary has responded to the DC’s committed threshold. To address this challenge, we exploit a structural property of the game of coding. For any threshold committed by the DC and any corresponding response of the adversary, the induced probability of acceptance and the estimation error are not arbitrary. They lie on a curve determined by the statistical model and the acceptance rule. Importantly, this curve is independent of the utility functions of both players. Therefore, even though the DC cannot observe the estimation error directly, it can use repeated accept/reject observations to estimate the probability of acceptance and then map this estimate to the corresponding induced utility. Using this idea, we design an adaptive threshold-learning algorithm. The algorithm maintains a set of active thresholds and updates an estimate of the DC’s utility for each active threshold using only binary acceptance feedback. It assigns larger uncertainty bonuses to thresholds that have been sampled less often and gradually refines the search by activating new thresholds in regions that are not yet well represented. As a result, the algorithm spends more time near thresholds that may be close to optimal while still exploring insufficiently sampled regions of the threshold space. The contributions of this paper are as follows. First, we formulate the unknown-adversary game of coding as an online Stackelberg learning problem with a cumulative regret
objective, where every threshold used during learning affects performance. Second, we show how the DC can learn from binary acceptance feedback, even though it does not directly observe its utility. Third, we design an adaptive thresholdlearning policy for the continuous threshold space and prove that it achieves sublinear regret. Finally, we provide numerical experiments showing that the proposed policy outperforms the explore-then-commit baseline of [26]. The paper is organized as follows. Section II presents the problem formulation. Section III provides the preliminaries. Section IV presents the main theorem, which is proved in Section V. Section VI presents the numerical experiments. II. P ROBLEM F ORMULATION In this section we present the problem formulation. We consider a system consisting of two nodes1 and a DC (See Fig. 1). The DC aims to estimate u but does not have direct access to it. Instead, it relies on the two nodes. One of the nodes is honest, while the other is adversarial. The identity of the adversarial node is hidden from the DC. The honest node sends yh = u + nh , where the probability density function (PDF) of nh , denoted by fnh , is symmetric, and Pr (|nh | > ∆) = 0 for some ∆ ∈ R. The adversary sends ya = u + na , where na is independent of u. The PDF of na , denoted by g(.), is chosen by the adversary. The DC is unaware of this choice. We assume that M , ∆, and the distribution of nh are known to all players, and ∆ ≪ M . yh = u + n h
Honest node
|yh − ya | ≤ η∆
Adversarial node
Yes
Estimate u
û
ya = u + na No
Data Collector
Reject
Fig. 1. Two-node game-of-coding model. The DC first commits to η. The honest node reports yh = u + nh , where |nh | ≤ ∆, while the adversarial node reports ya = u + na , where the distribution of na is chosen arbitrarily by the adversary in response to η. The DC accepts the reports if |yh − ya | ≤ η∆ and then forms an estimate û; otherwise, it rejects them.
The DC receives y ≜ {y1 , y2 } and evaluates it as follows: • First, the DC accepts y if and only if |y1 − y2 | ≤ η∆, for η ≥ 2. We denote by Aη the event that the inputs are accepted, and define PA(g(.), η) ≜ Pr(Aη ). • Second, if the inputs are accepted, the DC outputs est(y) as its estimate of u, where est : R2 → R. The estimation cost is defined as MSE (est(., .), g(.), η) ≜ E[(u − est(y))2 | Aη ]. The DC chooses the estimator est∗η,g ≜ arg min MSE (est(., .), g(.), η). We define est:R2 →R
MMSE(g(.), η) ≜ MSE est∗η,g (., .), g(.), η .
(1)
The interaction between the DC and the adversary is modeled as a two-player Stackelberg game [47]. The DC utility and 1 For simplicity of exposition, in this conference paper we focus on system with two nodes. Based on [24], the result of this paper can be directly used for system with more than two nodes.
the adversary utility are respectively defined as UDC (g(.), η) ≜ QDC (MMSE, PA) and UAD (g(.), η) ≜ QAD (MMSE, PA). The function QDC : R2 → R is non-increasing with respect to MMSE and non-decreasing with respect to PA. Conversely, QAD : R2 → R is strictly increasing with respect to both arguments. We assume that the adversary knows both utility functions, whereas the DC does not know QAD . We assume that the DC chooses η ∈ ΛDC ≜ [ηmin , ηmax ], where 2 ≤ ηmin < ηmax , and that the adversary selects its strategy from ΛAD ≜ {g(.) | g(.) : R → R is a valid PDF}. For each ΛDC to which the DC commits, the adversary observes η and chooses a best response B η ≜ arg max UAD (g(.), η). Elements of B η provide the same utility to the adversary, but they may induce different utilities for the DC. We define B̄ η ≜ arg min UDC (g(.), η).
(2)
g(.)∈Bη
For every η ∈ ΛDC , fix an arbitrary gη∗ (.) ∈ B̄ η and define α(η) ≜ PA(gη∗ (.), η) and m(η) ≜ MMSE(gη∗ (.), η). Thus, the induced utility of the DC when it commits to η is U(η) ≜ UDC (gη∗ (.), η) = QDC (m(η), α(η)) .
(3)
We define the optimal utility as U∗ΛDC ≜ supη∈ΛDC U(η). We now define the multi-round interaction. At the beginning of round t, the DC has access to the history Ht−1 = {ηs , ys , 1{Aηs }}t−1 s=1 . A policy π of the DC is a sequence of maps πt : Ht−1 → ΛDC , and the DC commits to ηt = πt (Ht−1 ). After observing ηt , the adversary myopically chooses gt (.) ∈ B̄ ηt . The term myopic means that the adversary maximizes its immediate utility for the current round t with respect to the value of ηt . The DC observes the reports yt and the acceptance indicator Zt ≜ 1{Aηt }. Conditioned on Ht−1 and ηt , the acceptance indicator satisfies E [Zt | Ht−1 , ηt ] = α(ηt ).
(4)
The objective is to design a policy π = {πt }t≥1 whose performance is good over the entire trajectory. We measure the performance of π, by the cumulative regret with respect to the best fixed acceptance parameter in ΛDC : T X RegT (π) = Eπ [ (U∗ΛDC − U(ηt ))].
(5)
t=1
III. P RELIMINARIES For any η ∈ ΛDC and α ∈ [0, 1], we define cη (α) ≜ max MMSE(g(.), η) g(.)∈ΛAD
s.t.
PA(g(.), η) ≥ α.
Note that the function cη (.) does not depend on QDC or QAD . A key characterization from the game-of-coding framework [22]–[26] states that, for any gη∗ (.) ∈ B̄ η , we have MMSE(gη∗ (.), η) = cη PA(gη∗ (.), η) . This implies that m(η) = cη (α(η)). Define Fη (α) ≜ QDC (cη (α), α). Based on (3), we have U(η) = QDC (cη (α(η)), α(η)) = Fη (α(η)). This identity is central to our algorithm. The DC does not know QAD , does not know the adversary’s selected response
Algorithm 1 Game-of-Coding Zooming Algorithm Require: Metric D, Lipschitz constant ℓ, maps {Fη (.)}η∈ΛDC Ensure: Commitments η1 , η2 , . . . 1: ℓ̄ ← max{1, ℓ}, t ← 0 2: for phases i = 1, 2, . . . do 3: Si ← ∅ 4: for local rounds s = 1, . . . , 2i do 5: t←t+1 6: for each v ∈ Si do 7: α bi (v) ← Niacc (v)/Ni (v) if Ni (v) > 0, and 0 otherwise b i (v) ← Π[0,1] (Fv (b 8: U αi (v))) p 9: ρi (v) ← ℓ̄ 8i/(2 + Ni (v)) 10: end for [ BD (v, ρi (v)) then 11: if ΛDC ⊈ v∈Si
Add an uncovered ηn to Si with Ni (ηn ) = Niacc (ηn ) = 0 13: end if n o b i (v) + 2ρi (v) 14: Choose vi ∈ arg maxv∈Si U 15: Commit to ηt = vi and observe Zt = 1{Aηt } 16: Ni (vi ) ← Ni (vi )+1, Niacc (vi ) ← Niacc (vi )+Zt 17: end for 18: end for 12:
gη∗ (.), and does not observe samples with mean U(η). Instead, when the DC commits to ηt , it observes the binary acceptance indicator Zt , whose conditional expectation is α(η) by (4). Repeated plays of the same η therefore allow the DC to estimate α(η). The function Fη (.) then converts this estimate of α(η) into an estimate of the induced utility U(η). IV. M AIN R ESULTS In this section, we present the main results. Let Γ(η) ≜ U∗ΛDC − U(η),
(6)
for all η ∈ ΛDC . We impose the following assumptions, which are discussed in Appendix A. A1. For all η ∈ ΛDC , we assume that 0 ≤ U(η) ≤ 1. A2. We assume that there exists a metric D such that |U(η) − U(η ′ )| ≤ D(η, η ′ ) for all η, η ′ ∈ ΛDC . The diameter of a set S under D is defined as diam (S, D) ≜ supη,η′ ∈S D(η, η ′ ). We assume that diam (ΛDC , D) ≤ 1. A3. For all η ∈ ΛDC and all α, α′ ∈ [0, 1], we assume that |Fη (α) − Fη (α′ )| ≤ ℓ|α − α′ |. We define ℓ̄ ≜ max{1, ℓ}. A4. For every r ∈ (0, 1], define the gap annulus r Λr ≜ {η ∈ ΛDC : < Γ(η) ≤ r}. (7) 2 We assume that the game-of-coding instance IGoC ≜ (ΛDC , D, U) has (Cz , dz )-zooming dimension, meaning that for every r ∈ (0, 1], the set Λr can be covered by at most Cz r−dz sets of D-diameter at most 8r . For x ∈ R, let Π[0,1] (x) ≜ min{1, max{0, x}}. Also, for v ∈ ΛDC and r > 0, let BD (v, r) ≜ {η ∈ ΛDC : D(η, v) ≤ r}.
We now present Algorithm 1, which is based on the phasebased zooming algorithm of [48]. The algorithm runs in phases, where phase i has length 2i rounds. At the beginning of each phase, the active set is reset. We denote by Si the set of active thresholds in phase i. For each active threshold v ∈ Si , let Ni (v) be the number of times v has been played so far in phase i, and let Niacc (v) be the number of accepted plays. Thus, if v has been played in rounds t1 , . . . , tNi (v) of PNi (v) phase i, then Niacc (v) = j=1 Ztj . When Ni (v) > 0, the empirical acceptance probability is α bi (v) = Niacc (v)/Ni (v), b and the utility estimate is Ui (v) = Π[0,1] (Fv (b αi (v))). The confidence radius assigned to v in phase i is ρi (v) = p ℓ̄ 8i/(2 + Ni (v)). This radius captures the statistical unb i (v) and also determines the region of the certainty in U decision space represented by v, namely BD (v, ρi (v)). The b i (v) + 2ρi (v), where the optimistic index of v is Ii (v) = U first term estimates the utility and the second term provides an optimism bonus. The algorithm plays active thresholds with large optimistic index and activates a new threshold only when the current active balls do not cover the entire decision space. The intuition behind Algorithm 1 is simple. As an active threshold v is sampled more often, Ni (v) increases and ρi (v) decreases, giving a more accurate estimate of its utility. If some region of ΛDC is not covered by the current active balls, the algorithm activates a new threshold in that region. The algorithm plays the active threshold with the largest optimistic index Ii (v). In this way, the algorithm adaptively concentrates its search around thresholds that may be near-optimal. Theorem 1. Under the Assumptions A1–A4, let πZ be the policy induced by Algorithm 1. Then, for every T ≥ 2, 1 dz +1 (8) RegT (πZ ) = O Cz ℓ̄2 ln2 T dz +2 T dz +2 . Theorem 1 implies that since (dz + 1)/(dz + 2) < 1, we have RegT (πZ )/T → 0, as T → ∞. Thus, although the DC observes only binary acceptance feedback, its average loss relative to the best fixed threshold in hindsight vanishes. Moreover, The regret exponent in Theorem 1 is the same zooming-type exponent obtained for metric-space bandits with zooming dimension dz [48]. V. P ROOF OF T HEOREM 1 In this section, we prove Theorem 1. Note that the DC does not observe samples with mean U(η). Instead, by (4), it observes binary acceptance indicators with mean α(η). The next lemma shows that these observations still provide valid confidence intervals for the utility U(η) = Fη (α(η)). Lemma 1. For every phase i, every active threshold v ∈ Si and every time in phase i, with probability at least 1 − 8−i , b i (v) − U(v)| ≤ ρi (v). we have |U Proof. Fix a phase i, and let Vi,1 , . . . , Vi,Ji be the thresholds activated during this phase, listed in their activation order. Since phase i has length 2i and at most one new threshold can be activated in each round, we have Ji ≤ 2i .
For an activated threshold Vi,j , let Zi,j,1 , . . . , Zi,j,s denote the first s acceptance indicators observed Psfrom plays of Vi,j in phase i, and define α bi,j,s ≜ s−1 τ =1 Zi,j,τ . By (4), each acceptance indicator observed after committing to Vi,j has conditional mean α(Vi,j ). Therefore, Hoeffding’s inequality [49] gives, for every fixed j and s ≥ 1, p 16is ). Pr(|b αi,j,s − α(Vi,j )| > 8i/(2 + s)) ≤ 2 exp(− 2+s Since s/(2 + s) ≥ 1/3 for s ≥ 1, the right-hand side is at most 2e−16i/3 . There are at most 2i activated thresholds and at most 2i possible sample sizes for each threshold. Hence, by the union bound, the probability that any empirical acceptance estimate in phase i violates the above bound is at most 2i · 2i · 2e−16i/3 ≤ 8−i . Thus, with probability at least 1 − 8−i , for all activated thresholds Vi,j and all sample sizes s ≤ 2i , p (9) |b αi,j,s − α(Vi,j )| ≤ 8i/(2 + s). Now suppose this event holds, and let v ∈ Si be active. If Ni (v) = s > 0, then v = Vi,j for some j and α bi (v) = α bi,j,s . b i (v) = Π[0,1] (Fv (b By definition, U αi (v))). Since U(v) ∈ [0, 1] by Assumption A1 and projection onto [0, 1] is non-expansive, b i (v) − U(v)| ≤ |Fv (b |U αi (v)) − Fv (α(v))| .
(10)
b Using Assumption A3 p and (9), we obtain |Ui (v) − U(v)| ≤ ℓ |b αi (v) − α(v)| ≤ ℓ̄ 8i/(2 + Ni (v)) = ρi (v). b i (v) = 0. By If Ni (v) = 0, then Algorithm 1 sets U p b Assumption A1, |Ui (v)−U(v)| ≤ 1. Also, ρi (v) = ℓ̄ 8i/2 = √ 2ℓ̄ i ≥ 1, since i ≥ 1 and ℓ̄ ≥ 1. Hence Lemma 1 also holds when Ni (v) = 0. This proves the lemma. To complete the proof, we invoke [48, Theorem 4.2]. The theorem applies to the phase-based zooming algorithm of [48, Algorithm 2.3], which maintains a finite active set of arms in each phase. At each round, the algorithm checks whether the confidence balls around the active arms cover the whole metric space. If not, it activates an uncovered arm. It then assigns each active arm v the optimistic index µ bt (v) + 2b rt (v) and plays an active arm with the largest index, where µ bt (v) is an estimator of the payoff and rbt (v) is its confidence radius. In the notation of [48, Theorem 4.2], the bandit instance is (L, X, µ), where X is the arm set, L is the metric, and µ is the payoff function. The theorem assumes that µ : X → [0, 1], diam(X, L) ≤ 1, and |µ(x) − µ(y)| ≤ L(x, y) for all x, y ∈ X. It also defines µ∗ ≜ supx∈X µ(x) and ∆(x) ≜ µ∗ − µ(x). The theorem requires the instance to have zooming dimension d with constant c, meaning that, for every r ∈ (0, 1], the set Xr ≜ {x ∈ X : r/2 < ∆(x) ≤ r} can be covered by at most cr−d sets of L-diameter at most r/8. It also requires clean phases, namely |b µt (v)−µ(v)| ≤ rbt (v) for every active arm v and every time t in phase i, with probability at least 1 − 8−i . Finally, the radius must be smooth, meaning (3/4)b rt (v) ≤ rbt+1 (v) ≤ rbt (v), and (q, c0 )-good, meaning that ∆(v) ≤ 4b rt (v) implies nt (v) ≤ c0 i ∆(v)−q , where nt (v) is the number of times v has been played earlier in phase i.
Under these conditions, if d + q > 1, [48, Theorem 4.2] implies that the regret of the zooming policy satisfies 1 1 RegT (π) ≤ C0 cc0 ln2 (eT ) d+q T 1− d+q , (11) for a universal constant C0 > 0. We now verify these conditions for Algorithm 1. We identify X = ΛDC , L = D, and µ = U. By Assumption A1, µ(η) = U(η) ∈ [0, 1] for all η ∈ ΛDC . By Assumption A2, diam(ΛDC , D) ≤ 1 and |µ(η) − µ(η ′ )| = |U(η) − U(η ′ )| ≤ D(η, η ′ ) for all η, η ′ ∈ ΛDC . Thus, the boundedness, diameter, and Lipschitz requirements are satisfied. The optimal value in the induced bandit instance is µ∗ = supη∈ΛDC U(η) = U∗ΛDC . Hence the bandit gap is ∆(η) = µ∗ − µ(η) = Γ(η), so the set Xr is exactly the set Λr in (7). By Assumption A4, the zooming-dimension condition holds with c = Cz and d = dz . It remains to verify the algorithmic conditions. Under the above identification, Algorithm 1 has the same phase structure, activation rule, covering rule, and optimistic-index rule as the phase-based zooming algorithm in [48, Algorithm 2.3]. Its b i (v) and rbt (v) = ρi (v), estimator and radius are µ bt (v) = U where i is the current phase. Lemma 1 proves the cleanphase condition. It remains only to prove the smoothness and goodness conditions, where we prove in the following lemma. Lemma 2. for all i, the radius ρi (v) satisfies the smoothness condition. Moreover, it is (2, 128ℓ̄2 )-good. Proof. Let n = Ni (v) be the number of times v has been played so far in phase i. If v is not played in the next round, then the radius does not change.pIf v is played, then n becomes n + 1, and based on ρi (v) = ℓ̄ 8i/(2 + Ni (v)), we have r r ρi (n + 1) 2+n 2 3 = ≥ > . (12) ρi (n) 3+n 3 4 + Therefore, (3/4)ρi (v) ≤ ρ+ i (v) ≤ ρi (v), where ρi (v) is the radius after the next round. This proves smoothness. We now provepgoodness. Suppose Γ(v) ≤ 4ρi (v). This gives Γ(v) ≤ 4ℓ̄ 8i/(2 + Ni (v)). Squaring both sides and rearranging yields 2 + Ni (v) ≤ 128ℓ̄2 i Γ(v)−2 , and therefore Ni (v) ≤ 128ℓ̄2 i Γ(v)−2 . Since Γ(v) = ∆(v), this is the goodness condition with q = 2 and c0 = 128ℓ̄2 .
We now apply [48, Theorem 4.2] with c = Cz , d = dz , q = 2, and c0 = 128ℓ̄2 . Since dz + 2 > 1, (11) gives 1 dz +1 RegT (πZ ) ≤ C0 128Cz ℓ̄2 ln2 (eT ) dz +2 T dz +2 . (13) This completes the proof of Theorem 1. VI. N UMERICAL E XPERIMENTS In this section, we compare Algorithm 1 with the explorethen-commit baseline of [26]. In the unknown-adversary formulation of [26], the DC first explores for a fixed number of rounds and is evaluated only through the final selected threshold η̂, with guarantee Pr U∗ΛDC − U(η̂) > λ < δ. In contrast, our formulation evaluates the entire learning trajectory through the cumulative regret in (5).
Fig. 2. Induced DC utility as a function of the acceptance threshold η. The dashed vertical line marks the optimal threshold η ∗ = 12.7189.
Fig. 3. Cumulative regret over T = 100000 rounds. The proposed algorithm achieves lower trajectory regret than the explore-then-commit baseline.
We consider the two-node setting from Section II. The honest noise is nh ∼ Unif[−∆, ∆] with ∆ = 1, and the threshold space is ΛDC = [2, 30]. For each fixed η, the adversary chooses the induced acceptance probability as α(η) ∈ arg max0<α≤1 QAD (cη (α), α). The corresponding DC utility is U(η) = QDC (cη (α(η)), α(η)). In the experiment, we use QAD (MMSE, PA) = ln(MMSE) + 0.2 ln(PA) and QDC (MMSE, PA) = −MMSE + 200PA. Using the procedure described in [22, Algorithm 1], the best threshold over [2, 30] is η ∗ = 12.7189, with U∗2,30 = 44.7935. Fig. 2 shows the induced DC utility curve, where the dashed vertical line marks η ∗ . For the explore-then-commit baseline, we set λ = 0.5 and δ = 0.05. Following [26], this gives n = 13 and k = 3280. Hence, the baseline explores n+1 = 14 grid points and spends (n + 1)k = 45920 rounds in the exploration phase. We run both algorithms for T = 100000 rounds. In each round, we sample u ∼ Unif[−M, M ] and na is sampled following the procedure described in [22, Algorithm 2]. The baseline spends 45920 rounds exploring and then commits for the remaining 54080 rounds. It selects η̂old = 10.6154, achieving final cumulative regret 14058.9731. Algorithm 1 activates only 11 thresholds over the trajectory. It achieves final cumulative regret 8852.6987. Fig. 3 compares the cumulative regret of the two algorithms. VII. ACKNOWLEDGMENT This work has been partially supported by the National Science Foundation under Grant CCF-2348638.
R EFERENCES [1] V. Guruswami, A. Rudra, and M. Sudan, Essential Coding Theory. Draft is Available, 2022. [2] R. Yosibash and R. Zamir, “Frame codes for distributed coded computation,” in 2021 11th International Symposium on Topics in Coding (ISTC), pp. 1–5, 2021. [3] T. Jahani-Nezhad and M. A. Maddah-Ali, “Codedsketch: A coding scheme for distributed computation of approximated matrix multiplication,” IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 4185–4196, 2021. [4] R. M. Roth, “Analog error-correcting codes,” IEEE Transactions on Information Theory, vol. 66, no. 7, pp. 4075–4088, 2020. [5] P. Moradi, H. Akbarinodehi, and M. A. Maddah-Ali, “General coded computing: Adversarial settings,” arXiv preprint arXiv:2502.08058, 2025. [6] S. Dutta, M. Fahim, F. Haddadpour, H. Jeong, V. Cadambe, and P. Grover, “On the optimal recovery threshold of coded matrix multiplication,” IEEE Transactions on Information Theory, vol. 66, no. 1, pp. 278–301, 2019. [7] S. Dutta, V. Cadambe, and P. Grover, “Short-dot: Computing large linear transforms distributedly using coded short dot products,” Advances In Neural Information Processing Systems, vol. 29, 2016. [8] Q. Yu, M. Maddah-Ali, and S. Avestimehr, “Polynomial codes: an optimal design for high-dimensional coded matrix multiplication,” Advances in Neural Information Processing Systems, vol. 30, 2017. [9] Q. Yu and A. S. Avestimehr, “Entangled polynomial codes for secure, private, and batch distributed matrix multiplication: Breaking the" cubic" barrier,” in 2020 IEEE International Symposium on Information Theory (ISIT), pp. 245–250, IEEE, 2020. [10] Q. Yu, S. Li, N. Raviv, S. M. M. Kalan, M. Soltanolkotabi, and S. A. Avestimehr, “Lagrange coded computing: Optimal design for resiliency, security, and privacy,” in The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1215–1225, PMLR, 2019. [11] J. Sliwinski and R. Wattenhofer, “Blockchains cannot rely on honesty,” in The 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2020), 2019. [12] R. Han, Z. Sui, J. Yu, J. Liu, and S. Chen, “Fact and fiction: Challenging the honest majority assumption of permissionless blockchains,” in Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security, pp. 817–831, 2021. [13] J. S. Gans and H. Halaburda, “"Zero Cost" majority attacks on permissionless blockchains,” tech. rep., National Bureau of Economic Research, 2023. [14] N. S. Bitcoin, “Bitcoin: A peer-to-peer electronic cash system,” 2008. [15] V. Buterin et al., “Ethereum white paper,” GitHub repository, vol. 1, pp. 22–23, 2013. [16] S. Ruoti, B. Kaiser, A. Yerukhimovich, J. Clark, and R. Cunningham, “SoK: Blockchain technology and its potential use cases,” arXiv preprint arXiv:1909.12454, 2019. [17] M. Shafay, R. W. Ahmad, K. Salah, I. Yaqoob, R. Jayaraman, and M. Omar, “Blockchain for deep learning: review and open challenges,” Cluster Computing, vol. 26, no. 1, pp. 197–221, 2023. [18] S. Ding and C. Hu, “Survey on the convergence of machine learning and blockchain,” in Proceedings of SAI Intelligent Systems Conference, pp. 170–189, Springer, 2022. [19] S. Kayikci and T. M. Khoshgoftaar, “Blockchain meets machine learning: a survey,” Journal of Big Data, vol. 11, no. 1, pp. 1–29, 2024. [20] R. Tian, L. Kong, X. Min, and Y. Qu, “Blockchain for ai: A disruptive integration,” in 2022 IEEE 25th International Conference on Computer Supported Cooperative Work in Design (CSCWD), pp. 938–943, IEEE, 2022. [21] K. Salah, M. H. U. Rehman, N. Nizamuddin, and A. Al-Fuqaha, “Blockchain for ai: Review and open research challenges,” IEEE Access, vol. 7, pp. 10127–10149, 2019. [22] H. A. Nodehi, V. R. Cadambe, and M. A. Maddah-Ali, “Game of coding: Beyond honest-majority assumptions,” IEEE Transactions on Information Theory (submitted), 2024. [23] H. A. Nodehi, P. Moradi, S. Mohajer, and M. A. Maddah-Ali, “Game of coding for vector-valued computations,” arXiv preprint arXiv:2602.04810, 2026. [24] H. A. Nodehi, V. R. Cadambe, and M. A. Maddah-Al, “Game of coding: Sybil resistant decentralized machine learning with minimal trust assumption,” arXiv preprint, 2024. https://arxiv.org/abs/2410.05540.
[25] H. A. Nodehi, V. R. Cadambe, and M. A. Maddah-Ali, “Game of coding: Coding theory in the presence of rational adversaries, motivated by decentralized machine learning,” arXiv preprint arXiv:2601.02313, 2026. [26] H. Akbari Nodehi, P. Moradi, and M. A. Maddah-Ali, “Game of coding with an unknown adversary,” in 2025 IEEE International Symposium on Information Theory (ISIT), (Ann Arbor, MI, USA), 2025. [27] V. Conitzer and T. Sandholm, “Computing the optimal strategy to commit to,” in Proceedings of the 7th ACM conference on Electronic commerce, pp. 82–90, 2006. [28] J. Gan, M. Han, J. Wu, and H. Xu, “Robust stackelberg equilibria,” arXiv preprint arXiv:2304.14990, 2023. [29] J. Letchford, V. Conitzer, and K. Munagala, “Learning and approximating the optimal strategy to commit to,” in Algorithmic Game Theory: Second International Symposium, SAGT 2009, Paphos, Cyprus, October 18-20, 2009. Proceedings 2, pp. 250–262, Springer, 2009. [30] A. Blum, N. Haghtalab, and A. D. Procaccia, “Learning optimal commitment to overcome insecurity,” Advances in Neural Information Processing Systems, vol. 27, 2014. [31] B. Peng, W. Shen, P. Tang, and S. Zuo, “Learning optimal strategies to commit to,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 2149–2156, 2019. [32] P. G. Sessa, I. Bogunovic, M. Kamgarpour, and A. Krause, “Learning to play sequential games versus unknown opponents,” Advances in neural information processing systems, vol. 33, pp. 8971–8981, 2020. [33] M.-F. Balcan, A. Blum, N. Haghtalab, and A. D. Procaccia, “Commitment without regrets: Online learning in stackelberg security games,” in Proceedings of the sixteenth ACM conference on economics and computation, pp. 61–78, 2015. [34] N. Haghtalab, T. Lykouris, S. Nietert, and A. Wei, “Learning in stackelberg games with non-myopic agents,” in Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 917–918, 2022. [35] J. Dong, A. Roth, Z. Schutzman, B. Waggoner, and Z. S. Wu, “Strategic classification from revealed preferences,” in Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 55–70, 2018. [36] R. Kleinberg and T. Leighton, “The value of knowing a demand curve: Bounds on regret for online posted-price auctions,” in 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pp. 594–605, IEEE, 2003. [37] T. L. Lai and H. Robbins, “Asymptotically efficient adaptive allocation rules,” Advances in Applied Mathematics, vol. 6, no. 1, pp. 4–22, 1985. [38] P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit problem,” Machine Learning, vol. 47, no. 2–3, pp. 235–256, 2002. [39] S. Bubeck and N. Cesa-Bianchi, “Regret analysis of stochastic and nonstochastic multi-armed bandit problems,” Foundations and Trends in Machine Learning, vol. 5, no. 1, pp. 1–122, 2012. [40] T. Lattimore and C. Szepesvári, Bandit Algorithms. Cambridge University Press, 2020. [41] A. Slivkins, “Introduction to multi-armed bandits,” Foundations and Trends in Machine Learning, vol. 12, no. 1–2, pp. 1–286, 2019. [42] R. Agrawal, “The continuum-armed bandit problem,” SIAM Journal on Control and Optimization, vol. 33, no. 6, pp. 1926–1951, 1995. [43] R. D. Kleinberg, “Nearly tight bounds for the continuum-armed bandit problem,” in Advances in Neural Information Processing Systems, vol. 17, 2004. [44] P. Auer, R. Ortner, and C. Szepesvári, “Improved rates for the stochastic continuum-armed bandit problem,” in Proceedings of the 20th Annual Conference on Learning Theory, pp. 454–468, Springer, 2007. [45] R. Kleinberg, A. Slivkins, and E. Upfal, “Multi-armed bandits in metric spaces,” in Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 681–690, 2008. [46] S. Bubeck, R. Munos, G. Stoltz, and C. Szepesvári, “X-armed bandits,” Journal of Machine Learning Research, vol. 12, pp. 1655–1695, 2011. [47] H. Von Stackelberg, Market structure and equilibrium. Springer Science & Business Media, 2010. [48] R. Kleinberg, A. Slivkins, and E. Upfal, “Multi-armed bandits in metric spaces,” in Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 681–690, 2008. [49] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” The collected works of Wassily Hoeffding, pp. 409–426, 1994.
A PPENDIX A D ISCUSSION OF A SSUMPTIONS AND Z OOMING D IMENSION
Then D is again a metric. This is due the fact that for any a, b ≥ 0, we have
This appendix discusses the assumptions used in Theorem 1.
min{a + b, 1} ≤ min{a, 1} + min{b, 1}.
A. Utility Normalization Theorem 1 assumes 0 ≤ U(η) ≤ 1,
∀η ∈ ΛDC .
(14)
This is a standard normalization. Suppose instead that the induced utility is bounded as Umin ≤ U(η) ≤ Umax ,
∀η ∈ ΛDC ,
Indeed, if a < 1 and b < 1, then the right-hand side is a + b, and the inequality is immediate. If either a ≥ 1 or b ≥ 1, then the right-hand side is at least one, while the left-hand side is at most one. Therefore, by this new construction, diam (ΛDC , D) ≤ 1.
(26)
(15)
Moreover, the Lipschitz condition is preserved. If D0 (η, η ′ ) < 1, then D(η, η ′ ) = D0 (η, η ′ ), so (23) gives the result. If D0 (η, η ′ ) ≥ 1, then D(η, η ′ ) = 1. Since the utility is normalized, 0 ≤ U(η) ≤ 1, we have
(16)
|U(η) − U(η ′ )| ≤ 1 = D(η, η ′ ).
where RU ≜ Umax − Umin .
(25)
(27)
If RU = 0, then all thresholds have the same utility and the regret is identically zero. Otherwise, define the normalized utility
Therefore, replacing D0 by D does not change the validity of the Lipschitz assumption.
U(η) − Umin e U(η) ≜ . RU
(17)
e 0 ≤ U(η) ≤ 1.
(18)
Recall that for each r ∈ (0, 1], the zooming dimension examines the gap annulus o n r (28) Λr = η ∈ ΛDC : < Γ(η) ≤ r . 2 If Λr can be covered by at most Cz r−dz sets of diameter at most r/8, then dz measures the effective dimension of the region where the regret gap is of order r. Smaller dz means fewer distinguishable near-optimal thresholds and a faster regret rate. The following examples compute dz explicitly.
Then
The corresponding optimal value is e∗ = U
U∗ΛDC − Umin . RU
(19)
Therefore, the normalized gap satisfies
Example 1. Let
e ∗ − U(η) e e Γ(η) ≜U U∗ − U(η) Γ(η) = ΛDC = . RU RU
X = [a, b] ⊂ R,
g (π) = 1 Reg (π). Reg T T RU
(21)
Xr ⊆ X.
B. Metric Normalization Theorem 1 assumes that the metric space has diameter at most one: (22)
|U(η) − U(η )| ≤ D0 (η, η ),
′
∀η, η ∈ ΛDC .
Therefore, the covering condition holds with dz = 1 and Cz = 8L(b − a) + 1. Hence the exact zooming dimension is always bounded above by one under the scaled absolute-value metric. Example 2. Let D(x, y) = |x − y|,
(32)
and let (23)
µ(x) = 1 − x.
(33)
∆(x) = µ∗ − µ(x) = x.
(34)
Then µ∗ = 1 and
If the diameter of D0 is larger than one, define D(η, η ′ ) ≜ min{D0 (η, η ′ ), 1}.
(30)
Partition [a, b] into intervals of Euclidean length at most r/(8L). Each such interval has D-diameter at most r/8. The number of intervals is at most 8L(b − a) ≤ (8L(b − a) + 1) r−1 . (31) r
X = [0, 1],
This is only a normalization. Suppose first that we have a metric D0 such that ′
(29)
For any utility µ : X → [0, 1] that is Lipschitz with respect to D, the zooming dimension is at most one. Indeed, for any r ∈ (0, 1],
A regret bound for the normalized utility therefore gives the corresponding original-scale regret bound after multiplication by RU . Hence, assuming (14) does not change the substance of the result.
diam (ΛDC , D) ≤ 1.
D(x, y) = min{L|x − y|, 1}.
(20)
Thus, for any policy π,
′
C. Why the Zooming Dimension Appears
(24)
Solving e−1/x = r/2 gives
For r ∈ (0, 1], n o r i r Xr = x ∈ [0, 1] : < x ≤ r = ,r . (35) 2 2 This interval has length r/2. It can be covered by at most four intervals of length r/8. Therefore, the covering number is bounded by a constant independent of r, so dz = 0.
(36)
x=
Xr =
1 1 , . ln(2/r) ln(1/r)
(51)
The length of this interval is ln 2 . ln(1/r) ln(2/r)
|Xr | = D(x, y) = |x − y|,
(50)
Thus
Example 3. Let X = [0, 1],
1 . ln(2/r)
(37)
(52)
Covering it by intervals of length r/8 requires on the order of
and let, for p ≥ 1, xp µ(x) = 1 − . p
1 r ln (1/r)
(38)
sets. This is at most a constant times r−1 , so dz = 1 is sufficient. However, for any d < 1,
Then µ is 1-Lipschitz on [0, 1] because |µ′ (x)| = xp−1 ≤ 1.
(39)
rd−1 1/(r ln2 (1/r)) = 2 →∞ −d r ln (1/r)
The gap is ∆(x) =
(53)
2
xp . p
(40)
as r ↓ 0.
Therefore no d < 1 is sufficient, and the exact zooming dimension is
The annulus Xr is
dz = 1.
Xr =
xp r ≤r . x ∈ [0, 1] : < 2 p
(41)
Xr =
pr 1/p 2
, (pr)
1/p
(55)
Example 5 (Snowflake metric can give dz > 1). Let X = [0, 1],
Equivalently,
(54)
Da (x, y) = |x − y|a ,
0 < a < 1. (56)
This is a valid metric. Let
.
(42)
Its Euclidean length is
µ(x) = 1 − x.
(57)
Then
|Xr | = p
1/p
1−2
−1/p
r
1/p
.
(43)
A set of D-diameter at most r/8 has Euclidean length at most r/8. Therefore, the covering number is on the order of 1 r1/p = r−(1− p ) . r Thus the exact zooming dimension is
(44)
1 dz = 1 − . p
(45)
Example 4. Let D(x, y) = |x − y|,
X = [0, 1],
(46)
and define the gap by ∆(x) = e−1/x ,
∆(0) = 0,
x > 0.
Let µ(x) = 1 − ∆(x). For small r, the annulus is n o r Xr = x : < e−1/x ≤ r . 2
(47)
(48)
Solving e−1/x = r gives x=
1 . ln(1/r)
(49)
|µ(x) − µ(y)| = |x − y| ≤ |x − y|a = Da (x, y),
(58)
so µ is 1-Lipschitz with respect to Da . The gap is ∆(x) = x, so r i ,r . (59) Xr = 2 This annulus has Euclidean length r/2. A set with Da diameter at most r/8 has Euclidean diameter at most r 1/a . (60) 8 Therefore, the number of sets required is on the order of 1 r = r−( a −1) . (61) r1/a Hence 1 dz = − 1. (62) a For example, if a = 1/3, then dz = 2.