Minimax-optimal trust-aware multi-armed bandits

• Thank you for the insightful question. Assumption 1 allows us to focus on scenarios where sublinear regret is information-theoretically achievable. When the trust set does not contain any optimal arm, even perfect recommendations will inevitably reduce trust, incurring a linear regret in the worst case.

  Following reviewers' suggestions, we added a section in the appendix to discuss the case where the trust set does not include any optimal arm. Without Assumption 1, we show that the minimax lower bound becomes $\\Omega(\\sqrt{KH}+\\epsilon H)$ where \\epsilon:=\\max_{k\\in\\mathcal T}r(k)-r^\\star is the suboptimality gap of the best arm in the trust set. This implies that when $\\epsilon$ is constant large, any algorithm must incur a linear regret in the worst case.

  In addition, our algorithm remains robust in this setting. By slightly modifying our proof, we can show that the regret upper bound of the proposed algorithm becomes $\\widetilde{O}(\\sqrt{KH}+K^4+\\epsilon H)$. This demonstrates that our algorithm is still nearly minimax optimal (up to some logarithmic factors) when $H$ is sufficiently large. When the trust set contains moderately good arms ($\\epsilon=\\widetilde O(1/\\sqrt{H})$), it can still attain the classical minimax regret $\\widetilde{O}(\\sqrt{H})$. Similarly, when the optimal arm is included with some probability, the bounds above generalize by replacing $\\epsilon$ with the expected reward gap.

• This is certainly another valid point.

  • First, this assumption is motivated by various real-world human-autonomy interaction applications. One example arises from shared control in semi-autonomous driving [1]. While both the autonomous system and humans can execute the same actions (e.g., turning the steering wheel left), humans need to touch the wheel if they decide to take actions on their own. In this case, pressure sensors on the steering wheel can directly record whether humans follow or override autonomy, where human control corresponds to $\\chi_h=1$. Another example is human-robot collaboration to complete certain tasks [2,3], where recommendation compliance is indeed observed and recorded due to the collaborative nature of the missions. Hence, we adopt this observability assumption in our framework. As our work represents an initial exploration into trust-aware MABs, we believe this setup maintains practical relevance and implications.
  • Next, we briefly discuss how to extend our algorithm where such observability is infeasible in certain scenarios. Recall that $\\chi_h$ is used in the first stage to estimate unknown trust $t_h$ because $t_h = \\mathbb E[\\chi_h]$. When $\\chi_h$ is unobservable, we can approximate it by $\\tilde\\chi_h\\coloneqq{1}\\{a^{pm}_h=a^{ac}_h\\}.$ As the reviewer pointed out, $\\tilde \\chi_h$ is no longer an unbiased estimator of $t_h$: given the recommended arm $a^{pm}$, we have $\\mathbb E[\\tilde\\chi_h]=t_h+\\pi^{own}_h(a^{pm})$. When $\\pi^{own}_h$ remains relatively stable over short periods, we can incorporate an additional procedure in the first stage of our algorithm to obtain a reasonable estimate of $\\pi^{own}_h(\\cdot)$. For example, the empirical distribution of the samples satisfying $a^{pm}_h \\neq a^{ac}_h$ can be used. Similar to the current setting, we can show that choosing the length of the first stage polynomial in $K$ would achieve the desired estimation accuracy, and only introduce an extra term (polynomial large in $K$) to the regret upper bound. Hence the regret of the resulting algorithm remains near-optimal with respect to $H$.
  • Finally, we acknowledge that fully addressing the unobservable case requires additional work. As this paper serves as an initial attempt to build theoretical foundations for trust-aware decision-making, we choose to focus on the observable case---a condition that holds in many practical applications while conveying the core insights of this work. A comprehensive treatment of the unobservable scenario is an important direction for future work.

[1] Wang, Chengshi, et al. "Haptic assistive control with learning-based driver intent recognition for semi-autonomous vehicles." IEEE Transactions on Intelligent Vehicles 8.1 (2021): 425-437.

[2] Chen, Min, et al. "Planning with trust for human-robot collaboration." Proceedings of the 2018 ACM/IEEE international conference on human-robot interaction. 2018.

[3] Bhat, Shreyas, et al. "Clustering trust dynamics in a human-robot sequential decision-making task." IEEE Robotics and Automation Letters 7.4 (2022): 8815-8822.

Response to Weakness

• Yes, we assume the policy-maker has access to $(\\chi_h)_{h\\geq1}$.
  • First, this assumption is motivated by various real-world human-autonomy interaction applications. One example arises from shared control in semi-autonomous driving [1]. While both the autonomous system and humans can execute the same actions (e.g., turning the steering wheel left), humans need to touch the wheel if they decide to take actions on their own. In this case, pressure sensors on the steering wheel can directly record whether humans follow or override autonomy, where human control corresponds to $\\chi_h=1$. Another example is human-robot collaboration to complete certain tasks [2,3], where recommendation compliance is indeed observed and recorded due to the collaborative nature of the missions. Hence, we adopt this observability assumption in our framework. As our work represents an initial exploration into trust-aware MABs, we believe this setup maintains practical relevance and implications.
  • Next, we briefly discuss how to extend our algorithm where such observability is infeasible in certain scenarios. Recall that $\\chi_h$ is used in the first stage to estimate unknown trust $t_h$ because $t_h = \\mathbb E[\\chi_h]$. When $\\chi_h$ is unobservable, we can approximate it by $\\tilde\\chi_h\\coloneqq{1}\\{a^{pm}_h=a^{ac}_h\\}.$ As the reviewer pointed out, $\\tilde \\chi_h$ is no longer an unbiased estimator of $t_h$: given the recommended arm $a^{pm}$, we have $\\mathbb E[\\tilde\\chi_h]=t_h+\\pi^{own}_h(a^{pm})$. When $\\pi^{own}_h$ remains relatively stable over short periods, we can incorporate an additional procedure in the first stage of our algorithm to obtain a reasonable estimate of $\\pi^{own}_h(\\cdot)$. For example, the empirical distribution of the samples satisfying $a^{pm}_h \\neq a^{ac}_h$ can be used. Similar to the current setting, we can show that choosing the length of the first stage polynomial in $K$ would achieve the desired estimation accuracy, and only introduce an extra term (polynomial large in $K$) to the regret upper bound. Hence the regret of the resulting algorithm remains near-optimal with respect to $H$.
  • Finally, we acknowledge that fully addressing the unobservable case requires additional work. As this paper serves as an initial attempt to build theoretical foundations for trust-aware decision-making, we choose to focus on the observable case---a condition that holds in many practical applications while conveying the core insights of this work. A comprehensive treatment of the unobservable scenario is an important direction for future work.
• This is certainly a valid point. We have revised the statement of the regret bound to $\widetilde{O}(\sqrt{KH}+K^4)$.
• Thanks for the suggestion. We have changed "minimax optimal" to "near-optimal" in the title and other places.

[1] Wang, Chengshi, et al. "Haptic assistive control with learning-based driver intent recognition for semi-autonomous vehicles." IEEE Transactions on Intelligent Vehicles 8.1 (2021): 425-437.

[2] Chen, Min, et al. "Planning with trust for human-robot collaboration." Proceedings of the 2018 ACM/IEEE international conference on human-robot interaction. 2018.

[3] Bhat, Shreyas, et al. "Clustering trust dynamics in a human-robot sequential decision-making task." IEEE Robotics and Automation Letters 7.4 (2022): 8815-8822.

Response to Weakness

• While our model does not cover all complex trust frameworks, we believe it serves as an initial step toward a theoretical understanding of trust-aware decision-making. It effectively shows that classical MAB algorithms may be inefficient when trust issues arise, highlights the necessity of trust-aware algorithms, and conveys our core principle of "building trust before learning" in algorithmic design. We leave the exploration of more complicated trust models to future work.

• Thank you for the insightful observation. Our analysis actually guarantees that for a fixed trust set $\\mathcal{T}$, the proposed algorithm achieves a regret bound of $\\widetilde{O}(\\sqrt{|\\mathcal{T}|H}+K^4)$. The current bound in Theorem 2 results from taking the supremum over $|\\mathcal{T}|$ (which can equal $K$). In the updated version, we have modified the proof to clarify this point. As for the dependence on $K$, our future work will focus on refining the algorithm to achieve the optimal dependence, which may require developing a more sophisticated trust-building phase.

• Due to space constraints, we only showed a representative example that best demonstrates how trust issues hurt vanilla UCB and highlights our method's effectiveness. When the trust set consists of the best two arms, gaining trust becomes extremely difficult since the arms recommended in the early exploration stage are mostly suboptimal and do not belong to the trust set. As proved in Theorem 1, ignoring trust issues would lead to linear regrets in this case. Conversely, when the trust set contains many suboptimal arms, building trust is much easier.

  In the appendix of the updated version, we included additional numerical experiments for the scenarios suggested, including (1) \\pi^{own}_h(a^\\star) is increasing in $h$; (2) $\\mathcal{T}$ contains the best-50% arms; (3) $\\mathcal{T}$ contains optimal and highly suboptimal arms; (4) $\\mathcal{T}$ includes only one of multiple optimal arms. As can be seen from the plots, our method achieves regret scaling as $\\sqrt{H}$, with comparable or superior performances to UCB algorithms.

  Regarding trust-aware UCB's superior performance, this is due to the chosen own policy $\\pi^{own}$, which pulls the best two arms. Therefore, during the exploration stage before the optimal arm is identified, whenever the implementer executes $\\pi^{own}$, the regret incurred by $\\pi^{own}$ tends to be smaller than that of UCB without decision deviations. This explains why trust-aware UCB achieves a smaller regret, despite sharing the same order in $H$.

Response to Questions

• Thank you for the suggestion. Following reviewers' suggestions, we added a section in the appendix to discuss the case when the trust set does not include any optimal arm. In particular, we added a theorem to rigorously justify that without Assumption 1, the minimax lower bound becomes $\\Omega(\\sqrt{KH}+\\epsilon H)$ where \\epsilon:=\\max_{k\\in\\mathcal T}r(k)-r^\\star. This implies that when the best arm in the trust set has a constant large suboptimality gap, any algorithm must incur a linear regret in the worst case.
• Thanks for the suggestion. Exploiting implementer behavior patterns is a promising avenue for improving the regret guarantees. For instance, it would be interesting to consider the following scenarios including (1) uniform random selection within the trust set, (2) only pulling arms outside the recommended set, and (3) the probability of choosing the optimal arm increasing over time. Incorporating this prior knowledge into the design of the trust set identification and trust-building stages could potentially yield more efficient algorithms. We leave the detailed theoretical investigation to future work.

Response to Weakness

• Due to space constraints, we only showed a representative example that best demonstrates how trust issues hurt vanilla UCB and highlights our method's effectiveness. When the trust set consists of the best two arms, gaining trust becomes extremely difficult since the arms recommended in the early exploration stage are mostly suboptimal and do not belong to the trust set. As proved in Theorem 1, ignoring trust issues would lead to linear regrets in this case. Conversely, when the trust set contains many suboptimal arms, building trust is much easier.

  In the appendix of the updated version, we included additional numerical experiments for the scenarios suggested, including (1) \\pi^{own}_h(a^\\star) is increasing in $h$; (2) $\\mathcal{T}$ contains the best-50% arms; (3) $\\mathcal{T}$ contains optimal and highly suboptimal arms; (4) $\\mathcal{T}$ includes only one of multiple optimal arms. As can be seen from the plots, our method achieves regret scaling as $\\sqrt{H}$, with comparable or superior performances to UCB algorithms.

• Assumption 1 allows us to focus on scenarios where sublinear regret is information-theoretically achievable. When the trust set does not contain any optimal arm, even perfect recommendations will inevitably reduce trust, incurring a linear regret in the worst case.

  Following reviewers' suggestions, we added a section in the appendix to discuss the case where the trust set does not include any optimal arm. Without Assumption 1, we show that the minimax lower bound becomes $\\Omega(\\sqrt{KH}+\\epsilon H)$ where \\epsilon:=\\max_{k\\in\\mathcal T}r(k)-r^\\star is the suboptimality gap of the best arm in the trust set. This implies that when $\\epsilon$ is constant large, any algorithm must incur a linear regret in the worst case. In addition, our algorithm remains robust in this setting. By slightly modifying our proof, we can show that the regret upper bound of the proposed algorithm becomes $\\widetilde{O}(\\sqrt{KH}+K^4+\\epsilon H)$. This demonstrates that our algorithm is still nearly minimax optimal (up to some logarithmic factors) when $H$ is sufficiently large. When the trust set contains moderately good arms ($\\epsilon=\\widetilde O(1/\\sqrt{H})$), it can still attain the classical minimax regret $\\widetilde{O}(\\sqrt{H})$.

• First, our intention is to cover as many decision deviation possibilities as possible so our model does not exclude the case where the implementer may strongly oppose certain high-reward arms. Nevertheless, even in such a case, as long as the trust set includes at least one optimal arm (B), our algorithm can still identify the trust set and recommend arm $B$. Since arms $A$ and $B$ have the same expected rewards, the algorithm achieves near-optimal regrets even though arm $A$ reduces trust and will not be pulled often.

  Second, we fully agree other reasonable trust update rules are worth exploring, such as the performance-based rule where increasing trust when the empirical average of the recommended arm exceeds a certain threshold chosen by the implementer. However, we note that while specific algorithmic details may vary, our core principle of "building trust before learning" remains valid across different trust models. Due to space limits, we leave the detailed exploration of other trust update models for future works.

• Thank you for the suggestion. We have increased the font size.

Response to Question

This is certainly an important extension. If the trust level is calculated over a sliding window of $L$ steps, the suboptimality of UCB remains. Due to its aggressive exploration, most recommended arms during initial exploration are suboptimal, driving trust near zero before the optimal arm is identified. Even with the $L$-step trust update rule, this near-zero trust issue remains, causing the implementer to follow their own policy and not pull those recommended suboptimal arms in practice. Hence, UCB keeps recommending those suboptimal arms and trust never increases again. On the other hand, our trust-aware algorithm will perform better in this setup. As trust levels increase faster, the $L$-step trust update accelerates both trust set identification and trust-building phases, leading to reduced regret.