Artificial Replay: A Meta-Algorithm for Harnessing Historical Data in Bandits
Authors: Sid Banerjee
Sean R. Sinclair
Milind Tambe
Lily Xu
Christina Yu
Venue: Submitted to ICLR 2023 (2023)
Keywords: multi-armed bandits
historical data
adaptive discretization
online learning

Abstract: While standard bandit algorithms sometimes incur high regret, their performance can be greatly improved by "warm starting" with historical data. Unfortunately, how best to incorporate historical data is unclear: naively initializing reward estimates using all historical samples can suffer from spurious data and imbalanced data coverage, leading to computational and storage issues - particularly in continuous action spaces. We address these two challenges by proposing Artificial Replay, a meta-algorithm for incorporating historical data into any arbitrary base bandit algorithm. Artificial Replayuses only a subset of the historical data as needed to reduce computation and storage. We show that for a broad class of base algorithms that satisfy independence of irrelevant data (IIData), a novel property that we introduce, our method achieves equal regret as a full warm-start approach while potentially using only a fraction of historical data. We complement these theoretical results with a case study of $K$-armed and continuous combinatorial bandit algorithms, including on a green security domain using real poaching data, to show the practical benefits of Artificial Replayin achieving optimal regret alongside low computational and storage costs.

Under review as a conference paper at ICLR 2023
ARTIFICIAL REPLAY: A META-ALGORITHM FOR HARNESSING HISTORICAL DATA IN BANDITS
Anonymous authors Paper under double-blind review
ABSTRACT
While standard bandit algorithms sometimes incur high regret, their performance can be greatly improved by "warm starting" with historical data. Unfortunately. how best to incorporate historical data is unclear: naively initializing reward esti- mates using all historical samples can suffer from spurious data and imbalanced data coverage, leading to computational and storage issues particularly in con- tinuous action spaces. We address these two challenges by proposing ARTIFICIAL REPLAY, meta-algorithm for incorporating historical data into any arbitrary base bandit algorithm. ARTIFICIAL REPLAY uses only a subset of the histori- cal data as needed to reduce computation and storage. We provide guarantees that our method achieves equal regret as a full warm-start approach while potentially using only a fraction of the historical data for broad class of base algorithms that satisfy independence of irrelevant data (IIData). a novel property that we intro- duce. We complement these theoretical results with a case study of K K-armed and continuous combinatorial bandit algorithms, including on a green security domain using real poaching data, to show the practical benefits of ARTIFICIAL REPLAY achieving optimal regret alongside low computational and storage costs. Across these experiments, we show that ARTIFICIAL REPLAY performs well for set- tings that we consider, even for base algorithms that do not satisfy IIData.
INTRODUCTION
Multi-armed bandits and their variants are robust models for many real-world problems. Resulting algorithms have been applied wireless networks (Zuo & Joe- Wong 202T), COVID testing regu- lations (Bastani et al. 202T). and conservation efforts to protect wildlife from poaching (Xu et al., 2021I Typical bandit algorithms assume no prior knowledge of the expected rewards of each ac- tion, simply taking actions online to address the exploration-exploiaaeee
trade-off. However, many real-world applications offer access to historical data. For example, in the wildlife conservation setting, may have access to years of historical patrol records that should be incorporated to learn poaching risk before deploying any bandit algorithm.
There is consensus on how optimally incorporate this historical data into online learning al- gorithms. The naive approach uses the full historical dataset to initialize reward estimates (Shiv- aswamy & Joachims 2012). possibly incurring unnecessary and onerous computation and storage costs. These costs are particularly salient in continuous action settings with adaptive discretization, where the number of discretized regions is a direct function of the number of historical samples. If excessive data was collected on poor- npor-performing actions, this spurious data with imbalanced data coverage would lead us unnecessarily process and store an extremely large number fine dis- cretizations in low-performing areas of the action space, even when a significantly coarser discretiza- tion would be sufficient to inform us that region is not worth exploring. These two key challenges highlight that the value of information of the historical dataset may not be a direct function of its size. Real-world decision makers echo this sentiment: Martin et al. (2017) note that for conservation decisions, more information does not always translate into better actions; time is the resource which matters most.
ask is: Is there efficient way (in terms of space, computational, and sample complexity) to use historical data to achieve regret-optin regret-optimal performance? For example, many real-world applications of bandit algorithms, such online recommender systems, may
A natural question

---

Under review as a conference paper at ICLR 2023
tain historical datasets with millions of data points. Processing these millions of points would require an exceptional amount of upfront computation and storage cost, especially if many of those histori- cal points are no longer relevant; many samples may encode out-of-date data such old movies or discontinued products.
To this end, we propose ARTIFICIAL REPLAY, meta-algorithm that modifies any base bandit algorithm to harness historical data. ARTIFICIAL REPLAY reduces computation and storage costs by only using historical data on an as needed basis. The key intuition is if we could choose which samples to include in the historical dataset, a natural approach would be to use a regret-optimal bandit algorithm to guide the sampling. ARTIFICIAL REPLAY builds on this intuition by using historical data as a replay buffer to artificially simulate online actions. Every time the base algorithm picks an action, we first check the historical data for any unused samples from the chosen action. If an unused sample exists, update the reward estimates and continue without advancing to the next timestep. Otherwise, sample from the environment, update the estimates using the observion, and continue to the next timestep. While this idea is easiest to understand in the context of the standard K-armed bandit problem. we discuss later how this framework naturally extends to other structure and information models, including continuous action spaces with semi-bandit feedback.
Although ARTIFICIAL REPLAY seems to be a natural heuristic to minimize use of historical data, is not clear how to analyze its segret-specificalll how much it loses compared to "full warm-start" (i.e., where the base algorithm is initialized with the full dataset). Surprisingly, however, we prove that under widely applicable condition, the regret of ARTIFICIAL. REPLAY (as random variable) is distributionally identical to that of a full warm-start approach, while also guaranteeing significantly better time and storage complexity. Specifically, we show a sample-path coupling between our AR- TIFICIAL REPLAY approach and the full warm start approach with the same base algorithm, as long as the base algorithm satisfies a novel independence of irrelevant data (IIData) assumption. While our goal is not to show regret improvements, this result highlights how ARTIFICIAL REPLAY is a simple approach for incorporating historical data with identical regret to full warm start (approach done in practice) with significantly smaller computational overhead.
Finally, we show the practical benefits of our method by instantiating ARTIFICIAL REPLAY for several broad classes of bandits and evaluating on real-world data. To highlight the breadth of algorithms that satisfy the IIData property, we provide examples of regret-optimal IIData polices for K K-armed and continuous combinatorial bandits. We these examples prove that ARTIFI- CIAL REPLAY can lead to arbitrary better storage and computational complexity requirements. We close with a case study of combinatorial bandit algorithms for continuous resource allocation in the context of green security domains, using a novel adaptive discretization technique. Across the ex- periments, we observe concrete gains in storage and runtime using real-world poaching data from the ARTIFICIAL REPLAY framework over range of base algorithms, including algorithms that do not satisfy IIData such as Thompson sampling and Information Directed Sampling (IDS).
1.1 RELATED WORK
Multi-armed bandit problems have a long history in the online learning literature. We highlight the most closely related works below; for more extensive references please see our detailed discussion in Appendix B and Bubeck et al. (012)): Slivkins 2019);; Lattimore & Szepesvári (2020).
Multi-Armed Bandit Algorithms. The design and amalysis of bandit algorithms have been con- sidered under a wide range of models. These algorithms were first studied in the K-armed bandit model in Lai & Robbins (1985). where the decision maker has access actions at each timestep. However, numerous follow-up works have considered similar approaches when designing algorithms in continuous action spaces (Kleinberg et al. 2019 and with combina- torial constraints (Chen et al., 2013: Xu et al. 2021 Zuo & Joe- Wong 2021). Our work provides a framework to modily existing algorithms to harness historical data. Moreover, we also propose a novel algorithm to incorporate adaptive discretization for combinatorial multi-armed bandits for continuous resource allocation, extending the discrete model from Zuo Joe- neenog (2021).
finite set of K possible
'That is, we construct the regret process for both algorithms simultancously on joint probability space such that each individual process has the correct marginal, but hoth processes equal over each sample path.
2

---

Under review as a conference paper at ICLR 2023
Incorporating Historical Data. Several papers have started to investigate how to incorporate historical data into bandit algorithms, starting with Shivaswamy & Joachims (2012) who consider K-armee bandit model where each arm has dataset of historical pulls. The authors develop a "warm start" UCB algorithm to initialize the confidence bound of each arm based on the full historical data-prion learning. [Bouneffout al. (20T9) extended similar techniques to models with pre-clustered arms. These techniques were later extended to Bayesian and frequentist linear contextual bandits, where the linear feature vector is initialized based on standard regression over the historical data (Oetomo et al. 2021 Wang et al. 2017p. Our work provides a contrasting approach to harnessing historical data in algorithm design: our meta-algorithm can be applied to any standard bandit framework and uses the historical data only needed, leading to improved computation and storage gains.
PRELIMINARIES
We now define the general bandit model and specify the finite-armed and online combinatorial allocation settings that we study in our experiments. See Appendix C for details.
2.1 GENERAL STOCHASTIC BANDIT MODEL
We consider stochastic bandit problem with a fixed action set A. Let R A - ( 1J) be a collection of independent and unknown reward distributions over A. Our goal is to pick an action a E to maximize [[), the expected reward, which we denote p(a)) The optimal reward is:
OPT = max p(a).
a
For now, we do not impose any additional structure on A, which could potentially be discrete, continuous, encode combinatorial constraints.
Historical Data. We assume that the algorithm designer has access to historical dataset H = {aff, R255 )еe containing H historical points with actions {a]t ]ee[H] and rewards R23 sampled according to R.a))). We do not make any assumptions on how the historical actions at are chosen and view them as deterministic and fixed upfront. Our goal is to efficiently incorporate this historical data to improve the performance of bandit algorithm.
Online Structure. Since the mean reward function pla) is initially unknown, consider settings where the algorithm interacts with the environment sequentially over T timesteps. At timestep t E [7). the decision maker picks action A, A according to their policy The environment then reveals a reward R2 sampled from the distribution RY (A))). The optimal reward OPT would be achieved using a policy with full knowledge of the true distribution. We thus define regret as:
REGRET ,, Hhitt T OPT Σ P(A.)
where the dependence on Hhit highlights that A, can additionally depend on the historical dataset.
2.2 FINITE, CONTINUOUS, AND COMBINATORIAL ACTION SPACES
Finite-Armed Bandit. The finite-armed bandit model can be viewed in this framework by consid- ering K discrete actions A = [K] = =1,...,,K,
Combinatorial Mulri-Armed Bandit for Continuous Resource Allocation (CMAB-CRA). A central planner has access metric space S of resources with metric ds. They are tasked with splitting a total amount of B divisible budget across N different resources within S. An action consists of choosing N resources, i.e., N points S, and allocating the budget among that chosen subset. The feasible space of allocations is B = [0, 1] and the feasible action space is:
A (B,,)) E S x BN Σ 1= 300) < B, ds(p()) ( p())))) 2 Vi +}
(s(p))
(3)
The chosen action must satisfy the budgetary constraint (i.e., Σ, (000) < B), and the resources must be distinct (aka e-away from each other according to ds for some > 0) to ensure the "same" resource is not chosen at multiple allocations. We additionally assume that R decomposes indepen- dently over the (resource, allocation) pairs, in that p(a) E (1) 8()). Lastly, we assume
3

