# Deep Reinforcement Learning Powered IRS-Assisted Downlink NOMA

Muhammad Shehab, Bekir S. Ciftler, Tamer Khattab, Mohamed M. Abdallah, Daniele
Trinchero M. Shehab and T. Khattab are with the Department of Electrical
Engineering, Qatar University, Doha, Qatar. B. Ciftler and M. Abdallah are
with the Division of Information and Computing Technology, College of Science
and Engineering, Hamad Bin Khalifa University, Doha, Qatar. D. Trinchero is
with Dipartimento di Elettronica, Politecnico di Torino, Torino, Italy.

###### Abstract

In this work, we examine an intelligent reflecting surface (IRS) assisted
downlink non-orthogonal multiple access (NOMA) scenario with the aim of
maximizing the sum rate of users. The optimization problem at the IRS is quite
complicated, and non-convex, since it requires the tuning of the phase shift
reflection matrix. Driven by the rising deployment of deep reinforcement
learning (DRL) techniques that are capable of coping with solving non-convex
optimization problems, we employ DRL to predict and optimally tune the IRS
phase shift matrices. Simulation results reveal that IRS assisted NOMA based
on our utilized DRL scheme achieves high sum rate compared to OMA based one,
and as the transmit power increases, the capability of serving more users
increases. Furthermore, results show that imperfect successive interference
cancellation (SIC) has a deleterious impact on the data rate of users
performing SIC. As the imperfection increases by ten times, the rate decreases
by more than 10%.

###### Index Terms:

Intelligent Reflecting Surfaces (IRS), Non-Orthogonal Multiple Access (NOMA),
Deep Reinforcement learning (DRL), 5G and beyond, 6G, Phase shift design.

##  I Introduction

With the increasing progressions in the wireless communications, future
communication systems are favorable to support higher data rates, higher
spectral efficiencies, reduced latencies, wider coverage areas and massive
number of connections, among other features.

As wireless technologies have grown exponentially over the last few decades,
wireless systems are promising to meet the demand for the enormous number of
connections. The next generation networks will be an end-to-end ecosystem to
enable a fully connected and sustainable community. The main purpose of these
networks is to provide seamless and ubiquitous communications for users with a
higher throughput, low latency, low energy consumption and support the
escalation in mobile data consumption for hundreds of thousands of
connections. As 5G networks are being deployed, technologies for 6G networks
are being researched and examined to attain more reliable and faster
communication systems [1].

Among these technologies, are the intelligent reflecting surfaces (IRS)s,
which regulate the wireless environment to boost the energy and spectral
efficiencies. IRS consists of a huge number of passive elements or IRS units,
each unit can passively reflect the incident electromagnetic wave signal and
modify it in terms of phase, frequency, amplitude or polarization. Most of the
research papers in the literature are considering passive IRS where only a
phase shift to the incident signal is applied. Thus, the IRS will not consume
any transmit power. Consequently, the IRS optimization problem is focused on
the phase-shift matrix [2]. Further, the IRS can aid the transmissions among
the transmitters and receivers, especially where there is no line of sight
(LoS) between the transmitting antenna and the receiving antenna, or if the
direct link suffers from shadowing and deep fading rendering the quality of
the channel for direct communications unreliable [3]. Compared to decode and
forward and amplify and forward, IRS demands less energy and power consumption
because of its passive features. Hence, IRS is anticipated to be a promising
solution for future 5G / 6G communication systems [4]. IRS can be related to
technologies such as massive or large multiple input multiple output (M-MIMO)
antenna networks since it utilizes large number of antennas to increase the
energy and spectrum efficiency. Thus, IRS is considered a potential component
in 6G networks, which is analogous to M-MIMO potential in 5G networks.
Nonetheless, the difference is that the IRS regulates the propagation in the
wireless environment.

Non-orthogonal multiple access (NOMA) is a vital component in 5G wireless
communication systems and beyond because of the high spectrum efficiency it
provides in addition to its support for massive connectivity. In the previous
cellular systems, many multiple access technologies were adopted such as the
time division multiple access (TDMA), frequency division multiple access
(FDMA), spatial division multiple access (SDMA) and orthogonal frequency
division multiple access (OFDMA). Based on their design, these technologies
are considered as orthogonal multiple access (OMA) techniques, since the
wireless resources are allocated to multiple users orthogonally. The users are
separated in the chosen access domain whether it is in frequency, time, or
space. If orthogonality is violated, the users will suffer from interference
and quality of communications links will degrade leading to loss of
information and/or inefficient resources utilization. Nonetheless, OMA schemes
cannot satisfy the requirements for future communication systems which causes
the need for NOMA [5]. NOMA achieves high sum rate capacity as compared to the
traditional orthogonal multiple access (OMA) techniques. The reason is that it
enables multiple users to transmit simultaneously in the same set of shared
resources. This results in an interference, but NOMA utilizes a method called
successive interference cancellation (SIC) to eliminate the resulting
interference.

###  I-A Related Work

Many research studies related to IRS in 5G and 6G communication networks are
being conducted. Some of these studies inspected IRS for OMA schemes such as
in [6] \- [10], but these studies did not include NOMA in their scenarios.
However, several recent research studies started investigating IRS for NOMA
communication. The authors in [11] examined an uplink scenario for IRS NOMA
and they maximized the sum rate for all users taking into consideration the
power constraint for each user. They solved the non-convex problem using semi-
definite relaxation which is a mathematical method and provides near-optimal
solution. In [12], the authors proposed a simple design for the IRS assisted
NOMA system. First they utilized spatial division multiple access on the base
station (BS) side for orthogonal beams generation. This is done by making use
of the spatial directions of the channels of the nearby users. Then the
authors employed IRS aided NOMA to serve the additional users on the cell
edge. They demonstrated the performance of the IRS-NOMA system by providing
analytical results. The authors in [13] inspected secure communication
transmission in IRS assisted NOMA system for a practical eavesdropper scenario
having imperfect channel state information. They proposed a joint IRS phase
shift and transmit beamforming scheme to ensure secure transmission via IRS.
Moreover, they used the alternating optimization algorithm which is a
mathematical method to find out stationary point solutions. Further, in [14]
IRS assisted downlink NOMA system was considered with the aim of enhancing the
performance of the rate and maximizing the signal to interference plus noise
ratio (SINR). The authors achieved this by jointly optimizing the phase shift
at the IRS and the transmit beamforming at the BS. They used efficient
mathematical method based on semi-definite relaxation and block coordinated
decent techniques. mmWave technology was included in the IRS NOMA scenario in
[15], where the authors inspected the downlink scenario of IRS mmWave NOMA,
and the formulated problem included joint optimization of the passive and
active beamforming as well as power allocation with the aim of enhancing the
performance of the system. To solve the problem, the authors used a
mathematical method based on an iterative algorithm utilizing successive
convex approximation and alternating optimization.

Nonetheless, the above studies [11] \- [15] assumed that the channels between
the IRS and users are known. Such assumption contradicts the practical case,
where IRSs are passive elements incapable of estimating channels. In the case
where part of the channels are unknown, the use of machine learning techniques
can add value to the problem.

###  I-B Contributions

In our research work, we address the aforementioned gap in surveyed literature
by leveraging reinforcement learning (RL); in particular, deep reinforcement
learning (DRL), to optimize the sum rate of a NOMA downlink system utilizing
IRS under the assumption of unknown channel states information between the IRS
and users. In particular, we exploit Deep Deterministic Policy Gradient (DDPG)
due to its suitability for our scenario because the problem is non-convex, the
objective function is non-convex and the unit modulus constraints are
fundamentally non-convex. Therefore, it is an NP-hard problem [8], [16]. The
major challenge presents in the constant modulus constraint of the phase shift
since the IRS can reflect the signal without amplifying it. Hence, it is not
easy to obtain an optimal solution in closed form. The use of DDPG is very
efficient when coping with intractable problems, it will remove the need for
gathering a large dataset for training. DDPG method is anticipated to provide
a solid and robust performance.

Our contributions in this work can be summarized as follows:

  * •

First, we formulate the IRS NOMA downlink phase shift optimization problem
with the objective of maximizing the sum-rate for NOMA users taking into
consideration that the instantaneous channel states information between the
IRS and users are unknown.

  * •

Second, we incorporate imperfect interference cancellation in practical NOMA
within our system model formulation.

  * •

Third, DDPG based solution is proposed for predicting the best phase shift
matrix in which the IRS learns the best way for reflecting the incident
signals by modifying the phase.

  * •

Fourth, numerical results reveal the effectiveness of the DDPG algorithm,
since the sum rate value for the DDPG based IRS assisted NOMA system
outperforms OMA based systems with minimum training overhead.

###  I-C Paper organization

The rest of the paper is structured as follows. Section II outlines the system
and channel model. Section III explains the DDPG-based phase control for IRS.
Section IV presents the numerical results, and Section V concludes the paper.

##  II System Model

We consider the downlink of an IRS assisted NOMA system with $K$ users as
shown in Fig. 1. Without loss of generality, the users are ordered according
to their distance from the IRS such that user $1$ is the farthest user from
the IRS and user $k$ is the nearest user to the IRS. Consequently, the users
can be considered as ordered based on the expected value of their channel
gains assuming
$|\mathbf{h}_{r,1}|^{2}<|\mathbf{h}_{r,2}|^{2}<\ldots<|\mathbf{h}_{r,k}|^{2}$.
All users as well as the BS are assumed to have a single antenna each. It is
assumed that there is no direct line of sight (LOS) link between the users and
the BS. Thus, the communication between the BS and users is performed through
the IRS which is deployed with $M=M_{x}M_{y}$ reflecting elements, where
$M_{x}$ and $M_{y}$ represent the number of passive elements in the IRS in
every row and column, respectively.

Figure 1: IRS Assisted Downlink NOMA

The transmitted signal at the BS is

$\displaystyle x=\sum_{k=1}^{K}\sqrt{P_{k}}s_{k},$ (1)

where $s_{k}$ represents the signal for user $k$ with unit power (i.e.,
$\mathbb{E}[|s_{k}|^{2}]=1$, $k\in\\{1,...,K\\}$, where $\mathbb{E}[.]$
denotes the expectation). The power allocated to each user is
$P_{k}=\beta_{k}P$, where
$\boldsymbol{\beta}=[\beta_{1},\beta_{2},...,\beta_{k}]$ is the vector of
coefficients of the users’ power allocated such that
$\beta_{1}+\beta_{2}+...+\beta_{k}=1$ and $P$ is the BS total transmit power.
The power allocated for users is fixed and it satisfies the relationship:
$P_{1}>P_{2}>...>P_{K}$. When allocating power to users, we will take into
consideration the following conditions $P_{1}>P_{2}+P_{3}+...+P_{K}$,
$P_{2}>P_{3}+P_{4}+...+P_{K}$, and so on.

The received signal for user k can be written as:

$\displaystyle y_{k}$
$\displaystyle=\mathbf{h}_{r,k}^{H}\mathbf{\Phi}\mathbf{h}_{t}x+n,$ (2)
$\displaystyle y_{k}$
$\displaystyle=\mathbf{h}_{r,k}^{H}\mathbf{\Phi}\mathbf{h}_{t}\sum_{k=1}^{K}\sqrt{P_{k}}s_{k}+n,$

