# On the design of autonomous agents from multiple data sources

Émiland Garrabé and Giovanni Russo∗ ∗ E. Garrabé (email<EMAIL_ADDRESS>and G. Russo (email<EMAIL_ADDRESS>are with the Department of
Information and Electrical Engineering and Applied Mathematics (DIEM) at the
University of Salerno, 84084, Salerno, Italy.

###### Abstract

This paper is concerned with the problem of designing agents able to
dynamically select information from multiple data sources in order to tackle
tasks that involve tracking a target behavior while optimizing a reward. We
formulate this problem as a data-driven optimal control problem with integer
decision variables and give an explicit expression for its solution. The
solution determines how (and when) the data from the sources should be used by
the agent. We also formalize a notion of agent’s regret and, by relaxing the
problem, give a regret upper bound. Simulations complement the results.

##  I INTRODUCTION

The problem of designing agents able to tackle tasks by using data coming from
multiple sources is attracting much research attention. Learning algorithms
with multiple simulators in the loop [1], robots navigating via maps from
other robots [2] and the sharing economy [3] are a few examples that involve
making decisions based on the crowdsourcing of information [4]. For these
crowdsourcing agents, which craft their actions from mutually excluding
options, a number of key questions arise: is it possible to optimally
orchestrate the use of the sources? And can performance be rigorously
quantified? Positively answering these questions would have intriguing
implications, highlighting the possibility of designing agents that can
optimally perform tasks by re-using different datasets. In this context, this
paper presents an optimal decision making strategy that allows an agent to
switch between the sources in order to tackle certain tasks. Moreover, we
define and quantify the regret of the agent that uses our strategy.

### Related Work

in [4], we formalized the so-called crowdsourcing control problem (CCP) as a
finite-horizon data-driven optimal control problem. Results on data-driven
control include [5, 6, 7], which take a behavioral systems perspective, [8],
that presents an approach to compute minimum-energy controls for linear
systems, [9, 10, 11] which introduce algorithms inspired from MPC, [12], where
a data-driven design approach is devised for stabilizable Lipschitz systems.
We also recall here [13] which, by leveraging an approach that can be traced
back to [14], seeks to synthesize control policies from demonstration datasets
for systems with actuation constraints and the recent [15], which discusses
some of the key challenges of extracting control relevant information from
large amounts of data. Recently, it has been shown that data-driven control
can benefit from the use of properly patched data from multiple sources [16].
In the context of learning systems, a Multi-Fidelity Reinforcement Learning
(RL) algorithm, enabling an agent to build a policy by sampling from different
datasets, has been introduced/analyzed in [1] and, in e.g. [17, 18], it has
been also shown that state-of-the-art RL algorithms can improve their
performance if these are trained on multiple, heterogeneous, offline datasets.

### Contributions

we consider the problem of designing agents able to dynamically choose between
multiple sources in order to fulfill tasks that involve tracking a target
behavior while optimizing a reward function. We formulate this problem as a
data-driven, integer, optimal control problem. For this problem: (i) we
formalize the problem as a data-driven control problem. This leads to an
optimal control formulation with integer decision variables; (ii) by relaxing
the problem, we find an explicit expression for its optimal solution. The
solution determines, at each time step, which source should be picked by the
agent; (iii) finally, we formalize a notion of regret w.r.t. an oracle and
give a regret upper bound. The oracle is obtained by relaxing the original
control problem. This leads to an infinite-dimensional convex problem that we
also solve explicitly. Our results are complemented via simulations.

While the results of this paper are inspired by the ones presented in [4], our
paper extends this in several ways. First, differently from [4], here the
formalization of the control problem leads to study an optimization problem
with integer decision variables. Second, we find an optimal solution for the
problem considered here and actually prove that this solution coincides with a
non-optimal solution from [4]. Moreover, we introduce a notion of regret and
give a regret upper bound. This leads to an infinite-dimensional convex
problem that was not considered in [4] and, as a result, our regret analysis
cannot obtained with the results from [4].

### Mathematical Preliminaries

sets are in calligraphic and vectors in bold. Consider the measurable space
$(\mathcal{X},\mathcal{F}_{x})$, where $\mathcal{X}\subseteq\mathbb{R}^{d}$
($\mathcal{X}\subseteq\mathbb{Z}^{d}$) and $\mathcal{F}_{x}$ is a
$\sigma$-algebra on $\mathcal{X}$. We denote a random variable on
$(\mathcal{X},\mathcal{F}_{x})$ by $\mathbf{X}$ and its realization by
$\mathbf{x}$. The probability density (mass) function or pdf (pmf) of a
continuous (discrete) $\mathbf{X}$ is denoted by $p(\mathbf{x})$ and
$\mathcal{D}$ is the convex subset of pdfs/pmfs. When we take the integrals
(sums) involving pdfs (pmfs) we always assume that these exist. The
expectation of a function $\mathbf{h}(\cdot)$ of the continuous variable
$\mathbf{X}$ is
$\mathbb{E}_{{p}}[\mathbf{h}(\mathbf{X})]:=\int\mathbf{h}(\mathbf{x})p(\mathbf{x})d\mathbf{x}$,
where the integral is over the support of $p(\mathbf{x})$ \- for discrete
variables the integral is replaced with the sum. The joint pdf (pmf) of two
random variables, $\mathbf{X}_{1}$ and $\mathbf{X}_{2}$, is
$p(\mathbf{x}_{1},\mathbf{x}_{2})$ and the conditional pdf (pmf) of
$\mathbf{X}_{1}$ w.r.t. $\mathbf{X}_{2}$ is
$p\left(\mathbf{x}_{1}|\mathbf{x}_{2}\right)$. Countable sets are denoted by
$\\{w_{k}\\}_{k_{1}:k_{n}}$, where $w_{k}$ is a set element and $k_{1}:k_{n}$
is the closed set of consecutive integers between index $k_{1}$ and $k_{n}$.
We also let $p_{0:N}:=p(\mathbf{x}_{0},\ldots,\mathbf{x}_{N})$,
$p_{k:k}:=p_{k}(\mathbf{x}_{k})$ and
$p_{k|k-1}:=p_{k}(\mathbf{x}_{k}|\bf{x}_{k-1})$. Also: (i) functionals are
denoted by capital calligraphic characters with arguments in curly brackets;
(ii) the internal product between tensors is $\langle\cdot,\cdot\rangle$;
(iii) likelihoods have the arguments in square brackets. The Kullback-Leibler
(KL) divergence of $p:=p(\mathbf{x})$ w.r.t. $q:=q(\mathbf{x})$, with $p$
absolutely continuous with respect to $q$, is
$\mathcal{D}_{\text{KL}}\left(p||q\right):=\int
p\;\ln\left({p}/{q}\right)\,d\mathbf{x}$ (for discrete variables the integral
is replaced by the sum). For pdfs/pmfs,
$\mathcal{D}_{\text{KL}}\left(p^{(1)}||p^{(2)}\right)$ measures the proximity
of the pair $p^{(1)}$, $p^{(2)}$.

##  II The set-up

The agent seeks to craft its behavior by gathering data from a number of
sources in order to fulfill a task that involves tracking a target/desired
behavior while, at the same time, maximizing a reward function. In what
follows, $\mathbf{x}_{k}\in\mathcal{X}$ is the state at time step $k$,
$\mathbf{d}_{0:N}:=\\{\mathbf{x}_{0},\ldots,\mathbf{x}_{N}\\}$ is the dataset
of the target state trajectory for the agent over $\mathcal{T}:={0:N}$ and
$p(\mathbf{d}_{0:N})=p(\mathbf{x}_{0},\ldots,\mathbf{x}_{N})$. Now, by making
the standard assumption that the Markov property holds, we have:

$\begin{split}p_{0:N}&=p_{0:0}\prod_{k=1}^{N}p_{k|k-1}=:p_{0:0}p_{1:N|0},\end{split}$
(1)

which is termed as target behavior. As noted in [4], the agent behavior can be
designed by designing the joint pdf/pmf
$\pi(\mathbf{x}_{0},\ldots,\mathbf{x}_{N})$. By letting
$\pi_{k|k-1}:=\pi_{k}(\mathbf{x}_{k}|\mathbf{x}_{k-1})$ we have:

$\begin{split}\pi_{0:N}&=\pi_{0:0}\prod_{k=1}^{N}\pi_{k|k-1}=:\pi_{0:0}\pi_{1:N|0}.\end{split}$
(2)

That is, the agent behavior $\pi_{0:N}$ can be designed by shaping the
$\pi_{k|k-1}$’s. We let $r_{k}:\mathcal{X}\rightarrow\mathbb{R}$ be the reward
obtained by the agent for being in state $\mathbf{x}_{k}$ at time $k$. Hence,
the expected reward for the agent that follows the behavior in (2) is
$\mathbb{E}_{\pi_{k-1:k-1}}\left[\tilde{r}_{k}(\mathbf{X}_{k-1})\right]:=\mathbb{E}_{\pi_{k-1:k-1}}\left[\mathbb{E}_{\pi_{k|k-1}}\left[r_{k}(\mathbf{X}_{k})\right]\right]=\mathbb{E}_{\pi_{k:k}}\left[r_{k}(\mathbf{X}_{k})\right]$.
We let $\mathcal{S}:={1:S}$ be the set of sources that the agent can use and
$\left\\{\pi_{k|k-1}^{(i)}\right\\}_{1:N}$ be the sequence of pdfs/pmfs (i.e.
the behavior) provided by the $i$-th source. While the sources do not know the
target behavior/reward of the agent, we make the following assumption, which,
as discussed in [4], is not restrictive in practice:

###### Assumption 1

$\mathcal{D}_{\text{KL}}(\pi_{k|k-1}^{(i)}||p_{k|k-1})<+\infty$, $\forall k$,
$\forall i\in\mathcal{S}$.

###### Remark 1

situations where the $\pi_{k|k-1}^{(i)}$’s are available to the agent
naturally arise in a number of applications. For example, within the multi-
fidelity RL framework, the sources might be simulators available to the agent
and each $\pi_{k|k-1}^{(i)}$ might be given by the output of the $i$-th
simulator.

###### Remark 2

in what follows, we use $p_{1:n|0}$ and $\pi_{1:n|0}$ for
$p(\mathbf{x}_{1},\ldots,\mathbf{x}_{n}|\mathbf{x}_{0})$ and
$\pi(\mathbf{x}_{1},\ldots,\mathbf{x}_{n}|\mathbf{x}_{0})$ to make equations
more compact.

##  III The control problem and a link with the CCP

Let $\alpha_{k}^{(i)}$, $i\in\mathcal{S}$, be a weight and
$\boldsymbol{\alpha}_{k}$ be the stack of the $\alpha_{k}^{(i)}$’s. Then, the
problem of designing agents able to dynamically choose between different
sources in order to track their own target behavior while optimizing the
agent-specific reward can be recast via the following

###### Problem 1

find the sequence ${\left\\{\boldsymbol{\alpha}_{k}^{\ast}\right\\}_{1:N}}$
solving

$\displaystyle\underset{\left\\{\boldsymbol{\alpha}_{k}\right\\}_{1:N}}{\text{min}}$
$\displaystyle\mathcal{D}_{\text{KL}}\left(\pi_{1:N|0}||p_{1:N|0}\right)-\sum_{k=1}^{N}\mathbb{E}_{\pi_{k-1:k-1}}\left[\tilde{r}_{k}(\mathbf{X}_{k-1})\right]$
(3) $\displaystyle s.t.$ $\displaystyle\
\pi_{k|k-1}=\sum_{i\in\mathcal{S}}\alpha_{k}^{(i)}\pi_{k|k-1}^{(i)},\ \ \
\forall k$ $\displaystyle\sum_{i\in\mathcal{S}}\alpha_{k}^{(i)}=1,\ \
\alpha_{k}^{(i)}\in\\{0,1\\},\ \ \forall k.$

In Problem 1 the constraints formalize the fact that, at each $k$, the agent
picks the behavior from one source. The first term in the cost quantifies the
discrepancy between the agent behavior and the target: hence, minimizing this
term amounts to tracking the target behavior. Instead, minimizing the second
term in the cost implies maximizing the agent’s expected reward.

###### Remark 3

Problem 1 captures situations where an agent needs to pick between (rather
than combine) multiple sources. These situations arise in a number of
applications, such as multi-fidelity RL where the agents needs to make its
decision based on the output of different simulators.

###### Definition 1

$\left\\{{\pi}^{\ast}_{k|k-1}\right\\}_{1:N}$ is an optimal solution of
Problem 1 if
${\pi}^{\ast}_{k|k-1}:=\sum_{i\in\mathcal{S}}{\alpha_{k}^{(i)}}^{\ast}\pi_{k|k-1}^{(i)}$,
with the weights being an optimal solution of (3).

We now state the CCP from [4] in terms of Problem 1.

###### Problem 2

the CCP is the relaxation of Problem 1 obtained by replacing, $\forall k$,
$\alpha_{k}^{(i)}\in\\{0,1\\}$ with $\alpha_{k}^{(i)}\geq 0$.

In what follows, we also make use of the following definition

###### Definition 2

$\left\\{\tilde{\pi}_{k|k-1}\right\\}_{1:N}$ is an approximate solution of the
CCP if
$\tilde{\pi}_{k|k-1}:=\sum_{i\in\mathcal{S}}{\tilde{\alpha}_{k}^{(i)}}\pi_{k|k-1}^{(i)}$,
with the weights being the solution of a problem having the same constraints
as the CCP and a cost upper-bounding the cost of the CCP.

Finding the optimal solution of the CCP would involve computing, at each $k$,
$\mathcal{D}_{\text{KL}}(\sum_{i\in\mathcal{S}}\alpha_{k}^{(i)}\pi^{(i)}_{k|k-1}||p_{k|k-1})$.
Even for Gaussians, this computation is analytically intractable and
computationally expensive [19, 20]. Hence, in [4] an approximate solution for
the CCP is obtained. Namely:

###### Lemma 1

consider the CCP. Then $\left\\{\tilde{\pi}_{k|k-1}\right\\}_{1:N}$, with
$\tilde{\pi}_{k|k-1}=\sum_{i\in\mathcal{S}}{\tilde{\alpha}_{k}^{(i)}}\pi_{k|k-1}^{(i)}$
and

$\displaystyle\tilde{\boldsymbol{\alpha}}_{k}\in\underset{\boldsymbol{\alpha}_{k}}{\text{arg
min}}$ $\displaystyle\ \
\mathbf{a}_{k}^{T}(\mathbf{x}_{k-1})\boldsymbol{\alpha}_{k}$ (4)
$\displaystyle s.t.$ $\displaystyle\
\sum_{i\in\mathcal{S}}\alpha_{k}^{(i)}=1,\ \alpha_{k}^{(i)}\geq 0,$

is an approximate solution of the CCP. In (4),
$\mathbf{a}_{k}(\mathbf{x}_{k-1}):=[a_{k}^{(1)}(\mathbf{x}_{k-1}),\ldots,a_{k}^{(S)}(\mathbf{x}_{k-1})]^{T}$,
while
${a}_{k}^{(i)}(\mathbf{x}_{k-1}):=\mathcal{D}_{\text{KL}}\left(\pi_{k|k-1}^{(i)}||p_{k|k-1}\right)-\mathbb{E}_{\pi^{(i)}_{k|k-1}}\left[\bar{r}_{k}({\mathbf{X}_{k}})\right]$,
and $\bar{r}_{k}({\mathbf{X}_{k}})$ is obtained via backward recursion as

$\begin{split}&\bar{r}_{k}(\mathbf{x}_{k}):=r_{k}(\mathbf{x}_{k})+\hat{r}_{k}(\mathbf{x}_{k}),\\\
&\hat{r}_{k}(\mathbf{x}_{k})=-\mathbf{a}^{T}_{k+1}(\mathbf{x}_{k})\tilde{\boldsymbol{\alpha}}_{k+1},\
\ \hat{r}_{N}(\mathbf{x}_{N})=0.\end{split}$ (5)

###### Remark 4

the solution of (4) is determined, $\forall k$, based on
$\mathbf{a}_{k}(\mathbf{x}_{k-1})$ and hence $\tilde{\boldsymbol{\alpha}}_{k}$
depends on $\mathbf{x}_{k-1}$. This dependency is omitted in what follows for
notational convenience.

##  IV Finding a solution to Problem 1

We now show that the non-optimal solution to the CCP from Lemma 1 is actually
the optimal solution for Prob. 1.

###### Theorem 1

the approximate solution of the CCP given in Lemma 1 is also the optimal
solution of Problem 1.

###### Proof:

we first (Step $1$) characterize the optimal solution of Problem 1. Then (Step
$2$) we show that the approximate solution of the CCP given by Lemma 1 must
necessarily coincide with the optimal solution of Problem 1.

Step $1$. In what follows we make use of the shorthand notation
$\mathcal{J}_{n}(\pi_{1:n-1|0},p_{1:n-1|0})$ to denote
$\mathcal{D}_{\text{KL}}\left(\pi_{1:n-1|0}||p_{1:n-1|0}\right)-\sum_{k=1}^{n-1}\mathbb{E}_{\pi_{k-1:k-1}}\left[\tilde{r}_{k}(\mathbf{X}_{k-1})\right]$.
The chain rule for pdfs/pmfs [4], the linearity of the expectation and the
fact that $\mathcal{D}_{\text{KL}}\left(\pi_{N|N-1}||p_{N|N-1}\right)$ depends
only on $\mathbf{x}_{N-1}$ imply that the cost in (3) can be re-written as

$\displaystyle\mathcal{J}_{N}(\pi_{1:N-1|0},p_{1:N-1|0})+\mathbb{E}_{\pi_{1:N-1|0}}\left[\mathcal{D}_{\text{KL}}\left(\pi_{N|N-1}||p_{N|N-1}\right)\right]-\mathbb{E}_{\pi_{N-1:N-1}}\left[\tilde{r}_{N}(\mathbf{X}_{N-1})\right]$
$\displaystyle=\mathcal{J}_{N}(\pi_{1:N-1|0},p_{1:N-1|0})+\mathbb{E}_{\pi_{N-1:N-1}}\left[\mathcal{D}_{\text{KL}}\left(\pi_{N|N-1}||p_{N|N-1}\right)\right]-\mathbb{E}_{\pi_{N-1:N-1}}\left[\tilde{r}_{N}(\mathbf{X}_{N-1})\right]$
$\displaystyle=\mathcal{J}_{N}(\pi_{1:N-1|0},p_{1:N-1|0})+\mathbb{E}_{\pi_{N-1:N-1}}\left[\mathcal{D}_{\text{KL}}\left(\pi_{N|N-1}||p_{N|N-1}\right)-\tilde{r}_{N}(\mathbf{X}_{N-1})\right].$

Hence, (3) can be formulated as the sum of two sub-problems:

$\displaystyle\underset{\left\\{\boldsymbol{\alpha}_{k}\right\\}_{1:N-1}}{\text{min}}$
$\displaystyle\mathcal{J}_{N}(\pi_{1:N-1|0},p_{1:N-1|0})$ (6) $\displaystyle
s.t.$ $\displaystyle\
\pi_{k|k-1}=\sum_{i\in\mathcal{S}}\alpha_{k}^{(i)}\pi_{k|k-1}^{(i)},\ k\in
1:N-1$ $\displaystyle\sum_{i\in\mathcal{S}}\alpha_{k}^{(i)}=1,\
\alpha_{k}^{(i)}\in\\{0,1\\},\ k\in 1:N-1,$

and, by letting

$c_{N}(\mathbf{x}_{N-1}):=\mathcal{D}_{\text{KL}}\left(\pi_{N|N-1}||p_{N|N-1}\right)-\mathbb{E}_{\pi_{N|N-1}}\left[\bar{r}_{N}(\mathbf{X}_{N})\right],$

where we set $\bar{r}_{N}(\mathbf{x}_{N})=r_{N}(\mathbf{x}_{N})$:

$\displaystyle\underset{\boldsymbol{\alpha}_{N}}{\text{min}}$ $\displaystyle\
\mathbb{E}_{\pi_{N-1:N-1}}\left[c_{N}(\mathbf{X}_{N-1})\right]$ (7)
$\displaystyle s.t.$ $\displaystyle\
\pi_{N|N-1}=\sum_{i\in\mathcal{S}}\alpha_{N}^{(i)}\pi_{N|N-1}^{(i)}$
$\displaystyle\sum_{i\in\mathcal{S}}\alpha_{N}^{(i)}=1,\
\alpha_{N}^{(i)}\in\\{0,1\\}.$

That is, Problem 1 can be approached by first solving (7) and then by taking
into account its minimum to solve (6). Also, the optimal cost of (7) is
$\mathbb{E}_{\pi_{N-1:N-1}}\left[c_{N}^{\ast}(\bf{X}_{N-1}))\right]$, where
$c_{N}^{\ast}(\bf{x}_{N-1})$ is the optimal cost obtained by solving:

$\displaystyle\underset{\boldsymbol{\alpha}_{N}}{\text{min}}$ $\displaystyle\
c_{N}(\mathbf{x}_{N-1})$ (8) $\displaystyle s.t.$ $\displaystyle\
\pi_{N|N-1}=\sum_{i\in\mathcal{S}}\alpha_{N}^{(i)}\pi_{N|N-1}^{(i)}$
$\displaystyle\sum_{i\in\mathcal{S}}\alpha_{N}^{(i)}=1,\
\alpha_{N}^{(i)}\in\\{0,1\\}.$

The constraints of (8) imply that its optimal solution is a vector, say
$\boldsymbol{\alpha}_{N}^{\ast}$, having all of its elements equal to $0$
except one element, say $j_{N}^{\ast}$, which is equal to $1$. Moreover, by
evaluating the cost of (8) at each feasible solution, we have that
$j_{N}^{\ast}\in{\text{arg min}}_{j\in\mathcal{S}}\
{a}_{N}^{(j)}(\mathbf{x}_{N-1})$, where we used the definition of
${a}_{k}^{(j)}(\mathbf{x}_{k-1})$ given in Lemma 1. The cost of the sub-
problem in (7) is then
$\mathbb{E}_{\pi_{N-1:N-1}}\left[\mathbf{a}_{N}^{T}(\mathbf{X}_{N-1})\boldsymbol{\alpha}_{N}^{\ast}\right]$,
where the vector $\mathbf{a}_{N}(\mathbf{x}_{N-1})$ is defined as in Lemma 1.
Now, the fact that the original problem has been reformulated as the sum of
the two sub-problems (6) and (7) implies that the cost of Problem 1 is equal
to

$\mathcal{J}_{N}(\pi_{1:N-1|0},p_{1:N-1|0})+\mathbb{E}_{\pi_{N-1:N-1}}\left[\mathbf{a}_{N}^{T}(\mathbf{X_{N-1}})\boldsymbol{\alpha}_{N}^{\ast}\right],$

which, by means of the chain rule for pdfs/pmfs and the definition of
expectation, can be shown to be equal to

$\displaystyle\mathcal{J}_{N}(\pi_{1:N-1|0},p_{1:N-1|0})+\mathbb{E}_{\pi_{N-2:N-2}}\left[\mathbb{E}_{\pi_{N-1|N-2}}\left[\mathbf{a}_{N}^{T}(\mathbf{X_{N-1}})\boldsymbol{\alpha}_{N}^{\ast}\right]\right]$
$\displaystyle=\mathcal{J}_{N-1}(\pi_{1:N-2|0},p_{1:N-2|0})+\mathbb{E}_{\pi_{1:N-2|0}}\left[\mathcal{D}_{\text{KL}}(\pi_{N-1|N-2}||p_{N-1|N-2})\right]$
$\displaystyle-\mathbb{E}_{\pi_{N-2:N-2}}\left[\tilde{r}_{N-1}(\mathbf{X}_{N-2})\right]+\mathbb{E}_{\pi_{N-2:N-2}}\left[\mathbb{E}_{\pi_{N-1|N-2}}\left[\mathbf{a}_{N}^{T}(\mathbf{X_{N-1}})\boldsymbol{\alpha}_{N}^{\ast}\right]\right]$
$\displaystyle=\mathcal{J}_{N-1}(\pi_{1:N-2|0},p_{1:N-2|0})+\mathbb{E}_{\pi_{N-2:N-2}}\left[\mathcal{D}_{\text{KL}}(\pi_{N-1|N-2}||p_{N-1|N-2})\right]$
$\displaystyle-\mathbb{E}_{\pi_{N-2:N-2}}\left[\mathbb{E}_{\pi_{N-1|N-2}}\left[r_{N-1}(\mathbf{X}_{N-1})-\mathbf{a}_{N}^{T}(\mathbf{X_{N-1}})\boldsymbol{\alpha}_{N}^{\ast}\right]\right].$

As a result, the problem can be split as the sum of:

$\displaystyle\underset{\left\\{\boldsymbol{\alpha}_{k}\right\\}_{1:N-2}}{\text{min}}$
$\displaystyle\mathcal{J}_{N-1}(\pi_{1:N-2|0},p_{1:N-2|0})$ (9a)
$\displaystyle s.t.$ $\displaystyle\
\pi_{k|k-1}=\sum_{i\in\mathcal{S}}\alpha_{k}^{(i)}\pi_{k|k-1}^{(i)},\ k\in
1:N-2$
$\displaystyle\sum_{i\in\mathcal{S}}\alpha_{k}^{(i)}=1,\alpha_{k}^{(i)}\in\\{0,1\\},k\in
1:N-2,$ and $\displaystyle\underset{\boldsymbol{\alpha}_{N-1}}{\text{min}}$
$\displaystyle\
\mathbb{E}_{\pi_{N-2:N-2}}\left[c_{N-1}(\mathbf{X}_{N-2})\right]$ (9b)
$\displaystyle s.t.$ $\displaystyle\
\pi_{N-1|N-2}=\sum_{i\in\mathcal{S}}\alpha_{N-1}^{(i)}\pi_{N-1|N-2}^{(i)}$
$\displaystyle\sum_{i\in\mathcal{S}}\alpha_{N-1}^{(i)}=1,\ \
\alpha_{N-1}^{(i)}\in\\{0,1\\},$

with

$\displaystyle
c_{N-1}(\mathbf{x}_{N-2}):=\mathcal{D}_{\text{KL}}\left(\pi_{N-1|N-2}||p_{N-1|N-2}\right)-\mathbb{E}_{\pi_{N-1|N-2}}\left[\bar{r}_{N-1}(\mathbf{X}_{N-1})\right],$
$\displaystyle\bar{r}_{N-1}(\mathbf{x}_{N-1})={r}_{N-1}(\mathbf{x}_{N-1})+\hat{r}_{N-1}(\mathbf{x}_{N-1})$
$\displaystyle\hat{r}_{N-1}(\mathbf{x}_{N-1}):=-\mathbf{a}_{N}^{T}(\mathbf{x}_{N-1})\boldsymbol{\alpha}_{N}^{\ast}.$

Again, the optimal solution of (9b) is the vector
$\boldsymbol{\alpha}_{N-1}^{\ast}$ having all of its elements equal to $0$
except element $j_{N-1}^{\ast}$, which is equal to $1$. Moreover, this time we
have $j_{N-1}^{\ast}\in{\text{arg min}}_{j\in\mathcal{S}}\
{a}_{N-1}^{(j)}(\mathbf{x}_{N-2})$, and the cost of (9b) is given by
$\mathbb{E}_{\pi_{N-2:N-2}}\left[\mathbf{a}^{T}_{N-1}(\mathbf{X}_{N-2})\boldsymbol{\alpha}_{N-1}^{\ast}\right]$.
By iterating the above arguments, we find that, $\forall k\in 1:N-2$, Problem
1 can always be split as the sum of two sub-problems, where the problem for
the last $k$ can be solved by finding:

$\displaystyle\underset{\boldsymbol{\alpha}_{k}}{\text{min}}$ $\displaystyle\
\mathcal{D}_{\text{KL}}\left(\pi_{k|k-1}||p_{k|k-1}\right)-\mathbb{E}_{\pi_{k|k-1}}\left[\bar{r}_{k}(\mathbf{X}_{k})\right]$
$\displaystyle s.t.$ $\displaystyle\
\pi_{k|k-1}=\sum_{i\in\mathcal{S}}\alpha_{k}^{(i)}\pi_{k|k-1}^{(i)}$
$\displaystyle\sum_{i\in\mathcal{S}}\alpha_{k}^{(i)}=1,\ \
\alpha_{k}^{(i)}\in\\{0,1\\},$

with
$\bar{r}_{k}(\mathbf{x}_{k}):=r_{k}(\mathbf{x}_{k})+\hat{r}_{k}(\mathbf{x}_{k})$
and
$\hat{r}_{k}(\mathbf{x}_{k}):=-\mathbf{a}^{T}_{k+1}(\mathbf{x}_{k})\boldsymbol{\alpha}_{k+1}^{\ast}$.
Hence, the optimal solution of Problem 1 is, $\forall k$, the vector
$\boldsymbol{\alpha}_{k}^{\ast}$ that has all of its elements equal to $0$,
except one, say $j_{k}^{\ast}$, equal to $1$. Moreover, at time step $k$:

$\displaystyle j_{k}^{\ast}\in\underset{j\in\mathcal{S}}{\text{arg min}}$
$\displaystyle\ {a}_{k}^{(j)}(\mathbf{x}_{k-1}).$ (10)

Step $2$. We now consider the approximate solution from Lemma 1, obtained by
solving, at each $k$, the problem in (4). Note that this is a linear problem
with the standard simplex as feasibility domain. Also, note that the vertices
of the standard simplex all have entries equal to $0$, except one equal to
$1$. Hence, the solution of such a problem at each $k$ is the vector,
$\tilde{\boldsymbol{\alpha}}_{k}$ having all of its elements equal to $0$,
except element $j_{k}$ which is equal to $1$. Moreover, the element $j_{k}$
solving the problem in (4) corresponds to the index of the smallest element in
the vector $\mathbf{a}_{k}(\mathbf{x}_{k-1})$. This is, however, given by (10)
and hence, $\forall k$, $j_{k}=j_{k}^{\ast}$. ∎

##  V Regret analysis

We define the regret of an agent that follows
$\left\\{\tilde{\pi}_{k|k-1}\right\\}_{1:N}$:

###### Definition 3

consider the cost functional
$\mathcal{C}\left\\{\pi_{1:N|0}\right\\}:=\mathcal{D}_{\text{KL}}\left(\pi_{1:N|0}||p_{1:N|0}\right)-\sum_{k=1}^{N}\mathbb{E}_{\pi_{k-1:k-1}}\left[\tilde{r}_{k}(\mathbf{X}_{k-1})\right]$.
Then, the regret of the agent is
$\bar{R}_{1:N|0}:=\mathcal{C}\left\\{\tilde{\pi}_{1:N|0}\right\\}-\mathcal{C}\left\\{\bar{\pi}_{1:N|0}\right\\}$.

In the above definition, $\bar{\pi}_{1:N|0}$ is the solution to the following

###### Problem 3

find the sequence $\\{\bar{\pi}_{k|k-1}\\}_{1:N}$ solving

$\displaystyle\underset{\left\\{\pi_{k|k-1}\right\\}_{1:N}}{\text{min}}$
$\displaystyle\mathcal{D}_{\text{KL}}\left(\pi_{1:N|0}||p_{1:N|0}\right)-\sum_{k=1}^{N}\mathbb{E}_{\pi_{k-1:k-1}}\left[\tilde{r}_{k}(\mathbf{X}_{k-1})\right]$
(11) $\displaystyle s.t.$ $\displaystyle\ \pi_{k|k-1}\in\mathcal{D},\ \
\forall k.$

Problem 3 is an infinite-dimensional relaxation of Problem 1 and its solution
is an oracle for such a problem.

###### Definition 4

$\bar{\pi}_{0:N}:=\pi_{0:0}\prod_{k=1}^{N}\bar{\pi}_{k|k-1}=\pi_{0:0}\bar{\pi}_{1:N|0}$,
is an oracle for Problem 1 if
$\mathcal{C}\left\\{\bar{\pi}_{1:N|0}\right\\}\leq\mathcal{C}\left\\{{\hat{\pi}}_{1:N|0}\right\\}$,
$\forall\hat{\pi}_{1:N|0}\in\mathcal{D}$.

That is, by definition, no agent can obtain a better (i.e. lower) cost than
the oracle. The next result gives an explicit expression for the oracle.

###### Lemma 2

the solution of Problem 3 is $\left\\{\bar{\pi}_{k|k-1}\right\\}_{1:N}$, with

$\bar{\pi}_{k|k-1}=\frac{p_{k|k-1}\exp\left(\bar{\rho}_{k}(\mathbf{x}_{k})\right)}{\int
p_{k|k-1}\exp\left(\bar{\rho}_{k}(\mathbf{x}_{k})\right)d\mathbf{x}_{k}},$
(12)

where
$\bar{\rho}_{k}(\mathbf{x}_{k}):={r}_{k}(\mathbf{x}_{k})+\hat{\rho}_{k}(\mathbf{x}_{k})$,
and

$\begin{split}&\hat{\rho}_{k}(\mathbf{x}_{k}):=\ln\mathbb{E}_{p_{k+1|k}}\left[\exp(\bar{\rho}_{k+1}(\mathbf{X}_{k+1}))\right],\\\
&\bar{\rho}_{N+1}(\mathbf{x}_{N+1})=0.\end{split}$ (13)

###### Proof:

See the Appendix. ∎

###### Remark 5

Lemma 1 and Prop. 1 (see next) are stated for pdfs. These results can also be
stated for pmfs by replacing integrals with sums (statements omitted here for
brevity).

### Regret bound

we now give an upper bound for $\bar{R}_{1:N|0}$. In doing so, we make use of
the following set of assumptions.

###### Assumption 2

for each $i$, $\left\\{\pi_{k|k-1}^{(i)}\right\\}_{1:N}$ is the solution of

$\displaystyle\underset{\left\\{\pi_{k|k-1}\right\\}_{1:N}}{\text{min}}$
$\displaystyle\mathcal{D}_{\text{KL}}\left(\pi_{1:N|0}||p_{1:N|0}^{(i)}\right)-\sum_{k=1}^{N}\mathbb{E}_{\pi_{k-1:k-1}}\left[\tilde{r}^{(i)}_{k}(\mathbf{X}_{k-1})\right]$
(14) $\displaystyle s.t.$ $\displaystyle\ \pi_{k|k-1}\in\mathcal{D},\ \
\forall k,$

where $p_{1:N|0}^{(i)}:=\prod_{k=1}^{N}p^{(i)}_{k|k-1}$ and
$\tilde{r}^{(i)}_{k}(\mathbf{x}_{k-1})=\mathbb{E}_{\pi_{k|k-1}}\left[r_{k}^{(i)}(\mathbf{X}_{k})\right]$
are target and reward of the $i$-th source.

Assumption 2 states that the behavior of the sources is optimal for a task,
which is (in general) different from that of the agent (the cost in (14) is
different from the cost in Prob. 1). Any behavior can be formally obtained as
a solution of a problem of the form of (14). Indeed, let
$\pi_{1:N|0}^{(i)}=\prod_{k=1}^{N}\pi_{k|k-1}^{(i)}$. Then, this behavior is
the solution of a problem of the form of (14) having
$p_{1:N|0}^{(i)}=\pi_{1:N|0}^{(i)}$ and zero reward. Assumption 2 and Lemma 2
imply that the behavior provided by the $i$-th source is of the form:

$\begin{split}\pi_{1:N|0}^{(i)}&=\prod_{k=1}^{N}\frac{p_{k|k-1}^{(i)}\exp\left(\bar{r}_{k}^{(i)}(\mathbf{x}_{k})\right)}{\int
p_{k|k-1}^{(i)}\exp\left(\bar{r}_{k}^{(i)}(\mathbf{x}_{k})\right)d\mathbf{x}_{k}},\end{split}$
(15)

with $\bar{r}_{N+1}^{(i)}(\mathbf{x}_{N+1})=0$ and:

$\begin{split}&\bar{r}_{k}^{(i)}(\mathbf{x}_{k})=r_{k}^{(i)}(\mathbf{x}_{k})+\hat{r}_{k}^{(i)}(\mathbf{x}_{k}),\\\
&\hat{r}_{k}^{(i)}(\mathbf{x}_{k})=\ln\mathbb{E}_{p_{k+1|k}^{(i)}}\left[\exp(\bar{r}_{k+1}^{(i)}(\mathbf{X}_{k+1}))\right].\end{split}$
(16)

We let $j_{k}$ be the source picked, at time step $k$, by an agent that
follows $\left\\{\tilde{\pi}_{k|k-1}\right\\}_{1:N}$. We can now state the
following

###### Assumption 3

$\forall k$, there exist bounded constants, $l_{k}$ and $L_{k}$, such that
$\forall\mathbf{x}_{k}\in\mathcal{X}$,
${l}_{k}\leq\ln({p^{(j_{k})}_{k|k-1}}/{p_{k|k-1}})\leq L_{k}$.

###### Assumption 4

$\forall k$, there exists a bounded constant, say $R_{k}$, such that
$\forall\mathbf{x}_{k}\in\mathcal{X}$,
$\left|r_{k}^{(j_{k})}(\mathbf{x}_{k})-r_{k}(\mathbf{x}_{k})\right|\leq
R_{k}$.

###### Remark 6

Asn. 3 implies that the log-likelihood ratio
$\Lambda_{1:N}:=\ln{\prod_{k=1}^{N}p_{k|k-1}^{(j_{k})}}/{\prod_{k=1}^{N}p_{k|k-1}}$
is bounded. Asn. 4 is on the difference between the rewards of the sources and
that of the agent. This is fulfilled when e.g. rewards are bounded.

We are now ready to state the following result.

###### Proposition 1

let Assumption 2 \- 4 hold. Then,
$\bar{R}_{1:N|0}\leq\sum_{k=1}^{N}\left(L_{k}-l_{k}+2R_{k}\right)$.

###### Proof:

the result is proved by obtaining an explicit expression for the regret, which
is then upper-bounded by leveraging Assumption 2 and Lemma 2. The desired
bound is finally obtained by means of Assumption 4 and Assumption 3. Following
Def. 3, $\bar{R}_{1:N|0}$ is given by:

$\mathcal{D}_{\text{KL}}\left(\tilde{\pi}_{1:N|0}||p_{1:N|0}\right)+\sum_{k=1}^{N}\mathbb{E}_{\bar{\pi}_{k-1:k-1}}\left[\mathbb{E}_{\bar{\pi}_{k|k-1}}\left[{r}_{k}(\mathbf{X}_{k})\right]\right]-\mathcal{D}_{\text{KL}}\left(\bar{\pi}_{1:N|0}||p_{1:N|0}\right)-\sum_{k=1}^{N}\mathbb{E}_{\tilde{\pi}_{k-1:k-1}}\left[\mathbb{E}_{\tilde{\pi}_{k|k-1}}\left[{r}_{k}(\mathbf{X}_{k})\right]\right].$
(17)

Note that (using $d\mathbf{x}_{1:N}$ as a shorthand notation for
$d\mathbf{x}_{1}\ldots d\bf{x}_{N}$):

$\displaystyle\mathcal{D}_{\text{KL}}\left(\bar{\pi}_{1:N|0}||p_{1:N|0}\right)$
$\displaystyle:=\int\bar{\pi}_{1:N|0}\ln\frac{\bar{\pi}_{1:N|0}}{p_{1:N|0}}d\mathbf{x}_{1:N}$
$\displaystyle=\int\bar{\pi}_{1:N|0}\ln\frac{\tilde{\pi}_{1:N|0}}{p_{1:N|0}}d\mathbf{x}_{1:N}+\int\bar{\pi}_{1:N|0}\ln\frac{\bar{\pi}_{1:N|0}}{\tilde{\pi}_{1:N|0}}d\mathbf{x}_{1:N}$
$\displaystyle\geq\int\tilde{\pi}_{1:N|0}\ln\frac{\tilde{\pi}_{1:N|0}}{p_{1:N|0}}d\mathbf{x}_{1:N}+\int\left(\bar{\pi}_{1:N|0}-\tilde{\pi}_{1:N|0}\right)\ln\frac{\tilde{\pi}_{1:N|0}}{p_{1:N|0}}d\mathbf{x}_{1:N}$
$\displaystyle=\mathcal{D}_{\text{KL}}\left(\tilde{\pi}_{1:N|0}||p_{1:N|0}\right)+\int\left(\bar{\pi}_{1:N|0}-\tilde{\pi}_{1:N|0}\right)\ln\frac{\tilde{\pi}_{1:N|0}}{p_{1:N|0}}d\mathbf{x}_{1:N},$

where we used the fact that

$\int\bar{\pi}_{1:N|0}\ln\frac{\bar{\pi}_{1:N|0}}{\tilde{\pi}_{1:N|0}}d\mathbf{x}_{1:N}=\mathcal{D}_{\text{KL}}\left(\bar{\pi}_{1:N|0}||\tilde{\pi}_{1:N|0}\right)\geq
0.$

As a result, the expression in (17) is upper bounded by

$-\langle\bar{\pi}_{1:N|0}-\tilde{\pi}_{1:N|0},\ln\frac{\tilde{\pi}_{1:N|0}}{p_{1:N|0}}\rangle+\sum_{k=1}^{N}(\mathbb{E}_{\bar{\pi}_{k-1:k-1}}\left[\tilde{r}_{k}(\mathbf{X}_{k-1})\right]-\mathbb{E}_{\tilde{\pi}_{k-1:k-1}}\left[\tilde{r}_{k}(\mathbf{X}_{k-1})\right]).$

Assumption 2 and Lemma 2 imply that the behaviors from the sources are of the
form (15) - (16). Hence we get that
$-\langle\bar{\pi}_{1:N|0}-\tilde{\pi}_{1:N|0},\ln\frac{\tilde{\pi}_{1:N|0}}{p_{1:N|0}}\rangle$
equals

$\int\left(\tilde{\pi}_{1:N|0}-\bar{\pi}_{1:N|0}\right)\left(\ln\frac{\prod_{k=1}^{N}p_{k|k-1}^{(j_{k})}}{\prod_{k=1}^{N}p_{k|k-1}}+\sum_{k=1}^{N}\bar{r}_{k}^{(j_{k})}(\mathbf{x}_{k})\right)d\mathbf{x}_{1:N}-\int\
\left(\tilde{\pi}_{1:N|0}-\bar{\pi}_{1:N|0}\right)\sum_{k=1}^{N}\hat{r}_{k-1}^{(j_{k})}(\mathbf{x}_{k-1})d\mathbf{x}_{1:N},$

thus implying that (17) is upper bounded by

$\begin{split}&\langle\tilde{\pi}_{1:N|0}-\bar{\pi}_{1:N|0},\Lambda_{1:N}\rangle+\mathbb{E}_{\tilde{\pi}_{1:N|0}}\left[\sum_{k=1}^{N}\bar{r}_{k}^{(j_{k})}(\mathbf{X}_{k})\right]+\sum_{k=1}^{N}\mathbb{E}_{\bar{\pi}_{k:k}}\left[{r}_{k}(\mathbf{X}_{k})\right]-\mathbb{E}_{\bar{\pi}_{1:N|0}}\left[\sum_{k=1}^{N}\bar{r}_{k}^{(j_{k})}(\mathbf{X}_{k})\right]\\\
&-\sum_{k=1}^{N}\mathbb{E}_{\tilde{\pi}_{k:k}}\left[{r}_{k}(\mathbf{X}_{k})\right]+\mathbb{E}_{\bar{\pi}_{1:N|0}}\left[\sum_{k=1}^{N}\hat{r}_{k-1}^{(j_{k})}(\mathbf{X}_{k-1})\right]-\mathbb{E}_{\tilde{\pi}_{1:N|0}}\left[\sum_{k=1}^{N}\hat{r}_{k-1}^{(j_{k})}(\mathbf{X}_{k-1})\right].\end{split}$
(18)

Moreover, linearity of the expectation together with the fact that
$\bar{r}_{k}^{(j_{k})}(\cdot)$ only depends on the state at time step $k$
implies that:

$\displaystyle\mathbb{E}_{\tilde{\pi}_{1:N|0}}\left[\sum_{k=1}^{N}\bar{r}_{k}^{(j_{k})}(\mathbf{X}_{k})\right]$
$\displaystyle=\sum_{k=1}^{N}\mathbb{E}_{\tilde{\pi}_{1:N|0}}\left[\bar{r}_{k}^{(j_{k})}(\mathbf{X}_{k})\right]$
$\displaystyle=\sum_{k=1}^{N}\mathbb{E}_{\tilde{\pi}_{k:k}}\left[\bar{r}_{k}^{(j_{k})}(\mathbf{X}_{k})\right].$

Likewise, we have:

$\displaystyle\mathbb{E}_{\bar{\pi}_{1:N|0}}\left[\sum_{k=1}^{N}\bar{r}_{k}^{(j_{k})}(\mathbf{X}_{k})\right]$
$\displaystyle=\sum_{k=1}^{N}\mathbb{E}_{\bar{\pi}_{k:k}}\left[\bar{r}_{k}^{(j_{k})}(\mathbf{X}_{k})\right];$
$\displaystyle\mathbb{E}_{\bar{\pi}_{1:N|0}}\left[\sum_{k=1}^{N}\hat{r}_{k-1}^{(j_{k})}(\mathbf{X}_{k-1})\right]$
$\displaystyle=\sum_{k=1}^{N}\mathbb{E}_{\bar{\pi}_{k-1:k-1}}\left[\hat{r}_{k-1}^{(j_{k})}(\mathbf{X}_{k-1})\right];$
$\displaystyle\mathbb{E}_{\tilde{\pi}_{1:N|0}}\left[\sum_{k=1}^{N}\hat{r}_{k-1}^{(j_{k})}(\mathbf{X}_{k-1})\right]$
$\displaystyle=\sum_{k=1}^{N}\mathbb{E}_{\tilde{\pi}_{k-1:k-1}}\left[\hat{r}_{k-1}^{(j_{k})}(\mathbf{X}_{k-1})\right].$

These relationships, together with (18) and the first relationship in (16),
lead to the following upper bound for $\bar{R}_{1:N|0}$:

$\begin{split}&\langle\tilde{\pi}_{1:N|0}-\bar{\pi}_{1:N|0},\Lambda_{1:N}\rangle+\sum_{k=1}^{N}\mathbb{E}_{\tilde{\pi}_{k:k}}\left[r_{k}^{(j_{k})}(\mathbf{X}_{k})-{r}_{k}(\mathbf{X}_{k})\right]+\sum_{k=1}^{N}\mathbb{E}_{\bar{\pi}_{k:k}}\left[{r}_{k}(\mathbf{X}_{k})-r_{k}^{(j_{k})}(\mathbf{X}_{k})\right]\\\
&+\sum_{k=1}^{N}\left(\mathbb{E}_{\tilde{\pi}_{k:k}}\left[\hat{r}_{k}^{(j_{k})}(\mathbf{X}_{k})\right]-\mathbb{E}_{{\bar{\pi}}_{k:k}}\left[\hat{r}_{k}^{(j_{k})}(\mathbf{X}_{k})\right]\right)+\sum_{k=1}^{N}\left(\mathbb{E}_{{\bar{\pi}}_{k-1:k-1}}\left[\hat{r}_{k-1}^{(j_{k})}(\mathbf{X}_{k-1})\right]-\mathbb{E}_{\tilde{\pi}_{k-1:k-1}}\left[\hat{r}_{k-1}^{(j_{k})}(\mathbf{X}_{k-1})\right]\right).\end{split}$
(19)

Now, the sums in the last two lines of (19) can be recast as
$\mathbb{E}_{\bar{\pi}_{0:0}}\left[\hat{r}_{0}^{(j_{0})}(\mathbf{X}_{0})\right]-\mathbb{E}_{\tilde{\pi}_{0:0}}\left[\hat{r}_{0}^{(j_{0})}(\mathbf{X}_{0})\right]$.
Since (see Def. 4) the agent and the oracle have the same initial pdf/pmf,
then this means that (19) equals

$\langle\tilde{\pi}_{1:N|0}-\bar{\pi}_{1:N|0},\Lambda_{1:N}\rangle+\sum_{k=1}^{N}\mathbb{E}_{\tilde{\pi}_{k:k}}\left[r_{k}^{(j_{k})}(\mathbf{X}_{k})-{r}_{k}(\mathbf{X}_{k})\right]+\sum_{k=1}^{N}\mathbb{E}_{\bar{\pi}_{k:k}}\left[{r}_{k}(\mathbf{X}_{k})-r_{k}^{(j_{k})}(\mathbf{X}_{k})\right].$

Prop. 1 follows by noticing that, for such expression: (i) from Assumption 4,
the sums are upper bounded by $2\sum_{k=1}^{N}R_{k}$; (ii) from Assumption 3,
$\langle\tilde{\pi}_{1:N|0}-\bar{\pi}_{1:N|0},\Lambda_{1:N}\rangle\leq\sum_{k=1}^{N}\left(L_{k}-l_{k}\right)$.
∎

Figure 1: a connected car has access to multiple navigation services/sources
to navigate within a grid-like area.

##  VI Numerical Example

We consider the scenario of Fig. 1, where a connected car (i.e. the agent)
travels within a geographic area and has access to multiple navigation
services. The services come from different providers and each of them returns
a different navigation strategy. We now make use of our results to design a
mechanism enabling the agent to dynamically choose which service to follow in
order to fulfill a navigation task. The road network we consider is the one of
Fig. 1. We set $N=8$ and the agent wishes to reach node $24$ from node $0$. We
let $x_{k}\in\mathcal{X}:=0:24$ be the position of the agent on the graph at
time step $k$, while the target behavior is given by the pmfs
$p_{k|k-1}=p_{k}(x_{k}|x_{k-1})$, which might e.g. describe the preferred
route of the passengers (see Fig. 2). These pmfs can be obtained from past
trips via e.g. the algorithm of [21, 22]. The agent has access to $3$
navigation services/sources and each provides a navigation strategy through
the pmfs $\pi^{(i)}_{k|k-1}$’s, $i=1:3$ (see Fig. 2). These pmfs are the
optimal solution of a problem of the form of Problem 3 having the reward set
to $0$. Hence, following Lemma 2, we have for each $k$ that
$\pi^{(i)}_{k|k-1}=p^{(i)}_{k|k-1}$ (the pmfs $p^{(i)}_{k|k-1}$’s are the
target behavior/route for the $i$-th service)111All pmfs, together with full
size versions of the figures are given at https://tinyurl.com/24ns3joy. Code
available upon request..

Figure 2: routes sampled from the $p_{k|k-1}$’s (top-left) and
$\pi^{(i)}_{k|k-1}$’s (top-right). Routes from the sources are highlighted
with different colors (online). Bottom panel: reward used in our second set of
numerical experiments - node $18$ is penalized, while $11$ is favored.

We implemented a Python script which, given the destination of the agent,
returns: (i) the solution to Problem 1, i.e.
$\left\\{\pi_{k|k-1}^{\ast}\right\\}_{1:N}$, by implementing the backward
recursion of Lemma 1; (ii) the route obtained by sampling, at each $k$, from
$\pi_{k|k-1}^{\ast}$; (iii) the cost,
$\mathcal{C}\left\\{\pi_{1:N|0}^{\ast}\right\\}$ (the expression for
$\mathcal{C}\left\\{\cdot\right\\}$ is in Def. 3). We now consider two cases.
First, the agent reward is set to $0$. This reward captures situations where
the agent only wishes to track the target behavior (e.g. the preferred route).
This yields the pmfs (and hence the routes) of Fig. 3 \- top panels. The
corresponding cost, i.e. $\mathcal{C}\left\\{\pi_{1:N|0}^{\ast}\right\\}$, is
equal to $0$ and, from Prop. 1, we get $\bar{R}_{1:N|0}=0$. In our second set
of simulations, we use the reward of Fig. 2. As shown in the bottom panels of
Fig. 3, since node $11$ is now favored over node $18$ (due to e.g.
risks/traffic associated to the latter node), the agent deviates from its
target and the resulting route avoids node $18$. The corresponding cost is
$\mathcal{C}\left\\{\pi^{\ast}_{1:N|0}\right\\}={1.57}$ while, by means of
Prop. 1, we have that $\bar{R}_{1:N|0}\leq{27.32}$, with this non-zero bound,
due to the discrepancy between the target/rewards of the agent and these of
the sources.

Figure 3: the agent route (left panels) and the pmfs from which it is sampled
(right panels). In the top panels the reward is set to $0$, while in the
bottom panels the reward is the one of Fig. 2. The colors (online) for the
routes highlight which source is selected at each $k$ by the agent (the same
color code as Fig. 2 is used).

##  VII Conclusions

We considered the problem of designing agents that are able to dynamically
choose between different data sources in order to tackle tracking tasks. We
formulated the problem as a data-driven control problem and this led to study
an integer optimal control problem. After finding the optimal solution, which
determines how the use of the different sources should be orchestrated by the
agent, we formalized a notion of regret. Then, by solving a relaxation of the
control problem, we gave a regret upper bound. The results were complemented
via simulations on a connected cars scenario.

### Proof of Lemma 2

we first show that Problem 3 can be decomposed into a sequence of sub-
problems, which can be solved via backward recursion. Then, the expression for
the optimal solution is obtained by explicitly solving the sub-problems. We
use $\mathcal{J}_{n}\left\\{\pi_{1:n-1|0},p_{1:n-1|0}\right\\}$ to denote
$\mathcal{D}_{\text{KL}}\left(\pi_{1:n-1|0}||p_{1:n-1|0}\right)-\sum_{k=1}^{n-1}\mathbb{E}_{\pi_{k-1:k-1}}\left[\tilde{r}_{k}(\mathbf{X}_{k-1})\right]$.
Following the same reasoning used to prove Theorem 1, we find that (11) can be
formulated as the sum of:

$\displaystyle\underset{\left\\{\pi_{k|k-1}\right\\}_{1:N-1}}{\text{min}}$
$\displaystyle\mathcal{J}_{N}\left\\{\pi_{1:N-1|0},p_{1:N-1|0}\right\\}$ (20)
$\displaystyle s.t.$ $\displaystyle\ \pi_{k|k-1}\in\mathcal{D},\ \ k\in
1:N-1,$

and

$\displaystyle\underset{\pi_{N|N-1}}{\text{min}}$
$\displaystyle\mathbb{E}_{\pi_{N-1:N-1}}\left[\mathcal{D}_{\text{KL}}\left(\pi_{N|N-1}||p_{N|N-1}\right)-\tilde{r}_{N}(\mathbf{X}_{N-1})\right]$
(21) $\displaystyle s.t.$ $\displaystyle\ \pi_{N|N-1}\in\mathcal{D}.$

We can then approach Problem 3 by solving (21) and then by taking into account
its solution to solve (20). Moreover, the minimum of the above problem is
$\mathbb{E}_{\pi_{N-1:N-1}}\left[\bar{c}_{N}(\bf{X}_{N-1}))\right]$, where
$\bar{c}_{N}(\bf{x}_{N-1})$ is the optimal cost of:

