**footnotetext: These authors contributed equally to this work.

# Algorithms for Adaptive Experiments that Trade-off Statistical Analysis with
Reward: Combining Uniform Random Assignment and Reward Maximization

Jacob Nogas ∗
University of Toronto
<EMAIL_ADDRESS>
Tong Li ∗
University of Toronto
<EMAIL_ADDRESS>
Fernando J. Yanez
University of Toronto
<EMAIL_ADDRESS>
Arghavan Modiri
University of Toronto
<EMAIL_ADDRESS>
Nina Deliu
University of Cambridge
<EMAIL_ADDRESS>
Ben Prystawski
Stanford University
<EMAIL_ADDRESS>
Sofia S. Villar
University of Cambridge
<EMAIL_ADDRESS>
Audrey Durand
Université Laval
<EMAIL_ADDRESS>
Anna Rafferty
Carleton College
<EMAIL_ADDRESS>
Joseph J. Williams
University of Toronto
<EMAIL_ADDRESS>

###### Abstract

Multi-armed bandit algorithms like Thompson Sampling can be used to conduct
adaptive experiments, in which maximizing reward means that data is used to
progressively assign more participants to more effective arms. Such assignment
strategies increase the risk of statistical hypothesis tests identifying a
difference between arms when there is not one, and failing to conclude there
is a difference in arms when there truly is one (Rafferty et al., 2019). We
present simulations for 2-arm experiments that explore two algorithms that
combine the benefits of uniform randomization for statistical analysis, with
the benefits of reward maximization achieved by Thompson Sampling (TS). First,
Top-Two Thompson Sampling (Russo, 2016) adds a fixed amount of uniform random
allocation (UR) spread evenly over time. Second, a novel heuristic algorithm,
called TS PostDiff (Posterior Probability of Difference). TS PostDiff takes a
Bayesian approach to mixing TS and UR: the probability a participant is
assigned using UR allocation is the posterior probability that the difference
between two arms is ‘small’ (below a certain threshold), allowing for more UR
exploration when there is little or no reward to be gained. We find that TS
PostDiff method performs well across multiple effect sizes, and thus does not
require tuning based on a guess for the true effect size.

##  1 Introduction

Randomized controlled trials (RCTs) are a standard method to learn about the
effectiveness of different alternatives in fields like online education
(Williams and Williams, 2013; Heffernan and Heffernan, 2014; Kizilcec and
Brooks, 2017; Kizilcec et al., 2020) and mobile health (Buchholz et al., 2013;
Thorsteinsen et al., 2014). RCTs are typically conducted by allocating
participants to arms uniformly at random, with a participant having an equal
probability of experiencing each of the possible arms. If the arms being
compared differ in how beneficial they are to participants, then one might
wish to direct more participants to more effective arms. Adaptive algorithms
such as those for solving multi-armed bandit problems offer one potential way
to do so (Lomas et al., 2016; Williams et al., 2018). These algorithms vary
the probability that a participant will be assigned to an arm based on the
effectiveness of the arms for previous participants.

However, data collected with adaptive algorithms can exhibit measurement bias
(Nie et al., 2018; Erraqabi et al., 2017) and deviates from the assumptions of
typical hypothesis testing approaches (Villar et al., 2015). Traditional
statistical hypothesis tests on data collected using common multi-armed bandit
algorithms, such as Thompson Sampling (TS; Chapelle and Li (2011)), exhibit
both lowered Power (probability of correctly detecting a difference in arms)
and higher false positive rates (FPR, probability of incorrectly concluding a
difference exists) (Rafferty et al., 2019; Villar et al., 2015).

Traditional RCTs and multi-armed bandit-based adaptive experimental designs
are two ends of a continuum in terms of the amount of uniform random (UR)
allocation of participants to arms. In this paper, we explore the consequences
of mixing UR allocation and adaptive experimentation. While a variety of
approaches indirectly increase UR allocation in bandit algorithms in order to
try to decrease measurement error or improve the results of statistical
inference from the collected data (Williamson et al., 2017; Erraqabi et al.,
2017; Yao et al., 2020), directly mixing these two modes of allocation has the
advantage of increasing the interpretability of allocation and analysis for
those deploying these experiments.

We present simulations that compare: (1) Top-Two Thompson Sampling (Top-2 TS;
Russo (2016)), adding a fixed amount of UR spread evenly over time. (2) A
novel heuristic algorithm, called TS PostDiff (Posterior Probability of
Difference). Taking a Bayesian approach, TS PostDiff approximates the
posterior probability that the difference between two arms is ’small’ (below a
certain threshold) and uses this as the probability a new participant will be
allocated to an arm using UR rather than TS; this allows for more UR
exploration when there is little or no reward to be gained by exploiting.

We find that Top-2 TS as a fixed randomized approach can improve Power and FPR
in adaptive experiments. But it is difficult to tune, as it requires knowledge
of the true difference in expected reward between arms to avoid potentially
poor outcomes. The TS PostDiff approach provides the benefit of performing
well across a range of possible scenarios (arm differences), and is less
reliant on knowledge of the true difference between arms. Code for simulations
is made
public.111https://github.com/IAIresearchlab/TSPostDiff2021NeurIPSWorkshop

##  2 Related Work

Given the well-documented challenges of drawing inferences from adaptively
collected data (Xu et al., 2013; Bowden and Trippa, 2017; Nie et al., 2018;
Shin et al., 2019; Deshpande et al., 2018; Zhang et al., 2020; Villar et al.,
2015; Rafferty et al., 2019), two general approaches have been taken to
address this issue: developing methods to make correct inferences directly
from data collected using existing adaptive algorithms, or changing the
adaptive algorithm to collect better data. Work taking the first approach has
primarily focused on characterizing bias from ordinary least squares estimates
and reducing that bias through a variety of statistical approaches (Xu et al.,
2013; Bowden and Trippa, 2017; Deshpande et al., 2018; Nie et al., 2018; Shin
et al., 2019); reducing the bias of an estimator is related to the final
performance of a hypothesis test, but does not directly address the hypothesis
testing procedure (typically evaluated through FPR and Power). We focus on
statistical hypothesis testing because that is the dominant paradigm for
analyzing data in digital field experiments (Bayarri and Berger, 2004); future
work could explore the impact of adding uniform random allocation on Bayesian
analysis. There is reason to believe that the issues in incorrect statistical
conclusions extend beyond hypothesis tests, as the issues in bias in estimates
of means (Nie et al., 2018) and unequal sample sizes are not restricted to one
particular kind of test.

More closely related to this paper is work that considers changing the
adaptive algorithm to balance competing goals of minimizing regret and
obtaining data that is useful for drawing conclusions. In active exploration
(Antos et al., 2010; Carpentier et al., 2011), the objective is to estimate
the value of all arms as accurately as possible, and thus ensure low
estimation errors. The tradeoff between active exploration and maximizing
cumulative reward was first addressed using a heuristic algorithm (Liu et al.,
2014), and later formalized as a multi-objective bandit problem integrating
rewards and estimation errors (Erraqabi et al., 2017) which lead to a
rigorous, but deterministic, strategy with theoretical guarantees. The work in
this paper is complementary to Erraqabi et al. (2017) as it focuses on
randomized, rather than deterministic strategies, which are likely to be of
interest to researchers who typically conduct experiments.

Several recent papers have directly tackled how to collect data that is
amenable to statistical hypothesis testing. The Power-constrained bandits
algorithm (Yao et al., 2020) explores making multiple allocation decisions for
one participant, with the bandit aiming to guarantee the Power of a later
hypothesis test while also minimizing regret. Other work (Williamson et al.,
2017) uses a finite horizon MDP approach to minimize regret while constraining
the minimum number of participants assigned to each arm; they show this leads
to improved Power and lower estimation errors compared to an adaptive
algorithm without this constraint. Top-2 TS is a high-performing algorithm
that introduces a fixed amount of additional exploration of the second-best
arm as modeled by TS (Russo, 2016). In contrast to the fixed amount of UR
introduced by Top-2 TS, we introduce the TS PostDiff algorithm which
adaptively varies the amount of UR and compare it to the state-of-the-art
Top-2 TS.

##  3 Mixing MAB Allocation with Uniform Randomization

Maximizing the benefit of an experiment to participants can be modelled as a
MAB problem, in which an agent has to effectively choose among $K$ available
actions or arms. At each time step $t$, the agent chooses an arm
$k\in\\{1,\dots,K\\}$ and receives a reward $y_{k}$ associated with that arm.
Rewards are generally stochastic, and the expected reward might vary between
arms. The agent’s goal is to maximize cumulative reward, i.e., the sum of all
rewards earned from all time steps. To achieve this goal, the agent must trade
off the benefits of exploring unknown or poorly explored arms to learn more
about their associated reward, with exploiting already known arms by choosing
the one with highest expected reward (see Lattimore and Szepesvári, 2020, for
an overview).

We first consider adding UR allocation to an adaptive allocation strategy by
spreading the UR allocation evenly over time (fixed) with Top-2 TS. We then
illustrate our proposal of combining adaptive assignment with fixed UR
allocation, based on what we call Posterior Probability of Difference
(PostDiff). The idea behind PostDiff is to modulate the amount of additional
UR adaptively, depending on the empirical evidence about effect sizes
(difference in expected reward between arms).

###  3.1 Beta-Bernoulli Thompson Sampling

Thompson sampling is a commonly used, randomized MAB algorithm (Chapelle and
Li, 2011). With binary rewards, a Beta-Bernoulli model of the arms is typical.
The true rate of reward from each arm $k$, denoted $p_{k}^{\ast}$, is unknown.
Instead, we maintain a Beta distribution over our estimate of $p_{k}$,
capturing uncertainty about the effectiveness of each arm. Independent beta-
distributed priors with parameters $\alpha_{k}=1$ and $\beta_{k}=1$
(corresponding to a uniform distribution) over the estimation of each $p_{k}$
are assumed. At each iteration of TS, a sample is drawn from the posterior
distribution of $p_{k}$ for each arm, and the arm with the largest sampled
value is selected (Chapelle and Li, 2011; Russo et al., 2017). Choosing
actions with TS balances exploration and exploitation in the long run,
sampling from arms with the goal of converging on an optimal arm
asymptotically (Agrawal and Goyal, 2012). If there are two arms with the same
expected reward, then choosing either arm is equivalent from the perspective
of maximizing reward and TS can still converge to only sampling from one of
the arms.

###  3.2 Top-Two Thompson Sampling

Top-2 TS (Russo, 2016) introduces additional fixed random exploration through
a parameter $\beta$, and achieves high performance in best-arm identification.
At each time step, Top-2 TS samples from the posterior distribution for each
arm, and with probability $\beta$ chooses the arm with the highest sampled
value, and with probability $1-\beta$ chooses the arm with second-highest
sampled value. With two-arms, this corresponds to allocating with UR with
probability $\epsilon$ and with TS with probability $1-\epsilon$, where
$\beta$ = $1-\frac{\epsilon}{2}$.

###  3.3 Thompson-Sampling PostDiff (TS PostDiff) Policy

If an effect is small, the difference in reward between arms is not great, but
the demand on Power in detecting this effect is large, and thus we would
prefer the algorithm to assign participants to conditions closer to uniformly,
to ensure we can detect this small effect. Likewise, when no effect exists,
there is no reward to be gained, but MAB attempts to maximize reward can
inflate FPR. We would thus want to choose actions uniformly at random in this
case. Finally, as the effect size grows larger, we would like the algorithm to
assign more participants to the reward-maximizing arm.

Thus, we would like to increase UR assignment when there are nonexistent or
smaller effects (and less evidence for these effects), with a minimal loss in
reward when there is a substantial effect and reward to be gained. Towards
this end, we propose the PostDiff algorithm, which operates as follows:

  * •

with probability $\phi_{t}$, choose action uniformly at random.

  * •

with probability $1-\phi_{t}$, choose action according to an adaptive
allocation strategy (e.g., TS).

We define $\phi_{t}$ to be the posterior probability (after $t$ steps) that
the difference in expected reward between the $2$ arms is less than a
threshold $c\in[0,1]$ set by the experimenter, i.e.,

