# Modeling Human Exploration Through Resource-Rational Reinforcement Learning

Marcel Binz
MPI for Biological Cybernetics
Tübingen, Germany
<EMAIL_ADDRESS>&Eric Schulz
MPI for Biological Cybernetics
Tübingen, Germany
<EMAIL_ADDRESS>
###### Abstract

Equipping artificial agents with useful exploration mechanisms remains a
challenge to this day. Humans, on the other hand, seem to manage the trade-off
between exploration and exploitation effortlessly. In the present article, we
put forward the hypothesis that they accomplish this by making optimal use of
limited computational resources. We study this hypothesis by meta-learning
reinforcement learning algorithms that sacrifice performance for a shorter
description length (defined as the number of bits required to implement the
given algorithm). The emerging class of models captures human exploration
behavior better than previously considered approaches, such as Boltzmann
exploration, upper confidence bound algorithms, and Thompson sampling. We
additionally demonstrate that changing the description length in our class of
models produces the intended effects: reducing description length captures the
behavior of brain-lesioned patients while increasing it mirrors cognitive
development during adolescence.

##  1 Introduction

Knowing how to efficiently balance between exploring unfamiliar parts of an
environment and exploiting currently available knowledge is an essential
ingredient of any intelligent organism. In theory, it is possible to obtain a
Bayes-optimal solution to this exploration-exploitation dilemma by solving an
augmented problem known as a Bayes-adaptive Markov decision process (BAMDP,
Duff, 2003). However, BAMDPs are intractable to solve in general and
analytical solutions are only available for a few special cases (Gittins,
1979). The intractability of this optimal solution prompted researchers to
develop a body of heuristic strategies (Auer et al., 2002; Kaufmann et al.,
2012; Russo et al., 2017; Russo and Van Roy, 2014). Most of these heuristics
can be divided into two broad categories: directed and random exploration
strategies (Wilson et al., 2014; Schulz and Gershman, 2019). Directed
exploration strategies provide bonus rewards that encourage the agent to visit
parts of the environment that ought to be explored, whereas random exploration
strategies inject some form of stochasticity into the policy.

Having access to a vast amount of existing exploration strategies leads to the
question: which of them should we use when building artificial agents? To
answer this question, we may take inspiration from how people approach the
exploration-exploitation dilemma. Human exploration has been studied
extensively in the multi-armed bandit setting (Mehlhorn et al., 2015; Wilson
et al., 2021; Brändle et al., 2021). Prior work indicates that people
substantially deviate from the Bayes-optimal strategy even for the simplest
bandit problems (Steyvers et al., 2009; Zhang and Angela, 2013; Binz and
Endres, 2019). They, however, use uncertainty estimates to intelligently guide
their choices through a combination of both directed and random exploration
(Wilson et al., 2014; Gershman, 2018). The question of when and why
individuals rely on a particular exploration strategy has been under-explored
so far.

We take the first steps towards answering these questions by looking at human
exploration from a resource-rational perspective (Gershman et al., 2015;
Lieder and Griffiths, 2020; Binz et al., 2022). More specifically, we
investigate the hypothesis that people solve the exploration-exploitation
dilemma by making optimal use of limited computational resources. To test this
hypothesis, we devise a family of resource-rational reinforcement learning
algorithms by combining ideas from meta-learning (Bengio et al., 1991;
Schmidhuber et al., 1996) and information theory (Hinton and Van Camp, 1993).
The resulting model – which we call resource-rational RL2 (RR-RL2) –
implements a free-standing reinforcement learning algorithm that achieves
optimal behavior subject to the constraint that it can be implemented with a
given number of bits.

We demonstrate that RR-RL2 captures many aspects of human exploration by
reanalyzing data from three previously conducted psychological studies. First,
we show that it explains human choices in a two-armed bandit task better than
traditional approaches, such as Thompson sampling (Thompson, 1933), upper
confidence bound (UCB) algorithms (Kaufmann et al., 2012), and mixtures
thereof (Gershman, 2018). We then verify that the manipulation of
computational resources in our class of models matches the manipulation of
resources in human subjects in two different contexts. Taken together, these
results enrich our understanding of human exploration and provide insights
into how to improve the exploratory capabilities of artificial agents.

##  2 Methods

We start by describing the general problem setting considered in this article
and its optimal solution, followed by a brief summary of the meta-
reinforcement learning framework. We then show how to augment the standard
meta-reinforcement learning objective with an information-theoretic
constraint, allowing us to construct reinforcement learning algorithms that
trade-off performance against the number of bits required to implement them.

###  2.1 Notation and Preliminaries

Each task considered in this article can be interpreted as a multi-armed
bandit problem. In a $k$-armed bandit problem, an agent repeatedly interacts
with $k$ slot machines that are associated with a reward distribution
$p(r_{t}|a_{t},\omega)$ with unknown parameters $\omega$. In each time-step,
the agent selects an action $a_{t}$ and is provided a reward $r_{t}$ based on
the associated reward distribution.

The goal of an agent is to select actions such that the sum of rewards over a
finite horizon $H$ is maximized. We assume that the agent additionally has
access to a prior distribution $p(\omega)$ over bandit problems that it may
encounter, which can be updated after observing a history of observations
$h_{t}\coloneqq\left(a_{1},r_{1},\ldots,a_{t-1},r_{t-1}\right)$ by applying
Bayes’ rule:

$p(\omega|h_{t})\propto p(\omega)\prod_{m=1}^{t-1}p(r_{m}|a_{m},\omega)$ (1)

The policy that optimally trades-off exploration and exploitation can be
obtained by reasoning how the agent’s beliefs about reward functions evolve
with future observations (Martin, 1967). Formally, this is accomplished by
transforming the original bandit problem into a corresponding BAMDP defined by
the tuple $(\mathcal{H},\mathcal{A},H,T,R)$. In this augmented problem,
$\mathcal{H}$ represents the set of all possible histories, while
$\mathcal{A}$ and $H$ correspond to the action space and the horizon of the
original bandit problem. The transition probabilities $T$ and reward function
$R$ are given by:

$\displaystyle T(h_{t+1}|a_{t},h_{t})$
$\displaystyle=p(r_{t}|a_{t},h_{t})\delta\left[h_{t+1}=\left(h_{t},a_{t},r_{t}\right)\right]$
(2) $\displaystyle R(a_{t},h_{t})$
$\displaystyle=\mathbb{E}_{p(r_{t}|a_{t},h_{t})}\left[r_{t}\right]$ (3)

with the marginal reward probabilities:

$p(r_{t}|a_{t},h_{t})=\int p(r_{t}|a_{t},\omega)p(\omega|h_{t})d\omega$ (4)

The policy that maximizes the sum of rewards in the BAMDP corresponds to the
Bayes-optimal policy for the original bandit problem.

###  2.2 Meta-Reinforcement Learning

While the BAMDP formalism provides a precise recipe for deriving a Bayes-
optimal policy, finding an analytical expression of this policy is typically
not possible. Recent work on meta-reinforcement learning, however, has shown
that it is possible to learn an approximation to it (Wang et al., 2016; Ortega
et al., 2019; Zintgraf et al., 2019). Duan et al. (2016) refer to this
approach as RL2 because it uses a traditional reinforcement learning algorithm
to meta-learn another free-standing reinforcement learning algorithm.

RL2 parametrizes the to-be-learned reinforcement learning algorithm with a
general-purpose function approximator. Typically, this function approximator
takes the form of a recurrent neural network that receives the last action and
reward as inputs, uses them to update its hidden state, and produces a policy
that is conditioned on the new hidden state. Let $\mathbf{W}$ denote the
parameters of this recurrent neural network. In an outer-loop meta-learning
process, the network is then trained on the prior distribution over bandit
problems $p(\omega)$ to find the history-dependent policy
$\pi(a_{t}|h_{t},\mathbf{W})$ that maximizes the sum of obtained rewards. If
the meta-learning procedure has successfully converged to its optimum, RL2
implements a free-standing reinforcement learning algorithm that mimics the
Bayes-optimal policy. Importantly, learning at this stage is fully implemented
through the forward dynamics of the recurrent neural network and no further
updating of its parameters is required.

###  2.3 Resource-Rational RL2

We transform RL2 into a resource-rational algorithm by augmenting its meta-
learning objective with an information-theoretic constraint and refer to this
resource-rational variant as RR-RL2. More precisely, RR-RL2 is obtained by
solving the following optimization problem:

$\displaystyle\max_{\mathbf{\Lambda}}~{}$
$\displaystyle\mathbb{E}_{q(\mathbf{W}|\mathbf{\Lambda})p(\omega)\prod
p(r_{t}|a_{t},\omega)\pi(a_{t}|h_{t},\mathbf{W})}\left[\sum_{t=1}^{H}r_{t}\right]$
s.t.
$\displaystyle\text{KL}\left[q(\mathbf{W}|\mathbf{\Lambda})||p(\mathbf{W})\right]\leq
C$ (5)

The first component of Equation 2.3 corresponds to the standard meta-
reinforcement learning objective, while the second component ensures that the
Kullback–Leibler (KL) divergence between a stochastic parameter encoding
$q(\mathbf{W}|\mathbf{\Lambda})$ and a prior $p(\mathbf{W})$ remains smaller
than some constant $C$. The KL term can be interpreted as the description
length of neural network parameters, i.e., the number of bits required to
store them.111The desired coding length can, for example, be achieved using
bits-back coding (Hinton and Van Camp, 1993) or minimal random coding (Havasi
et al., 2018). RR-RL2 therefore optimally trades-off performance against the
number of bits required to implement the emerging reinforcement learning
algorithm. Note that the objective from Equation 2.3 can also be motivated by
a PAC-Bayes bound on generalization performance to unseen tasks (Yin et al.,
2019; Rothfuss et al., 2020; Jose and Simeone, 2020). While we focus on the
resource-rational interpretation in the present article, we believe that both
of these perspectives are complementary.

