Enhancing Preference-based Linear Bandits via Human Response Time

Thank you for your detailed and thoughtful review, and for recognizing the novelty and clarity of our work.

Weakness: algorithm analysis

In our paper draft, we provide asymptotic theoretical results to show the following intuition on why response time can improve the learning performance:

Combining response times and choices, information from easy queries can be extracted more efficiently. This is not possible using choices only.

We 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.

We leave for future work to provide non-asymptotic error probability for the entire algorithm (Algoithm 1 in the paper).

Weakness: practical usage of response time when $a$ is unknown

One straightforward approach is to always incorporate response times:

1. Based on our empirical results, it seems that incorporating response times, if not improving the performance, rarely degrades performance.
2. 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.

Alternatively, 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.

Thank you for your positive and constructive review; we appreciate your feedback and recognition of our work's novelty and usefulness.

Weakness: real-world empirical result

We 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.

Firstly, 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.

Secondly, 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.

Therefore, 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.

We 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.

• [1] Myers et al. 2022
• [2] Li et al. 2010
• [3] Wagenmakers et al. 2007

Question: about lapses and data processing

In 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.

The 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.

Another 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].

• [1] Krajbich 2019
• [2] Myers et al. 2022
• [3] Alós-Ferrer et al. 2021
• [4] Fudenberg et al. 2020

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.

Weakness: about EZ-DDM vs DDM and EZ-DDM's assumptions

Thank 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.

As 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.

To 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.

• [1] Wagenmakers et al. 2007
• [2] Berlinghieri et al. 2023
• [3] Clithero (2018)

Question: why choice-only could perform better asymptotically?

Given 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.

Both 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}$. The 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.

We 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.

While 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. For 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.

Finally, 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.

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:

Weakness: non-asymptotic result

In our paper draft, we provide asymptotic theoretical results to show the following intuition on why response time can improve the learning performance:

Combining response times and choices, information from easy queries can be extracted more efficiently. This is not possible using choices only.

We 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.

We leave for future work to provide non-asymptotic error probability for the entire algorithm (Algoithm 1 in the paper).

Weakness: real-world empirical result

We 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.

Weakness+question: background of DDM models

We plan to include the following summary of DDM literature in the appendix:

1. Literature on modeling choices and response times

Bounded 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. DDM with time-decaying barriers theoretically connects to human Bayesian RL models [5]. DDMs also characterize human attention during decision-making, by modeling choices, response times, and eye gazes on options or attributes [7]. Race 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. Neurophysiological evidence supports BAMs. EEG recordings show neurons exhibit accumulation processes and decision thresholds [2][6].

2. Literature on using response times (survey [10])

Response 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.

Another 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.

• [1] Ratcliff and McKoon 2008
• [2] Webb 2019
• [3] Wagenmakers et al. 2007
• [4] Usher and McClelland 2001
• [5] Fudenberg et al. 2018
• [6] Ratcliff et al. 2016
• [7] Krajbich 2019
• [8] Clithero 2018
• [9] Alós-Ferrer et al. 2019
• [10] Clithero 2018.
• [13] Pedersen et al. 2017
• [14] Bengs et al. 2021

Question: about other link functions that models human choices

First, 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.

Second, 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.

Lastly, 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.

• [1] Bengs et al. 2021
• [2] Stochastic Choice Theory, Econometric Society Monograph