'I pick you choose': Joint human-algorithm decision making in multi-armed bandits
Authors: Kate Donahue
Sreenivas Gollapudi
Kostas Kollias
Venue: Submitted to ICLR 2023 (2023)
Keywords: human algorithm collaboration
multi-armed bandits
complementarity

Abstract: Online learning in multi-armed bandits has been a rich area of research for decades, resulting in numerous \enquote{no-regret} algorithms that efficiently learn the arm with highest expected reward. However, in many settings the final decision of which arm to pull isn't under the control of the algorithm itself. For example, a driving app typically suggests a subset of routes (arms) to the driver, who ultimately makes the final choice about which to select. Typically, the human also wishes to learn the optimal arm based on historical reward information, but decides which arm to pull based on a potentially different objective function, such as being more or less myopic about exploiting near-term rewards. In this paper, we show when this joint human-algorithm system can achieve good performance. Specifically, we explore multiple possible frameworks for human objectives and give theoretical regret bounds for regret. Finally, we include experimental results exploring how regret varies with the human decision-maker's objective, as well as the number of arms presented. 

Under review as a conference paper at ICLR 2023
"I PICK YOU CHOOSE": JOINT HUMAN-ALGORITHM DECISION MAKING IN MULTI-ARMED BANDITS
Anonymous authors
Paper under double-blind review
ABSTRACT
Online learning in multi-armed bandits has been a rich area of research for decades, resulting in numerous "no-regret" algorithms that efficiently learn the arm with highest expected reward. However, in many settings the final decision of which arm to pull isn't 't under the control of the algorithm itself. For example, a driving app typically suggests a subset of routes (arms) to the driver, who ulti- mately makes the final choice about which to select. Typically, the human also wishes to learn the optimal arm based on historical reward information, but de- cides which arm to pull based
potentially different objective function, such as being more or less myopic about exploiting near-term rewards. In this paper, we show when this joint human-algorithm system can achieve good performance. Specifically, we explore multiple possible frameworks for human objectives and give theoretical regret bounds for regret. Finally, include experimental results exploring how regret varies with the human decision-maker's objective, as well as the number of arms presented.
INTRODUCTION
Consider the following motivating example:
Alice has recently moved to new town and does not know the area yet. She uses a navigation app while driving, which narrows down the thousands of potential routes to a few options for her to choose from. She and the app only get to see the actual driving time of the final route she picks. Because of varying traffic and weather delays, the actual driving times of each route is unpredictable. Both the navigation app and Alice wish to minimize her average travel time. However, they might have different short-term objectives. For example, Alice might be myopic and prefer choosing a route that has performed well in the past, rather than exploring
one. Altermatively, Alice may be adventurous and actively seek out new routes the hope that there might be quicker than ones she has previously explored. The navigation app uses generic algorithm that doesn't 't know Alice's s specific objective function. Under what situations can Alice and her navigation app achieve their goal of quickly finding the quickest route?
If Alice's navigation app were able to tell Alice exactly which route she must take, then this problem would reduce to that of multi-armed bandits (MAB), celebrated online-learing paradigm. How- ever, in the driving directions setting, it is unrealistic assume that the algorithm can force Alice to take particular route. In human-algorithm collaboration more generally, often the algorithm can provide assistance, but the human makes the final decision. This is the case other settings as teacher
well: diner trying to find the best restaurant. doctor trying to find the best treatment, trying to find the best pedagogical method. This framework requires a shift in thinking: rather than focus on optimizing the performance of the algorithm alone, the goal is to build algorithm that maximizes the performance of the human alggorithm system.
For multi- bandits, the standard objective is minimize expected regret, the amount of reward that missed by not selecting the optimal arm. In human- aulan-algorithm multi-armed bandits, some aspects (such the behavior of the human), entirely out of our control, and the system cannot

---

Under review as a conference paper at ICLR 2023
be completely optimized. Instead, the goal of this paper is descriptive: to characterize settings where sublinear regret is possible and settings where linear regret is unavoidable.
In Section 2 discuss how our setting and results relate to previous literature in MAB and in numan-algorthhm collaboration. In Section 3 we formalize the model that we analyze, including multiple different models of human behavior. Section 4 contains theoretical results, such as bounds on expected regret. Specifically, we show that, so long as the human isn' 't completely myopic (has some weak preference for exploring arms that haven" 't been frequently pulled), then sublinear regret is achievable. If the human is myopic, then it is unavoidable that the regret includes a linear depen- dence on time. Section [ enriches these theoretical results with experimental simulations. These results show that if the human is more myopic than the algorithm, overall regret decreases the more arms are shown to the human. On the other hand, if the human is less myopie, the opposite true, and regret increases the more arms are shown to the human. Finally, in Section 6 we briefly discuss implications of our work and potential future directions.
2 RELATED WORK
MULTI-ARMED BANDITS
The area of multi armed bandits is wide enough to admit multiple textbooks Slivkins et al. (2019); Lattimore & Szepesvári (2020). In this section, we will highlight some of the most related papers.
Yue et al. (2012) proposed "ducling bandits", where multiple arms are presented simultancously and the feedback is noisy binary signal as to which has higher reward. Since this, there has been numerous extensions (Sui et al. (2018) 2017b); Komiyama al. (2015). such as those that allow more than 2 arms to be presented Saha & Gopalan [ et al. (2020); (Si et al. (2017a). Shivaswamy & Joachims 2015) studies related problem where the task of the algorithm
rank
a set of items. The human then improves the ranking according to their true utility function, but with some bounded degree of improvement reflecting limits on human rationality. One major difference between ducling bandits and our framework is that we assume feedback is given by human who learning about the rewards of the arms themselves, whereas dueling bandits typically assume that responses between the arms are fixed. Additionally, dueling bandits typically involves boolean feedback, where we allow real-valued access to the rewards.
There has also been series of work looking more specifically at human-algorithm collaboration in bandit settings. Gao et al. (202T) learns from batched historical human data to develop an algorithm that assigns each task at test time to either itself human. Chan et al. (2019) studies a setting similar to ours in that the human is simultancously learning which option is best for them. However, their framework allows the algorithm to overrule the human, which makes sense in many settings, but not all, such as our motivating example of driving directions. Bordt & Von Luxburg (2022) formalizes the problem that affect the reward both experience.
two-player setting where both the human and algorithm take actions
Additionally, some work has used the framework of the human as the final decision-maker and studied how to disclose information so as to incentivize them to take the "right" action. [Immrrlica al. (2018) studies how to match the best regret a setting where myopic humans pull the final arm. Hu et al. (2022) studies a related problem with combinatorial bandits, where the goal is to select a subset of the total arms to pull. Bastani et al. (022)) investigates more applied setting where each human is a potential customer who will become disengaged and leave if they are suggested products (arms) that are a sufficiently poor fit. Kannan et al.] (2017) looks
similar model of sellers considering sequential clients, specifically investigating questions of fairness. In general, these works differ from ours that they assume a new human arrives at each time step, and so the algorithm is able to selectively disclose information to them. In our setting, the human may be the same between time steps, and we typically assume that they have access to the same information as the algorithm.
HUMAN-ALGORITHE COLLABORATION
Studying Human-algoritte collaboration is a rapidly growing, highly interdisciplinary area of re- search. In general, most work focuses on offline learning settings, which differs from our MAB
2

---

Under review as a conference paper at ICLR 2023
analysis. Some veins of research are more ethnographic, studying how people use algorithmic imput in their decision-men makiiigonmmnii//////o Lebovitz et al. (2021 2020); Beede et al. (2020); Yang et al. (2018) k Okolo al. (202T). Other avenues work developing ML tools designed to work with humans, such in medical settings Raghu et al. (2018) or child welfare phone screenings Chouldechova et al. 2018)
Finally, and most closely related this paper, some works develop theoretical models ana analyze human-algorithm systems, such as Rastogi et al. 2022); Cowgill & Stevenson (2020); Bansal et al. (2021a); Steyvers al. (0022) Madras et (2018). Bansal et al. (2021b) proposes the notion of complementarity, which is achieved when a numan-algos algorithm system together has performance that strictly better than either the human or the algorithm could achieve along. /Stritourii et al. (2022) studies "conformal prediction" where the algorithm narrows down the the list of possible item la- bels to a subset, from which the human picks. This formulation is structurally similar to ours, but considers the offline labeling task, rather than online MAB.
3 MODEL AND ASSUMPTIONS
3.1 MODEL
We assume that there are N arms, each of rewards drawn i.d from the distribution X; ~ Di, for i E [N]. WLOG, we will order the arms descending order of expected reward. This means arm O has the highest expected reward, and we will set A to be the difference between the expected reward of arm and arm O. There are two actors, the human (If) and the algorithm (A). Each of them has access to the same historical information but uses it in different ways. For each time step t E [T], the algorithm selects a subset of & E [1, N arms to present to the human. Among those k presented, the human selects single final arm Ie to be pulled. Both the human and algorithm observe reward X,, ~ D; Note that for = this reduces to the algorithm selecting the final arm (because the human
only select from those that are presented), while for k N this reduces to the human making unconstrained selection. Throughout, our goal will be to minimize expected regret, or the amount of reward the algaanta system misses out on by pulling sub-optimal arms:
T 44
Σ Blund E(AN
3.2
ALGORITHM AND HUMAN BEHAVIOR
Next, we will describe the assumptions behind how the algorithm and human behave. One standard selection approach we will incorporate is the UCB algorithm, which at time & selects whichever arm maximizes Auer al. 2002):
In(() ni,e
s5, + 0a V
for empirical mean Ar. Re.r E1 [[4e-
= = -x, Because the UCB algorithm is standard
algorithm for multi-armed bandit settings, we will assume the algorithm A uses some variant of it. However, in this paper, we will explore scenarios where the human H uses multiple different selection rules. For example, we say that H (a,, m)-myopic if it selects randomly among the presented arms with probability 8 and otherwise selects whichever maximizes the UCB algorithm with coefficient ox:
x Unif[k]
r ~~ Unif(0, 1] $ 8
In(t)
argmax;
Pr.x + an
otherwise
In addition to these objectives, we will assume that the human and algorithm both prefer to pull each arm least once before pulling any other arm.
3

---

Under review as a conference paper at ICLR 2023
4 THEORETICAL ANALYSIS
In this section, we will provide theoretical regret bounds for our human- aulaan-agoorthmm setting. First, will show in Lemma that any human with 5 must incur at linear regret (proof in the Appendix). Additionally, this result has lower bound that is increasing in k, the number of arms shown to the human. This suggests that, the human selects randomly with some nonzero probability, it may be optimal show few arms possible them. Following this result, we will assume å throughout the rest of the paper.
Lemma 1. Any human that selects uniformly at randomly with probability 0 among 2 incurrs regret (i(T) that is increasing in k.
Next, we will work to bound total regret when ò = O. We will find it useful to use Lemma 2 which gives high-probability bound for the relative ordering the UCB values for two arms.
Lemma 2. Consider arm i with Di.t 2 a²
Im(t) 2.27 for [0,0.5], 2 1. Then, if any UCB
algorithu selecting according UCB,,, P&. t probability at least 1- 72
In(t)
Then, UCB UCBu,, with 18,
First, we consider the case where on 0, so the human isn't completely myopic in its choice of arm. Theorem gives a regret bound for this scenario. One key area of focus in human-al maggrial collaboration in general is how the performance of the joint system compares to that of the human and algorithm separately SaatratteyyBanaalll Bansal et al. (2021b a). Overall performance could be better than either the human algorithm (complementary performance, defined inBansal al. (2021b)), or could be worse, or could be somewhere in between. For Theorem | the regret bound involves a max(af, a term. This effectively means that regret for the human-algorithm system is guaranteed to at least as good as the worse of the two components (human or algorithm).
Theorem 1. Consider the case with ab, Oa > 1. Then, the expected regret is bounded by:
V N W. In( (1 4. max (.)) + 16 N
Proof. First, will divide the two arms into groups:
1. Group 1 contains arms with A; < N In(T)
2. Group 2 contains arms with A, >
N
(T)
T
In order to bound total regret, we can bound regret from group as:
Σ
n&e n.. A
In()):
Σ n.T I
In() T / T.
T
T
IEG
IEG
The remaining portion of the proof will bound regret from arms of group 2.
First, we will work bound the number of times that arm i, for * 0, can be pulled for all time (ngr).
We will use I to indicate the arm pulled at time Our goal to bound the expected value of n,,r-
We will use ni, = -ax (a a.) In(t) to denote a minimum threshold of samples we need from
4

---

Under review as a conference paper at ICLR 2023
arm i in order to obtain certain sish-rrbbbillity guarantees.
T
E E|u,r]
= E
114+1 =
1=
=14 + E
11 17++1 =i)]
t=
= =1+ E
(1++1 i/14s < n
E
Σ 1 (1++1= = (dm11=)
S n +
(1+1= i/nss 2 m211)
N=
In the second line, we used the fact that each arm must be pulled at least once. In the third line, we conditioned on the probability of pulling arm depending on whether has already been pulled ni, times not. In the fourth line, we use the fact that arm i can only be pulled ni times until ni, < ni is no longer satisfied.
Next we will bound the second term: the number of times arm can be selected, given that it has already been pulled at least ni,r- Here, we will find it useful to rewrite the expectation as the sum of probabilities:
T Σ N
T Σ (1 2 mi,1)
E
(1411 = i|ri, n1,))
t=N
Recall that the algorithm uses UCB fa, fa,ta''
[n(()) Ri.e"
while the human uses UCB j. tan
that, according to Lemma 2 we have enough UCB,, and 2) UCB., UCB Statement 1) means that if arm i is presented to the human, with high probability arm O will be as
In(t))
We have set ni,, max (a a²) In(()
V "ia""
samples that with probability at least 1 1) UCB,
well. Statement 2) means that if both arms are presented to the human, with high probability the human will pick arm O. If either of these fails, then arm i could get picked.
We can use both of these facts to bound regret from this portion based on the probability that either of these conditions fails:
4 12
Σ 2
2-2
1=N
We can bound the instence-nndependent regret from this term (for arms in group 2):
nh, A, 5 (nirr + 16) A
IEG2
(1: max (a), oz)
In
+
16
A;
A7
lT())
Σ 4 max (az, oz0
+ 16 A,
A;
IEG2
4 max (at, a2) In(T) VT
N T
16
InTT) <
N In())
iEG2
< 4- max (a a²) /N N T In( + 16 N
Overall, if we add in the regret from arms of group 1, we get a regret bound of:
VN T In(T) + 4 max (a,, a²) VN- In(T)) + 16 N
-/N. T Im() (1 4. max (o) 2)) + 16 N
5

---

Next, consider the where an 0, so the human greedily pulls whichever arm has had highest empirical reward (of those presented to it). Theorem 2 gives a regret bound for this sce- mario. As compared with Theorem IT note that this bound includes linear dependence on T that Under review as a conference paper at ICLR 2023
increases with k; the number of arms shown to the human. In Lemma we show that linear regret unavoidable if the human picks purely myopically.
Theorem 2. Consider any human using myopic selection (on = 0) and Oa 2 1. Then, the expected regret is bounded by:
V. (n()) (1+ a² N
2
+
Pi.
for Pi., = PxoNDa (Xo S N0 (1-6) A.).
Proof. The first part of this proof identical to that of Theorem 1 First, we will divide the two arms into groups (group with low-regret arms, group 2 with high regret arms). For arms from group 1, we've shown that we can bound:
Σ iEG,
RAT A S V In())
For arms from group work to bound the number of times that arm for 0, be pulled In(t)
for all time (NG,T). We will use ni, = a ア.7 to denote a minimum threshold of samples we need from arm i in order to obtain certain high-probability guarantees.
E N
E
1(141 i)
T
S n +
Σ
(I++1 = i/n4, 2 nin))
N==
- + Σ P (I++1= = iimm 2 nt,))
N
This proof differs from Theorem because the human selects myopically, greedily optimizing whichever arm has fúg maximized. Let Xo ~ Dy denote the first pull from each arm, respectively. We will use
Pi.e = PX.-D, [Xo S Ho (1 We know with high probability that júa S 14 +e A,, but if Xo S μo - 61 A; μ4 + A.. then possible that Xo S f0;.. this occurs, arm i will always be preferred over arm 0, so arm would never be pulled again, after the first time.
With probability - Pt... Xo > μr - (1 - e) A = p: te A,. If this occurs, with probability at least 1 2. the following inequalities hold:
In(t)
2 f2
Pr. S p4 V
Chernoff bound with probability
nt,t
In(1) ns,e
In(t) .7 ag -I(()) S Se.A,
S 14 + A;
A - Mal S
c) ()- A
XD
by assumption
we know that with high probability the algorithm will rank arm 0 above arm i. This fails to occur with probability no more than &. Overall, the number of times arm i could be pulled is upper bounded by:
Because nir 2 a²
In(t) A.
T
Σ Piee + - -Pi.).
$2 S Pi. T
Σ < Pr.e T (1- Pi.))
t2 t=N

---

Under review as a conference paper at ICLR 2023
We can bound the instance-independenn regret from this term (for arms in group 2):
In(7)
Σ
Ditt
A
<
22 A Pi,e T (1 -Ph.e) A;
iEGs
In(T)
Σ
+ Pi.e T A. + 88. (1-..- A.
A
iEG2
a In([T) VT
Σ
2 VN. PP..' +8
iEG2
a (In(T) - T
Epie Pie.T TT iEG2
For the last component, we can actually improve the linear dependence slightly. We know that k arms are shown to the human. Therefore, even if Xo < μ4 + eA; for more than & arms, it won't increase regret by more than the total probability for the & largest probabilities. Because pt. is defined relative to distribution Du this will be the arms i with smallest A, The upper bound becomes:
a <
2 (
Pie T
Combined with the regret from the group I arms, this gives us regret:
(1+ a²
VN-T-In(T)
+8 +8.
Σ Pie T
Lemma 3. If Pi,e for any and ls 2 regret is P(T)).
with linear regret. Suppose that Dj for j & 0: Xj D)- Mj with probability 1. Suppose that k > 2, so the algorithm always must present at least one other after 1 samples A사 = Xo Ho (1 <)- A, If this occurs, then myopic human will always select arm i rather than arm O. Because arm is deterministic, A. will update, but will remain greater than Ho, which means arm 0 will never be pulled again. This leads to regret Pt.. T.
Proof. Then, will show it is possible to construct
besides the optimal arm. Consider any arm j O. Then, with probability pi.
Collectively, these results give an upper bound on expected regret for the human buman-algorithy algorithm MAB setting. Additionally, they demonstrate areas where we should linear regret is unavoidable.
EXPERIMENTAL RESULTS
Next, this section we further explore this setting through simulations. Specifically, our goal will be to demonstrate how expected regret varies with different features, such as the number of arms that are presented to the human, or the distribution of rewards for each arm. each simulation, we have N = 5 arms and varying k [1, N). There is single best arm 0 with highest expected reward drawn N(ug, r),, while all other arms have identical rewards M(44 σ)) (unless otherwise noted). We use rewards drawn from normal distributions because varying will allow us change Pi., while keeping the relative expected means Po, μi the same. We fix the algorithm's exploration coefficient Qg throughout, but vary the human's exploration coefficient ay.
5.1 VARYING NUMBER OF ARMS PRESENTED
In Figure I we explore the effect of varying the human's 's exploration coefficient an for values in {0, 0.5, 1, 27. Note that for a = (Figure Ia]. linear regret dominates and is increasing in the number of arms presented to the human k would be expected from Theorem 2 As intuition,
7

---

Under review as a conference paper at ICLR 2023
consider the fact that for larger k the human has higher probability of being presented with an arm i for which the first sample Xo < 140 - (1 - c) A, Therefore, showing more arms increases the linear component of regret.
For Ce > regret sublinear in T. For Figure Ib with aa > aq > 0, regret is decreasing in k: showing more arms the human decreases regret. Obviously, for Figure Ic with 0A Ga regret is constant in & because the human and algorithm are using the same metric to decide which arm to pick. Finally, for Figure Id with Or > Oa. regret is again increasing in k. As intuition, it might be useful to recall that the standard UCB algorithm Auer et al. (202) has regret that is increasing in a, for a > O. If ay < Qe- then for larger k the human doing "more" of the selection, because has more arms to choose from. Because of this, the overall regret will be dominated by the human's ss with a coefficient of ox-- Conversely, if Or > Oa. then for larger regret will be higher, again because the human is "responsible" for choosing among larger set of items.
These experimental results indicate that it could be possible to find a version of Theorem Ihhat also depends on k. However, this attempt might be complicated by the non-linear relationship between regret and k. For Figure db] for example, there is large jump in regret from much smaller one between k = 4 and k 3. Interestingly, these experimental results also seem to indicate that complementarity (strict improvements through human- allgoitt collaboration) might be impossible. For every simulation shown, either the human alone (k N) or the algorithm alone (k: = 1) performs optimally.
to 4, but a
5.2 VARYING REWARD DISTRIBUTION
Finally, we explored the impact of varying the reward distribution. Figure 2 shows another example with on 0, but where regret is sublinear, compared with Figure Ta which has a₁ 0, but linear regret. In Figure 2 the gap A; is larger, so pi,e is extremely small. This means that the linear dependence on T is very small, so regret dominated by the sublinear term. This example shows (empirically) that it is possible to achieve low regret, given certain distributional assumptions on the arms.
CONCLUSION AND FUTURE DIRECTIONS
In this paper, we have explored human-algorithm collaboration in a multi-armed bandit scenario. We proved theoretical bounds regret, as well as demonstrated empirical patterns in regret when varying number of arms are presented. There are multiple possible avenues for future work. For example, in our work we have assumed that the algorithm is using UCB. While this is standard MAB approach that achieves sublinear regret with human collaborator in many cases, it may not be optimal. It would be interesting performance for a range of models of human behavior. In particular, so far results seem to imply that complementarity is impossible with the current setting. It would be useful know whether this limitation is inherent to the setting or if regret could be improved to achieve complementarity Relatedly, Section 5 shows intriguing experimental patterns in average regret, k. and aa an that could be useful explore theoretically. Finally, it would be interesting to explore cases where the human and algorithm have access to different historical sets of rewards data (reflecting cases where the human, for example, may have lived in the city for while, and so has access prior information about the best routes).
explore whether another algorithm could achieve superior
REFERENCES
Arpit Agarwal, Nicholas Johnson, and Shivani Agarwal. Choice bandits. Advances in neural infor- mation processing systems, 011118999-8410 2020.
Peter Auer, Nicolo Cesa-Bianchi and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235 256. 2002.
Gagan Bansal, Besmira Nushi, Ece Kamar, Eric Horvitz, and Daniel S Weld. Is the most accurate AI the best teammate? Optimizing Al for teamwork. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11 11405-1 1414, 2021a.
8

---

Under review as a conference paper at ICLR 2023
Average and max/min regret. da=1, ah=0
Average and maximin regret. da= ah=0.5
0.0030
ammm
0.6
Noemaltedd
0.4
0.2
0.0000
4000
6000
8000
10000
4000
0000
0000
10000
Time step
(a)
0
(b) 0.5
Average regret.
Average regret.
0.0035
0.0030
aggegete
0.044
0.0015
0.033
0.0010
am
0.022
am
am
am
sm
0.011
am
0.0000
am
am
0.000
-0,0005
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
Time step
Time step
(c) ax
(d) Ck
Figure 1: Plots show regret for (line shows average regret, shaded region is max and min regret, for 100 simulations, each with 10,000 time steps). Each simulation has 5 arms total, where the single best arm has reward drawn from N/ 0.5, 0.1) and the other arms have reward N N(p = 0.45, o = 0.1).
Average and max/min regret. aa=1, ah=0
0.0030
NOTTMNLOR eggregent regges
0.0025
0.0020
0.0015
0.0010
ar
0.0005
0.0000
am
0
2000
4000
6000
8000
10000
except that, while the best arm still has reward drawn from N(μ 0.5, o 0.1), the other arms now have reward drawn from A(u 0.1, 0.1). The larger gap in rewards means that Pi.c is smaller, so the linear dependence on T does not dominate overall regret.
Figure 2: Simulation identical to Figure la

---

Under review as a conference paper at ICLR 2023
Gagan Bansal, Tongshuang Wu, Joyce Zhou, Raymond Fok. Besmira Nushi, Ece Kamar, Marco Tulio Ribeiro, and Daniel Weld. Does the whole exceed its parts? The effect of Al explanations complementary team performance. In Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems, pp. 1-16, 2021b.
Hamsa Bastani, Pavithra Harsha, Georgia Perakis, and Divya Singhvi. Learning personalized prod- uet recommendations with customer disengagement. Manufacturing & Service Operations Man- agement, 24(4):2010-2022 2022.
Emma Beede, Elizabeth Baylor, Fred Hersch, Anna lurchenko, Lauren Wilcox, Paisan Ruamviboon- suk, and Laura M Vardoulakis. human-center's evaluation of deep learning system deployed in clinics for the detection of diabetic retinopathy. In Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems, pp. 1-12, 2020.
Sebastian Bordt and Ulrike Von Luxburg. A bandit model for human-machine decision making with private information and opacity. In International Conference Artificial Intelligence and Statistics, pp. 7300-7319, PMLR, 2022.
Lawrence Chan, Dylan Badfield-Menel., Siddhartha Srinivasa, and Anea Dragan. The assistive multi-armed bandit. In 2019 14th ACM/IEEE International Conference on Human- Rohan Inter- action (HRR), pp. 354-363, IEEE, 2019.
Alexandra Chouldechova, Diana Genavides-Pradie Oleksandr Fialko, and Rhema Vaithianathan. A case study of algorithn-assisted decision making in child maltreatment hotline screening deci- sions. In Conference on Fairness, Accountability and Transparency, pp. 134-148. PMLR, 2018.
Bo Cowgill and Megan T Stevenson. Algorithmic social engineering. In AEA Papers and Proceed- ings, volume 1 110, pp. 96-100, 2020.
Ruijiang Gao, Maytal Taec-nssch,nkky Maria De-Arteaga, Ligong Han, Min Kyung Lee, and Matthew Lease. Human-ai collaboration with bandit feedback. arXiv preprint arXiv:2105. 10614, 2021.
Xinyan Hu, Dung Daniel Ngo, Aleksandrs Slivkins, and Zhiwei Steven Wu. Incentivizing combi- natorial bandit exploration. arXiv preprint arXiv:2206.00 00494, 2022.
Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, and Zhiwei Steven Wu. Incentivizing explo- ration with selective data disclosure. arXiv preprint arXiv: arXiv: 180.000 2018
Sampath Kannan, Michael Kearns, Jamie Morgenstern, Mallesh Pai, Aaron Roth, Rakesh Vohra, and Zhiwei Steven Wu. Faimess incentives for myopic agents. In Proceedings of the 2017 ACM Conference on Economics and Computation, pp. 369-386, 2017.
Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In Conference on learning theory, pp. 1 1141-1154. PMLR, 2015.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Sarah Lebovitz, Hila Lifshitz-Assal and Natalia Levina. To incorporate not to incorporate ai for critical judgments: The importance of ambiguity in professionals' judgment process. Collective Intelligence, The Association for Computing Machinery, 2020.
Sarah Lebovitz, Natalia Levina, and Hila Lifshitz-Assat Is AI ground truth really "true"? the dan- gers of training and evaluating AI tools based on experts' know-what. Management Information Systems Quarterly, 2021.
David Madras, Toni Pitassi, and Richard Zemel. Predict responsibly: Improving fairness and accu- racy by learning to defer. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.). Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018. URL http:/a:p/p/cceciiiiiiaa wwwpiiinnnnnnnuuuuioeeee httpur/ppp..cppppp////111/./
fi
10

---

Under review as a conference paper at ICLR 2023
Chinasa T Okolo, Srujana Kamath, Nicola Dell, and Aditya Vashistha. "it cannot do all of my work": Community health worker perceptions of ai-enabled mobile health applications in rural india. In Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems, pp- 1-20, 2021.
Maithra Raghu, Katy Blumer, Greg Corrado, Jon Kleinberg, Ziad Obermeyer, and Sendhil Mul- lainathan. The algorithmic automation problem: Prediction, triage, and human effort. NeurlPS Workshop on Machine Learning for Health (ML4H), 2018.
Charvi Rastogi, Liu Leqi, Kenneth Holstein, and Hoda Heidari. A unifying framework for combin- ing complementary strengths of humans and ml toward better predictive decision- decision-making. arXiv preprint 10000 2022.
Aadirupa Saha and Aditya Gopalan. Battle of bandits. In UAI, pp. 805-814, 2018.
Pannaga Shivaswamy and Thorsten Joachims. Coactive learning. Journal of Artificial Intelligence Research, 53:1-40, 2015.
Aleksandrs Slivkins al. Introduction multi-armed bandits. Foundations and Trends@ in Ma- chine Learning, 12(1-2):1-286 2019.
Mark Steyvers, Heliodoro Tejeda, Gavin Kerrigan, and Padhraic Smyth. Bayesian modeling of human-ai complementarity. Proceedings of the National Academy of Sciences, 119(11): e2111547119, 2022.
Eleni Straitouri, Lequn Wang, Nastaran Okati, and Manuel Gomez Rodriguez. Provably improving expert predictions with conformal prediction, 2022.
Yanan Sui, Yisong Yue, and Joel W Burdick. Correlational dueling bandits with application to clinical treatment in large decision spaces. arXiv preprint 1rXiv:1707.023711 2017a.
Yanan Sui, Vincent Zhuang. Joel W Burdick, and Yisong Yue. Multi-dueling bandits with dependent arms. arXiv preprint arXiv: / 700. 2017b.
Yanan Sui, Masrour Zoghi, Katja Hofmann, and Yisong Yue, Advancements dueling bandits. In IJCAI, pp. 5502-5510, 2018
Qian Yang, Alex Scuito, John Zimmerman, Jodi Forlizzi, and Aaron Steinfeld. Investigating how experienced ux designers effectively work with machine learning. In Proceedings of the 2018 Designing Interactive Systems Conference, pp. 585-596, 2018
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1538-1556 2012.
A SUPPLEMENTARY PROOFS
Lemma 1. Any human that selects uniformly at randomly with probability 6 0 amoog k 2 arms incurrs regret ST(T) that is increasing in
Proof. Suppose that k arms are presented and the human selects randomly with probability 8. Each of the presented arms has at least 2 probability of being selected. This chance could be higher, the human selects according to some other strategy, but 8 is lower bound, We can similarly lower bound regret by assuming that the algorithm (in each round) is optimal and selects the top arms to present to the human.
because with probability
Then, expected regret in given round is lower bounded by by:
8
A
2
8
A
k
k
2
11

---

Under review as a conference paper at ICLR 2023
which gives an overall lower bound regret by given by:
T k 2
For > 0, 2 2, this gives regret that is linear in T'
In(t) Lemma 2. Consider arm with Di,t 2 a² 22.27 for [0,0.5], 2
Then, if any UCB
algorithm selecting according UCBrt Pug + a probability at least
In(t] ne,
Then, UCBi, UCBo, with
z..
Proof.
In(t)
UCB Pig ta.
Ri,1
In(() 62 A
Titt 2 0² In(1))
$ iug +
a² 22-1n -n((t)
2 A
< C.
In(1)
In(t) A7
+
10s Mel 5 V
S
a² (l(() Se e A, probability 1 [2
mist
Po
es 0.5
In(1)
< B..
14 S jua + o.
with probability 1 f
V
ni.
Overall, this inequality holds with probability at least
12


Reviews:
[{"review_id": "meQA4aPja9g", "reviewer": "Reviewer_Skb5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper considers joint human-algorithm system in multi-armed bandits. The authors explore multiple possible frameworks for human objectives and provide theoretical regret bounds. They also give experimental results which show how regret varies with the human decision-maker’s objective and the number of arms.", "summary_of_the_review": "This paper considers a very interesting and well-motivated problem, i.e., a joint human-algorithm system in multi-armed bandits. But the formulation considered in this paper is too simple, which makes the theoretical analysis in this paper too standard (very similar to classic UCB analysis). The unique challenge of joint human-algorithm system is not well captured and analyzed in this paper. The writing of this paper looks causal, and needs to be improved. For these reasons, I give rejection.\n\n=========\n\nThank the authors for their response. I think this problem is well-motivated and worth a deeper analysis. The current formulation and analysis is too simple to fully capture the interesting insights and unique challenges of human-algorithm decision making. I think this work can be significantly improved by using theoretically deeper formulation and analysis. Therefore, I keep my score.", "strength_and_weaknesses": "Strengths:\n\n1. The considered joint human-algorithm system in multi-armed bandits is very interesting and well-motivated.\n\nWeaknesses:\n\n1. While the considered joint human-algorithm system in multi-armed bandits is a very interesting and well-motivated problem, the formulation for this human-algorithm system in this paper is too simple. Specifically, the formulation just considers a simple combination of selecting the empirical best arm and selecting the optimistic best arm (according to the classic UCB algorithm). Under this simple formulation, the joint human-algorithm system does not bring too many challenges to the original multi-armed bandit problem. \n\n2. The theoretical analysis and results in this paper are similar to those in the classic multi-armed bandit works, e.g., the upper confidence bound-based analysis and the empirical myopic analysis. It is unclear to me what unique challenges the joint human-algorithm system impose on the theoretical analysis in this paper.\n\n3. The writing of this paper seems causal. There are several blanks and typos.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VKppiOjxH3", "reviewer": "Reviewer_c8Yy", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper considers a human-algorithm collaborative framework in bandit problems. In this framework, the algorithm will first pick several candidate arms based on its picking rule, and then the human will choose one arm in this candidates to pull, based on his/her choosing rule. In this paper, the authors mainly consider the case that both the human and the algorithm are running UCB-type algorithms, i.e., their decisions are made based on the upper confidence bounds of all the arms (with different parameter $\\alpha_h$ and $\\alpha_a$). In this case, they show that when both $\\alpha_a$ and $\\alpha_h$ are large enough (e.g., larger than 1), then the regret of the system is at most the same as the worse one (either the human or the algorithm). On the other hand, if $\\alpha_h = 0$ (i.e., the human is totally greedy), then the regret of this system is linear with $T$, as long as the algorithm must provide at least 2 candidate arms to the human. Finally, the authors use some experimental results to demonstrate their theoretical findings. ", "summary_of_the_review": "Overall, I do not think the contribution of this paper is enough for an ICLR submission. ", "strength_and_weaknesses": "Strength\n\n1. The human-algorithm collaborative framework plays an important role in machine learning researches.\n\nWeakness\n\n1. The algorithm seems to be useless in the system.\n\nWhen $\\alpha_h = 0$, it is showed that the regret is linear with $T$, even if there is an algorithm that controls the candidate arms. Though this regret can be better than the only-human case, we do not want to regard it as an efficient framework.\n\nWhen $\\alpha_h \\ge 1$, according to Theorem 1, the algorithm can only make the regret upper bound worse (or at least the improvement is limited).\n\nThen my question is, why we must use such a human-algorithm collaborative framework is these examples? Why not get rid of the algorithm and only let the human make decisions?\n\n2. The theoretical contribution of this paper is limited.\n\nThe theorems and lemmas in this paper seem trivial. I read the full proofs, but I do not see any new techniques or novel insights within them. They are just tranditional UCB-based analysis and there seem to be no technical challenges.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Fa0SPiVlz_", "reviewer": "Reviewer_PnxP", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper considers the problem of reward maximization in human-algorithm coorperation situation. The paper provides a policy and theoretical analysis. Then the paper shows some experiment results.", "summary_of_the_review": "This paper is not ready to be published.", "strength_and_weaknesses": "Strength:\n* The problem of human-algorithm coorperation is interesting. The authors provide sufficient literature on such problem.\n\nWeaknesses:\n* The problem formulation is quite standard, which provides narrow space to make contributions.\n* Section~3.2 only introduces the part of a policy for \"human\", and I don't see the other part for \"algorithm\" (or assumptions on how the \"algorithm\" will behave). So I don't understand what the theoretical analysis and the regret results are for.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "9pj9FlgISPT", "reviewer": "Reviewer_DhuT", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper is about a model of sequential decision-making in which the algorithm is only allowed to select a subset of the possible options, and a human user is then required to choose one among them. The authors analysed theoretically the case in which both the agents (algorithm and human) are both relying on a Hoeffding-like bound to select the options. Finally, they present some synthetically generated experiments to evaluate the performance of the UCB-like algorithm when different numbers of arms are shown to the user.", "summary_of_the_review": "The paper presents a novel setting, but the authors did not succeed in providing a deep analysis of it.", "strength_and_weaknesses": "I think that the motivating example provides an interesting setting in which the research is still somehow missing a deeper analysis. However, the arguments and analysis of the authors do not seem to be complete enough yet for publication at ICLR. In my opinion, the author should focus more on the setting, for instance analysing the lower bound on the regret before proposing algorithms.\n\nMoreover, I think that the regret defined by the authors does not reflect the fact that the user might have different goals. I think that the modeling in this aspect may be revised and improved.\n\nFinally, the experimental results are not convincing at all. Indeed, they are on a too narrow set of settings, and statistical significance is not provided in most of the cases.\n\nLemma 1: Increasing in K is a bit generic. What is the dependence on this parameter?\n\n\n\nMinor:\nRemove all the contractions like isn't and doesn't\n\nI think that in the literature review, you should also mention and discuss the corrupted bandit setting. For instance,\n\nGajane, Pratik, Tanguy Urvoy, and Emilie Kaufmann. \"Corrupt bandits.\" EWRL (2016).\n\nZhao, Heyang, Dongruo Zhou, and Quanquan Gu. \"Linear contextual bandits with adversarial corruptions.\" arXiv preprint arXiv:2110.12615 (2021).\n\nand literature therein cited.\n\nDefine a symbol for regret.\n\nPlease provide the comments on Theorem 1 after it has been stated.\n\nTheorem 1: It is not clear to me where did you use the fact that \\alpha_h > 1 and \\alpha_a > 1\n\nTheorem 2: Does this regret match the theoretical lower bound? Is it possible to show that this is the best one might do in this setting?\n\nAssuming the shaded areas are the confidence intervals for the analysed mean regret (it is not clearly stated in the text), I think that the results provided are not statistically significant.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject