# Adaptive Decision-Making with Constraints and Dependent Losses: Performance
Guarantees and Applications to Online and Nonlinear Identification

Michael Muehlebach  Max Planck Institute for Intelligent Systems, Max Planck
Ring 4, 72076 Tuebingen, Germany (e-mail: michaelm@tue.mpg.de).

###### Abstract

: We consider adaptive decision-making problems where an agent optimizes a
cumulative performance objective by repeatedly choosing among a finite set of
options. Compared to the classical prediction-with-expert-advice set-up, we
consider situations where losses are constrained and derive algorithms that
exploit the additional structure in optimal and computationally efficient
ways. Our algorithm and our analysis is instance dependent, that is,
suboptimal choices of the environment are exploited and reflected in our
regret bounds. The constraints handle general dependencies between losses
(even across time), and are flexible enough to also account for a loss budget,
which the environment is not allowed to exceed. The performance of the
resulting algorithms is highlighted in two numerical examples, which include a
nonlinear and online system identification task.

###### keywords:

adaptive decision-making; online learning; hedge; multiplicative weights;
optimization; system identification; nonlinear system identification

††thanks: The author thanks Fang Nan for fruitful discussions that led to
parts of this work. He also thanks the German Research Foundation and the
Branco Weiss Fellowship, administered by ETH Zurich, for the support.

##  1 Introduction

The multiplicative weights (or hedge) algorithm is a cornerstone of online
learning. It not only provides a unified framework for many important
algorithms in computer science (see Arora et al. (2012)), but represents the
basis for online convex optimization, (Hazan, 2022) and bandit algorithms,
(Lattimore and Szepesvári, 2020). However, despite being both simple and
successful, it has arguably received little attention in the control
community. Indeed, the fact that the algorithm often deals with decisions over
a fixed and finite set of choices and involves either a stationary or a
strongly adversarial environment can be perceived as show-stoppers for control
problems, which involve dynamics, transients, and decisions over continuous
spaces. The article shows that, despite some of these seemingly fundamental
differences, the adaptive-decision making framework has the potential to bring
new perspectives to control theory and offers flexible tools for designing
computationally efficient algorithms with theoretical guarantees. This will be
highlighted by introducing a new variant of multiplicative weights that
accounts for constraints. These constraints can be used to model a-priori
knowledge, uncertainty, dependencies across time, and can account for a loss
budget of the environment. We also show that the concept of regret
minimization provides a natural framework for nonlinear and online system
identification problems.

_Related work:_ Adaptive decision-making and online learning has a very rich
history, (Cesa-Bianchi and Lugosi, 2006), (Littlestone et al., 1995), (Shalev-
Shwartz, 2011), due to its connections to game theory, economics, machine
learning, and optimization. In its basic set-up, an agent chooses among a
finite set of options at every iteration. The environment, which chooses the
losses, is assumed to be adversarial, resulting in the typical non-asymptotic
regret bound $\sqrt{T\text{log}(m)/2}$ (Karlin and Peres, 2016). More
recently, various extensions of this setting have been considered. For
example, when both, the agent and the environment, make their choices
according to the same (randomized) procedure, see e.g. Syrgkanis et al.
(2015), faster convergence is achieved, resulting in a regret that scales with
$\log(m)\log(T)^{4}$, (Daskalakis et al., 2021). A different approach has been
taken in Rakhlin et al. (2011), where either deterministic or stochastic
constraints are imposed on the adversary. The work characterizes the impact of
constraints on online learning rates that are theoretically achievable. An
even more general, non-parametric setting has been considered in Daskalakis
and Golowich (2022), where the authors quantify the impact of constraints and
construct an explicit algorithm based on a combination of (optimistic)
multiplicative weights and a generalization of the Standard Optimal Algorithm,
(Littlestone, 1988).

The aim of our approach is different compared to these important works.
Instead of exposing fundamental relations between the complexity of
constraints and the attainable regret in the worst case, we provide an
instance-dependent algorithm that is able to exploit knowledge about the
constraints, while benefiting from a suboptimal play of the environment. We
show that our algorithm is optimal in a precise min-max sense when the time
horizon is large. Moreover, the algorithm recovers multiplicative weights in
the absence of constraints and for an adversarial environment. Our research is
in line with recent work in reinforcement learning (Foster et al., 2020; Rolf
et al., 2021); and we will see that both aspects, the ability to cope with
constraints and the instance-dependency will lead to vast improvements over
multiplicative weights.

_Structure:_ The article is structured as follows. Sec. 2 formulates the
adaptive decision-making problem and discusses the multiplicative weights
algorithm. Sec. 3 presents our variant of multiplicative weights that can
handle constraints. Sec. 4 analyzes box constraints, which provides important
intuition and optimality guarantees for our algorithms. The article concludes
with two numerical examples in Sec. 5 and a summary in Sec. 6.

##  2 Preliminaries

We start by summarizing the classical adaptive decision-making framework and
the multiplicative weights algorithm. This sets the stage for the later
developments.

###  2.1 Problem formulation

We consider the set-up described in Alg. 1, where an agent has to choose among
a set of $m$ options during $T$ iterations (both $m$ and $T$ are positive
integers). At iteration $t$, the agent has access to the history of past
losses, which are represented by the vectors $l_{j}\in\mathbb{R}^{m}$,
$j=0,1,\dots,t-1$, as well as the set $X_{t}$ that constrains $l_{t}$. He
chooses the option $a_{t}$, the environment then reveals $l_{t}\in X_{t}$, and
inflicts the loss $l_{t}^{a_{t}}$ on the agent. In general, the sets $X_{t}$
change dynamically over time and may be influenced by past losses and actions,
with the only requirement that at time $t$, the agent has knowledge of
$X_{t}$. Throughout the article, we use subscripts to denote time (or the
iteration number) and superscripts to denote the elements of a vector. As we
will see, the agent has a strong incentive to randomize his choices. We
therefore introduce the variable $p_{t}\in\Delta_{m}$ to represent the agent’s
probability distribution over the options $\\{1,\dots,m\\}$ at time $t$, where
$\Delta_{m}$ refers to the $m$-dimensional probability simplex. More
precisely, we have

$\Pr(a_{t}=i\leavevmode\nobreak\ |\leavevmode\nobreak\
l_{t-1},\dots,l_{0})=p_{t}^{i},$

and as a result, the expected loss
${\mathop{\mathrm{E}}}[l_{t}^{a_{t}}\leavevmode\nobreak\ |\leavevmode\nobreak\
l_{t-1},\dots,l_{0}]$ of the agent at time $t$ can be expressed concisely as
$p_{t}^{\mathsf{\tiny{T}}}l_{t}$. The agent seeks to minimize regret, which is
defined as

$\sum_{t=0}^{T-1}p_{t}^{\mathsf{\tiny{T}}}l_{t}-\min_{i\in\\{1,\dots,m\\}}\sum_{t=0}^{T-1}l_{t}^{i}.$
(1)

The regret compares the expected performance of the agent (conditioned on the
past) to the performance of the best single option had the agent known all the
losses $l_{t},t=0,\dots,T-1$ beforehand. At first sight, this performance
metric seems weak, since it does not compare against strategies that switch
between options. However, we will see that in system identification, for
example, there is really one single optimal option, which amounts to the best
model among a set of candidates. Moreover, our formalism can also account for
a small number of strategies that switch (for example, play option 1 if $t$ is
even and option 2 if $t$ is odd), since these can simply be added to the set
of options $\\{1,\dots,m\\}$. In the following, we will derive uniform upper
bounds on (1); uniform in the sense that the bounds hold for any strategy of
the environment (any sequence $l_{0},l_{1},\dots$). This includes randomized
strategies, or even strategies that depend on the agent’s past choices
$a_{t-1},\dots,a_{0}$. We will also derive lower bounds that conversely take
any potential strategy of the agent into account. Compared to the traditional
setting (Cesa-Bianchi and Lugosi, 2006) the losses of the environment are
restricted to the sets $X_{t}$, which are both known to the environment and
the agent.

Algorithm 1 Adaptive decision-making framework with constraints.

for $t=0\leavevmode\nobreak\ \mathrm{to}\leavevmode\nobreak\ T-1$ do

1\. agent chooses $a_{t}\in\\{1,2,\dots,m\\}$

$\rhd\leavevmode\nobreak\ a_{t}$ may be the outcome of a random event

$\rhd\leavevmode\nobreak\ a_{t}$ may depend on $l_{t-1}$,
$l_{t-2},\dots,l_{0}$

$\rhd\leavevmode\nobreak\ a_{t}$ may depend on $X_{t},X_{t-1},\dots,X_{0}$

2\. environment reveals loss $l_{t}\in X_{t}\subset\mathbb{R}^{m}$

$\rhd\leavevmode\nobreak\ l_{t}$ may be the outcome of a random event

$\rhd\leavevmode\nobreak\ l_{t}$ may depend on $a_{t-1},\dots,a_{0}$

3\. decider incurs loss $l_{t}^{a_{t}}$

end for

Objective
agent:$\sum\limits_{t=0}^{T-1}p_{t}^{\mathsf{\tiny{T}}}l_{t}-\\!\\!\min\limits_{i\in\\{1,\dots,m\\}}\sum\limits_{t=0}^{T-1}l_{t}^{i}\rightarrow\min$

###  2.2 The multiplicative weights (hedge) algorithm

The following subsection summarizes the multiplicative weights algorithm,
which is sometimes also referred to as hedge. The multiplicative weights
algorithm is designed for
$X_{0}=X_{1}=\dots=X_{T-1}=[0,L]\times\dots\times[0,L]$, where $L>0$ is a
(potentially large) constant. This represents an adversarial setup, where the
agent has essentially no prior knowledge except that losses are positive. (It
turns out that minor extensions can handle situations where $L$ is unknown
a-priori and could become arbitrarily large.) The multiplicative weights
algorithm is summarized in Alg. 2 and is particularly appealing due to its
simplicity. At each iteration, the weights $w_{t}^{i}$ are formed and
represent the performance of option $i$ up to iteration $t-1$. The probability
distribution $p_{t}^{i}$ is chosen to be proportional to $w_{t}^{i}$, and can
be motivated as follows:

$p_{t}:=\mathop{\mathrm{argmin}}_{q\in\Delta_{m}}q^{\mathsf{\tiny{T}}}\sum_{j=0}^{t-1}l_{j}-\frac{1}{\epsilon}H(q),$
(2)

where $H(q):=\sum_{i=1}^{m}-q_{i}\log(q_{i})$ denotes the Shannon entropy of
the distribution $q\in\Delta_{m}$. The objective function in (2) balances the
observed performance over the past iterations with the entropy of $q$, which
accounts for the uncertainty over the environment’s choice of $l_{t}$. The
amount of entropy regularization is controlled with the parameter $\epsilon$
and varies with the number of rounds that are played (if $T$ is large, the
weight on the regularization is increased, if $T$ is small the weight is
decreased).

Algorithm 2 Multiplicative weights

$\epsilon\leftarrow\sqrt{8\log(m)/T}/L$

for $t=0\leavevmode\nobreak\ \mathrm{to}\leavevmode\nobreak\ T-1$ do

$w_{t-1}^{i}\leftarrow\exp(-\epsilon\sum_{j=0}^{t-1}l_{j}^{i})$
$\triangleright$ $w_{-1}^{i}=1$ for $t=0$

$p_{t}^{i}\leftarrow w_{t-1}^{i}/(\sum_{i=0}^{m}w_{t-1}^{i})$

Sample $a_{t}$ according to $p_{t}$

end for

###  2.3 Analysis of the multiplicative weights algorithm

This subsection analyzes the regret that follows from Alg. 2 in a setting
where $X_{0}=\dots=X_{T-1}=[0,L]\times\dots\times[0,L]$. This represents the
starting point for the subsequent derivations.

The analysis of Alg. 2 hinges on the (Lyapunov) function
$\phi_{t}:=\sum_{i=1}^{m}w_{t}^{i}$. The reason why the analysis of $\phi_{t}$
is particularly useful is that $\phi_{t}$ is lower bounded by any
$w_{t}^{j},j=1,2,\dots,m$, and, in particular, by the weight corresponding to
the best single option in hindsight. Moreover, $\phi_{t}$ relates to
$\phi_{t-1}$ in the following way:

