Flickering Multi-Armed Bandits

• URL: http://arxiv.org/abs/2602.17315v1
• Date: Thu, 19 Feb 2026 12:24:01 GMT
• Title: Flickering Multi-Armed Bandits
• Authors: Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni, Lijun Chen,
• Abstract summary: We introduce Flickering Multi-Armed Bandits (FMAB), a new MAB framework where the set of available arms (or actions) can change at each round.<n>We model this constrained, evolving availability using random graph processes, where arms are nodes and the agent's movement is restricted to its local neighborhood.<n>We show that our algorithm is near-optimal by establishing a matching information-theoretic lower bound for this problem class.
• Score: 7.465238700168576
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce Flickering Multi-Armed Bandits (FMAB), a new MAB framework where the set of available arms (or actions) can change at each round, and the available set at any time may depend on the agent's previously selected arm. We model this constrained, evolving availability using random graph processes, where arms are nodes and the agent's movement is restricted to its local neighborhood. We analyze this problem under two random graph models: an i.i.d. Erdős--Rényi (ER) process and an Edge-Markovian process. We propose and analyze a two-phase algorithm that employs a lazy random walk for exploration to efficiently identify the optimal arm, followed by a navigation and commitment phase for exploitation. We establish high-probability and expected sublinear regret bounds for both graph settings. We show that the exploration cost of our algorithm is near-optimal by establishing a matching information-theoretic lower bound for this problem class, highlighting the fundamental cost of exploration under local-move constraints. We complement our theoretical guarantees with numerical simulations, including a scenario of a robotic ground vehicle scouting a disaster-affected region.

Related papers

• Influential Bandits: Pulling an Arm May Change the Environment [44.71145269686588]
  Real-world applications often involve non-stationary environments and interdependencies between arms.<n>We propose the influential bandit problem, which models inter-arm interactions through an unknown, symmetric, positive semi-definite interaction matrix.<n>We introduce a new algorithm based on a lower confidence bound (LCB) estimator tailored to the structure of the loss dynamics.
  arXiv  Detail & Related papers  (2025-04-11T02:05:51Z)
• Semi-Parametric Batched Global Multi-Armed Bandits with Covariates [0.48342038441006807]
  The multi-armed bandits (MAB) framework is a widely used approach for sequential decision-making.<n>We propose a novel semi-parametric framework for batched bandits with coparametrics and a shared parameter across arms.<n>Our algorithm, Batched single-Index Dynamic binning and Successive arm elimination (BIDS), employs a batched successive arm elimination strategy.
  arXiv  Detail & Related papers  (2025-03-01T17:23:55Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  We consider a multi-armed bandit setting in which each arm yields an $M$-dimensional vector reward upon selection.<n>The end goal is to identify the best arm of em every objective in the shortest (expected) time subject to an upper bound on the probability of error.<n>We propose an algorithm that uses the novel idea of em surrogate proportions to sample the arms at each time step, eliminating the need to solve the max-min optimisation problem at each step.
  arXiv  Detail & Related papers  (2025-01-23T12:28:09Z)
• Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints [8.784438985280094]
  We study problems as pure exploration in multi-armed bandits with unknown linear constraints. First, we propose a Lagrangian relaxation of the sample complexity lower bound for pure exploration under constraints. Second, we leverage the Lagrangian lower bound and the properties of convex to propose two computationally efficient extensions of Track-and-Stop and Gamified Explorer, namely LATS and LAGEX.
  arXiv  Detail & Related papers  (2024-10-24T15:26:14Z)
• Latency-Aware Contextual Bandit: Application to Cryo-EM Data Collection [23.51929492181581]
  We introduce a latency-aware contextual bandit framework that generalizes the standard contextual bandit problem.<n>In this setting, the learner observes the context and may select multiple arms from a decision set, with the total time determined by the selected subset.<n>We show that our algorithm balances exploration, exploitation, and action latency to minimize regret relative to the optimal average-reward policy.
  arXiv  Detail & Related papers  (2024-10-17T00:44:50Z)
• Best Arm Identification under Additive Transfer Bandits [49.69203462561861]
  We study the setting when, despite the means being unknown, there is a known additive relationship between the source and target MAB instances. We propose and theoretically analyze an LUCB-style algorithm to identify an $epsilon$-optimal target arm with high probability.
  arXiv  Detail & Related papers  (2021-12-08T02:20:18Z)
• PAC Best Arm Identification Under a Deadline [101.10352416022559]
  We study $(epsilon, delta)$-PAC best arm identification, where a decision-maker must identify an optimal arm with probability at least $1 - delta$, while minimizing the number of arm pulls (samples) In this work, the decision-maker is given a deadline of $T$ rounds, where, on each round, it can adaptively choose which arms to pull and how many times to pull them. We propose Elastic Batch Racing (EBR), a novel algorithm for this setting and bound its sample complexity, showing that EBR is optimal with respect to both
  arXiv  Detail & Related papers  (2021-06-06T19:48:32Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  We study exploration in multi-armed bandits when we have access to a divisible resource that can be allocated in varying amounts to arm pulls. We focus in particular on the allocation of distributed computing resources, where we may obtain results faster by allocating more resources per pull.
  arXiv  Detail & Related papers  (2020-10-31T18:19:29Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  We consider the contextual bandit problem under the high dimensional linear model. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. We propose doubly growing epochs and estimating the parameter using the best subset selection method.
  arXiv  Detail & Related papers  (2020-09-04T04:10:39Z)

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.