# Data Freshness in Mixed-Memory Intermittently-Powered Systems

James Scott Broadhead and Przemysław Pawełczak  Embedded and Networked
Systems, EEMCS, Delft University of Technology, The Netherlands
Email: {J.S.Broadhead<EMAIL_ADDRESS>
###### Abstract

Age of Information (AoI) is a key metric to understand data freshness in
Internet of Things (IoT) devices. In this paper we analyse an intermittently-
powered IoT sensor—with mixed-memory (volatile and non-volatile)
architecture—that uses a Time-Dependent Checkpointing (TDC) scheme. We derive
the average Peak Age of Information (PAoI) and average AoI of the system, and
use these metrics to understand which device parameters most significantly
influence performance. We go on to consider how the average PAoI of a mixed-
memory system compares with entirely volatile or entirely non-volatile
architecture, and also introduce an alternative TDC strategy to improve system
resilience in unpredictable environmental conditions.

##  I Introduction

With an increasing paradigm shift towards battery-free energy harvesting-based
design in low-powered embedded systems, new methods of operation have been
developed to address the inherent intermittency of available harvested energy.
Current _intermittent computing techniques_ [1, 2, 3, 4, 5] seek to minimise
the time and energy impact of power failure by strategically
checkpointing—effectively saving—the system state from Volatile Memory (VM) to
Non-Volatile Memory (NVM) in mixed-memory systems [6] (such as the popular
Texas Instruments MSP430 micro-controller [1, Section 3.1] [7, Section
2.1.1]). Whilst much work has been done to develop new checkpointing
strategies, there is still opportunity to better describe these systems
mathematically [7, Section 3.2.2], in particular from a data freshness
perspective.

A relevant metric to measure data freshness is the Age of Information (AoI)
[8, 9, 10, 11, 12, 13, 14], which will form the basis of our analysis. We seek
to model an Intermittently-Powered Device (IPD), implementing Time-Dependent
Checkpointing (TDC) [15, Fig. 3],[16] where the VM system state is saved to
NVM after a certain number of clock ticks have passed, and observe how
fundamental system parameters (failure rate, checkpointing overhead, etc.)
affect the freshness of locally sensed data. We also look to compare the
mixed-memory architecture of our IPD with single-type VM and single-type NVM
memory structures. We go on to introduce an alternative TDC scheme, Split-
Frequency Checkpointing (SFC), and consider how this can improve system
resilience in unpredictable environmental conditions.

Our work builds on [17] by accounting for the mixed-memory nature of many
battery-free devices and the checkpointing schemes used to move data between
memory types. To the best of our knowledge, this is the first evaluation and
comparison of AoI in IPDs with mixed-memory architecture. The efficiency of
TDC has been considered in other areas of research, notably for distributed
stream processing [18] (which looked to minimise system utilization) and also
in High Performance Computing (HPC) applications [19] (which used _wall-clock
length_ as the objective). However, this form of checkpointing has not been
analysed for transiently-operating embedded devices, or with system freshness
as the core tenet of consideration—which forms the premise of our work.

In this paper we identify the average Peak Age of Information (PAoI) and
average AoI for an IPD that uses TDC. These results allow us to better
understand the role of mixed-memory architecture in IPDs and how the inter-
checkpointing time can be best adjusted to minimise AoI. We also show that
mixed-memory architecture can improve the system freshness of an IPD compared
with single-type VM, however it cannot surpass entirely NVM architecture. We
further show that SFC can improve system performance in unpredictable
environmental conditions compared to inappropriately assigned single-frequency
checkpoint intervals.

SenseProcessing _Volatile Memory_ Checkpointed Device State _Non-Volatile
Memory_ TransmitCheckpointRestoration

Figure 1: System model for an IPD that checkpoints its internal system state
to protect from data corruption. The device performs sensing, on-board
processing (that takes $P_{i}$ clock ticks to complete), and transmission.
Sensing and transmission occur instantaneously. Data stored in VM is
checkpointed to NVM taking $D_{i}$ clock ticks, and system state restoration
from NVM to VM takes $V_{i}$ clock ticks. The system suffers frequent power
failures.

##  II System Model

We consider a communication device, presented in Fig. 1, which is powered by
an intermittent energy source (sun, vibrations, temperature gradient, etc.)
and consequently suffers frequent power failure. The device has mixed-memory
architecture (VM and NVM) and checkpoints the system state (processor
registers, hardware registers, main memory, etc.) from VM to NVM after a fixed
number of clock ticks, where clock ticks act as a base unit for the system’s
on-board clock. The sensed data is then processed and transmitted, e.g.
wirelessly through a low-powered LED [7], to a central collecting unit.

Packet Generation/Sensing. Packets containing data from an on-board sensor are
produced as required in a _generate-at-will_ type policy—where sensing only
occurs when processing of the preceding packet is complete—as considered in
[17]. We assume that sensing is instantaneous and that this data is then
immediately processed, from which a packet is created. Packets are not dropped
due to power failure, since the last computation state can always be restored
from NVM to VM.

System Operation. _Data processing_ occurs in the volatile memory of Fig. 1
and encompasses a number of possible steps; such as peripheral control,
filtering, and packet framing. To reduce unnecessary system complexity we have
considered all processing as one stage that takes $P_{i}$ clock ticks to
complete. The time between data sensing and packet transmission, the
_completion time_ , is $S_{i}$ clock ticks and the time between two sequential
packet transmissions, the _inter-completion time_ , is $Y_{i}$ clock ticks,
where the idle time between a packet transmission and the next generated
packet is $I_{i}$ clock ticks.

System Failure. IPDs suffer frequent power failures due to a lack of available
harvested energy. We do not explicitly consider energy as part of our system
model, as in [9, Section V], [17, 20], rather assuming that the depleted
energy will cause a number of random power failures. An amount of processing
time $L_{i,j}$ clock ticks, where the $i$ represents the overall cycle number
and $j$ the fail number within the cycle, will be wasted for each fail (since
the updated system state including this processing has not been checkpointed
from VM to NVM before failure). Our system will also be inactive for a period
of $R_{i,j}$ clock ticks after failure. During power failure no new data is
generated since the device cannot perform sensing. Once power is restored the
system takes $V_{i,j}$ clock ticks to restore the last checkpointed system
state from NVM to VM. For simplicity of analysis we assume that
$V_{i,1}=V_{i,j}=V$ for all $j$. In practice this term would likely be fixed
by design.

TimeAoI$\bigtimes$$\bullet$$\bigtimes$$\bullet$$\bigtimes$$\bullet$$Q_{A,i}$$Q_{A,i+1}$$S_{i-1}$$I_{i}$$S_{i}$$I_{i+1}$$Y_{i}$$Y_{i+1}$$S_{i+1}$$\bigtimes$$\scriptscriptstyle\largestar$$\scriptscriptstyle\bigstar$$\ddagger$$\medtriangleup$$\filledmedtriangleup$$\scriptscriptstyle\largestar$$\bullet$$\bigtimes$$K_{i,n}$$D$$L_{i,j}$$S_{i-1}$$R_{i,j}$$V$$K_{i,n+1}$$D$$I_{i}$

Figure 2: AoI evolution for an IPD that checkpoints its state with a fixed
regularity. Symbol notation: $\bigtimes$ denotes the start of sensing,
$\ddagger$ denotes device failure, $\bullet$ denotes the end of the final
checkpoint and instantaneous packet transmission,
$\scriptscriptstyle\largestar$ denotes the start of checkpointing from VM to
NVM, $\scriptscriptstyle\bigstar$ denotes the end of checkpointing from VM to
NVM, $\medtriangleup$ denotes start of restoration from NVM to VM, and
$\filledmedtriangleup$ denotes the end of restoration from NVM to VM. All
variables are defined in Section II.

Checkpointing Strategy. The system will save the current device state stored
in VM to NVM with a pre-determined regularity. This inter-checkpoint time is
given by $K_{i,n}$ clock ticks where $n$ is the checkpoint number within cycle
$i$. The action of checkpointing will also take a fixed amount of $D_{i,n}$
clock ticks to complete. Here, for simplicity of analysis, we assume that
$D_{i,1}=D_{i,n}=D$ for all $n$. This is consistent with, for example, [15,
Fig. 3]. We also assume that $P_{i}$ is a multiple of the inter-checkpointing
time.

Transmission. Our model considers the transmissions of packets to be
instantaneous and occurring after a final checkpoint.

##  III Age of Information Background

Let us now re-introduce several previously derived results that form the basis
of our analysis. Canonically we define AoI as [17, Eq. (1)] [9, Section II]

$\Delta(t)=t-u(t),$ (1)

where $\Delta(t)$ is the AoI of data sensed by the device, $t$ is the current
time, and $u(t)$ is the time stamp of the last completed packet. The AoI time
evolution for our proposed system model is depicted in Fig. 2. Using this
graphical representation we can calculate the expectation of (1) as follows.
Let us denote a trapezium $Q_{A,i}$, whose area is given by

$Q_{A,i}=\frac{1}{2}\left((S_{i-1}+Y_{i})^{2}-S_{i}^{2}\right).$ (2)

This is the isosceles triangle created by $S_{i-1}+Y_{i}$ minus the smaller
isosceles triangle with base $S_{i}$. The area $Q_{A,i+1}$ is highlighted in
Fig. 2 as an example. Given that $S_{i-1}$ and $Y_{i}$ are independent and
$S_{i-1}$ and $S_{i}$ are identically distributed, as considered in [17, Eq.
(5)], the expectation of (2) becomes

$\operatorname{\mathbb{E}}[Q_{A,i}]=\frac{1}{2}\operatorname{\mathbb{E}}[Y_{i}^{2}]+\operatorname{\mathbb{E}}[S_{i-1}]E[Y_{i}].$
(3)

As argued in [17, Eq. (6)], and in concordance with the geometry presented in
Fig. 2, the average AoI is

$\operatorname{\mathbb{E}}[\Delta]=\lambda\operatorname{\mathbb{E}}[Q_{A,i}],$
(4)

where $\lambda$ is the interarrival time of packets to the device. Since our
system model considers packet generation, rather than packet arrival, the
distribution of $\lambda$ will be predicated on the distribution of time
between sensing (which is equivalent to the distribution of time between
transmission) hence $\lambda=\frac{1}{E[Y]}$. Here we introduce $Y$ and $S$
for the _inter-completion time_ and _completion time_ , respectively, when
taking their expected values, $\operatorname{\mathbb{E}}[Y]$ and
$\operatorname{\mathbb{E}}[S]$, as time tends to infinity. This is possible
due to the ergodicity of the system. As such (4) simplifies to [17, Eq. (6)]

$\operatorname{\mathbb{E}}[\Delta]=\frac{\operatorname{\mathbb{E}}[Y^{2}]}{2\operatorname{\mathbb{E}}[Y]}+\operatorname{\mathbb{E}}[S].$
(5)

The average PAoI, a more manageable measure of data freshness compared to
average AoI, is given by [17, Eq. (7)] [9, Eq. (8)]

$\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]=\operatorname{\mathbb{E}}[Y]+\operatorname{\mathbb{E}}[S].$
(6)