where $\mathbf{h_{t}}\in\mathbb{C}^{M\times 1}$ is the channel between the BS
and the IRS, and $\mathbf{h}_{r,k}\in\mathbb{C}^{M\times 1}$ is the channel
between the IRS and users. Both channels follow the Rician fading model:

$\displaystyle\mathbf{h_{t}}=\sqrt{\frac{K_{1}}{K_{1}+1}}\mathbf{\bar{h}t}+\sqrt{\frac{1}{K_{1}+1}}\mathbf{\tilde{h}t},$
(3)

$\displaystyle\mathbf{h_{r,k}}=\sqrt{\frac{K_{2}}{K_{2}+1}}\mathbf{\bar{h}_{r,k}}+\sqrt{\frac{1}{K_{2}+1}}\mathbf{\tilde{h}_{r,k}},$
(4)

where $K_{1}$ is the rician factor of $\mathbf{h_{t}}$,
$\mathbf{\bar{h}t}\in{C}^{M\times 1}$ and $\mathbf{\tilde{h}t}\in{C}^{M\times
1}$ are the LoS component and non-LoS (NLoS) component, respectively.
Similarly, $K_{2}$ is the rician factor of $\mathbf{h_{r,k}}$,
$\mathbf{\bar{h}_{r,k}}\in{C}^{M\times 1}$ and
$\mathbf{\tilde{h}_{r,k}}\in{C}^{M\times 1}$ are the LoS component and non-LoS
(NLoS) component, respectively. The phase shift reflection matrix is
represented by
$\large\mathbf{\Phi}=\text{diag}(e^{j\theta_{1}},e^{j\theta_{2}},...,e^{j\theta_{M}})$,
and satisfies the constant modulus constraint
$|\phi_{i}|^{2}=|e^{j\theta_{i}}|^{2}=1$, $\forall i\in\\{1,2,...,M\\}$,
because the IRS reflects the signal without amplifying it, where
$\text{diag}(.)$ denotes a diagonal matrix. Further, the phase shift of the
$i^{th}$ passive reflecting element is denoted by $\theta_{i}$, where the
value of $\theta_{i}$ is between $0$ and $2\pi$, and
$n\sim\mathcal{C}\mathcal{N}(0,\sigma^{2})$ represents the additive white
Gaussian noise (AWGN).

Hence, the received SINR at user $k$ can be represented by the following
equation:

$\displaystyle\large\gamma_{k}=\bigg{(}\frac{|\mathbf{h}_{r,k}^{H}\mathbf{\Phi}\mathbf{h}_{t}|^{2}P_{k}}{\sum_{i=k+1}^{K}|\mathbf{h}_{r,k}^{H}\mathbf{\Phi}\mathbf{h}_{t}|^{2}P_{i}+\sigma^{2}}\Bigg{)},$
(5)

when $k=K$, the term
$\large\sum_{i=k+1}^{K}|\mathbf{h}_{r,k}^{H}\mathbf{\Phi}\mathbf{h}_{t}|^{2}P_{i}=0$.

Furthermore, the data rate of user $k$ is represented by:

$\displaystyle\large R_{k}=\log_{2}(1+\gamma_{k}).$ (6)

Our objective in this study is to maximize the sum-rate of all users where:

$\displaystyle\large
R_{sum}=\sum_{k=1}^{K}\log_{2}\left(1+\large\gamma_{k}\right).$ (7)

Therefore, the formulated problem at the IRS is to obtain the phase shift
reflection matrix $\mathbf{\Phi}$ that maximizes $R_{sum}$ for users.

$\displaystyle\large\max_{\Phi}\sum_{k=1}^{K}$
$\displaystyle\log_{2}\left(1+\large\gamma_{k}\right),$ (8) $\displaystyle
s.t.\leavevmode\nobreak\ $ $\displaystyle|\mathbf{\phi}_{i}|^{2}=1,\forall
i\in\\{1,2,...,M\\},$
$\displaystyle\large{\beta_{1}+\beta_{2}+...+\beta_{k}=1},$

The above equation (8) is valid for perfect successive interference
cancellation (SIC) which is the ideal case, where the interference from the
far users is assumed to be perfectly eliminated at the near users receiver. In
this case near users have perfect knowledge of the far users’ data signal.
Nonetheless, in the case of imperfect SIC, the interference of the far users
is not perfectly removed at the near users receiver. In this case, the data
signal of the far user is not perfectly known at the near user due to
distortion caused by fading and AWGN which is more realistic practically.
Thus, the received SINR in (5) at user $k$ can be rewritten as:

$\displaystyle\small\tilde{\gamma}_{k}=\frac{|\mathbf{h}_{r,k}^{H}\mathbf{\Phi}\mathbf{h}_{t}|^{2}P_{k}}{\large\epsilon\sum_{j=1}^{k-1}|\mathbf{h}_{r,k}^{H}\mathbf{\Phi}\mathbf{h}_{t}|^{2}P_{j}+\sum_{i=k+1}^{K}|\mathbf{h}_{r,k}^{H}\mathbf{\Phi}\mathbf{h}_{t}|^{2}P_{i}+\sigma^{2}},$
(9)

when $k$ = 1, the term
$\large\sum_{i=1}^{k-1}|\mathbf{h}_{r,k}^{H}\mathbf{\Phi}\mathbf{h}_{t}|^{2}P_{j}=0$.
The term epsilon ($\large\epsilon$) represents the fraction of the residual
interference leftover due to imperfect SIC.

Accordingly, the optimization problem in (8) becomes

$\displaystyle\large\max_{\Phi}\sum_{k=1}^{K}$
$\displaystyle\log_{2}\left(1+\large\tilde{\gamma}_{k}\right),$ (10)
$\displaystyle s.t.\leavevmode\nobreak\ $
$\displaystyle|\mathbf{\phi}_{i}|^{2}=1,\forall i\in\\{1,2,...,M\\},$
$\displaystyle\large{\beta_{1}+\beta_{2}+...+\beta_{k}=1},$

###  II-A Upperbound on Performance

To measure the performance of the DDPG algorithm and to verify that our sum-
rate values approach the upperbound, an exhaustive search method is used to
search for the optimum phase shift matrix that results in the maximum sum-rate
as shown in Algorithm 1. Further, to avoid the huge complexity of the
exhaustive search scheme, we will consider a limited number of IRS reflecting
elements as a case proof that our DDPG algorithm can track the upperbound. For
every IRS element we will consider the phases between 0 and $2\pi$ with a step
size of 16, this will give us $16^{M}$ combinations of phase shift matrices.
Then we will calculate the sum-rates accordingly for $K$ users.

Algorithm 1 Exhaustive Search for the Phase Shift Matrix

1:Initialize M = 4, $\Delta\Phi=\frac{2\pi}{16}$,

2:for $\phi_{1}=0:\frac{2\pi}{16}:2\pi;$ do

3: for $\phi_{2}=0:\frac{2\pi}{16}:2\pi;$ do

4: for $\phi_{2}=0:\frac{2\pi}{16}:2\pi;$ do

5: for $\phi_{3}=0:\frac{2\pi}{16}:2\pi;$ do

6: Calculate and store $R_{sum}(\phi_{1},\phi_{2},\phi_{3},\phi_{4})$

7: end for

8: end for

9: end for

10:end for

11:Find
$\Phi^{*}=\operatorname*{argmax}_{\phi_{1},\phi_{2},\phi_{3},\phi_{4}}R_{sum}$

###  II-B OMA Baseline Scheme

The signal model for OMA is assumed such that the resources (frequency / time)
are divided equally between the $K$ users. This enables OMA users to receive
the signal with free interference, whereas the merit of NOMA is the
simultaneous transmission and the interference can be controlled. However, to
serve K OMA users, FDMA / TDMA requires $K$ time slots. The first user will
use the first frequency/time slot, the second user will use the second
frequency/time slot, and user $K$ will use the $K^{th}$ frequency/time slot
accordingly.

The transmitted signal by the BS is given by:

$\displaystyle x^{OMA}_{k}=\sqrt{P}s_{k},$ (11)

The received signal at the user side can be expressed as:

$\displaystyle
y^{OMA}_{k}=\sqrt{P}s_{k}\mathbf{h}_{r,k}^{H}\mathbf{\Phi}\mathbf{h}_{t}+n,$
(12)

Hence, the received SNR at user k can be represented as:

$\displaystyle\gamma_{k}=\bigg{(}\frac{|\mathbf{h}_{r,k}^{H}\mathbf{\Phi}\mathbf{h}_{t}|^{2}P}{\sigma^{2}}\Bigg{)},$
(13)

Further, data rate of user k is represented by:

$\displaystyle R^{OMA}_{k}=\frac{1}{K}log_{2}(1+\gamma^{OMA}_{k}),$ (14)

Therefore, the sum-rate of OMA can be expressed as:

$\displaystyle R^{OMA}_{sum}=\sum_{k=1}^{K}R^{OMA}_{k},$ (15) $\displaystyle
R^{OMA}_{sum}=\frac{1}{K}\sum_{k=1}^{K}\log_{2}\Bigg{(}1+\frac{|\mathbf{h}_{r,k}^{H}\mathbf{\Phi}\mathbf{h}_{t}|^{2}P}{\sigma^{2}}\Bigg{)}.$
(16)

##  III Proposed DRL-Based Phase Control for IRS

###  III-A Overview on DRL method:

Reinforcement Learning (RL) method is a field of machine learning that allows
the agent in an interactive environment to learn by trial and error relying on
a feedback from its own experiences. The model in Fig. 2 demonstrates the
basic concept of the RL. Further, the fundamental factors that characterize
the RL problem are the agent, environment, state, reward, policy, and value.
The environment is the physical surrounding where the agent operates, the
state is the agent’s current status, the reward is the feedback the agent
experience from the environment, the policy is the process of mapping the
state of the agent to actions, and the value is the agent’s future reward that
it receives when taking action in a specific state. The agent at time $t$ gets
state $s^{(t)}$ from the environment and selects action $a^{(t)}$ based on
policy $\pi$. After selecting the action the state changes from $s^{(t)}$ to
$s^{(t+1)}$ and generate reward $r^{(t)}$. The objective of RL is to maximize
the total reward, the reward is the performance measure of a specific action
during the current state. RL models the interaction between the agent and the
environment as Markov’s decision process (MDP). Many RL algorithms use dynamic
programming methods, but the prime difference between RL algorithms and
dynamic programming is that RL algorithms don’t assume the awareness of a
specific MDP’s mathematical model. Further, RL algorithms are aimed for large
MDPs in which specific procedures become impracticable [17].

Figure 2: DRL Model

Q-learning (QL) is a model-free RL method since it does not require a model,
it obtains the best action under the current state, where "Q" denotes the
quality. Further, it is an off-policy algorithm since QL learns actions that
are outside the current policy so it may take actions that are random and
therefore the policy is not needed here. When the agent interacts with the
environment and needs to update the action-state pairs in the Q-table, it has
two choices, either to explore or exploit. Exploration is to explore the
environment in order to obtain information and knowledge about it, in this
case the agent acts randomly. Whereas exploitation is to exploit the available
"already known" information about the environment so as to maximize the
reward. Precisely, QL selects the optimal policy in order to maximize the
total reward.