In practice, we solve a sample-based approximation of the optimization problem
in Equation 2.3 using a standard on-policy actor-critic algorithm (Mnih et
al., 2016; Wu et al., 2017). We rely on a dual gradient ascent procedure
(Haarnoja et al., 2018) to ensure that the constraint is satisfied. Appendix A
contains a complete description of the network architecture, choices of prior
and encoding distribution, and the meta-learning procedure. A public
implementation of our model and the following analyses is available under
https://github.com/marcelbinz/resource-rational-reinforcement-learning.

Which exploration strategies RR-RL2 implements will partially depend on its
available computational resources. Models with limited resources must
implement strategies that rely on simple computations, such as computing
average rewards or noisy estimates thereof. Models with access to more
resources, on the other hand, can spend some of them to compute more complex
statistics, such as uncertainty estimates, and incorporate these into their
decision-making process. Moreover, what strategies are resource-rational not
only depends on the computational resources of the decision-maker but also on
the characteristics of the particular problem under consideration. Problems
with a short task horizon, for instance, require less exploration and thereby
make exploitation more appealing, while problems with a longer horizon allow
for the application of more sophisticated exploration strategies.

##  3 Modeling Human Exploration

(a) Exploration Strategies | (b) Embedding
---|---
|
Figure 1: Illustration of exploration strategies implemented by RR-RL2 (also
see Equation 6 and the corresponding explanation in the main text). (a) Probit
regression coefficients obtained by fitting the hybrid model to data simulated
by RR-RL2 with varying description lengths (depicted on a logarithmic scale).
The blue line shows the influence of the estimated mean on choices (Boltzmann
exploration), the orange line shows the influence of the option’s uncertainty
estimates (UCB-based exploration), and the green line shows the influence of
the uncertainty-scaled estimated mean (which corresponds to Thompson sampling
in this particular task). (b) UMAP embeddings of probit regression
coefficients for RR-RL2 and human participants.

We now demonstrate that RR-RL2 explains human choices on both a qualitative
and quantitative level. We first show that varying its description length
leads to a set of diverse exploration strategies, allowing us to capture
individual differences in human decision-making. When reanalyzing data from a
two-armed bandit benchmark (Gershman, 2018), we furthermore find that RR-RL2
beats previously considered algorithms in terms of fitting human behavior by a
large margin.

Experimental Design: The behavioral data-set of Gershman (2018) contains
records of $44$ participants who each played $20$ two-armed bandit problems
with an episode length of $H=10$. The mean reward for each arm $a$ was drawn
from $p(\omega_{a})=\mathcal{N}(0,10)$ at the beginning of the task and the
reward in each time-step from
$p(r_{t}|a_{t},\omega)=\mathcal{N}(\omega_{a_{t}},1)$.

Analysis: To analyze the set of emerging exploration strategies, we adopted a
method proposed by Gershman (2018). He assumed that an agent uses Bayes’ rule
as described in Equation 1 to update its beliefs over unobserved parameters.
If prior and reward are both normally distributed, the posterior will also be
normally distributed and the corresponding updating rule is given by the
Kalman filtering equations. Let
$p(\omega_{a}|h_{t})=\mathcal{N}(\mu_{a,t},\sigma_{a,t})$ be the posterior
distribution at time-step $t$. Based on the parameters of this posterior
distribution, he then defined the following probit regression model:

$\displaystyle p(A_{t}=0|h_{t},\mathbf{w})$
$\displaystyle=\mathbf{\Phi}\left(\mathbf{w}_{1}\text{V}_{t}+\mathbf{w}_{2}\text{RU}_{t}+\mathbf{w}_{3}\dfrac{\text{V}_{t}}{\text{TU}_{t}}\right)$
(6) $\displaystyle\text{V}_{t}$ $\displaystyle=\mu_{0,t}-\mu_{1,t}$
$\displaystyle\text{RU}_{t}$ $\displaystyle=\sigma_{0,t}-\sigma_{1,t}$
$\displaystyle\text{TU}_{t}$
$\displaystyle=\sqrt{\sigma_{0,t}^{2}+\sigma_{1,t}^{2}}$

with $\mathbf{\Phi}$ denoting the cumulative distribution function of a
standard normal distribution. Equation 6 is also referred to as the hybrid
model as it contains several known exploration strategies as special cases. We
can recover a Boltzmann-like exploration strategy for
$\mathbf{w}=[\mathbf{w}_{1},0,0]$, a variant of the UCB algorithm for
$\mathbf{w}=[\mathbf{w}_{1},\mathbf{w}_{2},0]$, and Thompson sampling for
$\mathbf{w}=[0,0,1]$.

Fitting the coefficients of the hybrid model to behavioral data allows us to
inspect how much a given agent relied on a particular exploration strategy.
Previously, Gershman (2018) has applied this form of analysis to human data,
which revealed that people rely on a mixture of directed and random
exploration. In this article, we extend this approach to artificial data
generated by RR-RL2.

Results: We trained RR-RL2 with a targeted description length of
$\\{1,2,\ldots,10000\\}$ nats on the same distribution used in the original
experimental study and examined how the description length of these models
influences their exploration behavior using the previously described probit
regression analysis. Figure 1 (a) illustrates the results of this analysis. We
find that RR-RL2 implements a Boltzmann-like exploration strategy for
description lengths between $1$ and $100$ nats. Note that behavior at this
stage is quite noisy as indicated by the small probit regression weights
(average regression coefficient of $0.15$). Beginning from $100$ nats, we
observe a rise of the factor corresponding to Thompson sampling, which
continues to rise until the limit of $10000$ nats. Between $100$ and $1000$
nats, we additionally find minor influences of a Boltzmann-like exploration
strategy (average regression coefficient of $0.19$). For a description length
of $1000$ nats and larger, Boltzmann-like exploration diminishes and is
replaced with minor influences of a UCB-based strategy (average regression
coefficient of $0.23$).

(a) Model Comparison |  (b) Posterior Probabilities
---|---
|
Figure 2: Model comparison results on the two-armed bandit data from Gershman
(2018). (a) Bayesian information criterion (BIC) values for the aggregated
data of all participants. Lower values correspond to a better fit to human
behavior. (b) Posterior probabilities for each model and participant. Higher
values correspond to a better fit to human behavior.

Having established that different styles of exploration emerge in RR-RL2
depending on its description length, we next set out to test how well it
explains human choices. In order to do so, we conducted a Bayesian model
comparison (Bishop, 2006). A detailed summary of our comparison procedure is
provided in Appendix B. We used the Bayesian information criterion (BIC,
Schwarz, 1978) as an approximation to the model evidence. The resulting BIC
values for each candidate model are illustrated in Figure 2 (a). We find that
the BIC value for RR-RL2 is substantially lower compared to that of the hybrid
model ($5562.63$ against $6158.91$) when aggregated across all participants;
all other models provide a less adequate fit to human choices. The majority of
participants ($n=32$) was best described by RR-RL2 and the protected
exceedance probability (PXP), which measures the probability that a particular
model is the most frequent within a set of alternatives (Rigoux et al., 2014),
also favored RR-RL2 decisively (PXP $\approx 1$). We provide a detailed
illustration of the posterior probabilities for each model and participant in
Figure 2 (b).

Finally, we compared the probit regression coefficients of human participants
to the ones of RR-RL2. Figure 1 (b) shows a two-dimensional UMAP embedding
(McInnes et al., 2018) of these coefficients. The figure reveals a set of
diverse exploration strategies within the human population and confirms that
RR-RL2 captures the overall variability in human exploration appropriately.

##  4 Manipulating Computational Resources

RR-RL2 also makes precise predictions about what should happen if
computational resources are actively manipulated. Do these predictions align
with the actual behavior of people? Providing answers to this question is non-
trivial because we cannot simply ask a person to use an algorithm with a
shorter or longer description length. There are, however, two types of studies
that can provide insights. The first type consists of lesion studies that
compare the behavior of healthy participants to that of participants suffering
from brain damage, whereas the second type consists of developmental studies
that investigate how behavior evolves during cognitive development. We next
take a look at an example of each of them and demonstrate that RR-RL2
reproduces their key findings.

###  4.1 Damage to Ventromedial Prefrontal Cortex

(a) Humans | (b) RR-RL2
---|---
|
Figure 3: Probability of selecting low- and high-risks arms in the Iowa
Gambling Task. (a) Human data taken from Bechara et al. (1994). The
probability of selecting an inferior high-risk arm is increased in
participants with vmPFC damage. (b) Data simulated from RR-RL2 with large and
small description length. The probability of selecting an inferior high-risk
arm is increased for models with fewer bits, mirroring the results of the
original study.

There has been a long history of analyzing people with brain lesions in
cognitive neuroscience (Damasio and Damasio, 1989). We focused on a particular
study conducted by Bechara et al. (1994) for the purpose of this article and
predicted that reducing the description length of RR-RL2 should correspond to
the behavior of brain-lesioned patients.

Experimental Design: To probe decision-making in clinical populations, Bechara
et al. (1994) introduced an experimental paradigm called the Iowa Gambling
Task (IGT). The IGT involves $100$ choices in a single four-armed bandit
problem. Two of the arms are high-risk arms, while the other two are low-risk
arms. High-risk arms result in a constant positive reward of $100$ but have a
chance to yield a noisy penalty with an expected value of $125$. Low-risk arms
result in a constant positive reward of $50$ but have a chance to yield a
noisy penalty with an expected value of $25$. A complete list of trials is
printed in Table D1. Bechara et al. (1994) used the IGT to compare the
decision-making of healthy participants to that of participants with
ventromedial prefrontal cortex (vmPFC) damage.

Analysis: The focus of our analysis was the proportion of selected low- and
high-risk arms across the entire experiment. High-risk arms cause an average
loss of $25$ points per trial, while low-risk arms provide an average payoff
of $25$ points per trial. We should therefore expect an agent to select the
superior low-risk arms with higher frequency. Healthy participants are indeed
able to learn about the structure of the task and will after a while start to
sample the superior low-risk arms. Participants with vmPFC damage, however,
continue to sample to the inferior high-risk as illustrated in Figure 3 (a).
This pattern is striking because performance in these subjects remains worse
than chance regardless of how often they interact with the task.

Results: RR-RL2 requires a distribution over bandit problems for meta-
learning, but participants in the IGT only encountered a single bandit task.
Therefore, we cannot directly use the task of the original study for meta-
learning as we have done in the previous example. We instead constructed a
distribution over bandit problems that maintains the key characteristics of
the IGT:

  * •