##  IV Completion and Inter-Completion Time

Given (5) and (6) it is imperative that we find expressions for $Y_{i}$ and
$S_{i}$ from which we can calculate their expected values,
$\operatorname{\mathbb{E}}[Y]$ and $\operatorname{\mathbb{E}}[S]$, over many
cycles. From Fig. 2 we see that the _inter-completion time_ for cycle $i$ is

$Y_{i}=\underbrace{\vphantom{\sum_{j=1}^{f}\left(L_{i,j}+R_{i,j}+V\right)}I_{i}}_{\text{Idle
time}}\\!+\\!\underbrace{\sum_{j=1}^{f}\left(L_{i,j}+R_{i,j}+V\right)}_{\text{Events
associated with failure}}\\\
+\underbrace{\vphantom{\sum_{j=1}^{f}\left(L_{i,j}+R_{i,j}+V\right)}\sum_{n=1}^{h}K_{i,n}}_{\text{Processing
$\triangleq
P_{i}$}}\\!+\\!\underbrace{\vphantom{\sum_{j=1}^{f}\left(L_{i,j}+R_{i,j}+V\right)}Dh,}_{\text{Checkpointing}}$
(7)

where $f$ and $h$ are the number of system fails and the number of
successfully performed checkpoints during the period of time $Y_{i}$,
respectively. The time between data being sensed and a packet being
transmitted, the _completion time_ , for cycle $i$ is

$S_{i}=Y_{i}-I_{i}.$ (8)

##  V Expectation of Completion and Inter-Completion Time

To identify the expected values of AoI in (5) and (6), and hence understand
the freshness of data produced by the modelled IPD, we must first find the
expected values of (7) and (8) over many cycles. We assume that all variables
in (7) and (8) have well-defined means and known variance. Due to the assumed
ergodicity of the system we can also simplify notation when taking the
expected values of variables (for example, the expectation of $I_{i}$ is
$\operatorname{\mathbb{E}}[I]$ as $t$ tends to infinity). By following the
approach of [17, Eq. (10)], we use Wald’s identity to find that the expected
values of _inter-completion time_ and _completion time_ are

$\displaystyle\operatorname{\mathbb{E}}[Y]$
$\displaystyle=\operatorname{\mathbb{E}}[I]+\operatorname{\mathbb{E}}[f]\left(\operatorname{\mathbb{E}}[L]+\operatorname{\mathbb{E}}[R]+V\right)$
$\displaystyle\qquad+\operatorname{\mathbb{E}}[h]\operatorname{\mathbb{E}}[K]+D\operatorname{\mathbb{E}}[h],$
(9) $\displaystyle\operatorname{\mathbb{E}}[S]$
$\displaystyle=\operatorname{\mathbb{E}}[Y]-\operatorname{\mathbb{E}}[I],$
(10)

respectively. By definition, the amount of wasted processing per failure will
take a value $L_{i,j}\in[1\mathrel{{.}\,{.}}\nobreak K_{i,\theta}+D]$ clock
ticks where $L_{i,j}\in\mathbb{N}^{+}$ and $\theta$ is the checkpoint number
of the processing cycle started but interrupted in $L_{i,j}$. For instance in
Fig. 2, $\theta=n+1$ since the $K_{i,n+1}$ cycle was initially started in
$L_{i,j}$, however could not finish before failure. We also assume that all
possible values of $L_{i,j}$ are equally likely. Therefore, based on these
assumptions, the expectation of wasted processing time per failure is

$\operatorname{\mathbb{E}}[L]=\frac{\operatorname{\mathbb{E}}[K]+D+1}{2}.$
(11)

Given the definition of processing time $P_{i}$, given in the second summation
of (7), its expected value will be

$\operatorname{\mathbb{E}}[P]=\operatorname{\mathbb{E}}[h]\operatorname{\mathbb{E}}[K].$
(12)

Substituting (11) and (12) into (V) yields

$\operatorname{\mathbb{E}}[Y]=\
\operatorname{\mathbb{E}}[f]\left(C_{1}+\frac{\operatorname{\mathbb{E}}[P]}{2\operatorname{\mathbb{E}}[h]}\right)+C_{2}+D\operatorname{\mathbb{E}}[h],$
(13)

where $C_{1}=\operatorname{\mathbb{E}}[R]+V+\frac{D+1}{2}$, and
$C_{2}=\operatorname{\mathbb{E}}[I]+\operatorname{\mathbb{E}}[P]$ are defined
for compactness of presentation.

##  VI Expectation of Average PAoI

Given (6) and expressions (10) and (13) the average PAoI for our mixed-memory
IPD is therefore

$\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{MM}}=2\operatorname{\mathbb{E}}[f]\left(C_{1}+\frac{\operatorname{\mathbb{E}}[P]}{2\operatorname{\mathbb{E}}[h]}\right)+C_{2}\\\
\qquad+\operatorname{\mathbb{E}}[P]+2D\operatorname{\mathbb{E}}[h].$ (14)

We can see from this expression the clear conflict between over and under
checkpointing. If failure occurs, which is a core phenomenon associated with
an IPD, then an increase in the checkpointing frequency (meaning an increase
in $\operatorname{\mathbb{E}}[h]$) increases
$\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{MM}}$ through the
final $2D\operatorname{\mathbb{E}}[h]$ term—i.e. the overhead associated with
checkpointing. In contrast, an increase in $\operatorname{\mathbb{E}}[h]$ also
reduces the
$\frac{\operatorname{\mathbb{E}}[P]}{2\operatorname{\mathbb{E}}[h]}$ term,
since more frequent checkpointing reduces the expected wasted processing time
per power failure. From (14) we also observe that the constant $C_{1}$ (and
hence the constants $V$ and $D$) increase the average PAoI, so these should be
minimised by systems designers. Further, increases in
$\operatorname{\mathbb{E}}[I]$ and $\operatorname{\mathbb{E}}[R]$ will also
increase $\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{MM}}$,
however we consider these to be outside the control of the designer.

Minimising the Average PAoI. Due to the conflict of over and under
checkpointing we can find a value of $\operatorname{\mathbb{E}}[h]$ to
minimise the average PAoI as follows. Taking the derivative of (14), with
respect to $\operatorname{\mathbb{E}}[h]$ we have

$\frac{d\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{MM}}}{d\operatorname{\mathbb{E}}[h]}=2D-\frac{\operatorname{\mathbb{E}}[f]\operatorname{\mathbb{E}}[P]}{\operatorname{\mathbb{E}}[h]^{2}}.$
(15)

Then, letting (15) equal to zero and solving for
$\operatorname{\mathbb{E}}[h]$, we find that (14) is minimised when

$\operatorname{\mathbb{E}}[h]=\sqrt{\frac{\operatorname{\mathbb{E}}[f]\operatorname{\mathbb{E}}[P]}{2D}}.$
(16)

This expression is comparable to [19, Eq. (7)] and shows that checkpoint
optimisation is not inherently changed by the unique characteristics of the
sensor device. Expression (16) shows that the optimum number of checkpoints in
a cycle is based on three fundamental parameters of the system;
$\operatorname{\mathbb{E}}[f]$, $\operatorname{\mathbb{E}}[P]$, and
$\operatorname{\mathbb{E}}[D]$. This is consistent with intuition since a
decrease in the expected number of failures would mean fewer required
checkpoints, an increase in processing time would necessitate more
checkpoints, and an increase in the checkpoint overhead would reduce its
desirability.

##  VII Expectation of Average AoI

From (5) we can find an expression for the average AoI of our system by
substituting in (13) and (10), and by finding
$\operatorname{\mathbb{E}}[Y^{2}]$. Since we have assumed that the variance of
each term in $Y$ is known, we are able to use the definition of variance to
find $\operatorname{\mathbb{E}}[Y^{2}]$ from

$\operatorname{\mathbb{E}}[Y^{2}]=\mathrm{Var}(Y)+\operatorname{\mathbb{E}}[Y]^{2}.$
(17)

By substituting (17) into (5) the expression for the average AoI becomes

$\operatorname{\mathbb{E}}[\Delta]=\frac{\mathrm{Var}(Y)}{2\operatorname{\mathbb{E}}[Y]}+\frac{3\operatorname{\mathbb{E}}[Y]}{2}-\operatorname{\mathbb{E}}[I].$
(18)

As such, by substitution, we find that the average AoI of the system is

$\operatorname{\mathbb{E}}[\Delta]_{\text{MM}}=\frac{\mathrm{Var}(Y)}{2C_{3}+\frac{C_{4}}{\operatorname{\mathbb{E}}[h]}+2D\operatorname{\mathbb{E}}[h]}-\operatorname{\mathbb{E}}[I]\\\
+\frac{3}{2}\left(C_{3}+\frac{C_{4}}{2\operatorname{\mathbb{E}}[h]}+D\operatorname{\mathbb{E}}[h]\right),$
(19)

where $C_{3}=\operatorname{\mathbb{E}}[f]C_{1}+C_{2}$ and
$C_{4}=\operatorname{\mathbb{E}}[f]\operatorname{\mathbb{E}}[P]$ are defined
for compactness of presentation. From (19) we see that the average AoI, as
with the average PAoI, is dependent on $\operatorname{\mathbb{E}}[f]$ and
$\operatorname{\mathbb{E}}[h]$. Whilst minimisation of this expression with
respect to $\operatorname{\mathbb{E}}[h]$ is not presented here, a tractable
solution can be found by setting the derivative of (19) to zero and solving
for $\operatorname{\mathbb{E}}[h]$.

(a) Impact of Harvested Energy

(b) Impact of Memory Structure

(c) Impact of Checkpointing Strategy

Figure 3: Set of example numerical result (its source code is available at
[21]). (a) _Scenario RF 2_ conditions require fewer checkpoints than _Scenario
RF 1_. Under-checkpointing causes significant increase in average PAoI. (b)
Mixed-memory performs better than VM for most failure conditions. (c) SFC is
better than inaccurately selected single-frequency.

##  VIII Peak Age of Information: Mixed-Memory Versus Single-Memory
Architecture

Having identified an expression for the average PAoI of our model in (14) we
proceed to examine to what extent checkpointing in mixed-memory architecture
has affected the performance of our IPD compared to a single-memory device.
Whilst in practice, typical commercially available devices are mixed-memory
[1, Section 1], we can consider two possible alternatives, a single-memory IPD
entirely comprised of NVM [22, 23], or a single-memory IPD entirely comprised
of VM. We assume that both types of memory are able to perform processing at
the same rate.

######  Lemma 1.

An entirely NVM IPD will have a lower or equal average PAoI than a
checkpointing mixed-memory IPD.

###### Proof.

Using the same formulation as (7), the _inter-completion time_ for such an NVM
IPD would be

$Y_{i}=I_{i}+\sum_{j=1}^{f}R_{i,j}+P_{i},$ (20)

since the device does not checkpoint and the only impact of failure is the
system off-time. The _completion time_ would take the same form as (8).
Following the same steps as Sections V and VI, the average PAoI of the device
would be

