Paper Overview
- Field: Machine Learning
- Authors: Ashutosh Soni, Peizhong Ju, Atilla Eryilmaz
- Posted: 2025-03-30
- arXiv: 2503.23700
- Models MAB with side-observations via a bipartite graph under stochastic arm availability (varying activation sets per round).
- Proposes UCB-LP-A, an LP-based sampling policy for the exploration-exploitation trade-off under availability constraints.
- Derives theoretical regret upper bounds characterizing the impact of network structure and activation probabilities.
- Numerical simulations show UCB-LP-A significantly outperforms existing heuristics that ignore side-information or availability constraints.
Summary
We study the stochastic multi-armed bandit (MAB) problem where an underlying network structure enables side-observations across related actions. A bipartite graph connects actions to a set of unknowns, so selecting an action reveals observations of all unknowns connected to it. While previous work assumes all actions are permanently accessible, we study the more practical stochastic availability setting, where the set of playable arms (the "activation set") changes dynamically each round. This framework models real systems with structural dependencies and volatility, such as social networks, where users provide side-information about peer preferences but are not always online and queryable.
To address this challenge, we propose UCB-LP-A, a novel policy that uses a linear programming (LP) approach to optimize the exploration-exploitation trade-off under stochastic availability. Unlike standard network bandit algorithms that assume constant access, UCB-LP-A computes the optimal sampling distribution achievable on each activation set, ensuring the necessary observations are collected using only the currently active arms.