The positive reward component was independently sampled for each arm from a
uniform distribution with a minimum value of $0$ and a maximum value of $150$.

  * •

The mean across all trials of the negative reward component was also sampled
from a uniform distribution with a minimum value of $0$ and a maximum value of
$150$.

  * •

The negative reward component had an occurrence probability sampled randomly
from a uniform distribution with a minimum value of $0.05$ and a maximum value
of $0.95$.

  * •

We furthermore added additive noise sampled from a zero-mean normal
distribution with a standard deviation of $10$ to the negative reward
component in each time-step.

We trained RR-RL2 with a targeted description length of
$\\{100,200,\ldots,10000\\}$ nats on the previously described distribution.
When tested on the IGT, we find that RR-RL2 replicates the pattern reported by
Bechara et al. (1994). Models with a high description length successfully
solve the task by selecting low-risk arms in the majority of time-steps. If
description length is however sufficiently reduced, RR-RL2 predominately
samples high-risk arms. We illustrate this behavior for two example models in
Figure 3 (b). Figure D2 provides a more detailed picture of how description
length mediates choice behavior.

In summary, our analysis sheds light on why brain-lesioned patients display
below-chance performance in the IGT. Intuitively, any resource-limited agent
must primarily devote its computational resources to things that are easy to
estimate. In the IGT, the deterministic positive reward component is easier to
estimate than the noisy negative component. An agent with significantly
restricted resources will thus focus on the positive component while ignoring
the negative. In turn, the agent will assign higher estimated payoffs to the
inferior high-risk arms and therefore select them more frequently. We found
that RR-RL2 implements this behavior and that reducing its description length
captured participants with lesioned vmPFC.

###  4.2 Developmental Trajectories

(a) Humans | (b) RR-RL2
---|---
|
Figure 4: Illustration of strategic directed and random exploration in the
horizon task. (a) Human data from Somerville et al. (2017). During
adolescence, people start to engage more in strategic directed exploration,
whereas strategic random exploration remains constant over time. (b) Data
simulated from RR-RL2 with varying description lengths. Like in the human
data, we observe an increase in strategic directed exploration, but no change
in strategic random exploration.

People are not born with fully-developed cognitive abilities but instead
develop them during their lifetime. In this section, we tested whether
increasing the description length of RR-RL2 matches the behavioral
trajectories of people as they grow up. To test this hypothesis, we reanalyzed
data collected by Somerville et al. (2017), who studied changes in exploration
behavior between early adolescence and adulthood.

Experimental Design: In their study, Somerville et al. (2017) made use of an
experimental paradigm known as the horizon task (Wilson et al., 2014). Each
task was based on a two-armed bandit problem and involved four forced-choice
trials, followed by either one or six free-choice trials. Participants were
aware of the number of remaining choices and could use this information to
guide their behavior. The mean reward of one of the arms was drawn randomly
from $\\{40,60\\}$, while the mean reward for the other was determined by
sampling the difference to the first arm from $\\{4,8,12,20,30\\}$. The
arrangement of arms as well as the sign of their difference was randomized. In
each time-step, the observed reward was sampled from a normal distribution
with the corresponding mean value and a standard deviation of $8$. The
addition of forced-choice trials allowed to control the amount of information
that was available to participants. They either provided an equal amount of
information for both arms (i.e., two observations each) or an unequal amount
of information (i.e., a single observation from one arm, three from the
other). In total, Somerville et al. (2017) collected data for $147$
participants between the ages of $12.08$ and $28$, completing $160$ bandit
tasks each.

Analysis: Following Somerville et al. (2017), we used the decision in the
first free-choice trial to distinguish between different types of exploration.
In the unequal information condition, a choice was classified as directed
exploration if it corresponded to the option that was observed fewer times
during the forced-choice trials. In the equal information condition, a choice
was classified as random exploration if it corresponded to the option with the
lower estimated mean. We refer to an exploration behavior as strategic if it
occurs more frequently in the long horizon tasks compared to the short horizon
tasks. Somerville et al. (2017) found – as shown in Figure 4 (a) – that
strategic directed exploration emerges during adolescence, whereas strategic
random exploration is age-invariant.

To quantify these effects, they fitted two independent linear regression
models, using the probability of engaging in directed and random exploration
as dependent variables. Both models used age, the corresponding horizon, and
the interaction between the two as regressors. They found a significant effect
of horizon in both conditions, indicating that participants engaged more in
both directed and random exploration in tasks with a longer horizon.
Furthermore, they found a significant interaction effect between horizon and
age for directed exploration but not for random exploration, confirming that
strategic directed exploration increases during cognitive development, while
strategic random exploration remains constant over time.

Results: We trained RR-RL2 with a targeted description length of
$\\{100,200,\ldots,10000\\}$ nats on the same distribution used in the
original experimental study. Figure 4 (b) visualizes how strategic directed
and random exploration change as the description length of RR-RL2 increases.
Matching the main result of the experimental study, we find that strategic
directed exploration increases with description length, while strategic random
exploration remains unaffected. We repeated the previously described
regression analysis on data simulated by RR-RL2 to quantify this conclusion
(replacing age as a regressor with description length). The outcome of this
analysis mirrored the results of the original study. We found a significant
effect of horizon on both directed ($F_{1,194}=56.50,p<0.001,\eta^{2}=0.20$)
and random exploration ($F_{1,194}=6.80,p=0.01,\eta^{2}=0.03$). This means
that RR-RL2 made more exploratory decisions of both types if it was beneficial
to do so. We also found a significant interaction effect between horizon and
description length on directed exploration
($F_{1,194}=17.48,p<0.001,\eta^{2}=0.06$) but not on random exploration
($F_{1,194}=0.02,p=0.89$). These results confirm that description length and
age have comparable qualitative effects on the development of strategic
exploration.

However, when comparing the effect sizes of our analysis to those from the
experimental study, we find that the interaction effect between description
length and horizon on directed exploration only amounts to around half of the
effect between age and horizon. We speculated that part of this difference
comes from a mismatch between the distribution used to train our models and
what kind of tasks people expect in the experiment. People, for instance,
might assume that task rewards are noisier than they are, which would require
more exploratory choices, and, in turn, lead to stronger effects. We tested
this hypothesis by retraining RR-RL2 on the same distribution but with the
standard deviation of the reward noise increased by $50\%$. While this
modification increased the effect size of the interaction effect on directed
exploration, it did not close the gap entirely, suggesting that there are
additional – currently undiscovered – factors that contribute to the
development of strategic directed exploration during adolescence. Furthermore,
we found that, while strategic random exploration was unaffected by both age
and description length, humans had a higher base rate of engaging in random
exploration than our models. We, however, believe that this issue could be
resolved by adding an $\varepsilon$-greedy error model to our models as doing
so would naturally increase the base rate of random exploration.

##  5 General Discussion

The exploration-exploitation dilemma is one of the core challenges in
reinforcement learning. How do humans arbitrate between exploration and
exploitation, and which kind of exploration strategies do they engage in? We
have put forward the hypothesis that people tackle this problem in a resource-
rational manner. To test this hypothesis, we proposed a method for meta-
learning reinforcement learning algorithms with limited description length.
The resulting class of models – which we coined RR-RL2 – makes precise
predictions about how people make decisions. We have put these predictions to
a rigorous test by comparing our model to data from three psychological
studies. RR-RL2 displayed key elements of human decision-making in all three
of them:

  1. 1.

It captured human exploration in a two-armed bandit task on both a qualitative
and quantitative level.

  2. 2.

Reducing its description length aligned with decision-making in brain-lesioned
patients.

  3. 3.

Increasing its description length reflected changes in exploration behavior
attributed cognitive development.

In summary, our results demonstrate that it is possible to meta-learn
resource-rational reinforcement learning algorithms and that human exploration
is well-characterized by these very algorithms.

###  5.1 Limitations and Future Work

We have focused on comparing RR-RL2 to human exploration in the simple multi-
armed bandit setting. In the real world, however, people face much more
sophisticated challenges that call for a richer repertoire of exploration
strategies (Schulz et al., 2019; Brändle et al., 2021). This criticism is not
necessarily a shortcoming of the proposed model, which could in principle be
applied to more complex tasks, but rather one regarding the experimental
research in cognitive psychology, which has predominately focused on multi-
armed bandit problems. In future work, we intend to develop new experimental
paradigms that allow us to compare RR-RL2 against human behavior in more
complex settings. Potential paradigms may include contextual bandits, grid
world problems, and multi-agent scenarios.

RR-RL2 also places a constraint on a particular type of computational
resource: the description length of the reinforcement learning algorithm in
use. People, on the other hand, are subject to a variety of additional
computational constraints. They can, for instance, only run algorithms with
finite computation time or only store a restricted amount of chunks in their
short-term memory (Collins et al., 2014). Future work should aim to unify all
of these constraints in a common framework.

It would also be interesting to investigate how RR-RL2 could be implemented in
a biologically plausible way. We believe that replacing the standard recurrent
neural networks used in this article with spiking neural networks could
provide one promising path towards this goal. Earlier work of Bellec et al.
(2018) showed that it is indeed possible to train spiking neural networks in a
meta-learning setting and would therefore provide an excellent starting point
for this endeavor.

Finally, there are many alternative ways of how one could apply meta-learning
to our setting. It is, for example, possible to meta-learn hyperparameters of
standard reinforcement learning algorithms (Doya, 2002; Luksys et al., 2009),
or to use model-agnostic meta-learning to find optimal weight initializations
for neural networks that are trained by gradient descent (Finn et al., 2017).
Future work should compare these and other models against each other. For this
to be effective, we believe that a set of commonly-accepted benchmarks needs
to be established.

###  5.2 Conclusion

Many applications could benefit from the availability of human-like agents.
Having access to such agents may be especially valuable in cooperative self-
play scenarios, where training with them is crucial for successful
coordination with people (Carroll et al., 2019; Strouse et al., 2021). The
traditional path towards constructing agents that learn and think like people
is to take inspiration from the cognitive processes of the human mind and
incorporate them into existing systems (Lake et al., 2017). In this article,
we have pursued a different approach. Instead of hard-coding cognitive
processes directly into our agents, we have identified two computational
principles – meta-learning and resource rationality – that give rise to many
aspects of human behavior. The presented approach is very general, easy to
adapt to new domains, and can be scaled to more complex problem settings
without major modifications.