$\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{\acs{nvm}}}=\operatorname{\mathbb{E}}[I]+2\operatorname{\mathbb{E}}[f]\operatorname{\mathbb{E}}[R]+2\operatorname{\mathbb{E}}[P].$
(21)

We can compare the above expression with the average PAoI of our system by
finding the difference between (14) and (21), i.e.

$\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{MM}}-\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{\acs{nvm}}}=2D\operatorname{\mathbb{E}}[h]\\\
+\operatorname{\mathbb{E}}[f]\left(2V+D+1+\frac{\operatorname{\mathbb{E}}[P]}{\operatorname{\mathbb{E}}[h]}\right),$
(22)

which shows that

$\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{\acs{nvm}}}\leq\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{MM}}\forall\operatorname{\mathbb{E}}[f],\operatorname{\mathbb{E}}[h],$
(23)

and hence a system comprised of entirely NVM would always perform better than
or equal to the mixed-memory system. ∎

######  Lemma 2.

Under certain environmental conditions a mixed-memory IPD will have a lower
average PAoI than a (single-memory) VM IPD.

###### Proof.

A single-memory device comprised of entirely VM, following the same
formulation as (7), would have an _inter-completion time_ of

$Y_{i}=I_{i}+\sum_{j=1}^{f}(R_{i,j}+\Gamma_{i,j}+I_{i,j})+P_{i},$ (24)

where $\Gamma_{i,j}$ is the amount of wasted processing that occurs due to
failure $j$ in cycle $i$ and the system does not checkpoint or restore (rather
it re-senses after failure). $I_{i,j}$ is the idle time before the system re-
senses after failure $j$. The expected value of $\Gamma_{i,j}$ will be
$\operatorname{\mathbb{E}}[\Gamma]=\frac{\operatorname{\mathbb{E}}[P]+1}{2}$
since the system could waste up to $P_{i}$ clock ticks of processing per fail
and each amount of wasted processing time is equally likely. The _completion
time_ would take the same form as (8). Following the same steps as Sections V
and VI, the average PAoI of a single VM IPD is

$\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{\acs{vm}}}=2\operatorname{\mathbb{E}}[f]\left(\operatorname{\mathbb{E}}[R]+\frac{\operatorname{\mathbb{E}}[P]+1}{2}+\operatorname{\mathbb{E}}[I]\right)\\\
+\operatorname{\mathbb{E}}[I]+2E[P].$ (25)

The above expression can be greater than or smaller than (14) depending on the
selected system parameters, hence

$\exists\operatorname{\mathbb{E}}[f],\operatorname{\mathbb{E}}[h]\ni\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{\acs{vm}}}>\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{MM}},$
(26)

and thus there is a set of environments in which checkpointing in mixed-memory
architecture is more efficient than not checkpointing in single-memory VM
architecture. This improvement is most evident when the mixed-memory IPD has a
low checkpointing overhead and high failure rate. ∎

##  IX Improving System Resilience in Variable Environmental Conditions

Thus far we have considered a checkpointing system that can be optimised based
on a known expected number of failures, yet in reality IPDs are often placed
in environments with variable and unpredictable failure rates—making it
difficult to pre-determine an optimum rate of checkpointing. We now propose an
alternative method of TDC for mixed-memory devices to improve system
resilience— Split-Frequency Checkpointing (SFC)—in which the inter-
checkpointing time varies between predefined intervals $\alpha$ and $\beta$.
Here we once again use the framework devised in Sections II and III. We now
assume that the duration of processing between checkpoints, previously
$K_{i,n}$, varies between two fixed amounts, $K_{i,\alpha}$ and $K_{i,\beta}$.
Then, the processing time
$P_{i}=\sum_{\alpha=1}^{h_{\alpha}}K_{i,\alpha}+\sum_{\beta=1}^{h_{\beta}}K_{i,\beta}$.
Additionally, the expected wasted processing per fail would be
$\operatorname{\mathbb{E}}[L]=p_{\alpha}\operatorname{\mathbb{E}}[L_{\alpha}]+p_{\beta}\operatorname{\mathbb{E}}[L_{\beta}]$
where $p_{\alpha}$ and $p_{\beta}$ are the probabilities of failure during an
$\alpha$ and $\beta$ checkpoint, respectively, such that
$p_{\alpha}=\frac{\operatorname{\mathbb{E}}[K_{\alpha}]}{\operatorname{\mathbb{E}}[K_{\alpha}]+\operatorname{\mathbb{E}}[K_{\beta}]}$
and
$p_{\beta}=\frac{\operatorname{\mathbb{E}}[K_{\beta}]}{\operatorname{\mathbb{E}}[K_{\alpha}]+\operatorname{\mathbb{E}}[K_{\beta}]}$.
$\operatorname{\mathbb{E}}[L_{\alpha}]$ and
$\operatorname{\mathbb{E}}[L_{\beta}]$ are the expected wasted processing due
to a failure in an $\alpha$ and $\beta$ checkpoint, respectively, where
$\operatorname{\mathbb{E}}[L_{\alpha}]=\frac{\operatorname{\mathbb{E}}[K_{\alpha}]+D+1}{2}$
and
$\operatorname{\mathbb{E}}[L_{\beta}]=\frac{\operatorname{\mathbb{E}}[K_{\beta}]+D+1}{2}$.
This can also be expressed as

$\operatorname{\mathbb{E}}[L]=\frac{\operatorname{\mathbb{E}}[K_{i,\alpha}]^{2}+\operatorname{\mathbb{E}}[K_{i,\beta}]^{2}}{2(\operatorname{\mathbb{E}}[K_{i,\alpha}]+\operatorname{\mathbb{E}}[K_{i,\beta}])}+\frac{D+1}{2}.$
(27)

Following the same derivation of average PAoI as in Sections V and VI, the
average PAoI of a SFC system with two frequencies is

$E[\Delta^{\text{Peak}}]_{\text{MM(split)}}=C_{2}+2D(\operatorname{\mathbb{E}}[h_{\alpha}]+\operatorname{\mathbb{E}}[h_{\beta}])\\\
+\operatorname{\mathbb{E}}[P]+2\operatorname{\mathbb{E}}[f]\left(C_{1}+\frac{\operatorname{\mathbb{E}}[K_{i,\alpha}]^{2}+\operatorname{\mathbb{E}}[K_{i,\beta}]^{2}}{2([\operatorname{\mathbb{E}}[K_{i,\alpha}]+\operatorname{\mathbb{E}}[K_{i,\beta}])}\right).$
(28)

From this expression we observe that the average PAoI is dependent on a number
of system parameters (including $\operatorname{\mathbb{E}}[P]$,
$\operatorname{\mathbb{E}}[f]$, and $D$), however most interesting is the
dependence on inter-checkpointing times
$\operatorname{\mathbb{E}}[K_{i,\alpha}$] and
$\operatorname{\mathbb{E}}[K_{i,\beta}$], which is notably different to the
$\frac{\operatorname{\mathbb{E}}[P]}{2\operatorname{\mathbb{E}}[h]}\rightarrow\frac{\operatorname{\mathbb{E}}[K]}{2}$
term in (14).

##  X Numerical Results

We now provide a set of example numerical results in Fig. 3 using _Scenario RF
1_ and _Scenario RF 2_ energy harvesting conditions, with data taken from [24,
Fig. 1] and summarized in Table I—we note that we have converted $\mathrm{ms}$
to our base units of clock ticks therein).

Impact of Harvested Energy. We present the average PAoI of our considered
mixed-memory IPD system (expression (14)) in Fig. 3a using the parameters of
Table I. From Fig. 3a we see that the average PAoI varies under different
energy conditions and that the decrease in $\operatorname{\mathbb{E}}[f]$
between _RF 1_ and _RF 2_ decreases the value of
$\operatorname{\mathbb{E}}[h]$ that minimises average PAoI. We also see that
under-checkpointing has a far more significant impact of data freshness than
over-checkpointing.

Impact of Memory Structure. We also consider the relationship between memory
architecture and data freshness. Fig. 3b presents plotted expressions (14),
(21), and (25) as a function of the expected number of failures
$\operatorname{\mathbb{E}}[f]$ (using Table I RF1 parameters and
$\operatorname{\mathbb{E}}[h]=10$ for MM). From Fig. 3b it is evident that,
whilst not universally true, for an expected checkpointing overhead and above
a low number of failures
$\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{VM}}>\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{MM}}>\operatorname{\mathbb{E}}[\Delta^{\text{Peak}}]_{\text{NVM}}$.
This shows that whilst entirely NVM architecture will always produce the best
possible average PAoI, mixed-memory structures using checkpointing can provide
significant improvements in data freshness compared with entirely volatile
IPDs.

Impact of Checkpointing Strategy. Finally we show the impact of checkpoining
strategy by plotting expressions (14) and (28). Results are presented in Fig.
3c. We see that the system using two inter-checkpointing times
($\operatorname{\mathbb{E}}[K_{i,\alpha}]=5$ and
$\operatorname{\mathbb{E}}[K_{i,\beta}]=20$) is the most efficient for a range
$30\lessapprox\operatorname{\mathbb{E}}[f]\lessapprox 50$ and also provides
reasonable performance for all $\operatorname{\mathbb{E}}[f]$. Whilst SFC
cannot exceed the theoretical optimum for a single frequency (expression (16))
it can provide additional resilience by reducing the risk of a very high
average PAoI due to an inappropriately chosen inter-checkpoint interval in an
environment with unknown or variable failure rate.

Table I: System Parameter Values used for Numerical Results

| $\operatorname{\mathbb{E}}[P]^{\diamond}$ | $\operatorname{\mathbb{E}}[R]^{\ast}$ | $\operatorname{\mathbb{E}}[f]^{\ast}$ | $\operatorname{\mathbb{E}}[I]^{\lhd}$ | $D^{\wr}$ | $V^{\dagger}$
---|---|---|---|---|---|---
_Scenario RF 1_ | 500 | 50 | 15 | 200 | 5 | 10
_Scenario RF 2_ | 500 | 75 | 6 | 200 | 5 | 10

⋄Set as a baseline for the system. This value varies significantly based on
processing needs. ∗Representative of the dynamic variation of off-time for the
first two scenarios in [24, Fig.1] where failure occurs approximately every
$50\text{\,}\mathrm{ms}$ and $100\text{\,}\mathrm{ms}$, respectively.
⊲Approximate boot time of TinyOS from [24, Section 2]. ≀Overhead can vary
significantly in real-world system, $5\text{\,}\mathrm{ms}$ is of the order of
magnitude expected compared with on-time in [24, Fig.1]. †Restoration overhead
is typically around twice the checkpoint overhead due to additional management
and fixed boot costs.

##  XI Conclusion

In this paper we have considered an Intermittently-Powered Device (IPD) with
mixed-memory architecture that periodically checkpoints the system state from
volatile memory to non-volatile memory—from which it can be restored should
power failure occur. We have identified expressions for the average Age of
Information (AoI) and average Peak Age of Information (PAoI) of the system,
and found a relationship for the expected checkpointing rate that minimises
the expected PAoI. We have also shown that a mixed-memory IPD using Time-
Dependent Checkpointing (TDC) can reduce the system PAoI compared with a
single volatile memory IPD for selected system parameters. Further, we have
proposed an alternative TDC scheme, Split-Frequency Checkpointing, which can
improve IPD performance compared with inaccurately selected single-frequency
checkpoint intervals.

