Online Bandit Nonlinear Control with Dynamic Batch Length and Adaptive Learning Rate
Authors: Jihun Kim
Javad Lavaei
Venue: Accepted by TMLR ()

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 Dynamic Batch length and Adaptive learning Rate (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.

Published in Transactions on Machine Learning Research (05/2025)
Online Bandit Nonlinear Control with Dynamic Batch Length and Adaptive Learning Rate
Jihun Kim
jhun.kim@berreeeey..dd
Deportment of Industrial Engineering and Operations Research
University of California, Berkeley
Javad Lavaci
laxaci@bberkeee...o edu
Department of Industrial Engineering and Operations Research University of Colifornia, Berkeley
Reviewed on OpenReview: https: // openreview. net/ pet/ffrrmm id= gmii TkLdbL
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 unknown types for a given nonlinear dynamical system. We develop an algorithm, named Dynamic Batch Length and Adaptive Learning Rate (DBAR), and study its stability and regret. Unlike the existing Exp3 algorithm requiring an exponentially stabilizing controller, DBAR only needs 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 bchaves as if there were no destabilizing controllers. Moreover, adaplive 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 immodiate cost feedback for each arm pulled. Given a finite number 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 Tt+1 = f(re, ue, w:) and set of cost functions c,(2,, ue) for O...., T, where the goal is to minimize the sum of costs over time, while both f and с are fully or partially unknown. Basically, MAB is 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 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 feodback of pulling the controller-am (Lin al., 2023 Li ct al., 2023).
In this paper, address the online non-stochastic control problem where both transition dynamic f and cost functions Gt be unbounded, nonlinear, and adversarially chosen. We only have knowledge about x, and the bandit foedback (z(2,, W/) at time t, with adversarial disturbances wy injected at cach time step as in Gradu el al. (2020) and Casssl & Koren (2020). 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 advance, where we are not aware of whether cach controller can stabilize the system but we are allowed to alternate between these controllers within single trajectory according to a specific logic. We refer to this problem as the online bandit nontinear control problem.

---

Published in Transactions on Machine Learning Research (05/2025)
To deal with this online bandit nonlinear control, Li et al. (2023) adopted their Exp3-ISS algorithm, which uses the well-known Exp3 algorithm (Auer et al. 2002) with mini-batch approach (Arora et al. 2012). while successively removing destabilizing controllers when detected in terms of suput-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 algorithı DBAR (Dynamic Batch Length and Adaptive Learning Rate).
Motivation and contribution. Our main contribution is to allow broader class of controllers to qualify stabilizing controller within priori controller pool. For the motivation, consider continuous time gradient flow in the vector space:
=(1) - -VF(()(()
(1)
where F: R" + R is a smooth function. A merely convex F can be extremely flat around its minimum, leading to slowly (asymptotically) converging trajectory unlike exponentially converging behavior achieved for strongly convex F' (Khalil 2015). In fact, assuming that a minimizer x² of F exists, the decay rate F(x(()) - F(x") ) is O(1/(((( (o ()) if is convex] (Siegel & Wojtowytsch 2023), and O(e=*) ') if F is strongly convex. In the machine learning literature, a loss function [[g(z), y) of a gradient- based method often given as a convex function in g (e.g., mean-squared error or cross-cntropy loss), but not necessarily strongly convex since g is oflen over-paraaeeeerieed and there could be a continuum of parameters corresponding to the value of g. Analogous to this concept, one consider F' as f(z,, (Iz)), w.), dynamic governed by given controller и and its converging behavior as (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 erponentially 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 O(T2/3) regret under general convex cost functions (Cassel & Koren 2020 Chen & Hazan 2021 Ghai et al. 2023) ). In this paper, will achieve the same ( 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 certily the stability of the system without requiring exponentially stabilizing controllers and achieve both asymptotic system stability and a sublinear regret bound. The batch length is scheduled be non-decreasing and growing unboundedly over time, but its growth amount eventually saturates. However, the strategy suffers from resulting multiplicative exponential regret in return.
2. To alleviate the multiplicative exponential regret without requiring the conservative notion of exponen- tially 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 use a non-incrcasing learning rate, we decrease the learning rate the state is unstable and subsoquently increase the learning rate if the stale returns to stable region. By implementing this approach, we can alleviate the multiplicative exponential term in all cases. In particular, for a specific class of stabilizing controllers beyond exponential notions, we attain regret bound order (Ō(T2/3) + 11/3) exp(O((4))) (14) + 1)", where a = 1/3 if [4] is known and a = 1/2 if [ is unknown.
Table g shows a summary of our results with related works. Appendix A provides more details on the intermodiate step "Dynamic Batching", which operates under asymptotically stabilizing controller assumptions, and on how we devised DBAR algorithm to avoid the multiplicative exponential term.
Note that O(1/(tlog* t)) is intograble at infinity. In the context of controllers, we also handle the challenging case where far, a(21), wx) inf f(z,, ((x), un) may be integrable at infinity. This corresponds to convex function without. minimizers, such as log-exp-type softmax loss function for classification.
2

---

Published in Transactions on Machine Learning Research (05/2025)
Table 1: Summaary of required controllers and results: U is the set of destabilizing controllers and [M] its cardinality. n the dimension of the state. Polynomial factors on N and [ are hidden.
denotes
Required Controller
Closed-loop system
Algorithm
Regret Bound
asymptotic stability
Chen & Hazan 2021
Exponential
N/A
O(T4/5)+
et al. (2023)
Exponential
No
O expl (O(())
Dynamic Batching
Asymptotic
Yes
O + (T (xp(O((4))
Algorithm (DBAR)
Asymptotic
Yes
O(T213) + +( exp (x()))))(((()
Related works. Optimal control problems have been widely leveraged in a variety of fields with the influential dynamic programming approach (Bellman 1957). Recent successes of reinforcement learning (RI.) in safety-critical systems, such as aircraft (Razzaghi et al.; 2022), robotics (Tbarz al. 2021] and autonomous driving [Krann et al.) 2021), ) are also deeply rooted optimal control methods (Bertsckas) 2019).
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. 2010 Battistelli et al.. 2010 Stefanovic & Safooov
2011 Battistelli
et al.
2018 Li et al. 2023
Online non-stochastic 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 leverage optimal policy structure with cost function gradients (Agarwal al. 2019 Foster & Simchowitz,
2020:
Hazan et al., 2020; Hazan & Singh, 2022). Later, studies were generalized lizd to address the problem
without cost gradients information (Gradu et al. 2020 Cassel & Koren 2020: Ghai et al. 2023 Sun et al., 2023); 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 addressod in the pionecring work by Auer et al. (2002) under bounded costs in their notable Exp3 algorithm. Arora et al. 2012) later improved the algorithm using the same controller within mini-batch, attaining regret bound equivalent to the lower bound presented in Dekel et al. (2014). As we have access to the candidate controller pool in our problem setting, we adopt bandit-related approach.
Dynamic batching gained considcrable 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 (Dearakonda)) et al., 2017 Bollapragada et al. 2018: Shallue et al., 2019 Ma et al. 2023). Although this has been widely used in the machine learning literature, we adopt this idea to online control, progressively increasing the batch length within single trajectory to achieve asymptotic stability.
Adaptive learning rate in machine learning is generally determined by set of gradients observed so far (Ruder 2016). As we do not have access to the gradients in our problem, we focus on the learning rate for bandit algorithms. Several works (van Erven et al., 2011 de Rooij et al., 2014) in hedge setting, an instance of multi-armed bandit problem, suggested using decreasing learning rate as the batch length increases. Building on this idca, Li et al. (2023) proposed to use a non-increasing learning rate over time, while no thcoretical 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-incrcasing.
Outline. The paper is organized as follows. In Section 2 we formulate the problem and provide necessary definitions and assumptions. In Section 3] we propose our DBAR algorithm. In Section 4 we study the stability of the algorithm, the regret bound, and its applications in switched systems. In Section 5 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 G
3

---

Published in Transactions on Machine Learning Research (05/2025)
Notation. For vector 2, ||^|| denotes the Euclidean norm of the vector. We use (() for the big-O notation, o()) for the small-o notation, and O-) for the big-O notation hiding logarithmic factors. Let E denote the expectation operator. For a set Z, we use |Z] for the cardinality and z for the complement of the set Z. For a real number e, we use [e] for the ceiling of e. Let R denote the set of real numbers and Σ+ denote the set of nonnegative integers. For 61,62 E 24 where e2 S 61; let Verzez denote the set (fe : e2 S e S ei,e e E 24). For the notations used in the problem formulation and algorithm, see Appendix B
2 Problem Formulation
Consider a general discrete-time dynamical system Fe+1 = f(a u, we) for I t= o,....,, T1 where 2, E R is the system state at time t, u, E R" is the control input at time to be designed via an algorithm. u, is determined by selecting controller from priori finite number of controller pool consisting of n, R" + R" for i= 1, I, N. Wi E W C IR9 is the adversarial noise at time I, where W {w E R :|w||| S Wmax) and the bounding constant Wmax > O is assumed to be known. Each time instance t is associated with cost function G: IR" x I + IR. The state transition is governed by the dynamic f f: R" x R" x R2 + R. We have the following assumptions on the dynamic f.
Assumption 2.1 (Dynamic). The transition dynamic f is Ly-Lisschitz continuous with L, 2 1; é.e., [f(z, u. w) - fā, ū, ui < 1 - ø|| + I|u üll + ||we - wil) for all x, 2 E R", u E RM, w. E W. We let /(0,0,0) = fo-
We adopt the notion of locally Lipschitz continuous cost functions ot given in Li et al. 2023 which contains quadratic tracking costs along an arbitrary bounded state trajectory and action sequence.
such that 1q u) a(, x) S (Iea (max [||=]],, [| + max max{[]u]] [[wl]] []@]]]) + [2le all + || - ail) for all x, E R", R",u,ū E Rm Z There exists Co,max 2 0 such that (c,(0,0) 0)] I Cu,max for all E Z_
Assumption 2.2 (Cost functions). There exist Lei, Lez
Inpul-to-state (asymplotic) stability (ISS) is classic notion of stability implying that the controller successfully stabilizes the system under any bounded noises [Sontag 2008 Khalil 2015). Incremental (asymptotic) stability extends the input-to-state stability to describe the asymptotic behavior of some trajectory towards a different trajectory TTan et al., 2016). It is worth noting that Li et al. (023) also adopted these concepts under an exponential stability assumption; i.e., they require some collrs to satisfy exponential ial TSS 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 ι is (asymptotically) input-to-state stable (ISS) if there exists a non-increasing function B(.) : Z__ - R that satisfies ((0)= = L with lim (() = 0 and 7 > 0 such that for any Io E R" and ||we|| < Wmax for all 2 0, the sequence {zx he20 determined by 2+41 = f(z,, क (2;), w,) satisfies ||ار||| s [(t)]|zoll + max
Definition 2.4 (Incrementally stable controller). A controller x is (asymptotically) incrementally stable if there exists non-incrcasing function /(()) Z, - R that satisfies /(()) 1 with lim 38() = 0 such that for any Fo. To E R and ||w]]| S Wmax for all t 2 0, it holds that ||2: - xell < B(t) - Zoll for any two sequences determined by I++1 = f f(a,, x (1z), we) and Je+1 = f( ((x)), wx).
A Assumption 2.5 (Controller pool). Consider the candidate controller index set Po = (1,.... ......,y NY. in which
there exists a controller satisfying Definitions 2.3 and 2.4 There exists T0,max 2 0 such that [| (0)l < max for all E Po. All candidate controllers are L Lipschitz continuous; i.e., [T) +T) || $ L, | Ell for all 2, 5 E Rd and i E Po-
In Figure 1 we illustrate a concept of the controller pool for the unknown system, and how general the requirement of asymptotically stable notion is. For future use, we define the relevant sets regarding controller stability below.
Thii assumption in Definitions 2.3 and 2.4 is to guarantee 9(1)² < (8(1) for all t, which can he overcome by large 7. If relax Assumption 2.2 on ee be Lppschitz innuu, we can remove the assumption ((0)- = 1.
4

---

Published in Transactions on Machine Learning Research (05/2025)
Stubitard vita Costrilcs
Reporetally Saale Nake: Ieesptiinds (lilendyy) c=81
Stchiladd with Controler
Stahiteed Contilles
Stchileed wita Ocatriee A. E
Stehileed with Contrdess 3, U,
Ribhllaed with Conrnilex A, B
True Farametes
(a) Controller Stability notions
(b) Controller pool for unkmown nonlinear systems
Figure 1: Illustration of Assumption 2.5 (a) Our work does not require exponentially stabilizing controllers, which allow the learner to detect the stability in ((log(1/c) time. Instead, only require asymptotically stabilizing controller of the true system, where the detectable time may be arbitrarily long. (b) One can design stabilizing controllers for each parameter characterizing the nonlinear system. While we know that at least one of them should work, we do not know which one works, since the learner is unaware of the true parameter of the system. Assumption 2.5 is always satisfied the given pool contains a rich set of controllers, as long as the true system is stabilizable.
Definition 2.6 (Stabilizing and destabilizing controller). Let S denote an index set of stabilizing controllers that satisfy both of Definitions 2.3 and 2.4 We also let 21 denote an index set of destabilizing controllers that do not satisfy Definition 2.3 Thus, we have [S] 2 and S u.
Remark 2.7. Definition 2.4 is a stronger notion than Definition 2.3 due to the triangle inequality. However, for a special case of linear systems with additive noise; i.e., f(z,, π (xx). we) = Ar, + f(w,), where A E ==* and R - R", controller æ satisfying Definition [.3 also satisfies Definition 2.4 In such case,
Assumption 2.5 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 wis where ||wlll S Wmax 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 1980). Hence, it is desirable to achieve both system stability notions.
Definition 2.8 (Asymptotic stability). A system asymptotically stable if the sum of state norms satisfies limr + El | S max
Definition 2.9 (Finite-gain stability). A system is finite-gain C1 stable if there exist constants A1, > 0 such that for all T E Z4, it holds that Σ || S A Wmax T + A2.
Recall that Te and u, denote the state and action sequence for the system according to the algorithm. We
also let o and ut denote the optimal state and action sequence generated by the best stabilizing controller i' that satisfics both of Definitions 2.3 and 2.4 i.e., i* arg min;es E (2,,,, (x()))) subject to the dynamic f. Then, the regret of the algorithu is defined as follows.
Definition 2.10 (Regret). The regret of the algorithm implementing the policy nh, time t O...., T - is defined as Regret, = Eir-ro I!- [cr (Ft, u)) ca(x7, u.)].
3 Algorithm Description
Denote the number of batches in the algorithm by B. Denote by to the start time for each batch = 0, 0, B We implement the same policy within the mini-batch.
Assumption 3.1 (Dynamic batch length). We design our batch length (no)o2 as follows:
Tb is non-docrcasing and limg To = +00.
2. maxx20 To To
Tb+1 Ti and lim 76
Th+1 1.
5

---

Published in Transactions on Machine Learning Research (05/2025)
For example, 76 21 (vb + 22)as for every b 2 0 with the constants 21, 22, 23, > 0 satisfy Assumption 3.1 Specifically, 21 is a scaling factor, #2 provides an initial shift, 23 controls the polynomial growth rate, and y determines the rate at which the batch length increases with b. For future use, we refer to this type of formulation as polynomial batches with (21, 22, 2), V).
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. (2023) and the literature on linear dynamics (Cassel & Koren 2020 Chen & Hazan 2021 Ghai et al. 2023). Figure 5 in Appendix [ strongly supports the necessity of a growing batch length regardless of the noise assumption, On the other hand, our batch length requires limp-+o Ihil = 1, which means the To
ratio of two consecutive batch lengths should approach 1 as time goes by (e-g-, geometric sequences are not acceptable). In other words, the batch length is designed to increase over time but eventually saturates, which is used to ensure both asymptotic system stability and a sublinear regret. We formally present both
properties in Theorems and 4.6
Algorithm Description. We propose our DBAR algorithm in Algorithm [ (see Appendix for the notations). Lines 3 generate the state trajectory based on the selected controller Tu, for the current batch 6, and falsify the controller if it is found to violate Definition 2.3 i.e., is E U. Here, let U denote the number of times that the Break statement in Line 7 is activated. In the rest of the paper, when say the Break statement is activated, it means that Line Y of Algorithm has been activated. As the controllers in U do not suffer from the Break statement, they always remain in the controller pool. Accordingly, we have U S [4).
Lines 20 keep track of the state norm of T6+1 by determining 0&+1 and 86+1 that indicates the magnitude of the next batch's initial state norm compared to ||zoll- Note that we keep adjusting the value of 06+1 to avoid 1 > 86 + 1 (Line [4), and the adjusted 06+11 is guaranteed to be bounded by some constant (see Lemma C.5 in the Appendix). It is later discussed formally in Lemma 1.7 that these observations cause 86 * O to occur at most OUU) times throughout the algorithm.
Lines 26 determine the weight W (k) for each controller k. In Line 21 we use the sum of costs al the current batch b to add up to the weight in Line 25 In Lines 22
26 we reset the weight if $641 * Sb. This resetting weight idea to forget the costs in the past is also proposed in van Erven et al. (2011). In the scenario that the Lipschitz constant L is very large, it may help to forget the time-iarying costs co.... .--1 and restart gathering the information from the outset. Line 22 reflects this case where the next batch's 's state norm significantly deviates from the current state norm.
Lines 27 29 calculate the adaptive learning rate M6+1 = n for the next batch b+ 1 used to apply the Exp3 algorithm to our problem. Since (0++1))*++1 increases when the state norm || ll is large, and 96+1 resets to zero for sufficiently small state norm, the corresponding 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 based on the state norm. However, it essential to note that the effective learning rate, determined by the ratio indeed decreases the batch length increases even if 86+1 86. The only T.² plausible situation in which the effective rate may increase is $b+1 < S, with (ao+1)2 > 2011, Apart from this scenario, the effective learning rate experiences a polynomial decay with polynomial batches defined in Assumption 3.1 which does not cause any contradiction with the polynomially decreasing learning rate concept proposed in Aubert et al. (023).
Our adaptive learning rate stabilizes the cost of current batch, alleviating the multiplicative exponential term in the regret bound (see Table D. 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.
In the next section, we will provide a formal analysis and a proof sketch for the guaranteed system stability (Desinitions 2.8 and 2.9 and the attained regret bound (Definition 2.10 of Algorithm 1
6

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm DBAR
Input: Time horizon T; Batch length (Tb)62a; Controller parameters 9()) and 7; y (1 (7))))
Initial state zy # O: Initial learning rate ?/o > Initial time to O; Initial weight Wo(k) 0 for all h E Po. Initial probability distribution po(k) for all Po (uniform); Initial parameters so 0. 00 1.
do 2: Sample is from a distribution Ph- Terminate the algorithm if Po is empty.
1: for Batch b = 0,
15:
clse
16:
Let 8b+1 = 8 and let 0b+1 ob-
17:
end if
// Phase 1: Falsify detected dostabilixing controller
18:
else
for == tb..... min + T6 1. do
19:
Let sb+1 and let ab+1 Ct..
Implement "i, observe 24+1-
20:
end if
if | [(t 1- 1x mmmxx then
// Phase 2: Set reset weight for each controller
6:
Set Po+1 Pb {is). 7: Break
21:
Let wp((s) = Eim Ct (1 Ue)
and wx((k) = mb((s)
p.(k) [(o R) for k E Po.
8: end if
22:
if 5641 # sb then
end for
23:
Let Wo+1 (k) = 0 for all k E Po.
10:
Let to+1 =t+1
24:
else
// Record the magnitude of state norm for Phase
25:
Let W6+1 (k) = Wo(k) + we for k E Pa.
11:
if | 0g/| + 5 then
26:
end if
12:
Pick 2 that satisfies
Let 7/++1 = (0/(a))1) 22
27:
[[=)l < || ó < (as)*+1
28: For all 1 Po+1, let
13:
if S S > then
Pb+1(k)) Exep,t)
exp(-1e-1 Wo (R))
14:
Let a6+1 be any a > ag such that a [>bol||zool| S || 8 < a 2 |xol
expl ao+ Wo+1 (i)
29: end for
and let 16+1 8b
4
Main Results
4.1 Stability
In this section, we will present the stability results Algorithm !
Theorem 4.1 (Asymptotic stability). In Algorithm suppose that 2 3(00) < 1. Then, it holds that
lim T 000
|r S 7 maz-
T
2=
Theorem 4.2 (Finite-gain stability). In Algorithm 1 suppose that To 3(TO) < 1. Assume that lim H()) < 00. Then Algorithm 7 achieves fonile-gain Li slabuily;; ie., there erist constants A1, A2 > 0 such that.
T
Iz S Ai WmonT + A2, V220 0.
Lemma 4.3. Define H(t) :- ((),, which determines the scope of stabilizing controllers throughout the H(t) = 0.
entire horizon. Under Assumption 9.1 have lim
Proof sketch of Theorems and 4.2 Let B denote the number of batches in Algorithm | and recall that U
denote the number of times that the Break statement in Line 7 is activated. By using Lemma 4.3 (see the proof in Lemma
C.1 with the non-decreasing property of both T and H (T6),, obtain
ΣR- H(T))
H(TB-1)
B-2
lim T-200
lim B-0
II
Tbt1 = -0-1 1
0,
(2)
T
TB-1
Tb
B=B-U-1
7

---

Published in Transactions on Machine Learning Research (05/2025)
where the equalities stem from two important steps: limg-ro M(rg-1) 0, which follows from Lemma 4.3
78-1
with the unboundedly increasing batch length stated in Assumption 3.1 and limg-se I I 7
7x12 1,
which follows from the saturating batch length stated in Assumption 311 (more detailed derivation can
found in 17 Moreover, Lemmas C.3 C.7 indicate that falsifying destabilizing controllers in Lines result in the existence of constant M such that the following inequality holds for all T 2
B ((E((T)) + +T).
-ell S M + mamax
(3)
Substituting 2 into
3 proves both Theorems 4.1 and
4.2 (see Appendix for more proof details).
Remark 4.4. With a fixed batch length 7 as presented in Li et al. (023 the resulting closed-loop system
cannot achieve asymplotic stability since limn--so 7 Ei | 70 (1 + O(+)) > 7W0max- Thus, it is intuitively desirable to design as lim T6 = 0o to achieve an asymptotic system stability, validating our dynamic batch length strategy in Algorithm [ This idea also results in having limy B/T = 0 (sce Lemma C.9 in the Appendix). It crucial to note that we have achieved asymptotic stability even when sime- HL)) = oo. In addition, finite-gain stability can be achieved for every (3-) that satisfies H(-) < oc, which incorporates exponentially stabilizing controllers.
4.2 Regret
In this section, we will present the regret bound Algorithm | where the regret defined in Definition 2.10 is equivalent to Ei - [ce(xe, u,) - (2 ut),, considering that the policy at each time is determined by the policy Ts at the corresponding batch b.
Theorem 4.5 (Regret Bound). In Algoritho suppose that Ii To
(B((T)))
2 Then, we have
B-1 Regret,- = 0(4)) + Ō(u + 1 + +0 H(T)))
B-1 + NoNN [exp(((21)000t 0
Σ (T)))).
2
6=0
6=0
Theorem 4.6 (Regret bound with known U) Consider Algorithm | with polymomial batches defined in
Assumplion 3.1 with proper paromelers salisfying 2o (B(To)) < 2 Then, with = O 01 (R41+1)2/3 and
T2/9N175
2 maxt [N( +1)) N ([4)++))}, we achieve a sublinear regret bound. Moreover when H()) S 0 4)
R4 1/2
for all t 2 1, we have
Regrety = + 100 N1/3 + 1)1/3.
(4)
Theorem 4.6
follows from Theorem 4.5 by substituting the relevant parameters, where the regret bound in
Theorem 4.5 deeply hinges on Lemma 4.7 For the lemma, define - (0 < b < B - 1, b E 2, 86+1 * st) and Also, define V= {0 < 6 S B 1, b e Σ, 36 + 0}. In other words, [C] is the number of transitions of ss across the batches, and [V] is the number of batches whose Sp is nonzero. It turns out that both quantitics are bounded in terms of the number of the Break statement activation U (see the proof details Lemma D.3
Lemma 4.7. In Algorithm 7 suppose that 3(7)) < 1 and let U denote the number of times that the Break stotement is activated. Then, it holds that [ = O(U) and O())
Proof sketch of Theorem 4.3 Note that the expected total cost can be written as Ein- [ [w] [k)] due Lemma D.I By adopting the analysis performed previous works (Cesa- Bianchi & Lugosi 2006 van
(Cesa-Bianchi
Erven al. 2011 de Rooij et al. 2014). we divide the inner expectation of the total cost into two terms:
1
mix loss
log(EErp,, (k)))) mixability gap Espps [k)]())] + log(En-p, exp(- (k)))
7o
77u
3 Among stabilizing controllers achieving Ö(T2/3) regret bound, also cover the case where H(1) can be the order of harmonic series that is not summable infinity.
8

---

Published in Transactions on Machine Learning Research (05/2025)
Unlike the previous analysis which has the same value for nu and lh. our approach uses different learning
rates for "o and 7h since we use an adaptive learning rale given by the update rule in Line 27 The additional
terms introduced by using different rates are in [C] for the cumulative mix loss (see Lemma D. and [V] for
the cumulative mixability gap (see Lemma D.5 These terms are bounded in terms of U by Lemma 4.7 and
are reflected in the first two lerms of Theorem 4.5 since U S [2A]
After bounding the expected total cost with cumulative mix loss and mixability gap, we need study B-1
Bi Ei -t=t, - (ealaf" (("), (x")) - -e(2t, m[)], where oef (t) and uf (1) for t= to,... 1,61 - denote the state and action sequence generated by selecting the controllers before batch b according to Algorithm [ while selecting the controller i at batch b. This does not produce any exponential term since the costs are regularized
(ou)
with the factor (an)2*s, The additional term introduced by regularization is in ((V)) + O BB1 (Tx)) (see
Lemma D.7p, where [ is again bounded in terms of U. These terms are reflected in the first and the third terms of Theorem 4.5 More proof details on the rest of the terms are provided in Appendix D
Remark 4.8 (Lower bound). The regret bound 0(T2//N1/3( + 1)3/3) provided in Theorem 4.6 is similar
to the lower bound presented in Dekel et al. (2014), except that there is an extra term ((4) + 1) 173 reflecting
the unbounded costs that cannot be mitigated by merely asymptotically stabilizing controllers. Moreover, a stability-agnootte 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((Z()) in regret. To illustrate, the Chen & Hazan 2021 provides the lower bound involving an exponential term in the state dimension n (see Theorem 3 in their work), which is analogous to [M]] in our setting in the sense that the magnilude of both quantities explains the difficulty of controlling the system. They showed that any algorithm must observe at least (n)) states to learn every mode of the system and arrive at a stabilizing controllor, during which it inevitably experiences a regret bound of exp(O(n)). Similarly, in our setting with a finite set of controllers, any algorithm should observe the behaviors of [u]] number of destabilizing controllers before consistently applying a stabilizing controller, and exp(O(((4)) is unavoidable as a result. While Chen & Hazan (2021) assumed linear dynamics, our work deals with nonlinear dynamics for which finding an optimal controller is NP-hard, and thus the discrepancy between the lower bounds exp(O(n)) and exp(O((4)) is indeed necessary to reduce some of the complexity. Due to our case of the lower bound, the exponentially increasing term can be lackled by reducing it by the inverse power term on T al best. Theorem 4.6 aligns with this idea since the resulting regret bound involves the term O(T- exp(O((4)) by factoring in every potential exponential term to be multiplied with the initial lcarning rate no = (QTT-2/3), which inherently serves as 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 and Appendix (A).
Remark 4.9 (Nonlinear control). Our approach is useful to extend the stability and regret analysis beyond linear dynamics, but if [4] is too large, it would be difficult to reach good enough performance as the regret bound depends on (x)(O((Z))) This occurs because we have focused 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 [ number of connected sets, where [24] is not too large and each set disjoint from the others. The agent can apply tochniques of contimuous parameterization (e.g. gradient descent) within a set and also transition between separate sets by leveraging our technique, where many real-world problems involve both lypes of decisions, parameters within that strategy (continuous).
such as selecting a high-level strategy (discrete) and This mixture of algorithms for discrete and connected sets will be an interesting future work.
4.3 Regret with Unknown Number of Destabilizing Controllers
Now, a question ariscs as to what happens if [M]] is not known in advance. With Algorithm 1 one can leverage [2]] + 1 N to upper-bound the regret in Theorem 4.6 and achieve (/72//N2/5 at best (without considering exponential terms) by determining no and (T. (o))020 as if there were only one stabilizing controller. It turns out that we can roduce the bound to 2 as in Algorithm D where we increase the value of μb if the Break statement in Algorithm [ is activated and keep it unchanged otherwise.
N 1/13 (117 + 1)1/2) by adaptively changing the value of n)
9

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm DBAR- [4]
Input: Add two more inputs μo = 0. y > 0.
// Modification Add the following IF IF-ELSE Statement right after Line Algorithm
if Pb+1 Po then 16+1 PAb- else Pb-1 1bb + 1. end if
// Modification 2: Incorporate 16+1 to set 76+11 in Line 27 in Algorithm
1/ 1/o (16+1 +
Theorem 4.10 (Regret bound with unknown (U). Consider Algorithm 1 Then, with 2.2 no = 0 ((773/17))) and T 2 max Ni N); we achieve a sublinear regret bound. Moreover, when H(1) - O for all L 2 1, we have
2 with polynomial batches defined in
Assumption 3.1 with proper parameters satisfying 2 (3(TT))2 < 2V5'
Regret, = = + Ö(T-1/3) (sp(O())) + 1)1/2.
55)
Proof sketch: Define Ya.r == n/ It turns out that for every r = =,...., U, Ō "u.r"' appears in the regret instead of the integrated term ( (1)))1) in Theorem 4.5 The constant [2]] + 1 is dist among each term. Under the constraints given by the disintegration rule using Lemma 4.7 for each r, one can Ö( Y0.r
establish an upper bound of ( (1()+)))1) on the sum of Ó ((1)) terms over r = O,...., U by attaining the coefficients of these terms with complementary slackness in Karush-Kuhn-Tucker (KKT) conditions. The
details are available in Appendix B
Our DBAR algorithm can also be applied to scenarios such as those switched systems [Tuusi et al. 2008
Zhao et al. 2022) in which the transition dynamics and the associated controller pool change according
either the detection of destabilizing controller or pre-determined time instants (Battistelli et al.) [001]]
well as the ballooning problem [Ghalme et al. 2021 where the controller pool may expand. We proposed
Algorithm 3 the switching version of DBAR, in Appendix F
5 Numerical Experiments
To demonstrate the main results of this paper, we provide illustrative examples on both linear and nonlinear dynamics with adversarial disturbances.
Enample 1 (Linear): Consider the following linear dynamical system with xe E R.0 and E R
Z++1 A"x; + B" + we. t= 0,
(6)
where A and B" are 10 10 matrices whose entrics randomly generated from Uniform[-1, 1]. We also set zo [100, 200]' @ 1; and Wy = [sin( (4) sin & 1s, where @ denotes Kronecker product and 1, denotes d x 1 vector of ones. We consider a linear policy 1, Krt, where K E 100010 To construct controller pool, we first generate K* such that the absolute values of all eigenvalues of A + 8 K* are less than 0.8. K* is naturally an exponentially stabilizing controller. Then, we construct our controller pool to include K along with 100 other controllers, each of which is a variation of K* obtained by selecting one entry of K* and multiplying it by 1.1. The constructed pool has U 58 out of 101 candidate controllers. The goal is keep the state near the origin, where the cost function quadratic each time, namely Ce(2t, u.) ||
Falsifying destabilizing controllers moderately stabilizes the state norm (i et al. 2023 Compared to their work, Figures 2(a) and 2(b) 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 60%
of controllers in the pool are destabilizing the system. In this case, Figures [ and 2(d) 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 In Appendix G.1 also provide the experiment details and simulation results with noise terms generated by uniform random
10

---

Published in Transactions on Machine Learning Research (05/2025)
Gend Boal foad
Rest P, Rood
draauii v, fand
fand v, aikeltis y
Mrassaos, fool
drramic v, iidaptoo a (1MBAZ)) 340
dysamte staptine (DBAR)
adeptice
Bedl adaptin
Apsuntt skkpine q Yehwwe
dpwcckle c. adlapto (DBAR)
3000 SIT [n]
5
12000
Ernen
12000
12010
(a) Stability analysis
(b) Regret analysis
(c) Adaptive learning rate under (d) Dynamic batch length under dynamic batch length
adaptive learning rate
Figure 2: The stability and the regret in the linear system under sinusoidal noise. Fized T, fixed n represents the algorithm in Li et al. (2023). Ablation study of the algorithm is presented.
1.0
400
threente ry fisad y
dyassse lsall
Pellearr
food v. staptavng
food v, silopivv
dhruenie rudetti (DEAR))
dysoure r.attttt (DRAI))
Aypecca
300
Begreet
0.6
Tell poilte
Lender System
Sogieti 2 2
2003
0.1
3
100
0.2
Soiee App Be
0
.000
2000
5000
40C3
500
1000
20000
5000
4000
5.00
time 2
time
(a) Ball-beam Leader-follower system
(b) Stability analysis under (1()) (c) Regret analysis under (1(()
Figure 3: The stability and the regret in the leader-follower system under sinusoidal noise, where the leader is represented by a ball- beal- system. We selected (1())= = min mnin(10) (10/tl.00 05 ,1} and used squared sum of state and action norms as the cost.
walk, where - w has uniform distribution for t 2 1, as well as the results with truncated Gaussian noise for sanity check.
We now consider the 100-dimensional leader-follower system (orbidi et al. 201 where the leader is represented by a ball-beam system, and the followers leverage the leader's state sta stabilize themselves. Specifically, if the leader is controlled by destabilizing controllers, the followers may also fail to stabilize. The leader is represented by nonlinear noiso-injected ball-beam system (Hauser et al. 1992
Example 2 (Nonlinear):
G = B(x - 9.81 sin 0) + 3wz, Ö = Uzz
B = 0.7143.
where æ is the ball position, 0 is the beam angle, u, is the action, and w.x(() sin (+) Also, consider the followers' system:
2 = A(x, 3, -9,81B0, -9.81B8 + Az + u2 + 3w.z
(8)
where ( 0, E R2 are the states of the leader given below in 7 z E R96
are the states of the followers, u, e R6 is the action of the followers, w. = isin ( ), sin( (Tm)) I & 148 E I9 and A, A are relevant random
matrices. Note that the number of states in the entire system is 100.
For the action uay we now adopt a broader notion of stabilizing controllers and choose the policy class to be the nested saturating control (Teel 1992), without considering exponentially stabilizing notions. For the action ug we consider a linear policy in 2; however, the policy is inherently nonlincar with respect to the entire state, as the leader's system itself is nonlinear. In Figures 3(b] and 3(c] we observe that dynamic batching does not necessarily stabilize the state norm by itself. However, if an adaptive learning rate is additionally
11

---

Published in Transactions on Machine Learning Research (05/2025)
1.0
vn (0.30 10
fowd Bood gg
foel Lood
135
deturiio v. Frodd adaptire
Sphorio r, [bed
vi (0 10)1
0.8
faxi slaptheer y
1.04
dpporll v. Ailppeee y (DBAR)
doserric v, v,aseatti (DSMR
Regretoo
7 J
10
Regrete
0.6
1.00-
76 - (0 10+00 20)//
0.75
7 (5 + 20)1/
0.20
102
0.2
0.25
0,00
0.00
1100
2030
30402
40000
50020
2000
3000
000
5000
time
(a) Robustness batch length designs (b) Stability analysis under (t( (e) Regret analysis under (a())
Scnsitivity analysis of hyperparameters. (a) For the lincar system in Example 1, we report the regret at time 2000 based on various initial batch lengths and batch length designs. (b), (c) For the nonlinear
Figure 4:
system in Example 2, we selected (2()) min 1.8 11 to compare with 31 (t) given in Figure 3
applied, DBAR effectively stabilizes the explosion of the nonlinear system and enjoys the improved regret, even when we use polynomially stabilizing criterion (t) min (10/r1.06, 1) O to define the stabilizing controllers (sce Definition 2.3 More experiment details are available in Appendix G.2
Sensitivity Analysis of Hyperparameters: We now provide the robustness of our algorithm under modifications in hyperparameters. For the linear system in Example 1, we examine the hyperparameters associated with the two important components of DBAR: the batch lengths (To)220 and the initial learning rate 'uu- Figure ((a) presents the behavior of different batch length designs, and shows that any batch length т. yields a desirable regret at time 2000, as long as the initial batch length To is sufficiently large. This phenomenon strongly supports Theorem 4.6 stating that To (B(TT))2 2/2 with polynomial batches defined in Assumption ensures a regret given in (4.. Note that a large To will naturally satisfy the inequality since ((-) is a non-increasing function and the polynomial batch structure ensures that 4 remains constant regardless of To- Meanwhile, we observed that the policy selection was not affected by the initial learning rate fJo, resulting in the same regret and demonstrating the robustness of our algorithm to To.
3.1
For the nonlinear system in Example 2, we provide the robustness of our algorithm with respect to the choice of ((t) defined in Definitions 2.3 and 2.4. We compare two polynomially decreasing functions: (1(() = min 1} (see Figures 3(b) 3(c) and B2(t) = min(10/t2.08 1} (see Figures 4(b) A(c).. While DBAR performs effectively in both cases, the behaviors of the two functions are slightly different in the sense that the system already appears to be stabilized even without some components of DBAR based on (2((). This stems from the extent of destabilizing controller removal: (2()) removes the controller based on criteria more strict than (1) since 1.08 > 1.05. 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 candidate controller pool had not included any controller satisfying the strict assumptions, the algorithm would have terminated, failing to keep the system running. This finding illustrates why it is crucial to allow a broader class of controllers and yet achieve a light regret bound, which was the ultimate goal of our work.
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 novel Exp3-type algorithm with theorctical guarantees. The proposed algorithm uses a dynamic batch length to achieve asymplotic 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 inchude extending these results to problems with explicit safety constraints while selecting the best stabilizing controller among continuum of candidate controllers.
12

---

Published in Transactions on Machine Learning Research (05/2025)
Acknowledgments
This work was supported by the U. S. Army Research Laboratory and the U. S. Army Research Office under Grant. W911NF2010219, Office of Naval Research under Grant N000142413 42411424,,77, AFOSR, NSF, and the UC Noyce Initiative.
References
Naman Agarwal, Brian Bullins, Elad Hazan, Sham M. Kakade, and Karan Singh. Online control with adversarial disturbances. In International Conference on Machine Learning, pp. 111-119. PMLR, 2019.
Jason Altschuler and Kunal Talwar. Online learning over finite action set with limited switching. In Conference Learning Theory, volume 75, pp. 1569-15733 PMLR, 2018
Oren Anava, Elad Hazan, and Shie Mannor. Online learming for adversaries with memory: Price of past mistakes. In Advances in Neural Information Processing Systems, volume 28, pp. 784-792, 2015.
Raman Arora, Ofer Dekel, and Ambuj Tewari. Online bandit learning against an adaptive adversary: from regret to policy regret. In International Conference Machine Learning, pp. 1747 1754. PMLR, 2012.
Raman Arora, Teodor V. Marinov, and Mchryar Mohri. Bandits with feedback graphs and switching costs.
In Advances in Newral Information Processing Systems, volume 32, pp. 10397-10407, 2019.
Julien Aubert, Lue Luhéricy, and Patricia Reynaud-Bouree On the convergence of the mle as an estimator of the learning rate the exp3 algorithm. In International Conference on Machine Learning, pp. 1244 1275. PMLR, 2023.
Peter Auer, Nicoló Cesa-Bianchi. Yoav Freund, and Robert E. Schapire. The non-stochastic multi-armed bandit. problem. STAM Journal on Compuling, 32(1):48 77, 2002.
Simone Baldi, Giorgio Battistelli, Edoardo Mosca, and Pietro Tesi. Multi-model unfalsified adaptive switching supervisory control. Automatica, 46(2):249 259, 2010.
Corneliu Barbu, Rodolphe Sepulchre, Wei Lin, and Petar V. Kokotović. Global asymptotic stabilization of the ball-and-beam system. In Conference on Decision and Control. IEEE, 1997.
Giorgio Battistelli, Edoardo Mosca, Michael G. Safonov, and Pietro Tesi. Stability of unfalsified adaptive switching control in noisy environments. IEEE Transactions on Automatic Control, 55(10))2424-2444 2010.
Giorgio Battistelli, João P. Hespanha, Edoardo Mosca, and Pietro Tesi. Model-free adaptive switching control of uncertain time-varying plants. The International Federation of Automatic Control, 44(1):1273 1278, 2011.
Giorgio Battistelli, Daniele Mari, Daniela Selvi, and Pictro Tesi. Direct control design via controller unfalsification. International Journal of Robust and Nonlinear Control,
2018.
Richard E, Bellman. Dynamic programming. Princeton university press, 1957.
Dimitri P Bertsekas. Reinforcement learning and optimal control. Athena Scientific Belmont, MA, 2019.
Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi, and Ping Tak Peter Tang. A progressive batching I-bfgs method for machine learning. In International Conference Machine Learning, pp. 620 629. PMLR, 2018.
Asaf Cassel and Tomer Koren. Bandit linear control. In Advances in Neural Information Processing Systems, volume 33, pp. 8872 8882, 2020.
N. Cesa- Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
13

---

Published in Transactions on Machine Learning Research (05/2025)
Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems. In Conference on Learning Theory, volume 134, pp. 1114-1143. PMLR, 2021.
Steven de Rooij, Tim van Erven, Peter Grünwald, and Wouter M Koolen. Follow the leader if you can, hedge if you must. Journal of Machine Learning Research, 15(1):1281- 1316, 2014.
Ofer Dekel, Jian Ding, Tomer Koren, and Yuval Peres. Bandits with switching costs: T2/3 regret. In Symposium on the Theory of Computing, pp. 459-467, 2014.
Aditya Devarakonda, Maxim Naumov, and Michael Garland. Adabatch: Adaptive batch sizes for training deep neural networks. arXiv preprint
2017.
Dylan J. Foster and Max Simchowitz. Logarithmic regret for adversarial online control. International Conference on Machine Learning, pp. 3211 12112221, 2020.
Udaya Ghai, Arushi Gupla, Wenhan Xia, Karan Singh, and Elad Hazan. Online nonstochastic model-free reinforcement learning. In Advances in Neural Information Processing Systems, volume 36, 2023.
Ganesh Ghalme, Swapnil Dhamal, Shweta Jain, Sujit Gujar, and Y. Narahari. Ballooning bandits. Artificial Intelligence, 296:103485, 2021.
Paula Gradu, John Halmaan, and Flad Hazan. Non-stochastic control with bandit feedback. Tn Adoances in Neural Information Processing Systems, volume 34, pp. 10764 10774, 2020.
John Hauser, Shankar Sastry, and Petar V. Kokotović. Nonlinear control via approximate input-output linearization: the ball and beam example. IEEE Transactions Aulomatic Control, 37(3):392 398, 1992.
Elad Hazan and Karan Singh. Introduction online nonstochastic control. orXie preprint ar trXiw:2211.09619
2022.
Elad Hazan, Sham M. Kakade, and Karan Singh. The nonstochastic control problem. In Proceedings of the
31st International Conference on Algorithmic Learning Theory, volume 117, pp. 408-421. PMT.R, 2020.
David J. Hill and Peter J. Moylan. Connections between finite-gain and asymptotic stability. IEEE Transactions Automatic Control, 25(5):931 936, 1980.
Julian Ibarz, Jie Tan, Chelsea Finn, Mrinal Kalakrishnan, Peter Pastor, and Sergey Levine. How to train your robot with deep reinforcement learning: lessons we have learned. The International Journal of Robotics Research, 40(4-5):698 721, 2021.
Hassan K. Khalil. Nonlinear Systems. Pearson Education, 2015.
B. Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A. Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Trunsactions Intelligent Transportation Systems, 23(6):4909 4926, 2021.
Yingying Li, James A. Preiss, Na Li, Yiheng Lin, Adam Wierman, and Jeff Shamma. Online switching control with stability and regret guarantees. In Learning for Dynamics and Control Conference, pp. 1138 1151. PMLR, 2023.
Yiheng Lin, James A. Preiss, Emile Anand, Yingying Li, Yisong Yue, and Adam Wierman, Online adaptive policy selection in time-varying systems: No-regret via contractive perturbations. In Advances in Neural Information Processing Systems, volume 37, 2023.
Zhenguo Ma, Yang Xu, Hongli Xu, Zeyu Meng, Liusheng Huang, and Yinxing Xue. Adaptive batch size for federated learning in resource-constrained edge computing. IEEE Transactions on Mobile Computing, 22 (1):37-53, 2023.
Fabio Morbidi, Francesco Bullo, and Domenico Prattichizzo. Visibility maintenance via controlled invariance for Sader-follower vehicle formations. Aulomation, 47(5), 2011.
14

---

Published in Transactions on Machine Learning Research (05/2025)
Pouria. Razzaghi, Amin Tabrizian, Wei Guo, Shulu Chen, Abenezer Taye, Ellis Thompson, Alexis Bregeon, Ali Baheri, and Peng Wei. A survey on reinforcement learning in aviation applications. or arxiv preprinl arXiu:2211.02144. 2022.
Sebastian Ruder. An overview of gradient descent optimization algorithms. ar preprint 1609.000..4400 2016.
Christopher J. Shallue, Jaehoon Lee, Joseph Antoguini, Jascha Sohl-Dickstein, Roy Frostig, and George E. Dahl. Measuring the effects of data parallelism on neural network training. Journal of Machine Learning Research, 20(112):1-499 2019.
Jonathan W. Siegel and Stephan Wojtowytsch. A qualitative difference between gradient flows of convex functions in finite- and infinitediimensional hilbert spaces. arXiv preprint orXiv:2310.17611 2023.
Eduardo D. Sontag. Input to state stability: Basic concepts and results. Nonlinear and Oplimal Control Theory, pp. 163 220, 2008.
Margareta Stefanovic and Michael G. Safonov. Safe Adaptive Control: Data-driven Stability Analysis and Robust Synthesis. Springer, 2011.
Jennifer Sun, Stephen Newman, and Elad Hazan. Optimal rates for bandit nonstochastic control. Advances in Newral Information Processing Systems, volume 36, 2023.
Andrew R. Teel. Global stabilization and restricted tracking for multiple integrators with bounded controls. Systems & control letters, 18(3):165 171, 1992.
Mani M. Tousi, Idin Karuci, Shahin Hashtrudi-Z4e and Amir G. Aghdam. Supervisory control of switching control systems. Systems & control letters, 57(2):132 141, 2008.
Duc N. Tran, Björn Rüffer, and Christopher M. Kellett. Incremental stability properties for discrete-time systems. In Conference on Decision and Control. IEEE, 2016.
Tim van Erven, Wouter M Koolen, Steven de Rooij, and Peter Grünwald. Adaptive hedge. In Advances in Neural Information Processing Systems, pp. 10565-10576, 2011.
Rui Zhao, Zhiqiang Zuo, and Yijing Wang. Event-triggered control for networked switched systems with quantization. IEEE Transactions on Systems, Man, and Cyberneties: Systems, 52(10))6120-6118, 2022.
15

---

Published in Transactions on Machine Learning Research (05/2025)
A Necessity of DBAR under weaker stability notion of required controllers
To illustrate how siguificant 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 achiove a state near 0, and we would like to detect this stability by observing whether one arrives at a state less than 1 c, where is an arbitrarily small positive number. Exponentially stabilizing controllers guarantee to detect the stability in ((log(1/e) time. However, with an asymptotically stabilizing controller, if the controller is designed to keep the system state unchanged for arbitrarily long time T and then collapse the state towards O afterward, one camnot, detect the stability before time T regardless of how small is. In such a case, even though the controller ultimately achieves the goal, it may take 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 in our problem setting, it may take long time to observe any abuormal behavior in the closed-loop system. Such an issue cannot be handled by fixed batch length and in that sense dynamic batch length is a necessary part of our work. In Table D we have stated the intermediate step "Dynamic Batching" to achieve closed-loop system asymptotic stability, which was not achievable by the previous works.
Figure 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 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 "ymax = 1.5, while the orange line remains below the red line after certain time.
Bood
douanier r
dynamde
Statistical Noise (a)
(b) Adversarial Noise
Figure 5: The state norm with fixed batch length compared to that with dynamic batch length. T++1 Iz + 0.15,, + We with un Krx where K E [-3.0, 2.9, 228, ................................ 4.9, 4.9,5.0). We use To 10, 7 3, and
set Fmax = 0.5. The noise we is (a) i.idd sampled from Uniform -.22, 0.5], and (b) 0.15 + 0.35 sin5ssn( 1.)
However, it turns out that the resulting regret by dynamic batching contains the multiplicative term 0(T1/3). ex((O)()))), which is because dynamic batch length induces H(TB-1) to be necessarily multiplied with exp(O((4()). (sce Corollary D.10p. 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 asymptotie). We developed this approach by factoring in every potential exponential term to be multiplied with the initial learning rate 1jo- O(T-2/3). which has negative exponent on T, thus inherently serving as mitigating factor (see Theorem 4.6 and the term NoN B-1 E., (f*))² in Lemma D.5p. Due to Lemma 4.7 one can explain that the remaining terms produced by the splitting can be bounded by O(Z))). More details can be found in Appendix D
16

---

Published in Transactions on Machine Learning Research (05/2025)
B
Glossary
Before formally presenting the proofs, we provide a glossary to help readers understand the notations of our algorithm DBAR (sce Algorithm 1
Table 2: Glossary
Notation
Mcaning
state at time t in the algorithm
optimal state at time t
U2
action at time t in the algorithm
optimal action at time t
(2 Up
cost at time the maximum norm of the noise the length of time in the algorithm the number of batches in the algorithm
Wmmxx
T
B
the initial time for each batch b the batch length at batch b
Tb
learning rate at batch
in
the controller selected at batch b the number of controllers in the candidate pool
N
Wn. (K)
the weight of controller k at batch b
(b(k)
the probability of selecting controller h at batch b a. set of available controllers at batch b
Po
Ob, 86
(or))hh indicates the magnitude of the state norm at 4, compared to |
B(1),
applying a stabilizing controller incurs | S [()]]]=ol + 7m0mx
Lf
Lipschitz constant for the dynamic f Lipschitz constant for any controller и
L
U
the number of times the Break statement is activated the next batch after the Break statement is activated
b by
C Stability Proof
Let by..... by denote the next batch after the Break statement is activated: i.e., | || > (tr.. to =1)l + mm for every u l....UU. U. For future use, let bo = and bu+1 B. Accordingly, too = to 0 and fby_, =t = 1
Lemma C.1 (Restatement of Lemmn 4.3 Define H(I) = E 3(1). Under Assumption 3. we have
H(t) 0.
lim 1000
Proof. Recall that we designed ((-) to be non-increasing and nonnegative. Then, we have 3(1) S fi_,,,_, 3(x)dx for every integer 2 Using the inequality, one can write
0 0 = 3(0) + Σ 3(1) < 8(0) + f 1(d ((z)dz.
(9)
H(t) 1 If lime-so H1()) < oo, clearly lim ((t) + 0 as + oo to derive
0 holds. If Tim H(1) Do, we leverage I, L'Hôpital's rule with
lim H(t) lim
3(0) + Sa f--1 3(x)dr
3(t 1) 0,
lim
where the first inequality follows from
17

---

Published in Transactions on Machine Learning Research (05/2025)
Lemma C.2. For 0 $ j & k, we have
H(Tx)
S Tk (TT))
Tj
Proof. For 0 osjs < k
H(T))) (T) S (T;))
H(Ty) + EX-
3(1)
(Tk - ( -((r))
Tk Tj
S +
Tj B(TT)
where the last incquality is due to the non-increasing property of B(-). The equality holds when 8(0) 8(T 1)..
Lemma C.3 (Sum of state norms in single batch). In Algorithm 7 for each butch b = 0, 1..... B 1, the
following inequality holds:
t++1-1 -1
|ل S (T mard 1)
Proof. For = 1b, we have ||x||| s ((0)]aaa, |l since ((0) = For lb < S 16+1 1, we have
| & B(t (b) 1 ma
(10)
Summing up all incqualitics gives
|sll| < H(b++ [n)ll + 70max(l6+ lb - 1).
Ammt
Since Line 5 of Algorithm D is not satisfied, tb+1 ty. This completes the proof.
Lemma C.4 (Weighted sum state norms between the two consccutive Break statements). In Algorithm 1 suppose that I ((Ta) < 1. For every next batch index after the Break stalemend u 0,..., U, the following
To
inequality holds:
besi-1
WWmax
H (Tr.)))/ET H(To)llzalll E That1 ((To..) Tou
|| + 1 ((T. b=
H(T.).
Proof. Since we designed (To)220 to have non-decreasing тr and non-increasing Teil ((T)) S Toll ( & ( & a 3(7o) < 1 for every b 2 1 since ((-) is non-incnern non-increasing.
notice that we have
If but1 bu + 1, the inequality clearly holds since Te. B(T bb
Otherwise, consider the following
inequality for bn < but1 1:
H(n))lE < (( ll H(TT)
H(m.) 3 ((T--))H(TT-- .ll HT.))yuax:
H(T-11)
where the inequality holds since Line 5 of Algorithm is not satisfied. Recursively applying this inequality, one arrives
H H(Ta+1) ((Ta)
3(Ta)) (HTr. || HTT)) (1 (1+ + Σ II ((T)))
a=
b' bb=by +1 a=b
H (To++1) H(Ta)
3(Ta)]
((m..)[2Ea) (TT)) (1+ +
Σ
[8 [8(00++1]&--
b'=b.
18

---

Published in Transactions on Machine Learning Research (05/2025)
(Ta+1)) B(Ta)] H (TT. ) ((T)) 1- (
(11)
H (Ta)
a=
Ta+1 (Taa)
-H(rblllareoo (Tb)) B 3(Tb....
WW
Ta
a a=bu
Tout1 B(Tow))
b-bb
-HT
(T))
WW
The
1 B(Tt++1)
where the second inequality comes from the con-increasing property of B(-), the third inequality is by
((To+t1) < 1, the fourth inoquality is duc to Lemma C.2 and the last incquality comes from the non-increasing
property of Th+1 ((r)). Since Thu-l ((To.) < summing up the above inequalities for ba < S bu+1
completes the proof.
]
Lemma C.5 (Next state norm after the Break statement). Define Mi =- L5(1 L Lorr (To, Wmox) fo- Then, for every 1,..., U, we have
F s (2 + 2t. M₁.
Proof. Suppose we picked a controller ne at time step t. Then, by Assumption 2.5 we have
| || = (zz) (0) + T. (0) < [[=((x)) n. (0) + [|)] S T. ||aeel + To,max-
(12)
Combining the above inequality with Assumption 2.1 one can write
||++1||| = (I, ue, we) - /(0, 0, + 1(, 0)
S (Ire, ue, we) - f(0, 0, 0)11 + 11( 0)1 - ( + +|uuell +/, II) + fo
S ([ + L [xell + TT, wmax) + fo
(1 + L=) [2zell (TT, Wmax) fo.
Thus, for every u = I,... U, we obtain that
| || S L1 + L.m 11 -||| + L mao + Wmax) fo
< L + (3(L,. - 1b--1 - 1)ll .ll + 70max) ) + (T0, + +mmxx) + fo
= [1 + (to, -b--1 1)1|=em.-11 || + M1
s L1 + [.))( -1,. + M1.
where the second inequality holds since Line 5 of Algorithm I is not satisfied during to < S to. 1 and the equality holds for the last inequality when 4. = lb, 1 1. This completes the proof.
Lemma C.6 (Weighted sum of state norms along the Break statements). In Algorithm TWmmes + Mi. Then, there exists a consland C 2 such that
suppose that
(T)))) < 1. Defone M2 == Ly + L 3(0)) 1
(1 (.)
(LL, + (=) - 1)M2 H (y (0) [Too
Σ H(T 11
+ 1]2
Proof. Since we designed
Til to converge, there exists R > such that Di To
< for all b 2 0. Moreover,
since lim Ro+1 = and ((To) < 1, there exists b² > such that
b b'
To+1 <
1
(13)
Tb
B(To)
19

---

Published in Transactions on Machine Learning Research (05/2025)
Accordingly, for any two batches d' > 626 O, have
8' Ta+1 Ta
R¹. B(TO))
TV [8(m)))0' - [B(TT)]
(14)
a=b
considering that 6 and 8' b* yields the largest possible upper bound due to Now, define C R
8(m))
Notice that we have C' 2 since the left-hand side of 14 is greater than equal to when = b + 1. Then, for every u = 11....,,, one can write
(Tb..)
H(rb))ll || S L1 + (00)
|l HTo M
H(To--1)
((b
ba-2
((Ta+)) ((Ta)
L (=))(0)
II
B(Ta)] H(Too-))
H (
ambu
L + (0) 1- ((Th (T........
YWmax
L (x) ((r...)
[3( bu-1-11-11 -u ((To..)) 1 + H (To M2
((To.-1)
[3(Tbu } })bu-Bu-11- -u-1-1 H(TD 1 H(To.) < Ly + L=))((0) The
Tb
(1+ L,) ((Tb.-))|[Z
(To,
where the first inequality is due to Lemma C.5 the second inequality is by 11 in Lemma C.4 the fourth
incquality is due to Lemma C.2 and the last incquality is by (14). Recursively applying this incquality, one arrives at
H(To 12th || $ (11(0((()))))) M2
[1, + Lz)
$ +,,1(=++)))00000) (T
Ly + + )8(0)C
M2H(T
< (1 +1)+4(0)))) [ + LG(1 + L=)3(0)C 1
where the second inequality comes from the non-decreasing property of H(-) and the equality holds when
H(r,)) = ... H H(ro)). Notice that for &' > b 2 0, the case H(Ty) H(T)) arises when
B(T) + +)= -..- ((Tx) O. Since L1 La 3(0)C > 1, summing up the above inequality for u = 1,..., U
completes the proof.
Lemma C.7 (Sum of state norms). In Algorithm 1 suppose that to B(T)) < 1. Then, we have
T | s
B-1
Σ
(||=oll + H( ))) + ma
(0
2 H(T.)) + T)
t=0
b
Proof. Applying Lemma
C
C.4
and C.6 in turn, we have
T
butt 1 f-111
Σ
|
Σ
Σ
|
tmty
butt
H(TT) 12
w 1)
b=b,
but1-1
1
H. (To..) || ||+ 1 ((To
Wmx
Σ
(((T)) 7Wmax (Wmax(touss th -1)
+h
B(TTw)
u=0
b=b,+1
20

---

Published in Transactions on Machine Learning Research (05/2025)
U
B
U
$
(Tb.. 1l 1l + 1- (())
max
H(m)) Σ H(T)))) + yW (T U)
(TO)
==
6=
u=0
1
H (Tb.. (0ob))l12 1| ||
max
H HTT)) + TWmmxx
L (T))
1 (T))
TO
6=0
(TO) [oll
[ + LA 1,)3())))++
H (
(L + L.) 1)M2
Di (TT)
(TT)
[1 + L [=00( 1)2
B-1
71mmax
Σ
H(Tr) + mym
1 (-)(m))
B-1
= =[ Lx)3(0)C1 (Ilæoll + (Tb.))) ))) + max (0
H(T))) + +T)
b=0
where the equality holds for the fourth inequality when Line b horizon.
Algorithm is not satisfied for the entire
Theorem C.8 (Restatement Theorem Asymptotic stability). In Algorithm suppose that
I (T)) < 1. Then, holds that
lim
[xell S 7/W maz.
Proof. We mainly use Lemma C.1 to prove the asymptotic stability. First, we have
H(Tby) S H(TT-1) =(T- o(T),
(15)
where the first equality is due to Lemma C.1 and TB-1 T when there is only batch over the entire horizon. Now, consider the following relationship between the mumber of batch B and the time horizon T:
B
B-U-1
Σ
T2T
Σ b=0
+
(16)
b=0
where the second inequality is due to the non-decreasing property of n. Now, if Eb= H < co, clearly ΣE H(T)) (T)) Otherwise, define H(Tn) = ((Tn-)). Then, we have
BB-1 ((T))
lim DB-1 (T6)
S H (Tb)
db
lim T-000
lim
B
2b=0
- To +U
B
Tu -0 U--U1
Todb +
(TTB-1)
H(TB-1)
B-2
T++1
lim
lim
B+000
TB-U-1 B
TB-1
b= U-1
0 10 =0
(17)
where the second inequality leverages the non-decreasing property of both тh and H(n,,, the remaining
equalities leverage L'Hôpital's rule, Lemma C.1 and limo Th
Tael 1. Thus, with Lemma C.7 we have
Σ |لll| s (1 (læol + o(T))) + Wax (T + oTT).
This completes the proof.
Lemma C.9. In Algorithm have
B lim
0
T T
21

---

Published in Transactions on Machine Learning Research (05/2025)
Proof. Recall the relationship stated in 16
between T and B. Using the second incquality, we have
B
B
B
S lim 7-0
lim
lim T
T
T0000
0==
B-U-1
To
+U
To + p Todb + U
lim T-220 7B-U-1
0,
where the third inequality uses the non-decreasing property of To, after which we use L'Hôpital's rule. This completes the proof.
Theorem C.10 (Restatement Theorem 4.2 Finite-gain stability). In Algorithm suppose that ((T)) < 1.
Assume that lim (t) oo. Then, Algorithm 7 A1, A2 > 0 such that for all T E Z.t
achieves fonite-gain L1 stability; i.e., there exist constants
T |stlll < A Wmar + A2-
Proof. Since lim H(t) < 00. there exists constant d that upper-bounds H(t); i.e., H(t) S 41 for all
12 O. Likewise, by Lemma C.9 there exists a constant that upper-bounds T- Thus, with Lemma C.7 one can write
x S OLL ([æzll + q:)) + yWmax (O(Bq)) +T)
B
=0(L((1+..))00)))) (11 + 91)) + 7(1 _ (g1)) Wmax T
s 00(1,1((+++++)00000)(0)()0) + +
+ 7 + (q)
Wmax T.
This completes the proof.
D Regret Proof for Algorithm
Lemma D.1. In Algorithm we have
E (16)) Eip- Eanps (k)]].
Proof. Given i io: we have
wr((b) I(is=10 = wbb)),
Ex [w/[k)]]
Σ po(k)
(18)
(k)
KEP
which implics that (k) sampled from Ps is unbiased estimator of wi (16). Thus, for all b -=00 0, 1..., B 1, one can write
E ig oi [it)] Eig, [1os((s) Ei,- Ei, (wo((b) i=)10)
E Er, [Eapps [A))] i
E [E [k)]] Eip-ra [Eapp [w]] (k)].
where the first equality is because i- 18+1 does not affect the value of ws(is) and the remaining equalities are by law of total expectation and (88.
Now, we let w (i) denote the cost incurred batch b if one selects the controllers for batch 0, o....,b according to Algorithm 1 and the controller for batch b to be i.
22

---

Published in Transactions on Machine Learning Research (05/2025)
Lemma D.2. In Algorithm 1 for any Pb, have
Bi [w](()]
Eig Sng (i)
and for some controller 1 E Pb, we have
E R- 1:0
1J0 (wb (16))
$
no-N
E, no (2)))
2 (b(b
2
Proof. For all b ==0 0, o....... B - and for all E Po, we have
E, B- n: [w/(i)] Ess. [w)( = no LE (w((()) i6-1:00]
(a((b)
Eig 1.0l Σ pb(
(h(
MEP.
= Ei, 1.0 [uo (i)] = Eig a. 1oo (i)
where the first equality is because in-1, in-1,...., No+1 does not affect the value of (i) and the last equality is because i is does not affect the value of wi (i). Next, we can also obtain that
770 (ws(1)))2
710
(wh (i+))
1/0 (wb(in))²
Bgg 2 (b(())
Eiv.o
Ei, 1. Lo,Ei,
i 1:001:0
2
po(
2
pb pb(
(wb(6))))
Eig-1o
Σ
Too (o(
Eio-1.0
?10
(wr (16)))
(o((s)
2
P.P.
NoNN I
Eig_ 1:0 (wy (1"))2
for the controller 5h arg P, (w.² (i))2. This completes the proof.
In Algorithm define L = b be Z+ : $b+1 + $t} and let b² b'....,D bl denote the batch where Line 22 of Algorithm is satief;d;; i.e., 8/+1 # 8y for 1 111,,... 1,.... .... For convenience, we let 8 0, b141+1
and sB SB-1. 1. Also, define = (0 b S B- be 2+ sb + 0}.
Lemma D.3 (Restatement of Lemma 4.7). In Algorithem 4 suppose that (TT) and let U denote the number of times that the Break statement activated. Then, it holds that [C] = OU)) and M O(U).
Proof. For every batch b = O....,B 1, we have
| ll <
+
(19)
by Lines 11 20 If the Break statement is not activated, since we designed 8 30max it yields that
T- -(())
| |l S (TT))l==,,1 || mmmax S (as))
ou ||rll| + 3(To)5 + yumax
< (an) ||ol|| < (at) 1 + 5,
where the second and the last incqualities are due to ((T)) < ((T)) < 1 and the third inequality is by the formulation of Then, 86+1 > cannot occur when the Break statement is not activated. Also, Line [4] avoids $6+1 > 56 + 1. As a result, starting from 5g = 0, the event 8b+1 = Sb + 1 can occur at most U times. Accordingly, the event 8541 < 8h also can occur at most times, leading to [ 2U.
Now, observe the number of batches i needed to stabilize the state norm; i.e., min > 0: 8845 86) when the Brcak statement is not activated. Starting from batch and the corresponding 8s, provided that the Break statement is not activated, one write
| S B(T648- ((7646-1)1122,4 1)1 |l mmxax & ((T0)]|27)
o-, maxxx
23

---

Published in Transactions on Machine Learning Research (05/2025)
s (3(70))(1133,)
|| + maxx (3(T)) (B(T))) + - B(TT)
mWmmxx
s (3(7)) || + <
|| + d] +
(20)
where the first and third inequalities are due to not satisfying Line iteratively when the Break statement is not activated, the second and fourth inequalities are by B(7)) (T)) < 1, and the last two inequalities are by the design of 8 and 19 It is desirable to find the minimum value of that makes the right-hand side of
20) smaller than (ax) æoll + 6::
(B(T)) 50 " |
+ +8] + S
| +ô
2 a6 +
(21)
(8(T))
(ar)) |1r0l|
where the right-hand side of (1 can be upper-bounded by as + [
since Og > 1. Thus, 86 7 0,
min > :0:0844 $648 < $b} < log(os +
|
(22)
log ((To)
when the Break statement is not activated. In other words, starting from a batch b where > 0, within the number of batches on the right-hand side [22). cither the Break statement is activated or the value of sb decreases.
the Break statement activated} and B2 {0 s b < B 1,b E Z+ 8b+1 < sb). Let B = B1 U be the set ordered by batch numbers. Then, the batch interval between two consecutive batches in B is upper-bounded by (22 Thus, considering that [C| < 20, we have
More specifically, consider two sets of batches: B₁ (0 b B B- Z+
log(ar +
6
||=0l|
| S (2U 1)
log (TT)
which completes the proof.
Lemma D.4 (cumulative mix loss). In Algorithm cumulative mix loss is upper-bounded follows:
1 for any controller i' E U for 0,...,14, the
E
Σ
B-1
1
log(Ea<pp exp(-nxu((k) -
ŌU +1) + EE p
[C| 8-1111
Wbb
K (i')
7/0
110
(ars) 220h
b=0
1=0 b=
Proof. Given 1 = 0,. ...... . LI, we analyze single mix loss for b = b 1,... b1+1 as follows:
log( log(En>p, exp(- sx((-mow((kk))
log(
ps (k)) sxpp-mmw' (k)))
170
170
REP.
ΣKEP, exp( ( W/
log(
170
ΣiEP, exp( exp(-n
1
EREP, exp( - mp (1+1(1)))) Eiep, exp( 7/6 Wi())
log(
(23)
170
while a mix loss for b b/ is as follows:
1
log(En (Exmpo exp(- (k)))
1
log( Σ
Pe (k) (xp)exp(-mng my w/y (k)))
7/0
170
NEP
1
log
exp(-mawl w/ (k)))
7o0
PPol
kEP,
24

---

Published in Transactions on Machine Learning Research (05/2025)
log N
1
log( Σ
exp(-116 Tb w/y (k)))
(24)
%/
7/0
log N
1
log
exp(-116: (k))()))),
(25)
70
7/
kEP
where the last equality only holds when 6+z > b + 1. Now, notice that the batches b = bl,............ "W....,'+.. 6++ 1 share the same learning rate; i.e., Th
M since the same 8b yields the same as, and thus the same π)b. Thus, in the case where b/+1 > D + 1, we have
bi+1_1 -1 ENEP,,, exp( exp(-nx Wb()))
log N
Σ
log (Bkpp.
log(
II
110
700
77
ΣNEP, exp(-1) Wo(k))
bm 8
log(
exp(- W (k)))
kEP
log N
1
log(
Σ
exp( exp(-76: (()+((()))
(26)
7o
kEP
where the first inequality is by (23 and 255
and the second inequality comes from Pa S P Considering
both cases 24 and 26), for any controller 10
ال E Ut, one can write
B
log( (Exp exp(-mou(((k))
log N
1
log(
exp(
(-p(-166
Σ
wo((k)))
70
1/0
1/0
6=0
1=0
REP
P=
C
b Σ
(|C) + 1)
log N
log(exp(-1) (no
wg((t)))
770
1o0
1=0
b E2
ŌU + 1)
12
-++-1
(1((1))
ba
(27)
170
(arss 228g)
1=0
where the first incquality considers W (A) -0ti (k((k) in 266 the second incquality is because any
controller i' is element of Pott111 and the last equality comes from the definition of The =1/ (an)(an)))) )asy and
[ = OU)) by Lemma D.3 Finally, by Lemma D.2 taking the expectation of (27 with respect to 8g-10
completes the proof.
Now, we consider the cumulative mixability gap.
Lemma D.5 (cumulative mixability gap). In Algorithm 1 there erists set of controllers 1 Po for b O,.... B - such that the cumnlaative mixzbillly gap is upper-bounded as follows:
E Eig-1s
Σ b=0
B-1
E Exmps
[k)] + log(Ea<po exp()m,(((k))
1
O(U),
+
No B-1
Σ
B (w) (a²))²
170
2170
h=0
Proof. Given the set V, we can analyze single mixability gap for b $ and E V, respectively. Since ss for & V, given i..,,..., io, we have
Ex [wg (x)) + Eog(En exp( - m)w((())) = Exmpr [xmmp(u + log (E
770
1
< E Ba (wb,(k))
+
- (Eanps exp( exp(-moul (xp(-mow((k)) 1)
170
1
(Ex~pm (w((())))²
< Ex-pa (1b(())) +
mo 2
7o
25

---

Published in Transactions on Machine Learning Research (05/2025)
100
E ( (k))
2
1J0
(wb (wo((o))) Σ po(k)
(p)():))2 ((n=
170 (ws(is))
(28)
=
2
2 pb (i(
REP
where the first inequality uses log(z) I x - for all x E IR and the second inequality uses ex S 11- +
x + 2
for
all x E R. Now, for be E V. given 10-1...., io: we obtain that
[x [k)] + 7jo
log(En~po exp( (ow S ER [w]]))]/[[(({]]] + (IEx~ss exp(-nouc, 1)
1/0
Ex (u(())))
V/l (k))2
mow)(()) 1
Exrpaluf [b){ + (Exrps
2
170
70 Bk-pol (uc((()))))]
1
no (wo())))
(29)
21j0
2
pb (i(6))
2110
where the second inequality uses c" < for all x I 0 and the third incquality uses x² + 20 for all
a E R. Since [V] = OU) by Lemma D.3 we have inequality (29 holding at most O(U) times and 28
holding in the remaining batches among ......... B-,B-1 1. Finally, by Lemma D.2 taking expectation of 28 and 29 with respect to 8 1:0 completes the proof.
We let Ta and ue denote the state and action sequence in the algorithm depending the context. We let of (i) and ux (i) for t = la..... 16+1 1 denote the state and action sequence generated by selecting the controllers before batch b according to Algorithm ! while selecting the controller i at batch b. Accordingly, we have w (i) = Etnr ca (x (i), uf (i)). We also let of and u, denote the optimal state and action sequence generated by the best stabilizing controller i" that satisfies both of Definitions 2.3 and 2.4 i.e.,
i' = arg minses Et= (e nH (xx)) subject to the transition dynamics.
Lemma D.6. In Algorithm we have
suppose that 7. (B(Tn))² <
1 For any controller 10 E Ps for b= o,.... B-1, 2/2
B-1
B-1
E 1o (wg K (1)))² = -000= + 0
(T))
b=0
6=0
Proof. By Assumption 2.2
for all x E I and w E Rmm we have
(a(2, w)
(a u) (0. + (0, S -c(00)) (c,
s (La, (1|= + [| + [[]]| + [|ul]) + C0,max
La (||=|| + + + [+/l] + Cu,max
s 2Le, (||= + [|lll (22=| + [|u]]] + C0,max
+
(30)
where the last inequality is due to Cauchy Schwarz inequality. Thus, we can upper-bound (w (18))² for any controller it Pg for b b= O..... B- 1 as follows:
1 1
ut (())
1441-1
(wg (10))²
Σ
cx
(
Σ t=ts
ca(21 uZ (t4)) - -tb)
E=
1---1
< (16+1 - 1b)
(2hez (1 K (1-)12 + 1| ( (()))1 (1 ((*) + 11 (d²)l)) + co.
1=
1441-1
< 55(1++1 - (b)
Σ
(4T2, (112 (("))= + (1-4 ((5)))) 123 (r")) + 1| (r^))12) + - (31)
t=
where the first and the third inequalities are due to Cauchy-Schwazz Schwarz inequality.
26

---

Published in Transactions on Machine Learning Research (05/2025)
From 10p. for to < to+1 1, we have
| k (1²)1 < 2[3(1 - (6)1 1 (x))) 2- 2 || (t*)]* 8[3(t tb)l I2 (+")) 8y w
(32)
(33)
where the inequalities are by Cauchy-Schwaid inequality. Accordingly, we obtain that
|z (+))1² (46 - (1)1 (1))12 + wixx (4++1 - Lb 1)
(34)
Σ
| ((*))*
(())) + 87 8 wax (1++1 - Lb 1);
(35)
where we use 8(-) S 1 to derive Eee [B(t)] s Ei 4o ([((t) [lo++1 tb) for p 2 1.
From 12 for to S t < fo+1 - 1, we have
|| (t))1 < 1| (t"))? + 2 ||u (t")1I < | (f*) + STO, max:
(36)
(37)
where the inequalities are by Cauchy-Schwar inequality. Now, we substitute (34p.
335
36
37
and
6o+1 to S Tb into the right-hand side of 31 to upper-bound (w,, (i²))² as follows:
21 (u) (u0x((")) (1-))² 3L (2,
2 (1))
(11 w + max) + (1 2 " + 2 T.. + 2
(D)ll (1 M ( (1"]
M M (To) x0, MsT
(38)
where M3, M4, M5 are constants determined by Lei, Lez, Lmx 7s Wmax To mamax and Co.max- The last equality
comes from R (i9) It, for any 1 E Poo
Meanwhile, can upper-bound both Σe (T.) | 1 and Eioo n. (T))) by successively applying
Lemma
C.3
C.4
and C.6 in the same fashion as presented in the proof of Lemma C.7 Since {8((((T)) < 1,
by
32
and 33 there exists C1. C2 2 1 such that
B-1
B
Σ
Ty H.
11 + |, (,) (1|=0||* + Tbu H(T ))) + 8 w max
0
To (T)))
6=0
b=
R-1
B-1
rull (T.))l,) o, ([|zo] + Thu H (Tbu ))) + 27 2 max
0
roll(Tn))
b=u
Substituting the equalities into the summation of 38 for b = O...., B - 1 yields
B-1
B-1
B-1
(xx())===x(((U))))___.1 (T + 0 (T.l(())) + 0 Σ (n.)²).
Σ
(39)
6=0
6=0
Notice that taking expectation of (w (t²))2 with respect to i--10 does not affect the incquality. Finally, Thy S TB-1 and ((T,) = O(T.) completes the proof.
Lemma D.7. In Algorithm 1 for the best stabilizing controller i S, we have
B- 1441-1
(1 (i*), uK ((*)()
R-1 $ (O(U)+00 H(r)).
E Eig-10
Σ
Σ
6=0
t=
27

---

Published in Transactions on Machine Learning Research (05/2025)
Proof. Since z is generated by stabilizing controller, we have
| || - [zol + YWmax - {](0)] mamax
| || v 23()) | 2 2 max S 23(0)² + 2y²² w
2 maxx:
where the inequalities are by Cauchy-Schwarz inequality and the non-increasing property of (())- Then, by 36), we have
12
30 and
ce(di ui) - 2L, (1|=ī]| + [| + Laz (11x; + [|4]]]) + commax
s 2h, ((1 - 1 2 m,axx + Lez + LM) | + To,max) + CO, max
s 4La (1 + (00)) 2|=20|1 + Le (x) |sol| 4L.1 (1 222 2 wmax
+ Lee(1 muxx + 4L To. + To, + C0,max := M6.
(40)
In Algorithm ! one can write
Fta
(ag))=+11
roll +
S av 00011001 +
(41)
(an) mm
(as)
[(t)|
+ 7(0max
S 3(00|_== + 7amax
(42)
(ag)*t
(or))s
where the equalities hold for the last inequalities of (41) and 42 when Sb =
By Assumption 2.2 for the best stabilizing controller i" and for to S < fb+1, we have
1
ce(a K (i"), u (f*)) (x uf)l
(as)
25h
x
(Le1 (max | (i Il | max (1) 11 (122 (i*) ( x; + (1x(((1)) -2(])
(ah)22n
(Lel ((1 + La) max { ||
|l, ||] + To ma.) + Lo2) + La 1 (i*) x;ll
(ap)
x (i*)
xt
Let Tox + Lee
K (it) x
= (1 + (Lac + Lmm maxt
} +
(ox))* eb
(az) 2b
(or))
(ab)os
(i*) ) tgg
K
2t
<
(1+ Lol (1 + Lx) maxt
(cro)%
(ar))e
+ Lal (1 + Lew yumax + Los max + Leg B(t - 1b)
Ith
{(*)) sts (cx)) )00
(cr))>
L (a((1+)))3(t to)² (1
Fzi
2
< LLa(1
(as))
+ (an)
+ Lai (1 Te ) Lsca max + ba (1 (1+ Lz) (118((-t))) tt) +1)((1 Ite
+
(an)))
(ax)
Lo.11 + L3))3((t - 10) ((ab + ((0)) + +8 7Wmax)
+ (L.1 + LG )mmax max + Lo2)(1 + La Lz) (ba + ((0))||zol| + 8 w
S M73(( - 2b) + Mt - tb),
(43)
where Mr and Mg are constants determined by Lei. Lez, L,, Tom 3(0), 6, y, Wmax and max Notice that os in Line 14 of Algorithm D is upper-bounded by some constant by Lemma C.5 The second inequality is by 112), the third inequality is due to Definition 2.4 and by leveraging the same stabilizing controller 8" from to for both trajectorics 2z ((*) and æ;, the fourth incquality uses 2 (i") Ft,, and the
I) ag.
fifth inequality is by 41 and 42
By combining (40) and (3 we have
(zff ). u (i*)) C ca ut) (a
cx(x (i*), K (i*))
(x uf)
(a0)
Celat, uz)
=
(2%))
(ar))as
(ar, 220 (2%
28

---

Published in Transactions on Machine Learning Research (05/2025)
- (an)2x0 la( ((xx((()) (i"), uz (t*) - - 2;)1+ + (0p))20 -1
c( u7)
M73(1 - 1b)2+ + MgB(tt - -bb,
if = 0,
M7B(t. 16)2 + MMB(tt (b) Ma,
if 8b + 0.
Thus, one can conclude that
B 1++111
cola ce(xx(("))
(i"), (i*)
B-1
ex (x) uz)
s MolV| + Σ
(My + Mg)
1o to)
(ar))
b=0
b=0
0(U) + 0 R-1
H(Tr)).
(44)
6=0
where the first inequality uses (3-) < 1 to derive E
1011-110 13(L - 14)] < Σ 1-11- 1 13(1-1))) = H(6+1 1b)
to
and the last equality uses to+1 - to S 76 and Lemma D.3 Taking expectation of (44) with respect to 8-01-0 completes the proof.
Theorem D.8 (Restatement Theorem 4.5 Regret Bound). In Algorithm 1 suppose that to Then, the regret bound is as follows:
(B(To)) < 2V2
T
Eig 1.0
Σle
IcolFen un) - co(xi,u1)) u7)]
t=0
Ó(K4] +1)
No
= O((U) + 0 (())))
0 1 (T.)
1/0
2
b=U
b=0
Proof. By Lemma
D.1
we have
B-1 1o+1-1
B [wb((e)]
Big-10
(x We) = Rig-no
(x Uz) Fig-10
t=
B-1 1
= Eig- 1.0
Ek [k])
b=0
Ó + 1)
+
Nn
B-1
E
E0 (w (w<(()) (1a))2 + Eig-1.0
[C] B 1-11_1
Wh
(i*)
f1o
2
(arb) 20h
b=0
1=0
b=
Ó + 1)
N
+
(Tp(0( + 0
(T)
170
b=0
B-1 Σ H(TT)) + Eig 1:0
+ +OU)) + 0
Σ c u²),
b=0
where the first inequality is due Lemma D.4 and D.5 and the last incquality due Lemma D.6 and
D.7 Using U < [24] completes the proof.
Theorem D.9 (Restatement of Theorem 4.6 Regret bound with known [4]. In Algorithm
4 let π.
(wb+z) 1/2 for every b 2 0 with the constants z, v > 0 that satisfies To > 0 and (B(TT)) 2 Also, let
(1)
nu = O (11++1)2/8 When T 2 max 1)) N(U + 1)}, we have 1//3/2
T Σ t=
E. 1.
[er(ar, uz) ca(at, wz)] = 0 N 2/ ([U) + 1)1/3)) + +o(1) (()))))((())) + +
29

---

Published in Transactions on Machine Learning Research (05/2025)
which implies that we achieve sublinear regret bound. Moreouer, when H(t) & O !)) for all t 1,
have
E
Llc((e un) calot, =
+ 1)
t=0
Proof. By the formulation of (to)b20, we have
(vb 2)1/2
B-1
B-1
(vb + 2)1/2 (N(( + 1))1/2 + 1),
Σ T6
T T
(N(H 1))
where we can further use non-decreasing property of (-)2/2 to arrive at
2/2 2 [v(( 1) + 22)3/2 23/2]
- -1 2/22 1 (vb + 2)
3u (N((U) + 1))1/2
(N(( + 1))1/2 - 5T
Le (vb 2)1/2ab
(N((U) 11))1/2 + -1 3y [uB + 2)332 33/2
+ +BB-1 11--1 1),
(45)
(N(U 1))
thus we have B 01/ 1)1/3) from the first incquality and T 0(B3/2 + 1)--1/2
from the second inequality and 2 N(U) 1). Similarly, we can find the order of ΣB (Th) as follows:
B Σ mm))
B-1
(ub + 2)2/2
- % [N(( + + (N(( + 11)11/2 + db
p (vb+2) + +) + 2(ub + =)1/2
(N(()) + 1))1/2
b=0
6=0
B²
=0 N(U + 1) O(T4/)0 (13((11 + 1)
(46)
where the last equality is by B 0 - 1)2/2). We also have
TB-1 (u(B - ","
1)-1/3).
(47)
N([[+1]
Thus, we have
=o(1)
o(1)
O(TB-IH((BB-I) ((((B_1))) - 2/3 2/3 3(2( + 1) 2/33
(48)
No
3/2
where the first equality due to Lemma C.1
With T
(1((4))) we have
No
(49)
0(14)) = 1/T3/3 + 1)333)
(50)
With 446
48
449
and 50 we can apply Theorem D.8 to derive
B-1 (a, u.) - ca(at, uf)] = O 0 + 1)1/3) + +x()))))((O()))) + 0 t
T
Ein-1o 1.0
Σ H(T))).
6=0
Applying
17 to 0 H(T))) achieves a sublinear regret bound.
Morcover, when lim (t) < 00, there exists constant 91 that upper-bounds H(t): ie.. H(t) S 91 for all
2 0. Then, we have
B = 0(B) = 1)1/3).
(51)
30

---

Published in Transactions on Machine Learning Research (05/2025)
Also,
48
and
49
can be modified to
TB
No =
+ -
(52)
Similarly, when (t) = -(E for all t 2 1, we have
B-1
Σ
((m))
BH -((loo-a))(( - - + +1)11,,
(53)
No
+ 1)113)) exp()((()))
(54)
Using 51,,
9
53 and
54
completes the proof.
Small modification provides the regret bound for the intermediate step "Dynamic Batching" mentioned
Appendix A
Corollary D.10. Consider "Dynamic Batching" strategy without adaptive learning rate, i.e. Sb 0 for all
= 0,..., B 1 in Algorithm 1 Let To...., TB-1 and noo be the same quantity with Theorem D.9 When
T 2 max [NTR +1JJTZ, N[ + 1)}, the term o(1) exp(O((41) in the regret bound of Theorem D.9 is replaced
R//0/2
by (T /3) exp(O((4)))
Proof. Since 8; = 0 for all b, we need to modify Lemma
D.7 Equation
43 is modified to
|e(2, (1*), (i*)) e (xt, ut)l ( S Tea (1 + I. 3(1 - 4,) ((1rr,) | + || II) + Laa (1 + T 1
+ Le mo,aa L1e [,) (0) ll + | II):
which incurs
A4-1-
Σ
(e, (1*), |/ |000:/00000000000000000000000100
Thus, it follows that
B-1 1441-1
le<x (it) (0) c,(,, uz) exp(0 + ||0ll)) + +exp(O(u())((T==-)))
0=
1=4
=ex)(O((4)) - /37
where the last equality is by the choice of TB-1 = (( (T1133 that o(1) (x)()((())) in Theorem D.9 should be replaced by o(T2/3) exp(O((())) in the algorithm without adaptive learning rate.
=((13) and applying Lemma 4.3 This shows
E Regret Proof for Algorithm 2
Theorem E.1 (Restalement of Theorem 4.10 Regret bound with unknown [4]. In Algoritlom g let
TU (1bt=))1/2 for every 2 0 with the constants 2, v > that satisfies To > and 7 (B(TT))2 2 Also,
1//3/22
lel 110 0( (77//3)))) and y 2. When T 2 max 117271 N}, we have
Eig (ler(ar, ca(xt;u0)) O + 1)) + o(1) (x)( + 1)1/2 + o(T),
which implies that we achieve a sublinear regret bound. Moreover, when H(t) < O !) for all t 2 1, we have
T
Eig 1.0
[el wx) - ce(2t, wf)l = O (00=01=)))00( + 1)1/2
31

---

Published in Transactions on Machine Learning Research (05/2025)
Proof. By the formulation of (To)o2u, in 45
can derive
= 0 and T = 0113
when 2 N. We can also obtain
B-1
(n.)2 0(14/3N-1/3) and ((TB-)(((TB-i)) (212//N-213)
Now, define no == no(r + 1) vor Let B, denote the set of batches where N4 = r; c. B = (0 b B - E 2+ : 14b = =r. Then, one can write
similar to 46
and 48
U
No U
no. Bis n. (w) K (2h))² v Σ
VU+ + IE (w6 (i'))
2
r=0 B
r=0 DEB
B
VU +N
Σ (m))
b=0
S +1 (o1))ex(())))(( 0(T2))
(55)
where the first equality holds by Lemma D.6 and the second incquality holds by U $ [4]-
Recall the definition and the cardinality of L (0 < b S B - 1, b Z, 86+1 # 86} and v = (0 S b <
B-1, b E 24 : 96 + 0} in Lemma D.3 We focus on the mix loss and the mixability gap with the denominator + (og(EE<p exp(-1ows((k) (k))). Considering
10ori i.e., 17.r log (Ex-p exp(-mm (k))) and Ex=py (k)] [x
that Ro.r
my still remains to be (mr)) as in Algorithm Lemma D.4 can be modified to
[C| 8--111 Σ
p log N
K (it)
E
Σ r=
Σ B
log(Ex<p, exp(- (k)))
Eig
Wh
(56)
1/0rr
mo.
(ap) 2 %
b=
where P. denotes the number of batches in B, O L. Similarly, considering that no.r now depends on the value of r, Lemma D.5 can be modified to
U
Eig 1:0
Ex- Ex-polug +
log (Ex(En exp( (xp(-mo(((k))
100rr
#=
O B.
U
N U
p
Σ
no To
2.0 (
(57)
21Jo.r
r=0
r= beB,
Now, our goal is to upper-bound Σ d oo.-
where of denotes the number of batches in B, V.
To Dtn el Nog in (56) and Dt oi Vr+I
ou in 57 It is straightforward to infer that
No. To 0
Pb + 1 .... + pb S 20 + 1 by Lemma D.3 and 277). which also leads to pa + p1 .... P/. < 2r +
+ Pt S (2U 1)1 log
for 0,...,C U. Similarly, we can infer that P and of + log
by for r I....,U. Define
log ((ro)
Lemma D.3 and 29 which also leads to pf + ....4 + P. s (2r 1) log, ((70)
U.
Mg = log(as Tep ((ro)
and consider the following maximization problems to get the upper bound.
U
1" max Po
Σ
0" max p P.....
-
s.t.
ph <
s.t.
p < Mg
pb + p 33
pf + 03 S 3Mg
t + p) +... pb < 20 +1,
pi + P3 + ...
ph S (2U 1)Mg.
32

---

Published in Transactions on Machine Learning Research (05/2025)
We can easily achieve optimal point of each linear programming (LP) problem by the well-known Karush-Kuhn- Kuhk--ukeer (KKT) conditions. There exist positive constants λo,-.. AU, -i,.... such that
[1
Ae
(58)
v2
VU
Ky
Kr
kyl.
(59)
V2
v3
VU
+1
which yields Ay = No = VU4T' =
- for r= I...., U- 1, and Ag = 1 Since
/2
every dual variable is positive, complementary slacknoss tells that there is no slack for every incquality at the optimal solution. Thus, the optimal solutions are
P 1,
U. U. pi Mg: P = 2Mg. r :...,,,;
=2 T=
where the corresponding optimal objective values are
U
2
V2+ { vr+I
+
S
dr Vr O
+r+1
r=1
M
U
2Mg
Mg +
2Mg
U 1 0
V3 2 Vr+I -
+ 2Mg
P=
where we leverage the non-increasing property of VrII for the inequalities. Thus, we have both
e log O + 1)1/2) and D Jr4 0(12/8 + 1)2/3). Combining 55 To and with Lemma D.7 and S [211, one can write
E Bgg-10 100
[a((,, u4) - cx(xx u4)l
B-1
=0/T3/3 + 1)2/2) + o(1) (x)((( + 1)1/2 -((U)) + 0
Σ
H(m))
6=0
B-1
1/ + 1)) o(1) (x) 1) 0
Σ
H(T)))
3/2
where the second equality holds when 2
Using
17
shows a sublinear regret bound. When
H(t) < 5O }) for all / 2 1, 51 and 52 are modified to
B-1 Σ s (BB(((t-))) -
TB 0 O(T N-13)/
N (0)(0(44)))(rr -(( (0 ex)())
Applying this equality re-derive
(55
completes the proof.
F Applications: Switched systems
So far, have used the best stabilizing controller i S for all time steps = O,.... T as the baseline of regret. However, the proofs of the theorems stated above imply even any set of controllers
33

---

Published in Transactions on Machine Learning Research (05/2025)
169,21 .....} S S as a baseline, where the controller is switched from i' to g++1 whenever the cumulative weight (-) resets. This motivates the application of our DBAR algorithm to scenarios such as the switched systems (Tousi et al. 2008 Zhao et al. 2022) for which the transition dynamics and the associated controller pool may undergo changes, as well as the ballooning problem (Ghalme et al. 2021 where the controller pool may expand up to some finile set. We propose Algorithm 3 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 > is additionally incurred when the controller is switched; i.e., d Ei=I 1) done in Altschuler & Talwar (2018) and Arora et al. (2019).
For an event A, I(A) denotes an indicator function, where I(a) = 1 if an event A occurs and I[)) = 0 otherwise. Pr(A) denotes the probability of an event A. Let x', and un denote the state and action sequence generated by our set of best stabilizing controllers (6..... 1/c } _ S. We consider a regret with switching cost where the unit switching cost is d 2 1; i.C., Eig Rig-10 EE ( mx) ca(a"e u4)] + dd EE I(ibtto-)) d E [
A Algorithm 3 can easily be generalized to the situation where we have O(U) number of system switches controller pool switches. In fact, we can simply add (41+1>-.... (att4>>---MM440000 (c)+ 8 to the set of best stabilizing controllers (% // S where [4] = O(U) by Lemma D.3 Thus, it suffices to derive the regret bound
of Algorithm 3 even in the context of general switched systems or ballooning problem. We first provide a useful lemma to construct regret bound.
A Algorithm 3 DBAR-switching
// Modification: Use this IF-ELSE Statement to select the current policy in Line 2
Algorithm
if b> O and 86 = 86-1 and Ps = Pa-1 then exp(-maWs(6-)) (16-)))) Pick is = is-1 with probability exp(-% 1W, 1666 2)) Sample is from distribution ps with exp(- 7/ Wn(in-1))
probability 1
expl- 16-1(1s-1)
else
Sample i from a distribution pa- Terminate the algorithm if Ps is empty.
end if
Lemma F.1. In Algorithm 3 let nh (((()1))) )
)12 for every b 2 0 with the constants 2, > 0 that satisfies When T (0())==((((()))))2 (N((1)1)))
To > 0 and to (B(TT))) < 2/2"
we have
E Ein-10
Iintto = + O(NNT).
Proof. For all b b...... B
1 such that 86 = 8b-1; given ib-1,..., to, we have
exp( 7/6 ((b-1)))
exp( - 7/6 Wo (bb-1))
Pr(is * i S
$1 1
exp(- - 7-- 6/ا1 (io-1)
exp(-mo-11 W W-1 (
=1 =1-exp( 17- w// (io-1) $ exp(-now'_ (io-1))
S nowb = 170 Wh- (i)11
(60)
pb- (ib-1)
where the second inequality is because Th Th- when sb 8b-1, the third inequality uses no 2 ?bb for all
b 0, and the last inequality uses 1 + x e" for all x R. Now, given a set of controllers 1 E Pe for
b 0, B- 1, we can upper-bound === (i') by lb+1 ls S as follows:
B-2
B-2
B 8-26m-1-3
B-2 2-41-111 -1
wb((")) (+7) = Σ Σ
c(T,, u. <
Σ
2Lg (1|xe|2+ + 1lua
+ [ezeel + [luell) + Co,max
0=0
0=0 t=
0=0
t=
R-2 24-1-1
< Σ
Σ
2Lg ((1 + +22222))
+ 2 2m
+ Le2((1 + I.) + To,uuxx) + CD,max
6=0
t=
34

---

Published in Transactions on Machine Learning Research (05/2025)
B S 2 (1 + (1) + L1 + H.)))
+
7o(4 00. oo + C0,ax
b=0
B-2 ((T))) + 0 2 mb),
0(exp((( + 0
(61)
6=0
6=0
where the first incquality is due to due to using 8(-) S 1 to derive Σ f
130
the second incquality is by 12 and 36 the third inoquality is
[3(t]]² I Σi=o -6 [B(t) = H (fo+1 - tb and the last equality can be
0
With T2 (a())esp(O( )))a/2
derived in the same fashion with 339
we obtain by 470 that
(N(M+1))1/2
B-2
B-2
((e)p(O(ZI))((mm))
0 Σ
H(m)) + +
Σ bm0
Tb) S O(T).
(62)
bm0
Thus, one can write
Big
I 11 Σ Bino 11
Σ
B 11 Fij (to i6-100)
b=1
B-1
Σ Bio-ro 1:0 Pr(is + ib-1 i0-1:0)
B
Σ
Eig 1:0
[Pr(sp = =sb-1, - 1r0)) * i--1 sb = sb 11-1,16-1:0)
b=1
+ Pr(sb F 8b-1 or Po + Po-1 is 16-1:0) Pr + i St + Sb-1
Pb # Po-1, is 1
B
= =
Ei, [Pr(s) 11 Pb = Po-1
i Pr(is + 4-- Sb-1. Po = Po- 2 1:0)
b=1
B-1
+ +
E. 1.0 Pr(is # is-1 = 8b-1, = 20-1,10-1:0)
6=1
(ib-1)
+
Σ
F 2/0
pb- (ib-1)
Wh 1b-1(10-1)
= +U++U++
Exp-20 2:0 Emp
770
Pb- (ib-1)
2002:0
B-1
Wh W3-1 ((0-1)
= +C++U++ +
Pb-1
Pb-1
6=1
IEP
B-1
+ +
NE
Wh ((
(63)
6m1
for the controller 1h1 arg maxieP__, (b)) The first equality is because in-1.... i641 does not affect
on Iiisi 1) and the second inequality is by 600. Taking expectation of 61 with respect to i and applying it to (3) yields
B-1
E Bip-10
Iun 1) = |C] + U + O(nNT)
by 62 Using [C| = OUU) Lemma
D.3 and U < [ completes the proof.
1 if or 8, + 86- or Ps + Pa-1- It turns out that even if S 56-1 and P3- Po-11 the distribution of policy from Algorithm and 3 are indeed the same, which is motivated by Anava et al. (2015). For the sake of completeness, state the lemma in this paper.
Agorith uses the same distribution with Algorithm
35

---

Published in Transactions on Machine Learning Research (05/2025)
Lemma F.2. Let ps and po denote the distribution of policy at batch b O,..., B --1 resulting from Algorithm and respeclineky. Then, and are the some distribution.
Proof. For b = 0, (k) = Po(k) 1 for all k E Po. For all b = l..... B - such that o 8b-1 or Po * Po-1. it holds that Pb = Pb- Thus, it suffices to prove the induction step for = 1,... B such that 86 = Sb-1 and Pb- = Po-1. Define Y, = EkEP, exp( (k)) and suppose that pb-1 = pb-1- Thus, we have
N
(xp(->)W6(kk))
exp( 176 Wo(1)
(k) p
1/6 exp( 11101 1 pb())
Σ
(1
exp( 7/ W ())) -1)-
iEPs
exp( 7/6 (xp(-n%,Wa (k:))
exp( 76 Wi(1)
= Pb-1(1))
exp( 77- W6 1 (k)))
(1
W (i-1 ) 11)
exp( 1
iEPs
exp( - 1/-
exp( 77 (k:)))
Y6-1
exp( 1/6- Wo (k-)(k))
exp(
1/b (k:)))
exp( 1xp(--mWh(0)
exp( - 7/6 W 1
Yo
exp( 776 Wo)
Yo-1
REPb
exp( 776 (k)))
exp( (xp(-moWo(kk)
exp( 1-p(--1--10 7pb-1 W (i)) 1xpp(-16oWa
Yb-1
Y,
Y--1
iEP
exp( Th (b))) +
1ep(-noW6(k
Yo-1 Yo
exp(-TnWo(ke Yo- pc()),
Yo-1
Y.
Y
Yo Yo-1
where the first equality due to the law of total probability, the second equality is due to the induction
hypothesis, and the fifth equality is by Pa Po-1- Notice that ss = 8b-1 yields n7 77-1 and Wk(k) 2 exp(=m.W.(k))
(k),,),, and thus 0 V exp(-7%-1 Wa- S 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 [2]) In Algorithm for every b 2 0 with the constants 2, > that satisfies 0 and Ti (3(TT))² (14+1))28 0 (27881/5av7)
let T. =( (NilU) +1)
(ub+t) 1122
2V2 Also, let nj
To
(o())app((((()))) Rapraa ) When T 2 max( (N(R((1)) [1] N(R2 + 1)d), we have
T
B-1
[4|
Eig 1.
[el(Er, uz) celx'' u/)l + +dd Σ Σ t=
[((
b=1
1=1 = /0
1)333 + o(T),
which implies that we achieve a sublinear regret bound. Moreover, when lim (t)) < oo and T > 3//3
maxf exp(Onu))
(1) N(U + 1)d}, we have
d313
B-1
[2 d I [
E, Ein-10
Σ [l((z.)))) u.) ca u4)1 + d
Σ I Iishi b=1
1/333/133)
Proof. The distribution of policy is the same for Algorithm D.8 with Lemma F.1 to achieve
D and by Lemma
F.2
Thus, we use Theorem
B-1
14
Eiz-1o
E
(ar, ue) - (2/, u4)1 + d
I Tiott 1) - d
I ((
1=
1=1
1=1
Ó( 1)
NooN
(exp(0(41)00(7=
+0( [T)
7/0
2
B-1
+ 0
+(du)) + Odd,NT),
(64)
0=
36

---

Published in Transactions on Machine Learning Research (05/2025)
since d 2 and Σ I O. Notice that (ro)22 is the same for Algorithm and Accordingly,
still have B = (1 [ 1) by 45 and T 2 N(U + 1)d N(U) 1). We also still have 46
and T 1/ [I we obtain that and 47 Thus, with T (o(1))zp((( (M
(N(1)+))))
NuNNepp (..eepp(((41)000t>_ttttt--)) o 1/3) exp(O((u))) - +1)
O(diu)) 20T2///2/// + 1)138
Also, with T N(U + 1)d, have
O(droNT) O // + 1113)
Combining all the above equalities with 64), one can write
T
B-1
|2]
Bin
Σ Tel un) ce ca u4)) +
I Tish i 1)
I p 1
b=1
1=1
B-1
O(T2/33N111 ( + / + 0 Σ H(n)))
b=0
Using
17
shows a sublinear regret bound. When lim H(t x0; 52
modified to
No (eppO 0 (1 + 1/133/1/3)
only with T
(XP(O
This completes the proof.
G Numerical Experiment Details
In the two following subsections, we will present experiment details on linear and nonlinear systems, respectively. Since Algorithm ! only hinges the system state norm context, 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 Algorithm T The second factor the randomness of adversarial disturbances stated 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.
avoid computational burden;
G.1 Experiments for the Linear system
In this subsection, we introduce the implementation details and present more experiments on the linear The random matrices A", B" I 10 generated by seed 42
system discussed Example of Section 5
is follows:
0.250
0.901
0.463
0.197
-0.687
0.688
- -0.833
0.732
0.202
0.416
0.958
0.939
0.664
-0.55
-0.636
0.633
-0.391
0.049
-0.136
-0.417
0.223
0..21
-0.415
0.267
-0.087
0.570
0.600
0.028
0.184
-09077
0.215
0.658
-0.869
0.897
0.931
0.616
0.390
-0.804
0.368
-0.199
00.75
0.009
-0.931
0.818
-0.482
0.325
0.376
0.040
0.093
-06330
A'
0.939
0.550
0.878
0.789
0.195
0.843
0.823
0.608
-0.909
-0.49
- -0.222
0.457
0.657
-0.286
-0.438
0.085
00.718
0.604
-08550
0.973
0.544
0.602
-..88
0.630
0.413
0.458
0.542
-0.851
-02883
-0.768
0.726
0.246
0.338
-0.872
0..78
0.349
0.459
0.275
0.774
-0.055
-0.760
0.426
0.521
0.122
0.541
0.012
0.045
-0.144
0.949
-0.884
37

---

Published in Transactions on Machine Learning Research (05/2025)
0.937
0.272
-0.371
0.017
0.815
-0.501
-0.179
0,511
-0.542
-0.846
0.420
-0.677
0.859
0.616
0.266
0.742
0.607
-0.626
0.785
0.078
0.614
0.792
-0.363
-0.779
-0.544
-0.145
0.636
0.721
-0.986
0.021
0.165
0..55
-0.760
0.324
0.885
-0.353
0.037
0.406
-0.272
0.943
0.924
-0496
-0.005
0.398
-0.430
-.922
0.219
0.005
-0.897
-0.442
B
0.816
0..20
-0.710
0.021
0.971
-0.515
0.344
0.523
-0.524
0.456
0.264
0.264
0.267
0.071
-0819
0.670
-0.588
-0.626
0..188
0.181
0.355
0.966
0.024
-0.577
0.290
-0.651
0.381
-0.226
0.873
-0.724
0.317
0.773
0.849
0.754
00.84
0.319
0.634
0.110
0.059
-0.516
-0.83
0.794
0.800
0.266
0..21
-0301
0.451
0.794
0.774
0.559
The generated K"
which renders the absolute values of all eigenvalues of A B* less than 0.8
- 400.488
12.262
-39.333
-4.008
-8.199
20.9771
16.954
17.300
61.898
4.465
31.536
- -10.692
27.743
3.956
6.884
15.973
-12.235
- 113.553
-4.8662
3.885
142.210
43.435
-137.480
-17.793
2889937
-73.009
61.443
60.575
218.313
11.5883
93.148
-30.162
88.110
11.829
19.573
48.086
39.6686
-40.256
141.263
10.178
-64.436
18.536
63.263
-8.220
-12.714
-328899
28.580
27.373
98.987
-7.165
K*
-67.582
21.285
63.397
-7.021
-13.663
-33.861
27.655
28.119
100.042
-8.308
101.088
32.099
95.308
12.523
21.119
51.371
-41.999
-42.555
112.2449
12.494
- -94.335
29.944
-7.5337
100944
-99.780
-47.585
38.049
39.530
139.826
-00.609
20.847
-6.058
20.699
2.767
3.727
10.752
100.122
-8.425
332.410
2.621
6.452
-1.20
5.426
0.085
0.618
2.488
-2.833
2.061
-8.201
1.019
We construct a controller pool by selecting each entry from K and multiplying it by 1.1. Among 101 controllers including K 43 controllers are stabilizing controllers, and the others are destabilizing controllers. We consider three different noises for the experiments. To perform fair comparison, the bounding constant. Wmax is set to 1.
(a) Sanity check: Gaussian noise with mean 0.3 and standard deviation 0.1, truncated to/-0.4,
sin 1
)
(b) Sinusoidal noise wi = sin
& 1s
11x
2
10
(c) Uniform random walk, where wio = Uniform
+
37
3
3T
2 2 10
and wi w follows Uniform
37
3T
where T is time horizon. One can easily see that for uniform random walk, |wr| S 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 [ which means that we consider four scenarios: (fixed, dynamic) batch length and (fixed, adaptive) learning rate. For the experiments implementing the algorithm, we use T 1200, 7/o 0.025, 7 = 2.5, ag 1.01, and 2g = [100, 200] < 15. For the dynamic batch length, we consider TO and π, Too 1 It is well known that every (asymptotically) stabilizing controller in the linear system is indeed exponentially stabilizing controller (Khalil 2015). Hence, relaxing the assumptions stabilizing controllers. Finally, use ò TWmaa
3(t) 0.99* without I-B(To) Since the sinusoidal noise
case is already presented in Figure 2
we only present truncated Gaussian noise and uniform random
walk case here.
In Figures 2 D and we observe that each component of DBAR, a dynamic batch length and an adaptive learning rate, joinlly 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 (sce Figures 7(a) and 7(b).. However, when applied together with an adaptive learning rate, a potential multiplicative exponential term mitigated (see Remark (.8) and the
state thus stabilized. This can be observed in Figures 2(d) 6(d) and 7(d) when comparing fixed
38

---

Published in Transactions on Machine Learning Research (05/2025)
Goad v, iand Bled
Exad v. Eind
droende Bord q
Beed odagtic y
dyeanec v. baod
drsaine v, anlapiive y (DBAR) VWtwer
dysanes adaeptoe y (DEAR)
alaeeoe
Exsd adaptin y
Rpuaniic cnlaphion
Opeance alaptiong (DRAR)
100
6:25
103
120tr
11007
(a) Stability analysis
(b) Regret analysis
Adaptive learning rate under (d) Dynamic batch length under dynamic batch length
(c)
adaptive learning rate
Figure 6: The stability and the regret the linear system under truncated Gaussian noise. Ablation study of the algorithm is presented.
300
Eanil v, Gioa Bood
Land Laad Fuslly Eand adaptiin coneek sdigthe y (DUAL)
desenic Bad o dysasiie elggtiie (DAR) Tieear
Food it edaption
dynnnie maleptooe (DEAR)
1.3
adupticn
dysmuie alppiin 9
Jul 2011 Fal.
8:0
Liaa 3
(a) Stability analysis
(b) Regret analysis
(c)
Adaptive learning rate under (d) Dynamic batch length under dynamic batch length
adaptive learning rate
Figure 7: The stability and the regret in the lincar system under Uniform random walk. Ablation study of the algorithun is presented.
and dynamic batch lengths under an adaptive learning rate. This results from using a non-dccreasing batch length where the increasing ratio between two consecutive batch lengths is determined to converge to (see Assumption 3.1. 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 [(c) [[c] and [[c] 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 mamax and minimizes the regret, where the two components support each other.
G.2 Experiments for the Nonlinear system
In this subsection, we introduce the implementation details and present more experiments on the nonlincar ball-beam system introduced in Example 2 of Section 5 To study this continuous-time nonlinear system, we first derive the first-order state representation of the leader system (7) with the states (y1, 32, y3. y4)
(a, B8, -9) E Rd and the action -9.81Bu.
ys
VIVA B(9.81)2
s y2. d/2 9.81B sin
(
+ 3w.
V = y4. Va 8,
where Wy is a sinusoidal noise sin( (+) and Wmax 1. A nested saturating control policy is known to successfully stabilize the leader ball-beam system if the correct parameters are given, but it does not nccessarily exponentially stabilize the system (Barbu et al.] 1997]. 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 o'
39

---

Published in Transactions on Machine Learning Research (05/2025)
determined by three positive parameters (p, k1, R2):
P1 = p. P2 p
p
p
6
v yी 12
P3 =
e²
P1 e3
21 y1 + k13/2 + k1y3 3/4
22 = 122 + k2ys + 4/,
23 = y3 + 1/1
24 = 94
r' or (24 pps (23 + pp. (22 + pp. (21)))),
where 0p(2) is the saturating function defined as p if 2 p: -p if P. and 2 if |2| S p. We consider the controller pool
V' = = :p (2, 30, 44, 58, 72, 86, 100), A E 3, 5,5,
22 E (1, 1.5, 2, 3, 5,5,,
which has a total of 800 controllers. Morcover, the follower systems are formulated by generating A, as random matrices, where each entry is independently sampled from Unif(0, 1]. For the action u, of the follower systems, we consider linear policy in Example 1. Then, the action is parameterized by ut K2z, where K2 E 196x96 We let K₂ be multiple of identity matrix, and the diagonal entry is selected from the pool (-45, -4..5, -50,- -2..5 -5,, -60,- -70,- -00 -90, - -100}. Thus, considering the actions of both leader and followers, the controller pool contains 8000 controllers. Among them, we do not know if each controller stabilizes the system.
For simplicity, we perform forward-Euide Euler discretization on the system with a sampling time 0.01. The resulting discrete-time states and actions are denoted by [y', 2²] and [uy. vf] at 9th sampling time. We use the cost function ea cy 2", oy ) lly" 2 || + || + ||u]]]2 to stabilize the ball position and the beam angle towards O. We again perform the ablation study of Algorithm [ For the experiments implementing the algorithm, we use 7 = 5000, 7/0 0.25, a. = 1.01, 30 = 1- 32, 24, 5.6, 24], and 20 = [10, 10.... J E 1296 For the dynamic batch length, we consider TO = 9 and T = [ ( )0.51
Unlike the choice of ((() in Section G.1 we select the stabilizing controller only to satisfy (asymptotic) ISS in Definition 2.3 instead of exponential ISS. To deeply study this notion, we consider different polynomially decreasing series (which not exponentially decreasing) to be the candidates for 3()):
10 11.05 x1.0511. }
B2(() min 10 11.08 }
(1(1) min
and A(c) show the stability and regret analysis of the system under 3(t) and 3()). In our experiment, there are 3400 controllers out 8000 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 5600 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, Figures 3(b) and 3(c) illustrate that dynamic batch length by itself still suffers from multiplicative exponential term regarding series of destabilizing controllers. However, for both }3 (t) and (2),), even though (t) and O !) are close, one can observe from Figures 3(b) 3(c) (() and [(c) (hat the combination of the two components of DBAR
Figures 3(b)
3 4(b)
effectively resolves this malignant term and the resulting closed-loop system enjoys both asymptotic system stability and the improved regret (sec Table 1
40


Reviews:
[{"review_id": "5C0Am3np9d", "reviewer": "Reviewer_Wv4b", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths** \n+ The paper is very well written and treats an interesting problem, namely that of nonlinear online control with bandit feedback. \n+ The theory seems to be correct and the work is complemented with experiments which is appreciated.  \n+ The algorithms relies of well known ideas in the online learning community, like exponential weighting and batching but the combination of these ideas yield an interesting algorithm, especially the adaptive batching idea although this part may benefit from a better exposition.  \n**Weaknesses** \n- The idea of using EXP3 is very natural and expected for this type of problem. In other words there are no surprises here. The challanges that come from using EXP3 here are not very clear.  \n- The assumption that the pool of controllers is finite (see Assumption 2.5) simplifies the problem dramatically in contrast with prior work even if they assume access Stabilizing controller. Indeed, note that not having a finite pool of controllers yields a different notion of regret than the one considered by these authors, in particular a harder regret benchmark. Moreover the issue of having access to stabilizing controller was addressed by Chen and Hazan without the requirement of having a finite pool of controllers.  Therefore, I am not sure how is your method comparable to that of Chen and Hazan?   \n - Robust control is typically concerned with settings where the disturbances may not be bounded. The current work is limited to the case where the disturbances are bounded. I find this a big limitation at least for applications in control.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider an online control problem with nonlinear dynamics subject to adversarial disturbances, with bandit feedback. More specifically, they assume that they have access to a finite set of controllers that may not be all stabilizing but at least one is. They study the regret minimization task and propose DARP an algorithm that guarantees a regret of order $O(T^{3/2}) + o(1) \\exp(O(\\vert U\\vert))$. The algorithm proceeds by narrowing down the set of stabilizing controllers by checking  wither they verify certain stability criteria, then combines that with an exponentially weighted algorithm to adaptively find the best controller.  The authors further complement their findings with numerical experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like the authors to address some points I highlighted in the weaknesses. Moreover, here few more questions: \n+ How strong is the Lipchitzness assumption of the function $f$? \n+ How challenging really is the assumption that you have bounded adversarial noise? \n+ Exponential weighting algorithm is a well known algorithm in online learning, and this work seems to directly apply this algorithm. What novel insight or challenges did you face in using this algorithm for this particular application? I am not convinced by their claim that they develop a novel Exp3-type algorithm.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6PbLlIbWb0", "reviewer": "Reviewer_WJWD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The algorithm is novel due to its removal of a commonplace assumption in the literature, but it is unclear what kind of practical improvement this result offers. \n\nTypically, most systems already have an exponentially stabilizing controller so it is unclear how much improvement is offered by those systems. In this thread, the lower bound discussed by the authors is only for the exponentially stabilizing case, so it is unclear how much more restrictive the lower bound in this (more challenging) regime is. For instance, I'm also curious what is the computational complexity of the control process (in terms of the batch rate).\n\nMoreover, it is not obvious that (with the additional assumptions) the asymptotic stabilizer does not immediately imply the existence of an exponential stabilizer. Also, if the batch length increases, can it not increase unboundedly?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In the control theory literature, an exponentially stabilizing controller is required to exist in the candidate pool to guarantee closed-loop asymptotic stability. This paper relaxes this assumption to only require an asymptotically stabilizing controller, to achieve regret bounds that are competitive with existing bounds in the literature of $O(T^{2/3}) + o(1) + \\exp(O(|U|))$. The paper achieves this by using a dynamic batch length (instead of the adaptive learning rate framework in most of the literature). \n\nTheir algorithm (DBAR) essentially slows down the batch rate when experiencing a destabilizing controller, and increases the batch rate when learning to \"trust\" a stabilizing controller: this framework is reflective of adaptive control (from Li et. al., which the authors reference). The authors also provide a simplistic linear example and a follow-the-leader nonlinear example with numerical experiments to support their theoretical results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Would appreciate an answer to questions posed in the previous section.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "30bPgmmBEL", "reviewer": "Reviewer_EsbM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n• The relaxation from exponential to asymptotic stability broadens the applicability of the approach. \n\n• The integration of dynamic batching with adaptive learning rates is novel. Dynamic batching allows the system to “wait” longer when stability is not yet observable, while the adaptive rate helps mitigate the exponential penalty from destabilizing controllers.\n\n• The theoretical analysis is comprehensive, with detailed proofs provided in the appendices.\n\n• The experimental section demonstrates promising performance on both linear and nonlinear systems.\n\nPotential Weaknesses \n\nScalability to High-Dimensional Systems:\n\n  – The algorithm’s complexity might increase significantly as the state or controller dimensions grow. High-dimensional systems could exacerbate issues like the exponential dependency in regret and make the dynamic batching mechanism less effective.\n\n  – It is not well discussed how the approach scales, both in terms of computation and performance, when applied to large-scale systems.\n\nComputational Overhead and Real-Time Applicability:\n\n  – The frequent weight updates, adaptive learning rate computations, and dynamic batching could introduce non-negligible computational overhead.\n\n  – For systems requiring real-time control, it is important to assess whether DBAR can run fast enough while still providing stability guarantees.\n\nLimited Discussion on Hyperparameter Robustness:\n\n  – A sensitivity analysis showing how changes in the initial batch size, growth rate, or learning rate impact performance would help clarify its practical robustness.\n\nController Pool Discretization and Continuity:\n\n  – The method assumes a finite set of candidate controllers. In many practical situations, controllers are chosen from a continuous space. Discretizing this space may lead to gaps in performance, where the true optimal controller lies between discretized options.\n\n  – It remains unclear how sensitive the overall performance is to the density and coverage of the candidate controller pool, and whether more sophisticated techniques (like clustering or interpolation between controllers) might be needed.\n\n**If an adversary can exploit the dynamics of batch length or learning rate adjustments (e.g., by inducing disturbances that trigger frequent resets), it may be possible to degrade the algorithm’s performance more than the current analysis suggests.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper attacks the challenging problem of online bandit nonlinear control by introducing the DBAR algorithm. Its core contribution is to relax the often unrealistic exponential stabilization requirement and instead rely on merely asymptotic stabilization. To do so, the authors combine two innovative ideas: a dynamic batching strategy that gradually increases the batch length to help certify stability and an adaptive learning rate that adjusts according to the state norm. The paper rigorously proves asymptotic and finite-gain stability (Theorems 4.1 and 4.2) and provides regret bounds (Theorems 4.5, 4.6, and 4.10).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Title Capitalization: Change the title from “Dynamic Batch length and Adaptive learning Rate” to “Dynamic Batch Length and Adaptive Learning Rate.”\n- Standardize Inequality Notation: Change “x0 ̸= 0” to “x₀ ≠ 0” for clarity.\n- Improve Punctuation Around Math Expressions: Ensure that inline expressions (e.g., “cₜ(xₜ, uₜ), t = 0, …, T”) have proper punctuation and clear separation.\n- Consistent Subscript and Variable Notation: Use uniform formatting for subscripts (e.g., always use πᵢ(0) and xₜ₊₁) throughout the document.\n- Refine Algorithm Input Formatting: Reformat the algorithm’s parameter list so that each parameter (e.g., T, η₀, (τ_b) for b ≥ 0, etc.) is clearly separated for better readability.\n- Correct Spacing Around Operators: Add necessary spaces in expressions such as changing “1-β(τ₀)” to “1 - β(τ₀).”\n- Ensure Uniform Use of Key Terms: Decide on a single form (e.g., “nonstochastic” or “non-stochastic”) and apply it consistently.\n- Adaptive Learning Rate Expression Formatting: Rewrite the update rule for η₍b+1₎ to include proper spacing and parentheses (e.g., η₍b+1₎ = η₀ / (α₍b+1₎)^(2 s₍b+1₎)).\n- Clarify Dynamic Batch Length Expression: Reformat and explain the expression for τ₀ (e.g., τ₀ = ⎣z₁(z₂)z₃⎦ > 0) with proper spacing and a brief explanation of the parameters z₁, z₂, and z₃.\n- Detailed Regret Bound Derivation: Provide additional intermediate steps and clearer explanations in the derivation of the regret bounds.\n- Expand Proofs for Stability Theorems: Enhance the proofs of Theorems 4.1 and 4.2 with more detailed explanations of key steps.\n- Include Sensitivity Analysis: Add a discussion (and corresponding derivations if possible) on how changes in key parameters (e.g., η₀, τ_b, β(·)) affect stability and regret.\n- Improve Transitions Between Sections: Add transitional sentences between major sections (e.g., from the algorithm pseudocode to the theoretical proofs) to guide the reader smoothly.\n- Provide Illustrative Examples: Include examples that demonstrate the algorithm’s behavior under various parameter settings to clarify the practical implications of the theoretical results.\n\nOverall, the paper presents a strong and innovative contribution to online bandit nonlinear control and can be accepted after these minor revisions addressing grammar, notation, and clarity are implemented.", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The results are solid and it is worth bringing these results to the community.
Decision: Accept (poster)