Best-Arm Identification with Noisy Actuation

1. Problem Formulation

The paper addresses the Fixed-Confidence Best-Arm Identification (BAI) problem within a Multi-Armed Bandit (MAB) framework, but introduces a critical constraint: noisy actuation.

• Standard Setting: A learner selects an arm $a$, receives a reward, and iteratively identifies the arm with the highest mean reward $\mu_{a^*}$ with probability at least $1-\delta$.
• Noisy Actuation Setting: The learner does not directly pull an arm. Instead, it sends a command $X_t$ (the intended arm) over a Discrete Memoryless Channel (DMC) $W$. The agent receives an output $Y_t$ and executes arm $\tilde{a}_t = Y_t$.
• The Challenge: The learner observes the reward from the executed arm but does not observe the channel output $Y_t$. The goal is to identify the true best arm $a^*$ despite the fact that the executed arm may differ from the intended command due to channel noise (confusability).
• Key Metric: The performance is measured by the total number of physical rounds (channel uses) required to achieve $\delta$-correctness, compared to an idealized noise-free benchmark $N_{clean}(\delta, \mu)$.

2. Methodology and Models

The authors analyze three distinct models of agent capability, ranging from passive execution to active state management. The analysis relies heavily on Zero-Error Capacity and Confusability Graphs (Shannon capacity concepts).

Model 1: No Decoding (Passive Agent)

• Mechanism: The agent executes the received symbol $Y_t$ immediately without any decoding logic or codebook.
• Analysis: The learner observes a "mixed" reward distribution $\tilde{\mu} = W\mu$, where $W$ is the channel transition matrix.
• Result:
  • If $W$ is non-injective (e.g., specific error probabilities make distinct arms indistinguishable), identification is impossible.
  • If $W$ is invertible, the learner can estimate $\mu$ by "unmixing" ($\hat{\mu} = W^{-1}\hat{\tilde{\mu}}$). However, this amplifies estimation error.
  • Performance: The sample complexity inflates by a factor of $1/\sigma_{min}(W)^2$, where $\sigma_{min}(W)$ is the smallest singular value of the channel matrix. This factor depends heavily on the error probability $\epsilon$ and can diverge as $\epsilon \to 0.5$ (for even $K$).

Model 2: Fixed Decoding (Pre-shared Codebook)

• Mechanism: The agent possesses a pre-shared codebook allowing it to decode received signals into actions with zero error, provided the channel's zero-error capacity $C_0(G) > 0$.
• Two Schemes:
  1. Zero-Error Capacity Codebook: The learner sends a block of $n_u$ symbols to transmit one arm index. The agent decodes the block and executes the arm.
  2. Independent Set Schedules: The learner restricts commands to an independent set of the confusability graph $G$ (where no two arms are confusable). The agent knows the schedule and decodes single symbols with zero error.
• Result:
  • The dependence on error probability $\epsilon$ is eliminated.
  • Performance: The sample complexity suffers a constant multiplicative slowdown factor ($n_u$ or a factor between 1 and 2 depending on the schedule). This factor depends only on the graph structure (confusability), not the noise level.
  • Example: For a 5-arm typewriter channel ($C_5$), a block length of $n_u=2$ suffices to send any of the 5 arms with zero error.

Model 3: Stateful Plan Execution (Packetized Successive Elimination)

• Mechanism: The agent can maintain state and execute multi-round plans. The learner sends a "plan packet" (a zero-error code) instructing the agent to pull a specific sequence of arms for a specific duration. The agent executes this plan continuously while the next packet is being transmitted.
• Algorithm: Packetized Successive Elimination (PSE). The learner uses a phased elimination strategy. In each phase, a plan is installed (taking $n_r$ channel uses) to pull remaining arms a set number of times.
• Result:
  • The communication cost is converted from a multiplicative factor to an additive overhead.
  • Performance: $\tau \leq N_{SE}(\delta, \mu) + \sum n_r$.
  • The additive term is proportional to the number of phases (logarithmic in $1/\Delta_{min}$), whereas the statistical term $N_{SE}$ dominates for small gaps. This is significantly more efficient than Model 2 when the gaps between arms are small.

3. Key Contributions

1. Formulation of Noisy Actuation: The paper introduces a novel MAB setting where the action channel is noisy, distinct from the standard noisy reward channel literature.
2. Zero-Error Capacity as a Threshold: It establishes that the zero-error capacity of the underlying channel is the critical threshold. If $C_0(G) = 0$, no strategy can eliminate dependence on noise. If $C_0(G) > 0$, performance guarantees can be made independent of the noise probability $\epsilon$.
3. Three-Tiered Analysis:
   • Case 1: Shows that without coding, performance degrades based on the channel's conditioning (singular values).
   • Case 2: Demonstrates that fixed zero-error codes remove noise dependence but incur a constant multiplicative penalty.
   • Case 3: Proves that stateful execution reduces the penalty to an additive overhead, which is asymptotically optimal for small gaps.
4. Constructive Schemes: Provides explicit coding constructions for "Typewriter Channels" (e.g., $C_5$ and $C_6$) using independent sets and block codes to achieve zero-error communication.

4. Key Results Summary

• Identifiability: In Case 1, if the channel matrix is singular (e.g., $K$ even, $\epsilon=0.5$ for typewriter channels), the best arm cannot be identified. In Cases 2 and 3, identifiability is guaranteed as long as $C_0(G) > 0$.
• Efficiency: Case 3 (PSE) is the most efficient for high-precision requirements (small $\delta$ or small $\Delta$), as the communication cost becomes negligible compared to the sampling cost.

5. Significance

• Theoretical Insight: The paper bridges the gap between Information Theory (specifically Shannon's zero-error capacity and confusability graphs) and Sequential Decision Making (MAB). It shows that the fundamental limit of action communication is not the error probability, but the structure of confusability.
• Practical Relevance: This model applies to real-world scenarios where commands are sent over unreliable interfaces, such as:
  • Remote control of robots over low-bandwidth or lossy links.
  • Human-in-the-loop systems where instructions might be misunderstood.
  • Distributed control systems with physical constraints.
• Design Implications: It suggests that for systems requiring high reliability, investing in stateful agents capable of executing pre-installed plans (Case 3) is far superior to simple command-and-execute architectures, as it minimizes the communication overhead to a constant additive term rather than a multiplicative penalty.

In conclusion, the paper demonstrates that while noisy actuation poses a significant challenge, leveraging zero-error coding and stateful execution allows distributed agents to achieve performance guarantees that are robust to channel noise, depending solely on the topological properties of the channel's confusability graph.