Enhancing Preference-based Linear Bandits via Human Response Time
Authors: Shen Li
Yuyang Zhang
Zhaolin Ren
Claire Liang
Na Li
Julie Shah
Venue: NeurIPS 2024 oral (2024)
Keywords: human response time
preference learning
linear bandits
dueling bandits
psychology
economics
Primary area: bandits
TL;DR: Leveraging human response times to accelerate preference learning from binary choices

Abstract: Interactive preference learning systems infer human preferences by presenting queries as pairs of options and collecting binary choices. Although binary choices are simple and widely used, they provide limited information about preference strength. To address this, we leverage human response times, which are inversely related to preference strength, as an additional signal. We propose a computationally efficient method that combines choices and response times to estimate human utility functions, grounded in the EZ diffusion model from psychology. Theoretical and empirical analyses show that for queries with strong preferences, response times complement choices by providing extra information about preference strength, leading to significantly improved utility estimation. We incorporate this estimator into preference-based linear bandits for fixed-budget best-arm identification. Simulations on three real-world datasets demonstrate that using response times significantly accelerates preference learning compared to choice-only approaches. Additional materials, such as code, slides, and talk video, are available at https://shenlirobot.github.io/pages/NeurIPS24.html.

Enhancing Preference-based Linear Bandits via Human Response Time
Shen Lif-
Yuyang Zhang2* Zhaolin Ren Claire Liang' Na Li Julie A. Shah
Massaacussetts Institute of Technology Harvard University {shenli, cy148) @mit. edu, julie___shaaeeeeeee sts.asssshhhssaallsaaaaaaaaaaaae mitai.iii.......mm. mit. edu (yuyangzhang, zhaol @g harvard. edu, mali@seas. harvard.edu
Abstract
Interactive preference learning systems infer human preferences by presenting queries as pairs of options and collecting binary choices. Although binary choices are simple and widely used, they provide limited information about preference strength. To address this, we leverage human response times, which inversely related to preference strength, as an additional signal. We propose a computa- tionally efficient method that combines choices and response times estimate human utility functions, grounded in the EZ diffusion model from psychology. Theoretical and empirical analyses show that for queries with strong preferences, response times complement choices by providing extra information about prefer- ence strength, leading to significantly improved utility estimation. We incorporate this estimator into preference-ber fication. Simulations on three real-world datasets demonstrate that using response times significantly accelerates preference learning compared to choice-only ap- proaches. Additional materials, such as code, slides, and talk video, are available at htttps::/shenlirrobee wwt.gg.ttoooooooo... wtt.:huw...o/page//eeeeeeee IPS24 html
linear bandits for fixed-budget best-arm identi-
Introduction
Interactive preference learning from human binary choices is widely used in recommender systems 9
21
59 This 56], assistive robots [54 and fine-tuning large language models 43
process is often framed as a preference-based bandit problem 7 [1] where the system repeatedly presents queries as pairs of options, the human selects a preferred option, and the system infers preferences from these choices. Binary choices are popular because they are easy to implement and impose low cognitive load on users [37 72 However, while binary choices reveal preferences, they provide little information about preference strength (77). To address this, researchers have incorporated additional explicit human feedback, such as ratings [50] 58), labels [74), and slider bars [5] 72). but these approaches often complicate interfaces and increase cognitive demands [36 37
In this paper, we propose leveraging implicit human feedback, specifically response times, provide additional insights into preference strength. Unlike explicit feedback, response time is unobtrusive and effortless measure [7], offering valuable information that complements binary choices 16)
For instance, consider an online retailer that repeatedly presents users with a binary query, whether to purchase or skip a recommended product [35]. Since most users skip products most of the time [33. the probability of skipping becomes nearly for most items. This lack of variation in choices makes it difficult assess how much a user likes dislikes any specific product, limiting the system's ability to accurately infer their preferences. Response time can help overcome this limitation. Psychological research shows an inverse relationship between response time and preference strength [I7]: users who strongly prefer to skip product tend to do quickly, while longer response times can indicate
First two authors have equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

weaker preferences. Thus, even when choices appear similar, response time can uncover subtle differences in preference strength, helping to accelerate preference learning.
Leveraging response times for preference learning presents notable challenges. Psychological research has extensively studied the relationship between human choices and response times [97 using complex models like Drift-Diffusion Models [51] and Race Models [12 66]. While these models align with both behavioral and neurobiological evidence [70], they rely on computationally intensive methods, such as hierarchical Bayesian inference [Z]] and maximum likelihood estimation (MLE) [52] estimate the underlying human utility functions from both human choices and response times, making them impractical for real-time interactive systems. Although faster estimators exist [8] 30]67] (8), they typically estimate the utility functions for single pair of options without aggregating data across multiple pairs. This limits their ability to leverage structures like linear utility
functions, which are widely adopted both in preference learning with large option spaces [21 24
54 [66]
and in cognitive models for human multi- multi-attribute decision-making 226 64 76
To address these challenges, we propose computationally efficient method for estimating linear human utility functions from both choices and response times, grounded in the difference-based EZ diffusion model 8 67]. Our method leverages response times to transform binary choices into richer continuous signals, framing utility estimation as a linear regression problem that aggregates data across multiple pairs of options. We compare our estimator to traditional logistic regression methods that rely solely on choices 311. For queries with strong preferences, our theoretical and empirical analyses show that response times complement choices by providing additional information about preference strength. This significantly improves utility estimation compared to using choices alone. For queries with weak preferences, response times add little value but do not degrade performance. In summary, response times complement choices, particularly for queries with strong preferences.
Our sinear-regression-basee estimator integrates seamlessly into algorithms for preference-basee bandits with linear human utility functions 31), enabling interactive learning systems to leverage response times for faster learning. We specifically integrated our estimator into the Generalized Successive Elimination algorithm (3] for fixed -xdget best-arm identification [29 34), Simulations
using three real-world datasets [6 39 57] consistently show that incorporating response times significantly reduces identification errors, compared to traditional methods that rely solely on choices. To the best of our knowledge, this the first work to integrate response times into bandits (and RI.).
Section introouuess the preference- based linear bandit problem and the difference- model. Section 3 presents our utility estimator, incorporating both choices and response times, and offers a theoretical comparison to the choice-only estimator, Section iintegrates both estimators into the Generalized Successive Elimination algorithm. Section 5 presents empirical results for estimation and bandit learning. Section 6 discusses the limitations of our approach. Appendix B reviews response time models, parameter estimation techniques, and their connection to preference-based RL.
EZ diffusion
Nomenclature: We use [n]] to denote the set {1...., n). For a scalar random variable x. the expectation and variance are denoted by E [zx] and V [x], respectively. The function (z)) denotes the sign of x.
2 Problem setting and preliminaries
Preference-based bandits with a linear utility function. The learner is given finite set of options (or "arms"), each represented by a feature vector in C Rdd, and finite set of binary queries, where each query is the difference between two arms, denoted by X C Rd. For instance, if the learner can query any pair of arms, the query space X' = {2 - z': 2, z' E Z). In the online retailer example Z ). where represents purchasing product and žakip represents skipping (often set as 0). For each arm 2 E Z, the human utility is assumed to be linear in the feature space, defined as Ug := z T 0", where 0 E IR represents the human's 's preference parameters. For any query 2 E X, the utility difference is then defined as u, := x 0*.
from section [ the query space is X' = {= Zskip
Given a query x = 21 - 22 E XX we model human choices and response times using the difference- based Di-Diffusion Model (dEZDM) 88 67], integrated with our linear utility structure. (See appendix B. for comparison with other models.) This model interprets human decision maainng as a stochastic process in which evidence accumulates over time to compare two options. As shown in fig. Tal after receiving a query x, the human first spends fixed amount of non-decision time, denoted by tnnnde 0, to perceive and encode the query. Then, evidence E, accumulates over

---

time following Brownian motion with drift x 8" and two symmetric absorbing barriers, > 0 and -a. Specifically, at time énonde: + T where 5 2 the evidence is E.,- x 0 T + B(T). where B(r) ~ (0,,T) is standard Brownian motion. This process continues until the evidence reaches either the upper barrier a or lower barrier- -n, at which point a decision made. The random stopping time, l == min (r > 0: E E (a, -a }. represents the decision time. If Eg,t, = the human chooses 21; if Ex,t_ = - a, they choose 22. The choice is represented by the random variable Cz. where C2 = 1 if is chosen, and -1 if 22 is chosen. The total response time, a is the sum of the non-decision time and the decision time: ÁRT.. nondes + lz. The choice probability, expected choice, choice variance, and expected decision time are given as follows [88 eq. (A.16) and (7.17)):
1
Vo E X: F(ee- = 1] 1 exp( 2-2x T 0+)²
IE [cx] tanh(ar 00))
(1)
Lanh(ax T 0*) if x 0" +0 if x 0 = 0
V 1 tanh (ax 0*), E [tal
This choice probability matches that of the Bradley and Terry [0] model. If the learner relies solely on choices, then our bandit problem reduces to the transductive linear logistic bandit problem [31].
Figures lb and Ic illustrate the roles of the parameters x T and a. First, the absolute drift (or the absolute utilityy difference), |x: 0*I, reflects the human's preference strength for the query æ. Larger values indicate stronger preferences, leading to faster decisions and more consistent choices. Smaller values suggest weaker preferences, resulting in slower decisions and less consistent choices. Second, the barrier a represents the human's 's conservativeness in ceriiiionmmaking [40]. A more conservative human (higher a) requires more evidence to decide, resulting in slower but more consistent choices. In contrast, less conservative human (lower a) decides faster but makes less consistent choices.
E [t.] + Fr.
E [c + d
Evidence Ex
E [e.] + Orr
Efc] + C
gondee
0.0
0.1
0.3
0.4
0.5
0.6
Time (sec)
0
0
(a)
(b) = 0.8
(c) a = 1.8
Figure I: (a) depicts the human decision making process for binary query X, where the human selects between two arms. The human first spends a fixed non-decision time fnonde encoding the query. Then, the human's 's evidence accumulates according When the evidence reaches the upper barrier a or lower barrier -a, the human makes a choice, denoted by cu
Brownian motion with drift x 0*
ca 1,, respectively. The random stopping time of the accumulation process is the decision time tu. and the total response time is fRT,. = fmnnde + fz. (b) and (c) plot the expected choice E[cz] and the expected decision time E[tz] with shaded regions representing one standard deviation, plotted as functions of the utility difference x O for two barrier values a.
We adopt the common assumption that nondee is constant across all queries for a given human 16 76 and further assume that montte is known to the learner. This assumption enables the learner to perfectly recover fr from the observed fRT,Z- In section 5.2 we empirically show that even when foondec is unknown, its impact on the performance of our method that relies on decision times is negligible.
Learning objective: Best-arm identification with fixed budget. We focus on the fixed-budget best-arm identification problem 22 34
The learner is provided with a total interaction time budget B> > 0, an arm space Z, query space X, and non-decision time moniee.. Both the human's 's preference vector O* and the decision barrier are unknown. In each episode & E N. the learner selects query x, X. receives human feedback (Ca,, te generated by the dEZDM, and consumes tRT. time. When the cumulative interaction time exceeds the budget B at some episode S, i.c., ES IRT, > B, the learner must stop and recommend an arm 2 E Z. The goal is to recommend the unique best arm 2" == arg m 2 0*, minimizing the error probability IP [2 * 2*).
3

---

To address this problem, we adopt the Generalized Successive Elimination (GSE) algorithm 33,75 75 GSE divides the total budget B into multiple phases. In each phase, strategically samples queries until the phase's budget is exhausted, collecting both human choices and decision times. It then estimates the preference vector 0* and eliminates arms with low estimated utilities, Decision times play a key role in the estimation step by providing complementary information about preference strength, which can enable more accurate estimation of l than choices alone. Next, in section 3 we introduce a novel estimator that combines decision times and choices to estimate 0*. Then, in we discuss how this estimator is integrated into GSE to improve preference learning.
section 4
3 Utility estimation
This section addresses the problem of estimating human preference 8 from fixed dataset, denoted by x2, Ca,ez, fa, (E(en.. Here, Asamplc denotes the set of queries in the dataset, f2 denotes the number of samples for each query sample and 8 denotes the episode when x is sampled for the i-th time. Samples from the same query are i.i..., while samples from different queries are independent. Section 3.1 introduces new estimator, the "choice-decisiontine uses both choices and decision times, in contrast to the commonly used "choice-only estimator" that only uses choices [3] 31. Sections 3.22 and 3.3 theoretically compares these estimators, analyzing both asymptotic and non non-asymptotic performance and highlighting the advantages of incorporating decision times. Section 5.1 presents empirical results that validate our theoretical insights.
estimator," " which
3.1 Choice-decision-tiie estimator and choice-only estimator
The choice- phoice-decision--e decision-time time estimator is based on the following relationship between human utilities, choices, and decision times, derived from eq. (
0
E [2] E [tz]
Vz E X:
x
(2)
a
Intuitively, when a human provides consistent choices (i.e., large [B(cx] and makes decisions quickly (i.e., small Ett,)). it implies strong preference (i.e., large [x 0r). This relationship formulates the estimation 8" as a linear regression problem. Accordingly, the choice-decision time estimator calculates the empirical means of both choices and decision times, aggregates the ratios across all sampled queries, and applies ordinary least squares (OLS) to estimate 8'/a. Since the ranking of arm utilities based on 0* /o is identical to that based 0*, estimating /a sufficient for identifying the best arm. Formally, this estimate 0* /a, denoted by OCH.DT. is given by:
ØCHLT ==
Σ BE &
Th. Wa.
ng. x
Ei=1 Cz.az.
(3)
In contrast, the choice-only estimator is based on eq. (.. which shows that for each query E X, the random variable (c, + 1)/2 follows Bernoulli distribution with mean 1/[1 exp(-z" 220 }] Similar to the seniceedecssonnttin estimator, the parameter 2a does not impact the ranking of arms, so estimating 2 is sufficient for best-arm identification. This estimation is formulated as logistic
regression problem 3 31, with MLE providing the following estimate of 2a0*, denoted by OCH:
OCH := arg max
log p(Ca,ee x TT),
DERd
I.E 1=1
where ((y) 1/(1 -x1++)x((-)) is the standard logistic function. While this MLE lacks closed-form
solution, it can be efficiently solved using optimization methods like Newton's 's algorithm 25 44
3.2 Asymptotic normality of the two estimators
The choice-decision estimator from eq. satisfies the following asymptotic normality result:

---

Theorem 3.1 (Asymptotic normality of (CHLDT). Given a fixed i.i.d. dataset {z, Cz.sx, t2,0x, a jilml for each I. E Ksampie where ExeXamt xx > O, and assuming that the datasets for different I Xsample are independent, then, for any vector y E RR, as n + oc, the following holds:
Vny" (OCH.DTM -0 00 - N0.
Here, the asymptotic variance depends a problem-specifee constant, S², with upper bounded:
2² Ilvlll Eoexmopt
mmin. 2 E|t,-]] xxx
The proof is provided in appendix C.2
The asymptotic variance upper bound shows that all sampled queries are weighted by a common factor minn'eXXame E [(z/], which is the smallest expected decision time among all the sampled queries sample This weight represents the amount of information provided by each query's s choices and decision times for utility estimation. A larger weight indicates that all queries Xuumple provides more information, leading lower variance and better estimates.
In contrast, the choice-only estimator from eq. (4) has the following asymptotic normality result, as derived from Fahrmeir and Kaufmann
2 corollary 1]:
Theorem 3.2 (Asymptotic normality of OCH). Given a fixed i...d. dataset {ar, Cr.s.. ba ii for
each x E Xsamlee, where ExEXimnu xr O, and assuming that the datasets for different Xsample are independent, then, for any vector E Rd. as + oc, the following holds:
Vny (Den. - 200-) 2 N (0.4u² 1ull
(ree anpt [a² Vl==ll=xx
This asymptotic variance shows that each sampled query X E Xaample is weighted by its own factor a² V [cz]. representing the amount of information the query's ' choices contribute to utility estimation. A larger weight indicates that the query contributes more information, leading to better estimates.
The weights in both theorems highlight the different contributions of choices and decision times to utility estimation. In the choice-only estimator (theorem 3.2). each query is weighted by a² V [Ca], which depends on the utility difference x 6* for fixed barrier a. As shown by the gray curves in fig. 2a this weight quickly decays to zero as preferences become stronger (i.e., | 0- increases). This indicates that choices from queries with strong preferences provide little information. Intuitively, when preferences are strong, humans consistently select the same option, making hard distinguish whether their preference is moderately or very strong. As a result, choices from such queries contribute minimally to utility estimation. This intuition aligns with the online retailer example in section [
For the choice-decision-tine estimator (theorem 3.1 queries are weighted by m EE [tzr) which depends on both Xsample and [t..]. To better understand this weight, we first plot E [t.] without the "min' operator the orange curves in fig. 2a Comparing the orange and gray curves shows that EE [tz]] is generally larger than the choice-only weight, a V [cz]. ] The actual weight the seriicedeciiion-tiiin
estimator, which is the minimum expected decision time across sampled queries, is less than or equal to the orange curve but is likely still higher than the choice-only weight, especially for queries with strong preferences. This suggests that when preferences are strong, decision times complement choices by capturing preference sirength, leading to improved estimation.
When queries have weak preferences, the only weight. However, since the choice-decision time weight represents only an upper bound on the asymptotic variance (theorem 3. no definitive conclusions can be drawn from the theory alone. Empirically, as shown in section 5.1 decision times add little value but do not degrade performance.
time weight may be lower than the choice-
As the barrier increases, the choice-decision-time weight rises. In contrast, the choice-only weight increases for queries with weak preferences, but this increase is concentrated in narrower region, with weights decreasing elsewhere. Intuitively, a higher barrier reflects greater conservativeness in human decision-makiin leading longer decision times and more consistent choices (fig. [T. As result, more queries exhibit strong preferences, making choices from these queries less informative.
5

---

3.0
B 1.8
0.7
mon CH DT a =1.8
E [t)
a00.
=0.8
0.6
noi-toyn MCEDT a =0,8
2.0
V [c]
1.8
0.5
notetdyll "CC a 118
1.5
V [c,]
=0.8
0.4
MCE =0.8
0.3
0.2
0.5
0.1
0.0
-6
21' 8"
8
(a) [t,] and a² V [cx] in asymptotic variances
(b) Weights in non-asymptotic concentration bounds
Figure 2: This figure illustrates key terms from our theoretical analyses, highlighting the different contributions of choices and decision times to utility estimation. These terms are functions of the utility difference x² f and are plotted for two barrier values, (a) compares the weights E [t. and a² [cz] in the asymptotic variances for the choice-decision-tine and the choice-only estimator (gray, theorem 3.2). respectively. This comparison shows that decision times complement choices, particularly for queries with strong preferences. (b) compares the weights in the non-asymptotic concentration bounds (theorems 3.3 anaan 3.4), showing similar trends, though these weights may not be optimal due to proof techniques.
estimator (orange, theorem 3.1
3.3 Non-asymptotic concentration of the two estimators for utility difference estimation
In this section, we focus on the simpler problem of estimating the utility difference for a single query, without aggregating data from multiple queries. Comparing the non-asymptotic concentration bounds of both estimators, in this case, provides insights similar to those discussed in section 3.2 Extending this non-asymptotic analysis to the full estimation of the preference vector 0* is left for future work.
Given a query X, the task is to estimate the utility difference u, x T using the fixed i.i.d. dataset {(Cr,ez. tt,ee.)) (eeee.))) Applying the choice-decision--ie time estimator from eq. (3), we get the following estimate (for details, see appendix C.3.I). which estimates u rather than Ugg
>1El Co.so.t
T CHLDT
Σ tz,er..
In contrast, applying the choice-only estimator from eq. 4 we get the following estimate (for details, see appendix C.3.2). which estimates 2au, rather than ug:
Cr. +
T == 1
2
where (Cr.9.. + 1)/2 the binary choice coded as or 1, and μ (pp(p) = log (p/(1-1)))) - p)) is the logit function (inverse of introduced in eq.
Notably, the choice-only estimator in eq. (6) aligns with the EZ-diffusion model's drift estimator (67
eq. (5)]. Moreover, the estimators in Xiang Chiong et al. [73] eq. (6)] and Berlinghieri et al. 8
eq. (7)] combine elements of both estimators from eqs. (5) and (6). In section 5.2 we demonstrate
that both estimators from Wagenmakers et al. [67 eq. (5)] and Xiang Chiong et al. [73 eq. (6)) are
outperformed by our proposed estimator eq. for the full bandit problem.
Assuming the utility difference ur + O. the choice-decision-tim estimator in eq. 5 satisfies the following non-asymptotic concentration bound, proven in appendix C.3.I
Theorem 3.3 aNon-asymptotic concentration of (..CH. For each query x E X with uy + O, given fixed i.i.d. dataset { (Cr,,e.s (x, fefma for any > satisfying s min (luzl/(VZa), (1+ 2 aluzl I/ I/E [tul]. the following holds:
((0,.CH.Dr - Ug
> E) < 4exp (-
non-asym
(x (0))) [e [e.a]²).
non-asym where CCDD
(x = E [tx))) [(2 2 a).

---

In contrast, the choice-only estimator in eq. adapted from Jun et al. [I] theorem 5
(6) has the following non-asymptotic concentration result,
Theorem 3.4 (Non-asymptotic concentration of (2, For each query X, given fixed iid. dataset ( for any positive < 0.3, if 2 1/j((2aux)
max(3² log(6e)/e², 64 log(3)/ - -e² /0.3"), the following holds:
IP P(ūZz,C 2au e) 6exp (- [men
non-asym (=)0 n2 le/((a))²)
where MCH
non-asym
(x (T) = a / [cr) 2.4
The weights MCHDDT
m (.) and MCH non-asym (-) from theorems 3.3 and 3.4 respectively, are functions of the utility difference x 8" for fixed barrier a. These weights determine how quickly estimation errors decay as the dataset size n, grows, with larger weights indicating faster emoor reduction. While these weights may not be optimal due to proof techniques, they highlight the distinct contributions of choices and decision times, consistent with our asymptotic analysis in section 33.2 Figure 2b estimator (orange, MCHLDT
compares the weights for the choice-decision-tinn
asy (-)) and the choice-
only estimator (gray, "ICH (( (-)). For strong preferences, the choice-only weights quickly decay to zero, while the prooiceddecsionn-tiiee weights remain relatively large. This supports our key insight that decision times complement choices and improve estimation for queries with strong preferences.
In summary, both asymptotic (section 3.2) and non-asymptotic (section 3.3 analyses demonstrate that the choice-decision-iing time estimator extracts more information from queries with strong preferences. This finding aligns with prior empirical work [66] and further supported by our results section [5.]]
In fixed- buddet best-arm identification, our mnoicc-deciiioon-iie estimator's ' ability to extract more information from queries with strong preferences is especially valuable. Bandit learners, such as GSE B1, strategically sample queries, update estimates of 6", and eliminate power-utility arms. With the choice-only estimator, learners struggle extract information from queries with strong preferences. To resolve this, one approach is to selectively sample queries with weak preferences, but this has two drawbacks. First, queries with weak preferences take longer to answer (i.e., require more resources), potentially lowering the 'bang per buck' (information per resource) [4. Second, since 6* unknown in advance, learners cannot reliably target queries with weak preferences. In contrast, with our seniceddcisiiontime estimator, learners leverage decision times to gain more information from queries with strong preferences, improving bandit learning performance. We integrate both estimators into bandit learning in section 4 and evaluate their performance in section
4 Interactive learning algorithm
We introduce the Generalized Successive Elimination (GSE) algorithm 13 75 for fixed-budget
best-arm identification in preference-based linear bandits, and outline the key options for each GSE component, which we empirically compare in section 5
The pseudo-code for GSE is shown in algorithm II The algorithm uses a hyperparameter 1 to control the number of phases, the budget per phase, and the number of arms eliminated in each phase. GSE divides the total budget B evenly across phases and reserves a buffer, sized by another hyperparameter Buuff, prevent overspending in any phase (line 4p. In each phase, GSE computes an experimental design X, a probability distribution over the query space, to guide query sampling. We consider two designs: the transductive design [24], Amans (line 5), and the weak-preference design (31), Aweak (line (6.. Both designs minimize the worst-case variance of utility differences between surviving arms. The transductive design weights all queries equally, whereas the weak- preference design prioritizes queries with weak preferences to counter the choice-only estimator's difficulty in extracting information from queries with strong preferences (section B Since 6* is unknown, the weak-preferenee design identifies queries with weak preferences based on the previous phase's 's estimate θOH. Then, GSE samples queries based on the design (line 7 and, after exhausting the phase's budget, estimates 0* using either the choice-decision-time estimator 0CH.DT (line 8 the
choice-only estimator Oeh (line 9). It then eliminates arms with low estimated utilities (line 10) This process repeats until only arm remains, which GSE recommends as the best arm (line 12
In Jun al.
31 theorem 5], we let
w; 1 and tell 1.
7

---

The key difference between algorithm I lnd previous GSE algorithms 13 75 is that our setting involves queries with random response times, unknown to the learner. Previous work assumes fixed resource consumption per query and uses deterministic rounding methods 3 24 to pre-allocate queries. This approach does not handle random resource usage. Instead, we adopt a random sampling procedure [13] [6] in line to allocate queries based on the design. Random resource usage also requires tuning the elimination parameter 77, to balance data collection and arm climination, and the buffer size Braff to prevent overspending. In our empirical study (section 5.2). we manually tune both parameters. Further theoretical analysis is needed to better understand and optimize them.
Algorithm 1 Generalized Successive Elimination (GSE)
1: Input: Arm space 2, query space X', non-decision time (nndde. and total budget B,
2: Hyperparameters: Elimination parameter 7) and buffer size Bratt.
3: Initialization: 21- <- 2.
4: for each phase 1...., K = log,, [2] with the budget Bx = B/K Boutt do
5: Design 1. 0g = A f- arg minxeale ma || z11? (Enex T2
6: Design dR Awenk,k t- arg min xea (al maX x112 " (Eeex M(x Pe-1) dearT)
7: Sample queries x, 0 and stop at Jn if Σ j=1 txT, S B& and Ej= tRT e 7 Bk.
8: Estimate 1. 0g OCH.DT,E apply eq. 33 to all the Js samples.
9: Estimate 2. 0g = f < apply eq. (4 to all the Jj samples.
10: Update Z++1 f Top- [2xl arms Zz. ranked by the estimated utility = -00g.
11: end for
12: Output: the single one 2 E 2k+1-
Empirical results
This section empirically compares the GSE variations introduced in section Transductive design with
(1) (Auans ²CHDDT):
estimator. (2) (Aurass Pcu): Transductive design with choice-only estimator. (3) (Aweak, 0cn): Weak-preference design with choice-only estimator.
5.1 Estimation performance on synthetic data
We evaluate the estimation performance of the GSE variations the "sphere" synthetic problem,
standard linear bandit problem in the literature (0 42 61] Details are provided in appendix [.1
Estimation performance, as discussed in section 3 depends on the utility difference x. 0* and the barrier a. We vary a over a range of values commonly used in psychology [16 71]. To examine how preference strength impacts estimation, utility difference x T 8" to cz x 8" Small cz values correspond to problems with weak preferences, while large values correspond strong preferences. For each (cz, a) pair, the system generates 100 random problem instances and runs 100 repeated simulations per instance. In each simulation, the
scale each arm Z to ez effectively scaling each
GSE variations sample 50 queries, ignoring the response time budget, and compute 0. Performance is evaluated by P(arg max = =²), which reflects the best-arm identification goal defined in section 2 To isolate the effect of estimation, we allow Aweak access to the true 8*, enabling it to perfectly compute the terms ji(x' 0*) used in line algorithm!!
As shown in fig. 3a fixing the barrier a and examining the vertical line, as c2 increases and preferences become stronger, the performance of the choice-only estimator with the transductive design first improves and then declines. The initial improvement arises because larger eg increases utility differences between the best arm and others, theoretically simplifying best-arm identification. The subsequent decline, highlighted by the dark curved band, supports our insight from section 3 that choices from queries with strong preferences provide limited information. Fixing eg and examining the horizontal line, performance first improves and then declines. This trend aligns with fig. 2a and section
3.2 where higher barriers increase the choice-only weights for queries with weak

---

1.0
Amn scaling factor 02
Anu scoling Jastor 02
Amu sealing fector 02
0.6
0.2
DV
ST.
11
81
12
S
ST
DO
97
Barrier
Barrier
Barrier
(a) (Auans fCH)
(Aweaks bcu)
(Amas OCHLTI)
Figure 3: Three heatmaps show estimation error probabilities, P/arg max & 2*}. 1 for three GSE variations, shown functions of the arm scaling factor ez and barrier a. Darker colors indicate better estimation. (a) The choice-only estimator feu with the transductive design Amans struggles as cz increases (i.e., preferences become stronger), highlighting that choices from queries with strong preferences provide limited information. (b) The weak-preference design Aweak improves (a) by sampling queries with weak preferences but assumes perfect knowledge of 0" and equal resource consumption across queries. (c) The choice-decision-time estimator OCHLDT with Arans outperforms both choice-only methods in (a) and (b), showing that decision times complement choices and improve estimation, especially for strong preferences.
preferences, initially improving performance. However, grows, fewer queries exhibit increased weights, while most queries' weights decrease, leading to the later performance drop.
In Figure 3b] for moderate cz, the choice-only estimator with the weak-preference design outperforms the transductive design (fig. [aa), demonstrating that focusing on queries with weak preferences improves estimation. However, as Cz becomes too large, performance declines because many Úix" 0*) in 6 of algorithm approach zero, preventing informative queries from being sampled. This advantage of the weak-preference design assumes perfect knowledge of (0 and equal resource consumption across queries. In practice, where 0* is unknown and seak-preference queries require longer response times, the transductive design performs better, as shown in section 5.2
Figure 3c shows that the poooccedecision-tine estimator consistently outperforms the choice-only estimators under both the transductive and weak preference designs, particularly for strong prefer- ences. This suggests that for queries with strong preferences, decision times complement choices and improve estimation, confirming our theoretical insights from section [ while for queries with weak preferences, decision times add little value but do not degrade performance. The performance also improves with higher barrier supporting the insights conveyed by fig. 2a and section 3.2
5.2 Fridet best-arm identification performance on real datasets
This section compares the bandit performance of six GSE variations. The first three are as previously defined at the beginning of section ( @CHDT)) (Auans: bcH), and (Aweaks BcH).
The 4th GSE variation, (Aurams (CU,RT), evaluates the performance of the phoicc-deciision-iie estima- tor when the non-decision time facedoe is unknown. The estimator, θCH.RI, is identical to the original choice-decision citeissio--imeeeeee estimator from Eq. (3). but with response times used in place of decision times.
The 5th GSE variation, (Arrans O.H.iogi), ). is based on Wagenmakers et 67 eq. (5)), which states that xT (2a0r) μ (Pic, 1)), where (p) log (p/ (1 (1-11) p)). By incorporating our linear utility structure, we obtain the following choice-onle estimator OCH.oogui
OCHLogii
nr .T
Σ X
The x 1 (ē.).
where C. = ny E 1 (Ca,ont + is the empirical mean of the binary choices coded as 0 or 1.

---

(Aeaan Beasel
Ohoosa Rea!
(Arca Bea)
Aunan Baiar))
1.0
1.0
1.0
Eror probutaiity PB =1
0.8
0.8-
Emor probubilitty P 4
0.8
Ero probubiiity P
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0-
0.0
0.0-
5000
1000
100
300
2000
300
Budget (800)
Budget (see)
Budget (s00)
(a) Food-risk dataset
57
(b) Snack dataset
16
(c) Snack dataset
3D
Figure This figure shows violin plots (with overlaid box plots) for datasets (a), (b), and (c), showing the distribution of best-arm identification error probabilities, PP [2 * 2"), for all bandit instances across six GSE variations and budgets. The box plots follow the convention the matplotlib Python package For each GSE variation and budget, the horizontal line in the middle of the box represents the median of the error probabilities across all bandit instances. Each error probability is averaged over 300 repeated simulations under different random seeds. The box's 's upper and lower borders represent the third and first quartiles, respectively, with whiskers extending to the farthest points within 1.5x x the interquartile range. Flier points indicate outliers beyond the whiskers.
The 6th GSE variation, (Aurans: (CH.DT. ), is based on Xiang Chiong et al. 73 eq. (6)), which states that x sgn (cz)) v [cz] /E Mi 0.5 y- (P (cz = I]). This identity forms the foundation of the estimator in Berlinghieri et al. 88 eq. (7)1. By incorporating our linear utility structure, we obtain the following choice-decision-ting estimator OCH,
ICILDToooii
=
Σ DE Naampi
Σ Namppl
Dh x. sgn (cz)
C2 t
2 4-1 (T.).
We evaluate six GSE variations bandit instances constructed from three real-world datasets of human choices and response times. Each dataset includes multiple participants. For each participant, we estimated dEZDM parameters, built a bandit instance, and simulated the GSE variations assess performance. Details on experimental procedures are provided in appendix D Key results for the three domains shown in fig. 4 with full results in appendix D First, (Auans OCH.DT) consistently outperforms (Auans (CH). demonstrating the benefit of incorporating decision times. Second, both of these variations outperform (Aweak, Ocu). as discussed in section 5.1 Third, (Aurams, PCHDDY) performs similarly to (Atrams, (CHRTT) suggesting that not knowing the non-decision time has minimal impact. Finally, (Aarnos, OcH,.ogin) [67] and (Arranss (CH.DT,
do not perform as consistently well as (Aaronss OCH.DT), highlighting the effectiveness of our proposed choice-decision-iine time estimator (eq. 3
Conclusion and future work
This work is the first to leverages human response times to improve fixed-budget best-arm identi- fication in sefference-basee linear bandits. We proposed a utility estimator that combines choices and response times. Both theoretical and empirical analyses show that response times provide com- plementary information about preference strength, particularly for queries with strong preferences, enhancing estimation performance. When integrated into a bandit algorithm, incorporating response times consistently improved results across three real-world datasets.
One limitation of this approach is its reliance on reliable response time data, which may be challenging crowdsoureing settings where participants' focus can vary 455, Future work could integrate eye- tracking data into the DDM framework [26] 38 responses. Another direction to relax the assumption of known non-decision times by estimating them directly from data, following methods proposed by Wagenmakers et al. (67].
39
57
76 to monitor attention and filter unreliable
10

---

References
[1] A. Alieva, A. Cutkosky, and A. Das. Robust pure exploration in linear bandits with limited budget. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 187- 195. PMLR, 18-24 Jul 2021. /ttppstts///p/oceediiaa html
mlr wwt.pppwwssseeeeeeee.eee httee//v39/aalevve22 alleva22
[2] C. Alós-Ferrer, E. Fehr, and N. Netzer. Time will tell: Recovering preferences when choices are noisy. Journal of Political Economy, 129(6):1828-1877 2021. doi: 10.1086/713732. URL
https://doi. org/10. 10. 1086/713732
[3] M. Azizi, B. Kveton, and M. Ghavamzadeh. Fixed-budget best-arm identification in structured bandits. In L.. D. Raedt, editor, Proceedings of the T'iitty-Frst International Joint Conference on Artificial Intelligence, IJCAI-22, pages Artificial Intelligence Organization, 7 2022. doi: 0.224963/jcaai.222222 //doi.org/10. 24963/ijcai. 20222/388 Main Track.
International Joint Conferences
URL https
[4] A. Badanidiyuru, R. Kleinberg, and A. Slivkins. Bandits with knapsacks. Journal of the ACM (JACM), 65(3):1-55, 2018.
[5] Y. Bai, A. Jones, K. Ndousse, A. Askell, A. Chen, N. DasSarma, D. Drain, S. Fort, D. Ganguli, Henighan, Joseph, S. Kadavath, J. Kernion, T. Conerly, El-Showk, N. Elhage, Z. Hatfield- Dodds, D. Hernandez, T. Hume, S. Johnston, S. Kravec, L. Lovitt, N. Nanda, C. Olsson, D. Amodei, T. Brown, J. Clark, S. McCandlish, C. Olah, B. Mann, and J. Kaplan. Training a helpful and harmless assistant with reinforcement learning from human feedback, 2022. URL bttps://arxxs org/ 2204 05862
[6] C. Baldassi, S. Cerreia- Vioglio, F. Maccheroni, M. Marinacci, and M. Pirazzini. A behavioral characterization of the drift diffusion model and its multialternative extension for choice under time pressure. Management Science, 66(1 50755505993, 2020. doi: 10. (0.12287/mss:2219.4475 URL htttt:tt//oooo. org/ 10.
2019.3475)
[7] V. Bengs, R. Busa-Fekete, learning with dueling bandits: A survey, Journal of Machine Learning Research, 22(7):1-108,
Mesaoudi- and Hüllermeier. Preference- online
2021.
//jttp http:///mmmmoooopppprreeeeeee v2s2ss//2221//// 100//118555 118-5546htmm
[8] R. Berlinghieri, I. Krajbich, F. Maccheroni, M. Marinacci, and M. Pirazzini. Measuring utility
with diffusion models. Science Advances, 934) 2023. doi: 10. so.
URL httph:t/t///ttt www.eccceeecc... wttg//////a///////////oo//////// www.:1122/cciicc 1665
[9] V. Bogina, T. Kuflik, D. Jannach, M. Bielikova, M. Kompan, and C. Trattnrr Considering
temporal aspects in recommender systems: survey. User Modeling and User-Adapted Interaction, 33(1):81-119, 2023. doi: 10.10077/111257--22-999939 org/10. 1007 1 http//111227222-995555
URL hhtth::
[10] R. A. Bradley and M. E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324 345, 1952. ISSN 00063444, 14643510. URL http://www jstor. jot.or.rr/stteee.eeeeeee httg//stable/2344022
[11]
Brown and A. Heathcote. A ballistie model choice response time. Psychological review, 1 112(1):117, 2005.
[12] S. D. Brown and A. Heathcote. The simplest complete model of choice response time: Linear ballistic accumulation. Cognitive Psychology, 57(3):153-178, 2008. ISSN 0010-0285, doi: htps://doi.org/100 101.1001101.ooogyccc.00011111110 12.000.....0000000000..22 URL htthh:ttp//wwwt wwtp://wwwwweneeeeee.....cc.eeee com/
[13] R. Camilleri, K. Jamieson, and J. Katz-Samuels. High-dimensional experimental design and kernel bandits. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1227-1237. PMLR, 18-24 Jul 2021. URL htRL:ttts: URLp mlr. press/v139/
Familleri2ia. html
[14] S. C. Castro, D. L. Strayer, D. Matzke, and A. Heathcote. Cognitive workload measurement and modeling under divided attention. Journal of experimental psychology: human perception and performance, 45(6):826, 2019.
11

---

[15] W. Chu, L. Li, L. Reyzin, and R. Schapire. Contextual bandits with linear payoff functions. In G. Gordon, D. Dunson, and M. Dudik, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 208-214, Fort Lauderdale, FI., USA, 11-13 Apr 2011. PMLR. URL. httts::/prroceedinn mlr press/ press/vv1/chiie http///hhhlaaaa.mm.mm
[16] J. A. Clithero. Improving out-of-sample predictions using response times and a model of the decision process. Journal of Economic Behavior & Organization, 148:344-375, 2018. ISSN 0167-2681. doi:
201 8.02.007. URL https
www.sccieneeirect.oom com/ http:////..aaaeeaaraa.aaaa//////
[17] A. Clithero. Response times in economics: Looking through the lens of sequential sampling models. Journal of Economic Psychology, 69:61 2018. ISSN 0167-4870. doi: hitps:
008. BRLphttps://wwe http://wwww..ciicederrreett com/science
[18] D. R. Cox. The theory of stochastic processes. Routledge, 2017.
[19] P. De Boeck and M. Jeon. An overview of models for response times and processes in cognitive tests. Frontiers in Psychology, 10, 2019. ISSN 1664-1078. doi: 10.3389/fpsyg. 2019.00102. URL https:t:::// / www.:ffootiersi.... otgg://oonaass//yyooooo///rrotta 10. ww38/3/9p988 2019 00102
[20] R. Degenne, P. Menard, X. Shang, and M. Valko. Gamification of pure exploration for lin- ear bandits. In H. D. III and A. Singh, editors, Proceedings of the 37th International Con- ference on Machine Learning, volume 119 of Proceedings of Machine Learning Research. pages 2432-2442. PMLR, 13-18 Jul 2020. URL https://pprceeeddngg .ml.. pat..ppeess/v1////// degenne20a. html
[21] Y. Deldjoo, M. Schedl, and P. Knees. Content-driven music recommendation: Evolution, state of the art, and challenges. Computer Science Review, 51:100618, 2024. ISSN 1574-0137. doi: https://doi.org/10.. 101 10t.1010///.ccsee22220....666 ccceeccc/aattcceee/p/////7777173
URL https: //wp::///ww... www. www.sccceiecirtt.cccmmmm com/
[22] J. Drugowitsch. Fast and accurate monte carlo sampling of first-passage times from wiener diffusion models. Scientific reports, 6(1):20490, 2016.
[23] L. Fahrmeir and H. Kaufmann. Consistency and asymptotic normality of the maximum likelihood estimator in generalized linear models. The Annals of Statistics, 13(1):342-36 368, 1985. ISSN 00905364, 21688966. URL http:http//// http:///www.....rr//o/oo org/ htt///aalleee222//
[24] T. Fiez, L. Jain, K. G. Jamieson, and L. Ratliff. Sequential experimental design for transductive linear bandits. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL
[25] S. Filippi, O. Cappe. A. Garivier, and C. Szepesvári. Parametric bandits:
The generalized linear case. In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010. URL
pdf
[26] G. Fisher. An attentional drift diffusion model over binary-attribute choice. Cognition, 168: 45 2017. ISSN 0010-0277. doi:
URL
[27] D. Fudenberg, P. Strack, and T. Strzalecki. Speed, accuracy, and the optimal timing of choices.
American Economic Review, 108 84, December 2018. doi: 10. 10.12777er.001507422
URL httLht:ts///www aeaweb. org/ htt.aaaricccsiccco
1257 1257/aer.20150742
[28] D. Fudenberg, W. Newey, P. Strack, and T. Strzalecki. Testing the drift-diffusion model. Proceedings of the National Academy of Sciences, 11 111762))33141-333444 2020. doi: 10. pnas.201 1446117. http::ts::/ http///wwwwpp.w..o..//aa/a.aaaap wttp://///////....o.oo.// wtt. 201114......11111..7.
[29] V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. In F. Pereira, C. Burges, I.. Bottou, and K. Wein- berger, editors, Advances in Neural Information Processing Systems, volume 25. Curran As-
12

---

sociates, Inc., 2012. htpp:////proooociiing http://ww....ooooo.ooo//oopooo/p 0012911/40002$$$660000004444141 Paper pdf
[30] R. Grasman, E.-J. Wagenmakers, and H. L.. van der Maas. On the mean and variance of response times under the diffusion model with an application to parameter estimation. Journal
of Mathematical Psychology. 53(2):55-68, 2009. ISSN 0022-2496. doi: hups://doi.on
10. 10.1016/j.jmp.20000 2009.01 .066.
www.ssseeinnedrrrt....mmmm wwwpsciincee/cceecccccccccccccce coom/scienne//rticlee. article/
p11/5802224969000066
[31]
K.-S. Jun, L. Jain, B. Mason, and H. Nassif. Improved confidence bounds for the linear logistic model and applications to bandits. In M. Meila and T. Zhang, editors. Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5148-5155 5157. PMLR, 18 24 Jul 2021. URL.https:/pprooeeddie mlr. ww.ppesssvvss. jun21a. html
[32] M. Karimi, D. Jannach, and M. Jugovac. News recommender systems - survey and roads ahead. Information Processing & Management, 54(6):1233-1227, 2018. ISSN 0306-4573. doi: acciacce/attiidd///////666777333
201..0000000000000000. URI httth:ttt//wwt http///www.iinnedeeeeeeeee. com/
[33] N. Karpov and Q. Zhang. Instance-sensitive algorithms for pure exploration in multinomial logit bandit. Proceedings of the AAA/ Conference on Artificial Intelligence, 36(7):709--7003, Jun. 2022. doi: 10. (6.9/09/aaai, 3617.20666) URL https://ojss.... aaai wo..orgg//ooo.. http//nddxxx./// http:/iiixx.ppph/AAaaaa AAT/
article/view 20669
[34] E. Kaufmann, O. Cappé, and A. Garivier. On the complexity of best-arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17(1):1-42, 2016. URL
http://jmlr
16a. html
[35] A. Konovalov and I. Krajbich. Revealed strength of preference: Inference from response times. Judgment and Decision Making, 14(4):381-39) 2019. doi: 10.1017/S 93029770009977000822.....
[36] Koppol, H. Admoni, and R. Simmons. Iterative interactive reward learning. In Participatory Approaches to Machine Learning, International Conference on Machine Learning Workshop, 2020.
[37] Koppol, H. Admoni, and R. Simmons. Interaction considerations in learning from humans. In 7..H. Zhou, editor, Proceedings of the Thirtieth International Joint Conference Artificial Intelligence, IJCAI-21, pages 283-291. International Joint Conferences on Artificial Intelligence Organization, 8 2021. doi: 10. 20,24663jjcai.222214400 URL https:///oi...... 02g911.219933
ijcai 2021/40024400 Main Track.
[38] I. Krajbich. Accounting for attention in sequential sampling models of decision making. Current Opinion in Psychology. 29:6-11 2019. ISSN 2-0XX doi: https///dii.or//00..00 1016/ j.cosyyc2008..00.m 10.008. httpttps: $2352250x18301566 Attention & Perception.
com//science///ticll///...
[39] I. Krajbich, C. Armel, and A. Rangel. Visual fixations and the computation and comparison of value in simple choice. Nature Neuroscience, 13(10911222-129, 2010. doi: 10. 1038/nn.2635.
URI.tttps :tttpp:://oi... wtg./ioooo///ooooooooooooooooelo org/ 10. 1008/nn..n.... 2635
[40] V. Lerche, A. Voss, and M. Nagler. How many trials are required for parameter estimation
in diffusion modeling? a comparison of different optimization criteria. Behavior Research Methods, 49(2):513-537, 2017. doi: 1.37586613428--11-0774000 URL httpp://///oii org/ 00.3758//s13428-1 016-0740-2
[41] L. Li, W. Chu, J. Langford, and R. E. Schapire. A contextual-bandis approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, WWW ' 10, page 661-670, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 978 1781665587998. doi: 01145/177269011777555 Uttpstts:://doi org/
10. N1..14//1772690.. 1772758
[42] Z. Li, K. Jamieson, and L. Jain. Optimal exploration is no harder than Thompson sampling. In S. Dasgupta, S. Mandt, and Li, editors, Proceedings of The 27th International Conference on Artificial Intelligence and Stutistics, volume 238 of Proceedings of Machine Learning Research, pages 1684-1692, PMLR, 02-04 May 2024. URL http:httt//////eeeee htttps:/ppooeeednggs mmr press/v238/ 1124h.11hhhh 1124hhhtml html
13

---

[43] Menick, M. Trebacz, V. Mikulik, J. Aslanides, F. Song, M. Chadwick, M. Glaese, S. Young, G. Irving, et al. Teaching language models to support answers with verified quotes. arXiv preprint arXiv:2203. /144,, 2022.
L.
[44] T. P. Minka. A comparison of numerical optimizers for logistic regression. Unpublished draft, 2003. URL httctpss:/tminka.t githuu..bb.... io/ httpp/pppee///ooggg///aaaaaa-aee logren pdf
[45] C. E. Myers, A. Interian, and A. A. Moustafa. A practical introduction to using the drift diffusion model of decision decision-making in cognitive psychology. neuroscience, and health sci- ences. Frontiers in Psychology, 13, 2022. ISSN 1664-1078 doi: 10.3389/fpsyg.2022 1039172. URL https://www.w.... www.noorrnsnnnnn.mmmmr org/ http:/oooomllaaaaycoooooo/////// www.:///oogggrrrteee/eee//e 3389/fpsyg. 2022. 1039172
[46] R. Nakano, Hilton, S. Balaji, J. Wu, L. Ouyang, C. Kim, C. Hesse, S. Jain, V. Kosaraju, W. Saunders, et al. Webgpt: Browser-assisted questin--nsseriig with human feedback. arXiv 2021.
preprint arXiv:
[47] L. Ouyang. J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin. C. Zhang, S. Agarwal, K. Slama, A. Ray, Schulman, J. Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, P. Welinder, P. F. Christiano, J. Leike, and R. Lowe. Training language models to follow instructions with hu- man feedback. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 27730-27744 Cur- ran Associates, Inc., 2022. URL /ttp/tttpp//prrrcceiing..so www..eeeuu..pp.reeeeooeee
Cone Conf p
[48] J. Palmer, A. C. Huk, and M. N. Shadlen. The effect of stimulus strength on the speed and accuracy of perceptual decision. Journal of Vision, 11,) 05 2005. ISSN 1534-7362. doi: 10.1167/5.5.1. URL httph::t//// //doi. org/ 10. 1167/5..5...
[49] M. L. Pedersen, M. J. Frank, and G. Biele. The drift diffusion model as the choice rule in reinforcement learning. Psychonomic Bulletin & Review, 24(4):1234-125) 1231-1251, 2017. doi: 10.3758/s13423-011 11----011---99-9--- 1199-y. URL URL/tttss:// https:///oot .rrgg/org///go 10. 3758/ -16-1999--
[50] M. Pérez-Ortiz, A. Mikhailiuk, E. Zerman, V. Hulusic, G. Valenzise, and R. K. Mantiuk. From pairwise comparisons and rating to a unified quality scale. IEEE Transactions on Image
Processing. 29:1 139-1151, 2020. doi: 10.
[51] R. Ratcliff and G. McKoon. The Diffusion Decision Model: Theory and Data for Two- Choice Decision Tasks. Neural Computation, 20(4):873-922, 04 2008. ISSN 0899-7667. doi: 10.1162/neco. (t162//cco.208.... 12-06-42.
/rg/:///////ooo//////////// w162/neco.......... 2008. 12-06 06-00004444 420
[52] R. Ratcliff and F. Tuerlinckx. Estimating parameters of the diffusion model: Approaches to dealing with contaminant reaction times and parameter variability. Psychonomic Bulletin & Review, 933):338 481, 2002. doi: 10.3758/BF0319630
orgo 0tgg/1..5 3758/
BF03196302
[53] R. Ratcliff, P. L. Smith, S. D. Brown, and G. McKoon. Diffusion decision model: Current issues and history. Trends in Cognitive Sciences, 20(4):200-21,, 2016. ISSN 1364-6613, doi: https://doi.ooo wttg//..1/11/////. wit..iic.........000. science/articce. /ttp:///1///11111111000100
URL https://wwws wwwp http///wwwwwiieneeeeeettteteee com/
[54] D. Sadigh, A. Dragan, S. Sastry, and S. Seshia. Active preference- learning of reward functions. In Proceedings of Robotics: Science and Systems, Cambridge, Massachusetts, July 2017. doi: 10.15607/RSS 2017 7.1.III1..053.
[55] M. Shvartsman, B. Letham, E. Bakshy, and S. L. Keeley. Response time improves gaussian process models for perception and preferences. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024.
[56) N. Silva, H. Werneck, T. Silva, A. C. Pereira, and I. Rocha, Multi-armed bandits in recommen- dation systems: A survey of the state-of-the-art and future directions. Expert Systems with Appli- cations, 197:116669) 2022. ISSN 0957-4174. doi: https///doi.or/11011116....... 16666 16669, http://iiieeeeetcceeeee////////o
www.:eccienneeeceeeeeeeemm URL/ittppe//ww..scicccddeeettttt com/ httm///iiinneeeeecieeeeeeeeeeeee
[57] S. M. Smith and I. Krajbich. Attention and choice across domains. Journal of Experimental Psychology: General, 147(12):1810, 2018.
[58] T. Somers, N. R. Lawrance, and G. A. Hollinger. Efficient learning of trajectory preferences using combined ratings and rankings. In Robotics: Science and Systems Conference Workshop on Mathematical Models, Algorithms, and Human-Robot Interaction, 2017. 20177.
14

---

[59] N. Stiennon, L. Ouyang, J. Wu, D. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. F. Christiano. Learning to summarize with human feedback. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural In- formation Processing Systems, volume 33, pages 3008-3021 Curran Associates, Inc., 2020. URL httpss:/ wwwr.gs.......pp...... F1S851555966666641344488-------- Papp:e/bee.eeeeee---aaaprere.eee
[60] T. Strzalecki. Stochastic Choice Theory. Econometric Society Monographs. Cambridge University Press, 2025. URLjattps://sshoo
edu/ttlesstommazz/ atttoaass//tlee//nnnnsi....ppppp
[61] C. T,,, S. Blanco, and Y. Zhou. Best arm identification in linear bandits with linear dimension de- pendeney. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 4877-4886. PMLR, 10-15 Jul 2018. URL URL
mmlr. press/ /e/////00//t//// ttt//aallaa..a///.. html
[62] A. W. Thomas, F, Molter, I. Krajbich, H. R. Heekeren, and P. N. C. Mohr. Gaze bias differences capture individual choice behaviour. Nature Human Behaviour, (6)) 633,,,5,,,, 2019. doi: 10. 10.1038/s41562-019 000--22------------
org/ 10. 0038//44162-009-005552
[63] A. Tirinzoni and R. Degenne. On elimination strategies for bandit fixed-confidence identi- fication. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 18586-18598, Cur- ran Associates, Inc., 2022. URL
newrtiiinninnnnnneepeee..... nwwrips httpprpppppccppppp/////eeeeeee Ponfred pdf
[64] S. Trueblood, S. D. Brown, and A. Heathcote. The multiattribute linear ballistic accumulator model of context effects in multialternative choice. Psychological review, 121 2014.
[65] M. Tucker, E. Novoseller, C. Kann, Y. Sui. Y. Yue, W. Burdick, and A. D. Ames. Preference- based learning for exoskeleton gait optimization. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 2351-2357, 2020. 9196661.
doi: 10.1100/CRR440945.0002
[66] M. Usher and J. L.. McClelland. The time course of perceptual choice: the leaky, competing accumulator model. Psychological review, 108(3):550, 2001.
[67] E.-J. Wagenmakers, H. I.. J. Van Der Maas, and R. P. P. Grasman. An e7-diffusion model for response time and accuracy. Psychonomic Bulletin & Review, 14(1):3-22, 2007. doi: 10.3758/BF03194022, Uttttttss:// //doi. org/ 00tg/0..778)) 30..3758/BBRB 33758/BF0319402
[68] E.-J. Wagenmakers, H. L. J. van der Maas, C. V. Dolan, and R. P. P. P. Grasman. Ez does it! extensions of the e7-diffusion model. Psychonomic Bulletin & Review, 1229 2008. doi: 10.3758/PBR.155 15.6. 1229. Uttpstss:: http:///ii..ogg///// wtt//o..///00001011 111.0.073//P... 11.8.155.66 15.6.
[69] M. J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[70] R. Webb. The (neural) dynamics of stochastic choice. Management Science, 65(1):230-255 2019. doi: 10. 11277/mmsc221111 2017.2931. /tttpp 1287m//........./.......ooo 2017 2931
1287/
[71] T. V. Wiecki, I. Sofer, and M. J. Frank. Hddm: Hierarchical bayesian estimation of the drift-diffusion model python. Frontiers in Neuroinformatics, 7, 2013. ISSN 1662-
5196. doi: 20.3389/fniff.201 3.00014. URL htttps:://wwtt www.::.rooooiiiiiiie org/ jorjjauralls/ 3389 13899ffninf fninf. 2013. 000144
[72] N. Wilde, E. Biyik, D. Sadigh, and S. L. Smith. Learning reward functions from scale feedback. In A. Faust, D. Hsu, and G. Neumann, editors, Proceedings of the 5th Conference on Robot Learning, volume 164 of Proceedings of Machine Learning Research, pages 353-362. PMLR, www.mmll..ssss. prres//164//iideee
08-11 Nov 2022. URL. https: ttktts:://prcceedinn
.html
[73] K. Xiang Chiong, M. Shum, R. Webb, and R. Chen. Combining choice and response time data:
A drift-diffusion model of mobile advertisements. Management Science, 70(2):1238-13 1257, 2024. doi: 10. www.122mmmc..223..1.
BtRL:ttts:://oot htt:///oooorr/0///// 10. /w/.///mmsc... 2023 4738
[74] Y. Xu, H. Zhang, K. Miller, A. Singh, and A. Dubrawski. Noise-tolerant interactive learning us- ing pairwise comparisons. I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, vol- ume 30. Curran Associates, Inc., 2017. URt/https::/ Assoodiss......o.///.///aae//spo
neurips...ppp.... cttccc//pppaa cc/paper"/ .dff
15

---

[75] J. Yang and V. Tan. Minimax optimal fixed-budget best amm identification in linear ban- dits. In S. Koyejo. S. Mohamed, A. Agarwal. D. Belgrave, K. Cho, and A. Oh, editors. Advances in Neural Information Processing Systems, volume 35, pages 12253-12266. Cur- ran Associates, Inc., 2022. URL URL itL. newpreeeeeddddneeeeeeerer..r.rp neurips cc/pappe/55ffllsss/ 1t002///1e/449342200 21511221512251031103303000226630 Con pdf
[76] X. Yang and I. Krajbich. A dynamic computatiionl model of gaze and choice in multi-attribute decisions. Psychological Review, 130(1):52, 2023.
[77] H. Yu, R. M. Aronson, K. H. Allen, and E. S. Short. From "thumbs up" "10 out of 10": Reconsidering scalar feedback in interactive reinforcement learning. In 2023 IEEF/RSJ International Conference Intelligent Robots and Systems (IROS), pages 4121-4128, 2023. doi: 10.1 (09//ROS55552..223...00 10344458.
[78] C. Zhang, C. Kemp, and N. Lipovetzky. Goal recognition with timing information. Proceedings of the International Conference Automated Planming and Scheduling, 33(1):443-451, Jul. 2023. doi: 10. wtt.////cw.........2...
URL https://///j aaw:: org/ index pwpp/CAPSp////////////
Siicceeviee/27222-
[79] C. C.Zhang, C. Kemp, and N. Lipovetzky. Human goal recognition as bayesian inference: In- vestigating the impact of actions, timing, and goal solvability. In Proceedings of the 23rd International Conference
Aulonomous Agents and Multiagent Systems, AAMAS '24, page
2066-2074, Richland, SC, 2024. International Foundation for Autonomous Agents and Multia- gent Systems. ISBN 9798400704864.
16

---

A Broader impacts
Incorporating human response times in human-interactiiv AI systems provides significant benefits, such as efficiently eliciting user preferences, reducing cognitive loads on users, and improving accessibility for users with disabilities and various cognitive abilities. These benefits can greatly improve recommendation systems, assistive robots, online shopping platforms, and fine-tuning for large language models. However, using human response times also raises concerns about privacy, manipulation, and bias against individuals with slower response times. Governments and law enforcement should work together mitigate these negative consequences by establishing ethical standards and regulations. Businesses should always obtain user consent before recording response times.
17

---

B Literature review
B.1 Bounded accumulation models for choices and response times
Bounded Accumulation Models (BAMs) describe human decision making using an accumulator (or sampling rule) and stopping rule [70]. In binary choice tasks, such as two-alternative forced choice tasks, a widely used BAM is the drift-diffusion model (DDM) [5T), which models decisions as Brownian motion with fixed boundaries. To capture differences in human response times for correct and incorrect answers, Ratcliff and McKoon [5]] allows drift, starting point, and non-decision time to vary across trials. Wagenmakers et al. [67] later introduced the EZ-diifusion model (EZDM), simplified version of DDM with closed form solutions for choice and response time moments, making parameter estimation easier and more robust. EZDM assumes deterministic drift, starting point, and non-decision time, fixed across trials, with the starting point equidistant from the boundaries. Berlinghieri et al. 8 specialized EZDM to the difference-based EZDM (dEZDM), where the drift represents the utility difference between two options. For binary queries with arms 21 and 22, the drift is modeled as 11z, Mzg. where U2 and U2 the utilities of 21 and 22-
As discussed section 2 we impose linear utility structure on the dEZDM, where each arm's utility is given by v, 0", with 0" denotes the human preference vector. This approach is supported by both bandit and psychology literature. In bandits, linear utility models scale efficiently with large number of arms [15 41]. In psychology. linear combinations of attributes are commonly used in multi-attribute
massiinnmmaiingg models [26] 64 [6].. The standard dEZDM in (8) Definition 1] is special case of our dEZDM with linear utility structure, where arms correspond to the standard basis vectors in Euclidean space TR This mirrors the relationship between multi-armed bandits and linear bandits.
Similarly to our approach, Shvartsman et al. (55 parameterize the human utility function as a Gaussian process and propose a moment-matching Bayesian inference method that uses both choices and response times to estimate latent utilities. Unlike our work, their focus is solely on estimation and does not address bandit optimization, Integrating their estimation techniques into bandit optimization presents an interesting avenue for future research.
Another widely used BAM is the race model [ 66). which naturally extends to queries with more than two options. In race models, each option has its own accumulator, and the decision ends when any accumulator reaches its barrier. BAMs can also model human attention during decision-making For example, the attentional-DDM B8 39 76) movements across different options or attributes. Similarly, Thomas et al. [62] introduce the gaze- weighted linear accumulator model to study gaze bias at the trial level. To incorporate learning effects, Pedersen et al. [49] combine reinforcement learning (RL) with DDM, where the human adjusts when interacting with humans. BAMs also connect to Bayesian RL models of human cognition. For example, Fudenberg et al. 27 propose a model where humans balance decision accuracy and time cost, showing it is equivalent to DDM with time-decaying boundaries. Neurophysiological evidence supports BAMs. For instance, EEG recordings demonstrate that neurons exhibit accumulation processes and decision Additionally, diffusion processes have been used to model neural firing rates [53
jointly models choices, response times, and eye
the drift through RL. In contrast, our work uses RI. for Al decision-make
thresholds 70
B.2 Parameter estimation for bounded accumulation models
BAMs often lack closed-form density functions, so hicrarchical Bayesian inference commonly used for parameter estimation [71]. While flexible, these methods are computationally intensive, making them impractical for real-time applications in online learning systems. Faster estimators [ 67 73
usually estimate parameters for individual option pairs without leveraging data across pairs To address this, we propose a computationally efficient method for estimating linear human utility functions, which integrate into bandit learning. In section 5.2 empirically show that estimator outperforms those from prior work 67 73).
In practice, using response time data requires pre-processing and model fitting, as outlined by Myers al. (55). Additionally, Alós-Ferrer et al. (2) Baldassi et al. (). Fudenberg et al. 28 propose statistical tests to assess the suitability of various DDM extensions for a given dataset.
18

---

B.3 Uses of response times
Response times serve multiple purposes, as highlighted by Clithero 17]. A primary use improving choice prediction. For instance, Clithero [16] showed that DDM predicts choice probabilities more accurately than the logit model, with parameters estimated through Bayesian Markov chain Monte Carlo. Similarly, Alós-Ferrer et al. [2] demonstrated that response times enhance the identifiability of human preferences compared to using choices alone.
Response times also shed light on human decision-making processes. Castro et al. 14] applied DDM analysis explore how cognitive workload, induced by secondary tasks, influences decision-making. Analyzing response times has been a long-standing method in cognitive testing to assess mental capabilities 19]. Additionally, Zhang al. 78 79 introduced framework that uses human planning time to infer their intended goals.
Response times also enhance AI decision-making In dueling bandits and preference-based RL 77, human choice models are commonly used for preference elicitation. One such model, the random utility model, can be derived from certain BAMs 22. For example, as diseussed after eq. ( both the Bradley-Terry model [0] and dEZDM S 67 yield logistic choice probabilities the form
P(z1 22] d'logisti( (12, M2,)
(1 exp (-c- c (u=, Wzg))) where U2 and 12 denote
the utilities of and 22 and e is some constant 7 section 3.2]. Our work leverages this connection
between random utility models and choice-response-timg models estimate human utilities using
both choices and response times.
We hypothesize that our key insight, that response times provide complementary information, es- pecially for queries with strong preferences, extends beyond the dEZDM and the specific logistic link function Iagistiic Many psychological models capture both choices and response times but lack closed-form choice distributions. In such cases, the choice probability is often expressed as P(z1 22] a² (uzz M2z)), where of is funetion of Uz and U22 without closed form. Fixing Uez and varying Usy defines the psychometric function of Uzg), which typically exhibits an "S" shape [60] fig. 1.1]. As preferences become stronger, of flattens, similar to figs. lb and Ic sug- gesting that choices carry less information. We conjecture that response times remain a valuable complementary signal in such cases.
If we further assume the choice probability depends only the utility difference, Usy u2gg then P(z1 22] ( Uz,,), ). where the link function o is typically assumed to be strictly monotonic and bounded within [0, 1] [7]] section 3.2]. These properties naturally produce an "S" "S""shaped curve that flattens preferences become stronger, again suggesting that choices provide less information. In such cases, we conjecture that response times can complement choices to enhance learning.
In summary, BAMs, like DDMs and race models, offer a strong theoretical framework for understand- ing human decision-making, supported by both behavioral and neurophysiological evidence. These models have been widely applied to choice prediction and the study of human cognitive processes. Our work connects BAMs with bandit algorithms by introducing a computationally efficient estimator for online preference learning. Future research could explore other BAM variants to further examine the benefits of incorporating response times.
19

---

C
Proofs
C.1 Parameters of the differeece-based EZ.DDiffusion Model (dEZDM) 8 67
Given a human preference vector 0" for each query z E X. the utility difference is defined as ug =
0" In the dEZDM model (introduced in section 2), with barrier according to Wagenmakers
et al. 667 eq. (4), (6), and (9)), the human choice Cg has the following properties:
exp -awu,)
P (cx = 1) + exp 2au,)
IP (c2 = - + exp ( -auz)
Thus, the expected choice is E [cx] = tanh (au,) and the choice variance [Ca] = 1 (an)()u,)) (restating eq. I
The human decision time ty has the following properties:
tanh(au.)
if u2 + if U2 =
B [[m]
(restating eq.
exp(4au, )-1 1- 4an, exp(2am.))
if u2
V [ta]
(exp(2auz)+1) +1]
2a
/
if ut
From this, obtain the following key relationship:
E
(1or)
(restating eq. (2)
a
All these parameters depend solely on the utility difference Uh == x 0r and the barrier a.
C.2 Asymptotic normality of the choice-decision-tine estimator for estimating the human preference vector 6"
We now present the proof of the asymptotic normality result for the choice-decision-tigg time estimator, ÓCH.DT. as stated theorem 3.1 which is restated as follows:
Theorem 3.1 (Asymptotic normality of ÜCH.DT). Given a fixed i...d. dataset {ar, C2,52,0 I2, iE(m) for each x E Xsumpies where ExEXimp. xx" > O, and assuming that the datasets for different Xsample are independent, then, for any vector y E RRd, n + o0, the following holds: 1 0/)) Here, the asymptotic variance depends on a problem-specift constant, <², with an upper bounded:
Vny" (OCH.DTm-
D, (202c
2² ||yll Exex [min cx E[(e.]] I
Proof. To simplify notation, we define:
C c--1 Cr,
[E=E] F
Σ
To F Ett.]
(7)
For brevity, we abbreviate Nample as and iCHDDT,, as θ. The estimator 1 can be expressed as:
θ= Σ nx'x'T
Σ
nx
(restating eq. 33).
T
We rewrite fa/a as:
-1
0r
8" //-
Σ ax'a
Σ
nær
a
Ex
ZEN
(8)
C.
Σ nada!
Σ
NE
T
20

---

Therefore, for any vector E R", we have: 0 = 1/²
Σ EEE
na'a'
-1
Σ DEN
na
Cx
C2 T
Σ #EA
&
C T
C2 Tx
Tx
where & is defined as &nr = (Er'Ex nx x) næ. In eq. (9). the only random variables are C. and Tz. For simplicity, for any I; X (01,-.. Z1 slighly abuse the notation and use S. Ci 14. C., Ti, C₁ and T denote Euz Cx. bxx Cr,, Tap Cr,, and Tz respectively. By applying the multidimensional central limit theorem, we have:
E C1
V [ca] cov [11cc]
cov [er, h]
T C1
V (41
vn
D N
0,
G|i| GpE)
V [qx1 cov [4x] Gail
cov [qre tixil [4x1
Txx Gpxl
V Veal [ttl..... v [9xil v [txil)
- 0, diag
(10)
In the first line of eq. 10). the block-diagonal structure of the covariance matrix emerges because
(C,, Te) are independent of each other. For any fixed r;, to derive the second line of eq. (10).
we use the fact that:
E [40]
(c: = 1) E 4/c; = 1] + (a= = - 1) 1E [-1 4/e = -1]
(P (c: 1) P (c. -1)) B [t/c 1]
(11)
E [c E [t.]
where (i) is because [t 1] = E [t.cc = 11 [48] eq. (A.7) and (A.9)). Therefore, eq. implies that cov(c,, t,)
which justifies the second line of eq. (10
Now, define the function g(c,, 4, ..x) 4x11 Eiellan & Gf/4 The gradient of y is:
(x1))x)) [5/4 - f/x/4xx1 -(xx19x1/(x111 (12)
Using the multivariate delta method, we obtain:
C2
Σ
&
T.
T
v
g C, .,. Gx Txl)
(c..
T.... .ix) Txx))
[cll
v(4]
D, N
0, Vg
AVgT((ca (CN.
v [qxi]
v(c)) + -. (iccs)
-
=
0, Σ
?
T.
2
V(c)) + a²Ct aFC7v(1i)
T. v(())
N
0, 2
Σ xI]
&
T.
(13)
"Equation 11] implies that for any query æ,, the human choice e and decision time t; are uncorrelated. Moreover, they are independent, as discussed by Drugowitsch [22] the discussion above eq. (7) and Baldassi al. 6 proposition 3J.
21

---

By applying the identities outlined in appendix C.1
we can establish the following identity:
c²c² 1 T
Vi E [|~|]
V(G)
v(L)
(14)
T.
Te
Substituting this identity into eq.
13
we obtain:
&
C
D
N
0, 1 2 Σ 2 7,7,
(15)
T
T
a² xE||xa]
x|||
Finally, the asymptotic variance be upper bounded follows:
Σ
c
T:
1
Σ =E||a2]
a min Te
1
ΣVT
Σ na'x"
n² Fxxx T
Σ
na aa
= a² minie||x11] Te
DEX
WX'E
(16)
a² mingelix!! To '7
1
E
x'aeT
NEEN
-1
1
min To alao' xE(1x1]]
y
1
a² ||:l|
(Exe [miineuii Milatzrr>-
22

---

C.3
Non-asymptotic concentration of the two estimators for estimating the utility difference Uz given query x
C.3.1
The choice-decision-iie estimator
focuses the problem of estimating the utility difference for single query. Given query x E Æx the objective is to estimate the utility difference Uy == _T 8" using an i.i.d. dataset, denoted by (Crz,s,,) t2, Je((m.)
Section 3.3
We begin by applying the ceaice-decision-tiie estimator from eq. which derived by solving the following least squares problem:
Eie(nr] Cz,sais Eie(nel bur,on
OCHLD min
Σ
x To
dER
2E
Similarly, the utility difference for single query is estimated the solution to the following least squares problem, yielding the estimate:
Eie(n.) Coloar
Eie(na) Czioni Lie(nal tir,oos
7g CH.CD = arg min wER
(restating eq. (
Eie(na] tix,0ni
The resulting estimate, UHDCH approximates uz/a rather than Mg. However, since the ranking of arm utilities is preserved between uz/a and Ug estimating uz/a a is sufficient for the purpose of best-arm identification.
For the case where the utility difference Ugr *f O, the non-asymptotic concentration inequality for this estimator is presented in theorem 3.3 To prove this, first introduce lemma C.1 which demonstrates that for any given query v, the decision time is sub-exponential random variable.
To simplify notation, we define:
CN U2,CH.T
C₂
Co
C₂
E [cx],
T
To [[2),
1l
Th.t
T
(17)
Lemma C.1. uf + then (tz 'T2) sub-exponential SE (v2 az). where Vs /2a//lll /uml and 0g == 2/12.
Proof. For simplicity, we will omit the subscript x throughout the proof and assume, without loss of generality, that 0.
Our objective is to establish the following inequality, which holds for all s E (2 w²/2):
22a 22a2/u² 52
E (exp (s (l-T)) exp
(18)
This implies that (L-T) is sub-exponential SE (v²,a). a), defined by Wainwright tion 2.7].
69 Defini-
Step 1: Transform eq. 18 into more manageable inequality (eq. 24 )
23

---

Using Cox 18 eq. (128)], with A == 22 -22, 81 = =- V and 02 == - + VA, we have
E (exp (st)) exp (a0)) cxp (2a02 + a01)
cxp (a02) cxp (2a01 + aL2)
exp (2a01) exp (2af2)
exp (2a01) ) exp (2a02) exp (a02) [] + exp (a0g + ad1)l
exp (a01) [1 + exp (a01 + a82)l
exp (2a01) exp (2a82)
cxp (2a01) oxp (2a02)
(exp (af1) exp (al22) + exp (alt + a01))
exp (2a81) ) - exp (2a02) exp (a02 + a02)
(19)
exp (a0)) + exp (a02)
exp (-au) + exp (aw)
exp
-ay avv A + exp av A
N
D(s)
In the last line, define N 2 coss((au) and D(s) cosh(av))) Thus, we arrive
N
N
E (exp (s (t- T)))
(20)
((s)
exp T)
exp (sa tanh(au) //)/ D(s)
To prove the original inequality in eq.
(18 it is now sufficient to show:
D(s) exp tanh(au)s uz
2 N.
(21)
For = 0, the inequality holds trivially, as:
D(0) 1 = 22cosh(au)) N.
(22)
For * O, taking the derivative of the left-hand side of eq. 21 yields:
(
a² 42
(ss)
exp
tanh(au)s+ +
ds
exp
a
tanh(au)s
+ w
=
a²
2a
sinh (avA) + 2 2osh (avA): ( tanh(au)) +
+2 a²
12
VA
a²
(avA)= (-va tanh (av A
+ tanh(au) +2 a²
2exp
tanh(au)s +
x2
cosh
u
w²
(23)
In step 2, we will prove the following inequality:
tanh (avA) + a tanh(au) + 2 a²
0.
vs 0,
(24)
22
vs 0,
Equation 24 implies that D(s) exp tanh(au)s + a² (²5²) 2 N, which finishes the proof.
Step 2. Prove eq. 24
In Cox [18 eq. (128)), setting 2a and leads the desired result.

---

For 2 0, the following holds:
+ 2 a
VA
tanh avv A
+
tanh(au)
u
tanh
(avA)
1
+
"
VA
a tanh (avA)
-ss
+ +2
u2
uv A
VA + 1
(25)
tanh (aVA) A
a
2 a²
-
28
u
VA
+
u
avA
u²
(4)
d²
2
28
1+1
1
2
u
u
0.
Here, (i) follows from tan)(au) tanh(av/A) tanh(av u 2s) and (ii) follows from tanh(x)/2= S 1.
For O. the following holds:
tanh(au) +2 a²
tanh (av A
VA
u
(
(1
+ 2 a
S a tanh (avA)
VA
u2
a²
tanh (avA
A
a²
(26)
- 2s
2 u²
u
A
avA
(8)
a²
a
2s
1+2
2
2
u
0.
Here, (i) follows from tanh(au) tanh(z)/z
tanh(aa /²2 -2s) and (ii) follows from < tanh(av/ AA)
By combining both cases, conclude that the inequality in eq. (4 holds, which completes Step and proves the desired result.
Next, prove theorem 3.3 which provides the non-asymptotic concentration inequality for the estimator from eq. restated as follows:
Theorem 3.3 aNon-asymptotic concentration of (.,CHH.DT) For each query E X with Ue # 0. given fixed i.i.d. dataset {Cr,ee. tx, seinal for any satisfying s min (lunl/(V2a)) (1 + v2) aluzl/R. [tz]], the following holds:
((0E.CH.Dr Un
> E) s 4exp (-
CH.DD
non-asym
(x [B n₂ [e aaa))
(x = E [tz] [2 2v a]. where m CHDDT
non-asym
Proof. For clarity, we will omit the subscripts æ throughout this proof. Based on lemma C.T define the constants == /2a/|u| and a = 2/u².
we
We begin by introducing Ec := T/ (V2+ + /2v|Cl/T) e and ET = vrc. From the identities provided
in appendix C.1 we know that vCClTT /2a/ |u] lul/a = 22. This allows to simplify the constants <c and 6T as:
T
VT
cc
2 (v2 +
and eT = V2 v2(v2+1) +1)
(27)
25

---

For any satisfying the following condition:
1 22(1 + V2
I min
(28)
v
at
observe that ey min (T(1 v2/ /2/ following:
We now apply lemma C.2
to derive the
P (
no
s 2exp
(29)
2v²
Thus, by combining the results, conclude:
Č c T
Č C
22th + FT IC//T
P
> e
= P
>
T T
T
P
(1ē
cl
Ec)
IP
(1F-7/ > oT)
-T-
(18)
ned
neT
S 2 2xxp
2
exp
(30)
2v2
(81)
nEē
4cxp
T2
4xxp
4 + v2)
Here, (1) follows from lemma C.3 eq. 27
(it) uses lemma C.2 and eq. 29 and (ibi) follows from
Supporting Details
Lemma C.2. For each query x with U2 * O, and constants ec 0 and eT E (0, /22)) the following inequalities hold:
P ((G.- - C. 2 <c) s 2exp
(-
net
P P( - -Tx 2 (T) S 2exp
net
(31)
2
2v?
Here, the constants are V2 //2a/us and ag 2/12.
Proof.
Since er E 11,,1). by applying Hoeffding's inequality 669
proposition 2.5], we obtain:
P ((e, - co Ec) s 2 exp
nc2
(32)
2
From lemma C.I we know that tx sub-exponential SE ax). By applying Wainwright 669 proposition 2.9 and eq. (8)1 we obtain:
P ((T Ta 2 eT) S exp
ne²
VeT (0, (0,
(33)
2v²
Lemma C.3. Consider constants E IR, > Ec > O. and ET E (0. For any
E CC ec, C Ec) and & E IT <T, T + c the following inequality holds
? c
CT. Cl/T
$ T
(34)
7 T
T
26

---

Proof. The maximum value of CCT is attained the extremum of CL/T. Since C/T linear in C, the extremum of C/T is attained at C E {C cc, + ect for any 7 E [T T + c7) > 0. Given that T >> O, the extremum of C* /T is attained T {T <T, T ET). Therefore, the extremum of C/T lies in the set:
Č C c-c
cc.
C-cc
C+
C C+
T -T"
T Tee
ET
T + ET
(35)
For any combination (se, ST) E {+1} {=1}. and using the function CT S (1-1/v2)1
have:
C + sCEC
C s STETC
EC + ET|C VV +
(36)
T STET
T
(T + STET)
T(T - cT)
T
By combining these results, conclude that:
C T
C+ sere C
$ -2 + +T/Cc/TT
max (sc.eT (Ec=)))(
Celc-co,Cteel Tcl
T
T+
T
C.3.2 The choice-only estimator
We now apply the renssticrrerrssion--oe based choice-only estimator from eq. (4) to estimate the utility difference for a single query. Recall that for each query x X. the human choice C2 E [11 We define the binary-encoded choice 6z == (cz 1) /2 E (0, 1). We reformulate the MLE in eq. (4) into a utility difference estimation problem for a single query, leading to the following optimization problem:
Ur,CHI = arg max MER
Σ se[nal
log (Cz,,az, u)
arg max
Σ
log
(u(u)) (ul (u(-u))==eaaa)
WER
xE(m=]
The first-order optimality condition provides the optimal solution:
Üg 11
(restating eq. (6))
f1.
vE[nz]
where f (p) == log (p/(1 - p)) the logit function (also known as the log-odds), defined as inverse of the function pl-) introduced in eq. (4)
The resulting estimate, ur Ur from eq. (6) gives an estimate of 2au not ug. However, since the ranking of arm utilities based on 20u is the same as that based on the true ug estimating 2au
suffices for identifying the best arm.
The non-ave -symmttttiiic concentration inequality for this estimator is stated in theorem 3.4 This result is
directly adapted from Jun al. BI theorem 5], by letting ø1 It and fat d 1.
27

---

D Experiment details
Our empirical experiments (Sec. 5 were conducted on MacBook Pro (M3 Pro, Nov 2023) with 36
GB of memory.
Our implementation is available via http:://sheelllroot..iii wttp:/htt.......e///eeeeseeeeeee 199
The code is written in Julia and builds on the implementation by Tirinzoni and Degenne [63]. where the transductive and weak-preference designs solved using the Frank-Wolfe algorithm [24]. Their code is accessible at htttp:://gtthut wwmmAnnreeaaiiiinnooi...
html
immttiooelminaationn Simulations and Bayesian inference for the DDM are implemented using the Julia package SeggenniialSaammlligttoooellee j1. available at https:://ttssti
github..h........ io/
For query x E X. the estimators from Wagenmakers et al. [67 and Xiang Chiong et al. 73 ana- lyzed in section 3.3 and benchmarked in section 5.2 require caleulating μ (p) = log (p/ (1 p)),
where μ (-) is the logit function and p 1/n,, Li=1 (Cr,s..; + 1) /2 represents the empirical mean of the human binary choices coded as or 1. Since p = or p = makes this calculation
Vix
undefined, we follow Wagenmakers et al. [67 the discussion below fig. 6] and approximate p as (2mg) when p = 1 and 1/(2n,)) when p =
1
D.1 The "Sphere" Synthetic Problem for Evaluating Estimation Performance section 5.1
We evaluate estimation performance using the "sphere" synthetic problem, standard benchmark linear bandit literature 20 42 61]. In this problem, the arm space C {z E IR: ||=||2 = 1} contains 10 randomly generated arms. To define the true preference vector 0", we select the two arms and z' that are closest in direction, i.e., (z, E arg max =z', and set z 0.01 -z) In this way, 2 the best arm. The query space is X = {= z': 2}.
28

---

D.2 Processing the food-risk dataset with choices (-1 or 1) [57
We accessed the food-risk dataset with choices (-1 or 1) [57 through Yang and Krajbich 76 repository (https://osí 1 Lo/d766//). This dataset includes the choices and response times of 42 participants, each responding to between 60 and 200 queries. Each query compares two arms, with each arm containing two food items. By selecting an arm, participants had an equal chance of receiving either food item, hence the name "food risk" (or (rood-gamble)) task. Additionally, participants' eye movements were tracked during the experiment. Yang and Krajbich [76 modeled each participant's choices, response times, and eye movements using the attentional DDM (39), where the drift for each query is linear combination of the participant's 's ratings of the four food items in the query, with the weights adjusting based on their eye movements. The ratings, E {-10, -9, -9....... ...,, ................................ 9, 10), were collected before the participants interacted with the binary queries.
In our work, for each participant, we define each arm's 's feature vector as the participant's ratings of the two corresponding food items, augmented with recond-order polynomials. We fit each participant's s with a linear utility structure, as introduced in section 2 For each participant, using Bayesian inference with non-informative priors [16], we estimated the preference vector 0* E R., non-decision time momdee, and barrier a. Across participants, the barrier a ranged from 0.715 to 2.467, with mean of 1.437, and nondee ranged from 0.206 to 1.917 seconds, with a mean of 0.746 seconds. This procedure generated one bandit instance per participant, with preference vector 0* RR, an arm space Z C R where |2| E [31, 95]. and query space X : {z =':2 E Z}. Then, we used the fitted models to simulate human feedback for bandit experiments.
data to a difference-bante based EZZ-diffusion model X 67
For each bandit instance, we benchmarked six GSE variations (introduced in section 5.2p (Aurans: (CHLD)) (Aurans: fcuar), (Aurams Pcu), (Aweak, Ocu), (Aurans fcIuooii, and (Aurans (CH.DTIooa For each GSE variation, we ran 300 repeated simulations under different random seeds, with human choices and response times sampled from the dEZDM with the identified parameters. Since each bandit instance contains different number of arms, rather than tuning the elimination parameter v) in algorithm| [ for each instance, we set = 2, following the convention in previous bandit research, e.g., Azizi al. (3] section 3]. We manually tuned the buffer size Buuff in algorithm to 20. 30, or 50 seconds based on empirical performance, ensuring the budget was not exceeded in each phase. The full results are shown in fig. 5 with selected results highlighted in fig. 4a
(Peaa Resssaal
Ornoke Bens
(Amma Boa)
Auuan Benarr)
Duuan ResLa:))
1.0
0.8
Eroo alllyy Pl
0.8-
0.4
0.2
0.0
250
1000
1500
2500
5000
Budget (see)
Figure 5: A violin plot overlaid with box plot showing the best-arm identification error probability, P * 2*1, as function of budget for each GSE variation, simulated using the food-risk dataset with choices (-1 1) [57] as described in appendix D.2] The box plots follow the convention of the matplotlib Python package, For each GSE variation and budget, the horizontal line the middle of the box represents the median of the error probabilities across all bandit instances. Each error probability is averaged over 300 repeated simulations under different random seeds. The box's 's upper and lower borders represent the third and first quartiles, respectively, with whiskers extending to the farthest points within 1.5x the interquartile range. Flier points indicate outliers beyond the whiskers.
29

---

D.3 Processing the snack dataset with choices (yes or no) 16
We accessed the snack dataset with choices (yes or no) 16 through the supplementary material pro- vided by Alós-Ferrer et al. [2] at stttps://wwz journals uchi cago. edu/doi/abee aas/aa.s...//////.b./.../a/a 10. 1086/ 713732 This dataset consists of training and testing data. The training data was collected from a "YN" task, where 31 participants provided binary feedback ("Yes" or "No") and response times for queries comparing each of the 17 snack items to a fixed reference snack, with each query repeated 10 times. The reference snack, assigned a utility of 0, remained fixed throughout the experiment. The testing data was collected using a two-alternative forced-choice task, where participants provided binary choices and response times for queries comparing two snack items, with each query repeated once. Clithero [[6] fit a difference-based EZ-diffusion model [8] 67 to the training data using Bayesian inference with non-informative priors, without imposing linear utility structure, and tested the model using the testing data.
In our work, we fit each participant's training data to difference- a linear utility structure, as described in section 2 and used the fitted model to simulate human feedback for bandit experiments. We preprocessed the data by removing outliers, following Clithero 16 footnote 22], excluding trials with response times below 200 ms or greater than five standard deviations above the mean. After cleaning, the number of trials per participant ranged from 167 to 170. Since the dataset does not provide feature vectors for the 17 non-reference snack items, we used one-hot encoding to represent each snack item feature vector in IR= This allowed us to construct a bandit instance for each participant with a preference vector 0 E I an arm space Z C R 17 with |Z| = 17, and a query space X' {2 0: E Z} to represent comparisons with the reference snack. We applied Bayesian inference with non-informative priors [16] to estimate each participant's 's preference vector 8*, non-decision time foonde,, and barrier Across participants, the barrier a ranged from 0.759 to 1.399, with a mean of 1.1, and momdee ranged from 0.139 to 0.485 seconds, with mean of 0.367 seconds.
EZ-diffusion model with
For each of the six GSE variations (introduced in section 5.2 (Aurans PCHLDT), (Auans CCHBTT
(Aurams; dcn); (Nweak: bcu). (Aarams OCILooii). ), and (Aurans: OCHLDT.OO)) ). we tuned the elimination param- using the following procedure: We considered E [2, 4,5,, 6, 7,8,7881 8,9), 9}.
eter in algorithm| [
resulting in the number of phases == [log,, |2|] = [log,, (17) (line of algorithm ! being (5,3,3, 2, 2, 2, 2). respectively. We excluded 17 > [17/2] = 9. as those cases also result in 2 phases, the same as 77 E {5, 6, 7, 8,8.9) Then, for each 17. for each of the 31 bandit instances, and for each budget E {50, 75, 100, 125, 150, 200, 250, 300} seconds, we ran 50 repeated simulations per GSE variation under different random seeds, sampling human feedback from the fitted dEZDM. We then aggregated the results into a single best-arm identification error probability for each GSE variation, 17, bandit instance, and budget. These error probabilities were compiled into violin and box plots, as shown in fig. 6
For each GSE variation, we selected the v that minimized the median error probability, as shown in the box plots in fig. If multiple 7) values yielded the same median, we used the third quartile, and if necessary, the first quartile, to break ties. Based on this approach, we selected: n 6 for (Arranss OCH.DT), ), 7) for (Arrans; (CH.RT), 17- for (Aurnss OCH), 1) = 9 for (Aweaks OCH). " = 9 for (Aarons: (CH.logu). and 17 = 5 for (Auans OCH.DT.ogit).
After tuning 7, we manually set the buffer size Buuff in algorithm I to 10 seconds based on empirical results, ensuring the budget was not exceeded in any phase. We then benehmarked each GSE variation on all 31 bandit instances using its own manually tuned 17 and B Each variation was evaluated over 300 repeated simulations with different random seeds, where human choices and response times were sampled from the dEZDM with the identified parameters. The full results are shown in fig. with selected results presented fig. 4b
30

---

1.0
Error probellllity P
Eirar probebility
0.6
0.4
0.2
0.2
0.0
0.0
2
3
8
9
2
3
6 Elimination parameter !)
Elimination parameter
(a) (Juruss (CHDTT)
(b) (Aurnna, OCuRT).
1.0
1.0
8
8-0.8
p
0.6
0.6
Estor probablity
0.4
0.4
0.2
0.2
0.0
0.0
2
9
3
Elimination parameter
Elimination parameter 1)
(c) (Awesks OCH).
(d) (Aaanss BCH). ).
Eror polehiiity F|3 *
18
Eror proteliity
2
Elimination parameter
Elimination parameter
(e) (Aues, OeHaga))
(0) (Auran, OCHDTAOgi)
Figure Violin plots overlaid with box plots, used for tuning the elimination parameter 1) in algorithm [ for each GSE variation, simulated based on the snack dataset with choices (yes or no) 16), as discussed in appendix [D.] Each plot shows the best-arm identification error probability, + as function of 1). The box plots follow the convention of the matplotlib Python package. The horizontal line each box represents the median of the error probabilities across all bandit instances and budgets. Each eтror probability is averaged over 50 repeated simulations under different random seeds. The top and bottom borders of box represent the third and first quartiles, respectively, while the whiskers extend to the farthest points within 1.5x the interquartile range. Flier points are the outliers past the end of the whiskers.
31

---

Puuaa Pessbaa)
Ohnasa Rea)
Poraa Rea))
Chean Penarr
Duean Rasaee)
Duna POLDTSSR)
1.0
Dioce probaMiity d 4
0.8
0.4
0.2
0.0
50
75
150
Buudggt (see)
Figure 7: A violin plot overlaid with box plot showing the best-arm identification error probability, [ * 2*], function of budget for each GSE variation, simulated using the snack dataset with choices (yes or no) [6), as described in appendix D.3 The box plots follow the convention of the matplotlib Python packagel For each GSE variation and budget, the horizontal line in the middle of the box represents the median of the error probabilities across all bandit instances. Fach error probability is averaged over 300 repeated simulations under different random seeds. The box's upper and lower borders represent the third and first quartiles, respectively, with whiskers extending to the farthest points within 1.5x the interquartile range. Flier points indicate outliers beyond the whiskers.
32

---

D.4 Processing the snack dataset with choices (-1 or 1) 39
We accessed the snack dataset with choices (-1 or package at httpps:/wwwl aeaweb org/ httaaarriccsssiidea 10. 1257 aer 20150742 This dataset contains choices and response times from 39 participants, each responding to between 49 and 100 queries comparing two snack items. Participants' eye movements were tracked during the experiment. Krajbich al. 39 modeled each participant's choices, response times, and eye movements using the attentional DDM, where the drift for each query is linear combination of the participant's 's ratings of both snack items in the query, with the weights influenced by their eye movements. The ratings, -9.... .,..., 9, 10), were collected before participants interacted with the binary queries.
via Fudenberg et al. [27 replication
In our work, avoid creating trivial bandit problems by encoding snack items as I-dimensional vectors (as done in appendix D.2,, we defined the feature vector for each snack item with participant rating T== {-10,- .......
9, 10} as a one-hot vector in R21, where the (r, + 11)-th element is 1 and the rest are O. The preference vector 0* is structured as 3 [-10, - ........ O,... ,, 10] _ E R221, where 88 is participant-specifi and unknown to the learner. This ensures that, for each arm 2, the participant's 's utility u, 0 T r=33". In this way, each participant's 's data generated bandit
instance with a preference vector 0 E R a set of arms Z C R22 with |Z| = 21, and a query space X z': z E Z}.
We fit each participant's 's data to a difference- EZ-diffusion model 8 67 using the linear utility structure described above. For each participant, using Bayesian inference with non-informative priors [16]. we estimated the preference vector 8" (or equivalently. the parameter 3²), non -ec-iiciionn time moondec, and barrier Across participants, the barrier ranged from 0.75 2. 2.192 with a mean of 1.335, and fomdee ranged from 0.387 to 1.22 seconds with a mean of 0.641 seconds. We then used these fitted models simulate human feedback for bandit experiments, assuming the learner did not know the underlying structure 0* = 3 10, -9,... 0, ,,,......1.. 10 For each of the following GSE variations (introduced in section 5.2 (Auans θCH.DT), (Auans OCHETT)
(Auanss (CH). (Dweak. dCH), (Auams: (CHLooois and (Aurams (CH,DT. ), tuned the elimination parame- ter in algorithm Jsing the following procedure: We considered 17 E {2, 3, 4, 5, 6, 7,8, 9, 10, 11}, which resulted in the number of phases == [log,, |2]] = [log,, (17) (line of algorithm 1 being 3,,3,3 3, 2, 2, 2, 2, 2, 2, 2). respectively. We excluded cases where > [21
11, as these result in 2 phases, identical to when 7) E {5, 6, 7, 8, 9, 10, 113. Then, for each 17. for each of the 39 bandit in- stances, and for each budget E {150, 200, 250, 300, 350, 400, 450, 500} seconds, we ran 50 repeated simulations per GSE variation under different random seeds, sampling human feedback from the fitted dEZDM. We then aggregated the results into a single best-arm identification error probability for each GSE variation, 17. bandit instance, and budget. These error probabilities were compiled into violin and box plots, as shown in fig.
For each GSE variation, we selected the 7) that minimized the median error probability, shown in the box plots in fig. 8 If multiple 7) values yielded the same median, we used the third quartile, and if necessary, the first quartile, to break ties. Based on this approach, we selected: n 4 for 4 for (Auanss θcH). 17 = 2 for (Aweak, den), 17 5 for
(Durans: (CH.DT), ) 7) 4 for (Nrrams: (CH,RT), (Aarans: HCH.og))) ). and 1) = 5 for (Mirnns (CH.DT..ogi)
After tuning 7, we manually set the buffer size Buuff in algorithm I to 20 seconds based on empirical results, ensuring the budget was not exceeded in any phase. We then benchmarked each GSE variation on all 39 bandit instances using its own manually tuned Each variation was evaluated over 300 repeated simulations with different random seeds, where human choices and response times were sampled from the dEZDM with the identified parameters. The full results are shown in fig. 9 with selected results presented in fig. 4c
33

---

0.0.8
Eirar probebility P
Error probelalitty P
0.6
0.4
0.2
0.2
0.0
0.0
3
8
10
11
3
5
7
9
10
11
Elimination paramette
Elimination parameten
(a) (Jurss OCHDTT). )-
(b) ( (Arans, OCuRT).
1.0
1.0
1-..8
1-0.8
Ento pobabiiity P
0.6
0.6
Entor pobablits
0.4
0.4
0.2
0.2
0.0
10
9
Elimination parameeter
Elimination parameter 1)
(c) (Awesks OCH).
(d) (Aaans BCH) ).
Eror polehhiity F/ 141
Erar prolehiity
3
11
Elimination parameter
Elimination parameter
(e) (Aunss OeHagaa)
(0 (Aram,, OCHDTIOgi)
Figure Violin plots overlaid with box plots, used for tuning the elimination parameter n in algorithm for each GSE variation, simulated based on the snack dataset with choices (-1 or 1) 39 as discussed in appendix D.4 Each plot shows the best-arm identification error probability, [2 2*] as function of 17. The box plots follow the convention of the mmtplotlii Python package. The horizontal line in each box represents the median of the error probabilities across all bandit instances and budgets. Each error probability is averaged over 50 repeated simulations under different random seeds. The top and bottom borders of the box represent the third and first quartiles, respectively, while the whiskers extend to the farthest points within 1.5x the interquartile range. Flier points are outliers past the end of the whiskers.
34

---

Dunaa Peasaa)
Ohnasa Rea)
Poraa Rea)
Chran Penarr
Queao Rawee)
Dioce prokaMiit e
0.8
0.4
0.2
0.0
150
Buudgget
(see)
Figure 9: A violin plot overlaid with box plot showing the best-arm identification error probability, [ * 2, function of budget for each GSE variation, simulated using the snack dataset with choices (-1 or 1) [39], as described in appendix D.4 The box plots follow the convention of the matplotlib Python package) For each GSE variation and budget, the horizontal line in the middle of the box represents the median of the error probabilities across all bandit instances. Fach error probability is averaged over 300 repeated simulations under different random seeds. The box's upper and lower borders represent the third and first quartiles, respectively, with whiskers extending to the farthest points within 1.5x the interquartile range. Flier points indicate outliers beyond the whiskers.
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the key contribution, that incorpo- rating response times in preference learning, and align with the paper's scope and findings.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed in section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
36

---

All assumptions are stated within theorems, and full proofs are provided in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer:[Yes)
The full algorithm is detailed in algorithm I and implementation details, including dataset conversions to bandit instances, are provided in section 5 and appendix D
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
37

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We will release code with instructions reproduce the results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ priips.cc/publicc/uuieee CoodeSumeeieeeeee ssi iessonPolll mollicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Implementation details, hyperparameter tuning, and procedures for data processing and conversion to bandit instances are provided in appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Key empirical results (fig. use violin and box plots to visualize variability, and clarify sources of randomness the text.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
38

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Details on compute resources are provided in appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't I make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We reviewed the NeurIPS ethics guidelines and adhered to them throughout the research process.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Societal impacts are discussed in appendix A
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
39

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not release data or models prone to misuse but focuses on estimation methods for preference learning. Potential societal impacts are discussed in appendix A
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite original papers and sources for code and datasets (section and appendix D
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
40

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We will release code with detailed documentation and an appropriate license.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This work does not involve crowdsourcing human-subject research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing or human-subject research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
41

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
42


Reviews:
[{"review_id": "3aFt6Omqkb", "reviewer": "Reviewer_f1Vk", "summary": "This paper studies whether leveraging human response times can lead to better performance in bandit learning from preference feedback. More specifically, the paper integrates the drift-diffusion model (DDM) from psychology into the best-arm identification problem in linear bandits. Given a fixed interaction time, the goal is to utilize response times alongside binary choices so as to maximize the probability of recommending the optimal arm.\n\nThe paper introduces an estimator of the preference/reward vector using both binary responses and response times via linear regression. This estimator can be incorporated into bandit algorithms. Asymptotic normality results and three simulations indicate that this new estimator leveraging response times can make easier queries more useful, in comparison with traditional estimators that only use binary responses.", "questions": "See above for questions on related work.\n\nI am also curious -- the estimator that uses only binary responses essentially assumes the Bradley-Terry model, if my understanding is correct. Looking at the logistic sigmoid function, I can see that the when $x^\\top \\theta^*$ is away from 0, the curve becomes flat and therefore not much information can be gained here. Have you considered other noise models that do not use a link function like the logistic sigmoid function? Would you expect similar behavior?", "limitations": "Limitations have been discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The studied problem seems novel, interesting, and relevant to the community. To my knowledge, DDMs have not been (widely) explored in bandits and reinforcement learning, although I am not very familiar with the DDM literature in psychology and neuroeconomics. This model may be of particular interests to researchers studying dueling bandits and RLHF. \n\n- The model leads to a simple and clean estimator of human preferences $\\theta^*$, which uses both binary preference feedback and response times. To my understanding, this estimator can be integrated into various bandit algorithms, not limited to ones for best-arm identification.\n\n- The paper presents both theoretical and empirical evidence on the role of response times, and discusses the intuition behind when/why they can be useful.\n\n- The paper is well-organized and well-written. It is a joy to read.", "weaknesses": "- It would be helpful to see more discussion on related work, especially on DDMs and race models. For example, what evidence has been given in the psychology literature that DDMs can explain the human decision-making process? What are the typical objectives in papers that study DDMs, and how are they different from the best-arm identification problem in this work? Have DDMs been considered in bandits and reinforcement learning?\n\n- On the theoretical side, there are no non-asymptotic results regarding the performance of the bandit algorithm, such as bounds on the error probability.\n\n- On the empirical side, only one dataset contains the response times of the participants. The last two experiments simulate response times according to the DDM -- it is reasonable to expect that they are then useful to estimating $\\theta^*$. The algorithm also has a hyperparameter that requires tuning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and thoughtful review. We appreciate your recognition of the novelty of our work and positive feedback on the writing. Here are our responses to your concerns and questions:\n\n## Weakness: non-asymptotic result\nIn our paper draft, we provide asymptotic theoretical results to show the following intuition on why response time can improve the learning performance:\n\n*Combining response times  and choices, information from easy queries can be extracted more efficiently. This is not possible using choices only.*\n\nWe added non-asymptotic error probability on estimating reward $x^{\\top}\\theta^*/a$ for every query $x$ using both methods, i.e. combining response times with choices and using choices only. Similar intuition can be confirmed as is shown in the `Author Rebuttal' section.\n\nWe leave for future work to provide non-asymptotic error probability for the entire algorithm (Algoithm 1 in the paper).\n\n## Weakness: real-world empirical result\nWe included a new simulation study based on another dataset of human choices and response times in the `Author Rebuttal` section. This study shows that incorporating response times improves best-arm identification performance.\n\n## Weakness+question: background of DDM models\nWe plan to include the following summary of DDM literature in the appendix:\n\n#### 1. Literature on modeling choices and response times\nBounded accumulation models (BAMs) capture the human decision-making process with an accumulator and a stopping rule. For binary choices, DDM [1] models the human's speed-accuracy trade-off with one accumulator, fixed barriers, random starting points, drift, and non-decision times. Our paper adopts EZ-DDM [3], a simplified version with deterministic parameters.\nDDM with time-decaying barriers theoretically connects to human Bayesian RL models [5].\nDDMs also characterize human attention during decision-making, by modeling choices, response times, and eye gazes on options or attributes [7].\nRace models [4] extends to queries with more than two options by assuming an accumulator for each option and stopping when any accumulator reaches its threshold.\nNeurophysiological evidence supports BAMs. EEG recordings show neurons exhibit accumulation processes and decision thresholds [2][6].\n\n\n#### 2. Literature on using response times (survey [10])\nResponse times improve choice prediction. [8] showed the full DDM predicts choice probabilities better than the logit model. [9] proved that response times could enhance the identifiability of human preferences, compared to choices alone.\n\nAnother application of response times is enhancing AI agents' decision-making. Dueling bandits and preference-based RL [14] typically use human choice models for preference elicitation. One popular choice model, the random utility model, can be derived from certain BAMs [9]. For example, both the Bradley-Terry model and EZ-DDM yield logistic choice probabilities (Eq.1 in our paper). To the best of our knowledge, **our work** is the first to leverage this connection to integrate BAMs within the framework of bandits (and RL). Note that our work lets the AI agent use RL to make decisions, which is different from [13] which models the human as an RL agent.\n\n- [[1] Ratcliff and McKoon 2008](https://ieeexplore.ieee.org/abstract/document/6796810)\n- [[2] Webb 2019](https://pubsonline.informs.org/doi/abs/10.1287/mnsc.2017.2931)\n- [[3] Wagenmakers et al. 2007](https://link.springer.com/article/10.3758/bf03194023)\n- [[4] Usher and McClelland 2001](https://psycnet.apa.org/record/2001-07628-003)\n- [[5] Fudenberg et al. 2018](https://www.aeaweb.org/articles?id=10.1257/aer.20150742)\n- [[6] Ratcliff et al. 2016](https://www.cell.com/trends/cognitive-sciences/abstract/S1364-6613(16)00025-5)\n- [[7] Krajbich 2019](https://www.sciencedirect.com/science/article/abs/pii/S2352250X18301866)\n- [[8] Clithero 2018](https://www.sciencedirect.com/science/article/abs/pii/S0167268118300398)\n- [[9] Alós-Ferrer et al. 2019](https://www.journals.uchicago.edu/doi/full/10.1086/713732)\n- [[10] Clithero 2018.](https://www.sciencedirect.com/science/article/abs/pii/S0167487016306444)\n- [[13] Pedersen et al. 2017](https://link.springer.com/article/10.3758/s13423-016-1199-y)\n- [[14] Bengs et al. 2021](https://www.jmlr.org/papers/volume22/18-546/18-546.pdf)\n\n## Question: about other link functions that models human choices\nFirst, the EZ-DDM model's marginal distribution for choices (Eq.1 in our draft) coincides with the Bradley-Terry model. Therefore, we have adopted the logistic link function to form a fair comparison.\n\nSecond, let's explore beyond the logistic link function. Suppose that the choice probability $\\mathbb{P}[z_1\\succ z_2]=\\sigma(u_{z_1},u_{z_2})$, where $\\sigma$ is a link function depending on the utilities $u_{z_1}$ and $u_{z_2}$. If we fix $u_{z_2}$ and only vary $u_{z_1}$, the function $\\sigma(\\cdot,u_{z_2})$ is known as a psychometric function, typically \"S\" shaped (see Fig.1.1 in [2]). This \"S\" shape means that as the human's preference strength becomes very large or very small, $\\sigma(\\cdot,u_{z_2})$ becomes flat and less informative, as you mentioned. In these circumstances, response times can be very helpful.\n\nLastly, if we further assume that $\\sigma$ depends only on the utility difference, $u_{z_1}-u_{z_2}$, this $\\sigma$ becomes the link function commonly adopted in the preference learning literature. According to Sec.3.2 of [1], the usual assumptions are that $\\sigma$ is strictly monotone in $(u_{z_1}-u_{z_2})$ and bounded within $[0, 1]$. Thus, as the utility difference becomes very large or very small, $\\sigma(u_{z_1}-u_{z_2})$ becomes flat, so the same intuition holds.\n\n- [[1] Bengs et al. 2021](https://www.jmlr.org/papers/volume22/18-546/18-546.pdf)\n- [[2] Stochastic Choice Theory, Econometric Society Monograph](https://scholar.harvard.edu/sites/scholar.harvard.edu/files/tomasz/files/manuscript_01.pdf)", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "nsIj9bym77", "reviewer": "Reviewer_qjfL", "summary": "The submission proposes to use response times to obtain additional information from participants in preference learning settings. They apply a variant of the Drift-Diffusion Model, a popular model of human decision making from psychology, and combine it with an algorithm applicable to linear bandits. In asymptotic analysis and application to real data, they demonstrate the benefits of taking advantage of response times, especially for queries with large value differences.", "questions": "* Why should choice-only would ever do better asymptotically. L186 makes this claim w.r.t. section 3.2 but I don't see it in the figure -- the orange lines (dashed or solid) seem always above the gray lines. \n* For figure 2, if possible it should be moved below section 3.2., so that it can be interpreted after the asymptotic min-weight of both estimators has been discussed. This is also the part of the submission which is most confusing -- mental calisthenics are needed to map from asymptotic min-weight to the variance of theta estimates and therefore to the influence of observations at various value differences. Another editing / clarification pass could be helpful. \n\nAdditional notes: \n* All figure axis tick labels are very tiny, should ideally be larger. In addition, adding color legends in fig 4 (outside the caption) would help with readability.", "limitations": "Discussed and addressed, even with additional analyses (and as noted above, the limitation regarding nondecision time might be possible to work around, though I could be missing something there).", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "I think this is a very sensible approach to improving preference learning, considering the fact that response times can be available \"for free\" from existing preference learning paradigms. I also think the application of a simplified variant of the DDM (EZ-Diffusion) as a way to get an analytic handle on things is also a good idea, and I think the results are compelling. It's a good paper, and I enjoyed reading it.", "weaknesses": "* I think the paper slightly misrepresents the actual model it's using. Unless I'm missing something, the DDM is usually defined as the first passage time of a two-boundary Wiener process, and the likelihood of a RT under that model involves solving an SDE which has no closed-form solution. However, moments of the DDM RT distribution are available, which is what enables approaches that use them to approximately solve for parameters (this includes the E-Z Diffusion model of Wagenmakers et al., the current contribution (as far as I can tell), as well as the related work of Shvartsman et al. 2023 (arxiv:2306.06296). I think using E-Z diffusion type approaches is great, I just think the paper shouldn't represent them as the full DDM. Also note that the E-Z diffusion line of work provides for closed-form estimation of nondecision time (by estimating drift (i.e. value difference) based on response time variance, and then backing into the response time mean from there -- this might help address the issue of unknown nondecision time identified by the authors. \n* Related to the above, moving away from the simplifying assumption of E-Z diffusion would introduce the concern of other unknown DDM parameters such as drift variability, nonsymmetrical initial conditions, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and positive review. We appreciate your constructive feedback and are glad you enjoyed the paper. We will reorganize the theoretical sections and figure presentation as suggested.\n\n## Weakness: about EZ-DDM vs DDM and EZ-DDM's assumptions\nThank you for pointing out the distinction between DDM and EZ-DDM [1]. We will ensure that our language in the paper accurately reflects this difference. Our work indeed adopts the assumptions of EZ-DDM, including deterministic starting points (zero-valued), drift, and non-decision time. Lifting these assumptions within the bandit framework could be a fruitful direction for future research.\n\nAs mentioned, our work assumes known non-decision time for simplicity. We appreciate your reference to EZ-DDM's procedure for estimating non-decision time (Eq.9 of [1]), and we agree that integrating this method with our approach is a promising avenue for future work. One reason we have not yet incorporated this method is that the estimation procedures in [1] and [2] treat each query’s non-decision time separately. In contrast, our work, following [3], assumes a common non-decision time across all queries. A potential future direction is to aggregate data across queries via the common non-decision time, similar to how we aggregate data in our current draft via the linear utility structure.\n\nTo compare our estimator with those in [1], consider the estimation of the drift $u_x$ for a query $x$. Our choice-and-response-time estimator (Eq. 4 in our draft) becomes the ratio of the expected choice and the expected response time. In contrast, [1]'s estimator (Eq. 5 in [1]) is based solely on the choices' log-odds, $\\log\\left(\\mathbb{P}(c_x=1)/(1-\\mathbb{P}(c_x=1))\\right)$. As our non-asymptotic analysis in `Author Rebuttal` indicates, our estimator can perform better for easy queries, while the choice-based estimator may be more effective for hard queries. When the utilities are parameterized linearly, our choice-and-response-time estimator is Eq. 4 in our paper draft, whereas [1]'s estimator becomes Eq. 5 in our paper draft. Our asymptotic analysis in Theorems 3.1 and 3.2 again highlights that using response times can be beneficial for easy queries.\n\n- [1] [Wagenmakers et al. 2007](https://link.springer.com/article/10.3758/BF03194023)\n- [2] [Berlinghieri et al. 2023](https://www.science.org/doi/10.1126/sciadv.adf1665)\n- [3] [Clithero (2018)](https://www.sciencedirect.com/science/article/abs/pii/S0167268118300398})\n\n## Question: why choice-only could perform better asymptotically?\nGiven some arm $y\\in\\mathcal{Z}$, we use asymptotic variance to measure how much the estimated utility $y^T\\widehat{\\theta}$ varies around the true utility value $y^T\\theta^*$ when the sample size is very large. Our goal is to compare the asymptotic variance of the choice-response-time estimator to that of the choice-only estimator.\n\nBoth estimators' asymptotic variances depend on how much information the estimator retain from the data, i.e. human responses to queries $x\\in \\mathcal{X}\\_{sample}$.\nThe choice-response-time estimator and the choice-only estimator retain different aspects of information from $x$. Intuitively, choices retain the \"sign\" of the utility difference $x^T\\theta^*$, while response times retain the preference strength. The \"amount\" of information they retained is formally presented as the weights $\\mathcal{M}\\_{CH,DT}$ and $m_{CH}$ in Theorems 3.1 and 3.2, respectively. Higher values of these terms indicate more retained information, leading to lower variance and better estimation.\n\nWe compare the weights $\\mathcal{M}\\_{CH,DT}$ and $m_{CH}$ in Theorems 3.1 and 3.2. The choice-only estimator assigns each query $x$ a weight $m_{CH}(x^T\\theta^*)$, represented by the gray curve in Figure 2. In contrast, the choice-response-time estimator assigns all queries the same weight $\\mathcal{M}\\_{CH,DT}\\coloneqq\\min_{x}m_{CH,DT}(x^T\\theta^*)$, with $m_{CH,DT}(x^T\\theta^*)$ plotted as the orange curve in Figure 2.\n\nWhile the orange curve is consistently higher than the gray curve, indicating that $m_{CH,DT}(x^T\\theta^*)>m_{CH}(x^T\\theta^*)$ for each query $x$, the choice-response-time estimator's weight is $\\mathcal{M}\\_{CH,DT}$, not $m_{CH,DT}(x^T\\theta^*)$. Consequently, $\\mathcal{M}\\_{CH,DT}$ may be larger or smaller than $m_{CH}(x^T\\theta^*)$ depending on the queries in the data.\nFor instance, if the data contains both hard queries where $x^T\\theta^*\\in[-1,1]$ and one easy query where $x^T\\theta^*=4$, the choice-response-time estimator will have small weights for all queries due to the \"min\" in the definition of $\\mathcal{M}\\_{CH,DT}$, while the choice-only estimator will have large weights for hard queries even if the easy query exists. In this scenario, the choice-only estimator may perform better. Conversely, if the data only contain easy queries, the choice-response-time estimator will have a larger weight, making it superior.\n\nFinally, we would like to note that the \"min\" in the definition of $\\mathcal{M}\\_{CH,DT}$ is a result of our proof techniques. It is possible to obtain tighter theoretical analysis, and we leave it for future work.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "hAOysYOfOi", "reviewer": "Reviewer_a7WX", "summary": "The paper studies linear bandit preference learning, where binary preference data have been augmented with response times. A joint model for choice and response time falls from setting the linear preference model as the drift parameter in a drift-diffusion model. Experiments and theoretical analysis show that including response time in the model increases the value of \"easy\" responses, and thus improves bandit performance.", "questions": "On the topic of real human response time data, should we expect the model to be robust to lapses, or would some sort of data pre-processing be necessary to remove those?", "limitations": "Addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written. Including response time in a linear bandit preference model is novel to my knowledge, and certainly useful. The development of the method is clear, and the method itself is well-motivated and seems computationally reasonable and useful. The theoretical analysis is helpful, and I really appreciated how the paper uses that analysis to draw insights into the source of improvement from including response times in the model. The experiments were well-designed, and included the necessary baseline of choice-only. The analysis of the experiments provides helpful guidance for the situations in which the method does not outperform baselines.", "weaknesses": "The paper has one significant weakness: all of the experiments use simulated response times, simulated from the model developed in the paper. We thus don't get a sense for the \"real-world\" performance of the method, where response times will not adhere precisely to the DDM model. I agree with the paper that response time is easy to collect alongside binary preferences. Surely there are some datasets available that include actual human response times? Real human response times are the big missing piece of the experimental evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive and constructive review; we appreciate your feedback and recognition of our work's novelty and usefulness.\n\n## Weakness: real-world empirical result\nWe acknowledge the importance of using real-world data for evaluation. Below is the rationale behind our simulator-based study and additional results using a different human dataset, as detailed in the `Author Rebuttal` section.\n\nFirstly, our bandit algorithm is an online algorithm, requiring us to sample response times of different queries online adaptively. Existing offline datasets are not collected adaptively, and is hard to be used for evaluating our algorithm. Although, there exist offline policy evaluation methods[2] that evaluate online algorithms with offline data, they require extensive data from a single user. Unfortunately, we have not been able to find such large-scaled datasets for response times.\n\nSecondly, online collecting response time data can suffer from outliers due to human inattention or anticipation [1]. Successful studies may require integrating data cleansing techniques [1] into online algorithms, which we consider as a separate contribution in future work.\n\nTherefore, in our work, we adopt a third approach: training a simulator from real-world data and then using the simulator to evaluate algorithms. This approach assumes that the EZ-DDM is the ground truth model, which is a reasonable assumption given the empirical support for this model [3]. We believe this approach justifies our insights—using response times makes easy queries more useful—while leaving a full user study for future work.\n\nWe have included a new simulation-based study using another dataset of human choices and response times in the `Author Rebuttal` section. This study confirms that incorporating response times improves best-arm identification performance.\n\n- [[1] Myers et al. 2022](https://www.frontiersin.org/journals/psychology/articles/10.3389/fpsyg.2022.1039172/full)\n- [[2] Li et al. 2010](https://dl.acm.org/doi/abs/10.1145/1772690.1772758?casa_token=RuMgk8seZScAAAAA:YyJgdyVIfKDBquZ8uuDO-RAg3kK3vVmu-3Drco_J8CCUxYJXGgg2TCUepSwV6UvWqU4hYbpNwDTbVg)\n- [[3] Wagenmakers et al. 2007](https://link.springer.com/article/10.3758/bf03194023)\n\n## Question: about lapses and data processing\nIn general, there are two types of lapses: 1) lapses at the very beginning of the decision process; 2) lapses, or distractions, in the middle of the decision process. The first type of lapse can be interpreted as the non-decision time in the EZ-DDM model. The appendix includes our discussions about the issue of unknown non-decision times. Future work could involve estimating non-decision times from data.\n\nThe second type of lapse occurs when humans lose attention or get distracted during the decision process, resulting in very long response times. Alternatively, humans might anticipate the current trial based on previous trials, leading to very short response times [2]. To handle such outliers in real-world datasets, a common procedure is to define cut-off thresholds to eliminate very short and very long response times [2]. Additionally, human attention can be monitored using eye-tracking devices. There is a line of psychological literature [1] that tracks human eye gazes during decision-making and incorporates human visual attention within the DDM framework.\n\nAnother important procedure for handling real-world response time data is to test whether DDM is an appropriate model for a given dataset. There is literature on statistically testing whether observed response time data is generated by DDM [3][4].\n\n- [[1] Krajbich 2019](https://www.sciencedirect.com/science/article/abs/pii/S2352250X18301866)\n- [[2] Myers et al. 2022](https://www.frontiersin.org/journals/psychology/articles/10.3389/fpsyg.2022.1039172/full)\n- [[3] Alós-Ferrer et al. 2021](https://www.journals.uchicago.edu/doi/full/10.1086/713732)\n- [[4] Fudenberg et al. 2020](https://www.pnas.org/doi/abs/10.1073/pnas.2011446117)", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "6GmAOb6zws", "reviewer": "Reviewer_64dM", "summary": "The paper explores the interactive preference learning problem.\nTraditional binary choice feedback is limited in conveying preference strength. \nThe authors propose leveraging human response time, which inversely correlates with preference strength, as additional information. \nThey adopt the difference-based Drift-Diffusion Model with linear human utility functions and propose a computationally efficient linear utility estimator that incorporates human response times.\nDiscussions about the proposed estimator and traditional estimators relying on the logistic regression are provided.\nThe authors also integrate the proposed estimator into the Generalized Successive Elimination(GME) algorithm for the fixed-budget best arm identification problem.\nThe proposed method is evaluated on both synthetic and real-world datasets, demonstrating the effectiveness of incorporating human response times for essay queries.", "questions": "Please refer to the weaknesses mentioned above.", "limitations": "Limitations are adequately discussed in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea of incorporating human response times is novel and interesting. The authors provide a clear motivation to incorporate human response times, give illustrative examples to illustrate the benefits and explain their methods in detail.\n- The paper is well-written and easy to follow. The background, methods, and experiments are well-organized and well-explained.\n- The authors clearly discuss the effects of parameters $x^T\\theta^{*}$ and $a$, and compare the estimator with and without response times, which provides a good understanding of the proposed method.\n- The authors conduct extensive experiments on both synthetic and real-world datasets, and provide a detailed analysis of the results about the estimation performance and identification performance. The methods to pre-process the datasets and determine the parameters are also well explained.", "weaknesses": "- Although the authors provide the asymptotic analysis for their estimators, they do not provide a theoretical analysis for the proposed algorithm.\n- As mentioned in the paper, when the barrier $a$ is small, incorporating response times may not improve estimation performance. Since the parameter $a$ is also unknown, like $\\theta^{*}$, learners may not know whether to incorporate response times. It would be beneficial if the authors could have a discussion about the practical choice of the estimator under these conditions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and thoughtful review, and for recognizing the novelty and clarity of our work.\n\n## Weakness: algorithm analysis\nIn our paper draft, we provide asymptotic theoretical results to show the following intuition on why response time can improve the learning performance:\n\n*Combining response times  and choices, information from easy queries can be extracted more efficiently. This is not possible using choices only.*\n\nWe added non-asymptotic error probability on estimating reward $x^{\\top}\\theta^*/a$ for every query $x$ using both methods, i.e. combining response times with choices and using choices only. Similar intuition can be confirmed as is shown in the `Author Rebuttal' section.\n    \nWe leave for future work to provide non-asymptotic error probability for the entire algorithm (Algoithm 1 in the paper).\n\n## Weakness: practical usage of response time when $a$ is unknown\nOne straightforward approach is to always incorporate response times:\n1. Based on our empirical results, it seems that incorporating response times, if not improving the performance, rarely degrades performance.\n2. Our theoretical and empirical results indicate that when queries are very difficult for humans to answer, incorporating response times may be less beneficial and could slightly decrease performance. However, in these scenarios, humans typically don’t have strong preferences, so they might be more tolerant of the minor performance impact caused by using response times.\n\nAlternatively, one can first incorporate response times to filter out many suboptimal options, and then use choice-only estimation for further learning. In the first stage, both good and bad arms exist. In this case, many queries, composed of one good arm and one bad arm, are easy and response times help extract more information from those easy queries. In the second stage, most arms will be similarly good. In this case, the queries are harder and choice-only estimation is sufficient to identify the best arm. Determining the optimal point to switch from using response times to relying solely on choices is an area for future research.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:
We address the two major concerns raised by multiple reviewers: the limited use of real-world datasets and the lack of non-asymptotic results.

## 1. New Simulation on a Real-world dataset
We present new simulation results based on another real-world response time dataset. This dataset [1] contains human binary choices and response times. In each query, each arm consists of two food items, and the human has an equal chance of obtaining either item after choosing that arm. For each user, we construct a bandit instance where the feature vector for each arm is composed of the user's ratings of the food items, augmented via second-order polynomials. For each user, an EZ-DDM is identified via Bayesian MCMC and then used as a simulator to generate human feedback. We compare the best-arm-identification errors over $100$ repetitions for three algorithms:
1. Transductive design with our choice-and-response-time estimator, denoted by $\left(\lambda\_{trans},\widehat{\theta}\_{CH,DT}\right)$.
2. Transductive design with a choice-only estimator, denoted by $\left(\lambda\_{trans},\widehat{\theta}\_{CH}\right)$.
3. Hard-query design with a choice-only estimator, denoted by $\left(\lambda\_{hard},\widehat{\theta}\_{CH}\right)$.

The results are plotted in Fig. 1 of our rebuttal PDF document. As shown, under various budgets and participant indices, incorporating response times (method (1), plotted in red) outperformed the other two methods.


## 2. New Non-asymptotic Analysis
We added lemmas stating non-asymptotic error probabilities on estimating the utility difference $x^{\top}\theta^*/a$ using both methods, i.e. combining response times with choices and using choices only. The results convey the same intuition as in the Thm. 3.1 and 3.2 in our draft:

*Response times make easy queries more useful. In other words, combining response times and choices, information from easy queries can be extracted more efficiently. This is not possible using choices only.*

We analyzed the non-asymptotic concentration for the utility difference estimated as the ratio between the empirical mean of choices and the empirical mean of response times, which appears on the right-hand side of Eq. 4 in our paper draft.
The error probability for such choice-and-response-time estimator is as follows:

**Lemma 1.** Consider any query $x\in\mathcal{X}$. For any scalar $\epsilon_r$ satisfying
\begin{equation}\begin{split}
    \epsilon_r \leq \min\left\\{\frac{x^{\top}\theta^*}{\sqrt{2}a}, \frac{(1+\sqrt{2})ax^{\top}\theta^*}{\mathbb{E}[t_x]}\right\\}
\end{split}\end{equation}
we have that
\begin{equation}\begin{split}
    \mathbb{P}\left(\left|\frac{\sum_{i\in[n_x]} c_{x,i}}{\sum_{i\in[n_x]} t_{x,i}} - \frac{x^{\top}\theta^*}{a}\right| > \epsilon_r\right)\leq 4\exp\left(-\frac{\left(\mathbb{E}[t_x]/(\sqrt{2}+2)\right)^2}{2} n_x\epsilon_r^2\right).
\end{split}\end{equation}


Alternatively, utility difference (or DDM drift) can be estimated using choices only (Eq. 5 in [1]). Converting $\mathbb{E}[c_x]\in[-1,1]$ to $\mathbb{E}[(c_x+1)/2]\in[0,1]$ and applying the logit function $h^{-1}(p)\colon=\text{logit}(p)=\log\left(p/(1-p)\right)$ estimates $2ax^{\top}\theta^*$.
The error probability for such choice-only estimator is as follows:

**Lemma 2.** Consider any query $x\in\mathcal{X}$. We have that
\begin{equation}\begin{split}
    \mathbb{P}\left(\frac{h^{-1}\left(\mathbb{E}[(c_x+1)/2]\right)}{2a^2}-\frac{x^{\top}\theta^*}{a} > \epsilon_r\right) \leq \exp\left(-\frac{\left(4a^2h'(2ax^{\top}\theta^*)\right)^2}{2}n_x\epsilon_r^2\right).
\end{split}\end{equation}
Here $h(x) = 1/\left(1+\exp(-x)\right)$.

For easy queries with $x^{\top}\theta^* \gg 1$, the factor $4a^2h'(2ax^\top\theta^*)$ in Lemma 2 is significantly smaller than factor $\mathbb{E}[t_x]/(\sqrt{2}+2)$ in Lemma 1. As a result, with $x^{\top}\theta^*\gg 1$, error probability of our estimation with both response times and choices is much smaller than that of the choice-only estimation.

The aforementioned two factors are plotted as functions of the utility difference $x^{\top}\theta^*$ in Fig. 2 of our rebuttal PDF document. Recall that this plot of non-asymptotic results looks similar to Fig. 2 (asymptotic results) in our paper draft. Indeed, they convey similar insights. In particular, When the human conservative parameter $a$ is small, for hard queries, the gray curve is slightly higher than the orange one, indicating that only using choices is slightly better. When $a$ is large, the gray curve is higher only for hard queries, while lower for easy queries. This conveys a similar insight as our Thm. 3.1 and 3.2, that using choice is better for hard queries, while using response time makes easy queries more useful.


- [[1] Wagenmakers et al. 2007](https://link.springer.com/article/10.3758/bf03194023)

Meta-review: The paper studies preference-based linear bandits in fixed-budget best-arm identification problem. The authors investigate the benefit of incorporating human response time which inversely correlates with preference strength. The authors propose to incorporate the drift-diffusion model (DDM) from psychology with an elimination-based solution.  The paper presents both theoretical and empirical results showing that incorporating response time makes easy queries more useful and thus improves overall performance.  The reviewers are unanimously positive, recognizing the motivation and novelty of introducing response time and appreciating the solid analysis and clear paper presentation. The reviewers' questions about real-world datasets and the non-asymptotic results are addressed by the rebuttal. I recommend acceptance of the paper. The authors are suggested incorporate the discussion and new results from the rebuttal into the final version.
Decision: Accept (oral)