#  A Comparative Study on Reward Models for UI Adaptation with Reinforcement
Learning

Daniel Gaspar-Figueiredo
Marta Fernández-Diego  ITI & Universitat Politècnica de València
Valencia, Spain
Email<EMAIL_ADDRESS>Universitat Politècnica de València
Valencia, Spain
Email<EMAIL_ADDRESS>Silvia Abrahão
Emilio Insfran  Universitat Politècnica de València
Valencia, Spain
Email<EMAIL_ADDRESS>Universitat Politècnica de València
Valencia, Spain
Email<EMAIL_ADDRESS>
###### Abstract

Background: Adapting the User Interface (UI) of software systems to user
requirements and the context of use is challenging. The main difficulty
consists of suggesting the right adaptation at the right time in the right
place in order to make it valuable for end-users. We believe that recent
progress in Machine Learning techniques provides useful ways in which to
support adaptation more effectively. In particular, Reinforcement learning
(RL) can be used to personalise interfaces for each context of use in order to
improve the user experience (UX). However, determining the reward of each
adaptation alternative is a challenge in RL for UI adaptation. Recent research
has explored the use of reward models to address this challenge, but there is
currently no empirical evidence on this type of model. Objective: In this
paper, we propose a confirmatory study design that aims to investigate the
effectiveness of two different approaches for the generation of reward models
in the context of UI adaptation using RL: (1) by employing a reward model
derived exclusively from predictive Human-Computer Interaction (HCI) models
(HCI), and (2) by employing predictive HCI models augmented by Human Feedback
(HCI&HF). Method: The controlled experiment will use an AB/BA crossover design
with two treatments: HCI and HCI&HF. We shall determine how the manipulation
of these two treatments will affect the UX when interacting with adaptive user
interfaces (AUI). The UX will be measured in terms of user engagement and user
satisfaction, which will be operationalized by means of predictive HCI models
and the Questionnaire for User Interaction Satisfaction (QUIS), respectively.
By comparing the performance of two reward models in terms of their ability to
adapt to user preferences with the purpose of improving the UX (i.e.
increasing user engagement, improving user satisfaction), our study
contributes to the understanding of how reward modelling can facilitate UI
adaptation using RL.

###### Index Terms:

User Interface Adaptation, Reinforcement Learning, Reward Modelling, Human
Feedback, Experiment

Figure 1: An interface is adapted by simulating several possible sequences of
adaptations and evaluating them using predictive models in HCI. This approach
avoids greedy, disadvantageous adaptations, and may anticipate possible user
responses even with limited observation data. Figure adapted from [1]

##  I Introduction

Adaptive systems and adaptive user interfaces (AUI) have become increasingly
important in modern software applications. They have been introduced in order
to address some of the usability problems in many software applications [2].
These systems can change aspects of their structure, functionality, or
interface to accommodate the differing needs of individuals or groups of users
and the changing needs of users over time [3]. However, suggesting the right
adaptation at the right time in the right place in order to make it valuable
for end-users is challenging. In previous work, we proposed a framework for
intelligent UI adaptation [4]. This framework proposes the use of Machine
Learning algorithms in order to provide valuable UI adaptations. Several
approaches have been proven successful in simple adaptation problems, such as
recommendations and the calibration of interface parameters [5, 6]. However,
Reinforcement Learning (RL) is more appropriate as regards learning policies
for sequences of adaptations in which rewards are not immediately achievable.
Indeed, the UI adaptation problem can be defined as a stochastic sequential
decision problem, where the adaptive system should plan a sequence of
adaptations over a long horizon [7]. RL involves training an agent to make
decisions based on rewards received from the environment for certain actions
[8, 9]. In UI adaptation, the agent will make decisions regarding which
adaptations to apply by considering the user’s interaction behaviour. The goal
of UI adaptation is to personalize the UI for each context of use so as to
improve the user experience (UX).

In this context, one challenge of RL for UI adaptation is determining the
reward of each adaptation. Traditional RL uses numerical rewards, which are
difficult to define in scenarios in which the outcome of the action or the
agent’s goal is complex.

Recent research has, therefore, explored ordinal rewards as an alternative
[10], which induce scale-invariance and reduce manual reward engineering [11].
Another approach is to make the reward function part of the learning process.
In complex environments, the use of reward models can be very profitable.
Reward models are a key component of RL that are used to specify the user’s
goals and the system [12]. During the process of learning the goal, putting
the human into the loop may be particularly powerful. Human Feedback (HF)
could be used as regards specifying the goal more intuitively and quickly when
compared to manual objective hand-crafted methods [13, 14].

On the one hand, reward models in UI adaptation can be defined using
predictive HCI models. An HCI model is a computational model that can explain
how users interact with interfaces at the level of individual human cognition
[15]. It simulates consequences – benefits and costs – of possible adaptation
sequences without actually executing them. These models are based on various
factors, such as the user’s behaviour, task difficulty, and interface design
features. By simulating human behaviour, HCI models can provide insights into
how users will interact with a new interface (or an adapted version) before it
is even built, thus allowing software developers to make informed decisions
about interface design. However, finding the best adaptation is
computationally costly, especially when considering sequences of changes over
a long horizon. To solve this computational problem in an online setting,
Monte Carlo Tree Search (MCTS) could be used for planning adaptations [7] (see
Section 2). On the other hand, putting the user into the loop, or using user
feedback, involves collecting user ratings or preferences on various aspects
of the UI, which can be used to enhance a reward model by reflecting the
users’ goals and needs (preferences). This falls in the promising field of
Reinforcement Learning from Human Feedback (RLHF), or RL from human
preferences, in which the HF helps to train a reward model [16, 14]. Although
these techniques for generating reward models appear to be useful, there is,
to the best of our knowledge, no empirical evidence concerning which is most
effective as regards supporting UI adaptation in a given context of use.

In this paper, we present a confirmatory study design to compare two different
approaches to generate reward models in the context of UI adaptation using RL.
Our study aims to investigate the effectiveness of using a reward model
derived exclusively from predictive HCI models and predictive HCI models
augmented with HF. The user goal may differ depending on the application
domain. For example, user engagement is a key factor for the success of
e-commerce systems and online catalogues as it can significantly impact on the
users’ purchase decisions and improve overall satisfaction. By comparing the
performance of different types of reward modelling in terms of their ability
to adapt to user preferences and improve UX, our study contributes to the
understanding of how reward modelling can facilitate UI adaptation using RL.

##  II Background and Related Work

Adaptive User Interfaces (AUI) have attracted increasing attention in recent
years as a means to improve UX and task performance. Several studies have
explored the benefits of using AUI in various application domains, such as
e-commerce, education, and healthcare systems. The major challenge in this
context is to determine the sequence of adaptations that have to be carried
out in order to improve the system’s quality, the user performance or UX. To
this end, several studies have applied different methods, such as defining
rules and heuristics or the use of Machine Learning and RL methods. For
example, in the context of menu searching in UI, MCTS has been proposed as a
promising technique for the development of adaptive menu search interfaces
[7]. In this recent work, Todi et al. [7] used predictive HCI models to
predict rewards for each state during simulations. Since online simulations
can be computationally expensive, a pretrained value network was used to
directly obtain value estimates for unexplored states. Training data for this
neural network was generated using the predictive HCI models. The authors
showed that while the computation time increases drastically with simulations
as search depth increases,it remains constant with the neural network approach
without interfering much in the overall success rate (92.7% with model-based
simulation vs. 89.6%).

Fig. 1 shows how MCTS planning could be applied to our domain. In the current
state of the tree at t0 (i.e., the actual design of the interface and user
observations from his/her previous interaction session with the interface),
the algorithm i) selects a child node based on a selection policy that
balances exploration and exploitation until reaching the most promising leaf
node; ii) expands the node only if it has already been explored by adding
child nodes for all the possible adaptations and pick one child node at
random; iii) roll-outs and simulates rewards using predictive HCI models while
adaptations are chosen at random since the tree has no value estimates with
which to inform the selection of consequential states. A sample of these roll-
outs will be augmented by HF, and iv) backpropagates the updated statistics of
all nodes visited during selection and expansion up the tree. These four steps
are repeated until a stopping criterion is met. After the X iterations allowed
by the MCTS algorithm and a shallow roll-out horizon of H steps, an adaptation
decision is made on the basis of the highest expected reward from among the
nodes that are located at t1, resulting in an adapted UI. To move from t1 to
t2, the tree is re-unfolded from the current UI at t1, and so on.

Note that we have defined an environment in which to train and compare RL
agents for the context of AUI in a previous study [17]. In this work, we have
defined the state representation, and the actions that the system can perform
to adapt the UI: i) change the UI layout; ii) change the colour scheme; iii)
change the font size; iv) show/hide content, and v) do nothing.

In [18], the authors formulated UI adaptation as a multi-agent RL problem,
with both a user agent who learns to interact with a UI so as to complete a
task and an interface agent who learns UI adaptations to maximise the user
agent’s performance. The joint exploration of both agents makes the adaptative
UIs goal-agnostic. However, we believe that HF could be used to optimise the
reward model. For example, Christiano et al. [14], propose a method with which
to train RL agents using human preferences. The authors present an off-policy
RL algorithm that learns from HF in the form of pairwise comparisons of
trajectories. The algorithm uses a deep neural network to represent the value
function and a ranking loss to optimise the network parameters. The authors
evaluate their method with a variety of tasks, including Atari games and
robotic manipulation, and show that it outperforms existing methods that use
hand-crafted reward functions. The paper concludes that their method is a
promising approach with which to train RL agents in complex environments where
designing reward functions is difficult. In [19], the authors propose an
algorithm that does not require any special adaptations for the off-policy or
offline RL settings.

##  III Experimental Design

According to the GQM template for goal definition [20], the goal of this study
is to analyze reward models derived from predictive HCI models and predictive
HCI models augmented with HF in RL algorithms with the purpose to assess their
impact to adapt UI with respect to their ability to improve the UX of software
applications from the point-of-view of both developers and researchers
interested in reward modelling in RL-based methods for UI adaptation. The
former might be interested in how the use of RL for UI adaptation can improve
UX in order to inform the design of more effective interfaces. This study will
also provide insights into obtaining user feedback for the development of
adaptive systems that can effectively adapt the UI. The latter might be
interested in our study results to delineate future research (e.g., means of
attaining feedback with which to evaluate the UI adaptation). Furthermore, the
findings could inform the development of new approaches and tools for the
improvement of UX in software applications, and could ultimately lead to more
efficient and effective software design and development processes. The context
consists of a group of undergraduate and Master’s degree students in Computer
Science at the Universitat Politècnica de València interacting with UIs from
the e-commerce and e-learning domains.

###  III-A Research questions and hypotheses

We aim to study the systematic variation of reward models so as to measure
their influence on the selection of UI adaptations that maximise the user’s
experience (i.e., user engagement and user satisfaction) in an experimental
set-up. For this purpose, we shall implement and monitor two RL-based AUI
strategies (using each of the reward models selected) in two different
domains. Fig. 2 shows the context used to train the RL agent that employs
MCTS, with reward models such as HCI models and with HF. In our case, the RL
agent will take actions (UI adaptations) and the environment will return
observations. A reward model will then return reward predictions on the basis
of 1) predictive HCI models only and 2) predictive models enriched with HF.

The objective of this study is to answer the following research questions and
hypotheses:

RQ1: Does the incorporation of HF in the reward models improve the
effectiveness of AUIs in terms of user engagement, when compared to reward
models derived exclusively from predictive HCI models? RQ1 sheds light on the
cost and benefits of training RL models with or without human feedback in
terms of their impact on user engagement (operationalized by means of
predictive HCI models). Since deciding about the best adaptation or sequence
of adaptations to perform is not obvious for a human, incorporating humans
into the loop to train the agent needs to be tested. As far as we are
concerned, there is no evidence of the improvement in AUI. According to
literature, the use of human feedback could bring benefits such as capturing
the way in which humans naturally propose or expect what to adapt, and when to
make changes, but it could also have costs related to the ability of the
system to scale with the availability of computational resources. Since the
analysis of costs vs. benefits for the specific problem of AUIs obtained using
RL models with or without human feedback has not yet been studied, we prefer
to be conservative and not postulate an effect in favour of AUIs with human
feedback. We therefore, propose the following null hypothesis:

  1. $H_{n1}$

