Paper deep dive

Logarithmic Regret via Passive Change Detection in Piecewise-Stationary Self-Tuning Regulation

A. Ch. Madhusudanarao, Rahul Singh

Year: 2026Venue: arXiv preprintArea: cs.LGType: PreprintEmbeddings: 190

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%

Last extracted: 10/11/2026, 4:38:20 AM

Summary

The paper introduces PIECE-CD, a self-tuning regulation algorithm for piecewise-stationary autoregressive systems with unknown coefficient changes. It achieves logarithmic regret by using passive change detection via output energy monitoring during exploitation, combined with gated recursive least squares (RLS) and periodic exploration. The method ensures stability and feasibility under bounded disturbances and provides theoretical guarantees for detection delay and regret bounds.

Entities (6)

PIECE-CD · algorithm · 98%Recursive Least Squares · method · 95%Change Detection · process · 93%Logarithmic Regret · metric · 92%Autoregressive System · system · 90%Output Energy · signal · 88%

Relation Signals (5)

PIECE-CD → uses → Recursive Least Squares

confidence 95% · PIECE-CD explores initially and after alarms, then uses gated recursive least squares for control.

PIECE-CD → employs → Change Detection

confidence 93% · Logarithmic Regret via Passive Change Detection

PIECE-CD → achieves → Logarithmic Regret

confidence 92% · we prove O((C+1)log((T+1)/δ)) regret

PIECE-CD → appliesto → Autoregressive System

confidence 90% · We study minimum-variance control of an unknown autoregressive system

Change Detection → monitors → Output Energy

confidence 88% · Its energy test compares windowed output power with a threshold

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:We study minimum-variance control of an unknown autoregressive system with exogenous inputs and coefficients that change at unknown times. Under bounded independent disturbances, fixed detection gaps, stability and feasibility conditions, and sufficient time between changes, we prove $O((C+1)\log((T+1)/\delta))$ regret with probability at least $1-\delta$, where $T$ is the horizon and $C$ the number of changes. Unlike switching bandits, where unselected arms can change unobserved, admissible plant changes provide information during exploitation: the correct feasible controller leaves only the disturbance in the output, whereas a detectable change raises output energy under the old controller. PIECE-CD explores initially and after alarms, then uses gated recursive least squares for control. Its energy test compares windowed output power with a threshold above the noise floor; the extension to unstable controller mismatches also monitors the reference controller's input proposal. We control false alarms across the horizon and prove logarithmic detection delay. Inputs are clipped to prescribed bounds. Logarithmic regret also holds under an explicit condition ensuring that clipping becomes inactive after a finite burn-in. Under the stated feasibility conditions, the extended detector covers destabilizing changes with detectable excess energy over a fixed window.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

186,252 characters extracted from source content.

Expand or collapse full text

