Best-Arm Identification with Noisy Actuation This work is partially supported by NSF grants #2221871, #2007714, and #2221871, by Army Research Laboratory grant under Cooperative Agreement W911NF-17-2-0196, and by Amazon Faculty Award.
Merve Karakas † , Osama Hanna ‡ , Lin F. Yang † , and Christina Fragouli † † University of California, Los Angeles, ‡ Meta, Central Applied Science Email: [email protected], [email protected], {linyang, christina.fragouli}@ucla.edu · 2026
Read Best-Arm Identification with Noisy Actuation This work is partially supported by NSF grants #2221871, #2007714, and #2221871, by Army Research Laboratory grant under Cooperative Agreement W911NF-17-2-0196, and by Amazon Faculty Award. by Merve Karakas † , Osama Hanna ‡ , Lin F. Yang † , and Christina Fragouli † † University of California, Los Angeles, ‡ Meta, Central Applied Science Email: [email protected], [email protected], {linyang, christina.fragouli}@ucla.edu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-02255.txt.
Introduction
Karakas and colleagues identify the best arm of a bandit when commands to a remote agent pass over a noisy channel. Depending on what the agent can do, they design communication schemes and analyze them, linking performance to the zero error capacity of the channel. The work shows how channel noise, not just reward noise, shapes the search for the best arm, and which schemes cope best when actuation itself is unreliable.
Catalog record
| CREATOR | Merve Karakas † , Osama Hanna ‡ , Lin F. Yang † , and Christina Fragouli † † University of California, Los Angeles, ‡ Meta, Central Applied Science Email: [email protected], [email protected], {linyang, christina.fragouli}@ucla.edu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46729 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.02255
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Best-Arm Identification with Noisy Actuation This work is partially supported by NSF grants #2221871, #2007714, and #2221871, by Army Research Laboratory grant under Cooperative Agreement W911NF-17-2-0196, and by Amazon Faculty Award. Merve Karakas † , Osama Hanna ‡ , Lin F. Yang † , and Christina Fragouli † † University of California, Los Angeles, ‡ Meta, Central Applied Science Email: [email protected], [email protected], {linyang, christina.fragouli}@ucla.edu Abstract In this paper, we consider a multi-armed bandit (MAB) instance and study how to identify the best arm when arm commands are conveyed from a central learner to a distributed agent over a discrete memoryless channel (DMC). Depending on the agent capabilities, we provide communication schemes along with their analysis, which interestingly relate to the zero-error capacity of the underlying DMC. I Introduction Motivated by the growing interest in distributed learning applications, recent work has begun to investigate learning over noisy communication channels [ 6 , 5 , 9 , 10 , 16 ] . Within this landscape, we consider a new formulation: best arm identification in which arm commands are conveyed from a central learner to a distributed agent over a discrete memoryless channel (DMC). Such channels can model situations in which actions are communicated over unreliable interfaces, including physical controls, low-bandwidth links, or human-mediated instructions, where commands may be received correctly or confused with a small set of alternatives. Despite their simplicity, DMCs capture key sources of noise in practical action-communication pipelines and allow us to derive theoretical insights. Our focus is on identifying when performance guarantees can be made independent of the channel error probabilities and depend only on confusability. For that question, zero-error capacity is the natural threshold quantity. In this paper, we study three models of increasing capability for the distributed agent. In the first model, the agent can only execute the commands it receives. In the second, the agent is equipped with a preloaded codebook that allows it to decode the received signals into actions. In the third, most powerful model, the agent can maintain state and execute multi-round plans installed via zero-error packets. For each model, we compare performance against an idealized benchmark in which communication occurs over an error-free channel. Our main findings are summarized below: • Case 1 (No decoding). If the agent simply executes received commands, the channel induces mixing of the action distributions. Performance degrades by a factor governed by the smallest singular value of the channel matrix, which depends on the channel error probability. • Case 2 (Fixed decoding). If the zero-error capacity of the channel is nonzero and the agent can use a fixed block code, then the resulting performance loss can be only a constant multiplicative factor, independent of the channel error probabilities. • Case 3 (Stateful execution). If the agent can maintain state and execute multi-round plans installed via zero-error packets, then the performance gap relative to the error-free benchmark can be reduced to an additive overhead. We note that when the zero-error capacity of the underlying DMC is zero, no coding strategy can eliminate dependence on the channel noise (Remark 1 ), and performance necessarily degrades with the channel error probability. Related Work. Multi-armed bandits (MAB) are a standard model for sequential decision-making under uncertainty; see, e.g., [ 13 ] and references therein. Our objective is fixed-confidence best-arm identification (BAI), for which classic elimination and tracking-style algorithms yield instance-dependent sample complexities of order \tilde{O}\!\big(\sum_{a\neq a^{\star}}\Delta_{a}^{-2}\log(1/\delta)\big) ; representative references include successive elimination [ 2 ] , lil’UCB [ 7 ] , and Track-and-Stop [ 3 ] as well as complexity/lower-bound characterizations [ 11 ] . Prior work on noisy bandits focuses on the reward channel—adversarial corruption [ 15 , 4 , 1 ] and delayed/censored feedback [ 8 ] —but assumes the chosen arm is executed as intended. Recent work has studied uncertainty in the executed arm via arm-erasure models, for regret [ 6 , 5 , 9 , 10 ] and BAI [ 16 ] . In contrast, we consider general discrete memoryless actuation channels with confusability (typewriter channels as a running example), leveraging zero-error communication tools [ 17 , 14 , 12 ] . Paper Organization. Section II provides our model, objectives, and background on zero-error capacity; Sections III , IV , and V discuss cases 1–3 respectively. II Model and Objectives II-A Bandit instance and objective (BAI) We consider a stochastic K -armed bandit with arms indexed by \mathcal{K}\coloneq\{0,1,\dots,K-1\} . Pulling arm a produces a reward r\sim\nu_{a} with mean \mu_{a}\triangleq\mathbb{E}[r] . Let a^{\star}\in\arg\max_{a\in\mathcal{K}}\mu_{a} denote a best arm (assumed unique for simplicity), and define gaps \Delta_{a}\triangleq\mu_{a^{\star}}-\mu_{a} for a\neq a^{\star} . Our goal is fixed-confidence best-arm identification (BAI) : an algorithm adaptively interacts with the environment, stops at a (random) time \tau , and outputs \hat{a} . It is \delta -correct if \Pr(\hat{a}=a^{\star})\geq 1-\delta. Hence, we measure performance primarily by the total number of physical rounds (pulls). In our interface, each round also uses the command channel once, so the pull count coincides with the number of channel uses. In the noiseless setting, instance - dependent lower and upper bounds show that fixed - confidence BAI can be solved with \Theta\left(\sum_{a\neq a^{\star}}\Delta^{-2}_{a}\log{(1/\delta)}\right) samples (see, e.g., [ 7 , 2 , 3 ] ). We will treat this benchmark as N_{\text{clean}}(\delta,\mu) . II-B Actuation Channel and Arm Mismatch At each time slot t , the learner produces a channel input X_{t}\in\mathcal{X} which is passed through a discrete memoryless channel (DMC) W:\mathcal{X}\to\mathcal{Y} , yielding an output Y_{t}\in\mathcal{Y} at the agent according to W(y\mid x)\;\triangleq\;\Pr(Y_{t}=y\mid X_{t}=x). We consider an arm channel with \mathcal{X}=\mathcal{Y}=\mathcal{K} , so X_{t},Y_{t}\in\mathcal{K} and block codes correspond to sequences X^{n},Y^{n}\in\mathcal{K}^{n} . The agent then executes an arm \tilde{a}_{t}\in\mathcal{K} (as a function of its received symbols and actuation rule), and a reward r_{t} is generated with mean \mu_{\tilde{a}_{t}} . The learner observes r_{t} and its own transmissions X_{t} , but does not observe channel outputs Y_{t} . II-C Zero-error capacity and confusability graphs We briefly introduce notation and review zero-error communication over a DMC. Zero-error rates depend only on which outputs are possible for each input (the support of W ), not on their probabilities [ 17 ] . Define the output support sets \mathcal{Y}(x)\triangleq\{y\in\mathcal{Y}:W(y\mid x)>0\},\qquad x\in\mathcal{X}. Confusability graph The confusability graph of W is the undirected graph G=(V,E) with V=\mathcal{X} and \{x,x^{\prime}\}\in E\quad\Longleftrightarrow\quad\mathcal{Y}(x)\cap\mathcal{Y}(x^{\prime})\neq\emptyset. Blocklength- n packets A length- n packet is an input sequence x^{n}\in V^{n} . Confusability of length- n sequences is captured by the n -fold strong graph power G^{\boxtimes n} : distinct x^{n},(x^{\prime})^{n}\in V^{n} are adjacent in G^{\boxtimes n} iff for all coordinates i , x_{i}=x^{\prime}_{i} or \{x_{i},x^{\prime}_{i}\}\in E [ 17 , 12 ] . Zero-error message count Let \alpha(\cdot) be the independence number. The maximum number of messages conveyable with zero decoding error using exactly n channel uses is M(n)\;\triangleq\;\alpha\!\big(G^{\boxtimes n}\big), (1) via the standard equivalence between zero-error codebooks and independent sets [ 17 ] . Minimal blocklength for a message set For a finite message set \mathcal{S} with |\mathcal{S}|<\infty , define n^{\star}(\mathcal{S})\;\triangleq\;\min\{n\in\mathbb{N}:\alpha(G^{\boxtimes n})\geq|\mathcal{S}|\}. (2) Zero-error capacity Shannon’s zero-error capacity is C_{0}(G)\;\triangleq\;\lim_{n\to\infty}\frac{1}{n}\log_{2}\alpha\!\big(G^{\boxtimes n}\big)\;=\;\log_{2}\Theta(G), (3) where \Theta(G) is the Shannon capacity [ 17 ] . When C_{0}(G)>0 , M(n) grows exponentially in n , so any fixed finite message set is achievable with some finite blocklength.