# GAN-based Intrinsic Exploration For Sample Efficient Reinforcement Learning

Doğay Kamar1, Nazım Kemal Üre1,2 and Gözde Ünal1,2
1Faculty of Computer and Informatics, Istanbul Technical University, Istanbul,
Turkey
2Artificial Intelligence and Data Science Research Center, Istanbul Technical
University, Istanbul, Turkey
{kamard, ure<EMAIL_ADDRESS>

###### Abstract

In this study, we address the problem of efficient exploration in
reinforcement learning. Most common exploration approaches depend on random
action selection, however these approaches do not work well in environments
with sparse or no rewards. We propose Generative Adversarial Network-based
Intrinsic Reward Module that learns the distribution of the observed states
and sends an intrinsic reward that is computed as high for states that are out
of distribution, in order to lead agent to unexplored states. We evaluate our
approach in Super Mario Bros for a no reward setting and in Montezuma’s
Revenge for a sparse reward setting and show that our approach is indeed
capable of exploring efficiently. We discuss a few weaknesses and conclude by
discussing future works.

##  1 INTRODUCTION

In reinforcement learning, an agent learns which action to take depending on
the current state by trying to maximize the reward signal provided by the
environment [Sutton and Barto, 2018]. The agent is not given any prior
information about the environment or which action to take, but instead, it
learns which actions return more reward in a trial-and-error manner. To do so,
agents are usually incentivized to explore the state-action space before
committing to the known rewards in order to avoid exploitation of a non-
optimal solution.

Most common approaches to exploration, such as $\epsilon$-greedy in Deep-Q-
Network (DQN) [Mnih et al., 2013], adding Ornstein–Uhlenbeck to action in Deep
Deterministic Policy Gradient (DDPG) [Lillicrap et al., 2016] or maximizing
entropy over the action space in Asynchronous Advantage Actor-Critic (A3C)
[Mnih et al., 2016], rely on increasing the probability of a random action.
This approach works fine in an environment with dense reward signals. However,
in sparse or no reward settings, the agent fails to find a reward signal to
guide itself, thus failing to find a solution.

Related works have focused on providing an extra intrinsic reward to the agent
in addition to the extrinsic reward, i.e. the reward from the environment.
Prediction-based exploration models estimate the novelty of an observation by
learning the environment dynamics and assigning higher rewards to the
observation which the future of it can not predict well, i.e. it makes the
agent act ”curiously” [Schmidhuber, 1991, Pathak et al., 2017, Stadie et al.,
2015]. In another work, environment dynamics is modeled using variational
inference and the novelty of a state is measured through prediction using this
model [Houthooft et al., 2016]. [Pathak et al., 2019] proposed a framework
with multiple dynamic models, and the intrinsic reward is calculated by the
disagreement between the dynamic models.

Another set of methods are based on count-based exploration, by counting the
number of times a state is visited and encouraging the agent to visit less-
visited states. However, if the state space is high dimensional, it is not
feasible to keep track of all the states. Recent studies proposed density
models to approximate how frequently a state is visited [Bellemare et al.,
2016, Ostrovski et al., 2017, Zhao and Tresp, 2019]. [Tang et al., 2017]
benefited from hashing in order to shrink the state-space to keep the count of
the visitations to states.

In ”Random Network Distillation (RND)”, features of an observation are
calculated through a fixed, randomly initialized network and another network
is trained to predict these features, with the error being the intrinsic
reward [Burda et al., 2019]. ”Never Give Up” adds on to RND by a memory-based
episodic reward module, where they keep the embeddings of the states observed
in the current episode and compare the new states to the ones in the memory,
discouraging the agent to visit the same states in the episode, while also
using RND for the long-term exploration [Badia et al., 2020]. DORA framework
creates an identical MDP to the task at hand with E-values fixed to 0 instead
of Q-values for every state-action pair, and assigns a bonus intrinsic reward
for how well the framework can predict the E-value in the current state
[Choshen et al., 2018].

Instead of computing an intrinsic reward, [Ecoffet et al., 2021] proposes ”Go-
Explore”, a method that focuses on exploring until a solution is found before
starting policy learning. In ”Go-explore”, a memory is maintained to keep the
visited states, which are encoded into lower-sized cells, and periodically, a
state is selected from the memory to go back to and explore from. Selection of
the state is probabilistic, however, the probabilities are assigned using a
heuristic, which tries to assign higher probabilities to ”interesting” states,
i.e. states that have better chances to lead to a good exploration. Once a
solution is found through exploration, the agent goes through a
robustification phase using imitation learning. A similar idea named ”Diverse
Trajectory-conditioned Self-Imitation Learning (DTSIL)” is proposed by [Guo et
al., 2019], where they train a policy using Self-Imitation Learning [Oh et
al., 2018] to follow trajectories stored in a memory, which lead agent to
less-frequently-visited states, in order to learn a policy for exploring the
environment.

This study follows the trend of providing an intrinsic reward to the agent by
using Generative Adversarial Networks (GAN) [Goodfellow et al., 2014]. GANs
consist of two networks: a generator $G$ tasked with generating synthetic data
similar to real data, and a discriminator $D$ tasked with measuring the
probability of the input being real to discriminate real and generated data.
Both $G$ and $D$ have tasks adversarial to each other as $G$ tries to fool $D$
that the data it generates is real, and $D$ tries to successfully detect data
generated by $G$. The convergence of GAN happens when $G$ is able to generate
data indistinguishable to $D$, and $D$ has 50% accuracy of detecting fake
data, meaning $D$ starts to randomly guess. $G$’s ability to generate new data
comes from its learning and fitting to the distribution of the real data,
therefore, in theory, with the right input, $G$ should be able to generate
exactly the same sample from the original data distribution. This idea is
realized in the anomaly detection task in [Schlegl et al., 2017] and [Schlegl
et al., 2019], in which, after the training of GAN, $G$ is forced to generate
the query sample and an anomaly score is assigned by measuring the difference
between generated and query sample. A high anomaly score means the query
sample is an out-of-distribution sample. Inspired by this work [Schlegl et
al., 2019], we propose a GAN-based exploration method for reinforcement
learning, where a GAN is trained using the visited state observations. The
trained $G$ is used to assign an intrinsic reward to the agent, and unobserved
novel states are assigned higher rewards due to them not being in the
distribution of the observed states used in GAN’s training.

A recent study has also utilized GANs for the task of exploration [Hong et
al., 2019] by using $D$ to distinguish between visited and novel states.
However, their approach trains $G$ less frequently so that $D$ does not lose
the ability to distinguish between fake and real data. This approach has two
weaknesses: (a) $G$ needs to train just good enough to incentivize $D$ to
improve itself, but not good enough so that GAN does not reach convergence,
and with the right hyperparameter setup, the task of keeping this balance is
hard to accomplish; and (b) $D$ is trained to separate real data from what $G$
generates, however, there is no guarantee on how $D$ will act on an unseen
instance, resulting in unreliable feedback. In our proposed method, the GAN is
trained to convergence so that $G$ is able to generate data similar to real
states, and an encoder $E$ is trained to map a newly observed state to the
latent noise space, to then be regenerated by $G$. The difference between the
observed state and the generated state is then fed as the intrinsic reward to
the learning agent. We chose to use GANs for this task because (a) with this
approach, learning the dynamics of the environment is not required, we are
only interested in learning the distribution of the observed states, and (b)
GANs are very widely studied and its use-cases have expanded to many areas. We
believe that GANs can be integrated into reinforcement learning and showcasing
a successful application will open the gates for the future studies.

We evaluate our proposed method on Montezuma’s Revenge, an Atari game that is
notoriously hard to explore due to rewards being very sparse and difficult to
reach from the initial position by random exploration [Bellemare et al.,
2016]. In addition to the sparse reward setting, we also evaluate our method
in a no-reward setting in the game of Super Mario Bros. [Kauten, 2018]. We
show by that using only the intrinsic reward, the agent is capable of
exploring the environment. We discuss how the method can be further improved
and invite readers to build upon the proposed method.

Figure 1: A general reinforcement learning framework with our proposed GAN-
based Intrinsic Reward Module (GIRM). At each time step $t$, agent observes a
state $s_{t}$ from the environment MDP $\mathcal{M}$, chooses an action
depending on its policy $\pi$, and receives an extrinsic reward $r^{e}_{t}$
from the environment and an intrinsic reward $r^{i}_{t}$ from GIRM. In GIRM,
the encoder $E$ maps $s_{t}$ to the input noise space of the generator $G$ and
outputs $E(s_{t})$. $G$ generates a synthetic state $G(E(s_{t}))$ and the
error measured between $s_{t}$ and $G(E(s_{t}))$ is then sent to the agent as
an intrinsic reward. Operation $-$ in the GIRM module is not necessarily
subtraction, but could be any function that computes the residual between
$s_{t}$ and $G(E(s_{t}))$. $\mathcal{L}_{D}$ is used for training the Encoder.

##  2 PRELIMINARIES

Generative Adversarial Networks. Proposed by [Goodfellow et al., 2014],
Generative Adversarial Networks (GAN) is a framework that consists of two
neural networks, called generator and discriminator, competing against each
other in order to train the generator to be able to generate synthetic data
similar to real data. Discriminator $D$ is optimized to detect if the input
sample is real or generated, and the generator $G$ tries to fool the
discriminator by generating data similar to the real data $\boldsymbol{x}$
from an input noise $\boldsymbol{z}$ sampled from a distribution
$p_{\boldsymbol{z}}$. $D$ outputs the probability of the input being real
data, and is originally optimized to maximize $\log
D(\boldsymbol{x})+\log(1-D(G(\boldsymbol{z})))$ while $G$ is optimized to
minimize $\log(1-D(G(\boldsymbol{z})))$. In an optimal training, $G$ is able
to learn the distribution of the real data and can sample new synthetic data
from the same distribution.

Reinforcement Learning. In reinforcement learning, environments are modeled by
a Markov Decision Process (MDP), defined as
$\mathcal{M}=(\mathcal{S},\mathcal{A},\mathcal{R},\mathcal{P},\rho_{0})$,
where $\mathcal{S}$ is the set of states, $\mathcal{A}$ the set of actions,
$\mathcal{R}$ the reward function, $\mathcal{P}$ the state transition
probability distribution and $\rho_{0}$ the distribution of the initial state.
Given a state $s_{t}$ in $t^{th}$ time step, the agent takes an action $a_{t}$
according to its policy $\pi(s_{t})$, receives a reward $r_{t}$ and observes
the next state $s_{t+1}$. The aim is to find a policy $\pi*$ that maximizes
the expected total discounted reward,

$\pi^{*}=\arg\max_{\pi}\mathbb{E}_{\pi(s_{t}),\mathcal{P}}\left[\sum_{t}\gamma^{t}r_{t}\right]$
(1)

where $\gamma\in[0,1)$ is the discount factor that determines the weight of
rewards in the distant future compared to present.

Exploration in Reinforcement Learning. One of the longstanding problems of
reinforcement learning is to explore the environment efficiently before agent
exploits a sub-optimal but positive reward it receives. The most common
approaches for exploration depend on diversifying action selection, meaning
that agent ideally performs a random action in a state it did not previously
observe, rather than sticking to a single action. These approaches do not
necessarily guide agent to unvisited states, but occasionally lets the agent
take a random action that might guide it to a better reward. However, if the
reward signals in an environment are sparse or nonexistent, the policy $\pi$’s
behaviour will be random at any state as the agent does not encounter a reward
signal to guide itself. In such problems, an efficient exploration method is
necessary to discover unvisited states in order to find the sparse rewards to
learn the $\pi^{*}$.

##  3 EXPLORATION GUIDED BY GAN-BASED INTRINSIC REWARD MODULE

Influenced by the anomaly detection framework of [Schlegl et al., 2019], we
propose a ”GAN-based Intrinsic Reward Module (GIRM)” in order to incentivize
the policy learning agent to explore unvisited states. To do so, at every
time-step, in addition to the extrinsic reward received from the environment
$r^{e}_{t}$, GIRM will also feed the agent with an intrinsic reward
$r^{i}_{t}$, which will be higher for the unexplored states. Policy of the
agent is then updated to maximize the total reward,
$r_{t}=r^{e}_{t}+r^{i}_{t}$. Providing an intrinsic reward is especially
important for the environments with sparse or no rewards, because in such
environments, the agent usually fails to find the states with rewards and it
needs reinforcement to find the set of actions that will maximize the total
reward received. With the intrinsic reward, the agent will now be reinforced
into exploring the environment to find the extrinsic rewards. Figure 1
illustrates the proposed GIRM-enhanced reinforcement learning framework.

The first goal of GIRM is to learn the distribution of the visited states. To
that end, we train a GAN with the visited states as the train data, using the
improved WGAN architecture [Gulrajani et al., 2017]. Since the generator $G$
is trained to minimize the divergence between $G$’s sample distribution and
the distribution of the training data, $G$ is trained to fit to the
distribution of the visited states, i.e. $G$ learns the mapping
$\boldsymbol{z}\rightarrow G(\boldsymbol{z})$ where $G(\boldsymbol{z})$ is a
synthetic state similar to the visited states.

After training of the GAN is complete, an encoder $E$ is trained to learn the
mapping $s_{t}\rightarrow\boldsymbol{z}$, i.e. $E$ maps the state $s_{t}$ to
the input noise distribution of $G$. The aim is to find the $\boldsymbol{z}$
that is mapped to a $G(\boldsymbol{z})$ which is the most similar synthetic
state in the distribution of $G$, to the input state $s_{t}$. To that aim,
first, we define an MSE loss to minimize the difference between the input
$s_{t}$ and the recreated image $G(\boldsymbol{z})=G(E(s_{t}))$:

$\min_{E}\mathcal{L}\left(s_{t}\right)=\frac{1}{n}\|s_{t}-G(E(s_{t}))\|^{2}$
(2)

where $n$ is the number of dimensions in the state space (if states are
images, n represent the number of pixels). As pointed in [Schlegl et al.,
2017] and [Schlegl et al., 2019], the discriminator $D$ is able to learn the
feature representations of the inputs in an intermediate layer, and in
addition to the loss in Eq. 2, minimizing the difference between the feature
encodings of the training data and the recreated data improves the training of
$E$. Therefore, we adapt the loss of feature encodings of $s_{t}$ and
$G(E(s_{t})$ as
$\mathcal{L}_{D}\left(s_{t}\right)=\frac{\lambda}{n_{d}}\|f(s_{t})-f(G(E(s_{t})))\|^{2}$
and finalize the loss function for $E$ as:

$\begin{split}\min_{E}\mathcal{L}\left(s_{t}\right)+&\mathcal{L}_{D}\left(s_{t}\right)=\frac{1}{n}\|s_{t}-G(E(s_{t}))\|^{2}+\\\
&\frac{\lambda}{n_{d}}\|f(s_{t})-f(G(E(s_{t})))\|^{2}\end{split}$ (3)

where $f$ is the output of an intermediate layer in $D$, $n_{d}$ number of the
dimensions in the feature representations, and $\lambda$ is a hyperparameter
scaling the feature representation loss. After $E$ is trained, as illustrated
in Fig. 1, for an observed state by the agent $s_{t}$, the intrinsic reward is
computed as:

$r^{i}_{t}=\frac{1}{n}\|s_{t}-G(E(s_{t}))\|^{2},$ (4)

which is the MSE between $s_{t}$ and $G(E(s_{t})$. If $s_{t}$ is a frequently
visited state, it will belong to the distribution learned by $G$, therefore it
can be recreated and $r^{i}_{t}$ will be low. On the contrary, if $s_{t}$ is
an unvisited state, the difference between $s_{t}$ and $G(E(s_{t})$ will be
significant and $r^{i}_{t}$ will be high, reinforcing the agent to explore
towards $s_{t}$. Notice that, we do not multiply $r^{i}_{t}$ with a constant
scalar to scale it. It is true that in different environments, the scale of
the intrinsic rewards will be different, however as the distribution of the
visited states change, so will the scale of intrinsic rewards. Therefore,
instead of a constant scalar, we calculate the exponentially weighted moving
average($EMA$) and variance($EMV$) of the rewards as:

$EMA=\begin{cases}r^{i}_{1},&\text{if}\ t=1\\\
\alpha*r^{i}_{t}+(1-\alpha)*EMA,&\text{otherwise}\end{cases}$ (5)

$EMV=\begin{cases}0,&\text{if}\ t=1\\\
\begin{split}\alpha*(r^{i}_{t}-EMA)^{2}+\\\
(1-\alpha)*EMV\end{split},&\text{otherwise}\end{cases}$ (6)

and then, standardize the intrinsic reward:

$r^{i}_{t}=\frac{r^{i}_{t}-EMA}{\sqrt{EMV}}.$ (7)

In this study, we used $\alpha=0.01$. The standardization ensures that the
distribution of the rewards will have the same mean and variance throughout
the training and in different environments. In Eq. 7, the intrinsic reward is
standardized to have a mean of 0 and a variance of 1, and in this study, we
used this equation for standardization, however the equation can be modified
to have different mean and variance if needed. With the standardization of
$r^{i}_{t}$, the optimization problem in Eq. 1 becomes:

$\pi^{*}=\arg\max_{\pi}\mathbb{E}_{\pi(s_{t}),\mathcal{P}}\left[\sum_{t}\gamma^{t}(r^{e}_{t}+r^{i}_{t})\right].$
(8)

Figure 2: A full view of the first level in the game Super Mario Bros. Player
starts at the left side of the level and only perceives the surroundings of
the character it is controlling, while the camera is always centered at the
character in the horizontal-axis. To complete the level, the player needs to
reach the castle at the far right of the level. With no reward given, a
reinforcement learning agent only depends on exploration to find the end of
the level.  Figure 3: First room in the game Montezuma’s Revenge. The player
starts the game in this room and needs to collect the key first, and then go
to one of the doors to escape from the room. Only rewards are received when a
key is grabbed or a door is unlocked. The player needs to complete a complex
set of actions to reach the key, as it needs to climb down two stairs, jump to
a rope, avoid an enemy, and then climb up a stair while avoiding death. The
camera is static, the player has the full view of the room and it only changes
when the player goes to another room.

GIRM is trained periodically during the policy learning. To do so, the states
observed by the agent are stored in a memory $M=s_{0},s_{1},...,s_{N}$ with a
pre-defined capacity $N$. As soon as $M$ reaches full capacity, we stop policy
learning of the agent, and train GIRM with the data stored in $M$ using
stochastic gradient descent. After training of the GIRM is finished, $M$’s
content is cleared and the policy learning, as well as storing observed states
to $M$, restarts. Every time $M$ reaches full capacity, the GIRM is trained
with the new data as the distribution of visited states keeps changing during
the policy learning. Since GIRM consists of only random networks before the
first time $M$ is full, GIRM does not provide an intrinsic reward until the
first training phase, and the agent only receives the extrinsic rewards from
the environment. Until the first training phase of GIRM is finished, we use
exploration by randomly selected actions. Moreover, the first time $M$ is
full, GIRM is trained for larger number of epochs to train it until
convergence. Afterwards, GIRM is fine-tuned with the newly observed data for a
lesser number of epochs.

##  4 EXPERIMENTS

Table 1: Comparison of agents in Super Mario Bros. in terms of furthest point they explored and percentage of the states that are further from certain point out of all of the states they visited in horizontal axis.  Method | # of Frames | Furthest Visited | visited $>$ 500 | visited $>$ 1000 | visited $>$ 1500
---|---|---|---|---|---
A2C | 32M | 1673 | 41.3% | 2.3% | 0.1%
A2C+GIRM | 8M | 3150 (End of level) | 60.3% | 21.5% | 4.1%

###  4.1 Experimental Setup

As the baseline reinforcement learning algorithm, we used Advantage Actor-
Critic (A2C), a synchronous version of A3C [Mnih et al., 2016] in the
experiments. The main difference between A2C and A3C is, while in A3C, there
are a number of workers with their own network weights asynchronously working
and updating a global network, in A2C, workers send transition synchronously,
and share one global network. In our experiments, we used sixteen workers
synchronously running their own environments. For both A2C and GIRM, observed
state visuals are converted to grayscale from RGB and resized to $84\times
84$. The actor-critic network has 3 convolutional layers, followed by a fully
connected layer. First convolutional layer has 32 filters of 8$\times$8 kernel
size with stride 4, second convolutional layer has 64 filters of 4$\times$4
kernel size with stride 2, the third convolutional layer has 64 filters of
kernel size 3$\times$3 with stride 1 and finally, the fully connected layer
has 512 hidden units. Each layer has Leaky ReLU as its activation function
with a negative slope of $0.01$. The output of the fully connected layer is
then sent to two separate fully connected layers, one of them selecting the
action(actor) and the other predicting the value of the state(critic).

As depicted in Figure 1, the GIRM consists of 3 networks: generator $G$,
discriminator $D$ and encoder $E$. The size of the input noise is 128 for $G$,
and it is created as a 2D input, with the size $1\times 1$ and 128 channels.
$G$ consists of 5 transposed convolutional layers, with 64 filters in the
first 4 layers and 1 filter in the last layer, each filter having a kernel
size of $4\times 4$. $D$ consists of 6 convolutional layers with 64 filters in
the first 5 layers and 1 filter in the last, with kernel sizes of 4, 5, 5, 3,
1, and 5, respectively. The output of the first 5 layers of $D$ is also used
as the intermediate feature representation for the training of $E$. Finally,
$E$ is formed with 5 convolutional layers with 64 filters in the first 4
layers and 128 filters in the last, which is the size of the input noise.
Kernel Sizes are 4, 5, 5, 3, and 5, respectively. All three networks use Batch
Normalization [Ioffe and Szegedy, 2015] at the end of each layer except the
final ones. Hidden layers in $D$ and $E$ are activated with Leaky ReLU with a
negative slope of $0.2$, and hidden layers of $G$ uses ReLU as the activation
function, except the final layer which uses tanh as its activation function.

For all the networks, we used ADAM optimizer [Kingma and Ba, 2014] to update
the weights. For training the actor-critic network, learning rate is
$2.5*10^{-4}$ and for the networks in GIRM module, learning rate is $10^{-4}$.
$\beta_{1}=0.9$ and $\beta_{2}=0.999$ for all the networks.

To evaluate our proposed module, we set up two environments, one of which has
sparse reward signals and the other has no reward signal other than the one in
the goal state. We evaluate our module by running an agent with and without
the module and compare the results. Later on, we compare our results with the
other studies in the field.

First of the environments is the game Super Mario Bros. [Kauten, 2018]. Fig. 2
shows the full layout of the first level, which is the level our agent is
trained in. The agent can only partially observe the environment, as the
states include only the surroundings of the character it’s controlling. The
initial position is at the far left side of the level and the goal position is
the flag next to the castle at the far right side. In this environment, we
disable all the extrinsic rewards other than the one given for reaching the
goal state. Without an extrinsic reward, the agent depends only on its
exploration strategy, and with random exploration, it is a significantly hard
task to go past the first few obstacles, let alone reach the goal state.

The second environment is the game Montezuma’s Revenge, which is notoriously
hard to solve for an AI agent due to its sparse rewards. Fig. 3 shows the room
the player starts in. In order to receive the first extrinsic reward signal,
the player needs to navigate to the key. However, the agent needs to select a
specific set of actions in order to reach the key, as a fall from any height
results in death, so the agent needs to navigate the character to jump to the
middle platform, climb down the stairs, jump to the rope and to the platform
on right, climb down the second stairs, avoid the enemy and finally climb up
the stairs. Producing an action set randomly to carry out all these tasks is
especially hard. Differing from Super Mario Bros, the observed environment
does not change with the movement of the agent and the background stays static
until the agent moves to a different room. This provides a different challenge
to the GIRM, as the generated image by the generator $G$ will have the same
background whether the state is visited or not, until a new room is explored,
and $r^{i}_{t}$ calculated in Eq. 4 will only have small differences between
states. Standardization in Eq. 7 is especially important in this type of
environments to make the $r^{i}_{t}$ computed for visited and unvisited states
have a meaningful difference.

###  4.2 Results and Discussion

Super Mario Bros. Table 1 compares the agents trained with A2C with and
without GIRM module, by the distance they covered in horizontal axis in the
first level of the game Super Mario Bros. With no reward signal received, the
agent only depends on its exploration strategy to find the goal state of the
environment. In the case of no GIRM module, a strategy to maximize the entropy
of the actions is used [Mnih et al., 2016]. Results show that when GIRM is
introduced, the agent can find the goal state, whereas without it, the agent
can only reach nearly half point of the level and it can only visit there
once.

In Mario, as shown in Fig. 2, in order to explore the environment, the agent
needs to go right consistently. When there is no extrinsic reward, exploration
depends only on the observation of new environmental elements and vertical
movement does not provide new information and is only useful for overcoming
obstacles. Since the intrinsic rewards from the GIRM are higher in the
unobserved states that are on the right side of the level, the agent
eventually needs to learn to go right in order to explore efficiently. As
shown in Table 1, the visited states by the agent with GIRM that are further
from half point of the level amounts to $4.1\%$ of all visited states. Through
the observed rewards from GIRM in the first part of the level, the agent
learns to go right as it receives higher rewards from the states on the right
side of the map and through this learnt policy, the agent manages to find the
end of the level without roaming around in the second half of the level. Even
though there is no extrinsic reward, through the rewards from the GIRM, our
agent learns to explore the environment by learning to move right until the
end of the episode, showing that it is capable of efficient exploration. This
is an important trait for the agent to have, as, through the usage of the
GIRM, we show that the agent can learn how to explore efficiently in the
specific environment setting it is in.

Figure 4: Mean scores during the training of A2C and A2C + GIRM in Montezuma’s
Revenge.

Montezuma’s Revenge. An exceptionally hard-to-solve environment, it is very
crucial to explore efficiently and find the rewards in Montezuma’s Revenge.
Our agent trained with the GIRM has shown capable of doing so, guided to
rewards and achieved better scores than the baseline A2C agent, as shown in
Fig. 4. Agent trained without the GIRM was capable of finding the reward for
grabbing key in the first room very few times, and in those cases, it could
not find its way out of the room to receive further rewards. Agent trained
with the GIRM has shown its capability to further explore the environment,
finding rewards in the other rooms as well. However, it should be noted that
an early convergence happens as the agent could not break out of the score of
3600. We observed that the agent found a 3000 reward for killing an enemy and
started to exploit that big reward rather than exploring. This shows that even
though our GIRM guides the agent into exploration, exploiting extrinsic
rewards when the difference between intrinsic and extrinsic rewards is high
could not be avoided. Results in Table 2 further shows that our method is
capable of exploring and matching the results of some of the works in the
literature but could not beat the performances of the state-of-the-art.

Table 2: Comparison of our results in Montezuma’s Revenge against DQN-GAEX [Hong et al., 2019], Go-explore [Ecoffet et al., 2021], NGU [Badia et al., 2020], RND [Burda et al., 2019] and DTSIL [Guo et al., 2019]. Scores are reported by the authors of the methods, except the baseline result from A2C and our method, GIRM. Bold indicates the best result.  Method | # of Frames | Mean Score
---|---|---
A2C | 20M | 0
A2C+GIRM | 20M | 3,594
DQN-GAEX | 200M | 420
Go-explore |  12B | 43,791
NGU | 35B | 10,400
RND | 16B | 10,070
DTSIL | 3.2B | 22,616

Another factor affecting the performance of the GIRM is the static background
observation in the rooms, resulting in small differences between the observed
state and the regenerated state by the generator $G$(even if the observed
state is novel) as long as the agent stays in the same room, because the only
difference between state observations is the position of the character. We
addressed this problem by introducing exponentially weighted moving average
($EMA$) and variance ($EMV$) in Section 3 to make even very small differences
into meaningful intrinsic rewards. However, when the agent manages to find new
rooms in the level, the difference for calculating intrinsic reward grows
bigger, which also increases $EMA$ and $EMV$. This results in small
differences being not significant enough anymore, hindering the exploration in
an already observed room. Nevertheless, as shown by the results in both Super
Mario Bros. and Montezuma’s Revenge, we can conclude that our proposed GIRM is
capable of incentivizing the agent into exploring, heavily outperforming the
random exploration approaches that are most commonly used in the literature,
however, we also identified a few aforementioned weaknesses as well.

Sample Efficiency of GIRM. As explained, GIRM is trained when the memory $M$
that stores observed states is full and the first training phase of GIRM
occurs for a larger number of epochs in order to train it until convergence.
This leads to optimized networks in the GIRM even after the first training
phase and GIRM becomes capable of computing accurate intrinsic rewards, i.e.
rewards that are higher for unobserved states. Because of this, to start
leading the agent into exploring the environment efficiently, GIRM needs only
the amount of data $M$ initially stored. Our reported results in Table 1 and
Table 2 uses only 8 million and 20 million of frames for each respective
environment. Especially in Montezuma’s Revenge, as also shown in Table 2,
recent studies have benefited from billions of frames even for efficient
exploration. Our method proves to be sample efficient, as it successfully
provides the necessary intrinsic reinforcement for the agent with
significantly less amount of data.

##  5 CONCLUSION AND FUTURE WORK

Common exploration strategies work well when reward signals are dense, however
an additional incentive is needed in environments with sparse or no rewards.
In this work, we proposed the ”GAN-based Intrinsic Reward Module (GIRM)” to
compute an intrinsic reward for a reinforcement learning agent, in order to
incentivize the agent to explore the environment it is in. GIRM is trained so
that the intrinsic reward is higher for the novel or less-frequently-visited
states to guide the agent into exploring the environment. The memory mechanism
that we employ in the training of GIRM provides an adaptation to the changing
distribution in the observed environment. Since GIRM is an extension module,
it can be applied to any reinforcement learning algorithm. In this work, we
used Asynchronous Actor-Critic (A2C) as the baseline algorithm, comparing
agents trained with and without GIRM.

We show GIRM’s capability of exploration in a sparse reward and a no reward
setting. We used Super Mario Bros. [Kauten, 2018] for the no reward setting
and show that the agent trained with GIRM provides the necessary intrinsic
reward so that the agent explores and completes the level and outperforms the
agent without GIRM. Our agent does so by learning the pattern of going right
in order to find unexplored states. For the sparse reward setting, we
evaluated our agent in Montezuma’s Revenge, an atari game that’s been recently
used for benchmarking in reinforcement learning, due to its difficulty. While
the agent trained without GIRM is not capable of escaping the initial room,
with the addition of GIRM, our agent explores multiple rooms throughout the
environment, achieving a mean score of 3954. On the one hand, we show that
GIRM provides a more efficient exploration strategy, but on the other hand, we
observe that our agent converges early, beginning to exploit the high rewards
from the environment.

We also identify another weakness of GIRM through Montezuma’s Revenge:
standardizing rewards through the usage of $EMA$ and $EMV$ turns small
differences between the observed novel state and regenerated state into
meaningful intrinsic rewards, however, as the agent begins to explore new
rooms, the already high difference between regenerated and novel states gets
higher, which also increases the distribution $EMA$ and $EMV$ represents,
therefore GIRM loses the capability of assigning meaningful rewards to novel
states in the frequently visited rooms. In the future, we would like to
address this problem. A potential solution could be leaving out the very high
or very low intrinsic reward when updating $EMA$ and $EMV$, treating them as
an anomaly. Furthermore, a more efficient reward scaling method could be
investigated.

Another future direction is to make use of GANs to train a model to learn the
dynamics of the environment, instead of the distribution of observations.
Since the dynamics throughout the environment do not change drastically, a
model that learns the dynamics might have a better generalization property
throughout the environment. This idea is not a direct improvement to GIRM, but
instead, we recommend an idea to utilize GANs in the efficient exploration
problem in reinforcement learning with a different approach.

## ACKNOWLEDGEMENTS

This work is supported by Istanbul Technical University BAP Grant NO:
MOA-2019-42321.

## REFERENCES

  * Badia et al., 2020 Badia, A. P., Sprechmann, P., Vitvitskyi, A., Guo, Z. D., Piot, B., Kapturowski, S., Tieleman, O., Arjovsky, M., Pritzel, A., Bolt, A., and Blundell, C. (2020).  Never give up: Learning directed exploration strategies.  CoRR, abs/2002.06038.
  * Bellemare et al., 2016 Bellemare, M. G., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., and Munos, R. (2016).  Unifying count-based exploration and intrinsic motivation.  In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16, page 1479–1487, Red Hook, NY, USA. Curran Associates Inc.
  * Burda et al., 2019 Burda, Y., Edwards, H., Storkey, A., and Klimov, O. (2019).  Exploration by random network distillation.  In 7th International Conference on Learning Representations (ICLR 2019), pages 1–17.  Seventh International Conference on Learning Representations, ICLR 2019 ; Conference date: 06-05-2019 Through 09-05-2019.
  * Choshen et al., 2018 Choshen, L., Fox, L., and Loewenstein, Y. (2018).  Dora the explorer: Directed outreaching reinforcement action-selection.  ArXiv, abs/1804.04012.
  * Ecoffet et al., 2021 Ecoffet, A., Huizinga, J., Lehman, J., Stanley, K. O., and Clune, J. (2021).  First return, then explore.  Nature, 590(7847):580–586.
  * Goodfellow et al., 2014 Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. (2014).  Generative adversarial nets.  In Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N., and Weinberger, K. Q., editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc.
  * Gulrajani et al., 2017 Gulrajani, I., Ahmed, F., Arjovsky, M., Dumoulin, V., and Courville, A. C. (2017).  Improved training of wasserstein gans.  In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc.
  * Guo et al., 2019 Guo, Y., Choi, J., Moczulski, M., Bengio, S., Norouzi, M., and Lee, H. (2019).  Efficient exploration with self-imitation learning via trajectory-conditioned policy.  ArXiv, abs/1907.10247.
  * Hong et al., 2019 Hong, W., Zhu, M., Liu, M., Zhang, W., Zhou, M., Yu, Y., and Sun, P. (2019).  Generative adversarial exploration for reinforcement learning.  In Proceedings of the First International Conference on Distributed Artificial Intelligence, DAI ’19, New York, NY, USA. Association for Computing Machinery.
  * Houthooft et al., 2016 Houthooft, R., Chen, X., Duan, Y., Schulman, J., De Turck, F., and Abbeel, P. (2016).  Vime: Variational information maximizing exploration.
  * Ioffe and Szegedy, 2015 Ioffe, S. and Szegedy, C. (2015).  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  CoRR, abs/1502.03167.
  * Kauten, 2018 Kauten, C. (2018).  Super Mario Bros for OpenAI Gym.  GitHub.
  * Kingma and Ba, 2014 Kingma, D. and Ba, J. (2014).  Adam: A method for stochastic optimization.  International Conference on Learning Representations.
  * Lillicrap et al., 2016 Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. (2016).  Continuous control with deep reinforcement learning.  In Bengio, Y. and LeCun, Y., editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings.
  * Mnih et al., 2016 Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., and Kavukcuoglu, K. (2016).  Asynchronous methods for deep reinforcement learning.  In Balcan, M. F. and Weinberger, K. Q., editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1928–1937, New York, New York, USA. PMLR.
  * Mnih et al., 2013 Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M. A. (2013).  Playing atari with deep reinforcement learning.  CoRR, abs/1312.5602.
  * Oh et al., 2018 Oh, J., Guo, Y., Singh, S., and Lee, H. (2018).  Self-imitation learning.  In Dy, J. and Krause, A., editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3878–3887. PMLR.
  * Ostrovski et al., 2017 Ostrovski, G., Bellemare, M. G., van den Oord, A., and Munos, R. (2017).  Count-based exploration with neural density models.  In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, page 2721–2730. JMLR.org.
  * Pathak et al., 2017 Pathak, D., Agrawal, P., Efros, A. A., and Darrell, T. (2017).  Curiosity-driven exploration by self-supervised prediction.  In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, page 2778–2787. JMLR.org.
  * Pathak et al., 2019 Pathak, D., Gandhi, D., and Gupta, A. (2019).  Self-supervised exploration via disagreement.  In ICML.
  * Schlegl et al., 2017 Schlegl, T., Seeböck, P., Waldstein, S., Schmidt-Erfurth, U., and Langs, G. (2017).  Unsupervised anomaly detection with generative adversarial networks to guide marker discovery.  pages 146–157.
  * Schlegl et al., 2019 Schlegl, T., Seeböck, P., Waldstein, S. M., Langs, G., and Schmidt-Erfurth, U. (2019).  f-anogan: Fast unsupervised anomaly detection with generative adversarial networks.  Medical Image Analysis, 54:30–44.
  * Schmidhuber, 1991 Schmidhuber, J. (1991).  Curious model-building control systems.  In [Proceedings] 1991 IEEE International Joint Conference on Neural Networks, pages 1458–1463 vol.2.
  * Stadie et al., 2015 Stadie, B. C., Levine, S., and Abbeel, P. (2015).  Incentivizing exploration in reinforcement learning with deep predictive models.  CoRR, abs/1507.00814.
  * Sutton and Barto, 2018 Sutton, R. S. and Barto, A. G. (2018).  Reinforcement Learning: An Introduction.  The MIT Press, second edition.
  * Tang et al., 2017 Tang, H., Houthooft, R., Foote, D., Stooke, A., Chen, X., Duan, Y., Schulman, J., De Turck, F., and Abbeel, P. (2017).  #exploration: A study of count-based exploration for deep reinforcement learning.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 2750–2759, Red Hook, NY, USA. Curran Associates Inc.
  * Zhao and Tresp, 2019 Zhao, R. and Tresp, V. (2019).  Curiosity-driven experience prioritization via density estimation.  CoRR, abs/1902.08039.


# Alternating Direction Based Sequential Boolean Quadratic Programming Method
for Transmit Antenna Selection

Shijie Zhu† Xu Du† †The first two authors contributed equally. SZ and XD are
with the School of Information Science and Technology, ShanghaiTech
University, Shanghai, China. SZ is also with Innovation Academy for
Microsatellites, Chinese Academy of Sciences, Shanghai, China. XD is also with
Shanghai Institute of Microsystem and Information Technology, Chinese Academy
of Sciences. SZ and XD are also with the University of Chinese Academy of
Sciences, China while XD is with the Center for Intelligent Networking and
Communications, the National Key Laboratory of Science and Technology on
Communications, University of Electronic Science and Technology of China.
{zhushj<EMAIL_ADDRESS>
###### Abstract

The wireless mobile communication system is updated and iterated on the whole
almost every decade. It is now in the development period of the application
scenarios of the fifth generation mobile communication system (5G).
Unfortunately, 5G relies on plenty of small base stations with a large number
of antennas that consume a lot of energy. In this paper, a novel Boolean
variable quadratic programming algorithm is designed for the antenna selection
optimization problem to reduce power consumption. Experiments show that the
proposed algorithm achieves high complementarity satisfaction accuracy with
only a few steps.

_Keywords:_ 5G, Boolean variables, Power consumption, Complementarity
satisfaction

##  I INTRODUCTION

With the explosion of wireless devices and services, challenges like climbing
demand of communication capability cannot be solved easily. Fortunately, there
are various promising technologies for 5G such as massive multiple-input
multiple-output (mMIMO), turbo code etc [1].

Among these, mMIMO is considered a leading technology since multiple antenna
technology provides not only larger communication capacity with spatial
multiplexing but reliability with spatial diversity [2], therefore mMIMO with
typically tens of antennas can address the aforementioned challenge [1].
However, the power consumption corresponding to the rising numbers of antennas
at the base station is becoming one of the research hotpots of economical
concerns [3]. The consumption of electric power on base stations with massive
antennas which are always active contributes to over 70% of the electricity
bill for the cellular operators [1]. Therefore, the research direction of
_green communication_ has been well studied for balancing the communication
quality and power consumption and become one of the core of 5G . Green
communication contains many techniques like new architecture such as
intelligent reflecting surface (IRS) [4] or resource allocation techniques,
namely hybrid beamforming and antenna selection [5], different variations of
efficiency optimization objective has been well studied by [6]. A _Group
Lasso_ formulation has been used for turning off selected transmit source by
[7], in details, the green communication framework with cloud radio access
network can be formulated into a joint subset selection and power minimization
beamforming problem. Another article happens to coincide with an approach to
select the active antennas with radio-frequency (RF) chains by using
relaxation of Boolean variables, exhaustive search, interior point method [8].
However, the methods proposed in the above literatures suffer a slow
convergence rate and low accuracy for Boolean variables in the selection
problem.

Historically, Boolean optimization has been explored in various fields. An
early theory literature was proposed by [9], a Boolean linear programming
exercise has been well studied [10]. Moreover, [11] solves a Boolean quadratic
programming problem with $\\{-1,1\\}$ variables in a semidefinite programming
fashion. Theoretically, pruning and sparsity optimization techniques can be
also considered as Boolean variable optimization problems such as [12] and
[13]. The scaling and approximation methods of Boolean variables are also
often mentioned [13]. Nowadays, a new type of problem named _Linear
Complementary Quadratic Programming_ (LCQP) [14] appears which aims at solving
optimal control problems with complementary dynamic constraints, the idea is
to linearize a corresponding penalization term without destroying the
structure of _QP_. More related application can be found [15] and [14].
However, this algorithm can only solve the problem with objective function of
QP and complementarity constraints, which makes the application scenarios of
this method limited.

In the present paper, we propose an _Alternating Direction Based Sequential
Boolean QP_ (AD-SBQP) algorithm to solve general mix-integer nonlinear problem
in an SQP fashion. In some literatures, AD is also named as alternating
optimization (AO). The idea is to split Boolean and continuous variables in
different steps without destroying the core structure of LCQP. The proposed
algorithm shows better performance on economic objective, complementarity
satisfaction and computation time with limit iteration while the comparison
with state-of-art methods has been shown in a given case study.

The rest of this paper is organized as follows: Section II reviews the basics
concepts of wireless communications. Sections III proposed the AD-SBQP
algorithm. And the numerical result is shown in Section IV.

##  II Basics of Wireless Communication Systems

In this section, we reviewed the basics of wireless communication that
includes additive Gaussian white noise wireless channel model, maximum
transmission ratio as well as antenna selection problem. Assuming perfect
channel state information at transmit side (CSIT) is acquired, the system
model can be idealized without propagation error during the process of signal
transfer.

###  II-A Wireless Channel

As shown in Figure 1 multi-user MIMO (MU-MIMO) is a system equipped with
multiple transmission and receiving antennas for broadcast information
utilizing multipath propagation, while the operating bandwidth is defined as
$B$ Hz.

Figure 1: Multi-user MIMO communication network.

The wireless channel of a MIMO system with $N$ transmit (TX) and $K$ receive
(RX) antennas can be represented by a deterministic complex matrix

$\begin{split}H&=[h_{(:,1)},h_{(:,2)},\cdots,h_{(:,j)},\cdots,h_{(:,K)}]\\\
&=\begin{bmatrix}h_{11}&\cdots&h_{1K}\\\ \vdots&\vdots&\vdots\\\
h_{N1}&\cdots&h_{NK}\end{bmatrix}\in\mathbb{C}^{N\times K},\end{split}$ (1)

here channel gain $h_{ij}$ connects $i$th transmit antenna with $j$th user,
$h_{(:,j)}$ indicates the vector including all $h_{ij}$ of $j$th user [2].

The relationship between the transmit side and receive side can be depicted as
[2]:

$r=H^{\top}t+n,$

here $r\in\mathbb{C}^{K}$, $t\in\mathbb{C}^{N}$ and
$n$$\sim$${\mathcal{CN}(0,N_{0}\mathbf{I}_{K})}$ denote the received signal,
transmitted signal and additive white Gaussian noise respectively. $N_{0}$
denotes the noise power density while $\mathbf{I}_{K}\in\mathbb{R}^{K}$ is an
identity matrix.

The power allocation matrix

$\begin{split}P&=[p_{(:,1)},p_{(:,2)},\cdots,p_{(:,j)},\cdots,p_{(:,K)}]\\\
&=\begin{bmatrix}p_{11}&\cdots&p_{1K}\\\ \vdots&\vdots&\vdots\\\
p_{N1}&\cdots&p_{NK}\end{bmatrix}\in\mathbb{R}^{N\times K}\end{split}$ (2)

denotes the power amount associated with the channel gain. For instance,
$p_{ij}$ represents the power allocated from $i$th transmit antenna to $j$th
receive antenna, i.e. $p_{ij}$ correlates with the channel gain $h_{ij}$.

###### Remark 1

To avoid ambiguity, we consider the multi-user multiple-input single-output
(MU-MISO) as the special case of MU-MIMO when each user terminal only carries
one antenna.

As a kind of linear precoding schemes111 _Dirty paper coding_ (DPC) is an
optimal nonlinear precoding scheme which has high complexity especially with
huge amounts of antennas while linear precoding can achieve 98% performance of
DPC [16]. , the concept of maximum ratio transmission (MRT) was introduced in
[17] to maximize the signal-to-noise ratio (SNR) at each receiver (i.e. $j$th
user) in multi-antenna communication, in details,

$\mathrm{SNR}_{j}=\frac{\sum_{i=1}^{N}p_{ij}|h_{(:,j)}^{H}v_{j}|^{2}}{N_{0}B}$
(3)

with given beamforming directions [18]

$v_{j}=\frac{h_{(:,j)}}{\|h_{(:,j)}\|},\forall j.$

Here $(\cdot)^{H}$ denotes Hermitian transpose.

###  II-B Shannon Capacity

In this paper _Shannon Capacity_ relies on both MRT and transmit antenna
selection (TAS). With (3), _Shannon Capacity_ [2] can be formulated as

$\displaystyle R(P)$
$\displaystyle=\sum_{j=1}^{K}B\log_{2}(1+\mathrm{SNR}_{j})$ (4)
$\displaystyle=\sum_{j=1}^{K}B\log_{2}\left(1+\frac{\sum_{i=1}^{N}p_{ij}\frac{|h_{(:,j)}^{H}h_{(:,j)}|^{2}}{\|h_{(:,j)}\|^{2}}}{N_{0}B}\right)$
$\displaystyle=\sum_{j=1}^{K}B\log_{2}\left(1+\frac{\sum_{i=1}^{N}p_{ij}\|h_{(:,j)}\|^{2}}{N_{0}B}\right)$

which depicts the ideal communication rate that the wireless communication
system could get. TAS is a signal processing method to save the cost of RF
chains connected with transmit antennas equipped at base station (BS), when
the set of antennas is selected with the principle of maximizing the downlink
capacity [19].

As shown in Figure 2, the switch vector $x\in\\{0,1\\}^{N}$ controls the on-
off state of each RF chain with the corresponding transmit antenna [20].

Figure 2: Multi-user MISO wireless communication system with transmit antenna
selection.

By considering the switch variable $x$, (4) can be reformulated into

$\displaystyle\tilde{R}(P,x)$
$\displaystyle=\sum_{j=1}^{K}B\log_{2}\left(1+\frac{\sum_{i=1}^{N}p_{ij}x_{i}\|h_{(:,j)}\odot
x\|^{2}}{N_{0}B}\right),$ (5)

here Hadamard product $\odot$ indicates the element wise multiplication.

###  II-C Economic Sum Rate

Inspired by [7] and [21] whose bi-linear structure with Boolean variable is
nonconvex, here we propose a simplified _Economic Sum Rate_ problem with the
following linear summation objective function

$\displaystyle\min_{P,x}\;\;$ $\displaystyle
f(P,x)=\sum_{i=1}^{N}(\sum_{j=1}^{K}p_{ij}x_{i}+p^{RF}x_{i})$ (6a)
$\displaystyle\quad\mathrm{s.t.}\;\;$ $\displaystyle\tilde{R}(P,x)\geq R^{th}$
(6b) $\displaystyle x_{i}\in\\{0,1\\},\qquad i=1,2,\dots,N$ (6c)
$\displaystyle\sum_{j=1}^{K}p_{ij}\leq p^{th}$ (6d) $\displaystyle 0\leq
p_{ij},\qquad\quad\dbinom{i=1,2,\dots,N}{j=1,2,\dots,K}$ (6e)

Here, (6a) can be viewed as a cost function while the sum rate inequality
constraint (6b) is certainly satisfied with a given threshold sum rate
$R^{th}$. A constant $p^{RF}$ stands for the standby power of RF chain, and a
constant $p^{th}$ indicates the upper bound of power allocated at each
transmit antenna.

##  III Alternating Direction Based Sequential Boolean Quadratic Programming

In this section, after basic theory of BQP is reviewed, an extension of which
named _Alternating Direction Based Sequential BQP_ is proposed for solving
general nonlinear programming problem with linear complementarity constraints
by splitting normal and Boolean variables into different steps.

###  III-A Basics of BQP

Consider a tuple
$(\mathcal{D},\mathcal{Y},\mathcal{Z})\in\mathbb{R}^{n_{d}}\times\mathbb{R}^{n_{C}\times
n_{d}}\times\mathbb{R}^{n_{C}\times n_{d}}$, linear complementarity [14] can
be defined as

$\displaystyle Yd$ $\displaystyle\geq 0$ (7a) $\displaystyle Zd$
$\displaystyle\geq 0$ (7b) $\displaystyle d^{\top}Y^{\top}Zd$
$\displaystyle=0,$ (7c)

$(d,Y,Z)\in(\mathcal{D},\mathcal{Y},\mathcal{Z})$ collects the decision
variable and linear transformation matrix respectively. Boolean constraint
(6c) in _Economic Sum Rate_ (II-C) can be somehow treated as a special case of
(7) and can be expressed as

$\displaystyle x$ $\displaystyle\geq 0$ (8a) $\displaystyle\bm{1}-x$
$\displaystyle\geq 0$ (8b) $\displaystyle x^{\top}(\bm{1}-x)$
$\displaystyle=0$ (8c)

where $\bm{1}$ represents a vector with all entries being one.

Based on above definition, _Boolean Quadratic Programming_ (BQP) can be
depicted as the following equation by introducing Boolean constraint (8)

$\displaystyle BQP:\min_{x}\;\;$
$\displaystyle\frac{1}{2}x^{\top}Qx+g^{\top}x$ (9a)
$\displaystyle\mathrm{s.t.}\;\;$ $\displaystyle Ax-u\leq 0$ (9b)
$\displaystyle 0\leq x\perp(\bm{1}-x)\geq 0,$ (9c)

here $0\prec Q\in\mathbb{R}^{n_{x}\times n_{x}}$, $g\in\mathbb{R}^{n_{x}}$,
$A\in\mathbb{R}^{n_{A}\times n_{x}}$ and $u\in\mathbb{R}^{n_{A}}$ collect the
corresponding parameters. Here we introduce a penalty function [22] relate to
(8c),

$\varphi(x)=x^{\top}(\bm{1}-x).$ (10)

Therefore, (9) can be reformulated as penalty BQP (pBQP)

$\begin{split}pBQP:\min_{x}\;\;&\frac{1}{2}x^{\top}Qx+g^{\top}x+\rho\cdot\varphi(x)\\\
\mathrm{s.t.}\;\;&\eqref{eq:leftcompcons},\eqref{eq:rightcompcons},\eqref{lcqp:lpcons}\end{split}$
(11)

with a penalty parameter $\rho\in\mathbb{R}$.

The following BQP algorithm inherits the key idea of [14] by using linear
approximation of the penalty function in Step 2.

Algorithm 1 BQP method

Input: coefficients $Q,g,A,u$, a termination tolerance $\epsilon>0$, an
initial factor $\rho>0$ and update rate $\beta>1$.
Repeat:

  1. 1.

_Globally Search:_ solve QP without complementarity constraints:

$\begin{split}\hat{x}=\arg\min_{x}\;\;&\frac{1}{2}x^{\top}Qx+g^{\top}x\\\
\quad\mathrm{s.t.}\;\;&\eqref{eq:leftcompcons},\eqref{eq:rightcompcons},\eqref{lcqp:lpcons}\end{split}$
(12)

  2. 2.

_Penalty Function Approximate:_

$\begin{split}\varphi(x)&\approx\varphi(\hat{x})+(x-\hat{x})^{\top}\nabla\varphi(\hat{x})\\\
&=(\varphi(\hat{x})-\hat{x}^{\top}\nabla\varphi(\hat{x}))+x^{\top}\nabla\varphi(\hat{x})\end{split}$

  3. 3.

_Locally Search:_ Minimize the reformulated penalty QP222Complementarity
$\varphi(x)$ [14] cannot be utilized due to the nonlinearity and nonconvexity
properties, which can be replaced by the first order Taylor approximation
$(\bm{1}-2\hat{x})^{\top}x$ that keeps the structure of QP.:

$\displaystyle\tilde{x}=\arg\min_{x}$
$\displaystyle\frac{1}{2}x^{\top}Qx+(g+\rho\nabla\varphi(\hat{x}))^{\top}x$
$\displaystyle\quad\mathrm{s.t.}$
$\displaystyle\eqref{eq:leftcompcons},\eqref{eq:rightcompcons},\eqref{lcqp:lpcons}$

  4. 4.

_Line Search and Termination Criterion 333$\alpha$ can be obtained by any kind
of line search method [23]. :_

$\alpha=StepLength(\hat{x},\tilde{x},\rho);$

$\hat{x}\approx\hat{x}+\alpha(\tilde{x}-\hat{x})$

check if $\|\varphi(\hat{x})\|\leq\epsilon$, if not, go to step 5.

  5. 5.

_Penalty Parameter Update:_

$\rho=\beta\cdot\rho$ and return step 2

Output: $x^{*}\leftarrow\hat{x}$.

###  III-B Theory of AD-SBQP

For a generic nonlinear programming problem with Boolean constraints

$\displaystyle\min_{x}\;\;$ $\displaystyle F(x)$ (13a)
$\displaystyle\mathrm{s.t.}\;\;$ $\displaystyle c(x)\leq 0\;|\lambda$ (13b)
$\displaystyle 0\leq x\perp(\bm{1}-x)\geq 0$ (13c)

with smooth nonlinear maps $F:\mathbb{R}^{n}\rightarrow\mathbb{R},\
c:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$. The Lagrangian function of which
is constructed as $\mathcal{L}(x,\lambda)=F(x)+\lambda^{\top}c(x)$ with a
multiplier $\lambda\in\mathbb{R}^{m}$ of the corresponding dimension [23].
Assume $\bar{x}$ and $\bar{\lambda}$ are obtained from the previous nonlinear
programming (NLP) iteration, a second-order Taylor expansion of the Lagrangian
function $\tilde{F}(x)$ is shown as below with
$\nabla^{2}\mathcal{L}(\bar{x},\bar{\lambda})\succ 0$,

$\displaystyle\tilde{F}(x)=$
$\displaystyle\frac{1}{2}(x-\bar{x})^{\top}\nabla^{2}\mathcal{L}(\bar{x},\bar{\lambda})(x-\bar{x})$
(14) $\displaystyle+\nabla F(\bar{x})^{\top}(x-\bar{x})+F(\bar{x}).$

Inspired from the framework of Sequential QP (SQP), (15) can be treated as a
single step of _Sequential Boolean QP_ (SBQP) which connects with (9) and
Algorithm 1.

$\displaystyle\min_{x}\;\;$ $\displaystyle\tilde{F}(x)$ (15a)
$\displaystyle\mathrm{s.t.}\;\;$ $\displaystyle\nabla
c(\bar{x})(x-\bar{x})+c(\bar{x})\leq 0$ (15b) $\displaystyle 0\leq
x\perp(\bm{1}-x)\geq 0.$ (15c)

The above discussion summarizes the solution of generic nonlinear Boolean
optimization problem. When there are additional continuous variables in the
optimization problem, the local optimal solution can be obtained by optimizing
different kinds of variables in alternate directions without destroying the
SBQP structure. With this spirit of Algorithm 1, Algorithm 2 and Figure 3 show
an new version of BQP named _Alternating Direction Based SBQP method_ (AD-
SBQP).

Algorithm 2 Alternating Direction Based SBQP method

Input: initial guess of $\bar{x}\in\mathbb{R}^{N}$,
$\bar{P}\in\mathbb{R}^{N\times K}$ a termination tolerance $\epsilon>0$, an
initial factor $\rho>0$ and update rate $\beta>1$.
Repeat:

  1. 1.

_Optimal Power Allocation (AD1):_ Solve (6) with constant $\bar{x}$ by any NLP
solver Output: $P^{*}(\bar{{x}})$, $\bar{\lambda}$ .

  2. 2.

Sequential BQP (AD2): set

$\left\\{\begin{aligned} F(x)&=f(P^{*}(\bar{x}),x)\\\
c(x)&=\tilde{R}(P^{*}(\bar{x}),x)\end{aligned}\right.$

solve (13) by SBQP (15) and Algorithm 1.

Output: $x^{*}$

  3. 3.

Termination Criterion:
Check if

$\|\begin{bmatrix}P^{*}(\bar{x})|x^{*}\end{bmatrix}-\begin{bmatrix}\bar{P}|\bar{x}\end{bmatrix}\|\leq\epsilon$
(16)

if not go back to step 1) and set $\bar{P}=P^{*}(\bar{x})$, $\bar{x}=x^{*}$.

Output: $P^{*},x^{*}$.

####  III-B1 AD1

This stage, which is derived from _water-filling_ [2], aims to reduce the
power consumption of the aforementioned MIMO system with fixed state $x$. The
Quality of Service (QoS) requirement (6b), the lower bound of $p_{ij}$ (6e),
and the upper bound of power for each antenna (6d) are all considered as
physical constraints. Moreover, the constraint (6d) as the upper bound denotes
the power of each antenna, that ensures the optimized sum power will not
exceed the preset upper bound.

####  III-B2 AD2

After AD1, the Hessian $\nabla^{2}\mathcal{L}(\bar{x},\bar{\lambda})$ and
gradient $\nabla F(\bar{x})$ are evaluated jointly with
$(P^{*}(\bar{x}),\bar{\lambda})$. Assume the local minimizer of (15) is in the
neighborhood of the global minimizer (12), In order to search a specific local
minimizer, the objective function (15a) is replaced by

$\displaystyle\hat{F}(x)=$
$\displaystyle\tilde{F}(x)+\rho\nabla\varphi(\bar{x})^{\top}(x-\bar{x})$ (17)
$\displaystyle=$
$\displaystyle\frac{1}{2}(x-\bar{x})^{\top}\nabla^{2}\mathcal{L}(\bar{x},\bar{\lambda})(x-\bar{x})$
$\displaystyle+(\nabla
F(\bar{x})+\rho\nabla\varphi(\bar{x}))^{\top}(x-\bar{x})+F(\bar{x})$

which inherits the spirit of Step 2 in Algorithm 1. Moreover, another key part
of AD2 is the complementarity tolerance check.

Figure 3: Flowchart of AD-SBQP.

##  IV Numerical Experiments

In this section, we present the numerical performance of Algorithm 2 drawing
upon a MU-MISO TAS communication network shown in Figure 2. We illustrate the
numerical comparison among 4 different configurations of wireless network.

###  IV-A Data and Environment

In a two-dimensional Cartesian coordinate system, a wireless communication
network is shown as Figure 4: a) a BS at the origin point equipped with a
uniform linear array of $N=64$ antennas, b) $K=64$ users are distributed
randomly in a circular cell centered at $(100,0)$ with a radius of 20 meters.
$\xi(\delta_{j})=T_{0}\delta_{j}^{-\eta}$ denotes the distance-dependent path
loss with parameters c) the distances $\delta_{j}$ between $j$th user and the
BS , d) the path loss at reference distance per meter $T_{0}=-30$ dB and e)
the path loss exponent $\eta=3.67$ [24]. We denote
$h_{(:,j)}=\sqrt{\xi(\delta_{j})}\tilde{h}_{(:,j)}$ where $\tilde{h}_{(:,j)}$
denotes $j$th origin channel gain subjects to Rayleigh fading due to the rich
environment of scattering. In order to simplify the experiment, the total
power is normalized to 1 while the noise $N_{0}B$ at each user is also
normalized to 1. The $p^{RF}$ is set as $0.0078$ while the threshold sum rate
$R^{th}$ is set as $82.71$.

