Online Bandit Nonlinear Control with Dynamic Batch Length and Adaptive Learning Rate

## Abstract

Abstract This paper is concerned with the online bandit nonlinear control, which aims to learn the best stabilizing controller from a pool of stabilizing and destabilizing controllers of unknown types for a given nonlinear dynamical system. We develop an algorithm, named D ynamic B atch length and A daptive learning R ate (DBAR), and study its stability and regret. Unlike the existing Exp3 algorithm requiring an exponentially stabilizing controller, DBAR only needs a significantly weaker notion of controller stability, in which case substantial time may be required to certify the system stability. Dynamic batch length in DBAR effectively addresses this issue and enables the system to attain asymptotic stability, where the algorithm behaves as if there were no destabilizing controllers. Moreover, adaptive learning rate in DBAR only uses the state norm information to achieve a tight regret bound even when none of the stabilizing controllers in the pool are exponentially stabilizing.

## 1 Introduction

The multi-armed bandit (MAB) problem aims to minimize the total cost of pulling a series of arms while receiving immediate cost feedback for each arm pulled. Given a finite number of arms, the problem balances between exploration and exploitation of arms without knowing the exact cost structure of each arm. On the other hand, the online optimal control problem considers a transition dynamic $x_{t+1}=f(x_{t},u_{t},w_{t})$ and a set of cost functions $c_{t}(x_{t},u_{t}),~{}t=0,\dots,T$, where the goal is to minimize the sum of costs over time, while both $f$ and $c_{t}$ are fully or partially unknown.
Basically, MAB is a special type of the online optimal control problem in the sense that MAB is stateless and simply selects an action each time, while the online control problem has a countable or an uncountable number of states and selects a controller, acting as a function from states into actions, each time without knowing the cost functions.
Bandit algorithms can thus be leveraged for online control, wherein the average cost incurred with a controller can be interpreted as the bandit feedback of pulling the controller-arm (Lin et al. (); Li et al. ()).

In this paper, we address the online nonstochastic control problem where both a transition dynamic $f$ and cost functions $c_{t}$ can be unbounded, nonlinear, and adversarially chosen. We only have knowledge about $x_{t}$ and the bandit feedback $c_{t}(x_{t},u_{t})$ at time $t$, with adversarial disturbances $w_{t}$ injected at each time step as in Gradu et al. () and Cassel & Koren ().
We operate the system with a single trajectory where the system state cannot be reset.
To overcome the difficulties of an unknown nonlinear system, we are given a finite set of $N$ controllers in advance, where we are not aware of whether each controller can stabilize the system but we are allowed to alternate between these controllers within a single trajectory according to a specific logic.
We refer to this problem as the online bandit nonlinear control problem.

To deal with this online bandit nonlinear control, Li et al. ()
adopted their Exp3-ISS algorithm, which uses the well-known Exp3 algorithm (Auer et al. ()) with a mini-batch approach (Arora et al. ()), while successively removing destabilizing controllers when detected in terms of input-to-state stability (ISS).
In this paper, we aim to significantly relax the requirement on the controllers and yet guarantee asymptotic stability of the closed-loop system and sharpen the regret bound
by designing our algorithm DBAR (Dynamic Batch length and Adaptive learning Rate).

Motivation and contribution. Our main contribution is to allow a broader class of controllers to qualify as a stabilizing controller within a priori controller pool. For the motivation, consider a continuous-time gradient flow in the vector space:

$$ $\displaystyle\dot{x}(t)=-\nabla F(x(t)),$ (1) $$

where $F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a smooth function. A merely convex $F$ can be extremely flat around its minimum, leading to a slowly (asymptotically) converging trajectory unlike
exponentially converging behavior achieved for strongly convex $F$ (Khalil ()). In fact, assuming that a minimizer $x^{\ast}$ of $F$ exists, the decay rate $F(x(t))-F(x^{\ast})$ is $O(1/(t\log^{2}t))$ if $F$ is convex(^1^11Note that $O(1/(t\log^{2}t))$ is integrable at infinity. In the context of controllers, we also handle the challenging case where $f(x_{t},\pi(x_{t}),w_{t})-\inf_{x\in\mathbb{R}^{n}}f(x,\pi(x),w_{t})$ may not be integrable at infinity. This corresponds to a convex function without minimizers, such as a log-exp-type softmax loss function for classification.) (Siegel & Wojtowytsch ()), and $O(e^{-t})$ if $F$ is strongly convex.
In the machine learning literature, a loss function $l(g(x),y)$ of a gradient-based method is often given as a convex function in $g$ (e.g., mean-squared error or cross-entropy loss), but not necessarily strongly convex since $g$ is often over-parameterized and there could be a continuum of parameters corresponding to the value of $g$. Analogous to this concept, one can consider $F$ as $f(x_{t},\pi(x_{t}),w_{t})$, a dynamic governed by a given controller $\pi$ and its converging behavior as a (asymptotic or exponential) controller stability. Our work merely requires the existence of at least one asymptotically stabilizing controller in the pool, which is far weaker than exponentially stabilizing notions and represents a more realistic environment one may encounter.

The existing literature on online bandit control of linear dynamics with adversarial disturbance has intrinsically assumed the existence of strongly stable controllers, which are exponentially stabilizing controllers in our context, and achieves $\tilde{O}(T^{2/3})$ regret under general convex cost functions (Cassel & Koren (); Chen & Hazan (); Ghai et al. ()). In this paper, we will achieve the same $\tilde{O}(T^{2/3})$ regret bound even when none of the stabilizing controllers are exponentially stabilizing.

Algorithm Design. The idea of our algorithm is two-fold:

1. We adopt a dynamic batch length instead of a fixed length to certify the stability of the system without requiring exponentially stabilizing controllers and achieve both asymptotic and finite-gain stability. The batch length is scheduled to be non-decreasing and growing unboundedly over time. However, the strategy suffers from a resulting multiplicative exponential regret in return.

2. To alleviate the multiplicative exponential regret without requiring the conservative notion of exponentially stabilizing controllers, we adopt a novel adaptive learning rate scheme that relies on the system state norm, instead of a fixed learning rate. While the conventional way to apply the Exp3 Algorithm is to use a non-increasing learning rate, we decrease the learning rate if the state is unstable and subsequently increase the learning rate if the state returns to a stable region. By implementing this approach, we can alleviate the multiplicative term $\tilde{O}(T^{1/3})\cdot\exp(O(|\mathcal{U}|))$ created by using a dynamic batch length and attain a regret bound order $[\tilde{O}(T^{2/3})+\tilde{O}(T^{-1/3})\cdot\exp(O(|\mathcal{U}|))]\cdot(|\mathcal{U}|+1)^{\alpha}$, where $\alpha=1/3$ if $|\mathcal{U}|$ is known and $\alpha=1/2$ if $|\mathcal{U}|$ is unknown.