$\displaystyle\underset{\pi_{N|N-1}}{\text{min}}$
$\displaystyle\mathcal{C}_{N}\left\\{\pi_{N|N-1}\right\\}$ (22) $\displaystyle
s.t.$ $\displaystyle\ \pi_{N|N-1}\in\mathcal{D},$

$\mathcal{C}_{N}\left\\{\pi_{N|N-1}\right\\}:=\mathcal{D}_{\text{KL}}\left(\pi_{N|N-1}||p_{N|N-1}\right)-\tilde{r}_{N}(\mathbf{x}_{N-1})$.
We also note that (22) is convex with a strictly convex twice differentiable
(w.r.t. the decision variable) cost functional and we now find its minimizer
by imposing the first order stationarity conditions on its Lagrangian

$\mathcal{L}\left(\pi_{N|N-1},\lambda_{N}\right):=\int\pi_{N|N-1}\left(\ln\left(\frac{\pi_{N|N-1}}{p_{N|N-1}}-\bar{\rho}_{N}(\mathbf{x}_{N})\right)\right)d\mathbf{x}_{N}+\lambda_{N}\left(\int\pi_{N|N-1}d\mathbf{x}_{N}-1\right),$

where
$\bar{\rho}_{N}(\mathbf{x}_{N}):={r}_{N}(\mathbf{x}_{N})+\hat{\rho}_{N}(\mathbf{x}_{N})$,
with $\hat{\rho}_{N}(\mathbf{x}_{N})=0$, and $\lambda_{N}$ is the Lagrange
multiplier corresponding to the only constraint of the problem in (22). By
imposing the stationarity condition with respect to $\pi_{N|N-1}$ we get that
the optimal solution $\bar{\pi}_{N|N-1}$ must satisfy

