Algorithm 2 Change Detection of M-UCB: CD Abstract We study the piecewise-stationary restless multi-armed bandit (PS-RMAB) problem, where each arm evolves as a Markov chain but mean rewards may change across unknown segments . To address the resulting exploration–detection delay trade-off, we propose a modular framework that integrates arbitrary RMAB base algorithms with change detection and a novel diminishing exploration mechanism. This design enables flexible plug-and-play use of existing solvers and detectors, while efficiently adapting to mean changes without prior knowledge of their number. To evaluate performance, we introduce a refined regret notion that measures the excess regret due to exploration and detection , benchmarked against an oracle that restarts the base algorithm at the true change points. Under this metric, we prove a regret bound of O ~ ​ ( L ​ M ​ K ​ T ) \tilde{O}(\sqrt{LMKT}) , where L L denotes the maximum mixing time of the Markov chains across all arms and segments, M M the number of segments, K K the number of arms, and T T the horizon. Simulations confirm that our framework achieves regret close to that of the segment oracle and consistently outperforms base solvers that do not incorporate any mechanism to handle environmental changes. A Modularized Framework for Piecewise-Stationary Restless Bandits Kuan-Ta Li Chia-Chun Lin Institute of Communications Engineering National Yang Ming Chaio Tung University Hsinchu, Taiwan Institute of Communications Engineering National Yang Ming Chaio Tung University Hsinchu, Taiwan Ping-Chun Hsieh Yu-Chih Huang Department of Computer Science National Yang Ming Chaio Tung University Hsinchu, Taiwan Institute of Communications Engineering National Yang Ming Chaio Tung University Hsinchu, Taiwan 1  Introduction Restless multi-armed bandits (RMABs) provide a powerful abstraction for sequential decision-making under resource constraints. In contrast to the classical stochastic multi-armed bandit (MAB), where unselected arms remain frozen, RMABs model each arm as an evolving Markov chain that continues to transition regardless of whether it is activated. This restless property enables RMABs to capture a wide range of dynamic allocation problems where opportunities or risks evolve continuously, even in the absence of intervention. Since the seminal work of 26 , RMABs have been studied extensively in both theory and practice. Whittle introduced the Whittle index, derived from a Lagrangian relaxation of the original optimization problem, which provides a computationally tractable priority rule under the indexability condition. Although finding the exact optimal policy is PSPACE-hard ( 18 ) , this line of work has inspired a rich literature on both theoretical guarantees and practical algorithms. Beyond its theoretical significance, the RMAB framework has proven highly impactful in practice, demonstrating utility across multiple domains. In communication systems, RMAB formulations underpin opportunistic scheduling tasks such as dynamic spectrum access in cognitive radio networks and downlink scheduling in wireless networks ( 13 ) . The same framework has been applied in healthcare, where RMAB-based policies help optimize limited intervention resources (e.g., scheduling follow-up calls to patients) in public health outreach programs to maximize engagement and outcomes ( 15 ) . Likewise, modern recommender systems leverage RMAB models to adapt content delivery as user preferences evolve over time ( 16 ) . Another important application arises in maintaining information freshness, where scheduling to minimize the Age of Information (AoI) can be naturally cast as an RMAB problem ( 9 ) . However, most existing studies assume stationary dynamics, which rarely hold in practice. Real-world environments often undergo gradual or abrupt changes, requiring policies that adapt over time. This motivates the study of RMABs in piecewise-stationary settings, where environments are segmented and the transition dynamics of arms shift at change points. These shifts are typically characterized by changes in the underlying Markov chains. To remain effective, the player’s policy must continually adjust to the new segments. Classical piecewise-stationary bandit problems employ two broad strategies for adaptation: active and passive methods. Active approaches couple standard bandit algorithms with change detection modules, which trigger resets upon detecting environmental shifts, making them well-suited for abrupt changes. In contrast, passive methods exploit mechanisms such as sliding windows or discount factors that gradually down-weight outdated samples, allowing the algorithm to adapt smoothly without explicit resets. While piecewise-stationary bandits have been extensively studied, extending these ideas to RMABs introduces unique challenges. In RMABs, different states of an arm can yield varying reward means, complicating the distinction between routine state transitions and genuine environmental changes. This variability raises the risk of false alarms, where a detection module may mistakenly interpret state-based fluctuations as true shifts in the environment. Building on this motivation, our work makes the following contributions: Modular framework for PS-RMABs. We introduce a modular algorithmic framework that integrates three key components: a stationary base solver, a change detection module, and a diminishing exploration schedule. This design ensures flexibility and plug-and-play adaptability, while isolating the two core sources of cost in piecewise-stationary environments: forced exploration and detection delay. Refined excess-regret notion. We formalize a new notion of excess regret , which explicitly captures the overhead caused by exploration and change detection, distinct from the intrinsic regret of the stationary base solver. Existing results for piecewise-stationary bandits show that the dominant terms in regret already arise from this exploration–delay balance, with the state-of-the-art scaling at \tilde{O}(\sqrt{MKT}) . Our formulation makes this balance transparent and provides a principled way to analyze its extension to restless settings. Diminishing exploration with minimal assumptions and low complexity. Our diminishing exploration (DE) requires no prior knowledge of the number of change points M , yet achieves a nearly optimal extra-regret bound of \tilde{\mathcal{O}}(\sqrt{MKT}) . It adds virtually no computational overhead, relying only on simple scheduling to trigger exploration phases. Theoretical guarantees and general-case analysis. We establish general excess-regret bounds that hold for arbitrary choices of base solvers and change detectors. These bounds confirm that the exploration–delay overhead is tightly controlled and does not exceed the known minimax rate in the piecewise-stationary setting. Consequently, whenever the stationary base solver is near-optimal, our framework preserves this near-optimality under piecewise-stationary extensions. Unlike passive adaptation methods such as sliding-window or discounted bandits, which continuously down-weight past observations, our approach actively coordinates exploration and change detection through a diminishing exploration schedule. This mechanism ensures sufficient statistical evidence for reliable detection while avoiding excessive exploration, and crucially eliminates the need for prior knowledge of the number of change points. Moreover, our framework naturally extends these ideas to restless settings, where passive forgetting mechanisms alone may fail due to state-dependent reward fluctuations. A natural question is whether one can simply combine existing change-detection schemes with learning algorithms designed for stationary restless bandits. However, naive integration may lead to unreliable detection, excessive resets, or degraded regret performance, particularly in restless environments where state evolution can obscure mean shifts. Our framework identifies conditions under which such integration remains stable and preserves regret guarantees. 1.1 Related Work Restless Bandit Problem. Restless bandits demand a range of algorithmic approaches. In planning settings with known models, index-based policies (Whittle’s and its variants) and LP-relaxation methods offer tractable solutions with guarantees like asymptotic optimality or constant-factor approximation ( 26 ; 8 ) . In online learning settings, even under partial observability, the RMAB community has achieved sublinear regret. A notable early algorithm is Colored UCRL2 ( 17 ) , which adapts the UCRL2 framework for restless bandits and provides \tilde{\mathcal{O}}(\sqrt{T}) regret under mild mixing assumptions, nearly matching the fundamental lower bound of \Omega(\sqrt{ST}) established in ( 17 ) , where S is the total number of states. More recent methods refine this paradigm using UCB-driven optimism—e.g., UCWhittle ( 23 ) and Restless-UCB ( 24 ) —to improve computational efficiency and adaptability. These developments supply both strong theoretical guarantees and broaden the practical applicability of RMAB solutions. These methods assume stationary environments and do not address change detection or adaptation to piecewise-stationary dynamics, which is the focus of our work. Recent works have begun to address non-stationary RMABs under smoothly varying environments. For instance, 21 propose a sliding-window Whittle index policy that adapts to time-varying transition kernels under a bounded variation budget, achieving sublinear dynamic regret. Similarly, 10 develop an optimistic Whittle-based algorithm with arm-specific sliding windows and establish regret guarantees under a global variation budget constraint. These approaches model non-stationarity through gradual drift in transition dynamics and rely on continuous adaptation mechanisms such as sliding windows. Another line of work considers more general non-stationarity under adversarial environments. For example, 27 study adversarial RMABs with unknown transitions and bandit feedback, where rewards can change arbitrarily across episodes, and develop reinforcement learning algorithms with \tilde{O}(\sqrt{T}) regret guarantees. These settings capture worst-case non-stationarity and require fundamentally different techniques based on online learning and occupancy measures. In contrast, our work focuses on piecewise-stationary environments with abrupt changes, where the main challenge lies in detecting change points and coordinating exploration with detection. Compared to variation-budget settings that assume gradual drift, and adversarial settings that allow arbitrary changes, our formulation imposes a structured non-stationarity model that enables sharper regret guarantees while still capturing realistic abrupt changes. Piecewise-Stationary Bandits. Existing approaches to PS-MAB can be broadly categorized into passive and active methods. Passive methods adapt to changes through forgetting mechanisms such as Discounted UCB ( 11 ) , Sliding-Window UCB ( 7 ) , and their Thompson Sampling counterparts ( 20 ; 19 ) , all achieving {\mathcal{O}}(\sqrt{KMT}\,\mathrm{polylog}(T)) regret. Active methods, in contrast, integrate change detection with standard bandit algorithms. Examples include CD-UCB ( 12 ) and M-UCB ( 5 ) , which combine UCB with detectors like CUSUM or simple window-based tests to obtain {\mathcal{O}}(\sqrt{KMT\log T}) regret. More recent efforts, such as AdSwitch ( 3 ) and GLR-klUCB ( 4 ) , avoid assuming prior knowledge of the number of changes M , advancing practical applicability. Among active methods, complexity is largely dictated by the change detector: M-UCB ( 5 ) uses a lightweight window-based test, while GLR-klUCB adopts a more statistically refined GLR detector, incurring moderately higher cost but achieving nearly optimal guarantees and strong empirical performance. AdSwitch, in contrast, features a substantially more complex detection scheme with elegant theory but no empirical validation. For example, 14 design detectors based on empirical gaps between arms; 22 quantify significant shifts at each step to avoid reliance on prior non-stationarity knowledge; and 1 achieve comparable guarantees under abrupt changes. Complementary to these, multi-scale approaches such as 25 maintain multiple competing instances of the base algorithm to strengthen robustness. Although these works do not explicitly target the restless bandit problem, their designs—typically involving change detection or adaptive re-weighting—suggest potential applicability. However, their theoretical analyses usually rely on specific assumptions about the base algorithm (e.g., optimism or structural properties), which narrows the range of admissible base solvers that can be used while still guaranteeing strong regret bounds. Our framework differs from these works in two key aspects: (i) it introduces a diminishing exploration mechanism to systematically supply evidence for detection without prior knowledge of change frequency, and (ii) it extends these ideas to restless bandits, where state evolution can confound detection. 2  Problem Formulation We study the piecewise-stationary RMAB (PS-RMAB) problem. The system consists of a single learner interacting with K arms. Each arm k\in\{1,\ldots,K\} is modeled as a finite-state Markov chain \mathcal{M}_{k}=(\mathcal{S},P_{k},R_{k}) , where \mathcal{S}=\{1,\ldots,S\} is the state space, P_{k}:\mathcal{S}\times\mathcal{S}\to[0,1] is the transition kernel, and R_{k}:\mathcal{S}\to[0,1] is the reward distribution. At each round t=1,2,\ldots,T , the learner selects an arm A_{t} , observes its current state s_{A_{t},t} , and receives a random reward R_{A_{t}}(s_{A_{t},t})\in[0,1] . The expectation of this reward is denoted by \mu_{A_{t},s_{A_{t},t}}=\mathbb{E}[R_{A_{t}}(s_{A_{t},t})] , which we call the per-state mean reward . We assume the environment is piecewise-stationary . There exist change points 0=\nu_{0}<\nu_{1}<\cdots<\nu_{M}=T such that, within each segment i\in\{1,\ldots,M\} , arm k is characterized by a Markov chain \mathcal{M}_{k}^{(i)}=(P_{k}^{(i)},R_{k}^{(i)}) with per-state mean rewards \mu_{k,s}^{(i)} . The object of interest is the arm-mean vector \bar{\bm{\mu}}^{(i)}=(\bar{\mu}_{1}^{(i)},\ldots,\bar{\mu}_{K}^{(i)}) , which represents the long-run average rewards of all arms in segment i . This vector remains fixed within each segment (\nu_{i-1},\nu_{i}] but may change across consecutive segments (i.e., \bar{\bm{\mu}}^{(i)}\neq\bar{\bm{\mu}}^{(i+1)} for at least one arm). Any modification that alters an arm mean is regarded as a change point. Figure 1 illustrates the instant reward of one of the arms in a PS-RMAB environment. Figure 1: Instant reward of Arm k in PS-RMAB environment Fix a stationary RMAB base solver \mathcal{B} . The segment-wise oracle \pi^{\mathrm{seg}}(\mathcal{B}) knows the true change points \nu_{1},\ldots,\nu_{M-1} and simply restarts \mathcal{B} at the beginning of each segment (all other details—model class, observability, and action constraints—are identical to those faced by the learner). Let r_{t}^{\pi} denote the expected reward at time t under the learner’s policy and r_{t}^{\mathrm{seg}} the counterpart under \pi^{\mathrm{seg}}(\mathcal{B}) We define the excess regret of a policy \pi (relative to \pi^{\mathrm{seg}}(\mathcal{B}) ) as \mathcal{R}_{\mathrm{excess}}(T)\;=\;\mathbb{E}\!\Big[\sum_{t=1}^{T}r_{t}^{\mathrm{seg}}\Big]\;-\;\mathbb{E}\!\Big[\sum_{t=1}^{T}r_{t}^{\pi}\Big]. (1) This metric depends only on the overhead induced by exploration and change detection (and any reset misalignment), while factoring out the stationary performance of the chosen base solver. 3  Proposed Framework: Diminishing Exploration Our framework builds upon the active method paradigm ( 28 ; 12 ; 5 ) , which combines a stationary bandit algorithm with a change-detection module. Whenever a change is detected, the base algorithm is restarted in the new segment. To ensure sufficient environmental sampling for change detection, we further integrate a novel exploration scheme, diminishing exploration , which dynamically balances the trade-off between exploration cost and detection delay. This modular design allows arbitrary stationary solvers and detectors to be flexibly combined without altering their internal structures. 3.1 Diminishing Exploration Most existing works adopt a uniform exploration scheme that allocates a constant fraction of time to exploration ( 12 ; 5 ) . While effective for detecting changes, the approach results in regret that scales linearly with the exploration rate and therefore requires prior knowledge of the number of change points M in order to appropriately set this rate. To address this limitation, we introduce diminishing exploration , which adaptively reduces the frequency of forced exploration over time, thereby eliminating the need for prior knowledge of M . Let us define \tau_{i} as the i -th time when the algorithm alarms a change. In the proposed method, a uniform exploration round starts at u_{i-1}^{(j)} for j\in\{1,2,\ldots\} with u_{i-1}^{(1)}=\tau_{i-1}+1 . i.e., the learner chooses to pull the arm 1,2,\ldots,K at time u_{i-1}^{(j)},u_{i-1}^{(j)}+1,\ldots,u_{i-1}^{(j)}+K-1 , respectively. The process restarts whenever a new change \tau_{i} is detected. Figure 2: Diminishing exploration. We aim to balance the regret resulting from exploration and that associated with the performance of change detection by dynamically adjusting the exploration rate within a segment . Let u_{i-1}^{(j)} be the start time of the j -th uniform exploration session between two consecutive alarms \tau_{i} and \tau_{i-1} . In our approach, these sessions are designed in such a way that u_{i-1}^{(j+1)}-u_{i-1}^{(j)} is greater than u_{i-1}^{(j)}-u_{i-1}^{(j-1)} . This means that the inter-session time within the same time segment increases with j , which in turn results in a reduction in the exploration rate. Specifically, for the i -th segment, we choose u_{i}^{(1)}=\left\lceil\left(\alpha-K/4\alpha\right)^{2}\right\rceil and u_{i}^{(j)}=\left\lceil u_{i}^{(j-1)}+\frac{K}{\alpha}\sqrt{u_{i}^{(j-1)}}+\frac{K^{2}}{4\alpha^{2}}\right\rceil,\quad\forall~1\leq i\leq M\textrm{,}~j\geq 2 , without the knowledge of M and the parameter \alpha will be chosen later. Clearly, we have u_{i}^{(j-1)}+K0 , under the Algorithm 1 , we have \mathbb{P}\left(D_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right)\geq 1-\frac{1}{T}. (10) This lemma guarantees that each genuine change is detected with high probability, which prevents the algorithm from staying too long in a mismatched segment. Lemma 4.7 (Expected detection delay) . Consider a piecewise-stationary bandit environment. For any \bm{\mu}^{(i)},\bm{\mu}^{(i+1)}\in\left[0,1\right]^{K} with parameters chosen in equation 3 and equation 4 and h_{i}=\left\lceil w\left(\frac{K}{2\alpha}+1\right)\sqrt{s_{i}+1}+\frac{w^{2}}{4}\left(\frac{K}{2\alpha}+1\right)^{2}\right\rceil, (11) for some K\in{\mathcal{K}},i\geq 1 and c>0 , under the Algorithm 1 , we have \mathbb{E}\left[\tau_{i}-\nu_{i}\middle|\overline{F}_{i}D_{i}\overline{F}_{i-1}D_{i-1}\right]\leq h_{i}. (12) In other words, once a change occurs, the delay before detection is bounded in expectation by h_{i} , which scales sublinearly with s_{i} under our parameter choice. This ensures that the regret accumulated during delays is well controlled. Putting everything together. The regret from diminishing exploration (Lemma 4.4 ) is \mathcal{O}(\sqrt{KMT}) ; the false alarm contribution (Lemma 4.5 ) is negligible; and the regret during detection delays (Lemmas 4.6 – 4.7 ) is bounded by \tilde{\mathcal{O}}(\sqrt{KMT}) . Substituting these into the general bound in Theorem 4.1 , we obtain \mathcal{R}_{\mathrm{excess}}(T)\leq\mathcal{O}\!\left(\sqrt{KMT\log T}\right), (13) which concludes the proof sketch. In the one-state setting, PS-RMAB reduces to the classical piecewise-stationary MAB. In addition to the extra-regret perspective, our framework naturally extends to a standard regret analysis against a clairvoyant oracle that always pulls the best arm in each segment. If the base solver \mathcal{B} is chosen as UCB, then under bounded rewards and a change detector with controlled false-alarm probability and expected delay, the total regret of Algorithm 1 remains near-optimal, scaling as \tilde{\mathcal{O}}(\sqrt{KMT}) . The detailed proof is deferred to Supplementary Materials. 4.2 General Case Compared to the one-state case, the general PS-RMAB setting introduces additional challenges due to the temporal dependence of rewards induced by the Markovian dynamics. To handle this dependence, our analysis leverages the mixing time of each arm’s Markov chain, which allows us to approximate independence and apply concentration inequalities. To make this argument rigorous, we require a technical assumption ensuring that each arm’s Markov chain admits well-defined steady-state behavior. In particular, ergodicity guarantees the existence of unique stationary distributions and enables the use of concentration tools in our regret analysis. Assumption 4.8 . All Markov chains \mathcal{M}_{k}^{(i)}=(P_{k}^{(i)},R_{k}^{(i)}) are ergodic. This ensures the existence of a unique steady-state distribution d_{k}^{(i)} for each arm k in segment i , satisfying d_{k}^{(i)}=d_{k}^{(i)}P_{k}^{(i)} with \sum_{s\in\mathcal{S}}d_{k}^{(i)}(s)=1 . We then define the steady-state arm mean as \bar{\mu}_{k}^{(i)}:=d_{k}^{(i)}R_{k}^{(i)} . This assumption is necessary because the reward sequence of each arm arises from a Markov chain, which induces temporal dependence. Ergodicity allows us to approximate independence through the mixing properties of the chains and to apply concentration inequalities (e.g., Hoeffding-type bounds for Markov processes). Without this assumption, the notion of a stationary arm mean would not be well defined, and regret guarantees could not be rigorously established. To accommodate this dependence within the change detection module, we refine the choice of its parameters. Specifically, the window size w and threshold b are tuned in accordance with the mixing-time bound, ensuring that the detector achieves the required statistical guarantees while remaining compatible with the diminishing exploration schedule. Formally, we select w\;=\;\frac{4}{\delta_{\min}^{2}}\!\left(\sqrt{2\ln(2KT^{2})}\;\right.\\ +\left.\;\sqrt{144\,L\,\ln(2KT^{2})}\;+\;\sqrt{144\,L\,\ln(2T)}\right)^{2}, (14) b\;=\;\sqrt{\frac{w}{2}\,\ln(2KT^{2})}\;+\;\sqrt{144\,w\,L\,\ln(2KT^{2})}. (15) where \delta_{\min} is a known lower bound on the mean shift, and L=\max_{i\in\{1,\dots,M\}}\max_{k\in\mathcal{K}}L_{k}^{(i)} denotes the maximum mixing time of the Markov chains associated with all arms and segments. Corollary 4.9 . Combining Algorithm 1 (diminishing exploration with resets) with the base solver \mathcal{B} and Algorithm 2 with parameters (w,b) given in Equations 14 and 15 , the excess regret is upper-bounded as \mathcal{R}_{\mathrm{excess}}(T)\;\leq\;\mathcal{O}\!\left(\sqrt{MKLT\log T}\right), (16) where L=\max_{i\in\{1,\dots,M\}}\max_{k\in\mathcal{K}}L_{k}^{(i)} denotes the maximum mixing time of the Markov chains associated with all arms and segments. Proof Outline of Corollary 4.9 . The overall proof follows the same decomposition as in Corollary 4.3 , namely by bounding the regret incurred from (i) diminishing exploration within stationary segments, (ii) regret caused by false alarms, and (iii) regret due to delays in detecting true changes. The bounds from Lemma 4.4 apply directly here as well. For the false alarm probability, we now invoke Lemma 4.5 , which states that under Algorithm 2 with parameters chosen according to Equations 14 and 15 , the probability of a false alarm in each stationary period is at most \mathbb{P}\!\left(F_{i}\,\middle|\,\overline{F}_{i-1}D_{i-1}\right)\;\leq\;\frac{\epsilon\|\varphi\|_{d}+1}{T}. (17) This again ensures that the contribution of false alarms to the overall regret is negligible in expectation. For the detection probability and delay, Lemma 4.6 shows that for each change, with the choice of parameters w,b as in Equations 14 and 15 and the delay threshold h_{i} , \mathbb{P}\!\left(\overline{D}_{i}\,\middle|\,\overline{F}_{i-1}D_{i-1}\right)\;\leq\;\frac{\epsilon\|\varphi\|_{d}}{T}, (18) so that missed detections occur with vanishing probability. Moreover, the expected detection delay is bounded by h_{i} , which scales sublinearly with the segment length. These results play the same role as Lemmas 4.6 and 4.7 in the one-state case. Here, \epsilon>0 is an arbitrarily small constant, and \varphi denotes the initial state distribution of the Markov chains. Therefore, the regret contributions from diminishing exploration, false alarms, and detection delays remain of the same order as before, and substituting these bounds into Theorem 4.1 yields \mathcal{R}_{\mathrm{excess}}(T)\leq\mathcal{O}\!\left(\sqrt{KMLT\log T}\right), (19) which establishes Corollary 4.9 . From Theorem 4.1 , the additional cost introduced by diminishing exploration and change detection, captured by \mathcal{R}_{\mathrm{excess}} , is strictly controlled and does not alter the order of regret. To argue near-optimality, we turn to the one-state case , which reduces to the classical PS-MAB setting. Here, our framework combined with UCB attains the known \tilde{\mathcal{O}}(\sqrt{KMT}) bound, confirming that the overhead is indeed compatible with near-optimal performance. The regret bound depends on problem-specific parameters such as the mixing time of the underlying Markov chains, reward gaps, and detector parameters. These quantities influence constant factors but do not alter the asymptotic rate. In particular, larger mixing times or smaller mean shifts may increase detection difficulty, leading to longer delays, yet the overall regret order remains unchanged. Motivated by this evidence, we extend the conclusion to the general PS-RMAB setting: Principle 4.10 (Transfer Principle) . If the base solver \mathcal{B} achieves near-optimal regret in the stationary RMAB setting, then Algorithm 1 equipped with \mathcal{B} and a suitable change detector \mathcal{D} inherits this near-optimality in the PS-RMAB setting. Proof. Since the stationary RMAB already admits a minimax lower bound of \Omega(\sqrt{ST}) ( 17 ) , and our framework in the piecewise-stationary case introduces only an additional \tilde{\mathcal{O}}(\sqrt{MKT}) overhead, the overall regret rate remains \tilde{\mathcal{O}}(\sqrt{T}) . Thus, the near-optimality of stationary solvers is preserved under piecewise-stationary extensions. ∎ 5  Simulation Results We evaluate our framework using RestlessUCB and colorUCRL2 as base algorithms. For each case, we report both the excess regret defined in our framework and the standard regret benchmarked against a value-iteration oracle baseline. The simulations adopt the partial modular setting, where information is shared between the exploration module and the base algorithm, enabling more accurate and comprehensive estimation for arm selection; this may explain why, as shown in Figures 3(a) , the observed excess regret can occasionally be smaller than that of the segment oracle. The results are summarized in Figures 3(a) and 3(b) . Environment Configuration. We simulate a PS-RMAB environment with a horizon of T=100{,}000 time steps, partitioned into M=5 stationary segments. The problem consists of K=3 arms, each modeled as a Markov chain with S=3 states. The stationary mean rewards of the arms are configured as \bar{\mu}^{(i)}_{k}\in\{0.2,\,0.5,\,0.8\} , assigned according to the rule (i+k)\bmod 3=2,0,1 , respectively, for segment i and arm k . Extra vs. Standard Regret. As shown in Figure 3(a) , the excess regret exhibits only minor variation across different choices of base algorithms. This indicates that the additional overhead induced by our mechanism is essentially independent of the base solver. Comparing with the standard regret in Figure 3(b) , we observe that the overhead introduced by our framework is negligible relative to the dominant regret incurred by the base algorithms themselves. In particular, the UE curve represents the optimal exploration amount achievable when the number of segments is known in advance, while DE corresponds to our proposed diminishing exploration scheme without prior knowledge of the number of changes. (a) Excess Regret. (b) Standard Regret. Figure 3: Significance of Change Detection. One may wonder: since the regret of the base algorithms already dominates, is it sufficient to simply let them adapt on their own, without any change-detection or exploration mechanism? To examine this, we also simulate the scenario where no change-detection module is used. As shown in Figures 3(a) and 3(b) , the regret exhibits a much sharper growth when the environment changes are ignored, indicating that the base algorithms alone struggle to adapt promptly to non-stationarity. This illustrates the potential performance degradation caused by neglecting environmental shifts. 6  Conclusion We addressed the PS-RMAB problem by introducing a modular framework that integrates stationary solvers, change detection, and a novel diminishing exploration schedule. Central to our analysis is a refined notion of excess regret, which isolates the costs of exploration and detection delay. We proved that this overhead matches the minimax order known for piecewise-stationary bandits, and established a transfer principle showing that the near-optimality of stationary solvers carries over to the PS-RMAB setting. This provides both a unifying theoretical perspective and a practical recipe for extending stationary algorithms to dynamic environments. Appendix A Change Detection Algorithm Change Detector of M-UCB The following algorithm is the change detection algorithm for M-UCB ( 5 ) In this algorithm, one requires w observations as input and check whether the difference between the sample average of the first half and that of the second half exceeds a prescribed threshold b (line 1). Integration with the change detector of M-UCB. The following two assumptions are required to establish the analytical results when integrating M-UCB into our modularized framework. Assumption A.1 . The algorithm knows a lower bound \delta>0 such that \delta\leq\min_{i}\max_{k\in\mathcal{K}}\delta^{\left(i\right)}_{k} . Note that Assumption A.1 is Assumption 1(b) of 5 , which is required for the M-UCB detector to determine good w and b in regret analysis. It is worth noting that almost all schemes that actively detect changes share similar assumptions; however, different algorithms may impose distinct sets of assumptions. This assumption is mild since \delta may be statistically derived from historical information. Furthermore, even if the lower bound does not hold, and we occasionally encounter changes with expected reward gaps smaller than the assumed \delta , such changes may be perceived as too minor to result in significant regret. Assumption A.2 . We assume s_{i}=\Omega\left((\log{KT}+\sqrt{K\log{KT}})\sqrt{s_{i-1}}\right). (20) In particular, if s_{i}=\Theta\left(\left(\log{KT}+\sqrt{K\log{KT}}\right)^{2(1+\epsilon)}\right) for every i , Assumption A.2 holds. This assumption essentially posits that the changes are not overly dense, a condition that holds in many practical scenarios. Simple math would then show that given D_{i-1} is true, with this assumption and the proposed diminishing exploration, each arm will have at least w/2 observations before and after a change point. Again, we note that similar assumptions are imposed in other algorithms that actively detect changes, while different algorithms may impose different assumptions. This assumption is necessary with our proof technique, which requires every change to be successfully detected with high probability. Appendix B Proof Detail In this appendix, we provide detailed proofs of the results presented in Section 4. Each proof is carefully elaborated to ensure clarity and rigor. B.1 Proof of Section 4 In this subsection, we present the proofs of theorems in Section 4. In what follows, the first lemma bounds the regret accumulated during the diminishing exploration part of the algorithm. We denote by R_{\mathrm{DE}}\left(\tau_{i-1},\nu_{i}\right) as the regret caused by the exploration part of the algorithm and by N_{\mathrm{DE},k}\left(\tau_{i-1},\nu_{i}\right) the number of times that the arm k is selected in the exploration phase from the previous alarm time to the next change point. Lemma B.1 (Diminishing exploration regret) . If the mean values of the arms remain the same during the time interval [\tau_{i-1},\nu_{i}) , then we have N_{\mathrm{DE},k}\left(\tau_{i-1},\nu_{i}\right)\leq\frac{2\alpha\sqrt{\nu_{i}-\tau_{i-1}}}{K}+\frac{3}{2}, (21) and \mathbb{E}\left[R_{\mathrm{DE}}\left(\tau_{i-1},\nu_{i}\right)\right]\leq 2\alpha\sqrt{\nu_{i}-\tau_{i-1}}+\frac{3}{2}K. (22) Proof. Recall that u_{i}^{(j)} is the beginning of the j -th uniform exploration session in the i -th segment. In Algorithm 1 , the initial time of the first exploration session after each \tau_{i} is given by: u_{i}^{(1)}=\left\lceil\left(\alpha-\frac{K}{4\alpha}\right)^{2}\right\rceil, (23) and subsequent times follow the recursive equation: u_{i}^{(j)}=\left\lceil u_{i}^{(j-1)}+\frac{K}{\alpha}\sqrt{u_{i}^{(j-1)}}+\frac{K^{2}}{4\alpha^{2}}\right\rceil\geq u_{i}^{(j-1)}+\frac{K}{\alpha}\sqrt{u_{i}^{(j-1)}}+\frac{K^{2}}{4\alpha^{2}}. (24) Based on equation 23 and equation 24 , one could easily check that the sequence u_{i}^{(n)} satisfies that for every natural number n , u_{i}^{(n)}\geq\left(\frac{\left(2n-3\right)K}{4\alpha}+\alpha\right)^{2}. (25) Let u_{i}^{(m)} be the last exploration start time in time interval [\tau_{i-1},\nu_{i}) . Then, we have \mathbb{E}\left[R_{\mathrm{DE}}\left(\nu_{i},\tau_{i-1}\right)\right]\leq mK. (26) Additionally, we have: \nu_{i}-\tau_{i-1}\geq u_{i}^{(m)}\geq\left(\frac{\left(2m-3\right)K}{4\alpha}+\alpha\right)^{2}\geq\left(\frac{2\mathbb{E}\left[R_{DE}\left(\nu_{i}-\tau_{i-1}\right)\right]-3K}{4\alpha}+\alpha\right)^{2}. (27) Finally, based on the equation 26 and equation 27 , we can conclude that: \mathbb{E}\left[R_{\textrm{DE}}\left(\nu_{i},\tau_{i-1}\right)\right]\leq 2\alpha\sqrt{\nu_{i}-\tau_{i-1}}-2\alpha^{2}+\frac{3}{2}K\leq 2\alpha\sqrt{\nu_{i}-\tau_{i-1}}+\frac{3}{2}K, (28) and N_{\textrm{DE},k}\left(\nu_{i},\tau_{i-1}\right)\leq\frac{2\alpha\sqrt{\nu_{i}-\tau_{i-1}}}{K}+\frac{3}{2}. (29) ∎ In the following lemma, we aim to explore how many time steps it takes for a given arm to reach a certain number of samples through diminishing exploration. Lemma B.2 (Samples-time steps transform) . When each arm has accumulated n samples, the required time is as follows: If the counting of the n samples begins immediately after a reset, the required time is given by T_{reset}\leq\left(\alpha+\frac{\left(2n-3\right)K}{4\alpha}+n\right)^{2}+K. (30) However, if there is a delay of t_{d} time steps after the reset before the counting begins, the required time is given by T_{t_{d}}\leq 2n\left(\frac{K}{2\alpha}+1\right)\sqrt{t_{d}+1}+n^{2}\left(\frac{K}{2\alpha}+1\right)^{2}. (31) Proof. We can derive the following from Equation 24 in the proof of Lemma B.1 : u^{(j)}\leq u^{(j-1)}+\frac{k}{\alpha}\sqrt{u^{(j-1)}}+\frac{k^{2}}{4\alpha^{2}}+1\leq\left(\sqrt{u^{(j-1)}}+\frac{k}{2\alpha}\right)^{2}+1\leq\left(\sqrt{u^{(j-1)}}+\frac{k}{2\alpha}+1\right)^{2}. (32) First, let us consider the case where the counting of n samples begins immediately after the reset. From Equation 23 , we can derive the following: u^{(1)}\leq\left(\alpha-\frac{K}{4\alpha}+1\right)^{2}. (33) Using Equation 32 , we can further derive: u^{(2)}\leq\left(\alpha-\frac{K}{4\alpha}+1+\frac{K}{2\alpha}+1\right)^{2}. (34) Finally, we obtain: u^{(n)}\leq\left(\alpha-\frac{K}{4\alpha}+1+(n-1)\left(\frac{K}{2\alpha}+1\right)\right)^{2}. (35) Here, u^{(n)} represents the starting time of the n -th exploration block. The total time required to guarantee that all K arms have been sampled n times is therefore: T_{\text{reset}}=u^{(n)}+K\leq\left(\alpha+\frac{(2n-3)K}{4\alpha}+n\right)^{2}+K. (36) Next, we consider how long it takes for each arm to be sampled n times after t_{d} time steps following the reset. We first assume that, prior to t_{d} , each arm has already been sampled x times. For simplicity, we assume an ideal case where the exploration block starts exactly at time t_{d}+1 . Therefore, we have: u^{(x+1)}=t_{d}+1. (37) Since, in reality, the exploration block start time may not exactly coincide with t_{d}+1 , we account for the possibility that it could begin at a later time by considering the next exploration block’s start time. This allows us to bound the non-ideal case. Following the same approach as in the first part of the proof, we eventually obtain: u^{(x+n+1)}\leq\left(\sqrt{t_{d}+1}+n\left(\frac{K}{2\alpha}+1\right)\right)^{2}. (38) Finally, we derive that the total time required for each arm to be sampled n times after t_{d} time steps is: T_{t_{d}}=u^{(x+n+1)}-u^{(x+1)}\leq 2n\left(\frac{K}{2\alpha}+1\right)\sqrt{t_{d}+1}+n^{2}\left(\frac{K}{2\alpha}+1\right)^{2}. (39) ∎ Define R_{\mathrm{excess}}(r,s):=\mathbb{E}[\textstyle\sum_{t=r}^{s}r_{t}^{\mathrm{seg}}]-\textstyle\sum_{t=r}^{s}r_{t}^{\pi} be the regret accumulated during r and s . In the next lemma, we provide an upper bound on the regret accumulated from the \left(i-1\right) -th alarm time to the end of \left(i-1\right) -th segment, given that the previous change was successfully detected. Lemma B.3 (Excess Regret bound with stationary bandit) . Consider a stationary bandit interval with \nu_{i-1}<\tau_{i-1}<\nu_{i} . Condition on the successful detection events \overline{F}_{i-1} and D_{i-1} , the expected regret accumulated during \left(\tau_{i-1},\nu_{i}\right) can be bounded by \mathbb{E}\left[R_{\mathrm{excess}}\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i-1}D_{i-1}\right]\leq 2\alpha\sqrt{s_{i}}+T\cdot\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right), (40) Proof. We begin by rewriting the definition of the excess regret over a stationary segment (\tau_{i-1},\nu_{i}] as R_{\mathrm{excess}}\!\left(\tau_{i-1},\nu_{i}\right)=\Bigg(\mathbb{E}\Big[\textstyle\sum_{t=\tau_{i-1}}^{\nu_{i}}r_{t}^{\star}\Big]-\textstyle\sum_{t=\tau_{i-1}}^{\nu_{i}}r_{t}^{\pi}\Bigg)-\Bigg(\mathbb{E}\Big[\textstyle\sum_{t=\tau_{i-1}}^{\nu_{i}}r_{t}^{\star}\Big]-\mathbb{E}\Big[\textstyle\sum_{t=\tau_{i-1}}^{\nu_{i}}r_{t}^{\mathrm{seg}}\Big]\Bigg), where the first term corresponds to the standard regret and the second to the standard regret of the segment oracle. We denote the standard regret over this interval by R(\tau_{i-1},\nu_{i}) and analyze it first. For every i , conditioning on the previous successful detection \overline{F}_{i-1}D_{i-1} , we decompose the regret depending on whether a false alarm occurs: \displaystyle\mathbb{E}\!\left[R\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i-1}D_{i-1}\right] \displaystyle=\mathbb{E}\!\left[R\left(\tau_{i-1},\nu_{i}\right)\middle|F_{i}\overline{F}_{i-1}D_{i-1}\right]\mathbb{P}\!\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right) (41a) \displaystyle\quad+\mathbb{E}\!\left[R\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right]\mathbb{P}\!\left(\overline{F}_{i}\middle|\overline{F}_{i-1}D_{i-1}\right) (41b) \displaystyle\leq T\cdot\mathbb{P}\!\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right)+\mathbb{E}\!\left[R\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right] (41c) \displaystyle\leq T\cdot\mathbb{P}\!\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right)+2\alpha\sqrt{s_{i}}+\sum_{i=1}^{M}C_{i}, (41d) Next, subtracting the segment–oracle standard regret on the same interval cancels out the base regret terms \sum_{i=1}^{M}C_{i} , leaving only the exploration and detection contributions. This yields the desired excess regret bound stated in Lemma B.3 . ∎ Theorem B.4 (Excess-regret bound) . For any base solver \mathcal{B} and change detector \mathcal{D} , the excess regret of Algorithm 1 satisfies \mathcal{R}_{\mathrm{excess}}(T)\leq 2\alpha\sqrt{MT}+\sum^{M-1}_{i=1}\mathbb{E}\left[\tau_{i}-\nu_{i}\middle|D_{i}\overline{F}_{i}D_{i-1}\overline{F}_{i-1}\right]+T\sum^{M}_{i=1}\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right)+T\sum^{M-1}_{i=1}\mathbb{P}\left(\overline{D}_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right), (42) Proof. Recall that R_{\mathrm{excess}}(r,s):=\mathbb{E}[\textstyle\sum_{t=1}^{T}r_{t}^{\mathrm{seg}}]-\textstyle\sum_{t=1}^{T}r_{t}^{\pi} , then \mathcal{R}_{\mathrm{excess}}\left(T\right)=\mathbb{E}\left[R_{\mathrm{excess}}\left(1,T\right)\right] . We have \displaystyle\mathcal{R}_{\mathrm{excess}}\left(T\right) \displaystyle=\mathbb{E}\left[R_{\mathrm{excess}}\left(1,T\right)\right] (43a) \displaystyle=\mathbb{E}\left[R_{\mathrm{excess}}\left(1,T\right)\middle|\overline{F}_{0}D_{0}\right] (43b) \displaystyle\leq\mathbb{E}\left[R_{\mathrm{excess}}\left(1,\nu_{1}\right)\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right]+\mathbb{E}\left[R_{\mathrm{excess}}\left(\nu_{1},T\right)\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right]+T\cdot\mathbb{P}\left(F_{1}\middle|\overline{F}_{0}D_{0}\right) (43c) \displaystyle\leq 2\alpha\sqrt{\left(\nu_{1}-\nu_{0}\right)}+\mathbb{E}\left[R\left(\nu_{1},T\right)\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right]+T\cdot\mathbb{P}\left(F_{1}\middle|\overline{F}_{0}D_{0}\right), (43d) where equation 43b holds because \tau_{0}=0 , equation 43c is due to the law of total expectation and some trivial bounds, and equation 43d follows from Lemmas B.9 . The third term in equation 43d is then further bounded as follows: \displaystyle\hskip-20.0pt\mathbb{E}\left[R_{\mathrm{excess}}\left(\nu_{1},T\right)\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right] \displaystyle\leq\mathbb{E}\left[R_{\mathrm{excess}}\left(\nu_{1},T\right)\middle|D_{1}\overline{F}_{1}\overline{F}_{0}D_{0}\right]+T\cdot\left(1-\mathbb{P}\left(D_{1}\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right)\right) (44a) \displaystyle\hskip-60.0pt\leq\mathbb{E}\left[R_{\mathrm{excess}}\left(\nu_{1},T\right)\middle|D_{1}\overline{F}_{1}\overline{F}_{0}D_{0}\right]+T\cdot\mathbb{P}\left(\overline{D}_{1}\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right) (44b) \displaystyle\hskip-60.0pt=\mathbb{E}\left[R_{\mathrm{excess}}\left(\tau_{1},T\right)\middle|D_{1}\overline{F}_{1}\overline{F}_{0}D_{0}\right]+\mathbb{E}\left[R\left(\nu_{1},\tau_{1}\right)\middle|D_{1}\overline{F}_{1}\overline{F}_{0}D_{0}\right]+T\cdot\mathbb{P}\left(\overline{D}_{1}\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right) (44c) \displaystyle\hskip-60.0pt\leq\mathbb{E}\left[R_{\mathrm{excess}}\left(\tau_{1},T\right)\middle|\overline{F}_{1}D_{1}\right]+\mathbb{E}\left[\tau_{1}-\nu_{1}\middle|\overline{F}_{1}D_{1}\overline{F}_{0}D_{0}\right]+T\cdot\mathbb{P}\left(\overline{D}_{1}\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right) (44d) \displaystyle\hskip-60.0pt\leq\mathbb{E}\left[R_{\mathrm{excess}}\left(\tau_{1},T\right)\middle|\overline{F}_{1}D_{1}\right]+\mathbb{E}\left[\tau_{1}-\nu_{1}\middle|\overline{F}_{1}D_{1}\right]+T\cdot\mathbb{P}\left(\overline{D}_{1}\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right), (44e) where equation 44a applies the law of total expectation and some trivial bounds. From here, we can set up the following recursion: \displaystyle\mathbb{E}\left[R_{\mathrm{excess}}\left(1,T\right)\right]=\mathbb{E}\left[R_{\mathrm{excess}}\left(1,T\right)\middle|\overline{F}_{0}D_{0}\right] (45a) \displaystyle\leq\mathbb{E}\left[R_{\mathrm{excess}}\left(\tau_{1},T\right)\middle|\overline{F}_{1}D_{1}\right]+2\alpha\sqrt{s_{1}-1}+\mathbb{E}\left[\tau_{1}-\nu_{1}\middle|\overline{F}_{1}D_{1}\right] (45b) \displaystyle\hskip 60.0pt+T\cdot\mathbb{P}\left(F_{1}\middle|\overline{F}_{0}D_{0}\right)+T\cdot\mathbb{P}\left(\overline{D}_{1}\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right) (45c) \displaystyle\leq\mathbb{E}\left[R_{\mathrm{excess}}\left(\tau_{2},T\right)\middle|\overline{F}_{2}D_{2}\right]+2\alpha\sum^{2}_{i=1}\sqrt{s_{i}-1} (45d) \displaystyle+\sum^{2}_{i=1}\mathbb{E}\left[\tau_{i}-\nu_{i}\middle|\overline{F}_{i-1}D_{i-1}\right]+T\sum^{2}_{i=1}\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right)+T\sum^{2}_{i=1}\mathbb{P}\left(\overline{D}_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (45e) \displaystyle\hskip 150.0pt\vdots \displaystyle\leq 2\alpha\sum^{M}_{i=1}\sqrt{s_{i}}+\sum^{M-1}_{i=1}\mathbb{E}\left[\tau_{i}-\nu_{i}\middle|\overline{F}_{i-1}D_{i-1}\right] (45f) \displaystyle\hskip 60.0pt+T\sum^{M}_{i=1}\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right)+T\sum^{M-1}_{i=1}\mathbb{P}\left(\overline{D}_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (45g) \displaystyle\leq 2\alpha\sqrt{MT}+\sum^{M-1}_{i=1}\mathbb{E}\left[\tau_{i}-\nu_{i}\middle|\overline{F}_{i-1}D_{i-1}\right] (45h) \displaystyle\hskip 60.0pt+T\sum^{M}_{i=1}\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right)+T\sum^{M-1}_{i=1}\mathbb{P}\left(\overline{D}_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (45i) where equation 45h follows from the Cauchy–Schwarz inequality \displaystyle\left(\sum^{M}_{i=1}\sqrt{s_{i}}\right)^{2}\leq\left(\sum^{M}_{i=1}s_{i}\right)\left(\sum^{M}_{i=1}1\right)=M\sum^{M}_{i=1}s_{i}=MT, (46a) and the fact that \sum^{M}_{i=1}s_{i}=T . This completes the proof. ∎ B.2 Proof of One-State Special Case With the general regret bound in Theorem B.4 , a regret bound of the change detector with the proposed diminishing exploration can be obtained by bounding \mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right) , \mathbb{P}\left(D_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) , and \mathbb{E}\left[\tau_{i}-\nu_{i}\middle|\overline{F}_{i}D_{i}\overline{F}_{i-1}D_{i-1}\right] . In what follows, we adopt window-based change detectors (Algorithm A ) as the basis for our subsequent analysis. First, in Lemma B.5 , we show that the probability of false alarm is very small; thereby, its contribution to the regret is negligible. Lemma B.5 (Probability of false alarm) . Under Algorithm 1 with parameter in Equations 3 and 4 , we have \mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right)\leq wK\left(1-\left(1-\exp\left(-2b^{2}/w\right)\right)^{\left\lfloor T/w\right\rfloor}\right)\leq\frac{1}{T}. (47) Proof. Suppose that at time t , we have gathered w samples of arm k\in{\mathcal{K}} , namely Y_{k,1},Y_{k,2},\ldots,Y_{k,w} , for change detection in line 17 of Algorithm 1 , and we define S_{k,t}=\sum^{w}_{\ell=w/2+1}Y_{k,\ell}-\sum^{w/2}_{\ell=1}Y_{k,\ell}. (48) Note that S_{k,t}=0 when there is insufficient (less than w ) samples to trigger the change detection algorithm. By definition, we have \tau_{k,i}=\inf\{t\geq\tau_{i-1}+w:\left\lvert S_{k,t}\right\rvert>b\}. (49) Given that the events D_{i-1} and \bar{F}_{i-1} hold, we define \tau_{k,i} as the first detection time of the k -th arm after \nu_{i} . Clearly, \tau_{i}=\min_{k\in{\mathcal{K}}}\left\{\tau_{k,i}\right\} as Algorithm 1 would reset every time a change is detected. Using the union bound, we have \displaystyle\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right)= \displaystyle\mathbb{P}\left(\max_{k\in\mathcal{K}}\sum_{t=\tau_{i-1}+1}^{\nu_{i}}\bm{1}_{\left\{A_{t}=k\right\}}\geq w,F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right) (50a) \displaystyle+\mathbb{P}\left(\max_{k\in\mathcal{K}}\sum_{t=\tau_{i-1}+1}^{\nu_{i}}\bm{1}_{\left\{A_{t}=k\right\}}b\}. (51) Clearly, \tau_{k,i}=\min\{\tau_{k,i}^{(0)},\ldots,\tau_{k,i}^{(w-1)}\} . Let us define, for any 0\leq j\leq w-1 , \xi_{k,i}^{(j)}=\frac{\left(\tau_{k,i}^{(j)}-j-\tau_{i-1}\right)}{w}. (52) Note that condition on the events D_{i-1} and \bar{F}_{i-1} , \xi_{k,i}^{(j)} is a geometric random variable with parameter p:=\mathbb{P}(\left\lvert S_{k,t}\right\rvert>b) , because when fixing j , there is no overlap between the samples in the current window and the next. \mathbb{P}\left(\tau_{k,i}^{(j)}=\tau_{i-1}+nw+j\middle|\overline{F}_{i-1}D_{i-1},\sum_{t=\tau_{i-1}+1}^{\nu_{i}}\bm{1}_{\left\{A_{t}=k\right\}}\geq w\right)\\ =\mathbb{P}\left(\xi_{k,i}=n\middle|\overline{F}_{i-1}D_{i-1},\sum_{t=\tau_{i-1}+1}^{\nu_{i}}\bm{1}_{\left\{A_{t}=k\right\}}\geq w\right)=p(1-p)^{n-1}. (53) Here, the inclusion of subsequent events as conditions should not impact the results, as when entering the change detection algorithm, those events have already occurred. Moreover, by union bound, we have that for any k\in{\mathcal{K}} , \displaystyle\mathbb{P}\left(\tau_{k,i}\leq\nu_{i}\middle|\overline{F}_{i-1}D_{i-1},\sum_{t=\tau_{i-1}+1}^{\nu_{i}}\bm{1}_{\left\{A_{t}=k\right\}}\geq w\right) \displaystyle\leq w\left(1-\left(1-p\right)^{\left\lfloor\left(\nu_{i}-\tau_{i-1}\right)/w\right\rfloor}\right) (54a) \displaystyle\leq w\left(1-(1-p)^{\left\lfloor T/w\right\rfloor}\right). (54b) We further use the McDiarmid’s inequality and the union bound to show that \displaystyle p \displaystyle=\mathbb{P}\left(\left\lvert S_{k,t}\right\rvert>b\right)=\mathbb{P}\left(S_{k,t}>b\right)+\mathbb{P}\left(S_{k,t}<-b\right) (55a) \displaystyle\leq 2\cdot\exp\left(-\frac{2b^{2}}{w}\right). (55b) Using the result in equation 54b and equation 55b into equation 50g , \displaystyle\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right)\leq\sum^{K}_{k=1}w\left(1-\left(1-2\exp\left(-\frac{2b^{2}}{w}\right)\right)^{\left\lfloor T/w\right\rfloor}\right) (56a) \displaystyle=wK\left(1-\left(1-2\exp\left(-\frac{2b^{2}}{w}\right)\right)^{\left\lfloor T/w\right\rfloor}\right). (56b) Moreover, applying \left(1-x\right)^{a}>1-ax for any a>1 and 00 , under the Algorithm 1 , we have \mathbb{P}\left(D_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right)\geq 1-\frac{1}{T}. (59) Proof. \displaystyle\mathbb{P}\left(D_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right)= \displaystyle\mathbb{P}\left(\tau_{i}\leq\nu_{i}+h_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (60a) \displaystyle\geq \displaystyle\max_{t\in\left\{\nu_{i}+1,\ldots,\nu_{i}+h_{i}\right\}}\mathbb{P}\left(S_{\tilde{k},t}>b\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (60b) \displaystyle\geq \displaystyle\max_{j\in\left\{0,\ldots,w/2\right\}}\left(1-2\exp\left(-\frac{(j\left\lvert\delta^{(i)}_{\tilde{k}}\right\rvert-b)^{2}}{w}\right)\right) (60c) \displaystyle= \displaystyle 1-2\exp\left(-\frac{(w|\delta^{(i)}_{\tilde{k}}|/2-b)^{2}}{w}\right) (60d) \displaystyle\geq \displaystyle 1-2\exp\left(-\frac{wc^{2}}{4}\right). (60e) where S_{\tilde{k},t} is defined in equation 48 , equation 60c follows from the McDiarmid’s inequality, and equation 60d is due to the fact that the maximum value is attained when j=w/2 . Last, equation 60e is true for any choice of w,b and c such that \delta^{(i)}_{\tilde{k}}\geq 2b/w+c holds. We thus set w and b as in equation 3 and equation 4 , respectively, and choose c=2\sqrt{\log\left(2T\right)/w} , which leads to \mathbb{P}\left(D_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right)\geq 1-1/T . ∎ Lemma B.7 further bounds the expected detection delay in the situation where the change detection algorithm successfully detects the change within the desired interval. Lemma B.7 (Expected detection delay) . Consider a piecewise-stationary bandit environment. For any \bm{\mu}^{(i)},\bm{\mu}^{(i+1)}\in\left[0,1\right]^{K} with parameters chosen in equation 3 and equation 4 and h_{i}=\left\lceil w\left(\frac{K}{2\alpha}+1\right)\sqrt{s_{i}+1}+\frac{w^{2}}{4}\left(\frac{K}{2\alpha}+1\right)^{2}\right\rceil, (61) for some k\in{\mathcal{K}},i\geq 1 and c>0 , under the Algorithm 1 , we have \mathbb{E}\left[\tau_{i}-\nu_{i}\middle|\overline{F}_{i}D_{i}\overline{F}_{i-1}D_{i-1}\right]\leq h_{i}. (62) Proof. For any 1\leq i\leq M , we have \displaystyle\mathbb{E}\left[\tau_{i}-\nu_{i}\middle|\overline{F}_{i}D_{i}\overline{F}_{i-1}D_{i-1}\right] \displaystyle=\sum^{h_{i}}_{j=1}\mathbb{P}\left(\tau_{i}\geq\nu_{i}+j\middle|\overline{F}_{i}D_{i}\overline{F}_{i-1}D_{i-1}\right)\leq h_{i}. (63a) ∎ Plugging the bounds in Lemmas B.5 , B.6 and B.7 into Theorem B.4 shows the following regret bound in Corollary B.8 . Corollary B.8 . Combining Algorithm 1 (diminishing exploration with resets) with the base solver \mathcal{B} and Algorithm 2 with parameters (w,b) given in Equations 3 and 4 , the excess regret is upper-bounded as \mathcal{R}_{\mathrm{excess}}(T)\leq 2\alpha\sqrt{MT}+w\left(\frac{K}{2\alpha}+1\right)\sqrt{M\left(T+M\right)}+\frac{w^{2}M}{4}\left(\frac{K}{2\alpha}+1\right)^{2}+2M. (64) By setting \alpha=c\sqrt{K\log{\left(KT\right)}} for some constant c , the expected regret is upper-bounded by \mathcal{O}(\sqrt{KMT\log{T}}) . B.2.1 Proof of standard regret in one-state case Define R\left(r,s\right):=\sum^{s}_{t=r}\max_{k\in{\mathcal{K}}}\mathbb{E}\left[X_{k,t}\right]-X_{A_{t},t} be the regret accumulated during r and s . In the next lemma, we provide an upper bound on the regret accumulated from the \left(i-1\right) -th alarm time to the end of \left(i-1\right) -th segment, given that the previous change was successfully detected. Lemma B.9 (Regret bound with stationary bandit) . Consider a stationary bandit interval with \nu_{i-1}<\tau_{i-1}<\nu_{i} . Condition on the successful detection events \overline{F}_{i-1} and D_{i-1} , the expected regret accumulated during \left(\tau_{i-1},\nu_{i}\right) can be bounded by \mathbb{E}\left[R\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i-1}D_{i-1}\right]\leq\tilde{C}_{i}+2\alpha\sqrt{s_{i}}+T\cdot\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right), (65) where \tilde{C}_{i}=8\sum_{\Delta^{\left(i\right)}_{k}>0}\frac{\log T}{\Delta^{\left(i\right)}_{k}}+\left(\frac{5}{2}+\frac{\pi^{2}}{3}+K\right)\sum^{K}_{k=1}\Delta^{\left(i\right)}_{k} . Proof. For every i , we have \displaystyle\mathbb{E}\left[R\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i-1}D_{i-1}\right] \displaystyle=\mathbb{E}\left[R\left(\tau_{i-1},\nu_{i}\right)\middle|F_{i}\overline{F}_{i-1}D_{i-1}\right]\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right) (66a) \displaystyle\hskip-20.0pt+\mathbb{E}\left[R\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right]\mathbb{P}\left(\overline{F}_{i}\middle|\overline{F}_{i-1}D_{i-1}\right) (66b) \displaystyle\hskip-20.0pt\leq T\cdot\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right)+\mathbb{E}\left[R\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right]. (66c) Now, define N_{k}\left(t_{1},t_{2}\right):=\sum^{t_{2}}_{t=t_{1}}\bm{1}_{\left\{A_{t}=k\right\}} to be the number of times that arm k is selected by Algorithm 1 from t_{1} to t_{2} . Note that \mathbb{E}\left[R\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right]=\sum_{\Delta^{\left(i\right)}_{k}>0}\Delta^{\left(i\right)}_{k}\cdot\mathbb{E}\left[N_{k}\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right]. (67) To bound the second term of equation 66c , we further bound N_{k}\left(\tau_{i-1},\nu_{i}\right) as follows, \displaystyle N_{k}\left(\tau_{i-1},\nu_{i}\right)= \displaystyle\sum^{\nu_{i}}_{t=\tau_{i-1}+1}\bm{1}_{\left\{A_{t}=k,\tau_{i}>\nu_{i},N_{k}\left(\tau_{i-1},\nu_{i}\right)\nu_{i},N_{k}\left(\tau_{i-1},\nu_{i}\right)\geq l\right\}} (68a) \displaystyle\leq \displaystyle l+N_{DE,k}\left(\nu_{i}-\tau_{i-1}\right)+\sum^{\nu_{i}}_{t=\tau_{i-1}+1}\bm{1}_{\left\{k=\argmax_{k\in{\mathcal{K}}}\mathrm{UCB}_{k\in{\mathcal{K}}},\tau_{i}>\nu_{i},N_{k}\left(\tau_{i-1},\nu_{i}\right)\geq l\right\}} (68b) \displaystyle\leq \displaystyle l+\frac{2\alpha\sqrt{\nu_{i}-\tau_{i-1}}}{K}+\frac{3}{2}+\sum^{\nu_{i}}_{t=\tau_{i-1}+1}\bm{1}_{\left\{k=\argmax_{k\in{\mathcal{K}}}\mathrm{UCB}_{k\in{\mathcal{K}}},\tau_{i}>\nu_{i},N_{k}\left(\tau_{i-1},\nu_{i}\right)\geq l\right\}} (68c) \displaystyle\leq \displaystyle l+\frac{2\alpha\sqrt{s_{i}}}{K}+\frac{3}{2}+\sum^{\nu_{i}}_{t=\tau_{i-1}+1}\bm{1}_{\left\{k=\argmax_{k\in{\mathcal{K}}}\mathrm{UCB}_{k\in{\mathcal{K}}},\tau_{i}>\nu_{i},N_{k}\left(\tau_{i-1},\nu_{i}\right)\geq l\right\}}, (68d) Equation 68c follows from Lemma B.1 . Setting l=\left\lceil 8\log T/\left(\Delta^{(i)}_{k}\right)^{2}\right\rceil , and following the same steps as in the proof of Theorem 1 of 2 , we arrive at \mathbb{E}\left[N_{k}\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right]\leq\frac{2\alpha\sqrt{s_{i}}}{K}+\frac{8\log T}{\left(\Delta^{(i)}_{k}\right)^{2}}+\frac{5}{2}+\frac{\pi^{2}}{3}+K. (69) Putting everything together completes the proof. ∎ The term \tilde{C}_{i} in equation 65 involves \Delta_{k}^{(i)} . In what follows, we establish an upper bound of \tilde{C_{i}} that avoids this dependence. Lemma B.10 (Regret bound without involving \Delta_{k}^{(i)} ) . Consider a stationary bandit interval with \nu_{i-1}<\tau_{i-1}<\nu_{i} . Condition on the successful detection events \overline{F}_{i-1} and D_{i-1} , and let \Delta>0 , the expected regret accumulated during \left(\tau_{i-1},\nu_{i}\right) can be bounded by \mathbb{E}\left[R\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i-1}D_{i-1}\right]\leq 2\alpha\sqrt{s_{i}}+\frac{8K\log{T}}{\Delta}+\Delta\cdot s_{i}+\left(\frac{5}{2}+\frac{\pi^{2}}{3}+K\right)K+T\cdot\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right). (70) Moreover, by selecting \Delta=\sqrt{MK\log{T}/T} , we have \mathbb{E}\left[R\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i-1}D_{i-1}\right]\leq 2\alpha\sqrt{s_{i}}+8\sqrt{\frac{KT\log{T}}{M}}+\sqrt{\frac{MK\log{T}}{T}}s_{i}+\left(\frac{5}{2}+\frac{\pi^{2}}{3}+K\right)K+T\cdot\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right). (71) Proof. We rewite the equation 67 as follows, \displaystyle\mathbb{E}\left[R\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right] \displaystyle=\sum_{\Delta^{\left(i\right)}_{k}>0}\Delta^{\left(i\right)}_{k}\cdot\mathbb{E}\left[N_{k}\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right] (72a) \displaystyle=\sum_{\Delta^{\left(i\right)}_{k}\geq\Delta}\Delta^{\left(i\right)}_{k}\cdot\mathbb{E}\left[N_{k}\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right] (72b) \displaystyle+\sum_{\Delta^{\left(i\right)}_{k}<\Delta}\Delta^{\left(i\right)}_{k}\cdot\mathbb{E}\left[N_{k}\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right]\hskip-241.84842pt (72c) \displaystyle\leq\sum_{\Delta^{\left(i\right)}_{k}\geq\Delta}\left[\frac{2\alpha\sqrt{s_{i}}}{K}\cdot\Delta^{(i)}_{k}+\frac{8\log{T}}{\Delta^{\left(i\right)}_{k}}+\left(\frac{5}{2}+\frac{\pi^{2}}{3}+K\right)\cdot\Delta^{(i)}_{k}\right]+\Delta\cdot s_{i} (72d) \displaystyle\leq 2\alpha\sqrt{s_{i}}+\sum_{\Delta^{(i)}_{k}\geq\Delta}\frac{8\log{T}}{\Delta^{\left(i\right)}_{k}}+\left(\frac{5}{2}+\frac{\pi^{2}}{3}+K\right)\sum_{\Delta^{(i)}_{k}\geq\Delta}\Delta^{(i)}_{k}+\Delta\cdot s_{i} (72e) \displaystyle\leq 2\alpha\sqrt{s_{i}}+\frac{8K\log{T}}{\Delta}+\left(\frac{5}{2}+\frac{\pi^{2}}{3}+K\right)K+\Delta\cdot s_{i}. (72f) Equations 72b to 72d are derived using equation 69 , while the transition from 72c to 72d leverages the inequalities \Delta>\Delta^{(i)}_{k} and s_{i}>\mathbb{E}\left[N_{k}\left(\tau_{i-1},\nu_{i}\right)\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right] . The second part of the lemma follows straightforwardly by plugging \Delta=\sqrt{MK\log{T}/T} into then the equation 72f . ∎ Theorem B.11 can then be proved by recursively applying Lemma B.9 . Theorem B.11 (Standard Regret bound of M-UCB) . Combining Algorithms 1 and 2 with the parameters in Equation 3 , and Equation 4 achieves the expected regret upper bound as follows: \mathbb{E}\left[R\left(1,T\right)\right]\leq\underbrace{9\sqrt{MKT\log{T}}+\left(\frac{5}{2}+\frac{\pi^{2}}{3}+K\right)MK}_{(a)}+\underbrace{2\alpha\sqrt{MT}}_{(b)}+\underbrace{w\left(\frac{K}{2\alpha}+1\right)\sqrt{M\left(T+M\right)}}_{(c)}\\ +\underbrace{\frac{w^{2}M}{4}\left(\frac{K}{2\alpha}+1\right)^{2}}_{(c)}+\underbrace{2M}_{(d)}. (73) By setting \alpha=c\sqrt{K\log{\left(KT\right)}} for some constant c , the expected regret is upper-bounded by \mathcal{O}(\sqrt{KMT\log{T}}) . Proof. Recall that R\left(r,s\right)=\sum^{s}_{t=r}\max_{k\in{\mathcal{K}}}\mathbb{E}\left[X_{k,t}\right]-X_{A_{t},t} , then {\mathcal{R}}\left(T\right)=\mathbb{E}\left[R\left(1,T\right)\right] . We have \displaystyle{\mathcal{R}}\left(T\right) \displaystyle=\mathbb{E}\left[R\left(1,T\right)\right] (74a) \displaystyle=\mathbb{E}\left[R\left(1,T\right)\middle|\overline{F}_{0}D_{0}\right] (74b) \displaystyle\leq\mathbb{E}\left[R\left(1,\nu_{1}\right)\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right]+\mathbb{E}\left[R\left(\nu_{1},T\right)\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right]+T\cdot\mathbb{P}\left(F_{1}\middle|\overline{F}_{0}D_{0}\right) (74c) \displaystyle\leq\tilde{C}_{1}+2\alpha\sqrt{\left(\nu_{1}-\nu_{0}\right)}+\mathbb{E}\left[R\left(\nu_{1},T\right)\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right]+T\cdot\mathbb{P}\left(F_{1}\middle|\overline{F}_{0}D_{0}\right), (74d) where equation 74b holds because \tau_{0}=0 , equation 74c is due to the law of total expectation and some trivial bounds, and equation 74d follows from Lemmas B.9 . The third term in equation 74d is then further bounded as follows: \displaystyle\hskip-20.0pt\mathbb{E}\left[R\left(\nu_{1},T\right)\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right] \displaystyle\leq\mathbb{E}\left[R\left(\nu_{1},T\right)\middle|D_{1}\overline{F}_{1}\overline{F}_{0}D_{0}\right]+T\cdot\left(1-\mathbb{P}\left(D_{1}\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right)\right) (75a) \displaystyle\hskip-60.0pt\leq\mathbb{E}\left[R\left(\nu_{1},T\right)\middle|D_{1}\overline{F}_{1}\overline{F}_{0}D_{0}\right]+T\cdot\mathbb{P}\left(\overline{D}_{1}\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right) (75b) \displaystyle\hskip-60.0pt=\mathbb{E}\left[R\left(\tau_{1},T\right)\middle|D_{1}\overline{F}_{1}\overline{F}_{0}D_{0}\right]+\mathbb{E}\left[R\left(\nu_{1},\tau_{1}\right)\middle|D_{1}\overline{F}_{1}\overline{F}_{0}D_{0}\right]+T\cdot\mathbb{P}\left(\overline{D}_{1}\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right) (75c) \displaystyle\hskip-60.0pt\leq\mathbb{E}\left[R\left(\tau_{1},T\right)\middle|\overline{F}_{1}D_{1}\right]+\mathbb{E}\left[\tau_{1}-\nu_{1}\middle|\overline{F}_{1}D_{1}\overline{F}_{0}D_{0}\right]+T\cdot\mathbb{P}\left(\overline{D}_{1}\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right) (75d) \displaystyle\hskip-60.0pt\leq\mathbb{E}\left[R\left(\tau_{1},T\right)\middle|\overline{F}_{1}D_{1}\right]+\mathbb{E}\left[\tau_{1}-\nu_{1}\middle|\overline{F}_{1}D_{1}\right]+T\cdot\mathbb{P}\left(\overline{D}_{1}\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right), (75e) where equation 75a applies the law of total expectation and some trivial bounds.From here, we can set up the following recursion: \displaystyle\mathbb{E}\left[R\left(1,T\right)\right]=\mathbb{E}\left[R\left(1,T\right)\middle|\overline{F}_{0}D_{0}\right] (76a) \displaystyle\leq\mathbb{E}\left[R\left(\tau_{1},T\right)\middle|\overline{F}_{1}D_{1}\right]+\tilde{C}_{1}+2\alpha\sqrt{s_{1}-1}+\mathbb{E}\left[\tau_{1}-\nu_{1}\middle|\overline{F}_{1}D_{1}\right] (76b) \displaystyle\hskip 60.0pt+T\cdot\mathbb{P}\left(F_{1}\middle|\overline{F}_{0}D_{0}\right)+T\cdot\mathbb{P}\left(\overline{D}_{1}\middle|\overline{F}_{1}\overline{F}_{0}D_{0}\right) (76c) \displaystyle\leq\mathbb{E}\left[R\left(\tau_{2},T\right)\middle|\overline{F}_{2}D_{2}\right]+\sum^{2}_{i=1}\tilde{C}_{i}+2\alpha\sum^{2}_{i=1}\sqrt{s_{i}-1} (76d) \displaystyle+\sum^{2}_{i=1}\mathbb{E}\left[\tau_{i}-\nu_{i}\middle|\overline{F}_{i-1}D_{i-1}\right]+T\sum^{2}_{i=1}\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right)+T\sum^{2}_{i=1}\mathbb{P}\left(\overline{D}_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (76e) \displaystyle\hskip 150.0pt\vdots \displaystyle\leq\sum^{M}_{i=1}\tilde{C}_{i}+2\alpha\sum^{M}_{i=1}\sqrt{s_{i}}+\sum^{M-1}_{i=1}\mathbb{E}\left[\tau_{i}-\nu_{i}\middle|\overline{F}_{i-1}D_{i-1}\right] (76f) \displaystyle\hskip 60.0pt+T\sum^{M}_{i=1}\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right)+T\sum^{M-1}_{i=1}\mathbb{P}\left(\overline{D}_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (76g) \displaystyle\leq\sum^{M}_{i=1}\tilde{C}_{i}+2\alpha\sqrt{MT}+\sum^{M-1}_{i=1}\mathbb{E}\left[\tau_{i}-\nu_{i}\middle|\overline{F}_{i-1}D_{i-1}\right] (76h) \displaystyle\hskip 60.0pt+T\sum^{M}_{i=1}\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right)+T\sum^{M-1}_{i=1}\mathbb{P}\left(\overline{D}_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (76i) where equation 76h follows from the Cauchy–Schwarz inequality \displaystyle\left(\sum^{M}_{i=1}\sqrt{s_{i}}\right)^{2}\leq\left(\sum^{M}_{i=1}s_{i}\right)\left(\sum^{M}_{i=1}1\right)=M\sum^{M}_{i=1}s_{i}=MT, (77a) Finally, by lemma B.10 , we know that \displaystyle\sum^{M}_{i}\tilde{C}_{i} \displaystyle\leq\sum^{M}_{i=1}\left[8\sqrt{\frac{KT\log{T}}{M}}+\left(\frac{5}{2}+\frac{\pi^{2}}{3}+K\right)K+\sqrt{\frac{MK\log{T}}{T}}\cdot s_{i}\right] (78a) \displaystyle=8\sqrt{MKT\log{T}}+\left(\frac{5}{2}+\frac{\pi^{2}}{3}+K\right)MK+\sqrt{\frac{MK\log{T}}{T}}\cdot\sum^{M}_{i=1}s_{i}. (78b) \displaystyle=8\sqrt{MKT\log{T}}+\left(\frac{5}{2}+\frac{\pi^{2}}{3}+K\right)MK+\sqrt{\frac{MK\log{T}}{T}}\cdot T. (78c) \displaystyle=8\sqrt{MKT\log{T}}+\left(\frac{5}{2}+\frac{\pi^{2}}{3}+K\right)MK+\sqrt{MKT\log{T}} (78d) \displaystyle=9\sqrt{MKT\log{T}}+\left(\frac{5}{2}+\frac{\pi^{2}}{3}+K\right)MK. (78e) Then, plugging equation 78e into equation 76h completes the proof of Theorem B.11 . ∎ B.3 Proof of General Case To handle the temporal dependence induced by the Markovian dynamics, we leverage a concentration inequality for ergodic Markov chains. Assumption B.12 ensures the existence of unique stationary distributions for each arm in each segment, allowing us to apply the following Hoeffding-type bound for Markovian rewards 6 , which plays a key role in bounding the probabilities of false alarms \mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right) and successful detections \mathbb{P}\left(D_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) . Assumption B.12 . All Markov chains \mathcal{M}_{k}^{(i)}=(P_{k}^{(i)},R_{k}^{(i)}) are ergodic. This ensures the existence of a unique steady-state distribution d_{k}^{(i)} for each arm k in segment i , satisfying d_{k}^{(i)}=d_{k}^{(i)}P_{k}^{(i)} with \sum_{s\in\mathcal{S}}d_{k}^{(i)}(s)=1 . We then define the steady-state arm mean as \bar{\mu}_{k}^{(i)}:=d_{k}^{(i)}R_{k}^{(i)} . Lemma B.13 (Hoeffding Bound for Markovian Reward 6 ) . Let \mathcal{M} be an ergodic Markov chain with state space \mathcal{S} and stationary distribution d . Let L=T(\epsilon) be its \varepsilon -mixing time for \varepsilon\leq 1/8 . Let (V_{1},\cdots,V_{t}) denote a t -step random walk on \mathcal{M} starting from an initial distribution \phi . Let f_{\ell}:\mathcal{S}\mapsto[0,1] be a weight function at \ell time step such that expected weighted \mathbb{E}_{v\leftarrow d}=\mu for all \ell . Define total weight walk X\triangleq\sum^{t}_{\ell=1}f_{\ell}(V_{\ell}) . There exists some constant c (which is independent to d,\delta,\epsilon ) and let 0\leq\delta\leq 1 such that \displaystyle\mathbb{P}[X\geq\left(1+\delta\right)\mu t] \displaystyle\leq c{\lVert\phi\rVert}_{d}\exp{\left(-\delta^{2}\mu t/\left(72L\right)\right)} (79) \displaystyle\mathbb{P}[X\leq\left(1-\delta\right)\mu t] \displaystyle\leq c{\lVert\phi\rVert}_{d}\exp{\left(-\delta^{2}\mu t/\left(72L\right)\right)}. Using Lemma B.13 , we now control the probability of false alarms within each stationary segment. The following lemma shows that, with appropriate choices of the detection window and threshold parameters, the probability of triggering a false alarm is negligible. Lemma B.14 (Probability of false alarm) . Under Algorithm 2 with the parameter choices specified in Equations 14 and 15 , the probability of a false alarm in each stationary segment satisfies \mathbb{P}\!\left(F_{i}\,\middle|\,\overline{F}_{i-1}D_{i-1}\right)\;\leq\;\frac{\epsilon\lVert\varphi\rVert_{d}+1}{T}, (80) where \epsilon>0 is an arbitrarily small constant, \varphi is the initial state distribution, and \lVert\varphi\rVert_{d} is the corresponding d -norm. Proof. We formalize this analysis by defining an equivalent function S_{k,t} and establishing the stopping conditions necessary for detecting such events. The function S_{k,t} serves as a proxy for the behavior of Algorithm 2 and is defined as follows: S_{k,t}=\sum_{\ell=w/2+1}^{w}Z_{k,\ell}-\sum_{\ell=1}^{w/2}Z_{k,\ell},\quad\text{for any}\quad k\in K,t\geq w, (81) where w is window size. To formalize the conditions for triggering a change detection, we define the stopping time: \lvert S_{k,t}\rvert\geq b , which is equalivent to the change alerts in Algorithm 2 . To facilitate analysis, we divide the stopping time events into w subsequences indexed by j with each subsequence corresponding to a distinct offset. The stopping time for the j -th subsequence is given by: \tau_{k,i}^{(j)}:=\inf\left\{t=\tau_{i-1}+j+nw,n\in\mathbb{Z}^{+}:\left|S_{k,t}\right|>b\right\}, (82) where b is the detection threshold. By dividing the stopping time events into these w subsequences, we ensure that the samples within each subsequences are independent over w -time steps. This independence is achieved because the samples are aggregated over disjoint time intervals defined by the periodic offset j . Such independence is crucial for applying concentration inequalities later in the analysis. Clearly, \tau_{k,i}=\min\left\{\tau_{k,i}^{(0)},\ldots,\tau_{k,i}^{(w-1)}\right\} . Let us define \xi_{k,i}^{(j)} \xi_{k,i}^{(j)}=\frac{\left(\tau_{k,i}^{(j)}-j-\tau_{k,i-1}\right)}{w},\quad\text{for any}\quad 0\leq j\leq w-1. (83) Note that condition on the events D_{i-1} and F_{i-1},\xi_{k,i}^{(j)} is a geometric random variable with parameter p:=\mathbb{P}\left(\left|S_{k,t}\right|>b\right) , because when fixing j , there is no overlap between the samples in the current window and the next. \displaystyle\mathbb{P}\left(\tau_{k,i}^{(j)}=\tau_{i-1}+nw+j\middle|\bar{F}_{i-1}D_{i-1},\sum_{t=\tau_{i}+1}^{\nu_{i}}\bm{1}_{A_{t}=k}\geq w\right)=\mathbb{P}\left(\xi_{k,i}=n\middle|\bar{F}_{i-1}D_{i-1},\sum_{t=\tau_{i}+1}^{\nu_{i}}\bm{1}_{A_{t}=k}\geq w\right)=p(1-p)^{n-1}. Here, the inclusion of subsequent events as conditions should not impact the results, as when entering the change detection algorithm, those events have already occurred. Moreover, by union bound, we have that for any i\in\mathbb{N} , \displaystyle\mathbb{P}\left(\tau_{k,i}\leq\nu_{i}\mid\bar{F}_{i-1}D_{i-1}\right) \displaystyle\leq w\left(1-(1-p)^{\left\lfloor\left(\nu_{i}-\tau_{i}-1\right)/w\right\rfloor}\right) (85a) \displaystyle\leq w\left(1-(1-p)^{\lfloor T/w\rfloor}\right). (85b) We further upper bound the probability p_{k} for each arm k by decomposing the reward into two parts: (i) a state-dependent mean component , determined by the Markovian state of the arm; and (ii) an independent noise term n_{t}\in[-1,1] with zero mean. The key idea is to separately bound the effects of the distributional fluctuations induced by the Markov chain and the reward noise . Accordingly, we split the detection threshold into two components, b=b_{d}+b_{n} , where b_{d} handles deviations due to distributional shifts and b_{n} accounts for noise fluctuations. Let V_{k,t} denote the state of arm k at time t , and let f_{k,t}:\mathcal{S}\mapsto[0,1] be the corresponding reward mean function. Then the probability of the detection statistic exceeding the threshold can be bounded as follows: \displaystyle p \displaystyle=\mathbb{P}\left[\left\lvert S_{k,\ell}\right\rvert\geq b\right] (86a) \displaystyle=\mathbb{P}\left[\left\lvert\sum_{\ell=w/2+1}^{w}\left(f_{k,\ell}\left(V_{k,\ell}\right)+n_{\ell}\right)-\sum_{\ell=1}^{w/2}\left(f_{k,\ell}\left(V_{k,\ell}\right)+n_{\ell}\right)\right\rvert\geq b_{d}+b_{n}\right] (86b) \displaystyle\leq 1-\mathbb{P}\left[\left\lvert\sum_{\ell=w/2+1}^{w}f_{k,\ell}(V_{k,\ell})-\sum_{\ell=1}^{w/2}f_{k,\ell}(V_{k,\ell})\right\rvert\leq b_{d}\right]\cdot\mathbb{P}\left[\left\lvert\sum_{\ell=1}^{w}n_{\ell}\right\rvert\leq b_{n}\right]. (86c) To apply the concentration inequality, we focus on the case that induces the largest deviation from the steady-state distribution. This occurs when the rewards within the detection window are collected consecutively in time, which leads to the strongest temporal dependence among samples. We then derive the concentration probability of this distributional deviation. To fit the requirement of Lemma B.13 , we shift the original reward function f_{\ell} to a new function f^{\prime}_{k,\ell} such that f_{k,\ell}^{\prime}:\mathcal{S}\mapsto[0,1] : \displaystyle f^{\prime}_{k,\ell}=\begin{cases}\frac{1-f_{k,\ell}}{2}&1\leq\ell\leq\frac{w}{2},\\ \frac{1+f_{k,\ell}}{2}&\frac{w}{2}+1\leq\ell\leq w.\end{cases} (87) We first focus on the first probability term in Equation 86c . By substituting Equation 87 into it, we obtain \displaystyle\mathbb{P}\left[\left\lvert\sum_{\ell=w/2+1}^{w}f_{k,\ell}(V_{k,\ell})-\sum_{\ell=1}^{w/2}f_{k,\ell}(V_{k,\ell})\right\rvert\leq b_{d}\right] (88a) \displaystyle=\mathbb{P}\left[\left\lvert 2\sum_{\ell=w/2+1}^{w}f^{\prime}_{k,\ell}(V_{k,\ell})+2\sum_{\ell=1}^{w/2}f^{\prime}_{k,\ell}(V_{k,\ell})-w\right\rvert\leq b_{d}\right] (88b) \displaystyle=\mathbb{P}\left[\left\lvert\sum_{\ell=1}^{w}f^{\prime}_{k,\ell}(V_{k,\ell})-\frac{w}{2}\right\rvert\leq\frac{b_{d}}{2}\right] (88c) \displaystyle=1-\mathbb{P}\left[\sum_{\ell=1}^{w}f^{\prime}_{k,\ell}(V_{k,\ell})-\frac{w}{2}>\frac{b_{d}}{2}\right]-\mathbb{P}\left[\sum_{\ell=1}^{w}f^{\prime}_{k,\ell}(V_{k,\ell})-\frac{w}{2}<-\frac{b_{d}}{2}\right]. (88d) \displaystyle=1-\mathbb{P}\left[\sum_{\ell=1}^{w}f^{\prime}_{k,\ell}(V_{k,\ell})>\frac{w}{2}+\frac{b_{d}}{2}\right]-\mathbb{P}\left[\sum_{\ell=1}^{w}f^{\prime}_{k,\ell}(V_{k,\ell})<\frac{w}{2}-\frac{b_{d}}{2}\right]. (88e) Specifically, Equation 88b follows from the definition of f^{\prime}_{k,\ell} in Equation 87 . Next, by simple algebraic rearrangement, we obtain Equation 88c . Equation 88d is derived by decomposing the absolute value event into two separate one-sided probability terms, and Equation 88e then follows from further rearranging these terms. By applying Lemma B.13 to the two probability terms above, we obtain \displaystyle\mathbb{P}\left[\sum_{\ell=1}^{w}f^{\prime}_{k,\ell}(V_{k,\ell})>\frac{w}{2}+\frac{b_{d}}{2}\right] (89a) \displaystyle\leq\epsilon\lVert\varphi\rVert_{d}\exp\left(-\frac{b_{d}^{2}}{144L_{k}}\right), (89b) \displaystyle\mathbb{P}\left[\sum_{\ell=1}^{w}f^{\prime}_{k,\ell}(V_{k,\ell})<\frac{w}{2}-\frac{b_{d}}{2}\right] (89c) \displaystyle\leq\epsilon\lVert\varphi\rVert_{d}\exp\left(-\frac{b_{d}^{2}}{144L_{k}}\right). (89d) Combining the above two inequalities, we have \mathbb{P}\left[\left\lvert\sum_{\ell=w/2+1}^{w}f_{k,\ell}(V_{k,\ell})-\sum_{\ell=1}^{w/2}f_{k,\ell}(V_{k,\ell})\right\rvert\leq b_{d}\right]\geq 1-2\epsilon\lVert\varphi\rVert_{d}\exp\left(-\frac{b_{d}^{2}}{144L_{k}}\right), (90) where L_{k} is the mixing time of arm k . If we set b_{d}=\sqrt{144L\log\left(2KT^{2}\lVert\varphi\rVert_{d}^{-1}\right)} , where L=\max_{k}L_{k} , then we have \mathbb{P}\left[\left\lvert\sum_{\ell=w/2+1}^{w}f_{k,\ell}(V_{k,\ell})-\sum_{\ell=1}^{w/2}f_{k,\ell}(V_{k,\ell})\right\rvert\leq b_{d}\right]\geq 1-\frac{\epsilon\lVert\varphi\rVert_{d}}{KT^{2}}. (91) Next, we bound the second probability term in Equation 86c . Since the noise terms n_{\ell} are independent and bounded within [-1,1] , we can apply McDiarmid’s inequality to obtain: \mathbb{P}\left[\left\lvert\sum_{\ell=1}^{w}n_{\ell}\right\rvert\leq b_{n}\right]\geq 1-\mathbb{P}\left[\left\lvert\sum_{\ell=1}^{w}n_{\ell}\right\rvert>b_{n}\right]\geq 1-\mathbb{P}\left[\sum_{\ell=1}^{w}n_{\ell}>b_{n}\right]-\mathbb{P}\left[\sum_{\ell=1}^{w}n_{\ell}<-b_{n}\right]\geq 1-2\exp\left(-\frac{2b_{n}^{2}}{w}\right). (92) By setting b_{n}=\sqrt{w\log\left(2KT^{2}\right)/2} , we have \mathbb{P}\left[\left\lvert\sum_{\ell=1}^{w}n_{\ell}\right\rvert\leq b_{n}\right]\geq 1-\frac{1}{KT^{2}}. (93) Combining the bounds for both probability terms, we obtain p\leq 1-\left(1-\frac{\epsilon\lVert\varphi\rVert_{d}}{KT^{2}}\right)\left(1-\frac{1}{KT^{2}}\right)\leq\frac{\epsilon\lVert\varphi\rVert_{d}+1}{KT^{2}}. (94) Finally, we can bound the probability of false alarm as follows: \displaystyle\mathbb{P}\left(F_{i}\middle|\overline{F}_{i-1}D_{i-1}\right) \displaystyle\leq\sum_{k=1}^{K}\mathbb{P}\left(\tau_{k,i}\leq\nu_{i}\mid\overline{F}_{i-1}D_{i-1}\right) (95a) \displaystyle\leq\sum_{k=1}^{K}w\left(1-\left(1-\frac{\epsilon\lVert\varphi\rVert_{d}+1}{KT^{2}}\right)^{\lfloor T/w\rfloor}\right) (95b) \displaystyle\leq\sum_{k=1}^{K}w\cdot\frac{\epsilon\lVert\varphi\rVert_{d}+1}{KT^{2}}\cdot\lfloor T/w\rfloor (95c) \displaystyle\leq\frac{\epsilon\lVert\varphi\rVert_{d}+1}{T}. (95d) Here, equation 95a follows from the union bound; equation 95b follows from the earlier derived bound on p ; equation 95c uses the inequality (1-x)^{n}\geq 1-nx for x\in[0,1] and n\geq 1 ; and equation 95d simplifies the expression to yield the final result. ∎ We next use the same concentration tool to establish that, with high probability, each true change is successfully detected within a sublinear delay. Lemma B.15 (Probability of successful detection) . Under Algorithm 2 with the parameter choices specified in equation 14 and equation 15 , and with the delay threshold h_{i}=\left\lceil w\left(\frac{K}{2\alpha}+1\right)\sqrt{s_{i}+1}+\frac{w^{2}}{4}\left(\frac{K}{2\alpha}+1\right)^{2}\right\rceil, (96) for any i\geq 1 , the probability of successful detection satisfies \mathbb{P}\!\left(D_{i}\,\middle|\,\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right)\;\geq\;1-\frac{\epsilon\lVert\varphi\rVert_{d}}{T}, (97) where \epsilon>0 is an arbitrarily small constant, \varphi is the initial state distribution, and d is the stationary distribution. Proof. \displaystyle\mathbb{P}\left(D_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) \displaystyle=1-\mathbb{P}\left(\tau_{i}>\nu_{i}+h_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (98a) \displaystyle\hskip-40.0pt\geq\max_{t\in\left\{\nu_{i}+1,\ldots,\nu_{i}+h_{i}\right\}}\mathbb{P}\left(\exists k\in{\mathcal{K}},\left|S_{k,t}\right|>b\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (98b) \displaystyle\hskip-40.0pt\geq\max_{j\in\left\{0,\ldots,w/2\right\}}\mathbb{P}\left(\left\lvert\sum^{w}_{\ell=j+1}\left(f_{k,\ell}\left(V_{k,\ell}\right)+n_{\ell}\right)-\sum^{j}_{\ell=1}\left(f_{k,\ell}\left(V_{k,\ell}\right)+n_{\ell}\right)\right\rvert>b\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (98c) \displaystyle\hskip-40.0pt\geq\mathbb{P}\left(\left\lvert\sum^{w}_{\ell=w/2+1}\left(f_{k,\ell}\left(V_{k,\ell}\right)+n_{\ell}\right)-\sum^{w/2}_{\ell=1}\left(f_{k,\ell}\left(V_{k,\ell}\right)+n_{\ell}\right)\right\rvert>b\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (98d) Here, equation 98a follows from the definition of successful detection; equation 98b follows from the definition of the stopping time; equation 98c mirrors the derivation from equation 86a to equation 86b ; and equation 98d follows from noting that the maximum is attained at j=w/2 and decomposing the absolute value event into two separate probability terms, one capturing the distributional deviation and the other the noise fluctuation. First, we bound the first probability term in equation 98d . \displaystyle\mathbb{P}\left(\left\lvert\sum^{w}_{\ell=w/2+1}f_{k,\ell}\left(V_{k,\ell}\right)-\sum^{w/2}_{\ell=1}f_{k,\ell}\left(V_{k,\ell}\right)\right\rvert>b+b_{d}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (99a) \displaystyle=\mathbb{P}\left(\sum^{w}_{\ell=w/2+1}f_{k,\ell}\left(V_{k,\ell}\right)-\sum^{w/2}_{\ell=1}f_{k,\ell}\left(V_{k,\ell}\right)>b+b_{d}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (99b) \displaystyle\hskip 20.0pt+\mathbb{P}\left(\sum^{w/2}_{\ell=1}f_{k,\ell}\left(V_{k,\ell}\right)-\sum^{w}_{\ell=w/2+1}f_{k,\ell}\left(V_{k,\ell}\right)>b+b_{d}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (99c) \displaystyle\geq\mathbb{P}\left(\sum^{w}_{\ell=w/2+1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i)}\right)-\sum^{w/2}_{\ell=1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i-1)}\right)>b+b_{d}-\frac{w}{2}\left(\bar{\mu}^{(i)}_{k}-\bar{\mu}^{(i-1)}_{k}\right)\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (99d) \displaystyle\hskip 20.0pt+\mathbb{P}\left(\sum^{w/2}_{\ell=1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i-1)}\right)-\sum^{w}_{\ell=w/2+1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i)}\right)>b+b_{d}-\frac{w}{2}\left(\bar{\mu}^{(i-1)}_{k}-\bar{\mu}^{(i)}_{k}\right)\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (99e) \displaystyle\geq\mathbb{P}\left(\bar{\mu}^{(i)}_{k}>\bar{\mu}^{(i-1)}_{k}\right)\mathbb{P}\left(\sum^{w/2}_{\ell=1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i-1)}\right)<\frac{\left(\bar{\mu}^{(i)}_{k}-\bar{\mu}^{(i-1)}_{k}\right)w}{4}-\frac{\left(b+b_{n}\right)}{2}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (99f) \displaystyle\hskip 20.0pt\cdot\mathbb{P}\left(\sum^{w}_{\ell=w/2+1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i)}\right)>\frac{\left(b+b_{n}\right)}{2}-\frac{\left(\bar{\mu}^{(i)}_{k}-\bar{\mu}^{(i-1)}_{k}\right)w}{4}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (99g) \displaystyle\hskip 20.0pt+\mathbb{P}\left(\bar{\mu}^{(i)}_{k}<\bar{\mu}^{(i-1)}_{k}\right)\mathbb{P}\left(\sum^{w}_{\ell=w/2+1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i)}\right)<-\frac{\left(\bar{\mu}^{(i-1)}_{k}-\bar{\mu}^{(i)}_{k}\right)w}{4}-\frac{\left(b+b_{n}\right)}{2}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (99h) \displaystyle\hskip 20.0pt\cdot\mathbb{P}\left(\sum^{w/2}_{\ell=1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i-1)}\right)>\frac{\left(b+b_{n}\right)}{2}+\frac{\left(\bar{\mu}^{(i-1)}_{k}-\bar{\mu}^{(i)}_{k}\right)w}{4}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (99i) \displaystyle\geq\mathbb{P}\left(\bar{\mu}^{(i)}_{k}>\bar{\mu}^{(i-1)}_{k}\right)\mathbb{P}\left(\sum^{w/2}_{\ell=1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i-1)}\right)<\frac{\delta w}{4}-\frac{\left(b+b_{n}\right)}{2}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (99j) \displaystyle\hskip 20.0pt\cdot\mathbb{P}\left(\sum^{w}_{\ell=w/2+1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i)}\right)>\frac{\left(b+b_{n}\right)}{2}-\frac{\delta w}{4}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (99k) \displaystyle\hskip 20.0pt+\mathbb{P}\left(\bar{\mu}^{(i)}_{k}<\bar{\mu}^{(i-1)}_{k}\right)\mathbb{P}\left(\sum^{w}_{\ell=w/2+1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i)}\right)<-\frac{\delta w}{4}-\frac{\left(b+b_{n}\right)}{2}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (99l) \displaystyle\hskip 20.0pt\cdot\mathbb{P}\left(\sum^{w/2}_{\ell=1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i-1)}\right)>\frac{\left(b+b_{n}\right)}{2}+\frac{\delta w}{4}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (99m) Here, equation 99b and equation 99c follow from decomposing the absolute value event into two separate one-sided probability terms; equation 99d and equation 99e follow from rearranging the terms and adding and subtracting the respective means; equation 99f and equation 99h follow from conditioning on whether the mean reward has increased or decreased; equation 99g and equation 99i follow from rearranging the terms; and equation 99j and equation 99l follow from the definition of the minimum change size \delta . Let \zeta_{k}^{(i)}=\frac{\delta/2-\left(b+b_{n}\right)/w}{\bar{\mu}^{(i-1)}_{k}} and \zeta_{k}^{(i-1)}=\frac{\delta/2-\left(b+b_{n}\right)/w}{\bar{\mu}^{(i-1)}_{k}} . Then, equation 99j –equation 99m become \displaystyle\mathbb{P}\left(\left\lvert\sum^{w}_{\ell=w/2+1}f_{k,\ell}\left(V_{k,\ell}\right)-\sum^{w/2}_{\ell=1}f_{k,\ell}\left(V_{k,\ell}\right)\right\rvert>b+b_{d}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (100a) \displaystyle\geq\mathbb{P}\left(\bar{\mu}^{(i)}_{k}>\bar{\mu}^{(i-1)}_{k}\right)\mathbb{P}\left(\sum^{w/2}_{\ell=1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i-1)}\right)<\frac{1}{2}\left(\frac{\delta/2-\left(b+b_{n}\right)/w}{\bar{\mu}^{(i-1)}_{k}}\right)\bar{\mu}^{(i-1)}_{k}w\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (100b) \displaystyle\hskip 20.0pt\cdot\mathbb{P}\left(\sum^{w}_{\ell=w/2+1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i)}\right)>-\frac{1}{2}\left(\frac{\delta/2-\left(b+b_{n}\right)/w}{\bar{\mu}^{(i)}_{k}}\right)\bar{\mu}^{(i)}_{k}w\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (100c) \displaystyle\hskip 20.0pt+\mathbb{P}\left(\bar{\mu}^{(i)}_{k}<\bar{\mu}^{(i-1)}_{k}\right)\mathbb{P}\left(\sum^{w}_{\ell=w/2+1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i)}\right)<\frac{1}{2}\left(\frac{\delta/2-\left(b+b_{n}\right)/w}{\bar{\mu}^{(i)}_{k}}\right)\bar{\mu}^{(i)}_{k}w\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (100d) \displaystyle\hskip 20.0pt\cdot\mathbb{P}\left(\sum^{w/2}_{\ell=1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i-1)}\right)>-\frac{1}{2}\left(\frac{\delta/2-\left(b+b_{n}\right)/w}{\bar{\mu}^{(i-1)}_{k}}\right)\bar{\mu}^{(i-1)}_{k}w\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (100e) \displaystyle\geq\mathbb{P}\left(\bar{\mu}^{(i)}_{k}>\bar{\mu}^{(i-1)}_{k}\right)\mathbb{P}\left(\sum^{w/2}_{\ell=1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i-1)}\right)<\frac{\zeta_{k}^{(i-1)}\bar{\mu}^{(i-1)}_{k}w}{2}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (100f) \displaystyle\hskip 20.0pt\cdot\mathbb{P}\left(\sum^{w}_{\ell=w/2+1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i)}\right)>-\frac{\zeta_{k}^{(i)}\bar{\mu}^{(i)}_{k}w}{2}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (100g) \displaystyle\hskip 20.0pt+\mathbb{P}\left(\bar{\mu}^{(i)}_{k}<\bar{\mu}^{(i-1)}_{k}\right)\mathbb{P}\left(\sum^{w}_{\ell=w/2+1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i)}\right)<\frac{\zeta_{k}^{(i)}\bar{\mu}^{(i)}_{k}w}{2}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (100h) \displaystyle\hskip 20.0pt\cdot\mathbb{P}\left(\sum^{w/2}_{\ell=1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i-1)}\right)>-\frac{\zeta_{k}^{(i-1)}\bar{\mu}^{(i-1)}_{k}w}{2}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (100i) Here, equation 100a –equation 100g follow from substituting the definitions of \zeta_{k}^{(i)} and \zeta_{k}^{(i-1)} ; and equation 100h and equation 100i follow from rearranging the terms. Before applying Lemma B.13 , we rewrite the above as \displaystyle\mathbb{P}\left(\left\lvert\sum^{w}_{\ell=w/2+1}f_{k,\ell}\left(V_{k,\ell}\right)-\sum^{w/2}_{\ell=1}f_{k,\ell}\left(V_{k,\ell}\right)\right\rvert>b+b_{d}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (101a) \displaystyle\geq\mathbb{P}\left(\bar{\mu}^{(i)}_{k}>\bar{\mu}^{(i-1)}_{k}\right)\left(1-\mathbb{P}\left(\sum^{w/2}_{\ell=1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i-1)}\right)\geq\frac{\left(1+\zeta_{k}^{(i-1)}\right)\bar{\mu}^{(i-1)}_{k}w}{2}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right)\right) (101b) \displaystyle\hskip 20.0pt\cdot\left(1-\mathbb{P}\left(\sum^{w}_{\ell=w/2+1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i)}\right)\leq\frac{\left(1-\zeta_{k}^{(i)}\right)\bar{\mu}^{(i)}_{k}w}{2}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right)\right) (101c) \displaystyle\hskip 20.0pt+\mathbb{P}\left(\bar{\mu}^{(i)}_{k}<\bar{\mu}^{(i-1)}_{k}\right)\left(1-\mathbb{P}\left(\sum^{w}_{\ell=w/2+1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i)}\right)\geq\frac{\left(1+\zeta_{k}^{(i)}\right)\bar{\mu}^{(i)}_{k}w}{2}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right)\right) (101d) \displaystyle\hskip 20.0pt\cdot\left(1-\mathbb{P}\left(\sum^{w/2}_{\ell=1}\left(f_{k,\ell}\left(V_{k,\ell}\right)-\bar{\mu}_{k}^{(i-1)}\right)\leq\frac{\left(1-\zeta_{k}^{(i-1)}\right)\bar{\mu}^{(i-1)}_{k}w}{2}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right)\right) (101e) Here, equation 101a –equation 101d follow from rearranging the terms. Now, we can apply Lemma B.13 to bound the probability terms in equation 101b –equation 101e . For example, for the term in equation 101b , we have \displaystyle\mathbb{P}\left(\left\lvert\sum^{w}_{\ell=w/2+1}f_{k,\ell}\left(V_{k,\ell}\right)-\sum^{w/2}_{\ell=1}f_{k,\ell}\left(V_{k,\ell}\right)\right\rvert>b+b_{d}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right) (102a) \displaystyle\geq\mathbb{P}\left(\bar{\mu}^{(i)}_{k}>\bar{\mu}^{(i-1)}_{k}\right)\left(1-\epsilon\lVert\varphi\rVert_{d}\exp\left(-\frac{\left(c/2-b_{n}/w\right)^{2}}{144L}\right)\right)^{2} (102b) \displaystyle\hskip 20.0pt+\mathbb{P}\left(\bar{\mu}^{(i)}_{k}<\bar{\mu}^{(i-1)}_{k}\right)\left(1-\epsilon\lVert\varphi\rVert_{d}\exp\left(-\frac{\left(c/2-b_{n}/w\right)^{2}}{144L}\right)\right)^{2} (102c) \displaystyle=\left(1-\epsilon\lVert\varphi\rVert_{d}\exp\left(-\frac{\left(c/2-b_{n}/w\right)^{2}}{144L}\right)\right)^{2} (102d) Finally, to satisfy the inequality \delta^{(i)}_{k}\geq 2b/w+c , we set w and b as in equation 14 and equation 15 , and choose c=2\left(\sqrt{144L\ln T/w}+\sqrt{\ln(2KT^{2})/2w}\right) , which leads to \mathbb{P}\left(\left\lvert\sum^{w}_{\ell=w/2+1}f_{k,\ell}\left(V_{k,\ell}\right)-\sum^{w/2}_{\ell=1}f_{k,\ell}\left(V_{k,\ell}\right)\right\rvert>b+b_{d}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right)\geq 1-\frac{\epsilon\lVert\varphi\rVert_{d}}{T}. (103) The second probability term in equation 98d can be bounded similarly as in equation 93 , the successful detection probability is then obtained by substituting equation 103 and equation 93 back into equation 98d . \mathbb{P}\left(D_{i}\middle|\overline{F}_{i}\overline{F}_{i-1}D_{i-1}\right)\geq 1-\frac{\epsilon\lVert\varphi\rVert_{d}}{T}. (104) ∎ Lemma B.16 further bounds the expected detection delay in the situation where the change detection algorithm successfully detects the change within the desired interval. Lemma B.16 (Expected detection delay) . Consider a piecewise-stationary restless bandit environment. For any \bm{\bar{\mu}}^{(i)},\bm{\bar{\mu}}^{(i+1)}\in\left[0,1\right]^{K} with parameters chosen in equation 3 and equation 4 and h_{i}=\left\lceil w\left(\frac{K}{2\alpha}+1\right)\sqrt{s_{i}+1}+\frac{w^{2}}{4}\left(\frac{K}{2\alpha}+1\right)^{2}\right\rceil, (105) for some k\in{\mathcal{K}},i\geq 1 and c>0 , under the Algorithm 1 , we have \mathbb{E}\left[\tau_{i}-\nu_{i}\middle|\overline{F}_{i}D_{i}\overline{F}_{i-1}D_{i-1}\right]\leq h_{i}. (106) Proof. For any 1\leq i\leq M , we have \displaystyle\mathbb{E}\left[\tau_{i}-\nu_{i}\middle|\overline{F}_{i}D_{i}\overline{F}_{i-1}D_{i-1}\right] \displaystyle=\sum^{h_{i}}_{j=1}\mathbb{P}\left(\tau_{i}\geq\nu_{i}+j\middle|\overline{F}_{i}D_{i}\overline{F}_{i-1}D_{i-1}\right)\leq h_{i}. (107a) ∎ Plugging the bounds in Lemmas B.14 , B.15 and B.7 into Theorem B.4 shows the following regret bound in Corollary B.17 . Corollary B.17 . Combining Algorithm 1 (diminishing exploration with resets) with the base solver \mathcal{B} and Algorithm 2 with parameters (w,b) given in Equations 3 and 4 , the excess regret is upper-bounded as \mathcal{R}_{\mathrm{excess}}(T)\leq 2\alpha\sqrt{MT}+w\left(\frac{K}{2\alpha}+1\right)\sqrt{M\left(T+M\right)}+\frac{w^{2}M}{4}\left(\frac{K}{2\alpha}+1\right)^{2}+2\epsilon\lVert\varphi\rVert_{d}+1. (108) By setting \alpha=c\sqrt{KL\log{\left(KT\right)}} for some constant c , the expected regret is upper-bounded by \mathcal{O}(\sqrt{KLMT\log{T}}) . Appendix C Algorithms and Parameters Tuning In this appendix, we provide an explanation of our parameter selection. Algorithm Setting. For change detection mechanism, the window size w is set to \left\lfloor 100\sqrt{144L}\right\rfloor , where L is the mixing time for \epsilon=1/8 , the threshold b=\sqrt{w/2\ln{(2KT^{2})}}+\sqrt{144wL\ln{(2KT^{2})}} . For uniform sampling scheme, the sample rate \alpha=\sqrt{M/T\log{(T/M)}} is following the setting in 12 . For diminishing exploration scheme, the sampling parameter \alpha=1 . In RestlessUCB algorithm, the minimum sampling amount is set as m(T)=100 , and the confidence radius rad(T)=\sqrt{T/(2Mm(T))} . For the Colored-UCRL2 algorithm, \delta=1/\min(10000,T) and B=S , following the work in 17 . To improve computational efficiency, we restrict the value of \delta so that the value iteration can run faster without significant loss of accuracy. Environment Setting. We consider an experiment consisting of three Markov chains (arms), indexed by k\in\{1,2,3\} , each evolving over five segments, indexed by i\in\{1,2,3,4,5\} . The transitions between states in each Markov chain are governed by transition probability matrices, and each state is associated with a reward mean function. Markov Chain Transition Kernels. The transition kernel for each segment i is given by a set of transition matrices P^{(i,k)} , where each row represents the probability distribution over the next states, given the current state. For each segment i , we define: P^{(i)}=\begin{bmatrix}P^{(i)}_{1}&P^{(i)}_{2}&P^{(i)}_{3}\end{bmatrix} (109) where P^{(i)}_{k} represents the transition matrix for arm k . The transition matrices for each segment are: P^{(1)}=\begin{bmatrix}\begin{bmatrix}0.50&0.50&0.00\\ 0.17&0.66&0.17\\ 0.00&0.50&0.50\end{bmatrix},&\begin{bmatrix}0.36&0.64&0.00\\ 0.39&0.22&0.39\\ 0.00&0.50&0.50\end{bmatrix},&\begin{bmatrix}0.55&0.45&0.00\\ 0.43&0.36&0.21\\ 0.00&0.50&0.50\end{bmatrix}\end{bmatrix} (110) P^{(2)}=\begin{bmatrix}\begin{bmatrix}0.43&0.57&0.00\\ 0.45&0.30&0.25\\ 0.00&0.64&0.36\end{bmatrix},&\begin{bmatrix}0.33&0.67&0.00\\ 0.32&0.42&0.26\\ 0.00&0.50&0.50\end{bmatrix},&\begin{bmatrix}0.50&0.50&0.00\\ 0.11&0.47&0.42\\ 0.00&0.67&0.33\end{bmatrix}\end{bmatrix} (111) P^{(3)}=\begin{bmatrix}\begin{bmatrix}0.62&0.38&0.00\\ 0.50&0.44&0.06\\ 0.00&0.62&0.38\end{bmatrix},&\begin{bmatrix}0.50&0.50&0.00\\ 0.43&0.21&0.36\\ 0.00&0.38&0.62\end{bmatrix},&\begin{bmatrix}0.17&0.83&0.00\\ 0.50&0.28&0.22\\ 0.00&0.44&0.56\end{bmatrix}\end{bmatrix} (112) P^{(4)}=\begin{bmatrix}\begin{bmatrix}0.57&0.43&0.00\\ 0.20&0.47&0.33\\ 0.00&0.57&0.43\end{bmatrix},&\begin{bmatrix}0.60&0.40&0.00\\ 0.18&0.47&0.35\\ 0.00&0.50&0.50\end{bmatrix},&\begin{bmatrix}0.53&0.47&0.00\\ 0.20&0.20&0.60\\ 0.00&0.73&0.27\end{bmatrix}\end{bmatrix} (113) P^{(5)}=\begin{bmatrix}\begin{bmatrix}0.38&0.62&0.00\\ 0.31&0.13&0.56\\ 0.00&0.56&0.44\end{bmatrix},&\begin{bmatrix}0.55&0.45&0.00\\ 0.45&0.46&0.09\\ 0.00&0.64&0.36\end{bmatrix},&\begin{bmatrix}0.33&0.67&0.00\\ 0.56&0.25&0.19\\ 0.00&0.40&0.60\end{bmatrix}\end{bmatrix} (114) Reward Mean Functions. The rewards are randomly generated based on the current state in each segment, denoted as R^{(i)}_{k}(s) , where k=1,2,3 represents the arm, i=1,2,3,4,5 represents the segment, and s=1,2,3 represents the state. R^{(i)}=\begin{bmatrix}R^{(i)}_{1}(1)&R^{(i)}_{1}(2)&R^{(i)}_{1}(3)\\ R^{(i)}_{2}(1)&R^{(i)}_{2}(2)&R^{(i)}_{2}(3)\\ R^{(i)}_{3}(1)&R^{(i)}_{3}(2)&R^{(i)}_{3}(3)\end{bmatrix} (115) The values for each segment are: R^{(1)}=\begin{bmatrix}0.24090&0.21567&0.11303\\ 0.68377&0.55163&0.29024\\ 0.88837&0.87993&0.40863\end{bmatrix}\quad R^{(2)}=\begin{bmatrix}0.76023&0.42959&0.15431\\ 0.95580&0.81347&0.63100\\ 0.37325&0.24685&0.06446\end{bmatrix} (116) R^{(3)}=\begin{bmatrix}0.83859&0.80774&0.19539\\ 0.29037&0.23361&0.08248\\ 0.95163&0.45959&0.03668\end{bmatrix}\quad R^{(4)}=\begin{bmatrix}0.52273&0.14461&0.03640\\ 0.67324&0.54894&0.31872\\ 0.93209&0.88988&0.62226\end{bmatrix} (117) R^{(5)}=\begin{bmatrix}0.64763&0.56596&0.36023\\ 0.87041&0.82968&0.08825\\ 0.22632&0.21085&0.13084\end{bmatrix} (118) Mixing Time Calculation. The mixing time L is calculated based on the transition matrices of the Markov chains. For each arm k in segment i , we compute the second largest eigenvalue modulus (SLEM) of the transition matrix P^{(i,k)} . The mixing time is then determined using the formula: L^{(i,k)}=\frac{\ln(1/\epsilon)}{1-\lambda_{2}^{(i,k)}} (119) where \lambda_{2}^{(i,k)} is the SLEM of P^{(i,k)} and \epsilon is the desired accuracy level (set to 1/8 in our experiments). The overall mixing time L used in the algorithm is the maximum mixing time across all arms and segments: L=\max_{i,k}L^{(i,k)} (120) Appendix D One-State Special Case Simulation Results In this appendix, we assess the effectiveness of the proposed diminishing exploration scheme across various dimensions, encompassing regret scaling in M , K , and T , regrets in synthetic environments, and regrets in a real-world scenario. In addition to evaluating M-UCB ( 5 ) with our diminishing exploration, we also examine a variant of CUSUM-UCB ( 12 ) that incorporates diminishing exploration with CUSUM-UCB, further highlighting the efficacy of the proposed exploration method. We will compare our approach with M-UCB, CUSUM-UCB, GLR-UCB, Discounted-UCB, Discounted Thompson Sampling, and MASTER. Unless stated otherwise, we report the average regrets over 100 simulation trials. Detailed configuration is provided in Appendix E . Regret in Each Time Step. In this simulation, we consider a multi-armed bandit problem with T=20000 time stpdf and M=5 . Recall that \mu^{(i)}_{k} represents the expected value for arm k in the i -th segment. Here, we set \mu^{(i)}_{k}=0.2,0.5,0.8 for i with (i+k)\bmod 3=2,0,1 , respectively. Figure 4(a) shows that for both CUSUM-UCB and M-UCB, employing diminishing exploration can effectively reduce the additional regret caused by constant exploration. Moreover, M-UCB with the proposed diminishing exploration achieves the lowest regret. In the figure, the change points are clearly evident by observing the breakpoints in each line. The reason for the overall steeper slope of CUSUM-UCB (both with and without diminishing exploration) is due to the heightened sensitivity of the CUSUM detector itself, resulting in more frequent false alarms. (a) Scaling in t . (b) Scaling in M . (c) Scaling in T . (d) Yahoo Data Set. Figure 4: Regret in the synthetic environments and under the Yahoo data set. Regret Scaling in M . Based on the settings outlined above, with the only variation being in the parameter M , Figure 4(b) illustrates the dynamic regrets across various values of M . In this experiment, adjustments to the exploration parameter settings are required based on the size of M when using a constant exploration rate. However, this is not the case for the proposed diminishing exploration. The result confirms the earlier-discussed rationale that the proposed diminishing exploration can automatically adapt to the environment, resulting in the best regret performance among the algorithms. Regret Scaling in T . In line with the setting described above, with the only variation being the parameter T , we present the dynamic regrets across different values of T . Observations similar to those made above can again be found in Figure 4(c) , where the proposed diminishing exploration can effectively reduce the regret. Regret and Execution Time. Here, we compare the computation time and regret across different algorithms for various choices of M and T with other parameters same as above. Specifically, we conduct experiments under three scenarioso: one where the environment changes rapidly ( M=50 and T=20000 ), one where the environment changes slowly ( M=5 and T=20000 ), and one where the considered time horizon is double ( M=5 and T=40000 ). As shown in Figure 5(a) to 5(c) , despite oblivious of M , our algorithm almost always achieves the lowest computation time and regret in all the scenarios. Moreover, comparing to Master+UCB, another algorithm not requiring the knowledge of M , our algorithm is always significantly better as shown in these figures. Figure 5(d) plots the ratio of average execution time of Master+UCB to that of M-UCB with our DE for various T . It is shown that the growth rate is faster than 0.5\log T , and it appears to become even linear in T as T increases. (a) M=50 , T=20000 . (b) M=5 , T=20000 . (c) M=5 , T=40000 . (d) Ratio of avg. execution time of Master+UCB to that of M-UCB (DE). Figure 5: Regret and computation times. Regret in an Environment Built from a Real-World Dataset. We further utilize the benchmark dataset publicly published by Yahoo! for evaluation. To enhance arm distinguishability in our simulation, we scale up the data by a factor of 10 . The number of segments is set to M=9 and the number of arms is set to K=6 . Figure 4(d) shows the evolution of dynamic regret. Again, we see that the diminishing exploration scheme could help M-UCB, GLR-UCB and CUSUM-UCB achieve similar or better regret even without knowing M . Scenarios when Assumptions are Violated. In Assumption A.1 , we assumes the knowledge of \delta to select an appropriate w . We emphasize that our settings in many of the above simulations actually violate this assumption. Take Figure 4(a) for example, w=200 is chosen, which corresponds to \delta\approx 0.6 when back calculating, which is much larger than the actual \delta=0.3 of this scenario. Assumptions A.2 provide guarantees that the segment length is sufficiently long. However, in the last data point of our Figure 4(b) ( M=100 ), these assumptions are clearly violated. In this case, it becomes challenging for the active methods to promptly detect every change point. For algorithms like M-UCB and CUSUM-UCB, which require knowledge of M , their awareness of quick changes causes them to invest more effort into change detection, leading to a very high exploration rate. However, this does not always guarantee successful detection, resulting in very high regret. Diminishing exploration, on the other hand, continues to decrease the exploration rate regardless of M when no changes are detected. This allows more resources to be invested for UCB, which might gradually adapt to the environment’s changes, leading to a regret that is lower than that of uniform exploration. Appendix E One-State Special Case Algorithms and Parameters Tuning In this appendix, we provide an explanation of our parameter selection. For M-UCB, the window size w is set to 200 unless otherwise specified; however, for the last data point ( M=100 ) in Figure 4(b) , we chose w=50 due to the limitations inherent to change detection. We compute the change detection threshold b_{\textrm{M-UCB}}=\sqrt{w/2\log\left(2KT^{2}\right)} following the original formulation in 5 . Additionally, the uniform exploration rate \gamma_{\textrm{M-UCB}}=\sqrt{MK\log{T}/T} is determined as initially stated in 4 .Concerning CUSUM-UCB, we adhere to 12 by fixing \epsilon=0.1 , setting the change detection threshold b_{\textrm{CUSUM-UCB}}=\log\left(T/M-1\right) , and establishing the uniform exploration rate \gamma_{\textrm{CUSUM-UCB}}=\sqrt{MK\log{T}/T} as initially stated in 4 . Additionally, in CUSUM-UCB, the change point detection involves averaging the first H samples, where H is set to 100. For GLR-UCB ( 4 ) , we set \gamma_{m,\textrm{GLR-UCB}}=\sqrt{mK\log{T}/T} , where m is the number of alarms. We utilize the threshold function \beta(n,\delta)=\log{\left(n^{3/2}/\delta\right)} and set \delta=1/\sqrt{T} . In our setup, for both the diminishing versions of M-UCB and CUSUM-UCB, we follow the parameter selection approach described earlier, except for the choice of the exploration rate. In this context, we opt for \alpha=1 . For passive methods, including DUCB ( 7 ) and DTS ( 19 ) , we use a discounting factor \gamma=0.75 . MASTER, on the other hand, follows the theoretical settings outlined in 25 and is categorized as an active method. To evaluate the scalability of our methods, we conducted three sets of scaling experiments. For scaling in t (Figure 4(a) ), scaling in M (Figure 4(b) ), and scaling in T (Figure 4(c) ), The parameters of DUCB, DTS and MASTER follow the theoretical settings outlined in 7 , 19 and 25 , respectively. Table 1: Parameter Selection for Active and Passive Methods Method Parameters