Sequential Best-Arm Identification with Application to P300 Speller
Authors: Xin Zhou
Botao Hao
Tor Lattimore
Jian Kang
Lexin Li
Venue: Accepted by TMLR ()

Abstract: A brain-computer interface (BCI) is an advanced technology that facilitates direct communication between the human brain and a computer system, by enabling individuals to interact with devices using only their thoughts. The P300 speller is a primary type of BCI system, which allows users to spell words without using a physical keyboard, but instead by capturing and interpreting brain electroencephalogram (EEG) signals under different stimulus presentation paradigms. Traditional non-adaptive presentation paradigms, however, treat each word selection as an isolated event, resulting in a lengthy learning process. To enhance efficiency, we cast the problem as a sequence of best-arm identification tasks within the context of multi-armed bandits, where each task corresponds to the interaction between the user and the system for a single character or word. Leveraging large language models, we utilize the prior knowledge learned from previous tasks to inform and facilitate subsequent tasks. We propose a sequential top-two Thompson sampling algorithm under two scenarios: the fixed-confidence setting and the fixed-budget setting. We study the theoretical property of the proposed algorithm, and demonstrate its substantial empirical improvement through both simulations as well as the data generated from a P300 speller simulator that was built upon the real BCI experiments.

Published in Transactions on Machine Learning Research (08/2024)
Sequential Best-Arm Identification with Application to P300 Speller
Xin Zhou Division of Biostatistics, University of California at Berkeley
sinchou@@bereeley..dd
Botao Hao
haobotao@000@mmail..com
Google Deepmind
Tor Lattimore Google Deed
tor tor.lattimorre@maail.comm
Jian Kang
jiankang@umich..o edu
Department of Biostatistics, University of Michigan
Lexin Li
lezinli@@berkeley.cm edu
Division of Biostatistics, University of California Berkeley
Reviewed on OpenReview: https: openeevee......e net/ forum? id= QueNiiquN)
Abstract
A brain-computer interface (BCI) is an advanced technology that facilitates direct communi- cation between the human brain and computer system, by enabling individuals to interact with devices using only their thoughts. The P300 speller is primary type of BCI system, which allows users to spell words without using physical keyboard, but instead by cap- turing and interpreting brain electroenceehaalogran (EEG) signals under different stimulus presentation paradigms. Traditional non-adaptive presentation paradigms, however, treat each word selection as an isolated event, resulting in a lengthy learning process. To enhance efficiency, we cast the problem as soquence of best-arm identification tasks within the context of multi-armed bandits, where each (ask corresponds to the interaction between the user and the system for single character word. Leveraging large language models, utilize the prior knowledge learned from previous tasks to inform and facilitate subsequent tasks. We propose a sequential top-two Thompson sampling algorithm under two seenarios: the fixed-confilence setting and the fixed-budget setting. We study the theoretical property of the proposed algorithm, and demonstrate its substantial empirical improvement through both simulations as well the data generated from P300 speller simulator that was built upon the real BCT experiments.
1 Introduction
A brain-computer interface (BCT) a groundbreaking technology that enables direct communication be- tween the brain and an external device or computer system. It involves the use of various sensors, such electroencephalograalyy (EEG), electrocorticograplyy (ECoG), implantable neural electrodes, which detect and record the electrical signals produced by the brain. The brain signals are then processed by machine learning algorithms to interpret and extract meaningful commands and intentions. BCI holds immense po- tential for a wide range of ipplications in medicine, rehabilitation, and human augmentation. For instance, it provides a valuable communication aid for individuals with disabilities /Wolpaw et al. 2018
The P300 speller is a primary type of BCI system that allows users select characters spell words on a computer screen without using physical keyboard but instead brain signals. Tt is based the P300 event-

---

Published in Transactions on Machine Learning Research (08/2024)
Recoting
User
Uve
Computee Scoaen
Figure A schematic illustration: For each character or word the user intends to type, they focus their attention on the desired character or word on the virtual screen. To identify this character or word, the system presents a sequence of flashes on the virtual screen to the user. The user responds to these flashes, eliciting target or non-target brain signals. These EEG signals are captured by the electrodes, analyzed within a fixed time window after each flash, and transformed to a classifier score by a pre-trained classifier. A higher score indicates that the flash is more likely to contain the desired character or word. Consider the identification of a set of words the user intends to type as an example. It can be formulated as a series of best-arm identification problems. Here the system (not the user) acts as an agent, and it displays J words on the virtual screen. A task means to identify the single word the user intends type, which forms single bandit environment. There are totally M words the user intends to type, M total tasks. An action aj, say, pulling the jth arm, refers to flashing the jth word on the screen out of totally J candidate words. At the mth task and the tth step, the agent selects an action Atm from the action set A = fai....,a.)) and receives a reward R,, which corresponds to the classifier score from the flash. The optimal arm A E A means flashing the word the user intends to type in the mth task, and the decision umn refers to the word the system believes the user intends to type.
related potential (ERP), which is a brain response, in the form of a specific pattern of voltage fluctuation, that occurs approxinately 300 milliseconds after a relevant larget stimulus is presented. Specifically, the system presents
individual character or word through a sequence of flashes, with each flash being stimulus, usually in a grid-like layout on virtual screen for the user. If the flash contains the character or word the user wishes to type, an ERP is detected and recorded by a scalp EEG cap or similar device. In that case, the user elicits a target. brain signal. Otherwise, the user elicits a non-target brain signal. The recorded EEG signals are then analyzed by signal processing and machine learning algorithms, which detect the target stimulus and determine the target character. Figure I gives an illustration of the P300 speller.
A key limitation of the existing system is that the stimuli are usually presented in fixed and predetermined fashion. In addition, when presenting word (i.e., collection of characters), or a sentence (i.e., collection of words), the system treats each character or each word independently, and totally ignores the inherent relations among the characters or words. As a result, a large number of stimulus flashes are usually required to achieve a cortain level of accuracy of character or word identification. A language model essentially defines a collection of conditional probability distributions over the next token given the past tokens. Recently, large language models (LLMs) such as GPT-3 (Brown et al.) 2020) have achieved striking success in natural language processing, and can produce coherent and human- text. In this article, we aim to utilize language models the prior information to improve the sampling efficiency of the P300 BCI system through an adaptive stimulus design.
Contributions: Our contributions are three-fold.
We introduce a novel sequential best-arm identification formulation for the P300 speller BCI application. We treat each word the user wishes to type as an optimal arm, and formulate stimulus presentation as an adaptive selection problem. We leverage language models as an informative prior, and aim to identify the larget sequence of words as soon as possible in the fixed-confidence setting, or to make as fewer mistakes possible given fixed number of flashes in the fixed-budget setting.
We propose a sequential top-two Thompson sampling (STTS) algorithm that utilizes the prior information in a coherent. way. We derive the probability error bound in the fixed-budget setting that explicitly
2

---

Published in Transactions on Machine Learning Research (08/2024)
quantifies the prior effect through the conditional entropy of the prior distribution of the optimal arms. We also study the probability error bound in the fixed-confidence setting.
We conduct intensive experiments using both simulations and data generated from a P300 speller simulator that was built based on real BCT experiments (Ma et al.) 2022). We consider two ways to generate the target sentence, or say, the set of words, that a user wishes to type. First, we use GPT-3 (Brown et al. 2020) to generate two sets of words given two prompts. Next, we choose a full sentence from a benchmark phrase set (MacKenzie & Soukoreff 2003), and a full sentence from a recent news article (Wong) 2024). We use GPT-2 (Radford et al.] 2019) to inform the prior distribution, and demonstrate the substantial improvement over several state-of-Che-arl baseline algorithms that do not utilize the prior information.
Related work: We first review the literature on multi-armed bandits, then the literature on P300 BCL.
The multi-armed bandit (MAB) problem Robbins 1952) is a classic scenario in decision theory and rein- forcement learning that studies the problem of balancing exploration and exploitation. involves an agent that seeks to optimize actions that maximize expected rewards. The agent must explore the action space sulficiently to acquire the knowledge needed to exploit the best action. Best-arm identification (BAI) is a variant of MAB, where the learner's objective is to identify the optimal arm, ie., the arm with the highest expected reward, with high accuracy. BAT is especially relevant to the P300 speller problem, where the goal is to swiftly and accurately identify target characters or words.
For learning a single task, Even-Dar et al. (002) first introduced best-arm identification in the fixed- confidence sctting, ensuring a specifiod confidence level in the correctness of the identification. [Audbeet et al., (2010) studied the fixed-budget setting, where the goal is to identify the best arm within a given number of trials budget. Tn the BAT problem, we use sample complexity, the number of samples or pulls needed to correctly identify the best arm, to measure the theoretical properties of the algorithms. [Kaufmann et al. (2016) investigated optimal sample complexity, and Russo (2016) proposed the top-two Thompson sampling as an effective anytime sampling rule that does not depend on the confidence parameter. Its theorelical properties were studied in Russo (2016); Qin et al. (2017); Shang et al. (2020); Qin & Russo (2022 Jourdan et al. p2022). However, most existing asymptotic analyses did not quantify the prior effect. An exception is Qin & Russo (2022), who showed the prior effect through entropy in the simple regret setting. [Jun et al.) (2016) explored scenarios where multiple pulls of the arms can be conducted simultaneously in batches, rather than soquentially.
For learning multiple tasks sequentially, Boutilier et al. 2020 ; Simchowitz et al. 2021 Kveton et al. (022] Azizi et al. (2022) ) studied meta-learning in the context of Bayesian bandits for cumulative and simple regret minimization. They assumed that an unknown instance prior is drawn from a known meta-prior. Then each lask is sampled independently from this instance prior. In contrast, we assume the sequence of tasks is sampled from a joint prior distribution such that each task is not independent of each other. This necessitates the prior-dependent analysis that has only been studied in the regret minimization setting (Russo & Van Roy
2016 Hao et al. 2023
For P300 BCI studies, there have recently emerged a number of proposals for adaptive stimulus selection. 2011] used language models to weigh the output of stepwise linear discriminant analysis (LDA) for classification confidence. Park & Kim (2012) framed the problem as a a partially observable Markov decision process (POMDP). However, as the number of states grows, the belief states grow expo- nentially for POMDP, and the problem becomes intractable for a real-time system with large search space. Koçanaogulları et al. 2018) formulated the problem as query selection optimization and utilized language models to obtain the prior. However, they focused on single task setting. Naively extending their solution to multiple tasks in effect requires that the prior information of the previous tasks must all be correct. If an incorrect selection is made in one (ask, then the subsequent prior information would be incorrect, which would in turn derail the subsequent stimulus selection. Besides, they did not establish any theoretical guar- antec. Ma et al. (2021) used Beta-Bernoulli Thompson sampling for adaptive stimulus selection, but did not formulate the problem as best-arm identification, and did not incorporate any prior from language models. We refer to Heskebeck al. 20022) for review of the multi-armed bandits approaches in the BCT setting.
Speier et al.
3