Finally, we want to emphasize that low description lengths might not only be a
biological necessity, but also a feature (Gigerenzer et al., 1999; Zador,
2019). Implementing an algorithm in just a few bits acts as a strong form of
regularization and could, in turn, produce exploration strategies that are
applicable across domains. Hence, we believe that constructing artificial
systems with such constraints could lead us towards more generally capable
agents.

## Acknowledgments and Disclosure of Funding

This work was funded by the Max Planck Society, the Volkswagen Foundation, as
well as the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation)
under Germany’s Excellence Strategy–EXC2064/1–390727645.

## References

  * Akaike (1974) Hirotugu Akaike.  A new look at the statistical model identification.  _IEEE transactions on automatic control_ , 19(6):716–723, 1974.
  * Auer et al. (2002) Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47(2-3):235–256, 2002.
  * Bechara et al. (1994) Antoine Bechara, Antonio R Damasio, Hanna Damasio, and Steven W Anderson.  Insensitivity to future consequences following damage to human prefrontal cortex.  _Cognition_ , 50(1-3):7–15, 1994.
  * Bellec et al. (2018) Guillaume Bellec, Darjan Salaj, Anand Subramoney, Robert Legenstein, and Wolfgang Maass.  Long short-term memory and learning-to-learn in networks of spiking neurons.  _Advances in neural information processing systems_ , 31, 2018.
  * Bengio et al. (1991) Y Bengio, S Bengio, and J Cloutier.  Learning a synaptic learning rule.  In _IJCNN-91-Seattle International Joint Conference on Neural Networks_ , volume 2, pages 969–vol. IEEE, 1991.
  * Binz and Endres (2019) Marcel Binz and Dominik Endres.  Where do heuristics come from?  In _Proceedings of the 41th Annual Meeting of the Cognitive Science Society_ , pages 1402–1408, 2019.
  * Binz et al. (2022) Marcel Binz, Samuel J Gershman, Eric Schulz, and Dominik Endres.  Heuristics from bounded meta-learned inference.  _Psychological Review_ , (Advance online publication), 2022\.
  * Bishop (2006) Christopher M Bishop.  Machine learning and pattern recognition.  _Information science and statistics. Springer, Heidelberg_ , 2006\.
  * Brändle et al. (2021) Franziska Brändle, Marcel Binz, and Eric Schulz.  Exploration beyond bandits.  2021\.
  * Carroll et al. (2019) Micah Carroll, Rohin Shah, Mark K Ho, Tom Griffiths, Sanjit Seshia, Pieter Abbeel, and Anca Dragan.  On the utility of learning about humans for human-ai coordination.  _Advances in Neural Information Processing Systems_ , 32:5174–5185, 2019.
  * Cho et al. (2014) Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio.  Learning phrase representations using rnn encoder-decoder for statistical machine translation.  _arXiv preprint arXiv:1406.1078_ , 2014.
  * Collins et al. (2014) Anne GE Collins, Jaime K Brown, James M Gold, James A Waltz, and Michael J Frank.  Working memory contributions to reinforcement learning impairments in schizophrenia.  _Journal of Neuroscience_ , 34(41):13747–13756, 2014.
  * Damasio and Damasio (1989) H. Damasio and A.R. Damasio.  _Lesion Analysis in Neuropsychology_.  Oxford University Press, 1989.
  * Doya (2002) Kenji Doya.  Metalearning and neuromodulation.  _Neural networks_ , 15(4-6):495–506, 2002.
  * Duan et al. (2016) Yan Duan, John Schulman, Xi Chen, Peter L Bartlett, Ilya Sutskever, and Pieter Abbeel.  Rl 2: Fast reinforcement learning via slow reinforcement learning.  _arXiv preprint arXiv:1611.02779_ , 2016.
  * Duff (2003) Michael O Duff.  Optimal learning: Computational procedures for bayes-adaptive markov decision processes.  2003\.
  * Eysenbach et al. (2021) Ben Eysenbach, Russ R Salakhutdinov, and Sergey Levine.  Robust predictable control.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Finn et al. (2017) Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _International conference on machine learning_ , pages 1126–1135. PMLR, 2017.
  * Gelman et al. (1995) Andrew Gelman, John B Carlin, Hal S Stern, and Donald B Rubin.  _Bayesian data analysis_.  Chapman and Hall/CRC, 1995.
  * Gershman (2018) Samuel J Gershman.  Deconstructing the human algorithms for exploration.  _Cognition_ , 173:34–42, 2018.
  * Gershman et al. (2015) Samuel J Gershman, Eric J Horvitz, and Joshua B Tenenbaum.  Computational rationality: A converging paradigm for intelligence in brains, minds, and machines.  _Science_ , 349(6245):273–278, 2015.
  * Gigerenzer et al. (1999) G. Gigerenzer, P.M. Todd, and ABC Research Group.  _Simple Heuristics that Make Us Smart_.  Oxford University Press, 1999.
  * Gittins (1979) John C Gittins.  Bandit processes and dynamic allocation indices.  _Journal of the Royal Statistical Society. Series B (Methodological)_ , pages 148–177, 1979.
  * Haarnoja et al. (2018) Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al.  Soft actor-critic algorithms and applications.  _arXiv preprint arXiv:1812.05905_ , 2018.
  * Havasi et al. (2018) Marton Havasi, Robert Peharz, and José Miguel Hernández-Lobato.  Minimal random code learning: Getting bits back from compressed model parameters.  In _International Conference on Learning Representations_ , 2018.
  * Hinton and Van Camp (1993) Geoffrey E Hinton and Drew Van Camp.  Keeping the neural networks simple by minimizing the description length of the weights.  In _Proceedings of the sixth annual conference on Computational learning theory_ , pages 5–13, 1993.
  * Jose and Simeone (2020) Sharu Theresa Jose and Osvaldo Simeone.  Transfer meta-learning: Information-theoretic bounds and information meta-risk minimization, 2020.
  * Kaufmann et al. (2012) Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier.  On bayesian upper confidence bounds for bandit problems.  In _Artificial intelligence and statistics_ , pages 592–600, 2012\.
  * Kingma and Welling (2013) Diederik P Kingma and Max Welling.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_ , 2013.
  * Kingma et al. (2015) Durk P Kingma, Tim Salimans, and Max Welling.  Variational dropout and the local reparameterization trick.  _Advances in neural information processing systems_ , 28:2575–2583, 2015.
  * Lake et al. (2017) Brenden M Lake, Tomer D Ullman, Joshua B Tenenbaum, and Samuel J Gershman.  Building machines that learn and think like people.  _Behavioral and brain sciences_ , 40, 2017.
  * Levine (2018) Sergey Levine.  Reinforcement learning and control as probabilistic inference: Tutorial and review.  _arXiv preprint arXiv:1805.00909_ , 2018.
  * Lieder and Griffiths (2020) Falk Lieder and Thomas L Griffiths.  Resource-rational analysis: Understanding human cognition as the optimal use of limited computational resources.  _Behavioral and Brain Sciences_ , 43, 2020.
  * Luksys et al. (2009) Gediminas Luksys, Wulfram Gerstner, and Carmen Sandi.  Stress, genotype and norepinephrine in the prediction of mouse behavior using reinforcement learning.  _Nature neuroscience_ , 12(9):1180–1186, 2009\.
  * Martin (1967) James John Martin.  _Bayesian decision problems and Markov chains_.  Wiley, 1967.
  * McInnes et al. (2018) Leland McInnes, John Healy, and James Melville.  Umap: Uniform manifold approximation and projection for dimension reduction.  _arXiv preprint arXiv:1802.03426_ , 2018.
  * Mehlhorn et al. (2015) Katja Mehlhorn, Ben R Newell, Peter M Todd, Michael D Lee, Kate Morgan, Victoria A Braithwaite, Daniel Hausmann, Klaus Fiedler, and Cleotilde Gonzalez.  Unpacking the exploration–exploitation tradeoff: A synthesis of human and animal literatures.  _Decision_ , 2(3):191, 2015.
  * Mnih et al. (2016) Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu.  Asynchronous methods for deep reinforcement learning.  In _International conference on machine learning_ , pages 1928–1937. PMLR, 2016.
  * Molchanov et al. (2017) Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov.  Variational dropout sparsifies deep neural networks.  In _International Conference on Machine Learning_ , pages 2498–2507. PMLR, 2017.
  * Ortega et al. (2019) Pedro A Ortega, Jane X Wang, Mark Rowland, Tim Genewein, Zeb Kurth-Nelson, Razvan Pascanu, Nicolas Heess, Joel Veness, Alex Pritzel, Pablo Sprechmann, et al.  Meta-learning of sequential strategies.  _arXiv preprint arXiv:1905.03030_ , 2019.
  * Rigoux et al. (2014) Lionel Rigoux, Klaas Enno Stephan, Karl J Friston, and Jean Daunizeau.  Bayesian model selection for group studies—revisited.  _Neuroimage_ , 84:971–985, 2014.
  * Rothfuss et al. (2020) Jonas Rothfuss, Vincent Fortuin, and Andreas Krause.  Pacoh: Bayes-optimal meta-learning with pac-guarantees.  _arXiv preprint arXiv:2002.05551_ , 2020.
  * Russo and Van Roy (2014) Daniel Russo and Benjamin Van Roy.  Learning to optimize via information-directed sampling.  In _Advances in Neural Information Processing Systems_ , pages 1583–1591, 2014.
  * Russo et al. (2017) Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen.  A tutorial on thompson sampling.  _arXiv preprint arXiv:1707.02038_ , 2017.
  * Schmidhuber et al. (1996) Juergen Schmidhuber, Jieyu Zhao, and MA Wiering.  Simple principles of metalearning.  _Technical report IDSIA_ , 69:1–23, 1996.
  * Schulz and Gershman (2019) Eric Schulz and Samuel J Gershman.  The algorithmic architecture of exploration in the human brain.  _Current opinion in neurobiology_ , 55:7–14, 2019.
  * Schulz et al. (2019) Eric Schulz, Rahul Bhui, Bradley C Love, Bastien Brier, Michael T Todd, and Samuel J Gershman.  Structured, uncertainty-driven exploration in real-world consumer choice.  _Proceedings of the National Academy of Sciences_ , 116(28):13903–13908, 2019.
  * Schwarz (1978) Gideon Schwarz.  Estimating the dimension of a model.  _The annals of statistics_ , pages 461–464, 1978.
  * Somerville et al. (2017) Leah H Somerville, Stephanie F Sasse, Megan C Garrad, Andrew T Drysdale, Nadine Abi Akar, Catherine Insel, and Robert C Wilson.  Charting the expansion of strategic exploratory behavior during adolescence.  _Journal of experimental psychology: general_ , 146(2):155, 2017.
  * Steyvers et al. (2009) Mark Steyvers, Michael D Lee, and Eric-Jan Wagenmakers.  A bayesian analysis of human decision-making on bandit problems.  _Journal of Mathematical Psychology_ , 53(3):168–179, 2009.
  * Strouse et al. (2021) DJ Strouse, Kevin McKee, Matt Botvinick, Edward Hughes, and Richard Everett.  Collaborating with humans without human data.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Thompson (1933) William R Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3/4):285–294, 1933.
  * Wang et al. (2016) Jane X Wang, Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel Z Leibo, Remi Munos, Charles Blundell, Dharshan Kumaran, and Matt Botvinick.  Learning to reinforcement learn.  _arXiv preprint arXiv:1611.05763_ , 2016.
  * Wilson et al. (2014) Robert C Wilson, Andra Geana, John M White, Elliot A Ludvig, and Jonathan D Cohen.  Humans use directed and random exploration to solve the explore–exploit dilemma.  _Journal of Experimental Psychology: General_ , 143(6):2074, 2014.
  * Wilson et al. (2021) Robert C Wilson, Elizabeth Bonawitz, Vincent D Costa, and R Becket Ebitz.  Balancing exploration and exploitation with information and randomization.  _Current Opinion in Behavioral Sciences_ , 38:49–56, 2021\.
  * Wu et al. (2017) Yuhuai Wu, Elman Mansimov, Roger B Grosse, Shun Liao, and Jimmy Ba.  Scalable trust-region method for deep reinforcement learning using kronecker-factored approximation.  _Advances in neural information processing systems_ , 30:5279–5288, 2017.
  * Yin et al. (2019) Mingzhang Yin, George Tucker, Mingyuan Zhou, Sergey Levine, and Chelsea Finn.  Meta-learning without memorization.  _arXiv preprint arXiv:1912.03820_ , 2019.
  * Zador (2019) Anthony M Zador.  A critique of pure learning and what artificial neural networks can learn from animal brains.  _Nature communications_ , 10(1):1–7, 2019.
  * Zhang and Angela (2013) Shunan Zhang and J Yu Angela.  Forgetful bayes and myopic planning: Human learning and decision-making in a bandit setting.  In _Advances in neural information processing systems_ , pages 2607–2615, 2013.
  * Zintgraf et al. (2019) Luisa Zintgraf, Kyriacos Shiarlis, Maximilian Igl, Sebastian Schulze, Yarin Gal, Katja Hofmann, and Shimon Whiteson.  Varibad: A very good method for bayes-adaptive deep rl via meta-learning.  _arXiv preprint arXiv:1910.08348_ , 2019.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes] See Section 5.1.

    3. (c)

