Maximum Average Randomly Sampled: A Scale Free and Non-parametric Algorithm for Stochastic Bandits
Authors: Masoud Moravej Khorasani
Erik Weyer
Venue: NeurIPS 2023 poster (2023)
Keywords: Stochastic Multi-armed bandit
Online Learning
Upper Confidence Bound
TL;DR: A data-dependent UCB algorithm for multi-armed bandits that eliminates the need for prior scale parameter knowledge, constructing upper confidence bounds based on randomly sampled rewards, with a derived regret bound

Abstract: Upper Confidence Bound (UCB) methods are one of the most effective methods in dealing with the exploration-exploitation trade-off in online decision-making problems. The confidence bounds utilized in UCB methods tend to be constructed based on concentration equalities which are usually dependent on a parameter of scale (e.g. a bound on the payoffs, a variance, or a subgaussian parameter) that must be known in advance. The necessity of knowing a scale parameter a priori and the fact that the confidence bounds only use the tail information can deteriorate the performance of the UCB methods.

Here we propose a data-dependent UCB algorithm called MARS (Maximum Average Randomly Sampled) in a non-parametric setup for multi-armed bandits with symmetric rewards. The algorithm does not depend on any scaling, and the data-dependent upper confidence bound is constructed based on the maximum average of randomly sampled rewards inspired by the work of Hartigan in the 1960s and 70s. A regret bound for the multi-armed bandit problem is derived under the same assumptions as for the $\psi$-UCB method without incorporating any correction factors. The method is illustrated and compared with baseline algorithms in numerical experiments.

Maximum Average Randomly Sampled: A Scale Free and Non-parametric Algorithm for Stochastic Bandits
Masoud Moravej Khorasani"
Department of Electrical and Electronic Engineering
The University of Melbourne Parkville, Melbourne, Victoria, Australia m. moravej kh@gmail, com
Erik Weyer
Department of Electrical and Electronic Engineering
The University of Melbourne Parkville, Melbourne, Victoria, Australia ewey@unimelb. edu. au
Abstract
Upper Confidence Bound (UCB) methods are one of the most effective methods in dealing with the exploration opplorationeexploitatioo trade-off in online secision-making problems. The confidence bounds utilized in UCB methods tend to be constructed based on concentration equalities which are usually dependent on a parameter scale (e.g. bound the payoffs, variance, must be known in advance. The necessity of knowing a scale parameter a priori and the fact that the confidence bounds only use the tail information deteriorate the performance of the UCB methods. Here we propose data-dependent UCB algorithm called MARS (Maximum Average of Randomly Sampled Rewards) in a -on-paramctric setup for multi-armed bandits with symmetric rewards. The algorithm does depend on any scaling, and the data deta-dependent upper confidence bound is constructed based on the maximum average of randomly sampled rewards inspired by the work of Hartigan in the 1960s and 70s. A regret bound for the multi- armed bandit problem is derived under the same assumptions as for the 3U-UCB method without incorporating any correction factors. The method is illustrated and compared with baseline algorithms in numerical experiments.
subgaussian parameter) that
Introduction
The classical stochastic multi-armed bandit problem introduced by [21) has been studied extensively in statistics, computer science, electrical engineering, and economics. New applications in machine learning and data science such as personalized new recommendation and Monte-Carlo tree search have generated renewed interest in the problem.
The problem is described as follows: The classical stochastic multi-armed bandit problem is an online decision-make problem where each arm represents action. At each round E {1.... nn) the agent chooses an action (arm) A, E A and observe a reward X, E IR where A is the set of available actions and its finite cardinality is K 2. The reward X, is sample from underlying distribution
*The code reproduce the results of the paper found at httpp:///gptaiiii wwt.hab.coo/aaaoouaoooaaaaaaa/e
MARS-Neur
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

