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 funcci,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(-) 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
Fr (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 (P) = (px
Given the iuportance-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
(P)) 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 1/3))
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 ())))) 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 dependent 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)) is 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-dependentt 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++ 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 eeeionndependent 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-

---

Oer 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-frie 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 22128338566,,, 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...17068.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": "d4I6qczahX5", "reviewer": "Reviewer_oRvo", "summary": "This paper studies a multi-armed bandit problem where the past actions affect the future reward distribution of the arms. The authors propose an algorithm achieving $\\tilde O (KT^{2/3})$ regret in expectation (where K is number of arms and T is the horizon), and provide a lower bound of  $\\Omega (KT^{2/3})$. The authors accompanied the theoretical analysis with simulations.", "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": "Overall I find the paper well-written, the flow is clear and easy to follow. Under the formulation with the delayed impact of actions, the authors provide a good characterization on the expected regret minimization with matching upper and lower bounds. \nOne main concern I have is that I would like to see more explicit explanations and motivating examples on how the formulation in this work is connected to the related work on algorithmic fairness studied in sequential settings. The authors provide an example application in section 2.1 which is police example, and it is reasonable to consider that the future \"reward\" distributions can be affected by the past actions. However it is not very clear to me how this formulation is explicitly related to the fairness concern, e.g. common fairness criteria in related works [Fairness in Learning: Classic and Contextual Bandits, Roth et al 2016]?\nBesides, in consideration of the examples mentioned in the paper (such as loan application, policing): Although in these examples, it is clear that past actions can affect future reward distributions, I would like to see a bit more discussions on how the proposed algorithms might be able to apply in these applications. \n\nminor typos: \nline 118: delta is undefined\n\n--------------------------------------------------------------------------------------------------\nConsidering the authors' response, I decide to change my score from 5 to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors mentioned potential connections to algorithmic fairness and the long-term impact of actions in sequential learning settings. I would suggest adding more concrete discussions on how the framework in the paper can be instantiated with common social welfare and fairness notions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "_dHadopioEv", "reviewer": "Reviewer_i7rY", "summary": "This paper considers a multi-armed bandit problem with delayed impact of actions, where the present actions influence future rewards via an impact function. The goal is to maximize the cumulative reward over time considering the dynamics created by the delayed impacts of historical actions. Algorithms that are `fair' are designed to address this problem, and have tight regret bounds. Numerical simulations validate the performance improvements.\n\n\nThe action-dependency and its connection to fairness is interesting. A few questions and suggestion follow. \n", "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": "1a. Isn't Lemma 3 just a restatement of the well-known fact that any classical bandit algorithm applied to a non-stationary setting incurs a linear regret? \n1b. The `importance-weighting technique' in (5) is again a well-known method to infer unobserved rewards. \nThe authors should cite relevant papers and acknowledge the sources. \n\n2. The history-dependent setting needs more clarification. \nTo assess the reward and impact of an action (meta-arm), the authors propose repeatedly choosing the same arm to `forget' the history and resembles an action-dependent case. However, the reward so obtained also contains sliding-window effect (transients) owing to repeatedly using the same arm. So in a sense this reward is not truly assessing the impact one-arm but one-arm applied many times over different situations. \n\n3. The impact function proposed is co-ordinate wise is simplistic, which perhaps limits applications. Can the impact function handle correlations? For example, could a simple linear transform of the history of all arms affect the future arms rewards? How will the results change? \n\n4. The numerical section is weak. More effort should be expended to explain the results rather than mere reporting. \nFor example, \na. The performance of the proposed algorithm is unaffected by $\\gamma$. Why is it so? What does this mean?\nb. What explains the gap between the proposed algorithm and the second best algorithm for changing $\\gamma$? The reason provided is weak. \nc. What explains proportional dependence between the number of arms and the slope of the regret curve? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The related literature section should primarily highlight the similarities and key differences with the relevant streams like non-stationary, Lipschitz and combinatorial bandits. What are the main contributions of the paper in comparison with these streams? \n\nThe authors should also cite relevant literature instead as discussed before. Key references for well-known techniques are missing. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "GDNaXW4VRPn", "reviewer": "Reviewer_MXxs", "summary": "This work investigates a non-stationary variant of the multi-armed bandit problem, specifically considering a rested setting. They provide a lower bound to the proposed problem and a learning policy whose regret matches such a bound.\nFinally, synthetic experiments corroborates the theoretical findings.", "questions": "", "limitations": "", "rating": 6, "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": "Authors proposed a novel rested bandit setting. I do not see clear motivations why the proposed protocol involving meta-arms should represent the reality. I would rather expect the adoption of meta-arms to be a component of the designed policy and not part of the protocol (e.g. if considering non-deterministic policies). Can you motivate more about this?\n\nIn some paragraphs authors speak about fairness without formally defining it. I do not get what they mean when referring to that topic and in which sense they claim their work to belong to the algorithmic-fairness area.\n\nIn my opinion the key result is that their policy matches the lower-bound. That being said, I would like to have a proof sketch of Theorem 6.1 in the main body or to know which are the technical difficulties/challenges authors encounter when proving the theoretical guaranteees.\n\nThe writing is quite clear. I think there is a typo in line 118, $\\delta ==> \\gamma$.\n\nSOA\n\nI found the SOA not complete and not accurate. In line 71 authors have cited together [34,49]. But the first work considers payoffs to be parameterized by delays since the arm was last pulled. Along the exact same direction you have the work of [51] but the parametrization is now given in terms of the number of pulls and I would encourage to consider also the following works:\n\n- Stochastic bandits with delay-dependent payoffs. L Cella, N Cesa-Bianchi. International Conference on Artificial Intelligence and Statistics\n\n- Online Learning for Active Cache Synchronization. A Kolobov, S Bubeck, J Zimmert. International Conference on Machine Learning, 5371-5380.\n\n- Recovering bandits. C Pike-Burke, S Grünewälder. arXiv preprint arXiv:1910.14354\n\nDifferently, in [49] the objective is to evaluate the impact of delays in observing the feedback after selecting one arm. This does not consider arm payoff distributions to be non-stationary. For instance, a novel work under the same line is given by\n- Stochastic bandits with arm-dependent delays. MA Gael, C Vernade, A Carpentier, M Valko. International Conference on Machine Learning, 3348-3356\n\nExperiments\n\nCan you specify which are the baselines, how have you tuned their parameters? More specifically, you have considered SOA non-stationary bandit policies ? How have you selected those baselines?\n\nOverall, besides the aforementioned limitations I found the paper interesting.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "6pzlDTD9U1u", "reviewer": "Reviewer_PRpe", "summary": "This paper considers a stochastic bandit setting with history-dependent reward structure, where the decision to play an arm k (with some probability) now impacts the reward of that arm in the future. The authors show negative results for this setting for a number of standard bandit algorithms, and provide a phased UCB-like algorithm for the problem, which they prove has nearly optimal regret scaling (by constructing a lower bound) for a specific delayed impact structure.\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": "I find this problem setting quite intriguing, and the motivation for studying delayed impact of actions in a bandit setting is natural.\n\nI like the inclusion of the negative result for “natural” algorithms in Lemma 3.1. However, unless I am missing something, it seems that the negative result follows effectively because the optimal action can be a “mixed” strategy, instead of always playing a single arm. Could you give an example of a setting where the optimal strategy is to play a _single_ arm, but UCB (or some other natural bandit alg) still fails? Such a setting seems like a more natural comparison, since the objective of UCB is to identify the single best arm, not mixed strategies, and I suspect one could still construct an adversarial history-dependence to make UCB fail in this setting.\n\nI found the presentation of the technical results and algorithms well done. The proof sketches were a nice addition, as they give a good overview of the analysis. I think that adding some more details to the main ideas needed for the lower bound instance would be useful for the paper presentation.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, adequately addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The Reviewers have no objection on the technical results provided by the paper or on the significance. By the way, let me remark that some Reviewers ask for re-writing some parts of the paper since they raised major presentation concerns. In particular, the authors should properly address the connection of the paper to fairness and other related works.
Decision: Accept (Poster)