$\ln\frac{\bar{\pi}_{N|N-1}}{p_{N|N-1}}-\bar{\rho}_{N}(\mathbf{x}_{N})+1+\lambda_{N}=0,$

which then yields

$\bar{\pi}_{N|N-1}=p_{N|N-1}\frac{\exp(\bar{\rho}_{N}(\mathbf{x}_{N}))}{\exp(1+\lambda_{N})}.$

The Lagrange multiplier $\lambda_{N}$ can be found by imposing the
stationarity condition of the Lagrangian with respect to $\lambda_{N}$. By
imposing such a condition we get

$\exp(1+\lambda_{N})=\int
p_{N|N-1}{\exp(\bar{\rho}_{N}(\mathbf{x}_{N}))}d\mathbf{x}_{N}.$

Hence:

$\bar{\pi}_{N|N-1}=\frac{p_{N|N-1}\exp\left(\bar{\rho}_{N}(\mathbf{x}_{N})\right)}{\int
p_{N|N-1}\exp\left(\bar{\rho}_{N}(\mathbf{x}_{N})\right)d\mathbf{x}_{N}}.$

This yields (12) - (13) at $k=N$. Moreover, the minimum of (22) is given by
$-\ln\mathbb{E}_{p_{N|N-1}}\left[\exp(\bar{\rho}_{N}(\mathbf{X}_{N}))\right]$.
From this, the minimum for (21) is
$-\mathbb{E}_{\pi_{N-1:N-1}}\left[\ln\mathbb{E}_{p_{N|N-1}}\left[\exp(\bar{\rho}_{N}(\mathbf{X}_{N}))\right]\right]$.
Next, we solve Problem 3 for the remaining time instants. Having split Problem
3 as the sum of the sub-problems (20) - (21) implies that its cost functional
can be written as

