  In many real-world sequential decision-making problems, an action does not
immediately reflect on the feedback and spreads its effects over a long time
frame. For instance, in online advertising, investing in a platform produces an
instantaneous increase of awareness, but the actual reward, i.e., a conversion,
might occur far in the future. Furthermore, whether a conversion takes place
depends on: how fast the awareness grows, its vanishing effects, and the
synergy or interference with other advertising platforms. Previous work has
investigated the Multi-Armed Bandit framework with the possibility of delayed
and aggregated feedback, without a particular structure on how an action
propagates in the future, disregarding possible dynamical effects. In this
paper, we introduce a novel setting, the Dynamical Linear Bandits (DLB), an
extension of the linear bandits characterized by a hidden state. When an action
is performed, the learner observes a noisy reward whose mean is a linear
function of the hidden state and of the action. Then, the hidden state evolves
according to linear dynamics, affected by the performed action too. We start by
introducing the setting, discussing the notion of optimal policy, and deriving
an expected regret lower bound. Then, we provide an optimistic regret
minimization algorithm, Dynamical Linear Upper Confidence Bound (DynLin-UCB),
that suffers an expected regret of order $\widetilde{\mathcal{O}} \Big( \frac{d
\sqrt{T}}{(1-\overline{\rho})^{3/2}} \Big)$, where $\overline{\rho}$ is a
measure of the stability of the system, and $d$ is the dimension of the action
vector. Finally, we conduct a numerical validation on a synthetic environment
and on real-world data to show the effectiveness of DynLin-UCB in comparison
with several baselines.
