Paper deep dive
Flickering Multi-Armed Bandits
Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni, Lijun Chen
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 7/21/2026, 12:05:14 AM
Summary
The paper introduces Flickering Multi-Armed Bandits (FMAB), a sequential decision-making framework where action availability is restricted to a local neighborhood dependent on the agent's current choice, modeled via stochastically evolving graphs (i.i.d. Erdős–Rényi and Edge-Markovian). The authors propose a two-phase lazy random walk algorithm for exploration and exploitation, establishing high-probability sublinear regret bounds and proving near-optimality through information-theoretic lower bounds, validated by robotic disaster-response simulations.
Entities (10)
Relation Signals (9)
Amit Kiran Rege → authored → Flickering Multi-Armed Bandits
confidence 99% · Name Amit Kiran Rege... We introduce Flickering Multi-Armed Bandits
Sourav Chakraborty → authored → Flickering Multi-Armed Bandits
confidence 99% · Name Sourav Chakraborty... We introduce Flickering Multi-Armed Bandits
Lijun Chen → authored → Flickering Multi-Armed Bandits
confidence 99% · Name Lijun Chen... We introduce Flickering Multi-Armed Bandits
Claire Monteleoni → authored → Flickering Multi-Armed Bandits
confidence 99% · Name Claire Monteleoni... We introduce Flickering Multi-Armed Bandits
Flickering Multi-Armed Bandits → uses → Erdős–Rényi Graph Process
confidence 95% · We analyze FMAB under i.i.d. Erdős--R'enyi and Edge-Markovian process
Flickering Multi-Armed Bandits → uses → Edge-Markovian Process
confidence 95% · We analyze FMAB under i.i.d. Erdős--R'enyi and Edge-Markovian process
Flickering Multi-Armed Bandits → solvedby → Two-phase lazy random walk algorithm
confidence 92% · proposing a two-phase lazy random walk algorithm for robust exploration
Two-phase lazy random walk algorithm → achieves → Sublinear regret bounds
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We introduce Flickering Multi-Armed Bandits (FMAB) to model sequential decision-making in environments with changing action availability, where accessibility of the next action is restricted to a subset dependent on the agent's current choice. We formalize these constraints through stochastically evolving graphs where actions are limited to local neighborhoods. This mobility-constrained structure imposes a dual challenge: the statistical requirement of information acquisition and the physical overhead of navigation. We analyze FMAB under i.i.d. Erdős--R'enyi and Edge-Markovian process, proposing a two-phase lazy random walk algorithm for robust exploration. We establish high-probability sublinear regret bounds and prove near-optimality via a matching information-theoretic lower bound. Our results characterize the intrinsic cost of learning under local-move constraints, complemented by a robotic disaster-response simulation.
Tags
Links
- Source: https://arxiv.org/abs/2602.17315v3
- Canonical: https://arxiv.org/abs/2602.17315v3
Trouble viewing inline? Open PDF directly →
Full Text
221,483 characters extracted from source content.
Expand or collapse full text
* max * min Flickering Multi-Armed Bandits Chakraborty† .chakraborty@colorado.edu Kiran Rege†111Equal Contribution with S. Chakraborty. .rege@colorado.edu Monteleoni†‡ .monteleoni@colorado.edu Chen† .chen@colorado.edu †University of Colorado Boulder USA. ‡INRIA Paris France Abstract We introduce Flickering Multi-Armed Bandits (FMAB) to model sequential decision-making in environments with changing action availability, where accessibility of the next action is restricted to a subset dependent on the agent’s current choice. We formalize these constraints through stochastically evolving graphs where actions are limited to local neighborhoods. This mobility-constrained structure imposes a dual challenge: the statistical requirement of information acquisition and the physical overhead of navigation. We analyze FMAB under i.i.d. Erdős–Rényi and Edge-Markovian process, proposing a two-phase lazy random walk algorithm for robust exploration. We establish high-probability sublinear regret bounds and prove near-optimality via a matching information-theoretic lower bound. Our results characterize the intrinsic cost of learning under local-move constraints, complimented by a robotic disaster-response simulation. keywords: Online Learning; Multi-Armed Bandits. 1 Introduction In the aftermath of a natural disaster, emergency responders must rapidly restore communication capabilities across a disrupted and unstable region. A robotic ground vehicle is deployed to scout candidate locations, moving carefully through streets that may be temporarily blocked by debris or diverted traffic. The environment is fluid: pathways open and close unexpectedly, and access to promising sites may vanish without warning. At each stop, the vehicle assesses the quality of local coverage it could provide if deployed there. Over time, it explores locations, limited to nearby, currently accessible sites, while building a sense of which locations offer the most promise. After navigating this uncertain landscape, the vehicle must ultimately select the site where it can provide the most reliable service, deploying the relay at that location to support ongoing recovery efforts. This scenario reveals a decision-making structure where the agent interacts with an environment with changing availability of actions. At each step, it can access only a limited subset of those actions, dependent on the agent’s most recent choice. This class of problems falls under the broad umbrella of sequential decision-making under uncertainty, a domain formally studied through the multi-armed bandit (MAB) framework (thompson1933likelihood; lai1985asymptotically). In its classical form, the learner repeatedly interacts with a fixed set of actions (referred to interchangeably as arms), each of which yields an unknown real-valued payoff, or reward. At each round, the learner selects one arm, receives a corresponding reward, and uses this information to guide future decisions. The goal is to make a sequence of choices that collectively lead to high cumulative reward over time. At its core, the MAB model captures the tension between selecting uncertain actions to improve the agent’s knowledge (exploration), and leveraging current beliefs to choose the action that appears most promising (exploitation). This model has been successfully applied across a wide range of applications, including clinical trials (gittins1), wireless communication (cogradio), recommendation systems (Li_2010; bouneffouf:hal-00753401), financial optimization (brochu), and economically motivated incentivized explorations (fraz; wang; liu20; chakraborty2024incentivized; chakraborty2025incentivized). Classical MAB framework provides a rich suite of strategies for balancing exploration and exploitation, supported by well-established theoretical guarantees (see surveys (slivkins2024introduction; lattimore_2020)). However, these results assume that the learner has unrestricted access to all actions. This assumption fails in many real-world settings, including the emergency relay deployment example mentioned earlier, where the set of available actions may change over time and depend on the agent’s most recent choice. In such environments, the learner is constrained to select from only a limited, dynamically varying subset of actions at each step. These limitations fundamentally alter the learning problem and require new models that explicitly account for restricted and evolving access to actions. We introduce the Flickering Multi-Armed Bandit (FMAB) model, where the set of available actions: (i) may be a restricted subset of the full action set, (i) can change over time, and (i) may depend on the agent’s most recent arm choice. As in standard bandit problems, the learner’s objective is to maximize cumulative reward by identifying and repeatedly selecting high-performing actions. However, FMAB introduces a local-move constraint: while the agent may eventually reach any arm over the long-term, it may lack global access to the entire action set at any single round. This requires a strategy that balances the need to visit all arms for identification with the challenge of navigating a landscape of fluctuating connectivity. We formalize the constraints through random graph processes defined over the action set. Under this representation, the available actions at each round are restricted to the neighborhood of the learner’s current arm. We consider two primary graph processes. First, we analyze the i.i.d. setting, defined by the Erdős–Rényi (ER) model (erdos1960evolution), where each potential edge is sampled independently at every round. Our analysis addresses the general heterogeneous case where probabilities are edge-specific, which inherently encompasses the homogeneous setting of uniform probabilities as a special instance (see Section 2). Second, we introduce the Edge-Markovian model (edge-flip1; edge-flip2). In this setting, the graph is not fully re-sampled; instead, it evolves from an initial map as edges independently appear or disappear according to fixed probabilities (see Section 2). Contributions. We formalize the FMAB framework (see Figure 1) to characterize environments where action availability is both dynamic and dependent on the agent’s preceding selection. We model these constraints using two canonical processes: (i) i.i.d. Erdős–Rényi evolution (encompassing both homogeneous and heterogeneous cases) and (i) Edge-Markovian process. We analyze learning under the structural evolution of random graphs, not previously addressed. Our work bridges spectral techniques for evolving Markov chains with concentration tools for time-varying graphs to provide a unified regret analysis. We establish high-probability sublinear regret bounds and demonstrate their near-optimality by deriving a matching information-theoretic lower bound. To our knowledge, this is the first analysis to couple lazy-walk exploration with these specific classes of evolving availability. Finally, we validate our theoretical findings through simulations, including a robotic scouting scenario in a disaster-response environment. Figure 1: A 4-arm FMAB problem at t=s,s+1,s+2t=s,s+1,s+2, with pull sequence as=3,as+1=4,as+2=2a_s=3,a_s+1=4,a_s+2=2 (from as−1=1a_s-1=1). (A) Problem view: Blue/White arms are accessible/inaccessible. Pulled arm has a dark blue border. (B) Graph view: Learner starts at the dark blue node (at−1a_t-1) and can move to blue neighbors (Lt(at−1)L_t(a_t-1)). Related work. The Sleeping Bandits model (kleinberg2010regret) features time-varying arm sets, but availability is independent of the learner’s actions and measured against a different, time-varying benchmark. Mortal Bandits (chakrabarti2008mortal) consider arms that disappear intermittently or permanently, but maintain a constant number of active arms and reveal the availability set at each round regardless of the past action. Volatile Bandits (bnaya2013volatile) associate arms with unknown lifespans and have time-varying rewards, causing the optimal action to shift. Graph-based bandit models (lina-graph; lina-graph-2) also place arms on a graph, but typically assume a fixed, globally-known graph, which enables shortest-path-based planning. In contrast, FMAB models availability using a changing graph, and we develop lightweight algorithms that rely only on neighborhood information. 2 Models and Problem Formulation We consider a finite set of n arms (or actions) A=1,2,…,nA=\1,2,…,n\, with each arm a∈Aa∈ A associated with a fixed but unknown reward distribution (a)D(a) on [0,1][0,1] and mean μ(a)∈[0,1]μ(a)∈[0,1]. Without the loss of generality, we assume a∗ argmaxa∈Aμ(a)a^* _a∈ Aμ(a) to be the unique optimal arm. We denote the sub-optimality gap for any other arm as Δ(a) μ(a∗)−μ(a)>0 (a) μ(a^*)-μ(a)>0. The learner’s objective is to maximize the cumulative reward over a time horizon T. Since the reward of the optimal arm is a fixed benchmark, this is equivalent to minimizing the regret R(T)R(T), defined as the difference between the total reward achievable by an oracle and the learner’s cumulative reward: R(T) ∑t=1T(μ(a∗)−rt(at)).R(T) _t=1^T (μ(a^*)-r_t(a_t) ). The goal is to design a learning algorithm that selects a sequence of actions a1,…,aTa_1,…,a_T to ensure the expected regret is sublinear, i.e., [R(T)]=o(T)E[R(T)]=o(T), as T→∞T→∞. A key feature of our model is that the learner’s access to arms is constrained by a stochastically evolving graph. At each round t, the environment reveals a graph Gt=(A,Et)G_t=(A,E_t) over the action set. The learner, residing at its previously chosen arm at−1a_t-1, gets access only to its neighborhood, which defines the set of available arms as: Lt(at−1) a∈A:(a,at−1)∈Et∪at−1.L_t(a_t-1) \\,a∈ A:(a,a_t-1)∈ E_t\,\∪\a_t-1\. The learner then selects an arm at∈Lt(at−1)a_t∈ L_t(a_t-1), and receives a stochastic reward rt(at)∼(at)r_t(a_t) (a_t). To describe the stochastic evolution of the graphs Gt\G_t\, we introduce a general graph evolution operator Ψ:×Θ→(), :G× (G), where G denotes the space of graphs on the node set A, Θ is a model-specific parameter space, and ()P(G) is the space of probability measures over G. At each round, the environment samples the next graph according to Gt∼Ψ(Gt−1;θ)G_t (G_t-1;θ), where θ∈Θθ∈ specifies the parameters governing the evolution. We now define the two graph processes that form the basis of our analysis. Figure 2: Evolution of FMAB availability graphs. (A) i.i.d. ER evolution: edge re-sampling with some probability pijp_ij for each edge (i,j)(i,j) across snapshots t,t+1,t+2t,t+1,t+2. (B) Edge-Markovian process: evolution featuring appearing edges (green solid, with probability α) and disappearing edges (red dotted, with probability β) relative to the preceding round. Erdős–Rényi (ER) Graph Process. In this setting, the environment generates an i.i.d. sequence of graphs Gt\G_t\ (see Figure 2 (A)). We define this through the heterogeneous ER model, ΨhetER(θ) ^ER_het(θ), with parameters θ=(n,pij)θ=(n,\p_ij\). At each round t, a new graph Gt=(A,Et)G_t=(A,E_t) is realized by including each possible edge (i,j)∈Et(i,j)∈ E_t independently with probability pijp_ij. This model effectively captures environments with non-uniform connectivity across the action set. The homogeneous model, ΨhomER(θ) ^ER_hom(θ) with θ=(n,p)θ=(n,p), is a special case where pij=p_ij=p for all pairs (i,j)(i,j). Because the sequence of graphs is i.i.d., the distribution of GtG_t is independent of the previous graph Gt−1G_t-1. Consequently, we omit the conditional argument from the notation for this process. Edge-Markovian Graph Process. This process is defined by the operator ΨM(Gt−1;θ) ^M(G_t-1;θ) with parameters θ=(n,α,β)θ=(n,α,β) (see Figure 2 (B)). In this model, the graph Gt=(A,Et)G_t=(A,E_t) evolves from the previous configuration Gt−1G_t-1 as each potential edge follows an independent, time-homogeneous Markov chain with two states. Specifically, an edge absent in Gt−1G_t-1 appears in GtG_t with probability α∈(0,1)α∈(0,1), and an edge present in Gt−1G_t-1 disappears with probability β∈(0,1)β∈(0,1). These transitions occur independently across all edges. This formulation allows the framework to capture environments where action availability is dictated by the preceding graph configuration, effectively modeling the “stickiness” or persistence of connectivity over time. The evolving graph models above impose localized access (see Figure 1): at each round, the learner can only move to neighbors in GtG_t, restricting standard bandit strategies that assume global access. In the next section, we introduce algorithms that use only local movement and feedback. 3 A Phase-Based Learning Algorithm Our algorithm is a two-phase learning strategy: an exploration phase of a predetermined length T0T_0, followed by an exploitation phase. To facilitate this, the learner maintains two quantities for all arms a∈Aa∈ A, initialized to zero: the total visitation count ϕt(a) _t(a) and cumulative reward sum St(a)S_t(a). • Phase I (Best Arm Identification, 1≤t≤T01≤ t≤ T_0): The goal of this phase is to collect sufficient information to identify the optimal arm. To do this, the learner employs a lazy random walk policy, defined by a one-step transition kernel WtW_t. At each round, the learner selects ata_t uniformly at random from the available set Lt(at−1)L_t(a_t-1): Wt(i,j) W_t(i,j) ℙ(at=j|at−1=i,Gt)=1|Lt(i)|∀j∈Lt(i) (a_t=j|a_t-1=i,G_t)= 1|L_t(i)| ∀ j∈ L_t(i) Wt(i,j) W_t(i,j) =0if j∉Lt(i). =0 j∉ L_t(i). Upon selecting ata_t and receiving rt(at)r_t(a_t), the learner updates its trackers: ϕt(at)=ϕt−1(at)+1 _t(a_t)= _t-1(a_t)+1 and St(at)=St−1(at)+rt(at)S_t(a_t)=S_t-1(a_t)+r_t(a_t). At the end of this phase (at round T0T_0), the learner identifies the target arm by computing the empirical means μ^(a) ST0(a)/ϕT0(a) μ(a) S_T_0(a)/ _T_0(a) (using μ^(a)=0 μ(a)=0 if ϕT0(a)=0 _T_0(a)=0), and setting a^∗ argmaxa∈Aμ^(a) a^* _a∈ A μ(a). • Phase I (Navigation & Commitment, T0<t≤T_0<t≤ T): With the target arm a^∗ a^* now identified, the learner continues to follow the same lazy random walk policy WtW_t until the first round T0<τ≤T_0<τ≤ T that it lands on a^∗ a^*. For all subsequent rounds τ<t≤Tτ<t≤ T, the learner selects at=a^∗a_t= a^*. The above algorithm serves as a unified template across all graph models, but its performance analysis and the choice of the phase length T0T_0 depend on the evolution dynamics of the environment, that we will analyze in Section 4. 4 Performance Guarantees We now present our main theoretical results, establishing high-probability, sublinear regret guarantees for the two-phase learning algorithm introduced in Section 3. We analyze the algorithm’s performance under the two primary random graph models mentioned in Section 2. 4.1 Regret for FMAB with i.i.d. Erdős–Rényi Graphs We first analyze our algorithm (Section 3) under i.i.d. graph evolution. During the exploration phase (Phase I), the agent performs a lazy random walk for a predetermined length T0T_0. The goal of this phase is to collect enough samples to identify the optimal arm a∗a^*, which has the highest mean reward μ(a∗)μ(a^*). We define the minimum sub-optimality gap as Δmin mina≠a∗(μ(a∗)−μ(a)) _ _a≠ a^*(μ(a^*)-μ(a)). In the homogeneous setting, ΨhomER(n,p) ^ER_hom(n,p), the exploration walk is characterized by its expected transition kernel W¯ [Wt] W [W_t]. Because the environment re-samples the graph independently and every potential edge shares the same probability p, all nodes are statistically indistinguishable. This inherent symmetry ensures that W¯ W is a symmetric and doubly stochastic matrix, which implies a uniform stationary distribution π(a)=1/nπ(a)=1/n. We analyze this process using a regeneration argument (Appendix A), showing that the walk has a constant probability of resetting its dependence on the past and jumping to a random arm. This “forgetting” property guarantees that the walk covers all n arms efficiently. This symmetry-based approach is not applicable to the heterogeneous case, ΨhetER(n,pij) ^ER_het(n,\p_ij\), where the expected kernel W¯ W is generally not symmetric due to the non-uniform edge probabilities. Instead, our analysis (Appendix B) utilizes a uniform typicality argument. We prove that, with high probability, the structural properties of the realized graph GtG_t at every round are sharply concentrated around their expected values. This concentration ensures that even without global symmetry, the realized walk mixes efficiently across the action space to maintain the uniform coverage required for identification. These two distinct analyses culminate in a unified regret structure. This result accounts for both the exploration cost of the lazy walk and the navigation cost of the policy defined in Section 3. We formalize these findings in the following theorem. Theorem 4.1 (Regret for ER Graphs). Under the FMAB model with i.i.d. ER graph evolution, for any δ∈(0,1)δ∈(0,1), there exist constants ci>0c_i>0 such that for T0≥c1nlog(nT/δ)+c2nlog(n/δ)/Δmin2T_0≥ c_1n (nT/δ)+c_2n (n/δ)/ _ ^2, the regret R(T)R(T) satisfies, with probability ≥1−δ≥ 1-δ: R(T)≤c1nlog(nT/δ)+c2nlog(n/δ)Δmin2⏟Exploration Cost+c3nlog(n/δ)⏟Navigation Cost.R(T)≤ c_1n (nT/δ)+c_2 n (n/δ) _ ^2_Exploration Cost+ c_3n (n/δ)_Navigation Cost. Proof 4.2. (Sketch) The proof (detailed in Appendices A and B) budgets the failure probability δ across three key steps. First, the exploration coverage analysis ensures T0T_0 is sufficient to gather s0 O(log(n/δ)/Δmin2)s_0 O( (n/δ)/ _ ^2) samples from each arm. As mentioned above, the homogeneous case (Appendix A) uses a regeneration argument on the expected kernel W¯ W, while the general heterogeneous case (Appendix B) uses a uniform typicality argument on the realized kernels WtW_t. Both methods show that an exploration time scaling linearly with n is sufficient. Second, since the number of samples for every arm are atleast s0s_0, the identification step is a standard application of Hoeffding’s inequality and a union bound (Lemma A.12), guaranteeing a∗a^* is correctly identified with high probability. Third, the navigation cost TnavT_nav (the c3nlog(n/δ)c_3n (n/δ) term) bounds the time to reach a∗a^* using the lazy random walk policy from Section 3. This “mixing route” (Lemma B.10) bounds the time it takes for the walk to mix across the graph and hit the target a∗a^*, which is O(nlog(n/δ))O(n (n/δ)) and succeeds as long as the expected graph is connected. Remark 4.3 (General Analysis and the Homogeneous Case). The clean O(n)O(n) scaling in Theorem 4.1 is an asymptotic result of the analysis for the heterogenous ER case (Appendix B), where the exploration cost scales with the “effective graph size” neffn_eff. For homogeneous graphs, neffn_eff specializes to Θ(n) (n) (Remark B.16), recovering the linear dependence on the number of arms. 4.2 Regret for FMAB with Edge-Markovian Graphs We next analyze the algorithm under Edge-Markovian evolution, where the graph GtG_t evolves from its preceding configuration Gt−1G_t-1. This setting introduces a fundamental analytical challenge: the agent’s walk and the environment’s evolution are coupled stochastic processes. Because the graph evolves as the learner moves, the target stationary distribution πt _t becomes a moving target. The “Two Speeds” Challenge. Our analysis (detailed in Appendix C) reveals that successful learning is possible only if the learner’s walk mixes faster than the graph’s structure drifts. We characterize this requirement through two competing quantities: the (i) walk speed γt _t, which admits a uniform lower bound γ0=Ω(1) _0= (1) under typicality (Lemma C.15), and the (i) drift speed εmax _ (Lemma C.20), which quantifies the maximum per-step variation in the stationary law πt _t. To ensure the agent can visit all n arms before the topology re-wires, the graph must be sufficiently sticky. This intuition is formalized by our stickiness condition (Corollary C.28), which reveals that the edge disappearance rate must scale with the graph size such that β≤O(1/n)β≤ O(1/n). Burn-in and Exploration Phases. This analysis introduces two distinct requirements for the exploration phase of our algorithm. First, the analysis requires the graph process to be in its statistically stationary state (the homogeneous ER model ΨhomER(n,p∞) ^ER_ (n,p_∞) where p∞=α/(α+β)p_∞=α/(α+β)). This requires an initial burn-in period of Tburn=O(log(nT/δ)/(α+β))T_burn=O( (nT/δ)/(α+β)) steps (Lemma C.6). Second, after burn-in, the learner must continue exploring for an additional sample-gathering period, TexpT_exp, to collect sufficient samples (Theorem C.29). Therefore, the two-phase algorithm from Section 3 is adapted for this setting: the total exploration phase length T0T_0 must cover both periods, i.e., T0≥Tburn+TexpT_0≥ T_burn+T_exp. The regret bound in Theorem 4.4 reflects this structure, with the total regret being the sum of costs from these distinct phases. Theorem 4.4 (Regret for Edge-Markovian Graphs). Under the typicality (Lemma C.8) and stickiness (β≤O(1/n)β≤ O(1/n)) conditions, for any δ∈(0,1)δ∈(0,1), there exist constants ci>0c_i>0 such that the two-phase algorithm with total exploration duration T0=Tburn+TexpT_0=T_burn+T_exp satisfies, with probability at least 1−δ1-δ: R(T)≤c0log(nT/δ)α+β⏟Tburn (Burn-in)+c1nlog(nT/δ)+c2nlog(n/δ)Δmin2⏟Texp (Exploration)+c3nlog(n/δ)⏟Tnav (Navigation).R(T)≤ c_0 (nT/δ)α+β_T_burn (Burn-in)+ c_1n (nT/δ)+c_2 n (n/δ) _ ^2_T_exp (Exploration)+ c_3n (n/δ)_T_nav (Navigation). Proof 4.5. (Sketch) The total regret (Theorem C.33) is the sum of the regret from the three distinct phases of the agent’s timeline: burn-in, exploration, and navigation. First, the agent incurs regret for TburnT_burn steps while the graph process mixes to its stationary measure (Lemma C.6). Second, the agent incurs regret during the TexpT_exp steps required for sample gathering. The stickiness condition is crucial here. It ensures the graph’s drift εmax _ is slow enough relative to the walk’s mixing speed γ0 _0 to guarantee a positive effective visitation probability πeff π0−2εmax/γ0=Ω(1/n) _eff _0-2 _ / _0= (1/n) (Corollary C.28). This positive rate, combined with a martingale concentration bound (Lemma C.26), ensures TexpT_exp is sufficient to gather s0 O(log(n/δ)/Δmin2)s_0 O( (n/δ)/ _ ^2) samples for correct identification. Third, the navigation cost TnavT_nav (the c3c_3 term) bounds the time to reach a∗a^* using the lazy random walk policy. On the typical graph, the walk has a constant gap γ0 _0 and πt(a∗)=Ω(1/n) _t(a^*)= (1/n). The “mixing route” analysis (Lemma C.31) shows the total time to hit a∗a^* is bounded by O(nlog(n/δ))O(n (n/δ)). 4.3 Expected Regret for FMAB Our high-probability bounds in Theorems 4.1 and 4.4 lead to a unified result for the expected regret. By converting the high-probability bound to an expectation, we obtain a clean asymptotic guarantee that is independent of the specific graph parameters. Corollary 4.6 (Expected Regret Bound). Under the assumptions of Theorem 4.1 (for i.i.d. ER) or Theorem 4.4 (for edge-Markovian), the expected cumulative regret [R(T)]E [R(T) ] of the two-phase algorithm is bounded by: [R(T)]=O(nlog(nT)Δmin2).E [R(T) ]=O ( n (nT) _ ^2 ). Proof 4.7. (Sketch) We use the law of total expectation: [R(T)]=[R(T)|ℰsuccess](1−δ)+[R(T)|ℰfail]δE [R(T) ]=E [R(T)|E_success ](1-δ)+E [R(T)|E_fail ]δ. The regret on the failure event ℰfailE_fail is at most T. A standard technique in regret analysis is to set the failure probability δ=1/Tδ=1/T. This choice optimally balances the regret on the success event (which grows with log(1/δ)=log(T) (1/δ)= (T)) against the maximum possible regret T incurred on the failure event. With this setting, the regret contribution from the failure event is bounded by [R(T)|ℰfail]δ≤T⋅(1/T)=1E [R(T)|E_fail ]δ≤ T·(1/T)=1. The regret on the success event is bounded by the high-probability costs from our theorems. When δ=1/Tδ=1/T, all mixing, navigation, and burn-in costs (which scale as O(nlog(nT))O(n (nT)) or O(log(nT)/(α+β))O( (nT)/(α+β))) become asymptotically smaller than the identification cost component of T0T_0. The final bound is therefore dominated by this identification cost, which is O(nlog(nT)/Δmin2)O(n (nT)/ _ ^2) (see Corollaries A.18 and C.35). Remark 4.8 (Near-Optimality of Exploration). The expected regret is dominated by the identification cost, as the additive terms for burn-in and navigation are lower-order. For any Δmin∈(0,1] _ ∈(0,1], the total regret simplifies to: [R(T)]≤O(nlog(nT)Δmin2)+O(nlog(nT))=O(nlog(nT)Δmin2).E[R(T)]≤ O ( n (nT) _ ^2 )+O(n (nT))=O ( n (nT) _ ^2 ). This performance matches the fundamental limits of the problem class. In Appendix D, we establish an information-theoretic lower bound (Theorem D.10) showing that for equal-gap instances, the expected identification time TID(δ)T_ID(δ) must satisfy: [TID(δ)]≥Ω((n−1)kl(1−δ,δ)Δmin2).E[T_ID(δ)]≥ ( (n-1)kl(1-δ,δ) _ ^2 ). By setting δ=1/Tδ=1/T, we recover a fundamental hardness of Ω(nlog(T)/Δmin2) (n (T)/ _ ^2). Thus, our two-phase approach achieves a near-optimal exploration cost, matching the lower bound up to logarithmic factors. Furthermore, the Ω(n) (n) worst-case traversal time (Lemma D.7) is fully subsumed by this statistical limit and does not represent an additional bottleneck. This result brings the analysis full circle. While our high-probability analysis necessarily depends on the internal graph parameters used to model the availability constraints, the final expected regret depends only on the problem’s minimal parameters: the number of arms n, the time T, and the reward gap Δmin _ . 5 Numerical Simulations We validate our theoretical results through controlled experiments and a simulated robotic deployment scenario. Theoretical Validation. We conduct two sets of experiments to verify our regret and navigation cost bounds. First, we simulate both i.i.d. ER and Edge-Markovian models with T=10,000T=10,000 and p=0.5p=0.5 for graphs of size n∈10,50,100n∈\10,50,100\. By scaling T0T_0 with n and Δmin _ as theoretically prescribed, Figures 3(a) and (b) show the average regret R(t)/tR(t)/t converging toward zero, empirically confirming our sublinear guarantees. Second, we isolate the Phase I navigation cost in Figure 3(c) by fixing T0=5,000T_0=5,000 to decouple movement from identification. Plotting navigation time TnavT_nav against sparsity p for the i.i.d. ER model reveals a clear monotonic trend where median values rise from ≈21≈ 21 at p=0.8p=0.8 to ≈120≈ 120 at p=0.01p=0.01. These results validate the O(1/p)O(1/p) navigation cost component of our regret bound. (a) (b) (c) Figure 3: (a) Average cumulative regret R(t)/tR(t)/t over time for i.i.d ER case. The main plot and the inset (showing the initial t≤200t≤ 200 rounds) demonstrate the algorithm’s rapid convergence. (b) Same plot for the Edge-Markovian Case. (c) Box plot for the navigation cost for ER case with respect to the sparsity. 5.1 Application: Disaster Response Scenario The goal is to locate and repeatedly assess high-utility candidate locations that offer strong and reliable signal coverage. These locations are unknown, their pathways are unstable, and they must be discovered through repeated interaction with the environment. The vehicle operates without centralized coordination, relying only on local sensing and movement. Repeated visitation is essential for building a reliable estimate of signal quality and stability before committing to a final deployment location. The physical region spans five square kilometers and is discretized into n=500n=500 candidate locations (e.g., street intersections or clearings). This discretization is an approximate representation of potential deployment sites in an urban map. At any given time-stamp t, the discretized sites (or locations) defines the node set A of a random graph GtG_t, where the navigable streets between adjacent locations correspond to the edges EtE_t. These connections evolve stochastically over time due to debris, structural damage, or diverted traffic. Each location a∈Aa∈ A has an unknown reward μ(a)∈[0,1]μ(a)∈[0,1], representing the quality and stability of communication coverage the site could provide. When the vehicle visits a location ata_t, it takes a measurement and receives a binary reward rt(at)∼Bernoulli(μ(at))r_t(a_t) (μ(a_t)) (e.g., ‘signal strength beyond a threshold’ or not), with no feedback from neighboring zones. The environment (i.e., pathway access) evolves independently of the vehicle’s actions. The reward structure is sparse and clustered. A single location is designated as the hotspot with μ(a∗)=0.95μ(a^*)=0.95 (i.e., a location with the best coverage), ten others have moderate rewards drawn from [0.45,0.65][0.45,0.65] (i.e., acceptable but partially obstructed sites), and the remaining 489 lie in [0.1,0.4][0.1,0.4] (i.e., in low-lying areas or “urban canyons”). These values reflect deployment scenarios, where only a few locations are suitable for a high-bandwidth relay, while most are non-viable. The vehicle runs the natural lazy walk (Section 3), fully embedded in its onboard control stack. A discretized map, node structure, and initial connectivity are preloaded before deployment. During operation, the vehicle localizes itself using GPS/LIDAR and maps real-time observations, such as blocked streets or accessible pathways, to its current neighborhood in the evolving graph. All decisions are made locally, without access to a global map or external planner. The algorithm runs continuously over the entire duration of a two-week mission (T=80,640T=80,640 rounds). A decision interval of 15 seconds (e.g., the time to move between intersections or take a stable signal measurement) allowing for adaptive, long-term learning and prioritization of high-value areas in real time. Performance Results. We simulate our two-phase algorithm under the Edge-Markovian graph evolution, with parameters (α=0.01,β=0.03)(α=0.01,β=0.03) set to match the scenario’s stationary density. Since our analysis shows that the algorithm’s long-term convergence is independent of the initial graph G0G_0 (see Lemma C.6), we start with a randomly generated arbitrary graph. (a) (b) Figure 4: (a) Average cumulative regret R(t)/tR(t)/t for the disaster response scenario. (b) Spatial visitation density (log-scale) illustrating the behavioral transition from the exploration and exploitation rounds. Figure 4(a) plots the average regret R(t)/tR(t)/t. The algorithm converges rapidly, demonstrating its ability to efficiently manage the exploration–exploitation trade-off under evolving connectivity and local movement. Figure 4(b) presents spatial visitation heatmaps as separate histograms for each mission phase rather than cumulative sums. This captures the agent’s behavioral evolution: initial sparse wandering (Rounds 1–500) transitions to a diffuse “blue cloud” during Late Exploration (Rounds 501–T0T_0). This uniform coverage confirms the lazy random walk has mixed sufficiently to gather the unbiased samples required to compute a^∗ a^*. Post-identification (t>T0t>T_0), the visitation becomes sparse as the vehicle executes the navigation path and repeatedly pulls a^∗ a^*. The “Ground Truth” panel visually confirms that this committed arm matches the true optimal arm a∗a^*. 6 Conclusion We introduce the Flickering Multi-Armed Bandit (FMAB) framework, a novel sequential decision-making model where action accessibility is strictly constrained by the localized, time-varying neighborhood structure of the action space. We characterize this dynamic accessibility through two canonical graph processes: i.i.d. Erdős–Rényi and Edge-Markovian evolution. Our theoretical analysis demonstrates that a two-phase strategy utilizing lazy random walks is inherently robust to these connectivity constraints and achieves near-optimal exploration performance across diverse regimes. Future work involves developing adaptive, anytime algorithms and extending the FMAB framework to non-stationary rewards or multi-agent systems. Ultimately, this work establishes a rigorous foundation for analyzing the fundamental tension between information acquisition and physical mobility in dynamic environments. References Appendix Contents 1 Introduction 2 Models and Problem Formulation 3 A Phase-Based Learning Algorithm 4 Performance Guarantees 4.1 Regret for FMAB with i.i.d. Erdős–Rényi Graphs 4.2 Regret for FMAB with Edge-Markovian Graphs 4.3 Expected Regret for FMAB 5 Numerical Simulations 5.1 Application: Disaster Response Scenario 6 Conclusion References A Regret Analysis: Homogeneous Erdős–Rényi (ER) Graphs A.1 Model, Notations and Graph Dynamics A.1.1 Problem Setup and i.i.d. Erdős–Rényi Graph Process A.1.2 Uniform-Move Policy: Dynamics and Properties A.2 Algorithm and Analysis Overview A.3 Analysis of the Exploration Phase A.3.1 Coverage Guarantees via Regeneration A.4 Analysis of the Exploitation Phase A.5 Final Regret Bound B Regret Analysis: Heterogeneous i.i.d. ER Graphs B.1 Model, Analytical Challenge, and Population Profile B.2 Uniform Guarantees for Realized Kernels B.3 Regret Analysis C Regret Analysis: Edge-Markovian Graphs C.1 Model, Notation and Graph Dynamics C.1.1 Problem Setup and Edge-Markovian Process C.1.2 Lazy Walk Dynamics and Properties C.2 Burn-in and Typicality of the Edge Process C.2.1 Burn-in for Stationarity C.2.2 Typicality Event: Degree and Edge Count Concentration C.2.3 Definition of the Typical Event C.3 Spectral Gap Analysis of Agent’s Lazy Walk C.4 Kernel Drift and Stationary Distribution Drift C.5 TV Drift Recursion, One-Step Contraction and Its Solution C.6 Uniform Visitation Guarantees C.7 Post-Exploration Cost and Final Regret D Intrinsic Hardness of Identification Under Local Moves D.1 Per-arm fixed-confidence sample requirement D.2 Traversal baseline D.3 Identification-time lower bound and consequences Appendix A Regret Analysis: Homogeneous Erdős–Rényi (ER) Graphs A.1 Model, Notations and Graph Dynamics A.1.1 Problem Setup and i.i.d. Erdős–Rényi Graph Process We begin by specializing the problem formulation from Section 2 to the i.i.d. Erdős–Rényi (ER) environment. This section establishes the core notation for this model and formalizes its basic probabilistic properties, which serve as a foundation for the subsequent analysis. i.i.d. Erdős–Rényi Graph Process. In this model, the environment’s availability structure is encoded by a sequence of graphs Gtt=1T\G_t\_t=1^T. At the beginning of each round t, a new undirected graph Gt=(A,Et)G_t=(A,E_t) is drawn independently from the homogenous ER distribution Ψ0ER(n,p) ^ER_0(n,p), independent of all past graphs and actions. The learner, residing at the arm at−1a_t-1 chosen in the previous round, observes the set of available arms Lt(at−1)L_t(a_t-1). This set is defined by the local neighborhood in the newly drawn graph GtG_t: Lt(at−1) at−1∪j∈A∖at−1:at−1,j∈Et.L_t(a_t-1) \\,a_t-1\,\∪\\,j∈ A \a_t-1\:\a_t-1,j\∈ E_t\,\. The learner then selects a new arm at∈Lt(at−1)a_t∈ L_t(a_t-1) and receives a reward rt(at)∼(at)r_t(a_t) (a_t). For any arm a∈Aa∈ A, its degree in GtG_t is a random variable dt(a)∼Bin(n−1,p)d_t(a) (n-1,p). The size of the available set from a is thus also a random variable, |Lt(a)|=1+dt(a)|L_t(a)|=1+d_t(a), whose distribution is 1+Bin(n−1,p)1+Bin(n-1,p) and whose expected size is [|Lt(a)|]=1+(n−1)pE[|L_t(a)|]=1+(n-1)p. Because GtG_t is drawn independently at each step, this information is independent of the past history ℱt−1F_t-1. The next lemma formalizes the probability that any specific arm j becomes available to the learner, a property that holds uniformly over all (possibly adaptive) learning strategies. Lemma A.1 (ER Availability). Fix any arm j∈Aj∈ A. For every round t≥1t≥ 1 and any history ℱt−1F_t-1 up to time t−1t-1, the conditional probability that j is available at round t (given the learner is at at−1a_t-1) satisfies ℙ(j∈Lt(at−1)|ℱt−1)=at−1=j+p 1at−1≠j.P\! (j∈ L_t(a_t-1)\, |\,F_t-1 )=1\a_t-1=j\+p\,1\a_t-1≠ j\. Consequently, the expected number of times j is available over T rounds is bounded below: [∑t=1Tj∈Lt(at−1)]≥pTfor all T≥1.E [ _t=1^T1\j∈ L_t(a_t-1)\ ]≥ pT all T≥ 1. Proof A.2. Fix any arm j∈Aj∈ A and round t≥1t≥ 1. We seek to compute the conditional probability ℙ(j∈Lt(at−1)∣ℱt−1)P(j∈ L_t(a_t-1) _t-1). Conditioned on ℱt−1F_t-1, the learner’s position at−1a_t-1 is a fixed and known arm. We analyze this probability by cases based on the learner’s position at−1a_t-1: • Case 1: at−1=ja_t-1=j. By the definition Lt(j) j∪…L_t(j) \j\∪\…\, the learner can always choose to stay at their current arm. Thus, j∈Lt(j)j∈ L_t(j) deterministically, and ℙ(j∈Lt(at−1)∣ℱt−1)=1P(j∈ L_t(a_t-1) _t-1)=1. • Case 2: at−1≠ja_t-1≠ j. In this case, the arm j is available, j∈Lt(at−1)j∈ L_t(a_t-1), if and only if the edge at−1,j\a_t-1,j\ is present in the graph GtG_t. Since GtG_t is drawn independently from G(n,p)G(n,p) and is independent of ℱt−1F_t-1, this event occurs with probability p. Combining these two mutually exclusive cases yields the first statement in the lemma: ℙ(j∈Lt(at−1)∣ℱt−1)=at−1=j⋅1+at−1≠j⋅p.P(j∈ L_t(a_t-1) _t-1)=1\a_t-1=j\· 1+1\a_t-1≠ j\· p. For the second statement, we apply the law of total expectation to the sum: [∑t=1Tj∈Lt(at−1)] [ _t=1^T1\j∈ L_t(a_t-1)\ ] =∑t=1T[[j∈Lt(at−1)∣ℱt−1]] = _t=1^TE [E [1\j∈ L_t(a_t-1)\ _t-1 ] ] =∑t=1T[ℙ(j∈Lt(at−1)∣ℱt−1)]. = _t=1^TE [P(j∈ L_t(a_t-1) _t-1) ]. From the first part, the inner conditional probability is a random variable that always takes a value in 1,p\1,p\. Since p∈(0,1)p∈(0,1), this value is always greater than or equal to p. Therefore: [ℙ(j∈Lt(at−1)∣ℱt−1)]≥[p]=p.E [P(j∈ L_t(a_t-1) _t-1) ] [p]=p. Summing this over T rounds gives the claimed bound: ∑t=1Tp=pT _t=1^Tp=pT. Finally, for the last part of the lemma, the degree dt(a)d_t(a) for any arm a is the sum of n−1n-1 independent Bernoulli(p)Bernoulli(p) trials (one for each other arm). Thus, dt(a)∼Bin(n−1,p)d_t(a) (n-1,p), and the available set size is |Lt(a)|=1+dt(a)|L_t(a)|=1+d_t(a). As GtG_t is independent of ℱt−1F_t-1, so are dt(a)d_t(a) and |Lt(a)||L_t(a)|. This completes the proof. The preceding lemma’s i.i.d. availability property directly implies a simple bound on the waiting time to access a specific arm from a fixed position. This quantity will be critical for bounding the cost of navigating to the optimal arm after identification. Corollary A.3 (Waiting Time to Availability). Fix two distinct arms a,j∈Aa,j∈ A. Suppose the learner adopts a “wait-at-a” strategy, holding its position at arm a until arm j appears in the available set Lt(a)L_t(a). The waiting time τa→j _a→ j until j is first available is a geometric random variable with success parameter p, satisfying [τa→j]=1/pE[ _a→ j]=1/p. Proof A.4. Fix distinct arms a,j∈Aa,j∈ A. Under the “wait-at-a” strategy, the learner’s position is fixed at at−1=a_t-1=a for all rounds t prior to the move. By Lemma A.1, since a≠ja≠ j, the event j∈Lt(a)j∈ L_t(a) occurs at each round t with probability p. Because the graphs GtG_t are drawn i.i.d. in each round, these availability events are independent Bernoulli(p)Bernoulli(p) trials across t. The waiting time τa→j _a→ j is therefore the time of the first success in this sequence, which is, by definition, a geometric random variable with parameter p. Its expectation is [τa→j]=1/pE[ _a→ j]=1/p. A.1.2 Uniform-Move Policy: Dynamics and Properties As part of the algorithm design (see Sections 3 and 4), the learner’s movement during the exploration phase is modeled as a uniform-move policy. At each exploration round t, given the learner is at at−1a_t-1, a new graph Gt∼Ψ0ER(n,p)G_t ^ER_0(n,p) is revealed, and the learner selects the next arm ata_t uniformly at random from the available set Lt(at−1)L_t(a_t-1). We now analyze the properties of this uniform-move process, as this analysis is central to quantifying the rate at which the learner visits all arms during exploration. Because the graph GtG_t is drawn i.i.d. at each step, the transition probability ℙ(at=j∣at−1=a)P(a_t=j a_t-1=a) depends only on a and j, not on the time t. The learner’s location sequence (at)t≥0(a_t)_t≥ 0 under this policy is therefore a time-homogeneous Markov chain. This stands in contrast to the time-inhomogeneous chain induced by the temporally correlated Markovian model. We denote the transition matrix of this chain by W and summarize its properties in the following theorem. Theorem A.5 (Properties of the Uniform-Move Kernel). Consider the time-homogeneous Markov chain on A induced by the uniform-move policy, where at each round t, the environment samples Gt∼Ψ0ER(n,p)G_t ^ER_0(n,p) and the learner transitions from at−1a_t-1 to ata_t by sampling uniformly from Lt(at−1)L_t(a_t-1). Let W be its transition matrix. The chain and its properties are as follows: (i) Transition Probabilities: The random-walk matrix W is symmetric with entries W(a,a)=[11+dt(a)]=1−(1−p)npandW(a,j)=np−1+(1−p)np(n−1)for a≠j,W(a,a)=E\! [ 11+d_t(a) ]= 1-(1-p)^nnp W(a,j)= np-1+(1-p)^nnp(n-1) a≠ j, where the expectation is over dt(a)∼Bin(n−1,p)d_t(a) (n-1,p). (i) Ergodicity: The chain is irreducible and aperiodic. (i) Stationarity: The chain is reversible with respect to the uniform distribution π(a)=1/nπ(a)=1/n, which is its unique stationary distribution. (iv) Spectrum and Spectral Gap: The eigenvalues of W are λ1=1 _1=1 (with multiplicity one) and λ2=⋯=λn=1−(1−p)n−p(n−1) _2=·s= _n= 1-(1-p)^n-pp(n-1). The spectral gap is γ 1−λ2>0γ 1- _2>0. (v) Mixing Time: For every ε∈(0,1) ∈(0,1), the total-variation mixing time satisfies tmix(ε)≤log(n/ε)γt_mix( )≤ (n/ )γ. (vi) Uniform Gap Bound: In the dense regime (p∈(0,1)p∈(0,1) fixed) and the standard sparse regime (p=c/np=c/n for c>0c>0), the spectral gap γ is bounded below by a positive absolute constant γ0 Ω(1) _0 (1), and the mixing time is tmix(ε)=O(logn)t_mix( )=O( n). Proof A.6. We analyze the properties of the time-homogeneous Markov chain W in a sequence of steps. Step 1. Transition Probabilities. First, consider the diagonal entries W(a,a)=ℙ(at=a∣at−1=a)W(a,a)=P(a_t=a a_t-1=a). Given at−1=a_t-1=a, the environment draws Gt∼Ψ0ER(n,p)G_t ^ER_0(n,p). The learner is at arm a, and the available set is Lt(a)L_t(a), which has size |Lt(a)|=1+dt(a)|L_t(a)|=1+d_t(a), where dt(a)∼Bin(n−1,p)d_t(a) (n-1,p). The learner stays at a by selecting it uniformly from Lt(a)L_t(a), which occurs with probability 1/|Lt(a)|1/|L_t(a)|. To find W(a,a)W(a,a), we take the expectation over the randomness of GtG_t: W(a,a)=Gt∼Ψ0ER(n,p)[11+dt(a)].W(a,a)=E_G_t ^ER_0(n,p)\! [ 11+d_t(a) ]. Let m=n−1m=n-1 and D∼Bin(m,p)D (m,p). We compute this expectation in closed form using the identity 1k+1(mk)=1m+1(m+1k+1) 1k+1 mk= 1m+1 m+1k+1: [11+D] \! [ 11+D ] =∑k=0m1k+1(mk)pk(1−p)m−k=1m+1∑k=0m(m+1k+1)pk(1−p)m−k = _k=0^m 1k+1 mkp^k(1-p)^m-k= 1m+1 _k=0^m m+1k+1p^k(1-p)^m-k =1(m+1)p∑l=1m+1(m+1l)pl(1−p)(m+1)−l(letting l=k+1) = 1(m+1)p _l=1^m+1 m+1lp^l(1-p)^(m+1)-l (letting l=k+1) =1(m+1)p[∑l=0m+1(m+1l)pl(1−p)(m+1)−l−(1−p)m+1] = 1(m+1)p [ _l=0^m+1 m+1lp^l(1-p)^(m+1)-l-(1-p)^m+1 ] =1−(1−p)m+1(m+1)p=1−(1−p)np. = 1-(1-p)^m+1(m+1)p= 1-(1-p)^nnp. Next, consider the off-diagonal entries W(a,j)=ℙ(at=j∣at−1=a)W(a,j)=P(a_t=j a_t-1=a) for a≠ja≠ j. By the symmetry of the G(n,p)G(n,p) model, this probability is identical for all j≠aj≠ a. Let this common value be C. Since W is a row-stochastic matrix, the row sums must be 1: W(a,a)+∑j≠aW(a,j)=1⟹W(a,a)+(n−1)C=1.W(a,a)+ _j≠ aW(a,j)=1 W(a,a)+(n-1)C=1. Solving for C and substituting the expression for W(a,a)W(a,a) (which we denote D for simplicity in this step) gives: W(a,j)=C=1−W(a,a)n−1=1−1−(1−p)npn−1=np−1+(1−p)np(n−1).W(a,j)=C= 1-W(a,a)n-1= 1- 1-(1-p)^nnpn-1= np-1+(1-p)^nnp(n-1). Step 2. Irreducibility and Aperiodicity. We show that W(a,j)>0W(a,j)>0 for all a,j∈Aa,j∈ A. The diagonal entry W(a,a)=1−(1−p)np>0W(a,a)= 1-(1-p)^nnp>0 since p∈(0,1)p∈(0,1). For the off-diagonal entry W(a,j)W(a,j) (where a≠ja≠ j), we analyze the numerator f(p)=np−1+(1−p)nf(p)=np-1+(1-p)^n for p∈(0,1]p∈(0,1]. Note f(0)=0f(0)=0. The derivative is f′(p)=n−n(1−p)n−1=n(1−(1−p)n−1).f (p)=n-n(1-p)^n-1=n (1-(1-p)^n-1 ). Since n≥2n≥ 2 and p∈(0,1)p∈(0,1), we have 0<(1−p)n−1<10<(1-p)^n-1<1, which implies f′(p)>0f (p)>0. Thus, f(p)f(p) is strictly increasing on [0,1][0,1] from f(0)=0f(0)=0, and f(p)>0f(p)>0 for all p∈(0,1]p∈(0,1]. This proves W(a,j)>0W(a,j)>0 for all a≠ja≠ j. Since all states have positive self-loops (W(a,a)>0W(a,a)>0), the chain is aperiodic. Since all off-diagonal entries are positive (W(a,j)>0W(a,j)>0), the chain is irreducible (and in fact, fully connected). Step 3. Stationarity and Reversibility. From the formulas derived in Step 1, we observe that W(a,a)=W(j,j)W(a,a)=W(j,j) and W(a,j)=W(j,a)W(a,j)=W(j,a) for all a,j∈Aa,j∈ A. The transition matrix W is therefore symmetric (W=WTW=W^T). A symmetric, row-stochastic matrix is necessarily doubly stochastic. This implies that the uniform distribution π(a)=1/nπ(a)=1/n for all a∈Aa∈ A is the unique stationary distribution, since πW=π W=π is satisfied. Furthermore, the chain is reversible with respect to π. We verify the detailed balance equations: π(a)W(a,j)=1nW(a,j)=1nW(j,a)=π(j)W(j,a),π(a)W(a,j)= 1nW(a,j)= 1nW(j,a)=π(j)W(j,a), which holds precisely because W is symmetric. Step 4. Spectrum and Spectral Gap. The transition matrix W has the form W=CJ+(D−C)IW=CJ+(D-C)I, where D=W(a,a)D=W(a,a), C=W(a,j)C=W(a,j) (a≠ja≠ j), I is the identity matrix, and J is the all-ones matrix. The matrix J has a well-known spectrum: one eigenvalue equal to n (for the all-ones eigenvector) and n−1n-1 eigenvalues equal to 0. The eigenvalues of W are thus: • For the all-ones eigenvector: λ1=C⋅n+(D−C)⋅1=1 _1=C· n+(D-C)· 1=1. This corresponds to the stationary distribution. • For the n−1n-1 other eigenvectors (which are orthogonal to the all-ones vector): λk=C⋅0+(D−C)⋅1=D−C _k=C· 0+(D-C)· 1=D-C for k=2,…,nk=2,…,n. The second-largest eigenvalue (in magnitude) is λ2=D−C _2=D-C. We compute this value: λ2=D−C=1−(1−p)np−np−1+(1−p)np(n−1)=(n−1)(1−(1−p)n)−(np−1+(1−p)n)np(n−1). _2=D-C= 1-(1-p)^nnp- np-1+(1-p)^nnp(n-1)= (n-1)(1-(1-p)^n)-(np-1+(1-p)^n)np(n-1). A simpler form is λ2=1−(1−p)n−p(n−1) _2= 1-(1-p)^n-pp(n-1). Since 0<λ2<10< _2<1 for p∈(0,1)p∈(0,1) and n≥2n≥ 2, the spectral gap is γ 1−λ2>0γ 1- _2>0. Step 5. Mixing Time Bound. Because W is reversible with respect to π (Step 3), it is self-adjoint in the L2(π)L_2(π) norm. For any initial distribution ν, the L2(π)L_2(π)-norm of the deviation from stationarity contracts by λ2 _2 at each step. This leads to the standard bound relating total variation (TV) distance to the spectral gap γ=1−λ2γ=1- _2: ‖νWt−π‖TV≤12nλ2t.\|ν W^t-π\|_TV≤ 12 n\, _2^t. To ensure ‖νWt−π‖TV≤ε\|ν W^t-π\|_TV≤ , it suffices to choose t such that t≥log(n/(2ε))−logλ2t≥ ( n/(2 ))- _2. Using the inequality −log(1−γ)≥γ- (1-γ)≥γ, we get the final bound: tmix(ε)≤log(n/ε)−log(1−γ)≤log(n/ε)γ.t_mix( )≤ (n/ )- (1-γ)≤ (n/ )γ. Step 6. Asymptotics and Uniform Gap Bound. We analyze the gap γ in two limiting regimes as n→∞n→∞: • Dense regime (p∈(0,1)p∈(0,1) fixed): As n→∞n→∞, (1−p)n→0(1-p)^n→ 0. The second eigenvalue is λ2=1−(1−p)n−p(n−1)→0 _2= 1-(1-p)^n-pp(n-1)→ 0. Therefore, the spectral gap γ=1−λ2→1γ=1- _2→ 1. • Sparse regime (p=c/np=c/n for c>0c>0 fixed): As n→∞n→∞, (1−p)n=(1−c/n)n→e−c(1-p)^n=(1-c/n)^n→ e^-c. The numerator of λ2 _2 approaches 1−e−c−c/n→1−e−c1-e^-c-c/n→ 1-e^-c, while the denominator p(n−1)=(c/n)(n−1)→cp(n-1)=(c/n)(n-1)→ c. Thus, λ2→1−e−c _2→ 1-e^-cc. The limiting spectral gap is γ→1−1−e−c=c−1+e−cγ→ 1- 1-e^-cc= c-1+e^-cc, which is strictly positive for c>0c>0. In both standard regimes (fixed p or p=c/np=c/n), the spectral gap γ is bounded below by a positive absolute constant, γ0 Ω(1) _0 (1). This allows γ to be treated as a constant in the final regret analysis, where factors of 1/γ1/γ can be absorbed into the CiC_i constants. Remark A.7 (Implications of the Uniform-Move Kernel). Theorem A.5 provides a crucial guarantee for the analysis of the i.i.d. ER environment. It shows that the simple uniform-move policy induces an exploration walk that mixes in O(logn)O( n) time, independent of the edge probability p (so long as p is not o(1/n)o(1/n)). This rapid mixing ensures that the agent can quickly achieve uniform coverage of all arms, forming the basis of our sample complexity bounds for the exploration phase. A.2 Algorithm and Analysis Overview We now formally define the two-phase algorithm analyzed for the i.i.d. ER environment. The algorithm operates in an exploration phase, followed by an exploitation phase. The analysis of this algorithm relies on the properties of the uniform-move kernel W established in Theorem A.5. The Algorithm. The algorithm proceeds in two distinct phases: • Phase I: Exploration. For a predetermined exploration length of TexpT_ rounds (t=1,…,Texpt=1,…,T_ ), the learner follows the Uniform-Move Policy (see Theorem A.5). At each round t, the learner, residing at at−1a_t-1, observes the newly drawn graph Gt∼Ψ0ER(n,p)G_t ^ER_0(n,p) and selects its next action ata_t uniformly at random from the available set Lt(at−1)L_t(a_t-1). During this phase, the learner updates the running empirical mean, μ^t(a) μ_t(a), for each arm a it plays. Let ϕTexp(a) ∑t=1Texpat=a _T_ (a) _t=1^T_ 1\a_t=a\ be the total visitation count for arm a by the end of the phase. The final, frozen empirical mean used for exploitation is μ^(a) μ^Texp(a) μ(a) μ_T_ (a), which is computed based on these ϕTexp(a) _T_ (a) samples. • Phase I: Exploitation. For all subsequent rounds t>Texpt>T_ , the learner follows a greedy policy with respect to the frozen estimates μ^(a) μ(a) computed during exploration. At each round t, the learner, residing at at−1a_t-1, observes the new graph Gt∼Ψ0ER(n,p)G_t ^ER_0(n,p) and selects the arm with the highest empirical mean from the available set: at∈argmaxj∈Lt(at−1)μ^(j).a_t∈ _j∈ L_t(a_t-1) μ(j). We note that once the learner reaches the empirically best arm a∗a^* (assuming successful identification), it will remain there, as a∗a^* is always available from itself (a∗∈Lt(a∗)a^*∈ L_t(a^*)). Analysis Roadmap and Probabilistic Framework. Our objective is to derive a high-probability, instance-dependent bound on the cumulative regret, R(T)R(T). The analysis relies on bounding the cost of each phase separately. The total regret is bounded by the sum of the regret from the exploration phase (which is at most TexpT_ ) and the regret from the exploitation phase. The exploitation regret is dominated by the number of steps TnavT_nav required to navigate to and stay at the optimal arm a∗a^*. Our final bound will hold with probability at least 1−δ1-δ, for a total failure budget δ∈(0,1)δ∈(0,1). We explicitly budget this failure probability across the three key probabilistic steps of the analysis: (i) Exploration Coverage: Bounding the time TexpT_ required to ensure ϕTexp(a)≥s0 _T_ (a)≥ s_0 (a sufficient sample count) for all arms a∈Aa∈ A. We budget a failure probability of δcov=δ/3 _cov=δ/3. (i) Identification: Ensuring that the empirical means μ^(a) μ(a) correctly identify the optimal arm a∗a^* given the coverage event. We budget δid=δ/3 _id=δ/3. (i) Navigation: Bounding the navigation time TnavT_nav during the exploitation phase, conditional on successful identification. We budget δnav=δ/3 _nav=δ/3. By a union bound, the total failure probability of our analysis is at most δcov+δid+δnav=δ _cov+ _id+ _nav=δ. A.3 Analysis of the Exploration Phase We now analyze the exploration phase defined in Section A.2. The goal is to determine a sufficient exploration time TexpT_ to ensure the learner collects enough samples from every arm for a high-probability guarantee of correct identification. A.3.1 Coverage Guarantees via Regeneration The first step is to find a TexpT_ that guarantees every arm a∈Aa∈ A is visited a sufficient number of times, ϕTexp(a)≥s0 _T_ (a)≥ s_0. Our analysis relies on the regenerative properties of the uniform-move kernel W. From Theorem A.5, we know W is a time-homogeneous, reversible, and irreducible Markov chain with a uniform stationary distribution π(a)=1/nπ(a)=1/n and a positive spectral gap γ=Ω(1)γ= (1), which we treat as an absolute constant. This kernel admits a global minorization, which is a key tool for proving coverage. Lemma A.8 (Doeblin Minorization). Let W be the uniform-move transition kernel from Theorem A.5, and let π be its uniform stationary distribution. For all a∈Aa∈ A and all measurable B⊆AB A: ℙ(at∈B∣at−1=a)=W(a,B)≥απ(B),P(a_t∈ B a_t-1=a)=W(a,B)≥α\,π(B), where the minorization constant α is exactly the spectral gap: α=n⋅W(a,j)(a≠j)=np−1+(1−p)np(n−1)=γ.α=n· W(a,j) (a≠ j) = np-1+(1-p)^np(n-1)=γ. Proof A.9. Fix a∈Aa∈ A and j∈Aj∈ A. From Theorem A.5, we know the diagonal entry W(a,a)=DW(a,a)=D and the off-diagonal entry W(a,j)=CW(a,j)=C for a≠ja≠ j satisfy D≥C>0D≥ C>0. Therefore, W(a,j)≥CW(a,j)≥ C for all j. Since the stationary distribution π is uniform, π(j)=1/nπ(j)=1/n for all j. We can thus write: W(a,j)≥C=(nC)⋅(1/n)=(nC)π(j).W(a,j)≥ C=(nC)·(1/n)=(nC)π(j). Let α nCα nC. Summing over all j∈Bj∈ B gives: W(a,B)=∑j∈BW(a,j)≥∑j∈Bαπ(j)=απ(B).W(a,B)= _j∈ BW(a,j)≥ _j∈ Bαπ(j)=απ(B). To compute α explicitly, we substitute the expression for C from Theorem A.5: α=nC=n(np−1+(1−p)np(n−1))=np−1+(1−p)np(n−1).α=nC=n ( np-1+(1-p)^nnp(n-1) )= np-1+(1-p)^np(n-1). From Theorem A.5(iv), the spectral gap is γ=1−λ2=1−(D−C)γ=1- _2=1-(D-C). Substituting the expressions for D and C: γ=1−(1−(1−p)np−np−1+(1−p)np(n−1))=⋯=np−1+(1−p)np(n−1).γ=1- ( 1-(1-p)^nnp- np-1+(1-p)^nnp(n-1) )=…= np-1+(1-p)^np(n-1). Thus, α=γα=γ, as claimed. By a standard splitting argument, Lemma A.8 implies a regeneration representation for the exploration kernel: W=γπ+(1−γ)RW= 1π+(1-γ)R, where R is a residual stochastic kernel. This shows that at each step, with probability γ, the next state is drawn afresh from the uniform distribution π, independently of the past. This property allows us to bound the total visitation counts. Lemma A.10 (Exploration Coverage). Fix the total failure probability δ∈(0,1)δ∈(0,1). Let the required sample count per arm be s0 2log(6n/δ)Δmin2.s_0 2 (6n/δ) _ ^2. Let γ=Ω(1)γ= (1) be the spectral gap of the uniform-move kernel W (from Theorem A.5). There exists an absolute constant c>0c>0 such that if the exploration length TexpT_ satisfies Texp≥cnγ(s0+log(nT/δ)),T_ ≥ c\, nγ (s_0+ (nT/δ) ), then with probability at least 1−δ/31-δ/3, the visitation count satisfies ϕTexp(a)≥s0 _T_ (a)≥ s_0 for all arms a∈Aa∈ A. Proof A.11. Let B be the number of regeneration rounds among the first TexpT_ exploration steps. From Lemma A.8, the regeneration indicators are i.i.d. Bernoulli(γ)Bernoulli(γ), so B∼Binomial(Texp,γ)B (T_ ,γ). At each regeneration round, the next state is drawn from π (the uniform distribution), so the number of visits to a fixed arm a∈Aa∈ A contributed by regeneration rounds is Ya∣B∼Binomial(B,1/n)Y_a B (B,1/n). The total visit count is ϕTexp(a)≥Ya _T_ (a)≥ Y_a. We will show that Ya≥s0Y_a≥ s_0 for all a with probability at least 1−δ/31-δ/3. First, we bound the number of regenerations B. For any u∈(0,1)u∈(0,1), a Chernoff bound gives: ℙ(B≤(1−u)γTexp)≤exp(−u22γTexp).P (B≤(1-u)γ T_ )≤ (- u^22\,γ T_ ). Setting u=1/2u=1/2, we have ℙ(B≤γTexp2)≤exp(−γTexp8)P (B≤ γ T_ 2 )≤ (- γ T_ 8 ). Next, we bound YaY_a conditional on B. On the event B≥γTexp2\B≥ γ T_ 2\, the conditional expectation of YaY_a is [Ya∣B]=Bn≥γTexp2nE[Y_a B]= Bn≥ γ T_ 2n. Applying a Chernoff bound to Ya∣BY_a B (for a downward deviation by 1/21/2): ℙ(Ya≤[Ya∣B]2|B)≤ℙ(Ya≤B2n|B)≤exp(−[Ya∣B]8)≤exp(−B8n).P (Y_a≤ E[Y_a B]2\; |\;B ) (Y_a≤ B2n\; |\;B )≤ (- E[Y_a B]8 )≤ (- B8n ). Combining these two deviations via a union bound: ℙ(Ya≤γTexp4n)≤ℙ(B≤γTexp2)+ℙ(Ya≤B2n|B≥γTexp2)≤exp(−γTexp8)+exp(−γTexp8n).P (Y_a≤ γ T_ 4n ) (B≤ γ T_ 2 )+P (Y_a≤ B2n\; |\;B≥ γ T_ 2 )≤ (- γ T_ 8 )+ (- γ T_ 8n ). We need ϕTexp(a)≥s0 _T_ (a)≥ s_0 for all a. It suffices to show ℙ(Ya<s0)≤δ/(3n)P(Y_a<s_0)≤δ/(3n) for a single arm a, as a union bound over n arms will give the desired total failure probability of δ/3δ/3. ℙ(mina∈AϕTexp(a)<s0)≤n⋅ℙ(Ya<s0).P ( _a∈ A _T_ (a)<s_0 )≤ n·P(Y_a<s_0). Let Texp≥cnγ(s0+log(nT/δ))T_ ≥ c nγ(s_0+ (nT/δ)) for a sufficiently large constant c. First, this choice ensures the condition γTexp4n≥c4(s0+log(nT/δ))≥s0 γ T_ 4n≥ c4(s_0+ (nT/δ))≥ s_0 (by choosing c≥4c≥ 4). Second, we bound the failure probability. The second term is dominant: n⋅exp(−γTexp8n)≤n⋅exp(−c(s0+log(nT/δ))8).n· (- γ T_ 8n )≤ n· (- c(s_0+ (nT/δ))8 ). By choosing c large enough (e.g., c≥8c≥ 8), this term is bounded by n⋅(nT/δ)−1=(δ/T)≤δ/6n·(nT/δ)^-1=(δ/T)≤δ/6. The first term is even smaller: n⋅exp(−γTexp8)≤n⋅exp(−cn(s0+log(nT/δ))8),n· (- γ T_ 8 )≤ n· (- cn(s_0+ (nT/δ))8 ), which is ≤δ/6≤δ/6 for large n. Summing these gives ℙ(minaϕ(a)<s0)≤δ/3P( _aφ(a)<s_0)≤δ/3. This completes the proof. Lemma A.12 (Identification). Let s0s_0 be the sample count defined in Lemma A.10. Conditioned on the coverage event ℰcov minaϕTexp(a)≥s0E_cov \ _a _T_ (a)≥ s_0\, the following holds with probability at least 1−δ/31-δ/3: |μ^(a)−μ(a)|<Δmin2for alla∈A, | μ(a)-μ(a) |< _ 2 all\ a∈ A, which implies argmaxaμ^(a)=a∗ _a μ(a)=\a^*\. Proof A.13. We are conditioned on the coverage event ℰcovE_cov, which guarantees that for every arm a∈Aa∈ A, its empirical mean μ^(a) μ(a) is an average of ϕTexp(a)≥s0 _T_ (a)≥ s_0 independent rewards. The rewards are bounded in [0,1][0,1]. We apply Hoeffding’s inequality to bound the probability of a large deviation for a single arm a. We use an error tolerance of ϵ=Δmin/2ε= _ /2: ℙ(|μ^(a)−μ(a)|≥Δmin2|ℰcov) ( | μ(a)-μ(a) |≥ _ 2\; |\;E_cov ) ≤2exp(−2ϵ2ϕTexp(a)) ≤ 2 (-2ε^2 _T_ (a) ) ≤2exp(−2(Δmin2)2s0) ≤ 2 (-2 ( _ 2 )^2s_0 ) =2exp(−Δmin2s02). =2 (- _ ^2s_02 ). We now substitute the definition of s0=2log(6n/δ)Δmin2s_0= 2 (6n/δ) _ ^2 from Lemma A.10: ℙ(|μ^(a)−μ(a)|≥Δmin2|ℰcov) ( | μ(a)-μ(a) |≥ _ 2\; |\;E_cov ) ≤2exp(−Δmin22⋅2log(6n/δ)Δmin2) ≤ 2 (- _ ^22· 2 (6n/δ) _ ^2 ) =2exp(−log(6n/δ)) =2 (- (6n/δ) ) =2(δ6n)=δ3n. =2 ( δ6n )= δ3n. This bounds the failure probability for a single arm. To ensure this holds for all arms simultaneously, we apply a union bound over all n arms in A: ℙ(∃a∈A:|μ^(a)−μ(a)|≥Δmin2|ℰcov) (∃ a∈ A: | μ(a)-μ(a) |≥ _ 2\; |\;E_cov ) ≤∑a∈Aℙ(|μ^(a)−μ(a)|≥Δmin2|ℰcov) ≤ _a∈ AP ( | μ(a)-μ(a) |≥ _ 2\; |\;E_cov ) ≤n⋅(δ3n)=δ3. ≤ n· ( δ3n )= δ3. Therefore, the success event ℰid ∀a∈A,|μ^(a)−μ(a)|<Δmin2E_id \∀ a∈ A, | μ(a)-μ(a) |< _ 2 \ holds with probability at least 1−δ/31-δ/3, as budgeted. Finally, we show this success event implies correct identification of a∗a^*. For any suboptimal arm a≠a∗a≠ a^*, on the event ℰidE_id we have: 1. μ^(a∗)>μ(a∗)−Δmin2 μ(a^*)>μ(a^*)- _ 2 2. μ^(a)<μ(a)+Δmin2 μ(a)<μ(a)+ _ 2 By the definition of the gaps, μ(a∗)−μ(a)=Δ(a)≥Δminμ(a^*)-μ(a)= (a)≥ _ . Rearranging, μ(a∗)−Δmin/2≥μ(a)+Δmin/2μ(a^*)- _ /2≥μ(a)+ _ /2. Combining these inequalities, we have: μ^(a∗)>μ(a∗)−Δmin2≥μ(a)+Δmin2>μ^(a). μ(a^*)>μ(a^*)- _ 2≥μ(a)+ _ 2> μ(a). This shows μ^(a∗)>μ^(a) μ(a^*)> μ(a) for all a≠a∗a≠ a^*, which implies argmaxaμ^(a)=a∗ _a μ(a)=\a^*\. Combining Lemmas A.10 and A.12, and applying a union bound, we conclude that after TexpT_ steps, the algorithm has successfully identified a∗a^* with total probability at least 1−2δ/31-2δ/3. A.4 Analysis of the Exploitation Phase Finally, we analyze the exploitation phase, which begins at t=Texp+1t=T_ +1. The goal is to bound the number of rounds, TnavT_nav, required for the learner to find and ”lock on” to the optimal arm a∗a^*, given that identification was successful. Lemma A.14 (Navigation Cost). Fix the total failure probability δ∈(0,1)δ∈(0,1), and let the budget for this phase be δnav=δ/3 _nav=δ/3. Condition on the identification event from Lemma A.12, ℰid=argmaxaμ^(a)=a∗E_id=\ _a μ(a)=\a^*\\. (i) If the learner is at at−1=a∗a_t-1=a^*, the greedy policy selects at=a∗a_t=a^* deterministically. (i) If at−1≠a∗a_t-1≠ a^*, the optimal arm a∗a^* is available in the next step, a∗∈Lt(at−1)a^*∈ L_t(a_t-1), with probability p. The time τ=mint>Texp:at=a∗τ= \t>T_ :a_t=a^*\ to first hit a∗a^* is stochastically dominated by a Geometric(p) random variable. (i) The total navigation cost, Tnav τ−TexpT_nav τ-T_ , is bounded with high probability: Tnav≤log(3/δ)p,T_nav≤ (3/δ)p, with probability at least 1−δ/31-δ/3 (conditional on ℰidE_id). Proof A.15. We prove each part conditional on the event ℰidE_id that a∗a^* is the unique arm with the highest empirical mean μ μ. (i) Staying at the optimum. If the learner is at at−1=a∗a_t-1=a^*, the available set is Lt(a∗)L_t(a^*). By definition, a∗∈Lt(a∗)a^*∈ L_t(a^*) (the learner can always stay). Since μ^(a∗)>μ^(j) μ(a^*)> μ(j) for all j≠a∗j≠ a^*, the greedy selection argmaxj∈Lt(a∗)μ^(j) _j∈ L_t(a^*) μ(j) will uniquely return a∗a^*. Thus, at=a∗a_t=a^* deterministically. (i) Finding the optimum. If at−1≠a∗a_t-1≠ a^*, the greedy policy will select at=a∗a_t=a^* if and only if a∗a^* is in the available set Lt(at−1)L_t(a_t-1), as it has the highest μ μ of any arm. By Lemma A.1, ℙ(a∗∈Lt(at−1)∣ℱt−1)=pP(a^*∈ L_t(a_t-1) _t-1)=p. Since the graphs GtG_t are drawn i.i.d., each round is an independent Bernoulli(p)Bernoulli(p) trial for a∗a^* to become available, until it is reached. The time to hit a∗a^*, τ, is therefore stochastically dominated by a Geometric(p)Geometric(p) random variable. (i) High-probability bound. We want to bound Tnav=τ−TexpT_nav=τ-T_ . Let τ′∼Geometric(p)τ (p). We need to find k such that ℙ(τ′>k)≤δ/3P(τ >k)≤δ/3. ℙ(τ′>k)=(1−p)k≤e−pk.P(τ >k)=(1-p)^k≤ e^-pk. Setting this failure probability to be at most δ/3δ/3, we solve for k: e−pk≤δ/3⟹−pk≤log(δ/3)⟹pk≥log(3/δ)⟹k≥log(3/δ)p.e^-pk≤δ/3 -pk≤ (δ/3) pk≥ (3/δ) k≥ (3/δ)p. Thus, with probability at least 1−δ/31-δ/3, the navigation phase ends within log(3/δ)p (3/δ)p steps. A.5 Final Regret Bound We now combine the results from the exploration and exploitation analyses to derive the final, high-probability bound on the cumulative regret R(T)R(T). Theorem A.16 ((Full Version) Regret Bound for i.i.d. ER). Fix a total failure probability δ∈(0,1)δ∈(0,1). Let TexpT_ be the exploration length satisfying the condition in Lemma A.10: Texp≥cnγ(2log(6n/δ)Δmin2+log(nT)),T_ ≥ c\, nγ ( 2 (6n/δ) _ ^2+ (nT) ), where γ is the spectral gap from Theorem A.5. Then with probability at least 1−δ1-δ, the cumulative regret R(T)R(T) after T rounds is bounded by: R(T)≤Texp+log(3/δ)p.R(T)≤ T_ + (3/δ)p. Since 1/γ=O(1)1/γ=O(1) by Theorem A.5(vi), the total regret has the asymptotic bound: R(T)=O(nlog(nT)+nlog(n/δ)Δmin2)+O(log(1/δ)p).R(T)=O (n (nT)+ n (n/δ) _ ^2 )+O ( (1/δ)p ). Proof A.17. The proof proceeds by defining a “good” event, ℰgoodE_good, on which the algorithm succeeds, and bounding its failure probability using our δ-budget. Let ℰcovE_cov be the event that minaϕTexp(a)≥s0 _a _T_ (a)≥ s_0, as defined in Lemma A.10. Let ℰidE_id be the event that argmaxaμ^(a)=a∗ _a μ(a)=\a^*\, as defined in Lemma A.12. Let ℰnavE_nav be the event that the navigation time Tnav≤log(3/δ)pT_nav≤ (3/δ)p, as defined in Lemma A.14. The final ”good” event is the intersection ℰgood=ℰcov∩ℰid∩ℰnavE_good=E_cov _id _nav. We bound the probability of its complement, ℰgoodcE_good^c, using a union bound and our probability ledger from Section A.2: ℙ(ℰgoodc) (E_good^c) =ℙ(ℰcovc∪ℰidc∪ℰnavc) =P(E_cov^c _id^c _nav^c) ≤ℙ(ℰcovc)+ℙ(ℰidc∣ℰcov)+ℙ(ℰnavc∣ℰcov∩ℰid) (E_cov^c)+P(E_id^c _cov)+P(E_nav^c _cov _id) ≤δ/3+δ/3+δ/3=δ. ≤δ/3+δ/3+δ/3=δ. Thus, ℰgoodE_good holds with probability at least 1−δ1-δ. We now bound the regret R(T)R(T) conditioned on ℰgoodE_good. The regret is the sum of per-round regrets, ∑t=1T(μ(a∗)−μ(at)) _t=1^T(μ(a^*)-μ(a_t)), which is at most 1 per round. • Exploration Phase (1≤t≤Texp1≤ t≤ T_ ): The agent takes TexpT_ actions. The regret incurred in this phase is at most TexpT_ . • Exploitation Phase (t>Texpt>T_ ): This phase is conditioned on ℰidE_id. – Navigation (Texp<t≤Texp+TnavT_ <t≤ T_ +T_nav): On ℰnavE_nav, this period lasts at most Tnav=log(3/δ)pT_nav= (3/δ)p steps. The regret is at most TnavT_nav. – Post-Navigation (t>Texp+Tnavt>T_ +T_nav): On ℰnavE_nav, the agent has reached a∗a^*. By Lemma A.14(i), the agent deterministically stays at a∗a^* for all subsequent rounds. The per-round regret is μ(a∗)−μ(a∗)=0μ(a^*)-μ(a^*)=0. Summing these costs, the total regret on ℰgoodE_good is bounded by: R(T)≤Texp+Tnav≤Texp+log(3/δ)p.R(T)≤ T_ +T_nav≤ T_ + (3/δ)p. This holds with probability at least 1−δ1-δ. The asymptotic form in the theorem statement follows from substituting the O(⋅)O(·) bound for TexpT_ and noting that 1/γ=O(1)1/γ=O(1). Corollary A.18 (Expected Regret Bound). Under the same conditions as Theorem A.16, by setting the failure probability δ=1/Tδ=1/T, the expected cumulative regret R(T)R(T) is bounded by: [R(T)]≤O(nlog(nT)Δmin2).E[R(T)]≤ O ( n (nT) _ ^2 ). Proof A.19. We use the law of total expectation, decomposing the regret based on the high-probability event ℰgoodE_good from the proof of Theorem A.16, which occurs with probability at least 1−δ1-δ. [R(T)]=[R(T)∣ℰgood]ℙ(ℰgood)+[R(T)∣ℰgoodc]ℙ(ℰgoodc).E[R(T)]=E[R(T) _good]P(E_good)+E[R(T) _good^c]P(E_good^c). We bound the two terms: • On the ”good” event ℰgoodE_good: The per-round regret is at most 1. The total regret consists of the exploration cost (TexpT_ ) and the expected navigation cost. From Lemma A.14(i), the navigation time TnavT_nav is stochastically dominated by a Geometric(p)Geometric(p) random variable, so its expectation is [Tnav]≤1/pE[T_nav]≤ 1/p. Thus, [R(T)∣ℰgood]≤Texp+1/pE[R(T) _good]≤ T_ +1/p. • On the ”failure” event ℰgoodcE_good^c: This event occurs with probability at most δ. The maximum possible regret over T rounds is T (since per-round regret is at most 1). Combining these, we get: [R(T)]≤(Texp+1p)⋅(1)+(T)⋅(δ).E[R(T)]≤ (T_ + 1p )·(1)+(T)·(δ). To obtain a sublinear bound, we set δ=1/Tδ=1/T. This gives: [R(T)]≤Texp+1p+T⋅(1T)=Texp+1p+1.E[R(T)]≤ T_ + 1p+T· ( 1T )=T_ + 1p+1. The asymptotic form for TexpT_ follows by substituting δ=1/Tδ=1/T into the expression from Theorem A.16, noting that log(nT) (nT) and log(n/δ)=log(nT) (n/δ)= (nT) are asymptotically equivalent. Appendix B Regret Analysis: Heterogeneous i.i.d. ER Graphs In this section, we analyze the FMAB problem under the heterogeneous i.i.d. Erdős–Rényi model, ΨhetER(n,pij) ^ER_het(n,\p_ij\). This setting generalizes the homogeneous case from Appendix A. Here, at each round t, a new graph Gt=(A,Et)G_t=(A,E_t) is drawn independently, where each edge (a,j)(a,j) appears with its own unique probability paj∈[0,1]p_aj∈[0,1]. This heterogeneity introduces a significant new analytical challenge. The analysis from Appendix A, which relied on the properties of the expected transition kernel W¯ [Wt] W [W_t], cannot be directly applied. In the homogeneous case, the symmetry of pij=p_ij=p ensures that W¯ W is symmetric and reversible, admitting the simple spectral analysis of Theorem A.5. In the heterogeneous setting, the expected degrees da⋆d_a are non-uniform. This breaks the symmetry of W¯ W, rendering it non-symmetric and non-reversible, and its stationary distribution π is no longer uniform. This invalidates the analytical framework used in Appendix A. Our analysis proceeds by defining the “population-level” (expected) properties of the graph. We show that the sampled graph properties (e.g., degrees) concentrate around these population means. This allows us to derive new, non-uniform bounds for the spectral gap and the stationary distribution, which we then plug into the regret analysis framework established in Appendix A. B.1 Model, Analytical Challenge, and Population Profile Heterogeneous ER Model. The environment is defined by the process ΨhetER(n,P) ^ER_het(n,P). At each round t, a new graph Gt=(A,Et)G_t=(A,E_t) is drawn, where each edge (a,j)(a,j) appears independently with probability pajp_aj, i.i.d. across all t. The algorithm is the same as in Section 3: an exploration phase using the uniform-move policy, followed by a greedy exploitation phase. In our analysis, we do not analyze W¯ W. Instead, we analyze the sequence of realized, time-varying kernels Wt\W_t\. As shown in Lemma C.3, for any realized graph GtG_t, the lazy walk kernel WtW_t is reversible with respect to its own stationary distribution πt(a)∝dt(a)+1 _t(a) d_t(a)+1. Our analysis will show that the key properties of WtW_t (its spectral gap γt _t and stationary distribution πt _t) concentrate around “population” values, which allows for a uniform bound. Population Profile. We define the key “population” (expected) quantities based on the probability matrix P. These serve as the ”center” for our concentration bounds. • Expected Degree: The expected degree for an arm a is da⋆ ∑j≠apajd_a _j≠ ap_aj. • Min/Max Expected Degree: We define the extrema σmin⋆ minada⋆ _ _ad_a and σmax⋆ maxada⋆ _ _ad_a . • Population Volume and Cut: For any subset S⊆AS A, we define its population volume and cut: VolP(S) ∑a∈Sda⋆=∑a∈S∑j≠apaj,ΦP(S) ∑a∈S,j∉Spaj.Vol_P(S) _a∈ Sd_a = _a∈ S _j≠ ap_aj, _P(S) _a∈ S,\,j∉ Sp_aj. • Population Conductance: The population conductance is the minimum conductance over all cuts in the expected graph: φ⋆ min 0<VolP(S)≤VolP(A)/2ΦP(S)VolP(S). _\,0<Vol_P(S) _P(A)/2\; _P(S)Vol_P(S). Analysis Roadmap and Probability Ledger. Our analytical goal is to derive uniform, high-probability bounds for the spectral gap γt _t and the stationary mass πt(a) _t(a) in terms of the population profile. These new, non-uniform bounds (which we will call γhet _het and 1/neff1/n_eff) will then be used in a regret analysis that follows the same logical structure as Appendix A (coverage, identification, navigation). We follow the same probabilistic framework as in Section A.2, with a total failure budget of δ, split across the analysis as laid out in. B.2 Uniform Guarantees for Realized Kernels Our analysis hinges on showing that the key properties of the realized kernel WtW_t (which is reversible) concentrate around the deterministic properties of the population matrix P. The primary tool for this is the concentration of sums of non-identically distributed Bernoulli variables (a Poisson-Binomial sum). Lemma B.1 (Poisson–Binomial Chernoff). Let X=∑k=1mYkX= _k=1^mY_k with independent Yk∼Ber(qk)Y_k (q_k) and μ=[X]=∑k=1mqkμ=E[X]= _k=1^mq_k. For any ε∈(0,1) ∈(0,1), Pr[X≤(1−ε)μ]≤e−ε2μ/2,Pr[X≥(1+ε)μ]≤e−ε2μ/3. \! [X≤(1- )μ ]≤ e^- ^2μ/2, \! [X≥(1+ )μ ]≤ e^- ^2μ/3. We apply this lemma to the degrees dt(a)=∑j≠a(a,j)∈Etd_t(a)= _j≠ a1\(a,j)∈ E_t\ (with mean da⋆d_a ) and to the cut sizes |∂GtS||∂ G_tS| (with mean ΦP(S) _P(S)). By applying a careful union bound over all t≤Tt≤ T, all n nodes, and all S⊆AS A, we obtain the following uniform typicality event. Lemma B.2 (Uniform Typicality: Degrees and Cuts). Fix η∈(0,1/2)η∈(0,1/2) and δ∈(0,1)δ∈(0,1). There exists a universal constant C>0C>0 such that if the minimum expected degree satisfies σmin⋆≥Clog(nT/δ), _ \;≥\;C\, \! (nT/δ ), then with probability at least 1−δ/41-δ/4 (per the ledger in Sec. B.1), the following hold simultaneously for all t≤Tt≤ T and all S⊆AS A: (i) dt(a)∈[(1−η)da⋆,(1+η)da⋆]d_t(a)∈[(1-η)d_a ,(1+η)d_a ] for all a∈Aa∈ A. (i) |∂GtS|≥(1−η)ΦP(S)|∂ G_tS|≥(1-η)\, _P(S). (i) VolGt(S) ∑a∈Sdt(a)≤(1+η)VolP(S)Vol_G_t(S) _a∈ Sd_t(a)≤(1+η)\,Vol_P(S). Proof B.3. The proof proceeds by applying Lemma B.1 to all n node degrees and all 2n2^n possible cuts, and then taking a union bound over all t≤Tt≤ T. 1. Degree Concentration. For any arm a, dt(a)d_t(a) is a Poisson-Binomial random variable with mean da⋆≥σmin⋆d_a ≥ _ . Applying Lemma B.1 and a union bound over all n arms and T time steps: ℙ(∃a,t:dt(a)∉[(1−η)da⋆,(1+η)da⋆])≤∑t=1T∑a∈A2e−η2σmin⋆/3=2nTe−η2σmin⋆/3.P(∃ a,t:d_t(a)∉[(1-η)d_a ,(1+η)d_a ])≤ _t=1^T _a∈ A2e^-η^2 _ /3=2nTe^-η^2 _ /3. 2. Cut and Volume Concentration. We apply the union bound over all S⊆AS A with 1≤|S|≤n/21≤|S|≤ n/2 (the other half follows by symmetry). For a fixed k=|S|k=|S|, there are (nk) nk such sets. For (i), the mean is ΦP(S)≥φ⋆VolP(S)≥φ⋆kσmin⋆ _P(S)≥ Vol_P(S)≥ k _ . For (i), the mean is VolP(S)≥kσmin⋆Vol_P(S)≥ k _ . In both cases, the mean is ≥Ω(kσmin⋆)≥ (k _ ) (assuming φ⋆ is a constant). Using the bound (nk)≤(en/k)k nk≤(en/k)^k, the failure probability for a fixed t is bounded by: ℙ(∃S,t:ℰS,tc) (∃ S,t:E_S,t^c) ≤∑k=1⌊n/2⌋(nk)2exp(−cη2kσmin⋆) ≤ _k=1 n/2 nk2 \! (-c\,η^2\,k\, _ ) ≤∑k=1⌊n/2⌋2exp(klog(en/k)−cη2kσmin⋆) ≤ _k=1 n/2 2 \! (k (en/k)-c\,η^2\,k\, _ ) =∑k=1⌊n/2⌋2exp(−k[cη2σmin⋆−log(en/k)]). = _k=1 n/2 2 \! (-k [c\,η^2\, _ - (en/k) ] ). By choosing σmin⋆≥Clog(nT/δ) _ ≥ C (nT/δ) with C large enough, C≥(cη2)−1log(en)C≥(cη^2)^-1 (en), the term in the exponent is negative and linear in k. The sum is a geometric series bounded by its first term (k=1k=1): ∑k=1⌊n/2⌋2exp(…)≤2exp(−[cη2σmin⋆−log(en)])1−exp(−[cη2σmin⋆−log(en)])≤4e−(cη2σmin⋆−log(en)). _k=1 n/2 2 (…)≤ 2 (-[cη^2 _ - (en)])1- (-[cη^2 _ - (en)])≤ 4e^-(cη^2 _ - (en)). 3. Total Failure Probability. We bound the total failure probability (summing (1) and (2) and multiplying by T): ℙ(ℰc)≤2nTe−η2σmin⋆/3+4Te−(cη2σmin⋆−log(en)).P(E^c)≤ 2nTe^-η^2 _ /3+4Te^-(cη^2 _ - (en)). By choosing C in the condition σmin⋆≥Clog(nT/δ) _ ≥ C (nT/δ) sufficiently large, both terms can be made smaller than δ/8δ/8, bounding the total failure probability by δ/4δ/4. This typicality event is the foundation for our analysis. It allows us to translate the static, population-level conductance φ⋆ into a uniform, high-probability lower bound on the spectral gap γt _t of every realized kernel WtW_t. Theorem B.4 (Profile-Aware Spectral Gap). On the uniform typicality event of Lemma B.2, there exists a universal constant c>0c>0 such that, uniformly for all t≤Tt≤ T, the spectral gap γt _t of the lazy-walk kernel WtW_t satisfies: γt≥c(1−η1+η)2φ⋆ 2(1+1(1−η)σmin⋆)2 γhet. _t\;≥\;c\, ( 1-η1+η )^\!2 ^\,2 (1+ 1(1-η)\, _ )^\!2\; \; _het. Proof B.5. The proof follows the standard Cheeger inequality argument for reversible chains. Step 1: Graph Conductance. First, we bound the conductance of the realized graph GtG_t, hgraph(Gt)h_graph(G_t). By Lemma B.2, for every S⊆AS A and every t: |∂GtS|VolGt(S)≥(1−η)ΦP(S)(1+η)VolP(S). |∂ G_tS|Vol_G_t(S)\ ≥\ (1-η)\, _P(S)(1+η)\,Vol_P(S). Taking the minimum over S (with the appropriate volume constraint) gives hgraph(Gt)≥1−η1+ηφ⋆.h_graph(G_t)≥ 1-η1+η\, . Step 2: Lazy-Walk Conductance. Next, we relate the graph conductance to the conductance of the lazy-walk chain WtW_t. The chain’s conductance Φchain(S) _chain(S) (using πt(a)∝dt(a)+1 _t(a) d_t(a)+1 and Zt=∑k(dt(k)+1)Z_t= _k(d_t(k)+1)) is: Φchain(S)=∑a∈S,j∉Sπt(a)Wt(a,j)∑a∈Sπt(a)=|∂GtS|∑a∈S(dt(a)+1)=|∂GtS|VolGt(S)+|S|. _chain(S)\;=\; _a∈ S,j∉ S _t(a)W_t(a,j) _a∈ S _t(a)\;=\; |∂ G_tS| _a∈ S(d_t(a)+1)\;=\; |∂ G_tS|Vol_G_t(S)+|S|. Using VolGt(S)≥|S|⋅minadt(a)≥|S|⋅(1−η)σmin⋆Vol_G_t(S)≥|S|· _ad_t(a)≥|S|·(1-η) _ (from typicality): Φchain(S)≥|∂GtS|VolGt(S)(1+1minadt(a))≥|∂GtS|VolGt(S)⋅11+1(1−η)σmin⋆. _chain(S)\ ≥\ |∂ G_tS|Vol_G_t(S) (1+ 1 _ad_t(a) )\ ≥\ |∂ G_tS|Vol_G_t(S)· 11+ 1(1-η) _ . Minimizing over S and applying the bound from Step 1 gives: Φchain(Gt)≥1−η1+ηφ⋆⋅11+1(1−η)σmin⋆. _chain(G_t)\ ≥\ 1-η1+η\, · 11+ 1(1-η) _ . Step 3: Cheeger Inequality. Finally, the standard Cheeger inequality for reversible Markov chains (see Appendix A) states γt≥12Φchain(Gt)2 _t≥ 12 _chain(G_t)^2. Plugging in the bound from Step 2 gives the result. Similarly, the typicality lemma provides a uniform lower bound on the stationary mass of any arm a, which is no longer 1/n1/n but is now governed by the ”effective size” of the graph. Lemma B.6 (Stationary Mass Lower Bound and Effective Size). On the uniform typicality event of Lemma B.2, the stationary distribution πt _t of the kernel WtW_t satisfies: πmin mina,tπt(a)≥(1−η)σmin⋆(1+η)∑jdj⋆+n 1neff⋆, _ _a,t _t(a)\;≥\; (1-η)\, _ (1+η) _jd_j +n\; \; 1n_eff , where neff⋆n_eff is the effective size of the graph. We define the clean parameter neff≔∑jdj⋆+nσmin⋆,n_eff\; \; _jd_j +n _ , and note that neff⋆≍neffn_eff n_eff (i.e., they are equivalent up to constants depending on η). Proof B.7. By Lemma B.2, for every t and a, dt(a)+1≥dt(a)≥(1−η)da⋆≥(1−η)σmin⋆d_t(a)+1≥ d_t(a)≥(1-η)d_a ≥(1-η) _ . The normalization factor Zt=∑j(dt(j)+1)=∑jdt(j)+n≤(1+η)∑jdj⋆+nZ_t= _j(d_t(j)+1)= _jd_t(j)+n≤(1+η) _jd_j +n. Thus, πt(a)=dt(a)+1Zt≥(1−η)σmin⋆(1+η)∑jdj⋆+n, _t(a)= d_t(a)+1Z_t\ ≥\ (1-η) _ (1+η) _jd_j +n, which implies the displayed bounds by minimizing over a and t. B.3 Regret Analysis With the uniform, high-probability bounds on the spectral gap (γhet _het) and the stationary mass (πmin≥1/neff⋆ _ ≥ 1/n_eff ) established, we can derive the final regret bound. The analysis first establishes a minimum visitation guarantee for the exploration walk and then computes the required exploration time for identification. Minimum Visitation Guarantee. The core of the analysis is a non-asymptotic bound on the visitation counts, which separates the martingale (variance) component from the mixing (bias) component of the walk. Lemma B.8 (Min-Visitation via Every-Step Contraction). Work on the uniform typicality event (Lemma B.2) and the spectral-gap event (Theorem B.4). Fix the failure budget δcov=δ/4 _cov=δ/4 (per the ledger in Sec. B.1) and set the bias-bounding term b ⌈2γhetlog8nTδ⌉.b\; \; 2 _het\, \! 8nTδ . Let πt _t be the (realized) stationary law on GtG_t. Then, with probability at least 1−δ/41-δ/4, mina∈A∑t=1Texpat=a≥Texpπmin−C1b−C2(Texpπmin+C1b)log4nδ−C3log4nδ, _a∈ A\ _t=1^T_ 1\a_t=a\\ ≥\ T_ \, _ \ -\ C_1\,b\ -\ C_2\, (T_ \, _ +C_1b)\, 4nδ-C_3 4nδ\ , (1) for absolute constants C1,C2,C3>0C_1,C_2,C_3>0, where πmin≥1/neff⋆ _ ≥ 1/n_eff (from Lemma B.6). Proof B.9 (Proof Sketch). Write Yt(a)≔at=aY_t(a) 1\a_t=a\ and ξt(a)≔Yt(a)−[Yt(a)∣ℱt−1] _t(a) Y_t(a)-E[Y_t(a) _t-1]. The total visitation count is ∑t≤TexpYt(a)=∑t≤Texpπt(a)+∑t≤Texp([Yt(a)∣ℱt−1]−πt(a))+∑t≤Texpξt(a) _t≤ T_ Y_t(a)= _t≤ T_ _t(a)+ _t≤ T_ (E[Y_t(a) _t-1]- _t(a))+ _t≤ T_ _t(a). We bound the mass, bias, and martingale terms. Mass Term: ∑t≤Texpπt(a)≥Texpπmin _t≤ T_ _t(a)≥ T_ _ . Bias Term: Using the every-step TV contraction for lazy reversible chains, ∑t≤Texp|[Yt(a)∣ℱt−1]−πt(a)|≤∑t≤Texp∥μt−1−πt−1∥TV≤∑t=0∞e−tγhet/2≈2γhet. _t≤ T_ |E[Y_t(a) _t-1]- _t(a) |≤ _t≤ T_ \| _t-1- _t-1\|_TV≤ _t=0^∞e^-t _het/2≈ 2 _het. The b term, which includes log(T/δ) (T/δ), provides a high-probability bound on this total bias, ∑t≤Texp(μt−1(a)−πt(a))≥−C1b _t≤ T_ ( _t-1(a)- _t(a))≥-C_1b. Martingale Term: The sum MTexp=∑t≤Texpξt(a)M_T_ = _t≤ T_ _t(a) is a martingale. The predictable quadratic variation VTexp=∑t=1Texp[ξt(a)2∣ℱt−1]V_T_ = _t=1^T_ E[ _t(a)^2 _t-1] is bounded using the sharper variance bound: [ξt(a)2∣ℱt−1]=Var(Yt(a)∣ℱt−1)≤[Yt(a)∣ℱt−1]=μt−1(a).E[ _t(a)^2 _t-1]=Var(Y_t(a) _t-1) [Y_t(a) _t-1]= _t-1(a). Thus, VTexp≤∑t≤Texpμt−1(a)≤∑t≤Texpπt(a)+∑t≤Texp‖μt−1−πt−1‖TV≤Texpπmin+C1bV_T_ ≤ _t≤ T_ _t-1(a)≤ _t≤ T_ _t(a)+ _t≤ T_ \| _t-1- _t-1\|_TV≤ T_ \, _ +C_1b. By Freedman’s inequality with this VTexpV_T_ and x=log(4n/δ)x= (4n/δ), with probability at least 1−δ/41-δ/4, MTexp(a)≥−C(VTexpx+x)≥−C2(Texpπmin+C1b)log4nδ−C3log4nδM_T_ (a)≥-C ( V_T_ x+x )≥-C_2 (T_ \, _ +C_1b)\, 4nδ-C_3 4nδ simultaneously for all a. Combining the terms yields Eq. (1). Sufficient Exploration and Identification. We now find TexpT_ such that we get enough samples for identification. We allocate a failure budget of δ/4δ/4 for identification. Let s0 C′log(4n/δ)Δmin2s_0 C (4n/δ) _ ^2 be the required sample count per arm. From Eq. (1), we need TexpT_ large enough for the RHS to be ≥s0≥ s_0. This requires TexpπminT_ _ to dominate s0s_0, b, and the martingale term. This leads to two additive requirements for TexpT_ : 1. Mixing Cost (Tmix-hetT_mix-het): TexpT_ must be large enough to ensure non-trivial visitation. TexpπminT_ _ must dominate b and the martingale term. • Texpπmin b⟹Texp b/πmin=O(neff⋆γhetlog(nT/δ))T_ _ b T_ b/ _ =O ( n_eff _het (nT/δ) ). • Texpπmin (Texpπmin+b)log(⋅)⟹(Texpπmin)2 (Texpπmin+b)log(⋅)T_ _ (T_ _ +b) (·) (T_ _ )^2 (T_ _ +b) (·). This is satisfied if Texpπmin (b+log(⋅))T_ _ (b+ (·)), which leads to Texp O(neff⋆(b+log(⋅)))T_ O(n_eff (b+ (·))). This gives Tmix-het O(neff⋆γhetlog(nT/δ)+neff⋆log(n/δ))T_mix-het O ( n_eff _het (nT/δ)+n_eff (n/δ) ). 2. Identification Cost (Tid-hetT_id-het): The resulting number of samples Nmin≈Texpπmin≥Ω(Texp/neff⋆)N_ ≈ T_ _ ≥ (T_ /n_eff ) must be at least s0s_0. Texpneff⋆≥s0⟹Texp≥neff⋆⋅s0=O(neff⋆log(n/δ)Δmin2). T_ n_eff ≥ s_0 T_ ≥ n_eff · s_0=O ( n_eff (n/δ) _ ^2 ). The total exploration time must satisfy Texp≥Tmix-het+Tid-hetT_ ≥ T_mix-het+T_id-het. Navigation Cost. The navigation analysis provides two distinct bounds: one based on the time to mix across the graph, and one based on the time to wait for a direct connection to a⋆a . Lemma B.10 (Navigation Cost, Inhomogeneous). Fix the failure budget δnav=δ/4 _nav=δ/4. Work on the uniform typicality event (Lemma B.2) and the spectral-gap bound (Theorem B.4). Let a⋆a be the optimal arm and define the optimal-arm availability floor p⋆ mina≠a⋆pa,a⋆.p \; \; _a≠ a p_a,a . Then the number of steps TnavT_nav needed after exploration to reach a⋆a satisfies, with probability at least 1−δ/41-δ/4, Tnav≤minO(1γhetlognTδ+neff⋆lognδ)⏟mixing–hitting route,O(1p⋆log1δ)⏟availability route.T_nav\;≤\; \! \ O ( 1 _het\, \! nTδ\;+\;n_eff \, \! nδ )_mixing--hitting route, O ( 1p \, \! 1δ )_availability route \. Moreover, the expected navigation time is [Tnav]≤minO(neff⋆+1/γhet),1/p⋆E[T_nav]≤ \O(n_eff +1/ _het),1/p \. Proof B.11. We provide the high-probability bounds for the two routes. (A) Availability route. From any a≠a⋆a≠ a , the agent can wait for a⋆a to become available. This is an i.i.d. Bernoulli trial with success probability pa,a⋆≥p⋆p_a,a ≥ p . The waiting time is Geom(pa,a⋆)Geom(p_a,a ). A standard geometric tail bound and a union bound over a≠a⋆a≠ a gives Tnav≤O(log(4/δ)/p⋆)T_nav≤ O( (4/δ)/p ) w.h.p. (This route is vacuous if p⋆=0p =0). (B) Mixing–hitting route. The agent’s walk mixes to πt _t in b=O(log(nT/δ)/γhet)b=O( (nT/δ)/ _het) steps. After this, Pr(at=a⋆)≥πt(a⋆)−(TV error)≥πmin−ϵ≥Ω(1/neff⋆) (a_t=a )≥ _t(a )-(TV error)≥ _ -ε≥ (1/n_eff ). The time to hit a⋆a is then geometric with success prob. Ω(1/neff⋆) (1/n_eff ). A tail bound on this geometric variable gives the O(neff⋆log(4/δ))O(n_eff (4/δ)) term. The total time is Tnav≤b+(hit time)T_nav≤ b+(hit time). Final Regret Bound. We now combine these results for the final theorem. For clarity, we use the simpler and typically tighter ”availability route” for navigation, assuming p⋆>0p >0. Theorem B.12 ((Full Version) Regret Bound for i.i.d. Inhomogeneous ER). Under the i.i.d. inhomogeneous ER model with σmin⋆≥Clog(nT/δ) _ ≥ C (nT/δ) and p⋆>0p >0, the regret is bounded with probability at least 1−δ1-δ by: R(T)≤Texp+Tnav,R(T)\;≤\;T_ +T_nav, where Texp=O(neff⋆γhetlog(nT/δ)+neff⋆log(n/δ)⏟Mixing Cost+neff⋆log(n/δ)Δmin2⏟Identification Cost)T_ =O ( n_eff _het (nT/δ)+n_eff (n/δ)_Mixing Cost+ n_eff (n/δ) _ ^2_Identification Cost ) and Tnav=O(log(1/δ)p⋆).T_nav=O ( (1/δ)p ). Proof B.13. The total failure probability is bounded by ℙ(ℰtypicalityc)+ℙ(ℰvisitationc)+ℙ(ℰidentificationc)+ℙ(ℰnavc)≤δ/4+δ/4+δ/4+δ/4=δP(E_typicality^c)+P(E_visitation^c)+P(E_identification^c)+P(E_nav^c)≤δ/4+δ/4+δ/4+δ/4=δ. On the success event, the regret is the sum of the exploration cost (TexpT_ ) and the navigation cost (TnavT_nav). The final bound for TexpT_ is the sum of the identification cost (Tid-hetT_id-het) and the mixing cost (Tmix-hetT_mix-het). Corollary B.14 ((Full Version) Expected Regret Bound). Under the same conditions, by setting δ=1/Tδ=1/T, the expected cumulative regret R(T)R(T) is bounded by: [R(T)]=O(neff⋆γhetlog(nT)+neff⋆log(nT)+neff⋆log(nT)Δmin2+log(T)p⋆).E[R(T)]\;=\;O ( n_eff _het (nT)+n_eff (nT)+ n_eff (nT) _ ^2+ (T)p ). Proof B.15. Follows from Theorem B.12 by setting δ=1/Tδ=1/T and noting that the regret contribution from the failure event is at most T⋅ℙ(fail)≤T⋅(1/T)=1T·P(fail)≤ T·(1/T)=1. Remark B.16 (Consistency with Homogeneous ER). This analysis is a strict generalization of Appendix A. In the homogeneous case (paj≡p_aj≡ p), the parameters simplify: • da⋆=(n−1)pd_a =(n-1)p, so σmin⋆=(n−1)p _ =(n-1)p. • φ⋆=Ω(1) = (1) and γhet=Ω(1) _het= (1) (as shown in Theorem B.4). • neff⋆≍neff=n(n−1)p+n(n−1)p=Θ(n)n_eff n_eff= n(n-1)p+n(n-1)p= (n) (assuming np 1np 1). • p⋆=p_ =p. Substituting these into Corollary B.14 gives [R(T)]=O(nlog(nT)+nlog(nT)+nlog(nT)Δmin2+log(T)p).E[R(T)]\;=\;O (n (nT)+n (nT)+ n (nT) _ ^2+ (T)p ). This expression simplifies to O(nlog(nT)+nlog(nT)Δmin2+log(T)p)O(n (nT)+ n (nT) _ ^2+ (T)p). This result matches the O(nlog(nT)/Δmin2)O(n (nT)/ _ ^2) identification cost and O(log(T)/p)O( (T)/p) navigation cost from Appendix A, and also recovers the O(nlog(nT))O(n (nT)) mixing cost, confirming the analyses are consistent. Appendix C Regret Analysis: Edge-Markovian Graphs C.1 Model, Notation and Graph Dynamics C.1.1 Problem Setup and Edge-Markovian Process We begin by formally restating the core problem setup from Section 2 to establish a self-contained foundation for our analysis. The problem environment consists of a finite set of n actions, or arms, denoted by the set A=1,2,…,nA=\1,2,…,n\. Each arm a∈Aa∈ A is associated with a fixed, unknown reward distribution (a)D(a) which is supported on the interval [0,1][0,1]. The mean of this distribution is denoted μ(a)∈[0,1]μ(a)∈[0,1] and is also unknown to the learner. The learner’s interaction with this environment unfolds over a time horizon of T discrete rounds. At the beginning of each round t∈1,…,Tt∈\1,…,T\, the learner resides at the arm at−1a_t-1 chosen in the previous round. The environment then reveals a time-varying set of available arms Lt(at−1)⊆AL_t(a_t-1) A. This set is defined by the local graph structure at time t relative to the learner’s position at−1a_t-1. Specifically, Lt(at−1) a∈A:(a,at−1)∈Et∪at−1L_t(a_t-1) \\,a∈ A:(a,a_t-1)∈ E_t\,\∪\a_t-1\, where EtE_t is the edge set of the graph GtG_t at time t. The learner must then select a new arm ata_t from this constrained set, at∈Lt(at−1)a_t∈ L_t(a_t-1), after which they receive and observe a stochastic reward rt(at)∼(at)r_t(a_t) (a_t). The learner’s objective is to design a selection policy that minimizes the expected cumulative regret, [R(T)]E[R(T)], as defined in Section 2. In this appendix, we focus exclusively on the stochastic process that governs the environment’s evolution under the Edge-Markovian model. We will formally define this process and establish the graph-theoretic notation essential for our analysis. The specific dynamics of the learner’s movement algorithm, which we define as a natural lazy random walk on this evolving graph, and the properties of the resulting time-inhomogeneous Markov chain will be analyzed in detail in Appendix C.1.2. Edge-Markovian Evolution of the Environment. The environment’s availability structure is encoded by a sequence of undirected graphs, Gtt=1T\G_t\_t=1^T, where each Gt=(A,Et)G_t=(A,E_t) is defined over the fixed vertex set A. The graphs evolve according to a homogeneous, first-order edge-Markov process, which we denote by Gt∼ΨM(Gt−1;n,α,β)G_t ^M(G_t-1;n,α,β). In this model, the state of each potential edge (each unordered pair of distinct vertices i,j\i,j\) evolves independently of all other pairs. For any given pair i,j\i,j\, its state (being present in EtE_t or absent from EtE_t) follows a discrete-time, two-state Markov chain. The transition probabilities are fixed for all t and all pairs: • Edge Appearance: The probability that an absent edge appears is [(i,j)∈Et∣(i,j)∉Et−1]=α [(i,j)∈ E_t (i,j)∉ E_t-1]=α • Edge Disappearance: The probability that a present edge disappears is [(i,j)∉Et∣(i,j)∈Et−1]=β [(i,j)∉ E_t (i,j)∈ E_t-1]=β The parameters α,β∈(0,1)α,β∈(0,1) fully define this process. Consequently, the dynamics of a single edge are governed by the 2×22× 2 transition matrix P over the states 0 (absent),1 (present)\0 (absent),1 (present)\: P=[1−αβ1−β]P= bmatrix1-α&α\\[2.0pt] β&1-β bmatrix This single-edge Markov chain is finite-state. Since we assume α,β∈(0,1)α,β∈(0,1), it is: 1. Irreducible: It is possible to transition from state 0 to 1 (with probability α>0α>0) and from state 1 to 0 (with probability β>0β>0). 2. Aperiodic: Both states have positive self-loop probabilities (1−α>01-α>0 and 1−β>01-β>0, assuming neither is 1). By standard Markov chain theory (levin2017markov), this process admits a unique stationary distribution πedge=(π0,π1) _edge=( _0, _1), which is the unique solution to the system πedgeP=πedge _edgeP= _edge subject to the constraint π0+π1=1 _0+ _1=1. We can solve this system explicitly. From the second column of πedgeP=πedge _edgeP= _edge, we have: π0α+π1(1−β)=π1 _0α+ _1(1-β)= _1 π0α=π1−π1(1−β)=π1β _0α= _1- _1(1-β)= _1β Substituting π0=1−π1 _0=1- _1: (1−π1)α=π1β⟹α−π1α=π1β⟹α=π1(α+β)(1- _1)α= _1β α- _1α= _1β α= _1(α+β) This yields the stationary probabilities: π1=α+β p∞andπ0=1−π1=βα+β _1= α+β p_∞ _0=1- _1= βα+β Thus, after the process has mixed, the stationary law of the graph GtG_t is an Erdős–Rényi graph G(n,p∞)G(n,p_∞), where every edge appears independently with probability p∞p_∞. This p∞p_∞ represents the long-run expected edge density of the graph. This process of continuous, independent edge-flipping implies a natural measure of the environment’s volatility: the expected number of edges that change state (appear or disappear) in a single time step. We formalize this quantity below. Claim 1 (Expected Per-Step Edge Flips). Let m=(n2)m= n2 be the total number of possible edges. Let ζt [|Et△Et−1|] _t [|E_t E_t-1|] be the expected total number of edge flips at time t, where the expectation is over the graph evolution process. 1. (Uniform Bound) The expected number of flips is uniformly bounded by ζt≤m⋅max(α,β) _t≤ m· (α,β) 2. (Stationary Bound) If the graph Gt−1G_t-1 is drawn from the stationary distribution (i.e., each edge exists i.i.d. with probability p∞p_∞), the expected number of flips is ζ=m⋅2αβα+βζ=m· 2αβα+β Proof C.1. Let Xij,t∈0,1X_ij,t∈\0,1\ be the indicator variable for the presence of edge (i,j)(i,j) at time t. The set of flipped edges is the symmetric difference Et△Et−1E_t E_t-1, and its size is |Et△Et−1|=∑1≤i<j≤nXij,t≠Xij,t−1|E_t E_t-1|= _1≤ i<j≤ n1\X_ij,t≠ X_ij,t-1\. By linearity of expectation, ζt=[|Et△Et−1|]=∑1≤i<j≤n (Xij,t≠Xij,t−1) _t=E[|E_t E_t-1|]= _1≤ i<j≤ n (X_ij,t≠ X_ij,t-1) The probability of a single edge flipping, (flip) (flip), depends on its state at t−1t-1: (Xij,t≠Xij,t−1) (X_ij,t≠ X_ij,t-1) = (Xij,t=1∣Xij,t−1=0) (Xij,t−1=0) = (X_ij,t=1 X_ij,t-1=0) (X_ij,t-1=0) + (Xij,t=0∣Xij,t−1=1) (Xij,t−1=1) + (X_ij,t=0 X_ij,t-1=1) (X_ij,t-1=1) =α⋅ (Xij,t−1=0)+β⋅ (Xij,t−1=1) =α· (X_ij,t-1=0)+β· (X_ij,t-1=1) Let pt−1(ij) (Xij,t−1=1)p_t-1^(ij) (X_ij,t-1=1) be the marginal probability that edge (i,j)(i,j) exists. Since the process is homogeneous, this probability is the same for all edges, pt−1(ij)=pt−1p_t-1^(ij)=p_t-1. (flip)=α(1−pt−1)+βpt−1=α+(β−α)pt−1 (flip)=α(1-p_t-1)+β p_t-1=α+(β-α)p_t-1 This is a linear function of pt−1∈[0,1]p_t-1∈[0,1]. The maximum must occur at the endpoints pt−1=0p_t-1=0 or pt−1=1p_t-1=1. • If pt−1=0p_t-1=0, (flip)=α (flip)=α. • If pt−1=1p_t-1=1, (flip)=β (flip)=β. Thus, the per-edge flip probability is uniformly bounded by max(α,β) (α,β). Substituting this into the sum for ζt _t (which has m=(n2)m= n2 terms) proves Part 1: ζt=∑1≤i<j≤n (flip)≤∑1≤i<j≤nmax(α,β)=m⋅max(α,β) _t= _1≤ i<j≤ n (flip)≤ _1≤ i<j≤ n (α,β)=m· (α,β) For Part 2, we assume the process is in stationarity, so pt−1=p∞=α+βp_t-1=p_∞= α+β. We substitute this into the expression for the per-edge flip probability: (flip) (flip) =α(1−p∞)+βp∞ =α(1-p_∞)+β p_∞ =α(βα+β)+β(α+β)=αβ+αβα+β=2αβα+β =α ( βα+β )+β ( α+β )= αβ+αβα+β= 2αβα+β Substituting this constant probability back into the sum for ζt _t proves Part 2: ζ=∑1≤i<j≤n(2αβα+β)=m⋅2αβα+βζ= _1≤ i<j≤ n ( 2αβα+β )=m· 2αβα+β The parameter α+βα+β governs the temporal correlation scale of the graph sequence. This value is precisely the spectral gap of the 2×22× 2 matrix P. When α+βα+β is small (close to 0), the second eigenvalue 1−(α+β)1-(α+β) is close to 1, implying slow mixing and high correlation between GtG_t and Gt−1G_t-1. Conversely, as α+βα+β approaches 1, the process becomes less correlated, and in the limit α+β=1α+β=1, the graph GtG_t is drawn i.i.d. from the stationary distribution at each step, independent of Gt−1G_t-1. Per-step Structure and Notation. We now define the core notation used to describe the properties of the graph GtG_t at a single time step t. • Degree: For any node i∈Ai∈ A, let dt(i)d_t(i) denote its degree in the graph GtG_t. Formally, we define dt(i) |j∈A∖i:(i,j)∈Et|d_t(i) |\\,j∈ A \i\:(i,j)∈ E_t\,\|. • Normalization Factor: We define a normalization factor ZtZ_t as: Zt ∑i∈A(dt(i)+1)Z_t _i∈ A(d_t(i)+1) We can simplify this expression by appealing to the handshaking lemma (sum of degrees is twice the number of edges): Zt=∑i∈Adt(i)+∑i∈A1=(2|Et|)+nZ_t= _i∈ Ad_t(i)+ _i∈ A1=(2|E_t|)+n This quantity ZtZ_t will be essential for defining the stationary distribution of the random walk on GtG_t. • Conditional Expectation: We use t[⋅] [⋅∣Gt]E_t[·] [· G_t] to denote an expectation conditioned on the realization of the graph GtG_t at time t. • Asymptotic Notation: We use the shorthand A≍BA B to indicate equality up to absolute constants (i.e., C1B≤A≤C2BC_1B≤ A≤ C_2B for C1,C2>0C_1,C_2>0) that are independent of the problem parameters n,T,α,βn,T,α,β. C.1.2 Lazy Walk Dynamics and Properties As part of the algorithm design (see Sections 3 and 4), the learner’s movement is modeled as a natural lazy random walk on the current graph GtG_t. Conditioned on the graph GtG_t being fixed for round t, the learner’s transition from their current node i (i.e., at=ia_t=i) to the next node j (i.e., at+1=ja_t+1=j) is defined by a one-step transition kernel WtW_t. From a node i, the set of available options is its 1-hop neighborhood union the node itself: j∈A:(i,j)∈Et∪i\\,j∈ A:(i,j)∈ E_t\,\∪\i\. The size of this set is dt(i)+1d_t(i)+1. The walk moves by selecting one of these dt(i)+1d_t(i)+1 options uniformly at random. This defines the transition probabilities: Wt(i,j)=1/(dt(i)+1),if j=i or (i,j)∈Et,0,otherwise.W_t(i,j)= cases1/(d_t(i)+1),&if j=i or (i,j)∈ E_t,\\[2.0pt] 0,&otherwise. cases The kernel WtW_t defines the learner’s movement for a single step, given a fixed graph GtG_t. We now formally show how the sequence of these kernels, driven by the stochastic evolution of the graphs, induces a time-inhomogeneous Markov chain on the action set A. Claim 2 (Markovianity of the Induced Dynamics). Let the environment’s graph sequence Gtt≥0\G_t\_t≥ 0 evolve according to the edge-Markovian process Gt∼ΨM(Gt−1;n,α,β)G_t ^M(G_t-1;n,α,β), independent of the learner’s actions. Let the learner’s action sequence att≥0\a_t\_t≥ 0 evolve according to the rule at+1∼Wt(at,⋅)a_t+1 W_t(a_t,·), where WtW_t is the lazy walk kernel on GtG_t. 1. The joint process t=(at,Gt)Z_t=(a_t,G_t) is a first-order Markov chain on the product space A×A×G, where G is the space of all graphs on A. 2. The learner’s action sequence (at)t≥0(a_t)_t≥ 0 is a time-inhomogeneous Markov chain. Proof C.2. 1. To prove the joint process t=(at,Gt)Z_t=(a_t,G_t) is Markov, we must show that its state at t+1t+1 depends only on its state at t. Let ℋt=(0,…,t)H_t=(Z_0,…,Z_t) be the history up to time t. We want to show (t+1∣ℋt)= (t+1∣t) (Z_t+1 _t)= (Z_t+1 _t). The state at t+1t+1 is t+1=(at+1,Gt+1)Z_t+1=(a_t+1,G_t+1). We analyze the transition probability using the chain rule: (at+1,Gt+1∣ℋt)= (Gt+1∣at+1,ℋt)⋅ (at+1∣ℋt) (a_t+1,G_t+1 _t)= (G_t+1 a_t+1,H_t)· (a_t+1 _t) Let’s analyze each term: • (at+1∣ℋt)= (at+1∣at,Gt,…,a0,G0) (a_t+1 _t)= (a_t+1 a_t,G_t,…,a_0,G_0): By the definition of the learner’s algorithm, the choice of at+1a_t+1 is a sample from Wt(at,⋅)W_t(a_t,·). This rule depends only on the current state ata_t and the current graph GtG_t. Thus, (at+1∣ℋt)= (at+1∣at,Gt)=Wt(at,⋅) (a_t+1 _t)= (a_t+1 a_t,G_t)=W_t(a_t,·) • (Gt+1∣at+1,ℋt) (G_t+1 a_t+1,H_t): The graph evolution Gt+1∼ΨM(Gt,⋅)G_t+1 ^M(G_t,·) is exogenous; it depends only on the previous graph GtG_t and is independent of all actions (a0,…,at+1)(a_0,…,a_t+1). Therefore, (Gt+1∣at+1,ℋt)= (Gt+1∣Gt) (G_t+1 a_t+1,H_t)= (G_t+1 G_t) Substituting these back, we get: (at+1,Gt+1∣ℋt)= (Gt+1∣Gt)⋅ (at+1∣at,Gt) (a_t+1,G_t+1 _t)= (G_t+1 G_t)· (a_t+1 a_t,G_t) The right-hand side is a function P((at+1,Gt+1)∣(at,Gt))P((a_t+1,G_t+1) (a_t,G_t)) which defines a valid transition kernel from tZ_t to t+1Z_t+1. Since the probability of the next state given the entire history depends only on the current state, the joint process tZ_t is a first-order Markov chain. 2. To prove the action sequence (at)(a_t) is a Markov chain, we must show that (at+1∣at,…,a0)= (at+1∣at) (a_t+1 a_t,…,a_0)= (a_t+1 a_t). Let t=(a0,…,at)A_t=(a_0,…,a_t) be the action history. (at+1∣t) (a_t+1 _t) =[at+1∣t] =E[1\a_t+1\ _t] =Gt,…,G0[ (at+1∣t,Gt,…,G0)∣t](by Law of Total Expectation) =E_G_t,…,G_0 [ (a_t+1 _t,G_t,…,G_0) _t ] (by Law of Total Expectation) =Gt,…,G0[Wt(at,⋅)∣t](as shown in Part 1) =E_G_t,…,G_0 [W_t(a_t,·) _t ] (as shown in Part 1) The kernel WtW_t is a deterministic function of GtG_t. The graph process Gt\G_t\ is independent of the action history t\A_t\. Therefore, the expectation over the graph history is independent of tA_t (except for the ata_t term inside WtW_t). (at+1∣t)=Gt[Wt(at,⋅)] (a_t+1 _t)=E_G_t [W_t(a_t,·) ] where the expectation Gt[⋅]E_G_t[·] is taken over the randomness of the graph GtG_t, whose distribution (Gt) (G_t) is determined by the initial graph G0G_0 and the t-step evolution of the ΨM ^M process. Let us define the effective transition kernel W~t W_t as this expectation: W~t(i,j) Gt[Wt(i,j)] W_t(i,j) _G_t [W_t(i,j) ] Then we have shown: (at+1=j∣at=i,at−1,…,a0)=W~t(i,j) (a_t+1=j a_t=i,a_t-1,…,a_0)= W_t(i,j) Since the transition probability depends only on the current state i=ati=a_t (and the time t), the process (at)(a_t) is a Markov chain. Because the kernel W~t W_t changes with t (as the distribution of GtG_t evolves towards stationarity), the chain is time-inhomogeneous. This claim formally establishes that the learner’s trajectory (at)(a_t) is a time-inhomogeneous Markov chain. However, our subsequent analysis will not focus on the effective (expected) kernel W~t W_t. Instead, we will analyze the realized trajectory of the learner by conditioning on a specific, typical sequence of graphs Gtt≥0\G_t\_t≥ 0. In this conditional view, the learner’s movement is a time-inhomogeneous Markov chain driven by the sequence of concrete, deterministic kernels Wtt≥0\W_t\_t≥ 0 corresponding to the realized graphs. The properties of these individual kernels WtW_t are therefore paramount to understanding the learner’s behavior. We characterize these properties in the following lemma. Lemma C.3 (Properties of the Lazy Walk Kernel). For any graph GtG_t with at least one node (n≥1n≥ 1), the transition kernel WtW_t defined above satisfies: 1. (Stochasticity) WtW_t is a row-stochastic matrix. 2. (Aperiodicity) WtW_t defines an aperiodic Markov chain. 3. (Reversibility) WtW_t is reversible with respect to the distribution πt(i)=dt(i)+1Zt _t(i)= d_t(i)+1Z_t, which is its unique stationary distribution. Proof C.4. 1. Stochasticity: We show that for any i∈Ai∈ A, the entries in row i sum to one: ∑j∈AWt(i,j)=1 _j∈ AW_t(i,j)=1. By definition, Wt(i,j)W_t(i,j) is non-zero only for the set of available actions Lt(i) i∪j≠i:(i,j)∈EtL_t(i) \i\∪\j≠ i:(i,j)∈ E_t\. The size of this set is precisely |Lt(i)|=1+dt(i)|L_t(i)|=1+d_t(i). We can therefore compute the row-sum by partitioning the sum over A into this set and its complement (where all terms are zero): ∑j∈AWt(i,j) _j∈ AW_t(i,j) =∑j∈Lt(i)Wt(i,j)+∑j∉Lt(i)Wt(i,j)⏟=0 = _j∈ L_t(i)W_t(i,j)+ _j∉ L_t(i) W_t(i,j)_=0 =∑j∈Lt(i)(1dt(i)+1) = _j∈ L_t(i) ( 1d_t(i)+1 ) =|Lt(i)|⋅(1dt(i)+1) =|L_t(i)|· ( 1d_t(i)+1 ) =(1+dt(i))⋅(1dt(i)+1)=1. =(1+d_t(i))· ( 1d_t(i)+1 )=1. Since Wt(i,j)≥0W_t(i,j)≥ 0 for all (i,j)(i,j) and each row sums to 1, WtW_t is a row-stochastic matrix. 2. Aperiodicity: A Markov chain is aperiodic if all its states are aperiodic. A sufficient condition is that the self-loop probability Wt(i,i)>0W_t(i,i)>0 for all i. By definition, Wt(i,i)=1dt(i)+1.W_t(i,i)= 1d_t(i)+1. Since the degree is non-negative, dt(i)≥0d_t(i)≥ 0, the denominator is dt(i)+1≥1d_t(i)+1≥ 1. The maximum possible degree in a graph with n nodes is n−1n-1. Therefore, we have a strict positive lower bound: Wt(i,i)≥1(n−1)+1=1n>0.W_t(i,i)≥ 1(n-1)+1= 1n>0. Since all states have positive self-loop probability, the chain is aperiodic. 3. Reversibility: We must verify that the detailed balance equations, πt(i)Wt(i,j)=πt(j)Wt(j,i) _t(i)W_t(i,j)= _t(j)W_t(j,i), hold for all pairs i,j∈Ai,j∈ A. Case 1: i=ji=j. The equation is trivially satisfied: πt(i)Wt(i,i)=πt(i)Wt(i,i) _t(i)W_t(i,i)= _t(i)W_t(i,i). Case 2: i≠ji≠ j and (i,j)∉Et(i,j)∉ E_t. By definition of WtW_t, Wt(i,j)=0W_t(i,j)=0 and Wt(j,i)=0W_t(j,i)=0. The equation becomes πt(i)⋅0=πt(j)⋅0 _t(i)· 0= _t(j)· 0, which is 0=00=0. Case 3: i≠ji≠ j and (i,j)∈Et(i,j)∈ E_t. This is the only non-trivial case. We use the definitions of πt _t and WtW_t: πt(i)Wt(i,j) _t(i)W_t(i,j) =(dt(i)+1Zt)(1dt(i)+1)=1Zt = ( d_t(i)+1Z_t ) ( 1d_t(i)+1 )= 1Z_t πt(j)Wt(j,i) _t(j)W_t(j,i) =(dt(j)+1Zt)(1dt(j)+1)=1Zt = ( d_t(j)+1Z_t ) ( 1d_t(j)+1 )= 1Z_t Since πt(i)Wt(i,j)=πt(j)Wt(j,i) _t(i)W_t(i,j)= _t(j)W_t(j,i), the detailed balance equations hold. Because WtW_t is reversible with respect to πt _t, πt _t is a stationary distribution. Since the chain is also finite and irreducible (on any connected component of GtG_t), this stationary distribution is unique to that component. C.2 Burn-in and Typicality of the Edge Process This section provides a high-probability guarantee that after a short burn-in period, the graph sequence (Gt)(G_t) behaves in a statistically typical manner: degrees, edge counts, and spectral structure concentrate around their stationary values. This typicality is required to apply uniform bounds on the walk kernel, its spectral gap, and the stationary distribution in later sections. C.2.1 Burn-in for Stationarity Throughout the regret analysis in this appendix, we will establish high-probability guarantees on the behavior of various quantities associated with the graph sequence, the walk process, and the learner’s sampling law. To this end, we fix a total confidence parameter δ∈(0,1)δ∈(0,1) and ensure that each component of the analysis fails with probability at most a small fraction of δ. The final regret bound will then hold with probability at least 1−δ1-δ via an explicit union bound. In this subsection, we quantify the number of initial rounds required for the edge–Markovian graph process (Gt)t≥0(G_t)_t≥ 0 to become statistically close to its stationary distribution. We refer to this initial period as the burn-in phase, and the corresponding time as the burn-in length. Definition C.5 (Burn-in Length). Let δ∈(0,1)δ∈(0,1) be the desired overall failure probability. We define the burn-in time as Tburn ⌈2logn+log(1/δ)α+β⌉,T_burn 2 n+ (1/δ)α+β , where α+βα+β is the total flip rate of the edge–Markov process ΨM ^M, and n is the number of nodes in the graph. This quantity ensures that by time TburnT_burn, the distribution of the graph GtG_t is δ-close in total variation distance to the stationary edge distribution, which is a product of independent Bernoulli variables with parameter p∞ α+β.p_∞ α+β. We now formalize this convergence to stationarity. Lemma C.6 (Convergence to the stationary edge distribution). Let (Gt)t≥0(G_t)_t≥ 0 evolve according to the edge–Markov process Gt∼ΨM(Gt−1;n,α,β)G_t ^M(G_t-1;n,α,β), starting from an arbitrary initial graph G0G_0. Then for every t≥Tburnt≥ T_burn, ‖(Gt∈⋅)−∞(⋅)‖TV≤δ, \|P(G_t∈·)-P_∞(·) \|_TV≤δ, where ∞P_∞ denotes the stationary product measure under which each edge is independently present with probability p∞ α/(α+β)p_∞ α/(α+β). Proof C.7. We prove the result by analyzing the convergence of each individual edge’s marginal distribution to stationarity, and then bounding the total variation distance over the joint graph distribution via a union bound across all edges. The argument proceeds in three steps: (i) we derive an exact recursion for the marginal probability pt(i,j)p_t(i,j) that edge (i,j)(i,j) is present at time t, (i) we use this to bound the total variation distance between the full graph law and the product Bernoulli(p∞p_∞) stationary law, and (i) we determine a sufficient value of t to ensure this joint distance is at most δ. Each unordered edge (i,j)(i,j) evolves independently as a two–state Markov chain with transition matrix P=[1−αβ1−β],over states 0:absent, 1:present.P\;=\; bmatrix1-α&α\\[2.0pt] β&1-β bmatrix, states 0\!:\!absent,\;1\!:\!present. This chain is irreducible and aperiodic (see Appendix C.1.1), and hence admits a unique stationary distribution πedge=(π0,π1) _edge=( _0, _1) satisfying πedgeP=πedge _edgeP= _edge. Solving these balance equations gives π1=α+β p∞,π0=βα+β. _1= α+β p_∞, _0= βα+β. Step 1: marginal recursion. Let pt(i,j) [(i,j)∈Et]p_t(i,j) [(i,j)∈ E_t] denote the probability that edge (i,j)(i,j) is present at time t. Conditioning on the previous state yields the scalar recursion pt+1(i,j)=(1−β)pt(i,j)+α(1−pt(i,j))=(1−α−β)pt(i,j)+α.p_t+1(i,j)=(1-β)\,p_t(i,j)+α\, (1-p_t(i,j) )=(1-α-β)\,p_t(i,j)+α. Subtracting p∞p_∞ from both sides and using the identity p∞=(1−α−β)p∞+αp_∞=(1-α-β)p_∞+α gives pt+1(i,j)−p∞=(1−α−β)(pt(i,j)−p∞).p_t+1(i,j)-p_∞=(1-α-β)\, (p_t(i,j)-p_∞ ). Iterating this recurrence yields the explicit form pt(i,j)−p∞=(1−α−β)t(p0(i,j)−p∞),p_t(i,j)-p_∞=(1-α-β)^t\, (p_0(i,j)-p_∞ ), and hence the magnitude satisfies |pt(i,j)−p∞|≤(1−α−β)t. |p_t(i,j)-p_∞ |≤(1-α-β)^t. Step 2: from marginal to joint total variation. Let m (n2)m n2 denote the total number of edges. Since the edge processes are mutually independent, the joint law of the entire graph is the product of these m independent two–state chains. For product measures, the total variation distance between the joint distribution and its stationary product law can be bounded by the sum of the marginal distances: ‖(Gt)−∞‖TV≤∑i,j‖((i,j)∈Et)−∞((i,j)∈Et)‖TV. \|P(G_t)-P_∞ \|_TV≤ _\i,j\ \|P ((i,j)\!∈\!E_t )-P_∞ ((i,j)\!∈\!E_t ) \|_TV. For a single edge variable taking values in 0,1\0,1\, the total variation distance between two Bernoulli distributions equals the absolute difference of their means. Using (C.7) we therefore obtain ‖(Gt)−∞‖TV≤∑i,j|pt(i,j)−p∞|≤m(1−α−β)t. \|P(G_t)-P_∞ \|_TV≤ _\i,j\ |p_t(i,j)-p_∞ |≤ m\,(1-α-β)^t. Step 3: ensuring δ–closeness. To guarantee that the right-hand side of (C.7) does not exceed δ, we require (1−α−β)t≤δm.(1-α-β)^t≤ δm. Since 1−x≤e−x1-x≤ e^-x for x∈(0,1)x∈(0,1), it suffices that e−(α+β)t≤δm⟺t≥1α+βlog(mδ).e^-(α+β)t≤ δm t≥ 1α+β\, \! ( mδ ). Using m=12n(n−1)<n2/2m= 12n(n-1)<n^2/2 and the elementary bound log(m/δ)≤2logn+log(1/δ) (m/δ)≤ 2 n+ (1/δ), we conclude that the choice Tburn ⌈2logn+log(1/δ)α+β⌉T_burn 2 n+ (1/δ)α+β suffices to ensure ‖(Gt)−∞‖TV≤δ \|P(G_t)-P_∞ \|_TV≤δ for all t≥Tburnt≥ T_burn. This lemma justifies our analysis beginning at time TburnT_burn, after which we may treat the graphs GtG_t as approximately distributed according to the Erdős–Rényi model (n,p∞) ER(n,p_∞) with i.i.d. edges, up to a total variation error of at most δ. All high-probability events in the remainder of the analysis will be conditioned on this post–burn-in regime. C.2.2 Typicality Event: Degree and Edge Count Concentration Having established that the edge process converges to its stationary law after the burn-in period, we now show that, with high probability, the graphs GtG_t drawn from this distribution satisfy certain structural regularity properties. Specifically, we show that the degrees of all nodes and the total edge count in GtG_t concentrate sharply around their expectations under the Erdős–Rényi law. These guarantees form the backbone of the uniform bounds used throughout our regret analysis. Analysis overview. We condition on the fact that for all t≥Tburnt≥ T_burn, the distribution of GtG_t is within δ in total variation of the stationary product measure. We then prove that, under this stationary law, the node degrees and total edge count concentrate via standard Chernoff bounds. A union bound over all nodes and over the entire time horizon yields the desired typicality event. We will state all results in terms of the stationary edge density p∞ α+β,p_∞ α+β, but may use the explicit expression involving α and β when this improves readability or makes dependence on parameters more transparent. These forms are interchangeable. Lemma C.8 (Typicality of graph structure after burn-in). Fix any δ∈(0,1)δ∈(0,1) and let T≥TburnT≥ T_burn be the total time horizon. Suppose that n⋅α+β≥C0⋅log(nTδ)n· α+β\;≥\;C_0· ( nTδ ) for a sufficiently large absolute constant C0>0C_0>0. Then with probability at least 1−δ/51-δ/5, the following hold simultaneously for all rounds t∈[Tburn,T]t∈[T_burn,T]: (i) Degree concentration. For all nodes i∈Ai∈ A, |dt(i)−(n−1)⋅α+β|≤c1⋅n⋅α+β⋅log(nTδ). |\,d_t(i)-(n-1)· α+β\, |≤ c_1· n· α+β· ( nTδ ). (i) Edge count concentration. The number of edges satisfies ||Et|−12n(n−1)⋅α+β|≤c2⋅n⋅α+β⋅log(nTδ). |\,|E_t|- 12n(n-1)· α+β\, |≤ c_2· n· α+β· ( nTδ ). (i) Stationary mass lower bound. For all i∈Ai∈ A, πt(i)=dt(i)+1Zt≥c3n, _t(i)= d_t(i)+1Z_t\;≥\; c_3n, where Zt 2|Et|+nZ_t 2|E_t|+n is the walk normalization factor. (iv) Normalization scale. The denominator ZtZ_t satisfies Zt≍n2⋅α+β.Z_t n^2· α+β. Proof C.9. We work conditionally on the event ℰstationary=Gt∼∞ for all t∈[Tburn,T]E_stationary=\G_t _∞ for all t∈[T_burn,T]\, where ∞P_∞ is the product edge law with edge probability p∞=α/(α+β)p_∞=α/(α+β). From Lemma C.6, we know that this event fails with probability at most δ/5δ/5. All bounds below are proven under this event. (i) Degree concentration. For fixed i∈Ai∈ A, the degree dt(i)d_t(i) is distributed as Binomial(n−1,p∞)Binomial(n-1,p_∞) under ∞P_∞. Let Xi∼Bin(n−1,p∞)X_i (n-1,p_∞). Applying a standard Chernoff bound: [|Xi−(n−1)p∞|>ϵ]≤2exp(−ϵ23(n−1)p∞). [\, |X_i-(n-1)p_∞ |>ε\, ]≤ 2 (- ε^23(n-1)p_∞ ). Set ϵ c1np∞log(nTδ),ε c_1 np_∞ ( nTδ ), with c1c_1 large enough to ensure the failure probability is at most δ/(5nT)δ/(5nT) per time-node pair. Applying a union bound over all n nodes and T rounds ensures that the bound holds for all t∈[Tburn,T]t∈[T_burn,T] and all i∈Ai∈ A with failure probability at most δ/5δ/5. (i) Edge count concentration. The total number of edges |Et||E_t| is distributed as Binomial(m,p∞)Binomial(m,p_∞) with m=(n2)m= n2. Applying a similar Chernoff bound: [||Et|−mp∞|>ϵ]≤2exp(−ϵ23mp∞). [\, ||E_t|-mp_∞ |>ε\, ]≤ 2 (- ε^23mp_∞ ). Setting ϵ c2⋅n⋅p∞log(nTδ)ε c_2· n· p_∞ ( nTδ ) and union bounding over T rounds ensures the bound holds uniformly with probability at least 1−δ/51-δ/5. (i) Stationary mass lower bound. From part (i), we have dt(i)≥(n−1)p∞−ϵd_t(i)≥(n-1)p_∞-ε, where ϵ=O(np∞log(nT/δ))ε=O ( np_∞ (nT/δ) ). Similarly, from part (i), we have |Et|≤12n(n−1)p∞+ϵ′|E_t|≤ 12n(n-1)p_∞+ε for a similar ϵ′ε . Combining these, we get πt(i)=dt(i)+12|Et|+n≥(n−1)p∞−ϵ+1n2p∞+O(np∞log(nT/δ))≥c3n, _t(i)= d_t(i)+12|E_t|+n≥ (n-1)p_∞-ε+1n^2p_∞+O(n p_∞ (nT/δ))≥ c_3n, for a constant c3>0c_3>0 provided np∞ log(nT/δ)np_∞ (nT/δ). (iv) Normalization bound. This follows immediately from (i): Zt=2|Et|+n=n2⋅p∞⋅(1+o(1))≍n2⋅α+β.Z_t=2|E_t|+n=n^2· p_∞·(1+o(1)) n^2· α+β. High-Probability Bound on Edge Flips. The kernel drift and stationary distribution drift analyses in Section C.4 rely on bounding the per-step fluctuation in the graph sequence, as measured by the number of edge flips Ft |Et△Et−1|F_t |E_t E_t-1|. While the expected number of flips per round, defined as ζ [Ft]n2=2αβα+β⋅(n2)n2,ζ E[F_t]n^2= 2αβα+β· n2n^2, provides a useful baseline, it does not control the realized behavior with high probability. We now establish a high-probability uniform upper bound on the flip count over all rounds t∈[Tburn,T]t∈[T_burn,T], and define a deterministic quantity ζ0 _0 that bounds Ft/n2F_t/n^2 with high probability. All drift-based quantities in subsequent sections will be expressed in terms of ζ0 _0. Lemma C.10 (High-Probability Flip Envelope). Fix any δ∈(0,1)δ∈(0,1), and let ζ [|Et△Et−1|]n2ζ E[|E_t E_t-1|]n^2 denote the expected per-step flip envelope under the stationary law. Then, with probability at least 1−δ/51-δ/5, the number of flipped edges between consecutive graphs satisfies |Et△Et−1|≤n2ζ0for all t∈[Tburn,T],|E_t E_t-1|≤ n^2 _0 all t∈[T_burn,T], where ζ0 ζ+Cζlog(nT/δ)n2+C′log(nT/δ)n2 _0 ζ+C ζ (nT/δ)n^2+ C (nT/δ)n^2 for absolute constants C,C′>0C,C >0. Proof C.11. Let m (n2)m n2 denote the total number of possible undirected edges. Define Ft |Et△Et−1|F_t |E_t E_t-1|, the number of flipped edges between rounds t−1t-1 and t. Under the edge–Markovian process in stationarity, each edge i,j\i,j\ evolves independently as a two-state Markov chain with transition matrix P=[1−αβ1−β].P= bmatrix1-α&α\\ β&1-β bmatrix. Thus, for any t, the random variables Xij,t≠Xij,t−1i<j\X_ij,t≠ X_ij,t-1\_i<j are independent Bernoulli variables, where the probability of a flip depends only on the stationary distribution. As shown in Appendix C.1.1, the expected number of flips is [Ft]=m⋅(α⋅(1−p∞)+β⋅p∞)=m⋅ζ,E[F_t]=m· (α·(1-p_∞)+β· p_∞ )=m·ζ, where p∞=α/(α+β)p_∞=α/(α+β) and ζ 2αβα+βζ 2αβα+β. Each Xij,t≠Xij,t−1X_ij,t≠ X_ij,t-1 is a Bernoulli variable in [0,1][0,1] with mean at most maxα,β≤1 \α,β\≤ 1. Applying a standard Bernstein-type inequality (or multiplicative Chernoff) for the sum of m independent bounded variables, we have: ℙ[Ft≥[Ft]+u]≤exp(−u22[Ft]+2u/3).P [F_t [F_t]+u ]≤ (- u^22E[F_t]+2u/3 ). We now set u=2mζlog(nT/δ)+23log(nT/δ)u= 2mζ (nT/δ)+ 23 (nT/δ) and obtain: ℙ[Ft≥mζ+2mζlog(nT/δ)+23log(nT/δ)]≤δ5nT.P [F_t≥ mζ+ 2mζ (nT/δ)+ 23 (nT/δ) ]≤ δ5nT. Applying a union bound over all t∈[Tburn,T]t∈[T_burn,T] (at most T values), the failure probability remains at most δ/5nδ/5n per node-pair, and hence: ℙ[∀t∈[Tburn,T],Ft≤mζ+2mζlog(nT/δ)+23log(nT/δ)]≥1−δ/5.P [∀ t∈[T_burn,T],\;F_t≤ mζ+ 2mζ (nT/δ)+ 23 (nT/δ) ]≥ 1-δ/5. We now divide both sides by n2n^2 to convert this to the normalized form: Ftn2≤mn2ζ⏟ζ+2mζlog(nT/δ)n2⏟first fluctuation+23⋅log(nT/δ)n2⏟second fluctuation. F_tn^2≤ mn^2ζ_ζ+ 2mζ (nT/δ)n^2_first fluctuation+ 23· (nT/δ)n^2_second fluctuation. Finally, defining: ζ0 ζ+Cζlog(nT/δ)n2+C′log(nT/δ)n2, _0 ζ+C ζ (nT/δ)n^2+ C (nT/δ)n^2, for suitable constants C,C′>0C,C >0, we obtain the desired result: Ft≤n2ζ0for all t∈[Tburn,T],F_t≤ n^2 _0 all t∈[T_burn,T], with probability at least 1−δ/51-δ/5. Bounding Node-Level Flip Concentration. While Lemma C.10 controls the total number of edge flips per round, our analysis of the kernel drift (Lemma C.18) requires a finer guarantee: we must also bound the number of flipped edges incident to any individual node. This ensures that no row of the walk kernel WtW_t undergoes a disproportionately large perturbation, which would otherwise dominate the Frobenius norm. We now establish a high-probability upper bound on the number of incident flips at any node i, uniformly over all rounds t∈[Tburn,T]t∈[T_burn,T]. The resulting bound will be expressed in terms of the same flip envelope ζ0 _0 introduced earlier, ensuring a consistent treatment of temporal variability in both global and local terms. Lemma C.12 (Max Node Flip Count). With probability at least 1−δ/51-δ/5, the number of edge flips incident to any node satisfies si:=|j:(i,j)∈Et△Et−1|≤Cnζ0,for all i∈[n],t∈[Tburn,T],s_i:=|\j:(i,j)∈ E_t E_t-1\|≤ Cn _0, all i∈[n],\;t∈[T_burn,T], where ζ0 _0 is the high-probability flip envelope from Lemma C.10 and C>0C>0 is an absolute constant. Proof C.13. Fix any node i∈[n]i∈[n] and time step t. Let si:=|j:(i,j)∈Et△Et−1|s_i:=|\j:(i,j)∈ E_t E_t-1\| denote the number of edges incident to node i that flipped between rounds t−1t-1 and t. Since each undirected edge i,j\i,j\ evolves independently and is flipped with probability at most ζ0 _0 (by Lemma C.10), the random variables Xij:=(i,j)∈Et△Et−1X_ij:=1_\(i,j)∈ E_t E_t-1\ are independent Bernoulli variables with means [Xij]≤ζ0E[X_ij]≤ _0. Hence si=∑j≠iXij,[si]≤(n−1)ζ0≤nζ0.s_i= _j≠ iX_ij, [s_i]≤(n-1) _0≤ n _0. Step 1. Chernoff bound per node. For any ϵ>0ε>0, the standard Chernoff inequality for sums of independent Bernoulli variables gives ℙ[si≥(1+ϵ)[si]]≤exp(−ϵ22+ϵ[si]).P\! [s_i≥(1+ε)\,E[s_i] ]≤ \! (- ε^22+ε\,E[s_i] ). Setting ϵ=1ε=1 yields ℙ[si≥2nζ0]≤exp(−nζ03).P\! [s_i≥ 2n _0 ]≤ \! (- n _03 ). Step 2. Union bound over all nodes and times. There are at most n nodes and T time steps (excluding burn‑in). By the union bound, ℙ[∃i,t with si≥2nζ0]≤nTexp(−nζ03).P\! [∃\,i,t with s_i≥ 2n _0 ]≤ nT \! (- n _03 ). To make this probability ≤δ/5≤δ/5, it suffices that nζ0≥3log(nT/δ).n _0≥ 3 (nT/δ). Step 3. Verifying the condition. By definition of ζ0 _0 in Lemma C.10, ζ0=ζ+Cζlog(nT/δ)n2+C′log(nT/δ)n2. _0=ζ+C ζ (nT/δ)n^2+ C (nT/δ)n^2. Hence nζ0≥nζ+Cζlog(nT/δ)+C′log(nT/δ)n,n _0≥ nζ+C ζ (nT/δ)+C (nT/δ)n, which dominates log(nT/δ) (nT/δ) for all sufficiently large n. Thus the above exponential tail bound ensures that ℙ[∃i,t:si≥2nζ0]≤δ5.P\! [∃\,i,t:s_i≥ 2n _0 ]≤ δ5. Step 4. Conclusion. Therefore, with probability at least 1−δ/51-δ/5, for all nodes i and all rounds t, si≤Cnζ0,s_i≤ Cn _0, for an absolute constant C>0C>0. C.2.3 Definition of the Typical Event We now define the event that will be assumed to hold in all subsequent analysis: Definition C.14 (ER–typical event). We define ℰtypE_typ as the event that all four properties in Lemma C.8 hold simultaneously for all t∈[Tburn,T]t∈[T_burn,T]. Then: [ℰtyp]≥1−δ/5. [E_typ ]≥ 1-δ/5. In the remainder of the analysis, we condition on the event ℰtypE_typ without further mention. All high-probability claims will account for this conditioning in the final failure budget. C.3 Spectral Gap Analysis of Agent’s Lazy Walk We now derive a uniform lower bound on the spectral gap γt _t of the lazy–walk kernel WtW_t for all t∈[Tburn,T]t∈[T_burn,T] under the typicality event ℰtypE_typ (Definition C.14). The argument proceeds through the conductance form of the Cheeger inequality and uses elementary concentration bounds to quantify the expansion of Erdős–Rényi graphs. Throughout this subsection, recall that p∞ α/(α+β)p_∞ α/(α+β) and that np∞≥C0log(nT/δ)np_∞≥ C_0 (nT/δ) under our standing assumptions from Lemma C.8. We will freely use the shorthand p∞↔α/(α+β)p_∞ α/(α+β) interchangeably when convenient. Analysis overview. We first express the Cheeger constant of the lazy walk in terms of the edge boundary size |∂GtS|| _G_tS| of subsets S⊆AS A. We then show via a Chernoff argument that for all S of moderate size, |∂GtS|| _G_tS| concentrates near its expectation [|∂GtS|]=(n−|S|)|S|p∞E[| _G_tS|]=(n-|S|)|S|p_∞, yielding a high–probability lower bound of the form |∂GtS|≥(1−η)|S|(n−|S|)p∞| _G_tS|≥(1-η)|S|(n-|S|)p_∞. Finally, substituting this expansion guarantee into the Cheeger inequality for reversible chains provides an explicit lower bound on γt _t. Lemma C.15 (Spectral Gap Lower Bound). Let the typicality event ℰtypE_typ of Definition C.14 hold, and assume that np∞≥C0log(nTδ)np_∞\;≥\;C_0 \! ( nTδ ) for a sufficiently large absolute constant C0>0C_0>0. Then, for all t∈[Tburn,T]t∈[T_burn,T], the lazy walk kernel WtW_t satisfies with high probability (at least 1−δ/51-δ/5 over the randomness of the graph sequence): γt 1−λ2(Wt)≥(1−η)28(1+1np∞), _t\; \;1- _2(W_t)\;≥\; (1-η)^28\! (1+ 1np_∞ ), where η∈(0,1)η∈(0,1) is a fixed constant determined by the concentration level of the expansion bound. Proof C.16. The proof proceeds in four steps. We condition on the event ℰtypE_typ holding. Step 1: Cheeger inequality for reversible chains. For any reversible Markov kernel WtW_t with stationary distribution πt _t (established in Lemma C.3), the spectral gap γt=1−λ2(Wt) _t=1- _2(W_t) satisfies γt≥ht22,ht minS⊂Aπt(S)∈(0,1/2]∑i∈S,j∉Sπt(i)Wt(i,j)πt(S). _t\;≥\; h_t^22, h_t\; \; _ subarraycS⊂ A\\ _t(S)∈(0,1/2] subarray _i∈ S,j∉ S _t(i)W_t(i,j) _t(S). Here, hth_t is the conductance (or Cheeger constant) of the chain. We have used the fact that minπt(S),πt(A∖S)=πt(S) \ _t(S), _t(A S)\= _t(S) by restricting the minimum to sets S with πt(S)≤1/2 _t(S)≤ 1/2. Step 2: Conductance expressed through the edge boundary. We first simplify the numerator of the conductance, Q(S,Sc) ∑i∈S,j∉Sπt(i)Wt(i,j)Q(S,S^c) _i∈ S,j∉ S _t(i)W_t(i,j). Using the definitions πt(i)=(dt(i)+1)/Zt _t(i)=(d_t(i)+1)/Z_t and Wt(i,j)=1/(dt(i)+1)W_t(i,j)=1/(d_t(i)+1) for (i,j)∈Et(i,j)∈ E_t: Q(S,Sc) Q(S,S^c) =∑i∈Sπt(i)∑j∉SWt(i,j)=∑i∈S(dt(i)+1Zt)∑j∉S(i,j)∈Et(1dt(i)+1) = _i∈ S _t(i) _j∉ SW_t(i,j)= _i∈ S ( d_t(i)+1Z_t ) _ subarraycj∉ S\\ (i,j)∈ E_t subarray ( 1d_t(i)+1 ) =∑i∈S1Zt∑j∉S(i,j)∈Et1=1Zt∑i∈S|j∉S:(i,j)∈Et| = _i∈ S 1Z_t _ subarraycj∉ S\\ (i,j)∈ E_t subarray1= 1Z_t _i∈ S|\\,j∉ S:(i,j)∈ E_t\,\| =|∂GtS|Zt, = | _G_tS|Z_t, where ∂GtS _G_tS is the set of edges with one endpoint in S and one in ScS^c. The denominator is πt(S)=∑i∈S(dt(i)+1)Zt _t(S)= _i∈ S(d_t(i)+1)Z_t. Substituting these into the expression for hth_t yields: ht=minS⊂Aπt(S)∈(0,1/2]|∂GtS|/Zt(∑i∈S(dt(i)+1))/Zt=minS⊂Aπt(S)∈(0,1/2]|∂GtS|∑i∈S(dt(i)+1).h_t\;=\; _ subarraycS⊂ A\\ _t(S)∈(0,1/2] subarray | _G_tS|/Z_t( _i∈ S(d_t(i)+1))/Z_t\;=\; _ subarraycS⊂ A\\ _t(S)∈(0,1/2] subarray | _G_tS| _i∈ S(d_t(i)+1). This shows the conductance of the lazy walk is equivalent to the conductance of a modified graph where each node i has weight dt(i)+1d_t(i)+1. Step 3: Concentration of edge boundaries. We now show that |∂GtS|| _G_tS| is large for all S. We analyze this under the stationary law ∞P_∞ (justified by Lemma C.6 and ℰtypE_typ). For a fixed subset S with |S|=s|S|=s, the number of possible edges between S and ScS^c is s(n−s)s(n-s). Under ∞P_∞, each edge exists independently with probability p∞p_∞. Thus, the boundary size |∂GtS|| _G_tS| is a binomial random variable: |∂GtS|∼Binomial(s(n−s),p∞).| _G_tS| (s(n-s),p_∞). The expectation is [|∂GtS|]=s(n−s)p∞E[| _G_tS|]=s(n-s)p_∞. Applying a standard Chernoff bound for any η∈(0,1)η∈(0,1): [|∂GtS|<(1−η)[|∂GtS|]]≤exp(−η2[|∂GtS|]2)=exp(−η2s(n−s)p∞2). \! [\,| _G_tS|<(1-η)\,E[| _G_tS|]\, ]≤ \! (- η^2\,E[| _G_tS|]2 )= \! (- η^2\,s(n-s)p_∞2 ). We must ensure this holds for all S and all t. We take a union bound. First, restrict to 1≤s=|S|≤n/21≤ s=|S|≤ n/2. In this range, s(n−s)≥1⋅(n−1)≥n/2s(n-s)≥ 1·(n-1)≥ n/2 (for n≥2n≥ 2). So, [|∂GtS|]≥np∞/2E[| _G_tS|]≥ np_∞/2. The failure probability for a single set S is at most exp(−η2np∞4) (- η^2np_∞4). We union bound over all ≈2n≈ 2^n possible subsets S and all T time steps: Pfail≤T⋅∑s=1⌊n/2⌋(ns)exp(−η2s(n−s)p∞2)≤T⋅2n⋅exp(−η2np∞4)P_fail≤ T· _s=1 n/2 ns \! (- η^2s(n-s)p_∞2 )≤ T· 2^n· \! (- η^2np_∞4 ) Pfail≤exp(logT+nlog2−η2np∞4)P_fail≤ \! ( T+n 2- η^2np_∞4 ) By our assumption np∞≥C0log(nT/δ)np_∞≥ C_0 (nT/δ), choosing C0C_0 large enough (e.g., C0>4(log2+1)/η2C_0>4( 2+1)/η^2) ensures the np∞np_∞ term dominates the nlog2n 2 and logT T terms, making the total failure probability less than δ/5δ/5. Thus, with probability at least 1−δ/51-δ/5, for all t∈[Tburn,T]t∈[T_burn,T] and all S with 1≤|S|≤n/21≤|S|≤ n/2: |∂GtS|≥(1−η)s(n−s)p∞.| _G_tS|\;≥\;(1-η)\,s(n-s)p_∞. (This also covers sets with |S|>n/2|S|>n/2 by considering their complements). Step 4: Substituting into the Cheeger constant. We now combine the bounds from Steps 2 and 3, using the explicit guarantees from the typicality event ℰtypE_typ (Lemma C.8) to replace the asymptotic arguments. Our goal is to find a uniform lower bound for hth_t as defined in (C.16): ht=minS⊂Aπt(S)∈(0,1/2]|∂GtS|∑i∈S(dt(i)+1).h_t\;=\; _ subarraycS⊂ A\\ _t(S)∈(0,1/2] subarray | _G_tS| _i∈ S(d_t(i)+1). We bound the numerator from below and the denominator from above. Let s=|S|s=|S|. We restrict our minimum to sets with 1≤s≤n/21≤ s≤ n/2, as the πt(S)≤1/2 _t(S)≤ 1/2 condition is guaranteed to include the minimizing set (or its complement), and ℰtypE_typ ensures πt(S) _t(S) is roughly proportional to s/ns/n. Numerator Lower Bound. From Step 3, (C.16), we have with high probability for all S with 1≤s≤n/21≤ s≤ n/2: |∂GtS|≥(1−ηc)s(n−s)p∞,| _G_tS|\;≥\;(1- _c)\,s(n-s)p_∞, where ηc∈(0,1) _c∈(0,1) is the constant from the Chernoff bound. Since s≤n/2s≤ n/2, we have n−s≥n/2n-s≥ n/2, which gives: |∂GtS|≥(1−ηc)s(n/2)p∞.| _G_tS|\;≥\;(1- _c)\,s(n/2)p_∞. Denominator Upper Bound. From ℰtypE_typ (Lemma 4, (i)), we have a uniform bound on the maximum degree. Let ℒ=log(nT/δ)L= (nT/δ). The lemma states: dt(i)≤(n−1)p∞+c1np∞ℒ.d_t(i)\;≤\;(n-1)p_∞+c_1 np_∞L. Using the assumption np∞≥C0ℒnp_∞≥ C_0L, which implies ℒ≤np∞/C0L≤ np_∞/C_0, we can write: np∞ℒ≤np∞⋅(np∞/C0)=np∞C0. np_∞L\;≤\; np_∞·(np_∞/C_0)= np_∞ C_0. Substituting this back into the degree bound: dt(i)≤(n−1)p∞+c1C0np∞≤np∞+c1C0np∞=np∞(1+c1C0).d_t(i)\;≤\;(n-1)p_∞+ c_1 C_0np_∞\;≤\;np_∞+ c_1 C_0np_∞=np_∞ (1+ c_1 C_0 ). Let ϵd=c1/C0 _d=c_1/ C_0. By assuming C0C_0 in Lemma 4 is sufficiently large, we can make ϵd _d an arbitrarily small positive constant (e.g., ϵd≤1 _d≤ 1). Now we can bound the denominator term: ∑i∈S(dt(i)+1) _i∈ S(d_t(i)+1) ≤∑i∈S(np∞(1+ϵd)+1) \;≤\; _i∈ S(np_∞(1+ _d)+1) =s⋅(np∞(1+ϵd)+1). \;=\;s·(np_∞(1+ _d)+1). Combining the Bounds. We substitute these bounds into the expression for hth_t: ht h_t ≥min1≤s≤n/2(1−ηc)s(n/2)p∞s⋅(np∞(1+ϵd)+1) \;≥\; _1≤ s≤ n/2 (1- _c)s(n/2)p_∞s·(np_∞(1+ _d)+1) =(1−ηc)(n/2)p∞np∞(1+ϵd)+1 = (1- _c)(n/2)p_∞np_∞(1+ _d)+1 (Cancel s) =(1−ηc)np∞2(np∞(1+ϵd)+1) = (1- _c)np_∞2(np_∞(1+ _d)+1) =(1−ηc)2(1+ϵd+1/(np∞)). = (1- _c)2(1+ _d+1/(np_∞)). (Divide num/den by np∞np_∞) Now, let the constant η∈(0,1)η∈(0,1) in the lemma’s final statement be defined as η=1−1−ηc1+ϵdη=1- 1- _c1+ _d. Since ηc _c is a fixed constant and ϵd _d is a small positive constant, η is also a fixed constant in (0,1)(0,1). This gives: ht≥(1−η)(1+ϵd)2(1+ϵd+1/(np∞))=1−η2(1+1np∞(1+ϵd)).h_t\;≥\; (1-η)(1+ _d)2(1+ _d+1/(np_∞))= 1-η2 (1+ 1np_∞(1+ _d) ). Since 1+ϵd≥11+ _d≥ 1, we have np∞(1+ϵd)≥np∞np_∞(1+ _d)≥ np_∞, which implies 1np∞(1+ϵd)≤1np∞ 1np_∞(1+ _d)≤ 1np_∞. This gives us the final, clean lower bound on the conductance: ht≥1−η2(1+1/(np∞)).h_t\;≥\; 1-η2(1+1/(np_∞)). Applying the Cheeger Inequality. Finally, we apply the Cheeger inequality (C.16): γt≥ht22≥12(1−η2(1+1/(np∞)))2 _t\;≥\; h_t^22\;≥\; 12 ( 1-η2(1+1/(np_∞)) )^2 γt≥(1−η)28(1+1np∞)2. _t\;≥\; (1-η)^28 (1+ 1np_∞ )^2. This proves the lemma (noting the squared denominator, which is a rigorous consequence of γ≥h2/2γ≥ h^2/2). Corollary C.17 (Simplified constant-gap regime). Under the same conditions as Lemma C.15, if np∞np_∞ is sufficiently large (e.g., np∞≥1np_∞≥ 1), then 1np∞≤1 1np_∞≤ 1 and hence 1+1np∞≤21+ 1np_∞≤ 2. This gives: γt≥(1−η)28⋅(2)=(1−η)216 γ0for all t∈[Tburn,T]. _t\;≥\; (1-η)^28·(2)= (1-η)^216 _0 all t∈[T_burn,T]. In particular, the spectral gap is bounded below by an absolute constant γ0=Ω(1) _0= (1), ensuring that the lazy walk mixes in O(log(n))O( (n)) steps. This uniform lower bound γ0 _0 will be used throughout the remainder of the analysis to control the rate at which the walk distribution tracks the instantaneous stationary law. The near-constant value of γ0 _0 reflects that under typical ER connectivity (average degree Θ(np∞) (np_∞)), the lazy random walk mixes rapidly in each round, a property that remains stable under the slow structural drift of the edge–Markovian process. C.4 Kernel Drift and Stationary Distribution Drift Lemma C.18 (Kernel Drift under Typicality). Let the static typicality event ℰtypE_typ (Definition C.14) hold, and suppose the high-probability flip bounds from Lemma C.10 (for ζ0 _0) and Lemma C.12 (for si(t)s_i(t)) also hold. Then for all t∈[Tburn,T]t∈[T_burn,T], the spectral norm of the kernel difference satisfies: κt ‖Wt−Wt−1‖2≤C(ζ0p∞+ζ0p∞3/2), _t \|W_t-W_t-1\|_2≤ C ( _0p_∞+ _0p_∞^3/2 ), where C is an absolute constant, ζ0 _0 is the high-probability flip envelope, and p∞=α/(α+β)p_∞=α/(α+β) is the stationary edge density. Proof C.19. The proof proceeds by bounding the Frobenius norm, which is an upper bound on the spectral (operator) norm: ‖Wt−Wt−1‖2≤‖Wt−Wt−1‖F=(∑i=1n‖Wt(i,⋅)−Wt−1(i,⋅)‖22)1/2.\|W_t-W_t-1\|_2≤\|W_t-W_t-1\|_F= ( _i=1^n\|W_t(i,·)-W_t-1(i,·)\|_2^2 )^1/2. Let si(t) |j:(i,j)∈Et△Et−1|s_i(t) |\j:(i,j)∈ E_t E_t-1\| be the number of incident flips at node i at time t, and let Di(t) mindt(i)+1,dt−1(i)+1,D_i(t) \d_t(i)+1,\,d_t-1(i)+1\, denote the minimal lazy-walk denominator at node i across the two time steps. As derived from the definition of WtW_t, the per-row squared ℓ2 _2-distance is bounded by the sum of contributions from changed and unchanged neighbor sets: ‖Wt(i,⋅)−Wt−1(i,⋅)‖22≤si(t)Di(t)2+si(t)2Di(t)3.\|W_t(i,·)-W_t-1(i,·)\|_2^2≤ s_i(t)D_i(t)^2+ s_i(t)^2D_i(t)^3. Summing over all n rows gives the squared Frobenius norm bound: ‖Wt−Wt−1‖F2≤∑i=1n(si(t)Di(t)2+si(t)2Di(t)3).\|W_t-W_t-1\|_F^2≤ _i=1^n ( s_i(t)D_i(t)^2+ s_i(t)^2D_i(t)^3 ). We now bound the two terms in this sum separately, conditioned on our combined high-probability event. Uniform Degree Lower Bound. We first establish a uniform lower bound on Di(t)D_i(t) derived from the static typicality event ℰtypE_typ (Lemma C.8). From Lemma C.8(i) (Degree concentration), we have for all i,ti,t: |dt(i)−(n−1)p∞|≤c1np∞log(nT/δ) ϵn.|d_t(i)-(n-1)p_∞|≤ c_1 np_∞ (nT/δ) _n. The assumption in Lemma C.8, np∞≥C0log(nT/δ)np_∞≥ C_0 (nT/δ), implies that the deviation ϵn _n is bounded relative to the mean: ϵn≤c1C0np∞. _n≤ c_1 C_0np_∞. By ensuring C0C_0 in our typicality assumption is sufficiently large (e.g., C0≥(2c1)2C_0≥(2c_1)^2), we guarantee ϵn≤12np∞ _n≤ 12np_∞. This gives a uniform lower bound on the degree: dt(i)≥(n−1)p∞−ϵn≥(n−1)p∞−12np∞=(12n−1)p∞.d_t(i)≥(n-1)p_∞- _n≥(n-1)p_∞- 12np_∞= ( 12n-1 )p_∞. For n≥4n≥ 4, this implies dt(i)≥14np∞d_t(i)≥ 14np_∞. Thus, for some absolute constant c0>0c_0>0 (e.g., c0=1/4c_0=1/4), we have dt(i)+1≥c0np∞d_t(i)+1≥ c_0np_∞ for all i,ti,t. This implies the minimal denominator is also bounded: Di(t)=mindt(i)+1,dt−1(i)+1≥c0np∞.D_i(t)= \d_t(i)+1,\,d_t-1(i)+1\≥ c_0np_∞. Bounding the Linear Term. We use the uniform denominator bound Di(t)≥c0np∞D_i(t)≥ c_0np_∞ on the first sum: ∑i=1nsi(t)Di(t)2≤1(c0np∞)2∑i=1nsi(t). _i=1^n s_i(t)D_i(t)^2≤ 1(c_0np_∞)^2 _i=1^ns_i(t). The sum of incident flips is exactly twice the total number of flipped edges, Ft |Et△Et−1|F_t |E_t E_t-1|: ∑i=1nsi(t)=2Ft. _i=1^ns_i(t)=2F_t. From Lemma C.10, we have the high-probability bound Ft≤n2ζ0F_t≤ n^2 _0. Substituting this in: ∑i=1nsi(t)Di(t)2≤2n2ζ0c02n2p∞2=2ζ0c02p∞2. _i=1^n s_i(t)D_i(t)^2≤ 2n^2 _0c_0^2n^2p_∞^2= 2 _0c_0^2p_∞^2. Bounding the Quadratic Term. We apply the uniform bounds on both si(t)s_i(t) and Di(t)D_i(t) to the second sum: ∑i=1nsi(t)2Di(t)3≤∑i=1n(maxjsj(t))2(c0np∞)3. _i=1^n s_i(t)^2D_i(t)^3≤ _i=1^n ( _js_j(t))^2(c_0np_∞)^3. Using the high-probability bound from Lemma C.12, si(t)≤C1nζ0s_i(t)≤ C_1n _0 for all i: ∑i=1nsi(t)2Di(t)3≤∑i=1n(C1nζ0)2(c0np∞)3=n⋅(C12n2ζ02c03n3p∞3). _i=1^n s_i(t)^2D_i(t)^3≤ _i=1^n (C_1n _0)^2(c_0np_∞)^3=n· ( C_1^2n^2 _0^2c_0^3n^3p_∞^3 ). The sum over n identical terms gives: ∑i=1nsi(t)2Di(t)3≤C12n3ζ02c03n3p∞3=C12ζ02c03p∞3. _i=1^n s_i(t)^2D_i(t)^3≤ C_1^2n^3 _0^2c_0^3n^3p_∞^3= C_1^2 _0^2c_0^3p_∞^3. Combining and Final Result. We combine the bounds for the linear and quadratic terms: ‖Wt−Wt−1‖F2≤2ζ0c02p∞2+C12ζ02c03p∞3.\|W_t-W_t-1\|_F^2≤ 2 _0c_0^2p_∞^2+ C_1^2 _0^2c_0^3p_∞^3. Taking the square root and using the inequality a+b≤a+b a+b≤ a+ b, we get: ‖Wt−Wt−1‖2≤‖Wt−Wt−1‖F \|W_t-W_t-1\|_2≤\|W_t-W_t-1\|_F ≤2ζ0c02p∞2+C12ζ02c03p∞3 ≤ 2 _0c_0^2p_∞^2+ C_1^2 _0^2c_0^3p_∞^3 =2c0ζ0p∞+C1c03/2ζ0p∞3/2. = 2c_0 _0p_∞+ C_1c_0^3/2 _0p_∞^3/2. By collecting all absolute constants (c0,2,C1c_0, 2,C_1) into a single constant C>0C>0, we arrive at the final bound: ‖Wt−Wt−1‖2≤C(ζ0p∞+ζ0p∞3/2).\|W_t-W_t-1\|_2≤ C ( _0p_∞+ _0p_∞^3/2 ). This holds with high probability, as it is conditioned on the typicality events ℰtypE_typ, Lemma C.10, and Lemma C.12. Bounding Stationary Drift. To quantify how closely the distribution of the walk aligns with the time-varying stationary laws, we must control the drift of the stationary distributions πt\ _t\ themselves. Specifically, we require a uniform upper bound on the total variation distance εt ‖πt+1−πt‖TV _t \| _t+1- _t\|_TV in order to analyze the deviation of the walk marginal μt _t from its local equilibrium. We first derive a baseline upper bound on εt _t in terms of the number of flipped edges per round, based on the explicit form of the natural lazy-walk stationary distribution. We then obtain a tighter and more elegant bound by invoking perturbation theory for lazy reversible chains, which allows us to relate εt _t directly to the kernel drift norm κ=‖Wt+1−Wt‖2κ=\|W_t+1-W_t\|_2. The latter result will be used as the primary input to our contraction analysis in the tracking recursion. Lemma C.20 (Stationary Distribution Drift). Under the ER-typical event ℰtypE_typ (Definition 5) and the high-probability flip bound from Lemma C.10, the stationary distributions πt _t satisfy the uniform bound εt ‖πt+1−πt‖TV≤Cζ0p∞for all t∈[Tburn,T], _t \| _t+1- _t\|_TV≤ C _0p_∞ all t∈[T_burn,T], with high probability, where ζ0 _0 is the high-probability flip envelope and C>0C>0 is an absolute constant. We thus define the uniform drift bound as εmax supεt≤Cζ0p∞. _ _t≤ C _0p_∞. Proof C.21. Let πt _t and πt+1 _t+1 be the stationary distributions for WtW_t and Wt+1W_t+1, respectively. πt(i)=degt(i)+1Zt,where Zt=2|Et|+n. _t(i)= _t(i)+1Z_t, Z_t=2|E_t|+n. The total variation distance is one-half of the L1L_1 distance. We bound the L1L_1 distance using the triangle inequality by introducing a hybrid term π′(i)=(degt(i)+1)/Zt+1π (i)=( _t(i)+1)/Z_t+1: 2εt 2 _t =2‖πt+1−πt‖TV=∑i=1n|πt+1(i)−πt(i)| =2\| _t+1- _t\|_TV= _i=1^n | _t+1(i)- _t(i) | ≤∑i=1n|πt+1(i)−π′(i)|+∑i=1n|π′(i)−πt(i)| ≤ _i=1^n | _t+1(i)-π (i) |+ _i=1^n |π (i)- _t(i) | =∑i=1n|degt+1(i)+1Zt+1−degt(i)+1Zt+1|⏟(a) Bounding the degree change+∑i=1n|degt(i)+1Zt+1−degt(i)+1Zt|⏟(b) Bounding the denominator shift. = _i=1^n | _t+1(i)+1Z_t+1- _t(i)+1Z_t+1 |_(a) Bounding the degree change+ _i=1^n | _t(i)+1Z_t+1- _t(i)+1Z_t |_(b) Bounding the denominator shift. We now bound these two terms, conditioned on our high-probability typicality events. Let Ft |Et+1△Et|F_t |E_t+1 E_t| be the number of flipped edges. Under ℰtypE_typ, we have Zt,Zt+1≥Zmin≥czn2p∞Z_t,Z_t+1≥ Z_ ≥ c_zn^2p_∞ for some cz>0c_z>0. (a) Bounding the degree change. The first term simplifies by factoring out the common denominator Zt+1Z_t+1: Term (a)=1Zt+1∑i=1n|degt+1(i)−degt(i)|≤1Zmin∑i=1n|degt+1(i)−degt(i)|.Term (a)= 1Z_t+1 _i=1^n| _t+1(i)- _t(i)|≤ 1Z_ _i=1^n| _t+1(i)- _t(i)|. The change in degree for a node i is at most the number of incident flips, si(t)s_i(t). Summing over all nodes, we have ∑isi(t)=2Ft _is_i(t)=2F_t. Thus: Term (a)≤1Zmin(2Ft)=2FtZmin.Term (a)≤ 1Z_ (2F_t)= 2F_tZ_ . (b) Bounding the denominator shift. The second term simplifies by factoring out the common numerator (degt(i)+1)( _t(i)+1): Term (b)=|1Zt+1−1Zt|∑i=1n(degt(i)+1)=|1Zt+1−1Zt|⋅Zt.Term (b)= | 1Z_t+1- 1Z_t | _i=1^n( _t(i)+1)= | 1Z_t+1- 1Z_t |· Z_t. We bound the difference of the reciprocals: |1Zt+1−1Zt|=|Zt−Zt+1|ZtZt+1≤|Zt−Zt+1|Zmin2. | 1Z_t+1- 1Z_t |= |Z_t-Z_t+1|Z_tZ_t+1≤ |Z_t-Z_t+1|Z_ ^2. The change in the normalization constant is |Zt+1−Zt|=2||Et+1|−|Et|||Z_t+1-Z_t|=2||E_t+1|-|E_t||. This net change is at most the total number of flips, so |Zt+1−Zt|≤2Ft|Z_t+1-Z_t|≤ 2F_t. Substituting this in: Term (b)≤2FtZmin2⋅Zt≤2FtZmin2⋅Zmax.Term (b)≤ 2F_tZ_ ^2· Z_t≤ 2F_tZ_ ^2· Z_ . Under ℰtypE_typ, Zmax≍n2p∞≍ZminZ_ n^2p_∞ Z_ . Thus, Zmax/Zmin2≤C/ZminZ_ /Z_ ^2≤ C/Z_ for some C. Term (b)≤C′FtZmin.Term (b)≤ C F_tZ_ . (c) Combining bounds. Adding the two terms, we find the L1L_1 distance is bounded: 2εt≤2FtZmin+C′FtZmin≤CFtZmin,2 _t≤ 2F_tZ_ + C F_tZ_ ≤ CF_tZ_ , for a new absolute constant C. Finally, we substitute our high-probability bounds. From Lemma C.10, Ft≤n2ζ0F_t≤ n^2 _0. From ℰtypE_typ, Zmin≥czn2p∞Z_ ≥ c_zn^2p_∞. εt=12(2εt)≤CFt2Zmin≤C(n2ζ0)2(czn2p∞)=(C2cz)ζ0p∞. _t= 12(2 _t)≤ CF_t2Z_ ≤ C(n^2 _0)2(c_zn^2p_∞)= ( C2c_z ) _0p_∞. Absorbing all constants into a single C′C , we achieve the final bound: εt≤C′ζ0p∞. _t≤ C _0p_∞. This holds uniformly for all t∈[Tburn,T]t∈[T_burn,T] with high probability. Tracking the Walk Marginal. Having bounded the kernel drift and stationary distribution drift across time, we now turn to analyzing how closely the marginal distribution μt _t of the random walk aligns with its time-varying stationary distribution πt _t. Since the underlying graph process is dynamic, the walk never fully mixes to any fixed π; however, if the temporal variation is sufficiently slow, the walk can still approximately track the evolving stationary law. To formalize this, we define the deviation dt ‖μt−πt‖TVd_t \| _t- _t\|_TV and derive a recursive inequality that bounds dt+1d_t+1 in terms of dtd_t and the stationary drift εt ‖πt+1−πt‖TV _t \| _t+1- _t\|_TV. The recursion reflects the dual forces at play: contraction under the lazy-walk dynamics, and drift induced by changes in the underlying graph. This recursion forms the backbone of our tracking and visitation guarantees. C.5 TV Drift Recursion, One-Step Contraction and Its Solution We now analyze how the distribution νt _t of the learner’s position evolves over time compared to the stationary distribution πt _t of the lazy walk kernel WtW_t. The aim is to show that even though the kernels vary across rounds, the deviation ‖νt−πt‖TV\| _t- _t\|_TV remains small after sufficient steps, due to the contraction properties of the walk and the bounded drift in the stationary law. We begin with the following key one-step recursion: Lemma C.22 (TV Recursion with Kernel and Stationary Drift). Let νt _t denote the distribution of the learner’s location at round t, and let πt _t be the stationary distribution of the lazy‑walk kernel WtW_t. Then for all t≥Tburnt≥ T_burn, ‖νt+1−πt+1‖TV≤(1−γ0)‖νt−πt‖TV+εt,\| _t+1- _t+1\|_TV≤(1- _0)\,\| _t- _t\|_TV+ _t, where γt≥γ0 _t≥ _0 is a uniform lower bound on the spectral gaps of Wt\W_t\, and εt:=‖πt+1−πt‖TV _t:=\| _t+1- _t\|_TV is the stationary‑law drift. Proof C.23. We start from the decomposition ‖νt+1−πt+1‖TV≤‖νtWt−πtWt‖TV+‖πtWt−πt+1‖TV.\| _t+1- _t+1\|_TV≤\| _tW_t- _tW_t\|_TV+\| _tW_t- _t+1\|_TV. The second term equals εt _t because πtWt=πt _tW_t= _t. We therefore focus on the contraction term ‖νtWt−πtWt‖TV\| _tW_t- _tW_t\|_TV. Step 1. Express the deviation through a mean‑zero function. Define the relative‑density perturbation ht(i):=νt(i)πt(i)−1h_t(i):= _t(i) _t(i)-1, so that ∑iπt(i)ht(i)=0 _i _t(i)h_t(i)=0 and νt(i)=πt(i)[1+ht(i)]. _t(i)= _t(i)\,[1+h_t(i)]. Then, for any node j, (νtWt−πt)(j) ( _tW_t- _t)(j) =∑iνt(i)Wt(i,j)−∑iπt(i)Wt(i,j) = _i _t(i)W_t(i,j)- _i _t(i)W_t(i,j) =∑iπt(i)ht(i)Wt(i,j). = _i _t(i)h_t(i)W_t(i,j). Step 2. Use detailed balance to move WtW_t to the right. Because WtW_t is reversible with respect to πt _t, πt(i)Wt(i,j)=πt(j)Wt(j,i) _t(i)W_t(i,j)= _t(j)W_t(j,i). Hence ∑iπt(i)ht(i)Wt(i,j)=πt(j)∑iht(i)Wt(j,i)=πt(j)[Wtht](j), _i _t(i)h_t(i)W_t(i,j)= _t(j) _ih_t(i)W_t(j,i)= _t(j)\,[W_th_t](j), where (Wtht)(j):=∑iWt(j,i)ht(i)(W_th_t)(j):= _iW_t(j,i)h_t(i) is the usual action of the kernel on a column vector. Therefore, νtWt−πt=πt⊙(Wtht), _tW_t- _t= _t (W_th_t), where ⊙ denotes entrywise product. Step 3. Relate total variation to an L2(πt)L^2( _t) norm. The total variation distance can now be written as ‖νtWt−πt‖TV=12∑jπt(j)|(Wtht)(j)|.\| _tW_t- _t\|_TV= 12 _j _t(j)\,|(W_th_t)(j)|. Apply Cauchy–Schwarz with weights πt(j) _t(j): ∑jπt(j)|xj|≤(∑jπt(j)xj2)1/2, _j _t(j)|x_j|≤ ( _j _t(j)x_j^2 )^1/2, to obtain ‖νtWt−πt‖TV≤12‖Wtht‖2(πt),\| _tW_t- _t\|_TV≤ 12\,\|W_th_t\|_2( _t), where ‖v‖2(πt):=(∑jπt(j)v(j)2)1/2\|v\|_2( _t):=( _j _t(j)v(j)^2)^1/2. Step 4. Apply spectral contraction in L2(πt)L^2( _t). For any mean‑zero function g, reversibility implies that WtW_t is self‑adjoint in L2(πt)L^2( _t) and satisfies ‖Wtg‖2(πt)≤(1−γt)‖g‖2(πt).\|W_tg\|_2( _t)≤(1- _t)\,\|g\|_2( _t). Since hth_t has ∑iπt(i)ht(i)=0 _i _t(i)h_t(i)=0, we may apply this with g=htg=h_t: ‖Wtht‖2(πt)≤(1−γt)‖ht‖2(πt).\|W_th_t\|_2( _t)≤(1- _t)\,\|h_t\|_2( _t). Substituting into the previous inequality gives ‖νtWt−πt‖TV≤12(1−γt)‖ht‖2(πt).\| _tW_t- _t\|_TV≤ 12(1- _t)\,\|h_t\|_2( _t). Step 5. Relate ‖ht‖2(πt)\|h_t\|_2( _t) back to total variation. Again by Cauchy–Schwarz, ‖νt−πt‖TV=12∑iπt(i)|ht(i)|≤12‖ht‖2(πt).\| _t- _t\|_TV= 12 _i _t(i)|h_t(i)|≤ 12\|h_t\|_2( _t). Combining the two displays yields ‖νtWt−πt‖TV≤(1−γt)‖νt−πt‖TV.\| _tW_t- _t\|_TV≤(1- _t)\,\| _t- _t\|_TV. Step 6. Add the stationary‑law drift. Finally, ‖νt+1−πt+1‖TV≤(1−γt)‖νt−πt‖TV+εt.\| _t+1- _t+1\|_TV≤(1- _t)\,\| _t- _t\|_TV+ _t. Using γt≥γ0 _t≥ _0 completes the proof. This completes the derivation of the fundamental one‑step recursion. It shows that the total‑variation deviation between the learner’s marginal and the instantaneous stationary law contracts multiplicatively by (1−γ0)(1- _0) at each step, up to an additive perturbation εt _t arising from the gradual evolution of the graph sequence. In the following subsection we unroll this recursion over the exploration window, derive a closed‑form bound on ‖νt−πt‖TV\| _t- _t\|_TV, and then use it to obtain a uniform lower bound on visitation frequencies. Corollary C.24 (Iterated Contraction Bound). The one-step recursive inequality from Lemma C.22 implies the following explicit bound for the tracking error for all t≥1t≥ 1: ‖νt−πt‖TV≤(1−γ0)t−1+εmaxγ0\| _t- _t\|_TV≤(1- _0)^t-1+ _ _0 This bound separates the exponentially decaying initial error from the asymptotic error floor, d∞ εmax/γ0d_∞ _ / _0. Proof C.25. From Lemma C.22, we have the recursive inequality ‖νt+1−πt+1‖TV≤(1−γ0)‖νt−πt‖TV+εt\| _t+1- _t+1\|_TV≤(1- _0)\| _t- _t\|_TV+ _t. Using the uniform drift bound εmax _ from Lemma C.20 (which holds for t≥Tburnt≥ T_burn), we can write the simpler recursion: ‖νt+1−πt+1‖TV≤(1−γ0)‖νt−πt‖TV+εmax,for all t≥Tburn.\| _t+1- _t+1\|_TV≤(1- _0)\| _t- _t\|_TV+ _ , all t≥ T_burn. We prove the corollary by unrolling this recurrence. Step 1. Unroll the recurrence. We expand the inequality step-by-step to establish the pattern: For t=1: t=1: ‖ν1−π1‖TV \| _1- _1\|_TV For t=2: t=2: ‖ν2−π2‖TV≤(1−γ0)‖ν1−π1‖TV+εmax \| _2- _2\|_TV≤(1- _0)\| _1- _1\|_TV+ _ For t=3: t=3: ‖ν3−π3‖TV≤(1−γ0)‖ν2−π2‖TV+εmax \| _3- _3\|_TV≤(1- _0)\| _2- _2\|_TV+ _ ≤(1−γ0)[(1−γ0)‖ν1−π1‖TV+εmax]+εmax \| _3- _3\|_TV≤(1- _0) [(1- _0)\| _1- _1\|_TV+ _ ]+ _ =(1−γ0)2‖ν1−π1‖TV+(1−γ0)εmax+εmax \| _3- _3\|_TV=(1- _0)^2\| _1- _1\|_TV+(1- _0) _ + _ For t=4: t=4: ‖ν4−π4‖TV≤(1−γ0)‖ν3−π3‖TV+εmax \| _4- _4\|_TV≤(1- _0)\| _3- _3\|_TV+ _ ≤(1−γ0)[(1−γ0)2‖ν1−π1‖TV+(1−γ0)εmax+εmax]+εmax \| _4- _4\|_TV≤(1- _0) [(1- _0)^2\| _1- _1\|_TV+(1- _0) _ + _ ]+ _ =(1−γ0)3‖ν1−π1‖TV+(1−γ0)2εmax+(1−γ0)εmax+εmax \| _4- _4\|_TV=(1- _0)^3\| _1- _1\|_TV+(1- _0)^2 _ +(1- _0) _ + _ By induction, this establishes the general form for any t≥1t≥ 1: ‖νt−πt‖TV≤(1−γ0)t−1‖ν1−π1‖TV+εmax∑k=0t−2(1−γ0)k.\| _t- _t\|_TV≤(1- _0)^t-1\| _1- _1\|_TV+ _ _k=0^t-2(1- _0)^k. Step 2. Bound the initial condition. The initial distribution ν1 _1 and the stationary distribution π1 _1 are both probability distributions over the same finite set A. The total variation distance between any two such distributions is bounded by 1. Therefore: ‖ν1−π1‖TV≤1.\| _1- _1\|_TV≤ 1. Step 3. Sum the geometric series. The second term is a finite geometric series with t−1t-1 terms (for t≥2t≥ 2), first term a=εmaxa= _ , and ratio r=(1−γ0)r=(1- _0). εmax∑k=0t−2(1−γ0)k=εmax(1−(1−γ0)t−11−(1−γ0))=εmaxγ0(1−(1−γ0)t−1). _ _k=0^t-2(1- _0)^k= _ ( 1-(1- _0)^t-11-(1- _0) )= _ _0 (1-(1- _0)^t-1 ). Step 4. Combine terms. Substituting the bounds from Steps 2 and 3 into the unrolled expression from Step 1 gives the exact form of the bound: ‖νt−πt‖TV≤(1−γ0)t−1⋅1+εmaxγ0(1−(1−γ0)t−1).\| _t- _t\|_TV≤(1- _0)^t-1· 1+ _ _0 (1-(1- _0)^t-1 ). A simpler, looser bound is obtained by noting that (1−(1−γ0)t−1)≤1(1-(1- _0)^t-1)≤ 1 for all t≥1t≥ 1: ‖νt−πt‖TV≤(1−γ0)t−1+εmaxγ0.\| _t- _t\|_TV≤(1- _0)^t-1+ _ _0. This form usefully separates the transient error (the first term, which decays to 0) from the steady-state error floor (the second term). C.6 Uniform Visitation Guarantees In the previous sections, we established the fundamental dynamic properties of the learner’s lazy random walk. We have shown that under the typicality event ℰallE_all, the walk kernel WtW_t has a uniform spectral gap γ0>0 _0>0 (Lemma C.15) and its stationary distribution πt _t drifts by at most εmax _ per step (Lemma C.20). Corollary C.24 combined these results to show that the learner’s distribution, νt _t, exponentially converges to the (drifting) stationary distribution, πt _t, up to a small asymptotic error floor ∝εmax/γ0 _ / _0. While this tracking guarantee is a powerful theoretical tool, our bandit algorithm requires a more concrete assurance: that the learner actually visits every arm a sufficient number of times during the exploration phase. The purpose of this section is to translate our abstract total variation bound into a high-probability lower bound on the realized visitation count for every arm. The following lemma formalizes this by combining the deterministic bound on the expected visitations (derived from the TV tracking) with a high-probability concentration bound (derived from a martingale inequality) for the random component of the walk. Lemma C.26 (Uniform Visitation Lower Bound). Let ℰallE_all be the high-probability event (holding with probability ≥1−4δ/5≥ 1-4δ/5) that the guarantees from ℰtypE_typ (Definition C.14), Lemma C.15 (for γ0 _0), and Lemma C.20 (for εmax _ ) all hold. Let π0 _0 be the uniform lower bound on πt(a) _t(a) from ℰtypE_typ. Define the effective minimal visitation probability as: πeff π0−2εmaxγ0. _eff _0- 2 _ _0. Then, conditioned on ℰallE_all, for any exploration length Texp≥1T_ ≥ 1, the total visitation count ϕTexp(a) _T_ (a) satisfies the following inequality simultaneously for all arms a∈Aa∈ A with probability at least 1−δ/51-δ/5 (over the exploration randomness): ϕTexp(a)≥Texp⋅πeff−2γ0−(2Texplog(5n/δ)+23log(5n/δ)). _T_ (a)\;≥\;T_ · _eff- 2 _0- ( 2T_ (5n/δ)+ 23 (5n/δ) ). (2) Proof C.27. The proof proceeds by decomposing the visitation count for a fixed arm a into its expectation and a deviation term (a martingale sum), and then bounding each component. Part 1. Decomposition of the Visitation Count. We define the total visitation count for arm a as ϕTexp(a) ∑t=1Texpat=a _T_ (a) _t=1^T_ 1\a_t=a\. Let νt _t be the law (i.e., the probability distribution over A) of the learner’s location at time t. We are interested in its components, νt(a) (at=a) _t(a) (a_t=a), which is the marginal probability of visiting arm a at time t. By linearity of expectation, the expected total visitation count is: [ϕTexp(a)]=[∑t=1Texpat=a]=∑t=1Texp[at=a]=∑t=1Texpνt(a).E[ _T_ (a)]=E [ _t=1^T_ 1\a_t=a\ ]= _t=1^T_ E[1\a_t=a\]= _t=1^T_ _t(a). We can therefore decompose the visitation count as the sum of its expectation and a zero-mean deviation term: ϕTexp(a)=∑t=1Texpνt(a)⏟Predictable Sum (Expectation)+∑t=1Texp(at=a−νt(a))⏟Martingale Difference Sum. _T_ (a)= _t=1^T_ _t(a)_Predictable Sum (Expectation)+ _t=1^T_ (1\a_t=a\- _t(a) )_Martingale Difference Sum. Our strategy is to find a uniform lower bound for the predictable sum and show that the martingale difference sum concentrates sharply around its mean of zero. Part 2. Lower Bound on the Predictable Sum. This term is the expected total visitations, [ϕTexp(a)]E[ _T_ (a)]. We lower-bound each νt(a) _t(a). By the definition of total variation distance, the difference at a single coordinate is bounded by the L1L_1 distance, which is 2∥⋅∥TV2\|·\|_TV: |νt(a)−πt(a)|≤‖νt−πt‖1=2‖νt−πt‖TV.| _t(a)- _t(a)|≤\| _t- _t\|_1=2\| _t- _t\|_TV. Conditioned on ℰallE_all, we have the uniform stationary floor πt(a)≥π0 _t(a)≥ _0 for all t,at,a. νt(a)=πt(a)−(πt(a)−νt(a))≥πt(a)−|πt(a)−νt(a)|≥π0−2‖νt−πt‖TV. _t(a)= _t(a)-( _t(a)- _t(a))≥ _t(a)-| _t(a)- _t(a)|≥ _0-2\| _t- _t\|_TV. We now substitute the iterated contraction bound from Corollary C.24: νt(a)≥π0−2((1−γ0)t−1+εmaxγ0). _t(a)≥ _0-2 ((1- _0)^t-1+ _ _0 ). Summing this from t=1t=1 to TexpT_ : ∑t=1Texpνt(a) _t=1^T_ _t(a) ≥∑t=1Texp(π0−2εmaxγ0)−∑t=1Texp2(1−γ0)t−1 ≥ _t=1^T_ ( _0- 2 _ _0 )- _t=1^T_ 2(1- _0)^t-1 =Texp(π0−2εmaxγ0)−2∑k=0Texp−1(1−γ0)k. =T_ ( _0- 2 _ _0 )-2 _k=0^T_ -1(1- _0)^k. The last term is a geometric series bounded by its infinite sum: ∑k=0Texp−1(1−γ0)k≤∑k=0∞(1−γ0)k=11−(1−γ0)=1γ0. _k=0^T_ -1(1- _0)^k≤ _k=0^∞(1- _0)^k= 11-(1- _0)= 1 _0. Substituting this back gives the lower bound on the expected visitations: [ϕTexp(a)]=∑t=1Texpνt(a)≥Texp(π0−2εmaxγ0)−2γ0=Texp⋅πeff−2γ0.E[ _T_ (a)]= _t=1^T_ _t(a)≥ T_ ( _0- 2 _ _0 )- 2 _0=T_ · _eff- 2 _0. (3) Part 3. Bound on the Martingale Difference Sum. The sum MTexp(a) ∑t=1Texp(at=a−νt(a))M_T_ (a) _t=1^T_ (1\a_t=a\- _t(a)) is a sum of martingale differences. The terms at=a1\a_t=a\ are not independent, as the learner’s position ata_t depends on at−1a_t-1. We therefore use a martingale concentration inequality. Let ℱt−1=σ(G0,…,Gt,a0,…,at−1)F_t-1=σ(G_0,…,G_t,a_0,…,a_t-1) be the filtration (history) up to the point of choosing ata_t. Define the martingale difference ξt(a) at=a−νt(a) _t(a) 1\a_t=a\- _t(a). The term νt(a)= (at=a∣ℱt−1) _t(a)= (a_t=a _t-1) is, by definition, the conditional expectation of at=a1\a_t=a\ given the past. Therefore: [ξt(a)∣ℱt−1]=[at=a∣ℱt−1]−νt(a)=νt(a)−νt(a)=0.E[ _t(a) _t-1]=E[1\a_t=a\ _t-1]- _t(a)= _t(a)- _t(a)=0. The increments are bounded: ξt(a)∈[0−1,1−0]=[−1,1] _t(a)∈[0-1,1-0]=[-1,1]. We apply Freedman’s inequality for martingales with bounded increments. For any x>0x>0: (MTexp(a)≤−x)≤exp(−x22(VTexp(a)+x/3)), (M_T_ (a)≤-x)≤ (- x^22(V_T_ (a)+x/3) ), where VTexp(a)V_T_ (a) is the predictable quadratic variation: VTexp(a) ∑t=1Texp[ξt(a)2∣ℱt−1]=∑t=1TexpVar(at=a∣ℱt−1).V_T_ (a) _t=1^T_ E[ _t(a)^2 _t-1]= _t=1^T_ Var(1\a_t=a\ _t-1). We bound the variance: Var(⋅)=νt(a)(1−νt(a))≤νt(a)Var(·)= _t(a)(1- _t(a))≤ _t(a). Thus: VTexp(a)≤∑t=1Texpνt(a)=[ϕTexp(a)]≤Texp.V_T_ (a)≤ _t=1^T_ _t(a)=E[ _T_ (a)]≤ T_ . Plugging the worst-case bound VTexp(a)≤TexpV_T_ (a)≤ T_ into Freedman’s inequality: (MTexp(a)≤−x)≤exp(−x22(Texp+x/3)). (M_T_ (a)≤-x)≤ (- x^22(T_ +x/3) ). We set the failure probability to δ/(5n)δ/(5n) for a single arm a. We must solve for x in: exp(−x22Texp+2x/3)≤δ5n⟺x22Texp+2x/3≥log(5n/δ). (- x^22T_ +2x/3 )≤ δ5n x^22T_ +2x/3≥ (5n/δ). This inequality holds if x is large enough to satisfy both x2≥2Texplog(5n/δ)x^2≥ 2T_ (5n/δ) and x2≥(2x/3)log(5n/δ)x^2≥(2x/3) (5n/δ). This is satisfied by: x≥2Texplog(5n/δ)+23log(5n/δ).x≥ 2T_ (5n/δ)+ 23 (5n/δ). Let xδx_δ be this lower bound. By a union bound over all n arms: (∃a:MTexp(a)≤−xδ)≤∑a=1n (MTexp(a)≤−xδ)≤n⋅(δ5n)=δ5. (∃ a:M_T_ (a)≤-x_δ)≤ _a=1^n (M_T_ (a)≤-x_δ)≤ n· ( δ5n )= δ5. Thus, with probability at least 1−δ/51-δ/5, MTexp(a)≥−xδM_T_ (a)≥-x_δ holds for all a simultaneously . Part 4. Combining Bounds. We combine the lower bound on the predictable sum (Part 2) and the high-probability bound on the martingale sum (Part 3): ϕTexp(a)=[ϕTexp(a)]+MTexp(a)≥[Texp⋅πeff−2γ0]−xδ. _T_ (a)=E[ _T_ (a)]+M_T_ (a)≥ [T_ · _eff- 2 _0 ]-x_δ. Substituting the expression for xδx_δ yields (2) . Corollary C.28 (Structural Condition for Non-Vacuous Exploration). The visitation lower bound in Lemma C.26 is dominated by the linear TexpT_ term and is thus non-vacuous (positive for large TexpT_ ) only if the effective minimal visitation πeff>0 _eff>0. This imposes the structural condition: π0−2εmaxγ0>0⟺εmax<π0γ02. _0- 2 _ _0>0 _ < _0 _02. (4) Using the high-probability bounds from ℰallE_all (specifically εmax≤Cζ0/p∞ _ ≤ C _0/p_∞ from Lemma C.20 and π0≥c3/n _0≥ c_3/n from Lemma C.8), this condition is satisfied if: Cζ0p∞≤(c3/n)γ02⟺ζ0≤C′p∞γ0n, C _0p_∞≤ (c_3/n) _02 _0≤ C p_∞ _0n, for some absolute constant C′C . This explicitly links the high-probability flip rate ζ0 _0 to the graph’s structural properties. To make this fully concrete, we substitute the definitions of these parameters (ignoring constants C′C and log factors for clarity). We require ζ0 p∞γ0/n _0 p_∞ _0/n. Assuming the graph is sufficiently connected such that we have a constant spectral gap γ0=Ω(1) _0= (1), and using ζ0≈ζ=2αβα+β _0≈ζ= 2αβα+β and p∞=α+βp_∞= α+β: 2αβα+β 1n(α+β)⟹β 1n. 2αβα+β 1n ( α+β ) β 1n. This reveals the core structural requirement for this analysis: for exploration to be guaranteed, the edge disappearance rate β must be on the order of O(1/n)O(1/n) or smaller. The graph must be ”sticky” enough (i.e., edges must persist long enough) to ensure the walk can cover the graph before it re-wires. We now assemble the high-probability guarantees for the graph’s static structure (Lemma C.8), spectral gap (Lemma C.15), and dynamic drift (Lemma C.20) with the uniform visitation bound (Lemma C.26) to derive a sufficient exploration length, TexpT_ , that guarantees the learner can identify the optimal arm with high probability. Theorem C.29 (Sufficient Exploration Length). Let Δmin mina≠a⋆Δ(a) _ _a≠ a (a) be the minimum sub-optimality gap. Assume the graph process satisfies a set of high-probability structural conditions (detailed in the proof), including a structural condition on the flip rate ζ0 _0. Then, there exist absolute constants C1,C2,C3>0C_1,C_2,C_3>0 such that choosing an exploration length TexpT_ satisfying Texp≥C1n+C2nlog(nδ)+C3nlog(n/δ)Δmin2T_ \;≥\;C_1\,n+C_2\,n\, \! ( nδ )+C_3\, n\, (n/δ) _ ^2 (5) is sufficient to guarantee that, with probability at least 1−δ1-δ, all empirical means satisfy |μ^(a)−μ(a)|≤Δ(a)/2| μ(a)-μ(a)|≤ (a)/2 for all arms a∈Aa∈ A. This ensures the correct identification of the optimal arm a⋆a . Proof C.30. The proof proceeds in five parts. We first define the high-probability ”base event” on which our analysis is conditioned. Second, we state our goal: the minimum number of samples NminN_ required for successful arm identification. Third, we invoke our uniform visitation lemma to get a high-probability lower bound on the actual visits ϕTexp(a) _T_ (a). Fourth, we derive the structural condition on the graph’s flip rate required for this bound to be meaningful. Finally, we solve for a TexpT_ large enough to guarantee ϕTexp(a)≥Nmin _T_ (a)≥ N_ . Step 1. The High-Probability Base Event. Our analysis is conditioned on a high-probability ”base event” ℰbaseE_base, which is the intersection of all typicality events established in the previous sections. We allocate a failure budget of δ/5δ/5 to each, for a total of 3δ/53δ/5 for this base event. ℰbaseE_base is the event that: (i) The static graph properties hold (Event ℰtypE_typ from Def. 5), so πt(a)≥π0≥cπ/n _t(a)≥ _0≥ c_π/n. This event holding requires the graph parameters to satisfy np∞≥C0log(nT/δ)np_∞≥ C_0 (nT/δ). (i) The uniform spectral gap holds (Lemma C.15), so γt≥γ0≥cγ>0 _t≥ _0≥ c_γ>0. (i) The stationary drift is bounded (Lemma C.20, using Lemma C.10), so εmax≤Cdζ0/p∞ _ ≤ C_d _0/p_∞. By a union bound, Pr(ℰbase)≥1−3δ/5 (E_base)≥ 1-3δ/5. All subsequent analysis is conditioned on ℰbaseE_base. Step 2. The Goal: Estimation Requirement. For the final estimation to succeed, we must ensure every arm a is sampled ϕTexp(a)≥Nmin _T_ (a)≥ N_ times. We must choose NminN_ to guarantee |μ^(a)−μ(a)|≤Δ(a)/2| μ(a)-μ(a)|≤ (a)/2 (and thus ≤Δmin/2≤ _ /2). For rewards in [0,1][0,1], we apply Hoeffding’s inequality. We allocate a failure budget of δ/5δ/5 for this estimation step. By a union bound over n arms, we require the failure probability for each arm to be at most δ/(5n)δ/(5n): Pr(|μ^(a)−μ(a)|>Δmin2)≤2exp(−NminΔmin22)≤δ5n. (| μ(a)-μ(a)|> _ 2 )≤ 2 (- N_ _ ^22 )≤ δ5n. Solving for NminN_ gives the minimum sample requirement. Let L log(10n/δ)L (10n/δ). Nmin≥2Δmin2log(10nδ) 2LΔmin2.N_ ≥ 2 _ ^2 ( 10nδ ) 2L _ ^2. Our goal is to find TexpT_ such that ϕTexp(a)≥2LΔmin2 _T_ (a)≥ 2L _ ^2 for all a, with high probability. Step 3. The Guarantee: Visitation Lower Bound. We invoke Lemma C.26, which provides a bound on the realized visitation counts. This lemma’s proof uses a martingale concentration (Freedman’s inequality) that requires its own δ/5δ/5 budget. Conditioned on ℰbaseE_base, with probability at least 1−δ/51-δ/5 (over the walk’s randomness), we have for all arms a: ϕTexp(a)≥Y(a)−(2VTexp(a)L+23L), _T_ (a)\;≥\;Y(a)- ( 2V_T_ (a)L+ 23L ), where Y(a)=∑t=1Texpνt(a)Y(a)= _t=1^T_ _t(a) is the predictable sum (expected visits), VTexp(a)≤Y(a)V_T_ (a)≤ Y(a) is the predictable quadratic variation, and L=log(5n/δ)L= (5n/δ) (we use this L for simplicity, as it has the same dependencies). From the proof of Lemma C.26 (Eq. 3), we have the lower bound: Y(a)≥Texp⋅πeff−2γ0,where πeff π0−2εmaxγ0.Y(a)≥ T_ · _eff- 2 _0, _eff _0- 2 _ _0. We also have a simple upper bound VTexp(a)≤Y(a)≤Texp⋅supt,aπt(a)V_T_ (a)≤ Y(a)≤ T_ · _t,a _t(a). Since πt(a)≤(dt(a)+1)/Zt≈np∞/(n2p∞)=1/n _t(a)≤(d_t(a)+1)/Z_t≈ np_∞/(n^2p_∞)=1/n, we have VTexp(a)≤(cπ′/n)TexpV_T_ (a)≤(c _π/n)T_ for some constant cπ′c _π. Plugging these into the visitation bound gives: ϕTexp(a)≥(Texpπeff−2γ0)−2cπ′LnTexp−23L. _T_ (a)≥ (T_ _eff- 2 _0 )- 2c _πLnT_ - 23L. Step 4. The Structural Condition for Exploration. For the bound in Step 3 to be useful (i.e., to grow linearly with TexpT_ ), we require the effective visitation probability πeff _eff to be strictly positive. πeff=π0−2εmaxγ0>0⟹εmax<π0γ02. _eff= _0- 2 _ _0>0 _ < _0 _02. This is a fundamental structural condition: the stationary distribution must not drift so fast that it overcomes the walk’s ability to mix. We now use our high-probability bounds from ℰbaseE_base to make this condition concrete: Cdζ0p∞⏟from εmax<(cπ/n)⋅cγ2⟹ζ0p∞≤Cs1n, C_d _0p_∞_from _ < (c_π/n)· c_γ2 _0p_∞≤ C_s 1n, for some new absolute constant CsC_s. We assume this structural condition on the graph’s flip dynamics holds. This implies πeff≥(cπ/n)−(cπ/n)/2=cπ/(2n) _eff≥(c_π/n)-(c_π/n)/2=c_π/(2n). Let cv cπ/2c_v c_π/2. Our guaranteed bound from Step 3 becomes: ϕTexp(a)≥cvnTexp−2cπ′LnTexp−2cγ−23L. _T_ (a)≥ c_vnT_ - 2c _πLnT_ - 2c_γ- 23L. Step 5. Sizing TexpT_ . We must choose TexpT_ large enough to satisfy ϕTexp(a)≥Nmin _T_ (a)≥ N_ (from Step 2). It is sufficient to enforce: cvnTexp−2cπ′LnTexp−(2cγ+23L)≥2LΔmin2. c_vnT_ - 2c _πLn T_ - ( 2c_γ+ 23L )\;≥\; 2L _ ^2. Let A=cv/nA=c_v/n, B=2cπ′L/nB= 2c _πL/n, and C=2LΔmin2+2cγ+23LC= 2L _ ^2+ 2c_γ+ 23L. We need to solve ATexp−BTexp≥CAT_ -B T_ ≥ C. A sufficient condition is to find TexpT_ such that ATexp/2≥CAT_ /2≥ C and ATexp/2≥BTexpAT_ /2≥ B T_ . 1. Texp≥2CA=2ncv(2LΔmin2+2cγ+23L)T_ ≥ 2CA= 2nc_v ( 2L _ ^2+ 2c_γ+ 23L ) 2. Texp≥4B2A2=4(2cπ′L/n)(cv/n)2=(8cπ′cv2)nLT_ ≥ 4B^2A^2= 4(2c _πL/n)(c_v/n)^2= ( 8c _πc_v^2 )nL We must take TexpT_ to be at least the sum of these requirements (or their maximum). Term (1) gives the O(nL/Δmin2)O(nL/ _ ^2), O(n)O(n), and O(nL)O(nL) components. Term (2) gives another O(nL)O(nL) component. Combining these and absorbing all absolute constants (cv,cγ,cπ′,L,L′c_v,c_γ,c _π,L,L ) into C1,C2,C3C_1,C_2,C_3 and L=O(log(n/δ))L=O( (n/δ)) gives the final form: Texp≥C1n+C2nlog(nδ)+C3nlog(n/δ)Δmin2.T_ \;≥\;C_1\,n+C_2\,n\, \! ( nδ )+C_3\, n\, (n/δ) _ ^2. Step 6. Total Success Probability. The overall success of the exploration phase requires ℰbaseE_base to hold, the visitation concentration (Step 3) to hold, and the estimation concentration (Step 2) to hold. Pr(Success) (Success) =Pr(ℰbase∩Visit∩Estimate) = (E_base ) =Pr(ℰbase)⋅Pr(Visit∣ℰbase)⋅Pr(Estimate∣Visit,ℰbase) = (E_base)· (Visit _base)· (Estimate ,E_base) ≥(1−3δ/5)⋅(1−δ/5)⋅(1−δ/5) ≥(1-3δ/5)·(1-δ/5)·(1-δ/5) ≥1−3δ/5−δ/5−δ/5=1−δ. ≥ 1-3δ/5-δ/5-δ/5=1-δ. Thus, the algorithm succeeds with total probability at least 1−δ1-δ. C.7 Post-Exploration Cost and Final Regret Lemma C.31 (Post-exploration navigation cost to a⋆a ). Fix an overall confidence level δ∈(0,1)δ∈(0,1) and let the navigation tail budget be δnav:=δ/5 _nav:=δ/5. Work on the base high-probability event ℰbaseE_base (typicality, spectral gap, and kernel drift), which holds with probability at least 1−3δ/51-3δ/5, where: (i) πt(a)≥π0 _t(a)≥ _0 for all t,at,a with π0≥cπ/n _0≥ c_π/n; (i) γ0≥cγ _0≥ c_γ (absolute constant via the Cheeger bound); (i) the per-step TV recursion holds: ‖νt+1−πt+1‖TV≤(1−γ0)‖νt−πt‖TV+εmax∀t≥1.\| _t+1- _t+1\|_TV\ ≤\ (1- _0)\,\| _t- _t\|_TV+ _ ∀ t≥ 1. Assume the stickiness choice (in outer parameters) is such that εmaxγ0≤π08. _ _0\ ≤\ _08\,. (6) Define tmix:=mins≥1:(1−γ0)s−1≤π08≤ 1+1γ0log8π0,thit:=⌈2π0log5δ⌉.t_mix:= \s≥ 1:\ (1- _0)^s-1≤ _08 \\ ≤\ 1+ 1 _0 8 _0, t_hit:= 2 _0\, 5δ . Then, starting from the (arbitrary) state at commit time, the lazy walk reaches a⋆a within Tnav:=tmix+thitT_nav\ :=\ t_mix+t_hit steps with probability at least 1−δnav=1−δ/51- _nav=1-δ/5, conditional on ℰbaseE_base. In particular, using π0≥cπ/n _0≥ c_π/n and γ0≥cγ _0≥ c_γ, tmix≤1cγlog8ncπ=O(logn),thit≤2ncπlog5δ=O(nlog1δ),t_mix\ ≤\ 1c_γ\, \! 8nc_π\ =\ O( n), t_hit\ ≤\ 2nc_π\, \! 5δ\ =\ O\! (n 1δ ), so Tnav=O(logn+nlog(1/δ))T_nav=O\! ( n+n (1/δ) ) in outer parameters. Proof C.32. Unrolling the recursion gives ‖νs−πs‖TV≤(1−γ0)s−1+εmax/γ0\| _s- _s\|_TV≤(1- _0)^s-1+ _ / _0. By the choice of tmixt_mix and (6), ‖νtmix−πtmix‖TV≤π0/8+π0/8=π0/4\| _t_mix- _t_mix\|_TV≤ _0/8+ _0/8= _0/4. Hence for all t≥tmixt≥ t_mix, Pr(at=a⋆∣ℱt−1)=νt(a⋆)≥πt(a⋆)−2‖νt−πt‖TV≥π0−2⋅π04=π02. (a_t=a _t-1)= _t(a )\ ≥\ _t(a )-2\| _t- _t\|_TV\ ≥\ _0-2· _04= _02. Let τ:=inft≥tmix:at=a⋆τ:= \t≥ t_mix:a_t=a \. Iterated conditioning yields Pr(τ>tmix+L∣ℱtmix)≤(1−π0/2)L≤exp(−(π0/2)L) (τ>t_mix+L _t_mix)≤(1- _0/2)^L≤ (-( _0/2)L). Choosing L=⌈(2/π0)log(5/δ)⌉L= (2/ _0) (5/δ) makes this tail ≤δ/5≤δ/5. Finally substitute γ0≥cγ _0≥ c_γ and π0≥cπ/n _0≥ c_π/n for the outer-parameter bounds on tmixt_mix and thitt_hit. Theorem C.33 (High-probability final regret). Fix a horizon T≥1T≥ 1 and confidence δ∈(0,1)δ∈(0,1). Rewards are bounded in [0,1][0,1]. Assume the edge-flip model at stationary edge density p∞∈(0,1)p_∞∈(0,1) with per-step flip envelope ζ0 _0 (from the kernel-drift lemma). Suppose the outer-parameter conditions hold (as in the exploration theorem): • Typicality & spectral gap (time-uniform). There exists Ctyp>0C_typ>0 such that np∞≥CtyplognTδnp_∞≥ C_typ \! nTδ and, on the corresponding ER-typical event, the lazy-walk kernels Mt\M_t\ satisfy γ0≥cγ _0≥ c_γ (a positive absolute constant from the Cheeger bound) and the stationary floor πt(a)≥π0≥cπ/n _t(a)≥ _0≥ c_π/n for all t,at,a, with absolute cγ,cπ∈(0,1)c_γ,c_π∈(0,1). • Stickiness (slow flips, outer form). There exists an absolute κ>0κ>0 such that ζ0p∞≤κn _0p_∞≤ κn, chosen so that the visitation slope is positive (equivalently, π0−2εmax/γ0≥cv/n _0-2 _ / _0≥ c_v/n for an absolute cv>0c_v>0). Let Δmin:=mina≠a⋆Δ(a) _ := _a≠ a (a). Then there exist absolute constants Cburn,C0,…,C4>0C_burn,C_0,…,C_4>0 such that, with probability at least 1−δ1-δ, R(T)≤Cburnα+βlognTδ⏟burn-in+C0n+C1nlog5nδ+C2nlog5nδΔmin2⏟exploration+C3logn+C4nlog5δ⏟navigation.R(T)\;≤\; C_burnα+β\, \! nTδ_burn-in\;+\; C_0\,n\;+\;C_1\,n\, \! 5nδ\;+\;C_2\, n\, \! 5nδ _ ^2_exploration\;+\; C_3\, n\;+\;C_4\,n\, \! 5δ_navigation. (7) Proof C.34. Split δ evenly across the five buckets: typicality, spectral gap, drift, visitation, estimation/navigation (each at level δ/5δ/5). By the burn-in lemma (time-uniform typicality for the window up to T), after Tburn≤Cburnα+βlognTδT_burn≤ C_burnα+β \! nTδ steps the base event ℰbaseE_base holds with probability at least 1−3δ/51-3δ/5 and yields: (i) πt(a)≥cπ/n _t(a)≥ c_π/n for all t,at,a; (i) γ0≥cγ _0≥ c_γ; (i) the TV recursion with finite εmax _ from the kernel-drift lemma. Under the stickiness condition, π0−2εmax/γ0≥cv/n _0-2 _ / _0≥ c_v/n. Exploration. On ℰbaseE_base, the exploration-length theorem (self-normalized Freedman + Hoeffding with visitation/estimation budgets δ/5δ/5) implies that choosing Texp≤C0n+C1nlog5nδ+C2nlog5nδΔmin2T_ ≤ C_0\,n+C_1\,n \! 5nδ+C_2\, n \! 5nδ _ ^2 suffices to identify a⋆a with probability at least 1−δ/51-δ/5. Navigation. Conditional on ℰbaseE_base and successful identification, the navigation lemma with tail δ/5δ/5 gives a path to a⋆a in Tnav≤C3logn+C4nlog5δT_nav≤ C_3\, n+C_4\,n \! 5δ steps with probability at least 1−δ/51-δ/5. On the intersection of these events (probability at least 1−δ1-δ by a union bound), exploitation incurs zero regret thereafter, hence R(T)≤Tburn+Texp+TnavR(T)≤ T_burn+T_ +T_nav, which is exactly (7). Corollary C.35 ((Restated) Expected Regret Bound). Under the same structural conditions as Theorem C.33, by setting the failure probability δ=1/Tδ=1/T, the expected cumulative regret [R(T)]E[R(T)] for the Explore-then-Commit strategy is bounded by: [R(T)]≤O(nlog(nT)Δmin2).E[R(T)]≤ O ( n (nT) _ ^2 ). Proof C.36. We use the law of total expectation, decomposing the regret based on the high-probability success event from the proof of Theorem C.33. Let ℰsuccessE_success be the event that all high-probability bounds hold and the optimal arm is correctly identified. From the theorem’s proof (Step 6), we know Pr(ℰsuccess)≥1−δ (E_success)≥ 1-δ. [R(T)]=[R(T)∣ℰsuccess]Pr(ℰsuccess)+[R(T)∣ℰsuccessc]Pr(ℰsuccessc).E[R(T)]=E[R(T) _success] (E_success)+E[R(T) _success^c] (E_success^c). We bound the two terms in this decomposition: • On the ”success” event ℰsuccessE_success: The algorithm’s regret is incurred entirely during the exploration phase, t∈[1,Texp]t∈[1,T_ ]. During this phase, the per-round regret is at most 1, contributing a total of TexpT_ . During the subsequent exploitation phase, t∈(Texp,T]t∈(T_ ,T], ℰsuccessE_success guarantees that the optimal arm a⋆a is selected, incurring 0 regret. Thus: [R(T)∣ℰsuccess]≤Texp.E[R(T) _success]≤ T_ . • On the ”failure” event ℰsuccesscE_success^c: This event occurs with probability at most δ. In the worst case, the algorithm incurs a regret of 1 on every single round. Thus, the maximum possible regret is T. [R(T)∣ℰsuccessc]≤T.E[R(T) _success^c]≤ T. Combining these bounds and using Pr(ℰsuccess)≤1 (E_success)≤ 1 and Pr(ℰsuccessc)≤δ (E_success^c)≤δ: [R(T)]≤(Texp)⋅(1)+(T)⋅(δ).E[R(T)]≤ (T_ )·(1)+(T)·(δ). To obtain a sublinear bound, we follow standard practice and set the failure probability δ=1/Tδ=1/T. This gives: [R(T)]≤Texp+T⋅(1T)=Texp+1.E[R(T)]≤ T_ +T· ( 1T )=T_ +1. The asymptotic form for TexpT_ follows by substituting δ=1/Tδ=1/T into the expression from Theorem C.29, noting that log(n/δ)=log(nT) (n/δ)= (nT), which leads us to the final bound. Appendix D Intrinsic Hardness of Identification Under Local Moves This appendix gives a self-contained derivation of the model-agnostic, fixed-confidence identification-time lower bound that follows solely from the local move constraint. Throughout, rewards are bounded in [0,1][0,1], and the best arm a⋆a is unique. Notation. Let A=1,…,nA=\1,…,n\ with means μ(a)a∈A\μ(a)\_a∈ A and gaps Δ(a) μ(a⋆)−μ(a)>0 (a) μ(a )-μ(a)>0 for a≠a⋆a≠ a . A (possibly randomized) policy π interacts over rounds t=1,2,…t=1,2,… as follows: at the start of round t the learner is at at−1∈Aa_t-1∈ A, the environment reveals a feasible set Lt(at−1)⊆AL_t(a_t-1) A with at−1∈Lt(at−1)a_t-1∈ L_t(a_t-1), the learner chooses at∈Lt(at−1)a_t∈ L_t(a_t-1), receives a reward Yt∈[0,1]Y_t∈[0,1] with [Yt∣ℱt−1,at]=μ(at)E[Y_t _t-1,a_t]=μ(a_t), and moves to ata_t (which becomes at−1a_t-1 for the next round). Let Na(t)N_a(t) denote the number of times arm a was pulled up to (and including) round t, and write Na≡Na(τ)N_a≡ N_a(τ) for the number of pulls up to a stopping time τ. For distributions P,QP,Q, KL(P∥Q)KL(P\|Q) denotes Kullback–Leibler divergence, and for p,q∈(0,1)p,q∈(0,1), kl(p,q) plogpq+(1−p)log1−p1−qkl(p,q) p \! pq+(1-p) \! 1-p1-q. Definition D.1 (Local move feasibility). A feasible-set process Lt(⋅)t≥1\L_t(·)\_t≥ 1 is valid if for all t and all a∈Aa∈ A, a∈Lt(a)⊆A\,a∈ L_t(a) A. No additional structure (stochastic or otherwise) is assumed. Definition D.2 (Fixed-confidence identification time). Given δ∈(0,1/2)δ∈(0,1/2), define the (policy-dependent) stopping time TIDπ(δ) inft≥1:π outputs a^t s.t. supvalid Lt,reward inst.ℙ(a^t≠a⋆)≤δ.T_ID^π(δ)\ \ \t≥ 1:\ π outputs a_t s.t. _valid \L_t\,\ reward inst.P\! ( a_t≠ a )≤δ \. Equivalently, the policy is δ-correct at time t if, for every valid feasible-set process and every [0,1][0,1]-bounded reward instance in the model class, the recommendation is correct with probability ≥1−δ≥ 1-δ. One observation per round. Because exactly one arm is pulled each round, TIDπ(δ)=∑a∈ANa(deterministically, on every sample path).T_ID^π(δ)\ =\ _a∈ AN_a (deterministically, on every sample path). (8) D.1 Per-arm fixed-confidence sample requirement For [0,1][0,1]-bounded rewards it suffices to work with Bernoulli instances via the standard reduction. Our proof relies on a divergence decomposition (lattimore_2020; garivier2011kl) inequality that relates the number of arm pulls to the difficulty of distinguishing between two bandit instances. Lemma D.3 (Stopping-Time Version of Divergence decomposition). Fix two bandit instances ν=(νa)a∈Aν=( _a)_a∈ A and ν′=(νa′)a∈Aν =( _a )_a∈ A, where νa _a is the reward law of arm a. Let π be any policy with a stopping time τ. Let ℙνP_ν (resp. ℙν′P_ν ) denote the law of the entire transcript (actions, rewards up to τ) under ν (resp. ν′ν ). Then, for any event E measurable w.r.t. the transcript, ∑a∈Aν[Na(τ)]KL(νa∥νa′)≥kl(ℙν(E),ℙν′(E)). _a∈ A\ E_ν[N_a(τ)]\ KL\! ( _a\,\|\, _a )\ ≥\ kl\! (P_ν(E),\,P_ν (E) ). Lemma D.4 (Per-arm lower bound (Bernoulli reduction)). Fix δ∈(0,1/2)δ∈(0,1/2). Consider the Bernoulli subclass: νa=Bernoulli(pa) _a=Bernoulli(p_a) with pa∈(0,1)p_a∈(0,1) and a unique best arm a⋆a . Let π be any policy that is δ-correct at time TIDπ(δ)T_ID^π(δ). Then, for each a≠a⋆a≠ a , [Na]≥kl(1−δ,δ)KL(Bern(pa)∥Bern(pa+2Δ(a))).E[N_a]\ ≥\ kl(1-δ,δ)KL\! (Bern(p_a)\,\|\,Bern(p_a+2 (a)) ). (9) In particular, if pa=12−Δ(a)p_a= 12- (a) (so μ(a)=12−Δ(a)μ(a)= 12- (a) and μ(a⋆)=12μ(a )= 12), then [Na]≥kl(1−δ,δ)2Δ(a)log1+2Δ(a)1−2Δ(a)≥332kl(1−δ,δ)Δ(a)2for all Δ(a)∈(0,14],E[N_a]\ ≥\ kl(1-δ,δ)2 (a)\, \! 1+2 (a)1-2 (a)\ ≥\ 332\ kl(1-δ,δ) (a)^2 all \ (a)∈ (0, 14 ], (10) where the last inequality uses log1+x1−x≤2x1−x2 \! 1+x1-x≤ 2x1-x^2 with x=2Δ(a)x=2 (a). Proof D.5. Fix a≠a⋆a≠ a . Work with Bernoulli rewards. Let ν be the instance with means μ(a⋆)=pa⋆μ(a )=p_a and μ(a)=paμ(a)=p_a, with gap Δ(a)=pa⋆−pa>0 (a)=p_a -p_a>0. Define the alternative instance ν′ν by modifying only arm a: νa′=Bernoulli(pa+2Δ(a)) _a =Bernoulli(p_a+2 (a)) and νb′=νb _b = _b for b≠ab≠ a. Under ν′ν , arm a is the unique best arm. Let τ≡TIDπ(δ)τ≡ T_ID^π(δ) and E≡“π recommends a⋆ at time τ”E≡\``$π$ recommends $a $ at time $τ$′\. By δ-correctness, ℙν(E)≥1−δP_ν(E)≥ 1-δ, whereas under ν′ν recommending a⋆a is an error, so ℙν′(E)≤δP_ν (E)≤δ. Applying Lemma D.3 with this E and noting that only arm a differs between ν and ν′ν gives [Na]⋅KL(Bern(pa)∥Bern(pa+2Δ(a)))≥kl(1−δ,δ),E[N_a]·KL\! (Bern(p_a)\,\|\,Bern(p_a+2 (a)) )\ ≥\ kl(1-δ,δ), which is (9). If in addition pa=12−Δ(a)p_a= 12- (a) so that pa+2Δ(a)=12+Δ(a)p_a+2 (a)= 12+ (a), the Bernoulli KL has the closed form KL(Bern(12−Δ)∥Bern(12+Δ))= 2Δlog1+2Δ1−2Δ,KL\! (Bern\! ( 12- )\, \|\,Bern\! ( 12+ ) )\ =\ 2 \, \! 1+2 1-2 , and the elementary inequality log1+x1−x≤2x1−x2 \! 1+x1-x≤ 2x1-x^2 for x∈(0,1)x∈(0,1) yields 2Δlog1+2Δ1−2Δ≤8Δ21−4Δ2≤323Δ2(Δ≤14),2 \, \! 1+2 1-2 \ ≤\ 8 ^21-4 ^2\ ≤\ 323\, ^2 ( ≤ 14), hence 12Δlog1+2Δ1−2Δ≥332⋅1Δ2 12 \, \! 1+2 1-2 \ ≥\ 332· 1 ^2, which gives (10). Remark D.6 (Why Bernoulli suffices for bounded rewards). Given [0,1][0,1]-bounded rewards with mean μ, by the standard data-processing argument (apply a mean-preserving thresholding), distinguishing means μ vs. μ+εμ+ is no easier than for Bernoulli(μ)(μ) vs. Bernoulli(μ+ε)(μ+ ). Thus the Bernoulli subclass yields valid lower bounds for the full [0,1][0,1]-bounded model. D.2 Traversal baseline The next lemma isolates a pure traversal effect of locality. It is not needed once the statistical term already scales with n (e.g., equal gaps), but we include it for completeness. Lemma D.7 (Traversal lower bound under local moves). For any policy and any n≥2n≥ 2, there exists a valid feasible-set process such that the time to visit all n arms at least once is deterministically at least n−1n-1. Proof D.8. Consider the time-homogeneous process with Lt(i)=i,i+1L_t(i)=\i,i+1\ for i<ni<n and Lt(n)=nL_t(n)=\n\, starting at a0=1a_0=1. Let τk=inft≥1:at=k _k= \t≥ 1:\ a_t=k\; then τk+1≥τk+1 _k+1≥ _k+1 for k<nk<n, hence τn≥n−1 _n≥ n-1. Remark D.9 (Movement and sampling are not additive in time). Since each round yields a single observation, TID=∑aNaT_ID= _aN_a by (8). The identification time is therefore at least the sampling budget ∑a≠a⋆[Na] _a≠ a E[N_a], and it may also be lower-bounded by the traversal time when many arms need negligible sampling. In equal-gap or small-δ regimes, ∑a≠a⋆[Na] _a≠ a E[N_a] already scales like n, so the traversal baseline is dominated and can be omitted. D.3 Identification-time lower bound and consequences Theorem D.10 (Identification-time lower bound under local moves). Let π be any policy that is δ-correct at time TIDπ(δ)T_ID^π(δ) for some δ∈(0,1/2)δ∈(0,1/2). For [0,1][0,1]-bounded rewards, working through the Bernoulli subclass, TIDπ(δ)=(8)∑a∈A[Na]≥∑a≠a⋆kl(1−δ,δ)2Δ(a)log1+2Δ(a)1−2Δ(a).E\,T_ID^π(δ)\ eq:TisSumNa-app=\ _a∈ AE[N_a]\ ≥\ _a≠ a kl(1-δ,δ)2 (a)\, \! 1+2 (a)1-2 (a). (11) In particular, for all Δ(a)∈(0,1/4] (a)∈(0,1/4], TIDπ(δ)≥332∑a≠a⋆kl(1−δ,δ)Δ(a)2.E\,T_ID^π(δ)\ ≥\ 332 _a≠ a kl(1-δ,δ) (a)^2. (12) If, moreover, Δ(a)≡Δ (a)≡ (equal-gap instance), then TIDπ(δ)≥332(n−1)kl(1−δ,δ)Δ2.E\,T_ID^π(δ)\ ≥\ 332\ (n-1)\,kl(1-δ,δ) ^2. (13) Proof D.11. Equation (8) is deterministic. Apply Lemma D.4 to each a≠a⋆a≠ a and sum the inequalities to obtain (11). Using the bound in (10) gives (12). The equal-gap statement (13) follows immediately.