4G

    fourth generation
5G

    fifth generation
AoA

    angle of arrival
AoD

    angle of departure
AP

    access point
BCRLB

    Bayesian CRLB
BS

    base stations
BPP

    binomial point process
BP

    broadcast probing
CDF

    cumulative density function
CF

    closed-form
CRLB

    Cramer-Rao lower bound
ECDF

    empirical cumulative distribution function
EI

    Exponential Integral
eMBB

    enhanced mobile broadband
FIM

    Fisher Information Matrix
GoF

    goodness-of-fit
GPS

    global positioning system
GE

    group exploration
GNSS

    global navigation satellite system
HetNets

    heterogeneous networks
IoT

    internet of things
IIoT

    industrial internet of things
LOS

    line of sight
MAB

    multi-armed bandit
MBS

    macro base station
MEC

    mobile-edge computing
mIoT

    massive internet of things
MIMO

    multiple input multiple output
mm-wave

    millimeter wave
mMTC

    massive machine-type communications
MS

    mobile station
MVUE

    minimum-variance unbiased estimator
NLOS

    non line-of-sight
OFDM

    orthogonal frequency division multiplexing
PDF

    probability density function
PGF

    probability generating functional
PLCP

    Poisson line Cox process
PLT

    Poisson line tessellation
PLP

    Poisson line process
PPP

    Poisson point process
PV

    Poisson-Voronoi
QoS

    quality of service
RAT

    radio access technique
RL

    reinforcement-learning
RSSI

    received signal-strength indicator
BS

    base station
SINR

    signal to interference plus noise ratio
SNR

    signal to noise ratio
SWIPT

    simultaneous wireless information and power transfer
TS

    Thompson Sampling
TS-CD

    TS with change-detection
KS

    Kolmogorov-Smirnov
UCB

    upper confidence bound
ULA

    uniform linear array
UE

    user equipment
URLLC

    ultra-reliable low-latency communications
V2V

    vehicle-to-vehicle
wpt

    wireless power transfer

# Actively Tracking the Optimal Arm in Non-Stationary Environments with
Mandatory Probing

Gourab Ghatak  Member, IEEE The author is with the Department of Electrical
Engineering at IIT Delhi, India 110016. Email<EMAIL_ADDRESS>
###### Abstract

We study a novel multi-armed bandit (MAB) setting which mandates the agent to
probe all the arms periodically in a non-stationary environment. In
particular, we develop TS-GE that balances the regret guarantees of classical
Thompson sampling (TS) with the broadcast probing (BP) of all the arms
simultaneously in order to actively detect a change in the reward
distributions. Once a system-level change is detected, the changed arm is
identified by an optional subroutine called group exploration (GE) which
scales as $\log_{2}(K)$ for a $K-$armed bandit setting. We characterize the
probability of missed detection and the probability of false-alarm in terms of
the environment parameters. The latency of change-detection is upper bounded
by $\sqrt{T}$ while within a period of $\sqrt{T}$, all the arms are probed at
least once. We highlight the conditions in which the regret guarantee of TS-GE
outperforms that of the state-of-the-art algorithms, in particular, ADSWITCH
and M-UCB. Furthermore, unlike the existing bandit algorithms, TS-GE can be
deployed for applications such as timely status updates, critical control, and
wireless energy transfer, which are essential features of next-generation
wireless communication networks. We demonstrate the efficacy of TS-GE by
employing it in a n industrial internet-of-things (IIoT) network designed for
simultaneous wireless information and power transfer (SWIPT).

Most practical environments that reinforcement learning algorithms target are
non-stationary in nature. In case the number of choices is large, detecting
non-stationarity, especially in the sub-optimal arms is non-trivial, and hence
the state-of-the-art algorithms incur a regret that scales as a product of
$\sqrt{K}$ and $\sqrt{T\log T}$ for a $K$-armed bandit setting. This article
develops a novel bandit algorithm that not only detects the changed arm in
$\mathcal{O}\left(\log K\right)$ but also it ensures periodic probing of all
the arms in the environment. In particular, unlike existing algorithms, our
proposal ensures an upper bound of $\sqrt{T}$ for the age of probing each arm.
This feature makes it an attractive solution for applications where not only
the current best-arm needs to be identified but also all the arms need to be
interacted with periodically. The proposed algorithm will find applications in
wireless communications (e.g., simultaneous wireless information and power
transfer), portfolio optimization (e.g., hedging across multiple instruments),
and computational advertisement (e.g., building user profiles while maximizing
revenue). Multi-armed bandits, Thompson sampling, Non-stationarity, Online
learning.

##  1 Introduction

Sequential decision making problems in reinforcement-learning (RL) are
popularly formulated using the multi-armed bandit (MAB) framework, wherein, an
agent (or player) selects one or multiple options (or arms) out of a set of
arms at each time slot [1, 2, 3, 4, 5]. The player performs such an action-
selection based on the current estimate or belief of the expected reward of
the arms. Each time the player selects an arm or a group of arms, it receives
a reward characterized by the reward distribution of the played arm/arms. The
player updates its belief of the played arms based on the reward received. In
case the reward distribution of the arms is stationary, several algorithms
have been shown to perform optimally [6]. On the contrary, most real-world
applications such as internet of things (IoT) networks [7], wireless
communications [8], computational advertisement [9], and portfolio
optimization [10] are better characterized by non-stationary rewards. However,
non-stationarity in reward distributions are notoriously difficult to handle
analytically.

To address this, researchers either i) construct passively-adaptive algorithms
that are change-point agnostic and work by discounting the impact of past
rewards gradually or ii) derive frameworks to actively detect the changes in
the environment. Among the actively-adaptive algorithms, the state-of-the-art
solutions, e.g., ADSWITCH by Auer et al. [11] provide a regret guarantee of
$\mathcal{O}\left(\sqrt{KN_{C}T\log T}\right)$ for a $K$-armed bandit setting
experiencing $N_{C}$ changes in a time-horizon $T$. Recently, researchers have
also explored predictive sampling frameworks for tackling non-stationarity
[12].

In contrast to this we propose an algorithm based on grouped probing of the
arms that identifies the arm that has undergone a change in its mean. We
investigate the conditions under which the proposed algorithm achieves
superior regret guarantees than ADSWITCH.

###  1.1 Related Work

Actively-adaptive algorithms have been experimentally shown to perform better
than the passively-adaptive ones [13]. In particular, ADAPT-EVE, detects
abrupt changes via the Page-Hinkley statistical test (PHT) [14]. However,
their evaluation is empirical without any regret guarantees. Similarly,
another work [10] employs the Kolmogorov-Smirnov statistical test to detect a
change in distribution of the arms. Interestingly, tests such as the PHT has
been applied in different contexts in bandit frameworks, e.g., to adapt the
window length of SW-UCL [15]. The results by [16, 17], and by Cao et al. [18]
detect a change in the empirical means of the rewards of the arms by assuming
a constant number of changes within an interval. While the algorithm in [18],
called M-UCB achieves a regret bound of $\mathcal{O}(\sqrt{KN_{C}T\log T})$,
the work by Yu et al. leverages side-information to achieve a regret of
$\mathcal{O}(K\log T)$. However, the proposed algorithms in both these works
assume a prior knowledge of either the number of changes or the change
frequency. On these lines, recently, Auer et al. [11] have proposed ADSWITCH
based on the mean-estimation based checks for all the arms. Remarkably, the
authors show regret guarantees of the order of $\mathcal{O}(\sqrt{KN_{C}T\log
T})$ for ADSWITCH without any pre-condition on the number of changes $N_{C}$
for the $K$-arm bandit problem. If the number of changes $N_{C}$ is known, a
safeguard against a change in an inferior arm $a_{i}$ can be achieved by
sampling it in inverse proportion of its sub-optimality gap $\Delta_{i}$. This
achieves a regret of $\mathcal{O}(\sqrt{KLT})$. However, if the number of
changes is not known, setting the sampling rate is challenging and if the
number of changes is greater than $\sqrt{T}$, several algorithms experience
linear regret. In order to avoid this, the main idea in ADSWITCH is to draw
consecutive samples from arms, thereby incurring a regret that scales as
$\mathcal{O}\left(\sqrt{K}\right)$ in the worst-case. Nevertheless, since both
M-UCB and ADSWITCH provide the same regret guarantees, we choose them as the
competitor algorithms for our proposal.

###  1.2 Motivation and Contribution

