Bandit Learning with Delayed Impact of Actions
Authors: Wei Tang
Chien-Ju Ho
Yang Liu
Venue: NeurIPS 2021 Poster (2021)
Keywords: action delay impact
bandit learning

Abstract: We consider a stochastic multi-armed bandit (MAB) problem with delayed impact of actions. In our setting, actions taken in the past
impact the arm rewards in the subsequent future. This delayed impact of actions is prevalent in the real world. For example, the capability to pay back a loan for people in a certain social group might depend on historically how frequently that group has been approved loan applications. If banks keep rejecting loan applications to people in a disadvantaged group, it could create a feedback loop and further damage the chance of getting loans for people in that group. In this paper, we formulate this delayed and long-term impact of actions within the context of multi-armed bandits. We generalize the bandit setting to encode the dependency of this ``bias" due to the action history during learning. The goal is to maximize the collected utilities over time while taking into account the dynamics created by the delayed impacts of historical actions. We propose an algorithm that achieves a regret of $\tilde{O}(KT^{2/3})$ and show a matching regret lower bound of $\Omega(KT^{2/3})$, where $K$ is the number of arms and $T$ is the learning horizon. Our results complement the bandit literature by adding techniques to deal with actions with long-term impacts and have implications in designing fair algorithms.

Bandit Learning with Delayed Impact of Actions
Wei Tang', Chien-Ju Ho', and Yang Liu" Washington University in St. Louis, "University of California, Santa Cruz {w. tang, chienju. ho @Qwustl.edu yangliuducsc. edu
Abstract
We consider stochastic multi-armed bandit (MAB) problem with delayed impact actions. In our setting, actions taken in the past impact the arm rewards the subsequent future. This delayed impact of actions is prevalent in the real world. For example, the capability to pay back a loan for people in a certain social group might depend historically how frequently that group has been approved loan applications. If banks keep rejecting loan applications to people a disadvantaged group, it could create feedback loop and further damage the chance of getting loans for people in that group. In this paper, we formulate this delayed and long- term impact of actions within the context of multi-armed bandits. We generalize the bandit setting to encode the dependency of this "bias" due to the action history during learning. The goal is maximize the collected utilities over time while taking into account the dynamics created by the delayed impacts of historical actions. We propose an algorithm that achieves a regret of Ö(K72/3) and show a matching regret lower bound of Q KT2233), where is the number of arms and T' is the learning horizon. Our results complement the bandit literature by adding techniques to deal with actions with long-term impacts and have implications in designing fair algorithms.
Introduction
Algorithms have been increasingly involved in high-stakes decision making. Examples include approving/rejecting loan applications [23 37], deciding on employment and compensation [5] [9] and recidivism and bail decisions M. Automating these high-stakes decisions has raised ethical concerns on whether it amplifies the discriminative bias against protected classes (52 14. There have also been growing efforts towards studying algorithmic approaches to mitigate these concerns. Most of the above efforts have focused static settings: to ensure her actions satisfy some fairness criteria at the decision time, without considering the fong-term impacts of actions. However, in practice, these decisions may often introduce leng-term impacts the rewards and well-beings for the human agents involved. For example,
decision maker needs
A regional financial institute may decide on the fraction of loan applications from different social groups to approve. These decisions could affect the development of these groups: The capability of applicants from group pay back loan might depend on the group's 's socio-economic status, which is influenced by how frequently applications from this group have been approved 6 [
The police department may decide on the amount of patrol time or the probability of patrol in neighborhood (primarily populated with demographic group). The likelihood to catch crime in neighborhood might depend on how frequent the police decides to patrol this area 28
These observations raise the following concerns. If being insensitive with the long-term impact of actions, the decision maker risks treating a historically disadvantaged group unfairly. Making things worse, these unfair and oblivious decisions might reinforce existing biases and make harder to observe the true potential for a disadvantaged group. While being a relatively under-
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

explored (but important) topic, several recent works have looked into this problem of delayed impact of actions in algorithm design. However, these studies have so far focused on understanding the impact in a one-step delay of actions 45
36
31, or sequential decision making setting without
uncertainty 47
20 67
Our work departs from the above line of efforts by studying the long-term impact of actions in sequential decision making under uncertainty. We generalize the multi-armed bandit setting by introducing the impact functions funaci,functions that encode the dependency of the "bias" due to the action history of the learning to the arm rewards. Our goal learn to maximize the rewards obtained over time, in which the rewards' evolution could depend on the past actions.
The History-dependee particular, we first show that applying standard bandit algorithms leads to linear regret, i.e., existing approaches will obtain low rewards with a biased learning process. To address this challenge, under relatively mild conditions for the dependency dynamics, we present an algorithm, based on a phased- learning template which smoothes out the historical bias during learning, that achieves a regret of OKT2//3) Moreover, we show matching lower regret bound of (KT2)) that demonstrates that our algorithm is order-optimal. Finally, we conduct a series of simulations showing that our algorithms compare favorably to other state-of-the-art methods proposed in other application domains. From a policy maker's 's point of view, our paper explores solutions to learn the optimal sequential intervention when the actions taken in the past impact the learning environment in an unknown and long-term manner. We believe our work nicely complements the existing literature that focuses more on the "understanding" of the dynamics 3
reward structure makes our problem substantially more challenging. In
Related work. Our work contributes to algorithmic fairness studied in sequential settings. Prior works either study fairness in sequential learning settings without considering long-term impact of
actions KE 49
30 5e or explore the delayed impacts of actions with focus addressing the
one-step delayed impacts or sequential learning with full information
K3 45 33
[1 T8 20] Our
work differs from the above and studies delayed impacts of actions sequential decision making under uncertainty. Our formulation bears similarity to reinforcement learning since our impact
function encodes memory (and is in fact Markovian 3 62) ), although we focus on studying the
tradeoff in bandit formulation. Our learning formulation builds on the rich
Our in that we also assume the Lipschitz reward structure and consider combinatorial action space. There
bandit learning literature 42 E and related to non-stationary bandits [60] 4
38
techniques share similar insights with I Lipschitz bandits [39 59 and combinatorial bandits [K]
are also recent works that have formulated delayed action impact in bandit learning (50 KS) but in all of these works, the setting and the formulation are different from the ones we consider in the present work. More discussions on related work can be found in Appendix A
2 Problem Setting
We formulate the setting in which institution sequentially determines how to allocate resource to different groups. For example, a regional financial institute may decide on overall frequency of loan applications approve from different social groups The police department may decide on the amount of patrol time allocated to different regions.
The institution is assumed to be a utility maximizer, aiming to maximize the expected reward associated with the allocation policy over time. If we assume the reward" for allocating a unit of resource to a group is i...d. drawn from some unknown distribution, this problem can be reduced to standard bandit problem, with each group representing an arm. The goal of the institution is then to leam sequence of arm selections maximize its cumulative rewards.
In this work, we extend the bandit setting and consider the delayed impact of actions. Below we formalize our setup which introduces impact functions to bandit framework.
Action space. There are K base arms, indexed from A K, with each base arm representing a group. At each discrete time t, the institution chooses an action, called a meta arm, which specifies
1 'The reward could be whether a crime has been stopped or whether the borrower pays the monthly payment on time. For applications that require longer time periods to assess the rewards, the duration of a time step, i.e., the frequency to update the policy, would also need to be adjusted accordingly.

---

the probability to activate each base arm. Let P = A[[]] be the (K - 1) -dimensioona probability simplex. We denote the meta arm as p(t) {pi (t). ................................ ((t))....PP(())) (t)} E P. Each base arm k is activated independently according to their (t) in p(t). The institution only observes the reward from the arms that are activated. Our feedback model deviates slightly from the classical bandit feedback and shares similarity to combinatorial bandits: instead of assuming always observing one arm's 's reward each time, we observe the reward of one arm in expectation, i.c., we can potentially observe no arm's reward or multiple arms' rewards. This modeling choice is mainly needed to resolve a technicality issue and has been adopted in the literature (65 13.. Most of our algorithms and results extend to the case where only one arm is activated according to pt))
Remark 2.1. We can also interpret the meta-arm as specifying the proportion of resources allocated to each base arm. The interpretation impacts the way the rewards are generated (i.e., instead of observing the rewards of the realized base arms, the institution observes the rewards of all base arms with non-zero allocations.) Our analysis utilizes the idea of importance weighting and could deal with both cases in the sume framework. To simplify the presentation, we focus on the case of interpreting the meta-art arm as probabilities, though our results apply both interpretations.
Delayed impacts of actions. We consider the scenario in which the rewards of actions are unknown a priori and are influenced by the action history. Formally, let H(() - {p())) be the action history at time t. We define the impact function f(t) = F(H((t) to summarize the impact of the learner's actions to the reward generated in each group, where F(-) is the function mapping the action history to its current impact on arms' rewards. the following discussion, we make F-) implicit and use the vector f(t)= = (t)........ ft) to denote the impact to each group, where (t) captures the impact of action history to arm k.
Rewards and regret. The reward for selecting group k at time depends on both pt((t) and the historical impact (t). In partieular, when the arm representing group k is activated, the institution observes a reward (the instantaneous reward is bounded within [0. 1)) drawn i.i.d. from a unknown distribution with mean r' (f)( [0, 1] and claims the sum of rewards from activated arms as total rewards. (-) is unknown priori but is Lipschitz continuous (with known Lipschitz constant LA E (0, IJ) with respect to its input, i.e., small deviation of the institution's 's actions has small impacts on the unit reward from each group. When action p(4 is taken at time I, the institution
obtains an expected reward
Up((()) = Σ Pa()) TA (fa(I))
(1)
k=
As for the impact function, we focus on the setting in which f(t is a time-discounted average, with each component (t) defined as
fxe(t) En= pa(s)
(2)
-i=170-
where y E [0, 1) is the time-discounting factor. D Intuitively, (x( is weighted average with more weights on recent actions. We would like to highlight that our results extend to more general family of impact functions and do not require the exact knowledge of impact functions (see discussion in Section 5.2). We also note that when y = O, our setting reduces to a special case where the impact function only depends on the current action pa (t) (action dependent), instead of the entire history of actions (discounted by 0 right away). We study this special case of interest in Section
Let A be the algorithm the institution deploys. The goal of A is to choose a sequence of actions {p(t)) that maximizes the total utility. The performance of A is characterized by regret, defined as
T
Reg(T)= = sup
Σ
U.(P))
Σ v.CD(o)).
pEP
where the expectation is taken on the randomness of algorithm A and the utility realization f
2 'The upper bound becomes 0(x44512/3) which is slightly worse than (KT2/33 in K. But the upper bound is still tight in T'. We provide discussions in Remark D.6
3 'eere we follow the tradition to define 0 when y 'In this paper, we adopt the standard regret definition and compare against the optimal fixed policy. Another possible regret definition is to compare against the optimal dynamic policy that could change based the
3

---

2.1 Exemplary Application of Our Setup
We provide an illustrative example to instantiate our model. Consider a police department who needs to dispatch number of police officers to K different districts. Each district has a different crime distribution, and the goal (absent additional fairness constraints) might be maximize the number of crimes caught [22]- Fl The effects of police patrol resource allocated to each district may aggregate over time and then impact the crime rate of that district. In other words, the crime rate in each district depends on how frequently the police officers have been dispatched historically in this district.
To simplify the discussion, we normalize the expected police resource be one unit. Each district k has a default average crime rate F& E (0, 1) at the beginning of the learning process. This crime rate can (at most) be decreased to I E FR). All of these are unknown the police department. The police department makes resource allocation decision at each time step. We use rx(() E (0, 1) to denote the crime rate in district it time t, taking into account the impact of historical decisions. Assume P& (t) is the amount of police resource dispatched to district & at time t 'E (x( = 1 for all f), the expected number of crimes caught at district l at time / would be p& (t). Note that here (t) can be interpreted as the probability of allocating police resource (randomly sending the patrol team to each of the K districts) or the fraction of allocated police resource.
Below we provide one natural example of the interaction between the impact function and the reward. At time step + 1, let (t) == {px ..),,............ pk (t)} denote the historical decisions of the police department for district k. Now given Ha (t+ = (H&(() Up) (t + 1)} where pa (t + 1) is the current decision for district k assume that the crime rate at time + district l is in the following form:
(t + 1) Tx - (u( + 1)) x (7x Ix):
(4)
where fx(+): 1J - [0. 1J is the impact function that summarizes how historical actions would
impact the current crime rate. One possible example is fie(H((tt)) = E Pa))"" as we defined in
E
Equation 2 This impact function has two natural properties:
When (t)))((t) = 1 (e.g.. (s) 1, Vs S (). the police department keeps dispatching the police officers to district k with probability 1, then district &o will reach its lowest crime rate.
When fa (t)) + 0 (e.g., (s) + 0, Vs < t), the police department rarely dispatch police officers to district k The crime rate in district & will reach its highest level.
In this example, treating each district as arm and directly applying standard bandit algorithms might reach suboptimal solutions since the reward dynamic is not considered. In this paper, we develop algorithms that can take into account this history-dependent reward dynamic and achieve no-regret learning. Our results hold for a general class of impact functions (under mild conditions) and do not need to assume the exact knowledge of the impact function.
3 Overview of Main Results
We summarize our main results in this section. First, we present an important, though perhaps not surprising. negative result: if the institution not aware of the delayed impact of actions, applying existing standard bandit algorithms in our setting leads to linear regrets. This negative result highlights the importance of designing new algorithms when delayed impact of actions are present. The formal statement and analysis are in Appendix C
Lemma 3.1 (Informal). If the institution is wnaware of the delayed impact of actions, applying standard bandit algorithms (including UCB, Thompson Sampling) leads to linear regrets.
While the negative result might not be surprising, as it resembles similarity to the negative results on applying classic bandit algorithm to a non-stationary setting, it points out the need to design new algorithms for settings with delayed impact of actions. The key challenge introduced by our setting is in estimating the arm rewards: when pulling the same meta arm at different time steps, the institution
history. However, calculating the optimal dynamic policy in our setting is nontrivial as it requires to solve an MDP with continuous states.
As discussed by Elzayn et al. 22 there might be other goals besides simply catching criminals, including preventing crime, fostering community relations, and promoting public safety. We use the same goal they adopted for the illustrative purpose.

---

does not guarantee to obtain rewards drawn from the targeted distribution according to the chosen meta arm, as the arm reward depends on the impact function ft). To address this challenge, we note that if the institution keeps pulling the same meta-arm repeatedly, the impact function (and thus the arm reward associated with the meta-arm) would converge to some value. This observation leads to our approaches. We first develop bandit algorithm that works with impacts that converge "immediately" (or equivalently only depend on "immediate" actions, echoing the case with y = in Equation 2 We then propose a phased-learning reduction template that reduces our general setting to the above one and achieves a sublinear regret.
Theorem 3.2 (Informal). There is an algorithm that achieves an optimal regret bound ((KT233) the bandit problem with the impact function defined in Equation 2 In addition, there a matching lower bound of Dd 2(KT2/3).
To provide an overview of our approaches, we start with action-dependent bandits (Section P.. where the impact at time depends only on the action at I, i.e., f(() = p((), namely Y 0 in Equation 2 This setting not only captures the one-step impact but also offers a backbone for the phase-lcamiing template for the general depeededd scenario. In this setting, when meta-arm p = {p PK] is selected, each base arms is activated with probability pk. and the institution observes the realized rewards for all activated base arms and receives the sum of them as total rewards. Since we know the probability Pk for activating each base arm, we may apply importance weighting to simulate the case if the learner is selecting K probabilities and obtain K signals at each time step. This interpretation transforms our problem structure to a setting similar to combinatorial bandits. Furthermore, since both r-).) are Lipschitz continuous, to discretize the continuous space of each Pk- With these ideas combined, we design a UCB-like algorithm that achieves a regret of (l
adopt the idea from Lipschitz bandits
With the solution of action-dependent bandits, we explore the general history-dependent bandits with impact functions following Equation 2 (Section 53. The main idea is to divide total time rounds into phases, and then selecting the same actions in each phase to smooth out impacts of historically made actions, which will then help reduce the problem to an action-dependen one. One challenge to construct appropriate confidence bound and adjust the length of each phase to account for the historical action bias. With a careful combination with our results for action-depender bandits, we present an algorithm which can also achieve regret of the order (KKT2/3). We further proceed to show that this bound is tight and provide numerical experiments.
4 Action-Dependent Bandits
In this section, we study action-dependent bandits, in which the impact function f(() p()), corresponding to 7 0 in Equation ( Our algorithm starts with discretization over the space P. Formally, we uniformly discretize [0, 1] for each base arm into intervals of a fixed length e, with carefully chosen such that I/e is an positive integer Let P. be the space of discretized meta arms, i.c., for each p .P }K} Pe. ΣK Pk and p E {c, 2e, 1} for all k.
Let P := sup suppEP, Ex= Ph T& (px) denote the optimal strategy in discretized space Pe. After meta arm p(!) = (I), Px
px()) ( E Pe is selected, each arm k is independently activated with probability (t). From now, we use Fe(-) to denote the realization of corresponding reward. The learner observes activated arms, and observes the instantancous reward ig (t)) of each activated arm k. We use importance weighting elements in p:
29 to construct the unbiased realized reward for each of the K
Rr (p) = {o. (t)(p(())/pa arm k is activated 0.
(5)
arm l is not activated
Since the probability activating arm k is (t),,, it is easy to see that (F) = (px
Given the suportance-weighted rewards (Fr (t))). we re-frame our problem as choosing a K- dimensional probability measure (one value for each base arm). In particular, for each base arm k. Pk will take the value from {c, .e,.....7 1}. and we refer to pk as the discretized arm.
Remark 4.1. The above anportance-weighttin technique enables us "observe" samples of rh (px) for all base arms k when selecting p = {pI,..., ,PK), }. This technique helps to bridge the gap between
6 Smarter discretization generally does not lead better regret bounds
39
5

---

the interpretation of whether p is a probability distribution or an allocation over base arms. Our following techniques can be applied in either interpretation.
Algorithm 1 Jaction-Dependee UCB
Input: K
2: Initialization: For each discretized arm, play an arbitrary meta arm such that this discretized arm is included (if the selection of the arm is realized, then simply initialize its reward to otherwise initialize it to the observed reward divided/reweighted by the selection probability).
3: for t [K/c] 1,... do
4: Select p(() = arg maxppe,, (CB where UCB,(P) is defined as in
5: Arm l is activated w.p. pı (t) and observe its realized reward (t)).
6: Update the importance- weightedd rewards (Fr (p& (f)) as in and update the empirical mean
(t)) for each base arm as in
7: end for
By doing so, our problem is now similar to combinatorial bandits, in which we are choosing K discretized arms and observe the corresponding rewards. Below we describe our UCB-like algorithm based on the reward estimation of discretized arms. We define the set (p(p)) = {s E [4] Ps. E p(s)} record all the time steps such that the deployed meta arm p(s) contains the discretized arm ps- We can maintain the empirical estimates of the mean reward for each discretized arm and compute the UCB index for each meta arm p E P.:
Fe(pk) E (Pk) (Pk))
K Int minp.ep ne (pk)
UC)
+
Σ Pk Fe(p)), PA Ep
(6)
where (P(kk) is the cardinality of set (pk).. With the UCB index in place, we are now ready to state The next theorem provides the regret bound of Algorithm
our algorithm in Algorithm [
Theorem 4.2. Let = (() The regret of Algorithm (with respect to the optimal arm in non-discretized P) is upper bounded as follows: Reg(T) = OKT22/ (In 133))
Proof Sketch. Similar to the proof's of the family of UCB-style algorithms for MAB, after an appro- priate discretization, we can derive the regret as the sum of the badness (suboptimality of meta arm) for all (discretized) suboptimal meta arm selection. However, this will cost us an exponential K in the order of final regret bound: this is because need to take the summation over all feasible suboptimal meta arms, which the number grows exponentially with K. To tackle this challenge, we focus on the derivations of badness via tracking the minimum suboptimal selections in the space of realized actions (base arms), which enables us to reduce the exponential to polynomial K. On a high level, our proof proceeds in the following steps:
In Step 1, we obtain a high probability bound of the estimation error for the expected rewards of meta arms after discretization.
In Step 2, bound the probability deploying a suboptimal meta when selected sufficiently many number of times, where we quantify such sufficiency via minprep ny (Pk), which is the minimum number of selection of discretized arm contained in a suboptimal meta
In Step 3 and Wrapping-up step, we bound the expected value of milpp nx(pk) ) and connect the regret for playing suboptimal meta arms p with the regret incurred by including discretized arms Pk $ P. which are not in optimal strategy (in discretized space).
Finally, the regret bound of Algorithm can be achieved by optimizing the discretization parameter.
Discussions Our techniques have close connections to Lipschitz bandits [16 50
and combinatorial bandits [I3 [2). Given the Lipschitz property of rx r-),), we are able to utilize the idea of Lipschitz
bandits discretize the strategy space and achieve sublinear regret with respect to the optimal strategy in the non-discretized strategy space. Moreover, we achieve significantly improved regret bound by utilizing the connection between our problem setting and combinatorial bandits. In combinatorial bandits, the learner selects K actions out of action space M at each time step, where [M] @(K/e)

---

in our setting. Directly applying state-of oh-the-art combinatorial bandit algorithms [33 in our setting would achieve an instance-indeepndent regret bound of (K (In (l)))) while we achieve a lower regret of (KTT2 TT)/3) The reason for improvement is that, for each base arm, regardless of which probability it was chosen, we can update the reward of the base arm, which provides information for all meta arms that select this arm with a different probability. This reduces the exploration and helps achieving the improvement. In addition to the above improvement, we would like to highlight that another of our main contributions is extend the action-dependent bandits to the problem of history-dependent bandits, as discussed in Section 5
Another natural attempt to tackle our problem is to apply EXP3 E. which achieves sublinear regret even when the arm reward is generated adversarially. However, note that the optimal policy in our setting could be a mixed strategy, while the "sublinear" regret of EXP3 is with respect to a fixed strategy. Therefore, when applying EXP3 over the set of base arms, still implies a linear regret in our setting. The other option is apply EXP3 over the set of meta arms. Since the number of meta arms is exponential in K, it would incur a regret exponential in K due to the size of meta arms.
5 History-Dependent Bandits
We now describe how to utilize our results for action-dependent bandits to solve the history-dependent bandit learning problem, with the impact function specified in Equation ( The crux of our analysis is the observation that, in deseeryddependent bandits, if the learner keeps selecting the same strategy P for a long enough period of time, the expected one-shot utility will be approaching the utility of selecting p in the action dependenn bandits. More specifically, suppose after time the current action impact for all arms is f(t) = p(*) (t) = (t), PK
( (t)}. Assume that the learner is interested in learning about the utility of selecting p {pI . PK) } next. Since the rewards are influenced by f(t), selecting p at time t ++1 does not necessarily give us the utility samples at (p)) Instead, the learner can keep pulling this meta arm for non-negligible consecutive rounds to ensure that f(l + 8) approaches p. Following this idea, we decompose the total number of time rounds T into [T/L] phases which each phase is associated with L rounds. We denote E [L...., | LJ] as the phase index and p(m) as the selected meta-arm arm in the m-th phase. To summarize the above phased-learning template:
In each phase m, we start with an approaching stage: the first S, rounds of the phase. This stage is used "move" f(1 + 8) with S 8 S 8a towards to p.
Phase
Phase 2
Plase mn
Time
In the second stage, namely, estimation stage, of each phase: the remaining L Sa rounds. This stage is used for collecting the realized rewards and estimating the true reward mean action p.
Approaching Stage: s, Estimation Stage: L- 5.
p(n)
Fig. I: We deploy p for all rounds m- th phases, therefore, we use p(n) = p to represent p(t) = p for simplicity.
Finally, we leverage our tools in action-dependent ban- dits to decide what meta arm to select in each phase.
Note that even if we keep pulling the arm i with the constant probability pk in the approaching stage, the action impact in the estimation stage is not exactly the same as meta arm we want to learn, i.e., f(t + s) # p for E (Sa, L). due to the finite length of the stage. However, we can guarantee all f(t + s) for s E (sa. L] is close enough to p by bounding its approximation error w.r.t p. The above idea enables a more general reduction algorithm that is compatible with any bandit algorithm that solves the action-dependent case. Let = (L sa)/L L be the ratio of number of rounds in estimation stage of each phase. We present this reduction in Algorithm 2 and graphical illustration in Figure]
5.1 Hestory- UCB
In this section, we show how utilize the reduction template to achieve Ö(KT2/3) regret bound for history-dependent bandits. We first introduce some notations. each discretized arm Pk. similar to action-dependent case, we define r I.m
For
We compare our results with tight regret bound achieved in Theorem 2 of [3] The detailed derivations are deferred to Appendix D.2.1
7

---

Algorithm 2 Reduction Template
1: Input: K.T; 7,
e P 1).1)..... Sa.
2: Input: A bandit algorithm A: History-Dependent UCB (Algorithm
3: Split all rounds into consecutive phases of I. 8a/(1 p) rounds each.
4: for m = L.... do
5: Query algorithm A for its meta arm selection p(m) P.
6: Each phase separated into two stages:
1). Approaching stage: t L(m 1) + 1, ...., [(m 1) Sai
2). Estimation stage: = L(m 1) + 8a + 1..... Lm.
7:
fort ((m 1) 1, ...... L(m 1) + Sa do
8:
Deploy the meta arm end for
9:
10:
for I-(m= 1) + 8a + 1, 1,..., Lm do
11:
Deploy the meta arm p:
12:
Collect the realized rewards it of activated arms to estimate the mean reward as in end for
14:
Update Uçat (p) as in
end for
{:: SE (IL+ sa, (L] where pk E p(), Vi E [ml] as the set of all time indexes till the end of phase m in estimation stages such that arm is pulled with probability pk. We define the following empirical peat (px) computed from our observations and the empirical utility U (p):
Pm (px)
Σ
Fe (s))
T ms
(p)
Pk Fm (Px), PAEP
Σ
(7)
nest (pt)
(pe)
where na (pk) = Im (px)) is the total number of rounds pulling arm & with probability pk in all
estimation stages, and Fs (.(pk out frequency (p(²)(s) (s)) sET. in the estimation stage an approximation for the discounted frequency right after the approaching stage.
(p( (s)) defined similarly as in Equation ( We use the smoothed-
We compute our UCB for each meta arm at the end of each phase. We define and
Algorithm 3
UCB
compute err == Ky* (L* + 1), the ap- proximation
1: Construct UCB for each meta arm p E Pe at the end of each phase m 1,2,.... as follows:
incurred after tempt to smooth out the historical ac- tion impact. With these preparations, we present the phased Distory-dependent UCB algorithm (in companion with Al- gorithm 2 in Algorithm 3 The main result of this section is given as follows:
K In (T.p) minprep n (pk)
UCB, (p) Tesst (p) err 3,
2: Select p(n + 1) arg max, UCB (p) with ties breaking equally.
Theorem 5.1. For any constant ratio p E (0,1) and E (0, 1), let ((In((p))(TT)))) and 8, (In((1/33 //////////// K)/ k))nn)) The regret of Algorithm 2 with Algorithm as input bounds as follows:
RTg(T)= = = OKK22/3 ((I(TT))\pp)
For constant ratio p. we match the optimal regret order for action-dependent bandits. When is smaller, the impact function "forgets" the impact past-taken actions faster, therefore less rounds in approaching stage would be needed (see s, 's dependence in 7) and this leads to larger p.
our Remark 5.2. The dependence of our regret on the phase length is encoded in p. When implementing algorithm (Section 7 calculate L via Sa given the ratio p. We also simulations of our algorithu on different ratios p. the results show that the performance of our algorithm are not sensitive w.r.t. specifying ps in practice, do not require the exact knowledge of p. instead we can afford to use a rough estimation of its upper bound to compute L..
est in superscript stands for esttimation stage.
8

---

DUCB
Dutt
DUC3
(a) Action-dependent
(b) 7 0.2
(c) y
(d) 7 = 0.6
Fig. 2: (a): Behavior of the different algorithms for action-dependent bandits. (h)-(d): Behavior of the different.
algorithms for history-dependent bandits on different 7.-
5.2 Extension to General Impact Functions
So far, we discuss settings when the impact function is specified as Equation 2 However, the same technique presented earlier can be applied for more general faailly of impact functions. In particular, as long as the impact function converges after the learner keeps selecting the same action, result holds. To be more precise, only require [(t) to satisfy the condition (t++t))-g(( gpx)) S 7 E (0, 1) when the learner keeps pulling arm k with probability Pi: for round. The function g(-) can be an arbitrary monotone function long it is continuous and differentiable, for example: g(x) = x. In fact, the property of f(t) is only used when we estimate how close is to g(p) after the approaching stage with repeatedly selecting p. For different f(t), we define new reward mean functions (.) = T1 (g())) and tune parameters and 8a accordingly to bound the approximation error for (p) - U+==(() (p) (change the Lipschitz constant). This way we can follow the same algorithmic template achieve similar regret.
Moreover, we do not require exact knowledge of the impact function f(t). We only require the impact functions to satisfy the above conditions for our algorithms/analysis to hold. With the same arguments, while we assume the reward function rx(-) fed with the same impact function f. our formulation generalizes to different impact functions for r*("). ) long these impact functions able to stabilize given a consecutive adoption of the desired action.
Matching Lower Bounds
For both action- and history-dependent bandit learning problems, we have proposed algorithms that achieve regret bound of Ō(K72/3) We now show the above bounds order-optimal with respect K and T, i.e., the lower bounds of action- and history-dependent bandits both (KKT)/3) as summarized below.
Theorem 6.1. Let > 2K and K 2 4, there exist problem instances that for our action- and history- dependent bandits, respectively, the regret for any algorithm A follows: inf Reg(T") > 2/KT2/33
For the lower bound proof of action eetionndependent bandits (included in Appendix FD, standard randomized problem instances construction used in combinatorial bandits and Lipschitz bandits and use information inequality to prove the lower bound. For history-dependent bandits, show that for general class of reward function rx(+)) which satisfies the proper property (see Definition G.T. solving history-dependent bandits is as least as hard as solving action-dependent bandits. Armed with the above derived lower bound of action-dependent bandits, we can then
we following the
conclude the lower bound of history-dependee bandits.
7 Numeric Experiments
We conducted a series of simulations to understand the performance of our algorithms. The detailed setups and discussion are in Appendix[] []] We first compare our algorithm with some baselines under action-dependent bandits and other non-stationary baselines under history-dependent bandits with different 7 (the parameter in time-discounted frequency). The results, as shown in Fig 2 demonstrate that our proposed algorithm consistently outperforms the baseline methods. We also note that the performance of our algorithm is relatively robust w.r.t. difference choices of 7, i.c., the time-

---

OeT gue-de
Du aquatre
OUT ARAAESEE
SW.CD
SMUCS
SILOCS
(a) K 3
(b) K
(c) K
(d) different ratio
Fig. 3: (a)-(c): Behavior the different algorithms on different K, the remaining parameters are the same with the simulations comparison on different K. (d): The performance of our algorithms on different ratios, we set K = 2 and remaining parameters are also same before.
discounting factor for the impact. One explanation is that our algorithm utilizes repeated pulling to smooth out historical bias. Given the exponential-decayine of pulling required for the impact to converge does not depend on y too heavily. As shown in our theoretical regret upper bounds, gamma can be absorbed with other numeric constants, and when the time horizon increases, the effect of gamma on our algorithm's performance is diminishing, which aligns with our empirical observation. We also examine arms and different ratios The results, as in Figure 3 show that our algorithm outperforms other baselines when K goes large. Furthermore, in our regret bounds (see Theorem 5.I). the regret scales linearly w.r.t K. Though the presented results absorb other numeric constants, it is expected see that the slope of the regret curve is proportionally increasing along with increasing K. The results also suggest that our algorithm is not sensitive to different p. though one could see the regret slightly lower when p is increasing, which is expected from our regret bound.
nature of time discounting, the amount
algorithm with larger number of base
8 Conclusion and Future Work
We explore a multi-armed bandit problem in which actions have delayed impacts to the arm rewards. We propose algorithms that achieve a regret of ((K22/3) and provide a matching lower regret bound of (2KK2333) Our results complement the bandit literature by exploring the action history dependent biases in bandits. While model have its limitations, it captures important but relatively under-explored angle in algorithmic fairness, the long-term impact of actions sequential learning settings. We hope study will open more discussions along this direction.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their valuable comments. This work supported in part by the Office of Naval Research Grant 100014-20-1-22444 and the National Science Foundation (NSF) FAI program in collaboration with Amazon under grant IIS-1939677 and IIS-2040800.
References
[1] Angwin, J., Larson, J., Mattu, S., and Kirchner, L. Machine bias. ProPublica, May, 23:2016. 2016.
[2] Audibert, J.-Y, and Bubeck, Regret bounds and minimax policies under partial monitoring. Journal of Machine Learning Research, 11:2785-2833 2010.
[3] Auer, P., Cesa-Bianchi, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235 256, 2002.
[4] Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
[5] Bartik, A. and Nelson, S. Credit reports resumes: The incidence of pre-employment credit screening. 2016.
[6] Bartlett, R., Morse, A., Stanton, R., and Wallace, Consumer-lending discrimination in the of fintech. Unpublished working paper. University of California, Berkeley, 2018.
10

---

[7] Bechavod, Y., Ligett, K., Roth, A., Waggoner, B., and Wu, S. Z. Equal opportunity in online classification with partial feedback. In Advances in Neural Information Processing Systems, pp. 8972-8982, 2019.
[8] Besbes, O., Gur, Y., and Zeevi, Stochastic multi-armed--andee problem with con-statinnary rewards. In Advances in neural information processing systems, pp. 199-207, 2014.
[9] Besbes, O., Gur, Y., and Zeevi, A. Non-stationary stochastic optimization. Operations research, 63(5):1227-1244, 2015.
[10] Cella, I.. and Cesa-Bianchi, N. Stochastic bandits with delay-dependent payoffs. In International Conference Artificial Intelligence and Statistics, pp. 168-1177. PMLR, 2020.
[11] Cesa-Bianchi, N. and Lugosi, G. Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 140414044440 1422, 2012.
[12] Chen, W., Hu, W. Li. F., Li, J., Liu, Y., and Lu, P. Combinatorial multi armed bandit with general reward functions. In Advances in Neural Information Processing Systems, pp. 1659- 1667, 2016.
[13] Chen, W., Wang, Y. Yuan, Y., and Wang. Q. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. The Journal of Machine Learning Research, 17 (1):1746-1778, 2016.
[14] Chouldechova, A. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153-163, 2017.
[15] Combes, R., Shahi, M. S. T. M., Proutiere, A., et al. Combinatorial bandits revisited. In Advances in Neural Information Processing Systems, pp. 2116 2124, 2015.
[16] Combes, R., Proutière, A., and Fauquette, A. Unimodal bandits with continuous arms: Order- optimal regret without smoothness. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(1):1-28, 2020.
[17] Cortes, C., DeSalvo, G., Kuznetsov, V., Mohri, M., and Yang, S. Discrepancy-based algorithms for non-stationary rested bandits. arXiv preprint arXiv:1710.1065 2017.
[18] Cowgill, B. and Tucker, C. E. Economics, fairness and algorithmic bias. preparation for: Journal of Economic Perspectives, 2019.
[19] Cowgill, B. and Zitzewitz, E. Incentive effects of equity compensation: Employee level evidence from google. Dartmouth Department of Economics working paper, 2009.
[20] Amour, A., Srinivasan, H., Atwood, J., Baljekar, P., Sculley, D., and Halpern, Y. Fairness is not static: deeper understanding of long term fairness via simulation studies. In Proceedings of the 2020 Conference Fairness, Accountability, and Transparency, pp. 525-534, 2020.
[21] Duran, S. and Verloop, I. M. Asymptotic optimal control of markov-modulaan restless bandits. Proceedings of the ACM Measurement and Analysis of Computing Systems, 2(1):1-25, 2018.
[22] Elzayn, H., Jabbari, S., Jung, C., Kearns, M., Neel, S., Roth, A., and Schutzman, Z. Fair algorithms for learning in allocation problems. In Proceedings of the Conference Fairness, Accountability, and Transparency, pp. 170-179, 2019.
[23] Fuster, A., Goldsmitth-innkham P., Ramadorai, T., and Walther, A. Predictably unequal? the effects of machine learning on credit markets. 2018
[24] Gael, M. A., Vernade, C., Carpentier, A., and Valko, M. Stochastic bandits with arm-dependent delays. In International Conference on Machine Learning, pp. 3348-3356 PMLR, 2020.
[25] Garivier, A. and Moulines, E. On upper-confidence bound policies for switching bandit problems. In International Conference on Algorithmic Learning Theory, pp. 174-188, 2011.

---

[26] Gelman, A., Fagan, J., and Kiss, A. An analysis of the new york city police department's s "stop-and- and--risfffsk" policy in the context of claims of racial bias. Journal of the American statistical association, 102(479):813-823, 2007.
[27]
Gillen, S., Jung, C., Kearns, M., and Roth, A. Online learning with an unknown fairness metric. In Advances Neural Information Processing Systems, pp. 2600-26000 2018.
[28] Goel, S., Rao, J. M., Shroff, R., et al. Precinct or prejudice? understanding racial disparities in new york city's stop-and-fris policy. The Anmals of Applied Statistics, 10(1):365-394, 2016.
[29]
Gretton, A., Smola, A., Huang, J., Schmitufull, M., Borgwardt, K., and Schölkopf, B. Covariate shift by kernel mean matching. Dataset shift in machine learning, 3(4):5, 2009.
[30] Gupta, S. and Kamble, V. Individual fairness in hindsight. In Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 005-806, 2019.
[31] Heidari, H., Nanda, V., and Gummadi, K. P. On the long-term impact of algorithmic decision policies: Effort unfairness and feature segregation through social learning. arXiv preprint drXiv:1903.01209, 2019.
[32] Ho, C.-J, Slivkins, A., and Vaughan, W. Adaptive contract design for crowdsoureing markets: Bandit algorithms for repeated principal-agent problems. Journal of Artificial Intelligence Research, 55:317-359, 2016.
[33] Hu, and Chen, Y. A short-term intervention for long-term faimesss in the labor market. In Proceedings of the 2018 World Wide Web Conference, pp. 1389-1398, 2018.
[34] Joseph, M., Kearns, M., Morgenstern, J. H., and Roth, A. Faimnsss in learning: Classic and contextual bandits. In Advances Neural Information Processing Systems, pp. 325-333, 2016.
[35] Joulani, P., Gyorgy, A., and Szepesvári, C. Online learning under delayed feedback. In International Conference on Machine Learning, pp. 1453-1461, 2013.
[36] Kannan, S., Roth, A., and Ziani, J. Downstream effects of affirmative action. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 240-248, 2019.
[37] Kleinberg, J., Ludwig, J., Mullainathan, S., and Sunstein, C. R. Discrimination in the age of algorithms. Journal of Legal Analysis, 10, 2018
[38] Kleinberg, R. and Immorlica, N. Recharging bandits. In 2018 IEEE 59th Anmual Symposium on Foundations of Computer Science, pp. 209-3192991 2018.
[39] Kleinberg, R., Slivkins, A., and Upfal, E. Multi-armed bandits in metric spaces. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 681-690, 2008
[40] Kocsis, L.. and Szepesvári, C. Discounted ucb. In 2nd PASCAL Challenges Workshop, volume 2, 2006.
[41] Kolobov, A., Bubeck, S., and Zimmert, J. Online learning for active cache synchronization, In International Conference on Machine Learning, pp. 5371-5380. PMLR, 2020.
[42] Lai, T. and Robbins, H. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
[43] Levine, N., Crammer, K., and Mannor, S. Rotting bandits. In Advances in neural information processing systems, pp. 3074-3083, 2017.
[44] Li, F., Liu, J., and Ji, B. Combinatorial sleeping bandits with faimess constraints. IEEE Transactions on Network Science and Engineering, 2019.
[45] Liu, L. T., Dean, S., Rolf, E., Simchowitz, M., and Hardt, M. Delayed impact of fair machine learning. In International Conference Machine Learning, pp. 3150-3158, 2018
[46] Liu, L. T., Wilson, A., Haghtalab, N., Kalai, A. T., Borgs, C., and Chayes, J. The disparate equilibria of algorithmic decision making when individuals invest rationally. In Proceedings of the 2020 Conference Fairness, Accountability, and Transparency, pp. 381-391, 2020.
12

---

[47] Liu, Y. Fair optimal stopping policy for matching with mediator. In Uncertainty in Artificial Intelligence, 2017.
[48] Liu, Y. and Ho, C.-J. Incentivizing high quality user contributions: New arm generation in bandit learning. In Thirly-Second AAAI Conference on Artificial Intelligence, 2018.
[49] Liu, Y., Radanovic, G., Dimitrakakis, C., Mandal, D., and Parkes, D. C. Calibrated fairness in bandits. Proceedings of the 4th Workshop on Fairness, Accountability, and Transparency in Machine Learning, 2017.
[50] Magureanu, S., Combes, R., and Proutiere, A. Lipschitz bandits: Regret lower bound and optimal algorithms. In Conference on Learning Theory, pp. 975-999. 2014.
[51] Mouzannar, H., Ohannessian, M. I., and Srebro, N. From fair decision making to social equality. Proceedings of the Conference on Fairnsss, Accountability, and Transparency, pp. 359-368, 2019.
[52] Obermeyer, Z., Powers, B., Vogeli, C., and Mullainathan, S. Dissecting racial bias in an algorithm used to manage the health of populations. Science, 366(6464):447-4555 2019.
[53] Ortner, R., Ryabko, D., Auer, P., and Munos, R. Regret bounds for restless markov bandits, In International Conference on Algorithmic Learning Theory, pp. 214-228, 2012.
[54] Patil, V., Ghalme, G., Nair, V., and Narahari, Y. Achieving fairness in the stochastic multi-armed bandit problem. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5379-5386, 2020.
[55] Pike-Burke, C. and Grünewälder, Recovering bandits. arXiv preprint urXiv:1910.143:: 2019.
[56] Pike-Burke, C., Agrawal, S., Szepesvari, C., and Grunewalder, Bandits with delayed, aggregated anonymous feedback. In International Conference on Machine Learning, pp. 4105-4113, 2018
[57] Schmit, S. and Riquelme, C. Human interaction with recommendation systems. In International Conference on Artificial Intelligence and Statistics, pp. 862-877777 870, 2018.
[58) Seznec, J., Locatelli, A., Carpentier, A., Lazaric, A., and Valko, M. Rotting bandits are no harder than stochastic ones. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2564-2572, 2019.
[59] Slivkins, A. Contextual bandits with similarity information. The Journal of Machine Learning Research, 15(1):2533-2555 22128338,66,,, 2014.
[60] Slivkins, A. and Upfal, E. Adapting to changing environment: the brownian restless bandits. In Conference on Learning Theory, pp. 343-354, 2008
[61] Tang, W. and Ho, C.-J. Bandit learning with biased human feedback. In Eighteenth International Conference on Autonomous Agents and Multi-Agent Systems, 2019.
[62] Tekin, C. and Liu, M. Online algorithms for the multi-armed bandit problem with markovian rewards. In Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2010.
[63] Verloop, I. M. et al. Asymptotically optimal priority policies for indexable and nonindexable restless bandits. The Annals of Applied Probability, 2674):194-11995, 2016.
[64] Vernade, C., Cappé, O., and Perchet, V. Stochastic bandit models for delayed conversions. arXiv preprint arXiv: 1e...17066.9666 2017.
[65] Wang, Q and Chen, W. Improving regret bounds for combinatorial semi-bandits with proba- bilistically triggered arms and applications. Advances in Neural Information Processing Systems, pp. 1161-1171, 2017.
13

---

[66] Zhang, X., Khaliligarekani, M., Tekin, C., et al. Group retention when using machine learning in sequential decision making: the interplay between user dynamics and faimesss In Advances in Neural Information Processing Systems, pp- 15243-15252, 2019.
[67] Zhang, X., Tu, R., Liu, Y., Liu, M., Kjellström, H., Zhang, K., and Zhang, C. How do fair decisions fare in long-term qualification? 2020.
14


Reviews:
[{"review_id": "xOscAunMYEo", "reviewer": "Reviewer_dTZk", "summary": "The authors formulate and solve the problem of resource allocation to K groups under the bandit setting where the impact of actions perseveres over time and affects the corresponding reward function. They key idea is to realize that deploying the policy for a certain period of time helps us estimate its utility and therefore mixing this with updating the policy helps us to learn the optimal one.  A regret bound of Otilde(KT^2/3) is shown with a matching lower bound. Experiments are shown on synthetic datasets comparing it with EXP3, DUCB and SWUCB to show the performance improvement in terms of cumulative regret. ", "questions": "", "limitations": "", "rating": 7, "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": "Overall, the paper is well-written and solves an important problem for the community.  In particular, it is concerned with resource allocation in delayed settings which are both challenging as well as critically important for healthcare, crime and financial domains. \n\nPros:\n\n(A) The problem is well-motivated by a crime example of deploying police officers to districts to reduce the rate of incidents. Also, applying standard algorithms is shown to lead to linear regret. These are typical in most of these settings but it is good to be formalized in Lemma 3.1\n(B) Similar to EXP3, we see the importance weighting being utilized to redefine the reward function of the observed arms so that the expected reward is maintained. \n(C) First the case where the impact functions are limited to the current selection are tackled and this is similar to UCB with the reweighted weights from above. The observation that history-dependent can then solved by utilizing the previous freeze and gather evidence and update the policy cycle is really nice and leads to an optimal regret. This is both theoretically and experimentally validated.\n\nCons/Questions:\n\n(1) The setting was a bit unclear to me from the delay perspective. So, the reward of say loan applications to a certain group will result in a certain reward but usually there is a delay in observing such rewards. Is it the case that we need both to have a better model? We have impact of the previous decisions affecting the current rewards and also the current rewards and not observed till some future date? \n(2) The issue with importance weighting, as we know, is that it can lead to high variance. How does your approach tackle the case where the policy has low probability for some of the arms? Could the usual tricks of having a biased estimator but lower variance help with this as we see with EXP3 -> EXP3-IX?\n(3) The regret is compared to a static policy and it would have been nicer if the regret performance was over the optimal dynamic policy.\n\nAfter rebuttal:\n\nThanks for the responses. I will keep my score unchanged as it clarifies the questions I had and is aligned with the other reviews as well.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "iaPmzIbzNur", "reviewer": "Reviewer_ZiMd", "summary": "The paper considers a bandit problem where actions have a discounted impact on future rewards. The authors propose an algorithm that achieves an $O(KT^\\frac{2}{3})$ regret bound, assuming that the reward function is Lipschitz and resorting to a discretization of the action space and a waiting time that enables the rewards to stabilize (the last actions are the one that will impact the rewards the most). They provide a matching lower bound.", "questions": "", "limitations": "", "rating": 7, "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": "## Originality \nDelayed rewards and rested bandits have already been studied, but the originality of this paper lies in the fact that the actions chosen at a certain time will impact their future rewards decreasingly (their rewards can decrease even at a time step when they are not pulled).\nOne of my concerns however is that it is the probability of choosing an arm that impacts its evolution. I do not understand in which practical case a probability of choosing an arm is key, rather than its effective choice. I would like the authors to clarify this point.\nAlso, I wonder what would happen, should the impact function structure depend on the arm (for example if the discount factor depended on the chosen arm)? This would maybe be a more realistic setting. \n\n## Quality\nThe upper bound of order of $T^{2/3}$ seems satisfactory and is supported by a matching lower bound.\nI am a little uncertain about the use of discretization. How should $\\epsilon$ be chosen? Is $\\epsilon$ a function of the Lipschitz constant? If so, this is an important limitation that should be discussed.\n\n\n## Clarity\nSome parts could be explained in more detail. The intuition behind the lower bound could be explained a little bit in the main paper for example, since it is a little expeditious as is.\nI think the paper would really benefit from a discussion of the choice of the length of the approaching stage. How is the learner supposed to set $\\rho$? How does it affect $L$?\n\n## Typos\n- I think $\\delta$ should be $\\gamma$, l118 and l172. \n- \"our model has its limitation\" l350\n\n## Edit\nI thank the authors for taking the time to write clear answers. The only drawback of the paper that I see is that the fact that probabilities of actions impact their evolution is justified by very specific applications. Let me be clear, these use cases make sense to me but I think they should really be justified more in detail in the final version. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The way the authors discuss the limitations of their work is satisfactory to me.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "dLuX9EB0Emf", "reviewer": "Reviewer_8ugy", "summary": "This paper investigates a bandit variant with the changing rewards. The rewards of actions depend on history information, which is very interesting and practical. The idea of combining epsilon-cover (to discretize the action space) and CMAB to design a learning algorithm is very novel. They provide an instance-independent regret upper bound and also a matching regret lower bound, which means their proposed learning algorithm has an order optimal regret guarantee.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "The paper is quite organized and written. It has several motivating applications included, which contributes to understanding the learning problem. I have some questions.\n\nI am wondering for some special problem instances, is  it possible to have instance-dependent regret bound (takes the O(1/Delta) form) and a matching regret lower bound? \n\nRegarding the content just above Section~5, I still cannot understand why EXP3 would fail. Can authors clarify more?\n\nRegarding the learning algorithm, is there any computational issue to find epsilon covers? If yes, is it possible to have advanced algorithm that does not have any computational issue?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see too much discussion about the negative impact of their proposed setting. However, I think the framework proposed has a positive impact on society such as how to dispatch police resources to reduce the crime rate.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "UmjG3fAhhie", "reviewer": "Reviewer_aHiG", "summary": "In this paper, the authors formulate and study a multi-armed bandit problem with delayed impact\nof actions, in which the actions are taken in the past affect the rewards in the future. Under this\nsetting, the authors design an algorithm that utilizes the dynamics introduced by the delayed\nimpacts of past actions to look for the optimal meta arm that maximizes the collected utilities\nover time. The algorithm is shown to incur regret of at most $\\Tilde{O}(KT^{2/3})$, which\nmatches the theoretical lower bound for this problem.", "questions": "", "limitations": "", "rating": 7, "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": "Strengths:\nThe paper is well written and structured. The model is novel in the current bandit's literature with\ndelayed impacts due to its consideration of long-term impacts. The paper provides good intuition\nas to the applications of MABs with long-delayed impacts (the example in Section 2 well\nillustrates the model set-up and the roles of the impact function). The theoretical results for both\naction-dependent and history-dependent bandits are well explained. In particular, Algorithm 2/3\nuses a simple idea that uses a short approaching stage to achieve the convergence of $f(t)$,\na longer estimation stage to estimate the reward of meta arm $p$, and a UCB-type algorithm to\nfind a good meta arm. The regret upper bound also matches the theoretical lower bound, which\ndemonstrates the optimality of the proposed algorithm.\n\nQuestions:\n- How would one determine the choice of $\\rho$ in Algorithm 2? Empirically, the authors\nargue that the choice of $\\rho$ does not influence the cumulative regret too much. But if\n$\\rho$ gets too small it seems that the theoretical upper bound worsens. Is there\nanything that prevents us from always selecting a large $\\rho$?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Weaknesses:\nOne limitation of the current paper is that most of the analysis on action-dependent and\nhistory-dependent bandits is done using the impact function in Equation (2). Although the\nauthors remark in Section 5.2 that similar analysis can be applied to impact functions that\nconverge when one keeps selecting the same meta arm, it is not clear how one should select\nthe monotone function $g(.)$ for a general impact function. Since this restriction does not really\napply to general functions, it might be better to state it as a formal assumption.\nIn the regret definition, the authors choose the optimal fixed policy instead of the stronger\noptimal dynamic policy as the benchmark. In Appendix H, the authors justify their choice by\narguing that for history-dependent bandits, the optimal strategy in the limit is well defined and\ncan be characterized as the best-in-hindsight policy. From the intuitive explanations, it is unclear\nto me why this holds and might need a more rigorous treatment.\n\nMinor comments:\n- On pages 3 and 4, “$\\delta = 0$” is a typo and should be $\\gamma = 0$.\n- In Section 4, it says that $p_k \\in \\{\\epsilon, 2\\epsilon, \\dots, 1\\}$. Can $p_k$ take the\nvalue of 0 as well?\n- It might be good to compare the performance of the algorithm of different $rho$ values\nagainst the benchmark algorithms. From Figure 3d alone, it is difficult to tell that the\nalgorithm is not sensitive to different values of $\\rho$.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "LQeO5wfxV2", "reviewer": "Reviewer_L6w5", "summary": "This paper generalizes the stochastic bandit model by redefining the action space as a sequence of resource allocations, with a time discounted action-dependent bias on future resource allocations. The authors provide an example application based on their model, and propose an algorithm with proved near optimal regret upper bound. A lower bound based on the proposed model is provided.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The paper is well written and easy to read, with many details fully explained. I also think that this idea is novel especially the time discounted action impact. Existing works focus more on long-term impact by reward history, for example current action is influenced by a feedback function on reward history, such as https://arxiv.org/pdf/1802.05693.pdf, while this paper considers long-term influence by an impact function on action history, which differs from previous works by new non-trivial problem formulation and policy design.\nI have one question: since the value of \\epsilon and s_a affect the regret, and they are required as inputs, I am wondering how to tune these values to make the regret under control, or if only we make sure that \\epsilon and s_a are in the orders as stated in Theorem 5.1, the we can guarantee a good regret regradless of the coefficients before the order? How can I get some clue when tuning the parameters?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the authors have adequately addressed parts of limitation and potential negative societal impact of their work. There could be some other limitations, such as a more general format of function f(), but that could also be a future work. My suggestion would be that the authors could consider adding more insights of why the current function f() look like that, and how to generalize it, so as to cover more applications.\nAnother tiny concern is that, in Line 118 & 172, I think it should be \\gamma instead of \\delta.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a novel bandit setting which is certainly of contemporary interest; the delayed impact of actions can well be an important consideration in applications like police patrol policies, and getting this right is important in light of the potential for negative societal impact. The reviewers were uniformly positive on this work. The authors clearly explain why direct application of previous approaches will not achieve the optimal regret, and they successfully devise an algorithm based on a simple intuition (repeatedly pulling the same meta-arm until rewards stabilize) which provably achieves the optimal regret. As this setting is new, another important contribution is proving a lower bound, which allows the authors to claim optimality.

I would like to briefly mention a few minor weaknesses, in the hopes that the camera-ready version of the paper can be stronger. First, essentially nothing is said in the main text about how the lower bounds are proved, and I agree with reviewer ZiMd that the paper's main text would benefit from including the intuition behind the lower bound. Also, similar to reviewer ZiMd, I found the assumption that it is the probability of choosing an arm that impacts the evolution of the arm's reward as odd in some situations. The authors' response to this point, about security games where the probabilities are revealed, does work, but this only makes sense for certain applications. Therefore, I suggest that the authors provide more justification (or at least discussion) of why it is the probability (and not the pulling of an arm itself) which influences the evolution of an arm’s reward.

Overall, this paper provides a very strong contribution and should be of interest not only to researchers in online learning but also the broader community given the motivation for this work. This paper would be a welcome contribution to the NeurIPS 2021 proceedings.
Decision: Accept (Poster)