There is no significant difference in user engagement between AUIs that
incorporate HF in the reward models and those that use reward models derived
exclusively from predictive HCI models.

Moreover, to assess the benefits of AUIs, it is desirable to understand the
degree to which they improve the UX when compared to non-adaptive interfaces.
This could be done by comparing the user engagement (operationalized using the
User Engagement Scale - UES [21]) and user satisfaction (operationalized using
the Questionnaire for User Interaction Satisfaction - QUIS [22]) with the
adapted and non-adapted UIs in different application domains.

Literature has already demonstrated the positive effect of AUIs in certain
contexts, but has also reported the limitations that could impede the expected
benefits [23]: risk of misfit (the end-user’s needs are incorrectly captured
or interpreted), user cognitive disruption (the end-user is disrupted by the
adaptation), lack of prediction (the end user does not know when and how the
adaptation will take place), lack of explanation (the end-user is not informed
of the reasons for adaptation). Moreover, adopting a poor adaptation strategy
may have negative effects on the user due to surprise or relearning effort.
Such costly changes should be avoided. Thus, to be conservative, we prefer not
to postulate that AUIs will be superior when compared to its non-AUIs version.
Also, the impact of system adaptivity on user engagement has been studied in
certain contexts (e.g., adaptive video streaming systems [24], large display-
based UIs [25]), but evidence to understand the benefits of using RL models to
support UI adaptation is required. To achieve this, we formulate the following
research questions and hypotheses:

RQ2: Does the use of AUIs, obtained with reward models, improve user
engagement when compared to non-adaptive interfaces in different application
domains?

  * •

$H_{n2}$ There is no significant difference in user engagement between AUIs
obtained with reward models derived exclusively from predictive HCI models and
non-adaptive interfaces.

  * •

$H_{n3}$ There is no significant difference in user engagement between AUIs
obtained with reward models derived from predictive HCI models that
incorporate HF and non-adaptive interfaces.

RQ3: Does the use of AUIs, obtained with reward models, improve user
satisfaction when compared to non-adaptive interfaces in different application
domains?

  1. $H_{n4}$

There is no significant difference in user satisfaction between AUIs obtained
with reward models derived exclusively from predictive HCI models and non-
adaptive interfaces.

  2. $H_{n5}$

There is no significant difference in user satisfaction between AUIs obtained
with reward models derived from predictive HCI models that incorporate HF and
non-adaptive interfaces.

The scope of RQ1 lies in training the RL agent with the two different reward
models, while the scope of RQ2 and RQ3 is the actual usage of systems (using
UIs that do or do not employ the RL agent) by end users. The goal of the
statistical analysis will be to reject these hypotheses and possibly to accept
the alternative ones (e.g., $H_{a1}$ = $\neg H_{n1}$). All the hypotheses are
two-sided because we did not postulate that any effect would occur as a result
of different reward models usage.

Figure 2: The RL agent employing two strategies to obtain reward predictions:
predictive HCI models only (orange) and predictive HCI models with human
feedback (green)

###  III-B Variables

This section outlines the variables and measurement scales, and how they will
be operationalized to ensure reliable data collection. Statistical analyses
are detailed in Section III.E.

####  III-B1 Independent variables

The main independent variable in this study is the type of reward model
employed by the two RL-based UI adaptation strategies that will be implemented
as part of our experimentation. The scale of this variable is nominal, and can
assume two possible values: adaptive UI using predictive HCI models only (HCI)
and adaptive UI using predictive HCI models augmented with HF (HCI&HF).
However, to understand the gain in the improvement of UX when compared to a
baseline (non-adaptive UI), we introduce a third system without any adaptive
features (non-adaptive, NA). The secondary independent variable is the
application domain (i.e., adaptive system), which is a nominal variable with
three possible values: Sports, Courses and Trips. The former is an online
sporting goods store (e-commerce domain) while the latter is a Course
management system (e-learning domain).

####  III-B2 Dependent variables

The dependent variable in this study is user experience (UX). It is defined by
the ISO 9241-210: 2010 as ”a person’s perceptions and responses that result
from the use and/or anticipated use of a product, system or service”. In
contrast to task-oriented interactions, UX represents a focus on “experience”,
encompassing also hedonic qualities, emotions and affect (e.g., interested,
enthusiastic, irritable) that people experience while interacting with
software systems. It can be operationalized in several ways as this is a
complex concept with several dimensions. In this study, we measure UX in terms
of user engagement and user satisfaction.

User engagement is a quality of user experience with software systems that is
characterised among others by aesthetic, sensory appeal, perceived control and
time, awareness, motivation, and affect [26] [27] [28]. It will be measured in
two different stages: 1) when training the RL model (for calculating reward
predictions using predictive HCI models that employs behaviour logging
approaches), and 2) during the user interaction with the system (i.e.,
experimental task). In the fist stage, user engagement will be operationalized
using a set of metrics collected from the literature [28], [29], [30] (i.e.,
individual event counts, relative frequencies of events, total number of user
actions, and task completion time); while, in the second stage, it will be
operationalized using the UES questionnaire in a post-experimental task.

On the other hand, user satisfaction is a measure of the quality of the UX and
refers to the extent to which a user’s expectations are met [31]. It will be
measured after the user interaction with each of the adaptive systems (i.e.,
post-experimental task) using the Questionnaire for User Interaction
Satisfaction (QUIS) [22]. It contains a measure of overall system satisfaction
along six sub-scales and measures of four specific UI factors (screen factors,
terminology and system feedback, learning factors, and system capabilities).
Each area measures the overall satisfaction on a 10-point scale.

###  III-C Subjects

Participants for this study will be recruited using a convenience sampling
technique, a non-probability sampling method that selects individuals based on
their availability and willingness to participate [32]. The study will target
undergraduate and Master’s students in computer science at the Universitat
Politècnica de València. We will will recruit participants during class time,
providing a brief overview of the study and inviting interested students to
participate. To ensure the voluntary nature of participation, we will
emphasise that all participants have the opportunity to decline without any
negative consequences. Once the participants have been selected, we will give
them the informed consent document. The experiment will be conducted online
and will follow the university IRB protocol. In particular, the consent form
will state that no personal data is collected, or if it is collected, that it
will not be published, and will be destroyed.

###  III-D Design

TABLE I: The treatment sequence with three techniques (NA, HCI and HCI&HF) and three application domains (Trips, Sports and Courses) Domain | Trips | Sports | Courses
---|---|---|---
Period | Period 1 | Period 2 | Period 3
Technique |  NA |  HCI |  HCI&HF |  NA |  HCI |  HCI&HF |  NA |  HCI |  HCI&HF
Group 1 | x | - | - | - | x | - | - | - | x
Group 2 | x | - | - | - | - | x | - | x | -
Group 3 | - | x | - | x | - | - | - | - | x
Group 4 | - | x | - | - | - | x | x | - | -
Group 5 | - | - | x | x | - | - | - | x | -
Group 6 | - | - | x | - | x | - | x | - | -

The experiment is designed as a balanced within-subject three-treatment
factorial crossover design. We will carry out a power analysis to allow us to
determine the appropriate sample size to detect an effect of medium size. We
chose this design because it addresses the issue of small sample sizes and
increases the sensitivity of experiments. In a balanced crossover design the
measures are taken several times from a participant (i.e., a participant is
assigned to a sequence of treatments). We follow the guidelines proposed by
Vegas et al. [33] to define the crossover design. In particular, we will
analyse not only the effects of the treatments (i.e., NA, HCI and HCI&HF) on
the dependent variables, but also the effects of critical crossover variables
(i.e., period, sequence and carryover). In this scenario, it is necessary to
differentiate between the concepts of period and session. A period is defined
by the application of one treatment by one participant to one application
domain (adaptive system), whereas a session is a portion of time taken by a
subject to complete (one or more) experimental tasks [33]. We consequently
will have three periods, since each participant had to perform two treatments
and for reasons of the students’ class timetable. We, therefore, will carry
out one period in a session. Carryover is the persistence of the effect of one
treatment when another treatment is applied later. The objective is to find
out whether these additional factors are influencing the dependent variables.
Table I shows that we have a special type of design called a factorial
crossover design, which has the same number of periods as treatments.

Each period will be assigned to a domain and each group will follow a
different sequence of adaptation techniques. Producing 6 different sequences
(see Table I). In the first period, every group will interact with a Trip
Planner system. Groups 1 and 2 will use the system without adaptation
capabilities (NA), while Groups 3 and 4 will interact with AUI that employs a
RL agent with predictive HCI models (HCI) and Groups 5 and 6 will interact
with AUI that employs a RL agent with predictive HCI models and Human Feedback
(HCI&HF). In the second period, everyone will interact with an e-commerce
system (Sporting Goods Store). Groups 3 and 5 will use the system without
adaptation capabilities (NA), while Groups 1 and 6 will interact with AUI-HCI
and, Groups 2 and 4 will interact with AUI-HCI&HF. In the third period,
everyone will interact with an e-learning system (Courses Management system).
Groups 4 and 6 will use the system without adaptation capabilities (NA), while
Groups 2 and 5 will interact with AUI-HCI and, Groups 1 and 3 will interact
with AUI-HCI&HF. We carefully selected these sequences to ensure that any
potential order effects are minimised. In this scenario, we do not believe
that there is the possibility that any of the sequences would have improved
the experimental results.

We choose the trip, sporting, and courses systems from the e-commerce and
e-learning domains as application domains for this experiment because, these
domains are representative of different types of software products and user
requirement needs. Moreover, these domains are popular and widely used, making
them relevant for a wide range of users. Finally, the selected systems have
similar complexity.

###  III-E Analysis plan

The results of the experiment will be collected using i) the user engagement
computed with the predictive HCI models exclusively and ii) predictive HCI
models with HF. Additionally, the participants will carried out a post-
experimental task that we will allow us to measure their user satisfaction by
using the QUIS questionnaire.

We will use descriptive statistics, violin plots, and statistical tests to
analyse the data collected from the experiment. As is usual, we accepted a
probability of 5% of committing a Type-I Error in all the statistical tests.

We will first carry out a descriptive study of the measures for the dependent
variables. Then, as a crossover design will be used in the study, it is
necessary to analyse the experiment factors including periods, sequences, and
carryover. To test the formulated hypotheses, the Linear Mixed Model (LMM)
will be employed. Following the guidelines proposed by Vegas et al. [33], the
LMM includes the following fixed factors: Reward model technique (treatment),
period (confounded with the application domain), and sequence (confounded with
carryover and period-technique interaction), and subject as a random factor
nested within the sequence. The LMM will be used to assess whether these
factors have influenced the results. All the assumptions of LMMs will be
tested and reported. In order to apply the LMM, the residuals had to meet the
condition of normality [33]. To ensure that the model was valid, we therefore
will use the Shapiro-Wilk test if the sample size ends up being smaller than
50 and Kolmogorov–Smirnov if the sample size is higher than 50 to confirm the
normality of the residuals. We will then apply the LMM to each dependent
variable in order to assess whether the period (confounded with the
application domain), sequences (confounded with period-technique and
carryover) or technique (treatment) had statistical significance.

We will report the results of the QUIS scores for the experiment. We will also
assess the questionnaire quality in terms of its reliability, validity and
sensitivity. Then, we will measure the effect size to assess the magnitude of
differences caused by the treatments. The effect size of the treatments should
be measured only if the period, sequence or any blocking variables have no
bearing, and there is no carryover [34]. To this end, we will use Cohen’s d.

###  III-F Threats to validity

