Skip to content

Adapting to Decision-Relevant Non-Stationarity in Decentralized Heterogeneous Bandits

Sep 2026 · arXiv.org · Vol abs/2609.16824 · 0 citations
Computer Science

TL;DR

This work introduces Decision-Relevant Fresh Comparison (DRFC), which uses new, balanced samples from all agents to compare arms at the network level and switches only when fresh global evidence indicates that the common best arm has changed, and proves a high-probability dynamic regret bound with no adaptation term depending on $\Stloc$.

Abstract

Decentralized bandit systems often contain heterogeneous agents: rewards can change at individual agents even when the best action for the network stays the same. These local changes may cancel when rewards are averaged across agents, so the number of local changes $\Stloc$ can be much larger than the number of changes in the best common arm $\Stdec$. We introduce Decision-Relevant Fresh Comparison (DRFC), which uses new, balanced samples from all agents to compare arms at the network level and switches only when fresh global evidence indicates that the common best arm has changed. We prove a high-probability dynamic regret bound with no adaptation term depending on $\Stloc$, and show that every algorithm must still pay for identifying genuine decision switches and propagating them through the communication graph. Under a distinct time-average benchmark, an anytime-valid sliding-window extension handles gradual drift; experiments on synthetic, semi-real, and MovieLens-1M replays show that DRFC ignores decision-irrelevant local changes while the extension avoids false switches.

View source

Similar papers

Preprint Aug 2026

The Price of Decentralization in Top-$K$ Arm Identification

Change-of-measure lower bounds show that shared-reward identification is optimal up to one universal logarithmic factor, and that the entire statistical price of removing communication is a multiplicative $\rho^2$ in sample complexity.

Larissa Xu, Jasmine Nguyen, William Chang · 0 citations
Review

Non‑ S tationary Multi‑Armed Bandits: Evolution and Challenges of Dynamic Decision‑Making Frameworks

This review systematically examines two types of algorithms: passive methods (e.g., sliding-window UCB, discounted UCB), which filter out outdated data’s interference through forgetting mechanisms; and active methods (e.g., TS-CD, R-BOCPD), which dynamically update their parameters by detecting changes.

Ran An · 0 citations
#artificial intelligence Preprint Aug 2026

COVER: Identifiable Evaluation of Coalition Routing

COLD is an auditable measurement methodology, an evaluation contract that fixes a public information boundary, downstream stack G, and finite legal team family before outcomes are generated, which exposes selection headroom without manufacturing a routing win.

R. Sugumar, Amrit Gopinath · 0 citations
#machine learning Preprint Aug 2026

Constant Individual Regret in General Games

This work introduces \emph{ECHO-OFTRL}: optimistic follow-the-regularized-leader (OFTRL) equipped with an EMA cascade for high-order optimism (ECHO), where EMA denotes exponential moving average, and leverages a new form of optimism inspired by modern filter design.

Mingyang Liu, Gabriele Farina, A. Ozdaglar · 6 citations · ⚡4
#machine learning Preprint Sep 2026

Measuring the Value of World-Model Updates: A Counterfactual Utility Protocol for Continual Adaptation

The fork ledger is introduced, which branches a deployment stream at pre-registered decision points into matched update and hold continuations under common random numbers, allowing triggers to be judged by the updates they select rather than by surprise detection alone.

An-Qi Li, Kaden Kim · 1 citation

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.