Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.

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.

I 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? 

Regarding the content just above Section~5, I still cannot understand why EXP3 would fail. Can authors clarify more?

Regarding 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?

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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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. 

Pros:

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

Cons/Questions:

(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? 
(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?
(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.

After rebuttal:

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

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors formulate and study a multi-armed bandit problem with delayed impact
of actions, in which the actions are taken in the past affect the rewards in the future. Under this
setting, the authors design an algorithm that utilizes the dynamics introduced by the delayed
impacts of past actions to look for the optimal meta arm that maximizes the collected utilities
over time. The algorithm is shown to incur regret of at most $\Tilde{O}(KT^{2/3})$, which
matches the theoretical lower bound for this problem.
main_review: Strengths:
The paper is well written and structured. The model is novel in the current bandit's literature with
delayed impacts due to its consideration of long-term impacts. The paper provides good intuition
as to the applications of MABs with long-delayed impacts (the example in Section 2 well
illustrates the model set-up and the roles of the impact function). The theoretical results for both
action-dependent and history-dependent bandits are well explained. In particular, Algorithm 2/3
uses a simple idea that uses a short approaching stage to achieve the convergence of $f(t)$,
a longer estimation stage to estimate the reward of meta arm $p$, and a UCB-type algorithm to
find a good meta arm. The regret upper bound also matches the theoretical lower bound, which
demonstrates the optimality of the proposed algorithm.

Questions:
- How would one determine the choice of $\rho$ in Algorithm 2? Empirically, the authors
argue that the choice of $\rho$ does not influence the cumulative regret too much. But if
$\rho$ gets too small it seems that the theoretical upper bound worsens. Is there
anything that prevents us from always selecting a large $\rho$?
limitations_and_societal_impact: Weaknesses:
One limitation of the current paper is that most of the analysis on action-dependent and
history-dependent bandits is done using the impact function in Equation (2). Although the
authors remark in Section 5.2 that similar analysis can be applied to impact functions that
converge when one keeps selecting the same meta arm, it is not clear how one should select
the monotone function $g(.)$ for a general impact function. Since this restriction does not really
apply to general functions, it might be better to state it as a formal assumption.
In the regret definition, the authors choose the optimal fixed policy instead of the stronger
optimal dynamic policy as the benchmark. In Appendix H, the authors justify their choice by
arguing that for history-dependent bandits, the optimal strategy in the limit is well defined and
can be characterized as the best-in-hindsight policy. From the intuitive explanations, it is unclear
to me why this holds and might need a more rigorous treatment.

Minor comments:
- On pages 3 and 4, “$\delta = 0$” is a typo and should be $\gamma = 0$.
- In Section 4, it says that $p_k \in \{\epsilon, 2\epsilon, \dots, 1\}$. Can $p_k$ take the
value of 0 as well?
- It might be good to compare the performance of the algorithm of different $rho$ values
against the benchmark algorithms. From Figure 3d alone, it is difficult to tell that the
algorithm is not sensitive to different values of $\rho$.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.
I 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?
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.
Another tiny concern is that, in Line 118 & 172, I think it should be \gamma instead of \delta.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: ## Originality 
Delayed 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).
One 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.
Also, 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. 

## Quality
The upper bound of order of $T^{2/3}$ seems satisfactory and is supported by a matching lower bound.
I 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.


## Clarity
Some 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.
I 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$?

## Typos
- I think $\delta$ should be $\gamma$, l118 and l172. 
- "our model has its limitation" l350

## Edit
I 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. 
limitations_and_societal_impact: The way the authors discuss the limitations of their work is satisfactory to me.
review_title: null

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)