Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the stochastic bandits problem, where historical data is available. The goal is to learn a policy that exploits the available historical data to reduce regret (the difference between the maximum achievable reward and the policy's reward).


The authors propose a meta-algorithm named ARTIFICIAL REPLAY that uses a bandit algorithm (satisfying IIData property) as a base algorithm. The proposed algorithm only uses a subset of the historical data (hence reducing the computational cost), but it has the same regret bound as the algorithm that uses all historical data upfront (without suffering from issues like spurious data). They also validate the proposed algorithm's performance on synthetic and real-world datasets.
strength_and_weaknesses: **Strengths of paper:**
1. The problem of exploiting historical data is interesting, and as discussed in the paper, many real-world applications already have historical data.

2. The proposed meta-algorithm only uses a subset of historical data and has the better regret as a bandit algorithm (satisfying IIData property) that uses all historical data for initializing reward estimates. 

3. The proposed two-base bandit algorithms, MONUCB (for K-armed bandits) and CMAB-CRA (combinatorial MAB for Continuous Resource Allocation), enjoy IIData property. The authors empirically validated the different performance aspects of the proposed algorithm on synthetic and real datasets. 

**Weakness of paper:**
1. The assumption of IIData, i.e., having additional information about other actions won't change the bandit algorithm decision in a given round, is too strong and counterintuitive. Best of my knowledge, no existing bandit algorithm that has IIData property.

2. The statement, "We present ARTIFICIAL REPLAY, a meta-algorithm that modifies any base bandit algorithm to efficiently harness historical data." in the Conclusion and a similar statement in the Abstract is misleading. Because ARTIFICIAL REPLAY only works when the base algorithm has IIData property.

3. The storage and computational problems are not that big in many real-world applications, and the authors have not motivated enough by giving suitable examples of where one should care about these issues. Even for the proposed algorithm, all history needed to be stored, so the storage issue is still there. However, one can have a computationally efficient implementation for accessing historical data. This problem will get more challenging for the continuous action space as finding action within the $\epsilon$ range may be computationally intensive.

4. The proposed algorithm is horizon dependent and needs $T$ as input. Making such an assumption may not be practical in many real-world applications as $T$ (how long the algorithm will be used in practice) may not be known.

5. In the experiments, authors have not used Thomson sampling variants (which enjoy better empirical performance than their UCB counterparts) against their proposed algorithms. It would be interesting to see how MONUCB (with ARTIFICIAL REPLAY) performs against the Thomson sampling variant that does not use any history (even for a K-armed bandit).

6. Some related work for Combinatorial Multi-Armed Bandit for Continuous Resource Allocation is missing, e.g.,  
i. Tor Lattimore, Koby Crammer, and Csaba Szepesvári. Optimal resource allocation with semi-bandit feedback. UAI, 2014.
ii. Tor Lattimore, Koby Crammer, and Csaba Szepesvári. Linear multi-resource allocation with semi-bandit feedback. NIPS, 2015.
iii. Yuval Dagan and Crammer Koby. A better resource allocation algorithm with semi-bandit feedback. ALT, 2018.
iv. Other recent work.


**Question and other comments.** 

Please address the above weakness. I have one more question:
1. Page 3, paragraph after Eq. (3): Why do chosen resources for different arms needs to be $\epsilon$-away from each other?


I have a few minor comments:
1. $H_1$ needs to be initialized as an empty set.
2. $H^{\text{hist}}$ needs to be updated after getting a sample from it; otherwise, it is possible to sample the same action-reward tuple when the existing action is chosen again.

I am open to changing my score based on the authors' responses.
clarity,_quality,_novelty_and_reproducibility: **Clarity:**
The paper is well organized, but the presentation has minor details that could be improved, as discussed earlier in **Strength And Weaknesses**.

**Quality:** 
Overall, the paper appears to be technically sound. The proofs appear correct, but I have not carefully checked the details. The experimental evaluation is adequate and supports the main claims. 

**Novelty:** 
This paper contributes some new ideas, but they only represent incremental advances.

**Reproducibility:** 
The key resources (e.g., proofs and code) are available, and sufficient details are given to reproduce the main results.
summary_of_the_review: This paper significantly overlaps with my current work, and I am very knowledgeable about most of the topics covered by the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers the stochastic bandit learning problem when the algorithm has access to information regarding historical actions and their corresponding rewards. By leveraging already available information regarding the rewards from historical actions, a bandit algorithm can obtain significantly improved regret over vanilla bandit algorithms. A simple, but naive, approach to use historical information is to incorporate all available data to “initialize” a bandit algorithm - while this approach effectively utilizes the available historical information, it suffers from being computationally expensive. Instead the paper proposes a new meta-algorithm: for any online bandit algorithm, when the bandit algorithm recommends action A_t at time t, instead of actually playing action A_t it checks if action A_t is available in the historical data and updates the internal state of the algorithm using the historical reward instead. The authors show that under certain assumptions on the base bandit algorithm, this strategy has regret equivalent to the naive approach above that uses the entire historical data upfront.
strength_and_weaknesses: Strengths:
+ Proposed algorithm is simple and intuitive.
+ The IIData condition is novel, yet easy to verify for different algorithms.

Weaknesses:
- Could you add a discussion of gap independent regret? How much data is needed to give asymptotic improvements in the regret?
- It is unclear what the exact computational /  storage costs are for using all the available historical data. For the K-armed bandit problem, the storage costs are simply a function of the number of arms and remain unchanged whether the algorithm builds UCB estimates for all the arms using all the historical data at time 0 or whether it uses the historical data incrementally. Even for the CMAB-CRA problem, the entire available historical data still needs to be stored (for potential future look-ups); so it’s not fully clear what the savings are.
- I am interested in a discussion of the setting where the historical data is also obtained via actions of a no-regret bandit algorithm (which is likely to be the case when such an algorithm is actually deployed). In this setting, the collected historical data is unlikely to contain spurious data - and it will be interesting to see whether the empirical gains still hold.

clarity,_quality,_novelty_and_reproducibility: The paper is well-written and is very clear and nicely structured. The key idea is highlighted appropriately and the main algorithm as well as the experiments are presented well. The algorithm itself is very natural and simple - but I actually consider that a positive. 

The appendix includes enough details for reproducibility (especially once the code is released).
summary_of_the_review: The paper is well-written and proposes a simple, intuitive (meta)-algorithm to harness historical information in stochastic bandit settings. The proposed approach makes efficient use of the available historical information and obtains significantly improved regret without using the full historical dataset at the beginning.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper considers the problem of bandit optimization when the learner has access to historic data. In this setting, the paper studies how best to use the historic data in order to reduce the computational and storage costs of the learner, while not hurting its regret. 

The main contribution of the paper is to propose an artificial-replay based algorithm that makes efficient use of the historic data. This algorithm works as a wrapper around any bandit algorithm. For any action recommended by the bandit algorithm, the meta algorithm first checks if there is a data point corresponding to that action in the historic data. If yes, it sends the reward of that action to the learner and removes that point from history. If not, the algorithm simply queries the environment for the reward of the action. Under a condition called "independence of irrelevant data", the authors show that the artificial replay algorithm achieves the same regret as  the regret obtained by warm-starting the bandit algorithm with the entire historic data. 

The authors instantiate their framework on two special bandit problems: stochastic multi-armed bandits (MAB), Combinatorial Multi-Armed Bandit for Continuous Resource Allocation (CMAB-CRA). For both these problems, the authors design modified versions of UCB algorithms that satisfy the IIData condition. Experimentally, the authors show that the proposed techniques are computationally more efficient than full warm-start based approaches, which achieving same regret. 

strength_and_weaknesses: Strengths: 
1) The problem is very relevant in the context of modern recommendation systems where we often have a lot of historic data. Incorporating the entire historic data in the bandit algorithm can be computationally expensive. So, a natural question that arises is whether we can trade-off a little bit of regret for computational efficiency. The paper takes a step towards answering this question. It shows that under IIData condition, the artificial-replay based algorithm has the same regret as the full-start algorithm while being computationally more efficient. 
2) The proposed meta-algorithm is simple and can be used with any bandit algorithm.

