An LP-based Sampling Policy for Multi-Armed Bandits with Side-Observations and Stochastic Availability

• URL: http://arxiv.org/abs/2603.26647v1
• Date: Fri, 27 Mar 2026 17:50:42 GMT
• Title: An LP-based Sampling Policy for Multi-Armed Bandits with Side-Observations and Stochastic Availability
• Abstract summary: We study the multi-armed bandit (MAB) problem where an underlying network structure enables side-observations across related actions.<n>We use a bipartite graph to link actions to a set of unknowns, such that selecting an action reveals observations for all the unknowns it is connected to.
• Score: 40.54677625701658
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the stochastic multi-armed bandit (MAB) problem where an underlying network structure enables side-observations across related actions. We use a bipartite graph to link actions to a set of unknowns, such that selecting an action reveals observations for all the unknowns it is connected to. While previous works rely on the assumption that all actions are permanently accessible, we investigate the more practical setting of stochastic availability, where the set of feasible actions (the "activation set") varies dynamically in each round. This framework models real-world systems with both structural dependencies and volatility, such as social networks where users provide side-information about their peers' preferences, yet are not always online to be queried. To address this challenge, we propose UCB-LP-A, a novel policy that leverages a Linear Programming (LP) approach to optimize exploration-exploitation trade-offs under stochastic availability. Unlike standard network bandit algorithms that assume constant access, UCB-LP-A computes an optimal sampling distribution over the realizable activation sets, ensuring that the necessary observations are gathered using only the currently active arms. We derive a theoretical upper bound on the regret of our policy, characterizing the impact of both the network structure and the activation probabilities. Finally, we demonstrate through numerical simulations that UCB-LP-A significantly outperforms existing heuristics that ignore either the side-information or the availability constraints.

Related papers

• Learning to Watch: Active Video Anomaly Understanding via Interleaved Policy Optimization [56.150184676745205]
  Video anomaly understanding (VAU) relies on sparse, context-dependent cues.<n>We propose $Anomtext-$, a closed-loop framework that reconceptualizes video understanding as an active sequential decision-making process.<n>Inspired by human video-reviewing behavior, this framework unifies internal cognitive reasoning and strategic evidence acquisition into an interleaved policy.
  arXiv  Detail & Related papers  (2026-07-01T08:41:49Z)
• Stochastic Encodings for Active Feature Acquisition [100.47043816019888]
  Active Feature Acquisition is an instance-wise, sequential decision making problem.<n>The aim is to dynamically select which feature to measure based on current observations, independently for each test instance.<n>Common approaches either use Reinforcement Learning, which experiences training difficulties, or greedily maximize the conditional mutual information of the label and unobserved features, which makes myopic.<n>We introduce a latent variable model, trained in a supervised manner. Acquisitions are made by reasoning about the features across many possible unobserved realizations in a latent space.
  arXiv  Detail & Related papers  (2025-08-03T23:48:46Z)
• Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
  We propose SEQUOIA, an RL algorithm that directly optimize for long-term reward over the feasible action space.<n>We empirically validate SEQUOIA on four novel restless bandit problems with constraints: multiple interventions, path constraints, bipartite matching, and capacity constraints.
  arXiv  Detail & Related papers  (2025-03-01T21:25:21Z)
• Scalable Multi-Agent Offline Reinforcement Learning and the Role of Information [37.18643811339418]
  We propose a novel scalable routine for both dataset collection and offline learning.<n>Agents first collect diverse datasets coherently with a pre-specified information-sharing network.<n>We show how this approach allows to bound the inherent error of the supervised-learning phase of FQI with the mutual information between shared and unshared information.
  arXiv  Detail & Related papers  (2025-02-16T20:28:42Z)
• Offline Learning for Combinatorial Multi-armed Bandits [56.96242764723241]
  Off-CMAB is the first offline learning framework for CMAB.<n>Off-CMAB combines pessimistic reward estimations with solvers.<n>Experiments on synthetic and real-world datasets highlight the superior performance of CLCB.
  arXiv  Detail & Related papers  (2025-01-31T16:56:18Z)
• Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts [27.62165569135504]
  A line of research, known as online clustering of bandits, extends contextual MAB by grouping similar users into clusters.<n>Existing algorithms, which rely on the upper confidence bound (UCB) strategy, struggle to gather adequate statistical information to accurately identify unknown user clusters.<n>We propose two novel algorithms, UniCLUB and PhaseUniCLUB, which incorporate enhanced exploration mechanisms to accelerate cluster identification.
  arXiv  Detail & Related papers  (2025-01-01T16:38:29Z)
• Distributed Multi-Task Learning for Stochastic Bandits with Context Distribution and Stage-wise Constraints [0.0]
  We present conservative distributed multi-task learning in linear contextual bandits with heterogeneous agents.<n>The exact context is unknown, and only a context distribution is available to the agents.<n>Our algorithm constructs a pruned action set during each round to ensure the constraints are met.<n>It includes synchronized sharing of estimates among agents via a central server.
  arXiv  Detail & Related papers  (2024-01-21T18:43:55Z)
• Federated Learning for Heterogeneous Bandits with Unobserved Contexts [0.0]
  We study the problem of federated multi-arm contextual bandits with unknown contexts. We propose an elimination-based algorithm and prove the regret bound for linearly parametrized reward functions.
  arXiv  Detail & Related papers  (2023-03-29T22:06:24Z)
• Generative Slate Recommendation with Reinforcement Learning [49.75985313698214]
  reinforcement learning algorithms can be used to optimize user engagement in recommender systems. However, RL approaches are intractable in the slate recommendation scenario. In that setting, an action corresponds to a slate that may contain any combination of items. In this work we propose to encode slates in a continuous, low-dimensional latent space learned by a variational auto-encoder. We are able to (i) relax assumptions required by previous work, and (ii) improve the quality of the action selection by modeling full slates.
  arXiv  Detail & Related papers  (2023-01-20T15:28:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.