$\mathcal{J}_{N}\left\\{\pi_{1:N-1|0},p_{1:N-1|0}\right\\}-\mathbb{E}_{\pi_{N-1:N-1}}\left[\ln\mathbb{E}_{p_{N|N-1}}\left[\exp(\bar{\rho}_{N}(\mathbf{X}_{N}))\right]\right],$

which, (see Property 1 of [23]), is equal to:

$\displaystyle\mathcal{J}_{N-1}\left\\{\pi_{1:N-2|0},p_{1:N-2|0}\right\\}-\mathbb{E}_{\pi_{N-2:N-2}}\left[\tilde{r}_{N-1}(\mathbf{X}_{N-2})\right]+\mathbb{E}_{\pi_{1:N-2|0}}\left[\mathcal{D}_{\text{KL}}\left(\pi_{N-1|N-2}||p_{N-1|N-2}\right)\right]$
$\displaystyle-\mathbb{E}_{\pi_{N-1:N-1}}\left[\ln\mathbb{E}_{p_{N|N-1}}\left[\exp(\bar{\rho}_{N}(\mathbf{X}_{N}))\right]\right].$

Moreover:

$\displaystyle-\mathbb{E}_{\pi_{N-1:N-1}}\left[\ln\mathbb{E}_{p_{N|N-1}}\left[\exp(\bar{\rho}_{N}(\mathbf{X}_{N}))\right]\right]$
$\displaystyle=-\mathbb{E}_{\pi_{N-1:N-1}}\left[\hat{\rho}_{N-1}(\mathbf{X}_{N-1})\right]$
$\displaystyle=-\mathbb{E}_{\pi_{N-2:N-1}}\left[\hat{\rho}_{N-1}(\mathbf{X}_{N-1})\right]$
$\displaystyle=\int\int\pi_{N-1|N-2}\left(\mathbf{x}_{N-1}|\mathbf{x}_{N-2}\right)\pi_{N-2:N-2}(\mathbf{x}_{N-2})\hat{\rho}_{N-1}(\mathbf{x}_{N-1})d\mathbf{x}_{N-1}d\mathbf{x}_{N-2}$
$\displaystyle=-\mathbb{E}_{\pi_{N-2:N-2}}\left[\mathbb{E}_{\pi_{N-1|N-2}}\left[\hat{\rho}_{N-1}(\mathbf{X}_{N-1})\right]\right],$