$\displaystyle\phi_{t}$
$\displaystyle=\sum_{i=1}^{m}w_{t}^{i}=\phi_{t-1}\sum_{i=1}^{m}\frac{w_{t-1}^{i}}{\phi_{t-1}}\exp(-\epsilon
l_{t}^{i})$ (3) $\displaystyle=\underbrace{\phi_{t-1}\exp(-\epsilon
l_{t}^{\mathsf{\tiny{T}}}p_{t})}_{\text{part\leavevmode\nobreak\
i}}\underbrace{\sum_{i=1}^{m}\frac{w_{t-1}^{i}}{\phi_{t-1}}\exp(-\epsilon\sum_{j=1}^{m}p_{t}^{j}(l_{t}^{i}-l_{t}^{j}))}_{\text{part\leavevmode\nobreak\
ii}},$

where we have used the definition of $w_{t}^{i}$ in the second step, before
factoring out $\exp(-\epsilon l_{t}^{\mathsf{\tiny{T}}}p_{t})$ in the last
step. Up to this point we have not used the fact that $w_{t-1}^{i}$ and
$p_{t}^{i}$ are related, as for example prescribed by Alg. 2. Thus, the above
equation for $\phi_{t}$ holds for any choice of losses and any
$p_{t}\in\Delta_{m}$. We also note that part i of the expression captures the
running cost of the agent, i.e., the first term in (1), whereas $\phi_{t}$
dominates the performance of the best single option up to time $t$ and relates
to the second term in (1). Hence, part ii, which is the ratio between
$\phi_{t}$ and part i, directly determines the regret, and we will therefore
design $p_{t}$, such that part ii is small. To this end, we reformulate part
ii by applying Taylor’s theorem to the exponential

part ii
$\displaystyle=1-\epsilon\sum_{i=1}^{m}\sum_{j=1}^{m}\frac{w_{t-1}^{i}}{\phi_{t-1}}p_{t}^{j}(l_{t}^{i}-l_{t}^{j})$
$\displaystyle+\frac{\epsilon^{2}}{2}\sum_{i=1}^{m}\frac{w_{t-1}^{i}}{\phi_{t-1}}\left(\sum_{j=1}^{m}p_{t}^{j}(l_{t}^{i}-l_{t}^{j})\right)^{2}+\frac{\epsilon^{3}}{6}\rho_{t},$
(4)

where $\rho_{t}$ captures terms of order $\epsilon^{3}$ and higher. We note
that $\rho_{t}$ is bounded by $L^{3}\exp(\epsilon L)$. In order to simplify
the presentation we assume $\epsilon L\leq 1$, which is obtained for $T\geq
8\text{log}(m)$. (The assumption can be avoided by applying Hoeffding’s lemma
to (3), which, as we will see in the next section, is too coarse for our
purposes.) As discussed above, the key for obtaining a small regret is to
design $p_{t}$ such that part ii is small. In multiplicative weights, this is
achieved with $p_{t}^{i}=w_{t-1}^{i}/\phi_{t-1}$, which ensures that the
_first-order_ term vanishes due to the fact that the summand
$p_{t}^{i}p_{t}^{j}(l_{t}^{i}-l_{t}^{j})$ is skew symmetric. Hence, the
environment’s choice of $l_{t}$ can at most affect second-order terms. We
further note that the second-order term describes nothing but the variance of
$l_{t}^{a_{t}}$, which by applying Popoviciu’s inequality, can be bounded by
$L^{2}/4$. (The bound is attained if the adversary chooses the losses
$l_{t}^{i}$ in such a way that half of the probability $p_{t}$ is concentrated
on losses $l_{t}^{i}=0$ and half of the probability $p_{t}$ is concentrated on
losses $l_{t}^{i}=L$.) This yields therefore

$\text{part\leavevmode\nobreak\ ii}\leq
1+\epsilon^{2}L^{2}/8+\epsilon^{3}\rho_{t}/6.$

As we will see in the following, terms of order $\epsilon^{3}$ are essentially
irrelevant, as they contribute at most to additive constants in the final
regret bound. We continue by bounding the right-hand side, where we exploit
the assumption $\epsilon L\leq 1$ and $\rho_{t}\leq L^{3}\exp(1)$ to obtain

$\text{part\leavevmode\nobreak\ ii}\leq
1+\epsilon^{2}L^{2}/8+\epsilon^{3}L^{3}/2\leq\exp(\epsilon^{2}L^{2}/8+\epsilon^{3}L^{3}/2),$

where we have again used a Taylor expansion of the exponential in the last
step. Unrolling the recursion for $\phi_{t}$, see (3), yields therefore
$\max_{i\in\\{1,\dots,m\\}}w_{T-1}^{i}\leq\phi_{T-1}$ and

$\phi_{T-1}\leq\phi_{-1}\exp(-\epsilon\sum_{t=0}^{T-1}l_{t}^{\mathsf{\tiny{T}}}p_{t}+\epsilon^{2}L^{2}T/8+\epsilon^{3}L^{3}T/2).$

We now rearrange terms, note that $\phi_{-1}=m$, and insert the definition of
$\epsilon$, which yields finally

$\displaystyle\sum_{t=0}^{T-1}p_{t}^{\mathsf{\tiny{T}}}l_{t}-\\!\\!\\!\\!\min_{i\in\\{1,\dots,m\\}}\\!\sum_{t=0}^{T-1}l_{t}^{i}$
$\displaystyle\leq L\sqrt{\text{log}(m)T/2}+4L\text{log}(m).$

We note that all of our steps, except for the application of Popoviciu’s
inequality, are tight for small $\epsilon$, i.e., for a large time horizon
$T$. It is therefore not surprising that there is a matching lower bound,
which indeed holds for large $T$ and $m$. Moreover, the additional constant
$4L\text{log}(m)$ can be avoided with a more careful bookkeeping. We summarize
the sharpened results in the next proposition.

###### Proposition 2.1

(See, e.g., Karlin and Peres (2016, Ch. 18)) The regret of Alg. 2 is bounded
by

$\sum_{t=0}^{T-1}p_{t}^{\mathsf{\tiny{T}}}l_{t}-\\!\\!\\!\\!\min_{i\in\\{1,\dots,m\\}}\\!\sum_{t=0}^{T-1}l_{t}^{i}\leq
L\sqrt{\text{log}(m)T/2}.$

Moreover, for any decision algorithm and constant $\epsilon^{\prime}>0$ there
exists $T>0$, $m>0$ and a deterministic loss sequence $l_{0},l_{1},\dots,$
such that

$\sum_{t=0}^{T-1}p_{t}^{\mathsf{\tiny{T}}}l_{t}-\\!\\!\\!\\!\min_{i\in\\{1,\dots,m\\}}\\!\sum_{t=0}^{T-1}l_{t}^{i}\geq
L\sqrt{\text{log}(m)T/2}-\epsilon^{\prime}.$

##  3 Decision-making with constraints

As we have seen in the previous section, the analysis of multiplicative
weights hinges on a Taylor series expansion in (3) and an appropriate choice
of $p_{t}$ that results in vanishing first-order terms. However, we also
realize that the final bound arises from the sum of all the second-order
terms. This motivates our research, which develops an update scheme that
factors in constraints and improves the second-order terms.

Our treatment starts by parametrizing $p_{t}$ in the following way

$p_{t}=\frac{w_{t-1}}{\phi_{t-1}}-\frac{\epsilon}{2}\underbrace{\left(\frac{\text{diag}(w_{t-1})}{\phi_{t-1}}-\frac{w_{t-1}w_{t-1}^{\mathsf{\tiny{T}}}}{\phi_{t-1}^{2}}\right)}_{:=Q_{t-1}}q_{t},$
(5)

where $q_{t}\in\mathbb{R}^{m}$ will be the decision-variable of our algorithm.
The parameterization is designed in such a way that
$\sum_{i=1}^{m}p_{t}^{i}=1$ for all $q_{t}\in\mathbb{R}^{m}$ and recovers
multiplicative weights for $q_{t}=0$. We also note that $Q_{t-1}$ is positive
semi-definite (see App. C). As a consequence of the parametrization, we obtain
the following expression for the remainder term part ii in (4)

$\text{part\leavevmode\nobreak\
ii}=1+\frac{\epsilon^{2}}{2}l_{t}^{\mathsf{\tiny{T}}}Q_{t-1}(l_{t}-q_{t})+\frac{\epsilon^{4}}{4}(l_{t}^{\mathsf{\tiny{T}}}Q_{t-1}q_{t})^{2}+\frac{\epsilon^{3}}{6}\rho_{t}.$

We therefore conclude that the second-order term can be actively controlled,
for example by choosing $q_{t}$ as follows

$\displaystyle r_{t}^{*}:=\min_{q_{t}\in\mathcal{Q}_{t}}$
$\displaystyle\max_{l_{t}\in
X_{t}}l_{t}^{\mathsf{\tiny{T}}}Q_{t-1}(l_{t}-q_{t}),$ (6)

where the set $\mathcal{Q}_{t}$ is defined as

$\mathcal{Q}_{t}:=\Big{\\{}q\in\mathbb{R}^{m}\leavevmode\nobreak\
|\leavevmode\nobreak\ q^{\mathsf{\tiny{T}}}\mathbf{1}=0,\leavevmode\nobreak\
\mathbf{1}\geq\frac{\epsilon}{2}(q-\mathbf{1}w_{t-1}^{\mathsf{\tiny{T}}}q/\phi_{t-1})\Big{\\}},$

with $\mathbf{1}:=(1,\dots,1)^{\mathsf{\tiny{T}}}\in\mathbb{R}^{m}$. The set
imposes $p_{t}\geq 0$ and includes a normalization with
$q^{\mathsf{\tiny{T}}}\mathbf{1}=0$, since both (5) and (6) are invariant to
transformations of the type $q^{\prime}\leftarrow q+\delta\mathbf{1}$. We can
express the objective function in (6) more succinctly by following elementary
manipulations:

$\displaystyle\sum_{i,j=1}^{m}\\!\frac{w_{t-1}^{i}w_{t-1}^{j}}{2\phi_{t-1}^{2}}\\!\left((l_{t}^{i}-l_{t}^{j})^{2}\\!-\\!(l_{t}^{i}-l_{t}^{j})(q_{t}^{i}-q_{t}^{j})\right).$

We note that (6) amounts to a somewhat pessimistic perspective, where the
agent considers the worst case over all the possible choices $l_{t}\in X_{t}$
of the environment. However, compared to multiplicative weights, we do not
assume that all weights $w_{t-1}^{i}$, $i=1,\dots,m$ are equal (this done when
applying Popoviciu’s inequality), which allows Alg. 3 and our analysis to
adapt and exploit an environment that plays in a suboptimal manner.
Furthermore, the constraints $X_{t}$ are allowed to depend on past actions
$a_{t-1},a_{t-2},\dots$ and similarly on past losses $l_{t-1},l_{t-2},\dots$,
and can therefore also account for budget constraints on the losses $l_{t}$.

The remaining part of this section establishes a regret bound for Alg. 3,
which is based on choosing $q_{t}$ according to (6).

Algorithm 3 Multiplicative weights with constraints

$c_{1}>0$, $c_{2}>0$ $\triangleright$ e.g. $c_{1}=10^{-2}$, $c_{2}=L^{2}/4$

$\bar{r}^{*}\leftarrow c_{1}\log(m)^{2/3}L^{2}T^{-1/3}$

for $t=0\leavevmode\nobreak\ \mathrm{to}\leavevmode\nobreak\ T-1$ do

$\epsilon_{t-1}\leftarrow\sqrt{\frac{2\text{log}(m)}{c_{2}+\sum_{j=0}^{t-1}\tilde{r}_{j}^{*}}}$
$\triangleright$ $\epsilon_{-1}=\sqrt{2\text{log}(m)/c_{2}}$

$w_{t-1}^{i}\leftarrow\exp(-\epsilon_{t-1}\sum_{j=0}^{t-1}l_{j}^{i})$
$\triangleright$ $w_{-1}^{i}=1$

$\phi_{t-1}\leftarrow\sum_{i=1}^{m}w_{t-1}^{i}$

$q_{t}^{*}\leftarrow\mathop{\mathrm{argmin}}_{q_{t}\in\mathcal{Q}_{t}}\max_{l_{t}\in
X_{t}}l_{t}^{\mathsf{\tiny{T}}}Q_{t-1}(l_{t}-q_{t})$

$p_{t}\leftarrow\frac{w_{t-1}}{\phi_{t-1}}-\frac{\epsilon_{t-1}}{2}Q_{t-1}q_{t}^{*}$

Sample $a_{t}$ according to $p_{t}$, observe $l_{t}$

$\tilde{r}_{t}^{*}\leftarrow\max\\{l_{t}^{\mathsf{\tiny{T}}}Q_{t-1}(l_{t}-q_{t}^{*}),\bar{r}^{*}\\}$

end for

We note that Alg. 3 adapts the parameter $\epsilon_{t-1}$ on the go. (This is
due to the fact that $r_{t}^{*}$ depends on $w_{t}^{i}$, which is only
available at time $t$.) In order to simplify the exposition, we start by
analyzing the constant step-size version of Alg. 3; it turns out that the
adaptive algorithm can be analyzed with the same ideas, see App. A.
Furthermore, in our analysis the constant $L$ will be defined as

$L:=\max_{t\in\\{0,1,\dots,T-1\\}}\max_{l_{t}\in X_{t}}|l_{t}^{i}-l_{t}^{j}|.$

According to the previous discussion, we obtain the following bound for part
ii:

$\text{part\leavevmode\nobreak\ ii}\leq
1+\epsilon^{2}r_{t}^{*}/2+\epsilon^{3}L^{3}/2,$

where $r_{t}^{*}$ is given by (6) and we have used the fact that
$q_{t}^{\mathsf{\tiny{T}}}Q_{t-1}l_{t}\leq L^{2}/4$ and that $\rho_{t}$ (see
(4)) is bounded by $L^{3}\exp(1)$. We note that this matches almost verbatim
the derivation of multiplicative weights. Thus, by following the same steps,
which include unrolling the recursion for $\phi_{t}$, rearranging terms and
dividing by $\epsilon$ we obtain

$\sum_{t=0}^{T-1}p_{t}^{\mathsf{\tiny{T}}}l_{t}-\\!\\!\\!\\!\min_{i\in\\{1,\dots,m\\}}\\!\sum_{t=0}^{T-1}l_{t}^{i}\leq\text{log}(m)/\epsilon+\epsilon\sum_{t=0}^{T-1}r_{t}^{*}/2+\epsilon^{2}L^{3}T/2.$

By choosing the parameter $\epsilon$ to be
$\sqrt{2\text{log}(m)/\sum_{j=0}^{T-1}r_{j}^{*}}$, we finally arrive at the
following bound for the regret

$\sum_{t=0}^{T-1}p_{t}^{\mathsf{\tiny{T}}}l_{t}-\\!\\!\\!\\!\min_{i\in\\{1,\dots,m\\}}\\!\sum_{t=0}^{T-1}l_{t}^{i}\leq\sqrt{2\text{log}(m)\sum_{j=0}^{T-1}r_{j}^{*}}+\frac{\text{log}(m)L^{3}}{\bar{r}^{*}},$

where $\bar{r}^{*}>0$ denotes a lower bound on $r_{j}^{*}$.111We assume
$r_{j}^{*}\geq 0$ without loss of generality. If
$\sum_{j=0}^{T-1}r_{j}^{*}=\mathcal{O}(T^{2/3})$, then an even smaller regret
on the order $T^{1/3}$ can be achieved. It is clear that a slightly improved
choice of $\epsilon$ can balance the two cases, i.e., transition from a
$\mathcal{O}(\sqrt{T})$ to a $\mathcal{O}(T^{1/3})$ regret. This is included
in Alg. 3, but we have omitted further explanations to simplify the
presentation. The first term on the right-hand side, closely resembles the
regret bound from the previous section. In fact, for
$X_{t}=[0,L]\times\dots\times[0,L]$, $r_{t}^{*}$ can be bounded by $L^{2}/4$,
which recovers the result from the previous section. However, if the
accumulation of $r_{j}^{*}$ is small, the algorithm proposed in this section
largely outperforms multiplicative weights. Alg. 3, which chooses the
parameter $\epsilon$ adaptively, achieves almost the same result, as
summarized by the following proposition. The proof is a bit more involved due
to the fact that $\epsilon$ is varying, see App. A.

###### Proposition 3.1

Let $c_{2}=2\log(m)L^{2}$. Then, the regret of Alg. 3 is bounded by

$\sum_{t=0}^{T-1}p_{t}^{\mathsf{\tiny{T}}}l_{t}-\\!\\!\\!\\!\min_{i\in\\{1,\dots,m\\}}\\!\sum_{t=0}^{T-1}l_{t}^{i}\leq
3\sqrt{\text{log}(m)\sum_{j=0}^{T-1}\tilde{r}_{j}^{*}}\\\
+\frac{7\log(m)L^{3}}{4\bar{r}^{*}}\text{log}\left(8\log(m)+4/L^{2}\sum_{j=0}^{T-1}\tilde{r}_{j}^{*}\right).$

##  4 Intervals

In the previous section $X_{t}$ was allowed to be an arbitrary closed subset
of $\mathbb{R}^{m}$. We now turn to the case where
$X_{t}=[\underline{l}_{t}^{1},\bar{l}_{t}^{1}]\times\dots\times[\underline{l}_{t}^{m},\bar{l}_{t}^{m}]$,
that is, where each loss $l_{t}^{i}$ is restricted to the interval
$[\underline{l}_{t}^{i},\bar{l}_{t}^{i}]$. This leads to an important
simplification in (6), which is summarized by the following lemma.

###### Lemma 4.1

Let $q_{t}\in\mathbb{R}^{m}$ be an arbitrary vector, and
$X_{t}=[\underline{l}_{t}^{1},\bar{l}_{t}^{1}]\times\dots\times[\underline{l}_{t}^{m},\bar{l}_{t}^{m}]$.
Then $l_{t}^{\mathsf{\tiny{T}}}Q_{t-1}(l_{t}-q_{t})$ achieves its maximum for
$l_{t}\in X_{t}$ on the corners of $X_{t}$, that is, when
$l_{t}\in\\{\underline{l}_{t}^{1},\bar{l}_{t}^{1}\\}\times\dots\times\\{\underline{l}_{t}^{m},\bar{l}_{t}^{m}\\}$.

###### Proof.

The proof is by contradiction and starts by assuming that the maximizer
$l_{t}^{*}\in X_{t}$ has at least one component $j$, which is in the interior
of the interval $[\underline{l}_{t}^{j},\bar{l}_{t}^{j}]$. We now consider
$l_{t}=l_{t}^{*}+e_{j}\delta$, where $e_{j}\in\mathbb{R}^{m}$ is the $j$th
unit vector of the standard basis in $\mathbb{R}^{m}$, and
$\delta\in\mathbb{R}$ is a small scalar. For small values of $\delta$, we are
guaranteed that $l_{t}\in X_{t}$. Moreover, evaluating the objective function
at $l_{t}$ yields

$(l_{t}^{*})^{\mathsf{\tiny{T}}}Q_{t-1}(l_{t}^{*}-q_{t}^{*})+\delta
e_{j}^{\mathsf{\tiny{T}}}Q_{t-1}(2l_{t}^{*}-q_{t})+\delta^{2}e_{j}^{\mathsf{\tiny{T}}}Q_{t-1}e_{j},$

where $e_{j}^{\mathsf{\tiny{T}}}Q_{t-1}e_{j}$ is strictly positive due to the
positivity of the weights $w_{t-1}$. The term linear in $\delta$ is either
nonnegative or strictly negative. Hence, by choosing a small enough $\delta$,
either $\delta>0$ or $\delta<0$, the above expression exceeds the optimal
function value $(l_{t}^{*})^{\mathsf{\tiny{T}}}Q_{t-1}(l_{t}^{*}-q_{t}^{*})$,
which leads to a contradiction. ∎∎

Lemma 4.1 leads to the following important conclusions, as summarized by the
next proposition.

###### Proposition 4.1

Let
$E_{t}:=\\{\underline{l}_{t}^{1},\bar{l}_{t}^{1}\\}\times\dots\times\\{\underline{l}_{t}^{m},\bar{l}_{t}^{m}\\}$.
Then, the minmax problem stated in (6) is equivalent to the linear program

$r_{t}^{*}=\min_{q_{t}\in\mathcal{Q}_{t},\xi\in\mathbb{R}}\xi\quad\text{s.t.}\quad\xi\geq
l_{t}^{\mathsf{\tiny{T}}}Q_{t-1}(l_{t}-q_{t}),\leavevmode\nobreak\ \forall
l_{t}\in E_{t},$

which includes $2^{m}+m+1$ linear constraints. Moreover, the resulting
$q_{t}^{*}$ is optimal in the following sense: there exists a randomized
strategy $l_{t}^{*}$ of the environment, such that

$\text{E}_{l_{t}^{*}}[{l_{t}^{*}}^{\mathsf{\tiny{T}}}Q_{t-1}(l_{t}^{*}-q)]\geq
r_{t}^{*},\quad\forall q\in\mathcal{Q}_{t}.$

###### Proof.

The first part is an immediate corollary of Lemma 4.1. For the second part
(optimality) we consider any randomized strategy $l_{t}$ that only selects
elements in $E_{t}$. As a result, in expectation, the cost is given by

$\sum_{l\in E_{t}}l^{\mathsf{\tiny{T}}}Q_{t-1}(l-q)\text{Pr}(l_{t}=l),$

which is a linear function in $q$ and $\\{\text{Pr}(l_{t}=l)\\}_{l\in E_{t}}$.
Moreover, $\mathcal{Q}_{t}$ is compact and convex, which yields, according to
von Neumann’s minimax theorem

$\max_{\\{\text{Pr}(l_{t}=l)\\}_{l\in
E_{t}}}\min_{q_{t}\in\mathcal{Q}_{t}}\sum_{l\in
E_{t}}l^{\mathsf{\tiny{T}}}Q_{t-1}(l-q_{t})\text{Pr}(l_{t}=l)=\\\
\min_{q_{t}\in\mathcal{Q}_{t}}\max_{\\{\text{Pr}(l_{t}=l)\\}_{l\in
E_{t}}}\sum_{l\in
E_{t}}l^{\mathsf{\tiny{T}}}Q_{t-1}(l-q_{t})\text{Pr}(l_{t}=l).$ (7)

We consider the maximum on the right-hand side: For a fixed $q_{t}$, the
objective is linear in $\text{Pr}(l_{t}=l)$, which means that the maximum is
attained by choosing $l_{t}\in E_{t}$ deterministically. In other words, the
right-hand side achieves the same cost as

$\min_{q_{t}\in\mathcal{Q}}\max_{l_{t}\in
E_{t}}l_{t}^{\mathsf{\tiny{T}}}Q_{t-1}(l_{t}-q_{t})=r_{t}^{*}.$

Moreover, the maximum on the left-hand side of (7) is guaranteed to be
attained for some probability distribution $\\{\text{Pr}(l_{t}^{*}=l)\\}_{l\in
E_{t}}$, which implies

$\min_{q_{t}\in\mathcal{Q}_{t}}\sum_{l\in
E_{t}}l^{\mathsf{\tiny{T}}}Q_{t-1}(l-q_{t})\text{Pr}(l_{t}^{*}=l)=r_{t}^{*},$

leading to the desired conclusion. ∎∎

Prop. 4.1 provides three important results: i) $q_{t}$ can be obtained by
solving a linear program; ii) the resulting $q_{t}$ is optimal, in the sense
that there is no algorithm that is able to improve upon (4) for small enough
$\epsilon$. We note that the second order terms in (4) determine the regret up
to a constant (see Sec. 3); iii) the minimax theorem gives us an explicit
approach for computing the worst-case strategy $l_{t}^{*}$ of the environment.
For a given sequence of $X_{t}$, we can therefore recursively compute the
strategies $l_{t}^{*}$ for which any algorithm suffers at least the loss
$r_{t}^{*}$, $t=0,2,\dots,T-1$ in expectation. Compared to the lower bound
established in Prop. 2.1, this allows for a much more fine-grained analysis
and points to the fact that the result in Prop. 3.1 cannot be improved except
for constant (additive and multiplicative) factors.

Unfortunately, the linear program stated in Prop. 4.1 involves $2^{m}+m+1$
constraints. If $m$ is large, its solution can be computationally challenging.
The next proposition provides a simple strategy for choosing $p_{t}$ when $m$
is large. The strategy is even optimal for $m=2$ (see next section) and also
reduces to multiplicative weights, whenever
$\bar{l}_{t}^{1}=\dots=\bar{l}_{t}^{m}$ and
$\underline{l}_{t}^{1}=\dots=\underline{l}_{t}^{m}$ with
$\bar{l}_{t}^{i}-\underline{l}_{t}^{i}=L$.

###### Proposition 4.2

Without loss of generality we assume that all intervals overlap pairwise.222If
the intervals do not overlap pairwise, we can easily exclude the intervals
$i$, which are such that $\underline{l}_{t}^{i}\geq\bar{l}_{t}^{j}$ for some
$j\in\\{1,\dots,m\\}$. This is done by setting the corresponding $p_{t}^{i}=0$
and $w_{t-1}^{i}=0$. This will also be discussed in the next section (see case
$B$). An approximate solution to (6) is given by

$\hat{q}_{t}=\mathop{\mathrm{argmin}}_{q\in\mathcal{Q}_{t}}\sum_{i=1}^{m}\Big{|}q^{i}-\mu_{t}^{i}\Big{|}^{2},\leavevmode\nobreak\
\mu_{t}^{i}:=\bar{l}_{t}^{i}+\underline{l}_{t}^{i}-\frac{1}{m}\sum_{j=1}^{m}(\bar{l}_{t}^{j}+\underline{l}_{t}^{j}).$

For small enough $\epsilon$, the approximate solution achieves

$\displaystyle\max_{l_{t}\in
X_{t}}l_{t}^{\mathsf{\tiny{T}}}Q_{t-1}(l_{t}-\hat{q}_{t})$
$\displaystyle\leq\sum_{i,j=1,i\neq
j}^{m}\frac{w_{t-1}^{i}w_{t-1}^{j}}{2\phi_{t-1}^{2}}(\bar{l}_{t}^{i}-\underline{l}_{t}^{j})(\bar{l}_{t}^{j}-\underline{l}_{t}^{i}).$

We note that the proposition chooses each $q_{t}^{i}$ as close as possible to
$\mu_{t}^{i}$ subject to the constraint $\mathcal{Q}_{t}$. The value
$\mu_{t}^{i}$ compares the mid point of the interval $i$ to the average of all
mid points. The proposition will be further motivated in the next section and
a proof is included in App. B.

###  4.1 Closed-form solutions for $m=2$

For $m=2$ we can compute the solution of (6) in closed form. According to
Lemma 4.1 we are guaranteed that the maximum over $l_{t}$ is attained for
$l_{t}^{1}\in\\{\underline{l}_{t}^{1},\bar{l}_{t}^{1}\\}$ and
$l_{t}^{2}\in\\{\underline{l}_{t}^{2},\bar{l}_{t}^{2}\\}$, and we can also
rule out the cases $l_{t}^{1}=\underline{l}_{t}^{1}$,
$l_{t}^{2}=\underline{l}_{t}^{2}$ and $l_{t}^{1}=\bar{l}_{t}^{1}$,
$l_{t}^{2}=\bar{l}_{t}^{2}$. This leaves us with

$\min_{q_{t}\in\mathcal{Q}_{t}}\frac{w_{t-1}^{1}w_{t-1}^{2}}{\phi_{t-1}^{2}}\max\\{(\bar{l}_{t}^{1}-\underline{l}_{t}^{2})^{2}-(\bar{l}_{t}^{1}-\underline{l}_{t}^{2})(q_{t}^{1}-q_{t}^{2}),\\\
(\underline{l}_{t}^{1}-\bar{l}_{t}^{2})^{2}-(\underline{l}_{t}^{1}-\bar{l}_{t}^{2})(q_{t}^{1}-q_{t}^{2})\\}.$

The objective is therefore given by the maximum of two linear functions. More
importantly, the weights $w_{t-1}$ merely affect the scaling of the objective
function and are therefore irrelevant to the solution. This is no longer true
for $m>2$. Depending on the values of $\bar{l}_{t}^{1}-\underline{l}_{t}^{2}$
and $\bar{l}_{t}^{2}-\underline{l}_{t}^{1}$ we distinguish three different
cases, as summarized in Fig. 1. (In total there are six different cases, but
the remaining three can be reduced to $A$, $B$, $C$ by relabeling the losses
$l_{t}^{i}$.) We note that in case $B$ the objective is unbounded below, which
means that the resulting optimal strategy is given by $p_{t}^{1}=0$,
$p_{t}^{2}=1$. This clearly matches our intuition, since the agent has no
incentive in playing option $1$. In case $A$ and $C$ the optimal solution for
(6) is given by

$q_{t}^{1}=\begin{cases}\mu_{t}^{1},&\text{for}\leavevmode\nobreak\
-\frac{1}{\epsilon}\frac{\phi_{t-1}}{w_{t-1}^{1}}\leq\mu_{t}^{1}\leq\frac{1}{\epsilon}\frac{\phi_{t-1}}{w_{t-1}^{2}}\\\
\frac{1}{\epsilon}\frac{\phi_{t-1}}{w_{t-1}^{2}},&\text{for}\leavevmode\nobreak\
\mu_{t}^{1}\geq\frac{1}{\epsilon}\frac{\phi_{t-1}}{w_{t-1}^{2}}\\\
-\frac{1}{\epsilon}\frac{\phi_{t-1}}{w_{t-1}^{1}},&\text{for}\leavevmode\nobreak\
\mu_{t}^{1}\leq-\frac{1}{\epsilon}\frac{\phi_{t-1}}{w_{t-1}^{1}},\end{cases}$

where $\mu_{t}^{1}$ is defined in Prop. 4.2. By definition, we have
$q_{t}^{2}=-q_{t}^{1}$. The previous equation has a very intuitive meaning,
since $\mu_{t}^{1}$ is nothing but the difference between the midpoint of the
interval $[\underline{l}_{t}^{1},\bar{l}_{t}^{1}]$ and the midpoint of the
interval $[\underline{l}_{t}^{2},\bar{l}_{t}^{2}]$.

Provided that $q_{t}^{1}=\mu_{t}^{1}$ and $q_{t}^{2}=\mu_{t}^{2}$ the
resulting cost is given by

$\frac{w_{t-1}^{1}w_{t-1}^{2}}{\phi_{t-1}^{2}}(\bar{l}_{t}^{1}-\underline{l}_{t}^{2})(\bar{l}_{t}^{2}-\underline{l}_{t}^{1});$

a lower cost is attained in the remaining cases for $\epsilon$ small enough.
The term
$(\bar{l}_{t}^{1}-\underline{l}_{t}^{2})(\bar{l}_{t}^{2}-\underline{l}_{t}^{1})$
can be reformulated as

$\underbrace{\left(\frac{\bar{l}_{t}^{1}-\underline{l}_{t}^{1}+\bar{l}_{t}^{2}-\underline{l}_{t}^{2}}{2}\right)^{2}}_{\text{average\leavevmode\nobreak\
length}^{2}}-\underbrace{\left(\frac{\bar{l}_{t}^{1}+\underline{l}_{t}^{1}}{2}-\frac{\bar{l}_{t}^{2}+\underline{l}_{t}^{2}}{2}\right)^{2}}_{\text{distance\leavevmode\nobreak\
between\leavevmode\nobreak\ center}^{2}},$

which implies that for two intervals of fixed length, the worst-case cost is
maximal if the intervals are centered and vanishes when
$\bar{l}_{t}^{1}=\underline{l}_{t}^{2}$ or
$\underline{l}_{t}^{1}=\bar{l}_{t}^{2}$. It also directly reduces to $L^{2}/4$
in the multiplicative weights setting and therefore generalizes the analysis
from Sec. 2.3.

$1$
---
$2$
---
$1$
---
$2$
---
$1$
---
$2$
---
$A$
---
$B$
---
$C$
---
$q_{t}^{1}-q_{t}^{2}$
---
$q_{t}^{1}-q_{t}^{2}$
---
$q_{t}^{1}-q_{t}^{2}$
---
$(q_{t}^{1}-q_{t}^{2})^{*}$
---
$(q_{t}^{1}-q_{t}^{2})^{*}$
---
Figure 1: This figure illustrates the three different cases, where $A$ is
given by
$\bar{l}_{t}^{1}-\underline{l}_{t}^{2}\geq\bar{l}_{t}^{1}-\underline{l}_{t}^{2}\geq
0$, $B$ by $\bar{l}_{t}^{1}\geq\underline{l}_{t}^{2}$, and $C$ by
$\bar{l}_{t}^{1}-\underline{l}_{t}^{2}\geq 0$,
$\underline{l}_{t}^{2}-\bar{l}_{t}^{2}\leq 0$. In case $A$ the minimum over
$q_{t}^{1}-q_{t}^{2}$ is attained for negative values, whereas for case $C$
the minimum is attained for positive values. For case $B$ the objective
function is unbounded, which matches our intuition since the interval
$[\underline{l}_{t}^{1},\bar{l}_{t}^{1}]$ dominates
$[\underline{l}_{t}^{2},\bar{l}_{t}^{2}]$.

##  5 Numerical examples

The following section contains two numerical examples that highlight the
effectiveness of Alg. 3.

###  5.1 Random intervals

In the first example we choose
$X_{t}=[\underline{l}_{t}^{1},\bar{l}_{t}^{1}]\times\dots[\underline{l}_{t}^{m},\bar{l}_{t}^{m}]$,
where each $\underline{l}_{t}^{i}$ and $\bar{l}_{t}^{i}$ correspond to two
independent samples from the uniform distribution over $[0,1]$. (The samples
are ordered such that $\underline{l}_{t}^{i}\leq\bar{l}_{t}^{i}$.) The losses
$l_{t}^{i}$ are obtained by sampling from the uniform distribution over
$[\underline{l}_{t}^{i},\bar{l}_{t}^{i}]$. Fig. 2 and Fig. 3 compare Alg. 3 to
multiplicative weights for $T=200$ and $m=10$, and $T=200$, $m=100$. In the
latter case the optimization (6) is approximated with the method summarized in
Prop. 4.2. We note that Alg. 3 indeed exploits the available knowledge about
the intervals $[\underline{l}_{t}^{i},\bar{l}_{t}^{i}]$ leading to an
accumulated cost that is substantially below the cost of the best single
option in hindsight (negative regret).

$60$$65$$70$$75$$80$$85$$90$$95$$100$$105$$0$$0.1$$0.2$$0.3$acc. cost at
$T=200$counts (norm.)Alg. 3MWBest Figure 2: The figure shows the histogram of
the accumulated cost for problems where the intervals
$[\underline{l}_{t}^{i},\bar{l}_{t}^{i}]$ are randomly generated in $[0,1]$.
We set $m=10$ and $T=200$, and directly solve (6). “Best” denotes the best
option in hindsight and “MW” multiplicative weights. We note that Alg. 3
largely outperforms the multiplicative weights algorithm.
$50$$55$$60$$65$$70$$75$$80$$85$$90$$95$$100$$105$$110$$0$$0.1$$0.2$$0.3$$0.4$acc.
cost at $T=200$counts (norm.)Alg. 3MWBest Figure 3: The figure shows the
histogram of the accumulated cost for problems where the intervals
$[\underline{l}_{t}^{i},\bar{l}^{i}]$ are randomly generated in $[0,1]$. We
set $m=100$ and $T=200$, and we have chosen $\epsilon$ as specified in Alg. 3
and Alg. 2 with $L=1$. The optimization in Alg. 3 is approximated with Prop.
4.2. “Best” denotes the best option in hindsight and “MW” multiplicative
weights. We note that Alg. 3 largely outperforms the multiplicative weights
algorithm.

###  5.2 Nonlinear online identification

The decision-making framework discussed in this article can be used for
nonlinear and online system identification, which we will illustrate next. We
assume that there exists a finite number of candidate models, for example

$x_{t+1}=\theta
x_{t}(1-x_{t}),\quad\theta\in\\{\theta^{1},\dots,\theta^{m}\\},$ (8)

where $x_{t}\in\mathbb{R}$ denotes the state at time $t$, and where one of the
candidate models accurately describes the behavior of the underlying unknown
system. The losses $l_{t}^{i}$ are chosen as the one-step prediction error,

$l_{t}^{i}=|\hat{x}_{t+1}-\theta^{i}\hat{x}_{t}(1-\hat{x}_{t})|,$

where $\hat{x}_{t+1}$ denotes the state of the underlying system at time
$t+1$. The dynamics specified in (8) are known to exhibit chaos, depending on
the value of $\theta$. We note that our results have a logarithmic dependency
on the number of options $m$. This means that if $\theta$ arises from a
discretization of a bounded region in $n_{p}$ dimensions with width $\delta$,
$\log(m)\sim n_{p}\log(1/\delta)$ and hence the regret is expected to scale
with $\sqrt{n_{p}}$, which is relatively mild. In our numerical example we set
$\theta^{i}$ to be an equidistant discretization with $m=50$ of the interval
$[3.0,3.9]$. Moreover, the underlying dynamics were set to

$\hat{x}_{t+1}=(3.57+n_{t})\hat{x}_{t}(1-\hat{x}_{t}),\quad
n_{t}\sim\text{Unif}([-0.05,0.05]),$

where the noise samples $n_{t}$ are independent. We note that the value of
3.57 exhibits chaos and lies between $\theta^{32}$ and $\theta^{33}$. The
intervals $\underline{l}_{t}^{i}$ and $\bar{l}_{t}^{i}$ are obtained by
maximizing, respectively minimizing
$|(3.57+n-\theta^{i})\hat{x}_{t}(1-\hat{x}_{t})|$ for $n\in[-0.05,0.05]$. The
evolution of the resulting accumulated cost is shown in Fig. 4 and we have
again approximated (6) with Prop. 4.2. The plot indicates that Alg. 3 has
again a competitive edge on multiplicative weights, even though for this
example, the difference is less pronounced. We believe that this is due to two
factors: i) the information contained in the intervals
$[\underline{l}_{t}^{i},\bar{l}_{t}^{i}]$ is limited, ii) the environment,
which chooses the losses is relatively benign in the sense that it closely
follows the model given by $\theta^{32}$ and/or $\theta^{33}$.

$0$$5$$10$$15$$20$$25$$30$$35$$40$$45$$50$$0$$5\cdot
10^{-2}$$0.1$$0.15$$0.2$$0.25$iterations $t$acc. prediction errorAlg. 3MWBest
Figure 4: The figure shows the accumulated prediction error as a function of
the number of iterations. “MW” refers to multiplicative weights and “Best” to
the best single action in hindsight.

##  6 Conclusion

The article analyzed adaptive decision-making problems, where an agent
repeatedly chooses among $m$ options and aims at minimizing regret. We
considered a setting where the losses are constrained, which provides the
agent with additional information. We developed an algorithm that accounts for
the constraints and is instance-adaptive, i.e., it exploits suboptimal choices
of the adversary. The algorithm relies on the solution of an optimization
problem at every iteration and largely outperforms multiplicative weights. We
also discussed an approximation strategy to reduce the computational effort
and highlighted an application to nonlinear and online system identification.

## References

  * Arora et al. (2012) Arora, S., Hazan, E., and Kale, S. (2012).  The multiplicative weights update method: a meta algorithm and applications.  _Theory of computing_ , 8(1), 121–164.
  * Cesa-Bianchi and Lugosi (2006) Cesa-Bianchi, N. and Lugosi, G. (2006).  _Prediction, Learning, and Games_.  Cambridge University Press.
  * Daskalakis et al. (2021) Daskalakis, C., Fishelson, M., and Golowich, N. (2021).  Near-optimal no-regret learning in general games.  _Advances of Neural Information Processing Systems_ , 34, 1–39.
  * Daskalakis and Golowich (2022) Daskalakis, C. and Golowich, N. (2022).  Fast rates for nonparametric online learning: From realizability to learning in games.  _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , 1–14.
  * Foster et al. (2020) Foster, D.J., Rakhlin, A., Simchi-Levi, D., and Xu, Y. (2020).  Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective.  _arXiv:2010.03104_ , 1–102.
  * Hazan (2022) Hazan, E. (2022).  _Introduction to Online Convex Optimization_.  MIT Press, second edition.
  * Karlin and Peres (2016) Karlin, A.R. and Peres, Y. (2016).  _Game Theory, Alive_.  American Mathematical Society.
  * Lattimore and Szepesvári (2020) Lattimore, T. and Szepesvári, C. (2020).  _Bandit Algorithms_.  Cambridge University Press.
  * Littlestone et al. (1995) Littlestone, N., Long, P.M., and Warmuth, M.K. (1995).  On-line learning of linear functions.  _Computational Complexity_ , 5, 1–23.
  * Littlestone (1988) Littlestone, N. (1988).  Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.  _Machine Learning_ , 2, 285–318.
  * Rakhlin et al. (2011) Rakhlin, A., Sridharan, K., and Tewari, A. (2011).  Online learning: Stochastic and constrained adversaries.  _arXiv:1104.5070_ , 1–34.
  * Rolf et al. (2021) Rolf, E., Fridovich-Keil, D., Simchowitz, M., Recht, B., and Tomlin, C. (2021).  A successive-elimination approach to adaptive robotic sensing.  _IEEE Transactions On Robotics_ , 37(1), 34–47.
  * Shalev-Shwartz (2011) Shalev-Shwartz, S. (2011).  Online learning and online convex optimization.  _Foundation and Trends in Machine Learning_ , 4(2), 107–194.
  * Syrgkanis et al. (2015) Syrgkanis, V., Agarwal, A., Luo, H., and Schapire, R.E. (2015).  Fast convergence of regularized learning in games.  _Advances in Neural Information Processing Systems_ , 28, 1–23.

##  Appendix A Proof of Prop. 3.1

We again analyze $\phi_{t}=\sum_{i=1}^{m}w_{t}^{i}$, which we express as

$\displaystyle\phi_{t}$
$\displaystyle=\phi_{t-1}^{\frac{\epsilon_{t}}{\epsilon_{t-1}}}\sum_{i=1}^{m}\left(\frac{w_{t-1}^{i}}{\phi_{t-1}}\right)^{\frac{\epsilon_{t}}{\epsilon_{t-1}}}e^{-\epsilon_{t}l_{t}^{i}}$
$\displaystyle=$
$\displaystyle\phi_{t-1}^{\frac{\epsilon_{t}}{\epsilon_{t-1}}}e^{-\epsilon_{t}\sum_{i=1}^{m}p_{t}^{i}l_{t}^{i}}\sum_{i=1}^{m}\left(\frac{w_{t-1}^{i}}{\phi_{t-1}}e^{-\epsilon_{t-1}(l_{t}^{i}-\sum_{j=1}^{m}p_{t}^{j}l_{t}^{j})}\right)^{\frac{\epsilon_{t}}{\epsilon_{t-1}}}\\!\\!\\!,$

for any $t\geq 0$. Due to the fact that $\epsilon_{t}\leq\epsilon_{t-1}$ we
can invoke the following variant of Jensen’s inequality

$\sum_{i=1}^{m}x_{i}^{\alpha}\leq
m^{1-\alpha}\left(\sum_{i=1}^{m}x_{i}\right)^{\alpha},$

which holds for any $x_{1}\geq 0,\dots,x_{m}\geq 0$ and $\alpha\in(0,1]$. We
obtain therefore the following upper bound on $\phi_{t}$

$\phi_{t-1}^{\frac{\epsilon_{t}}{\epsilon_{t-1}}}e^{-\epsilon_{t}p_{t}^{i}l_{t}^{i}}m^{1-\frac{\epsilon_{t}}{\epsilon_{t-1}}}\left(\underbrace{\sum_{i=1}^{m}\frac{w_{t-1}^{i}}{\phi_{t-1}}e^{-\epsilon_{t-1}(l_{t}^{i}-p_{t}^{j}l_{t}^{j})}}_{\text{part\leavevmode\nobreak\
ii}}\right)^{\frac{\epsilon_{t}}{\epsilon_{t-1}}},$

where we used Einstein’s summation convention to simplify the notation. We
apply Taylor’s expansion to the exponential in the sum over $w_{t-1}^{i}$,
which yields

$\text{part
ii}=1-\epsilon_{t-1}\sum_{i=1}^{m}\frac{w_{t-1}^{i}}{\phi_{t-1}}(l_{t}^{i}-p_{t}^{j}l_{t}^{j})\\\
+\frac{\epsilon_{t-1}^{2}}{2}\sum_{i=1}^{m}\frac{w_{t-1}^{i}}{\phi_{t-1}}(l_{t}^{i}-p_{t}^{j}l_{t}^{j})^{2}+\frac{\epsilon_{t-1}^{3}}{6}\rho_{t},$

where the remainder term $\rho_{t}$ is bounded by $L^{3}e^{L\epsilon_{t-1}}$.
By choosing $p_{t}=w_{t-1}/\phi_{t-1}-\epsilon_{t-1}Q_{t-1}q_{t}^{*}/2$, see
Alg. 3, we thus obtain

$\text{part ii}\leq
1+\frac{\epsilon_{t-1}^{2}}{2}\tilde{r}_{t}^{*}+\frac{\epsilon_{t-1}^{3}}{6}\rho_{t}\leq
e^{\frac{\epsilon_{t-1}^{2}}{2}\tilde{r}_{t}^{*}+\frac{\epsilon_{t-1}^{3}}{6}\rho_{t}},$

which gives rise to

$\phi_{t}\leq\phi_{t-1}^{\frac{\epsilon_{t}}{\epsilon_{t-1}}}m^{1-\frac{\epsilon_{t}}{\epsilon_{t-1}}}e^{-\epsilon_{t}p_{t}^{i}l_{t}^{i}+\frac{\epsilon_{t}\epsilon_{t-1}}{2}\tilde{r}_{t}^{*}+\frac{\epsilon_{t}\epsilon_{t-1}^{2}}{6}\rho_{t}},$

for any $t\geq 0$. Thus, after unrolling the recursion we obtain

$\phi_{t}\leq\phi_{-1}^{\epsilon_{t}/\epsilon_{-1}}m^{\epsilon_{t}\sum_{j=0}^{t}\frac{\epsilon_{j-1}-\epsilon_{j}}{\epsilon_{j-1}\epsilon_{j}}}\\\
e^{-\epsilon_{t}\sum_{j=0}^{t}p_{j}^{i}l_{j}^{i}}e^{\epsilon_{t}\sum_{j=0}^{t}\frac{\epsilon_{j-1}}{2}\tilde{r}_{j}^{*}+\frac{\epsilon_{j-1}^{2}}{6}\rho_{j}}.$

We further note that, by construction, $\phi_{t}\geq
e^{-\epsilon_{t}\sum_{j=0}^{t}l_{j}^{i}}$ for any $i\in\\{1,\dots,m\\}$, which
yields after rearranging terms

$\sum_{t=0}^{T-1}p_{t}^{\mathsf{\tiny{T}}}l_{t}-\\!\\!\\!\\!\min_{i\in\\{1,\dots,m\\}}\\!\sum_{t=0}^{T-1}l_{t}^{i}\leq\frac{\log(m)}{\epsilon_{-1}}+\log(m)\sum_{t=0}^{T-1}\frac{\epsilon_{t-1}-\epsilon_{t}}{\epsilon_{t-1}\epsilon_{t}}\\\
+\sum_{t=0}^{T-1}\frac{\epsilon_{t-1}\tilde{r}_{t}^{*}}{2}+\frac{\epsilon_{t-1}^{2}}{6}\rho_{t}.$

We introduce the variable $s_{t}:=\sum_{j=0}^{t}\tilde{r}_{j}^{*}+c_{2}$,
which means that $\epsilon_{t}$ can be expressed as $\sqrt{2\log(m)/s_{t}}$.
As a result,

$\displaystyle\sum_{t=0}^{T-1}\frac{\epsilon_{t-1}-\epsilon_{t}}{\epsilon_{t-1}\epsilon_{t}}$
$\displaystyle=\frac{1}{\sqrt{2\log(m)}}\sum_{t=0}^{T-1}\sqrt{s_{t}}-\sqrt{s_{t-1}}$
(9)
$\displaystyle=\frac{\sqrt{s_{T-1}}-\sqrt{L^{2}/4}}{\sqrt{2\log(m)}}=\sqrt{\frac{s_{T-1}}{2\log(m)}}-\frac{\text{log}(m)}{\epsilon_{-1}}.$

We now prove the following claim.
Claim 1:

$\sum_{j=0}^{t}\frac{\tilde{r}_{j}^{*}}{\sqrt{s_{j-1}}}\leq
2\sqrt{2s_{t}},\quad\forall t\geq 0.$ (10)

The claim is proved by induction. The claim can be easily verified for $t=0$.
We therefore proceed with the induction step, that is, we assume that the
claim holds for $t\geq 0$, and show that it is also satisfied for $t+1$. More
precisely, the induction hypothesis implies

$\displaystyle\sum_{j=0}^{t+1}\frac{\tilde{r}_{j}^{*}}{\sqrt{s_{j-1}}}=\frac{\tilde{r}_{t+1}^{*}}{\sqrt{s_{t}}}+\sum_{j=0}^{t}\frac{\tilde{r}_{j}^{*}}{\sqrt{s_{j-1}}}\leq\frac{\tilde{r}_{t+1}^{*}}{\sqrt{s_{t}}}+2\sqrt{2s_{t}}.$

The right-hand side can further be bounded as

$\displaystyle\frac{\tilde{r}_{j+1}^{*}}{\sqrt{s_{j}}}+2\sqrt{2}\sqrt{s_{t+1}-\tilde{r}_{t+1}^{*}}\leq\frac{\tilde{r}_{j+1}^{*}}{\sqrt{s_{j}}}+2\sqrt{2s_{t+1}}\left(1-\frac{\tilde{r}_{t+1}^{*}}{2s_{t+1}}\right),$

where we have used $s_{t}=s_{t+1}-\tilde{r}_{t+1}^{*}$ in the first step and
$\sqrt{1-\xi}\leq 1-\xi/2$ for all $\xi\in[0,1]$ in the second step. We
therefore obtain

$\displaystyle\sum_{j=0}^{t+1}\frac{\tilde{r}_{j}^{*}}{\sqrt{s_{j-1}}}\leq
2\sqrt{2s_{t+1}}+\frac{\tilde{r}_{t+1}^{*}}{\sqrt{s_{t+1}}}\left(\frac{\sqrt{s_{t+1}}}{\sqrt{s_{t}}}-\sqrt{2}\right).$

Due to the fact that $\tilde{r}_{j}^{*}\leq L^{2}/4$ we obtain
$s_{t+1}/s_{t}\leq 2$. This means the the claim holds true for $t+1$. By
induction, we can therefore infer that the claim is true. ∎

We make a second claim, which we will prove subsequently.
Claim 2:

$\sum_{j=0}^{t}\frac{1}{s_{j-1}}\leq\frac{1}{\bar{r}^{*}}\text{log}(4s_{t}/L^{2})+\frac{1}{c_{2}},\quad\forall
t\geq 0.$ (11)

The claim is again proved by induction and we note that it holds (trivially)
for $t=0$. We perform the step from $t$ to $t+1$ as follows

$\displaystyle\sum_{j=0}^{t+1}$
$\displaystyle\frac{1}{s_{j-1}}\leq\frac{1}{s_{t+1}}+\frac{1}{\bar{r}^{*}}\log(4s_{t}/L^{2})+\frac{1}{c_{2}}$
$\displaystyle=\\!\frac{1}{s_{t+1}}\\!+\\!\frac{1}{\bar{r}^{*}}\log(4s_{t+1}/L^{2})\\!+\\!\frac{1}{\bar{r}^{*}}\log(1\\!-\\!\tilde{r}_{t+1}^{*}/s_{t+1})\\!+\\!\frac{1}{c_{2}}.$

Due to the fact that $\log(1-\xi)\leq-\xi$ for all $\xi\leq 1$, we obtain

$\sum_{j=0}^{t+1}\frac{1}{s_{j-1}}\leq\frac{1}{\bar{r}^{*}}\log(4s_{t+1}/L^{2})+\frac{1-\tilde{r}_{t+1}^{*}/\bar{r}^{*}}{s_{t+1}}+\frac{1}{c_{2}}.$

The term $1-\tilde{r}_{t+1}^{*}/\bar{r}^{*}$ in the previous equation is
negative, since $\tilde{r}_{t+1}^{*}\geq\bar{r}^{*}$, see Alg. 3, which proves
the claim. ∎

We can now combine all the ingredients ((9), (10), and (11)) and obtain the
following regret bound

$\sum_{t=0}^{T-1}p_{t}^{\mathsf{\tiny{T}}}l_{t}-\\!\\!\\!\\!\min_{i\in\\{1,\dots,m\\}}\\!\sum_{t=0}^{T-1}l_{t}^{i}\leq(\frac{\sqrt{2}}{2}+2)\sqrt{s_{T-1}\log(m)}\\\
+\frac{\log(m)\exp(1)L^{3}}{3c_{2}}+\frac{L^{3}\exp(1)}{6\bar{r}^{*}}\log(4s_{T-1}/L^{2}).$

We can further use the inequality $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for all
$a,b\geq 0$ and the fact that $c_{2}=2\log(m)L^{2}\geq 2\log(2)L^{2}$ to
rewrite the above bound as

$\sum_{t=0}^{T-1}p_{t}^{\mathsf{\tiny{T}}}l_{t}-\\!\\!\\!\\!\min_{i\in\\{1,\dots,m\\}}\\!\sum_{t=0}^{T-1}l_{t}^{i}\leq
3\sqrt{\log(m)\sum_{j=0}^{T-1}\tilde{r}_{j}^{*}}+3\sqrt{c_{2}\log{m}}\\\
+\frac{L}{2}+\frac{L^{3}}{2\bar{r}^{*}}(\log(4s_{T-1}/L^{2})).$

The remaining steps are simple manipulations, which also rely on the fact that
$4/s_{T-1}/L^{2}\geq 8\log(m)\geq 8\log(2)$ and $L^{2}/4\geq\bar{r}^{*}$. ∎

##  Appendix B Proof of Prop. 4.1

We note that for small $\epsilon$, $\hat{q}_{t}=\mu_{t}$, and introduce the
notation $l_{t}^{ij}:=\bar{l}_{t}^{i}-\underline{l}_{t}^{j}$. As a result, we
obtain

$\max_{l_{t}\in X_{t}}l_{t}^{\mathsf{\tiny{T}}}Q_{t-1}(l_{t}-\hat{q}_{t})=\\\
\max_{l_{t}\in
X_{t}}\sum_{i,j=1}^{m}\frac{w_{t-1}^{i}w_{t-1}^{j}}{2\phi_{t-1}^{2}}(l_{t}^{i}-l_{t}^{j})(l_{t}^{i}-l_{t}^{j}-l_{t}^{ij}+l_{t}^{ji}).$
(12)

We further note that $-l_{t}^{ji}=\underline{l}_{t}^{i}-\bar{l}_{t}^{j}\leq
l_{t}^{i}-l_{t}^{j}\leq\bar{l}_{t}^{i}-\underline{l}_{t}^{j}=l_{t}^{ij}$, and
consider a single summand on the right-hand side of the above equation. We
denote this summand as

$f_{ij}(l_{t}^{i}-l_{t}^{j}):=\frac{w_{t-1}^{i}w_{t-1}^{j}}{2\phi_{t-1}^{2}}(l_{t}^{i}-l_{t}^{j})(l_{t}^{i}-l_{t}^{j}-l_{t}^{ij}+l_{t}^{ji}),$

and conclude that $f_{ij}$ is convex in $l_{t}^{i}-l_{t}^{j}$. Thus, for any
$\lambda\in[0,1]$ we have

$f_{ij}(l_{t}^{i}-l_{t}^{j})\leq\lambda
f_{ij}(-l_{t}^{ji})+(1-\lambda)f_{ij}(l_{t}^{ij}),$

where both $f_{ij}(-l_{t}^{ji})$ and $f_{ij}(l_{t}^{ij})$ evaluate to the same
value $w_{t-1}^{i}w_{t-1}^{j}l_{t}^{ji}l_{t}^{ij}/2\phi_{t-1}^{2}$. By
applying the same argument to all summands in (12), we conclude

$\max_{l_{t}\in
X_{t}}l_{t}^{\mathsf{\tiny{T}}}Q_{t-1}(l_{t}-\hat{q}_{t})\leq\sum_{i,j=1}^{m}\frac{w_{t-1}^{i}w_{t-1}^{j}}{2\phi_{t-1}^{2}}l_{t}^{ij}l_{t}^{ji},$

which yields the desired result. ∎

##  Appendix C Positive semi-definiteness of $Q_{t-1}$

We note that for any $x\in\mathbb{R}^{m}$,
$x^{\mathsf{\tiny{T}}}Q_{t-1}x=\sum_{i=1}^{m}(x^{i})^{2}u^{i}-(\sum_{i=1}^{m}u^{i}x^{i})^{2}$,
where $u:=w_{t-1}/\phi_{t-1}$. According to Sedrakyan’s inequality we have

$(\sum_{i=1}^{m}u^{i}x^{i})^{2}=\frac{(\sum_{i=1}^{m}u^{i}x^{i})^{2}}{\sum_{i=1}^{m}u^{i}}\leq\sum_{i=1}^{m}u^{i}(x^{i})^{2},$

which concludes that $Q_{t-1}$ is indeed positive semi-definite.


# Error Convergence Analysis and Stability of a Cloud Control AGV