The trade-off between exploration and exploitation is balanced by using a
specific parameter $\zeta$ which can be set based on how often we want to
exploit or explore. Moreover, QL is based on the concept of a Q-function,
which is a function of states and actions. The Q-function $Q^{\pi}(s,a)$
measures the expected discounted sum of rewards or the return achieved from
selecting action $a$ in a state $s$ based on policy $\pi$. It evaluates how
good a particular action is, for a given state. The optimal Q-value
$Q^{*}(s,a)$ is defined as the maximum return achieved from a given state $s$
and action $a$ while obeying the optimal policy. In order to update the
Q-value for any action we use the Bellman equation. It provides us the best
reward and the optimal policy to achieve this reward. It means that the
maximum value of the return from the action and state is equal to the
expectation of the current maximum possible reward plus the maximum possible
long-term reward achieved from the next state s’ discounted by
$\gamma\in[0,1]$ which is the discount factor, and the equation is expressed
as:

$\displaystyle
Q^{*}(s,a)=\mathbb{E}[r(s,a)+\gamma\max_{a^{\prime}}Q^{*}(s^{\prime},a^{\prime})],$
(17)

where $\mathbb{E}[.]$ denotes the expectation. The updates will occur after
each action and it will end when the episode finishes. In order to converge
and learn optimal values, the agent needs to learn and explore many episodes.
Furthermore, there are three important steps in the update, the first step is
that the agent will take action for each state and receive a reward. The
second step is that the agent will either select the action by checking the
highest value in the Q-table or by random $\zeta$. The third step is to update
the Q-values employing the following formula:

$\displaystyle
Q^{new}(s,a)=(1-\alpha)Q(s,a)+\alpha[r(s,a)+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})],$
(18)

The step size is adjusted using the learning rate $\alpha$ which measures the
acceptance of the new value compared to the old one [17].

Figure 3: Q-Learning vs Deep Q-Learning

Deep Q-Learning (DQL) uses neural network that approximates the Q-function.
Fig. 3 shows a comparison between QL and DQL, instead of calculating Q-values
immediately for each action and state via iterations, we will utilize a
function approximator for estimating Q-values for each possible action. To
perform this we need to employ neural networks (NN). The NN accepts states as
input from the environment and generates the estimated Q-values for every
action the agent can select. Furthermore, in many problems in DQL it is not
practical to represent the Q-function based on $s$ and $a$ only, the reason is
that we will train the neural network (NN) with parameters $\theta$ to
evaluate the Q-values such that $Q(s,a,\theta)\approx Q^{*}(s,a)$.

$\displaystyle
Q_{\pi}(s,a;\theta)=\mathbb{E_{\pi}}[R^{(t)}_{s^{(t)}=s,a^{(t)}=a}],$ (19)

where $R^{(t)}=\sum_{t=0}^{+\infty}\gamma^{t}r^{(t)}$ is the cumulative
expected reward. The aim of the DQN is to maximize the value of the Q-function
in (19) by DNN training. The optimal Q-value is obtained from the Bellman
equation. At this stage, we can calculate the loss by comparing the Q-value
for a given state-action pair to the target value which is the right hand side
of the Bellman equation expression which gives us the below expressions:

$\displaystyle\text{Loss = }Q^{*}(s,a;\theta)-Q(s,a;\theta),$ (20)

$\displaystyle\mathbb{E}[r(s,a;\theta)+\gamma\max_{a^{\prime}}Q^{*}(s^{\prime},a^{\prime};\theta)]-\mathbb{E}[\sum_{t=0}^{+\infty}\gamma^{t}r_{t}],$
(21)

Next the NN will update its weight values in the policy network based on the
gradient descent and back propagation algorithms. We will keep repeating this
process time after time for many episodes until we sufficiently minimize the
loss [17].

Policy gradient (PG) is on-policy, model-free RL method, used for continuous
action space. The PG agent is a RL agent which is policy-based, it aims
directly to maximize the expected reward by obtaining a parametrized policy
that generates a trajectory $\tau$, where the trajectory represents the
states, actions and rewards i.e. $s_{0},a_{0},r_{1},s_{1},a_{1},r_{2},...$. In
other words, we need to find out the parameters $\theta$ that maximizes $J$,
where $\theta$ represents the weights of the neural networks.

$\displaystyle J(\theta)=\mathbb{E_{\pi}}[r(\tau)],$ (22)

where $r(\tau)$ denotes the total reward for a specified trajectory $\tau$. A
well known approach in machine learning to solve the maximization problem is
the gradient descent or ascent to step through the parameters. By using the
gradient ascent we get the following equation:

$\displaystyle\theta_{t+1}=\theta_{t}+\alpha\nabla J(\theta_{t}),$ (23)

where $\alpha$ represents the learning rate.

$\displaystyle\nabla
J(\theta)=\nabla\mathbb{E_{\pi}}[r(\tau)]=\mathbb{E_{\pi}}[r(\tau)\nabla\log(\pi(\tau))],$
(24)

By reformulating the gradient we get:

$\nabla\mathbb{E}_{\pi_{\theta_{t}}}[r(\tau)]=\nabla\int\pi(\tau)r(\tau)d\tau,$
$\nabla\mathbb{E}_{\pi_{\theta_{t}}}[r(\tau)]=\int\nabla\pi(\tau)r(\tau)d\tau,$
$\pi(\tau)\nabla
log\pi(\tau)=\frac{\pi(\tau)\nabla\pi(\tau)}{\pi(\tau)}=\nabla\pi(\tau)$,
$\nabla\mathbb{E}_{\pi_{\theta_{t}}}[r(\tau)]=\int\pi(\tau)\nabla
log\pi(\tau)r(\tau)d\tau,$

The theory of the policy gradient states that the derivative of the
expectation of the reward is equivalent to the expectation of the reward times
the gradient of the log policy $\pi_{\theta}$ :

$\displaystyle\nabla\mathbb{E}_{\pi_{\theta_{t}}}[r(\tau)]=\mathbb{E}_{\pi_{\theta_{t}}}[r(\tau)\nabla_{\theta_{t}}\log(\pi_{\theta}(\tau))],$
(25)

Therefore, the policy training is demonstrated as a gradient ascent process:

$\displaystyle\theta_{t+1}=\theta_{t}+\alpha\mathbb{E}_{\pi_{\theta_{t}}}[r(\tau)\nabla_{\theta_{t}}\log(\pi_{\theta}(\tau))],$
(26)

where $Q_{\pi_{\theta_{t}}}(\tau)$ is the Q-value for the trajectory $\tau$,
and policy $\pi_{\theta_{t}}$. Throughout the training, the PG agent estimates
the probability of selecting each action and chooses actions by random
depending on the probability distribution. Before it learns from experience
and updates the policy parameters, the PG agent performs a full training
episode utilizing the existing policy. The disadvantage of PG method is that
the network policy is updated after the completion of the episode only. This
slackens the convergence rate [17].

###  III-B DDPG-based IRS phase control method

We propose a DDPG-based IRS phase control method considering the optimization
problem in (8). Deep Q-Networks are not suitable because they deal with
discrete time spaces only. Moreover, the convergence of the policy gradient
(PG) algorithm is not sufficient in the context of wireless communication.
DDPG merges the Q-networks and the PG scheme as shown in Fig. 4, and overcomes
the disadvantages of both algorithms[17].

Figure 4: DDPG merges both DPG and DQN

DDPG is a model-free reinforcement learning technique which combines the
advantages of policy gradients and Q-learning. DDPG uses the Bellman equation
and the off-policy data to learn the Q-function, and then uses the Q-function
to learn the policy. DDPG consists of four neural networks (see Fig. 5); one
for actor network, one for critic network, one for target actor network, and
one for target critic network, which ensures the stability. The optimization
problem in (8) can be solved using DDPG by learning the policy.

The actor network is a policy network that accepts state as input and
generates the precise action continuously. In deep Q-networks the optimal
action is obtained by calculating the argmax over all the Q-values for a
finite number of discrete actions. In DDPG the actor network performs the same
but for continuous action spaces, it generates the actions directly by taking
the argmax, and selects actions $a=\mu(s|\theta^{\mu})$ from a continuous
action settings $\mathcal{A}$, where $\mu$ is the policy, $s$ denotes the
states, and $\theta^{\mu}$ denotes the parameters of the deterministic policy
network (DPN). Thus, the actor is a DPN that calculates the action directly,
rather than generating the probability distributions over all actions. The
critic network accepts states and actions as input and generates the Q-value,
so it is considered as the Q-value network $Q(s,a|\theta^{Q})$, where
$\theta^{Q}$ represents the parameters of the Q-network. The critic network
evaluates the performance of the selected action. Therefore, DDPG is an
enhancement for the actor-critic vanilla network, its aim is to maximize the
Q-value which is the output, and it can only be utilized for environments
having continuous action settings. The optimal action is expressed as:

$\displaystyle\mu^{*}(s|\theta^{\mu})=\operatorname*{argmax}_{a}Q^{*}(s,a|\theta^{Q})$
(27)

where $Q^{*}(s,a|\theta^{Q})$ is the optimal Q-value function. Further, to
maximize the Q-value a replay memory $\mathcal{D}$ is utilized to minimize the
correlation of various training samples. This is significant for the algorithm
behavior in order to be stable. The replay memory needs to be adequately large
to include a broad range of previous experiences. Moreover, DDPG makes use of
target networks to increase the stability during the training.

A copy from the actor and critic network are formed to find out the Q-value
for the next state i.e. $a=\mu^{\prime}(s|\theta^{\mu^{\prime}})$ and
$Q^{\prime}(s,a|\theta^{Q^{\prime}})$. Based on the main networks, the weights
of these target networks are updated periodically. In deep Q-networks, the
weight of the main network is copied periodically to the target network and
this called "hard update", whereas in DDPG "soft update" is performed where a
only fraction of the weights of the main network are transferred to the target
network as expressed below:

$\displaystyle\theta^{Q^{\prime}}\leftarrow\tau\theta^{Q}+(1-\tau)\theta^{Q^{\prime}},$
(28)
$\displaystyle\theta^{\mu^{\prime}}\leftarrow\tau\theta^{\mu}+(1-\tau)\theta^{\mu^{\prime}},$
(29)

Figure 5: DDPG Model

Algorithm 2 DDPG-based IRS Phase Control Training

1:Initialization: Set $t=0$ and initialize reply buffer of DDPG agent
$\mathcal{D}$ with capacity M.

2:Randomly initializes the weights of actor networks $\theta^{\mu}$ and critic
networks $\theta^{Q}$.

3:Initialize target networks: $\theta^{\mu^{\prime}}\leftarrow\theta^{\mu}$
and $\theta^{Q^{\prime}}\leftarrow\theta^{Q}$.

4:for $t=1$ to $\infty$ do

5: Observe state $\textbf{s}^{(t)}$ and and select an action with exploration
OU noise $\textbf{a}^{(t)}=\mu(\textbf{s}^{(t)}|\theta^{\mu})+\textbf{n}_{t}$

