🤖 machine learning

Cost of Structural Learning Under Censored Feedback: A Threshold-Bandit Approach

This paper introduces the Threshold-Activated Cooperative Multi-Armed Bandit (TAC-MAB) framework to address learning under censored feedback, proposing a centralized algorithm with logarithmic regret and a decentralized event-triggered protocol that achieves near-centralized performance with a 23-fold reduction in communication.

Original authors: Michael Ledford, William Regli

Published 2026-05-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Michael Ledford, William Regli

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are leading a team of rescue workers trying to open a series of locked doors. Each door leads to a treasure room, but there's a catch: you don't know how many people are needed to open each door.

If you send too few people, the door doesn't budge. The lock just clicks silently, and you get zero information. You don't know if the door is broken, if the lock is jammed, or if you simply didn't send enough people.
If you send enough people, the door opens. If the treasure is there, you get a reward. If the door opens but the room is empty, you get a "failure" signal, but at least you know the door can be opened.

This is the core problem the paper tackles: How do you learn the rules of the game when your failures are completely silent?

The Problem: The "Silent Failure" Trap

In many real-world team scenarios (like search-and-rescue or coordinating drones), success depends on a specific number of people working together.

The Trap: If you try a task with too few people, you get no feedback. It looks exactly the same as if you tried with enough people but got "unlucky" (stochastic failure).
The Result: If agents (team members) act alone, they will keep trying small groups, getting silent failures, and never realizing they need a bigger team. They get stuck in a loop of inefficiency.

The Solution: A Two-Step Strategy

The authors propose a new way to think about this, called TAC-MAB (Threshold-Activated Cooperative Multi-Armed Bandit). They treat the "number of people needed" as a hidden number you have to guess.

They tested two approaches:

1. The Centralized Approach (The "Control Tower")

Imagine a single commander in a tower who sees everything.

How it works: The commander tells the team exactly who goes where. If a door fails, the commander knows, "Okay, we sent 2 people, but it failed. Let's try 3 next time."
The Result: This works very well. The team learns the rules quickly and stops wasting time. The paper proves mathematically that this method is highly efficient, with the "cost" of learning growing very slowly over time.

2. The Decentralized Approach (The "Whisper Network")

Now, imagine the team has no commander. Everyone is on their own, but they can talk to each other.

The Challenge: If everyone talks all the time, they waste energy and bandwidth. If they never talk, they might disagree on how many people are needed (e.g., Agent A thinks 3 people are needed, Agent B thinks 5). If they disagree, they might send mismatched teams and fail.
The Innovation (D-TAC): The authors created a smart rule: "Don't talk unless something important changes."
- The agents work silently most of the time.
- They only stop and sync up (share their notes) if they discover something new, like: "Hey, I tried with 3 people and it worked!" (This is a breakthrough) OR "I tried with 3 people and it failed 5 times in a row; maybe we need 4." (This is a structural change).
The Result: This method is almost as good as the Control Tower but uses 23 times less communication. It's like a team that only holds a meeting when they find a new clue, rather than holding a meeting every 5 minutes.

The Key Takeaways

Silent failures are dangerous: Without coordination, teams can't learn when they need more people because the "failure" looks like "bad luck."
Structure matters: You have to learn the structure of the problem (how many people are needed) before you can optimize the stats (how likely the treasure is to be there).
Efficiency is possible: You don't need constant, noisy communication to solve this. By only syncing up when your "theory" about the rules changes, a decentralized team can perform nearly as well as a centralized one.

In a Nutshell

The paper shows that when a team's success depends on hitting an unknown "minimum group size," acting alone leads to failure. However, by using a smart strategy where agents only share information when their understanding of the "minimum group size" changes, they can learn the rules efficiently without needing to talk constantly. It's the difference between a team shouting updates every second versus a team that only speaks up when they discover a new rule.

Technical Summary: Cost of Structural Learning under Censored Feedback

1. Problem Formulation: TAC-MAB

The paper introduces the Threshold-Activated Cooperative Multi-Armed Bandit (TAC-MAB), a framework modeling cooperative multi-agent systems where task success depends on a coalition of agents meeting an unknown size threshold.

Setting: A team of $M$ homogeneous agents operates over a horizon $T$ across $K$ stationary tasks. Each task $k$ has an unknown integer feasibility threshold $\tau_k$ , a success probability $p_k$ , and a value $v_k$ .
Censored Feedback: If the coalition size $c_{k,t}$ assigned to task $k$ is less than $\tau_k$ , the execution yields a deterministic outcome of 0. Crucially, the agents cannot distinguish between censoring (insufficient coalition size) and stochastic failure (coalition size $\ge \tau_k$ but the task failed probabilistically).
The Identifiability Challenge: Under censored feedback, independent exploration fails because agents cannot learn the threshold $\tau_k$ from failures; a failure provides no signal regarding whether the coalition was too small or simply unlucky.
Objective: Maximize cumulative reward by solving two coupled sub-problems: (1) learning the unknown thresholds $\tau$ under censored feedback, and (2) optimizing the allocation of $M$ agents to tasks (a 0/1 knapsack problem) to maximize expected reward.

2. Methodology

Centralized Baseline: C-TAC

The authors first analyze an idealized centralized architecture (C-TAC) where a coordinator observes all outcomes and broadcasts allocations at zero cost.

Algorithm: C-TAC maintains a phase for each task: SEARCH, MONITOR, or INFEASIBLE.
- In the SEARCH phase, the algorithm incrementally tests coalition sizes (linear search). If a failure occurs, it increments the estimated threshold $\hat{\tau}_k$ . If a success occurs, the task transitions to MONITOR, freezing $\hat{\tau}_k$ and focusing on estimating the mean reward $\hat{\mu}_k$ .
- A failure budget $N_{max}$ prevents infinite SEARCH phases; if $N_{max}$ consecutive failures occur at a specific size, the threshold is incremented.
- The coordinator solves an exact 0/1 knapsack problem at each round using Upper Confidence Bound (UCB1) indices based on current estimates.
Theoretical Guarantee: Theorem 1 establishes that C-TAC achieves $O(\log T)$ cumulative regret. The regret is decomposed into:
1. Structural Search Term: The cost of resolving feasibility under censored feedback, scaling with $\sum \min(\tau_k, M) \log T$ .
2. Statistical Monitoring Term: The cost of estimating success probabilities, scaling with standard combinatorial bandit terms ( $\sum \frac{v_k^2 \log T}{\Delta_k}$ ).
3. Tail Failures: A constant term bounding rare confidence interval failures.

Decentralized Protocol: D-TAC

Recognizing that continuous synchronization is costly, the authors propose D-TAC, a decentralized event-triggered protocol.

Virtual Coordinator: Each agent runs a local copy of the C-TAC planner.
Deterministic Consensus: Agents use a shared, deterministic assignment rule (based on agent IDs) to map joint plans to individual actions. If agents hold identical belief states, they execute identical plans without negotiation.
Event-Triggered Synchronization: Agents communicate only when specific structural events occur, rather than every round:
- Type I (Feasibility Breakthrough): An agent observes a success with a coalition size smaller than the currently synced lower bound (refuting the hypothesis).
- Type II (Structural Pruning): An agent accumulates $N_{max}$ consecutive failures at the current estimated threshold, forcing an increment in the local lower bound.
- Periodic Heartbeat: A low-frequency sync to bound divergence in reward estimates.
Belief Fusion: Upon sync, agents fuse beliefs conservatively: lower bounds are updated via max-fusion (monotone non-decreasing), and upper bounds via min-fusion. This ensures structural disagreement is self-limiting.
Complexity: Proposition 2 states that the total number of structural synchronization events required to reach consensus is bounded by $O(KM)$.

3. Key Results

Theoretical Findings

Regret Decomposition: The paper proves that the cost of learning under censored feedback is separable from statistical estimation. The structural learning cost is incurred early and does not scale with the horizon $T$ beyond the logarithmic factor.
Identifiability Condition: Sublinear regret is only possible if a known lower bound $p_{min} > 0$ exists for feasible tasks, ensuring that stochastic failure is distinguishable from censoring over repeated trials.

Empirical Findings

Experiments were conducted with $M=5$ agents, $K=10$ tasks, and $T=10,000$ rounds.

Failure of Independent Learning: Independent UCB agents exhibit sustained linear regret. Without coordination, they fail to form the necessary coalitions, receiving only censored feedback and converging to suboptimal, low-threshold tasks.
Performance of C-TAC and D-TAC: Both algorithms incur an initial coordination cost to resolve feasibility, after which regret growth slows significantly.
Communication Efficiency: D-TAC achieves a 23 $\times$ reduction in communication compared to the centralized baseline (4,303 messages vs. 100,000 messages) while maintaining cumulative regret within the same order of magnitude.
Scalability: As the maximum feasibility threshold $\tau_{max}$ increases, independent agents suffer rapidly increasing regret. D-TAC degrades gracefully, approaching centralized performance even under high coordination requirements.

4. Significance and Claims

The paper claims to characterize the coordination cost of learning under censored feedback. Its primary contributions are:

Formalization: Defining TAC-MAB to isolate the structural difficulty of feasibility-gated feedback from standard statistical estimation.
Algorithmic Design: Demonstrating that near-centralized performance is achievable in a decentralized setting without continuous synchronization.
Efficiency: Showing that event-triggered protocols can drastically reduce communication overhead (by an order of magnitude) while preserving the ability to learn unknown structural constraints.

The authors explicitly state that their work isolates the cost of learning feasibility from logistical coordination costs. They note limitations regarding non-stationary environments and adversarial failures, acknowledging that formal worst-case regret guarantees for the decentralized setting under intermittent communication remain an open direction for future work.