Figure 4: A two-dimensional Cartesian coordinate system: red solid point in
origin denotes the BS while blue rectangles in red ring denotes users.

The implementation of SBQP relies on qpOASES [25] while other parts depend on
IPOPT [26]. Both subsolvers are utilized through the Casadi [27] interface
with MATLAB 2021b.

###  IV-B Implementation and Numerical Comparison

Note that the AD framework consists of two essential parts: AD1 can be solved
by any NLP solver, while AD2 is a nonconvex and nonsmooth problem. In AD2, we
set $\rho=1$ as initial penalty parameter and its update factor $\beta=2$.
Moreover, we select Armijo rule as line search method. We initialize the
switch vector $\bar{x}$ as $\frac{1}{2}\cdot$$\bm{1}$ to ensure the fairness
between the lower and upper bound. To assess the numerical effect of the
proposed AD-SBQP algorithm, we compare Algorithm 2 with other two variants of
penalty BQP: one method, named by NSPen, solves (13) by adding (10) into (13a)
to substitute for (13c), the other penalty method, SPen, solves (15) with the
same penalty function (10). Therefore, we call the other two methods in same
AD framework as AD-NSPen and AD-SPen temporarily.

TABLE I: Numerical Comparison Methods | AD-SBQP | AD-SPen | AD-NSPen
---|---|---|---
objective | 0.5269 | 0.5933 | 0.6093
complementarity | 2.9816e-19 | 6.4000e-07 | 6.4000e-07
time (seconds) | 281.4971 | 519.0302 | 1.3190e+03