Weaknesses: 
1) While the IIData condition looks interesting, it is a strong condition. It requires the bandit algorithm's recommendation at a particular time instant to be the same even if it is provided with more information about all the other arms that are not being recommended. None of the bandit algorithms I know of seem to satisfy this condition (e.g., UCB, Thompson Sampling, Phased elimination).  This is worrisome because we are now forced to construct good bandit algorithms that satisfy the IIData condition.  Does this make the decades of work on designing bandit algorithms irrelevant? Is there an easy way to modify any given bandit algorithm to satisfy the IIData condition? 

         In practice, there is no need for a stringent requirement that the artificial-replay algorithm and the full start algorithm have the same regret. It is okay to trade-off a little bit of regret for computational efficiency. Is it possible to weaken the IIData condition to take this into account?

2) One important aspect that the paper hasn't touched upon at all is the regret optimality of the proposed algorithms. Is ARTIFICIAL REPLAY(MONUCB) regret optimal for both MAB and CMAB-CRA problems? Are there any regret lower bounds that can be provided in the presence of historic data? These lower bounds can help us understand how optimal the proposed algorithms are.

         Atleast for MAB, it doesn't look like the proposed algorithm is optimal. When there is no historic data, it is well known that standard UCB is not optimal in both minimax and instance dependent sense [1, 2]. There are several other algorithms that have been proposed to fix this issue.  

