Paper deep dive
Cost of Structural Learning Under Censored Feedback: A Threshold-Bandit Approach
Michael Ledford, William Regli
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 7/8/2026, 9:04:45 PM
Summary
The paper introduces the Threshold-Activated Cooperative Multi-Armed Bandit (TAC-MAB) to address multi-agent coordination under censored feedback, where tasks only yield rewards if a coalition meets an unknown size threshold. It proposes a centralized algorithm (C-TAC) with O(log T) cumulative regret, decomposed into structural search and statistical monitoring components, and a decentralized event-triggered protocol (D-TAC) that reduces communication by 23x while maintaining feasibility alignment. The work characterizes the coordination cost of learning under censored feedback and demonstrates that near-centralized efficiency is achievable without continuous synchronization.
Entities (9)
Relation Signals (7)
TAC-MAB → addresses → Censored Feedback
confidence 95% · This censorship creates an identifiability problem... We formalize this setting as the Threshold-Activated Cooperative Multi-Armed Bandit (TAC-MAB)
William Regli → affiliatedwith → University of Maryland, College Park
confidence 95% · Michael Ledford & William Regli University of Maryland, College Park
Michael Ledford → affiliatedwith → University of Maryland, College Park
confidence 95% · Michael Ledford & William Regli University of Maryland, College Park
D-TAC → reduces → Communication Cost
confidence 95% · D-TAC achieves a 23x reduction in communication relative to the centralized baseline
C-TAC → achieves → O(log T) Cumulative Regret
confidence 90% · a centralized algorithm (C-TAC) achieves cumulative regret O(log T)
TAC-MAB → formulates → 0/1 Knapsack Problem
confidence 90% · optimal allocation solves a 0/1 knapsack with weights τk and values pkvk
C-TAC → utilizes → UCB1
confidence 85% · using UCB1-based indices
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In many multi-agent applications, tasks yield rewards only when executed by a coalition meeting an unknown size threshold; otherwise, feedback is fully censored. This censorship creates an identifiability problem: agents cannot distinguish stochastic failure from insufficient coordination. We formalize this setting as the Threshold-Activated Cooperative Multi-Armed Bandit (TAC-MAB) and analyze it under both centralized and decentralized coordination. We show that a centralized algorithm (C-TAC) achieves cumulative regret O(log T), decomposed into a structural-search term that captures the cost of resolving feasibility under censored feedback and a statistical-monitoring term for value estimation. We then introduce D-TAC, a decentralized event-triggered protocol in which agents synchronize only when their structural beliefs change. Empirically, D-TAC achieves a 23x reduction in communication relative to the centralized baseline while preserving feasibility alignment under conservative belief fusion. These results characterize the coordination cost of learning under censored feedback and show that near-centralized communication efficiency is achievable without continuous synchronization.
Tags
Links
- Source: https://arxiv.org/abs/2605.27076v1
- Canonical: https://arxiv.org/abs/2605.27076v1
Trouble viewing inline? Open PDF directly →
Full Text
47,400 characters extracted from source content.
Expand or collapse full text
Cost of Structural Learning under Censored Feedback: A Threshold-Bandit Approach Michael Ledford &William Regli University of Maryland, College Park mledfor, regli@umd.edu Abstract In many multi-agent applications, tasks yield rewards only when executed by a coalition meeting an unknown size threshold; otherwise, feedback is fully censored. This censorship creates an identifiability problem: agents cannot distinguish stochastic failure from insufficient coordination. We formalize this setting as the Threshold-Activated Cooperative Multi-Armed Bandit (TAC-MAB) and analyze it under both centralized and decentralized coordination. We show that a centralized algorithm (C-TAC) achieves cumulative regret O(logT)O( T), decomposed into a structural-search term that captures the cost of resolving feasibility under censored feedback and a statistical-monitoring term for value estimation. We then introduce D-TAC, a decentralized event-triggered protocol in which agents synchronize only when their structural beliefs change. Empirically, D-TAC achieves a 23×23× reduction in communication relative to the centralized baseline while preserving feasibility alignment under conservative belief fusion. These results characterize the coordination cost of learning under censored feedback and show that near-centralized communication efficiency is achievable without continuous synchronization. 1 Introduction Cooperative multi-agent systems often operate in environments where task success depends on coordinated action by multiple agents, and execution feedback becomes informative only when a sufficient coalition acts jointly. Consider domains such as search-and-rescue Cao et al. (2024), where multiple agents explore an environment and success depends on deploying a coalition of the right size acting in unison. Similar coordination dependencies arise in distributed sensing, signal jamming, and logistics coordination, where agents must combine capabilities to achieve an outcome. In these settings, the coalition size required to produce informative feedback can be viewed as a latent feasibility threshold, a quantitative constraint that is hidden from agents but determines whether a joint action yields any reward. When too few agents are deployed, execution fails silently without producing informative feedback, making stochastic failure indistinguishable from insufficient coordination. Existing models for cooperative decision making typically assume execution feedback is informative whenever agents act, enabling learning through independent or weakly coordinated exploration Landgren et al. (2021). This challenge persists across modeling frameworks: MARL methods under sparse rewards Mahajan et al. (2019) treat feasibility as a learning problem but do not exploit its structural nature, while Dec-POMDP formulations Oliehoek et al. (2016) assume observation models that censored feedback violates. A multi-armed bandit framing, by contrast, isolates the allocation decision from state and policy dynamics, making the coordination cost itself analytically tractable. When task outcomes are gated by unknown coalition-size requirements, execution attempts below the feasibility threshold yield fully censored feedback, and the probability of independently forming a feasible coalition vanishes as coalition-size requirements grow. Independent exploration thus cannot reliably resolve feasibility on its own. Coordination requirements could in principle be specified offline, but feasibility often depends on transient or adversarial conditions that resist pre-programming, and offline training suffers from the sim-to-real gap Tobin et al. (2017). Teams must therefore infer feasibility online. Yet committing more agents is not free: practical deployments incur communication and execution costs Chakraborty et al. (2017) (energy, bandwidth, time) when allocating larger coalitions. This creates an exploration dilemma: independent learning fails under censored feedback, while naive full coordination is prohibitively costly. We measure the resulting inefficiency using regret, which captures the cost of operating under incorrect feasibility beliefs. To address this challenge, we introduce the Threshold-Activated Cooperative Multi-Armed Bandit (TAC-MAB), a model that isolates the structural difficulty of feasibility-gated feedback. We first analyze an idealized centralized baseline (C-TAC) and prove O(logT)O( T) cumulative regret, decomposed into a structural-search term that captures the cost of resolving feasibility under censored feedback and a statistical-monitoring term for value estimation (Theorem 1). We then propose D-TAC, a decentralized event-triggered protocol in which agents synchronize only when structural beliefs change. Once structural beliefs align, D-TAC executes the same plan as C-TAC and empirically approaches its asymptotic performance, modulo a transient during the structural-learning phase (Section 4). Empirically, D-TAC achieves a 23×23× reduction in communication relative to the centralized baseline while preserving feasibility alignment through conservative belief fusion. 2 Problem Formulation We study a cooperative multi-agent learning problem in which M agents must allocate themselves across K tasks, where each task requires an unknown integer number of agents to activate. Below this threshold, execution attempts yield no informative feedback. We refer to this setting as the Threshold-Activated Cooperative Multi-Armed Bandit (TAC-MAB). TAC-MAB is a multi-agent specialization of the censored semi-bandit framework of Verma et al. Verma et al. (2019), which studies single-learner allocation with continuous-valued thresholds and a divisible resource budget. Our setting differs in three structural ways: the resource is a coalition of M distinct agents (rather than a divisible budget), thresholds are integer-valued (rather than continuous), and observations are partitioned by agent assignment under decentralized execution. These differences enable the study of decentralized coordination protocols, which we develop in Section 4. 2.1 Agents and Task Types The team consists of M homogeneous agents indexed by i∈1,…,Mi∈\1,…,M\ operating over a finite horizon T. The environment contains K stationary tasks indexed by k∈1,…,Kk∈\1,…,K\, each characterized by a feasibility threshold τk∈ℤ≥1 _k _≥ 1 (the minimum coalition size required to activate task k, possibly with τk>M _k>M for structurally infeasible tasks), a success probability pk∈[0,1]p_k∈[0,1] (the probability that task k succeeds when executed by a feasible coalition), and a task value vk∈ℝ+v_k _+ (the reward obtained on a successful execution). These parameters are stationary over the horizon. Together with the fixed feasibility set C defined in Section 2.4, this makes the oracle’s optimal allocation ⋆ c time-invariant. An instance of TAC-MAB is identified by (,,,M,T)( τ, p, v,M,T). The vectors τ and p are unknown and must be learned through interaction. The remaining quantities are known to the team: K, M, T, the per-task values =vkk=1K v=\v_k\_k=1^K, and a known lower bound pmin∈(0,1]p_ ∈(0,1] such that pk≥pminp_k≥ p_ for all feasible tasks (i.e., tasks with τk≤M _k≤ M). We treat v as known; this is standard in resource-allocation problems with pre-specified task values Verma et al. (2019) and lets us isolate the cost of learning (,)( τ, p). Extending to unknown v is left to future work. We assume K>MK>M throughout, the regime in which the team cannot evaluate all tasks in parallel and must select a subset to attempt each round. This is what makes the allocation problem non-trivial: even with full knowledge of (,,)( τ, p, v), the optimal allocation solves a 0/1 knapsack with weights τk _k and values pkvkp_kv_k. 2.2 Joint Actions and Censored Feedback In round t, the team selects t=(c1,t,…,cK,t) c_t=(c_1,t,…,c_K,t) with ck,t∈0,…,Mc_k,t∈\0,…,M\ and ∑kck,t≤M _kc_k,t≤ M. For each task k and round t, Xk,t∼Bernoulli(pk)X_k,t (p_k) is drawn independently across tasks and rounds. The observed outcome is Yk,t=Xk,tvk,if ck,t≥τk,0,if ck,t<τkY_k,t= casesX_k,t\,v_k,&if c_k,t≥ _k,\\ 0,&if c_k,t< _k cases (1) Censoring at observation, not generation. Xk,tX_k,t is realized regardless of coalition size, but the team observes Yk,t=0Y_k,t=0 deterministically when ck,t<τkc_k,t< _k. Crucially, when Yk,t=0Y_k,t=0, the team cannot distinguish censoring (ck,t<τkc_k,t< _k) from stochastic failure (Xk,t=0X_k,t=0 with ck,t≥τkc_k,t≥ _k). This is the identifiability challenge that motivates our analysis. Observation convention. We treat Yk,tY_k,t as the per-task aggregate outcome; this is what enters the regret definition. In our implementation, the reward vkv_k is distributed evenly across the coalition assigned to task k; each agent on task k thus observes the success indicator Yk,t>01\Y_k,t>0\ via its own share. The team-level cumulative reward and our regret analysis are invariant to this distribution choice. 2.3 Observations and Communication Each agent i observes only the outcome Yk,tY_k,t for its assigned task at round t, via the share convention above. Agents do not observe outcomes of other tasks, nor the thresholds τk _k, but each agent knows the coalition size assigned to its own task (via the coordinator in the centralized setting and via the protocol in the decentralized setting). A successful outcome (Yk,t>0Y_k,t>0) reveals that the executed coalition was feasible and that Xk,t=1X_k,t=1; a failed outcome (Yk,t=0Y_k,t=0) is uninformative about which of the two failure modes occurred. Agents may communicate at the end of each round; communication, when it occurs, is reliable and synchronous within the round. We abstract communication cost as the number of messages exchanged per round (independent of payload size), corresponding to a shared-medium broadcast model for one-to-many transmissions and point-to-point unicast for direct messages. A single broadcast counts as one message, while all-to-all exchange among M agents incurs (M2)O(M^2) messages. We analyze TAC-MAB under two coordination architectures. In the centralized architecture, all observations in a round are available to a coordinator that maintains global estimates and selects joint actions; this serves as a theoretical baseline (Section 3). In the decentralized architecture, each agent has access only to its own observations and may exchange messages with peers subject to the cost model above; coordination protocols are developed in Section 4. In our centralized analysis (Section 3), we treat coordinator-to-agent communication as a zero-cost idealization to isolate the statistical cost of learning; decentralized communication costs are accounted for in Section 4. 2.4 Objective and Regret The objective of the team is to maximize cumulative reward over the horizon T. This requires solving two coupled sub-problems online: 1. Threshold learning under censored feedback. Estimate τ from observed outcomes, where failures below τk _k provide no information distinguishing insufficient coordination from stochastic failure. 2. Optimal allocation under resource constraints. Given threshold estimates τ and value estimates μ, select an allocation ∈ c that maximizes expected reward, where =∈ℤ≥0K:∑kck≤MC=\ c ^K_≥ 0: _kc_k≤ M\. Since K>MK>M, this is a 0/1 knapsack. These sub-problems are coupled through the per-round resource constraint: probing a task’s threshold requires committing agents to it, which forecloses other allocations that round. Threshold learning therefore competes with reward collection for the same scarce resource. Let μk=pkvk _k=p_kv_k. The oracle benchmark knows (,)( τ, μ) and selects ⋆∈argmax∈∑k=1Kck≥τkμk, c ∈ _ c _k=1^K1\c_k≥ _k\\, _k, (2) which does not depend on t by stationarity. We assume a unique maximizer for clarity. Let μ⋆=∑k=1Kck⋆≥τkμkμ \;=\; _k=1^K1\c _k≥ _k\\, _k denote the expected reward of this optimal joint allocation. Cumulative regret is R(T)=[∑t=1T(μ⋆−∑k=1Kck,t≥τkXk,tvk)],R(T)=E\! [ _t=1^T (μ - _k=1^K1\c_k,t≥ _k\\,X_k,t\,v_k ) ], (3) where the expectation is over Xk,t\X_k,t\ and any randomness in the learning policy. The oracle is assumed to solve the allocation optimization exactly; regret is measured relative to this ideal benchmark. Regret in TAC-MAB decomposes into two sources: the cost of resolving threshold uncertainty under censored feedback, and the cost of estimating the success probabilities p under the integer knapsack constraint. Theorem 1 (Section 3) characterizes both. 3 Centralized Coordination Baseline We first analyze TAC-MAB under an idealized centralized coordination architecture in which a coordinator observes all task outcomes immediately and broadcasts joint allocations at zero cost. This baseline isolates the statistical difficulty of learning under censored feedback from the logistical cost of coordination, and provides a regret reference for the decentralized strategies in Section 4. 3.1 Structural and Statistical Uncertainty Even with perfect information sharing, learning under TAC-MAB couples two sources of uncertainty. Structural uncertainty arises from unknown feasibility thresholds τ that gate informative feedback: when a coalition is below threshold, outcomes are fully censored and failures do not distinguish insufficient coordination from stochastic effects. Statistical uncertainty arises from unknown success probabilities p once a task is executed by a feasible coalition. Theorem 1 decomposes regret along this split. To ensure regret is measured only with respect to information limitations, we assume the coordinator has access to an exact planning oracle that solves the integer 0/1 knapsack at each round given current estimates. Under this assumption, regret is attributable to censored feedback and statistical estimation, not computational approximation. For our integer-threshold setting, the knapsack is solved exactly in O(KM)O(KM) time via dynamic programming. 3.2 A Constructive Centralized Strategy We instantiate this baseline as C-TAC (Centralized Threshold-Activated Coordination), shown in Algorithm 1. We assume the identifiability condition: every feasible task k (i.e., τk≤M _k≤ M) satisfies pk≥pmin>0p_k≥ p_ >0 for some known constant pminp_ . Without this condition, feasibility cannot be distinguished from stochastic failure under censored feedback, making sublinear regret impossible. C-TAC maintains a per-task phase ϕk∈search,monitor,infeasible _k∈\ search, monitor, infeasible\, with the first two labeled active. A task begins in search with τ^k=1 τ_k=1 and advances τ^k τ_k on repeated failures; the first non-zero observation at τ^k τ_k transitions the task to monitor, freezing τ^k τ_k and confining further updates to the mean-reward estimate μ^k μ_k. This avoids spurious pruning once feasibility is confirmed. If τ^k τ_k exceeds M during search, the task is marked infeasible and excluded from planning. Each round, the coordinator solves an exact 0/1 knapsack over active tasks using UCB1-based indices Auer et al. (2002) (Algorithm 1, line 3). We use linear search for threshold updates, appropriate for the team sizes we consider; larger teams could employ doubling or binary search for a logM M reduction at the cost of harder analysis. Algorithm 1 C-TAC (Centralized Threshold-Activated Coordination) 0: Tasks K, Agents M, Horizon T, Values v, Identifiability bound pminp_ , Failure budget NmaxN_ , UCB constant c 1: Initialize: For each task k, set τ^k←1 τ_k← 1, ϕk←search _k← search, Nfail,k←0N_fail,k← 0, μ^k←0 μ_k← 0, Nk←0N_k← 0 2: for t=1,…,Tt=1,…,T do 3: Planning: t∗← c_t^*← exact 0/1 knapsack over active tasks k:ϕk≠infeasible\k: _k≠ infeasible\ with weights τ^k τ_k and per-task indices μ^k+vkclogt/Nk μ_k+v_k c t/N_k (Nk=0N_k=0 treated as +∞+∞) 4: Execution: Execute t∗ c_t^*, observe outcomes Yk,t\Y_k,t\ 5: for each task k with coalition size ck,t∗≥τ^kc_k,t^*≥ τ_k do 6: if ϕk=search _k= search then 7: if Yk,t>0Y_k,t>0 then 8: ϕk←monitor _k← monitor; Nfail,k←0N_fail,k← 0 feasibility confirmed 9: Nk←Nk+1N_k← N_k+1; update μ^k μ_k via empirical mean 10: else 11: Nfail,k←Nfail,k+1N_fail,k← N_fail,k+1 censored failure 12: if Nfail,k≥NmaxN_fail,k≥ N_ then 13: τ^k←τ^k+1 τ_k← τ_k+1; Nfail,k←0N_fail,k← 0 linear prune 14: if τ^k>M τ_k>M then 15: ϕk←infeasible _k← infeasible 16: end if 17: end if 18: end if 19: else if ϕk=monitor _k= monitor then 20: Nk←Nk+1N_k← N_k+1; update μ^k μ_k via empirical mean 21: end if 22: end for 23: end for Before stating the theoretical guarantees, we formally define the suboptimality gaps for our combinatorial setting, adapting standard definitions from the combinatorial semi-bandit literature Chen et al. (2013); Combes et al. (2015). Let μ()=∑j=1Kcj≥τjμjμ( c)= _j=1^K1\c_j≥ _j\\, _j denote the expected reward of any feasible allocation ∈ c , and let Δ=μ⋆−μ() _ c=μ -μ( c) be its corresponding suboptimality gap. For each task k, the task-specific gap Δk _k is defined as the minimum positive suboptimality gap among all allocations that feasibly activate task k: Δk=min∈:ck≥τk,Δ>0Δ _k= _ c :\,c_k≥ _k,\, _ c>0 _ c (4) Furthermore, let Δmax=max∈Δ _ = _ c _ c denote the maximum possible suboptimality gap across all valid allocations. Theorem 1 (Centralized TAC-MAB Regret). Consider the TAC-MAB problem with K tasks and M agents over a time horizon T, under centralized coordination. Setting the failure budget to Nmax=⌈2logTlog(1/(1−pmin))⌉N_ = 2 T (1/(1-p_ )) , the expected cumulative team regret R(T)R(T) of C-TAC satisfies: R(T)=(∑k=1Kmin(τk,M)logTpminμ⋆⏟structural search+∑k:τk≤Mvk2logTΔk⏟statistical monitoring+KΔmax⏟tail failures)R(T)=O ( _k=1^K ( _k,M) Tp_ μ _structural search\,+\\ _k: _k≤ M v_k^2 T _k_statistical monitoring\,+ K _ _tail failures ) (5) Proof sketch. We decompose the expected cumulative regret into three components: structural search under censored feedback, statistical monitoring of feasible allocations, and a constant bounding the tail failures. (i) Structural search. For any feasible coalition allocation ck,t≥τkc_k,t≥ _k, the probability of NmaxN_ consecutive Bernoulli(pk)(p_k) failures is at most (1−pk)Nmax(1-p_k)^N_ , which by the identifiability condition (pk≥pminp_k≥ p_ ) is at most (1−pmin)Nmax≤1/T2(1-p_ )^N_ ≤ 1/T^2. By a union bound over T rounds and K tasks, with probability at least 1−K/T1-K/T no feasible task is incorrectly marked infeasible. The search-only pruning rule advances τ^k τ_k incrementally, taking at most min(τk,M) ( _k,M) phases. Each phase costs Nmax=O(logT/pmin)N_ =O( T/p_ ) rounds, during which the team forgoes a worst-case expected reward of up to μ⋆μ (the optimal joint allocation) per round. The monitor transition freezes τ^k τ_k on the first feasible success, and tasks never re-enter search, so no further structural regret accrues. Summing over tasks yields the first term. (i) Statistical monitoring and tail failures. Conditioned on feasible execution, the per-pull reward sequence Xk,tvk\X_k,tv_k\ is i.i.d. with support 0,vk\0,v_k\. Crucially, the empirical mean μ^k←(1/Nk)∑s≤t:feasible exec on kYk,s μ_k←(1/N_k) _s≤ t:feasible exec on kY_k,s and pull counter NkN_k are only updated during these feasible executions, ensuring the estimates remain unbiased by censored feedback. At any round t, the Hoeffding bound yields a confidence radius of vkclogt/Nkv_k c t/N_k for a constant c>0c>0, cleanly recovered by our planning index. Applying the gap-dependent regret bound for combinatorial semi-bandits with multi-play feedback Combes et al. (2015) bounds the statistical regret by O(vk2logT/Δk)O(v_k^2 T/ _k) per feasible task. The tail failure term O(KΔmax)O(K _ ) arises from the exponentially decaying failure tails of the confidence intervals Auer et al. (2002); Chen et al. (2013). ∎ Implementation details. While Theorem 1 dictates a conservative failure budget that scales with logT T, in our experiments we use a fixed budget of Nmax=5N_ =5, which provides sufficient feasibility-resolution power for the environments we consider. For the exploration radius, we use c=2c=2, the standard UCB1 constant. The mean-reward estimate μ^k μ_k is updated only on feasible executions; failures below τ^k τ_k contribute only to the search-phase pruning counter. The per-round computational cost is (KM)O(KM) to exactly solve the integer knapsack via dynamic programming, plus (K)O(K) for the UCB index updates. 4 Decentralized Coordination Unlike the centralized baseline, decentralized agents lack access to a global view of outcomes. They observe only their own rewards and must rely on communication to synchronize their beliefs. The primary challenge is not just statistical estimation, but alignment on feasibility: if agents disagree on the current hypothesis τ^k τ_k, they may compute conflicting optimal plans, leading to mis-coordinated coalitions that fail to trigger tasks. To address this, we introduce D-TAC (Decentralized Threshold-Activated Coordination). D-TAC instantiates a Virtual Coordinator at each agent: a local copy of the C-TAC planner (Section 3) that operates on the agent’s belief state. Because every agent runs the same deterministic planner under shared rules, identical belief states produce identical joint plans without explicit negotiation. Following the “Public Agent” paradigm Chakraborty et al. (2017), agents share four pieces of structure prior to deployment: the C-TAC planner, a rank-based assignment rule, belief-state fusion rules, and common synchronization triggers. Under these shared rules, communication is required only to maintain belief-state consistency, not to coordinate actions. The contribution of D-TAC lies in the event-triggered protocol that schedules belief synchronization based on structural changes; the action-coordination mechanism is inherited from prior work. Because feasibility threshold estimates are non-decreasing under conservative max-fusion and bounded by M, structural disagreement is self-limiting and the team stabilizes on a shared hypothesis within a finite number of events (Proposition 2). 4.1 The Virtual Coordinator Architecture Each agent i maintains a local belief state ℬitB_i^t comprising, for each task k: a threshold lower bound τ^klo τ_k^lo, a threshold upper bound τ^khi τ_k^hi, a phase indicator ϕk∈search,monitor,infeasible _k∈\ search, monitor, infeasible\, and reward statistics (μ^k,Nk)( μ_k,N_k). The agent also stores the most recent joint plan ∗ c^*. The lower bound τ^klo τ_k^lo is initialized to 11 and advances on Type I events; the upper bound τ^khi τ_k^hi is initialized to M (the maximum coalition size) and tightens to min(τ^khi,ck,t) ( τ_k^hi,c_k,t) on observing Yk,t>0Y_k,t>0. The planner uses τ^khi τ_k^hi as the coalition-size weight, since it represents the smallest empirically-confirmed feasible size. Each agent also stores τ^klo,synced τ_k^lo,synced and ϕksynced _k^synced, the values of τ^klo τ_k^lo and ϕk _k at the most recent sync, used to detect Type I breakthroughs against the last globally-known hypothesis. Deterministic Consensus. We use consensus in the engineering sense of a shared assignment rule, not in the distributed-systems sense of a negotiated protocol: there is no message exchange in this step. Agents are indexed by unique IDs i∈1,…,Mi∈\1,…,M\. If the joint plan ∗ c^* allocates ck∗c_k^* agents to task k, agents are assigned in ID order: the first c1∗c_1^* to task 11, the next c2∗c_2^* to task 22, and so on. Agents with index beyond ∑kck∗ _kc_k^* idle that round. Since this rule is deterministic and depends only on ∗ c^*, any two agents holding identical plans produce identical assignments. Transient disagreement may occur between syncs; agents persist with the last agreed-upon plan (“sticky execution”) to avoid mis-coordination. 4.2 Structure-Aware Communication Protocol D-TAC uses an event-triggered protocol with a low-frequency heartbeat backstop, optimizing for the number of synchronization rounds rather than payload size (consistent with Section 2.3). Agents operate silently by default. A sync is triggered when one of three events occurs: • Type I (Feasibility Breakthrough): agent i observes Yk,t>0Y_k,t>0 at ck,t<τ^klo,syncedc_k,t< τ_k^lo,synced or at a task with ϕksynced=infeasible _k^synced= infeasible. • Type I (Structural Pruning): agent i accumulates NmaxN_ consecutive informative failures (coalition ≥τ^klo≥ τ_k^lo in phase search), advancing τ^klo τ_k^lo and changing the planner’s coalition-size weight. • Periodic Heartbeat: every ThT_h rounds, to bound divergence in reward estimates. Performance is robust to ThT_h over a wide range. D-TAC begins with a warmup phase (t=1,…,Kt=1,…,K) in which all M agents probe each task once; a single sync at t=K+1t=K+1 pools the warmup observations. When a sync fires, agents broadcast belief states and fuse peer states under three rules. Threshold bounds are fused conservatively: τ^klo←maxjτ^k,jlo τ_k^lo← _j τ_k,j^lo (monotone non-decreasing) and τ^khi←minjτ^k,jhi τ_k^hi← _j τ_k,j^hi (tightening on any peer’s success). Phases combine under the precedence monitor≻infeasible≻search monitor infeasible search, so a single peer with empirically confirmed feasibility overrides others’ search or pessimistic infeasible claims. Reward estimates are fused as the count-weighted mean μ^k←(∑jNk,jμ^k,j)/(∑jNk,j) μ_k←( _jN_k,j μ_k,j)/( _jN_k,j) over local observations accumulated since the last sync, yielding the same posterior as pooling raw samples. Fusion is idempotent: a repeated sync with no new observations leaves belief components unchanged. Algorithm 2 D-TAC (Agent i View) 0: Tasks K, Agents M, Heartbeat ThT_h, Failure budget NmaxN_ 1: Init: ℬi←B_i← priors; ∗←Planner(ℬi) c^* (B_i) 2: Warmup: for t=1,…,Kt=1,…,K, all M agents probe task t; sync at t=K+1t=K+1 3: for t=K+1,…,Tt=K+1,…,T do 4: Sync←(tmodTh=0)Sync←(t T_h=0) 5: if Type I or Type I event since last sync then 6: Sync←TrueSync 7: end if 8: if Sync then 9: Broadcast ℬiB_i; receive ℬj\B_j\ 10: Fuse: τ^klo←maxj τ_k^lo← _j, τ^khi←minj τ_k^hi← _j, ϕk _k by precedence, μ^k μ_k count-weighted 11: τ^klo,synced←τ^klo τ_k^lo,synced← τ_k^lo; ϕksynced←ϕk _k^synced← _k; ∗←Planner(ℬi) c^* (B_i) 12: end if 13: Execute k←∗[i]k← c^*[i]; observe Yk,tY_k,t 14: if Yk,t>0Y_k,t>0 then 15: τ^khi←min(τ^khi,ck,t) τ_k^hi← ( τ_k^hi,c_k,t) 16: if ck,t<τ^kloc_k,t< τ_k^lo then 17: τ^klo←1 τ_k^lo← 1 refutation 18: end if 19: Update μ^k,Nk μ_k,N_k 20: if ϕk∈search,infeasible _k∈\ search, infeasible\ then 21: ϕk←monitor _k← monitor 22: end if 23: Flag Type I if ck,t<τ^klo,syncedc_k,t< τ_k^lo,synced or ϕksynced=infeasible _k^synced= infeasible 24: else if ϕk=search _k= search and ck,t≥τ^kloc_k,t≥ τ_k^lo then 25: Nfail,k←Nfail,k+1N_fail,k← N_fail,k+1 26: if Nfail,k≥NmaxN_fail,k≥ N_ then 27: Advance τ^klo τ_k^lo; flag Type I 28: end if 29: end if 30: end for Convergence and Communication Bound. D-TAC is not designed to provide worst-case regret guarantees under decentralization in this work; a formal characterization requires bounding the transient phase of mismatched plans, the expected time to belief alignment, and the impact of stale estimates, which we defer to ongoing work. Instead, we establish a finite bound on the structural communication overhead. Proposition 2 (D-TAC Communication Complexity). Under the D-TAC protocol, the total number of structural synchronization events (Type I and Type I triggers) over any horizon T is at most (KM)O(KM) network-wide before structural consensus is established at sync events. Proof sketch. We bound the number of sync events triggered by structural changes team-wide. Type I events advance τ^klo τ_k^lo, whose team-synced value is monotone non-decreasing through 1,…,M+1\1,…,M+1\ under max-fusion; at most M such advances per task. Type I events fire when successes refute the team’s synced hypothesis; each such event tightens the team-synced upper bound, which is monotone non-increasing through the same range under min-fusion; at most M such tightenings per task. Summing over K tasks gives (KM)O(KM) structural sync events team-wide; beyond this, only the heartbeat fires. ∎ Once structural beliefs align (within (KM)O(KM) events) and all feasible tasks transition to monitor, D-TAC’s planner produces the same plan that C-TAC would given the shared belief state. From this point, regret accrues only from statistical estimation and the bounded lag between heartbeat syncs, so D-TAC empirically approaches C-TAC’s asymptotic performance, modulo a transient during the structural-learning phase. The total communication budget under D-TAC is therefore (KM+T/Th)O(KM+T/T_h), with heartbeats dominating once structural consensus is reached. 5 Experimental Evaluation We evaluate TAC-MAB to quantify the cost of learning under censored feedback and to assess whether explicit coordination is necessary to escape feasibility-gated failure modes. Our experiments isolate structural difficulty (identifying unknown coalition-size requirements) from standard statistical estimation error, and compare centralized and decentralized coordination under a shared observation model. Experimental setup and baselines. All results are averaged over N=40N=40 independent runs with different random seeds; shaded regions and error bars indicate ±1± 1 standard error. Unless otherwise stated, methods are evaluated with horizon T=10,000T=10,000, M=5M=5 agents, and K=10K=10 task types. The environment includes two infeasibility decoys (τ>Mτ>M), one full-team task (τ=Mτ=M), several mid-coordination tasks, and low-threshold distractors. D-TAC uses heartbeat period Th=50T_h=50 and failure budget Nmax=5N_ =5. C-TAC uses an exact knapsack planner (Section 3), isolating learning and coordination effects from computational approximation. We compare the following strategies: • Oracle Allocation: a full-information benchmark that knows all feasibility thresholds and success probabilities and selects the optimal allocation in every round. • Independent UCB: a decentralized baseline in which agents independently estimate task values using UCB without communication or coordination. • C-TAC: the centralized feasibility-aware strategy described in Section 3 (Algorithm 1), which explicitly probes coalition sizes to resolve feasibility. • D-TAC: the decentralized coordination protocol introduced in Section 4 (Algorithm 2), which synchronizes agents only upon structural belief updates. All methods receive the same local observations as defined in Section 2.3; only coordination and communication differ. We omit direct comparison against decentralized cooperative-MAB baselines such as Landgren-CoopUCB Landgren et al. (2021) and DDUCB Martínez-Rubio et al. (2018): faithful reproduction requires implementation choices (e.g., UCB exploration constants, fusion conventions) that could not be calibrated against authors’ reference implementations. We defer this comparison to follow-up work. Censored feedback breaks independent exploration. We first consider an environment containing one high-value cooperative task that requires full-team coordination and several low-threshold distractor tasks that provide immediate but smaller rewards. This setting isolates the censored-feedback failure mode: without explicit coordination, independent agents are unlikely to activate the cooperative task and instead converge to suboptimal alternatives. Figure 1 reports cumulative regret over time. Independent UCB exhibits sustained linear regret, reflecting its inability to reliably form sufficiently large coalitions under censored feedback. Failures below the feasibility threshold provide no informative signal, so independent exploration does not guide agents toward larger coalitions. C-TAC (centralized) and D-TAC (decentralized) incur an initial coordination cost during early structure learning; once feasibility is resolved, regret growth slows substantially. The cost of learning feasibility is incurred early and does not scale with the horizon. Communication efficiency. At T=10,000T=10,000, D-TAC achieves cumulative regret of 13,70013,700 using 4,3034,303 messages, versus C-TAC’s 4,5004,500 regret at 100,000100,000 messages—a 23×23× reduction in communication while remaining within the same order of magnitude in regret. D-TAC’s message budget is amortized over structural events: the periodic heartbeat accounts for most messages once feasibility is resolved, while Type I and Type I structural triggers fire only during the learning phase. Figure 1: Cumulative regret under censored feedback. Cumulative regret R(t)R(t) over T=10,000T=10,000 steps, averaged over N=40N=40 independent runs. Independent UCB exhibits sustained linear regret due to censored feedback. C-TAC and D-TAC incur an early coordination cost to resolve feasibility, after which regret growth slows. Shaded regions denote ±1± 1 standard error. Structural hardness induced by feasibility thresholds. We next examine how learning difficulty scales with the magnitude of coordination requirements. We vary the maximum feasibility threshold τmax _ across environments while keeping the number of agents, tasks, rewards, and success probabilities fixed. As τmax _ increases, informative feedback becomes increasingly unlikely under uncoordinated exploration. Figure 2 reports the final cumulative regret R(T)R(T) as a function of τmax _ . Independent UCB suffers rapidly increasing regret as coordination requirements grow, reflecting the vanishing probability of independently activating threshold-gated tasks. C-TAC maintains consistently low regret across all threshold levels by explicitly probing feasibility. D-TAC degrades gracefully and approaches centralized performance, demonstrating that event-triggered coordination preserves feasibility learning while substantially reducing communication. Figure 2: Structural hardness versus regret. Final cumulative regret R(T)R(T) as a function of the maximum feasibility threshold τmax _ . Independent UCB exhibits increasing regret as coordination requirements grow. C-TAC maintains low regret across all threshold levels. D-TAC approaches centralized performance while substantially reducing communication. Results are averaged over N=40N=40 runs with horizon T=10,000T=10,000; error bars denote ±1± 1 standard error. Limitations. Our experiments focus on stationary feasibility thresholds and synchronous rounds. In settings with non-stationary coordination requirements, delayed communication, or adversarial failures, additional mechanisms may be required to maintain feasibility alignment. While D-TAC substantially reduces communication in practice, we do not provide worst-case decentralization regret guarantees; characterizing the minimal communication required for feasibility learning under adversarial or dynamic conditions remains an open direction. 6 Related Work Our work intersects with several primary domains in sequential decision-making, each with distinct limitations when applied to decentralized, threshold-gated coordination. Multi-Agent Multi-Armed Bandits (MAMAB). Recent advances in MAMAB explore communication-constrained coordination Landgren et al. (2021); Martínez-Rubio et al. (2018); Chang et al. (2022); Chakraborty et al. (2017); Agarwal et al. (2022), including event-triggered and on-demand protocols Chen et al. (2023), gossip-based information sharing Chawla et al. (2020), heterogeneous and collision-aware decentralized learning Kalathil et al. (2014); Magesh and Veeravalli (2021), and fully-decentralized cooperation without communication Chang and Lu (2023). These formulations assume rewards are triggered by individual agent actions or independent arm pulls. They fail in environments where task feasibility is gated by coalition size, as independent exploration yields fully censored feedback, preventing agents from learning task values. Related work in ad hoc teamwork Barrett et al. (2014) addresses coordination among agents with unknown communication protocols but focuses on uncertainty over teammate behavior rather than environmental coordination requirements. Combinatorial and Knapsack Bandits. Centralized combinatorial multi-armed bandits (CMAB) and knapsack-based bandits study how to allocate limited resources to maximize reward over time Chen et al. (2013); Combes et al. (2015); Tran-Thanh et al. (2012); Das et al. (2022). These models typically assume that resource costs or activation conditions are known in advance. In our setting, the feasibility threshold is a latent parameter that must be learned online, imposing an additional structural learning cost that standard CMAB frameworks do not address. Censored Feedback and Resource Allocation. Bandit models with threshold-based or censored feedback have recently gained traction. Abernethy et al. Abernethy et al. (2016) study settings where rewards are observed only if expected values exceed a known threshold; Zhang et al. Zhang et al. (2024) extend this to actively learning thresholds with latent values under single-agent censored feedback. Most closely related, Verma et al. Verma et al. (2019) introduce censored semi-bandits. This literature is restricted to centralized settings allocating a continuous, divisible resource budget; it does not address the discrete, integer-based coordination of distinct agents, nor does it provide mechanisms for decentralized agents to align on unknown thresholds under communication constraints. Our Contributions. TAC-MAB and D-TAC address these gaps. We model task requirements as integer coalition thresholds and prove that the proposed centralized algorithm (C-TAC) achieves O(logT)O( T) cumulative regret, decomposed into a structural-search term capturing the cost of resolving feasibility under censored feedback and a statistical-monitoring term for value estimation (Theorem 1). We then introduce a decentralized event-triggered protocol (D-TAC) that maintains feasibility alignment under conservative max-fusion and empirically achieves a 23×23× reduction in communication relative to the centralized baseline (Section 5). 7 Conclusion We introduced the Threshold-Activated Cooperative Multi-Armed Bandit (TAC-MAB), a framework for cooperative tasks whose rewards are gated by unknown coalition-size requirements and are fully censored below feasibility. Independent exploration fails structurally in this setting: agents receive no informative feedback below threshold and cannot distinguish infeasibility from stochastic failure. Decomposing regret into feasibility learning and value estimation, we proved that the centralized algorithm achieves O(logT)O( T) cumulative regret under the identifiability condition pk≥pmin>0p_k≥ p_ >0 for feasible tasks (Theorem 1), with feasibility resolving in O(logT/pmin)O( T/p_ ) probes per task. Empirically, C-TAC resolves feasibility via targeted coalition-size probing, while D-TAC approximates this behavior through event-triggered synchronization—achieving a 23×23× reduction in communication relative to the centralized baseline while preserving feasibility alignment under conservative max-fusion. Extending D-TAC to lossy or adversarial communication remains open; we are pursuing a formal regret characterization under intermittent communication in ongoing work. Acknowledgements The conclusions and opinions expressed in this research paper are those of the authors and do not necessarily reflect the official policy or position of the U.S. Government or Department of Defense. References J. D. Abernethy, K. Amin, and R. Zhu (2016) Threshold bandits, with and without censored feedback. Advances In Neural Information Processing Systems 29. Cited by: §6. M. Agarwal, V. Aggarwal, and K. Azizzadenesheli (2022) Multi-agent multi-armed bandits with limited communication. Journal of Machine Learning Research 23 (212), p. 1–24. Cited by: §6. P. Auer, N. Cesa-Bianchi, and P. Fischer (2002) Finite-time analysis of the multiarmed bandit problem. Machine learning 47, p. 235–256. Cited by: §3.2, §3.2. S. Barrett, N. Agmon, N. Hazon, S. Kraus, and P. Stone (2014) Communicating with unknown teammates. In ECAI 2014, p. 45–50. Cited by: §6. X. Cao, M. Li, Y. Tao, and P. Lu (2024) HMA-sar: multi-agent search and rescue for unknown located dynamic targets in completely unknown environments. IEEE Robotics and Automation Letters 9 (6), p. 5567–5574. Cited by: §1. M. Chakraborty, K. Y. P. Chua, S. Das, and B. Juba (2017) Coordinated versus decentralized exploration in multi-agent multi-armed bandits.. In IJCAI, p. 164–170. Cited by: §1, §4, §6. W. Chang, M. Jafarnia-Jahromi, and R. Jain (2022) Online learning for cooperative multi-player multi-armed bandits. In 2022 IEEE 61st Conference on Decision and Control (CDC), p. 7248–7253. Cited by: §6. W. Chang and Y. Lu (2023) Optimal cooperative multiplayer learning bandits with noisy rewards and no communication. arXiv preprint arXiv:2311.06210. Cited by: §6. R. Chawla, A. Sankararaman, A. Ganesh, and S. Shakkottai (2020) The gossiping insert-eliminate algorithm for multi-agent bandits. In International conference on artificial intelligence and statistics, p. 3471–3481. Cited by: §6. W. Chen, Y. Wang, and Y. Yuan (2013) Combinatorial multi-armed bandit: general framework and applications. In International Conference on Machine Learning, p. 151–159. Cited by: §3.2, §3.2, §6. Y. J. Chen, L. Yang, X. Wang, X. Liu, M. Hajiesmaili, J. C.S. Lui, and D. Towsley (2023) On-demand communication for asynchronous multi-agent bandits. In International Conference on Artificial Intelligence and Statistics, p. 3903–3930. Cited by: §6. R. Combes, M. S. Talebi Mazraeh Shahi, A. Proutiere, et al. (2015) Combinatorial bandits revisited. Advances in neural information processing systems 28. Cited by: §3.2, §3.2, §6. D. Das, S. Jain, and S. Gujar (2022) Budgeted combinatorial multi-armed bandits. arXiv preprint arXiv:2202.03704. Cited by: §6. D. Kalathil, N. Nayyar, and R. Jain (2014) Decentralized learning for multiplayer multiarmed bandits. IEEE Transactions on Information Theory 60 (4), p. 2331–2345. Cited by: §6. P. Landgren, V. Srivastava, and N. E. Leonard (2021) Distributed cooperative decision making in multi-agent multi-armed bandits. Automatica 125, p. 109445. Cited by: §1, §5, §6. A. Magesh and V. V. Veeravalli (2021) Decentralized heterogeneous multi-player multi-armed bandits with non-zero rewards on collisions. IEEE Transactions on Information Theory 68 (4), p. 2622–2634. Cited by: §6. A. Mahajan, T. Rashid, M. Samvelyan, and S. Whiteson (2019) Maven: multi-agent variational exploration. Advances in neural information processing systems 32. Cited by: §1. D. Martínez-Rubio, V. Kanade, and P. Rebeschini (2018) Decentralized cooperative stochastic bandits. arXiv preprint arXiv:1810.04468. Cited by: §5, §6. F. A. Oliehoek, C. Amato, et al. (2016) A concise introduction to decentralized pomdps. Vol. 1, Springer. Cited by: §1. J. Tobin, R. Fong, A. Ray, J. Schneider, W. Zaremba, and P. Abbeel (2017) Domain randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), p. 23–30. Cited by: §1. L. Tran-Thanh, A. Chapman, A. Rogers, and N. Jennings (2012) Knapsack based optimal policies for budget–limited multi–armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 26, p. 1134–1140. Cited by: §6. A. Verma, M. Hanawal, A. Rajkumar, and R. Sankaran (2019) Censored semi-bandits: a framework for resource allocation with censored feedback. Advances in Neural Information Processing Systems 32. Cited by: §2.1, §2, §6. J. Zhang, T. Lin, W. Zheng, Z. Feng, Y. Teng, and X. Deng (2024) Learning thresholds with latent values and censored feedback. In The Twelfth International Conference on Learning Representations (ICLR), Cited by: §6.