## References

  * [1] B. Lucia, V. Balaji, A. Colin, K. Maeng, and E. Ruppel, “Intermittent computing: Challenges and opportunities,” in _Proc. SNAPL_ , Asilomar, CA, USA, May 2017.
  * [2] K. Ganesan, J. San Miguel, and N. Enright Jerger, “The what’s next intermittent computing architecture,” in _Proc. IEEE HPCA_ , Washington, DC, USA, Feb. 2019.
  * [3] M. Surbatovich, B. Lucia, and L. Jia, “Towards a formal foundation of intermittent computing,” in _Proc. ACM OOPSLA_ , Chicago, IL, USA, Nov. 2020\.
  * [4] V. Kortbeek, K. S. Yıldırım, A. Bakar, J. Sorber, J. Hester, and P. Pawełczak, “Time-sensitive intermittent computing meets legacy software,” in _Proc. ACM ASPLOS_ , Lausanne, Switzerland, Mar. 2020.
  * [5] J. de Winkel, C. Delle Donne, K. S. Yıldırım, P. Pawełczak, and J. Hester, “Reliable timekeeping for intermittent computing,” in _Proc. ACM ASPLOS_ , Lausanne, Switzerland, Mar. 2020.
  * [6] J. Hester and J. Sorber, “The future of sensing is batteryless, intermittent, and awesome,” in _Proc. ACM SenSys_ , Delft, The Netherlands, Nov. 2017.
  * [7] J. S. Broadhead and P. Przemysław, “Position paper: Why intermittent computing could unlock low-power visible light communication,” in _Proc. Workshop on Light Up the IoT (ACM MobiCom 2020 Workshop)_ , London, United Kingdom, Sep. 2020.
  * [8] S. Kaul, R. D. Yates, and M. Gruteser, “Real-time status: How often should one update?” in _Proc. IEEE INFOCOM_ , Orlando, FL, USA, Mar. 2012\.
  * [9] R. D. Yates, Y. Sun, D. R. Brown III, S. K. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” Jul. 2020, arXiv:2007.08564.
  * [10] C. Kam, S. Kompella, and A. Ephremides, “Age of information under random updates,” in _Proc. IEEE ISIT_ , Istanbul, Turkey, Jul. 2013.
  * [11] A. Behrouzi-Far, E. Soljanin, and R. D. Yates, “Data freshness in leader-based replicated storage,” in _Proc. IEEE ISIT_ , Los Angeles, CA, USA, Jun. 2020.
  * [12] S. Kaul and R. D. Yates, “Age of information: Updates with priority,” in _Proc. IEEE ISIT_ , Vail, CO, USA, May 2018.
  * [13] A. Baknina, S. Ulukus, O. Ozel, J. Yang, and A. Yener, “Sending information through status updates,” in _Proc. IEEE ISIT_ , Vail, CO, USA, Jun. 2018.
  * [14] Y.-P. Hsu, E. Modiano, and L. Duan, “Age of information: Design and analysis of optimal scheduling algorithms,” in _Proc. IEEE ISIT_ , Aachen, Germany, Jun. 2017.
  * [15] D. Balsamo, A. S. Weddell, A. Das, A. R. Arreola, D. Brunelli, B. M. Al-Hashimi, G. V. Merrett, and L. Benini, “Hibernus++: A self-calibrating and adaptive system for transiently-powered embedded devices,” _IEEE Trans. Comput.-Aided Design Integr. Circuits Syst._ , vol. 35, no. 12, pp. 1968–1980, Mar. 2016.
  * [16] O. Subasi, G. Kestor, and S. Krishnamoorthy, “Toward a general theory of optimal checkpoint placement,” in _Proc. IEEE International Conference on Cluster Computing_ , Honolulu, HI, USA, Sep. 2017.
  * [17] O. Ozel, “Timely status updating through intermittent sensing and transmission,” in _Proc. IEEE ISIT_ , Los Angeles, CA, USA, Jun. 2020.
  * [18] S. Jayasekara, A. Harwood, and S. Karunasekera, “A utilization model for optimization of checkpoint intervals in distributed stream processing systems,” _Future Generation Computer Systems_ , vol. 110, Apr. 2020.
  * [19] S. Di, M. S. Bouguerra, L. Bautista-Gomez, and F. Cappello, “Optimization of multi-level checkpoint model for large scale HPC applications,” in _Proc. IEEE Int. Parallel and Distributed Processing Symp._ , Phoenix, AZ, USA, Aug. 2014.
  * [20] P. Rafiee and O. Ozel, “Active status update packet drop control in an energy harvesting node,” in _Proc. IEEE SPAWC_ , Atlanta, GA, USA, May 2020\.
  * [21] J. S. Broadhead and P. Pawełczak, “Source code for numerical results of this paper,” https://github.com/tudssl/intermittency-aoi, Feb. 2021, last accessed: Feb. 1, 2021.
  * [22] F. Su, K. Ma, X. Li, T. Wu, Y. Liu, and V. Narayanan, “Nonvolatile processors: Why is it trending?” in _Proc. ACM/IEEE DATE_ , Lausanne, Switzerland, Mar. 2017.
  * [23] T.-K. Chien, L. Chiou, C.-C. Lee, Y.-C. Chuang, S.-H. Ke, S.-S. Sheu, H.-Y. Li, P.-H. Wang, T.-K. Ku, M.-J. Tsai, and C.-I. Wu, “An energy-efficient nonvolatile microprocessor considering software-hardware interaction for energy harvesting applications,” in _Proc. IEEE VLSI-DAT_ , Hsinchu, Taiwan, Apr. 2016.
  * [24] B. Ransford, J. Sorber, and K. Fu, “Mementos: System support for long-running computation on RFID-scale devices,” in _Proc. ACM ASPLOS_ , Newport Beach, CA, USA, Mar. 2011.

  *[AoI]: Age of Information
  *[IoT]: Internet of Things
  *[TDC]: Time-Dependent Checkpointing
  *[PAoI]: Peak Age of Information
  *[VM]: Volatile Memory
  *[NVM]: Non-Volatile Memory
  *[IPD]: Intermittently-Powered Device
  *[SFC]: Split-Frequency Checkpointing
  *[IPDs]: Intermittently-Powered Device
  *[HPC]: High Performance Computing


# Representation Learning for Context-Dependent Decision-Making ††thanks: Y.
Qin and F. Pasqualetti are with the Department of Mechanical Engineering
({yuzhenqin,fabiopas}@engr.ucr.edu), and S. Oymak is with the Department of
Electrical and Computer Engineering (oymak@ece.ucr.edu), University of
California, Riverside, CA, USA. T. Menara is with the Department of Mechanical
and Aerospace Engineering, University of California, San Diego, La Jolla, CA
92093, USA. S. Ching is with the Department of Electrical and Systems
Engineering and Biomedical Engineering, Washington University in St. Louis,
MO, USA. This material was based upon work supported by awards ARO
W911NF1910360 and NSF NCS-FO-1926829.

Yuzhen Qin, Tommaso Menara, Samet Oymak, ShiNung Ching, and Fabio Pasqualetti

###### Abstract

Humans are capable of adjusting to changing environments flexibly and quickly.
Empirical evidence has revealed that representation learning plays a crucial
role in endowing humans with such a capability. Inspired by this observation,
we study representation learning in the sequential decision-making scenario
with contextual changes. We propose an online algorithm that is able to learn
and transfer context-dependent representations and show that it significantly
outperforms the existing ones that do not learn representations adaptively. As
a case study, we apply our algorithm to the Wisconsin Card Sorting Task, a
well-established test for the mental flexibility of humans in sequential
decision-making. By comparing our algorithm with the standard Q-learning and
Deep-Q learning algorithms, we demonstrate the benefits of adaptive
representation learning.

##  I Introduction

Real-world decision-making is complicated since environments are often complex
and rapidly changing. Yet, human beings have shown the remarkable ability to
make good decisions in such environments. At the core of this ability is the
flexibility to adapt their behaviors in different situations [1]. Such
adaption is usually fast since humans learn to abstract experiences into
compact representations that support the efficient construction of new
strategies [2].

Lacking the ability to adapt to new environments and abstract compressed
information from experiences, existing learning techniques often struggle in
complex scenarios that undergo contextual changes. To elaborate on this point,
let us consider a running example – the Wisconsin Card Sorting Task (WCST).
The WCST is one of the most frequently used neuropsychological tests to assess
people’s ability to abstract information and shift between contexts [3].
Illustrated in Fig. 1, participants are initially given four cards and are
required to associate a sequence of stimulus cards with these four cards
according to some sorting rules – number, color, and shape. Participants have
no prior knowledge of the current sorting rule, thus need to learn it by trial
and error. They receive a feedback indicating whether their sort action is
correct or incorrect. What makes the task more challenging is that the sorting
rule changes every once in a while without informing the participants. Thus,
the participants need to learn the changes and adjust their strategy.

Healthy humans usually perform very well in the WCST. Some neuroimaging
studies have found that different brain regions, such as the dorsolateral
prefrontal cortex and the anterior cingulate cortex, play crucial roles in
context shifting, error detection, and abstraction, all of which are needed by
the WCST [4]. By contrast, classical learning algorithms such as tabular-Q-
learning and Deep-Q-learning struggle in the WCST, especially when the sorting
rule changes rapidly. It can be seen from Fig. 1 that standard reinforcement
learning (RL) algorithms111For the Deep-Q-learning, we considered a three-
layer structure with 12 nodes in the hidden layers (more details can be found
in Section IV). Deeper or wider networks were also tried, but similar
performances were observed. perform barely better than the strategy that takes
random sorting actions at every round.

Motivated by these observations, we aim to develop decision-making strategies
that have more human-like performance. In this paper, we focus on
demonstrating the benefits of the ability to abstract compact information
(i.e., learn the representation) and adapt to changing contexts in the
framework of a sequential decision-making model – linear multi-armed bandits.
As we will show later, the WCST can be readily modeled in this framework.

Figure 1: The Wisconsin Card Sorting Task. Left: Illustration of the task.
Participants need to sort a sequence of stimulus cards into four categories
according to unknown changing rules: number, color, and shape. Right:
Performance of classical reinforcement learning algorithms in this task where
the sorting rule changes after every 20 rounds. Here, we consider that
participants receive reward 1 for a correct sorting action and 0 otherwise
Each shaded area contains 20 realizations of the corresponding algorithm.

Related Work. As a classical model for decision-making, multi-armed bandits
have attracted extensive interests. The Upper Confidence Bound (UCB) algorithm
and its variants have proven their strength in tackling multi-armed bandit
problems (e.g., see [5, 6]). Various generalizations of the classical bandit
problem have been studied, in which non-stationary reward functions [7, 8],
restless arms [9], satisficing reward objectives [10], risk-averse decision-
makers [11], heavy-tailed reward distributions [12], and multiple players [13]
are considered. Recently, increasing attention has been also paid to tackling
bandit problems in a distributed fashion (e.g., see [14, 15, 16, 17]).