Unlike M-UCB but similar to ADSWITCH, we consider a framework where the number
of changes $N_{C}$ is not known a-priori but to be fewer than $\sqrt{T}$.
Furthermore, we target an additional requirement - the agent algorithm should
guarantee that the age between two consecutive plays of each arm is bounded.
Although the issue of age has previously been addressed in some works (e.g.,
see [19]), the solutions cater to stationary environments. On the contrary, in
this work, under an assumption of the hard-core distance between two
consecutive changes, we propose TS-GE which outperforms ADSWITCH and M-UCB
under several regimes of $K$ and the time-horizon, $T$, while simultaneously
satisfying the mandatory probing requirement. The major innovation in this
paper is two-fold - i) by allowing simultaneous probing of multiple arms in a
coded manner, we reduce the scaling of changed-arm identification form
$\mathcal{O}\left(K\right)$ to $\mathcal{O}\left(\log_{2}(K)\right)$, and ii)
by design, TS-GE guarantees that the last sample of each arm is not older than
$\sqrt{T}$. Overall, the main contributions of this paper are:

  * •

We develop and characterize TS-GE, tuned for non-stationary environments with
unknown number of change-points. The additional design guarantee of TS-GE is
the periodic mandatory probing of all the arms. Although this is relevant for
several applications, to the best of our knowledge, this requirement has not
been treated previously in literature. By balancing the regret guarantees of
stationary Thompson sampling with grouped probing of all the arms, TS-GE
ensures an upper bound of $\sqrt{T}$ in the sampling age of each arm.

  * •

We propose a coded grouping of the arms based on the arm indices and
consequently, derive the probability of missed detection of change and the
probability of false alarm and highlight the conditions to limit these
probabilities. Based on this, we show that TS-GE achieves sub-linear regret,
$\mathcal{O}\left(K\log T+\sqrt{T}\left[\max\\{N_{C}\left(1+\log
K\right),T^{\frac{2}{5}}\\}\right]\right)$. We compare this bound with the
best known bound of $\mathcal{O}(\sqrt{KN_{C}T\log T})$ and discuss the
conditions under which the bound of TS-GE outperforms the latter.

  * •

Finally, as a case-study, we consider an industrial internet of things (IIoT)
network where a central controller is required to sustain simultaneous
wireless information and power transfer (SWIPT) services to the IoT devices.
The different phases of TS-GE are mapped to the data-transfer and energy-
transfer operations of the network. We demonstrate the performance of TS-GE
with respect to the statistical upper-bound derived using stochastic geometry
tools. Contrary to our proposal, in other algorithms such as M-UCB the exists
non-zero probability that the IoT devices do not receive any energy transfer
and hence our proposal will find applications that constrain sample age.

The rest of the paper is organized as follows. In Section II we describe the
system model and the proposed TS-GE algorithm. The regret analysis is
presented in Section III. We present a discussion on the regret bound in
Section IV and demonstrate the performance of TS-GE in a case-study in Section
V and compare it with statistical bounds. Finally the paper concludes in
Section VI.

##  2 TS-GE: Algorithm Description and Features

Consider a $K$-arm bandit setting with arms $\\{a_{i}\\}\in\mathcal{K}$, where
$i=1,2,\ldots,K$. For the discussion in this paper, let us assume that
$K=2^{d}$. It may be noted that in case the number of arms is not a power of
2, the same can be transformed into one by adding dummy arms which are sub-
optimal with a probability of 1 (e.g., arms with a constant reward of
$-\infty$). The reward $R_{a_{i}}(t)$ of an arm $a_{i}$ at time $t$ is assumed
to be a Gaussian distributed random variable with mean $\mu_{i}(t)$ and
variance $\sigma^{2}$. Thus, the variance of all the arms is constant and is
the same for all arms111This assumption is simply due to the ease of notations
and the derivation of the regret bounds. The algorithm can be executed with
this assumption does not hold. However, the regret analysis for such a case is
much more involved and will be investigated in a future work., however, the
mean is a function of time.

######  Assumption 1.

We assume that at all times: $R_{a_{i}}(t)\leq R_{max},\quad\forall
i=1,2,\ldots,K.$

In other words, the reward of all the arms is bounded above. Such an
assumption is valid for most practical wireless applications, e.g., upper
bound on received power or data-rate. Additionally, we assume a success or
failure event associated to each $R_{a_{i}}(t)$ which are generated according
to Bernoulli i.i.d. observations. Corresponding to each reward, the agent
observes a success event with a probability:

$\displaystyle R_{\pi}(t)=\frac{R_{a_{i}}(t)}{r_{max}}.$

For example, in wireless communication applications, this corresponds to a
success or failure in transmission associated with a data-rate of
$R_{a_{i}}(t)$. The agent has access to both $R_{a_{i}}(t)$ and $R_{\pi}(t)$.
Accordingly, the Thompson Sampling (TS) phase of our algorithm works with Beta
priors with the sequence of $R_{\pi}(t)$. Furthermore, we assume that at any
time-slot, multiple arms can be played by the agent. However, in that case,
the agent observes a weighted average of the rewards of the pulled arms. This
is formally mentioned below.

######  Assumption 2.

In case at any time-slot the agent pulls multiple (say $n$) arms,
$\mathcal{S}=\\{a_{k}\\}\subset\mathcal{K}$, then the reward observed by the
player is:

$\displaystyle R(t)=\frac{1}{n}\sum_{a_{k}\in\mathcal{S}}R_{a_{k}}$

Note that the player does not have access to the individual arm rewards of the
set of arms it has played. At this stage, we note that such an assumption is
not present in [11]. However, in several applications this is feasible - e.g.,
in wireless communications this may correspond to distributing the total
transmit power among the available channels, in portfolio optimization this
may correspond to distributing the total capital among different options.

###  2.1 Non-stationarity model

The player interacts with the bandit framework in a sequence of $N_{l}$
episodes, denoted by $E_{i}$, $i=1,2,\ldots,N_{l}$, each of length $T_{l}$.
Consequently, the total time-horizon $T$ can be expressed as $T=N_{l}T_{l}$.

######  Condition 1.

The framework mandates that each arm be probed (either individually or in a
group) at least once in each episode.

We assume a piece-wise stationary environment in which changes in the reward
distribution occur at time slots called change points, denoted by $T_{C_{j}}$,
$j=1,2,\ldots$, where each $T_{C_{j}}\in[T]$. At each change point, exactly
one of the arms $a_{i}$, uniformly selected from $\mathcal{K}$ experiences a
change (increase or decrease) in its mean by an unknown amount
$\Delta_{i}^{C}$.

######  Assumption 3.

We assume $\Delta_{C}^{i}$ to be bounded as: $\Delta_{i}^{C}\geq 2\sigma.$

Furthermore, we assume that during each episode, at most one change point
occurs with a probability $p_{C}$ and the total number of changes is $N_{C}$
within $T$, which is unknown to the player. In particular, during each time
slot of an episode, the environment samples a Bernoulli random variable $C$
with success probability $p_{b}$. In case of a success, the change occurs in
that slot, while in case of a failure, the bandit framework does not change.
Once a change occurs in an episode, the change framework is paused until the
next episode. Thus,

$\displaystyle\mathbb{P}\left(\text{Episode }E_{i}\text{ experiences $c_{i}$
changes}\right)$ $\displaystyle=\begin{cases}p_{C};&c_{i}=1,\\\
1-p_{C};&c_{i}=0,\\\ 0;&c_{i}>1.\end{cases}$

where, $p_{C}=\sum_{k=1}^{T_{l}}(1-p_{b})^{k-1}p_{b}$.

######  Assumption 4.

For a time horizon of $T$, we assume that the probability of change in each
slot $p_{b}$ is lower bounded as:

$\displaystyle p_{b}\geq
1-\left(\frac{1}{T}\right)^{\frac{1}{\sqrt{T}-T^{\frac{2}{5}}}}.$ (1)

Since the right hand side of the above is a decreasing function, for large
values of $T$, the above is a fairly mild assumption.

The challenge for the player is to quickly identify changes that any arm has
undergone and adapt its corresponding parameters. For benchmarking the
performance of a candidate player policy, at a given time slot, a policy $\pi$
competes against a policy class which selects the arm with the maximum
expected reward at that time slot. Thus, any policy $\pi$ that intends to
balance between the exploration-exploitation trade-off of the bandit framework
experiences a regret given by:

$\displaystyle\mathcal{R}(T)=\sum_{t=1}^{T}\max_{i}\mu_{i}(t)-\mathbb{E}\left[\mu_{\pi}(t)\right],$
(2)

where $\mu_{\pi}(t)$ is the mean of the arm $a_{\pi}(t)$ picked by the policy
$\pi$ at time $t$. It can be noted here that unlike stationary environments,
the identity of the best arm $a_{j}$, where,
$j=\operatorname*{arg\,max}_{i}\mu_{i}(t)$ is not fixed and may change with at
each change point.

The key features of our proposed algorithm TS-GE are i) actively detecting the
change in the bandit framework, ii) identifying the arm which has undergone a
change, and iii) modify its probability of getting selected in the further
rounds based on the amount of change. The TS-GE algorithm consists of an
initialization phase called explore-then-commit, ETC, followed by two
alternating phases: classical TS phase followed by a broadcast probing (BP)
phase to determine a change in the system. In case a change is detected in the
BP phase, the arm which has undergone a change is identified using an optional
sub-routine called group exploration (GE). Thus, the GE phase is only
triggered if a change is detected in the BP phase. The overall algorithm is
illustrated in Fig. LABEL:fig:Illustration and presented in Algorithm 1. Each
$E_{i}$ consists of one TS phase, one BP phase, and (optionally) one GE phase.
Next let us elaborate on the constituent phases of TE-GE.

###  2.2 Initialization: ETC for TS-GE

For initialization, the player performs a ETC for TS-GE, wherein each arm is
played an $n_{ETC}$ number of times and consequently, their mean $\mu_{i}$ is
estimated to be $\hat{\mu}_{i}$.

######  Definition 1.

An arm $a_{i}$ is defined to be well-localized if the empirical estimate
$\hat{\mu}_{i}$ of its mean $\mu_{i}$ is bounded as:

$\displaystyle|\hat{\mu}_{i}(t)-\mu_{i}(t)|\leq\delta.$ (3)

######  Lemma 1.

In the stationary regime, in order for the arm $a_{i}$ to be well-localized
with a probability $1-p_{L}$, the arm needs to have been played at least
$n_{ETC}$ times, where:

$\displaystyle n_{ETC}=\frac{1}{2\delta^{2}}\ln\frac{1}{p_{L}}$

###### Proof.

The proof follows from Hoeffding’s inequality. ∎

Thus, the ETC phase lasts for at least
$T_{ETC}=Kn_{ETC}=\frac{K}{2\delta^{2}}\ln\frac{1}{p_{L}}$ rounds. Naturally,
in order to restrict $p_{L}$ to $\mathcal{O}(\frac{1}{T})$, $n_{ETC}$ needs to
be $\mathcal{O}(\ln T)$.

###  2.3 Alternating TS and BP phases

Each episode consists of a TS phase, a BP phase, and an optional GE phase. Let
us set $T_{l}=\sqrt{T}$. In the TS phase, the player performs the action
selection of the choices according to the TS algorithm for $T_{TS}$ slots as
given in [20]. We set $T_{TS}=\sqrt{T}-T^{\frac{2}{5}}$. Each arm $a_{i}$ is
characterized by its TS parameters $\alpha_{i}$ and $\beta_{i}$, all of which
are initially set to unity222Note that the TS parameters can be initialized
according to the observed rewards in the ETC phase. However, in order to
safeguard against changes in the ETC phase, we begin the TS phase with fresh
parameters.. After each play of an arm $a_{i}$, its estimated mean
$\hat{\mu}_{i}$ is updated. Let $a_{i}$ be played at time slots
$\\{t_{i}\\}\in[T]$ and the number of times it is played is $n_{i}(t)$ until
(and including) the time-slot $t$, then:

$\displaystyle\hat{\mu}_{i}(t)=\frac{1}{n_{i}(t)}\sum_{t\in
t_{i}}R_{a_{i}}(t)$ (4)

Additionally, the TS parameters for the played arm $a_{i}$, i.e., $\alpha_{i}$
and $\beta_{i}$ are updated as per a Bernoulli trial with a success
probability $R_{\pi}(t),\forall t\in\\{t_{i}\\}$ each time $a_{i}$ is played.
Here $R_{\pi}(t)$ is the normalized version of the reward obtained by playing
the arm $a_{i}$ as shown in step 8 of Algorithm 1.

Each TS phase is followed by the BP phase for $T_{BP}=T^{\frac{2}{5}}$ time-
slots, where the player samples all the arms simultaneously for $T_{BP}$
rounds. During this phase, the reward observed by the player is the average of
the rewards from all the arms as mentioned in Assumption 2. The reward in the
BP phase is then compared with the average of the estimates of all the arms to
detect whether an arm of the framework has changed its mean. Recall that as
per Assumption 2, during the BP phase of the $m$-th episode, the player
receives the following reward for each play:

$\displaystyle R_{BP}(t)=$
$\displaystyle\frac{1}{K}\sum_{a_{i}\in\mathcal{K}}R_{i}(t)\sim\mathcal{N}\left(\frac{1}{K}\sum_{a_{i}\in\mathcal{K}}\mu_{i}(t),\frac{\sigma^{2}}{K}\right)$
$\displaystyle\forall(m-1)T_{l}+T_{TS}<t\leq(m-1)T_{l}+T_{TS}+T_{BP}$

At the end of the $m$-th BP phase, a change is detected if:

$\displaystyle\Big{|}\frac{1}{K}$
$\displaystyle\sum_{a_{i}\in\mathcal{K}}\hat{\mu}_{i}((m-1)T_{l}+T_{TS})-$
$\displaystyle\frac{1}{T_{BP}}\sum_{t=(m-1)T_{l}+T_{TS}+1}^{(m-1)T_{l}+T_{TS}+T_{BP}}R_{BP}(t)\Big{|}\geq
4\delta$ (5)

Here the first term is the average of the estimated means of all the arms at
the end of the $m$-th TS phase, while the second term represents the same
evaluated during the $m$-th BP phase. In case the change does not occur or
goes undetected, the algorithm continues with the next TS phase. However, in
case a change is detected or a false-alarm is generated, the algorithm moves
on to the GE sub-routine as described below.

###  2.4 Policy after change detection

If a change is detected in the BP phase, the GE phase begins for the
identification of the changed arm. The key step in this phase is the creation
of $d$ sets $B_{k}\subset\mathcal{K},k=1,2,\ldots,d$, called super arms as
shown in Algorithm 2. Recall that $d$ is a number such that $d=\log_{2}(K)$.
It may be noted that an optimal grouping of arms may be derived that considers
the fact that the arms that have been played a fewer number of times have a
larger error variance of its mean estimate. However, such a study is out of
scope for the current text and will be treated in a future work. The $i$-th
arm, where $i=1,2,\ldots,K$ is added to a super arm $B_{k}$ if and only if the
binary representation of $i$ has a ”1” in the $k$-th place. In other words,
$a_{i}$ is added to $B_{k}$ if:

$\displaystyle\texttt{bin2dec}\left(\texttt{dec2bin}(i)\;\texttt{ AND
}\;\texttt{onehot}(k)\right)\neq 0$

where $\texttt{bin2dec}()$ and $\texttt{dec2bin}()$ are respectively operators
that convert binary numbers to decimals and decimal numbers to binary.
Additionally, $\texttt{onehot}(k)$ is a binary number with all zeros except 1
at the $k$-th binary position. AND is the bit-wise AND operator. In the GE
phase, each super arm is played $n_{ge}$ times and the player obtains a reward
which is the average of rewards of all the arms that belong to $B_{k}$ as per
Assumption 2, i.e., each time the super arm $B_{k}$ is played, the player gets
a reward that is sampled from the distribution:

$\displaystyle R_{B_{k}}\sim\mathcal{N}\left(\frac{1}{|B_{k}|}\sum_{i\in
B_{k}}\mu_{i},\frac{\sigma^{2}}{|B_{k}|}\right)$

Let the mean reward of the super arm $B_{k}$ be denoted by $\mu_{B_{k}}$.
Before the beginning of each GE phase, $\mu_{B_{k}}$ is estimated using the
individual mean estimates. As an example, let a change be detected after the
$m$-th BP phase. Then, the estimate of the mean reward of the super arm
$B_{k}$ is:

$\displaystyle\hat{\mu}_{B_{k}}(m(T_{TS}+T_{BP}))=\frac{1}{|B_{k}|}\sum_{a_{i}\in
B_{k}}\hat{\mu}_{i}(m(T_{TS}+T_{BP}))$ (6)

Then, the arm with the changed mean is the one that belongs to the all super
arms in which a change of mean is detected. In other words, a change in arm
$a_{j}$ is detected if:

$\displaystyle
a_{j}\in\bigcap\limits_{k=1}^{d}B_{k}:|\hat{\mu}_{B_{k}}(m(T_{TS}+T_{BP})-$
$\displaystyle\frac{1}{n_{ge}|B_{k}|}\sum_{j=1}^{n_{ge}}R_{B_{k}}(m(T_{TS}+T_{BP}+(k-1)n_{ge}+j)|\geq
2\delta.$ (7)

Once the change is detected and the arm is identified, the corresponding mean
of $a_{j}$ is updated as:

$\displaystyle\hat{\mu}_{j}=\sum_{k:a_{j}\in
B_{k}}\hat{\mu}_{B_{k}}-\sum_{k:a_{j}\in B_{k}}\sum_{a_{i}\in B_{k}:i\neq
j}\hat{\mu}_{i}$ (8)

Then the TS parameters of the arm is updated. In particular, we set the
parameters of $a_{j}$ to be same as the arm that has an estimated mean closest
ot $a_{j}$ as:

$\displaystyle\alpha_{j}=\alpha_{k},\quad\beta_{j}=\beta_{k}$ where
$\displaystyle k=\operatorname*{arg\,min}_{i\neq
j}|\hat{\mu}_{i}-\hat{\mu}_{j}|$

In the next section we characterize the probability with which TS-GE misses
detection a change or raises a false alarm in case of no change. This
eventually leads to the regret.

Algorithm 1 TS-GE

1:Parameters:

2:Initialization: $\alpha_{k}=\beta_{k}=1$, $\forall k=1,\ldots K$.

3: Thompson Sampling Phase:

4:for $e_{i}=E_{1},\ldots,E_{N_{l}}$ do

5: for $t=1,\ldots,T_{N}$ do

6: $\theta_{i}\sim\text{Beta}\left(\alpha_{i},\beta_{i}\right)$.
$\backslash\backslash$ Sample the Beta prior.

7: $a_{j}\leftarrow a_{i}|\theta_{j}=\max(\theta_{i})$ $\backslash\backslash$
Select the best arm.

8: $R_{\texttt{TS-GE}}(t)\leftarrow R_{a_{j}}(t)$ $\backslash\backslash$
Reward at time $t$.

9: $R_{\pi}(t)\leftarrow\frac{R_{a_{j}}(t)}{R_{max}}$ $\backslash\backslash$
Normalize for Beta update.

10: $R^{*}$ = Bern $(R_{\pi}(t))$ $\backslash\backslash$ Bernoulli trial for
Beta update.

11: $\alpha_{j}\leftarrow\alpha_{j}+1-R^{*}$ $\backslash\backslash$ Update
priors.

12: $\beta_{j}\leftarrow\beta_{j}+R^{*}$ $\backslash\backslash$ Update priors.

13: $n_{j}\leftarrow n_{j}+1$ $\backslash\backslash$ Count of arm $a_{j}$.

14:
$\hat{\mu}_{j}(t)=\frac{\sum_{s=1}^{t}R_{a_{j}}(s)\mathcal{I}(a_{j}(s))}{n_{j}}$
$\backslash\backslash$ Update estimated mean of $a_{j}$.

15: end for

16: $p\leftarrow p+1$. $\backslash\backslash$End of the $p$-th TS phase.

17: Broadcast Probing Phase:

18: Play all the arms simultaneously for $T_{BP}$ rounds and build the
estimate:
$\displaystyle\hat{\mu}_{BP}=\frac{1}{T_{BP}}\sum_{t=(e_{i}-1)T_{l}+T_{TS}+1}^{(e_{i}-1)T_{l}+T_{TS}+T_{BP}}R_{BP}(t)$

19: if Equation (5) holds then

20: Change is detected.

21:Group Exploration Phase:

22: Construct super-arms $\\{B_{k}\\}=\texttt{CSA}({\bf a})$.

23: for $T_{GE}$ slots do

24: Play $B_{k}$ for $T_{B_{k}}$ rounds.

25: $\backslash\backslash$ Update $\mu_{B_{k}}$:
$\displaystyle\hat{\mu}_{B_{k}}(e_{i}(T_{TS}+T_{BP}))=\frac{1}{|B_{k}|}\sum_{a_{i}\in
B_{k}}\hat{\mu}_{i}(e_{i}(T_{TS}+T_{BP}))$

26: end for

27:
$a_{j}\in\bigcap\limits_{k=1}^{n}B_{k}:|\hat{\mu}_{B_{k}}-\frac{1}{n}\sum_{i\in
B_{k}}\hat{\mu}_{i}(pT_{N})|\geq\Delta,k=1,2,\ldots,n.$,
$\backslash\backslash$ Identify changed arm.

28: $\hat{\mu}_{j}(e_{i}T_{l}+1)=\sum_{k:a_{j}\in
B_{k}}\hat{\mu}_{B_{k}}-\sum_{k:a_{j}\in B_{k}}\sum_{a_{i}\in B_{k}:i\neq
j}\hat{\mu}_{i}$ $\backslash\backslash$ Update the changed arm.

29: Update the Beta parameters of the changed arm:
$\displaystyle\alpha_{j}=\alpha_{k},\quad\beta_{j}=\beta_{k}$ where
$\displaystyle k=\operatorname*{arg\,min}_{i}|\hat{\mu}_{i}-\hat{\mu}_{j}|$

30: else

31: Continue. $\backslash\backslash$ When no change is detected

32: end if

33:end for

Algorithm 2 Construct Super-Arms CSA

Input: ${\bf a}$ and ${\bf n}$.

Initialize: $B_{k}=\\{\\}$, $\forall k=1,2,\ldots,K$.

for $k=1$ to $n$ do

for $i=1$ to $K$ do

if dec2bin$(i)$ AND onehot$(k)\neq\texttt{zeros}(1,n)$ then

$B_{k}=B_{k}\cup a_{i}$

end if

end for

end for

Return $B_{k}$

##  3 Analysis of TS-GE

Let us recall that the GE phase is triggered only if a change is detected in
the BP phase. Consequently, the algorithm can miss detecting the chase in case
the change occurs either in the TS phase or the BP phase, which we analyze
below.

###  3.1 Probability of Missed Detection

Let the change occur in the arm $a_{i}$ at $t_{c}$ time slots within the
$m$-th TS phase, i.e., $T_{ETC}+(m-1)(T_{TS}+T_{BP})<t_{c}\leq
T_{ETC}+mT_{TS}+(m-1)T_{BP}$. The mean is assumed to change from $\mu_{i}^{-}$
to $\mu_{i}^{+}$. In other words, the distribution of the reward of $a_{i}$ is
given as:

$\displaystyle R_{i}(t)\sim$
$\displaystyle\begin{cases}X_{i}^{-}\sim\mathcal{N}\left(\mu_{i}^{-},\sigma^{2}\right);\;t\leq
T_{ETC}+(m-1)(T_{N}+T_{BP})+t_{c}\\\
X_{i}^{+}\sim\mathcal{N}\left(\mu_{i}^{+},\sigma^{2}\right);\;t>T_{ETC}+(m-1)(T_{N}+T_{BP})+t_{c}\end{cases}$

The following lemma characterizes the probability of missed detection when the
change occurs in the TS phase.

######  Lemma 2.

Let the arm $a_{i}$ change its mean from $\mu_{i}^{-}$ to $\mu_{i}^{+}$, where
$\Delta_{i}^{C}$ at a time slot $t_{c}$ in the $m$-th TS phase. Then the
probability of missed detection after the $m$-th BP phase following this
change is upper bounded by:

$\displaystyle\mathcal{P}_{M}^{TS}\leq\frac{1}{T}$ (9)

###### Proof.

See Appendix 7. ∎

######  Lemma 3.

Let the arm $a_{i}$ change its mean from $\mu_{i}^{-}$ to $\mu_{i}^{+}$, where
$\Delta_{i}^{C}$ at a time slot $t_{c}$ in the $m$-th BP phase. Then the
probability of missed detection after the $m$-th BP phase following this
change has the following characteristic:

$\displaystyle\mathcal{P}_{M}^{BP}=\begin{cases}\mathcal{P}_{M,Case1}^{BP};&\text{with
probability }>1-\frac{1}{T}\\\ \mathcal{P}_{M,Case2}^{BP};&\text{with
probability}\leq\frac{1}{T},\end{cases}$ (10)

where, $\mathcal{P}_{M,Case1}^{BP}\leq\frac{1}{T}$ and
$\mathcal{P}_{M,Case2}^{BP}>1-\frac{1}{T}$.

###### Proof.

See Appendix 8. ∎

Thus, a change in the BP phase results in a different probability of missed
detection based on the exact point of change.

###  3.2 Probability of False Alarm

The BP phase can raise a false alarm when a change has not occurred in an
episode while, the condition (5) holds true simultaneously. However, in case
of no change, the test statistic is simply:

$\displaystyle Z_{NC}\sim\mathcal{N}\left(0,\sigma_{NC}\right)$ (11)

where
$\sigma^{2}_{NC}=\frac{\sigma^{2}}{K}\left(\frac{1}{n_{ETC}}+\frac{1}{mT_{BP}}+\sum_{a_{j}\in\mathcal{K}}\frac{1}{n_{j}(m(T_{TS}+T_{BP}))}\right)$.
Here $n_{j}(mT_{l})$ is the number of times the arm $a_{j}$ has been played in
all the TS phases. Thus,

$\displaystyle\mathcal{P}_{FA}$ $\displaystyle=\mathbb{P}\left(|Z_{NC}|\geq
4\delta\right)\leq\mathcal{Q}\left(\frac{4\delta}{{\sigma_{NC}}}\right)\leq\frac{1}{T}$
(12)

###  3.3 On the Regret of TS-GE

Now we have all the necessary results to derive the regret bound for TS-GE.
Each episode either experiences a change or doesn’t. Accordingly, the regret
cna be dissected into the following components.

####  3.3.1 Regret in case of no change.

The number of such episodes is $N_{l}-N_{C}$. Each such episode experiences a
mandatory regret bounded by:

$\displaystyle\mathcal{R}_{\text{no
change}}^{1}(T_{l})\leq\underbrace{\mathcal{O}\left[\log\left(\sqrt{T}-T^{\frac{2}{5}}\right)\right]}_{A}+\underbrace{\mathcal{O}\left(T^{\frac{2}{5}}\right)}_{B},$

where the term $A$ is due to the TS phase and the term B is due to the BP
phase. In case of a false alarm, the algorithm subsequently experiences worst-
case regret in all the subsequent phases. This occurs with a probability of
$\mathcal{P}_{FA}$, and hence its contribution to the overall regret is:

$\displaystyle\mathcal{R}_{\text{no
change}}^{2}(T_{l})\leq\mathcal{P}_{FA}\Delta_{max}T\overset{(a)}{\leq}K_{1}$

The step (a) follows from (12). Thus, overall, for the case of no change, the
regret is:

$\displaystyle\mathcal{R}_{\text{no
change}}(T_{l})\leq\mathcal{O}\left[\log\left(\sqrt{T}-T^{\frac{2}{5}}\right)\right]+\mathcal{O}\left(T^{\frac{2}{5}}\right)+K_{1}.$
(13)

####  3.3.2 Regret in case of change.

The number of such episodes is $N_{c}$. Each such episode experiences a
mandatory regret bounded by:

$\displaystyle\mathcal{R}_{\text{change}}^{1}\leq\mathcal{O}\left(\Delta_{max}\sqrt{T}\right).$

However, in case of missed detection, the algorithm subsequently experiences
worst-case regret in all the subsequent phases. This occurs with a probability
$\mathcal{P}_{M}=p_{C}^{TS}\mathcal{P}_{M}^{TS}+p_{C}^{BP}\mathcal{P}_{M}^{BP}$
and hence its contribution to the overall regret is:

$\displaystyle\mathcal{R}_{\text{change}}^{2}\leq\mathcal{P}_{M}\Delta_{max}T\overset{(a)}{=}K_{2}$

Thus, overall, for the case of no change, the regret is:

$\displaystyle\mathcal{R}_{change}\leq\mathcal{O}\left(\Delta_{max}\sqrt{T}\right)+K_{2}$
(14)

Using the above development, we can bound the regret of TS-GE as follows:

$\displaystyle\mathcal{R}(T)$
$\displaystyle=\mathcal{R}_{ETC}\left(T_{ETC}\right)+\sum_{i=1}^{N_{l}}\mathcal{R}_{i}(T_{l})$
$\displaystyle\leq\mathcal{O}\left(K\log
T\right)+(N_{l}-N_{C})\mathcal{R}_{\text{no
change}}+N_{C}\mathcal{R}_{\text{change}}$
$\displaystyle\leq\mathcal{O}\left(K\log
T+\sqrt{T}\left[\max\\{N_{C}\left(1+\log
K\right),T^{\frac{2}{5}}\\}\right]\right)$ (15)

Thus, not only the regret of TS-GE is sub-linear but also as discussed in the
next section, it outperforms the known bounds under several regimes.

##  4 Discussion

(a) $K=100$. (b) $K=500$.  (c) $K=1000$.

Figure 1: Comparison of the regret bound of TS-GE with the best known regret
bounds of ADSWITCH and M-UCB for different values of $K$

.

In this section, we discuss the derived regret bound of TS-GE with respect to
the best known bound of ADSWITCH [11] and M-UCB [18], Let us define three time
slots $T_{1}$, $T_{2}$. and $T_{3}$ as follows:

  * •

$T_{1}\overset{\cdot}{=}t:N_{C}(1+\log_{2}K)=t^{\frac{2}{5}}$.

  * •

$T_{2},T_{3}\overset{\cdot}{=}t:\mathcal{R}_{\texttt{TS-
GE}}(t)=\sqrt{N_{C}Kt\log t}$, $T_{2}\leq T_{3}$.

In other words, $T_{2}$ and $T_{3}$ are the time instants where the regret
bound of TS-GE matches the bound of ADSWITCH or M-UCB. We compare the regret
bounds for three different number of arms relevant for a massive IoT setup:
small - $K=100$ arms, medium - $K=500$ arms, and large - $K=1000$ arms. We
consider a time-horizon of $T=1e5$ number of plays.

For $K=500$, Fig. 1b shows that there are specific regions where TS-GE
outperforms M-UCB. Beyond $T_{2}$, M-UCB outperforms TS-GE. The point of
interest for our discussion is the exact location of $T_{2}$ for different
values of $K$. For $K=100$, the value of $T_{2}$ is low (see Fig. 1a) and the
regret bound of M-UCB is lower than TS-GE for most part of the time-horizon.
However, in case of $K=1000$, the value of $T_{2}$ is beyond the time-horizon,
and accordingly, beyond time step 5000, throughout the time frame of interest,
TS-GE outperforms M-UCB. This highlights the fact that the time-period of
interest in a specific application would dictate the choice of a particular
algorithm.

Figure 2: Comparison of the regret of TS-GE with M-UCB and TS.

In Fig. 2, we compare the classical TS algorithm with TS-GE and M-UCB. In
order to highlight the change detection framework, we consider fixed change
points across different realizations of the algorithms. Specifically, changes
occur at $E_{i}=30,60,90,120,150$. We see that TS-GE outperforms the others by
detecting the exact arm that has undergone a change. Interestingly, M-UCB
performs worse than TS, mainly due to the fact that M-UCB flushes all the past
(potentially relevant) rewards and restarts the exploration procedure once a
system-level change is detected.

##  5 Case Study: SWIPT in an IIoT Network

In this section, we employ the TS-GE algorithm to evaluate an IIoT network
where a central controller transmits data-packets to the device with the best
channel condition and simultaneously performs wireless power transfer to all
the devices.

###  5.1 Network Model

Let us consider an IIoT network consisting of a central wireless access point
(AP) and $K$ IoT devices. The set of the devices is denoted by $\mathcal{K}$.
Typically an industrial environment deals with a large $K$ that represent
multiple sensors and cyber-physical systems. The AP provisions two wireless
services in the network: i) periodic wireless power transfer (wpt) to all the
IoT devices and ii) a unicast broadband data transmission to one selected IoT
device. 333The unicast service is relevant in cases when the AP intends to
select the best storage-enabled IoT device to transfer large files for caching
at the edge. This may then be accessed by the other IoT devices, e.g., using
device-to-device link. However, in this paper, we do not delve deeper into
such an analysis.

####  5.1.1 Network Parameters

Let the scenario of interest be modeled as a two-dimensional disk
$\mathcal{B}(0,R)$ of radius $R$ centered around the origin similar to [21].
The transmit power of the AP is $P_{t}$. The location of the devices is
assumed to be uniform in $\mathcal{B}(0,R)$. Each AP-device link may be
blocked by roaming blockages in the environment. The probability that a link
of length $r$ is in line of sight (LOS) is assumed to be $p_{L}(r)=exp(-\omega
r)$ [22]. Furthermore, note that due to the presence of a large number of
metallic objects, an industrial scenario presents a dense scattering
environment. Consequently, we assume that each transmission link experiences a
fast-fading $h$ modeled as a Rayleigh distributed random variable with
variance 1. Thus, The received power at an IoT device at a distance of $r$
from the AP is given by $P_{r}(r)=KP_{t}hr^{-\gamma}$ with a probability
$p_{L}(r)$. Here $K$ and $\gamma$ respectively are the path-loss coefficient
and the path-loss exponent. The total transmission bandwidth is assumed to be
$B$ which is orthogonally allotted to the users scheduled in one time-slot.

At each episode, the controller selects the device with the best channel
conditions and executes information transfer in a sequence of time-slots using
the TS phase of the algorithm. The device-specific transmission can be
facilitated by employing techniques such as beamforming. However we do not
consider the details of such procedures. The TS phase information transfer is
followed by joint power transfer to all the devices. This is mapped to the BP
phase of the algorithm. At the end of the BP phase, the total energy harvested
at all the devices at the end of the BP phase is reported back to the
controller. Using this total energy transfer report, the controller detects
whether a change in the large-scale channel conditions has taken place. If so,
then the controller probes multiple devices grouped together as per TS-GE to
detect the device with the current best channel conditions.

###  5.2 Performance Bounds using Stochastic Geometry

Before proceeding with the evaluation of TS-GE in this network, let us first
derive the upper bound on the statistical performance of data-rate. This will
enable a comparison with not only an existing algorithm but also the
performance limit. Since the location of the devices is assumed to be uniform
across the factory floor, they form a realization of a binomial point process
(BPP). Additionally, due to the assumption that the blockage in each link is
independent of each other, the IoT devices are either in LOS or NLOS state.
The probability that at least one of the IoT devices is in LOS state is given
by:

$\displaystyle B_{L}$ $\displaystyle=\left[\int_{0}^{R}\exp(-\omega
t)\frac{2t}{R}dt\right]^{K}$ $\displaystyle=\left(2\frac{1-\exp\left(-\omega
R^{2}\right)\left(\omega R^{2}+1\right)}{\omega^{2}R^{2}}\right)^{K}$

The above expression follows similarly to [23]. On the same lines, the
probability that at least one of the IoT devices is in NLOS state is given by

$\displaystyle B_{N}$ $\displaystyle=\left(R-2\frac{1-\exp\left(-\omega
R^{2}\right)\left(\omega R^{2}+1\right)}{\omega^{2}R^{2}}\right)^{K}$

####  5.2.1 Best-link transmission for information transfer

Out of the possible IoT devices, the central controller selects the device
with the best channel condition for information transfer. For that first, let
us derive the distance distributions of the nearest LOS and NLOS devices.

######  Lemma 4.

The distribution of the distance to the nearest LOS device, $r_{L1}$ and the
nearest NLOS device, $r_{N1}$ are respectively:

$\displaystyle\mathbb{P}\left(r_{L1}\geq x\right)$
$\displaystyle=\frac{\left(x^{2}U_{L}(x)\frac{R^{2}}{R^{2}-x^{2}}\right)^{K+1}-1}{x^{2}U_{L}(x)\frac{R^{2}}{R^{2}-x^{2}}-1}\left(\frac{R^{2}-x^{2}}{R^{2}}\right)^{K}$
$\displaystyle\mathbb{P}\left(r_{N1}\geq x\right)$
$\displaystyle=\frac{\left(x^{2}U_{N}(x)\frac{R^{2}}{R^{2}-x^{2}}\right)^{K+1}-1}{x^{2}U_{N}(x)\frac{R^{2}}{R^{2}-x^{2}}-1}\left(\frac{R^{2}-x^{2}}{R^{2}}\right)^{K}$

where,

$\displaystyle U_{L}(x)$ $\displaystyle=\frac{2\left(1-\exp\left(-\omega
x\left(\omega x+1\right)\right)\right)}{\omega^{2}x}$ $\displaystyle U_{N}(x)$
$\displaystyle=x-\frac{2\left(1-\exp\left(-\omega x\left(\omega
x+1\right)\right)\right)}{\omega^{2}x}$

###### Proof.

Using the void probabilities (see [24]) we have:

$\displaystyle\mathbb{P}\left(r_{L1}\geq x\right)$
$\displaystyle=\sum_{k=0}^{K}\left[\int_{0}^{x}\exp\left(-\omega
t\right)\frac{2t}{x^{2}}dt\right]^{k}\left(\frac{x^{2}}{R^{2}}\right)^{k}\left(\frac{R^{2}-x^{2}}{R^{2}}\right)^{K-k}$
$\displaystyle=\sum_{k=0}^{K}\left[x^{2}U_{L}(x)\left(\frac{R^{2}}{R^{2}-x^{2}}\right)\right]^{k}\left(\frac{R^{2}-x^{2}}{R^{2}}\right)^{K}$

Evaluating the above series derives the result. The case for the NLOS device
also follows in a similar manner. ∎

######  Corollary 1.

Thus, the probability that the best device is in LOS state is given as:

$\displaystyle\mathcal{P}_{L}$
$\displaystyle=\mathbb{P}\left(KPr_{L1}^{-\gamma_{L}}\geq
KPr_{N1}^{-\gamma_{N}}\right)$ $\displaystyle=\mathbb{P}\left(r_{L1}\leq
r_{N1}^{\frac{\gamma_{N}}{\gamma_{L}}}\right)$
$\displaystyle=\mathbb{E}_{r_{N1}}\left[1-\frac{\left(r_{N1}^{\frac{2\gamma_{N}}{\gamma_{L}}}U_{L}(r_{N1}^{\frac{\gamma_{N}}{\gamma_{L}}})\frac{R^{2}}{R^{2}-r_{N1}^{\frac{2\gamma_{N}}{\gamma_{L}}}}\right)^{K+1}-1}{r_{N1}^{\frac{2\gamma_{N}}{\gamma_{L}}}U_{L}(r_{N1}^{\frac{\gamma_{N}}{\gamma_{L}}})\frac{R^{2}}{R^{2}-r_{N1}^{\frac{2\gamma_{N}}{\gamma_{L}}}}-1}\right.$
$\displaystyle\left.\left(\frac{R^{2}-r_{N1}^{\frac{2\gamma_{N}}{\gamma_{L}}}}{R^{2}}\right)^{K}\right].$

Across different realizations of the network, the best link experiences a
fading-averaged downlink received power

$\displaystyle P_{r}=\begin{cases}KP_{t}r_{L1}^{-\gamma_{L}};&\text{with
probability }\mathcal{P}_{L}\\\ KP_{t}r_{N1}^{-\gamma_{N}};&\text{with
probability }1-\mathcal{P}_{L}\end{cases}$ (17)

Over a time-horizon of $T$ slots the throughput experienced by the system can
then be evaluated as:

$\displaystyle\mathcal{T}=\frac{N_{l}T_{TS}}{N_{l}T_{BP}+T_{ETC}+N_{C}T_{GE}}\mathbb{E}\left[B\log_{2}\left(1+\frac{P_{r}}{N_{0}}\right)\right]$
(18)

where the expectation taken over $P_{r}$ as per (17).

####  5.2.2 Multicast/Broadcast transmission for power transfer

Let us assume that in the multicast transmission phase, the AP transmits data
to a subset $\mathcal{J}\subset\mathcal{K}$ of the IoT devices, where
$|\mathcal{J}|=N_{J}$. In this case, the available bandwidth $B$ is shared
among the $N_{J}$ devices. The harvested power experienced by an IoT device of
$\mathcal{J}$ is:

$\displaystyle\mathcal{T}_{j}=\begin{cases}\theta_{e}\frac{N_{j}}{K}{KPr_{j}^{-\gamma_{L}}}\;\text{
with probability }\exp\left(-\omega r_{j}\right)\\\
\theta_{e}\frac{N_{j}}{K}\frac{BN_{0}}{N_{j}}\;\text{ with probability
}1-\exp\left(-\omega r_{j}\right)\end{cases}$ (19)

Accordingly, the network sum-energy is given by:

$\displaystyle\mathcal{T}_{T}=\sum_{j\in\mathcal{J}}T_{j},$ (20)

in one slot. In case of the BP phase, naturally we have
$\mathcal{J}=\mathcal{K}$.

###  5.3 Numerical Example

We run the TS-GE algorithm in our IIoT network for a total of 1000s with time-
slots of 10 ms [25]. Additionally we assume slow moving blockages in which
each 30 seconds the visibility state of exactly one IoT device changes from
LOS to NLOS or vice-versa.

Figure 3: Expected bes-device throughput and worst-case harversted energy with
TS-GE.

In Fig. 3 we plot the average throughput of the information transfer phase
(i.e., to the best device) as well as the minimum harvested energy in a device
in the IIoT network. We observe that in case of a fewer IoT devices, the M-UCB
algorithm performs better than TS-GE. Indeed resetting all arms does not incur
a large exploration loss in M-UCB in case $K$ is small. Additionally, M-UCB is
not constrained by mandatory exploration. Accordingly, it enjoys a higher
throughput as compared to TS-GE which needs to transfer energy all the
devices.

Interestingly, as the number of devices in the network increases beyond a
threshold, TS-GE outperforms M-UCB especially due to rapid changed state
identification in the device. Naturally, as $K$ increases, the amount of time
dedicated for energy transfer decreases. This is reflected in the reduced
energy harvested in the worst device.

Several open problems are apparent. For example, the condition on that each
episode can experience only one change can be too stringent to be applied
meaningfully in contexts. Furthermore, change detection in the distributions
rather than mean and extension to multiple players are indeed interesting
directions of research which will be treated in a future work.

##  6 Conclusion

Existing multi-armed bandit algorithms tuned for non-stationary environments
sample sub-optimal arms in a probabilistic manner in proportion to their sub-
optimality gap. However, several applications require periodic mandatory
probing of all the arms. To address this, we develop a novel algorithm called
TS-GE which balances the regret guarantees of classical Thompson sampling with
a periodic group-exploration phase which not only ensures the mandatory
probing of all the arms but also acts as a mechanism to detect changes in the
framework. We show that the regret guarantees provided by TS-GE outperforms
the state-of-the-art algorithms like M-UCB and ADSWITCH for several time-
horizons, especially for a high number of arms. We demonstrated the efficacy
of TS-GE in an industrial IoT network designed for simultaneous wireless
information and power transfer.

## References

  * [1] A. Slivkins et al., “Introduction to multi-armed bandits,” Foundations and Trends® in Machine Learning, vol. 12, no. 1-2, pp. 1–286, 2019.
  * [2] W. R. Thompson, “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples,” Biometrika, vol. 25, no. 3/4, pp. 285–294, 1933.
  * [3] J. Gittins, K. Glazebrook, and R. Weber, Multi-armed bandit allocation indices.  John Wiley & Sons, 2011.
  * [4] S. Pilarski, S. Pilarski, and D. Varró, “Delayed reward bernoulli bandits: Optimal policy and predictive meta-algorithm pardi,” IEEE Transactions on Artificial Intelligence, vol. 3, no. 2, pp. 152–163, 2022.
  * [5] S. Pilarski, S. Pilarski, and D. Varró, “Optimal policy for bernoulli bandits: Computation and algorithm gauge,” IEEE Transactions on Artificial Intelligence, vol. 2, no. 1, pp. 2–17, 2021.
  * [6] E. Contal, D. Buffoni, A. Robicquet, and N. Vayatis, “Parallel gaussian process optimization with upper confidence bound and pure exploration,” in Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 225–240, Springer, 2013.
  * [7] A. Uprety and D. B. Rawat, “Reinforcement learning for iot security: A comprehensive survey,” IEEE Internet of Things Journal, vol. 8, no. 11, pp. 8693–8706, 2020.
  * [8] S. K. Singh, V. S. Borkar, and G. Kasbekar, “User association in dense mmwave networks as restless bandits,” IEEE Transactions on Vehicular Technology, pp. 1–1, 2022.
  * [9] J. Huh and E. C. Malthouse, “Advancing computational advertising: Conceptualization of the field and future directions,” Journal of Advertising, vol. 49, no. 4, pp. 367–376, 2020.
  * [10] G. Ghatak, H. Mohanty, and A. U. Rahman, “Kolmogorovsmirnov test-based actively-adaptive thompson sampling for non-stationary bandits,” IEEE Transactions on Artificial Intelligence, 2021.
  * [11] P. Auer, P. Gajane, and R. Ortner, “Adaptively tracking the best bandit arm with an unknown number of distribution changes,” in Conference on Learning Theory, pp. 138–158, 2019.
  * [12] Y. Liu, B. Van Roy, and K. Xu, “Nonstationary bandit learning via predictive sampling,” arXiv preprint arXiv:2205.01970, 2022.
  * [13] J. Mellor and J. Shapiro, “Thompson sampling in switching environments with bayesian online change detection,” in Artificial Intelligence and Statistics, pp. 442–450, 2013.
  * [14] C. Hartland, S. Gelly, N. Baskiotis, O. Teytaud, and M. Sebag, “Multi-armed bandit, dynamic environments and meta-bandits,” 2006.
  * [15] V. Srivastava, P. Reverdy, and N. E. Leonard, “Surveillance in an abruptly changing world via multiarmed bandits,” in 53rd IEEE Conference on Decision and Control, pp. 692–697, IEEE, 2014.
  * [16] J. Y. Yu and S. Mannor, “Piecewise-stationary bandit problems with side observations,” in Proceedings of the 26th annual international conference on machine learning, pp. 1177–1184, 2009.
  * [17] G. Ghatak, “A change-detection-based thompson sampling framework for non-stationary bandits,” IEEE Transactions on Computers, vol. 70, no. 10, pp. 1670–1676, 2020.
  * [18] Y. Cao, Z. Wen, B. Kveton, and Y. Xie, “Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit,” in The 22nd International Conference on Artificial Intelligence and Statistics, pp. 418–427, 2019.
  * [19] S. Fatale, K. Bhandari, U. Narula, S. Moharir, and M. K. Hanawal, “Regret of age-of-information bandits,” IEEE Transactions on Communications, vol. 70, no. 1, pp. 87–100, 2022.
  * [20] S. Agrawal and N. Goyal, “Analysis of thompson sampling for the multi-armed bandit problem,” in Conference on learning theory, pp. 39–1, 2012.
  * [21] G. Ghatak, S. R. Khosravirad, and A. De Domenico, “Stochastic geometry framework for ultra-reliable cooperative communications with random blockages,” IEEE Internet of Things Journal, 2021.
  * [22] T. Bai, R. Vaze, and R. W. Heath, “Analysis of Blockage Effects on Urban Cellular Networks,” IEEE Trans. Wireless Commun., vol. 13, no. 9, pp. 5070–5083, 2014.
  * [23] T. Bai and R. W. Heath, “Coverage and rate analysis for millimeter-wave cellular networks,” IEEE Transactions on Wireless Communications, vol. 14, no. 2, pp. 1100–1114, 2014.
  * [24] D. Stoyan, W. S. Kendall, S. N. Chiu, and J. Mecke, Stochastic geometry and its applications.  John Wiley & Sons, 2013.
  * [25] J.-C. Lin, “Synchronization requirements for 5g: An overview of standards and specifications for cellular networks,” IEEE Vehicular Technology Magazine, vol. 13, no. 3, pp. 91–99, 2018.

##  7  Proof of Lemma 2

Let the number of times the arm $a_{i}$ is played is $t_{i}^{-}$ times before
$t_{c}$ and $t_{i}^{+}$ times after $t_{c}$. The test statistic (i.e., the
parameter to be compared to $2\delta$) is simply a random variable $Z_{TS}$
given by:

$\displaystyle
Z_{TS}=\frac{1}{Kn_{ETC}}\sum_{q=(i-1)n_{ETC}+1}^{in_{ETC}}X_{i}^{-}(q)+\frac{1}{K}\sum_{a_{j}\neq
a_{i}}\frac{1}{n_{ETC}}$
$\displaystyle\sum_{q=(j-1)n_{ETC}+1}^{jn_{ETC}}X_{j}(q)+\frac{1}{(K)n_{j}(T^{\prime})}\sum_{a_{j}\neq
a_{i}}\sum_{q_{j}=T_{ETC}+1}^{T^{\prime}}\cdot$ $\displaystyle
X_{j}(q)\mathbb{I}(a_{\texttt{TS-
GE}}(q)=a_{j})+\frac{1}{t_{i}^{-}+t_{i}^{+}}\left[\sum_{q}X_{i}^{-}(q)+\right.$
$\displaystyle\left.\sum
X_{i}^{+}(q)\right]-\frac{1}{KT_{BP}}\sum_{q=T^{\prime}}^{T^{\prime\prime}}X_{i}^{+}(q)-\frac{1}{KT_{BP}}\sum_{q=T^{\prime}}^{T^{\prime\prime}}\sum_{a_{j}\neq
a_{i}}X_{j}(q)$ (21)

Here $T^{\prime}=T_{ETC}+(m-1)(T_{TS}+T_{BP})+T_{TS}$,
$T^{\prime\prime}=T_{ETC}+m(T_{TS}+T_{BP})$, and $n_{j}(t)$ is the number to
times the arm $a_{j}$ has been played until time $t$. Since all the arms
except $a_{i}$ remain stationary, we have:

$\displaystyle\mathbb{P}\left(\Big{|}\frac{1}{K}\sum_{a_{j}\neq
a_{i}}\frac{1}{n_{ETC}}\sum_{q=(j-1)n_{ETC}+1}^{jn_{ETC}}X_{j}(q)+\frac{1}{(K)n_{j}(T^{\prime})}\right.$
$\displaystyle\left.\sum_{a_{j}\neq
a_{i}}\sum_{q_{j}=T_{ETC}+1}^{T^{\prime}}X_{j}(q)\mathbb{I}(a_{\texttt{TS-
GE}}(q)=a_{j})+\right.$
$\displaystyle\left.-\frac{1}{KT_{BP}}\sum_{q=T^{\prime}}^{T^{\prime\prime}}\sum_{a_{j}\neq
a_{i}}X_{j}(q)\Big{|}\geq
2\delta\right)\leq\mathcal{O}\left(\frac{1}{T^{2}}\right)$ (22)

Consequently, for the decision of change detection it is of interest to
consider the following random variable instead:

$\displaystyle Z_{TS}^{\prime}=$
$\displaystyle\frac{1}{Kn_{ETC}}\sum_{q=(i-1)n_{ETC}+1}^{in_{ETC}}X_{i}^{-}(q)+\frac{1}{K(t_{i}^{-}+t_{i}^{+})}$
$\displaystyle\left[\sum_{q}X_{i}^{-}(q)+\sum
X_{i}^{+}(q)\right]-\frac{1}{KT_{BP}}\sum_{q=T^{\prime}}^{T^{\prime\prime}}X_{i}^{+}(q),$
(23)

and compare it to a threshold of $2delta$. Note that $Z^{\prime}_{TS}$ is
Gaussian distributed with mean
$\mu_{Z^{\prime}_{TS}}=\Delta_{i}^{C}+\frac{1}{t_{i}^{-}+t_{i}^{+}}\left(t_{i}^{-}\mu_{i}^{-}+t_{i}^{+}\mu_{I}^{+}\right)$
and variance given by
$\sigma_{Z^{\prime}_{TS}}^{2}=\frac{\sigma^{2}}{K^{2}}\left(\frac{1}{n_{ETC}}+\frac{1}{t_{i}^{-}+t_{i}^{+}}+\frac{1}{T_{BP}}\right)$.
Consequently, there are two cases of interest:

Case 1 - $\Delta^{C}_{i}>0$: This is the case where the mean of the arm
$a_{i}$ increases from $\mu_{i}^{-}$ to $\mu_{i}^{+}$. Accordingly the missed
detection probability can be written as:

$\displaystyle\mathcal{P}_{M}^{TS}$
$\displaystyle=\mathbb{P}\left(|Z^{\prime}_{TS}|\leq
2\delta\right)\leq\mathcal{Q}\left[\frac{\mu_{Z^{\prime}_{TS}}-2\delta}{\sigma_{Z^{\prime}_{TS}}}\right]$
$\displaystyle\overset{(a)}{\leq}\mathcal{Q}\left[\frac{\Delta^{C}_{i}-2\delta}{\frac{\sigma}{K}\sqrt{\frac{1}{n_{ETC}}+\frac{1}{t_{i}^{-}+t_{i}^{+}}+\frac{1}{KT_{BP}}}}\right]$
$\displaystyle\overset{(b)}{\leq}\mathcal{Q}\left[\frac{K\sqrt{n_{ETC}+t_{i}^{-}+t_{i}^{+}+T_{BP}}}{3}\frac{\Delta^{C}_{i}-2\delta}{\sigma}\right]$
$\displaystyle\overset{(c)}{\leq}\frac{1}{T}.$

In the above $\mathcal{Q}(\cdot)$ is the Gaussian-Q function. The inequality
(a) follows from the facts that
$\frac{1}{t_{i}^{-}+t_{i}^{+}}\left(t_{i}^{-}\mu_{i}^{-}+t_{i}^{+}\mu_{I}^{+}\right)\geq
0$ and the $\mathcal{Q}(\cdot)$ is a decreasing function. The step (b) follows
from the AM $>$ HM inequality, while the step (c) follows from the Assumption
3 and the inequality $Q(K.\sqrt{x^{(}2/5)})\leq\frac{1}{x}$ for $K\geq 1$.

Case 2 - $\Delta_{i}^{C}\leq 0$: This refers to the case where the mean of arm
$a_{i}$ decreases from $\mu_{i}^{-}$ to $\mu_{i}^{+}$, i.e.,
$\mu_{i}^{+}\leq\mu_{i}^{-}$. Accordingly, the missed detection probability
follows similarly to the above:

$\displaystyle\mathcal{P}_{M}^{TS}$
$\displaystyle=\mathbb{P}\left(|Z^{\prime}_{TS}|\leq
2\delta\right)\leq\frac{1}{T}$

##  8  Proof of Lemma 3

Let in the BP phase, the number of times all the arms are played
simultaneously be $t_{i}^{-}$ times before $t_{c}$ and $t_{i}^{+}$ times after
$t_{c}$. Given that other arms $a_{j}$ where $j\neq i$ have not changed, the
test statistic (i.e., the parameter to be compared to $2\delta$) is simply a
random variable $Z_{BP}$ similar to $Z_{TS}$. Since all the arms except
$a_{i}$ remain stationary, we have:

$\displaystyle\mathbb{P}\left(\Big{|}\frac{1}{K}\sum_{a_{j}\neq
a_{i}}\frac{1}{n_{ETC}}\sum_{q=(j-1)n_{ETC}+1}^{jn_{ETC}}X_{j}(q)+\frac{1}{Kn_{j}(T^{\prime})}\right.$
$\displaystyle\left.\sum_{a_{j}\neq
a_{i}}\sum_{q_{j}=T_{ETC}+1}^{T^{\prime}}X_{j}(q)\mathbb{I}(a_{\texttt{TS-
GE}}(q)=a_{j})+\right.$
$\displaystyle\left.-\frac{1}{KT_{BP}}\sum_{q=T^{\prime}}^{T^{\prime\prime}}\sum_{a_{j}\neq
a_{i}}X_{j}(q)\Big{|}\geq
2\delta\right)\leq\mathcal{O}\left(\frac{1}{T^{2}}\right)$ (24)

Consequently, for the decision of change detection it is of interest to
consider the following random variable instead:

$\displaystyle Z_{BP}^{\prime}=$
$\displaystyle\frac{1}{Kn_{ETC}}\sum_{q=(i-1)n_{ETC}+1}^{in_{ETC}}X_{i}^{-}(q)+\frac{1}{Kn_{i}(T^{\prime})}\sum_{q}X_{i}^{-}(q)$
$\displaystyle-\frac{1}{K(t_{i}^{-}+t_{i}^{+})}\left[\sum_{q}X_{i}^{-}(q)+\sum
X_{i}^{+}(q)\right]$ (25)

Note that $Z^{\prime}_{BP}$ is Gaussian distributed with mean
$\mu_{Z^{\prime}_{BP}}=\mu_{i}^{-}-\frac{1}{t_{i}^{-}+t_{i}^{+}}\left(t_{i}^{-}\mu_{i}^{-}+t_{i}^{+}\mu_{i}^{+}\right)$
and variance given by
$\sigma_{Z^{\prime}_{TS}}^{2}=\frac{\sigma^{2}}{K^{2}}\left(\frac{1}{n_{ETC}}+\frac{1}{t_{i}^{-}+t_{i}^{+}}+\frac{1}{T_{BP}}\right)$.

Case 1 - $\Delta_{i}^{C}>4\delta$ and
$t_{i}^{-}\leq\frac{T_{BP}(\Delta_{i}^{C}-4\delta)}{\Delta_{i}^{C}}$:

This case occurs with a high probability. Due to the fact that for this case,
we have $t_{i}^{-}\leq\frac{T_{BP}(\Delta_{i}^{C}-4\delta)}{\Delta_{i}^{C}}$,
i.e., $\mu_{Z^{\prime}_{BP}}\geq 4\delta$, thus, similar to the Lemma 2,

$\displaystyle\mathcal{P}_{M|\text{Case 1}}^{BP}\leq\frac{1}{T}$ (26)

Thus, we have:

$\displaystyle\mathcal{P}_{M,\text{Case 1}}^{BP}=\mathcal{P}_{M|\text{Case
1}}^{BP}\cdot\mathcal{P}_{\text{Case 1}}\leq\frac{1}{T},$ (27)

Case 2 - $\Delta_{i}^{C}>4\delta$ and
$t_{i}^{-}>\frac{T_{BP}(\Delta_{i}^{C}-4\delta)}{\Delta_{i}^{C}}$: Here we
have $\mu_{Z^{\prime}_{BP}}<4\delta$, and accordingly, the probability of
missed detection is high. However, let us first observe the probability that
the change occurs such that
$t_{i}^{-}>\frac{T_{BP}(\Delta_{i}^{C}-4\delta)}{\Delta_{i}^{C}}$. We have:

$\displaystyle\mathbb{P}\left(\text{Case 2}\right)$
$\displaystyle=\mathbb{P}\left(t_{i}^{-}>\frac{T_{BP}(\Delta_{i}^{C}-4\delta)}{\Delta_{i}^{C}}\right)$
$\displaystyle=\mathbb{P}\left(\frac{t_{i}^{+}}{t_{i}^{-}}\geq\frac{4\delta}{\Delta_{i}^{C}-4\delta}\right)\overset{(a)}{\leq}\frac{1}{T}$

where the step (a) is due to Assumption 4.

Case 3 - $\Delta_{i}^{C}<4\delta$ and
$t_{i}^{-}\leq\frac{T_{BP}(-\Delta_{i}^{C}-4\delta)}{\Delta_{i}^{C}}$: This
case is similar to Case 1 and hence we skip the detailed proof for brevity. In
summary, similar to Case 1, for Case 3 the probability that the change occurs
at a time step such that
$t_{i}^{-}\leq\frac{T_{BP}(-\Delta_{i}^{C}-4\delta)}{\Delta_{i}^{C}}$ holds is
high. However, the probability of missed detection is bounded by
$\frac{1}{T}$.

Case 4 - $\Delta_{i}^{C}<4\delta$ and
$t_{i}^{-}>\frac{T_{BP}(-\Delta_{i}^{C}-4\delta)}{\Delta_{i}^{C}}$: This is
similar to Case 2, wherein the probability of missed detection is high, while
due to the Assumption 4, the occurrence of the change such that the condition
$t_{i}^{-}>\frac{T_{BP}(-\Delta_{i}^{C}-4\delta)}{\Delta_{i}^{C}}$ holds is
bounded by $\frac{1}{T}$.

  *[RL]: reinforcement-learning
  *[MAB]: multi-armed bandit
  *[IoT]: internet of things
  *[IIoT]: industrial internet of things
  *[SWIPT]: simultaneous wireless information and power transfer
  *[TS]: Thompson Sampling
  *[BP]: broadcast probing
  *[GE]: group exploration
  *[AP]: access point
  *[wpt]: wireless power transfer
  *[LOS]: line of sight
  *[BPP]: binomial point process