In this section, we discuss the issues that will may threat the validity of
our experiment and how we will mitigate them [35]. One potential threat to
internal validity is the Hawthorne effect [36], where participants may alter
their behaviour due to being observed. To mitigate this threat, participants
will be instructed to behave as they would in a natural setting. Another
potential threat is the maturation effect, where participants’ responses may
change over time due to natural changes such as fatigue or boredom. To
mitigate this, we will have a long break in the middle of each session. Also,
to mitigate potential threats related to participant’s interaction,
participants will be recruited from different academic degrees (i.e.,
Bachelor’s and Master’s in Computer Science) which happen in different
semesters. Participants from these groups are not expected to interact with
each other during the study periods/sessions.

To address the potential threat to conclusion validity, a sufficient number of
participants will be recruited to ensure adequate statistical power and the
proper statistical tests will be performed for the variables and their
assumptions [37].

The potential threats to the construct validity, are the validity and
reliability of the HCI and HCI&HF models and the questionnaires used to
measure user satisfaction and engagement. To mitigate these threats, the
models will be based on existing research [28, 29, 30] and validated by domain
experts. To validate the measures of user engagement obtained with the
predictive HCI models, during the interaction, we will gather the
participants’ engagement through User Engagement Scale (UES) [21] and the
participants’ satisfaction through QUIS questionnaire [22], which are
empirically validated questionnaires, as post-experimental tasks.

To increase external validity, we will address the potential threat of
participants’ behaviour not generalising to real-world situations by using a
realistic scenario for each domain to make the tasks more meaningful.
Additionally, we will design the tasks used to measure the effectiveness of
the adaptive UIs to reflect realistic browsing and purchasing behaviours.
Nevertheless, the representativeness of the results may be affected by the
profile of the participants. Replications with industry participants are
necessary.

##  IV Execution Plan

The experiment will be conducted over the course of two weeks, with each
participant attending three sessions. Before the first session, all
participants will complete a brief demographic survey and will be assigned to
one of the six groups. In the first session, they will interact with a Trip
Planner system using the three approaches (NA, HCI, HCI&HF). Groups 1 and 2
will use the system without adaptation capabilities (NA). Groups 3 and 4 will
interact with AUI-HCI and, Groups 5 and 6 will interact with AUI-HCI&HF. In
the second session, participants will switch to another approach in an
e-commerce system (Sporting Goods Store). Specifically, Groups 3 and 5 will
use the NA, while Groups 1 and 6 will use the HCI and, Groups 2 and 4 will use
the HCI&HF. Finally, in the third session, participants will switch to the
last approach that they haven’t used in an an e-learning system (Courses
Management system). Groups 4 and 6 will use NA, while Groups 2 and 5 will use
HCI and, Groups 1 and 3 will use HCI&HF.

Each session will consist of the following steps:

  1. 1.

Introduction and task explanation.

  2. 2.

Task execution: Participants will perform the tasks using the assigned AUI.
The tasks will be defined once the adaptations for the selected sytems are
defined.

  3. 3.

Post-task questionnaires: The participant will be asked to fill the QUIS and
the UES to evaluate their satisfaction and engagement with the UI,
respectively. The questionnaires will be administered through an Excel file
and participants will have to complete after each session.

All sessions will be conducted in a controlled lab environment with identical
equipment and software configurations. Participants will be seated at a desk
with a computer screen, mouse, and keyboard. The order of the sessions will be
counterbalanced to control for any potential order effects. Each session will
last, at most, 120 minutes. However, participants will not be required to
complete the tasks within this time frame, and there will be no time pressure
on them to do so.

## Acknowledgment

This work is supported by the AKILA project (CIAICO/2021/303) funded by the
Generalitat Valenciana (GVA). Daniel Gaspar-Figueiredo is funded by the GVA
under the grant ACIF/2021/172, which is cofunded by the European Union through
the ESF.

## References

  * [1] G. Chaslot, S. Bakkes, I. Szita, and P. Spronck, “Monte-carlo tree search: A new framework for game ai,” _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , vol. 4, no. 1, pp. 216–217, 2021.
  * [2] P. A. Akiki, A. K. Bandara, and Y. Yu, “Adaptive model-driven user interface development systems,” _ACM Comput. Surv._ , vol. 47, no. 1, may 2014. [Online]. Available: https://doi.org/10.1145/2597999
  * [3] G. Viano, A. Parodi, J. Alty, C. Khalil, I. Angulo, D. Biglino, M. Crampes, C. Vaudry, V. Daurensan, and P. Lachaud, “Adaptive user interface for process control based on multi-agent approach,” in _Proc. of the Working Conference on Advanced Visual Interfaces_ , ser. AVI ’00. New York, NY, USA: Association for Computing Machinery, 2000, p. 201–204. [Online]. Available: https://doi.org/10.1145/345513.345316
  * [4] S. Abrahão, E. Insfrán, A. Sluÿters, and J. Vanderdonckt, “Model-based intelligent user interface adaptation: challenges and future directions,” _Software and Systems Modeling_ , vol. 20, no. 5, pp. 1335–1349, 2021.
  * [5] J. D. Lomas, J. Forlizzi, N. Poonwala, N. Patel, S. Shodhan, K. Patel, K. Koedinger, and E. Brunskill, “Interface design optimization as a multi-armed bandit problem,” in _Proc. of the 2016 CHI Conference on Human Factors in Computing Systems_. ACM, 2016, p. 4142–4153.
  * [6] J. J. Dudley, J. T. Jacques, and P. O. Kristensson, “Crowdsourcing interface feature design with bayesian optimization,” in _Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems_ , ser. CHI ’19. New York, NY, USA: ACM, 2019, p. 1–12.
  * [7] K. Todi, G. Bailly, L. Leiva, and A. Oulasvirta, “Adapting user interfaces with model-based reinforcement learning,” in _Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems_ , ser. CHI ’21. New York, NY, USA: Association for Computing Machinery, 2021. [Online]. Available: https://doi.org/10.1145/3411764.3445497
  * [8] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.
  * [9] L. P. Kaelbling, M. L. Littman, and A. W. Moore, “Reinforcement learning: A survey,” _Journal of artificial intelligence research_ , vol. 4, pp. 237–285, 1996.
  * [10] A. Zap, T. Joppen, and J. Fürnkranz, “Deep ordinal reinforcement learning,” in _Machine Learning and Knowledge Discovery in Databases_ , U. Brefeld, E. Fromont, A. Hotho, A. Knobbe, M. Maathuis, and C. Robardet, Eds. Springer International Publishing, 2020, pp. 3–18.
  * [11] D. Schmidt, N. Moran, J. Rosenfeld, J. Rosenthal, and J. Yedidia, “Self-play learning without a reward metric,” 12 2019.
  * [12] X. Chen, L. Yao, X. Wang, A. Sun, and Q. Z. Sheng, “Generative adversarial reward learning for generalized behavior tendency inference,” _IEEE Trans on Knowledge and Data Engineering_ , pp. 1–12, 2022.
  * [13] S. Armstrong, J. Leike, L. Orseau, and S. Legg, “Pitfalls of learning a reward function online,” in _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence_ , ser. IJCAI’20, 2021.
  * [14] P. F. Christiano, J. Leike, T. Brown, M. Martic, S. Legg, and D. Amodei, “Deep reinforcement learning from human preferences,” in _Advances in Neural Information Processing Systems_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds., vol. 30. Curran Associates, Inc., 2017.
  * [15] C. Paton, A. W. Kushniruk, E. M. Borycki, M. English, and J. Warren, “Improving the usability and safety of digital health systems: The role of predictive Human-Computer interaction modeling,” _J Med Internet Res_ , vol. 23, no. 5, p. e25281, May 2021.
  * [16] N. Stiennon, L. Ouyang, J. Wu, D. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. F. Christiano, “Learning to summarize with human feedback,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 3008–3021, 2020.
  * [17] D. Gaspar-Figueiredo, S. Abrahao, E. Insfran, and M. Fernández-Diego, “Reinforcement learning agent environment for adaptation of user interfaces (in Spanish),” in _JISBD2023_. SISTEDES, 2023 (submitted on April).
  * [18] T. Langerak, S. Christen, M. Albaba, C. Gebhardt, and O. Hilliges, “Marlui: Multi-agent reinforcement learning for goal-agnostic adaptive uis,” _arXiv preprint arXiv:2209.12660_ , 2022.
  * [19] J. Schrittwieser, T. K. Hubert, A. Mandhane, M. Barekatain, I. Antonoglou, and D. Silver, “Online and offline reinforcement learning by planning with a learned model,” in _Advances in Neural Information Processing Systems_ , A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., 2021. [Online]. Available: https://openreview.net/forum?id=HKtsGW-lNbw
  * [20] V. R. Basili, G. Caldiera, and H. D. Rombach, “The goal question metric approach,” 1994.
  * [21] H. L. O’Brien, P. Cairns, and M. Hall, “A practical approach to measuring user engagement with the refined user engagement scale (ues) and new ues short form,” _International Journal of Human-Computer Studies_ , vol. 112, pp. 28–39, 2018.
  * [22] K. L. Norman, B. Shneiderman, B. Harper, and L. Slaughter, “Questionnaire for user interaction satisfaction,” Available at: https://site.unibo.it/hfrs/en/questionnaire-and-scales-2/quis, 1998.
  * [23] T. Lavie and J. Meyer, “Benefits and costs of adaptive user interfaces,” _International Journal of Human-Computer Studies_ , vol. 68, no. 8, pp. 508 – 524, 2010. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S1071581910000145
  * [24] C. Qiao, J. Wang, Y. Wang, Y. Liu, and H. Tuo, “Understanding and improving user engagement in adaptive video streaming,” in _2021 IEEE/ACM 29th International Symposium on Quality of Service (IWQOS)_ , 2021, pp. 1–10.
  * [25] A. X. Li, X. Lou, P. Hansen, and R. Peng, “Improving the User Engagement in Large Display Using Distance-Driven Adaptive Interface,” _Interacting with Computers_ , vol. 28, no. 4, pp. 462–478, 06 2016. [Online]. Available: https://doi.org/10.1093/iwc/iwv021
  * [26] H. L. O’Brien and E. G. Toms, “What is user engagement? a conceptual framework for defining user engagement with technology,” _Journal of the American society for Information Science and Technology_ , vol. 59, no. 6, pp. 938–955, 2008.
  * [27] K. Doherty and G. Doherty, “Engagement in hci: conception, theory and measurement,” _ACM Computing Surveys (CSUR)_ , vol. 51, no. 5, pp. 1–39, 2018.
  * [28] J. Lehmann, M. Lalmas, E. Yom-Tov, and G. Dupret, “Models of user engagement,” in _User Modeling, Adaptation, and Personalization_ , J. Masthoff, B. Mobasher, M. C. Desmarais, and R. Nkambou, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 164–175.
  * [29] E. Barbaro, E. M. Grua, I. Malavolta, M. Stercevic, E. Weusthof, and J. van den Hoven, “Modelling and predicting user engagement in mobile applications,” _Data Science_ , vol. 3, no. 2, pp. 61–77, 2020.
  * [30] J. Carlton, A. Brown, C. Jay, and J. Keane, “Using interaction data to predict engagement with interactive media,” in _Proceedings of the 29th ACM International Conference on Multimedia_ , 2021, pp. 1258–1266.
  * [31] “Ergonomics of human-system interaction-Part 11: Usability: Definitions and concepts.” International Organization for Standardization, Tech. Rep., 2018.
  * [32] S. Baltes and P. Ralph, “Sampling in software engineering research: a critical review and guidelines,” _Empirical Software Engineering_ , vol. 27, no. 4, p. 94, Apr 2022. [Online]. Available: https://doi.org/10.1007/s10664-021-10072-8
  * [33] S. Vegas, C. Apa, and N. Juristo, “Cross-over designs in software engineering experiments: Benefits and perils,” _IEEE Transactions on Software Engineering_ , vol. 42, pp. 1–1, 01 2015.
  * [34] J. C. Carver, “Towards reporting guidelines for experimental replications: A proposal,” in _1st international workshop on replication in empirical software engineering_ , vol. 1, 2010, pp. 1–4.
  * [35] C. Wohlin, P. Runeson, M. Höst, M. C. Ohlsson, B. Regnell, and A. Wesslén, _Empirical Strategies_. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 9–36.
  * [36] J. G. Adair, “The hawthorne effect: a reconsideration of the methodological artifact.” _Journal of applied psychology_ , vol. 69, no. 2, p. 334, 1984.
  * [37] M. K.D., “Applied statistics for software managers,” _Applied Statistics for Software Managers_ , 2002. [Online]. Available: https://cir.nii.ac.jp/crid/1573668924056253312


# Sparse Actuator Scheduling for Discrete-Time Linear Dynamical Systems

Krishna Praveen V. S. Kondapi1, Chandrasekhar Sriram2, Geethu Joseph3 and
Chandra R. Murthy1
Fellow, IEEE 1K. Kondapi and C. R. Murthy are with the Dept. of ECE at the
Indian Institute of Science (IISc), Bangalore 560012, India. Emails:
{praveenkvsk<EMAIL_ADDRESS>Sriram is with Texas Instruments India
Pvt. Ltd. He was at the Dept. of ECE, IISc, during the course of this work.
Email<EMAIL_ADDRESS>Joseph is with the Faculty of
Electrical Engineering, Mathematics, and Computer Science at the Delft
University of Technology, Delft 2628 CD, Netherlands. Email:
<EMAIL_ADDRESS>
###### Abstract

We consider the control of discrete-time linear dynamical systems using sparse
inputs where we limit the number of active actuators at every time step. We
develop an algorithm for determining a sparse actuator schedule that ensures
the existence of a sparse control input sequence, following the schedule, that
takes the system from any given initial state to any desired final state.
Since such an actuator schedule is not unique, we look for a schedule that
minimizes the energy of sparse inputs. For this, we optimize the trace of the
inverse of the resulting controllability Gramian, which is an approximate
measure of the average energy of the inputs. We present a greedy algorithm
along with its theoretical guarantees. Finally, we empirically show that our
greedy algorithm ensures the controllability of the linear system with a small
number of active actuators per time step without a significant average energy
expenditure compared to the fully actuated system.

###### Index Terms:

Greedy algorithm, controllability, time-varying schedule, sparse actuator
selections, piecewise sparsity.

##  I Introduction

The field of networked control systems, in which the controllers, sensors, and
actuators communicate over a band-limited network to achieve a given control
objective, is a growing area of research [1, 2, 3]. Due to the bandwidth
constraints, these systems demand communication-efficient control inputs. One
way to reduce the communication cost is to use only a few available actuators
at any given time instant, i.e., the number of nonzero entries of the control
input is small compared to its length, leading to a _sparse control input_ [4,
3]. The sparse vectors admit compact representation in a suitable basis [5],
and thus, save bandwidth. Sparse control also finds applications in resource-
constrained systems such as environmental control systems and network opinion
dynamics [6, 7]. Motivated by this, we consider the problem of designing an
actuator schedule for sparse control inputs to drive the system to any given
desired state.

The controllability of a discrete-time linear dynamical system (LDS) using
sparse inputs, along with its necessary and sufficient conditions, was defined
and developed in [8]. Here, at each time step, the input can utilize at most
$s$ actuators, but the selected subset of $s$ actuators can be time-varying.
However, the work does not provide the actuator schedule or design the sparse
inputs. Some researchers have considered the actuator scheduling for
continuous-time systems by maximizing the trace of the controllability Gramian
with a limit on the number of active actuators per time step [9, 10, 11, 12].
This problem has been extended to cases where system dynamics are unknown,
resulting in the development of an online, data-driven approach for learning
the optimal actuator placement [11, 12]. Some works have considered a
restrictive variant where the subset of chosen actuators remains fixed across
time [13, 14, 15]. However, time-varying actuator scheduling can potentially
ensure the controllability of systems that are uncontrollable systems when
using inputs with fixed support, and could guide the LDS to the desired state
faster than time-invariant actuator scheduling. A variant of time-varying
sparse actuator scheduling problem considered in the literature only limits
the _average_ number of active actuators across all the time steps [16, 17].
They developed schedulers that yield a Gramian matrix that approximates the
Gramian matrix of the fully actuated system. An alternative approach for the
time-varying actuator scheduling problem is using a linear-quadratic regulator
or linear-quadratic-Gaussian control [18, 19]. The authors in [20] also
consider a time-varying sparse schedule with the goal of obtaining
controllability with a symmetric transfer matrix $\boldsymbol{A}$. To the best
of our knowledge, our problem of identifying a time-varying sparse actuator
schedule that ensures controllability with minimal control energy has not been
explored in the literature.

We formulate our actuator scheduling problem as minimizing the trace of the
inverse of the controllability Gramian, a widely used metric for quantifying
average control enegry [16]. This optimization is subject to a constraint
limiting the active actuators to at most $s$ per time step. The specific
contributions of this paper are as follows:

  * •

We show that our objective function exhibits approximate supermodularity, and
the sparsity constraint is a matroid. This result leads to a greedy algorithm
for finding the sparse actuator schedule with provable guarantees.

  * •

Using our algorithm, we empirically study the tradeoff between the sparsity
and average energy for time-invariant and time-varying schedules. We observe
that, for large random systems with sparse and time-varying schedules, the
increase in the average control energy compared to the average energy required
by a fully actuated system is inversely proportional to the fraction of active
actuators.

Overall, we present a systematic study of sparse time-varying actuator
scheduling, develop a novel scheduling algorithm with theoretical guarantees,
and empirically elucidate its energy requirements.

##  II Actuator Scheduling Problem

We consider a discrete-time LDS whose dynamics are governed by the following
equation:

$\boldsymbol{x}(k+1)=\boldsymbol{A}\boldsymbol{x}(k)+\boldsymbol{B}\boldsymbol{u}(k),$
(1)

where $k=0,1,\ldots$ is the integer time index. Here,
$\boldsymbol{x}(k)\in\mathbb{R}^{n}$ is the system state and
$\boldsymbol{u}(k)\in\mathbb{R}^{m}$ is the input to the system. The matrices
$\boldsymbol{A}\in\mathbb{R}^{n\times n}$ and
$\boldsymbol{B}\in\mathbb{R}^{n\times m}$ are the system transfer matrix and
the input matrix, respectively. We aim to design $s$-sparse inputs, i.e.,
$\|\boldsymbol{u}(k)\|_{0}\leq s$, for all values of $k$ to drive the system
to a desired state. Finding sparse inputs is hard because of the nonconvex
sparsity constraint. However, if the support $\mathcal{S}_{k}$ of
$\boldsymbol{u}_{k}$ is known, we can easily find the sparse vectors using
techniques like the least squares method. Therefore, we aim to design a sparse
actuator schedule (support of the sparse inputs), independent of the initial
and final state of the LDS, that can drive the LDS to any given desired state
in $K$ time steps.

We denote the sparse actuator schedule by
$(\mathcal{S}_{0},\mathcal{S}_{1},\ldots,\mathcal{S}_{K-1})$, where,
$\mathcal{S}_{k}\subseteq\\{1,2,\ldots,m\\}$ and $|\mathcal{S}_{k}|\leq s$ for
all values of $k$ to satisfy the sparsity constraint.  This sparsity structure
is referred to as piecewise sparsity. It is known that for any $s$-sparse
controllable LDS, we can find a finite $K$ and sparse actuator schedule
$(\mathcal{S}_{0},\mathcal{S}_{1},\ldots,\mathcal{S}_{K-1})$ with
$|\mathcal{S}_{k}|\leq s$ such that

$\mathsf{Rank}\left\\{\begin{bmatrix}\boldsymbol{A}^{K-1}\boldsymbol{B}_{\mathcal{S}_{0}}&\boldsymbol{A}^{K-2}\boldsymbol{B}_{\mathcal{S}_{1}}&\ldots&\boldsymbol{B}_{\mathcal{S}_{K-1}}\end{bmatrix}\right\\}=n.$
(2)

Sparse controllability is equivalent to two conditions being satisfied: the
system is controllable and $s\geq
n-\mathsf{Rank}\left\\{\boldsymbol{A}\right\\}$ [8]. So, in the sequel, to
ensure that the problem is feasible, we assume that these two conditions hold.

Further, for an $s$-sparse controllable LDS, the minimum number of time steps
$K$ required to ensure controllability is bounded as [8]

$\frac{n}{s}\leq
K\leq\min\left(q\left\lceil\frac{\mathsf{Rank}\left\\{\boldsymbol{B}\right\\}}{s}\right\rceil,n-s+1\right)\leq
n.$ (3)

where $q$ is the degree of the minimum polynomial of $\boldsymbol{A}$. For
simplicity, we let $K=n$. Our goal is to find an actuator schedule
$\mathcal{S}=(\mathcal{S}_{0},\mathcal{S}_{1},\ldots,\mathcal{S}_{n-1})\in\Phi$
such that (2) holds, where the feasible set $\Phi$ for $\mathcal{S}$ is
defined as

$\Phi\\!=\\!\left\\{\\!(\mathcal{S}_{0},\mathcal{S}_{1},\ldots,\mathcal{S}_{n-1})\\!\\!:\mathcal{S}_{k}\\!\subseteq\\!\\{1,2,\ldots,m\\},|\mathcal{S}_{k}|\leq
s,\forall k\right\\}.$ (4)

The rank of the controllability matrix can be analyzed using the Gramian
matrix. For any actuator schedule
$\mathcal{S}=(\mathcal{S}_{0},\mathcal{S}_{1},\ldots,\mathcal{S}_{n-1})\in\Phi$,
the corresponding Gramian is

$\boldsymbol{W}_{\mathcal{S}}=\sum_{k=1}^{n}\boldsymbol{A}^{k-1}\boldsymbol{B}_{\mathcal{S}_{n-k}}\boldsymbol{B}_{\mathcal{S}_{n-k}}^{\mathsf{T}}(\boldsymbol{A}^{k-1})^{\mathsf{T}}.$
(5)

Our goal is to select the actuator schedule $\mathcal{S}$ so that
$\mathsf{Rank}\left\\{\boldsymbol{W}_{\mathcal{S}}\right\\}=n$, which in turn
ensures that the system is controllable. However, the solution does not need
to be unique. Therefore, we look at minimizing
$\mathsf{Tr}\left\\{\boldsymbol{W}_{\mathcal{S}}^{-1}\right\\}$ which is a
popular measure of the “difficulty of controllability” [21]. It represents the
average energy to drive the LDS from $\boldsymbol{x}(0)=\boldsymbol{0}$ to a
uniformly random point on the unit sphere. We present a greedy algorithm to
minimize $\mathsf{Tr}\left\\{\boldsymbol{W}_{\mathcal{S}}^{-1}\right\\}$ next.

##  III Greedy Scheduling Algorithm

First, we note that
$\mathsf{Tr}\left\\{\boldsymbol{W}_{\mathcal{S}}^{-1}\right\\}$ is not well-
defined if $\boldsymbol{W}_{\mathcal{S}}$ is rank-deficient. So, we use the
lower bound
$\mathsf{Tr}\left\\{(\boldsymbol{W}_{\mathcal{S}}+\epsilon\boldsymbol{I})^{-1}\right\\}(\leq\mathsf{Tr}\left\\{(\boldsymbol{W}_{\mathcal{S}})^{-1}\right\\})$
as an alternative cost function, referred to as the $\epsilon$-auxiliary
energy, for some small $\epsilon>0$. The term $\epsilon\boldsymbol{I}$
guarantees that the inverse exists and the cost function is well-defined for
any schedule. Thus, our new optimization problem is

$\underset{\mathcal{S}\in\Phi}{\arg\min}\;\mathsf{Tr}\left\\{(\boldsymbol{W}_{\mathcal{S}}+\epsilon\boldsymbol{I})^{-1}\right\\}.$
(6)

where $\Phi$ is defined in (4) and $\boldsymbol{W}_{\mathcal{S}}$ is given by
(5). As $\epsilon$ decreases, (6) becomes a better approximation of the
original objective of attaining full rank matrix
$\boldsymbol{W}_{\mathcal{S}}$.

Next, we observe that any actuator schedule of length $n$ can be represented
using a subset of the set

$\mathcal{V}=\\{(k,j)|k=0,1,\ldots,n-1,\;j=1,2,\ldots,m\\}.$ (7)

Here, $k$ represents the time index, and $j$ represents the actuator index.
Let $2^{\mathcal{V}}$ denote the power set of $\mathcal{V}$. It is clear that
there is a natural bijection between any $\mathcal{T}\in 2^{\mathcal{V}}$ and
the corresponding actuator schedule:

$\mathcal{S}(\mathcal{T})=(\mathcal{S}_{0},\mathcal{S}_{1},\ldots,\mathcal{S}_{n-1})\;\;\text{with}\;\;\mathcal{S}_{k}=\\{j:(k,j)\in\mathcal{T}\\}.$
(8)

Therefore, the problem in (6) can be written using $\mathcal{V}$ as

$\underset{\mathcal{T}\in
2^{\mathcal{V}}}{\min}\;\mathsf{Tr}\left\\{(\boldsymbol{W}_{\mathcal{S}(\mathcal{T})}+\epsilon\boldsymbol{I})^{-1}\right\\}\;\text{s.t.}\;\mathcal{S}(\mathcal{T})\in\Phi.$
(9)

Using the new formulation, the greedy algorithm starts with $\mathcal{T}$
being the empty set and finds the element from $\mathcal{V}$ which when added
to $\mathcal{T}$ minimizes the cost function. Specifically, in the $r$th
iteration of the algorithm, let $\mathcal{T}^{(r)}$ set of indices collected
up to the previous iteration. Then, we find

$(k^{*},j^{*})=\underset{(k,j)\in\mathcal{V}^{(r)}}{\arg\min}\mathsf{Tr}\left\\{(\boldsymbol{W}_{\mathcal{S}(\mathcal{T}^{(r)}\cup\\{(k,j)\\})}+{\epsilon}\boldsymbol{I})^{-1}\right\\},$
(10)

where $\mathcal{V}^{(r)}\subseteq\mathcal{V}\setminus\mathcal{T}^{(r)}$ is
obtained by removing all infeasible index pairs, i.e.,

$\mathcal{V}^{(r)}=\left\\{(i,j)\in\mathcal{V}\setminus\mathcal{T}^{(r)}:\mathcal{S}(\mathcal{T}^{(r)}\cup(i,j))\in\Phi\right\\}.$
(11)

Finally, to complete the algorithm’s description, we must choose $\epsilon$.
We start with some $\epsilon_{0}>0$ and repeat the greedy algorithm (outer
loop) for decreasing values of $\epsilon$ until we obtain a full-rank Gramian
matrix. The overall procedure is outlined in Algorithm 1.

Algorithm 1 Greedy actuator scheduling

1:System matrices: $\boldsymbol{A},\boldsymbol{B}$; sparsity $s$

2: Parameters: $\epsilon_{0}>0$, $c>1$

3:Initialize outer loop index $t=0$

4:do

5: Initialize $r=1$, $\mathcal{T}^{(r)}=\emptyset$,
$\mathcal{V}^{(r)}=\mathcal{V}$

6: while $\mathcal{V}^{(r)}\neq\emptyset$ do

7: $(k^{*},j^{*})$ using (10) with $\epsilon=\epsilon_{t}$

8: $\mathcal{T}^{(r+1)}=\mathcal{T}^{(r)}\cup\\{(k^{*},j^{*})\\}$

9:
$\mathcal{S}=(\mathcal{S}_{0},\mathcal{S}_{1},\ldots,\mathcal{S}_{n-1})=\mathcal{S}(\mathcal{T}^{(r+1)})$

10: if $|\mathcal{S}_{k^{*}}|=s$ then

11:
$\mathcal{V}^{(r+1)}=\mathcal{V}^{(r)}\setminus\\{(k^{*},j),\;j=1,2,\ldots,m\\}$

12: else

13: $\mathcal{V}^{(r+1)}=\mathcal{V}^{(r)}\setminus\\{(k^{*},j^{*})\\}$

14: end if

15: $r\leftarrow r+1$

16: end while

17: $t\leftarrow t+1$, $\epsilon_{t+1}=\epsilon_{t}/c$

18:while $\mathsf{Rank}\left\\{\boldsymbol{W}_{\mathcal{S}}\right\\}<n$

19:Actuator schedule $\mathcal{S}$

The intuition behind the greedy algorithm is as follows. For a given value of
$\epsilon$, let $\mathcal{S}^{(r)}$ be the actuator schedule obtained in the
$r$th iteration of the greedy algorithm. Suppose that
$\mathsf{Rank}\left\\{\boldsymbol{W}_{\mathcal{S}^{(r)}}\right\\}=R$, which
implies it has $R$ nonzero eigenvalues $\\{\lambda_{i}\\}_{i=1}^{R}$. Then,
for a small $\epsilon$, the objective function is

$\displaystyle\mathsf{Tr}\left\\{(\boldsymbol{W}_{\mathcal{S}^{(r)}}+\epsilon\boldsymbol{I})^{-1}\right\\}$
$\displaystyle=\sum_{i=1}^{R}\frac{1}{\lambda_{i}+\epsilon}+{\frac{n-R}{\epsilon}}.$
(12)

The term $(n-R)/\epsilon$ acts as the penalty added to the objective function
when $\boldsymbol{W}_{\mathcal{S}^{(r)}}$ is rank deficient. Our next result
shows that the greedy algorithm improves the rank of the resulting Grammian
until the rank becomes $n$ under the availability of such actuators for
sufficiently small $\epsilon$.

###### Proposition 1

For a given outer loop iteration index $t$ of Algorithm 1, let the $r$th
(inner) iteration start with $\mathcal{T}^{(r)}$ and its search space be
$\mathcal{V}^{(r)}$ be as defined in (11). Suppose that the following set,

$\left\\{v\in\mathcal{V}^{(r)}:\mathsf{Rank}\left\\{\boldsymbol{W}_{\mathcal{S}(\mathcal{T}^{(r)}\cup\\{v\\})}\right\\}>\mathsf{Rank}\left\\{\boldsymbol{W}_{\mathcal{S}(\mathcal{T}^{(r)})}\right\\}\right\\},$
(13)

is nonempty. Then, there exists $\epsilon^{*}>0$ such that if
$\epsilon_{t}<\epsilon^{*}$, the next iteration of the greedy algorithm
satisfies

$\mathsf{Rank}\left\\{\boldsymbol{W}_{\mathcal{S}(\mathcal{T}^{(r+1)})}\right\\}=\mathsf{Rank}\left\\{\boldsymbol{W}_{\mathcal{S}(\mathcal{T}^{(r)})}\right\\}+1.$
(14)

Here, the schedule $\mathcal{S}(\cdot)$ is defined in (8) and the resulting
Gramian is defined in (5).

###### Proof:

See Appendix A. ∎

The above result shows that the greedy algorithm favors adding an element that
increases the rank of the Gramian over an element that only increases the
eigenvalues of $\boldsymbol{W}_{\mathcal{S}^{(r+1)}}$ without concurrently
increasing its rank. The inner iteration of Algorithm 1 performs a greedy
optimization of (9). When the stopping criterion of Algorithm 1 is not
satisfied, $\epsilon$ is reduced by a factor of $c$. From 1, reducing
$\epsilon$ in the outer iteration eventually forces the algorithm to choose an
actuator that improves the rank in the next inner iteration. Thus, when
$\epsilon$ becomes small enough, the approach greedily chooses actuators to
minimize the average control energy while improving controllability.

Next, in order to characterize the near-optimality of Algorithm 1, we
introduce the notions of supermodularity and matroid constraints:

######  Definition 1 (Supermodularity)

The set function $f:\mathcal{U}\to\mathbb{R}$ is said to be
$\alpha$-submodular if $\alpha\in\mathbb{R}_{+}$ is the largest number for
which the following holds
$\forall\mathcal{A}\subseteq\mathcal{B}\subseteq\mathcal{U}$ and $\forall
e\in\mathcal{U}\setminus\mathcal{B}$,

$f(\mathcal{A}\cup\\{e\\})-f(\mathcal{A})\geq{\alpha[f(\mathcal{B}\cup\\{e\\})-f(\mathcal{B})]}.$
(15)

Also, the function $-f(\cdot)$ is said to be $\alpha$-supermodular.

######  Definition 2 (Matroid)

A matroid is a pair $(\mathcal{U},\mathcal{I})$ where $\mathcal{U}$ is a
finite set and $\mathcal{I}\subseteq 2^{\mathcal{U}}$ satisfies the following
three properties: (i) $\emptyset\in\mathcal{I}$; (ii) For any two sets,
$\mathcal{A}\subseteq\mathcal{B}\subseteq\mathcal{U}$, if
$\mathcal{B}\in\mathcal{I}$, then $\mathcal{A}\in\mathcal{I}$; (iii) For any
two sets, $\mathcal{A},\mathcal{B}\in\mathcal{I}$, if
$|\mathcal{B}|>|\mathcal{A}|$, then there exists
$e\in\mathcal{B}\setminus\mathcal{A}$ such that
$\mathcal{A}\cup\\{e\\}\in\mathcal{I}$.

Our next result establishes that the cost function of the optimization problem
in (9) is supermodular and that its constraint set is a matroid.

###### Proposition 2

The objective function of (9),
$E(\mathcal{T},\epsilon)\triangleq\mathsf{Tr}\left\\{(\boldsymbol{W}_{\mathcal{S}(\mathcal{T})}+\epsilon\boldsymbol{I})^{-1}\right\\}$
is an $\alpha$-supermodular function with $\alpha$ satisfying

$\alpha(\epsilon)\geq\cfrac{\epsilon}{\lambda_{\max}(\epsilon\boldsymbol{I}+\boldsymbol{W})},$
(16)

where
$\boldsymbol{W}\triangleq\sum_{k=1}^{n}\boldsymbol{A}^{k-1}\boldsymbol{B}\boldsymbol{B}^{\mathsf{T}}(\boldsymbol{A}^{k-1})^{\mathsf{T}}$
and $\lambda_{\max}(\cdot)$ is the largest magnitude eigenvalue. Also,
($\mathcal{V}$,$\left\\{\mathcal{T}:\;\mathcal{S}(\mathcal{T})\in\Phi\right\\}$)
is a matroid.

###### Proof:

See Appendix B. ∎

In (16), we explicitly retain the dependence of $\alpha$ on $\epsilon$, as the
value of $\epsilon$ varies across the iterations of Algorithm 1. From 2, we
have the following guarantee for the inner loop of Algorithm 1.

###### Theorem 1

Let $(\boldsymbol{A}\in\mathbb{R}^{n\times
m},\boldsymbol{B}\in\mathbb{R}^{n\times m})$ be an $s$-sparse controllable
LDS. Let
$\beta(\epsilon)=\min\left(\frac{\alpha(\epsilon)}{2},\frac{\alpha(\epsilon)}{1+\alpha(\epsilon)}\right)$
where $\alpha(\cdot)$ is the submodularity constant of the cost function of
(9). The cost function corresponding to the set $\mathcal{S}$ returned by the
inner loop of Algorithm 1 run with a given value of $\epsilon$ satisfies

$\mathsf{Tr}\left\\{(\boldsymbol{W}_{\mathcal{S}}+\epsilon\boldsymbol{I})^{-1}\right\\}<\left[1-\beta(\epsilon)\right]\frac{n}{\epsilon}+\beta(\epsilon)E^{*},$
(17)

where $E^{*}$ is the optimal value of the objective function of the
optimization problem in (9) with $\epsilon=0$.

###### Proof:

See Appendix C. ∎

Theorem 1 shows that the cost function evaluated at the solution returned by
Algorithm 1 for a given value of $\epsilon$ is an additive term away from the
optimal cost. Admittedly, the $n/\epsilon$ dependence in the additive term on
the right hand side makes the bound loose. In practice, Algorithm 1 returns a
schedule that far outperforms, for example, a random schedule. However,
besides the above result, it is hard to quantify the optimality gap even
numerically, due to the combinatorial nature of the problem.

When Algorithm 1 terminates, the resulting actuator schedule $\mathcal{S}$
satisfies $\mathsf{Rank}\left\\{\boldsymbol{W}_{\mathcal{S}}\right\\}=n$. Note
that, due to the greedy nature of the algorithm, $\mathcal{V}^{(r)}$ could
become an empty set before $\boldsymbol{W}_{\mathcal{S}}$ attains full rank,
and the algorithm may not terminate. However, we have never found this to be
an issue in any of our experiments.

Finally, we note that our approach can also be used to find a time-invariant
sparse actuator schedule. For this, we change $\Phi$, the feasible set of (6),
defined in (4), to
$\left\\{(\mathcal{S}_{0},\mathcal{S}_{0},\ldots,\mathcal{S}_{0})\\!\\!:\mathcal{S}_{0}\\!\subseteq\\!\\{1,2,\ldots,m\\},\;|\mathcal{S}_{0}|\leq
s\right\\}$, i.e., $\mathcal{S}_{k}=\mathcal{S}_{0}$. We can drop the index
$t$ to replace $\mathcal{V}$ with $\\{1,2,\ldots,m\\}$ and define the schedule
obtained from $\mathcal{T}$ as $(\mathcal{T},\mathcal{T},\ldots,\mathcal{T})$
instead of (8) (Step 6 of Algorithm 1). Also, in this case,
$\mathcal{V}^{(r)}=\\{1,2,\ldots,m\\}\setminus\mathcal{T}^{(r)}$. Similar to
2, we can prove that this new problem optimizes an $\alpha$-supermodular
function subject to a matroid constraint, and like Theorem 1, the modified
greedy strategy possesses similar guarantees. We omit the details to avoid
repetition.

Figure 1: CDF of
$10\log_{10}\left(\mathsf{Tr}\left\\{\left(\boldsymbol{W}_{\mathcal{S}}\right)^{-1}\right\\}\right)$
for varying sparsity levels with $m=n=20$. Figure 2:
$\frac{\mathbb{E}_{A,B}\mathsf{Tr}\left\\{\boldsymbol{W}_{\mathcal{S}}^{-1}\right\\}}{\mathbb{E}_{A,B}\mathsf{Tr}\left\\{\boldsymbol{W}^{-1}\right\\}}$
vs. the fraction of active actuators ($\frac{s}{m}$), averaged over 100
independent trials with $m=50$.

##  IV Simulation Results

In this section, we illustrate the performance of the time-varying and sparse
actuator scheduling algorithm developed in this work by applying it to an LDS
whose transfer matrix $\boldsymbol{A}$ is generated from an Erdős-Renyi random
graph. An Erdős-Renyi random graph consists of $n$ vertices. The pairs of
vertices are independently connected by an edge with probability
$p=\frac{2\log n}{n}$, a setting used to model real-time networked systems
[14]. The transfer matrix of the LDS is then generated from the graph as
$\boldsymbol{A}=\boldsymbol{I}-\frac{1}{n}\boldsymbol{L}$, where
$\boldsymbol{L}$ is the graph Laplacian.

We first illustrate the dependence of the average control energy,
$\mathsf{Tr}\left\\{\left(\boldsymbol{W}_{\mathcal{S}}\right)^{-1}\right\\}$,
on the sparsity level $s$ of the control inputs. To this end, we generate the
transfer matrices $\boldsymbol{A}$ from $500$ Erdős-Renyi random graphs drawn
independently. We use Algorithm 1 to determine the sparse actuator schedule,
and compute
$\mathsf{Tr}\left\\{\left(\boldsymbol{W}_{\mathcal{S}}\right)^{-1}\right\\}$
corresponding to the schedule $\mathcal{S}$ returned by the algorithm. For
this experiment, we set $n=20$, $m=n$, and $\boldsymbol{B}=\boldsymbol{I}$. In
Fig. 1, we show the empirical cumulative distribution function (CDF) of
$\mathsf{Tr}\left\\{\left(\boldsymbol{W}_{\mathcal{S}}\right)^{-1}\right\\}$
in two settings: the time-varying support case with sparsity levels
$s=5,10,15$, and the fixed support case with $s=10,15$. We also plot the CDF
for the case with no sparsity constraint. The curves shift to the right as $s$
is decreased as expected since the system becomes more constrained, thereby
incurs a higher average control energy. Similarly, using a fixed support makes
the system more constrained and hence requires higher average control energy
compared to the time-varying support case. Further, the control energy with
time-varying support and $s=15,s=10$ is close to the control energy without
sparsity constraints. Therefore, time-varying sparsity constraints do not
impose a significant energy burden to control the LDS at moderate sparsity
levels; we elaborate on this in our next experiment.

Next, we illustrate the relative cost of imposing the sparsity constraints
compared to the non-sparse case. Here, the entries of the input matrix
$\boldsymbol{B}$ are i.i.d. and uniformly distributed over $[0,1]$. We plot
$\rho\triangleq{\mathbb{E}_{A,B}\mathsf{Tr}\left\\{\boldsymbol{W}_{\mathcal{S}}^{-1}\right\\}}/{\mathbb{E}_{A,B}\mathsf{Tr}\left\\{\boldsymbol{W}^{-1}\right\\}}$
as a function of the fraction of active actuators at each time instant
(${s}/{m}$). The quantity $\rho$ represents the ratio of the average control
energy with the sparsity constraint to the average control energy in the
unconstrained case. We show the behavior in Fig. 2, with $m$ fixed at $50$ and
for various values of $n$ from $20$ to $80$. We observe that there is nearly
an inverse-linear relationship between $s/m$ and $\rho$. This shows that using
time-varying $s$-sparse control inputs increases the average energy to control
the system by a factor proportional to the reciprocal of the fraction of
active actuators. We have also observed this trend when $\boldsymbol{B}$ is a
random matrix with i.i.d. entries drawn from a Gaussian distribution and when
$\boldsymbol{B}$ = $\boldsymbol{I}$ (for $n=m$). With reasonable
approximations, it is possible to mathematically derive that this behavior
holds when $\boldsymbol{B}$ has i.i.d. entries; we omit the details due to
lack of space.

Figure 3: $\mathsf{Tr}\left\\{\boldsymbol{W}_{\mathcal{S}}^{-1}\right\\}$ as a
function of sparsity ($s$), averaged over $100$ independent trials with
$n=100,m=50$.

Next, we compare Algorithm 1 with schedulers that are adapted from [16], the
closest to our work. The algorithms in [16] are developed under an _average_
sparsity constraint, i.e., the individual inputs need not be sparse, but the
overall sequence of inputs need to satisfy an average sparsity constraint. We
modify the algorithms in [16] by adding a piecewise sparsity constraint. In
Fig. 3, we plot
$\mathsf{Tr}\left\\{\boldsymbol{W}_{\mathcal{S}}^{-1}\right\\}$ as a function
of $s$ for four algorithms adapted from [16], namely, random-weighted, random-
unweighted, deterministic-unweighted, and deterministic-weighted. The random
scheduler samples an actuator from the probability distribution given in [16,
Algorithm 6] and adds it to the schedule provided adding it still satisfies
the sparsity constraint. The deterministic scheduler picks a actuator that
greedily optimizes the objective function used in [16, Algorithm 1]. The
weighted schedulers have an additional weight (amplification) associated with
the selected actuator, while the weights are set to $1$ for the unweighted
schedule (see [16, Algorithms 2, 6, 7].) For the unweighted random scheduler,
the actuators are sampled without replacement. The plot shows that Algorithm 1
generally outperforms existing algorithms modified to satisfy our sparsity
constraint, especially at lower sparsity levels.

##  V Conclusion

We studied the problem of finding an energy-efficient actuator schedule for
controlling an LDS in a finite number of steps, with at most $s$ active inputs
per time step. We presented a greedy scheduling algorithm by considering the
minimization of
$\mathsf{Tr}\left\\{\boldsymbol{W}_{\mathcal{S}}^{-1}\right\\}$, which models
the average control energy. We presented several interesting theoretical
guarantees for the algorithm. Through simulations, we showed that the
algorithm returns a feasible schedule, with the average energy increasing
(compared to the case without sparsity constraints) by a factor proportional
to the inverse of the fraction of active inputs, for randomly drawn LDSs.
Overall, we conclude that sparse inputs can drive an LDS to a desired state
without a significant increase in energy requirements, at moderate sparsity
levels.

##  Appendix A Proof of 1

Let $\mathcal{S}$ be the actuator schedule at some iteration of the greedy
algorithm such that
$\mathsf{Rank}\left\\{\boldsymbol{W}_{\mathcal{S}}\right\\}$ = $R<n$. By (13),
there exists a candidate feasible schedule $\hat{\mathcal{S}}$ for the next
iteration such that
$\mathsf{Rank}\left\\{\boldsymbol{W}_{\hat{\mathcal{S}}}\right\\}$ = $R+1$.
Suppose there is an alternative feasible schedule $\tilde{\mathcal{S}}$ such
that $\mathsf{Rank}\left\\{\boldsymbol{W}_{\tilde{\mathcal{S}}}\right\\}$ =
$R$. The greedy algorithm chooses the schedule $\hat{\mathcal{S}}$ if

$\mathsf{Tr}\left\\{(\boldsymbol{W}_{\tilde{\mathcal{S}}}+\epsilon\boldsymbol{I})^{-1}\right\\}>\mathsf{Tr}\left\\{(\boldsymbol{W}_{\hat{\mathcal{S}}}+\epsilon\boldsymbol{I})^{-1}\right\\}.$

Let $\lambda_{i},i=1,2,\ldots n$, with
$\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{n}$ denote the ordered
eigenvalues of $\boldsymbol{W}_{\mathcal{S}}$ (similarly, $\hat{\lambda}_{i}$
and $\tilde{\lambda}_{i}$ for $\boldsymbol{W}_{\hat{S}}$ and
$\boldsymbol{W}_{\tilde{S}}$, respectively). Then, we can write

$\displaystyle\mathsf{Tr}\left\\{(\boldsymbol{W}_{\tilde{\mathcal{S}}}+\epsilon\boldsymbol{I})^{-1}\right\\}\geq\frac{R}{\tilde{\lambda}_{1}+\epsilon}+\frac{n-R}{\epsilon},$
(18)
$\displaystyle\mathsf{Tr}\left\\{(\boldsymbol{W}_{\hat{\mathcal{S}}}+\epsilon\boldsymbol{I})^{-1}\right\\}\leq\frac{R+1}{\hat{\lambda}_{R+1}+\epsilon}+\frac{n-R-1}{\epsilon}.$
(19)

The following inequality is a sufficient condition for the greedy algorithm to
choose $\hat{\mathcal{S}}$:

$\frac{R}{\tilde{\lambda}_{1}+\epsilon}+\frac{n-R}{\epsilon}>\frac{R+1}{\hat{\lambda}_{R+1}+\epsilon}+\frac{n-R-1}{\epsilon},$
(20)

Simplifying the above, we get

$\tilde{\lambda}_{1}\hat{\lambda}_{R+1}>\epsilon\left[R\tilde{\lambda}_{1}-(R+1)\hat{\lambda}_{R+1}\right],$
(21)

The inequality holds trivially for
$R\tilde{\lambda}_{1}-(R+1)\hat{\lambda}_{R+1}\leq 0$. For
$R\tilde{\lambda}_{1}-(R+1)\hat{\lambda}_{R+1}>0$, we obtain

$\epsilon<\frac{\tilde{\lambda}_{1}\hat{\lambda}_{R+1}}{R\tilde{\lambda}_{1}-(R+1)\hat{\lambda}_{R+1}}.$
(22)

The right hand side of above equation is finite and positive, and $\epsilon$
is decreased by factor $c>1$ in each iteration of the Algorithm 1. Hence,
there will always exists an $\epsilon$ for which (22) is satisfied. Hence, for
a sufficiently small $\epsilon$, (22) holds for any $\tilde{\mathcal{S}}$
given an $\hat{\mathcal{S}}$. Thus, the greedy algorithm chooses an actuator
that improves the rank.  $\blacksquare$

##  Appendix B Proof of 2

From [22, Theorem 2], we know that the real-valued function $f$ of the form

$f({\mathcal{A}})=\mathsf{Tr}\left\\{\left(\boldsymbol{M}_{\emptyset}+\sum_{i\in\mathcal{A}}\boldsymbol{M}_{i}\right)^{-1}\right\\},$
(23)

where $\mathcal{A}$ is an index set and $\boldsymbol{M}_{\emptyset}\succ 0$
and $\boldsymbol{M}_{i}\succeq 0$, is monotonically decreasing and
$\alpha$-supermodular with $\alpha\geq\frac{\mu_{\min}}{\mu_{\max}}>0,$ where

$0<\mu_{\min}\leq\lambda_{\min}(\boldsymbol{M}_{\emptyset})\leq\lambda_{\max}(\boldsymbol{M}_{\emptyset}+\sum_{i\in\mathcal{A}}\boldsymbol{M}_{i})\leq\mu_{\max}.$
(24)

Here, $\lambda_{\max}(\cdot)$ and $\lambda_{\min}(\cdot)$ are the largest and
smallest eigenvalues in magnitude, respectively. Our cost function
$E(\mathcal{T},\epsilon)$ takes the same form as $f(\mathcal{A})$, with
$\boldsymbol{M}_{\emptyset}=\epsilon\boldsymbol{I}\succ 0$ and the matrices
$\boldsymbol{M}_{i}$ being constructed as the submatrices of the
controllability gramian $\boldsymbol{W}$ (see (5)). Further, from the
definitions, we can set $\mu_{\min}=\epsilon$ and
$\mu_{\max}=\lambda_{\max}(\epsilon\boldsymbol{I}+\boldsymbol{W})$. Hence, the
function $E(\mathcal{T},\epsilon)$ is $\alpha$-supermodular with $\alpha$
satisfying (16).

We next complete the proof by showing that the sparsity constraint on the
actuator set is a matroid constraint. For this proof, we consider the
equivalent sparsity constraint on $\mathcal{T}\in 2^{\mathcal{V}}$ in (9). The
constraint is given by

$|\\{j:(k,j)\in\mathcal{T}\\}|\leq s,\;\text{for }k=0,1,\ldots,n-1$ (25)

To prove that the above constraint is a matroid, we verify the three
conditions of 2. The first condition holds trivially. If we have a set
$\mathcal{T}$ that satisfies the sparsity constraint in (25), then any subset
$\mathcal{T}^{\prime}\subseteq\mathcal{T}$ also satisfies the sparsity
constraint. Hence, the second condition holds. For the third condition,
suppose there exist sets $\mathcal{T},\mathcal{T}^{\prime}\in 2^{\mathcal{V}}$
satisfying the sparsity constraint in (25) and
$|\mathcal{T}|>|\mathcal{T}^{\prime}|$. Then, there exists at least one time
index $k$ such that

$|\\{j:(k,j)\in\mathcal{T}\\}|>|\\{j:(k,j)\in\mathcal{T}^{\prime}\\}|.$ (26)

If we take an element
$\tilde{j}\in\\{j:(k,j)\in\mathcal{T}\setminus\mathcal{T}^{\prime}\\}$, the
new set $\mathcal{T}^{\prime}\cup\\{(k,\tilde{j})\\}$ satisfies

$\displaystyle\left|\left\\{j:(k,j)\in\mathcal{T}^{\prime}\right\\}\cup\\{(k,\tilde{j})\\}\right|$
$\displaystyle=\left|\left\\{j:(k,j)\in\mathcal{T}^{\prime}\right\\}\right|+1$
$\displaystyle\leq\left|\left\\{j:(k,j)\in\mathcal{T}\right\\}\right|\leq s.$

So, the new set $\mathcal{T}^{\prime}\cup\\{(k,\tilde{j})\\}$ also satisfies
(25), verifying the third condition and completing the proof.  $\blacksquare$

##  Appendix C Proof of Theorem 1

Consider the problem of minimizing an $\alpha$-supermodular function
$f:2^{\mathcal{V}}\rightarrow\mathbb{R}$ subject a matroid constraint
$(\mathcal{V},\mathcal{I})$ i.e.,

$\min_{\mathcal{A}\in
2^{\mathcal{V}}}f(\mathcal{A})\;\text{s.t.}\;\mathcal{A}\in\mathcal{I}.$ (27)

Suppose $f^{*}$ is the optimal solution of (27) and $\tilde{f}$ is the
solution returned by a greedy algorithm that starts with
$\mathcal{A}=\emptyset$ and adds elements from $\mathcal{V}$ one-by-one, so
that at step $t$, it updates $\mathcal{A}_{t}$ as
$\mathcal{A}_{t+1}=\mathcal{A}_{t}\cup e^{*}$, where
$e^{*}=\text{argmin}_{e\in\mathcal{V}\backslash\mathcal{A}_{t},\mathcal{A}_{t}\cup
e\in\mathcal{I}}f(\mathcal{A}_{t}\cup e)$.  Then, from [18, Theorem 1] we
have,

$\frac{f^{*}-\tilde{f}}{f^{*}-f(\emptyset)}\leq
1-\min\left(\frac{\alpha}{2},\frac{\alpha}{1+\alpha}\right),$ (28)

where $\alpha$ is the submodularity constant of $f$.

From 2, our cost function is $\alpha$-supermodular and the constraint set is a
matroid. Further, Algorithm 1 is a greedy algorithm of the form described
above. For a fixed $\epsilon$, let $E^{*}(\epsilon)$ be the optimal energy
obtained by solving (9) exactly and
$\tilde{E}(\epsilon)=\mathsf{Tr}\left\\{\left(\boldsymbol{W}_{\mathcal{S}}+\epsilon\boldsymbol{I}\right)^{-1}\right\\}$
be the objective function returned by Algorithm 1 with parameter $\epsilon$.
Then, using (28), we have

$\frac{\tilde{E}(\epsilon)-E^{*}(\epsilon)}{n/\epsilon-E^{*}(\epsilon)}\leq
1-\beta(\epsilon),$ (29)

where $\beta(\epsilon)>0$ is defined in Theorem 1. Let,
$E^{*}=\mathsf{Tr}\left\\{\boldsymbol{W}_{\mathcal{S}^{*}}^{-1}\right\\}$
where $\mathcal{S}^{*}$ be the corresponding optimal actuator schedule
obtained by solving (9) with $\epsilon=0$. We obtain the following inequality,

$E^{*}=\mathsf{Tr}\left\\{\boldsymbol{W}_{\mathcal{S}^{*}}^{-1}\right\\}>\mathsf{Tr}\left\\{\left(\boldsymbol{W}_{\mathcal{S}^{*}}+\epsilon\boldsymbol{I}\right)^{-1}\right\\}\geq
E^{*}(\epsilon).$ (30)

Plugging in this inequality into (29) leads to

$\tilde{E}(\epsilon)\leq\frac{n(1-\beta(\epsilon))}{\epsilon}+\beta(\epsilon)E^{*}(\epsilon)<\frac{n(1-\beta(\epsilon))}{\epsilon}+\beta(\epsilon)E^{*}.$
(31)

Hence, the proof is complete.  $\blacksquare$

## References

  * [1] S. C. Tatikonda, “Control under communication constraints,” Ph.D. dissertation, Dept. Elect. Comput. Sci., MIT, Cambridge, USA, 2000.
  * [2] A. Jadbabaie, A. Olshevsky, G. J. Pappas, and V. Tzoumas, “Minimal reachability is hard to approximate,” _IEEE Trans. Autom. Control_ , vol. 64, no. 2, pp. 783–789, 2019.
  * [3] M. Nagahara and D. E. Quevedo, “Sparse representations for packetized predictive networked control,” _IFAC Proc. Volumes_ , vol. 44, no. 1, pp. 84 – 89, 2011.
  * [4] Z. Li, Y. Xu, H. Huang, and S. Misra, “Sparse control and compressed sensing in networked switched systems,” _IET Control Theory Appl._ , vol. 10, no. 9, pp. 1078–1087, 2016.
  * [5] S. Foucart and H. Rauhut, _A Mathematical Introduction to Compressive Sensing_. Birkhäuser, 2013.
  * [6] G. Joseph, B. Nettasinghe, V. Krishnamurthy, and P. K. Varshney, “Controllability of network opinion in Erdos-Renyi graphs using sparse control inputs,” _SIAM J. Control Optim._ , vol. 59, no. 3, pp. 2321–2345, 2021.
  * [7] N. Wendt, C. Dhal, and S. Roy, “Control of network opinion dynamics by a selfish agent with limited visibility,” _IFAC-PapersOnLine_ , vol. 52, no. 3, pp. 37 – 42, 2019, iFAC Symp. Large Scale Complex Syst.
  * [8] G. Joseph and C. R. Murthy, “Controllability of linear dynamical systems under input sparsity constraints,” _IEEE Trans. Autom. Control_ , vol. 66, no. 2, pp. 924–931, 2021.
  * [9] A. Olshevsky, “On a relaxation of time-varying actuator placement,” _IEEE Control Syst. Lett._ , vol. 4, no. 3, pp. 656–661, 2020.
  * [10] T. Ikeda and K. Kashima, “Sparsity-constrained controllability maximization with application to time-varying control node selection,” _IEEE Control Syst. Lett._ , vol. 2, no. 3, pp. 321–326, 2018.
  * [11] F. Fotiadis and K. G. Vamvoudakis, “Learning-based actuator placement for uncertain systems,” in _Proc. CDC_ , 2021, pp. 90–95.
  * [12] F. Fotiadis, K. G. Vamvoudakis, and Z.-P. Jiang, “Data-based actuator selection for optimal control allocation,” in _Proc. CDC_ , 2022, pp. 4674–4679.
  * [13] A. Olshevsky, “Minimal controllability problems,” _IEEE Trans. Control Netw. Syst._ , vol. 1, no. 3, pp. 249–258, 2014.
  * [14] V. Tzoumas, M. A. Rahimian, G. J. Pappas, and A. Jadbabaie, “Minimal actuator placement with bounds on control effort,” _IEEE Trans. Control Netw. Syst._ , vol. 3, no. 1, pp. 67–78, 2016.
  * [15] A. S. A. Dilip, “The controllability gramian, the hadamard product, and the optimal actuator/leader and sensor selection problem,” _IEEE Control Syst. Lett._ , vol. 3, no. 4, pp. 883–888, 2019.
  * [16] M. Siami, A. Olshevsky, and A. Jadbabaie, “Deterministic and randomized actuator scheduling with guaranteed performance bounds,” _IEEE Trans. Autom. Control_ , vol. 66, no. 4, pp. 1686–1701, 2020.
  * [17] M. Siami and A. Jadbabaie, “A separation theorem for joint sensor and actuator scheduling with guaranteed performance bounds,” _Automatica_ , vol. 119, p. 109054, 2020.
  * [18] L. F. O. Chamon, A. Amice, and A. Ribeiro, “Matroid-constrained approximately supermodular optimization for near-optimal actuator scheduling,” in _Proc. CDC_ , 2019, pp. 3391–3398.
  * [19] J. Jiao, D. Maity, J. S. Baras, and S. Hirche, “Actuator scheduling for linear systems: A convex relaxation approach,” _IEEE Control Syst. Lett._ , vol. 7, pp. 7–12, 2023.
  * [20] Y. Zhao, F. Pasqualetti, and J. Cortés, “Scheduling of control nodes for improved network controllability,” in _Proc. CDC_ , 2016, pp. 1859–1864.
  * [21] A. Olshevsky, “On (non)supermodularity of average control energy,” _IEEE Tran. Control Netw. Syst._ , vol. 5, no. 3, pp. 1177–1181, 2018.
  * [22] L. F. O. Chamon, G. J. Pappas, and A. Ribeiro, “The mean square error in Kalman filtering sensor selection is approximately supermodular,” in _Proc. CDC_ , 2017, pp. 343–350.


# Well-Posedness of the Bochner Integral Form of Operator-Valued Riccati
Equations

James Cheung  Millennium Space Systems, A Boeing Company. 2265 E. El Segundo
Blvd, El Segundo, CA, 90245.

###### Abstract.

In this short paper, we prove that the Bochner integral form of the operator-
valued Riccati equation has a unique solution if and only if its mild form has
a unique solution. This implies that the mild and Bochner integral forms of
this equation are equivalent. The result is obtained through an operator
representation argument.

##  1\. Introduction

Let $H$ be a separable Hilbert space equipped with the inner product
$(\cdot,\cdot)_{H}$. We define $\mathcal{L}(H)$ to be the space of bounded
linear operators defined on $H$. We will then denote
$A:\mathcal{D}(A)\rightarrow H$ as the generator of a $C_{0}$-semigroup
$S(t)\in\mathcal{L}(H)$ for all $t\in[0,\tau]$, where $\tau>0$ and
$\mathcal{D}(A)$ is the domain of $A$ defined densely in $H$. The solution
space of interest in this work is $\mathcal{C}([0,\tau],\mathcal{L}(H))$,
which defines the space of bounded operators that are norm-continuous with
respect to $t\in[0,\tau]$.

In the differential form, the operator-valued Riccati equation is given by

(1) $\left\\{\begin{aligned}
\frac{d}{dt}\Sigma(t)&=A\Sigma(t)+\Sigma(t)A^{*}+\Sigma(t)G\Sigma(t)-F\\\
\Sigma(0)&=\Sigma_{0},\end{aligned}\right.$

for all $t\in[0,\tau]$, where $F,\Sigma_{0}\in\mathcal{L}(H)$ are self-adjoint
operators, and $G$ is an unbounded self-adjoint operator whose domain is dense
in $H$. The mild form of this equation is then given by

(2)
$\Sigma(t)\phi=S(t)\Sigma_{0}S^{*}(t)\phi+\int_{0}^{t}S(t-s)\left({F-\Sigma
G\Sigma}\right)S^{*}(t-s)\phi ds$

for all $\phi\in H$ and $t\in[0,\tau]$. From the results presented in [1], we
know that it is generally known that (1) and (2) are equivalent, meaning that
there exists a unique $\Sigma(\cdot)\in\mathcal{C}([0,\tau],\mathcal{L}(H))$
that satisfies both equations. In this paper, we demonstrate that
$\Sigma(\cdot)\in\mathcal{C}([0,\tau],\mathcal{L}(H))$ satisfying (2) also
satisfies

(3) $\Sigma(t)=S(t)\Sigma_{0}S^{*}(t)+\int_{0}^{t}S(t-s)\left({F-\Sigma
G\Sigma}\right)S^{*}(t-s)ds$

for all $t\in[0,\tau]$.

The well-posedness of the Bochner integral form of the operator-valued Riccati
equation plays an important part in determining theoretical error bounds for
approximations to this equation [2, 4]. The previously known result presented
in [3] indicates that the Bochner integral form of the operator-valued Riccati
equation is well-posed if the operators $F,G$ in (3) are compact. This result
was derived through an approximation argument. This work extends well-
posedness to cases where $G$ is not necessarily bounded. We proceed to prove
this result in the following section.

##  2\. Analysis

In the analysis, we will use an operator representation argument to
demonstrate that the mild form and the Bochner integral form of the operator-
valued Riccati equation are equivalent. To this end, we will utilize the
following corollary to the Riesz Representation Theorem found in [5, Theorem
A.63].

######  Lemma 1.

If $q(\cdot):H\rightarrow\mathbb{R}$ is a bounded quadratic form on $H$, then
there exists a unique self-adjoint operator $Q\in\mathcal{L}(H)$ such that

$q(\phi)=\left({\phi,Q\phi}\right)_{H}$

for all $\phi\in H$.

We now move to prove the main result of this work given in the following.

######  Theorem 1.

Let $S(t)\in\mathcal{L}(H)$ be a $C_{0}$-semigroup defined on $t\in[0,\tau]$.
Now, suppose that there exists an unique time-dependent self-adjoint operator
$\Sigma(\cdot)\in\mathcal{C}([0,\tau],\mathcal{L}(H))$ that satisfies the
following mild form of the operator-valued Riccati equation

(4)
$\Sigma(t)\phi=S(t)\Sigma_{0}S^{*}(t)\phi+\int_{0}^{t}S(t-s)\left({F-\Sigma
G\Sigma}\right)S^{*}(t-s)\phi ds$

for all $\phi\in H$ and $t\in[0,\tau]$, where $F,\Sigma_{0}\in\mathcal{L}(H)$
are bounded self-adjoint operators and $G$ is a generally unbounded self-
adjoint operator whose domains is dense in $H$. Then
$\Sigma(\cdot)\in\mathcal{C}([0,\tau],\mathcal{L}(H))$ satisfies (4) if and
only if it satisfies also the following Bochner integral form of the operator-
valued Riccati equation

(5) $\Sigma(t)=S(t)\Sigma_{0}S^{*}(t)+\int_{0}^{t}S(t-s)\left({F-\Sigma
G\Sigma}\right)S^{*}(t-s)ds$

for all $t\in[0,\tau]$.

###### Proof.

Since $\Sigma(\cdot)\in\mathcal{C}([0,\tau],\mathcal{L}(H))$ satisfies (4),
then we must have that

(6)
$\left({\phi,\Sigma(t)\phi}\right)_{H}=\left({\phi,S(t)\Sigma_{0}S^{*}(t)\phi}\right)_{H}+\left({\phi,\int_{0}^{t}S(t-s)\left({F-\Sigma
G\Sigma}\right)(s)S^{*}(t-s)\phi ds}\right)_{H}$

for all $\phi\in H$ and $t\in[0,\tau]$.

Defining

$\displaystyle q^{1}_{t}(\phi)$
$\displaystyle:=\left({\phi,\Sigma(t)\phi}\right)_{H}$ $\displaystyle
q^{2}_{t}(\phi)$
$\displaystyle:=\left({\phi,S(t)\Sigma_{0}S^{*}(t)\phi}\right)_{H}$
$\displaystyle q^{3}_{t}(\phi)$
$\displaystyle:=\left({\phi,\int_{0}^{t}S(t-s)\left({F-\Sigma
G\Sigma}\right)(s)S^{*}(t-s)\phi ds}\right)_{H}$

as quadratic forms defined for all $\phi\in H$ and $t\in[0,\tau]$. The
boundedness of $q^{1}_{t}(\cdot)$ follows from the observation that
$\Sigma(t)\phi\in H$ for all $\phi\in H$ and $t\in[0,\tau]$. Equation (4) then
requires that $S(t)\Sigma_{0}S^{*}(t)\phi\in H$ and that
$\int_{0}^{t}S(t-s)\left({F-\Sigma G\Sigma}\right)(s)S^{*}(t-s)\phi ds\in H$
for all $\phi\in H$ and $t\in[0,\tau]$, which implies the boundedness of
$q^{2}_{t}(\cdot),q^{3}_{t}(\cdot)$. Applying Lemma 1 then implies that there
exists unique operators $Q^{1}_{t},Q^{2}_{t},Q^{3}_{t}\in\mathcal{L}(H)$ so
that

$\displaystyle q^{1}_{t}(\phi)=\left({\phi,Q^{1}_{t}\phi}\right)_{H}$
$\displaystyle q^{2}_{t}(\phi)=\left({\phi,Q^{2}_{t}\phi}\right)_{H}$
$\displaystyle q^{3}_{t}(\phi)=\left({\phi,Q^{3}_{t}\phi}\right)_{H}$

for all $\phi\in H$ and $t\in[0,\tau]$.

It then follows from (6) that

$q^{1}_{t}(\phi)=q^{2}_{t}(\phi)+q^{3}_{t}(\phi)$

for all $\phi\in H$ and $t\in[0,\tau]$. This can only be true if

$Q^{1}_{t}=Q^{2}_{t}+Q^{3}_{t}$

for all $t\in[0,\tau]$. Then, by the definition of
$q^{1}_{t},q^{2}_{t},q^{3}_{t}$ and the uniqueness of
$Q^{1}_{t},Q^{2}_{t},Q^{3}_{t}$ (implied by Lemma 1) associated with their
respective quadratic forms, we have necessarily that

$\displaystyle Q^{1}_{t}$ $\displaystyle=\Sigma(t)$ $\displaystyle Q^{2}_{t}$
$\displaystyle=S(t)\Sigma_{0}S^{*}(t)$ $\displaystyle Q^{3}_{t}$
$\displaystyle=\int_{0}^{t}S(t-s)\left({F-\Sigma
G\Sigma}\right)(s)S^{*}(t-s)ds,$

for all $t\in[0,\tau]$. Hence,
$\Sigma(\cdot)\in\mathcal{C}\left({[0,\tau],\mathcal{L}(H)}\right)$ must also
satisfy

$\Sigma(t)=S(t)\Sigma_{0}S^{*}(t)+\int_{0}^{t}S(t-s)\left({F-\Sigma
G\Sigma}\right)(s)S^{*}(t-s)ds$

for all $t\in[0,\tau]$. Thus we have proven the “if” part of the theorem. The
proof in the other direction follows by testing (5) with any $\phi\in H$. ∎

######  Remark 1.

We would like to point out that the analysis presented in the proof above
implies that the operator-valued integral

$\int_{0}^{t}S(t-s)\left({F-\Sigma G\Sigma}\right)(s)S^{*}(t-s)ds$

is the unique representation of the bounded self-adjoint time-dependent linear
operator $Q_{t}\in\mathcal{C}([0,\tau],\mathcal{L}(H))$ that satisfies

$\left({\phi,Q_{t}\phi}\right)_{H}:=\left({\phi,\int_{0}^{t}S(t-s)\left({F-\Sigma
G\Sigma}\right)(s)S^{*}(t-s)\phi ds}\right)_{H}$

for all $\phi\in H$ and $t\in[0,\tau]$. This indicates that the operator-
valued integral used in the Bochner integral form of the operator-valued
Riccati equation is well-defined.

##  3\. Discussion

We have demonstrated above that the mild and Bochner integral forms of the
operator-valued Riccati equation are equivalent. Instead of using an
approximation argument, as done in [3], we have utilized an operator
representation argument to achieve this result. This simpler proof then allows
us to extend the known well-posedness results for the Bochner integral form to
cases where the coefficient operator $G$ in the equation are unbounded.

In following works, the author will utilize the result presented in this paper
to determine error bounds for approximation methods to operator-valued Riccati
equations for cases where the coefficient operators $G$ in the equation are
defined by boundary and point control/observation operators.

## References

  * [1] Alain Bensoussan, Giuseppe Da Prato, Michel C Delfour, and Sanjoy K Mitter.  Representation and control of infinite dimensional systems, volume 1.  Springer, 2007.
  * [2] John A Burns and James Cheung.  Optimal convergence rates for galerkin approximation of operator riccati equations.  Numerical Methods for Partial Differential Equations, 2022.
  * [3] John A Burns and Carlos N Rautenberg.  Solutions and approximations to the riccati integral equation with values in a space of compact operators.  SIAM Journal on Control and Optimization, 53(5):2846–2877, 2015\.
  * [4] James Cheung.  On the approximation of operator-valued riccati equations in hilbert spaces.  arXiv preprint arXiv:2308.10130, 2023.
  * [5] Brian C Hall.  Quantum theory for mathematicians.  Springer, 2013.