6: Execute action $\textbf{a}^{(t)}$ at IRS.

7: Receive the immediate reward $r^{(t)}$, and observe next state $s^{(t+1)}$,
store transition
$(\textbf{s}^{(t)},\textbf{a}^{(t)},r^{(t)},\textbf{s}^{(t+1)})$ in $D$.

8: Randomly sample mini-batch transitions from $\mathcal{D}$:
$B\leftarrow\\{(\textbf{s}^{(i)},\textbf{a}^{(i)},r^{(i)},\textbf{s}^{(i+1)})\\}\in\mathcal{D}$
.

9: Compute the targets:
$\tilde{Q}(\textbf{s}^{(i)},\textbf{a}^{(i)}|\theta^{Q^{\prime}})=r^{(i)}+\Gamma
Q(\textbf{s}^{(i+1)},\mu(\textbf{s}^{(i)}|\theta^{\mu^{\prime}})|\theta^{Q^{\prime}})$

10: Update the $\theta^{Q}$ in critic network by minimizing the loss:
$L=\frac{1}{|B|}\sum_{i=1}^{|B|}\big{(}\tilde{Q}(\textbf{s}^{(i)},\textbf{a}^{(i)}|\theta^{Q^{\prime}})-Q(\textbf{s}^{(i)},\textbf{a}^{(i)}|\theta^{Q})\big{)}^{2}$

11: Update the $\theta^{\mu}$ in actor network according to the sampled policy
gradient:
$\nabla_{\theta\mu}\bm{J}\approx\frac{1}{|B|}\sum_{i=1}^{|B|}\nabla_{a}{Q}(\textbf{s}^{(i)},\textbf{a}^{(i)}|\theta^{Q})\nabla_{\theta\mu}\mu(\textbf{s}^{(i)}|\theta^{\mu})$

12: Update the target networks:
$\theta^{Q^{\prime}}\leftarrow\tau\theta^{Q}+(1-\tau)\theta^{Q^{\prime}}$
$\theta^{\mu^{\prime}}\leftarrow\tau\theta^{\mu}+(1-\tau)\theta^{\mu^{\prime}}$

13:end for

where $\tau\ll 1$. Soft updates are significant in order to accelerate the
convergence of the Actor-Critic process since it stabilizes learning. The main
networks which are copied are called evaluation networks. The target networks
and the evaluation networks have the same structure but the difference is in
parameters. The target networks are delayed networks compared to the main
networks [17].

###  III-C RL System Mapping

The first step in solving a problem using RL is to map the problem into the
key components of an RL system; namely, state-space, action space, and reward
function. In the following, we discuss this mapping as well as the general
behaviour of the RL method using DDPG.

####  III-C1 State-space

The state space of the DDPG agent at timestep ${(t)}$ can be defined as
follows

$\displaystyle\textbf{s}^{(t)}=[\leavevmode\nobreak\
\textbf{h}_{t}^{(t)},\leavevmode\nobreak\
\bm{\Phi}^{(t-1)},\leavevmode\nobreak\
\bm{\hat{\gamma}}^{(t-1)}\leavevmode\nobreak\ ],$ (30)

where $\textbf{h}_{t}$ represents the channel gain between the source and IRS,
$\bm{\Phi}$ is the last phase action taken by IRS, and $\bm{\hat{\gamma}}$ is
the estimated SINR values of the users based on their data rates for that
action (i.e.,
$\bm{\gamma}=[\gamma_{1},\gamma_{2},\dots,\gamma_{k},\dots,\gamma_{K}]$ ).

####  III-C2 Action-space

The action space definition is defined by the policy function as follows

$\displaystyle\textbf{a}^{(t)}=\mu(\textbf{s}^{(t)}|\theta^{\mu})+\textbf{n}{(t)}$
(31)

where $\mu$ is the policy function and $\theta^{\mu}$ is parameters (i.e.,
weights of neural network), and $\textbf{n}(t)$ is the Ornstein-Uhlenbeck (OU)
process-based action noise [18]. Final output is an array that defines the
phase of each element in the IRS.

####  III-C3 Reward function

The reward function is defined based on the current channel capacity and the
maximum capacity ever reached as follows:

$\displaystyle r^{(t)}=R_{sum}^{(t)}-R_{sum,max},$ (32)

where $R_{sum}^{(t)}$ is the actual sum-rate of the users, while $R_{sum,max}$
is the maximum sum-rate achieved.

####  III-C4 Exploration vs. Exploitation

Since the action space of the DDPG is continuous, the exploration of action
space is handled with noise generated by the OU process. OU process samples
noise from a correlated normal distribution.

####  III-C5 DDPG Algorithm

As shown in Algorithm 2, we begin initializing the replay buffer $D$ of the
agent with transaction capacity $M$ in step 1. In step 2, we initialize the
weights of actor and critic networks for the agent. The target networks are
initialized by copying the same weights in step 3. From step 4 to 13,
represents each iteration (i.e., timestep $t$). In each iteration (i.e.,
timestep $t$), we observe the state s for the agent (IRS), determine an action
(i.e., phase value) with exploration noise based on OU process in step 5.
After the agent determined and executed the action, a reward $r^{(t)}$ is
received and new state $\textbf{s}^{(t+1)}$ is observed, and transactions are
stored in respective replay memories in steps 6 and 7. A random mini-batch of
transitions are sampled in step 8. Using the Bellman equation, the actors and
critic networks’ targets are computed in step 9. The critic network weights
are updated by minimizing the loss using computed targets in step 10. The
actor network weights are updated for the sampled policy gradient in step 11.
Finally, the agent’s target networks are updated using the update rate
($\tau$) for stability in step 12.

####  III-C6 Neural Network Architecture

DDPG agent’s architecture consists of $4$ neural networks including actor and
critic networks and target actor and critic for stability. Both actor and
critic networks consist of $2$ hidden layers, with $256$ hidden nodes in each
layer. The actor-network input has the size of $2M+K$, and output is $M$,
thanks to the continuous definition of DDPG. As can be seen from DDPG agents’
structure, it allows scalability to a much larger extent with linearly
increasing complexity.

###  III-D Discussion on Complexity

To reveal the value of using DDPG, we provide a quick quantitative analysis of
the exhaustive search algorithm complexity, $\mathcal{N}_{E}$ versus the
complexity, $\mathcal{N_{D}}$ of the proposed DDPG based algorithm. The
complexities can be easily deduced from the description of the algorithms
given in Algorithm 1 and Algorithm 2. For exhaustive search asssuming $K$
users, $M$ IRS elements and $N=\frac{2\pi}{\Delta\Phi}$ phase change steps, we
can write the complexity as

$\displaystyle\mathcal{N}_{E}=O(K\times N^{M}).$ (33)

For the DDPG based system, the complexity for the trained network (steady
state complexity) depends mainly on the forward network architecture (Actor
Network). Assume the number of states (size of actor network input) is $S$,
number of hidden layers is $n$, number of neurons in each hidden layer is $U$,
number of actions (i.e., phase of each IRS element) which is size of the
output layer is $A$, and the DDPG algorithm will always provide the action of
the highest reward for the $A$ distinct actions as output. Therefore, the
complexity of the DDPG can be written as

$\displaystyle\mathcal{N}_{D}=O(S\times n\times U\times A).$ (34)

Thus, the complexity of DDPG is much lower than that of the exhaustive search
as the number of users or the number of IRS elements increases.

##  IV Numerical Results

In this section, we first measured the performance of the DDPG algorithm to
make sure that the sum-rate values calculated are close to the upperbound. By
using the exhaustive search algorithm we calculated the maximum sum-rate by
obtaining the optimum phase shift matrix and assuming that the channel is
known. The exhaustive search scheme is very complex, so the number of IRS
reflecting element used is $M$ = 4 rather than $M$ = 16. This is to verify
that our DDPG algorithm can approach the upperbound. For each element we
considered the phases between 0 and $2\pi$ with a step size of 16. Thus, the
total number of combinations of phase shift matrices is $16^{4}$. The sum-
rates are calculated for 16 users and for monte-carlo simulations equal to
1000. Fig. 6 reveals that NOMA sum-rate generated by the DDPG algorithm
approaches the upperbound and it is close to optimal. The complexity of the
exhaustive search algorithm can be calculated as 1000 x $16^{5}$ which is
equal to $1.0486\times 10^{9}$ iterations with elapsed time equal to 12.51
hours.

Figure 6: Upperbound on Performance vs Proposed DDPG Algorithm. M = 4, K = 16,
and $\Delta\Phi=\frac{2\pi}{16}$. Figure 7: NOMA Sum Rate vs Iteration Plots

Moreover, the result in Fig. 7 verifies the convergence of our DRL algorithm.
It shows the average NOMA rate verses the iteration plots. The average rate is
increasing with time. This means that the training process is conducted
successfully. Further, the simulation results below reveal the performance of
our DRL based IRS NOMA system with IRS reflecting elements $M=16$. The default
parameters used in the simulation are shown in Table I. The number of of users
is $K=32$, the number of BS antennas is $N_{t}=1$, the number of antennas per
each user is $N_{r}=1$, the distance between the BS and the IRS is 50 m and
the distances between the IRS and the users are randomly generated between 200
and 1500 m. The channel between the BS and the IRS and the channel between the
IRS and users follow the rician fading model with rician factor K1 = K2 = 10.
However, the channel between the BS and the IRS is assumed to be perfectly
estimated, whereas the channels between the IRS and users are assumed to be
unknown. The bandwidth is 10 MHz, the BS transmit power Pt is 40 dBm, and the
noise power spectral density equals -174 dBm/Hz. Simulation results are
generated using $10^{3}$ monte-carlo runs.

Figure 8: Comparison between NOMA and OMA sum rates Table I: Parameters Used in Simulation Simulation Parameters | Values
---|---
Number of Users (K) | 32
Number of Reflecting Elements (M) | 16
Number of BS antennas $N_{t}$ | 1
Number of antennas per user $N_{r}$ | 1
Distance between BS and IRS | 50
Distance between the IRS and the users | 200 - 1500
BS transmit power | 40 dBm
Bandwidth | 10 MHz
Noise power spectral density | -174 dBm/Hz
BS to IRS Path loss exponent | 2
IRS to users Path loss exponent | 2.8
Rician Factor | 10
Critic learning rate | 0.001
Actor learning rate | 0.0005
Discount factor $\Gamma$ | 0.05
Coefficient of Soft Updates $\tau$ | 0.05
Batch size | 64
Buffer Capacity $\mathcal{C}$ | 10000

In the proposed DDPG algorithm, the actor and critic networks are both dense
neural networks (DNN). The input of the actor network is the number of states
that contains 128 neurons while the output is the number of actions which
contains 16 neurons. The hidden layers in the actor network are two layers
that contain 256 neurons each, followed by ReLU activation function. The
output layer of the actor network uses the tanh(·) function in order to
provide enough gradient. For the critic network, the input layer is the number
of states and the number of actions. The state input is followed by two dense
layers of 128, and 256 neurons respectively with ReLU activation functions,
and the action input is followed by one dense layer of 128 neuron. Both
outputs are passed via separate layer before concatenating to represent the
input of the critic network. After that, two hidden layers are added each of
256 neurons with ReLU activation functions. This is pursued by the output
layer of the critic network which contains 16 neurons. Both actor and critic
main networks use Adam optimizer to update parameters. Moreover, we set the
number of steps in each episode B = 1000, the actor learning rate = 0.0005,
the critic learning rate = 0.001, the coefficient of soft updates $\tau=0.05$
, the discount factor $\gamma=0.05$, the buffer capacity = 100 000. The noise
is complex additive white Gaussian with mean equal to zero and variance equal
to 0.1.

A comparison between NOMA and OMA sum rates versus the number of users is
shown in Fig. 8, where the transmit power Pt is 40 dBm. It is realized that
NOMA performs better than OMA since it provides higher sum rate for a number
of users less than 16. The reason is that in NOMA there is resource sharing
among users since NOMA multiplexes users in the power domain, and thus there
is no bandwidth division. Therefore the rate and spectral efficiency are
higher. However, in OMA there is no resource sharing and thus the bandwidth is
divided among users. Further, when the number of users increases above 16,
interference between users increases and thus OMA performs better in this case
and provides higher sum rate than NOMA.

Figure 9: NOMA sum rate for various power levels Figure 10: Achievable Sumrate
at nearest user with imperfect SIC

Moreover, Fig. 9 demonstrates the sum rate of NOMA vs the number of users for
different power levels starting from 10 up to 80 dBm. The lower curve
represents the sum rate generated at transmit power equals 10 dBm, and the
highest curve depicts the sum rate generated at at transmit power equals 80
dBm. It is realized that as power increases the sum rate increases and thus
our IRS NOMA system is able to server more number of users.

Furthermore, Fig. 10 shows the rate for user K, the nearest user to the BS,
when considering imperfect SIC. It is well known that user 1, the farthest
user from the BS, does not perform SIC and thus we will plot the rate for user
K which during imperfect SIC will have residual interference of all users’
power in the denominator. It is obvious that as the imperfection increases,
the rate will be lower. The curves are plotted for different values of
$\large\epsilon$ which represents the fraction of residual interference. When
$\large\epsilon$ equals 0, SIC is perfect, and thus the rate for user k is the
highest. As $\large\epsilon$ value increases the rate decreases due to
increasing the fraction of imperfectness. Therefore, imperfect SIC has a
deleterious impact on the rate of the users performing SIC.

##  V Conclusion

In this paper, we considered the downlink scenario of the IRS NOMA system. Our
main goal was to maximize the sum rate of NOMA users. The formulated problem
is non-convex since it involves the constant modulus constraint, and the
objective function which is also non-convex. Thus, the problem is suitable for
DRL learning techniques. In particular, we have used the DDPG which is a DRL
algorithm to solve the sum rate maximization problem for our IRS NOMA
scenario. Simulation results revealed that the sum rate for NOMA can track the
upperbound obtained through exhaustive search, and it is superior to OMA for a
specific number of users and predefined transmit power. Moreover, increasing
the transmit power results in increasing the number of users served by the IRS
NOMA system since NOMA multiplexes users in the power domain. Further, when
considering the imperfect SIC scenario, which is more realistic, results
showed that as the imperfection factor increases, the sum rate of users
decreases. This reveals the significance of performing SIC perfectly.

## References

  * [1] Xiaohu YOU, Cheng-Xiang WANG, Jie HUANG “Towards 6G wireless communication networks: vision, enabling technologies, and new paradigm shifts” in SCIENCE CHINA January 2021.
  * [2] Jun Zhao, Yang Liu “A Survey of Intelligent Reflecting Surfaces (IRSs): Towards 6G Wireless Communication Networks” arXiv:1907.04789v3 Nov 2019.
  * [3] Xidong Mu, Yuanwei Liu, Li Guo, Jiaru Lin, and Naofal Al-Dhahir, “Exploiting Intelligent Reflecting Surfaces in NOMA Networks: Joint Beamforming Optimization” IEEE Transactions on Wireless Communications 13 July 2020.
  * [4] H. Guo, Y. Liang, J. Chen, and E. G. Larsson, “Weighted sum-rate maximization for intelligent reflecting surface enhanced wireless networks,”2019 IEEE Global Communications Conference.
  * [5] Linglong Dai, Bichai Wang, Zhiguo Ding, Zhaocheng Wang, Sheng Chen, and Lajos Hanzo "A Survey of Non-Orthogonal Multiple Access for 5G" IEEE Communications Surveys and Tutorials, VOL. 20, NO. 3, Third quarter 2018.
  * [6] Helin Yang, Zehui Xiong, Jun Zhao, Member, Liang Xiao, and Qingqing Wu “Deep Reinforcement Learning-Based Intelligent Reflecting Surface for Secure Wireless Communications” in IEEE Transactions on Wireless Communications, VOL. 20, NO. 1, JANUARY 2021.
  * [7] Chongwen Huang, Ronghong Mo and Chau Yuen “Reconfigurable Intelligent Surface Assisted Multiuser MISO Systems Exploiting Deep Reinforcement Learning” 08 June 2020 IEEE Journal on Selected Areas in Communications.
  * [8] Keming Feng, Qisheng Wang, Xiao Li, and Chao-Kai Wen “Deep Reinforcement Learning Based Intelligent Reflecting Surface Optimization for MISO Communication Systems” IEEE Wireless Communications Letters vol. 9, NO. 5, MAY 2020.
  * [9] Abdelrahman Taha, Yu Zhang, Faris B. Mismar, and Ahmed Alkhateeb, “Deep Reinforcement Learning for Intelligent Reflecting Surfaces Towards Standalone Operation” IEEE 21st International Workshop on Signal Processing Advances in Wireless Communications (SPAWC) 26 May 2020.
  * [10] Abdelrahman Taha, Muhammad Alrabeiah, and Ahmed Alkhateeb “Deep Learning for Large Intelligent Surfaces in Millimeter Wave and Massive MIMO Systems” 2019 IEEE Global Communications Conference (GLOBECOM).
  * [11] Ming Zeng, Xingwang Li, Gen Li, Wanming Hao and Octavia A. Dobre, “Sum Rate Maximization for IRS-assisted Uplink NOMA", IEEE Communications Letters, January 2021.
  * [12] Zhiguo Ding ,and H. Vincent Poor “A Simple Design of IRS-NOMA Transmission”, in IEEE Communications Letters”, 17 February 2020.
  * [13] Zheng Zhang, Lu Lv, Qingqing Wu, Hao Deng, and Jian Chen “Robust and Secure Communications in Intelligent Reflecting Surface Assisted NOMA networks,”in IEEE Communications Letters, 23 November 2020.
  * [14] Gang Yang ; Xinyue Xu ; Ying-Chang Liang “Intelligent Reflecting Surface Assisted Non-Orthogonal Multiple Access,” in 2020 IEEE Wireless Communications and Networking Conference (WCNC) 25-28 May 2020.
  * [15] Jiakuo Zuo, Yuanwei Liu, Ertugrul Basar, Senior,and Octavia A. Dobre “Intelligent Reflecting Surface Enhanced Millimeter-Wave NOMA Systems,” in IEEE Communications Letters 14 July 2020.
  * [16] Xianghao Yu, Dongfang Xu, and Robert Schober “MISO Wireless Communication Systems via Intelligent Reflecting Surfaces,” in IEEE/CIC international Conference on Communications in China (ICCC) 2019.
  * [17] Vincent François-Lavet, Peter Henderson, Riashat Islam, Marc G. Bellemare and Joelle Pineau (2018), “An Introduction to Deep Reinforcement Learning”, Foundations and Trends in Machine Learning: Vol. 11, No. 3-4, 2018.
  * [18] G E. Uhlenbeck and L S. Ornstein, "On the Theory of the Brownian Motion", Revista Latinoamericana De Microbiologia, 1930.


# Accelerating the Learning of TAMER with Counterfactual Explanations

Jakob Karalus  Institute of Artificial Intelligence
Ulm University
Ulm, Germany
<EMAIL_ADDRESS>Felix Lindner  Institute of Artificial Intelligence
Ulm University
Ulm, Germany
<EMAIL_ADDRESS>
###### Abstract

The capability to interactively learn from human feedback would enable agents
in new settings. For example, even novice users could train service robots in
new tasks naturally and interactively. Human-in-the-loop Reinforcement
Learning (HRL) combines human feedback and Reinforcement Learning (RL)
techniques. State-of-the-art interactive learning techniques suffer from slow
learning speed, thus leading to a frustrating experience for the human. We
approach this problem by extending the HRL framework TAMER for evaluative
feedback with the possibility to enhance human feedback with two different
types of counterfactual explanations (action and state based). We
experimentally show that our extensions improve the speed of learning.

###### Index Terms:

Human-in-the-loop Reinforcement Learning, Counterfactuals, Explainability

##  I Introduction

Classical Machine Learning approaches like Supervised Learning or
Reinforcement Learning can solve complex tasks with sophisticated
architectures, but they allow for little to no interaction possibilities with
the human throughout their training. The field of Human-in-the-loop
Reinforcement Learning (HRL) aims to integrate the human into the learning
process, allowing the agent to learn directly from the human. This integration
of humans into the training process allows non-experts to train or modify an
agent’s behavior naturally.

While integrating humans into the learning process opens up new possibilities,
doing so also introduces new challenges. In this work, we address two of them:
the integration of an enhanced interface for evaluative feedback and the
learning speed of the algorithm. When teaching an agent, humans naturally want
to enrich their feedback with explanations, and a too simplistic interface can
lead to frustration on the human side, see [1, 2]. In most previous work,
humans can only give simple binary feedback [3] or control a single dimension
[4]. Moreover, human feedback is more costly than automated feedback from the
environment or a simulator. State-of-the-art Reinforcement Learning needs
millions of episodes with billions of frames (see [5]). It is insufficient to
use the same algorithms and replace the environmental reward with the human
reward since it is not feasible for a human to watch the agent for weeks or
months of training. In addition to the time constraint, if progress is slow,
it can lead to early frustration for the human if they see no impact of their
feedback in training. Therefore, the algorithms’ learning speed is crucial for
a positive user experience.

Since the flexible interfaces and learning speed are both crucial for the
experience of the human, we want to investigate with this work if the
inclusion of counterfactuals in TAMER can be beneficial for the learning
speed. Counterfactuals are methods of explanations to describe a causal link
between two possible outcomes in the form of: “If event B rather than A had
happened, then outcome Y rather than X would have happened”. Since
counterfactuals contain more information (due to the second outcome, see
Section III-B), we believe they could be a solution to enhance the learning
speed. In concrete, we focus on optional upward-directed counterfactuals,
which should speed up learning and give humans more flexibility in their
feedback when working with TAMER. We show that this type of feedback can be
easily added to one of the most prominent methods for evaluative feedback,
TAMER.

Source code and evaluations are available under:
https://anonymous.4open.science/r/InteractiveRL-25A1.

##  II Related Work