Table [1](#S1.T1) shows a summary of our results with related works. Appendix [A](#A1) provides more details on the intermediate step "Dynamic Batching", which operates under asymptotically stabilizing controller assumptions, and on how we devised DBAR algorithm to avoid the multiplicative exponential term.

**Table 1: Summary of required controllers and results: Polynomial factors on $N$ and $|\mathcal{U}|$ are hidden.**
| Algorithm | Required | Closed-loop system | Regret Bound |
| --- | --- | --- | --- |
| Controller | asymptotic stability |  |  |
| Chen & Hazan () | Exponential | N/A | $\tilde{O}(T^{2/3})+\exp(O(|\mathcal{U}|))$ |
| Li et al. () | Exponential | No | $\tilde{O}(T^{2/3})+\exp(O(|\mathcal{U}|))$ |
| Dynamic Batching | Asymptotic | Yes | $\tilde{O}(T^{2/3})+o(T^{1/3})\cdot\exp(O(|\mathcal{U}|))$ |
| Algorithm [1](#alg1) (DBAR) | Asymptotic | Yes | $\tilde{O}(T^{2/3})+\tilde{O}(T^{-1/3})\cdot\exp(O(|\mathcal{U}|))$ |

Related works. Optimal control problems have been widely leveraged in a variety of fields with the influential dynamic programming approach (Bellman ()). Recent successes of reinforcement learning (RL) in safety-critical systems, such as aircraft (Razzaghi et al. ()), robotics (Ibarz et al. ()), and autonomous driving (Kiran et al. ()), are also deeply rooted in optimal control methods (Bertsekas ()).
The common idea to gain system stability of optimal control problems is to falsify the detected destabilizing controller, meaning that one can completely remove those controllers failing to satisfy certain stability criteria from the controller pool (Baldi et al. (); Battistelli et al. (; ; ); Stefanovic & Safonov (); Li et al. ()).

Online nonstochastic control considers a dynamical system with adversarial disturbances, which is more challenging than having statistical noise. Early papers assumed full access to cost functions, enabling us to leverage optimal policy structure with cost function gradients (Agarwal et al. (); Foster & Simchowitz (); Hazan et al. (); Hazan & Singh ()).
Later, studies were generalized to address the problem without cost gradients information (Gradu et al. (); Cassel & Koren (); Ghai et al. (); Sun et al. ()); instead, they estimated the cost gradients, using the history of scalar cost (bandit feedback) along the trajectory.
However, the above research restricts the system to linear transition dynamics. Instead, our work considers the candidate controller pool to handle unknown nonlinear systems.

Multi-armed bandits with adversarial disturbances were first addressed in the pioneering work by Auer et al. () under bounded costs in their notable Exp3 algorithm. Arora et al. () later improved the algorithm using the same controller within a mini-batch, attaining a regret bound equivalent to the lower bound presented in Dekel et al. (). As we have access to the candidate controller pool in our problem setting, we adopt a bandit-related approach.

Dynamic batching gained considerable attention for training deep neural networks by increasing the batch size over time and adaptively increasing the learning rate to maintain the ratio between the two (Devarakonda et al. (); Bollapragada et al. (); Shallue et al. (); Ma et al. ()). Although this has been widely used in the machine learning literature, we adopt this idea to our online control problem, progressively increasing the batch length within a single trajectory to achieve asymptotic stability.

Adaptive learning rate in machine learning is generally determined by a set of gradients observed so far (Ruder ()). As we do not have access to the gradients in our problem, we focus on the learning rate for bandit algorithms.
Recently, it was shown in Aubert et al. () that two different constant learning rates for bandits cannot be distinguished in the learning process, thus they emphasized the necessity of using a polynomially decreasing learning rate.
Several works (van Erven et al. (); de Rooij et al. ()) also suggested using decreasing learning rate as the batch length increases.
Building on this idea, Li et al. () proposed to use a non-increasing learning rate over time, while no theoretical guarantee was presented. To the best of our knowledge, this paper is the first work to provide theoretical guarantees for the adaptive learning rate scheme based on the stability of state norm, where the rate is not necessarily non-increasing.

Outline. The paper is organized as follows. In Section [2](#S2), we formulate the problem and provide necessary definitions and assumptions. In Section [3](#S3), we propose our DBAR algorithm. In Section [4](#S4), we study the stability of the algorithm, the regret bound, and its applications in switched systems. In Section [5](#S5), we present numerical experiments on the DBAR algorithm with an ablation study on batch length and learning rate. Finally, concluding remarks are provided in Section [6](#S6).

Notation. For a vector $z$, $\|z\|$ denotes the Euclidean norm of the vector. We use $O(\cdot)$ for the big-O notation, $o(\cdot)$ for the small-o notation, and $\tilde{O}(\cdot)$ for the big-O notation hiding logarithmic factors. Let $\mathbb{E}$ denote the expectation operator. For a set $Z$, we use $|Z|$ for the cardinality and $Z^{c}$ for the complement of the set $Z$. For a real number $e$, we use $\lfloor e\rfloor$ for the floor and $\lceil e\rceil$ for the ceiling of $e$. Let $\mathbb{R}$ denote the set of real numbers and $\mathbb{Z}_{+}$ denote the set of nonnegative integers. For $e_{1},e_{2}\in\mathbb{Z}_{+}$ where $e_{2}\leq e_{1}$, let $i_{e_{1}:e_{2}}$ denote the set $\{i_{e}:e_{2}\leq e\leq e_{1},e\in\mathbb{Z}_{+}\}$.

## 2 Problem Formulation

Consider a general discrete-time dynamical system $x_{t+1}=f(x_{t},u_{t},w_{t}),~{}t=0,\dots,T-1$, where $x_{t}\in\mathbb{R}^{n}$ is the system state at time $t$, $u_{t}\in\mathbb{R}^{m}$ is the control input at time $t$ to be designed via an algorithm. $u_{t}$ is determined by selecting a controller from a priori finite number of controller pool consisting of $\pi_{i}:\mathbb{R}^{n}\to\mathbb{R}^{m},~{}i=1,\dots,N$. $w_{t}\in\mathcal{W}\subset\mathbb{R}^{g}$ is the adversarial noise at time $t$, where
$\mathcal{W}=\{w\in\mathbb{R}^{g}:\|w\|\leq w_{\text{max}}\}$ and the bounding constant $w_{\text{max}}>0$ is assumed to be known.
Each time instance $t$ is associated with a cost function $c_{t}:\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}$. The state transition is governed by the dynamic $f:\mathbb{R}^{n}\times\mathbb{R}^{m}\times\mathbb{R}^{g}\to\mathbb{R}$. We have the following assumptions on the dynamic $f$.

###### Assumption 2.1 (Dynamic) .

The transition dynamic $f$ is $L_{f}$-Lipschitz continuous with $L_{f}\geq 1$; i.e., $|f(x,u,w)-f(\tilde{x},\tilde{u},\tilde{w})|\leq L_{f}(\|x-\tilde{x}\|+\|u-\tilde{u}\|+\|w-\tilde{w}\|)$ for all $x,\tilde{x}\in\mathbb{R}^{n}$, $u,\tilde{u}\in\mathbb{R}^{m}$, $w,\tilde{w}\in\mathcal{W}$.
We let $f(0,0,0)=f_{0}$.

We adopt the notion of locally Lipschitz continuous cost functions $c_{t}$ given in Li et al. (), which contains quadratic tracking costs along an arbitrary bounded state trajectory and action sequence.

###### Assumption 2.2 (Cost functions) .

There exist $L_{c1},L_{c2}>0$ such that $|c_{t}(x,u)-c_{t}(\tilde{x},\tilde{u})|\leq(L_{c1}(\max\{\|x\|,\|\tilde{x}\|\}+\max\{\|u\|,\|\tilde{u}\|\})+L_{c2})(\|x-\tilde{x}\|+\|u-\tilde{u}\|)$ for all $x,\tilde{x}\in\mathbb{R}^{n},u,\tilde{u}\in\mathbb{R}^{m},t\in\mathbb{Z}_{+}$. There exists $c_{0,\text{max}}\geq 0$ such that $|c_{t}(0,0)|\leq c_{0,\text{max}}$ for all $t\in\mathbb{Z}_{+}$.

Input-to-state (asymptotic) stability (ISS) is a classic notion of stability implying that the controller successfully stabilizes the system under any bounded noises (Sontag (); Khalil ()). Incremental (asymptotic) stability extends the input-to-state stability to describe the asymptotic behavior of some trajectory towards a different trajectory (Tran et al. ()). It is worth noting that Li et al. () also adopted these concepts under an exponential stability assumption; i.e., they require some controllers to satisfy exponential ISS and exponential incremental stability. However, in practice, general asymptotic concepts need to be considered for stabilizing controllers. We will address this controller stability issue below.

###### Definition 2.3 (Input-to-state stable controller) .

A controller $\pi$ is (asymptotically) input-to-state stable (ISS) if there exists a non-increasing function $\beta(\cdot):\mathbb{Z}_{+}\to\mathbb{R}$ that satisfies $\beta(0)=1$(^2^22This assumption in Definitions [2.3](#S2.Thmtheorem3) and [2.4](#S2.Thmtheorem4) is to guarantee $\beta(t)^{2}\leq\beta(t)$ for all $t$, which can be overcome by a large $\gamma$. If we relax Assumption [2.2](#S2.Thmtheorem2) on $c_{t}$ to be Lipschitz continuous, we can remove the assumption $\beta(0)=1$.) with $\lim_{t\to\infty}\beta(t)=0$ and $\gamma>0$ such that for any $x_{0}\in\mathbb{R}^{n}$ and $\|w_{t}\|\leq w_{\text{max}}$ for all $t\geq 0$, the sequence $\{x_{t}\}_{t\geq 0}$ determined by $x_{t+1}=f(x_{t},\pi(x_{t}),w_{t})$ satisfies $\|x_{t}\|\leq\beta(t)\|x_{0}\|+\gamma w_{\text{max}}$.

###### Definition 2.4 (Incrementally stable controller) .

A controller $\pi$ is (asymptotically) incrementally stable if there exists a non-increasing function $\beta(\cdot):\mathbb{Z}_{+}\to\mathbb{R}$ that satisfies $\beta(0)=1$ with $\lim_{t\to\infty}\beta(t)=0$ such that for any $x_{0},\tilde{x}_{0}\in\mathbb{R}^{n}$ and $\|w_{t}\|\leq w_{\text{max}}$ for all $t\geq 0$, it holds that $\|x_{t}-\tilde{x}_{t}\|\leq\beta(t)\|x_{0}-\tilde{x}_{0}\|$ for any two sequences determined by $x_{t+1}=f(x_{t},\pi(x_{t}),w_{t})$ and $\tilde{x}_{t+1}=f(\tilde{x}_{t},\pi(\tilde{x}_{t}),w_{t})$.

###### Assumption 2.5 (Controller pool) .

Consider the candidate controller index set $\mathcal{P}_{0}=\{1,\dots,N\}$, in which there exists a controller satisfying Definitions [2.3](#S2.Thmtheorem3) and [2.4](#S2.Thmtheorem4). There exists $\pi_{0,\text{max}}\geq 0$ such that $\|\pi_{i}(0)\|\leq\pi_{0,\text{max}}$ for all $i\in\mathcal{P}_{0}$. All candidate controllers are $L_{\pi}$-Lipschitz continuous; i.e., $\|\pi_{i}(x)-\pi_{i}(\tilde{x})\|\leq L_{\pi}\|x-\tilde{x}\|$ for all $x,\tilde{x}\in\mathbb{R}^{n}$ and $i\in\mathcal{P}_{0}$.

###### Definition 2.6 (Stabilizing and destabilizing controller) .

Let $\mathcal{S}$ denote an index set of stabilizing controllers that satisfy both of Definitions [2.3](#S2.Thmtheorem3) and [2.4](#S2.Thmtheorem4). We also let $\mathcal{U}$ denote an index set of destabilizing controllers that do not satisfy Definition [2.3](#S2.Thmtheorem3). Thus, we have $|\mathcal{S}|\geq 1$ and $\mathcal{S}\subseteq\mathcal{U}^{c}$.

###### Remark 2.7 .

Definition [2.4](#S2.Thmtheorem4) is a stronger notion than Definition [2.3](#S2.Thmtheorem3) due to the triangle inequality. However, for a special case of linear systems with additive noise; i.e., $f(x_{t},\pi(x_{t}),w_{t})=Ax_{t}+h(w_{t})$, where $A\in\mathbb{R}^{n\times n}$ and $h:\mathbb{R}^{g}\to\mathbb{R}^{n}$, a controller $\pi$ satisfying Definition [2.3](#S2.Thmtheorem3) also satisfies Definition [2.4](#S2.Thmtheorem4). In such a case, Assumption [2.5](#S2.Thmtheorem5) boils down to requiring at least one ISS controller in the pool.

Now, we define different notions of closed-loop system stability with bounded adversarial disturbances $w_{t}$, where $\|w_{t}\|\leq w_{\text{max}}$ holds.
Asymptotic stability and finite-gain stability both shed light on the connection between the disturbance input and the state output, where none of them implies the other (Hill & Moylan ()). Hence, it is desirable to achieve both system stability notions.

###### Definition 2.8 (Asymptotic stability) .

A system is asymptotically stable if the sum of state norms satisfies $\lim_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T}\|x_{t}\|\leq\gamma w_{\text{max}}$.

###### Definition 2.9 (Finite-gain stability) .

A system is finite-gain $\mathcal{L}_{1}$ stable if there exist constants $A_{1},A_{2}>0$ such that for all $T\in\mathbb{Z}_{+}$, it holds that $\sum_{t=0}^{T}\|x_{t}\|\leq A_{1}\cdot w_{\text{max}}T+A_{2}$.

Recall that $x_{t}$ and $u_{t}$ denote the state and action sequence for the system according to the algorithm. We also let $x_{t}^{*}$ and $u_{t}^{*}$ denote the optimal state and action sequence generated by the best stabilizing controller $i^{*}$ that satisfies both of Definitions [2.3](#S2.Thmtheorem3) and [2.4](#S2.Thmtheorem4); i.e., $i^{*}=\arg\min_{i\in\mathcal{S}}\mathbb{E}[\sum_{t=0}^{T}c_{t}(x_{t},\pi_{i}(x_{t}))]$ subject to the dynamic $f$. Then, the regret of the algorithm is defined as follows.

###### Definition 2.10 (Regret) .

The regret of the algorithm implementing the policy $\pi_{i_{t}}$ at time $t=0,\dots,T-1$ is defined as $\textit{Regret}_{T}=\mathbb{E}_{i_{T-1:0}}\sum_{t=0}^{T}[c_{t}(x_{t},u_{t})-c_{t}(x_{t}^{*},u_{t}^{*})]$.

###### Assumption 2.1 (Dynamic) .

###### Assumption 2.2 (Cost functions) .

###### Definition 2.3 (Input-to-state stable controller) .

###### Definition 2.4 (Incrementally stable controller) .

###### Assumption 2.5 (Controller pool) .

###### Definition 2.6 (Stabilizing and destabilizing controller) .

###### Remark 2.7 .

###### Definition 2.8 (Asymptotic stability) .

###### Definition 2.9 (Finite-gain stability) .

###### Definition 2.10 (Regret) .

## 3 Algorithm Description

Denote the number of batches in the algorithm by $B$. Denote by $t_{b}$ the start time for each batch $b=0,1,\dots,B-1$. We implement the same policy within the mini-batch.

###### Assumption 3.1 (Dynamic batch length) .

We design our batch length $(\tau_{b})_{b\geq 0}$ as follows:

1. $\tau_{b}$ is non-decreasing in $b$ and $\lim_{b\to\infty}\tau_{b}=+\infty$.

2. $\max_{b\geq 0}\frac{\tau_{b+1}}{\tau_{b}}=\frac{\tau_{1}}{\tau_{0}}$ and $\lim_{b\to\infty}\frac{\tau_{b+1}}{\tau_{b}}=1$.

For example, $\tau_{0}=\lfloor z_{1}(z_{2})^{z_{3}}\rfloor>0$ and $\tau_{b}=\lceil z_{1}(\nu b+z_{2})^{z_{3}}\rceil$ for every $b\geq 1$ with the constants $z_{1},z_{2},z_{3},\nu>0$ satisfy Assumption [3.1](#S3.Thmtheorem1). For future use, we refer to this type of formulation as polynomial batches with $(z_{1},z_{2},z_{3},\nu)$.

###### Remark 3.2 .

As our dynamic batch length eventually grows unboundedly over time, excessively strict controller stability criteria may result in most of the candidate controllers violating these criteria. Thus, it is crucial to adopt (asymptotic) ISS and incremental stability as our criteria, instead of exponential notions in Li et al. () and the literature on linear dynamics (Cassel & Koren (); Chen & Hazan (); Ghai et al. ()). Moreover, our design only requires $\max_{b\geq 0}\frac{\tau_{b+1}}{\tau_{b}}=\frac{\tau_{1}}{\tau_{0}}$, and thus one can adjust $\frac{\tau_{b+1}}{\tau_{b}}$ in a more flexible manner after the first two batches. Figure [3](#A1.F3) in Appendix [A](#A1) strongly supports the necessity of a dynamic batch length regardless of the noise assumption.

We propose our DBAR algorithm in Algorithm [1](#alg1) (see Appendix [B](#A2) for the notations). Lines [3](#alg1.l3)-[9](#alg1.l9) generate the state trajectory based on the selected controller $\pi_{K_{b}}$ for the current batch $b$, and falsify the controller if it is found to violate Definition [2.3](#S2.Thmtheorem3); i.e., $K_{b}\in\mathcal{U}$.
Here, let $U$ denote the number of times that the Break statement in Line [7](#alg1.l7) is activated.
In the rest of the paper, when we say the Break statement is activated, it means that Line [7](#alg1.l7) of Algorithm [1](#alg1) has been activated. As the controllers in $\mathcal{U}^{c}$ do not suffer from the Break statement, they always remain in the controller pool.
Accordingly, we have $U\leq|\mathcal{U}|$.

Lines [11](#alg1.l11)-[20](#alg1.l20) keep track of the state norm of $x_{b+1}$ by determining $\alpha_{b+1}$ and $s_{b+1}$ that indicates the magnitude of the next batch’s initial state norm compared to $\|x_{0}\|$.
Note that we keep adjusting the value of $\alpha_{b+1}$ to avoid $s_{b+1}>s_{b}+1$ (Line [14](#alg1.l14)), and the adjusted $\alpha_{b+1}$ is guaranteed to be bounded by some constant
(see Lemma [C.5](#A3.Thmtheorem5) in the Appendix). It is later discussed formally in Lemma [4.7](#S4.Thmtheorem7) that these observations cause $s_{b}\neq 0$ to occur at most $O(U)$ times throughout the algorithm.

Figure: Algorithm 1 DBAR

Lines [21](#alg1.l21)-[26](#alg1.l26) determine the weight $W_{b+1}(k)$ for each controller $k$. In Line [21](#alg1.l21),
we use the sum of costs at the current batch $b$
to add up to the weight in Line [25](#alg1.l25). In Lines [22](#alg1.l22)-[26](#alg1.l26), we reset the weight if $s_{b+1}\neq s_{b}$. This resetting weight idea to forget the costs in the past is also proposed in van Erven et al. (). In the scenario that the Lipschitz constant $L_{f}$ is very large, it may help to forget the time-varying costs $c_{0},\dots,c_{t-1}$ and restart gathering the information from the outset. Line [22](#alg1.l22) reflects this case where the next batch’s state norm significantly deviates from the current state norm.

Lines [27](#alg1.l27)-[29](#alg1.l29) calculate the adaptive learning rate $\eta_{b+1}$ for the next batch $b+1$ used to apply the Exp3 algorithm to our problem. It indicates that the learning rate decreases in unstable states and increases back to the initial value when the state norm returns to a stable region. Thus, the learning rate fluctuates depending on the state norm. However, it is essential to note that the effective learning rate, determined by the ratio $\frac{\eta_{b}}{\tau_{b}}$, indeed decreases as the batch length increases even if $s_{b+1}=s_{b}$. The only plausible situation in which the effective rate may increase is $s_{b+1}<s_{b}$ with $(\alpha_{b+1})^{2}>\frac{\tau_{b+1}}{\tau_{b}}$. Apart from this scenario, the effective learning rate experiences a polynomial decay with polynomial batches defined in Assumption [3.1](#S3.Thmtheorem1), which does not cause any contradiction with the polynomially decreasing learning rate concept proposed in Aubert et al. ().

Our adaptive learning rate stabilizes the cost of current batch, which can be unbounded with a dynamic batch length. This alleviates the multiplicative exponential term
in the regret bound (see Table [1](#S1.T1)). Moreover, since we run the algorithm along a single trajectory with the selection of the policy only relying on the state norm as a context, we obtain a linear-time algorithm by harnessing a form of contextual bandit without requiring strict assumptions.

###### Assumption 3.1 (Dynamic batch length) .

###### Remark 3.2 .

## 4 Main Results

### 4.1 Stability

In Algorithm [1](#alg1), we define $H(t):=\sum_{i=0}^{t-1}\beta(i)$, which determines the scope of stabilizing controllers throughout the entire horizon. In this section, we will present the stability results of Algorithm [1](#alg1), which deeply hinge on Lemma [4.3](#S4.Thmtheorem3).

###### Theorem 4.1 (Asymptotic stability) .

In Algorithm [1](#alg1), suppose that $\frac{\tau_{1}}{\tau_{0}}\beta(\tau_{0})<1$. Then, it holds that

$\lim_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T}\|x_{t}\|\leq\gamma w_{\text{max}}.$

###### Theorem 4.2 (Finite-gain stability) .

In Algorithm [1](#alg1), suppose that $\frac{\tau_{1}}{\tau_{0}}\beta(\tau_{0})<1$. Assume that $\lim_{t\to\infty}H(t)<\infty$. Then, Algorithm [1](#alg1) achieves finite-gain $\mathcal{L}_{1}$ stability; i.e., there exist constants $A_{1},A_{2}>0$ such that for all $T\in\mathbb{Z}_{+}$,

$\sum_{t=0}^{T}\|x_{t}\|\leq A_{1}\cdot w_{\text{max}}T+A_{2}.$

###### Lemma 4.3 .

Define $H(t):=\sum_{i=0}^{t-1}\beta(i)$. Then, we have
$\lim_{t\to\infty}\frac{H(t)}{t}=0.$

###### Proof.

If $\lim_{t\to\infty}H(t)<\infty$, clearly $\lim_{t\to\infty}\frac{H(t)}{t}=0$ holds. If $\lim_{t\to\infty}H(t)=\infty$, we leverage L’Hôpital’s rule with $\beta(t)\to 0$ as $t\to\infty$ to derive

$$ $\displaystyle\lim_{t\to\infty}\frac{H(t)}{t}$ $\displaystyle\leq\lim_{t\to\infty}\frac{\beta(0)+\int_{0}^{t-1}\beta(x)dx}{t}=\lim_{t\to\infty}\frac{\beta(t-1)}{1}=0,$ $$

where the first inequality is due to designing $\beta(\cdot)$ to be non-increasing and nonnegative.
The proof details can be found in the Appendix (see Lemma [C.1](#A3.Thmtheorem1)).
∎

Proof sketch of Theorems [4.1](#S4.Thmtheorem1) and [4.2](#S4.Thmtheorem2):
By Lemma [4.3](#S4.Thmtheorem3), we have $\lim_{t\to\infty}\frac{H(t)}{t}=0$. Using this result with the non-decreasing property of both $\tau_{b}$ and $H(\tau_{b})$, we obtain that
$\sum_{b=0}^{B-1}H(\tau_{b})=o(T)$
according to Assumption [3.1](#S3.Thmtheorem1) for the dynamic batch length. This assumption further indicates that falsifying destabilizing controllers in Lines [5](#alg1.l5)-[8](#alg1.l8) results in the existence of a constant $M>0$ such that the following inequality holds for all $T\geq 0$:

$$ $\displaystyle\sum_{t=0}^{T}\|x_{t}\|$ $\displaystyle\leq M+\gamma w_{\text{max}}\cdot(O(\sum_{b=0}^{B-1}H(\tau_{b}))+T).$ (2) $$

Thus, $\sum_{b=0}^{B-1}H(\tau_{b})=o(T)$ along with ([2](#S4.E2)) proves both Theorems [4.1](#S4.Thmtheorem1) and [4.2](#S4.Thmtheorem2). More details about the proof are provided in Appendix [C](#A3). ∎

###### Remark 4.4 .

With a fixed batch length $\tau$ as presented in Li et al. (), the resulting closed-loop system cannot achieve asymptotic stability since $\lim_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T}\|x_{t}\|=\gamma w_{\text{max}}(1+O(\frac{1}{\tau}))>\gamma w_{\text{max}}$. Thus, it is intuitively desirable to design as $\lim_{b\to\infty}\tau_{b}=\infty$ to achieve an asymptotic system stability, validating our dynamic batch length strategy in Algorithm [1](#alg1).
This idea also results in having $\lim_{T\to\infty}B/T=0$ (see Lemma [C.9](#A3.Thmtheorem9) in the Appendix). It is crucial to note that we have achieved asymptotic stability even when $\lim_{t\to\infty}H(t)=\infty$. In addition, finite-gain stability can be achieved for every $\beta(\cdot)$ that satisfies $H(\cdot)<\infty$, which incorporates exponentially stabilizing controllers.

###### Theorem 4.1 (Asymptotic stability) .

###### Theorem 4.2 (Finite-gain stability) .

###### Lemma 4.3 .

###### Proof.

###### Remark 4.4 .

### 4.2 Regret

In this section, we will present the regret bound of Algorithm [1](#alg1), where the regret defined in Definition [2.10](#S2.Thmtheorem10) is equivalent to
$\mathbb{E}_{K_{B-1:0}}\sum_{t=0}^{T}[c_{t}(x_{t},u_{t})-c_{t}(x_{t}^{*},u_{t}^{*})],$
considering that the policy at each time $t$ is determined by the policy at the corresponding batch.

###### Theorem 4.5 (Regret Bound) .

In Algorithm [1](#alg1), suppose that $\frac{\tau_{1}}{\tau_{0}}(\beta(\tau_{0}))^{2}<\frac{1}{2\sqrt{2}}$. Then, we have

$$ $\displaystyle\textit{Regret}_{T}=O(|\mathcal{U}|)+O(\sum_{b=0}^{B-1}H(\tau_{b}))+\frac{\tilde{O}(|\mathcal{U}|+1)}{\eta_{0}}+\frac{\eta_{0}N}{2}[\exp(O(|\mathcal{U}|))O(\tau_{B-1}H(\tau_{B-1}))+O(\sum_{b=0}^{B-1}(\tau_{b})^{2})].$ $$

###### Theorem 4.6 (Regret bound with known $|\mathcal{U}|$ ) .

Consider Algorithm [1](#alg1) with
polynomial batches defined in Assumption [3.1](#S3.Thmtheorem1) with $(\frac{1}{(N(|\mathcal{U}|+1))^{1/2}},z,\frac{1}{2},\nu)$, where the constants $z,\nu>0$ satisfy $\tau_{0}>0$ and $\frac{\tau_{1}}{\tau_{0}}(\beta(\tau_{0}))^{2}<\frac{1}{2\sqrt{2}}$. Then, with $\eta_{0}=O(\frac{(|\mathcal{U}|+1)^{2/3}}{T^{2/3}N^{1/3}})$ and $T\geq\max\{\frac{|\mathcal{U}|^{3/2}}{(N(|\mathcal{U}|+1))^{1/2}},N(|\mathcal{U}|+1)\}$, we achieve a sublinear regret bound.
Moreover(^3^33Among stabilizing controllers achieving $\tilde{O}(T^{2/3})$ regret bound, we also cover the case where $H(t)$ can be of the order of a harmonic series that is not summable at infinity.), when $H(t)\leq O(\sum_{i=1}^{t}\frac{1}{i})$ for all $t\geq 1$, we have

$$ $\textit{Regret}_{T}=\bigr{[}\tilde{O}(T^{2/3})+\tilde{O}(T^{-1/3})\exp(O(|\mathcal{U}|))\bigr{]}N^{1/3}(|\mathcal{U}|+1)^{1/3}.$ $$

The regret bound deeply relies on Lemma [4.7](#S4.Thmtheorem7). For the lemma, define $\mathcal{L}:=\{0\leq b\leq B-1,~{}b\in\mathbb{Z}_{+}:s_{b+1}\neq s_{b}\}$ and
let $b^{1},\dots,b^{|\mathcal{L}|}$ denote the batch where Line [22](#alg1.l22) is satisfied; i.e., $s_{b^{l}+1}\neq s_{b^{l}}$ for $l=1,\dots,|\mathcal{L}|$. For convenience, we let $b^{0}=0$, $b^{|\mathcal{L}|+1}=B-1,$ and $s_{B}=s_{B-1}$.
Also, define $\mathcal{V}:=\{0\leq b\leq B-1,~{}b\in\mathbb{Z}_{+}:s_{b}\neq 0\}$.

###### Lemma 4.7 .

In Algorithm [1](#alg1), suppose that $\beta(\tau_{0})<1$ and let $U$ denote the number of times that the Break statement is activated. Then, it holds that $|\mathcal{L}|=O(U)$ and $|\mathcal{V}|=O(U)$.

###### Proof.

For every batch $b=0,\dots,B-1$, we have

$$ $\displaystyle\|x_{t_{b}}\|<(\alpha_{b})^{s_{b}+1}\|x_{0}\|+\delta$ (3) $$

by Lines [11](#alg1.l11)-[20](#alg1.l20). If the Break statement is not activated, since we designed $\delta\geq\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{0})}$, it yields that

$$ $\displaystyle\|x_{t_{b+1}}\|$ $\displaystyle\leq\beta(\tau_{b})\|x_{t_{b}}\|+\gamma w_{\text{max}}\leq\beta(\tau_{0})(\alpha_{b})^{s_{b}+1}\|x_{0}\|+\beta(\tau_{0})\delta+\gamma w_{\text{max}}$ $\displaystyle\leq\beta(\tau_{0})(\alpha_{b})^{s_{b}+1}\|x_{0}\|+\delta<(\alpha_{b})^{s_{b}+1}\|x_{0}\|+\delta,$ $$

which implies that $s_{b+1}>s_{b}$ cannot occur when the Break statement is not activated. As a result, starting from $s_{0}=0$, the event $s_{b+1}=s_{b}+1$ can occur at most $U$ times. Also, since Line [14](#alg1.l14) avoids $s_{b+1}>s_{b}+1$, the event $s_{b+1}<s_{b}$ can occur at most $U$ times as well, leading to $|\mathcal{L}|\leq 2U$.

Now, we observe the number of batches $\tilde{b}>0$ needed to stabilize the state norm; i.e., $\min\{\tilde{b}>0:s_{b+\tilde{b}}<s_{b}\}$.
When the Break statement is not activated, one can write

$$ $\displaystyle\|x_{t_{b+\tilde{b}}}\|$ $\displaystyle\leq\beta(\tau_{0})\|x_{t_{b+\tilde{b}-1}}\|+\gamma w_{\text{max}}\leq(\beta(\tau_{0}))^{\tilde{b}}\|x_{t_{b}}\|+\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{0})}$ $\displaystyle\leq(\beta(\tau_{0}))^{\tilde{b}}\|x_{t_{b}}\|+\delta<(\beta(\tau_{0}))^{\tilde{b}}[(\alpha_{b})^{s_{b}+1}\|x_{0}\|+\delta]+\delta,$ (4) $$

where the last two inequalities are by the design of $\delta$ and ([3](#S4.E3)). It is desirable to find the minimum value of $\tilde{b}>0$ that makes the right-hand side of ([4.2](#S4.Ex6)) smaller than $(\alpha_{b})^{s_{b}}\|x_{0}\|+\delta$:

$$ $\displaystyle(\beta(\tau_{0}))^{\tilde{b}}[(\alpha_{b})^{s_{b}+1}\|x_{0}\|+\delta]+\delta\leq(\alpha_{b})^{s_{b}}\|x_{0}\|+\delta\quad\Longleftrightarrow\quad\frac{1}{(\beta(\tau_{0}))^{\tilde{b}}}\geq\alpha_{b}+\frac{\delta}{(\alpha_{b})^{s_{b}}\|x_{0}\|},$ (5) $$

where the right-hand side of ([5](#S4.E5)) can be upper-bounded by $\alpha_{b}+\frac{\delta}{\|x_{0}\|}$ since $\alpha_{b}>1$. Thus, if $s_{b}\neq 0$,

$$ $\displaystyle\min\{\tilde{b}>0:s_{b+\tilde{b}}<s_{b}\}\leq\Biggr{\lceil}\frac{\log(\alpha_{b}+\frac{\delta}{\|x_{0}\|})}{-\log\beta(\tau_{0})}\Biggr{\rceil},$ (6) $$

when the Break statement is not activated. In other words, starting from any arbitrary batch $b$ where $s_{b}>0$, within the number of batches on the right-hand side of ([6](#S4.E6)), either the Break statement is activated or the value of $s_{b}$ decreases.
Thus, considering that $|\mathcal{L}|\leq 2U$, we have

$$ $|\mathcal{V}|\leq(2U-1)\Biggr{\lceil}\frac{\log(\alpha_{b}+\frac{\delta}{\|x_{0}\|})}{-\log\beta(\tau_{0})}\Biggr{\rceil},$ $$

which completes the proof. More proof details can be found in the Appendix (see Lemma [D.3](#A4.Thmtheorem3)).
∎

Proof sketch of Theorems [4.5](#S4.Thmtheorem5) and [4.6](#S4.Thmtheorem6): By adopting the analysis performed in previous works (Cesa-Bianchi & Lugosi (); van Erven et al. (); de Rooij et al. ()), we divide the expected total cost into the mix loss $-\frac{1}{\eta_{0}}\log(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{b}w_{b}^{\prime}(k)))$ and the mixability gap $\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]+\frac{1}{\eta_{0}}\log(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{b}w_{b}^{\prime}(k)))$. The big difference between the previous analysis and our approach is that we use different learning rates for the one in the denominator ($\eta_{0}$) and the other inside the exponential term ($\eta_{b}$) as we use an adaptive learning rate. The additional term introduced by using different rates is bounded in terms of $U$ by Lemma [4.7](#S4.Thmtheorem7).

After bounding the expected total cost with cumulative mix loss and mixability gap, we need to study $\mathbb{E}_{K_{B-1:0}}\sum_{b=0}^{B-1}\sum_{t=t_{b}}^{t_{b+1}-1}\bigr{[}\frac{c_{t}(x_{t}^{K}(i^{*}),u_{t}^{K}(i^{*}))}{(\alpha_{b})^{2s_{b}}}-c_{t}(x_{t}^{*},u_{t}^{*})\bigr{]}$, where $x_{t}^{K}(i)$ and $u_{t}^{K}(i)$ for $t=t_{b},\dots,t_{b+1}-1$ denote the state and action sequence generated by selecting the controllers before batch $b$ according to Algorithm [1](#alg1), while selecting the controller $i$ at batch $b$.
This does not produce any exponential term since the costs are regularized with the factor $(\alpha_{b})^{2s_{b}}$. The additional term introduced by regularization is also bounded by the order of $U$ due to Lemma [4.7](#S4.Thmtheorem7). The proof details are provided in Appendix [D](#A4). ∎

###### Remark 4.8 (Lower bound) .

The regret bound $\tilde{O}(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3})$ provided in Theorem [4.6](#S4.Thmtheorem6) is similar to the lower bound presented in Dekel et al. (), except that there is an extra term $(|\mathcal{U}|+1)^{1/3}$, reflecting the unbounded costs for the bandits. Moreover, a stability-agnostic nature of the given controllers implies that any algorithm will normally encounter destabilizing controllers and it is unavoidable to face the exponential term $\exp(O(|\mathcal{U}|))$ in regret.
To be more specific, our work has an exponential term in the number of destabilizing controllers ($|\mathcal{U}|$), while the work Chen & Hazan () provides the lower bound involving an exponential term in $L>kd_{u}$ (see Section 2.1 and Theorem 3), where $d_{u}$ is the dimension of the action and $k$ is the controllability index. Here, a large controllability index implies that the system is complex to control as more stages of control actions are needed to stabilize the system. Thus, together with a dimension of the controller action $d_{u}$, a large $kd_{u}$ in their work is analogous to a large $|\mathcal{U}|$ in our setting.
Thus, due to the lower bound, the exponentially increasing term can be tackled by reducing it by the inverse power term on $T$ at best.
Theorem [4.6](#S4.Thmtheorem6) aligns with this idea since the resulting regret bound involves the term $\tilde{O}(T^{-1/3})\cdot\exp(O(|\mathcal{U}|))$ by factoring in every potential exponential term to be multiplied with the initial learning rate $\eta_{0}=O(T^{-2/3})$, which inherently serves as a mitigating factor.
Note that instead of dramatically reducing the regret bound, our main contribution is on significantly relaxing the stability assumptions for required controllers (see Table [1](#S1.T1) and Appendix [A](#A1)).

###### Remark 4.9 (Nonlinear control) .

Our approach is useful to extend the stability and regret analysis beyond linear dynamics, but if $|\mathcal{U}|$ is too large, it would be difficult to reach good enough performance as the regret bound depends on $\exp(O(|\mathcal{U}|))$. This occurs because we have focused on a discrete set of controllers instead of a connected set as in linear dynamics. Note that in the linear dynamics case, it is guaranteed that the set of stabilizing controllers is connected. However, adopting a discrete set was inevitable to handle unknown nonlinear systems since the set of stabilizing controllers may not be connected. To address this limitation, we believe that this issue can be mitigated by the formulation where the problem of interest is $|\mathcal{U}|$ number of connected sets, where $|\mathcal{U}|$ is not too large and each set is disjoint from the others. The agent can apply techniques of continuous parameterization (e.g. gradient descent) within a set and also transition between separate sets by leveraging our technique. This mixture of algorithms for discrete and connected sets will be an interesting future work.

Now, a question arises as to what happens if $|\mathcal{U}|$ is not known in advance.
With Algorithm [1](#alg1), one can leverage $|\mathcal{U}|+1\leq N$ to upper-bound the regret in Theorem [4.6](#S4.Thmtheorem6) and achieve $\tilde{O}(T^{2/3}N^{2/3})$ at best (without considering exponential terms) by determining $\eta_{0}$ and $(\tau_{b})_{b\geq 0}$ as if there were only one stabilizing controller. It turns out that we can reduce the bound to $\tilde{O}(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/2})$ by adaptively changing the value of $\eta_{b}$ as in Algorithm [2](#alg2), where we increase the value of $\mu_{b}$ if the Break statement in Algorithm [1](#alg1) is activated and keep it unchanged otherwise.

###### Theorem 4.10 (Regret bound with unknown $|\mathcal{U}|$ ) .

Consider Algorithm [2](#alg2) with
polynomial batches defined in Assumption [3.1](#S3.Thmtheorem1) with $(\frac{1}{N^{1/2}},z,\frac{1}{2},\nu)$, where the constants $z,\nu>0$ satisfy $\tau_{0}>0$ and $\frac{\tau_{1}}{\tau_{0}}(\beta(\tau_{0}))^{2}<\frac{1}{2\sqrt{2}}$. Also, let $\eta_{0}=O(\frac{1}{T^{2/3}N^{1/3}})$ and $y=\frac{1}{2}$. When $H(t)\leq O(\sum_{i=1}^{t}\frac{1}{i})$ for all $t\geq 1$ and $T\geq\max\{\frac{|\mathcal{U}|^{3/2}}{N^{1/2}(|\mathcal{U}|+1)^{3/4}},N\}$, we have

$$ $\textit{Regret}_{T}=\bigr{[}\tilde{O}(T^{2/3})+\tilde{O}(T^{-1/3})\exp(O(|\mathcal{U}|))\bigr{]}N^{1/3}(|\mathcal{U}|+1)^{1/2}.$ $$

Figure: Algorithm 2 DBAR-unknown $|\mathcal{U}|$

Proof sketch: Define $\eta_{0,r}:=\eta_{0}\sqrt{r+1}$. It turns out that for every $r=0,\dots,U$, $\tilde{O}(\frac{1}{\eta_{0,r}})$ appears in the regret instead of the integrated term $\tilde{O}(\frac{|\mathcal{U}|+1}{\eta_{0}})$ in Theorem [4.5](#S4.Thmtheorem5). The constant $|\mathcal{U}|+1$ is distributed among each $\tilde{O}(\frac{1}{\eta_{0,r}})$ term. Under the constraints given by the disintegration rule using Lemma [4.7](#S4.Thmtheorem7) for each $r$, one can establish an upper bound of $\tilde{O}(\frac{(|\mathcal{U}|+1)^{1/2}}{\eta_{0}})$ on the sum of $\tilde{O}(\frac{1}{\eta_{0,r}})$ terms over $r=0,\dots,U$ by attaining the coefficients of these terms with complementary slackness in Karush-Kuhn-Tucker (KKT) conditions.
The details are available in Appendix [E](#A5). ∎

Our DBAR algorithm can also be applied to scenarios such as those switched systems (Tousi et al. (); Zhao et al. ()) in which the transition dynamics and the associated controller pool change according to either the detection of a destabilizing controller or pre-determined
time instants (Battistelli et al. ()), as well as the ballooning problem (Ghalme et al. ()) where the controller pool may expand.
We proposed Algorithm [3](#alg3), the switching version of DBAR, in Appendix [F](#A6).

###### Theorem 4.5 (Regret Bound) .

###### Theorem 4.6 (Regret bound with known | 𝒰 | 𝒰 |\mathcal{U}| ) .

###### Lemma 4.7 .

###### Proof.

###### Remark 4.8 (Lower bound) .

###### Remark 4.9 (Nonlinear control) .

###### Theorem 4.10 (Regret bound with unknown | 𝒰 | 𝒰 |\mathcal{U}| ) .

## 5 Numerical Experiments

To demonstrate the main results of this paper, we provide illustrative examples on both linear and nonlinear dynamics with adversarial disturbances. While the simulations are on low-dimensional systems for illustration purposes, similar observations can be made for high-dimensional systems.

Example 1: Consider the following linear dynamical system with $x_{t}\in\mathbb{R}^{2}$ and $u_{t}\in\mathbb{R}^{2}$:

$$ $\displaystyle x_{t+1}=\begin{bmatrix}2&1.2\\ 1.1&2.5\end{bmatrix}x_{t}+\begin{bmatrix}1&0.3\\ 0.4&0.9\end{bmatrix}u_{t}+w_{t},\quad t=0,1,\dots,$ (7) $$

where $x_{0}=[100,200]^{\prime}$ and $w_{t}=[\sin\bigr{(}\frac{t}{5\pi}\bigr{)},\sin\bigr{(}\frac{t}{11\pi}\bigr{)}]^{\prime}$. We consider a linear policy $u_{t}=Kx_{t}=\begin{bmatrix}k_{1}&k_{2}\\
k_{3}&k_{4}\end{bmatrix}x_{t}$
and a controller pool
$K^{\prime}=\{K\in\mathbb{R}^{2\times 2}:k_{1},k_{3},k_{4}\in\{-3,-2,-1\},k_{2}\in\{-1,0,1\}\}$
that has
$|\mathcal{U}|=53$
out of 81 candidate controllers.
The goal is to keep the state near the origin, where the cost function is quadratic at each time, namely $c_{t}(x_{t},u_{t})=\|x_{t}\|^{2}$.

Falsifying destabilizing controllers moderately stabilizes the state norm (Li et al. ()). Compared to their work, Figures [1(a)](#S5.F1.sf1) and [1(b)](#S5.F1.sf2) show that both integral components of our algorithm DBAR, dynamic batch length and adaptive learning rate, further lowers the regret and stabilizes the system, where approximately 2/3 of controllers in $K^{\prime}$ are destabilizing the system. In this case, Figures [1(c)](#S5.F1.sf3) and [1(d)](#S5.F1.sf4) both demonstrate that the two components of our algorithm mutually reinforce each other, where each component stabilizes the state norm with or without time delay. This supports the observations in Appendix [A](#A1).
In Appendix [G.1](#A7.SS1), we also provide the experiment details and simulation results with noise terms generated by uniform random walk, where $w_{t}-w_{t-1}$ has a uniform distribution for $t\geq 1$, as well as the results with truncated Gaussian noise for sanity check.

Figure: (a) Stability analysis
Refer to caption: /html/2410.03230/assets/figures/stabsinu.png

Figure: (a) Ball-beam system
Refer to caption: /html/2410.03230/assets/figures/ballbeam.png

Example 2: Consider the following nonlinear noise-injected ball-beam system (Hauser et al. ()):

$$ $\displaystyle\ddot{x}=B(x\dot{\theta}^{2}-9.81\sin\theta)+3w,\quad\ddot{\theta}=u,\quad B=0.7143,$ (8) $$

where $x$ is the ball position, $\theta$ is the beam angle, $u$ is the action, and $w(t)=\sin\bigr{(}\frac{t}{7\pi}\bigr{)}$. We now adopt a broader notion of stabilizing controllers and choose the policy class to be the nested saturating control (Teel ()), without considering exponentially stabilizing notions. In Figures [2(b)](#S5.F2.sf2) and [2(c)](#S5.F2.sf3), we observe that
each of the two components of DBAR does not necessarily stabilize the state norm by itself. However, if they are jointly applied, DBAR effectively stabilizes the explosion of the nonlinear system and enjoys the improved regret, even when we use $\beta(t)=O(1/t)$ to define the stabilizing controllers (see Definition [2.3](#S2.Thmtheorem3)).
We also provide the simulation results with different polynomially decreasing $\beta(\cdot)$ series at various rates. More experiment details are available in Appendix [G.2](#A7.SS2).

## 6 Conclusion

In an online bandit nonlinear control problem, an agent makes decisions with the bandit feedback information, while suffering from nonlinear dynamics and adversarial disturbances. To address such challenges, this paper develops a novel Exp3-type algorithm with theoretical guarantees.
The proposed algorithm uses a dynamic batch length to achieve asymptotic stability of the system without requiring an exponential assumption on stabilizing controllers in the pool.
Our adaptive learning rate scheme observes the stability of state norm to overcome the inherent multiplicative exponential term in the regret, thereby improving the overall regret. Future directions include extending these results to problems with
explicit safety constraints while selecting the best stabilizing controller among a continuum of candidate controllers.

## Appendix A Necessity of DBAR under weaker stability notion of required controllers

To illustrate how significant the weaker controller stability notion is compared to the exponential notions, let us further present a one-dimensional system, where the current system state is $1$. The goal is to achieve a state near 0 0, and we would like to detect this stability by observing whether one arrives at a state less than $1-\epsilon$, where $\epsilon$ is an arbitrarily small positive number. Exponentially stabilizing controllers guarantee to detect the stability in $O(\log(\epsilon))$ time. However, with an asymptotically stabilizing controller, if the controller is designed to keep the system state unchanged for an arbitrarily long time $T$ and then collapse the state towards 0 0 afterward, one cannot detect the stability before time $T$ regardless of how small $\epsilon$ is. In such a case, even though the controller ultimately achieves the goal, it may take a lot of time to learn whether a closed-loop system would be stable or not.

Note that dynamic batch length is an important part of our work. If an exponentially stabilizing controller is applied to a system, one can quickly certify the stability. However, if we only have the asymptotically stabilizing controllers as in our problem setting, it may take a long time to observe any abnormal behavior in the closed-loop system. Such an issue cannot be handled by a fixed batch length and in that sense dynamic batch length is a necessary part of our work. In Table [1](#S1.T1), we have stated the intermediate step "Dynamic Batching" to achieve closed-loop system asymptotic stability, which was not achievable by the previous works.

Figure [3](#A1.F3) also demonstrates the necessity of a dynamic batch length regardless of the noise assumption. The blue and orange lines represent the state norms generated by a fixed batch length and a dynamic batch length, respectively. With both relatively easier statistical noise and more challenging adversarial noise, the blue line shows a larger state norm than the orange line. Moreover, the blue line occasionally has higher values than the red line, which is our asymptotic stability bound $\gamma w_{\text{max}}=1.5$, while the orange line remains below the red line after a certain time.

Figure: (a) Statistical Noise
Refer to caption: /html/2410.03230/assets/figures/statnoise.png

However, it turns out that the resulting regret by dynamic batching contains the multiplicative term $o(T^{1/3})\cdot\exp(O(|\mathcal{U}|))$, which is because a dynamic batch length induces $H(\tau_{B-1})$ to be necessarily multiplied with $\exp(O(|\mathcal{U}|))$. (see Corollary [D.10](#A4.Thmtheorem10)).
Thus, we came up with a careful switching strategy, an adaptive learning rate, to address this issue. The multiplicative term can be resolved with splitting technique by introducing an adaptive learning rate, achieving both closed-loop system asymptotic stability (by dynamic batch length) and the improved regret (by adaptive learning rate), even though we have greatly relaxed the assumption on controller stability (exponential to asymptotic).
We developed this approach by factoring in every potential exponential term to be multiplied with the initial learning rate $\eta_{0}=O(T^{-2/3})$, which has a negative exponent on $T$, thus inherently serving as a mitigating factor (see Theorem [4.6](#S4.Thmtheorem6) and the term $\frac{\eta_{0}N}{2}\sum_{b=0}^{B-1}\mathbb{E}_{K_{b-1:0}}(w_{b}^{K}(i^{b}))^{2}$ in Lemma [D.5](#A4.Thmtheorem5)).
Due to Lemma [4.7](#S4.Thmtheorem7), one can explain that the remaining terms produced by the splitting can be bounded by $O(|\mathcal{U}|)$. More details can be found in Appendix [D](#A4).

## Appendix B Glossary

Before formally presenting the proofs, we provide a glossary to help readers understand the notations of our algorithm DBAR (see Algorithm [1](#alg1)).

**Table 2: Glossary**
| Notation | Meaning |
| --- | --- |
| $x_{t}$ | state at time $t$ in the algorithm |
| $x_{t}^{*}$ | optimal state at time $t$ |
| $u_{t}$ | action at time $t$ in the algorithm |
| $u_{t}^{*}$ | optimal action at time $t$ |
| $c_{t}(x_{t},u_{t})$ | cost at time $t$ |
| $w_{\text{max}}$ | the maximum norm of the noise |
| $T$ | the length of time in the algorithm |
| $B$ | the number of batches in the algorithm |
| $t_{b}$ | the start time for each batch $b$ |
| $\tau_{b}$ | the batch length at batch $b$ |
| $\eta_{b}$ | learning rate at batch $b$ |
| $K_{b}$ | the controller selected at batch $b$ |
| $N$ | the number of controllers in the candidate pool |
| $W_{b}(k)$ | the weight of controller $k$ at batch $b$ |
| $p_{b}(k)$ | the probability of selecting controller $k$ at batch $b$ |
| $P_{b}$ | a set of available controllers at batch $b$ |
| $\alpha_{b},s_{b}$ | $(\alpha_{b})^{s_{b}}$ indicates the magnitude of the state norm at $t_{b}$ compared to $\|x_{0}\|$ |
| $\beta(t)$, $\gamma$ | applying a stabilizing controller incurs $\|x_{t}\|\leq\beta(t)\|x_{0}\|+\gamma w_{\text{max}}$ |
| $L_{f}$ | Lipschitz constant for the dynamic $f$ |
| $L_{\pi}$ | Lipschitz constant for any controller $\pi$ |
| $U$ | the number of times the Break statement is activated |
| $b_{1},\dots,b_{U}$ | the next batch after the Break statement is activated |

## Appendix C Stability Proof

Let $b_{1},\dots,b_{U}$ denote the next batch after the Break statement is activated; i.e., $\|x_{t_{b_{u}}}\|>\beta(t_{b_{u}}-t_{b_{u}-1})\|x_{t_{b_{u}-1}}\|+\gamma w_{\text{max}}$ for every $u=1,\dots,U$. For future use, let $b_{0}=0$ and $b_{U+1}=B$. Accordingly, $t_{b_{0}}=t_{0}=0$ and $t_{b_{U+1}}=t_{B}=T+1$.

###### Lemma C.1 (Restatement of Lemma 4.3 ) .

Define $H(t):=\sum_{i=0}^{t-1}\beta(i)$. Then, we have

$$ $\lim_{t\to\infty}\frac{H(t)}{t}=0.$ $$

###### Proof.

Recall that we designed $\beta(\cdot)$ to be non-increasing and nonnegative. Then, we have $\beta(i)\leq\int_{i-1}^{i}\beta(x)dx$ for every integer $i\geq 1$. Using the inequality, one can write

$$ $\displaystyle 0\leq H(t)=\beta(0)+\sum_{i=1}^{t-1}\beta(i)\leq\beta(0)+\int_{0}^{t-1}\beta(x)dx.$ (9) $$

If $\lim_{t\to\infty}H(t)<\infty$, clearly $\lim_{t\to\infty}\frac{H(t)}{t}=0$ holds. If $\lim_{t\to\infty}H(t)=\infty$, we leverage L’Hôpital’s rule with $\beta(t)\to 0$ as $t\to\infty$ to derive

$$ $\displaystyle\lim_{t\to\infty}\frac{H(t)}{t}\leq\lim_{t\to\infty}\frac{\beta(0)+\int_{0}^{t-1}\beta(x)dx}{t}=\lim_{t\to\infty}\frac{\beta(t-1)}{1}=0,$ $$

where the first inequality follows from ([9](#A3.E9)).
∎

###### Lemma C.2 .

For $0\leq j\leq k$, we have

$$ $\frac{H(\tau_{k})}{H(\tau_{j})}\leq\frac{\tau_{k}}{\tau_{j}}.$ $$

###### Proof.

For $0\leq j\leq k$,

$$ $\frac{H(\tau_{k})}{H(\tau_{j})}\leq\frac{H(\tau_{j})+\sum_{i=\tau_{j}}^{\tau_{k}-1}\beta(i)}{H(\tau_{j})}\leq 1+\frac{(\tau_{k}-\tau_{j})\cdot\beta(\tau_{j})}{\tau_{j}\cdot\beta(\tau_{j})}=\frac{\tau_{k}}{\tau_{j}},$ $$

where the last inequality is due to the non-increasing property of $\beta(\cdot)$. The equality holds when $\beta(0)=\dots=\beta(\tau_{k}-1)$.
∎

###### Lemma C.3 (Sum of state norms in a single batch) .

In Algorithm [1](#alg1), for each batch $b=0,1,\dots,B-1$, the following inequality holds:

$$ $\sum_{t=t_{b}}^{t_{b+1}-1}\|x_{t}\|\leq H(\tau_{b})\|x_{t_{b}}\|+\gamma w_{\text{max}}(\tau_{b}-1)$ $$

###### Proof.

For $t=t_{b}$, we have $\|x_{t}\|\leq\beta(0)\|x_{t_{b}}\|$ since $\beta(0)=1$. For $t_{b}<t\leq t_{b+1}-1$, we have

$$ $\displaystyle\|x_{t}\|\leq\beta(t-t_{b})\|x_{t_{b}}\|+\gamma w_{\text{max}}.$ (10) $$

Summing up all inequalities gives

$$ $\sum_{t=t_{b}}^{t_{b+1}-1}\|x_{t}\|\leq H(t_{b+1}-t_{b})\|x_{t_{b}}\|+\gamma w_{\text{max}}(t_{b+1}-t_{b}-1).$ $$

Since Line [5](#alg1.l5) of Algorithm [1](#alg1) is not satisfied, $\tau_{b}=t_{b+1}-t_{b}$. This completes the proof.
∎

###### Lemma C.4 (Weighted sum of state norms between the two consecutive Break statements) .

In Algorithm [1](#alg1), suppose that $\frac{\tau_{1}}{\tau_{0}}\beta(\tau_{0})<1$. For every next batch index after the Break statement $u=0,\dots,U$, the following inequality holds:

$$ $\sum_{b=b_{u}}^{b_{u+1}-1}H(\tau_{b})\|x_{t_{b}}\|\leq\frac{1}{1-\frac{\tau_{b_{u}+1}}{\tau_{b_{u}}}\beta(\tau_{b_{u}})}H(\tau_{b_{u}})\|x_{t_{b_{u}}}\|+\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{b_{u}+1})}\sum_{b=b_{u}+1}^{b_{u+1}-1}H(\tau_{b}).$ $$

###### Proof.

Since we designed $(\tau_{b})_{b\geq 0}$ to have a non-decreasing $\tau_{b}$ and non-increasing $\frac{\tau_{b+1}}{\tau_{b}}$, notice that we have $\beta(\tau_{b})\leq\frac{\tau_{b+1}}{\tau_{b}}\beta(\tau_{b})\leq\frac{\tau_{b}}{\tau_{b-1}}\beta(\tau_{b-1})\leq\frac{\tau_{1}}{\tau_{0}}\beta(\tau_{0})<1$ for every $b\geq 1$ since $\beta(\cdot)$ is non-increasing.

If $b_{u+1}=b_{u}+1$, the inequality clearly holds since $\frac{1}{1-\frac{\tau_{b_{u}+1}}{\tau_{b_{u}}}\beta(\tau_{b_{u}})}>0$. Otherwise, consider the following inequality for $b_{u}<b\leq b_{u+1}-1$:

$$ $\displaystyle H(\tau_{b})\|x_{t_{b}}\|$ $\displaystyle\leq H(\tau_{b})\beta(\tau_{b-1})\|x_{t_{b-1}}\|+H(\tau_{b})\gamma w_{\text{max}}$ $\displaystyle=\frac{H(\tau_{b})}{H(\tau_{b-1})}\beta(\tau_{b-1})H(\tau_{b-1})\|x_{t_{b-1}}\|+H(\tau_{b})\gamma w_{\text{max}},$ $$

where the inequality holds since Line [5](#alg1.l5) of Algorithm [1](#alg1) is not satisfied. Recursively applying this inequality, one arrives at

$$ $\displaystyle H(\tau_{b})\|x_{t_{b}}\|$ $\displaystyle\leq\Pi_{a=b_{u}}^{b-1}\Bigr{[}\frac{H(\tau_{a+1})}{H(\tau_{a})}\beta(\tau_{a})\Bigr{]}\cdot H(\tau_{b_{u}})\|x_{t_{b_{u}}}\|+H(\tau_{b})\gamma w_{\text{max}}(1+\sum_{b^{\prime}=b_{u}+1}^{b-1}\Pi_{a=b^{\prime}}^{b-1}\beta(\tau_{a}))$ $\displaystyle\leq\Pi_{a=b_{u}}^{b-1}\Bigr{[}\frac{H(\tau_{a+1})}{H(\tau_{a})}\beta(\tau_{a})\Bigr{]}\cdot H(\tau_{b_{u}})\|x_{t_{b_{u}}}\|+H(\tau_{b})\gamma w_{\text{max}}(1+\sum_{b^{\prime}=b_{u}+1}^{b-1}[\beta(\tau_{b_{u}+1})]^{b-b^{\prime}})$ $\displaystyle\leq\Pi_{a=b_{u}}^{b-1}\Bigr{[}\frac{H(\tau_{a+1})}{H(\tau_{a})}\beta(\tau_{a})\Bigr{]}\cdot H(\tau_{b_{u}})\|x_{t_{b_{u}}}\|+H(\tau_{b})\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{b_{u}+1})}$ (11) $\displaystyle\leq\Pi_{a=b_{u}}^{b-1}\Bigr{[}\frac{\tau_{a+1}}{\tau_{a}}\beta(\tau_{a})\Bigr{]}\cdot H(\tau_{b_{u}})\|x_{t_{b_{u}}}\|+H(\tau_{b})\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{b_{u}+1})}$ $\displaystyle\leq\Bigr{[}\frac{\tau_{b_{u}+1}}{\tau_{b_{u}}}\beta(\tau_{b_{u}})\Bigr{]}^{b-b_{u}}\cdot H(\tau_{b_{u}})\|x_{t_{b_{u}}}\|+H(\tau_{b})\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{b_{u}+1})},$ $$

where the second inequality comes from the non-increasing property of $\beta(\cdot)$, the third inequality is by $\beta(\tau_{b_{u}+1})<1$, the fourth inequality is due to Lemma [C.2](#A3.Thmtheorem2), and the last inequality comes from the non-increasing property of $\frac{\tau_{b+1}}{\tau_{b}}\beta(\tau_{b})$. Since $\frac{\tau_{b_{u}+1}}{\tau_{b_{u}}}\beta(\tau_{b_{u}})<1$, summing up the above inequalities for $b_{u}<b\leq b_{u+1}-1$ completes the proof.
∎

###### Lemma C.5 (Next state norm after the Break statement) .

Define $M_{1}:=L_{f}(1+L_{\pi})\gamma w_{\text{max}}+L_{f}(\pi_{0,\text{max}}+w_{\text{max}})+f_{0}.$ Then, for every $u=1,\dots,U$, we have

$$ $\|x_{t_{b_{u}}}\|\leq L_{f}(1+L_{\pi})\beta(0)\|x_{t_{b_{u}-1}}\|+M_{1}.$ $$

###### Proof.

Suppose we picked a controller $\pi_{t}$ at time step $t$. Then, by Assumption [2.5](#S2.Thmtheorem5), we have

$$ $\displaystyle\|u_{t}\|=\|\pi_{t}(x_{t})-\pi_{t}(0)+\pi_{t}(0)\|\leq\|\pi_{t}(x_{t})-\pi_{t}(0)\|+\|\pi_{t}(0)\|\leq L_{\pi}\|x_{t}\|+\pi_{0,\text{max}}.$ (12) $$

Combining the above inequality with Assumption [2.1](#S2.Thmtheorem1), one can write

$$ $\displaystyle\|x_{t+1}\|$ $\displaystyle=\|f(x_{t},u_{t},w_{t})-f(0,0,0)+f(0,0,0)\|$ $\displaystyle\leq\|f(x_{t},u_{t},w_{t})-f(0,0,0)\|+\|f(0,0,0)\|\leq L_{f}(\|x_{t}\|+\|u_{t}\|+\|w_{t}\|)+f_{0}$ $\displaystyle\leq L_{f}(\|x_{t}\|+L_{\pi}\|x_{t}\|+\pi_{0,\text{max}}+w_{\text{max}})+f_{0}$ $\displaystyle=L_{f}(1+L_{\pi})\|x_{t}\|+L_{f}(\pi_{0,\text{max}}+w_{\text{max}})+f_{0}.$ $$

Thus, for every $u=1,\dots,U$, we obtain that

$$ $\displaystyle\|x_{t_{b_{u}}}\|$ $\displaystyle\leq L_{f}(1+L_{\pi})\|x_{t_{b_{u}}-1}\|+L_{f}(\pi_{0,\text{max}}+w_{\text{max}})+f_{0}$ $\displaystyle\leq L_{f}(1+L_{\pi})(\beta(t_{b_{u}}-t_{b_{u}-1}-1)\|x_{t_{b_{u}-1}}\|+\gamma w_{\text{max}})+L_{f}(\pi_{0,\text{max}}+w_{\text{max}})+f_{0}$ $\displaystyle=L_{f}(1+L_{\pi})\beta(t_{b_{u}}-t_{b_{u}-1}-1)\|x_{t_{b_{u}-1}}\|+M_{1}$ $\displaystyle\leq L_{f}(1+L_{\pi})\beta(0)\|x_{t_{b_{u}-1}}\|+M_{1},$ $$

where the second inequality holds since Line [5](#alg1.l5) of Algorithm [1](#alg1) is not satisfied during $t_{b_{u}-1}\leq t\leq t_{b_{u}}-1$ and the equality holds for the last inequality when $t_{b_{u}}=t_{b_{u}-1}+1$. This completes the proof.
∎

###### Lemma C.6 (Weighted sum of state norms along the Break statements) .

In Algorithm [1](#alg1), suppose that $\frac{\tau_{1}}{\tau_{0}}\beta(\tau_{0})<1$. Define $M_{2}:=L_{f}(1+L_{\pi})\beta(0)\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{1})}+M_{1}$. Then, there exists a constant $C\geq 1$ such that

$$ $\sum_{u=0}^{U}H(\tau_{b_{u}})\|x_{t_{b_{u}}}\|\leq\frac{[L_{f}(1+L_{\pi})\beta(0)C]^{U+1}-1}{L_{f}(1+L_{\pi})\beta(0)C-1}H(\tau_{0})\|x_{0}\|+\frac{([L_{f}(1+L_{\pi})\beta(0)C]^{U}-1)M_{2}}{[L_{f}(1+L_{\pi})\beta(0)C-1]^{2}}H(\tau_{b_{U}})$ $$

###### Proof.

Since we designed $\frac{\tau_{b+1}}{\tau_{b}}$ to converge, there exists $R>0$ such that $\frac{\tau_{b+1}}{\tau_{b}}\leq R$ for all $b\geq 0$. Moreover, since $\lim_{b\to\infty}\frac{\tau_{b+1}}{\tau_{b}}=1$ and $\beta(\tau_{0})<1$, there exists $b^{*}>0$ such that

$$ $\displaystyle b\geq b^{*}\implies\frac{\tau_{b+1}}{\tau_{b}}<\frac{1}{\beta(\tau_{0})}.$ (13) $$

Accordingly, for any two batches $b^{\prime}>b\geq 0$, we have

$$ $\displaystyle\frac{\tau_{b^{\prime}}}{\tau_{b}}[\beta(\tau_{b})]^{b^{\prime}-b-1}$ $\displaystyle\leq[\beta(\tau_{0})]^{b^{\prime}-b-1}\Pi_{a=b}^{b^{\prime}-1}\frac{\tau_{a+1}}{\tau_{a}}\leq\frac{R^{b^{*}}}{\beta(\tau_{0})},$ (14) $$

considering that $b=0$ and $b^{\prime}=b^{*}$ yields the largest possible upper bound due to ([13](#A3.E13)). Now, define $C:=\frac{R^{b^{*}}}{\beta(\tau_{0})}$. Notice that we have $C\geq 1$ since the left-hand side of ([14](#A3.E14)) is greater than equal to $1$ when $b^{\prime}=b+1$. Then, for every $u=1,\dots,U$, one can write

$$ $\displaystyle H(\tau_{b_{u}})\|x_{t_{b_{u}}}\|$ $\displaystyle\leq L_{f}(1+L_{\pi})\beta(0)\frac{H(\tau_{b_{u}})}{H(\tau_{b_{u}-1})}H(\tau_{b_{u}-1})\|x_{t_{b_{u}-1}}\|+H(\tau_{b_{u}})M_{1}$ $\displaystyle\leq L_{f}(1+L_{\pi})\beta(0)\frac{H(\tau_{b_{u}})}{H(\tau_{b_{u}-1})}\Pi_{a=b_{u-1}}^{b_{u}-2}\Bigr{[}\frac{H(\tau_{a+1})}{H(\tau_{a})}\beta(\tau_{a})\Bigr{]}\cdot H(\tau_{b_{u-1}})\|x_{t_{b_{u-1}}}\|$ $\displaystyle\hskip 113.81102pt+L_{f}(1+L_{\pi})\beta(0)H(\tau_{b_{u}})\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{b_{u-1}+1})}+H(\tau_{b_{u}})M_{1}$ $\displaystyle\leq L_{f}(1+L_{\pi})\beta(0)\frac{H(\tau_{b_{u}})}{H(\tau_{b_{u-1}})}[\beta(\tau_{b_{u-1}})]^{b_{u}-b_{u-1}-1}\cdot H(\tau_{b_{u-1}})\|x_{t_{b_{u-1}}}\|+H(\tau_{b_{u}})M_{2}$ $\displaystyle\leq L_{f}(1+L_{\pi})\beta(0)\frac{\tau_{b_{u}}}{\tau_{b_{u-1}}}[\beta(\tau_{b_{u-1}})]^{b_{u}-b_{u-1}-1}\cdot H(\tau_{b_{u-1}})\|x_{t_{b_{u-1}}}\|+H(\tau_{b_{u}})M_{2}$ $\displaystyle\leq L_{f}(1+L_{\pi})\beta(0)C\cdot H(\tau_{b_{u-1}})\|x_{t_{b_{u-1}}}\|+H(\tau_{b_{u}})M_{2}$ $$

where the first inequality is due to Lemma [C.5](#A3.Thmtheorem5), the second inequality is by ([C](#A3.Ex18)) in Lemma [C.4](#A3.Thmtheorem4), the fourth inequality is due to Lemma [C.2](#A3.Thmtheorem2), and the last inequality is by ([14](#A3.E14)). Recursively applying this inequality, one arrives at

$$ $\displaystyle H(\tau_{b_{u}})\|x_{t_{b_{u}}}\|$ $\displaystyle\leq[L_{f}(1+L_{\pi})\beta(0)C]^{u}H(\tau_{0})\|x_{0}\|+M_{2}\cdot\sum_{i=1}^{u}[L_{f}(1+L_{\pi})\beta(0)C]^{u-i}H(\tau_{b_{i}})$ $\displaystyle\leq[L_{f}(1+L_{\pi})\beta(0)C]^{u}H(\tau_{0})\|x_{0}\|+M_{2}H(\tau_{b_{U}})\cdot\frac{[L_{f}(1+L_{\pi})\beta(0)C]^{u}-1}{L_{f}(1+L_{\pi})\beta(0)C-1}$ $\displaystyle<[L_{f}(1+L_{\pi})\beta(0)C]^{u}\cdot\biggr{[}H(\tau_{0})\|x_{0}\|+\frac{M_{2}H(\tau_{b_{U}})}{L_{f}(1+L_{\pi})\beta(0)C-1}\biggr{]},$ $$

where the second inequality comes from the non-decreasing property of $H(\cdot)$ and the equality holds when $H(\tau_{b_{1}})=\dots=H(\tau_{b_{U}})$. Notice that for $b^{\prime}>b\geq 0$, the case $H(\tau_{b^{\prime}})=H(\tau_{b})$ arises when $\tau_{b^{\prime}}=\tau_{b}$ or $\beta(\tau_{b}+1)=\dots=\beta(\tau_{b^{\prime}})=0$. Since $L_{f}(1+L_{\pi})\beta(0)C>1$, summing up the above inequality for $u=1,\dots,U$ completes the proof.
∎

###### Lemma C.7 (Sum of state norms) .

In Algorithm [1](#alg1), suppose that $\frac{\tau_{1}}{\tau_{0}}\beta(\tau_{0})<1$. Then, we have

$$ $\sum_{t=0}^{T}\|x_{t}\|\leq O([L_{f}(1+L_{\pi})\beta(0)C]^{U}(\|x_{0}\|+H(\tau_{b_{U}})))+\gamma w_{\text{max}}\cdot(O(\sum_{b=0}^{B-1}H(\tau_{b}))+T)$ $$

###### Proof.

Applying Lemma [C.3](#A3.Thmtheorem3), [C.4](#A3.Thmtheorem4), and [C.6](#A3.Thmtheorem6) in turn, we have

$$ $\displaystyle\sum_{t=0}^{T}\|x_{t}\|$ $\displaystyle=\sum_{u=0}^{U}\sum_{b=b_{u}}^{b_{u+1}-1}\sum_{t=t_{b}}^{t_{b+1}-1}\|x_{t}\|$ $\displaystyle\leq\sum_{u=0}^{U}\sum_{b=b_{u}}^{b_{u+1}-1}\biggr{[}H(\tau_{b})\|x_{t_{b}}\|+\gamma w_{\text{max}}(\tau_{b}-1)\biggr{]}$ $\displaystyle\leq\sum_{u=0}^{U}\biggr{[}\frac{1}{1-\frac{\tau_{b_{u}+1}}{\tau_{b_{u}}}\beta(\tau_{b_{u}})}H(\tau_{b_{u}})\|x_{t_{b_{u}}}\|+\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{b_{u}+1})}\sum_{b=b_{u}+1}^{b_{u+1}-1}H(\tau_{b})+\gamma w_{\text{max}}(t_{b_{u+1}}-t_{b_{u}}-1)\biggr{]}$ $\displaystyle\leq\frac{1}{1-\frac{\tau_{1}}{\tau_{0}}\beta(\tau_{0})}\sum_{u=0}^{U}H(\tau_{b_{u}})\|x_{t_{b_{u}}}\|+\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{1})}(\sum_{b=0}^{B-1}H(\tau_{b})-\sum_{u=0}^{U}H(\tau_{b_{u}}))+\gamma w_{\text{max}}(T-U)$ $\displaystyle\leq\frac{1}{1-\frac{\tau_{1}}{\tau_{0}}\beta(\tau_{0})}\sum_{u=0}^{U}H(\tau_{b_{u}})\|x_{t_{b_{u}}}\|+\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{1})}\sum_{b=0}^{B-1}H(\tau_{b})+\gamma w_{\text{max}}T$ $\displaystyle\leq\frac{H(\tau_{0})\|x_{0}\|}{1-\frac{\tau_{1}}{\tau_{0}}\beta(\tau_{0})}\frac{[L_{f}(1+L_{\pi})\beta(0)C]^{U+1}-1}{L_{f}(1+L_{\pi})\beta(0)C-1}+\frac{H(\tau_{b_{U}})}{1-\frac{\tau_{1}}{\tau_{0}}\beta(\tau_{0})}\frac{([L_{f}(1+L_{\pi})\beta(0)C]^{U}-1)M_{2}}{[L_{f}(1+L_{\pi})\beta(0)C-1]^{2}}$ $\displaystyle\hskip 256.0748pt+\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{1})}\sum_{b=0}^{B-1}H(\tau_{b})+\gamma w_{\text{max}}T$ $\displaystyle=O([L_{f}(1+L_{\pi})\beta(0)C]^{U}(\|x_{0}\|+H(\tau_{b_{U}})))+\gamma w_{\text{max}}\cdot(O(\sum_{b=0}^{B-1}H(\tau_{b}))+T)$ $$

where the equality holds for the fourth inequality when Line [5](#alg1.l5) of Algorithm [1](#alg1) is not satisfied for the entire horizon.
∎

###### Theorem C.8 (Restatement of Theorem 4.1 , Asymptotic stability) .

In Algorithm [1](#alg1), suppose that
$\frac{\tau_{1}}{\tau_{0}}\beta(\tau_{0})<1$. Then, it holds that

$$ $\lim_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T}\|x_{t}\|\leq\gamma w_{\text{max}}.$ $$

###### Proof.

We mainly use Lemma [C.1](#A3.Thmtheorem1) to prove the asymptotic stability. First, we have

$$ $\displaystyle H(\tau_{b_{U}})\leq H(\tau_{B-1})=o(\tau_{B-1})=o(T),$ (15) $$

where the first equality is due to Lemma [C.1](#A3.Thmtheorem1) and $\tau_{B-1}=T$ when there is only one batch over the entire horizon. Now, consider the following relationship between the number of batch $B$ and the time horizon $T$:

$$ $\displaystyle\sum_{b=0}^{B-1}\tau_{b}\geq T\geq\sum_{b=0}^{B-U-1}\tau_{b}+U,$ (16) $$

where the second inequality is due to the non-decreasing property of $\tau_{b}$. Now, if $\sum_{b=0}^{B-1}H(\tau_{b})<\infty$, clearly $\sum_{b=0}^{B-1}H(\tau_{b})=o(T)$. Otherwise, define $H(\tau_{B})=H(\tau_{B-1})$. Then, we have

$$ $\displaystyle\lim_{T\to\infty}\frac{\sum_{b=0}^{B-1}H(\tau_{b})}{T}$ $\displaystyle\leq\lim_{B\to\infty}\frac{\sum_{b=0}^{B-1}H(\tau_{b})}{\sum_{b=0}^{B-U-1}\tau_{b}+U}\leq\lim_{B\to\infty}\frac{\int_{0}^{B}H(\tau_{b})db}{\tau_{0}+\int_{0}^{B-U-1}\tau_{b}db+U}$ $\displaystyle=\lim_{B\to\infty}\frac{H(\tau_{B-1})}{\tau_{B-U-1}}=\lim_{B\to\infty}\frac{H(\tau_{B-1})}{\tau_{B-1}}\Pi_{b=B-U-1}^{B-2}\frac{\tau_{b+1}}{\tau_{b}}$ $\displaystyle=0\cdot 1^{U}=0$ (17) $$

where the second inequality leverages the non-decreasing property of both $\tau_{b}$ and $H(\tau_{b})$, the remaining equalities leverage L’Hôpital’s rule, Lemma [C.1](#A3.Thmtheorem1), and $\lim_{b\to\infty}\frac{\tau_{b+1}}{\tau_{b}}=1$. Thus, with Lemma [C.7](#A3.Thmtheorem7), we have

$$ $\sum_{t=0}^{T}\|x_{t}\|\leq O([L_{f}(1+L_{\pi})\beta(0)C]^{U}(\|x_{0}\|+o(T)))+\gamma w_{\text{max}}\cdot(T+o(T)).$ $$

This completes the proof.
∎

###### Lemma C.9 .

In Algorithm [1](#alg1), we have

$$ $\lim_{T\to\infty}\frac{B}{T}=0$ $$

###### Proof.

Recall the relationship stated in ([16](#A3.E16)) between $T$ and $B$. Using the second inequality, we have

$$ $\displaystyle 0\leq\lim_{T\to\infty}\frac{B}{T}\leq\lim_{T\to\infty}\frac{B}{\sum_{b=0}^{B-U-1}\tau_{b}+U}$ $\displaystyle\leq\lim_{T\to\infty}\frac{B}{\tau_{0}+\int_{0}^{B-U-1}\tau_{b}db+U}$ $\displaystyle=\lim_{T\to\infty}\frac{1}{\tau_{B-U-1}}=0,$ $$

where the third inequality uses the non-decreasing property of $\tau_{b}$, after which we use L’Hôpital’s rule. This completes the proof.
∎

###### Theorem C.10 (Restatement of Theorem 4.2 , Finite-gain stability) .

In Algorithm [1](#alg1), suppose that $\frac{\tau_{1}}{\tau_{0}}\beta(\tau_{0})<1$. Assume that $\lim_{t\to\infty}H(t)<\infty$. Then, Algorithm [1](#alg1) achieves finite-gain $\mathcal{L}_{1}$ stability; i.e., there exist constants $A_{1},A_{2}>0$ such that for all $T\in\mathbb{Z}_{+}$,

$$ $\sum_{t=0}^{T}\|x_{t}\|\leq A_{1}\cdot w_{\text{max}}T+A_{2}.$ $$

###### Proof.

Since $\lim_{t\to\infty}H(t)<\infty$, there exists a constant $q_{1}$ that upper-bounds $H(t)$; i.e., $H(t)\leq q_{1}$ for all $t\geq 0$. Likewise, by Lemma [C.9](#A3.Thmtheorem9), there exists a constant $q_{2}$ that upper-bounds $\frac{B}{T}$. Thus, with Lemma [C.7](#A3.Thmtheorem7), one can write

$$ $\displaystyle\sum_{t=0}^{T}\|x_{t}\|$ $\displaystyle\leq O([L_{f}(1+L_{\pi})\beta(0)C]^{U}(\|x_{0}\|+q_{1}))+\gamma w_{\text{max}}\cdot(O(Bq_{1})+T)$ $\displaystyle=O([L_{f}(1+L_{\pi})\beta(0)C]^{U}(\|x_{0}\|+q_{1}))+\gamma(1+\frac{B}{T}O(q_{1}))\cdot w_{\text{max}}T$ $\displaystyle\leq O([L_{f}(1+L_{\pi})\beta(0)C]^{U}(\|x_{0}\|+q_{1}))+\gamma(1+O(q_{1}q_{2}))\cdot w_{\text{max}}T.$ $$

This completes the proof.
∎

###### Lemma C.1 (Restatement of Lemma 4.3 ) .

###### Proof.

###### Lemma C.2 .

###### Proof.

###### Lemma C.3 (Sum of state norms in a single batch) .

###### Proof.

###### Lemma C.4 (Weighted sum of state norms between the two consecutive Break statements) .

###### Proof.

###### Lemma C.5 (Next state norm after the Break statement) .

###### Proof.

###### Lemma C.6 (Weighted sum of state norms along the Break statements) .

###### Proof.

###### Lemma C.7 (Sum of state norms) .

###### Proof.

###### Theorem C.8 (Restatement of Theorem 4.1 , Asymptotic stability) .

###### Proof.

###### Lemma C.9 .

###### Proof.

###### Theorem C.10 (Restatement of Theorem 4.2 , Finite-gain stability) .

###### Proof.

## Appendix D Regret Proof for Algorithm 1

###### Lemma D.1 .

In Algorithm [1](#alg1), we have

$$ $\mathbb{E}_{K_{B-1:0}}[w_{b}(K_{b})]=\mathbb{E}_{K_{B-1:0}}[\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]],$ $$

###### Proof.

Given $K_{b-1},\dots,K_{0}$, we have

$$ $\displaystyle\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]=\sum_{k\in\mathcal{P}_{b}}p_{b}(k)\frac{w_{b}(K_{b})}{p_{b}(k)}\mathcal{I}_{(K_{b}=k)}=w_{b}(K_{b}),$ (18) $$

which implies that $w_{b}^{\prime}(k)$ sampled from $p_{b}$ is an unbiased estimator of $w_{b}(K_{b})$.

Thus, for all $b=0,1,\dots,B-1$, one can write

$$ $\displaystyle\mathbb{E}_{K_{B-1:0}}[w_{b}(K_{b})]$ $\displaystyle=\mathbb{E}_{K_{b:0}}[w_{b}(K_{b})]=\mathbb{E}_{K_{b-1:0}}\mathbb{E}_{K_{b}}[w_{b}(K_{b})~{}|~{}K_{b-1:0}]$ $\displaystyle=\mathbb{E}_{K_{b-1:0}}\mathbb{E}_{K_{b}}[\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]~{}|~{}K_{b-1:0}]$ $\displaystyle=\mathbb{E}_{K_{b:0}}[\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]]=\mathbb{E}_{K_{B-1:0}}[\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]],$ $$

where the first equality is because $K_{B-1},\dots,K_{b+1}$ does not affect the value of $w_{b}(K_{b})$ and the remaining equalities are by law of total expectation and ([18](#A4.E18)).
∎

Now, we let $w_{b}^{K}(i)$ denote the cost incurred at batch $b$ if one selects the controllers for batch $0,\dots,b-1$ according to Algorithm [1](#alg1), and the controller for batch $b$ to be $i$.

###### Lemma D.2 .

In Algorithm [1](#alg1), for any $i\in\mathcal{P}_{b}$, we have

$$ $\mathbb{E}_{K_{B-1:0}}[w_{b}^{\prime}(i)]=\mathbb{E}_{K_{B-1:0}}[w_{b}^{K}(i)]$ $$

and for some controller $i^{b}\in\mathcal{P}_{b}$, we have

$$ $\mathbb{E}_{K_{B-1:0}}\biggr{[}\frac{\eta_{0}}{2}\frac{(w_{b}(K_{b}))^{2}}{p_{b}(K_{b})}\biggr{]}\leq\frac{\eta_{0}N}{2}\mathbb{E}_{K_{b-1:0}}(w_{b}^{K}(i^{b}))^{2}.$ $$

###### Proof.

For all $b=0,1,\dots,B-1$ and for all $i\in\mathcal{P}_{b}$, we have

$$ $\displaystyle\mathbb{E}_{K_{B-1:0}}[w_{b}^{\prime}(i)]$ $\displaystyle=\mathbb{E}_{K_{b:0}}[w_{b}^{\prime}(i)]=\mathbb{E}_{K_{b-1:0}}[\mathbb{E}_{K_{b}}[w_{b}^{\prime}(i)~{}|~{}K_{b-1:0}]]$ $\displaystyle=\mathbb{E}_{K_{b-1:0}}[\sum_{K_{b}\in\mathcal{P}_{b}}p_{b}(K_{b})\frac{w_{b}(K_{b})}{p_{b}(i)}\mathcal{I}_{(K_{b}=i)}]$ $\displaystyle=\mathbb{E}_{K_{b-1:0}}[w_{b}^{K}(i)]=\mathbb{E}_{K_{B-1:0}}[w_{b}^{K}(i)]$ $$

where the first equality is because $K_{B-1},\dots,K_{b+1}$ does not affect the value of $w_{b}^{\prime}(i)$ and the last equality is because $K_{B-1},\dots,K_{b}$ does not affect the value of $w_{b}^{K}(i)$. Next, we can also obtain that

$$ $\displaystyle\mathbb{E}_{K_{B-1:0}}\biggr{[}\frac{\eta_{0}}{2}\frac{(w_{b}(K_{b}))^{2}}{p_{b}(K_{b})}\biggr{]}$ $\displaystyle=\mathbb{E}_{K_{b:0}}\biggr{[}\frac{\eta_{0}}{2}\frac{(w_{b}(K_{b}))^{2}}{p_{b}(K_{b})}\biggr{]}=\mathbb{E}_{K_{b-1:0}}\mathbb{E}_{K_{b}}\biggr{[}\frac{\eta_{0}}{2}\frac{(w_{b}(K_{b}))^{2}}{p_{b}(K_{b})}~{}|~{}K_{b-1:0}\biggr{]}$ $\displaystyle=\mathbb{E}_{K_{b-1:0}}\sum_{K_{b}\in\mathcal{P}_{b}}\biggr{[}\frac{\eta_{0}}{2}p_{b}(K_{b})\frac{(w_{b}(K_{b}))^{2}}{p_{b}(K_{b})}\biggr{]}=\mathbb{E}_{K_{b-1:0}}\sum_{K_{b}\in\mathcal{P}_{b}}\biggr{[}\frac{\eta_{0}}{2}(w_{b}(K_{b}))^{2}\biggr{]}$ $\displaystyle\leq\frac{\eta_{0}N}{2}\mathbb{E}_{K_{b-1:0}}(w_{b}^{K}(i^{b}))^{2},$ $$

for the controller $i^{b}=\arg\max_{i\in\mathcal{P}_{b}}(w_{b}^{K}(i))^{2}$. This completes the proof.
∎

In Algorithm [1](#alg1), define $\mathcal{L}:=\{0\leq b\leq B-1,~{}b\in\mathbb{Z}_{+}:s_{b+1}\neq s_{b}\}$ and
let $b^{1},\dots,b^{|\mathcal{L}|}$ denote the batch where Line [22](#alg1.l22) of Algorithm [1](#alg1) is satisfied; i.e., $s_{b^{l}+1}\neq s_{b^{l}}$ for $l=1,\dots,|\mathcal{L}|$. For convenience, we let $b^{0}=0$, $b^{|\mathcal{L}|+1}=B-1,$ and $s_{B}=s_{B-1}$.
Also, define $\mathcal{V}:=\{0\leq b\leq B-1,~{}b\in\mathbb{Z}_{+}:s_{b}\neq 0\}$.

###### Lemma D.3 (Restatement of Lemma 4.7 ) .

In Algorithm [1](#alg1), suppose that $\beta(\tau_{0})<1$ and let $U$ denote the number of times that the Break statement is activated. Then, it holds that $|\mathcal{L}|=O(U)$ and $|\mathcal{V}|=O(U)$.

###### Proof.

For every batch $b=0,\dots,B-1$, we have

$$ $\displaystyle\|x_{t_{b}}\|<(\alpha_{b})^{s_{b}+1}\|x_{0}\|+\delta$ (19) $$

by Lines [11](#alg1.l11)-[20](#alg1.l20). If the Break statement is not activated, since we designed $\delta\geq\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{0})}$, it yields that

$$ $\displaystyle\|x_{t_{b+1}}\|$ $\displaystyle\leq\beta(\tau_{b})\|x_{t_{b}}\|+\gamma w_{\text{max}}\leq\beta(\tau_{0})(\alpha_{b})^{s_{b}+1}\|x_{0}\|+\beta(\tau_{0})\delta+\gamma w_{\text{max}}$ $\displaystyle\leq\beta(\tau_{0})(\alpha_{b})^{s_{b}+1}\|x_{0}\|+\delta<(\alpha_{b})^{s_{b}+1}\|x_{0}\|+\delta,$ $$

where the second and the last inequalities are due to $\beta(\tau_{b})\leq\beta(\tau_{0})<1$ and the third inequality is by the formulation of $\delta$. Then, $s_{b+1}>s_{b}$ cannot occur when the Break statement is not activated. Also, Line [14](#alg1.l14) avoids $s_{b+1}>s_{b}+1$. As a result, starting from $s_{0}=0$, the event $s_{b+1}=s_{b}+1$ can occur at most $U$ times. Accordingly, the event $s_{b+1}<s_{b}$ also can occur at most $U$ times, leading to $|\mathcal{L}|\leq 2U$.

Now, we observe the number of batches $\tilde{b}$ needed to stabilize the state norm; i.e., $\min\{\tilde{b}>0:s_{b+\tilde{b}}<s_{b}\}$ when the Break statement is not activated. Starting from batch $b$ and the corresponding $s_{b}$, provided that the Break statement is not activated, one can write

$$ $\displaystyle\|x_{t_{b+\tilde{b}}}\|$ $\displaystyle\leq\beta(\tau_{b+\tilde{b}-1})\|x_{t_{b+\tilde{b}-1}}\|+\gamma w_{\text{max}}\leq\beta(\tau_{0})\|x_{t_{b+\tilde{b}-1}}\|+\gamma w_{\text{max}}$ $\displaystyle\leq(\beta(\tau_{0}))^{\tilde{b}}\|x_{t_{b}}\|+\gamma w_{\text{max}}\sum_{a=0}^{\tilde{b}-1}(\beta(\tau_{0}))^{a}\leq(\beta(\tau_{0}))^{\tilde{b}}\|x_{t_{b}}\|+\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{0})}$ $\displaystyle\leq(\beta(\tau_{0}))^{\tilde{b}}\|x_{t_{b}}\|+\delta<(\beta(\tau_{0}))^{\tilde{b}}[(\alpha_{b})^{s_{b}+1}\|x_{0}\|+\delta]+\delta,$ (20) $$

where the first and third inequalities are due to not satisfying Line [5](#alg1.l5) iteratively when the Break statement is not activated, the second and fourth inequalities are by $\beta(\tau_{b})\leq\beta(\tau_{0})<1$, and the last two inequalities are by the design of $\delta$ and ([19](#A4.E19)). It is desirable to find the minimum value of $\tilde{b}$ that makes the right-hand side of ([D](#A4.Ex75)) smaller than $(\alpha_{b})^{s_{b}}\|x_{0}\|+\delta$:

$$ $\displaystyle(\beta(\tau_{0}))^{\tilde{b}}[(\alpha_{b})^{s_{b}+1}\|x_{0}\|+\delta]+\delta\leq(\alpha_{b})^{s_{b}}\|x_{0}\|+\delta~{}~{}\Longleftrightarrow~{}~{}\frac{1}{(\beta(\tau_{0}))^{\tilde{b}}}\geq\alpha_{b}+\frac{\delta}{(\alpha_{b})^{s_{b}}\|x_{0}\|},$ (21) $$

where the right-hand side of ([21](#A4.E21)) can be upper-bounded by $\alpha_{b}+\frac{\delta}{\|x_{0}\|}$ since $\alpha_{b}>1$. Thus, if $s_{b}\neq 0$,

$$ $\displaystyle\min\{\tilde{b}>0:s_{b+\tilde{b}}<s_{b}\}\leq\Biggr{\lceil}\frac{\log(\alpha_{b}+\frac{\delta}{\|x_{0}\|})}{-\log\beta(\tau_{0})}\Biggr{\rceil},$ (22) $$

when the Break statement is not activated.
In other words, starting from a batch $b$ where $s_{b}>0$, within the number of batches on the right-hand side of ([22](#A4.E22)), either the Break statement is activated or the value of $s_{b}$ decreases.

More specifically, consider two sets of batches: $\mathcal{B}_{1}=\{0\leq b\leq B-1,b\in\mathbb{Z}_{+}:\text{the Break statement activated}\}$ and $\mathcal{B}_{2}=\{0\leq b\leq B-1,b\in\mathbb{Z}_{+}:s_{b+1}<s_{b}\}$. Let $\mathcal{B}=\mathcal{B}_{1}\cup\mathcal{B}_{2}$ be the set ordered by batch numbers. Then, the batch interval between two consecutive batches in $\mathcal{B}$ is upper-bounded by ([22](#A4.E22)).
Thus, considering that $|\mathcal{L}|\leq 2U$, we have

$$ $|\mathcal{V}|\leq(2U-1)\Biggr{\lceil}\frac{\log(\alpha_{b}+\frac{\delta}{\|x_{0}\|})}{-\log\beta(\tau_{0})}\Biggr{\rceil},$ $$

which completes the proof.
∎

###### Lemma D.4 (cumulative mix loss) .

In Algorithm [1](#alg1), for any controller $i^{l}\in\mathcal{U}^{c}$ for $l=0,\dots,|\mathcal{L}|$, the cumulative mix loss is upper-bounded as follows:

$$ $\mathbb{E}_{K_{B-1:0}}\sum_{b=0}^{B-1}-\frac{1}{\eta_{0}}\log(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{b}w_{b}^{\prime}(k)))\leq\frac{\tilde{O}(U+1)}{\eta_{0}}+\mathbb{E}_{K_{B-1:0}}\sum_{l=0}^{|\mathcal{L}|}\sum_{b=b^{l}}^{b^{l+1}-1}\frac{w_{b}^{K}(i^{l})}{(\alpha_{b})^{2s_{b}}}$ $$

###### Proof.

Given $l=0,\dots,|\mathcal{L}|$, we can analyze a single mix loss for $b=b^{l}+1,\dots,b^{l+1}-1$ as follows:

$$ $\displaystyle-\frac{1}{\eta_{0}}\log(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{b}w_{b}^{\prime}(k)))$ $\displaystyle=-\frac{1}{\eta_{0}}\log(\sum_{k\in\mathcal{P}_{b}}p_{b}(k)\exp(-\eta_{b}w_{b}^{\prime}(k)))$ $\displaystyle=-\frac{1}{\eta_{0}}\log(\frac{\sum_{k\in\mathcal{P}_{b}}\exp(-\eta_{b}W_{b}(k))\exp(-\eta_{b}w_{b}^{\prime}(k))}{\sum_{i\in\mathcal{P}_{b}}\exp(-\eta_{b}W_{b}(i))})$ $\displaystyle=-\frac{1}{\eta_{0}}\log(\frac{\sum_{k\in\mathcal{P}_{b}}\exp(-\eta_{b}W_{b+1}(k))}{\sum_{i\in\mathcal{P}_{b}}\exp(-\eta_{b}W_{b}(i))}),$ (23) $$

while a mix loss for $b=b^{l}$ is as follows:

$$ $\displaystyle-\frac{1}{\eta_{0}}\log(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{b^{l}}w_{b^{l}}^{\prime}(k)))$ $\displaystyle=-\frac{1}{\eta_{0}}\log(\sum_{k\in\mathcal{P}_{b^{l}}}p_{b^{l}}(k)\exp(-\eta_{b^{l}}w_{b^{l}}^{\prime}(k)))$ $\displaystyle=-\frac{1}{\eta_{0}}\log(\frac{1}{|\mathcal{P}_{b^{l}}|}\sum_{k\in\mathcal{P}_{b^{l}}}\exp(-\eta_{b^{l}}w_{b^{l}}^{\prime}(k)))$ $\displaystyle\leq\frac{\log N}{\eta_{0}}-\frac{1}{\eta_{0}}\log(\sum_{k\in\mathcal{P}_{b^{l}}}\exp(-\eta_{b^{l}}w_{b^{l}}^{\prime}(k)))$ (24) $\displaystyle=\frac{\log N}{\eta_{0}}-\frac{1}{\eta_{0}}\log(\sum_{k\in\mathcal{P}_{b^{l}}}\exp(-\eta_{b^{l}}W_{b^{l}+1}(k))),$ (25) $$

where the last equality only holds when $b^{l+1}>b^{l}+1$. Now, notice that the batches $b=b^{l},\dots,b^{l+1}-1$ share the same learning rate; i.e., $\eta_{b^{l}}=\dots=\eta_{b^{l+1}-1}$ since the same $s_{b}$ yields the same $\alpha_{b}$, and thus the same $\eta_{b}$. Thus, in the case where $b^{l+1}>b^{l}+1$, we have

$$ $\displaystyle\sum_{b=b^{l}}^{b^{l+1}-1}-\frac{1}{\eta_{0}}\log(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{b}w_{b}^{\prime}(k)))$ $\displaystyle\leq\frac{\log N}{\eta_{0}}-\frac{1}{\eta_{0}}\log(\Pi_{b=b^{l}+1}^{b^{l+1}-1}\frac{\sum_{k\in\mathcal{P}_{b-1}}\exp(-\eta_{b^{l}}W_{b}(k))}{\sum_{k\in\mathcal{P}_{b}}\exp(-\eta_{b^{l}}W_{b}(k))})$ $\displaystyle\hskip 85.35826pt-\frac{1}{\eta_{0}}\log(\sum_{k\in\mathcal{P}_{b^{l+1}-1}}\exp(-\eta_{b^{l}}W_{b^{l+1}}(k)))$ $\displaystyle\leq\frac{\log N}{\eta_{0}}-\frac{1}{\eta_{0}}\log(\sum_{k\in\mathcal{P}_{b^{l+1}-1}}\exp(-\eta_{b^{l}}W_{b^{l+1}}(k))),$ (26) $$

where the first inequality is by ([23](#A4.E23)) and ([25](#A4.E25)) and the second inequality comes from $\mathcal{P}_{b}\subseteq\mathcal{P}_{b-1}$. Considering both cases ([24](#A4.E24)) and ([26](#A4.E26)), for any controller $i^{0},\dots,i^{|\mathcal{L}|}\in\mathcal{U}^{c}$, one can write

$$ $\displaystyle\sum_{b=0}^{B-1}-\frac{1}{\eta_{0}}\log(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{b}w_{b}^{\prime}(k)))$ $\displaystyle\leq\sum_{l=0}^{|\mathcal{L}|}\biggr{[}\frac{\log N}{\eta_{0}}-\frac{1}{\eta_{0}}\log(\sum_{k\in\mathcal{P}_{b^{l+1}-1}}\exp(-\eta_{b^{l}}\sum_{b=b^{l}}^{b^{l+1}-1}w_{b}^{\prime}(k)))\biggr{]}$ $\displaystyle\leq\frac{(|\mathcal{L}|+1)\log N}{\eta_{0}}-\sum_{l=0}^{|\mathcal{L}|}\frac{1}{\eta_{0}}\log(\exp(-\eta_{b^{l}}\sum_{b=b^{l}}^{b^{l+1}-1}w_{b}^{\prime}(i^{l})))$ $\displaystyle=\frac{\tilde{O}(U+1)}{\eta_{0}}+\sum_{l=0}^{|\mathcal{L}|}\frac{\sum_{b=b^{l}}^{b^{l+1}-1}w_{b}^{\prime}(i^{l})}{(\alpha_{b^{l}})^{2s_{b^{l}}}},$ (27) $$

where the first inequality considers $W_{b^{l}+1}(k)=\sum_{b=b^{l}}^{b^{l+1}-1}w_{b}^{\prime}(k)$ in ([26](#A4.E26)), the second inequality is because any controller $i^{l}$ is an element of $\mathcal{P}_{b^{l+1}-1}$, and the last equality comes from the definition of $\eta_{b^{l}}=\eta_{0}/(\alpha_{b^{l}})^{2s_{b^{l}}}$ and $|\mathcal{L}|=O(U)$ by Lemma [D.3](#A4.Thmtheorem3). Finally, by Lemma [D.2](#A4.Thmtheorem2), taking the expectation of ([D](#A4.Ex86)) with respect to $K_{B-1:0}$ completes the proof.
∎

Now, we consider the cumulative mixability gap.

###### Lemma D.5 (cumulative mixability gap) .

In Algorithm [1](#alg1), there exists a set of controllers $i^{b}\in\mathcal{P}_{b}$ for $b=0,\dots,B-1$ such that the cumulative mixability gap is upper-bounded as follows:

$$ $\mathbb{E}_{K_{B-1:0}}\sum_{b=0}^{B-1}\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]+\frac{1}{\eta_{0}}\log(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{b}w_{b}^{\prime}(k)))\leq\frac{O(U)}{2\eta_{0}}+\frac{\eta_{0}N}{2}\sum_{b=0}^{B-1}\mathbb{E}_{K_{b-1:0}}(w_{b}^{K}(i^{b}))^{2}$ $$

###### Proof.

Given the set $\mathcal{V}$, we can analyze a single mixability gap for $b\notin\mathcal{V}$ and $b\in\mathcal{V}$, respectively. Since $s_{b}=0$ for $b\notin\mathcal{V}$, given $K_{b-1},\dots,K_{0}$, we have

$$ $\displaystyle\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]+\frac{1}{\eta_{0}}\log(\mathbb{E}_{k\sim p_{b}}\exp(-$ $\displaystyle\eta_{b}w_{b}^{\prime}(k)))=\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]+\frac{1}{\eta_{0}}\log(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{0}w_{b}^{\prime}(k)))$ $\displaystyle\leq\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]+\frac{1}{\eta_{0}}(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{0}w_{b}^{\prime}(k))-1)$ $\displaystyle\leq\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]+\frac{1}{\eta_{0}}(\mathbb{E}_{k\sim p_{b}}\frac{\eta_{0}^{2}(w_{b}^{\prime}(k))^{2}}{2}-\eta_{0}w_{b}^{\prime}(k))$ $\displaystyle=\frac{\eta_{0}}{2}\mathbb{E}_{k\sim p_{b}}[(w_{b}^{\prime}(k))^{2}]$ $\displaystyle=\frac{\eta_{0}}{2}\sum_{k\in\mathcal{P}_{b}}p_{b}(k)\frac{(w_{b}(K_{b}))^{2}}{(p_{b}(k))^{2}}\mathcal{I}_{(K_{b}=k)}=\frac{\eta_{0}}{2}\frac{(w_{b}(K_{b}))^{2}}{p_{b}(K_{b})},$ (28) $$

where the first inequality uses $\log(x)\leq x-1$ for all $x\in\mathbb{R}$ and the second inequality uses $e^{x}\leq 1+x+\frac{x^{2}}{2}$ for all $x\in\mathbb{R}$. Now, for $b\in\mathcal{V}$, given $K_{b-1},\dots,K_{0}$, we obtain that

$$ $\displaystyle\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]+\frac{1}{\eta_{0}}\log(\mathbb{E}_{k\sim p_{b}}\exp($ $\displaystyle-\eta_{b}w_{b}^{\prime}(k)))\leq\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]+\frac{1}{\eta_{0}}(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{b}w_{b}^{\prime}(k))-1)$ $\displaystyle\leq\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]$ $\displaystyle\leq\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]+\frac{1}{\eta_{0}}(\mathbb{E}_{k\sim p_{b}}\frac{\eta_{0}^{2}(w_{b}^{\prime}(k))^{2}}{2}-\eta_{0}w_{b}^{\prime}(k)+\frac{1}{2})$ $\displaystyle=\frac{\eta_{0}}{2}\mathbb{E}_{k\sim p_{b}}[(w_{b}^{\prime}(k))^{2}]+\frac{1}{2\eta_{0}}=\frac{\eta_{0}}{2}\frac{(w_{b}(K_{b}))^{2}}{p_{b}(K_{b})}+\frac{1}{2\eta_{0}},$ (29) $$

where the second inequality uses $e^{x}\leq 1$ for all $x\leq 0$ and the third inequality uses $\frac{x^{2}}{2}+x+\frac{1}{2}\geq 0$ for all $x\in\mathbb{R}$. Since $|\mathcal{V}|=O(U)$ by Lemma [D.3](#A4.Thmtheorem3), we have inequality ([D](#A4.Ex93)) holding at most $O(U)$ times and ([D](#A4.Ex89)) holding in the remaining batches among $b=0,\dots,B-1$. Finally, by Lemma [D.2](#A4.Thmtheorem2), taking expectation of ([D](#A4.Ex89)) and ([D](#A4.Ex93)) with respect to $K_{B-1:0}$ completes the proof.
∎

We let $x_{t}$ and $u_{t}$ denote the state and action sequence in the algorithm depending on the context. We let $x_{t}^{K}(i)$ and $u_{t}^{K}(i)$ for $t=t_{b},\dots,t_{b+1}-1$ denote
the state and action sequence
generated by selecting the controllers before batch $b$ according to Algorithm [1](#alg1), while selecting the controller $i$ at batch $b$.
Accordingly, we have $w_{b}^{K}(i)=\sum_{t=t_{b}}^{t_{b+1}-1}c_{t}(x_{t}^{K}(i),u_{t}^{K}(i))$. We also let $x_{t}^{*}$ and $u_{t}^{*}$ denote the optimal state and action sequence generated by the best stabilizing controller $i^{*}$ that satisfies both of Definitions [2.3](#S2.Thmtheorem3) and [2.4](#S2.Thmtheorem4); i.e., $i^{*}=\arg\min_{i\in\mathcal{S}}\sum_{t=0}^{T}c_{t}(x_{t},\pi_{i^{*}}(x_{t}))$ subject to the transition dynamics.

###### Lemma D.6 .

In Algorithm [1](#alg1), suppose that $\frac{\tau_{1}}{\tau_{0}}(\beta(\tau_{0}))^{2}<\frac{1}{2\sqrt{2}}$. For any controller $i^{b}\in\mathcal{P}_{b}$ for $b=0,\dots,B-1$, we have

$$ $\sum_{b=0}^{B-1}\mathbb{E}_{K_{b-1:0}}(w_{b}^{K}(i^{b}))^{2}=\exp(O(U))O(\tau_{B-1}H(\tau_{B-1}))+O(\sum_{b=0}^{B-1}(\tau_{b})^{2}).$ $$

###### Proof.

By Assumption [2.2](#S2.Thmtheorem2), for all $x\in\mathbb{R}^{n}$ and $u\in\mathbb{R}^{m}$, we have

$$ $\displaystyle|c_{t}(x,u)|$ $\displaystyle=|c_{t}(x,u)-c_{t}(0,0)+c_{t}(0,0)|\leq|c_{t}(x,u)-c_{t}(0,0)|+|c_{t}(0,0)|$ $\displaystyle\leq(L_{c_{1}}(\|x\|+\|u\|)+L_{c2})(\|x\|+\|u\|)+c_{0,\text{max}}$ $\displaystyle=L_{c_{1}}(\|x\|+\|u\|)^{2}+L_{c2}(\|x\|+\|u\|)+c_{0,\text{max}}$ $\displaystyle\leq 2L_{c_{1}}(\|x\|^{2}+\|u\|^{2})+L_{c2}(\|x\|+\|u\|)+c_{0,\text{max}},$ (30) $$

where the last inequality is due to Cauchy–Schwarz inequality. Thus, we can upper-bound $(w_{b}^{K}(i^{b}))^{2}$ for any controller $i^{b}\in\mathcal{P}_{b}$ for $b=0,\dots,B-1$ as follows:

$$ $\displaystyle(w_{b}^{K}(i^{b}))^{2}$ $\displaystyle=\biggr{[}\sum_{t=t_{b}}^{t_{b+1}-1}c_{t}(x_{t}^{K}(i^{b}),u_{t}^{K}(i^{b}))\biggr{]}^{2}\leq\sum_{t=t_{b}}^{t_{b+1}-1}c_{t}(x_{t}^{K}(i^{b}),u_{t}^{K}(i^{b}))^{2}(t_{b+1}-t_{b})$ $\displaystyle\leq(t_{b+1}-t_{b})\sum_{t=t_{b}}^{t_{b+1}-1}(2L_{c_{1}}(\|x_{t}^{K}(i^{b})\|^{2}+\|u_{t}^{K}(i^{b})\|^{2})+L_{c2}(\|x_{t}^{K}(i^{b})\|+\|u_{t}^{K}(i^{b})\|)+c_{0,\text{max}})^{2}$ $\displaystyle\leq 5(t_{b+1}-t_{b})\sum_{t=t_{b}}^{t_{b+1}-1}(4L_{c_{1}}^{2}(\|x_{t}^{K}(i^{b})\|^{4}+\|u_{t}^{K}(i^{b})\|^{4})+L_{c2}^{2}(\|x_{t}^{K}(i^{b})\|^{2}+\|u_{t}^{K}(i^{b})\|^{2})+c_{0,\text{max}}^{2})$ (31) $$

where the first and the third inequalities are due to Cauchy–Schwarz inequality.

From ([10](#A3.E10)), for $t_{b}<t\leq t_{b+1}-1$, we have

$$ $\displaystyle\|x_{t}^{K}(i^{b})\|^{2}\leq 2[\beta(t-t_{b})]^{2}\|x_{t_{b}}^{K}(i^{b})\|^{2}+2\gamma^{2}w_{\text{max}}^{2}$ (32) $\displaystyle\|x_{t}^{K}(i^{b})\|^{4}\leq 8[\beta(t-t_{b})]^{4}\|x_{t_{b}}^{K}(i^{b})\|^{4}+8\gamma^{4}w_{\text{max}}^{4},$ (33) $$

where the inequalities are by Cauchy-Schwarz inequality. Accordingly, we obtain that

$$ $\displaystyle\sum_{t=t_{b}}^{t_{b+1}-1}\|x_{t}^{K}(i^{b})\|^{2}\leq 2H(t_{b+1}-t_{b})\|x_{t_{b}}^{K}(i^{b})\|^{2}+2\gamma^{2}w_{\text{max}}^{2}(t_{b+1}-t_{b}-1)$ (34) $\displaystyle\sum_{t=t_{b}}^{t_{b+1}-1}\|x_{t}^{K}(i^{b})\|^{4}\leq 8H(t_{b+1}-t_{b})\|x_{t_{b}}^{K}(i^{b})\|^{4}+8\gamma^{4}w_{\text{max}}^{4}(t_{b+1}-t_{b}-1),$ (35) $$

where we use $\beta(\cdot)\leq 1$ to derive $\sum_{t=0}^{t_{b+1}-t_{b}-1}[\beta(t)]^{p}\leq\sum_{t=0}^{t_{b+1}-t_{b}-1}[\beta(t)]=H(t_{b+1}-t_{b})$ for $p\geq 1$.

From ([12](#A3.E12)), for $t_{b}\leq t\leq t_{b+1}-1$, we have

$$ $\displaystyle\|u_{t}^{K}(i^{b})\|^{2}\leq 2L_{\pi}^{2}\|x_{t}^{K}(i^{b})\|^{2}+2\pi_{0,\text{max}}^{2}$ (36) $\displaystyle\|u_{t}^{K}(i^{b})\|^{4}\leq 8L_{\pi}^{4}\|x_{t}^{K}(i^{b})\|^{4}+8\pi_{0,\text{max}}^{4},$ (37) $$

where the inequalities are by Cauchy-Schwarz inequality. Now, we substitute ([34](#A4.E34)), ([35](#A4.E35)), ([36](#A4.E36)), ([37](#A4.E37)), and $t_{b+1}-t_{b}\leq\tau_{b}$ into the right-hand side of ([D](#A4.Ex100)) to upper-bound $(w_{b}^{K}(i^{b}))^{2}$ as follows:

$$ $\displaystyle(w_{b}^{K}(i^{b}))^{2}$ $\displaystyle\leq 5\tau_{b}[32L_{c1}^{2}(1+8L_{\pi}^{4})H(\tau_{b})\|x_{t_{b}}^{K}(i^{b})\|^{4}+2L_{c2}^{2}(1+2L_{\pi}^{2})H(\tau_{b})\|x_{t_{b}}^{K}(i^{b})\|^{2}]+$ $\displaystyle 5\tau_{b}^{2}[32L_{c1}^{2}((1+8L_{\pi}^{4})\gamma^{4}w_{\text{max}}^{4}+\pi_{0,\text{max}}^{4})+2L_{c2}^{2}((1+2L_{\pi}^{2})\gamma^{2}w_{\text{max}}^{2}+\pi_{0,\text{max}}^{2})+c_{0,\text{max}}^{2}]$ $\displaystyle=M_{3}\tau_{b}H(\tau_{b})\|x_{t_{b}}^{K}(i^{b})\|^{4}+M_{4}\tau_{b}H(\tau_{b})\|x_{t_{b}}^{K}(i^{b})\|^{2}+M_{5}\tau_{b}^{2}$ $\displaystyle=M_{3}\tau_{b}H(\tau_{b})\|x_{t_{b}}\|^{4}+M_{4}\tau_{b}H(\tau_{b})\|x_{t_{b}}\|^{2}+M_{5}\tau_{b}^{2},$ (38) $$

where $M_{3},M_{4},M_{5}$ are constants determined by $L_{c1},L_{c2},L_{\pi},\gamma,w_{\text{max}},\pi_{0,\text{max}}$, and $c_{0,\text{max}}$. The last equality comes from $x_{t_{b}}^{K}(i^{b})=x_{t_{b}}$ for any $i^{b}\in\mathcal{P}_{b}$.

Meanwhile, one can upper-bound both $\sum_{b=0}^{B-1}\tau_{b}H(\tau_{b})\|x_{t_{b}}\|^{4}$ and $\sum_{b=0}^{B-1}\tau_{b}H(\tau_{b})\|x_{t_{b}}\|^{2}$ by successively applying Lemma [C.3](#A3.Thmtheorem3), [C.4](#A3.Thmtheorem4), and [C.6](#A3.Thmtheorem6) in the same fashion as presented in the proof of Lemma [C.7](#A3.Thmtheorem7). Since $\frac{\tau_{1}^{2}}{\tau_{0}^{2}}8(\beta(\tau_{0}))^{4}<1$, by ([32](#A4.E32)) and ([33](#A4.E33)), there exists $C_{1},C_{2}\geq 1$ such that

$$ $\displaystyle\sum_{b=0}^{B-1}\tau_{b}H(\tau_{b})\|x_{t_{b}}\|^{4}=O([8L_{f}^{4}(1+L_{\pi})^{4}\beta(0)^{4}C_{1}]^{U}(\|x_{0}\|^{4}+\tau_{b_{U}}H(\tau_{b_{U}})))+8\gamma^{4}w_{\text{max}}^{4}\cdot O(\sum_{b=0}^{B-1}\tau_{b}H(\tau_{b}))$ $\displaystyle\sum_{b=0}^{B-1}\tau_{b}H(\tau_{b})\|x_{t_{b}}\|^{2}=O([2L_{f}^{2}(1+L_{\pi})^{2}\beta(0)^{2}C_{2}]^{U}(\|x_{0}\|^{2}+\tau_{b_{U}}H(\tau_{b_{U}})))+2\gamma^{2}w_{\text{max}}^{2}\cdot O(\sum_{b=0}^{B-1}\tau_{b}H(\tau_{b})).$ $$

Substituting the equalities into the summation of ([D](#A4.Ex102)) for $b=0,\dots,B-1$ yields

$$ $\displaystyle\sum_{b=0}^{B-1}(w_{b}^{K}(i^{b}))^{2}=\exp(O(U))O(\tau_{b_{U}}H(\tau_{b_{U}}))+O(\sum_{b=0}^{B-1}\tau_{b}H(\tau_{b}))+O(\sum_{b=0}^{B-1}(\tau_{b})^{2}).$ (39) $$

Notice that taking expectation of $(w_{b}^{K}(i^{b}))^{2}$ with respect to $K_{b-1:0}$ does not affect the inequality. Finally, $\tau_{b_{U}}\leq\tau_{B-1}$ and $H(\tau_{b})=o(\tau_{b})$ completes the proof.
∎

###### Lemma D.7 .

In Algorithm [1](#alg1), for the best stabilizing controller $i^{*}\in\mathcal{S}$, we have

$$ $\mathbb{E}_{K_{B-1:0}}\sum_{b=0}^{B-1}\sum_{t=t_{b}}^{t_{b+1}-1}\biggr{[}\frac{c_{t}(x_{t}^{K}(i^{*}),u_{t}^{K}(i^{*}))}{(\alpha_{b})^{2s_{b}}}-c_{t}(x_{t}^{*},u_{t}^{*})\biggr{]}\leq O(U)+O(\sum_{b=0}^{B-1}H(\tau_{b})).$ $$

###### Proof.

Since $x_{t}^{*}$ is generated by a stabilizing controller, we have

$$ $\displaystyle\|x_{t}^{*}\|\leq\beta(t)\|x_{0}\|+\gamma w_{\text{max}}\leq\beta(0)\|x_{0}\|+\gamma w_{\text{max}}$ $\displaystyle\|x_{t}^{*}\|^{2}\leq 2\beta(t)^{2}\|x_{0}\|^{2}+2\gamma^{2}w_{\text{max}}^{2}\leq 2\beta(0)^{2}\|x_{0}\|^{2}+2\gamma^{2}w_{\text{max}}^{2},$ $$

where the inequalities are by Cauchy-Schwarz inequality and the non-increasing property of $\beta(\cdot)$. Then, by ([12](#A3.E12)), ([D](#A4.Ex97)), and ([36](#A4.E36)), we have

$$ $\displaystyle c_{t}(x_{t}^{*},u_{t}^{*})$ $\displaystyle\leq 2L_{c_{1}}(\|x_{t}^{*}\|^{2}+\|u_{t}^{*}\|^{2})+L_{c2}(\|x_{t}^{*}\|+\|u_{t}^{*}\|)+c_{0,\text{max}}$ $\displaystyle\leq 2L_{c_{1}}((1+2L_{\pi}^{2})\|x_{t}^{*}\|^{2}+2\pi_{0,\text{max}}^{2})+L_{c2}((1+L_{\pi})\|x_{t}^{*}\|+\pi_{0,\text{max}})+c_{0,\text{max}}$ $\displaystyle\leq 4L_{c1}(1+2L_{\pi}^{2})(\beta(0))^{2}\|x_{0}\|^{2}+L_{c2}(1+L_{\pi})\beta(0)\|x_{0}\|+4L_{c1}(1+2L_{\pi}^{2})\gamma^{2}w_{\text{max}}^{2}$ $\displaystyle\hskip 65.44133pt+L_{c2}(1+L_{\pi})\gamma w_{\text{max}}+4L_{c1}\pi_{0,\text{max}}^{2}+L_{c2}\pi_{0,\text{max}}+c_{0,\text{max}}:=M_{6}.$ (40) $$

In Algorithm [1](#alg1), one can write

$$ $\displaystyle\biggr{\|}\frac{x_{t_{b}}}{(\alpha_{b})^{s_{b}}}\biggr{\|}\leq\frac{(\alpha_{b})^{s_{b}+1}\|x_{0}\|+\delta}{(\alpha_{b})^{s_{b}}}\leq\alpha_{b}\|x_{0}\|+\delta$ (41) $\displaystyle\biggr{\|}\frac{x_{t}^{*}}{(\alpha_{b})^{s_{b}}}\biggr{\|}\leq\frac{\beta(t)\|x_{0}\|+\gamma w_{\text{max}}}{(\alpha_{b})^{s_{b}}}\leq\beta(0)\|x_{0}\|+\gamma w_{\text{max}},$ (42) $$

where the equalities hold for the last inequalities of ([41](#A4.E41)) and ([42](#A4.E42)) when $s_{b}=0$.

By Assumption [2.2](#S2.Thmtheorem2), for the best stabilizing controller $i^{*}\in\mathcal{S}$ and for $t_{b}\leq t<t_{b+1}$, we have

$$ $\displaystyle\frac{1}{(\alpha_{b})^{2s_{b}}}|c_{t}(x_{t}^{K}(i^{*}),u_{t}^{K}(i^{*}))-c_{t}(x_{t}^{*},u_{t}^{*})|$ $\displaystyle\leq\frac{1}{(\alpha_{b})^{2s_{b}}}(L_{c1}(\max\{\|x_{t}^{K}(i^{*})\|,\|x_{t}^{*}\|\}+\max\{\|u_{t}^{K}(i^{*})\|,\|u_{t}^{*}\|\})+L_{c2})(\|x_{t}^{K}(i^{*})-x_{t}^{*}\|+\|u_{t}^{K}(i^{*})-u_{t}^{*}\|)$ $\displaystyle\leq\frac{1}{(\alpha_{b})^{2s_{b}}}(L_{c1}((1+L_{\pi})\max\{\|x_{t}^{K}(i^{*})\|,\|x_{t}^{*}\|\}+\pi_{0,\text{max}})+L_{c2})(1+L_{\pi})\|x_{t}^{K}(i^{*})-x_{t}^{*}\|$ $\displaystyle=(1+L_{\pi})(L_{c1}(1+L_{\pi})\max\{\biggr{\|}\frac{x_{t}^{K}(i^{*})}{(\alpha_{b})^{s_{b}}}\biggr{\|},\biggr{\|}\frac{x_{t}^{*}}{(\alpha_{b})^{s_{b}}}\biggr{\|}\}+\frac{L_{c1}\pi_{0,\text{max}}+L_{c2}}{(\alpha_{b})^{s_{b}}})\biggr{\|}\frac{x_{t}^{K}(i^{*})-x_{t}^{*}}{(\alpha_{b})^{s_{b}}}\biggr{\|}$ $\displaystyle\leq(1+L_{\pi})(\beta(t-t_{b})L_{c1}(1+L_{\pi})\max\{\biggr{\|}\frac{x_{t_{b}}^{K}(i^{*})}{(\alpha_{b})^{s_{b}}}\biggr{\|},\biggr{\|}\frac{x_{t_{b}}^{*}}{(\alpha_{b})^{s_{b}}}\biggr{\|}\}$ $\displaystyle\hskip 113.81102pt+\frac{L_{c1}(1+L_{\pi})\gamma w_{\text{max}}+L_{c1}\pi_{0,\text{max}}+L_{c2}}{(\alpha_{b})^{s_{b}}})\cdot\beta(t-t_{b})\biggr{\|}\frac{x_{t_{b}}^{K}(i^{*})-x_{t_{b}}^{*}}{(\alpha_{b})^{s_{b}}}\biggr{\|}$ $\displaystyle\leq L_{c1}(1+L_{\pi})^{2}\beta(t-t_{b})^{2}\biggr{(}\biggr{\|}\frac{x_{t_{b}}}{(\alpha_{b})^{s_{b}}}\biggr{\|}+\biggr{\|}\frac{x_{t_{b}}^{*}}{(\alpha_{b})^{s_{b}}}\biggr{\|}\biggr{)}^{2}$ $\displaystyle\hskip 85.35826pt+\frac{L_{c1}(1+L_{\pi})\gamma w_{\text{max}}+L_{c1}\pi_{0,\text{max}}+L_{c2}}{(\alpha_{b})^{s_{b}}}(1+L_{\pi})\beta(t-t_{b})\biggr{(}\biggr{\|}\frac{x_{t_{b}}}{(\alpha_{b})^{s_{b}}}\biggr{\|}+\biggr{\|}\frac{x_{t_{b}}^{*}}{(\alpha_{b})^{s_{b}}}\biggr{\|}\biggr{)}$ $\displaystyle\leq L_{c1}(1+L_{\pi})^{2}\beta(t-t_{b})^{2}((\alpha_{b}+\beta(0))\|x_{0}\|+\delta+\gamma w_{\text{max}})^{2}$ $\displaystyle\hskip 42.67912pt+(L_{c1}(1+L_{\pi})\gamma w_{\text{max}}+L_{c1}\pi_{0,\text{max}}+L_{c2})(1+L_{\pi})\beta(t-t_{b})((\alpha_{b}+\beta(0))\|x_{0}\|+\delta+\gamma w_{\text{max}})$ $\displaystyle\leq M_{7}\beta(t-t_{b})^{2}+M_{8}\beta(t-t_{b}),$ (43) $$

where $M_{7}$ and $M_{8}$ are constants determined by $L_{c1},L_{c2},L_{\pi},\pi_{0,\text{max}},\beta(0),\delta,\gamma,w_{\text{max}}$ and $\max_{b\in\{0,1,\dots,B-1\}}\alpha_{b}$. Notice that $\alpha_{b}$ in Line [14](#alg1.l14) of Algorithm [1](#alg1) is upper-bounded by some constant by Lemma [C.5](#A3.Thmtheorem5). The second inequality is by ([12](#A3.E12)), the third inequality is due to Definition [2.4](#S2.Thmtheorem4) and by leveraging the same stabilizing controller $i^{*}$ from $t_{b}$ for both trajectories $x_{t}^{K}(i^{*})$ and $x_{t}^{*}$, the fourth inequality uses $x_{t_{b}}^{K}(i^{*})=x_{t_{b}}$, and the fifth inequality is by ([41](#A4.E41)) and ([42](#A4.E42)). By combining ([D](#A4.Ex110)) and ([D](#A4.Ex113)), we have

$$ $\displaystyle\biggr{|}\frac{c_{t}(x_{t}^{K}(i^{*}),u_{t}^{K}(i^{*}))}{(\alpha_{b})^{2s_{b}}}-c_{t}(x_{t}^{*},u_{t}^{*})\biggr{|}$ $\displaystyle=\biggr{|}\frac{c_{t}(x_{t}^{K}(i^{*}),u_{t}^{K}(i^{*}))}{(\alpha_{b})^{2s_{b}}}-\frac{c_{t}(x_{t}^{*},u_{t}^{*})}{(\alpha_{b})^{2s_{b}}}-\frac{(\alpha_{b})^{2s_{b}}-1}{(\alpha_{b})^{2s_{b}}}c_{t}(x_{t}^{*},u_{t}^{*})\biggr{|}$ $\displaystyle\leq\frac{1}{(\alpha_{b})^{2s_{b}}}|c_{t}(x_{t}^{K}(i^{*}),u_{t}^{K}(i^{*}))-c_{t}(x_{t}^{*},u_{t}^{*})|+\frac{(\alpha_{b})^{2s_{b}}-1}{(\alpha_{b})^{2s_{b}}}c_{t}(x_{t}^{*},u_{t}^{*})$ $\displaystyle\leq\begin{dcases*}M_{7}\beta(t-t_{b})^{2}+M_{8}\beta(t-t_{b}),&if $s_{b}=0$,\\ M_{7}\beta(t-t_{b})^{2}+M_{8}\beta(t-t_{b})+M_{6},&if $s_{b}\neq 0$.\end{dcases*}$ $$

Thus, one can conclude that

$$ $\displaystyle\sum_{b=0}^{B-1}\sum_{t=t_{b}}^{t_{b+1}-1}\biggr{[}\frac{c_{t}(x_{t}^{K}(i^{*}),u_{t}^{K}(i^{*}))}{(\alpha_{b})^{2s_{b}}}-c_{t}(x_{t}^{*},u_{t}^{*})\biggr{]}$ $\displaystyle\leq M_{6}|\mathcal{V}|+\sum_{b=0}^{B-1}(M_{7}+M_{8})H(t_{b+1}-t_{b})$ $\displaystyle=O(U)+O(\sum_{b=0}^{B-1}H(\tau_{b})),$ (44) $$

where the first inequality uses $\beta(\cdot)\leq 1$ to derive $\sum_{t=t_{b}}^{t_{b+1}-1}[\beta(t-t_{b})]^{2}\leq\sum_{t=t_{b}}^{t_{b+1}-1}[\beta(t-t_{b})]=H(t_{b+1}-t_{b})$ and the last equality uses $t_{b+1}-t_{b}\leq\tau_{b}$ and Lemma [D.3](#A4.Thmtheorem3). Taking expectation of ([D](#A4.Ex126)) with respect to $K_{B-1:0}$ completes the proof.
∎

###### Theorem D.8 (Restatement of Theorem 4.5 , Regret Bound) .

In Algorithm [1](#alg1), suppose that $\frac{\tau_{1}}{\tau_{0}}(\beta(\tau_{0}))^{2}<\frac{1}{2\sqrt{2}}$. Then, the regret bound is as follows:

$$ $\displaystyle\mathbb{E}_{K_{B-1:0}}\sum_{t=0}^{T}[c_{t}(x_{t},u_{t})-c_{t}(x_{t}^{*},u_{t}^{*})]$ $\displaystyle=O(|\mathcal{U}|)+O(\sum_{b=0}^{B-1}H(\tau_{b}))+\frac{\tilde{O}(|\mathcal{U}|+1)}{\eta_{0}}+\frac{\eta_{0}N}{2}[\exp(O(|\mathcal{U}|))O(\tau_{B-1}H(\tau_{B-1}))+O(\sum_{b=0}^{B-1}(\tau_{b})^{2})].$ $$

###### Proof.

By Lemma [D.1](#A4.Thmtheorem1), we have

$$ $\displaystyle\mathbb{E}_{K_{B-1:0}}\sum_{t=0}^{T}c_{t}(x_{t},u_{t})$ $\displaystyle=\mathbb{E}_{K_{B-1:0}}\sum_{b=0}^{B-1}\sum_{t=t_{b}}^{t_{b+1}-1}c_{t}(x_{t},u_{t})=\mathbb{E}_{K_{B-1:0}}\sum_{b=0}^{B-1}[w_{b}(K_{b})]$ $\displaystyle=\mathbb{E}_{K_{B-1:0}}\sum_{b=0}^{B-1}[\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]]$ $\displaystyle\leq\frac{\tilde{O}(U+1)}{\eta_{0}}+\frac{\eta_{0}N}{2}\sum_{b=0}^{B-1}\mathbb{E}_{K_{b-1:0}}(w_{b}^{K}(i^{b}))^{2}+\mathbb{E}_{K_{B-1:0}}\sum_{l=0}^{|\mathcal{L}|}\sum_{b=b^{l}}^{b^{l+1}-1}\frac{w_{b}^{K}(i^{*})}{(\alpha_{b})^{2s_{b}}}$ $\displaystyle\leq\frac{\tilde{O}(U+1)}{\eta_{0}}+\frac{\eta_{0}N}{2}[\exp(O(U))O(\tau_{B-1}H(\tau_{B-1}))+O(\sum_{b=0}^{B-1}(\tau_{b})^{2})]$ $\displaystyle\hskip 76.82243pt+O(U)+O(\sum_{b=0}^{B-1}H(\tau_{b}))+\mathbb{E}_{K_{B-1:0}}\sum_{t=0}^{T}c_{t}(x^{*},u^{*}),$ $$

where the first inequality is due to Lemma [D.4](#A4.Thmtheorem4) and [D.5](#A4.Thmtheorem5), and the last inequality is due to Lemma [D.6](#A4.Thmtheorem6) and [D.7](#A4.Thmtheorem7). Using $U\leq|\mathcal{U}|$ completes the proof.
∎

###### Theorem D.9 (Restatement of Theorem 4.6 , Regret bound with known $|\mathcal{U}|$ ) .

In Algorithm [1](#alg1), let $\tau_{0}=\lfloor(\frac{z}{N(|\mathcal{U}|+1)})^{1/2}\rfloor$ and $\tau_{b}=\lceil(\frac{(\nu b+z)}{N(|\mathcal{U}|+1)})^{1/2}\rceil$ for every $b\geq 1$ with the constants $z,\nu>0$ that satisfies $\tau_{0}>0$ and $\frac{\tau_{1}}{\tau_{0}}(\beta(\tau_{0}))^{2}<\frac{1}{2\sqrt{2}}$. Also, let $\eta_{0}=O(\frac{(|\mathcal{U}|+1)^{2/3}}{T^{2/3}N^{1/3}})$. When $T\geq\max\{\frac{|\mathcal{U}|^{3/2}}{(N(|\mathcal{U}|+1))^{1/2}},N(|\mathcal{U}|+1)\}$, we have

$$ $\mathbb{E}_{K_{B-1:0}}\sum_{t=0}^{T}[c_{t}(x_{t},u_{t})-c_{t}(x_{t}^{*},u_{t}^{*})]=\tilde{O}(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3}))+o(1)\exp(O(|\mathcal{U}|))+o(T),$ $$

which implies that we achieve a sublinear regret bound. Moreover, when $H(t)\leq O(\sum_{i=1}^{t}\frac{1}{i})$ for all $t\geq 1$, we have

$$ $\mathbb{E}_{K_{B-1:0}}\sum_{t=0}^{T}[c_{t}(x_{t},u_{t})-c_{t}(x_{t}^{*},u_{t}^{*})]=\bigr{[}\tilde{O}(T^{2/3})+\tilde{O}(T^{-1/3})\exp(O(|\mathcal{U}|))\bigr{]}N^{1/3}(|\mathcal{U}|+1)^{1/3}.$ $$

###### Proof.

By the formulation of $(\tau_{b})_{b\geq 0}$, we have

$$ $\displaystyle\sum_{b=0}^{B-1}\frac{(\nu b+z)^{1/2}}{(N(|\mathcal{U}|+1))^{1/2}}-1\leq\sum_{b=0}^{B-1}\tau_{b}=T\leq\sum_{b=0}^{B-1}\frac{(\nu b+z)^{1/2}}{(N(|\mathcal{U}|+1))^{1/2}}+(B-1),$ $$

where we can further use non-decreasing property of $(\cdot)^{1/2}$ to arrive at

$$ $\displaystyle\frac{z^{1/2}+\frac{2}{3\nu}[(\nu(B-1)+z)^{3/2}-z^{3/2}]}{(N(|\mathcal{U}|+1))^{1/2}}-1=\frac{z^{1/2}+\int_{0}^{B-1}(\nu b+z)^{1/2}db}{(N(|\mathcal{U}|+1))^{1/2}}-1\leq T$ $\displaystyle\hskip 85.35826pt\leq\frac{\int_{0}^{B}(\nu b+z)^{1/2}db}{(N(|\mathcal{U}|+1))^{1/2}}+(B-1)=\frac{\frac{2}{3\nu}[(\nu B+z)^{3/2}-z^{3/2}]}{(N(|\mathcal{U}|+1))^{1/2}}+(B-1),$ (45) $$

thus we have $B=O(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3})$ from the first inequality and $T=O(B^{3/2}N^{-1/2}(|\mathcal{U}|+1)^{-1/2})$ from the second inequality and $T\geq N(|\mathcal{U}|+1)$. Similarly, we can find the order of $\sum_{b=0}^{B-1}(\tau_{b})^{2}$ as follows:

$$ $\displaystyle\sum_{b=0}^{B-1}(\tau_{b})^{2}\leq\sum_{b=0}^{B-1}\biggr{[}\frac{(\nu b+z)^{1/2}}{(N(|\mathcal{U}|+1))^{1/2}}+1$ $\displaystyle\biggr{]}^{2}\leq\int_{0}^{B}\biggr{[}\frac{(\nu b+z)}{(N(|\mathcal{U}|+1))}+\frac{2(\nu b+z)^{1/2}}{(N(|\mathcal{U}|+1))^{1/2}}+1\biggr{]}db$ $\displaystyle=O(\frac{B^{2}}{N(|\mathcal{U}|+1)})=O(T^{4/3}N^{-1/3}(|\mathcal{U}|+1)^{-1/3}),$ (46) $$

where the last equality is by $B=O(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3})$. We also have

$$ $\displaystyle\tau_{B-1}=\lceil(\frac{(\nu(B-1)+z)}{N(|\mathcal{U}|+1)})^{1/2}\rceil=O(B^{1/2}N^{-1/2}(|\mathcal{U}|+1)^{-1/2})=O(T^{1/3}N^{-1/3}(|\mathcal{U}|+1)^{-1/3}).$ (47) $$

Thus, we have

$$ $\displaystyle O(\tau_{B-1}H(\tau_{B-1}))=o((\tau_{B-1})^{2})=o(T^{2/3}N^{-2/3}(|\mathcal{U}|+1)^{-2/3})=\frac{o(1)}{\eta_{0}N},$ (48) $$

where the first equality is due to Lemma [C.1](#A3.Thmtheorem1). With $T\geq\frac{|\mathcal{U}|^{3/2}}{(N(|\mathcal{U}|+1))^{1/2}}$, we have

$$ $\displaystyle\eta_{0}N\exp(O(|\mathcal{U}|))O(\tau_{B-1}H(\tau_{B-1}))=o(1)\exp(O(|\mathcal{U}|))$ (49) $\displaystyle O(|\mathcal{U}|)=O(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3}).$ (50) $$

With ([D](#A4.Ex138)), ([48](#A4.E48)), ([49](#A4.E49)), and ([50](#A4.E50)), we can apply Theorem [D.8](#A4.Thmtheorem8) to derive

$$ $\mathbb{E}_{K_{B-1:0}}\sum_{t=0}^{T}[c_{t}(x_{t},u_{t})-c_{t}(x_{t}^{*},u_{t}^{*})]=\tilde{O}(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3})+o(1)\exp(O(|\mathcal{U}|))+O(\sum_{b=0}^{B-1}H(\tau_{b})).$ $$

Applying ([C](#A3.Ex51)) to $O(\sum_{b=0}^{B-1}H(\tau_{b}))$ achieves a sublinear regret bound.

Moreover, when $\lim_{t\to\infty}H(t)<\infty$, there exists a constant $q_{1}$ that upper-bounds $H(t)$; i.e., $H(t)\leq q_{1}$ for all $t\geq 0$. Then, we have

$$ $\displaystyle\sum_{b=0}^{B-1}H(\tau_{b})\leq q_{1}B=O(B)=O(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3}).$ (51) $$

Also, ([48](#A4.E48)) and ([49](#A4.E49)) can be modified to

$$ $\displaystyle\tau_{B-1}H(\tau_{B-1})\leq q_{1}\tau_{B-1}=O(T^{1/3}N^{-1/3}(|\mathcal{U}|+1)^{-1/3}),$ $\displaystyle\eta_{0}N\exp(O(|\mathcal{U}|)))O(\tau_{B-1}H(\tau_{B-1}))=O(T^{-1/3}N^{1/3}(|\mathcal{U}|+1)^{1/3})\cdot\exp(O(|\mathcal{U}|)).$ (52) $$

Similarly, when $H(t)=O(\sum_{i=1}^{t}\frac{1}{i})$ for all $t\geq 1$, we have

$$ $\displaystyle\sum_{b=0}^{B-1}H(\tau_{b})\leq BH(\tau_{B-1})=O(B\log\tau_{B-1})=\tilde{O}(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3}),$ (53) $\displaystyle\eta_{0}N\exp(O(|\mathcal{U}|)))O(\tau_{B-1}H(\tau_{B-1}))=\tilde{O}(T^{-1/3}N^{1/3}(|\mathcal{U}|+1)^{1/3})\cdot\exp(O(|\mathcal{U}|)).$ (54) $$

Using ([51](#A4.E51)), ([D](#A4.Ex140)), equation [53](#A4.E53), and equation [54](#A4.E54) completes the proof.
∎

Small modification provides the regret bound for the intermediate step "Dynamic Batching" mentioned in Appendix [A](#A1).

###### Corollary D.10 .

Consider "Dynamic Batching" strategy without adaptive learning rate, i.e. $s_{b}=0$ for all $b=0,\dots,B-1$ in Algorithm [1](#alg1). Let $\tau_{0},\dots,\tau_{B-1}$ and $\eta_{0}$ be the same quantity with Theorem [D.9](#A4.Thmtheorem9). When $T\geq\max\{\frac{|\mathcal{U}|^{3/2}}{(N(|\mathcal{U}|+1))^{1/2}},N(|\mathcal{U}|+1)\}$, the term $o(1)\exp(O(|\mathcal{U}|))$ in the regret bound of Theorem [D.9](#A4.Thmtheorem9) is replaced by $o(T^{1/3})\exp(O(|\mathcal{U}|))$.

###### Proof.

Since $s_{b}=0$ for all $b$, we need to modify Lemma [D.7](#A4.Thmtheorem7). Equation equation [D](#A4.Ex113) is modified to

$$ $\displaystyle|c_{t}(x_{t}^{K}(i^{*}),u_{t}^{K}(i^{*}))-c_{t}(x_{t}^{*},u_{t}^{*})|\leq L_{c1}(1$ $\displaystyle+L_{\pi})^{2}\beta(t-t_{b})^{2}(\|x_{t_{b}}\|+\|x_{t_{b}}^{*}\|)^{2}+L_{c1}(1+L_{\pi})\gamma w_{\text{max}}$ $\displaystyle+L_{c1}\pi_{0,\text{max}}+L_{c2}(1+L_{\pi})\beta(t-t_{b})(\|x_{t_{b}}\|+\|x_{t_{b}}^{*}\|),$ $$

which incurs

$$ $\displaystyle\sum_{t=t_{b}}^{t_{b+1}-1}|c_{t}(x_{t}^{K}(i^{*}),u_{t}^{K}(i^{*}))-c_{t}(x_{t}^{*},u_{t}^{*})|\leq O(H(\tau_{b})\|x_{t_{b}}\|^{2})+O(H(\tau_{b})\|x_{t_{b}}\|)+O(H(\tau_{b})).$ $$

Thus, it follows that

$$ $\displaystyle\sum_{b=0}^{B-1}\sum_{t=t_{b}}^{t_{b+1}-1}|c_{t}(x_{t}^{K}(i^{*}),u_{t}^{K}(i^{*}))-c_{t}(x_{t}^{*},u_{t}^{*})|$ $\displaystyle\leq\exp(O(|\mathcal{U}|))(\|x_{0}\|^{2}+\|x_{0}\|)+\exp(O(|\mathcal{U}|))H(\tau_{B-1})$ $\displaystyle=\exp(O(|\mathcal{U}|))\cdot o(T^{1/3}),$ $$

where the last equality is by the choice of $\tau_{B-1}=O(B^{1/2})=O(T^{1/3})$ and applying Lemma [4.3](#S4.Thmtheorem3). This shows that $o(1)\exp(O(|\mathcal{U}|))$ in Theorem [D.9](#A4.Thmtheorem9) should be replaced by $o(T^{1/3})\exp(O(|\mathcal{U}|))$ in the algorithm without adaptive learning rate.
∎

###### Lemma D.1 .

###### Proof.

###### Lemma D.2 .

###### Proof.

###### Lemma D.3 (Restatement of Lemma 4.7 ) .

###### Proof.

###### Lemma D.4 (cumulative mix loss) .

###### Proof.

###### Lemma D.5 (cumulative mixability gap) .

###### Proof.

###### Lemma D.6 .

###### Proof.

###### Lemma D.7 .

###### Proof.

###### Theorem D.8 (Restatement of Theorem 4.5 , Regret Bound) .

###### Proof.

###### Theorem D.9 (Restatement of Theorem 4.6 , Regret bound with known | 𝒰 | 𝒰 |\mathcal{U}| ) .

###### Proof.

###### Corollary D.10 .

###### Proof.

## Appendix E Regret Proof for Algorithm 2

###### Theorem E.1 (Restatement of Theorem 4.10 , Regret bound with unknown $|\mathcal{U}|$ ) .

In Algorithm [2](#alg2), let $\tau_{0}=\lfloor(\frac{z}{N})^{1/2}\rfloor$ and $\tau_{b}=\lceil(\frac{(\nu b+z)}{N})^{1/2}\rceil$ for every $b\geq 1$ with the constants $z,\nu>0$ that satisfies $\tau_{0}>0$ and $\frac{\tau_{1}}{\tau_{0}}(\beta(\tau_{0}))^{2}<\frac{1}{2\sqrt{2}}$. Also, let $\eta_{0}=O(\frac{1}{T^{2/3}N^{1/3}})$ and $y=\frac{1}{2}$. When $T\geq\max\{\frac{|\mathcal{U}|^{3/2}}{N^{1/2}(|\mathcal{U}|+1)^{3/4}},N\}$, we have

$$ $\mathbb{E}_{K_{B-1:0}}\sum_{t=0}^{T}[c_{t}(x_{t},u_{t})-c_{t}(x_{t}^{*},u_{t}^{*})]=\tilde{O}(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/2})+o(1)\exp(O(|\mathcal{U}|))(|\mathcal{U}|+1)^{1/2}+o(T),$ $$

which implies that we achieve a sublinear regret bound. Moreover, when $H(t)\leq O(\sum_{i=1}^{t}\frac{1}{i})$ for all $t\geq 1$, we have

$$ $\mathbb{E}_{K_{B-1:0}}\sum_{t=0}^{T}[c_{t}(x_{t},u_{t})-c_{t}(x_{t}^{*},u_{t}^{*})]=\bigr{[}\tilde{O}(T^{2/3})+\tilde{O}(T^{-1/3})\exp(O(|\mathcal{U}|))\bigr{]}N^{1/3}(|\mathcal{U}|+1)^{1/2}$ $$

###### Proof.

By the formulation of $(\tau_{b})_{b\geq 0}$, as in ([D](#A4.Ex137)), we can derive

$$ $\displaystyle B=O(T^{2/3}N^{1/3})\quad\text{and}\quad T=O(B^{3/2}N^{-1/2})$ $$

when $T\geq N$. We can also obtain

$$ $\displaystyle\sum_{b=0}^{B-1}(\tau_{b})^{2}=O(T^{4/3}N^{-1/3})\quad\text{and}\quad O(\tau_{B-1}H(\tau_{B-1}))=o(T^{2/3}N^{-2/3})$ $$

similar to ([D](#A4.Ex138)) and ([48](#A4.E48)). Now, define $\eta_{0,r}:=\eta_{0}(r+1)^{y}=\eta_{0}\sqrt{r+1}$. Let $\mathcal{B}_{r}$ denote the set of batches where $\mu_{b}=r$; i.e., $\mathcal{B}_{r}=\{0\leq b\leq B-1,~{}b\in\mathbb{Z}_{+}:\mu_{b}=r\}$. Then, one can write

$$ $\displaystyle\frac{N}{2}\sum_{r=0}^{U}\sum_{b\in\mathcal{B}_{r}}$ $\displaystyle\eta_{0,r}\mathbb{E}_{K_{b-1:0}}(w_{b}^{K}(i^{b}))^{2}\leq\frac{\eta_{0}N}{2}\sum_{r=0}^{U}\sum_{b\in\mathcal{B}_{r}}\sqrt{U+1}\mathbb{E}_{K_{b-1:0}}(w_{b}^{K}(i^{b}))^{2}$ $\displaystyle=\sqrt{U+1}\cdot O(T^{-2/3}N^{2/3})[\exp(O(U))O(\tau_{B-1}H(\tau_{B-1}))+O(\sum_{b=0}^{B-1}(\tau_{b})^{2})]$ $\displaystyle\leq\sqrt{|\mathcal{U}|+1}\cdot[o(1)\exp(O(|\mathcal{U}|))+O(T^{2/3}N^{1/3})],$ (55) $$

where the first equality holds by Lemma [D.6](#A4.Thmtheorem6) and the second inequality holds by $U\leq|\mathcal{U}|$.

Recall the definition and the cardinality of $\mathcal{L}=\{0\leq b\leq B-1,~{}b\in\mathbb{Z}_{+}:s_{b+1}\neq s_{b}\}$ and $\mathcal{V}=\{0\leq b\leq B-1,~{}b\in\mathbb{Z}_{+}:s_{b}\neq 0\}$ in Lemma [D.3](#A4.Thmtheorem3). We focus on the mix loss and the mixability gap with the denominator $\eta_{0,r}$; i.e., $-\frac{1}{\eta_{0,r}}\log(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{b}w_{b}^{\prime}(k)))$ and $\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]+\frac{1}{\eta_{0,r}}\log(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{b}w_{b}^{\prime}(k)))$. Considering that $\frac{\eta_{b}}{\eta_{0,r}}$ still remains to be $\frac{1}{(\alpha_{b})^{2s_{b}}}$ as in Algorithm [1](#alg1), Lemma [D.4](#A4.Thmtheorem4) can be modified to

$$ $\displaystyle\mathbb{E}_{K_{B-1:0}}\sum_{r=0}^{U}\sum_{b\in\mathcal{B}_{r}}-\frac{1}{\eta_{0,r}}\log(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{b}w_{b}^{\prime}(k)))\leq\sum_{r=0}^{U}\frac{\rho_{r}^{l}\log N}{\eta_{0,r}}+\mathbb{E}_{K_{B-1:0}}\sum_{l=0}^{|\mathcal{L}|}\sum_{b=b^{l}}^{b^{l+1}-1}\frac{w_{b}^{K}(i^{l})}{(\alpha_{b})^{2s_{b}}},$ (56) $$

where $\rho_{r}^{l}$ denotes the number of batches in $\mathcal{B}_{r}\cap\mathcal{L}$. Similarly, considering that $\eta_{0,r}$ now depends on the value of $r$, Lemma [D.5](#A4.Thmtheorem5) can be modified to

$$ $\displaystyle\mathbb{E}_{K_{B-1:0}}\sum_{r=0}^{U}\sum_{b\in\mathcal{B}_{r}}\mathbb{E}_{k\sim p_{b}}[w_{b}^{\prime}(k)]+\frac{1}{\eta_{0,r}}\log(\mathbb{E}_{k\sim p_{b}}\exp(-\eta_{b}w_{b}^{\prime}(k)))$ $\displaystyle\hskip 142.26378pt\leq\sum_{r=0}^{U}\frac{\rho_{r}^{v}}{2\eta_{0,r}}+\frac{N}{2}\sum_{r=0}^{U}\sum_{b\in\mathcal{B}_{r}}\eta_{0,r}\mathbb{E}_{K_{b-1:0}}(w_{b}^{K}(i^{b}))^{2},$ (57) $$

where $\rho_{r}^{v}$ denotes the number of batches in $\mathcal{B}_{r}\cap\mathcal{V}$. Now, our goal is to upper-bound $\sum_{r=0}^{U}\frac{\rho_{r}^{l}}{\eta_{0,r}}=\frac{1}{\eta_{0}}\sum_{r=0}^{U}\frac{\rho_{r}^{l}\log N}{\sqrt{r+1}}$ in ([56](#A5.E56)) and $\sum_{r=0}^{U}\frac{\rho_{r}^{v}}{\eta_{0,r}}=\frac{1}{\eta_{0}}\sum_{r=0}^{U}\frac{\rho_{r}^{v}}{\sqrt{r+1}}$ in ([E](#A5.Ex152)). It is straightforward to infer that $\rho_{0}^{l}+\rho_{1}^{l}+\dots+\rho_{U}^{l}\leq 2U+1$ by Lemma [D.3](#A4.Thmtheorem3) and ([D](#A4.Ex86)), which also leads to $\rho_{0}^{l}+\rho_{1}^{l}+\dots+\rho_{r}^{l}\leq 2r+1$ for $r=0,\dots,U$. Similarly, we can infer that $\rho_{0}^{v}=0$ and $\rho_{1}^{v}+\dots+\rho_{U}^{v}\leq(2U-1)\lceil\frac{\log(\alpha_{b}+\frac{\delta}{\|x_{0}\|})}{-\log\beta(\tau_{0})}\rceil$ by Lemma [D.3](#A4.Thmtheorem3) and ([D](#A4.Ex93)), which also leads to $\rho_{1}^{v}+\dots+\rho_{r}^{v}\leq(2r-1)\lceil\frac{\log(\alpha_{b}+\frac{\delta}{\|x_{0}\|})}{-\log\beta(\tau_{0})}\rceil$ for $r=1,\dots,U$. Define $M_{9}:=\lceil\frac{\log(\alpha_{b}+\frac{\delta}{\|x_{0}\|})}{-\log\beta(\tau_{0})}\rceil$ and consider the following maximization problems to get the upper bound.

$$ $\displaystyle l^{*}=\max_{\rho_{0}^{l},\dots,\rho_{U}^{l}}$ $\displaystyle\mathrlap{\sum_{r=0}^{U}\frac{\rho_{r}^{l}}{\sqrt{r+1}}}$ $\displaystyle v^{*}=\max_{\rho_{1}^{v},\dots,\rho_{U}^{v}}$ $\displaystyle\mathrlap{\sum_{r=1}^{U}\frac{\rho_{r}^{v}}{\sqrt{r+1}}}$ s.t. $\displaystyle\rho_{0}^{l}\leq 1$ s.t. $\displaystyle\rho_{1}^{v}\leq M_{9}$ $\displaystyle\rho_{0}^{l}+\rho_{1}^{l}\leq 3$ $\displaystyle\rho_{1}^{v}+\rho_{2}^{v}\leq 3M_{9}$ $\displaystyle\dots$ $\displaystyle\dots$ $\displaystyle\rho_{0}^{l}+\rho_{1}^{l}+\dots+\rho_{U}^{l}\leq 2U+1,$ $\displaystyle\rho_{1}^{v}+\rho_{2}^{v}+\dots+\rho_{U}^{v}\leq(2U-1)M_{9}.$ $$

We can easily achieve an optimal point of each linear programming (LP) problem by the well-known Karush-Kuhn-Tucker (KKT) conditions. There exist positive constants $\lambda_{0},\dots,\lambda_{U},\kappa_{1},\dots,\kappa_{U}$ such that

$$ $\displaystyle[1\quad\frac{1}{\sqrt{2}}\quad\dots\quad\frac{1}{\sqrt{U+1}}]=[\sum_{r=0}^{U}\lambda_{r}\quad\sum_{r=1}^{U}\lambda_{r}\quad\dots\quad\lambda_{U}]$ (58) $\displaystyle[\frac{1}{\sqrt{2}}\quad\frac{1}{\sqrt{3}}\quad\dots\quad\frac{1}{\sqrt{U+1}}]=[\sum_{r=1}^{U}\kappa_{r}\quad\sum_{r=2}^{U}\kappa_{r}\quad\dots\quad\kappa_{U}],$ (59) $$

which yields $\lambda_{U}=\kappa_{U}=\frac{1}{\sqrt{U+1}}$,  $\lambda_{r}=\kappa_{r}=\frac{1}{\sqrt{r+1}}-\frac{1}{\sqrt{r+2}}>0$ for $r=1,\dots,U-1$, and $\lambda_{0}=1-\frac{1}{\sqrt{2}}$. Since every dual variable is positive, complementary slackness tells that there is no slack for every inequality at the optimal solution. Thus, the optimal solutions are

$$ $\displaystyle\rho_{0}^{l}=1,\quad\rho_{r}^{l}=2,\quad r=1,\dots,U.$ $\displaystyle\rho_{1}^{v}=M_{9},\quad\rho_{r}^{v}=2M_{9},\quad r=2,\dots,U,$ $$

where the corresponding optimal objective values are

$$ $\displaystyle l^{*}=1+\sum_{r=1}^{U}\frac{2}{\sqrt{r+1}}\leq 1+\sqrt{2}+2\int_{1}^{U}\frac{1}{\sqrt{r+1}}dr=O(\sqrt{U+1})$ $\displaystyle v^{*}=\frac{M_{9}}{\sqrt{2}}+\sum_{r=2}^{U}\frac{2M_{9}}{\sqrt{r+1}}\leq\frac{M_{9}}{\sqrt{2}}+\frac{2M_{9}}{\sqrt{3}}+2M_{9}\int_{2}^{U}\frac{1}{\sqrt{r+1}}dr=O(\sqrt{U+1}),$ $$

where we leverage the non-increasing property of $\frac{1}{\sqrt{r+1}}$ for the inequalities. Thus, we have both $\frac{1}{\eta_{0}}\sum_{r=0}^{U}\frac{\rho_{r}^{l}\log N}{\sqrt{r+1}}=\tilde{O}(T^{2/3}N^{1/3}(U+1)^{1/2})$ and $\frac{1}{\eta_{0}}\sum_{r=0}^{U}\frac{\rho_{r}^{v}}{\sqrt{r+1}}=O(T^{2/3}N^{1/3}(U+1)^{1/2})$. Combining ([E](#A5.Ex150)), ([56](#A5.E56)), and ([E](#A5.Ex152)) with Lemma [D.7](#A4.Thmtheorem7) and $U\leq|\mathcal{U}|$, one can write

$$ $\displaystyle\hskip 14.22636pt\mathbb{E}_{K_{B-1:0}}\sum_{t=0}^{T}[c_{t}(x_{t},u_{t})-c_{t}(x_{t}^{*},u_{t}^{*})]$ $\displaystyle=\tilde{O}(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/2})+o(1)\exp(O(|\mathcal{U}|))(|\mathcal{U}|+1)^{1/2}+O(|\mathcal{U}|)+O(\sum_{b=0}^{B-1}H(\tau_{b}))$ $\displaystyle=\tilde{O}(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/2})+o(1)\exp(O(|\mathcal{U}|))(|\mathcal{U}|+1)^{1/2}+O(\sum_{b=0}^{B-1}H(\tau_{b})),$ $$

where the second equality holds when $T\geq\frac{|\mathcal{U}|^{3/2}}{N^{1/2}(|\mathcal{U}|+1)^{3/4}}$. Using ([C](#A3.Ex51)) shows a sublinear regret bound. When $H(t)\leq O(\sum_{i=1}^{t}\frac{1}{i})$ for all $t\geq 1$, ([51](#A4.E51)) and ([D](#A4.Ex140)) are modified to

$$ $\displaystyle\sum_{b=0}^{B-1}H(\tau_{b})\leq O(BH(\tau_{B-1}))=\tilde{O}(T^{2/3}N^{1/3}),$ $\displaystyle\tau_{B-1}H(\tau_{B-1})\leq\tau_{B-1}O(\log(\tau_{B-1}))=\tilde{O}(T^{1/3}N^{-1/3}),$ $\displaystyle\eta_{0}N\exp(O(|\mathcal{U}|)))O(\tau_{B-1}H(\tau_{B-1}))=\tilde{O}(T^{-1/3}N^{1/3})\cdot\exp(O(|\mathcal{U}|)).$ $$

Applying this equality to re-derive equation [E](#A5.Ex150) completes the proof.
∎

###### Theorem E.1 (Restatement of Theorem 4.10 , Regret bound with unknown | 𝒰 | 𝒰 |\mathcal{U}| ) .

###### Proof.

## Appendix F Applications: Switched systems

So far, we have used the best stabilizing controller $i^{*}\in\mathcal{S}$ for all time steps $t=0,\dots,T$ as the baseline of regret. However, the proofs of the theorems stated above imply one can even use any set of controllers
$\{i^{0},i^{1},\ldots\}\subseteq\mathcal{S}$
as a baseline, where the controller is switched from $i^{l}$ to $i^{l+1}$ whenever the cumulative weight $W(\cdot)$ resets. This motivates the application of our DBAR algorithm to scenarios such as the switched systems (Tousi et al. (); Zhao et al. ()) for which the transition dynamics and the associated controller pool may undergo changes, as well as the ballooning problem (Ghalme et al. ()) where the controller pool may expand up to some finite set. We propose Algorithm [3](#alg3), the switching version of DBAR, which resets the weight whenever the system is faced with a finite number of $O(U)$ switches. Here, we consider the regret with switching costs where the unit cost $d\geq 1$ is additionally incurred when the controller is switched; i.e., $d\sum_{t=1}^{T}\mathcal{I}_{(i_{t}\neq i_{t-1})}$ done in Altschuler & Talwar () and Arora et al. ().

For an event $A$, $\mathcal{I}_{(A)}$ denotes an indicator function, where $\mathcal{I}_{(A)}=1$ if an event $A$ occurs and $\mathcal{I}_{(A)}=0$ otherwise. $Pr(A)$ denotes the probability of an event $A$.
Let $x_{t}^{\prime}$ and $u_{t}^{\prime}$ denote the state and action sequence generated by our set of best stabilizing controllers $\{i_{0}^{\prime},\ldots,i_{|\mathcal{L}|}^{\prime}\}\subseteq\mathcal{S}$.
We consider a regret with switching cost where the unit switching cost is $d\geq 1$; i.e., $\mathbb{E}_{K_{B-1:0}}\bigr{[}\sum_{t=0}^{T}[c_{t}(x_{t},u_{t})-c_{t}(x_{t}^{\prime},u_{t}^{\prime})]+d\sum_{b=1}^{B-1}\mathcal{I}_{(K_{b}\neq K_{b-1})}-d\sum_{l=1}^{|\mathcal{L}|}\mathcal{I}_{(i_{l}^{\prime}\neq i_{l-1}^{\prime})}\bigr{]}$.

Algorithm [3](#alg3) can easily be generalized to the situation where we have $O(U)$ number of system switches or controller pool switches.
In fact, we can simply add $i_{|\mathcal{L}|+1}^{\prime},\ldots,i_{|\mathcal{L}|+O(U)}^{\prime}\in\mathcal{S}$ to the set of best stabilizing controllers $\{i_{0}^{\prime},\ldots,i_{|\mathcal{L}|}^{\prime}\}\subseteq\mathcal{S}$, where $|\mathcal{L}|=O(U)$ by Lemma [D.3](#A4.Thmtheorem3). Thus, it suffices to derive the regret bound of Algorithm [3](#alg3), even in the context of general switched systems or ballooning problem.
We first provide a useful lemma to construct a regret bound.

Figure: Algorithm 3 DBAR-switching

###### Lemma F.1 .

In Algorithm [3](#alg3), let $\tau_{0}=\lfloor(\frac{z}{N(|\mathcal{U}|+1)})^{1/2}\rfloor$ and $\tau_{b}=\lceil(\frac{(\nu b+z)}{N(|\mathcal{U}|+1)})^{1/2}\rceil$ for every $b\geq 1$ with the constants $z,\nu>0$ that satisfies $\tau_{0}>0$ and $\frac{\tau_{1}}{\tau_{0}}(\beta(\tau_{0}))^{2}<\frac{1}{2\sqrt{2}}$. When $T\geq\frac{(o(1)exp(O(|\mathcal{U}|)))^{3/2}}{(N(|\mathcal{U}|+1))^{1/2}}$, we have

$$ $\mathbb{E}_{K_{B-1:0}}\sum_{b=1}^{B-1}\mathcal{I}_{(K_{b}\neq K_{b-1})}=O(|\mathcal{U}|)+O(\eta_{0}NT).$ $$

###### Proof.

For all $b=1,\dots,B-1$ such that $s_{b}=s_{b-1}$, given $K_{b-1},\dots,K_{0}$, we have

$$ $\displaystyle Pr(K_{b}\neq K_{b-1})$ $\displaystyle\leq 1-\frac{\exp(-\eta_{b}W_{b}(K_{b-1}))}{\exp(-\eta_{b-1}W_{b-1}(K_{b-1}))}\leq 1-\frac{\exp(-\eta_{b-1}W_{b}(K_{b-1}))}{\exp(-\eta_{b-1}W_{b-1}(K_{b-1}))}$ $\displaystyle=1-\exp(-\eta_{b-1}w_{b-1}^{\prime}(K_{b-1}))\leq 1-\exp(-\eta_{0}w_{b-1}^{\prime}(K_{b-1}))$ $\displaystyle\leq\eta_{0}w_{b-1}^{\prime}(K_{b-1})=\eta_{0}\frac{w_{b-1}(K_{b-1})}{p_{b-1}(K_{b-1})},$ (60) $$

where the second inequality is because $\eta_{b}=\eta_{b-1}$ when $s_{b}=s_{b-1}$, the third inequality uses $\eta_{0}\geq\eta_{b}$ for all $b\geq 0$, and the last inequality uses $1+x\leq e^{x}$ for all $x\in\mathbb{R}$. Now, given a set of controllers $i^{b}\in\mathcal{P}_{b}$ for $b=0,\dots,B-1$, we can upper-bound $\sum_{b=0}^{B-2}w_{b}(i^{b})$ by $t_{b+1}-t_{b}\leq\tau_{b}$ as follows:

$$ $\displaystyle\sum_{b=0}^{B-2}w_{b}(i^{b})$ $\displaystyle=\sum_{b=0}^{B-2}\sum_{t=t_{b}}^{t_{b+1}-1}c_{t}(x_{t},u_{t})\leq\sum_{b=0}^{B-2}\sum_{t=t_{b}}^{t_{b+1}-1}2L_{c_{1}}(\|x_{t}\|^{2}+\|u_{t}\|^{2})+L_{c2}(\|x_{t}\|+\|u_{t}\|)+c_{0,\text{max}}$ $\displaystyle\leq\sum_{b=0}^{B-2}\sum_{t=t_{b}}^{t_{b+1}-1}2L_{c_{1}}((1+2L_{\pi}^{2})\|x_{t}\|^{2}+2\pi_{0,\text{max}}^{2})+L_{c2}((1+L_{\pi})\|x_{t}\|+\pi_{0,\text{max}})+c_{0,\text{max}}$ $\displaystyle\leq\sum_{b=0}^{B-2}2L_{c_{1}}(1+2L_{\pi}^{2})H(\tau_{b})\|x_{t_{b}}\|^{2}+L_{c2}(1+L_{\pi})H(\tau_{b})\|x_{t_{b}}\|+\tau_{b}[4L_{c_{1}}\pi_{0,\text{max}}^{2}+L_{c2}\pi_{0,\text{max}}+c_{0,\text{max}}]$ $\displaystyle=O(\exp(O(|\mathcal{U}|))H(\tau_{b_{U}}))+O(\sum_{b=0}^{B-2}H(\tau_{b}))+O(\sum_{b=0}^{B-2}\tau_{b}),$ (61) $$

where the first inequality is due to ([D](#A4.Ex97)), the second inequality is by ([12](#A3.E12)) and ([36](#A4.E36)), the third inequality is due to using $\beta(\cdot)\leq 1$ to derive $\sum_{t=0}^{t_{b+1}-t_{b}}[\beta(t)]^{2}\leq\sum_{t=0}^{t_{b+1}-t_{b}}[\beta(t)]=H(t_{b+1}-t_{b})$, and the last equality can be derived in the same fashion with ([39](#A4.E39)). With $T\geq\frac{(o(1)exp(O(|\mathcal{U}|)))^{3/2}}{(N(M+1))^{1/2}}$, we obtain by ([47](#A4.E47)) that

$$ $\displaystyle O(\exp(O(|\mathcal{U}|))H(\tau_{b_{U}}))+O(\sum_{b=0}^{B-2}H(\tau_{b}))+O(\sum_{b=0}^{B-2}\tau_{b})\leq O(T).$ (62) $$

Thus, one can write

$$ $\displaystyle\mathbb{E}_{K_{B-1:0}}\sum_{b=1}^{B-1}\mathcal{I}_{(K_{b}\neq K_{b-1})}=\sum_{b=1}^{B-1}\mathbb{E}_{K_{b:0}}\mathcal{I}_{(K_{b}\neq K_{b-1})}=\sum_{b=1}^{B-1}\mathbb{E}_{K_{b-1:0}}\mathbb{E}_{K_{b}}[\mathcal{I}_{(K_{b}\neq K_{b-1})}~{}|~{}K_{b-1:0}]$ $\displaystyle=\sum_{b=1}^{B-1}\mathbb{E}_{K_{b-1:0}}Pr(K_{b}\neq K_{b-1}~{}|~{}K_{b-1:0})$ $\displaystyle=\sum_{b=1}^{B-1}\mathbb{E}_{K_{b-1:0}}[Pr(s_{b}=s_{b-1},\mathcal{P}_{b}=\mathcal{P}_{b-1}~{}|~{}K_{b-1:0})Pr(K_{b}\neq K_{b-1}~{}|~{}s_{b}=s_{b-1},\mathcal{P}_{b}=\mathcal{P}_{b-1},K_{b-1:0})$ $\displaystyle\hskip 56.9055pt+Pr(s_{b}\neq s_{b-1}~{}\text{or}~{}\mathcal{P}_{b}\neq\mathcal{P}_{b-1}~{}|~{}K_{b-1:0})Pr(K_{b}\neq K_{b-1}~{}|~{}s_{b}\neq s_{b-1}~{}\text{or}~{}\mathcal{P}_{b}\neq\mathcal{P}_{b-1},K_{b-1:0})]$ $\displaystyle=|\mathcal{L}|+U+\sum_{b=1}^{B-1}\mathbb{E}_{K_{b-1:0}}[Pr(s_{b}=s_{b-1},\mathcal{P}_{b}=\mathcal{P}_{b-1}~{}|~{}K_{b-1:0})Pr(K_{b}\neq K_{b-1}~{}|~{}s_{b}=s_{b-1},\mathcal{P}_{b}=\mathcal{P}_{b-1},K_{b-1:0})$ $\displaystyle\leq|\mathcal{L}|+U+\sum_{b=1}^{B-1}\mathbb{E}_{K_{b-1:0}}Pr(K_{b}\neq K_{b-1}~{}|~{}s_{b}=s_{b-1},\mathcal{P}_{b}=\mathcal{P}_{b-1},K_{b-1:0})$ $\displaystyle\leq|\mathcal{L}|+U+\sum_{b=1}^{B-1}\mathbb{E}_{K_{b-1:0}}\eta_{0}\frac{w_{b-1}(K_{b-1})}{p_{b-1}(K_{b-1})}$ $\displaystyle=|\mathcal{L}|+U+\sum_{b=1}^{B-1}\mathbb{E}_{K_{b-2:0}}\mathbb{E}_{K_{b-1}}\biggr{[}\eta_{0}\frac{w_{b-1}(K_{b-1})}{p_{b-1}(K_{b-1})}~{}|~{}K_{b-2:0}\biggr{]}$ $\displaystyle=|\mathcal{L}|+U+\sum_{b=1}^{B-1}\eta_{0}\mathbb{E}_{K_{b-2:0}}\sum_{K_{b-1}\in\mathcal{P}_{b-1}}p_{b-1}(K_{b-1})\frac{w_{b-1}(K_{b-1})}{p_{b-1}(K_{b-1})}$ $\displaystyle\leq|\mathcal{L}|+U+\sum_{b=1}^{B-1}\eta_{0}N\mathbb{E}_{K_{b-2:0}}w_{b-1}(i^{b-1})$ (63) $$

for the controller $i^{b-1}=\arg\max_{i\in\mathcal{P}_{b-1}}w_{b-1}(i)$. The first equality is because $K_{B-1},\dots,K_{b+1}$ does not affect on $\mathcal{I}_{(K_{b}\neq K_{b-1})}$ and the second inequality is by ([F](#A6.Ex165)). Taking expectation of ([F](#A6.Ex167)) with respect to $K_{b-1:0}$ and applying it to ([F](#A6.Ex170)) yields

$$ $\displaystyle\mathbb{E}_{K_{B-1:0}}\sum_{b=1}^{B-1}\mathcal{I}_{(K_{b}\neq K_{b-1})}=|\mathcal{L}|+U+O(\eta_{0}NT)$ $$

by ([62](#A6.E62)). Using $|\mathcal{L}|=O(U)$ in Lemma [D.3](#A4.Thmtheorem3) and $U\leq|\mathcal{U}|$ completes the proof.
∎

Algorithm [3](#alg3) uses the same distribution with Algorithm [1](#alg1) if $b=0$ or $s_{b}\neq s_{b-1}$ or $\mathcal{P}_{b}\neq\mathcal{P}_{b-1}$. It turns out that even if $s_{b}=s_{b-1}$ and $\mathcal{P}_{b}=\mathcal{P}_{b-1}$, the distribution of policy from Algorithm [1](#alg1) and [3](#alg3) are indeed the same, which is motivated by Anava et al. (). For the sake of completeness, we state the lemma in this paper.

###### Lemma F.2 .

Let $p_{b}$ and $\tilde{p}_{b}$ denote the distribution of policy at batch $b=0,\dots,B-1$ resulting from Algorithm [1](#alg1) and [3](#alg3), respectively. Then, $p$ and $\tilde{p}$ are the same distribution.

###### Proof.

For $b=0$, $p_{0}(k)=\tilde{p}_{0}(k)=\frac{1}{N}$ for all $k\in\mathcal{P}_{0}$. For all $b=1,\dots,B-1$ such that $s_{b}\neq s_{b-1}$ or $\mathcal{P}_{b}\neq\mathcal{P}_{b-1}$, it holds that $p_{b}=\tilde{p}_{b}$. Thus, it suffices to prove the induction step for $b=1,\dots,B-1$ such that $s_{b}=s_{b-1}$ and $\mathcal{P}_{b}=\mathcal{P}_{b-1}$. Define $Y_{b}:=\sum_{k\in\mathcal{P}_{b}}\exp(-\eta_{b}W_{b}(k))$ and suppose that $p_{b-1}=\tilde{p}_{b-1}$. Thus, we have

$$ $\displaystyle\tilde{p}_{b}(k)$ $\displaystyle=\tilde{p}_{b-1}(k)\cdot\frac{\exp(-\eta_{b}W_{b}(k))}{\exp(-\eta_{b-1}W_{b-1}(k))}+p_{b}(k)\cdot\sum_{i\in\mathcal{P}_{b}}(1-\frac{\exp(-\eta_{b}W_{b}(i))}{\exp(-\eta_{b-1}W_{b-1}(i))})\cdot\tilde{p}_{b-1}(i)$ $\displaystyle=p_{b-1}(k)\cdot\frac{\exp(-\eta_{b}W_{b}(k))}{\exp(-\eta_{b-1}W_{b-1}(k))}+p_{b}(k)\cdot\sum_{i\in\mathcal{P}_{b}}(1-\frac{\exp(-\eta_{b}W_{b}(i))}{\exp(-\eta_{b-1}W_{b-1}(i))})\cdot p_{b-1}(i)$ $\displaystyle=\frac{\exp(-\eta_{b-1}W_{b-1}(k))}{Y_{b-1}}\cdot\frac{\exp(-\eta_{b}W_{b}(k))}{\exp(-\eta_{b-1}W_{b-1}(k))}$ $\displaystyle\hskip 85.35826pt+\frac{\exp(-\eta_{b}W_{b}(k))}{Y_{b}}\sum_{i\in\mathcal{P}_{b}}(1-\frac{\exp(-\eta_{b}W_{b}(i))}{\exp(-\eta_{b-1}W_{b-1}(i))})\frac{\exp(-\eta_{b-1}W_{b-1}(k))}{Y_{b-1}}$ $\displaystyle=\frac{\exp(-\eta_{b}W_{b}(k))}{Y_{b-1}}+\frac{\exp(-\eta_{b}W_{b}(k))}{Y_{b}}\sum_{i\in\mathcal{P}_{b}}\frac{\exp(-\eta_{b-1}W_{b-1}(i))-\exp(-\eta_{b}W_{b}(i))}{Y_{b-1}}$ $\displaystyle=\frac{\exp(-\eta_{b}W_{b}(k))}{Y_{b-1}}+\frac{\exp(-\eta_{b}W_{b}(k))}{Y_{b}}\cdot\frac{Y_{b-1}-Y_{b}}{Y_{b-1}}=\frac{\exp(-\eta_{b}W_{b}(k))\cdot Y_{b-1}}{Y_{b}\cdot Y_{b-1}}=p_{b}(k),$ $$

where the first equality is due to the law of total probability, the second equality is due to the induction hypothesis, and the fifth equality is by $\mathcal{P}_{b}=\mathcal{P}_{b-1}$. Notice that $s_{b}=s_{b-1}$ yields $\eta_{b}=\eta_{b-1}$ and $W_{b}(k)\geq W_{b-1}(k)$, and thus $0\leq\frac{\exp(-\eta_{b}W_{b}(k))}{\exp(-\eta_{b-1}W_{b-1}(k))}\leq 1$; i.e., the probability distribution is properly defined for every batch. This completes the proof.
∎

###### Theorem F.3 (Regret with switching costs bound with known $|\mathcal{U}|$ ) .

In Algorithm [3](#alg3), let $\tau_{0}=\lfloor(\frac{z}{N(|\mathcal{U}|+1)})^{1/2}\rfloor$ and $\tau_{b}=\lceil(\frac{(\nu b+z)}{N(|\mathcal{U}|+1)})^{1/2}\rceil$ for every $b\geq 1$ with the constants $z,\nu>0$ that satisfies $\tau_{0}>0$ and $\frac{\tau_{1}}{\tau_{0}}(\beta(\tau_{0}))^{2}<\frac{1}{2\sqrt{2}}$. Also, let $\eta_{0}=O(\frac{(|\mathcal{U}|+1)^{2/3}}{T^{2/3}N^{1/3}d^{1/3}})$. When $T\geq\max\{\frac{(o(1)exp(O(|\mathcal{U}|)))^{3/2}}{(N(|\mathcal{U}|+1))^{1/2}},\frac{|\mathcal{U}|^{3/2}d}{(N(|\mathcal{U}|+1))^{1/2}},N(|\mathcal{U}|+1)d\}$, we have

$$ $\displaystyle\mathbb{E}_{K_{B-1:0}}\Biggr{[}\sum_{t=0}^{T}[c_{t}(x_{t},u_{t})-c_{t}(x_{t}^{\prime},u_{t}^{\prime})]+d\sum_{b=1}^{B-1}\mathcal{I}_{(K_{b}\neq K_{b-1})}-d\sum_{l=1}^{|\mathcal{L}|}\mathcal{I}_{(i_{l}^{\prime}\neq i_{l-1}^{\prime})}\Biggr{]}$ $\displaystyle\hskip 199.16928pt=\tilde{O}(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3}d^{1/3})+o(T),$ $$

which implies that we achieve a sublinear regret bound. Moreover, when $\lim_{t\to\infty}H(t)<\infty$ and $T\geq\max\{\frac{\exp(O(|\mathcal{U}|))}{d^{2/3}},\frac{|\mathcal{U}|^{3/2}d}{(N(|\mathcal{U}|+1))^{1/2}},N(|\mathcal{U}|+1)d\}$, we have

$$ $\mathbb{E}_{K_{B-1:0}}\Biggr{[}\sum_{t=0}^{T}[c_{t}(x_{t},u_{t})-c_{t}(x_{t}^{\prime},u_{t}^{\prime})]+d\sum_{b=1}^{B-1}\mathcal{I}_{(K_{b}\neq K_{b-1})}-d\sum_{l=1}^{|\mathcal{L}|}\mathcal{I}_{(i_{l}^{\prime}\neq i_{l-1}^{\prime})}\Biggr{]}=\tilde{O}(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3}d^{1/3}).$ $$

###### Proof.

The distribution of policy is the same for Algorithm [1](#alg1) and [3](#alg3) by Lemma [F.2](#A6.Thmtheorem2). Thus, we can use Theorem [D.8](#A4.Thmtheorem8) with Lemma [F.1](#A6.Thmtheorem1) to achieve

$$ $\displaystyle\mathbb{E}_{K_{B-1:0}}\Biggr{[}\sum_{t=0}^{T}[c_{t}(x_{t},u_{t})-c_{t}(x_{t}^{\prime},u_{t}^{\prime})]+d\sum_{b=1}^{B-1}\mathcal{I}_{(K_{b}\neq K_{b-1})}-d\sum_{l=1}^{|\mathcal{L}|}\mathcal{I}_{(i_{l}^{\prime}\neq i_{l-1}^{\prime})}\Biggr{]}$ $\displaystyle\leq\frac{\tilde{O}(|\mathcal{U}|+1)}{\eta_{0}}+\frac{\eta_{0}N}{2}[\exp(O(|\mathcal{U}|))O(\tau_{B-1}H(\tau_{B-1}))+O(\sum_{b=0}^{B-1}(\tau_{b})^{2})]$ $\displaystyle\hskip 184.9429pt+O(\sum_{b=0}^{B-1}H(\tau_{b}))+O(d|\mathcal{U}|)+O(d\eta_{0}NT),$ (64) $$

since $d\geq 1$ and $\sum_{l=1}^{L}\mathcal{I}_{(i_{l}^{\prime}\neq i_{l-1}^{\prime})}\geq 0$. Notice that $(\tau_{b})_{b\geq 0}$ is the same for Algorithm [1](#alg1) and [3](#alg3). Accordingly, we still have $B=O(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3})$ by ([D](#A4.Ex137)) and $T\geq N(|\mathcal{U}|+1)d\geq N(|\mathcal{U}|+1)$. We also still have ([D](#A4.Ex138)) and ([47](#A4.E47)). Thus, with $T\geq\frac{(o(1)exp(O(|\mathcal{U}|)))^{3/2}}{(N(|\mathcal{U}|+1))^{1/2}}$ and $T\geq\frac{|\mathcal{U}|^{3/2}d}{(N(|\mathcal{U}|+1))^{1/2}}$, we obtain that

$$ $\displaystyle\eta_{0}N\exp(O(|\mathcal{U}|))O(\tau_{B-1}H(\tau_{B-1}))=o(d^{-1/3})\exp(O(|\mathcal{U}|))=O(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3}d^{-1/3}).$ $\displaystyle O(d|\mathcal{U}|)=O(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3}d^{1/3}).$ $$

Also, with $T\geq N(|\mathcal{U}|+1)d$, we have

$$ $\displaystyle O(d\eta_{0}NT)=O(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3}d^{1/3}).$ $$

Combining all the above equalities with ([F](#A6.Ex189)), one can write

$$ $\displaystyle\mathbb{E}_{K_{B-1:0}}\Biggr{[}\sum_{t=0}^{T}[c_{t}(x_{t},u_{t})-c_{t}(x_{t}^{\prime},u_{t}^{\prime})]+d\sum_{b=1}^{B-1}\mathcal{I}_{(K_{b}\neq K_{b-1})}-d\sum_{l=1}^{|\mathcal{L}|}\mathcal{I}_{(i_{l}^{\prime}\neq i_{l-1}^{\prime})}\Biggr{]}$ $\displaystyle\hskip 170.71652pt=O(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3}d^{1/3})+O(\sum_{b=0}^{B-1}H(\tau_{b})).$ $$

Using ([C](#A3.Ex51)) shows a sublinear regret bound. When $\lim_{t\to\infty}H(t)<\infty$, ([D](#A4.Ex140)) is modified to

$$ $\displaystyle\eta_{0}N\exp(O(|\mathcal{U}|))O(\tau_{B-1}H(\tau_{B-1}))=O(T^{2/3}N^{1/3}(|\mathcal{U}|+1)^{1/3}d^{1/3}),$ $$

only with $T\geq\frac{\exp(O(|\mathcal{U}|))}{d^{2/3}}$. This completes the proof.
∎

###### Lemma F.1 .

###### Proof.

###### Lemma F.2 .

###### Proof.

###### Theorem F.3 (Regret with switching costs bound with known | 𝒰 | 𝒰 |\mathcal{U}| ) .

###### Proof.

## Appendix G Numerical Experiment Details

In the two following subsections, we will present experiment details on linear and nonlinear systems, respectively. Since our Algorithm [1](#alg1) only hinges on the system state norm as a context, we can avoid computational burden; thus, Apple M1 Chip with 8-Core CPU is sufficient for the experiments.
The error bars (shaded area) in all the figures in the paper report 95% confidence intervals based on the standard error. We calculate the standard error by randomly sampling 100 seeds to consider the variability of our experimental results.
The first factor of variability is the randomness of selecting the policy determined by the probability calculated in Algorithm [1](#alg1). The second factor is the randomness of adversarial disturbances stated in each experiment. For example, sinusoidal noise does not involve any randomness but the uniform random walk contains the randomness in the difference between two consecutive noises.

### G.1 Experiments for the Linear system

In this subsection, we introduce the implementation details and present more experiments on the linear system ([7](#S5.E7)) discussed in Example 1 of Section [5](#S5).

We consider three different noises for the experiments. To perform a fair comparison, the bounding constant $w_{\text{max}}$ is set to 1.

$$ $\displaystyle\text{(a) Sanity check: Gaussian noise with mean 0.3 and standard deviation 0.1, truncated to}[-0.4,1]$ $\displaystyle\text{(b) Sinusoidal noise }w_{t}=\Bigr{[}\sin\Bigr{(}\frac{t}{5\pi}\Bigr{)},\sin\Bigr{(}\frac{t}{11\pi}\Bigr{)}\Bigr{]}^{\prime}$ $\displaystyle\text{(c) Uniform random walk, where }w_{0}=\text{Uniform}\biggr{[}\frac{1}{3}-\frac{2}{3T},\frac{1}{3}+\frac{2}{3T}\biggr{]}^{2}$ $\displaystyle\hskip 115.23366pt\text{ and }w_{t}-w_{t-1}\text{ follows Uniform}\biggr{[}-\frac{2}{3T},\frac{2}{3T}\biggr{]}^{2},$ $$

where $T$ is time horizon. One can easily see that for uniform random walk, $|w_{T}|\leq 1$ for any $T$. Notice that we use statistical (Gaussian) noise for the sanity check, and the rest are the adversarial disturbances.

We perform the ablation study of Algorithm [1](#alg1), which means that we consider four scenarios: (fixed, dynamic) batch length and (fixed, adaptive) learning rate.
For all the experiments implementing the algorithm, we use $T=3000,\eta_{0}=0.025,\gamma=2.5,\alpha_{0}=1.01,$ and $x_{0}=[100,200]^{\prime}$.
For the dynamic batch length, we consider $\tau_{0}=11$ and $\tau_{b}=\lceil\tau_{0}\cdot(\frac{b+10}{10})^{0.5}\rceil$. It is well known that every (asymptotically) stabilizing controller in the linear system is indeed exponentially stabilizing controller (Khalil ()). Hence, we use $\beta(t)=0.99^{t}$ without relaxing the assumptions on stabilizing controllers. Finally, we use $\delta=\frac{\gamma w_{\text{max}}}{1-\beta(\tau_{0})}$. Since the sinusoidal noise case is already presented in Figure [1](#S5.F1), we only present truncated Gaussian noise case and uniform random walk case here.

In Figures [1](#S5.F1), [4](#A7.F4), and [5](#A7.F5), we observe that each component of DBAR, a dynamic batch length and an adaptive learning rate, jointly improves both the stability and the regret regardless of the noise form. For example, a dynamic batch length delays the time that large state norms occur during learning, but does not necessarily stabilize that state norm by itself (see Figures [5(a)](#A7.F5.sf1) and [5(b)](#A7.F5.sf2)). However, when applied together with an adaptive learning rate, a potential multiplicative exponential term is mitigated (see Remark [4.8](#S4.Thmtheorem8)) and the state norm is thus stabilized. This can be observed in Figures [1(d)](#S5.F1.sf4), [4(d)](#A7.F4.sf4), and [5(d)](#A7.F5.sf4) when comparing fixed and dynamic batch lengths under an adaptive learning rate. This results from using a non-decreasing batch length where the increasing ratio between two consecutive batch lengths is determined to converge to 1 (see Assumption [3.1](#S3.Thmtheorem1)). On the other hand, an adaptive learning rate effectively lowers the state norm at the time that large state norms occur without delay, since the learning rate adaptively decreases whenever the agent faces large state norm. This can be seen in [1(c)](#S5.F1.sf3), [4(c)](#A7.F4.sf3), and [5(c)](#A7.F5.sf3), the ablation study about the comparison between fixed and adaptive learning rates under a dynamic batch length. Thus, DBAR effectively stabilizes the state norm below $\gamma w_{\text{max}}$ and minimizes the regret, where the two components support each other.

Figure: (a) Stability analysis
Refer to caption: /html/2410.03230/assets/figures/stabsanity.png

Figure: (a) Stability analysis
Refer to caption: /html/2410.03230/assets/figures/stabwalk.png

### G.2 Experiments for the Nonlinear system

In this subsection, we introduce the implementation details and present more experiments on the nonlinear ball-beam system introduced in Example 2 of Section [5](#S5). To study this continuous-time nonlinear system, we first derive the first-order state representation of ([8](#S5.E8)) with the states $(y_{1},y_{2},y_{3},y_{4})=(x,\dot{x},-9.81B\theta,-9.81B\dot{\theta})\in\mathbb{R}^{4}$ and the action $v=-9.81Bu$:

$$ $\displaystyle\dot{y_{1}}=y_{2},\quad\dot{y_{2}}=9.81B\sin\Bigr{(}\frac{y_{3}}{9.81B}\Bigr{)}+\frac{y_{1}y_{4}^{2}}{B(9.81)^{2}}+3w,\quad\dot{y_{3}}=y_{4},\quad\dot{y_{4}}=v,$ $$

where $w$ is a sinusoidal noise $\sin\bigr{(}\frac{t}{7\pi}\bigr{)}$ and $w_{\text{max}}=1$.
A nested saturating control policy is known to successfully stabilize the ball-beam system if the correct parameters are given, but it does not necessarily exponentially stabilize the system (Barbu et al. ()). This necessitates our approach of extending the notion of stabilizing controllers beyond exponential assumptions.
In this experiment, we aim to learn the parameters of the best stabilizing controller.
We choose a nested saturating control policy $v^{\prime}$ determined by three positive parameters $(p,k_{1},k_{2})$:

$$ $\displaystyle\epsilon=\frac{1}{\sqrt{1+y_{1}^{2}+y_{2}^{2}}},\quad p_{1}=p,\quad p_{2}=\frac{p}{\epsilon},\quad p_{3}=\frac{p}{\epsilon^{2}},\quad p_{4}=\frac{p}{\epsilon^{3}},$ $\displaystyle z_{1}=y_{1}+k_{1}y_{2}+k_{1}y_{3}+y_{4},\quad z_{2}=y_{2}+k_{2}y_{3}+y_{4},\quad z_{3}=y_{3}+y_{4},\quad z_{4}=y_{4},$ $\displaystyle v^{\prime}=\sigma_{p_{4}}(z_{4}+\sigma_{p_{3}}(z_{3}+\sigma_{p_{2}}(z_{2}+\sigma_{p_{1}}(z_{1})))),$ $$

where $\sigma_{p}(z)$ is the saturating function defined as $p$ if $z>p$, $-p$ if $z<-p$, and $z$ if $|z|\leq p$. We consider the controller pool

$$ $\displaystyle V^{\prime}=\{v^{\prime}:p\in\{2,16,30,44,58,72,86,100\},~{}$ $\displaystyle k_{1}\in\{2,2.5,3,3.5,4,4.5,5,5.5,6,6.5\},$ $\displaystyle k_{2}\in\{1,1.5,2,2.5,3,3.5,4,4.5,5,5.5\}\},$ $$

which has a total of 800 controllers. Among them, we do not know if a controller stabilizes the system. For simplicity, we perform forward-Euler discretization on the system with a sampling time $0.01$. The resulting discrete-time states and actions are denoted by $y^{t}$ and $v^{t}$ at $t^{\text{th}}$ sampling time. We use the cost function $c_{t}(y^{t},v^{t})=\|y^{t}\|^{2}+\|v^{t}\|^{2}$ to stabilize the ball position and the beam angle towards 0.

We again perform the ablation study of Algorithm [1](#alg1).
For the experiments implementing the algorithm, we use $T=5000$, $\eta_{0}=0.025,\gamma=1.5,\alpha_{0}=1.01$, and $y^{0}=[-32,24,5.6,24]$. For the dynamic batch length, we consider $\tau_{0}=9$ and $\tau_{b}=\lceil\tau_{0}\cdot(\frac{b+41}{40})^{0.5}\rceil$.

Unlike the choice of $\beta(t)$ in Section [G.1](#A7.SS1), we select the stabilizing controller only to satisfy (asymptotic) ISS in Definition [2.3](#S2.Thmtheorem3), instead of exponential ISS.
To deeply study this notion, we consider different polynomially decreasing series (which is not exponentially decreasing) to be the candidates for $\beta(t)$:

$$ $\displaystyle\beta_{1}(t)=\min\biggr{\{}\frac{10}{t},1\biggr{\}},\quad\beta_{2}(t)=\min\biggr{\{}\frac{10}{t^{1.02}},1\biggr{\}}.$ $$

Figure: (a) Stability analysis: $\beta_{1}(t)$
Refer to caption: /html/2410.03230/assets/figures/nonstab100.png

Figure: (a) Stability analysis: $\beta_{3}(t)$
Refer to caption: /html/2410.03230/assets/figures/nonstab105.png

Figures [2(b)](#S5.F2.sf2) and [2(c)](#S5.F2.sf3) show the stability and regret analysis of the system under $\beta_{1}(t)$. For the completeness, we present the same pictures in Figures [6(a)](#A7.F6.sf1) and [6(b)](#A7.F6.sf2).
Notice that our notion of stabilizing controllers also include the case where $H(t)$ is not summable at infinity (see the footnote in Theorem [4.6](#S4.Thmtheorem6)), which is demonstrated by the choice of $\beta_{1}(t)$ as a stabilizing criterion.

In our experiment, there are 225 controllers out of 800 controllers that induces the system to explode, starting from the initial state. However, there exist far more destabilizing controllers within this pool, since most of 575 controllers are only locally stabilizing controllers, meaning that the system is stabilized only at some initial states. With only few stabilizing controllers in the pool,
Figure [6](#A7.F6) illustrates that a dynamic batch length by itself still suffers from a multiplicative exponential term regarding a series of destabilizing controllers. However, for both $\beta_{1}(t)$ and $\beta_{2}(t)$, even though $H(t)$ and $O(\sum_{i=1}^{t}\frac{1}{i})$ are close enough, one can observe that the combination of the two components of DBAR effectively resolves this malignant term and the resulting closed-loop system enjoys both asymptotic system stability and the improved regret (see Table [1](#S1.T1)).

We also consider two different $\beta(\cdot)$’s at different rates and present the results in Figure [7](#A7.F7):

$$ $\displaystyle\beta_{3}(t)=\min\biggr{\{}\frac{10}{t^{1.05}},1\biggr{\}},\quad\beta_{4}(t)=\min\biggr{\{}\frac{10}{t^{1.08}},1\biggr{\}}.$ $$

The behaviors of $\beta_{3}(t)$ and $\beta_{4}(t)$ are slightly different from those of $\beta_{1}(t)$ and $\beta_{2}(t)$, in the sense that while DBAR still performs well, the system already appears stabilized even without some components of DBAR. This stems from the amount of discarding the destabilizing controllers. $\beta_{4}(t)$ removes the controller with the most strict criteria, followed by $\beta_{3}(t)$, $\beta_{2}(t)$, and $\beta_{1}(t)$ since $1.08>1.05>1.02>1$. This prevents the explosion of the nonlinear system by eliminating potential destabilizing controllers not yet seen in an unstable region in advance. However, in practice, if the given candidate controller set had not included any controller satisfying the strict assumptions, the algorithm would have terminated, failing to keep the system running.
This finding again demonstrates why it is crucial to allow a broader class of controllers and still achieve a tight regret bound. Moreover, the experimental results strongly support that our algorithm DBAR performs well for any choice of $\beta(t)$, which determines the scope of stabilizing controllers.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. How does the dynamically increasing batch length affect the algorithm's computational cost, particularly in real-time applications? It would be helpful to discuss any trade-offs between stability assurance and computational efficiency.

2. The current experimental setup involves relatively simple, low-dimensional systems. Can the authors provide results on more challenging benchmarks to better demonstrate DBAR’s performance and stability claims?
soundness: 3
strengths: Originality: 
    The paper introduces a new algorithm, DBAR, combining a dynamic batch length and an adaptive learning rate, which expands on existing Exp3 approaches for bandit learning. This design theoretically broadens the applicability of online control by relaxing the requirement for exponentially stabilizing controllers, a novel aspect in nonlinear control with adversarial disturbances.

Quality: 
    The paper presents a well-structured algorithm and offers some theoretical analysis, including stability and regret bounds, which demonstrate rigor in method development. The authors provide proofs for their main results and discuss conditions under which stability is achieved, showcasing technical precision.

Clarity: 
    The problem setup, assumptions, and main results are generally clear, with key terms defined (e.g., asymptotic stability and finite-gain stability) and a well-organized structure. The authors also make efforts to contextualize the algorithm in comparison to prior work, which aids readability for readers with a background in online control or bandit learning.
summary: The paper addresses the online bandit nonlinear control problem, where the objective is to learn an optimal controller for a nonlinear dynamical system amid unknown stabilizing and destabilizing controllers. The authors introduce the DBAR (Dynamic Batch length and Adaptive learning Rate) algorithm, which adapts batch length and learning rate to improve control stability and minimize regret without requiring exponentially stabilizing controllers. Unlike existing approaches that need stronger stability assumptions, DBAR works with a weaker, asymptotic stability notion. This flexibility allows DBAR to achieve stability and a regret bound even when the pool of stabilizing controllers is limited or includes only asymptotically stabilizing ones.

Theoretical contributions include proving asymptotic and finite-gain stability of DBAR and bounding its regret. The authors also compare DBAR's performance with existing algorithms, illustrating through simulations that DBAR provides improved stability and reduced regret in both linear and nonlinear systems under adversarial disturbances.
weaknesses: Originality: 
    While DBAR's approach to adapting the learning rate and batch size is new, the actual contribution may be seen as incremental. The improvements over existing algorithms are mainly in modifying specific assumptions rather than introducing a breakthrough method, and it is unclear if these modifications substantively advance the field.

Quality: 
    The theoretical guarantees, though valuable, rest on assumptions that may be difficult to satisfy in real-world applications, such as requiring knowledge of an ISS controller in advance. Furthermore, empirical validation is limited to relatively simple experiments, which may not fully demonstrate the algorithm’s effectiveness or scalability in more complex settings.

Significance: 
    The practical impact of DBAR appears limited, as the algorithm’s assumptions—particularly on controller stability—may not align well with typical scenarios in nonlinear control. The significance for broader ML audiences is thus moderate, as DBAR seems primarily useful in niche settings where exact stability knowledge is available.

Significance: 
    The paper's experimental evaluation does not robustly validate the theoretical claims, as it relies on lower-dimensional systems that may not capture the challenges posed by high-dimensional, complex environments. This limits the confidence in DBAR's utility beyond the examples shown, reducing its impact.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 2
questions: See Weaknesses.
soundness: 3
strengths: 1. The removal of exponentially stabilizing policies looks pretty good.
2. The resulting regret is satisfactory.
3. The algorithms are stated and motivated clearly.
4. Results are supplemented with numerical evaluations.
summary: This paper studies the problem of online bandit non-linear control where both transition dynamics and cost functions are non-linear and adversarial, and we only receive bandit feedback on either of them. Removing the assumption on exponentially stabilizing controllers, this paper ensured $\tilde{\mathcal O}(T^{2/3})$ regret with the help of only asymptotically stabilizing controllers.

Technically, this paper uses geometricly increasing batch lengthes to remove the requirement of exponentially stabilizing controllers, and further make the $\mathcal O(T^{1/3} e^{\lvert \mathcal U\rvert})$ dependency to $\mathcal O(T^{-1/3} e^{\lvert \mathcal U\rvert})$ via an adaptive learning rate tuning scheme.
weaknesses: From the main text, it looks like the two main techniques, geometrically-increasing batch lengthes and geometrically-decaying learning rates, are the main technical contributions of this paper. But these two techniques seems both extensively studied in other online learning problems. So --
1. How are they different from those used in other online learning problems? Say, do you specifically adapt them to this control theory problem?
2. Do they bring special difficulties under this specific setup of nonlinear control? Say, do they break some previous analysis ideas in online nonlinear control?
3. Why previous works didn't use them?

[EDIT. After rebuttal, it turns out that batch lengths and learning rates are both not simply geometric, but follow some more meticulous designs.]

Minor:

1. To create a reference inside parentheses, please try using the command `\citep{}` instead of manually typing `(\citet{})`.
2. Section 2 is notation heavy. I suggest the authors to add subsections / paragraphs to group the definitions.
3. The results part (especially Section 4.2) contains a huge amount of formal statements with almost no informal descriptions of them; it is definitely not enjoyable to read. I suggest the authors to replace them with informal versions (and also add a paragraph of intuitive description before/after each of them) and defer the formal ones into the appendix.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: Please refer to the weakness part.
soundness: 3
strengths: 1. The problem of online bandit nonlinear control is well-motivated.

2. This paper weakens the assumptions in previous works and derive a stronger regret bound. The proof looks correct.

3. There are simulations to support the theoretical findings.
summary: In this paper, the authors study the online bandit nonlinear control, which aims to learn the best stabilizing controller from a pool of stabilizing and destabilizing controllers of unknown types for a given nonlinear dynamical system. They develop an algorithm, named Dynamic Batch length and Adaptive learning Rate (DBAR), and study its stability and regret. DBAR achieves better regret bounds than Exp3 under even weaker assumptions.
weaknesses: Main concerns:

1. It seems to me that the results heavily depend on the assumption that $H(t)$ has finite limitation (Thm 4.2) or $H(t)\leq O(\log t)$ (Thm 4.6), this assumption does not seem to be very mild ($H(t)$ has finite limitation is far from the conclusion in Lem 4.3). What will the result be like without such assumptions? Or is there any further justifications of such assumption?

2. In the experiments, the claim 'While the simulations are on low-dimensional systems for illustration purposes, similar observations can be made for high-dimensional systems.' is made. Is this a conjecture, or is there any experimental evidence for this? It seems not hard to do experiments with higher dimensionality.

Some questions and suggestions for writing:

1. The notation $|\mathcal{U}|$ first appears in the table, while it is not defined until Def 2.6.

2. The previous papers depend on 'exponential stability'. What is its definition and how is it stronger compared to 'asymptotic stability'?

3. I did not quite understand the motivation of Lemma 4.3. This is too weak to support the assumption $\lim_{t\rightarrow\infty}H(t)<\infty$.

4. Listing the steps to solve for $z,\nu$ in Theorem 4.6 could help justify the results.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 2
questions: 1. Could you include more experimental results on complex systems?
2. Could you explain the necessity of Assumption 2.5? You may refer to previous literature to support your explanation.
3. Could you clarify the proof ideas and intuition behind Theorems 4.5 and 4.6? The current explanation is quite brief, and it's difficult to grasp the core proof strategy as well as how the earlier algorithm design relates to this proof. I suggest expanding this section and moving some of the lemma proofs, such as Lemma 4.7, to the appendix.
soundness: 3
strengths: 1. The paper provides rigorous theoretical analysis, including stability proofs and regret bounds, which demonstrate the effectiveness of the DBAR algorithm under weaker assumptions. The comparison with existing methods is clear and it strengthens the contribution. 
2. The introduction of the DBAR algorithm relaxes the requirement for exponentially stabilizing controllers, allowing a broader range of controllers to stabilize the system. It also achieves better result for known and unknown $\mathcal{U}$.
summary: This paper addresses the problem of online bandit nonlinear control, proposing a new algorithm called Dynamic Batch length and Adaptive learning Rate (DBAR). The algorithm in this paper is designed to handle a nonlinear dynamical system with a mix of stabilizing and destabilizing controllers, offering stability guarantees and regret bounds.
weaknesses: 1. While the theoretical analysis is thorough, the experiments are somewhat limited. The paper focuses on low-dimensional systems (a 2D linear system and a simple nonlinear system), and it would be beneficial to demonstrate the algorithm's performance in more complex, high-dimensional scenarios to validate the practical applicability of DBAR.
2. The writing of this paper is not very clear, especially in Section 2 and Section 3. I suggest using more references, formulas, and illustrations to explain the rationale behind the assumptions and the intuition behind the algorithm design, rather than relying solely on extensive text descriptions.

Meta-review: Summary:
This paper investigates online nonlinear control using bandit feedback. Its primary contribution lies in introducing dynamic batch length and learning rate techniques to relax the commonly used exponentially stabilizing controller assumption. Instead, it adopts a weaker assumption termed the asymptotic stabilizing assumption, achieving a better regret bound. Experimental results support the authors' claims.

Strengths:

- The use of dynamic batch size and adaptive step size to mitigate stability issues is a compelling approach.
- The motivation for this work is clear and well-articulated.
- The experiments, while conducted on simulations, seem sound and adequately support the proposed methodology.

Weaknesses:

- The paper’s presentation needs significant improvement and currently falls short of publication standards. Both my own reading and other reviewers' comments highlight the excessive reliance on dense notations, making the paper less accessible to readers unfamiliar with the field.
- The significance of the asymptotic stability assumption is insufficiently emphasized, leaving the contribution somewhat unclear in the context of existing literature. The draft lacks clarity in positioning this work within the broader research landscape.

Decision: I recommend rejecting this paper in its current form due to the weaknesses outlined above.

Decision: Reject