Logarithmic Regret via Passive Change Detection in Piecewise-Stationary Self-Tuning Regulation A.Ch. Madhusudanarao Affiliation: Department of Computer Science and Automation Affiliation: Indian Institute of Science, Bengaluru, India Email: madhusudanar@iisc.ac.in Rahul Singh Affiliation: Laboratoire de Recherche de l’EPITA, Paris, France Email: rahulsingh0188@gmail.com Abstract We study minimum-variance control of an unknown autoregressive system with exogenous inputs and coefficients that change at unknown times. Under bounded independent disturbances, fixed detection gaps, stability and feasibility conditions, and sufficient time between changes, we prove O⁡((C+1)log⁡((T+1)/δ))O((C+1) ((T+1)/δ)) regret with probability at least 1−δ1-δ, where T is the horizon and C the number of changes. Unlike switching bandits, where unselected arms can change unobserved, admissible plant changes provide information during exploitation: the correct feasible controller leaves only the disturbance in the output, whereas a detectable change raises output energy under the old controller. PIECE-CD explores initially and after alarms, then uses gated recursive least squares for control. Its energy test compares windowed output power with a threshold above the noise floor; the extension to unstable controller mismatches also monitors the reference controller’s input proposal. We control false alarms across the horizon and prove logarithmic detection delay. Inputs are clipped to prescribed bounds. Logarithmic regret also holds under an explicit condition ensuring that clipping becomes inactive after a finite burn-in. Under the stated feasibility conditions, the extended detector covers destabilizing changes with detectable excess energy over a fixed window. 1 Introduction Self-tuning regulation (STR) seeks minimum-variance control of an unknown autoregressive system with exogenous inputs (ARX). The ideal controller cancels the predictable part of the next output, leaving only the disturbance. Classical work established stability and asymptotic efficiency (Goodwin et al.,, 1981; Becker et al.,, 1985; Kumar and Praly,, 1987; Lai,, 1986; Lai and Wei,, 1987); Singh et al., (2024) obtained finite-time logarithmic regret for a stationary plant. We ask whether this rate survives unknown changes in the plant coefficients. A controller must detect these changes and identify the new plant, while avoiding repeated exploration caused by false alarms. The key observation is that minimum-variance control can supply evidence of a change during exploitation. With the correct feasible controller, yt+1=wt+1y_t+1=w_t+1, so output power equals the disturbance variance σw2 _w^2. A change that raises output power under the old controller can therefore be detected from ordinary control observations. This differs from switching bandits, where an unselected arm can change unobserved and even a two-breakpoint class has an Ω⁡(T) ( T) minimax lower bound (Garivier and Moulines,, 2011). The distinction is informational: our guarantee requires a fixed detectable energy gap and sufficient time between changes, and does not apply to arbitrary nonstationarity. Our regret measures the predictable output energy left uncancelled by the learner; its expectation equals the expected excess output energy above the disturbance level ((3)–(4)). Our algorithm, PIECE-CD, extends Probing Inputs for Exploration in Certainty Equivalence (PIECE). It explores initially and after an alarm, then controls with gated recursive least squares (RLS) around an estimated reference gain. Its principal version combines an output-energy test with a boundary alarm on the reference controller’s requested input. The latter controls clipping errors when a changed plant is driven by the old gain. Outputs remain dependent, and alarm times depend on the observed history; both features matter for the guarantees. Contributions. 1. A common detector and logarithmic regret. Theorem 5 proves no false alarms, logarithmic detection delay, and ℛT=O⁡((C+1)log⁡((T+1)/δ))R_T=O((C+1) ((T+1)/δ)) with probability at least 1−δ1-δ, where C is the number of changes. Under own-regime feasibility, the theorem covers stable mismatches with a stationary power gap and potentially unstable mismatches with a finite-window energy gap, without identifying which condition applies. For the compact minimum-phase ARX class, non-Schur mismatches imply a uniform finite-window gap. The rate holds for fixed model, feasibility, and detectability bounds under the stated dwell-time requirements. 2. Identification and control after random restarts. We establish excitation and estimation bounds for complete exploration blocks conditional on the history at each restart. An RLS potential bound controls both accepted RLS actions and reference fallback actions. Chronological failure-event bounds combine these results with detection without assuming independent episodes or conditioning on future alarms. 3. Supporting guarantees under stable mismatches. An energy-only baseline isolates the stationary-gap argument (Theorem 4). A separate extension replaces uniform clipping feasibility by a steady-state slack condition and a finite burn-in, preserving logarithmic regret (Theorem 6). 1.1 Related Work Our closest predecessor is stationary PIECE (Singh et al.,, 2024). Its covariance analysis treats sparse, recurring exploration episodes. Here the exploration phase is a contiguous block after a data-dependent restart. This requires conditional excitation guarantees and a control analysis that remains valid before the next change or alarm, together with a detector for the dependent observations generated by feedback. Detect-and-restart methods are well established in piecewise-stationary bandits, including CUSUM-based CD-UCB (Liu et al.,, 2018), M-UCB (Cao et al.,, 2019), GLR-klUCB (Besson et al.,, 2022), and the modular DAB framework (Huang et al.,, 2026). Their exploration schedules address changes hidden by partial feedback. Additional structural information can permit logarithmic gap-dependent bounds, as when all arms change simultaneously (Mukherjee and Maillard,, 2019). PIECE-CD similarly uses a restricted detectable class; its monitoring signal comes from outputs observed during exploitation. Sequential detection provides the statistical background (Veeravalli and Banerjee,, 2014; Xie et al.,, 2021; Tartakovsky et al.,, 2014). Fully unknown online linear-quadratic regulation has square-root local minimax regret (Simchowitz and Foster,, 2020). STR instead has no positive input penalty, and its ideal controller leaves only the innovation in the output. This property makes the noise floor an observable reference for detecting the changes admitted here. 2 MODEL AND SCOPE We consider a scalar ARX system of known orders p,q≥1p,q≥ 1 whose coefficients change C times over a horizon T. Let 0=τ(0)<τ(1)<⋯<τ(C)<τ(C+1)=T0=τ^(0)<τ^(1)<·s<τ^(C)<τ^(C+1)=T denote the deterministic segment boundaries, with the C interior boundaries unknown. On segment c∈0,…,Cc∈\0,…,C\, yt+1 y_t+1 =∑i=1pai(c)yt−i+1+∑j=1qbj(c)ut−j+1+wt+1, = _i=1^pa_i^(c)y_t-i+1+ _j=1^qb_j^(c)u_t-j+1+w_t+1, (1) τ(c)≤t<τ(c+1). 60.00009ptτ^(c)≤ t<τ^(c+1). Here yty_t is the output, utu_t the control input, and wtw_t the disturbance. The unknown parameter vector is constant within each segment: θ(c) θ^(c) =(a1(c),…,ap(c),b1(c),…,bq(c)). =(a_1^(c),…,a_p^(c),b_1^(c),…,b_q^(c)) T. Write θt=θ(c) _t=θ^(c) for τ(c)≤t<τ(c+1)τ^(c)≤ t<τ^(c+1). We use Euclidean vector norms, induced spectral matrix norms, and ‖x‖M2=xMx x _M^2=x TMx. We use two regressors: ψt _t =(yt,…,yt−p+1,ut−1,…,ut−q+1), =(y_t,…,y_t-p+1,u_t-1,…,u_t-q+1) T, ϕt _t =(yt,…,yt−p+1,ut,…,ut−q+1). =(y_t,…,y_t-p+1,u_t,…,u_t-q+1) T. The control regressor ψt∈ℝd _t ^d, with d=p+q−1d=p+q-1, contains quantities available before utu_t is chosen. The identification regressor ϕt∈ℝp+q _t ^p+q additionally includes utu_t, so that yt+1=(θ(c))ϕt+wt+1y_t+1=(θ^(c)) T _t+w_t+1. The lagged-input block in ψt _t is empty when q=1q=1. For a generic parameter vector θ=(a1,…,ap,b1,…,bq)θ=(a_1,…,a_p,b_1,…,b_q) T with b1≠0b_1≠ 0, define the minimum-variance gain λ⁡(θ) λ(θ) :=−1b1(a1,…,ap,b2,…,bq). :=- 1b_1(a_1,…,a_p,b_2,…,b_q) T. (2) On segment c, yt+1=b1(c)ut−λ(θ(c))ψt+wt+1.y_t+1=b_1^(c)\u_t-λ(θ^(c)) T _t\+w_t+1. When feasible, the ideal action ut⋆=λ(θ(c))ψtu_t =λ(θ^(c)) T _t therefore leaves yt+1=wt+1y_t+1=w_t+1. We measure learning by the predictable output energy ℛT:=∑t=0T−1(yt+1−wt+1)2. _T:= _t=0^T-1(y_t+1-w_t+1)^2. (3) Let ℱtF_t include the observations and randomization available through the choice of utu_t. Then vt+1:=yt+1−wt+1v_t+1:=y_t+1-w_t+1 is ℱtF_t-measurable and ⁡[vt+1wt+1∣ℱt]=0E[v_t+1w_t+1 _t]=0. Hence ℛT=∑t=0T−1(yt+12−wt+12). _T=E _t=0^T-1(y_t+1^2-w_t+1^2). (4) This is an expectation identity; the realized excess output cost also contains 2∑tvt+1wt+12 _tv_t+1w_t+1. Our high-probability bounds concern ℛTR_T. We first state the conditions for the stable-mismatch baseline. The extension in Section 5 replaces its mismatch and feasibility conditions; the model, noise, and open-loop switching conditions remain in force. Appendices A–B give the corresponding constants and exploration conditions. Assumption 1 (Baseline conditions). The controller knows a compact class Θ⊂ℝp+q ^p+q containing every θ(c)θ^(c). Each θ∈Θθ∈ has a Schur-stable AR polynomial, a minimum-phase input polynomial, and 0<bmin≤b1≤b¯0<b_ ≤ b_1≤ b. The autonomous output dynamics are uniformly exponentially stable under admissible switching. The disturbances are i.i.d., independent of the available past, and satisfy wt=0Ew_t=0, wt2=σw2>0Ew_t^2= _w^2>0, and |wt|≤Bw|w_t|≤ B_w, where σw2 _w^2 and BwB_w are known. Uniform clipping feasibility holds: |λ(θ)ψ|≤Bu|λ(θ) Tψ|≤ B_u for every θ∈Θθ∈ and every regressor ψ reachable under admissible switching, bounded disturbances, and inputs in [−Bu,Bu][-B_u,B_u]. For each change c∈1,…,Cc∈\1,…,C\, let θ−=θ(c−1)θ^-=θ^(c-1) and θ+=θ(c)θ^+=θ^(c). The unclipped loop obtained by applying the old gain λ⁡(θ−)λ(θ^-) to the new plant θ+θ^+ has matrix AΔ:=A⁡(θ−,θ+)A_ :=A(θ^-,θ^+), where A⁡(θ−,θ+):=Acl(λ⁡(θ−),θ+)A(θ^-,θ^+):=A_ cl(λ(θ^-),θ^+), satisfying ‖AΔk‖≤CΔρΔk A_ ^k ≤ C_ _ ^k for all k≥0k≥ 0, with known common CΔ<∞C_ <∞ and ρΔ∈(0,1) _ ∈(0,1). Its stationary output power satisfies Jy(λ⁡(θ−),θ+)≥σw2+Δ J_y(λ(θ^-);θ^+)≥ _w^2+ (5) for a known fixed Δ>0 >0. Here Jy=σw2∑k≥0(e1AΔke1)2J_y= _w^2 _k≥ 0(e_1 TA_ ^ke_1)^2, where e1e_1 is the first coordinate vector in ℝdR^d. For exploration length H and delay bound D defined below, the dwell conditions, when C≥1C≥ 1, are τ(1) τ^(1) ≥H,T−τ(C)≥D, ≥ H, T-τ^(C)≥ D, τ(c+1)−τ(c) τ^(c+1)-τ^(c) ≥D+H(1≤c<C). ≥ D+H (1≤ c<C). (6) The final exploration may be truncated at T. Stability and detectability serve different purposes. Stability controls the discrepancy between the learner and the exact old-gain loop; the power gap supplies the detection signal. A parameter change preserving the minimum-variance gain can remain at the noise floor and is excluded by the gap condition. The algorithm uses known model, noise, excitation, and gap bounds for tuning, while the segment parameters and change times are unknown. The alternative feasibility conditions are stated with their respective results in Sections 5 and 6. Switching stability and clipped inputs give known deterministic bounds |yt|≤BY|y_t|≤ B_Y and ‖ψt‖≤Bψ _t ≤ B_ψ; their explicit values are given in (40). 3 PIECE-CD We first specify the energy-only baseline; Section 5 adds the boundary alarm for potentially unstable mismatches. At initialization and after each alarm, PIECE-CD estimates a fixed reference gain from H exploration rounds. During exploitation, a gate keeps RLS actions close to that reference while the detector monitors output energy. Use δ0=δ/[32(T+1)] _0=δ/[32(T+1)] for estimation and RLS and δd=δ/2 _d=δ/2 for detection. Exploration and the reference controller. Let r denote the start time of the current exploration phase, with r=0r=0 at initialization. After an alarm upon observing yt+1y_t+1, the next exploration phase starts at r=t+1r=t+1. For t=r,…,r+H−1t=r,…,r+H-1, draw i.i.d. mean-zero inputs from a prescribed distribution with positive variance and support in [−Bu,Bu][-B_u,B_u], independently of the disturbances. Let r0=max⁡p,qr_0= \p,q\, choose H>r0H>r_0, and retain the rows ℐr=r+r0,…,r+H−1I_r=\r+r_0,…,r+H-1\, whose lagged measurements all follow the restart. Fix a ridge parameter ν>0ν>0. Write IkI_k for the k×k× k identity matrix and ΠΘ _ for a Euclidean nearest-point projection onto Θ . After completing exploration, compute Vrθ V_r^θ =νIp+q+∑t∈ℐrϕtϕt, =ν I_p+q+ _t _r _t _t T, θ~r θ_r =(Vrθ)−1∑t∈ℐrϕtyt+1, =(V_r^θ)^-1 _t _r _ty_t+1, θ^r θ_r =ΠΘ(θ~r),b^r=b1(θ^r). = _ ( θ_r), b_r=b_1( θ_r). (7) The reference gain λ¯r=λ⁡(θ^r) λ_r=λ( θ_r) and b^r b_r remain fixed until the next restart. The computable parameter and reference-gain error bounds Eθ(H,δ0)E_θ(H, _0) and Eλ(H,δ0)E_λ(H, _0) are defined in (46)–(47). For the prescribed choice of H and a complete exploration block within segment c, with probability at least 1−2δ01-2 _0 conditional on the restart history, ‖θ^r−θ(c)‖ θ_r-θ^(c) ≤Eθ(H,δ0), ≤ E_θ(H, _0), Eθ(H,δ0) E_θ(H, _0) =O⁡(log⁡((T+1)/δ)H). =O\! ( ((T+1)/δ)H ). (8) This reference accuracy sets the gate tolerance: gH=4Eλ(H,δ0)g_H=4E_λ(H, _0). Write εu=5Eλ(H,δ0)Bψ _u=5E_λ(H, _0)B_ψ for the resulting reference-tracking tolerance used in the analysis. Gated control and recursive estimation. Let λ^t λ_t denote the current RLS gain estimate and VtV_t its regularized d×d× d Gram matrix. Initialize both from the exploration data: Vr+H=νId+∑t∈ℐrψtψt,λ^r+H=λ¯r.V_r+H=ν I_d+ _t _r _t _t T, λ_r+H= λ_r. At each subsequent control round, form the input proposal ztz_t and clip it to the prescribed bounds: zt z_t =λ^tψt,|(λ^t−λ¯r)ψt|≤gH‖ψt‖,λ¯rψt,otherwise, = cases λ_t T _t,&|( λ_t- λ_r) T _t|≤ g_H _t ,\\ λ_r T _t,&otherwise, cases ut u_t =min⁡Bu,max⁡−Bu,zt. = \B_u, \-B_u,z_t\\. (9) The gate limits departure from the reference action used for detection; clipping enforces the prescribed input bound. After observing yt+1y_t+1, construct the response xt+1λx_t+1^λ and update RLS: xt+1λ x_t+1^λ =ut−yt+1b^r, =u_t- y_t+1 b_r, Vt+1 V_t+1 =Vt+ψtψt, =V_t+ _t _t T, λ^t+1 λ_t+1 =λ^t+Vt+1−1ψt⋅(xt+1λ−λ^tψt). = λ_t+V_t+1^-1 _t·(x_t+1^λ- λ_t T _t). (10) RLS uses every exploitation observation, including rounds with a reference fallback or an active clip. The analysis accounts for bias from estimating b1(c)b_1^(c). Monitoring and restarting. Let the positive integers h and m denote the sampling interval and detection-window size, respectively, chosen below. After exploration, fix the recording times sj=r+H+jhs_j=r+H+jh, j=1,2,…j=1,2,…. At each sjs_j, store ysj2y_s_j^2 and retain the most recent m values. Once j≥mj≥ m, raise an alarm if J^(sj):=1m∑i=j−m+1jysi2≥σw2+Δ2. J(s_j):= 1m _i=j-m+1^jy_s_i^2≥ _w^2+ 2. (11) Control and RLS updates continue every round; only the energy test is subsampled. An alarm at sjs_j clears the estimates and stored values, sets r=sjr=s_j, and starts a new exploration phase. Choosing the exploration and detection lengths. Choose the smallest integer H>r0H>r_0 satisfying (93), (51), and (52) in Appendix B. These conditions ensure informative exploration and sufficiently accurate reference estimates for control and detection. Choose the smallest h≥1h≥ 1 satisfying σw2CΔ2ρΔ2h1−ρΔ2≤Δ8. _w^2C_ ^2 _ ^2h1- _ ^2≤ 8. Recorded outputs remain dependent; their spacing permits concentration around lag-h conditional second moments. Let BoB_o be the known common bound in (50) on disturbances, actual outputs, and outputs of the new plant driven by the exact old gain from the state at the change. Set the window size m and associated detection-delay bound D to m m =⌈512Bo4Δ2log⁡4T2δd⌉, = 512B_o^4 ^2 4T^2 _d , D D =(m+1)h. =(m+1)h. (12) This window size controls fluctuations across the horizon’s repeated tests. For fixed problem constants, h=O⁡(1)h=O(1) and H,m,D=O⁡(log⁡((T+1)/δ))H,m,D=O( ((T+1)/δ)). Algorithm 1: PIECE-CD: stable-mismatch baseline 1. Initialize r=0r=0. Stop at T, including during an incomplete phase. 2. Explore for H rounds; compute (7), the reference gain, and the RLS initialization. Clear the detector buffer and fix the sampling times sj=r+H+jhs_j=r+H+jh. 3. At every exploitation round, apply (9), observe yt+1y_t+1, and update (10). At sampling times, update the buffer and test (11) once it is full. 4. If an alarm occurs on observing yt+1y_t+1, set r=t+1r=t+1 and return to step 2; otherwise continue step 3. 4 FINITE-TIME ANALYSIS The proof bounds detection delays and false alarms, then controls prediction error on each unchanged exploitation interval. These bounds yield the stable-mismatch baseline in Theorem 4. Section 5 extends the detector analysis to potentially unstable mismatches under alternative input feasibility. Detection guarantee. Let ℰrefE_ ref be the event that every reached, complete, unchanged exploration block whose restart precedes the first detector failure produces an accurate reference gain. Here a detector failure is a false alarm or a change not detected by its D-round deadline; the precise reference-event definition is given in (74). Let ℰdetE_ det be the event of no false alarms and exactly one alarm per change. Writing τ^(c) τ^(c) for the output time of the alarm corresponding to change c, this event also requires τ(c)<τ^(c)≤τ(c)+D,c=1,…,C. τ^(c)< τ^(c)≤τ^(c)+D, c=1,…,C. (13) Theorem 2 (Alarm correspondence). Under the complete assumptions in Appendices A and B and the tuning above, ℙ⁡(ℰref∩ℰdetc)≤δd. (E_ ref _ det^c)≤ _d. (14) Proof. See Theorem 18 and Appendix H. ∎ This joint bound controls detector failure on accurate-reference histories; reference-estimation failures enter Theorem 4 separately. Why the detector works. Let ℱtF_t denote the information available when utu_t is selected, including the controller’s randomization and the selected input. Suppose the current reference is accurate and the plant has not changed since its exploration. The gate and input feasibility then give, at each recorded output time s, ys=ws+vs,|vs|≤εy, y_s=w_s+v_s, |v_s|≤ _y, (15) where vs:=ys−wsv_s:=y_s-w_s is ℱs−1F_s-1-measurable and εy _y is the deterministic output-tracking bound in (49). Thus wsw_s is fresh noise relative to vsv_s. The tuning makes vs2v_s^2 small enough that concentration of ws2w_s^2 and 2wsvs2w_sv_s keeps unchanged windows below the threshold with high probability. After a change from θ−θ^- to θ+θ^+ at control time τ, we compare the learner with an auxiliary process that applies the exact old gain λ⁡(θ−)λ(θ^-) to the new plant. It starts from the learner’s regressor ψτ _τ and uses the same future disturbances: ψτaux _τ aux =ψτ, = _τ, ψt+1aux _t+1 aux =AΔψtaux+e1wt+1,t≥τ. =A_ _t aux+e_1w_t+1, t≥τ. Here AΔA_ is the closed-loop matrix of the new plant under the old gain, e1∈ℝde_1 ^d is the first coordinate vector, and ysaux=e1ψsauxy_s aux=e_1 T _s aux is the auxiliary output; see (68). For a fixed calendar time s with s−h≥τs-h≥τ, the fresh disturbances over the preceding h steps give ⁡[(ysaux)2∣ℱs−h] [(y_s aux)^2 _s-h] =(e1AΔhψs−haux)2+σw2∑j=0h−1(e1AΔje1)2 =(e_1 TA_ ^h _s-h aux)^2+ _w^2 _j=0^h-1(e_1 TA_ ^je_1)^2 ≥σw2+7Δ8. ≥ _w^2+ 7 8. (16) The initial-state term is nonnegative, and the choice of h loses at most Δ/8 /8 from the stationary power gap. On an accurate-reference history, the gate and stability also ensure |ys2−(ysaux)2|≤Δ/8|y_s^2-(y_s aux)^2|≤ /8 until the next alarm or plant change. With high probability, the average of m fully post-change auxiliary output squares lies at most Δ/8 /8 below its average conditional power. Unless an alarm occurs earlier, the actual average is therefore at least σw2+5Δ/8 _w^2+5 /8, above the threshold. The sampling calendar supplies such a window by τ+Dτ+D; the dwell-time condition prevents another change before this deadline. Restart times depend on past observations. For each potential restart, the proof uses a continuation with the same control and recording rules but suppresses subsequent restarts. It agrees with the implemented trajectory through the first alarm. Joint failure bounds over reached histories give the global guarantee without conditioning on future detector success; see Appendices H and I. With restarts and detection delays controlled, we next bound the RLS regret accumulated during unchanged exploitation. Theorem 3 (Unchanged exploitation prefixes). Suppose a full exploration block [r,r+H)[r,r+H) lies in one regime and its Gram and estimation events hold. Under the baseline conditions and tuning, conditional on the history at r+Hr+H, with probability at least 1−δ01- _0, simultaneously for every exploitation prefix ending no later than the next plant change, restart, or horizon, ∑t=r+Hr+H+n−1(yt+1−wt+1)2≤RE(n,δ0). _t=r+H^r+H+n-1(y_t+1-w_t+1)^2≤ R_E(n, _0). (17) Here RER_E is the explicit bound in (78). For fixed model, noise, and exploration constants and the prescribed choice of H, it satisfies RE(T,δ0)=O⁡(log⁡((T+1)/δ))R_E(T, _0)=O( ((T+1)/δ)). Theorem 19 and Appendix G give the conditional, time-uniform bound. Its main mechanism is as follows. RLS argument. Consider an unchanged exploitation interval in segment c after successful exploration, and write λ=λ⁡(θ(c))λ=λ(θ^(c)) and b⋆=b1(c)b_ =b_1^(c). Define the RLS proposal error and the applied action error by at=(λ^t−λ)ψt,et=ut−λψt.a_t=( λ_t-λ) T _t, e_t=u_t-λ T _t. Reference accuracy, the gate, and feasibility of the ideal action imply et2≤at2e_t^2≤ a_t^2. Thus it suffices to control the cumulative RLS proposal error, even on rounds that use the reference input or clipping. The response used by RLS satisfies xt+1λ x_t+1^λ =λψt+αet+ηt+1, =λ T _t+α e_t+ _t+1, α α :=1−b⋆b^r,ηt+1:=−wt+1b^r. :=1- b_ b_r, _t+1:=- w_t+1 b_r. Here αetα e_t is the predictable bias caused by estimating b⋆b_ , whereas ηt+1 _t+1 is bounded and conditionally mean zero. To track estimation progress, define Qt Q_t =(λ^t−λ)Vt(λ^t−λ), =( λ_t-λ) TV_t( λ_t-λ), ℓt _t =ψtVt+1−1ψt. = _t TV_t+1^-1 _t. Exploration controls both |α||α| and ℓt _t. Consequently, the exact RLS identity gives Qt+1−Qt≤−c0at2+2atηt+1+2ℓtηt+12, Q_t+1-Q_t≤-c_0a_t^2+2a_t _t+1+2 _t _t+1^2, (18) with c0>0c_0>0 defined in (77). With probability at least 1−δ01- _0, a time-uniform martingale bound controls the cumulative mixed term by a fraction of c0∑tat2c_0 _ta_t^2 plus a confidence term. Bounded noise and the log-determinant bound on ∑tℓt _t _t control the final term logarithmically. Summing (18), using Qt≥0Q_t≥ 0 and Qr+H≤Q¯HQ_r+H≤ Q_H, therefore bounds ∑tat2 _ta_t^2 simultaneously over every exploitation prefix. Finally, (yt+1−wt+1)2=b⋆2et2≤b¯2at2,(y_t+1-w_t+1)^2=b_ ^2e_t^2≤ b^2a_t^2, which yields Theorem 3. Appendix G gives the identities and concentration details. Theorem 4 (Stable-mismatch regret guarantee). Under Assumption 1, the exploration setup in Section 3, and the precise model and exploration bounds in Appendices A–B, choose the smallest feasible H and the detector tuning (12). Then, with probability at least 1−δ1-δ, there are no false alarms, every change has exactly one alarm satisfying (13), and ℛT≤CKDD+(C+1)KXH+(C+1)RE(T,δ0), _T≤ CK_DD+(C+1)K_XH+(C+1)R_E(T, _0), (19) where the fixed per-step delay and exploration bounds KD,KXK_D,K_X are defined in (84)–(85). Consequently, when all problem constants (model orders, model-class and noise bounds, initial state, exploration and ridge settings, stability constants, clipping threshold, and power gap) are held fixed as T grows, ℛT=O⁡((C+1)log⁡T+1δ). _T=O\! ((C+1) T+1δ ). (20) Proof. See Theorem 20 and Appendices I–J. ∎ Proof sketch of Theorem 4. The regret splits into three parts: each change costs at most KDDK_DD before it is detected (per-step cost KDK_D times delay D), each of the C+1C+1 exploration blocks costs at most KXHK_XH, and Theorem 3 bounds the regret on the remaining unchanged exploitation periods. For the probability, each restart can fail in three ways (insufficient excitation, inaccurate estimate, or RLS failure), each with probability at most δ0 _0, and at most T+1T+1 restarts are possible. Adding the detector failure probability δd _d gives a total of 3(T+1)δ0+δd<δ3(T+1) _0+ _d<δ. Because restart times are random, failures are counted in time order, each only if its restart is actually reached; Appendix I gives the details. 5 DETECTION UNDER STABLE AND UNSTABLE MISMATCHES The baseline theorem in Section 4 assumes that the new plant remains stable under the old controller. We now allow this mismatched closed loop to be unstable. Its stationary power may then be unavailable, and clipping can alter its output-energy signal. We address these issues by converting both detectability conditions below into a common finite-window gap and combining the energy test with an alarm on the reference gain’s input proposal. Fixed-window comparisons replace the comparison over the full detection delay used in the stable analysis. Two sources of detectable energy. Let ⊆Θ2P ^2 be the prescribed class of admissible adjacent parameter pairs. For an actual change zc=(θ(c−1),θ(c))z_c=(θ^(c-1),θ^(c)), c=1,…,Cc=1,…,C, write Ac:=Azc:=A⁡(θ(c−1),θ(c)),A_c:=A_z_c:=A(θ^(c-1),θ^(c)), the closed-loop matrix of the new plant under the old gain. We cover P by two possibly overlapping subfamilies. In the stable subfamily P_ S, known common constants C<∞C_ S<∞, ρ∈(0,1) _ S∈(0,1), and Δ¯>0 _ S>0 satisfy ‖Ack‖ A_c^k ≤Cρk(k≥0), ≤ C_ S _ S^k (k≥ 0), Jy(λ⁡(θ(c−1)),θ(c)) J_y(λ(θ^(c-1));θ^(c)) ≥σw2+Δ¯. ≥ _w^2+ _ S. (21) In the finite-visible subfamily P_ F, a known common Δ¯>0 _ F>0 instead satisfies ⁡(zc):=σw2∑j=1d(e1Acje1)2≥Δ¯, (z_c):= _w^2 _j=1^d(e_1 TA_c^je_1)^2≥ _ F, (22) where e1∈ℝde_1 ^d is the first coordinate vector. The coefficients e1Acje1e_1 TA_c^je_1 describe a disturbance’s effect on later outputs, so ⁡(zc)V(z_c) measures its excess energy over the first d lags. This condition permits unstable mismatches. Every actual pair belongs to ⊆∪P _ S _ F; the algorithm uses the class-wide bounds for tuning but never determines which subfamily covers a particular change. A common finite-window gap. For an integer h≥1h≥ 1 and a d×d× d matrix A, define Gh(A):=σw2∑j=1h−1(e1Aje1)2.G_h(A):= _w^2 _j=1^h-1(e_1 TA^je_1)^2. It measures the excess variance supplied by the preceding h−1h-1 disturbances. For stable pairs, the omitted tail is bounded by r(h)r_ S(h) below. When both subfamilies are nonempty, choose r(h) r_ S(h) :=σw2C2ρ2h1−ρ2, := _w^2C_ S^2 _ S^2h1- _ S^2, h h_ S :=min⁡h≥1:r(h)≤Δ¯/8, := \h≥ 1:r_ S(h)≤ _ S/8\, h h_ U :=max⁡d+1,h,Δ¯:=min⁡7Δ¯/8,Δ¯. := \d+1,h_ S\, _ U:= \7 _ S/8, _ F\. (23) Appendix K gives the convention when a subfamily is empty. Since h≥h_ U≥ h_ S bounds the stable tail and h≥d+1h_ U≥ d+1 includes every term in (22), Gh(Ac)≥7Δ¯/8,zc∈,Δ¯,zc∈,≥Δ¯. G_h_ U(A_c)≥ cases7 _ S/8,&z_c _ S,\\ _ F,&z_c _ F, cases≥ _ U. (24) Stable pairs therefore need not satisfy a separate first-d visibility condition: their stationary gap supplies the required finite-window gap. The detector and its tuning. Algorithm L.1 retains PIECE-CD’s exploration, estimation, gated RLS updates, and restart rule. Its energy test records one output square every h_ U rounds and raises an alarm when the average of the latest m_ U recorded squares reaches σw2+Δ¯/2 _w^2+ _ U/2. Let B_ U be the common bound on disturbances, actual outputs, and auxiliary old-gain outputs over an h_ U-step comparison, defined in (141). The auxiliary bound is finite even for an unstable mismatch because each comparison lasts only h_ U steps. Set the number of recorded outputs and the detection-delay bound to m m_ U :=⌈512B4Δ¯2log⁡4T2δd⌉, := 512B_ U^4 _ U^2 4T^2 _d , D D_ U :=(m+1)h. :=(m_ U+1)h_ U. (25) To handle clipping, replace uniform feasibility by closed own-regime feasibility (Assumption 24). Each ideal gain must respect the input bound on every regressor reached after at least r0r_0 controls under its own plant, from any initial regressor of norm at most BψB_ψ, with bounded disturbances and arbitrary inputs in [−Bu,Bu][-B_u,B_u]. Equality is allowed. This is an alternative condition: it need not follow from baseline feasibility because it also allows initially unreachable regressors. The old gain need not remain feasible after a change. The additional test monitors the reference gain’s input proposal. After observing yt+1y_t+1 and forming ψt+1 _t+1, it raises an alarm if |λ¯rψt+1|>Bu+ζH,ζH:=Eλ(H,δ0)Bψ. | λ_r T _t+1|>B_u+ _H, _H:=E_λ(H, _0)B_ψ. (26) With an accurate reference, own-regime feasibility prevents this alarm while the plant is unchanged. After a change, before this alarm fires, the old ideal input exceeds the allowed interval by at most 2ζH2 _H, and the applied input differs from it by at most 7ζH7 _H. These bounds control the effect of clipping in the finite-step comparison. Choose H to satisfy the exploration and RLS conditions together with (142), which controls finite-window tracking errors. Smaller gaps require longer exploration and detection windows, increasing the required dwell time and regret constant. Either test triggers a restart, with simultaneous crossings counted as one alarm. The following theorem gives the detection and logarithmic-regret guarantees. Theorem 5 (Detection and regret for the union class). Retain the compact-model, noise, and open-loop switching-stability conditions of Assumption 1, and impose the own-regime feasibility above. Under the precise union-class conditions in Assumption 26, suppose each actual adjacent pair satisfies at least one of (21) and (22), without revealing which one. Choose H as the smallest feasible integer satisfying (93), (51), and (142); choose m,Dm_ U,D_ U by (25), and impose (6) with D_ U in place of D. Then Algorithm L.1, with probability at least 1−δ1-δ, has no false alarms, and each change has exactly one alarm τ^(c) τ^(c) satisfying τ(c)<τ^(c)≤τ(c)+D, τ^(c)< τ^(c)≤τ^(c)+D_ U, (27) and ℛT≤CKDD+(C+1)KXH+(C+1)RE(T,δ0). _T≤ CK_DD_ U+(C+1)K_XH+(C+1)R_E(T, _0). (28) For fixed model and union-class bounds, including every applicable positive gap bound for the nonempty cover components, this is O⁡((C+1)log⁡((T+1)/δ))O((C+1) ((T+1)/δ)). The algorithm never determines which subfamily covers any particular change. Proof. See Theorem 31 in Appendix L. ∎ Detection argument for Theorem 5. The proof starts a separate h_ U-step auxiliary process before each stored output. If the boundary test has not already crossed, the actual and auxiliary output squares remain close over these finitely many steps. For a pair in P_ S, its stationary gap and stable-tail bound give conditional auxiliary energy at least σw2+7Δ¯/8 _w^2+7 _ S/8; for a pair in P_ F, finite visibility gives at least σw2+Δ¯ _w^2+ _ F. Equation (24) therefore supplies the same Δ¯ _ U to the concentration argument in both cases. Finite-order visibility of unstable ARX mismatches. Spectral instability alone does not imply visibility for arbitrary matrices. For this compact minimum-phase ARX class, (131) derives a uniform finite-order gap from ρ⁡(A⁡(θ−,θ+))≥1ρ(A(θ^-,θ^+))≥ 1, so no separate visibility assumption is needed on that subclass. Why input feasibility is needed. Some restriction on saturation is unavoidable for the regret benchmark in (3). For every clipped policy, ℛT≥bmin2∑t=0T−1(|λ(θt)ψt|−Bu)+2. _T≥ b_ ^2 _t=0^T-1(|λ( _t) T _t|-B_u)_+^2. (29) Appendix K also gives an exploitation bound with this saturation energy as an additive term. Persistent saturation can therefore force linear regret, even when the parameter is known. 6 EVENTUAL CLIPPING INACTIVITY For stable detectable mismatches, a separate variant replaces uniform clipping feasibility by a steady-state slack condition. Define P∞(Bu):=(Cy1−ρy(Bw+BbBu))2+(q−1)Bu2,P_∞(B_u):= ( C_y1- _y(B_w+B_bB_u) )^2+(q-1)B_u^2, where Cy,ρyC_y, _y are the uniform open-loop switching bounds and BbB_b bounds the sum of absolute input coefficients. Let Λ=supθ∈Θ‖λ⁡(θ)‖ = _θ∈ λ(θ) . The quantity P∞P_∞ bounds the forced-response contribution to the regressor norm; the slack absorbs the decaying initial-state term. Theorem 6 (Regret under eventual clipping inactivity). Retain the baseline model, noise, switching-stability, stable power-gap, and exploration conditions, but replace uniform feasibility by μ0:=Bu−ΛP∞(Bu)>0. _0:=B_u- P_∞(B_u)>0. (30) Choose the smallest baseline-feasible H also satisfying εu≤μ0/2 _u≤ _0/2. After each full exploration, use the clipped reference controller for τnc _ nc rounds, with RLS and detection disabled, where τnc _ nc is given by (119) with μnc=μ0−εu _ nc= _0- _u. At t0=r+H+τnct_0=r+H+ _ nc, initialize RLS from the same exploration data as in Section 3, and record outputs at t0+jht_0+jh, j≥1j≥ 1. Use (6) with H+τncH+ _ nc in place of H. With probability at least 1−δ1-δ, there are no false alarms, every change is detected within D rounds, and ℛT≤ _T≤ CKDD+(C+1)KXH+(C+1)KDτnc+RE(T,δ0). CK_DD+(C+1)K_XH+(C+1)\K_D _ nc+R_E(T, _0)\. (31) For fixed problem constants and positive slack, τnc=O⁡(1) _ nc=O(1), so the regret remains O⁡((C+1)log⁡((T+1)/δ))O((C+1) ((T+1)/δ)). Proposition 23 and the burn-in argument in Appendix K.2 establish feasibility after the burn-in, including the continuations needed for detection. Thus only the additional bounded cost per restart enters the regret decomposition. 7 LIMITATIONS The logarithmic horizon dependence holds for fixed change count, confidence level, and problem constants. The bounds retain the factor C+1C+1 when changes become more frequent. A uniform energy gap and sufficient dwell time are essential: hidden or arbitrarily weak changes are outside the guarantees. The algorithm also requires supplied bounds on noise, detectability, excitation, and the relevant stability and finite-window sensitivities. Smaller gaps increase the delay and required dwell time. Estimating these bounds, removing knowledge of the horizon, and accommodating heavy-tailed disturbances remain open extensions. The feasibility conditions restrict the nonlinear effects of saturation; they do not cover arbitrary clipped dynamics. 8 CONCLUSION We establish high-probability regret O⁡((C+1)log⁡((T+1)/δ))O((C+1) ((T+1)/δ)) for minimum-variance control of unknown piecewise-stationary ARX systems under fixed detectability gaps and the stated feasibility and dwell-time conditions. PIECE-CD uses output observations during exploitation to detect changes, explores at initialization and after each alarm, and uses gated RLS to control regret between changes. A common detection rule covers both stable controller mismatches with a stationary power gap and potentially unstable mismatches whose disturbance response produces detectable excess energy within a fixed number of steps. AI Use Statement Generative AI tools assisted with editing and reorganizing the exposition, checking consistency between main-text statements and the appendices, and LaTeX formatting and compilation checks. The authors take responsibility for the final text, mathematical claims, proofs, and references. References Abbasi-Yadkori et al., (2011) Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24. Audibert and Bubeck, (2009) Audibert, J.-Y. and Bubeck, S. (2009). Minimax policies for adversarial and stochastic bandits. In Proceedings of the 22nd Annual Conference on Learning Theory. Azuma, (1967) Azuma, K. (1967). Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, 19(3):357–367. Becker et al., (1985) Becker, A., Kumar, P. R., and Wei, C.-Z. (1985). Adaptive control with the stochastic approximation algorithm: Geometry and convergence. IEEE Transactions on Automatic Control, 30(4):330–338. Besbes et al., (2014) Besbes, O., Gur, Y., and Zeevi, A. (2014). Stochastic multi-armed-bandit problem with non-stationary rewards. In Advances in Neural Information Processing Systems, volume 27, pages 199–207. Besson et al., (2022) Besson, L., Kaufmann, E., Maillard, O.-A., and Seznec, J. (2022). Efficient change-point detection for tackling piecewise-stationary bandits. Journal of Machine Learning Research, 23(77):1–40. Cao et al., (2019) Cao, Y., Wen, Z., Kveton, B., and Xie, Y. (2019). Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 418–427. PMLR. Garivier and Moulines, (2011) Garivier, A. and Moulines, E. (2011). On upper-confidence bound policies for switching bandit problems. In Proceedings of the 22nd International Conference on Algorithmic Learning Theory, pages 174–188. Goodwin et al., (1981) Goodwin, G. C., Ramadge, P. J., and Caines, P. E. (1981). Discrete time stochastic adaptive control. SIAM Journal on Control and Optimization, 19(6):829–853. Hoeffding, (1963) Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30. Horn and Johnson, (2013) Horn, R. A. and Johnson, C. R. (2013). Matrix Analysis. Cambridge University Press, Cambridge, 2 edition. Howard et al., (2020) Howard, S. R., Ramdas, A., McAuliffe, J., and Sekhon, J. (2020). Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys, 17:257–317. Huang et al., (2026) Huang, Y.-H., Gerogiannis, A., Bose, S., and Veeravalli, V. V. (2026). Detection augmented bandit procedures for piecewise stationary MABs: A modular approach. IEEE Transactions on Information Theory. Kumar and Praly, (1987) Kumar, P. R. and Praly, L. (1987). Self-tuning trackers. SIAM Journal on Control and Optimization, 25(4):1053–1071. Lai, (1986) Lai, T. L. (1986). Asymptotically efficient adaptive control in stochastic regression models. Advances in Applied Mathematics, 7(1):23–45. Lai and Robbins, (1985) Lai, T. L. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4–22. Lai and Wei, (1987) Lai, T. L. and Wei, C.-Z. (1987). Asymptotically efficient self-tuning regulators. SIAM Journal on Control and Optimization, 25(2):466–481. Liu et al., (2018) Liu, F., Lee, J., and Shroff, N. B. (2018). A change-detection based framework for piecewise-stationary multi-armed bandit problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, pages 3651–3658. Mukherjee and Maillard, (2019) Mukherjee, S. and Maillard, O.-A. (2019). Distribution-dependent and time-uniform bounds for piecewise i.i.d. bandits. arXiv preprint arXiv:1905.13159. Simchowitz and Foster, (2020) Simchowitz, M. and Foster, D. (2020). Naive exploration is optimal for online LQR. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8937–8948. PMLR. Singh et al., (2024) Singh, R., Mete, A., Kar, A., and Kumar, P. R. (2024). Finite time logarithmic regret bounds for self-tuning regulation. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 45571–45636. PMLR. Tartakovsky et al., (2014) Tartakovsky, A., Nikiforov, I., and Basseville, M. (2014). Sequential Analysis: Hypothesis Testing and Changepoint Detection. CRC Press. Tropp, (2011) Tropp, J. A. (2011). Freedman’s inequality for matrix martingales. Electronic Communications in Probability, 16:262–270. Veeravalli and Banerjee, (2014) Veeravalli, V. V. and Banerjee, T. (2014). Quickest change detection. Academic Press Library in Signal Processing, 3:209–255. Ville, (1939) Ville, J. (1939). Étude critique de la notion de collectif. Gauthier-Villars, Paris. Xie et al., (2021) Xie, L., Zou, S., Xie, Y., and Veeravalli, V. V. (2021). Sequential (quickest) change detection: Classical results and new directions. IEEE Journal on Selected Areas in Information Theory, 2(2):494–514. Zhou et al., (2020) Zhou, H., Wang, L., Varshney, L. R., and Lim, E.-P. (2020). A near-optimal change-detection based algorithm for piecewise-stationary combinatorial semi-bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 6933–6940. APPENDIX CONTENTS AAppendix A MODEL AND ASSUMPTIONS.A BAppendix B THE PIECE-CD ALGORITHM.B CAppendix C CHANGE-DETECTION GUARANTEES.C DAppendix D REGRET ANALYSIS.D EAppendix E DETERMINISTIC BOUNDS AND RESTART CONVENTIONS.E FAppendix F EXPLORATION, EXCITATION, AND THE RESTARTED ESTIMATE.F GAppendix G THE RLS POTENTIAL ARGUMENT.G HAppendix H DETAILED DETECTOR PROOFS.H IAppendix I GLOBAL EVENT AND REGRET DECOMPOSITION.I JAppendix J TUNING FEASIBILITY AND ORDERS.J KAppendix K RELAXATIONS OF CLIPPING AND MISMATCH STABILITY.K LAppendix L A UNIFIED DETECTOR FOR THE UNION CLASS.L ROADMAP OF THE APPENDICES A. Specifies the piecewise-stationary ARX model, regret criterion, and assumptions on stability, noise, clipping feasibility, and detectability of adjacent changes. B. Gives the exploration estimator, gated RLS controller, output-energy detector, tuning and dwell-time requirements, and complete PIECE-CD algorithm. C. Proves action tracking, sampled-square concentration, false-alarm control, detection delay, and correspondence between alarms and true changes. D. Derives exploitation regret on unchanged segments and combines it with exploration and detection-delay costs to obtain the total regret guarantee. E. Establishes deterministic output and regressor bounds, clipping projection inequalities, auxiliary-process bounds, and conditioning conventions at random restarts. F. Proves conditional excitation, exploration Gram-matrix growth, and projected ridge estimation bounds for a complete unchanged exploration block. G. Develops the RLS potential identity, time-uniform noise control, and elliptical-potential bound underlying the segmentwise exploitation guarantee. H. Supplies detailed auxiliary-process power, sampling, coupling, and calendar arguments supporting the detection results in Appendix C. I. Constructs a common success event and partitions the horizon to complete the proof of the global regret bound. J. Verifies feasibility of the tuning requirements and derives the logarithmic orders of exploration length, detection delay, and regret. K. Develops the clipping-feasibility relaxations, eventual nonclipping, boundary alarms, finite-order visibility and union-class detection, and regret bounds with saturation. L. Presents the unified union-class algorithm and common tuning, then proves detection and regret guarantees without identifying the realized mismatch class. Appendix A MODEL AND ASSUMPTIONS Fix an integer horizon T≥1T≥ 1, confidence level δ∈(0,1)δ∈(0,1), and integer model orders p,q≥1p,q≥ 1. The deterministic but unknown segment boundaries are 0=τ(0)<τ(1)<⋯<τ(C)<τ(C+1)=T.0=τ^(0)<τ^(1)<·s<τ^(C)<τ^(C+1)=T. On segment c, the parameter θ(c) θ^(c) :=(a1(c),…,ap(c),b1(c),…,bq(c))′ :=(a_1^(c),…,a_p^(c),b_1^(c),…,b_q^(c)) is active at control times τ(c)≤t<τ(c+1)τ^(c)≤ t<τ^(c+1), and the system obeys yt+1 y_t+1 =∑i=1pai(c)yt−i+1+∑j=1qbj(c)ut−j+1+wt+1,τ(c)≤t<τ(c+1). = _i=1^pa_i^(c)y_t-i+1+ _j=1^qb_j^(c)u_t-j+1+w_t+1, τ^(c)≤ t<τ^(c+1). (32) Write θt=θ(c) _t=θ^(c) on this segment and Yt=(yt,…,yt−p+1)′Y_t=(y_t,…,y_t-p+1) . The initial history is fixed, with ‖Y0‖<∞ Y_0 <∞ and |ut|≤Bu|u_t|≤ B_u for t=−q+1,…,−1t=-q+1,…,-1. The control and identification regressors are ψt _t :=(yt,…,yt−p+1,ut−1,…,ut−q+1)′, :=(y_t,…,y_t-p+1,u_t-1,…,u_t-q+1) , (33) ϕt _t :=(yt,…,yt−p+1,ut,ut−1,…,ut−q+1)′,d:=p+q−1. :=(y_t,…,y_t-p+1,u_t,u_t-1,…,u_t-q+1) , d:=p+q-1. (34) For θ=(a1,…,ap,b1,…,bq)θ=(a_1,…,a_p,b_1,…,b_q) with b1≠0b_1≠ 0, define λ⁡(θ):=−1b1(a1,…,ap,b2,…,bq)′. λ(θ):=- 1b_1(a_1,…,a_p,b_2,…,b_q) . (35) The corresponding gain representation is yt+1=b1(c)ut−λ(θ(c))′ψt+wt+1. y_t+1=b_1^(c)\u_t-λ(θ^(c)) _t\+w_t+1. (36) The ideal input ut=λ(θ(c))′ψtu_t=λ(θ^(c)) _t leaves only the disturbance in the output. Our sample-path learning regret is ℛT:=∑t=0T−1(yt+1−wt+1)2. _T:= _t=0^T-1(y_t+1-w_t+1)^2. Let ℱtF_t contain the initial history, the controller randomization revealed through time t, and all inputs and outputs available when utu_t is selected. In particular, utu_t is ℱtF_t-measurable. Assumption 7 (Known model class). The controller knows a compact set Θ⊂ℝp+q ^p+q containing every θ(c)θ^(c). For each θ∈Θθ∈ , the autoregressive polynomial is Schur stable, the input polynomial is minimum phase, and 0<bmin≤b1(θ)≤b¯<∞. 0<b_ ≤ b_1(θ)≤ b<∞. (37) The gain map in (35) is therefore Lipschitz on Θ ; fix a strictly positive known Lipschitz bound Lλ>0L_λ>0 satisfying ‖λ⁡(θ)−λ⁡(ϑ)‖≤Lλ‖θ−ϑ‖,θ,ϑ∈Θ. λ(θ)-λ( ) ≤ L_λ θ- , θ, ∈ . (38) Write Λ:=supθ∈Θ‖λ⁡(θ)‖ := _θ∈ λ(θ) and Bb:=supθ∈Θ∑j=1q|bj(θ)|B_b:= _θ∈ _j=1^q|b_j(θ)|. Let Ay(θ)A_y(θ) be the companion matrix in (88). A parameter sequence is admissible if it takes values in Θ and is piecewise constant at the specified segment boundaries. Individual Schur stability does not ensure stability under switching, so we impose the following uniform product bound. Assumption 8 (Uniform switching stability). There are 1≤Cy<∞1≤ C_y<∞ and ρy∈(0,1) _y∈(0,1) such that, for every admissible parameter sequence and every k≥0k≥ 0, ‖Ay(θt+k−1)⋯Ay(θt)‖≤Cyρyk. A_y( _t+k-1)·s A_y( _t) ≤ C_y _y^k. (39) Assumption 9 (Noise). Each wtw_t is independent of ℱt−1F_t-1, and the disturbances are identically distributed. They satisfy wt=0,wt2=σw2>0,|wt|≤Bwalmost surely. _t=0, _t^2= _w^2>0, |w_t|≤ B_w surely. The detector knows σw2 _w^2 and BwB_w. The algorithm always clips its input to [−Bu,Bu][-B_u,B_u]. Consequently, Assumptions 7–9 imply the deterministic bounds BY B_Y :=Cy‖Y0‖+Cy1−ρy(Bw+BbBu), :=C_y Y_0 + C_y1- _y(B_w+B_bB_u), |yt| |y_t| ≤BY, ≤ B_Y, Bψ B_ψ :=pBY2+(q−1)Bu21/2, :=\pB_Y^2+(q-1)B_u^2\^1/2, ‖ψt‖ _t ≤Bψ. ≤ B_ψ. (40) A proof is given in Appendix E. For the baseline analysis, the ideal action must also be feasible at every reachable regressor. Here, reachability is from the fixed initial history under admissible parameter sequences, disturbances bounded by BwB_w, and inputs in [−Bu,Bu][-B_u,B_u]. Assumption 10 (Uniform clipping feasibility). The ideal action belongs to the closed clipping interval: |λ(θ)′ψ|≤Bufor every θ∈Θand every reachable ψ with ‖ψ‖≤Bψ. |λ(θ) ψ |≤ B_u every θ∈ every reachable ψ with ψ ≤ B_ψ. The stronger condition ΛBψ≤Bu B_ψ≤ B_u is sufficient. Equality is allowed; projection nonexpansiveness requires no positive margin. For a gain ℓ∈ℝd ^d and parameter θ, let Acl(ℓ,θ)A_ cl( ,θ) be the matrix satisfying ψt+1=Acl(ℓ,θ)ψt+e1wt+1 _t+1=A_ cl( ,θ) _t+e_1w_t+1 (41) when the unclipped input ut=ℓ′ψtu_t= _t is applied. Here e1e_1 is the first coordinate vector. If the input is ut=ℓ′ψt+etu_t= _t+e_t, the regressor dynamics become ψt+1=Acl(ℓ,θ)ψt+gu(θ)et+e1wt+1, _t+1=A_ cl( ,θ) _t+g_u(θ)e_t+e_1w_t+1, where the input-channel vector and its uniform bound are defined by gu(θ):=b1(θ)e1,q=1,(b1(θ),0p−1′,1,0q−2′)′,q≥2,Gu:=supθ∈Θ‖gu(θ)‖≤b¯2+1. g_u(θ):= casesb_1(θ)e_1,&q=1,\\ (b_1(θ),0_p-1 ,1,0_q-2 ) ,&q≥ 2, cases G_u:= _θ∈ g_u(θ) ≤ b^2+1. (42) Here 0k0_k denotes the zero vector in ℝkR^k; the final block is absent when q=2q=2. When Acl(ℓ,θ)A_ cl( ,θ) is Schur stable, define its stationary output power Jy(ℓ,θ):=σw2∑j=0∞e1′Acl(ℓ,θ)je12. J_y( ;θ):= _w^2 _j=0^∞\e_1 A_ cl( ,θ)^je_1\^2. (43) To justify this terminology, freeze (ℓ,θ)( ,θ) and put A=Acl(ℓ,θ)A=A_ cl( ,θ). The zero-mean stationary solution of ψt+1=Aψt+e1wt+1 _t+1=A _t+e_1w_t+1 is ψtstat=∑j=0∞Aje1wt−j. _t stat= _j=0^∞A^je_1w_t-j. The series converges in mean square because A is Schur. Its first coordinate is the stationary output. Independence, zero mean, and wt2=σw2Ew_t^2= _w^2 eliminate all cross terms, so ⁡[(ytstat)2] [(y_t stat)^2] =∑j,k≥0(e1′Aje1)(e1′Ake1)[wt−jwt−k] = _j,k≥ 0(e_1 A^je_1)(e_1 A^ke_1)E[w_t-jw_t-k] =σw2∑j=0∞(e1′Aje1)2=Jy(ℓ,θ). = _w^2 _j=0^∞(e_1 A^je_1)^2=J_y( ;θ). Thus (43) is the stationary second moment (and, because the mean is zero, the variance) of the unclipped frozen-gain output process. It is not asserted directly for the implemented clipped trajectory; Lemmas 13 and 16 provide that comparison. In particular, Jy(λ⁡(θ),θ)=σw2J_y(λ(θ);θ)= _w^2. Assumption 11 (Stable and detectable adjacent changes). There are CΔ<∞C_ <∞, ρΔ∈(0,1) _ ∈(0,1), and Δ>0 >0 such that, for every actual adjacent pair (θ(c−1),θ(c))(θ^(c-1),θ^(c)), ‖Acl(λ⁡(θ(c−1)),θ(c))k‖ A_ cl(λ(θ^(c-1)),θ^(c))^k ≤CΔρΔk,k≥0, ≤ C_ _ ^k, k≥ 0, (44) Jy(λ⁡(θ(c−1)),θ(c)) J_y(λ(θ^(c-1));θ^(c)) ≥σw2+Δ. ≥ _w^2+ . (45) The power-gap condition excludes changes that leave the old controller’s output power unchanged. Appendix K gives two extensions: a burn-in variant under eventual nonclipping, and a boundary-alarm variant covering both stable power gaps and finite-order visibility. Tuning requires valid bounds for CΔC_ , ρΔ _ , and Δ , and the model and exploration bounds defining BψB_ψ, BoB_o, and κG _G in (40), (50), and (92). Conservative bounds suffice; the analysis does not provide a data-driven calibration rule. Appendix B THE PIECE-CD ALGORITHM Each PIECE-CD cycle consists of H exploration rounds followed by gated RLS control and output-energy monitoring. An alarm starts a new cycle. B.1 Exploration and Estimation Let s:=p+qs:=p+q, r0:=max⁡p,qr_0:= \p,q\, and nH:=H−r0n_H:=H-r_0. Fix a ridge parameter ν>0ν>0. Exploration uses fresh i.i.d. mean-zero inputs, bounded by Be≤BuB_e≤ B_u and of variance σe2>0 _e^2>0, independent of the disturbance sequence. Conditional on ℱrF_r, uru_r is fixed and the subsequent exploration inputs remain independent with this distribution. For a full unchanged exploration block satisfying (93), Proposition 21 gives λmin(∑t=r+r0r+H−1ϕtϕt′)≥κGnH _ \! ( _t=r+r_0^r+H-1 _t _t )≥ _Gn_H with conditional probability at least 1−δ01- _0 given ℱrF_r. The constant κG>0 _G>0 in (92) is uniform over Θ and the bounded restart states. Put Bϕ:=(Bψ2+Bu2)1/2B_φ:=(B_ψ^2+B_u^2)^1/2 and SΘ:=supθ∈Θ‖θ‖S_ := _θ∈ θ . For a confidence level δ0 _0, define the deterministic estimation bound ℒH(δ0) _H( _0) :=2log⁡(1/δ0)+slog⁡(1+HBϕ2sν), :=2 (1/ _0)+s \! (1+ HB_φ^2sν ), Eθ(H,δ0) E_θ(H, _0) :=2BwℒH(δ0)+νSΘν+κGnH, := 2\B_w L_H( _0)+ νS_ \ ν+ _Gn_H, (46) Eλ(H,δ0) E_λ(H, _0) :=LλEθ(H,δ0), :=L_λE_θ(H, _0), gH g_H :=4Eλ(H,δ0). :=4E_λ(H, _0). (47) For the estimator and reference gain in (55)–(56), Proposition 22 establishes ‖θ^r−θ‖≤Eθ θ_r-θ ≤ E_θ and ‖λ¯r−λ⁡(θ)‖≤Eλ λ_r-λ(θ) ≤ E_λ on the joint Gram and estimation event. For the horizon-wide theorem we use δd:=δ/2,δ0:=δ32(T+1). _d:=δ/2, _0:= δ32(T+1). (48) This allocation remains valid without knowing C, because no more than T+1T+1 restart locations are possible. B.2 Tuning and Dwell Time On the successful reference event, Lemma 13 bounds the action and unchanged-regime output errors by εu:=54gHBψ,εy:=b¯εu. _u:= 54g_HB_ψ, _y:= b\, _u. (49) For a post-change fixed-old-gain auxiliary trajectory, set Baux B_ aux :=CΔBψ+CΔBw1−ρΔ, :=C_ B_ψ+ C_ B_w1- _ , Bo B_o :=max⁡BY,Baux,Bw, := \B_Y,B_ aux,B_w\, (50) RΔ(H) R_ (H) :=CΔGuεu1−ρΔ. := C_ G_u _u1- _ . Choose H>r0H>r_0 as the smallest integer for which the sample-size condition (93) and the following inequalities hold: Eθ(H,δ0)bmin E_θ(H, _0)b_ ≤116, ≤ 116, Bψ2ν+κGnH B_ψ^2ν+ _Gn_H ≤116, ≤ 116, (51) εy2 _y^2 ≤Δ8,εy≤Bo, ≤ 8, _y≤ B_o, 2BoRΔ(H) 2B_oR_ (H) ≤Δ8. ≤ 8. (52) Condition (51) controls the RLS bias and leverage; (52) controls the null bias and coupling error. Choose the integer sampling interval h, window size m, and delay bound D by h h :=min⁡k≥1:σw2CΔ2ρΔ2k1−ρΔ2≤Δ8, := \k≥ 1: _w^2C_ ^2 _ ^2k1- _ ^2≤ 8 \, (53) m m :=⌈512Bo4Δ2log⁡4T2δd⌉, := 512B_o^4 ^2 4T^2 _d , D D :=(m+1)h. :=(m+1)h. (54) The spacing truncates the stationary-power tail at Δ/8 /8. The window size controls both null and post-change deviations uniformly over potential restart locations and test endpoints. Assumption 12 (Minimum dwell time). The first change satisfies τ(1)≥Hτ^(1)≥ H when C≥1C≥ 1. Every pair of successive changes satisfies τ(c+1)−τ(c)≥D+H,c=1,…,C−1, τ^(c+1)-τ^(c)≥ D+H, c=1,…,C-1, and the terminal segment satisfies T−τ(C)≥DT-τ^(C)≥ D when C≥1C≥ 1. When each change is detected within D rounds, these conditions leave a full unchanged exploration block before the next change. The final exploration block may be truncated at T. B.3 Algorithm For a vector x, let ΠΘ(x) _ (x) be a measurable Euclidean projection onto Θ . If Θ is not convex, any measurable nearest-point selection can be used; the only property required below is ‖ΠΘ(x)−θ‖≤2‖x−θ‖ _ (x)-θ ≤ 2 x-θ for θ∈Θθ∈ . Indeed, since θ itself is an admissible point in the nearest-point minimization, ‖ΠΘ(x)−x‖≤‖θ−x‖. _ (x)-x ≤ θ-x . The triangle inequality therefore gives ‖ΠΘ(x)−θ‖≤‖ΠΘ(x)−x‖+‖x−θ‖≤2‖x−θ‖ _ (x)-θ ≤ _ (x)-x + x-θ ≤ 2 x-θ . This factor transfers the unprojected ridge error to the feasible estimate in Proposition 22. If Θ is closed and convex, projection is nonexpansive and the factor two can be replaced by one. Algorithm 2: The PIECE-CD algorithm Input: the known orders and model class; T,δT,δ; all tuning quantities defined above; and the exploration distribution. Initialize the restart time r←0r← 0 and clear the detector buffer. Loop. While r<Tr<T, execute the following cycle. (a) Explore. For t=r,…,min⁡r+H−1,T−1t=r,…, \r+H-1,T-1\, draw the independent exploratory input, apply it, and observe yt+1y_t+1. If the horizon ends, stop. (b) Estimate. Using the post-boundary rows ℐr:=r+r0,…,r+H−1I_r:=\r+r_0,…,r+H-1\, form Vrθ V_r^θ :=νIs+∑t∈ℐrϕtϕt′, :=ν I_s+ _t _r _t _t , θ~r θ_r :=(Vrθ)−1∑t∈ℐrϕtyt+1, :=(V_r^θ)^-1 _t _r _ty_t+1, (55) θ^r θ_r :=ΠΘ(θ~r), := _ ( θ_r), b^r b_r :=b1(θ^r), :=b_1( θ_r), λ¯r λ_r :=λ⁡(θ^r). :=λ( θ_r). (56) Initialize Vr+H:=νId+∑t∈ℐrψtψt′,λ^r+H:=λ¯r. V_r+H:=ν I_d+ _t _r _t _t , λ_r+H:= λ_r. (57) Clear the detector buffer and declare the output-time sampling grid r:=r+H+h+jh:j=0,1,…. _r:=\r+H+h+jh:j=0,1,…\. (c) Exploit and monitor. For t=r+H,r+H+1,…,T−1t=r+H,r+H+1,…,T-1, set zt:=λ^t′ψt,|(λ^t−λ¯r)′ψt|≤gH‖ψt‖,λ¯r′ψt,otherwise,ut:=clip[−Bu,Bu]⁡(zt). z_t:= cases λ_t _t,& |( λ_t- λ_r) _t |≤ g_H _t ,\\ λ_r _t,&otherwise, cases u_t:=clip_[-B_u,B_u]\! (z_t ). (58) Before observing yt+1y_t+1, declare it detector-eligible exactly when t+1∈rt+1 _r. Observe yt+1y_t+1 and make the standard RLS update with pseudo-response xt+1λ x_t+1^λ :=ut−yt+1b^r, :=u_t- y_t+1 b_r, Vt+1 V_t+1 :=Vt+ψtψt′, :=V_t+ _t _t , (59) λ^t+1 λ_t+1 :=λ^t+Vt+1−1ψt(xt+1λ−λ^t′ψt). := λ_t+V_t+1^-1 _t(x_t+1^λ- λ_t _t). (60) If yt+1y_t+1 was declared eligible, append yt+12y_t+1^2 to the buffer. Retain only the most recent m stored values. When the buffer is full, compute J^(t+1):=1m∑z∈bufferz. J(t+1):= 1m _z z. If J^(t+1)≥σw2+Δ/2 J(t+1)≥ _w^2+ /2, raise an alarm, set r←t+1r← t+1, clear the buffer, and begin a new cycle. If no alarm is raised and t=T−1t=T-1, stop. Appendix C CHANGE-DETECTION GUARANTEES Throughout this appendix, the assumptions and tuning of Appendices A and B are in force. Fix a restart r with a full uncontaminated exploration block: the parameter remains equal to θ−θ^- throughout [r,r+H)[r,r+H). Write λ−:=λ⁡(θ−)λ^-:=λ(θ^-) and define the reference event rest:=‖λ¯r−λ−‖≤gH/4 _r est:= \ λ_r-λ^- ≤ g_H/4 \ whose failure probability is controlled by Proposition 22. Lemma 13 (Gate and action tracking). On restG_r est, at every exploitation time before the next alarm, including times after an undetected change, |ut−(λ−)′ψt|≤54gH‖ψt‖≤εu. |u_t-(λ^-) _t |≤ 54g_H _t ≤ _u. (61) If no true change has occurred and at:=(λ^t−λ−)′ψta_t:=( λ_t-λ^-) _t, then the applied action error et:=ut−(λ−)′ψte_t:=u_t-(λ^-) _t also satisfies et2≤at2. e_t^2≤ a_t^2. (62) Proof. If the recursive branch of (58) is selected, then |zt−(λ−)′ψt|≤gH‖ψt‖+(gH/4)‖ψt‖. |z_t-(λ^-) _t |≤ g_H _t +(g_H/4) _t . If the reference branch is selected, the same left-hand side is at most (gH/4)‖ψt‖(g_H/4) _t . Since the ideal action (λ−)′ψt(λ^-) _t lies in [−Bu,Bu][-B_u,B_u] by Assumption 10, the metric projection onto this interval is nonexpansive and (61) follows after clipping. For (62), equality holds in the recursive branch before clipping, and nonexpansiveness can only reduce the error. In the reference branch, |at| |a_t| ≥|(λ^t−λ¯r)′ψt|−|(λ¯r−λ−)′ψt| ≥ |( λ_t- λ_r) _t |- |( λ_r-λ^-) _t | >34gH‖ψt‖, > 34g_H _t , whereas the reference action error is at most (gH/4)‖ψt‖(g_H/4) _t . Clipping again cannot increase it. ∎ C.1 Sampled-Square Concentration The sampling interval h allows concentration around conditional moments given the history h steps earlier. Lemma 14 (Lagged sampled-square concentration). Let h≤s1<⋯<smh≤ s_1<·s<s_m be finite lag-h predictable output times, meaning sk=t∈ℱt−h\s_k=t\ _t-h for every t, and suppose sk+1−sk≥hs_k+1-s_k≥ h. If XskX_s_k is ℱskF_s_k-measurable and |Xsk|≤Bo|X_s_k|≤ B_o, then, for every a>0a>0, ℙ⁡(1m∑k=1mXsk2−⁡[Xsk2∣ℱsk−h]≤−a)≤exp⁡(−ma22Bo4). \! ( 1m _k=1^m\X_s_k^2-E[X_s_k^2 _s_k-h]\≤-a )≤ \! (- ma^22B_o^4 ). (63) The analogous upper-tail bound also holds. Proof. Set Zk=Xsk2−⁡[Xsk2∣ℱsk−h]Z_k=X_s_k^2-E[X_s_k^2 _s_k-h]. With ℋk−1=ℱsk−hH_k-1=F_s_k-h and, for k<mk<m, ℋk=ℱsk+1−hH_k=F_s_k+1-h, the spacing condition implies that ZkZ_k is ℋkH_k-measurable and has conditional mean zero. Moreover, ℋm:=ℱsmH_m:=F_s_m contains ZmZ_m. Lag predictability makes the random-indexed sigma-fields well defined as stopped sigma-fields, and ℱsk⊆ℱsk+1−hF_s_k _s_k+1-h. Moreover, |Zk|≤Bo2|Z_k|≤ B_o^2. The Azuma–Hoeffding inequality (Azuma,, 1967; Hoeffding,, 1963) gives (63); the upper tail follows by applying it to −Zk-Z_k. ∎ C.2 False Alarms For each potential restart r, define an alarm-suppressed continuation by retaining the control, RLS, grid, and buffer recursions while recording threshold crossings without restarting. It coincides with the implemented trajectory through the first alarm. A block is null for restart r if every stored output is generated under the reference parameter θ−θ^-. If that parameter remains active until control time τ, a block ending at output time τ is null: yτy_τ is generated by uτ−1u_τ-1. On restG_r est, (36) and Lemma 13 give, for each stored output in a null block, ys=ws+vs,vs:=b1(θ−)us−1−(λ−)′ψs−1,|vs|≤εy. y_s=w_s+v_s, v_s:=b_1(θ^-)\u_s-1-(λ^-) _s-1\, |v_s|≤ _y. (64) The variable vsv_s is ℱs−1F_s-1-measurable, while wsw_s is independent of ℱs−1F_s-1. Hence, for any null detector block S of m stored samples, 1m∑s∈S(ys2−σw2) 1m _s∈ S(y_s^2- _w^2) =1m∑s∈S(ws2−σw2)+2m∑s∈Swsvs+1m∑s∈Svs2. = 1m _s∈ S(w_s^2- _w^2)+ 2m _s∈ Sw_sv_s+ 1m _s∈ Sv_s^2. (65) Lemma 15 (One-block false-alarm bound). Suppose (52) holds. Conditional on any ℱr+HF_r+H history on which restG_r est holds, any fixed potential block generated by the predictable sampling grid that is null for restart r crosses the threshold with probability at most δd/(2T2) _d/(2T^2). Proof. By (64), every summand in the last term of (65) satisfies vs2≤εy2v_s^2≤ _y^2. Consequently, 1m∑s∈Svs2≤εy2≤Δ8, 1m _s∈ Sv_s^2≤ _y^2≤ 8, where the final inequality is exactly the first condition in (52). The standard bounded-increment exponential supermartingale for the predictably sampled disturbance squares (Hoeffding,, 1963; Howard et al.,, 2020), applied along the fixed predictable block through its predetermined endpoint, gives ℙ⁡(1m∑s∈S(ws2−σw2)>Δ8) \! ( 1m _s∈ S(w_s^2- _w^2)> 8 ) ≤exp⁡(−mΔ232Bw4). ≤ \! (- m ^232B_w^4 ). (66) The products wsvsw_sv_s form bounded martingale differences, so the same Azuma–Hoeffding construction (Azuma,, 1967; Hoeffding,, 1963) applies. If εy=0 _y=0, this cross term vanishes identically. Otherwise, the analogous stopped exponential bound gives ℙ⁡(2m∑s∈Swsvs>Δ8) \! ( 2m _s∈ Sw_sv_s> 8 ) ≤exp⁡(−mΔ2512Bw2εy2). ≤ \! (- m ^2512B_w^2 _y^2 ). (67) With m from (54) and Bo≥max⁡Bw,εyB_o≥ \B_w, _y\, each right-hand side is at most δd/(4T2) _d/(4T^2). Outside these two deviations, the left side of (65) is at most 3Δ/8<Δ/23 /8< /2. ∎ C.3 Detection after a Change Suppose the current cycle has not alarmed when the parameter changes from θ−θ^- to θ+θ^+ at control time τ. Starting from ψτaux=ψτ _τ aux= _τ, define the auxiliary process driven by the same future disturbances and the exact old gain: ψt+1aux _t+1 aux =AΔψtaux+e1wt+1, =A_ _t aux+e_1w_t+1, AΔ A_ :=A⁡(θ−,θ+). :=A(θ^-,θ^+). (68) Let ytauxy_t aux be its first coordinate. By (44), |ytaux|≤Baux|y_t aux|≤ B_ aux. Lemma 16 (Actual-to-auxiliary coupling). On restG_r est, until the first of the next alarm and the next true change after τ, ‖ψt−ψtaux‖ _t- _t aux ≤RΔ(H), ≤ R_ (H), (69) |yt2−(ytaux)2| |y_t^2-(y_t aux)^2 | ≤2BoRΔ(H)≤Δ/8. ≤ 2B_oR_ (H)≤ /8. (70) Proof. Writing the actual input as ut=λ(θ−)′ψt+etu_t=λ(θ^-) _t+e_t and subtracting (68) yields ψt+1−ψt+1aux=AΔ(ψt−ψtaux)+gu(θ+)et. _t+1- _t+1 aux=A_ ( _t- _t aux)+g_u(θ^+)e_t. Put δt:=ψt−ψtaux _t:= _t- _t aux. Because the two processes start from the same state, δτ=0 _τ=0. Iterating the displayed recursion gives, for every t>τt>τ before the stopping endpoint, δt _t =∑k=τt−1AΔt−1−kgu(θ+)ek. = _k=τ^t-1A_ ^t-1-kg_u(θ^+)e_k. Lemma 13 gives |ek|≤εu|e_k|≤ _u, while (42) and (44) give ‖gu(θ+)‖≤Gu g_u(θ^+) ≤ G_u and ‖AΔj‖≤CΔρΔj A_ ^j ≤ C_ _ ^j. Therefore ‖δt‖ _t ≤CΔGuεu∑k=τt−1ρΔt−1−k ≤ C_ G_u _u _k=τ^t-1 _ ^t-1-k ≤CΔGuεu1−ρΔ=RΔ(H), ≤ C_ G_u _u1- _ =R_ (H), which is (69). Since output is the first state coordinate, |yt−ytaux|≤‖δt‖≤RΔ(H)|y_t-y_t aux|≤ _t ≤ R_ (H). Both outputs are bounded by BoB_o, and hence |yt2−(ytaux)2| |y_t^2-(y_t aux)^2| =|yt−ytaux||yt+ytaux| =|y_t-y_t aux|\,|y_t+y_t aux| ≤2BoRΔ(H)≤Δ8, ≤ 2B_oR_ (H)≤ 8, where the last inequality is the second condition in (52). This proves (70). ∎ For every auxiliary output time s whose preceding h controls are all post-change, independence gives the exact finite-horizon identity ⁡[(ysaux)2∣ℱs−h] [(y_s aux)^2 _s-h] =(e1′AΔhψs−haux)2+σw2∑j=0h−1(e1′AΔje1)2. =(e_1 A_ ^h _s-h aux)^2+ _w^2 _j=0^h-1(e_1 A_ ^je_1)^2. (71) Indeed, iterating (68) for h steps and taking the first coordinate gives ysaux y_s aux =e1′AΔhψs−haux+∑j=0h−1e1′AΔje1ws−j. =e_1 A_ ^h _s-h aux+ _j=0^h-1e_1 A_ ^je_1\,w_s-j. Conditional on ℱs−hF_s-h, the first term is fixed. Every future disturbance is centered and independent of that field and of the other future disturbances. Thus the state–noise cross terms and the cross terms with distinct disturbance indices have conditional expectation zero, while each diagonal disturbance term contributes its coefficient squared times σw2 _w^2. This proves (71) at deterministic s. The same identity holds at a finite lag-h predictable random output time: on each event s=t∈ℱt−h\s=t\ _t-h it is the deterministic-time identity, and summing over t gives the equality conditional on the stopped field ℱs−hF_s-h. The first term is nonnegative. Equations (45) and (53) imply the remaining inequality as follows. With AΔ=Acl(λ⁡(θ−),θ+)A_ =A_ cl(λ(θ^-),θ^+), σw2∑j=0h−1(e1′AΔje1)2 _w^2 _j=0^h-1(e_1 A_ ^je_1)^2 =Jy(λ⁡(θ−),θ+)−σw2∑j=h∞(e1′AΔje1)2 =J_y(λ(θ^-);θ^+)- _w^2 _j=h^∞(e_1 A_ ^je_1)^2 ≥σw2+Δ−σw2∑j=h∞‖AΔj‖2 ≥ _w^2+ - _w^2 _j=h^∞ A_ ^j ^2 ≥σw2+Δ−σw2CΔ2ρΔ2h1−ρΔ2 ≥ _w^2+ - _w^2C_ ^2 _ ^2h1- _ ^2 ≥σw2+7Δ8. ≥ _w^2+ 7 8. Combining this bound with the nonnegative conditional-state term in (71) proves ⁡[(ysaux)2∣ℱs−h]≥σw2+7Δ8. [(y_s aux)^2 _s-h]≥ _w^2+ 7 8. (72) Lemma 17 (One-change detection). Fix a potential restart r and a change time τ with r+H≤τr+H≤τ and τ+D≤Tτ+D≤ T. Let r,τ∈ℱτA_r,τ _τ be the event that the cycle at r is reached, θ−θ^- is active throughout [r,τ)[r,τ), restG_r est holds, and the cycle remains in exploitation after observing yτy_τ. Suppose θ+θ^+ is active throughout [τ,τ+D)[τ,τ+D). Let τ^r τ_r be this cycle’s first alarm output time strictly after τ, with value +∞+∞ if none occurs. Then, almost surely on r,τA_r,τ, ℙ⁡(τ^r>τ+D∣ℱτ)≤δd4T2. ( τ_r>τ+D _τ)≤ _d4T^2. (73) Proof. Condition on an arbitrary ℱτF_τ history in r,τA_r,τ. In the continuation in which alarms are suppressed, the restart-relative sampling grid, the auxiliary initial state ψτ _τ, and the old reference are now fixed, while all future disturbances remain fresh. Within fewer than 2h2h steps, the grid has an output time s1s_1 with s1−h≥τs_1-h≥τ. The next m−1m-1 grid times are h steps apart, and the last satisfies sm−τ<2h+(m−1)h=(m+1)h=D. s_m-τ<2h+(m-1)h=(m+1)h=D. Thus the complete block exists within the finite horizon. If any earlier block alarms, the claim is already true. Otherwise the actual and alarm-suppressed paths agree through this complete post-change block. The conditional version of Lemma 14 is valid because the future innovations are fresh after ℱτF_τ and ℱτ⊆ℱs1−hF_τ _s_1-h by construction. It, together with (72) and a=Δ/8a= /8, gives ℙ⁡(1m∑k=1m(yskaux)2<σw2+3Δ4) \! ( 1m _k=1^m(y_s_k aux)^2< _w^2+ 3 4 ) ≤exp⁡(−mΔ2128Bo4)≤δd4T2. ≤ \! (- m ^2128B_o^4 )≤ _d4T^2. Outside this deviation, Lemma 16 applies because no second change occurs before the tested block and gives an actual average at least σw2+5Δ/8 _w^2+5 /8, which crosses the detector threshold. This proves (73). Equivalently, for every A∈ℱτA _τ with A⊆r,τA _r,τ, ℙ(A∩τ^r>τ+D)≤δd4T2ℙ(A), (A∩\ τ_r>τ+D\)≤ _d4T^2P(A), which is the eventwise form used below. ∎ C.4 Alarm Correspondence Theorem 18 (Alarm correspondence and delay). Suppose Assumptions 7–12 hold. Let σdet _ det be the first output time at which a false alarm occurs or the first deadline at which a true change remains unmatched, with inf∅=+∞ =+∞. For each potential r, let ℰrreachE_r^reach be the event that r is reached, r<σdetr< _ det, and [r,r+H)[r,r+H) is a full, unchanged exploration block. Define ℰref:=⋂r=0T(ℰrreach)c∪rest. _ ref:= _r=0^T\(E_r^reach)^c _r est\. (74) Let ℰdetE_ det be the event that PIECE-CD has no false alarms and raises exactly one alarm τ^(c) τ^(c) for each true change, with τ(c)<τ^(c)≤τ(c)+D,c=1,…,C. τ^(c)< τ^(c)≤τ^(c)+D, c=1,…,C. (75) Then ℙ⁡(ℰref∩ℰdetc)≤δd. (E_ ref _ det^c)≤ _d. (76) Proof. There are at most T potential restart locations and at most T potential test endpoints after each location. Fix such a pair. Intersect its crossing event with the events that the restart is reached, its reference event holds, no earlier detector failure has occurred, and every control generating an output in the block uses the same parameter as the reference exploration; that is, the block is null for this restart. Conditional on the history at the end of exploration, apply Lemma 15 to the fixed predictable block in the continuation with alarms suppressed. If the actual test is reached, the continuation and actual trajectory agree through that test. Thus the probability of this joint gated event, rather than a probability conditional on survival to the test, is at most δd/(2T2) _d/(2T^2). A union bound over the restart–endpoint pairs gives a total false-alarm contribution at most δd/2 _d/2. For a true change τ(c)τ^(c), intersect missed detection with the successful history up to that change. For each potential r, the event that the past detector history is successful, the cycle at r is active at τ(c)τ^(c), and its reference succeeds is an ℱτ(c)F_τ^(c)-measurable subset of r,τ(c)A_r,τ^(c) from Lemma 17. These events are disjoint over r. The dwell conditions give r+H≤τ(c)r+H≤τ^(c), τ(c)+D≤Tτ^(c)+D≤ T, and no second change in [τ(c),τ(c)+D)[τ^(c),τ^(c)+D). Multiplying (73) by each active-cycle indicator, taking expectations, and summing over the disjoint partition gives δd/(4T2) _d/(4T^2) for that change, without an additional restart factor. There are at most C≤T−1C≤ T-1 changes, so the total missed-delay contribution is at most Cδd/(4T2)≤(T−1)δd/(4T2)<δd/4C _d/(4T^2)≤(T-1) _d/(4T^2)< _d/4. A block containing outputs from both sides of a true change is not a null block; if it crosses, it is a valid earlier detection. On the complement of these gated deviations, induction over the change index gives one-to-one alarm correspondence. The deterministic calendar calculation in Appendix H shows that the complete post-change block ends strictly before τ(c)+Dτ^(c)+D; no probability is spent on boundary or integer-rounding conventions. The dwell condition ensures that each alarm occurs before the next change and, when another change remains, leaves an uncontaminated H-step exploration block for the next cycle. The false-alarm contribution is at most δd/2 _d/2 and the missed-delay contribution is less than δd/4 _d/4, so their sum is below δd _d. This proves (76). ∎ Appendix D REGRET ANALYSIS On the detection event of Theorem 18, the horizon splits into exploration, detection-delay, and unchanged exploitation intervals. The first two have bounded per-round cost; the RLS potential argument controls the cumulative cost of the third. D.1 Segmentwise Exploitation Regret Consider an unchanged exploitation interval following a restart at r. Suppress the restart subscript and write b⋆=b1(θ)b_ =b_1(θ), λ=λ⁡(θ)λ=λ(θ), b^=b^r b= b_r, and λ¯=λ¯r λ= λ_r. Define α α :=1−b⋆b^, :=1- b_ b, α¯ α :=Eθ(H,δ0)bmin, := E_θ(H, _0)b_ , v¯H v_H :=ν+κGnH, :=ν+ _Gn_H, ℓ¯ :=Bψ2v¯H, := B_ψ^2 v_H, c0 c_0 :=1−2α¯−2ℓ¯(1+α¯)2, :=1-2 α-2 (1+ α)^2, Bη B_η :=Bw/bmin, :=B_w/b_ , Q¯H Q_H :=Eλ(H,δ0)2(ν+nHBψ2), :=E_λ(H, _0)^2(ν+n_HB_ψ^2), Γ⁡(n) (n) :=dlog⁡(1+nBψ2dv¯H). :=d \! (1+ nB_ψ^2d v_H ). (77) The tuning condition (51) ensures c0>0.7c_0>0.7. Theorem 19 (Logarithmic exploitation regret). Suppose a single parameter θ is active throughout the full exploration block [r,r+H)[r,r+H) and throughout an exploitation interval [r+H,r+H+N)[r+H,r+H+N) of that same cycle, ending no later than its next alarm. Suppose the Gram and estimation events in Propositions 21 and 22 hold for this same θ. Conditional on the history at the end of exploration, with probability at least 1−δ01- _0, simultaneously for every prefix length 0≤n≤N0≤ n≤ N, ∑t=r+Hr+H+n−1(yt+1−wt+1)2 _t=r+H^r+H+n-1(y_t+1-w_t+1)^2 ≤RE(n,δ0), ≤ R_E(n, _0), (78) RE(n,δ0) R_E(n, _0) :=b¯2[2Q¯Hc0+8Bη2c02log⁡1δ0+4Bη2c0Γ(n)]. := b^2 [ 2 Q_Hc_0+ 8B_η^2c_0^2 1 _0+ 4B_η^2c_0 (n) ]. Proof. We give the core argument; Appendix G records the matrix identities and conditioning details. Let dt=λ^t−λd_t= λ_t-λ, at=dt′ψta_t=d_t _t, and et=ut−λ′ψte_t=u_t-λ _t. Lemma 13 gives et2≤at2e_t^2≤ a_t^2. From (36), the pseudo-response in (59) obeys xt+1λ x_t+1^λ =λ′ψt+αet+ηt+1, =λ _t+α e_t+ _t+1, ηt+1 _t+1 :=−wt+1/b^. :=-w_t+1/ b. Here ηt+1 _t+1 is conditionally mean zero and BηB_η-sub-Gaussian. Let Qt=dt′VtdtQ_t=d_t V_td_t and ℓt=ψt′Vt+1−1ψt _t= _t V_t+1^-1 _t. To display the algebra, set ωt:=αet+ηt+1−at _t:=α e_t+ _t+1-a_t. The RLS update and Vt+1=Vt+ψtψt′V_t+1=V_t+ _t _t give dt+1 d_t+1 =dt+Vt+1−1ψtωt, =d_t+V_t+1^-1 _t _t, Qt+1 Q_t+1 =dt′Vt+1dt+2ωtdt′ψt+ωt2ψt′Vt+1−1ψt =d_t V_t+1d_t+2 _td_t _t+ _t^2 _t V_t+1^-1 _t =Qt+at2+2atωt+ℓtωt2. =Q_t+a_t^2+2a_t _t+ _t _t^2. Substituting the definition of ωt _t and collecting at2−2at2=−at2a_t^2-2a_t^2=-a_t^2 gives the exact identity Qt+1−Qt=−at2+2at(αet+ηt+1)+ℓt(αet+ηt+1−at)2. Q_t+1-Q_t=-a_t^2+2a_t(α e_t+ _t+1)+ _t(α e_t+ _t+1-a_t)^2. (79) On the exploration event, |α|≤α¯|α|≤ α and ℓt≤ℓ¯ _t≤ . Using |et|≤|at||e_t|≤|a_t| in (79) yields Qt+1−Qt≤−c0at2+2atηt+1+2ℓtηt+12. Q_t+1-Q_t≤-c_0a_t^2+2a_t _t+1+2 _t _t+1^2. (80) For completeness, conditional BηB_η-sub-Gaussianity and predictability of ata_t imply that, for every fixed ξ>0ξ>0, Mn:=exp⁡ξ∑t=r+Hr+H+n−1atηt+1−ξ2Bη22∑t=r+Hr+H+n−1at2 M_n:= \! \ξ _t=r+H^r+H+n-1a_t _t+1- ξ^2B_η^22 _t=r+H^r+H+n-1a_t^2 \ is a nonnegative supermartingale starting at one. Ville’s inequality (Ville,, 1939; Howard et al.,, 2020) therefore gives, with probability at least 1−δ01- _0, simultaneously over every prefix, ∑tatηt+1≤ξBη22∑tat2+1ξlog⁡1δ0. _ta_t _t+1≤ ξ B_η^22 _ta_t^2+ 1ξ 1 _0. Taking the deterministic value ξ=c0/(2Bη2)ξ=c_0/(2B_η^2) yields ∑tatηt+1≤c04∑tat2+2Bη2c0log⁡1δ0. _ta_t _t+1≤ c_04 _ta_t^2+ 2B_η^2c_0 1 _0. (81) Appendix G gives the same argument directly from the one-step conditional moment-generating-function inequality. Moreover, the matrix determinant lemma gives ∑tℓt≤log⁡detVr+H+ndetVr+H≤Γ⁡(n). _t _t≤ V_r+H+n V_r+H≤ (n). (82) Summing (80), using Qt≥0Q_t≥ 0, ηt+12≤Bη2 _t+1^2≤ B_η^2, and (81)– (82), gives ∑tat2≤2Qr+Hc0+8Bη2c02log⁡1δ0+4Bη2c0Γ(n). _ta_t^2≤ 2Q_r+Hc_0+ 8B_η^2c_0^2 1 _0+ 4B_η^2c_0 (n). (83) Finally, Qr+H≤Q¯HQ_r+H≤ Q_H and, by (36), (yt+1−wt+1)2=b⋆2et2≤b¯2at2(y_t+1-w_t+1)^2=b_ ^2e_t^2≤ b^2a_t^2. This proves (78). ∎ D.2 Delay and Exploration Costs The deterministic state bound gives the per-step delay cost KD:=(BY+Bw)2. K_D:=(B_Y+B_w)^2. (84) During exploration, |ut|≤Be|u_t|≤ B_e and ‖ψt‖≤Bψ _t ≤ B_ψ, so (36) gives the per-step bound KX:=b¯2(Be+ΛBψ)2. K_X:= b^2(B_e+ B_ψ)^2. (85) Thus a delay interval of length at most D costs at most KDDK_DD, and an exploration block costs at most KXHK_XH. D.3 Total Regret Theorem 20 (Finite-time regret of PIECE-CD). Let Assumptions 7–12 hold. Let H be the smallest integer greater than r0r_0 that satisfies (93) and (51)–(52); choose h,m,Dh,m,D by (53)–(54), and run Algorithm B.3. Then, with probability at least 1−δ1-δ, there are no false alarms, every change has exactly one alarm satisfying (75), and ℛT≤CKDD+(C+1)KXH+(C+1)RE(T,δ0). _T≤ CK_DD+(C+1)K_XH+(C+1)R_E(T, _0). (86) Consequently, for fixed orders and fixed model, noise, initialization, exploration, ridge, stability, clipping, and gap bounds, ℛT=O⁡((C+1)log⁡T+1δ). _T=O\! ((C+1) T+1δ ). (87) Proof. If T≤HT≤ H, Assumption 12 forces C=0C=0. The algorithm then performs only truncated exploration, and the deterministic exploration bound gives ℛT≤KXT≤KXHR_T≤ K_XT≤ K_XH, which is bounded by the right-hand side of (86). Hence assume T>HT>H below. At every potential full, unchanged restart block, gate the estimation and RLS failure events by the event that this restart is reached with a successful history, and then condition on the past. Propositions 21 and 22 cost at most 2δ02 _0, and the time-uniform RLS event in Theorem 19 costs another δ0 _0. The tower property and a union bound over at most T+1T+1 locations give 3(T+1)δ0=3δ/323(T+1) _0=3δ/32. Gating the false-alarm and delay events in the same chronological way, Theorem 18 costs less than δd=δ/2 _d=δ/2. Their intersection therefore has probability greater than 1−δ1-δ. Appendix I gives the full induction; in particular, it never conditions an early detector event on future estimator success. On this intersection, each of the C true changes has a pre-alarm interval of length at most D, giving CKDDCK_DD. There is one initial exploration block and at most one block after each alarm, giving at most (C+1)KXH(C+1)K_XH. Removing these intervals leaves at most C+1C+1 unchanged exploitation prefixes. Apply Theorem 19 to each and upper-bound its length by T; this gives the last term in (86). Appendix J constructs a feasible H=O⁡(log⁡((T+1)/δ))H=O( ((T+1)/δ)); the smallest feasible value is therefore no larger. Equations (53)–(54) give fixed h and D=O⁡(log⁡((T+1)/δ))D=O( ((T+1)/δ)). Finally, Q¯H Q_H, Γ⁡(T) (T), and log⁡(1/δ0) (1/ _0) are all O⁡(log⁡((T+1)/δ))O( ((T+1)/δ)). Substitution proves (87). When C=0C=0, the delay term is absent, leaving the stationary logarithmic bound rather than the meaningless expression O⁡(Clog⁡T)O(C T). ∎ Appendix E DETERMINISTIC BOUNDS AND RESTART CONVENTIONS Bounded applied inputs and Assumptions 7–9 yield the pathwise bounds (40). E.1 Output and Regressor Bounds Let Yt=(yt,…,yt−p+1)′Y_t=(y_t,…,y_t-p+1) . Equation (32) has the state form Yt+1=Ay(θt)Yt+e1ζt+1,ζt+1:=wt+1+∑j=1qbj(θt)ut−j+1. Y_t+1=A_y( _t)Y_t+e_1 _t+1, _t+1:=w_t+1+ _j=1^qb_j( _t)u_t-j+1. (88) Since |ut|≤Bu|u_t|≤ B_u by construction, |ζt+1|≤Bw+BbBu. | _t+1|≤ B_w+B_bB_u. Unrolling (88) and applying (39) gives ‖Yt‖ Y_t ≤Cyρyt‖Y0‖+Cy(Bw+BbBu)∑j=0t−1ρyj ≤ C_y _y^t Y_0 +C_y(B_w+B_bB_u) _j=0^t-1 _y^j ≤Cy‖Y0‖+Cy1−ρy(Bw+BbBu)=BY. ≤ C_y Y_0 + C_y1- _y(B_w+B_bB_u)=B_Y. Every output coordinate is therefore bounded by BYB_Y. The definition (33) and clipping give ‖ψt‖2≤pBY2+(q−1)Bu2=Bψ2, _t ^2≤ pB_Y^2+(q-1)B_u^2=B_ψ^2, and (34) gives ‖ϕt‖≤Bϕ _t ≤ B_φ. E.2 Projection onto the Clipping Interval Let clip[−B,B]⁡(x)=(−B)∨x∧Bclip_[-B,B](x)=(-B) x B. As the Euclidean projection onto a closed convex set, it is nonexpansive: |clip[−B,B]⁡(x)−clip[−B,B]⁡(z)|≤|x−z|. |clip_[-B,B](x)-clip_[-B,B](z)|≤|x-z|. If z∈[−B,B]z∈[-B,B], this becomes |clip[−B,B]⁡(x)−z|≤|x−z|. |clip_[-B,B](x)-z|≤|x-z|. (89) Assumption 10 permits (89) with z=λ(θ)′ψtz=λ(θ) _t for θ∈Θθ∈ . For an arbitrary target z, the bound includes its distance from the clipping interval: |clip[−Bu,Bu]⁡(x)−z|≤|x−z|+(|z|−Bu)+. |clip_[-B_u,B_u]\! (x )-z|≤|x-z|+(|z|-B_u)_+. E.3 Auxiliary-Process Bounds For the fixed mismatch matrix AΔA_ in (68), (44) gives, for t≥τt≥τ, ‖ψtaux‖ _t aux ≤CΔρΔt−τ‖ψτ‖+CΔBw∑j=0t−τ−1ρΔj ≤ C_ _ ^t-τ _τ +C_ B_w _j=0^t-τ-1 _ ^j ≤CΔBψ+CΔBw1−ρΔ=Baux. ≤ C_ B_ψ+ C_ B_w1- _ =B_ aux. Thus both actual and auxiliary outputs are bounded in absolute value by BoB_o. E.4 Conditioning at a Random Restart An alarm time r is an ℱt\F_t\-stopping time. Conditional on ℱrF_r, the state ψr _r is fixed with ‖ψr‖≤Bψ _r ≤ B_ψ, and future disturbances retain the independence, moments, and bound in Assumption 9. The input uru_r is already ℱrF_r-measurable; subsequent exploratory inputs are fresh and independent of the disturbances. Consider a conditional concentration bound that holds uniformly over these restart histories, with failure probability at most εfail _ fail. For any eligibility event r∈ℱrC_r _r, the tower property gives ℙ⁡(r∩failure at r) (C_r∩\failure at r\) =⁡[rℙ(failure at r∣ℱr)] =E\! [1_C_rP(failure at r _r) ] ≤εfailℙ(r)≤εfail. ≤ _ failP(C_r)≤ _ fail. A union bound over at most T+1T+1 possible restart locations then controls these failures across the horizon. This is the basis for the allocation (48). Appendix F EXPLORATION, EXCITATION, AND THE RESTARTED ESTIMATE The covariance analysis of stationary PIECE in Singh et al., (2024) concerns sparse, recurring exploration episodes. Here we establish linear Gram growth and estimation bounds for a contiguous exploration block after a random restart. F.1 Conditional Excitation Fix a complete exploration block [r,r+H)[r,r+H) during which the parameter remains equal to θ. Put s:=p+qs:=p+q, L:=r0=max⁡p,qL:=r_0= \p,q\, and σ¯2:=min⁡σw2,σe2 σ^2:= \ _w^2, _e^2\. At any exploration time t≥r+Lt≥ r+L, collect the most recent innovations in Zt:=(wt−p+1,…,wt,ut−q+1,…,ut)′.Z_t:=(w_t-p+1,…,w_t,u_t-q+1,…,u_t) . Because the parameter is fixed within the exploration block, repeated substitution in the ARX recursion gives ϕt=M⁡(θ)Zt+ξt. _t=M(θ)Z_t+ _t. (90) To make the remainder explicit, let Z¯t Z_t collect the members of (wt−L+1,…,wt,ut−L+1,…,ut)(w_t-L+1,…,w_t,u_t-L+1,…,u_t) that do not already occur in ZtZ_t. Repeated substitution gives ξt=ct+M¯(θ)Z¯t _t=c_t+ M(θ) Z_t, where ctc_t is ℱt−LF_t-L-measurable. Conditional on ℱt−LF_t-L, the vector ZtZ_t is centered, is independent of Z¯t Z_t, and has covariance Cov⁡(Zt∣ℱt−L)=diag⁡(σw2Ip,σe2Iq).Cov(Z_t _t-L)=diag( _w^2I_p, _e^2I_q). Thus ZtZ_t and ξt _t are conditionally independent. The remainder depends on the ℱt−LF_t-L-measurable history and the omitted innovations. To see the triangular structure explicitly, order the output coordinates and their disturbances chronologically as (yt−p+1,…,yt)(y_t-p+1,…,y_t) and (wt−p+1,…,wt)(w_t-p+1,…,w_t). The equation for yjy_j contains wjw_j with coefficient one and only disturbances dated at or before j. Thus the output–disturbance block is triangular with unit diagonal. Ordering the current exploration inputs as (ut−q+1,…,ut)(u_t-q+1,…,u_t) makes the input-coordinate block the identity. All remaining post-ℱt−LF_t-L innovations are precisely those collected in Z¯t Z_t; older terms belong to ctc_t. Hence, up to these fixed row and column permutations, M⁡(θ)M(θ) has the block-triangular form M⁡(θ)=[Tw(θ)Tu(θ)0Iq], M(θ)= bmatrixT_w(θ)&T_u(θ)\\ 0&I_q bmatrix, where Tw(θ)T_w(θ) is triangular with unit diagonal: each yjy_j contains its contemporaneous disturbance wjw_j with coefficient one. Hence M⁡(θ)M(θ) is nonsingular. Continuity and compactness give χ:=infθ∈Θσmin(M⁡(θ))>0,κinn:=σ¯2χ2>0. χ:= _θ∈ _ (M(θ))>0, _ inn:= σ^2χ^2>0. For completeness, let ΣZ:=Cov⁡(Zt∣ℱt−L) _Z:=Cov(Z_t _t-L). Conditional independence removes both cross-covariance terms, and hence Cov⁡(ϕt∣ℱt−L) ( _t _t-L) =M⁡(θ)ΣZM(θ)′+Cov⁡(ξt∣ℱt−L) =M(θ) _ZM(θ) +Cov( _t _t-L) ⪰σ¯2M(θ)M(θ)′⪰σ¯2σmin(M⁡(θ))2Is. σ^2M(θ)M(θ) σ^2 _ (M(θ))^2I_s. Also, ⁡[ϕtϕt′∣ℱt−L]E[ _t _t _t-L] equals this covariance plus the positive semidefinite outer product of the conditional mean. Therefore ⁡[ϕtϕt′∣ℱt−L]⪰Cov⁡(ϕt∣ℱt−L)⪰κinnIs. [ _t _t _t-L] ( _t _t-L) _ innI_s. (91) The bound is uniform over the history in ℱt−LF_t-L. F.2 Exploration Gram Bound Fix a restart r and the trimmed set ℐr=r+r0,…,r+H−1I_r=\r+r_0,…,r+H-1\. Let Φr _r :=[ϕr+r0′ϕr+H−1′], := bmatrix _r+r_0 \\ \\ _r+H-1 bmatrix, Gr G_r :=Φr′Φr=∑t∈ℐrϕtϕt′. := _r _r= _t _r _t _t . Set NH:=1+⌊nH−1L⌋,κG:=κinn2L. N_H:=1+ n_H-1L , _G:= _ inn2L. (92) Consider only the L-spaced rows tk=r+L+(k−1)Lt_k=r+L+(k-1)L, k=1,…,NHk=1,…,N_H. They are contained in ℐrI_r, and NH≥nH/LN_H≥ n_H/L. The conditioning argument in Appendix E applies at a stopping-time restart r. Although uru_r is already ℱrF_r-measurable, the trimming starts at t=r+Lt=r+L, so every innovation appearing in ZtZ_t has index at least r+1r+1. Consequently, (90)–(96) apply without treating r as deterministic. Proposition 21 (Exploration Gram bound). Let r be a stopping time with r+H≤Tr+H≤ T, and suppose a single θ∈Θθ∈ is active at every control time t=r,…,r+H−1t=r,…,r+H-1. If NH≥10Bϕ4κinn2log⁡sδ0, N_H≥ 10B_φ^4 _ inn^2 s _0, (93) then, conditional on ℱrF_r, ℙ(λmin(Gr)≥κGnH,tr(Gr)≤nHBϕ2|ℱr)≥1−δ0. \! ( _ (G_r)≥ _Gn_H, (G_r)≤ n_HB_φ^2\ |\ F_r )≥ 1- _0. (94) The same event implies λmin(∑t∈ℐrψtψt′)≥κGnH. _ \! ( _t _r _t _t )≥ _Gn_H. (95) Proof. Condition on ℱrF_r. For Xk:=ϕtkϕtk′X_k:= _t_k _t_k , use the stopped filtration ℋ0=ℱrH_0=F_r and ℋk=ℱtk=ℱr+kLH_k=F_t_k=F_r+kL. Here t1−L=rt_1-L=r, and tk−L=tk−1t_k-L=t_k-1 for k≥2k≥ 2, so (91) gives Ak:=⁡[Xk∣ℋk−1]⪰κinnIs.A_k:=E[X_k _k-1] _ innI_s. Also 0⪯Xk⪯Bϕ2Is0 X_k B_φ^2I_s. Thus Dk:=Xk−AkD_k:=X_k-A_k is a self-adjoint matrix-martingale difference with ‖Dk‖≤Bϕ2 D_k ≤ B_φ^2 and predictable quadratic variation bounded by NHBϕ4IsN_HB_φ^4I_s. Moreover, κinn≤Bϕ2 _ inn≤ B_φ^2 because Ak⪯Bϕ2IsA_k B_φ^2I_s. The lower-tail form of the matrix Freedman inequality (Tropp,, 2011), applied to −∑kDk- _kD_k, gives ℙ⁡(λmin(∑k=1NHXk)≤κinnNH2|ℱr) \! ( _ \! ( _k=1^N_HX_k )≤ _ innN_H2\ |\ F_r ) ≤sexp⁡−κinn2NH8Bϕ4+(4/3)Bϕ2κinn ≤ s \! \- _ inn^2N_H8B_φ^4+(4/3)B_φ^2 _ inn \ ≤sexp⁡(−κinn2NH10Bϕ4). ≤ s \! (- _ inn^2N_H10B_φ^4 ). (96) Condition (93) makes the right-hand side at most δ0 _0. Since Gr⪰∑kXkG_r _kX_k and NH≥nH/LN_H≥ n_H/L, the claimed eigenvalue bound follows. The trace bound is deterministic because ‖ϕt‖≤Bϕ _t ≤ B_φ. Finally, ∑t∈ℐrψtψt′ _t _r _t _t is the principal block of GrG_r obtained by deleting the current-input row and column. Eigenvalue interlacing, or direct restriction of the Rayleigh quotient, proves (95). ∎ F.3 Projected Ridge Estimation Proposition 22 (Restarted parameter and gain estimate). Let r be a stopping time with r+H≤Tr+H≤ T, and suppose a single θ∈Θθ∈ is active at every control time t=r,…,r+H−1t=r,…,r+H-1. Given ℱrF_r, event (100) has probability at least 1−δ01- _0. On its intersection with the event in Proposition 21, the estimator defined in (55)–(56) satisfies ‖θ^r−θ‖ θ_r-θ ≤Eθ(H,δ0), ≤ E_θ(H, _0), (97) ‖λ¯r−λ⁡(θ)‖ λ_r-λ(θ) ≤Eλ(H,δ0)=gH/4. ≤ E_λ(H, _0)=g_H/4. Moreover, the RLS initialization satisfies v¯HId⪯Vr+H⪯(ν+nHBψ2)Id v_HI_d V_r+H (ν+n_HB_ψ^2)I_d (98) in the sense of its smallest- and largest-eigenvalue bounds. If (93) holds, the Gram event and the two estimates above therefore hold jointly with conditional probability at least 1−2δ01-2 _0. Proof. Let V=VrθV=V_r^θ and Sr=∑t∈ℐrϕtwt+1S_r= _t _r _tw_t+1. Since yt+1=ϕt′θ+wt+1y_t+1= _t θ+w_t+1 during the uncontaminated block, write Gr=∑t∈ℐrϕtϕt′G_r= _t _r _t _t and calculate ∑t∈ℐrϕtyt+1 _t _r _ty_t+1 =∑t∈ℐrϕt(ϕt′θ+wt+1) = _t _r _t( _t θ+w_t+1) =Grθ+Sr=(V−νIs)θ+Sr. =G_rθ+S_r=(V-ν I_s)θ+S_r. Multiplication by V−1V^-1 gives θ~r θ_r =θ+V−1(Sr−νθ), =θ+V^-1(S_r-νθ), and therefore θ~r−θ=V−1(Sr−νθ). θ_r-θ=V^-1(S_r-νθ). (99) Assumption 9 and Hoeffding’s lemma make wt+1w_t+1 conditionally BwB_w-sub-Gaussian. The fixed-ridge self-normalized inequality (Abbasi-Yadkori et al.,, 2011, Theorem 1) gives, with conditional probability at least 1−δ01- _0, ‖Sr‖V−1≤Bwlog⁡detVνsδ02. S_r _V^-1≤ B_w Vν^s _0^2. (100) Here again s=p+qs=p+q, and νs=det(νIs)ν^s= (ν I_s) is the determinant of the initial ridge matrix. Also ‖νθ‖V−1≤νSΘ νθ _V^-1≤ νS_ . By the arithmetic-geometric mean inequality and the trace bound, the determinant step can be written explicitly. Let γ1,…,γs≥0 _1,…, _s≥ 0 be the eigenvalues of GrG_r. Since V=νIs+GrV=ν I_s+G_r, detVνs Vν^s =∏i=1s(1+γiν) = _i=1^s (1+ _iν ) ≤(1s∑i=1s(1+γiν))s=(1+tr⁡(Gr)sν)s ≤ ( 1s _i=1^s (1+ _iν ) )^s= (1+ tr(G_r)sν )^s ≤(1+nHBϕ2sν)s. ≤ (1+ n_HB_φ^2sν )^s. The last inequality uses tr⁡(Gr)=∑t∈ℐr‖ϕt‖2≤nHBϕ2tr(G_r)= _t _r _t ^2≤ n_HB_φ^2. Taking logarithms and using nH≤Hn_H≤ H yields log⁡detVνs≤slog⁡(1+nHBϕ2sν)≤slog⁡(1+HBϕ2sν). Vν^s≤ s \! (1+ n_HB_φ^2sν )≤ s \! (1+ HB_φ^2sν ). (101) Equations (94), (99)–(101) imply the unprojected Euclidean error bound equal to one half of (46). A nearest-point projection onto a compact set containing θ increases Euclidean error by at most a factor two, proving (97). If Θ is closed and convex, projection is nonexpansive and the factor two may be removed. The gain bound follows from (38). The lower eigenvalue in (98) follows from (95); the upper eigenvalue follows from ∑ψtψt′⪯(∑‖ψt‖2)IdΣ _t _t (Σ _t ^2)I_d. ∎ The linear Gram bound (94) is the excitation estimate used in Appendix J to obtain H=O⁡(log⁡((T+1)/δ))H=O( ((T+1)/δ)). Appendix G THE RLS POTENTIAL ARGUMENT We establish the potential estimates used in Theorem 19. Consider its unchanged exploration block and exploitation interval, and condition on an ℱr+HF_r+H history on which the Gram and estimation events hold. We use the constants in (77), set t0=r+Ht_0=r+H, and let t1≥t0t_1≥ t_0 denote the final control time of an exploitation prefix. G.1 Control Error and Prediction Error Let λ be the true gain on the unchanged segment and let λ¯ λ be the exploration reference. For a gate of radius g>0g>0, the recursive proposal is accepted when |(λ^t−λ¯)′ψt|≤g⁡‖ψt‖|( λ_t- λ) _t|≤ g _t and the reference proposal is used otherwise. Suppose ‖λ¯−λ‖≤ϵ,g>ϵ. λ-λ ≤ε, g>ε. For at=(λ^t−λ)′ψta_t=( λ_t-λ) _t, the unclipped gated action error e~t=zt−λ′ψt e_t=z_t-λ _t obeys e~t2≤Kgat2,Kg:=max⁡1,(ϵg−ϵ)2. e_t^2≤ K_ga_t^2, K_g:= \1, ( εg-ε )^2 \. (102) If ψt=0 _t=0, then at=e~t=0a_t= e_t=0 and the claim is immediate. If ψt≠0 _t≠ 0, then on the accepted branch e~t=at e_t=a_t. On the fallback branch, |at| |a_t| ≥|(λ^t−λ¯)′ψt|−|(λ¯−λ)′ψt| ≥|( λ_t- λ) _t|-|( λ-λ) _t| >(g−ϵ)‖ψt‖, >(g-ε) _t , while |e~t|≤ϵ⁡‖ψt‖| e_t|≤ε _t . Since g−ϵ>0g-ε>0, division gives |e~t|≤ϵg−ϵ|at|. | e_t|≤ εg-ε|a_t|. Squaring this inequality and taking the larger constant over the two branches proves (102). If the ideal action lies in the clipping interval, nonexpansiveness preserves (102). In the algorithm, g=gHg=g_H and ϵ=Eλ=gH/4ε=E_λ=g_H/4. Therefore ϵ/(g−ϵ)=1/3ε/(g-ε)=1/3 and Kg=1K_g=1. G.2 Exact Regression and Potential Identity On the segment, yt+1=b⋆(ut−λ′ψt)+wt+1. y_t+1=b_ (u_t-λ _t)+w_t+1. (103) Let γ=b⋆/b^γ=b_ / b, α=1−γα=1-γ, and et=ut−λ′ψte_t=u_t-λ _t. The pseudo-response is exactly xt+1λ x_t+1^λ =ut−yt+1/b =u_t-y_t+1/ b =λ′ψt+αet+ηt+1, =λ _t+α e_t+ _t+1, ηt+1 _t+1 =−wt+1/b^. =-w_t+1/ b. Because θ^r∈Θ θ_r∈ by projection and hence b^≥bmin b≥ b_ by (37), |ηt+1|≤Bη=Bw/bmin| _t+1|≤ B_η=B_w/b_ and Hoeffding’s lemma gives ⁡[exp⁡(ξηt+1)∣ℱt]≤exp⁡(ξ2Bη2/2),ξ∈ℝ. [ (ξ _t+1) _t]≤ (ξ^2B_η^2/2), ξ . (104) Set dt=λ^t−λd_t= λ_t-λ, at=dt′ψta_t=d_t _t, Qt=dt′VtdtQ_t=d_t V_td_t, and ℓt:=ψt′Vt+1−1ψt. _t:= _t V_t+1^-1 _t. The update (60) becomes dt+1=dt+Vt+1−1ψt(αet+ηt+1−at). d_t+1=d_t+V_t+1^-1 _t(α e_t+ _t+1-a_t). (105) Using Vt+1=Vt+ψtψt′V_t+1=V_t+ _t _t in (105) and expanding gives Qt+1−Qt=−at2+2at(αet+ηt+1)+ℓt(αet+ηt+1−at)2. Q_t+1-Q_t=-a_t^2+2a_t(α e_t+ _t+1)+ _t(α e_t+ _t+1-a_t)^2. (106) On the exploration event, |α|=|b^−b⋆|b^≤Eθbmin=α¯. |α|= | b-b_ | b≤ E_θb_ = α. Also Vt+1⪰Vr+H⪰v¯HIV_t+1 V_r+H v_HI, so 0≤ℓt≤‖ψt‖2v¯H≤ℓ¯. 0≤ _t≤ _t ^2 v_H≤ . By et2≤at2e_t^2≤ a_t^2 and (x+y)2≤2x2+2y2(x+y)^2≤ 2x^2+2y^2, 2αatet 2α a_te_t ≤2α¯at2, ≤ 2 αa_t^2, ℓt(αet+ηt+1−at)2 _t(α e_t+ _t+1-a_t)^2 ≤2ℓt(1+α¯)2at2+2ℓtηt+12. ≤ 2 _t(1+ α)^2a_t^2+2 _t _t+1^2. Substitution into (106) proves (80). G.3 Time-Uniform Noise Bound For any fixed ξ>0ξ>0, (104) and predictability of ata_t imply that the prefix-indexed process exp⁡ξ∑t=t0t1atηt+1−ξ2Bη22∑t=t0t1at2 \ξ _t=t_0^t_1a_t _t+1- ξ^2B_η^22 _t=t_0^t_1a_t^2 \ is a nonnegative supermartingale starting at one, conditionally on ℱt0F_t_0. Its one-step multiplicative increment satisfies ⁡[exp⁡ξatηt+1−ξ2Bη2at22|ℱt]≤1, \! [ \! \ξ a_t _t+1- ξ^2B_η^2a_t^22 \ |F_t ]≤ 1, because ata_t is ℱtF_t-measurable and (104) applies with argument ξatξ a_t. Ville’s inequality (Ville,, 1939; Howard et al.,, 2020) says that, with probability at least 1−δ01- _0, this process never exceeds 1/δ01/ _0. Taking logarithms on that event and dividing by the fixed ξ>0ξ>0 gives, simultaneously for every exploitation prefix, ∑tatηt+1≤ξBη22∑tat2+1ξlog⁡1δ0. _ta_t _t+1≤ ξ B_η^22 _ta_t^2+ 1ξ 1 _0. Choosing the deterministic value ξ=c0/(2Bη2)ξ=c_0/(2B_η^2) gives ∑tatηt+1≤c04∑tat2+2Bη2c0log⁡(1/δ0). _ta_t _t+1≤ c_04 _ta_t^2+ 2B_η^2c_0 (1/ _0). (107) G.4 Elliptical Potential For xt=ψt′Vt−1ψtx_t= _t V_t^-1 _t, the Sherman–Morrison identity Vt+1−1=Vt−1−Vt−1ψtψt′Vt−1/(1+xt)V_t+1^-1=V_t^-1-V_t^-1 _t _t V_t^-1/(1+x_t) and the matrix determinant lemma give ℓt _t =xt1+xt, = x_t1+x_t, detVt+1detVt V_t+1 V_t =1+xt. =1+x_t. Since x/(1+x)≤log⁡(1+x)x/(1+x)≤ (1+x) for x≥0x≥ 0, ∑t=t0t1ℓt≤log⁡detVt1+1detVt0. _t=t_0^t_1 _t≤ V_t_1+1 V_t_0. The determinants are positive since Vt0⪰v¯HI≻0V_t_0 v_HI 0. Set Sn:=∑t=t0t1ψtψt′,An:=Vt0−1/2SnVt0−1/2,n:=t1−t0+1. S_n:= _t=t_0^t_1 _t _t , A_n:=V_t_0^-1/2S_nV_t_0^-1/2, n:=t_1-t_0+1. Then An⪰0A_n 0 and log⁡detVt1+1detVt0 V_t_1+1 V_t_0 =logdet(I+An) = (I+A_n) ≤dlog⁡(1+tr⁡(An)d) ≤ d \! (1+ tr(A_n)d ) ≤dlog⁡(1+nBψ2dv¯H)=Γ⁡(n). ≤ d \! (1+ nB_ψ^2d v_H )= (n). (108) The first inequality follows by applying Jensen’s inequality to log⁡(1+x) (1+x) over the nonnegative eigenvalues of AnA_n. For the second, tr⁡(An) (A_n) =∑t=t0t1ψt′Vt0−1ψt≤1v¯H∑t=t0t1‖ψt‖2≤nBψ2v¯H. = _t=t_0^t_1 _t V_t_0^-1 _t≤ 1 v_H _t=t_0^t_1 _t ^2≤ nB_ψ^2 v_H. For the standard elliptical-potential argument, see Abbasi-Yadkori et al., (2011, Lemma 11). G.5 Completion of the Segment Bound Sum (80). Since Qt1+1≥0Q_t_1+1≥ 0, ηt+12≤Bη2 _t+1^2≤ B_η^2, and (107)–(108) hold, c0∑tat2 c_0 _ta_t^2 ≤Qt0+2∑tatηt+1+2Bη2Γ(n) ≤ Q_t_0+2 _ta_t _t+1+2B_η^2 (n) ≤Qt0+c02∑tat2+4Bη2c0log⁡(1/δ0)+2Bη2Γ(n). ≤ Q_t_0+ c_02 _ta_t^2+ 4B_η^2c_0 (1/ _0)+2B_η^2 (n). Rearranging yields (83). At initialization, Qt0 Q_t_0 =(λ¯−λ)′Vt0(λ¯−λ) =( λ-λ) V_t_0( λ-λ) ≤Eλ2λmax(Vt0)≤Eλ2(ν+nHBψ2)=Q¯H. ≤ E_λ^2 _ (V_t_0)≤ E_λ^2(ν+n_HB_ψ^2)= Q_H. Finally, (103) and the gate charging inequality give ∑t(yt+1−wt+1)2=b⋆2∑tet2≤b¯2∑tat2, _t(y_t+1-w_t+1)^2=b_ ^2 _te_t^2≤ b^2 _ta_t^2, which proves Theorem 19. Appendix H DETAILED DETECTOR PROOFS This appendix supplies the conditional power estimates, concentration arguments, and calendar bounds used in Appendix C. The assumptions and tuning of Appendices A and B remain in force. H.1 Finite-Horizon Power of the Auxiliary Process Fix a change at control time τ and write A=AΔA=A_ . For s−h≥τs-h≥τ, iterating (68) for h steps gives ψsaux=Ahψs−haux+∑j=0h−1Aje1ws−j. _s aux=A^h _s-h aux+ _j=0^h-1A^je_1w_s-j. Taking the first coordinate and squaring, all cross terms involving distinct disturbances have conditional expectation zero. Thus ⁡[(ysaux)2∣ℱs−h]=(e1′Ahψs−haux)2+σw2∑j=0h−1(e1′Aje1)2. [(y_s aux)^2 _s-h]=(e_1 A^h _s-h aux)^2+ _w^2 _j=0^h-1(e_1 A^je_1)^2. (109) The stationary power is Jy(λ−,θ+)=σw2∑j=0∞(e1′Aje1)2. J_y(λ^-;θ^+)= _w^2 _j=0^∞(e_1 A^je_1)^2. Since the first term of (109) is nonnegative, ⁡[(ysaux)2∣ℱs−h] [(y_s aux)^2 _s-h] ≥Jy(λ−,θ+)−σw2∑j=h∞‖Aj‖2 ≥ J_y(λ^-;θ^+)- _w^2 _j=h^∞ A^j ^2 ≥Jy(λ−,θ+)−σw2CΔ2ρΔ2h1−ρΔ2. ≥ J_y(λ^-;θ^+)- _w^2C_ ^2 _ ^2h1- _ ^2. Equations (45) and (53) yield (72) for every initial state at time s−hs-h. The calculation also holds when s is a finite lag-h predictable random time. Indeed, s=t∈ℱt−h\s=t\ _t-h; multiplying the deterministic-time identity by s=t1\s=t\ and summing over t gives (109) with s and the stopped sigma-field ℱs−hF_s-h. H.2 Lag-Predictable Sampling Let h≤s1<⋯<smh≤ s_1<·s<s_m be finite lag-h predictable output times with sk+1−sk≥hs_k+1-s_k≥ h. Define ℋk−1:=ℱsk−h,k=1,…,m,ℋm:=ℱsm. _k-1:=F_s_k-h, k=1,…,m, _m:=F_s_m. Lag predictability makes these stopped sigma-fields well defined. The spacing condition gives ℱsk⊆ℋkF_s_k _k for k<mk<m, and the inclusion also holds for k=mk=m by definition. Hence ysk2−⁡[ysk2∣ℱsk−h]y_s_k^2-E[y_s_k^2 _s_k-h] is ℋkH_k-measurable and has conditional mean zero given ℋk−1H_k-1. This is the martingale structure used in Lemma 14; it need not hold for consecutive outputs centered at lag h, or for samples selected after observing their values. H.3 Null Windows Fix a potential restart r with a full uncontaminated exploration block and a potential test endpoint e. In the alarm-suppressed continuation from r, let Sr,eS_r,e be the corresponding block of m calendar samples. The block is null for r when each sampled output is generated under the reference parameter. If that parameter remains active throughout [r,τ)[r,τ), a block ending at output time τ is null, since yτy_τ is generated at control time τ−1τ-1. Condition on an ℱr+HF_r+H history on which restG_r est holds. The calendar fixes the block before its outputs are observed, and (64) applies to every stored output of a null block. Each ws2−σw2w_s^2- _w^2 is centered and lies in an interval of length Bw2B_w^2. The Hoeffding exponential process (Hoeffding,, 1963; Howard et al.,, 2020) therefore gives, for x>0x>0, ℙ⁡(∑s∈Sr,e(ws2−σw2)≥mx|ℱr+H)≤exp⁡(−2mx2Bw4). \! ( _s∈ S_r,e(w_s^2- _w^2)≥ mx\ |\ F_r+H )≤ \! (- 2mx^2B_w^4 ). (110) For the cross term, vsv_s is predictable and |wsvs|≤Bwεy|w_sv_s|≤ B_w _y. If εy=0 _y=0, the cross term is identically zero. Otherwise, the corresponding Azuma–Hoeffding exponential process (Azuma,, 1967; Hoeffding,, 1963) gives ℙ⁡(∑s∈Sr,ewsvs≥mx|ℱr+H)≤exp⁡(−mx22Bw2εy2). \! ( _s∈ S_r,ew_sv_s≥ mx\ |\ F_r+H )≤ \! (- mx^22B_w^2 _y^2 ). (111) Taking x=Δ/8x= /8 in (110) and x=Δ/16x= /16 in (111) gives (66) and (67). The deterministic term in (65) is at most εy2≤Δ/8 _y^2≤ /8. Outside the two deviation events, the excess empirical power is therefore at most 3Δ/83 /8, below the threshold Δ/2 /2. If the actual test at e is reached, the alarm-suppressed continuation agrees with the implemented trajectory through that test. The conditional bound thus controls the joint event that the reference succeeds, the test is reached, its block is null for that reference, and the threshold is crossed. There are at most T2T^2 potential restart–endpoint pairs; applying the δd/(2T2) _d/(2T^2) one-block bound separately to each pair and taking a union bound gives a horizon-wide false-alarm contribution of at most δd/2 _d/2. Overlapping windows require no independence, and the argument does not condition on survival to a test. H.4 Trajectory Coupling Let δt=ψt−ψtaux _t= _t- _t aux and use the input-channel bound GuG_u from (42). On restG_r est, for control times after the change at τ and before the next alarm or true change, Lemma 13 gives ut=(λ−)′ψt+et,‖gu(θ+)et‖≤Guεu. u_t=(λ^-) _t+e_t, g_u(θ^+)e_t ≤ G_u _u. Consequently, δt+1=Aδt+gu(θ+)et,δτ=0. _t+1=A _t+g_u(θ^+)e_t, _τ=0. Unrolling and using (44), ‖δt‖ _t ≤∑j=0t−τ−1‖Aj‖Guεu≤CΔGuεu1−ρΔ=RΔ(H). ≤ _j=0^t-τ-1 A^j G_u _u≤ C_ G_u _u1- _ =R_ (H). The gate bound uses feasibility of the old-gain action (λ−)′ψt(λ^-) _t at the actual state. The auxiliary action is unclipped and need not be feasible. The comparison holds up to the first alarm or next true change, while the actual plant parameter remains the fixed θ+θ^+ used in A. H.5 Calendar and Delay Consider a change at control time τ under the hypotheses of Lemma 17: the cycle is still in exploitation after observing yτy_τ, r+H≤τr+H≤τ, and τ+D≤Tτ+D≤ T. In its alarm-suppressed continuation, stored output times form an arithmetic grid with gap h. Let s1s_1 be the first grid output with s1−h≥τs_1-h≥τ. The distance from τ+hτ+h to the next grid point is less than h, so s1−τ<2h. s_1-τ<2h. The mmth grid output is sm=s1+(m−1)hs_m=s_1+(m-1)h, hence sm−τ<(m+1)h=D. s_m-τ<(m+1)h=D. Every interval [sk−h,sk)[s_k-h,s_k) lies after the change, so the auxiliary outputs at these times satisfy (72). The post-change parameter remains active throughout the block by the hypotheses of Lemma 17. If any earlier block alarms, the change has already been detected. Otherwise, the actual and alarm-suppressed trajectories agree through the complete post-change test at sms_m. Since times are integer valued, sm≤τ+D−1s_m≤τ+D-1; the test is therefore available within the horizon. For the induction in Theorem 18, the dwell condition places the first change after the initial exploration. If change c<Cc<C is detected by τ(c)+Dτ^(c)+D, the next exploration ends by τ(c)+D+H≤τ(c+1)τ^(c)+D+H≤τ^(c+1). Thus each subsequent change is preceded by a full uncontaminated reference block on the successful detection history. Appendix I GLOBAL EVENT AND REGRET DECOMPOSITION We combine the restart and detector guarantees on a common event and partition the control times to prove Theorem 20. I.1 Global Success Event Assume T>HT>H; the case T≤HT≤ H is handled deterministically in the proof of Theorem 20. Record each failure at its first adapted decision time: at the end of a reached full, unchanged exploration block if its Gram or self-normalized event fails; at the first same-parameter exploitation prefix violating its time-uniform RLS event; at a false detector crossing; or at the deadline of a missed change. Ties at an exploration endpoint are ordered as Gram, self-normalized, and then RLS. Since the true parameter sequence is deterministic in the analysis, these decisions are measurable with respect to the history at their decision times. Thus ℰ≤tgood:=no failure has been recorded by time t∈ℱt. _≤ t^good:=\no failure has been recorded by time t\ _t. For each potential restart r∈0,…,Tr∈\0,…,T\, define r:=r is reached∩ℰ≤rgood∩[r,r+H) is full and has one parameter. _r:=\r is reached\ _≤ r^good∩\[r,r+H) is full and has one parameter\. The first two events are ℱrF_r-measurable, and the last is fixed by the change sequence, so r∈ℱrC_r _r. Let ℰrGE_r^G and ℰrθE_r^θ denote the Gram and self-normalized events. Let ℰrRE_r^R be the time-uniform RLS event on the subsequent exploitation prefix with the same parameter as in [r,r+H)[r,r+H), ending at the first of the next true change, the next alarm output time, and the horizon. Set ℰrR=ΩE_r^R= when this prefix is empty. The controller-failure events are ℬrG _r^G :=r∩(ℰrG)c, :=C_r∩(E_r^G)^c, ℬrθ _r^θ :=r∩ℰrG∩(ℰrθ)c, :=C_r _r^G∩(E_r^θ)^c, ℬrR _r^R :=r∩ℰrG∩ℰrθ∩(ℰrR)c. :=C_r _r^G _r^θ∩(E_r^R)^c. Conditional on ℱrF_r, Propositions 21 and 22 bound the Gram and self-normalized failure probabilities by δ0 _0 each. On their joint success event, Theorem 19 bounds the conditional RLS failure probability given ℱr+HF_r+H by δ0 _0. Multiplying by the corresponding history indicators and applying the tower property gives ℙ⁡(ℬrG) (B_r^G) ≤δ0, ≤ _0, ℙ⁡(ℬrθ) (B_r^θ) ≤δ0, ≤ _0, ℙ⁡(ℬrR) (B_r^R) ≤δ0. ≤ _0. Consequently, for ℬctrl:=⋃r=0T(ℬrG∪ℬrθ∪ℬrR)B_ ctrl:= _r=0^T(B_r^G _r^θ _r^R), ℙ⁡(ℬctrl)≤3(T+1)δ0=3δ32. (B_ ctrl)≤ 3(T+1) _0= 3δ32. (112) On ℬctrlcB_ ctrl^c, every reached full, unchanged reference whose restart precedes the first detector failure is accurate: otherwise the first controller failure would belong to one of the events above. Hence ℬctrlc∩ℰdetc⊆ℰref∩ℰdetcB_ ctrl^c _ det^c _ ref _ det^c, and Theorem 18 gives ℙ⁡(ℬctrlc∩ℰdetc)≤δd. (B_ ctrl^c _ det^c)≤ _d. This bounds a joint event and does not condition an early detector test on the success of a later estimator. Define ℰgood:=ℬctrlc∩ℰdetE_ good:=B_ ctrl^c _ det. Then ℙ⁡(ℰgood)≥1−3δ32−δ2=1−19δ32>1−δ. (E_ good)≥ 1- 3δ32- δ2=1- 19δ32>1-δ. On this event, the initial reference is valid, every change is detected, and the dwell condition ensures that each nonterminal post-alarm exploration block is full and uncontaminated. I.2 Regret Decomposition On ℰgoodE_ good, let τ^(c) τ^(c) be the alarm corresponding to change c. Its delay interval is c:=τ(c),…,τ^(c)−1,|c|≤D,c=1,…,C. _c:=\τ^(c),…, τ^(c)-1\, |D_c|≤ D, c=1,…,C. The initial and post-alarm exploration intervals are 0 _0 :=0,…,min⁡H,T−1, :=\0,…, \H,T\-1\, c _c :=τ^(c),…,minτ^(c)+H,T−1,c=1,…,C. :=\ τ^(c),…, \ τ^(c)+H,T\-1\, c=1,…,C. An interval is empty when its lower endpoint exceeds its upper endpoint. The dwell condition makes the delay and exploration intervals disjoint, and |c|≤H|X_c|≤ H. Their complement consists of at most C+1C+1 unchanged exploitation prefixes cP_c, one in each true segment, with empty prefixes allowed. Therefore 0,…,T−1=(⋃c=1Cc)∪˙(⋃c=0Cc)∪˙(⋃c=0Cc). \0,…,T-1\= ( _c=1^CD_c ) ∪ ( _c=0^CX_c ) ∪ ( _c=0^CP_c ). For t∈ct _c, the bound |yt+1−wt+1|≤BY+Bw|y_t+1-w_t+1|≤ B_Y+B_w gives cost at most KDK_D. For t∈ct _c, (36) gives cost at most KXK_X. Set nc:=|c|n_c:=|P_c|. Every nonempty cP_c follows a full, unchanged exploration block, so Theorem 19 bounds its regret by RE(nc,δ0)R_E(n_c, _0), uniformly over the resulting prefix length. An empty prefix has zero regret, also bounded by RE(0,δ0)R_E(0, _0). Consequently, ℛT _T ≤∑c=1CKD|c|+∑c=0CKX|c|+∑c=0CRE(nc,δ0) ≤ _c=1^CK_D|D_c|+ _c=0^CK_X|X_c|+ _c=0^CR_E(n_c, _0) ≤CKDD+(C+1)KXH+(C+1)RE(T,δ0), ≤ CK_DD+(C+1)K_XH+(C+1)R_E(T, _0), which is (86). Appendix J TUNING FEASIBILITY AND ORDERS We verify that the exploration and detector requirements in Appendix B admit the logarithmic choices used in Theorem 20. The asymptotic statements keep the model orders and the model, noise, initialization, exploration, ridge, stability, clipping, and gap bounds fixed. J.1 Exploration Length Equation (49) gives εy=5b¯LλBψEθ(H,δ0). _y=5 bL_λB_ψE_θ(H, _0). It is sufficient to require Eθ(H,δ0)≤ϵ⋆, E_θ(H, _0)≤ _ , where ϵ⋆:=min _ := \ 1,bmin16,Δ/85b¯LλBψ,Δ⁡(1−ρΔ)80BoCΔGuLλBψ,Bo5b¯LλBψ. 1, b_ 16, /85 bL_λB_ψ, (1- _ )80B_oC_ G_uL_λB_ψ, B_o5 bL_λB_ψ \. The four accuracy terms enforce the leading-coefficient bound, the null-bias margin, the coupling margin, and εy≤Bo _y≤ B_o, respectively. The cap at one ensures log⁡(1/ϵ⋆)≥0 (1/ _ )≥ 0. All denominators are positive under the standing assumptions, including Lλ>0L_λ>0 from Assumption 7. The deterministic bound (46) satisfies Eθ(H,δ0)≤K01+log⁡(1/δ0)+slog⁡(1+K1H)H−r0 E_θ(H, _0)≤ K_0\1+ (1/ _0)+s (1+K_1H)\ H-r_0 (113) for constants K0,K1K_0,K_1 independent of H,T,δH,T,δ. Thus ℋ:=H∈ℕ:H>r0, := \H :H>r_0, NH≥10Bϕ4κinn2log⁡sδ0,Eθ(H,δ0)≤ϵ⋆, N_H≥ 10B_φ^4 _ inn^2 s _0, E_θ(H, _0)≤ _ , Bψ2ν+κGnH≤116 B_ψ^2ν+ _Gn_H≤ 116 \ is nonempty: as H→∞H→∞, NHN_H grows linearly, while Eθ(H,δ0)E_θ(H, _0) and the leverage bound tend to zero. Every member satisfies (93) and (51)–(52). The smallest feasible integer selected in Appendix B is therefore at most min⁡ℋ . For a,b≥1a,b≥ 1, the condition x≥2alog⁡(2ab)x≥ 2a (2ab) implies x≥alog⁡(bx). x≥ a (bx). (114) Indeed, setting z=x/(2a)z=x/(2a) gives log⁡(bx)=log⁡(2ab)+log⁡z≤log⁡(2ab)+z≤2z=x/a (bx)= (2ab)+ z≤ (2ab)+z≤ 2z=x/a. Squaring (113), restricting to H≥2r0H≥ 2r_0, and applying (114) shows that the accuracy condition is satisfied with H=O⁡(ϵ⋆−2log⁡(1/δ0)+slog⁡(1/ϵ⋆)+1). H=O\! ( _ ^-2\ (1/ _0)+s (1/ _ )+1\ ). The Gram-size and leverage conditions require only O⁡(log⁡(1/δ0)+1)O( (1/ _0)+1) additional lower bounds on H and are absorbed in this order. Since δ0=δ/[32(T+1)] _0=δ/[32(T+1)], H=O⁡(log⁡((T+1)/δ)). H=O( ((T+1)/δ)). (115) J.2 Detector Spacing and Delay Since ρΔ∈(0,1) _ ∈(0,1), the spacing in (53) is finite. Writing log+⁡(x):=max⁡0,log⁡x _+(x):= \0, x\, its explicit form is h=max⁡1,⌈log+⁡(8σw2CΔ2(1−ρΔ2)Δ)2log⁡(1/ρΔ)⌉. h= \1, _+\! ( 8 _w^2C_ ^2(1- _ ^2) )2 (1/ _ ) \. Thus h is independent of T. Equation (54) gives m=O⁡(Bo4Δ2log⁡T+1δ),D=O⁡(hBo4Δ2log⁡T+1δ). m=O\! ( B_o^4 ^2 T+1δ ), D=O\! ( hB_o^4 ^2 T+1δ ). (116) J.3 Regret Constants Under (51), c0 c_0 ≥1−18−18(1716)2>0.73. ≥ 1- 18- 18 ( 1716 )^2>0.73. Equation (46) also yields Q¯H Q_H =Eλ2(ν+nHBψ2)=O⁡(log⁡(1/δ0)+slog⁡(1+H)) =E_λ^2(ν+n_HB_ψ^2)=O\! ( (1/ _0)+s (1+H) ) =O⁡(log⁡((T+1)/δ)), =O( ((T+1)/δ)), while Γ⁡(T) (T) =dlog⁡(1+TBψ2dv¯H)=O⁡(dlog⁡T). =d \! (1+ TB_ψ^2d v_H )=O(d T). Therefore RE(T,δ0)=O⁡(log⁡((T+1)/δ))R_E(T, _0)=O( ((T+1)/δ)). Substituting this bound together with (115) and (116) into (86) proves (87). Appendix K RELAXATIONS OF CLIPPING AND MISMATCH STABILITY This appendix establishes the feasibility and detection results used in Sections 6 and 5. The extensions use either eventual nonclipping or own-regime feasibility with a boundary alarm. K.1 Closed Clipping Feasibility Let P⁡(x)=clip[−Bu,Bu]⁡(x)P(x)=clip_[-B_u,B_u](x). Projection onto a closed interval is nonexpansive. If x∈[−Bu,Bu]x∈[-B_u,B_u], including x=±Bux=± B_u, then |P⁡(z)−x|=|P⁡(z)−P⁡(x)|≤|z−x|. |P(z)-x|=|P(z)-P(x)|≤|z-x|. (117) Equation (117) is the only consequence of the clipping condition used in Lemma 13. That lemma and every later detector, RLS, and global-regret argument therefore hold under the closed feasibility condition in Assumption 10; no positive margin enters a proof constant. For the stable-mismatch theorem, Assumption 10 can be replaced by feasibility of the true reference gain along every unchanged exploitation prefix and every complete alarm-suppressed continuation used in the detector analysis. K.2 Eventual Inactivity of Clipping A quantitative steady-state slack condition yields eventual inactivity of clipping and a burn-in time uniform over restarts. This gives the variant of PIECE-CD in Theorem 6. Define the forced-response output bound and its corresponding regressor bound by Y∞(Bu) Y_∞(B_u) :=Cy1−ρy(Bw+BbBu), := C_y1- _y(B_w+B_bB_u), P∞(Bu) P_∞(B_u) :=Y∞(Bu)2+(q−1)Bu21/2, := \Y_∞(B_u)^2+(q-1)B_u^2 \^1/2, μnc _ nc :=Bu−εu−ΛP∞(Bu). :=B_u- _u- P_∞(B_u). (118) Here εu=54gHBψ _u= 54g_HB_ψ, defined in (49), bounds the raw-proposal error on restG_r est. Suppose μnc>0 _ nc>0. With the convention τnc=0 _ nc=0 when ΛCyBY=0 C_yB_Y=0, put otherwise τnc:=max⁡0,⌈log⁡(ΛCyBY/μnc)log⁡(1/ρy)−H⌉. _ nc:= \! \0, ( C_yB_Y/ _ nc) (1/ _y)-H \. (119) Proposition 23 (Uniform eventual inactivity of clipping). Fix a reached restart r whose full exploration block has one parameter θ−θ^-, and suppose restG_r est holds. At every exploitation time before the next restart satisfying t≥r+H+τnc, t≥ r+H+ _ nc, the raw gated proposal belongs to the clipping interval: |zt|≤Bu,ut=zt. |z_t|≤ B_u, u_t=z_t. (120) The conclusion remains valid after a plant change and does not require the old-gain/new-plant mismatch matrix to be Schur. Proof. The implemented input is clipped at every time, so |ut|≤Bu|u_t|≤ B_u regardless of whether the conclusion has already become true. Starting the state recursion (88) at r, uniform switching stability therefore gives, for every t≥rt≥ r and for any admissible changes after r, ‖Yt‖ Y_t ≤Cyρyt−r‖Yr‖+Y∞(Bu) ≤ C_y _y^t-r Y_r +Y_∞(B_u) ≤Cyρyt−rBY+Y∞(Bu). ≤ C_y _y^t-rB_Y+Y_∞(B_u). The q−1q-1 stored inputs in ψt _t each have magnitude at most BuB_u. Consequently, ‖ψt‖ _t ≤[Y∞(Bu)+Cyρyt−rBY2+(q−1)Bu2]1/2 ≤ [\Y_∞(B_u)+C_y _y^t-rB_Y\^2+(q-1)B_u^2 ]^1/2 ≤P∞(Bu)+Cyρyt−rBY. ≤ P_∞(B_u)+C_y _y^t-rB_Y. On restG_r est, the raw (pre-clipping) part of the gate calculation in Lemma 13 does not use feasibility. On the recursive branch its distance from (λ−)ψt(λ^-) T _t is at most (gH+gH/4)‖ψt‖(g_H+g_H/4) _t , and on the reference branch it is at most (gH/4)‖ψt‖(g_H/4) _t . Hence, on either branch and also after a change, |zt−(λ−)ψt|≤εu. |z_t-(λ^-) T _t|≤ _u. Since ‖λ−‖≤Λ λ^- ≤ , the preceding two displays imply |zt| |z_t| ≤εu+ΛP∞(Bu)+ΛCyBYρyt−r ≤ _u+ P_∞(B_u)+ C_yB_Y _y^t-r =Bu−μnc+ΛCyBYρyt−r. =B_u- _ nc+ C_yB_Y _y^t-r. Definition (119) makes the last term at most μnc _ nc whenever t−r≥H+τnct-r≥ H+ _ nc, proving (120). It also gives |(λ−)ψt|≤Bu−εu|(λ^-) T _t|≤ B_u- _u. The calculation is pathwise on the reference event and uniform over admissible switching sequences. ∎ Proposition 22 and the restart union in (74) give ℙ⁡(ℰref)≥1−2(T+1)δ0=1−δ/16P(E_ ref)≥ 1-2(T+1) _0=1-δ/16. On this event, the conclusion holds simultaneously for every reached full, unchanged exploration block whose restart precedes the first detector failure. Both P∞P_∞ and εu _u depend on BuB_u, so a positive μnc _ nc is not guaranteed by increasing the clipping threshold. An explicit sufficient condition is obtained by setting a0:=CyBw1−ρy,a1:=CyBb1−ρy,κu:=1−Λ⁡a1+q−1. a_0:= C_yB_w1- _y, a_1:= C_yB_b1- _y, _u:=1- \a_1+ q-1\. If κu>0 _u>0, choose Bu>2Λa0κuand then choose H so thatεu≤κuBu2. B_u> 2 a_0 _u then choose $H$ so that _u≤ _uB_u2. (121) Indeed, P∞(Bu)≤a0+(a1+q−1)BuP_∞(B_u)≤ a_0+(a_1+ q-1)B_u, so (121) implies μnc>0 _ nc>0. For fixed BuB_u the required inequality for εu _u is achieved by a sufficiently large feasible H (when the horizon permits) under the exploration bound in (46). A direct sufficient check for immediate nonclipping is (Λ+gH)Bψ≤Bu( +g_H)B_ψ≤ B_u: since ‖λ¯r‖≤Λ λ_r ≤ , every raw exploitation proposal then lies in the clipping interval and no burn-in is needed. Bounded noise alone does not ensure eventual nonclipping. Consider the known scalar system yt+1=12yt+ut+wt+1,Bu=14,ℙ⁡(wt=1)=ℙ⁡(wt=−1)=12. y_t+1= 12y_t+u_t+w_t+1, B_u= 14, (w_t=1)=P(w_t=-1)= 12. The exact minimum-variance gain is λ=−1/2λ=-1/2. If the exact minimum-variance law were unclipped from some finite time onward, then yt+1=wt+1y_t+1=w_t+1 from that time onward, and every following raw action would have magnitude 1/2>Bu1/2>B_u, a contradiction. Thus no finite τnc _ nc exists for this example under that law. Burn-in variant. Before the burn-in ends, clipping may invalidate gate charging and the detector estimates. After each full exploration block, apply reference control for τnc _ nc rounds with detection and RLS updates disabled and the detector buffer empty. Use zt=λ¯rψtz_t= λ_r T _t and ut=clip[−Bu,Bu]⁡(zt)u_t=clip_[-B_u,B_u](z_t). At t0=r+H+τnct_0=r+H+ _ nc set Vt0=νId+∑t∈ℐrψtψtV_t_0=ν I_d+ _t _r _t _t T and λ^t0=λ¯r λ_t_0= λ_r, then use the shifted output grid rnc=t0+h+jh:j≥0S_r nc=\t_0+h+jh:j≥ 0\. Truncate exploration or burn-in at T. Require the first change no earlier than H+τncH+ _ nc, successive changes to be separated by at least D+H+τncD+H+ _ nc, and the terminal segment to have length at least D. From t0t_0 onward clipping is inactive by (120), so the baseline gate, false-alarm, coupling, and RLS proofs apply without Assumption 10. The regret bound gains only the deterministic term (C+1)KDτnc(C+1)K_D _ nc, and the logarithmic order is unchanged whenever τnc=O⁡(log⁡((T+1)/δ)) _ nc=O( ((T+1)/δ)) (in particular, when it is a fixed problem-dependent constant). K.3 Own-Regime Feasibility and a Boundary Alarm A boundary alarm controls the post-change action error under feasibility of each gain only on regressors generated by its own plant. Call a regressor an own-regime successor for θ if it can occur after at least r0r_0 consecutive controls generated by plant θ, starting from any regressor with norm at most BψB_ψ, under disturbances bounded by BwB_w and arbitrary inputs in [−Bu,Bu][-B_u,B_u]. This definition includes the successors produced during exploration and the terminal state at a segment boundary; it is not restricted to states generated by the ideal policy. Assumption 24 (Closed own-regime clipping feasibility). For every θ∈Θθ∈ and every own-regime successor ψ for θ, |λ(θ)ψ|≤Bu. |λ(θ) Tψ|≤ B_u. (122) Equality is allowed, and no positive clipping margin is required. Assumption 24 is an alternative feasibility condition: it checks each gain only on its own-regime successors and does not require the old gain to remain feasible on states produced by the new regime. Because the successor definition permits any norm-bounded starting regressor, including unreachable states, this condition is not asserted to follow from Assumption 10. Define the deterministic reference uncertainty and safe tracking bounds ζH _H :=Eλ(H,δ0)Bψ, :=E_λ(H, _0)B_ψ, ε¯u _u :=εu+2ζH=7LλBψEθ(H,δ0), := _u+2 _H=7L_λB_ψE_θ(H, _0), ε¯y _y :=b¯ε¯u. := b\, _u. (123) The branch-free union-class version of PIECE-CD adds the following test. After an exploitation round t, once yt+1y_t+1 has been observed and ψt+1 _t+1 has been formed, raise one alarm and restart at control time t+1t+1 if |λ¯rψt+1|>Bu+ζH. | λ_r T _t+1|>B_u+ _H. (124) The strict inequality is part of the test: under the null, equality with the upper bound is possible for discrete disturbances. If both the boundary and energy tests cross at the same output, they count as one alarm. Algorithm L.1 states the complete composite procedure. Lemma 25 (Boundary-alarm dichotomy). Under Assumption 24, fix a reached cycle whose full exploration block has parameter θ−θ^-, and suppose restG_r est holds. Then the boundary test cannot cross while the reference parameter remains active. On such an unchanged exploitation interval, with at:=(λ^t−λ⁡(θ−))ψta_t:=( λ_t-λ(θ^-)) T _t and et:=ut−λ(θ−)ψte_t:=u_t-λ(θ^-) T _t, one also has et2≤at2e_t^2≤ a_t^2. After a change within this exploitation cycle, at every control time before the cycle’s next alarm, (|λ(θ−)ψt|−Bu)+ (|λ(θ^-) T _t|-B_u )_+ ≤2ζH, ≤ 2 _H, (125) |ut−λ(θ−)ψt| |u_t-λ(θ^-) T _t| ≤ε¯u. ≤ _u. (126) These inequalities also hold in the alarm-suppressed continuation at control states satisfying |λ¯rψt|≤Bu+ζH| λ_r T _t|≤ B_u+ _H. Proof. While the reference parameter θ−θ^- remains active, every exploitation regressor is an own-regime successor. On restG_r est, ‖λ¯r−λ⁡(θ−)‖≤Eλ(H,δ0) λ_r-λ(θ^-) ≤ E_λ(H, _0), so (122) gives |λ¯rψt| | λ_r T _t| ≤|λ(θ−)ψt|+‖λ¯r−λ⁡(θ−)‖‖ψt‖ ≤|λ(θ^-) T _t|+ λ_r-λ(θ^-) _t ≤Bu+ζH. ≤ B_u+ _H. The strict test in (124) therefore cannot give a boundary false alarm. Since the old ideal action is feasible on the unchanged interval, the gate-charging and projection argument of Lemma 13 applies verbatim and gives et2≤at2e_t^2≤ a_t^2. For a change occurring during the exploitation cycle in the lemma, at the first post-change control the regressor is still an own-regime successor for θ−θ^-, so its saturation deficit is zero. At every later post-change control time with no previous boundary alarm, |λ(θ−)ψt| |λ(θ^-) T _t| ≤|λ¯rψt|+Eλ(H,δ0)Bψ≤Bu+2ζH, ≤| λ_r T _t|+E_λ(H, _0)B_ψ≤ B_u+2 _H, which proves (125). The raw gated proposal satisfies |zt−λ(θ−)ψt|≤εu|z_t-λ(θ^-) T _t|≤ _u. For P⁡(x)=clip[−Bu,Bu]⁡(x)P(x)=clip_[-B_u,B_u](x) and any x,z∈ℝx,z , |P⁡(z)−x| |P(z)-x| ≤|P⁡(z)−P⁡(x)|+|P⁡(x)−x| ≤|P(z)-P(x)|+|P(x)-x| ≤|z−x|+(|x|−Bu)+. ≤|z-x|+(|x|-B_u)_+. Combining this inequality with (125) gives (126). The same calculation applies pointwise in the alarm-suppressed continuation whenever |λ¯rψt|≤Bu+ζH| λ_r T _t|≤ B_u+ _H. ∎ K.4 Detection under the Union Condition The boundary tracking bound (126) permits a common finite-window detector for stable, directly visible, and non-Schur ARX mismatches. For an admissible adjacent pair z=(θ−,θ+)z=(θ^-,θ^+), write Az:=A⁡(θ−,θ+),Gh(Az):=σw2∑j=1h−1(e1Azje1)2. A_z:=A(θ^-,θ^+), G_h(A_z):= _w^2 _j=1^h-1(e_1 TA_z^je_1)^2. The supplied admissible adjacent-pair class ⊆Θ2P ^2 has a cover ⊆∪P _ S _ F. The finite-window component may itself be covered by ⊆∪P_ F _ D _ A. The set P_ D uses a directly supplied finite-order gap, whereas P_ A uses only the ARX non-Schur condition ρ⁡(Az)≥1ρ(A_z)≥ 1. These sets may overlap. These classes specify uniform tuning bounds. Define the finite-order innovation visibility ⁡(z):=σw2∑j=1de1Azje12. (z):= _w^2 _j=1^d\e_1 TA_z^je_1\^2. (127) For θ∈Θθ∈ , define the monic old-input polynomial B¯θ(ξ):=ξq−1+b2(θ)b1(θ)ξq−2+⋯+bq(θ)b1(θ), B_θ(ξ):=ξ^q-1+ b_2(θ)b_1(θ)ξ^q-2+·s+ b_q(θ)b_1(θ), with B¯θ≡1 B_θ≡ 1 when q=1q=1. Under the minimum-phase convention in Assumption 7, every root of B¯θ B_θ lies in the open unit disk. Continuity of polynomial roots and compactness therefore give a safe uniform number rB≥supθ∈Θmax⁡|β|:B¯θ(β)=0,0≤rB<1, r_B≥ _θ∈ \|β|: B_θ(β)=0\, 0≤ r_B<1, (128) where the maximum over the empty set is zero. Also let RA≥max⁡1,sup(θ−,θ+)∈Θ2‖Acl(λ⁡(θ−),θ+)‖2<∞,KA:=∑k=1dRAd−k∑j=0k−1(dj)RAj. R_A≥ \1, _(θ^-,θ^+)∈ ^2 A_ cl(λ(θ^-),θ^+) _2 \<∞, K_A:= _k=1^dR_A^d-k _j=0^k-1 djR_A^j. (129) These are offline model-class bounds. The uniform root bound follows from continuity of polynomial zeros and compactness (Horn and Johnson,, 2013, Appendix D, Theorem D1, and Appendix E). Finite-order visibility of non-Schur mismatches. Define Δ¯:=σw2(1−rB)q−1KA2>0. _ A:= _w^2 \ (1-r_B)^q-1K_A \^2>0. (130) Then every ARX mismatch matrix AzA_z satisfying ρ⁡(Az)≥1ρ(A_z)≥ 1 obeys ⁡(z)≥Δ¯. (z)≥ _ A. (131) This implication uses the ARX and minimum-phase structure; it is false for a general square matrix. To prove it, put hj=e1Azje1h_j=e_1 TA_z^je_1 and Dz(ξ) D_z(ξ) :=det(ξI−Az)=ξd+∑k=1ddkξd−k, := (ξ I-A_z)=ξ^d+ _k=1^dd_kξ^d-k, Q−(ξ) Q_-(ξ) :=ξpB¯θ−(ξ)=ξd+∑k=1dqkξd−k. :=ξ^p B_θ^-(ξ)=ξ^d+ _k=1^dq_kξ^d-k. A cofactor expansion using the shift rows of AzA_z gives e1adj⁡(ξI−Az)e1=ξp−1B¯θ−(ξ). e_1 Tadj(ξ I-A_z)e_1=ξ^p-1 B_θ^-(ξ). (132) Indeed, deleting the first row and column leaves a block-lower-triangular minor: its output-shift block has determinant ξp−1ξ^p-1 and its old-input companion block has determinant B¯θ−(ξ) B_θ^-(ξ). The adjugate formula and the Laurent expansion at infinity then give the exact disturbance-to-output identity, for |ξ|>ρ⁡(Az)|ξ|>ρ(A_z) (equivalently, as a formal Laurent identity at infinity), ξe1(ξI−Az)−1e1=1+∑j≥1hjξ−j=Q−(ξ)Dz(ξ). ξ e_1 T(ξ I-A_z)^-1e_1=1+ _j≥ 1h_jξ^-j= Q_-(ξ)D_z(ξ). (133) Comparing the coefficient of ξd−kξ^d-k in Dz(ξ)(1+∑j≥1hjξ−j)=Q−(ξ)D_z(ξ)(1+ _j≥ 1h_jξ^-j)=Q_-(ξ) gives, with d0=1d_0=1, qk−dk=∑i=1kdk−ihi,k=1,…,d. q_k-d_k= _i=1^kd_k-ih_i, k=1,…,d. (134) Let η:=max1≤j≤d⁡|hj|η:= _1≤ j≤ d|h_j| and choose an eigenvalue λ⋆ _ with |λ⋆|=ρ⁡(Az)≥1| _ |=ρ(A_z)≥ 1. Since |dj|≤(dj)RAj|d_j|≤ djR_A^j and |λ⋆|≤RA| _ |≤ R_A (the spectral radius is bounded by every induced matrix norm (Horn and Johnson,, 2013, Theorem 5.6.9)), equations (134) and Dz(λ⋆)=0D_z( _ )=0 imply |Q−(λ⋆)|≤ηKA. |Q_-( _ )|≤η K_A. On the other hand, Q−Q_- has p zeros at zero and its other q−1q-1 zeros have modulus at most rBr_B, so |Q−(λ⋆)|≥|λ⋆|p(|λ⋆|−rB)q−1≥(1−rB)q−1. |Q_-( _ )|≥| _ |^p(| _ |-r_B)^q-1≥(1-r_B)^q-1. Combining the last two displays and using ⁡(z)≥σw2η2V(z)≥ _w^2η^2 proves (131). If a stronger class-wide margin ρ⁡(Az)≥ca>1ρ(A_z)≥ c_a>1 is available, the same proof gives the sharper constant Δ¯(ca):=σw2cap(ca−rB)q−1/KA2 _ A(c_a):= _w^2\c_a^p(c_a-r_B)^q-1/K_A\^2, which may replace Δ¯ _ A in the tuning. Such a margin is not required for the theorem below. Assumption 26 (Union stable/direct/non-Schur detectability). Every realized adjacent pair zc=(θ(c−1),θ(c))z_c=(θ^(c-1),θ^(c)), c=1,…,Cc=1,…,C, belongs to P. For a nonempty stable component there are supplied constants C≥1C_ S≥ 1, ρ∈(0,1) _ S∈(0,1), and Δ¯>0 _ S>0; for a nonempty direct-visibility component there is a supplied Δ¯>0 _ D>0; and the possibly empty ARX non-Schur component satisfies z∈ z _ S ⟹‖Azk‖≤Cρk(k≥0),Jy(λ(θ−);θ+)−σw2≥Δ¯, A_z^k ≤ C_ S _ S^k (k≥ 0), J_y(λ(θ^-);θ^+)- _w^2≥ _ S, z∈ z _ D ⟹⁡(z)≥Δ¯, (z)≥ _ D, z∈ z _ A ⟹ρ⁡(Az)≥1. ρ(A_z)≥ 1. (135) Each admitted pair satisfies at least one component condition. A stable pair requires no separate finite-order gap; for a non-Schur pair, that gap is supplied by (130). Set Γ=Δ¯ _ D= _ D when ≠∅P_ D≠ and Γ=+∞ _ D=+∞ otherwise. Set Γ=Δ¯ _ A= _ A when ≠∅P_ A≠ and Γ=+∞ _ A=+∞ otherwise. If ≠∅P_ F≠ , define Δ¯:=min⁡Γ,Γ>0. _ F:= \ _ D, _ A\>0. (136) Equations (127) and (131) then give the derived common bound z∈⟹⁡(z)≥Δ¯. z _ F (z)≥ _ F. (137) This is the finite-visible condition used in Section 5. For a nonempty stable component, define h h_ S :=min⁡k≥1:σw2C2ρ2k1−ρ2≤Δ¯8, := \k≥ 1: _w^2C_ S^2 _ S^2k1- _ S^2≤ _ S8 \, Γ _ S :=7Δ¯8. := 7 _ S8. If =∅P_ S= , set (h,Γ)=(1,+∞)(h_ S, _ S)=(1,+∞). If ≠∅P_ F≠ , set (h,Γ)=(d+1,Δ¯)(h_ F, _ F)=(d+1, _ F); otherwise set (h,Γ)=(1,+∞)(h_ F, _ F)=(1,+∞). If =∅P= , set h=1h_ U=1 and choose any fixed finite Δ¯>0 _ U>0 for null calibration; every missed-change statement is then vacuous. Otherwise at least one cover component is nonempty, and set h h_ U :=max⁡h,h, := \h_ S,h_ F\, Δ¯ _ U :=min⁡Γ,Γ>0. := \ _ S, _ F\>0. (138) The resulting common finite-horizon power separation is Gh(Az)≥Δ¯,z∈. G_h_ U(A_z)≥ _ U, z . (139) Indeed, if z∈z _ S, then Gh(Az) G_h_ U(A_z) =Jy(λ⁡(θ−),θ+)−σw2−σw2∑j=h∞(e1Azje1)2 =J_y(λ(θ^-);θ^+)- _w^2- _w^2 _j=h_ U^∞(e_1 TA_z^je_1)^2 ≥Δ¯−σw2C2ρ2h1−ρ2≥7Δ¯8≥Δ¯. ≥ _ S- _w^2C_ S^2 _ S^2h_ U1- _ S^2≥ 7 _ S8≥ _ U. If z∈z _ F, then h≥d+1h_ U≥ d+1 and the nonnegative summands give Gh(Az)≥⁡(z)≥Δ¯≥Δ¯G_h_ U(A_z) (z)≥ _ F≥ _ U. This proves (139) without identifying which route holds for the realized change. The first d impulse coefficients exhaust finite-order visibility by Cayley–Hamilton (Horn and Johnson,, 2013, Theorem 2.4.3.2). Let hj=e1Aje1h_j=e_1 TA^je_1, so h0=1h_0=1, and write the characteristic polynomial as pA(z)=zd+κd−1zd−1+⋯+κ0p_A(z)=z^d+ _d-1z^d-1+·s+ _0. If h1=⋯=hd=0h_1=·s=h_d=0, sandwiching pA(A)=0p_A(A)=0 between e1e_1 T and e1e_1 gives κ0=0 _0=0. Sandwiching AkpA(A)=0A^kp_A(A)=0 for k≥1k≥ 1 and using strong induction then gives hj=0h_j=0 for every j≥1j≥ 1. Thus every change visible through a noise-driven impulse coefficient is visible by order d. If =∅P= , set L0,=Lw,=Lu,=0L_0, U=L_w, U=L_u, U=0. Otherwise, the same model-class bound RAR_A gives the explicit finite-horizon choices L0, L_0, U :=RAh, :=R_A^h_ U, Lw, L_w, U :=∑j=0h−1RAj, := _j=0^h_ U-1R_A^j, Lu, L_u, U :=Gu∑j=0h−1RAj. :=G_u _j=0^h_ U-1R_A^j. (140) Indeed, |xAjy|≤‖x‖2‖A‖2j‖y‖2|x TA^jy|≤ x _2 A _2^j y _2. These bounds are finite because h_ U is finite, even when some matrices in P_ A are non-Schur. Sharper supplied bounds may replace them without changing the proof. Define Baux, B_ aux, U :=L0,Bψ+Lw,Bw, :=L_0, UB_ψ+L_w, UB_w, B B_ U :=max⁡BY,Baux,,Bw, := \B_Y,B_ aux, U,B_w\, R(H) R_ U(H) :=Lu,ε¯u. :=L_u, U _u. (141) In addition to the exploration sample-size condition and (51), choose the smallest H satisfying ε¯y2 _y^2 ≤Δ¯8, ≤ _ U8, ε¯y _y ≤B, ≤ B_ U, 2BR(H) 2B_ UR_ U(H) ≤Δ¯8. ≤ _ U8. (142) Use spacing h_ U, the energy threshold σw2+Δ¯/2 _w^2+ _ U/2, and set m m_ U :=⌈512B4Δ¯2log⁡4T2δd⌉, := 512B_ U^4 _ U^2 4T^2 _d , D D_ U :=(m+1)h. :=(m_ U+1)h_ U. (143) Assumption 12 is read with D_ U in place of D. Fix z=(θ−,θ+)∈z=(θ^-,θ^+) and a potential restart r whose exploration reference estimates λ⁡(θ−)λ(θ^-). Continue the clipped controller on the same restart-relative calendar with both alarms suppressed. Its regressor remains bounded by BψB_ψ on every path. For a stored output time s with s−h≥r+Hs-h_ U≥ r+H, define the h_ U-step auxiliary ψ~s−h(s) ψ_s-h_ U^(s) :=ψs−h, := _s-h_ U, ψ~t+1(s) ψ_t+1^(s) =Azψ~t(s)+e1wt+1,s−h≤t<s. =A_z ψ_t^(s)+e_1w_t+1, s-h_ U≤ t<s. (144) Let y~s(s) y_s^(s) be its first coordinate. This auxiliary is defined on every continuation path, including paths on which the boundary test would cross. Lemma 27 (Sample-local union power and comparison). For the pair z∈z and continuation defined above, suppose θ+θ^+ is active throughout [s−h,s)[s-h_ U,s). Then |y~s(s)| | y_s^(s)| ≤Baux,, ≤ B_ aux, U, (145) ⁡[(y~s(s))2∣ℱs−h] [( y_s^(s))^2 _s-h_ U] ≥σw2+Δ¯. ≥ _w^2+ _ U. (146) On restG_r est and on the event that the boundary test has not crossed at the states used for the controls in [s−h,s)[s-h_ U,s), |ys−y~s(s)| |y_s- y_s^(s)| ≤R(H), ≤ R_ U(H), |ys2−(y~s(s))2| |y_s^2-( y_s^(s))^2| ≤2BR(H)≤Δ¯8. ≤ 2B_ UR_ U(H)≤ _ U8. (147) The conditional statements remain valid at finite lag-h_ U predictable output times. Proof. Iterating (144) gives ψ~s(s)=Azhψs−h+∑j=0h−1Azje1ws−j. ψ_s^(s)=A_z^h_ U _s-h_ U+ _j=0^h_ U-1A_z^je_1w_s-j. The definitions of L0,L_0, U and Lw,L_w, U give (145). Conditional on ℱs−hF_s-h_ U, the starting state is fixed and ws−h+1,…,wsw_s-h_ U+1,…,w_s are fresh, independent, and centered. Hence ⁡[(y~s(s))2∣ℱs−h] [( y_s^(s))^2 _s-h_ U] =(e1Azhψs−h)2+σw2∑j=0h−1(e1Azje1)2 =(e_1 TA_z^h_ U _s-h_ U)^2+ _w^2 _j=0^h_ U-1(e_1 TA_z^je_1)^2 ≥σw2+Gh(Az)≥σw2+Δ¯, ≥ _w^2+G_h_ U(A_z)≥ _w^2+ _ U, which proves (146). On the no-boundary event in the statement, Lemma 25 gives ut=λ(θ−)ψt+etu_t=λ(θ^-) T _t+e_t with |et|≤ε¯u|e_t|≤ _u throughout [s−h,s)[s-h_ U,s). Subtracting the two state recursions and unrolling from their common state at s−hs-h_ U gives |ys−y~s(s)| |y_s- y_s^(s)| ≤ε¯u∑j=0h−1|e1Azjgu(θ+)|≤Lu,ε¯u. ≤ _u _j=0^h_ U-1|e_1 TA_z^jg_u(θ^+)|≤ L_u, U _u. Both output magnitudes are at most B_ U, so |x2−z2|≤|x−z|(|x|+|z|)|x^2-z^2|≤|x-z|(|x|+|z|) proves (147). For a finite lag-h_ U predictable time, multiply the deterministic-time identities by s=t∈ℱt−h1\s=t\ _t-h_ U and sum over t. This gives the same relations with the stopped field ℱs−hF_s-h_ U. ∎ Lemma 28 (One-change detection under the union condition). Adopt the stopping-time, active-cycle, and horizon hypotheses of Lemma 17, use Algorithm L.1, replace D by D_ U, and suppose Assumptions 24 and 26 hold. Almost surely on the corresponding r,τA_r,τ, ℙ⁡(τ^r>τ+D∣ℱτ)≤δd4T2. ( τ_r>τ+D_ U _τ)≤ _d4T^2. (148) Proof. Condition on an arbitrary ℱτF_τ history in r,τA_r,τ and use the alarm-suppressed continuation just defined. The deterministic calendar argument in Appendix H gives stored output times s1,…,sms_1,…,s_m_ U such that s1−h≥τs_1-h_ U≥τ, sk+1−sk=hs_k+1-s_k=h_ U, and sm−τ<Ds_m_ U-τ<D_ U. Conditionally on ℱτF_τ, the restart-relative grid is lag-h_ U predictable, ℱτ⊆ℱs1−hF_τ _s_1-h_ U, and the disturbances used by the sample-local auxiliaries remain fresh. Apply the conditional form of Lemma 14 given ℱτF_τ to the sample-local variables y~sk(sk) y_s_k^(s_k), using the lagged filtration ℋk−1:=ℱsk−hH_k-1:=F_s_k-h_ U. Lemma 27 gives the required conditional means, and |y~sk(sk)|≤B| y_s_k^(s_k)|≤ B_ U. Therefore ℙ⁡(1m∑k=1m(y~sk(sk))2<σw2+7Δ¯8|ℱτ) \! ( 1m_ U _k=1^m_ U( y_s_k^(s_k))^2< _w^2+ 7 _ U8\ |\ F_τ ) ≤exp⁡(−mΔ¯2128B4) ≤ \! (- m_ U _ U^2128B_ U^4 ) ≤δd4T2. ≤ _d4T^2. (149) This concentration bound is not conditioned on survival of the boundary test. If either test raises an alarm at or before sms_m_ U, the change has already been detected. Otherwise, the actual and alarm-suppressed trajectories agree through the complete block, and (147) holds at every sample. Outside the deviation in (149), the actual empirical energy is at least σw2+3Δ¯/4 _w^2+3 _ U/4, which crosses the threshold σw2+Δ¯/2 _w^2+ _ U/2. Consequently, τ^r>τ+D⊆1m∑k=1m(y~sk(sk))2<σw2+7Δ¯8. \ τ_r>τ+D_ U\ \ 1m_ U _k=1^m_ U( y_s_k^(s_k))^2< _w^2+ 7 _ U8 \. Taking probabilities proves (148). ∎ A smaller Δ¯ _ U increases the exploration and window requirements in (142)–(143). Uniform finite delay requires every admitted Schur pair to satisfy either the stable-gap or direct-visibility condition. A scalar non-Schur mismatch. Take p=q=1p=q=1, Bu=10B_u=10, zero initial history, and Rademacher noise with Bw=σw=1B_w= _w=1. Let Θ=θ−,θ+ =\θ^-,θ^+\ and consider the one-change sequence θ−→θ+θ^-→θ^+, where θ−=(−0.2,0.2),θ+=(0.2,1). θ^-=(-0.2,0.2), θ^+=(0.2,1). Both open-loop coefficients have magnitude 0.20.2, and the deterministic output bound is BY=11/(1−0.2)=13.75B_Y=11/(1-0.2)=13.75. The interval [−BY,BY][-B_Y,B_Y] is invariant under either plant with |ut|≤Bu|u_t|≤ B_u and |wt|≤1|w_t|≤ 1. The two ideal gains are λ−=1λ^-=1 and λ+=−0.2λ^+=-0.2. Every one-step own-regime successor satisfies |λ−y+| |λ^-y^+| ≤0.2BY+0.2Bu+Bw=5.75, ≤ 0.2B_Y+0.2B_u+B_w=5.75, |λ+y+| |λ^+y^+| ≤0.2BY=2.75. ≤ 0.2B_Y=2.75. Thus Assumption 24 holds, while the old gain need not be feasible on every state produced by the new plant. Nevertheless, A⁡(θ−,θ+)=0.2+1⋅1=1.2A(θ^-,θ^+)=0.2+1· 1=1.2. Here d=1d=1, so h=2h_ F=2 and ⁡(θ−,θ+)=1.22=1.44V(θ^-,θ^+)=1.2^2=1.44. Since rB=0r_B=0 here, the non-Schur formula itself supplies the valid positive bound Δ¯=1 _ A=1; no separate visibility assumption is needed. K.5 Regret with Saturation Without clipping feasibility, exploitation regret can be controlled by the realized saturation energy. For a true gain λ, define dtsat:=(|λψt|−Bu)+. d_t^sat:= (|λ T _t|-B_u )_+. (150) On an unchanged exploitation segment with a successful reference and gH=4Eλg_H=4E_λ, the unclipped gate-charging inequality from Appendix G and the projection distance inequality give |ut−λψt|≤|at|+dtsat,at=(λ^t−λ)ψt. |u_t-λ T _t|≤|a_t|+d_t^sat, a_t=( λ_t-λ) T _t. (151) Let βs:=1/8 _s:=1/8 and define cs c_s :=1−2α¯−βs−4ℓ¯(1+α¯)2, :=1-2 α- _s-4 (1+ α)^2, ks k_s :=α¯2(βs−1+4ℓ¯). := α^2( _s^-1+4 ). (152) Under (51), cs>0.467c_s>0.467. Proposition 29 (Exploitation regret with saturation energy). Under the estimation, Gram, and unchanged-segment hypotheses of Theorem 19, but without clipping feasibility, with conditional probability at least 1−δ01- _0, simultaneously for every prefix of length n, ∑t(yt+1−wt+1)2≤2b¯2[ _t(y_t+1-w_t+1)^2≤ 2 b^2 [ 2Q¯Hcs+8Bη2cs2log⁡1δ0+4Bη2csΓ(n) 2 Q_Hc_s+ 8B_η^2c_s^2 1 _0+ 4B_η^2c_s (n) +(1+2kscs)∑t(dtsat)2]. + (1+ 2k_sc_s ) _t(d_t^sat)^2 ]. (153) Proof. Start from the exact identity (79). From (151), |et|≤|at|+dtsat|e_t|≤|a_t|+d_t^sat. Young’s inequality gives 2αatet 2α a_te_t ≤(2α¯+βs)at2+α¯2βs(dtsat)2, ≤(2 α+ _s)a_t^2+ α^2 _s(d_t^sat)^2, (αet+ηt+1−at)2 (α e_t+ _t+1-a_t)^2 ≤4(1+α¯)2at2+4α¯2(dtsat)2+2ηt+12. ≤ 4(1+ α)^2a_t^2+4 α^2(d_t^sat)^2+2 _t+1^2. Using ℓt≤ℓ¯ _t≤ yields Qt+1−Qt≤−csat2+2atηt+1+2ℓtηt+12+ks(dtsat)2. Q_t+1-Q_t≤-c_sa_t^2+2a_t _t+1+2 _t _t+1^2+k_s(d_t^sat)^2. The same time-uniform exponential supermartingale as in (81), now evaluated with csc_s, and the same elliptical-potential bound give ∑tat2≤2Q¯Hcs+8Bη2cs2log⁡1δ0+4Bη2csΓ(n)+2kscs∑t(dtsat)2. _ta_t^2≤ 2 Q_Hc_s+ 8B_η^2c_s^2 1 _0+ 4B_η^2c_s (n)+ 2k_sc_s _t(d_t^sat)^2. Finally, (yt+1−wt+1)2≤2b¯2(at2+(dtsat)2)(y_t+1-w_t+1)^2≤ 2 b^2(a_t^2+(d_t^sat)^2), which proves (153). ∎ Proposition 29 gives logarithmic unchanged-segment regret when ∑t(dtsat)2=O⁡(log⁡((T+1)/δ)) _t(d_t^sat)^2=O( ((T+1)/δ)). A global detection guarantee additionally requires a blockwise power gap for the clipped loop or control of its saturation residual on every potential detector block. The non-Schur gap (130) applies to the unclipped auxiliary; Lemma 27 transfers it to the actual output using the boundary test. Proposition 30 (Saturation lower bound). For every policy with |ut|≤Bu|u_t|≤ B_u, ℛT≥bmin2∑t=0T−1(|λ(θt)ψt|−Bu)+2. _T≥ b_ ^2 _t=0^T-1(|λ( _t) T _t|-B_u)_+^2. (154) Consequently, if the realized saturation energy grows faster than log⁡T T, logarithmic regret under (3) is impossible, even when the parameter sequence is known. Proof. For xt=λ(θt)ψtx_t=λ( _t) T _t and every feasible action, |ut−xt|≥dist⁡(xt,[−Bu,Bu])=(|xt|−Bu)+. |u_t-x_t| (x_t,[-B_u,B_u])=(|x_t|-B_u)_+. The gain form (36) gives (yt+1−wt+1)2=b1(θt)2(ut−xt)2(y_t+1-w_t+1)^2=b_1( _t)^2(u_t-x_t)^2. Use b1(θt)≥bminb_1( _t)≥ b_ and sum over t. ∎ Appendix L A UNIFIED DETECTOR FOR THE UNION CLASS Algorithm L.1 implements the union-class detector introduced in Section 5. Its two tests use constants supplied offline; the algorithm neither receives the realized pair’s class nor computes its spectral radius. The terms Schur and non-Schur refer to the old-gain/new-plant matrix Acl(λ⁡(θ−),θ+)A_ cl(λ(θ^-),θ^+). The plant retains Assumptions 7, 8, and 9; bounded applied inputs therefore preserve the deterministic state bound. L.1 Complete Algorithm Algorithm 3: Branch-free union-class PIECE-CD Input: p,q,Θ,T,δ,Bu,ν,σw2,Bwp,q, ,T,δ,B_u,ν, _w^2,B_w; the exploration distribution and the safe model/excitation bounds used in Bψ,κG,EθB_ψ, _G,E_θ; H satisfying (93), (51), and (142); the offline union-class constants defining h_ U and Δ¯ _ U in (138); the model-class bounds rB,RAr_B,R_A in (128)–(129) when the non-Schur route is used; the finite-horizon constants in (140); and m,Dm_ U,D_ U from (143). Set ζH=Eλ(H,δ0)Bψ _H=E_λ(H, _0)B_ψ. Initialize the restart time r←0r← 0 and clear the energy buffer. Loop. While r<Tr<T, execute one cycle. (a) Explore. For t=r,…,min⁡r+H−1,T−1t=r,…, \r+H-1,T-1\, draw a fresh exploratory input, apply it, and observe yt+1y_t+1. If the horizon is reached during this step, stop. (b) Estimate and initialize. From ℐr=r+r0,…,r+H−1I_r=\r+r_0,…,r+H-1\, compute Vrθ V_r^θ :=νIs+∑t∈ℐrϕtϕt, :=ν I_s+ _t _r _t _t T, θ~r θ_r :=(Vrθ)−1∑t∈ℐrϕtyt+1, :=(V_r^θ)^-1 _t _r _ty_t+1, θ^r θ_r :=ΠΘ(θ~r), := _ ( θ_r), b^r b_r :=b1(θ^r), :=b_1( θ_r), λ¯r λ_r :=λ⁡(θ^r). :=λ( θ_r). Initialize Vr+H:=νId+∑t∈ℐrψtψt,λ^r+H:=λ¯r. V_r+H:=ν I_d+ _t _r _t _t T, λ_r+H:= λ_r. Clear the energy buffer and declare the predictable output-time grid r:=r+H+h+jh:j=0,1,…. _r:=\r+H+h_ U+jh_ U:j=0,1,…\. (c) Exploit and monitor. For t=r+H,r+H+1,…,T−1t=r+H,r+H+1,…,T-1, form zt z_t :=λ^tψt,|(λ^t−λ¯r)ψt|≤gH‖ψt‖,λ¯rψt,otherwise, := cases λ_t T _t,&|( λ_t- λ_r) T _t|≤ g_H _t ,\\ λ_r T _t,&otherwise, cases ut u_t :=clip[−Bu,Bu]⁡(zt). :=clip_[-B_u,B_u](z_t). Before observing yt+1y_t+1, mark that output as energy-eligible exactly when t+1∈rt+1 _r. Apply utu_t, observe yt+1y_t+1, and form ψt+1 _t+1. Make the RLS update xt+1λ x_t+1^λ :=ut−yt+1b^r, :=u_t- y_t+1 b_r, Vt+1 V_t+1 :=Vt+ψtψt, :=V_t+ _t _t T, λ^t+1 λ_t+1 :=λ^t+Vt+1−1ψt(xt+1λ−λ^tψt). := λ_t+V_t+1^-1 _t(x_t+1^λ- λ_t T _t). Set the boundary flag Bt+1:=|λ¯rψt+1|>Bu+ζH. B_t+1:=1\! \| λ_r T _t+1|>B_u+ _H \. The strict inequality is part of the algorithm. If yt+1y_t+1 was marked eligible, append yt+12y_t+1^2 to the energy buffer and retain only the most recent m_ U stored values. Set Et+1:=|buffer|=m,1m∑z∈bufferz≥σw2+Δ¯2,t+1∈r,0,t+1∉r. E_t+1:= cases1\! \|buffer|=m_ U,\ 1m_ U _z z≥ _w^2+ _ U2 \,&t+1 _r,\\ 0,&t+1 _r. cases If Bt+1=1B_t+1=1 or Et+1=1E_t+1=1, raise one alarm at output time t+1t+1, discard the current estimates, set r←t+1r← t+1, clear the buffer, and return to step (a). If both flags equal one, still record only one alarm. If neither flag crosses and t=T−1t=T-1, stop; otherwise continue exploitation. Eligibility is declared before yt+1y_t+1 is observed, so the sampling grid is predictable. The boundary flag is checked after every exploitation output, not only at energy-sampling times. It is therefore available before the next control is chosen. L.2 Common Tuning Under Assumption 26, (138) specifies a common lag h_ U and separation Δ¯ _ U. For the excess innovation power GhG_h defined in Appendix K, (139) gives Gh(A)≥Δ¯ G_h_ U(A)≥ _ U for every admitted mismatch A=Acl(λ⁡(θ−),θ+)A=A_ cl(λ(θ^-),θ^+). The finite-horizon bounds in (140)– (141), the accuracy conditions (142), and the window in (143) therefore provide one calibration for all three detection conditions. L.3 Detection and Regret Guarantee Theorem 31 (Branch-free union-class detector and regret guarantee). Retain Assumptions 7, 8, and 9. Replace global cross-regime clipping feasibility and stable mismatch by closed own-regime feasibility (Assumption 24) and the union stable/direct/non-Schur condition (Assumption 26), with the common separation (139) and finite-horizon bounds (140). Choose H as the smallest feasible integer satisfying (93), (51), and (142); choose m,Dm_ U,D_ U by (143); and read Assumption 12 with D_ U in place of D. Then Algorithm L.1 satisfies, with probability at least 1−δ1-δ, no false alarms and exactly one alarm τ^(c) τ^(c) for every true change, with τ(c)<τ^(c)≤τ(c)+D, τ^(c)< τ^(c)≤τ^(c)+D_ U, (155) and ℛT≤CKDD+(C+1)KXH+(C+1)RE(T,δ0). _T≤ CK_DD_ U+(C+1)K_XH+(C+1)R_E(T, _0). (156) For fixed problem constants and fixed C, ℛT=O⁡(log⁡((T+1)/δ))R_T=O( ((T+1)/δ)). More generally, ℛT=O⁡((C+1)log⁡T+1δ). _T=O\! ((C+1) T+1δ ). (157) Proof. If T≤HT≤ H, the dwell condition forces C=0C=0. Algorithm L.1 performs only truncated exploration and stops, so ℛT≤KXT≤KXHR_T≤ K_XT≤ K_XH, which is bounded by the right-hand side of (156). Hence assume T>HT>H below. Read the restart, reference, and detector events from Theorem 18 and Appendix I using the first composite crossing and D_ U in place of D. Fix a potential restart r and test endpoint e for which the reference parameter remains active throughout [r,e)[r,e). Condition on an ℱr+HF_r+H history with a full exploration block and restG_r est. Since H>r0H>r_0, the action and boundary-test regressors are own-regime successors throughout the unchanged exploitation interval. Lemma 25 therefore excludes boundary crossings and gives et2≤at2e_t^2≤ a_t^2, as required by Theorem 19. This includes a test at output time e=τe=τ when the first subsequent change occurs at control time τ. For each fixed null energy block, the proof of Lemma 15 applies with (Δ,Bo,m)( ,B_o,m) replaced by (Δ¯,B,m)( _ U,B_ U,m_ U). Indeed, |vs|≤εy≤ε¯y|v_s|≤ _y≤ _y, ε¯y2≤Δ¯/8 _y^2≤ _ U/8, and B≥max⁡Bw,ε¯yB_ U≥ \B_w, _y\. The conditional crossing probability is bounded by exp⁡(−mΔ¯232Bw4)+exp⁡(−mΔ¯2512Bw2ε¯y2)≤δd2T2, \! (- m_ U _ U^232B_w^4 )+ \! (- m_ U _ U^2512B_w^2 _y^2 )≤ _d2T^2, where the second term is omitted when ε¯y=0 _y=0. If the actual test is reached, its trajectory agrees with the alarm-suppressed continuation through that test. The bound therefore controls the joint event that the reference succeeds, the test is reached with the stated null history, and the threshold is crossed. It does not condition on survival to the test. Before the first detector failure, every false-alarm candidate has such an unchanged null history. After a change, any earlier crossing of either test completes detection. Otherwise, the absence of a boundary crossing bounds the old ideal action’s saturation deficit by 2ζH2 _H and the applied-action error by ε¯u _u. Lemma 27 then compares each output in the complete post-change block with its h_ U-step auxiliary. These auxiliaries are defined on the full alarm-suppressed continuation, so Lemma 14 applies without conditioning on survival of either test. The event inclusion in Lemma 28 gives a composite alarm by τ+Dτ+D_ U except with conditional probability δd/(4T2) _d/(4T^2) on each eligible ℱτF_τ history. The null bounds are unioned over at most T2T^2 restart–endpoint pairs. At a fixed true change, the successful-history active-cycle events are disjoint ℱτF_τ-measurable subsets of the corresponding r,τA_r,τ. Multiplying the conditional missed-detection bound by these indicators and summing over r costs at most δd/(4T2) _d/(4T^2) for that change. The chronological induction in Theorem 18 and Appendix I therefore applies with total detector failure probability at most δd _d; boundary crossings add no null failure probability on successful-reference histories. Controller failures cost at most 3(T+1)δ03(T+1) _0, so the allocation in (48) is below δ. The delay intervals cost at most CKDDCK_DD_ U, exploration costs at most (C+1)KXH(C+1)K_XH, and unchanged exploitation prefixes cost at most (C+1)RE(T,δ0)(C+1)R_E(T, _0). This proves (155)–(156). It remains to check the order. Because ε¯u=7LλBψEθ(H,δ0) _u=7L_λB_ψE_θ(H, _0) and ε¯y=7b¯LλBψEθ(H,δ0) _y=7 bL_λB_ψE_θ(H, _0), the detector conditions follow from Eθ(H,δ0)≤ϵuni:=min E_θ(H, _0)≤ _ U uni:= \ bmin16,Δ¯/87b¯LλBψ,B7b¯LλBψ, b_ 16, _ U/87 bL_λB_ψ, B_ U7 bL_λB_ψ, Δ¯112BLu,LλBψ, _ U112B_ UL_u, UL_λB_ψ \, (158) Omit the last entry when Lu,=0L_u, U=0. Appendix J and (143) then prove (157). ∎

Instant research discovery