One of the first proposed frameworks for HRL with evaluative feedback is the
TAMER framework [3], which we use as a basis for our work (see chapter III).
Throughout this work, we use the standard extension DeepTAMER [6], which
enables the usage of Deep Neural Nets as a function approximator. Multiple
extensions of TAMER tackle the problem of combining human feedback with
environmental feedback. TAMER+RL [7] and continuous TAMER+RL [8] both re-
introduce the environmental reward and enable learning from multiple feedback
sources. A common trend is introducing Reinforcement Learning frameworks into
TAMER: Arakawa et al.[9] combine it with Deep-Q learning, and Vien et al.[10]
use an actor-critic setting to enable the usage in continuous-actions spaces.
While all these approaches enable the usage of TAMER in additional types of
environments, their assumption and interface for human feedback stay the same.
Therefore our work would also be applicable to each of them.

COACH [11] assumes that the feedback given by the human is advantage-based
(”How much better is the current policy than the previous one?”), which allows
to learn a policy directly. Since the significant difference between COACH and
TAMER are the different assumptions about human feedback (forward-looking
versus advantage-based) both variants are targeted toward different types of
feedback. While our work is transferable to COACH, the crucially different
assumption about how humans formulate feedback makes it hard to compare both
methods fairly on a technical basis. At the same time, it is still open which
assumptions are preferred by humans. Therefore we refrain from an in-depth
comparison of different both approaches.

In contrast to TAMER’s reward-shaping approach, a different approach to HRL is
policy-shaping [12]. Policy-shaping uses the feedback directly as labels for
the corresponding policy instead of interpreting it as a reward signal. A
prominent variant of this is the work of Celemin et al.[4] for their COACH
framework (a different COACH than the above mentioned), which can learn a
policy from corrections. The concept of corrections bears similarities to our
counterfactual actions. We refrain from a direct evaluation of counterfactuals
in this framework due to the incompatibilities in the action spaces (their
correction are on continuous actions, while ours are currently on discrete
actions only).

A different avenue for feedback in HRL has been preference-based methods, [13]
where humans can give preference for one whole trajectory over another. This
type of feedback requires the generation of trajectories, which can limit the
application for inherently safe applications or simulated environments.
Nevertheless, while our work is not directly applicable, the concepts should
be easily adaptable for preference-based methods.

Action Advising [14] is a popular feedback method for HRL, in which the human
advises the agent on which actions it should perform next. Conceptually,
advising is similar to our counterfactual actions, with the difference that
advice is given beforehand instead of afterward. Moreover, a critical
difference between Action Advising and our counterfactual actions is the
contrastive nature of counterfactuals (see Section III-E). Since our work is
motivated by allowing more flexible feedback from humans rather than
benchmarking different interfaces for feedback in HRL, we refrain from a
technical comparison and refer to [15].

Guan et al.[16] integrate human explanation into the HRL by using saliency-
based attention annotation combined with Deep Convolutions Networks. This
method showed that the inclusion of explanations in HRL could lead to better
performance. However, this method can only be applied in specific cases due to
Saliency Maps and Deep Neural Nets. In contrast, our current proposed solution
is primarily independent of the input shape and the approximator’s chosen
architecture.

While counterfactuals have not been used in HRL, other work has successfully
used counterfactuals in different areas. Lu et al.[17] have shown that an
integration of counterfactuals, through the usage of Structural Causal Models
(SCM), in Reinforcement Learning (without human feedback) can be beneficial to
label efficiency. Work by Jin et al.[18, 19] used counterfactuals in partial
observable settings to increase the learning speed, and robustness of their
Reinforcement Learning approaches. Foerster et al.[20] use a counterfactual
loss in a multi-agent reinforcement setting to increase their performance.
Menglin et al.[21] use counterfactual experiences to solve inefficiencies with
exploration in the early stages of SARSA with counterfactuals.

The concept of counterfactuals has been included in different applications
with success. With this work, we formulate a general method for the inclusion
of counterfactuals in HRL.

##  III Background and Methods

This Section explains the relevant background and highlights our extension of
the existing method. First, we will explain TAMER, introduce counterfactuals,
and investigate the convergence of TAMER from a Reinforcement Learning
perspective. Afterward we use this perspective as motivation to introduce
counterfactuals in TAMER.

###  III-A The TAMER Framework

Human-in-the-loop Reinforcement Learning (HRL) allows the agent to learn from
human feedback directly and incrementally, even in environments with no other
reward signal. A major difference of human feedback is the potential
inconsistency and sub-optimality of human feedback. Humans can give feedback
at various stages throughout the training, but the agent cannot depend on a
fixed and reliable reward (unlike the standard environmental reward). HRL is
also advantageous in very complex environments where a specification of a
solid reward function is challenging since even slight misspecifications of
the reward function can lead to unexpected side-effects in actual use cases
[22].

In this work, we use TAMER, a framework for evaluative feedback. In this
scenario, after the agents performed an action $a$ in a specific state $s$,
the human has the opportunity to give his evaluative feedback $\mathit{f}$
towards the agent. No additional reward function is given and the agent has to
learn a policy from the human reward. In most work the range of the feedback
is restricted towards discrete feedback of $-1$ and $+1$.

TAMER [3] allows to learn a policy with human evaluative feedback by assuming
that the human already considers the long-term solution in his feedback. This
assumption lets us greedily learn a function that maps states to their
excepted feedback: ($H:S\times A\rightarrow F$). In TAMER, mapping $H$ is
learned immediately with a single state/action pair when feedback is given.
This learned function of the human reward ($H$) is used to greedily select
actions with the highest expected human reward at each time-step, i.e.,
$argmax_{a}(H(s,a))$. Therefore, TAMER is conceptually similar to Q-Learning
with the crucial difference that it assumes long-term feedback and therefore
does not have the credit assignment problem. TAMER does not use any
environmental reward, methodical exploration, or longer-term planning
mechanism.

DeepTAMER [6] extends TAMER by using Deep Neural Networks as the approximator
for the $H$ function. The network architecture consists of shared base layers
and individual fully-connected heads for each action. Additionally, a replay
buffer (which stores past feedback/states) is used to stabilize training. In
our work, we will roughly follow the architecture of DeepTAMER, with minor
modifications due to different state space and action space sizes.

###  III-B Counterfactuals

Counterfactual explanations describe a causal connection between two possible
events in the form: “If event B rather than A had happened, then outcome Y
rather than X would have happened” [23]. Counterfactuals thus refer to an
event $A$ that actually has happened and caused some outcome _fact_ $X$, and
to the contrast $B$, which would have resulted in a different outcome (the
_foil_) $Y$ [24]. It is important to note that a counterfactual does not only
provide a second data point—the contrast-foil pair—, but also the contrast
relationship between the fact and the foil is an equally important property.
We will make use of both these properties, that is, we treat the foil as an
additional example and exploit the contrastive relationship between fact and
foil to achieve faster learning.

As multiple studies [25, 26] show, it is easier for most people to envision a
world “better-off” than a world “worse-off”. Additionally, positively-directed
counterfactuals are usually of higher quality [23]. We therefore allow humans
to state counterfactual explanations of negative feedback to an observed event
$\langle state,action\rangle$. The counterfactuals can take the form “If $a$
had been performed in state $s_{\mathit{cf}}$ rather than in state $s$, then
my feedback would have been positive rather than negative” and “If action
$a_{\mathit{cf}}$ had been performed $s$ rather than action $a$, then my
feedback would have been positive rather than negative.” This allows the agent
to learn how to get from a state with bad feedback into a state with good
feedback.

Figure 1: Left: Visualization of the MiniGrid environment with the goal as a
green square. The highlighted area indicates the current viewpoint of the
agent. Right: Verbalization of the various feedback mechanism in natural
language.

###  III-C The convergence of Reinforcement Learning algorithms

In HRL, learning speed is particularly essential because humans are asked to
give feedback to the learner. This is a tedious task we naturally want to
minimize. An agent which learns too slowly or shows no progress can limit the
motivation of the human to give further feedback [27]. In Reinforcement
Learning, the convergence difference between an expert policy $\pi^{*}$ and a
sub-optimal $\pi$ can be described by the distance between the optimal
distribution of visited states and the current distribution (also known as
performance difference lemma due to Kakade [28]):

$V^{\pi^{*}}-V^{\pi}=\sum_{s}\pi^{*}(s)\sum_{a}(\pi^{*}(a\mid s)-\pi(a\mid
s))Q^{\pi}(s,a)$ (1)

The optimal policy is denoted by $\pi^{*}$, $\pi^{*}(s)$ is the visited state
distribution of $\pi^{*}$, and $\pi^{*}(a\mid s)$ is the action distribution
of the optimal policy. Accordingly, there will always be a difference in
performance as long as there is a substantial difference in the visited
states. While the original lemma was formulated for classical Q-learning, we
apply the same concept to TAMER since its replacement of $Q$ with $H$ can be
seen as identical in function and convergence. In a setting with an ample
state/action space, under a random policy $\pi$, the distribution of visited
states will drastically differ from the expert distribution. This leads to a
“chicken/egg” problem, where to learn quickly, an agent has to reach states
similar to the states the expert would reach, but doing that is essentially
the goal of learning.

The previously introduced concept of positively-directed counterfactuals comes
directly from the expert distribution since it indicates which part of the
current $\langle state,action\rangle$ pair should have been different. This
should allow the agent to reduce the difference $V^{\pi^{*}}-V^{\pi}$, which
leads to faster learning. To experimentally test this hypothesis, we introduce
two different types of positively-directed counterfactuals into the TAMER
framework and confirm that their inclusions lead to faster learning. Besides
the above-discussed human reasons for “better-off” counterfactuals, the
performance difference thus offers an additional viewpoint favoring our focus
on positively-directed counterfactuals.

###  III-D Using counterfactuals in TAMER

To introduce counterfactuals into TAMER, we have to change the fact of our
current $\langle state,action\rangle$ pair, so that the new contrast would
receive a positive reward. To achieve this contrast, we modify either the
state or the action of our fact. We call the modified element counterfactual
state or counterfactual action. In the following we will denote counterfactual
actions or states with the subscript $s_{\mathit{cf}}$ and $a_{\mathit{cf}}$.
When asking the human for feedback with $gather\\_\mathit{f}eedback(s,a)$ the
subscripts $s_{t-1}$, $a_{t-1}$ indicate the last state or action performed
(since the human gives their feedback after an action is performed, so the
agent is already in a new state).

A counterfactual state provides a state where the action would be a good one.
The feedback $gather\\_\mathit{f}eedback(s_{t-1},a_{t-1})=(-1,\langle
1,s_{\mathit{cf}},a\rangle$) can be read as “Action $a$ would be good if you
were in state $s_{\mathit{cf}}$ instead of $s$”. In case of counterfactual
actions, $gather\\_\mathit{f}eedback(s_{t-1},a_{t-1})=(-1,\langle
1,s,a_{\mathit{cf}}\rangle$) can be described in natural language with: “In
state $s$, action $a_{\mathit{cf}}$ would be better than action $a$”. Both
types of counterfactuals are exemplified in Figure 1.

0: $H$ function approximator; total episodes $N_{e}$; maximum number of steps
per episode $N_{s}$

