# Blind Exploration and Exploitation of Stochastic Experts

Noyan C. Sevüktekin and Andrew C. Singer
Department of Electrical and Computer Engineering
University of Illinois at Urbana-Champaign
<EMAIL_ADDRESS>
###### Abstract

We present blind exploration and exploitation (BEE) algorithms for identifying
the most reliable stochastic expert based on formulations that employ
posterior sampling, upper-confidence bounds, empirical Kullback-Leibler
divergence, and minmax methods for the stochastic multi-armed bandit problem.
Joint sampling and consultation of experts whose opinions depend on the hidden
and random state of the world becomes challenging in the unsupervised, or
blind, framework as feedback from the true state is not available. We propose
an empirically realizable measure of expert competence that can be inferred
instantaneously using only the opinions of other experts. This measure
preserves the ordering of true competences and thus enables joint sampling and
consultation of stochastic experts based on their opinions on dynamically
changing tasks. Statistics derived from the proposed measure is
instantaneously available allowing both blind exploration-exploitation and
unsupervised opinion aggregation. We discuss how the lack of supervision
affects the asymptotic regret of BEE architectures that rely on UCB1, KL-UCB,
MOSS, IMED, and Thompson sampling. We demonstrate the performance of different
BEE algorithms empirically and compare them to their standard, or supervised,
counterparts.

##  I Introduction

The standard stochastic multi-armed bandit framework captures the exploration-
exploitation trade-off in sequential decision making problems under partial
feedback constraints. The objective is to actively identify the best member,
or members, of a community comprising stochastic sources, termed arms, while
suffering the relative loss of non-ideal choices. Often, the arms yield
rewards that belong to a known probability distribution with hidden
parameters, and upon choosing an arm, the decision maker observes the reward
from that arm directly. For ergodic reward distributions, [1] shows that the
dynamic programming solution takes the form of an index policy111The orignial
formulation of [1] was in the Bayesian framework., called dynamic allocation
indices, which motivated the rich body of work that led to the arm-selection
rules that eventually achieved the asymptotic regret lower bounds of [2].
Alternatively, when the probability law that governs the rewards is defined
conditionally with respect to a hidden state that represents the “changing
world”, restless bandit framework of [3] leads to arm-selection policies that
are often computationally demanding. A key challenge that we address here is
to develop index policies that identify the best source in an environment
where the underlying state of the world changes erratically and hence, the
observations are generated from different probability distributions at each
point in time.

Specifically, we consider the case where each arm represents a stochastic
expert providing opinions on changing tasks and thus, upon consulting an
expert, the decision maker observes an opinion, rather than a direct reward.
Stochastic experts are sources of subjective information that might fail but
not purposefully deceive, as discussed in [4], and often, expert suggestions,
or opinions, are used with the aid of side-information: Feedback from past
states of the world is used in boosting, [5], models of expert stochasticity,
or direct information of expert reliability, or competence, are often used in
the Bayesian framework, [6]. In the absence of any side information, the
decision maker operates in a regime that can be termed unsupervised, relying
solely on the information in the opinions. Unsupervised opinion aggregation
methods such as expectation maximization (EM) [7], belief propagation (BP)
[8], and spectral meta-learner (SML) [9] exhibit an interesting phenomenon:
The reliability of experts are inferred as side-product of the underlying
optimization for estimating past states based on a block of opinions. On the
other hand, joint sampling and consultation of experts without supervision, or
blind exploration and exploitation (BEE) as termed here, requires
instantaneously available statistics that would allow reliable inference of
expert reliabilities at any and all states of the world.

We propose a method that relies solely on opinions to infer the competence of
an expert by re-defining the notion competence as the probability of agreeing
with peers rather than being objectively correct. The proposed method does not
only allow empirical inference of competence without any supervision but also
enables the use of index policies to efficiently address exploration and
exploitation dilemma when the underlying task changes at random. We show that
standard, or supervised, exploration-exploitation (SEE) strategies extend
their uses to the BEE problem by consulting multiple experts for each task,
equivalent to sampling multiple arms in the standard framework. Specifically,
we consider the index rules that rely on posterior sampling, [10], upper-
confidence bounds such as UCB1, [11], and KL-UCB, [12], minimum empirical
Kullback-Leibler divergence, in particular, IMED, [13], and minmax rule MOSS
of [14]. We investigate two operational regimes: First, a fixed number of
experts are consulted for each task and the opinion of the expert who is
believed to be most-reliable at that time is chosen. Second, upon consulting a
group of experts, a decision is formed by aggregating their opinions without
further supervision. We empirically compare the performance of different BEE
index rules and demonstrate that exploration-exploitation-based choice of
experts leads to comparable results to those of the original algorithms in the
unsupervised framework.

The organization of this paper is as follows: We summarize the notation used
in this paper, provide a background on stochastic experts, and define the BEE
problem formally in Section II. We discuss the motivation, formal definition,
and properties of our technique for unsupervised reliability inference in
Section III. Then, we discuss the fundamental properties of the BEE index
rules in Section IV. The experiments for comparing different BEE algorithms as
well as comparing them to their SEE counterparts are in Section V. The proofs
are deferred to the appendix.

##  II Notation, Background, and Problem Formulation

We begin with a brief overview of the notation used in this paper. Then, we
formally define the key concepts regarding stochastic experts. We conclude
this section by defining the BEE problem.

###  II-A Notation

A probability space is a triplet $\left(\Omega,\mathscr{F},\mathbb{P}\right)$,
where $\Omega$ is the event space, $\mathscr{F}$ is the sigma-field defined on
$\Omega$, and $\mathbb{P}$ is the probability measure. Random variables are
denoted by capital letters with the corresponding samples being denoted by
lowercase letters: $(X,x)$. A random process is an indexed collection of
random variables: $\left\\{Y(t):t\in\mathbb{T}\right\\}$, where $\mathbb{T}$
is the index set. Independent random variables $\left(X_{1},X_{2}\right)$ are
denoted by $X_{1}\perp X_{2}$ and conditionally independent random variables
$\left(X_{1},X_{2}\right)$ conditioned on $Y$ are denoted by $X_{1}-Y-X_{2}$.
Expectation, conditional expectation, and conditional probability operators
are denoted by $\mathbb{E}\left[\cdot\right]$,
$\mathbb{E}\left[\cdot\;\middle|\;\cdot\right]$, and
$\mathbb{P}\left(\cdot\;\middle|\;\cdot\right)$ respectively. The indicator
function is denoted by $\mathds{1}\left(\cdot\right)$, where domain is to be
understood from context. We use $[T]\triangleq\left\\{1,\cdots,T\right\\}$ to
denote the positive natural numbers up to a finite limit $T<\infty$. All
logarithms $\left(\log\right)$ are taken with respect to the natural base. We
use big $O$ notation when necessary.

###  II-B Background

Conceptually, stochastic experts are honest-but-fallible computational
entities that do not deceive the decision maker deliberately. Here, we
consider experts that do not collaborate while generating their opinions; [4]
provides a detailed discussion. The goal of this paper is to propose
techniques that identify the best stochastic experts, while dynamically
consulting others on varying tasks. In that context, consulting an expert on a
task is equivalent to pulling an arm in the standard multi-armed bandit
framework. The true reward, however, remains hidden.

Formally, let us begin with a random process $\left\\{Y(t):t\in[T]\right\\}$
that represents binary states of the world, or tasks with binary labels:
$Y(t)\in\left\\{-1,1\right\\}$, $\forall t\in[T]$. We allow the nature to
generate tasks independently:

$Y\left(t_{1}\right)\perp Y\left(t_{2}\right),~{}\forall t_{1}\neq
t_{2}\in[T].$ (1)

Furthermore, let the random process $Y(t)$ that governs the evolution of tasks
maximize the uncertainty:

$\mathbb{P}\left(Y(t)=1\right)=\mathbb{P}\left(Y(t)=-1\right)=\nicefrac{{1}}{{2}},~{}\forall
t\in[T].$ (2)

It is worth noting that any bias from non-uniform task generation can either
be estimated directly from labeled data, or inferred without supervision via
methods such as [15]. Furthermore, while independence assumption appears to be
restrictive, it is common in stochastic multi-armed bandit formulations, [16].

Formal characterization of stochastic experts involves the reliability of
their opinions and statistical dependence to the others. The probability with
which the opinion of an expert identifies the true state of the world
correctly determines the reliability, or competence, of that expert:

$p_{i}\triangleq\mathbb{P}\left(X_{i}(t)=Y(t)\right),~{}\forall t\in[T].$ (3)

Here, the reliability of an expert does not depend on the underlying state of
the world 222A notable exception to this model is the “two-coin” model from
[17], where conditionally static competences are discussed.. We further allow
that experts generate opinions $\left\\{X_{i}(t):i\in[M]\right\\}$
independently from one another for every task $t\in[T]$. Formally:

$X_{i}(t)-Y(t)-X_{j}(t),~{}\forall i\neq j\in[M],~{}\forall t\in[T].$ (4)

Conceptually, it makes sense that for meaningful inference, two different
opinions on the same task should never be statistically independent.
Furthermore, experts having conditionally independent opinions is equivalent
to independence of rewards in the standard framework.

Given the probability law defined by eq. (1)-(4), we can formally discuss why
SEE algorithms requires a toolset to address the impact of the underlying
uncertainty. Observe that:

$\lim\limits_{t\rightarrow\infty}\frac{1}{t}\sum_{\tau=1}^{t}X_{i}(t)=0,~{}\forall
p_{i}\in\left[0,1\right],$ (5)

which follows from the law of total probability, see appendix A. Conceptually,
eq. (5) indicates that the average opinion does not reflect the competence of
an expert, which is the true reward, posing a challenge for joint exploration
and exploitation in the context of sequentially consulting stochastic experts,
which we formally define next.

###  II-C Problem Definition

The first objective of the BEE problem is to identify the best expert in a
population while actively consulting members of that group on tasks that
change from one consultation to another. The following notion of regret,
written here in normalized form, formally captures this phenomenon:

$R_{T}=\frac{1}{T}\sum_{t=1}^{T}\mathds{1}\left(X^{*}(t)=Y(t)\right)-\frac{1}{T}\sum_{t=1}^{T}\mathds{1}\left(X_{I_{t}}(t)=Y(t)\right).$
(6)

Here $X^{*}$ is the opinion of the most competent expert; $X^{*}=X_{i^{*}}$,
where $i^{*}=\operatorname*{arg\,max}_{i\in[M]}p_{i}$ and $I_{t}\in[M]$,
$\forall t\in[T]$ is the expert chosen at time $t$. Observe that the regret,
as defined in eq. (6) depends on the sample path of opinions and hence, it is
difficult to analyze rigorously. Nonetheless, it simplifies asymptotically:

$\lim\limits_{T\rightarrow\infty}R_{T}=\max_{i\in[M]}p_{i}-\lim\limits_{T\rightarrow\infty}\frac{1}{T}\sum_{t=1}^{T}\mathds{1}\left(X_{I_{t}}(t)=Y(t)\right).$
(7)

The first term is a direct consequence of the ergodicity of the processs
$\mathds{1}\left(X^{*}(t)=Y(t)\right)$, which follows directly from eq.
(1)-(3). Conceptually, this amounts to the fact that one can measure the true
reliability of an expert given sufficiently many labeled tasks, as long as the
reliability of the expert does not change across tasks, as is the case here.

Motivated by similar asymptotic behaviors, a notion of pseudo regret often
arises in the context of stochastic bandits, see, for instance, [16]. In the
context of stochastic experts, the pseudo regret is defined as follows:

$\tilde{R}_{T}=\max_{i\in[M]}p_{i}-\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\mathds{1}\left(X_{I_{t}}(t)=Y(t)\right)\right].$
(8)

Another notion of pseudo regret provides a reliable metric for the performance
of BEE rules that aggregate opinions after consulting experts. Let a $m<M$
experts be consulted for every task $t$, indexed by
$\mathcal{C}_{t}\subset[M]$ and let $f:\left\\{\pm
1\right\\}^{\left|\mathcal{C}\right|}\rightarrow\left\\{\pm 1\right\\}$ be a
known opinion aggregation rule. Define the pseudo regret as:

$\tilde{R}_{T}=\max_{\begin{subarray}{c}\mathcal{C}\subset[M]\\\
\left|\mathcal{C}\right|=m\end{subarray}}\mathbb{P}\left(f\left(\left\\{X_{i}(t):i\in\mathcal{C}\right\\}\right)=Y(t)\right)-\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}\mathds{1}\left(f\left(\left\\{X_{i}(t):i\in\mathcal{C}_{t}\right\\}\right)=Y(t)\right)\right].$
(9)

To emphasize the difference in objectives, we will refer to the rules that aim
to minimize eq. (8) as BEE rules and to those that sequentially weight and
aggregate opinions of reliable members (SWARM) and thus, aim to minimize eq.
(9), as SWARM rules.

Given an arm-selection strategy, it is more intuitive to structure a
theoretical analysis based on the pseudo regrets in eq. (8)-(9), provided the
true rewards
$\left\\{\mathds{1}\left(X_{I_{\tau}}(\tau))=Y(\tau)\right):\tau\in[t]\right\\}$
are known. Nonetheless, the main challenge remains: At any given time $t$, the
decision maker does not have access to the past labels
$\left\\{Y_{\tau}:\tau\in[t]\right\\}$ and thus, does not get to observe the
true rewards. We address this challenge by consulting multiple experts for
each task and leveraging the increased reliability of a collection of experts
for inferring those of the individuals. Next, we formally define and discuss
the properties of the competence estimation technique that facilitates joint
exploration and exploitation based on opinions alone.

##  III Unsupervised Estimation of Competences with Instantaneous Updates

Two seemingly conflicting statistical phenomena should be reconciled to
facilitate sampling and consultation of experts based only on their opinions.
On one hand, standard index policies for exploration and exploitation require
observations from a joint probability distribution that does not evolve in
time. On the other hand, opinions $\left\\{X_{1}(t),\cdots,X_{M}(t)\right\\}$
are based on the hidden state $Y(t)$ and thus, their statistics change
randomly in time. Furthermore, an operational challenge exists: Multi-armed
bandit problems often allow observations to be available instantly so that the
player can decide which arm to pull next. This is in sharp contrast to the
unsupervised opinion aggregation strategies such as SML, EM, BP from [9, 7, 8]
respectively, that yield the reliability of experts as a side-product of an
optimization process that is often carried out over a block of opinions.