$\displaystyle\phi_{t}$
$\displaystyle=\int_{[0,1]^{2}}\mathbb{I}\big{[}|\mathbb{E}(y_{t}|x_{t}=1,p_{1})-\mathbb{E}(y_{t}|x_{t}=2,p_{2})|<c\big{]}\pi(\textbf{p}|\mathcal{D}_{t})\
d\textbf{p}$
$\displaystyle=\int_{[0,1]^{2}}\mathbb{I}\big{[}|p_{1}-p_{2}|<c\big{]}\pi(\textbf{p}|\mathcal{D}_{t})\
d\textbf{p}.$ (1)

where $\mathbb{I}$ is the indicator function, $\textbf{p}=(p_{1},p_{2})$ is
the parameter vector, $\mathcal{D}_{t}$ is set of available data up to time
$t$, and $\pi(\textbf{p}|\mathcal{D}_{t})$ is the posterior distribution of
the unknown $p_{k}$’s parameters given the observed data $\mathcal{D}_{t}$.
Specifically, we choose an action uniformly at random if $|p_{1}-p_{2}|<c$,
and use a MAB adaptive allocation strategy otherwise, with a probability of UR
allocation of $\phi_{t}$. We can think of $c$ as the effect size below which
we are willing to forgo reward in favour of improved FPR and Power.

##### Example: TS PostDiff

As an example, we show how can we apply the PostDiff mixture strategy to
Thompson Sampling. The procedure, which we call TS PostDiff, is illustrated in
Algorithm 1.

1:procedure TS PostDiff($\alpha$,$\beta$)

2: for $t=1,2,\ldots$ do

3: for $k=1,2$ do

4: Sample ${p}_{k}\sim\text{Beta}(\alpha_{k},\beta_{k})$

5: if $|p_{1}-p_{2}|<c$ then

6: $x_{t}=u+1$, with $u\sim\text{Bern}(1/2)$$\triangleright$ Follow UR policy

7: else

8: for $k=1,2$ do

9: Sample ${p}_{k}\sim\text{Beta}(\alpha_{k},\beta_{k})$$\triangleright$
Resampling Step

10: $x_{t}=\arg\max_{k}{p}_{k}$ $\triangleright$ Follow TS policy

11: Apply $x_{t}$ and observe the reward $y_{t}$

12: Update posterior for selected arm

Algorithm 1 TS PostDiff algorithm pseudocode

Note the inclusion of a resampling step.222This step is used to prevent using
the same p sample to determine if a difference exceeds $c$, and for action
selection, as this can result in TS behaving too exploitatively, choosing the
estimated best arm too frequently.

##  4 Simulation Experiments

Combining UR assignment with adaptive MAB allocation using a strategy that
models the differences between arms may have a very different impact on
inference compared to a strategy that includes a fixed amount of UR. All
approaches that increase UR exploration are likely to allow us to draw more
accurate conclusions from statistical hypothesis testing, but they may vary in
their impact on FPR versus Power. Additionally, the impact of each approach is
likely to vary based on the environment in which it is acting, including the
total number of time steps and the actual difference between arms. Since the
actual difference between arms is not known a priori, it would be beneficial
to have an algorithm that performed well across multiple effect sizes. We use
simulations to explore the impact of adding fixed or model-based amounts of UR
allocation to TS.

###  4.1 Methods

Following standard practice for hypothesis testing for differences in means,
we set our null hypothesis as the case where the expected Reward for arms are
identical (i.e. $H_{0}:p_{1}^{*}=p_{2}^{*}$), and the alternative hypothesis
as there is a difference between the arms (i.e. $H_{1}:p_{1}^{*}\neq
p_{2}^{*}$). We use the Wald Z-Test statistic (Wald, 1943), which relies on a
comparison of the sample means and their respective standard errors, for
rejecting or accepting the null hypothesis. This choice is driven by the fact
that it is a widely used test statistic and its asymptotic characteristics
have been well investigated by statisticians (Engle, 1984). As sample sizes
approach infinity, the Wald Z-Test, Likelihood Ratio test, t-tests and
Lagrange multiplier tests are equivalent; $n=30$ gives already a good
equivalence (Agresti, 2003).

##### False Positive Rate (FPR) and Statistical Power:

In conducting our hypothesis test, we are concerned with two performance
metrics: 1) FPR, which is the probability that we conclude there is a
difference between groups when there is no difference; and 2) statistical
Power, which is the probability that we correctly detect that an effect
exists. In our simulations, we approximate the FPR as proportion of times we
reject the null hypothesis when $H_{0}$, and Power is approximated as the
number of times we reject the null hypothesis when $p_{1}^{*}\neq p_{2}^{*}$ .
We use a significance level of $0.05$, which is commonly used in social and
behavioral sciences (Fisher, 1992; Queen et al., 2002).

##### Mean Reward:

We are also interested in measuring performance with respect to reward
maximization. To this end, we look at mean Reward, which is referred to as
Reward.

##### Effect Sizes (Differences in Arm Means) and Sample Sizes:

Let $w$ be the effect size, which could be equal to 0, 0.1, 0.2, 0.3, and 0.5.
In our simulations, we consider a $2$-armed Bernoulli bandit setting with arm
means set as $p_{1}^{*}=0.5+\frac{w}{2}$, $p_{2}^{*}=0.5-\frac{w}{2}$. More
precisely, we set $p_{1}^{*}=p_{2}^{*}=0.5$ for effect size $0$,
$p_{1}^{*}=0.55$, $p_{2}^{*}=0.45$ for effect size $0.1$, $p_{1}^{*}=0.60$,
$p_{2}^{*}=0.40$ for effect size $0.2$, etc. In our experiments we analyze
sample sizes $n$, which is the sample size required for $0.8$ Power for a
given effect size using a fixed UR allocation. This results in $n=197$, and
$n=785$, for effect sizes $0.2$, and $0.1$ respectively. To see the change in
Power and Reward when the effect size increases, we also included effect size
0.3 and 0.5 for $n=197$ and effect size 0.2 and 0.3 for $n=785$. When there is
no effect, we use the same sample sizes as when there is an effect.

##### Algorithms and Parameter Settings:

We conducted simulations with additional algorithms such as $\epsilon$-Greedy,
and probability clipping applied to TS (where if the probability of assignment
exceeded or was lower than a value, the probability of assignment was clipped
to that value). In the interests of space, we will focus our comparison and
discussion between Top-2 TS and TS PostDiff, as these were top performers. See
Appendix A for $\epsilon$-Greedy ad Probability Clipping results. The results
of TS and UR will be compared with Top-2 TS and TS PostDiff as benchmarks. For
the sake of a fair comparison, we pick four different values for $\beta$ in
Top-2 TS and for $c$ in TS PostDiff for each sample size, such that the four
corresponding algorithms in each case have a FPR close to (but not exceeding)
$6\%$, $7\%$, $8\%$, and $10\%$ respectively when there’s no effect. More
specifically, in the case where $n=197$, we have $\beta=0.7625$ (FPR=0.058),
$\beta=0.85$ (FPR=0.068), $\beta=0.9125$ (FPR=0.079), and $\beta=0.95$
(FPR=0.093) for Top-2 TS, and $c=0.275$ (FPR=0.057), $c=0.225$ (FPR=0.064),
$c=0.175$ (FPR=0.079), $c=0.125$ (FPR=0.096) for TS PostDiff. Similarly, in
the case where $n=785$, we have $\beta=0.8375$ (FPR=0.060), $\beta=0.8875$
(FPR=0.070), $\beta=0.9375$ (FPR=0.078), and $\beta=0.975$ (FPR=0.096) for
Top-2 TS, and $c=0.15$ (FPR=0.059), $c=0.125$ (FPR=0.066), $c=0.1$
(FPR=0.078), $c=0.075$ (FPR=0.094) for TS PostDiff. For all results, we
average across the outcomes of $10,000$ simulations.

###  4.2 Results

Figure 1: Power-reward plots for Uniform Random, Thompson Sampling, Top-2 TS
and TS PostDiff under sample size 197 and 785. The blue dashed lines separate
simulation results for different effect sizes. For the case with sample size
of 785, Uniform Random produces the same results for effect size 0.2 and 0.3.

####  4.2.1 TS PostDiff can adapt towards sample size and effect size and
achieve a good trade-off between Reward and Power

Simulation results are summarized in Figure 1. Unsurprisingly, the Reward for
the Uniform Random algorithm is always 0.5, since the average Reward of the
two arms are always 0.5. Both Top-2 TS and TS PostDiff achieve intermediate
Power and Reward compared to Thompson Sampling and Uniform Random, matching
the goal of taking both metrics into consideration. For TS PostDiff, larger
$c$ indicates that extra UR should be added for a larger range of effect
sizes, while for Top-2 TS, a higher $\beta$ will decrease the amount of UR it
allocates.

We further compare TS PostDiff with Top-2 TS with specific $c$ and $\beta$
value that yield similar FPR when there’s no effect, and we plot corresponding
results in the same color (Figure 1). Firstly, we find that TS PostDiff always
has better Power than Top-2 TS. Such an advantage is bigger when effect size
is relatively small (for example, when effect size = 0.2 and sample size =
197). In other words, in the situation where the sample size is not quite
enough to detect differences in treatments, TS PostDiff tends to behave closer
to Uniform Random and thus achieve a higher Power, which is often what we care
most in such a scenario. This could be further explained from the nature of
the TS PostDiff algorithm: when the TS PostDiff algorithm hasn’t collected
enough evidence of differences in arm means, the posterior distribution of the
two arms will be similar (i.e., with greater overlap). Thus, the UR re-
sampling step will more likely to be triggered, which will lead to more
Uniform Random sampling.

On the other hand, when the effect size is relatively easy to detect, TS
PostDiff provides good Reward while maintaining Power. For example, when
effect size = 0.5 and sample size = 197, TS PostDiff has same Power as Top-2
TS (both are close to 1), while the Reward of TS PostDiff is higher. When the
posterior distribution of the two arms are distinct, the UR re-sampling step
will happen less frequently, which means that TS PostDiff will behave closer
to the regular Thompson Sampling algorithm and exploit more to get higher
reward. This suggests that TS PostDiff can adapt to the sample size and effect
size, giving a good trade-off.

##  5 Limitations & Future Work

There are several limitations of the current work, that point towards future
directions. TS PostDiff does require choice of the parameter for what is a
’small’ difference, so guidance is needed on choosing the parameter or tuning
it based on data333See Appendix B for preliminary guidelines for choosing $c$.
We use simulations informed by the real-world deployments we have conducted,
but can include the deployments themselves in a longer submission, or
appendix. We start with the ubiquitous and important 2-arm trials, and it
would be valuable to explore 3 or more arms, such as generalizing TS PostDiff.
Another omission is more systematic comparisons to TS with Probability
Clipping (Zhang et al., 2020, e.g.), which provides a different way of using
randomization to limit the exploitative nature of TS (by not allowing
assignment probabilities to go above/below a certain threshold). We have
conducted simulations already and will include these results in a longer
version of this work. Future work could also explore adapting the threshold
for probability clipping based on the data (May Lee and Lee (2021)). It should
be noted that some past work Erraqabi et al. (2017) formulates an explicit
objective function for the trade-off between reward and measurement error in
arm means. We hope the current paper can inform future work on how to more
directly formalize an objective function for explicitly trading off between
Reward, FPR and Power.

## Acknowledgments and Disclosure of Funding

Sofia S. Villar thanks the UK Medical Research Council (grant number:
$MC\\_UU\\_00002/15$).

Nina Deliu was supported by the NIHR Cambridge Biomedical Research Centre
(BRC-1215-20014). The views expressed are those of the authors and not
necessarily those of the NIHR or the Department of Health and Social Care.

