Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
55,184 characters · 11 sections · 72 citation commands
Enhancing Preference-based Linear Bandits via Human Response Time
Interactive preference learning from human binary choices is widely used in recommender systems karimi2018news,silva2022multi,bogina2023considering,deldjoo2024content, assistive robots sadigh2017active,tucker2020preference, and fine-tuning large language models stiennon2020learning,menick2022teaching,nakano2021webgpt,ouyang2022training,bai2022training. This process is often framed as a preference-based bandit problem bengs2021preference,jun2021improved, 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 xu2017noise,wilde2021learning,koppol2021interaction. However, while binary choices reveal preferences, they provide little information about preference strength yu2023thumbs. To address this, researchers have incorporated additional explicit human feedback, such as ratings somers2017efficient,perez2019pairwise, labels xu2017noise, and slider bars wilde2021learning,bai2022training, but these approaches often complicate interfaces and increase cognitive demands koppol2020iterative,koppol2021interaction.
In this paper, we propose leveraging implicit human feedback, specifically response times, to provide additional insights into preference strength. Unlike explicit feedback, response time is unobtrusive and effortless to measure clithero2018response, offering valuable information that complements binary choices clithero2018improving,alos2021time. For instance, consider an online retailer that repeatedly presents users with a binary query, whether to purchase or skip a recommended product konovalov2019revealed. Since most users skip products most of the time karpov2022instance, the probability of skipping becomes nearly 1 for most items. This lack of variation in choices makes it difficult to assess how much a user likes or 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 clithero2018response: users who strongly prefer to skip a product tend to do so quickly, while longer response times can indicate 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 clithero2018response,de2019overview using complex models like Drift-Diffusion Models ratcliff2008diffusion and Race Models usher2001time,brown2008simplest. While these models align with both behavioral and neurobiological evidence webb2019neural, they rely on computationally intensive methods, such as hierarchical Bayesian inference wiecki2013hddm and maximum likelihood estimation (MLE) ratcliff2002estimating, to 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 wagenmakers2007ez,wagenmakers2008ez,grasman2009mean,fudenberg2020testing,berlinghieri2023measuring, they typically estimate the utility functions for a 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 li2010contextual,sadigh2017active,fiez2019sequential,silva2022multi,deldjoo2024content and in cognitive models for human multi-attribute decision-making trueblood2014multiattribute,fisher2017attentional,yang2023dynamic.
To address these challenges, we propose a computationally efficient method for estimating linear human utility functions from both choices and response times, grounded in the difference-based EZ diffusion model wagenmakers2007ez,berlinghieri2023measuring. 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 azizi2021fixed,jun2021improved. 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 linear-regression-based estimator integrates seamlessly into algorithms for preference-based bandits with linear human utility functions azizi2021fixed,jun2021improved, enabling interactive learning systems to leverage response times for faster learning. We specifically integrated our estimator into the Generalized Successive Elimination algorithm azizi2021fixed for fixed-budget best-arm identification gabillon2012best,kaufmann2016complexity. Simulations using three real-world datasets smith2018attention,clithero2018improving,krajbich2010visual 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 is the first work to integrate response times into bandits (and RL).
(ref) introduces the preference-based linear bandit problem and the difference-based EZ diffusion model. (ref) presents our utility estimator, incorporating both choices and response times, and offers a theoretical comparison to the choice-only estimator. (ref) integrates both estimators into the Generalized Successive Elimination algorithm. (ref) presents empirical results for estimation and bandit learning. (ref) discusses the limitations of our approach. (ref) reviews response time models, parameter estimation techniques, and their connection to preference-based RL.
Nomenclature: We use $[n]$ to denote the set $\{1,\dots,n\}$. For a scalar random variable $x$, the expectation and variance are denoted by $\bbE\qb{x}$ and $\bbV\qb{x}$, respectively. The function $\text{sgn}(x)$ denotes the sign of $x$.
\paragraph{Preference-based bandits with a linear utility function.} The learner is given a finite set of options (or “arms”), each represented by a feature vector in $\mathcal{Z}\subset\mathbb{R}^d$, and a finite set of binary queries, where each query is the difference between two arms, denoted by $\mathcal{X}\subset\mathbb{R}^d$. For instance, if the learner can query any pair of arms, the query space is $\mathcal{X}=\left\{z-z'\colon z,z'\in\mathcal{Z}\right\}$. In the online retailer example from (ref), the query space is $\mathcal{X}=\left\{z-z_{\text{skip}}\colon z\in\mathcal{Z}\right\}$, where $z$ represents purchasing a product and $z_{\text{skip}}$ represents skipping (often set as $\mathbf{0}$). For each arm $z \in \mathcal{Z}$, the human utility is assumed to be linear in the feature space, defined as $u_z\coloneqq z^\top\theta^*$, where $\theta^*\in\mathbb{R}^d$ represents the human's preference parameters. For any query $x\in\mathcal{X}$, the utility difference is then defined as $u_x\coloneqq x^\top\theta^*$.
Given a query $x\coloneqq z_1-z_2\in\mathcal{X}$, we model human choices and response times using the difference-based EZ-Diffusion Model (dEZDM) wagenmakers2007ez,berlinghieri2023measuring, integrated with our linear utility structure. (See (ref) for a comparison with other models.) This model interprets human decision-making as a stochastic process in which evidence accumulates over time to compare two options. As shown in (ref), after receiving a query $x$, the human first spends a fixed amount of non-decision time, denoted by $t_{\text{nondec}}>0$, to perceive and encode the query. Then, evidence $E_x$ accumulates over time following a Brownian motion with drift $x^\top\theta^*$ and two symmetric absorbing barriers, $a>0$ and $-a$. Specifically, at time $t_{\text{nondec}}+\tau$ where $\tau\geq 0$, the evidence is $E_{x,\tau}=x^\top\theta^*\cdot \tau + B(\tau)$, where $B(\tau)\sim\mathcal{N}(0, \tau)$ is standard Brownian motion. This process continues until the evidence reaches either the upper barrier $a$ or lower barrier $-a$, at which point a decision is made. The random stopping time, $t_x\coloneqq\min\left\{\tau>0\colon E_{x,\tau}\in\left\{a, -a\right\}\right\}$, represents the decision time. If $E_{x,t_x}=a$, the human chooses $z_1$; if $E_{x,t_x}=-a$, they choose $z_2$. The choice is represented by the random variable $c_x$, where $c_x=1$ if $z_1$ is chosen, and $-1$ if $z_2$ is chosen. The total response time, $t_{\text{RT}, x}$, is the sum of the non-decision time and the decision time: $t_{\text{RT}, x}=t_{\text{nondec}}+t_x$. The choice probability, expected choice, choice variance, and expected decision time are given as follows palmer2005effect:
This choice probability matches that of the BradleyTerry1952 model. If the learner relies solely on choices, then our bandit problem reduces to the transductive linear logistic bandit problem jun2021improved.
(ref) illustrate the roles of the parameters $x\t\theta^*$ and $a$. First, the absolute drift (or the absolute utility difference), $|x^\top\theta^*|$, reflects the human's preference strength for the query $x$. 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 conservativeness in decision-making lerche2017many. A more conservative human (higher $a$) requires more evidence to decide, resulting in slower but more consistent choices. In contrast, a less conservative human (lower $a$) decides faster but makes less consistent choices.
We adopt the common assumption that $t_{\text{nondec}}$ is constant across all queries for a given human clithero2018improving,yang2023dynamic and further assume that $t_{\text{nondec}}$ is known to the learner. This assumption enables the learner to perfectly recover $t_x$ from the observed $t_{\text{RT},x}$. In (ref), we empirically show that even when $t_{\text{nondec}}$ is unknown, its impact on the performance of our method that relies on decision times is negligible.
\paragraph{Learning objective: Best-arm identification with a fixed budget.} We focus on the fixed-budget best-arm identification problem gabillon2012best,kaufmann2016complexity. The learner is provided with a total interaction time budget $B > 0$, an arm space $\mathcal{Z}$, a query space $\mathcal{X}$, and a non-decision time $t_{\text{nondec}}$. Both the human's preference vector $\theta^*$ and the decision barrier $a$ are unknown. In each episode $s\in\mathbb{N}$, the learner selects a query $x_s\in\mathcal{X}$, receives human feedback $(c_{x_s,s},t_{x_s,s})$ generated by the dEZDM, and consumes $t_{\text{RT},x_s,s}$ time. When the cumulative interaction time exceeds the budget $B$ at some episode $S$, i.e., $\sum_{s=1}^S t_{\text{RT},x_s,s}>B$, the learner must stop and recommend an arm $\widehat{z}\in\mathcal{Z}$. The goal is to recommend the unique best arm $z^*\coloneqq\operatorname*{arg\,max}_{z\in\mathcal{Z}}z\t\theta^*$, minimizing the error probability $\mathbb{P}\left[\widehat{z}\neq z^*\right]$.
To address this problem, we adopt the Generalized Successive Elimination (GSE) algorithm azizi2021fixed,alieva2021robust,yang2022minimax. GSE divides the total budget $B$ into multiple phases. In each phase, it strategically samples queries until the phase's budget is exhausted, collecting both human choices and decision times. It then estimates the preference vector $\theta^*$ 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 $\theta^*$ than choices alone. Next, in (ref), we introduce a novel estimator that combines decision times and choices to estimate $\theta^*$. Then, in (ref), we discuss how this estimator is integrated into GSE to improve preference learning.
This section addresses the problem of estimating human preference $\theta^*$ from a fixed dataset, denoted by $\left\{x,c_{x,s_{x,i}},t_{x,s_{x,i}}\right\}_{x\in\mathcal{X}_{\text{sample}},i\in[n_x]}$. Here, $\calX_{\text{sample}}$ denotes the set of queries in the dataset, $n_x$ denotes the number of samples for each query $x\in\calX_{\text{sample}}$, and $s_{x,i}$ denotes the episode when $x$ is sampled for the $i$-th time. Samples from the same query $x$ are i.i.d., while samples from different queries are independent. (ref) introduces a new estimator, the “choice-decision-time estimator,” which uses both choices and decision times, in contrast to the commonly used “choice-only estimator” that only uses choices azizi2021fixed,jun2021improved. (ref) theoretically compares these estimators, analyzing both asymptotic and non-asymptotic performance and highlighting the advantages of incorporating decision times. (ref) presents empirical results that validate our theoretical insights.
The choice-decision-time estimator is based on the following relationship between human utilities, choices, and decision times, derived from (ref):
Intuitively, when a human provides consistent choices (i.e., large $|\mathbb{E}[c_x]|$) and makes decisions quickly (i.e., small $\mathbb{E}[t_x]$), it implies a strong preference (i.e., large $|x^\top \theta^*|$). This relationship formulates the estimation of $\theta^*$ 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 $\theta^*/a$. Since the ranking of arm utilities based on $\theta^*/a$ is identical to that based on $\theta^*$, estimating $\theta^*/a$ is sufficient for identifying the best arm. Formally, this estimate of $\theta^*/a$, denoted by $\widehat{\theta}_{\text{CH,DT}}$, is given by:
In contrast, the choice-only estimator is based on (ref), which shows that for each query $x \in \mathcal{X}$, the random variable $(c_x + 1)/2$ follows a Bernoulli distribution with mean $1/[1 + \exp(- x^\top\cdot 2a\theta^*)]$. Similar to the choice-decision-time estimator, the parameter $2a$ does not impact the ranking of arms, so estimating $2a \theta^*$ is sufficient for best-arm identification. This estimation is formulated as a logistic regression problem azizi2021fixed,jun2021improved, with MLE providing the following estimate of $2a \theta^*$, denoted by $\widehat{\theta}_{\text{CH}}$:
where $\mu(y)\coloneqq1/[1+\exp(-y)]$ is the standard logistic function. While this MLE lacks a closed-form solution, it can be efficiently solved using optimization methods like Newton's algorithm minka2003comparison,Filippi_NIPS2010_c2626d85.
The choice-decision-time estimator from (ref) satisfies the following asymptotic normality result:
The proof is provided in (ref). The asymptotic variance upper bound shows that all sampled queries are weighted by a common factor $\min_{x'\in\calX_{\text{sample}}} \bbE\qb{t_{x'}}$, which is the smallest expected decision time among all the sampled queries in $\calX_{\text{sample}}$. This weight represents the amount of information provided by each query's choices and decision times for utility estimation. A larger weight indicates that all queries in $\calX_{\text{sample}}$ provides more information, leading to lower variance and better estimates.
In contrast, the choice-only estimator from (ref) has the following asymptotic normality result, as derived from Fahrmeir85:
This asymptotic variance shows that each sampled query $x\in\calX_{\text{sample}}$ is weighted by its own factor $a^2\,\bbV\qb{c_x}$, 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 ((ref)), each query is weighted by $a^2\,\bbV\qb{c_x}$, which depends on the utility difference $x\t\theta^*$ for a fixed barrier $a$. As shown by the gray curves in (ref), this weight quickly decays to zero as preferences become stronger (i.e., as $|x^\top \theta^*|$ 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 it hard to 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 (ref).
For the choice-decision-time estimator ((ref)), queries are weighted by $\min_{x'\in\calX_{\text{sample}}} \bbE\qb{t_{x'}}$, which depends on both $\calX_{\text{sample}}$ and $\bbE\qb{t_x}$. To better understand this weight, we first plot $\bbE\qb{t_x}$ without the `min' operator as the orange curves in (ref). Comparing the orange and gray curves shows that $\bbE\qb{t_x}$ is generally larger than the choice-only weight, $a^2\,\bbV\qb{c_x}$. The actual weight in the choice-decision-time 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 strength, leading to improved estimation.
When queries have weak preferences, the choice-decision-time weight may be lower than the choice-only weight. However, since the choice-decision-time weight represents only an upper bound on the asymptotic variance ((ref)), no definitive conclusions can be drawn from the theory alone. Empirically, as shown in (ref), decision times add little value but do not degrade performance.
As the barrier $a$ 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 a narrower region, with weights decreasing elsewhere. Intuitively, a higher barrier reflects greater conservativeness in human decision-making, leading to longer decision times and more consistent choices ((ref)). As a result, more queries exhibit strong preferences, making choices from these queries less informative.
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 (ref). Extending this non-asymptotic analysis to the full estimation of the preference vector $\theta^*$ is left for future work.
Given a query $x\in\mathcal{X}$, the task is to estimate the utility difference $u_x\coloneqq x^\top\theta^*$ using the fixed i.i.d. dataset $\{(c_{x,s_{x,i}}, t_{x,s_{x,i}})\}_{i\in[n_x]}$. Applying the choice-decision-time estimator from (ref), we get the following estimate (for details, see (ref)), which estimates $\smash{u_x/a}$ rather than $\smash{u_x}$:
In contrast, applying the choice-only estimator from (ref), we get the following estimate (for details, see (ref)), which estimates $\smash{2a u_x}$ rather than $\smash{u_x}$:
where $(c_{x,s_{x,i}}+1)/2$ is the binary choice coded as 0 or 1, and $\mu^{-1}(p)\coloneqq\log\b{p/(1-p)}$ is the logit function (inverse of $\mu$ introduced in (ref)).
Notably, the choice-only estimator in (ref) aligns with the EZ-diffusion model's drift estimator wagenmakers2007ez. Moreover, the estimators in xiang2024combining and berlinghieri2023measuring combine elements of both estimators from (ref). In (ref), we demonstrate that both estimators from wagenmakers2007ez and xiang2024combining are outperformed by our proposed estimator in (ref) for the full bandit problem.
Assuming the utility difference $u_x \neq 0$, the choice-decision-time estimator in (ref) satisfies the following non-asymptotic concentration bound, proven in (ref):
In contrast, the choice-only estimator in (ref) has the following non-asymptotic concentration result, adapted from jun2021improved\footnote{In jun2021improved, we let $x_1=\cdots=x_t=1$ and $t_{\text{eff}}=d=1$.}:
The weights $m_{\text{CH,DT}}^{\text{non-asym}}(\cdot)$ and $m_{\text{CH}}^{\text{non-asym}}(\cdot)$ from (ref), respectively, are functions of the utility difference $x\t\theta^*$ for a fixed barrier $a$. These weights determine how quickly estimation errors decay as the dataset size $n_x$ grows, with larger weights indicating faster error 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 (ref). (ref) compares the weights for the choice-decision-time estimator (orange, $m_{\text{CH,DT}}^{\text{non-asym}}(\cdot)$) and the choice-only estimator (gray, $m_{\text{CH}}^{\text{non-asym}}(\cdot)$). For strong preferences, the choice-only weights quickly decay to zero, while the choice-decision-time 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 ((ref)) and non-asymptotic ((ref)) analyses demonstrate that the choice-decision-time estimator extracts more information from queries with strong preferences. This finding aligns with prior empirical work clithero2018improving and is further supported by our results in (ref).
In fixed-budget best-arm identification, our choice-decision-time estimator's ability to extract more information from queries with strong preferences is especially valuable. Bandit learners, such as GSE azizi2021fixed, strategically sample queries, update estimates of $\theta^*$, and eliminate lower-utility arms. With the choice-only estimator, learners struggle to 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) badanidiyuru2018bandits. Second, since $\theta^*$ is unknown in advance, learners cannot reliably target queries with weak preferences. In contrast, with our choice-decision-time 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 (ref) and evaluate their performance in (ref).
We introduce the Generalized Successive Elimination (GSE) algorithm azizi2021fixed,alieva2021robust,yang2022minimax 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 (ref).
The pseudo-code for GSE is shown in (ref). The algorithm uses a hyperparameter $\eta$ 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 $B_{\text{buff}}$, to prevent overspending in any phase ((ref)). In each phase, GSE computes an experimental design $\lambda$, a probability distribution over the query space, to guide query sampling. We consider two designs: the transductive design fiez2019sequential, $\lambda_{\text{trans}}$ ((ref)), and the weak-preference design jun2021improved, $\lambda_{\text{weak}}$ ((ref)). 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 ((ref)). Since $\theta^*$ is unknown, the weak-preference design identifies queries with weak preferences based on the previous phase's estimate $\widehat{\theta}_{\text{CH}}$. Then, GSE samples queries based on the design ((ref)) and, after exhausting the phase's budget, estimates $\theta^*$ using either the choice-decision-time estimator $\widehat{\theta}_{\text{CH,DT}}$ ((ref)) or the choice-only estimator $\widehat{\theta}_{\text{CH}}$ ((ref)). It then eliminates arms with low estimated utilities ((ref)). This process repeats until only one arm remains, which GSE recommends as the best arm ((ref)).
The key difference between (ref) and previous GSE algorithms azizi2021fixed,alieva2021robust,yang2022minimax 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 fiez2019sequential,azizi2021fixed to pre-allocate queries. This approach does not handle random resource usage. Instead, we adopt a random sampling procedure tao2018best,camilleri2021high in (ref) to allocate queries based on the design. Random resource usage also requires tuning the elimination parameter $\eta$, to balance data collection and arm elimination, and the buffer size $B_{\text{buff}}$, to prevent overspending. In our empirical study ((ref)), we manually tune both parameters. Further theoretical analysis is needed to better understand and optimize them.
This section empirically compares the GSE variations introduced in (ref): (1) $(\lambda_{\text{trans}},\widehat{\theta}_{\text{CH,DT}})$: Transductive design with choice-decision-time estimator. (2) $(\lambda_{\text{trans}},\widehat{\theta}_{\text{CH}})$: Transductive design with choice-only estimator. (3) $(\lambda_{\text{weak}},\widehat{\theta}_{\text{CH}})$: Weak-preference design with choice-only estimator.
We evaluate the estimation performance of the GSE variations on the “sphere” synthetic problem, a standard linear bandit problem in the literature li2023optimal,tao2018best,degenne2020gamification. Details are provided in (ref).
Estimation performance, as discussed in (ref), depends on the utility difference $x^\top\theta^*$ and the barrier $a$. We vary $a$ over a range of values commonly used in psychology wiecki2013hddm,clithero2018improving. To examine how preference strength impacts estimation, we scale each arm $z$ to $c_{\mathcal{Z}} \cdot z$, effectively scaling each utility difference $x^\top\theta^*$ to $c_{\mathcal{Z}} \cdot x^\top\theta^*$. Small $c_{\mathcal{Z}}$ values correspond to problems with weak preferences, while large values correspond to strong preferences. For each $(c_{\mathcal{Z}}, a)$ pair, the system generates $100$ random problem instances and runs $100$ repeated simulations per instance. In each simulation, the GSE variations sample $50$ queries, ignoring the response time budget, and compute $\widehat{\theta}$. Performance is evaluated by $\mathbb{P}[\operatorname*{arg\,max}_{z\in\mathcal{Z}} z^\top \widehat{\theta}\neq z^*]$, which reflects the best-arm identification goal defined in (ref). To isolate the effect of estimation, we allow $\lambda_{\text{weak}}$ access to the true $\theta^*$, enabling it to perfectly compute the terms $\dot{\mu}(x^\top\theta^*)$ used in (ref) of (ref).
As shown in (ref), fixing the barrier $a$ and examining the vertical line, as $c_{\mathcal{Z}}$ 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 $c_{\mathcal{Z}}$ 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 (ref) that choices from queries with strong preferences provide limited information. Fixing $c_{\mathcal{Z}}$ and examining the horizontal line, performance first improves and then declines. This trend aligns with (ref) and (ref), where higher barriers $a$ increase the choice-only weights for queries with weak preferences, initially improving performance. However, as $a$ grows, fewer queries exhibit increased weights, while most queries' weights decrease, leading to the later performance drop.
In (ref), for moderate $c_{\mathcal{Z}}$, the choice-only estimator with the weak-preference design outperforms the transductive design ((ref)), demonstrating that focusing on queries with weak preferences improves estimation. However, as $c_{\mathcal{Z}}$ becomes too large, performance declines because many $\dot{\mu}(x^\top\theta^*)$ in (ref) of (ref) approach zero, preventing informative queries from being sampled. This advantage of the weak-preference design assumes perfect knowledge of $\theta^*$ and equal resource consumption across queries. In practice, where $\theta^*$ is unknown and weak-preference queries require longer response times, the transductive design performs better, as shown in (ref).
(ref) shows that the choice-decision-time estimator consistently outperforms the choice-only estimators under both the transductive and weak-preference designs, particularly for strong preferences. This suggests that for queries with strong preferences, decision times complement choices and improve estimation, confirming our theoretical insights from (ref), while for queries with weak preferences, decision times add little value but do not degrade performance. The performance also improves with a higher barrier $a$, supporting the insights conveyed by (ref) and (ref).
This section compares the bandit performance of six GSE variations. The first three are as previously defined at the beginning of (ref): $(\lambda_{\text{trans}},\widehat{\theta}_{\text{CH,DT}})$, $(\lambda_{\text{trans}},\widehat{\theta}_{\text{CH}})$, and $(\lambda_{\text{weak}},\widehat{\theta}_{\text{CH}})$.
The 4th GSE variation, $(\lambda_{\text{trans}}, \widehat{\theta}_{\text{CH},\mathbb{RT}})$, evaluates the performance of the choice-decision-time estimator when the non-decision time $t_{\text{nondec}}$ is unknown. The estimator, $\widehat{\theta}_{\text{CH},\mathbb{RT}}$, is identical to the original choice-decision-time estimator from Eq. (ref), but with response times used in place of decision times.
The 5th GSE variation, $(\lambda_{\text{trans}},\widehat{\theta}_{\text{CH,logit}})$, is based on wagenmakers2007ez, which states that $x\t\cdot\b{2a\theta^*}=\mu^{-1}(\mathbb{P}[c_x=1])$, where $\mu^{-1}(p)\coloneqq\log\b{p/\b{1-p}}$. By incorporating our linear utility structure, we obtain the following choice-only estimator $\widehat{\theta}_{\text{CH,logit}}$:
where $\wh{\mathfrak{C}}_{x}\coloneqq\frac{1}{n_x}\sum_{i=1}^{n_x}\frac{1}{2}\b{c_{x,s_{x,i}}+1}$ is the empirical mean of the binary choices coded as 0 or 1.
The 6th GSE variation, $(\lambda_{\text{trans}}, \widehat{\theta}_{\text{CH,DT,logit}})$, is based on xiang2024combining, which states that $x\t\theta^*=\text{sgn}\b{c_x} \sqrt{\bbE\qb{c_x}/\bbE\qb{t_x} \cdot 0.5\:\mu^{-1}\b{\mathbb{P}\qb{c_x=1}}}$. This identity forms the foundation of the estimator in berlinghieri2023measuring. By incorporating our linear utility structure, we obtain the following choice-decision-time estimator $\widehat{\theta}_{\text{CH,DT,logit}}$:
We evaluate six GSE variations on 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 to assess performance. Details on experimental procedures are provided in (ref). Key results for the three domains are shown in (ref), with full results in (ref). First, $(\lambda_{\text{trans}},\widehat{\theta}_{\text{CH,DT}})$ consistently outperforms $(\lambda_{\text{trans}},\widehat{\theta}_{\text{CH}})$, demonstrating the benefit of incorporating decision times. Second, both of these variations outperform $(\lambda_{\text{weak}},\widehat{\theta}_{\text{CH}})$, as discussed in (ref). Third, $(\lambda_{\text{trans}},\widehat{\theta}_{\text{CH,DT}})$ performs similarly to $(\lambda_{\text{trans}},\widehat{\theta}_{\text{CH,}\mathbb{RT}})$, suggesting that not knowing the non-decision time has minimal impact. Finally, $(\lambda_{\text{trans}},\widehat{\theta}_{\text{CH,logit}})$ wagenmakers2007ez and $(\lambda_{\text{trans}},\widehat{\theta}_{\text{CH,DT,logit}})$ xiang2024combining do not perform as consistently well as $(\lambda_{\text{trans}},\widehat{\theta}_{\text{CH,DT}})$, highlighting the effectiveness of our proposed choice-decision-time estimator ((ref)).
This work is the first to leverages human response times to improve fixed-budget best-arm identification in preference-based linear bandits. We proposed a utility estimator that combines choices and response times. Both theoretical and empirical analyses show that response times provide complementary 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 in crowdsourcing settings where participants' focus can vary myers2022practical. Future work could integrate eye-tracking data into the DDM framework krajbich2010visual,fisher2017attentional,smith2018attention,krajbich2019accounting,yang2023dynamic to monitor attention and filter unreliable responses. Another direction is to relax the assumption of known non-decision times by estimating them directly from data, following methods proposed by wagenmakers2007ez.