and

$\displaystyle\mathbb{E}_{\pi_{1:N-2|0}}\left[\mathcal{D}_{\text{KL}}\left(\pi_{N-1|N-2}||p_{N-1|N-2}\right)\right]$
$\displaystyle=\mathbb{E}_{\pi_{N-2:N-2}}\left[\mathcal{D}_{\text{KL}}\left(\pi_{N-1|N-2}||p_{N-1|N-2}\right)\right].$

Hence:

$\displaystyle-\mathbb{E}_{\pi_{N-2:N-2}}\left[\tilde{r}_{N-1}(\mathbf{X}_{N-2})\right]+\mathbb{E}_{\pi_{1:N-2|0}}\left[\mathcal{D}_{\text{KL}}\left(\pi_{N-1|N-2}||p_{N-1|N-2}\right)\right]-\mathbb{E}_{\pi_{N-1:N-1}}\left[\ln\mathbb{E}_{p_{N|N-1}}\left[\exp(\bar{\rho}_{N}(\mathbf{X}_{N}))\right]\right]$
$\displaystyle=\mathbb{E}_{\pi_{N-2:N-2}}\left[\mathcal{D}_{\text{KL}}\left(\pi_{N-1|N-2}||p_{N-1|N-2}\right)-\mathbb{E}_{\pi_{N-1|N-2}}\left[{r}_{N-1}(\mathbf{X}_{N-1})+\hat{\rho}_{N-1}(\mathbf{X}_{N-1})\right]\right]$

Again, this means that the problem can be split as the sum of:

$\displaystyle\underset{\left\\{\pi_{k|k-1}\right\\}_{1:N-2}}{\text{min}}$
$\displaystyle\mathcal{J}_{N-1}\left\\{\pi_{1:N-2|0},p_{1:N-2|0}\right\\}$
$\displaystyle s.t.$ $\displaystyle\ \pi_{k|k-1}\in\mathcal{D},\ \ k\in
1:N-2,$

and

$\displaystyle\underset{\pi_{N-1|N-2}}{\text{min}}$
$\displaystyle\mathbb{E}_{\pi_{N-2:N-2}}\left[\mathcal{C}_{N-1}\left\\{\pi_{N-1|N-2}\right\\}\right]$
(23) $\displaystyle s.t.$ $\displaystyle\ \pi_{N-1|N-2}\in\mathcal{D},$

with

$\displaystyle\mathcal{C}_{N-1}\left\\{\pi_{N-1|N-2}\right\\}:=\int\pi_{N-1|N-2}(\ln\frac{\pi_{N-1|N-2}}{p_{N-1|N-2}}-\bar{\rho}_{N-1}(\mathbf{x}_{N-1}))d\mathbf{x}_{N-1}$
and
$\displaystyle\bar{\rho}_{N-1}(\mathbf{x}_{N-1})={r}_{N-1}(\mathbf{x}_{N-1})+\hat{\rho}_{N-1}(\mathbf{x}_{N-1}).$