---

Published in Transactions on Machine Learning Research (08/2024)
2 Sequential best-arm identification
2.1 Problem formulation
We formulate the problem as an agent sequentially interacting with M bandit environments, with each interaction referred to as a task. Each environment, indexed by m [M]] = [l...., "il...,,,,, is characterized by a random vector mm E R with prior distribution V/m()), which will be discussed in detail in Section 2.2 The action set is A = {ui,...,,. ...) C R', where aj is the standard basis vector with the jth element equal to one and the rest all zero. At each task m and step t, the agent selects an action Atm E A, and receives reward Re. = (A,,, mm) + Tm., where (: is the vector inner product, and (M..m) I's are a sequence of independent standard Gaussian variables. The optimal arm, Am = argmax lma, a, is also a random variable. Let (St, J, .FF)) P) denote a measurable space, He the history of task m up to step t, Dm = (Hr.1,..... -,,.--1m-11))) and IP, (-) Fm Dm..
We consider two distinct scenarios.
In the fixed-confidence scenario (Even-Das Dar et al. 2002), the agent chooses policy xhh = (me, )mm)) The horizon is not fixed in advance, as the agent decides a stopping time adapted to filtration, 1FTh = (Fr.m))on with Fi,m = (A1.. Ri.m:.... A,m Rt,m); where a is the Borel o-algebra. The agent makes a decision 4/m at the end of the task. For given confidence level E (0, 1), the objective is output a sequence of arms that are optimal for each task with probability at Icast 1 as soon as possible.
In the fixed-budger budget scenario (Bubeck et al. 2009), the agent is given budget for each task, choose a policy n"h = (Trmm))== and makes decision 1/m at the end of the task. The objective is to make the cumulative probability that aim is sub-optimal as small as possible.
In the context of a P300 speller experiment, take the identification of a set of words as an example. An agent refers to the system (not the user). A task means identifying a single word the user intends to type, which forms single bandit environment. An action, or say, pulling an arm, means flashing one word on the virtual user screen, and the reward is the classifier score computed based the captured EEG signals and pre-trained binary classifier. A decision is the word the system believes the user intends to type. A budget is the total number of flashes the system is to make for a single task. In this setup, M is the total number of words the user intends to type, and J is the total number of flashes.
We also comment that we formulate our problem as a scries of best-arm identification tasks within the context of multi-armed bandits, rather than reinforcement learning, because in our setting, there is no obvious definition of the state. If we define the underlying true word as a state, then the action we take would not affect the future state. Therefore, we feel the bandits formulation is more suitable for problem.
2.2 Prior specification
A language model p defines collection of conditional probability distributions (p::..., (PM) where Pm denotes probability distribution over the mth word given the first m - 1 words, [M]. In P300 speller experiment, the word that an individual attempts to type is viewed as the optimal arm. The joint distribution over the iollection of optimal arms (Ai,... Azr) can be written through the chain rule:
M Pm = II P (A = (.
p(Ai
AMr
II m=1
(2.1)
m=1
For each task, the prior distribution of 9m can be specified through
Um VP=P(Om (Om E .IAi.....
A²m-1) Σ
P (Om E . = = Ai Amn-)) x XP
(A = ailAA, = -
prior of the conditional mean reward
prior of the optimal arm
(2.2)
4

---

Published in Transactions on Machine Learning Research (08/2024)
which is mixture distribution. While the prior of the optimal arm can be defined by (2.1) there are several ways to specify the prior of the conditional mean reward, depending on the problem setting. For the P300 speller experiment, the reward only differs upon whether the stimulus is a target or non-target. Consoquently, all sub-optimal arms share the same mean reward. It thus natural to assume that,
Am =
-1 (p.....
11 ,)),
jth
where 1 (O0 of), and A exp(01), for some do, 01 0. We note that, for the P300 speller experiment, there often offline data available so that A can be accurately estimated (Ma et al. 2021
3 Sequential top-two Thompson sampling procedure
We propose sequential top-two Thompson sampling (STTS) algorithm that utilizes the prior information in coherent way. We also develop the corresponding stopping rule and the decision rule for both the fixedccofidence setting and the fixed-budget setting.
3.1 Sampling procedure
Our proposed STTS algorithm requires posterior sampling oracle that can be obtained exactly when conjugate prior is used, or through various approximation methods, such as Markov chain Monte Carlo.
Definition 3.1 (Posterior sampling oracle). Given a prior Vn over 6m and history He,m: Dm, the posterior sampling oracle, abbreviated as SAMP, is subroutine that returns a sample from the posterior distribution (0. -). Multiple calls to the procedure result in independent samples.
Our STTS algorithm extends the top-two Thompson sampling algorithm of Qin & Russo 2022); Russo (016)) that was designed for a single task setting now to the sequential multiple tasks setting, where we sequentially call the language model p to construct an informative prior. At task m and step i, STTS first draws a posterior sample fr.m using SAMP as well as the language model p, and sets Ar,,, argmax 0. Then STTS repeatedly samples from SAMP to obtain 6t.m: and sets At, argmax o until Atm,a # Atm.2 We pick At, = 1,,,,1 with probability equal to 3 E (0, 1]. and A,, Atm,2 with probability equal to B. In practice, we recommend = 1/2, following Qin & Russo (2022). We also comment that SAMP is a subroutine that is frequently used in the literature (see, e.g., Russo et al. 2018 Jourdan et al. 2022). It can obtained exactly when a conjugate prior is used, or approximately through various methods such as MCMC and variational inference.
3.2 Stopping rule and decision rule
For the fixed-confident setting, we employ the Chernoff stopping rule introduced by Garivier & Kaufmann (2016); Shang et al. (2020). More specifically, let Nr, denote the number of pulls of arm as before step for each task, He, the posterior mean for arm dg and Mt.i,j = (Na,f,, + Ne. (/,,, + Ne.)). We further define Ze, KT, M4,5,) for any two arms a, and a,, and define Ze(0s, a.) 0 if Maj Pe.i: and Zela,, a3) Zt,a, Ze.j. otherwise. Here we follow Garivier & Kaufmann (0016) and focus the simple case where the distributions are fully parameterized by their means, and we use KL #2) to denote the KL-divergence between the two distributions with means μ1 and f12 respectively. For each task m, the Chernoff stopping rule is,
Tm = inf LE N max min Zi(ai, aj), 2 71.5 =inf
TurfLE
E.A(a)AA((a))
where Yt.8 is the threshold parameter, and controls the level of confidence. As noted in Shang et al. (2020) Za a,) can be interpreted as generalized likelihood ratio statistic. As the agent interacts with M tasks sequentially, we employ the Bonferroni correction to handle multiple comparisons (Dunn] 1961.. As such, the fasely-wise error rate dM 5/M, and the level of confidence for each task becomes 8/M. For the
5

---

Published in Transactions on Machine Learning Research (08/2024)
Algorithm Sequential best-arm ideetification.
Input: The LLM p. the sampling oracle SAMP, the level of confidence o, the sampling parameter Output: A sequence of recommended actions "y.....,3Ms?
for m [M] do
Construct the informative prior based on p and the history (s1,,..,, 1m
Set 8= =00. 0.
while TRUE do Set 1. Sample 0r,m from SAMP, and set Ar,,,1 Ar,m, argmax In a. while At,,,1 A,, do Ro-sample fr.m from SAMP, and set Atm,2 = argmax pm end while
Sample Ct.m Bernoulli(3).
if Ct.m then
Set At,m At,m.1- else
Set Ar. = Ar,m2
end
Pull arm Atm, and receive Ru.
Update SAMP, Nr,s Pa, Mt.i.j"
if maXo,EA mina, faa)) ) Ze(ai, aj) 2 78,8 then Identify the best arm mm- STOP and break the while loop end if end while end for
final decision rule, choose the Bayes optimal decision rule, th., argmax,, Mm We summarize the full procedure for the exeedconfidence setting in Algorithm I
For the fixed- budget setting, the only change is that we stop the algorithm when some pre-specified budget constraint is met.
4 Theoretical properties
We first consider the fixed-budget setting. When the recommended word at the end of task wrong, we say the agent makes a mistake. The next theorem derives the corresponding probability error bound.
Theorem 4.1. Consider sequence of M besl-armm identifiontion problems, and assume for each task m, all the sub-optimal arms have the same and known sub- obboomammaitty gap, Am (Ai, a, pm), for any A. If STTS is applied with B 2 1/2 and with the Bayes optimal decision rule thay then for any positive integer-valued badgel nt,
1 M
Σ
P ( # A
M.
hm 6
log ((1+
1
Σ
m-
6
log J(1 +
M
1 1+n n
M
A,
1 n
(4.1)
where hm HA", 14
AD), and H(--.) is the conditional entropy.
We discuss the individual terms in the error bound in 4.1 The first. term in the bound is the main term, where hm = |: Ai) specifically characterizes the effect of the prior. In the P300 speller, the prior distribution of A informed by a language model such that HA 1 Ai) ) than log(J). This can be validated through an experiment shown in Figure 2 left panel, where the entropy of the probability distribution over the next word putted by GPT-2 is to be much smaller than
is much smaller

---

Published in Transactions on Machine Learning Research (08/2024)
5
0.5
-
entropy
4
0.4
0=
3
0.3
-
2
0.2
Prompt 1
1
Prompt 2
0.1
0
0.0
5
10
15
20
0
100 200 300 400 500
token index
mmax
Figure 2: Left panel: the entropy of the next word under two different prompts (the red and blue curves) versus the entropy of a uniform distribution (the dashed line). Right panel: the KL divergence between the allocation rule of STTS and the optimal allocation rule versus the maxinum number of steps when STTS stops. larger p indicates stronger prior.
uniform distribution. The second term in the bound the remainder term, which is the price the agent pays for making mistakes. Together, our bound in (4.1) explicitly characterizes the impact of the prior through the conditional entropy. When the prior is more informative, the conditional entropy decreases, and the error probability decreases. Morcover, the error probability converges to zero as the budget n goes to infinity.
In this theorem, we have assumed the gaps for all sub-optimal arms are the same and known. This assumption allows us to use a simple regret guarantee to bound the error probability. We argue this is a reasonable assumption, especially for the application such as the P300 speller, since all the non-target stimuli have the same level of FEG responses and the gap can usually be estimated though the offline data (see, e-g., Ma et al. 2021 Kalika et al., 2017 Mainsah et al.) 2017 On the other hand, when the gaps unknown, how to establish the theoretical guarantee for the top-two TS under a fixed budget is still open question even for the single task setting, and we leave it for future research.
We next consider the fixed-confidence setting. Choosing the threshold 2c5 = 4 In(4 + In(()) + 2C(In(( - 12) for some constant C, and applying Theorem 1 of [Shang el al. (2020) leads to an asymptotic sample complexity bound for STTS, coupled with the Bonferroni correction, as,
2mmi E[Tm]
M
M Σ
/
2J Am
lim sup 6-50
<
dum (Am),
1og(1/0)
where the expectation is taken over the prior of 6m on both sides. We remark that, this asymptotic result can not fully characterize the prior effect, as the asymptotic complexity measure only depends on the prior of the gap Am, rather than the prior of the position of the optimal arm. Typically, the overall sample complexity consists of two parts: the cost due to the optimal allocation rule, and the cost due to finding the optimal allocation rule. The latter is a lower-order term with respect to log(1/6). We conjecture that a more informative prior could greatly reduce the cost of finding the optimal allocation rule in the finite time. We conduct numerical experiment to verify our conjecture. The detailed simulation setting is described in Appendix B We report in Figure 2 right pancl, the KI-divergence between the asymptotically optimal allocation rule and the allocation rule induced by STTS. It is clearly seen that, when the prior is stronger, as reflected by a larger value of the parameter that controls the strength of the prior, the allocation rule induced by STTS converges faster the asymptotically optimal allocation rule. Mcanwhile, rigorous theoretical analysis requires much more involved finite-time dependent analysis for top-two TS, and we leave it future research.

---

Published in Transactions on Machine Learning Research (08/2024)
5 Synthetic experiments
5.1
Simulation setup
We carry out simulations to investigate the empirical performance of our method and the effect of prior. We compare with the following baselines solutions.
Vanilla top-two Thompson sampling (VTTS) (Russo) 2016 Qin & Russo 2022 the top-two Thompson sampling that does not use any informative prior from the LLM.
Random Policy (Random): the uniform sampling.
Batch Racing (BR) (Jun et al. 2016); A frequentist. algorithm that uses confidence interval to identify best arms in the fixed-confidence setting.
In our comparison, VTTS and Random use the same stopping rule and decision rule as described in Section while BR is only for the fixed-conidence setting. There are several other popular best-arm identification algorithms, c.g., Jamicson & Nowak 2014]; Garivier & Kaufmann (2016) in the literature, but none of them is designed for the sequential lask setling.
3.2
We define the prior for the mean reward On through 2.2 which requires the specification for the prior of the optimal arm, and the prior of the conditional mean reward. We assume the prior of the optimal arms satisfies the Markov properly, in that the distribution of the mith optimal arm depends only the (m- - 1jth optimal arm. More specifically, the optimal arm for mth task is sampled from PA = ay) = if E (supp(A
+ 1, (.ppppppmmm.. + J} n [J], and P(4 = az)) = (1 - p)/(J - if j E (supp(Amm1) + 1, supp((A;..))) +1 -- [11-]]n[]]] where supp(v) denotes the position where the non-zero entry for a unit vector is located, S denotes the complement of set S, and p [0, 1] is a parameter that controls the strength of the prior, with a larger p indicating stronger prior.
Next, set the prior of the mean reward of the jth arm to follow Gaussian mixture distribution,
P(0m.. E EAA 1 = Pm. N + oz) + (1 - Pm, ((,,
where we set the prior parameters as f 0, 0 = 0.2, A = 2. Moreover, when there is an oracle or external resource that reveals the identity of the optimal arm at the end each task, STTS can start with an exact prior, which we call STTS-Oracle. We set Pm. E [0, 1] for different algorithms as follows.
For STTS, we set Pm.j P(A a-lAm-1 1m for [T], where 1im.....mm1)) are the recom- mended actions.
For STTS-Oracle, we set Pm.j PAA ag1Am-1 am--) for j E [J], where realized instances of the optimal arms.
denote the
For VTTS, we set Pm,1 =... Pm.J J-1
Moreover, let pm.ry denote the posterior mean, and o the posterior variance.
We take one sentence as one experiment, and one word the sentence as one task, with each sentence consisting of M 20 words. We replicate each experiment B 200 times. We vary the number of arms J {10, 20}, and set the confidence level 0.1.
We consider two accuracy measures for each experiment. One is the 0-1 accuracy, where long the agent makes at least one mistake among 20 words, we mark that experiment failure. The other is the average accuracy, where we compute the percentage of correctly identified words among a sentence: EM Dh T( = A (tt.,/((MM) where vi A denotes the recommended action and the optimal action for the mth task the bth experiment, respectively.
We make a few comments. First, our proposed method does not require the Markov assumption. We have only adopted the Markov setting in our synthetic experiments for simplicity. Second, due to the Gaussian
8

---

Published in Transactions on Machine Learning Research (08/2024)
J=10
J=20
5000
5000
STTS
-STTS STTSS-Orade
total steps
4000
STTS-Oracle VTTS
total steps
4000
VTTS
3000
Random
3000
Random
BR
BR
2000
2000
1000
1000
0
0.00
0.25
0.50
0.75
0.00
0.25
0.50
0.75
1.00
p
p
The total number of steps versus the prior strength p for the fixed-confidence setting. smaller number of total steps indicates better performance of the method, and a larger p indicates stronger prior. The shaded area represents the 95% confidence interval.
Figure 3:
reward noise, the posterior distribution retains the form of Gaussian mixture distribution. As such, the posterior sampling oracle SAMP can be easily derived. Finally, we note that the proposed STTS is fairly general algorithm that can be coupled with any prior. As an illustration, we consider a different prior specification in Appendix C
5.2 Fixed-confidence setting
We first consider the fixed-confidence setting. We vary the parameter in the prior the optimal arm p E ( (0.1,0.2, 1.03. A larger p indicates a stronger prior effect, and p = J-1 means non- informative prior. our setting, we stop the algorithm when the Chernoff stopping rule is satisfied; i.e.
Ti min {
min Ftem Von m. suupp(pee.) + o
Mmmt Mmmte 2 9t
where bm. argmax, Mm,t, and %4- (2)gg(lgg())M//))) Here, we approximate the KL-divergence of two Gaussian mixture distributions by the KT-divergence two Gaussian distributions with the same mean and variance (Hershey Olsen 2007). Moreover, as the theoretical stopping rule of BR is conservative, we multiply range by a factor 0.25.
We compare different methods via the total number of steps under the varying prior strength p, whereas all methods achieve least 1 - 5 = 0.9 for the 0-1 accuracy. Figure reports the results. We see that, with the prior becoming more in informative, STTS clearly out perporrs the baseline solutions VTTS, BR, and Random. The improvement also increases with an increasing number of arms. When the prior of the optimal arms is uniformly distributed, STTS coincides with VTTS as expected. Furthermore, STTS and exhibit similar performances. This because, as the accuracy of STTS is consistently close to one, IPA -A = -) and PA = IA = wm-1) are very close. We also briefly comment that, in real P300 speller experiments, it impractical to run the number of steps into thousands. This step number can be adjusted by adjusting the accuracy measure. Here mostly use this simulation example to illustrate the effect of the prior and the difference in performance of different, solutions.
5.3 Fixed-budget setting
We next consider the fixed-budget setting. The sampling and decision rules remain the same, while the stopping rule is determined by whether the algorithm reaches pre-specified budget of maximum step t per task. We vary /max E (5, 10, 15, 100}, and E (J-1, 0,5, 0.8, 1.0).
We compare different methods via the average accuracy under the varying number of maximum step tmax- Figure Eegureerepon reports the results. We see that, when the prior becomes more informative, STTS and STTS-Orachs reach high accuracy with smaller budget. When the prior is non-informative, STTS and STTS-Orace perform similarly. We do not compare with BR, as it was designed for the fixed confidence setting only.
9

---

Published in Transactions on Machine Learning Research (08/2024)
J=10
p=
p= 0.5
p- 0.8
p.
1.0
1.0
1.0
1.0
average accuracy
B8 rogge accuracy
average accuracy
averadd accuracy
0.8
0.8
0.8
0.8
3..G
0.6
STTS STTS Oradle
0.5
STTS SITS Oracle
STTS SITS Oracle VTTS
STTS Oracle
VTTS
0.4
Random
0.4
Rancom
0.4
Random
25
number steps
number steps
number steps
number steps
J
p- 0.05
p- 0.5
p- 0.8
p-1.0
1.0
1.0
1.0
1.0
averade accuracy
evereoo accuracy
average accuracy
averege accuracy
0.8
0.8
0.8
SITS--Oracle VTTS
STTSS-rract VTTS
STTTS-Cracle VITS
Cracle
STTS- Oradde VTTS
STTS-Omace
0.4
0.4
0.4
25
75 100
25
75 160
25
75 100
100
number of steps
number of steps
number steps
number steps
Figure 4: The average accuracy versus the maximum number of steps mmax under different prior strength p for the fixed-budget setting. A larger p indicates a stronger prior. The shaded area represents the 95% confidence interval.
6 P300 speller simulator experiment
We carry out an experiment by generating the brain EEG signal data using a realistic P300 speller simulator developed by Ma et al. (2022). We do not use any public BCI data. This is because our method employs an adaptive policy that inffuences both data generation and collection, in contrast the random and non- adaptive baseline policy that is typically associated with such type of datasets. Thus, offline data alone is insufficient for our needs, and are aware of any online benchmark data that is suitable for our purpose. On the other hand, the simulator of Ma et al. (2022) has been built based upon real BCI experiments, and can adeptly generate signals that capture and match the complex tpetiolltemporal EEG patterns observed in real experiments. Moreover, we generate the sentence of words that a participant wishes to type using GPT-3 Brown et al. 2020). and obtain the prior distribution using GPT-2 [Rafford et al.) 2019). This mimics the potentially imperfect prior information that commonly arises real-world scenarios. All computations were done using CPUs on Google Colab Cluster.
More specifically, the P300 speller simulator of Ma et al. (2022) is built Bayesian generative model, and was trained with the data from actual BCT experiments. It employs novel split-and-merge Gaussian process priors to ensure an accurate emulation of the EEG signal generation mechanism inherent in the P300 speller in response to both target and non-target stimuli. For instance, the generated EEG signals exhibit the target ERPs of the frontal and central channels with a negative drop around 100 ms and an ascend to the first peak approximately at 250 ms latency. This pattern aligns seamlessly with the N100 and P300 patterns outlined in Stemmer & W Whitaker (2008), underscoring the simulator's capacity mirror real experimental conditions effectively. In our experiment, the noise spatial correlation based on Gaussian kernel function, the noise temporal correlation from an AR(1) model with an autocorrelation 0.9, and the mean magnitude of the target stimulus five times that of the non-target stimulus. In accordance with the current practice (Manyakov el al. 2011), we first train a binary classifier for the P300 offline data based on stepwise linear discriminant analysis (Donchin et al,, 2000 Krusienski et al. (2088). This classifier converts the raw EEG signals into the classifier scores, and we take these scores as the rewards in our setting. A higher score indicates that the EEG signal is more likely to correspond to a target stimulus.
set the number of electrodes to 16, the noise variance o {1, 2.5),
10

---

Published in Transactions on Machine Learning Research (08/2024)
Table 1: The total number of steps, i.e. the stimulus flashes, for the fixed-confidence setting, using the P300
speller simulator and the GPT-generated set of words. Two prompts are used. A larger LEGG indicates
larger noise level in the simulated EEG signals.
Prompt
EEG
Method
total steps (std)
Prompt
EEG
Method
total steps (std)
STTS
668.30 (136.5)
2
1
STTS
824.80 (171.3)
VTTS
1445.0 (237.2)
VTTS
1441.1 (221.8)
Random
6865.5 (826.6)
Random
7016.6 (956.8)
BR
2611.8 (112.6)
BR
2662.0 (140.3)
BBTS
1430.4 (203.5)
BETS
1421.7 (197.2)
2.5
STTS
1623.0
(240.6)
2.5
STTS
1877.4 (258.2)
VTTS
2493.2 (275.5)
VTTS
2445.8 (252.3)
Random
13523.2
(829.9)
Random
13517.0 (952.6)
BR
4396.4
(322.8)
BR
4441.7 (271.2)
BBTS
1712.5 (248.1)
BBTS
1694.0 (266.8)
We consider two ways to generate the target sentence, say, the set of words, that a user wishes to type. First, use GPT-3 (Brown et al. 2020 to generate M 20 words under two given prompts, "The most popular food in the United States is" as Prompt 1, and "My favorite sport is" as Prompt 2. Next, we choose a sentence with M = 9 words from a benchmark phrase set (MacKenzie & Soukoreff 2003). and sentence with M- = 15 words and punctuation marks from a recent news article on Nature (Wong 2024 We use GPT-2 (Radford et a 2019) to inform the prior distribution and specify the prior of the optimal arms. That is, given an input token, GPT-2 specifies a probability distribution of the next token over the full vocabulary space. Besides, for the very first word in the set of words, we provide the prompt to GPT-2 to obtain the prior in the GPT-3 generation case, provide no information at all to GPT-2 in the case of using the sentence from the benchmark phrase set, and provide the preceding sentence to GPT-2 in the case of using the sentence for the news article. We truncate the vocabulary size of GPT-2 from the original size of 50257 to 100, following the top- sampling (Fan et al.) 2018) and the muclous sampling (Holtzman et al. 2019) This keeps the candidate words with the lop-100 highest probabilities, and in effect substantially reduces the size of the action space to = 100. We repeat each prompt B 100 times, and set the confidence level at 1 0.9. We report the results based on GPT-3 generation in this section, and report the results based the chosen sentences in Appendix E
We compare the algorithms studied in Section experiment continue to run and reveal the identity of the optimal arm. As such, STTS and STTS-Oracle yield the same results. We also add the comparison with Beta- BettoBernoulli Thompson sampling (BBTS) algorithm of Ma et al. (2021).
5.1
When a wrong action is recommended, we let the
For the fixed-confidence setting, we stop the algorithm when the Chernoff stopping rule is met. Table reports the total number of steps, ie., the stimulus flashes, whereas the 0-1 accuracy and the average accuracy for all methods are above 0.9. We see that, facilitated by the LLMM-informed prior, STTS manages to reduce the total number of stimulus flashes by 25% to 50%, while maintaining about the same accuracy.
For the fixed-budget setting, we stop the algorithm when it reaches the pre-specified maximum number of flashes fmax E (5, 10, 15,..., 150). Figure 5 reports both the 0-1 accuracy and the average accuracy. We see that STTS achieves the highest accuracy compared to the alternative solutions. We also note that, the bascline random policy, which is currently used in most P300 experiments, requires about 150 steps to reach the 95% accuracy. This agrees with the practical observations that usually 100 to 150 steps are needed (Kindermans et al. 2012). In contrast, our method only requires 60 steps, which is significant improvement.
7 Conclusion
The BCI technology has the potential to revolutionize human communication by bypassing physical con- straints and interacting directly with the brain. In this article, we have proposed a sequential best-arm
11

---

Published in Transactions on Machine Learning Research (08/2024)
Prompt
EEG
EEG = =2.5
EEG
22.5
average accuracy
1.00
average eccuracy
1.00
1.00
ST -Random RRTS
1.00
-STTS
0.75
0.75
accuracy
0.75
accuracy
0.75
-Random RRRTS
0.50
0.50
-VTTS
VTTS -Random
Random
number steps
number steps
number steps
number of steps
Prompt
EEG
FEEG = 2.5
O
1
EEG
-2.5
average acccurac
1.00
Sereegg accuracy
1.00
1.00
-TTTS -VITS
1.00
-STTS
-VTTS
0./b
0.75
accuracy
-BTTS
Lcccurac
0.75
-BBTS
0.50
0.50
0.50
0.25
SSTS -Random
0.25
SSTS -Rendomm -BSTS
0.00
0.00
0.00
0.00
100
150
100 number of steps
150
150
150
number steps
number of steps
number of steps
Figure The average accuracy and the 0-1 accuracy for the fixed-budget setting using the P300 speller simulator and the GPT-generated of words. Two prompts are used. A larger BB indicates a larger noise level in the simulated EEG signals.
identification formulation for the P300 speller BCI system that greatly enhances its sampling efficiency. It integrates the prior information derived from LLMs with the top-two Thompson sampling algorithm. However, it is more than merely simple extension, and offers several useful contributions. Notably, algorithm extends Qin & Russo (2022); Koçansogulları et al. (2018) from the setting of single task to that of multiple and dependent tasks, while relaxing the stringent requirement that all priors have to be correctly specified. Our theory, to the best of our knowledge, is the first work that establishes an explicit error probability bound for top-two Thompson sampling within a fixed-budget context. Finally, we apply our method the P300 speller type BCT experiments, which we hope could pave the way for more adoption of adaptive bandits algorithms in this important application area.
References
Oven-Yees Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In COLT, pp. 41 53, 2010.
Mohammadjavad Azizi, Branislav Kveton, Mohammad Ghavamzadeh, and Sumeet Katariya. Meta-learning for simple regret minimization. arXiv preprint XrX::22202. 12888, 2022.
Craig Boutilier, Chih Wei Hsu, Branislav Kveton, Martin Mladenov, Csaba Szepesvari, and Manzil Zaheer. Differentiable meta-learning of bandit. policies. Advances in Neural Information Processing Systems, 33: 2122 2134, 2020.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits problems. In Algorithmic Learning Theory: 20th International Conference, ALT 2009, Porto, Portugal, October 3-5, 2009. Proceedings 20, pp. 23 37. Springer, 2009.
12

---

Published in Transactions on Machine Learning Research (08/2024)
Bernardo Dal Seno, Matteo Matteucci, and Luca T Mainardi. The utility metric: novel method to assess the overall performance of discrete brain-computa computer interfaces. IEEE Transactions on Neural Systems and Rehabilitation Engineering, 18(1):20 28, 2009.
Emanuel Donchin, Kevin M Spencer, and Ranjith Wijesinghe. The mental prosthesis: assessing the speed p300-based brain-computer interface. IEEE transactions on rehabilitation engincering, 8(2):174-179, 2000.
Olive Jean Dunn. Multiple comparisons among means. Journal of the American statistical association, 56 (293):52-644 1961.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov decision processes. In COLT, volume 2, pp. 255-277 270. Springer, 2002.
ar preprint Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. arXiv:1805.0488, 2018.
Aurélion Garivier and Emilic Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pp. 998 1027. PMLR, 2016.
Botao Hao, Rahul Jain, Tor Lattimore, Benjamin Van Roy, and Zheng Wen. Leveraging demonstrations improve online learning: Quality matters. arXiv preprint (xXi:2232.00811) 2023.
John R Hershey and Poder A Olsen. Approximating the kullback leibler divergence between gaussian mixture models. In 2007 IEEE International Conference on Acoustics, Speech and Signal Proeessing-CAASSP '7, volume 4, pp. IV-317. IEEE, 2007.
Frida Heskebeck, Carolina Bergeling, and Bo Bernhardsson. Multi-armed bandits in brain-computer inter- faces. Frontiers in Human Neuroscience, 16, 2022.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degener- ation. In International Conference on Leorning Representations, 2019.
Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In 2014 48th Annual Conference Information Sciences and Systems (CISS), pp. 1 6. IEEE, 2014.
Mare Jourdan, Rémy Degenne, Dorian Baudry, Rianne de Heide, and Emilic Kaufmann. Top two algorithms revisited. arXiv preprint arXio:2206. 05979, 2022.
Kwang-Sung Jun, Kevin Jamieson, Robert Nowak, and Xiaojin Zhu. Top arm identification in multi-armed bandits with batch arm pulls. In Artificial Intelligence and Statistics, pp. 139 148. PMLR, 2016.
Dmitry Kalika, Leslie M Collins, Chandra S Throckmorton, and Boyla O Mainsah. Adaptive stimulus selection in ersebased computcomputer interfaces by maximizing expected discrimination gain. In 2017 IEEE International Conference on Systems, Mon, and Cybernetics (SMC), pp. 1405-1410. IEEE, 2017.
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17:1-42, 2016.
Pieter-Jan Kindermans, David Verstraeten, and Benjamin Schrauwen. A bayesian model for exploiting application constraints to enable unsupervised training of a p300-based bei. PloS one, 7(4))e33758, 2012.
Aziz Koçanaogulları, Yeganeh M Marghi, Murat Akçakaya, and Deniz Erdogmuş, Optimal query selection using multi-armed bandits. IEEE signal processing letters, 25(12):180--1874 2018.
Dean J Krusienski, Eric W Sellers, Dennis McFarland, Theresa M Vaughan, and Jonathan Wolpaw, Toward enhanced p300 speller performance. Journal of neuroscience methods, 167(1):15 21, 2008.
13

---

Published in Transactions on Machine Learning Research (08/2024)
Branislav Kveton, Mikhail Konobeev, Manzil Zaheer, Chih-wei Hsu, Martin Mladenov, Craig Boutilier, and Csaba Szepesvari. Meta-thompson sampling. In International Conference on Machine Learning, pp- 5884 5893. PMLR, 2021.
Tianwen Ma, Jane E Huggins, and Jian Kang. Adaptive sequence-based stimulus selection an erp- based brain-computer interface by thompson sampling in a multi-armed bandit problem. In 2021 IEEE International Conference on Bioinformalics and Biomedicine (BIBM), pp- 3648 3655. IEFE, 2021.
Tianwen Ma, Yang Li, Jane E Huggins, Ji Zhu, and Jian Kang. Bayesian inferences on neural activity in cog-based brain-computer interface. Journal of the American Statistical Association, pp. 1-12, 2022.
Scott MacKenzie and R William Soukoreff. Phrase sets for evaluating text entry techniques. In CHT03
extended abstracts on Human factors in computing systems, pp. 754 755, 2003.
BO Mainsah, G Reeves, LM Collins, and CS Throckmorton. Optimizing the stimulus presentation paradigm design for the p300-based brain-computer interface using performance prediction. Journal of neural engi- neering, 14(4):046025, 2017.
Nikolay V Manyakov, Nikolay Chumerin, Adrien Combaz, and Marc M Van Hulle. Comparison of classifi- cation methods for p300 brain-computer interface on disabled subjects. Computational intelligence and neuroscience, 2011:1-12, 2011.
Jaeyoung Park and Kee-Eung Kim. A pomdp approach to optimizing p300 speller bei paradigm. IEEE Transactions on Neural Systems and Rehabilitation Engineering, 20(4):584 594, 2012.
Chao Qin and Daniel Russo. Adaptivity and confounding in multi-armed bandit experiments. arXiv preprint arXiv:2202.0005: 2022.
Chao Qin, Diego Klabjan, and Daniel Russo. Improving the expected improvement algorithm. Advances in Newral Information Processing Systems, 30, 2017.
Alee Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAT blog, 188):9, 2019.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mothe- matical Society, 58(5):527 - 535, 1952.
Daniel Russo. Simple bayesian algorithms for best arm identification. In Conference on Learning Theory, pp. 1417 1418. PMLR, 2016.
Daniel Russo and Benjamin Van Roy. An information-thcorcti analysis of thompson sampling. The Journal of Machine Learning Research, 1711):2442-2477 2016.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Tan Osband, Zheng Wen, el al. Lutorial on thompson sampling. Foundations and Trendso in Machine Learning, 11(1):1 96, 2018
Xuedong Shang, Rianne Heide, Pierre Menard, Emilie Kaufmann, and Michal Valko. Fixed-confidencce guarantees for bayesian best-arm identification. In International Conference on Artificial Intelligence and Slatistics, pp. 1823 1832. PMLR, 2020.
Max Simchowitz, Christopher Tosh, Akshay Krishnamurthy; Daniel J Hsu, Thodoris Lykouris, Miro Dudik, and Robert E Schapire. Bayesian decision maasinnnmmaiiggg under misspecified priors with applications to meta- learning. Advances in Neural Information Processing Systems, 44:26382-26309 2021.
William Speier, Corey Arnold, Jessica Lu, Ricky K Taira, and Nader Pouratian. Natural language processing with dynamic classification improves p300 speller accuracy and bit rate. Journal of Neural Engineering. 9 (1):016004, 2011.
Brigitte Stemmer and Harry A Whitaker. Handbook of the Neuroscience of Language. Academic Press, 2008.
14

---

Published in Transactions on Machine Learning Research (08/2024)
Jonathan R Wolpaw, Herbert Ramoser, Dennis McFarland, and Gert Pfurtscheller. Eeg-based communi- cation: improved accuracy by response verification. IEEF transactions on Rehabilitation Engineering, 6 (3):326 333, 1998.
Jonathan R Wolpaw, Richard S Bodlack, Domenic J Reda, Robert J Ringer, Patricia G Banks, Theresa M Vaughan, Susan M Heckman, Lyun M McCane, Charles S Carmack, Stefan Winden, et al. Independent home use of brain-computer interface by people with amyotrophic lateral sclerosis. Neurology, 91(3):
c258-c267, 2018.
Carissa Wong, Smoking bans are coming: what does the evidence say? Nature, 628:695 696, 2024.
A Proof of Theorem
We first consider the case when the recommended action wrong, the subsequent task would use the wrong information. Suppose the prior as specified Section 2.2 Define the sub-optimality gap Am = (Amm 0m) (a, mm) for any a E A, + A... Note that
E [(Ar 0m) (Wm: 0m)) = E (((A 0m) (p's 0m)) (1m + ATd + E [((A 0m) - (tim 0m)) (vim = AT))
E [m (v' * A
where th is the recommended action at the end task m. Since we assume all the sub-oplinal arms have the same mean reward, and the sub-optimality gap is known, the error probability can be bounded through the simple regret:
1 P (1/m + A = Am
E[ 9m) (w': 0m
where the expectation in the seft-hand-side is with respect to the prior distribution of 0.. We then employ Proposition 1 of Qin & Russo (2022) for the top-two Thompson sampling for a single task. Define an event &m = { =
#m-1 = J- starting with a correct prior, we decompose the simple regret term based on &m as,
. As Qin & Russo (2022) requires the top-two Thompson sampling
E [44%) 0m) - (W', 0m)) = [((Am) 0m) - (thm 0m)) I(EM)) + [((A) 0m) - (Wm 9m,) T(E
(A.1)
Applying Proposition of Qin & Russo (2022). we obtain that,
I s BV log(
(o (1 + (A - A7)(1 + n2-1
(A.2)
where H(-l.) is the conditional entropy. To bound 12, have that,
12 EE [[(A,,
0m) (Wm, 0m)) I((E))
<< Am
E
I
(1)
Ai..... 1m-1 = A 1)))
( = A3W13 13-1:-.. = Ai) 1)
m
Am
PP
j=1
m--1
(1 PP (by + 13105-1 -4)1
Am
Applying Proposition 1 of Qin & Russo (2022 again, we have that,
6
Log(J(C + n)) IH) A1)
P (v) # Al10y-1 - 0 Ai) <
(A.3)
+ n
15

---

Published in Transactions on Machine Learning Research (08/2024)
Denote Pm 6[log(J(1 + n))H(A Am A1)(1 n)-11////Am. obtain that,
Putting A.1
A.3
together, we
(
12 (1 pj)
IP (1 # Am) S Pm
j=1
Summing over all the tasks, we obtain that,
M
M
M
m-1
Σ m==1
( # Am) S Pm
Σ
+
Σ
1 1
II (1 (1-p))
m=1
m=1
==1
where the second term is the price the agent pays for the wrong prediction. This completes the proof.
B Additional discussion on the theory
First, we note that, for the fixed-budget setting, there is another practical scenario where at the end of task m, the agent is given the identity of the optimal arm Am If the recommended action is wrong, the agent pays an extra price c. For P300 speller, if the system outputs a wrong recommendation, the participant will gaze the backspace and the system will repeat the process until the right word recommended. In this case, the event En {v1 Ai...., 4'm-1 11 always holds. Based on A.2). the error probability can be bounded by
M Σ Pv + Am m=
M
hm
log(J(1 n))
S
m M V
M
1
m=
and the number of mistakes is bounded by > EM P (1/m + A
Next, we verify the role of prior in the fixed-confidence setting in our conjecture in Section 4 Specifically, we study how fast the allocation rule of each arm using STTS converges to the optimal allocation rule and how the information the prior affects the convergence. Following the prior specified in Section 3 and the computation in IShang et al. (2020), the optimal allocation rule p" pulls the optimal arm with probability
1/2, and all the other arms with probability 1/(2J - 2). We set the prior parameters и == 0, 1, A 0.5, the number of arms J 10, and we vary p (0.1, 0.9). Define Pt.e, Nr, the proportion of selections of arm a, before step t. The algorithm stops when it reaches the pre-specified maximum number of steps fmax E (50, 100, 150. .50)) per task. Figure 2 right panel, reports the KL divergence KL(Pt,P") that compares the STTS allocation rule and the optimal allocation rule. We see clearly that, when the prior becomes stronger, the allocation rule induced by STTS converges faster to the optimal allocation rule.
C Alternative prior specification
Our proposed algorithm STTS general and can be coupled with any prior specification. As an illustration, we consider Gaussian prior specification. Recall the language model Pm only requires the previous best A to define the prior distríbution Vm = =V(mm (A o)T, where do is the standard deviation parameter, and Pm specified as follows. We first introduce three matrices U(I) U22), and U13).
For (11), we set.
(()) - 1, (02 (2- Jida
0, otherwise
which means that the optimal arm the next task is more likely to be the one immediately following the current. optimal arm.
16

---

Published in Transactions on Machine Learning Research (08/2024)
For UT2), set
1, (1.J2) E (2,3)), (11,),,22))....0--),,000-0---0- 1,
(122)
J1:d2
0, otherwise
which consists of two groups where the first (J 2) arms are in the first group, and the last two arms are in the second group.
For US}) set
1. (2- (11
U+3)) Judz
0.5, (j2 -1) (2 J,2]
0, otherwise
which possesses more uncertainty than U())
Let ej be the unit vector with length J with the jth entry being 1. We define Pm (m for m 2 2, where U takes one of the forms of U(), U(), and U(3), Ao controls the magnitude of the best arm. For m = I, we assign each arm to be the optimal arm with equal probability, and V1 = ( if arm j is the optimal arm. The instance 6n is sampled from the prior distribution Vn- In this case, we set the posterior mean pm.t.j [[0mj E . Dm)) and the posterior variance mm Var(Om. -HH Dm)) Moreover, set the number of tasks M 20, and the agent interacts with M bandit instances with the confidence level 1 - = 0.9, and the reward noise variance o² = 1. For VTTS, we specify the non-informative Gaussian prior as Mo,m.jj = O, and Dom = 10 for E [J].
Table 2: The accuracy and the number of total steps with a Gaussian prior specification. larger po and a smaller dg means a stronger prior information.
Ho
To
Method
U
((2)
U(3)
accuracy
steps
accuracy
steps
accuracy
steps
5
0.5
STTS
100.0
60.0
100.0
50.8
98.5
307.5
VTTS
100.0
253.1
100.0
251.4
99.5
715.9
Random
100.0
405.1
100.0
406.1
98.0
1351.3
5
0.5
STTS
100.0
47.1
100.0
47.3
99.5
76.6
VTTS
100.0
184.1
100.0
183.3
99.5
370.6
Random
100.0
295.7
100.0
296.6
99.5
708.5
1
STTS
98.5
412.1
97.5
429.8
89.5
2008.0
VTTS
98.5
644.3
98.5
655.8
89.0
2183.9
Random
96.5
1052.1
98.5
1048.1
82.5
3332.3
1
STTS
99.5
81.8
98.5
80.3
94.5
1115.3
VTTS
99.5
267.6
99.5
273.2
93.5
1286.8
Random
99.5
449.0
100.0
459.3
94.0
2088.8
10
0.5
STTS
100.0
62.6
98.5
62.2
98.5
455.5
VTTS
100.0
480.9
100.0
482.1
99.5
1110.1
Random
100.0
1030.0
99.5
1036.2
98.0
3173.1
5
0.5
STTS
100.0
54.9
100.0
54.8
100.0
94.8
VTTS
100.0
333.1
100.0
336.3
100.0
525.7
Random
100.0
764.5
100.0
760.8
100.0
1517.3
STTS
98.5
1588.8
96.0
1425.2
93.0
5362.4
VTTS
99.0
2162.3
98.0
2145.4
94.5
5700.2
Random
95.5
4803.8
95.0
4786.2
88.0
11594.4
1
STTS
98.5
109.9
100.0
138.0
97.0
2341.1
VTTS
100.0
597.4
100.0
616.5
97.5
2771.5
Random
100.0
1375.8
98.5
1424.1
96.5
6288.7
17

---

Published in Transactions on Machine Learning Research (08/2024)
We repeat the experiments 200 times for J E {5, 10), Mo {4,5), and du E {0.5, 1}. Table 2 reports the accuracy and the number of total steps. It. is seen from the table that STTS achieves the smallest number of total steps, while maintaining the desired accuracy. When po is large and do is small, which indicates a strong prior information, the improvement of STTS over VTTS in terms of the total steps is more evident.
D Computational complexity evaluation
In the P300 speller system, sequence of flashes is presented on virtual screen to the user. The time interval between two consecutive flashes is constant, denoted Co. which is also the time taken for each step. We follow Ma et al. (2021), and set this time interval = 160 ms. We observe that our proposed algorithm as well as the alternative algorithms require much shorter time than co in each step. As such, instead of reporting the computational time alone, we employ the information transfer rate (ITR) (Wolpaw et al.) 1998), and the BCI utility (Utility) (Dal Seno et al. 2009). as the metrics to evaluate the overall computational complexity of all the algorithms. Specifically, we compute the two measures as,
1 logg J + +ooogg o + (1 (1- (1-6) log2 (-
ITR =
Utility
max {0, (2x - 1) logg(J 1)}:
which take into account the time interval co, the average accuracy o, and the total number of arms J. Figure
O reports the ITR and Utility measures for the P300 speller simulator example studied in Section 6 We see that STTS achieves the best performance in terms of the ITR and the utility mcasure.
E Additional P300 simulator experiment
In Section D we have generated the target set of words that a user wishes to type using GPT-3. Tn this soction, we consider another scenario of using some chosen sentences. Specifically, we choose Sentence 1,
Prompt
2
=1
OgEG =1
O 2.5
D 2.5
1.5
VTTS
Random
1.5
-VTTS
-Random
1.5
-VITS Random
VVTTS -Random
1.0
utility
1.0
QC 1.0
utility
1.0
0.5
0.5
0.5
0.0
0.0
0.0
50
100
150
300 number of steps
150
100
150
300 number steps
150
number of steps
number of steps
Prompt
g
LEE 1
C = 2.5
E = 2.5
STTS
-STTS -VTTS - -BBTS
-STTS -VTTS BBTS
-STTS -VTTS -BSTS
VTTS BBTS
1.5
1.5
1.5
1.5
1.0
utility
1.0
utility
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
50
100
150
50
100
150
0
50
100
150
0
100
150
number of steps
number of steps
number of steps
number of steps
Figure 6: The information transfer rate (TTR) and the utility measure for the fixed-budget setting using the P300 speller simulator and the GPT-generatod set of words. Two prompts are used. A larger P indicates a larger noise level in the simulated EEG signals.
18

---

Published in Transactions on Machine Learning Research (08/2024)
Table 3: The total number of steps, i.e. the stimulus flashes, for the fxed-confidence setting using the P300 speller simulator and the chosen sentences. Two sentences used, one from benchmark phrase set, and
the other from news article. A larger केEG indicates larger noise level in the simulated EEG signals.
Sentence
EEG
Method
total steps (std)
Sentence
EEG
Method
total steps (std)
STTS
368.71 (69.66)
2
STTS
443.05 (S6.39)
VTTS
623.27 (132.1)
VTTS
1081.42 (190.8)
Random
3071.16 (609.9)
Random
5055.45 (711.3)
BR
1148.36 (77.54)
BR
1918.71 (99.80)
BBTS
623.81 (112.8)
BBTS
1006.45 (154.4)
2.5
STTS
596.58 (101.9)
2.5
STTS
830.07 (116.7)
VTTS
872.5 (136.1)
VITS
1668.23 (193.1)
Random
5750.19
(729.8)
Random
9930.46 (809.5)
BR
1879.16
(174.9)
BR
3207 29 (220.9)
BETS
749.81 (143.9)
BBTS
1286.29 (208.2)
"Rent is paid at the beginning of the month. " with M 9 words, from benchmark phrase set MMcCKenzee & Soukoreff 2003). We choose Sentence 2, "It substantially raises the risk of discoses including cancer, heart disease and diabeles." with = 15 words and punctuation marks, from recent. news article (Wong. 2024) Note that this news article was published in April, 2024, and thus is not in the GPT-2's training data which is up to October, 2019 only. Similarly as before, we use GPT-2 (Radford et al. 2019) obtain the prior distribution. However, for the very first word of sentence, we provide no information all to GPT-2 for Sentence and provide the immediately preceding sentence, "The health harms of smoking tobacco have been established for decudes -' to GPT-2 for Sentence 2. We again conduct experiments for both the fixed-cofiidnce setting and the fixed-budger setting.
For the fixed-confidence setting, Table g reports the total number of steps, or flashes, whereas the 0-1 accuracy and the average accuracy for methods are above 0.9. We again see that, facilitated by the LLM-
Sentence
EEE
GEEC = 2.5
EEC
FEEC 2.5
average accuracy
0.75
1.00
8N Aierrage eccuracy
0.75
1.00
0-1 accuracy
0.75
1.00
BBTS Randomm -VTTS
eccuracy
1.00
0.75
-Random -VTTS
-BBTS
0.50
0.50
0.50
-andom
-Random -ST1S-
0.25
-STSS- Oracle
0.00
150
150
number steps
number steps
number steps
number of steps
Sentence 2
OpFC =1
PFR = 2.5
OFFC
OFFc = 2.5
average accurac)
1.00
000000 agg accuracy
1.00
1.00
BPTS Random
1.00
-BTTS -Randor -VITS
0.75
0.75
accuracy
0.
-VTTS
accurecy
0.50
0.50
0.50
0.25
-BBTS -STTS-Oracle
0.25
BBTS 1S-rrrd
0.00
100 number steps
150
number of steps
number of steps
number of steps
Figure The average accuracy and the 0-1 accuracy for the fixed-budget setting using the P300 speller simulator and the chosen sentences. Two sentences are used, one from a benchmark phrase set, and the other from news article. A larger oera indicates a larger noise level in the simulated EEG signals.
19

---

Published in Transactions on Machine Learning Research (08/2024)
Sentence
EEG
-1
6EG -1
GEEG 2.55
EEB - 2255
-BATS -Ranoom -STSS-Orale
-BATS -Random
-BRTS -Random -STSS-Orae -VITS
-BETS -Random -VTTS
1.5
1.5
-STTS-Oracle -VTTS
1.5
2.5
-VTTS
utility
utility
1.0
1.0
1.0
0.5
0.5
0.5
0.0
0.0
0.0 0
0.0
50
100
150
0
50
100
150
50 number of steps
100
150
0
50
100
150
number of steps
number of steps
number of steps
Sentence 2
1
G 2.5
OEE 2.5
BGTS STTS Oracke -VTS
BBTS TS STTS Oracle -VTTS
90 -STTS Oracie -VITS
BBTS -STTS Oracle -VTTS
1.5
1.5
1.5
ITPP
1.0
utility
1.0
X 1.0
utility
2.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
150
150
150
number of steps
number of steps
number steps
number steps
Figure 8: The information transfer rate (TTR) and the utility measure for the fixed-budget setting using the P300 speller simulator and the chosen sentences. Two sentences are used, one from a benchmark phrase set, and the other from a news article. A larger LèB indicates larger noise level in the simulated EEG signals.
informed prior, STTS achieves the smallest number of steps, while maintaining about the same accuracy as other methods. It manages to reduce the total number of flashes by 25% to 60%.
For the fixed-budget setting, Figure / reports both the 0-1 accuracy and the average accuracy. We see that STTS achieves the highest accuracy compared to the alternative solutions. Figure the corresponding computational complexity ovaluation measures. Again, STTS outperforms other methods in terms of the ITR. and the utility measure.
These results agree with those for the P300 speller simulator example studied in Section and Appendix with the GPT-generated set of words.
20


Reviews:
[{"review_id": "TN92u76Awr", "reviewer": "Reviewer_5hRY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths \n- The problem seems motivated by a concrete application that is\n  relevant.\n- Numerical results seem to indicate that the solution performs well. \n\n# Weaknesses \nThe theoretical formulation of the problem is not clear to me: I did\nnot understand the relationship between the exposed problem in section\n2 and the application to the P300 speller. For instance:\n- what do M, m and j correspond to?\n- what is an arm?\n- why is the noise Gaussian?\n- what is the feedback? and who provides the feedback?\n- why is the reward as specified in the last equation of section 2.2? \n- It seems to me that the prior plays an important role... But what is\n  the signal that we observe before taking a decision (EEG or EDCoG) ?\n  Why is it not in the model?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes to use bandit algorithms to improve the\nperformance of a brain-computer interface system, called \"P300\nspeller\". The proposed algorithm tries to predict what will be the\nnext word that the user wants to output.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The model should be clarified and its relationship with the title and introduction should be precised.", "broader_impact_concerns": "There is no impact statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "RRjAQuXAtw", "reviewer": "Reviewer_cuzS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The paper focuses on an important and interesting problem, making a clear contribution over previous methods. \n- The combination of multi-armed banded paradigm with the language prior was cleverly done. \n- The experimental evaluation of the proposed algorithm was generally well-done and the use of the P300 simulator and the GPT-3 and GPT-2 models was, I thought, a good choice.  \n- The presence of theoretical analysis of the algorithm is also a strength of the paper. \n\nWeaknesses\n- While the text reads clearly and is generally free from typos - there are some higher level things that could be made more clear.  The first time I read the paper entirely through I was still unclear at the end exactly how the multi-armed bandit (MAB) framework was being for the P300 Speller task; what were the MAB actions, what were the rewards, what was the sequence of tasks, etc.  After looking at some of the work that was cited (specifically Heskebeck et al. 2022 was very helpful) I was able to piece together how everything was working and the problem and approach made sense.  I think that this could be made a lot more clear in the paper.  In the beginning of Section 2.1 the variables and components of the problem are defined, but in an abstract way.  This is fine, except for besides connecting the tasks to words, the individual components of the model (actions and reward vector) are not explicitly connected back to the P300 Speller setting.  For me it took a lot of extra effort and reading the other cited work to connect the dots between MAB and the P300 Speller. I would encourage the authors to make these connections more clear so that the motivating problem and surrounding context can be understood from the beginning without prior knowledge of the P300 speller task. \n- In a similar vein, I was disappointed in the related work section on multi-armed bandits.  It seemed to omit the basics of what a MAB is and why it is important.  The first sentence of the MAB review starts talking about \"best-arm identification in the fixed-confidence setting\".  To a reader who isn't the most familiar with MAB these are potentially foreign concepts.  What is the best-arm identification task?  What does fixed confidence mean?  I would encourage the authors to give a short introduction to the basics the MAB setting, describing what is going on, and then carefully define each related task and setting (best-arm identification, fixed-confidence, fixed-budget, batch arm pulls setting, sample-complexity, etc.)  I think this would help the paper be much more comprehensible and impactful to a wider audience. \n- Some of the notation got a little bit clunky with the actions being subscripts and having their own subscripts (like on page 5, you have $\\mu_{t,a_i,a_j}$)  I wonder if that could be replaced by $\\mu_{t,i,j}$ or something, where $i$ and $j$ are then specific actions.  Then on page 8 when describing the Chernoff stopping rule, $\\mu_{m,t,j_1}$ is used, which doesn't seem to match up with the previous definition.  Sometimes it seemed like the indices $i$ and $j$ were used to directly refer to actions.  I think this could be adjusted to be more consistent. \nOther minor notational issues and questions I had are listed in the following questions:\n\nQuestions\n- In algorithm 1 on page 5 - the \"Pull arm\" step is written as if $A_{t,m}$ is a convex combination of $A_{t,m,1}$ and $A_{t,m,2}$, but the text indicates that $A_{t,m}$ should equal either $A_{t,m,1}$ or $A_{t,m,2}$ with $C_{t,m}$ specifying the probability that the first is selected.  I think this should be re-written to be more clear. \n- Also in algorithm 1 -when is the mean $\\mu_{t,a_i}$ updated, along with the number of pulls $N_{t,a_i}$?  Doesn't this need to happen before the \"if max min $Z \\geq \\gamma$\" statement, since $Z$ uses those values?\n- On page 5, in the text description of the $Z$ terms,  you say that $KL(\\mu_1, \\mu_2)$ is the KL-divergence between two distributions with those means.  It seems that the KL divergence cannot be determined from only the means of two distributions, without additional assumptions about those distributions.  Is there something else going on here?  \n- On page 7 - why does $\\mu_{m,t}$ not have a $j$ or $i$ subscript, but $\\sigma^2_{m,t,j}$ does?  It seems like these should be indexed the same, as they refer to different parts of the same distribution.\n- On page 8 - Do the results for STTS and STTS-Oracle exactly overlap?  As it is, I don't see both results. It looks like only one line is in the figures, but both are included in the figure legend.\n- On page 8 - You state that \"it is impractical to run the number of steps into the thousands\"  How many steps are considered reasonable for this task?  What is the state-of-the-art? \n\nMinor/Typos\n- Page 1 \"instead the brain signals\" could perhaps be \"instead brain signals\"\n- Page 3 \"indenpendently\" should be \"independently\" \n- Page 4 \"We also comment that, SAMP is ...\" I think the comma could be omitted. \n- Page 14 \"recommeded\" should be \"recommended\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new algorithm for problems inspired by the P300 speller, a brain-computer interface that allows people to \"type\" words with only their brains. \nThe authors frame the problem of determining which letter or word is being typed as a multi-armed bandit problem, where the goal is to identify the best arm, which is the letter/arm the person is intending to type.  The key insight is that due to the fact that natural language is being used for communication, existing language models can be used as a prior to help give guidance as to which next letters/words are most likely, given what has already been typed.  The algorithm proposed to address this sequential best-arm identification problem utilizes a top-two Thompson sampling method and can be used either with a confidence or budget termination condition.  An error bound on the algorithm under certain conditions is proven, and the algorithm is experimentally evaluated in a simulated sequential setting, as well as with a P300 simulator, showing in each case improvements over alternative methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Addition of MAB background and description of how the components of the MAB framework align with the components of the P300 Speller task, as discussed above.  (Critical)\n- Some polishing of the notation, at least addressing the questions that I raise above. (Strengthening)", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "w105ckeEM2", "reviewer": "Reviewer_SkCS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n1. The idea of using LLMs as the prior for BCI spellers is interesting and seems to be a useful application of both LLMs and BAI that may have significant real world impact if developed into real products.\n2. Theoretical analysis is provided.\n3. The proposed algorithm is compared against suitable baselines.\n4. There is an attempt to demonstrate real world relevance with the use of the P300 speller simulator (however, please see comments below).\n\n### Weaknesses:\n1. **Inadequate description/justification of experiments**. In the synthetic experiments section, it is written \"We take one sentence as one experiment, and one word in the sentence as one task, with each sentence consisting of M = 20 words.\" There is nothing written on where these sentences come from. Are they generated from a LLM as in the P300 simulator experiment, or from some dataset? Lack of this information hinders understanding and reproducibility. In the P300 experiments section, it is written \"We use GPT-3 to generate M = 20 words, under a given prompt, as the words that the participant wishes to type, which form the optimal arms. We consider two prompts: Prompt 1 “The most popular food in the United States is”, and Prompt 2 “My favorite sport is”.\" There is no justification for why these prompts and why LLM generated sentences instead of real sentences used in BCI experiments, of which there should be plenty if there are public BCI data and data upon which the simulator was built. In fact, the use of GPT-3 generated sentences is problematic as GPT-2 is used as the prior, and it is reasonable to expect that GPT-2's training data is at least a subset of that of GPT-3, and therefore that GPT-2 would be a particularly good prior on GPT-3 generations. This does not inspire confidence that the proposed method leads to significant advantage on the distribution of real sentences that BCI users wish to type.\n2. **Clarity can be improved**. The writing is unclear in some parts. For example, the description of how the P300 speller works in the introduction was not understandable to me as someone encountering this for the first time. I relied on the description in Sec. 4 of \"Brain–Computer Interface Spellers: A Review\" by Rezeika et al. (2018) to understand the mechanism. \n3. **Lack of reproducibility**. In addition to the inadequate experiment description mentioned in point 1, no code is released. The P300 speller simulator is also unavailable to anyone trying to reproduce the results in this study.\n4. **Insignificant contribution to the general BAI literature**. The algorithm is a straightforward application of LLMs as a prior to an existing algorithm, top-two Thompson sampling. The strengths of this paper lie in its application to BCI spellers rather than to the general field.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the use of best arm identification (BAI) by brain-computer interfaces (BCIs), in particular P300 spellers, a type of BCI that selects from a pool of letters/words based on the magnitude of the user's P300 brain responses when each letter/word is highlighted to the user. In this study, each sentence is a task, each word in a sentence is an arm, and the P300 brain responses are the observed rewards. The proposed algorithm uses LLMs as a prior for top-two Thompson sampling. Theoretical results in both the fixed budget setting and the fixed confidence setting to account for the multi-task case is provided. Empirical evaluations of the proposed algorithm are provided in synthetic benchmarks and with a P300 speller simulator built from real world data.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Critical to securing recommendation:\n1. Please completely specify the synthetic experiments and how the sentences are chosen.\n2. In the P300 simulator experiments, either use real sentences used in real world BCI experiments, or justify the choices of prompts and use of GPT-3 generations over real sentences.\n\n### Would strengthen the work:\n1. Release code for reproducibility. Ideally, the P300 simulator could be released as well; however, if this is not possible, the code for the synthetic experiments should at least be available.\n2. Rewrite the introduction and description of P300 spellers so that it is accessible to non-experts.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: There were concerns on the presentation, which were raised by most of reviewers. While the paper is now in a better shape after revision, one reviewer is not satisfied yet, claiming that he/she does not see clearly the relationship between the theoretical model and the practical problem to solve and the model should be better explained. The same thing can happen for many readers who wish to see a real-world application of the best-arm identification but are not familiar with BCI and P300 speller. Thus I would like to suggest the authors to elaborate Fig. 1 such that 
it clearly illustrates how a sequence of best-arm identification is formulated in the context of a P300 speller. Once what is going on becomes clear in the first place, the rest of things will be easily caught up.
Decision: Accept (poster)