Did you discuss any potential negative societal impacts of your work? [No]
There are no immediate negative societal impacts.

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [N/A]

    2. (b)

Did you include complete proofs of all theoretical results? [N/A]

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [No]
We did not provide code at the time of the initial submission, but will make
it publicly available once the paper is accepted.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes] Information to reproduce our results is presented
in the main text and in Appendix A.

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes] We fitted Bayesian linear regression models
mapping description length of a model to the measure of interest and report
the resulting uncertainty over the mean (see for example Figures 1, 4 and D2).
This method assumes that models with a similar description length score
similar on the respective measure.

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] No special
compute resources were used during this project. Models were trained using
standard CPUs on an internal cluster.

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes]

    2. (b)

Did you mention the license of the assets? [N/A]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [N/A]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A] We used existing data from experiments
conducted in previous work. This information can be found in the original
articles.

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A] We used existing data from
experiments conducted in previous work. This information can be found in the
original articles.

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A] We used existing data from
experiments conducted in previous work. This information can be found in the
original articles.

##  Appendix A Meta-Learning Details

###  A.1 Meta-Learning Procedure

We employed a standard on-policy actor-critic procedure [Mnih et al., 2016, Wu
et al., 2017] to optimize a sample-based approximation of Equation 2.3 using
the Adam optimizer with a learning rate of $3\text{\times}{10}^{-4}$. We
simultaneously updated a dual parameter to satisfy the constraint on
description length as suggested in prior work [Haarnoja et al., 2018,
Eysenbach et al., 2021]. Models were trained on one million batches of size
$32$. By the end of meta-learning, all models have converged. We additionally
scaled rewards to roughly fall within the range of $[-1,1]$ to further
stabilize training. Pseudocode for the meta-learning procedure is provided in
Algorithm 1.

Algorithm 1 Meta-Learning Procedure

Initialize $\mathbf{\Lambda}$ and $\beta$

for $n=1$ to $N$ do

$~{}\omega~{}\sim p(\omega)$

$\mathbf{W}\sim q(\mathbf{W}|\mathbf{\Lambda})$

$a_{0},r_{0},h_{0}$ = model.init()

for $t=1$ to $H$ do

$h_{t},V_{t},\pi(a_{t}|h_{t},\mathbf{W})$ =
model.forward$\left(a_{t-1},r_{t-1},h_{t-1}\right)$

$a_{t}\sim\pi(a_{t}|h_{t},\mathbf{W})$

$r_{t}\sim p(r_{t}|a_{t},\omega)$

end for

$\mathcal{L}_{\text{dual}}~{}\leftarrow-\beta\left(\text{KL}\left[q(\mathbf{W}|\mathbf{\Lambda})||p(\mathbf{W})\right]-C\right)$

$\mathcal{L}_{\text{critic}}\leftarrow 0$

$\mathcal{L}_{\text{actor}}\leftarrow 0$

for $t=1$ to $H$ do

$\mathcal{L}_{\text{critic}}\leftarrow\mathcal{L}_{\text{critic}}+\left(r_{t}+V_{t+1}-V_{t}\right)^{2}$

$\mathcal{L}_{\text{actor}}\leftarrow\mathcal{L}_{\text{actor}}-\left(r_{t}+V_{t+1}-V_{t}\right)\log\pi(a_{t}|h_{t},\mathbf{W})$

end for

$\mathbf{\Lambda}\leftarrow\mathbf{\Lambda}-\alpha\nabla_{\mathbf{\Lambda}}\left(H^{-1}\left(\mathcal{L}_{\text{critic}}+\mathcal{L}_{\text{actor}}\right)+\beta\text{KL}\left[q(\mathbf{W}|\mathbf{\Lambda})||p(\mathbf{W})\right]\right)$

$\beta~{}\leftarrow\beta-\alpha\nabla_{\beta}\mathcal{L}_{\text{dual}}$

end for

###  A.2 Model Architecture

The model architecture consists of a single gated recurrent unit (GRU, Cho et
al., 2014) layer with a hidden size of $128$. Inputs to this GRU layer
correspond to the action and reward from the previous time-step. Its outputs
were then transformed by two linear layers, projecting to the policy and value
estimate respectively.

###  A.3 Prior and Encoding Distributions

The prior over network weights corresponds to a variational dropout prior
[Kingma et al., 2015]. The encoding distribution is parametrized by a set of
independent normal distributions over network weights. We adopted the
approximation suggested by Molchanov et al. [2017] to estimate the KL
divergence between the encoding and prior distribution and obtained gradients
with respect to $\mathbf{\Lambda}$ using the reparametrization trick [Kingma
and Welling, 2013].

##  Appendix B Bayesian Model Comparison

In the main text, we conducted a Bayesian model comparison to evaluate how
well each model fitted the behavioral data from the two-armed bandit task. For
this comparison, we computed the posterior probability that participant $i$
with corresponding data $\mathcal{D}_{i}$ used model $m$ via Bayes’ theorem:

$p(m|\mathcal{D}_{i})\propto p(\mathcal{D}_{i}|m)p(m)$ (7)

We assumed a uniform prior over models and approximated the model evidence
with the Bayesian information criterion:

$\log
p(\mathcal{D}_{i}|m)\approx-\frac{1}{2}|\theta|\log(NH)+\max_{\theta}\sum_{n=1}^{N}\sum_{t=1}^{H}\log
p(A_{t}^{i,n}=a_{t}^{i,n}|h_{t}^{i,n},\theta,m)$ (8)

where $N$ is the total number of tasks, $H$ is the number of trials within
each task, and $|\theta|$ is the number of fitted parameters. We use
$a_{t}^{i,n}$ and $h_{t}^{i,n}$ to denote the action chosen and the history
observed by participant $i$ in task $n$ and trial $t$. The policy of our
baseline models is directly given by Equation 6. For RL2 and RR-RL2, we
additionally assumed an $\varepsilon$-greedy error model:

$p(A_{t}=0|h_{t},\theta,m)=(1-\varepsilon)\pi(A_{t}=0|h_{t},\theta,m)+0.5\varepsilon$
(9)

Furthermore, we approximated the integral over neural network weights with a
Monte Carlo approximation of $S=10$ samples:

$\displaystyle\pi(A_{t}=0|h_{t},\theta,m)\approx\frac{1}{S}\sum_{s=1}^{S}\pi(A_{t}=0|h_{t},\mathbf{W}_{s},\theta)\qquad\qquad\mathbf{W}_{s}\sim
q(\mathbf{W}|\mathbf{\Lambda})$ (10)