3) At a number of places in the paper, it is claimed that the proposed algorithm is better in computation and storage than the baseline algorithm. However, I don't see this clearly. Note that the full start algorithm only requires storing sufficient statistics (and not the entire data). For MAB, these sufficient statistics are the average reward and number of pulls of each arm. So, if we knew that we are using the full start algorithm ahead of time, then we only need to store these statistics, and the resulting algorithm only requires O(K) storage and O(K) additional compute. This is in fact much better than the artificial replay algorithm which requires O(H) storage and O(sqrt{T}) additional compute. Overall, I believe the MAB setting is not clearly showcasing the computational, storage benefits of the proposed algorithm. A more challenging setting with continuous action spaces (e.g., Linear UCB, Neural UCB) would have been more  interesting. While the authors do consider the CMAB-CRA problem, most of its details are relegated to the appendix. Moreover, the problem is studied by a niche community. I'd instead recommend the authors to consider a more fundamental problem (like LinearUCB) and showcase the benefits of the proposed algorithm.
 
4) Minor comments: 
  (a) the greedy algorithm mentioned in section 4.2 is never defined in the paper.  Given this, it is hard to evaluate the optimality of the proposed algorithm. 
  (b) in the statement of theorem 4.2, the run time of artificial-replay algorithm should be the minimum of sqrt{T} of log{T}/square of sub-optimality gap.
  (c) in experiments, it'd be good to report runtime and storage improvements achieved by the proposed algorithm. 
  (d) In figure 8 (bottom right), why does the FULL START algorithm have such bad performance? It looks counter intuitive.

[1] Lattimore, Tor. "Optimally confident UCB: Improved regret for finite-armed bandits." arXiv preprint arXiv:1507.07880 (2015).

[2] Garivier, Aurélien, and Olivier Cappé. "The KL-UCB algorithm for bounded stochastic bandits and beyond." In Proceedings of the 24th annual conference on learning theory, pp. 359-376. JMLR Workshop and Conference Proceedings, 2011.

More historic data hurting the regret is weird, counter-intuitive and requires more understanding. 
clarity,_quality,_novelty_and_reproducibility: Clarity: the paper is mostly well written and easy to follow. 
summary_of_the_review: While the problem being considered in the paper is interesting, the results could be significantly improved. For example, more interesting examples (than MAB) should be used to illustrate the benefits of the proposed algorithm. Moreover, the paper doesn't really talk about the regret optimality of the proposed algorithms. It'd be great if the authors address my concerns above.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studied an important bandit problem: how to deal with historical data. This paper proposed a meta-algorithm to handle computation and storage issues. 
strength_and_weaknesses: The problem this paper studied is important and interesting. The meta-algorithm is simple and intuitive. I feel before we talk about computational efficiency and storage, it is better to fully understand the statistical efficiency (regret) for this problem. I have some questions about the regret guarantee and use Theorem 4.3 as an example since this is the basic multi-armed bandits.
 
1. I feel there lacks sufficient discussion on how the historical data can reduce the online regret. The paper just mentioned "equally improved regret guarantee". This should be discussed quantitively. How about minimax regret? The abstract mentioned spurious and imbalance data could appear in historical data. How they affect the regret? 
 
2. I feel different historical data could affect online regret in a very different way. For example, if historical data contains all the optimal actions, online algorithms could just do imitation learning. If historical data contains a lot very sub-optimal actions, we could use them to remove bad actions. This work seems to not cover those issues. And the question is what exactly a full start algorithm is? There are many different ways to use full historical data and this also depends on what is your base algorithm.
 
3. In (2), the regret definition seems to be independent of historical data. How does this happens? Should it be conditional on historical data? Will a_j^H be random variables? 
 
4. The authors claimed they propose regret-optimal IIData policies. Where the optimality comes from? I didn't see any lower bound here and is this instance-dependent or minimax optimal?
 
 
   
 

clarity,_quality,_novelty_and_reproducibility: Overall this paper is good but the theory part needs more clarification. 
summary_of_the_review: Good problem but the theory part needs to be strengthened.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a meta-algorithm for incorporating historical data into any base bandit algorithm. The proposed approach is analyzed and also empirically evaluated.

The initial reviews of the paper were 2x borderline and 2x reject, and this did not change after the discussion. The main issue that leads to low scores is a strong i.i.d. assumption in the analysis, which is not satisfied by any existing bandit algorithm. This is also the main reason for rejection. I wanted to add two more comments:

* There are closely related prior works that are not cited, such as [Warm-starting Contextual Bandits: Robustly Combining Supervised and Bandit Feedback](https://proceedings.mlr.press/v97/zhang19b.html).

* The problem of warm-starting can be naturally treated from the Bayesian point of view, where the prior is learned from historical data using either frequentist or Bayesian techniques. Why would this be a bad idea?
justification_for_why_not_higher_score: The assumptions in the analysis are not satisfied by any existing bandit algorithm.
Decision: Reject