Table I shows the comparison among objective function, complementarity
satisfaction and operation time. It was apparent that the objective function
obtained by AD-SBQP is the lowest. Moreover, one can see that the precision of
AD-SBQP in complementartiy is higher than other algorithms while its
computation time is much less.

Figure 5 shows the objective convergence comparison by using the above three
methods, all of which converge in four steps. Note that AD-NSPen and AD-SPen
solve optimization problem with (9c) directly and trap into different local
minimizer while Step 1 of Algorithm 1 avoid it by optimizing without
$\varphi(x)$ term.

Figure 5: The blue dash-dotted and black dotted line represent the objective
functions with AD-NSPen and AD-SPen respectively. The red solid line denotes
the numerical result optimized by Algorithm 2.

###### Remark 2

When the complementarity tolerance is set as $10^{-10}$, even the penalty
parameter $\rho$ increase to a very large value as $2^{32}$ of AD2, both AD-
SPen and AD-NSPen will not well satisfy the complementarity tolerance.

Figure 6: Convergence of primal variables $(P,x)$ and dual $\lambda$.

Figure 6 shows the convergence of primal $(P,x)$ and dual variables $\lambda$.
One can see that all of the variables converge to optimal solution with only
four steps, thus the proposed method can be potentially treated as a real time
algorithm.

Furthermore, the objective convergence of $8\times 8,16\times 16,32\times 32$
antenna configuration are similar to Figure 5 and Figure 6 with less operation
time.

Figure 7 shows the convergence of objective function and complementarity
satisfaction at AD2 step in the first iteration of Algorithm 2, and
complementarity is well satisfied in two AD2 iterations.

Figure 7: Objective function $\tilde{F}(x^{*})$ and complementarity
$|\varphi(x^{*})|$ obtained by AD2 of Algorithm 2.

##  V CONCLUSION

This work proposed an algorithm to solve Mixed Boolean Nonlinear Programming
in an antenna selection scenario. Our simulation of a $64\times 64$ antenna
MU-MIMO network shows that, without destroying the BQP structure, AD-SBQP
internally uses the linear approximation term of penalty function constructed
from Boolean constraints, which results in extremely high complementary
satisfaction accuracy compared with other algorithms. Moreover, the power
consumption can be reduced to less than 55% in several alternate direction
steps.

## References

  * [1] Cheng-Xiang Wang, Fourat Haider, Xiqi Gao, Xiao-Hu You, Yang Yang, Dongfeng Yuan, Hadi M Aggoune, Harald Haas, Simon Fletcher, and Erol Hepsaydir.  Cellular architecture and key technologies for 5g wireless communication networks.  IEEE communications magazine, 52(2):122–130, 2014.
  * [2] David Tse and Pramod Viswanath.  Fundamentals of wireless communication.  Cambridge university press, 2005.
  * [3] Emil Björnson, Luca Sanguinetti, Jakob Hoydis, and Mérouane Debbah.  Optimal design of energy-efficient multi-user mimo systems: Is massive mimo the answer?  IEEE Transactions on wireless communications, 14(6):3059–3075, 2015\.
  * [4] Qingqing Wu and Rui Zhang.  Intelligent reflecting surface enhanced wireless network via joint active and passive beamforming.  IEEE Transactions on Wireless Communications, 18(11):5394–5409, 2019.
  * [5] Jiayi Zhang, Emil Björnson, Michail Matthaiou, Derrick Wing Kwan Ng, Hong Yang, and David J Love.  Prospective multiple antenna technologies for beyond 5g.  IEEE Journal on Selected Areas in Communications, 38(8):1637–1660, 2020.
  * [6] Emil Björnson, Jakob Hoydis, and Luca Sanguinetti.  Massive mimo networks: Spectral, energy, and hardware efficiency.
  * [7] Yuanming Shi, Jun Zhang, and Khaled B Letaief.  Group sparse beamforming for green cloud-ran.  IEEE Transactions on Wireless Communications, 13(5):2809–2823, 2014\.
  * [8] Saad Mahboob, Rukhsana Ruby, and Victor CM Leung.  Transmit antenna selection for downlink transmission in a massively distributed antenna system using convex optimization.  In 2012 Seventh International Conference on Broadband, Wireless Computing, Communication and Applications, pages 228–233. IEEE, 2012.
  * [9] Robert Connelly.  On the algorithms of szwarc and federowicz for linear programming problems with boolean variables.  Technical report, CARNEGIE INST OF TECH PITTSBURGH PA GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATION, 1963.
  * [10] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe.  Convex optimization.  Cambridge university press, 2004.
  * [11] Zhi-Quan Luo, Tsung-Hui Chang, D Palomar, and Y Eldar.  Sdp relaxation of homogeneous quadratic optimization: approximation.  Convex Optimization in Signal Processing and Communications, page 117, 2010.
  * [12] Lida Kouhalvandi, Osman Ceylan, and Serdar Ozoguz.  Automated top-down pruning optimization approach in rf power amplifier designs.  Analog Integrated Circuits and Signal Processing, 106(3):525–534, 2021.
  * [13] Baojian Zhou, Feng Chen, and Yiming Ying.  Stochastic iterative hard thresholding for graph-structured sparsity optimization.  In International Conference on Machine Learning, pages 7563–7573. PMLR, 2019.
  * [14] Jonas Hall, Armin Nurkanović, Florian Messerer, and Moritz Diehl.  A sequential convex programming approach to solving quadratic programs and optimal control problems with linear complementarity constraints.  IEEE Control Systems Letters, 2021.
  * [15] Armin Nurkanović, Tommaso Sartor, Sebastian Albrecht, and Moritz Diehl.  A Time-Freezing Approach for Numerical Optimal Control of Nonsmooth Differential Equations with State Jumps.  IEEE Control Systems Letters, 5(2):439–444, 2021.
  * [16] Xiang Gao, Ove Edfors, Fredrik Rusek, and Fredrik Tufvesson.  Linear pre-coding performance in measured very-large mimo channels.  In 2011 IEEE Vehicular Technology Conference (VTC Fall), pages 1–5. IEEE, 2011.
  * [17] Titus KY Lo.  Maximum ratio transmission.  In 1999 IEEE international conference on communications (Cat. No. 99CH36311), volume 2, pages 1310–1314. IEEE, 1999.
  * [18] Emil Björnson and Eduard Jorswieck.  Optimal resource allocation in coordinated multi-cell systems.  Now Publishers Inc, 2013.
  * [19] Shahab Sanayei and Aria Nosratinia.  Antenna selection in mimo systems.  IEEE Communications magazine, 42(10):68–73, 2004.
  * [20] Xiang Gao, Ove Edfors, Fredrik Tufvesson, and Erik G Larsson.  Massive mimo in real propagation environments: Do all antennas contribute equally?  IEEE Transactions on Communications, 63(11):3917–3928, 2015.
  * [21] Xunan Li, Chong Li, and Ye Jin.  Dynamic resource allocation for transmit power minimization in ofdm-based noma systems.  IEEE Communications Letters, 20(12):2558–2561, 2016.
  * [22] Daniel Ralph* and Stephen J Wright.  Some properties of regularization and penalization schemes for mpecs.  Optimization Methods and Software, 19(5):527–556, 2004.
  * [23] Jorge Nocedal and Stephen Wright.  Numerical optimization.  Springer Science & Business Media, 2006.
  * [24] Evolved Universal Terrestrial Radio Access.  Further advancements for e-utra physical layer aspects (release 9), 3gpp.  TS, 36:V9, 2010.
  * [25] H.J. Ferreau, C. Kirches, A. Potschka, H.G. Bock, and M. Diehl.  qpOASES: A parametric active-set algorithm for quadratic programming.  Mathematical Programming Computation, 6(4):327–363, 2014.
  * [26] Andreas Wächter and Lorenz T Biegler.  On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming.  Mathematical programming, 106(1):25–57, 2006.
  * [27] Joel A E Andersson, Joris Gillis, Greg Horn, James B Rawlings, and Moritz Diehl.  CasADi – A software framework for nonlinear optimization and optimal control.  Mathematical Programming Computation, 11(1):1–36, 2019.