In addition to the two meta-learning models, we considered several baseline
algorithms within our model comparison procedure. These include the hybrid
model from Equation 6, Thompson sampling, an upper confidence bound algorithm,
and a Boltzmann-like exploration strategy. Note that our baseline algorithms
can be obtained by restricting a sub-set of parameters in the hybrid model to
be zero. Table B1 specifies fitted parameters $\theta$ for each model and
their corresponding search domains. We applied a simple grid search procedure
over the values given in Table B1 to obtain the maximum likelihood estimate of
parameters for RL2 and RR-RL2. Parameters of the baseline models were
optimized using a Newton-Raphson algorithm.

Table B1: Fitted parameters in each model, together with their corresponding search domains. Model | Parameters | Domain
---|---|---
RR-RL2 | $\varepsilon$ | $\\{0.01,0.02,\ldots,1\\}$
| $C$ | $\\{1,2,\ldots,10000\\}$
Hybrid | $\mathbf{w}_{1},\mathbf{w}_{2},\mathbf{w}_{3}$ | continuous
Boltzmann | $\mathbf{w}_{1}$ | continuous
UCB | $\mathbf{w}_{1},\mathbf{w}_{2}$ | continuous
Thompson | $\mathbf{w}_{3}$ | continuous
RL2 | $\varepsilon$ | $\\{0.01,0.02,\ldots,1\\}$

##  Appendix C Two-Armed Bandit Task

Models were trained as described in Appendix A. Figure C1 (a) confirms that
performance improves as description length is increased. Figure C1 (b)
verifies that our models achieved their targeted description length.

(a) Performance | (b) Description Length
---|---
|
Figure C1: Performance and description lengths in the two-armed bandit task.
(a) Regrets for models with varying description lengths. Depicted on a
logarithmic scale to ensure comparability with Figure 1. The solid line shows
a moving average over a window of fifty. (b) Targeted description lengths $C$
plotted against description lengths of the converged models.

###  C.1 Model Comparison Based on AIC

We complemented our Bayesian model comparison from the main text with a model
comparison that relies on the Akaike information criterion (AIC, Akaike,
1974):

$\text{AIC}=2|\theta|-2\max_{\theta}\sum_{n=1}^{N}\sum_{t=1}^{H}\log
p(A_{t}^{i,n}=a_{t}^{i,n}|h_{t}^{i,n},\theta,m)$ (11)

This measure offers a simple approximation to the out-of-sample predictive
accuracy of a model [Gelman et al., 1995]. Figure C2 visualizes the AIC values
for each model on the aggregated data of all participants. The results of this
analysis are fully consistent with the results based on BIC reported in the
main text.

Figure C2: Akaike information criterion (AIC) values for the two-armed bandit
data from Gershman [2018]. Lower values correspond to a better fit to human
behavior.

##  Appendix D Iowa Gambling Task

Models were trained as described in Appendix A. In addition, we assumed a
discount factor of $\gamma=0.9$ for this set of experiments. A geometric
discount factor can be interpreted as a modification to the task dynamics such
that an agent believes to reach a terminal state with probability $1-\gamma$
Levine [2018]. We used this interpretation of the discount factor to model
that participants in the IGT are not informed about the duration of the task.

Figure D1 (a) confirms that performance improves as description length is
increased. Figure D1 (b) verifies that our models achieved their targeted
description length. Table D1 contains a trial-wise overview of the IGT. Figure
D2 depicts the probability of selecting low- and high-risks arms for all
description lengths.

(a) Performance | (b) Description Length
---|---
|
Figure D1: Performance and description lengths in the meta-learning version of
the Iowa Gambling Task. (a) Regrets for models with varying description
lengths. The solid line shows the mean prediction of a Bayesian polynomial
regression model. Shaded contours represent the standard deviation of the
mean. (b) Targeted description lengths $C$ plotted against description lengths
of the converged models. Table D1: Example of ten consecutive trials in the
Iowa Gambling Task. We assume ten blocks of ten trials each. The order of
trials within each block is randomized. The top row for each arm shows the
deterministic positive component, while the bottom row shows the noisy
negative component.

Trial |  Trial |  Trial |  Trial |  Trial |  Trial |  Trial |  Trial |  Trial |  Trial |
---|---|---|---|---|---|---|---|---|---|---
Arm |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10
1 |  $+100$ |  $+100$ |  $+100$ |  $+100$ |  $+100$ |  $+100$ |  $+100$ |  $+100$ |  $+100$ |  $+100$
|  $0$ |  $0$ |  $-150$ |  $0$ |  $-300$ |  $0$ |  $-200$ |  $0$ |  $-250$ |  $-350$
2 |  $+100$ |  $+100$ |  $+100$ |  $+100$ |  $+100$ |  $+100$ |  $+100$ |  $+100$ |  $+100$ |  $+100$
|  $0$ |  $0$ |  $0$ |  $0$ |  $0$ |  $0$ |  $0$ |  $0$ |  $-1250$ |  $0$
3 |  $+50$ |  $+50$ |  $+50$ |  $+50$ |  $+50$ |  $+50$ |  $+50$ |  $+50$ |  $+50$ |  $+50$
|  $0$ |  $0$ |  $-50$ |  $0$ |  $-50$ |  $0$ |  $-50$ |  $0$ |  $-50$ |  $-50$
4 |  $+50$ |  $+50$ |  $+50$ |  $+50$ |  $+50$ |  $+50$ |  $+50$ |  $+50$ |  $+50$ |  $+50$
|  $0$ |  $0$ |  $0$ |  $0$ |  $0$ |  $0$ |  $0$ |  $0$ |  $0$ |  $-250$

Figure D2: Probability of selecting low- and high-risks arms in the Iowa
Gambling Task for all description lengths. Mean choice probabilities are
illustrated as solid lines obtained by fitting a Bayesian polynomial
regression model to the underlying data. Shaded contours represent the
standard deviation of the mean.

##  Appendix E Horizon Task

Models were trained as described in Appendix A. In addition, models received a
binary value encoding the horizon of the current task. Like the humans in the
experimental study, they could use this information to guide their exploration
behavior. We unrolled the network during the forced-choice trials by providing
it with the externally specified actions and rewards. We did not use the
forced-choice trials to update the parameters of the network.

Figure E1 (a) confirms that performance improves as description length is
increased. Figure E1 (b) verifies that our models achieved their targeted
description length.

(a) Performance | (b) Description Length
---|---
|
Figure E1: Performance and description lengths in the horizon task. (a)
Regrets for models with varying description lengths. The solid line shows the
mean prediction of a Bayesian polynomial regression model. Shaded contours
represent the standard deviation of the mean. (b) Targeted description lengths
$C$ plotted against description lengths of the converged models.


# Performance of Uncoded Implementation of Grover’s Algorithm on Today’s
Quantum Processors

Yunos El Kaderi∗† and Andreas Honecker∗ and Iryna Andriyanova† ∗LPTM UMR8089
Laboratory and †ETIS UMR8051 Laboratory
CY Cergy Paris University, ENSEA, CNRS
Cergy, France

###### Abstract

This work tests the performance of Grover’s search circuits on some IBM
superconducting quantum devices in case of the size of search space $N=2^{4}$
and $N=2^{5}$. Ideally, we expect to get an outcome probability distribution
that is clearly peaked at the goal (marked) state. However, the quantum
circuit executed on real devices is vulnerable to noise which leads to
fluctuations in the results. The contributions of the paper are therefore the
following: a) it presents two new Grover’s search circuits for $N=16$ which
were not yet reported in the state of the art; b) it shows performance
difference between simulation results and results obtained on real devices; c)
it shows the need of adding error-correction on the circuit for $N\geq 2^{5}$.

##  I Introduction

Quantum computing has become one of the hottest topics of the last decade in
physics, mathematics and computer science fields. This comes from the
deployment of Noisy Intermediate Scale Quantum (NISQ) devices, that allow to
accelerate execution of a number of algorithms. In contrast to Large Scale
Quantum (LSQ) systems, NISQ devices are not based on fault-tolerant quantum
circuits that use error-correction codes, but make use of error mitigation
techniques.

It is agreed that quantum error correction will play an essential role in
development of LSQ systems. A lot of literature is devoted to the topic, and
the research field is quickly developing in last years [1, 2]. It would be
also interesting to investigate whether error-control coding might be useful
for NISQ technologies. To the best of our knowledge, no tests with the use of
error correction have been performed on NISQ devices until very recently. At
the end of 2022, the authors of [3] have reported a performance improvement
while using a [[4,2,2]] error-detection code.

The goal of this work is to show performance limitations of quantum algorithms
implemented on available NISQ devices, and to discuss their improvements,
possibly with the use of error correction, in line with recent results from
[3]. For better understanding, we are going to focus on a particular case of
the Grover’s search algorithm (GSA). This algorithm has been suggested in [4]
to search for a marked element over an unsorted dataset and theoretically
outperforms classical search algorithms (the GSA has complexity growing as
$\sqrt{N}$ with the dataset size $N$, while the best classical search
algorithm behaves as $O(N)$). An information-theoretic analysis of the GSA can
be found in [5].

The reason of choosing the GSA is two-fold. Firstly, it makes part of the most
common algorithms used for tests on NISQ devices since the last two years, and
a number of references is available for a benchmark. Secondly, the Grover’s
algorithm is the one with the largest depth of quantum circuit, therefore it
is the most sensitive to noise [6]. In fact, there exist recent publications
presenting results on real devices where the noise overshadows the signal.
This observation will be discussed later in the paper.

The paper is organized as follows. Section II presents the Grover’s search
algorithm, one circuit implementation from the state of the art and two
circuits suggested by the authors of the paper. Section III presents numerical
results obtained by running the circuits over NISQ devices and Section IV
concludes the paper. It is to note that the circuits have been first run on
the Qiskit simulator [7] and then on IBM quantum devices of $7$ and $27$
qubits.

###  I-A State of the art