Fortunately, there exists an empirically realizable measure of competence that
is only based on opinions. Conceptually, consider a compact measure, for
instance, an ideal ruler for measuring the length of a two-dimensional line.
The length of any such line can be measured reliably by this ruler and these
measurements can be used to determine which line is the longest. Recall that
the true competence of an expert can be measured experimentally via:

$\lim\limits_{t\rightarrow\infty}\frac{1}{t}\sum_{\tau=1}^{t}\mathds{1}\left(X_{i}(t)=Y(t)\right)=p_{i}.$
(10)

In other words, state feedback is an ideal ruler in our example. In the
absence of such reliable reference, one can choose to accept a random line as
a measure of length, replacing the phrase “this line is $\ell$ units long”
with “this line is $\beta$ measuring lines long”. This strategy cannot, of
course, infer the true length of any line however, it can infer the relative
length of every other line, which is sufficient for constructing index rules
that solve the BEE problem.

We introduce an alternative notion of reliability, termed pseudo competence,
that allows instantaneous, opinion-based inference of the competences, while
preserving the true ordering of the competences. Formally, the pseudo
competence of an expert is defined as follows:

$\tilde{p}_{i}=\mathbb{P}\left(X_{i}(t)=V\left(\left\\{X_{j}(t):j\in\mathcal{C}\right\\}\right)\right)=\mathbb{P}\left(X_{i}(t)=\operatorname{sign}\left[\sum_{j\in\mathcal{C}}X_{j}(t)\right]\right).$
(11)

Here, $V\left(\cdot\right)$ denotes majority voting (where ties are broken
arbitrarily333The $\left(\operatorname{sign}\right)$ operator does not
conventionally “break ties arbitrarily”. However, we allow
$\operatorname{sign}\left[0\right]=Z$, where
$\mathbb{P}\left(Z=1\right)=\mathbb{P}\left(Z=-1\right)=\nicefrac{{1}}{{2}}$
in eq. (11) for notational clarity.) over a committee $\mathcal{C}$ that
excludes the $i^{th}$ expert:
$\mathcal{C}\subset[T]\setminus\left\\{i\right\\}$. Observe that it is
possible to estimate pseudo competences empirically:

$\lim\limits_{t\rightarrow\infty}\frac{1}{t}\sum_{\tau=1}^{t}\mathds{1}\left(X_{i}(t)=V\left(\left\\{X_{j}(t):j\in\mathcal{C}\right\\}\right)\right)=\tilde{p}_{i}.$
(12)

Further note that similar to the standard formulation with direct rewards, one
can easily keep track of number of times an expert is consulted and the number
of times that expert agreed with the others.

Let us denote the probability of the committee $\mathcal{C}$ being correct by:

$p_{\mathcal{C}}\triangleq\mathbb{P}\left(V\left(\left\\{X_{j}(t):j\in\mathcal{C}\right\\}\right)\right).$
(13)

Then, the pseudo competence can be written explicitly as:

$\tilde{p}_{i}=p_{i}p_{\mathcal{C}}+\left(1-p_{i}\right)\left(1-p_{\mathcal{C}}\right).$
(14)

The proof of eq. (14) appears in appendix B as a part of the proof for
Proposition 1. Conceptually, the pseudo competence of an expert increases
during empirical estimation if either both the expert and committee are
correct or both are incorrect.

Beyond allowing empirical estimation, the pseudo competence, as a measure of
reliability, demonstrates a key property: Given pseudo competences for a set
experts, or given sufficiently large number of tasks and the corresponding
opinions thanks to eq. (12), it is possible to rank experts based on their
true competence, as discussed next.

###### Proposition 1

For a committee $\mathcal{C}\subset[T]$, the following holds for every
$i,j\notin\mathcal{C}$:

$\tilde{p}_{i}-\tilde{p}_{j}=\left(2p_{\mathcal{C}}-1\right)\left(p_{i}-p_{j}\right).$
(15)

Therefore, if the probability of the committee $\mathcal{C}$ making a correct
decision under majority rule satisfies:

$p_{\mathcal{C}}=\mathbb{P}\left(V\left(\left\\{X_{j}(t):j\in\mathcal{C}\right\\}\right)=Y(t)\right)>\nicefrac{{1}}{{2}},$
(16)

then pseudo competence preserves the ordering of true competences:

$p_{i}\geq p_{j}\iff\tilde{p}_{i}\geq\tilde{p}_{j}.$ (17)

The proof is given in appendix B. It is worth noting that while the condition
in eq. (16) is not too restrictive, it is also unavoidable. Conceptually, this
condition amounts to the committee $\mathcal{C}$ of peers being collectively
reliable. Equivalently, it is not possible to infer the reliability of an
expert based on opinions from a group that often collectively fails to
identify the true state of the world. Formally, we restrict our attention to
the case where experts are reasonably reliable: $p_{i}>\nicefrac{{1}}{{2}}$,
$\forall i\in[M]$, which implies that eq. (16) holds for every subset
$\mathcal{C}\subset[M]$ of experts. We further discuss the definition and the
properties of the pseudo competence for the experts that belong to the
committee $i,j\in\mathcal{C}$ in appendix C.

##  IV Fundamental Properties of Different BEE and SWARM Rules

There is a rich literature governing how to jointly sample and consult experts
when feedback from the true state of the world
$\left\\{Y(\tau):\tau\in[t-1]\right\\}$ is available to the player. In this
section, we propose unsupervised applications of different exploration-
exploitation strategies using pseudo competence as reward. Specifically, we
focus on UCB1, [11], due to its use of the Chernoff-Hoeffding bound, KL-UCB,
[12], due its optimality for the Bernoulli rewards, IMED, [13], due to its
near-optimal performance and empirical robustness, MOSS, [14], due to its
minmax optimality, and Thompson sampling due to the strong synergy between
posterior sampling and pseudo competences. The proposed BEE algorithms have
the following form:

Algorithm 1 BEE Algorithm

Require: Choice of $\Psi_{i}(\cdot)$ for exploration-exploitation strategy, as
defined in eq. (20)-(24).

Initialize:

Consult every expert on the first task,

Update agreements via eq. (18), estimate competences via (19) with
$\mathcal{C}_{1}=[M]$.

Loop:

$\mathcal{C}_{t}\leftarrow$ Pick top $m$ (bottom for IMED) experts ranked by
$\Psi_{i}(t)$,

$I_{t}\leftarrow\operatorname*{arg\,max}_{i\in[\mathcal{C}_{t}]}\Psi_{i}(t)$
($\operatorname*{arg\,min}$ for IMED),

Commit to $X_{I_{t}}$ as the player decision,

Update agreements via eq. (18), estimate competences via (19) with
$\mathcal{C}_{t}$.

As discussed in Section III, the notion of pseudo competence is built upon the
availability of peer opinions therefore, we will consider consulting multiple
experts for each task $t\in[T]$, equivalent to playing multiple arms, see, for
instance, [18]. Let $\mathcal{C}_{t}$ denote the set of experts consulted for
task $t\in[T]$ and define the reward from consulting an expert as whether that
expert agrees with the collective decision of the peers for that task:

$R_{i}(t;\mathcal{C}_{t})=\mathds{1}\left(X_{i}(t)=V\left(\left\\{X_{j}\left(t\right):~{}j\in\mathcal{C}_{t}\setminus\left\\{i\right\\}\right\\}\right)\right).$
(18)

Observe that contrary to the state feedback, opinions
$\left\\{X_{j}:j\in\mathcal{C}_{t}\right\\}$ are available from any subset
$\mathcal{C}_{t}\subset[M]$ of experts therefore, the empirical pseudo
competence estimate for an expert at time $t$ takes the form:

$\tilde{p}_{i,T_{i}(t-1)}\triangleq\frac{1}{T_{i}(t-1)}\sum_{\tau\in[t-1]:~{}i\in\mathcal{C}_{\tau}}R_{i}(\tau;\mathcal{C}_{\tau}).$
(19)

We will now use the statistics on agreements among experts as defined in eq.
(18) and the concomitant empirical competence estimation in eq. (19) to form
the relevant statistics $\Psi_{i}(t)$ for sampling and consulting experts in
the unsupervised setup.

To begin with the upper-confidence bound strategies, UCB1 leads to consulting
experts that have highest ranking in:

$\Psi_{i}^{\text{UCB1}}(t)=\tilde{p}_{i,T_{i}(t-1)}+\sqrt{\frac{2\log
t}{T_{i}(t-1)}}.$ (20)

Particularly in the Bernoulli case, several refinements to UCB1 algorithm
exist: Notably, [12] shows that Kullback-Leibler upper confidence bound (KL-
UCB) algorithm achieves the regret lower bound of [2]. In the unsupervised
setup, experts with the highest ranking according to the following
(operational)444[12] remark that the threshold $\log\left(t\right)$ should be
taken as $\log\left(t\right)+c\log\log\left(t\right)$ for analytical purposes,
where they recommend $c=0$ in practice. Furthermore, we experimentally
implement its more robust counterpart KL-UCB+, see [19]. statistics are
consulted:

$\Psi_{i}^{\text{KL-
UCB}}(t)=\max\left(q\in\left[0,1\right]:~{}T_{i}(t-1)~{}d\left(\tilde{p}_{i,T_{i}(t-1)},q\right)\leq\log\left(\frac{t}{T_{i}\left(t-1\right)}\right)\right),$
(21)

where Kullback-Leibler divergence $d\left(\cdot,\cdot\right)$ is defined as:

$d\left(p,q\right)=p\log\frac{p}{q}+\left(1-p\right)\log\frac{1-p}{1-q}.$

Albeit more computationally demanding, the performance of the KL-UCB algorithm
makes it an appealing choice for binary opinions. Alternatively, using indexed
minimum empirical divergence (IMED) algorithm of [13], we consult the experts
that have the lowest ranking according to:

$\Psi_{i}^{\text{IMED}}(t)=T_{i}(t-1)~{}d\left(\tilde{p}_{i,T_{i}(t-1)},\max_{i\in[M]}\tilde{p}_{i,T_{i}(t-1)}\right)+\log
T_{i}(t-1).$ (22)

Another key idea is that of minmax optimality, which is achieved by MOSS in
the supervised framework and can be applied to the unsupervised framework by
selecting experts with highest ranking in:

$\Psi_{i}^{\text{MOSS}}(t)=\tilde{p}_{i,T_{i}(t-1)}+\sqrt{\frac{\max\left(\log\left(\frac{T}{MT_{i}\left(t-1\right)}\right),0\right)}{T_{i}\left(t-1\right)}}.$
(23)

Finally, Thompson sampling (TS) suggests randomly sampling arms based on the
posterior distribution over competences. Specifically,

$\Psi^{\text{TS}}_{i}\left(t\right)=Z_{i},\text{ where
}Z_{i}\sim\text{Beta}\left(\alpha_{i}(t),\beta_{i}(t)\right).$ (24)

The prior is often taken be uniform for every expert,
$\left(\alpha_{i}(0),\beta_{i}(0)\right)=\left(1,1\right)$, $\forall i\in[M]$
and, in the Bernoulli case, update rules of the beta distribution have a well-
defined form, see, for instance, [20]:

$\left(\alpha_{i}(t),\beta_{i}(t)\right)=\left(\alpha_{i}(t),\beta_{i}\right)(t)+\left(R_{i}\left(t,\mathcal{C}_{t}\right)+1-R_{i}\left(t,\mathcal{C}_{t}\right)\right),\forall
i\in\mathcal{C}_{t},$

where $R_{i}\left(t,\mathcal{C}_{t}\right)$ is defined in eq. (18) and the
statistics
$\left(\left(\alpha_{i},\beta_{i}\right):j\in[M]\setminus\mathcal{C}_{t}\right)$
of the non-consulted experts are not updated at that time.

As a random process, $R_{i}\left(t,\mathcal{C}_{t}\right)$, as shown in eq.
(18), is defined conditionally with respect to the choice of experts through
$\Psi_{i}\left(\cdot\right)$, $\forall i\in[M]$, and the resulting opinions,
up to time $t$ of consulting. Therefore, it is challenging to form a complete
theoretical analysis of how choosing $R_{i}\left(t,\mathcal{C}_{t}\right)$
changes the the difference between the “rewards” in the unsupervised setup
compared to those that correspond to the true competences. Nevertheless, for a
fixed committee $\mathcal{C}$ of peers, choosing
$R_{i}\left(t,\mathcal{C}\right)$ pushes the competences together in a way
that is as quantified through eq. (15) of Proposition 1, making it possible to
observe the impact of using pseudo competences on the regret of the
exploration-exploitation strategies. The following result is a corollary to
Proposition 1 and [14, Theorem 2] for UCB1, [12, Theorem 1] for KL-UCB, [13,
Theorem 5] for IMED, [14, Theorem 6] for MOSS, and [21, Theorem 1] for
Thompson sampling.

###### Lemma 1

Let the player designate a subset of experts $\mathcal{C}\subset[M]$ as peers
prior to exploration and exploitation and consult them for every task
$\mathcal{C}_{t}=\mathcal{C}$, $\forall t\in[T]$. Define the difference
between competences:

$\Delta_{i}=\max_{j\in[M]}p_{j}-p_{i},$ (25)

and a potential function for a given set of competences:

$\Phi=\frac{\log T}{T}\sum_{\begin{subarray}{c}i\in[M]\setminus\mathcal{C}\\\
\Delta_{i}>0\end{subarray}}\frac{1}{\Delta_{i}}.$ (26)

Then, the regret of a BEE algorithm that picks
$I_{t}=\operatorname*{arg\,max}_{i\in[M]\setminus\mathcal{C}}\Psi_{i}(t)$
($\operatorname*{arg\,min}$ for IMED) via statistics for UCB1, eq. (20), KL-
UCB, eq. (21), or IMED, eq. (22), is bounded by:

$\tilde{R}_{T}\leq C\frac{\Phi}{2p_{\mathcal{C}}-1},$ (27)

where the constant $C=10$ for UCB1, $C=\nicefrac{{1}}{{2}}$ for KL-UCB and
IMED. The regret of Thompson sampling, eq. (24), also takes the form in eq.
(27) with $C=1+\varepsilon$ but with additional term of order
$O\left(\frac{M}{\varepsilon^{2}}\right)$. Furthermore, for MOSS, eq. (23),
the regret is upper bounded by:

$\tilde{R}_{T}^{MOSS}\leq\frac{23M}{T}\left[\frac{1}{2p_{\mathcal{C}}-1}\sum_{\begin{subarray}{c}i\in[M]\setminus\mathcal{C}\\\
\Delta_{i}>0\end{subarray}}\frac{\max\left(\log\frac{T\left(\left(2p_{\mathcal{C}}-1\right)\Delta_{i}\right)^{2}}{M},1\right)}{\Delta_{i}}\right].$
(28)

