Technical Summary: Flickering Multi-Armed Bandits

1. Problem Formulation

The paper introduces the Flickering Multi-Armed Bandit (FMAB) framework to address sequential decision-making in environments where action availability is dynamic, restricted, and dependent on the agent's current state. Unlike classical Multi-Armed Bandit (MAB) problems, which assume unrestricted access to a fixed set of arms, FMAB models scenarios where an agent can only select from a subset of arms defined by its current location in a stochastically evolving graph.

Core Constraints:

• Local Accessibility: At any round $t$, the agent resides at arm $a_{t-1}$. The set of available arms $L_t(a_{t-1})$ is restricted to the neighborhood of $a_{t-1}$ in the current graph $G_t$, plus the current arm itself.
• Stochastic Evolution: The graph $G_t$ evolves over time. The agent cannot jump arbitrarily to any arm; it must navigate through the graph structure to reach unvisited or promising arms.
• Dual Challenge: The agent faces a tension between statistical information acquisition (exploring arms to identify the optimal one) and physical navigation overhead (the cost of moving through the graph to reach those arms).

Graph Models:
The authors formalize the evolution of action availability through two primary random graph processes:

1. i.i.d. Erdős–Rényi (ER): At each round, a new graph is sampled independently. Edges exist with probability $p$ (homogeneous) or edge-specific probabilities $p_{ij}$ (heterogeneous).
2. Edge-Markovian: The graph evolves from the previous state. Edges appear with probability $\alpha$ and disappear with probability $\beta$. This models "sticky" connectivity where the topology changes gradually rather than resetting completely.

The objective is to minimize cumulative regret $R(T) = \sum_{t=1}^T (\mu(a^*) - r_t(a_t))$, where $a^*$ is the optimal arm, subject to these local-move constraints.

2. Methodology

The proposed solution is a Two-Phase Learning Algorithm that utilizes a Lazy Random Walk for exploration.

Phase I: Best Arm Identification (Exploration)

• Policy: The agent performs a lazy random walk. At each step, given the current arm $a_{t-1}$ and the realized graph $G_t$, the agent selects the next arm $a_t$ uniformly at random from the available set $L_t(a_{t-1})$.
• Duration: This phase lasts for a predetermined time $T_0$.
• Goal: To collect sufficient samples from all arms to estimate their mean rewards $\hat{\mu}(a)$ accurately.
• Termination: At the end of Phase I, the agent identifies the candidate optimal arm $\hat{a}^* = \arg\max_a \hat{\mu}(a)$.

Phase II: Navigation & Commitment (Exploitation)

• Policy: The agent continues the lazy random walk until it successfully reaches the identified target $\hat{a}^*$.
• Commitment: Once the agent lands on $\hat{a}^*$, it commits to this arm for all subsequent rounds. Since the agent can always stay at its current arm (self-loop), it remains at $\hat{a}^*$ indefinitely.

Theoretical Analysis Techniques

The analysis bridges spectral techniques for evolving Markov chains with concentration inequalities for time-varying graphs:

• For i.i.d. ER Graphs:
  • Homogeneous Case: The expected transition kernel is symmetric and doubly stochastic, yielding a uniform stationary distribution. The authors use a regeneration argument to show the walk mixes efficiently.
  • Heterogeneous Case: The kernel is not symmetric. The authors employ a uniform typicality argument, proving that realized graph properties (degrees, cuts) concentrate sharply around their expected values, allowing for uniform bounds on the spectral gap and stationary distribution.
• For Edge-Markovian Graphs:
  • The analysis addresses the coupling between the agent's walk and the graph's evolution.
  • A "Two Speeds" condition is established: The graph must evolve slowly enough (stickiness condition $\beta \le O(1/n)$) relative to the mixing speed of the random walk.
  • The algorithm requires a burn-in period ($T_{burn}$) for the graph process to reach its stationary distribution before the standard exploration phase begins.

3. Key Results

Regret Bounds

The paper establishes high-probability sublinear regret bounds for both graph models.

Theorem 1 (i.i.d. ER Graphs):
For the heterogeneous ER model, the regret $R(T)$ satisfies with probability $1-\delta$:
$$R(T) \le \underbrace{O\left(n \log(nT/\delta) + \frac{n \log(n/\delta)}{\Delta_{\min}^2}\right)}_{\text{Exploration Cost}} + \underbrace{O\left(n \log(n/\delta)\right)}_{\text{Navigation Cost}}$$
where $\Delta_{\min}$ is the minimum sub-optimality gap. The exploration cost scales linearly with the number of arms $n$, and the navigation cost accounts for the time to reach the optimal arm.

Theorem 3 (Edge-Markovian Graphs):
Under typicality and stickiness conditions, the regret includes an additional burn-in term:
$$R(T) \le \underbrace{O\left(\frac{\log(nT/\delta)}{\alpha+\beta}\right)}_{\text{Burn-in}} + \underbrace{O\left(n \log(nT/\delta) + \frac{n \log(n/\delta)}{\Delta_{\min}^2}\right)}_{\text{Exploration}} + \underbrace{O\left(n \log(n/\delta)\right)}_{\text{Navigation}}$$

Expected Regret and Near-Optimality

By setting the failure probability $\delta = 1/T$, the authors derive the expected regret bound:
$$E[R(T)] = O\left(\frac{n \log(nT)}{\Delta_{\min}^2}\right)$$
The paper proves that this bound is near-optimal by deriving an information-theoretic lower bound. The lower bound shows that any algorithm must incur an identification time of $\Omega(n \log(T)/\Delta_{\min}^2)$. The proposed two-phase approach matches this lower bound up to logarithmic factors, demonstrating that the "cost of navigation" does not fundamentally increase the statistical hardness of the problem beyond the identification requirement.

Simulations

The theoretical findings are validated through:

1. Controlled Experiments: Simulations on i.i.d. ER and Edge-Markovian graphs confirm that average regret converges to zero and that navigation time scales inversely with edge probability $p$ (i.e., $O(1/p)$).
2. Robotic Disaster Response Scenario: A simulation of a ground vehicle scouting for communication relay sites in a disaster zone. The vehicle operates with local sensing (no global map) and navigates a dynamically changing street network (Edge-Markovian). The results show the algorithm successfully identifies the optimal location and converges to it, validating the practical applicability of the FMAB model.

4. Significance and Contributions

The paper claims the following contributions:

• Novel Framework: It introduces the FMAB model, which is the first to explicitly couple local-move constraints (navigation) with sequential decision-making under uncertainty. This addresses a gap in existing literature where "Sleeping" or "Volatile" bandits assume availability is independent of the agent's actions or globally known.
• Unified Analysis: It provides a unified regret analysis for learning on evolving random graphs, handling both i.i.d. and Markovian dynamics.
• Algorithmic Robustness: The proposed lazy random walk strategy is shown to be robust across diverse connectivity regimes (homogeneous, heterogeneous, and time-correlated).
• Fundamental Limits: By establishing a matching lower bound, the work characterizes the intrinsic cost of learning under local-move constraints, proving that the physical overhead of navigation does not degrade the fundamental statistical rate of learning (up to log factors).
• Practical Relevance: The work bridges theoretical online learning with physical constraints, offering a rigorous foundation for applications in robotics, disaster response, and networked systems where agents cannot teleport between options.

The authors conclude that while the high-probability analysis depends on specific graph parameters, the final expected regret depends only on fundamental problem parameters ($n, T, \Delta_{\min}$), suggesting that the structural constraints of the environment are effectively managed by the proposed exploration strategy.