for e = 1 to $N_{e}$ do

for t = 1 to $N_{s}$ do

$s_{t}$ $\leftarrow$ observe state

$f,\langle f_{\mathit{cf}},s_{\mathit{cf}},a_{\mathit{cf}}\rangle\leftarrow$
gather feedback ($s_{t-1}$, $a_{t-1})$

if $(f_{\mathit{cf}})$ then

update $H$ with
$L(s_{t-1},a_{t-1},f,s_{\mathit{cf}},a_{\mathit{cf}},f_{\mathit{cf}})$

else

update $H$ with $\langle f,s_{t-1},a_{t-1}\rangle$

end if

$a_{t}$ $\leftarrow$ $argmax_{a}(H(s,a))$

perform action $a_{t}$

end for

end for

Algorithm 1 TAMER with Counterfactual Feedback

To include these counterfactuals in TAMER, we extend the human feedback
function to return an optional triple
$\langle\mathit{f}_{\mathit{cf}},s_{\mathit{cf}},a_{\mathit{cf}}\rangle$. This
triple contains the counterfactual feedback $\mathit{f}_{\mathit{cf}}$ and
either $s_{\mathit{cf}}$ or $a_{\mathit{cf}}$ contains a counterfactual
version of the original input, depending on the type of counterfactual
feedback provided. When provided by the human, we use the triple for an
additional update of $H$, combined with the standard TAMER update
$\langle\mathit{f},s,a\rangle$. The full procedure with all steps is also
described in Algorithm 1.

###  III-E Using the contrastive nature of counterfactuals

Besides using counterfactuals as additional data points, we will also leverage
another essential property of counterfactuals: their natural contrast between
the fact and the foil. This contrast allows us to introduce an additional term
with contrastive constraints in the loss function to distance the activations
of each state-action pair from each other.

In Equation 2, our contrastive loss is shown, where $E(s,a)$ is the output (or
embedding) of the last-hidden layer, which is common to the counterfactual and
feedback pair (depending on the respective architecture for the H-Model). This
loss term should speed up the learning process due to the additional
information contained in the gradients.