The proof is given in appendix D. The important takeaways from Lemma 1 are
twofold: First, using pseudo competences introduces additional regret within a
constant factor of the original regret bounds but facilitates exploration and
exploitation in the unsupervised regime. Second, the factor
$\nicefrac{{1}}{{\left(2p_{\mathcal{C}}-1\right)}}$ diminishes as the
committee $\mathcal{C}$ collectively becomes more competent, which is
important since the proposed BEE and SWARM rules that gradually select more
competent experts.

By consulting multiple experts, a set of opinions on each task is acquired and
making an unsupervised decision based on such sparsely sampled opinions is
often carried out by rules such as SML, EM, or BP from [9, 7, 8] respectively.
However, inference of pseudo competences allow an unsupervised opinion
aggregation strategy that instantaneously yield a decision:

$f\left((X_{i}(t),\tilde{p}_{i,T_{i}(t)}):i\in\mathcal{C}_{t}\right)=\operatorname{sign}\left(\sum_{i\in\mathcal{C}_{t}}X_{i}(t)\left(\tilde{p}_{i,T_{i}(t)}-\nicefrac{{1}}{{2}}\right)\right).$
(29)

The opinion-aggregation rule in eq. (29) is a linearized variant of the naïve
Bayes decision rule, which is robust to the variance of empirical averaging in
(19), as discussed in [22]. In Section V, we compare the BEE algorithm to
their SEE counterparts and we demonstrate the performance of the SWARM rule
that uses linearized naïve Bayes decision rule with pseudo competence-based
weights, comparing them to their state feedback-based counterparts.

Algorithm 2 SWARM Algorithm

Require:

Choice of $\Psi_{i}\left(\cdot\right)$ for exploration-exploitation strategy,
as defined in eq. (20)-(24).

Choice of $f\left(\cdot\right)$ for unsupervised opinion aggregation, as
defined (29)

Initialize:

Consult every expert on the first task,

Update agreements via eq. (18), estimate competences via (19) with
$\mathcal{C}_{1}=[M]$,

Commit to majority vote: $V\left(X_{i}:i\in[M]\right)$ as the first decision.

Loop:

$\mathcal{C}_{t}\leftarrow$ Pick top $m$ (bottom for IMED) experts ranked by
$\Psi_{i}(t)$,

Update agreements via eq. (18), estimate competences via (19) with
$\mathcal{C}_{t}$.

Commit to
$f\left((X_{i}(t),\tilde{p}_{i,T_{i}(t)}):i\in\mathcal{C}_{t}\right)$ as the
player decision.

##  V Experiments

In this section, we discuss empirical performance of BEE and SWARM algorithms
that rely on pseudo competences for reliability inference and UCB1, KL-UCB,
IMED, MOSS, or Thompson sampling for exploration and exploitation. For
experiments, we chose $M=100$ experts with competences chosen uniformly at
random from $\left[0.5,0.75\right]$ being consulted on $T=10^{5}$ tasks. The
reason for such a competence interval is to avoid powerful experts in a
community that would render the lack of supervision obsolete, similar to the
use of weak classifiers in the boosting framework, [5]. For BEE experiments,
we consider the true normalized regret as defined in eq. (6), where for SWARM
experiments, we consider the pseudo normalized regret in eq. (9), allowing the
opinion-aggregation rule over the best committee to have direct access to the
true competences. In other words, BEE algorithms are compared against
supervised rules with state feedback, where SWARM algorithms compete against
rules that explore and exploit with state feedback and aggregate opinions with
complete information. Figure 2 provides an overview of BEE algorithms and
Figure 2 provides one for SWARM rules.

###  V-A BEE

We allow subcommittee sizes $m\in\left[2,24\right]$, even numbers, where $m$
is the number of experts that are consulted for each task. Even number of
experts chosen to make sure peers for every expert can reach a deterministic
decision.

Figure 2 summarizes the performance of BEE algorithms that adaptively choose
their subcommittees. We note that MOSS- and TS-based policies perform better
than the rest for small subcommittee sizes, where KL-UCB-based BEE rule
outperforms all for larger subcommittee sizes $\left(m>8\right)$. Figure 9
illustrates the performance of UCB1, KL-UCB, Thompson sampling, MOSS, and IMED
with multiple plays for reference. Interestingly, BEE algorithms that use
upper-confidence bound-based exploration and exploitation strategies, as seen
in Figures 9-9, perform almost identically to their SEE counterparts for large
subcommittee sizes. On the other hand, the impact of supervision is clearer
across the board for IMED, in Figure 9, MOSS, in Figure 9, and Thompson
sampling, as seen in Figure 9. Importantly, Figures 9-9 indicate that BEE
rules that rely on IMED and KL-UCB sequentially consult experts that on
average provide opinions within $0.5\%$ of the probability of correctness of
the best available expert without any supervision upon consulting modest
number $\left(m=8\right)$ of experts for each task.

Figure 1: Performance Comparison of
Different BEE Algorithms

Figure 2: Performance Comparison of
Different SWARM Algorithms

Figure 3: Overview of Multi-play SEE Algorithms

Figure 4: IMED

Figure 5: KL-UCB

Figure 6: UCB1

Figure 7: MOSS

Figure 8: Thompson Sampling

Figure 9: Overview of the BEE Experiments: Performance Comparison to
Supervised Counterparts

###  V-B SWARM

Subcommittee sized up to $m=20$ appears to be sufficient for SWARM experiments
as all of the tested rules demonstrate lower than $1\%$ normalized pseudo
regret for $m>10$. Figure 2 outlines the performance of the SWARM algorithms,
with their supervised counterpart given in Figure 10, showing that MOSS-,
IMED- and TS-based rules perform the with the additional opinion-aggregation
objective. It might be expected for TS, as shown in Figure 10, considered the
synergy between consulting experts based on the posterior distribution on the
competences and using an approximation of the maximum a posteriori rule that
is naïve Bayes for opinion aggregation. It is worth noting however, that the
performance of IMED-based and MOSS-based consultation, which have overall
robust performance in the BEE framework as shown in Figures 9,9, stand out in
the SWARM framework, as seen in Figures 10,10. Furthermore, Figures 10,10
indicate a similar phenomenon for the upper-confidence bound-based strategies
as the BEE framework, where the performance difference between supervised and
unsupervised rules diminish almost entirely. Importantly, SWARM rules achieve
probability of correctness within $0.5\%$ of the opinion aggregation rule that
has direct access to true competences and uses the opinions from the best
available experts.

(a) Overview Multi-play SEE
with Opinion Aggregation

(b) Thompson Sampling

(c) MOSS

(d) IMED

(e) UCB1

(f) KL-UCB

Figure 10: Overview of the SWARM Experiments: Performance Comparison to
Supervised Counterparts

##  VI Conclusions

In this paper, we proposed techniques that allow exploration-exploitation
algorithms to operate in a regime where the rewards are observed indirectly
from opinions on dynamically changing tasks. The proposed measure of
competence not only allows instantaneous inference, which commonly requires
either state feedback or block processing, but also enables the use of a near-
optimal opinion aggregation rule in real time. Furthermore, we point out that
the formal analysis of the convergence and competence ordering for BEE and
SWARM algorithms are exciting open problems with the numerical evidence
presented here indicating their strong potential.

##  Appendix A On Averaging Opinions

Observe that the law of total probability yields the following:

$\mathbb{P}\left(X_{i}(t)=1\right)=\sum_{j\in\left\\{\pm
1\right\\}}\mathbb{P}\left(X_{i}(t)=1\;\middle|\;Y(t)=j\right)\mathbb{P}\left(Y(t)=j\right)$
(30)

Since
$\mathbb{P}\left(Y(t)=1\right)=\mathbb{P}\left(Y(t)=-1\right)=\nicefrac{{1}}{{2}}$
and $\mathbb{P}\left(X_{i}(t)=j\;\middle|\;Y(t)=j\right)=p_{i}$ for every
task, we can further write that:

$\mathbb{P}\left(X_{i}(t)=1\right)=\frac{p_{i}}{2}+\frac{1-p_{i}}{2}=\frac{1}{2},$
(31)

which indicates that $\mathbb{E}\left[X_{i}(t)\right]=0$, $\forall t$. The
ergodicity of the opinion process yields eq. (5). Note that this hold for
every expert.

##  Appendix B Proof of Property 1

We drop the time dependence, such as $\left\\{X_{i}(t),Y(t)\right\\}$, for
notational clarity and instead write $\left\\{X_{i},Y\right\\}$. The proof is
a direct application of the law of total probability:

$\displaystyle\tilde{p}_{i}$
$\displaystyle=\mathbb{P}\left(X_{i}=V\left(\left\\{X_{k}:k\in\mathcal{C}\right\\}\right)\right)$
(32)
$\displaystyle=\mathbb{P}\left(X_{i}=Y,V\left(\left\\{X_{k}:k\in\mathcal{C}\right\\}\right)=Y\right)+\mathbb{P}\left(X_{i}\neq
Y,V\left(\left\\{X_{k}:k\in\mathcal{C}\right\\}\right)\neq Y\right)$ (33)

Since $j\notin\mathcal{C}$, the opinion $X_{j}$ is conditional independent of
$V\left(\left\\{X_{k}:k\in\mathcal{C}\right\\}\right)$ and thus, whether an
opinion and votes over another set of opinions is correct or incorrect is
independent of one another. Formally:

$\mathds{1}\left(X_{i}=Y\right)\perp\mathds{1}\left(V\left(\left\\{X_{k}:k\in\mathcal{C}\right\\}\right)=Y\right).$
(34)

Therefore, one can write:

$\displaystyle\tilde{p}_{i}$
$\displaystyle=\mathbb{P}\left(X_{i}=Y\right)\mathbb{P}\left(V\left(\left\\{X_{k}:k\in\mathcal{C}\right\\}\right)=Y\right)+\mathbb{P}\left(X_{i}\neq
Y\right)\mathbb{P}\left(V\left(\left\\{X_{k}:k\in\mathcal{C}\right\\}\right)\neq
Y\right),$ (35)
$\displaystyle=p_{i}\mathbb{P}\left(V\left(\left\\{X_{k}:k\in\mathcal{C}\right\\}\right)=Y\right)+(1-p_{i})\left(1-\mathbb{P}\left(V\left(\left\\{X_{k}:k\in\mathcal{C}\right\\}\right)=Y\right)\right),$
(36)
$\displaystyle=p_{i}p_{\mathcal{C}}+(1-p_{i})\left(1-p_{\mathcal{C}}\right).$
(37)

Now consider the difference between pseudo competences:

$\displaystyle\tilde{p}_{i}-\tilde{p}_{j}$
$\displaystyle=p_{i}p_{\mathcal{C}}+(1-p_{i})\left(1-p_{\mathcal{C}}\right)-p_{j}p_{\mathcal{C}}+(1-p_{j})\left(1-p_{\mathcal{C}}\right),$
(38)
$\displaystyle=\left(p_{i}-p_{j}\right)p_{\mathcal{C}}+\left(1-p_{i}-\left(1-p_{j}\right)\right)\left(1-p_{\mathcal{C}}\right),$
(39)
$\displaystyle=\left(p_{i}-p_{j}\right)p_{\mathcal{C}}-\left(p_{i}-p_{j}\right)\left(1-p_{\mathcal{C}}\right)$
(40) $\displaystyle=\left(p_{i}-p_{j}\right)\left(2p_{\mathcal{C}}-1\right),$
(41)

which yields that as long as $p_{\mathcal{C}}>\nicefrac{{1}}{{2}}$, the pseudo
competence preserves the ordering of true competences: $p_{i}\gtrless
p_{j}\iff\tilde{p}_{i}\gtrless\tilde{p}_{j}$.

##  Appendix C The Pseudo Competence of Experts that Belong to the Same
Committee

When the pseudo competence of experts that belong to a committee
$\mathcal{C}\subset[M]$ is concerned, the definition of pseudo competence is
modified to exclude vote of the expert whose competence is to be inferred.
Formally, if $i\in\mathcal{C}$, then the pseudo competence $\tilde{p}_{i}$ is
defined as:

$\tilde{p}_{i}\triangleq\mathbb{P}\left(X_{i}=V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{i\right\\}\right)\right).$
(42)

Note that different from the definition in eq. (11) and the concomitant
properties listed in Proposition 1, peers of each expert have collectively
different competences. Therefore, further refinement for the ordering property
is necessary: First, let us define the random variable of correctness for each
experts:

$\eta_{i}(t)=\mathds{1}\left(X_{i}(t)=Y(t)\right),\forall t\in[T].$ (43)

Observe that $\eta_{i}(t)$ is a Bernoulli random variable with parameter
$p_{i}$, $\forall t\in[T]$ and $\eta_{i}(t)\perp\eta_{j}(t)$, $\forall i\neq
j\in[M]$ at all times. Therefore, given that $i,j\in\mathcal{C}$, the law of
total probability yields that we can write the pseudo competence as:

$\displaystyle\tilde{p}_{i}$ $\displaystyle=\sum_{\eta_{i}\in\left\\{\pm
1\right\\}}\sum_{\eta_{j}\in\left\\{\pm
1\right\\}}\mathbb{P}\left(X_{i}=V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{i\right\\}\right)\;\middle|\;\eta_{i},\eta_{j}\right)\mathbb{P}\left(\eta_{i},\eta_{j}\right),$
(44) $\displaystyle=\sum_{\eta_{i}\in\left\\{\pm
1\right\\}}\sum_{\eta_{j}\in\left\\{\pm
1\right\\}}\mathbb{P}\left(X_{i}=V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{i\right\\}\right)\;\middle|\;\eta_{i},\eta_{j}\right)\mathbb{P}\left(\eta_{i}\right)\mathbb{P}\left(\eta_{j}\right).$
(45)

The last line following from $\eta_{i}\perp\eta_{j}$. Further observe that:

$\displaystyle\mathbb{P}\left(X_{i}=V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{i\right\\}\right)\;\middle|\;\eta_{i},\eta_{j}\right)\mathbb{P}\left(\eta_{i}\right)$
$\displaystyle=\left[\mathbb{P}\left(V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{i\right\\}\right)=Y\;\middle|\;\eta_{j}\right)p_{i}+\mathbb{P}\left(V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{i\right\\}\right)\neq
Y\;\middle|\;\eta_{j}\right)\left(1-p_{i}\right)\right].$ (46)

Thus, one can explicitly write out the pseudo competence as:

$\displaystyle\tilde{p}_{i}$
$\displaystyle=\mathbb{P}\left(V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{i\right\\}\right)=Y\;\middle|\;X_{j}=Y\right)p_{i}p_{j}$
(47) $\displaystyle\hskip
10.00002pt+\mathbb{P}\left(V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{i\right\\}\right)\neq
Y\;\middle|\;X_{j}=Y\right)\left(1-p_{i}\right)p_{j}$ $\displaystyle\hskip
10.00002pt+\mathbb{P}\left(V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{i\right\\}\right)=Y\;\middle|\;X_{j}\neq
Y\right)p_{i}\left(1-p_{j}\right)$ $\displaystyle\hskip
10.00002pt+\mathbb{P}\left(V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{i\right\\}\right)\neq
Y\;\middle|\;X_{j}\neq Y\right)\left(1-p_{i}\right)\left(1-p_{j}\right).$

It is possible to derive $\tilde{p}_{j}$ by swapping $i$ and $j$ in eq. (47).
An important set of observation is as follows:

$\displaystyle\mathbb{P}\left(V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{i\right\\}\right)=Y\;\middle|\;X_{j}=Y\right)$
$\displaystyle=\mathbb{P}\left(V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{j\right\\}\right)=Y\;\middle|\;X_{i}=Y\right),$
(48)
$\displaystyle\mathbb{P}\left(V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{i\right\\}\right)\neq
Y\;\middle|\;X_{j}\neq Y\right)$
$\displaystyle=\mathbb{P}\left(V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{j\right\\}\right)\neq
Y\;\middle|\;X_{i}\neq Y\right),$ (49)

which follows from the fact that the rest of the committee
$\mathcal{C}\setminus\left\\{i,j\right\\}$ is the same for both sides of the
equations. Then, if the following holds:

$\frac{\tilde{p}_{i}-\tilde{p}_{j}}{p_{i}-p_{j}}=\mathbb{P}\left(V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{j\right\\}\right)=Y\\!\;\middle|\;X_{i}\neq
Y\right)\\!-\mathbb{P}\left(V\left(X_{k}:k\in\mathcal{C}\setminus\left\\{j\right\\}\right)\neq
Y\\!\;\middle|\;X_{i}=Y\right),$

then pseudo competences preserves ordering.

##  Appendix D Proof of Lemma 1

Note that with a fixed committee $\mathcal{C}$ and experts with competences
$\left\\{p_{i}:i\in[]M\right\\}$using agreement statistics as reward in the
unsupervised setup is equivalent to having Bernoulli arms with mean
$\left\\{\tilde{p}_{i},\forall i\in[M]\right\\}$ in the supervised setup. Then
the difference between rewards become:

$\tilde{\Delta}_{i}=\max_{i\in[M]}\tilde{p}_{i}-\tilde{p}_{i}=\left(2p_{\mathcal{C}}-1\right)\Delta_{i}$
(50)

by eq. (15) in Proposition 1, yielding the proposed upper-bounds on regret by
resorting to [14, Theorem 2] for UCB1,[14, Theorem 6] for MOSS, and [21,
Theorem 1] for Thompson sampling. For IMED and KL-UCB, observe that by
Pinsker’s inequality [23]:

$d\left(p,q\right)\geq 2\left(p-q\right)^{2}$ (51)

regret bounds of [12, Theorem 1] for KL-UCB, and [13, Theorem 5] for IMED (due
to bounded support for reward distribution) yield the proposed bounds. Of
course, the elegant analyses of both KL-UCB and IMED yields much sharper
bounds but the use of Pinsker’s inequality captures the impact of the
unsupervised framework on regret.

## References

  * [1] J. C. Gittins, “Bandit processes and dynamic allocation indices,” _Journal of the Royal Statistical Society: Series B (Methodological)_ , vol. 41, no. 2, pp. 148–164, 1979.

  * [2] T. L. Lai and H. Robbins, “Asymptotically efficient adaptive allocation rules,” _Advances in applied mathematics_ , vol. 6, no. 1, pp. 4–22, 1985\.
  * [3] P. Whittle, “Restless bandits: Activity allocation in a changing world,” _Journal of applied probability_ , pp. 287–298, 1988.
  * [4] N. Cesa-Bianchi and G. Lugosi, _Prediction, learning, and games_. Cambridge university press, 2006.
  * [5] R. E. Schapire and Y. Freund, _Boosting: Foundations and Algorithms_. MIT Press, 2012.
  * [6] H. V. Poor, _An introduction to signal detection and estimation_. Springer Science & Business Media, 2013.
  * [7] P. Welinder and P. Perona, “Online crowdsourcing: Rating annotators and obtaining cost-effective labels,” in _2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition-Workshops_. IEEE, 2010, pp. 25–32.
  * [8] D. R. Karger, S. Oh, and D. Shah, “Iterative learning for reliable crowdsourcing systems,” in _Advances in Neural Information Processing Systems_ , 2011, pp. 1953–1961.
  * [9] F. Parisi, F. Strino, B. Nadler, and Y. Kluger, “Ranking and combining multiple predictors without labeled data,” _Proceedings of the National Academy of Sciences_ , vol. 111, no. 4, pp. 1253–1258, 2014.
  * [10] W. R. Thompson, “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples,” _Biometrika_ , vol. 25, no. 3/4, pp. 285–294, 1933.
  * [11] P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multiarmed bandit problem,” _Machine learning_ , vol. 47, no. 2, pp. 235–256, 2002.
  * [12] A. Garivier and O. Cappé, “The kl-ucb algorithm for bounded stochastic bandits and beyond,” in _Proceedings of the 24th annual Conference On Learning Theory_ , 2011, pp. 359–376.
  * [13] J. Honda and A. Takemura, “Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards,” _Journal of Machine Learning Research_ , vol. 16, no. 113, pp. 3721–3756, 2015.
  * [14] J.-Y. Audibert, S. Bubeck et al., “Minimax policies for adversarial and stochastic bandits.” in _COLT_ , vol. 7, 2009, pp. 1–122.
  * [15] A. Jaffe, E. Fetaya, B. Nadler, T. Jiang, and Y. Kluger, “Unsupervised ensemble learning with dependent classifiers,” in _Artificial Intelligence and Statistics_. PMLR, 2016, pp. 351–360.
  * [16] S. Bubeck and N. Cesa-Bianchi, “Regret analysis of stochastic and nonstochastic multi-armed bandit problems,” _arXiv preprint arXiv:1204.5721_ , 2012.
  * [17] A. P. Dawid and A. M. Skene, “Maximum likelihood estimation of observer error-rates using the EM algorithm,” _Journal of the Royal Statistical Society: Series C (Applied Statistics)_ , vol. 28, no. 1, pp. 20–28, 1979.
  * [18] J. Komiyama, J. Honda, and H. Nakagawa, “Optimal regret analysis of thompson sampling in stochastic multi-armed bandit problem with multiple plays,” in _International Conference on Machine Learning_. PMLR, 2015, pp. 1152–1161.
  * [19] J. Honda, “A note on kl-ucb+ policy for the stochastic bandit,” _arXiv preprint arXiv:1903.07839_ , 2019.
  * [20] D. Russo, B. Van Roy, A. Kazerouni, I. Osband, and Z. Wen, “A tutorial on thompson sampling,” _arXiv preprint arXiv:1707.02038_ , 2017.
  * [21] S. Agrawal and N. Goyal, “Further optimal regret bounds for thompson sampling,” in _Artificial intelligence and statistics_. PMLR, 2013, pp. 99–107.
  * [22] D. Berend and A. Kontorovich, “A finite sample analysis of the naive bayes classifier.” _J. Mach. Learn. Res._ , vol. 16, no. 1, pp. 1519–1545, 2015\.
  * [23] T. M. Cover, _Elements of information theory_. John Wiley & Sons, 1999.