The minimum for (23) is
$\mathbb{E}_{\pi_{N-2:N-2}}\left[\bar{c}_{N-1}(\mathbf{X}_{N-2}))\right]$,
with $\bar{c}_{N-1}(\mathbf{x}_{N-2})$ being the cost obtained by solving:

$\displaystyle\underset{\pi_{N-1|N-2}}{\text{min}}$
$\displaystyle\mathcal{C}_{N-1}\left\\{\pi_{N-1|N-2}\right\\}$ $\displaystyle
s.t.$ $\displaystyle\pi_{N|N-2}\in\mathcal{D}.$

That is, once the problem at time $N$ is solved, the optimization problem up
to $N-1$ can be still split as the sum of two sub-problems with the one at
$k=N-1$ being independent on the sub-problem up to $k=N-2$. The sub-problem at
$k=N-1$ has the same structure as (22). Hence, by defining
$\bar{\rho}_{N-1}(\mathbf{x}_{N-1})={r}_{N-1}(\mathbf{x}_{N-1})+\hat{\rho}_{N-1}(\mathbf{x}_{N-1})$,
we have that its solution is

$\bar{\pi}_{N-1|N-2}=\frac{p_{N-1|N-2}\exp\left(\bar{\rho}_{N-1}(\mathbf{x}_{N-1})\right)}{\int
p_{N-1|N-2}\exp\left(\bar{\rho}_{N-1}(\mathbf{x}_{N-1})\right)d\mathbf{x}_{N-1}}.$

This gives (12) - (13) at $k=N-1$. The optimal cost for the sub-problem at
$k=N-1$ is

$-\mathbb{E}_{\pi_{N-2:N-2}}\left[\ln\mathbb{E}_{p_{N-1|N-2}}\left[\exp(\bar{\rho}_{N-1}(\mathbf{X}_{N-1}))\right]\right].$

We can then conclude the proof by noticing the following. By iterating the
above arguments we find that, at each of the remaining time steps in $1:N-2$,
Problem 3 can always be split as the sum of two sub-problems, where the last
one can be solved by finding the minimum of:

$\displaystyle\underset{\pi_{k|k-1}}{\text{min}}$
$\displaystyle\mathcal{D}_{\text{KL}}\left(\pi_{k|k-1}||p_{k|k-1}\right)-\mathbb{E}_{\pi_{k|k-1}}\left[\bar{\rho}_{k}(\mathbf{X}_{k-1})\right]$
(24) $\displaystyle s.t.$ $\displaystyle\ \pi_{k|k-1}\in\mathcal{D},$

and
$\bar{\rho}_{k}(\mathbf{x}_{k})={r}_{k}(\mathbf{x}_{k})+\hat{\rho}_{k}(\mathbf{x}_{k})$
with
$\hat{\rho}_{k}(\mathbf{x}_{k}):=\ln\mathbb{E}_{p_{k+1|k}}\left[\exp(\bar{\rho}_{k+1}(\mathbf{X}_{k+1}))\right]$.
Hence, the solution of (24) is

$\bar{\pi}_{k|k-1}=\frac{p_{k|k-1}\exp\left(\bar{\rho}_{k}(\mathbf{x}_{k})\right)}{\int
p_{k|k-1}\exp\left(\bar{\rho}_{k}(\mathbf{x}_{k})\right)d\mathbf{x}_{k}},$

and from this we can draw the desired conclusion. ∎

## References

  * [1] M. Cutler, T. J. Walsh, and J. P. How, “Real-world reinforcement learning via multifidelity simulators,” _IEEE Trans. on Robotics_ , vol. 31, no. 3, pp. 655–671, 2015.
  * [2] M. Waibel _et al._ , “Roboearth,” _IEEE Rob. Aut. Mag._ , vol. 18, no. 2, pp. 69–82, 2011.
  * [3] E. Crisostomi _et al._ , Eds., _Analytics for the Sharing Economy: Mathematics, Engineering and Business Perspectives_. Springer, 2020.
  * [4] G. Russo, “On the crowdsourcing of behaviors for autonomous agents,” _IEEE Control Sys. Letters_ , vol. 5, no. 4, pp. 1321–1326, 2021.
  * [5] J. Coulson, J. Lygeros, and F. Dörfler, “Data-enabled predictive control: In the shallows of the DeePC,” in _European Control Conference_ , 2019, pp. 307–312.
  * [6] C. De Persis and P. Tesi, “Formulas for data-driven control: Stabilization, optimality, and robustness,” _IEEE Trans. on Automatic Control_ , vol. 65, no. 3, pp. 909–924, 2020.
  * [7] H. J. van Waarde _et al._ , “Data informativity: A new perspective on data-driven analysis and control,” _IEEE Trans. on Aut. Contr._ , vol. 65, pp. 4753–4768, 2020.
  * [8] G. Baggio, V. Katewa, and F. Pasqualetti, “Data-driven minimum-energy controls for linear systems,” _IEEE Control Systems Letters_ , vol. 3, no. 3, pp. 589–594, 2019.
  * [9] U. Rosolia and F. Borrelli, “Learning model predictive control for iterative tasks. A data-driven control framework,” _IEEE Trans. on Automatic Control_ , vol. 63, no. 7, pp. 1883–1896, 2018.
  * [10] K. P. Wabersich and M. N. Zeilinger, “Bayesian model predictive control: Efficient model exploration and regret bounds using posterior sampling,” ser. Proc. of ML Research, vol. 120, 2020, pp. 455–464.
  * [11] J. Berberich _et al._ , “Data-driven model predictive control with stability and robustness guarantees,” _IEEE Trans. on Aut. Contr._ , pp. 1–1, 2020.
  * [12] Marko Tanaskovic, _et al._ , “Data-driven control of nonlinear systems: An on-line direct approach,” _Automatica_ , vol. 75, pp. 1 – 10, 2017.
  * [13] D. Gagliardi and G. Russo, “On the synthesis of control policies from example datasets,” in _21st IFAC World Congress_ , 2020.
  * [14] M. Kárný, “Towards fully probabilistic control design,” _Automatica_ , vol. 32, no. 12, pp. 1719–1722, 1996.
  * [15] M. Sznaier, “Control oriented learning in the era of big data,” _IEEE Control Systems Letters_ , vol. 5, no. 6, pp. 1855–1867, 2021.
  * [16] H. J. van Waarde  _et al._ , “Willems’ fundamental lemma for state-space systems and its extension to multiple datasets,” _IEEE Control Systems Letters_ , vol. 4, no. 3, pp. 602–607, 2020.
  * [17] R. Agarwal, D. Schuurmans, and M. Norouzi, “An optimistic perspective on offline reinforcement learning,” in _Proc. of the 37th Intl. Conf. on Machine Learning_ , vol. 119, 2020, pp. 104–114.
  * [18] A. Kumar _et al._ , “Conservative Q-Learning for offline reinforcement learning,” in _34th Conf. Neur. Inf. Proc. Sys._ , 2020, pp. 104–114.
  * [19] J. R. Hershey and P. A. Olsen, “Approximating the Kullback Leibler divergence between gaussian mixture models,” in _2007 IEEE Intl. Conf. on Acoustics, Speech and Sig. Proc._ , vol. 4, 2007, pp. 317–320.
  * [20] F. Nielsen and K. Sun, “Guaranteed bounds on information-theoretic measures of univariate mixtures using piecewise log-sum-exp inequalities,” _Entropy_ , vol. 18, p. 442, 2016.
  * [21] Y. Lassoued _et al._ , “A hidden Markov model for route and destination prediction,” in _IEEE Intl. Conf. on Int. Transp. Sys._ , 2017, pp. 1–6.
  * [22] S. Sweeney _et al._ , “A context-aware e-bike system to reduce pollution inhalation while cycling,” _IEEE Trans. on Int. Transp. Sys._ , vol. 20, no. 2, pp. 704–715, 2019.
  * [23] D. Gagliardi and G. Russo, “On a probabilistic approach to synthesize control policies from example datasets,” https://arxiv.org/abs/2005.11191, 2020\.