VA, with bounded mean MA., Hence, stochastic bandit is a set of distributions v = fus A} which is unknown for the agent.
The agent aims to minimize the following regret over y rounds.
n
R
n max Pi E
Σ
X
(I)
EA
with respect to the actions A A.
The minimization of the regret necessitates balancing the trade-off between exploration and ex- ploitation where exploration means investigation to accumulate more information about arms and exploitation means the maximization of the immediate performance. See the book [9] and survey 7 for comprehensive discussion.
class of algorithms for multi-armed bandit problems that strikes balance between exploration and exploitation is Upper Confidence Bound (UCB) methods 3 12 I
The UCB algorithm is based on the principle of optimism in the face of uncertainty. According to this principle, one should construct probabilistically optimistic guesses for the expected payoff (mean) of all actions and play the with the highest guess. The performance of the UCB algorithms in dealing with the exploration exploitation dilemma depends on the tightness the upper confidence bound. The literature includes several approaches which construct upper confidence bound based on concentration inequalities such as Hoeffding-tyie inequalities 4 and self-normalized inequalities 1
exploration-exploittiii
As an example gCUCC Method introduced in assumes that there exist convex function (³(+) which satisfy the following conditions.
Vt, A 2 0, log Bee
(A) and log B(M s (()).
(2)
Let (.) be the Legendre- Fenchel transform of ()))), that
(E) - sup(As (A)),
AER
Then, with probability at least
Bs, (1b))-1 (1 log (1))
where i4. is the sample mean of rewards obtained by pulling arm for times.
At time f, using the obtained UCB and letting 5 = 1/t?,, we select
T) - (((tt-1))] 1
log(t)
A = armax,
where T.(t - 1) denotes the number of times action was chosen by the learner after the end of round 1 1. It was proved 7 that:
3 (A,/2)
R S Σ
log(n) +
#A,
where A; is the suboptimality gap A; = maxiE P4
However, there two weaknesses associated with the bounds obtained by concentration inequalities as above. First, they are commonly conservative since they are not data-dependent and only care about tail information of distribution. Second, those bounds usually depend on scaling factors or functions, egg. vb()) in (-CC-UCB and poor choices can make the bounds conservative.
1.1 Related Works
Recently several works have focused on non-parametric bandit algorithms based on subsampling and bootstrapping 18
22 Those works use the empirical distribution of the data instead of fitting given model to the data. The Garbage In, Reward Out (GIRO) method [18 relies on the

---

history of past observed rewards and enhances its regret bound by augmenting fake samples into the history. The Perturbed- -ettrred--History Exploration method (PHE) [7 serves as faster and memory- alternative to GIRO. However, PHE has the limitation of being restricted to bounded distributions and involves tunable parameter. The Residual Bootstrap exploration (ReBoot) 22 perturbs the history in order to improve the regret bound.
Bootstrapping Upper Confidence Bound uses bootstrap to construct sharper confidence intervals in UCB-type algorithm [2]. However, a second-order correction is used to guarantee the non- asymptotic validity of the bootstrap threshold. The second-order correction is not sharp, and includes scaling factors.
Another line of works which include the Best Empirical Sampled Average method (BESA) [5] and the Sub-sampling Duelling Algorithms (SDA) [6] use subsampling to conduct pairwise comparison (duels) between arms. BESA organize the duels between arms and find the winner by comparing the empirical average of sub-sampled rewards. SDA extends the concept of BESA duels to a round-based comparison by incorporating sub-sampling scheme and it eliminates the need for forced exploration.
Apart from Reboot which was analysed for Gaussian distributions, and SDA which was analysed for family of distribution satisfying balance condition (including Gaussian and Poisson), the other algorithms were analysed for distributions with known bounded support.
1.2 Contributions
In this paper, we propose a new non non-parane non-parametric UCB algorithm which is fully data-dependent without any scale parameter. The proposed approach called MARS (Maximum Average Randomly Sampled) constructs data-dependent upper confidence bound by selecting the maximum average among randomly sampled rewards. This upper confidence bound is inspired by Leave-out Sign- dominant Correlation Regions (LSCC) method which construct non-asymptotic confidence regions for parameters of dynamical systems (8 9 [1] 15 20 16). The upper confidence bound inspired by LSCR is non-asymptotic and probabilistically guaranteed, i.e. larger than the true value with an exact user-chosen probability and for finite number of data points.
The problem-dependent regret bound of the method given for multi-armed bandits where all underlying distributions {v; E A} are symmetrically distributed about their mean e.g. exponential, uniform, or logistic distribution and inequality (2) satisfied. As (-(-) does not need to be known, MARS avoids the problem with sub-optimal choice of vi(-), and still achieves logarithmic regret.
1.3 Notation
subset of positive integers up to and including a constant i is denoted as [k] - f1..... is the smallest integer greater than or equal to x. The cardinality of set S is denoted by |S]. e.g. [[K]] = kt I(A predicate) is the indicator function defined as
......,), k).. [x]
{ 0
if the predicate is TRUE,
I(A predicate)
otherwise,
Without loss of generality assume the first arm is optimal i.c. μ4 = max, μ4. Define the sub-optimality gap A, #1 #r for i E ... KK. Further, let
T:(1) = IAA==i)
be the number of times action was chosen by the learner after the end round t. Xx,s is the reward the jth time arm i is pulled. U(a b) is a uniform distribution bounded by and b (a < b), and B(a) a Bernoulli distribution with mean a.
The remainder of the paper is organized as follows. In the next section, a new randomized approach to compute an upper confidence bound is presented. In Section the non-parametric UCB algorithm is introduced and regret bound for the multi-armed bandit problem with symmetric rewards is given. Section 4 expllore the numerical performance the proposed MARS method, and Section concludes the paper.
3

---

2 A New Randomized Upper Confidence Bound
In this section, an approach compute data-dependent upper confidence bound for a finite number of observations is proposed.
Hartigan in [4 proposed approach which is useful compute confidence interval for unknown parameter. The confidence interval was computed by a number estimates the mean using different subsets of the data. The estimates of the mean in [[2] was computed using number of balanced sets of subsamples determined by group theory.
The paper [9] used random strings instead of balanced sets of subsamples which brings computational advantage. Now, we use the method in [4] and to propose a new non-asymptotic upper confidence bound.
We have the observations { from arm and we want to find an upper confidence bound UCB; with probability 1 - 5 such that
Pr(UCB, 2 p.) 2-
In this section T; is assumed to be fixed number of observations which does not depend on other actions taken or observed rewards. In Section the situation where T; dependent on the past actions and observed rewards will be considered.
Before introducing the new upper confidence bound, let define typical values.
Definition 1. The set of ascending ooddered and continuously distributed random variables Z(1,, Ziz)...., -11-11) a set of typical values for μ if the probabilities that μ belongs to each of following intervals are the same
(-0,,Z(1, Z(2)) ....., (Z.-)()))))):
that is
=... Pr (M( 2()) Pr =... Pr (1)) = M
Now, based on Theorem in g the following theorem introduces set of typical values for the means of ith arm Hi.
Theorem 1. We have the observations {X from arm i and E(Xi,s = 14 for all E [Ti]. Assume that the observations {Xi.s} admit continuous distributions and are independent and symmetrically distributed about their mean.
Then, a typical values for p4 given by
Σ hy Xis for [M 1]
ES 11j.
where M 2h is positive integer and {hy,1} are independent random sequences such that
Pr(h = 0} = Pr(h,,, = 1
A string (hg,e) \ sm is discarded turns out to be equal already constructed string.
Proof. Follows along the same line as the Proof of Theorem in See Section in the supplement for further details.
Theorem I shows that typical values for μi; and partition the real line into equiprobable segments where μni belong each one of those segments with equal probability. As a consequence of Theorem [ we conclude that
estimates mean computed by random sub-sampling are a set of
Pr. max JE[M-1]
1- 1/M.
M is user-chosen parameter and hence the probability the confidence bound can tuned by the user. Since M < 27 the maximum confidence which can be achieved by computing subsample

---

max, Xi,s
w.p. 827.
log(d -1 1ng(2)
if i;; <
UCB
w.p. -
max, (t),
otherwise
Table 1: Data-dependent and scale-free UCB.
means is 1/2": and we can not get upper confidence bound with arbitrary high confidence. To overcome this problem, we use the fact that all means μ4 are bounded and the following upper confidence bound is proposed.
Compute M [6-11 random subsample means as The non-parametric upper confidence
bound is given in Table
The probability of the constructed upper confidence bound is presented in the next theorem.
Theorem
Let T, be a fixed number of observations from arm i. For each i [K] assume {X,,a s= independent random variables with continuous distribution functions which are symmetrically distributed about its mean p4, Let the user-chosen parameter E (0, 1) be chosen such that 8-1 is an integer. Then for all T; > 0 the following non-asymptotic equality holds
Pr(UCB; 2 [4] 11-
(5)
Note that T; is deterministic, and the probability is with respect to both {Xs, and {hg,
Proof. See Section 2 in the supplement.
Theorem shows that the probability of the proposed confidence region is exact and hence it is conservative. This result holds for a finite number of observations long the reward is symmetrically distributed around its mean and T; is fixed given number.
In Figure we compare different approaches calculate 95% UCB for the population mean based on samples from Gaussian and uniform distribution. The upper confidence bounds are calculated for different number of data points. The almost exact quantile is computed by finding 95% quantile of the population of sample means available by repeating experiment 10000 times. Naive bootstrap threshold and bootstrapped threshold were computed by equation (2.6) in Remark 2.3 in [12
Example 1
The figures shows that for most sample sizes the MARS bound is sharper than naive bootstrapped threshold, bootstrapped threshold, sub-Gausae Gaussian bound, and Hoeffding bound. The naive bootstrap is sharper for small sample sizes, but as shown in [12). naive bootstrap do not produce reliable results for small samples sizes. It is also notable that the MARS bound is probabilistically guaranteed for finite number of data points as shown Theorem 2
Algorithm and Regret Bound
The UCB method using the proposed upper confidence bound for rounds is given in Algorithm At the initial rounds, the algorithm tends to adopt an optimistic outlook in the face of uncertainty. This is reflected in the upper confidence bound, which is set infinity or the highest reward observed. As the number of rounds increases, the upper confidence bounds approach the mean reward for each arm with high probability. Consequently, the algorithm progressively leans towards exploitation.
two or more UCBs in line 15 Algorithm among the minimizers.
take on the same value, randomly choose an action
MARS necessitates keeping [1/8] sub-sampled means for each arm. This leads to memory requirement of O(Kn) when 1/n. The computational complexity of MARS is also depends
5

---

16:
Dactericeed Prandd
Phaviie (O0lecrn 2ound
88-
32
6.0
201
420
(a)
(b)
Figure I: 95% UCBs of sample means computed by different approaches. The underlying distribu- tions uniform between -1 and +1 in (a) and Gaussian with mean 0 and variance in (b). The results are averaged over 10000 realisations.
Algorithm Maximum Average Randomly Sampled (MARS)
Input:
I: M + [8-1]
Initialization
2: E [K], Vj E [M] T.(0) + 0, H3g +
3: for + to n do
4:
i to K do
Computing upper confidence bound
5:
(t 1) = then
6:
UT 1)
else 0 < Ti(t 1) log(d then Tog[2)
7:
8:
Draw x 1))
9:
if x < (t?.(t-1) then
10:
UCB, ()) +- x0
11:
else
12:
UCB, (T:(( 1), + max, Xi.
else
14:
UCB:(Ti(1 1), < max; (1)
15:
A. < argmax, UCB, (T) 1),
Pulled arm
16:
Pull Arm A, and observe reward X,
17:
for i < 1 to K do if A, then
Update statistics
19:
TI(() 7,(1 1) +
20:
for j < 1 to M do
21:
Draw h4 B(0.5)
22:
Hj + H9g + hj
(t(()) +- (Hi 1)0 (1-
23:
24:
else
25:
for j 1 to M
26:
T2(1) + T -) (z((t) (t)
27:
on the choice of 6, as updating [1/6] sub-sampled means is performed in each round. Notably, to reduce the computational burden, the required Bernoulli variables the algorithm can be generated and stored before the start of the game.

---

The Next theorem provides a regret bound for the proposed MARS algorithm when applied to bandit problems with symmetric distributions.
Theorem 3. Let Ti(n) 0 be the total number of observation from arm i and 1/12. The following assumptions about all arms E [K] are in place.
)m are continuously distributed and independent random variables symmetrically distributed about its mean p4. The observations Xi,s for each arm i E [K] are independent of the observations from other arms and actions.
For all i [K] and E [T], there is a convex convexffucction (xr such that:
log (x -
E(Xx,))) s (A(
Then the regret is bounded by
(3
3 llg(n))
R(n) 5
Σ
D.
(6)
1A.20
where
1 1
exp( v. (Ai))
22 = = log
2
2
and (.) is the Legendre-Fenchel transform of (.)()), that is
(E) - sup(>e (A))
XER
Note that the expectation in the regret is with respect to both { and {h
Proof. See Section 3 in the supplement.
In Theorem we set 1/n² to simplify analysis. similar regret bound can also be achieved using 6, 1/22. is also notable that the regret bound in Theorem was achieved without any knowledge about the functions 4/s (A) apart from its existence. In particular, it was not used when the upper confidence bounds were computed. However, the eU-UCB method assumed that thr(A) (A)s known and used it in constructing the upper confidence bound.
The next corollary characterises a relationship between the regret bounds of the current method and those the UCUB method.
Corollary 1. Provided that 4 (A.) < 1.59, the regret bound O is simplified as follows
(lg(())
R(n) <
Σ
3
A,
W (A))
(A:20
Now, let for all arms i E [K]. the corresponding reward is a;-sub Gaussian. Then, 4 (A.) (2?))(2o?) Accordingly when (A?))(20?)
=
1.59 the regret bound is simplified to
3 + 12o; log(n)
R(n) v
Σ
(8)
A
$A,50
Proof. See Section 4 in the supplement.
As shown in equation (6. the regret bound for MARS is always O(log(n) without relying on the
use of (-). This demonstrates the effectiveness of the introduced non-parametric UCB method. When v/a (A,) < 1.59, the task becomes more challenging as identifying the optimal arms becomes harder. In such scenarios, both the regret bounds for the proposed MARS and the &UUCB, which employs (-)., become dependent on the function log(n)/vl (A,). Corollary [ also explore effectiveness of MARS when dealing with subgaussian rewards. It demonstrates that even without prior knowledge of the a; values, MARS successfully addresses bandit problems, achieving regret bound of O(Ei log(n)/ A,) for challenging scenarios where (2f)) 1.59.
7

---

Experiments
In this section, the performance of the proposed MARS method is compared with upper confidence bound based on concentration inequalities (Vanilla UCB, See c.g. Chapter 7 and in [19). Thompson sampling with normal prior (Normal-TS) (2) Bootstrapped UCB [2]. Garbage In, Reward Out (GIRO) [8] and Berturbed-Histonn Exploration (PHE) 17 implement these baseline methods.
The package PymaBandit was used
The probability of confidence regions the Vanilla UCB, Bootstrapped UCB, and the proposed MARS UCB is set to 0.999, i.e. 8 1/1000. In GIRO, the parameter a, which represents pseudo- rewards per unit of history, is set to 1. Due to the high sensitivity of the PHE approach to the choice of the tunable parameter a, simulations were performed for two values of a.
The number of arms K and the means are
1
1 4
1 = 5"
11 = 1, P2 - M3
14
145
First, consider the case where the rewards are Gaussian with variance for all arms. The cumulative regrets are show in Figure 2a Since Normal-TS uses distribution knowledge and the variances are correct it is the best as expected. The Vanilla UCB algorithm demonstrates comparable or superior performance compared to both the Bootstrapped UCB, MARS, and GIRO. The performance of the PHE approach is heavily dependent on the parameter When a 2.1, it shows linear regret. However, for a = 5.1, it outperforms most other approaches, except for Thompson sampling.
Both Vanilla UCB and Normal-TS depend the variances which were assumed known in the previous simulation. We repeat the simulation with the variances incorrectly set to 2. The result shown in Figure [bb Evidently MARS, GIRO, and Bootstrapped UCB outperform both Vanilla UCB and Normal-T' when incorrect values for the variances are used. MARS demonstrates superior performance over Bootstrapped UCB and GIRO after an initial set of rounds. Moreover, unlike GIRO and Bootstrapped UCB, MARS does not require the full storage of reward history, resulting in lower computational complexity. As previously observed, PHE with value of 2.1 demonstrated the poorest performance, whereas PHE with a value of 5.1 has the best performance.
Gr detic
Eostempped
12
tomer'
26-
(BO
HCIe-521
Rours
Faird
(a)
(b)
Figure 2: Cumulative regret for Gaussian bandit. The variances of rewards are true in (a) and wrong in (b). The results are averaged over 2000 realizations.
The MARS and GIRO do not use the tail information the rewards. However, Vanilla UCB, Normal- TS, and Bootstrapped UCB use the distribution and the tail information of the rewards respectively and their performance can deteriorate when the prior knowledge wrong or conservative. To illustrate this we repeated the simulation for the cases where the rewards admit uniform distribution over [-1, The results are shown Figure It shows that MARS which does not use the distribution of the rewards and the tail information, outperforms the other methods except PHE (a 2.1) in this case. An interesting observation that PHE (a = 5.1) exhibits outstanding performance in Gaussian setup, yet it performs poorly in Uniform setup, indicating strong reliance on the tunable
Thh package can be found at https: :/tp:w./wwwww//... di ens frwoiiiier http:///....ieee..ppp/e///////// wttppp//ooeeeee/eaaaaaaaa.ee

---

parameter. This dependence on the parameter could pose challenges in real-world applications where the environment unknown. In such cases methods like MARS and GIRO may be more practical alternatives.
Thompson
BoststrapUCB
60
PHE (a12.1)
PHE (a15.1)
Regret
40
10
250
500
750
1000
1250
1500
1750
2000
Round
Figure 3: Cumulative regret for uniform bandit. The results averaged over 2000 realizations.
See Section 5 in the supplement for further simulations.
5 Conclusion
In this paper, non-pane non-parametric and scale-free confidence bound was proposed based on random sub-sampling of rewards. The confidence bound was used to propose data-driven UCB algorithm. regret bound of the method for multi-armed bandit problems with symmetric distribution was presented, and it was shown that the regret bound is always O[log(n)). Moreover, the regret bound O(Es,,> log(n) /A,) for class of Bandit problems. Numerical experiments show that the proposed method performs well, and it outperforms baselines algorithms when the prior information mis-specified.
Extending the method to other bandit and reinforcement learning problems are interesting topics for future works e.g. evaluating the method on non-stationary bandits and contextual bandits using the ideas in [33 and [9]. As MARS does not use any concentration inequalities in the construction of the confidence bound, the application of MARS bandits with heavy tail is another interesting direction. Another interesting future direction is evaluation of the method on asymmetric rewads and robustification of the approach following ideas [00].
References
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaha Szepesvári. Improved algorithms lincar stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 201
[2] Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Artificial intelligence and statistics, pages 99-107, 2013.
[3] Peter Auer. Using confidence bounds for peploitation-xxpllraiett trade-offs. Journal of Machine Learning Research, ((Nov):397-422 2002.
Peter Auer, Nicolo Disa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-25 256. 2002.
[5] Akram Baransi, Ambrri Maillard, and Shie Mannor. Sub-sampling for nulti-armed bandits. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 115-131 Springer, 2014.

---

[6] Dorian Baudry, Emilie Kaufmann, and Odalric-Ambryn Maillard. Sub-sampling for efficient non- parametric bandit exploration. Advances in Neural Information Processing Systems, 33:5468-5478. 2020.
[7] Sébastien Bubeck, Nicolo Cesa- Dasa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-arme bandit problems. Foundations and Trends@ Machine Learning, 5(1):1-122, 2012.
[8] Marco C. Campi and Erik Weyer. Guaranteed non-asymptotic confidence regions in system identification. Automatica, 41(10):1751- 1-644, 2005.
[9] Marco C. Campi and Erik Weyer. Non-asymptotic confidence for the parameters of linear transfer functions, IEEE Transactions on Automatic Control, 55(12))2708-272 2010.
[10] Algo Care, Balázs Csanád Csáji, and Marco C. Campi. Sign-perturbed sums (SPS) with asymmetric noise: Robustness analysis and robustification techniques. In 2016 IEEE 55th Conference on Decision and Control (CDC). IEEE, 2016.
[11] Marco Dalai, Erik Weyer, Marco Campi. Parameter identification for nonlinear systems: Guaranteed confidence regions through LSCR. Automatica, 43(8):1418-1425, 2007.
[12] Botao Hao, Yasin Abbasi Yadkori. Zheng Wen, Guang Cheng. Bootstrapping upper confidence bound. In Advances in Neural Information Processing Systems, pages 12123-12133, 2019.
[13] Hartigan. Exact confidence intervals regression problems with independent symmetric errors. The Annals of Mathematical Statistics, pages 1992-1998, 1970.
[14] John Hartigan. Using subsample values as typical values. Journal of the American Statisticul Association. 1303331 1969.
[15] Masoud Moravej Khorasani and Erik Weyer. Non-asymptotic confidence regions the parameters of EIV systems. Automatica, 1 115:108873, 2020.
[16] Masoud Moravej Khorasani Erik Weyer. Non-asymptotic confidence regions for the transfer functions of eroos--n--variable systems. IEEE Transactions on Automatic Control, 67(5):2373-2388, 2021.
[17] Branislav Kveton, Csaha Szepesvari, Mohammad Ghavamzadeh, and Craig Boutilier. Perturbed-histon exploration in stochastic multi-armed bandits. arXiv preprint arXiv: 1902. 10089, 2019.
[18] Branislav Kveton, Csaba Szepesvari, Sharan Vaswani, Zheng Wen, Tor Lattimore, and Mohammad Ghavamzadeh. Garbage in, reward out: Bootstrapping exploration in multi-armed bandits. In International Conference on Machine Learning, pages 3601-3610. PMLR, 2019.
[19] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. preprint, page 28, 2018.
[20] Masoud Moravej Khorasani Erik Weyer. Non-asymptotic confidence regions errorsii-varrialles systems. In 18th IFAC symposium on system identification, volume 51, pages 1020-1025, Stockholm, Sweden, July 2018. IFAC-PapersOni
[21] Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):577-535 1952.
[22] Chi-Hua Wang, Yang Yu, Botao Hao, and Guang Cheng. Residual bootstrap exploration for bandit algorithms. arXiv preprint 2084420002.08466, 2020.
10


Reviews:
[{"review_id": "0qvP7lA3cy", "reviewer": "Reviewer_sKFK", "summary": "In multi-armed bandits (MAB), when the noise distribution is known, the UCB algorithm with a carefully constructed confidence bound achieves a gap-dependent regret depending on the noise distribution. This manuscript studies the following question: when the noise distribution is unknown, is there an algorithm that adaptively constructs the confidence bound and achieves a near-optimal regret? To answer this question, the authors used a cute observation in [Campi and Weyer, 2010]: if the distribution of a random variable is symmetric around its mean, then the sample means after subsampling (with probability 1/2) splits the real line into several equiprobable pieces for the true mean. This provides a fully data-driven approach to construct the upper confidence bound, and this manuscript shows that the resulting algorithm nearly achieves the optimal regret when the noise distribution is known. Experiments are also provided. ", "questions": "1. Could the authors say anything about adaptivity (possibility or impossibility) when the reward distribution is not symmetric around the mean? \n\n2. Theorem 3 still exhibits a gap compared with UCB with known noise distribution when Delta is large. Do you think this gap is essential (unavoidable for any algorithms), or can be closed using some other approaches? ", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall I like this paper. This paper asks a clean question and provides a satisfactory answer to it. Although the main observation comes from [Campi and Weyer, 2010], and the analysis of the algorithm essentially parallels the traditional UCB analysis, in my opinion the application to bandit problems is still nice and makes this paper interesting enough for a NeurIPS publication. ", "weaknesses": "I don't see a huge weakness of this work, but I can list some minor ones: \n\n1. The main novelty is the application of the observation in [Campi and Weyer, 2010] to a data-driven confidence bound in bandits, and everything else in the paper is pretty standard. \n\n2. The requirement that the distribution is symmetric around its mean is pretty restrictive. \n\n3. The computational complexity of the resulting algorithm could be high and may not lead to a practically useful algorithm. \n\nDespite the above concerns, I'd like to reiterate that the merits weigh more than the weaknesses in my opinion, and I still like this paper. \n\nDetailed comments: \n\nTable I: I think the probabilities on the first two rows should be swapped. \n\nSection 1: In my opinion, Section 1 should be a standalone section without resorting to bandits. In particular, the subscripts i should be removed. \n\nTheorem 2, or the case 2^T < M: is the modification in Table I really necessary for the application to MAB? After inspecting the proof, I feel that simply choosing UCB(T, delta) = \\infty whenever T < log_2(1/delta) also gives the same regret upper bound; is that true? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for insightful comments and for recognizing the utilization [Campi and Weyer, 2010] in the context of the multi-armed bandit problem.\n\n**@R1-A1) MARS performance for non-symmetric reward distributions**\n\nA new simulation was added to Supplementary material of the paper section 5 to demonstrate MARS’s performance when reward distribution is non-symmetrical. MARS was implemented when rewards have Bernoulli distribution, and the result was shown in Figure 3 supplementary material (in PDF file attached). The following text was added to the Section 5 of Supplementary material explaining the new simulation.\n\n*“To evaluate the robustness of MARS and its effectiveness where the assumption of symmetric reward distributions is not met, MARS is implemented on Bernoulli setup when the number of arms is $K = 2$ and the means are $\\mu_1=0.5$ and $\\mu_2=0.01$.\nThe findings are depicted in Figure 3 (Please refer to  (Figure 3 Supplement material) in the attached PDF file). The results indicate although the setup does not meet the symmetric assumption, yet MARS outperforms Vanilla UCB and Thompson sampling in this setup. Its performance is also comparable to that of BESA.”*\n\nAdditionally, the paper [\\*] assesses the impact of asymmetric distributions on confidence regions for model parameters using similar approach. It shows that the confidence regions remain robust to small asymmetries, showcasing the method's reliability in such scenarios.\n\n[\\*] Care, Algo, Balázs Csanád Csáji, and Marco C. Campi. \"Sign-Perturbed Sums (SPS) with asymmetric noise: Robustness analysis and robustification techniques.\" 2016 IEEE 55th Conference on Decision and Control (CDC). IEEE, 2016.\n\nThe following sentence is added to the future work below line 233 to mention above reference.\n\n*“Another interesting future direction is evaluation of the method on asymmetric rewads and robustification of approach following the same principles as proposed in the paper [\\*].”*\n\n**@R1-A2) Computational Complexity of MARS**\n\nComputational complexity of approach depends on the choice of $\\delta$ as MARS updates $\\lceil 1/\\delta \\rceil$ sub-sampled means in each round for the chosen arm. In order to address this important aspect of MARS, we added the following content after line 162\n \n*“MARS necessitates keeping $\\lceil 1/\\delta \\rceil$ sub-sampled means for each arm. This leads to a memory requirement of $O(Kn)$ when $\\delta=1/n$. The computational complexity of MARS is also depends on the choice of $\\delta$, as updating $\\lceil 1/\\delta \\rceil$ sub-sampled means is performed in each round. Notably, to reduce the computational burden, the required Bernoulli variables in the algorithm can be pre-generated and stored before the start of the game.”*\n\nTo further exploration of the efficiency of MARS and its applicability, we conducted an analysis of its runtime with alternative approaches. The relevant table can be found in the attached PDF, which has been added as an addition to Section 5 of the supplementary material.The following text also explain and analyse the result of the table.\n\n*“Table 1 displays the average runtime of different approaches for the multi-armed bandit with a Uniform setup when the number of rounds is set to $2000$. In MARS, the parameter $\\delta$ is set to $1/1000$, requiring updates of $1000$ subsampled means in each round. As a result, it takes more time compared to Vanilla UCB, Thompson Sampling, and PHE. However, MARS is faster than approaches like GIRO, which store the full memory of rewards.”*\n\n**@R1-A3) Probabilities in the first two rows need to be swapped**\n\nThe probabilities were swapped, and the typo was fixed.\n\n**@R1-A4) Section 1 can be standalone without bandits**\n\nAs suggested, this section can be treated as a standalone section introducing a new upper confidence bound for random variables. The section has been modified, and the subscripts \"i\" have been removed.\n\n**@R1-A5) By simply setting $\\text{UCB}(T, \\delta) = \\infty$ whenever $T < \\text{log}_2(1/\\delta)$, the same regret upper bound is achieved**\n\nBy doing so, equation (3) in the proof of Theorem 3 in supplementary material is not true anymore as we use:\n\n$$\\mathbb{P}\\left(\\mu_1\\geq{\\text{UCB}}_1(s,\\delta)\\right)=\\delta$$\n\nHence the modification is necessary.\n\n**@R1-A6) Does Theorem 3's gap with UCB under a known noise distribution for large Delta remain unavoidable, or can it be closed using alternative approaches**\n\nIn the current version of the algorithm, we believe this gap is unavoidable, primarily due to the assignment of infinity to UCB in the initial iterations. It is notable that the mentioned modification and assignment enables obtaining a guaranteed confidence bound for any number of observations without directly using $\\psi(\\cdot)$ function or making any other distributional assumptions on arms.\n\nWe would like to thank once again for your insightful feedback."}, {"review_id": "vGUnsYH0pw", "reviewer": "Reviewer_DQ4N", "summary": "The paper proposed a new method to compute the upper confidence bound (UCB). The new method does not require knowing or estimating the scale parameters. The property shown by Theorem 2 addresses the conservative issue of the existing methods. The practical importance of free from modeling the scale parameters is verified in the experiments.", "questions": "- (g) The symmetric assumption restricts the applicability of this submission. Can we remove it? What would the challenge(s) be?\n- (h) Visualizing the differences between the choice of scale parameters (Figure 1) and the choice of prior (Figure 2) is nice. Is it possible to demonstrate the difference between the conservative approaches (Lines 51--54) and the non-conservative (Lines 141--143) UCBs?\n- (i) Between the scale-free (this submission) and the scale-aware (baselines compared in this submission) approaches, another approach would be estimating the unknown scale parameters. If some scale-estimation approach does not require the symmetric assumption, it might be a strong baseline to be compared. A related paper would be (http://proceedings.mlr.press/v119/zhu20d/zhu20d.pdf).", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- (a) The paper contributes a new way to compute UCBs of practical importance; it does not require scale information.\n- (b) Rigorous theoretical analysis.\n- (c) Experiments demonstrate the advantage of the proposed UCBs.", "weaknesses": "- (d) What are typical values? It is defined in Definition 1, but its intuition and usage are unclear. Also, it would be great to explain the typical value's role in proving Theorem 2 (the only mention I saw of it is in the proof of Proposition 2).\n- (e) Maybe adding a discussion (after Line 192) about recovering the worst-case bound would make the paper more complete?\n- (f) Is it better to start the paper with an Introduction?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer for insightful comments and positive feedback on the conducted theoretical analysis.\n\n**@R2-A1) What are typical values? It is defined in Definition 1, but its intuition and usage are unclear. Also, it would be great to explain the typical value's role in proving Theorem 2 (the only mention I saw of it is in the proof of Proposition 2).**\n\nThe typical values in Definitions 1 consist of random variables that partition the real line into equally probable segments, where the true mean is positioned within one of these segments with identical probability. Theorem 1 proves that the mean calculated from sub-samples (with a probability of $1/2$) forms a set of typical values. This concept helps to establish a guaranteed upper confidence bound, as shown by Theorem 2 without using any concentration inequalities which are often conservative and including scaling parameters. Typical values is crucial in the proof of theorem 2 which was later used in algorithm and regret analysis.\n\nTo clarify that point, the following sentence is included after Theorem 1.\n\n*“Theorem 1 shows that $M-1$ estimates of mean computed by random sub-sampling are a set of typical values for $\\mu_i$ and partition the real line into equiprobable segments where $\\mu_i$ belong to each one of those segments with equal probability.”*\n\n**@R2-A2) Maybe adding a discussion (after Line 192) about recovering the worst-case bound would make the paper more complete?**\n\nTo clarify the regret bound lines 187-192 is revised as below\n\n*“As shown in equation (6), the regret bound for MARS is always $O(\\log(n))$ without relying on the use of $\\psi(\\cdot)$. When $\\psi_i^\\*(\\Delta_i)<1.59$, the task becomes more challenging as identifying the optimal arms becomes harder. In such scenarios, both the regret bounds for the proposed MARS and the $\\psi$-UCB, which employs $\\psi(\\cdot)$, become dependent on the function ${\\log(n)}/{\\psi_i^\\*(\\cdot)}$. This demonstrates the effectiveness of the introduced non-parametric UCB method.\nCorollary 1 also explore the effectiveness of MARS when dealing with subgaussian rewards. It demonstrates that even without prior knowledge of the $\\sigma_i$ values, MARS successfully addresses bandit problems, achieving a regret bound of $O(\\sum_{i:\\Delta_i>0}\\log(n)/\\Delta_i)$  for challenging scenarios where $(\\Delta_i^2)/(2\\sigma_i^2)<1.59$.”*\n\n**@R2-A3) Is it better to start the paper with an Introduction?**\n\nThe lines 17 to 96  of the paper  was  contained in a section labelled Introduction as proposed.\n\n**@R2-A4) The symmetric assumption restricts the applicability of this submission. Can we remove it? What would the challenge(s) be?**\n\nPlease see the first response in reviewer 1’s rebuttal labelled **@R1-A1** \n\n**@R2-A5) Visualizing the differences between the choice of scale parameters (Figure 1) and the choice of prior (Figure 2) is nice. Is it possible to demonstrate the difference between the conservative approaches (Lines 51--54) and the non-conservative (Lines 141--143) UCBs?**\n\nIn Section 3-Experiment a comparison among MARS using a non-conservative UCB and other methods were done. Two more methods GIRO and PHE were also added to the simulation which are available in the figure in PDF attached.\n\nThe Vanila UCB in those simulations uses a concentration inequality including a scaling parameter. \nThe Thompson sampling implemented in that section uses Gaussian prior. The performance of these methods was assessed and compared with that of MARS, along with several others. \n\n**@R2-A6) Between the scale-free (this submission) and the scale-aware (baselines compared in this submission) approaches, another approach would be estimating the unknown scale parameters. If some scale-estimation approach does not require the symmetric assumption, it might be a strong baseline to be compared. A related paper would be (mlr.press/v119/zhu20d/zhu20d.pdf).**\n\nWe appreciate your suggestion regarding the comparison of MARS with methods that estimate unknown scale parameters. In line with your concerns about enhancing empirical evaluation and conducting comparative analyses with alternative approaches, we added additional simulations into the paper. \n\nAs an example, we conducted a comparison of MARS with six alternative approaches within a multi-armed bandit setup with exponential distribution. The outcomes of this comparison are presented in “Figure 3 in Supplement” of the Supplementary section, available in the attached PDF. Among these six approaches, BESA (referred to as BESAMULTI) is a scale-free algorithm that selects arms through duels. As illustrated in the figure, MARS demonstrates superior performance over BESA within this exponential configuration. \n\nFor additional empirical assessments and comparisons, please see response labelled as  **@R3-A1** in Rebuttal for Reviewer 3.\n\nWe would like to thank once again for your insightful feedback."}, {"review_id": "2MYAwFTztn", "reviewer": "Reviewer_GPeu", "summary": "The paper presents a new approach to develop a data-dependent upper confidence bound to replace the classical UCB based on concentration inequalities. The data-dependent bound is constructed using sub-sampling of rewards and offers a tighter estimate on the error than the classical UCB resulting in improved performance.", "questions": "See above.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The approach adopted in the paper is quite interesting and seems to be significantly simpler than existing studies on data-dependent bounds. Although Theorem 1 is based on an existing result, its application to bandits is interesting and I haven't seen that before.", "weaknesses": "I am convinced that there is some novelty in the paper, especially on the theoretical aspect. However, I feel that it may not be sufficient for a paper like this to warrant a publication. While data-dependent bounds are interesting to study and analyze, they themselves have little to offer in terms of advancing the theoretical understanding of multi-armed bandits. These collection of studies that focus on data-dependent bounds are, at a fundamental level, studies that focus on improving practical implementation of MAB. Specifically, as pointed out even by the authors, the classical UCB requires some additional information, that is often difficult to obtain in practice, thereby making such data-dependent approaches a practical alternative.\n\nFor a result that is fundamentally based on improving practical implementation, the paper has very limited empirical evaluation. I strongly suggest that the authors add more detailed empirical evaluation, both in terms of comparison with more algorithms like GIRO and PHE and in terms of more complicated examples, preferably a real world example. \n\nA more extensive empirical evaluation will demonstrate the actual improvement offered in practice by this new data-dependent estimator and the existing theoretical results will _support_ and _explain_ those results, making a strong overall paper.\n\nI am willing to increase my score if the authors can add more detailed experiments with proper analysis. I do understand that the rebuttal period might not be sufficient for that in which case, I suggest the authors to resubmit with more experiments. The results definitely seem promising. \n\nEDIT: Score updated based on rebuttal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your recognition of the theoretical novelty presented in our work. To address your concerns regarding the empirical evaluation of MARS several experiments were added to the paper described below:\n\n__@R3-A1) Enhancing Empirical Evaluation of MARS in Paper__\n\nAs proposed GIRO and PHE were implemented and compared with MARS in all setups, i.e., Gaussian,Truncated Gaussian, Uniform, Exponential, and Bernouli. The specifics of these changes are outlined below.\nThe attached PDF file contains updated versions of Figures 2(a), 2(b), and 3. The original Figures 2(a), 2(b), and 3 were replaced with these new versions. After adding the new simulations and experiments, we revised the Section 3 and lines 194 to 220 were replaced with the following text.\n\n*“First, consider the rewards corresponding to all arms are Gaussian with variance 1. The cumulative regrets are show in Figure 1 (a). Since Normal-TS uses the distribution knowledge and the variances are correct in this case it is the best as expected. The Vanilla UCB algorithm demonstrates comparable or superior performance compared to both the Bootstrapped UCB, MARS, and GIRO. The performance of the PHE approach is heavily dependent on the parameter $a$. When $a=2.1$, it shows a linear regret. However, for $a=5.1$, it outperforms most other approaches, except for Thompson sampling.*\n\n*Both Vanilla UCB and Normal-TS depend on the variances which were assumed known in the previous simulation. We repeat the former simulation where the variances are incorrectly set to 2. The result is shown in Figure 2(b). Evidently MARS, GIRO, and Bootstrapped UCB outperform both Vanilla UCB and Normal-TS when incorrect values for variances are used. MARS demonstrates superior performance over Bootstrapped UCB and GIRO after an initial set of rounds. Moreover, unlike GIRO and Bootstrapped UCB, MARS does not require the full storage of reward history, resulting in lower computational complexity. As previously observed, PHE with a value of 2.1 demonstrated the poorest performance, whereas PHE with a value of 5.1 has the best performance.*\n\n*The MARS and GIRO does not use the tail information of the rewards. However, Vanilla UCB, Normal-TS, and Bootstrapped UCB use the distribution and the tail information of the rewards respectively and their performance can deteriorate when the prior knowledge is wrong or conservative.*\n\n*To illustrate this we repeated the simulation for the cases where the rewards admit uniform distribution over $[-1, 1]$. The results are shown in Figure 3. It shows that MARS which does not use the distribution of the rewards and the tail information, outperforms the other methods except PHE ($a=2.1$) in this case. An intriguing observation is that PHE ($a=5.1$) exhibits outstanding performance in a Gaussian setup, yet it performs poorly in a Uniform setup, indicating a strong reliance on the tunable parameter. This dependence on the parameter could pose challenges in real-world applications where the environment is unknown. Consequently, making methods like MARS and GIRO more practical alternatives.*\n\n*For additional simulations in the exponential setup and Gaussian setup, refer to Section 5 in the supplement.”*\n\n__@R3-A2) Enhancing Empirical Evaluation of MARS in Supplementary material__\n\nThree simulations were included in section 5 of supplementary material. The attached PDF file contains revised versions of Figures 1 and 2 in the supplementary. A new simulation and table were added to the supplementary to assess MARS for non-symmetric distributions and compare its runtime with other approaches. Detailed explanations of these additional simulations are provided herein.\n\n__(Truncated Gaussian Setup):__  Methods GIRO, PHE were added to the simulation and the explanation is changed as below\n\n*“The numerical experiment conducted in Section 3 of the main paper is replicated in Figure 1, utilizing Gaussian rewards truncated within the range of $[-1, 1]$. In line with the uniformly distributed rewards presented in the main paper, the results shows that MARS outperforms the other methods except PHE (a=2.1) thanks to not utilizing reward distribution and tail information.”*\n\n**(Exponential Setup)** New methods, GIRO, PHE was added to the simulation, leading to modifications in the explanations.\n\n*“MARS is a well-suited method for handling a wide range of symmetrically distributed rewards, as it does not rely on tail information. In this context, we replicate the numerical experiment from Section 3 of the main paper, using exponentially distributed rewards.\nIn this experiment, we also include a comparison of MARS with the BESA approach using sub-sampling [5], to provide a comprehensive evaluation. Figure 2 clearly demonstrates that MARS outperforms the other methods including BESA, PHE (a=2.1), and PHE (5.1).”*\n\n__@R3-A3) Runtime Analysis of the MARS__\n\nTo further exploration of the efficiency of MARS and its applicability in real-world scenarios, we conducted an analysis of its runtime with alternative approaches. Please see **@R1-A2** or further details.\n\n__@R3-A4) MARS performance for non-symmetric reward distributions (Bernoulli)__\n\n The Bernoulli Bandit is a framework for tackling various real-world challenges, like online advertising, where advertisers must make prompt decisions on which ad to present to a user to maximize the likelihood of the user clicking on the ad.\n\nIn this scenario, the assumption of MARS, i.e., rewards are distributed symmetrically around the mean, is not satisfied. To evaluate the robustness of MARS and its effectiveness in real-world applications when not all assumptions hold true, we implement MARS in the this setup. Through this evaluation, we can gain insights into MARS's suitability and performance in practical applications despite deviations from ideal assumptions. Please see **@R1-A1** for further details.\n\nWe would like to thank once again for the time, effort and your insightful feedback."}, {"review_id": "7Tgf8ak4GO", "reviewer": "Reviewer_t4Bj", "summary": "The authors propose a novel non-parametric algorithm for stochastic bandits, based on a sub-sampling scheme. While other algorithms using sub-sampling have been recently proposed, their approach significantly differs from these works. Indeed, instead of using sub-sampling to perform pairwise comparisons, they use it to build exact confidence intervals used in a UCB algorithm called MARS. To do that, they build on results provided by statisticians in the 60s and 70s, showing that sub-sampling can be used to build a set of *typical values* for the true mean of each distribution.\n\nAfter describing their method, the authors provide the theoretical guarantees of MARS: logarithmic regret under the assumption that the distributions are continuous and symmetric, and some exponential moment condition similar to the one used for $\\psi$-UCB. Interestingly, these guarantees are achieved while the algorithm does not use the function $\\phi$ directly, hence avoiding sub-optimal choices of $\\psi$, which is the advantage of non-parametric algorithms.\n\nThen, a set of experiments aim at validating the method.", "questions": "* The statistical validity of the estimator holds for large enough sample size. For smaller sample sizes, the author build a UCB using the *maximum of observed data and a fixed probability of returning $\\infty$ to keep the $\\delta$ confidence. At first read, this step is a bit confusing, and It may have been easier to simply provide the required $\\log(n)/\\log(2)$ samples per arm at the initialization of the algorithm. Is there an empirical motivation for not doing that (because from the theoretical point of view this do not seem to change much)?  \n* Related question: is it clear that the $2^{-T_i(n)}$ is tight? Since it is critical in terms of computation/memory cost it may be interesting to optimize it.\n* It would be interesting to understand how good the theoretical results are. You started to do that by comparing them with $\\psi$-UCB and the usual bound with $\\Delta^2$. Did you try to look at the Burnetas & Katehakis lower bound for this specific family of distributions?\n* Did you investigate an anytime version of MARS? It seems to me that the proof may easily adapt, making the algorithm more flexible.", "limitations": "No potential societal impact.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I think that the paper is overall well-written and clear, and that the algorithm and theoretical results are well presented and easy to understand. \n\nWhile the literature in bandits is now quite vast, it is difficult to come up with new principles, especially in the standard stochastic case. Recently, the literature on non-parametric algorithms based on bootstrap and sub-sampling has proposed interesting new approaches, and this paper is in my opinion a nice addition to this literature, showing new potentialities. In particular, the theoretical guarantees hold under original assumptions, for which no other algorithms is proved to work (additional assumptions would be needed). Furthermore, the empirical results validate the approach.\n\nOverall, I think that the paper brings enough interesting insights for publication at Neurips, up to some changes listed below. The derivation of the technical results seem correct to me.", "weaknesses": "In my opinion the paper has two major weaknesses, that are related:\n\n* I believe that in the context of the paper the literature review on non-parametric algorithms should be more precise, and the contribution of MARS compared to these approaches should be better explained. First, the presented algorithms are not all based on \"subsampling\", GIRO, PHE, Bootstrap-UCB and Reboot are closer to bootstrap, while only BESA and SDA are technically speaking based on sub-sampling. Those approaches are rather different, work under different assumptions, and do not share the same pros and cons. \n\nFurthermore, the last line \"One drawback of...\" is misleading, and make the reader believe that the said drawbacks are shared by all these algorithms, would be solved by MARS, and are in fact the motivation for MARS; while it seems to me that this all these perceived messages are wrong. \n\nIn my opinion, there are several axis that should be detailed when talking about these algorithms: the family of distributions for which they work (and maybe how tight are their guarantees for these families), what they need to know about the distributions, and their cost (memory and time). For instance, PHE is a faster and memory-less alternative to GIRO, but its guarantees are sub-optimal and restricted to bounded distributions, and there is a tunable parameter (but this method easily generalize to structured settings, which is its main strength). On the other hand, SDA works in much broader setting (families of distributions for which a \"balance\" condition is satisfied), but this generality costs the fact of storing all observations in memory: this is in my opinion similar to what is obtained with MARS. Furthermore, the question of improving the computation time and memory for SDA has been studied for the LB-SDA algorithm (http://proceedings.mlr.press/v139/baudry21b/baudry21b.pdf). \n\n* (Related) the memory and computation time of MARS are not well discussed. In particular, it seems worse than most existing approaches: maintaining the sub-sample means for each arm costs $O(Kn^2)$ (if $\\delta=1/n^2$ is set), while at most $O(n)$ is needed for the benchmarks. Furthermore, the update of the UCB also requires to sample $n^2$ Bernoulli variables at each time step, which is also much larger the cost of (even the less \"optimized\") existing non-parametric approach. Those are major drawbacks in my opinion, that should be explicitly discussed, providing comparisons with benchmarks. However, this does not mean than the approach is not interesting: I believe that the authors should really focus on the fact that their algorithms have guarantees under original assumptions for which there are no competitors (or no tight competitors).\n\n* The contribution of the paper is not on the technical side, most results and techniques used by the authors are known, but I think that it is interesting enough so that it is not an issue.\n\n* I find the set of experiments not very convincing: only a few curves/benchmark algorithms are used, and I don't understand why $\\delta$ is not set to the theoretically valid threshold ($4\\times 10^{-6}$). In my opinion SDA (for instance LB-SDA, which is the fastest SDA) should be present in the benchmarks since it is theoretically valid for all the settings considered. I would like to see a comparison of computation times too.\n\nI believe the authors left enough space so that all these discussions could be added. In my opinion they should be carefully addressed in the revision, and I would be happy to further raise my score in that case. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank your detailed and insightful review.\n\n**@R4-A1) More precise literature review and clarification of MARS’s contribution**\n\nTo enhance the precision and accuracy of the literature review, we revised the \"Related Work\" section in the paper. The text previously present in lines 56-69 was replaced with the following content: \n\n*“Recently several works have been focused on non-parametric bandit algorithms based on subsampling and Bootstrapping [5,6,16,15,20]. Those works use the empirical distribution of the data instead of fitting a given model to the data. \nGIRO relies on the history of past observed rewards and enhances its regret bound by augmenting fake samples into the history [16]. PHE serves as a faster and memory-efficient alternative to GIRO, demonstrating adaptability to structured settings. However, PHE has the limitation of being restricted to bounded distributions and involves a tunable parameter [15]. Reboot [20] perturbs the history in order to improve the regret bound.*\n\n*Bootstrapping Upper Confidence Bound is using bootstrap to construct sharper confidence intervals in UCB-type algorithm [11]. However, it used a second-order correction to guarantee the non-asymptotic validity of the bootstrap threshold. The second-order correction is not sharp, and it includes some scaling factors.*\n\n*Another line of works including BESA [5] and SDA [6]  use subsampling to conduct pairwise comparison (duels) between arms. BESA organize the duels between arms and find the winner by comparing the empirical average of sub-sampled rewards.  SDA extends the concept of BESA duels to a round-based structure by incorporating a sub-sampling scheme and it eliminates the need for forced exploration.*\n\n*Apart from Reboot which was analysed for Gaussian distributions, and SDA which was analysed for a family of distribution satisfying a balance condition (namely Gaussian and Poisson), the other algorithms were analysed for distributions with known bounded support.”*\n\nThe content in line 83 of the contribution section was substituted with the following information to provide a clearer explanation of MARS's contribution.\n\n*“MARS achieves logarithmic regret without using the function $\\psi(\\cdot)$. Hence it avoids sub-optimal choices of $\\psi(\\cdot)$”*\n\n**@R4-A2) Memory and Computational Complexity of MARS**\n\nWe agreed with the reviewers' observations concerning the computational complexity and memory aspects of the MARS. In order to address this important aspect, we added a paragraph after line 162. Please see Review 1’s Rebuttal section labelled **@R1-A2** for the paragraph and further details.\n\nWe conducted an analysis of its runtime with alternative approaches. The relevant table can be found in the attached PDF, which has been added as an addition to Section 5 of the supplementary material. Please see **@R1-A2** for the added text explaining the result of the table.\n\n**@R4-A3) Assessing the Quality of Theoretical Results and Examination of the Burnetas & Katehakis Lower Bound**\n\nThe current version presents the logarithmic upper bound for regret without directly utilizing $\\psi(\\cdot)$. We find the idea of exploring the possibility of establishing a lower bound for regret to be another interesting path for further theoretical investigation of MARS. We sincerely appreciate your valuable suggestion.\n\n**@R4-A4) Necessity of constructing a UCB using either the maximum of observed reward or infinity and possibility of alternative approach providing the necessary log(n)/log(2) samples per arm during the initialization phase**\n\nThe mentioned modification enables obtaining a guaranteed confidence bound for any number of observations without directly using $\\psi(\\cdot)$ function or making any distributional assumptions on arms. The confidence bound in Table 1 was proven to be guaranteed in Theorem 2. Then, the guaranteed bound was used in proving Theorem 3. In equation (4) in supplementary material we have\n$$\\mathbb{P}\\left(\\mu_1\\geq{\\text{UCB}}_1(s,\\delta)\\right)= \\delta,$$ which implied by Theorem 2. \nProviding log(n)/log(2) samples per arm does not guarantee a confidence region for all values of $\\delta$ within the range (0,1).\n\nIt is important to note that Table 1 contains a typo, regarding the placement of probabilities in front of \"w.p.\" The probabilities was swapped. The probability of assigning infinity to the upper confidence bound is not constant; rather, it diminishes as the number of times arm $i$ is pulled ($T_i$) increases.\n\n**@R4-A5) Is $2^{T_i(n)}$ tight?**\n\nWe think the initial stage of the algorithm is inevitable since we aim to avoid using $\\psi(\\cdot)$ or any tail information. MARS is in this phase for each arm when $T_t$ is less than $\\log(\\delta-1)/\\log(2)$. For example, when \\delta=10^-6, the initial phase occurs for $T_i<2\\log(10^6)/\\log(2)=39.87$.  \n\nIt is important to note that we demonstrated that this approach yields logarithmic regret with the proposed initial phase.\n\n**@R4-A6) empirical evaluation and numerical experiments**\n\nPlease see Review 3’s Rebuttal, sections labelled **@R3-A1, @R3-A2, @R3-A4**. \n\n**@R4-A7) why $\\delta$ is not set to the theoretically valid threshold $4×10^{-6}$**\n\nThe guidance provided in the book [17] on pages 104 proposes the following: \n\n_“This suggests we might choose $\\delta \\approx 1/n$ …”_\n\nAs a result, we choose a $\\delta=1/1000$. To be fair, the selection of $\\delta$ for both Vanilla UCB and Bootstrap UCB is the same.\n\n**@R4-A8) Anytime version of MARS**\n\nAlong the same line of Theorem 2.1's proof on Page 11 of reference [7], we can derive a logarithmic upper bound for regret by selecting $\\delta_t = 1/{t^2}$.\n\nWe would like to thank once again for the time, effort and your insightful feedback."}]

Author rebuttal:
We thank the reviewers for their valuable and generally positive feedback. We are encouraged that the reviewers found our work novel in terms of *“used a cute observation in [8] [...] provides a fully data-driven approach to construct the upper confidence bound, and this manuscript shows that the resulting algorithm nearly achieves the optimal regret [...]”* (**R1**), *“Rigorous theoretical analysis”* (**R2**), *“[...] quite interesting and seems to be significantly simpler than existing studies on data-dependent bounds”* (**R3**), *“Interestingly, these guarantees are achieved while the algorithm does not use the function  directly, hence avoiding sub-optimal choices of  [...]”* (**R4**), and *“Recently, the literature on non-parametric algorithms based on bootstrap and sub-sampling has proposed interesting new approaches, and this paper is in my opinion a nice addition to this literature, showing new potentialities”* (**R4**). 

Before discussing the main changes and added empirical evaluations, it worthwhile to mention a few points about rebuttals.

+ The numbered citations refer to references in the submitted paper. The additional citations are labelled by [\*]. 

+ As two new algorithms were added to all simulations and Figure 2 (a), Figure 2 (b), and Figure 3 in the paper and Figure 1, 2 in the supplementary material were replaced with the new figures found in the attached PDF file. One new figure and table was added to the paper, both of which available in the provided PDF. The figures referenced in all our responses to reviews are the new figures in the attached PDF file. 

+ To facilitate reference and prevent redundancy, we've labelled responses to reviewers as **@R{1/2/3/4}-A{1/2/…}**, e.g. **@R2-A5** mean Answer 5 in the rebuttal letter for Reviewer 2. 

The principal modifications and enhancements made to the paper are outlined as follows:

**Improvement of empirical evaluation of approach**

As suggested by **@R3** two approaches, namely GIRO and PHE were added to all simulations and the following text was added to the paper after line 200:

*“In GIRO, the parameter $a$, which represents pseudo-rewards per unit of history, is set to $1$. Due to the high sensitivity of the PHE approach to the choice of the tunable parameter $a$, simulations were performed for two values of $a$.*

Additional simulations demonstrate the strength of MARS as a non-parametric and scale-free algorithm, exhibiting strong performance without relying on tail information. The PHE algorithm relies on an adjustable parameter. PHE with two values for that parameter was added to experiments. Interestingly, the parameter that performed remarkably well in the Gaussian setup exhibited the weakest performance in the uniform setup, and conversely, the parameter that excelled in the uniform setup displayed the poorest performance in the Gaussian setup. This contrast highlight the importance of scale-free methods like MARS in real world problems when reward distribution is unknown.

For further discussion on the added simulations please see the Review 3’s rebuttal under the heading **@R3-A1** for simulations added to the main paper and **@R3-A2** for simulations added to the supplementary material.

**Discussion on memory and computational complexity of algorithm and a simulation comparing runtime of algorithms**

To provide clarity on this significant algorithmic aspect, an additional paragraph was included in the paper, accessible at **@R1-A2**. Furthermore, a comparison of the MARS algorithm's runtime with that of other algorithms was included, and the outcomes are presented in the Table in the attached PDF. The simulations indicate that MARS is faster than GIRO, which retains the entire history of rewards. For a more detailed explanations on the runtime comparisons, please refer to **@R1-A2**.

**Revision of Literature Review and Clearer Articulation of Contributions**

As advised by **@R4** we revised the related work section to provide a more precise explanations of existing algorithms along with their respective limitations and strengths.  The main contribution of the paper which is *“MARS achieves logarithmic regret without using the function $\psi(\cdot)$. Hence it avoids sub-optimal choices of $\psi(\cdot)$”* was explained more in the section contribution. Please see **@R4-A1** for further details.

**MARS performance for non-symmetric reward distributions**

A new simulation was added to Supplementary material of the paper demonstrating MARS’s performance when reward distribution is Bernoulli (non-symmetrical). The result was shown in Figure 3 supplementary material in PDF file attached. The results indicate although the setup does not meet the symmetric assumption, yet MARS outperforms Vanilla UCB and Thompson sampling in this setup. Its performance is also comparable to that of BESA.

Moreover, robustification of the approach for asymmetric rewards was added as a topic of future research inspired by the paper [*].

[*] Care, Algo, Balázs Csanád Csáji, and Marco C. Campi. "Sign-Perturbed Sums (SPS) with asymmetric noise: Robustness analysis and robustification techniques." 2016 IEEE 55th Conference on Decision and Control (CDC). IEEE, 2016.
Please see **@R1-A1** for further details.

We would like to express our gratitude once more for the time and effort.

Meta-review: This paper provides a novel nonparametric and parameter-free algorithm for the multi-armed bandit problem. The reviewers agreed that the algorithm is novel. On the other hand, the symmetric distribution assumption is strong. The empirical evidence against this weakness is quite limiting; I wonder if it is possible to find a pathological example where it clearly suffer a linear regret.

That said, the strength outweigh the weakness, thus recommending an accept.
Decision: Accept (poster)