Representation learning has been applied to a wide range of practical problems
including natural language processing, computer vision, and reinforcement
learning [18]. Some recent studies have shown that representation learning
improves data efficiency in the multi-task linear regression [19].
Representation learning has been proven to be beneficial for multi-task bandit
problems, e.g., see [20, 21, 22, 23]. Most of the aforementioned studies focus
on batch learning where all the tasks are played simultaneously. Despite some
attempts (e.g., see [24]), results on sequential bandits are sparse, although
one often needs to execute tasks sequentially in real life.

Paper Contribution. In this paper, we consider a decision-making scenario with
changing contexts. A multi-task decision-making model with tasks sequentially
drawn from distinct sets is used to describe a dynamic environment. Our main
contribution is an algorithm that is able to abstract low-dimensional
representations and adapt to contextual changes. We further derive some
analytical results, showing the benefits of adaptive representation learning
in complex and dynamic environments. To demonstrate our theoretical findings,
we apply our algorithm to the WCST and show that it significantly outperforms
classical RL algorithms.

Notation. Let $\mathbb{R}$, $\mathbb{R}^{+}$, and $\mathbb{Z}^{+}$ be the sets
of real numbers, positive reals, and positive integers, respectively. Given a
matrix $A\in\mathbb{R}^{m\times n}$, ${\rm span}(A)$ denotes its column space,
$A_{\perp}$ denote the matrix with orthonormal columns that form the
perpendicular complement of ${\rm span}(A)$, $\|A\|_{F}$ denotes its Frobenius
norm, and $[A]_{i}$ denotes its $i$th column. For any $x\in R^{+}$, $\lceil
x\rceil$ denotes the smallest integer larger than $x$. Given two functions
$f,g:\mathbb{R}^{+}\to\mathbb{R}^{+}$, we write $f(x)=O(g(x))$ if there is
$M_{o}>0$ and $x_{0}>0$ such that $f(x)\leq M_{o}g(x)$ for all $x\geq x_{0}$,
and $f(x)=\tilde{O}(g(x))$ if $f(x)=O(g(x)\log^{k}(x))$. Also, we denote
$f(x)=\Omega(g(x))$ if there is $M_{\Omega}>0$ and $x_{0}>0$ such that
$f(x)\geq M_{\Omega}g(x)$ for all $x\geq x_{0}$, and $f(x)=\Theta(g(x))$ if
$f(x)=O(g(x))$ and $f(x)=\Omega(g(x))$.

##  II Problem Setup

Motivated by real-world tasks like the WCST, we consider the following
sequential decision-making model:

$\displaystyle y_{t}=x_{t}^{\top}\theta_{\sigma(t)}+\eta_{t},$ (1)

where $x_{t}\in\mathcal{A}\subseteq\mathbb{R}^{d}$ is the action taken from
the action set $\mathcal{A}$ at round $t$, and $y_{t}\in\mathbb{R}$ is the
reward received by the agent (i.e., decision maker). The reward depends on the
action in a linear way determined by the unknown coefficient
$\theta_{\sigma(t)}$, and is also affected by the $1$-sub-Gaussian noise
$\eta_{t}$ that models the uncertainty. To make good decisions, the agent
needs to learn $\theta_{\sigma(t)}$ under the influence of uncertainty. This
decision-making model is also known as linear bandits [25]. Note that the
coefficient $\theta_{\sigma(t)}$ is time-varying, and $\sigma(t)$ is the
switching signal. For simplicity, we assume that each task is played for $N$
rounds, i.e., $\sigma(t)$ changes its value after every $N$ rounds. Further,
we assume that the agent plays $S$ tasks in total, and denote
$\mathcal{S}=\\{\theta_{1},\theta_{2},\dots,\theta_{S}\\}$ as the task
sequence.

To model the context changes that underlie real-world tasks like the WCST, we
assume that $\theta_{\sigma(t)}$ takes values from different sets.
Specifically, we assume there are $m$ sets
$\mathcal{S}_{1},\mathcal{S}_{2},\dots,\mathcal{S}_{m}$ from which
$\theta_{\sigma(t)}$ takes values in sequence. In each $\mathcal{S}_{k}$,
there are $n_{k}$ ($n_{k}$ can be infinite) tasks
$\theta^{k}_{1},\dots,\dots,\theta^{k}_{n_{k}}$, and we assume that they share
a common linear feature extractor. Different sets have different feature
extractors. Specifically, there is $B_{k}\in\mathbb{R}^{d\times r_{i}}$ with
orthonormal vectors such that for any $\theta^{k}_{i}$ there exists
$\alpha_{i}^{k}\in\mathbb{R}^{r_{i}}$ so that
$\theta^{k}_{i}=B_{k}\alpha^{k}_{i}$ (see Fig. 2). For simplicity, we assume
that all the extractors have the same dimension $r$, i.e., $r_{i}=r$ for all
$i$. Here, each of these mutually different matrices $B_{1},\dots,B_{m}$ are
also referred to as a linear representation [26] for the tasks in the
respective set.

As for real-world problems like the WCST, $B_{k}$ describes the low-
dimensional information that participants can abstract. For different
contexts, participants usually need to abstract distinct low-dimensional
features. Similar to the WCST in which participants do not know when the
sorting rule changes, we further assume that the agent is not informed when
$\theta_{\sigma(t)}$ starts to take values from a different task set. Denote
$\tau_{k},k=1,\dots,m$, as the unknown number of sequential tasks that
$\theta_{\sigma(t)}$ takes from $\mathcal{S}_{k}$.

Figure 2: Sequential decision-making scenario with contextual changes. Tasks
are taken from distinct sets in sequence. The tasks in each set share a low-
dimensional representation. The length of each subsequence is unknown.

The agent’s goal is to maximize the cumulative reward over the course of $SN$
rounds. To measure the performance, we introduce the regret
$R_{SN}=\sum_{t=1}^{SN}(x_{t}^{*}-x_{t})^{\top}\theta_{s(t)},$ where
$x^{*}_{t}$ is the optimal action that maximizes the reward at round $t$.
Given $\theta$, denote
$g(\theta)=\operatorname*{arg\,max\,\,}_{x\in\mathcal{A}}x^{\top}\theta$, and
then $x^{*}_{t}=g(\theta_{s(t)})$. The agent’s objective is then equivalent to
minimizing the regret $R_{SN}$.

We next make some standard assumptions on the action set $\mathcal{A}$ and the
task coefficients following existing studies (e.g., see [27, 28]), which are
considered to be satisfied throughout the remainder of this paper.

###### Assumption II.1

We assume that: (a) the action set $\mathcal{A}$ is a unit ball centered at
the origin, i.e., $\mathcal{A}:=\\{x\in\mathbb{R}^{d}:\|x\|\leq 1\\}$, and (b)
there are positive constants $\phi_{\min}$ and $\phi_{\max}$ so that
$\phi_{\min}\leq\|\theta_{s}\|\leq\phi_{\max}$ for all
$s\in\\{1,2,\dots,S\\}$.

Inspired by humans’ strategy, we seek to equip the agent with the ability to
learn and exploit representations and to quickly adjust to contextual changes
so that it can perform well even in complex environments with context changes.

##  III Adaptive Representation Learning

In this section, we present our main results. We first analytically
demonstrate why representation learning is beneficial especially for complex
tasks that have high dimensions. Second, we propose a strategy to explore and
transfer the representation under the setting of sequential tasks. Finally, we
present our main algorithm that has the ability to adjust to contextual
changes.

###  III-A Benefits of representation learning

To demonstrate the benefits of representation learning, we first restrict our
attention to a single-task model

$\displaystyle y_{t}=x_{t}^{\top}\theta+\eta_{t},$ (2)

where the task $\theta$ is played for $N$ times. For this classical model,
existing studies have established the lower bound for its regret [27, 25],
presented in the next lemma.

######  Lemma III.1 (Classical Lower Bound)

Let $\mathcal{P}$ be the set of all policies, and $\mathcal{I}$ be the set of
all the possible tasks. Then, for any $d\in\mathbb{Z}^{+}$ and $N>d^{2}$, the
regret $R_{N}$ for the task (2) satisfies
$\inf_{\mathcal{P}}\sup_{\mathcal{I}}\operatorname{\mathbb{E}}R_{N}=\Omega(d\sqrt{N}).$
$\triangle$

This lemma indicates that there is a constant $c>0$ such that the expected
regret incurred by any policy is no less than $cd\sqrt{N}$ for any
$d\in\mathbb{Z}^{+}$ and $N>d^{2}$. Next, we show how some additional
information on $\theta$ affects this lower bound.

######  Lemma III.2 (Lower Bound with a Representation)

Suppose there is a known matrix $B\in\mathbb{R}^{d\times r}$ with $r<d$ such
that $\theta=B\alpha$ for some $\alpha\in\mathbb{R}^{r}$. Let $\mathcal{P}$ be
the set of all policies, and $\mathcal{I}$ be the set of all the possible
tasks. Then, for any $d\in\mathbb{Z}^{+}$ and $N>d^{2}$, the regret $R_{N}$
for the task (2) satisfies
$\inf_{\mathcal{P}}\sup_{\mathcal{I}}\operatorname{\mathbb{E}}R_{N}=\Omega(r\sqrt{N}).$
$\triangle$

###### Proof:

Let $z_{t}=B^{\top}x_{t}$, and then the model in (2) becomes
$y_{t}=z_{t}^{\top}\alpha+\eta_{t}$. As a consequence, the problem becomes to
deal with a task with dimension $r$ instead of $d$. Following similar steps as
in [27], it can be shown that the minimax lower bound for the regret is
$\inf_{\mathcal{P}}\sup_{\mathcal{I}}\operatorname{\mathbb{E}}R_{N}=\Omega(r\sqrt{N})$,
which completes the proof. ∎

Comparing Lemma III.2 with Lemma III.1, one finds that the regret lower bound
decreases dramatically if $r\ll d$. This is because, with the knowledge of the
representation $B\in\mathbb{R}^{d\times r}$, one does not need to explore the
entire $\mathbb{R}^{d}$ space to learn the task coefficient $\theta$ for
decision-making. Instead, one only needs to learn $\alpha$ by exploring a much
lower-dimensional subspace ${\rm span}(B)$ and estimate $\theta$ by
$\hat{\theta}=B\hat{\alpha}$. As a consequence, $\theta$ can be learned much
more efficiently, which helps the agent make better decisions at earlier
stages.

Yet, such a representation $B$ is typically unknown beforehand. The agent
usually needs to estimate $B$ from its experiences before utilizing it. In the
next subsection, we show how to explore and transfer the representation in the
setting of sequential tasks.

###  III-B Representation learning in sequential tasks