---

Under review as a conference paper at ICLR 2023
Algorithm 1 ARTIFICIAL REPLAY
Require: Historical dataset H = {(aa,, Ry )e(m) base algorithm II
1: Initialize set of used historical data points H1 = 0, and set of online data Hi
2: for == -1,,2.... do
3: Initialize flag to be True
4: while flag True do
5: Pick action A, ~ IT(" U H4)
6:
if Ae is not contained in H \ H then
7:
Update flag to be False Set online action A, = At
Finish a full timestep
8:
9:
Execute action A, and observe reward R2 R(A,) Update M4+1 = He {(A,, R and H74 = 74
Take online sample
10:
11:
else
12:
Update H4" to include one sample for A, from historical dataset H
the algorithm observes semi-bande feedback of the form (p. (())
RR Jie[N] for each resource
and allocation pair sampled according to R(pp (9) ). Zuo Joe- Wong 202 proposed a discrete
model of this problem as a generalization of the works Dagan Koby 2018 Lattimore et al.
2014 2015 specialize to consider scheduling a finite set of resources to maximize the expected
number of jobs finished.
Extension to Green Securiry. The CMAB-CRA model can be used to specify green security do- mains from Xu et al. (202T) letting the space S represent a protected area and letting B represent the discrete set of patrol resources to allocate, such as number of ranger hours per week, with the total budget B being 40 hours. This formulation generalizes model of the landscape, instead of the artificial fixed discretization that was considered in prior work consisting of
more realistic continuous space
sq. km regions of the park. This also highlights the practical necessity that the chosen resources (here, the patrol locations) are c-far away to ensure sufficient spread. In Section 5 we show that enabling patrol planning at a continuous level can help park rangers more precisely identify poaching hotspots
ARTIFICIAL REPLAY FOR HARNESSING HISTORICAL DATA
We propose ARTIFICIAL REPLAY, meta-algorithm that can be integrated with any base algorithm to incorporate historical data. We later prove that for any base algorithm satisfying independence of irrelevant data (IIData), novel property we introduce, ARTIFICIAL. REPLAY has identical regret an approach which uses the full historical data upfront-showing that our approach reduces com- putation costs without trading off performance. Additionally, in Appendix we discuss empirical improvements of ARTIFICIAL REPLAY applied to Thompson Sampling and Information Directed Sampling, two algorithms which do not satisfy IIData.
Algorithm Formulation. Any algorithm for online stochastic bandits can be thought of as a func- tion mapping arbitrary ordered histories (i.e., collections of observed (a, R) pairs) to a distribution over actions in A. More specifically, let IT 'D + (AA) be an arbitrary base algorithm where D denotes the collection of possible histories (i.e.,
Uzzo(A x )R. The policy obtained by base algorithm 11 without incorporating historical data simply takes the action sampled according IONORANT(TT)
II(H)) where H4, the data observed by timestep In comparison, FULL START(II) which follows the same policy but uses the full historical data upfront, so takes the action sampled according to I U UH)..
to the policy Rt
consider an algorithm n.
3.1 ARTIFCIAL REPLAY
The ARTIFICIAL REPLAY meta-algorithm incorporates the historical data Hhit into arbitrary base algorithm II, resulting in a policy denote by π ARTIFCIAA REILAY(TT). See Algorithm | for the pseudocode. We let H be the set of historical datapoints used by the start of time Initially, H11 0. For an arbitrary timestep I, the ARTIFICIaL REPLAY approach works as follows:
4

---

Under review as a conference paper at ICLR 2023
Let A ~ II(H4" U H4) be the proposed action at the start of time t. Since we are focused on simulating the algorithm with historical data, we break into cases whether or not the current set of unused historical datapoints (i.c., Hhise H²"") contains any additional information about A..
No historical data available: If A is not contained in Hhis \ M4T then the selected action is A, = A,, and we advance to timestep /. + 1. We additionally set H -
Historical data available: A is contained in H \ Hg, add that data point to H,e and repeat by picking another proposed action. We remain at time
Strikingly, our framework imposes minimal computational and storage overhead top of exist- ing algorithms, simply requiring data structure to verify whether À E H "Hg". which can be performed with hashing techniques. is clear that the runtime and storage complexity of ARTIFI- CIAL REPLAY is worse than FULL START. We also note that most practical bandit applications incorporate historical data obtained from database systems (c.g. content recommendation systems, wildlife poaching model discussed). This historical data will be stored regardless of the algorithm being employed, and so the key consideration is around computational requirements and not storage.
Additionally, our approach extends naturally to the following different models:
Continuous Spaces. The ARTIHCIAL REPLAY framework can be applicd in continuous action spaces with discretization-batt algorithms. For example, suppose that II wants select action a E AA, but the historical data has a sample from a + c, a slightly perturbed point. Discretization- based algorithms avoid precision issues since they map the continuous space series of regions which together cover the action set, and run algorithms or subroutines over the discretization. Check- ing for historical data simply checks for data within the bounds of the chosen discretized action.
Semi-Band Bandit Feedback. ARTIFICIAL REPLAY also naturally extends to combinatorial action sets with semi-bandit feedback where actions are decomposable, that is, they can be written as = (o....., ax) with independent rewards. Suppose that II wants to select an action a = (a1, .2............................ aN) but the historical data has a sample from (a', .2. .ay). Even if the combina- torial action does not appear in its entirety in the historical data, as long as there exists some subcomponent a²" (sometimes referred to as "subarm" in combinatorial bandits) in the historical data (e.g., a2). we can add that subcomponent at to H update the base algorithm.
3.2 INDEPENDENCE OF IRRELEVANT DATA AND REGRET COUPLING
It is not immediately clear how to analyze the regret of ARTIFICIAL REPLAY. To enable regret analysis, we introduce a new property for bandit algorithms, independence of irrelevant data, which essentially requires that when algorithm is about take an action, providing additional data about other actions (i.e., those not selected by the algorithm) will not influence the algorithm's 's decision.
Definition 3.1 (Independence of irrelevant data). A deterministic base algorithm II satisfies the independence of irrelevant data (lIData) property if whenever A II(H.) then
IIH) = I(HUH')
(4)
for any H' containing data from any actions other than A (that is, a' + A).
Ilaata is a natural robustness property for an algorithm to satisfy, highlighting that the algorithm evaluates actions independently when making decisions. IIData is conceptually analogous to the independence of irrelevant alternatives (IIA) axiom in computational social choice as a desiderata used evaluate voting rules (Arrow 1951). In Theorem 3.2 we show that for any base algorithm satisfying IIData, the regret of o. FULL START(I)) and ARTIIIICAL (EI) will be equal.
Theorem 3.2. Suppose that algorithm Il satisfies the independence of irrelevant data property. Then for any problem instance, horizon T, and historical dataset Hhis we have the following:
ARTIFCIAAL (II) d. Tt. Tt
FULL START(II)
REGRET (T, ARTIFICIAL REPLAY(IT) Hhisty 4 REGRET (T, π FULL START(II) Hhitt)
5

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Monotone UCB (MONUCB)
Initialize nı (a) = 0, | (a) = 1, and UCB1 (a) for each E [K]
2: for f ... do
3: Let A, arg m[[K] (C)
4: Receive reward R₂ sampled from R(A))
5: Update ne+1 (At) [A() 1, (4+1(a)) ne(a) for a # As
6: Update M (AA) =
+ (Ra)/m41((A)) P(+1(a) (a) (t(aa) for a a A
7: Update UCB (C for + At and
UCB(+1(A)) = ( P. 22 (m) (At)
This theorem shows that ARTIFICIAL REPLAY allows us to achieve identical regret guarantees as FULL START while simultaneously using data more efficiently. In the subsequent section, we show three example regret-optimal algorithms which satisfy this property, even in the complex CMAB- CRA setting. The algorithms we modify are all UCB-based algorithms. In fact, is easy to modify most UCB-based algorithms to satisfy IIData by simply imposing monotonicity of the confidence bound estimates for an action rewards. This is easily implementable and preserves all regret guaran- tees. While for brevity we only discuss IIData algorithms in the K-Armed and CMAB-CRA set-up, is easy to see how to modify other UCB-based algoriths (e.g. LinUCB for linear bandits Abbasi-- Yadkori al. 201T)) to satisfy IIData. In the existing bandit literature, there has been narrow Tocus on only finding regret-optimal algorithms. We propose that IIData is another desirable property that implies and robustness for optimally and efficiently incorporating historical data.
4 IIDATA ALGORITHMS
In this section, we provide IIData algorithms with optimal regret guarantees for two settings: the K-armed and CMAB-CRA models. We show that IIData is easy to guarantee for UCB algorithms requiring only minor modification to existing algorithms while not impacting confidence bounds guarantees.
We defer algorithm details to Appendix and proofs to Appendix F We'll show in Appendix E that in practice, ARTIFICIAL REPLAY still performs nearly optimally even with algorithms that do not satisfy IIData.
4.1 K K-ARMED BANDITS
The first algorithm we propose, named Monotone UCB (denoted as MONUCB), is derived from the UCBI algorithm introduced in Auer et al. (2002). At every timestep t, the algorithm tracks the following: (i) (a) for the estimated mean reward of action a E [K]. (ii) (a(a) for the number of times the action has been selected by the algorithm prior to timestep t, and (iii) (CB, for an upper confidence bound estimate for the reward of action a. At every timestep t, the algorithm picks the action A, which maximizes (CB,(a) (breaking ties deterministically). After observing R. increment 1 (A₂) = (A(A), + 1, update T (At), and set:
UCB min (A), (4,)(A)) + m.11(A))
2 2log(T)
(5)
The only modification of Monotone UCB from standard UCB is the additional step forcing the UCB estimates to monotone decreasing over It is clear that this modification has no affect on the regret guarantees. Under the "good event" analysis, if (a) 2 μua) with high probability, then the condition still holds at time t + 1, even after observing a new data point. In the following theorem, show that MONUCB satisfies Iaaaa and is regret-optimal, achieving the same instance- dependent regret bound as the standard UCB algorithm.
Theorem 4.1. Monotone UCB satisfies the IIData property and has for (a)) max, pla')-
REGRET(T, T, (MOUUI))(MOXUCI)) Hisst = O E log(T)/A(a)).
(6)
This guarantee allows us to use Theorem 3.2 to establish that ARTIFICIAL REPLAY and FUL.I START have identical regret with MONUCH CB base algorithm. In the next theorem,

---

Under review as a conference paper at ICLR 2023
show that ARTIFICIAL REPLAY is robust to spurious data, where the historical data has excess sam- ples at coming from poor performing actions. Spurious data imposes computational challenges, since the FULL START approach will pre-process the full historical dataset regardless of the ob- served rewards or the inherent value of the historical data. In contrast, ARTIFICIAL. REPLAY will only use the amount of data useful for learning.
Theorem 4.2. For every H E N there exists historical dataset Hhitt with |7 H where the runtime of म. FULL MONRT)) QHH +T) whereas the runtime of a ARTIBCIAA REPLAY (MONUCBB O(T + min (T))) min, ()))
This highlights that the computational overhead of ARTIFICIAL. REPLAY in comparison FULL START can be arbitrarily better. For storage requirements, the FULL START algorithm requires O(K) storage for maintaining estimates for each arm. In contrast, naive implementation of AR- TIFICIAL REPLAY requires O(K + H) storage since the entire historical dataset needs to be stored. However, using hashing techniques can address the extra H factor. In Section we will see an example where IIData additionally has strong storage benefits over FULL START.
Lastly, to complement the computational improvements of ARTIFICIAL. REPLAY applied to MONUCB, we can also show an improvement of regret. This analysis crucially uses the regret coupling, since FULL (TORT(MONUCB)) is much casier to reason about than its ARTIFICIAL RE- PLAY counterpart.
Theorem 4.3. Let H. be the number of datapoints in Hhist for each action [K]. Then the regret of Monotone UCB with historical dataset Hiist is:
REGRET(T, nt ARTIFCIAAL REPLXY(MONUCB)) H 00
max (0, (2) (()))
H,A(a))).
oE[K]:A.
Theorem 4.2 together with Theorem helps highlight the advantage of using ARTIFICIAL REPLAY over FULL START in terms of improving computational complexity while maintaining equally improved regret guarantee. This reduces to the standard UCB guarantee when Hiisr = 0. Moreover, it highlights the impact historical data can have the regret. If HHa 2 (og(T)/(()))) 2 for each a then the regret of the algorithm will be constant not scaling with T. We note that there are no existing regret lower bounds for incorporating historical data bandit algorithms. Our main goal is not to improve regret guarantees (although Theorem but instead highlight a simple, intuitive, and implementable approach through ARTIFICIAL REPLAY which matches the performance of FULL START while simultaneously having smaller compute.
1.3 highlights the advantage of historical data),
We close with an example of K-armed bandit algorithm which does not satisfy the IIData as- sumption. Thompson Sampling (Russo et al. 2018 which samples arms according to the posterior probability that they are optimal, does not satisfy IIData. Data from other actions other than the one chosen will adjust the posterior distribution, and hence will adjust the selection probabilities as well. While we do not obtain a regret coupling, in Fig. g (appendix) we show that there are still empirical gains for using ARTIFICIAL REPLAY over FULL START across a variety of base algorithms.
4.2 CMAB-CRA
Incorporating historical data optimally and efficiently is difficult in continuous action settings. Two natural approaches are to (i) discretize the action space A based on the data using nearest neighbor estimates. or (ii) learn a regression of the mean reward using available data. Consider a setting where excessive data is collected from poor-perfor poor-performing actions. Discretization-baseed algorithms will unnecessarily process and store large number of discretizations in low-performing regions of the space. Regression-basee based methods will use compute resources to learn accurate predictor of the mean reward in irrelevant regions. The key issues are that the computational and storage cost grows with the size of the historical dataset, and the estimation and discretization is done independent of the quality of the reward.
To contrast this approach, we present two discretization-based algorithms that satisfy IIData with strong performance guarantees. In particular, we detail fixed and adaptive discretization (ADAMONUCB in Algorithm algorithms that only use the historical dataset to update estimates
7

---

Under review as a conference paper at ICLR 2023
of the reward. Due to space, describe the algorithms only at high level and defer details to Appendix D
Our algorithms are Upper Confidence Bound (UCB) style the selection rule maximizes Eq. over the combinatorial action set (Eq. 3 through a discretization of For each allocation 3 E B, the algorithm maintains a collection of regions P of S which covers S. For the fixed discretization variant, Pe is fixed at the start of learning, and in the adaptive discretization version it is refined over the course of learning based on observed data. At every timestep / and region R. Pi the algo- rithm tracks the following: (i) F4 (R, (8) for the estimated mean reward of region R. at allocation 3, (ii) ne (R, 9) for the number of times R has been selected at allocation 3 prior timestep t, and (iti) UCB,RR, 3) for an upper confidence bound estimate. At a high level, our algorithm performs three steps in each iteration
Greedily select at most N regions in P to maximize UCB, (R. 3) subject to the budget constraints (see Eq. (TC) in the appendix). Note that we must additionally ensure that each region is selected only a single allocation value.
Action selection:
2. Update parameters: For each of the selected regions, increment (R, 3) by one, update TI, (R, 3) based on observed data, and set UC, = min(UCC, 3), Th, (R, B) + (R,, }))} for some appropriate bonus term b(.). This enforces monotonicity in the UCB estimates similar to MonUCB and is required for the IIData property.
Re-partition: This step differentiates the adaptive discretization algorithm from fixed discretiza- tion, which maintains the same partition across all timesteps. We split a region when the confi- dence in its estimate (i.e., (R, B)) smaller than the diameter of the region. This condition may seem independent of the quality of a region, but since it is incorporated into a learning al- gorithm, the number of samples in a region correlated with its reward. In Fig. (appendix) we highlight how the adaptive discretization algorithm hones in on regions with large reward without knowing the reward function before learning.
These algorithms modify existing approaches applied to CMAB-CRA in the bandit and reinforce- ment learning literature, which have been shown to be regret-optimal (Xu et al. 202T Sinclair et al.) We additionally note that these approaches are IIData.
202T
Theorem 4.4. The fixed and adaptive discretization algorithms when using a "greedy" solution to
solve Eg. ① have property IIData.
Here we require the algorithm to use the standard "greedy approximation" to Eq. which is knapsack problem in the CMAB-CRA set-up (Williamson & Shmoys 2011 This introduces
additional approximation ratio limitations in general. However, under additional assumptions on the mean reward function μ(p, (8), the greedy solution is provably optimal. For example, optimality of
the greedy approximation holds when p(p. 3) is piecewise linear and monotone, or more broadly
when μıaa) is submodular. See Appendix D for more discussion.
Finally, we comment that the FULL START implementation of these adaptive discretization algo- rithms will have storage and computational costs proportional to the size of the historical dataset (since the algorithms ensure that the discretization scales with respect to the number of samples). In contrast, ARTIFICIAL REPLAY uses only fraction of the historical dataset and again has improved computation and storage complexity. This is validated in the experimental results in Ap- pendix
5 EXPERIMENTS
We show the benefits of ARTIFICIAL REPLAY by showing that our meta-algorithm achieves identical performance to FULI START while offering significant practical advantages reducing runtime and storage. We consider two classes of bandit domains: K-armed and CMAB-CRA. As part of our evaluation on combinatorial bandits, we introduce a new model for green security games with continuous actions by adaptively discretizing the landscape of large protected area of Murchison Falls National Park in Uganda.
All of the code to reproduce the experiments is available at artificial- replay Results are averaged over 60 iterations with random seeds, with standard error plotted; experiment details and additional results are available in Appendix F
8

---

Under review as a conference paper at ICLR 2023
Piecewise-liness
Quadratic
Wildlife conservation
150
Regret
100
100
100
50
0
0
Fixed
0
250
500
750
1,000
250
500
750
1,000
0
250
500
750
1,000
200
200
160
Regret
100
50
100
Adaptive
500
1,000
250
750
1,000
500
1,000
Timeslep
Tinestep f
Timestep
ARTIFICIAL REPLAY
FULLI START
IGNORANT
REGRESSOR
OPTIMAL
Figure 1: (CMAB-CRA) Cumulative regret (y-axis; lower is better) across time t E [T]. ARTIFICIAL REPLAY performs equally as well FULL START across all domain settings, including both fixed discretization (top row) and adaptive discretization (bottom). REGRESSOR performs quite poorly.
Domains. We conduct experiments the two bandit models described in Section 2.22 finite K-armed bandits and CMAB-CRA. using both fixed and adaptive discretization. For the contin- uous combinatorial setting, we provide stylized domains: piecewise-linear and quadratic reward function. To emphasize the practical benefit of ARTIFICIAL REPLAY, we evaluate on a real- world resource allocation setting for biodiversity conservation. We study real ranger patrol data from Murchison Falls National Park, shared as part of collaboration with the Uganda Wildlife Authority and the Wildlife Conservation Society. We use historical patrol observations to build the history Hist, we analyze these historical observations in detail in Appendix E to show that this dataset exhibits both spurious data and imbalanced coverage as discussed in Section
Baselines. We compare ARTIFICIAL REPLAY against IGNORANT and FULL START approaches for each setting. In the Kaamed model, we use MONUCB the base algorithm. In CMAB- CRA we use fixed and adaptive discretization well as REGRESSOR, neural network learner that is regression- -aassd approach analogue to FULII START. REGRESSOR initially trained on the entire historical dataset, then iteratively retrained after 128 new samples are collected. We also compute for each setting the performance of an OPTIMAL action based on the true rewards and a RANDOM baseline that acts randomly while satisfying the budget constraint.
Results. The results in Fig. D empirically validate our theoretical result from Theorem 3.2 the
performance of ARTIFICIAL REPLAY is identical to that of FULL START, and reduces regret consid- erably compared to the naive IGNORANT approach. We evaluate the regret (compared to OPTIMAL) of each approach across time / e [T]. Concretely, reward, quadratic reward, and green security with continuous space S = [0, 1 N = 5 possible action components, budget
consider the three domains of piecewise-linean
2, and 3 levels of effort. We include points. See Fig. 5 (appendix) for regret and analysis of historical data use on the K -armed bandit.
300 historical data
Not only does ARTIFICIAL REPLAY achieve equal performance, but its computational benefits over FULL START are clear even on practical problem sizes. As we increase historical data from H (10; 100; 1,000; 10,000) in Fig. 2 the proportion of irrelevant data increases. Our method achieves equal performance, overcoming the previously unresolved challenge of spurious datu, while FULIL START suffers from arbitrarily worse storage complexity (Theorem 4.2). With 10,000 historical samples and time horizon of 1,000, we that 58.2% of historical samples are irrelevant to producing the most effective policy.
When faced with imbalanced data coverage, the benefits of ARTIFICIAL REPLAY become clear- most notably in the continuous action setting with adaptive discretization. In Fig. S as we increase the number of historical samples bad regions (bottom 20th percentile of reward), the additional data require finer discretization, leading to arbitrarily worse storage and computational complexity for FUL.I. START with equal regret. In Fig. Ce., we see that with 10% of data bad arms, AR-

---

Under review as a conference paper at ICLR 2023
(a) Regret
(b) unused Hii
(c) Samples used over time
200
100
1,000
100
500
50
10
100
1000
10000
10
100
1000
10000
200
100
600
800
1,000
Historical samples
Historical samples I/
Timestep 1
ARTIFICIAL REPLAY
FULL START
IGNORANT
RANDOM
Figure 2: (K-Armed) Increasing the number of historical samples H leads FULL START to use un- necessary data, particularly Hl gets very large. ARTIFICIAL REPLAY achieves equal performance terms of regret (plot a) while using less than half the historical data (plot b). In plot we see that with H = 1,000 historical samples, ARTIFICIAL REPLAY uses (on average) 117 historical samples before taking its first online action. The number of historical samples used increases at a decreasing rate, using only 396 of 1,000 total samples by the horizon T. Results are shown the K K-armed bandit setting with K = 10 and horizon T = 1,000.
(a) Regret
(b) % unused of H
(c) Number of regions R
100
600
400
50
400
200
Fraction arms
Fraction arms
Fraction bad arms
ARTIFICIAL REPLAY
FULL START
IGNORANT
REGRESSOR
Figure 3: (CMAB-CRA) Holding H 10,000 constant, we increase the fraction of historical data samples on bad arms (bottom 20% of rewards). The plots show (a) regret, (b) % of unused historical data and (c) number of discretized regions in partition P. ARTIFICIAL REPLAY enables significantly improved runtime and reduced storage while matching the performance of FULL START. Results on the CMAB-CRA setting with adaptive discretization on the quadratic domain.
TIFICIAL REPLAY requires only 446 regions R compared to 688 used by FULL START; as we get more spurious data and that fraction increases 90%, then ARTIFICIAL REPLAY requires only 356 regions while FULL START still stores 614 regions.
6 CONCLUSION
We present ARTIFICIAL REPLAY, meta-algorithm that modifies any base bandit algorithm to effi- ciently harness historical data. We show that under a widely applicable IIData condition, the regret of ARTIFICIAL REPLAY (as random variable) is distributionally identical to that of a full warm- start approach, while also guaranteeing significantly better time complexity. We additionally give examples of regret-optimal IIData algorithms in the K-armed and CMAB-CRA settings. Our ex- perimental results highlight the advantage of using ARTIFICIAL REPLAY over FULL START via a variety of base algorithms, applied to K- Karreed and continuous combinatorial bandit models, in- cluding for algorithms such as Thompson sampling and Information Directed Sampling (IDS) that do not exhibit IIData. Directions for future work include (i) find IIData algorithms in other bandit domains such as linear contextual bandits, (ii) incorporate the ARTIFICIAL REPLAY approach into reinforcement learning, and (iii) provide theoretical bounds showing that ARTIFICIAL REPLAY has optimal data usage when incorporating historical data.
10

---

Under review as a conference paper at ICLR 2023
REFERENCES
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24, 2011.
Kenneth Arrow. Social choice and individual values. John Wiley Sons, 1951.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multi-armed bandit problem. Machine learning, 47(2):235-255 256,,,,,,,,,,,, 2002.
Hamsa Bastani, Kimon Drakopoulos, Vishal Gupta, Ioannis Vlachogiannis, Christos Hadji- cristodoulou, Pagona Lagiou, Gkikas Magiorkinis, Dimitrios Paraskevis, and Sotirios Tsiodras. Efficient and targeted COVID-19 border testing via reinforcement learning. Nature, 599(7883); 108-113, 2021.
Djallel Bouneffouf, Srinivasan Parthasarathy, Horst Samulowitz, and Martin Wistuba. Optimal ex- ploitation of clustering and history information in multi-armed bandit. In Proceedings of the Twenty-Fighth International Joint Conference on Artificial Intelligence, (IJCAI), pp. 2016-2022, 2019.
Sébastien Bubeck, Nicolo Bessa-Bincchi, et al. Regret amalysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122 2012.
Stefano Canessa, Gurutzeta Guillera-Arroita, José J Lahoz-Monfort, Darren M Southwell, Doug Armstrong, Iadine Chadès, Robert C Lacy, and Sarah J Converse. When do we need more data? primer on calculating the value of information for applied ecologists. Methods in Ecology and 20155
Evolution, ((10):1219-11)
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In Proceedings of the Thirtieth International Conference on Machine Learning (ICML). volume 28, pp. 151-159. PMLR, 2013.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourleenth International Conference Artificial Intelligence and Statistics (AISTATS), pp. 208-214, 2011.
Yuval Dagan and Crammer Koby. A better resource allocation algorithm with semi-bandit feedback. In Algorithmic Learning Theory, pp. 268-320. PMLR, 2018
Adam N Elmachtoub, Ryan McNellis, Sechan Oh, and Marek Petrik. A practical method for solving contextual bandit problems using decision trees. In Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence (UAI), 2017.
Fei Fang, Peter Stone, and Milind Tambe. When security games go green: Designing defender strategies to prevent poaching and illegal fishing. In Proceedings of the Twenty-fourth Interna- tional Joint Conference on Artificial Intelligence (IJCAI), 2015.
Shahrzad Gholami, Amulya Yadav, Long Tran-Thanie Bistra Dilkina, and Milind Tambe. Don't 't put all your strategies in one basket: Playing green security games with imperfect prior knowledge. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 403,-403,200 2019.
Debarun Kar. Benjamin Ford, Shahrzad Gholami, Fei Fang, Andrew Plumptre, Milind Tambe, Mar- garet Driciru, Fred Wanyama, Aggrey Rwetsiba, Mustapha Nsubaga, et al. Cloudy with a chance of poaching: Adversary behavior modeling and forecasting with real-world poaching data. In Proceedings of the 16th International Conference Autonomous Agents and Multiagent Systems (AAMAS), 2017.
Robert Kleinberg and Nicole Immorlica. Recharging bandits. In 2018 JEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 309-319, IEEE, 2018.
Robert Kleinberg, Alexandru Niculescu-Minn Mizil, and Yogeshwer Sharma. Regret bounds for sleeping experts and bandits. Machine Learning, 80(2):245-272 2010.

---

Under review as a conference paper at ICLR 2023
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. Journal of the ACM (JACM), 66(4):1-77, 2019.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules, Advances in Applied Mathematics, 6(1):4-22, 1985.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Tor Lattimore, Koby Crammer, and Csaba Szepesvári. Optimal resource allocation with semi-bandit feedback. UAI, 2014.
Tor Lattimore, Koby Crammer, and Csaba Szepesvári. Linear multi-resource allocation with semi- bandit feedback. Advances in Neural Information Processing Systems, 28, 2015.
Tara G Martin, Abbey E Camaclang, Hugh P Possingham, Lynn A Maguire, and ladine Chadès Timing of protection critical habitat matters. Conservation Letters, 10(3):308-316, 2017.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing Atari with deep reinforcement learning. In Proceedings of the Twenty-Sevnnn Conference on Neural Information Processing Systems (NeurIPS), 2013.
Thanh H Nguyen, Arunesh Sinha, Shahrzad Gholami, Andrew Plumptre, Lucas Joppa, Milind Tambe, Margaret Driciru, Fred Wanyama, Aggrey Rwetsiba, and Rob Critchlow. CAPTURE: A new predictive anti anti-poaching tool for wildlife protection. In Proceedings of the 2016 Interna- tional Conference on Autonomous Agents & Multiagent Systems (AAMAS), 2016.
Bastian Oetomo, R Malinga Perera, Renata Borovica-Gajie, and Benjamin IP Rubinstein. Cutting to the chase with warm-start contextual bandits. In 2021 IEEE International Conference Data Mining (ICDM), pp. 468. IEEE, 2021.
Andrew Plumptre, Richard A Fuller, Aggrey Rwetsiba, Fredrick Wanyama, Deo Kujirakwinja, Margaret Driciru, Grace Nangendo, James EM Watson, and Hugh P Possingham. Efficiently targeting resources to deter illegal activities in protected areas. Journal of Applied Ecology, 51 (3):714-725, 2014.
Larry D Pyeatt and Adele E Howe. Decision tree function approximation reinforcement learn- ing. In Proceedings of the Third International Symposium Adaptive Systems: Evolutionary Computation and Probabilistic Graphical Models, volume 2, pp. 70-77, 2001.
Yundi Qian, Chao Zhang, Bhaskar Krishnamachari. and Milind Tambe. Restless poachers: Handling exploration-explootation tradeoffs in security domains. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems (AAMAS), pp. 123-131, 2016.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directed sampling.
Operations Research, 66(1):230- 252, 2018
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al. A tutorial on Thompson sampling. Foundations and Trendy in Machine Learning, 11(1):1-96, 2018.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In Proceedings of the Fourth International Conference on Learning Representations (ICLR), 2017.
Pannagadatta Shivaswamy and Thorsten Joachims. Multi-armed bandit problems with history. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1046-1054 PMLR, 2012.
Sean Sinclair, Siddharhha Banerjce, and Christina Lee Yu. Adaptive discretization in online rein- forcement learning. arXiv preprint arXiv:21 15843, 2021.
Aleksandrs Slivkins. Contextual bandits with similarity information. In Proceedings of the Twenty- Fourth Annual Conference On Learning Theory (COLT), pp. 679-702, 2011.
Aleksandrs Slivkins. Introduction to multi-armed bandits. Foundations and Trends in Machine Learning, -216 2019, ISSN 1935-8237.
12

---

Under review as a conference paper at ICLR 2023
Adith Swaminathan and Thorsten Joachims. Batch learning from logged bandit feedback through counterfactual risk minimization. Journal of Machine Learning Research, 16(52):1731-1755
2015.
William TB Uther and Manuela M Veloso. Tree based discretization for continuous state space rein- forcement learning. In Proceedings of the Fifieenth National Conference on Artificial Intelligence (AAAI), 1998.
Lu Wang. Chengyu Wang, Keqiang Wang, and Xiaofeng He. BiUCB: A contextual bandit algorithm for cold-start and diversified recommendation. In 2017 IEEE International Conference Big Knowledge (ICBK), pp. 248-253, 2017.
David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge university press, 2011.
Lily Xu, Shahrzad Gholami, Sara Mc Carthy, Bistra Dilkina, Andrew Plumptre, Milind Tambe, Ro- hit Singh, Mustapha Nsubuga, Joshua Mabonga, Margaret Driciru, et al. Stay ahead of poachers: Illegal wildlife poaching prediction and patrol planning under uncertainty with field test evalua- tions. In Proceedings of the IEEE 36th International Conference on Data Engineering (ICDE), 2020.
Lily Xu, Elizabeth Bondi, Fei Fang, Andrew Perrault, Kai Wang, and Milind Tambe. Dual- mandate patrols: Multi-armed bandits for green security. In Proceedings of the 35th AAAI Conference Artificial Intelligence (AAAI), 2021.
Rong Yang, Benjamin J Ford, Milind Tambe, and Andrew Lemieux. Adaptive resource allocation for wildlife protection against illegal poachers. In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 453-460, 2014.
Chicheng Zhang, Alekh Agarwal, Hal Daumé li,, John Langford, and Sahand Negahban. Warm- starting contextual bandits: Robustly combining supervised and bandit feedback. In Proceedings of the 36th International Conference Machine Learning (ICML), volume 97, pp. 7335-7344, 2019.
Jinhang 7uo and Carlee Joe-Wong Combinatorial multi-armed bandits for resource allocation. In 55th Annual Conference on Information Sciences and Systems (CISS), pp. 1-4. IEEE, 2021.
Jinhang Zuo, Xiaoxi Zhang, and Carlee Joe- ToenWong. Observe before play: Multi- bandit with pre-observations. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), vol- ume 34, pp. 7023-7030, 2020.
13


Reviews:
[{"review_id": "qMPsz-bB2c", "reviewer": "Reviewer_ZUbC", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "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. ", "summary_of_the_review": "Good problem but the theory part needs to be strengthened. ", "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.\n \n1. 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? \n \n2. 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.\n \n3. 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? \n \n4. 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?\n \n \n   \n \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "efIYgjC1--", "reviewer": "Reviewer_Ai7i", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper 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).\n\n\nThe 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.", "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.", "strength_and_weaknesses": "**Strengths of paper:**\n1. The problem of exploiting historical data is interesting, and as discussed in the paper, many real-world applications already have historical data.\n\n2. 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. \n\n3. 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. \n\n**Weakness of paper:**\n1. 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.\n\n2. 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.\n\n3. 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.\n\n4. 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.\n\n5. 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).\n\n6. Some related work for Combinatorial Multi-Armed Bandit for Continuous Resource Allocation is missing, e.g.,  \ni. Tor Lattimore, Koby Crammer, and Csaba Szepesvári. Optimal resource allocation with semi-bandit feedback. UAI, 2014.\nii. Tor Lattimore, Koby Crammer, and Csaba Szepesvári. Linear multi-resource allocation with semi-bandit feedback. NIPS, 2015.\niii. Yuval Dagan and Crammer Koby. A better resource allocation algorithm with semi-bandit feedback. ALT, 2018.\niv. Other recent work.\n\n\n**Question and other comments.** \n\nPlease address the above weakness. I have one more question:\n1. Page 3, paragraph after Eq. (3): Why do chosen resources for different arms needs to be $\\epsilon$-away from each other?\n\n\nI have a few minor comments:\n1. $H_1$ needs to be initialized as an empty set.\n2. $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.\n\nI am open to changing my score based on the authors' responses.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "TNeGxjLEGVc", "reviewer": "Reviewer_oZhq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "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. \n\nThe 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. \n\nThe 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. \n", "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.", "strength_and_weaknesses": "Strengths: \n1) 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. \n2) The proposed meta-algorithm is simple and can be used with any bandit algorithm.\n\nWeaknesses: \n1) 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? \n\n         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?\n\n2) 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.\n\n         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.  \n\n3) 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.\n \n4) Minor comments: \n  (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. \n  (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.\n  (c) in experiments, it'd be good to report runtime and storage improvements achieved by the proposed algorithm. \n  (d) In figure 8 (bottom right), why does the FULL START algorithm have such bad performance? It looks counter intuitive.\n\n[1] Lattimore, Tor. \"Optimally confident UCB: Improved regret for finite-armed bandits.\" arXiv preprint arXiv:1507.07880 (2015).\n\n[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.\n\nMore historic data hurting the regret is weird, counter-intuitive and requires more understanding. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7eGtfOVGX2a", "reviewer": "Reviewer_NKDb", "summary": "", "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": "", "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.", "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.", "strength_and_weaknesses": "Strengths:\n+ Proposed algorithm is simple and intuitive.\n+ The IIData condition is novel, yet easy to verify for different algorithms.\n\nWeaknesses:\n- Could you add a discussion of gap independent regret? How much data is needed to give asymptotic improvements in the regret?\n- 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.\n- 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.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject