From Optimality to Robustness: Adaptive Re-Sampling Strategies in Stochastic Bandits
Authors: Dorian Baudry
Patrick Saux
Odalric-Ambrym Maillard
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-armed bandits
Stochastic Bandits
robustness
regret analysis

Abstract: The stochastic multi-arm bandit problem has been extensively studied under standard assumptions on the arm's distribution (e.g bounded with known support, exponential family, etc). These assumptions are suitable for many real-world problems but sometimes they require knowledge (on tails for instance) that may not be precisely accessible to the practitioner, raising the question of the robustness of bandit algorithms to model misspecification. In this paper we study a generic \emph{Dirichlet Sampling} (DS) algorithm, based on pairwise comparisons of empirical indices computed with \textit{re-sampling} of the arms' observations and a data-dependent \textit{exploration bonus}. We show that different variants of this strategy achieve provably optimal regret guarantees when the distributions are bounded and logarithmic regret for semi-bounded distributions with a mild quantile condition. We also show that a  simple tuning achieve robustness with respect to a large class of unbounded distributions, at the cost of slightly worse than logarithmic asymptotic regret. We finally provide numerical experiments showing the merits of DS in a decision-making problem on synthetic agriculture data.

From Optimality to Robustness:
Dirichlet Sampling Strategies in Stochastic Bandits
Dorian Baudry
Patrick Saux
Odalric-Ambrym Maillard
dorian. baudry@inria.ft fr
catrick.sauxinnia... saux@inria. fr
odalric.mail www. maillard@inria, fr
Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9198-CRISIAL, F-59000 Lille, France
Abstract
The stochastic multi-arn bandit problem has been extensively studied under stan- dard assumptions on the arm's distribution (e.g bounded with known support, exponential family, etc). These assumptions are suitable for many real-world prob- lems but sometimes they require knowledge (on tails for instance) that may not be precisely accessible to the practitioner, raising the question of the robustness bandit algorithms to model misspecification. Dirichlet Sampling (DS) algorithm, based on pairwise comparisons of empirical indices computed with re-sampling of the arms' observations and a data-dependent exploration bonus. We show that different variants of this strategy achieve provably optimal regret guarantees when the distributions are bounded and logarithmic regret for semi bounded distributions with mild quantile condition. We also show that simple tuning achieve robustness with respect to large class unbounded distri- butions, at the cost of slightly worse than logarithmic asymptotic regret. We finally provide numerical experiments showing the merits of DS in a decision-making problem on synthetic agriculture data.
this paper we study a generic
Introduction
The K K-armed stochastic bandit model is decision-makingg problem in which learner sequentially picks an action among K alternatives, called arms, and collects random reward. this setting, all rewards drawn from arm are independent and identically distributed. Hence, we can formally associate each arm & E f1...., K} with its reward distribution 14, with mean μ4g. The objective of the learner is to adapt her strategy (Az)eejy) in order to maximize the expected sum of rewards obtained after T selections (where T the horizon, unknown to the learner). This is equivalent to minimizing the regret, defined as the difference between the expected total reward of an oracle strategy always selecting an arm with largest mean and that of the algorithm, which is equal to
R2 = E Σ
MA Σ A.E(N.(T))
denotes the number of selections of arm k after T' time steps. J = max..(1.....K) Mj and A -r 14 is called the gap between arm k and the largest mean. To assess the performance of bandit algorithm, one naturally studies the best guarantees achievable by a uniformly efficient algorithm, i.e with sub-linear regret on any instance of a given class of problems. This guarantee was first provided by Lai and Robbins (1985) for I-dimensional parametric families of distributions, and then extended by Burnetas and Katehakis (1996) for more general families. It
Here, =
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

states that any algorithm that is uniformly efficient' on a family of distributions F must satisfy
RT Σ ke k=
D
lim inf T-x00 TTg(T)
GEF inf (KI,(U,,) G):(()))) (2)
A bandit algorithm is then called asymptotically optimal for family of distributions FF when its regret matches this lower bound. When F is a Linle-Paramette Exponential Family (SPEF), K is simply the Kullback-Leibler divergence between the distribution of mean f4 and that of mean μr in F, making for a theoretically appealing setting. The quantity K corresponding to the family F1- of distributions supported in (-o0, B] is also often considered in the literature, see e.g (Honda and Takemura, 2010, 2015; Cappé et al., 2013).
Overview of existing strategies An efficient strategy faces the classical exploration/exploittiion dilemma: it needs to obtain enough information from arms that have not been sampled a lot (ex- ploration), but also to sample arms that are well- well-performing sufficiently often (exploitation). Many algorithms have been proposed for the multi-armed bandits problem (see Lattimore and Szepesvári (2020) for a survey), and we propose in the following a non-exhaustive list of such methods. A first category contains the deterministic index policies, built on the concept of Optimism in Face of Uncer- tainty, the most celebrated of which being the Upper Confidence Bound (UCB) algorithms (Agrawal, 1995; Auer et al., 2002). These algorithms can obtain a logarithmic regret under classical hypothesis on the distributions (e.g bounded, sub- sub-gaussian, sub-exponential, ... and the strongest guarantees have been achieved by kI-UCB Cappé et al. (2013), DMED (Honda and Takemura, 2010), and IMED (Honda and Takemura, 2015), which share common pattern of solving a convex optimization prob- lem at each round. To be asymptotically optimal, these algorithms require either 1) the knowledge of a specific SPEF for each arm, or 2) a known upper bound on the support of each arm. A second general category is that of randomized bandit algorithms,, which has been formulated for instance in (Kveton et al., 201 9b) as General Randomized Exploration (GRE). The common feature of these methods is that, at each time step and for each arm, the algorithm draws an index from a distribution that depends on 1) the rewards observed from the arm, and 2) some knowledge on the arms distributions and chooses the arm with the largest index. Thompson Sampling (TS) (Thompson, 1933; Agrawal and Goyal, 2012) belongs to this category, and a proper choice of Bayesian prior/posterior ensures optimality of TS in SPEF (Korda et al., 2013). Different algorithms using Bootstrapping schemes have also been proposed (Osband and Roy, 2015; Kveton et al., 201 1a,b; Wang et al., 2020; Riou and Honda, 2020): they share the idea of computing noisy mean for empirical samples, enhanced by some exploration aid appropriately tuned to the family of distributions they consider. A last category contains the methods based on sub- sampling Baransi et al. (2014); Chan (2020); Baudry et al. (2020, 2021b), that achieve asymptotic optimality in SPEF withow knowing which family, when all arms share the same. However the proofs heavily rely on properties of the tails of SPEF so the results seem difficult to generalize outside these families.
Motivations While many algorithms achieve optimal regret for bounded distributions with the sole knowledge of the upper bound, the assumptions needed for algorithms working with unbounded distributions (e.g SPEF, aub-Gaussian, sub-exponential) generally assume known parametric model for the tails. While such assumption entails convenient properties on the theoretical side, the practitioner may have some difficulty determine which setting/parameters correspond to her problem. Furthermore, this uncertainty raises the question of robustness with respect to these hypotheses. Several works have considered this question: Hadiji and Stoltz (2020) shows that adapting to an unknown bounded range requires a tradeoff' between instance-dependent and worst- case regret, and recently (Agrawal al., 2020; Ashutosh et al., 2021) proved the impossibility of an instance- dependent logarithmic regret for light- distributions without explicit control on the tail parameters. The root cause for this is the lack of compactness of such families F, which allows mass to "leak" at infinity so that maximally confusing distributions with mean μ exist arbitrarily close to Vk, meaning Ki n²) = 0. The latter work also introduces a robust variant of UCB, that trades off logarithmic regret for O (f()) log(T)). where f essentially tracks the possible mass leakage at infinity. These results puts into question the usual hypotheses under which bandit algorithms are designed: considering a parametric control of the tails is indeed sensitive to model mis- missspeciiiiation. but on the other hand the examples chosen to prove infeasability results seem a bit extreme for the practitioner. In this paper, we propose simple alternative setups allowing unspecified tail shapes
'Tht is, for each bandit F. for each arm & with As 0, then [B| (T') =o(1") for all E (0. 1].

---

but avoiding "mass leakage" to infinity, for instance with mild conditions linking the quantiles and the means of the distributions. We consider this paper light-tailed distributions (see definition in Appendix 1. This problem is already non-trivial, so we let possible extensions for heavy-tail distributions for future work (e.g with tools like median-of-ment -feemsss see (Bubeck et al., 2013))
Outline In the novel settings we consider, we want algorithms that require the smallest level of knowledge on the tails of distributions. To this extent, the non-Parametric Thompson Sampling (NPTS, Riou and Honda (2020)) algorithm is good candidate, considering how little knowledge it requires to reach asymptotic optimality for bounded distributions with known bounds. Furthermore, the flexibility of this algorithm has been recently demonstrated with its adaptation in a risk-aware setting (Baudry et al., 2021a). We provide a generalization of NPTS that we call Dirichlet Sampling (DS): we combine the core elements of NPTS and a duel-based framework inspired by (Chan, 2020), introducing data-dependent exploration bonuses. We present the resulting algorithm and detail the technical motivations of this approach in Section 2. We then introduce in Section first regret decomposition of DS algorithms under general assumptions, and the technical results that allow to fine-tune the algorithm for different families (see Section 3.1). We provide three instances of DS algorithms and their regret guarantees in Section 3.2: Bounded Dirichlet Sampling (BDS) tackles bounded distributions with possibly unknown upper bounds, Quantile Dirichlet Sampling proposes a first generalization to the unbounded case using truncated distributions. Last, Robust Dirichlet Sampling (RDS) has a slightly larger than logarithmic regret for any unspecified light-tailed unbounded distributions, making it competitor to the Robust-UCH algorithm of Ashutosh et al. (2021). Finally, we study in Section Hoogenboom et al. (2019)), which naturally faces all the questions (robustness, model specification) that motivate this work and shows the merit of DS over state-of-the-ee methods for this problem.
use-case in agriculture using the DSSAT simulator (see
2 Dirichlet Sampling Algorithms
In this section we introduce Dirichlet Sampling, a strategy that aims at generalizing the Non- Parametric Thompson Sampling algorithm of Riou and Honda (2020) outside the scope of bounded distributions with a known support upper bound. For this purpose, we build an adaptive strategy in a duel-based framework, already used in sub-sampling based algorithms like SSMC (Chan, 2020).
Background Non-Paramctric Thompson Sampling is an index strategy where the index of each arm is random re-weighting of their observations. augmented by an exploration bonus. The weights are drawn from the Dirichlet distribution D,, = Dir((1...... 1)) for n data, which is the uniform distribution on the simplex pm {w E [0, 1j" w'1 = 1} and matches the Bayesian posterior (i.e Thompson Sampling) for multinomial arms. The exploration bonus is simply the known upper bound of the support, and avoids under-exploration of potentially "unlucky" good arm. We provide further explanations on the Dirichlet distribution and NPTS respectively in Appendix C.I and A.3.
The simplicity of NPTS and its strong theoretical guarantees are appealing for further generalization. As we fully depart from the Bayesian approach, considering other exploration bonuses, we derive new family of algorithms under the name of Dirichlet Sampling. We keep the two principles of re- weighting the observations using a Dirichlet distribution and the exploration aid, and explore how to apply them to more general (e.g unbounded) distributions. In particular, we allow in DS some pre pre-processing of the observations before re-weighting (see section 3.1 and 3.2) and motivate in Section 3.1 the use of data dependde bonus, that information from several arms. The complexity introduced by such bonus in the analysis requires a change of algorithm structure, dropping the index policy for leader vs challenger approach (Chan, 2020).
Round- based algorithm We define a round as a step of the algorithm at the end of which a set of (possibly several) arms are selected to be pulled. Let A, C. {1...., K} be the subset of the arms pulled at the beginning of a round r, we call T -round regret the quantity
T
K
R = E
ΣΣ
A E A.)
Σ A (N))
(3)
where we slightly change the definition of No (compared with 1) to (T We consider the Tround regret for simplicity, as it is a simple upper bound of the regret after T
=
11 1(k: E Ar).
3

---

b Play the duels pulls. At the beginning of each round we define reference arm (leader), and then organize pairwise comparisons called duels between this arm and the other arms (challengers). The leader is chosen as the arm with largest sample size, l" E argmax (e(r),
kE()....K)
where ties are broken first favor of the best empirical arm, then with random choice. A major motivation for this choice is that the leader will have a sample size that is linear in the number of rounds, as least one arm is chosen at each round. This ensures strong statistical properties that we will exploit to design the exploration bonus of DS strategies. Randomizing the index of the leader also unnecessary: competes against each challenger with its empirical mean. We also dismiss all the arms k that satisfy (r) (r) with the same argument. These choices have practical interest as they avoid the computation time of drawing the largest weight vectors. We believe this can be an alternative of independent interest to computationally intensive index policies.
Challenger's index We fix index that dependent on the round, but only on the history of the challenger and the leader available at this round, that we denote respectively by X' ( Xn). Y = (Yi...., Yv) for simplicity of notations. We denote by μ R + R the function that computes the average of set of observations. The duel can includes two steps, and the challenger wins if
1. m(x) 2 v()) (first compare the empirical means), or
2. T(X,)) )) 2 (()),, where R R IR denotes the chosen DS index.
We summarize in Algorithm 1 the steps of Dirichlet Sampling, that completely detail in Ap- pendix A.2. We write it for a generic "Dirichlet Sampling index" jú that must be computed by re-weighting of the observations augmented by an exploration bonus. As in NPTS, the weights are drawn with Dirichlet distribution. For instance, a canonical example of Dirichlet Sampling index with data-depend (instead of fixed) bonus B(X,))) is
E wiX; + Wn+1B((X))
= (Wi..... Wn+1) ~ Dn+1.
However, the algorithm structure in Algorithm could combined with any randomized index, which is of independent interest as we will see in Section 3. In the next section we study the theoretical properties of Dirichlet Sampling, and discuss the choice the index jú for different families of distributions.
Algorithm Generic Dirichlet Sampling
Input: K arms, horizon T. Dirichlet Sampling index
Init.: f 1,7 / = 1, Vk {1, K}: :: Xx = (X+). N& 1;
Draw each arm once Arm(s) to pull at the end of the round Choose Leader
while & < T do
A = +
t Leader(( (K, (eader((& N1). ...:: (Kr, Nx))
for & E {1............... K}: N₂ < N₂ do
if max (1( Mk). ). Ti(Xxs Xe)) 2 (X) then = A [k)
Draw arms from |A| if A is non-empty, else draw arm f. Update f, (N&) (e.e..,.... (J. (Xr (K..,.. > Collect Reward(s) update data
3 Regret Analysis and Technical Results
In this section, we analyze the regret of DS algorithms. We first derive general regret decomposition for any index zú that holds thanks the duel-based structure. We then introduce several properties of Dirichlet sampling, that theoretically guide proper tuning of DS index. We finally instantiate DS for three different problems and provide regret bounds these settings. Starting with the regret decomposition, we exhibit general conditions to ensure guarantees that are independent on the index and the run of the bandit algorithm. Allowing a different family of distribution Fs. for each arm the first one concerns the concentration of the mean of each distribution.

---

Condition 1 (C1) [Concentration] For all Vy E Fk, there exists a good rate function Ig satisfying (x) > 0 for x + Pk and for all x pkx y pig and any i.dd sequence XI...., Xn drawn from
n Σ n
P
X
Se-nde( and P
Se-nde(w)
(4)
This hypothesis is standard in the bandit literature, and is for instance satisfied by any light-tailed distributions. We refer to (Dembo and Zeitouni, 2010) for techniques to derive such functions.
We now provide upper bound on the round-regret presented in Section 2 for Algorithm 1. To simplify the notations we consider that there is only one optimal arm and, without loss of generality, that vk: > 1, /ig < ju1- Furthermore, for simplicity we write the following theorem for an index ((X', p). that only uses the mcan of the leader. The same result holds for any index using statistics on the leader's ' history that have concentration properties similar to (CI) (e.g possibly quantiles, variance, etc) with slight adaptations of the proof.
Theorem 3.1 (Generic regret decomposition of DS). Consider a bandit model v (Vi..... VK) where all distributions in v satisfy (CI). Then for any DS index the expected number of pulls of each arm k E , K} is upper bounded for each E [0, Ak) by
E [T)( S rT(TT) B C
where = 1(k E Art1, =1). C is independent on and, denoting Xn the set of n first observations of arm
K Σ 1=2
[2
1 (M(Xn) S P( 2 24)
B
Σ
sup mely--caytd
Ex,
n=1
The details of the proof of this result are to be found in Appendix B. The proof follows the general Ch explicit. This term related to
outline of Chan (2020), and makes all the components deviations of sample means for arms k and 1 and is typically bounded by (problem-dependent) constant under light-tail concentration (C1), so does not depend on já but only on the rate functions and the means of each arm. The other two terms of the RHS reflect the exploration strategy. n& (T') is the expected number of pulls of arm & when the best arm is the leader; we interpret it as the sample size required to statistically separate both arms at horizon T. On the other hand, B measures the capacity of the best arm to recover from a bad (small-sizede sample.
Theorem 3.1 is formulated to be as general as possible and can be regarded as a counterpart of Theorem 1 of Kveton et al. (2019b). We will later analyze instances of Dirichlet Sampling where the first-order term of the regret is driven entirely by nT(T). We therefore introduce the following condition to control the contribution of B to the regret.
Condition 2 (C2) For any / < μ11 and any nı (T) = o(log 7) it holds that
(T) Ex Exa
1 (H((En) 5 4) P PWwDD.1a (M(XX N m)
o(log 7')
The LHS represents the expected cost in terms of regret of underestimating the optimal arm; intuitively, it measures the expected number of losing rounds before finally winning one when starting with low rewards. This is classic decomposition in bandit analysis, and a counterpart of (C2) holds for most index policies with provable regret guarantees, e.g Theorem 1 in Kveton al. (2019b) (GIRO) or Lemma 4 in Agrawal and Goyal (2012)) (Bernoulli Thompson Sampling). We find it noteworthy that this regret decomposition depends only on the distribution of the best arm and its randomized Dirichlet Sampling index when it is a challenger.
Corollary 3.1.1 (Conditions for controlled regret). If condition (CI) and (C2) holds for the DS index on the families of distribution (Fx)kE(1.....k) the regret of the DS algorithm satisfies
K
R₂
Aang (T) o(log
2=2
5

---

Up to this point this result is quite abstract, but this standardized analysis allows us to instantiate the Dirichlet Sampling algorithm on different class of problems and calibrate in order to ensure condition (C2) holds and to make n& (T) explicit. In particular if ny (T) Ollo T),, we recover the logarithmic regret. In the next section, we present technical results to justify calibrations of the DS index for several kind of families.
3.1 Technical tools: boundary crossing probability of a DS index
In this section, we highlight some key properties of sum of random variables re-weighted by Dirichlet weight vector that help us suggest a sound tuning of the bonus B(X.3) for different kind of families. We then detail such tuning.
Boundary crossing probability (BCP) We consider set of + observation points X' ( C I=++1 (Intuitively, points are samples from challenger arm, and one point corresponds the added bonus). Then, for any μ E E. we introduce the following "Boundary Crossing Probability" (BCP) term, conditional on X
n+1 Σ ΣuXK2H
[BCP] := WwwDDat Da+1
where we recall that Dn+1 is the Dirichlet distribution with parameter (l...., of size 1,,, i.e the uniform distribution on the (n + 1)-simplex. We emphasize that here X' is considered fixed, and the only source of randomness comes from the weights w. When all observations are distinct this expression has a closed form, which is unfortunately untractable in the proof, as discussed in Appendix C.2. This quantity is of much interest as both the growth of n& (T) and (C2) can be derived from respectively upper and lower bounds for the BCP. Lemma 14 and Lemma 15 in (Riou and Honda, 2020) provide such bounds, resorting to classical concentration results and properties of the Dirichlet distribution that we recall in Appendix C. and C.2, and complete with additional technical results. The lower bounds suggest non-trivial tuning of the bonus. We first exhibit a necessary condition when the bonus is not allowed to depend on the set of observations X.
Lemma 3.2 (Necessary condition with data- independent bonus). Consider a fixed bonus B(X p) = B()), and distribution F (with CDF also denoted F). If Condition (C2) holds then
1
B(n) > 1 +
Er [(u X)+]
F())
This result is obtained using a "worst-case" scenario when all observations are below the threshold μ.. Hence, it does not cover all possible trajectories, yet it suggests to investigate the properties of bonuses with a similar form. Since the right-hand side of the inequality requires a knowledge on the arms distributions that would like to avoid, This suggests to introduce some parameter, p and data-dependent bonuses of the form
empirical estimator for the expectation.
= - = Σ (,)+
(5)
We interpret y as the leverage of the empirical excess gap 1 (4 X,)+ w.r. the threshold μ. We then tune P assuming an hypothesis on some upper quantile of the arm distribution, which is much less constraining than assuming knowledge of the shape of the entire tail. all DS algorithms we propose (sec next section), we use Equation 5 the basis for defining the appropriate bonus. Finally, we provide in Lemma 3.3 a novel lower bound on the BCP that reveals that in the general case of unbounded distributions, without further processing of the data, DS cannot achieve logarithmic regret when the maximum the data tends to too at some rate g(n).
Lemma 3.3 (Lower bound for the BCP). Consider set X = (X Xn+1) E 1a+t1, and assume X; 2 g(r)) some function g. Denoting A 1 L- x. clu -X))+ the
that X = iE iE(I...,,+1))
max
empirical positive gap, it holds that
a+1
A (()) 41
P Fw-Da.t
Σ
W p1 2 cxp
In particular, we see in this expression that g(n) may hinder the exponential rate in n. the next section we discuss three examples of DS algorithms and their theoretical guarantees.

---

3.2 Theoretical guarantees for Dirichlet Sampling algorithms
Building on the results from previous the section, we now instantiate the DS algorithms for three bandit problems. We first prove that optimal guarantees can be derived for DS with bounded distributions under non-standard definition of the problem (i.e unknown upper bound but alternative assumptions), motivated by practical considerations. Then, we consider a natural extension to unbounded distributions using a simple truncation mechanism, ensuring logarithmic regret under assumptions some quantile of the distributions. Finally we consider simple DS algorithm, securing slightly wugge-than-logarithmi
regret for the entire family of light-tailed distributions. In the following we denote by (XX, 14, p) the bonus defined in Equation 5 for set X, mean μ and some parameter p. For simplicity we will keep a generic I in our exposition, while its value is in practice the empirical mean of the leading arm. We detail each algorithm and their components in Appendix A.2 and the proofs of the three theorems in Appendix D. In all cases, the proof consists in showing that (C1) and (C2) hold for each proposed algorithms in the settings they tackle and deriving an expression for ny (T).
Optimality for bounded distributions Let Fi0.B) be the set of distributions supported in [b, B), and consider a bandit = (V1,...,, ,KK) with 1/2 ~ FB.) for some B₃ R. If we assume that Bg is known (case 1), then simply defining B₃ as the exploration bonus ensures an asymptotically optimal regret, with a direct adaptation of the proof of NPTS (Riou and Honda, 2020). However, the precise knowledge of the upper bound for each arm is sometimes inaccessible to the practitioner (e.g if the environment is new, or if no expert is available to provide an estimate of the bound). We propose an alternative setting, with the family FB = {3B : V E Fio.B), . P, 7, B)) 2 p} C Fi6.B]- B& is unknown but we assume it is detectable in the sense that we will observe sample from its neighborhood [Bx- 7, Bu] with a reasonable probability of at least p, with known 7, P (case 2). In this case we propose the following bonus, allowing obtain theoretical results in this setting,
B = max X +7, (,K.),) where X = maxf# E X'.
(6)
Theorem 3.4 (Optimality of BDS). If 4k E 12..... K} bonus of Equation 6 with p 2- 1/ log(1 p) ensures that
FB choosing the exploration
[[N+(T) - log(T) + 01)),
K (vks (1)
where Bp max (B Y, + plr, ( 1l)++))
-
This setting is a first example of the interest of data-dependent bonuses. It makes sense in practice by avoiding for instance distributions with small mass arbitrarily far from the rest of their support, which may not be likely in a real-world application. We now consider the unbounded case.
Unbounded distributions: truncating the upper tail Let consider the family Fig+ for some unknown b E TR. A natural way to extend algorithms designed for Fio.B) B] (where B < -00 ) is to truncate the upper tail of the distributions. We propose simple way to do this, by considering (as a parameter of the algorithm) a quantile 1 - a, denoted by Q1-a (v) for a distribution v, and truncation operator Ta that (1) do not change a distribution below its 1 a quantile, and (2) "summarizes" its upper tail by its expectation, known as Conditional Value at Risk (CVaR). Formally, we obtain (A) = v(A) for any A C [b, -1- (v)] and (v( (fx)) = al (z = C. (v)) for any >> (1), with C. (P) = E|X > (v)]. We then propose Quantile Dirichlet Sampling (QDS), that computes the index of a challenger (say arm k. with observations Xx) during a duel as follow: (1) apply Ta to the empirical distribution, (2) compute the bonus B(X,, 11, P). and (3) re-sample the truncated empirical distribution with weights drawn according to Dir(1,.... 1, na)
where parameter na is for the weight used with the empirical CVaR, and is simply the number of observations used to compute it (to avoid a bias in the re-sampled mean). We can obtain theoretical guarantees with this method by considering the subset of distributions
Fo) {u E Fi,, Vu > Ey (X), X
1o.)) (v, p)) 2 K (T),
where D2 = max (uk) Mn + pRuy (11 - X)+ and the second Kint is taken on the family Fl.mgg (using previously introduced notations). Although technical, this condition essentially states
7

---

that the bandit problem taken on the complete family +lb,+ is no harder than an alternative bandit problem considering the truncated distributions and bounded family, with an upper bound depending on the 1 - a quantile and the leverage of the exploration bonus.
Theorem 3.5 (Logarithmic Regret of QDS). Consider a bandit model v (Vi...., .VK... satisfying vk, V/_ E +)) for some b > -oo (lower-boured
support) and known a > 0. Then, for any Eo > small enough QDS with any parameters a' < a and p 2 (1 + a')/a²² satisfies
log T
(T)
+ 0(1),
X (Tx(v)), (1) -
with 2 (ax Mn + pE - X) and Ta is the truncation operator we defined.
This result is of particular interest as it captures the continuum between bounded and light-tailed distributions. In our opinion, it sheds new light on the interpretation of infeasability results of e.g Ashutosh et al. (2021): logarithmic regret can be achieved without specifying the tail with precise parameters, but a simple quantile condition is required to avoid pathological distributions that makes little sense in practice (e.g very small mass at a very large value). We further discuss this condition in Appendix E and provide examples of families for which it holds (exponential, Gaussian).
Remark 3.6. The restriction to the ceni-bounded case b > -oo is due to our proof technique, based on a discretization of the support of the truncated distribution (see Appendix D). Note that the actual value of b is not known by the algorithm. This is intuitive since Kint Kff.=.B Kint for all b, B E R. as proved in Theorem 2 of (Honda and Takemura, 2015). Different theoretical tools could allow to prove a logarithmic regret for QDS in the doubly unbounded case. possibly with a symmetric treatment of the two tails. We leave this extension for future work.
One may wonder whether the couple quantile condition/truncation is necessary to achieve theoretical results as well as good practical performance. Our last algorithm investigates this issue.
Robust regret for light-tailed distributions We call Robust Dirichlet Sumpling (RDS) the algo- rithm with bonus (X,,, 14: Pr), where the leverage Pn a function of the sample size n = | We prove that while being very simple, RDS achieves a robust sub-linear regret bound when each arm comes from any unknown light-tailed distribution, that we define as the family
Fe = (v E F(-00+000) Zr2 > 0, YY E [->u; Az), E. (cxp(AX)) < +00}
Theorem 3.7 (Robust regret bound for RDS). Let v = (V1,..., .......V vK) a bandit model satisfying
vk E Fe for all k. Consider any increasing sequence (Pn)neN with Pa. +00, Pn o(n). Then, for T large enough the expected number of pull of any sub-optimal arm in RDS is upper bounded by
E[N&(T)) < n. 7.50 (T)
(T) 0(1),
where any 1) E (0, 10, > 0, (T) is the sequence satisfying
m. (T) n((Ak -0) (M (Ma.ng -p) -b) with MR -max { 1::
log T
)) sPn
nkk
exp
-
nlolon)))
In particular, if pn = Olog n) then E[N+ = Ollo((T) log log(T)) for any light-ailed distribu- tion U4 E Fe.
The sequence Mn.n is large probability upper bound of the maximum of n observations from Fr. that we discuss in Appendix D. For light-tailed distributions, it holds that Mr... Ologn) (using Jensen inequality as in the proof of Theorem 2.5 in Boucheron et al. (2013)) Hence, choosing Pn = Olog n) we can further obtain the simpler upper bound in (log(T) log lTg( This slightly rate is a consequence of Lemma 3.3. In our opinion this is a small cost compared to the adaptive power of RDS. We call the algorithm robust because these theoretical guarantees are obtained on the broad class of light-tailed distributions, without any additional assumption. We recommend the leverage function p.. = O( ((o/lo((++1) which corresponds to the growth rate of the maximum of sub-Gaussian samples and empirically validated (see Appendix F). We emphasize that RDS thus avoids all hyperparameter tuning, desirable feature for the practitioner with little information on the problem she faces. Furthermore, in the next section we show that this algorithm performs very well in practice despite its non-logarithmic asymptotic guarantees.
8

---

Application in crop-farming environment
We consider practical decision decision-making problem using the DSSAT simulator (Hoogenboom et al., 2019). Harnessing more than 30 years expert knowledge, this simulator is calibrated on historical field data (soil measurements, genetics, planting date...) and generates realistic crop yields. Such simulations are used to explore crop management policies in silico before implementing them in the real world, where their actual effect may take months years to manifest themselves. More specifically, we model the problem of selecting a planting date for maize grains among 7 possible options, all else being equal, variability as well as exogenous randomness coming from stochastic meteorologic model. We illustrate this in Figure I with the histogram of four of these distributions, computed on 10 samples. They are typically right-skewed. multimodal and exhibit a peak at zero corresponding to years of poor harvest, hence they hardly fit a convenient parametric model (e.g SPEF/sub-Gaussian
7-armed bandit. The resulting distributions incorporate historical
3013
3271
3397
8119
Figure I: Distribution simulated dry grain yield (kg/ha) for four out of seven different planting dates. Reported the x-axis are the distribution minimum, mean and maximum values. The optimal arm is the third one (mean 3630 kg/ha).
Benchmarks A natural choice for the learner would be to use algorithms adapted for bounded distributions with known support. Indeed, one could argue that crop yields are fundamentally bounded by a very large value, that can be provided with some expert knowledge. However this method may have limits when the upper bound cannot be estimated accurately (few data, environment, ...), as a conservative bound can have cost on the regret. For this reason, we believe that the novel Dirichlet Sampling algorithms introduce in Section 3.2 problem. In particular, the three algorithms we propose in this paper are relevant in this setting: BDS keeps the bounded-support hypothesis but introduces the possible uncertainty while the light-tailed hypothesis of RDS and the quantile condition of QDS look reasonable. In Figure compare DS algorithms empirical IMED (Honda and Takemura, 2015) and NPTS (Riou and Honda, 2020), with two upper bounds: 1) the "exact" upper bound is provided looking at the maximum of all historical data collected (left figure), and 2) the algorithms use conservative estimate with value 1.5 times larger than the previous one (right figure). To avoid cluttering, we only report the performance of IMED and NPTS they were the most competitive baselines on this problem, but report figures with other competitors (e.g UCB1, Bernoulli TS, SDA) in Appendix F.
good alternative choice for this
the bound,
Tuning For BDS choose the parameters P = 4, 3500, corresponding p 20% in the hypothesis of Theorem 3.4, which is conservative in our example. For QDS, we set = 4 to be able to compare with BDS and a quantile 95%. Finally for RDS, we choose = Vlog (1 (1+n), which enters into the theoretical framework of Theorem 3.7.
Results Our results show that Dirichlet Sampling algorithms achieve similar or slightly lower regret to their competitors when the latter allowed to the "exact" upper bound, and compare favorably when they use a conservative estimate (1.5 times larger, right), see Figure 2. In particular, RDS the overall winner in both experiments. We think this demonstrates the merits of trading-off logarithmic regret (albeit only by factor O (log log T for finite-time adaptation to the tail behaviour via the leverage Pu. As side remark, note that round-based implementation is more efficient than NPTS as it does not draw random weights for the leader, which the most costly operation at each round. The code to reproduce the experiments is available in this github repository.
Decision Support System for Agrotechnology Transfer is an open-source project maintained by the DSSAT Foundation, see https: dssat. net//

---

empirical
IMED
empirical
IMED
NPTS
NPTS
600K
BDS
BDS
60OK
RDS
RDS
QDS
QDS
300K
300K
10K
10K
Figure 2: Average regret on 5000 simulations and horizon T = 10 Dashed lines correspond to 5%-95% regret quantiles. Empirical IMED and NPTS are run with exact upper bounds around 1.5 x 10 kg/ha (left) and the conservative upper bound 1.5 x 104 kg/ha (right).
Other experiments To further illustrate the properties of DS algorithms. we perform additional experiments on synthetic examples. Due to space limits, we present our results in Appendix F. First, we test the sensitivity DS w.r.t its hyperparameters, and check that their impact on the performance of the algorithms is moderate. Then, we show the merits of RDS in case of model misspecification, following the robustness experiments of Ashutosh et al. (2021). Finally, we consider the case of Gaussian mixtures, a common tool to model nonparametric distributions via kernel density estimation, and show that they fit the scope of DS but not that of usual bandit algorithms.
Conclusion
In this paper, we introduced new framework for randomized exploration in stochastic bandits based on resampling of the reward history and data-dependent bonus, which generalizes an opti- mal Thompson Sampling strategy for bounded distributions to light-tailed families. We proposed three instances of such Dirichlet Sampling (DS) algorithms, corresponding to different modeling assumptions. In our opinion, these algorithms appealing for the practitioner because 1) our theoretical results show strong guarantees under different settings, 2) DS algorithms are simple to implement despite the technically challenging analysis and achieve strong practical performances, and 3) they provide alternative robust ways to tackle unbounded distributions in bandit problems. Interesting future directions include extending the DS framework heavy tail distributions, and tightening the analysis of Boundary Crossing Probabilities of Section 3.1 to design sharper bonuses for general families of distributions motivated by real use-cases. Moreover, we believe the duel-based structure associated with the generic regret decomposition of Theorem 3.1 opens up new perspectives design exploration strategies in bandits. In particular, they allow to analyze policies using the history of two arms in the computation of single index.
Acknowledgments and Disclosure of Funding
The PhD of Dorian Baudry and Patrick Saux are respectively funded by a CNRS80 grant and the Université de Lille Nord Europe's 's I-SITE EXPAND, part of the Bandits For Health (B4H) project. This work has been supported by the French Ministry of Higher Education and Research, Inria, Scool, and the French Agence Nationale de la Recherche (ANR) under grant ANR-16-CE40-1 BADASS project).
(the
We thank the anonymous reviewers for their careful reading of the paper and their suggestions for improvements. We also warmly thank Emilie Kaufmann who managed carefully read the paper and make (as always) very useful comments while taking care of little Pascal, and Romain Gautron for his precious help for the experiments involving the DSSAT simulator. Experiments presented in this paper were carried out using the Grid' 5000 testbed, supported by scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https:/wwww.rri55000.n
10

---

References
R. Agrawal. Sample mean based index policies with o (log n) regret for the multi-armed bandit problem. Advances in Applied Probability, pages 1054-1078, 1995.
Agrawal and N. Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. In Proceedings of the 25th Annual Conference on Learning Theory, 2012.
S. Agrawal, W. M. Koolen, and S. Juneja. Optimal best-arm identification methods for tail-risk measures, Xrxiv preprint arXiv:2008.07666 2020.
K. Ashutosh, J. Nair, A. Kagrecha, and K. Jagannathan. Bandit algorithms: Letting go of logarithmic regret for statistical robustness. In International Conference on Artificial Intelligence and Statistics, pages 622-630. PMLR, 2021.
P. Auer, N. Machine learning. 47(2):33--256, 2002.
and P. Fischer. Finite-time analysis of the multiarmed bandit problem.
A. Baransi, O.-A. Maillard, and Mannor. Sub-sampling for multi-armed bandits. In Proceedings of the European Conference on Machine Learning, page 13, 2014.
D. Baudry, E. Kaufmann, and O.-A. Maillard. Sub-sampling for efficient non-parametric bandit exploration. Advances in Neural Information Processing Systems, 2020.
D. Baudry, R. Gautron, E. Kaufmann, and O. Maillard. Optimal thompson sampling strategies for support-aware aware evar bandits. Proceedings of Machine Learning Research. PMLR, 2021a.
D. Baudry, Y. Russac, and O. Cappé. On Limited-Memory Subsampling Strategies for Bandits. In ICML 2021- International Conference on Machine Learning, Vienna / Virtual, Austria, July 2021b.
S. P. Bhat and P. L.A. Concentration of risk measures: A wasserstein distance approach. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché-Buu Buc, E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities: independence. Oxford University Press, 2013.
asymptotic theory of
S. Bubeck, N. BisacBia and G. Lugosi. Bandits with heavy tail. IEEE Transactions on Information Theory, 59(1 (9(11))7711-711 2013.
A. N. Burnetas and M. N. Katehakis. Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics, 17(2): 1996.
O. Cappé, A. Garivier O.-A Maillard, R. Munos, and G. Stoltz. Kullback-Leibler upper confidence bounds for optimal sequential allocation. Annals of Statistics, 4163):1116-154,, 2013.
H. Chan. The multi-armed bandit problem: An efficient nonparametric solution. The Annals of Statistics, 48(1):346-333 2020.
Y. Cho and E. Cho. The volume of simplices clipped by half space. Applied mathematics letters, 14 (6):731-735, 2001.
A. Dembo and O. Zeitouni. Large Deviations Techniques and Applications, volume 95. 2010.
N. Fournier and A. Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(3-4):707, Aug. 2015.
H. Hadiji and Stoltz. Adaptation to the range in k-armed bandits. arXiv preprint arXiv:2006.03378. 2020.
J. Honda and A. Takemura. An asymptotically optimal bandit algorithm for bounded support models. In COLT, pages 67-79, 2010.
J. Honda and A. Takemura. Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. J. Mach. Learn. Res., 16:3721-3756, 2015.
G. Hoogenboom, C. Porter, Boote, Shelia, Wilkens, U. Singh, J. White, Asseng, Lizaso,
L. Moreno, et al. The dssat crop modeling ecosystem. Advances in crop modelling for sustainable agriculture, pages 173-216. 2019.
N. Korda, E. Kaufmann, and R. Munos. Thompson sampling for one-dimensional exponential family
bandits. In Advances in Neural Information Processing Systems, 2013.
11

---

B. Kveton, C. Szepesvári, M. Ghavamzadeh, and C. Boutilier. Perturbed history exploration in stochastic multi aamed bandits. In Proceedings of the Ehenty-Eightee International Joint Conference on Artificial Intelligence, IJCAI 2019, 2019a.
B. Kveton, C. Szepesvari, S. Vaswani, Z. Wen, T. Lattimore, and M. Ghavamzadeh. Garbage in, reward out: Bootstrapping exploration in multi-armed bandits. In International Conference on Machine Learning, pages 3601-3610. PMLR, 2019b.
T. L.. Lai and H. Robbins. Asympiotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Massart. The tight constant in the Dvoretzky-Kiethe Kiefer-Wolfowee inequality. The annals of Probabil- ity, pages 1269-1283, 1990.
I. Osband and B. V. Roy. Bootstrapped Thompson sampling and deep exploration. 0bs/1507.006 00300, 2015.
CoRR,
C. Riou and Honda. Bandit algorithms based on Thompson sampling for bounded reward distribu- tions. In Algorithmic Learning Theory, pages 777-826. PMLR, 2020.
W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):25-2294, 1933.
C. Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
C.-H. Wang, Y. Yu, B. Hao, and G. Cheng. Residual bootstrap exploration for bandit algorithms. arXiv preprint 2rXiv:2002.084333 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We present in this work bandit algorithm and show an application in a decision-making problem in agriculture.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See for instance Section 3.2 where we introduce our main result.
(b) Did you include complete proofs of all theoretical results? [Yes] To respect the page limit all the proofs are presented in Appendix C.2 (results the BCP), B (proof of Theorem 3.1), D (proof of Theorem 3.4, 3.5, 3.7).
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URLY? [Yes] See Supple- mentary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We specify the parameters of the distributions and the parameters of the bandit algorithms in the code, and explain their choice in Section 4
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] Confidence intervals are represented in all our figures. (d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [N/A] Our code does not require powerful computing ressources, experiments are replicable with laptop.
4. If you using existing assets (c.g., code, data, models) or curating/releasing assets...
12

---

(a) If your work uses existing assets, did you cite the creators? [Yes] We provided
references for the DSSAT environment.
(b) Did you mention the license of the assets? [Yes] DSSAT is open-source.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "tV62Z7mk_N5", "reviewer": "Reviewer_8C9i", "summary": "This paper considers robustness of MAB algorithm to model misspecification when knowledge on the distribution (e.g., tails) is not directly accessible. They study a generic Dirichlet Sampling algorithm and provide a generic theorem for regret decomposition. They applied the algorithm in three examples: 1) bounded distributions where optimal regret can be achieved, 2) light-tailed unbounded distributions where we can achieve slightly-worse-than-log regret through simple tuning strategies, and 3) unbounded distributions with some quantile condition where log regret is achievable.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*Originality*\n\nI'm not too familiar with this specific line of literature so can't comment with full confidence on its originality. From my understanding, it fills in a gap in existing works: it achieves logarithmic regret without specifying the tail with precise parameters, and also avoids pathological distributions that are not likely to be true in practice by imposing a quantile condition.\n\n*Quality*\n\n- This paper tells a complete story with all theorems proved and their implications well explained. The Dirichlet Sampling bandit algorithm looks intuitive to me on a high-level.\n\n- Some clarification questions:\n1. For theorem 3.5, can you elaborate on how we get $g_k = O(\\sqrt{\\log n})$ for sub-gaussian and $O(\\log n)$ for sub-exponential? Also, I'm a bit confused at its \"robustness\"; from my understanding of Theorem 3.5, $\\rho_n$ can't be arbitrary and needs to be of order lower than $g_k$?\n2. I don't fully understand why $\\mathcal{T}_{\\alpha}(\\mu)(\\{x\\})$ should be defined as $\\alpha$ at CVaR. Can you explain?\n3. In Theorem 3.6, how does $b$ come into this regret? Why the current proof does not support $b=-\\infty$? What's making $b=-\\infty$ difficult?\n\n*Clarity*\n\nThis paper is overall well organized. However, I do think it's a bit notation-heavy and sometimes makes the reading experience not so smooth (though authors do summarize notations in Appendix A). I am occasionally confused, for example, what's $M_{\\nu, \\mu, \\rho}$ in line 280? Besides, I think it would be good if the authors could provide more intuitive explanations. For example, in \"Logarithmic regret for unbounded distributions\", it can be helpful to also verbally discuss what these quantities represent and why they are important, which can save some processing time for readers.\n\n*Significance* \n\nI view this submission as a solid contribution to a somewhat relevant problem. In particular, many distributions I see in practice do look like Figure 1, so it can be of some values to practitioners.\n\n\n__________\n\nAfter discussion: I think my questions were well-addressed by the authors, so I'm willing to raise my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the limitations in the perspectives section. They look fair to me (as a non-expert reviewer in this particular line of work), and I look forward to their response to questions / comments in \"Main Review\".", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5 hours"}, "extra_text": {}}, {"review_id": "c9swBraAyj", "reviewer": "Reviewer_MKzx", "summary": "This work investigates a Dirichlet Sampling algorithm in stochastic multi-arm bandit problem. From the theoretical perspective, this work provides regret bounds of the DS algorithms for three different instances such as bounded, general light-tailed, and light-tailed distribution with additional quantile assumption. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: \nIt is a novel approach to combine non-parametric Thompson sampling with pairwise comparison between arms. Also, this duel-based structure makes it possible to have a general regret decomposition for index, which gives a theoretical foundation for three bandit setups.\n\nQuality: \nTheoretical results sound well-grounded and numerical experiments seem reasonably fair and supportive to this theoretical outcome, which makes a complete piece.\n\nClarity: \nThis submission starts with clear categorization for algorithm families, introduces sub-sampling based algorithm family, and develop new algorithms by combining existing algorithm along with novel duel structure. Theoretical arguments and following experimental results are overall well organized and easy to read.\n\nSignificance: \nThere are three algorithm categories for stochastic multi-arm bandit problems: UCB-type, TS-type algorithms, and sub-sampling based methods. This work focuses on third one, and extensively generalizes asymptotic theoretical guarantee to outside of single-para exponential family. Also, the DS algorithm this work suggested is useful in practice in that it does not require prior knowledge on the tail distributions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The last paragraph is denoted as \"Perspective\", but I suggest to have \"Conclusion\" section instead to make body better organized.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "D3iRGep36yd", "reviewer": "Reviewer_37Ux", "summary": "The goal of this paper is to construct a sequential decision-making algorithm under non-standard distributional assumptions. The authors propose a Dirichlet Sampling algorithm, employing pairwise comparisons of indices computed with the arms’ observations and a data-dependent exploration bonus.  They suggest three specific variants of this strategy under different distributional assumptions having distinct tail behaviors.  When it is applied to the bounded distributions, the algorithm is shown to be optimal. Numerical studies display some advantages of the proposed algorithms.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors study a class of algorithms that spins off nonparametric Thompson Sampling (NPTS) along the line of Subsample-mean comparisons (SSMC).  Their motivation is to handle so-called light-tailed distributions which cover more relaxed distributions than bounded or subgaussian distributions but avoids difficult situations of `mass leakage’ to infinity, which is the main cause of technical difficulties. The authors draw strengths of the distribution-free nature of NPTS and SSMC to compose a generic class of algorithms and give three specific cases with varying degrees of tail behavior. Regret analysis for each case and numerical studies are provided.  \n\nThe paper is dense and has a lot of information, yet is well written. The authors blend existing ideas of NPTS and SSMC which do not rely on any particular distributional assumptions.    Bringing pairwise comparison through SSMC seems to be a smart idea to estimate the critical value through subsampling without resorting to the distributional properties.  \n\nIt is nice to see finding a class of distributions satisfying Condition 2.  Some intuitive explanations on Condition 2 would be helpful.  \n\nIn the numerical studies, don’t we need to include the UCB in the comparison list? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In the numerical studies, don’t we need to include the UCB in the comparison list? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: I believe there is a strong consensus around this paper's novelty and its contributions, and on that note it is also a good chance to thank the reviewers and authors for the informative dialogue. From my own reading I can add that while the problem is well motivated, the exposition in various parts and the notational conventions make the paper less accessible than it can be and this is something that can be improved with the final version (I hope). It may also be worth commenting further on the nature of the histograms and the relevance to ones seen in various modeling instances, e.g., mixture models,  to ensure these are not perceived as just esoteric one-off examples.  
Decision: Accept (Poster)