Bandit algorithm adapts to shared decision changes ignoring local noise
Adapting to Decision-Relevant Non-Stationarity in Decentralized Heterogeneous Bandits
Machine Learning
Summary
In systems where many agents choose actions and get rewards that can change individually without affecting the overall best choice, the authors found a way to focus on when the best action really changes for the whole network. Their method, DRFC, collects new information from all agents to decide if a switch in the best action is truly needed, ignoring local reward changes that don’t matter to network decisions. This reduces unnecessary switching and improves decision-making. They also extended their approach to handle gradual changes over time and tested it on different data showing its effectiveness.
What this means in practice
- •For networked control teams: Manage decision updates in distributed control systems where local sensor data vary but overall control targets remain stable.
- •For recommendation system engineers: Improve handling of user preference changes across regions by focusing on global shifts rather than local noise in reward feedback.
Authors
Zhaojun Peng
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.