Representation learning in the setting of sequential tasks is challenging,
particularly when the agent has no knowledge of the number of sequential tasks
that share the same representation. There is a trade-off between the need to
explore more tasks to construct a more accurate estimate of the underlying
representation and the incentive to exploit the learned representation for
more efficient learning and higher instant rewards.

To investigate how to balance the trade-off, we consider that the agent plays
$\tau$ tasks in sequence, i.e.,
$\mathcal{T}=\\{\theta_{1},\theta_{2},\dots,\theta_{\tau}\\}$, without knowing
the number of tasks $\tau$. There is an unknown matrix
$B\in\mathbb{R}^{d\times r}$ such that for any $i$ it holds that
$\theta_{i}=B\alpha_{i}$ for some $\alpha_{i}\in\mathbb{R}^{r}$. In this
setting we aim to find a representation learning policy for each task
subsequence in Fig. 2, i.e., a within-context policy.

We propose an algorithm, the sequential representation learning algorithm
(SeqRepL, see Algorithm 3), that alternates between two sub-algorithms –
representation exploration (RE) and representation transfer (RT) algorithms.
Let us first elaborate on these two sub-algorithms, respectively.

Algorithm 1 Representation Exploration (RE)

Input: Horizon N, exploration length $N_{1}=\lceil d\sqrt{N}\rceil$

for $t=1:N_{1}$ do take $x_{t}=a_{i}$, $i=({t-1\mod d})+1$, where

$[a_{1},\dots,a_{d}]$ is any orthonormal basis of $\mathbb{R}^{d}$;

compute $\hat{\theta}=(X_{\rm re}X_{\rm re}^{\top})^{-1}X_{\rm re}Y_{\rm re}$,
where $X_{\rm re}=[x_{1},\dots,x_{N_{1}}]$, $Y_{\rm
re}=[y_{1},\dots,y_{N_{1}}]^{\top}$;

for $t=N_{1}+1:N$ do take
$x_{t}=\operatorname*{arg\,max\,\,}_{x\in\mathcal{A}}x^{\top}\hat{\theta}$

1) RE algorithm. RE, shown in Algorithm 1, is an explore-then-commit (ETC)
algorithm, which contains two phases: exploration and commitment, consisting
of $N_{1}$ and $N-N_{1}$ rounds, respectively. The central goal of RE is to
construct an accurate $\hat{\theta}_{i}$ for each task so that the collection
of $\hat{\theta}_{i}$’s can recover an accurate representation $\hat{B}$
(which will be shown soon). Meanwhile, we want to ensure that the algorithm
does not incur too much regret. To strike the balance, we set the exploration
length $N_{1}=\lceil d\sqrt{N}\rceil$. The exploration phase is accomplished
on the entire $\mathbb{R}^{d}$ space, in which $d$ linearly independent
actions are repeatedly taken in sequence. Then, $\theta$ is estimated by the
least-square regression $\hat{\theta}=(X_{\rm re}X_{\rm re}^{\top})^{-1}X_{\rm
re}Y_{\rm re}$, where $X_{\rm re}=[x_{1},\dots,x_{N_{1}}]$, $Y_{\rm
re}=[y_{1},\dots,y_{N_{1}}]^{\top}$. In the commitment phase, the greedy
action
$x_{t}=\operatorname*{arg\,max\,\,}_{x\in\mathcal{A}}x^{\top}\hat{\theta}$ is
taken. Note that the choice of $N_{1}$ ensures that the upper bound of RE is
$O(d\sqrt{N})$, which matches the lower bound in Lemma III.1. The proof
follows similar steps as those for Theorem 3.1 in [27].

Algorithm 2 Representation Transfer (RT)

Input: Horizon $N$, $\hat{B}\in\mathbb{R}^{d\times r}$, exploration length
$N_{2}=\lceil r\sqrt{N}\rceil$

for $t=1:N_{2}$ do take $x_{i}=a^{\prime}_{i}$, $i=({t-1\mod r})+1$, where

$[a^{\prime}_{1},\dots,a^{\prime}_{r}]$ is any orthonormal basis of ${\rm
span}(\hat{B})$;

compute $\hat{\alpha}=(\hat{B}^{\top}X_{\rm rt}X_{\rm
rt}^{\top}\hat{B})^{-1}\hat{B}^{\top}X_{\rm rt}Y_{\rm rt}$ and
$\hat{\theta}=\hat{B}\hat{\alpha}$, where $X_{\rm
rt}=[x_{1},x_{2},\dots,x_{N_{2}}]$ and $Y_{\rm
rt}=[y_{1},y_{2},\dots,y_{N_{2}}]^{\top}$;

for $t=N_{2}+1:N$ do take
$x_{t}=\operatorname*{arg\,max\,\,}_{x\in\mathcal{A}}x^{\top}\hat{\theta}$

2) RT algorithm. RT, shown in Algorithm 2, is also an ETC algorithm. Its key
feature is the utilization of $\hat{B}$. Thanks to $\hat{B}$, the exploration
phase of RT is just carried out in the $r$-dimensional subspace ${\rm
span}(\hat{B})$. Consequently, much fewer exploration rounds are required
($N_{2}=\lceil r\sqrt{N}\rceil$ rather than $\lceil d\sqrt{N}\rceil$). In the
exploration phase, $r$ linear independently actions in ${\rm span}(\hat{B})$
are repeatedly taken before the $N_{2}$ rounds are exhausted. Unlike RE
wherein $\hat{\theta}$ is directly constructed, RT first estimates $\alpha$ by
the least-square regression $\hat{\alpha}=(\hat{B}^{\top}X_{\rm rt}X_{\rm
rt}^{\top}\hat{B})^{-1}\hat{B}^{\top}X_{\rm rt}Y_{\rm rt}$ with $X_{\rm
rt}=[x_{1},x_{2},\dots,x_{N_{2}}]$ and $Y_{\rm
rt}=[y_{1},y_{2},\dots,y_{N_{2}}]^{\top}$, and then recovers $\theta$ by
$\hat{B}\hat{\alpha}$.

With a perfect estimate $\hat{B}=B$, RT can achieve a regret upper bounded by
$O(r\sqrt{N})$. This can be proven straightforwardly since the original model
can be rewritten into a $r$-dimensional one
$y_{t}=z_{t}^{\top}\alpha+\eta_{t}$ by letting $z_{t}=\hat{B}^{\top}x_{t}$.
Yet, constructing a perfect $\hat{B}$ is usually impossible given the noisy
environment. The next theorem provides an upper bound for the regret of RT
when there is some error between $\hat{B}$ and $B$.

######  Theorem III.3 (Upper Bound Given an Estimated Representation)

Assume that an estimate $\hat{B}$ of the true representation $B$ satisfies
$\|\hat{B}^{\top}B_{\perp}\|_{F}\leq\varepsilon$. If the agent plays the task
described by Eq. (2) for $N$ rounds using Algorithm 2 with $\hat{B}$, then the
regret satisfies
$\operatorname{\mathbb{E}}R_{N}=O(r\sqrt{N}+N\varepsilon^{2})$. $\triangle$

The upper bound in Theorem III.3 is less than the lower bound
$\Omega(d\sqrt{N})$ in Lemma III.1 if $\varepsilon<\sqrt{d}/N^{\frac{1}{4}}$.
This implies that the knowledge of an imperfect estimate of the representation
improves the performance as long as it is sufficiently accurate (i.e., small
$\|\hat{B}^{\top}B_{\perp}\|_{F}$).

Proof of Theorem III.3: Since $\theta=B\alpha$, then the model becomes
$y_{t}=x_{t}^{\top}B\alpha+\eta_{t}$. From Algorithm 2, it holds that
$\hat{\alpha}=(\hat{B}^{\top}X_{rt}X_{rt}^{\top}\hat{B})^{-1}\hat{B}^{\top}X_{rt}Y_{rt}.$
Without loss of generality, we assume $N_{2}$ is a multiple of $r$. Then, it
can be calculated that $X_{rt}X_{rt}^{\top}=\frac{N_{2}}{r}AA^{\top}$ with
$A=[a^{\prime}_{1},\dots,a^{\prime}_{r}]$, then we have
$\hat{\alpha}=\big{(}{N_{2}}\hat{B}^{\top}AA^{\top}\hat{B}/{r}\big{)}^{-1}\hat{B}^{\top}X_{rt}Y_{rt}.$
As $Y_{rt}=X_{rt}^{\top}B\alpha+\eta$ with
$\eta=[\eta_{1},\dots,\eta_{N_{2}}]^{\top}$, we have
$\hat{\alpha}=\big{(}{N_{2}}\hat{B}^{\top}AA^{\top}\hat{B}/{r}\big{)}^{-1}{N_{2}}\hat{B}^{\top}AA^{\top}B\alpha/{r}+\big{(}\frac{N_{2}}{r}\hat{B}^{\top}AA^{\top}\hat{B}\big{)}^{-1}\hat{B}^{\top}X_{rt}\eta.$
As $\hat{\theta}=\hat{B}\hat{\alpha}$ and $\theta=B\alpha$, it follows that

$\displaystyle\hat{B}\hat{\alpha}-B\alpha=$
$\displaystyle\underbrace{\hat{B}\big{(}{N_{2}}\hat{B}^{\top}AA^{\top}\hat{B}/{r}\big{)}^{-1}{N_{2}}\hat{B}^{\top}AA^{\top}B\alpha/r-B\alpha}_{s_{1}}$
$\displaystyle+\underbrace{\hat{B}\big{(}{N_{2}}\hat{B}^{\top}AA^{\top}\hat{B}/r\big{)}^{-1}\hat{B}^{\top}X\eta}_{s_{2}}.$

Then, it holds that
$\operatorname{\mathbb{E}}\left[\|\hat{\theta}(c)-\theta\|^{2}\right]\leq\operatorname{\mathbb{E}}\|s_{1}\|^{2}+\operatorname{\mathbb{E}}\|s_{2}\|^{2}$
since $\eta_{t}$ is an independent random variable with zero mean. It can be
derived (more details can be found in the extended version of this paper [29])
that $\operatorname{\mathbb{E}}\|s_{1}\|^{2}\leq
2c\phi_{\max}^{2}\varepsilon^{2}$ for some constant $c$ and
$\operatorname{\mathbb{E}}\|s_{2}\|^{2}\leq{r}/{\sqrt{N}}$. Combining
$\operatorname{\mathbb{E}}\|s_{1}\|^{2}$ and
$\operatorname{\mathbb{E}}\|s_{2}\|^{2}$, we have
$\operatorname{\mathbb{E}}\left[\|\hat{\theta}-\theta\|^{2}\right]\leq{r}/{\sqrt{N}}+2c\phi_{\max}^{2}\varepsilon^{2}$.

From [27], it follows that

$\displaystyle\operatorname{\mathbb{E}}[\max_{x\in\mathcal{A}}$ $\displaystyle
x^{\top}\theta-\max_{x\in\mathcal{A}}x^{\top}\hat{\theta}]$ $\displaystyle\leq
J\frac{\hat{r}}{\phi_{\min}\sqrt{N}}+2\frac{1}{\phi_{\min}}J\phi_{\max}^{2}(1+\mu)\varepsilon^{2}.$
(3)

For the commitment phase, there are $N-N_{2}$ steps. Thus, the overall regret
satisfies $\operatorname{\mathbb{E}}R_{N}\leq
N_{2}\phi_{\max}+(N-N_{2})\left(\max_{x\in\mathcal{A}}x^{\top}\theta-\operatorname{\mathbb{E}}\max_{x\in\mathcal{A}}x^{\top}\hat{\theta}\right)$.
Substituting Eq. (III-B) into the right-hand side we obtain
$\operatorname{\mathbb{E}}R_{N}\leq O(\hat{r}\sqrt{N}+N\varepsilon^{2})$,
which completes the proof. $\blacksquare$

3) SeqRepL algorithm. Let us now present the main algorithm in this
subsection, which performs sequential representation learning (SeqRepL). It
operates in a cyclic manner, alternating between RE and RT (see Algorithm 3).
In each cycle, there are two phases. In the RE phase of the $n$th cycle, $L$
tasks are played using RE. Then, the representation are estimated.
Specifically, let $\hat{P}=\sum\hat{\theta}_{i}\hat{\theta}_{i}^{\top}$, where
$\hat{\theta}_{i}$’s are the learned coefficients in all the previous $n$ RE
phases. Then, $\hat{B}$ is constructed by performing singular value
decomposition (SVD) to $\hat{P}$ in the following way:

$\displaystyle{\rm SVD:}\hskip 2.0pt\hat{P}=[U_{1},U_{2}]\Sigma V\hskip
12.0pt\longrightarrow\hskip 12.0pt\hat{B}=U_{1},$

where the columns of $U_{1}\in\mathbb{R}^{d\times r}$ are the singular vectors
that are associated with the $r$-largest singular values of $\hat{P}$. In the
RT phase, $nL$ tasks are played using RT with the estimated $\hat{B}$. Notice
that $L$ more tasks are played using RT in each cycle than the previous one.
This alternating scheme balances representation exploration and transfer well.

Algorithm 3 Sequential Representation Learning (SeqRepL)

Input: $\mathcal{S}_{\tau}=\\{\theta_{1},\dots,\theta_{\tau}\\}$, $L=c_{1}r$,
$\hat{P}=0_{d\times d}$ Initialize: $n=1$;

for each cycle $n$:

RE phase: play $L$ tasks in $\mathcal{S}_{\tau}$ using RE algorithm,
$\hat{P}=\hat{P}+\hat{\theta}_{i}\hat{\theta}_{i}^{\top}$,

$\hat{B}\leftarrow$ top $r$ singular vector of $\hat{P}$;

RT phase: play $nL$ tasks in $\mathcal{S}_{\tau}$ using RT algorithm with
latest $\hat{B}$;

update $n=n+1$.

Next, we make an assumption and provide an upper bound for SeqRepL.

###### Assumption III.4

For the task sequence $\mathcal{T}=\\{\theta_{1},\dots,\theta_{\tau}\\}$,
suppose that there exists $L=c_{1}r$ for some constant $c_{1}>0$ such that any
subsequence of length $L$ in $\mathcal{T}$ satisfies
$\sigma_{r}(W_{s}W_{s}^{\top})\geq\nu>0$ for any $s$, where
$W_{s}=[\theta_{s+1},\dots,\theta_{s+\ell}]$ and $\sigma_{r}(\cdot)$ denote
the $r$th largest singular value of a matrix. $\triangle$

This assumption states that the sequential tasks covers all the directions of
the $r$-dimensional subspace ${\rm span}(B)$, which ensures that $B$ can be
recovered in a sequential fashion.

######  Theorem III.5 (Upper Bound of SeqRepL)

Let the agent play a series of tasks
$\\{\theta_{1},\theta_{2},\dots,\theta_{\tau}\\}$ using SeqRepL in Algorithm
3, where $\tau>r^{2}$. Suppose that Assumption III.4 is satisfied, then the
regret, denoted by $R_{\tau N}$, satisfies $\operatorname{\mathbb{E}}R_{\tau
N}=\tilde{O}\left(d\sqrt{\tau rN}+\tau r\sqrt{N}\right).$ $\triangle$

Note that if one uses a standard algorithm, e.g., a UCB algorithm [25] or a
PEGE algorithm [27], to play the sequence of tasks without learning the
representation, the optimal regret would be $\Theta(\tau d\sqrt{N})$. This
bound is always larger than the two terms in our bound since $\tau>r^{2}$.
This indicates that our algorithm outperforms the standard algorithms that do
not learn the representations.

Proof of Theorem III.5: After the RE phase of $n$th cycle in the SeqRepL
algorithm, it can be derived (more details can be found in the extended
version of this paper [29]) that the estimate $\hat{B}$ and the true
representation $B$ satisfy
$\|\hat{B}^{\top}B_{\perp}\|_{F}=\tilde{O}\Big{(}\frac{d}{\nu}{\sqrt{\frac{1}{nLd\sqrt{N}}}}\Big{)}.$
The regret incurred in this phase of the $n$th cycle, denoted by $R_{\rm
RE}(n)$, satisfies $R_{\rm RE}=O(Ld\sqrt{N})$ Then, $nL$ tasks are played in
sequence utilizing the RT algorithm with input $\hat{B}$. It follows from
Lemma III.3 that the regret in the RT phase of the $n$th cycle, denoted as
$R_{\rm RT}(n)$, satisfies $\operatorname{\mathbb{E}}R_{\rm RT}(n)\lesssim
nLr\sqrt{N}+nLN\frac{d^{2}}{\nu^{2}}{\frac{1}{nLd\sqrt{N}}}=\tilde{O}(nLr\sqrt{N}+d\sqrt{N}).$
Observe that there are at most $\bar{L}=\lceil\sqrt{{2\tau}/{L}}\rceil$ cycles
in the sequence of length $\tau$ since
$L\bar{L}+L\bar{L}(\bar{L}+1)/2\geq\tau$. Summing up the regret in Phases 1
and 2 in every cycle, we obtain
$\operatorname{\mathbb{E}}R_{N\tau}\lesssim\bar{L}Ld\sqrt{N}+\sum_{m=1}^{\bar{L}}\left(nLr\sqrt{N}+d\sqrt{N}\right)\leq\bar{L}Ld\sqrt{N}+\tau
r\sqrt{N}+\bar{L}d\sqrt{N}.$ Since $L=c_{1}r$ for some constant $c_{1}$ and
$\bar{L}=\lceil\sqrt{{2\tau}/{L}}\rceil$, then
$\operatorname{\mathbb{E}}R_{\tau N}=\sum_{n=1}^{\bar{L}}R_{\rm RE}(n)+R_{\rm
RT}(n)=\tilde{O}\left(d\sqrt{\tau rN}+\tau r_{i}\sqrt{N}+d\sqrt{{\tau
N}/{r}}\right),$ which completes the proof. $\blacksquare$

###  III-C Representation learning with contextual changes

Finally, we are ready to address the problem that we set up in Section II,
i.e., representation learning in sequential tasks with changing contexts.

Algorithm 4 Outlier Detection (OD)

Input: $\hat{B}\in\mathbb{R}^{d\times r}$, $n_{\rm od}$, generate a random
orthonormal matrix $Q\in\mathbb{R}^{(d-r)\times n_{\rm od}}$, and let
$M=\hat{B}_{\perp}Q$.

for $t=1,\dots,n_{\rm od}$ do $x_{t}=\delta[M]_{t}\in\mathcal{A}$, collect
$y_{t}$ end for

if $Y_{n_{\rm od}}\notin\mathcal{C}_{n_{\rm od}}$ then outlier indicator
$\mathbb{I}_{\rm od}=1$ end if

Algorithm 5 Adaptive Representation Learning (AdaRepL)

Input: $k_{c}$ Initialize: $n_{c}=0$ (outlier counter), $\hat{B}=I_{d}$

for $\theta_{1},\theta_{2},\dots,\theta_{S}$ do:

invoke OD algorithm, return $\mathbb{I}_{\rm od}$

if $\mathbb{I}_{\rm od}=1$ do invoke RE algorithm,
$P=P+\hat{\theta}_{i}\theta_{i}^{\top}$, $n_{c}=n_{c}+1$

else $n_{c}=0$, invoke the cyclic SeqRepL

end if

if $n_{c}=k_{c}$ do restart SeqRepL end if

In the WCST, humans are able to realize of sorting rule changes quickly.
Inspired by that, we equip our algorithm with the ability to detect context
switches, which enables it to adapt to new environments.

As shown in Algorithm 4, the key idea is to take $n_{\rm od}$ probing actions
for every new task. These actions are randomly generated in the perpendicular
complement of ${\rm span}(\hat{B})$. Specifically, we generate a random
orthonormal matrix $Q\in\mathbb{R}^{(d-r)\times n_{\rm od}}$. The probing
actions are taken from the columns of the matrix $M=\delta\hat{B}_{\perp}Q$,
where $\delta>0$ ensures that the actions are within the action set
$\mathcal{A}$. If the current task $\theta$ satisfies $\theta=\hat{B}\alpha$
for some $\alpha$, it holds that $y_{t}=x_{t}^{\top}\theta+\eta_{t}=\eta_{t}$
since $Q^{\top}\hat{B}_{\perp}^{\top}\hat{B}\alpha=0$. Therefore, if the
received rewards considerably deviate from the level of noise, the new task is
an outlier to the current context (i.e., a task that does not lie in the
subspace ${\rm span}(B)$) with high probability.

Let $Y_{n_{\rm od}}=[y_{1},\dots,y_{n_{\rm rsd}}]^{\top}$ collect the rewards.
Also, we build a confidence interval for $Y_{n_{\rm od}}$, which is
$\mathcal{C}_{n_{\rm od}}=\left\\{Y_{\rm od}\in\mathbb{R}^{n_{\rm
od}}:\left|\|Y\|_{2}-\sqrt{n_{\rm od}}\right|\leq\xi_{\rm od}\right\\}$, where
$\xi_{\rm od}$ is the detection threshold chosen by the agent. If the observed
$Y_{\rm od}$ is beyond $\mathcal{C}_{n_{\rm od}}$, we decide that the new task
is an outlier.

The main algorithm in this paper, which we call Adaptive Representation
Learning algorithm (AdaRepL), is provided in Algorithm 5, which invokes both
SeqRepL and OD sub-algorithms. The former well balances representation
exploration and transfer in the sequential setting, and the latter enables the
algorithm to adapt to changing environments. To make our algorithm robust to
occasional outliers, we set a threshold $k_{c}$ so that the algorithm
considers that a context switch has occurred only when $k_{c}$ outliers have
been detected consecutively.

It is worth mentioning that with the aid of the OD algorithm, the agent can
detect context changes with high probability by properly selecting the
detection threshold $\xi_{\rm od}$ and the length of probing actions $n_{\rm
od}$. Within each context, the regret of AdaRepL has an upper bound presented
in Theorem III.5. Although context change detection incurs some regret, the
overall performance will still surpass the standard algorithms that are unable
to learn representations adaptively. We will verify this point in the next
section by revisiting the WCST.

##  IV Experimental Study of WCST

First, we provide more details on the tabular-Q learning and Deep-Q learning
algorithms in Fig. 1. We assume that the agent receives reward 1 if it takes
the classification action $x_{t}$ satisfies $x_{t}=\theta_{t}$, otherwise, it
receives reward 0.

For the tabular-Q learning, the problem is to construct the $4^{3}\times 4$ Q
table. This is because there are $4^{3}$ possible stimulus cards (4 colors, 4
numbers, 4 shapes) and each stimulus card can be taken as a state, and there
are 4 sorting actions.

For the Deep-Q learning, we formalize each input state by a 3-dimension vector
$\rm(shape,number,color)^{\top}\in\\{1,2,3,4\\}^{3}$. The result shown in Fig.
1 is based on a three-layer network with 3, 12, and 4 nodes in the input,
hidden, and output layers, respectively. We also considered deeper or wider
structures but obtained similar performances.

It can be observed from Fig. 1 that these two algorithms struggle in the WCST.
The reason is that a large number of samples (certainly more than $4^{4}$
samples) are needed to construct the Q table or train the network weights.
However, if the sorting rule changes much earlier than $4^{4}$ rounds, it is
impossible to find the optimal policy. Also, being unaware of the sorting rule
changes worsens the performance.

Next, we demonstrate how our proposed algorithm, which explore and exploit the
representation in the WCST and detect sorting rule changes, has a much better
performance.

Figure 3: Left: key steps to model WCST into a sequential decision-making
model with linear reward functions. Right: performance comparison between our
algorithm and standard RL algorithms in WCST. Sorting rules change every 20
rounds. Dotted circles indicate that our algorithm is able to adapt to new
contexts and learn new representations quickly.

To do that, we model the WCST into a sequential decision-making model.
Specifically, we use a matrix $A_{t}\in\mathbb{R}^{4\times 3}$ to describe the
stimulus card at round $t$. The first, second, and third columns of $A_{t}$
represent shape, number, and color, respectively, and they take values from
the set $\\{e_{1},e_{2},e_{3},e_{4}\\}$ with $e_{i}$ being the $i$th standard
basis of $\mathbb{R}^{4}$. In each column, $e_{i}$ indicates that this card
has the same shape/number/color as the $i$th card on table (see Fig. 3). For
example, the stimulus card (with two green circles) in Fig. 1 can be
represented by the matrix $A=[e_{1},e_{2},e_{3}]$ (see Fig. 3). Moreover, we
use a standard unit vector $B_{\sigma}$, which takes values from
$\\{b_{1},b_{2},b_{3}\\}$ with $b_{i}$ being the standard basis of
$\mathbb{R}^{3}$, to respectively describe the 3 sorting rules – shape,
number, and color. In addition, the action $x_{t}$ also takes value from the
set $\\{e_{1},e_{2},e_{3},e_{4}\\}$. The action $x_{t}=e_{i}$ means to sort
the stimulus card to the $i$th card on table.

Consequently, the WCST can be described by the sequential decision-making
model $y_{t}=x_{t}^{\top}\theta_{t}$ with $\theta_{t}=A_{t}B_{\sigma}$. Here
the unit vector $B_{\sigma}$ can be taken as the current representation since
the correct sorting action can always be computed by
$x_{t}^{*}=A_{t}B_{\sigma}$ no matter what card the agent sees. For instance,
suppose the rule is number (i.e., $B_{\sigma}=b_{2}$), if the agent sees the
stimulus card with two green circles, i.e., $A=[e_{1},e_{2},e_{3}]$, then
correct sort is the second card on table since it can be computed that
$x^{*}_{t}=A_{t}B_{\sigma}=[0,1,0,0]^{\top}$.

The problem then reduces to learn the underlying representation $B_{\sigma}$,
a task that is much easier than constructing the Q table or training the
weights in a Deep-Q network. Remarkably, one does not even need to learn
individual $\theta_{t}$ to construct $B_{\sigma}$. Instead, $B_{\sigma}$ can
be recovered by
$B_{\sigma}=(\sum\nolimits_{t=1}^{k}A_{t}^{\top}x_{t}x_{t}^{\top}A_{t})^{-1}\sum\nolimits_{t=1}^{k}A_{t}^{\top}x_{t}y_{t}$
immediately after $\sum_{t=1}^{k}A_{t}^{\top}x_{t}x_{t}^{\top}A_{t}$ becomes
invertible. This indicates that our idea in this paper can apply to more
general situations.

It can be observed in Fig. 3 that our algorithm significantly outperforms the
other two, which demonstrates the power of being able to abstract compact
representations and adapt to new environments.

##  V Concluding Remarks

In this paper, we have studied representation learning for decision-making in
environments with contextual changes. To describe such context-changing
environments, we employ a decision-making model in which tasks are drawn from
distinct sets sequentially. Inspired by strategies taken by humans, we propose
an online algorithm that is able to learn and transfer representations under
the sequential setting and has the ability to adapt to changing contexts. Some
analytical results have been obtained, showing that our algorithm outperforms
existing ones that are not able to learn representations. We also apply our
algorithm to a real-world task (WCST) and verify the benefits of the ability
to learn representations flexibly and adaptively. We are interested in
studying representation learning in more general RL frameworks such as
Markovian or non-Markovian processes.

## References

  * [1] A. Radulescu, Y. S. Shin, and Y. Niv, “Human representation learning,” _Annual Review of Neuroscience_ , vol. 44, no. 1, pp. 253–273, 2021.
  * [2] N. T. Franklin and M. J. Frank, “Generalizing to generalize: humans flexibly switch between compositional and conjunctive structures during reinforcement learning,” _PLoS Computational Biology_ , vol. 16, no. 4, p. e1007720, 2020\.
  * [3] B. R. Buchsbaum, S. Greer, W.-L. Chang, and K. F. Berman, “Meta-analysis of neuroimaging studies of the wisconsin card-sorting task and component processes,” _Human Brain Mapping_ , vol. 25, no. 1, pp. 35–45, 2005.
  * [4] C.-H. Lie, K. Specht, J. C. Marshall, and G. R. Fink, “Using fMRI to decompose the neural processes underlying the Wisconsin Card Sorting Test,” _Neuroimage_ , vol. 30, no. 3, pp. 1038–1049, 2006.
  * [5] P. Auer, “Using confidence bounds for exploitation-exploration trade-offs,” _Journal of Machine Learning Research_ , vol. 3, no. Nov, pp. 397–422, 2002\.
  * [6] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári, “Improved algorithms for linear stochastic bandits,” in _Advances in Neural Information Processing Systems_ , vol. 11, 2011, pp. 2312–2320.
  * [7] Y. Russac, C. Vernade, and O. Cappé, “Weighted linear bandits for non-stationary environments,” in _Advances in Neural Information Processing Systems_ , vol. 32. Curran Associates, Inc., 2019.
  * [8] L. Wei and V. Srivastava, “Nonstationary stochastic multiarmed bandits: UCB policies and minimax regret,” _arXiv preprint arXiv:2101.08980_ , 2021.
  * [9] T. Gafni and K. Cohen, “Learning in restless multiarmed bandits via adaptive arm sequencing rules,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 10, pp. 5029–5036, 2021.
  * [10] P. Reverdy, V. Srivastava, and N. E. Leonard, “Satisficing in multi-armed bandit problems,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 8, pp. 3788–3803, 2016.
  * [11] M. Malekipirbazari and O. Cavus, “Risk-averse allocation indices for multi-armed bandit problem,” _IEEE Transactions on Automatic Control_ , 2021, in Press.
  * [12] L. Wei and V. Srivastava, “Minimax policy for heavy-tailed bandits,” _IEEE Control Systems Letters_ , vol. 5, no. 4, pp. 1423–1428, 2020.
  * [13] M. K. Hanawal and S. Darak, “Multi-player bandits: A trekking approach,” _IEEE Transactions on Automatic Control_ , 2021, in Press.
  * [14] D. Kalathil, N. Nayyar, and R. Jain, “Decentralized learning for multiplayer multiarmed bandits,” _IEEE Transactions on Information Theory_ , vol. 60, no. 4, pp. 2331–2345, 2014.
  * [15] P. Landgren, V. Srivastava, and N. E. Leonard, “Distributed cooperative decision making in multi-agent multi-armed bandits,” _Automatica_ , vol. 125, p. 109445, 2021.
  * [16] U. Madhushani and N. E. Leonard, “A dynamic observation strategy for multi-agent multi-armed bandit problem,” in _2020 European Control Conf._ , 2020, pp. 1677–1682.
  * [17] J. Zhu and J. Liu, “A distributed algorithm for multi-armed bandit with homogeneous rewards over directed graphs,” in _American Control Conference_ , 2021, pp. 3038–3043.
  * [18] Y. Bengio, A. Courville, and P. Vincent, “Representation learning: A review and new perspectives,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 35, no. 8, pp. 1798–1828, 2013.
  * [19] N. Tripuraneni, C. Jin, and M. I. Jordan, “Provable meta-learning of linear representations,” _arXiv preprint arXiv:2002.11684_ , 2020.
  * [20] S. Lale, K. Azizzadenesheli, A. Anandkumar, and B. Hassibi, “Stochastic linear bandits with hidden low rank structure,” _arXiv preprint arXiv:1901.09490_ , 2019.
  * [21] K.-S. Jun, R. Willett, S. Wright, and R. Nowak, “Bilinear bandits with low-rank structure,” in _International Conference on Machine Learning_ , 2019, pp. 3163–3172.
  * [22] Y. Lu, A. Meisami, and A. Tewari, “Low-rank generalized linear bandit problems,” _arXiv preprint arXiv:2006.02948_ , 2020.
  * [23] J. Yang, W. Hu, J. D. Lee, and S. S. Du, “Impact of representation learning in linear bandits,” in _International Conference on Learning Representations_ , 2021.
  * [24] M. G. Azar, A. Lazaric, and E. Brunskill, “Sequential transfer in multi-armed bandit with finite set of models,” in _Advances in Neural Information Processing Systems_ , 2013, p. 2220–2228.
  * [25] V. Dani, T. P. Hayes, and S. M. Kakade, “Stochastic linear optimization under bandit feedback,” 2008.
  * [26] J. Hu, X. Chen, C. Jin, L. Li, and L. Wang, “Near-optimal representation learning for linear bandits and linear RL,” _arXiv preprint arXiv:2102.04132_ , 2021.
  * [27] P. Rusmevichientong and J. N. Tsitsiklis, “Linearly parameterized bandits,” _Mathematics of Operations Research_ , vol. 35, no. 2, pp. 395–411, 2010\.
  * [28] Y. Li, Y. Wang, X. Chen, and Y. Zhou, “Tight regret bounds for infinite-armed linear contextual bandits,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2021, pp. 370–378.
  * [29] Y. Qin, T. Menara, S. Oymak, S. Ching, and F. Pasqualetti, “Non-stationary representation learning in sequential linear bandits,” _arXiv preprint arXiv:2201.04805_ , 2022.