Shreya Tayade1, Peter Rost2 and Andreas Maeder2  1Intelligent Networks
Research Group,
German Research Center for Artificial Intelligence, Kaiserslautern, Germany
Email<EMAIL_ADDRESS>2Nokia Bell Labs, Munich, Germany
Email: {peter.m.rost<EMAIL_ADDRESS>
###### Abstract

In this paper, we present a cloud based Automated Guided vehicle (AGV) control
system. A controller in an Edge cloud sends the control inputs to an AGV to
follow a predefined reference track over a wireless channel. The AGV feedback
the position update via uplink channel. The objective of this paper is to
evaluate the stability criterion of an AGV control system in presence of an
uplink channel outages. Moreover, we also analyse the impact of feedback
control parameters on the error convergence. The results show error
convergence at higher rate with optimal selection of feedback parameters. The
optimal feedback parameters that converges the error with critical damping is
evaluated for two scenarios; with limited AGV velocity and without the
limitation on AGV velocity. Furthermore, the paper describe the discretization
process of a continuous control AGV system.

###### Index Terms:

Wireless Networked Control System, Automated Guided Vehicles, Industry 4.0,
Edge cloud, Stability, Error convergence.

##  I Introduction

New use-cases have emerged in vertical industries with the launch of 5G
technology. Applications such as logistics, assembly lines and automotive
manufacturing have growing demands for cloud control AGVs. Traditional AGVs
are programmed to execute a designated task autonomously. As the controllers
are located on the AGV, path-planning and task-customization is painstaking.
Therefore to facilitate more flexibility and agility, a cloud based controller
is proposed for new generation of AGVs. The cloud control AGV enables on-
demand task updating and path planning while simultaneously collaborating and
coordinating with the other connected devices in a factory. The energy
consumption of an AGV can also be reduced by selectively offloading the
controller function in cloud [1, 2]. Extensive research on the coordinated AGV
controller is performed in recent years [3, 4, 5, 6]. The communication
technologies are enhanced to enable cloud based industrial use-cases in [7, 8,
9]. The paper [10], presents a continuous-time stable AGV control system with
limited velocity and acceleration, however, in practice the AGV controller
operates in discrete time. Therefore, to study the error performance of a
cloud based AGV system, we discretize the continuous-time control system
presented in [10]. A key characteristic of a controller is to assure stability
of a system. The stability of a system is evaluated from the system response.
A system is considered stable if the response of system is either bounded or
decreases to zero over time. The AGV control system is time-varying and non-
linear, hence, the generic approach to evaluate the stability criterion of a
LTI system is inapplicable [11, 12]. Moreover, in a cloud control AGV system,
the communication between a controller and an actuator occurs over an
imperfect wireless channel. The wireless link may introduce a delay or loss of
the information packets causing instability of the control system. The
research in [13, 14, 15, 16] investigates the impact of wireless network
uncertainties on the control system. The authors in [13, 14] considered a
basic LTI system, whereas many practical control systems are non-linear time-
varying in nature. [15, 16] presents the impact of downlink channel outages on
the stability of a non-linear time-varying system, it does not consider uplink
channel outages. In this paper we evaluate the stability criterion of a non-
linear, discrete, time-varying AGV system in presence of uplink channel
outages. Furthermore, the authors in [10] determine the control rule and
optimal feedback parameters to maintain AGV’s stability. In this paper, we
analyse the impact of feedback control parameters on the error convergence of
a cloud based AGV system. The error convergence of an AGV is analysed for two
different scenarios; with no limitation on the AGV velocity and with maximum
permissible AGV velocity.

The objective of this paper is to evaluate the stability of a discrete non-
linear, time-varying, in-homogeneous AGV control system taking into account
uplink channel outages. An approach presented in [11] is followed to evaluate
the stability of a non-linear time varying control system. In Section II, we
describe the discretization process of a continuous-time AGV control system.
The control rule and stability in presence of uplink channel outages is
evaluated in Section IV and Section IV respectively. The results on error
convergence rate with respect to feedback parameters are presented in Section
V. The conclusions are discussed in Section VI.

Figure 1: Discrete system of Cloud Controlled AGV

##  II AGV control system

An AGV follows an intended reference path $X_{r}=[x_{r},y_{r},\theta_{r}]$
where $(x_{r},y_{r})$ is the x-y coordinate and $\theta$ is the angle of
orientation. The Fig. 1, shows the basic function blocks of the control
system. The error detector evaluates the difference between the actual AGV
position and the intended path. The controller generates translational $\nu$
and rotational velocity $\omega$ according to the evaluated position error.
These velocities are the control inputs applied to an AGV actuator. The AGV
attains a new position $X_{c}$ = [$x_{c}$, $y_{c}$, $\theta_{c}$] following
the application of control inputs. The updated AGV position is feedback to the
error detector. The error is sent to the controller and new control inputs are
determined. The process continues until the reference path is completed by the
AGV. The feedback mechanism direct the error to approach zero, as time goes to
infinity.

The paper [10] present a continuous-time AGV control system. However, for a
cloud controlled AGV, the control inputs and the AGV’s position updates are
received at discrete time instants over a wireless channel. In this section, a
detailed functional description and the mathematical model for each block of a
discrete AGV control 1 is presented.

#### Error detector

The error detector evaluates the error $\epsilon(k)$ between the actual
position $X_{c}$ of an AGV, to the reference position $X_{r}$ at $k^{th}$ time
sample as

$\displaystyle\epsilon(k)$ $\displaystyle=\left(\begin{array}[]{c}x_{e}(k)\\\
y_{e}(k)\\\ \theta_{e}(k)\end{array}\right)$ (4)
$\displaystyle=\left(\begin{array}[]{ccc}\cos\theta_{c}(k)&\sin\theta_{c}(k)&0\\\
-\sin\theta_{c}(k)&\cos\theta_{c}(k)&0\\\
0&0&1\end{array}\right)\left(X_{r}(k)-X_{c}(k)\right)$ (8)
$\displaystyle=\mathbf{T_{e}}(k)\left(X_{r}(k)-X_{c}(k)\right),$ (9)

where $\mathbf{T_{e}(k)}$ is the rotational matrix, $x_{e}$, $y_{e}$ is the
error determined as a result of difference in x, y coordinate, and
$\theta_{e}$ is the error in the orientation of an AGV.

#### Controller

The controller calculates the control input $u(k)$ = [$\nu(k);\omega(k)$]
according to the error $\epsilon(k)$ determined in (9) as

$\displaystyle u(k)$ $\displaystyle=\left[\begin{array}[]{c}\nu(k)\\\
\omega(k)\end{array}\right]$ (12)
$\displaystyle=\left[\begin{array}[]{c}\nu_{r}(k)\cos\theta_{e}(k)+K_{x}x_{e}(k)\\\
\omega_{r}(k)+\nu_{r}(k)\left[K_{y}y_{e}(k)+K_{\theta}\sin\theta_{e}(k)\right]\end{array}\right],$
(15)

where $K_{x}\,[\mathrm{s^{-1}}]$, $K_{y}\,[\mathrm{m^{-1}}]$ and
$K_{\theta}\,[\mathrm{m^{-1}}]$ are constants which impact the convergence
rate of the control system. The stabilized control rule without uplink channel
outages is derived in [10], in the section IV, we evaluate a stable control
rule with uplink channel outages.

#### State evolution of an AGV

Following the application of the control inputs $\nu$ and $\omega$, an AGV
attains a new position state. The position state evolution of an AGV is
described in differential form as

$\displaystyle\dot{X_{c}}(t)$
$\displaystyle=\left(\begin{array}[]{c}\dot{x}_{c}(t)\\\ \dot{y}_{c}(t)\\\
\dot{\theta}_{c}(t)\end{array}\right)=\underbrace{\left(\begin{array}[]{cc}\cos\theta_{c}(t)&0\\\
\sin\theta_{c}(t)&0\\\ 0&1\end{array}\right)}_{\mathbf{J}(t)}u(t)$ (22)
$\displaystyle\dot{X_{c}}(t)$ $\displaystyle=\mathbf{J}(t)u(t),$ (23)

where $\dot{x}_{c}$ = $\nu_{x}$ = $\cos\theta_{c}(t)\cdot\nu(t)$ is the
velocity component in x-direction. The actual position of an AGV is obtained
by solving (23).

As shown in the Fig. 1, controller at the cloud generates control input $u(k)$
at time $t_{k}=k\cdot T_{s}$ where $k=\left\\{0,1\dots\right\\}$, represent
the sample point and $T_{s}$ as the sampling time. These control inputs $u(k)$
are sent to the actuator of an AGV over a wireless channel. The discrete
control inputs cannot be directly applied to the actuator of an AGV, as the
AGV state evolution is a physical process and continuous in time (23). The
state of an AGV will continuously evolve for the given control input.
Therefore, the control inputs are converted into the continuous time by D/A
converter. The D/A converter holds the control input $u(k)$ for the sampling
time period $T_{s}$, before it is applied to an actuator. The position state
$X_{c}$ of an AGV’s actuator evolves continuously for the given control inputs
$u(k)$, although the control inputs $u(k)$ are constant over a sampling time
period $T_{s}$. Furthermore, the current position updates of an AGV are
feedback to the controller. These discrete updates are obtained by sampling
the position state at $k^{\text{th}}$ time instant by A/D converter.

##  III Discretization

As the exchange of information between the AGV actuator and cloud controller
is in discrete time, it is necessary to evaluate the behavior of the state
variables $X_{c}(t)$ at these discontinuities. The actual position state
$X_{c}$ of an AGV at time $t$, is obtained by solving the differential
equation in (23). The control inputs are constant sampling time period $T_{s}$
= $t_{\text{k+1}}$-$t_{\text{k}}$, the state at any time $t$, such as
$t_{k}<t<t_{k+1}$ can be evaluated by integrating the above equation over the
time interval $\left[t_{k}\>t\right]$.

$\int\limits^{t}_{t_{k}}\dot{X}_{c}(t)dt=\int\limits^{t}_{t_{k}}J(t)u(t)dt$
(24)

$u(t)$ is constant over the given sampling time period, hence, $u(t)$ =
$u(t_{k})$, is independent of dt.

$X_{c}(t)=X_{c}(t_{k})+\int\limits^{t}_{t_{k}}J(t)dt\cdot u(t_{k})$ (25)

where $J(t)$ is a in-homogeneous non-linear system matrix, hence, the
integration cannot be solved in a closed form. Therefore, to evaluate the
approximate solution to the differential equation, we use piece-wise
integration approach. Assuming that the sampling interval
$T_{s}=t_{k+1}-t_{k}$, is small, $J(t)$ will be linear over this time
interval. The equation transforms to

$\displaystyle X_{c}(t)=X_{c}(t_{k})+\int\limits^{t}_{t_{k}}J(t)dt\cdot
u(t_{k})$ (26) $\displaystyle X_{c}(t)=X_{c}(t_{k})+(t-t_{k})\cdot
J(t_{k})\cdot u(t_{k})$ (27)

The position state variable $X_{c}(t)$ for a sufficiently low sampling period,
at time $t=t_{k+1}$ is determined as

$\displaystyle X_{c}(t_{k+1})=X_{c}(t_{k})+T_{s}\cdot J(t_{k})\cdot u(t_{k})$
(28)

The time $t_{k}$ can be represented in terms of samples as

$X_{c}(k+1)=X_{c}(k)+T_{s}\cdot J(k)\cdot u(k)$ (29)

$\displaystyle\underbrace{\left[\begin{array}[]{c}x_{c}(k+1)\\\ y_{c}(k+1)\\\
\theta_{c}(k+1)\end{array}\right]}_{X_{c}(k+1)}$
$\displaystyle=\underbrace{\left[\begin{array}[]{c}x_{c}(k)\\\ y_{c}(k)\\\
\theta_{c}(k)\end{array}\right]}_{X_{c}(k)}+T_{s}\cdot\mathbf{J}(k)\underbrace{\left[\begin{array}[]{c}\nu(k)\\\
\omega(k)\end{array}\right]}_{u(k)}$ (38)

where $u(k)$ is the control input at $k-\text{th}$ sample, and $\mathbf{J}(k)$
is

$\displaystyle\mathbf{J}(k)=\left(\begin{array}[]{cc}\cos\theta_{c}(k)&0\\\
\sin\theta_{c}(k)&0\\\ 0&1\end{array}\right).$ (42)

Here, $\theta_{c}(k)$ is the orientation of an AGV with respect to the x-axis
at the $k^{\text{th}}$ sample. Therefore, the equation becomes

$X_{c}(k+1)=X_{c}(k)+T_{s}\cdot\mathbf{J}(k)\cdot u(k).$ (43)

The solution in (43) is the discrete approximate to evaluate the position
state of an AGV at next time instant. The method followed is the Euler’s
method to solve nonlinear differential equations. The evaluated position state
of an AGV is sent to the error detector to evaluate the error.

##  IV Impact of uplink channel outages

#### Control rule

The control rule in (15) does not consider the impact of wireless channel
outages. In this section a control rule and stability criterion are determined
with uplink channel outages. For the sake of brevity, downlink channel is
assumed perfect. The position update $X_{c}(k)$ is transmitted over uplink
channel at every $T_{s}$ seconds. In presence of an uplink channel outages,
the position update $X_{c}(k)$ is not successfully received by an error
detector at the cloud. The error is therefore calculated with the outdated AGV
position $X_{c}(k-n_{ul})$, where $n_{ul}$ is the number of consecutive
channel outages. The error with the outdated position update $X_{c}(k-n_{ul})$
is

$\displaystyle\epsilon_{ul}$
$\displaystyle=\mathbf{T_{e}}(k-n_{ul})\left(X_{r}(k)-X_{c}(k-n_{ul})\right)$
(44) $\displaystyle\left[\begin{array}[]{c}x_{e,ul}(k)\\\ y_{e,ul}(k)\\\
\theta_{e,ul}(k)\end{array}\right]$
$\displaystyle=\left(\begin{array}[]{ccc}\cos\theta_{c}(k-n_{ul})&\sin\theta_{c}(k-n_{ul})&0\\\
-\sin\theta_{c}(k-n_{ul})&\cos\theta_{c}(k-n_{ul})&0\\\
0&0&1\end{array}\right)\times$ (51)
$\displaystyle\left[X_{r}(k)-X_{c}(k-n_{ul})\right]$ (52)

where $\mathbf{T_{e}(k)}$ is the rotational matrix and $\epsilon_{ul}$ is the
error with uplink channel outages. The new control rule $u_{ul}$ is generated
by substituting the error from (44) in (15) as

$\displaystyle u_{ul}(k)$
$\displaystyle=\left[\begin{array}[]{c}\nu_{ul}(k)\\\
\omega_{ul}(k)\end{array}\right]$ (55)
$\displaystyle=\left[\begin{array}[]{c}\nu_{r}(k)\cos\theta_{e,ul}(k)+K_{x}x_{e,ul}(k)\\\
\omega_{r}(k)+\nu_{r}(k)\left[K_{y}y_{e,ul}(k)+K_{\theta}\sin\theta_{e,ul}(k)\right]\end{array}\right]$
(58)

These control inputs $u_{ul}(k)$ are applied to an AGV actuator therefore new
position state at time $t_{k+1}$ is

$X_{c}(k+1)=X_{c}(k)+T_{s}\cdot\mathbf{J}(k)u_{ul}(k)$ (59)

$\displaystyle\dot{\epsilon}(t)=\left(\begin{array}[]{c}(\omega_{r}(t)+\nu_{r}(t)\left[K_{y}y_{e}(t)+K_{\theta}\sin\theta_{e}(t)\right])y_{e}(t)-\nu(t)+\nu_{r}(t)\cos\theta_{e}(t)\\\
-(\omega_{r}(t)+\nu_{r}(t)\left[K_{y}y_{e}(t)+K_{\theta}\sin\theta_{e}(t)\right])x_{e}(t)+\nu_{r}(t)\sin\theta_{e}(t)\\\
\omega_{r}(t)-\omega_{r}(t)+\nu_{r}(t)\left[K_{y}y_{e}(t)+K_{\theta}\sin\theta_{e}(t)\right]\end{array}\right)$
(63)

$\mathbf{A}(k)=\left(\begin{array}[]{ccc}1-T_{s}\cdot
K_{x}\cdot\cos\left[\theta_{c}(k)\right]\cdot\cos\left[\theta_{c}(k-n_{ul})\right]&-T_{s}\cdot
K_{x}\cdot\cos\left[\theta_{c}(k)\right]\cdot\sin\left[\theta_{c}(k-n_{ul})\right]&-T_{s}\sin\left[\theta_{c}(k)\right]\nu_{r}(k-n_{ul})\\\
-T_{s}\cdot
K_{x}\cdot\sin\left[\theta_{c}(k)\right]\cdot\cos\left[\theta_{c}(k-n_{ul})\right]&1-T_{s}\cdot
K_{x}\cdot\sin\left[\theta_{c}(k)\right]\cdot\sin\left[\theta_{c}(k-n_{ul})\right]&T_{s}\cdot\cos\left[\theta_{c}(k)\right]\nu_{r}(k-n_{ul})\\\
T_{s}\cdot
k_{y}\sin\left[\theta_{c}(k-n_{ul})\right]\nu_{r}(k-n_{ul})&-T_{s}\cdot
k_{y}\cos\left[\theta_{c}(k-n_{ul})\right]\nu(k-n_{ul})&1-T_{s}\cdot
k_{\theta}\nu_{r}(k-n_{ul})\end{array}\right)$

(64)

#### Error dynamics and Stability

The control rule in (15) is derived such that it can maintain system stability
in presence of an error. A system is stable around $\epsilon=0$, if the error
$\epsilon$ $\to$ 0 or is bounded. Therefore, we analyse the error convergence
by evaluating the error dynamics of an AGV control. The error dynamics of the
continuous time system is evaluated by taking the time derivative of error as

$\displaystyle\dot{\epsilon}(t)=\left(\begin{array}[]{c}\omega(t)y_{e}(t)-\nu(t)+\nu_{r}(t)\cos\theta_{e}(t)\\\
-\omega(t)x_{e}(t)+\nu_{r}(t)\sin\theta_{e}(t)\\\
\omega_{r}(t)-\omega(t)\end{array}\right),$ (68)

[10]. Substituting the control inputs $\omega$ and $\nu$ from (15), (63) is
derived. The non-linear error dynamics in (63) are linearized to the form of
(69), by taking the Jacobian of differential equation at $\epsilon$ = 0,

$\displaystyle\dot{\epsilon}(t)=A(t)\epsilon(t)$ (69)

The system is stable if all the real roots of characteristics equation for $A$
are negative as per the Routh-Hurwitz Criterion. The stability is already
proved in [10].

#### Stability with uplink outages

The error dynamics of a discrete time control system should be known to
evaluate the stability criterion with uplink channel outages. The position
state evolution with uplink channel outages is derived in (59). An equilibrium
is reach if the error $\epsilon_{ul}(k)=0$, i.e $X_{r}(k+1)$ \- $X_{c}(k+1)$ =
0. We linearize the state space system of (59) in the form
$X_{c}(k+1)=\mathbf{A}(k)X_{c}(k)+\mathbf{B}(k)u_{ul}(k)$ by taking Jacobian
of (59) and then substituting $X_{r}=X_{c}$. The control matrix $\mathbf{A}$
is evaluated in (64), by taking partial derivatives of (59) with respect to
$x_{c}$, $y_{c}$ and $\theta_{c}$ respectively [15]. If
$\\{\lambda_{1}(k),\dots,\lambda_{M}(k)\\}$ = Eig($\mathbf{A(k)}$) are the
Eigenvalues of $\mathbf{A}$, a (LTI) system is stable if

$\forall i,k:0<|\lambda_{i}(k)|<1$ (70)

[17, 11]. To check the stability of a time varying system, the test for
stability needs to be repeated for each time step $k$ as evaluated for
downlink channel outages in [15, 16].

(a) AGV reference track $X_{r}$

(b) Reference translational velocity $\nu_{r}$

Figure 2: Reference track and velocity

##  V Simulation setup and Results

###  V-A Simulation setup

An AGV traces a reference track $X_{r}$ shown in Fig. 2(a), in $T$ = 100 s.
The number of steps required to trace the complete track is $N_{timesteps}$ =
$T/T_{s}$, where $T_{s}=5\,\mathrm{ms}$. The reference track and the reference
velocity $\nu_{r}$ for each time step is shown in Fig. 2(b). In presence of
non-zero error, the control inputs are generated according to (15) and are
applied to the AGV actuators so that the error $\epsilon(k)$ $\to$ 0, as $k\to
N_{timesteps}$. The optimal selection of feedback parameters $K_{x}$,$K_{y}$
and $K_{\theta}$ is required to immediately reduce the error. The discrete AGV
controller is implemented in Matlab.

(a) AGV’s followed tracks: unlimited $\nu$

(b) Error in y-direction $y_{e}$: unlimited $\nu$

(c) Translational velocity: unlimited $\nu$

(d) AGV’s followed tracks: limited $\nu$

(e) Error in y-direction $y_{e}$: limited $\nu$

(f) Translational velocities: limited $\nu$

Figure 3: AGV tracks and error convergence Table I: Variable description Variable | Description
---|---
$X_{r}$ | Reference position vector of an AGV
$X_{c}$ | Actual position vector of an AGV
$\nu$ | Translational velocity
$\omega$ | Rotational velocity
$\nu_{r}$ | Reference translational velocity
$\omega_{r}$ | Reference rotational velocity
$u$ | Control information vector
$T_{s}$ | Sampling time
$T$ | time to trace complete reference track
$N_{timesteps}$ | Total number of timesteps
$k$ | Time step
$\epsilon$ | Position error
$x_{e}$ | Position error in x-direction
$y_{e}$ | Position error in y-direction
$\theta_{e}$ | Orientation error
$n_{ul}$ | Consecutive uplink channel outages
$\epsilon_{ul}$ | Error with uplink channel outages
$u_{ul}$ | Control inputs with uplink channel outages

###  V-B Impact of feedback control parameters on error convergence

To study the impact of feedback control parameters on the error convergence,
an error in y-direction, $y_{e}$ = 5 m is introduced. The controller generates
$\nu$ and $\omega$ according to (15). The parameter $1/K_{x}$ is the time
constant that directs the rate at which error decreases to 0. In the discrete
control, the parameter $K_{x}$ determines the number of steps required to
direct an AGV back on the reference track.

#### No limitation on the translational velocity $\nu$

The Fig. 3(a), shows the starting position of an AGV is $5\,\mathrm{m}$ away
from the reference position in y-direction at time step $k=1$. The Fig. 3(a),
shows the tracks followed by AGV when $K_{x}$ is increased from
$5\,\mathrm{/sec}$ to $250\,\mathrm{/sec}$. At lower $K_{x}$ more number of
steps are required for an AGV to return to the reference track. As $K_{x}$ is
increased to $25\,\mathrm{/sec}$, the convergence rate increases. On further
increasing the $K_{x}=250\,\mathrm{/sec}$, an AGV oscillate before returning
to the reference track. The optimal response of an AGV is with no oscillation
and higher rate of error convergence. The rate of convergence of y-directional
error for varying $K_{x}$ is shown in Fig.3(b). Furthermore, Fig. 3(c) shows
the required velocity at every time step to reduce the error at the rate
specified by $K_{x}$. The required $\nu=-25\,\mathrm{m/s}$, from time-step
$k=1$ to $k=20$, with $K_{x}=5\,\mathrm{/sec}$ is very high for an AGV
operating on shop floor. Application of such high velocities is not
practically feasible, although the error converges in less number of
timesteps. Therefore, we evaluate the behaviour of error convergence with
limited $\nu$.

#### Limitation on the translational velocity $\nu\leq 6\,\mathrm{m/s}$

The Fig. 3(d), Fig. 3(e) and Fig. 3(f), shows the AGV tracks, error
convergence and the translational velocity required to navigate an AGV back on
the reference track by driving the AGV with maximum permissible velocity of
$6\,\mathrm{m/s}$. Due to limitation on the AGV velocity, feedback parameter
$K_{x}$ does not have a substantial impact on the error convergence. The error
convergence with $K_{x}=25\,\mathrm{/sec}$ and $K_{x}=250\,\mathrm{/sec}$,
shows similar behaviour of error over time. The response of translational
velocity of an AGV is shown in Fig. 3(f). At lower $K_{x}$ the generated
control inputs, i.e. the $\nu$, gradually approaches the reference velocity.
It illustrates a case of over-damped response,where the AGV returns to the
reference track gradually and requires more number of time-steps. On contrary,
at higher $K_{x}=250\,\mathrm{/sec}$, $\nu$ shows under-damped response, it
converges by oscillating around the reference velocity, which is not the
optimal case. If the oscillations are higher, it takes more time to converge.
An optimal case is of critical damping i.e. $\nu$ converges with less number
of timesteps and without oscillation. The optimal convergence is realized at
$K_{x}=25\,\mathrm{/sec}$.

##  VI Conclusions

We consider a practical use-case of an edge cloud AGV control system. A
discretization process of a stable continuous time AGV control system is
presented. We evaluate the control rule, error dynamics and stability
criterion of a discrete cloud control AGV in presence of uplink channel
outages. The derived stability criterion shows that the stability of an AGV
control is dependent upon the number of consecutive uplink outages and the
Eigen values of control matrix $A$ (64). Furthermore, we evaluate optimal
feedback control parameters that increases the rate of error convergence. The
paper consider two scenarios to study the impact of feedback parameters on
error convergence; with no limitation on AGV velocity and with limited AGV
velocity to 6 m/s. The result reveals that the optimal feedback parameter is
chosen with critical damping, i.e. it shows no oscillation an higher rate of
convergence. For cloud control AGV the critical damping is achieved at
$K_{x}=25\,\mathrm{/sec}$. Moreover, the results reveal that the impact of
feedback control parameters is higher in case of no-limitation on the AGV
velocity. If the AGV velocity is limited, the rate of error convergence does
not vary significantly with varying $K_{x}$. This effect is seen due to
limitation on the control inputs i.e. AGV velocity applied to an AGV and the
optimal feedback parameters is chosen from the response of the control inputs.
The feedback parameter corresponding to fastest convergence of control inputs
to the reference velocity with no oscillation is the optimal parameter. The
paper investigate the impact of feedback parameter corresponding to an error
in y-direction. In future, the research can be extended to evaluate the
optimal feedback parameters for x-direction and the orientation of an AGV. The
impact of uplink outages on the error convergence can also be investigated.

## References

  * [1] S. Tayade, P. Rost, A. Maeder, and H. D. Schotten, “Device-centric energy optimization for edge cloud offloading,” in _IEEE Global communications conference (Globecom)_ , 2017.
  * [2] ——, “Delay constrained energy optimization for edge cloud offloading,” in _2018 IEEE International Conference on Communications Workshops (ICC Workshops)_ , 2018.
  * [3] A. Alvarez Aguirre, “Remote control and motion coordination of mobile robots,” Ph.D. dissertation, 2011.
  * [4] K. Kanjanawanishkul, M. Hofmeister, and A. Zell, “Coordinated path following for mobile robots,” in _Autonome Mobile Systeme 2009_. Springer Berlin Heidelberg, 2009.
  * [5] X. Xiang, L. Lapierre, B. Jouvencel, and O. Parodi, “Coordinated path following control of multiple wheeled mobile robots through decentralized speed adaptation,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2009.
  * [6] R. Olmi, C. Secchi, and C. Fantuzzi, “Coordination of multiple agv’s in an industrial application,” in _IEEE International Conference on Robotics and Automation_ , 2008.
  * [7] M. Gundall, C. Huber, P. Rost, R. Halfmann, and H. D. Schotten, “Integration of 5g with tsn as prerequisite for a highly flexible future industrial automation: Time synchronization based on ieee 802.1as,” in _2020 IEEE 46th Annual Conference of the IEEE Industrial Electronics Society (IECON), October 18-21, Singapore, Singapore_. IEEE, 10 2020.
  * [8] A. Fellan, C. Schellenberger, M. Zimmermann, and H. D. Schotten, “Enabling communication technologies for automated unmanned vehicles in industry 4.0,” in _2018 International Conference on Information and Communication Technology Convergence (ICTC)_ , 2018, pp. 171–176.
  * [9] B. Han, S. Yuan, Z. Jiang, Y. Zhu, and H. D. Schotten, “Robustness analysis of networked control systems with aging status,” in _IEEE INFOCOM 2020 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , 2020, pp. 1360–1361.
  * [10] Y. Kanayama, Y. Kimura, F. Miyazaki, and T. Noguchi, “A stable tracking control method for an autonomous mobile robot,” in _Proceedings., IEEE International Conference on Robotics and Automation_ , 1990, pp. 384–389 vol.1.
  * [11] S. Y. Nof, _Springer handbook of automation_. Springer Science & Business Media, 2009.
  * [12] X. Liu and A. Goldsmith, _Cross-layer Design of Control over Wireless Networks_ , 01 2005, pp. 111–136.
  * [13] S. Tatikonda and S. Mitter, “Control over noisy channels,” _IEEE Transactions on Automatic Control_ , 2004.
  * [14] S. Tatikonda, A. Sahai, and S. Mitter, “Stochastic linear control over a communication channel,” _IEEE Transactions on Automatic Control_ , 2004.
  * [15] S. Tayade, P. Rost, A. Maeder, and H. D. Schotten, “Cloud control agv over rayleigh fading channel - the faster the better,” in _SCC 2019; 12th International ITG Conference on Systems, Communications and Coding_ , Feb 2019, pp. 1–6.
  * [16] ——, “Impact of short blocklength coding on stability of an agv control system in industry 4.0,” in _2020 IEEE International Conference on Communications Workshops (ICC Workshops)_ , 2020, pp. 1–6.
  * [17] K. J. A. Astroem and B. Wittenmark, _Computer-controlled Systems: Theory and Design_. Prentice-Hall, Inc., 1990\.