$\displaystyle L_{cos}(s_{t-1},a_{t-1},s_{\mathit{cf}},a_{\mathit{cf}})={}$
(2)
$\displaystyle\mspace{100.0mu}max(0,cos(E(s_{t-1},a_{t-1}),E(s_{\mathit{cf}},a_{\mathit{cf}}))$

With this contrastive term, the complete loss (see Equation 3) can be built as
a simple combination of all three loss terms. The $L_{normal}$ and the
$L_{\mathit{cf}}$ could be any loss classes, in our case, they both refer to a
L2-loss.

$\displaystyle
L(s_{t-1},a_{t-1},\mathit{f},s_{\mathit{cf}},a_{\mathit{cf}},\mathit{f}_{\mathit{cf}})={}$
(3) $\displaystyle\mspace{100.0mu}L_{normal}(s_{t-1},a_{t-1},\mathit{f})+{}$
$\displaystyle\mspace{100.0mu}L_{\mathit{cf}}(s_{\mathit{cf}},a_{\mathit{cf}},f_{\mathit{cf}})+{}$
$\displaystyle\mspace{100.0mu}L_{cos}(s_{t-1},a_{t-1},s_{\mathit{cf}},a_{\mathit{cf}})$

##  IV Evaluation

For our evaluation, we will use TAMER as the baseline, and compare it to the
proposed additions of counterfactuals states (TAMER+CFS) and counterfactual
actions (TAMER+CFA). First, we evaluate the performance of each variant in
different environments and show that our changes lead to faster learning.
Afterwards, we introduce changes in the feedback frequency and in the quality
of the feedback to show that the improvement with counterfactual feedback also
holds under more realistic feedback conditions. Finally, we perform some
simple ablations to evaluate our choices regarding the direction of
counterfactuals and their benefit over random samples.

###  IV-A Environment Setup & Measurements

We run the evaluations in multiple environments (CartPole, LunarLander,
Minigid 111https://github.com/maximecb/gym-minigrid). We changed the MiniGrid
environment, so that the goal position is random (instead of a static goal at
the bottom-right corner.) We selected an architecture similar to the one used
in DeepTAMER [6].

To evaluate the performance of the learning agent, we use the environmental
reward as a measure of success. This reward is only used to evaluate the agent
and is never seen or used in training. The agent fully learns from human
feedback. In the following sections, we will refer to this reward for the
evaluation of the algorithms. To track the learning progress, at fixed steps,
we run an evaluation (without learning) in 10 different (fixed) seeds of the
same environment. The total reward of each run is collected and then presented
as a mean. This allows us to track the learning of an agent throughout its
training. Since the learning of HRL can be highly unstable, we perform
multiple training runs per algorithm/environment with different random seeds
to initialize the agent and the environment. To allow for easier comparisons,
we normalize the rewards at the end of each episode so that a (perfect)
solution results in the total reward of 1, while random agents get a 0 reward
(on average). Since we want to enable faster learning and therefore want to
look at the whole training process (instead of the performance after the
training), we selected the optimality gap (the area between the current
performance and a perfect performance) as a metric for the evaluation. This
metric enables us to evaluate the performance of our variants in a
statistically sound way, without the pitfalls of showing large amounts of
metrics in large tables or interpreting graphs, as discussed by Agarwal et
al.[29].

With our scores already normalized, an utterly random agent would receive an
optimality gap of 1, while a perfect agent would produce a 0. Additionally, we
compute 95% confidence intervals through bootstrapping (as proposed by [29])
in each plot, indicated by the shaded area.

###  IV-B Human-Feedback Oracle

While HRL aims to incorporate human feedback into the training loop, it can be
costly to collect human feedback. This cost can hinder the development and
evaluation of HRL algorithms since evaluations are often performed with only a
few humans, leading to false interpretations due to statistical randomness. In
this work, we focus purely on the improvements of the feedback from a learning
standpoint. Therefore, we use a synthetic oracle to imitate human feedback
(like other prior work, e.g., by Christiano et al.[30]). To achieve this, we
trained an agent for the oracle with proximal policy optimization (PPO) [31]
algorithm on every environment for sufficiently many steps to solve the tasks.
We then use this policy to give dynamically calculated (counterfactual)
feedback for the actual learning algorithm.

The handling of inconsistent and sub-optimal feedback is one of the major
challenges in HRL. Our evaluation accounts for inconsistency and sub-
optimality by introducing two hyper-parameters. With the “feedback frequency”
parameter, we control how often the oracle gives feedback towards the agent to
archive inconsistent feedback. With the “feedback quality” parameter, we allow
the oracle to give random feedback, which results in lower-quality feedback.

Figure 2: Interquartile mean reward of each feedback method on the evaluation
set throughout training. Bold line is the IQM reward of random seeds (n=25),
area is the 95% confidence interval.

###  IV-C Results

As shown in Figure 2, TAMER extended with counterfactuals leads to faster
learning than the original TAMER. The main advantage is at the early stages of
training, where learning is significantly faster than the original TAMER. At
later stages of the training, the difference shrinks when all variants
(vanilla TAMER and our extensions) reach the maximum reward plateau (with
enough training steps).

To highlight the faster learning, we measure the absolute performance of each
variant at regular intervals for each environment and calculate the optimality
gap with these measurements. The results can be seen in Figure 3, which shows
that both of our methods learns faster than vanilla TAMER. Counterfactuals
actions perform better than counterfactuals states, since counterfactual
actions outperform vanilla TAMER, while counterfactual states struggle in some
environments.

Figure 3: Optimality Gap with confidence intervals on all tasks. (Lower means
better)

Reduced feedback frequency. Perfect feedback rates are not a realistic
assumption for HRL. Hence, we investigate our extensions under more realistic
conditions: we reduce the frequency in which the oracle gives feedback. This
mimics one essential characteristics of HRL, namely that the feedback is not
deterministic and can be inconsistent and sporadic [27]. To achieve this, we
change the feedback frequency of our oracle and evaluate our extension under
this changed condition. As shown in Figure 3, the results show that even with
reduced feedback rates, the general pattern of an increase in learning with
the inclusion of counterfactuals is similar to the results with a perfect
feedback rate. We noted that some environments suffer more from the reduced
rate of feedback.

Reduced feedback quality. Another essential characteristic of human feedback
is that it does not have to be optimal at every point in time. Next, we
evaluate the learning behavior for lower-quality feedback. We try to
approximate these with the synthetic oracle (see Section IV-B), for which set
the “feedback quality” parameter to 0.75. The results show that counterfactual
actions (CFA) still work with lower quality and outperform the baseline.
Naturally, the learning is slower with less optimal feedback since the “signal
strength” is lower. It can be noted that counterfactual states struggle to
perform on a same level than the baseline.

Downward Counterfactuals The usage of upward counterfactuals was motivated by
the performance differences lemma (see section III-C and the preference of
humans. We include a downward counterfactual condition in the evaluation to
evaluate whether the upward property is essential.

The results can be seen in Figure 4, for which we calculate on each comparison
the probability that one variant leads to a better optimality gap than the
other. Using downward counterfactuals still improves the learning compared to
vanilla TAMER, but upward-directed counterfactuals lead to faster learning
than downward counterfactuals.

Random Samples Since we treat counterfactual explanations as additional
samples, one could argue that, by counterfactual explanations, users just
submit more samples to the learning agent, and therefore the learning process
converges faster. To control for this possibility, we evaluate a Random
condition. In this condition, the oracle provides a random state/action tuple,
which is correct but totally unrelated to the current state. In this case we
disable the contrastive loss, since there is no guarantee for a contrast
between the current and the random tuple. Figure 4 shows that indeed the
counterfactual samples perform superior to the random samples.

Figure 4: Placeholder Probability of Improvement, calculated on the optimality
gap, so a improvements means a lower score $P(Y<X)$, for various ablations

###  IV-D Discussion

Faster learning. We extended TAMER to allow the human to give additional
counterfactual feedback and evaluated our extension in various environments
and under multiple conditions. The results indicate that the inclusion of
counterfactuals increases the learning in every condition. Thus,
counterfactual feedback is handled more label efficient than simple binary
feedback or random explanations. This behavior confirms the expectation stated
in section III-C: In the early stages of training, a large difference between
the agent and the expert (human) policy exists. Therefore, introducing a
single example from the expert policy can have a significant impact. In later
stages of the training, when the difference shrinks, the impact of additional
expert samples becomes lower. A limiting side-effect of the learning is that
the agent sees less and less upward counterfactual in the learning process
since we only give counterfactual feedback in negative cases, which occur
fewer in later stages of the training.

Less and lower quality feedback. In cases where the feedback is of lower
quality (which also makes the counterfactual feedback of lower quality), our
counterfactual actions still proves to increase the rate of learning. Our
counterfactual states struggle with reduced feedback quality. This is due to
our construction of the counterfactual feedback. Usually, the state space is
much larger than the action space. Since our lower quality feedback for
counterfactuals randomly samples the respective state or action space (for
either counterfactual states or actions), this leads to a lower signal
strength in counterfactual states. Further research could be done to determine
acceptable lower bounds for the quality of human feedback.

Counterfactual states vs. actions. Both extensions, counterfactual actions and
counterfactual states, increase the rate of learning, with counterfactual
actions (CFA) providing better results than counterfactual states (CFS). We
reason this is because counterfactual actions provide more immediate useful
feedback than counterfactual states feedback. This, in turn, can be explained
since with counterfactual actions, the agent already knows how to reach state
$s$, and it can use the counterfactual action $a_{\mathit{cf}}$ the next time
the agent reaches it.

Upward Counterfactuals & Random Feedback Our main focus in this work was on
upward counterfactuals. Since they come directly from the expert policy (see
III-C), we expected them to perform better than downward directed
counterfactuals. Additionally, as discussed, upward counterfactuals are
preferred by humans [25, 26]. Nevertheless, we evaluated the impact of
downward counterfactuals. To no surprise, they perform not as well as upward
counterfactuals but still benefit the learning. Similarly, we evaluated the
case when additional random feedback samples are given, which performed even
worse. This highlights that using explanation concepts can provide more
natural interfaces towards the human and provide more benefits than just
simple samples. In this work we have shown that counterfactuals, especially
upward-directed ones, provide a clear benefit from a learning perspective
while giving the human more freedom. We think these results can be seen as
motivation to investigate more explanations concepts.

Realistic oracles. With our implementation of a synthetic oracle, we took a
step to make the synthetic oracle more realistic due to the randomness in
feedback frequency and the reduced optimality of the feedback. This is far
from a perfect simulation of human feedback but the oracle also allowed us to
run experiments with a large sample size in multiple environments with
ablations. We believe that our reduced frequency and optimality are realistic
enough to ensure that the results of our extensions will still hold in
practice.

Interfaces for counterfactual feedback. Throughout our work, we have shown
that counterfactuals are beneficial for learning. However, it is still an open
question how humans would actually give this kind of feedback to the agents.
While the handling of more complex feedback is definitely a complex problem,
one should note there are many instances when humans naturally want to provide
more complex feedback. We argue that, depending on the use case, humans can be
enabled to give complex feedback through better interfaces. For example, an
NLP-based parsing of utterances could extract counterfactuals from humans.
Alternatively, for environments like MiniGrid, one could provide humans with a
graphical interface, where they can not only give feedback but also change the
state (by dragging objects around) to produce counterfactual states.

Feedback Cost Our results show that the inclusion of counterfactuals leads to
faster learning in terms of fewer steps in the environment needed before it is
‘solved‘. This also leads to fewer feedback interactions from humans. While
this is a preferable result, counterfactual feedback could also lead to
additional mental workload by the human. This load was not considered in our
evaluation. However, studies suggest that in many situations humans naturally
want to enrich their feedback with additional explanations (see [1, 2]),
without much thinking. Our method gives humans more flexibility in their
feedback and allows them to harness it. We believe that the additional mental
load depends on the environment and the feedback interface and has to be
evaluated on a case-by-case basis. Additionally, we think it could benefit the
user experience if the user could express his feedback differently.

## Conclusions

We have shown, with the help of synthetic oracle, that the inclusion of upward
counterfactual explanations in TAMER can significantly improve the speed of
learning as compared to simple binary feedback, random feedback, or downward
counterfactual feedback. Both approaches, counterfactuals based on states and
counterfactuals based on actions, show these improvements. Overall
counterfactual actions delivered the lowest optimality gap, speeding up the
learning the most, while counterfactual states still provide benefits over
TAMER without counterfactuals. We tried to circumvent the limitations of the
synthetic oracle with experiments in which the quality of the oracle had been
reduced. The results of these experiments showed that the improvements should
also hold under more realistic conditions. Nevertheless for definite results
further studies with human trainers are needed. Future work will investigate
how users actually use these enhanced feedback interfaces and how costly for
the human they are.

## References

  * [1] S. Krening and K. M. Feigh, “Interaction algorithm effect on human experience with reinforcement learning,” _J. Hum.-Robot Interact._ , vol. 7, no. 2, 2018\.
  * [2] S. Stumpf, V. Rajaram, L. Li, M. Burnett, T. Dietterich, E. Sullivan, R. Drummond, and J. Herlocker, “Toward harnessing user feedback for machine learning,” in _Proc. of the 12th Int. Conf. on Intelligent User Interfaces_ , 2007, p. 82–91.
  * [3] W. B. Knox and P. Stone, “TAMER: Training an agent manually via evaluative reinforcement,” _2008 7th IEEE Int. Conf. on Development and Learning ICDL_ , pp. 292 – 297, 2008.
  * [4] C. Celemin and J. R. del Solar, “COACH: Learning continuous actions from COrrective Advice Communicated by Humans,” _2015 Int. Conf. on Advanced Robotics (ICAR)_ , pp. 581–586, 2015.
  * [5] S. Milani, N. Topin, B. Houghton, W. H. Guss, S. P. Mohanty, K. Nakata, O. Vinyals, and N. S. Kuno, “Retrospective analysis of the 2019 MineRL competition on sample efficient reinforcement learning,” in _Proc. of the NeurIPS 2019 Competition and Demonstration Track_ , 2019.
  * [6] G. Warnell, N. R. Waytowich, V. Lawhern, and P. Stone, “DeepTAMER: interactive agent shaping in high-dimensional state spaces,” in _Proc. of the 32nd AAAI Conference on Artificial Intelligence_ , no. 1, 2018.
  * [7] W. B. Knox and P. Stone, “Combining manual feedback with subsequent MDP reward signals for reinforcement learning,” in _Proc. of the 9th Int. Conf. on Autonomous Agents and Multiagent Systems AAMAS_ , 2010, pp. 5–12.
  * [8] ——, “Reinforcement learning from simultaneous human and MDP reward,” in _Proc. of the 11th Int. Conf. on Autonomous Agents and Multiagent Systems AAMAS_ , 2012, p. 475–482.
  * [9] R. Arakawa, S. Kobayashi, Y. Unno, Y. Tsuboi, and S. Maeda, “DQN-TAMER: Human-in-the-loop reinforcement learning with intractable feedback,” _ArXiv_ , vol. abs/1810.11748, 2018.
  * [10] N. A. Vien, W. Ertel, and T. C. Chung, “Learning via human feedback in continuous state and action spaces,” _Applied Intelligence_ , vol. 39, no. 2, pp. 267–278, 2012.
  * [11] J. MacGlashan, M. K. Ho, R. Loftin, B. Peng, G. Wang, D. L. Roberts, M. E. Taylor, and M. L. Littman, “Interactive learning from policy-dependent human feedback,” in _Proc. of the 34th Int. Conf. on Machine Learning, ICML 2017_ , 2017, p. 2285–2294.
  * [12] S. Griffith, K. Subramanian, J. Scholz, C. L. Isbell, and A. L. Thomaz, “Policy shaping: Integrating human feedback with reinforcement learning,” in _Advances in Neural Information Processing Systems_ , vol. 26, 2013.
  * [13] R. Akrour, M. Schoenauer, and M. Sebag, “Preference-based policy learning,” in _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , 2011, pp. 12–27.
  * [14] L. A. Torrey and M. E. Taylor, “Teaching on a budget: agents advising agents in reinforcement learning,” in _Int. Conf. on Autonomous Agents and Multi-Agent Systems, AAMAS ’13_ , 2013, p. 1053–1060.
  * [15] P. Koppol, H. Admoni, and R. Simmons, “Interaction considerations in learning from humans,” in _Proc. of the Thirtieth Int. Joint Conf. on Artificial Intelligence, IJCAI-21_ , 2021, pp. 283–291.
  * [16] L. Guan, M. Verma, and S. Kambhampati, “Explanation augmented feedback in human-in-the-loop reinforcement learning,” in _ICML Workshop on Human in the Loop Learning (HILL)_ , 2020.
  * [17] C. Lu, B. Huang, K. Wang, J. M. Hernández-Lobato, K. Zhang, and B. Schölkopf, “Sample-efficient reinforcement learning via counterfactual-based data augmentation,” in _Proc. of Neural Information Processing Systems (NeurIPS) Workshop on Offline Reinforcement Learning_ , 2020.
  * [18] P. H. Jin, K. Keutzer, and S. Levine, “Regret minimization for partially observable deep reinforcement learning,” in _Proc. of the 35th Int. Conf. on Machine Learning, ICML 2018_ , 2018, pp. 2342–2351.
  * [19] L. Buesing, T. Weber, Y. Zwols, N. Heess, S. Racanière, A. Guez, and J. Lespiau, “Woulda, coulda, shoulda: Counterfactually-guided policy search,” in _7th Int. Conf. on Learning Representations, ICLR 2019_ , 2019\.
  * [20] J. N. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson, “Counterfactual multi-agent policy gradients,” in _Proc. of the 32nd AAAI Conference on Artificial Intelligence_ , vol. 32, no. 1, 2018.
  * [21] L. Menglin, C. Jing, C. Shaofei, and G. Wei, “A new reinforcement learning algorithm based on counterfactual experience replay,” in _2020 39th Chinese Control Conference (CCC)_ , 2020, pp. 1994–2001.
  * [22] G. Dulac-Arnold, D. Mankowitz, and T. Hester, “Challenges of real-world reinforcement learning,” in _Proc. of the 36th Int. Conf. on Machine Learning (ICML)_ , 2019.
  * [23] R. M. J. Byrne, “Counterfactuals in explainable artificial intelligence (xai): Evidence from human reasoning,” in _Proc. of the Twenty-Eighth Int. Joint Conf. on Artificial Intelligence, IJCAI-19_ , 7 2019, pp. 6276–6282.
  * [24] T. Miller, “Explanation in artificial intelligence: Insights from the social sciences,” _Artificial Intelligence_ , vol. 267, pp. 1–38, 2019.
  * [25] K. Markman, M. McMullen, and R. Elizaga, “Counterfactual thinking, persistence, and performance: A test of the reflection and evaluation model,” _Journal of Experimental Social Psychology_ , pp. 421–428, 2008\.
  * [26] S. Rim and A. Summerville, “How far to the road not taken? the effect of psychological distance on counterfactual direction,” _Personality & social psychology bulletin_, vol. 40, pp. 391–401, 2013.
  * [27] M. Cakmak and A. L. Thomaz, “Optimality of human teachers for robot learners,” in _2010 IEEE 9th Int. Conf. on Development and Learning ICDL_ , 2010, pp. 64–69.
  * [28] S. M. Kakade, “On the sample complexity of reinforcement learning.” Ph.D. dissertation, Gatsby Computational Neuroscience Unit, 2004.
  * [29] R. Agarwal, M. Schwarzer, P. S. Castro, A. Courville, and M. G. Bellemare, “Deep reinforcement learning at the edge of the statistical precipice,” in _35th Conference on Neural Information Processing Systems NeurIPS_ , 2021\.
  * [30] P. Christiano, J. Leike, T. B. Brown, M. Martic, S. Legg, and D. Amodei, “Deep reinforcement learning from human preferences,” in _31st Conference on Neural Information Processing Systems NeurIPS_ , 2017.
  * [31] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _arXiv preprint arXiv:1707.06347_ , 2017\.