NISQ implementations. Among a large amount of results on the NISQ
implementation, appeared in the last several years, let us report the most
relevant tests of the Grover’s algorithm. A 4-qubit String Detection Problem
(SDP) circuit has been introduced and tested in [8], for a multi-target
search, both on simulator and on quantum devices. It is to mention the GSA
with $N=8$, reported there, first failed to find correct marked states of the
system when carried on quantum devices, but it further succeeded with a slight
modification. In order to make the GSA with $N=8$ to succeed in searching for
a correct marked state, a circuit with auxiliary qubits has been presented in
[9]. This introduced a GSA with a bigger number of states than $N$, where the
redundant states are further removed by amplitude suppression. Furthermore, a
GSA with $N=8$ and one single ancilla qubit has been implemented on IBM
quantum devices in [10], and a GSA with $N=8$ both with and without ancilla
qubits has been executed on IonQ111Based on trapped atomic ion qubits quantum
devices in [11].

Error correction. Regarding the application of error-correction techniques to
the GSA implementation, the use of an error-correction code was considered in
[12], where the authors have applied two quantum BCH codes of parameters
[[7,1]] and [[15,7]] in order to correct errors after each stage of the GSA
with $N=128$ and $N=1024$. In [12], the performance evaluation of a noisy GSA
has been done by simulation, assuming a depolarizing channel of probability
$p$ within any two GSA stages, and no quantum devices have been used at that
time. Very recently, a NISQ implementation of the GSA with $N=4$ using a
[[4,2,2]] error-detection code has been reported in the literature [3].

###  I-B Useful notation

Let us introduce some notation which will be used though the paper. Denote two
pure states by $\ket{0}=\begin{pmatrix}1\\\ 0\end{pmatrix}$ and
$\ket{1}=\begin{pmatrix}0\\\ 1\end{pmatrix}$, and a superposed state by
$\ket{q}=a\ket{0}+b\ket{1}$, with $|a|^{2}+|b|^{2}=1$. One represents a system
of $n$ qubits as
$\ket{\textsl{system}}=\ket{q_{1}}\otimes\ket{q_{2}}\otimes...\ket{q_{N}}$,
where $\otimes$ is the Kronecker product. Thus, if
$\ket{q_{1}}=\ket{q_{2}}=...=\ket{q_{n}}=\ket{q}$, then
$\ket{\textsl{system}}=\ket{q}^{\otimes n}$. Finally, let
$\ket{+}=\frac{\ket{0}+\ket{1}}{\sqrt{2}}$ and
$\ket{-}=\frac{\ket{0}-\ket{1}}{\sqrt{2}}$.

Let us denote by $H$, $X$ and $Z$ the gates given by respective unitary
matrices

$\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\
-1&1\end{pmatrix},\quad\begin{pmatrix}0&1\\\ 1&0\end{pmatrix},\textrm{ and
}\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}.$

Also, the $CX$ the operator is given by the $4\times 4$ unitary matrix

$CX=I\oplus X,$

where $I$ is the $2\times 2$ identity matrix and $\oplus$ is the direct sum.
Similarly, let $CZ=I\oplus Z$, and more generally let
$C^{i}X=\underbrace{I\oplus\ldots\oplus I}_{\text{$i$ times}}\oplus X$ and
$C^{i}Z=\underbrace{I\oplus\ldots\oplus I}_{\text{$i$ times}}\oplus Z$ for all
$i\geq 1$.

##  II Grover’s Algorithm: theory and implementation

###  II-A GSA in Brief

The GSA can be briefly described as follows.

Algorithm 1 Grover’s search algorithm with $N=2^{n}$ [4]

Initialization:

  * •

Compute $R=\lfloor\pi\sqrt{N}/2-1/2\rfloor$.

  * •

Prepare two states of $n$ qubits each:
$\ket{s_{\textsl{initial}}}=\ket{0}^{\otimes n}$
$\ket{s_{\textsl{prepared}}}=H^{\otimes
n}\ket{s_{\textsl{initial}}}=\ket{+}^{\otimes n}$

  * •

One searches for a marked (goal) state $\ket{g}$ out of $N$ eligible states
$\ket{g_{1}},\ket{g_{2}},\ldots,\ket{g_{N}}$.

For $1\leq r\leq R$ do:

  * •

Phase Oracle: Perform the oracle operation
$U_{f}=\mathds{1}-2\ket{g}\bra{g}$, which maps $\ket{g}\mapsto-\ket{g}$, while
leaving all the other vectors unchanged.

  * •

Diffuser: Apply the diffuser operator
$V=\mathds{1}-2\ket{s_{\textsl{prepared}}}\bra{s_{\textsl{prepared}}}$

Measurement: Mesure the final state $\ket{s_{\textsl{final}}}$.

Output: Output the probability vector $(p_{1},p_{1},\ldots,p_{N})$ related to
$\ket{s_{\textsl{final}}}$. $p_{i}$ is an estimation of
$\textrm{Prob}(\ket{g}=\ket{g_{i}})$, $1\leq i\leq N$.

The actual performance of the algorithm is highly dependent on its circuit
implementation, and this even for ideal noiseless models, provided by quantum
simulators. To make the difference clear, the section below introduces several
versions of GSA circuits, along with simulation results.

###  II-B GSA Circuits and their Simulation

A first specificity of quantum circuits is in that they might have or not
contain auxiliary (ancilla) qubits. For various GSA implementations for $N=8$,
the reader is for instance referred to Fig. 1c of [11] for a circuit with one
ancilla qubit, to Fig. 4b of [10] for a circuit without ancilla qubits and to
[13] for circuits with and without ancilla qubits. The results presented in
[13] suggest that free-ancilla qubit circuits perform better than those with
ancilla qubits.

Let us focus on a more involved case of $N=16$. This case is covered by the
SDP circuit presented in [8] and detailed below. Also, in what follows we
suggest two new GSA circuits for $N=16$ which are slight extensions of GSA
circuits for $N=8$ from [11].

####  II-B1 SDP circuit [8]

Fig. 1 shows the SDP circuit with 4 data qubits $q_{0}$, $q_{1}$, $q_{2}$,
$q_{3}$, and one ancilla qubit $q_{4}$. The SDP circuit follows closely the
implementation of Algorithm 1. At the initialization stage, Hadamard (H) gates
are applied to data qubits in order to get $\ket{s_{\textsl{prepared}}}$. Note
that the ancilla qubit is prepared in the $\ket{-}$ state by successive
application of $X$ and $H$ gates. A phase oracle over all qubits is further
applied by the MCMT-CZ gate222For simplicity of presentation the MCMT-CZ gate
is not defined here, the reader is invited to refer to [7]. from [7] (drawn in
violet in Fig. 1). Note that two $X$ gates applied to $q_{0}$ before and after
the MCMT-CZ gate serve to fix $q_{0}$ to $0$ (and other data qubits will
therefore be fixed to $1$). Thus the goal state in the example of Fig. 1 is
$\ket{g}=\ket{q_{3}q_{2}q_{1}q_{0}}=\ket{1110}$. The diffuser operator applied
after the phase oracle is in fact the phase oracle targeting the $\ket{0000}$
state, put in between H gates. Note that the phase oracle and the diffuser
operations are to be repeated $R$ times, before proceeding to the final
measurement of $\ket{s_{\textsl{final}}}$. The performance of the SDP circuit
on a qasm simulator [7] (i.e. equivalent to a noiseless quantum device) is
given in Fig. 3 in blue. All the possible states
$\ket{g_{1}},\ldots,\ket{g_{N}}$ are presented on the $x$-axis, while the
$y$-axis gives the value of associated probabilities. One can see that the
goal state $\ket{1110}$ has been correctly detected as it has a higher
probability with respect to all other states.

Figure 1: Circuit for the SDP for $N=16$ from [8] with $\ket{1110}$ as the
goal (marked) state and $R=1$. $q_{4}$ is the ancilla qubit.  Figure 2: First
two stages (Initialization and Oracle) of the GSA circuit for $N=16$ with the
goal state $\ket{1110}$, when $R=1$. Diffuser and Measurement stages of the
GSA are similar to those in Fig. 1. No ancilla qubits are present.

####  II-B2 GSA with no ancilla qubit

We suggest a new GSA circuit for $N=16$ with only 4 qubits $q_{0}$, $q_{1}$,
$q_{2}$ and $q_{3}$. The initialization and the phase oracle stages of our
circuit are shown in Fig. 2, and the diffuser and measurement stages are
similar to those presented in Fig. 1. Note that, for the phase oracle, the
MCMT-CZ gate used in the SDP circuit, is replaced by the $C^{3}Z$ gate333In
Fig. 2, the $C^{3}Z$ gate is implemented as a $C^{3}X$ gate with $H$ gates
before and after the gate $X$, by using the fact that $HXH=Z$.. The
performance of the GSA circuit on a qasm simulator is given in Fig. 4 in blue.

####  II-B3 GSA with one ancilla qubit

We suggest another GSA circuit with 4 data qubits $q_{0}$, $q_{1}$, $q_{2}$,
$q_{3}$, and one ancilla qubit $q_{4}$. This circuit is very similar to the
one presented in Fig. 1, with only one exception: the MCMT-CZ gate of the
phase oracle is replaced by the $C^{4}X$ gate. Otherwise, as for SDP, $q_{4}$
is prepared in $\ket{-}$ as before, and the diffuser and measurement circuits
are the same. Note that the performance of this circuit on qasm is the same as
shown by the blue histogram in Fig. 4.

One can see that the difference between the three circuits above is in the
presence/absence of ancilla qubits and in the implementation of the phase
oracle. We will see in the next section that this difference is essential for
the circuit performance on real quantum devices.

##  III Performance Evaluation on NISQ Devices

Let us run the circuits presented in Section II-B on real quantum devices,
available on an IBM-Q cloud, in particular on ibm_oslo (7 qubits), ibm_algiers
(27 qubits) and ibm_canberra (27 qubits). It is to note that all the results
reported in this section have been obtained by means of Monte-Carlo tests with
1000 experiments (if simulation) or 4000 experiments (if test on real device).

Figure 3: Outcome of SDP [8] on qasm_simulator and ibm_algiers, $R=1$. Figure
4: Outcome of GSA with/without ancilla qubit on qasm_simulator and
ibm_algiers, $R=1$. Figure 5: Implementation of GSA on qasm_simulator for
different values of $R$. Figure 6: Implementation of GSA ibm_algiers for
different values of $R$.

####  III-1 Comparison of outcomes for a simulator and for a NISQ device

Fig. 3 shows the output of a SDP circuit in Fig. 1 [8] for
$\ket{g}=\ket{1110}$, obtained on qasm_simulator and on the device
ibm_algiers. We can observe that the probability associated with the state
$\ket{g}$ is larger w.r.t. the probabilities of other states. Also, the
results on ibm_algiers are more noisy than the ones from qasm. A similar
observation can be made for Fig. 4, which compares outputs of GSA with and
without ancilla qubit, for $\ket{g}=\ket{1110}$, tested both on qasm_simulator
and ibm_algiers. Both GSA circuits behave almost equally on the simulator
(blue histogram), but their outcomes are more noisy on ibm_algiers. Moreover,
the GSA without ancilla qubit is more resistant to the noise induced by the
quantum device and has better performance (red histogram). Finally, one
notices that the GSA with no ancilla qubit is the most efficient circuit among
the three circuits introduced in Section II-B.

####  III-2 Tests for different values of $R$ on a simulator and on a NISQ
device

Consider the GSA circuit without ancilla qubit. Fig. 5 (resp. Fig. 6)
illustrates the outcome of the circuit on the qasm_simulator (resp. on
ibm_algiers) for $R=1;2;3$. Note that Algorithm 1 is shown to converge with
the number of repetitions $R$. This is exactly what one observes in Fig. 5
(outcome on the simulator). However, Fig. 6 shows that the outcome gets worse
with $R$. This is due to the increase of the depth (i.e. the quantity of gates
in the circuit) with $R$ and to the accumulation of the noise induced by the
gates.

Circuits Devices | ibm_algiers | ibm_oslo | qasm_simulator
---|---|---|---
SDP | 4.5 | N/A | 7.2
GSA with ancilla | 8.3 | 0.1 | 13.7
GSA w/o ancilla | 10.8 | 5 | 13.37
TABLE I:  Selectivity for $N=8$ with $\ket{g}=\ket{110}$. Circuits Devices | ibm_algiers | ibm_canberra | qasm_simulator
---|---|---|---
SDP | 1.36 | 1.9 | 6.38
GSA with ancilla | 4 | 3.25 | 12.8
GSA w/o ancilla | 6.54 | 4.57 | 9.46
TABLE II:  Selectivity for $N=16$ with $\ket{g}=\ket{1110}$ and $R=1$.

####  III-3 Circuits vs. types of devices

Given the results above, we are ready to make a more complete comparison of
circuits run on different devices.

Assume a GSA circuit is run over some NISQ device. Let $g$ be the index of the
goal (marked state). Given a probability vector $(p_{1},p_{2},\ldots,p_{N})$
as outcome, define the _selectivity_ $S_{g}$ [14] as follows:

$S_{g}=10\log_{10}\frac{p_{g}}{\max_{i\not=g}p_{i}}.$ (1)

In fact, the selectivity plays the same role as signal-to-noise ratio in
communication systems. It is considered [14] that, if $S_{g}\geq 3$, then the
circuit is assumed to recognize the goal state $g$ successfully.

Tables I and II show the values of selectivity for the three GSA circuits from
Section II-B, implemented on two quantum devices, as well as on the
qasm_simulator, for $N=8$ and $N=16$ respectively. Note that the GSA circuit
performs the best on quantum devices and the SDP the worst. This observation
can be explained by the number of gates within the circuit. Indeed, the GSA
circuit contains the least number of gates w.r.t. the others, while the SDP
circuits contains the most. Moreover, the selectivity of a given circuit is
the best on qasm_simulator (perfect running environment) and is worse for
quantum devices. It also differs from one device to another due to their
differences in implementation (i.e. connectivity of qubits on the circuit) and
non-equal calibration parameters. The obtained results also warn that the
circuit comparison based on simulation results might not reflect the circuit
behaviour on real devices. If one only considers the qasm_simulator column,
one would say that the GSA with ancilla qubit is the best circuit. Meanwhile,
if one considers results on quantum devices, the GSA without ancilla qubit is
the one that distinguishes the goal state for all circuit examples.

####  III-4 Extension of GSA to $N=32$

We extended the GSA circuit without ancilla qubit to the case of $N=32$
($n=5$). The results obtained on a real device (see Fig. 7 for tests on
ibm_algiers) are not encouraging: as the number of gates in the circuit grows
with $n$, the selectivity $S_{g}$ takes values close to $0$, meaning that the
goal state is indistinguishable from the others. This result strongly suggests
that, in order to be able to run GSA circuits on real devices for larger
values of $N$, a noise-reducing method is to be implemented along with the
initial algorithm.

Figure 7: Implementation of GSA without ancilla qubit, for $N=32$ and
$\ket{g}=\ket{11100}$, on ibm_algiers. The bar related to $p_{g}$ is
underlined in red.

##  IV Discussion

The example of the Grover’s search algorithm, presented in this work, confirms
some implementation rules of quantum algorithms on NISQ devices: if possible,
one should avoid a high number of quantum gates in the circuit and/or ancilla
qubits. In case of GSA, this also means to keep the value of $N$ relatively
low. Indeed, for $N=32$ one seems to attain the limit of the GSA circuit
feasibility.

It is possible to improve the performance of the initial algorithm by adapting
it to the behaviour of quantum devices, like is has been suggested in [15]
with the aim to improve the GSA through hybrid search algorithm, optimization,
and divide-and-conquer search algorithm. However, this is a tedious approach
which needs reconsidering every algorithm in particular, and it might not be
sufficiently general in practice.

Another approach is the quantum error mitigation (QEM) [16], the goal of which
is to minimize the mean square error between the perfect circuit state and the
noisy circuit state. The QEM is an interesting approach to perform the
calibration of the quantum device of the system level, but it can also be
incorporated into the circuit level.

Finally, the third approach is the addition of error-control coding (QEC) to a
quantum circuit. To show the utility of error-correction schemes for NISQ
devices is an open challenging question – in most of cases the code rate of
the quantum error-correction schemes is quite low, namely of order $1/10$,
thus to add such a circuit implies an important increase in the number of
quantum gates in it, which in its turn increases the induced circuit noise.
Another alternative would be the use of higher-rate error-detecting codes
together with a QEM, like it was first tried in [3]. In general, a systematic
approach connecting QEM methods to QEC and merging them under a common
framework of error suppression is another open question.

##  V Acknowledgements

The authors acknowledge use of the IBM-Q in this work.

## References

  * [1] S. M. Girvin, “Introduction to quantum error correction and fault tolerance,” 2021\. [Online]. Available: https://arxiv.org/abs/2111.08894
  * [2] “Qubit kingdom,” in _The Error Correction Zoo_ , V. V. Albert and P. Faist, Eds., 2022. [Online]. Available: https://errorcorrectionzoo.org/kingdom/qubits_into_qubits
  * [3] B. Pokharel and D. Lidar, “Better-than-classical Grover search via quantum error detection and suppression,” 2022. [Online]. Available: https://arxiv.org/abs/2211.04543
  * [4] L. K. Grover, “Quantum mechanics helps in searching for a needle in a haystack,” _Phys. Rev. Lett._ , vol. 79, pp. 325–328, July 1997. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.79.325
  * [5] E. Arikan, “An information-theoretic analysis of Grover’s algorithm,” in _Proc. of IEEE International Symposium on Information Theory_ , 2003, p. 401\.
  * [6] T. Lubinski, S. Johri, P. Varosy, J. Coleman, L. Zhao, J. Necaise, C. H. Baldwin, K. Mayer, and T. Proctor, “Application-oriented performance benchmarks for quantum computing,” 2021. [Online]. Available: https://arxiv.org/abs/2110.03137
  * [7] “Qiskit documentation,” 2022. [Online]. Available: https://qiskit.org/documentation/
  * [8] Y. Wang, T. Zheng, and L. Horesh, “From string detection to orthogonal vector problem,” 2022. [Online]. Available: https://arxiv.org/abs/2209.11452
  * [9] A. Vlasic, S. Certo, and A. Pham, “Complement Grover’s search algorithm: An amplitude suppression implementation,” 2022. [Online]. Available: https://arxiv.org/abs/2209.10484
  * [10] T. Roy, S. Hazra, S. Kundu, M. Chand, M. P. Patankar, and R. Vijay, “Programmable superconducting processor with native three-qubit gates,” _Phys. Rev. Applied_ , vol. 14, p. 014072, July 2020. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevApplied.14.014072
  * [11] C. Figgatt, D. Maslov, K. Landsman, N. Linke, S. Debnath, and C. Monroe, “Complete 3-qubit Grover search on a programmable quantum computer,” _Nature communications_ , vol. 8, no. 1, p. 1918, December 2017. [Online]. Available: https://europepmc.org/articles/PMC5715115
  * [12] P. Botsinis, Z. Babar, D. Alanis, D. Chandra, H. Nguyen, S. X. Ng, and L. Hanzo, “Quantum error correction protects quantum search algorithms against decoherence,” _Nature Scientific Reports_ , no. 6, p. 38095, December 2016. [Online]. Available: https://doi.org/10.1038/srep38095
  * [13] Y. El Kaderi, “Implementation of the Grover algorithm on IBM NISQ platform,” 2022. [Online]. Available: https://depinfo.u-cergy.fr/~yunos/Implementation_of_the_Grover_algorithm_on_IBM_NISQ_platform.pdf
  * [14] Y. Wang and P. S. Krstic, “Prospect of using Grover’s search in the noisy-intermediate-scale quantum-computer era,” _Phys. Rev. A_ , vol. 102, p. 042609, Oct 2020. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.102.042609
  * [15] K. Zhang, P. Rao, K. Yu, H. Lim, and V. Korepin, “Implementation of efficient quantum search algorithms on NISQ computers,” _Quantum Information Processing_ , vol. 20, no. 7, p. 233, July 2021. [Online]. Available: https://doi.org/10.1007/s11128-021-03165-2
  * [16] Z. Cai, R. Babbush, S. C. Benjamin, S. Endo, W. J. Huggins, Y. Li, J. R. McClean, and T. E. O’Brien, “Quantum error mitigation,” 2022. [Online]. Available: https://arxiv.org/abs/2210.00921