## References

  * (1)
  * Agrawal and Goyal (2012) Shipra Agrawal and Navin Goyal. 2012.  Analysis of thompson sampling for the multi-armed bandit problem. In _Conference on learning theory_. 39–1.
  * Agresti (2003) Alan Agresti. 2003\.  _Categorical data analysis_. Vol. 482.  John Wiley & Sons.
  * Antos et al. (2010) András Antos, Varun Grover, and Csaba Szepesvári. 2010\.  Active learning in heteroscedastic noise.  _Theoretical Computer Science_ 411, 29-30 (2010), 2712–2728.
  * Bayarri and Berger (2004) M Jésus Bayarri and James O Berger. 2004.  The interplay of Bayesian and frequentist analysis.  _Statist. Sci._ (2004), 58–80.
  * Bowden and Trippa (2017) Jack Bowden and Lorenzo Trippa. 2017.  Unbiased estimation for response adaptive clinical trials.  _Statistical methods in medical research_ 26, 5 (2017), 2376–2388.
  * Buchholz et al. (2013) Susan Weber Buchholz, Joellen Wilbur, Diana Ingram, and Louis Fogg. 2013.  Physical activity text messaging interventions in adults: a systematic review.  _Worldviews on Evidence-Based Nursing_ 10, 3 (2013), 163–173.
  * Carpentier et al. (2011) Alexandra Carpentier, Alessandro Lazaric, Mohammad Ghavamzadeh, Rémi Munos, and Peter Auer. 2011\.  Upper-confidence-bound algorithms for active learning in multi-armed bandits. In _International Conference on Algorithmic Learning Theory_. Springer, 189–203.
  * Chapelle and Li (2011) Olivier Chapelle and Lihong Li. 2011.  An empirical evaluation of thompson sampling. In _Advances in neural information processing systems_. 2249–2257.
  * Cohen (1988) J Cohen. 1988.  Statistical power analysis for the behavioral sciences, 2nd edn. Á/L.
  * Deshpande et al. (2018) Yash Deshpande, Lester Mackey, Vasilis Syrgkanis, and Matt Taddy. 2018.  Accurate inference for adaptive linear models. In _International Conference on Machine Learning_. PMLR, 1194–1203.
  * Engle (1984) Robert F Engle. 1984\.  Wald, likelihood ratio, and Lagrange multiplier tests in econometrics.  _Handbook of econometrics_ 2 (1984), 775–826.
  * Erraqabi et al. (2017) Akram Erraqabi, Alessandro Lazaric, Michal Valko, Emma Brunskill, and Yun-En Liu. 2017.  Trading off rewards and errors in multi-armed bandits. In _Artificial Intelligence and Statistics_. 709–717.
  * Fisher (1992) Ronald Aylmer Fisher. 1992\.  Statistical methods for research workers.  In _Breakthroughs in statistics_. Springer, 66–70.
  * Heffernan and Heffernan (2014) Neil T Heffernan and Cristina Lindquist Heffernan. 2014\.  The ASSISTments ecosystem: Building a platform that brings scientists and teachers together for minimally invasive research on human learning and teaching.  _International Journal of Artificial Intelligence in Education_ 24, 4 (2014), 470–497.
  * Kizilcec and Brooks (2017) René F Kizilcec and Christopher Brooks. 2017.  Diverse big data and randomized field experiments in MOOCs.  _Handbook of Learning Analytics_ (2017), 211–222.
  * Kizilcec et al. (2020) René F Kizilcec, Justin Reich, Michael Yeomans, Christoph Dann, Emma Brunskill, Glenn Lopez, Selen Turkay, Joseph Jay Williams, and Dustin Tingley. 2020.  Scaling up behavioral science interventions in online education.  _Proceedings of the National Academy of Sciences_ 117, 26 (2020), 14900–14905.
  * Lattimore and Szepesvári (2020) Tor Lattimore and Csaba Szepesvári. 2020.  _Bandit algorithms_.  Cambridge University Press.
  * Liu et al. (2014) Yun-En Liu, Travis Mandel, Emma Brunskill, and Zoran Popovic. 2014.  Trading Off Scientific Knowledge and User Learning with Multi-Armed Bandits.. In _EDM_. 161–168.
  * Lomas et al. (2016) J Derek Lomas, Jodi Forlizzi, Nikhil Poonwala, Nirmal Patel, Sharan Shodhan, Kishan Patel, Ken Koedinger, and Emma Brunskill. 2016\.  Interface design optimization as a multi-armed bandit problem. In _Proceedings of the 2016 CHI conference on human factors in computing systems_. 4142–4153.
  * May Lee and Lee (2021) Kim May Lee and J Jack Lee. 2021.  Evaluating Bayesian adaptive randomization procedures with adaptive clip methods for multi-arm trials.  _Statistical Methods in Medical Research_ 30, 5 (2021), 1273–1287.
  * Nie et al. (2018) Xinkun Nie, Xiaoying Tian, Jonathan Taylor, and James Zou. 2018\.  Why adaptively collected data have negative bias and how to correct for it. In _International Conference on Artificial Intelligence and Statistics_. 1261–1269.
  * Queen et al. (2002) Jerry P Queen, Gerry P Quinn, and Michael J Keough. 2002\.  _Experimental design and data analysis for biologists_.  Cambridge university press.
  * Rafferty et al. (2019) Anna Rafferty, Huiji Ying, and Joseph Williams. 2019\.  Statistical consequences of using multi-armed bandits to conduct adaptive educational experiments.  _JEDM| Journal of Educational Data Mining_ 11, 1 (2019), 47–79.
  * Russo (2016) Daniel Russo. 2016\.  Simple bayesian algorithms for best arm identification. In _Conference on Learning Theory_. 1417–1418.
  * Russo et al. (2017) Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. 2017.  A tutorial on thompson sampling.  _arXiv preprint arXiv:1707.02038_ (2017).
  * Shin et al. (2019) Jaehyeok Shin, Aaditya Ramdas, and Alessandro Rinaldo. 2019\.  Are sample means in multi-armed bandits positively or negatively biased?. In _Advances in Neural Information Processing Systems_. 7102–7111.
  * Thorsteinsen et al. (2014) Kjærsti Thorsteinsen, Joar Vittersø, and Gunnvald Bendix Svendsen. 2014.  Increasing physical activity efficiently: an experimental pilot study of a website and mobile phone intervention.  _International journal of telemedicine and applications_ 2014 (2014).
  * Villar et al. (2015) Sofía S Villar, Jack Bowden, and James Wason. 2015\.  Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges.  _Statistical science: a review journal of the Institute of Mathematical Statistics_ 30, 2 (2015), 199.
  * Wald (1943) Abraham Wald. 1943\.  Tests of statistical hypotheses concerning several parameters when the number of observations is large.  _Transactions of the American Mathematical society_ 54, 3 (1943), 426–482.
  * Williams and Williams (2013) Joseph Williams and Betsy Williams. 2013.  Using randomized experiments as a methodological and conceptual tool for improving the design of online learning environments.  _Available at SSRN 2535556_ (2013).
  * Williams et al. (2018) Joseph Jay Williams, Anna N Rafferty, Dustin Tingley, Andrew Ang, Walter S Lasecki, and Juho Kim. 2018.  Enhancing online problems through instructor-centered tools for randomized experiments. In _Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems_. 1–12.
  * Williamson et al. (2017) S Faye Williamson, Peter Jacko, Sofía S Villar, and Thomas Jaki. 2017.  A Bayesian adaptive design for clinical trials in rare diseases.  _Computational statistics & data analysis_ 113 (2017), 136–153.
  * Xu et al. (2013) Min Xu, Tao Qin, and Tie-Yan Liu. 2013.  Estimation bias in multi-armed bandit algorithms for search advertising. In _Advances in Neural Information Processing Systems_. 2400–2408.
  * Yao et al. (2020) Jiayu Yao, Emma Brunskill, Weiwei Pan, Susan Murphy, and Finale Doshi-Velez. 2020.  Power-Constrained Bandits.  _arXiv preprint arXiv:2004.06230_ (2020).
  * Zhang et al. (2020) Kelly Zhang, Lucas Janson, and Susan Murphy. 2020\.  Inference for Batched Bandits. In _Advances in Neural Information Processing Systems_ , Vol. 33. 9818–9829.

##  Appendix A Comparing $\epsilon$-Greedy and TS Probability Clipping

In Table 1, we compare TS PostDiff to $\epsilon$-Greedy. We first compare TS
PostDiff to $\epsilon$-Greedy with $c=0.2$ and $\epsilon=0.6$; these values
are chosen as they give similar FPR for $n=785$. FPR is lower for
$\epsilon$-Greedy for $n=197$ (0.067 vs. 0.054), but Power is reduced (0.8 vs.
0.751), with little improvement in reward for effect size $0.1$ (0.518 vs.
0.506), and both power and reward are reduced for effect size $0.2$ for
$\epsilon$-Greedy compared to TS PostDiff (0.792 vs. 0.766 for Power, 0.546
vs. 0.534 for Reward).

Next, we compare $\epsilon$-Greedy with $\epsilon=0.1$ to TS PostDiff with
$c=0.125$ (again, chosen for similar FPR for $n=785$). We see some improvement
in reward for $\epsilon$-Greedy in this case (0.535 vs 0.518 for effect size
0.1, and 0.559 vs. 0.572 for effect size 0.2), but with a very large decrease
in Power (0.782 vs. 0.396 for effect size 0.1, and 0.753 vs. 0.414 for effect
size 0.2).

In Table 2, we compare TS PostDiff to TS Probability Clipping (named as TS
ProbClip in the table). TS ProbClip consists of using TS, but with assignment
probability constrained to not exceed the value $p_{max}$ (Zhang et al.,
2020).

First, we compare TS PostDiff to TS Probability Clipping with $c=0.2$ and
$p_{max}=0.6$; these values are chosen as they give similar FPR for $n=785$.
FPR is lower for TS Probability Clipping for $n=197$ (0.067 vs. 0.056), and
they have similar Power, but TS Probability Clipping doesn’t have much Reward
when Effect Size = 0.2.

Then, we compare TS Probability Clipping with $p_{max}=0.9$ to TS PostDiff
with $c=0.125$ (again, chosen for similar FPR for $n=785$). Again, TS
Probability Clipping provides lower FPR for $n=197$, but it has much lower
Power in the two settings (0.572 vs 0.782 for effect size 0.1, and 0.586 vs.
0.753 for effect size 0.2) with slight improvements in Reward.

We also compare Top-Two TS to $\epsilon$-Greedy in Table 3, and Top-Two TS to
TS ProbClip in Table 4. Again, by comparing models with similar FPR for
$n=785$ (adjacent rows), we find that Top-Two TS achieves greater power, with
little loss in reward compared to $\epsilon$-Greedy, and Top-Two TS generally
out-performs TS ProbClip, though with lower power but higher reward in some
cases ($\beta$=0.7 compared to $p_{max}$=0.6).

We compare Top-Two TS and TS PostDiff in the main text, as they are the higher
performing algorithms in this comparison.

| Effect Size $=0.0$ | Effect Size $=0.0$ | Effect Size $=0.1$ | Effect Size $=0.2$
---|---|---|---|---
| $n=785$ | $n=197$ | $n=785$ | $n=197$
|  FPR |  FPR |  Power |  Reward |  Power |  Reward
TS PostDiff ($c=0.125$) |  0.062 (0.002) |  0.099 (0.003) |  0.782 (0.004) |  0.518 (0.0) |  0.753 (0.004) |  0.559 (0.001)
$\epsilon$-Greedy ($\epsilon$=0.1) |  0.068 (0.003) |  0.101 (0.003) |  0.396 (0.005) |  0.535 (0.0) |  0.414 (0.005) |  0.572 (0.001)
TS PostDiff ($c=0.2$) |  0.054 (0.002) |  0.067 (0.003) |  0.8 (0.004) |  0.506 (0.0) |  0.792 (0.004) |  0.546 (0.001)
$\epsilon$-Greedy ($\epsilon$=0.6) |  0.052 (0.002) |  0.054 (0.002) |  0.751 (0.004) |  0.518 (0.0) |  0.766 (0.004) |  0.534 (0.0)
Table 1: Comparison of FPR (False Positive Rate), Power, and mean reward for $\epsilon$-Greedy and TS PostDiff. Values in brackets are standard errors. Sample sizes are chosen as the sample sizes required to achieve 0.8 power with UR for the given effect size.  | Effect Size $=0.0$ | Effect Size $=0.0$ | Effect Size $=0.1$ | Effect Size $=0.2$
---|---|---|---|---
| $n=785$ | $n=197$ | $n=785$ | $n=197$
|  FPR |  FPR |  Power |  Reward |  Power |  Reward
TS PostDiff ($c=0.125$) |  0.062 (0.002) |  0.099 (0.003) |  0.782 (0.004) |  0.518 (0.0) |  0.753 (0.004) |  0.559 (0.001)
TS ProbClip ($p_{max}$=0.9) |  0.065 (0.003) |  0.081 (0.003) |  0.572 (0.005) |  0.532 (0.0) |  0.586 (0.005) |  0.564 (0.001)
TS PostDiff ($c=0.2$) |  0.054 (0.002) |  0.067 (0.003) |  0.8 (0.004) |  0.506 (0.0) |  0.792 (0.004) |  0.546 (0.001)
TS ProbClip ($p_{max}$=0.6) |  0.051 (0.002) |  0.056 (0.002) |  0.795 (0.004) |  0.509 (0.0) |  0.799 (0.005) |  0.517 (0.0)
Table 2: Comparison of FPR (False Positive Rate), Power, and mean reward, for TS PostDiff, and TS ProbClip. Values in brackets are standard errors. Sample sizes are chosen as the sample sizes required to achieve 0.8 power with UR for the given effect size.  | Effect Size $=0.0$ | Effect Size $=0.0$ | Effect Size $=0.1$ | Effect Size $=0.2$
---|---|---|---|---
| $n=785$ | $n=197$ | $n=785$ | $n=197$
|  FPR |  FPR |  Power |  Reward |  Power |  Reward
Top-Two TS ($\beta=0.95$) |  0.068 (0.003) |  0.083 (0.003) |  0.658 (0.005) |  0.53 (0.0) |  0.678 (0.005) |  0.56 (0.0)
$\epsilon$-Greedy ($\epsilon$=0.1) |  0.068 (0.003) |  0.101 (0.003) |  0.396 (0.005) |  0.535 (0.0) |  0.414 (0.005) |  0.572 (0.001)
Top-Two TS ($\beta=0.7$) |  0.052 (0.002) |  0.054 (0.002) |  0.779 (0.004) |  0.516 (0.001) |  0.791 (0.004) |  0.53 (0.0)
$\epsilon$-Greedy ($\epsilon$=0.6) |  0.052 (0.002) |  0.054 (0.002) |  0.751 (0.004) |  0.518 (0.0) |  0.766 (0.004) |  0.534 (0.0)
Table 3: Comparison of FPR (False Positive Rate), Power, and mean reward for $\epsilon$-Greedy and Top-Two TS. Values in brackets are standard errors. Sample sizes are chosen as the sample sizes required to achieve 0.8 power with UR for the given effect size.  | Effect Size $=0.0$ | Effect Size $=0.0$ | Effect Size $=0.1$ | Effect Size $=0.2$
---|---|---|---|---
| $n=785$ | $n=197$ | $n=785$ | $n=197$
|  FPR |  FPR |  Power |  Reward |  Power |  Reward
Top-Two TS ($\beta=0.95$) |  0.068 (0.003) |  0.083 (0.003) |  0.658 (0.005) |  0.53 (0.0) |  0.678 (0.005) |  0.56 (0.0)
TS ProbClip ($p_{max}$=0.9) |  0.065 (0.003) |  0.081 (0.003) |  0.572 (0.005) |  0.532 (0.0) |  0.586 (0.005) |  0.564 (0.001)
Top-Two TS ($\beta=0.7$) |  0.052 (0.002) |  0.054 (0.002) |  0.779 (0.004) |  0.516 (0.001) |  0.791 (0.004) |  0.53 (0.0)
TS ProbClip ($p_{max}$=0.6) |  0.051 (0.002) |  0.056 (0.002) |  0.795 (0.004) |  0.509 (0.0) |  0.799 (0.005) |  0.517 (0.0)
Table 4: Comparison of FPR (False Positive Rate), Power, and mean reward, for
Top-Two TS, and TS ProbClip. Values in brackets are standard errors. Sample
sizes are chosen as the sample sizes required to achieve 0.8 power with UR for
the given effect size.

##  Appendix B Considerations in choice of $c$ for TS PostDiff

We consider some of the issues at play in choosing the $c$ parameter for the
PostDiff algorithm. We focus on TS PostDiff, although the same considerations
apply when using the PostDiff strategy to add UR allocation to other adaptive
algorithms. Values in brackets are standard errors.

##### Understanding Behaviour of TS PostDiff:

The choice of $c$ impacts how $\phi_{t}$ in Equation 1 of the main text
evolves as more participants are seen. In Figure 2, we show $\hat{\phi_{t}}$
for various choice of $c$, for effect sizes $0.0$ and $0.1$. We approximate
$\phi_{t}$ as $\hat{\phi_{t}}$ by taking the proportion of times
$|p_{1}-p_{2}|<c$ across $10,000$ simulations for the given sample size. When
$c$ is above the true effect size, $\hat{\phi}$ increases with sample size
towards $1$. When $c$ is less than the true effect size, $\hat{\phi}$
decreases towards $0$. These are non-trivial results, as they indicate that
the additional UR allocation of TS PostDiff is able to overcome the bias
induced by TS. For example, the above shows that the tendency of TS to
overestimate the size of the difference in arms does not prevent $\phi$ from
converging to $1$ when the effect size is $0.0$.

Figure 2: Values of $\hat{\phi_{t}}$, the estimated probability of choosing
actions uniformly, for different sample sizes and values of the exploration
parameter $c$ across $10,000$ simulations for the effect size $0.1$ (right)
and $0$ (left). The x-axis denotes sample size and the y-axis shows
$\hat{\phi}$. We approximate $\phi$, the true probability of choosing actions
uniformly randomly, as $\hat{\phi}$ by taking the proportion of times
$|p_{1}-p_{2}|<c$ across $10,000$ simulations, for the given sample size shown
on the x-axis. For values of $c$ greater than the effect size, $\hat{\phi}$
converges to $1$, meaning TS PostDiff allocates actions with UR. For values of
$c$ less than the effect size, $\hat{\phi}$ converges to $0$, meaning TS
PostDiff behaves like standard TS.

##### Possible Approaches to Choosing $c$:

One approach is to set $c$ to an effect size which is “small” enough that
maximizing Reward for participants in the experiment is less important than
getting better analysis of the data. More precisely, consider an experiment
where one is willing to accept $x$ loss in expected reward
($|p_{1}^{*}-p_{2}^{*}|$). Figure 2 shows that if we choose $c=x$, if $c$ is
greater than the true effect size $|p_{1}^{*}-p_{2}^{*}|$), the algorithm
converges to always using UR allocation. If the true effect size
$|p_{1}^{*}-p_{2}^{*}|$ is less than $c$, the algorithm will converge to TS.

What if one isn’t sure what reward they are willing to give up for improved
data analysis? Or, it might be hard for a social-behavioral scientist to make
that decision without greater clarity about how much is lost or gained on each
dimension of Reward, FPR, and Power. Another approach could be to choose $c$
as the best non-zero guess for the true effect size.

We motivate the recommendation of choosing $c$ as a guess for the true effect
size based on results shown in Figure 3, which compares FPR, Power and
percentage of TS Reward for a range of $c$ values and effect sizes of $0$ and
$0.1$. Figure 3 shows diminishing returns in Power when $c$ exceeds the effect
size of $0.1$, whereas the percentage of TS Reward decreases roughly linearly.
FPR also reaches diminishing returns, but a $c$ value of $0.1$ is close to the
value where we see such diminishing returns. Choosing a $c$ value of $0.1$ is
thus a reasonable choice, or in general a $c$ value equal to the effect size
when effect sizes are smaller. If the effect size is larger though, then the
loss in Reward will be greater. Though the percentage of TS Reward is
decreasing linearly, if TS Reward is large, then this linear decrease will be
more costly. Following the thresholds in behavioural science for small and
medium effect sizes Cohen (1988), we don’t recommend setting $c$ higher than
$0.2$.

Figure 3: As $c$ increases, FPR (left) decreases and Power (middle) increases,
while Reward (right) decreases. Improvements to Power and FPR diminish as $c$
increases, while the impact on Reward is roughly linear in $c$. Figures show
results for a sample size of $785$ simulated participants.

In sum, we can view the choice of $c$ from two perspectives. We can use $c$ to
minimize using TS when effect sizes are small enough that we would favour
improved inference over reward maximization, and we can also use $c$ as a way
to influence how TS PostDiff trades-off between reward maximization and UR
exploration. These two perspectives (and a combination of them) can thus guide
a user in choosing $c$.


# WHITE DWARFS IN A UNIFORM SPHERE APPROXIMATION, WITH GENERAL RELATIVITY
EFFECTS TAKEN INTO ACCOUNT

G. S. Bisnovatyi-Kogan111Institute of Space Research, Russian Academy of
Sciences, Moscow. Moscow Physics-Technical Institute MFTI, Dolgoprudnyi., Е.А.
Патраман 222 Moscow Physics-Technical Institute MFTI, Dolgoprudnyi.Институт
космических исследований РАН, Москва,

###### Abstract

The limiting mass of cold white dwarfs was first calculated by E. Stoner in an
approximate model of a uniform star and was soon reduced by 20an exact
solution of the equations for the stellar equilibrium. Here we examine uniform
models of white dwarfs taking general relativity effects and the influence of
finite temperature into account. Solutions are obtained in the form of finite
analytic formulas and, for masses differing by no more than 20the exact
solutions, found by numerical integration of the differential equations for
the stellar equilibrium.

Keywords:: white dwarfs: uniform model: general theory of relativity

##  1 Introduction

In studies of the structure of white dwarfs it is usually observed that they
can be in equilibrium only for masses not exceeding some limit known as the
Chandrasekhar limit. For a carbon-oxygen chemical composition, with two
nucleons per electron, i.e., $\mu_{e}=2$, this limit equals $\approx
1.46M_{\odot}$. Stoner [1], who examined a model of a white dwarf with a
uniform density (see [2], as well), concluded for the first time that there is
an upper bound on the mass for cold stars whose equilibrium is maintained by
the pressure of degenerate electrons. He generalized the earlier discussion on
degenerate electrons from [3, 4] to the case of high density under conditions
of ultrarelativistic degeneracy in which the equation of state for cold matter
takes the form [5]

$P(\rho)=\frac{(3\pi^{2})^{1/3}}{4}\frac{\hbar
c}{(\mu_{e}m_{u})^{4/3}}\rho^{4/3}=K\rho^{4/3}$ (1)

Here $\mathrm{\mu_{e}}$ is the number of nucleons per electron,
$\mathrm{m_{u}}$ is the atomic mass unit, equal to 1/12 of the mass of the
isotope $\mathrm{{}^{12}C}$.

The mass of a polytropic star, corresponding to $\mathrm{\gamma}=4/3$, n = 3,
according to the Emden theory is independent of the density and is uniquely
determined by the parameter K in the form [5]

$M_{p}=4\pi\Big{(}\frac{K}{\pi G}\Big{)}^{3/2}\cdot M_{3},\quad M_{3}=2.018$
(2)

Using (2), Chandrasekhar [6] and Landau [7],independently and almost
simultaneously, obtained a limiting mass for a white dwarf with the equation
of state(2) in the form

$M_{wd}=\frac{\sqrt{3\pi}}{2}\Big{(}\frac{\hbar
c}{G}\Big{)}^{3/2}\frac{M_{3}}{(\mu_{e}m_{u})^{2}}=\frac{5.83}{\mu_{e}^{2}}M_{\odot}$
(3)

To determine the limiting mass of observed white dwarfs, Chandrasekhar [6],
following Stoner [1], obtained a value
$\mathrm{M_{wd}}=0.933\mathrm{M_{\odot}}$. This refined Stoner’s value
$\mathrm{M_{wd}}=1.1\mathrm{M_{\odot}}$ for the same value of
$\mathrm{\mu_{e}}=2.5$ in the uniform density model. It follows from the
theory of stellar evolution, as well as from observations, that almost all
white dwarfs consist of a mixture of carbon $\mathrm{{}^{12}C}$ and oxygen
$\mathrm{{}^{16}O}$ for which $\mathrm{\mu_{e}}=2$ [8], while
$\mathrm{M_{wd}}=1.46\mathrm{M_{\odot}}$. For the first time a realistic value
of the mass limit for white dwarfs was obtained in [7], which merits a more
correct designation as the Stoner- Chandrasekhar-Landau limit.

We note that the values of the limiting masses of white dwarfs are given here
based on refined modern values for all the constants, which has led to a
difference of a few percent from the values given in the original papers. In
this paper a uniform model is used to construct approximate models of white
dwarfs with arbitrary masses at a finite temperature taking into account the
post-Newtonian corrections to Newtonian gravitation owing to the effects of
the general theory of relativity (GR). A comparison of the results for the
limiting masses of white dwarfs in the exact and uniform models shows that the
errors in determining all the values in the uniform model are around 20%.

##  2 White dwarfs in the approximation of a sphere of constant density

The energy method used by Stoner [1] for white dwarfs and later for the
general case in [9, 10]. The density distribution is taken to be specified,
with a single parameter in the form of the central density, with variations in
which the star changes homologically. For uniform stars this kind of parameter
is the constant density over the star. We write the total energy
$\mathrm{\varepsilon}$ of a uniform star in the form

$\varepsilon=E_{T}M+\varepsilon_{G}=E_{T}M-\frac{3}{5}G\frac{M^{2}}{R}=E_{T}M-\frac{3}{5}G\Big{(}\frac{4\pi
M^{5}}{3}\Big{)}^{1/3}\rho^{1/3}$ (4)

Here $\mathrm{E_{T}}$ is the internal energy per unit mass and the
gravitational energy of the uniform sphere $\mathrm{\varepsilon_{G}}$ is
defined in [11]. The equilibrium state and the stability condition for a star
with mass $M$ are thus determined, respectively, by the equations

$0=\frac{d\varepsilon}{d\rho^{1/3}}=3MP\rho^{-4/3}-\frac{3}{5}G\Big{(}\frac{4\pi
M^{5}}{3}\Big{)}^{1/3};\quad\frac{d^{2}\varepsilon}{d(\rho^{1/3})^{2}}=9MP\rho^{-5/3}\Big{(}\gamma-\frac{4}{3}\Big{)}>0$
(5)

Here we have used the thermodynamic relations [12]

$P=\rho^{2}\Big{(}\frac{\partial
E_{T}}{\partial\rho}\Big{)}_{|S};\quad\gamma=\Big{(}\frac{\partial\ln
P}{\partial\ln\rho}\Big{)}_{|S}$ (6)

The first equilibrium relation in (5) yields the only solution for the mass of
a uniform star $\mathrm{M_{u}}$, in the case of the equation of state
$P=K\rho^{4/3}$, in the form

$M_{u}=5.463\Big{(}\frac{K}{G}\Big{)}^{3/2}$ (7)

On comparing the masses $\mathrm{M_{u}}$ from (7)) and $\mathrm{M_{p}}$ from
(3), we obtain for the limiting mass

$M_{u}=\Big{(}\frac{5}{4}\Big{)}^{3/2}\frac{\sqrt{3}}{M_{3}}M_{wd}=1.199M_{wd}$
(8)

Thus, the approximate value for the limiting mass of a uniform star according
to Stoner is roughly 20% greater than the exact value. For cold white dwarfs
we have the following equation of state [5]

$P_{ec}=\frac{m_{e}^{4}c^{5}}{24\pi^{2}\hbar^{3}}[y(2y^{2}-3)\sqrt{y^{2}+1}+3\sinh^{-1}y],\quad
y=\Big{(}\frac{3\pi^{2}\rho}{\mu_{e}m_{u}}\Big{)}^{1/3}\frac{\hbar}{m_{e}c}=\Big{(}\frac{1.027\rho}{10^{9}\mu_{e}}\Big{)}^{1/3}.$
(9)

For cold white dwarfs at arbitrary density we obtain, with account of (9), the
following expression for the dependence of the stellar mass on its density
$M_{uc}(\rho)$ in the form

$M_{uc}=5.463\Big{(}\frac{P_{ec}\rho^{-4/3}}{G}\Big{)}^{3/2}.$ (10)

When the small corrections owing to deviations from an ultrarelativistic gas
for $y\gg 1$, and small temperature corrections
$\alpha=\frac{m_{e}c^{2}}{kT}\gg 1$, are taken into account, the equation of
state takes the form [5]

$P=\frac{m_{e}^{4}c^{5}}{12\pi^{2}\hbar^{3}}y^{4}\Big{(}1-\frac{1}{y^{2}}+\frac{2\pi^{2}}{3\alpha^{2}y^{2}}\Big{)}=P(\rho)=\frac{(3\pi^{2})^{1/3}}{4}\frac{\hbar
c}{(\mu_{e}m_{u})^{4/3}}\rho^{4/3}\Big{(}1-\frac{1}{y^{2}}+\frac{2\pi^{2}}{3\alpha^{2}y^{2}}\Big{)}$
(11)

Then in the uniform model the dependence of the mass on the density for high
densities, taking (10) into account, is written in the form

$M_{u}=5^{3/2}\frac{3\sqrt{\pi}}{16}(\frac{\hbar
c}{G})^{3/2}\frac{1}{(\mu_{e}m_{u})^{2}}\Big{(}1-\frac{1}{y^{2}}+\frac{2\pi^{2}}{3\alpha^{2}y^{2}}\Big{)}^{\frac{3}{2}}$
(12)

For white dwarfs at arbitrary density, with small temperature corrections, the
equation of state takes the form [5]

$P(\rho)=\frac{m_{e}^{4}c^{5}}{24\pi^{2}\hbar^{3}}\Big{[}y(2y^{2}-3)\sqrt{y^{2}+1}+3\sinh^{-1}y+\frac{4\pi^{2}}{3\alpha^{2}}y\frac{y^{2}+2}{\sqrt{y^{2}+1}}\Big{]}.$
(13)

The white dwarf mass $M_{ut}$ in the uniform model, at arbitrary density, with
small temperature corrections, is defined as

$M_{ut}=5^{3/2}\frac{3\sqrt{\pi}}{16}(\frac{\hbar
c}{G})^{3/2}\frac{1}{(\mu_{e}m_{u})^{2}}\Big{\\{}\frac{1}{2y^{4}}\Big{[}y(2y^{2}-3)\sqrt{y^{2}+1}+3\sinh^{-1}y+\frac{4\pi^{2}}{3\alpha^{2}}y\frac{y^{2}+2}{\sqrt{y^{2}+1}}\Big{]}\Big{\\}}^{3/2}.$
(14)

##  3 Models of uniform white dwarfs with account of small corrections for GR

We now examine models of uniform white dwarfs taking into account the post-
Newtonian corrections for the GR. For equilibrium stars the post-Newtonian
corrections to the energy are defined in [9], see also [13], in the integral
form, which are calculated analytically for a uniform sphere as

$\displaystyle\Delta E=I_{1}+I_{2}+I_{3}+I_{4}+I_{5},\qquad\qquad\qquad\qquad$
(15) $\displaystyle I_{1}=-\frac{G}{c^{2}}E_{T}\int
m\frac{dm}{r}=-\frac{3}{5}\Big{(}\frac{4\pi}{3}\Big{)}^{1/3}\frac{G}{c^{2}}M^{5/3}E_{T}\rho^{1/3}=-\frac{9}{25}\frac{G^{2}}{c^{2}}\Big{(}\frac{4\pi\rho}{3}\Big{)}^{\frac{2}{3}}M^{\frac{7}{3}},$
$\displaystyle I_{2}=-\frac{G^{2}}{2c^{2}}\int
m^{2}\frac{dm}{r^{2}}=-(3)^{\frac{1}{3}}\frac{G^{2}}{14c^{2}}(4\pi\rho)^{\frac{2}{3}}M^{\frac{7}{3}},\qquad\qquad$
$\displaystyle I_{3}=-\frac{G}{c^{2}}\int\Big{(}\int
E_{T}dm\Big{)}\frac{dm}{r}=-\frac{3}{5}\Big{(}\frac{4\pi}{3}\Big{)}^{1/3}\frac{G}{c^{2}}M^{5/3}E_{T}\rho^{1/3}=-\frac{9}{25}\frac{G^{2}}{c^{2}}\Big{(}\frac{4\pi\rho}{3}\Big{)}^{\frac{2}{3}}M^{\frac{7}{3}},$
$\displaystyle
I_{4}=\frac{G^{2}}{c^{2}}\int\Big{(}\int\frac{mdm}{r}\Big{)}\frac{dm}{r}=3^{\frac{4}{3}}\frac{G^{2}}{35c^{2}}(4\pi\rho)^{\frac{2}{3}}M^{\frac{7}{3}},\qquad\qquad$
$\displaystyle I_{5}=-\frac{G^{2}}{c^{2}}\int\Big{(}\int
mrdr\Big{)}\frac{mdm}{r^{4}}=-3^{\frac{1}{3}}\frac{G^{2}}{35c^{2}}(4\pi\rho)^{\frac{2}{3}}M^{\frac{7}{3}}.\qquad\qquad$

Ultimately we obtain the correction for the GR for a uniform sphere in the
form

$\Delta
E=-\frac{6}{5}\Big{(}\frac{4\pi}{3}\Big{)}^{1/3}\frac{G}{c^{2}}M^{5/3}E_{T}\rho^{1/3}-\frac{3}{70}\Big{(}\frac{4\pi}{3}\Big{)}^{2/3}M^{7/3}\rho^{2/3}$
(16)

For a polytropic sphere the following relation holds, derived from the virial
theorem [5]

$\varepsilon_{T}=E_{T}M=-\frac{n}{3}\varepsilon_{G}=\frac{n}{5}G\Big{(}\frac{4\pi}{3}\Big{)}^{1/3}M^{5/3}\rho^{1/3}$
(17)

The relation (17) is used in (15) for $n=3$, and in the first term of (17),
leading to the expression for the GR correction for a polytropic star with
uniform density and $n=3$ in the form

$\Delta E=-1.982\frac{G^{2}}{c^{2}}M^{7/3}\rho^{2/3}$ (18)

For the Emden polytropic model with n = 3 the GR corrections are written as
[9]

$\Delta E=-0.93\frac{G^{2}}{c^{2}}M^{7/3}\rho^{2/3}$ (19)

When the corrections for the GR are taken into account, the approximate
equation for the equilibrium in a uniform model including (5) и (18) is
written in the form

$\displaystyle
0=\frac{d\varepsilon}{d\rho^{1/3}}=3MP\rho^{-4/3}-\frac{3}{5}G\Big{(}\frac{4\pi
M^{5}}{3}\Big{)}^{1/3}+\frac{d\Delta E}{d\rho^{1/3}}=$
$\displaystyle=3MP\rho^{-4/3}-\frac{3}{5}G\Big{(}\frac{4\pi
M^{5}}{3}\Big{)}^{1/3}-3.964\frac{G^{2}}{c^{2}}M^{7/3}\rho^{1/3}$ (20)

The GR correction is calculated here using the virial theorem for the uniform
sphere at $n=3$, corresponding to the white dwarf which mass close to the
maximal one. For the low mass white dwarfs GR correction is negligibly small,
so we may use it in the form (18) for any lower mass as well. The dependence
$M(\rho)$ for a uniform white dwarf model including GR effects following from
(3), with the equation of state (11) is shown in Fig. 1. The maximum mass is
reached at $\rho_{m}=4.689\cdot 10^{9}$ g/sm3, $M_{m}=1.672M_{\odot}$.
Analogous curves for white dwarfs in exact polytropic models are constructed
in [10]. The dependence $M(\rho)$ for a uniform white dwarf model including GR
effects following from (3), with the equation of state (13), is shown in Fig.
2.

Figure 1: The dependence of the mass on the density around maximal mass, for
cold WD, with GR effects neglected and included. The blue curve corresponds to
a uniform model with GR effects neglected, with equation of state of (11). The
red curve shows a uniform model, using (11)), with small corrections for GR
included. The maximum is reached at the point $\rho_{m}=4.689\cdot 10^{9}$
г/см3, $M_{m}=1.672M_{\odot}$. Figure 2: The dependence of the mass at
arbitrary density, for cold WD with GR effects neglected and included. The
blue curve corresponds to a uniform model with GR effects neglected, with
equation of state of (13). The red curve shows a uniform model, using (13)),
with small corrections for GR included. The maximum is reached at the point
$\rho_{m}=4.689\cdot 10^{9}$ г/см3, $M_{m}=1.672M_{\odot}$.

A comparison shows that the curves for the uniform models around mass maximum
are roughly 20than for the corresponding curves from [10], and lose stability
owing to GR effects at a density of roughly a factor of 5 lower because of the
greater influence of these effects in the uniform model compared to the exact
polytropic model with n = 3. Using Eq. (3) we obtain an equation for the mass
of a uniform white dwarf with GR effects taken into account at a finite
temperature:

$M=\left(\frac{-\frac{3}{5}G\left(\frac{4\pi}{3}\right)^{\frac{1}{3}}+\sqrt{(\frac{3}{5}G\left(\frac{4\pi}{3}\right)^{\frac{1}{3}})^{2}+47.568\frac{G^{2}}{c^{2}}\rho^{-1}P}}{7.928\frac{G^{2}}{c^{2}}\rho^{\frac{1}{3}}}\right)^{\frac{3}{2}}$
(21)

The dependence of the mass on the density of uniform isothermal white dwarfs
for different temperatures with GR effects taken into account, from (21), is
shown in Fig. 3 for the equation of state (11). Similar curves for isothermal
white dwarfs in the exact polytropic model have been obtained in [10]. The
dependence of the mass in the same model at arbitrary density, for the
equation of state (13), is shown in Fig. 4.

Note, that the influence of GR effects on the stability of white dwarfs was
first studied by Kaplan [14].

Figure 3: Plots for isothermal uniform white dwarfs at high densities around
the mass maximum, with GR effects taken into account, according to (11),(21).
Figure 4: Plots for isothermal uniform white dwarfs at arbitrary densities,
with GR effects taken into account, according to (13),(21).

## Acknowledgements

This work was partially supported by RFFI grant 20-02-00455.

## References

  * [1] Stoner E.C., Phil. Mag. 9, 944 (1930)
  * [2] Thomas E.G., Phil. Mag. 91, 3416 (2011)
  * [3] Fowler R.H., MNRAS, 87, 114 (1926)
  * [4] Frenkel J.,Zs.Phys. 50, 234 (1928)
  * [5] Bisnovatyi-Kogan G.S. Physical Questions in the Theory of Stellar Evolution [in Russian], Nauka, Moscow (1989).
  * [6] Chandrasekhar, S., Astrophysical Journal. 74, 81 (1931)
  * [7] Landau L.D., Phys. Zs. Sowjet. 1, 285 (1932)
  * [8] Schatzman E. White dwarfs. Amsterdam. North Holland (1958).
  * [9] Zel’dovich Ya.B. and Novikov I.D. Usp. Fiz. Nauk 86, 447 (1965).
  * [10] Bisnovatyi-Kogan G.S. Astron. zh 43, 89 (1966), [Sov. Astron. 10, 69 (1966)].
  * [11] Landau L.D. and Lifshitz E.M. The Field Theory [in Russian] Fizmatgiz, Moscow (2001).
  * [12] Landau L.D. and Lifshitz E.M, Statistical Physics [in Russian], Nauka, Moscow (1976).
  * [13] Zel’dovich Ya.B. and Novikov I.D. Theory of Gravitation and the Evolution of Stars [in Russian], Nauka, Moscow (1971).
  * [14] Kaplan S.A., Uch. zap. L’vovskogo gos. un-ta, seriya fiz-mat. 15, 109 (1949)


# Problem-Solving in Language Model Networks

Ciaran Regan1, Alexandre Gournail2, Mizuki Oka1

1University of Tsukuba, Japan
2Grenoble INP - Ensimag, UGA, France
<EMAIL_ADDRESS>
###### Abstract

To improve the reasoning and question-answering capabilities of Large Language
Models (LLMs), several multi-agent approaches have been introduced. While
these methods enhance performance, the application of collective intelligence-
based approaches to complex network structures and the dynamics of agent
interactions remain underexplored. This work extends the concept of multi-
agent debate to more general network topologies, measuring the question-
answering accuracy, influence, consensus, and the effects of bias on the
collective. The results show that random networks perform similarly to fully
connected networks despite using significantly fewer tokens. Furthermore, a
strong consensus among agents in correlates with correct answers, whereas
divided responses typically indicate incorrect answers. Analysing the
influence of the agents reveals a balance between self-reflection and
interconnectedness; self-reflection aids when local interactions are
incorrect, and local interactions aid when the agent itself is incorrect.
Additionally, bias plays a strong role in system performance with correctly
biased hub nodes boosting performance. These insights suggest that using
random networks or scale-free networks with knowledgeable agents placed in
central positions can enhance the overall performance of multi-agent systems.

Figure 1: An overview of multi-agent debate on networks. Each node represents
an agent and each edge represents a communication channel between agents, with
self-loops indicating agent self-reflection. In the first round, each agent
answers the question individually, with all the agents getting the answer
incorrect. In the second round, agent 2 gets the answer correct through self-
reflection. This correct answer then spreads through the network in subsequent
rounds of debate. After the last round of debate, “C” is taken as the final
answer of the system as this is the most common answer.

## Introduction

Large Language Models (LLMs) have demonstrated impressive performance on a
wide range of tasks, such as reasoning and question-answering (QA), however,
they are still prone to hallucinations and fallacious answers. To address
these issues, a wide range of techniques have been introduced, many of which
have been motivated by the ways in which humans approach problem-solving.
Inspired by the ability of humans to combine task-oriented actions with verbal
reasoning, ReAct (Yao et al.,, 2022) enables LLM instances, or agents, to
engage in a series of reasoning and action steps, which leads to a reduction
in hallucinations in QA tasks. Similarly, motivated by how humans iteratively
learn from past mistakes, Reflexion (Shinn et al.,, 2024) introduces agent
self-reflection, where agents reflect on their past responses to induce better
decision-making in future trials.

While these approaches improve performance, they make use of only a single
agent. Collective intelligence, on the other hand, suggests that multi-agent
approaches can be used to create systems which are more adaptable and robust
(Ha and Tang,, 2022). To this end, several multi-agent methods have been
proposed, such as (Li et al.,, 2024), which suggests that scaling the number
of agents increases the overall performance in problem-solving tasks. In this
approach, many agents individually solve problems, before a majority vote is
carried out to determine the final answer of the system. Although this
technique introduces multiple agents, the agents do not interact with each
other. In contrast, multi-agent debate (Du et al.,, 2023; Liang et al.,, 2023)
combines the idea of collaborative problem-solving with agent self-reflection.
In this approach, agents first solve problems as individuals, before they
answer the question again after considering both their previous response and
the responses of all other agents. This process repeats for several rounds
before a majority vote is taken to determine the final answer of the system.
This method has been shown to increase the QA performance when compared to
single-agent baselines, with the accuracy increasing with the number of rounds
and the number of agents.

Although (Du et al.,, 2023; Li et al.,, 2024) demonstrates that agent
collaboration is a useful approach to improve QA performance, it is not clear
how the topological structure of the system impacts this performance.
Furthermore, the dynamics of how these agents influence each other are yet to
be understood. To this end, this work generalises multi-agent approaches to
more complex network structures by describing the system as an undirected
graph, where each agent is represented by a node, connected to their debate
partners along communication channel edges. In this context, (Du et al.,,
2023) and (Li et al.,, 2024) can be considered fully connected and fully
disconnected networks respectively, with self-loops indicating agent self-
reflection. Indeed, it is not clear how this approach extends to other types
of networks. While networks of LLM agents have been studied in the context of
opinion dynamics in social systems (Gao et al.,, 2023; Chuang et al.,, 2023),
these complex network structures are yet to be applied to the problem-solving
domain.

In this work, multi-agent problem-solving is implemented on scale-free,
random, fully connected and fully disconnected networks, with the latter two
serving as a benchmark to (Du et al.,, 2023; Li et al.,, 2024). Studying
complex networks in this context is motivated by one of the main limitations
of agent debate on fully connected networks; as the number of agents increases
so too does the input prompt for each agent, as the responses of all agents
are aggregated together. Not only do agents begin to lose focus on the entire
input prompt (Du et al.,, 2023), but this approach becomes computationally
expensive in large systems due to the growing number of connections. In a
fully connected network of $n$ agents, the number of edges is given by
$\frac{n(n-1)}{2}$, resulting in a quadratic increase in the number of input
tokens as the number of agents increases. Additionally, the limited context
window of current LLMs makes this approach infeasible with a large number of
agents, highlighting the need for alternative network topologies with
different degree distributions. Scale-free networks are of particular interest
in this study, as the presence of hubs provides an opportunity to investigate
the importance of central, well-connected nodes in the problem-solving domain.
Furthermore, although there is some debate about the real-world occurrence of
scale-free networks (Barabási and Albert,, 1999; Broido and Clauset,, 2019),
studying multi-agent problem-solving within these structures may provide
valuable insights into the design of social systems.

To understand how network topology affects the QA performance, we first
measure the QA accuracy by administering mathematics questions to various
25-agent networks. We then explore the effect of bias in these networks by
manually inserting correct or incorrect answers into hubs or edges of scale-
free networks, providing insight into how biased nodes impact the collective.
The agent’s influence is then examined, by analysing how likely an agent is to
agree with their neighbours, and how likely they are to change their responses
from their previous answer, thus providing insight into the relative strength
of individuality versus collaborative problem-solving. Additionally, the
dynamics of the agent’s responses are investigated, to understand if agents
tend to remain correct or switch back and forth between answers. Finally, we
analyse the level of consensus in the networks, to understand how split the
responses are within the system.

Our results show that random networks achieve similar performance to fully
connected networks while using significantly fewer input tokens. In contrast,
fully disconnected networks, characterised by agent self-reflection only,
demonstrate inferior performance, with agents’ answers degrading throughout
the debate. Additionally, the tendency for connected networks to reach a
strong consensus when the answer is correct, but disagree otherwise, provides
a way to quantify uncertainty in the system. Furthermore, analysing biased
systems suggests that agents are easily influenced by stubborn, well-connected
agents.

Understanding the dynamics of these systems is an important topic in the field
of artificial life (Bedau et al.,, 2000; Bullock and Sayama,, 2023; Valentini
et al.,, 2018; Khaluf and Hamann,, 2019), and analysing language model
networks has significant implications for how we design future models of
collective intelligence. In particular, we believe that utilising random
networks provides a cost-effective way to further improve the problem-solving
capabilities of LLMs, with the level of consensus acting as a measure of
uncertainty. Moreover, the increase in performance when correct agents are at
the hubs of scale-free networks suggests that future systems may benefit from
having powerful models at their core, and smaller models at their periphery.

In summary, this work makes the following contributions:

  * •

We extend the concept of multi-agent debate to more complex network
topologies, demonstrating that random networks perform similarly to fully
connected networks while using significantly fewer tokens.

  * •

We show that biased agents significantly affect the overall QA performance,
especially when correct agents are positioned at network hubs, highlighting
their impact on the collective.

  * •

We show the importance of both individuality and collaboration, illustrating
how self-reflection and interactions with neighbours influence agent
behaviour.

  * •

We demonstrate that agents tend to agree when the system answers correctly but
are divided otherwise, quantifying the system’s uncertainty.

## Methods

By representing LLM agents as nodes which are connected to their debate
partners along communication channel edges, multi-agent debate can be extended
to complex network topologies. Formally, a multi-agent system can be
represented as a graph $G=(A,E)$ where $A={a_{1},a_{2},...,a_{n}}$ is a set of
$n$ debating agents and $E\subseteq\\{(a_{i},a_{j})|a_{i},a_{j}\in A\\}$ is
the set of communication links between debate partners. Notably, the existence
of self-loops in these graphs allows for self-reflection.

In this approach, agents first solve the problem individually. Then, each
agent re-evaluates their solution by considering the responses and reasoning
provided by neighbouring agents, along with their own previous solution.
Importantly, the reasoning behind these solutions is included in the
subsequent iteration, enabling agents to incorporate both their own and
others’ thought processes when revising their solutions. This process repeats
for several rounds, until a majority vote is carried out, and the most popular
answer is taken as the answer of the collective. By querying the system with a
wide range of questions, the overall QA performance can be estimated by
calculating the percentage of questions the system solved correctly. An
overview of this approach is shown Fig 1, with the prompt used for
implementing QA shown in Fig 2.

(a) Initial QA prompt. The agent is instructed to answer a multiple-choice
question and explain their reasoning. Here question refers to a multiple
choice question with answers A, B, C or D.

(b) Follow-up prompt for the agent to reconsider their answer after being
exposed to their own and others’ responses. This prompt is concatenated with
(a) for QA in follow-up rounds. Here self_response refers to the previous
response of the individual agent and neighbour_response refers to the
concatenation of responses of the agent’s neighbours.

Figure 2: The two-part prompt used for question answering. Subfigure (a)
presents the initial prompt for agents to solve the problem independently.
Subfigure (b) introduces the second stage, where agents are asked to re-
evaluate their response after considering peer feedback and their previous
response. Figure 3: The prompt used to generate reasoning for biased agents,
where question is the multiple-choice question and biased_answer is either the
correct answer for correctly biased agents or an incorrect answer for
incorrectly biased agents.

In addition to evaluating the QA performance across different network
topologies, this study also investigates how the system responds to the
introduction of bias; where several agents are specifically instructed to
answer either correctly or incorrectly. By placing biased agents at the hubs
or edges of scale-free networks, the effect on the performance is analysed,
providing insights into how agents influence their neighbours. To administer
this bias, agents are specifically provided with the correct or incorrect
answer and asked to create a potential justification for this answer, with the
prompt shown in Fig 3. Crucially, this prompt generates an explanation for
this biased answer, even if it is incorrect, which allows for fair comparison
in this debate system where agents share their reasoning. Throughout the
debate, the biased agent’s response will not change from this initial answer.

## Experimental Setup

To analyze the QA performance and dynamics of these systems, 3 scale-free and
3 random 25-agent networks were used, shown in Fig 4, in addition to fully
connected and fully disconnected networks. In particular, the scale-free and
random networks were generated using the algorithms proposed by (Bollobás et
al.,, 2003) and (Gilbert,, 1959), respectively, which have been implemented in
the NetworkX Python library (Hagberg et al.,, 2008). The agents, powered by
GPT-3.5-Turbo, then engaged in 4 rounds of debate, answering 100 questions
from the MMLU high school mathematics dataset (Hendrycks et al.,, 2021). To
keep the reasoning and answers concise, the agents were limited to output a
maximum of 200 tokens each. To measure the QA accuracy of the collective, we
take the most common answer at the end of the debate to be the response of the
system. The average number of times the system answered a question correctly
can then be calculated to give an estimate of the performance. Moreover, each
of the 100 questions were administered 3 times, enabling the average accuracy
of the system to be measured to a sufficient certainty. As the average
diameter of the network used is approximately 4, 4 rounds of QA should be
enough for sufficient information spread. These choices of parameters are
further discussed in the Discussion and Limitations section.

(a) Scale-Free Networks

(b) Random Networks

Figure 4: The specific scale-free and random networks used in the experiments.

To understand how biased hub nodes affect performance, the two most central
nodes, measured by degree centrality, in each scale-free network were biased
with either the correct or an incorrect answer. A similar biasing was applied
to two random edge nodes for comparison. These agents do not change their
response throughout the debate, and therefore provide a consistently biased
answer to each of their neighbours. The debates are then run as before,
allowing the performance of biased and unbiased networks to be compared. It is
worth highlighting that the answer of biased agents is not included in the
majority vote, and so the biased agents only affect the performance via the
diffusion of their answers in the debate. In addition to analysing the effect
of network structure and bias on the QA performance, the dynamics of the
agent’s responses and the level of consensus in the collective are also
analysed. The code used to implement this work, as well as the agent’s
responses, are made publicly available: https://www.github.com/tsukuba-
websci/PSiLMN.

## Results

### Network Structure and QA Performance

Comparing the QA performance between different types of networks, it is
evident that structure plays a role in the accuracy, as shown in Table 1. In
particular, random networks achieve similar performance to fully connected
networks, while using $250$ times fewer input tokens per round of debate.
Scale-free networks, which use a similar amount of input tokens per round to
random networks, exhibit worse performance than random networks, suggesting
the random network topology is superior for problem-solving tasks. In
contrast, fully disconnected networks demonstrate the lowest performance,
highlighting the importance of collaborative problem-solving.

Network | Tokens per Round | Accuracy
---|---|---
Fully Connected | 125000 | $67.7\pm 1.1\%$
Fully Disconnected | 5000 | $63.9\pm 0.4\%$
Random | 28600 | $68.2\pm 0.5\%$
Scale-Free | 21800 | $64.8\pm 1.0\%$
Table 1: The accuracy and number of tokens used per round of debate for
various types of (unbiased) networks.

To understand how the QA performance of the system evolves with each round of
debate, a majority vote was taken after each round and the accuracy was
computed, shown in Fig 5. Initially, the accuracy of all systems is 50% as the
agents are yet to interact and influence each other. This performance can be
regarded as a single-agent baseline. In the next round, the accuracy for all
network types rises, with the steepest increase for fully connected networks,
as the correct answers become distributed around the network. Notably, the
accuracy of fully disconnected networks begins to decrease after round 2,
which can be qualitatively attributed to the responses decreasing in quality
throughout the debate. Inspecting the output of agents in these networks
reveals short responses such as “(B) 64” or “(D) 60”, with no reasoning
provided in the final rounds of debate.

Figure 5: Accuracy per round of debate for different types of networks.

### Bias and QA Performance

Comparing the performance between biased and unbiased systems, it is found
that bias also plays a role in QA accuracy, shown in Table 2.

Network | Accuracy
---|---
Unbiased | $64.8\pm 1.0\%$
Correctly Biased (Hub) | $88.1\pm 0.5\%$
Incorrectly Biased (Hub) | $43.8\pm 1.5\%$
Correctly Biased (Edge) | $65.7\pm 1.1\%$
Incorrectly Biased (Edge) | $64.9\pm 1.3\%$
Table 2: Accuracy for biased scale-free networks.

Networks with correctly (incorrectly) biased nodes at their hubs perform
significantly better (worse) than their unbiased counterpart. In particular,
networks with correctly biased hub nodes performed twice as well when compared
to networks with incorrectly biased hubs, with accuracies of $88.1\pm 0.5\%$
and $43.8\pm 1.5\%$ respectively. Although bias is expected to impact the
performance, the significant decrease in accuracy for incorrectly biased
networks highlights that it only takes a few biased and well-connected agents,
two in this case, to impair the results significantly. Moreover, the stronger
comparative performance of the unbiased system demonstrates that although
agents may be capable of solving problems correctly, they are easily
influenced by incorrect agents. In the case where bias is inserted on the edge
of the network on the other hand, it is found that there is little effect on
the QA performance.

The accuracy for each round of debate in biased systems was found, shown in
Fig 6. As in Fig 5, the accuracy for all systems is the same in round one and
increases in round two, with the largest increase for the system with
correctly biased hubs. This increase from $50\%$ to $80\%$ accuracy can be
attributed to the hub nodes communicating the correct answer to their
neighbours, which comprise a large proportion of the network. Although the
incorrectly biased hub nodes also communicate the incorrect answer to a large
proportion of the network, the system’s accuracy increases in round two. In
subsequent rounds, however, the accuracy of the incorrectly biased hub
networks decreases, which can be attributed to incorrect answers spreading
around the network.

Figure 6: Accuracy per round of debate for scale-free networks with different
types of biases.

### Influence

Figure 7: Agent influence; the likelihood of an agent being correct based on
both its own answer and the answer of its neighbours in the previous round.
The x-axis denotes the proportion of neighbours correct in the previous round,
and the y-axis denotes the probability of the agent being correct in the
current round. Points in green (red) indicate that the agent was correct
(incorrect) in the previous round.

|
---|---
|
|
|

(a) Fully Connected

(b) Fully Disconnected

(c) Scale-Free (Unbiased)

(d) Random

(e) Correctly Biased (Hub)

(f) Incorrectly Biased (Hub)

(g) Correctly Biased (Edge)

(h) Incorrectly Biased (Edge)

Figure 8: Answer changes for different networks and biases are illustrated.
Each subplot shows the changes in answers over each round of debate. The
number of agents remaining correct is indicated in green, while those
remaining incorrect are indicated in red. Dark blue represents the number of
agents switching from incorrect to correct, and light blue represents those
switching from correct to incorrect.

To understand how an agent may be influenced, the probability of the agent
being correct in round $n$, given its previous response and the response of
its neighbours in round $n-1$ is shown in Fig 7, with green (red) points
showing cases where the agents own response was correct (incorrect) in the
previous round. For clarity, the figure depicts the case of random networks,
where each node will have, on average, the same number of neighbours. The
figure shows that as the number of correct neighbours increases, so too does
the probability of the agent being correct. Furthermore, the tendency for
green points to lie above red points highlights the positive impact of self-
reflection; regardless of the neighbour’s response, an agent is more likely to
answer correctly if it was correct in the previous round.

Considering the edge cases reveals several interesting insights about the
agent’s behaviour. Firstly, when the agent and all of its neighbours were
incorrect in the previous round, there is a $10\%$ chance that the agent will
spontaneously switch to the correct answer.‘ If the agent was correct on the
other hand, this probability increases to $30\%$ demonstrating the positive
effects of self-reflection. Secondly, when an agent was incorrect in the
previous round, but is surrounded by correct agents, it is very unlikely to
remain incorrect, showing a decrease in the impact of self-reflection.
Finally, in the case where the neighbour’s responses are split, the agent is
equally likely to be correct or incorrect, with a slight increase for agents
correct in the previous round. These findings highlight the importance of both
individuality and collective thinking in multi-agent systems. That is,
collaborative problem-solving improves the overall performance of the
collective, while self-reflection acts to improve performance when local
interactions are misguided.

### Dynamics

To further understand the dynamics of these systems, the way in which agents
change their answers between rounds is shown in Fig 8. In the case of fully
connected (Fig 8(a)), scale-free (Fig 8(c)) and random (Fig 8(d)) networks,
the number of agents selecting and remaining on the correct answer increases
with each round of debate. For fully disconnected networks, on the other hand,
the number of agents remaining correct or incorrect is near-constant, with
agents continuing to switch between the correct and incorrect answers. This
behaviour is unique to fully disconnected networks, illustrated by the light
and dark blue bars in Fig 8(b).

Considering bias, networks correctly biased at their hubs (Fig 8(e)) exhibit a
large number of agents switching from incorrect to correct answers after the
first round, in agreement with Fig 6. These agents with correct answers tend
to keep the correct response throughout the remaining rounds of debate.
Networks incorrectly biased at their hubs (Fig 8(f)), on the other hand, have
an increasing number of agents switching from correct to incorrect after round
two. This is a significant result, as it highlights the fact that agents may
have the correct answer, but will be convinced to switch due to the influence
of their biased neighbours. Moreover, this suggests that multi-agent influence
plays a larger role in performance than self-reflection, in general agreement
with Fig 7. If self-reflection had a significant impact on the system then
correct agents would disregard the responses of their incorrect neighbours,
highlighting the importance of collective intelligence and collaboration in
the problem-solving domain. As expected, networks biased at their edges (Fig
8(g) and Fig 8(h)) have similar dynamics to the unbiased counterpart.

### Consensus

While the accuracy gave us an insight into the average QA performance of the
system, it provides little information on how the answers are distributed
inside the network during any given round and whether or not the agents agree.
In fact, the network can be correct with less than half of its agents giving
the correct answer, due to majority voting. This section explores how and
under which conditions a consensus is formed.

Figure 9: The percentage of agents that answered correctly in the final round.

Fig 9 shows the percentage of agents in the network that answered the question
correctly in the final round. Although this metric highlights the relationship
between the consensus towards the correct answer and the overall QA
performance, which captures the total number of questions answered correctly
(Table 1 and 2), little information is provided on how the answers are
distributed.

To gain insight into the distribution of answers, the Simpson index is used to
estimate the level of consensus within the collective (Simpson,, 1949). The
Simpson index $\lambda$, which is used to quantify diversity, measures the
probability that any two randomly selected agents give the same answer in the
final round of the experiment and is given by Simpson’s formula:

$\lambda=\sum_{i\in R}p_{i}^{2}$

where $R$ is the number of possible responses and $p_{i}$ is the proportional
abundance of answer type $i$.

In this experiment, agents can give five different types of responses: A, B,
C, D and “Undetermined”. A, B, C and D naturally correspond to the different
multiple-choice options of the MMLU dataset and “Undetermined” refers to the
situation where the agent fails to provide a valid option. In this approach,
the minimum Simpson index, which occurs when answers are evenly split between
all five types of responses, is given by $\lambda_{\text{min}}=5\times
0.2^{2}=0.2$. On the other hand, if all agents agree on the same answer, the
Simpson index is given by $\lambda_{\text{max}}=1$, regardless of whether the
answer is correct or incorrect. Moreover, if the responses are completely
split, for example, if half the agents answer A and the other half answer B,
then the Simpson index is $\lambda_{\text{split}}=0.5$. This consensus measure
allows us to remove the separation between correct and incorrect answers, and
to measure exclusively the consensus between agents.

The average Simpson index for each network type is shown in the “overall”
column of Table 3. High values for fully connected networks, followed by those
for random and scale-free networks, indicate a relationship between network
connectivity and the agreement among agents.

Network | Overall | Correct | Incorrect
---|---|---|---
Fully Connected | $0.710$ | $0.775$ | $0.574$
Fully Disconnected | $0.529$ | $0.618$ | $0.371$
Random | $0.628$ | $0.708$ | $0.457$
Scale-Free |  |  |
Unbiased | $0.623$ | $0.712$ | $0.459$
Correct (Hub) | $0.613$ | $0.641$ | $0.405$
Incorrect (Hub) | $0.506$ | $0.633$ | $0.407$
Correct (Edge) | $0.613$ | $0.703$ | $0.439$
Incorrect (Edge) | $0.614$ | $0.700$ | $0.455$
Table 3: Overall, correct, and incorrect Simpson consensus values for various
network and bias types.

The following question then arises; “when the system answers correctly, do
they tend to agree on the same correct answer, or are the responses split?”.
To answer this, the Simpson index $\lambda$ was calculated separately for
questions answered correctly and incorrectly by the system and is depicted in
the “correct” and “incorrect” columns of Table 3. In particular, we see that
when the system answers correctly, there is a higher consensus among agents,
indicating greater certainty. Conversely, when the system answers incorrectly,
the consensus is weaker, reflecting less certainty. Therefore, the degree of
consensus among agents can be used to quantify the confidence in the
correctness of an answer.

This is further highlighted by Fig 10, which plots the distribution of the
Simpson index for different types of networks. In all networks, a strong
consensus usually corresponds to correct answers, shown by the large green
spike and few red points at $\lambda\approx 1$. This indicates that when the
system reaches full consensus, it is likely correct. Conversely, split answers
tend to correlate with incorrect responses.

|
---|---
|

(a) Fully Connected

(b) Fully Disconnected

(c) Scale-Free (Unbiased)

(d) Random

Figure 10: The distribution of the Simpson index for each question
administered to the system, for different networks. Green (red) indicates
questions the system answered correctly (incorrectly). The distribution of
correct answers (green) tends to be left-skewed, highlighting a tendency for
systems to form a consensus when the answer is correct. Conversely, the
distribution is right-skewed for incorrect answers.

Bias in networks, regardless of being correct or incorrect bias, slightly
reduces the consensus among agents, as depicted in the “correct” and
“incorrect” columns of Table 3. This result suggests that when the system
answers incorrectly, the presence of bias leads to an increase in uncertainty
amongst the agents, thus reducing the average level of consensus.

Overall, these results show that analysing consensus in networks reveals
important insights into the agent’s collective behaviour and provides guidance
for designing networks for problem-solving tasks. The analysis highlights that
a high degree of consensus among agents correlates with correct answers,
indicating greater certainty. Conversely, when consensus is lower, the system
is more likely to be incorrect. These findings highlight the importance of
designing connected networks to facilitate the spreading of correct answers,
allowing agents to form a consensus.

## Conclusion

This work extends multi-agent debate to more complex network topologies by
representing each agent as a node, connected to their debate partners through
communication channel edges, with self-loops indicating agent self-reflection.
To understand the QA performance and dynamics of these systems, MMLU questions
were administered to scale-free, random, fully connected and fully
disconnected networks. Additionally, the effect of bias was analysed by
manually inserting correct or incorrect responses into the hubs and edges of
scale-free networks.

The results show that random networks perform similarly to fully connected
networks while using significantly fewer tokens. Fully disconnected networks,
on the other hand, perform the poorest, with answers degrading with each round
of debate. Additionally, bias plays a strong role in the QA capabilities, with
a few incorrectly biased agents severely weakening the overall performance.
Analysing how agents are influenced revealed several interesting behaviours,
such as the importance of self-reflection when surrounded by incorrect
neighbours and a weakening impact of self-reflection when the proportion of
correct neighbours increases, highlighting the importance of both
individuality and collaboration in the problem-solving domain. Furthermore,
the results show a relationship between network connectivity and consensus,
with answers likely to be correct when the collective is in full agreement,
quantifying the uncertainty in the system.

## Discussion and Limitations

The findings of this study have significant implications for the design of
future multi-agent systems, a topic of interest in the field of artificial
life. The results suggest that when designing collective systems of LLM agents
for problem-solving tasks, random networks provide a performant and cost-
effective approach. Moreover, measures of consensus, such as the Simpson
index, can be utilised as a useful tool for gauging the uncertainty in these
systems.

The effect of biasing scale-free networks also provides some insight into how
we design future systems. For instance, while it has been shown that combining
different models in multi-agent debate can lead to an increase in performance
(Du et al.,, 2023), the results of this study suggest that placing larger,
more powerful models at the central hubs and smaller models at the periphery
may lead to an increase in performance without the high computation cost of
using a system comprised of large models alone. An analysis of this behaviour
is left to future research.

A significant limitation in this work is the limited number of agents,
questions, rounds of debate and networks used. As the number of requests to
the OpenAI API increases significantly with each of these parameters, certain
experimental configurations become prohibitively expensive. In this work, the
parameters were selected as a trade-off between statistical significance and
generality. In future work, it would be interesting to study other network
structures such as small-world networks, and networks with dynamic topologies,
as well as increasing the number of agents, which may lead to an increase in
performance (Sayama et al.,, 2015). Additionally, while this work focused
solely on QA tasks, future research should explore other aspects of
intelligence. For instance, creativity may also benefit from multi-agent
discussions, as suggested by (Lu et al.,, 2024).

## References

  * Barabási and Albert, (1999) Barabási, A.-L. and Albert, R. (1999).  Emergence of scaling in random networks.  science, 286(5439):509–512.
  * Bedau et al., (2000) Bedau, M. A., McCaskill, J. S., Packard, N. H., Rasmussen, S., Adami, C., Green, D. G., Ikegami, T., Kaneko, K., and Ray, T. S. (2000).  Open problems in artificial life.  Artificial life, 6(4):363–376.
  * Bollobás et al., (2003) Bollobás, B., Borgs, C., Chayes, J. T., and Riordan, O. (2003).  Directed scale-free graphs.  In SODA, volume 3, pages 132–139. Baltimore, MD, United States.
  * Broido and Clauset, (2019) Broido, A. D. and Clauset, A. (2019).  Scale-free networks are rare.  Nature communications, 10(1):1017.
  * Bullock and Sayama, (2023) Bullock, S. and Sayama, H. (2023).  Agent heterogeneity mediates extremism in an adaptive social network model.  In ALIFE 2023: Ghost in the Machine: Proceedings of the 2023 Artificial Life Conference. MIT Press.
  * Chuang et al., (2023) Chuang, Y.-S., Goyal, A., Harlalka, N., Suresh, S., Hawkins, R., Yang, S., Shah, D., Hu, J., and Rogers, T. T. (2023).  Simulating opinion dynamics with networks of llm-based agents.  arXiv preprint arXiv:2311.09618.
  * Du et al., (2023) Du, Y., Li, S., Torralba, A., Tenenbaum, J. B., and Mordatch, I. (2023).  Improving factuality and reasoning in language models through multiagent debate.  arXiv preprint arXiv:2305.14325.
  * Gao et al., (2023) Gao, C., Lan, X., Lu, Z., Mao, J., Piao, J., Wang, H., Jin, D., and Li, Y. (2023).  S3: Social-network simulation system with large language model-empowered agents.  arXiv preprint arXiv:2307.14984.
  * Gilbert, (1959) Gilbert, E. N. (1959).  Random graphs.  The Annals of Mathematical Statistics, 30(4):1141–1144.
  * Ha and Tang, (2022) Ha, D. and Tang, Y. (2022).  Collective intelligence for deep learning: A survey of recent developments.  Collective Intelligence, 1(1):26339137221114874.
  * Hagberg et al., (2008) Hagberg, A., Swart, P., and S Chult, D. (2008).  Exploring network structure, dynamics, and function using networkx.  Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States).
  * Hendrycks et al., (2021) Hendrycks, D., Burns, C., Basart, S., Zou, A., Mazeika, M., Song, D., and Steinhardt, J. (2021).  Measuring massive multitask language understanding.  Proceedings of the International Conference on Learning Representations (ICLR).
  * Khaluf and Hamann, (2019) Khaluf, Y. and Hamann, H. (2019).  Modulating interaction times in an artificial society of robots.  In Artificial Life Conference Proceedings, pages 372–379. MIT Press One Rogers Street, Cambridge, MA 02142-1209, USA.
  * Li et al., (2024) Li, J., Zhang, Q., Yu, Y., Fu, Q., and Ye, D. (2024).  More agents is all you need.  arXiv preprint arXiv:2402.05120.
  * Liang et al., (2023) Liang, T., He, Z., Jiao, W., Wang, X., Wang, Y., Wang, R., Yang, Y., Tu, Z., and Shi, S. (2023).  Encouraging divergent thinking in large language models through multi-agent debate.  arXiv preprint arXiv:2305.19118.
  * Lu et al., (2024) Lu, L.-C., Chen, S.-J., Pai, T.-M., Yu, C.-H., Lee, H.-y., and Sun, S.-H. (2024).  Llm discussion: Enhancing the creativity of large language models via discussion framework and role-play.  arXiv preprint arXiv:2405.06373.
  * Sayama et al., (2015) Sayama, H., Dionne, S. D., and Yammarino, F. J. (2015).  Effects of social network size and topology on evolutionary decision making.  In Artificial Life Conference Proceedings, pages 603–603. MIT Press One Rogers Street, Cambridge, MA 02142-1209, USA journals-info ….
  * Shinn et al., (2024) Shinn, N., Cassano, F., Gopinath, A., Narasimhan, K., and Yao, S. (2024).  Reflexion: Language agents with verbal reinforcement learning.  Advances in Neural Information Processing Systems, 36.
  * Simpson, (1949) Simpson, E. H. (1949).  Measurement of diversity.  nature, 163(4148):688–688.
  * Valentini et al., (2018) Valentini, G., Moore, D. G., Hanson, J. R., Pavlic, T. P., Pratt, S. C., and Walker, S. I. (2018).  Transfer of information in collective decisions by artificial agents.  In Artificial Life Conference Proceedings, pages 641–648. MIT press One Rogers Street, Cambridge, MA 02142-1209, USA.
  * Yao et al., (2022) Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K., and Cao, Y. (2022).  React: Synergizing reasoning and acting in language models.  arXiv preprint arXiv:2210.03629.