# MiniBooNE Data Releases

A. A. Aguilar-Arevalo14, B. C. Brown5, J. M. Conrad13, R. Dharmapalan1,7, A.
Diaz13, Z. Djurcic2, D. A. Finley5, R. Ford5, G. T. Garvey10, S. Gollapinni10,
A. Hourlier13, E.-C. Huang10, N. W. Kamp13, G. Karagiorgi4, T. Katori12, T.
Kobilarcik5, K. Lin4,10, W. C. Louis10, C. Mariani17, W. Marsh5, G. B.
Mills10,†, J. Mirabal-Martinez10, C. D. Moore5, R. H. Nelson3,⋆, J. Nowak9, I.
Parmaksiz16, Z. Pavlovic5, H. Ray6, B. P. Roe15, A. D. Russell5, A.
Schneider13, M. H. Shaevitz4, H. Siegel4, J. Spitz15, I. Stancu1, R. Tayloe8,
R. T. Thornton10, M. Tzanov3,11, R. G. Van de Water10, D. H. White10,†, E. D.
Zimmerman3
(The MiniBooNE Collaboration)  1University of Alabama; Tuscaloosa, AL 35487,
USA
2Argonne National Laboratory; Argonne, IL 60439, USA
3University of Colorado; Boulder, CO 80309, USA
4Columbia University; New York, NY 10027, USA
5Fermi National Accelerator Laboratory; Batavia, IL 60510, USA
6University of Florida; Gainesville, FL 32611, USA
7University of Hawaii, Manoa; Honolulu, HI 96822, USA
8Indiana University; Bloomington, IN 47405, USA
9Lancaster University; Lancaster LA1 4YB, UK
10Los Alamos National Laboratory; Los Alamos, NM 87545, USA
11Louisiana State University; Baton Rouge, LA 70803, USA
12King’s College London; London WC2R 2LS, UK
13Massachusetts Institute of Technology; Cambridge, MA 02139, USA
14Instituto de Ciencias Nucleares; Universidad Nacional Autónoma de México;
CDMX 04510, México
15University of Michigan; Ann Arbor, MI 48109, USA
16University of Texas at Arlington, Arlington, TX 76019
17Center for Neutrino Physics; Virginia Tech; Blacksburg, VA 24061, USA
⋆Now at The Aerospace Corporation, Los Angeles, CA 90009, USA
†Deceased

###### Abstract

The MiniBooNE experiment has provided data releases for most publications.
Occasionally it is necessary to move data release pages. This document
provides a single point of reference that will be updated by the collaboration
to point to the present location of the MiniBooNE data releases.

The MiniBooNE experiment has provided data releases for most publications.
From 2007-2021 these data releases were located on a website at Fermi National
Accelerator Laboratory. However, due to recent changes in policy at Fermilab,
those data release web-pages are no longer available except to those with
Fermilab services accounts.

To enable continuous access, the data releases have been copied in the same
form to a public site. The purpose of this note is to provide a citable arXiv
entry pointing to the present location of the MiniBooNE data releases. This
note will be updated as releases are moved or more releases are added. Many
will be moved to https://www.hepdata.net

The releases listed below, representing the complete set as of October 2021,
are located at: https://rtayloe.pages.iu.edu/MB/data-releases/

  * •

Data Released with A.A. Aguilar-Arevalo et al., “Updated MiniBooNE Neutrino
Oscillation Results with Increased Data and New Background Studies”,
arXiv:2006.16883 [hep-ex], Phys. Rev. D 103, 052002 (2021).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “Dark Matter Search in
Nucleon, Pion, and Electron Channels from a Proton Beam Dump with MiniBooNE”,
arXiv:1807.06137 [hep-ex], Phys. Rev. D 98, 112004 (2018).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “Observation of a Significant
Excess of Electron-Like Events in the MiniBooNE Short-Baseline Neutrino
Experiment”, arXiv:1805.12028 [hep-ex], Phys. Rev. Lett. 121, 221801 (2018).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “First Measurement of
Monoenergetic Muon Neutrino Charged Current Interactions”, arXiv:1801.03848
[hep-ex], Phys. Rev. Lett. 120, 141802 (2018).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “First Measurement of the Muon
Antineutrino Double-Differential Charged-Current Quasielastic Cross section”,
arXiv:1301.7067 [hep-ex], Phys. Rev. D88, 032001 (2013).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “Improved Search for
$\bar{\nu}_{\mu}\rightarrow\bar{\nu}_{e}$ Oscillations in the MiniBooNE
Experiment”, arXiv:1303.2588, Phys. Rev. Lett. 110, 161801 (2013).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “Event Excess in the MiniBooNE
Search for numubar to nuebar Oscillations”, arXiv:1007.1150 [hep-ex], Phys.
Rev. Lett. 105, 181801 (2010).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “Measurement of Neutrino-
Induced Charged Current-Charged Pion Production Cross Sections on Mineral Oil
at Enu $\sim$ 1 GeV”, arXiv:1011.3572 [hep-ex], Phys. Rev. D 83, 052007
(2011).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “Measurement of Muon Neutrino-
Induced Charged-Current Neutral Pion Production Cross Sections on Mineral Oil
at Enu = 0.5-2.0 GeV”, arXiv:1010.3264 [hep-ex], Phys. Rev. D 83, 052009
(2011).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “Measurement of the Neutrino
Neutral-Current Elastic Differential Cross Section”, arXiv:1007.4730 [hep-ex],
Phys. Rev. D 82, 092005 (2010).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “First Measurement of the Muon
Neutrino Charged-Current Quasielastic Double Differential Cross section”,
arXiv:1002.2680 [hep-ex], Phys. Rev. D81, 092005 (2010).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “Measurement of $\nu_{\mu}$
and$\bar{\nu}_{\mu}$ Induced Neutral-Current Single $\pi^{0}$ Production Cross
Sections on Mineral Oil at $E_{\nu}\sim$O(1 GeV)”, arXiv:0911.2063 [hep-ex],
Phys. Rev. D81, 013005 (2010).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “A Search for Electron Anti-
Neutrino Appearance at $\Delta m^{2}\sim 1$ eV2 Scale”, arXiv:0904.1958 [hep-
ex], Phys. Rev. Lett. 103, 111801 (2009).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “A Search for Muon Neutrino
and Anti-Neutrino Disappearance in MiniBooNE”, arXiv:0903.2465 [hep-ex], Phys.
Rev. Lett. 103, 061802 (2009).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “Unexplained Excess of
Electron-Like Events From a 1 GeV Neutrino Beam”, arXiv:0812.2243 [hep-ex],
Phys. Rev. Lett. 102, 101802 (2009).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “The Neutrino Flux Prediction
at MiniBooNE”, arXiv:0806.1449 [hep-ex], Phys. Rev. D. 79, 072002 (2009).

  * •

Data Released with A.A. Aguilar-Arevalo et al., “A Search for Electron
Neutrino Appearance at the $\Delta m^{2}\sim 1$ eV2 Scale”, arXiv:0704.1500
[hep-ex], Phys. Rev. Lett. 98, 231801 (2007).